From 17c75e705e49eb544a943da69e806725e76cf0c7 Mon Sep 17 00:00:00 2001 From: simon Date: Sun, 24 Jul 2005 10:39:33 +0000 Subject: [PATCH] The very core of cross() is capable of suffering integer overflow on large puzzles. Resort to hand-hacked 64-bit arithmetic for doing dot products; everything else remains in `long' for the moment. (Ideally I'd auto-detect the presence of `long long' and use it in place of my cheap plastic imitation where possible, but since I currently don't have a configure mechanism that'll have to wait.) git-svn-id: svn://svn.tartarus.org/sgt/puzzles@6137 cda61777-01e9-0310-a592-d414129be87e --- untangle.c | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 107 insertions(+), 17 deletions(-) diff --git a/untangle.c b/untangle.c index 6bb010f..14a5c6c 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) + +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; +} + +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; +} + +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; /* @@ -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; } -- 2.11.0