X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/0d98f76fcfb547a00ba3a7c8d785fa98c02109e0..HEAD:/untangle.c diff --git a/untangle.c b/untangle.c index 6bb010f..beb2871 100644 --- a/untangle.c +++ b/untangle.c @@ -13,8 +13,11 @@ /* * TODO: * - * - Docs and checklist etc * - Any way we can speed up redraws on GTK? Uck. + * + * - It would be nice if we could somehow auto-detect a real `long + * long' type on the host platform and use it in place of my + * hand-hacked int64s. It'd be faster and more reliable. */ #include @@ -202,6 +205,90 @@ static char *validate_params(game_params *params, int full) return NULL; } +/* ---------------------------------------------------------------------- + * Small number of 64-bit integer arithmetic operations, to prevent + * integer overflow at the very core of cross(). + */ + +typedef struct { + long hi; + unsigned long lo; +} int64; + +#define greater64(i,j) ( (i).hi>(j).hi || ((i).hi==(j).hi && (i).lo>(j).lo)) +#define sign64(i) ((i).hi < 0 ? -1 : (i).hi==0 && (i).lo==0 ? 0 : +1) + +static int64 mulu32to64(unsigned long x, unsigned long y) +{ + unsigned long a, b, c, d, t; + int64 ret; + + a = (x & 0xFFFF) * (y & 0xFFFF); + b = (x & 0xFFFF) * (y >> 16); + c = (x >> 16) * (y & 0xFFFF); + d = (x >> 16) * (y >> 16); + + ret.lo = a; + ret.hi = d + (b >> 16) + (c >> 16); + t = (b & 0xFFFF) << 16; + ret.lo += t; + if (ret.lo < t) + ret.hi++; + t = (c & 0xFFFF) << 16; + ret.lo += t; + if (ret.lo < t) + ret.hi++; + +#ifdef DIAGNOSTIC_VIA_LONGLONG + assert(((unsigned long long)ret.hi << 32) + ret.lo == + (unsigned long long)x * y); +#endif + + return ret; +} + +static int64 mul32to64(long x, long y) +{ + int sign = +1; + int64 ret; +#ifdef DIAGNOSTIC_VIA_LONGLONG + long long realret = (long long)x * y; +#endif + + if (x < 0) + x = -x, sign = -sign; + if (y < 0) + y = -y, sign = -sign; + + ret = mulu32to64(x, y); + + if (sign < 0) { + ret.hi = -ret.hi; + ret.lo = -ret.lo; + if (ret.lo) + ret.hi--; + } + +#ifdef DIAGNOSTIC_VIA_LONGLONG + assert(((unsigned long long)ret.hi << 32) + ret.lo == realret); +#endif + + return ret; +} + +static int64 dotprod64(long a, long b, long p, long q) +{ + int64 ab, pq; + + ab = mul32to64(a, b); + pq = mul32to64(p, q); + ab.hi += pq.hi; + ab.lo += pq.lo; + if (ab.lo < pq.lo) + ab.hi++; + return ab; +} + /* * Determine whether the line segments between a1 and a2, and * between b1 and b2, intersect. We count it as an intersection if @@ -209,7 +296,8 @@ static char *validate_params(game_params *params, int full) */ static int cross(point a1, point a2, point b1, point b2) { - long b1x, b1y, b2x, b2y, px, py, d1, d2, d3; + long b1x, b1y, b2x, b2y, px, py; + int64 d1, d2, d3; /* * The condition for crossing is that b1 and b2 are on opposite @@ -233,11 +321,12 @@ static int cross(point a1, point a2, point b1, point b2) b2y = b2.y * a1.d - a1.y * b2.d; px = a1.y * a2.d - a2.y * a1.d; py = a2.x * a1.d - a1.x * a2.d; - /* Take the dot products. */ - d1 = b1x * px + b1y * py; - d2 = b2x * px + b2y * py; + /* Take the dot products. Here we resort to 64-bit arithmetic. */ + d1 = dotprod64(b1x, px, b1y, py); + d2 = dotprod64(b2x, px, b2y, py); /* If they have the same non-zero sign, the lines do not cross. */ - if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0)) + if ((sign64(d1) > 0 && sign64(d2) > 0) || + (sign64(d1) < 0 && sign64(d2) < 0)) return FALSE; /* @@ -246,21 +335,21 @@ static int cross(point a1, point a2, point b1, point b2) * condition becomes whether or not they overlap within their * line. */ - if (d1 == 0 && d2 == 0) { + if (sign64(d1) == 0 && sign64(d2) == 0) { /* Construct the vector a2-a1. */ px = a2.x * a1.d - a1.x * a2.d; py = a2.y * a1.d - a1.y * a2.d; /* Determine the dot products of b1-a1 and b2-a1 with this. */ - d1 = b1x * px + b1y * py; - d2 = b2x * px + b2y * py; + d1 = dotprod64(b1x, px, b1y, py); + d2 = dotprod64(b2x, px, b2y, py); /* If they're both strictly negative, the lines do not cross. */ - if (d1 < 0 && d2 < 0) + if (sign64(d1) < 0 && sign64(d2) < 0) return FALSE; /* Otherwise, take the dot product of a2-a1 with itself. If * the other two dot products both exceed this, the lines do * not cross. */ - d3 = px * px + py * py; - if (d1 > d3 && d2 > d3) + d3 = dotprod64(px, px, py, py); + if (greater64(d1, d3) && greater64(d2, d3)) return FALSE; } @@ -276,9 +365,10 @@ static int cross(point a1, point a2, point b1, point b2) b2y = a2.y * b1.d - b1.y * a2.d; px = b1.y * b2.d - b2.y * b1.d; py = b2.x * b1.d - b1.x * b2.d; - d1 = b1x * px + b1y * py; - d2 = b2x * px + b2y * py; - if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0)) + d1 = dotprod64(b1x, px, b1y, py); + d2 = dotprod64(b2x, px, b2y, py); + if ((sign64(d1) > 0 && sign64(d2) > 0) || + (sign64(d1) < 0 && sign64(d2) < 0)) return FALSE; /* @@ -706,7 +796,7 @@ static void mark_crossings(game_state *state) state->completed = TRUE; } -static game_state *new_game(midend_data *me, game_params *params, char *desc) +static game_state *new_game(midend *me, game_params *params, char *desc) { int n = params->n; game_state *state = snew(game_state); @@ -719,7 +809,7 @@ static game_state *new_game(midend_data *me, game_params *params, char *desc) state->graph = snew(struct graph); state->graph->refcount = 1; state->graph->edges = newtree234(edgecmp); - state->cheated = state->just_solved = FALSE; + state->completed = state->cheated = state->just_solved = FALSE; while (*desc) { a = atoi(desc); @@ -739,8 +829,8 @@ static game_state *new_game(midend_data *me, game_params *params, char *desc) #ifdef SHOW_CROSSINGS state->crosses = snewn(count234(state->graph->edges), int); -#endif mark_crossings(state); /* sets up `crosses' and `completed' */ +#endif return state; } @@ -910,8 +1000,8 @@ static char *solve_game(game_state *state, game_state *currstate, pts[i].d = 2; ox *= pts[i].d; oy *= pts[i].d; - pts[i].x = ox + 0.5; - pts[i].y = oy + 0.5; + pts[i].x = (long)(ox + 0.5F); + pts[i].y = (long)(oy + 0.5F); extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i, pts[i].x, pts[i].y, pts[i].d); @@ -928,6 +1018,11 @@ static char *solve_game(game_state *state, game_state *currstate, return ret; } +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + static char *game_text_format(game_state *state) { return NULL; @@ -973,14 +1068,16 @@ static void game_changed_state(game_ui *ui, game_state *oldstate, struct game_drawstate { long tilesize; + int bg, dragpoint; + long *x, *y; }; -static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, +static char *interpret_move(game_state *state, game_ui *ui, const game_drawstate *ds, int x, int y, int button) { int n = state->params.n; - if (button == LEFT_BUTTON) { + if (IS_MOUSE_DOWN(button)) { int i, best; long bestd; @@ -1014,12 +1111,12 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, return ""; } - } else if (button == LEFT_DRAG && ui->dragpoint >= 0) { + } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0) { ui->newpoint.x = x; ui->newpoint.y = y; ui->newpoint.d = ds->tilesize; return ""; - } else if (button == LEFT_RELEASE && ui->dragpoint >= 0) { + } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0) { int p = ui->dragpoint; char buf[80]; @@ -1093,13 +1190,13 @@ static void game_compute_size(game_params *params, int tilesize, *x = *y = COORDLIMIT(params->n) * tilesize; } -static void game_set_size(game_drawstate *ds, game_params *params, - int tilesize) +static void game_set_size(drawing *dr, game_drawstate *ds, + game_params *params, int tilesize) { ds->tilesize = tilesize; } -static float *game_colours(frontend *fe, game_state *state, int *ncolours) +static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); @@ -1143,17 +1240,26 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) return ret; } -static game_drawstate *game_new_drawstate(game_state *state) +static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) { struct game_drawstate *ds = snew(struct game_drawstate); + int i; ds->tilesize = 0; + ds->x = snewn(state->params.n, long); + ds->y = snewn(state->params.n, long); + for (i = 0; i < state->params.n; i++) + ds->x[i] = ds->y[i] = -1; + ds->bg = -1; + ds->dragpoint = -1; return ds; } -static void game_free_drawstate(game_drawstate *ds) +static void game_free_drawstate(drawing *dr, game_drawstate *ds) { + sfree(ds->y); + sfree(ds->x); sfree(ds); } @@ -1162,20 +1268,20 @@ static point mix(point a, point b, float distance) point ret; ret.d = a.d * b.d; - ret.x = a.x * b.d + distance * (b.x * a.d - a.x * b.d); - ret.y = a.y * b.d + distance * (b.y * a.d - a.y * b.d); + ret.x = (long)(a.x * b.d + distance * (b.x * a.d - a.x * b.d)); + ret.y = (long)(a.y * b.d + distance * (b.y * a.d - a.y * b.d)); return ret; } -static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, +static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, game_state *state, int dir, game_ui *ui, float animtime, float flashtime) { int w, h; edge *e; int i, j; - int bg; + int bg, points_moved; /* * There's no terribly sensible way to do partial redraws of @@ -1190,35 +1296,52 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, else bg = COL_FLASH2; + /* + * To prevent excessive spinning on redraw during a completion + * flash, we first check to see if _either_ the flash + * background colour has changed _or_ at least one point has + * moved _or_ a drag has begun or ended, and abandon the redraw + * if neither is the case. + * + * Also in this loop we work out the coordinates of all the + * points for this redraw. + */ + points_moved = FALSE; + for (i = 0; i < state->params.n; i++) { + point p = state->pts[i]; + long x, y; + + if (ui->dragpoint == i) + p = ui->newpoint; + + if (oldstate) + p = mix(oldstate->pts[i], p, animtime / ui->anim_length); + + x = p.x * ds->tilesize / p.d; + y = p.y * ds->tilesize / p.d; + + if (ds->x[i] != x || ds->y[i] != y) + points_moved = TRUE; + + ds->x[i] = x; + ds->y[i] = y; + } + + if (ds->bg == bg && ds->dragpoint == ui->dragpoint && !points_moved) + return; /* nothing to do */ + + ds->dragpoint = ui->dragpoint; + ds->bg = bg; + game_compute_size(&state->params, ds->tilesize, &w, &h); - draw_rect(fe, 0, 0, w, h, bg); + draw_rect(dr, 0, 0, w, h, bg); /* * Draw the edges. */ for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) { - point p1, p2; - long x1, y1, x2, y2; - - p1 = state->pts[e->a]; - p2 = state->pts[e->b]; - if (ui->dragpoint == e->a) - p1 = ui->newpoint; - else if (ui->dragpoint == e->b) - p2 = ui->newpoint; - - if (oldstate) { - p1 = mix(oldstate->pts[e->a], p1, animtime / ui->anim_length); - p2 = mix(oldstate->pts[e->b], p2, animtime / ui->anim_length); - } - - x1 = p1.x * ds->tilesize / p1.d; - y1 = p1.y * ds->tilesize / p1.d; - x2 = p2.x * ds->tilesize / p2.d; - y2 = p2.y * ds->tilesize / p2.d; - - draw_line(fe, x1, y1, x2, y2, + draw_line(dr, ds->x[e->a], ds->y[e->a], ds->x[e->b], ds->y[e->b], #ifdef SHOW_CROSSINGS (oldstate?oldstate:state)->crosses[i] ? COL_CROSSEDLINE : @@ -1236,12 +1359,9 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, int thisc = (j == 0 ? COL_POINT : j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT); for (i = 0; i < state->params.n; i++) { - long x, y; int c; - point p = state->pts[i]; if (ui->dragpoint == i) { - p = ui->newpoint; c = COL_DRAGPOINT; } else if (ui->dragpoint >= 0 && isedge(state->graph->edges, ui->dragpoint, i)) { @@ -1250,29 +1370,25 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate, c = COL_POINT; } - if (oldstate) - p = mix(oldstate->pts[i], p, animtime / ui->anim_length); - if (c == thisc) { - x = p.x * ds->tilesize / p.d; - y = p.y * ds->tilesize / p.d; - #ifdef VERTEX_NUMBERS - draw_circle(fe, x, y, DRAG_THRESHOLD, bg, bg); + draw_circle(dr, ds->x[i], ds->y[i], DRAG_THRESHOLD, bg, bg); { char buf[80]; sprintf(buf, "%d", i); - draw_text(fe, x, y, FONT_VARIABLE, DRAG_THRESHOLD*3/2, + draw_text(dr, ds->x[i], ds->y[i], FONT_VARIABLE, + DRAG_THRESHOLD*3/2, ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf); } #else - draw_circle(fe, x, y, CIRCLE_RADIUS, c, COL_OUTLINE); + draw_circle(dr, ds->x[i], ds->y[i], CIRCLE_RADIUS, + c, COL_OUTLINE); #endif } } } - draw_update(fe, 0, 0, w, h); + draw_update(dr, 0, 0, w, h); } static float game_anim_length(game_state *oldstate, game_state *newstate, @@ -1296,9 +1412,9 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, return 0.0F; } -static int game_wants_statusbar(void) +static int game_status(game_state *state) { - return FALSE; + return state->completed ? +1 : 0; } static int game_timing_state(game_state *state, game_ui *ui) @@ -1306,12 +1422,20 @@ static int game_timing_state(game_state *state, game_ui *ui) return TRUE; } +static void game_print_size(game_params *params, float *x, float *y) +{ +} + +static void game_print(drawing *dr, game_state *state, int tilesize) +{ +} + #ifdef COMBINED #define thegame untangle #endif const struct game thegame = { - "Untangle", "games.untangle", + "Untangle", "games.untangle", "untangle", default_params, game_fetch_preset, decode_params, @@ -1326,7 +1450,7 @@ const struct game thegame = { dup_game, free_game, TRUE, solve_game, - FALSE, game_text_format, + FALSE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -1341,7 +1465,9 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, - game_wants_statusbar, + game_status, + FALSE, FALSE, game_print_size, game_print, + FALSE, /* wants_statusbar */ FALSE, game_timing_state, - SOLVE_ANIMATES, /* mouse_priorities */ + SOLVE_ANIMATES, /* flags */ };