cairo-path-fixed.c

/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
/* cairo - a vector graphics library with display and print output
 *
 * Copyright © 2002 University of Southern California
 * Copyright © 2005 Red Hat, Inc.
  *
 * This library is free software; you can redistribute it and/or
 * modify it either under the terms of the GNU Lesser General Public
 * License version 2.1 as published by the Free Software Foundation
 * (the "LGPL") or, at your option, under the terms of the Mozilla
 * Public License Version 1.1 (the "MPL"). If you do not alter this
 * notice, a recipient may use your version of this file under either
 * the MPL or the LGPL.
 *
 * You should have received a copy of the LGPL along with this library
 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
 * You should have received a copy of the MPL along with this library
 * in the file COPYING-MPL-1.1
 *
 * The contents of this file are subject to the Mozilla Public License
 * Version 1.1 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
 * the specific language governing rights and limitations.
 *
 * The Original Code is the cairo graphics library.
 *
 * The Initial Developer of the Original Code is University of Southern
 * California.
 *
 * Contributor(s):
 *	Carl D. Worth <cworth@cworth.org>
 */

#include "cairoint.h"

#include "cairo-box-inline.h"
#include "cairo-error-private.h"
#include "cairo-list-inline.h"
#include "cairo-path-fixed-private.h"
#include "cairo-slope-private.h"

static cairo_status_t
_cairo_path_fixed_add (cairo_path_fixed_t  *path,
		       cairo_path_op_t	    op,
		       const cairo_point_t *points,
		       int		    num_points);

static void
_cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
			   cairo_path_buf_t   *buf);

static cairo_path_buf_t *
_cairo_path_buf_create (int size_ops, int size_points);

static void
_cairo_path_buf_destroy (cairo_path_buf_t *buf);

static void
_cairo_path_buf_add_op (cairo_path_buf_t *buf,
			cairo_path_op_t   op);

static void
_cairo_path_buf_add_points (cairo_path_buf_t       *buf,
			    const cairo_point_t    *points,
			    int		            num_points);

#define cairo_path_head(path__) (&(path__)->buf.base)
#define cairo_path_tail(path__) cairo_path_buf_prev (cairo_path_head (path__))

#define cairo_path_buf_next(pos__) \
    cairo_list_entry ((pos__)->link.next, cairo_path_buf_t, link)
#define cairo_path_buf_prev(pos__) \
    cairo_list_entry ((pos__)->link.prev, cairo_path_buf_t, link)

#define cairo_path_foreach_buf_start(pos__, path__) \
    pos__ = cairo_path_head (path__); do
#define cairo_path_foreach_buf_end(pos__, path__) \
    while ((pos__ = cairo_path_buf_next (pos__)) !=  cairo_path_head (path__))

void
_cairo_path_fixed_init (cairo_path_fixed_t *path)
{
    VG (VALGRIND_MAKE_MEM_UNDEFINED (path, sizeof (cairo_path_fixed_t)));

    cairo_list_init (&path->buf.base.link);

    path->buf.base.num_ops = 0;
    path->buf.base.num_points = 0;
    path->buf.base.size_ops = ARRAY_LENGTH (path->buf.op);
    path->buf.base.size_points = ARRAY_LENGTH (path->buf.points);
    path->buf.base.op = path->buf.op;
    path->buf.base.points = path->buf.points;

    path->current_point.x = 0;
    path->current_point.y = 0;
    path->last_move_point = path->current_point;

    path->has_current_point = FALSE;
    path->needs_move_to = TRUE;
    path->has_extents = FALSE;
    path->has_curve_to = FALSE;
    path->stroke_is_rectilinear = TRUE;
    path->fill_is_rectilinear = TRUE;
    path->fill_maybe_region = TRUE;
    path->fill_is_empty = TRUE;

    path->extents.p1.x = path->extents.p1.y = 0;
    path->extents.p2.x = path->extents.p2.y = 0;
}

cairo_status_t
_cairo_path_fixed_init_copy (cairo_path_fixed_t *path,
			     const cairo_path_fixed_t *other)
{
    cairo_path_buf_t *buf, *other_buf;
    unsigned int num_points, num_ops;

    VG (VALGRIND_MAKE_MEM_UNDEFINED (path, sizeof (cairo_path_fixed_t)));

    cairo_list_init (&path->buf.base.link);

    path->buf.base.op = path->buf.op;
    path->buf.base.points = path->buf.points;
    path->buf.base.size_ops = ARRAY_LENGTH (path->buf.op);
    path->buf.base.size_points = ARRAY_LENGTH (path->buf.points);

    path->current_point = other->current_point;
    path->last_move_point = other->last_move_point;

    path->has_current_point = other->has_current_point;
    path->needs_move_to = other->needs_move_to;
    path->has_extents = other->has_extents;
    path->has_curve_to = other->has_curve_to;
    path->stroke_is_rectilinear = other->stroke_is_rectilinear;
    path->fill_is_rectilinear = other->fill_is_rectilinear;
    path->fill_maybe_region = other->fill_maybe_region;
    path->fill_is_empty = other->fill_is_empty;

    path->extents = other->extents;

    path->buf.base.num_ops = other->buf.base.num_ops;
    path->buf.base.num_points = other->buf.base.num_points;
    memcpy (path->buf.op, other->buf.base.op,
	    other->buf.base.num_ops * sizeof (other->buf.op[0]));
    memcpy (path->buf.points, other->buf.points,
	    other->buf.base.num_points * sizeof (other->buf.points[0]));

    num_points = num_ops = 0;
    for (other_buf = cairo_path_buf_next (cairo_path_head (other));
	 other_buf != cairo_path_head (other);
	 other_buf = cairo_path_buf_next (other_buf))
    {
	num_ops    += other_buf->num_ops;
	num_points += other_buf->num_points;
    }

    if (num_ops) {
	buf = _cairo_path_buf_create (num_ops, num_points);
	if (unlikely (buf == NULL)) {
	    _cairo_path_fixed_fini (path);
	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
	}

	for (other_buf = cairo_path_buf_next (cairo_path_head (other));
	     other_buf != cairo_path_head (other);
	     other_buf = cairo_path_buf_next (other_buf))
	{
	    memcpy (buf->op + buf->num_ops, other_buf->op,
		    other_buf->num_ops * sizeof (buf->op[0]));
	    buf->num_ops += other_buf->num_ops;

	    memcpy (buf->points + buf->num_points, other_buf->points,
		    other_buf->num_points * sizeof (buf->points[0]));
	    buf->num_points += other_buf->num_points;
	}

	_cairo_path_fixed_add_buf (path, buf);
    }

    return CAIRO_STATUS_SUCCESS;
}

