1 //===-- llvm/ADT/bit.h - C++20 <bit> ----------------------------*- C++ -*-===// 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 /// \file 10 /// This file implements the C++20 <bit> header. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_BIT_H 15 #define LLVM_ADT_BIT_H 16 17 #include "llvm/Support/Compiler.h" 18 #include <cstdint> 19 #include <limits> 20 #include <type_traits> 21 22 #if !__has_builtin(__builtin_bit_cast) 23 #include <cstring> 24 #endif 25 26 #if defined(_MSC_VER) && !defined(_DEBUG) 27 #include <cstdlib> // for _byteswap_{ushort,ulong,uint64} 28 #endif 29 30 #if defined(__linux__) || defined(__GNU__) || defined(__HAIKU__) || \ 31 defined(__Fuchsia__) || defined(__EMSCRIPTEN__) || defined(__NetBSD__) || \ 32 defined(__OpenBSD__) || defined(__DragonFly__) 33 #include <endian.h> 34 #elif defined(_AIX) 35 #include <sys/machine.h> 36 #elif defined(__sun) 37 /* Solaris provides _BIG_ENDIAN/_LITTLE_ENDIAN selector in sys/types.h */ 38 #include <sys/types.h> 39 #define BIG_ENDIAN 4321 40 #define LITTLE_ENDIAN 1234 41 #if defined(_BIG_ENDIAN) 42 #define BYTE_ORDER BIG_ENDIAN 43 #else 44 #define BYTE_ORDER LITTLE_ENDIAN 45 #endif 46 #elif defined(__MVS__) 47 #define BIG_ENDIAN 4321 48 #define LITTLE_ENDIAN 1234 49 #define BYTE_ORDER BIG_ENDIAN 50 #else 51 #if !defined(BYTE_ORDER) && !defined(_WIN32) 52 #include <machine/endian.h> 53 #endif 54 #endif 55 56 #ifdef _MSC_VER 57 // Declare these intrinsics manually rather including intrin.h. It's very 58 // expensive, and bit.h is popular via MathExtras.h. 59 // #include <intrin.h> 60 extern "C" { 61 unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask); 62 unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask); 63 unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask); 64 unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); 65 } 66 #endif 67 68 namespace llvm { 69 70 enum class endianness { 71 big, 72 little, 73 #if defined(BYTE_ORDER) && defined(BIG_ENDIAN) && BYTE_ORDER == BIG_ENDIAN 74 native = big 75 #else 76 native = little 77 #endif 78 }; 79 80 // This implementation of bit_cast is different from the C++20 one in two ways: 81 // - It isn't constexpr because that requires compiler support. 82 // - It requires trivially-constructible To, to avoid UB in the implementation. 83 template < 84 typename To, typename From, 85 typename = std::enable_if_t<sizeof(To) == sizeof(From)>, 86 typename = std::enable_if_t<std::is_trivially_constructible<To>::value>, 87 typename = std::enable_if_t<std::is_trivially_copyable<To>::value>, 88 typename = std::enable_if_t<std::is_trivially_copyable<From>::value>> 89 [[nodiscard]] inline To bit_cast(const From &from) noexcept { 90 #if __has_builtin(__builtin_bit_cast) 91 return __builtin_bit_cast(To, from); 92 #else 93 To to; 94 std::memcpy(&to, &from, sizeof(To)); 95 return to; 96 #endif 97 } 98 99 /// Reverses the bytes in the given integer value V. 100 template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>> 101 [[nodiscard]] constexpr T byteswap(T V) noexcept { 102 if constexpr (sizeof(T) == 1) { 103 return V; 104 } else if constexpr (sizeof(T) == 2) { 105 uint16_t UV = V; 106 #if defined(_MSC_VER) && !defined(_DEBUG) 107 // The DLL version of the runtime lacks these functions (bug!?), but in a 108 // release build they're replaced with BSWAP instructions anyway. 109 return _byteswap_ushort(UV); 110 #else 111 uint16_t Hi = UV << 8; 112 uint16_t Lo = UV >> 8; 113 return Hi | Lo; 114 #endif 115 } else if constexpr (sizeof(T) == 4) { 116 uint32_t UV = V; 117 #if __has_builtin(__builtin_bswap32) 118 return __builtin_bswap32(UV); 119 #elif defined(_MSC_VER) && !defined(_DEBUG) 120 return _byteswap_ulong(UV); 121 #else 122 uint32_t Byte0 = UV & 0x000000FF; 123 uint32_t Byte1 = UV & 0x0000FF00; 124 uint32_t Byte2 = UV & 0x00FF0000; 125 uint32_t Byte3 = UV & 0xFF000000; 126 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24); 127 #endif 128 } else if constexpr (sizeof(T) == 8) { 129 uint64_t UV = V; 130 #if __has_builtin(__builtin_bswap64) 131 return __builtin_bswap64(UV); 132 #elif defined(_MSC_VER) && !defined(_DEBUG) 133 return _byteswap_uint64(UV); 134 #else 135 uint64_t Hi = llvm::byteswap<uint32_t>(UV); 136 uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32); 137 return (Hi << 32) | Lo; 138 #endif 139 } else { 140 static_assert(!sizeof(T *), "Don't know how to handle the given type."); 141 return 0; 142 } 143 } 144 145 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> 146 [[nodiscard]] constexpr inline bool has_single_bit(T Value) noexcept { 147 return (Value != 0) && ((Value & (Value - 1)) == 0); 148 } 149 150 namespace detail { 151 template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { 152 static unsigned count(T Val) { 153 if (!Val) 154 return std::numeric_limits<T>::digits; 155 if (Val & 0x1) 156 return 0; 157 158 // Bisection method. 159 unsigned ZeroBits = 0; 160 T Shift = std::numeric_limits<T>::digits >> 1; 161 T Mask = std::numeric_limits<T>::max() >> Shift; 162 while (Shift) { 163 if ((Val & Mask) == 0) { 164 Val >>= Shift; 165 ZeroBits |= Shift; 166 } 167 Shift >>= 1; 168 Mask >>= Shift; 169 } 170 return ZeroBits; 171 } 172 }; 173 174 #if defined(__GNUC__) || defined(_MSC_VER) 175 template <typename T> struct TrailingZerosCounter<T, 4> { 176 static unsigned count(T Val) { 177 if (Val == 0) 178 return 32; 179 180 #if __has_builtin(__builtin_ctz) || defined(__GNUC__) 181 return __builtin_ctz(Val); 182 #elif defined(_MSC_VER) 183 unsigned long Index; 184 _BitScanForward(&Index, Val); 185 return Index; 186 #endif 187 } 188 }; 189 190 #if !defined(_MSC_VER) || defined(_M_X64) 191 template <typename T> struct TrailingZerosCounter<T, 8> { 192 static unsigned count(T Val) { 193 if (Val == 0) 194 return 64; 195 196 #if __has_builtin(__builtin_ctzll) || defined(__GNUC__) 197 return __builtin_ctzll(Val); 198 #elif defined(_MSC_VER) 199 unsigned long Index; 200 _BitScanForward64(&Index, Val); 201 return Index; 202 #endif 203 } 204 }; 205 #endif 206 #endif 207 } // namespace detail 208 209 /// Count number of 0's from the least significant bit to the most 210 /// stopping at the first 1. 211 /// 212 /// Only unsigned integral types are allowed. 213 /// 214 /// Returns std::numeric_limits<T>::digits on an input of 0. 215 template <typename T> [[nodiscard]] int countr_zero(T Val) { 216 static_assert(std::is_unsigned_v<T>, 217 "Only unsigned integral types are allowed."); 218 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val); 219 } 220 221 namespace detail { 222 template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter { 223 static unsigned count(T Val) { 224 if (!Val) 225 return std::numeric_limits<T>::digits; 226 227 // Bisection method. 228 unsigned ZeroBits = 0; 229 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) { 230 T Tmp = Val >> Shift; 231 if (Tmp) 232 Val = Tmp; 233 else 234 ZeroBits |= Shift; 235 } 236 return ZeroBits; 237 } 238 }; 239 240 #if defined(__GNUC__) || defined(_MSC_VER) 241 template <typename T> struct LeadingZerosCounter<T, 4> { 242 static unsigned count(T Val) { 243 if (Val == 0) 244 return 32; 245 246 #if __has_builtin(__builtin_clz) || defined(__GNUC__) 247 return __builtin_clz(Val); 248 #elif defined(_MSC_VER) 249 unsigned long Index; 250 _BitScanReverse(&Index, Val); 251 return Index ^ 31; 252 #endif 253 } 254 }; 255 256 #if !defined(_MSC_VER) || defined(_M_X64) 257 template <typename T> struct LeadingZerosCounter<T, 8> { 258 static unsigned count(T Val) { 259 if (Val == 0) 260 return 64; 261 262 #if __has_builtin(__builtin_clzll) || defined(__GNUC__) 263 return __builtin_clzll(Val); 264 #elif defined(_MSC_VER) 265 unsigned long Index; 266 _BitScanReverse64(&Index, Val); 267 return Index ^ 63; 268 #endif 269 } 270 }; 271 #endif 272 #endif 273 } // namespace detail 274 275 /// Count number of 0's from the most significant bit to the least 276 /// stopping at the first 1. 277 /// 278 /// Only unsigned integral types are allowed. 279 /// 280 /// Returns std::numeric_limits<T>::digits on an input of 0. 281 template <typename T> [[nodiscard]] int countl_zero(T Val) { 282 static_assert(std::is_unsigned_v<T>, 283 "Only unsigned integral types are allowed."); 284 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val); 285 } 286 287 /// Count the number of ones from the most significant bit to the first 288 /// zero bit. 289 /// 290 /// Ex. countl_one(0xFF0FFF00) == 8. 291 /// Only unsigned integral types are allowed. 292 /// 293 /// Returns std::numeric_limits<T>::digits on an input of all ones. 294 template <typename T> [[nodiscard]] int countl_one(T Value) { 295 static_assert(std::is_unsigned_v<T>, 296 "Only unsigned integral types are allowed."); 297 return llvm::countl_zero<T>(~Value); 298 } 299 300 /// Count the number of ones from the least significant bit to the first 301 /// zero bit. 302 /// 303 /// Ex. countr_one(0x00FF00FF) == 8. 304 /// Only unsigned integral types are allowed. 305 /// 306 /// Returns std::numeric_limits<T>::digits on an input of all ones. 307 template <typename T> [[nodiscard]] int countr_one(T Value) { 308 static_assert(std::is_unsigned_v<T>, 309 "Only unsigned integral types are allowed."); 310 return llvm::countr_zero<T>(~Value); 311 } 312 313 /// Returns the number of bits needed to represent Value if Value is nonzero. 314 /// Returns 0 otherwise. 315 /// 316 /// Ex. bit_width(5) == 3. 317 template <typename T> [[nodiscard]] int bit_width(T Value) { 318 static_assert(std::is_unsigned_v<T>, 319 "Only unsigned integral types are allowed."); 320 return std::numeric_limits<T>::digits - llvm::countl_zero(Value); 321 } 322 323 /// Returns the largest integral power of two no greater than Value if Value is 324 /// nonzero. Returns 0 otherwise. 325 /// 326 /// Ex. bit_floor(5) == 4. 327 template <typename T> [[nodiscard]] T bit_floor(T Value) { 328 static_assert(std::is_unsigned_v<T>, 329 "Only unsigned integral types are allowed."); 330 if (!Value) 331 return 0; 332 return T(1) << (llvm::bit_width(Value) - 1); 333 } 334 335 /// Returns the smallest integral power of two no smaller than Value if Value is 336 /// nonzero. Returns 1 otherwise. 337 /// 338 /// Ex. bit_ceil(5) == 8. 339 /// 340 /// The return value is undefined if the input is larger than the largest power 341 /// of two representable in T. 342 template <typename T> [[nodiscard]] T bit_ceil(T Value) { 343 static_assert(std::is_unsigned_v<T>, 344 "Only unsigned integral types are allowed."); 345 if (Value < 2) 346 return 1; 347 return T(1) << llvm::bit_width<T>(Value - 1u); 348 } 349 350 namespace detail { 351 template <typename T, std::size_t SizeOfT> struct PopulationCounter { 352 static int count(T Value) { 353 // Generic version, forward to 32 bits. 354 static_assert(SizeOfT <= 4, "Not implemented!"); 355 #if defined(__GNUC__) 356 return (int)__builtin_popcount(Value); 357 #else 358 uint32_t v = Value; 359 v = v - ((v >> 1) & 0x55555555); 360 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 361 return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24); 362 #endif 363 } 364 }; 365 366 template <typename T> struct PopulationCounter<T, 8> { 367 static int count(T Value) { 368 #if defined(__GNUC__) 369 return (int)__builtin_popcountll(Value); 370 #else 371 uint64_t v = Value; 372 v = v - ((v >> 1) & 0x5555555555555555ULL); 373 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); 374 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; 375 return int((uint64_t)(v * 0x0101010101010101ULL) >> 56); 376 #endif 377 } 378 }; 379 } // namespace detail 380 381 /// Count the number of set bits in a value. 382 /// Ex. popcount(0xF000F000) = 8 383 /// Returns 0 if the word is zero. 384 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> 385 [[nodiscard]] inline int popcount(T Value) noexcept { 386 return detail::PopulationCounter<T, sizeof(T)>::count(Value); 387 } 388 389 // Forward-declare rotr so that rotl can use it. 390 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> 391 [[nodiscard]] constexpr T rotr(T V, int R); 392 393 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> 394 [[nodiscard]] constexpr T rotl(T V, int R) { 395 unsigned N = std::numeric_limits<T>::digits; 396 397 R = R % N; 398 if (!R) 399 return V; 400 401 if (R < 0) 402 return llvm::rotr(V, -R); 403 404 return (V << R) | (V >> (N - R)); 405 } 406 407 template <typename T, typename> [[nodiscard]] constexpr T rotr(T V, int R) { 408 unsigned N = std::numeric_limits<T>::digits; 409 410 R = R % N; 411 if (!R) 412 return V; 413 414 if (R < 0) 415 return llvm::rotl(V, -R); 416 417 return (V >> R) | (V << (N - R)); 418 } 419 420 } // namespace llvm 421 422 #endif 423