stdc_bit_ceil(3) and wrapping

[Alejandro Colomar <alx.manpages@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 1972 bytes --]

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/>

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 833 bytes --]