stdc_bit_ceil(3) and wrapping

stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

[-- 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 --]

Re: stdc_bit_ceil(3) and wrapping

[Yann Droneaud]

Hi,

30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" <libc-alpha@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;

> 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. :)
> 

-- 
Yann Droneaud
OPTEYA

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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

Hi Yann,

On 12/30/22 21:18, Yann Droneaud wrote:
> Hi,
> 
> 30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" <libc-alpha@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;

If upper_bound is 1, the only valid value is 0, but if it is 0, I prefer it to 
behave as if there was no bound at all, because then it allows a function 
shadow_random_range(min, max) to be implemented as:


/*
  * Return a uniformly-distributed random number in the inclusive range:
  * [min, max]
  */
unsigned long
shadow_random_range(unsigned long min, unsigned long max)
{
	return shadow_random_uniform(max - min + 1) + min;
}


That function has no problems when max is ULONG_MAX and min is 0, which is a 
nice feature.


BTW, this is something that might be interesting for both rand(3) and 
arc4random(3) in libc, since it's something that is error-prone to roll your own 
wrapper around the *_uniform() function (for example, shadow had it biased, and 
I'm fixing it).

If you want, I could prepare a patch for glibc.

> 
>      unsigned long max = upper_bound - 1;
>      unsigned long mask = ULONG_MAX >> __builtin_clzl(max);

I hate coding these magic operations out of a function, when I can give it a 
meaningful name.  That reads to me as a magic trick that many maintainers that 
read it after me will blame me for having to parse it.

Moreover, it requires you to have the special case for 0 at the top, which I 
don't want.

> 
>      do {
>          r = shadow_random();
>          r &= mask;

Moving the calculation of the mask out of the loop is something I had in mind, yep.

I also considered reusing the remaining bits if possible, but I prefer to keep 
the code simple, even if it has a few more calls to arc4random(3) underneath.

>      } while (r > max);

Yeah, this max is more friendly than my magic -1.  Thanks! :)

> 
>      return r;
> 

Cheers,

Alex

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

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

Re: stdc_bit_ceil(3) and wrapping

[Joseph Myers]

On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:

> 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

It's likely to be implemented by a shift, that might be by the number of 
bits in the argument in the overflow case, and shift by the width of the 
argument is undefined behavior; some architectures wrap the shift count 
modulo the width (do you actually want 1 or 0 as the result of 
stdc_bit_ceil?), some wrap the shift count modulo a larger value (e.g. 
treating 1 << 32 as 0 but 1 << 64 as 1) and for some architectures the 
result depends on the particular shift instruction used (meaning undefined 
behavior on the form of the result of an integer expression possibly 
comparing unequal to itself because the compiler duplicated the expression 
and then used different instructions to compute it in different places).

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

The CD ballot has closed, and this doesn't appear to be one of the 338 
comments raised on that ballot, and I don't really expect time at next 
month's meeting to deal with additional technical comments not on that 
list, when we have only 15 hours to deal with 338 comments.  Once we have 
an issue tracking process for the C standard again (hopefully involving an 
issue tracker that the public can readily submit issues in), I'd suggest 
raising such concerns there (unless there's a CD2 ballot; technical 
comments are best avoided at a DIS ballot if possible).

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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

Hi Joseph,

On 12/30/22 21:38, Joseph Myers wrote:
> On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:
> 
>> 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
> 
> It's likely to be implemented by a shift, that might be by the number of
> bits in the argument in the overflow case, and shift by the width of the
> argument is undefined behavior; some architectures wrap the shift count
> modulo the width (do you actually want 1 or 0 as the result of
> stdc_bit_ceil?), some wrap the shift count modulo a larger value (e.g.
> treating 1 << 32 as 0 but 1 << 64 as 1) and for some architectures the
> result depends on the particular shift instruction used (meaning undefined
> behavior on the form of the result of an integer expression possibly
> comparing unequal to itself because the compiler duplicated the expression
> and then used different instructions to compute it in different places).

For the C standard, shifts have wrap around semantics for unsigned types:

C2x(N3054)::6.5.7p4:

"
The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are 
filled with zeros.  If E1 has an unsigned type, the value of the result is E1 × 
2E2, wrapped around.  [...]
"

Which reminds me that I forgot to use 1ul << ...

Since the <stdbit.h> functions are only provided for unsigned types, there 
should be no problems, right?

> 
>> 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?
> 
> The CD ballot has closed, and this doesn't appear to be one of the 338
> comments raised on that ballot, and I don't really expect time at next
> month's meeting to deal with additional technical comments not on that
> list, when we have only 15 hours to deal with 338 comments.  Once we have
> an issue tracking process for the C standard again (hopefully involving an
> issue tracker that the public can readily submit issues in),

Hopefully.  And a public git repository and mailing list would be awesome  :)

*comes back to reality*

> I'd suggest
> raising such concerns there (unless there's a CD2 ballot; technical
> comments are best avoided at a DIS ballot if possible).

Ahh, no problem.  If it's something to be suggested for C3x or for a small C2y 
fix (like C17 was), that would be fine.

