nsz Git - musl/blob - src/prng/random.c

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