123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664 |
- /*
- * misc.c: Miscellaneous helpful functions.
- */
- #include <assert.h>
- #include <ctype.h>
- #ifdef NO_TGMATH_H
- # include <math.h>
- #else
- # include <tgmath.h>
- #endif
- #include <stdlib.h>
- #include <string.h>
- #include <stdio.h>
- #include "puzzles.h"
- char MOVE_UI_UPDATE[] = "";
- char MOVE_NO_EFFECT[] = "";
- char MOVE_UNUSED[] = "";
- void free_cfg(config_item *cfg)
- {
- config_item *i;
- for (i = cfg; i->type != C_END; i++)
- if (i->type == C_STRING)
- sfree(i->u.string.sval);
- sfree(cfg);
- }
- void free_keys(key_label *keys, int nkeys)
- {
- int i;
- for(i = 0; i < nkeys; i++)
- sfree(keys[i].label);
- sfree(keys);
- }
- /*
- * The Mines (among others) game descriptions contain the location of every
- * mine, and can therefore be used to cheat.
- *
- * It would be pointless to attempt to _prevent_ this form of
- * cheating by encrypting the description, since Mines is
- * open-source so anyone can find out the encryption key. However,
- * I think it is worth doing a bit of gentle obfuscation to prevent
- * _accidental_ spoilers: if you happened to note that the game ID
- * starts with an F, for example, you might be unable to put the
- * knowledge of those mines out of your mind while playing. So,
- * just as discussions of film endings are rot13ed to avoid
- * spoiling it for people who don't want to be told, we apply a
- * keyless, reversible, but visually completely obfuscatory masking
- * function to the mine bitmap.
- */
- void obfuscate_bitmap(unsigned char *bmp, int bits, bool decode)
- {
- int bytes, firsthalf, secondhalf;
- struct step {
- unsigned char *seedstart;
- int seedlen;
- unsigned char *targetstart;
- int targetlen;
- } steps[2];
- int i, j;
- /*
- * My obfuscation algorithm is similar in concept to the OAEP
- * encoding used in some forms of RSA. Here's a specification
- * of it:
- *
- * + We have a `masking function' which constructs a stream of
- * pseudorandom bytes from a seed of some number of input
- * bytes.
- *
- * + We pad out our input bit stream to a whole number of
- * bytes by adding up to 7 zero bits on the end. (In fact
- * the bitmap passed as input to this function will already
- * have had this done in practice.)
- *
- * + We divide the _byte_ stream exactly in half, rounding the
- * half-way position _down_. So an 81-bit input string, for
- * example, rounds up to 88 bits or 11 bytes, and then
- * dividing by two gives 5 bytes in the first half and 6 in
- * the second half.
- *
- * + We generate a mask from the second half of the bytes, and
- * XOR it over the first half.
- *
- * + We generate a mask from the (encoded) first half of the
- * bytes, and XOR it over the second half. Any null bits at
- * the end which were added as padding are cleared back to
- * zero even if this operation would have made them nonzero.
- *
- * To de-obfuscate, the steps are precisely the same except
- * that the final two are reversed.
- *
- * Finally, our masking function. Given an input seed string of
- * bytes, the output mask consists of concatenating the SHA-1
- * hashes of the seed string and successive decimal integers,
- * starting from 0.
- */
- bytes = (bits + 7) / 8;
- firsthalf = bytes / 2;
- secondhalf = bytes - firsthalf;
- steps[decode ? 1 : 0].seedstart = bmp + firsthalf;
- steps[decode ? 1 : 0].seedlen = secondhalf;
- steps[decode ? 1 : 0].targetstart = bmp;
- steps[decode ? 1 : 0].targetlen = firsthalf;
- steps[decode ? 0 : 1].seedstart = bmp;
- steps[decode ? 0 : 1].seedlen = firsthalf;
- steps[decode ? 0 : 1].targetstart = bmp + firsthalf;
- steps[decode ? 0 : 1].targetlen = secondhalf;
- for (i = 0; i < 2; i++) {
- SHA_State base, final;
- unsigned char digest[20];
- char numberbuf[80];
- int digestpos = 20, counter = 0;
- SHA_Init(&base);
- SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen);
- for (j = 0; j < steps[i].targetlen; j++) {
- if (digestpos >= 20) {
- sprintf(numberbuf, "%d", counter++);
- final = base;
- SHA_Bytes(&final, numberbuf, strlen(numberbuf));
- SHA_Final(&final, digest);
- digestpos = 0;
- }
- steps[i].targetstart[j] ^= digest[digestpos++];
- }
- /*
- * Mask off the pad bits in the final byte after both steps.
- */
- if (bits % 8)
- bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8));
- }
- }
- /* err, yeah, these two pretty much rely on unsigned char being 8 bits.
- * Platforms where this is not the case probably have bigger problems
- * than just making these two work, though... */
- char *bin2hex(const unsigned char *in, int inlen)
- {
- char *ret = snewn(inlen*2 + 1, char), *p = ret;
- int i;
- for (i = 0; i < inlen*2; i++) {
- int v = in[i/2];
- if (i % 2 == 0) v >>= 4;
- *p++ = "0123456789abcdef"[v & 0xF];
- }
- *p = '\0';
- return ret;
- }
- unsigned char *hex2bin(const char *in, int outlen)
- {
- unsigned char *ret = snewn(outlen, unsigned char);
- int i;
- memset(ret, 0, outlen*sizeof(unsigned char));
- for (i = 0; i < outlen*2; i++) {
- int c = in[i];
- int v;
- assert(c != 0);
- if (c >= '0' && c <= '9')
- v = c - '0';
- else if (c >= 'a' && c <= 'f')
- v = c - 'a' + 10;
- else if (c >= 'A' && c <= 'F')
- v = c - 'A' + 10;
- else
- v = 0;
- ret[i / 2] |= v << (4 * (1 - (i % 2)));
- }
- return ret;
- }
- char *fgetline(FILE *fp)
- {
- char *ret = snewn(512, char);
- int size = 512, len = 0;
- while (fgets(ret + len, size - len, fp)) {
- len += strlen(ret + len);
- if (ret[len-1] == '\n')
- break; /* got a newline, we're done */
- size = len + 512;
- ret = sresize(ret, size, char);
- }
- if (len == 0) { /* first fgets returned NULL */
- sfree(ret);
- return NULL;
- }
- ret[len] = '\0';
- return ret;
- }
- int getenv_bool(const char *name, int dflt)
- {
- char *env = getenv(name);
- if (env == NULL) return dflt;
- if (strchr("yYtT", env[0])) return true;
- return false;
- }
- /* Utility functions for colour manipulation. */
- static float colour_distance(const float a[3], const float b[3])
- {
- return (float)sqrt((a[0]-b[0]) * (a[0]-b[0]) +
- (a[1]-b[1]) * (a[1]-b[1]) +
- (a[2]-b[2]) * (a[2]-b[2]));
- }
- void colour_mix(const float src1[3], const float src2[3], float p, float dst[3])
- {
- int i;
- for (i = 0; i < 3; i++)
- dst[i] = src1[i] * (1.0F - p) + src2[i] * p;
- }
- void game_mkhighlight_specific(frontend *fe, float *ret,
- int background, int highlight, int lowlight)
- {
- static const float black[3] = { 0.0F, 0.0F, 0.0F };
- static const float white[3] = { 1.0F, 1.0F, 1.0F };
- float db, dw;
- int i;
- /*
- * New geometric highlight-generation algorithm: Draw a line from
- * the base colour to white. The point K distance along this line
- * from the base colour is the highlight colour. Similarly, draw
- * a line from the base colour to black. The point on this line
- * at a distance K from the base colour is the shadow. If either
- * of these colours is imaginary (for reasonable K at most one
- * will be), _extrapolate_ the base colour along the same line
- * until it's a distance K from white (or black) and start again
- * with that as the base colour.
- *
- * This preserves the hue of the base colour, ensures that of the
- * three the base colour is the most saturated, and only ever
- * flattens the highlight and shadow to pure white or pure black.
- *
- * K must be at most sqrt(3)/2, or mid grey would be too close to
- * both white and black. Here K is set to sqrt(3)/6 so that this
- * code produces the same results as the former code in the common
- * case where the background is grey and the highlight saturates
- * to white.
- */
- const float k = sqrt(3)/6.0F;
- if (lowlight >= 0) {
- db = colour_distance(&ret[background*3], black);
- if (db < k) {
- for (i = 0; i < 3; i++) ret[lowlight*3+i] = black[i];
- if (db == 0.0F)
- colour_mix(black, white, k/sqrt(3), &ret[background*3]);
- else
- colour_mix(black, &ret[background*3], k/db, &ret[background*3]);
- } else {
- colour_mix(&ret[background*3], black, k/db, &ret[lowlight*3]);
- }
- }
- if (highlight >= 0) {
- dw = colour_distance(&ret[background*3], white);
- if (dw < k) {
- for (i = 0; i < 3; i++) ret[highlight*3+i] = white[i];
- if (dw == 0.0F)
- colour_mix(white, black, k/sqrt(3), &ret[background*3]);
- else
- colour_mix(white, &ret[background*3], k/dw, &ret[background*3]);
- /* Background has changed; recalculate lowlight. */
- if (lowlight >= 0)
- colour_mix(&ret[background*3], black, k/db, &ret[lowlight*3]);
- } else {
- colour_mix(&ret[background*3], white, k/dw, &ret[highlight*3]);
- }
- }
- }
- void game_mkhighlight(frontend *fe, float *ret,
- int background, int highlight, int lowlight)
- {
- frontend_default_colour(fe, &ret[background * 3]);
- game_mkhighlight_specific(fe, ret, background, highlight, lowlight);
- }
- static void memswap(void *av, void *bv, int size)
- {
- char tmpbuf[512];
- char *a = av, *b = bv;
- while (size > 0) {
- int thislen = min(size, sizeof(tmpbuf));
- memcpy(tmpbuf, a, thislen);
- memcpy(a, b, thislen);
- memcpy(b, tmpbuf, thislen);
- a += thislen;
- b += thislen;
- size -= thislen;
- }
- }
- void shuffle(void *array, int nelts, int eltsize, random_state *rs)
- {
- char *carray = (char *)array;
- int i;
- for (i = nelts; i-- > 1 ;) {
- int j = random_upto(rs, i+1);
- if (j != i)
- memswap(carray + eltsize * i, carray + eltsize * j, eltsize);
- }
- }
- void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour)
- {
- int x0 = x, x1 = x+w-1, y0 = y, y1 = y+h-1;
- int coords[8];
- coords[0] = x0;
- coords[1] = y0;
- coords[2] = x0;
- coords[3] = y1;
- coords[4] = x1;
- coords[5] = y1;
- coords[6] = x1;
- coords[7] = y0;
- draw_polygon(dr, coords, 4, -1, colour);
- }
- void draw_rect_corners(drawing *dr, int cx, int cy, int r, int col)
- {
- draw_line(dr, cx - r, cy - r, cx - r, cy - r/2, col);
- draw_line(dr, cx - r, cy - r, cx - r/2, cy - r, col);
- draw_line(dr, cx - r, cy + r, cx - r, cy + r/2, col);
- draw_line(dr, cx - r, cy + r, cx - r/2, cy + r, col);
- draw_line(dr, cx + r, cy - r, cx + r, cy - r/2, col);
- draw_line(dr, cx + r, cy - r, cx + r/2, cy - r, col);
- draw_line(dr, cx + r, cy + r, cx + r, cy + r/2, col);
- draw_line(dr, cx + r, cy + r, cx + r/2, cy + r, col);
- }
- void move_cursor(int button, int *x, int *y, int maxw, int maxh, bool wrap)
- {
- int dx = 0, dy = 0;
- switch (button) {
- case CURSOR_UP: dy = -1; break;
- case CURSOR_DOWN: dy = 1; break;
- case CURSOR_RIGHT: dx = 1; break;
- case CURSOR_LEFT: dx = -1; break;
- default: return;
- }
- if (wrap) {
- *x = (*x + dx + maxw) % maxw;
- *y = (*y + dy + maxh) % maxh;
- } else {
- *x = min(max(*x+dx, 0), maxw - 1);
- *y = min(max(*y+dy, 0), maxh - 1);
- }
- }
- /* Used in netslide.c and sixteen.c for cursor movement around edge. */
- int c2pos(int w, int h, int cx, int cy)
- {
- if (cy == -1)
- return cx; /* top row, 0 .. w-1 (->) */
- else if (cx == w)
- return w + cy; /* R col, w .. w+h -1 (v) */
- else if (cy == h)
- return w + h + (w-cx-1); /* bottom row, w+h .. w+h+w-1 (<-) */
- else if (cx == -1)
- return w + h + w + (h-cy-1); /* L col, w+h+w .. w+h+w+h-1 (^) */
- assert(!"invalid cursor pos!");
- return -1; /* not reached */
- }
- int c2diff(int w, int h, int cx, int cy, int button)
- {
- int diff = 0;
- assert(IS_CURSOR_MOVE(button));
- /* Obvious moves around edge. */
- if (cy == -1)
- diff = (button == CURSOR_RIGHT) ? +1 : (button == CURSOR_LEFT) ? -1 : diff;
- if (cy == h)
- diff = (button == CURSOR_RIGHT) ? -1 : (button == CURSOR_LEFT) ? +1 : diff;
- if (cx == -1)
- diff = (button == CURSOR_UP) ? +1 : (button == CURSOR_DOWN) ? -1 : diff;
- if (cx == w)
- diff = (button == CURSOR_UP) ? -1 : (button == CURSOR_DOWN) ? +1 : diff;
- if (button == CURSOR_LEFT && cx == w && (cy == 0 || cy == h-1))
- diff = (cy == 0) ? -1 : +1;
- if (button == CURSOR_RIGHT && cx == -1 && (cy == 0 || cy == h-1))
- diff = (cy == 0) ? +1 : -1;
- if (button == CURSOR_DOWN && cy == -1 && (cx == 0 || cx == w-1))
- diff = (cx == 0) ? -1 : +1;
- if (button == CURSOR_UP && cy == h && (cx == 0 || cx == w-1))
- diff = (cx == 0) ? +1 : -1;
- debug(("cx,cy = %d,%d; w%d h%d, diff = %d", cx, cy, w, h, diff));
- return diff;
- }
- void pos2c(int w, int h, int pos, int *cx, int *cy)
- {
- int max = w+h+w+h;
- pos = (pos + max) % max;
- if (pos < w) {
- *cx = pos; *cy = -1; return;
- }
- pos -= w;
- if (pos < h) {
- *cx = w; *cy = pos; return;
- }
- pos -= h;
- if (pos < w) {
- *cx = w-pos-1; *cy = h; return;
- }
- pos -= w;
- if (pos < h) {
- *cx = -1; *cy = h-pos-1; return;
- }
- assert(!"invalid pos, huh?"); /* limited by % above! */
- }
- void draw_text_outline(drawing *dr, int x, int y, int fonttype,
- int fontsize, int align,
- int text_colour, int outline_colour, const char *text)
- {
- if (outline_colour > -1) {
- draw_text(dr, x-1, y, fonttype, fontsize, align, outline_colour, text);
- draw_text(dr, x+1, y, fonttype, fontsize, align, outline_colour, text);
- draw_text(dr, x, y-1, fonttype, fontsize, align, outline_colour, text);
- draw_text(dr, x, y+1, fonttype, fontsize, align, outline_colour, text);
- }
- draw_text(dr, x, y, fonttype, fontsize, align, text_colour, text);
- }
- /* kludge for sprintf() in Rockbox not supporting "%-8.8s" */
- void copy_left_justified(char *buf, size_t sz, const char *str)
- {
- size_t len = strlen(str);
- assert(sz > 0);
- memset(buf, ' ', sz - 1);
- assert(len <= sz - 1);
- memcpy(buf, str, len);
- buf[sz - 1] = 0;
- }
- /* Returns a dynamically allocated label for a generic button.
- * Game-specific buttons should go into the `label' field of key_label
- * instead. */
- char *button2label(int button)
- {
- /* check if it's a keyboard button */
- if(('A' <= button && button <= 'Z') ||
- ('a' <= button && button <= 'z') ||
- ('0' <= button && button <= '9') )
- {
- char str[2];
- str[0] = button;
- str[1] = '\0';
- return dupstr(str);
- }
- switch(button)
- {
- case CURSOR_UP:
- return dupstr("Up");
- case CURSOR_DOWN:
- return dupstr("Down");
- case CURSOR_LEFT:
- return dupstr("Left");
- case CURSOR_RIGHT:
- return dupstr("Right");
- case CURSOR_SELECT:
- return dupstr("Select");
- case '\b':
- return dupstr("Clear");
- default:
- fatal("unknown generic key");
- }
- /* should never get here */
- return NULL;
- }
- char *make_prefs_path(const char *dir, const char *sep,
- const game *game, const char *suffix)
- {
- size_t dirlen = strlen(dir);
- size_t seplen = strlen(sep);
- size_t gamelen = strlen(game->name);
- size_t suffixlen = strlen(suffix);
- char *path, *p;
- const char *q;
- if (!dir || !sep || !game || !suffix)
- return NULL;
- path = snewn(dirlen + seplen + gamelen + suffixlen + 1, char);
- p = path;
- memcpy(p, dir, dirlen);
- p += dirlen;
- memcpy(p, sep, seplen);
- p += seplen;
- for (q = game->name; *q; q++)
- if (*q != ' ')
- *p++ = tolower((unsigned char)*q);
- memcpy(p, suffix, suffixlen);
- p += suffixlen;
- *p = '\0';
- return path;
- }
- /*
- * Calculate the nearest integer to n*sqrt(k), via a bitwise algorithm
- * that avoids floating point.
- *
- * (It would probably be OK in practice to use floating point, but I
- * felt like overengineering it for fun. With FP, there's at least a
- * theoretical risk of rounding the wrong way, due to the three
- * successive roundings involved - rounding sqrt(k), rounding its
- * product with n, and then rounding to the nearest integer. This
- * approach avoids that: it's exact.)
- */
- int n_times_root_k(int n_signed, int k)
- {
- unsigned x, r, m;
- int sign = n_signed < 0 ? -1 : +1;
- unsigned n = n_signed * sign;
- unsigned bitpos;
- /*
- * Method:
- *
- * We transform m gradually from zero into n, by multiplying it by
- * 2 in each step and optionally adding 1, so that it's always
- * floor(n/2^something).
- *
- * At the start of each step, x is the largest integer less than
- * or equal to m*sqrt(k). We transform m to 2m+bit, and therefore
- * we must transform x to 2x+something to match. The 'something'
- * we add to 2x is at most floor(sqrt(k))+2. (Worst case is if m
- * sqrt(k) was equal to x + 1-eps for some tiny eps, and then the
- * incoming bit of m is 1, so that (2m+1)sqrt(k) =
- * 2x+2+sqrt(k)-2eps.)
- *
- * To compute this, we also track the residual value r such that
- * x^2+r = km^2.
- *
- * The algorithm below is very similar to the usual approach for
- * taking the square root of an integer in binary. The wrinkle is
- * that we have an integer multiplier, i.e. we're computing
- * n*sqrt(k) rather than just sqrt(k). Of course in principle we
- * could just take sqrt(n^2k), but we'd need an integer twice the
- * width to hold n^2. Pulling out n and treating it specially
- * makes overflow less likely.
- */
- x = r = m = 0;
- for (bitpos = UINT_MAX & ~(UINT_MAX >> 1); bitpos; bitpos >>= 1) {
- unsigned a, b = (n & bitpos) ? 1 : 0;
- /*
- * Check invariants. We expect that x^2 + r = km^2 (i.e. our
- * residual term is correct), and also that r < 2x+1 (because
- * if not, then we could replace x with x+1 and still get a
- * value that made r non-negative, i.e. x would not be the
- * _largest_ integer less than m sqrt(k)).
- */
- assert(x*x + r == k*m*m);
- assert(r < 2*x+1);
- /*
- * We're going to replace m with 2m+b, and x with 2x+a for
- * some a we haven't decided on yet.
- *
- * The new value of the residual will therefore be
- *
- * k (2m+b)^2 - (2x+a)^2
- * = (4km^2 + 4kmb + kb^2) - (4x^2 + 4xa + a^2)
- * = 4 (km^2 - x^2) + 4kmb + kb^2 - 4xa - a^2
- * = 4r + 4kmb + kb^2 - 4xa - a^2 (because r = km^2 - x^2)
- * = 4r + (4m + 1)kb - 4xa - a^2 (b is 0 or 1, so b = b^2)
- */
- for (a = 0;; a++) {
- /* If we made this routine handle square roots of numbers
- * significantly bigger than 3 or 5 then it would be
- * sensible to make this a binary search. Here, it hardly
- * seems important. */
- unsigned pos = 4*r + k*b*(4*m + 1);
- unsigned neg = 4*a*x + a*a;
- if (pos < neg)
- break; /* this value of a is too big */
- }
- /* The above loop will have terminated with a one too big. So
- * now decrementing a will give us the right value to add. */
- a--;
- r = 4*r + b*k*(4*m + 1) - (4*a*x + a*a);
- m = 2*m+b;
- x = 2*x+a;
- }
- /*
- * Finally, round to the nearest integer. At present, x is the
- * largest integer that is _at most_ m sqrt(k). But we want the
- * _nearest_ integer, whether that's rounded up or down. So check
- * whether (x + 1/2) is still less than m sqrt(k), i.e. whether
- * (x + 1/2)^2 < km^2; if it is, then we increment x.
- *
- * We have km^2 - (x + 1/2)^2 = km^2 - x^2 - x - 1/4
- * = r - x - 1/4
- *
- * and since r and x are integers, this is greater than 0 if and
- * only if r > x.
- *
- * (There's no need to worry about tie-breaking exact halfway
- * rounding cases. sqrt(k) is irrational, so none such exist.)
- */
- if (r > x)
- x++;
- /*
- * Put the sign back on, and convert back from unsigned to int.
- */
- if (sign == +1) {
- return x;
- } else {
- /* Be a little careful to avoid compilers deciding I've just
- * perpetrated signed-integer overflow. This should optimise
- * down to no actual code. */
- return INT_MIN + (int)(-x - (unsigned)INT_MIN);
- }
- }
- /* vim: set shiftwidth=4 tabstop=8: */
|