prng.c

// Copyright lowRISC contributors (OpenTitan project).
// Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
// All rights reserved.
// SPDX-License-Identifier: BSD-3-Clause
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
//   1. Redistributions of source code must retain the above copyright
//      notice, this list of conditions and the following disclaimer.
//
//   2. Redistributions in binary form must reproduce the above copyright
//      notice, this list of conditions and the following disclaimer in the
//      documentation and/or other materials provided with the distribution.
//
//   3. The names of its contributors may not be used to endorse or promote
//      products derived from this software without specific prior written
//      permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
// OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
#include <stddef.h>
#include <stdint.h>
 
/**
 * Mersenne Twister PRNG modified from:
 * http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/CODES/mt19937ar.c
 *
 * The code below is identical to the code at the link above except for:
 *    - Unused functions were removed,
 *    - `static` specifier was added to all remaining functions,
 *    - Data types were replaced with compatible types for consistency,
 *    - `clang-format` was run, and
 *    - `genrand_int32()` was specified as `noinline` to improve capture
 *       performance.
 */
 
/* Period parameters */
#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfUL   /* constant vector a */
#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffUL /* least significant r bits */
 
static uint32_t mt[N];       /* the array for the state vector  */
static uint32_t mti = N + 1; /* mti==N+1 means mt[N] is not initialized */
 
/* initializes mt[N] with a seed */
static void init_genrand(uint32_t s) {
  mt[0] = s & 0xffffffffUL;
  for (mti = 1; mti < N; mti++) {
    mt[mti] = (1812433253UL * (mt[mti - 1] ^ (mt[mti - 1] >> 30)) + mti);
    /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
    /* In the previous versions, MSBs of the seed affect   */
    /* only MSBs of the array mt[].                        */
    /* 2002/01/09 modified by Makoto Matsumoto             */
    mt[mti] &= 0xffffffffUL;
    /* for >32 bit machines */
  }
}
 
/* initialize by an array with array-length */
/* init_key is the array for initializing keys */
/* key_length is its length */
/* slight change for C++, 2004/2/26 */
static void init_by_array(uint32_t init_key[], uint32_t key_length) {
  uint32_t i, j, k;
  init_genrand(19650218UL);
  i = 1;
  j = 0;
  k = (N > key_length ? N : key_length);
  for (; k; k--) {
    mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1664525UL)) +
            init_key[j] + j; /* non linear */
    mt[i] &= 0xffffffffUL;   /* for WORDSIZE > 32 machines */
    i++;
    j++;
    if (i >= N) {
      mt[0] = mt[N - 1];
      i = 1;
    }
    if (j >= key_length)
      j = 0;
  }
  for (k = N - 1; k; k--) {
    mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1566083941UL)) -
            i;             /* non linear */
    mt[i] &= 0xffffffffUL; /* for WORDSIZE > 32 machines */
    i++;
    if (i >= N) {
      mt[0] = mt[N - 1];
      i = 1;
    }
  }
 
  mt[0] = 0x80000000UL; /* MSB is 1; assuring non-zero initial array */
}
 
/* generates a random number on [0,0xffffffff]-interval */
/* Note: Specified as noinline to improve capture performance. */
__attribute__((noinline)) static uint32_t genrand_int32(void) {
  uint32_t y;
  static uint32_t mag01[2] = {0x0UL, MATRIX_A};
  /* mag01[x] = x * MATRIX_A  for x=0,1 */
 
  if (mti >= N) { /* generate N words at one time */
    int32_t kk;
 
    if (mti == N + 1)       /* if init_genrand() has not been called, */
      init_genrand(5489UL); /* a default initial seed is used */
 
    for (kk = 0; kk < N - M; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
      mt[kk] = mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1UL];
    }
    for (; kk < N - 1; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
      mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
    }
    y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
    mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1UL];
 
    mti = 0;
  }
 
  y = mt[mti++];
 
  /* Tempering */
  y ^= (y >> 11);
  y ^= (y << 7) & 0x9d2c5680UL;
  y ^= (y << 15) & 0xefc60000UL;
  y ^= (y >> 18);
 
  return y;
}
 
/**
 * End of Mersenne Twister PRNG modified from:
 * http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/CODES/mt19937ar.c
 */
 
/**
 * TODO(alphan): Using MT for now as a proof of concept to minimize host-side
 * changes. We should probably replace this with a PRNG from xoshiro* family
 * for PRNGs, e.g. xoshiro128++, for better performance and less overhead.
 */
 
void prng_seed(uint32_t seed) { init_by_array(&seed, 1); }
 
uint32_t prng_rand_uint32(void) { return genrand_int32(); }
 
uint8_t prng_rand_byte(void) {
  uint32_t rand = 0;
  do {
    /**
     * Note: We shift right by 23 bits instead of 24 to match the behavior of
     * `random.randint(0, 255)` in python. This, however, is obviously less
     * efficient since it introduces a random delay for each byte.
     *
     * TODO(alphan): Use `random.randbytes()` on the host side instead of
     * `ktp.next()` and update this function to match.
     */
    rand = genrand_int32() >> 23;
  } while (rand > 255);
  return (uint8_t)rand;
}
 
void prng_rand_bytes(uint8_t *buffer, size_t buffer_len) {
  for (size_t i = 0; i < buffer_len; ++i) {
    buffer[i] = prng_rand_byte();
  }
}