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#define PRNG_A UINT64_C(6364136223846793005) 23#define PRNG_C UINT64_C(1442695040888963407) 24 25#endif /* JEMALLOC_H_TYPES */ 26/******************************************************************************/ 27#ifdef JEMALLOC_H_STRUCTS 28 29#endif /* JEMALLOC_H_STRUCTS */ 30/******************************************************************************/ 31#ifdef JEMALLOC_H_EXTERNS 32 33#endif /* JEMALLOC_H_EXTERNS */ 34/******************************************************************************/ 35#ifdef JEMALLOC_H_INLINES 36 37#ifndef JEMALLOC_ENABLE_INLINE 38uint64_t prng_lg_range(uint64_t *state, unsigned lg_range); 39uint64_t prng_range(uint64_t *state, uint64_t range); 40#endif 41 42#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_)) 43JEMALLOC_ALWAYS_INLINE uint64_t 44prng_lg_range(uint64_t *state, unsigned lg_range) 45{ 46 uint64_t ret; 47 48 assert(lg_range > 0); 49 assert(lg_range <= 64); 50 51 ret = (*state * PRNG_A) + PRNG_C; 52 *state = ret; 53 ret >>= (64 - lg_range); 54 55 return (ret); 56} 57 58JEMALLOC_ALWAYS_INLINE uint64_t 59prng_range(uint64_t *state, uint64_t range) 60{ 61 uint64_t ret; 62 unsigned lg_range; 63 64 assert(range > 1); 65 66 /* Compute the ceiling of lg(range). */ 67 lg_range = ffs_u64(pow2_ceil_u64(range)) - 1; 68 69 /* Generate a result in [0..range) via repeated trial. */ 70 do { 71 ret = prng_lg_range(state, lg_range); 72 } while (ret >= range); 73 74 return (ret); 75} 76#endif 77 78#endif /* JEMALLOC_H_INLINES */ 79/******************************************************************************/ 80