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 | |
34 | JEMALLOC_ALWAYS_INLINE uint32_t |
35 | prng_state_next_u32(uint32_t state) { |
36 | return (state * PRNG_A_32) + PRNG_C_32; |
37 | } |
38 | |
39 | JEMALLOC_ALWAYS_INLINE uint64_t |
40 | prng_state_next_u64(uint64_t state) { |
41 | return (state * PRNG_A_64) + PRNG_C_64; |
42 | } |
43 | |
44 | JEMALLOC_ALWAYS_INLINE size_t |
45 | prng_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 | |
64 | JEMALLOC_ALWAYS_INLINE uint32_t |
65 | prng_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 | |
75 | JEMALLOC_ALWAYS_INLINE uint64_t |
76 | prng_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 | |
86 | JEMALLOC_ALWAYS_INLINE size_t |
87 | prng_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 | |
102 | JEMALLOC_ALWAYS_INLINE uint32_t |
103 | prng_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 | |
126 | JEMALLOC_ALWAYS_INLINE uint64_t |
127 | prng_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 | |
147 | JEMALLOC_ALWAYS_INLINE size_t |
148 | prng_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 | |