shithub: puzzles

Download patch

ref: 985b538e5346b1aad6d5e09d534fb9ccacfe9235
parent: 19aa3a5d4b1a24c747826c6aeb3acaa5673d03b3
author: Simon Tatham <anakin@pobox.com>
date: Fri May 21 09:55:35 EDT 2021

Galaxies: avoid division by zero in draw_arrow().

During an interactive drag of an arrow, it's possible to put the mouse
pointer precisely on the pixel the arrow is pointing at. When that
happens, draw_arrow computes the zero-length vector from the pointer
to the target pixel, and tries to normalise it to unit length by
dividing by its length. Of course, this leads to computing 0/0 = NaN.

Depending on the platform, this can cause different effects.
Conversion of a floating-point NaN to an integer is not specified by
IEEE 754; on some platforms (e.g. Arm) it comes out as 0, and on
others (e.g. x86), INT_MIN.

If the conversion delivers INT_MIN, one possible effect is that the
arrow is drawn as an immensely long diagonal line, pointing upwards
and leftwards from the target point. To add to the confusion, that
line would not immediately appear on the display in full, because of
the draw_update system. But further dragging-around of arrows will
gradually reveal it as draw_update rectangles intersect the corrupted
display area.

However, that diagonal line need not show up at all, because once
draw_arrow has accidentally computed a lot of values in the region of
INT_MIN, it then adds them together, causing signed integer overflow
(i.e. undefined behaviour) to confuse matters further! In fact, this
diagonal-line drawing artefact has only been observed on the
WebAssembly front end. The x86 desktop platforms might very plausibly
have done it too, but in fact they didn't (I'm guessing because of
this UB issue, or else some kind of clipping inside the graphics
library), which is how we haven't found this bug until now.

Having found it, however, the fix is simple. If asked to draw an arrow
from a point to itself, take an early return from draw_arrow before
dividing by zero, and don't draw anything at all.

--- a/galaxies.c

+++ b/galaxies.c

@@ -3159,7 +3159,10 @@

 static void draw_arrow(drawing *dr, game_drawstate *ds,

                        int cx, int cy, int ddx, int ddy, int col)

 {

-    float vlen = (float)sqrt(ddx*ddx+ddy*ddy);

+    int sqdist = ddx*ddx+ddy*ddy;

+    if (sqdist == 0)

+        return;                        /* avoid division by zero */

+    float vlen = (float)sqrt(sqdist);

     float xdx = ddx/vlen, xdy = ddy/vlen;

     float ydx = -xdy, ydy = xdx;

     int e1x = cx + (int)(xdx*TILE_SIZE/3), e1y = cy + (int)(xdy*TILE_SIZE/3);