[Bug libstdc++/97311] New: Bug in std::seed_seq::generate() when integer type has more than 32 bits

[Bug libstdc++/97311] New: Bug in std::seed_seq::generate() when integer type has more than 32 bits

[kristian.spangsege at gmail dot com]

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

            Bug ID: 97311
           Summary: Bug in std::seed_seq::generate() when integer type has
                    more than 32 bits
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kristian.spangsege at gmail dot com
  Target Milestone: ---

As far as I can tell, std::seed_seq::generate() has a bug when _Type has more
than 32 bits.

The problem is that the following two additions can produce values greater
than, or equal to 2**32:

    __begin[(__k + __p) % __n] += __r1;
    __begin[(__k + __q) % __n] += __r2;

According to C++17 standard text, all operations must be performed modulo
2**32, so no generated value can be greater than, or equal to 2**32.

It seems that a possible fix would be to change those two lines to something
like this:

    __begin[(__k + __p) % __n] = __detail::__mod<_Type, __detail::_Shift<_Type,
32>::__value>(__begin[(__k + __p) % __n] + __r1));
    __begin[(__k + __q) % __n] = __detail::__mod<_Type, __detail::_Shift<_Type,
32>::__value>(__begin[(__k + __q) % __n] + __r2));

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-10-07
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I wonder why we don't just use uint32_t everywhere instead of those
metafunctions.

uint32_t __r3 = ...;
uint32_t __r4 = ...;
// ...
__begin[(__k + __p) % __n] = (uint32_t)__begin[(__k + __p) % __n] + __r3;
__begin[(__k + __q) % __n] = (uint32_t)__begin[(__k + __q) % __n] + __r4;

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[redi at gcc dot gnu.org]

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

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Or something like:

      auto __b = [__begin, __n](size_t __i) -> _Type& {
          return __begin[__i % __n];
      };
      auto __b32 = [__b](size_t __i) { return (uint32_t)__b(__i); };

      for (size_t __k = 0; __k < __m; ++__k)
        {
          uint32_t __arg = (__b32(__k) ^ __b32(__k + __p) ^ __b32(__k - 1));
          uint32_t __r1 = 1664525u * (__arg ^ (__arg >> 27));
          uint32_t __r2 = __r1;
          if (__k == 0)
            __r2 += __s;
          else if (__k <= __s)
            __r2 += __k % __n + _M_v[__k - 1];
          else
            __r2 += __k % __n;
          __b(__k + __p) = __b32(__k + __p) +  __r1;
          __b(__k + __q) = __b32(__k + __q) + __r2;
          __b(__k) = __r2;
        }

      for (size_t __k = __m; __k < __m + __n; ++__k)
        {
          uint32_t __arg = (__b32(__k) + __b32(__k + __p) + __b32(__k - 1));
          uint32_t __r3 = (uint32_t)1566083941u * (__arg ^ (__arg >> 27));
          uint32_t __r4 = __r3 - __k % __n;
          __b(__k + __p) ^= __r3;
          __b(__k + __q) ^= __r4;
          __b(__k) = __r4;
        }

The current code will work even if the implementation only provides
uint_least32_t and not uint32_t, but I don't think we support any targets
without uint32_t. So it could be a lot simpler.

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[kristian.spangsege at gmail dot com]

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

--- Comment #3 from Kristian Spangsege <kristian.spangsege at gmail dot com> ---
I would recommend not locking arithmetic to std::uint32_t, and instead working
with std::uint_fast32_t, because I can imaging a platform (current or future)
where 32-bit arithmetic is slower that 64-bit arithmetic. As a bonus, the code
will work on platforms that do not have std::uint32_t.

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Kristian Spangsege from comment #3)
> bonus, the code will work on platforms that do not have std::uint32_t.

GCC doesn't work on such platforms, and other parts of libstdc++ already assume
it exists, so that's not useful.

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I don't see how manually written arithmetic with explicit % operations is going
to beat using built-in types that do that automatically.

If 64-bit arithmetic is faster than 32-bit arithmetic, I would expect the
compiler to use 64-bit registers and mask them off to produce 32-bit results.
If the user has to do that manually to get better performance, then the
compiler has a bug.

The only reason not to use uint32_t is because some platforms don't support it,
and as I've already said that's not relevant for this implementation.

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[redi at gcc dot gnu.org]

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I can't get the algorithm to ever produce an intermediate result that doesn't
fit in 32 bits, so I'm not sure there's actually a problem here in practice.

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[redi at gcc dot gnu.org]

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

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oops, yes I can, I messed up my test.

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[cvs-commit at gcc dot gnu.org]

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

--- Comment #8 from CVS 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:3ee44d4c518d61c6bbf75fcf280edc6ce5326ce0

commit r11-3759-g3ee44d4c518d61c6bbf75fcf280edc6ce5326ce0
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Oct 9 16:10:31 2020 +0100

    libstdc++: Fix incorrect results in std::seed_seq::generate [PR 97311]

    This ensures that intermediate results are done in uint32_t values,
    meeting the requirement for operations to be done modulo 2^32.

    If the target doesn't define __UINT32_TYPE__ then substitute uint32_t
    with a class type that uses uint_least32_t and masks the value to
    UINT32_MAX.

    I've also split the first loop that goes from k=0 to k<m into three
    loops, for k=0, [1,s] and [s+1,m). This avoids branching for those three
    cases in the body of the loop, and also avoids the concerns in PR 94823
    regarding the k-1 index when k==0.

    libstdc++-v3/ChangeLog:

            PR libstdc++/97311
            * include/bits/random.tcc (seed_seq::generate): Use uint32_t for
            calculations. Also split the first loop into three loops to
            avoid branching on k on every iteration, resolving PR 94823.
            * testsuite/26_numerics/random/seed_seq/97311.cc: New test.
            * testsuite/26_numerics/random/pr60037-neg.cc: Adjust dg-erro
            line number.

[Bug libstdc++/97311] Bug in std::seed_seq::generate() when integer type has more than 32 bits

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
   Target Milestone|---                         |11.0
             Status|NEW                         |RESOLVED

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on master.

The current code produces the wrong results for signed 64-bit types, but I'm
not sure whether backporting it (and changing the results in the middle of a
release series) is a good idea.