Tents: mark squares as non-tents with {Shift,Control}-cursor keys.

[sgt-puzzles.git] / random.c

diff --git a/random.c b/random.c
index dad2c0e45cec49c80752e8af399b23c02ce6a9ea..fb54560c9570c12f19ca38c2f24a30188e230fc0 100644 (file)
--- a/random.c
+++ b/random.c
@@ -12,18 +12,10 @@
 
 #include <assert.h>
 #include <string.h>
+#include <stdio.h>
 
 #include "puzzles.h"
 
-typedef unsigned long uint32;
-
-typedef struct {
-    uint32 h[5];
-    unsigned char block[64];
-    int blkused;
-    uint32 lenhi, lenlo;
-} SHA_State;
-
 /* ----------------------------------------------------------------------
  * Core SHA algorithm: processes 16-word blocks into a message digest.
  */
@@ -108,14 +100,14 @@ static void SHATransform(uint32 * digest, uint32 * block)
  * the end, and pass those blocks to the core SHA algorithm.
  */
 
-static void SHA_Init(SHA_State * s)
+void SHA_Init(SHA_State * s)
 {
     SHA_Core_Init(s->h);
     s->blkused = 0;
     s->lenhi = s->lenlo = 0;
 }
 
-static void SHA_Bytes(SHA_State * s, void *p, int len)
+void SHA_Bytes(SHA_State * s, const void *p, int len)
 {
     unsigned char *q = (unsigned char *) p;
     uint32 wordblock[16];
@@ -158,7 +150,7 @@ static void SHA_Bytes(SHA_State * s, void *p, int len)
     }
 }
 
-static void SHA_Final(SHA_State * s, unsigned char *output)
+void SHA_Final(SHA_State * s, unsigned char *output)
 {
     int i;
     int pad;
@@ -177,26 +169,26 @@ static void SHA_Final(SHA_State * s, unsigned char *output)
     c[0] = 0x80;
     SHA_Bytes(s, &c, pad);
 
-    c[0] = (lenhi >> 24) & 0xFF;
-    c[1] = (lenhi >> 16) & 0xFF;
-    c[2] = (lenhi >> 8) & 0xFF;
-    c[3] = (lenhi >> 0) & 0xFF;
-    c[4] = (lenlo >> 24) & 0xFF;
-    c[5] = (lenlo >> 16) & 0xFF;
-    c[6] = (lenlo >> 8) & 0xFF;
-    c[7] = (lenlo >> 0) & 0xFF;
+    c[0] = (unsigned char)((lenhi >> 24) & 0xFF);
+    c[1] = (unsigned char)((lenhi >> 16) & 0xFF);
+    c[2] = (unsigned char)((lenhi >> 8) & 0xFF);
+    c[3] = (unsigned char)((lenhi >> 0) & 0xFF);
+    c[4] = (unsigned char)((lenlo >> 24) & 0xFF);
+    c[5] = (unsigned char)((lenlo >> 16) & 0xFF);
+    c[6] = (unsigned char)((lenlo >> 8) & 0xFF);
+    c[7] = (unsigned char)((lenlo >> 0) & 0xFF);
 
     SHA_Bytes(s, &c, 8);
 
     for (i = 0; i < 5; i++) {
-       output[i * 4] = (s->h[i] >> 24) & 0xFF;
-       output[i * 4 + 1] = (s->h[i] >> 16) & 0xFF;
-       output[i * 4 + 2] = (s->h[i] >> 8) & 0xFF;
-       output[i * 4 + 3] = (s->h[i]) & 0xFF;
+       output[i * 4] = (unsigned char)((s->h[i] >> 24) & 0xFF);
+       output[i * 4 + 1] = (unsigned char)((s->h[i] >> 16) & 0xFF);
+       output[i * 4 + 2] = (unsigned char)((s->h[i] >> 8) & 0xFF);
+       output[i * 4 + 3] = (unsigned char)((s->h[i]) & 0xFF);
     }
 }
 