Cheers,

Alex


> 

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

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

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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

Hi Yann,

On 12/30/22 21:18, Yann Droneaud wrote:
> 30 décembre 2022 à 20:55 "Alejandro Colomar via Libc-alpha" <libc-alpha@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;
}


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.


Cheers,

Alex

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

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

Re: stdc_bit_ceil(3) and wrapping

[Joseph Myers]

On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:

> For the C standard, shifts have wrap around semantics for unsigned types:

Only if the shift count is nonnegative and strictly less than the width of 
the type.  This is about shifting by an amount equal to the width of the 
type, which has undefined behavior.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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

On 12/30/22 21:56, Joseph Myers wrote:
> On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:
> 
>> For the C standard, shifts have wrap around semantics for unsigned types:
> 
> Only if the shift count is nonnegative and strictly less than the width of
> the type.  This is about shifting by an amount equal to the width of the
> type, which has undefined behavior.

Ahhh, right, I forgot that detail.  Yep, I need to special-case then.

Thanks!



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

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

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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

On 12/30/22 22:01, Alejandro Colomar wrote:
> On 12/30/22 21:56, Joseph Myers wrote:
>> On Fri, 30 Dec 2022, Alejandro Colomar via Gcc wrote:
>>
>>> For the C standard, shifts have wrap around semantics for unsigned types:
>>
>> Only if the shift count is nonnegative and strictly less than the width of
>> the type.  This is about shifting by an amount equal to the width of the
>> type, which has undefined behavior.
> 
> Ahhh, right, I forgot that detail.  Yep, I need to special-case then.
> 
> Thanks!
> 
> 
> 

This should work, I guess (and hopefully, the compiler will remove the special 
case in platforms that don't need it):


$ 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)
{
	int b;

	b = bit_widthul(x - 1);

	return b < ULONG_WIDTH ? 1ul << b : 0;
}


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

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

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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

Hi Yann,

On 12/30/22 21:33, Alejandro Colomar wrote:
> On 12/30/22 21:18, Yann Droneaud wrote:
>> What's wrong with the following ?

[...]

> 
>>
>>      unsigned long max = upper_bound - 1;
>>      unsigned long mask = ULONG_MAX >> __builtin_clzl(max);
> 
> I hate coding these magic operations out of a function, when I can give it a 
> meaningful name.  That reads to me as a magic trick that many maintainers that 
> read it after me will blame me for having to parse it.
> 
> Moreover, it requires you to have the special case for 0 at the top, which I 
> don't want.

I reconsidered; my -1 was equally magic.  And by calling it 'mask',
ULONG_MAX >> n is something not so magic.

The builtin still has the problem that it requires special-casing 0, so I prefer 
the C23 call, which provides the behavior I want for 0:


unsigned long
shadow_random_uniform(unsigned long upper_bound)
{
	unsigned long  r, max, mask;

	max = upper_bound - 1;
	mask = ULONG_MAX >> leading_zerosul(max);

	do {
		r = shadow_random();
		r &= mask;  // optimization
	} while (r > max);

	return r;
}


And, now I don't need to add a wrapper around bit_ceil() that removes the UB. 
stdc_leading_zerosul() is just fine for this use case.

Cheers,

Alex

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

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

Re: stdc_bit_ceil(3) and wrapping

[Alejandro Colomar]

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



On 12/30/22 23:33, Alejandro Colomar wrote:
> Hi Yann,
> 
> On 12/30/22 21:33, Alejandro Colomar wrote:
>> On 12/30/22 21:18, Yann Droneaud wrote:
>>> What's wrong with the following ?
> 
> [...]
> 
>>
>>>
>>>      unsigned long max = upper_bound - 1;
>>>      unsigned long mask = ULONG_MAX >> __builtin_clzl(max);
>>
>> I hate coding these magic operations out of a function, when I can give it a 
>> meaningful name.  That reads to me as a magic trick that many maintainers that 
>> read it after me will blame me for having to parse it.
>>
>> Moreover, it requires you to have the special case for 0 at the top, which I 
>> don't want.
> 
> I reconsidered; my -1 was equally magic.  And by calling it 'mask',
> ULONG_MAX >> n is something not so magic.
> 
> The builtin still has the problem that it requires special-casing 0, so I prefer 
> the C23 call, which provides the behavior I want for 0:
> 
> 
> unsigned long
> shadow_random_uniform(unsigned long upper_bound)
> {
>      unsigned long  r, max, mask;
> 
>      max = upper_bound - 1;
>      mask = ULONG_MAX >> leading_zerosul(max);

I just realized that this isn't good either.  Shifting right still has undefined 
behavior for max = 0.  I'll fall back to my original plan.

> 
>      do {
>          r = shadow_random();
>          r &= mask;  // optimization
>      } while (r > max);
> 
>      return r;
> }
> 
> 
> And, now I don't need to add a wrapper around bit_ceil() that removes the UB. 
> stdc_leading_zerosul() is just fine for this use case.
> 
> Cheers,
> 
> Alex
> 

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

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