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