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

[Yann Droneaud]

Hi,

Le 27/07/2022 à 17:57, Adhemerval Zanella Netto via Libc-alpha a écrit :
>
> 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);


For the special case where n is power of two, I think it should be 
__builtin_clz (n - 1).

For example n = 8, arc4random_uniform() returns a value up to 7, but 
mask would be 0x1111, while 0x111 would have been enough.


>    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

Thanks

-- 

Yann Droneaud

OPTEYA