From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ot1-x332.google.com (mail-ot1-x332.google.com [IPv6:2607:f8b0:4864:20::332]) by sourceware.org (Postfix) with ESMTPS id 0533F3856242 for ; Tue, 2 Aug 2022 13:31:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0533F3856242 Received: by mail-ot1-x332.google.com with SMTP id g20-20020a9d6a14000000b0061c84e679f5so10234585otn.2 for ; Tue, 02 Aug 2022 06:31:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=kzShoPgLsIh5ULoKXEfN2GrBmlamgWNLwx88LKOBydc=; b=GM47ZK00meWF4fey70ZNQkE2SSR0Uwb8y2O43njJd5A0cALMTeRB3kLx/HE5wMExSc WaCYOtlSJZViyfDh7iyyk4NS3j6CNcI8Gra+VUAo6CdMp6Kj6kbQg8/VEI4TbKZzHKIy 3gE6l6Wu+7gQ/5nsxC4BgRmCMjLfzioGgmngr4Seq+2uzxIj0ZWM9iQ7vmm5mXohR2mH z4Qe6CpD7F4QLQlLZR4lqJVVezAtTuJRvII8eJ6+kZBeXQsxOOEbrsoQvIijQECJWMVQ py9qfP7P8hSBBIVR+g3m4ivMadQCWxSsevJkusPFJslKkbXSfH6jt/4GEvJ0sWHtimsP xUbw== X-Gm-Message-State: AJIora+ckZQmczr8creqbcauzNYHmvvt9h8efs9938NTcMu3XDkvLVJl cZ7ky21mg5TfBBcwF5QfWWYhKOFPTF2P3DoLfXRMUStcwujr8w== X-Google-Smtp-Source: AGRyM1uI6pFImJz/Vk4LhnTK2ZTcVEWkFsgXNR8g1z9vxWgquvuE2TdN2NBNkbf9iS/35Y4rcmlxMMjZYJI+pcgkqDA= X-Received: by 2002:a05:6830:441f:b0:61c:a5bb:9c6a with SMTP id q31-20020a056830441f00b0061ca5bb9c6amr7244143otv.265.1659447091080; Tue, 02 Aug 2022 06:31:31 -0700 (PDT) MIME-Version: 1.0 References: <20220802132825.3218379-1-goldstein.w.n@gmail.com> In-Reply-To: <20220802132825.3218379-1-goldstein.w.n@gmail.com> From: Noah Goldstein Date: Tue, 2 Aug 2022 21:31:20 +0800 Message-ID: Subject: Re: [PATCH v1] stdlib: Add more room for reuse of random bits in arc4random_uniform To: GNU C Library Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-9.9 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:31:33 -0000 On Tue, Aug 2, 2022 at 9:28 PM Noah Goldstein wrote: > > The shift optimization doesn't need to clear all `z` bits. Bias is > only introduced if shift count is less than the number of leading 1s. > > I.e for n = 6, for `value & mask` to be greater than `n` the bits in > position 1/2 must be set so they must be set. But the bit in > position 0 can be 0/1 (is completely unrelated to the comparison) > so we can keep it for the next comparison only use a shift of 2. > > This patch reduces the number of expected syscalls if `n` is not a > power_of_two - 1 > --- > stdlib/arc4random_uniform.c | 8 +++++++- > 1 file changed, 7 insertions(+), 1 deletion(-) > > diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c > index 5aa98d1c13..e5c9dd04cf 100644 > --- a/stdlib/arc4random_uniform.c > +++ b/stdlib/arc4random_uniform.c > @@ -45,7 +45,13 @@ __arc4random_uniform (uint32_t n) > /* mask is the smallest power of 2 minus 1 number larger than n. */ > int z = __builtin_clz (n); > uint32_t mask = ~UINT32_C(0) >> z; > - int bits = CHAR_BIT * sizeof (uint32_t) - z; > + /* Amount of bits to shift out of value before retesting if `(value > + & mask) < n`. We want this to be as small as possible to avoid > + calling __arc4random (which has a syscall). The minimal value > + without adding bias to the result is the number of leading 1s in `n` > + starting at position `z`. popcount(n) is guaranteed to be as least > + that large and is relatively fast. */ > + int bits = __builtin_popcount (n); > > while (1) > { > -- > 2.34.1 > Thought on it a bit more. This patch is no good it will still introduce a slight amount of bias.