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