[gcc r17-3428] libstdc++: Make internal bit manipulation functions available in C++11.
Tomasz Kaminski
tkaminsk@gcc.gnu.org
Wed Aug 19 14:41:20 GMT 2026
https://gcc.gnu.org/g:c092571209a0cc163374adc156a4fb179b27942e
commit r17-3428-gc092571209a0cc163374adc156a4fb179b27942e
Author: Tomasz Kamiński <tkaminsk@redhat.com>
Date: Wed Aug 5 10:11:23 2026 +0200
libstdc++: Make internal bit manipulation functions available in C++11.
For __countl_zero, __countr_zero, __popcount we split defintions
using generic builtin (constexpr in C++11), and typed-builtin (constexpr
since C++14). The __countl_one, __countr_one and __has_single bit, that
are implemented with single return, as also left constexpr since C++11.
Specializations of __countl_zero, __countr_zero, __popcount and __bit_width
are provided for __rand_unit128. Using template specializations instead
of separate overloads, allow them to be selected by __countl_one, and
other functions that are implemented in terms of above. Despite being
implemented in terms of __countl_zero, __bit_width is specialized to
avoid dependency on __gnu_cxx::__int_traits.
The implementation of __bit_floor uses (std::__bit_width(__x) - 1) instead
of (_Nd - std::__countl_zero((_Tp)(__x >> 1)). This provide supports by
__rand_uint128 by using new overload. For that type __bit_width(__x) -1,
is more optimal that __bit_width(__x >> 1).
libstdc++-v3/ChangeLog:
* include/bits/random.h (std::__rotr, std::__rotl, std::__bit_ceil):
[__cplusplus >= 201103L]: Define as _GLIBCXX14_CONSTEXPR.
(std::__countl_zero, std::__countr_zero, std::__popcount)
[__cplusplus >= 201103L]: Split implementation using generic
builtin, define other as _GLIBCXX14_CONSTEXPR.
(std::__bit_width, std::__bit_floor) [__cplusplus >= 201103L]:
Modify to use single return statement.
* include/bits/random.tcc (std::__countl_zero, std::__countr_zero)
(std::__popcount, std::__bit_width): Define explicit specializations
for __detail::__rand_uint128.
* include/std/bit (std::__generate_canonical_pow2)
(std::__generate_canonical_any): Replace builtins call with
<bit> function calls.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
Diff:
---
libstdc++-v3/include/bits/random.h | 43 ++++++++++++++++++--
libstdc++-v3/include/bits/random.tcc | 17 +++-----
libstdc++-v3/include/std/bit | 79 ++++++++++++++++++++----------------
3 files changed, 88 insertions(+), 51 deletions(-)
diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h
index b01b92862ccd..cfec087f0cd2 100644
--- a/libstdc++-v3/include/bits/random.h
+++ b/libstdc++-v3/include/bits/random.h
@@ -31,6 +31,7 @@
#ifndef _RANDOM_H
#define _RANDOM_H 1
+#include <bit> // std::__bit_width
#include <vector>
#include <bits/ios_base.h>
#include <bits/uniform_int_dist.h>
@@ -68,13 +69,13 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
#endif
/// @cond undocumented
- // Implementation-space details.
- namespace __detail
- {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wc++17-extensions"
#ifndef __SIZEOF_INT128__
+ // Implementation-space details.
+ namespace __detail
+ {
// Emulate 128-bit integer type, for the arithmetic ops used in <random>.
// The __detail::__mod function needs: (type(a) * x + c) % m.
// std::philox_engine needs multiplication and bitwise ops.
@@ -522,8 +523,42 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
uint64_t _M_hi = 0;
uint64_t _M_lo = 0;
};
-#endif // ! __SIZEOF_INT128__
+ } // namespace __detail
+
+ template<>
+ constexpr int
+ __countl_zero(__detail::__rand_uint128 __val) noexcept
+ {
+ return __val._M_hi ? std::__countl_zero(__val._M_hi)
+ : std::__countl_zero(__val._M_lo) + 64;
+ }
+ template<>
+ constexpr int
+ __countr_zero(__detail::__rand_uint128 __val) noexcept
+ {
+ return __val._M_lo ? std::__countr_zero(__val._M_lo)
+ : std::__countr_zero(__val._M_hi) + 64;
+ }
+
+ template<>
+ constexpr int
+ __popcount(__detail::__rand_uint128 __val) noexcept
+ {
+ return std::__popcount(__val._M_hi) + std::__popcount(__val._M_lo);
+ }
+
+ template<>
+ constexpr int
+ __bit_width(__detail::__rand_uint128 __val) noexcept
+ {
+ return __val._M_hi ? std::__bit_width(__val._M_hi) + 64
+ : std::__bit_width(__val._M_lo);
+ }
+
+#endif // ! __SIZEOF_INT128__
+ namespace __detail
+ {
template<typename _UIntType, size_t __w,
bool = __w < static_cast<size_t>
(std::numeric_limits<_UIntType>::digits)>
diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index 9690fdf7a8f9..b2b18e66f5f1 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -3706,10 +3706,10 @@ namespace __detail
// Commented-out assignments below are of values specified in
// the Standard, but not used here for reasons noted.
// r = 2; // Redundant, we only support radix 2.
- using _Rng = decltype(_Urbg::max());
- const _Rng __rng_range_less_1 = _Urbg::max() - _Urbg::min();
+ using _URng = typename make_unsigned<decltype(_Urbg::max())>::type;
+ const _URng __rng_range_less_1(_Urbg::max() - _Urbg::min());
// R = _UInt(__rng_range_less_1) + 1; // May wrap to 0.
- const auto __log2_R = __builtin_popcountg(__rng_range_less_1);
+ const auto __log2_R = std::__popcount(__rng_range_less_1);
const auto __log2_uint_max = sizeof(_UInt) * __CHAR_BIT__;
// rd = _UInt(1) << __d; // Could overflow, UB.
const unsigned __k = (__d + __log2_R - 1) / __log2_R;
@@ -3804,8 +3804,7 @@ namespace __detail
// Cannot overflow, as _Urbg::max() - _Urbg::min() is not power of
// two minus one
constexpr _UIntR __R = _UIntR(_Urbg::max() - _Urbg::min()) + 1;
- constexpr unsigned __log2R
- = sizeof(_UIntR) * __CHAR_BIT__ - __builtin_clzg(__R) - 1;
+ constexpr unsigned __log2R = std::__bit_width(__R) - 1;
// We overstimate number of required bits, by computing
// m such that m * log2(R) >= d, so:
// R^m >= (2 ^ log2(R)) ^ m == 2 ^ (log2(R) * m) >= 2^d
@@ -3872,13 +3871,7 @@ namespace __detail
// __abits is maximum bit width of the value, that can
// be multiplied by R^l without overflowing 128 bit integer
- _GLIBCXX_GEN_CANON_CONST unsigned __bwRl
-#ifndef __SIZEOF_INT128__
- = __Rl._M_hi ? 128 - __builtin_clzg(__Rl._M_hi)
- : 64 - __builtin_clzg(__Rl._M_lo);
-#else
- = 128 - __builtin_clzg(__Rl);
-#endif
+ _GLIBCXX_GEN_CANON_CONST unsigned __bwRl = std::__bit_width(__Rl);
// For __R close to power of two, the actual __k may be smaller than __m,
// and will use less than 128bits, default to two 32 bits chunks.
diff --git a/libstdc++-v3/include/std/bit b/libstdc++-v3/include/std/bit
index 6ea0f6eef834..b735044ca18b 100644
--- a/libstdc++-v3/include/std/bit
+++ b/libstdc++-v3/include/std/bit
@@ -33,7 +33,7 @@
#pragma GCC system_header
#endif
-#if __cplusplus >= 201402L
+#if __cplusplus >= 201103L
#include <concepts> // for std::integral
#include <type_traits>
@@ -157,7 +157,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
template<typename _Tp>
- constexpr _Tp
+ _GLIBCXX14_CONSTEXPR _Tp
__rotl(_Tp __x, int __s) noexcept
{
constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
@@ -179,7 +179,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
template<typename _Tp>
- constexpr _Tp
+ _GLIBCXX14_CONSTEXPR _Tp
__rotr(_Tp __x, int __s) noexcept
{
constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
@@ -200,16 +200,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
}
+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clzg)
template<typename _Tp>
constexpr int
__countl_zero(_Tp __x) noexcept
+ {
+ return __builtin_clzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits);
+ }
+#else
+ template<typename _Tp>
+ _GLIBCXX14_CONSTEXPR int
+ __countl_zero(_Tp __x) noexcept
{
using __gnu_cxx::__int_traits;
constexpr auto _Nd = __int_traits<_Tp>::__digits;
-
-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clzg)
- return __builtin_clzg(__x, _Nd);
-#else
if (__x == 0)
return _Nd;
@@ -247,8 +251,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
unsigned long long __low = __x & __max_ull;
return (_Nd - _Nd_ull) + __builtin_clzll(__low);
}
-#endif
}
+#endif
template<typename _Tp>
constexpr int
@@ -257,16 +261,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return std::__countl_zero<_Tp>((_Tp)~__x);
}
- template<typename _Tp>
+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg)
+ template<typename _Tp>
constexpr int
__countr_zero(_Tp __x) noexcept
+ {
+ return __builtin_ctzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits);
+ }
+#else
+ template<typename _Tp>
+ _GLIBCXX14_CONSTEXPR int
+ __countr_zero(_Tp __x) noexcept
{
using __gnu_cxx::__int_traits;
constexpr auto _Nd = __int_traits<_Tp>::__digits;
-
-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg)
- return __builtin_ctzg(__x, _Nd);
-#else
if (__x == 0)
return _Nd;
@@ -292,8 +300,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
unsigned long long __high = __x >> _Nd_ull;
return __builtin_ctzll(__high) + _Nd_ull;
}
-#endif
}
+#endif
template<typename _Tp>
constexpr int
@@ -302,13 +310,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return std::__countr_zero((_Tp)~__x);
}
+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
template<typename _Tp>
constexpr int
__popcount(_Tp __x) noexcept
{
-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
return __builtin_popcountg(__x);
+ }
#else
+ template<typename _Tp>
+ _GLIBCXX14_CONSTEXPR int
+ __popcount(_Tp __x) noexcept
+ {
using __gnu_cxx::__int_traits;
constexpr auto _Nd = __int_traits<_Tp>::__digits;
@@ -332,16 +345,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
unsigned long long __high = __x >> _Nd_ull;
return __builtin_popcountll(__low) + __builtin_popcountll(__high);
}
-#endif
}
+#endif
template<typename _Tp>
constexpr bool
__has_single_bit(_Tp __x) noexcept
{ return std::__popcount(__x) == 1; }
+ template<typename _Tp>
+ constexpr int
+ __bit_width(_Tp __x) noexcept
+ {
+ return __gnu_cxx::__int_traits<_Tp>::__digits - std::__countl_zero(__x);
+ }
+
template<typename _Tp>
constexpr _Tp
+ __bit_floor(_Tp __x) noexcept
+ {
+ return (__x == 0) ? (_Tp)0 : ((_Tp)1u << (std::__bit_width(__x) - 1));
+ }
+
+ template<typename _Tp>
+ _GLIBCXX14_CONSTEXPR _Tp
__bit_ceil(_Tp __x) noexcept
{
using __gnu_cxx::__int_traits;
@@ -372,24 +399,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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);
- }
-
#pragma GCC diagnostic pop
/// @endcond
@@ -499,5 +508,5 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
-#endif // C++14
+#endif // C++11
#endif // _GLIBCXX_BIT
More information about the Libstdc++-cvs
mailing list