[gcc r16-9620] libstdc++: Handle generators with non-zero min in uniform_int_distribution [PR118665]

[Tomasz Kaminski]

https://gcc.gnu.org/g:04c3e1efd4917e9cc32f7e413e8ffdce65b5aa44

commit r16-9620-g04c3e1efd4917e9cc32f7e413e8ffdce65b5aa44
Author: Tomasz Kamiński <tkaminsk@redhat.com>
Date:   Mon Jul 27 16:39:46 2026 +0200

    libstdc++: Handle generators with non-zero min in uniform_int_distribution [PR118665]
    
    The commit r11-3757-g98c37d3bacbb2f that introduced Lemire's algorithm in
    uniform_int_distribution, assumed that any engine that generates range of
    size 2^32 or 2^64, returns a range starting from zero. While this is true
    for all standard providede engines, it may not be true for user provided
    range. In such case the produced output is no longer uniform:
    testDiscreteDist was failing for such engine.
    
    This patch simply substract __min (_Urbg::min()) from the generated number
    (__g()). As this value is compile time constant, this has no performance
    impact for generators producing ranges starting from zero.
    
            PR libstdc++/118665
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/uniform_int_dist.h (uniform_int_distribution::_S_nd):
            Substract __min (_Urbg::min()) from each generator invocation.
            * testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc:
            Add testDiscreteDist for shifted (with non-zero min()) engine.
    
    Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
    Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
    (cherry picked from commit 9d93ec2ac1b13ab09ca80bf0c684cb035e36a431)

Diff:
---
 libstdc++-v3/include/bits/uniform_int_dist.h       |  5 +++--
 .../uniform_int_distribution/operators/values.cc   | 22 ++++++++++++++++++++++
 2 files changed, 25 insertions(+), 2 deletions(-)

diff --git a/libstdc++-v3/include/bits/uniform_int_dist.h b/libstdc++-v3/include/bits/uniform_int_dist.h
index 9c5514c7c138..072c6351e1fa 100644
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -262,18 +262,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  static_assert(!_Wp_traits::__is_signed, "W must be unsigned");
 	  static_assert(_Wp_traits::__digits == (2 * _Up_traits::__digits),
 			"W must be twice as wide as U");
+	  constexpr auto __min = _Urbg::min();
 
 	  // reference: Fast Random Integer Generation in an Interval
 	  // ACM Transactions on Modeling and Computer Simulation 29 (1), 2019
 	  // https://arxiv.org/abs/1805.10941
-	  _Wp __product = _Wp(__g()) * _Wp(__range);
+	  _Wp __product = _Wp(__g() - __min) * _Wp(__range);
 	  _Up __low = _Up(__product);
 	  if (__low < __range)
 	    {
 	      _Up __threshold = -__range % __range;
 	      while (__low < __threshold)
 		{
-		  __product = _Wp(__g()) * _Wp(__range);
+		  __product = _Wp(__g() - __min) * _Wp(__range);
 		  __low = _Up(__product);
 		}
 	    }
diff --git a/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc
index 11758a3e2b68..fce14944d884 100644
--- a/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc
+++ b/libstdc++-v3/testsuite/26_numerics/random/uniform_int_distribution/operators/values.cc
@@ -21,6 +21,7 @@
 // 26.5.8.2.1 Class template uniform_int_distribution [rand.dist.uni.int]
 
 #include <random>
+#include <cstdint>
 #include <functional>
 #include <testsuite_random.h>
 
@@ -32,6 +33,19 @@
 # define ARGS
 #endif
 
+template<std::uint64_t Offset>
+struct shifted
+{
+  using result_type = std::uint64_t;
+  static constexpr result_type min() { return Offset; }
+  static constexpr result_type max() { return Offset + std::mt19937::max(); }
+
+  result_type operator()()
+  { return Offset + eng(); }
+
+  std::mt19937 eng;
+};
+
 void test01()
 {
   using namespace __gnu_test;
@@ -49,6 +63,14 @@ void test01()
   std::uniform_int_distribution<> uid3(1, 20);
   auto buid3 = std::bind(uid3, eng);
   testDiscreteDist<ARGS>(buid3, [](int n) { return uniform_int_pdf(n, 1, 20); } );
+
+  shifted<(std::uint64_t(1) << 16)> s16e;
+  auto buid4 = std::bind(uid3, s16e);
+  testDiscreteDist<ARGS>(buid4, [](int n) { return uniform_int_pdf(n, 1, 20); } );
+
+  shifted<(std::uint64_t(1) << 32)> s32e;
+  auto buid5 = std::bind(uid3, s32e);
+  testDiscreteDist<ARGS>(buid5, [](int n) { return uniform_int_pdf(n, 1, 20); } );
 }
 
 int main()