1/* Generate random integers.
2
3   Copyright (C) 2006, 2009-2010 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
34int
35main (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/* A source of random data for generating random integers.  */
54struct 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
70struct randint_source *
71randint_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 NULL (setting errno) if
81   unsuccessful.  */
82
83struct randint_source *
84randint_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) : NULL);
88}
89
90/* Return the random data source of *S.  */
91
92struct randread_source *
93randint_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.  */
101enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX };
102
103/* Return X shifted left by CHAR_BIT bits.  */
104static inline randint shift_left (randint x)
105{
106  return HUGE_BYTES ? 0 : x << CHAR_BIT;
107}
108
109/* Return X shifted right by CHAR_BIT bits.  */
110static inline randint
111shift_right (randint x)
112{
113  return HUGE_BYTES ? 0 : x >> CHAR_BIT;
114}
115
116
117/* Consume random data from *S to generate a random number in the range
118   0 .. GENMAX.  */
119
120randint
121randint_genmax (struct randint_source *s, randint genmax)
122{
123  struct randread_source *source = s->source;
124  randint randnum = s->randnum;
125  randint randmax = s->randmax;
126  randint choices = genmax + 1;
127
128  for (;;)
129    {
130      if (randmax < genmax)
131        {
132          /* Calculate how many input bytes will be needed, and read
133             the bytes.  */
134
135          size_t i = 0;
136          randint rmax = randmax;
137          unsigned char buf[sizeof randnum];
138
139          do
140            {
141              rmax = shift_left (rmax) + UCHAR_MAX;
142              i++;
143            }
144          while (rmax < genmax);
145
146          randread (source, buf, i);
147
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.  */
154
155          i = 0;
156
157          do
158            {
159              randnum = shift_left (randnum) + buf[i];
160              randmax = shift_left (randmax) + UCHAR_MAX;
161              i++;
162            }
163          while (randmax < genmax);
164        }
165
166      if (randmax == genmax)
167        {
168          s->randnum = s->randmax = 0;
169          return randnum;
170        }
171      else
172        {
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.
178
179             Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be
180             zero and there is no need to worry about dividing by
181             zero.  */
182
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;
187
188          if (randnum <= last_usable_choice)
189            {
190              s->randnum = randnum / choices;
191              s->randmax = excess_choices / choices;
192              return reduced_randnum;
193            }
194
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;
199        }
200    }
201}
202
203/* Clear *S so that it no longer contains undelivered random data.  */
204
205void
206randint_free (struct randint_source *s)
207{
208  memset (s, 0, sizeof *s);
209  free (s);
210}
211
212/* Likewise, but also clear the underlying randread object.  Return
213   0 if successful, -1 (setting errno) otherwise.  */
214
215int
216randint_all_free (struct randint_source *s)
217{
218  int r = randread_free (s->source);
219  int e = errno;
220  randint_free (s);
221  errno = e;
222  return r;
223}
224