unsigned long
_cairo_path_fixed_hash (const cairo_path_fixed_t *path)
{
    unsigned long hash = _CAIRO_HASH_INIT_VALUE;
    const cairo_path_buf_t *buf;
    unsigned int count;

    count = 0;
    cairo_path_foreach_buf_start (buf, path) {
	hash = _cairo_hash_bytes (hash, buf->op,
			          buf->num_ops * sizeof (buf->op[0]));
	count += buf->num_ops;
    } cairo_path_foreach_buf_end (buf, path);
    hash = _cairo_hash_bytes (hash, &count, sizeof (count));

    count = 0;
    cairo_path_foreach_buf_start (buf, path) {
	hash = _cairo_hash_bytes (hash, buf->points,
			          buf->num_points * sizeof (buf->points[0]));
	count += buf->num_points;
    } cairo_path_foreach_buf_end (buf, path);
    hash = _cairo_hash_bytes (hash, &count, sizeof (count));

    return hash;
}

unsigned long
_cairo_path_fixed_size (const cairo_path_fixed_t *path)
{
    const cairo_path_buf_t *buf;
    int num_points, num_ops;

    num_ops = num_points = 0;
    cairo_path_foreach_buf_start (buf, path) {
	num_ops    += buf->num_ops;
	num_points += buf->num_points;
    } cairo_path_foreach_buf_end (buf, path);

    return num_ops * sizeof (buf->op[0]) +
	   num_points * sizeof (buf->points[0]);
}

cairo_bool_t
_cairo_path_fixed_equal (const cairo_path_fixed_t *a,
			 const cairo_path_fixed_t *b)
{
    const cairo_path_buf_t *buf_a, *buf_b;
    const cairo_path_op_t *ops_a, *ops_b;
    const cairo_point_t *points_a, *points_b;
    int num_points_a, num_ops_a;
    int num_points_b, num_ops_b;

    if (a == b)
	return TRUE;

    /* use the flags to quickly differentiate based on contents */
    if (a->has_curve_to != b->has_curve_to)
    {
	return FALSE;
    }

    if (a->extents.p1.x != b->extents.p1.x ||
	a->extents.p1.y != b->extents.p1.y ||
	a->extents.p2.x != b->extents.p2.x ||
	a->extents.p2.y != b->extents.p2.y)
    {
	return FALSE;
    }

    num_ops_a = num_points_a = 0;
    cairo_path_foreach_buf_start (buf_a, a) {
	num_ops_a    += buf_a->num_ops;
	num_points_a += buf_a->num_points;
    } cairo_path_foreach_buf_end (buf_a, a);

    num_ops_b = num_points_b = 0;
    cairo_path_foreach_buf_start (buf_b, b) {
	num_ops_b    += buf_b->num_ops;
	num_points_b += buf_b->num_points;
    } cairo_path_foreach_buf_end (buf_b, b);

    if (num_ops_a == 0 && num_ops_b == 0)
	return TRUE;

    if (num_ops_a != num_ops_b || num_points_a != num_points_b)
	return FALSE;

    buf_a = cairo_path_head (a);
    num_points_a = buf_a->num_points;
    num_ops_a = buf_a->num_ops;
    ops_a = buf_a->op;
    points_a = buf_a->points;

    buf_b = cairo_path_head (b);
    num_points_b = buf_b->num_points;
    num_ops_b = buf_b->num_ops;
    ops_b = buf_b->op;
    points_b = buf_b->points;

    while (TRUE) {
	int num_ops = MIN (num_ops_a, num_ops_b);
	int num_points = MIN (num_points_a, num_points_b);

	if (memcmp (ops_a, ops_b, num_ops * sizeof (cairo_path_op_t)))
	    return FALSE;
	if (memcmp (points_a, points_b, num_points * sizeof (cairo_point_t)))
	    return FALSE;

	num_ops_a -= num_ops;
	ops_a += num_ops;
	num_points_a -= num_points;
	points_a += num_points;
	if (num_ops_a == 0 || num_points_a == 0) {
	    if (num_ops_a || num_points_a)
		return FALSE;

	    buf_a = cairo_path_buf_next (buf_a);
	    if (buf_a == cairo_path_head (a))
		break;

	    num_points_a = buf_a->num_points;
	    num_ops_a = buf_a->num_ops;
	    ops_a = buf_a->op;
	    points_a = buf_a->points;
	}

	num_ops_b -= num_ops;
	ops_b += num_ops;
	num_points_b -= num_points;
	points_b += num_points;
	if (num_ops_b == 0 || num_points_b == 0) {
	    if (num_ops_b || num_points_b)
		return FALSE;

	    buf_b = cairo_path_buf_next (buf_b);
	    if (buf_b == cairo_path_head (b))
		break;

	    num_points_b = buf_b->num_points;
	    num_ops_b = buf_b->num_ops;
	    ops_b = buf_b->op;
	    points_b = buf_b->points;
	}
    }

    return TRUE;
}

cairo_path_fixed_t *
_cairo_path_fixed_create (void)
{
    cairo_path_fixed_t	*path;

    path = malloc (sizeof (cairo_path_fixed_t));
    if (!path) {
	_cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
	return NULL;
    }

    _cairo_path_fixed_init (path);
    return path;
}

void
_cairo_path_fixed_fini (cairo_path_fixed_t *path)
{
    cairo_path_buf_t *buf;

    buf = cairo_path_buf_next (cairo_path_head (path));
    while (buf != cairo_path_head (path)) {
	cairo_path_buf_t *this = buf;
	buf = cairo_path_buf_next (buf);
	_cairo_path_buf_destroy (this);
    }

    VG (VALGRIND_MAKE_MEM_NOACCESS (path, sizeof (cairo_path_fixed_t)));
}

