src/vppinfra/pcg.h

   1 /*
   2  * Copyright (c) 2022 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 /*
  16  * PCG Random Number Generation for C.
  17  *
  18  * Copyright 2014-2019 Melissa O'Neill <oneill@pcg-random.org>,
  19  *                     and the PCG Project contributors.
  20  *
  21  * SPDX-License-Identifier: (Apache-2.0 OR MIT)
  22  *
  23  * Licensed under the Apache License, Version 2.0 (provided in
  24  * LICENSE-APACHE.txt and at http://www.apache.org/licenses/LICENSE-2.0)
  25  * or under the MIT license (provided in LICENSE-MIT.txt and at
  26  * http://opensource.org/licenses/MIT), at your option. This file may not
  27  * be copied, modified, or distributed except according to those terms.
  28  *
  29  * Distributed on an "AS IS" BASIS, WITHOUT WARRANTY OF ANY KIND, either
  30  * express or implied.  See your chosen license for details.
  31  *
  32  * For additional information about the PCG random number generation scheme,
  33  * visit http://www.pcg-random.org/.
  34  */
  35
  36 /* This implements the pcg64i_random_t PCG specialized generator:
  37  * https://www.pcg-random.org/using-pcg-c.html#specialized-generators
  38  * This generator produces each 64-bits output exactly once, which is
  39  * perfectly suited to generated non-repeating IVs. However, because of this
  40  * property the entire internal state is revealed with each output.
  41  * It has a 2^64 period and supports 2^63 non-overlaping streams */
  42
  43 #define clib_pcg64i_random_r  clib_pcg_setseq_64_rxs_m_xs_64_random_r
  44 #define clib_pcg64i_srandom_r clib_pcg_setseq_64_srandom_r
  45
  46 typedef struct
  47 {
  48   u64 state;
  49   u64 inc;
  50 } clib_pcg_state_setseq_64_t;
  51
  52 typedef clib_pcg_state_setseq_64_t clib_pcg64i_random_t;
  53
  54 static_always_inline void
  55 clib_pcg_setseq_64_step_r (clib_pcg_state_setseq_64_t *rng)
  56 {
  57   rng->state = rng->state * 6364136223846793005ULL + rng->inc;
  58 }
  59
  60 static_always_inline u64
  61 clib_pcg_output_rxs_m_xs_64_64 (u64 state)
  62 {
  63   u64 word =
  64     ((state >> ((state >> 59u) + 5u)) ^ state) * 12605985483714917081ull;
  65   return (word >> 43u) ^ word;
  66 }
  67
  68 static_always_inline u64
  69 clib_pcg_setseq_64_rxs_m_xs_64_random_r (clib_pcg_state_setseq_64_t *rng)
  70 {
  71   u64 oldstate = rng->state;
  72   clib_pcg_setseq_64_step_r (rng);
  73   return clib_pcg_output_rxs_m_xs_64_64 (oldstate);
  74 }
  75
  76 static_always_inline void
  77 clib_pcg_setseq_64_srandom_r (clib_pcg_state_setseq_64_t *rng, u64 initstate,
  78                               u64 initseq)
  79 {
  80   rng->state = 0U;
  81   rng->inc = (initseq << 1u) | 1u;
  82   clib_pcg_setseq_64_step_r (rng);
  83   rng->state += initstate;
  84   clib_pcg_setseq_64_step_r (rng);
  85 }