libstdc++-v3/include/std/bit

   1 // <bit> -*- C++ -*-
   2
   3 // Copyright (C) 2018-2021 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 #pragma GCC system_header
  33
  34 #if __cplusplus >= 201402L
  35
  36 #include <type_traits>
  37
  38 #if _GLIBCXX_HOSTED
  39 # include <ext/numeric_traits.h>
  40 #else
  41 # include <limits>
  42 /// @cond undocumented
  43 namespace __gnu_cxx
  44 {
  45   template<typename _Tp>
  46     struct __int_traits
  47     {
  48       static constexpr int __digits = std::numeric_limits<_Tp>::digits;
  49       static constexpr _Tp __max = std::numeric_limits<_Tp>::max();
  50     };
  51 }
  52 /// @endcond
  53 #endif
  54
  55 namespace std _GLIBCXX_VISIBILITY(default)
  56 {
  57 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  58
  59   /**
  60    * @defgroup bit_manip Bit manipulation
  61    * @ingroup numerics
  62    *
  63    * Utilities for examining and manipulating individual bits.
  64    *
  65    * @{
  66    */
  67
  68 #if __cplusplus > 201703l && __has_builtin(__builtin_bit_cast)
  69 #define __cpp_lib_bit_cast 201806L
  70
  71   /// Create a value of type `To` from the bits of `from`.
  72   template<typename _To, typename _From>
  73     [[nodiscard]]
  74     constexpr _To
  75     bit_cast(const _From& __from) noexcept
  76     {
  77       return __builtin_bit_cast(_To, __from);
  78     }
  79 #endif
  80
  81 #if __cplusplus > 202002L
  82 #define __cpp_lib_byteswap 202110L
  83
  84   /// Reverse order of bytes in the object representation of `value`.
  85   template<typename _Tp>
  86     [[nodiscard]]
  87     constexpr enable_if_t<is_integral<_Tp>::value, _Tp>
  88     byteswap(_Tp __value) noexcept
  89     {
  90       if constexpr (sizeof(_Tp) == 1)
  91         return __value;
  92 #if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8
  93       if !consteval
  94         {
  95           if constexpr (sizeof(_Tp) == 2)
  96             return __builtin_bswap16(__value);
  97           if constexpr (sizeof(_Tp) == 4)
  98             return __builtin_bswap32(__value);
  99           if constexpr (sizeof(_Tp) == 8)
 100             return __builtin_bswap64(__value);
 101           if constexpr (sizeof(_Tp) == 16)
 102 #if __has_builtin(__builtin_bswap128)
 103             return __builtin_bswap128(__value);
 104 #else
 105             return (__builtin_bswap64(__value >> 64)
 106                     | (static_cast<_Tp>(__builtin_bswap64(__value)) << 64));
 107 #endif
 108         }
 109 #endif
 110
 111       // Fallback implementation that handles even __int24 etc.
 112       using _Up = typename __make_unsigned<__remove_cv_t<_Tp>>::__type;
 113       size_t __diff = __CHAR_BIT__ * (sizeof(_Tp) - 1);
 114       _Up __mask1 = static_cast<unsigned char>(~0);
 115       _Up __mask2 = __mask1 << __diff;
 116       _Up __val = __value;
 117       for (size_t __i = 0; __i < sizeof(_Tp) / 2; ++__i)
 118         {
 119           _Up __byte1 = __val & __mask1;
 120           _Up __byte2 = __val & __mask2;
 121           __val = (__val ^ __byte1 ^ __byte2
 122                    ^ (__byte1 << __diff) ^ (__byte2 >> __diff));
 123           __mask1 <<= __CHAR_BIT__;
 124           __mask2 >>= __CHAR_BIT__;
 125           __diff -= 2 * __CHAR_BIT__;
 126         }
 127       return __val;
 128     }
 129 #endif
 130
 131   /// @cond undoc
 132
 133   template<typename _Tp>
 134     constexpr _Tp
 135     __rotl(_Tp __x, int __s) noexcept
 136     {
 137       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 138       if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
 139         {
 140           // Variant for power of two _Nd which the compiler can
 141           // easily pattern match.
 142           constexpr unsigned __uNd = _Nd;
 143           const unsigned __r = __s;
 144           return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
 145         }
 146       const int __r = __s % _Nd;
 147       if (__r == 0)
 148         return __x;
 149       else if (__r > 0)
 150         return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
 151       else
 152         return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
 153     }
 154
 155   template<typename _Tp>
 156     constexpr _Tp
 157     __rotr(_Tp __x, int __s) noexcept
 158     {
 159       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 160       if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
 161         {
 162           // Variant for power of two _Nd which the compiler can
 163           // easily pattern match.
 164           constexpr unsigned __uNd = _Nd;
 165           const unsigned __r = __s;
 166           return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
 167         }
 168       const int __r = __s % _Nd;
 169       if (__r == 0)
 170         return __x;
 171       else if (__r > 0)
 172         return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
 173       else
 174         return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
 175     }
 176
 177   template<typename _Tp>
 178     constexpr int
 179     __countl_zero(_Tp __x) noexcept
 180     {
 181       using __gnu_cxx::__int_traits;
 182       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 183
 184       if (__x == 0)
 185         return _Nd;
 186
 187       constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
 188       constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
 189       constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
 190
 191       if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
 192         {
 193           constexpr int __diff = _Nd_u - _Nd;
 194           return __builtin_clz(__x) - __diff;
 195         }
 196       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
 197         {
 198           constexpr int __diff = _Nd_ul - _Nd;
 199           return __builtin_clzl(__x) - __diff;
 200         }
 201       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
 202         {
 203           constexpr int __diff = _Nd_ull - _Nd;
 204           return __builtin_clzll(__x) - __diff;
 205         }
 206       else // (_Nd > _Nd_ull)
 207         {
 208           static_assert(_Nd <= (2 * _Nd_ull),
 209                         "Maximum supported integer size is 128-bit");
 210
 211           unsigned long long __high = __x >> _Nd_ull;
 212           if (__high != 0)
 213             {
 214               constexpr int __diff = (2 * _Nd_ull) - _Nd;
 215               return __builtin_clzll(__high) - __diff;
 216             }
 217           constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
 218           unsigned long long __low = __x & __max_ull;
 219           return (_Nd - _Nd_ull) + __builtin_clzll(__low);
 220         }
 221     }
 222
 223   template<typename _Tp>
 224     constexpr int
 225     __countl_one(_Tp __x) noexcept
 226     {
 227       return std::__countl_zero<_Tp>((_Tp)~__x);
 228     }
 229
 230   template<typename _Tp>
 231     constexpr int
 232     __countr_zero(_Tp __x) noexcept
 233     {
 234       using __gnu_cxx::__int_traits;
 235       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 236
 237       if (__x == 0)
 238         return _Nd;
 239
 240       constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
 241       constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
 242       constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
 243
 244       if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
 245         return __builtin_ctz(__x);
 246       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
 247         return __builtin_ctzl(__x);
 248       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
 249         return __builtin_ctzll(__x);
 250       else // (_Nd > _Nd_ull)
 251         {
 252           static_assert(_Nd <= (2 * _Nd_ull),
 253                         "Maximum supported integer size is 128-bit");
 254
 255           constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
 256           unsigned long long __low = __x & __max_ull;
 257           if (__low != 0)
 258             return __builtin_ctzll(__low);
 259           unsigned long long __high = __x >> _Nd_ull;
 260           return __builtin_ctzll(__high) + _Nd_ull;
 261         }
 262     }
 263
 264   template<typename _Tp>
 265     constexpr int
 266     __countr_one(_Tp __x) noexcept
 267     {
 268       return std::__countr_zero((_Tp)~__x);
 269     }
 270
 271   template<typename _Tp>
 272     constexpr int
 273     __popcount(_Tp __x) noexcept
 274     {
 275       using __gnu_cxx::__int_traits;
 276       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 277
 278       constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
 279       constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
 280       constexpr auto _Nd_u = __int_traits<unsigned>::__digits;
 281
 282       if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
 283         return __builtin_popcount(__x);
 284       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
 285         return __builtin_popcountl(__x);
 286       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
 287         return __builtin_popcountll(__x);
 288       else // (_Nd > _Nd_ull)
 289         {
 290           static_assert(_Nd <= (2 * _Nd_ull),
 291                         "Maximum supported integer size is 128-bit");
 292
 293           constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
 294           unsigned long long __low = __x & __max_ull;
 295           unsigned long long __high = __x >> _Nd_ull;
 296           return __builtin_popcountll(__low) + __builtin_popcountll(__high);
 297         }
 298     }
 299
 300   template<typename _Tp>
 301     constexpr bool
 302     __has_single_bit(_Tp __x) noexcept
 303     { return std::__popcount(__x) == 1; }
 304
 305   template<typename _Tp>
 306     constexpr _Tp
 307     __bit_ceil(_Tp __x) noexcept
 308     {
 309       using __gnu_cxx::__int_traits;
 310       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 311       if (__x == 0 || __x == 1)
 312         return 1;
 313       auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
 314       // If the shift exponent equals _Nd then the correct result is not
 315       // representable as a value of _Tp, and so the result is undefined.
 316       // Want that undefined behaviour to be detected in constant expressions,
 317       // by UBSan, and by debug assertions.
 318       if (!std::__is_constant_evaluated())
 319         {
 320           __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
 321         }
 322
 323       using __promoted_type = decltype(__x << 1);
 324       if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
 325         {
 326           // If __x undergoes integral promotion then shifting by _Nd is
 327           // not undefined. In order to make the shift undefined, so that
 328           // it is diagnosed in constant expressions and by UBsan, we also
 329           // need to "promote" the shift exponent to be too large for the
 330           // promoted type.
 331           const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
 332           __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
 333         }
 334       return (_Tp)1u << __shift_exponent;
 335     }
 336
 337   template<typename _Tp>
 338     constexpr _Tp
 339     __bit_floor(_Tp __x) noexcept
 340     {
 341       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 342       if (__x == 0)
 343         return 0;
 344       return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
 345     }
 346
 347   template<typename _Tp>
 348     constexpr _Tp
 349     __bit_width(_Tp __x) noexcept
 350     {
 351       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
 352       return _Nd - std::__countl_zero(__x);
 353     }
 354
 355   /// @endcond
 356
 357 #if __cplusplus > 201703L
 358
 359 #define __cpp_lib_bitops 201907L
 360
 361   /// @cond undoc
 362   template<typename _Tp, typename _Up = _Tp>
 363     using _If_is_unsigned_integer
 364       = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
 365   /// @endcond
 366
 367   // [bit.rot], rotating
 368
 369   /// Rotate `x` to the left by `s` bits.
 370   template<typename _Tp>
 371     [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
 372     rotl(_Tp __x, int __s) noexcept
 373     { return std::__rotl(__x, __s); }
 374
 375   /// Rotate `x` to the right by `s` bits.
 376   template<typename _Tp>
 377     [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
 378     rotr(_Tp __x, int __s) noexcept
 379     { return std::__rotr(__x, __s); }
 380
 381   // [bit.count], counting
 382
 383   /// The number of contiguous zero bits, starting from the highest bit.
 384   template<typename _Tp>
 385     constexpr _If_is_unsigned_integer<_Tp, int>
 386     countl_zero(_Tp __x) noexcept
 387     { return std::__countl_zero(__x); }
 388
 389   /// The number of contiguous one bits, starting from the highest bit.
 390   template<typename _Tp>
 391     constexpr _If_is_unsigned_integer<_Tp, int>
 392     countl_one(_Tp __x) noexcept
 393     { return std::__countl_one(__x); }
 394
 395   /// The number of contiguous zero bits, starting from the lowest bit.
 396   template<typename _Tp>
 397     constexpr _If_is_unsigned_integer<_Tp, int>
 398     countr_zero(_Tp __x) noexcept
 399     { return std::__countr_zero(__x); }
 400
 401   /// The number of contiguous one bits, starting from the lowest bit.
 402   template<typename _Tp>
 403     constexpr _If_is_unsigned_integer<_Tp, int>
 404     countr_one(_Tp __x) noexcept
 405     { return std::__countr_one(__x); }
 406
 407   /// The number of bits set in `x`.
 408   template<typename _Tp>
 409     constexpr _If_is_unsigned_integer<_Tp, int>
 410     popcount(_Tp __x) noexcept
 411     { return std::__popcount(__x); }
 412
 413   // [bit.pow.two], integral powers of 2
 414
 415 #define __cpp_lib_int_pow2 202002L
 416
 417   /// True if `x` is a power of two, false otherwise.
 418   template<typename _Tp>
 419     constexpr _If_is_unsigned_integer<_Tp, bool>
 420     has_single_bit(_Tp __x) noexcept
 421     { return std::__has_single_bit(__x); }
 422
 423   /// The smallest power-of-two not less than `x`.
 424   template<typename _Tp>
 425     constexpr _If_is_unsigned_integer<_Tp>
 426     bit_ceil(_Tp __x) noexcept
 427     { return std::__bit_ceil(__x); }
 428
 429   /// The largest power-of-two not greater than `x`.
 430   template<typename _Tp>
 431     constexpr _If_is_unsigned_integer<_Tp>
 432     bit_floor(_Tp __x) noexcept
 433     { return std::__bit_floor(__x); }
 434
 435   /// The smallest integer greater than the base-2 logarithm of `x`.
 436   template<typename _Tp>
 437     constexpr _If_is_unsigned_integer<_Tp>
 438     bit_width(_Tp __x) noexcept
 439     { return std::__bit_width(__x); }
 440
 441 #define __cpp_lib_endian 201907L
 442
 443   /// Byte order
 444   enum class endian
 445   {
 446     little = __ORDER_LITTLE_ENDIAN__,
 447     big    = __ORDER_BIG_ENDIAN__,
 448     native = __BYTE_ORDER__
 449   };
 450 #endif // C++2a
 451
 452   /// @}
 453
 454 _GLIBCXX_END_NAMESPACE_VERSION
 455 } // namespace std
 456
 457 #endif // C++14
 458 #endif // _GLIBCXX_BIT