boost/core/bit.hpp

0001 #ifndef BOOST_CORE_BIT_HPP_INCLUDED
0002 #define BOOST_CORE_BIT_HPP_INCLUDED
0003
0004 // MS compatible compilers support #pragma once
0005
0006 #if defined(_MSC_VER) && (_MSC_VER >= 1020)
0007 # pragma once
0008 #endif
0009
0010 // boost/core/bit.hpp
0011 //
0012 // A portable version of the C++20 standard header <bit>
0013 //
0014 // Copyright 2020 Peter Dimov
0015 // Distributed under the Boost Software License, Version 1.0.
0016 // https://www.boost.org/LICENSE_1_0.txt
0017
0018 #include <boost/config.hpp>
0019 #include <boost/static_assert.hpp>
0020 #include <boost/cstdint.hpp>
0021 #include <limits>
0022 #include <cstring>
0023 #include <cstdlib>
0024
0025 #if defined(_MSC_VER)
0026
0027 # include <intrin.h>
0028 # pragma intrinsic(_BitScanForward)
0029 # pragma intrinsic(_BitScanReverse)
0030
0031 # if defined(_M_X64)
0032 #  pragma intrinsic(_BitScanForward64)
0033 #  pragma intrinsic(_BitScanReverse64)
0034 # endif
0035
0036 # pragma warning(push)
0037 # pragma warning(disable: 4127) // conditional expression is constant
0038 # pragma warning(disable: 4244) // conversion from int to T
0039
0040 #endif // defined(_MSC_VER)
0041
0042 #if defined(BOOST_MSVC) && BOOST_MSVC >= 1925
0043 # define BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL
0044 #endif
0045
0046 #if defined(__has_builtin)
0047 # if __has_builtin(__builtin_bit_cast)
0048 #  define BOOST_CORE_HAS_BUILTIN_BIT_CAST
0049 # endif
0050 #endif
0051
0052 #if defined(BOOST_MSVC) && BOOST_MSVC >= 1926
0053 #  define BOOST_CORE_HAS_BUILTIN_BIT_CAST
0054 #endif
0055
0056 namespace boost
0057 {
0058 namespace core
0059 {
0060
0061 // bit_cast
0062
0063 #if defined(BOOST_CORE_HAS_BUILTIN_BIT_CAST)
0064
0065 template<class To, class From>
0066 BOOST_CONSTEXPR To bit_cast( From const & from ) BOOST_NOEXCEPT
0067 {
0068     return __builtin_bit_cast( To, from );
0069 }
0070
0071 #else
0072
0073 template<class To, class From>
0074 To bit_cast( From const & from ) BOOST_NOEXCEPT
0075 {
0076     BOOST_STATIC_ASSERT( sizeof(To) == sizeof(From) );
0077
0078     To to;
0079     std::memcpy( &to, &from, sizeof(To) );
0080     return to;
0081 }
0082
0083 #endif
0084
0085 // countl
0086
0087 #if defined(__GNUC__) || defined(__clang__)
0088
0089 namespace detail
0090 {
0091
0092 BOOST_CONSTEXPR inline int countl_impl( unsigned char x ) BOOST_NOEXCEPT
0093 {
0094     return x? __builtin_clz( x ) - ( std::numeric_limits<unsigned int>::digits - std::numeric_limits<unsigned char>::digits ): std::numeric_limits<unsigned char>::digits;
0095 }
0096
0097 BOOST_CONSTEXPR inline int countl_impl( unsigned short x ) BOOST_NOEXCEPT
0098 {
0099     return x? __builtin_clz( x ) - ( std::numeric_limits<unsigned int>::digits - std::numeric_limits<unsigned short>::digits ): std::numeric_limits<unsigned short>::digits;
0100 }
0101
0102 BOOST_CONSTEXPR inline int countl_impl( unsigned int x ) BOOST_NOEXCEPT
0103 {
0104     return x? __builtin_clz( x ): std::numeric_limits<unsigned int>::digits;
0105 }
0106
0107 BOOST_CONSTEXPR inline int countl_impl( unsigned long x ) BOOST_NOEXCEPT
0108 {
0109     return x? __builtin_clzl( x ): std::numeric_limits<unsigned long>::digits;
0110 }
0111
0112 BOOST_CONSTEXPR inline int countl_impl( boost::ulong_long_type x ) BOOST_NOEXCEPT
0113 {
0114     return x? __builtin_clzll( x ): std::numeric_limits<boost::ulong_long_type>::digits;
0115 }
0116
0117 } // namespace detail
0118
0119 template<class T>
0120 BOOST_CONSTEXPR int countl_zero( T x ) BOOST_NOEXCEPT
0121 {
0122     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0123
0124     return boost::core::detail::countl_impl( x );
0125 }
0126
0127 #else // defined(__GNUC__) || defined(__clang__)
0128
0129 namespace detail
0130 {
0131
0132 #if defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL)
0133
0134 BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0135 {
0136     if( __builtin_is_constant_evaluated() )
0137     {
0138         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 };
0139
0140         x |= x >> 1;
0141         x |= x >> 2;
0142         x |= x >> 4;
0143         x |= x >> 8;
0144         x |= x >> 16;
0145
0146         return mod37[ x % 37 ];
0147     }
0148     else
0149     {
0150         unsigned long r;
0151
0152         if( _BitScanReverse( &r, x ) )
0153         {
0154             return 31 - static_cast<int>( r );
0155         }
0156         else
0157         {
0158             return 32;
0159         }
0160     }
0161 }
0162
0163 BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint8_t x ) BOOST_NOEXCEPT
0164 {
0165     return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 24;
0166 }
0167
0168 BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint16_t x ) BOOST_NOEXCEPT
0169 {
0170     return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 16;
0171 }
0172
0173 #elif defined(_MSC_VER)
0174
0175 inline int countl_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0176 {
0177     unsigned long r;
0178
0179     if( _BitScanReverse( &r, x ) )
0180     {
0181         return 31 - static_cast<int>( r );
0182     }
0183     else
0184     {
0185         return 32;
0186     }
0187 }
0188
0189 inline int countl_impl( boost::uint8_t x ) BOOST_NOEXCEPT
0190 {
0191     return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 24;
0192 }
0193
0194 inline int countl_impl( boost::uint16_t x ) BOOST_NOEXCEPT
0195 {
0196     return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 16;
0197 }
0198
0199 #else
0200
0201 inline int countl_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0202 {
0203     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 };
0204
0205     x |= x >> 1;
0206     x |= x >> 2;
0207     x |= x >> 4;
0208     x |= x >> 8;
0209     x |= x >> 16;
0210
0211     return mod37[ x % 37 ];
0212 }
0213
0214 inline int countl_impl( boost::uint8_t x ) BOOST_NOEXCEPT
0215 {
0216     return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 24;
0217 }
0218
0219 inline int countl_impl( boost::uint16_t x ) BOOST_NOEXCEPT
0220 {
0221     return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) - 16;
0222 }
0223
0224 #endif
0225
0226 #if defined(_MSC_VER) && defined(_M_X64) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL)
0227
0228 BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0229 {
0230     if( __builtin_is_constant_evaluated() )
0231     {
0232         return static_cast<boost::uint32_t>( x >> 32 ) != 0?
0233             boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x >> 32 ) ):
0234             boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) + 32;
0235     }
0236     else
0237     {
0238         unsigned long r;
0239
0240         if( _BitScanReverse64( &r, x ) )
0241         {
0242             return 63 - static_cast<int>( r );
0243         }
0244         else
0245         {
0246             return 64;
0247         }
0248     }
0249 }
0250
0251 #elif defined(_MSC_VER) && defined(_M_X64)
0252
0253 inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0254 {
0255     unsigned long r;
0256
0257     if( _BitScanReverse64( &r, x ) )
0258     {
0259         return 63 - static_cast<int>( r );
0260     }
0261     else
0262     {
0263         return 64;
0264     }
0265 }
0266
0267 #elif defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL)
0268
0269 BOOST_CXX14_CONSTEXPR inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0270 {
0271     return static_cast<boost::uint32_t>( x >> 32 ) != 0?
0272         boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x >> 32 ) ):
0273         boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) + 32;
0274 }
0275
0276 #else
0277
0278 inline int countl_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0279 {
0280     return static_cast<boost::uint32_t>( x >> 32 ) != 0?
0281         boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x >> 32 ) ):
0282         boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) ) + 32;
0283 }
0284
0285 #endif
0286
0287 } // namespace detail
0288
0289 template<class T>
0290 BOOST_CXX14_CONSTEXPR int countl_zero( T x ) BOOST_NOEXCEPT
0291 {
0292     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0293
0294     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) );
0295
0296     BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint8_t) )
0297     {
0298         return boost::core::detail::countl_impl( static_cast<boost::uint8_t>( x ) );
0299     }
0300     else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint16_t) )
0301     {
0302         return boost::core::detail::countl_impl( static_cast<boost::uint16_t>( x ) );
0303     }
0304     else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint32_t) )
0305     {
0306         return boost::core::detail::countl_impl( static_cast<boost::uint32_t>( x ) );
0307     }
0308     else
0309     {
0310         return boost::core::detail::countl_impl( static_cast<boost::uint64_t>( x ) );
0311     }
0312 }
0313
0314 #endif // defined(__GNUC__) || defined(__clang__)
0315
0316 template<class T>
0317 BOOST_CONSTEXPR int countl_one( T x ) BOOST_NOEXCEPT
0318 {
0319     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0320
0321     return boost::core::countl_zero( static_cast<T>( ~x ) );
0322 }
0323
0324 // countr
0325
0326 #if defined(__GNUC__) || defined(__clang__)
0327
0328 namespace detail
0329 {
0330
0331 BOOST_CONSTEXPR inline int countr_impl( unsigned char x ) BOOST_NOEXCEPT
0332 {
0333     return x? __builtin_ctz( x ): std::numeric_limits<unsigned char>::digits;
0334 }
0335
0336 BOOST_CONSTEXPR inline int countr_impl( unsigned short x ) BOOST_NOEXCEPT
0337 {
0338     return x? __builtin_ctz( x ): std::numeric_limits<unsigned short>::digits;
0339 }
0340
0341 BOOST_CONSTEXPR inline int countr_impl( unsigned int x ) BOOST_NOEXCEPT
0342 {
0343     return x? __builtin_ctz( x ): std::numeric_limits<unsigned int>::digits;
0344 }
0345
0346 BOOST_CONSTEXPR inline int countr_impl( unsigned long x ) BOOST_NOEXCEPT
0347 {
0348     return x? __builtin_ctzl( x ): std::numeric_limits<unsigned long>::digits;
0349 }
0350
0351 BOOST_CONSTEXPR inline int countr_impl( boost::ulong_long_type x ) BOOST_NOEXCEPT
0352 {
0353     return x? __builtin_ctzll( x ): std::numeric_limits<boost::ulong_long_type>::digits;
0354 }
0355
0356 } // namespace detail
0357
0358 template<class T>
0359 BOOST_CONSTEXPR int countr_zero( T x ) BOOST_NOEXCEPT
0360 {
0361     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0362
0363     return boost::core::detail::countr_impl( x );
0364 }
0365
0366 #else // defined(__GNUC__) || defined(__clang__)
0367
0368 namespace detail
0369 {
0370
0371 #if defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL)
0372
0373 BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0374 {
0375     if( __builtin_is_constant_evaluated() )
0376     {
0377         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 };
0378         return mod37[ ( -(boost::int32_t)x & x ) % 37 ];
0379     }
0380     else
0381     {
0382         unsigned long r;
0383
0384         if( _BitScanForward( &r, x ) )
0385         {
0386             return static_cast<int>( r );
0387         }
0388         else
0389         {
0390             return 32;
0391         }
0392     }
0393 }
0394
0395 BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint8_t x ) BOOST_NOEXCEPT
0396 {
0397     return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x100 );
0398 }
0399
0400 BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint16_t x ) BOOST_NOEXCEPT
0401 {
0402     return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x10000 );
0403 }
0404
0405 #elif defined(_MSC_VER)
0406
0407 inline int countr_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0408 {
0409     unsigned long r;
0410
0411     if( _BitScanForward( &r, x ) )
0412     {
0413         return static_cast<int>( r );
0414     }
0415     else
0416     {
0417         return 32;
0418     }
0419 }
0420
0421 inline int countr_impl( boost::uint8_t x ) BOOST_NOEXCEPT
0422 {
0423     return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x100 );
0424 }
0425
0426 inline int countr_impl( boost::uint16_t x ) BOOST_NOEXCEPT
0427 {
0428     return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x10000 );
0429 }
0430
0431 #else
0432
0433 inline int countr_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0434 {
0435     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 };
0436     return mod37[ ( -(boost::int32_t)x & x ) % 37 ];
0437 }
0438
0439 inline int countr_impl( boost::uint8_t x ) BOOST_NOEXCEPT
0440 {
0441     return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x100 );
0442 }
0443
0444 inline int countr_impl( boost::uint16_t x ) BOOST_NOEXCEPT
0445 {
0446     return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) | 0x10000 );
0447 }
0448
0449 #endif
0450
0451 #if defined(_MSC_VER) && defined(_M_X64) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL)
0452
0453 BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0454 {
0455     if( __builtin_is_constant_evaluated() )
0456     {
0457         return static_cast<boost::uint32_t>( x ) != 0?
0458             boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) ):
0459             boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x >> 32 ) ) + 32;
0460     }
0461     else
0462     {
0463         unsigned long r;
0464
0465         if( _BitScanForward64( &r, x ) )
0466         {
0467             return static_cast<int>( r );
0468         }
0469         else
0470         {
0471             return 64;
0472         }
0473     }
0474 }
0475
0476 #elif defined(_MSC_VER) && defined(_M_X64)
0477
0478 inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0479 {
0480     unsigned long r;
0481
0482     if( _BitScanForward64( &r, x ) )
0483     {
0484         return static_cast<int>( r );
0485     }
0486     else
0487     {
0488         return 64;
0489     }
0490 }
0491
0492 #elif defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL)
0493
0494 BOOST_CXX14_CONSTEXPR inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0495 {
0496     return static_cast<boost::uint32_t>( x ) != 0?
0497         boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) ):
0498         boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x >> 32 ) ) + 32;
0499 }
0500
0501 #else
0502
0503 inline int countr_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0504 {
0505     return static_cast<boost::uint32_t>( x ) != 0?
0506         boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) ):
0507         boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x >> 32 ) ) + 32;
0508 }
0509
0510 #endif
0511
0512 } // namespace detail
0513
0514 template<class T>
0515 BOOST_CXX14_CONSTEXPR int countr_zero( T x ) BOOST_NOEXCEPT
0516 {
0517     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0518
0519     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) );
0520
0521     BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint8_t) )
0522     {
0523         return boost::core::detail::countr_impl( static_cast<boost::uint8_t>( x ) );
0524     }
0525     else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint16_t) )
0526     {
0527         return boost::core::detail::countr_impl( static_cast<boost::uint16_t>( x ) );
0528     }
0529     else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint32_t) )
0530     {
0531         return boost::core::detail::countr_impl( static_cast<boost::uint32_t>( x ) );
0532     }
0533     else
0534     {
0535         return boost::core::detail::countr_impl( static_cast<boost::uint64_t>( x ) );
0536     }
0537 }
0538
0539 #endif // defined(__GNUC__) || defined(__clang__)
0540
0541 template<class T>
0542 BOOST_CONSTEXPR int countr_one( T x ) BOOST_NOEXCEPT
0543 {
0544     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0545
0546     return boost::core::countr_zero( static_cast<T>( ~x ) );
0547 }
0548
0549 // popcount
0550
0551 #if defined(__GNUC__) || defined(__clang__)
0552
0553 #if defined(__clang__) && __clang_major__ * 100 + __clang_minor__ < 304
0554 # define BOOST_CORE_POPCOUNT_CONSTEXPR
0555 #else
0556 # define BOOST_CORE_POPCOUNT_CONSTEXPR BOOST_CONSTEXPR
0557 #endif
0558
0559 namespace detail
0560 {
0561
0562 BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned char x ) BOOST_NOEXCEPT
0563 {
0564     return __builtin_popcount( x );
0565 }
0566
0567 BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned short x ) BOOST_NOEXCEPT
0568 {
0569     return __builtin_popcount( x );
0570 }
0571
0572 BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned int x ) BOOST_NOEXCEPT
0573 {
0574     return __builtin_popcount( x );
0575 }
0576
0577 BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( unsigned long x ) BOOST_NOEXCEPT
0578 {
0579     return __builtin_popcountl( x );
0580 }
0581
0582 BOOST_CORE_POPCOUNT_CONSTEXPR inline int popcount_impl( boost::ulong_long_type x ) BOOST_NOEXCEPT
0583 {
0584     return __builtin_popcountll( x );
0585 }
0586
0587 } // namespace detail
0588
0589 #undef BOOST_CORE_POPCOUNT_CONSTEXPR
0590
0591 template<class T>
0592 BOOST_CONSTEXPR int popcount( T x ) BOOST_NOEXCEPT
0593 {
0594     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0595
0596     return boost::core::detail::popcount_impl( x );
0597 }
0598
0599 #else // defined(__GNUC__) || defined(__clang__)
0600
0601 namespace detail
0602 {
0603
0604 BOOST_CXX14_CONSTEXPR inline int popcount_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0605 {
0606     x = x - ( ( x >> 1 ) & 0x55555555 );
0607     x = ( x & 0x33333333 ) + ( ( x >> 2 ) & 0x33333333 );
0608     x = ( x + ( x >> 4 ) ) & 0x0F0F0F0F;
0609
0610     return static_cast<unsigned>( ( x * 0x01010101 ) >> 24 );
0611 }
0612
0613 BOOST_CXX14_CONSTEXPR inline int popcount_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0614 {
0615     x = x - ( ( x >> 1 ) & 0x5555555555555555 );
0616     x = ( x & 0x3333333333333333 ) + ( ( x >> 2 ) & 0x3333333333333333 );
0617     x = ( x + ( x >> 4 ) ) & 0x0F0F0F0F0F0F0F0F;
0618
0619     return static_cast<unsigned>( ( x * 0x0101010101010101 ) >> 56 );
0620 }
0621
0622 } // namespace detail
0623
0624 template<class T>
0625 BOOST_CXX14_CONSTEXPR int popcount( T x ) BOOST_NOEXCEPT
0626 {
0627     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0628
0629     BOOST_STATIC_ASSERT( sizeof(T) <= sizeof(boost::uint64_t) );
0630
0631     BOOST_IF_CONSTEXPR ( sizeof(T) <= sizeof(boost::uint32_t) )
0632     {
0633         return boost::core::detail::popcount_impl( static_cast<boost::uint32_t>( x ) );
0634     }
0635     else
0636     {
0637         return boost::core::detail::popcount_impl( static_cast<boost::uint64_t>( x ) );
0638     }
0639 }
0640
0641 #endif // defined(__GNUC__) || defined(__clang__)
0642
0643 // rotating
0644
0645 template<class T>
0646 BOOST_CXX14_CONSTEXPR T rotl( T x, int s ) BOOST_NOEXCEPT
0647 {
0648     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0649
0650     unsigned const mask = std::numeric_limits<T>::digits - 1;
0651     return static_cast<T>( x << (static_cast<unsigned>( s ) & mask) | x >> (static_cast<unsigned>( -s ) & mask) );
0652 }
0653
0654 template<class T>
0655 BOOST_CXX14_CONSTEXPR T rotr( T x, int s ) BOOST_NOEXCEPT
0656 {
0657     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0658
0659     unsigned const mask = std::numeric_limits<T>::digits - 1;
0660     return static_cast<T>( x >> (static_cast<unsigned>( s ) & mask) | x << (static_cast<unsigned>( -s ) & mask) );
0661 }
0662
0663 // integral powers of 2
0664
0665 template<class T>
0666 BOOST_CONSTEXPR bool has_single_bit( T x ) BOOST_NOEXCEPT
0667 {
0668     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0669
0670     return x != 0 && ( x & ( x - 1 ) ) == 0;
0671 }
0672
0673 // bit_width returns `int` now, https://cplusplus.github.io/LWG/issue3656
0674 // has been applied to C++20 as a DR
0675
0676 template<class T>
0677 BOOST_CONSTEXPR int bit_width( T x ) BOOST_NOEXCEPT
0678 {
0679     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0680
0681     return std::numeric_limits<T>::digits - boost::core::countl_zero( x );
0682 }
0683
0684 template<class T>
0685 BOOST_CONSTEXPR T bit_floor( T x ) BOOST_NOEXCEPT
0686 {
0687     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0688
0689     return x == 0? T(0): static_cast<T>( T(1) << ( boost::core::bit_width( x ) - 1 ) );
0690 }
0691
0692 namespace detail
0693 {
0694
0695 BOOST_CXX14_CONSTEXPR inline boost::uint32_t bit_ceil_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0696 {
0697     if( x == 0 )
0698     {
0699         return 0;
0700     }
0701
0702     --x;
0703
0704     x |= x >> 1;
0705     x |= x >> 2;
0706     x |= x >> 4;
0707     x |= x >> 8;
0708     x |= x >> 16;
0709
0710     ++x;
0711
0712     return x;
0713 }
0714
0715 BOOST_CXX14_CONSTEXPR inline boost::uint64_t bit_ceil_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0716 {
0717     if( x == 0 )
0718     {
0719         return 0;
0720     }
0721
0722     --x;
0723
0724     x |= x >> 1;
0725     x |= x >> 2;
0726     x |= x >> 4;
0727     x |= x >> 8;
0728     x |= x >> 16;
0729     x |= x >> 32;
0730
0731     ++x;
0732
0733     return x;
0734 }
0735
0736 } // namespace detail
0737
0738 template<class T>
0739 BOOST_CXX14_CONSTEXPR T bit_ceil( T x ) BOOST_NOEXCEPT
0740 {
0741     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed );
0742
0743     BOOST_STATIC_ASSERT( sizeof(T) <= sizeof(boost::uint64_t) );
0744
0745     BOOST_IF_CONSTEXPR ( sizeof(T) <= sizeof(boost::uint32_t) )
0746     {
0747         return static_cast<T>( boost::core::detail::bit_ceil_impl( static_cast<boost::uint32_t>( x ) ) );
0748     }
0749     else
0750     {
0751         return static_cast<T>( boost::core::detail::bit_ceil_impl( static_cast<boost::uint64_t>( x ) ) );
0752     }
0753 }
0754
0755 // endian
0756
0757 #if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
0758
0759 # define BOOST_CORE_BIT_NATIVE_INITIALIZER =little
0760
0761 #elif defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
0762
0763 # define BOOST_CORE_BIT_NATIVE_INITIALIZER =big
0764
0765 #elif defined(__BYTE_ORDER__) && defined(__ORDER_PDP_ENDIAN__) && __BYTE_ORDER__ == __ORDER_PDP_ENDIAN__
0766
0767 # define BOOST_CORE_BIT_NATIVE_INITIALIZER
0768
0769 #elif defined(__LITTLE_ENDIAN__)
0770
0771 # define BOOST_CORE_BIT_NATIVE_INITIALIZER =little
0772
0773 #elif defined(__BIG_ENDIAN__)
0774
0775 # define BOOST_CORE_BIT_NATIVE_INITIALIZER =big
0776
0777 #elif defined(_MSC_VER) || defined(__i386__) || defined(__x86_64__)
0778
0779 # define BOOST_CORE_BIT_NATIVE_INITIALIZER =little
0780
0781 #else
0782
0783 # define BOOST_CORE_BIT_NATIVE_INITIALIZER
0784
0785 #endif
0786
0787 #if !defined(BOOST_NO_CXX11_SCOPED_ENUMS)
0788
0789 enum class endian
0790 {
0791     big,
0792     little,
0793     native BOOST_CORE_BIT_NATIVE_INITIALIZER
0794 };
0795
0796 typedef endian endian_type;
0797
0798 #else
0799
0800 namespace endian
0801 {
0802
0803 enum type
0804 {
0805     big,
0806     little,
0807     native BOOST_CORE_BIT_NATIVE_INITIALIZER
0808 };
0809
0810 } // namespace endian
0811
0812 typedef endian::type endian_type;
0813
0814 #endif
0815
0816 #undef BOOST_CORE_BIT_NATIVE_INITIALIZER
0817
0818 // byteswap
0819
0820 namespace detail
0821 {
0822
0823 BOOST_CONSTEXPR inline boost::uint8_t byteswap_impl( boost::uint8_t x ) BOOST_NOEXCEPT
0824 {
0825     return x;
0826 }
0827
0828 BOOST_CONSTEXPR inline boost::uint16_t byteswap_impl( boost::uint16_t x ) BOOST_NOEXCEPT
0829 {
0830     return static_cast<boost::uint16_t>( x << 8 | x >> 8 );
0831 }
0832
0833 #if defined(__GNUC__) || defined(__clang__)
0834
0835 BOOST_CXX14_CONSTEXPR inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0836 {
0837     return __builtin_bswap32( x );
0838 }
0839
0840 BOOST_CXX14_CONSTEXPR inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0841 {
0842     return __builtin_bswap64( x );
0843 }
0844
0845 #elif defined(_MSC_VER) && defined(BOOST_CORE_HAS_BUILTIN_ISCONSTEVAL)
0846
0847 BOOST_CXX14_CONSTEXPR inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0848 {
0849     if( __builtin_is_constant_evaluated() )
0850     {
0851         boost::uint32_t step16 = x << 16 | x >> 16;
0852         return ((step16 << 8) & 0xff00ff00) | ((step16 >> 8) & 0x00ff00ff);
0853     }
0854     else
0855     {
0856         return _byteswap_ulong( x );
0857     }
0858 }
0859
0860 BOOST_CXX14_CONSTEXPR inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0861 {
0862     if( __builtin_is_constant_evaluated() )
0863     {
0864         boost::uint64_t step32 = x << 32 | x >> 32;
0865         boost::uint64_t step16 = (step32 & 0x0000FFFF0000FFFFULL) << 16 | (step32 & 0xFFFF0000FFFF0000ULL) >> 16;
0866         return (step16 & 0x00FF00FF00FF00FFULL) << 8 | (step16 & 0xFF00FF00FF00FF00ULL) >> 8;
0867     }
0868     else
0869     {
0870         return _byteswap_uint64( x );
0871     }
0872 }
0873
0874 #elif defined(_MSC_VER)
0875
0876 inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0877 {
0878     return _byteswap_ulong( x );
0879 }
0880
0881 inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0882 {
0883     return _byteswap_uint64( x );
0884 }
0885
0886 #else
0887
0888 BOOST_CXX14_CONSTEXPR inline boost::uint32_t byteswap_impl( boost::uint32_t x ) BOOST_NOEXCEPT
0889 {
0890     boost::uint32_t step16 = x << 16 | x >> 16;
0891     return ((step16 << 8) & 0xff00ff00) | ((step16 >> 8) & 0x00ff00ff);
0892 }
0893
0894 BOOST_CXX14_CONSTEXPR inline boost::uint64_t byteswap_impl( boost::uint64_t x ) BOOST_NOEXCEPT
0895 {
0896     boost::uint64_t step32 = x << 32 | x >> 32;
0897     boost::uint64_t step16 = (step32 & 0x0000FFFF0000FFFFULL) << 16 | (step32 & 0xFFFF0000FFFF0000ULL) >> 16;
0898     return (step16 & 0x00FF00FF00FF00FFULL) << 8 | (step16 & 0xFF00FF00FF00FF00ULL) >> 8;
0899 }
0900
0901 #endif
0902
0903 } // namespace detail
0904
0905 template<class T> BOOST_CXX14_CONSTEXPR T byteswap( T x ) BOOST_NOEXCEPT
0906 {
0907     BOOST_STATIC_ASSERT( std::numeric_limits<T>::is_integer );
0908
0909     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) );
0910
0911     BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint8_t) )
0912     {
0913         return static_cast<T>( boost::core::detail::byteswap_impl( static_cast<boost::uint8_t>( x ) ) );
0914     }
0915     else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint16_t) )
0916     {
0917         return static_cast<T>( boost::core::detail::byteswap_impl( static_cast<boost::uint16_t>( x ) ) );
0918     }
0919     else BOOST_IF_CONSTEXPR ( sizeof(T) == sizeof(boost::uint32_t) )
0920     {
0921         return static_cast<T>( boost::core::detail::byteswap_impl( static_cast<boost::uint32_t>( x ) ) );
0922     }
0923     else
0924     {
0925         return static_cast<T>( boost::core::detail::byteswap_impl( static_cast<boost::uint64_t>( x ) ) );
0926     }
0927 }
0928
0929 } // namespace core
0930 } // namespace boost
0931
0932 #if defined(_MSC_VER)
0933 # pragma warning(pop)
0934 #endif
0935
0936 #endif  // #ifndef BOOST_CORE_BIT_HPP_INCLUDED