[cairo] infinite loop when CAIRO_FIXED_FRAC_BITS is 8

[Carl Worth]

On Thu, 14 Feb 2008 16:29:02 -0500, Behdad Esfahbod wrote:
> On Thu, 2008-02-14 at 12:34 -0800, Carl Worth wrote:
> +    /* 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.

Quite likely. Thanks for the review.

> This breaks the compare function in that it will
> both return a<b and b<a for some input slopes a and b.

Right. In my defense, I was aware that this was giving special
attention to the order in which the arguments were presented to the
function, and I did _some_ analysis that we were calling it
consistently, (though my analysis was probably too shallow).

And for what it's worth, we *don't* call qsort with this comparison
function.

> 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;

Thanks, I like that. And it does seem to guarantee a total order.

Now, do you also have a good proposal for how to document the
behavior? The best I've got so far is:

	To resolve ambiguous cases, (where the angular difference is
	exactly pi), imagine subtracting an infinitesimally small
	amount from the dy value of each slope, (or if the dx value
	for both is 0, then add an infinitesimally small value to the
	dx value of each). The function returns a correct comparison
	for those effective slopes.

I *think* that's right, but it's quite awkward, (either subtracting or
adding), and it's not all that intuitive to start with that and figure
out what happens.

Other ideas?

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20080214/8fd81479/attachment.pgp