https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118665
Jonathan Wakely <redi at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Ever confirmed|0 |1
Last reconfirmed| |2026-05-13
Status|UNCONFIRMED |NEW
--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This can only happen if the the uniform random bit generator is not at all
uniform, specifically if the probablity of it producing values close to
Gen::max() is zero.
Libc++ uses a modified std::independent_bits_engine (with a runtime-provided
'w' value for required the number of bits in the result). That makes it
complete in finite time even if the URBG is broken, but with a large number of
division operations per sample from the URBG.
Lemire's nearly divisionless algorithm assumes that the URBG is not broken, but
performs much better for a working URBG.
Since the rejection path is already the slow path of Lemire's algorithm, we
could add an escape hatch for broken URBGs:
--- a/libstdc++-v3/include/bits/uniform_int_dist.h
+++ b/libstdc++-v3/include/bits/uniform_int_dist.h
@@ -271,7 +271,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__low < __range)
{
_Up __threshold = -__range % __range;
- while (__low < __threshold)
+ _Up __max_tries = 8; // defend against a broken URGB
+ while (__low < __threshold
+ && __builtin_expect(--__max_tries, true))
{
__product = _Wp(__g()) * _Wp(__range);
__low = _Up(__product);
This will not produce a uniform distribution, but that's the URBG's fault. It
shouldn't lie about its Gen::max() or be pathologically non-uniform.
