1 /* Generate random integers.
2
3 Copyright (C) 2006-2023 Free Software Foundation, Inc.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* Written by Paul Eggert. */
19
20 #include <config.h>
21
22 #include "randint.h"
23
24 #include <errno.h>
25 #include <limits.h>
26 #include <stdlib.h>
27 #include <string.h>
28
29
30 #if TEST
31 # include <inttypes.h>
32 # include <stdio.h>
33
34 int
35 main (int argc, char **argv)
36 {
37 randint i;
38 randint n = strtoumax (argv[1], nullptr, 10);
39 randint choices = strtoumax (argv[2], nullptr, 10);
40 char const *name = argv[3];
41 struct randint_source *ints = randint_all_new (name, SIZE_MAX);
42
43 for (i = 0; i < n; i++)
44 printf ("%"PRIuMAX"\n", randint_choose (ints, choices));
45
46 return (randint_all_free (ints) == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
47 }
48 #endif
49
50
51 #include "xalloc.h"
52
53 /* A source of random data for generating random integers. */
54 struct randint_source
55 {
56 /* The source of random bytes. */
57 struct randread_source *source;
58
59 /* RANDNUM is a buffered random integer, whose information has not
60 yet been delivered to the caller. It is uniformly distributed in
61 the range 0 <= RANDNUM <= RANDMAX. If RANDMAX is zero, then
62 RANDNUM must be zero (and in some sense it is not really
63 "random"). */
64 randint randnum;
65 randint randmax;
66 };
67
68 /* Create a new randint_source from SOURCE. */
69
70 struct randint_source *
71 randint_new (struct randread_source *source)
72 {
73 struct randint_source *s = xmalloc (sizeof *s);
74 s->source = source;
75 s->randnum = s->randmax = 0;
76 return s;
77 }
78
79 /* Create a new randint_source by creating a randread_source from
80 NAME and ESTIMATED_BYTES. Return nullptr (setting errno) if
81 unsuccessful. */
82
83 struct randint_source *
84 randint_all_new (char const *name, size_t bytes_bound)
85 {
86 struct randread_source *source = randread_new (name, bytes_bound);
87 return (source ? randint_new (source) : nullptr);
88 }
89
90 /* Return the random data source of *S. */
91
92 struct randread_source *
93 randint_get_source (struct randint_source const *s)
94 {
95 return s->source;
96 }
97
98 /* HUGE_BYTES is true on hosts hosts where randint and unsigned char
99 have the same width and where shifting by the word size therefore
100 has undefined behavior. */
101 enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX };
102
103 /* Return X shifted left by CHAR_BIT bits. */
104 static inline randint shift_left (randint x)
105 {
106 return HUGE_BYTES ? 0 : x << CHAR_BIT;
107 }
108
109
110 /* Consume random data from *S to generate a random number in the range
111 0 .. GENMAX. */
112
113 randint
114 randint_genmax (struct randint_source *s, randint genmax)
115 {
116 struct randread_source *source = s->source;
117 randint randnum = s->randnum;
118 randint randmax = s->randmax;
119 randint choices = genmax + 1;
120
121 while (1)
122 {
123 if (randmax < genmax)
124 {
125 /* Calculate how many input bytes will be needed, and read
126 the bytes. */
127
128 size_t i = 0;
129 randint rmax = randmax;
130 unsigned char buf[sizeof randnum];
131
132 do
133 {
134 rmax = shift_left (rmax) + UCHAR_MAX;
135 i++;
136 }
137 while (rmax < genmax);
138
139 randread (source, buf, i);
140
141 /* Increase RANDMAX by appending random bytes to RANDNUM and
142 UCHAR_MAX to RANDMAX until RANDMAX is no less than
143 GENMAX. This may lose up to CHAR_BIT bits of information
144 if (HUGE_BYTES ? 0 : RANDINT_MAX >> CHAR_BIT) < GENMAX,
145 but it is not worth the programming hassle of saving
146 these bits since GENMAX is rarely that large in practice. */
147
148 i = 0;
149
150 do
151 {
152 randnum = shift_left (randnum) + buf[i];
153 randmax = shift_left (randmax) + UCHAR_MAX;
154 i++;
155 }
156 while (randmax < genmax);
157 }
158
159 if (randmax == genmax)
160 {
161 s->randnum = s->randmax = 0;
162 return randnum;
163 }
164 else
165 {
166 /* GENMAX < RANDMAX, so attempt to generate a random number
167 by taking RANDNUM modulo GENMAX+1. This will choose
168 fairly so long as RANDNUM falls within an integral
169 multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM,
170 so discard this attempt and try again.
171
172 Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be
173 zero and there is no need to worry about dividing by
174 zero. */
175
176 randint excess_choices = randmax - genmax;
177 randint unusable_choices = excess_choices % choices;
178 randint last_usable_choice = randmax - unusable_choices;
179 randint reduced_randnum = randnum % choices;
180
181 if (randnum <= last_usable_choice)
182 {
183 s->randnum = randnum / choices;
184 s->randmax = excess_choices / choices;
185 return reduced_randnum;
186 }
187
188 /* Retry, but retain the randomness from the fact that RANDNUM fell
189 into the range LAST_USABLE_CHOICE+1 .. RANDMAX. */
190 randnum = reduced_randnum;
191 randmax = unusable_choices - 1;
192 }
193 }
194 }
195
196 /* Clear *S so that it no longer contains undelivered random data. */
197
198 void
199 randint_free (struct randint_source *s)
200 {
201 explicit_bzero (s, sizeof *s);
202 free (s);
203 }
204
205 /* Likewise, but also clear the underlying randread object. Return
206 0 if successful, -1 (setting errno) otherwise. */
207
208 int
209 randint_all_free (struct randint_source *s)
210 {
211 int r = randread_free (s->source);
212 int e = errno;
213 randint_free (s);
214 errno = e;
215 return r;
216 }