void
_cairo_path_fixed_destroy (cairo_path_fixed_t *path)
{
    _cairo_path_fixed_fini (path);
    free (path);
}

static cairo_path_op_t
_cairo_path_fixed_last_op (cairo_path_fixed_t *path)
{
    cairo_path_buf_t *buf;

    buf = cairo_path_tail (path);
    assert (buf->num_ops != 0);

    return buf->op[buf->num_ops - 1];
}

static inline const cairo_point_t *
_cairo_path_fixed_penultimate_point (cairo_path_fixed_t *path)
{
    cairo_path_buf_t *buf;

    buf = cairo_path_tail (path);
    if (likely (buf->num_points >= 2)) {
	return &buf->points[buf->num_points - 2];
    } else {
	cairo_path_buf_t *prev_buf = cairo_path_buf_prev (buf);

	assert (prev_buf->num_points >= 2 - buf->num_points);
	return &prev_buf->points[prev_buf->num_points - (2 - buf->num_points)];
    }
}

static void
_cairo_path_fixed_drop_line_to (cairo_path_fixed_t *path)
{
    cairo_path_buf_t *buf;

    assert (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO);

    buf = cairo_path_tail (path);
    buf->num_points--;
    buf->num_ops--;
}

cairo_status_t
_cairo_path_fixed_move_to (cairo_path_fixed_t  *path,
			   cairo_fixed_t	x,
			   cairo_fixed_t	y)
{
    _cairo_path_fixed_new_sub_path (path);

    path->has_current_point = TRUE;
    path->current_point.x = x;
    path->current_point.y = y;
    path->last_move_point = path->current_point;

    return CAIRO_STATUS_SUCCESS;
}

static cairo_status_t
_cairo_path_fixed_move_to_apply (cairo_path_fixed_t  *path)
{
    if (likely (! path->needs_move_to))
	return CAIRO_STATUS_SUCCESS;

    path->needs_move_to = FALSE;

    if (path->has_extents) {
	_cairo_box_add_point (&path->extents, &path->current_point);
    } else {
	_cairo_box_set (&path->extents, &path->current_point, &path->current_point);
	path->has_extents = TRUE;
    }

    if (path->fill_maybe_region) {
	path->fill_maybe_region = _cairo_fixed_is_integer (path->current_point.x) &&
				  _cairo_fixed_is_integer (path->current_point.y);
    }

    path->last_move_point = path->current_point;

    return _cairo_path_fixed_add (path, CAIRO_PATH_OP_MOVE_TO, &path->current_point, 1);
}

void
_cairo_path_fixed_new_sub_path (cairo_path_fixed_t *path)
{
    if (! path->needs_move_to) {
	/* If the current subpath doesn't need_move_to, it contains at least one command */
	if (path->fill_is_rectilinear) {
	    /* Implicitly close for fill */
	    path->fill_is_rectilinear = path->current_point.x == path->last_move_point.x ||
					path->current_point.y == path->last_move_point.y;
	    path->fill_maybe_region &= path->fill_is_rectilinear;
	}
	path->needs_move_to = TRUE;
    }

    path->has_current_point = FALSE;
}

cairo_status_t
_cairo_path_fixed_rel_move_to (cairo_path_fixed_t *path,
			       cairo_fixed_t	   dx,
			       cairo_fixed_t	   dy)
{
    if (unlikely (! path->has_current_point))
	return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);

    return _cairo_path_fixed_move_to (path,
				      path->current_point.x + dx,
				      path->current_point.y + dy);

}

cairo_status_t
_cairo_path_fixed_line_to (cairo_path_fixed_t *path,
			   cairo_fixed_t	x,
			   cairo_fixed_t	y)
{
    cairo_status_t status;
    cairo_point_t point;

    point.x = x;
    point.y = y;

    /* When there is not yet a current point, the line_to operation
     * becomes a move_to instead. Note: We have to do this by
     * explicitly calling into _cairo_path_fixed_move_to to ensure
     * that the last_move_point state is updated properly.
     */
    if (! path->has_current_point)
	return _cairo_path_fixed_move_to (path, point.x, point.y);

    status = _cairo_path_fixed_move_to_apply (path);
    if (unlikely (status))
	return status;

    /* If the previous op was but the initial MOVE_TO and this segment
     * is degenerate, then we can simply skip this point. Note that
     * a move-to followed by a degenerate line-to is a valid path for
     * stroking, but at all other times is simply a degenerate segment.
     */
    if (_cairo_path_fixed_last_op (path) != CAIRO_PATH_OP_MOVE_TO) {
	if (x == path->current_point.x && y == path->current_point.y)
	    return CAIRO_STATUS_SUCCESS;
    }

    /* If the previous op was also a LINE_TO with the same gradient,
     * then just change its end-point rather than adding a new op.
     */
    if (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO) {
	const cairo_point_t *p;

	p = _cairo_path_fixed_penultimate_point (path);
	if (p->x == path->current_point.x && p->y == path->current_point.y) {
	    /* previous line element was degenerate, replace */
	    _cairo_path_fixed_drop_line_to (path);
	} else {
	    cairo_slope_t prev, self;

	    _cairo_slope_init (&prev, p, &path->current_point);
	    _cairo_slope_init (&self, &path->current_point, &point);
	    if (_cairo_slope_equal (&prev, &self) &&
		/* cannot trim anti-parallel segments whilst stroking */
		! _cairo_slope_backwards (&prev, &self))
	    {
		_cairo_path_fixed_drop_line_to (path);
		/* In this case the flags might be more restrictive than
		 * what we actually need.
		 * When changing the flags definition we should check if
		 * changing the line_to point can affect them.
		*/
	    }
	}
    }

    if (path->stroke_is_rectilinear) {
	path->stroke_is_rectilinear = path->current_point.x == x ||
				      path->current_point.y == y;
	path->fill_is_rectilinear &= path->stroke_is_rectilinear;
	path->fill_maybe_region &= path->fill_is_rectilinear;
	if (path->fill_maybe_region) {
	    path->fill_maybe_region = _cairo_fixed_is_integer (x) &&
				      _cairo_fixed_is_integer (y);
	}
	if (path->fill_is_empty) {
	    path->fill_is_empty = path->current_point.x == x &&
				  path->current_point.y == y;
	}
    }

    path->current_point = point;

    _cairo_box_add_point (&path->extents, &point);

    return _cairo_path_fixed_add (path, CAIRO_PATH_OP_LINE_TO, &point, 1);
}

