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>>
bit_cast(const From & from)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>>>
byteswap(T V)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>>>
has_single_bit(T Value)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 {
countTrailingZerosCounter152   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