1234370Sjasone/******************************************************************************/ 2234370Sjasone#ifdef JEMALLOC_H_TYPES 3234370Sjasone 4234370Sjasone/* 5234370Sjasone * Simple linear congruential pseudo-random number generator: 6234370Sjasone * 7234370Sjasone * prng(y) = (a*x + c) % m 8234370Sjasone * 9234370Sjasone * where the following constants ensure maximal period: 10234370Sjasone * 11234370Sjasone * a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4. 12234370Sjasone * c == Odd number (relatively prime to 2^n). 13234370Sjasone * m == 2^32 14234370Sjasone * 15234370Sjasone * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints. 16234370Sjasone * 17234370Sjasone * This choice of m has the disadvantage that the quality of the bits is 18234370Sjasone * proportional to bit position. For example. the lowest bit has a cycle of 2, 19234370Sjasone * the next has a cycle of 4, etc. For this reason, we prefer to use the upper 20234370Sjasone * bits. 21234370Sjasone * 22234370Sjasone * Macro parameters: 23234370Sjasone * uint32_t r : Result. 24234370Sjasone * unsigned lg_range : (0..32], number of least significant bits to return. 25234370Sjasone * uint32_t state : Seed value. 26234370Sjasone * const uint32_t a, c : See above discussion. 27234370Sjasone */ 28234370Sjasone#define prng32(r, lg_range, state, a, c) do { \ 29234370Sjasone assert(lg_range > 0); \ 30234370Sjasone assert(lg_range <= 32); \ 31234370Sjasone \ 32234370Sjasone r = (state * (a)) + (c); \ 33234370Sjasone state = r; \ 34234370Sjasone r >>= (32 - lg_range); \ 35234370Sjasone} while (false) 36234370Sjasone 37234370Sjasone/* Same as prng32(), but 64 bits of pseudo-randomness, using uint64_t. */ 38234370Sjasone#define prng64(r, lg_range, state, a, c) do { \ 39234370Sjasone assert(lg_range > 0); \ 40234370Sjasone assert(lg_range <= 64); \ 41234370Sjasone \ 42234370Sjasone r = (state * (a)) + (c); \ 43234370Sjasone state = r; \ 44234370Sjasone r >>= (64 - lg_range); \ 45234370Sjasone} while (false) 46234370Sjasone 47234370Sjasone#endif /* JEMALLOC_H_TYPES */ 48234370Sjasone/******************************************************************************/ 49234370Sjasone#ifdef JEMALLOC_H_STRUCTS 50234370Sjasone 51234370Sjasone#endif /* JEMALLOC_H_STRUCTS */ 52234370Sjasone/******************************************************************************/ 53234370Sjasone#ifdef JEMALLOC_H_EXTERNS 54234370Sjasone 55234370Sjasone#endif /* JEMALLOC_H_EXTERNS */ 56234370Sjasone/******************************************************************************/ 57234370Sjasone#ifdef JEMALLOC_H_INLINES 58234370Sjasone 59234370Sjasone#endif /* JEMALLOC_H_INLINES */ 60234370Sjasone/******************************************************************************/ 61