Hi Joseph,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;
}
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:
$ 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);
}
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. :)
Cheers, Alex -- <http://www.alejandro-colomar.es/>
OpenPGP_signature
Description: OpenPGP digital signature
