Re: Fix random_sample_n and random_shuffle when RAND_MAX is small

[Jonathan Wakely <jwakely at redhat dot com>]

On 12/12/18 22:31 +0100, Giovanni Bajo wrote:
> Hello,
>
> we hit a bug today while cross-compiling a C++ program with mingw32:
> if random_shuffle or random_sample_n are called with a sequence of
> elements whose length is higher than RAND_MAX, the functions don't
> behave as expected because they ignore elements beyond RAND_MAX. This
> does not happen often on Linux where glibc defines RAND_MAX to 2**31,
> but mingw32 (all released versions) relies on the very old msvcrt.lib,
> where RAND_MAX is just 2**15.
>
> I found mentions of this problem in 2011
> (http://mingw-users.1079350.n2.nabble.com/RAND-MAX-still-16bit-td6299546.html)
> and 2006 (https://mingw-users.narkive.com/gAIO4G5V/rand-max-problem-why-is-it-only-16-bit).
>
> I'm attaching a proof-of-concept patch that fixes the problem by
> introducing an embedded xorshift generator, seeded with std::rand (so
> that the functions still depend on srand — it looks like this is not
> strictly required by the standard, but it sounds like a good thing to
> do for backward compatibility with existing programs). I was wondering
> if this approach is OK or something else is preferred.

I'd prefer not to introduce that change unconditionally. The existing
code works fine when std::distance(first, last) < RAND_MAX, and as we
have random access iterators we can check that cheaply.

We'd prefer a bug report in Bugzilla with a testcase that demonstrates
the bug. A portable regression test for our testsuite might not be
practical if it needs more than RAND_MAX elements, but one that runs
for mingw and verifies the fix there would be needed.

See https://gcc.gnu.org/contribute.html#patches for guidelines for
submitting patches (and the rest of the page for other requirements,
like copyright assignment or disclaimers).