gl/lib/randint.c

   1 /* Generate random integers.
   2
   3    Copyright (C) 2006-2023 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 <https://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], nullptr, 10);
  39   randint choices = strtoumax (argv[2], nullptr, 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 nullptr (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) : nullptr);
  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
 110 /* Consume random data from *S to generate a random number in the range
 111    0 .. GENMAX.  */
 112
 113 randint
 114 randint_genmax (struct randint_source *s, randint genmax)
 115 {
 116   struct randread_source *source = s->source;
 117   randint randnum = s->randnum;
 118   randint randmax = s->randmax;
 119   randint choices = genmax + 1;
 120
 121   while (1)
 122     {
 123       if (randmax < genmax)
 124         {
 125           /* Calculate how many input bytes will be needed, and read
 126              the bytes.  */
 127
 128           size_t i = 0;
 129           randint rmax = randmax;
 130           unsigned char buf[sizeof randnum];
 131
 132           do
 133             {
 134               rmax = shift_left (rmax) + UCHAR_MAX;
 135               i++;
 136             }
 137           while (rmax < genmax);
 138
 139           randread (source, buf, i);
 140
 141           /* Increase RANDMAX by appending random bytes to RANDNUM and
 142              UCHAR_MAX to RANDMAX until RANDMAX is no less than
 143              GENMAX.  This may lose up to CHAR_BIT bits of information
 144              if (HUGE_BYTES ? 0 : RANDINT_MAX >> CHAR_BIT) < GENMAX,
 145              but it is not worth the programming hassle of saving
 146              these bits since GENMAX is rarely that large in practice.  */
 147
 148           i = 0;
 149
 150           do
 151             {
 152               randnum = shift_left (randnum) + buf[i];
 153               randmax = shift_left (randmax) + UCHAR_MAX;
 154               i++;
 155             }
 156           while (randmax < genmax);
 157         }
 158
 159       if (randmax == genmax)
 160         {
 161           s->randnum = s->randmax = 0;
 162           return randnum;
 163         }
 164       else
 165         {
 166           /* GENMAX < RANDMAX, so attempt to generate a random number
 167              by taking RANDNUM modulo GENMAX+1.  This will choose
 168              fairly so long as RANDNUM falls within an integral
 169              multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM,
 170              so discard this attempt and try again.
 171
 172              Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be
 173              zero and there is no need to worry about dividing by
 174              zero.  */
 175
 176           randint excess_choices = randmax - genmax;
 177           randint unusable_choices = excess_choices % choices;
 178           randint last_usable_choice = randmax - unusable_choices;
 179           randint reduced_randnum = randnum % choices;
 180
 181           if (randnum <= last_usable_choice)
 182             {
 183               s->randnum = randnum / choices;
 184               s->randmax = excess_choices / choices;
 185               return reduced_randnum;
 186             }
 187
 188           /* Retry, but retain the randomness from the fact that RANDNUM fell
 189              into the range LAST_USABLE_CHOICE+1 .. RANDMAX.  */
 190           randnum = reduced_randnum;
 191           randmax = unusable_choices - 1;
 192         }
 193     }
 194 }
 195
 196 /* Clear *S so that it no longer contains undelivered random data.  */
 197
 198 void
 199 randint_free (struct randint_source *s)
 200 {
 201   explicit_bzero (s, sizeof *s);
 202   free (s);
 203 }
 204
 205 /* Likewise, but also clear the underlying randread object.  Return
 206    0 if successful, -1 (setting errno) otherwise.  */
 207
 208 int
 209 randint_all_free (struct randint_source *s)
 210 {
 211   int r = randread_free (s->source);
 212   int e = errno;
 213   randint_free (s);
 214   errno = e;
 215   return r;
 216 }