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 char UI_UPDATE[] = "";
  13
  14 void free_cfg(config_item *cfg)
  15 {
  16     config_item *i;
  17
  18     for (i = cfg; i->type != C_END; i++)
  19         if (i->type == C_STRING)
  20             sfree(i->u.string.sval);
  21     sfree(cfg);
  22 }
  23
  24 /*
  25  * The Mines (among others) game descriptions contain the location of every
  26  * mine, and can therefore be used to cheat.
  27  *
  28  * It would be pointless to attempt to _prevent_ this form of
  29  * cheating by encrypting the description, since Mines is
  30  * open-source so anyone can find out the encryption key. However,
  31  * I think it is worth doing a bit of gentle obfuscation to prevent
  32  * _accidental_ spoilers: if you happened to note that the game ID
  33  * starts with an F, for example, you might be unable to put the
  34  * knowledge of those mines out of your mind while playing. So,
  35  * just as discussions of film endings are rot13ed to avoid
  36  * spoiling it for people who don't want to be told, we apply a
  37  * keyless, reversible, but visually completely obfuscatory masking
  38  * function to the mine bitmap.
  39  */
  40 void obfuscate_bitmap(unsigned char *bmp, int bits, int decode)
  41 {
  42     int bytes, firsthalf, secondhalf;
  43     struct step {
  44         unsigned char *seedstart;
  45         int seedlen;
  46         unsigned char *targetstart;
  47         int targetlen;
  48     } steps[2];
  49     int i, j;
  50
  51     /*
  52      * My obfuscation algorithm is similar in concept to the OAEP
  53      * encoding used in some forms of RSA. Here's a specification
  54      * of it:
  55      *
  56      *  + We have a `masking function' which constructs a stream of
  57      *    pseudorandom bytes from a seed of some number of input
  58      *    bytes.
  59      *
  60      *  + We pad out our input bit stream to a whole number of
  61      *    bytes by adding up to 7 zero bits on the end. (In fact
  62      *    the bitmap passed as input to this function will already
  63      *    have had this done in practice.)
  64      *
  65      *  + We divide the _byte_ stream exactly in half, rounding the
  66      *    half-way position _down_. So an 81-bit input string, for
  67      *    example, rounds up to 88 bits or 11 bytes, and then
  68      *    dividing by two gives 5 bytes in the first half and 6 in
  69      *    the second half.
  70      *
  71      *  + We generate a mask from the second half of the bytes, and
  72      *    XOR it over the first half.
  73      *
  74      *  + We generate a mask from the (encoded) first half of the
  75      *    bytes, and XOR it over the second half. Any null bits at
  76      *    the end which were added as padding are cleared back to
  77      *    zero even if this operation would have made them nonzero.
  78      *
  79      * To de-obfuscate, the steps are precisely the same except
  80      * that the final two are reversed.
  81      *
  82      * Finally, our masking function. Given an input seed string of
  83      * bytes, the output mask consists of concatenating the SHA-1
  84      * hashes of the seed string and successive decimal integers,
  85      * starting from 0.
  86      */
  87
  88     bytes = (bits + 7) / 8;
  89     firsthalf = bytes / 2;
  90     secondhalf = bytes - firsthalf;
  91
  92     steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
  93     steps[decode ? 1 : 0].seedlen = secondhalf;
  94     steps[decode ? 1 : 0].targetstart = bmp;
  95     steps[decode ? 1 : 0].targetlen = firsthalf;
  96
  97     steps[decode ? 0 : 1].seedstart = bmp;
  98     steps[decode ? 0 : 1].seedlen = firsthalf;
  99     steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
 100     steps[decode ? 0 : 1].targetlen = secondhalf;
 101
 102     for (i = 0; i < 2; i++) {
 103         SHA_State base, final;
 104         unsigned char digest[20];
 105         char numberbuf[80];
 106         int digestpos = 20, counter = 0;
 107
 108         SHA_Init(&base);
 109         SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
 110
 111         for (j = 0; j < steps[i].targetlen; j++) {
 112             if (digestpos >= 20) {
 113                 sprintf(numberbuf, "%d", counter++);
 114                 final = base;
 115                 SHA_Bytes(&final, numberbuf, strlen(numberbuf));
 116                 SHA_Final(&final, digest);
 117                 digestpos = 0;
 118             }
 119             steps[i].targetstart[j] ^= digest[digestpos++];
 120         }
 121
 122         /*
 123          * Mask off the pad bits in the final byte after both steps.
 124          */
 125         if (bits % 8)
 126             bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
 127     }
 128 }
 129
 130 /* err, yeah, these two pretty much rely on unsigned char being 8 bits.
 131  * Platforms where this is not the case probably have bigger problems
 132  * than just making these two work, though... */
 133 char *bin2hex(const unsigned char *in, int inlen)
 134 {
 135     char *ret = snewn(inlen*2 + 1, char), *p = ret;
 136     int i;
 137
 138     for (i = 0; i < inlen*2; i++) {
 139         int v = in[i/2];
 140         if (i % 2 == 0) v >>= 4;
 141         *p++ = "0123456789abcdef"[v & 0xF];
 142     }
 143     *p = '\0';
 144     return ret;
 145 }
 146
 147 unsigned char *hex2bin(const char *in, int outlen)
 148 {
 149     unsigned char *ret = snewn(outlen, unsigned char);
 150     int i;
 151
 152     memset(ret, 0, outlen*sizeof(unsigned char));
 153     for (i = 0; i < outlen*2; i++) {
 154         int c = in[i];
 155         int v;
 156
 157         assert(c != 0);
 158         if (c >= '0' && c <= '9')
 159             v = c - '0';
 160         else if (c >= 'a' && c <= 'f')
 161             v = c - 'a' + 10;
 162         else if (c >= 'A' && c <= 'F')
 163             v = c - 'A' + 10;
 164         else
 165             v = 0;
 166
 167         ret[i / 2] |= v << (4 * (1 - (i % 2)));
 168     }
 169     return ret;
 170 }
 171
 172 void game_mkhighlight_specific(frontend *fe, float *ret,
 173                                int background, int highlight, int lowlight)
 174 {
 175     float max;
 176     int i;
 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         if (highlight >= 0)
 193             ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F;
 194         if (lowlight >= 0)
 195             ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F;
 196     }
 197 }
 198
 199 void game_mkhighlight(frontend *fe, float *ret,
 200                       int background, int highlight, int lowlight)
 201 {
 202     frontend_default_colour(fe, &ret[background * 3]);
 203     game_mkhighlight_specific(fe, ret, background, highlight, lowlight);
 204 }
 205
 206 static void memswap(void *av, void *bv, int size)
 207 {
 208     char tmpbuf[512];
 209     char *a = av, *b = bv;
 210
 211     while (size > 0) {
 212         int thislen = min(size, sizeof(tmpbuf));
 213         memcpy(tmpbuf, a, thislen);
 214         memcpy(a, b, thislen);
 215         memcpy(b, tmpbuf, thislen);
 216         a += thislen;
 217         b += thislen;
 218         size -= thislen;
 219     }
 220 }
 221
 222 void shuffle(void *array, int nelts, int eltsize, random_state *rs)
 223 {
 224     char *carray = (char *)array;
 225     int i;
 226
 227     for (i = nelts; i-- > 1 ;) {
 228         int j = random_upto(rs, i+1);
 229         if (j != i)
 230             memswap(carray + eltsize * i, carray + eltsize * j, eltsize);
 231     }
 232 }
 233
 234 void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour)
 235 {
 236     int x0 = x, x1 = x+w-1, y0 = y, y1 = y+h-1;
 237     int coords[8];
 238
 239     coords[0] = x0;
 240     coords[1] = y0;
 241     coords[2] = x0;
 242     coords[3] = y1;
 243     coords[4] = x1;
 244     coords[5] = y1;
 245     coords[6] = x1;
 246     coords[7] = y0;
 247
 248     draw_polygon(dr, coords, 4, -1, colour);
 249 }
 250
 251 void draw_rect_corners(drawing *dr, int cx, int cy, int r, int col)
 252 {
 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     draw_line(dr, cx + r, cy + r, cx + r, cy + r/2, col);
 260     draw_line(dr, cx + r, cy + r, cx + r/2, cy + r, col);
 261 }
 262
 263 void move_cursor(int button, int *x, int *y, int maxw, int maxh, int wrap)
 264 {
 265     int dx = 0, dy = 0;
 266     switch (button) {
 267     case CURSOR_UP:         dy = -1; break;
 268     case CURSOR_DOWN:       dy = 1; break;
 269     case CURSOR_RIGHT:      dx = 1; break;
 270     case CURSOR_LEFT:       dx = -1; break;
 271     default: return;
 272     }
 273     if (wrap) {
 274         *x = (*x + dx + maxw) % maxw;
 275         *y = (*y + dy + maxh) % maxh;
 276     } else {
 277         *x = min(max(*x+dx, 0), maxw - 1);
 278         *y = min(max(*y+dy, 0), maxh - 1);
 279     }
 280 }
 281
 282 /* Used in netslide.c and sixteen.c for cursor movement around edge. */
 283
 284 int c2pos(int w, int h, int cx, int cy)
 285 {
 286     if (cy == -1)
 287         return cx;                      /* top row, 0 .. w-1 (->) */
 288     else if (cx == w)
 289         return w + cy;                  /* R col, w .. w+h -1 (v) */
 290     else if (cy == h)
 291         return w + h + (w-cx-1);        /* bottom row, w+h .. w+h+w-1 (<-) */
 292     else if (cx == -1)
 293         return w + h + w + (h-cy-1);    /* L col, w+h+w .. w+h+w+h-1 (^) */
 294
 295     assert(!"invalid cursor pos!");
 296     return -1; /* not reached */
 297 }
 298
 299 int c2diff(int w, int h, int cx, int cy, int button)
 300 {
 301     int diff = 0;
 302
 303     assert(IS_CURSOR_MOVE(button));
 304
 305     /* Obvious moves around edge. */
 306     if (cy == -1)
 307         diff = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : diff;
 308     if (cy == h)
 309         diff = (button == CURSOR_RIGHT) ? -1 : (button == CURSOR_LEFT) ? +1 : diff;
 310     if (cx == -1)
 311         diff = (button == CURSOR_UP) ? +1 : (button == CURSOR_DOWN) ? -1 : diff;
 312     if (cx == w)
 313         diff = (button == CURSOR_UP) ? -1 : (button == CURSOR_DOWN) ? +1 : diff;
 314
 315     if (button == CURSOR_LEFT && cx == w && (cy == 0 || cy == h-1))
 316         diff = (cy == 0) ? -1 : +1;
 317     if (button == CURSOR_RIGHT && cx == -1 && (cy == 0 || cy == h-1))
 318         diff = (cy == 0) ? +1 : -1;
 319     if (button == CURSOR_DOWN && cy == -1 && (cx == 0 || cx == w-1))
 320         diff = (cx == 0) ? -1 : +1;
 321     if (button == CURSOR_UP && cy == h && (cx == 0 || cx == w-1))
 322         diff = (cx == 0) ? +1 : -1;
 323
 324     debug(("cx,cy = %d,%d; w%d h%d, diff = %d", cx, cy, w, h, diff));
 325     return diff;
 326 }
 327
 328 void pos2c(int w, int h, int pos, int *cx, int *cy)
 329 {
 330     int max = w+h+w+h;
 331
 332     pos = (pos + max) % max;
 333
 334     if (pos < w) {
 335         *cx = pos; *cy = -1; return;
 336     }
 337     pos -= w;
 338     if (pos < h) {
 339         *cx = w; *cy = pos; return;
 340     }
 341     pos -= h;
 342     if (pos < w) {
 343         *cx = w-pos-1; *cy = h; return;
 344     }
 345     pos -= w;
 346     if (pos < h) {
 347       *cx = -1; *cy = h-pos-1; return;
 348     }
 349     assert(!"invalid pos, huh?"); /* limited by % above! */
 350 }
 351
 352 void draw_text_outline(drawing *dr, int x, int y, int fonttype,
 353                        int fontsize, int align,
 354                        int text_colour, int outline_colour, const char *text)
 355 {
 356     if (outline_colour > -1) {
 357         draw_text(dr, x-1, y, fonttype, fontsize, align, outline_colour, text);
 358         draw_text(dr, x+1, y, fonttype, fontsize, align, outline_colour, text);
 359         draw_text(dr, x, y-1, fonttype, fontsize, align, outline_colour, text);
 360         draw_text(dr, x, y+1, fonttype, fontsize, align, outline_colour, text);
 361     }
 362     draw_text(dr, x, y, fonttype, fontsize, align, text_colour, text);
 363
 364 }
 365
 366 /* kludge for sprintf() in Rockbox not supporting "%-8.8s" */
 367 void copy_left_justified(char *buf, size_t sz, const char *str)
 368 {
 369     size_t len = strlen(str);
 370     assert(sz > 0);
 371     memset(buf, ' ', sz - 1);
 372     assert(len <= sz - 1);
 373     memcpy(buf, str, len);
 374     buf[sz - 1] = 0;
 375 }
 376
 377 /* vim: set shiftwidth=4 tabstop=8: */