[CC -= Theo]

Hi Arsen,

On 1/1/23 22:37, Arsen Arsenović wrote:
> Hi,
> 
> Alejandro Colomar via Libc-alpha <libc-alpha@sourceware.org> writes:
> 
>> Special-casing it in the implementation to return 0 was useless.
>> Instead, considering 0 as the value after UINT32_MAX has the property
>> that it allows implementing the following function without any
>> special cases:
>>
>> uint32_t
>> arc4random_range(uint32_t min, uint32_t max)
>> {
>> 	return arc4random_uniform(max - min + 1) + min;
>> }
>>
>> This works for any values of min and max (as long as min <= max, of
>> course), even for (0, UINT32_MAX).
>>
>> Oh, and the implementation of arc4random_uniform(3) is now 2 lines
>> simpler. :)
> 
> While I think this is better than the original meaning, the range [n, n)
> cannot produce a (N_0) value.

I'm not sure I follow.

To clarify, the arc4random_range() function suggested above is not defined to 
produce a number in the range [min, max), but rather a number in the range [min, 
max].  So, if you call it as arc4random_range(n, n), the range requested would 
be [n, n], which has exactly one possible value.

>  For this reason, I believe the best
> behavior for this would be to abort.
> 
> Zero is wrong because it's not in [0, 0), which goes also for all values
> of [0, 2**32), but not for [0, -1] in the unsigned number space (which
> is why I'm giving it more credit than just returning zero), though
> specifying that doesn't sit easy with me, since [x, n) and [x, n-1]
> aren't necessarily equivalent.

In the unsigned number space, [x, y) behaves equivalently to [x, y-1] for the 
cases where the former is defined.  However, the former is not defined for x==y 
(and an abort would probably be the best thing to do).  The latter does work for 
x==y, due to wrap around, since it can be reinterpreted as [x, y-1+2^32].

The current definition of arc4random_uniform(3) is the former, and the 
documentation didn't even cover the fact that is has no defined behavior for 0. 
The implementation chose a special value for the undefined behavior, which 
doesn't conform to any mathematical definition of the function.

Mathematically, we could redefine the function to use the latter definition, and 
it would be legal, since it is compatible in every defined case, plus has the 
benefit of having no undefined behavior.

However, due to concerns of existing code, we should be cautious with that, and 
an abort(3) might be better.  I'd like to see some existing code if possible 
before deciding.

And if we can't make the current API behave with the latter, more generous, 
definition, we could add a new function:

uint32_t
arc4random_uniform_wrap(uint32_t upper_bound)
{
	if (upper_bound == 0)
		return arc4random();

	return arc4random_uniform(upper_bound);
}

> 
> Furthermore, should the need to rely on "return zero for empty range"
> behavior arise, an Autoconf test for arc4random_uniform (0) behavior
> would be simpler if the test program aborted, as arc4random_uniform (n)
> == 0 is quite valid, and easily could happen at configure time.
> 
> Should one needs to produce a uniformly distributed value over the full
> range of [0, 2**32), they should invoke arc4random ().

Except that the value may be calculated.

>  Moving the
> special case into a wrapper function is similarly trivial to achieve
> either of the discussed behaviors.

Yes, it would be trivial to do:

uint32_t
arc4random_range(uint32_t min, uint32_t max)
{
	if (max == min - 1)
		return arc4random();

  	return arc4random_uniform(max - min + 1) + min;
}


Although that feels to me as a sign that something's wrong in the other API, and 
that we need yet another one which we can call arc4random_below() or 
arc4random_uniform_wrap() that behaves like _uniform() but returns [0, lim-1] 
instead of [0, lim).

> 
> Of course, changing existing APIs is never easy...  At least aborts are
> easy to spot.

Yes, I think an abort(3) is probably better than returning 0.
The 0 is just an off-by-one waiting to bite someone.

> 
> Have a great night.

Have a great night too.

Cheers,
Alex

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