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