This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Fix random_sample_n and random_shuffle when RAND_MAX is small

On 12/12/18 22:31 +0100, Giovanni Bajo wrote:

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
and 2006 (

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 for guidelines for
submitting patches (and the rest of the page for other requirements,
like copyright assignment or disclaimers).

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]