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 void move_cursor(int button, int *x, int *y, int maxw, int maxh, int wrap)
 248 {
 249     int dx = 0, dy = 0;
 250     switch (button) {
 251     case CURSOR_UP:         dy = -1; break;
 252     case CURSOR_DOWN:       dy = 1; break;
 253     case CURSOR_RIGHT:      dx = 1; break;
 254     case CURSOR_LEFT:       dx = -1; break;
 255     default: return;
 256     }
 257     if (wrap) {
 258         *x = (*x + dx + maxw) % maxw;
 259         *y = (*y + dy + maxh) % maxh;
 260     } else {
 261         *x = min(max(*x+dx, 0), maxw - 1);
 262         *y = min(max(*y+dy, 0), maxh - 1);
 263     }
 264 }
 265
 266 /* Used in netslide.c and sixteen.c for cursor movement around edge. */
 267
 268 int c2pos(int w, int h, int cx, int cy)
 269 {
 270     if (cy == -1)
 271         return cx;                      /* top row, 0 .. w-1 (->) */
 272     else if (cx == w)
 273         return w + cy;                  /* R col, w .. w+h -1 (v) */
 274     else if (cy == h)
 275         return w + h + (w-cx-1);        /* bottom row, w+h .. w+h+w-1 (<-) */
 276     else if (cx == -1)
 277         return w + h + w + (h-cy-1);    /* L col, w+h+w .. w+h+w+h-1 (^) */
 278
 279     assert(!"invalid cursor pos!");
 280     return -1; /* not reached */
 281 }
 282
 283 int c2diff(int w, int h, int cx, int cy, int button)
 284 {
 285     int diff = 0;
 286
 287     assert(IS_CURSOR_MOVE(button));
 288
 289     /* Obvious moves around edge. */
 290     if (cy == -1)
 291         diff = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : diff;
 292     if (cy == h)
 293         diff = (button == CURSOR_RIGHT) ? -1 : (button == CURSOR_LEFT) ? +1 : diff;
 294     if (cx == -1)
 295         diff = (button == CURSOR_UP) ? +1 : (button == CURSOR_DOWN) ? -1 : diff;
 296     if (cx == w)
 297         diff = (button == CURSOR_UP) ? -1 : (button == CURSOR_DOWN) ? +1 : diff;
 298
 299     if (button == CURSOR_LEFT && cx == w && (cy == 0 || cy == h-1))
 300         diff = (cy == 0) ? -1 : +1;
 301     if (button == CURSOR_RIGHT && cx == -1 && (cy == 0 || cy == h-1))
 302         diff = (cy == 0) ? +1 : -1;
 303     if (button == CURSOR_DOWN && cy == -1 && (cx == 0 || cx == w-1))
 304         diff = (cx == 0) ? -1 : +1;
 305     if (button == CURSOR_UP && cy == h && (cx == 0 || cx == w-1))
 306         diff = (cx == 0) ? +1 : -1;
 307
 308     debug(("cx,cy = %d,%d; w%d h%d, diff = %d", cx, cy, w, h, diff));
 309     return diff;
 310 }
 311
 312 void pos2c(int w, int h, int pos, int *cx, int *cy)
 313 {
 314     int max = w+h+w+h;
 315
 316     pos = (pos + max) % max;
 317
 318     if (pos < w) {
 319         *cx = pos; *cy = -1; return;
 320     }
 321     pos -= w;
 322     if (pos < h) {
 323         *cx = w; *cy = pos; return;
 324     }
 325     pos -= h;
 326     if (pos < w) {
 327         *cx = w-pos-1; *cy = h; return;
 328     }
 329     pos -= w;
 330     if (pos < h) {
 331       *cx = -1; *cy = h-pos-1; return;
 332     }
 333     assert(!"invalid pos, huh?"); /* limited by % above! */
 334 }
 335
 336 void draw_text_outline(drawing *dr, int x, int y, int fonttype,
 337                        int fontsize, int align,
 338                        int text_colour, int outline_colour, char *text)
 339 {
 340     if (outline_colour > -1) {
 341         draw_text(dr, x-1, y, fonttype, fontsize, align, outline_colour, text);
 342         draw_text(dr, x+1, y, fonttype, fontsize, align, outline_colour, text);
 343         draw_text(dr, x, y-1, fonttype, fontsize, align, outline_colour, text);
 344         draw_text(dr, x, y+1, fonttype, fontsize, align, outline_colour, text);
 345     }
 346     draw_text(dr, x, y, fonttype, fontsize, align, text_colour, text);
 347 }
 348
 349 /* vim: set shiftwidth=4 tabstop=8: */