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