#include <assert.h>
#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
#include "puzzles.h"
-int rand_upto(int limit)
+void free_cfg(config_item *cfg)
+{
+ config_item *i;
+
+ for (i = cfg; i->type != C_END; i++)
+ if (i->type == C_STRING)
+ sfree(i->sval);
+ sfree(cfg);
+}
+
+/*
+ * The Mines (among others) game descriptions contain the location of every
+ * mine, and can therefore be used to cheat.
+ *
+ * It would be pointless to attempt to _prevent_ this form of
+ * cheating by encrypting the description, since Mines is
+ * open-source so anyone can find out the encryption key. However,
+ * I think it is worth doing a bit of gentle obfuscation to prevent
+ * _accidental_ spoilers: if you happened to note that the game ID
+ * starts with an F, for example, you might be unable to put the
+ * knowledge of those mines out of your mind while playing. So,
+ * just as discussions of film endings are rot13ed to avoid
+ * spoiling it for people who don't want to be told, we apply a
+ * keyless, reversible, but visually completely obfuscatory masking
+ * function to the mine bitmap.
+ */
+void obfuscate_bitmap(unsigned char *bmp, int bits, int decode)
{
- unsigned long divisor = RAND_MAX / (unsigned)limit;
- unsigned long max = divisor * (unsigned)limit;
- unsigned long n;
+ int bytes, firsthalf, secondhalf;
+ struct step {
+ unsigned char *seedstart;
+ int seedlen;
+ unsigned char *targetstart;
+ int targetlen;
+ } steps[2];
+ int i, j;
+
+ /*
+ * My obfuscation algorithm is similar in concept to the OAEP
+ * encoding used in some forms of RSA. Here's a specification
+ * of it:
+ *
+ * + We have a `masking function' which constructs a stream of
+ * pseudorandom bytes from a seed of some number of input
+ * bytes.
+ *
+ * + We pad out our input bit stream to a whole number of
+ * bytes by adding up to 7 zero bits on the end. (In fact
+ * the bitmap passed as input to this function will already
+ * have had this done in practice.)
+ *
+ * + We divide the _byte_ stream exactly in half, rounding the
+ * half-way position _down_. So an 81-bit input string, for
+ * example, rounds up to 88 bits or 11 bytes, and then
+ * dividing by two gives 5 bytes in the first half and 6 in
+ * the second half.
+ *
+ * + We generate a mask from the second half of the bytes, and
+ * XOR it over the first half.
+ *
+ * + We generate a mask from the (encoded) first half of the
+ * bytes, and XOR it over the second half. Any null bits at
+ * the end which were added as padding are cleared back to
+ * zero even if this operation would have made them nonzero.
+ *
+ * To de-obfuscate, the steps are precisely the same except
+ * that the final two are reversed.
+ *
+ * Finally, our masking function. Given an input seed string of
+ * bytes, the output mask consists of concatenating the SHA-1
+ * hashes of the seed string and successive decimal integers,
+ * starting from 0.
+ */
+
+ bytes = (bits + 7) / 8;
+ firsthalf = bytes / 2;
+ secondhalf = bytes - firsthalf;
- assert(limit > 0);
+ steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
+ steps[decode ? 1 : 0].seedlen = secondhalf;
+ steps[decode ? 1 : 0].targetstart = bmp;
+ steps[decode ? 1 : 0].targetlen = firsthalf;
- do {
- n = rand();
- } while (n >= max);
+ steps[decode ? 0 : 1].seedstart = bmp;
+ steps[decode ? 0 : 1].seedlen = firsthalf;
+ steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
+ steps[decode ? 0 : 1].targetlen = secondhalf;
- n /= divisor;
+ for (i = 0; i < 2; i++) {
+ SHA_State base, final;
+ unsigned char digest[20];
+ char numberbuf[80];
+ int digestpos = 20, counter = 0;
- return (int)n;
+ SHA_Init(&base);
+ SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
+
+ for (j = 0; j < steps[i].targetlen; j++) {
+ if (digestpos >= 20) {
+ sprintf(numberbuf, "%d", counter++);
+ final = base;
+ SHA_Bytes(&final, numberbuf, strlen(numberbuf));
+ SHA_Final(&final, digest);
+ digestpos = 0;
+ }
+ steps[i].targetstart[j] ^= digest[digestpos++];
+ }
+
+ /*
+ * Mask off the pad bits in the final byte after both steps.
+ */
+ if (bits % 8)
+ bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
+ }
}
-void free_cfg(config_item *cfg)
+/* err, yeah, these two pretty much rely on unsigned char being 8 bits.
+ * Platforms where this is not the case probably have bigger problems
+ * than just making these two work, though... */
+char *bin2hex(const unsigned char *in, int inlen)
{
- config_item *i;
+ char *ret = snewn(inlen*2 + 1, char), *p = ret;
+ int i;
- for (i = cfg; i->type != C_END; i++)
- if (i->type == C_STRING)
- sfree(i->sval);
- sfree(cfg);
+ for (i = 0; i < inlen*2; i++) {
+ int v = in[i/2];
+ if (i % 2 == 0) v >>= 4;
+ *p++ = "0123456789abcdef"[v & 0xF];
+ }
+ *p = '\0';
+ return ret;
}
+
+unsigned char *hex2bin(const char *in, int outlen)
+{
+ unsigned char *ret = snewn(outlen, unsigned char);
+ int i;
+
+ memset(ret, 0, outlen*sizeof(unsigned char));
+ for (i = 0; i < outlen*2; i++) {
+ int c = in[i];
+ int v;
+
+ assert(c != 0);
+ if (c >= '0' && c <= '9')
+ v = c - '0';
+ else if (c >= 'a' && c <= 'f')
+ v = c - 'a' + 10;
+ else if (c >= 'A' && c <= 'F')
+ v = c - 'A' + 10;
+ else
+ v = 0;
+
+ ret[i / 2] |= v << (4 * (1 - (i % 2)));
+ }
+ return ret;
+}
+
+void game_mkhighlight(frontend *fe, float *ret,
+ int background, int highlight, int lowlight)
+{
+ float max;
+ int i;
+
+ frontend_default_colour(fe, &ret[background * 3]);
+
+ /*
+ * Drop the background colour so that the highlight is
+ * noticeably brighter than it while still being under 1.
+ */
+ max = ret[background*3];
+ for (i = 1; i < 3; i++)
+ if (ret[background*3+i] > max)
+ max = ret[background*3+i];
+ if (max * 1.2F > 1.0F) {
+ for (i = 0; i < 3; i++)
+ ret[background*3+i] /= (max * 1.2F);
+ }
+
+ for (i = 0; i < 3; i++) {
+ ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F;
+ ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F;
+ }
+}
+
+void shuffle(void *array, int nelts, int eltsize, random_state *rs)
+{
+ char *tmp = smalloc(eltsize);
+ char *carray = (char *)array;
+ int i;
+
+ for (i = nelts; i-- > 1 ;) {
+ int j = random_upto(rs, i+1);
+ if (j != i) {
+ memcpy(tmp, carray + eltsize * i, eltsize);
+ memcpy(carray + eltsize * i, carray + eltsize * j, eltsize);
+ memcpy(carray + eltsize * j, tmp, eltsize);
+ }
+ }
+ sfree(tmp);
+}
+
+void draw_rect_outline(frontend *fe, int x, int y, int w, int h, int colour)
+{
+ int x0 = x, x1 = x+w-1, y0 = y, y1 = y+h-1;
+
+ draw_line(fe, x0, y0, x0, y1, colour);
+ draw_line(fe, x0, y1, x1, y1, colour);
+ draw_line(fe, x1, y1, x1, y0, colour);
+ draw_line(fe, x1, y0, x0, y0, colour);
+}
+
+/* vim: set shiftwidth=4 tabstop=8: */
~ian / sgt-puzzles.git / blobdiff