src/prng/random.c

   1 #include <stdlib.h>
   2 #include <stdint.h>
   3 #include "libc.h"
   4
   5 /*
   6 this code uses the same lagged fibonacci generator as the
   7 original bsd random implementation except for the seeding
   8 which was broken in the original
   9 */
  10
  11 static uint32_t init[] = {
  12 0x00000000,0x5851f42d,0xc0b18ccf,0xcbb5f646,
  13 0xc7033129,0x30705b04,0x20fd5db4,0x9a8b7f78,
  14 0x502959d8,0xab894868,0x6c0356a7,0x88cdb7ff,
  15 0xb477d43f,0x70a3a52b,0xa8e4baf1,0xfd8341fc,
  16 0x8ae16fd9,0x742d2f7a,0x0d1f0796,0x76035e09,
  17 0x40f7702c,0x6fa72ca5,0xaaa84157,0x58a0df74,
  18 0xc74a0364,0xae533cc4,0x04185faf,0x6de3b115,
  19 0x0cab8628,0xf043bfa4,0x398150e9,0x37521657};
  20
  21 static int n = 31;
  22 static int i = 3;
  23 static int j = 0;
  24 static uint32_t *x = init+1;
  25 static volatile int lock[2];
  26
  27 static uint32_t lcg31(uint32_t x) {
  28         return (1103515245*x + 12345) & 0x7fffffff;
  29 }
  30
  31 static uint64_t lcg64(uint64_t x) {
  32         return 6364136223846793005ull*x + 1;
  33 }
  34
  35 static void *savestate() {
  36         x[-1] = (n<<16)|(i<<8)|j;
  37         return x-1;
  38 }
  39
  40 static void loadstate(uint32_t *state) {
  41         x = state+1;
  42         n = x[-1]>>16;
  43         i = (x[-1]>>8)&0xff;
  44         j = x[-1]&0xff;
  45 }
  46
  47 static void __srandom(unsigned seed) {
  48         int k;
  49         uint64_t s = seed;
  50
  51         if (n == 0) {
  52                 x[0] = s;
  53                 return;
  54         }
  55         i = n == 31 || n == 7 ? 3 : 1;
  56         j = 0;
  57         for (k = 0; k < n; k++) {
  58                 s = lcg64(s);
  59                 x[k] = s>>32;
  60         }
  61         /* make sure x contains at least one odd number */
  62         x[0] |= 1;
  63 }
  64
  65 void srandom(unsigned seed) {
  66         LOCK(lock);
  67         __srandom(seed);
  68         UNLOCK(lock);
  69 }
  70
  71 char *initstate(unsigned seed, char *state, size_t size) {
  72         void *old;
  73
  74         if (size < 8)
  75                 return 0;
  76         LOCK(lock);
  77         old = savestate();
  78         if (size < 32)
  79                 n = 0;
  80         else if (size < 64)
  81                 n = 7;
  82         else if (size < 128)
  83                 n = 15;
  84         else if (size < 256)
  85                 n = 31;
  86         else
  87                 n = 63;
  88         x = (uint32_t*)state + 1;
  89         __srandom(seed);
  90         savestate();
  91         UNLOCK(lock);
  92         return old;
  93 }
  94
  95 char *setstate(char *state) {
  96         void *old;
  97
  98         LOCK(lock);
  99         old = savestate();
 100         loadstate((uint32_t*)state);
 101         UNLOCK(lock);
 102         return old;
 103 }
 104
 105 long random(void) {
 106         long k;
 107
 108         LOCK(lock);
 109         if (n == 0) {
 110                 k = x[0] = lcg31(x[0]);
 111                 goto end;
 112         }
 113         x[i] += x[j];
 114         k = x[i]>>1;
 115         if (++i == n)
 116                 i = 0;
 117         if (++j == n)
 118                 j = 0;
 119 end:
 120         UNLOCK(lock);
 121         return k;
 122 }