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 typedef unsigned long uint32
;
22 unsigned char block
[64];
27 /* ----------------------------------------------------------------------
28 * Core SHA algorithm: processes 16-word blocks into a message digest.
31 #define rol(x,y) ( ((x) << (y)) | (((uint32)x) >> (32-y)) )
33 static void SHA_Core_Init(uint32 h
[5])
42 static void SHATransform(uint32
* digest
, uint32
* block
)
48 for (t
= 0; t
< 16; t
++)
51 for (t
= 16; t
< 80; t
++) {
52 uint32 tmp
= w
[t
- 3] ^ w
[t
- 8] ^ w
[t
- 14] ^ w
[t
- 16];
62 for (t
= 0; t
< 20; t
++) {
64 rol(a
, 5) + ((b
& c
) | (d
& ~b
)) + e
+ w
[t
] + 0x5a827999;
71 for (t
= 20; t
< 40; t
++) {
72 uint32 tmp
= rol(a
, 5) + (b
^ c
^ d
) + e
+ w
[t
] + 0x6ed9eba1;
79 for (t
= 40; t
< 60; t
++) {
81 5) + ((b
& c
) | (b
& d
) | (c
& d
)) + e
+ w
[t
] +
89 for (t
= 60; t
< 80; t
++) {
90 uint32 tmp
= rol(a
, 5) + (b
^ c
^ d
) + e
+ w
[t
] + 0xca62c1d6;
105 /* ----------------------------------------------------------------------
106 * Outer SHA algorithm: take an arbitrary length byte string,
107 * convert it into 16-word blocks with the prescribed padding at
108 * the end, and pass those blocks to the core SHA algorithm.
111 static void SHA_Init(SHA_State
* s
)
115 s
->lenhi
= s
->lenlo
= 0;
118 static void SHA_Bytes(SHA_State
* s
, void *p
, int len
)
120 unsigned char *q
= (unsigned char *) p
;
121 uint32 wordblock
[16];
126 * Update the length field.
129 s
->lenhi
+= (s
->lenlo
< lenw
);
131 if (s
->blkused
&& s
->blkused
+ len
< 64) {
133 * Trivial case: just add to the block.
135 memcpy(s
->block
+ s
->blkused
, q
, len
);
139 * We must complete and process at least one block.
141 while (s
->blkused
+ len
>= 64) {
142 memcpy(s
->block
+ s
->blkused
, q
, 64 - s
->blkused
);
143 q
+= 64 - s
->blkused
;
144 len
-= 64 - s
->blkused
;
145 /* Now process the block. Gather bytes big-endian into words */
146 for (i
= 0; i
< 16; i
++) {
148 (((uint32
) s
->block
[i
* 4 + 0]) << 24) |
149 (((uint32
) s
->block
[i
* 4 + 1]) << 16) |
150 (((uint32
) s
->block
[i
* 4 + 2]) << 8) |
151 (((uint32
) s
->block
[i
* 4 + 3]) << 0);
153 SHATransform(s
->h
, wordblock
);
156 memcpy(s
->block
, q
, len
);
161 static void SHA_Final(SHA_State
* s
, unsigned char *output
)
168 if (s
->blkused
>= 56)
169 pad
= 56 + 64 - s
->blkused
;
171 pad
= 56 - s
->blkused
;
173 lenhi
= (s
->lenhi
<< 3) | (s
->lenlo
>> (32 - 3));
174 lenlo
= (s
->lenlo
<< 3);
178 SHA_Bytes(s
, &c
, pad
);
180 c
[0] = (unsigned char)((lenhi
>> 24) & 0xFF);
181 c
[1] = (unsigned char)((lenhi
>> 16) & 0xFF);
182 c
[2] = (unsigned char)((lenhi
>> 8) & 0xFF);
183 c
[3] = (unsigned char)((lenhi
>> 0) & 0xFF);
184 c
[4] = (unsigned char)((lenlo
>> 24) & 0xFF);
185 c
[5] = (unsigned char)((lenlo
>> 16) & 0xFF);
186 c
[6] = (unsigned char)((lenlo
>> 8) & 0xFF);
187 c
[7] = (unsigned char)((lenlo
>> 0) & 0xFF);
191 for (i
= 0; i
< 5; i
++) {
192 output
[i
* 4] = (unsigned char)((s
->h
[i
] >> 24) & 0xFF);
193 output
[i
* 4 + 1] = (unsigned char)((s
->h
[i
] >> 16) & 0xFF);
194 output
[i
* 4 + 2] = (unsigned char)((s
->h
[i
] >> 8) & 0xFF);
195 output
[i
* 4 + 3] = (unsigned char)((s
->h
[i
]) & 0xFF);
199 static void SHA_Simple(void *p
, int len
, unsigned char *output
)
204 SHA_Bytes(&s
, p
, len
);
205 SHA_Final(&s
, output
);
208 /* ----------------------------------------------------------------------
209 * The random number generator.
212 struct random_state
{
213 unsigned char seedbuf
[40];
214 unsigned char databuf
[20];
218 random_state
*random_init(char *seed
, int len
)
222 state
= snew(random_state
);
224 SHA_Simple(seed
, len
, state
->seedbuf
);
225 SHA_Simple(state
->seedbuf
, 20, state
->seedbuf
+ 20);
226 SHA_Simple(state
->seedbuf
, 40, state
->databuf
);
232 unsigned long random_bits(random_state
*state
, int bits
)
237 for (n
= 0; n
< bits
; n
+= 8) {
238 if (state
->pos
>= 20) {
241 for (i
= 0; i
< 20; i
++) {
242 if (state
->seedbuf
[i
] != 0xFF) {
246 state
->seedbuf
[i
] = 0;
248 SHA_Simple(state
->seedbuf
, 40, state
->databuf
);
251 ret
= (ret
<< 8) | state
->databuf
[state
->pos
++];
254 ret
&= (1 << bits
) - 1;
258 unsigned long random_upto(random_state
*state
, unsigned long limit
)
261 unsigned long max
, divisor
, data
;
263 while ((limit
>> bits
) != 0)
270 divisor
= max
/ limit
;
271 max
= limit
* divisor
;
274 data
= random_bits(state
, bits
);
275 } while (data
>= max
);
277 return data
/ divisor
;
280 void random_free(random_state
*state
)