From patchwork Wed Aug 5 09:56:25 2026 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Tomasz_Kami=C5=84ski?= X-Patchwork-Id: 140637 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from vm01.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id DB1ED4BAE7CC for ; Wed, 5 Aug 2026 09:58:44 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DB1ED4BAE7CC Authentication-Results: sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=gcRzbkCg X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id 96F204BA5433 for ; Wed, 5 Aug 2026 09:58:04 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 96F204BA5433 Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 96F204BA5433 Authentication-Results: sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1785923884; cv=none; b=aAmxngI3RxXgcbYwbo19/gw1bfZRgIfUmekErKXfotlJCCbpRdcNgmwA8hmZQti9/4YY3d5eWF6ejbGJ3ZNtBsk5XRzlCZsnrekw4bwTTTMYGWS2NRWpXRPh/t+c+HYonb2iogSqE5PCRDl9ZThyK1Ju2EqxgWDSW9i5lyoDALU= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1785923884; c=relaxed/simple; bh=IkLVTpJCFq8vXZA4BBwErLREmsduMYQYbjOBQNstSRU=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=cVDiE808Tqi640VP/VYnHyqu4QeRGVeTNNZ+M8orBnFTMHhze8WYF4sxj2fWakfZF/jCRA5nT/itxAuej4NtHVu75PBw40WOJ8Wp0e0Iq2lku3OQRbLZGO7TIOH2nFDdBzNSf7WFlrDZZdGuuhHoQUc6PDauflzSMf1fimhfgSU= ARC-Authentication-Results: i=1; sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=gcRzbkCg DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 96F204BA5433 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1785923884; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=ympsdjpAY3iUsMmyEcCVlCHUS+Bkcf2q32KbIzvAIAQ=; b=gcRzbkCg5f3upsuwl8SgYx5uOoQIN+0sve6v4KIBANzWDhorDIqhyJ1AQTuWbbMS3aiTr8 sDu8Bp+JR8jjde8AjBWU8wuQoRJQ3zaFiv7ANhEDjTGcI8iaMxDKTPrLEetltUgpELt+kd snRAbnJAMGuOnswqHREyrpB1wUJ7+BQ= Received: from mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (ec2-54-186-198-63.us-west-2.compute.amazonaws.com [54.186.198.63]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-306-GC8swWrYPAeGbYA0-JcCiw-1; Wed, 05 Aug 2026 05:58:01 -0400 X-MC-Unique: GC8swWrYPAeGbYA0-JcCiw-1 X-Mimecast-MFC-AGG-ID: GC8swWrYPAeGbYA0-JcCiw_1785923880 Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mx-prod-mc-01.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id D1BC2195609D; Wed, 5 Aug 2026 09:57:59 +0000 (UTC) Received: from localhost (unknown [10.44.34.81]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 2A6061800598; Wed, 5 Aug 2026 09:57:58 +0000 (UTC) From: =?utf-8?q?Tomasz_Kami=C5=84ski?= To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Make internal bit manipulation functions available in C++11. Date: Wed, 5 Aug 2026 11:56:25 +0200 Message-ID: <20260805095757.875362-1-tkaminsk@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: jHTSN1qHXRkDFwJQdIVk3gLVtLVIxQQWS-7Z6L5Akmw_1785923880 X-Mimecast-Originator: redhat.com content-type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, RCVD_IN_SBL_CSS, SPF_HELO_PASS, SPF_NONE, TXREP shortcircuit=no autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~patchwork=sourceware.org@gcc.gnu.org For __countl_zero, __countr_zero, __popcount we split defintions using generic builtin (constexpr in C++11), and typed-builtin (constexpr since 20). 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 function calls. --- The followup enabling header in C++11, I have mentioned. It makes the function constexpr when possible. Testing on x86_64 and powerpc64le. *random* tested in all standard modes, -m32, debug and assertions. 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 b01b92862cc..cfec087f0cd 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 // std::__bit_width #include #include #include @@ -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 . // 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 (std::numeric_limits<_UIntType>::digits)> diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index b2afe411a7c..370109bd04f 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::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 6ea0f6eef83..b735044ca18 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 // for std::integral #include @@ -157,7 +157,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr template - 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 - 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 constexpr int __countl_zero(_Tp __x) noexcept + { + return __builtin_clzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits); + } +#else + template + _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 constexpr int @@ -257,16 +261,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::__countl_zero<_Tp>((_Tp)~__x); } - template +#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg) + template constexpr int __countr_zero(_Tp __x) noexcept + { + return __builtin_ctzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits); + } +#else + template + _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 constexpr int @@ -302,13 +310,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return std::__countr_zero((_Tp)~__x); } +#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg) template constexpr int __popcount(_Tp __x) noexcept { -#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg) return __builtin_popcountg(__x); + } #else + template + _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 constexpr bool __has_single_bit(_Tp __x) noexcept { return std::__popcount(__x) == 1; } + template + constexpr int + __bit_width(_Tp __x) noexcept + { + return __gnu_cxx::__int_traits<_Tp>::__digits - std::__countl_zero(__x); + } + template constexpr _Tp + __bit_floor(_Tp __x) noexcept + { + return (__x == 0) ? (_Tp)0 : ((_Tp)1u << (std::__bit_width(__x) - 1)); + } + + template + _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 - 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 - 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