[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.