Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

Hi Yann,

On 12/30/22 21:18, Yann Droneaud wrote:

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;

     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;
}





Cheers,

Alex

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

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.

OpenPGP_signature
Description: OpenPGP digital signature