src/jemalloc/include/jemalloc/internal/prng.h

   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
  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
  78 #endif /* JEMALLOC_H_INLINES */
  79 /******************************************************************************/