llvm/ADT/bit.h

0001 //===-- llvm/ADT/bit.h - C++20 <bit> ----------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file implements the C++20 <bit> header.
0011 ///
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_ADT_BIT_H
0015 #define LLVM_ADT_BIT_H
0016
0017 #include "llvm/Support/Compiler.h"
0018 #include <cstdint>
0019 #include <limits>
0020 #include <type_traits>
0021
0022 #if !__has_builtin(__builtin_bit_cast)
0023 #include <cstring>
0024 #endif
0025
0026 #if defined(_MSC_VER) && !defined(_DEBUG)
0027 #include <cstdlib>  // for _byteswap_{ushort,ulong,uint64}
0028 #endif
0029
0030 #if defined(__linux__) || defined(__GNU__) || defined(__HAIKU__) ||            \
0031     defined(__Fuchsia__) || defined(__EMSCRIPTEN__) || defined(__NetBSD__) ||  \
0032     defined(__OpenBSD__) || defined(__DragonFly__)
0033 #include <endian.h>
0034 #elif defined(_AIX)
0035 #include <sys/machine.h>
0036 #elif defined(__sun)
0037 /* Solaris provides _BIG_ENDIAN/_LITTLE_ENDIAN selector in sys/types.h */
0038 #include <sys/types.h>
0039 #define BIG_ENDIAN 4321
0040 #define LITTLE_ENDIAN 1234
0041 #if defined(_BIG_ENDIAN)
0042 #define BYTE_ORDER BIG_ENDIAN
0043 #else
0044 #define BYTE_ORDER LITTLE_ENDIAN
0045 #endif
0046 #elif defined(__MVS__)
0047 #define BIG_ENDIAN 4321
0048 #define LITTLE_ENDIAN 1234
0049 #define BYTE_ORDER BIG_ENDIAN
0050 #else
0051 #if !defined(BYTE_ORDER) && !defined(_WIN32)
0052 #include <machine/endian.h>
0053 #endif
0054 #endif
0055
0056 #ifdef _MSC_VER
0057 // Declare these intrinsics manually rather including intrin.h. It's very
0058 // expensive, and bit.h is popular via MathExtras.h.
0059 // #include <intrin.h>
0060 extern "C" {
0061 unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
0062 unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
0063 unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
0064 unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
0065 }
0066 #endif
0067
0068 namespace llvm {
0069
0070 enum class endianness {
0071   big,
0072   little,
0073 #if defined(BYTE_ORDER) && defined(BIG_ENDIAN) && BYTE_ORDER == BIG_ENDIAN
0074   native = big
0075 #else
0076   native = little
0077 #endif
0078 };
0079
0080 // This implementation of bit_cast is different from the C++20 one in two ways:
0081 //  - It isn't constexpr because that requires compiler support.
0082 //  - It requires trivially-constructible To, to avoid UB in the implementation.
0083 template <
0084     typename To, typename From,
0085     typename = std::enable_if_t<sizeof(To) == sizeof(From)>,
0086     typename = std::enable_if_t<std::is_trivially_constructible<To>::value>,
0087     typename = std::enable_if_t<std::is_trivially_copyable<To>::value>,
0088     typename = std::enable_if_t<std::is_trivially_copyable<From>::value>>
0089 [[nodiscard]] inline To bit_cast(const From &from) noexcept {
0090 #if __has_builtin(__builtin_bit_cast)
0091   return __builtin_bit_cast(To, from);
0092 #else
0093   To to;
0094   std::memcpy(&to, &from, sizeof(To));
0095   return to;
0096 #endif
0097 }
0098
0099 /// Reverses the bytes in the given integer value V.
0100 template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
0101 [[nodiscard]] constexpr T byteswap(T V) noexcept {
0102   if constexpr (sizeof(T) == 1) {
0103     return V;
0104   } else if constexpr (sizeof(T) == 2) {
0105     uint16_t UV = V;
0106 #if defined(_MSC_VER) && !defined(_DEBUG)
0107     // The DLL version of the runtime lacks these functions (bug!?), but in a
0108     // release build they're replaced with BSWAP instructions anyway.
0109     return _byteswap_ushort(UV);
0110 #else
0111     uint16_t Hi = UV << 8;
0112     uint16_t Lo = UV >> 8;
0113     return Hi | Lo;
0114 #endif
0115   } else if constexpr (sizeof(T) == 4) {
0116     uint32_t UV = V;
0117 #if __has_builtin(__builtin_bswap32)
0118     return __builtin_bswap32(UV);
0119 #elif defined(_MSC_VER) && !defined(_DEBUG)
0120     return _byteswap_ulong(UV);
0121 #else
0122     uint32_t Byte0 = UV & 0x000000FF;
0123     uint32_t Byte1 = UV & 0x0000FF00;
0124     uint32_t Byte2 = UV & 0x00FF0000;
0125     uint32_t Byte3 = UV & 0xFF000000;
0126     return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
0127 #endif
0128   } else if constexpr (sizeof(T) == 8) {
0129     uint64_t UV = V;
0130 #if __has_builtin(__builtin_bswap64)
0131     return __builtin_bswap64(UV);
0132 #elif defined(_MSC_VER) && !defined(_DEBUG)
0133     return _byteswap_uint64(UV);
0134 #else
0135     uint64_t Hi = llvm::byteswap<uint32_t>(UV);
0136     uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32);
0137     return (Hi << 32) | Lo;
0138 #endif
0139   } else {
0140     static_assert(!sizeof(T *), "Don't know how to handle the given type.");
0141     return 0;
0142   }
0143 }
0144
0145 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
0146 [[nodiscard]] constexpr inline bool has_single_bit(T Value) noexcept {
0147   return (Value != 0) && ((Value & (Value - 1)) == 0);
0148 }
0149
0150 namespace detail {
0151 template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
0152   static unsigned count(T Val) {
0153     if (!Val)
0154       return std::numeric_limits<T>::digits;
0155     if (Val & 0x1)
0156       return 0;
0157
0158     // Bisection method.
0159     unsigned ZeroBits = 0;
0160     T Shift = std::numeric_limits<T>::digits >> 1;
0161     T Mask = std::numeric_limits<T>::max() >> Shift;
0162     while (Shift) {
0163       if ((Val & Mask) == 0) {
0164         Val >>= Shift;
0165         ZeroBits |= Shift;
0166       }
0167       Shift >>= 1;
0168       Mask >>= Shift;
0169     }
0170     return ZeroBits;
0171   }
0172 };
0173
0174 #if defined(__GNUC__) || defined(_MSC_VER)
0175 template <typename T> struct TrailingZerosCounter<T, 4> {
0176   static unsigned count(T Val) {
0177     if (Val == 0)
0178       return 32;
0179
0180 #if __has_builtin(__builtin_ctz) || defined(__GNUC__)
0181     return __builtin_ctz(Val);
0182 #elif defined(_MSC_VER)
0183     unsigned long Index;
0184     _BitScanForward(&Index, Val);
0185     return Index;
0186 #endif
0187   }
0188 };
0189
0190 #if !defined(_MSC_VER) || defined(_M_X64)
0191 template <typename T> struct TrailingZerosCounter<T, 8> {
0192   static unsigned count(T Val) {
0193     if (Val == 0)
0194       return 64;
0195
0196 #if __has_builtin(__builtin_ctzll) || defined(__GNUC__)
0197     return __builtin_ctzll(Val);
0198 #elif defined(_MSC_VER)
0199     unsigned long Index;
0200     _BitScanForward64(&Index, Val);
0201     return Index;
0202 #endif
0203   }
0204 };
0205 #endif
0206 #endif
0207 } // namespace detail
0208
0209 /// Count number of 0's from the least significant bit to the most
0210 ///   stopping at the first 1.
0211 ///
0212 /// Only unsigned integral types are allowed.
0213 ///
0214 /// Returns std::numeric_limits<T>::digits on an input of 0.
0215 template <typename T> [[nodiscard]] int countr_zero(T Val) {
0216   static_assert(std::is_unsigned_v<T>,
0217                 "Only unsigned integral types are allowed.");
0218   return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val);
0219 }
0220
0221 namespace detail {
0222 template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
0223   static unsigned count(T Val) {
0224     if (!Val)
0225       return std::numeric_limits<T>::digits;
0226
0227     // Bisection method.
0228     unsigned ZeroBits = 0;
0229     for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
0230       T Tmp = Val >> Shift;
0231       if (Tmp)
0232         Val = Tmp;
0233       else
0234         ZeroBits |= Shift;
0235     }
0236     return ZeroBits;
0237   }
0238 };
0239
0240 #if defined(__GNUC__) || defined(_MSC_VER)
0241 template <typename T> struct LeadingZerosCounter<T, 4> {
0242   static unsigned count(T Val) {
0243     if (Val == 0)
0244       return 32;
0245
0246 #if __has_builtin(__builtin_clz) || defined(__GNUC__)
0247     return __builtin_clz(Val);
0248 #elif defined(_MSC_VER)
0249     unsigned long Index;
0250     _BitScanReverse(&Index, Val);
0251     return Index ^ 31;
0252 #endif
0253   }
0254 };
0255
0256 #if !defined(_MSC_VER) || defined(_M_X64)
0257 template <typename T> struct LeadingZerosCounter<T, 8> {
0258   static unsigned count(T Val) {
0259     if (Val == 0)
0260       return 64;
0261
0262 #if __has_builtin(__builtin_clzll) || defined(__GNUC__)
0263     return __builtin_clzll(Val);
0264 #elif defined(_MSC_VER)
0265     unsigned long Index;
0266     _BitScanReverse64(&Index, Val);
0267     return Index ^ 63;
0268 #endif
0269   }
0270 };
0271 #endif
0272 #endif
0273 } // namespace detail
0274
0275 /// Count number of 0's from the most significant bit to the least
0276 ///   stopping at the first 1.
0277 ///
0278 /// Only unsigned integral types are allowed.
0279 ///
0280 /// Returns std::numeric_limits<T>::digits on an input of 0.
0281 template <typename T> [[nodiscard]] int countl_zero(T Val) {
0282   static_assert(std::is_unsigned_v<T>,
0283                 "Only unsigned integral types are allowed.");
0284   return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val);
0285 }
0286
0287 /// Count the number of ones from the most significant bit to the first
0288 /// zero bit.
0289 ///
0290 /// Ex. countl_one(0xFF0FFF00) == 8.
0291 /// Only unsigned integral types are allowed.
0292 ///
0293 /// Returns std::numeric_limits<T>::digits on an input of all ones.
0294 template <typename T> [[nodiscard]] int countl_one(T Value) {
0295   static_assert(std::is_unsigned_v<T>,
0296                 "Only unsigned integral types are allowed.");
0297   return llvm::countl_zero<T>(~Value);
0298 }
0299
0300 /// Count the number of ones from the least significant bit to the first
0301 /// zero bit.
0302 ///
0303 /// Ex. countr_one(0x00FF00FF) == 8.
0304 /// Only unsigned integral types are allowed.
0305 ///
0306 /// Returns std::numeric_limits<T>::digits on an input of all ones.
0307 template <typename T> [[nodiscard]] int countr_one(T Value) {
0308   static_assert(std::is_unsigned_v<T>,
0309                 "Only unsigned integral types are allowed.");
0310   return llvm::countr_zero<T>(~Value);
0311 }
0312
0313 /// Returns the number of bits needed to represent Value if Value is nonzero.
0314 /// Returns 0 otherwise.
0315 ///
0316 /// Ex. bit_width(5) == 3.
0317 template <typename T> [[nodiscard]] int bit_width(T Value) {
0318   static_assert(std::is_unsigned_v<T>,
0319                 "Only unsigned integral types are allowed.");
0320   return std::numeric_limits<T>::digits - llvm::countl_zero(Value);
0321 }
0322
0323 /// Returns the largest integral power of two no greater than Value if Value is
0324 /// nonzero.  Returns 0 otherwise.
0325 ///
0326 /// Ex. bit_floor(5) == 4.
0327 template <typename T> [[nodiscard]] T bit_floor(T Value) {
0328   static_assert(std::is_unsigned_v<T>,
0329                 "Only unsigned integral types are allowed.");
0330   if (!Value)
0331     return 0;
0332   return T(1) << (llvm::bit_width(Value) - 1);
0333 }
0334
0335 /// Returns the smallest integral power of two no smaller than Value if Value is
0336 /// nonzero.  Returns 1 otherwise.
0337 ///
0338 /// Ex. bit_ceil(5) == 8.
0339 ///
0340 /// The return value is undefined if the input is larger than the largest power
0341 /// of two representable in T.
0342 template <typename T> [[nodiscard]] T bit_ceil(T Value) {
0343   static_assert(std::is_unsigned_v<T>,
0344                 "Only unsigned integral types are allowed.");
0345   if (Value < 2)
0346     return 1;
0347   return T(1) << llvm::bit_width<T>(Value - 1u);
0348 }
0349
0350 namespace detail {
0351 template <typename T, std::size_t SizeOfT> struct PopulationCounter {
0352   static int count(T Value) {
0353     // Generic version, forward to 32 bits.
0354     static_assert(SizeOfT <= 4, "Not implemented!");
0355 #if defined(__GNUC__)
0356     return (int)__builtin_popcount(Value);
0357 #else
0358     uint32_t v = Value;
0359     v = v - ((v >> 1) & 0x55555555);
0360     v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
0361     return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24);
0362 #endif
0363   }
0364 };
0365
0366 template <typename T> struct PopulationCounter<T, 8> {
0367   static int count(T Value) {
0368 #if defined(__GNUC__)
0369     return (int)__builtin_popcountll(Value);
0370 #else
0371     uint64_t v = Value;
0372     v = v - ((v >> 1) & 0x5555555555555555ULL);
0373     v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
0374     v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
0375     return int((uint64_t)(v * 0x0101010101010101ULL) >> 56);
0376 #endif
0377   }
0378 };
0379 } // namespace detail
0380
0381 /// Count the number of set bits in a value.
0382 /// Ex. popcount(0xF000F000) = 8
0383 /// Returns 0 if the word is zero.
0384 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
0385 [[nodiscard]] inline int popcount(T Value) noexcept {
0386   return detail::PopulationCounter<T, sizeof(T)>::count(Value);
0387 }
0388
0389 // Forward-declare rotr so that rotl can use it.
0390 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
0391 [[nodiscard]] constexpr T rotr(T V, int R);
0392
0393 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
0394 [[nodiscard]] constexpr T rotl(T V, int R) {
0395   unsigned N = std::numeric_limits<T>::digits;
0396
0397   R = R % N;
0398   if (!R)
0399     return V;
0400
0401   if (R < 0)
0402     return llvm::rotr(V, -R);
0403
0404   return (V << R) | (V >> (N - R));
0405 }
0406
0407 template <typename T, typename> [[nodiscard]] constexpr T rotr(T V, int R) {
0408   unsigned N = std::numeric_limits<T>::digits;
0409
0410   R = R % N;
0411   if (!R)
0412     return V;
0413
0414   if (R < 0)
0415     return llvm::rotl(V, -R);
0416
0417   return (V >> R) | (V << (N - R));
0418 }
0419
0420 } // namespace llvm
0421
0422 #endif