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_specific(frontend *fe, float *ret,
 171                                int background, int highlight, int lowlight)
 172 {
 173     float max;
 174     int i;
 175
 176     /*
 177      * Drop the background colour so that the highlight is
 178      * noticeably brighter than it while still being under 1.
 179      */
 180     max = ret[background*3];
 181     for (i = 1; i < 3; i++)
 182         if (ret[background*3+i] > max)
 183             max = ret[background*3+i];
 184     if (max * 1.2F > 1.0F) {
 185         for (i = 0; i < 3; i++)
 186             ret[background*3+i] /= (max * 1.2F);
 187     }
 188
 189     for (i = 0; i < 3; i++) {
 190         ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F;
 191         ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F;
 192     }
 193 }
 194
 195 void game_mkhighlight(frontend *fe, float *ret,
 196                       int background, int highlight, int lowlight)
 197 {
 198     frontend_default_colour(fe, &ret[background * 3]);
 199     game_mkhighlight_specific(fe, ret, background, highlight, lowlight);
 200 }
 201
 202 static void memswap(void *av, void *bv, int size)
 203 {
 204     char tmpbuf[512];
 205     char *a = av, *b = bv;
 206
 207     while (size > 0) {
 208         int thislen = min(size, sizeof(tmpbuf));
 209         memcpy(tmpbuf, a, thislen);
 210         memcpy(a, b, thislen);
 211         memcpy(b, tmpbuf, thislen);
 212         a += thislen;
 213         b += thislen;
 214         size -= thislen;
 215     }
 216 }
 217
 218 void shuffle(void *array, int nelts, int eltsize, random_state *rs)
 219 {
 220     char *carray = (char *)array;
 221     int i;
 222
 223     for (i = nelts; i-- > 1 ;) {
 224         int j = random_upto(rs, i+1);
 225         if (j != i)
 226             memswap(carray + eltsize * i, carray + eltsize * j, eltsize);
 227     }
 228 }
 229
 230 void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour)
 231 {
 232     int x0 = x, x1 = x+w-1, y0 = y, y1 = y+h-1;
 233     int coords[8];
 234
 235     coords[0] = x0;
 236     coords[1] = y0;
 237     coords[2] = x0;
 238     coords[3] = y1;
 239     coords[4] = x1;
 240     coords[5] = y1;
 241     coords[6] = x1;
 242     coords[7] = y0;
 243
 244     draw_polygon(dr, coords, 4, -1, colour);
 245 }
 246
 247 /* vim: set shiftwidth=4 tabstop=8: */