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