cairo_status_t
_cairo_path_fixed_rel_line_to (cairo_path_fixed_t *path,
			       cairo_fixed_t	   dx,
			       cairo_fixed_t	   dy)
{
    if (unlikely (! path->has_current_point))
	return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);

    return _cairo_path_fixed_line_to (path,
				      path->current_point.x + dx,
				      path->current_point.y + dy);
}

cairo_status_t
_cairo_path_fixed_curve_to (cairo_path_fixed_t	*path,
			    cairo_fixed_t x0, cairo_fixed_t y0,
			    cairo_fixed_t x1, cairo_fixed_t y1,
			    cairo_fixed_t x2, cairo_fixed_t y2)
{
    cairo_status_t status;
    cairo_point_t point[3];

    /* If this curves does not move, replace it with a line-to.
     * This frequently happens with rounded-rectangles and r==0.
    */
    if (path->current_point.x == x2 && path->current_point.y == y2) {
	if (x1 == x2 && x0 == x2 && y1 == y2 && y0 == y2)
	    return _cairo_path_fixed_line_to (path, x2, y2);

	/* We may want to check for the absence of a cusp, in which case
	 * we can also replace the curve-to with a line-to.
	 */
    }

    /* make sure subpaths are started properly */
    if (! path->has_current_point) {
	status = _cairo_path_fixed_move_to (path, x0, y0);
	assert (status == CAIRO_STATUS_SUCCESS);
    }

    status = _cairo_path_fixed_move_to_apply (path);
    if (unlikely (status))
	return status;

    /* If the previous op was a degenerate LINE_TO, drop it. */
    if (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO) {
	const cairo_point_t *p;

	p = _cairo_path_fixed_penultimate_point (path);
	if (p->x == path->current_point.x && p->y == path->current_point.y) {
	    /* previous line element was degenerate, replace */
	    _cairo_path_fixed_drop_line_to (path);
	}
    }

    point[0].x = x0; point[0].y = y0;
    point[1].x = x1; point[1].y = y1;
    point[2].x = x2; point[2].y = y2;

    _cairo_box_add_curve_to (&path->extents, &path->current_point,
			     &point[0], &point[1], &point[2]);

    path->current_point = point[2];
    path->has_curve_to = TRUE;
    path->stroke_is_rectilinear = FALSE;
    path->fill_is_rectilinear = FALSE;
    path->fill_maybe_region = FALSE;
    path->fill_is_empty = FALSE;

    return _cairo_path_fixed_add (path, CAIRO_PATH_OP_CURVE_TO, point, 3);
}

cairo_status_t
_cairo_path_fixed_rel_curve_to (cairo_path_fixed_t *path,
				cairo_fixed_t dx0, cairo_fixed_t dy0,
				cairo_fixed_t dx1, cairo_fixed_t dy1,
				cairo_fixed_t dx2, cairo_fixed_t dy2)
{
    if (unlikely (! path->has_current_point))
	return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);

    return _cairo_path_fixed_curve_to (path,
				       path->current_point.x + dx0,
				       path->current_point.y + dy0,

				       path->current_point.x + dx1,
				       path->current_point.y + dy1,

				       path->current_point.x + dx2,
				       path->current_point.y + dy2);
}

cairo_status_t
_cairo_path_fixed_close_path (cairo_path_fixed_t *path)
{
    cairo_status_t status;

    if (! path->has_current_point)
	return CAIRO_STATUS_SUCCESS;

    /*
     * Add a line_to, to compute flags and solve any degeneracy.
     * It will be removed later (if it was actually added).
     */
    status = _cairo_path_fixed_line_to (path,
					path->last_move_point.x,
					path->last_move_point.y);
    if (unlikely (status))
	return status;

    /*
     * If the command used to close the path is a line_to, drop it.
     * We must check that last command is actually a line_to,
     * because the path could have been closed with a curve_to (and
     * the previous line_to not added as it would be degenerate).
     */
    if (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO)
	    _cairo_path_fixed_drop_line_to (path);

    path->needs_move_to = TRUE; /* After close_path, add an implicit move_to */

    return _cairo_path_fixed_add (path, CAIRO_PATH_OP_CLOSE_PATH, NULL, 0);
}

cairo_bool_t
_cairo_path_fixed_get_current_point (cairo_path_fixed_t *path,
				     cairo_fixed_t	*x,
				     cairo_fixed_t	*y)
{
    if (! path->has_current_point)
	return FALSE;

    *x = path->current_point.x;
    *y = path->current_point.y;

    return TRUE;
}

static cairo_status_t
_cairo_path_fixed_add (cairo_path_fixed_t   *path,
		       cairo_path_op_t	     op,
		       const cairo_point_t  *points,
		       int		     num_points)
{
    cairo_path_buf_t *buf = cairo_path_tail (path);

    if (buf->num_ops + 1 > buf->size_ops ||
	buf->num_points + num_points > buf->size_points)
    {
	buf = _cairo_path_buf_create (buf->num_ops * 2, buf->num_points * 2);
	if (unlikely (buf == NULL))
	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);

	_cairo_path_fixed_add_buf (path, buf);
    }

    if (WATCH_PATH) {
	const char *op_str[] = {
	    "move-to",
	    "line-to",
	    "curve-to",
	    "close-path",
	};
	char buf[1024];
	int len = 0;
	int i;

	len += snprintf (buf + len, sizeof (buf), "[");
	for (i = 0; i < num_points; i++) {
	    if (i != 0)
		len += snprintf (buf + len, sizeof (buf), " ");
	    len += snprintf (buf + len, sizeof (buf), "(%f, %f)",
			     _cairo_fixed_to_double (points[i].x),
			     _cairo_fixed_to_double (points[i].y));
	}
	len += snprintf (buf + len, sizeof (buf), "]");

#define STRINGIFYFLAG(x)  (path->x ? #x " " : "")
	fprintf (stderr,
		 "_cairo_path_fixed_add (%s, %s) [%s%s%s%s%s%s%s%s]\n",
		 op_str[(int) op], buf,
		 STRINGIFYFLAG(has_current_point),
		 STRINGIFYFLAG(needs_move_to),
		 STRINGIFYFLAG(has_extents),
		 STRINGIFYFLAG(has_curve_to),
		 STRINGIFYFLAG(stroke_is_rectilinear),
		 STRINGIFYFLAG(fill_is_rectilinear),
		 STRINGIFYFLAG(fill_is_empty),
		 STRINGIFYFLAG(fill_maybe_region)
		 );
#undef STRINGIFYFLAG
    }

    _cairo_path_buf_add_op (buf, op);
    _cairo_path_buf_add_points (buf, points, num_points);

    return CAIRO_STATUS_SUCCESS;
}