-static void SHA_Simple(void *p, int len, unsigned char *output)
+void SHA_Simple(const void *p, int len, unsigned char *output)
 {
     SHA_State s;
 
@@ -215,7 +207,7 @@ struct random_state {
     int pos;
 };
 
-random_state *random_init(char *seed, int len)
+random_state *random_new(const char *seed, int len)
 {
     random_state *state;
 
@@ -229,9 +221,19 @@ random_state *random_init(char *seed, int len)
     return state;
 }
 
+random_state *random_copy(random_state *tocopy)
+{
+    random_state *result;
+    result = snew(random_state);
+    memcpy(result->seedbuf, tocopy->seedbuf, sizeof(result->seedbuf));
+    memcpy(result->databuf, tocopy->databuf, sizeof(result->databuf));
+    result->pos = tocopy->pos;
+    return result;
+}
+
 unsigned long random_bits(random_state *state, int bits)
 {
-    int ret = 0;
+    unsigned long ret = 0;
     int n;
 
     for (n = 0; n < bits; n += 8) {
@@ -251,7 +253,13 @@ unsigned long random_bits(random_state *state, int bits)
        ret = (ret << 8) | state->databuf[state->pos++];
     }
 
-    ret &= (1 << bits) - 1;
+    /*
+     * `(1 << bits) - 1' is not good enough, since if bits==32 on a
+     * 32-bit machine, behaviour is undefined and Intel has a nasty
+     * habit of shifting left by zero instead. We'll shift by
+     * bits-1 and then separately shift by one.
+     */
+    ret &= (1 << (bits-1)) * 2 - 1;
     return ret;
 }
 
@@ -266,7 +274,7 @@ unsigned long random_upto(random_state *state, unsigned long limit)
     bits += 3;
     assert(bits < 32);
 
-    max = 1 << bits;
+    max = 1L << bits;
     divisor = max / limit;
     max = limit * divisor;
 
@@ -281,3 +289,63 @@ void random_free(random_state *state)
 {
     sfree(state);
 }
+
+char *random_state_encode(random_state *state)
+{
+    char retbuf[256];
+    int len = 0, i;
+
+    for (i = 0; i < lenof(state->seedbuf); i++)
+       len += sprintf(retbuf+len, "%02x", state->seedbuf[i]);
+    for (i = 0; i < lenof(state->databuf); i++)
+       len += sprintf(retbuf+len, "%02x", state->databuf[i]);
+    len += sprintf(retbuf+len, "%02x", state->pos);
+
+    return dupstr(retbuf);
+}
+
+random_state *random_state_decode(const char *input)
+{
+    random_state *state;
+    int pos, byte, digits;
+
+    state = snew(random_state);
+
+    memset(state->seedbuf, 0, sizeof(state->seedbuf));
+    memset(state->databuf, 0, sizeof(state->databuf));
+    state->pos = 0;
+
+    byte = digits = 0;
+    pos = 0;
+    while (*input) {
+       int v = *input++;
+
+       if (v >= '0' && v <= '9')
+           v = v - '0';
+       else if (v >= 'A' && v <= 'F')
+           v = v - 'A' + 10;
+       else if (v >= 'a' && v <= 'f')
+           v = v - 'a' + 10;
+       else
+           v = 0;
+
+       byte = (byte << 4) | v;
+       digits++;
+
+       if (digits == 2) {
+           /*
+            * We have a byte. Put it somewhere.
+            */
+           if (pos < lenof(state->seedbuf))
+               state->seedbuf[pos++] = byte;
+           else if (pos < lenof(state->seedbuf) + lenof(state->databuf))
+               state->databuf[pos++ - lenof(state->seedbuf)] = byte;
+           else if (pos == lenof(state->seedbuf) + lenof(state->databuf) &&
+                    byte <= lenof(state->databuf))
+               state->pos = byte;
+           byte = digits = 0;
+       }
+    }
+
+    return state;
+}