src/prng/random.c

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