lib/randint.c

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