Attachment 105530 Details for Bug 74779 – proposed patch

[patch] proposed patch

0001-Bug-59098-segfault-in-cairo-polygon-intersect.c-acti.patch (text/plain), 4.94 KB, created by Massimo on 2014-09-01 06:06:48 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Massimo

Created: 2014-09-01 06:06:48 UTC

Size: 4.94 KB

patch

obsolete

>From dc4c7c14d07941a56e1378148c950fca63e39c7c Mon Sep 17 00:00:00 2001
>From: Massimo Valentini <mvalentini@src.gnome.org>
>Date: Mon, 1 Sep 2014 07:37:22 +0200
>Subject: [PATCH] Bug 59098: segfault in cairo-polygon-intersect.c:
> active_edges()
>
>this implementation of the sweep_line treats edges to be translated
>upward and shrinked by 1 and 2 epsilon.
>
>It means that all edge lower vertices are considered positioned at
>an y = nominal y - 2 * epsilon, the upper points at y - epsilon.
>
>It follows that events having the same y are processed in the order:
>
>STOP prior than START prior than INTERSECTION (floored to integer).
>
>This way START and STOP events should find the active-edges
>list correctly sorted, and sorting the new edges also using
>slope_compare should not miss intersection, nor move the sweep line
>back and forth.
>---
> src/cairo-polygon-intersect.c | 61 ++++++++++++++-----------------------------
> 1 file changed, 19 insertions(+), 42 deletions(-)
>
>diff --git a/src/cairo-polygon-intersect.c b/src/cairo-polygon-intersect.c
>index 2cd73d2..4b8210e 100644
>--- a/src/cairo-polygon-intersect.c
>+++ b/src/cairo-polygon-intersect.c
>@@ -77,9 +77,9 @@ struct _cairo_bo_edge {
> #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
> 
> typedef enum {
>-    CAIRO_BO_EVENT_TYPE_STOP,
>-    CAIRO_BO_EVENT_TYPE_INTERSECTION,
>-    CAIRO_BO_EVENT_TYPE_START
>+    CAIRO_BO_EVENT_TYPE_STOP = -1,
>+    CAIRO_BO_EVENT_TYPE_START = 0,
>+    CAIRO_BO_EVENT_TYPE_INTERSECTION = 1
> } cairo_bo_event_type_t;
> 
> typedef struct _cairo_bo_event {
>@@ -141,19 +141,6 @@ _line_compute_intersection_x_for_y (const cairo_line_t *line,
>     return x;
> }
> 
>-static inline int
>-_cairo_bo_point32_compare (cairo_bo_point32_t const *a,
>-			   cairo_bo_point32_t const *b)
>-{
>-    int cmp;
>-
>-    cmp = a->y - b->y;
>-    if (cmp)
>-	return cmp;
>-
>-    return a->x - b->x;
>-}
>-
> /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
>  * slope a is respectively greater than, equal to, or less than the
>  * slope of b.
>@@ -444,7 +431,7 @@ edges_compare_x_for_y (const cairo_bo_edge_t *a,
>        HAVE_BX      = 0x2,
>        HAVE_BOTH    = HAVE_AX | HAVE_BX
>     } have_ax_bx = HAVE_BOTH;
>-    int32_t ax, bx;
>+    int32_t ax = 0, bx = 0;
> 
>     if (y == a->edge.line.p1.y)
> 	ax = a->edge.line.p1.x;
>@@ -610,21 +597,14 @@ intersect_lines (cairo_bo_edge_t		*a,
> 					 den_det);
>     if (_cairo_int64_eq (qr.rem, den_det))
> 	return FALSE;
>-#if 0
>-    intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
>-#else
>+
>     intersection->x.exactness = EXACT;
>     if (! _cairo_int64_is_zero (qr.rem)) {
> 	if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
>-	    qr.rem = _cairo_int64_negate (qr.rem);
>-	qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
>-	if (_cairo_int64_ge (qr.rem, den_det)) {
>-	    qr.quo = _cairo_int64_add (qr.quo,
>-				       _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
>-	} else
>-	    intersection->x.exactness = INEXACT;
>+            qr.quo = _cairo_int64_add (qr.quo, _cairo_int32_to_int64 (-1));
>+
>+        intersection->y.exactness = INEXACT;
>     }
>-#endif
>     intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo);
> 
>     /* y = det (a_det, dy1, b_det, dy2) / den_det */
>@@ -633,21 +613,14 @@ intersect_lines (cairo_bo_edge_t		*a,
> 					 den_det);
>     if (_cairo_int64_eq (qr.rem, den_det))
> 	return FALSE;
>-#if 0
>-    intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
>-#else
>+
>     intersection->y.exactness = EXACT;
>     if (! _cairo_int64_is_zero (qr.rem)) {
> 	if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
>-	    qr.rem = _cairo_int64_negate (qr.rem);
>-	qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
>-	if (_cairo_int64_ge (qr.rem, den_det)) {
>-	    qr.quo = _cairo_int64_add (qr.quo,
>-				       _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
>-	} else
>-	    intersection->y.exactness = INEXACT;
>+            qr.quo = _cairo_int64_add (qr.quo, _cairo_int32_to_int64 (-1));
>+
>+        intersection->y.exactness = INEXACT;
>     }
>-#endif
>     intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo);
> 
>     return TRUE;
>@@ -728,7 +701,7 @@ _cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t		*edge,
> 
> 	top_x = _line_compute_intersection_x_for_y (&edge->edge.line,
> 						    edge->edge.top);
>-	return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) > 0;
>+	return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) >= 0;
>     } else { /* cmp_bottom == 0 */
> 	cairo_fixed_t bot_x;
> 
>@@ -787,7 +760,7 @@ cairo_bo_event_compare (const cairo_bo_event_t *a,
> {
>     int cmp;
> 
>-    cmp = _cairo_bo_point32_compare (&a->point, &b->point);
>+    cmp = a->point.y - b->point.y;
>     if (cmp)
> 	return cmp;
> 
>@@ -795,7 +768,11 @@ cairo_bo_event_compare (const cairo_bo_event_t *a,
>     if (cmp)
> 	return cmp;
> 
>-    return a - b;
>+    cmp = a->point.x - b->point.x;
>+    if (cmp)
>+	return cmp;
>+
>+    return a < b ? -1 : a == b ? 0 : 1;
> }
> 
> static inline void
>-- 
>1.9.3
>

Actions: View | Splinter Review

Attachments on bug 74779: 93749 | 95645 | 95646 | 95665 | 104163 | 104273 | 104274 | 105530 | 106407 | 106722

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.