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!
18 /* ----------------------------------------------------------------------
19 * Core SHA algorithm: processes 16-word blocks into a message digest.
22 #define rol(x,y) ( ((x) << (y)) | (((uint32)x) >> (32-y)) )
24 static void SHA_Core_Init(uint32 h
[5])
33 static void SHATransform(uint32
* digest
, uint32
* block
)
39 for (t
= 0; t
< 16; t
++)
42 for (t
= 16; t
< 80; t
++) {
43 uint32 tmp
= w
[t
- 3] ^ w
[t
- 8] ^ w
[t
- 14] ^ w
[t
- 16];
53 for (t
= 0; t
< 20; t
++) {
55 rol(a
, 5) + ((b
& c
) | (d
& ~b
)) + e
+ w
[t
] + 0x5a827999;
62 for (t
= 20; t
< 40; t
++) {
63 uint32 tmp
= rol(a
, 5) + (b
^ c
^ d
) + e
+ w
[t
] + 0x6ed9eba1;
70 for (t
= 40; t
< 60; t
++) {
72 5) + ((b
& c
) | (b
& d
) | (c
& d
)) + e
+ w
[t
] +
80 for (t
= 60; t
< 80; t
++) {
81 uint32 tmp
= rol(a
, 5) + (b
^ c
^ d
) + e
+ w
[t
] + 0xca62c1d6;
96 /* ----------------------------------------------------------------------
97 * Outer SHA algorithm: take an arbitrary length byte string,
98 * convert it into 16-word blocks with the prescribed padding at
99 * the end, and pass those blocks to the core SHA algorithm.
102 void SHA_Init(SHA_State
* s
)
106 s
->lenhi
= s
->lenlo
= 0;
109 void SHA_Bytes(SHA_State
* s
, void *p
, int len
)
111 unsigned char *q
= (unsigned char *) p
;
112 uint32 wordblock
[16];
117 * Update the length field.
120 s
->lenhi
+= (s
->lenlo
< lenw
);
122 if (s
->blkused
&& s
->blkused
+ len
< 64) {
124 * Trivial case: just add to the block.
126 memcpy(s
->block
+ s
->blkused
, q
, len
);
130 * We must complete and process at least one block.
132 while (s
->blkused
+ len
>= 64) {
133 memcpy(s
->block
+ s
->blkused
, q
, 64 - s
->blkused
);
134 q
+= 64 - s
->blkused
;
135 len
-= 64 - s
->blkused
;
136 /* Now process the block. Gather bytes big-endian into words */
137 for (i
= 0; i
< 16; i
++) {
139 (((uint32
) s
->block
[i
* 4 + 0]) << 24) |
140 (((uint32
) s
->block
[i
* 4 + 1]) << 16) |
141 (((uint32
) s
->block
[i
* 4 + 2]) << 8) |
142 (((uint32
) s
->block
[i
* 4 + 3]) << 0);
144 SHATransform(s
->h
, wordblock
);
147 memcpy(s
->block
, q
, len
);
152 void SHA_Final(SHA_State
* s
, unsigned char *output
)
159 if (s
->blkused
>= 56)
160 pad
= 56 + 64 - s
->blkused
;
162 pad
= 56 - s
->blkused
;
164 lenhi
= (s
->lenhi
<< 3) | (s
->lenlo
>> (32 - 3));
165 lenlo
= (s
->lenlo
<< 3);
169 SHA_Bytes(s
, &c
, pad
);
171 c
[0] = (unsigned char)((lenhi
>> 24) & 0xFF);
172 c
[1] = (unsigned char)((lenhi
>> 16) & 0xFF);
173 c
[2] = (unsigned char)((lenhi
>> 8) & 0xFF);
174 c
[3] = (unsigned char)((lenhi
>> 0) & 0xFF);
175 c
[4] = (unsigned char)((lenlo
>> 24) & 0xFF);
176 c
[5] = (unsigned char)((lenlo
>> 16) & 0xFF);
177 c
[6] = (unsigned char)((lenlo
>> 8) & 0xFF);
178 c
[7] = (unsigned char)((lenlo
>> 0) & 0xFF);
182 for (i
= 0; i
< 5; i
++) {
183 output
[i
* 4] = (unsigned char)((s
->h
[i
] >> 24) & 0xFF);
184 output
[i
* 4 + 1] = (unsigned char)((s
->h
[i
] >> 16) & 0xFF);
185 output
[i
* 4 + 2] = (unsigned char)((s
->h
[i
] >> 8) & 0xFF);
186 output
[i
* 4 + 3] = (unsigned char)((s
->h
[i
]) & 0xFF);
190 void SHA_Simple(void *p
, int len
, unsigned char *output
)
195 SHA_Bytes(&s
, p
, len
);
196 SHA_Final(&s
, output
);
199 /* ----------------------------------------------------------------------
200 * The random number generator.
203 struct random_state
{
204 unsigned char seedbuf
[40];
205 unsigned char databuf
[20];
209 random_state
*random_init(char *seed
, int len
)
213 state
= snew(random_state
);
215 SHA_Simple(seed
, len
, state
->seedbuf
);
216 SHA_Simple(state
->seedbuf
, 20, state
->seedbuf
+ 20);
217 SHA_Simple(state
->seedbuf
, 40, state
->databuf
);
223 unsigned long random_bits(random_state
*state
, int bits
)
225 unsigned long ret
= 0;
228 for (n
= 0; n
< bits
; n
+= 8) {
229 if (state
->pos
>= 20) {
232 for (i
= 0; i
< 20; i
++) {
233 if (state
->seedbuf
[i
] != 0xFF) {
237 state
->seedbuf
[i
] = 0;
239 SHA_Simple(state
->seedbuf
, 40, state
->databuf
);
242 ret
= (ret
<< 8) | state
->databuf
[state
->pos
++];
246 * `(1 << bits) - 1' is not good enough, since if bits==32 on a
247 * 32-bit machine, behaviour is undefined and Intel has a nasty
248 * habit of shifting left by zero instead. We'll shift by
249 * bits-1 and then separately shift by one.
251 ret
&= (1 << (bits
-1)) * 2 - 1;
255 unsigned long random_upto(random_state
*state
, unsigned long limit
)
258 unsigned long max
, divisor
, data
;
260 while ((limit
>> bits
) != 0)
267 divisor
= max
/ limit
;
268 max
= limit
* divisor
;
271 data
= random_bits(state
, bits
);
272 } while (data
>= max
);
274 return data
/ divisor
;
277 void random_free(random_state
*state
)