stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

Hi Yann,

On 12/30/22 21:18, Yann Droneaud wrote:
> Hi,
> 
> 30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" <libc-alpha@sourceware.org> a écrit:
>>
>> I'm implementing a small part of <stdbit.h> equivalent code for shadow. I need
>> stdc_bit_ceilul() for a random number generator limited to a range (you've seen
>> some of this in the glibc mailing list.
>>
>> $ grepc -tfd shadow_random_uniform
>> ./libmisc/random.c:76:
>> unsigned long
>> shadow_random_uniform(unsigned long upper_bound)
>> {
>>   unsigned long r;
>>
>>   do {
>>   r = shadow_random();
>>   r &= bit_ceil_wrapul(upper_bound) - 1; // optimization
>>   } while (r > upper_bound - 1);
>>
>>   return r;
>> }
>>
> 
> What's wrong with the following ?
> 
>      if (upper_bound < 2)
>          return 0;

If upper_bound is 1, the only valid value is 0, but if it is 0, I prefer it to 
behave as if there was no bound at all, because then it allows a function 
shadow_random_range(min, max) to be implemented as:


/*
  * Return a uniformly-distributed random number in the inclusive range:
  * [min, max]
  */
unsigned long
shadow_random_range(unsigned long min, unsigned long max)
{
	return shadow_random_uniform(max - min + 1) + min;
}


That function has no problems when max is ULONG_MAX and min is 0, which is a 
nice feature.


BTW, this is something that might be interesting for both rand(3) and 
arc4random(3) in libc, since it's something that is error-prone to roll your own 
wrapper around the *_uniform() function (for example, shadow had it biased, and 
I'm fixing it).

If you want, I could prepare a patch for glibc.

> 
>      unsigned long max = upper_bound - 1;
>      unsigned long mask = ULONG_MAX >> __builtin_clzl(max);

I hate coding these magic operations out of a function, when I can give it a 
meaningful name.  That reads to me as a magic trick that many maintainers that 
read it after me will blame me for having to parse it.

Moreover, it requires you to have the special case for 0 at the top, which I 
don't want.

> 
>      do {
>          r = shadow_random();
>          r &= mask;

Moving the calculation of the mask out of the loop is something I had in mind, yep.

I also considered reusing the remaining bits if possible, but I prefer to keep 
the code simple, even if it has a few more calls to arc4random(3) underneath.

>      } while (r > max);

Yeah, this max is more friendly than my magic -1.  Thanks! :)

> 
>      return r;
> 

Cheers,

Alex

-- 
<http://www.alejandro-colomar.es/>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <https://sourceware.org/pipermail/libc-alpha/attachments/20221230/af540bb7/attachment-0001.sig>