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>
bit_cast(const From & from)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>
has_single_bit(T value)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>
countr_zero(T value)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>
countr_zero(T value)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)
ADD_SPECIALIZATION(countr_zero,unsigned short,__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>
countl_one(T value)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>
countr_one(T value)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>
bit_width(T value)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>
bit_floor(T value)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>
bit_ceil(T value)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>
rotl(T value,int rotate)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>
rotr(T value,int rotate)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>
bit_or_static_cast(const From & 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>
popcount(T value)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>
popcount(T value)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
299