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