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
23#define	PRNG_A_32	UINT32_C(1103515241)
24#define	PRNG_C_32	UINT32_C(12347)
25
26#define	PRNG_A_64	UINT64_C(6364136223846793005)
27#define	PRNG_C_64	UINT64_C(1442695040888963407)
28
29#endif /* JEMALLOC_H_TYPES */
30/******************************************************************************/
31#ifdef JEMALLOC_H_STRUCTS
32
33#endif /* JEMALLOC_H_STRUCTS */
34/******************************************************************************/
35#ifdef JEMALLOC_H_EXTERNS
36
37#endif /* JEMALLOC_H_EXTERNS */
38/******************************************************************************/
39#ifdef JEMALLOC_H_INLINES
40
41#ifndef JEMALLOC_ENABLE_INLINE
42uint32_t	prng_state_next_u32(uint32_t state);
43uint64_t	prng_state_next_u64(uint64_t state);
44size_t	prng_state_next_zu(size_t state);
45
46uint32_t	prng_lg_range_u32(uint32_t *state, unsigned lg_range,
47    bool atomic);
48uint64_t	prng_lg_range_u64(uint64_t *state, unsigned lg_range);
49size_t	prng_lg_range_zu(size_t *state, unsigned lg_range, bool atomic);
50
51uint32_t	prng_range_u32(uint32_t *state, uint32_t range, bool atomic);
52uint64_t	prng_range_u64(uint64_t *state, uint64_t range);
53size_t	prng_range_zu(size_t *state, size_t range, bool atomic);
54#endif
55
56#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_))
57JEMALLOC_ALWAYS_INLINE uint32_t
58prng_state_next_u32(uint32_t state)
59{
60
61	return ((state * PRNG_A_32) + PRNG_C_32);
62}
63
64JEMALLOC_ALWAYS_INLINE uint64_t
65prng_state_next_u64(uint64_t state)
66{
67
68	return ((state * PRNG_A_64) + PRNG_C_64);
69}
70
71JEMALLOC_ALWAYS_INLINE size_t
72prng_state_next_zu(size_t state)
73{
74
75#if LG_SIZEOF_PTR == 2
76	return ((state * PRNG_A_32) + PRNG_C_32);
77#elif LG_SIZEOF_PTR == 3
78	return ((state * PRNG_A_64) + PRNG_C_64);
79#else
80#error Unsupported pointer size
81#endif
82}
83
84JEMALLOC_ALWAYS_INLINE uint32_t
85prng_lg_range_u32(uint32_t *state, unsigned lg_range, bool atomic)
86{
87	uint32_t ret, state1;
88
89	assert(lg_range > 0);
90	assert(lg_range <= 32);
91
92	if (atomic) {
93		uint32_t state0;
94
95		do {
96			state0 = atomic_read_uint32(state);
97			state1 = prng_state_next_u32(state0);
98		} while (atomic_cas_uint32(state, state0, state1));
99	} else {
100		state1 = prng_state_next_u32(*state);
101		*state = state1;
102	}
103	ret = state1 >> (32 - lg_range);
104
105	return (ret);
106}
107
108/* 64-bit atomic operations cannot be supported on all relevant platforms. */
109JEMALLOC_ALWAYS_INLINE uint64_t
110prng_lg_range_u64(uint64_t *state, unsigned lg_range)
111{
112	uint64_t ret, state1;
113
114	assert(lg_range > 0);
115	assert(lg_range <= 64);
116
117	state1 = prng_state_next_u64(*state);
118	*state = state1;
119	ret = state1 >> (64 - lg_range);
120
121	return (ret);
122}
123
124JEMALLOC_ALWAYS_INLINE size_t
125prng_lg_range_zu(size_t *state, unsigned lg_range, bool atomic)
126{
127	size_t ret, state1;
128
129	assert(lg_range > 0);
130	assert(lg_range <= ZU(1) << (3 + LG_SIZEOF_PTR));
131
132	if (atomic) {
133		size_t state0;
134
135		do {
136			state0 = atomic_read_z(state);
137			state1 = prng_state_next_zu(state0);
138		} while (atomic_cas_z(state, state0, state1));
139	} else {
140		state1 = prng_state_next_zu(*state);
141		*state = state1;
142	}
143	ret = state1 >> ((ZU(1) << (3 + LG_SIZEOF_PTR)) - lg_range);
144
145	return (ret);
146}
147
148JEMALLOC_ALWAYS_INLINE uint32_t
149prng_range_u32(uint32_t *state, uint32_t range, bool atomic)
150{
151	uint32_t ret;
152	unsigned lg_range;
153
154	assert(range > 1);
155
156	/* Compute the ceiling of lg(range). */
157	lg_range = ffs_u32(pow2_ceil_u32(range)) - 1;
158
159	/* Generate a result in [0..range) via repeated trial. */
160	do {
161		ret = prng_lg_range_u32(state, lg_range, atomic);
162	} while (ret >= range);
163
164	return (ret);
165}
166
167JEMALLOC_ALWAYS_INLINE uint64_t
168prng_range_u64(uint64_t *state, uint64_t range)
169{
170	uint64_t ret;
171	unsigned lg_range;
172
173	assert(range > 1);
174
175	/* Compute the ceiling of lg(range). */
176	lg_range = ffs_u64(pow2_ceil_u64(range)) - 1;
177
178	/* Generate a result in [0..range) via repeated trial. */
179	do {
180		ret = prng_lg_range_u64(state, lg_range);
181	} while (ret >= range);
182
183	return (ret);
184}
185
186JEMALLOC_ALWAYS_INLINE size_t
187prng_range_zu(size_t *state, size_t range, bool atomic)
188{
189	size_t ret;
190	unsigned lg_range;
191
192	assert(range > 1);
193
194	/* Compute the ceiling of lg(range). */
195	lg_range = ffs_u64(pow2_ceil_u64(range)) - 1;
196
197	/* Generate a result in [0..range) via repeated trial. */
198	do {
199		ret = prng_lg_range_zu(state, lg_range, atomic);
200	} while (ret >= range);
201
202	return (ret);
203}
204#endif
205
206#endif /* JEMALLOC_H_INLINES */
207/******************************************************************************/
208