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