static void
_cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
			   cairo_path_buf_t   *buf)
{
    cairo_list_add_tail (&buf->link, &cairo_path_head (path)->link);
}

COMPILE_TIME_ASSERT (sizeof (cairo_path_op_t) == 1);
static cairo_path_buf_t *
_cairo_path_buf_create (int size_ops, int size_points)
{
    cairo_path_buf_t *buf;

    /* adjust size_ops to ensure that buf->points is naturally aligned */
    size_ops += sizeof (double) - ((sizeof (cairo_path_buf_t) + size_ops) % sizeof (double));
    buf = _cairo_malloc_ab_plus_c (size_points, sizeof (cairo_point_t), size_ops + sizeof (cairo_path_buf_t));
    if (buf) {
	buf->num_ops = 0;
	buf->num_points = 0;
	buf->size_ops = size_ops;
	buf->size_points = size_points;

	buf->op = (cairo_path_op_t *) (buf + 1);
	buf->points = (cairo_point_t *) (buf->op + size_ops);
    }

    return buf;
}

static void
_cairo_path_buf_destroy (cairo_path_buf_t *buf)
{
    free (buf);
}

static void
_cairo_path_buf_add_op (cairo_path_buf_t *buf,
			cairo_path_op_t	  op)
{
    buf->op[buf->num_ops++] = op;
}

static void
_cairo_path_buf_add_points (cairo_path_buf_t       *buf,
			    const cairo_point_t    *points,
			    int		            num_points)
{
    if (num_points == 0)
	return;

    memcpy (buf->points + buf->num_points,
	    points,
	    sizeof (points[0]) * num_points);
    buf->num_points += num_points;
}

cairo_status_t
_cairo_path_fixed_interpret (const cairo_path_fixed_t		*path,
			     cairo_path_fixed_move_to_func_t	*move_to,
			     cairo_path_fixed_line_to_func_t	*line_to,
			     cairo_path_fixed_curve_to_func_t	*curve_to,
			     cairo_path_fixed_close_path_func_t	*close_path,
			     void				*closure)
{
    const cairo_path_buf_t *buf;
    cairo_status_t status;

    cairo_path_foreach_buf_start (buf, path) {
	const cairo_point_t *points = buf->points;
	unsigned int i;

	for (i = 0; i < buf->num_ops; i++) {
	    switch (buf->op[i]) {
	    case CAIRO_PATH_OP_MOVE_TO:
		status = (*move_to) (closure, &points[0]);
		points += 1;
		break;
	    case CAIRO_PATH_OP_LINE_TO:
		status = (*line_to) (closure, &points[0]);
		points += 1;
		break;
	    case CAIRO_PATH_OP_CURVE_TO:
		status = (*curve_to) (closure, &points[0], &points[1], &points[2]);
		points += 3;
		break;
	    default:
		ASSERT_NOT_REACHED;
	    case CAIRO_PATH_OP_CLOSE_PATH:
		status = (*close_path) (closure);
		break;
	    }

	    if (unlikely (status))
		return status;
	}
    } cairo_path_foreach_buf_end (buf, path);

    return CAIRO_STATUS_SUCCESS;
}

typedef struct _cairo_path_fixed_append_closure {
    cairo_point_t	    offset;
    cairo_path_fixed_t	    *path;
} cairo_path_fixed_append_closure_t;

static cairo_status_t
_append_move_to (void		 *abstract_closure,
		 const cairo_point_t  *point)
{
    cairo_path_fixed_append_closure_t	*closure = abstract_closure;

    return _cairo_path_fixed_move_to (closure->path,
				      point->x + closure->offset.x,
				      point->y + closure->offset.y);
}

static cairo_status_t
_append_line_to (void		 *abstract_closure,
		 const cairo_point_t *point)
{
    cairo_path_fixed_append_closure_t	*closure = abstract_closure;

    return _cairo_path_fixed_line_to (closure->path,
				      point->x + closure->offset.x,
				      point->y + closure->offset.y);
}

static cairo_status_t
_append_curve_to (void	  *abstract_closure,
		  const cairo_point_t *p0,
		  const cairo_point_t *p1,
		  const cairo_point_t *p2)
{
    cairo_path_fixed_append_closure_t	*closure = abstract_closure;

    return _cairo_path_fixed_curve_to (closure->path,
				       p0->x + closure->offset.x,
				       p0->y + closure->offset.y,
				       p1->x + closure->offset.x,
				       p1->y + closure->offset.y,
				       p2->x + closure->offset.x,
				       p2->y + closure->offset.y);
}

static cairo_status_t
_append_close_path (void *abstract_closure)
{
    cairo_path_fixed_append_closure_t	*closure = abstract_closure;

    return _cairo_path_fixed_close_path (closure->path);
}

cairo_status_t
_cairo_path_fixed_append (cairo_path_fixed_t		    *path,
			  const cairo_path_fixed_t	    *other,
			  cairo_fixed_t			     tx,
			  cairo_fixed_t			     ty)
{
    cairo_path_fixed_append_closure_t closure;

    closure.path = path;
    closure.offset.x = tx;
    closure.offset.y = ty;

    return _cairo_path_fixed_interpret (other,
					_append_move_to,
					_append_line_to,
					_append_curve_to,
					_append_close_path,
					&closure);
}

