contrib/llvm-project/libcxx/include/bit

   1 // -*- C++ -*-
   2 //===------------------------------ bit ----------------------------------===//
   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
  18   template <class T>
  19     constexpr bool ispow2(T x) noexcept; // C++20
  20   template <class T>
  21     constexpr T ceil2(T x);              // C++20
  22   template <class T>
  23     constexpr T floor2(T x) noexcept;    // C++20
  24   template <class T>
  25     constexpr T log2p1(T x) noexcept;    // C++20
  26
  27   // 23.20.2, rotating
  28   template<class T>
  29     constexpr T rotl(T x, unsigned int s) noexcept; // C++20
  30   template<class T>
  31     constexpr T rotr(T x, unsigned int s) noexcept; // C++20
  32
  33   // 23.20.3, counting
  34   template<class T>
  35     constexpr int countl_zero(T x) noexcept;  // C++20
  36   template<class T>
  37     constexpr int countl_one(T x) noexcept;   // C++20
  38   template<class T>
  39     constexpr int countr_zero(T x) noexcept;  // C++20
  40   template<class T>
  41     constexpr int countr_one(T x) noexcept;   // C++20
  42   template<class T>
  43     constexpr int popcount(T x) noexcept;     // C++20
  44
  45   // 20.15.9, endian
  46   enum class endian {
  47     little = see below,        // C++20
  48     big = see below,           // C++20
  49     native = see below         // C++20
  50 };
  51
  52 } // namespace std
  53
  54 */
  55
  56 #include <__config>
  57 #include <limits>
  58 #include <type_traits>
  59 #include <version>
  60 #include <__debug>
  61
  62 #if defined(__IBMCPP__)
  63 #include "support/ibm/support.h"
  64 #endif
  65 #if defined(_LIBCPP_COMPILER_MSVC)
  66 #include <intrin.h>
  67 #endif
  68
  69 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  70 #pragma GCC system_header
  71 #endif
  72
  73 _LIBCPP_PUSH_MACROS
  74 #include <__undef_macros>
  75
  76 _LIBCPP_BEGIN_NAMESPACE_STD
  77
  78 #ifndef _LIBCPP_COMPILER_MSVC
  79
  80 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
  81 int __libcpp_ctz(unsigned __x)           _NOEXCEPT { return __builtin_ctz(__x); }
  82
  83 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
  84 int __libcpp_ctz(unsigned long __x)      _NOEXCEPT { return __builtin_ctzl(__x); }
  85
  86 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
  87 int __libcpp_ctz(unsigned long long __x) _NOEXCEPT { return __builtin_ctzll(__x); }
  88
  89
  90 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
  91 int __libcpp_clz(unsigned __x)           _NOEXCEPT { return __builtin_clz(__x); }
  92
  93 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
  94 int __libcpp_clz(unsigned long __x)      _NOEXCEPT { return __builtin_clzl(__x); }
  95
  96 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
  97 int __libcpp_clz(unsigned long long __x) _NOEXCEPT { return __builtin_clzll(__x); }
  98
  99
 100 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 101 int __libcpp_popcount(unsigned __x)           _NOEXCEPT { return __builtin_popcount(__x); }
 102
 103 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 104 int __libcpp_popcount(unsigned long __x)      _NOEXCEPT { return __builtin_popcountl(__x); }
 105
 106 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 107 int __libcpp_popcount(unsigned long long __x) _NOEXCEPT { return __builtin_popcountll(__x); }
 108
 109 #else  // _LIBCPP_COMPILER_MSVC
 110
 111 // Precondition:  __x != 0
 112 inline _LIBCPP_INLINE_VISIBILITY
 113 int __libcpp_ctz(unsigned __x) {
 114   static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
 115   static_assert(sizeof(unsigned long) == 4, "");
 116   unsigned long __where;
 117   if (_BitScanForward(&__where, __x))
 118     return static_cast<int>(__where);
 119   return 32;
 120 }
 121
 122 inline _LIBCPP_INLINE_VISIBILITY
 123 int __libcpp_ctz(unsigned long __x) {
 124     static_assert(sizeof(unsigned long) == sizeof(unsigned), "");
 125     return __ctz(static_cast<unsigned>(__x));
 126 }
 127
 128 inline _LIBCPP_INLINE_VISIBILITY
 129 int __libcpp_ctz(unsigned long long __x) {
 130     unsigned long __where;
 131 #if defined(_LIBCPP_HAS_BITSCAN64)
 132     (defined(_M_AMD64) || defined(__x86_64__))
 133   if (_BitScanForward64(&__where, __x))
 134     return static_cast<int>(__where);
 135 #else
 136   // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls.
 137   if (_BitScanForward(&__where, static_cast<unsigned long>(__x)))
 138     return static_cast<int>(__where);
 139   if (_BitScanForward(&__where, static_cast<unsigned long>(__x >> 32)))
 140     return static_cast<int>(__where + 32);
 141 #endif
 142   return 64;
 143 }
 144
 145 // Precondition:  __x != 0
 146 inline _LIBCPP_INLINE_VISIBILITY
 147 int __libcpp_clz(unsigned __x) {
 148   static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
 149   static_assert(sizeof(unsigned long) == 4, "");
 150   unsigned long __where;
 151   if (_BitScanReverse(&__where, __x))
 152     return static_cast<int>(31 - __where);
 153   return 32; // Undefined Behavior.
 154 }
 155
 156 inline _LIBCPP_INLINE_VISIBILITY
 157 int __libcpp_clz(unsigned long __x) {
 158     static_assert(sizeof(unsigned) == sizeof(unsigned long), "");
 159     return __libcpp_clz(static_cast<unsigned>(__x));
 160 }
 161
 162 inline _LIBCPP_INLINE_VISIBILITY
 163 int __libcpp_clz(unsigned long long __x) {
 164   unsigned long __where;
 165 #if defined(_LIBCPP_HAS_BITSCAN64)
 166   if (_BitScanReverse64(&__where, __x))
 167     return static_cast<int>(63 - __where);
 168 #else
 169   // Win32 doesn't have _BitScanReverse64 so emulate it with two 32 bit calls.
 170   if (_BitScanReverse(&__where, static_cast<unsigned long>(__x >> 32)))
 171     return static_cast<int>(63 - (__where + 32));
 172   if (_BitScanReverse(&__where, static_cast<unsigned long>(__x)))
 173     return static_cast<int>(63 - __where);
 174 #endif
 175   return 64; // Undefined Behavior.
 176 }
 177
 178 inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned __x) {
 179   static_assert(sizeof(unsigned) == 4, "");
 180   return __popcnt(__x);
 181 }
 182
 183 inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long __x) {
 184   static_assert(sizeof(unsigned long) == 4, "");
 185   return __popcnt(__x);
 186 }
 187
 188 inline _LIBCPP_INLINE_VISIBILITY int __libcpp_popcount(unsigned long long __x) {
 189   static_assert(sizeof(unsigned long long) == 8, "");
 190   return __popcnt64(__x);
 191 }
 192
 193 #endif // _LIBCPP_COMPILER_MSVC
 194
 195 template <class _Tp>
 196 using __bitop_unsigned_integer _LIBCPP_NODEBUG_TYPE = integral_constant<bool,
 197          is_integral<_Tp>::value &&
 198          is_unsigned<_Tp>::value &&
 199         _IsNotSame<typename remove_cv<_Tp>::type, bool>::value &&
 200         _IsNotSame<typename remove_cv<_Tp>::type, signed char>::value &&
 201         _IsNotSame<typename remove_cv<_Tp>::type, wchar_t>::value &&
 202         _IsNotSame<typename remove_cv<_Tp>::type, char16_t>::value &&
 203         _IsNotSame<typename remove_cv<_Tp>::type, char32_t>::value
 204     >;
 205
 206
 207 template<class _Tp>
 208 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 209 _Tp __rotl(_Tp __t, unsigned int __cnt) _NOEXCEPT
 210 {
 211     static_assert(__bitop_unsigned_integer<_Tp>::value, "__rotl requires unsigned");
 212     const unsigned int __dig = numeric_limits<_Tp>::digits;
 213     if ((__cnt % __dig) == 0)
 214         return __t;
 215     return (__t << (__cnt % __dig)) | (__t >> (__dig - (__cnt % __dig)));
 216 }
 217
 218
 219 template<class _Tp>
 220 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 221 _Tp __rotr(_Tp __t, unsigned int __cnt) _NOEXCEPT
 222 {
 223     static_assert(__bitop_unsigned_integer<_Tp>::value, "__rotr requires unsigned");
 224     const unsigned int __dig = numeric_limits<_Tp>::digits;
 225     if ((__cnt % __dig) == 0)
 226         return __t;
 227     return (__t >> (__cnt % __dig)) | (__t << (__dig - (__cnt % __dig)));
 228 }
 229
 230
 231
 232 template<class _Tp>
 233 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 234 int __countr_zero(_Tp __t) _NOEXCEPT
 235 {
 236     static_assert(__bitop_unsigned_integer<_Tp>::value, "__countr_zero requires unsigned");
 237     if (__t == 0)
 238         return numeric_limits<_Tp>::digits;
 239
 240     if      (sizeof(_Tp) <= sizeof(unsigned int))
 241         return __libcpp_ctz(static_cast<unsigned int>(__t));
 242     else if (sizeof(_Tp) <= sizeof(unsigned long))
 243         return __libcpp_ctz(static_cast<unsigned long>(__t));
 244     else if (sizeof(_Tp) <= sizeof(unsigned long long))
 245         return __libcpp_ctz(static_cast<unsigned long long>(__t));
 246     else
 247     {
 248         int __ret = 0;
 249         int __iter = 0;
 250         const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
 251         while ((__iter = __libcpp_ctz(static_cast<unsigned long long>(__t))) == __ulldigits)
 252         {
 253             __ret += __iter;
 254             __t >>= __ulldigits;
 255         }
 256         return __ret + __iter;
 257     }
 258 }
 259
 260 template<class _Tp>
 261 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 262 int __countl_zero(_Tp __t) _NOEXCEPT
 263 {
 264     static_assert(__bitop_unsigned_integer<_Tp>::value, "__countl_zero requires unsigned");
 265     if (__t == 0)
 266         return numeric_limits<_Tp>::digits;
 267
 268     if      (sizeof(_Tp) <= sizeof(unsigned int))
 269         return __libcpp_clz(static_cast<unsigned int>(__t))
 270               - (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits);
 271     else if (sizeof(_Tp) <= sizeof(unsigned long))
 272         return __libcpp_clz(static_cast<unsigned long>(__t))
 273               - (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits);
 274     else if (sizeof(_Tp) <= sizeof(unsigned long long))
 275         return __libcpp_clz(static_cast<unsigned long long>(__t))
 276               - (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits);
 277     else
 278     {
 279         int __ret = 0;
 280         int __iter = 0;
 281         const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
 282         while (true) {
 283             __t = __rotr(__t, __ulldigits);
 284             if ((__iter = __countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits)
 285                 break;
 286             __ret += __iter;
 287             }
 288         return __ret + __iter;
 289     }
 290 }
 291
 292 template<class _Tp>
 293 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 294 int __countl_one(_Tp __t) _NOEXCEPT
 295 {
 296     static_assert(__bitop_unsigned_integer<_Tp>::value, "__countl_one requires unsigned");
 297     return __t != numeric_limits<_Tp>::max()
 298         ? __countl_zero(static_cast<_Tp>(~__t))
 299         : numeric_limits<_Tp>::digits;
 300 }
 301
 302
 303 template<class _Tp>
 304 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 305 int __countr_one(_Tp __t) _NOEXCEPT
 306 {
 307     static_assert(__bitop_unsigned_integer<_Tp>::value, "__countr_one requires unsigned");
 308     return __t != numeric_limits<_Tp>::max()
 309         ? __countr_zero(static_cast<_Tp>(~__t))
 310         : numeric_limits<_Tp>::digits;
 311 }
 312
 313
 314 template<class _Tp>
 315 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 316 int
 317 __popcount(_Tp __t) _NOEXCEPT
 318 {
 319     static_assert(__bitop_unsigned_integer<_Tp>::value, "__libcpp_popcount requires unsigned");
 320     if      (sizeof(_Tp) <= sizeof(unsigned int))
 321         return __libcpp_popcount(static_cast<unsigned int>(__t));
 322     else if (sizeof(_Tp) <= sizeof(unsigned long))
 323         return __libcpp_popcount(static_cast<unsigned long>(__t));
 324     else if (sizeof(_Tp) <= sizeof(unsigned long long))
 325         return __libcpp_popcount(static_cast<unsigned long long>(__t));
 326     else
 327     {
 328         int __ret = 0;
 329         while (__t != 0)
 330         {
 331             __ret += __libcpp_popcount(static_cast<unsigned long long>(__t));
 332             __t >>= numeric_limits<unsigned long long>::digits;
 333         }
 334         return __ret;
 335     }
 336 }
 337
 338
 339 // integral log base 2
 340 template<class _Tp>
 341 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 342 unsigned __bit_log2(_Tp __t) _NOEXCEPT
 343 {
 344     static_assert(__bitop_unsigned_integer<_Tp>::value, "__bit_log2 requires unsigned");
 345     return std::numeric_limits<_Tp>::digits - 1 - __countl_zero(__t);
 346 }
 347
 348 template <class _Tp>
 349 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 350 bool __ispow2(_Tp __t) _NOEXCEPT
 351 {
 352     static_assert(__bitop_unsigned_integer<_Tp>::value, "__ispow2 requires unsigned");
 353         return __t != 0 && (((__t & (__t - 1)) == 0));
 354 }
 355
 356
 357 #if _LIBCPP_STD_VER > 17
 358
 359 template<class _Tp>
 360 _LIBCPP_INLINE_VISIBILITY constexpr
 361 enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
 362 rotl(_Tp __t, unsigned int __cnt) noexcept
 363 {
 364     return __rotl(__t, __cnt);
 365 }
 366
 367
 368 // rotr
 369 template<class _Tp>
 370 _LIBCPP_INLINE_VISIBILITY constexpr
 371 enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
 372 rotr(_Tp __t, unsigned int __cnt) noexcept
 373 {
 374     return __rotr(__t, __cnt);
 375 }
 376
 377
 378 template<class _Tp>
 379 _LIBCPP_INLINE_VISIBILITY constexpr
 380 enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
 381 countl_zero(_Tp __t) noexcept
 382 {
 383     return __countl_zero(__t);
 384 }
 385
 386
 387 template<class _Tp>
 388 _LIBCPP_INLINE_VISIBILITY constexpr
 389 enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
 390 countl_one(_Tp __t) noexcept
 391 {
 392     return __countl_one(__t);
 393 }
 394
 395
 396 template<class _Tp>
 397 _LIBCPP_INLINE_VISIBILITY constexpr
 398 enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
 399 countr_zero(_Tp __t) noexcept
 400 {
 401         return __countr_zero(__t);
 402 }
 403
 404
 405 template<class _Tp>
 406 _LIBCPP_INLINE_VISIBILITY constexpr
 407 enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
 408 countr_one(_Tp __t) noexcept
 409 {
 410     return __countr_one(__t);
 411 }
 412
 413
 414 template<class _Tp>
 415 _LIBCPP_INLINE_VISIBILITY constexpr
 416 enable_if_t<__bitop_unsigned_integer<_Tp>::value, int>
 417 popcount(_Tp __t) noexcept
 418 {
 419     return __popcount(__t);
 420 }
 421
 422
 423 template <class _Tp>
 424 _LIBCPP_INLINE_VISIBILITY constexpr
 425 enable_if_t<__bitop_unsigned_integer<_Tp>::value, bool>
 426 ispow2(_Tp __t) noexcept
 427 {
 428     return __ispow2(__t);
 429 }
 430
 431 template <class _Tp>
 432 _LIBCPP_INLINE_VISIBILITY constexpr
 433 enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
 434 floor2(_Tp __t) noexcept
 435 {
 436     return __t == 0 ? 0 : _Tp{1} << __bit_log2(__t);
 437 }
 438
 439 template <class _Tp>
 440 _LIBCPP_INLINE_VISIBILITY constexpr
 441 enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
 442 ceil2(_Tp __t) noexcept
 443 {
 444     if (__t < 2) return 1;
 445     const unsigned __n = numeric_limits<_Tp>::digits - countl_zero((_Tp)(__t - 1u));
 446     _LIBCPP_DEBUG_ASSERT(__libcpp_is_constant_evaluated() || __n != numeric_limits<_Tp>::digits, "Bad input to ceil2");
 447
 448     if constexpr (sizeof(_Tp) >= sizeof(unsigned))
 449         return _Tp{1} << __n;
 450     else
 451     {
 452         const unsigned __extra = numeric_limits<unsigned>::digits  - numeric_limits<_Tp>::digits;
 453         const unsigned __retVal = 1u << (__n + __extra);
 454         return (_Tp) (__retVal >> __extra);
 455     }
 456 }
 457
 458 template <class _Tp>
 459 _LIBCPP_INLINE_VISIBILITY constexpr
 460 enable_if_t<__bitop_unsigned_integer<_Tp>::value, _Tp>
 461 log2p1(_Tp __t) noexcept
 462 {
 463     return __t == 0 ? 0 : __bit_log2(__t) + 1;
 464 }
 465
 466
 467 enum class endian
 468 {
 469     little = 0xDEAD,
 470     big    = 0xFACE,
 471 #if defined(_LIBCPP_LITTLE_ENDIAN)
 472     native = little
 473 #elif defined(_LIBCPP_BIG_ENDIAN)
 474     native = big
 475 #else
 476     native = 0xCAFE
 477 #endif
 478 };
 479
 480 #endif // _LIBCPP_STD_VER > 17
 481
 482 _LIBCPP_END_NAMESPACE_STD
 483
 484 _LIBCPP_POP_MACROS
 485
 486 #endif // _LIBCPP_BIT