Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar <alx.manpages@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 1603 bytes --]

Hi Yann,

On 12/30/22 21:18, Yann Droneaud wrote:
> 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;
> 
>      unsigned long max = upper_bound - 1;
>      unsigned long mask = ULONG_MAX >> __builtin_clzl(max);
> 
>      do {
>          r = shadow_random();
>          r &= mask;
>      } while (r > max);
> 
>      return r;
> 


Based on some of your suggestions, I updated it to be the following:

unsigned long
shadow_random_uniform(unsigned long upper_bound)
{
	unsigned long  r, max, mask;

	max = upper_bound - 1;
	mask = bit_ceilul(upper_bound) - 1;

	do {
		r = shadow_random();
		r &= mask;  // optimization
	} while (r > max);

	return r;
}


See how upper_bound == 0 acts as if upper_bound had a value one more than the 
maximum representable value in the type, which is a nice property.


Cheers,

Alex

-- 
<http://www.alejandro-colomar.es/>

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]