projects / rustc.git / blame
| Commit | Line | Data |
|---|---|---|
| 970d7e83 LB |
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 | |
| 1a4d82fc | 18 | * proportional to bit position. For example, the lowest bit has a cycle of 2, |
| 970d7e83 LB |
19 | * the next has a cycle of 4, etc. For this reason, we prefer to use the upper |
| 20 | * bits. | |
| 970d7e83 | 21 | */ |
| 54a0048b SL |
22 | #define PRNG_A UINT64_C(6364136223846793005) |
| 23 | #define PRNG_C UINT64_C(1442695040888963407) | |
| 970d7e83 LB |
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 | ||
| 54a0048b SL |
37 | #ifndef JEMALLOC_ENABLE_INLINE |
| 38 | uint64_t prng_lg_range(uint64_t *state, unsigned lg_range); | |
| 39 | uint64_t prng_range(uint64_t *state, uint64_t range); | |
| 40 | #endif | |
| 41 | ||
| 42 | #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_)) | |
| 43 | JEMALLOC_ALWAYS_INLINE uint64_t | |
| 44 | prng_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 | ||
| 58 | JEMALLOC_ALWAYS_INLINE uint64_t | |
| 59 | prng_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 | ||
| 970d7e83 LB |
78 | #endif /* JEMALLOC_H_INLINES */ |
| 79 | /******************************************************************************/ |