pintos-os.org Git - pintos-anon/blob - src/lib/random.c

   1 #include "random.h"
   2 #include <stdbool.h>
   3 #include <stdint.h>
   4 #include "debug.h"
   5
   6 /* RC4-based pseudo-random number generator (PRNG).
   7
   8    RC4 is a stream cipher.  We're not using it here for its
   9    cryptographic properties, but because it is easy to implement
  10    and its output is plenty random for non-cryptographic
  11    purposes.
  12
  13    See http://en.wikipedia.org/wiki/RC4_(cipher) for information
  14    on RC4.*/
  15
  16 /* RC4 state. */
  17 static uint8_t s[256];          /* S[]. */
  18 static uint8_t s_i, s_j;        /* i, j. */
  19
  20 /* Already initialized? */
  21 static bool inited;
  22
  23 /* Swaps the bytes pointed to by A and B. */
  24 static inline void
  25 swap_byte (uint8_t *a, uint8_t *b)
  26 {
  27   uint8_t t = *a;
  28   *a = *b;
  29   *b = t;
  30 }
  31
  32 /* Initializes or reinitializes the PRNG with the given SEED. */
  33 void
  34 random_init (unsigned seed)
  35 {
  36   uint8_t *seedp = (uint8_t *) &seed;
  37   int i;
  38   uint8_t j;
  39
  40   if (inited)
  41     return;
  42
  43   for (i = 0; i < 256; i++)
  44     s[i] = i;
  45   for (i = j = 0; i < 256; i++)
  46     {
  47       j += s[i] + seedp[i % sizeof seed];
  48       swap_byte (s + i, s + j);
  49     }
  50
  51   s_i = s_j = 0;
  52   inited = true;
  53 }
  54
  55 /* Writes SIZE random bytes into BUF. */
  56 void
  57 random_bytes (void *buf_, size_t size)
  58 {
  59   uint8_t *buf;
  60
  61   if (!inited)
  62     random_init (0);
  63
  64   for (buf = buf_; size-- > 0; buf++)
  65     {
  66       uint8_t s_k;
  67
  68       s_i++;
  69       s_j += s[s_i];
  70       swap_byte (s + s_i, s + s_j);
  71
  72       s_k = s[s_i] + s[s_j];
  73       *buf = s[s_k];
  74     }
  75 }
  76
  77 /* Returns a pseudo-random unsigned long.
  78    Use random_ulong() % n to obtain a random number in the range
  79    0...n (exclusive). */
  80 unsigned long
  81 random_ulong (void)
  82 {
  83   unsigned long ul;
  84   random_bytes (&ul, sizeof ul);
  85   return ul;
  86 }