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>
60extern "C" {
61unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
62unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
63unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
64unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
65}
66#endif
67
68namespace llvm {
69
70enum 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.
83template <
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.
100template <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
145template <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
150namespace detail {
151template <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)
175template <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)
191template <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.
215template <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
221namespace detail {
222template <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)
241template <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)
257template <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.
281template <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.
294template <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.
307template <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.
317template <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.
327template <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.
342template <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
350namespace detail {
351template <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
366template <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.
384template <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.
390template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
391[[nodiscard]] constexpr T rotr(T V, int R);
392
393template <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
407template <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