Yi Kong | 878f994 | 2023-12-13 12:55:04 +0900 | [diff] [blame^] | 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #ifndef _LIBCPP___BIT_COUNTL_H |
| 10 | #define _LIBCPP___BIT_COUNTL_H |
| 11 | |
| 12 | #include <__bit/rotate.h> |
| 13 | #include <__concepts/arithmetic.h> |
| 14 | #include <__config> |
| 15 | #include <__type_traits/is_unsigned_integer.h> |
| 16 | #include <limits> |
| 17 | |
| 18 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 19 | # pragma GCC system_header |
| 20 | #endif |
| 21 | |
| 22 | _LIBCPP_PUSH_MACROS |
| 23 | #include <__undef_macros> |
| 24 | |
| 25 | _LIBCPP_BEGIN_NAMESPACE_STD |
| 26 | |
| 27 | _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR |
| 28 | int __libcpp_clz(unsigned __x) _NOEXCEPT { return __builtin_clz(__x); } |
| 29 | |
| 30 | _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR |
| 31 | int __libcpp_clz(unsigned long __x) _NOEXCEPT { return __builtin_clzl(__x); } |
| 32 | |
| 33 | _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR |
| 34 | int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); } |
| 35 | |
| 36 | # ifndef _LIBCPP_HAS_NO_INT128 |
| 37 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| 38 | int __libcpp_clz(__uint128_t __x) _NOEXCEPT { |
| 39 | // The function is written in this form due to C++ constexpr limitations. |
| 40 | // The algorithm: |
| 41 | // - Test whether any bit in the high 64-bits is set |
| 42 | // - No bits set: |
| 43 | // - The high 64-bits contain 64 leading zeros, |
| 44 | // - Add the result of the low 64-bits. |
| 45 | // - Any bits set: |
| 46 | // - The number of leading zeros of the input is the number of leading |
| 47 | // zeros in the high 64-bits. |
| 48 | return ((__x >> 64) == 0) |
| 49 | ? (64 + __builtin_clzll(static_cast<unsigned long long>(__x))) |
| 50 | : __builtin_clzll(static_cast<unsigned long long>(__x >> 64)); |
| 51 | } |
| 52 | # endif // _LIBCPP_HAS_NO_INT128 |
| 53 | |
| 54 | template<class _Tp> |
| 55 | _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 |
| 56 | int __countl_zero(_Tp __t) _NOEXCEPT |
| 57 | { |
| 58 | static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type"); |
| 59 | if (__t == 0) |
| 60 | return numeric_limits<_Tp>::digits; |
| 61 | |
| 62 | if (sizeof(_Tp) <= sizeof(unsigned int)) |
| 63 | return std::__libcpp_clz(static_cast<unsigned int>(__t)) |
| 64 | - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits); |
| 65 | else if (sizeof(_Tp) <= sizeof(unsigned long)) |
| 66 | return std::__libcpp_clz(static_cast<unsigned long>(__t)) |
| 67 | - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits); |
| 68 | else if (sizeof(_Tp) <= sizeof(unsigned long long)) |
| 69 | return std::__libcpp_clz(static_cast<unsigned long long>(__t)) |
| 70 | - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits); |
| 71 | else |
| 72 | { |
| 73 | int __ret = 0; |
| 74 | int __iter = 0; |
| 75 | const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; |
| 76 | while (true) { |
| 77 | __t = std::__rotr(__t, __ulldigits); |
| 78 | if ((__iter = std::__countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits) |
| 79 | break; |
| 80 | __ret += __iter; |
| 81 | } |
| 82 | return __ret + __iter; |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | #if _LIBCPP_STD_VER >= 20 |
| 87 | |
| 88 | template <__libcpp_unsigned_integer _Tp> |
| 89 | _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr int countl_zero(_Tp __t) noexcept { |
| 90 | return std::__countl_zero(__t); |
| 91 | } |
| 92 | |
| 93 | template <__libcpp_unsigned_integer _Tp> |
| 94 | _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr int countl_one(_Tp __t) noexcept { |
| 95 | return __t != numeric_limits<_Tp>::max() ? std::countl_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits; |
| 96 | } |
| 97 | |
| 98 | #endif // _LIBCPP_STD_VER >= 20 |
| 99 | |
| 100 | _LIBCPP_END_NAMESPACE_STD |
| 101 | |
| 102 | _LIBCPP_POP_MACROS |
| 103 | |
| 104 | #endif // _LIBCPP___BIT_COUNTL_H |