libc-top-half/musl/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 #if defined(__wasilibc_unmodified_upstream) || defined(_REENTRANT)
  27 static volatile int lock[1];
  28 volatile int *const __random_lockptr = lock;
  29 #endif
  30
  31 static uint32_t lcg31(uint32_t x) {
  32         return (1103515245*x + 12345) & 0x7fffffff;
  33 }
  34
  35 static uint64_t lcg64(uint64_t x) {
  36         return 6364136223846793005ull*x + 1;
  37 }
  38
  39 static void *savestate() {
  40         x[-1] = (n<<16)|(i<<8)|j;
  41         return x-1;
  42 }
  43
  44 static void loadstate(uint32_t *state) {
  45         x = state+1;
  46         n = x[-1]>>16;
  47         i = (x[-1]>>8)&0xff;
  48         j = x[-1]&0xff;
  49 }
  50
  51 static void __srandom(unsigned seed) {
  52         int k;
  53         uint64_t s = seed;
  54
  55         if (n == 0) {
  56                 x[0] = s;
  57                 return;
  58         }
  59         i = n == 31 || n == 7 ? 3 : 1;
  60         j = 0;
  61         for (k = 0; k < n; k++) {
  62                 s = lcg64(s);
  63                 x[k] = s>>32;
  64         }
  65         /* make sure x contains at least one odd number */
  66         x[0] |= 1;
  67 }
  68
  69 void srandom(unsigned seed) {
  70         LOCK(lock);
  71         __srandom(seed);
  72         UNLOCK(lock);
  73 }
  74
  75 char *initstate(unsigned seed, char *state, size_t size) {
  76         void *old;
  77
  78         if (size < 8)
  79                 return 0;
  80         LOCK(lock);
  81         old = savestate();
  82         if (size < 32)
  83                 n = 0;
  84         else if (size < 64)
  85                 n = 7;
  86         else if (size < 128)
  87                 n = 15;
  88         else if (size < 256)
  89                 n = 31;
  90         else
  91                 n = 63;
  92         x = (uint32_t*)state + 1;
  93         __srandom(seed);
  94         savestate();
  95         UNLOCK(lock);
  96         return old;
  97 }
  98
  99 char *setstate(char *state) {
 100         void *old;
 101
 102         LOCK(lock);
 103         old = savestate();
 104         loadstate((uint32_t*)state);
 105         UNLOCK(lock);
 106         return old;
 107 }
 108
 109 long random(void) {
 110         long k;
 111
 112         LOCK(lock);
 113         if (n == 0) {
 114                 k = x[0] = lcg31(x[0]);
 115                 goto end;
 116         }
 117         x[i] += x[j];
 118         k = x[i]>>1;
 119         if (++i == n)
 120                 i = 0;
 121         if (++j == n)
 122                 j = 0;
 123 end:
 124         UNLOCK(lock);
 125         return k;
 126 }