Messages in this thread | | | Date | Tue, 11 Oct 2022 12:33:47 -0600 | From | "Jason A. Donenfeld" <> | Subject | Re: [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) |
| |
On Tue, Oct 11, 2022 at 03:21:44PM +0200, Rasmus Villemoes wrote: > 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].
Thanks! Note that this is an incomplete dev branch I haven't posted to the ML yet. As for the sparse error, I think I'll fix both issues at once by just doing (256 - ceil) % ceil.
Jason
| |