[Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop

[Bug libstdc++/114359] New: std::binomial_distribution hangs in infinite loop

[angelo.landi at outlook dot com]

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

            Bug ID: 114359
           Summary: std::binomial_distribution hangs in infinite loop
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: angelo.landi at outlook dot com
  Target Milestone: ---

Created attachment 57715
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57715&action=edit
minimal example to expose the issue

Due to an integer overflow: in any std::binomial_distribution<IntType>
initialized with 2^n trials with n >= (bit size of IntType) - 2, operator()
will be stuck in the do-while(__reject) loop forever.

The issue was originally found on StackOverflow by user Floyd Everest:
https://stackoverflow.com/questions/75179395/stdbinomial-distribution-hangs-forever-with-certain-inputs/75179982

You can find a more detailed explanation of the issue in my answer to that
post:
https://stackoverflow.com/questions/75179395/stdbinomial-distribution-hangs-forever-with-certain-inputs/75179982#75179982

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
> Due to an integer overflow

Hmm, I don't think this is an integer overflow but rather due to wrapping. Yes
there is a difference as overflow is undefined behavior while wrapping is
defined.

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[angelo.landi at outlook dot com]

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

--- Comment #2 from Angelo Landi <angelo.landi at outlook dot com> ---
(In reply to Andrew Pinski from comment #1)
> > Due to an integer overflow
> 
> Hmm, I don't think this is an integer overflow but rather due to wrapping.
> Yes there is a difference as overflow is undefined behavior while wrapping
> is defined.

Indeed; separating the cases for unsigned and signed integers, only the first
has the (conditionally) well-defined behaviour described, while the latter has
undefined behaviour.

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-03-16
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
This seems to fix it:

--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -1503,7 +1503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
          // sqrt(pi / 2)
          const double __spi_2 = 1.2533141373155002512078826424055226L;
          _M_s1 = std::sqrt(__np * __1p) * (1 + _M_d1 / (4 * __np));
-         _M_s2 = std::sqrt(__np * __1p) * (1 + _M_d2 / (4 * _M_t * __1p));
+         _M_s2 = std::sqrt(__np * __1p) * (1 + _M_d2 / (4 * (_M_t * __1p)));
          _M_c = 2 * _M_d1 / __np;
          _M_a1 = std::exp(_M_c) * _M_s1 * __spi_2;
          const double __a12 = _M_a1 + _M_s2 * __spi_2;

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:07e03761a7fc1626a6a74ed957e117f56981558c

commit r14-9551-g07e03761a7fc1626a6a74ed957e117f56981558c
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Mar 18 13:22:17 2024 +0000

    libstdc++: Fix infinite loop in std::binomial_distribution [PR114359]

    The multiplication (4 * _M_t * __1p) can wraparound to zero if _M_t is
    unsigned and 4 * _M_t wraps to zero. The third operand has type double,
    so do the second multiplication first, so that we aren't multiplying
    integers.

    libstdc++-v3/ChangeLog:

            PR libstdc++/114359
            * include/bits/random.tcc (binomial_distribution::param_type):
            Ensure arithmetic is done as type double.
            * testsuite/26_numerics/random/binomial_distribution/114359.cc: New
test.

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.4

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk so far.

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[cvs-commit at gcc dot gnu.org]

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

--- Comment #6 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:71e941b0e329d3a316e465569c92e08788a68614

commit r13-8771-g71e941b0e329d3a316e465569c92e08788a68614
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Mar 18 13:22:17 2024 +0000

    libstdc++: Fix infinite loop in std::binomial_distribution [PR114359]

    The multiplication (4 * _M_t * __1p) can wraparound to zero if _M_t is
    unsigned and 4 * _M_t wraps to zero. The third operand has type double,
    so do the second multiplication first, so that we aren't multiplying
    integers.

    libstdc++-v3/ChangeLog:

            PR libstdc++/114359
            * include/bits/random.tcc (binomial_distribution::param_type):
            Ensure arithmetic is done as type double.
            * testsuite/26_numerics/random/binomial_distribution/114359.cc: New
test.

    (cherry picked from commit 07e03761a7fc1626a6a74ed957e117f56981558c)

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 13.3 and 14.1 so far, I still plan to backport this to gcc-12 too.

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jonathan Wakely
<redi@gcc.gnu.org>:

https://gcc.gnu.org/g:bd31ecc1c7aef5b4ae7ddb04926a2f4105957df4

commit r12-10538-gbd31ecc1c7aef5b4ae7ddb04926a2f4105957df4
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Mar 18 13:22:17 2024 +0000

    libstdc++: Fix infinite loop in std::binomial_distribution [PR114359]

    The multiplication (4 * _M_t * __1p) can wraparound to zero if _M_t is
    unsigned and 4 * _M_t wraps to zero. The third operand has type double,
    so do the second multiplication first, so that we aren't multiplying
    integers.

    libstdc++-v3/ChangeLog:

            PR libstdc++/114359
            * include/bits/random.tcc (binomial_distribution::param_type):
            Ensure arithmetic is done as type double.
            * testsuite/26_numerics/random/binomial_distribution/114359.cc: New
test.

    (cherry picked from commit 07e03761a7fc1626a6a74ed957e117f56981558c)

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[redi at gcc dot gnu.org]

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

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Also fixed for 12.4

[Bug libstdc++/114359] std::binomial_distribution hangs in infinite loop

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:9b8c3e622c7cd4ea393f59b873c3107767e1ba88

commit r15-1301-g9b8c3e622c7cd4ea393f59b873c3107767e1ba88
Author: Alexandre Oliva <oliva@adacore.com>
Date:   Thu Jun 13 20:10:55 2024 -0300

    [libstdc++] [testsuite] require cmath for [PR114359]

    When !_GLIBCXX_USE_C99_MATH_TR1, binomial_distribution doesn't use the
    optimized algorithm that was fixed in response to PR114359.  Without
    that optimized algorithm, operator() ends up looping very very long
    for the test, to the point that it would time out by several orders of
    magnitude, without even exercising the optimized algorithm that we're
    testing for regressions.  Arrange for the test to be skipped if that
    bit won't be exercised.


    for  libstdc++-v3/ChangeLog

            PR libstdc++/114359
            * testsuite/26_numerics/random/binomial_distribution/114359.cc:
            Require cmath.