gl/lib/randint.c

   1 /* Generate random integers.
   2
   3    Copyright (C) 2006, 2009-2011 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 /* 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 NULL (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) : NULL);
  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 /* Return X shifted right by CHAR_BIT bits.  */
 110 static inline randint
 111 shift_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
 120 randint
 121 randint_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   while (1)
 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
 205 void
 206 randint_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
 215 int
 216 randint_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 }