libstdc++: Prevent hangs in uniform_int_distribution
Fixes infinite loops in uniform_int_distribution when used with non-conforming random number engines.
The uniform_int_distribution in libstdc++ could enter an infinite loop when paired with certain random number engines that consistently produce zero. This was due to an algorithm change that rejected low outputs. This patch modifies the rejection path to alternate between the front and back of the output range, ensuring uniformity without causing hangs.
In Details
The Lemire's algorithm for uniform_int_distribution, when applied to engines producing a power-of-two range, had a rejection path that could loop indefinitely if the engine outputted zero. This commit adjusts that path to alternate rejections from either end of the output range, maintaining uniformity while preventing hangs for undefined but plausible usage patterns. Affects uniform_int_distribution in <random>.
- uniform_int_distribution
- A C++ standard library class that generates random integers uniformly within a specified range. It's part of the <random> header.
- random number engine
- A pseudo-random number generator that produces a sequence of numbers. C++'s <random> library uses engines as the source for distributions.
- Lemire's algorithm
- An efficient algorithm for generating uniformly distributed random integers, often used in C++ standard library implementations.