1 /*
2 * This file is part of the Yices SMT Solver.
3 * Copyright (C) 2017 SRI International.
4 *
5 * Yices 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 * Yices 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 Yices. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 /*
20 * Simple PRNG based on a linear congruence modulo 2^32.
21 *
22 * Recurrence X_{t+1} = (a X_t + b) mod 2^32
23 * - X_0 is the seed,
24 * - a = 1664525,
25 * - b = 1013904223
26 * (Source: Wikipedia + Knuth's Art of Computer Programming, Vol. 2)
27 *
28 * The low-order bits are not random.
29 *
30 * Note: the state of the PRNG (variable seed) is local.
31 * So every file that imports this will have its own copy of the PRNG,
32 * and all copies have the same default seed.
33 */
34
35 #ifndef __PRNG_H
36 #define __PRNG_H
37
38 #include <stdint.h>
39
40 #define PRNG_MULTIPLIER 1664525
41 #define PRNG_CONSTANT 1013904223
42
43 #define PRNG_DEFAULT_SEED 0xabcdef98
44
random_seed(uint32_t * seedp,uint32_t s)45 static inline void random_seed(uint32_t *seedp, uint32_t s) {
46 *seedp = s;
47 }
48
random_uint32(uint32_t * seedp)49 static inline uint32_t random_uint32(uint32_t *seedp) {
50 uint32_t x = *seedp;
51 *seedp = x * ((uint32_t) PRNG_MULTIPLIER) + ((uint32_t) PRNG_CONSTANT);
52 return x;
53 }
54
random_int32(uint32_t * seedp)55 static inline int32_t random_int32(uint32_t *seedp) {
56 return (int32_t) random_uint32(seedp);
57 }
58
59 // random integer between 0 and n-1 (remove 8 low-order bits)
random_uint(uint32_t * seedp,uint32_t n)60 static inline uint32_t random_uint(uint32_t *seedp, uint32_t n) {
61 return (random_uint32(seedp) >> 8) % n;
62 }
63
64
65 #endif
66
67
68