contrib/llvm-project/libcxx/include/bit

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===---------------------------------------------------------------------===//
   9
  10 #ifndef _LIBCPP_BIT
  11 #define _LIBCPP_BIT
  12
  13 /*
  14     bit synopsis
  15
  16 namespace std {
  17   // [bit.cast], bit_cast
  18   template<class To, class From>
  19     constexpr To bit_cast(const From& from) noexcept; // C++20
  20
  21   // [bit.byteswap], byteswap
  22   template<class T>
  23     constexpr T byteswap(T value) noexcept;      // C++23
  24
  25   // [bit.pow.two], integral powers of 2
  26   template <class T>
  27     constexpr bool has_single_bit(T x) noexcept; // C++20
  28   template <class T>
  29     constexpr T bit_ceil(T x);                   // C++20
  30   template <class T>
  31     constexpr T bit_floor(T x) noexcept;         // C++20
  32   template <class T>
  33     constexpr int bit_width(T x) noexcept;       // C++20
  34
  35   // [bit.rotate], rotating
  36   template<class T>
  37     constexpr T rotl(T x, unsigned int s) noexcept; // C++20
  38   template<class T>
  39     constexpr T rotr(T x, unsigned int s) noexcept; // C++20
  40
  41   // [bit.count], counting
  42   template<class T>
  43     constexpr int countl_zero(T x) noexcept;  // C++20
  44   template<class T>
  45     constexpr int countl_one(T x) noexcept;   // C++20
  46   template<class T>
  47     constexpr int countr_zero(T x) noexcept;  // C++20
  48   template<class T>
  49     constexpr int countr_one(T x) noexcept;   // C++20
  50   template<class T>
  51     constexpr int popcount(T x) noexcept;     // C++20
  52
  53   // [bit.endian], endian
  54   enum class endian {
  55     little = see below,        // C++20
  56     big = see below,           // C++20
  57     native = see below         // C++20
  58   };
  59
  60 } // namespace std
  61
  62 */
  63
  64 #include <__assert> // all public C++ headers provide the assertion handler
  65 #include <__bit/bit_cast.h>
  66 #include <__bit/byteswap.h>
  67 #include <__bits> // __libcpp_clz
  68 #include <__concepts/arithmetic.h>
  69 #include <__config>
  70 #include <limits>
  71 #include <type_traits>
  72 #include <version>
  73
  74 #ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
  75 #  include <iosfwd>
  76 #endif
  77
  78 #if defined(_LIBCPP_COMPILER_MSVC)
  79 #  include <intrin.h>
  80 #endif
  81
  82 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  83 #  pragma GCC system_header
  84 #endif
  85
  86 _LIBCPP_PUSH_MACROS
  87 #include <__undef_macros>
  88
  89 _LIBCPP_BEGIN_NAMESPACE_STD
  90
  91 template<class _Tp>
  92 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
  93 _Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT
  94 {
  95     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type");
  96     const unsigned int __dig = numeric_limits<_Tp>::digits;
  97     if ((__cnt % __dig) == 0)
  98         return __t;
  99     return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig)));
 100 }
 101
 102 template<class _Tp>
 103 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 104 int __countl_zero(_Tp __t) _NOEXCEPT
 105 {
 106     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type");
 107     if (__t == 0)
 108         return numeric_limits<_Tp>::digits;
 109
 110     if      (sizeof(_Tp) <= sizeof(unsigned int))
 111         return std::__libcpp_clz(static_cast<unsigned int>(__t))
 112               - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits);
 113     else if (sizeof(_Tp) <= sizeof(unsigned long))
 114         return std::__libcpp_clz(static_cast<unsigned long>(__t))
 115               - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits);
 116     else if (sizeof(_Tp) <= sizeof(unsigned long long))
 117         return std::__libcpp_clz(static_cast<unsigned long long>(__t))
 118               - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits);
 119     else
 120     {
 121         int __ret = 0;
 122         int __iter = 0;
 123         const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
 124         while (true) {
 125             __t = std::__rotr(__t, __ulldigits);
 126             if ((__iter = std::__countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits)
 127                 break;
 128             __ret += __iter;
 129             }
 130         return __ret + __iter;
 131     }
 132 }
 133
 134 #if _LIBCPP_STD_VER > 17
 135
 136 template <__libcpp_unsigned_integer _Tp>
 137 _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotl(_Tp __t, unsigned int __cnt) noexcept {
 138   const unsigned int __dig = numeric_limits<_Tp>::digits;
 139   if ((__cnt % __dig) == 0)
 140     return __t;
 141   return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig)));
 142 }
 143
 144 template <__libcpp_unsigned_integer _Tp>
 145 _LIBCPP_HIDE_FROM_ABI constexpr _Tp rotr(_Tp __t, unsigned int __cnt) noexcept {
 146   return std::__rotr(__t, __cnt);
 147 }
 148
 149 template <__libcpp_unsigned_integer _Tp>
 150 _LIBCPP_HIDE_FROM_ABI constexpr int countl_zero(_Tp __t) noexcept {
 151   return std::__countl_zero(__t);
 152 }
 153
 154 template <__libcpp_unsigned_integer _Tp>
 155 _LIBCPP_HIDE_FROM_ABI constexpr int countl_one(_Tp __t) noexcept {
 156   return __t != numeric_limits<_Tp>::max() ? std::countl_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits;
 157 }
 158
 159 template <__libcpp_unsigned_integer _Tp>
 160 _LIBCPP_HIDE_FROM_ABI constexpr int countr_zero(_Tp __t) noexcept {
 161   if (__t == 0)
 162     return numeric_limits<_Tp>::digits;
 163
 164   if (sizeof(_Tp) <= sizeof(unsigned int))
 165     return std::__libcpp_ctz(static_cast<unsigned int>(__t));
 166   else if (sizeof(_Tp) <= sizeof(unsigned long))
 167     return std::__libcpp_ctz(static_cast<unsigned long>(__t));
 168   else if (sizeof(_Tp) <= sizeof(unsigned long long))
 169     return std::__libcpp_ctz(static_cast<unsigned long long>(__t));
 170   else {
 171     int __ret = 0;
 172     const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
 173     while (static_cast<unsigned long long>(__t) == 0uLL) {
 174       __ret += __ulldigits;
 175       __t >>= __ulldigits;
 176     }
 177     return __ret + std::__libcpp_ctz(static_cast<unsigned long long>(__t));
 178   }
 179 }
 180
 181 template <__libcpp_unsigned_integer _Tp>
 182 _LIBCPP_HIDE_FROM_ABI constexpr int countr_one(_Tp __t) noexcept {
 183   return __t != numeric_limits<_Tp>::max() ? std::countr_zero(static_cast<_Tp>(~__t)) : numeric_limits<_Tp>::digits;
 184 }
 185
 186 template <__libcpp_unsigned_integer _Tp>
 187 _LIBCPP_HIDE_FROM_ABI constexpr int popcount(_Tp __t) noexcept {
 188   if (sizeof(_Tp) <= sizeof(unsigned int))
 189     return std::__libcpp_popcount(static_cast<unsigned int>(__t));
 190   else if (sizeof(_Tp) <= sizeof(unsigned long))
 191     return std::__libcpp_popcount(static_cast<unsigned long>(__t));
 192   else if (sizeof(_Tp) <= sizeof(unsigned long long))
 193     return std::__libcpp_popcount(static_cast<unsigned long long>(__t));
 194   else {
 195     int __ret = 0;
 196     while (__t != 0) {
 197       __ret += std::__libcpp_popcount(static_cast<unsigned long long>(__t));
 198       __t >>= numeric_limits<unsigned long long>::digits;
 199     }
 200     return __ret;
 201   }
 202 }
 203
 204 template <__libcpp_unsigned_integer _Tp>
 205 _LIBCPP_HIDE_FROM_ABI constexpr bool has_single_bit(_Tp __t) noexcept {
 206   return __t != 0 && (((__t & (__t - 1)) == 0));
 207 }
 208
 209 // integral log base 2
 210 template <__libcpp_unsigned_integer _Tp>
 211 _LIBCPP_HIDE_FROM_ABI constexpr _Tp __bit_log2(_Tp __t) noexcept {
 212   return numeric_limits<_Tp>::digits - 1 - std::countl_zero(__t);
 213 }
 214
 215 template <__libcpp_unsigned_integer _Tp>
 216 _LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_floor(_Tp __t) noexcept {
 217   return __t == 0 ? 0 : _Tp{1} << std::__bit_log2(__t);
 218 }
 219
 220 template <__libcpp_unsigned_integer _Tp>
 221 _LIBCPP_HIDE_FROM_ABI constexpr _Tp bit_ceil(_Tp __t) noexcept {
 222   if (__t < 2)
 223     return 1;
 224   const unsigned __n = numeric_limits<_Tp>::digits - std::countl_zero((_Tp)(__t - 1u));
 225   _LIBCPP_ASSERT(__n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil");
 226
 227   if constexpr (sizeof(_Tp) >= sizeof(unsigned))
 228     return _Tp{1} << __n;
 229   else {
 230     const unsigned __extra = numeric_limits<unsigned>::digits - numeric_limits<_Tp>::digits;
 231     const unsigned __retVal = 1u << (__n + __extra);
 232     return (_Tp)(__retVal >> __extra);
 233   }
 234 }
 235
 236 template <__libcpp_unsigned_integer _Tp>
 237 _LIBCPP_HIDE_FROM_ABI constexpr int bit_width(_Tp __t) noexcept {
 238   return __t == 0 ? 0 : std::__bit_log2(__t) + 1;
 239 }
 240
 241 enum class endian {
 242   little = 0xDEAD,
 243   big = 0xFACE,
 244 #  if defined(_LIBCPP_LITTLE_ENDIAN)
 245   native = little
 246 #  elif defined(_LIBCPP_BIG_ENDIAN)
 247   native = big
 248 #  else
 249   native = 0xCAFE
 250 #  endif
 251 };
 252
 253 #endif // _LIBCPP_STD_VER > 17
 254
 255 _LIBCPP_END_NAMESPACE_STD
 256
 257 _LIBCPP_POP_MACROS
 258
 259 #endif // _LIBCPP_BIT