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