stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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/>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <https://gcc.gnu.org/pipermail/gcc/attachments/20221230/5d636cb1/attachment.sig>