1 | //===-- llvm/ADT/bit.h - C++20 <bit> ----------------------------*- 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 | /// |
9 | /// \file |
10 | /// This file implements the C++20 <bit> header. |
11 | /// |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_ADT_BIT_H |
15 | #define LLVM_ADT_BIT_H |
16 | |
17 | #include "llvm/Support/Compiler.h" |
18 | #include <cstdint> |
19 | #include <limits> |
20 | #include <type_traits> |
21 | |
22 | #if !__has_builtin(__builtin_bit_cast) |
23 | #include <cstring> |
24 | #endif |
25 | |
26 | #if defined(_MSC_VER) && !defined(_DEBUG) |
27 | #include <cstdlib> // for _byteswap_{ushort,ulong,uint64} |
28 | #endif |
29 | |
30 | #if defined(__linux__) || defined(__GNU__) || defined(__HAIKU__) || \ |
31 | defined(__Fuchsia__) || defined(__EMSCRIPTEN__) || defined(__NetBSD__) || \ |
32 | defined(__OpenBSD__) || defined(__DragonFly__) |
33 | #include <endian.h> |
34 | #elif defined(_AIX) |
35 | #include <sys/machine.h> |
36 | #elif defined(__sun) |
37 | /* Solaris provides _BIG_ENDIAN/_LITTLE_ENDIAN selector in sys/types.h */ |
38 | #include <sys/types.h> |
39 | #define BIG_ENDIAN 4321 |
40 | #define LITTLE_ENDIAN 1234 |
41 | #if defined(_BIG_ENDIAN) |
42 | #define BYTE_ORDER BIG_ENDIAN |
43 | #else |
44 | #define BYTE_ORDER LITTLE_ENDIAN |
45 | #endif |
46 | #elif defined(__MVS__) |
47 | #define BIG_ENDIAN 4321 |
48 | #define LITTLE_ENDIAN 1234 |
49 | #define BYTE_ORDER BIG_ENDIAN |
50 | #else |
51 | #if !defined(BYTE_ORDER) && !defined(_WIN32) |
52 | #include <machine/endian.h> |
53 | #endif |
54 | #endif |
55 | |
56 | #ifdef _MSC_VER |
57 | // Declare these intrinsics manually rather including intrin.h. It's very |
58 | // expensive, and bit.h is popular via MathExtras.h. |
59 | // #include <intrin.h> |
60 | extern "C" { |
61 | unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask); |
62 | unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask); |
63 | unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask); |
64 | unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); |
65 | } |
66 | #endif |
67 | |
68 | namespace llvm { |
69 | |
70 | enum class endianness { |
71 | big, |
72 | little, |
73 | #if defined(BYTE_ORDER) && defined(BIG_ENDIAN) && BYTE_ORDER == BIG_ENDIAN |
74 | native = big |
75 | #else |
76 | native = little |
77 | #endif |
78 | }; |
79 | |
80 | // This implementation of bit_cast is different from the C++20 one in two ways: |
81 | // - It isn't constexpr because that requires compiler support. |
82 | // - It requires trivially-constructible To, to avoid UB in the implementation. |
83 | template < |
84 | typename To, typename From, |
85 | typename = std::enable_if_t<sizeof(To) == sizeof(From)>, |
86 | typename = std::enable_if_t<std::is_trivially_constructible<To>::value>, |
87 | typename = std::enable_if_t<std::is_trivially_copyable<To>::value>, |
88 | typename = std::enable_if_t<std::is_trivially_copyable<From>::value>> |
89 | [[nodiscard]] inline To bit_cast(const From &from) noexcept { |
90 | #if __has_builtin(__builtin_bit_cast) |
91 | return __builtin_bit_cast(To, from); |
92 | #else |
93 | To to; |
94 | std::memcpy(&to, &from, sizeof(To)); |
95 | return to; |
96 | #endif |
97 | } |
98 | |
99 | /// Reverses the bytes in the given integer value V. |
100 | template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>> |
101 | [[nodiscard]] constexpr T byteswap(T V) noexcept { |
102 | if constexpr (sizeof(T) == 1) { |
103 | return V; |
104 | } else if constexpr (sizeof(T) == 2) { |
105 | uint16_t UV = V; |
106 | #if defined(_MSC_VER) && !defined(_DEBUG) |
107 | // The DLL version of the runtime lacks these functions (bug!?), but in a |
108 | // release build they're replaced with BSWAP instructions anyway. |
109 | return _byteswap_ushort(UV); |
110 | #else |
111 | uint16_t Hi = UV << 8; |
112 | uint16_t Lo = UV >> 8; |
113 | return Hi | Lo; |
114 | #endif |
115 | } else if constexpr (sizeof(T) == 4) { |
116 | uint32_t UV = V; |
117 | #if __has_builtin(__builtin_bswap32) |
118 | return __builtin_bswap32(UV); |
119 | #elif defined(_MSC_VER) && !defined(_DEBUG) |
120 | return _byteswap_ulong(UV); |
121 | #else |
122 | uint32_t Byte0 = UV & 0x000000FF; |
123 | uint32_t Byte1 = UV & 0x0000FF00; |
124 | uint32_t Byte2 = UV & 0x00FF0000; |
125 | uint32_t Byte3 = UV & 0xFF000000; |
126 | return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24); |
127 | #endif |
128 | } else if constexpr (sizeof(T) == 8) { |
129 | uint64_t UV = V; |
130 | #if __has_builtin(__builtin_bswap64) |
131 | return __builtin_bswap64(UV); |
132 | #elif defined(_MSC_VER) && !defined(_DEBUG) |
133 | return _byteswap_uint64(UV); |
134 | #else |
135 | uint64_t Hi = llvm::byteswap<uint32_t>(UV); |
136 | uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32); |
137 | return (Hi << 32) | Lo; |
138 | #endif |
139 | } else { |
140 | static_assert(!sizeof(T *), "Don't know how to handle the given type." ); |
141 | return 0; |
142 | } |
143 | } |
144 | |
145 | template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> |
146 | [[nodiscard]] constexpr inline bool has_single_bit(T Value) noexcept { |
147 | return (Value != 0) && ((Value & (Value - 1)) == 0); |
148 | } |
149 | |
150 | namespace detail { |
151 | template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { |
152 | static unsigned count(T Val) { |
153 | if (!Val) |
154 | return std::numeric_limits<T>::digits; |
155 | if (Val & 0x1) |
156 | return 0; |
157 | |
158 | // Bisection method. |
159 | unsigned ZeroBits = 0; |
160 | T Shift = std::numeric_limits<T>::digits >> 1; |
161 | T Mask = std::numeric_limits<T>::max() >> Shift; |
162 | while (Shift) { |
163 | if ((Val & Mask) == 0) { |
164 | Val >>= Shift; |
165 | ZeroBits |= Shift; |
166 | } |
167 | Shift >>= 1; |
168 | Mask >>= Shift; |
169 | } |
170 | return ZeroBits; |
171 | } |
172 | }; |
173 | |
174 | #if defined(__GNUC__) || defined(_MSC_VER) |
175 | template <typename T> struct TrailingZerosCounter<T, 4> { |
176 | static unsigned count(T Val) { |
177 | if (Val == 0) |
178 | return 32; |
179 | |
180 | #if __has_builtin(__builtin_ctz) || defined(__GNUC__) |
181 | return __builtin_ctz(Val); |
182 | #elif defined(_MSC_VER) |
183 | unsigned long Index; |
184 | _BitScanForward(&Index, Val); |
185 | return Index; |
186 | #endif |
187 | } |
188 | }; |
189 | |
190 | #if !defined(_MSC_VER) || defined(_M_X64) |
191 | template <typename T> struct TrailingZerosCounter<T, 8> { |
192 | static unsigned count(T Val) { |
193 | if (Val == 0) |
194 | return 64; |
195 | |
196 | #if __has_builtin(__builtin_ctzll) || defined(__GNUC__) |
197 | return __builtin_ctzll(Val); |
198 | #elif defined(_MSC_VER) |
199 | unsigned long Index; |
200 | _BitScanForward64(&Index, Val); |
201 | return Index; |
202 | #endif |
203 | } |
204 | }; |
205 | #endif |
206 | #endif |
207 | } // namespace detail |
208 | |
209 | /// Count number of 0's from the least significant bit to the most |
210 | /// stopping at the first 1. |
211 | /// |
212 | /// Only unsigned integral types are allowed. |
213 | /// |
214 | /// Returns std::numeric_limits<T>::digits on an input of 0. |
215 | template <typename T> [[nodiscard]] int countr_zero(T Val) { |
216 | static_assert(std::is_unsigned_v<T>, |
217 | "Only unsigned integral types are allowed." ); |
218 | return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val); |
219 | } |
220 | |
221 | namespace detail { |
222 | template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter { |
223 | static unsigned count(T Val) { |
224 | if (!Val) |
225 | return std::numeric_limits<T>::digits; |
226 | |
227 | // Bisection method. |
228 | unsigned ZeroBits = 0; |
229 | for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) { |
230 | T Tmp = Val >> Shift; |
231 | if (Tmp) |
232 | Val = Tmp; |
233 | else |
234 | ZeroBits |= Shift; |
235 | } |
236 | return ZeroBits; |
237 | } |
238 | }; |
239 | |
240 | #if defined(__GNUC__) || defined(_MSC_VER) |
241 | template <typename T> struct LeadingZerosCounter<T, 4> { |
242 | static unsigned count(T Val) { |
243 | if (Val == 0) |
244 | return 32; |
245 | |
246 | #if __has_builtin(__builtin_clz) || defined(__GNUC__) |
247 | return __builtin_clz(Val); |
248 | #elif defined(_MSC_VER) |
249 | unsigned long Index; |
250 | _BitScanReverse(&Index, Val); |
251 | return Index ^ 31; |
252 | #endif |
253 | } |
254 | }; |
255 | |
256 | #if !defined(_MSC_VER) || defined(_M_X64) |
257 | template <typename T> struct LeadingZerosCounter<T, 8> { |
258 | static unsigned count(T Val) { |
259 | if (Val == 0) |
260 | return 64; |
261 | |
262 | #if __has_builtin(__builtin_clzll) || defined(__GNUC__) |
263 | return __builtin_clzll(Val); |
264 | #elif defined(_MSC_VER) |
265 | unsigned long Index; |
266 | _BitScanReverse64(&Index, Val); |
267 | return Index ^ 63; |
268 | #endif |
269 | } |
270 | }; |
271 | #endif |
272 | #endif |
273 | } // namespace detail |
274 | |
275 | /// Count number of 0's from the most significant bit to the least |
276 | /// stopping at the first 1. |
277 | /// |
278 | /// Only unsigned integral types are allowed. |
279 | /// |
280 | /// Returns std::numeric_limits<T>::digits on an input of 0. |
281 | template <typename T> [[nodiscard]] int countl_zero(T Val) { |
282 | static_assert(std::is_unsigned_v<T>, |
283 | "Only unsigned integral types are allowed." ); |
284 | return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val); |
285 | } |
286 | |
287 | /// Count the number of ones from the most significant bit to the first |
288 | /// zero bit. |
289 | /// |
290 | /// Ex. countl_one(0xFF0FFF00) == 8. |
291 | /// Only unsigned integral types are allowed. |
292 | /// |
293 | /// Returns std::numeric_limits<T>::digits on an input of all ones. |
294 | template <typename T> [[nodiscard]] int countl_one(T Value) { |
295 | static_assert(std::is_unsigned_v<T>, |
296 | "Only unsigned integral types are allowed." ); |
297 | return llvm::countl_zero<T>(~Value); |
298 | } |
299 | |
300 | /// Count the number of ones from the least significant bit to the first |
301 | /// zero bit. |
302 | /// |
303 | /// Ex. countr_one(0x00FF00FF) == 8. |
304 | /// Only unsigned integral types are allowed. |
305 | /// |
306 | /// Returns std::numeric_limits<T>::digits on an input of all ones. |
307 | template <typename T> [[nodiscard]] int countr_one(T Value) { |
308 | static_assert(std::is_unsigned_v<T>, |
309 | "Only unsigned integral types are allowed." ); |
310 | return llvm::countr_zero<T>(~Value); |
311 | } |
312 | |
313 | /// Returns the number of bits needed to represent Value if Value is nonzero. |
314 | /// Returns 0 otherwise. |
315 | /// |
316 | /// Ex. bit_width(5) == 3. |
317 | template <typename T> [[nodiscard]] int bit_width(T Value) { |
318 | static_assert(std::is_unsigned_v<T>, |
319 | "Only unsigned integral types are allowed." ); |
320 | return std::numeric_limits<T>::digits - llvm::countl_zero(Value); |
321 | } |
322 | |
323 | /// Returns the largest integral power of two no greater than Value if Value is |
324 | /// nonzero. Returns 0 otherwise. |
325 | /// |
326 | /// Ex. bit_floor(5) == 4. |
327 | template <typename T> [[nodiscard]] T bit_floor(T Value) { |
328 | static_assert(std::is_unsigned_v<T>, |
329 | "Only unsigned integral types are allowed." ); |
330 | if (!Value) |
331 | return 0; |
332 | return T(1) << (llvm::bit_width(Value) - 1); |
333 | } |
334 | |
335 | /// Returns the smallest integral power of two no smaller than Value if Value is |
336 | /// nonzero. Returns 1 otherwise. |
337 | /// |
338 | /// Ex. bit_ceil(5) == 8. |
339 | /// |
340 | /// The return value is undefined if the input is larger than the largest power |
341 | /// of two representable in T. |
342 | template <typename T> [[nodiscard]] T bit_ceil(T Value) { |
343 | static_assert(std::is_unsigned_v<T>, |
344 | "Only unsigned integral types are allowed." ); |
345 | if (Value < 2) |
346 | return 1; |
347 | return T(1) << llvm::bit_width<T>(Value - 1u); |
348 | } |
349 | |
350 | namespace detail { |
351 | template <typename T, std::size_t SizeOfT> struct PopulationCounter { |
352 | static int count(T Value) { |
353 | // Generic version, forward to 32 bits. |
354 | static_assert(SizeOfT <= 4, "Not implemented!" ); |
355 | #if defined(__GNUC__) |
356 | return (int)__builtin_popcount(Value); |
357 | #else |
358 | uint32_t v = Value; |
359 | v = v - ((v >> 1) & 0x55555555); |
360 | v = (v & 0x33333333) + ((v >> 2) & 0x33333333); |
361 | return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24); |
362 | #endif |
363 | } |
364 | }; |
365 | |
366 | template <typename T> struct PopulationCounter<T, 8> { |
367 | static int count(T Value) { |
368 | #if defined(__GNUC__) |
369 | return (int)__builtin_popcountll(Value); |
370 | #else |
371 | uint64_t v = Value; |
372 | v = v - ((v >> 1) & 0x5555555555555555ULL); |
373 | v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); |
374 | v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; |
375 | return int((uint64_t)(v * 0x0101010101010101ULL) >> 56); |
376 | #endif |
377 | } |
378 | }; |
379 | } // namespace detail |
380 | |
381 | /// Count the number of set bits in a value. |
382 | /// Ex. popcount(0xF000F000) = 8 |
383 | /// Returns 0 if the word is zero. |
384 | template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> |
385 | [[nodiscard]] inline int popcount(T Value) noexcept { |
386 | return detail::PopulationCounter<T, sizeof(T)>::count(Value); |
387 | } |
388 | |
389 | // Forward-declare rotr so that rotl can use it. |
390 | template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> |
391 | [[nodiscard]] constexpr T rotr(T V, int R); |
392 | |
393 | template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>> |
394 | [[nodiscard]] constexpr T rotl(T V, int R) { |
395 | unsigned N = std::numeric_limits<T>::digits; |
396 | |
397 | R = R % N; |
398 | if (!R) |
399 | return V; |
400 | |
401 | if (R < 0) |
402 | return llvm::rotr(V, -R); |
403 | |
404 | return (V << R) | (V >> (N - R)); |
405 | } |
406 | |
407 | template <typename T, typename> [[nodiscard]] constexpr T rotr(T V, int R) { |
408 | unsigned N = std::numeric_limits<T>::digits; |
409 | |
410 | R = R % N; |
411 | if (!R) |
412 | return V; |
413 | |
414 | if (R < 0) |
415 | return llvm::rotl(V, -R); |
416 | |
417 | return (V >> R) | (V << (N - R)); |
418 | } |
419 | |
420 | } // namespace llvm |
421 | |
422 | #endif |
423 | |