From 64c306106b78f08c74908af717b7f5f4b49e444d Mon Sep 17 00:00:00 2001 From: Massimo Valentini Date: Wed, 6 Aug 2014 18:42:21 +0200 Subject: [PATCH] Bug 59098: segfault in cairo-polygon-intersect.c: active_edges() when the remainder of an integer division is negative the quotient is 1 unit above the 'floored' division (don't compute the remainder as it is not used) and storing the difference of 2 pointers in a signed int invokes undefined behaviour on 64 bit platforms and it seems that when a start event introduces an edge with an intersection at the same y as the endpoint but with a smaller x the intersection event is not added and the edge is never swapped with the other, resulting in an active edges list non sorted, the brittle work-around is to insert edges ordered 1 unit below the sweep-line, this is mainly intended to show where is a problem. --- src/cairo-polygon-intersect.c | 48 ++++++++++++++++--------------------------- 1 file changed, 18 insertions(+), 30 deletions(-) diff --git a/src/cairo-polygon-intersect.c b/src/cairo-polygon-intersect.c index 2cd73d2..46cf7c9 100644 --- a/src/cairo-polygon-intersect.c +++ b/src/cairo-polygon-intersect.c @@ -489,7 +489,7 @@ _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line, /* compare the edges if not identical */ if (! _line_equal (&a->edge.line, &b->edge.line)) { - cmp = edges_compare_x_for_y (a, b, sweep_line->current_y); + cmp = edges_compare_x_for_y (a, b, sweep_line->current_y + 1); if (cmp) return cmp; @@ -610,21 +610,15 @@ 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; - } -#endif + if (! _cairo_int64_is_zero (qr.rem)) + { + if (_cairo_int64_negative (qr.rem)) + qr.quo = _cairo_int64_add (qr.quo, _cairo_int32_to_int64 (-1)); + + intersection->y.exactness = INEXACT; + } intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo); /* y = det (a_det, dy1, b_det, dy2) / den_det */ @@ -633,21 +627,15 @@ 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; - } -#endif + if (! _cairo_int64_is_zero (qr.rem)) + { + if (_cairo_int64_negative (qr.rem)) + qr.quo = _cairo_int64_add (qr.quo, _cairo_int32_to_int64 (-1)); + + intersection->y.exactness = INEXACT; + } intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo); return TRUE; @@ -795,7 +783,7 @@ cairo_bo_event_compare (const cairo_bo_event_t *a, if (cmp) return cmp; - return a - b; + return a < b ? -1 : 1; } static inline void -- 1.9.3