]>
Commit | Line | Data |
---|---|---|
6f4e0fcf AZN |
1 | /* Random pseudo generator number which returns a single 32 bit value |
2 | uniformly distributed but with an upper_bound. | |
dff8da6b | 3 | Copyright (C) 2022-2024 Free Software Foundation, Inc. |
6f4e0fcf AZN |
4 | This file is part of the GNU C Library. |
5 | ||
6 | The GNU C Library is free software; you can redistribute it and/or | |
7 | modify it under the terms of the GNU Lesser General Public | |
8 | License as published by the Free Software Foundation; either | |
9 | version 2.1 of the License, or (at your option) any later version. | |
10 | ||
11 | The GNU C Library is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | Lesser General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU Lesser General Public | |
17 | License along with the GNU C Library; if not, see | |
18 | <https://www.gnu.org/licenses/>. */ | |
19 | ||
6f4e0fcf AZN |
20 | #include <stdlib.h> |
21 | #include <sys/param.h> | |
22 | ||
c622ac1b AZ |
23 | /* Return a uniformly distributed random number less than N. The algorithm |
24 | calculates a mask being the lowest power of two bounding the upper bound | |
25 | N, successively queries new random values, and rejects values outside of | |
26 | the request range. | |
6f4e0fcf | 27 | |
c622ac1b AZ |
28 | For reject values, it also tries if the remaining entropy could fit on |
29 | the asked range after range adjustment. | |
6f4e0fcf | 30 | |
c622ac1b AZ |
31 | The algorithm avoids modulo and divide operations, which might be costly |
32 | depending on the architecture. */ | |
6f4e0fcf AZN |
33 | uint32_t |
34 | __arc4random_uniform (uint32_t n) | |
35 | { | |
36 | if (n <= 1) | |
37 | /* There is no valid return value for a zero limit, and 0 is the | |
38 | only possible result for limit 1. */ | |
39 | return 0; | |
40 | ||
6f4e0fcf AZN |
41 | /* Powers of two are easy. */ |
42 | if (powerof2 (n)) | |
c622ac1b | 43 | return __arc4random () & (n - 1); |
6f4e0fcf | 44 | |
c622ac1b AZ |
45 | /* mask is the smallest power of 2 minus 1 number larger than n. */ |
46 | int z = __builtin_clz (n); | |
47 | uint32_t mask = ~UINT32_C(0) >> z; | |
48 | int bits = CHAR_BIT * sizeof (uint32_t) - z; | |
6f4e0fcf | 49 | |
c622ac1b | 50 | while (1) |
6f4e0fcf | 51 | { |
c622ac1b AZ |
52 | uint32_t value = __arc4random (); |
53 | ||
54 | /* Return if the lower power of 2 minus 1 satisfy the condition. */ | |
55 | uint32_t r = value & mask; | |
56 | if (r < n) | |
57 | return r; | |
58 | ||
59 | /* Otherwise check if remaining bits of entropy provides fits in the | |
60 | bound. */ | |
61 | for (int bits_left = z; bits_left >= bits; bits_left -= bits) | |
62 | { | |
63 | value >>= bits; | |
64 | r = value & mask; | |
65 | if (r < n) | |
66 | return r; | |
67 | } | |
6f4e0fcf AZN |
68 | } |
69 | } | |
70 | libc_hidden_def (__arc4random_uniform) | |
71 | weak_alias (__arc4random_uniform, arc4random_uniform) |