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