* [PATCH v1] stdlib: Add more room for reuse of random bits in arc4random_uniform
@ 2022-08-02 13:28 Noah Goldstein
2022-08-02 13:31 ` Noah Goldstein
0 siblings, 1 reply; 2+ messages in thread
From: Noah Goldstein @ 2022-08-02 13:28 UTC (permalink / raw)
To: libc-alpha
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
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH v1] stdlib: Add more room for reuse of random bits in arc4random_uniform
2022-08-02 13:28 [PATCH v1] stdlib: Add more room for reuse of random bits in arc4random_uniform Noah Goldstein
@ 2022-08-02 13:31 ` Noah Goldstein
0 siblings, 0 replies; 2+ messages in thread
From: Noah Goldstein @ 2022-08-02 13:31 UTC (permalink / raw)
To: GNU C Library
On Tue, Aug 2, 2022 at 9:28 PM Noah Goldstein <goldstein.w.n@gmail.com> 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.
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2022-08-02 13:31 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-08-02 13:28 [PATCH v1] stdlib: Add more room for reuse of random bits in arc4random_uniform Noah Goldstein
2022-08-02 13:31 ` Noah Goldstein
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).