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         if (highlight >= 0)
 191             ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F;
 192         if (lowlight >= 0)
 193             ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F;
 194     }
 195 }
 196
 197 void game_mkhighlight(frontend *fe, float *ret,
 198                       int background, int highlight, int lowlight)
 199 {
 200     frontend_default_colour(fe, &ret[background * 3]);
 201     game_mkhighlight_specific(fe, ret, background, highlight, lowlight);
 202 }
 203
 204 static void memswap(void *av, void *bv, int size)
 205 {
 206     char tmpbuf[512];
 207     char *a = av, *b = bv;
 208
 209     while (size > 0) {
 210         int thislen = min(size, sizeof(tmpbuf));
 211         memcpy(tmpbuf, a, thislen);
 212         memcpy(a, b, thislen);
 213         memcpy(b, tmpbuf, thislen);
 214         a += thislen;
 215         b += thislen;
 216         size -= thislen;
 217     }
 218 }
 219
 220 void shuffle(void *array, int nelts, int eltsize, random_state *rs)
 221 {
 222     char *carray = (char *)array;
 223     int i;
 224
 225     for (i = nelts; i-- > 1 ;) {
 226         int j = random_upto(rs, i+1);
 227         if (j != i)
 228             memswap(carray + eltsize * i, carray + eltsize * j, eltsize);
 229     }
 230 }
 231
 232 void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour)
 233 {
 234     int x0 = x, x1 = x+w-1, y0 = y, y1 = y+h-1;
 235     int coords[8];
 236
 237     coords[0] = x0;
 238     coords[1] = y0;
 239     coords[2] = x0;
 240     coords[3] = y1;
 241     coords[4] = x1;
 242     coords[5] = y1;
 243     coords[6] = x1;
 244     coords[7] = y0;
 245
 246     draw_polygon(dr, coords, 4, -1, colour);
 247 }
 248
 249 void draw_rect_corners(drawing *dr, int cx, int cy, int r, int col)
 250 {
 251     draw_line(dr, cx - r, cy - r, cx - r, cy - r/2, col);
 252     draw_line(dr, cx - r, cy - r, cx - r/2, cy - r, col);
 253     draw_line(dr, cx - r, cy + r, cx - r, cy + r/2, col);
 254     draw_line(dr, cx - r, cy + r, cx - r/2, cy + r, col);
 255     draw_line(dr, cx + r, cy - r, cx + r, cy - r/2, col);
 256     draw_line(dr, cx + r, cy - r, cx + r/2, cy - r, col);
 257     draw_line(dr, cx + r, cy + r, cx + r, cy + r/2, col);
 258     draw_line(dr, cx + r, cy + r, cx + r/2, cy + r, col);
 259 }
 260
 261 void move_cursor(int button, int *x, int *y, int maxw, int maxh, int wrap)
 262 {
 263     int dx = 0, dy = 0;
 264     switch (button) {
 265     case CURSOR_UP:         dy = -1; break;
 266     case CURSOR_DOWN:       dy = 1; break;
 267     case CURSOR_RIGHT:      dx = 1; break;
 268     case CURSOR_LEFT:       dx = -1; break;
 269     default: return;
 270     }
 271     if (wrap) {
 272         *x = (*x + dx + maxw) % maxw;
 273         *y = (*y + dy + maxh) % maxh;
 274     } else {
 275         *x = min(max(*x+dx, 0), maxw - 1);
 276         *y = min(max(*y+dy, 0), maxh - 1);
 277     }
 278 }
 279
 280 /* Used in netslide.c and sixteen.c for cursor movement around edge. */
 281
 282 int c2pos(int w, int h, int cx, int cy)
 283 {
 284     if (cy == -1)
 285         return cx;                      /* top row, 0 .. w-1 (->) */
 286     else if (cx == w)
 287         return w + cy;                  /* R col, w .. w+h -1 (v) */
 288     else if (cy == h)
 289         return w + h + (w-cx-1);        /* bottom row, w+h .. w+h+w-1 (<-) */
 290     else if (cx == -1)
 291         return w + h + w + (h-cy-1);    /* L col, w+h+w .. w+h+w+h-1 (^) */
 292
 293     assert(!"invalid cursor pos!");
 294     return -1; /* not reached */
 295 }
 296
 297 int c2diff(int w, int h, int cx, int cy, int button)
 298 {
 299     int diff = 0;
 300
 301     assert(IS_CURSOR_MOVE(button));
 302
 303     /* Obvious moves around edge. */
 304     if (cy == -1)
 305         diff = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : diff;
 306     if (cy == h)
 307         diff = (button == CURSOR_RIGHT) ? -1 : (button == CURSOR_LEFT) ? +1 : diff;
 308     if (cx == -1)
 309         diff = (button == CURSOR_UP) ? +1 : (button == CURSOR_DOWN) ? -1 : diff;
 310     if (cx == w)
 311         diff = (button == CURSOR_UP) ? -1 : (button == CURSOR_DOWN) ? +1 : diff;
 312
 313     if (button == CURSOR_LEFT && cx == w && (cy == 0 || cy == h-1))
 314         diff = (cy == 0) ? -1 : +1;
 315     if (button == CURSOR_RIGHT && cx == -1 && (cy == 0 || cy == h-1))
 316         diff = (cy == 0) ? +1 : -1;
 317     if (button == CURSOR_DOWN && cy == -1 && (cx == 0 || cx == w-1))
 318         diff = (cx == 0) ? -1 : +1;
 319     if (button == CURSOR_UP && cy == h && (cx == 0 || cx == w-1))
 320         diff = (cx == 0) ? +1 : -1;
 321
 322     debug(("cx,cy = %d,%d; w%d h%d, diff = %d", cx, cy, w, h, diff));
 323     return diff;
 324 }
 325
 326 void pos2c(int w, int h, int pos, int *cx, int *cy)
 327 {
 328     int max = w+h+w+h;
 329
 330     pos = (pos + max) % max;
 331
 332     if (pos < w) {
 333         *cx = pos; *cy = -1; return;
 334     }
 335     pos -= w;
 336     if (pos < h) {
 337         *cx = w; *cy = pos; return;
 338     }
 339     pos -= h;
 340     if (pos < w) {
 341         *cx = w-pos-1; *cy = h; return;
 342     }
 343     pos -= w;
 344     if (pos < h) {
 345       *cx = -1; *cy = h-pos-1; return;
 346     }
 347     assert(!"invalid pos, huh?"); /* limited by % above! */
 348 }
 349
 350 void draw_text_outline(drawing *dr, int x, int y, int fonttype,
 351                        int fontsize, int align,
 352                        int text_colour, int outline_colour, char *text)
 353 {
 354     if (outline_colour > -1) {
 355         draw_text(dr, x-1, y, fonttype, fontsize, align, outline_colour, text);
 356         draw_text(dr, x+1, y, fonttype, fontsize, align, outline_colour, text);
 357         draw_text(dr, x, y-1, fonttype, fontsize, align, outline_colour, text);
 358         draw_text(dr, x, y+1, fonttype, fontsize, align, outline_colour, text);
 359     }
 360     draw_text(dr, x, y, fonttype, fontsize, align, text_colour, text);
 361
 362 }
 363
 364 /* kludge for sprintf() in Rockbox not supporting "%-8.8s" */
 365 void copy_left_justified(char *buf, size_t sz, const char *str)
 366 {
 367     size_t len = strlen(str);
 368     assert(sz > 0);
 369     memset(buf, ' ', sz - 1);
 370     assert(len <= sz - 1);
 371     memcpy(buf, str, len);
 372     buf[sz - 1] = 0;
 373 }
 374
 375 /* vim: set shiftwidth=4 tabstop=8: */