1/* Random pseudo generator number which returns a single 32 bit value
2 uniformly distributed but with an upper_bound.
3 Copyright (C) 2022 Free Software Foundation, Inc.
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
20#include <endian.h>
21#include <libc-lock.h>
22#include <stdlib.h>
23#include <sys/param.h>
24
25/* Return the number of bytes which cover values up to the limit. */
26__attribute__ ((const))
27static uint32_t
28byte_count (uint32_t n)
29{
30 if (n < (1U << 8))
31 return 1;
32 else if (n < (1U << 16))
33 return 2;
34 else if (n < (1U << 24))
35 return 3;
36 else
37 return 4;
38}
39
40/* Fill the lower bits of the result with randomness, according to the
41 number of bytes requested. */
42static void
43random_bytes (uint32_t *result, uint32_t byte_count)
44{
45 *result = 0;
46 unsigned char *ptr = (unsigned char *) result;
47 if (__BYTE_ORDER == __BIG_ENDIAN)
48 ptr += 4 - byte_count;
49 __arc4random_buf (ptr, byte_count);
50}
51
52uint32_t
53__arc4random_uniform (uint32_t n)
54{
55 if (n <= 1)
56 /* There is no valid return value for a zero limit, and 0 is the
57 only possible result for limit 1. */
58 return 0;
59
60 /* The bits variable serves as a source for bits. Prefetch the
61 minimum number of bytes needed. */
62 uint32_t count = byte_count (n);
63 uint32_t bits_length = count * CHAR_BIT;
64 uint32_t bits;
65 random_bytes (&bits, count);
66
67 /* Powers of two are easy. */
68 if (powerof2 (n))
69 return bits & (n - 1);
70
71 /* The general case. This algorithm follows Jérémie Lumbroso,
72 Optimal Discrete Uniform Generation from Coin Flips, and
73 Applications (2013), who credits Donald E. Knuth and Andrew
74 C. Yao, The complexity of nonuniform random number generation
75 (1976), for solving the general case.
76
77 The implementation below unrolls the initialization stage of the
78 loop, where v is less than n. */
79
80 /* Use 64-bit variables even though the intermediate results are
81 never larger than 33 bits. This ensures the code is easier to
82 compile on 64-bit architectures. */
83 uint64_t v;
84 uint64_t c;
85
86 /* Initialize v and c. v is the smallest power of 2 which is larger
87 than n.*/
88 {
89 uint32_t log2p1 = 32 - __builtin_clz (n);
90 v = 1ULL << log2p1;
91 c = bits & (v - 1);
92 bits >>= log2p1;
93 bits_length -= log2p1;
94 }
95
96 /* At the start of the loop, c is uniformly distributed within the
97 half-open interval [0, v), and v < 2n < 2**33. */
98 while (true)
99 {
100 if (v >= n)
101 {
102 /* If the candidate is less than n, accept it. */
103 if (c < n)
104 /* c is uniformly distributed on [0, n). */
105 return c;
106 else
107 {
108 /* c is uniformly distributed on [n, v). */
109 v -= n;
110 c -= n;
111 /* The distribution was shifted, so c is uniformly
112 distributed on [0, v) again. */
113 }
114 }
115 /* v < n here. */
116
117 /* Replenish the bit source if necessary. */
118 if (bits_length == 0)
119 {
120 /* Overwrite the least significant byte. */
121 random_bytes (&bits, 1);
122 bits_length = CHAR_BIT;
123 }
124
125 /* Double the range. No overflow because v < n < 2**32. */
126 v *= 2;
127 /* v < 2n here. */
128
129 /* Extract a bit and append it to c. c remains less than v and
130 thus 2**33. */
131 c = (c << 1) | (bits & 1);
132 bits >>= 1;
133 --bits_length;
134
135 /* At this point, c is uniformly distributed on [0, v) again,
136 and v < 2n < 2**33. */
137 }
138}
139libc_hidden_def (__arc4random_uniform)
140weak_alias (__arc4random_uniform, arc4random_uniform)
141