static void
_cairo_path_fixed_offset_and_scale (cairo_path_fixed_t *path,
				    cairo_fixed_t offx,
				    cairo_fixed_t offy,
				    cairo_fixed_t scalex,
				    cairo_fixed_t scaley)
{
    cairo_path_buf_t *buf;
    unsigned int i;

    if (scalex == CAIRO_FIXED_ONE && scaley == CAIRO_FIXED_ONE) {
	_cairo_path_fixed_translate (path, offx, offy);
	return;
    }

    path->last_move_point.x = _cairo_fixed_mul (scalex, path->last_move_point.x) + offx;
    path->last_move_point.y = _cairo_fixed_mul (scaley, path->last_move_point.y) + offy;
    path->current_point.x   = _cairo_fixed_mul (scalex, path->current_point.x) + offx;
    path->current_point.y   = _cairo_fixed_mul (scaley, path->current_point.y) + offy;

    path->fill_maybe_region = TRUE;

    cairo_path_foreach_buf_start (buf, path) {
	 for (i = 0; i < buf->num_points; i++) {
	     if (scalex != CAIRO_FIXED_ONE)
		 buf->points[i].x = _cairo_fixed_mul (buf->points[i].x, scalex);
	     buf->points[i].x += offx;

	     if (scaley != CAIRO_FIXED_ONE)
		 buf->points[i].y = _cairo_fixed_mul (buf->points[i].y, scaley);
	     buf->points[i].y += offy;

	    if (path->fill_maybe_region) {
		path->fill_maybe_region = _cairo_fixed_is_integer (buf->points[i].x) &&
					  _cairo_fixed_is_integer (buf->points[i].y);
	    }
	 }
    } cairo_path_foreach_buf_end (buf, path);

    path->fill_maybe_region &= path->fill_is_rectilinear;

    path->extents.p1.x = _cairo_fixed_mul (scalex, path->extents.p1.x) + offx;
    path->extents.p2.x = _cairo_fixed_mul (scalex, path->extents.p2.x) + offx;
    path->extents.p1.y = _cairo_fixed_mul (scaley, path->extents.p1.y) + offy;
    path->extents.p2.y = _cairo_fixed_mul (scaley, path->extents.p2.y) + offy;
}

void
_cairo_path_fixed_translate (cairo_path_fixed_t *path,
			     cairo_fixed_t offx,
			     cairo_fixed_t offy)
{
    cairo_path_buf_t *buf;
    unsigned int i;

    if (offx == 0 && offy == 0)
	return;

    path->last_move_point.x += offx;
    path->last_move_point.y += offy;
    path->current_point.x += offx;
    path->current_point.y += offy;

    path->fill_maybe_region = TRUE;

    cairo_path_foreach_buf_start (buf, path) {
	for (i = 0; i < buf->num_points; i++) {
	    buf->points[i].x += offx;
	    buf->points[i].y += offy;

	    if (path->fill_maybe_region) {
		path->fill_maybe_region = _cairo_fixed_is_integer (buf->points[i].x) &&
					  _cairo_fixed_is_integer (buf->points[i].y);
	    }
	 }
    } cairo_path_foreach_buf_end (buf, path);

    path->fill_maybe_region &= path->fill_is_rectilinear;

    path->extents.p1.x += offx;
    path->extents.p1.y += offy;
    path->extents.p2.x += offx;
    path->extents.p2.y += offy;
}


static inline void
_cairo_path_fixed_transform_point (cairo_point_t *p,
				   const cairo_matrix_t *matrix)
{
    double dx, dy;

    dx = _cairo_fixed_to_double (p->x);
    dy = _cairo_fixed_to_double (p->y);
    cairo_matrix_transform_point (matrix, &dx, &dy);
    p->x = _cairo_fixed_from_double (dx);
    p->y = _cairo_fixed_from_double (dy);
}

/**
 * _cairo_path_fixed_transform:
 * @path: a #cairo_path_fixed_t to be transformed
 * @matrix: a #cairo_matrix_t
 *
 * Transform the fixed-point path according to the given matrix.
 * There is a fast path for the case where @matrix has no rotation
 * or shear.
 **/
void
_cairo_path_fixed_transform (cairo_path_fixed_t	*path,
			     const cairo_matrix_t     *matrix)
{
    cairo_box_t extents;
    cairo_point_t point;
    cairo_path_buf_t *buf;
    unsigned int i;

    if (matrix->yx == 0.0 && matrix->xy == 0.0) {
	/* Fast path for the common case of scale+transform */
	_cairo_path_fixed_offset_and_scale (path,
					    _cairo_fixed_from_double (matrix->x0),
					    _cairo_fixed_from_double (matrix->y0),
					    _cairo_fixed_from_double (matrix->xx),
					    _cairo_fixed_from_double (matrix->yy));
	return;
    }

    _cairo_path_fixed_transform_point (&path->last_move_point, matrix);
    _cairo_path_fixed_transform_point (&path->current_point, matrix);

    buf = cairo_path_head (path);
    if (buf->num_points == 0)
	return;

    extents = path->extents;
    point = buf->points[0];
    _cairo_path_fixed_transform_point (&point, matrix);
    _cairo_box_set (&path->extents, &point, &point);

    cairo_path_foreach_buf_start (buf, path) {
	for (i = 0; i < buf->num_points; i++) {
	    _cairo_path_fixed_transform_point (&buf->points[i], matrix);
	    _cairo_box_add_point (&path->extents, &buf->points[i]);
	}
    } cairo_path_foreach_buf_end (buf, path);

    if (path->has_curve_to) {
	cairo_bool_t is_tight;

	_cairo_matrix_transform_bounding_box_fixed (matrix, &extents, &is_tight);
	if (!is_tight) {
	    cairo_bool_t has_extents;

	    has_extents = _cairo_path_bounder_extents (path, &extents);
	    assert (has_extents);
	}
	path->extents = extents;
    }

    /* flags might become more strict than needed */
    path->stroke_is_rectilinear = FALSE;
    path->fill_is_rectilinear = FALSE;
    path->fill_is_empty = FALSE;
    path->fill_maybe_region = FALSE;
}

