[thirdparty/gcc.git] / libstdc++-v3 / include / std / bit

// <bit> -*- C++ -*-

// Copyright (C) 2018-2023 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file include/bit
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_BIT
#define _GLIBCXX_BIT 1

#pragma GCC system_header

#if __cplusplus >= 201402L

#include <concepts> // for std::integral
#include <type_traits>

#if _GLIBCXX_HOSTED || __has_include(<ext/numeric_traits.h>)
# include <ext/numeric_traits.h>
#else
# include <limits>
/// @cond undocumented
namespace __gnu_cxx
{
  template<typename _Tp>
    struct __int_traits
    {
      static constexpr int __digits = std::numeric_limits<_Tp>::digits;
      static constexpr _Tp __max = std::numeric_limits<_Tp>::max();
    };
}
/// @endcond
#endif

#define __glibcxx_want_bit_cast
#define __glibcxx_want_byteswap
#define __glibcxx_want_bitops
#define __glibcxx_want_int_pow2
#define __glibcxx_want_endian
#include <bits/version.h>

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**
   * @defgroup bit_manip Bit manipulation
   * @ingroup numerics
   *
   * Utilities for examining and manipulating individual bits.
   *
   * @{
   */

#ifdef __cpp_lib_bit_cast // C++ >= 20

  /// Create a value of type `To` from the bits of `from`.
  /**
   * @tparam _To   A trivially-copyable type.
   * @param __from A trivially-copyable object of the same size as `_To`.
   * @return       An object of type `_To`.
   * @since C++20
   */
  template<typename _To, typename _From>
    [[nodiscard]]
    constexpr _To
    bit_cast(const _From& __from) noexcept
#ifdef __cpp_concepts
    requires (sizeof(_To) == sizeof(_From))
      && __is_trivially_copyable(_To) && __is_trivially_copyable(_From)
#endif
    {
      return __builtin_bit_cast(_To, __from);
    }
#endif // __cpp_lib_bit_cast

#ifdef __cpp_lib_byteswap // C++ >= 23

  /// Reverse order of bytes in the object representation of `value`.
  /**
   * @tparam _Tp     An integral type.
   * @param __value  An object of integer type.
   * @return         An object of the same type, with the bytes reversed.
   * @since C++23
   */
  template<integral _Tp>
    [[nodiscard]]
    constexpr _Tp
    byteswap(_Tp __value) noexcept
    {
      if constexpr (sizeof(_Tp) == 1)
	return __value;
#if __cpp_if_consteval >= 202106L && __CHAR_BIT__ == 8
      if !consteval
	{
	  if constexpr (sizeof(_Tp) == 2)
	    return __builtin_bswap16(__value);
	  if constexpr (sizeof(_Tp) == 4)
	    return __builtin_bswap32(__value);
	  if constexpr (sizeof(_Tp) == 8)
	    return __builtin_bswap64(__value);
	  if constexpr (sizeof(_Tp) == 16)
#if __has_builtin(__builtin_bswap128)
	    return __builtin_bswap128(__value);
#else
	    return (__builtin_bswap64(__value >> 64)
		    | (static_cast<_Tp>(__builtin_bswap64(__value)) << 64));
#endif
	}
#endif

      // Fallback implementation that handles even __int24 etc.
      using _Up = typename __make_unsigned<__remove_cv_t<_Tp>>::__type;
      size_t __diff = __CHAR_BIT__ * (sizeof(_Tp) - 1);
      _Up __mask1 = static_cast<unsigned char>(~0);
      _Up __mask2 = __mask1 << __diff;
      _Up __val = __value;
      for (size_t __i = 0; __i < sizeof(_Tp) / 2; ++__i)
	{
	  _Up __byte1 = __val & __mask1;
	  _Up __byte2 = __val & __mask2;
	  __val = (__val ^ __byte1 ^ __byte2
		   ^ (__byte1 << __diff) ^ (__byte2 >> __diff));
	  __mask1 <<= __CHAR_BIT__;
	  __mask2 >>= __CHAR_BIT__;
	  __diff -= 2 * __CHAR_BIT__;
	}
      return __val;
    }
#endif // __cpp_lib_byteswap

  /// @cond undocumented

  template<typename _Tp>
    constexpr _Tp
    __rotl(_Tp __x, int __s) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
	{
	  // Variant for power of two _Nd which the compiler can
	  // easily pattern match.
	  constexpr unsigned __uNd = _Nd;
	  const unsigned __r = __s;
	  return (__x << (__r % __uNd)) | (__x >> ((-__r) % __uNd));
	}
      const int __r = __s % _Nd;
      if (__r == 0)
	return __x;
      else if (__r > 0)
	return (__x << __r) | (__x >> ((_Nd - __r) % _Nd));
      else
	return (__x >> -__r) | (__x << ((_Nd + __r) % _Nd)); // rotr(x, -r)
    }

  template<typename _Tp>
    constexpr _Tp
    __rotr(_Tp __x, int __s) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      if _GLIBCXX17_CONSTEXPR ((_Nd & (_Nd - 1)) == 0)
	{
	  // Variant for power of two _Nd which the compiler can
	  // easily pattern match.
	  constexpr unsigned __uNd = _Nd;
	  const unsigned __r = __s;
	  return (__x >> (__r % __uNd)) | (__x << ((-__r) % __uNd));
	}
      const int __r = __s % _Nd;
      if (__r == 0)
	return __x;
      else if (__r > 0)
	return (__x >> __r) | (__x << ((_Nd - __r) % _Nd));
      else
	return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
    }

  template<typename _Tp>
    constexpr int
    __countl_zero(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;

      if (__x == 0)
        return _Nd;

      constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
      constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
      constexpr auto _Nd_u = __int_traits<unsigned>::__digits;

      if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
	{
	  constexpr int __diff = _Nd_u - _Nd;
	  return __builtin_clz(__x) - __diff;
	}
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
	{
	  constexpr int __diff = _Nd_ul - _Nd;
	  return __builtin_clzl(__x) - __diff;
	}
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
	{
	  constexpr int __diff = _Nd_ull - _Nd;
	  return __builtin_clzll(__x) - __diff;
	}
      else // (_Nd > _Nd_ull)
	{
	  static_assert(_Nd <= (2 * _Nd_ull),
			"Maximum supported integer size is 128-bit");

	  unsigned long long __high = __x >> _Nd_ull;
	  if (__high != 0)
	    {
	      constexpr int __diff = (2 * _Nd_ull) - _Nd;
	      return __builtin_clzll(__high) - __diff;
	    }
	  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
	  unsigned long long __low = __x & __max_ull;
	  return (_Nd - _Nd_ull) + __builtin_clzll(__low);
	}
    }

  template<typename _Tp>
    constexpr int
    __countl_one(_Tp __x) noexcept
    {
      return std::__countl_zero<_Tp>((_Tp)~__x);
    }

  template<typename _Tp>
    constexpr int
    __countr_zero(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;

      if (__x == 0)
        return _Nd;

      constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
      constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
      constexpr auto _Nd_u = __int_traits<unsigned>::__digits;

      if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
	return __builtin_ctz(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
	return __builtin_ctzl(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
	return __builtin_ctzll(__x);
      else // (_Nd > _Nd_ull)
	{
	  static_assert(_Nd <= (2 * _Nd_ull),
			"Maximum supported integer size is 128-bit");

	  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
	  unsigned long long __low = __x & __max_ull;
	  if (__low != 0)
	    return __builtin_ctzll(__low);
	  unsigned long long __high = __x >> _Nd_ull;
	  return __builtin_ctzll(__high) + _Nd_ull;
	}
    }

  template<typename _Tp>
    constexpr int
    __countr_one(_Tp __x) noexcept
    {
      return std::__countr_zero((_Tp)~__x);
    }

  template<typename _Tp>
    constexpr int
    __popcount(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;

      constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
      constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
      constexpr auto _Nd_u = __int_traits<unsigned>::__digits;

      if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_u)
	return __builtin_popcount(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ul)
	return __builtin_popcountl(__x);
      else if _GLIBCXX17_CONSTEXPR (_Nd <= _Nd_ull)
	return __builtin_popcountll(__x);
      else // (_Nd > _Nd_ull)
	{
	  static_assert(_Nd <= (2 * _Nd_ull),
			"Maximum supported integer size is 128-bit");

	  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
	  unsigned long long __low = __x & __max_ull;
	  unsigned long long __high = __x >> _Nd_ull;
	  return __builtin_popcountll(__low) + __builtin_popcountll(__high);
	}
    }

  template<typename _Tp>
    constexpr bool
    __has_single_bit(_Tp __x) noexcept
    { return std::__popcount(__x) == 1; }

  template<typename _Tp>
    constexpr _Tp
    __bit_ceil(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;
      if (__x == 0 || __x == 1)
        return 1;
      auto __shift_exponent = _Nd - std::__countl_zero((_Tp)(__x - 1u));
      // If the shift exponent equals _Nd then the correct result is not
      // representable as a value of _Tp, and so the result is undefined.
      // Want that undefined behaviour to be detected in constant expressions,
      // by UBSan, and by debug assertions.
      if (!std::__is_constant_evaluated())
	{
	  __glibcxx_assert( __shift_exponent != __int_traits<_Tp>::__digits );
	}

      using __promoted_type = decltype(__x << 1);
      if _GLIBCXX17_CONSTEXPR (!is_same<__promoted_type, _Tp>::value)
	{
	  // If __x undergoes integral promotion then shifting by _Nd is
	  // not undefined. In order to make the shift undefined, so that
	  // it is diagnosed in constant expressions and by UBsan, we also
	  // need to "promote" the shift exponent to be too large for the
	  // promoted type.
	  const int __extra_exp = sizeof(__promoted_type) / sizeof(_Tp) / 2;
	  __shift_exponent |= (__shift_exponent & _Nd) << __extra_exp;
	}
      return (_Tp)1u << __shift_exponent;
    }

  template<typename _Tp>
    constexpr _Tp
    __bit_floor(_Tp __x) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      if (__x == 0)
        return 0;
      return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
    }

  template<typename _Tp>
    constexpr int
    __bit_width(_Tp __x) noexcept
    {
      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
      return _Nd - std::__countl_zero(__x);
    }

  /// @endcond

