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

[Alejandro Colomar]

On 12/31/22 03:36, Alejandro Colomar wrote:
> 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. :)
> 
> This will work with the current implementation because powerof2(3) will
> also consider 0 as a power of 2.  See powerof2(3):
> 
>   SYNOPSIS
>         #include <sys/param.h>
> 
>         int powerof2(x);
> 
>   DESCRIPTION
>         This  macro  returns true if x is a power of 2, and false
>         otherwise.
> 
>         0 is considered a power of 2.  This can make  sense  con‐
>         sidering wrapping of unsigned integers, and has interest‐
>         ing properties.
> 
> Cc: Theo de Raadt <deraadt@theos.com>
> Cc: Todd C. Miller <Todd.Miller@sudo.ws>
> Cc: "Jason A. Donenfeld" <Jason@zx2c4.com>
> Cc: Cristian Rodríguez <crrodriguez@opensuse.org>
> Cc: Adhemerval Zanella <adhemerval.zanella@linaro.org>
> Cc: Yann Droneaud <ydroneaud@opteya.com>
> Cc: Joseph Myers <joseph@codesourcery.com>
> Signed-off-by: Alejandro Colomar <alx@kernel.org>
> ---
> 
> Hi,
> 
> I CCd Theo and Todd, because theirs is the original implementation, and
> while this is a useful feature (IMO), it wouldn't make sense to do it
> without consensus with other implementations, and especially with the
> original implementation.
> 
> I found this useful for shadow, where the existing code had a function
> that produced a "random" value within a range, but due to the bogus
> implementation, it had bias for higher values.  Implementing a *_range()
> variant in terms of *_uniform() made it really simple, but the
> *_uniform() function needed to do something useful for 0 for that to
> work.

I forgot to link to the situation mentioned above:

<https://github.com/shadow-maint/shadow/pull/624>

> 
> Cheers,
> 
> Alex
> 
>   stdlib/arc4random_uniform.c | 10 ++++------
>   1 file changed, 4 insertions(+), 6 deletions(-)
> 
> diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c
> index 5aa98d1c13..1cd52c0d1c 100644
> --- a/stdlib/arc4random_uniform.c
> +++ b/stdlib/arc4random_uniform.c
> @@ -29,15 +29,13 @@
>      the asked range after range adjustment.
>   
>      The algorithm avoids modulo and divide operations, which might be costly
> -   depending on the architecture.  */
> +   depending on the architecture.
> +
> +   0 is treated as if it were UINT32_MAX + 1, and so arc4random_uniform(0)
> +   is equivalent to arc4random().  */
>   uint32_t
>   __arc4random_uniform (uint32_t n)
>   {
> -  if (n <= 1)
> -    /* There is no valid return value for a zero limit, and 0 is the
> -       only possible result for limit 1.  */
> -    return 0;
> -
>     /* Powers of two are easy.  */
>     if (powerof2 (n))
>       return __arc4random () & (n - 1);

-- 
<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://sourceware.org/pipermail/libc-alpha/attachments/20221231/69c3630a/attachment.sig>