2 * random.c: Internal random number generator, guaranteed to work
3 * the same way on all platforms. Used when generating an initial
4 * game state from a random game seed; required to ensure that game
5 * seeds can be exchanged between versions of a puzzle compiled for
8 * The generator is based on SHA-1. This is almost certainly
9 * overkill, but I had the SHA-1 code kicking around and it was
10 * easier to reuse it than to do anything else!
17 typedef unsigned long uint32
;
21 unsigned char block
[64];
26 /* ----------------------------------------------------------------------
27 * Core SHA algorithm: processes 16-word blocks into a message digest.
30 #define rol(x,y) ( ((x) << (y)) | (((uint32)x) >> (32-y)) )
32 static void SHA_Core_Init(uint32 h
[5])
41 static void SHATransform(uint32
* digest
, uint32
* block
)
47 for (t
= 0; t
< 16; t
++)
50 for (t
= 16; t
< 80; t
++) {
51 uint32 tmp
= w
[t
- 3] ^ w
[t
- 8] ^ w
[t
- 14] ^ w
[t
- 16];
61 for (t
= 0; t
< 20; t
++) {
63 rol(a
, 5) + ((b
& c
) | (d
& ~b
)) + e
+ w
[t
] + 0x5a827999;
70 for (t
= 20; t
< 40; t
++) {
71 uint32 tmp
= rol(a
, 5) + (b
^ c
^ d
) + e
+ w
[t
] + 0x6ed9eba1;
78 for (t
= 40; t
< 60; t
++) {
80 5) + ((b
& c
) | (b
& d
) | (c
& d
)) + e
+ w
[t
] +
88 for (t
= 60; t
< 80; t
++) {
89 uint32 tmp
= rol(a
, 5) + (b
^ c
^ d
) + e
+ w
[t
] + 0xca62c1d6;
104 /* ----------------------------------------------------------------------
105 * Outer SHA algorithm: take an arbitrary length byte string,
106 * convert it into 16-word blocks with the prescribed padding at
107 * the end, and pass those blocks to the core SHA algorithm.
110 static void SHA_Init(SHA_State
* s
)
114 s
->lenhi
= s
->lenlo
= 0;
117 static void SHA_Bytes(SHA_State
* s
, void *p
, int len
)
119 unsigned char *q
= (unsigned char *) p
;
120 uint32 wordblock
[16];
125 * Update the length field.
128 s
->lenhi
+= (s
->lenlo
< lenw
);
130 if (s
->blkused
&& s
->blkused
+ len
< 64) {
132 * Trivial case: just add to the block.
134 memcpy(s
->block
+ s
->blkused
, q
, len
);
138 * We must complete and process at least one block.
140 while (s
->blkused
+ len
>= 64) {
141 memcpy(s
->block
+ s
->blkused
, q
, 64 - s
->blkused
);
142 q
+= 64 - s
->blkused
;
143 len
-= 64 - s
->blkused
;
144 /* Now process the block. Gather bytes big-endian into words */
145 for (i
= 0; i
< 16; i
++) {
147 (((uint32
) s
->block
[i
* 4 + 0]) << 24) |
148 (((uint32
) s
->block
[i
* 4 + 1]) << 16) |
149 (((uint32
) s
->block
[i
* 4 + 2]) << 8) |
150 (((uint32
) s
->block
[i
* 4 + 3]) << 0);
152 SHATransform(s
->h
, wordblock
);
155 memcpy(s
->block
, q
, len
);
160 static void SHA_Final(SHA_State
* s
, unsigned char *output
)
167 if (s
->blkused
>= 56)
168 pad
= 56 + 64 - s
->blkused
;
170 pad
= 56 - s
->blkused
;
172 lenhi
= (s
->lenhi
<< 3) | (s
->lenlo
>> (32 - 3));
173 lenlo
= (s
->lenlo
<< 3);
177 SHA_Bytes(s
, &c
, pad
);
179 c
[0] = (lenhi
>> 24) & 0xFF;
180 c
[1] = (lenhi
>> 16) & 0xFF;
181 c
[2] = (lenhi
>> 8) & 0xFF;
182 c
[3] = (lenhi
>> 0) & 0xFF;
183 c
[4] = (lenlo
>> 24) & 0xFF;
184 c
[5] = (lenlo
>> 16) & 0xFF;
185 c
[6] = (lenlo
>> 8) & 0xFF;
186 c
[7] = (lenlo
>> 0) & 0xFF;
190 for (i
= 0; i
< 5; i
++) {
191 output
[i
* 4] = (s
->h
[i
] >> 24) & 0xFF;
192 output
[i
* 4 + 1] = (s
->h
[i
] >> 16) & 0xFF;
193 output
[i
* 4 + 2] = (s
->h
[i
] >> 8) & 0xFF;
194 output
[i
* 4 + 3] = (s
->h
[i
]) & 0xFF;
198 static void SHA_Simple(void *p
, int len
, unsigned char *output
)
203 SHA_Bytes(&s
, p
, len
);
204 SHA_Final(&s
, output
);
207 /* ----------------------------------------------------------------------
208 * The random number generator.
211 struct random_state
{
212 unsigned char seedbuf
[40];
213 unsigned char databuf
[20];
217 random_state
*random_init(char *seed
, int len
)
221 state
= snew(random_state
);
223 SHA_Simple(seed
, len
, state
->seedbuf
);
224 SHA_Simple(state
->seedbuf
, 20, state
->seedbuf
+ 20);
225 SHA_Simple(state
->seedbuf
, 40, state
->databuf
);
231 unsigned long random_bits(random_state
*state
, int bits
)
236 for (n
= 0; n
< bits
; n
+= 8) {
237 if (state
->pos
>= 20) {
240 for (i
= 0; i
< 20; i
++) {
241 if (state
->seedbuf
[i
] != 0xFF) {
245 state
->seedbuf
[i
] = 0;
247 SHA_Simple(state
->seedbuf
, 40, state
->databuf
);
250 ret
= (ret
<< 8) | state
->databuf
[state
->pos
++];
253 ret
&= (1 << bits
) - 1;
257 unsigned long random_upto(random_state
*state
, unsigned long limit
)
260 unsigned long max
, divisor
, data
;
262 while ((limit
>> bits
) != 0)
269 divisor
= max
/ limit
;
270 max
= limit
* divisor
;
273 data
= random_bits(state
, bits
);
274 } while (data
>= max
);
276 return data
/ divisor
;
279 void random_free(random_state
*state
)