/* Closure for path flattening */
typedef struct cairo_path_flattener {
    double tolerance;
    cairo_point_t current_point;
    cairo_path_fixed_move_to_func_t	*move_to;
    cairo_path_fixed_line_to_func_t	*line_to;
    cairo_path_fixed_close_path_func_t	*close_path;
    void *closure;
} cpf_t;

static cairo_status_t
_cpf_move_to (void *closure,
	      const cairo_point_t *point)
{
    cpf_t *cpf = closure;

    cpf->current_point = *point;

    return cpf->move_to (cpf->closure, point);
}

static cairo_status_t
_cpf_line_to (void *closure,
	      const cairo_point_t *point)
{
    cpf_t *cpf = closure;

    cpf->current_point = *point;

    return cpf->line_to (cpf->closure, point);
}

static cairo_status_t
_cpf_curve_to (void		*closure,
	       const cairo_point_t	*p1,
	       const cairo_point_t	*p2,
	       const cairo_point_t	*p3)
{
    cpf_t *cpf = closure;
    cairo_spline_t spline;

    cairo_point_t *p0 = &cpf->current_point;

    if (! _cairo_spline_init (&spline,
			      (cairo_spline_add_point_func_t)cpf->line_to,
			      cpf->closure,
			      p0, p1, p2, p3))
    {
	return _cpf_line_to (closure, p3);
    }

    cpf->current_point = *p3;

    return _cairo_spline_decompose (&spline, cpf->tolerance);
}

static cairo_status_t
_cpf_close_path (void *closure)
{
    cpf_t *cpf = closure;

    return cpf->close_path (cpf->closure);
}

cairo_status_t
_cairo_path_fixed_interpret_flat (const cairo_path_fixed_t		*path,
				  cairo_path_fixed_move_to_func_t	*move_to,
				  cairo_path_fixed_line_to_func_t	*line_to,
				  cairo_path_fixed_close_path_func_t	*close_path,
				  void					*closure,
				  double				tolerance)
{
    cpf_t flattener;

    if (! path->has_curve_to) {
	return _cairo_path_fixed_interpret (path,
					    move_to,
					    line_to,
					    NULL,
					    close_path,
					    closure);
    }

    flattener.tolerance = tolerance;
    flattener.move_to = move_to;
    flattener.line_to = line_to;
    flattener.close_path = close_path;
    flattener.closure = closure;
    return _cairo_path_fixed_interpret (path,
					_cpf_move_to,
					_cpf_line_to,
					_cpf_curve_to,
					_cpf_close_path,
					&flattener);
}

static inline void
_canonical_box (cairo_box_t *box,
		const cairo_point_t *p1,
		const cairo_point_t *p2)
{
    if (p1->x <= p2->x) {
	box->p1.x = p1->x;
	box->p2.x = p2->x;
    } else {
	box->p1.x = p2->x;
	box->p2.x = p1->x;
    }

    if (p1->y <= p2->y) {
	box->p1.y = p1->y;
	box->p2.y = p2->y;
    } else {
	box->p1.y = p2->y;
	box->p2.y = p1->y;
    }
}

/*
 * Check whether the given path contains a single rectangle.
 */
cairo_bool_t
_cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
			  cairo_box_t *box)
{
    const cairo_path_buf_t *buf = cairo_path_head (path);

    if (! path->fill_is_rectilinear)
	return FALSE;

    /* Do we have the right number of ops? */
    if (buf->num_ops < 4 || buf->num_ops > 6)
	return FALSE;

    /* Check whether the ops are those that would be used for a rectangle */
    if (buf->op[0] != CAIRO_PATH_OP_MOVE_TO ||
	buf->op[1] != CAIRO_PATH_OP_LINE_TO ||
	buf->op[2] != CAIRO_PATH_OP_LINE_TO ||
	buf->op[3] != CAIRO_PATH_OP_LINE_TO)
    {
	return FALSE;
    }

    /* we accept an implicit close for filled paths */
    if (buf->num_ops > 4) {
	/* Now, there are choices. The rectangle might end with a LINE_TO
	 * (to the original point), but this isn't required. If it
	 * doesn't, then it must end with a CLOSE_PATH. */
	if (buf->op[4] == CAIRO_PATH_OP_LINE_TO) {
	    if (buf->points[4].x != buf->points[0].x ||
		buf->points[4].y != buf->points[0].y)
		return FALSE;
	} else if (buf->op[4] != CAIRO_PATH_OP_CLOSE_PATH) {
	    return FALSE;
	}

	if (buf->num_ops == 6) {
	    /* A trailing CLOSE_PATH or MOVE_TO is ok */
	    if (buf->op[5] != CAIRO_PATH_OP_MOVE_TO &&
		buf->op[5] != CAIRO_PATH_OP_CLOSE_PATH)
		return FALSE;
	}
    }

    /* Ok, we may have a box, if the points line up */
    if (buf->points[0].y == buf->points[1].y &&
	buf->points[1].x == buf->points[2].x &&
	buf->points[2].y == buf->points[3].y &&
	buf->points[3].x == buf->points[0].x)
    {
	_canonical_box (box, &buf->points[0], &buf->points[2]);
	return TRUE;
    }

    if (buf->points[0].x == buf->points[1].x &&
	buf->points[1].y == buf->points[2].y &&
	buf->points[2].x == buf->points[3].x &&
	buf->points[3].y == buf->points[0].y)
    {
	_canonical_box (box, &buf->points[0], &buf->points[2]);
	return TRUE;
    }

    return FALSE;
}

