libstdc++: Fix std::random_shuffle for low RAND_MAX [PR88935]

When RAND_MAX is small and the number of elements being shuffled is
close to it, we get very uneven distributions in std::random_shuffle.

This uses a simple xorshift generator seeded by std::rand if we can't
rely on std::rand itself.

libstdc++-v3/ChangeLog:

	PR libstdc++/88935
	* include/bits/stl_algo.h (random_shuffle) [RAND_MAX < INT_MAX]:
	Use xorshift instead of rand().
	* testsuite/25_algorithms/random_shuffle/88935.cc: New test.

Co-authored-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Giovanni Bajo <rasky@develer.com>

1 files changed, 33 insertions, 9 deletions

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 541f588..778a37a 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -4521,15 +4521,39 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
 
-      if (__first != __last)
-	for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
-	  {
-	    // XXX rand() % N is not uniformly distributed
-	    _RandomAccessIterator __j = __first
-					+ std::rand() % ((__i - __first) + 1);
-	    if (__i != __j)
-	      std::iter_swap(__i, __j);
-	  }
+      if (__first == __last)
+	return;
+
+#if RAND_MAX < __INT_MAX__
+      if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
+	{
+	  // Use a xorshift implementation seeded by two calls to rand()
+	  // instead of using rand() for all the random numbers needed.
+	  unsigned __xss
+	    = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
+	  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+	    {
+	      __xss += !__xss;
+	      __xss ^= __xss << 13;
+	      __xss ^= __xss >> 17;
+	      __xss ^= __xss << 5;
+	      _RandomAccessIterator __j = __first
+					    + (__xss % ((__i - __first) + 1));
+	      if (__i != __j)
+		std::iter_swap(__i, __j);
+	    }
+	  return;
+	}
+#endif
+
+      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+	{
+	  // XXX rand() % N is not uniformly distributed
+	  _RandomAccessIterator __j = __first
+					+ (std::rand() % ((__i - __first) + 1));
+	  if (__i != __j)
+	    std::iter_swap(__i, __j);
+	}
     }
 
   /**