From 09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Mon, 22 Jul 2024 21:43:25 -0400 Subject: puzzles: resync with upstream This brings the puzzles source in sync with Simon's branch, commit fd304c5 (from March 2024), with some added Rockbox-specific compatibility changes: https://www.franklinwei.com/git/puzzles/commit/?h=rockbox-devel&id=516830d9d76bdfe64fe5ccf2a9b59c33f5c7c078 There are quite a lot of backend changes, including a new "Mosaic" puzzle. In addition, some new frontend changes were necessary: - New "Preferences" menu to access the user preferences system. - Enabled spacebar input for several games. Change-Id: I94c7df674089c92f32d5f07025f6a1059068af1e --- apps/plugins/puzzles/src/misc.c | 278 ++++++++++++++++++++++++++++++++++++---- 1 file changed, 250 insertions(+), 28 deletions(-) (limited to 'apps/plugins/puzzles/src/misc.c') diff --git a/apps/plugins/puzzles/src/misc.c b/apps/plugins/puzzles/src/misc.c index ed31acbbe4..f9eaf5d9b8 100644 --- a/apps/plugins/puzzles/src/misc.c +++ b/apps/plugins/puzzles/src/misc.c @@ -3,13 +3,21 @@ */ #include +#include +#ifdef NO_TGMATH_H +# include +#else +# include +#endif #include #include #include #include "puzzles.h" -char UI_UPDATE[] = ""; +char MOVE_UI_UPDATE[] = ""; +char MOVE_NO_EFFECT[] = ""; +char MOVE_UNUSED[] = ""; void free_cfg(config_item *cfg) { @@ -197,30 +205,85 @@ char *fgetline(FILE *fp) 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) { - float max; + 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; - /* - * Drop the background colour so that the highlight is - * noticeably brighter than it while still being under 1. + * 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. */ - max = ret[background*3]; - for (i = 1; i < 3; i++) - if (ret[background*3+i] > max) - max = ret[background*3+i]; - if (max * 1.2F > 1.0F) { - for (i = 0; i < 3; i++) - ret[background*3+i] /= (max * 1.2F); + 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]); + } } - - for (i = 0; i < 3; i++) { - if (highlight >= 0) - ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F; - if (lowlight >= 0) - ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F; + 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]); + } } } @@ -231,7 +294,7 @@ void game_mkhighlight(frontend *fe, float *ret, game_mkhighlight_specific(fe, ret, background, highlight, lowlight); } -static void swap_regions(void *av, void *bv, int size) +void swap_regions(void *av, void *bv, size_t size) { char tmpbuf[512]; char *a = av, *b = bv; @@ -288,15 +351,16 @@ void draw_rect_corners(drawing *dr, int cx, int cy, int r, int 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) +char *move_cursor(int button, int *x, int *y, int maxw, int maxh, bool wrap, + bool *visible) { - int dx = 0, dy = 0; + int dx = 0, dy = 0, ox = *x, oy = *y; 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; + default: return MOVE_UNUSED; } if (wrap) { *x = (*x + dx + maxw) % maxw; @@ -305,6 +369,13 @@ void move_cursor(int button, int *x, int *y, int maxw, int maxh, bool wrap) *x = min(max(*x+dx, 0), maxw - 1); *y = min(max(*y+dy, 0), maxh - 1); } + if (visible != NULL && !*visible) { + *visible = true; + return MOVE_UI_UPDATE; + } + if (*x != ox || *y != oy) + return MOVE_UI_UPDATE; + return MOVE_NO_EFFECT; } /* Used in netslide.c and sixteen.c for cursor movement around edge. */ @@ -402,12 +473,6 @@ void copy_left_justified(char *buf, size_t sz, const char *str) buf[sz - 1] = 0; } -/* another kludge for platforms without %g support in *printf() */ -int ftoa(char *buf, float f) -{ - return sprintf(buf, "%d.%06d", (int)f, abs((int)((f - (int)f)*1e6))); -} - /* Returns a dynamically allocated label for a generic button. * Game-specific buttons should go into the `label' field of key_label * instead. */ @@ -446,4 +511,161 @@ char *button2label(int button) 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: */ -- cgit v1.2.3