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
main(int argc,char ** argv)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 ("%ju\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 *
randint_new(struct randread_source * 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 *
randint_all_new(char const * name,size_t bytes_bound)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 *
randint_get_source(struct randint_source const * s)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.  */
shift_left(randint x)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
randint_genmax(struct randint_source * s,randint genmax)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
randint_free(struct randint_source * s)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
randint_all_free(struct randint_source * s)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 }
217