| 1 |
/* |
| 2 |
|
| 3 |
Pseudo-random number generator for Netpbm |
| 4 |
|
| 5 |
The interface provided herein should be flexible enough for anybody |
| 6 |
who wishes to use some other random number generator. |
| 7 |
|
| 8 |
--- |
| 9 |
|
| 10 |
If you desire to implement a different generator, or writing an original |
| 11 |
one, first take a look at the random number generator section of the |
| 12 |
GNU Scientific Library package (GSL). |
| 13 |
|
| 14 |
GNU Scientific Library |
| 15 |
https://www.gnu.org/software/gsl/ |
| 16 |
|
| 17 |
GSL Random Number Generators |
| 18 |
https://wnww.gnu.org/software/gsl/doc/html/rng.html |
| 19 |
|
| 20 |
*/ |
| 21 |
|
| 22 |
#include <stdio.h> |
| 23 |
#include <stdlib.h> |
| 24 |
#include <inttypes.h> |
| 25 |
#include <strings.h> |
| 26 |
#include <time.h> |
| 27 |
#include <float.h> |
| 28 |
#include <math.h> |
| 29 |
|
| 30 |
#include "netpbm/pm_c_util.h" |
| 31 |
#include "netpbm/mallocvar.h" |
| 32 |
#include "netpbm/pm.h" |
| 33 |
#include "netpbm/rand.h" |
| 34 |
|
| 35 |
/*----------------------------------------------------------------------------- |
| 36 |
Use |
| 37 |
------------------------------------------------------------------------------- |
| 38 |
Typical usage: |
| 39 |
|
| 40 |
#include "rand.h" |
| 41 |
|
| 42 |
... |
| 43 |
|
| 44 |
myfunction( ... , unsigned int const seed , ... ) { |
| 45 |
|
| 46 |
struct randSt; |
| 47 |
|
| 48 |
... |
| 49 |
|
| 50 |
pm_randinit(&randSt); |
| 51 |
pm_srand(&randSt, seed); // pm_srand2() is often more useful |
| 52 |
|
| 53 |
... |
| 54 |
|
| 55 |
pm_rand(&randSt); |
| 56 |
|
| 57 |
... |
| 58 |
|
| 59 |
pm_randterm(&randSt); |
| 60 |
|
| 61 |
} |
| 62 |
-----------------------------------------------------------------------------*/ |
| 63 |
|
| 64 |
|
| 65 |
|
| 66 |
/*----------------------------------------------------------------------------- |
| 67 |
Design note |
| 68 |
------------------------------------------------------------------------------- |
| 69 |
|
| 70 |
Netpbm code contains multiple instances where random numbers are used. |
| 71 |
Stock Netpbm always uses an internal pseudo-random number generator |
| 72 |
that implements the Mersenne Twister method and does not rely on any |
| 73 |
randomness facility of the operating system, but it is easy to compile |
| 74 |
an alternative version that uses the operating system function, or some |
| 75 |
other generator. |
| 76 |
|
| 77 |
The Mersenne Twister method was new to Netpbm in Netpbm 10.94 (March 2021). |
| 78 |
Before that, Netpbm used standard OS-provided facilities. |
| 79 |
|
| 80 |
Programs that use random numbers have existed in Netpbm since PBMPlus days. |
| 81 |
The system rand() function was used where randomness was required; |
| 82 |
exceptions were rare and all of them appear to be errors on the part of the |
| 83 |
original author. |
| 84 |
|
| 85 |
Although the rand() function is available in every system on which Netpbm |
| 86 |
runs, differences exist in the underlying algorithm, so that Netpbm programs |
| 87 |
produced different output on different systems even when the user specified |
| 88 |
the same random number seed. |
| 89 |
|
| 90 |
This was not considered a problem in the early days. Deterministic |
| 91 |
operation was not a feature users requested and it was impossible regardless |
| 92 |
of the random number generation method on most programs because they did not |
| 93 |
allow a user to specify a seed for the generator. |
| 94 |
|
| 95 |
This state of affairs changed as Netpbm got firmly established as a |
| 96 |
base-level system package. Security became critical for many users. A |
| 97 |
crucial component of quality control is automated regression tests (="make |
| 98 |
check"). Unpredictable behavior gets in the way of testing. One by one |
| 99 |
programs were given the -randomseed (or -seed) option to ensure reproducible |
| 100 |
results. Often this was done as new test cases were written. However, |
| 101 |
inconsistent output caused by system-level differences in rand() |
| 102 |
implementation remained a major obstacle. |
| 103 |
|
| 104 |
In 2020 the decision was made to replace all calls to rand() in the Netpbm |
| 105 |
source code with an internal random number generator. We decided to use the |
| 106 |
Mersenne Twister, which is concise, enjoys a fine reputation and is |
| 107 |
available under liberal conditions (see below.) |
| 108 |
-----------------------------------------------------------------------------*/ |
| 109 |
|
| 110 |
|
| 111 |
void |
| 112 |
pm_srand(struct pm_randSt * const randStP, |
| 113 |
unsigned int const seed) { |
| 114 |
/*---------------------------------------------------------------------------- |
| 115 |
Initialize (or "seed") the random number generation sequence with value |
| 116 |
'seed'. |
| 117 |
-----------------------------------------------------------------------------*/ |
| 118 |
pm_randinit(randStP); |
| 119 |
|
| 120 |
randStP->vtable.srand(randStP, seed); |
| 121 |
|
| 122 |
randStP->seed = seed; |
| 123 |
} |
| 124 |
|
| 125 |
|
| 126 |
|
| 127 |
void |
| 128 |
pm_srand2(struct pm_randSt * const randStP, |
| 129 |
bool const seedValid, |
| 130 |
unsigned int const seed) { |
| 131 |
/*---------------------------------------------------------------------------- |
| 132 |
Seed the random number generator. If 'seedValid' is true, use 'seed'. |
| 133 |
Otherwise, use pm_randseed(). |
| 134 |
|
| 135 |
For historical reasons pm_randseed() is defined in libpm.c rather than |
| 136 |
this source file. |
| 137 |
-----------------------------------------------------------------------------*/ |
| 138 |
pm_srand(randStP, seedValid ? seed : pm_randseed() ); |
| 139 |
|
| 140 |
} |
| 141 |
|
| 142 |
|
| 143 |
|
| 144 |
unsigned long int |
| 145 |
pm_rand(struct pm_randSt * const randStP) { |
| 146 |
/*---------------------------------------------------------------------------- |
| 147 |
An integer random number in the interval [0, randStP->max]. |
| 148 |
-----------------------------------------------------------------------------*/ |
| 149 |
return randStP->vtable.rand(randStP); |
| 150 |
} |
| 151 |
|
| 152 |
|
| 153 |
|
| 154 |
double |
| 155 |
pm_drand(struct pm_randSt * const randStP) { |
| 156 |
/*---------------------------------------------------------------------------- |
| 157 |
A floating point random number in the interval [0, 1]. |
| 158 |
|
| 159 |
Although the return value is declared as double, the actual value will have |
| 160 |
no more precision than a single call to pm_rand() provides. This is 32 bits |
| 161 |
for Mersenne Twister. |
| 162 |
-----------------------------------------------------------------------------*/ |
| 163 |
return (double) pm_rand(randStP) / randStP->max; |
| 164 |
} |
| 165 |
|
| 166 |
|
| 167 |
|
| 168 |
double |
| 169 |
pm_drand1(struct pm_randSt * const randStP) { |
| 170 |
/*---------------------------------------------------------------------------- |
| 171 |
A floating point random number in the interval [0, 1). |
| 172 |
-----------------------------------------------------------------------------*/ |
| 173 |
return (double) pm_rand(randStP) / ((double) randStP->max + 1.0); |
| 174 |
} |
| 175 |
|
| 176 |
|
| 177 |
|
| 178 |
double |
| 179 |
pm_drand2(struct pm_randSt * const randStP) { |
| 180 |
/*---------------------------------------------------------------------------- |
| 181 |
A floating point random number in the interval (0, 1). |
| 182 |
-----------------------------------------------------------------------------*/ |
| 183 |
return ((double) pm_rand(randStP) + 0.5) / ((double) randStP->max + 1.0); |
| 184 |
} |
| 185 |
|
| 186 |
|
| 187 |
|
| 188 |
void |
| 189 |
pm_gaussrand2(struct pm_randSt * const randStP, |
| 190 |
double * const r1P, |
| 191 |
double * const r2P) { |
| 192 |
/*---------------------------------------------------------------------------- |
| 193 |
Generate two Gaussian (or normally) distributed random numbers *r1P and |
| 194 |
*r2P. |
| 195 |
|
| 196 |
Mean = 0, Standard deviation = 1. |
| 197 |
|
| 198 |
This is called the Box-Muller method. |
| 199 |
|
| 200 |
For details of this algorithm and other methods for producing |
| 201 |
Gaussian random numbers see: |
| 202 |
|
| 203 |
http://www.doc.ic.ac.uk/~wl/papers/07/csur07dt.pdf |
| 204 |
-----------------------------------------------------------------------------*/ |
| 205 |
double u1, u2; |
| 206 |
|
| 207 |
u1 = pm_drand2(randStP); |
| 208 |
u2 = pm_drand1(randStP); |
| 209 |
|
| 210 |
*r1P = sqrt(-2.0 * log(u1)) * cos(2.0 * M_PI * u2); |
| 211 |
*r2P = sqrt(-2.0 * log(u1)) * sin(2.0 * M_PI * u2); |
| 212 |
} |
| 213 |
|
| 214 |
|
| 215 |
|
| 216 |
double |
| 217 |
pm_gaussrand(struct pm_randSt * const randStP) { |
| 218 |
/*---------------------------------------------------------------------------- |
| 219 |
A Gaussian (or normally) distributed random number. |
| 220 |
|
| 221 |
Mean = 0, Standard deviation = 1. |
| 222 |
|
| 223 |
If a randStP->gaussCache has a value, return that value. Otherwise call |
| 224 |
pm_gaussrand2; return one generated value, remember the other. |
| 225 |
-----------------------------------------------------------------------------*/ |
| 226 |
double retval; |
| 227 |
|
| 228 |
if (!randStP->gaussCacheValid) { |
| 229 |
pm_gaussrand2(randStP, &retval, &randStP->gaussCache); |
| 230 |
randStP->gaussCacheValid = true; |
| 231 |
} else { |
| 232 |
retval = randStP->gaussCache; |
| 233 |
randStP->gaussCacheValid = false; |
| 234 |
} |
| 235 |
|
| 236 |
return retval; |
| 237 |
} |
| 238 |
|
| 239 |
|
| 240 |
|
| 241 |
uint32_t |
| 242 |
pm_rand32(struct pm_randSt * const randStP) { |
| 243 |
/*----------------------------------------------------------------------------- |
| 244 |
Generate a 32-bit random number. |
| 245 |
-----------------------------------------------------------------------------*/ |
| 246 |
unsigned int const randMax = randStP->max; |
| 247 |
|
| 248 |
/* 'randMax is a power of 2 minus 1. Function pm_randinit() rejects |
| 249 |
generators which do not satisfy this condition. It is unlikely that |
| 250 |
such odd generators actually exist. |
| 251 |
|
| 252 |
Many system generators are known to return 31 bits (max = 2147483647 or |
| 253 |
0x7FFFFFFF). Historically, there were generators that returned only 15 |
| 254 |
bits. |
| 255 |
*/ |
| 256 |
|
| 257 |
uint32_t retval; |
| 258 |
|
| 259 |
if (randMax >= 0xFFFFFFFF) |
| 260 |
retval = pm_rand(randStP); |
| 261 |
else { |
| 262 |
uint32_t scale; |
| 263 |
|
| 264 |
retval = 0; /* Initial value */ |
| 265 |
|
| 266 |
for (scale = 0xFFFFFFFF; scale > 0; scale /= (randMax +1)) |
| 267 |
retval = retval * (randMax + 1) + pm_rand(randStP); |
| 268 |
} |
| 269 |
|
| 270 |
return retval; |
| 271 |
} |
| 272 |
|
| 273 |
|
| 274 |
|
| 275 |
void |
| 276 |
pm_randinit(struct pm_randSt * const randStP) { |
| 277 |
/*---------------------------------------------------------------------------- |
| 278 |
Initialize the random number generator. |
| 279 |
-----------------------------------------------------------------------------*/ |
| 280 |
switch (PM_RANDOM_NUMBER_GENERATOR) { |
| 281 |
case PM_RAND_SYS_RAND: |
| 282 |
randStP->vtable = pm_randsysrand_vtable; |
| 283 |
break; |
| 284 |
case PM_RAND_SYS_RANDOM: |
| 285 |
randStP->vtable = pm_randsysrandom_vtable; |
| 286 |
break; |
| 287 |
case PM_RAND_MERSENNETWISTER: |
| 288 |
randStP->vtable = pm_randmersenne_vtable; |
| 289 |
break; |
| 290 |
default: |
| 291 |
pm_error("INTERNAL ERROR: Invalid value of " |
| 292 |
"PM_RANDOM_NUMBER_GENERATOR (random number generator " |
| 293 |
"engine type): %u", PM_RANDOM_NUMBER_GENERATOR); |
| 294 |
} |
| 295 |
|
| 296 |
randStP->vtable.init(randStP); |
| 297 |
|
| 298 |
if (randStP->max == 0) |
| 299 |
pm_error("Random number generator maximum value must be positive."); |
| 300 |
else if (((long int) randStP->max & (long int) (randStP->max + 1)) != 0x0L) |
| 301 |
pm_error("Non-standard random number generator with maximum value " |
| 302 |
"%u. Cannot handle maximum values which are not powers " |
| 303 |
"of 2 minus 1", randStP->max); |
| 304 |
|
| 305 |
randStP->gaussCacheValid = false; |
| 306 |
} |
| 307 |
|
| 308 |
|
| 309 |
|
| 310 |
void |
| 311 |
pm_randterm(struct pm_randSt * const randStP) { |
| 312 |
/*---------------------------------------------------------------------------- |
| 313 |
Tear down the random number generator. |
| 314 |
-----------------------------------------------------------------------------*/ |
| 315 |
if (randStP->stateP) |
| 316 |
free(randStP->stateP); |
| 317 |
} |
| 318 |
|
| 319 |
|
| 320 |
|