[cairo] infinite loop when CAIRO_FIXED_FRAC_BITS is 8
Carl Worth
cworth at cworth.org
Sat Feb 16 13:40:35 PST 2008
On Fri, 15 Feb 2008 11:52:19 -0500, Behdad Esfahbod wrote:
> Ah. The fix is still valid and should go in though.
Yes, fair enough. It's still a good fix for _cairo_slope_compare.
So here are two follow-on patches. The first simply eliminates some
code as a cleanup, (I don't intend any functional change at all---so
any review to verify that would be appreciated).
Then, the second is as nice a fix as you could hope for I think. It
simply changes a >= to a > and makes the infinite loop go away.
Again, review is appreciated, but I'm feeling much more confident
about this stuff now. It seems much more "obviously correct". Plus,
I'm just plain excited to be ready to push out the next snapshot.
-Carl
PS. Behdad, I'm trying a different attachment method now, please let
me know if it isn't kinder for your mailer. I was quite embarrassed to
realize I'd been sending with an octet-stream mime tag. Hopefully now
they'll all be nicely tagged as text/plain, (and UTF-8 as
needed). Oddly enough, my mailer had always displayed the received
things as plain text and let me comment on them by just clicking
reply.
-------------- next part --------------
From c4b230a7885e5e6385de73dc1a1ff82ddbc2e59e Mon Sep 17 00:00:00 2001
From: Carl Worth <cworth at cworth.org>
Date: Sat, 16 Feb 2008 13:17:49 -0800
Subject: [PATCH] Remove _cairo_slope_[counter_]clockwise
These two functions were hiding away some important details
about strictness of inequalities. Also, the callers differ
on the strictness they need. Everything is cleaner and more
flexible by making the callers just call _cairo_slope_compare
directly.
---
src/cairo-path-stroke.c | 2 +-
src/cairo-pen.c | 30 ++++++++++++++++--------------
src/cairo-slope.c | 23 -----------------------
src/cairoint.h | 6 ------
4 files changed, 17 insertions(+), 44 deletions(-)
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index b82c28a..61ae38b 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -235,7 +235,7 @@ _cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out
_cairo_slope_init (&in_slope, &in->point, &in->cw);
_cairo_slope_init (&out_slope, &out->point, &out->cw);
- return _cairo_slope_clockwise (&in_slope, &out_slope);
+ return _cairo_slope_compare (&in_slope, &out_slope) < 0;
}
/**
diff --git a/src/cairo-pen.c b/src/cairo-pen.c
index cde129c..fc01970 100644
--- a/src/cairo-pen.c
+++ b/src/cairo-pen.c
@@ -302,13 +302,15 @@ _cairo_pen_compute_slopes (cairo_pen_t *pen)
/*
* Find active pen vertex for clockwise edge of stroke at the given slope.
*
- * Note: The behavior of this function is sensitive to the sense of
- * the inequality within _cairo_slope_clockwise/_cairo_slope_counter_clockwise.
+ * The strictness of the inequalities here is delicate. The issue is
+ * that the slope_ccw member of one pen vertex will be equivalent to
+ * the slope_cw member of the next pen vertex in a counterclockwise
+ * order. However, for this function, we care strongly about which
+ * vertex is returned.
*
- * The issue is that the slope_ccw member of one pen vertex will be
- * equivalent to the slope_cw member of the next pen vertex in a
- * counterclockwise order. However, for this function, we care
- * strongly about which vertex is returned.
+ * [I think the "care strongly" above has to do with ensuring that the
+ * pen's "extra points" from the spline's initial and final slopes are
+ * properly found when beginning the spline stroking.]
*/
void
_cairo_pen_find_active_cw_vertex_index (cairo_pen_t *pen,
@@ -318,8 +320,8 @@ _cairo_pen_find_active_cw_vertex_index (cairo_pen_t *pen,
int i;
for (i=0; i < pen->num_vertices; i++) {
- if (_cairo_slope_clockwise (slope, &pen->vertices[i].slope_ccw)
- && _cairo_slope_counter_clockwise (slope, &pen->vertices[i].slope_cw))
+ if ((_cairo_slope_compare (slope, &pen->vertices[i].slope_ccw) < 0) &&
+ (_cairo_slope_compare (slope, &pen->vertices[i].slope_cw) >= 0))
break;
}
@@ -336,8 +338,8 @@ _cairo_pen_find_active_cw_vertex_index (cairo_pen_t *pen,
/* Find active pen vertex for counterclockwise edge of stroke at the given slope.
*
- * Note: The behavior of this function is sensitive to the sense of
- * the inequality within _cairo_slope_clockwise/_cairo_slope_counter_clockwise.
+ * Note: See the comments for _cairo_pen_find_active_cw_vertex_index
+ * for some details about the strictness of the inequalities here.
*/
void
_cairo_pen_find_active_ccw_vertex_index (cairo_pen_t *pen,
@@ -352,8 +354,8 @@ _cairo_pen_find_active_ccw_vertex_index (cairo_pen_t *pen,
slope_reverse.dy = -slope_reverse.dy;
for (i=pen->num_vertices-1; i >= 0; i--) {
- if (_cairo_slope_counter_clockwise (&pen->vertices[i].slope_ccw, &slope_reverse)
- && _cairo_slope_clockwise (&pen->vertices[i].slope_cw, &slope_reverse))
+ if ((_cairo_slope_compare (&pen->vertices[i].slope_ccw, &slope_reverse) >= 0) &&
+ (_cairo_slope_compare (&pen->vertices[i].slope_cw, &slope_reverse) < 0))
break;
}
@@ -415,10 +417,10 @@ _cairo_pen_stroke_spline_half (cairo_pen_t *pen,
slope = final_slope;
else
_cairo_slope_init (&slope, &point[i], &point[i+step]);
- if (_cairo_slope_counter_clockwise (&slope, &pen->vertices[active].slope_ccw)) {
+ if (_cairo_slope_compare (&slope, &pen->vertices[active].slope_ccw) >= 0) {
if (++active == pen->num_vertices)
active = 0;
- } else if (_cairo_slope_clockwise (&slope, &pen->vertices[active].slope_cw)) {
+ } else if (_cairo_slope_compare (&slope, &pen->vertices[active].slope_cw) < 0) {
if (--active == -1)
active = pen->num_vertices - 1;
} else {
diff --git a/src/cairo-slope.c b/src/cairo-slope.c
index af97a63..d3f0db4 100644
--- a/src/cairo-slope.c
+++ b/src/cairo-slope.c
@@ -106,26 +106,3 @@ _cairo_slope_compare (cairo_slope_t *a, cairo_slope_t *b)
/* Finally, for identical slopes, we obviously return 0. */
return 0;
}
-
-/* XXX: It might be cleaner to move away from usage of
- _cairo_slope_clockwise/_cairo_slope_counter_clockwise in favor of
- directly using _cairo_slope_compare.
-*/
-
-/* Is a clockwise of b?
- *
- * Note: The strict equality here is not significant in and of itself,
- * but there are functions up above that are sensitive to it,
- * (cf. _cairo_pen_find_active_cw_vertex_index).
- */
-int
-_cairo_slope_clockwise (cairo_slope_t *a, cairo_slope_t *b)
-{
- return _cairo_slope_compare (a, b) < 0;
-}
-
-int
-_cairo_slope_counter_clockwise (cairo_slope_t *a, cairo_slope_t *b)
-{
- return ! _cairo_slope_clockwise (a, b);
-}
diff --git a/src/cairoint.h b/src/cairoint.h
index 0ca08f4..9dd30ee 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -2073,12 +2073,6 @@ _cairo_slope_init (cairo_slope_t *slope, cairo_point_t *a, cairo_point_t *b);
cairo_private int
_cairo_slope_compare (cairo_slope_t *a, cairo_slope_t *b);
-cairo_private int
-_cairo_slope_clockwise (cairo_slope_t *a, cairo_slope_t *b);
-
-cairo_private int
-_cairo_slope_counter_clockwise (cairo_slope_t *a, cairo_slope_t *b);
-
/* cairo_pattern.c */
cairo_private cairo_status_t
--
1.5.4.1
From 502a74a012a2c10f72a8a7103359b41013d9c775 Mon Sep 17 00:00:00 2001
From: Carl Worth <cworth at cworth.org>
Date: Sat, 16 Feb 2008 13:27:02 -0800
Subject: [PATCH] Eliminate a potential infinite loop in spline stroking
Sometimes > rather than >= can make a bug difference. The infinite loop
was noticed here:
Infinite loop when scaling very small values using 24.8
http://bugs.freedesktop.org/show_bug.cgi?id=14280
Note that that particular test case only exposes the infinite
loop when using 24.8 instead of 16.16 fixed-point values by
setting CAIRO_FIXED_FRAC_BITS to 8.
---
src/cairo-pen.c | 13 ++++++++++++-
1 files changed, 12 insertions(+), 1 deletions(-)
diff --git a/src/cairo-pen.c b/src/cairo-pen.c
index fc01970..37456d9 100644
--- a/src/cairo-pen.c
+++ b/src/cairo-pen.c
@@ -417,7 +417,18 @@ _cairo_pen_stroke_spline_half (cairo_pen_t *pen,
slope = final_slope;
else
_cairo_slope_init (&slope, &point[i], &point[i+step]);
- if (_cairo_slope_compare (&slope, &pen->vertices[active].slope_ccw) >= 0) {
+
+ /* The strict inequalities here ensure that if a spline slope
+ * compares identically with either of the slopes of the
+ * active vertex, then it remains the active vertex. This is
+ * very important since otherwise we can trigger an infinite
+ * loop in the case of a degenerate pen, (a line), where
+ * neither vertex considers itself active for the slope---one
+ * will consider it as equal and reject, and the other will
+ * consider it unequal and reject. This is due to the inherent
+ * ambiguity when comparing slopes that differ by exactly
+ * pi. */
+ if (_cairo_slope_compare (&slope, &pen->vertices[active].slope_ccw) > 0) {
if (++active == pen->num_vertices)
active = 0;
} else if (_cairo_slope_compare (&slope, &pen->vertices[active].slope_cw) < 0) {
--
1.5.4.1
-------------- 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/20080216/851d5d20/attachment.pgp
More information about the cairo
mailing list