diff options
Diffstat (limited to 'apps/plugins/puzzles/src/misc.c')
-rw-r--r-- | apps/plugins/puzzles/src/misc.c | 289 |
1 files changed, 261 insertions, 28 deletions
diff --git a/apps/plugins/puzzles/src/misc.c b/apps/plugins/puzzles/src/misc.c index ed31acbbe4..8e96d67039 100644 --- a/apps/plugins/puzzles/src/misc.c +++ b/apps/plugins/puzzles/src/misc.c | |||
@@ -3,13 +3,21 @@ | |||
3 | */ | 3 | */ |
4 | 4 | ||
5 | #include <assert.h> | 5 | #include <assert.h> |
6 | #include <ctype.h> | ||
7 | #ifdef NO_TGMATH_H | ||
8 | # include <math.h> | ||
9 | #else | ||
10 | # include <tgmath.h> | ||
11 | #endif | ||
6 | #include <stdlib.h> | 12 | #include <stdlib.h> |
7 | #include <string.h> | 13 | #include <string.h> |
8 | #include <stdio.h> | 14 | #include <stdio.h> |
9 | 15 | ||
10 | #include "puzzles.h" | 16 | #include "puzzles.h" |
11 | 17 | ||
12 | char UI_UPDATE[] = ""; | 18 | char MOVE_UI_UPDATE[] = ""; |
19 | char MOVE_NO_EFFECT[] = ""; | ||
20 | char MOVE_UNUSED[] = ""; | ||
13 | 21 | ||
14 | void free_cfg(config_item *cfg) | 22 | void free_cfg(config_item *cfg) |
15 | { | 23 | { |
@@ -197,30 +205,85 @@ char *fgetline(FILE *fp) | |||
197 | return ret; | 205 | return ret; |
198 | } | 206 | } |
199 | 207 | ||
208 | int getenv_bool(const char *name, int dflt) | ||
209 | { | ||
210 | char *env = getenv(name); | ||
211 | if (env == NULL) return dflt; | ||
212 | if (strchr("yYtT", env[0])) return true; | ||
213 | return false; | ||
214 | } | ||
215 | |||
216 | /* Utility functions for colour manipulation. */ | ||
217 | |||
218 | static float colour_distance(const float a[3], const float b[3]) | ||
219 | { | ||
220 | return (float)sqrt((a[0]-b[0]) * (a[0]-b[0]) + | ||
221 | (a[1]-b[1]) * (a[1]-b[1]) + | ||
222 | (a[2]-b[2]) * (a[2]-b[2])); | ||
223 | } | ||
224 | |||
225 | void colour_mix(const float src1[3], const float src2[3], float p, float dst[3]) | ||
226 | { | ||
227 | int i; | ||
228 | for (i = 0; i < 3; i++) | ||
229 | dst[i] = src1[i] * (1.0F - p) + src2[i] * p; | ||
230 | } | ||
231 | |||
200 | void game_mkhighlight_specific(frontend *fe, float *ret, | 232 | void game_mkhighlight_specific(frontend *fe, float *ret, |
201 | int background, int highlight, int lowlight) | 233 | int background, int highlight, int lowlight) |
202 | { | 234 | { |
203 | float max; | 235 | static const float black[3] = { 0.0F, 0.0F, 0.0F }; |
236 | static const float white[3] = { 1.0F, 1.0F, 1.0F }; | ||
237 | float db, dw; | ||
204 | int i; | 238 | int i; |
205 | |||
206 | /* | 239 | /* |
207 | * Drop the background colour so that the highlight is | 240 | * New geometric highlight-generation algorithm: Draw a line from |
208 | * noticeably brighter than it while still being under 1. | 241 | * the base colour to white. The point K distance along this line |
242 | * from the base colour is the highlight colour. Similarly, draw | ||
243 | * a line from the base colour to black. The point on this line | ||
244 | * at a distance K from the base colour is the shadow. If either | ||
245 | * of these colours is imaginary (for reasonable K at most one | ||
246 | * will be), _extrapolate_ the base colour along the same line | ||
247 | * until it's a distance K from white (or black) and start again | ||
248 | * with that as the base colour. | ||
249 | * | ||
250 | * This preserves the hue of the base colour, ensures that of the | ||
251 | * three the base colour is the most saturated, and only ever | ||
252 | * flattens the highlight and shadow to pure white or pure black. | ||
253 | * | ||
254 | * K must be at most sqrt(3)/2, or mid grey would be too close to | ||
255 | * both white and black. Here K is set to sqrt(3)/6 so that this | ||
256 | * code produces the same results as the former code in the common | ||
257 | * case where the background is grey and the highlight saturates | ||
258 | * to white. | ||
209 | */ | 259 | */ |
210 | max = ret[background*3]; | 260 | const float k = sqrt(3)/6.0F; |
211 | for (i = 1; i < 3; i++) | 261 | if (lowlight >= 0) { |
212 | if (ret[background*3+i] > max) | 262 | db = colour_distance(&ret[background*3], black); |
213 | max = ret[background*3+i]; | 263 | if (db < k) { |
214 | if (max * 1.2F > 1.0F) { | 264 | for (i = 0; i < 3; i++) ret[lowlight*3+i] = black[i]; |
215 | for (i = 0; i < 3; i++) | 265 | if (db == 0.0F) |
216 | ret[background*3+i] /= (max * 1.2F); | 266 | colour_mix(black, white, k/sqrt(3), &ret[background*3]); |
267 | else | ||
268 | colour_mix(black, &ret[background*3], k/db, &ret[background*3]); | ||
269 | } else { | ||
270 | colour_mix(&ret[background*3], black, k/db, &ret[lowlight*3]); | ||
271 | } | ||
217 | } | 272 | } |
218 | 273 | if (highlight >= 0) { | |
219 | for (i = 0; i < 3; i++) { | 274 | dw = colour_distance(&ret[background*3], white); |
220 | if (highlight >= 0) | 275 | if (dw < k) { |
221 | ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F; | 276 | for (i = 0; i < 3; i++) ret[highlight*3+i] = white[i]; |
222 | if (lowlight >= 0) | 277 | if (dw == 0.0F) |
223 | ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F; | 278 | colour_mix(white, black, k/sqrt(3), &ret[background*3]); |
279 | else | ||
280 | colour_mix(white, &ret[background*3], k/dw, &ret[background*3]); | ||
281 | /* Background has changed; recalculate lowlight. */ | ||
282 | if (lowlight >= 0) | ||
283 | colour_mix(&ret[background*3], black, k/db, &ret[lowlight*3]); | ||
284 | } else { | ||
285 | colour_mix(&ret[background*3], white, k/dw, &ret[highlight*3]); | ||
286 | } | ||
224 | } | 287 | } |
225 | } | 288 | } |
226 | 289 | ||
@@ -231,7 +294,7 @@ void game_mkhighlight(frontend *fe, float *ret, | |||
231 | game_mkhighlight_specific(fe, ret, background, highlight, lowlight); | 294 | game_mkhighlight_specific(fe, ret, background, highlight, lowlight); |
232 | } | 295 | } |
233 | 296 | ||
234 | static void swap_regions(void *av, void *bv, int size) | 297 | void swap_regions(void *av, void *bv, size_t size) |
235 | { | 298 | { |
236 | char tmpbuf[512]; | 299 | char tmpbuf[512]; |
237 | char *a = av, *b = bv; | 300 | char *a = av, *b = bv; |
@@ -288,15 +351,27 @@ void draw_rect_corners(drawing *dr, int cx, int cy, int r, int col) | |||
288 | draw_line(dr, cx + r, cy + r, cx + r/2, cy + r, col); | 351 | draw_line(dr, cx + r, cy + r, cx + r/2, cy + r, col); |
289 | } | 352 | } |
290 | 353 | ||
291 | void move_cursor(int button, int *x, int *y, int maxw, int maxh, bool wrap) | 354 | int compare_integers(const void *av, const void *bv) { |
355 | const int *a = (const int *)av; | ||
356 | const int *b = (const int *)bv; | ||
357 | if (*a < *b) | ||
358 | return -1; | ||
359 | else if (*a > *b) | ||
360 | return +1; | ||
361 | else | ||
362 | return 0; | ||
363 | } | ||
364 | |||
365 | char *move_cursor(int button, int *x, int *y, int maxw, int maxh, bool wrap, | ||
366 | bool *visible) | ||
292 | { | 367 | { |
293 | int dx = 0, dy = 0; | 368 | int dx = 0, dy = 0, ox = *x, oy = *y; |
294 | switch (button) { | 369 | switch (button) { |
295 | case CURSOR_UP: dy = -1; break; | 370 | case CURSOR_UP: dy = -1; break; |
296 | case CURSOR_DOWN: dy = 1; break; | 371 | case CURSOR_DOWN: dy = 1; break; |
297 | case CURSOR_RIGHT: dx = 1; break; | 372 | case CURSOR_RIGHT: dx = 1; break; |
298 | case CURSOR_LEFT: dx = -1; break; | 373 | case CURSOR_LEFT: dx = -1; break; |
299 | default: return; | 374 | default: return MOVE_UNUSED; |
300 | } | 375 | } |
301 | if (wrap) { | 376 | if (wrap) { |
302 | *x = (*x + dx + maxw) % maxw; | 377 | *x = (*x + dx + maxw) % maxw; |
@@ -305,6 +380,13 @@ void move_cursor(int button, int *x, int *y, int maxw, int maxh, bool wrap) | |||
305 | *x = min(max(*x+dx, 0), maxw - 1); | 380 | *x = min(max(*x+dx, 0), maxw - 1); |
306 | *y = min(max(*y+dy, 0), maxh - 1); | 381 | *y = min(max(*y+dy, 0), maxh - 1); |
307 | } | 382 | } |
383 | if (visible != NULL && !*visible) { | ||
384 | *visible = true; | ||
385 | return MOVE_UI_UPDATE; | ||
386 | } | ||
387 | if (*x != ox || *y != oy) | ||
388 | return MOVE_UI_UPDATE; | ||
389 | return MOVE_NO_EFFECT; | ||
308 | } | 390 | } |
309 | 391 | ||
310 | /* Used in netslide.c and sixteen.c for cursor movement around edge. */ | 392 | /* Used in netslide.c and sixteen.c for cursor movement around edge. */ |
@@ -402,12 +484,6 @@ void copy_left_justified(char *buf, size_t sz, const char *str) | |||
402 | buf[sz - 1] = 0; | 484 | buf[sz - 1] = 0; |
403 | } | 485 | } |
404 | 486 | ||
405 | /* another kludge for platforms without %g support in *printf() */ | ||
406 | int ftoa(char *buf, float f) | ||
407 | { | ||
408 | return sprintf(buf, "%d.%06d", (int)f, abs((int)((f - (int)f)*1e6))); | ||
409 | } | ||
410 | |||
411 | /* Returns a dynamically allocated label for a generic button. | 487 | /* Returns a dynamically allocated label for a generic button. |
412 | * Game-specific buttons should go into the `label' field of key_label | 488 | * Game-specific buttons should go into the `label' field of key_label |
413 | * instead. */ | 489 | * instead. */ |
@@ -446,4 +522,161 @@ char *button2label(int button) | |||
446 | return NULL; | 522 | return NULL; |
447 | } | 523 | } |
448 | 524 | ||
525 | char *make_prefs_path(const char *dir, const char *sep, | ||
526 | const game *game, const char *suffix) | ||
527 | { | ||
528 | size_t dirlen = strlen(dir); | ||
529 | size_t seplen = strlen(sep); | ||
530 | size_t gamelen = strlen(game->name); | ||
531 | size_t suffixlen = strlen(suffix); | ||
532 | char *path, *p; | ||
533 | const char *q; | ||
534 | |||
535 | if (!dir || !sep || !game || !suffix) | ||
536 | return NULL; | ||
537 | |||
538 | path = snewn(dirlen + seplen + gamelen + suffixlen + 1, char); | ||
539 | p = path; | ||
540 | |||
541 | memcpy(p, dir, dirlen); | ||
542 | p += dirlen; | ||
543 | |||
544 | memcpy(p, sep, seplen); | ||
545 | p += seplen; | ||
546 | |||
547 | for (q = game->name; *q; q++) | ||
548 | if (*q != ' ') | ||
549 | *p++ = tolower((unsigned char)*q); | ||
550 | |||
551 | memcpy(p, suffix, suffixlen); | ||
552 | p += suffixlen; | ||
553 | |||
554 | *p = '\0'; | ||
555 | return path; | ||
556 | } | ||
557 | |||
558 | /* | ||
559 | * Calculate the nearest integer to n*sqrt(k), via a bitwise algorithm | ||
560 | * that avoids floating point. | ||
561 | * | ||
562 | * (It would probably be OK in practice to use floating point, but I | ||
563 | * felt like overengineering it for fun. With FP, there's at least a | ||
564 | * theoretical risk of rounding the wrong way, due to the three | ||
565 | * successive roundings involved - rounding sqrt(k), rounding its | ||
566 | * product with n, and then rounding to the nearest integer. This | ||
567 | * approach avoids that: it's exact.) | ||
568 | */ | ||
569 | int n_times_root_k(int n_signed, int k) | ||
570 | { | ||
571 | unsigned x, r, m; | ||
572 | int sign = n_signed < 0 ? -1 : +1; | ||
573 | unsigned n = n_signed * sign; | ||
574 | unsigned bitpos; | ||
575 | |||
576 | /* | ||
577 | * Method: | ||
578 | * | ||
579 | * We transform m gradually from zero into n, by multiplying it by | ||
580 | * 2 in each step and optionally adding 1, so that it's always | ||
581 | * floor(n/2^something). | ||
582 | * | ||
583 | * At the start of each step, x is the largest integer less than | ||
584 | * or equal to m*sqrt(k). We transform m to 2m+bit, and therefore | ||
585 | * we must transform x to 2x+something to match. The 'something' | ||
586 | * we add to 2x is at most floor(sqrt(k))+2. (Worst case is if m | ||
587 | * sqrt(k) was equal to x + 1-eps for some tiny eps, and then the | ||
588 | * incoming bit of m is 1, so that (2m+1)sqrt(k) = | ||
589 | * 2x+2+sqrt(k)-2eps.) | ||
590 | * | ||
591 | * To compute this, we also track the residual value r such that | ||
592 | * x^2+r = km^2. | ||
593 | * | ||
594 | * The algorithm below is very similar to the usual approach for | ||
595 | * taking the square root of an integer in binary. The wrinkle is | ||
596 | * that we have an integer multiplier, i.e. we're computing | ||
597 | * n*sqrt(k) rather than just sqrt(k). Of course in principle we | ||
598 | * could just take sqrt(n^2k), but we'd need an integer twice the | ||
599 | * width to hold n^2. Pulling out n and treating it specially | ||
600 | * makes overflow less likely. | ||
601 | */ | ||
602 | |||
603 | x = r = m = 0; | ||
604 | |||
605 | for (bitpos = UINT_MAX & ~(UINT_MAX >> 1); bitpos; bitpos >>= 1) { | ||
606 | unsigned a, b = (n & bitpos) ? 1 : 0; | ||
607 | |||
608 | /* | ||
609 | * Check invariants. We expect that x^2 + r = km^2 (i.e. our | ||
610 | * residual term is correct), and also that r < 2x+1 (because | ||
611 | * if not, then we could replace x with x+1 and still get a | ||
612 | * value that made r non-negative, i.e. x would not be the | ||
613 | * _largest_ integer less than m sqrt(k)). | ||
614 | */ | ||
615 | assert(x*x + r == k*m*m); | ||
616 | assert(r < 2*x+1); | ||
617 | |||
618 | /* | ||
619 | * We're going to replace m with 2m+b, and x with 2x+a for | ||
620 | * some a we haven't decided on yet. | ||
621 | * | ||
622 | * The new value of the residual will therefore be | ||
623 | * | ||
624 | * k (2m+b)^2 - (2x+a)^2 | ||
625 | * = (4km^2 + 4kmb + kb^2) - (4x^2 + 4xa + a^2) | ||
626 | * = 4 (km^2 - x^2) + 4kmb + kb^2 - 4xa - a^2 | ||
627 | * = 4r + 4kmb + kb^2 - 4xa - a^2 (because r = km^2 - x^2) | ||
628 | * = 4r + (4m + 1)kb - 4xa - a^2 (b is 0 or 1, so b = b^2) | ||
629 | */ | ||
630 | for (a = 0;; a++) { | ||
631 | /* If we made this routine handle square roots of numbers | ||
632 | * significantly bigger than 3 or 5 then it would be | ||
633 | * sensible to make this a binary search. Here, it hardly | ||
634 | * seems important. */ | ||
635 | unsigned pos = 4*r + k*b*(4*m + 1); | ||
636 | unsigned neg = 4*a*x + a*a; | ||
637 | if (pos < neg) | ||
638 | break; /* this value of a is too big */ | ||
639 | } | ||
640 | |||
641 | /* The above loop will have terminated with a one too big. So | ||
642 | * now decrementing a will give us the right value to add. */ | ||
643 | a--; | ||
644 | |||
645 | r = 4*r + b*k*(4*m + 1) - (4*a*x + a*a); | ||
646 | m = 2*m+b; | ||
647 | x = 2*x+a; | ||
648 | } | ||
649 | |||
650 | /* | ||
651 | * Finally, round to the nearest integer. At present, x is the | ||
652 | * largest integer that is _at most_ m sqrt(k). But we want the | ||
653 | * _nearest_ integer, whether that's rounded up or down. So check | ||
654 | * whether (x + 1/2) is still less than m sqrt(k), i.e. whether | ||
655 | * (x + 1/2)^2 < km^2; if it is, then we increment x. | ||
656 | * | ||
657 | * We have km^2 - (x + 1/2)^2 = km^2 - x^2 - x - 1/4 | ||
658 | * = r - x - 1/4 | ||
659 | * | ||
660 | * and since r and x are integers, this is greater than 0 if and | ||
661 | * only if r > x. | ||
662 | * | ||
663 | * (There's no need to worry about tie-breaking exact halfway | ||
664 | * rounding cases. sqrt(k) is irrational, so none such exist.) | ||
665 | */ | ||
666 | if (r > x) | ||
667 | x++; | ||
668 | |||
669 | /* | ||
670 | * Put the sign back on, and convert back from unsigned to int. | ||
671 | */ | ||
672 | if (sign == +1) { | ||
673 | return x; | ||
674 | } else { | ||
675 | /* Be a little careful to avoid compilers deciding I've just | ||
676 | * perpetrated signed-integer overflow. This should optimise | ||
677 | * down to no actual code. */ | ||
678 | return INT_MIN + (int)(-x - (unsigned)INT_MIN); | ||
679 | } | ||
680 | } | ||
681 | |||
449 | /* vim: set shiftwidth=4 tabstop=8: */ | 682 | /* vim: set shiftwidth=4 tabstop=8: */ |