317 lines · c
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-exception6//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_H12#define LLVM_LIBC_SRC___SUPPORT_CPP_BIT_H13 14#include "hdr/stdint_proxy.h"15#include "src/__support/CPP/limits.h" // numeric_limits16#include "src/__support/CPP/type_traits.h"17#include "src/__support/macros/attributes.h"18#include "src/__support/macros/config.h"19#include "src/__support/macros/properties/compiler.h"20#include "src/__support/macros/sanitizer.h"21 22namespace LIBC_NAMESPACE_DECL {23namespace cpp {24 25#if __has_builtin(__builtin_memcpy_inline)26#define LLVM_LIBC_HAS_BUILTIN_MEMCPY_INLINE27#endif28 29// This implementation of bit_cast requires trivially-constructible To, to avoid30// UB in the implementation.31template <typename To, typename From>32LIBC_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>38bit_cast(const From &from) {39 MSAN_UNPOISON(&from, sizeof(From));40#if __has_builtin(__builtin_bit_cast) || defined(LIBC_COMPILER_IS_MSVC)41 return __builtin_bit_cast(To, from);42#else43 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#else49 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 56template <typename T>57[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>,58 bool>59has_single_bit(T value) {60 return (value != 0) && ((value & (value - 1)) == 0);61}62 63// A temporary macro to add template function specialization when compiler64// 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 most72/// 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)79template <typename T>80[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>81countr_zero(T value) {82 return __builtin_ctzg(value, cpp::numeric_limits<T>::digits);83}84#else85template <typename T>86[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>87countr_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 static_cast<int>(zero_bits);105}106#if __has_builtin(__builtin_ctzs)107ADD_SPECIALIZATION(countr_zero, unsigned short, __builtin_ctzs)108#endif // __has_builtin(__builtin_ctzs)109#if __has_builtin(__builtin_ctz)110ADD_SPECIALIZATION(countr_zero, unsigned int, __builtin_ctz)111#endif // __has_builtin(__builtin_ctz)112#if __has_builtin(__builtin_ctzl)113ADD_SPECIALIZATION(countr_zero, unsigned long, __builtin_ctzl)114#endif // __has_builtin(__builtin_ctzl)115#if __has_builtin(__builtin_ctzll)116ADD_SPECIALIZATION(countr_zero, unsigned long long, __builtin_ctzll)117#endif // __has_builtin(__builtin_ctzll)118#endif // __has_builtin(__builtin_ctzg)119 120/// Count number of 0's from the most significant bit to the least121/// stopping at the first 1.122///123/// Only unsigned integral types are allowed.124///125/// Returns cpp::numeric_limits<T>::digits on an input of 0.126// clang-19+, gcc-14+127#if __has_builtin(__builtin_clzg)128template <typename T>129[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>130countl_zero(T value) {131 return __builtin_clzg(value, cpp::numeric_limits<T>::digits);132}133#else134template <typename T>135[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>136countl_zero(T value) {137 if (!value)138 return cpp::numeric_limits<T>::digits;139 // Bisection method.140 unsigned zero_bits = 0;141 for (unsigned shift = cpp::numeric_limits<T>::digits >> 1; shift;142 shift >>= 1) {143 T tmp = value >> shift;144 if (tmp)145 value = tmp;146 else147 zero_bits |= shift;148 }149 return static_cast<int>(zero_bits);150}151#if __has_builtin(__builtin_clzs)152ADD_SPECIALIZATION(countl_zero, unsigned short, __builtin_clzs)153#endif // __has_builtin(__builtin_clzs)154#if __has_builtin(__builtin_clz)155ADD_SPECIALIZATION(countl_zero, unsigned int, __builtin_clz)156#endif // __has_builtin(__builtin_clz)157#if __has_builtin(__builtin_clzl)158ADD_SPECIALIZATION(countl_zero, unsigned long, __builtin_clzl)159#endif // __has_builtin(__builtin_clzl)160#if __has_builtin(__builtin_clzll)161ADD_SPECIALIZATION(countl_zero, unsigned long long, __builtin_clzll)162#endif // __has_builtin(__builtin_clzll)163#endif // __has_builtin(__builtin_clzg)164 165#undef ADD_SPECIALIZATION166 167/// Count the number of ones from the most significant bit to the first168/// zero bit.169///170/// Ex. countl_one(0xFF0FFF00) == 8.171/// Only unsigned integral types are allowed.172///173/// Returns cpp::numeric_limits<T>::digits on an input of all ones.174template <typename T>175[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>176countl_one(T value) {177 return cpp::countl_zero<T>(static_cast<T>(~value));178}179 180/// Count the number of ones from the least significant bit to the first181/// zero bit.182///183/// Ex. countr_one(0x00FF00FF) == 8.184/// Only unsigned integral types are allowed.185///186/// Returns cpp::numeric_limits<T>::digits on an input of all ones.187template <typename T>188[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>189countr_one(T value) {190 return cpp::countr_zero<T>(static_cast<T>(~value));191}192 193/// Returns the number of bits needed to represent value if value is nonzero.194/// Returns 0 otherwise.195///196/// Ex. bit_width(5) == 3.197template <typename T>198[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>199bit_width(T value) {200 return cpp::numeric_limits<T>::digits - cpp::countl_zero(value);201}202 203/// Returns the largest integral power of two no greater than value if value is204/// nonzero. Returns 0 otherwise.205///206/// Ex. bit_floor(5) == 4.207template <typename T>208[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>209bit_floor(T value) {210 if (!value)211 return 0;212 return static_cast<T>(T(1) << (cpp::bit_width(value) - 1));213}214 215/// Returns the smallest integral power of two no smaller than value if value is216/// nonzero. Returns 1 otherwise.217///218/// Ex. bit_ceil(5) == 8.219///220/// The return value is undefined if the input is larger than the largest power221/// of two representable in T.222template <typename T>223[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>224bit_ceil(T value) {225 if (value < 2)226 return 1;227 return static_cast<T>(T(1) << cpp::bit_width(value - 1U));228}229 230// Rotate algorithms make use of "Safe, Efficient, and Portable Rotate in C/C++"231// from https://blog.regehr.org/archives/1063.232 233// Forward-declare rotr so that rotl can use it.234template <typename T>235[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>236rotr(T value, int rotate);237 238template <typename T>239[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>240rotl(T value, int rotate) {241 constexpr int N = cpp::numeric_limits<T>::digits;242 rotate = rotate % N;243 if (!rotate)244 return value;245 if (rotate < 0)246 return cpp::rotr<T>(value, -rotate);247 return static_cast<T>((value << rotate) | (value >> (N - rotate)));248}249 250template <typename T>251[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>252rotr(T value, int rotate) {253 constexpr int N = cpp::numeric_limits<T>::digits;254 rotate = rotate % N;255 if (!rotate)256 return value;257 if (rotate < 0)258 return cpp::rotl<T>(value, -rotate);259 return static_cast<T>((value >> rotate) | (value << (N - rotate)));260}261 262// TODO: Do we need this function at all? How is it different from263// 'static_cast'?264template <class To, class From>265LIBC_INLINE constexpr To bit_or_static_cast(const From &from) {266 if constexpr (sizeof(To) == sizeof(From)) {267 return bit_cast<To>(from);268 } else {269 return static_cast<To>(from);270 }271}272 273/// Count number of 1's aka population count or Hamming weight.274///275/// Only unsigned integral types are allowed.276// clang-19+, gcc-14+277#if __has_builtin(__builtin_popcountg)278template <typename T>279[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>280popcount(T value) {281 return __builtin_popcountg(value);282}283#else // !__has_builtin(__builtin_popcountg)284template <typename T>285[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>286popcount(T value) {287 int count = 0;288 while (value) {289 value &= value - 1;290 ++count;291 }292 return count;293}294#define ADD_SPECIALIZATION(TYPE, BUILTIN) \295 template <> \296 [[nodiscard]] LIBC_INLINE constexpr int popcount<TYPE>(TYPE value) { \297 return BUILTIN(value); \298 }299#if __has_builtin(__builtin_popcount)300ADD_SPECIALIZATION(unsigned char, __builtin_popcount)301ADD_SPECIALIZATION(unsigned short, __builtin_popcount)302ADD_SPECIALIZATION(unsigned, __builtin_popcount)303#endif // __builtin_popcount304#if __has_builtin(__builtin_popcountl)305ADD_SPECIALIZATION(unsigned long, __builtin_popcountl)306#endif // __builtin_popcountl307#if __has_builtin(__builtin_popcountll)308ADD_SPECIALIZATION(unsigned long long, __builtin_popcountll)309#endif // __builtin_popcountll310#endif // __builtin_popcountg311#undef ADD_SPECIALIZATION312 313} // namespace cpp314} // namespace LIBC_NAMESPACE_DECL315 316#endif // LLVM_LIBC_SRC___SUPPORT_CPP_BIT_H317