lib/librte_eal/common/rte_random.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2019 Ericsson AB
   3  */
   4
   5 #include <stdlib.h>
   6
   7 #include <rte_branch_prediction.h>
   8 #include <rte_cycles.h>
   9 #include <rte_eal.h>
  10 #include <rte_lcore.h>
  11 #include <rte_memory.h>
  12 #include <rte_random.h>
  13
  14 struct rte_rand_state {
  15         uint64_t z1;
  16         uint64_t z2;
  17         uint64_t z3;
  18         uint64_t z4;
  19         uint64_t z5;
  20 } __rte_cache_aligned;
  21
  22 static struct rte_rand_state rand_states[RTE_MAX_LCORE];
  23
  24 static uint32_t
  25 __rte_rand_lcg32(uint32_t *seed)
  26 {
  27         *seed = 1103515245U * *seed + 12345U;
  28
  29         return *seed;
  30 }
  31
  32 static uint64_t
  33 __rte_rand_lcg64(uint32_t *seed)
  34 {
  35         uint64_t low;
  36         uint64_t high;
  37
  38         /* A 64-bit LCG would have been much cleaner, but good
  39          * multiplier/increments for such seem hard to come by.
  40          */
  41
  42         low = __rte_rand_lcg32(seed);
  43         high = __rte_rand_lcg32(seed);
  44
  45         return low | (high << 32);
  46 }
  47
  48 static uint64_t
  49 __rte_rand_lfsr258_gen_seed(uint32_t *seed, uint64_t min_value)
  50 {
  51         uint64_t res;
  52
  53         res = __rte_rand_lcg64(seed);
  54
  55         if (res < min_value)
  56                 res += min_value;
  57
  58         return res;
  59 }
  60
  61 static void
  62 __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)
  63 {
  64         uint32_t lcg_seed;
  65
  66         lcg_seed = (uint32_t)(seed ^ (seed >> 32));
  67
  68         state->z1 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 2UL);
  69         state->z2 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 512UL);
  70         state->z3 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 4096UL);
  71         state->z4 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 131072UL);
  72         state->z5 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 8388608UL);
  73 }
  74
  75 void
  76 rte_srand(uint64_t seed)
  77 {
  78         unsigned int lcore_id;
  79
  80         /* add lcore_id to seed to avoid having the same sequence */
  81         for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++)
  82                 __rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]);
  83 }
  84
  85 static __rte_always_inline uint64_t
  86 __rte_rand_lfsr258_comp(uint64_t z, uint64_t a, uint64_t b, uint64_t c,
  87                         uint64_t d)
  88 {
  89         return ((z & c) << d) ^ (((z << a) ^ z) >> b);
  90 }
  91
  92 /* Based on L’Ecuyer, P.: Tables of maximally equidistributed combined
  93  * LFSR generators.
  94  */
  95
  96 static __rte_always_inline uint64_t
  97 __rte_rand_lfsr258(struct rte_rand_state *state)
  98 {
  99         state->z1 = __rte_rand_lfsr258_comp(state->z1, 1UL, 53UL,
 100                                             18446744073709551614UL, 10UL);
 101         state->z2 = __rte_rand_lfsr258_comp(state->z2, 24UL, 50UL,
 102                                             18446744073709551104UL, 5UL);
 103         state->z3 = __rte_rand_lfsr258_comp(state->z3, 3UL, 23UL,
 104                                             18446744073709547520UL, 29UL);
 105         state->z4 = __rte_rand_lfsr258_comp(state->z4, 5UL, 24UL,
 106                                             18446744073709420544UL, 23UL);
 107         state->z5 = __rte_rand_lfsr258_comp(state->z5, 3UL, 33UL,
 108                                             18446744073701163008UL, 8UL);
 109
 110         return state->z1 ^ state->z2 ^ state->z3 ^ state->z4 ^ state->z5;
 111 }
 112
 113 static __rte_always_inline
 114 struct rte_rand_state *__rte_rand_get_state(void)
 115 {
 116         unsigned int lcore_id;
 117
 118         lcore_id = rte_lcore_id();
 119
 120         if (unlikely(lcore_id == LCORE_ID_ANY))
 121                 lcore_id = rte_get_master_lcore();
 122
 123         return &rand_states[lcore_id];
 124 }
 125
 126 uint64_t
 127 rte_rand(void)
 128 {
 129         struct rte_rand_state *state;
 130
 131         state = __rte_rand_get_state();
 132
 133         return __rte_rand_lfsr258(state);
 134 }
 135
 136 RTE_INIT(rte_rand_init)
 137 {
 138         rte_srand(rte_get_timer_cycles());
 139 }