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
22namespace LIBC_NAMESPACE_DECL {
23namespace 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.
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)
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
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 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)
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#else
85template <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
109ADD_SPECIALIZATION(countr_zero, unsigned int, __builtin_ctz)
110ADD_SPECIALIZATION(countr_zero, unsigned long, __builtin_ctzl)
111ADD_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)
122template <typename T>
123[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
124countl_zero(T value) {
125 return __builtin_clzg(value, cpp::numeric_limits<T>::digits);
126}
127#else
128template <typename T>
129[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
130countl_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 static_cast<int>(zero_bits);
144}
145#if __has_builtin(__builtin_clzs)
146ADD_SPECIALIZATION(countl_zero, unsigned short, __builtin_clzs)
147#endif
148ADD_SPECIALIZATION(countl_zero, unsigned int, __builtin_clz)
149ADD_SPECIALIZATION(countl_zero, unsigned long, __builtin_clzl)
150ADD_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.
162template <typename T>
163[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
164countl_one(T value) {
165 return cpp::countl_zero<T>(static_cast<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.
175template <typename T>
176[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
177countr_one(T value) {
178 return cpp::countr_zero<T>(static_cast<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.
185template <typename T>
186[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
187bit_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.
195template <typename T>
196[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
197bit_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.
210template <typename T>
211[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
212bit_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.
222template <typename T>
223[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
224rotr(T value, int rotate);
225
226template <typename T>
227[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
228rotl(T value, int rotate) {
229 constexpr int 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 static_cast<T>((value << rotate) | (value >> (N - rotate)));
236}
237
238template <typename T>
239[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
240rotr(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::rotl<T>(value, -rotate);
247 return static_cast<T>((value >> rotate) | (value << (N - rotate)));
248}
249
250// TODO: Do we need this function at all? How is it different from
251// 'static_cast'?
252template <class To, class From>
253LIBC_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)
266template <typename T>
267[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
268popcount(T value) {
269 return __builtin_popcountg(value);
270}
271#else // !__has_builtin(__builtin_popcountg)
272template <typename T>
273[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
274popcount(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 }
287ADD_SPECIALIZATION(unsigned char, __builtin_popcount)
288ADD_SPECIALIZATION(unsigned short, __builtin_popcount)
289ADD_SPECIALIZATION(unsigned, __builtin_popcount)
290ADD_SPECIALIZATION(unsigned long, __builtin_popcountl)
291ADD_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
299