libstdc++-v3/include/std/bit

   1 // <bit> -*- C++ -*-
   2
   3 // Copyright (C) 2018-2025 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file include/bit
  26  *  This is a Standard C++ Library header.
  27  */
  28
  29 #ifndef _GLIBCXX_BIT
  30 #define _GLIBCXX_BIT 1
  31
  32 #ifdef _GLIBCXX_SYSHDR
  33 #pragma GCC system_header
  34 #endif
  35
  36 #if __cplusplus >= 201402L
  37
  38 #include <concepts> // for std::integral
  39 #include <type_traits>
  40
  41 #if _GLIBCXX_HOSTED || __has_include(<ext/numeric_traits.h>)
  42 # include <ext/numeric_traits.h>
  43 #else
  44 # include <limits>
  45 /// @cond undocumented
  46 namespace __gnu_cxx
  47 {
  48   template<typename _Tp>
  49     struct __int_traits
  50     {
  51       static constexpr int __digits = std::numeric_limits<_Tp>::digits;
  52       static constexpr _Tp __max = std::numeric_limits<_Tp>::max();
  53     };
  54 }
  55 /// @endcond
  56 #endif
  57
  58 #define __glibcxx_want_bit_cast
  59 #define __glibcxx_want_byteswap
  60 #define __glibcxx_want_bitops
  61 #define __glibcxx_want_int_pow2
  62 #define __glibcxx_want_endian
  63 #include <bits/version.h>
  64
  65 namespace std _GLIBCXX_VISIBILITY(default)
  66 {
  67 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  68
  69   /**
  70    * @defgroup bit_manip Bit manipulation
  71    * @ingroup numerics
  72    *
  73    * Utilities for examining and manipulating individual bits.
  74    *
  75    * @{
  76    */
  77
  78 #ifdef __cpp_lib_bit_cast // C++ >= 20
  79
  80   /// Create a value of type `To` from the bits of `from`.
  81   /**
  82    * @tparam _To   A trivially-copyable type.
  83    * @param __from A trivially-copyable object of the same size as `_To`.
  84    * @return       An object of type `_To`.
  85    * @since C++20
  86    */
  87   template<typename _To, typename _From>
  88     [[nodiscard]]
  89     constexpr _To
  90     bit_cast(const _From& __from) noexcept
  91 #ifdef __cpp_concepts
  92     requires (sizeof(_To) == sizeof(_From))
  93       && is_trivially_copyable_v<_To> && is_trivially_copyable_v<_From>
  94 #endif
  95     {
  96       return __builtin_bit_cast(_To, __from);
  97     }
  98 #endif // __cpp_lib_bit_cast
  99
 100 #ifdef __cpp_lib_byteswap // C++ >= 23
 101
 102   /// Reverse order of bytes in the object representation of `value`.
 103   /**
 104    * @tparam _Tp     An integral type.
 105    * @param __value  An object of integer type.
 106    * @return         An object of the same type, with the bytes reversed.
 107    * @since C++23
 108    */
 109   template<integral _Tp>
 110     [[nodiscard]]
 111     constexpr _Tp
 112     byteswap(_Tp __value) noexcept
 113     {
 114       if constexpr (sizeof(_Tp) == 1)
 115         return __value;
 116 #if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8
 117       if !consteval
 118         {
 119           if constexpr (sizeof(_Tp) == 2)
 120             return __builtin_bswap16(__value);
 121           if constexpr (sizeof(_Tp) == 4)
 122             return __builtin_bswap32(__value);
 123           if constexpr (sizeof(_Tp) == 8)
 124             return __builtin_bswap64(__value);
 125           if constexpr (sizeof(_Tp) == 16)
 126 #if __has_builtin(__builtin_bswap128)
 127             return __builtin_bswap128(__value);
 128 #else
 129             return (__builtin_bswap64(__value >> 64)
 130                     | (static_cast<_Tp>(__builtin_bswap64(__value)) << 64));
 131 #endif
 132         }
 133 #endif
 134
 135       // Fallback implementation that handles even __int24 etc.
 136       using _Up = typename __make_unsigned<__remove_cv_t<_Tp>>::__type;
 137       size_t __diff = __CHAR_BIT__ * (sizeof(_Tp) - 1);
 138       _Up __mask1 = static_cast<unsigned char>(~0);
 139       _Up __mask2 = __mask1 << __diff;
 140       _Up __val = __value;
 141       for (size_t __i = 0; __i < sizeof(_Tp) / 2; ++__i)
 142         {
 143           _Up __byte1 = __val & __mask1;
 144           _Up __byte2 = __val & __mask2;
 145           __val = (__val ^ __byte1 ^ __byte2
 146                    ^ (__byte1 << __diff) ^ (__byte2 >> __diff));
 147           __mask1 <<= __CHAR_BIT__;
 148           __mask2 >>= __CHAR_BIT__;
 149           __diff -= 2 * __CHAR_BIT__;
 150         }
 151       return __val;
 152     }
 153 #endif // __cpp_lib_byteswap
 154
 155   /// @cond undocumented
 156 #pragma GCC diagnostic push
 157 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
 158
 159   template<typename _Tp>
 160     constexpr _Tp
 161     __rotl(_Tp __x, int __s) noexcept
 162     {
 163       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 164       if constexpr ((_Nd & (_Nd - 1)) == 0)
 165         {
 166           // Variant for power of two _Nd which the compiler can
 167           // easily pattern match.
 168           constexpr unsigned __uNd = _Nd;
 169           const auto __r = static_cast<unsigned>(__s);
 170           return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
 171         }
 172       const int __r = __s % _Nd;
 173       if (__r == 0)
 174         return __x;
 175       else if (__r > 0)
 176         return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
 177       else
 178         return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
 179     }
 180
 181   template<typename _Tp>
 182     constexpr _Tp
 183     __rotr(_Tp __x, int __s) noexcept
 184     {
 185       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 186       if constexpr ((_Nd & (_Nd - 1)) == 0)
 187         {
 188           // Variant for power of two _Nd which the compiler can
 189           // easily pattern match.
 190           constexpr unsigned __uNd = _Nd;
 191           const auto __r = static_cast<unsigned>(__s);
 192           return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
 193         }
 194       const int __r = __s % _Nd;
 195       if (__r == 0)
 196         return __x;
 197       else if (__r > 0)
 198         return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
 199       else
 200         return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
 201     }
 202
 203   template<typename _Tp>
 204     constexpr int
 205     __countl_zero(_Tp __x) noexcept
 206     {
 207       using __gnu_cxx::__int_traits;
 208       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 209
 210 #if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clzg)
 211       return __builtin_clzg(__x, _Nd);
 212 #else
 213       if (__x == 0)
 214         return _Nd;
 215
 216       constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
 217       constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
 218       constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
 219
 220       if constexpr (_Nd <= _Nd_u)
 221         {
 222           constexpr int __diff = _Nd_u - _Nd;
 223           return __builtin_clz(__x) - __diff;
 224         }
 225       else if constexpr (_Nd <= _Nd_ul)
 226         {
 227           constexpr int __diff = _Nd_ul - _Nd;
 228           return __builtin_clzl(__x) - __diff;
 229         }
 230       else if constexpr (_Nd <= _Nd_ull)
 231         {
 232           constexpr int __diff = _Nd_ull - _Nd;
 233           return __builtin_clzll(__x) - __diff;
 234         }
 235       else // (_Nd > _Nd_ull)
 236         {
 237           static_assert(_Nd <= (2 * _Nd_ull),
 238                         "Maximum supported integer size is 128-bit");
 239
 240           unsigned long long __high = __x >> _Nd_ull;
 241           if (__high != 0)
 242             {
 243               constexpr int __diff = (2 * _Nd_ull) - _Nd;
 244               return __builtin_clzll(__high) - __diff;
 245             }
 246           constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
 247           unsigned long long __low = __x & __max_ull;
 248           return (_Nd - _Nd_ull) + __builtin_clzll(__low);
 249         }
 250 #endif
 251     }
 252
 253   template<typename _Tp>
 254     constexpr int
 255     __countl_one(_Tp __x) noexcept
 256     {
 257       return std::__countl_zero<_Tp>((_Tp)~__x);
 258     }
 259
 260   template<typename _Tp>
 261     constexpr int
 262     __countr_zero(_Tp __x) noexcept
 263     {
 264       using __gnu_cxx::__int_traits;
 265       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 266
 267 #if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg)
 268       return __builtin_ctzg(__x, _Nd);
 269 #else
 270       if (__x == 0)
 271         return _Nd;
 272
 273       constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
 274       constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
 275       constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
 276
 277       if constexpr (_Nd <= _Nd_u)
 278         return __builtin_ctz(__x);
 279       else if constexpr (_Nd <= _Nd_ul)
 280         return __builtin_ctzl(__x);
 281       else if constexpr (_Nd <= _Nd_ull)
 282         return __builtin_ctzll(__x);
 283       else // (_Nd > _Nd_ull)
 284         {
 285           static_assert(_Nd <= (2 * _Nd_ull),
 286                         "Maximum supported integer size is 128-bit");
 287
 288           constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
 289           unsigned long long __low = __x & __max_ull;
 290           if (__low != 0)
 291             return __builtin_ctzll(__low);
 292           unsigned long long __high = __x >> _Nd_ull;
 293           return __builtin_ctzll(__high) + _Nd_ull;
 294         }
 295 #endif
 296     }
 297
 298   template<typename _Tp>
 299     constexpr int
 300     __countr_one(_Tp __x) noexcept
 301     {
 302       return std::__countr_zero((_Tp)~__x);
 303     }
 304
 305   template<typename _Tp>
 306     constexpr int
 307     __popcount(_Tp __x) noexcept
 308     {
 309 #if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
 310       return __builtin_popcountg(__x);
 311 #else
 312       using __gnu_cxx::__int_traits;
 313       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 314
 315       constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
 316       constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
 317       constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
 318
 319       if constexpr (_Nd <= _Nd_u)
 320         return __builtin_popcount(__x);
 321       else if constexpr (_Nd <= _Nd_ul)
 322         return __builtin_popcountl(__x);
 323       else if constexpr (_Nd <= _Nd_ull)
 324         return __builtin_popcountll(__x);
 325       else // (_Nd > _Nd_ull)
 326         {
 327           static_assert(_Nd <= (2 * _Nd_ull),
 328                         "Maximum supported integer size is 128-bit");
 329
 330           constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
 331           unsigned long long __low = __x & __max_ull;
 332           unsigned long long __high = __x >> _Nd_ull;
 333           return __builtin_popcountll(__low) + __builtin_popcountll(__high);
 334         }
 335 #endif
 336     }
 337
 338   template<typename _Tp>
 339     constexpr bool
 340     __has_single_bit(_Tp __x) noexcept
 341     { return std::__popcount(__x) == 1; }
 342
 343   template<typename _Tp>
 344     constexpr _Tp
 345     __bit_ceil(_Tp __x) noexcept
 346     {
 347       using __gnu_cxx::__int_traits;
 348       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 349       if (__x == 0 || __x == 1)
 350         return 1;
 351       auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
 352       // If the shift exponent equals _Nd then the correct result is not
 353       // representable as a value of _Tp, and so the result is undefined.
 354       // Want that undefined behaviour to be detected in constant expressions,
 355       // by UBSan, and by debug assertions.
 356       if (!std::__is_constant_evaluated())
 357         {
 358           __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
 359         }
 360
 361       using __promoted_type = decltype(__x << 1);
 362       if constexpr (!is_same<__promoted_type, _Tp>::value)
 363         {
 364           // If __x undergoes integral promotion then shifting by _Nd is
 365           // not undefined. In order to make the shift undefined, so that
 366           // it is diagnosed in constant expressions and by UBsan, we also
 367           // need to "promote" the shift exponent to be too large for the
 368           // promoted type.
 369           const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
 370           __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
 371         }
 372       return (_Tp)1u << __shift_exponent;
 373     }
 374
 375   template<typename _Tp>
 376     constexpr _Tp
 377     __bit_floor(_Tp __x) noexcept
 378     {
 379       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 380       if (__x == 0)
 381         return 0;
 382       return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
 383     }
 384
 385   template<typename _Tp>
 386     constexpr int
 387     __bit_width(_Tp __x) noexcept
 388     {
 389       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 390       return _Nd - std::__countl_zero(__x);
 391     }
 392
 393 #pragma GCC diagnostic pop
 394   /// @endcond
 395
 396 #ifdef __cpp_lib_bitops // C++ >= 20
 397
 398   /// @cond undocumented
 399   template<typename _Tp>
 400     concept __unsigned_integer = __is_unsigned_integer<_Tp>::value;
 401   /// @endcond
 402
 403   // [bit.rot], rotating
 404
 405   /// Rotate `x` to the left by `s` bits.
 406   template<__unsigned_integer _Tp>
 407     [[nodiscard]] constexpr _Tp
 408     rotl(_Tp __x, int __s) noexcept
 409     { return std::__rotl(__x, __s); }
 410
 411   /// Rotate `x` to the right by `s` bits.
 412   template<__unsigned_integer _Tp>
 413     [[nodiscard]] constexpr _Tp
 414     rotr(_Tp __x, int __s) noexcept
 415     { return std::__rotr(__x, __s); }
 416
 417   // [bit.count], counting
 418
 419   /// The number of contiguous zero bits, starting from the highest bit.
 420   template<__unsigned_integer _Tp>
 421     constexpr int
 422     countl_zero(_Tp __x) noexcept
 423     { return std::__countl_zero(__x); }
 424
 425   /// The number of contiguous one bits, starting from the highest bit.
 426   template<__unsigned_integer _Tp>
 427     constexpr int
 428     countl_one(_Tp __x) noexcept
 429     { return std::__countl_one(__x); }
 430
 431   /// The number of contiguous zero bits, starting from the lowest bit.
 432   template<__unsigned_integer _Tp>
 433     constexpr int
 434     countr_zero(_Tp __x) noexcept
 435     { return std::__countr_zero(__x); }
 436
 437   /// The number of contiguous one bits, starting from the lowest bit.
 438   template<__unsigned_integer _Tp>
 439     constexpr int
 440     countr_one(_Tp __x) noexcept
 441     { return std::__countr_one(__x); }
 442
 443   /// The number of bits set in `x`.
 444   template<__unsigned_integer _Tp>
 445     constexpr int
 446     popcount(_Tp __x) noexcept
 447     { return std::__popcount(__x); }
 448 #endif // __cpp_lib_bitops
 449
 450 #ifdef __cpp_lib_int_pow2 // C++ >= 20
 451   // [bit.pow.two], integral powers of 2
 452
 453   /// True if `x` is a power of two, false otherwise.
 454   template<__unsigned_integer _Tp>
 455     constexpr bool
 456     has_single_bit(_Tp __x) noexcept
 457     { return std::__has_single_bit(__x); }
 458
 459   /// The smallest power-of-two not less than `x`.
 460   template<__unsigned_integer _Tp>
 461     constexpr _Tp
 462     bit_ceil(_Tp __x) noexcept
 463     { return std::__bit_ceil(__x); }
 464
 465   /// The largest power-of-two not greater than `x`.
 466   template<__unsigned_integer _Tp>
 467     constexpr _Tp
 468     bit_floor(_Tp __x) noexcept
 469     { return std::__bit_floor(__x); }
 470
 471   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 472   // 3656. Inconsistent bit operations returning a count
 473   /// The smallest integer greater than the base-2 logarithm of `x`.
 474   template<__unsigned_integer _Tp>
 475     constexpr int
 476     bit_width(_Tp __x) noexcept
 477     { return std::__bit_width(__x); }
 478 #endif // defined (__cpp_lib_int_pow2)
 479
 480 #ifdef __cpp_lib_endian // C++ >= 20
 481
 482   /// Byte order constants
 483   /**
 484    * The platform endianness can be checked by comparing `std::endian::native`
 485    * to one of `std::endian::big` or `std::endian::little`.
 486    *
 487    * @since C++20
 488    */
 489   enum class endian
 490   {
 491     little = __ORDER_LITTLE_ENDIAN__,
 492     big    = __ORDER_BIG_ENDIAN__,
 493     native = __BYTE_ORDER__
 494   };
 495 #endif // __cpp_lib_endian
 496
 497   /// @}
 498
 499 _GLIBCXX_END_NAMESPACE_VERSION
 500 } // namespace std
 501
 502 #endif // C++14
 503 #endif // _GLIBCXX_BIT