bits.h (12750B)
1 // Copyright 2020 The Abseil Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_NUMERIC_INTERNAL_BITS_H_ 16 #define ABSL_NUMERIC_INTERNAL_BITS_H_ 17 18 #include <cstdint> 19 #include <limits> 20 #include <type_traits> 21 22 // Clang on Windows has __builtin_clzll; otherwise we need to use the 23 // windows intrinsic functions. 24 #if defined(_MSC_VER) && !defined(__clang__) 25 #include <intrin.h> 26 #endif 27 28 #include "absl/base/attributes.h" 29 #include "absl/base/config.h" 30 31 #if defined(__GNUC__) && !defined(__clang__) 32 // GCC 33 #define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) 1 34 #else 35 #define ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(x) ABSL_HAVE_BUILTIN(x) 36 #endif 37 38 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountl) && \ 39 ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll) 40 #define ABSL_INTERNAL_CONSTEXPR_POPCOUNT constexpr 41 #define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 1 42 #else 43 #define ABSL_INTERNAL_CONSTEXPR_POPCOUNT 44 #define ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT 0 45 #endif 46 47 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz) && \ 48 ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll) 49 #define ABSL_INTERNAL_CONSTEXPR_CLZ constexpr 50 #define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 1 51 #else 52 #define ABSL_INTERNAL_CONSTEXPR_CLZ 53 #define ABSL_INTERNAL_HAS_CONSTEXPR_CLZ 0 54 #endif 55 56 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz) && \ 57 ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll) 58 #define ABSL_INTERNAL_CONSTEXPR_CTZ constexpr 59 #define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 1 60 #else 61 #define ABSL_INTERNAL_CONSTEXPR_CTZ 62 #define ABSL_INTERNAL_HAS_CONSTEXPR_CTZ 0 63 #endif 64 65 namespace absl { 66 ABSL_NAMESPACE_BEGIN 67 namespace numeric_internal { 68 69 constexpr bool IsPowerOf2(unsigned int x) noexcept { 70 return x != 0 && (x & (x - 1)) == 0; 71 } 72 73 template <class T> 74 [[nodiscard]] ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateRight( 75 T x, int s) noexcept { 76 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 77 static_assert(IsPowerOf2(std::numeric_limits<T>::digits), 78 "T must have a power-of-2 size"); 79 80 return static_cast<T>(x >> (s & (std::numeric_limits<T>::digits - 1))) | 81 static_cast<T>(x << ((-s) & (std::numeric_limits<T>::digits - 1))); 82 } 83 84 template <class T> 85 [[nodiscard]] ABSL_ATTRIBUTE_ALWAYS_INLINE constexpr T RotateLeft( 86 T x, int s) noexcept { 87 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 88 static_assert(IsPowerOf2(std::numeric_limits<T>::digits), 89 "T must have a power-of-2 size"); 90 91 return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) | 92 static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1))); 93 } 94 95 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int 96 Popcount32(uint32_t x) noexcept { 97 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcount) 98 static_assert(sizeof(unsigned int) == sizeof(x), 99 "__builtin_popcount does not take 32-bit arg"); 100 return __builtin_popcount(x); 101 #else 102 x -= ((x >> 1) & 0x55555555); 103 x = ((x >> 2) & 0x33333333) + (x & 0x33333333); 104 return static_cast<int>((((x + (x >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24); 105 #endif 106 } 107 108 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int 109 Popcount64(uint64_t x) noexcept { 110 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_popcountll) 111 static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int) 112 "__builtin_popcount does not take 64-bit arg"); 113 return __builtin_popcountll(x); 114 #else 115 x -= (x >> 1) & 0x5555555555555555ULL; 116 x = ((x >> 2) & 0x3333333333333333ULL) + (x & 0x3333333333333333ULL); 117 return static_cast<int>( 118 (((x + (x >> 4)) & 0xF0F0F0F0F0F0F0FULL) * 0x101010101010101ULL) >> 56); 119 #endif 120 } 121 122 template <class T> 123 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline int 124 Popcount(T x) noexcept { 125 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 126 static_assert(IsPowerOf2(std::numeric_limits<T>::digits), 127 "T must have a power-of-2 size"); 128 static_assert(sizeof(x) <= sizeof(uint64_t), "T is too large"); 129 if constexpr (sizeof(x) <= sizeof(uint32_t)) { 130 return Popcount32(x); 131 } else { 132 return Popcount64(x); 133 } 134 } 135 136 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int 137 CountLeadingZeroes32(uint32_t x) { 138 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clz) 139 // Use __builtin_clz, which uses the following instructions: 140 // x86: bsr, lzcnt 141 // ARM64: clz 142 // PPC: cntlzd 143 144 static_assert(sizeof(unsigned int) == sizeof(x), 145 "__builtin_clz does not take 32-bit arg"); 146 // Handle 0 as a special case because __builtin_clz(0) is undefined. 147 return x == 0 ? 32 : __builtin_clz(x); 148 #elif defined(_MSC_VER) && !defined(__clang__) 149 unsigned long result = 0; // NOLINT(runtime/int) 150 if (_BitScanReverse(&result, x)) { 151 return 31 - result; 152 } 153 return 32; 154 #else 155 int zeroes = 28; 156 if (x >> 16) { 157 zeroes -= 16; 158 x >>= 16; 159 } 160 if (x >> 8) { 161 zeroes -= 8; 162 x >>= 8; 163 } 164 if (x >> 4) { 165 zeroes -= 4; 166 x >>= 4; 167 } 168 return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes; 169 #endif 170 } 171 172 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int 173 CountLeadingZeroes16(uint16_t x) { 174 #if ABSL_HAVE_BUILTIN(__builtin_clzg) 175 return x == 0 ? 16 : __builtin_clzg(x); 176 #elif ABSL_HAVE_BUILTIN(__builtin_clzs) 177 static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int) 178 "__builtin_clzs does not take 16-bit arg"); 179 return x == 0 ? 16 : __builtin_clzs(x); 180 #else 181 return CountLeadingZeroes32(x) - 16; 182 #endif 183 } 184 185 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int 186 CountLeadingZeroes64(uint64_t x) { 187 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_clzll) 188 // Use __builtin_clzll, which uses the following instructions: 189 // x86: bsr, lzcnt 190 // ARM64: clz 191 // PPC: cntlzd 192 static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int) 193 "__builtin_clzll does not take 64-bit arg"); 194 195 // Handle 0 as a special case because __builtin_clzll(0) is undefined. 196 return x == 0 ? 64 : __builtin_clzll(x); 197 #elif defined(_MSC_VER) && !defined(__clang__) && \ 198 (defined(_M_X64) || defined(_M_ARM64)) 199 // MSVC does not have __buitin_clzll. Use _BitScanReverse64. 200 unsigned long result = 0; // NOLINT(runtime/int) 201 if (_BitScanReverse64(&result, x)) { 202 return 63 - result; 203 } 204 return 64; 205 #elif defined(_MSC_VER) && !defined(__clang__) 206 // MSVC does not have __buitin_clzll. Compose two calls to _BitScanReverse 207 unsigned long result = 0; // NOLINT(runtime/int) 208 if ((x >> 32) && 209 _BitScanReverse(&result, static_cast<unsigned long>(x >> 32))) { 210 return 31 - result; 211 } 212 if (_BitScanReverse(&result, static_cast<unsigned long>(x))) { 213 return 63 - result; 214 } 215 return 64; 216 #else 217 int zeroes = 60; 218 if (x >> 32) { 219 zeroes -= 32; 220 x >>= 32; 221 } 222 if (x >> 16) { 223 zeroes -= 16; 224 x >>= 16; 225 } 226 if (x >> 8) { 227 zeroes -= 8; 228 x >>= 8; 229 } 230 if (x >> 4) { 231 zeroes -= 4; 232 x >>= 4; 233 } 234 return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes; 235 #endif 236 } 237 238 template <typename T> 239 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline int 240 CountLeadingZeroes(T x) { 241 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 242 static_assert(IsPowerOf2(std::numeric_limits<T>::digits), 243 "T must have a power-of-2 size"); 244 static_assert(sizeof(T) <= sizeof(uint64_t), "T too large"); 245 return sizeof(T) <= sizeof(uint16_t) 246 ? CountLeadingZeroes16(static_cast<uint16_t>(x)) - 247 (std::numeric_limits<uint16_t>::digits - 248 std::numeric_limits<T>::digits) 249 : (sizeof(T) <= sizeof(uint32_t) 250 ? CountLeadingZeroes32(static_cast<uint32_t>(x)) - 251 (std::numeric_limits<uint32_t>::digits - 252 std::numeric_limits<T>::digits) 253 : CountLeadingZeroes64(x)); 254 } 255 256 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int 257 CountTrailingZeroesNonzero32(uint32_t x) { 258 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctz) 259 static_assert(sizeof(unsigned int) == sizeof(x), 260 "__builtin_ctz does not take 32-bit arg"); 261 return __builtin_ctz(x); 262 #elif defined(_MSC_VER) && !defined(__clang__) 263 unsigned long result = 0; // NOLINT(runtime/int) 264 _BitScanForward(&result, x); 265 return result; 266 #else 267 int c = 31; 268 x &= ~x + 1; 269 if (x & 0x0000FFFF) c -= 16; 270 if (x & 0x00FF00FF) c -= 8; 271 if (x & 0x0F0F0F0F) c -= 4; 272 if (x & 0x33333333) c -= 2; 273 if (x & 0x55555555) c -= 1; 274 return c; 275 #endif 276 } 277 278 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int 279 CountTrailingZeroesNonzero64(uint64_t x) { 280 #if ABSL_NUMERIC_INTERNAL_HAVE_BUILTIN_OR_GCC(__builtin_ctzll) 281 static_assert(sizeof(unsigned long long) == sizeof(x), // NOLINT(runtime/int) 282 "__builtin_ctzll does not take 64-bit arg"); 283 return __builtin_ctzll(x); 284 #elif defined(_MSC_VER) && !defined(__clang__) && \ 285 (defined(_M_X64) || defined(_M_ARM64)) 286 unsigned long result = 0; // NOLINT(runtime/int) 287 _BitScanForward64(&result, x); 288 return result; 289 #elif defined(_MSC_VER) && !defined(__clang__) 290 unsigned long result = 0; // NOLINT(runtime/int) 291 if (static_cast<uint32_t>(x) == 0) { 292 _BitScanForward(&result, static_cast<unsigned long>(x >> 32)); 293 return result + 32; 294 } 295 _BitScanForward(&result, static_cast<unsigned long>(x)); 296 return result; 297 #else 298 int c = 63; 299 x &= ~x + 1; 300 if (x & 0x00000000FFFFFFFF) c -= 32; 301 if (x & 0x0000FFFF0000FFFF) c -= 16; 302 if (x & 0x00FF00FF00FF00FF) c -= 8; 303 if (x & 0x0F0F0F0F0F0F0F0F) c -= 4; 304 if (x & 0x3333333333333333) c -= 2; 305 if (x & 0x5555555555555555) c -= 1; 306 return c; 307 #endif 308 } 309 310 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int 311 CountTrailingZeroesNonzero16(uint16_t x) { 312 #if ABSL_HAVE_BUILTIN(__builtin_ctzg) 313 return __builtin_ctzg(x); 314 #elif ABSL_HAVE_BUILTIN(__builtin_ctzs) 315 static_assert(sizeof(unsigned short) == sizeof(x), // NOLINT(runtime/int) 316 "__builtin_ctzs does not take 16-bit arg"); 317 return __builtin_ctzs(x); 318 #else 319 return CountTrailingZeroesNonzero32(x); 320 #endif 321 } 322 323 template <class T> 324 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CTZ inline int 325 CountTrailingZeroes(T x) noexcept { 326 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 327 static_assert(IsPowerOf2(std::numeric_limits<T>::digits), 328 "T must have a power-of-2 size"); 329 static_assert(sizeof(T) <= sizeof(uint64_t), "T too large"); 330 return x == 0 ? std::numeric_limits<T>::digits 331 : (sizeof(T) <= sizeof(uint16_t) 332 ? CountTrailingZeroesNonzero16(static_cast<uint16_t>(x)) 333 : (sizeof(T) <= sizeof(uint32_t) 334 ? CountTrailingZeroesNonzero32( 335 static_cast<uint32_t>(x)) 336 : CountTrailingZeroesNonzero64(x))); 337 } 338 339 // If T is narrower than unsigned, T{1} << bit_width will be promoted. We 340 // want to force it to wraparound so that bit_ceil of an invalid value are not 341 // core constant expressions. 342 template <class T> 343 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline 344 typename std::enable_if<std::is_unsigned<T>::value, T>::type 345 BitCeilPromotionHelper(T x, T promotion) { 346 return (T{1} << (x + promotion)) >> promotion; 347 } 348 349 template <class T> 350 ABSL_ATTRIBUTE_ALWAYS_INLINE ABSL_INTERNAL_CONSTEXPR_CLZ inline 351 typename std::enable_if<std::is_unsigned<T>::value, T>::type 352 BitCeilNonPowerOf2(T x) { 353 // If T is narrower than unsigned, it undergoes promotion to unsigned when we 354 // shift. We calculate the number of bits added by the wider type. 355 return BitCeilPromotionHelper( 356 static_cast<T>(std::numeric_limits<T>::digits - CountLeadingZeroes(x)), 357 T{sizeof(T) >= sizeof(unsigned) ? 0 358 : std::numeric_limits<unsigned>::digits - 359 std::numeric_limits<T>::digits}); 360 } 361 362 } // namespace numeric_internal 363 ABSL_NAMESPACE_END 364 } // namespace absl 365 366 #endif // ABSL_NUMERIC_INTERNAL_BITS_H_