[PATCH v1] stdlib: Add more room for reuse of random bits in arc4random_uniform

[Noah Goldstein]

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