libc/src/__support/CPP/bit.h

   1 //===-- Implementation of the C++20 bit header  -----------------*- 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 // This is inspired by LLVM ADT/bit.h header.
   9 // Some functions are missing, we can add them as needed (popcount, byteswap).
  10
  11 #ifndef LLVM_LIBC_SRC___SUPPORT_CPP_BIT_H
  12 #define LLVM_LIBC_SRC___SUPPORT_CPP_BIT_H
  13
  14 #include "src/__support/CPP/limits.h" // numeric_limits
  15 #include "src/__support/CPP/type_traits.h"
  16 #include "src/__support/macros/attributes.h"
  17 #include "src/__support/macros/config.h"
  18 #include "src/__support/macros/sanitizer.h"
  19
  20 #include <stdint.h>
  21
  22 namespace LIBC_NAMESPACE_DECL {
  23 namespace cpp {
  24
  25 #if __has_builtin(__builtin_memcpy_inline)
  26 #define LLVM_LIBC_HAS_BUILTIN_MEMCPY_INLINE
  27 #endif
  28
  29 // This implementation of bit_cast requires trivially-constructible To, to avoid
  30 // UB in the implementation.
  31 template <typename To, typename From>
  32 LIBC_INLINE constexpr cpp::enable_if_t<
  33     (sizeof(To) == sizeof(From)) &&
  34         cpp::is_trivially_constructible<To>::value &&
  35         cpp::is_trivially_copyable<To>::value &&
  36         cpp::is_trivially_copyable<From>::value,
  37     To>
  38 bit_cast(const From &from) {
  39   MSAN_UNPOISON(&from, sizeof(From));
  40 #if __has_builtin(__builtin_bit_cast)
  41   return __builtin_bit_cast(To, from);
  42 #else
  43   To to;
  44   char *dst = reinterpret_cast<char *>(&to);
  45   const char *src = reinterpret_cast<const char *>(&from);
  46 #if __has_builtin(__builtin_memcpy_inline)
  47   __builtin_memcpy_inline(dst, src, sizeof(To));
  48 #else
  49   for (unsigned i = 0; i < sizeof(To); ++i)
  50     dst[i] = src[i];
  51 #endif // __has_builtin(__builtin_memcpy_inline)
  52   return to;
  53 #endif // __has_builtin(__builtin_bit_cast)
  54 }
  55
  56 template <typename T>
  57 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>,
  58                                                      bool>
  59 has_single_bit(T value) {
  60   return (value != 0) && ((value & (value - 1)) == 0);
  61 }
  62
  63 // A temporary macro to add template function specialization when compiler
  64 // builtin is available.
  65 #define ADD_SPECIALIZATION(NAME, TYPE, BUILTIN)                                \
  66   template <> [[nodiscard]] LIBC_INLINE constexpr int NAME<TYPE>(TYPE value) { \
  67     static_assert(cpp::is_unsigned_v<TYPE>);                                   \
  68     return value == 0 ? cpp::numeric_limits<TYPE>::digits : BUILTIN(value);    \
  69   }
  70
  71 /// Count number of 0's from the least significant bit to the most
  72 ///   stopping at the first 1.
  73 ///
  74 /// Only unsigned integral types are allowed.
  75 ///
  76 /// Returns cpp::numeric_limits<T>::digits on an input of 0.
  77 // clang-19+, gcc-14+
  78 #if __has_builtin(__builtin_ctzg)
  79 template <typename T>
  80 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
  81 countr_zero(T value) {
  82   return __builtin_ctzg(value, cpp::numeric_limits<T>::digits);
  83 }
  84 #else
  85 template <typename T>
  86 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
  87 countr_zero(T value) {
  88   if (!value)
  89     return cpp::numeric_limits<T>::digits;
  90   if (value & 0x1)
  91     return 0;
  92   // Bisection method.
  93   unsigned zero_bits = 0;
  94   unsigned shift = cpp::numeric_limits<T>::digits >> 1;
  95   T mask = cpp::numeric_limits<T>::max() >> shift;
  96   while (shift) {
  97     if ((value & mask) == 0) {
  98       value >>= shift;
  99       zero_bits |= shift;
 100     }
 101     shift >>= 1;
 102     mask >>= shift;
 103   }
 104   return zero_bits;
 105 }
 106 #if __has_builtin(__builtin_ctzs)
 107 ADD_SPECIALIZATION(countr_zero, unsigned short, __builtin_ctzs)
 108 #endif
 109 ADD_SPECIALIZATION(countr_zero, unsigned int, __builtin_ctz)
 110 ADD_SPECIALIZATION(countr_zero, unsigned long, __builtin_ctzl)
 111 ADD_SPECIALIZATION(countr_zero, unsigned long long, __builtin_ctzll)
 112 #endif // __has_builtin(__builtin_ctzg)
 113
 114 /// Count number of 0's from the most significant bit to the least
 115 ///   stopping at the first 1.
 116 ///
 117 /// Only unsigned integral types are allowed.
 118 ///
 119 /// Returns cpp::numeric_limits<T>::digits on an input of 0.
 120 // clang-19+, gcc-14+
 121 #if __has_builtin(__builtin_clzg)
 122 template <typename T>
 123 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
 124 countl_zero(T value) {
 125   return __builtin_clzg(value, cpp::numeric_limits<T>::digits);
 126 }
 127 #else
 128 template <typename T>
 129 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
 130 countl_zero(T value) {
 131   if (!value)
 132     return cpp::numeric_limits<T>::digits;
 133   // Bisection method.
 134   unsigned zero_bits = 0;
 135   for (unsigned shift = cpp::numeric_limits<T>::digits >> 1; shift;
 136        shift >>= 1) {
 137     T tmp = value >> shift;
 138     if (tmp)
 139       value = tmp;
 140     else
 141       zero_bits |= shift;
 142   }
 143   return zero_bits;
 144 }
 145 #if __has_builtin(__builtin_clzs)
 146 ADD_SPECIALIZATION(countl_zero, unsigned short, __builtin_clzs)
 147 #endif
 148 ADD_SPECIALIZATION(countl_zero, unsigned int, __builtin_clz)
 149 ADD_SPECIALIZATION(countl_zero, unsigned long, __builtin_clzl)
 150 ADD_SPECIALIZATION(countl_zero, unsigned long long, __builtin_clzll)
 151 #endif // __has_builtin(__builtin_clzg)
 152
 153 #undef ADD_SPECIALIZATION
 154
 155 /// Count the number of ones from the most significant bit to the first
 156 /// zero bit.
 157 ///
 158 /// Ex. countl_one(0xFF0FFF00) == 8.
 159 /// Only unsigned integral types are allowed.
 160 ///
 161 /// Returns cpp::numeric_limits<T>::digits on an input of all ones.
 162 template <typename T>
 163 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
 164 countl_one(T value) {
 165   return cpp::countl_zero<T>(~value);
 166 }
 167
 168 /// Count the number of ones from the least significant bit to the first
 169 /// zero bit.
 170 ///
 171 /// Ex. countr_one(0x00FF00FF) == 8.
 172 /// Only unsigned integral types are allowed.
 173 ///
 174 /// Returns cpp::numeric_limits<T>::digits on an input of all ones.
 175 template <typename T>
 176 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
 177 countr_one(T value) {
 178   return cpp::countr_zero<T>(~value);
 179 }
 180
 181 /// Returns the number of bits needed to represent value if value is nonzero.
 182 /// Returns 0 otherwise.
 183 ///
 184 /// Ex. bit_width(5) == 3.
 185 template <typename T>
 186 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
 187 bit_width(T value) {
 188   return cpp::numeric_limits<T>::digits - cpp::countl_zero(value);
 189 }
 190
 191 /// Returns the largest integral power of two no greater than value if value is
 192 /// nonzero.  Returns 0 otherwise.
 193 ///
 194 /// Ex. bit_floor(5) == 4.
 195 template <typename T>
 196 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
 197 bit_floor(T value) {
 198   if (!value)
 199     return 0;
 200   return static_cast<T>(T(1) << (cpp::bit_width(value) - 1));
 201 }
 202
 203 /// Returns the smallest integral power of two no smaller than value if value is
 204 /// nonzero.  Returns 1 otherwise.
 205 ///
 206 /// Ex. bit_ceil(5) == 8.
 207 ///
 208 /// The return value is undefined if the input is larger than the largest power
 209 /// of two representable in T.
 210 template <typename T>
 211 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
 212 bit_ceil(T value) {
 213   if (value < 2)
 214     return 1;
 215   return static_cast<T>(T(1) << cpp::bit_width(value - 1U));
 216 }
 217
 218 // Rotate algorithms make use of "Safe, Efficient, and Portable Rotate in C/C++"
 219 // from https://blog.regehr.org/archives/1063.
 220
 221 // Forward-declare rotr so that rotl can use it.
 222 template <typename T>
 223 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
 224 rotr(T value, int rotate);
 225
 226 template <typename T>
 227 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
 228 rotl(T value, int rotate) {
 229   constexpr unsigned N = cpp::numeric_limits<T>::digits;
 230   rotate = rotate % N;
 231   if (!rotate)
 232     return value;
 233   if (rotate < 0)
 234     return cpp::rotr<T>(value, -rotate);
 235   return (value << rotate) | (value >> (N - rotate));
 236 }
 237
 238 template <typename T>
 239 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
 240 rotr(T value, int rotate) {
 241   constexpr unsigned N = cpp::numeric_limits<T>::digits;
 242   rotate = rotate % N;
 243   if (!rotate)
 244     return value;
 245   if (rotate < 0)
 246     return cpp::rotl<T>(value, -rotate);
 247   return (value >> rotate) | (value << (N - rotate));
 248 }
 249
 250 // TODO: Do we need this function at all? How is it different from
 251 // 'static_cast'?
 252 template <class To, class From>
 253 LIBC_INLINE constexpr To bit_or_static_cast(const From &from) {
 254   if constexpr (sizeof(To) == sizeof(From)) {
 255     return bit_cast<To>(from);
 256   } else {
 257     return static_cast<To>(from);
 258   }
 259 }
 260
 261 /// Count number of 1's aka population count or Hamming weight.
 262 ///
 263 /// Only unsigned integral types are allowed.
 264 // clang-19+, gcc-14+
 265 #if __has_builtin(__builtin_popcountg)
 266 template <typename T>
 267 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
 268 popcount(T value) {
 269   return __builtin_popcountg(value);
 270 }
 271 #else // !__has_builtin(__builtin_popcountg)
 272 template <typename T>
 273 [[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
 274 popcount(T value) {
 275   int count = 0;
 276   while (value) {
 277     value &= value - 1;
 278     ++count;
 279   }
 280   return count;
 281 }
 282 #define ADD_SPECIALIZATION(TYPE, BUILTIN)                                      \
 283   template <>                                                                  \
 284   [[nodiscard]] LIBC_INLINE constexpr int popcount<TYPE>(TYPE value) {         \
 285     return BUILTIN(value);                                                     \
 286   }
 287 ADD_SPECIALIZATION(unsigned char, __builtin_popcount)
 288 ADD_SPECIALIZATION(unsigned short, __builtin_popcount)
 289 ADD_SPECIALIZATION(unsigned, __builtin_popcount)
 290 ADD_SPECIALIZATION(unsigned long, __builtin_popcountl)
 291 ADD_SPECIALIZATION(unsigned long long, __builtin_popcountll)
 292 #endif // __builtin_popcountg
 293 #undef ADD_SPECIALIZATION
 294
 295 } // namespace cpp
 296 } // namespace LIBC_NAMESPACE_DECL
 297
 298 #endif // LLVM_LIBC_SRC___SUPPORT_CPP_BIT_H