contrib/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  * 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 /******************************************************************************/