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