From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 30945 invoked by alias); 14 Jan 2019 20:38:17 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 30928 invoked by uid 89); 14 Jan 2019 20:38:16 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-0.8 required=5.0 tests=BAYES_00,KAM_SHORT,SPF_HELO_PASS,URI_HEX autolearn=no version=3.3.2 spammy=rand, 2006, our, HContent-Transfer-Encoding:8bit X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 14 Jan 2019 20:38:15 +0000 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 0C4EDC05B00E; Mon, 14 Jan 2019 20:38:14 +0000 (UTC) Received: from localhost (unknown [10.33.36.12]) by smtp.corp.redhat.com (Postfix) with ESMTP id C2FFC5EDE4; Mon, 14 Jan 2019 20:38:12 +0000 (UTC) Date: Mon, 14 Jan 2019 20:38:00 -0000 From: Jonathan Wakely To: Giovanni Bajo Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org, Andrea Griffini , mitalia@comelz.com Subject: Re: Fix random_sample_n and random_shuffle when RAND_MAX is small Message-ID: <20190114203811.GK15627@redhat.com> References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: X-Clacks-Overhead: GNU Terry Pratchett User-Agent: Mutt/1.10.1 (2018-07-13) X-SW-Source: 2019-01/txt/msg00803.txt.bz2 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).