svn commit: r300377 - head/sys/compat/ndis

Bruce Evans brde at optusnet.com.au
Sun May 22 00:07:02 UTC 2016


On Sat, 21 May 2016, Pedro Giffuni wrote:

> On 05/21/16 16:55, Conrad Meyer wrote:
>> On Sat, May 21, 2016 at 1:40 PM, Pedro Giffuni <pfg at freebsd.org> wrote:
>>> 
>>> 
>>> On 05/21/16 14:05, Conrad Meyer wrote:
>>>> Won't this still return a negative integer in many cases?
>>>> 
>>>> random(9) returns u_long, whereas this rand() routine returns 'int'.
>>>> 
>>>> Even on architectures where long is the same size as ordinary
>>>> integers, the range of possible results of the 'random() / 2 + 1'
>>>> expression, before implicit cast to signed, is [1, 2^31] (inclusive).
>>> 
>>> According to:
>>> sys/libkern/random.c
>>> 
>>> The result is uniform on [0, 2^31 - 1].
>> 
>> Ah, I missed that.  Sorry!  In that case, I'm not sure why this is
>> needed — the result fits in a non-negative 2's complement signed
>> integer.
>
> Actually, I had missed it too. And I also had no idea we were working around 
> the zero singularity.
>
> I will revert the change and will do an adjustment for the case where
> we use 0 as a seed (which in MS should be equivalent to 1).

The libc version has complications related to this.  The libkern
version has rotted by not being kept up to date with the libc version.
4.4BSD-Lite has sort of the reverse bitrot -- in libc, it only has the
bad LCG that copied from an example in the 1990 C standard, while
it has the better LCG copied from 1988 Communications in the ACM in libkern.
FreeBSD still has the ACM version in libkern, and has a fixed copy
of that in libc, with the bad old version under an ifdef.

The libc version now adjusts the range from [0, 0x7fffffff] to
0, 0x7ffffffd] and reduces RAND_MAX by 2 to match.  The claimed uniformity
for the larger range is very wrong, since the ACM algorithm can only
produce numbers in the range [1(or is it 0?), 0x7ffffffe] starting from a
seed in the range [1, 0x7ffffffe(or is it 1 higher?)].  There are problems
at both extremities, and it isn't clear if the new or old adjustments to
avoid them preserve uniformity.  It is clear that the range was at least
1 too high, since the ACM algorithm does a modulo by 0x7fffffff.

Bruce


More information about the svn-src-head mailing list