From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oa1-x31.google.com (mail-oa1-x31.google.com [IPv6:2001:4860:4864:20::31]) by sourceware.org (Postfix) with ESMTPS id 68A96385381B for ; Tue, 2 Aug 2022 13:07:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 68A96385381B Received: by mail-oa1-x31.google.com with SMTP id 586e51a60fabf-10edfa2d57dso6393829fac.0 for ; Tue, 02 Aug 2022 06:07:03 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc; bh=ZMMmndKhR7F3f3YcYtGC/ipBgw4P2IJBScKxN2wixY4=; b=HMZBZNAw++zoY/iiMZsWM7QHPX6k5W7LPmGK8YWZ705khERekF21/1BI/v85LWLOST iXzTcHRGBmLkIXA6JgFDhSz1YFc2rT73p2XtPEodHVotrc3i9shxtHJ02awTNtVYmtIJ UvVawdCZA76StIG0dQ5TZfEx8rBlQeoA6j4O0ATStMsU1kmZRuRZl3fHvbGDx9oN3vRe mYke2q/STNzGlrQnI6lfeYRuLVkPgUIbh2p/M27HjcPC7U05FeRcDtU3y2Jg3UVlIWqH dWmpaFM4QFBUN84qzhhmdvn/Hyj005FjnN3pZiywXKriHLSIfcGIpszkpxHkxluHB9G1 +j7Q== X-Gm-Message-State: AJIora8DP5kHisj10DxSwSBthz35SUho+f9FsZ6kZkrFnLAL4f2w1p9L UMqlofesKQrwDd6CoJduEVsH5pvX1XW3d0BfeCQbaJ41fNFwgw== X-Google-Smtp-Source: AGRyM1vVKkbW9JEMj4oTVWfQYPS0xH2LEOpiA+lc5WTXGrheBkvVJMpFlHGwFhQxs2JSp73PaZK14Q+RywqQQSDXk/4= X-Received: by 2002:a05:6870:e997:b0:10c:6f42:b05e with SMTP id r23-20020a056870e99700b0010c6f42b05emr8999612oao.89.1659445622700; Tue, 02 Aug 2022 06:07:02 -0700 (PDT) MIME-Version: 1.0 References: <20220729123211.876374-1-adhemerval.zanella@linaro.org> <178c4ebc-7754-e413-7b0d-f2044ceeb27f@opteya.com> In-Reply-To: <178c4ebc-7754-e413-7b0d-f2044ceeb27f@opteya.com> From: Noah Goldstein Date: Tue, 2 Aug 2022 21:06:51 +0800 Message-ID: Subject: Re: [PATCH v2] stdlib: Simplify arc4random_uniform To: Yann Droneaud Cc: GNU C Library Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 02 Aug 2022 13:07:06 -0000 On Tue, Aug 2, 2022 at 8:08 PM Yann Droneaud wrote: > > Hi, > > Le 01/08/2022 =C3=A0 21:20, Noah Goldstein a =C3=A9crit : > >> diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c > >> index 1326dfa593..5aa98d1c13 100644 > >> --- a/stdlib/arc4random_uniform.c > >> +++ b/stdlib/arc4random_uniform.c > >> > >> uint32_t > >> __arc4random_uniform (uint32_t n) > >> { > >> @@ -57,83 +38,33 @@ __arc4random_uniform (uint32_t n) > >> + while (1) > >> { > >> + uint32_t value =3D __arc4random (); > >> + > >> + /* Return if the lower power of 2 minus 1 satisfy the condition= . */ > >> + uint32_t r =3D value & mask; > >> + if (r < n) > >> + return r; > >> + > >> + /* Otherwise check if remaining bits of entropy provides fits i= n the > >> + bound. */ > >> + for (int bits_left =3D z; bits_left >=3D bits; bits_left -=3D b= its) > >> + { > >> + value >>=3D bits; > > Can this just be shift by 1 and repeat (32 - z) times or does that > > introduce bias (not seeing exactly why it would)? > > > That was bothering me too, as I was thinking a rotation would be > possible instead of shift. > > I posted the question > https://crypto.stackexchange.com/questions/101325/uniform-rejection-sampl= ing-by-shifting-or-rotating-bits-from-csprng-output-safe > > The answer: there's indeed a bias. Hmm, based on the answer it seems we could shift by `popcnt(n)` (which is guranteed to be <=3D bits). If I understand correctly the issue is the cons= ecutive leading 1s essentially fix ensuing ones but `popcnt(n)` will always clear those fixed ones. After the first zero, the rest of the bits can be anythin= g I believe so there will be no bias from them. > > This explains why my attempt with rotation leads to dieharder > complaining. It was so obvious ... Damn > > > Regards. > > > -- > > Yann Droneaud > > OPTEYA > >