stdc_bit_ceil(3) and wrapping

[Alejandro Colomar via Gcc]

Hi Joseph,





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





$ cat lib/bit.h
#include <limits.h>


inline int leading_zerosul(unsigned long x);
inline int bit_widthul(unsigned long x);
inline int bit_ceil_wrapul(unsigned long x);


inline int
leading_zerosul(unsigned long x)
{
        return (x == 0) ? ULONG_WIDTH : __builtin_clz(x);
}


inline int
bit_widthul(unsigned long x)
{
        return ULONG_WIDTH - leading_zerosul(x);
}


/* Similar to stdc_bit_ceilul(), but wrap around instead of UB.  */
inline int
bit_ceil_wrapul(unsigned long x)
{
        return 1 << bit_widthul(x - 1);
}









Cheers,

Alex


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

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. However, I need that it doesn't have undefined behavior if it doesn't fit the type, but rather that it wraps around (as the simplest implementation would do, BTW). I've done the following: I was wondering if there was any reason to make that UB in the standard, when unsigned wrapping has always been well-defined, and this is a case that is likely to be implemented with some operation that wraps around, right? I can't imagine of an implementation that invokes UB. Moreover, as you can see, it is useful to make it wrap around in a defined way. Would you consider either or both of being more generous in the GNU implementation and guarantee wrap around, and/or suggest that the standard guarantees the wrap around? And BTW, if any of this code helps you implement that for GNU, please feel free to take it. :)

OpenPGP_signature
Description: OpenPGP digital signature