[337] | 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 | }
|
---|