Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 1 | // -*- C++ -*- |
| 2 | //===------------------------------ bit ----------------------------------===// |
| 3 | // |
Chandler Carruth | d201210 | 2019-01-19 10:56:40 +0000 | [diff] [blame] | 4 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 5 | // See https://llvm.org/LICENSE.txt for license information. |
| 6 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 7 | // |
| 8 | //===---------------------------------------------------------------------===// |
| 9 | |
| 10 | #ifndef _LIBCPP_BIT |
| 11 | #define _LIBCPP_BIT |
| 12 | |
| 13 | /* |
| 14 | bit synopsis |
| 15 | |
| 16 | namespace std { |
| 17 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 18 | template <class T> |
| 19 | constexpr bool ispow2(T x) noexcept; // C++20 |
| 20 | template <class T> |
| 21 | constexpr T ceil2(T x); // C++20 |
| 22 | template <class T> |
| 23 | constexpr T floor2(T x) noexcept; // C++20 |
| 24 | template <class T> |
| 25 | constexpr T log2p1(T x) noexcept; // C++20 |
| 26 | |
| 27 | // 23.20.2, rotating |
| 28 | template<class T> |
| 29 | constexpr T rotl(T x, unsigned int s) noexcept; // C++20 |
| 30 | template<class T> |
| 31 | constexpr T rotr(T x, unsigned int s) noexcept; // C++20 |
| 32 | |
| 33 | // 23.20.3, counting |
| 34 | template<class T> |
| 35 | constexpr int countl_zero(T x) noexcept; // C++20 |
| 36 | template<class T> |
| 37 | constexpr int countl_one(T x) noexcept; // C++20 |
| 38 | template<class T> |
| 39 | constexpr int countr_zero(T x) noexcept; // C++20 |
| 40 | template<class T> |
| 41 | constexpr int countr_one(T x) noexcept; // C++20 |
| 42 | template<class T> |
| 43 | constexpr int popcount(T x) noexcept; // C++20 |
| 44 | |
Louis Dionne | fd77e4f | 2019-10-23 10:40:15 -0700 | [diff] [blame] | 45 | // 20.15.9, endian |
Marshall Clow | e8a18f3 | 2019-07-23 04:20:19 +0000 | [diff] [blame] | 46 | enum class endian { |
| 47 | little = see below, // C++20 |
| 48 | big = see below, // C++20 |
| 49 | native = see below // C++20 |
| 50 | }; |
| 51 | |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 52 | } // namespace std |
| 53 | |
| 54 | */ |
| 55 | |
| 56 | #include <__config> |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 57 | #include <limits> |
| 58 | #include <type_traits> |
Marshall Clow | 0a1e750 | 2018-09-12 19:41:40 +0000 | [diff] [blame] | 59 | #include <version> |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 60 | #include <__debug> |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 61 | |
| 62 | #if defined(__IBMCPP__) |
| 63 | #include "support/ibm/support.h" |
| 64 | #endif |
| 65 | #if defined(_LIBCPP_COMPILER_MSVC) |
| 66 | #include <intrin.h> |
| 67 | #endif |
| 68 | |
| 69 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 70 | #pragma GCC system_header |
| 71 | #endif |
| 72 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 73 | _LIBCPP_PUSH_MACROS |
| 74 | #include <__undef_macros> |
| 75 | |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 76 | _LIBCPP_BEGIN_NAMESPACE_STD |
| 77 | |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 78 | #ifndef _LIBCPP_COMPILER_MSVC |
| 79 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 80 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 81 | int __libcpp_ctz(unsigned __x) _NOEXCEPT { return __builtin_ctz(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 82 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 83 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 84 | int __libcpp_ctz(unsigned long __x) _NOEXCEPT { return __builtin_ctzl(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 85 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 86 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 87 | int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 88 | |
| 89 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 90 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 91 | int __libcpp_clz(unsigned __x) _NOEXCEPT { return __builtin_clz(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 92 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 93 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 94 | int __libcpp_clz(unsigned long __x) _NOEXCEPT { return __builtin_clzl(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 95 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 96 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 97 | int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 98 | |
| 99 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 100 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 101 | int __libcpp_popcount(unsigned __x) _NOEXCEPT { return __builtin_popcount(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 102 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 103 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 104 | int __libcpp_popcount(unsigned long __x) _NOEXCEPT { return __builtin_popcountl(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 105 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 106 | inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 107 | int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); } |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 108 | |
| 109 | #else // _LIBCPP_COMPILER_MSVC |
| 110 | |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 111 | // Precondition: __x != 0 |
| 112 | inline _LIBCPP_INLINE_VISIBILITY |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 113 | int __libcpp_ctz(unsigned __x) { |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 114 | static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); |
| 115 | static_assert(sizeof(unsigned long) == 4, ""); |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 116 | unsigned long __where; |
| 117 | if (_BitScanForward(&__where, __x)) |
| 118 | return static_cast<int>(__where); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 119 | return 32; |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 120 | } |
| 121 | |
| 122 | inline _LIBCPP_INLINE_VISIBILITY |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 123 | int __libcpp_ctz(unsigned long __x) { |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 124 | static_assert(sizeof(unsigned long) == sizeof(unsigned), ""); |
| 125 | return __ctz(static_cast<unsigned>(__x)); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 126 | } |
| 127 | |
| 128 | inline _LIBCPP_INLINE_VISIBILITY |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 129 | int __libcpp_ctz(unsigned long long __x) { |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 130 | unsigned long __where; |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 131 | #if defined(_LIBCPP_HAS_BITSCAN64) |
| 132 | (defined(_M_AMD64) || defined(__x86_64__)) |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 133 | if (_BitScanForward64(&__where, __x)) |
| 134 | return static_cast<int>(__where); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 135 | #else |
| 136 | // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 137 | if (_BitScanForward(&__where, static_cast<unsigned long>(__x))) |
| 138 | return static_cast<int>(__where); |
| 139 | if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32))) |
| 140 | return static_cast<int>(__where + 32); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 141 | #endif |
| 142 | return 64; |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 143 | } |
| 144 | |
| 145 | // Precondition: __x != 0 |
| 146 | inline _LIBCPP_INLINE_VISIBILITY |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 147 | int __libcpp_clz(unsigned __x) { |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 148 | static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); |
| 149 | static_assert(sizeof(unsigned long) == 4, ""); |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 150 | unsigned long __where; |
| 151 | if (_BitScanReverse(&__where, __x)) |
| 152 | return static_cast<int>(31 - __where); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 153 | return 32; // Undefined Behavior. |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 154 | } |
| 155 | |
| 156 | inline _LIBCPP_INLINE_VISIBILITY |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 157 | int __libcpp_clz(unsigned long __x) { |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 158 | static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 159 | return __libcpp_clz(static_cast<unsigned>(__x)); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 160 | } |
| 161 | |
| 162 | inline _LIBCPP_INLINE_VISIBILITY |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 163 | int __libcpp_clz(unsigned long long __x) { |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 164 | unsigned long __where; |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 165 | #if defined(_LIBCPP_HAS_BITSCAN64) |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 166 | if (_BitScanReverse64(&__where, __x)) |
| 167 | return static_cast<int>(63 - __where); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 168 | #else |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 169 | // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls. |
| 170 | if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32))) |
| 171 | return static_cast<int>(63 - (__where + 32)); |
| 172 | if (_BitScanReverse(&__where, static_cast<unsigned long>(__x))) |
| 173 | return static_cast<int>(63 - __where); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 174 | #endif |
| 175 | return 64; // Undefined Behavior. |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 176 | } |
| 177 | |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 178 | inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned __x) { |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 179 | static_assert(sizeof(unsigned) == 4, ""); |
| 180 | return __popcnt(__x); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 181 | } |
| 182 | |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 183 | inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long __x) { |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 184 | static_assert(sizeof(unsigned long) == 4, ""); |
| 185 | return __popcnt(__x); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 186 | } |
| 187 | |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 188 | inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long long __x) { |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 189 | static_assert(sizeof(unsigned long long) == 8, ""); |
| 190 | return __popcnt64(__x); |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 191 | } |
| 192 | |
Marshall Clow | ea687e2 | 2018-08-17 17:27:25 +0000 | [diff] [blame] | 193 | #endif // _LIBCPP_COMPILER_MSVC |
| 194 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 195 | template <class _Tp> |
| 196 | using __bitop_unsigned_integer _LIBCPP_NODEBUG_TYPE = integral_constant<bool, |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 197 | is_integral<_Tp>::value && |
| 198 | is_unsigned<_Tp>::value && |
| 199 | _IsNotSame<typename remove_cv<_Tp>::type, bool>::value && |
| 200 | _IsNotSame<typename remove_cv<_Tp>::type, signed char>::value && |
| 201 | _IsNotSame<typename remove_cv<_Tp>::type, wchar_t>::value && |
| 202 | _IsNotSame<typename remove_cv<_Tp>::type, char16_t>::value && |
| 203 | _IsNotSame<typename remove_cv<_Tp>::type, char32_t>::value |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 204 | >; |
| 205 | |
| 206 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 207 | template<class _Tp> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 208 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 209 | _Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 210 | { |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 211 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__rotl requires unsigned"); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 212 | const unsigned int __dig = numeric_limits<_Tp>::digits; |
| 213 | if ((__cnt % __dig) == 0) |
| 214 | return __t; |
| 215 | return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig))); |
| 216 | } |
| 217 | |
| 218 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 219 | template<class _Tp> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 220 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 221 | _Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 222 | { |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 223 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__rotr requires unsigned"); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 224 | const unsigned int __dig = numeric_limits<_Tp>::digits; |
| 225 | if ((__cnt % __dig) == 0) |
| 226 | return __t; |
| 227 | return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig))); |
| 228 | } |
| 229 | |
| 230 | |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 231 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 232 | template<class _Tp> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 233 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 234 | int __countr_zero(_Tp __t) _NOEXCEPT |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 235 | { |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 236 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__countr_zero requires unsigned"); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 237 | if (__t == 0) |
| 238 | return numeric_limits<_Tp>::digits; |
| 239 | |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 240 | if (sizeof(_Tp) <= sizeof(unsigned int)) |
| 241 | return __libcpp_ctz(static_cast<unsigned int>(__t)); |
| 242 | else if (sizeof(_Tp) <= sizeof(unsigned long)) |
| 243 | return __libcpp_ctz(static_cast<unsigned long>(__t)); |
| 244 | else if (sizeof(_Tp) <= sizeof(unsigned long long)) |
| 245 | return __libcpp_ctz(static_cast<unsigned long long>(__t)); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 246 | else |
| 247 | { |
| 248 | int __ret = 0; |
| 249 | int __iter = 0; |
| 250 | const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 251 | while ((__iter = __libcpp_ctz(static_cast<unsigned long long>(__t))) == __ulldigits) |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 252 | { |
| 253 | __ret += __iter; |
| 254 | __t >>= __ulldigits; |
| 255 | } |
| 256 | return __ret + __iter; |
| 257 | } |
| 258 | } |
| 259 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 260 | template<class _Tp> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 261 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 262 | int __countl_zero(_Tp __t) _NOEXCEPT |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 263 | { |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 264 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__countl_zero requires unsigned"); |
| 265 | if (__t == 0) |
| 266 | return numeric_limits<_Tp>::digits; |
| 267 | |
| 268 | if (sizeof(_Tp) <= sizeof(unsigned int)) |
| 269 | return __libcpp_clz(static_cast<unsigned int>(__t)) |
| 270 | - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits); |
| 271 | else if (sizeof(_Tp) <= sizeof(unsigned long)) |
| 272 | return __libcpp_clz(static_cast<unsigned long>(__t)) |
| 273 | - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits); |
| 274 | else if (sizeof(_Tp) <= sizeof(unsigned long long)) |
| 275 | return __libcpp_clz(static_cast<unsigned long long>(__t)) |
| 276 | - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits); |
| 277 | else |
| 278 | { |
| 279 | int __ret = 0; |
| 280 | int __iter = 0; |
| 281 | const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits; |
| 282 | while (true) { |
| 283 | __t = __rotr(__t, __ulldigits); |
| 284 | if ((__iter = __countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits) |
| 285 | break; |
| 286 | __ret += __iter; |
| 287 | } |
| 288 | return __ret + __iter; |
| 289 | } |
| 290 | } |
| 291 | |
| 292 | template<class _Tp> |
| 293 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 294 | int __countl_one(_Tp __t) _NOEXCEPT |
| 295 | { |
| 296 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__countl_one requires unsigned"); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 297 | return __t != numeric_limits<_Tp>::max() |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 298 | ? __countl_zero(static_cast<_Tp>(~__t)) |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 299 | : numeric_limits<_Tp>::digits; |
| 300 | } |
| 301 | |
| 302 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 303 | template<class _Tp> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 304 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 305 | int __countr_one(_Tp __t) _NOEXCEPT |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 306 | { |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 307 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__countr_one requires unsigned"); |
| 308 | return __t != numeric_limits<_Tp>::max() |
| 309 | ? __countr_zero(static_cast<_Tp>(~__t)) |
| 310 | : numeric_limits<_Tp>::digits; |
| 311 | } |
| 312 | |
| 313 | |
| 314 | template<class _Tp> |
| 315 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 316 | int |
| 317 | __popcount(_Tp __t) _NOEXCEPT |
| 318 | { |
| 319 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__libcpp_popcount requires unsigned"); |
| 320 | if (sizeof(_Tp) <= sizeof(unsigned int)) |
| 321 | return __libcpp_popcount(static_cast<unsigned int>(__t)); |
| 322 | else if (sizeof(_Tp) <= sizeof(unsigned long)) |
| 323 | return __libcpp_popcount(static_cast<unsigned long>(__t)); |
| 324 | else if (sizeof(_Tp) <= sizeof(unsigned long long)) |
| 325 | return __libcpp_popcount(static_cast<unsigned long long>(__t)); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 326 | else |
| 327 | { |
| 328 | int __ret = 0; |
| 329 | while (__t != 0) |
| 330 | { |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 331 | __ret += __libcpp_popcount(static_cast<unsigned long long>(__t)); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 332 | __t >>= numeric_limits<unsigned long long>::digits; |
| 333 | } |
| 334 | return __ret; |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | |
| 339 | // integral log base 2 |
| 340 | template<class _Tp> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 341 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 |
| 342 | unsigned __bit_log2(_Tp __t) _NOEXCEPT |
| 343 | { |
| 344 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__bit_log2 requires unsigned"); |
| 345 | return std::numeric_limits<_Tp>::digits - 1 - __countl_zero(__t); |
| 346 | } |
| 347 | |
| 348 | template <class _Tp> |
| 349 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
| 350 | bool __ispow2(_Tp __t) _NOEXCEPT |
| 351 | { |
| 352 | static_assert(__bitop_unsigned_integer<_Tp>::value, "__ispow2 requires unsigned"); |
Louis Dionne | fd77e4f | 2019-10-23 10:40:15 -0700 | [diff] [blame] | 353 | return __t != 0 && (((__t & (__t - 1)) == 0)); |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 354 | } |
| 355 | |
| 356 | |
| 357 | #if _LIBCPP_STD_VER > 17 |
| 358 | |
| 359 | template<class _Tp> |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 360 | _LIBCPP_INLINE_VISIBILITY constexpr |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 361 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp> |
| 362 | rotl(_Tp __t, unsigned int __cnt) noexcept |
| 363 | { |
| 364 | return __rotl(__t, __cnt); |
| 365 | } |
| 366 | |
| 367 | |
| 368 | // rotr |
| 369 | template<class _Tp> |
| 370 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 371 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp> |
| 372 | rotr(_Tp __t, unsigned int __cnt) noexcept |
| 373 | { |
| 374 | return __rotr(__t, __cnt); |
| 375 | } |
| 376 | |
| 377 | |
| 378 | template<class _Tp> |
| 379 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 380 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, int> |
| 381 | countl_zero(_Tp __t) noexcept |
| 382 | { |
| 383 | return __countl_zero(__t); |
| 384 | } |
| 385 | |
| 386 | |
| 387 | template<class _Tp> |
| 388 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 389 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, int> |
| 390 | countl_one(_Tp __t) noexcept |
| 391 | { |
| 392 | return __countl_one(__t); |
| 393 | } |
| 394 | |
| 395 | |
| 396 | template<class _Tp> |
| 397 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 398 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, int> |
| 399 | countr_zero(_Tp __t) noexcept |
| 400 | { |
| 401 | return __countr_zero(__t); |
| 402 | } |
| 403 | |
| 404 | |
| 405 | template<class _Tp> |
| 406 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 407 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, int> |
| 408 | countr_one(_Tp __t) noexcept |
| 409 | { |
| 410 | return __countr_one(__t); |
| 411 | } |
| 412 | |
| 413 | |
| 414 | template<class _Tp> |
| 415 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 416 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, int> |
| 417 | popcount(_Tp __t) noexcept |
| 418 | { |
| 419 | return __popcount(__t); |
| 420 | } |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 421 | |
| 422 | |
| 423 | template <class _Tp> |
| 424 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 425 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, bool> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 426 | ispow2(_Tp __t) noexcept |
| 427 | { |
| 428 | return __ispow2(__t); |
| 429 | } |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 430 | |
| 431 | template <class _Tp> |
| 432 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 433 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp> |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 434 | floor2(_Tp __t) noexcept |
| 435 | { |
| 436 | return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t); |
| 437 | } |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 438 | |
| 439 | template <class _Tp> |
| 440 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 441 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp> |
| 442 | ceil2(_Tp __t) noexcept |
| 443 | { |
| 444 | if (__t < 2) return 1; |
| 445 | const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u)); |
Marshall Clow | a2851c7 | 2019-07-02 03:21:16 +0000 | [diff] [blame] | 446 | _LIBCPP_DEBUG_ASSERT(__libcpp_is_constant_evaluated() || __n != numeric_limits<_Tp>::digits, "Bad input to ceil2"); |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 447 | |
| 448 | if constexpr (sizeof(_Tp) >= sizeof(unsigned)) |
| 449 | return _Tp{1} << __n; |
| 450 | else |
| 451 | { |
| 452 | const unsigned __extra = numeric_limits<unsigned>::digits - numeric_limits<_Tp>::digits; |
| 453 | const unsigned __retVal = 1u << (__n + __extra); |
| 454 | return (_Tp) (__retVal >> __extra); |
| 455 | } |
| 456 | } |
| 457 | |
| 458 | template <class _Tp> |
| 459 | _LIBCPP_INLINE_VISIBILITY constexpr |
| 460 | enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp> |
| 461 | log2p1(_Tp __t) noexcept |
Marshall Clow | 370375e | 2019-07-12 01:01:55 +0000 | [diff] [blame] | 462 | { |
| 463 | return __t == 0 ? 0 : __bit_log2(__t) + 1; |
| 464 | } |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 465 | |
Marshall Clow | e8a18f3 | 2019-07-23 04:20:19 +0000 | [diff] [blame] | 466 | |
| 467 | enum class endian |
| 468 | { |
| 469 | little = 0xDEAD, |
| 470 | big = 0xFACE, |
| 471 | #if defined(_LIBCPP_LITTLE_ENDIAN) |
| 472 | native = little |
| 473 | #elif defined(_LIBCPP_BIG_ENDIAN) |
| 474 | native = big |
| 475 | #else |
| 476 | native = 0xCAFE |
| 477 | #endif |
| 478 | }; |
| 479 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 480 | #endif // _LIBCPP_STD_VER > 17 |
| 481 | |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 482 | _LIBCPP_END_NAMESPACE_STD |
| 483 | |
Marshall Clow | d852d5d | 2019-07-01 23:00:32 +0000 | [diff] [blame] | 484 | _LIBCPP_POP_MACROS |
| 485 | |
Marshall Clow | bf32ec9 | 2018-08-17 16:07:48 +0000 | [diff] [blame] | 486 | #endif // _LIBCPP_BIT |