1#ifndef JEMALLOC_INTERNAL_PRNG_H
2#define JEMALLOC_INTERNAL_PRNG_H
3
4#include "jemalloc/internal/bit_util.h"
5
6/*
7 * Simple linear congruential pseudo-random number generator:
8 *
9 * prng(y) = (a*x + c) % m
10 *
11 * where the following constants ensure maximal period:
12 *
13 * a == Odd number (relatively prime to 2^n), and (a-1) is a multiple of 4.
14 * c == Odd number (relatively prime to 2^n).
15 * m == 2^32
16 *
17 * See Knuth's TAOCP 3rd Ed., Vol. 2, pg. 17 for details on these constraints.
18 *
19 * This choice of m has the disadvantage that the quality of the bits is
20 * proportional to bit position. For example, the lowest bit has a cycle of 2,
21 * the next has a cycle of 4, etc. For this reason, we prefer to use the upper
22 * bits.
23 */
24
25/******************************************************************************/
26/* INTERNAL DEFINITIONS -- IGNORE */
27/******************************************************************************/
28#define PRNG_A_32 UINT32_C(1103515241)
29#define PRNG_C_32 UINT32_C(12347)
30
31#define PRNG_A_64 UINT64_C(6364136223846793005)
32#define PRNG_C_64 UINT64_C(1442695040888963407)
33
34JEMALLOC_ALWAYS_INLINE uint32_t
35prng_state_next_u32(uint32_t state) {
36 return (state * PRNG_A_32) + PRNG_C_32;
37}
38
39JEMALLOC_ALWAYS_INLINE uint64_t
40prng_state_next_u64(uint64_t state) {
41 return (state * PRNG_A_64) + PRNG_C_64;
42}
43
44JEMALLOC_ALWAYS_INLINE size_t
45prng_state_next_zu(size_t state) {
46#if LG_SIZEOF_PTR == 2
47 return (state * PRNG_A_32) + PRNG_C_32;
48#elif LG_SIZEOF_PTR == 3
49 return (state * PRNG_A_64) + PRNG_C_64;
50#else
51#error Unsupported pointer size
52#endif
53}
54
55/******************************************************************************/
56/* BEGIN PUBLIC API */
57/******************************************************************************/
58
59/*
60 * The prng_lg_range functions give a uniform int in the half-open range [0,
61 * 2**lg_range).
62 */
63
64JEMALLOC_ALWAYS_INLINE uint32_t
65prng_lg_range_u32(uint32_t *state, unsigned lg_range) {
66 assert(lg_range > 0);
67 assert(lg_range <= 32);
68
69 *state = prng_state_next_u32(*state);
70 uint32_t ret = *state >> (32 - lg_range);
71
72 return ret;
73}
74
75JEMALLOC_ALWAYS_INLINE uint64_t
76prng_lg_range_u64(uint64_t *state, unsigned lg_range) {
77 assert(lg_range > 0);
78 assert(lg_range <= 64);
79
80 *state = prng_state_next_u64(*state);
81 uint64_t ret = *state >> (64 - lg_range);
82
83 return ret;
84}
85
86JEMALLOC_ALWAYS_INLINE size_t
87prng_lg_range_zu(size_t *state, unsigned lg_range) {
88 assert(lg_range > 0);
89 assert(lg_range <= ZU(1) << (3 + LG_SIZEOF_PTR));
90
91 *state = prng_state_next_zu(*state);
92 size_t ret = *state >> ((ZU(1) << (3 + LG_SIZEOF_PTR)) - lg_range);
93
94 return ret;
95}
96
97/*
98 * The prng_range functions behave like the prng_lg_range, but return a result
99 * in [0, range) instead of [0, 2**lg_range).
100 */
101
102JEMALLOC_ALWAYS_INLINE uint32_t
103prng_range_u32(uint32_t *state, uint32_t range) {
104 assert(range != 0);
105 /*
106 * If range were 1, lg_range would be 0, so the shift in
107 * prng_lg_range_u32 would be a shift of a 32-bit variable by 32 bits,
108 * which is UB. Just handle this case as a one-off.
109 */
110 if (range == 1) {
111 return 0;
112 }
113
114 /* Compute the ceiling of lg(range). */
115 unsigned lg_range = ffs_u32(pow2_ceil_u32(range));
116
117 /* Generate a result in [0..range) via repeated trial. */
118 uint32_t ret;
119 do {
120 ret = prng_lg_range_u32(state, lg_range);
121 } while (ret >= range);
122
123 return ret;
124}
125
126JEMALLOC_ALWAYS_INLINE uint64_t
127prng_range_u64(uint64_t *state, uint64_t range) {
128 assert(range != 0);
129
130 /* See the note in prng_range_u32. */
131 if (range == 1) {
132 return 0;
133 }
134
135 /* Compute the ceiling of lg(range). */
136 unsigned lg_range = ffs_u64(pow2_ceil_u64(range));
137
138 /* Generate a result in [0..range) via repeated trial. */
139 uint64_t ret;
140 do {
141 ret = prng_lg_range_u64(state, lg_range);
142 } while (ret >= range);
143
144 return ret;
145}
146
147JEMALLOC_ALWAYS_INLINE size_t
148prng_range_zu(size_t *state, size_t range) {
149 assert(range != 0);
150
151 /* See the note in prng_range_u32. */
152 if (range == 1) {
153 return 0;
154 }
155
156 /* Compute the ceiling of lg(range). */
157 unsigned lg_range = ffs_u64(pow2_ceil_u64(range));
158
159 /* Generate a result in [0..range) via repeated trial. */
160 size_t ret;
161 do {
162 ret = prng_lg_range_zu(state, lg_range);
163 } while (ret >= range);
164
165 return ret;
166}
167
168#endif /* JEMALLOC_INTERNAL_PRNG_H */
169