diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c index 792fbfa..b7e0742 100644 --- a/src/cairo-path-stroke.c +++ b/src/cairo-path-stroke.c @@ -36,6 +36,9 @@ #include "cairoint.h" +/* device space maximum representable double. */ +#define RANGE_MAX (32767.0 + 65535.0/65536.0) + typedef struct cairo_stroker { cairo_stroke_style_t *style; @@ -108,6 +111,11 @@ _cairo_stroker_face_clockwise (cairo_str static cairo_status_t _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out); +static double +_cairo_stroker_hypot (double x, double y); + +static double +_cairo_stroker_normalise_vector (double *x, double *y); static void _cairo_stroker_start_dash (cairo_stroker_t *stroker) @@ -260,8 +268,8 @@ _cairo_stroker_join (cairo_stroker_t *st case CAIRO_LINE_JOIN_MITER: default: { /* dot product of incoming slope vector with outgoing slope vector */ - double in_dot_out = ((-in->usr_vector.x * out->usr_vector.x)+ - (-in->usr_vector.y * out->usr_vector.y)); + double in_dot_out = ((in->usr_vector.x * out->usr_vector.x)+ + (in->usr_vector.y * out->usr_vector.y)); double ml = stroker->style->miter_limit; /* @@ -275,13 +283,11 @@ _cairo_stroker_join (cairo_stroker_t *st * * where psi is the angle between in and out * - * secant(psi/2) = 1/sin(psi/2) - * 1/sin(psi/2) <= ml - * 1 <= ml sin(psi/2) - * 1 <= ml² sin²(psi/2) - * 2 <= ml² 2 sin²(psi/2) - * 2·sin²(psi/2) = 1-cos(psi) - * 2 <= ml² (1-cos(psi)) + * secant(psi/2) = 1/cos(psi/2) + * 1/cos(psi/2) <= ml + * 1 <= ml cos(psi/2) + * 1 <= ml² cos(psi/2)² + * 2 <= ml² (1 + cos(psi)) * * in · out = |in| |out| cos (psi) * @@ -289,10 +295,10 @@ _cairo_stroker_join (cairo_stroker_t *st * * in · out = cos (psi) * - * 2 <= ml² (1 - in · out) + * 2 <= ml² (1 + in · out) * */ - if (2 <= ml * ml * (1 - in_dot_out)) { + if (2 <= ml * ml * (1 + in_dot_out)) { double x1, y1, x2, y2; double mx, my; double dx1, dx2, dy1, dy2; @@ -310,6 +316,8 @@ _cairo_stroker_join (cairo_stroker_t *st y1 = _cairo_fixed_to_double (inpt->y); dx1 = in->usr_vector.x; dy1 = in->usr_vector.y; + if (0.0 == dx1 && 0.0 == dy1) + goto FALL_BACK_TO_BEVEL; cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1); /* outer point of outgoing line face */ @@ -317,6 +325,8 @@ _cairo_stroker_join (cairo_stroker_t *st y2 = _cairo_fixed_to_double (outpt->y); dx2 = out->usr_vector.x; dy2 = out->usr_vector.y; + if (0.0 == dx2 && 0.0 == dy2) + goto FALL_BACK_TO_BEVEL; cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2); /* @@ -333,6 +343,8 @@ _cairo_stroker_join (cairo_stroker_t *st mx = (my - y1) * dx1 / dy1 + x1; else mx = (my - y2) * dx2 / dy2 + x2; + if ( ! (fabs (mx) <= RANGE_MAX && fabs (my) <= RANGE_MAX) ) + goto FALL_BACK_TO_BEVEL; /* * Draw the quadrilateral @@ -354,7 +366,8 @@ _cairo_stroker_join (cairo_stroker_t *st } /* fall through ... */ } - case CAIRO_LINE_JOIN_BEVEL: { + case CAIRO_LINE_JOIN_BEVEL: + FALL_BACK_TO_BEVEL: { cairo_point_t tri[3]; tri[0] = in->point; tri[1] = *inpt; @@ -499,10 +512,47 @@ _cairo_stroker_add_caps (cairo_stroker_t return CAIRO_STATUS_SUCCESS; } +/* Compute sqrt(x^2 + y^2) with less chance of underflow. Returns + * zero for NaNs. May return positive infinity. */ +static double +_cairo_stroker_hypot (double x, double y) +{ + x = fabs (x); y = fabs (y); + if (x==0 && y==0) { return 0.0; } + if (x <= y) { + double q = x/y; + return y*sqrt(q*q + 1); + } + else if (x > y) { + double q = y/x; + return x*sqrt(q*q + 1); + } + return 0.0; +} + +/* Normalises a vector to unit length and returns the magnitude of the + * vector before normalisation. If the vector has NaN components, or + * the computation of its norm overflowed, sets the components to zero + * and returns zero. */ +static double +_cairo_stroker_normalise_vector (double *x, double *y) +{ + double norm = _cairo_stroker_hypot (*x, *y); + if (0.0 != norm) { + *x /= norm; + *y /= norm; + if (norm <= HUGE_VAL) + return norm; + } + *x = 0.0; + *y = 0.0; + return 0.0; +} + static void _compute_face (cairo_point_t *point, cairo_slope_t *slope, cairo_stroker_t *stroker, cairo_stroke_face_t *face) { - double mag, det; + double det; double line_dx, line_dy; double face_dx, face_dy; cairo_point_double_t usr_vector; @@ -514,16 +564,8 @@ _compute_face (cairo_point_t *point, cai /* faces are normal in user space, not device space */ cairo_matrix_transform_distance (stroker->ctm_inverse, &line_dx, &line_dy); - mag = sqrt (line_dx * line_dx + line_dy * line_dy); - if (mag == 0) { - /* XXX: Can't compute other face points. Do we want a tag in the face for this case? */ - return; - } - - /* normalize to unit length */ - line_dx /= mag; - line_dy /= mag; - + /* normalize to unit length or the zero vector. */ + _cairo_stroker_normalise_vector (&line_dx, &line_dy); usr_vector.x = line_dx; usr_vector.y = line_dy; @@ -711,7 +753,7 @@ _cairo_stroker_line_to_dashed (void *clo cairo_matrix_transform_distance (stroker->ctm_inverse, &dx, &dy); - mag = sqrt (dx *dx + dy * dy); + mag = _cairo_stroker_hypot (dx, dy); remain = mag; fd1 = *p1; while (remain) { diff --git a/src/cairo-pen.c b/src/cairo-pen.c index 87de9a4..5769b4a 100644 --- a/src/cairo-pen.c +++ b/src/cairo-pen.c @@ -36,6 +36,14 @@ #include "cairoint.h" +/* Maximum number of pen vertices we can fit in 2G of memory, less + * four to allow for the spline stroker to add them. */ +#define MAX_PEN_VERTICES (2*(0x3FFFFFFF / sizeof(cairo_pen_vertex_t)) - 4) + +/* limits on the device space. */ +#define RANGE_MAX (32767.0 + 65535.0/65536.0) +#define RANGE_MIN (-32768.0) + static int _cairo_pen_vertices_needed (double tolerance, double radius, cairo_matrix_t *matrix); @@ -45,6 +53,9 @@ _cairo_pen_compute_slopes (cairo_pen_t * static cairo_status_t _cairo_pen_stroke_spline_half (cairo_pen_t *pen, cairo_spline_t *spline, cairo_direction_t dir, cairo_polygon_t *polygon); +static int +_cairo_pen_clamp_double_to_device_space (double *x); + cairo_status_t _cairo_pen_init_empty (cairo_pen_t *pen) { @@ -56,6 +67,23 @@ _cairo_pen_init_empty (cairo_pen_t *pen) return CAIRO_STATUS_SUCCESS; } +static int +_cairo_pen_clamp_double_to_device_space (double *x) +{ + if (RANGE_MIN <= *x && *x <= RANGE_MAX) { + return 1; + } + else if (*x >= RANGE_MAX) { + *x = RANGE_MAX; + return 1; + } + else if (*x < RANGE_MIN) { + *x = RANGE_MIN; + return 1; + } + return 0; +} + cairo_status_t _cairo_pen_init (cairo_pen_t *pen, double radius, @@ -80,7 +108,7 @@ _cairo_pen_init (cairo_pen_t *pen, radius, ctm); - pen->vertices = malloc (pen->num_vertices * sizeof (cairo_pen_vertex_t)); + pen->vertices = calloc (pen->num_vertices, sizeof (cairo_pen_vertex_t)); if (pen->vertices == NULL) { return CAIRO_STATUS_NO_MEMORY; } @@ -97,6 +125,12 @@ _cairo_pen_init (cairo_pen_t *pen, double dy = radius * sin (reflect ? -theta : theta); cairo_pen_vertex_t *v = &pen->vertices[i]; cairo_matrix_transform_distance (ctm, &dx, &dy); + + if (! _cairo_pen_clamp_double_to_device_space (&dx)) + continue; + if (! _cairo_pen_clamp_double_to_device_space (&dy)) + continue; + v->point.x = _cairo_fixed_from_double (dx); v->point.y = _cairo_fixed_from_double (dy); } @@ -259,19 +293,29 @@ _cairo_pen_vertices_needed (double t * compute number of vertices needed */ int num_vertices; + double step = 1 - tolerance / major_axis; /* Where tolerance / M is > 1, we use 4 points */ - if (tolerance >= major_axis) { - num_vertices = 4; - } else { - double delta = acos (1 - tolerance / major_axis); - num_vertices = ceil (M_PI / delta); - - /* number of vertices must be even */ - if (num_vertices % 2) - num_vertices++; + if (step > 0 && step < 1) { + double delta = acos (step); + double num_vertices_double = ceil (M_PI / delta); + + if (num_vertices_double >= 4) { + if (num_vertices_double < MAX_PEN_VERTICES) { + int num_vertices = num_vertices_double; + + /* number of vertices must be even */ + if (num_vertices % 2) + num_vertices++; + return num_vertices; + } + /* Infinity or just too big. */ + return MAX_PEN_VERTICES; + } } - return num_vertices; + /* At this point we've either got NaNs somewhere or too few + * vertices. */ + return 4; } static void @@ -315,6 +359,8 @@ _cairo_pen_find_active_cw_vertex_index ( break; } + if (i >= pen->num_vertices) + i = pen->num_vertices/2; *active = i; return CAIRO_STATUS_SUCCESS; @@ -343,6 +389,8 @@ _cairo_pen_find_active_ccw_vertex_index break; } + if (i < 0) + i = 0; *active = i; return CAIRO_STATUS_SUCCESS; @@ -423,7 +471,7 @@ _cairo_pen_stroke_spline (cairo_pen_t * /* If the line width is so small that the pen is reduced to a single point, then we have nothing to do. */ - if (pen->num_vertices <= 1) + if (pen->num_vertices <= 1 || ! (tolerance > 0)) return CAIRO_STATUS_SUCCESS; _cairo_polygon_init (&polygon);