cairo_bool_t
_cairo_path_fixed_is_stroke_box (const cairo_path_fixed_t *path,
				 cairo_box_t *box)
{
    const cairo_path_buf_t *buf = cairo_path_head (path);

    if (! path->fill_is_rectilinear)
	return FALSE;

    /* Do we have the right number of ops? */
    if (buf->num_ops != 5)
	return FALSE;

    /* Check whether the ops are those that would be used for a rectangle */
    if (buf->op[0] != CAIRO_PATH_OP_MOVE_TO ||
	buf->op[1] != CAIRO_PATH_OP_LINE_TO ||
	buf->op[2] != CAIRO_PATH_OP_LINE_TO ||
	buf->op[3] != CAIRO_PATH_OP_LINE_TO ||
	buf->op[4] != CAIRO_PATH_OP_CLOSE_PATH)
    {
	return FALSE;
    }

    /* Ok, we may have a box, if the points line up */
    if (buf->points[0].y == buf->points[1].y &&
	buf->points[1].x == buf->points[2].x &&
	buf->points[2].y == buf->points[3].y &&
	buf->points[3].x == buf->points[0].x)
    {
	_canonical_box (box, &buf->points[0], &buf->points[2]);
	return TRUE;
    }

    if (buf->points[0].x == buf->points[1].x &&
	buf->points[1].y == buf->points[2].y &&
	buf->points[2].x == buf->points[3].x &&
	buf->points[3].y == buf->points[0].y)
    {
	_canonical_box (box, &buf->points[0], &buf->points[2]);
	return TRUE;
    }

    return FALSE;
}

/*
 * Check whether the given path contains a single rectangle
 * that is logically equivalent to:
 * <informalexample><programlisting>
 *   cairo_move_to (cr, x, y);
 *   cairo_rel_line_to (cr, width, 0);
 *   cairo_rel_line_to (cr, 0, height);
 *   cairo_rel_line_to (cr, -width, 0);
 *   cairo_close_path (cr);
 * </programlisting></informalexample>
 */
cairo_bool_t
_cairo_path_fixed_is_rectangle (const cairo_path_fixed_t *path,
				cairo_box_t        *box)
{
    const cairo_path_buf_t *buf;

    if (! _cairo_path_fixed_is_box (path, box))
	return FALSE;

    /* This check is valid because the current implementation of
     * _cairo_path_fixed_is_box () only accepts rectangles like:
     * move,line,line,line[,line|close[,close|move]]. */
    buf = cairo_path_head (path);
    if (buf->num_ops > 4)
	return TRUE;

    return FALSE;
}

void
_cairo_path_fixed_iter_init (cairo_path_fixed_iter_t *iter,
			     const cairo_path_fixed_t *path)
{
    iter->first = iter->buf = cairo_path_head (path);
    iter->n_op = 0;
    iter->n_point = 0;
}

static cairo_bool_t
_cairo_path_fixed_iter_next_op (cairo_path_fixed_iter_t *iter)
{
    if (++iter->n_op >= iter->buf->num_ops) {
	iter->buf = cairo_path_buf_next (iter->buf);
	if (iter->buf == iter->first) {
	    iter->buf = NULL;
	    return FALSE;
	}

	iter->n_op = 0;
	iter->n_point = 0;
    }

    return TRUE;
}

cairo_bool_t
_cairo_path_fixed_iter_is_fill_box (cairo_path_fixed_iter_t *_iter,
				    cairo_box_t *box)
{
    cairo_point_t points[5];
    cairo_path_fixed_iter_t iter;

    if (_iter->buf == NULL)
	return FALSE;

    iter = *_iter;

    if (iter.n_op == iter.buf->num_ops && ! _cairo_path_fixed_iter_next_op (&iter))
	return FALSE;

    /* Check whether the ops are those that would be used for a rectangle */
    if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_MOVE_TO)
	return FALSE;
    points[0] = iter.buf->points[iter.n_point++];
    if (! _cairo_path_fixed_iter_next_op (&iter))
	return FALSE;

    if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
	return FALSE;
    points[1] = iter.buf->points[iter.n_point++];
    if (! _cairo_path_fixed_iter_next_op (&iter))
	return FALSE;

    /* a horizontal/vertical closed line is also a degenerate rectangle */
    switch (iter.buf->op[iter.n_op]) {
    case CAIRO_PATH_OP_CLOSE_PATH:
	_cairo_path_fixed_iter_next_op (&iter);
    case CAIRO_PATH_OP_MOVE_TO: /* implicit close */
	box->p1 = box->p2 = points[0];
	*_iter = iter;
	return TRUE;
    default:
	return FALSE;
    case CAIRO_PATH_OP_LINE_TO:
	break;
    }

    points[2] = iter.buf->points[iter.n_point++];
    if (! _cairo_path_fixed_iter_next_op (&iter))
	return FALSE;

    if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
	return FALSE;
    points[3] = iter.buf->points[iter.n_point++];

    /* Now, there are choices. The rectangle might end with a LINE_TO
     * (to the original point), but this isn't required. If it
     * doesn't, then it must end with a CLOSE_PATH (which may be implicit). */
    if (! _cairo_path_fixed_iter_next_op (&iter)) {
	/* implicit close due to fill */
    } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_LINE_TO) {
	points[4] = iter.buf->points[iter.n_point++];
	if (points[4].x != points[0].x || points[4].y != points[0].y)
	    return FALSE;
	_cairo_path_fixed_iter_next_op (&iter);
    } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_CLOSE_PATH) {
	_cairo_path_fixed_iter_next_op (&iter);
    } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_MOVE_TO) {
	/* implicit close-path due to new-sub-path */
    } else {
	return FALSE;
    }

    /* Ok, we may have a box, if the points line up */
    if (points[0].y == points[1].y &&
	points[1].x == points[2].x &&
	points[2].y == points[3].y &&
	points[3].x == points[0].x)
    {
	box->p1 = points[0];
	box->p2 = points[2];
	*_iter = iter;
	return TRUE;
    }

    if (points[0].x == points[1].x &&
	points[1].y == points[2].y &&
	points[2].x == points[3].x &&
	points[3].y == points[0].y)
    {
	box->p1 = points[1];
	box->p2 = points[3];
	*_iter = iter;
	return TRUE;
    }

    return FALSE;
}

cairo_bool_t
_cairo_path_fixed_iter_at_end (const cairo_path_fixed_iter_t *iter)
{
    if (iter->buf == NULL)
	return TRUE;

    return iter->n_op == iter->buf->num_ops;
}