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> 60extern "C" { 61unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask); 62unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask); 63unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask); 64unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); 65} 66#endif 67 68namespace llvm { 69 70enum 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. 83template < 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. 100template <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 145template <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 150namespace detail { 151template <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) 175template <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) 191template <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. 215template <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 221namespace detail { 222template <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) 241template <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) 257template <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. 281template <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. 294template <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. 307template <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. 317template <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. 327template <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. 342template <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 350namespace detail { 351template <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 366template <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. 384template <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. 390template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> 391[[nodiscard]] constexpr T rotr(T V, int R); 392 393template <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 407template <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