libstdc++-v3/include/std/bit

   1 // <bit> -*- C++ -*-
   2
   3 // Copyright (C) 2018-2019 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 #include <limits>
  38
  39 namespace std _GLIBCXX_VISIBILITY(default)
  40 {
  41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  42
  43   /**
  44    * @defgroup bit_manip Bit manipulation
  45    * @ingroup numerics
  46    *
  47    * Utilities for examining and manipulating individual bits.
  48    *
  49    * @{
  50    */
  51
  52   /// @cond undoc
  53
  54   template<typename _Tp>
  55     constexpr _Tp
  56     __rotl(_Tp __x, int __s) noexcept
  57     {
  58       constexpr auto _Nd = numeric_limits<_Tp>::digits;
  59       const int __r = __s % _Nd;
  60       if (__r == 0)
  61         return __x;
  62       else if (__r > 0)
  63         return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
  64       else
  65         return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
  66     }
  67
  68   template<typename _Tp>
  69     constexpr _Tp
  70     __rotr(_Tp __x, int __s) noexcept
  71     {
  72       constexpr auto _Nd = numeric_limits<_Tp>::digits;
  73       const int __r = __s % _Nd;
  74       if (__r == 0)
  75         return __x;
  76       else if (__r > 0)
  77         return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
  78       else
  79         return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
  80     }
  81
  82   template<typename _Tp>
  83     constexpr int
  84     __countl_zero(_Tp __x) noexcept
  85     {
  86       constexpr auto _Nd = numeric_limits<_Tp>::digits;
  87
  88       if (__x == 0)
  89         return _Nd;
  90
  91       constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits;
  92       constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits;
  93       constexpr auto _Nd_u = numeric_limits<unsigned>::digits;
  94
  95       if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
  96         {
  97           constexpr int __diff = _Nd_u - _Nd;
  98           return __builtin_clz(__x) - __diff;
  99         }
 100       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
 101         {
 102           constexpr int __diff = _Nd_ul - _Nd;
 103           return __builtin_clzl(__x) - __diff;
 104         }
 105       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
 106         {
 107           constexpr int __diff = _Nd_ull - _Nd;
 108           return __builtin_clzll(__x) - __diff;
 109         }
 110       else // (_Nd > _Nd_ull)
 111         {
 112           static_assert(_Nd <= (2 * _Nd_ull),
 113                         "Maximum supported integer size is 128-bit");
 114
 115           unsigned long long __high = __x >> _Nd_ull;
 116           if (__high != 0)
 117             {
 118               constexpr int __diff = (2 * _Nd_ull) - _Nd;
 119               return __builtin_clzll(__high) - __diff;
 120             }
 121           constexpr auto __max_ull = numeric_limits<unsigned long long>::max();
 122           unsigned long long __low = __x & __max_ull;
 123           return (_Nd - _Nd_ull) + __builtin_clzll(__low);
 124         }
 125     }
 126
 127   template<typename _Tp>
 128     constexpr int
 129     __countl_one(_Tp __x) noexcept
 130     {
 131       if (__x == numeric_limits<_Tp>::max())
 132         return numeric_limits<_Tp>::digits;
 133       return std::__countl_zero<_Tp>((_Tp)~__x);
 134     }
 135
 136   template<typename _Tp>
 137     constexpr int
 138     __countr_zero(_Tp __x) noexcept
 139     {
 140       constexpr auto _Nd = numeric_limits<_Tp>::digits;
 141
 142       if (__x == 0)
 143         return _Nd;
 144
 145       constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits;
 146       constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits;
 147       constexpr auto _Nd_u = numeric_limits<unsigned>::digits;
 148
 149       if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
 150         return __builtin_ctz(__x);
 151       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
 152         return __builtin_ctzl(__x);
 153       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
 154         return __builtin_ctzll(__x);
 155       else // (_Nd > _Nd_ull)
 156         {
 157           static_assert(_Nd <= (2 * _Nd_ull),
 158                         "Maximum supported integer size is 128-bit");
 159
 160           constexpr auto __max_ull = numeric_limits<unsigned long long>::max();
 161           unsigned long long __low = __x & __max_ull;
 162           if (__low != 0)
 163             return __builtin_ctzll(__low);
 164           unsigned long long __high = __x >> _Nd_ull;
 165           return __builtin_ctzll(__high) + _Nd_ull;
 166         }
 167     }
 168
 169   template<typename _Tp>
 170     constexpr int
 171     __countr_one(_Tp __x) noexcept
 172     {
 173       if (__x == numeric_limits<_Tp>::max())
 174         return numeric_limits<_Tp>::digits;
 175       return std::__countr_zero((_Tp)~__x);
 176     }
 177
 178   template<typename _Tp>
 179     constexpr int
 180     __popcount(_Tp __x) noexcept
 181     {
 182       constexpr auto _Nd = numeric_limits<_Tp>::digits;
 183
 184       if (__x == 0)
 185         return 0;
 186
 187       constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits;
 188       constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits;
 189       constexpr auto _Nd_u = numeric_limits<unsigned>::digits;
 190
 191       if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
 192         return __builtin_popcount(__x);
 193       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
 194         return __builtin_popcountl(__x);
 195       else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
 196         return __builtin_popcountll(__x);
 197       else // (_Nd > _Nd_ull)
 198         {
 199           static_assert(_Nd <= (2 * _Nd_ull),
 200                         "Maximum supported integer size is 128-bit");
 201
 202           constexpr auto __max_ull = numeric_limits<unsigned long long>::max();
 203           unsigned long long __low = __x & __max_ull;
 204           unsigned long long __high = __x >> _Nd_ull;
 205           return __builtin_popcountll(__low) + __builtin_popcountll(__high);
 206         }
 207     }
 208
 209   template<typename _Tp>
 210     constexpr bool
 211     __ispow2(_Tp __x) noexcept
 212     { return std::__popcount(__x) == 1; }
 213
 214   template<typename _Tp>
 215     constexpr _Tp
 216     __ceil2(_Tp __x) noexcept
 217     {
 218       constexpr auto _Nd = numeric_limits<_Tp>::digits;
 219       if (__x == 0 || __x == 1)
 220         return 1;
 221       auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
 222       // If the shift exponent equals _Nd then the correct result is not
 223       // representable as a value of _Tp, and so the result is undefined.
 224       // Want that undefined behaviour to be detected in constant expressions,
 225       // by UBSan, and by debug assertions.
 226 #ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED
 227       if (!__builtin_is_constant_evaluated())
 228         __glibcxx_assert( __shift_exponent != numeric_limits<_Tp>::digits );
 229 #endif
 230       using __promoted_type = decltype(__x << 1);
 231       if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
 232         {
 233           // If __x undergoes integral promotion then shifting by _Nd is
 234           // not undefined. In order to make the shift undefined, so that
 235           // it is diagnosed in constant expressions and by UBsan, we also
 236           // need to "promote" the shift exponent to be too large for the
 237           // promoted type.
 238           const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
 239           __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
 240         }
 241       return (_Tp)1u << __shift_exponent;
 242     }
 243
 244   template<typename _Tp>
 245     constexpr _Tp
 246     __floor2(_Tp __x) noexcept
 247     {
 248       constexpr auto _Nd = numeric_limits<_Tp>::digits;
 249       if (__x == 0)
 250         return 0;
 251       return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
 252     }
 253
 254   template<typename _Tp>
 255     constexpr _Tp
 256     __log2p1(_Tp __x) noexcept
 257     {
 258       constexpr auto _Nd = numeric_limits<_Tp>::digits;
 259       return _Nd - std::__countl_zero(__x);
 260     }
 261
 262   /// @endcond
 263
 264 #if __cplusplus > 201703L
 265
 266   /// @cond undoc
 267   template<typename _Tp, typename _Up = _Tp>
 268     using _If_is_unsigned_integer
 269       = enable_if_t<__is_unsigned_integer<_Tp>::value, _Up>;
 270   /// @endcond
 271
 272   // [bit.rot], rotating
 273
 274   /// Rotate `x` to the left by `s` bits.
 275   template<typename _Tp>
 276     [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
 277     rotl(_Tp __x, int __s) noexcept
 278     { return std::__rotl(__x, __s); }
 279
 280   /// Rotate `x` to the right by `s` bits.
 281   template<typename _Tp>
 282     [[nodiscard]] constexpr _If_is_unsigned_integer<_Tp>
 283     rotr(_Tp __x, int __s) noexcept
 284     { return std::__rotr(__x, __s); }
 285
 286   // [bit.count], counting
 287
 288   /// The number of contiguous zero bits, starting from the highest bit.
 289   template<typename _Tp>
 290     constexpr _If_is_unsigned_integer<_Tp, int>
 291     countl_zero(_Tp __x) noexcept
 292     { return std::__countl_zero(__x); }
 293
 294   /// The number of contiguous one bits, starting from the highest bit.
 295   template<typename _Tp>
 296     constexpr _If_is_unsigned_integer<_Tp, int>
 297     countl_one(_Tp __x) noexcept
 298     { return std::__countl_one(__x); }
 299
 300   /// The number of contiguous zero bits, starting from the lowest bit.
 301   template<typename _Tp>
 302     constexpr _If_is_unsigned_integer<_Tp, int>
 303     countr_zero(_Tp __x) noexcept
 304     { return std::__countr_zero(__x); }
 305
 306   /// The number of contiguous one bits, starting from the lowest bit.
 307   template<typename _Tp>
 308     constexpr _If_is_unsigned_integer<_Tp, int>
 309     countr_one(_Tp __x) noexcept
 310     { return std::__countr_one(__x); }
 311
 312   /// The number of bits set in `x`.
 313   template<typename _Tp>
 314     constexpr _If_is_unsigned_integer<_Tp, int>
 315     popcount(_Tp __x) noexcept
 316     { return std::__popcount(__x); }
 317
 318   // [bit.pow.two], integral powers of 2
 319
 320   /// True if `x` is a power of two, false otherwise.
 321   template<typename _Tp>
 322     constexpr _If_is_unsigned_integer<_Tp, bool>
 323     ispow2(_Tp __x) noexcept
 324     { return std::__ispow2(__x); }
 325
 326   /// The smallest power-of-two not less than `x`.
 327   template<typename _Tp>
 328     constexpr _If_is_unsigned_integer<_Tp>
 329     ceil2(_Tp __x) noexcept
 330     { return std::__ceil2(__x); }
 331
 332   /// The largest power-of-two not greater than `x`.
 333   template<typename _Tp>
 334     constexpr _If_is_unsigned_integer<_Tp>
 335     floor2(_Tp __x) noexcept
 336     { return std::__floor2(__x); }
 337
 338   /// The smallest integer greater than the base-2 logarithm of `x`.
 339   template<typename _Tp>
 340     constexpr _If_is_unsigned_integer<_Tp>
 341     log2p1(_Tp __x) noexcept
 342     { return std::__log2p1(__x); }
 343
 344 #define __cpp_lib_endian 201907L
 345
 346   /// Byte order
 347   enum class endian
 348   {
 349     little = __ORDER_LITTLE_ENDIAN__,
 350     big    = __ORDER_BIG_ENDIAN__,
 351     native = __BYTE_ORDER__
 352   };
 353 #endif // C++2a
 354
 355   /// @}
 356
 357 _GLIBCXX_END_NAMESPACE_VERSION
 358 } // namespace std
 359
 360 #endif // C++14
 361 #endif // _GLIBCXX_BIT