1 | #ifndef BOOST_CORE_BIT_HPP_INCLUDED |
2 | #define BOOST_CORE_BIT_HPP_INCLUDED |
3 | |
4 | // MS compatible compilers support #pragma once |
5 | |
6 | #if defined(_MSC_VER) && (_MSC_VER >= 1020) |
7 | # pragma once |
8 | #endif |
9 | |
10 | // boost/core/bit.hpp |
11 | // |
12 | // A portable version of the C++20 standard header <bit> |
13 | // |
14 | // Copyright 2020 Peter Dimov |
15 | // Distributed under the Boost Software License, Version 1.0. |
16 | // https://www.boost.org/LICENSE_1_0.txt |
17 | |
18 | #include <boost/config.hpp> |
19 | #include <boost/static_assert.hpp> |
20 | #include <boost/cstdint.hpp> |
21 | #include <limits> |
22 | #include <cstring> |
23 | #include <cstdlib> |
24 | |
25 | #if defined(_MSC_VER) |
26 | |
27 | # include <intrin.h> |
28 | # pragma intrinsic(_BitScanForward) |
29 | # pragma intrinsic(_BitScanReverse) |
30 | |
31 | # if defined(_M_X64) |
32 | # pragma intrinsic(_BitScanForward64) |
33 | # pragma intrinsic(_BitScanReverse64) |
34 | # endif |
35 | |
36 | # pragma warning(push) |
37 | # pragma warning(disable: 4127) // conditional expression is constant |
38 | # pragma warning(disable: 4244) // conversion from int to T |
39 | |
40 | #endif // defined(_MSC_VER) |
41 | |
42 | #if defined(BOOST_MSVC) && BOOST_MSVC >= 1925 |
43 | # define BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL |
44 | #endif |
45 | |
46 | #if defined(__has_builtin) |
47 | # if __has_builtin(__builtin_bit_cast) |
48 | # define BOOST_CORE_HAS_BUILTIN_BIT_CAST |
49 | # endif |
50 | # if __has_builtin(__builtin_bswap16) |
51 | # define BOOST_CORE_HAS_BUILTIN_BSWAP16 |
52 | # endif |
53 | #endif |
54 | |
55 | #if !defined(BOOST_CORE_HAS_BUILTIN_BIT_CAST) && (defined(BOOST_MSVC) && BOOST_MSVC >= 1926) |
56 | # define BOOST_CORE_HAS_BUILTIN_BIT_CAST |
57 | #endif |
58 | |
59 | #if !defined(BOOST_CORE_HAS_BUILTIN_BSWAP16) && (defined(BOOST_GCC) && BOOST_GCC >= 40800) |
60 | # define BOOST_CORE_HAS_BUILTIN_BSWAP16 |
61 | #endif |
62 | |
63 | namespace boost |
64 | { |
65 | namespace core |
66 | { |
67 | |
68 | // bit_cast |
69 | |
70 | #if defined(BOOST_CORE_HAS_BUILTIN_BIT_CAST) |
71 | |
72 | template<class To, class From> |
73 | BOOST_CONSTEXPR To bit_cast( From const & from ) BOOST_NOEXCEPT |
74 | { |
75 | return __builtin_bit_cast( To, from ); |
76 | } |
77 | |
78 | #else |
79 | |
80 | template<class To, class From> |
81 | To bit_cast( From const & from ) BOOST_NOEXCEPT |
82 | { |
83 | BOOST_STATIC_ASSERT( sizeof(To) == sizeof(From) ); |
84 | |
85 | To to; |
86 | std::memcpy( &to, &from, sizeof(To) ); |
87 | return to; |
88 | } |
89 | |
90 | #endif |
91 | |
92 | // countl |
93 | |
94 | #if defined(__GNUC__) || defined(__clang__) |
95 | |
96 | namespace detail |
97 | { |
98 | |
99 | BOOST_CONSTEXPR inline int countl_impl( unsigned char x ) BOOST_NOEXCEPT |
100 | { |
101 | return x? __builtin_clz( x ) - ( std::numeric_limits<unsigned int>::digits - std::numeric_limits<unsigned char>::digits ): std::numeric_limits<unsigned char>::digits; |
102 | } |
103 | |
104 | BOOST_CONSTEXPR inline int countl_impl( unsigned short x ) BOOST_NOEXCEPT |
105 | { |
106 | return x? __builtin_clz( x ) - ( std::numeric_limits<unsigned int>::digits - std::numeric_limits<unsigned short>::digits ): std::numeric_limits<unsigned short>::digits; |
107 | } |
108 | |
109 | BOOST_CONSTEXPR inline int countl_impl( unsigned int x ) BOOST_NOEXCEPT |
110 | { |
111 | return x? __builtin_clz( x ): std::numeric_limits<unsigned int>::digits; |
112 | } |
113 | |
114 | BOOST_CONSTEXPR inline int countl_impl( unsigned long x ) BOOST_NOEXCEPT |
115 | { |
116 | return x? __builtin_clzl( x ): std::numeric_limits<unsigned long>::digits; |
117 | } |
118 | |
119 | BOOST_CONSTEXPR inline int countl_impl( boost::ulong_long_type x ) BOOST_NOEXCEPT |
120 | { |
121 | return x? __builtin_clzll( x ): std::numeric_limits<boost::ulong_long_type>::digits; |
122 | } |
123 | |
124 | } // namespace detail |
125 | |
126 | template<class T> |
127 | BOOST_CONSTEXPR int countl_zero( T x ) BOOST_NOEXCEPT |
128 | { |
129 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
130 | |
131 | return boost::core::detail::countl_impl( x ); |
132 | } |
133 | |
134 | #else // defined(__GNUC__) || defined(__clang__) |
135 | |
136 | namespace detail |
137 | { |
138 | |
139 | #if defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL) |
140 | |
141 | BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
142 | { |
143 | if( __builtin_is_constant_evaluated() ) |
144 | { |
145 | constexpr unsigned char mod37[ 37 ] = { 32, 31, 6, 30, 9, 5, 0, 29, 16, 8, 2, 4, 21, 0, 19, 28, 25, 15, 0, 7, 10, 1, 17, 3, 22, 20, 26, 0, 11, 18, 23, 27, 12, 24, 13, 14, 0 }; |
146 | |
147 | x |= x >> 1; |
148 | x |= x >> 2; |
149 | x |= x >> 4; |
150 | x |= x >> 8; |
151 | x |= x >> 16; |
152 | |
153 | return mod37[ x % 37 ]; |
154 | } |
155 | else |
156 | { |
157 | unsigned long r; |
158 | |
159 | if( _BitScanReverse( &r, x ) ) |
160 | { |
161 | return 31 - static_cast<int>( r ); |
162 | } |
163 | else |
164 | { |
165 | return 32; |
166 | } |
167 | } |
168 | } |
169 | |
170 | BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint8_t x ) BOOST_NOEXCEPT |
171 | { |
172 | return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 24; |
173 | } |
174 | |
175 | BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
176 | { |
177 | return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 16; |
178 | } |
179 | |
180 | #elif defined(_MSC_VER) |
181 | |
182 | inline int countl_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
183 | { |
184 | unsigned long r; |
185 | |
186 | if( _BitScanReverse( &r, x ) ) |
187 | { |
188 | return 31 - static_cast<int>( r ); |
189 | } |
190 | else |
191 | { |
192 | return 32; |
193 | } |
194 | } |
195 | |
196 | inline int countl_impl( boost::uint8_t x ) BOOST_NOEXCEPT |
197 | { |
198 | return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 24; |
199 | } |
200 | |
201 | inline int countl_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
202 | { |
203 | return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 16; |
204 | } |
205 | |
206 | #else |
207 | |
208 | inline int countl_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
209 | { |
210 | static unsigned char const mod37[ 37 ] = { 32, 31, 6, 30, 9, 5, 0, 29, 16, 8, 2, 4, 21, 0, 19, 28, 25, 15, 0, 7, 10, 1, 17, 3, 22, 20, 26, 0, 11, 18, 23, 27, 12, 24, 13, 14, 0 }; |
211 | |
212 | x |= x >> 1; |
213 | x |= x >> 2; |
214 | x |= x >> 4; |
215 | x |= x >> 8; |
216 | x |= x >> 16; |
217 | |
218 | return mod37[ x % 37 ]; |
219 | } |
220 | |
221 | inline int countl_impl( boost::uint8_t x ) BOOST_NOEXCEPT |
222 | { |
223 | return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 24; |
224 | } |
225 | |
226 | inline int countl_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
227 | { |
228 | return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 16; |
229 | } |
230 | |
231 | #endif |
232 | |
233 | #if defined(_MSC_VER) && defined(_M_X64) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL) |
234 | |
235 | BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
236 | { |
237 | if( __builtin_is_constant_evaluated() ) |
238 | { |
239 | return static_cast<boost::uint32_t>( x >> 32 ) != 0? |
240 | boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x >> 32 ) ): |
241 | boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) + 32; |
242 | } |
243 | else |
244 | { |
245 | unsigned long r; |
246 | |
247 | if( _BitScanReverse64( &r, x ) ) |
248 | { |
249 | return 63 - static_cast<int>( r ); |
250 | } |
251 | else |
252 | { |
253 | return 64; |
254 | } |
255 | } |
256 | } |
257 | |
258 | #elif defined(_MSC_VER) && defined(_M_X64) |
259 | |
260 | inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
261 | { |
262 | unsigned long r; |
263 | |
264 | if( _BitScanReverse64( &r, x ) ) |
265 | { |
266 | return 63 - static_cast<int>( r ); |
267 | } |
268 | else |
269 | { |
270 | return 64; |
271 | } |
272 | } |
273 | |
274 | #elif defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL) |
275 | |
276 | BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
277 | { |
278 | return static_cast<boost::uint32_t>( x >> 32 ) != 0? |
279 | boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x >> 32 ) ): |
280 | boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) + 32; |
281 | } |
282 | |
283 | #else |
284 | |
285 | inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
286 | { |
287 | return static_cast<boost::uint32_t>( x >> 32 ) != 0? |
288 | boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x >> 32 ) ): |
289 | boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) + 32; |
290 | } |
291 | |
292 | #endif |
293 | |
294 | } // namespace detail |
295 | |
296 | template<class T> |
297 | BOOST_CXX14_CONSTEXPR int countl_zero( T x ) BOOST_NOEXCEPT |
298 | { |
299 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
300 | |
301 | BOOST_STATIC_ASSERT( sizeof(T) == sizeof(boost::uint8_t) || sizeof(T) == sizeof(boost::uint16_t) || sizeof(T) == sizeof(boost::uint32_t) || sizeof(T) == sizeof(boost::uint64_t) ); |
302 | |
303 | BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint8_t) ) |
304 | { |
305 | return boost::core::detail::countl_impl( static_cast<boost::uint8_t>( x ) ); |
306 | } |
307 | else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint16_t) ) |
308 | { |
309 | return boost::core::detail::countl_impl( static_cast<boost::uint16_t>( x ) ); |
310 | } |
311 | else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint32_t) ) |
312 | { |
313 | return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ); |
314 | } |
315 | else |
316 | { |
317 | return boost::core::detail::countl_impl( static_cast<boost::uint64_t>( x ) ); |
318 | } |
319 | } |
320 | |
321 | #endif // defined(__GNUC__) || defined(__clang__) |
322 | |
323 | template<class T> |
324 | BOOST_CONSTEXPR int countl_one( T x ) BOOST_NOEXCEPT |
325 | { |
326 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
327 | |
328 | return boost::core::countl_zero( static_cast<T>( ~x ) ); |
329 | } |
330 | |
331 | // countr |
332 | |
333 | #if defined(__GNUC__) || defined(__clang__) |
334 | |
335 | namespace detail |
336 | { |
337 | |
338 | BOOST_CONSTEXPR inline int countr_impl( unsigned char x ) BOOST_NOEXCEPT |
339 | { |
340 | return x? __builtin_ctz( x ): std::numeric_limits<unsigned char>::digits; |
341 | } |
342 | |
343 | BOOST_CONSTEXPR inline int countr_impl( unsigned short x ) BOOST_NOEXCEPT |
344 | { |
345 | return x? __builtin_ctz( x ): std::numeric_limits<unsigned short>::digits; |
346 | } |
347 | |
348 | BOOST_CONSTEXPR inline int countr_impl( unsigned int x ) BOOST_NOEXCEPT |
349 | { |
350 | return x? __builtin_ctz( x ): std::numeric_limits<unsigned int>::digits; |
351 | } |
352 | |
353 | BOOST_CONSTEXPR inline int countr_impl( unsigned long x ) BOOST_NOEXCEPT |
354 | { |
355 | return x? __builtin_ctzl( x ): std::numeric_limits<unsigned long>::digits; |
356 | } |
357 | |
358 | BOOST_CONSTEXPR inline int countr_impl( boost::ulong_long_type x ) BOOST_NOEXCEPT |
359 | { |
360 | return x? __builtin_ctzll( x ): std::numeric_limits<boost::ulong_long_type>::digits; |
361 | } |
362 | |
363 | } // namespace detail |
364 | |
365 | template<class T> |
366 | BOOST_CONSTEXPR int countr_zero( T x ) BOOST_NOEXCEPT |
367 | { |
368 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
369 | |
370 | return boost::core::detail::countr_impl( x ); |
371 | } |
372 | |
373 | #else // defined(__GNUC__) || defined(__clang__) |
374 | |
375 | namespace detail |
376 | { |
377 | |
378 | #if defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL) |
379 | |
380 | BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
381 | { |
382 | if( __builtin_is_constant_evaluated() ) |
383 | { |
384 | constexpr unsigned char mod37[ 37 ] = { 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 }; |
385 | return mod37[ ( -(boost::int32_t)x & x ) % 37 ]; |
386 | } |
387 | else |
388 | { |
389 | unsigned long r; |
390 | |
391 | if( _BitScanForward( &r, x ) ) |
392 | { |
393 | return static_cast<int>( r ); |
394 | } |
395 | else |
396 | { |
397 | return 32; |
398 | } |
399 | } |
400 | } |
401 | |
402 | BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint8_t x ) BOOST_NOEXCEPT |
403 | { |
404 | return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x100 ); |
405 | } |
406 | |
407 | BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
408 | { |
409 | return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x10000 ); |
410 | } |
411 | |
412 | #elif defined(_MSC_VER) |
413 | |
414 | inline int countr_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
415 | { |
416 | unsigned long r; |
417 | |
418 | if( _BitScanForward( &r, x ) ) |
419 | { |
420 | return static_cast<int>( r ); |
421 | } |
422 | else |
423 | { |
424 | return 32; |
425 | } |
426 | } |
427 | |
428 | inline int countr_impl( boost::uint8_t x ) BOOST_NOEXCEPT |
429 | { |
430 | return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x100 ); |
431 | } |
432 | |
433 | inline int countr_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
434 | { |
435 | return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x10000 ); |
436 | } |
437 | |
438 | #else |
439 | |
440 | inline int countr_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
441 | { |
442 | static unsigned char const mod37[ 37 ] = { 32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18 }; |
443 | return mod37[ ( -(boost::int32_t)x & x ) % 37 ]; |
444 | } |
445 | |
446 | inline int countr_impl( boost::uint8_t x ) BOOST_NOEXCEPT |
447 | { |
448 | return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x100 ); |
449 | } |
450 | |
451 | inline int countr_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
452 | { |
453 | return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x10000 ); |
454 | } |
455 | |
456 | #endif |
457 | |
458 | #if defined(_MSC_VER) && defined(_M_X64) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL) |
459 | |
460 | BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
461 | { |
462 | if( __builtin_is_constant_evaluated() ) |
463 | { |
464 | return static_cast<boost::uint32_t>( x ) != 0? |
465 | boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) ): |
466 | boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x >> 32 ) ) + 32; |
467 | } |
468 | else |
469 | { |
470 | unsigned long r; |
471 | |
472 | if( _BitScanForward64( &r, x ) ) |
473 | { |
474 | return static_cast<int>( r ); |
475 | } |
476 | else |
477 | { |
478 | return 64; |
479 | } |
480 | } |
481 | } |
482 | |
483 | #elif defined(_MSC_VER) && defined(_M_X64) |
484 | |
485 | inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
486 | { |
487 | unsigned long r; |
488 | |
489 | if( _BitScanForward64( &r, x ) ) |
490 | { |
491 | return static_cast<int>( r ); |
492 | } |
493 | else |
494 | { |
495 | return 64; |
496 | } |
497 | } |
498 | |
499 | #elif defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL) |
500 | |
501 | BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
502 | { |
503 | return static_cast<boost::uint32_t>( x ) != 0? |
504 | boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) ): |
505 | boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x >> 32 ) ) + 32; |
506 | } |
507 | |
508 | #else |
509 | |
510 | inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
511 | { |
512 | return static_cast<boost::uint32_t>( x ) != 0? |
513 | boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) ): |
514 | boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x >> 32 ) ) + 32; |
515 | } |
516 | |
517 | #endif |
518 | |
519 | } // namespace detail |
520 | |
521 | template<class T> |
522 | BOOST_CXX14_CONSTEXPR int countr_zero( T x ) BOOST_NOEXCEPT |
523 | { |
524 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
525 | |
526 | BOOST_STATIC_ASSERT( sizeof(T) == sizeof(boost::uint8_t) || sizeof(T) == sizeof(boost::uint16_t) || sizeof(T) == sizeof(boost::uint32_t) || sizeof(T) == sizeof(boost::uint64_t) ); |
527 | |
528 | BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint8_t) ) |
529 | { |
530 | return boost::core::detail::countr_impl( static_cast<boost::uint8_t>( x ) ); |
531 | } |
532 | else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint16_t) ) |
533 | { |
534 | return boost::core::detail::countr_impl( static_cast<boost::uint16_t>( x ) ); |
535 | } |
536 | else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint32_t) ) |
537 | { |
538 | return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) ); |
539 | } |
540 | else |
541 | { |
542 | return boost::core::detail::countr_impl( static_cast<boost::uint64_t>( x ) ); |
543 | } |
544 | } |
545 | |
546 | #endif // defined(__GNUC__) || defined(__clang__) |
547 | |
548 | template<class T> |
549 | BOOST_CONSTEXPR int countr_one( T x ) BOOST_NOEXCEPT |
550 | { |
551 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
552 | |
553 | return boost::core::countr_zero( static_cast<T>( ~x ) ); |
554 | } |
555 | |
556 | // popcount |
557 | |
558 | #if defined(__GNUC__) || defined(__clang__) |
559 | |
560 | #if defined(__clang__) && __clang_major__ * 100 + __clang_minor__ < 304 |
561 | # define BOOST_CORE_POPCOUNT_CONSTEXPR |
562 | #else |
563 | # define BOOST_CORE_POPCOUNT_CONSTEXPR BOOST_CONSTEXPR |
564 | #endif |
565 | |
566 | namespace detail |
567 | { |
568 | |
569 | BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned char x ) BOOST_NOEXCEPT |
570 | { |
571 | return __builtin_popcount( x ); |
572 | } |
573 | |
574 | BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned short x ) BOOST_NOEXCEPT |
575 | { |
576 | return __builtin_popcount( x ); |
577 | } |
578 | |
579 | BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned int x ) BOOST_NOEXCEPT |
580 | { |
581 | return __builtin_popcount( x ); |
582 | } |
583 | |
584 | BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned long x ) BOOST_NOEXCEPT |
585 | { |
586 | return __builtin_popcountl( x ); |
587 | } |
588 | |
589 | BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( boost::ulong_long_type x ) BOOST_NOEXCEPT |
590 | { |
591 | return __builtin_popcountll( x ); |
592 | } |
593 | |
594 | } // namespace detail |
595 | |
596 | #undef BOOST_CORE_POPCOUNT_CONSTEXPR |
597 | |
598 | template<class T> |
599 | BOOST_CONSTEXPR int popcount( T x ) BOOST_NOEXCEPT |
600 | { |
601 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
602 | |
603 | return boost::core::detail::popcount_impl( x ); |
604 | } |
605 | |
606 | #else // defined(__GNUC__) || defined(__clang__) |
607 | |
608 | namespace detail |
609 | { |
610 | |
611 | BOOST_CXX14_CONSTEXPR inline int popcount_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
612 | { |
613 | x = x - ( ( x >> 1 ) & 0x55555555 ); |
614 | x = ( x & 0x33333333 ) + ( ( x >> 2 ) & 0x33333333 ); |
615 | x = ( x + ( x >> 4 ) ) & 0x0F0F0F0F; |
616 | |
617 | return static_cast<unsigned>( ( x * 0x01010101 ) >> 24 ); |
618 | } |
619 | |
620 | BOOST_CXX14_CONSTEXPR inline int popcount_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
621 | { |
622 | x = x - ( ( x >> 1 ) & 0x5555555555555555 ); |
623 | x = ( x & 0x3333333333333333 ) + ( ( x >> 2 ) & 0x3333333333333333 ); |
624 | x = ( x + ( x >> 4 ) ) & 0x0F0F0F0F0F0F0F0F; |
625 | |
626 | return static_cast<unsigned>( ( x * 0x0101010101010101 ) >> 56 ); |
627 | } |
628 | |
629 | } // namespace detail |
630 | |
631 | template<class T> |
632 | BOOST_CXX14_CONSTEXPR int popcount( T x ) BOOST_NOEXCEPT |
633 | { |
634 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
635 | |
636 | BOOST_STATIC_ASSERT( sizeof(T) <= sizeof(boost::uint64_t) ); |
637 | |
638 | BOOST_IF_CONSTEXPR ( sizeof(T) <= sizeof(boost::uint32_t) ) |
639 | { |
640 | return boost::core::detail::popcount_impl( static_cast<boost::uint32_t>( x ) ); |
641 | } |
642 | else |
643 | { |
644 | return boost::core::detail::popcount_impl( static_cast<boost::uint64_t>( x ) ); |
645 | } |
646 | } |
647 | |
648 | #endif // defined(__GNUC__) || defined(__clang__) |
649 | |
650 | // rotating |
651 | |
652 | template<class T> |
653 | BOOST_CXX14_CONSTEXPR T rotl( T x, int s ) BOOST_NOEXCEPT |
654 | { |
655 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
656 | |
657 | unsigned const mask = std::numeric_limits<T>::digits - 1; |
658 | return static_cast<T>( x << (static_cast<unsigned>( s ) & mask) | x >> (static_cast<unsigned>( -s ) & mask) ); |
659 | } |
660 | |
661 | template<class T> |
662 | BOOST_CXX14_CONSTEXPR T rotr( T x, int s ) BOOST_NOEXCEPT |
663 | { |
664 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
665 | |
666 | unsigned const mask = std::numeric_limits<T>::digits - 1; |
667 | return static_cast<T>( x >> (static_cast<unsigned>( s ) & mask) | x << (static_cast<unsigned>( -s ) & mask) ); |
668 | } |
669 | |
670 | // integral powers of 2 |
671 | |
672 | template<class T> |
673 | BOOST_CONSTEXPR bool has_single_bit( T x ) BOOST_NOEXCEPT |
674 | { |
675 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
676 | |
677 | return x != 0 && ( x & ( x - 1 ) ) == 0; |
678 | } |
679 | |
680 | // bit_width returns `int` now, https://cplusplus.github.io/LWG/issue3656 |
681 | // has been applied to C++20 as a DR |
682 | |
683 | template<class T> |
684 | BOOST_CONSTEXPR int bit_width( T x ) BOOST_NOEXCEPT |
685 | { |
686 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
687 | |
688 | return std::numeric_limits<T>::digits - boost::core::countl_zero( x ); |
689 | } |
690 | |
691 | template<class T> |
692 | BOOST_CONSTEXPR T bit_floor( T x ) BOOST_NOEXCEPT |
693 | { |
694 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
695 | |
696 | return x == 0? T(0): static_cast<T>( T(1) << ( boost::core::bit_width( x ) - 1 ) ); |
697 | } |
698 | |
699 | namespace detail |
700 | { |
701 | |
702 | BOOST_CXX14_CONSTEXPR inline boost::uint32_t bit_ceil_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
703 | { |
704 | if( x == 0 ) |
705 | { |
706 | return 0; |
707 | } |
708 | |
709 | --x; |
710 | |
711 | x |= x >> 1; |
712 | x |= x >> 2; |
713 | x |= x >> 4; |
714 | x |= x >> 8; |
715 | x |= x >> 16; |
716 | |
717 | ++x; |
718 | |
719 | return x; |
720 | } |
721 | |
722 | BOOST_CXX14_CONSTEXPR inline boost::uint64_t bit_ceil_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
723 | { |
724 | if( x == 0 ) |
725 | { |
726 | return 0; |
727 | } |
728 | |
729 | --x; |
730 | |
731 | x |= x >> 1; |
732 | x |= x >> 2; |
733 | x |= x >> 4; |
734 | x |= x >> 8; |
735 | x |= x >> 16; |
736 | x |= x >> 32; |
737 | |
738 | ++x; |
739 | |
740 | return x; |
741 | } |
742 | |
743 | } // namespace detail |
744 | |
745 | template<class T> |
746 | BOOST_CXX14_CONSTEXPR T bit_ceil( T x ) BOOST_NOEXCEPT |
747 | { |
748 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed ); |
749 | |
750 | BOOST_STATIC_ASSERT( sizeof(T) <= sizeof(boost::uint64_t) ); |
751 | |
752 | BOOST_IF_CONSTEXPR ( sizeof(T) <= sizeof(boost::uint32_t) ) |
753 | { |
754 | return static_cast<T>( boost::core::detail::bit_ceil_impl( x: static_cast<boost::uint32_t>( x ) ) ); |
755 | } |
756 | else |
757 | { |
758 | return static_cast<T>( boost::core::detail::bit_ceil_impl( x: static_cast<boost::uint64_t>( x ) ) ); |
759 | } |
760 | } |
761 | |
762 | // endian |
763 | |
764 | #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ |
765 | |
766 | # define BOOST_CORE_BIT_NATIVE_INITIALIZER =little |
767 | |
768 | #elif defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ |
769 | |
770 | # define BOOST_CORE_BIT_NATIVE_INITIALIZER =big |
771 | |
772 | #elif defined(__BYTE_ORDER__) && defined(__ORDER_PDP_ENDIAN__) && __BYTE_ORDER__ == __ORDER_PDP_ENDIAN__ |
773 | |
774 | # define BOOST_CORE_BIT_NATIVE_INITIALIZER |
775 | |
776 | #elif defined(__LITTLE_ENDIAN__) |
777 | |
778 | # define BOOST_CORE_BIT_NATIVE_INITIALIZER =little |
779 | |
780 | #elif defined(__BIG_ENDIAN__) |
781 | |
782 | # define BOOST_CORE_BIT_NATIVE_INITIALIZER =big |
783 | |
784 | #elif defined(_MSC_VER) || defined(__i386__) || defined(__x86_64__) |
785 | |
786 | # define BOOST_CORE_BIT_NATIVE_INITIALIZER =little |
787 | |
788 | #else |
789 | |
790 | # define BOOST_CORE_BIT_NATIVE_INITIALIZER |
791 | |
792 | #endif |
793 | |
794 | #if !defined(BOOST_NO_CXX11_SCOPED_ENUMS) |
795 | |
796 | enum class endian |
797 | { |
798 | big, |
799 | little, |
800 | native BOOST_CORE_BIT_NATIVE_INITIALIZER |
801 | }; |
802 | |
803 | typedef endian endian_type; |
804 | |
805 | #else |
806 | |
807 | namespace endian |
808 | { |
809 | |
810 | enum type |
811 | { |
812 | big, |
813 | little, |
814 | native BOOST_CORE_BIT_NATIVE_INITIALIZER |
815 | }; |
816 | |
817 | } // namespace endian |
818 | |
819 | typedef endian::type endian_type; |
820 | |
821 | #endif |
822 | |
823 | #undef BOOST_CORE_BIT_NATIVE_INITIALIZER |
824 | |
825 | // byteswap |
826 | |
827 | namespace detail |
828 | { |
829 | |
830 | BOOST_CONSTEXPR inline boost::uint8_t byteswap_impl( boost::uint8_t x ) BOOST_NOEXCEPT |
831 | { |
832 | return x; |
833 | } |
834 | |
835 | #if defined(BOOST_CORE_HAS_BUILTIN_BSWAP16) |
836 | |
837 | BOOST_CONSTEXPR inline boost::uint16_t byteswap_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
838 | { |
839 | return __builtin_bswap16( x ); |
840 | } |
841 | |
842 | #else |
843 | |
844 | BOOST_CONSTEXPR inline boost::uint16_t byteswap_impl( boost::uint16_t x ) BOOST_NOEXCEPT |
845 | { |
846 | return static_cast<boost::uint16_t>( x << 8 | x >> 8 ); |
847 | } |
848 | |
849 | #endif |
850 | |
851 | #if defined(__GNUC__) || defined(__clang__) |
852 | |
853 | BOOST_CXX14_CONSTEXPR inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
854 | { |
855 | return __builtin_bswap32( x ); |
856 | } |
857 | |
858 | BOOST_CXX14_CONSTEXPR inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
859 | { |
860 | return __builtin_bswap64( x ); |
861 | } |
862 | |
863 | #elif defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL) |
864 | |
865 | BOOST_CXX14_CONSTEXPR inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
866 | { |
867 | if( __builtin_is_constant_evaluated() ) |
868 | { |
869 | boost::uint32_t step16 = x << 16 | x >> 16; |
870 | return ((step16 << 8) & 0xff00ff00) | ((step16 >> 8) & 0x00ff00ff); |
871 | } |
872 | else |
873 | { |
874 | return _byteswap_ulong( x ); |
875 | } |
876 | } |
877 | |
878 | BOOST_CXX14_CONSTEXPR inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
879 | { |
880 | if( __builtin_is_constant_evaluated() ) |
881 | { |
882 | boost::uint64_t step32 = x << 32 | x >> 32; |
883 | boost::uint64_t step16 = (step32 & 0x0000FFFF0000FFFFULL) << 16 | (step32 & 0xFFFF0000FFFF0000ULL) >> 16; |
884 | return (step16 & 0x00FF00FF00FF00FFULL) << 8 | (step16 & 0xFF00FF00FF00FF00ULL) >> 8; |
885 | } |
886 | else |
887 | { |
888 | return _byteswap_uint64( x ); |
889 | } |
890 | } |
891 | |
892 | #elif defined(_MSC_VER) |
893 | |
894 | inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
895 | { |
896 | return _byteswap_ulong( x ); |
897 | } |
898 | |
899 | inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
900 | { |
901 | return _byteswap_uint64( x ); |
902 | } |
903 | |
904 | #else |
905 | |
906 | BOOST_CXX14_CONSTEXPR inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT |
907 | { |
908 | boost::uint32_t step16 = x << 16 | x >> 16; |
909 | return ((step16 << 8) & 0xff00ff00) | ((step16 >> 8) & 0x00ff00ff); |
910 | } |
911 | |
912 | BOOST_CXX14_CONSTEXPR inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT |
913 | { |
914 | boost::uint64_t step32 = x << 32 | x >> 32; |
915 | boost::uint64_t step16 = (step32 & 0x0000FFFF0000FFFFULL) << 16 | (step32 & 0xFFFF0000FFFF0000ULL) >> 16; |
916 | return (step16 & 0x00FF00FF00FF00FFULL) << 8 | (step16 & 0xFF00FF00FF00FF00ULL) >> 8; |
917 | } |
918 | |
919 | #endif |
920 | |
921 | } // namespace detail |
922 | |
923 | template<class T> BOOST_CXX14_CONSTEXPR T byteswap( T x ) BOOST_NOEXCEPT |
924 | { |
925 | BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer ); |
926 | |
927 | BOOST_STATIC_ASSERT( sizeof(T) == sizeof(boost::uint8_t) || sizeof(T) == sizeof(boost::uint16_t) || sizeof(T) == sizeof(boost::uint32_t) || sizeof(T) == sizeof(boost::uint64_t) ); |
928 | |
929 | BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint8_t) ) |
930 | { |
931 | return static_cast<T>( boost::core::detail::byteswap_impl( x: static_cast<boost::uint8_t>( x ) ) ); |
932 | } |
933 | else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint16_t) ) |
934 | { |
935 | return static_cast<T>( boost::core::detail::byteswap_impl( x: static_cast<boost::uint16_t>( x ) ) ); |
936 | } |
937 | else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint32_t) ) |
938 | { |
939 | return static_cast<T>( boost::core::detail::byteswap_impl( x: static_cast<boost::uint32_t>( x ) ) ); |
940 | } |
941 | else |
942 | { |
943 | return static_cast<T>( boost::core::detail::byteswap_impl( x: static_cast<boost::uint64_t>( x ) ) ); |
944 | } |
945 | } |
946 | |
947 | } // namespace core |
948 | } // namespace boost |
949 | |
950 | #if defined(_MSC_VER) |
951 | # pragma warning(pop) |
952 | #endif |
953 | |
954 | #endif // #ifndef BOOST_CORE_BIT_HPP_INCLUDED |
955 | |