lkml.org 
[lkml]   [2022]   [Oct]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [crng-random:jd/get_random_u32_below 24/26] include/linux/random.h:64:77: sparse: sparse: cast truncates bits from constant value (e24d4d50 becomes 50)
From
On 11/10/2022 11.59, kernel test robot wrote:

> c440408cf6901e Jason A. Donenfeld 2017-01-22 53
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 54 u32 __get_random_u32_below(u32 ceil);
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 55 /* Returns a random integer in the interval [0, ceil), with uniform distribution. */
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 56 static inline u32 get_random_u32_below(u32 ceil)
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 57 {
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 58 if (!__builtin_constant_p(ceil))
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 59 return __get_random_u32_below(ceil);
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 60
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 61 for (;;) {
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 62 if (ceil <= 1U << 8) {
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 63 u32 mult = ceil * get_random_u8();
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 @64 if (is_power_of_2(ceil) || (u8)mult >= -(__force u8)ceil % ceil)
> dbc0933c6b1d8c Jason A. Donenfeld 2022-10-08 65 return mult >> 8;

I don't have a good suggestion for how to silence sparse, but I think
the cast and unary minus here needs to be interchanged. I.e., the
condition should be

if (is_power_of_2(ceil) || (u8)mult >= ((__force u8)-ceil) % ceil)

Otherwise it fails to provide uniform distribution for ceil=11, 19, 22,
23, ... [these are the numbers that are not divisors of 2^32-2^8].

Rasmus

\
 
 \ /
  Last update: 2022-10-11 15:24    [W:0.037 / U:1.168 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site