common/include/random.h

   1 /* nbdkit
   2  * Copyright (C) 2018 Red Hat Inc.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  * * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * * Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the distribution.
  14  *
  15  * * Neither the name of Red Hat nor the names of its contributors may be
  16  * used to endorse or promote products derived from this software without
  17  * specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY RED HAT AND CONTRIBUTORS ''AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  21  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
  22  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RED HAT OR
  23  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  26  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #ifndef NBDKIT_RANDOM_H
  34 #define NBDKIT_RANDOM_H
  35
  36 #include <stdint.h>
  37
  38 /* Generate pseudo-random numbers, quickly, with explicit state.
  39  *
  40  * This is based on the xoshiro/xoroshiro generators by David Blackman
  41  * and Sebastiano Vigna (http://xoshiro.di.unimi.it/).  Specifically
  42  * the main PRNG is ‘xoshiro256** 1.0’, and the seed generator is
  43  * ‘splitmix64’.
  44  *
  45  * This does _NOT_ generate cryptographically secure random numbers
  46  * (CSPRNG) and so should not be used when cryptography or security is
  47  * required - use gcrypt if you need those.
  48  */
  49
  50 /* You can seed ‘struct random_state’ by setting the s[] elements
  51  * directly - but you must NOT set them all to zero.  Alternately if
  52  * you have a 64 bit seed, you can call xsrandom to initialize the
  53  * state.
  54  */
  55 struct random_state {
  56   uint64_t s[4];
  57 };
  58
  59 static inline uint64_t
  60 snext (uint64_t *seed)
  61 {
  62   uint64_t z = (*seed += 0x9e3779b97f4a7c15);
  63   z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
  64   z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
  65   return z ^ (z >> 31);
  66 }
  67
  68 /* Seed the random state from a 64 bit seed. */
  69 static inline void  __attribute__((__nonnull__ (2)))
  70 xsrandom (uint64_t seed, struct random_state *state)
  71 {
  72   state->s[0] = snext (&seed);
  73   state->s[1] = snext (&seed);
  74   state->s[2] = snext (&seed);
  75   state->s[3] = snext (&seed);
  76 }
  77
  78 static inline uint64_t
  79 rotl (const uint64_t x, int k)
  80 {
  81   return (x << k) | (x >> (64 - k));
  82 }
  83
  84 /* Returns 64 random bits.  Updates the state. */
  85 static inline uint64_t __attribute__((__nonnull__ (1)))
  86 xrandom (struct random_state *state)
  87 {
  88   const uint64_t result_starstar = rotl (state->s[1] * 5, 7) * 9;
  89   const uint64_t t = state->s[1] << 17;
  90
  91   state->s[2] ^= state->s[0];
  92   state->s[3] ^= state->s[1];
  93   state->s[1] ^= state->s[2];
  94   state->s[0] ^= state->s[3];
  95
  96   state->s[2] ^= t;
  97
  98   state->s[3] = rotl (state->s[3], 45);
  99
 100   return result_starstar;
 101 }
 102
 103 #endif /* NBDKIT_RANDOM_H */