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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 5EF19385780E for ; Fri, 9 Oct 2020 16:05:54 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 5EF19385780E Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-123-4Q5wbWSqNHijg8tIqHpDiQ-1; Fri, 09 Oct 2020 12:05:48 -0400 X-MC-Unique: 4Q5wbWSqNHijg8tIqHpDiQ-1 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id DAFFA914700; Fri, 9 Oct 2020 16:05:47 +0000 (UTC) Received: from localhost (unknown [10.33.36.19]) by smtp.corp.redhat.com (Postfix) with ESMTP id 778DC5C1BB; Fri, 9 Oct 2020 16:05:47 +0000 (UTC) Date: Fri, 9 Oct 2020 17:05:46 +0100 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Fix incorrect results in std::seed_seq::generate [PR 97311] Message-ID: <20201009160546.GA750592@redhat.com> MIME-Version: 1.0 X-Clacks-Overhead: GNU Terry Pratchett X-Scanned-By: MIMEDefang 2.79 on 10.5.11.16 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: multipart/mixed; boundary="GvXjxJ+pjyke8COw" Content-Disposition: inline X-Spam-Status: No, score=-12.0 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP, URIBL_SBL, URIBL_SBL_A autolearn=unavailable autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 09 Oct 2020 16:05:56 -0000 --GvXjxJ+pjyke8COw Content-Type: text/plain; charset=us-ascii Content-Disposition: inline This ensures that intermediate results are done in uint32_t values, meeting the requirement for operations to be done modulo 2^32. If the target doesn't define __UINT32_TYPE__ then substitute uint32_t with a class type that uses uint_least32_t and masks the value to UINT32_MAX. I've also split the first loop that goes from k=0 to k Date: Fri Oct 9 16:10:31 2020 libstdc++: Fix incorrect results in std::seed_seq::generate [PR 97311] This ensures that intermediate results are done in uint32_t values, meeting the requirement for operations to be done modulo 2^32. If the target doesn't define __UINT32_TYPE__ then substitute uint32_t with a class type that uses uint_least32_t and masks the value to UINT32_MAX. I've also split the first loop that goes from k=0 to k> 27); - __r1 = __detail::__mod<_Type, - __detail::_Shift<_Type, 32>::__value>(1664525u * __r1); - _Type __r2 = __r1; - if (__k == 0) - __r2 += __s; - else if (__k <= __s) - __r2 += __k % __n + _M_v[__k - 1]; - else - __r2 += __k % __n; - __r2 = __detail::__mod<_Type, - __detail::_Shift<_Type, 32>::__value>(__r2); - __begin[(__k + __p) % __n] += __r1; - __begin[(__k + __q) % __n] += __r2; - __begin[__k % __n] = __r2; + uint32_t __r1 = 1371501266u; + uint32_t __r2 = __r1 + __s; + __begin[__p] += __r1; + __begin[__q] = (uint32_t)__begin[__q] + __r2; + __begin[0] = __r2; + } + + for (size_t __k = 1; __k <= __s; ++__k) + { + const size_t __kn = __k % __n; + const size_t __kpn = (__k + __p) % __n; + const size_t __kqn = (__k + __q) % __n; + uint32_t __arg = (__begin[__kn] + ^ __begin[__kpn] + ^ __begin[(__k - 1) % __n]); + uint32_t __r1 = 1664525u * (__arg ^ (__arg >> 27)); + uint32_t __r2 = __r1 + (uint32_t)__kn + _M_v[__k - 1]; + __begin[__kpn] = (uint32_t)__begin[__kpn] + __r1; + __begin[__kqn] = (uint32_t)__begin[__kqn] + __r2; + __begin[__kn] = __r2; + } + + for (size_t __k = __s + 1; __k < __m; ++__k) + { + const size_t __kn = __k % __n; + const size_t __kpn = (__k + __p) % __n; + const size_t __kqn = (__k + __q) % __n; + uint32_t __arg = (__begin[__kn] + ^ __begin[__kpn] + ^ __begin[(__k - 1) % __n]); + uint32_t __r1 = 1664525u * (__arg ^ (__arg >> 27)); + uint32_t __r2 = __r1 + (uint32_t)__kn; + __begin[__kpn] = (uint32_t)__begin[__kpn] + __r1; + __begin[__kqn] = (uint32_t)__begin[__kqn] + __r2; + __begin[__kn] = __r2; } for (size_t __k = __m; __k < __m + __n; ++__k) { - _Type __arg = (__begin[__k % __n] - + __begin[(__k + __p) % __n] - + __begin[(__k - 1) % __n]); - _Type __r3 = __arg ^ (__arg >> 27); - __r3 = __detail::__mod<_Type, - __detail::_Shift<_Type, 32>::__value>(1566083941u * __r3); - _Type __r4 = __r3 - __k % __n; - __r4 = __detail::__mod<_Type, - __detail::_Shift<_Type, 32>::__value>(__r4); - __begin[(__k + __p) % __n] ^= __r3; - __begin[(__k + __q) % __n] ^= __r4; - __begin[__k % __n] = __r4; + const size_t __kn = __k % __n; + const size_t __kpn = (__k + __p) % __n; + const size_t __kqn = (__k + __q) % __n; + uint32_t __arg = (__begin[__kn] + + __begin[__kpn] + + __begin[(__k - 1) % __n]); + uint32_t __r3 = 1566083941u * (__arg ^ (__arg >> 27)); + uint32_t __r4 = __r3 - __kn; + __begin[__kpn] ^= __r3; + __begin[__kqn] ^= __r4; + __begin[__kn] = __r4; } } diff --git a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc index 9cffc3d06f9..0b5f597040b 100644 --- a/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc +++ b/libstdc++-v3/testsuite/26_numerics/random/pr60037-neg.cc @@ -12,4 +12,4 @@ auto x = std::generate_canonical. + +// { dg-do run { target c++11 } } + +#include +#include +#include + +void +test01() +{ + // PR libstdc++/97311 + + using i64 = std::int_least64_t; // can hold all values of uint32_t + std::vector v(10); + std::seed_seq s; + s.generate(v.begin(), v.end()); + + const std::vector expected{ + 0xbc199682, + 0x7a094407, + 0xac05bf42, + 0x10baa2f4, + 0x822d6fde, + 0xf08cdc22, + 0x30382aee, + 0xbd5fb4aa, + 0xb26c5a35, + 0xb9619724 + }; + VERIFY( v == expected ); +} + +int +main() +{ + test01(); +} --GvXjxJ+pjyke8COw--