1 /******************************************************************************/ 2 #ifdef JEMALLOC_H_TYPES 3 4 /* 5 * Simple linear congruential pseudo-random number generator: 6 * 7 * prng(y) = (a*x + c) % m 8 * 9 * where the following constants ensure maximal period: 10 * 11 * a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4. 12 * c == Odd number (relatively prime to 2^n). 13 * m == 2^32 14 * 15 * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints. 16 * 17 * This choice of m has the disadvantage that the quality of the bits is 18 * proportional to bit position. For example, the lowest bit has a cycle of 2, 19 * the next has a cycle of 4, etc. For this reason, we prefer to use the upper 20 * bits. 21 * 22 * Macro parameters: 23 * uint32_t r : Result. 24 * unsigned lg_range : (0..32], number of least significant bits to return. 25 * uint32_t state : Seed value. 26 * const uint32_t a, c : See above discussion. 27 */ 28 #define prng32(r, lg_range, state, a, c) do { \ 29 assert((lg_range) > 0); \ 30 assert((lg_range) <= 32); \ 31 \ 32 r = (state * (a)) + (c); \ 33 state = r; \ 34 r >>= (32 - (lg_range)); \ 35 } while (false) 36 37 /* Same as prng32(), but 64 bits of pseudo-randomness, using uint64_t. */ 38 #define prng64(r, lg_range, state, a, c) do { \ 39 assert((lg_range) > 0); \ 40 assert((lg_range) <= 64); \ 41 \ 42 r = (state * (a)) + (c); \ 43 state = r; \ 44 r >>= (64 - (lg_range)); \ 45 } while (false) 46 47 #endif /* JEMALLOC_H_TYPES */ 48 /******************************************************************************/ 49 #ifdef JEMALLOC_H_STRUCTS 50 51 #endif /* JEMALLOC_H_STRUCTS */ 52 /******************************************************************************/ 53 #ifdef JEMALLOC_H_EXTERNS 54 55 #endif /* JEMALLOC_H_EXTERNS */ 56 /******************************************************************************/ 57 #ifdef JEMALLOC_H_INLINES 58 59 #endif /* JEMALLOC_H_INLINES */ 60 /******************************************************************************/ 61