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 T 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 <__bit/bit_cast.h>
  65 #include <__bit/byteswap.h>
  66 #include <__bits> // __libcpp_clz
  67 #include <__config>
  68 #include <__debug>
  69 #include <limits>
  70 #include <type_traits>
  71 #include <version>
  72
  73 #if defined(__IBMCPP__)
  74 #include "__support/ibm/support.h"
  75 #endif
  76 #if defined(_LIBCPP_COMPILER_MSVC)
  77 #include <intrin.h>
  78 #endif
  79
  80 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  81 #pragma GCC system_header
  82 #endif
  83
  84 _LIBCPP_PUSH_MACROS
  85 #include <__undef_macros>
  86
  87 _LIBCPP_BEGIN_NAMESPACE_STD
  88
  89 template<class _Tp>
  90 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
  91 _Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT
  92 {
  93     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotl requires an unsigned integer type");
  94     const unsigned int __dig = numeric_limits<_Tp>::digits;
  95     if ((__cnt % __dig) == 0)
  96         return __t;
  97     return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig)));
  98 }
  99
 100 template<class _Tp>
 101 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 102 _Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT
 103 {
 104     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__rotr requires an unsigned integer type");
 105     const unsigned int __dig = numeric_limits<_Tp>::digits;
 106     if ((__cnt % __dig) == 0)
 107         return __t;
 108     return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig)));
 109 }
 110
 111 template<class _Tp>
 112 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 113 int __countr_zero(_Tp __t) _NOEXCEPT
 114 {
 115     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_zero requires an unsigned integer type");
 116     if (__t == 0)
 117         return numeric_limits<_Tp>::digits;
 118
 119     if      (sizeof(_Tp) <= sizeof(unsigned int))
 120         return __libcpp_ctz(static_cast<unsigned int>(__t));
 121     else if (sizeof(_Tp) <= sizeof(unsigned long))
 122         return __libcpp_ctz(static_cast<unsigned long>(__t));
 123     else if (sizeof(_Tp) <= sizeof(unsigned long long))
 124         return __libcpp_ctz(static_cast<unsigned long long>(__t));
 125     else
 126     {
 127         int __ret = 0;
 128         const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
 129         while (static_cast<unsigned long long>(__t) == 0uLL)
 130         {
 131             __ret += __ulldigits;
 132             __t >>= __ulldigits;
 133         }
 134         return __ret + __libcpp_ctz(static_cast<unsigned long long>(__t));
 135     }
 136 }
 137
 138 template<class _Tp>
 139 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 140 int __countl_zero(_Tp __t) _NOEXCEPT
 141 {
 142     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_zero requires an unsigned integer type");
 143     if (__t == 0)
 144         return numeric_limits<_Tp>::digits;
 145
 146     if      (sizeof(_Tp) <= sizeof(unsigned int))
 147         return __libcpp_clz(static_cast<unsigned int>(__t))
 148               - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits);
 149     else if (sizeof(_Tp) <= sizeof(unsigned long))
 150         return __libcpp_clz(static_cast<unsigned long>(__t))
 151               - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits);
 152     else if (sizeof(_Tp) <= sizeof(unsigned long long))
 153         return __libcpp_clz(static_cast<unsigned long long>(__t))
 154               - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits);
 155     else
 156     {
 157         int __ret = 0;
 158         int __iter = 0;
 159         const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
 160         while (true) {
 161             __t = __rotr(__t, __ulldigits);
 162             if ((__iter = __countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits)
 163                 break;
 164             __ret += __iter;
 165             }
 166         return __ret + __iter;
 167     }
 168 }
 169
 170 template<class _Tp>
 171 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 172 int __countl_one(_Tp __t) _NOEXCEPT
 173 {
 174     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countl_one requires an unsigned integer type");
 175     return __t != numeric_limits<_Tp>::max()
 176         ? __countl_zero(static_cast<_Tp>(~__t))
 177         : numeric_limits<_Tp>::digits;
 178 }
 179
 180 template<class _Tp>
 181 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 182 int __countr_one(_Tp __t) _NOEXCEPT
 183 {
 184     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__countr_one requires an unsigned integer type");
 185     return __t != numeric_limits<_Tp>::max()
 186         ? __countr_zero(static_cast<_Tp>(~__t))
 187         : numeric_limits<_Tp>::digits;
 188 }
 189
 190 template<class _Tp>
 191 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 192 int __popcount(_Tp __t) _NOEXCEPT
 193 {
 194     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__popcount requires an unsigned integer type");
 195     if      (sizeof(_Tp) <= sizeof(unsigned int))
 196         return __libcpp_popcount(static_cast<unsigned int>(__t));
 197     else if (sizeof(_Tp) <= sizeof(unsigned long))
 198         return __libcpp_popcount(static_cast<unsigned long>(__t));
 199     else if (sizeof(_Tp) <= sizeof(unsigned long long))
 200         return __libcpp_popcount(static_cast<unsigned long long>(__t));
 201     else
 202     {
 203         int __ret = 0;
 204         while (__t != 0)
 205         {
 206             __ret += __libcpp_popcount(static_cast<unsigned long long>(__t));
 207             __t >>= numeric_limits<unsigned long long>::digits;
 208         }
 209         return __ret;
 210     }
 211 }
 212
 213 // integral log base 2
 214 template<class _Tp>
 215 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 216 unsigned __bit_log2(_Tp __t) _NOEXCEPT
 217 {
 218     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__bit_log2 requires an unsigned integer type");
 219     return numeric_limits<_Tp>::digits - 1 - __countl_zero(__t);
 220 }
 221
 222 template <class _Tp>
 223 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 224 bool __has_single_bit(_Tp __t) _NOEXCEPT
 225 {
 226     static_assert(__libcpp_is_unsigned_integer<_Tp>::value, "__has_single_bit requires an unsigned integer type");
 227     return __t != 0 && (((__t & (__t - 1)) == 0));
 228 }
 229
 230 #if _LIBCPP_STD_VER > 17
 231
 232 template<class _Tp>
 233 _LIBCPP_INLINE_VISIBILITY constexpr
 234 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
 235 rotl(_Tp __t, unsigned int __cnt) noexcept
 236 {
 237     return __rotl(__t, __cnt);
 238 }
 239
 240 template<class _Tp>
 241 _LIBCPP_INLINE_VISIBILITY constexpr
 242 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
 243 rotr(_Tp __t, unsigned int __cnt) noexcept
 244 {
 245     return __rotr(__t, __cnt);
 246 }
 247
 248 template<class _Tp>
 249 _LIBCPP_INLINE_VISIBILITY constexpr
 250 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, int>
 251 countl_zero(_Tp __t) noexcept
 252 {
 253     return __countl_zero(__t);
 254 }
 255
 256 template<class _Tp>
 257 _LIBCPP_INLINE_VISIBILITY constexpr
 258 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, int>
 259 countl_one(_Tp __t) noexcept
 260 {
 261     return __countl_one(__t);
 262 }
 263
 264 template<class _Tp>
 265 _LIBCPP_INLINE_VISIBILITY constexpr
 266 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, int>
 267 countr_zero(_Tp __t) noexcept
 268 {
 269     return __countr_zero(__t);
 270 }
 271
 272 template<class _Tp>
 273 _LIBCPP_INLINE_VISIBILITY constexpr
 274 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, int>
 275 countr_one(_Tp __t) noexcept
 276 {
 277     return __countr_one(__t);
 278 }
 279
 280 template<class _Tp>
 281 _LIBCPP_INLINE_VISIBILITY constexpr
 282 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, int>
 283 popcount(_Tp __t) noexcept
 284 {
 285     return __popcount(__t);
 286 }
 287
 288 template <class _Tp>
 289 _LIBCPP_INLINE_VISIBILITY constexpr
 290 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, bool>
 291 has_single_bit(_Tp __t) noexcept
 292 {
 293     return __has_single_bit(__t);
 294 }
 295
 296 template <class _Tp>
 297 _LIBCPP_INLINE_VISIBILITY constexpr
 298 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
 299 bit_floor(_Tp __t) noexcept
 300 {
 301     return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t);
 302 }
 303
 304 template <class _Tp>
 305 _LIBCPP_INLINE_VISIBILITY constexpr
 306 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
 307 bit_ceil(_Tp __t) noexcept
 308 {
 309     if (__t < 2) return 1;
 310     const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u));
 311     _LIBCPP_ASSERT(__n != numeric_limits<_Tp>::digits, "Bad input to bit_ceil");
 312
 313     if constexpr (sizeof(_Tp) >= sizeof(unsigned))
 314         return _Tp{1} << __n;
 315     else
 316     {
 317         const unsigned __extra = numeric_limits<unsigned>::digits  - numeric_limits<_Tp>::digits;
 318         const unsigned __retVal = 1u << (__n + __extra);
 319         return (_Tp) (__retVal >> __extra);
 320     }
 321 }
 322
 323 template <class _Tp>
 324 _LIBCPP_INLINE_VISIBILITY constexpr
 325 enable_if_t<__libcpp_is_unsigned_integer<_Tp>::value, _Tp>
 326 bit_width(_Tp __t) noexcept
 327 {
 328     return __t == 0 ? 0 : __bit_log2(__t) + 1;
 329 }
 330
 331 enum class endian
 332 {
 333     little = 0xDEAD,
 334     big    = 0xFACE,
 335 #if defined(_LIBCPP_LITTLE_ENDIAN)
 336     native = little
 337 #elif defined(_LIBCPP_BIG_ENDIAN)
 338     native = big
 339 #else
 340     native = 0xCAFE
 341 #endif
 342 };
 343
 344 #endif // _LIBCPP_STD_VER > 17
 345
 346 _LIBCPP_END_NAMESPACE_STD
 347
 348 _LIBCPP_POP_MACROS
 349
 350 #endif // _LIBCPP_BIT