From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 2F5BC384DED1 for ; Thu, 15 Feb 2024 11:45:27 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 2F5BC384DED1 Authentication-Results: sourceware.org; dmarc=pass (p=none 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 2F5BC384DED1 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707997530; cv=none; b=SYucUHw2Qcx4eCAyMt/RvmP8hPpL0SEFC4V77SVVFqEhkvXcrU8FkmXriuPF1CmxCC+G/diwjV7Ue5uUb9vzDOPFRr6CsaP1MZK0KReNZa5ghd1DgJqptopc0k4VyOKiy78dXDMYiMT1V1RP/ZtJxyxTOj3EPskWDGrlTuf32fo= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1707997530; c=relaxed/simple; bh=5mdRtXbDsKKcHQnWvEHe7BuAxY7cSPbN+7ni219KRD0=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=jV5wa+6rUdrJTtHkjWw2neQYaKOr/Bh2omi7C3bxESR2oUXBfjmGnn3LYcKAqsTIysWUf6W76dBhRB7Myz94S3S9YsYb3BNDY3L8qFvzBmiaPv9UQ6sMM6jV9ZnRJIwh8BMCtbnlblxU/QldshCdCjhIw5VFt68W4qya9IzRo0Y= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1707997526; 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=jzR0liH4S7KeQWXmretnsKxvrweA6eDus+VGadYPjt8=; b=UV6yHbcx9Qnx8utfrUHhMyDwerHgUzsDVfGf5KCsEy8YMcgzoXcXKnJ3sFNwKyVg5oxmRk lqiAdnoomFzuK77GkIb/QOtRRLOgQdYl++G48HToe+yJ6GFGcBbG6XncKv64kuzfeUBKfm StNKn8sHDMlHQv3Cn5hC3LYYqwsgIV8= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-388-zy-wLiOQOXe4Tnpv6F80PQ-1; Thu, 15 Feb 2024 06:45:23 -0500 X-MC-Unique: zy-wLiOQOXe4Tnpv6F80PQ-1 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (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 mimecast-mx02.redhat.com (Postfix) with ESMTPS id 852553C0009E; Thu, 15 Feb 2024 11:45:23 +0000 (UTC) Received: from localhost (unknown [10.42.28.206]) by smtp.corp.redhat.com (Postfix) with ESMTP id 51F88492BC6; Thu, 15 Feb 2024 11:45:23 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Use 128-bit arithmetic for std::linear_congruential_engine [PR87744] Date: Thu, 15 Feb 2024 11:44:07 +0000 Message-ID: <20240215114522.49628-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.9 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-12.5 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_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Tested aarch64-linux and x86_64-linux (-m64 and -m32). Pushed to trunk. -- >8 -- For 32-bit targets without __int128 we need to implement the LCG transition function by hand using 64-bit types. We can also slightly simplify the __mod function by using if-constexpr unconditionally, disabling -Wc++17-extensions warnings with diagnostic pragmas. libstdc++-v3/ChangeLog: PR libstdc++/87744 * include/bits/random.h [!__SIZEOF_INT128__] (_Select_uint_least_t): Define specialization for 64-bit generators with non-power-of-two modulus and large constants. (__mod): Use if constexpr unconditionally. * testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-error line number. * testsuite/26_numerics/random/linear_congruential_engine/87744.cc: New test. --- libstdc++-v3/include/bits/random.h | 116 ++++++++++++++++-- .../linear_congruential_engine/87744.cc | 22 ++++ .../26_numerics/random/pr60037-neg.cc | 2 +- 3 files changed, 132 insertions(+), 8 deletions(-) create mode 100644 libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/87744.cc diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h index 0fbd092e7ef..5fda21af882 100644 --- a/libstdc++-v3/include/bits/random.h +++ b/libstdc++-v3/include/bits/random.h @@ -64,6 +64,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Implementation-space details. namespace __detail { +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wc++17-extensions" + template (std::numeric_limits<_UIntType>::digits)> @@ -102,6 +105,108 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template struct _Select_uint_least_t<__s, 1> { __extension__ using type = unsigned __int128; }; +#elif __has_builtin(__builtin_add_overflow) \ + && __has_builtin(__builtin_sub_overflow) \ + && defined __UINT64_TYPE__ + template + struct _Select_uint_least_t<__s, 1> + { + // This is NOT a general-purpose 128-bit integer type. + // It only supports (type(a) * x + c) % m as needed by __mod. + struct type + { + explicit + type(uint64_t __a) noexcept : _M_lo(__a), _M_hi(0) { } + + // pre: __l._M_hi == 0 + friend type + operator*(type __l, uint64_t __x) noexcept + { + // Split 64-bit values __l._M_lo and __x into high and low 32-bit + // limbs and multiply those individually. + // l * x = (l0 + l1) * (x0 + x1) = l0x0 + l0x1 + l1x0 + l1x1 + + constexpr uint64_t __mask = 0xffffffff; + uint64_t __ll[2] = { __l._M_lo >> 32, __l._M_lo & __mask }; + uint64_t __xx[2] = { __x >> 32, __x & __mask }; + uint64_t __l0x0 = __ll[0] * __xx[0]; + uint64_t __l0x1 = __ll[0] * __xx[1]; + uint64_t __l1x0 = __ll[1] * __xx[0]; + uint64_t __l1x1 = __ll[1] * __xx[1]; + // These bits are the low half of __l._M_hi + // and the high half of __l._M_lo. + uint64_t __mid + = (__l0x1 & __mask) + (__l1x0 & __mask) + (__l1x1 >> 32); + __l._M_hi = __l0x0 + (__l0x1 >> 32) + (__l1x0 >> 32) + (__mid >> 32); + __l._M_lo = (__mid << 32) + (__l1x1 & __mask); + return __l; + } + + friend type + operator+(type __l, uint64_t __c) noexcept + { + __l._M_hi += __builtin_add_overflow(__l._M_lo, __c, &__l._M_lo); + return __l; + } + + friend type + operator%(type __l, uint64_t __m) noexcept + { + if (__builtin_expect(__l._M_hi == 0, 0)) + { + __l._M_lo %= __m; + return __l; + } + + int __shift = __builtin_clzll(__m) + 64 + - __builtin_clzll(__l._M_hi); + type __x(0); + if (__shift >= 64) + { + __x._M_hi = __m << (__shift - 64); + __x._M_lo = 0; + } + else + { + __x._M_hi = __m >> (64 - __shift); + __x._M_lo = __m << __shift; + } + + while (__l._M_hi != 0 || __l._M_lo >= __m) + { + if (__x <= __l) + { + __l._M_hi -= __x._M_hi; + __l._M_hi -= __builtin_sub_overflow(__l._M_lo, __x._M_lo, + &__l._M_lo); + } + __x._M_lo = (__x._M_lo >> 1) | (__x._M_hi << 63); + __x._M_hi >>= 1; + } + return __l; + } + + // pre: __l._M_hi == 0 + explicit operator uint64_t() const noexcept + { return _M_lo; } + + friend bool operator<(const type& __l, const type& __r) noexcept + { + if (__l._M_hi < __r._M_hi) + return true; + else if (__l._M_hi == __r._M_hi) + return __l._M_lo < __r._M_lo; + else + return false; + } + + friend bool operator<=(const type& __l, const type& __r) noexcept + { return !(__r < __l); } + + uint64_t _M_lo; + uint64_t _M_hi; + }; + }; #endif // Assume a != 0, a < m, c < m, x < m. @@ -149,14 +254,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline _Tp __mod(_Tp __x) { - if _GLIBCXX17_CONSTEXPR (__a == 0) + if constexpr (__a == 0) return __c; - else - { - // _Mod must not be instantiated with a == 0 - constexpr _Tp __a1 = __a ? __a : 1; - return _Mod<_Tp, __m, __a1, __c>::__calc(__x); - } + else // N.B. _Mod must not be instantiated with a == 0 + return _Mod<_Tp, __m, __a, __c>::__calc(__x); } /* @@ -216,6 +317,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __not_> >; +#pragma GCC diagnostic pop } // namespace __detail /// @endcond diff --git a/libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/87744.cc b/libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/87744.cc new file mode 100644 index 00000000000..f8a8f9fc822 --- /dev/null +++ b/libstdc++-v3/testsuite/26_numerics/random/linear_congruential_engine/87744.cc @@ -0,0 +1,22 @@ +// { dg-do run { target c++11 } } +// PR libstdc++/87744 Some valid instantiations of linear_congruential_engine +// produce compiler errors when __int128 isn't available + +#include +#include + +int main() +{ + std::linear_congruential_engine gen; + gen(); + VERIFY( gen() == 20120904253298372 ); + VERIFY( gen() == 499698276788149646 ); + + std::linear_congruential_engine> 1)> gen2; + for (int i = 0; i < 99; ++i) + gen2(); + VERIFY( gen2() == 5913590678204212798 ); +} diff --git a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc index 59cf84adb48..4c24e56cea2 100644 --- a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc +++ b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc @@ -10,6 +10,6 @@ std::__detail::_Adaptor aurng(urng); auto x = std::generate_canonical::digits>(urng); -// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 169 } +// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 271 } // { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 3351 } -- 2.43.0