misc.c

   1 /*
   2  * misc.c: Miscellaneous helpful functions.
   3  */
   4
   5 #include <assert.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <stdio.h>
   9
  10 #include "puzzles.h"
  11
  12 void free_cfg(config_item *cfg)
  13 {
  14     config_item *i;
  15
  16     for (i = cfg; i->type != C_END; i++)
  17         if (i->type == C_STRING)
  18             sfree(i->sval);
  19     sfree(cfg);
  20 }
  21
  22 /*
  23  * The Mines (among others) game descriptions contain the location of every
  24  * mine, and can therefore be used to cheat.
  25  *
  26  * It would be pointless to attempt to _prevent_ this form of
  27  * cheating by encrypting the description, since Mines is
  28  * open-source so anyone can find out the encryption key. However,
  29  * I think it is worth doing a bit of gentle obfuscation to prevent
  30  * _accidental_ spoilers: if you happened to note that the game ID
  31  * starts with an F, for example, you might be unable to put the
  32  * knowledge of those mines out of your mind while playing. So,
  33  * just as discussions of film endings are rot13ed to avoid
  34  * spoiling it for people who don't want to be told, we apply a
  35  * keyless, reversible, but visually completely obfuscatory masking
  36  * function to the mine bitmap.
  37  */
  38 void obfuscate_bitmap(unsigned char *bmp, int bits, int decode)
  39 {
  40     int bytes, firsthalf, secondhalf;
  41     struct step {
  42         unsigned char *seedstart;
  43         int seedlen;
  44         unsigned char *targetstart;
  45         int targetlen;
  46     } steps[2];
  47     int i, j;
  48
  49     /*
  50      * My obfuscation algorithm is similar in concept to the OAEP
  51      * encoding used in some forms of RSA. Here's a specification
  52      * of it:
  53      *
  54      *  + We have a `masking function' which constructs a stream of
  55      *    pseudorandom bytes from a seed of some number of input
  56      *    bytes.
  57      *
  58      *  + We pad out our input bit stream to a whole number of
  59      *    bytes by adding up to 7 zero bits on the end. (In fact
  60      *    the bitmap passed as input to this function will already
  61      *    have had this done in practice.)
  62      *
  63      *  + We divide the _byte_ stream exactly in half, rounding the
  64      *    half-way position _down_. So an 81-bit input string, for
  65      *    example, rounds up to 88 bits or 11 bytes, and then
  66      *    dividing by two gives 5 bytes in the first half and 6 in
  67      *    the second half.
  68      *
  69      *  + We generate a mask from the second half of the bytes, and
  70      *    XOR it over the first half.
  71      *
  72      *  + We generate a mask from the (encoded) first half of the
  73      *    bytes, and XOR it over the second half. Any null bits at
  74      *    the end which were added as padding are cleared back to
  75      *    zero even if this operation would have made them nonzero.
  76      *
  77      * To de-obfuscate, the steps are precisely the same except
  78      * that the final two are reversed.
  79      *
  80      * Finally, our masking function. Given an input seed string of
  81      * bytes, the output mask consists of concatenating the SHA-1
  82      * hashes of the seed string and successive decimal integers,
  83      * starting from 0.
  84      */
  85
  86     bytes = (bits + 7) / 8;
  87     firsthalf = bytes / 2;
  88     secondhalf = bytes - firsthalf;
  89
  90     steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
  91     steps[decode ? 1 : 0].seedlen = secondhalf;
  92     steps[decode ? 1 : 0].targetstart = bmp;
  93     steps[decode ? 1 : 0].targetlen = firsthalf;
  94
  95     steps[decode ? 0 : 1].seedstart = bmp;
  96     steps[decode ? 0 : 1].seedlen = firsthalf;
  97     steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
  98     steps[decode ? 0 : 1].targetlen = secondhalf;
  99
 100     for (i = 0; i < 2; i++) {
 101         SHA_State base, final;
 102         unsigned char digest[20];
 103         char numberbuf[80];
 104         int digestpos = 20, counter = 0;
 105
 106         SHA_Init(&base);
 107         SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
 108
 109         for (j = 0; j < steps[i].targetlen; j++) {
 110             if (digestpos >= 20) {
 111                 sprintf(numberbuf, "%d", counter++);
 112                 final = base;
 113                 SHA_Bytes(&final, numberbuf, strlen(numberbuf));
 114                 SHA_Final(&final, digest);
 115                 digestpos = 0;
 116             }
 117             steps[i].targetstart[j] ^= digest[digestpos++];
 118         }
 119
 120         /*
 121          * Mask off the pad bits in the final byte after both steps.
 122          */
 123         if (bits % 8)
 124             bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
 125     }
 126 }
 127
 128 /* err, yeah, these two pretty much rely on unsigned char being 8 bits.
 129  * Platforms where this is not the case probably have bigger problems
 130  * than just making these two work, though... */
 131 char *bin2hex(const unsigned char *in, int inlen)
 132 {
 133     char *ret = snewn(inlen*2 + 1, char), *p = ret;
 134     int i;
 135
 136     for (i = 0; i < inlen*2; i++) {
 137         int v = in[i/2];
 138         if (i % 2 == 0) v >>= 4;
 139         *p++ = "0123456789abcdef"[v & 0xF];
 140     }
 141     *p = '\0';
 142     return ret;
 143 }
 144
 145 unsigned char *hex2bin(const char *in, int outlen)
 146 {
 147     unsigned char *ret = snewn(outlen, unsigned char);
 148     int i;
 149
 150     memset(ret, 0, outlen*sizeof(unsigned char));
 151     for (i = 0; i < outlen*2; i++) {
 152         int c = in[i];
 153         int v;
 154
 155         assert(c != 0);
 156         if (c >= '0' && c <= '9')
 157             v = c - '0';
 158         else if (c >= 'a' && c <= 'f')
 159             v = c - 'a' + 10;
 160         else if (c >= 'A' && c <= 'F')
 161             v = c - 'A' + 10;
 162         else
 163             v = 0;
 164
 165         ret[i / 2] |= v << (4 * (1 - (i % 2)));
 166     }
 167     return ret;
 168 }
 169
 170 void game_mkhighlight(frontend *fe, float *ret,
 171                       int background, int highlight, int lowlight)
 172 {
 173     float max;
 174     int i;
 175
 176     frontend_default_colour(fe, &ret[background * 3]);
 177
 178     /*
 179      * Drop the background colour so that the highlight is
 180      * noticeably brighter than it while still being under 1.
 181      */
 182     max = ret[background*3];
 183     for (i = 1; i < 3; i++)
 184         if (ret[background*3+i] > max)
 185             max = ret[background*3+i];
 186     if (max * 1.2F > 1.0F) {
 187         for (i = 0; i < 3; i++)
 188             ret[background*3+i] /= (max * 1.2F);
 189     }
 190
 191     for (i = 0; i < 3; i++) {
 192         ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F;
 193         ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F;
 194     }
 195 }
 196
 197 static void memswap(void *av, void *bv, int size)
 198 {
 199     char tmpbuf[512];
 200     char *a = av, *b = bv;
 201
 202     while (size > 0) {
 203         int thislen = min(size, sizeof(tmpbuf));
 204         memcpy(tmpbuf, a, thislen);
 205         memcpy(a, b, thislen);
 206         memcpy(b, tmpbuf, thislen);
 207         a += thislen;
 208         b += thislen;
 209         size -= thislen;
 210     }
 211 }
 212
 213 void shuffle(void *array, int nelts, int eltsize, random_state *rs)
 214 {
 215     char *carray = (char *)array;
 216     int i;
 217
 218     for (i = nelts; i-- > 1 ;) {
 219         int j = random_upto(rs, i+1);
 220         if (j != i)
 221             memswap(carray + eltsize * i, carray + eltsize * j, eltsize);
 222     }
 223 }
 224
 225 void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour)
 226 {
 227     int x0 = x, x1 = x+w-1, y0 = y, y1 = y+h-1;
 228     int coords[8];
 229
 230     coords[0] = x0;
 231     coords[1] = y0;
 232     coords[2] = x0;
 233     coords[3] = y1;
 234     coords[4] = x1;
 235     coords[5] = y1;
 236     coords[6] = x1;
 237     coords[7] = y0;
 238
 239     draw_polygon(dr, coords, 4, -1, colour);
 240 }
 241
 242 /* vim: set shiftwidth=4 tabstop=8: */