Re: [PATCH] Give a useful meaning to arc4random_uniform(0);

["Arsen Arsenović" <arsen@aarsen.me>]

[-- Attachment #1: Type: text/plain, Size: 4705 bytes --]

Hey,

Alejandro Colomar <alx.manpages@gmail.com> writes:

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

Heh, excuse my overgeneralizing, I was talking about _uniform, which
produces values in the range of [0, n), when n==0, that's an empty
range, which is also the same range as every [x,x), which is why I used
the general case in my message.

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

Heh, indeed, the original (libbsd) definition is not very maths-y, but I
interpreted "... but less than upper_bound" as [0, n), in which case,
n==0 is invalid as you said, so that's why I suggest aborting.

Of course, that doesn't happen if the definition is changed to be
[0,n-1] in the unsigned space, yes.

Both before and after such a change, "return 0" is odd ;)

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

Right, but I see this case as one of two:

1) Zero is unintentional, abort () is desirable,
2) Zero is intentional and should mean XYZ, user should explicitly check
   for zero to do XYZ.

After all, just based on what value the expression computes to, we can't
be sure that it's what the user wanted.

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

Indeed, including a wrapper like you suggested to accompany the
arc4random APIs would be nice.

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

Thanks,
-- 
Arsen Arsenović

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 251 bytes --]