Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:100238 Return-Path: Mailing-List: contact internals-help@lists.php.net; run by ezmlm Delivered-To: mailing list internals@lists.php.net Received: (qmail 80100 invoked from network); 16 Aug 2017 22:03:03 -0000 Received: from unknown (HELO lists.php.net) (127.0.0.1) by localhost with SMTP; 16 Aug 2017 22:03:03 -0000 Authentication-Results: pb1.pair.com smtp.mail=solar@openwall.com; spf=pass; sender-id=pass Authentication-Results: pb1.pair.com header.from=solar@openwall.com; sender-id=pass Received-SPF: pass (pb1.pair.com: domain openwall.com designates 195.42.179.200 as permitted sender) X-PHP-List-Original-Sender: solar@openwall.com X-Host-Fingerprint: 195.42.179.200 mother.openwall.net Received: from [195.42.179.200] ([195.42.179.200:60900] helo=mother.openwall.net) by pb1.pair.com (ecelerity 2.1.1.9-wez r(12769M)) with ESMTP id CC/39-34801-611C4995 for ; Wed, 16 Aug 2017 18:03:03 -0400 Received: (qmail 20235 invoked from network); 16 Aug 2017 22:02:59 -0000 Received: from localhost (HELO pvt.openwall.com) (127.0.0.1) by localhost with SMTP; 16 Aug 2017 22:02:59 -0000 Received: by pvt.openwall.com (Postfix, from userid 503) id 16941AB18D; Thu, 17 Aug 2017 00:02:42 +0200 (CEST) Date: Thu, 17 Aug 2017 00:02:42 +0200 To: Nikita Popov Cc: Leigh , PHP internals Message-ID: <20170816220242.GA13012@openwall.com> References: <20170816191247.GA12324@openwall.com> <20170816214155.GA12831@openwall.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170816214155.GA12831@openwall.com> User-Agent: Mutt/1.4.2.3i Subject: Re: [PHP-DEV] PHP 7.1.0 to 7.2.0beta2 mt_rand() modulo bias bug From: solar@openwall.com (Solar Designer) On Wed, Aug 16, 2017 at 11:41:55PM +0200, Solar Designer wrote: > On Wed, Aug 16, 2017 at 10:06:02PM +0200, Nikita Popov wrote: > > I'd suggest to split the 32-bit and 64-bit code codepaths entirely, as the > > interleaved #ifs are somewhat hard to follow. Something like > > https://gist.github.com/nikic/64e7ec58ebb6121d350fb80927a65082 (not > > thoroughly tested). > > This looks good to me - especially how you reduced the nesting of if's > by special-casing the "Powers of two are not biased" return. With this > change, you can as well drop the "Special case where no modulus is > required", as it'd happen to be handled the same by your new return. > OTOH, that optimization might require an extra comment on its own. > > Here's what this might look like (totally untested): > > https://gist.github.com/solardiz/5e3d313bbee2c1ce6e200e433b750bef One difference I didn't notice at first: the currently committed code does only one php_mt_rand() call per loop iteration when it's skipping "numbers over the limit", even in the 64-bit case (thus, it replaces 32 bits of the value at a time). Your 64-bit version (and my revision of it) does two calls per iteration (replacing the whole number). Arguably, the currently committed code is smarter and more efficient in that respect, whereas yours is cleaner. Regardless, it's an extra change that will affect the generated random numbers in some cases where we could avoid making that change (it's not fixing any bug). I think it's preferable not to unnecessarily change what numbers are generated. Alexander