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 18286866Sjasone * 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 */ 22296221Sjasone#define PRNG_A UINT64_C(6364136223846793005) 23296221Sjasone#define PRNG_C UINT64_C(1442695040888963407) 24234370Sjasone 25234370Sjasone#endif /* JEMALLOC_H_TYPES */ 26234370Sjasone/******************************************************************************/ 27234370Sjasone#ifdef JEMALLOC_H_STRUCTS 28234370Sjasone 29234370Sjasone#endif /* JEMALLOC_H_STRUCTS */ 30234370Sjasone/******************************************************************************/ 31234370Sjasone#ifdef JEMALLOC_H_EXTERNS 32234370Sjasone 33234370Sjasone#endif /* JEMALLOC_H_EXTERNS */ 34234370Sjasone/******************************************************************************/ 35234370Sjasone#ifdef JEMALLOC_H_INLINES 36234370Sjasone 37296221Sjasone#ifndef JEMALLOC_ENABLE_INLINE 38296221Sjasoneuint64_t prng_lg_range(uint64_t *state, unsigned lg_range); 39296221Sjasoneuint64_t prng_range(uint64_t *state, uint64_t range); 40296221Sjasone#endif 41296221Sjasone 42296221Sjasone#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_)) 43296221SjasoneJEMALLOC_ALWAYS_INLINE uint64_t 44296221Sjasoneprng_lg_range(uint64_t *state, unsigned lg_range) 45296221Sjasone{ 46296221Sjasone uint64_t ret; 47296221Sjasone 48296221Sjasone assert(lg_range > 0); 49296221Sjasone assert(lg_range <= 64); 50296221Sjasone 51296221Sjasone ret = (*state * PRNG_A) + PRNG_C; 52296221Sjasone *state = ret; 53296221Sjasone ret >>= (64 - lg_range); 54296221Sjasone 55296221Sjasone return (ret); 56296221Sjasone} 57296221Sjasone 58296221SjasoneJEMALLOC_ALWAYS_INLINE uint64_t 59296221Sjasoneprng_range(uint64_t *state, uint64_t range) 60296221Sjasone{ 61296221Sjasone uint64_t ret; 62296221Sjasone unsigned lg_range; 63296221Sjasone 64296221Sjasone assert(range > 1); 65296221Sjasone 66296221Sjasone /* Compute the ceiling of lg(range). */ 67296221Sjasone lg_range = ffs_u64(pow2_ceil_u64(range)) - 1; 68296221Sjasone 69296221Sjasone /* Generate a result in [0..range) via repeated trial. */ 70296221Sjasone do { 71296221Sjasone ret = prng_lg_range(state, lg_range); 72296221Sjasone } while (ret >= range); 73296221Sjasone 74296221Sjasone return (ret); 75296221Sjasone} 76296221Sjasone#endif 77296221Sjasone 78234370Sjasone#endif /* JEMALLOC_H_INLINES */ 79234370Sjasone/******************************************************************************/ 80