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