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 | }
|
---|