From 3ee44d4c518d61c6bbf75fcf280edc6ce5326ce0 Mon Sep 17 00:00:00 2001
From: Jonathan Wakely <jwakely@redhat.com>
Date: Fri, 9 Oct 2020 16:10:31 +0100
Subject: [PATCH] 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<m into three
loops, for k=0, [1,s] and [s+1,m). This avoids branching for those three
cases in the body of the loop, and also avoids the concerns in PR 94823
regarding the k-1 index when k==0.

libstdc++-v3/ChangeLog:

	PR libstdc++/97311
	* include/bits/random.tcc (seed_seq::generate): Use uint32_t for
	calculations. Also split the first loop into three loops to
	avoid branching on k on every iteration, resolving PR 94823.
	* testsuite/26_numerics/random/seed_seq/97311.cc: New test.
	* testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-erro
	line number.
---
 libstdc++-v3/include/bits/random.tcc          | 90 ++++++++++++-------
 .../26_numerics/random/pr60037-neg.cc         |  2 +-
 .../26_numerics/random/seed_seq/97311.cc      | 53 +++++++++++
 3 files changed, 113 insertions(+), 32 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/26_numerics/random/seed_seq/97311.cc

diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index a921b9bf815..bf39a51559b 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -3237,42 +3237,70 @@ namespace __detail
       const size_t __q = __p + __t;
       const size_t __m = std::max(size_t(__s + 1), __n);
 
-      for (size_t __k = 0; __k < __m; ++__k)
+#ifndef __UINT32_TYPE__
+      struct _Up
+      {
+	_Up(uint_least32_t v) : _M_v(v & 0xffffffffu) { }
+
+	operator uint_least32_t() const { return _M_v; }
+
+	uint_least32_t _M_v;
+      };
+      using uint32_t = _Up;
+#endif
+
+      // k == 0, every element in [begin,end) equals 0x8b8b8b8bu
 	{
-	  _Type __arg = (__begin[__k % __n]
-			 ^ __begin[(__k + __p) % __n]
-			 ^ __begin[(__k - 1) % __n]);
-	  _Type __r1 = __arg ^ (__arg >> 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<std::size_t,
 
 // { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 167 }
 
-// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 3284 }
+// { dg-error "static assertion failed: template argument must be a floating point type" "" { target *-*-* } 3312 }
diff --git a/libstdc++-v3/testsuite/26_numerics/random/seed_seq/97311.cc b/libstdc++-v3/testsuite/26_numerics/random/seed_seq/97311.cc
new file mode 100644
index 00000000000..594e859b8f8
--- /dev/null
+++ b/libstdc++-v3/testsuite/26_numerics/random/seed_seq/97311.cc
@@ -0,0 +1,53 @@
+// Copyright (C) 2020 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.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+#include <random>
+#include <cstdint>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  // PR libstdc++/97311
+
+  using i64 = std::int_least64_t; // can hold all values of uint32_t
+  std::vector<i64> v(10);
+  std::seed_seq s;
+  s.generate(v.begin(), v.end());
+
+  const std::vector<i64> expected{
+    0xbc199682,
+    0x7a094407,
+    0xac05bf42,
+    0x10baa2f4,
+    0x822d6fde,
+    0xf08cdc22,
+    0x30382aee,
+    0xbd5fb4aa,
+    0xb26c5a35,
+    0xb9619724
+  };
+  VERIFY( v == expected );
+}
+
+int
+main()
+{
+  test01();
+}
-- 
2.30.2