diff --git a/libcxx/include/bit b/libcxx/include/bit --- a/libcxx/include/bit +++ b/libcxx/include/bit @@ -72,10 +72,10 @@ #include #if defined(__IBMCPP__) -#include "__support/ibm/support.h" +# include "__support/ibm/support.h" #endif #if defined(_LIBCPP_COMPILER_MSVC) -#include +# include #endif #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -87,199 +87,123 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -_Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotl requires an unsigned integer type"); - const unsigned int __dig = numeric_limits<_Tp>::digits; - if ((__cnt % __dig) == 0) - return __t; - return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -_Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type"); - const unsigned int __dig = numeric_limits<_Tp>::digits; - if ((__cnt % __dig) == 0) - return __t; - return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -int __countr_zero(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_zero requires an unsigned integer type"); - if (__t == 0) - return numeric_limits<_Tp>::digits; - - if (sizeof(_Tp) <= sizeof(unsigned int)) - return __libcpp_ctz(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long)) - return __libcpp_ctz(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long long)) - return __libcpp_ctz(static_cast(__t)); - else - { - int __ret = 0; - const unsigned int __ulldigits = numeric_limits::digits; - while (static_cast(__t) == 0uLL) - { - __ret += __ulldigits; - __t >>= __ulldigits; - } - return __ret + __libcpp_ctz(static_cast(__t)); - } -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -int __countl_zero(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type"); - if (__t == 0) - return numeric_limits<_Tp>::digits; - - if (sizeof(_Tp) <= sizeof(unsigned int)) - return __libcpp_clz(static_cast(__t)) - - (numeric_limits::digits - numeric_limits<_Tp>::digits); - else if (sizeof(_Tp) <= sizeof(unsigned long)) - return __libcpp_clz(static_cast(__t)) - - (numeric_limits::digits - numeric_limits<_Tp>::digits); - else if (sizeof(_Tp) <= sizeof(unsigned long long)) - return __libcpp_clz(static_cast(__t)) - - (numeric_limits::digits - numeric_limits<_Tp>::digits); - else - { - int __ret = 0; - int __iter = 0; - const unsigned int __ulldigits = numeric_limits::digits; - while (true) { - __t = __rotr(__t, __ulldigits); - if ((__iter = __countl_zero(static_cast(__t))) != __ulldigits) - break; - __ret += __iter; - } - return __ret + __iter; - } -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -int __countl_one(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_one requires an unsigned integer type"); - return __t != numeric_limits<_Tp>::max() - ? __countl_zero(static_cast<_Tp>(~__t)) - : numeric_limits<_Tp>::digits; -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -int __countr_one(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_one requires an unsigned integer type"); - return __t != numeric_limits<_Tp>::max() - ? __countr_zero(static_cast<_Tp>(~__t)) - : numeric_limits<_Tp>::digits; -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -int __popcount(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__popcount requires an unsigned integer type"); - if (sizeof(_Tp) <= sizeof(unsigned int)) - return __libcpp_popcount(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long)) - return __libcpp_popcount(static_cast(__t)); - else if (sizeof(_Tp) <= sizeof(unsigned long long)) - return __libcpp_popcount(static_cast(__t)); - else - { - int __ret = 0; - while (__t != 0) - { - __ret += __libcpp_popcount(static_cast(__t)); - __t >>= numeric_limits::digits; - } - return __ret; - } -} - -// integral log base 2 -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -unsigned __bit_log2(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__bit_log2 requires an unsigned integer type"); - return numeric_limits<_Tp>::digits - 1 - __countl_zero(__t); -} - -template -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR -bool __has_single_bit(_Tp __t) _NOEXCEPT -{ - static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__has_single_bit requires an unsigned integer type"); - return __t != 0 && (((__t & (__t - 1)) == 0)); -} - #if _LIBCPP_STD_VER > 17 template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, unsigned int __cnt) noexcept { - return __rotl(__t, __cnt); + const unsigned int __dig = numeric_limits<_Tp>::digits; + if ((__cnt % __dig) == 0) + return __t; + return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, unsigned int __cnt) noexcept { - return __rotr(__t, __cnt); + const unsigned int __dig = numeric_limits<_Tp>::digits; + if ((__cnt % __dig) == 0) + return __t; + return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr int countl_zero(_Tp __t) noexcept { - return __countl_zero(__t); + if (__t == 0) + return numeric_limits<_Tp>::digits; + + if (sizeof(_Tp) <= sizeof(unsigned int)) + return __libcpp_clz(static_cast(__t)) - + (numeric_limits::digits - numeric_limits<_Tp>::digits); + else if (sizeof(_Tp) <= sizeof(unsigned long)) + return __libcpp_clz(static_cast(__t)) - + (numeric_limits::digits - numeric_limits<_Tp>::digits); + else if (sizeof(_Tp) <= sizeof(unsigned long long)) + return __libcpp_clz(static_cast(__t)) - + (numeric_limits::digits - numeric_limits<_Tp>::digits); + else { + int __ret = 0; + int __iter = 0; + const unsigned int __ulldigits = numeric_limits::digits; + while (true) { + __t = std::rotr(__t, __ulldigits); + if ((__iter = std::countl_zero(static_cast(__t))) != __ulldigits) + break; + __ret += __iter; + } + return __ret + __iter; + } } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr int countl_one(_Tp __t) noexcept { - return __countl_one(__t); + return __t != numeric_limits<_Tp>::max() ? std::countl_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept { - return __countr_zero(__t); + if (__t == 0) + return numeric_limits<_Tp>::digits; + + if (sizeof(_Tp) <= sizeof(unsigned int)) + return __libcpp_ctz(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long)) + return __libcpp_ctz(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long long)) + return __libcpp_ctz(static_cast(__t)); + else { + int __ret = 0; + const unsigned int __ulldigits = numeric_limits::digits; + while (static_cast(__t) == 0uLL) { + __ret += __ulldigits; + __t >>= __ulldigits; + } + return __ret + std::__libcpp_ctz(static_cast(__t)); + } } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept { - return __countr_one(__t); + return __t != numeric_limits<_Tp>::max() ? std::countr_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept { - return __popcount(__t); + if (sizeof(_Tp) <= sizeof(unsigned int)) + return __libcpp_popcount(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long)) + return __libcpp_popcount(static_cast(__t)); + else if (sizeof(_Tp) <= sizeof(unsigned long long)) + return __libcpp_popcount(static_cast(__t)); + else { + int __ret = 0; + while (__t != 0) { + __ret += std::__libcpp_popcount(static_cast(__t)); + __t >>= numeric_limits::digits; + } + return __ret; + } } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr bool has_single_bit(_Tp __t) noexcept { - return __has_single_bit(__t); + return __t != 0 && (((__t & (__t - 1)) == 0)); +} + +// integral log base 2 +template <__libcpp_unsigned_integer _Tp> +_LIBCPP_HIDE_FROM_ABI constexpr _Tp __bit_log2(_Tp __t) noexcept { + return numeric_limits<_Tp>::digits - 1 - std::countl_zero(__t); } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_floor(_Tp __t) noexcept { - return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t); + return __t == 0 ? 0 : _Tp{1} << std::__bit_log2(__t); } template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_ceil(_Tp __t) noexcept { if (__t < 2) return 1; - const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u)); + const unsigned __n = numeric_limits<_Tp>::digits - std::countl_zero((_Tp)(__t - 1u)); _LIBCPP_ASSERT(__n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil"); if constexpr (sizeof(_Tp) >= sizeof(unsigned)) @@ -293,20 +217,19 @@ template <__libcpp_unsigned_integer _Tp> _LIBCPP_HIDE_FROM_ABI constexpr int bit_width(_Tp __t) noexcept { - return __t == 0 ? 0 : __bit_log2(__t) + 1; -} - -enum class endian -{ - little = 0xDEAD, - big = 0xFACE, -#if defined(_LIBCPP_LITTLE_ENDIAN) - native = little -#elif defined(_LIBCPP_BIG_ENDIAN) - native = big -#else - native = 0xCAFE -#endif + return __t == 0 ? 0 : std::__bit_log2(__t) + 1; +} + +enum class endian { + little = 0xDEAD, + big = 0xFACE, +# if defined(_LIBCPP_LITTLE_ENDIAN) + native = little +# elif defined(_LIBCPP_BIG_ENDIAN) + native = big +# else + native = 0xCAFE +# endif }; #endif // _LIBCPP_STD_VER > 17