linux-kernel - Re: [RFC PATCH v1 09/50] <linux/random.h> prandom_u32

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20200328103229.132a047f@hermes.lan>
Date:   Sat, 28 Mar 2020 10:32:29 -0700
From:   Stephen Hemminger <stephen@...workplumber.org>
To:     George Spelvin <lkml@....org>
Cc:     linux-kernel@...r.kernel.org,
        Hannes Frederic Sowa <hannes@...essinduktion.org>
Subject: Re: [RFC PATCH v1 09/50] <linux/random.h> prandom_u32_max() for
 power-of-2 ranges

On Sat, 16 Mar 2019 02:32:04 -0400
George Spelvin <lkml@....org> wrote:

> +static inline u32 prandom_u32_max(u32 range)
>  {
> -	return (u32)(((u64) prandom_u32() * ep_ro) >> 32);
> +	/*
> +	 * If the range is a compile-time constant power of 2, then use
> +	 * a simple shift.  This is mathematically equivalent to the
> +	 * multiplication, but GCC 8.3 doesn't optimize that perfectly.
> +	 *
> +	 * We could do an AND with a mask, but
> +	 * 1) The shift is the same speed on a decent CPU,
> +	 * 2) It's generally smaller code (smaller immediate), and
> +	 * 3) Many PRNGs have trouble with their low-order bits;
> +	 *    using the msbits is generaly preferred.
> +	 */
> +	if (__builtin_constant_p(range) && (range & (range - 1)) == 0)
> +		return prandom_u32() / (u32)(0x100000000 / range);
> +	else
> +		return reciprocal_scale(prandom_u32(), range);


The optimization is good, but I don't thin that the compiler
is able to propogate the constant property into the function.
Did you actually check the generated code.