prng.h revision 84f7cdb0c588322dfd50a26497fc1cb54b792018 
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 * Macro parameters:
23 *   uint32_t r          : Result.
24 *   unsigned lg_range   : (0..32], number of least significant bits to return.
25 *   uint32_t state      : Seed value.
26 *   const uint32_t a, c : See above discussion.
27 */
28#define prng32(r, lg_range, state, a, c) do {				\
29	assert(lg_range > 0);						\
30	assert(lg_range <= 32);						\
31									\
32	r = (state * (a)) + (c);					\
33	state = r;							\
34	r >>= (32 - lg_range);						\
35} while (false)
36
37/* Same as prng32(), but 64 bits of pseudo-randomness, using uint64_t. */
38#define prng64(r, lg_range, state, a, c) do {				\
39	assert(lg_range > 0);						\
40	assert(lg_range <= 64);						\
41									\
42	r = (state * (a)) + (c);					\
43	state = r;							\
44	r >>= (64 - lg_range);						\
45} while (false)
46
47#endif /* JEMALLOC_H_TYPES */
48/******************************************************************************/
49#ifdef JEMALLOC_H_STRUCTS
50
51#endif /* JEMALLOC_H_STRUCTS */
52/******************************************************************************/
53#ifdef JEMALLOC_H_EXTERNS
54
55#endif /* JEMALLOC_H_EXTERNS */
56/******************************************************************************/
57#ifdef JEMALLOC_H_INLINES
58
59#endif /* JEMALLOC_H_INLINES */
60/******************************************************************************/
61