Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:100239
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.223.178 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <20170816220242.GA13012@openwall.com>
References: <20170816191247.GA12324@openwall.com> <CAPwsocE+8_4J9ZFtWbExH4mKG1haMs1c0OsTXUijn_+rNUN5wQ@mail.gmail.com>
 <CAF+90c82H_4z5TGmKJGS1_Md0c15DvMBngPxUp=Upsx3mb0_2g@mail.gmail.com>
 <20170816214155.GA12831@openwall.com> <20170816220242.GA13012@openwall.com>
Date: Thu, 17 Aug 2017 00:57:56 +0200
Message-ID: <CAF+90c-q_6edO0aoJw=w5q_EopwbtWO8S7uYqAiiRys2zWr2ww@mail.gmail.com>
To: Solar Designer <solar@openwall.com>
Cc: Leigh <leight@gmail.com>, PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="001a11414af4a967550556e6d3e8"
Subject: Re: [PHP-DEV] PHP 7.1.0 to 7.2.0beta2 mt_rand() modulo bias bug
From: nikita.ppv@gmail.com (Nikita Popov)

--001a11414af4a967550556e6d3e8
Content-Type: text/plain; charset="UTF-8"

On Thu, Aug 17, 2017 at 12:02 AM, Solar Designer <solar@openwall.com> wrote:

> 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
>

Good point. However, I think that this optimization is not actually
correct. For example, let's take umax = 0x1_0000_0001, which is the
smallest value for which this codepath is taken. In this case limit would
be 0xffff_ffff_ffff_fffe, so we only resample if the value is exactly
0xffff_ffff_ffff_ffff. So if the resampling codepath is taken in this case,
and we only generate one new 32-bit value, the top word of the result will
be fixed to 0xffff_ffff. (A very small bias in this case, but there's
probably more significant cases.)

Nikita

--001a11414af4a967550556e6d3e8--