1 /* Generate random integers.
3 Copyright (C) 2006, 2009 Free Software Foundation, Inc.
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.
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.
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/>. */
18 /* Written by Paul Eggert. */
31 # include <inttypes.h>
35 main (int argc
, char **argv
)
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
);
43 for (i
= 0; i
< n
; i
++)
44 printf ("%"PRIuMAX
"\n", randint_choose (ints
, choices
));
46 return (randint_all_free (ints
) == 0 ? EXIT_SUCCESS
: EXIT_FAILURE
);
53 /* A source of random data for generating random integers. */
56 /* The source of random bytes. */
57 struct randread_source
*source
;
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
68 /* Create a new randint_source from SOURCE. */
70 struct randint_source
*
71 randint_new (struct randread_source
*source
)
73 struct randint_source
*s
= xmalloc (sizeof *s
);
75 s
->randnum
= s
->randmax
= 0;
79 /* Create a new randint_source by creating a randread_source from
80 NAME and ESTIMATED_BYTES. Return NULL (setting errno) if
83 struct randint_source
*
84 randint_all_new (char const *name
, size_t bytes_bound
)
86 struct randread_source
*source
= randread_new (name
, bytes_bound
);
87 return (source
? randint_new (source
) : NULL
);
90 /* Return the random data source of *S. */
92 struct randread_source
*
93 randint_get_source (struct randint_source
const *s
)
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
};
103 /* Return X shifted left by CHAR_BIT bits. */
104 static inline randint
shift_left (randint x
)
106 return HUGE_BYTES
? 0 : x
<< CHAR_BIT
;
109 /* Return X shifted right by CHAR_BIT bits. */
110 static inline randint
111 shift_right (randint x
)
113 return HUGE_BYTES
? 0 : x
>> CHAR_BIT
;
117 /* Consume random data from *S to generate a random number in the range
121 randint_genmax (struct randint_source
*s
, randint genmax
)
123 struct randread_source
*source
= s
->source
;
124 randint randnum
= s
->randnum
;
125 randint randmax
= s
->randmax
;
126 randint choices
= genmax
+ 1;
130 if (randmax
< genmax
)
132 /* Calculate how many input bytes will be needed, and read
136 randint rmax
= randmax
;
137 unsigned char buf
[sizeof randnum
];
141 rmax
= shift_left (rmax
) + UCHAR_MAX
;
144 while (rmax
< genmax
);
146 randread (source
, buf
, i
);
148 /* Increase RANDMAX by appending random bytes to RANDNUM and
149 UCHAR_MAX to RANDMAX until RANDMAX is no less than
150 GENMAX. This may lose up to CHAR_BIT bits of information
151 if shift_right (RANDINT_MAX) < GENMAX, but it is not
152 worth the programming hassle of saving these bits since
153 GENMAX is rarely that large in practice. */
159 randnum
= shift_left (randnum
) + buf
[i
];
160 randmax
= shift_left (randmax
) + UCHAR_MAX
;
163 while (randmax
< genmax
);
166 if (randmax
== genmax
)
168 s
->randnum
= s
->randmax
= 0;
173 /* GENMAX < RANDMAX, so attempt to generate a random number
174 by taking RANDNUM modulo GENMAX+1. This will choose
175 fairly so long as RANDNUM falls within an integral
176 multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM,
177 so discard this attempt and try again.
179 Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be
180 zero and there is no need to worry about dividing by
183 randint excess_choices
= randmax
- genmax
;
184 randint unusable_choices
= excess_choices
% choices
;
185 randint last_usable_choice
= randmax
- unusable_choices
;
186 randint reduced_randnum
= randnum
% choices
;
188 if (randnum
<= last_usable_choice
)
190 s
->randnum
= randnum
/ choices
;
191 s
->randmax
= excess_choices
/ choices
;
192 return reduced_randnum
;
195 /* Retry, but retain the randomness from the fact that RANDNUM fell
196 into the range LAST_USABLE_CHOICE+1 .. RANDMAX. */
197 randnum
= reduced_randnum
;
198 randmax
= unusable_choices
- 1;
203 /* Clear *S so that it no longer contains undelivered random data. */
206 randint_free (struct randint_source
*s
)
208 memset (s
, 0, sizeof *s
);
212 /* Likewise, but also clear the underlying randread object. Return
213 0 if successful, -1 (setting errno) otherwise. */
216 randint_all_free (struct randint_source
*s
)
218 int r
= randread_free (s
->source
);