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
21namespace 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.
29template <typename To, typename From>
30LIBC_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>
36bit_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
54template <typename T>
55[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>,
56 bool>
57has_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)
77template <typename T>
78[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
79countr_zero(T value) {
80 return __builtin_ctzg(value, cpp::numeric_limits<T>::digits);
81}
82#else
83template <typename T>
84[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
85countr_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)
105ADD_SPECIALIZATION(countr_zero, unsigned short, __builtin_ctzs)
106#endif
107ADD_SPECIALIZATION(countr_zero, unsigned int, __builtin_ctz)
108ADD_SPECIALIZATION(countr_zero, unsigned long, __builtin_ctzl)
109ADD_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)
120template <typename T>
121[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
122countl_zero(T value) {
123 return __builtin_clzg(value, cpp::numeric_limits<T>::digits);
124}
125#else
126template <typename T>
127[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
128countl_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)
144ADD_SPECIALIZATION(countl_zero, unsigned short, __builtin_clzs)
145#endif
146ADD_SPECIALIZATION(countl_zero, unsigned int, __builtin_clz)
147ADD_SPECIALIZATION(countl_zero, unsigned long, __builtin_clzl)
148ADD_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.
160template <typename T>
161[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
162countl_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.
173template <typename T>
174[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
175countr_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.
183template <typename T>
184[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
185bit_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.
193template <typename T>
194[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
195bit_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.
208template <typename T>
209[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
210bit_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.
220template <typename T>
221[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
222rotr(T value, int rotate);
223
224template <typename T>
225[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
226rotl(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
236template <typename T>
237[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, T>
238rotr(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'?
250template <class To, class From>
251LIBC_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)
264template <typename T>
265[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
266popcount(T value) {
267 return __builtin_popcountg(value);
268}
269#else // !__has_builtin(__builtin_popcountg)
270template <typename T>
271[[nodiscard]] LIBC_INLINE constexpr cpp::enable_if_t<cpp::is_unsigned_v<T>, int>
272popcount(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 }
284ADD_SPECIALIZATION(unsigned char, __builtin_popcount)
285ADD_SPECIALIZATION(unsigned short, __builtin_popcount)
286ADD_SPECIALIZATION(unsigned, __builtin_popcount)
287ADD_SPECIALIZATION(unsigned long, __builtin_popcountl)
288ADD_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

source code of libc/src/__support/CPP/bit.h