random.c

   1 /*
   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
   6  * different platforms.
   7  *
   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!
  11  */
  12
  13 #include <assert.h>
  14 #include <string.h>
  15
  16 #include "puzzles.h"
  17
  18 typedef unsigned long uint32;
  19
  20 typedef struct {
  21     uint32 h[5];
  22     unsigned char block[64];
  23     int blkused;
  24     uint32 lenhi, lenlo;
  25 } SHA_State;
  26
  27 /* ----------------------------------------------------------------------
  28  * Core SHA algorithm: processes 16-word blocks into a message digest.
  29  */
  30
  31 #define rol(x,y) ( ((x) << (y)) | (((uint32)x) >> (32-y)) )
  32
  33 static void SHA_Core_Init(uint32 h[5])
  34 {
  35     h[0] = 0x67452301;
  36     h[1] = 0xefcdab89;
  37     h[2] = 0x98badcfe;
  38     h[3] = 0x10325476;
  39     h[4] = 0xc3d2e1f0;
  40 }
  41
  42 static void SHATransform(uint32 * digest, uint32 * block)
  43 {
  44     uint32 w[80];
  45     uint32 a, b, c, d, e;
  46     int t;
  47
  48     for (t = 0; t < 16; t++)
  49         w[t] = block[t];
  50
  51     for (t = 16; t < 80; t++) {
  52         uint32 tmp = w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16];
  53         w[t] = rol(tmp, 1);
  54     }
  55
  56     a = digest[0];
  57     b = digest[1];
  58     c = digest[2];
  59     d = digest[3];
  60     e = digest[4];
  61
  62     for (t = 0; t < 20; t++) {
  63         uint32 tmp =
  64             rol(a, 5) + ((b & c) | (d & ~b)) + e + w[t] + 0x5a827999;
  65         e = d;
  66         d = c;
  67         c = rol(b, 30);
  68         b = a;
  69         a = tmp;
  70     }
  71     for (t = 20; t < 40; t++) {
  72         uint32 tmp = rol(a, 5) + (b ^ c ^ d) + e + w[t] + 0x6ed9eba1;
  73         e = d;
  74         d = c;
  75         c = rol(b, 30);
  76         b = a;
  77         a = tmp;
  78     }
  79     for (t = 40; t < 60; t++) {
  80         uint32 tmp = rol(a,
  81                          5) + ((b & c) | (b & d) | (c & d)) + e + w[t] +
  82             0x8f1bbcdc;
  83         e = d;
  84         d = c;
  85         c = rol(b, 30);
  86         b = a;
  87         a = tmp;
  88     }
  89     for (t = 60; t < 80; t++) {
  90         uint32 tmp = rol(a, 5) + (b ^ c ^ d) + e + w[t] + 0xca62c1d6;
  91         e = d;
  92         d = c;
  93         c = rol(b, 30);
  94         b = a;
  95         a = tmp;
  96     }
  97
  98     digest[0] += a;
  99     digest[1] += b;
 100     digest[2] += c;
 101     digest[3] += d;
 102     digest[4] += e;
 103 }
 104
 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.
 109  */
 110
 111 static void SHA_Init(SHA_State * s)
 112 {
 113     SHA_Core_Init(s->h);
 114     s->blkused = 0;
 115     s->lenhi = s->lenlo = 0;
 116 }
 117
 118 static void SHA_Bytes(SHA_State * s, void *p, int len)
 119 {
 120     unsigned char *q = (unsigned char *) p;
 121     uint32 wordblock[16];
 122     uint32 lenw = len;
 123     int i;
 124
 125     /*
 126      * Update the length field.
 127      */
 128     s->lenlo += lenw;
 129     s->lenhi += (s->lenlo < lenw);
 130
 131     if (s->blkused && s->blkused + len < 64) {
 132         /*
 133          * Trivial case: just add to the block.
 134          */
 135         memcpy(s->block + s->blkused, q, len);
 136         s->blkused += len;
 137     } else {
 138         /*
 139          * We must complete and process at least one block.
 140          */
 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++) {
 147                 wordblock[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);
 152             }
 153             SHATransform(s->h, wordblock);
 154             s->blkused = 0;
 155         }
 156         memcpy(s->block, q, len);
 157         s->blkused = len;
 158     }
 159 }
 160
 161 static void SHA_Final(SHA_State * s, unsigned char *output)
 162 {
 163     int i;
 164     int pad;
 165     unsigned char c[64];
 166     uint32 lenhi, lenlo;
 167
 168     if (s->blkused >= 56)
 169         pad = 56 + 64 - s->blkused;
 170     else
 171         pad = 56 - s->blkused;
 172
 173     lenhi = (s->lenhi << 3) | (s->lenlo >> (32 - 3));
 174     lenlo = (s->lenlo << 3);
 175
 176     memset(c, 0, pad);
 177     c[0] = 0x80;
 178     SHA_Bytes(s, &c, pad);
 179
 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);
 188
 189     SHA_Bytes(s, &c, 8);
 190
 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);
 196     }
 197 }
 198
 199 static void SHA_Simple(void *p, int len, unsigned char *output)
 200 {
 201     SHA_State s;
 202
 203     SHA_Init(&s);
 204     SHA_Bytes(&s, p, len);
 205     SHA_Final(&s, output);
 206 }
 207
 208 /* ----------------------------------------------------------------------
 209  * The random number generator.
 210  */
 211
 212 struct random_state {
 213     unsigned char seedbuf[40];
 214     unsigned char databuf[20];
 215     int pos;
 216 };
 217
 218 random_state *random_init(char *seed, int len)
 219 {
 220     random_state *state;
 221
 222     state = snew(random_state);
 223
 224     SHA_Simple(seed, len, state->seedbuf);
 225     SHA_Simple(state->seedbuf, 20, state->seedbuf + 20);
 226     SHA_Simple(state->seedbuf, 40, state->databuf);
 227     state->pos = 0;
 228
 229     return state;
 230 }
 231
 232 unsigned long random_bits(random_state *state, int bits)
 233 {
 234     unsigned long ret = 0;
 235     int n;
 236
 237     for (n = 0; n < bits; n += 8) {
 238         if (state->pos >= 20) {
 239             int i;
 240
 241             for (i = 0; i < 20; i++) {
 242                 if (state->seedbuf[i] != 0xFF) {
 243                     state->seedbuf[i]++;
 244                     break;
 245                 } else
 246                     state->seedbuf[i] = 0;
 247             }
 248             SHA_Simple(state->seedbuf, 40, state->databuf);
 249             state->pos = 0;
 250         }
 251         ret = (ret << 8) | state->databuf[state->pos++];
 252     }
 253
 254     /*
 255      * `(1 << bits) - 1' is not good enough, since if bits==32 on a
 256      * 32-bit machine, behaviour is undefined and Intel has a nasty
 257      * habit of shifting left by zero instead. We'll shift by
 258      * bits-1 and then separately shift by one.
 259      */
 260     ret &= (1 << (bits-1)) * 2 - 1;
 261     return ret;
 262 }
 263
 264 unsigned long random_upto(random_state *state, unsigned long limit)
 265 {
 266     int bits = 0;
 267     unsigned long max, divisor, data;
 268
 269     while ((limit >> bits) != 0)
 270         bits++;
 271
 272     bits += 3;
 273     assert(bits < 32);
 274
 275     max = 1 << bits;
 276     divisor = max / limit;
 277     max = limit * divisor;
 278
 279     do {
 280         data = random_bits(state, bits);
 281     } while (data >= max);
 282
 283     return data / divisor;
 284 }
 285
 286 void random_free(random_state *state)
 287 {
 288     sfree(state);
 289 }