[Bug libstdc++/118665] [13/14/15/16/17 Regression] std::uniform_int_distribution infinite loop with generator returning 0

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118665

--- Comment #10 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Tomasz Kaminski <tkaminsk@gcc.gnu.org>:

https://gcc.gnu.org/g:0af0216885480c9d25a7c06a461c396d0a24b75c

commit r17-3968-g0af0216885480c9d25a7c06a461c396d0a24b75c
Author: Tomasz KamiÅski <tkaminsk@redhat.com>
Date:   Wed Jul 22 14:01:02 2026 +0200

    libstdc++: Prevent hanging of uniform_int_distribution for non-conforming
engines [PR118665]

    Since r11-3757-g98c37d3bacbb2f the uniform_int_distribution uses Lemire's
    algorithm for engines outputting power of two range. As this algorithm
    (in-contrast to other) rejects low outputs from incoming generator, this
    change lead to hangs (due infinite loop) when distribution was mixed
    with non-uniform generator, that returns 0 constantly. Such usage has
    undefined behavior according to standard, however didn't lead to hangs
    prior to GCC 11 and other standard libraries.

    This patch, addresses above by changing the (slower) rejection path of the
    algorithm, to alternate between rejecting front/back value of the __prod %
2^N
    range. This still produces an uniform output, as the range of preserved
    values remain continuous and have same size.

    To elaborate, we notice that the values of  m (__product) are necessary
    an multiplies of range size s (__range), and the shift __product >> N
    distributes them along the bucket of size of 2^N. The produced distribution
    is uniform if each 2^N contains the same number of multiplies of s, i.e.
    we are equally likely to end inside it.

    The shift itself is biased, for example given s == 5 and N == 3, we
    get following buckets:
     [0, 8)   -> 0, 5
     [8, 16)  -> 10, 15
     [16, 24) -> 20
     [24, 32) -> 25, 30
     [32, 40) -> 35
    In that case, the 16 and 32 bucket (and corresponding 2 and 4 outputs)
    are half less likely to occur.

    To mitigate above we observe that any continuous range of size n * s
    (multiply of s) contains exactly n multiplies of s, so by reducing the size
    of the range from 2^N to continuous range of size that is multiply of s, we
    will produce uniform distribution. This can be simply done by rejecting
    2^N % s values in total from either or both sides of the range. It does not
    matter from which side they are rejected.
    As illustration the table bellow shows rejected value for s == 5, N == 3,
    the columns corresponds to buckets and rows labels +X/-Y describe rejecting
    X values from the front and Y values from the back.
           0  8   16  24  32
    +3/-0  0  10  -   25  -
    +2/-1  0  15  -   25  -
    +1/-2  0  15  -   30  -
    +0/-3  5  15  -   30  -

    With above changes, the algorithm finishes successfully for any generator
    that returns same value constantly. While, it is possible to create an
    generator that would still lead to infinite loop, by alternating between
    low and high values, I believe this is inherent property on any algorithm
    that rejects some of the engine's outputs.

    libstdc++-v3/ChangeLog:

            PR libstdc++/118665
            * include/bits/uniform_int_dist.h
            (uniform_int_distribution::_S_nd): Alternate between rejecting
            from beginning/end of the range.
            *
testsuite/26_numerics/random/uniform_int_distribution/operators/pr118665.cc:
            New test.
            *
testsuite/26_numerics/random/uniform_real_distribution/operators/gencanon.cc:
            Updated expected values for test_2p55p1 that's depends on
            uniform_int_distribution.

    Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
    Signed-off-by: Tomasz KamiÅski <tkaminsk@redhat.com>