Debian Codegraph @

lib/util/rand.c

raw
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