Hi Yann, On 12/30/22 21:18, Yann Droneaud wrote:
30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" <[email protected]> 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/>
OpenPGP_signature
Description: OpenPGP digital signature
