Re: [PATCH] stdlib: Tuned down tst-arc4random-thread internal parameters

[Adhemerval Zanella Netto <adhemerval.zanella@linaro.org>]

On 27/07/22 12:36, Florian Weimer wrote:
> * Adhemerval Zanella Netto:
> 
>>>>> By the way, I think we should switch to the standard arc4random_uniform
>>>>> implementation that doesn't try to conserve bits.  It's cheaper to get a
>>>>> larger number of bits once instead of obtaining 24 bits first, then 8
>>>>> bits.
>>>>
>>>> Yeah, it should simpler indeed.  But I do not consider this urgent
>>>> for 2.36.
>>>
>>> Well, the standard way probably has more obvious statistical properties
>>> and is harder to screw up. 8-/
>>
>> Right, do you consider this a blocker? I think I can send a patch to 
>> use a simpler algorithm.
> 
> I like it because it would minimize risk.  It's not a strict blocker.
> I'm not sure if I'll be able to work on it this week.  Maybe I can
> review a patch.

Without trying to be clever, what about something like the below, adapted
from Bitmask with Rejection [1].  It should be fast on most case since it
avoid the modulo operation, and the last part that tries to reuse the
extra entropy bits are not strictly required.


uint32_t
__arc4random_uniform (uint32_t n)
{
  if (n <= 1)
    /* There is no valid return value for a zero limit, and 0 is the
       only possible result for limit 1.  */
    return 0;

  /* mask is the smallest power of 2 minus 1 which is larger than n.  */
  int z = __builtin_clz (n);
  int bits = CHAR_BIT * sizeof (uint32_t) - z;
  uint32_t mask = ~UINT32_C(0) >> z;

  while (1)
    {
      uint32_t value = __arc4random ();

      /* Return is the lower power of 2 minus 1 satisfy the condition.  */
      uint32_t r = value & mask;
      if (r < n)
        return r;

      /* Otherwise check if remaining bits of entropy provides fits in the
         bound.  */
      int bits_left = z;
      while (bits_left >= bits)
        {
          value >>= bits;
          r = value & mask;
          if (r < n)
            return r;
          bits_left -= bits;
        }
    }
}

[1] https://www.pcg-random.org/posts/bounded-rands.html