Line data Source code
1 : /* Generate random integers.
2 :
3 : Copyright (C) 2006 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 <http://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], NULL, 10);
39 : randint choices = strtoumax (argv[2], NULL, 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 : #ifndef MAX
54 : # define MAX(a,b) ((a) < (b) ? (b) : (a))
55 : #endif
56 :
57 : /* A source of random data for generating random integers. */
58 : struct randint_source
59 : {
60 : /* The source of random bytes. */
61 : struct randread_source *source;
62 :
63 : /* RANDNUM is a buffered random integer, whose information has not
64 : yet been delivered to the caller. It is uniformly distributed in
65 : the range 0 <= RANDNUM <= RANDMAX. If RANDMAX is zero, then
66 : RANDNUM must be zero (and in some sense it is not really
67 : "random"). */
68 : randint randnum;
69 : randint randmax;
70 : };
71 :
72 : /* Create a new randint_source from SOURCE. */
73 :
74 : struct randint_source *
75 103 : randint_new (struct randread_source *source)
76 : {
77 103 : struct randint_source *s = xmalloc (sizeof *s);
78 103 : s->source = source;
79 103 : s->randnum = s->randmax = 0;
80 103 : return s;
81 : }
82 :
83 : /* Create a new randint_source by creating a randread_source from
84 : NAME and ESTIMATED_BYTES. Return NULL (setting errno) if
85 : unsuccessful. */
86 :
87 : struct randint_source *
88 105 : randint_all_new (char const *name, size_t bytes_bound)
89 : {
90 105 : struct randread_source *source = randread_new (name, bytes_bound);
91 105 : return (source ? randint_new (source) : NULL);
92 : }
93 :
94 : /* Return the random data source of *S. */
95 :
96 : struct randread_source *
97 22 : randint_get_source (struct randint_source const *s)
98 : {
99 22 : return s->source;
100 : }
101 :
102 : /* HUGE_BYTES is true on hosts hosts where randint and unsigned char
103 : have the same width and where shifting by the word size therefore
104 : has undefined behavior. */
105 : enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX };
106 :
107 : /* Return X shifted left by CHAR_BIT bits. */
108 1156 : static inline randint shift_left (randint x)
109 : {
110 1156 : return HUGE_BYTES ? 0 : x << CHAR_BIT;
111 : }
112 :
113 : /* Return X shifted right by CHAR_BIT bits. */
114 : static inline randint
115 : shift_right (randint x)
116 : {
117 : return HUGE_BYTES ? 0 : x >> CHAR_BIT;
118 : }
119 :
120 :
121 : /* Consume random data from *S to generate a random number in the range
122 : 0 .. GENMAX. */
123 :
124 : randint
125 747 : randint_genmax (struct randint_source *s, randint genmax)
126 : {
127 747 : struct randread_source *source = s->source;
128 747 : randint randnum = s->randnum;
129 747 : randint randmax = s->randmax;
130 747 : randint choices = genmax + 1;
131 :
132 : for (;;)
133 : {
134 827 : if (randmax < genmax)
135 : {
136 : /* Calculate how many input bytes will be needed, and read
137 : the bytes. */
138 :
139 386 : size_t i = 0;
140 386 : randint rmax = randmax;
141 : unsigned char buf[sizeof randnum];
142 :
143 : do
144 : {
145 386 : rmax = shift_left (rmax) + UCHAR_MAX;
146 386 : i++;
147 : }
148 386 : while (rmax < genmax);
149 :
150 386 : randread (source, buf, i);
151 :
152 : /* Increase RANDMAX by appending random bytes to RANDNUM and
153 : UCHAR_MAX to RANDMAX until RANDMAX is no less than
154 : GENMAX. This may lose up to CHAR_BIT bits of information
155 : if shift_right (RANDINT_MAX) < GENMAX, but it is not
156 : worth the programming hassle of saving these bits since
157 : GENMAX is rarely that large in practice. */
158 :
159 385 : i = 0;
160 :
161 : do
162 : {
163 385 : randnum = shift_left (randnum) + buf[i];
164 385 : randmax = shift_left (randmax) + UCHAR_MAX;
165 385 : i++;
166 : }
167 385 : while (randmax < genmax);
168 : }
169 :
170 786 : if (randmax == genmax)
171 : {
172 43 : s->randnum = s->randmax = 0;
173 43 : return randnum;
174 : }
175 : else
176 : {
177 : /* GENMAX < RANDMAX, so attempt to generate a random number
178 : by taking RANDNUM modulo GENMAX+1. This will choose
179 : fairly so long as RANDNUM falls within an integral
180 : multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM,
181 : so discard this attempt and try again.
182 :
183 : Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be
184 : zero and there is no need to worry about dividing by
185 : zero. */
186 :
187 743 : randint excess_choices = randmax - genmax;
188 743 : randint unusable_choices = excess_choices % choices;
189 743 : randint last_usable_choice = randmax - unusable_choices;
190 743 : randint reduced_randnum = randnum % choices;
191 :
192 743 : if (randnum <= last_usable_choice)
193 : {
194 703 : s->randnum = randnum / choices;
195 703 : s->randmax = excess_choices / choices;
196 703 : return reduced_randnum;
197 : }
198 :
199 : /* Retry, but retain the randomness from the fact that RANDNUM fell
200 : into the range LAST_USABLE_CHOICE+1 .. RANDMAX. */
201 40 : randnum = reduced_randnum;
202 40 : randmax = unusable_choices - 1;
203 : }
204 : }
205 : }
206 :
207 : /* Clear *S so that it no longer contains undelivered random data. */
208 :
209 : void
210 76 : randint_free (struct randint_source *s)
211 : {
212 76 : memset (s, 0, sizeof *s);
213 76 : free (s);
214 76 : }
215 :
216 : /* Likewise, but also clear the underlying randread object. Return
217 : 0 if successful, -1 (setting errno) otherwise. */
218 :
219 : int
220 76 : randint_all_free (struct randint_source *s)
221 : {
222 76 : int r = randread_free (s->source);
223 76 : int e = errno;
224 76 : randint_free (s);
225 76 : errno = e;
226 76 : return r;
227 : }
|