Skip site navigation (1)Skip section navigation (2)
Date:      Sun, 22 May 2016 10:06:48 +1000 (EST)
From:      Bruce Evans <brde@optusnet.com.au>
To:        Pedro Giffuni <pfg@freebsd.org>
Cc:        cem@freebsd.org, src-committers@freebsd.org, svn-src-all@freebsd.org,  svn-src-head@freebsd.org
Subject:   Re: svn commit: r300377 - head/sys/compat/ndis
Message-ID:  <20160522091455.A1014@besplex.bde.org>
In-Reply-To: <262938a6-50bd-b6f4-24c9-895b837a368e@FreeBSD.org>
References:  <201605211752.u4LHqiHQ031457@repo.freebsd.org> <CAG6CVpXjU3tHdar7d=xyr%2BTmffg0NrQu3q7SD=b6%2BjF=yvVr-Q@mail.gmail.com> <a88c14ea-ee78-54de-6142-08a561a49d98@FreeBSD.org> <CAG6CVpV_3%2B%2BWqg2X23=RM942zaDkyL6fxH2YN0TXUqpPjneCOw@mail.gmail.com> <262938a6-50bd-b6f4-24c9-895b837a368e@FreeBSD.org>

next in thread | previous in thread | raw e-mail | index | archive | help
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@freebsd.org> wrote:
>>>=20
>>>=20
>>> On 05/21/16 14:05, Conrad Meyer wrote:
>>>> Won't this still return a negative integer in many cases?
>>>>=20
>>>> random(9) returns u_long, whereas this rand() routine returns 'int'.
>>>>=20
>>>> 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).
>>>=20
>>> According to:
>>> sys/libkern/random.c
>>>=20
>>> The result is uniform on [0, 2^31 - 1].
>>=20
>> Ah, I missed that.  Sorry!  In that case, I'm not sure why this is
>> needed =E2=80=94 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 aro=
und=20
> 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=
=2E
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
From owner-svn-src-all@freebsd.org  Sun May 22 00:18:46 2016
Return-Path: <owner-svn-src-all@freebsd.org>
Delivered-To: svn-src-all@mailman.ysv.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org
 [IPv6:2001:1900:2254:206a::19:1])
 by mailman.ysv.freebsd.org (Postfix) with ESMTP id 13390B459FB;
 Sun, 22 May 2016 00:18:46 +0000 (UTC)
 (envelope-from andriyvos@gmail.com)
Received: from mail-lb0-f174.google.com (mail-lb0-f174.google.com
 [209.85.217.174])
 (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
 (Client CN "smtp.gmail.com",
 Issuer "Google Internet Authority G2" (verified OK))
 by mx1.freebsd.org (Postfix) with ESMTPS id 8F4A41A7D;
 Sun, 22 May 2016 00:18:45 +0000 (UTC)
 (envelope-from andriyvos@gmail.com)
Received: by mail-lb0-f174.google.com with SMTP id k7so24830044lbm.0;
 Sat, 21 May 2016 17:18:45 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20130820;
 h=x-gm-message-state:to:subject:references:date:mime-version
 :content-transfer-encoding:from:message-id:in-reply-to:user-agent;
 bh=mpZEUB2IAz8c49r7+L9IniXA/4F8THQZDDFsBde6e6o=;
 b=jKzIr2dvaGlkEUm8JztjyqzakSx7YrVDip5KS1wmMdf9qtlZI05ATQBzKfyFaE3np7
 qZNIW8+jW59vQSZUEdN6+SMKDc7eVccyzM3/IZsl21qox94AC023IO3zF8gU84iLXZjQ
 xKyjxS4k/+KhmwjBS+tGofpOUDCbR35iVa6/MkOiQDQpHfpuD3TOMMbclNAsniRztGF0
 vJhKHnruSJq4lbyrP1BLuIGCmbSefrQs7RvJC2VyqtTKFJTg0NU/8cV/MVWw7sbcK+Jx
 Aj2itQ6cL2cZ7Z2132ZINgaSpCdNtl8LcYU7sMFwRjTjgdhbb1lQP9h8RqcpQB9aBAfQ
 lNsg==
X-Gm-Message-State: AOPr4FV7LXJFai3RRh/1nBF7Uh9p4+2ImewIGQU/1Suhq0/ysBtq2/ZCFvfKutREwZi+WA==
X-Received: by 10.112.154.5 with SMTP id vk5mr3530789lbb.126.1463873048615;
 Sat, 21 May 2016 16:24:08 -0700 (PDT)
Received: from localhost (host-176-37-109-22.la.net.ua. [176.37.109.22])
 by smtp.gmail.com with ESMTPSA id d63sm2977547lfb.48.2016.05.21.16.24.07
 (version=TLS1 cipher=AES128-SHA bits=128/128);
 Sat, 21 May 2016 16:24:08 -0700 (PDT)
Content-Type: text/plain; charset=utf-8; format=flowed; delsp=yes
To: src-committers@freebsd.org, svn-src-all@freebsd.org,
 "svn-src-head@freebsd.org" <svn-src-head@freebsd.org>
Subject: Re: svn commit: r300383 - head/sys/net80211
References: <201605212321.u4LNLgDI029432@repo.freebsd.org>
Date: Sun, 22 May 2016 02:24:03 +0300
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: "Andriy Voskoboinyk" <avos@freebsd.org>
Message-ID: <op.yht5yd094dikkl@localhost>
In-Reply-To: <201605212321.u4LNLgDI029432@repo.freebsd.org>
User-Agent: Opera Mail/12.16 (FreeBSD)
X-BeenThere: svn-src-all@freebsd.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: "SVN commit messages for the entire src tree \(except for &quot;
 user&quot; and &quot; projects&quot; \)" <svn-src-all.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/svn-src-all>,
 <mailto:svn-src-all-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/svn-src-all/>;
List-Post: <mailto:svn-src-all@freebsd.org>
List-Help: <mailto:svn-src-all-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/svn-src-all>,
 <mailto:svn-src-all-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sun, 22 May 2016 00:18:46 -0000

Tested with wpi(4) and urtwn(4) in STA mode.



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20160522091455.A1014>