#ifdef __cpp_lib_bitops // C++ >= 20

  /// @cond undocumented
  template<typename _Tp>
    concept __unsigned_integer = __is_unsigned_integer<_Tp>::value;
  /// @endcond

  // [bit.rot], rotating

  /// Rotate `x` to the left by `s` bits.
  template<__unsigned_integer _Tp>
    [[nodiscard]] constexpr _Tp
    rotl(_Tp __x, int __s) noexcept
    { return std::__rotl(__x, __s); }

  /// Rotate `x` to the right by `s` bits.
  template<__unsigned_integer _Tp>
    [[nodiscard]] constexpr _Tp
    rotr(_Tp __x, int __s) noexcept
    { return std::__rotr(__x, __s); }

  // [bit.count], counting

  /// The number of contiguous zero bits, starting from the highest bit.
  template<__unsigned_integer _Tp>
    constexpr int
    countl_zero(_Tp __x) noexcept
    { return std::__countl_zero(__x); }

  /// The number of contiguous one bits, starting from the highest bit.
  template<__unsigned_integer _Tp>
    constexpr int
    countl_one(_Tp __x) noexcept
    { return std::__countl_one(__x); }

  /// The number of contiguous zero bits, starting from the lowest bit.
  template<__unsigned_integer _Tp>
    constexpr int
    countr_zero(_Tp __x) noexcept
    { return std::__countr_zero(__x); }

  /// The number of contiguous one bits, starting from the lowest bit.
  template<__unsigned_integer _Tp>
    constexpr int
    countr_one(_Tp __x) noexcept
    { return std::__countr_one(__x); }

  /// The number of bits set in `x`.
  template<__unsigned_integer _Tp>
    constexpr int
    popcount(_Tp __x) noexcept
    { return std::__popcount(__x); }
