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