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
38 uint64_t prng_lg_range(uint64_t *state, unsigned lg_range);
39 uint64_t prng_range(uint64_t *state, uint64_t range);
40 #endif
41
42 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_))
43 JEMALLOC_ALWAYS_INLINE uint64_t
prng_lg_range(uint64_t * state,unsigned lg_range)44 prng_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
58 JEMALLOC_ALWAYS_INLINE uint64_t
prng_range(uint64_t * state,uint64_t range)59 prng_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