#endif // __cpp_lib_bitops

#ifdef __cpp_lib_int_pow2 // C++ >= 20
  // [bit.pow.two], integral powers of 2

  /// True if `x` is a power of two, false otherwise.
  template<__unsigned_integer _Tp>
    constexpr bool
    has_single_bit(_Tp __x) noexcept
    { return std::__has_single_bit(__x); }

  /// The smallest power-of-two not less than `x`.
  template<__unsigned_integer _Tp>
    constexpr _Tp
    bit_ceil(_Tp __x) noexcept
    { return std::__bit_ceil(__x); }

  /// The largest power-of-two not greater than `x`.
  template<__unsigned_integer _Tp>
    constexpr _Tp
    bit_floor(_Tp __x) noexcept
    { return std::__bit_floor(__x); }

  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 3656. Inconsistent bit operations returning a count
  /// The smallest integer greater than the base-2 logarithm of `x`.
  template<__unsigned_integer _Tp>
    constexpr int
    bit_width(_Tp __x) noexcept
    { return std::__bit_width(__x); }
#endif // defined (__cpp_lib_int_pow2)

#ifdef __cpp_lib_endian // C++ >= 20

  /// Byte order constants
  /**
   * The platform endianness can be checked by comparing `std::endian::native`
   * to one of `std::endian::big` or `std::endian::little`.
   *
   * @since C++20
   */
  enum class endian
  {
    little = __ORDER_LITTLE_ENDIAN__,
    big    = __ORDER_BIG_ENDIAN__,
    native = __BYTE_ORDER__
  };
#endif // __cpp_lib_endian

  /// @}

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std

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