[cairo] infinite loop when CAIRO_FIXED_FRAC_BITS is 8

[Behdad Esfahbod]

On Thu, 2008-02-14 at 12:34 -0800, Carl Worth wrote:
> On Wed, 13 Feb 2008 20:20:50 -0800, Carl Worth wrote:
> > Anyway, I think I'll have a fix soon.
> 
> Here's what I've got. This fixes the infinite loop, adds a spline to
> the degenerate-pen test case, (which was triggering the infinite loop
> before the fix here), and then switches from 16.16 to 24.8 fixed-point
> format.
> 
> I'd appreciate any review of the change I made to
> _cairo_slope_compare. This is a fairly core part of cairo's
> computational geometric machinery so it's important to get the details
> right.

Sure thing.

@@ -78,6 +80,22 @@ _cairo_slope_compare (cairo_slope_t *a, cairo_slope_t *b)
     if (b->dx == 0 && b->dy ==0)
 	return -1;

+    /* Finally, we're looking at two vectors that are either equal or
+     * that differ by exactly pi. We can identify the "differ by pi"
+     * case by looking for a change in sign in either dx or dy between
+     * a and b.
+     *
+     * And in these cases, we eliminate the ambiguity by reducing the angle
+     * of b by an infinitesimally small amount, (that is, 'a' will
+     * always be considered less than 'b').
+     */
+    if (((a->dx > 0) != (b->dx > 0)) ||
+	((a->dy > 0) != (b->dy > 0)))
+    {
+	return -1;
+    }
+
+    /* Finally, for identical slopes, we obviously return 0. */
     return 0;
 }

I think this is wrong.  This breaks the compare function in that it will
both return a<b and b<a for some input slopes a and b.  That is, it
doesn't represent a total order anymore, and depending on qsort()'s
implementation, this may cause an infinite look in itself.

I suggest instead of "return -1", you do something like:

  if (a->dx > 0 || (a->dx == 0 && a->dy > 0))
    return +1;
  else
    return -1;



> -Carl

-- 
behdad
http://behdad.org/

"Those who would give up Essential Liberty to purchase a little
 Temporary Safety, deserve neither Liberty nor Safety."
        -- Benjamin Franklin, 1759