Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
  2. /* cairo - a vector graphics library with display and print output
  3.  *
  4.  * Copyright © 2002 University of Southern California
  5.  * Copyright © 2005 Red Hat, Inc.
  6.   *
  7.  * This library is free software; you can redistribute it and/or
  8.  * modify it either under the terms of the GNU Lesser General Public
  9.  * License version 2.1 as published by the Free Software Foundation
  10.  * (the "LGPL") or, at your option, under the terms of the Mozilla
  11.  * Public License Version 1.1 (the "MPL"). If you do not alter this
  12.  * notice, a recipient may use your version of this file under either
  13.  * the MPL or the LGPL.
  14.  *
  15.  * You should have received a copy of the LGPL along with this library
  16.  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  17.  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  18.  * You should have received a copy of the MPL along with this library
  19.  * in the file COPYING-MPL-1.1
  20.  *
  21.  * The contents of this file are subject to the Mozilla Public License
  22.  * Version 1.1 (the "License"); you may not use this file except in
  23.  * compliance with the License. You may obtain a copy of the License at
  24.  * http://www.mozilla.org/MPL/
  25.  *
  26.  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  27.  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  28.  * the specific language governing rights and limitations.
  29.  *
  30.  * The Original Code is the cairo graphics library.
  31.  *
  32.  * The Initial Developer of the Original Code is University of Southern
  33.  * California.
  34.  *
  35.  * Contributor(s):
  36.  *      Carl D. Worth <cworth@cworth.org>
  37.  */
  38.  
  39. #include "cairoint.h"
  40.  
  41. #include "cairo-error-private.h"
  42. #include "cairo-path-fixed-private.h"
  43. #include "cairo-slope-private.h"
  44.  
  45. static cairo_status_t
  46. _cairo_path_fixed_add (cairo_path_fixed_t  *path,
  47.                        cairo_path_op_t      op,
  48.                        const cairo_point_t *points,
  49.                        int                  num_points);
  50.  
  51. static void
  52. _cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
  53.                            cairo_path_buf_t   *buf);
  54.  
  55. static cairo_path_buf_t *
  56. _cairo_path_buf_create (int size_ops, int size_points);
  57.  
  58. static void
  59. _cairo_path_buf_destroy (cairo_path_buf_t *buf);
  60.  
  61. static void
  62. _cairo_path_buf_add_op (cairo_path_buf_t *buf,
  63.                         cairo_path_op_t   op);
  64.  
  65. static void
  66. _cairo_path_buf_add_points (cairo_path_buf_t       *buf,
  67.                             const cairo_point_t    *points,
  68.                             int                     num_points);
  69.  
  70. #define cairo_path_head(path__) (&(path__)->buf.base)
  71. #define cairo_path_tail(path__) cairo_path_buf_prev (cairo_path_head (path__))
  72.  
  73. #define cairo_path_buf_next(pos__) \
  74.     cairo_list_entry ((pos__)->link.next, cairo_path_buf_t, link)
  75. #define cairo_path_buf_prev(pos__) \
  76.     cairo_list_entry ((pos__)->link.prev, cairo_path_buf_t, link)
  77.  
  78. #define cairo_path_foreach_buf_start(pos__, path__) \
  79.     pos__ = cairo_path_head (path__); do
  80. #define cairo_path_foreach_buf_end(pos__, path__) \
  81.     while ((pos__ = cairo_path_buf_next (pos__)) !=  cairo_path_head (path__))
  82.  
  83. void
  84. _cairo_path_fixed_init (cairo_path_fixed_t *path)
  85. {
  86.     VG (VALGRIND_MAKE_MEM_UNDEFINED (path, sizeof (cairo_path_fixed_t)));
  87.  
  88.     cairo_list_init (&path->buf.base.link);
  89.  
  90.     path->buf.base.num_ops = 0;
  91.     path->buf.base.num_points = 0;
  92.     path->buf.base.size_ops = ARRAY_LENGTH (path->buf.op);
  93.     path->buf.base.size_points = ARRAY_LENGTH (path->buf.points);
  94.     path->buf.base.op = path->buf.op;
  95.     path->buf.base.points = path->buf.points;
  96.  
  97.     path->current_point.x = 0;
  98.     path->current_point.y = 0;
  99.     path->last_move_point = path->current_point;
  100.     path->has_last_move_point = FALSE;
  101.     path->has_current_point = FALSE;
  102.     path->has_curve_to = FALSE;
  103.     path->is_rectilinear = TRUE;
  104.     path->maybe_fill_region = TRUE;
  105.     path->is_empty_fill = TRUE;
  106.  
  107.     path->extents.p1.x = path->extents.p1.y = INT_MAX;
  108.     path->extents.p2.x = path->extents.p2.y = INT_MIN;
  109. }
  110.  
  111. cairo_status_t
  112. _cairo_path_fixed_init_copy (cairo_path_fixed_t *path,
  113.                              const cairo_path_fixed_t *other)
  114. {
  115.     cairo_path_buf_t *buf, *other_buf;
  116.     unsigned int num_points, num_ops;
  117.  
  118.     VG (VALGRIND_MAKE_MEM_UNDEFINED (path, sizeof (cairo_path_fixed_t)));
  119.  
  120.     cairo_list_init (&path->buf.base.link);
  121.  
  122.     path->buf.base.op = path->buf.op;
  123.     path->buf.base.points = path->buf.points;
  124.     path->buf.base.size_ops = ARRAY_LENGTH (path->buf.op);
  125.     path->buf.base.size_points = ARRAY_LENGTH (path->buf.points);
  126.  
  127.     path->current_point = other->current_point;
  128.     path->last_move_point = other->last_move_point;
  129.     path->has_last_move_point = other->has_last_move_point;
  130.     path->has_current_point = other->has_current_point;
  131.     path->has_curve_to = other->has_curve_to;
  132.     path->is_rectilinear = other->is_rectilinear;
  133.     path->maybe_fill_region = other->maybe_fill_region;
  134.     path->is_empty_fill = other->is_empty_fill;
  135.  
  136.     path->extents = other->extents;
  137.  
  138.     path->buf.base.num_ops = other->buf.base.num_ops;
  139.     path->buf.base.num_points = other->buf.base.num_points;
  140.     memcpy (path->buf.op, other->buf.base.op,
  141.             other->buf.base.num_ops * sizeof (other->buf.op[0]));
  142.     memcpy (path->buf.points, other->buf.points,
  143.             other->buf.base.num_points * sizeof (other->buf.points[0]));
  144.  
  145.     num_points = num_ops = 0;
  146.     for (other_buf = cairo_path_buf_next (cairo_path_head (other));
  147.          other_buf != cairo_path_head (other);
  148.          other_buf = cairo_path_buf_next (other_buf))
  149.     {
  150.         num_ops    += other_buf->num_ops;
  151.         num_points += other_buf->num_points;
  152.     }
  153.  
  154.     if (num_ops) {
  155.         buf = _cairo_path_buf_create (num_ops, num_points);
  156.         if (unlikely (buf == NULL)) {
  157.             _cairo_path_fixed_fini (path);
  158.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  159.         }
  160.  
  161.         for (other_buf = cairo_path_buf_next (cairo_path_head (other));
  162.              other_buf != cairo_path_head (other);
  163.              other_buf = cairo_path_buf_next (other_buf))
  164.         {
  165.             memcpy (buf->op + buf->num_ops, other_buf->op,
  166.                     other_buf->num_ops * sizeof (buf->op[0]));
  167.             buf->num_ops += other_buf->num_ops;
  168.  
  169.             memcpy (buf->points + buf->num_points, other_buf->points,
  170.                     other_buf->num_points * sizeof (buf->points[0]));
  171.             buf->num_points += other_buf->num_points;
  172.         }
  173.  
  174.         _cairo_path_fixed_add_buf (path, buf);
  175.     }
  176.  
  177.     return CAIRO_STATUS_SUCCESS;
  178. }
  179.  
  180. unsigned long
  181. _cairo_path_fixed_hash (const cairo_path_fixed_t *path)
  182. {
  183.     unsigned long hash = _CAIRO_HASH_INIT_VALUE;
  184.     const cairo_path_buf_t *buf;
  185.     int num_points, num_ops;
  186.  
  187.     hash = _cairo_hash_bytes (hash, &path->extents, sizeof (path->extents));
  188.  
  189.     num_ops = num_points = 0;
  190.     cairo_path_foreach_buf_start (buf, path) {
  191.         hash = _cairo_hash_bytes (hash, buf->op,
  192.                                   buf->num_ops * sizeof (buf->op[0]));
  193.         hash = _cairo_hash_bytes (hash, buf->points,
  194.                                   buf->num_points * sizeof (buf->points[0]));
  195.  
  196.         num_ops    += buf->num_ops;
  197.         num_points += buf->num_points;
  198.     } cairo_path_foreach_buf_end (buf, path);
  199.  
  200.     hash = _cairo_hash_bytes (hash, &num_ops, sizeof (num_ops));
  201.     hash = _cairo_hash_bytes (hash, &num_points, sizeof (num_points));
  202.  
  203.     return hash;
  204. }
  205.  
  206. unsigned long
  207. _cairo_path_fixed_size (const cairo_path_fixed_t *path)
  208. {
  209.     const cairo_path_buf_t *buf;
  210.     int num_points, num_ops;
  211.  
  212.     num_ops = num_points = 0;
  213.     cairo_path_foreach_buf_start (buf, path) {
  214.         num_ops    += buf->num_ops;
  215.         num_points += buf->num_points;
  216.     } cairo_path_foreach_buf_end (buf, path);
  217.  
  218.     return num_ops * sizeof (buf->op[0]) +
  219.            num_points * sizeof (buf->points[0]);
  220. }
  221.  
  222. cairo_bool_t
  223. _cairo_path_fixed_equal (const cairo_path_fixed_t *a,
  224.                          const cairo_path_fixed_t *b)
  225. {
  226.     const cairo_path_buf_t *buf_a, *buf_b;
  227.     const cairo_path_op_t *ops_a, *ops_b;
  228.     const cairo_point_t *points_a, *points_b;
  229.     int num_points_a, num_ops_a;
  230.     int num_points_b, num_ops_b;
  231.  
  232.     if (a == b)
  233.         return TRUE;
  234.  
  235.     /* use the flags to quickly differentiate based on contents */
  236.     if (a->is_empty_fill != b->is_empty_fill ||
  237.         a->has_curve_to != b->has_curve_to ||
  238.         a->maybe_fill_region != b->maybe_fill_region ||
  239.         a->is_rectilinear != b->is_rectilinear)
  240.     {
  241.         return FALSE;
  242.     }
  243.  
  244.     if (a->extents.p1.x != b->extents.p1.x ||
  245.         a->extents.p1.y != b->extents.p1.y ||
  246.         a->extents.p2.x != b->extents.p2.x ||
  247.         a->extents.p2.y != b->extents.p2.y)
  248.     {
  249.         return FALSE;
  250.     }
  251.  
  252.     num_ops_a = num_points_a = 0;
  253.     cairo_path_foreach_buf_start (buf_a, a) {
  254.         num_ops_a    += buf_a->num_ops;
  255.         num_points_a += buf_a->num_points;
  256.     } cairo_path_foreach_buf_end (buf_a, a);
  257.  
  258.     num_ops_b = num_points_b = 0;
  259.     cairo_path_foreach_buf_start (buf_b, b) {
  260.         num_ops_b    += buf_b->num_ops;
  261.         num_points_b += buf_b->num_points;
  262.     } cairo_path_foreach_buf_end (buf_b, b);
  263.  
  264.     if (num_ops_a == 0 && num_ops_b == 0)
  265.         return TRUE;
  266.  
  267.     if (num_ops_a != num_ops_b || num_points_a != num_points_b)
  268.         return FALSE;
  269.  
  270.     buf_a = cairo_path_head (a);
  271.     num_points_a = buf_a->num_points;
  272.     num_ops_a = buf_a->num_ops;
  273.     ops_a = buf_a->op;
  274.     points_a = buf_a->points;
  275.  
  276.     buf_b = cairo_path_head (b);
  277.     num_points_b = buf_b->num_points;
  278.     num_ops_b = buf_b->num_ops;
  279.     ops_b = buf_b->op;
  280.     points_b = buf_b->points;
  281.  
  282.     while (TRUE) {
  283.         int num_ops = MIN (num_ops_a, num_ops_b);
  284.         int num_points = MIN (num_points_a, num_points_b);
  285.  
  286.         if (memcmp (ops_a, ops_b, num_ops * sizeof (cairo_path_op_t)))
  287.             return FALSE;
  288.         if (memcmp (points_a, points_b, num_points * sizeof (cairo_point_t)))
  289.             return FALSE;
  290.  
  291.         num_ops_a -= num_ops;
  292.         ops_a += num_ops;
  293.         num_points_a -= num_points;
  294.         points_a += num_points;
  295.         if (num_ops_a == 0 || num_points_a == 0) {
  296.             if (num_ops_a || num_points_a)
  297.                 return FALSE;
  298.  
  299.             buf_a = cairo_path_buf_next (buf_a);
  300.             if (buf_a == cairo_path_head (a))
  301.                 break;
  302.  
  303.             num_points_a = buf_a->num_points;
  304.             num_ops_a = buf_a->num_ops;
  305.             ops_a = buf_a->op;
  306.             points_a = buf_a->points;
  307.         }
  308.  
  309.         num_ops_b -= num_ops;
  310.         ops_b += num_ops;
  311.         num_points_b -= num_points;
  312.         points_b += num_points;
  313.         if (num_ops_b == 0 || num_points_b == 0) {
  314.             if (num_ops_b || num_points_b)
  315.                 return FALSE;
  316.  
  317.             buf_b = cairo_path_buf_next (buf_b);
  318.             if (buf_b == cairo_path_head (b))
  319.                 break;
  320.  
  321.             num_points_b = buf_b->num_points;
  322.             num_ops_b = buf_b->num_ops;
  323.             ops_b = buf_b->op;
  324.             points_b = buf_b->points;
  325.         }
  326.     }
  327.  
  328.     return TRUE;
  329. }
  330.  
  331. cairo_path_fixed_t *
  332. _cairo_path_fixed_create (void)
  333. {
  334.     cairo_path_fixed_t  *path;
  335.  
  336.     path = malloc (sizeof (cairo_path_fixed_t));
  337.     if (!path) {
  338.         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
  339.         return NULL;
  340.     }
  341.  
  342.     _cairo_path_fixed_init (path);
  343.     return path;
  344. }
  345.  
  346. void
  347. _cairo_path_fixed_fini (cairo_path_fixed_t *path)
  348. {
  349.     cairo_path_buf_t *buf;
  350.  
  351.     buf = cairo_path_buf_next (cairo_path_head (path));
  352.     while (buf != cairo_path_head (path)) {
  353.         cairo_path_buf_t *this = buf;
  354.         buf = cairo_path_buf_next (buf);
  355.         _cairo_path_buf_destroy (this);
  356.     }
  357.  
  358.     VG (VALGRIND_MAKE_MEM_NOACCESS (path, sizeof (cairo_path_fixed_t)));
  359. }
  360.  
  361. void
  362. _cairo_path_fixed_destroy (cairo_path_fixed_t *path)
  363. {
  364.     _cairo_path_fixed_fini (path);
  365.     free (path);
  366. }
  367.  
  368. static cairo_path_op_t
  369. _cairo_path_last_op (cairo_path_fixed_t *path)
  370. {
  371.     cairo_path_buf_t *buf;
  372.  
  373.     buf = cairo_path_tail (path);
  374.     if (buf->num_ops == 0)
  375.         return -1;
  376.  
  377.     return buf->op[buf->num_ops - 1];
  378. }
  379.  
  380. static inline void
  381. _cairo_path_fixed_extents_add (cairo_path_fixed_t *path,
  382.                                const cairo_point_t *point)
  383. {
  384.     if (point->x < path->extents.p1.x)
  385.         path->extents.p1.x = point->x;
  386.     if (point->y < path->extents.p1.y)
  387.         path->extents.p1.y = point->y;
  388.  
  389.     if (point->x > path->extents.p2.x)
  390.         path->extents.p2.x = point->x;
  391.     if (point->y > path->extents.p2.y)
  392.         path->extents.p2.y = point->y;
  393. }
  394.  
  395. cairo_status_t
  396. _cairo_path_fixed_move_to (cairo_path_fixed_t  *path,
  397.                            cairo_fixed_t        x,
  398.                            cairo_fixed_t        y)
  399. {
  400.     cairo_status_t status;
  401.     cairo_point_t point;
  402.  
  403.     point.x = x;
  404.     point.y = y;
  405.  
  406.     /* If the previous op was also a MOVE_TO, then just change its
  407.      * point rather than adding a new op. */
  408.     if (_cairo_path_last_op (path) == CAIRO_PATH_OP_MOVE_TO) {
  409.         cairo_path_buf_t *buf;
  410.  
  411.         buf = cairo_path_tail (path);
  412.         buf->points[buf->num_points - 1] = point;
  413.     } else {
  414.         status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_MOVE_TO, &point, 1);
  415.         if (unlikely (status))
  416.             return status;
  417.  
  418.         if (path->has_current_point && path->is_rectilinear) {
  419.             /* a move-to is first an implicit close */
  420.             path->is_rectilinear = path->current_point.x == path->last_move_point.x ||
  421.                                    path->current_point.y == path->last_move_point.y;
  422.             path->maybe_fill_region &= path->is_rectilinear;
  423.         }
  424.         if (path->maybe_fill_region) {
  425.             path->maybe_fill_region =
  426.                 _cairo_fixed_is_integer (path->last_move_point.x) &&
  427.                 _cairo_fixed_is_integer (path->last_move_point.y);
  428.         }
  429.     }
  430.  
  431.     path->current_point = point;
  432.     path->last_move_point = point;
  433.     path->has_last_move_point = TRUE;
  434.     path->has_current_point = TRUE;
  435.  
  436.     return CAIRO_STATUS_SUCCESS;
  437. }
  438.  
  439. void
  440. _cairo_path_fixed_new_sub_path (cairo_path_fixed_t *path)
  441. {
  442.     path->has_current_point = FALSE;
  443. }
  444.  
  445. cairo_status_t
  446. _cairo_path_fixed_rel_move_to (cairo_path_fixed_t *path,
  447.                                cairo_fixed_t       dx,
  448.                                cairo_fixed_t       dy)
  449. {
  450.     if (unlikely (! path->has_current_point))
  451.         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
  452.  
  453.     return _cairo_path_fixed_move_to (path,
  454.                                       path->current_point.x + dx,
  455.                                       path->current_point.y + dy);
  456.  
  457. }
  458.  
  459. cairo_status_t
  460. _cairo_path_fixed_line_to (cairo_path_fixed_t *path,
  461.                            cairo_fixed_t        x,
  462.                            cairo_fixed_t        y)
  463. {
  464.     cairo_status_t status;
  465.     cairo_point_t point;
  466.  
  467.     point.x = x;
  468.     point.y = y;
  469.  
  470.     /* When there is not yet a current point, the line_to operation
  471.      * becomes a move_to instead. Note: We have to do this by
  472.      * explicitly calling into _cairo_path_fixed_move_to to ensure
  473.      * that the last_move_point state is updated properly.
  474.      */
  475.     if (! path->has_current_point)
  476.         return _cairo_path_fixed_move_to (path, point.x, point.y);
  477.  
  478.     /* If the previous op was but the initial MOVE_TO and this segment
  479.      * is degenerate, then we can simply skip this point. Note that
  480.      * a move-to followed by a degenerate line-to is a valid path for
  481.      * stroking, but at all other times is simply a degenerate segment.
  482.      */
  483.     if (_cairo_path_last_op (path) != CAIRO_PATH_OP_MOVE_TO) {
  484.         if (x == path->current_point.x && y == path->current_point.y)
  485.             return CAIRO_STATUS_SUCCESS;
  486.     }
  487.  
  488.     /* If the previous op was also a LINE_TO with the same gradient,
  489.      * then just change its end-point rather than adding a new op.
  490.      */
  491.     if (_cairo_path_last_op (path) == CAIRO_PATH_OP_LINE_TO) {
  492.         cairo_path_buf_t *buf;
  493.         const cairo_point_t *p;
  494.  
  495.         buf = cairo_path_tail (path);
  496.         if (likely (buf->num_points >= 2)) {
  497.             p = &buf->points[buf->num_points-2];
  498.         } else {
  499.             cairo_path_buf_t *prev_buf = cairo_path_buf_prev (buf);
  500.             p = &prev_buf->points[prev_buf->num_points - (2 - buf->num_points)];
  501.         }
  502.  
  503.         if (p->x == path->current_point.x && p->y == path->current_point.y) {
  504.             /* previous line element was degenerate, replace */
  505.             buf->points[buf->num_points - 1] = point;
  506.             goto FLAGS;
  507.         } else {
  508.             cairo_slope_t prev, self;
  509.  
  510.             _cairo_slope_init (&prev, p, &path->current_point);
  511.             _cairo_slope_init (&self, &path->current_point, &point);
  512.             if (_cairo_slope_equal (&prev, &self) &&
  513.                 /* cannot trim anti-parallel segments whilst stroking */
  514.                 ! _cairo_slope_backwards (&prev, &self))
  515.             {
  516.                 buf->points[buf->num_points - 1] = point;
  517.                 goto FLAGS;
  518.             }
  519.         }
  520.     }
  521.  
  522.     status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_LINE_TO, &point, 1);
  523.     if (unlikely (status))
  524.         return status;
  525.  
  526.   FLAGS:
  527.     if (path->is_rectilinear) {
  528.         path->is_rectilinear = path->current_point.x == x ||
  529.                                path->current_point.y == y;
  530.         path->maybe_fill_region &= path->is_rectilinear;
  531.     }
  532.     if (path->maybe_fill_region) {
  533.         path->maybe_fill_region = _cairo_fixed_is_integer (x) &&
  534.                                   _cairo_fixed_is_integer (y);
  535.     }
  536.     if (path->is_empty_fill) {
  537.         path->is_empty_fill = path->current_point.x == x &&
  538.                               path->current_point.y == y;
  539.     }
  540.  
  541.     path->current_point = point;
  542.     if (path->has_last_move_point) {
  543.         _cairo_path_fixed_extents_add (path, &path->last_move_point);
  544.         path->has_last_move_point = FALSE;
  545.     }
  546.     _cairo_path_fixed_extents_add (path, &point);
  547.     return CAIRO_STATUS_SUCCESS;
  548. }
  549.  
  550. cairo_status_t
  551. _cairo_path_fixed_rel_line_to (cairo_path_fixed_t *path,
  552.                                cairo_fixed_t       dx,
  553.                                cairo_fixed_t       dy)
  554. {
  555.     if (unlikely (! path->has_current_point))
  556.         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
  557.  
  558.     return _cairo_path_fixed_line_to (path,
  559.                                       path->current_point.x + dx,
  560.                                       path->current_point.y + dy);
  561. }
  562.  
  563. cairo_status_t
  564. _cairo_path_fixed_curve_to (cairo_path_fixed_t  *path,
  565.                             cairo_fixed_t x0, cairo_fixed_t y0,
  566.                             cairo_fixed_t x1, cairo_fixed_t y1,
  567.                             cairo_fixed_t x2, cairo_fixed_t y2)
  568. {
  569.     cairo_status_t status;
  570.     cairo_point_t point[3];
  571.  
  572.     /* make sure subpaths are started properly */
  573.     if (! path->has_current_point) {
  574.         status = _cairo_path_fixed_move_to (path, x0, y0);
  575.         if (unlikely (status))
  576.             return status;
  577.     }
  578.  
  579.     point[0].x = x0; point[0].y = y0;
  580.     point[1].x = x1; point[1].y = y1;
  581.     point[2].x = x2; point[2].y = y2;
  582.     status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_CURVE_TO, point, 3);
  583.     if (unlikely (status))
  584.         return status;
  585.  
  586.     path->current_point = point[2];
  587.     path->has_current_point = TRUE;
  588.     path->is_empty_fill = FALSE;
  589.     path->has_curve_to = TRUE;
  590.     path->is_rectilinear = FALSE;
  591.     path->maybe_fill_region = FALSE;
  592.  
  593.     /* coarse bounds */
  594.     if (path->has_last_move_point) {
  595.         _cairo_path_fixed_extents_add (path, &path->last_move_point);
  596.         path->has_last_move_point = FALSE;
  597.     }
  598.     _cairo_path_fixed_extents_add (path, &point[0]);
  599.     _cairo_path_fixed_extents_add (path, &point[1]);
  600.     _cairo_path_fixed_extents_add (path, &point[2]);
  601.  
  602.     return CAIRO_STATUS_SUCCESS;
  603. }
  604.  
  605. cairo_status_t
  606. _cairo_path_fixed_rel_curve_to (cairo_path_fixed_t *path,
  607.                                 cairo_fixed_t dx0, cairo_fixed_t dy0,
  608.                                 cairo_fixed_t dx1, cairo_fixed_t dy1,
  609.                                 cairo_fixed_t dx2, cairo_fixed_t dy2)
  610. {
  611.     if (unlikely (! path->has_current_point))
  612.         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
  613.  
  614.     return _cairo_path_fixed_curve_to (path,
  615.                                        path->current_point.x + dx0,
  616.                                        path->current_point.y + dy0,
  617.  
  618.                                        path->current_point.x + dx1,
  619.                                        path->current_point.y + dy1,
  620.  
  621.                                        path->current_point.x + dx2,
  622.                                        path->current_point.y + dy2);
  623. }
  624.  
  625. cairo_status_t
  626. _cairo_path_fixed_close_path (cairo_path_fixed_t *path)
  627. {
  628.     cairo_status_t status;
  629.  
  630.     if (! path->has_current_point)
  631.         return CAIRO_STATUS_SUCCESS;
  632.  
  633.     /* If the previous op was also a LINE_TO back to the start, discard it */
  634.     if (_cairo_path_last_op (path) == CAIRO_PATH_OP_LINE_TO) {
  635.         if (path->current_point.x == path->last_move_point.x &&
  636.             path->current_point.y == path->last_move_point.y)
  637.         {
  638.             cairo_path_buf_t *buf;
  639.             cairo_point_t *p;
  640.  
  641.             buf = cairo_path_tail (path);
  642.             if (likely (buf->num_points >= 2)) {
  643.                 p = &buf->points[buf->num_points-2];
  644.             } else {
  645.                 cairo_path_buf_t *prev_buf = cairo_path_buf_prev (buf);
  646.                 p = &prev_buf->points[prev_buf->num_points - (2 - buf->num_points)];
  647.             }
  648.  
  649.             path->current_point = *p;
  650.             buf->num_ops--;
  651.             buf->num_points--;
  652.         }
  653.     }
  654.  
  655.     status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_CLOSE_PATH, NULL, 0);
  656.     if (unlikely (status))
  657.         return status;
  658.  
  659.     return _cairo_path_fixed_move_to (path,
  660.                                       path->last_move_point.x,
  661.                                       path->last_move_point.y);
  662. }
  663.  
  664. cairo_bool_t
  665. _cairo_path_fixed_get_current_point (cairo_path_fixed_t *path,
  666.                                      cairo_fixed_t      *x,
  667.                                      cairo_fixed_t      *y)
  668. {
  669.     if (! path->has_current_point)
  670.         return FALSE;
  671.  
  672.     *x = path->current_point.x;
  673.     *y = path->current_point.y;
  674.  
  675.     return TRUE;
  676. }
  677.  
  678. static cairo_status_t
  679. _cairo_path_fixed_add (cairo_path_fixed_t   *path,
  680.                        cairo_path_op_t       op,
  681.                        const cairo_point_t  *points,
  682.                        int                   num_points)
  683. {
  684.     cairo_path_buf_t *buf = cairo_path_tail (path);
  685.  
  686.     if (buf->num_ops + 1 > buf->size_ops ||
  687.         buf->num_points + num_points > buf->size_points)
  688.     {
  689.         buf = _cairo_path_buf_create (buf->num_ops * 2, buf->num_points * 2);
  690.         if (unlikely (buf == NULL))
  691.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  692.  
  693.         _cairo_path_fixed_add_buf (path, buf);
  694.     }
  695.  
  696.     if (WATCH_PATH) {
  697.         const char *op_str[] = {
  698.             "move-to",
  699.             "line-to",
  700.             "curve-to",
  701.             "close-path",
  702.         };
  703.         char buf[1024];
  704.         int len = 0;
  705.         int i;
  706.  
  707.         len += snprintf (buf + len, sizeof (buf), "[");
  708.         for (i = 0; i < num_points; i++) {
  709.             if (i != 0)
  710.                 len += snprintf (buf + len, sizeof (buf), " ");
  711.             len += snprintf (buf + len, sizeof (buf), "(%f, %f)",
  712.                              _cairo_fixed_to_double (points[i].x),
  713.                              _cairo_fixed_to_double (points[i].y));
  714.         }
  715.         len += snprintf (buf + len, sizeof (buf), "]");
  716.  
  717.         fprintf (stderr,
  718.                  "_cairo_path_fixed_add (%s, %s)\n",
  719.                  op_str[(int) op], buf);
  720.     }
  721.  
  722.     _cairo_path_buf_add_op (buf, op);
  723.     _cairo_path_buf_add_points (buf, points, num_points);
  724.  
  725.     return CAIRO_STATUS_SUCCESS;
  726. }
  727.  
  728. static void
  729. _cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
  730.                            cairo_path_buf_t   *buf)
  731. {
  732.     cairo_list_add_tail (&buf->link, &cairo_path_head (path)->link);
  733. }
  734.  
  735. COMPILE_TIME_ASSERT (sizeof (cairo_path_op_t) == 1);
  736. static cairo_path_buf_t *
  737. _cairo_path_buf_create (int size_ops, int size_points)
  738. {
  739.     cairo_path_buf_t *buf;
  740.  
  741.     /* adjust size_ops to ensure that buf->points is naturally aligned */
  742.     size_ops += sizeof (double) - ((sizeof (cairo_path_buf_t) + size_ops) % sizeof (double));
  743.     buf = _cairo_malloc_ab_plus_c (size_points, sizeof (cairo_point_t), size_ops + sizeof (cairo_path_buf_t));
  744.     if (buf) {
  745.         buf->num_ops = 0;
  746.         buf->num_points = 0;
  747.         buf->size_ops = size_ops;
  748.         buf->size_points = size_points;
  749.  
  750.         buf->op = (cairo_path_op_t *) (buf + 1);
  751.         buf->points = (cairo_point_t *) (buf->op + size_ops);
  752.     }
  753.  
  754.     return buf;
  755. }
  756.  
  757. static void
  758. _cairo_path_buf_destroy (cairo_path_buf_t *buf)
  759. {
  760.     free (buf);
  761. }
  762.  
  763. static void
  764. _cairo_path_buf_add_op (cairo_path_buf_t *buf,
  765.                         cairo_path_op_t   op)
  766. {
  767.     buf->op[buf->num_ops++] = op;
  768. }
  769.  
  770. static void
  771. _cairo_path_buf_add_points (cairo_path_buf_t       *buf,
  772.                             const cairo_point_t    *points,
  773.                             int                     num_points)
  774. {
  775.     memcpy (buf->points + buf->num_points,
  776.             points,
  777.             sizeof (points[0]) * num_points);
  778.     buf->num_points += num_points;
  779. }
  780.  
  781. cairo_status_t
  782. _cairo_path_fixed_interpret (const cairo_path_fixed_t           *path,
  783.                              cairo_direction_t                   dir,
  784.                              cairo_path_fixed_move_to_func_t    *move_to,
  785.                              cairo_path_fixed_line_to_func_t    *line_to,
  786.                              cairo_path_fixed_curve_to_func_t   *curve_to,
  787.                              cairo_path_fixed_close_path_func_t *close_path,
  788.                              void                               *closure)
  789. {
  790.     const uint8_t num_args[] = {
  791.         1, /* cairo_path_move_to */
  792.         1, /* cairo_path_op_line_to */
  793.         3, /* cairo_path_op_curve_to */
  794.         0, /* cairo_path_op_close_path */
  795.     };
  796.     cairo_status_t status;
  797.     const cairo_path_buf_t *buf, *first;
  798.     cairo_bool_t forward = (dir == CAIRO_DIRECTION_FORWARD);
  799.     int step = forward ? 1 : -1;
  800.  
  801.     buf = first = forward ? cairo_path_head (path) : cairo_path_tail (path);
  802.     do {
  803.         cairo_point_t *points;
  804.         int start, stop, i;
  805.  
  806.         if (forward) {
  807.             start = 0;
  808.             stop = buf->num_ops;
  809.             points = buf->points;
  810.         } else {
  811.             start = buf->num_ops - 1;
  812.             stop = -1;
  813.             points = buf->points + buf->num_points;
  814.         }
  815.  
  816.         for (i = start; i != stop; i += step) {
  817.             cairo_path_op_t op = buf->op[i];
  818.  
  819.             if (! forward)
  820.                 points -= num_args[(int) op];
  821.  
  822.             switch (op) {
  823.             case CAIRO_PATH_OP_MOVE_TO:
  824.                 status = (*move_to) (closure, &points[0]);
  825.                 break;
  826.             case CAIRO_PATH_OP_LINE_TO:
  827.                 status = (*line_to) (closure, &points[0]);
  828.                 break;
  829.             case CAIRO_PATH_OP_CURVE_TO:
  830.                 status = (*curve_to) (closure, &points[0], &points[1], &points[2]);
  831.                 break;
  832.             default:
  833.                 ASSERT_NOT_REACHED;
  834.             case CAIRO_PATH_OP_CLOSE_PATH:
  835.                 status = (*close_path) (closure);
  836.                 break;
  837.             }
  838.             if (unlikely (status))
  839.                 return status;
  840.  
  841.             if (forward)
  842.                 points += num_args[(int) op];
  843.         }
  844.     } while ((buf = forward ? cairo_path_buf_next (buf) : cairo_path_buf_prev (buf)) != first);
  845.  
  846.     return CAIRO_STATUS_SUCCESS;
  847. }
  848.  
  849. typedef struct _cairo_path_fixed_append_closure {
  850.     cairo_point_t           offset;
  851.     cairo_path_fixed_t      *path;
  852. } cairo_path_fixed_append_closure_t;
  853.  
  854. static cairo_status_t
  855. _append_move_to (void            *abstract_closure,
  856.                  const cairo_point_t  *point)
  857. {
  858.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  859.  
  860.     return _cairo_path_fixed_move_to (closure->path,
  861.                                       point->x + closure->offset.x,
  862.                                       point->y + closure->offset.y);
  863. }
  864.  
  865. static cairo_status_t
  866. _append_line_to (void            *abstract_closure,
  867.                  const cairo_point_t *point)
  868. {
  869.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  870.  
  871.     return _cairo_path_fixed_line_to (closure->path,
  872.                                       point->x + closure->offset.x,
  873.                                       point->y + closure->offset.y);
  874. }
  875.  
  876. static cairo_status_t
  877. _append_curve_to (void    *abstract_closure,
  878.                   const cairo_point_t *p0,
  879.                   const cairo_point_t *p1,
  880.                   const cairo_point_t *p2)
  881. {
  882.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  883.  
  884.     return _cairo_path_fixed_curve_to (closure->path,
  885.                                        p0->x + closure->offset.x,
  886.                                        p0->y + closure->offset.y,
  887.                                        p1->x + closure->offset.x,
  888.                                        p1->y + closure->offset.y,
  889.                                        p2->x + closure->offset.x,
  890.                                        p2->y + closure->offset.y);
  891. }
  892.  
  893. static cairo_status_t
  894. _append_close_path (void *abstract_closure)
  895. {
  896.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  897.  
  898.     return _cairo_path_fixed_close_path (closure->path);
  899. }
  900.  
  901. cairo_status_t
  902. _cairo_path_fixed_append (cairo_path_fixed_t                *path,
  903.                           const cairo_path_fixed_t          *other,
  904.                           cairo_direction_t                  dir,
  905.                           cairo_fixed_t                      tx,
  906.                           cairo_fixed_t                      ty)
  907. {
  908.     cairo_path_fixed_append_closure_t closure;
  909.  
  910.     closure.path = path;
  911.     closure.offset.x = tx;
  912.     closure.offset.y = ty;
  913.  
  914.     return _cairo_path_fixed_interpret (other, dir,
  915.                                         _append_move_to,
  916.                                         _append_line_to,
  917.                                         _append_curve_to,
  918.                                         _append_close_path,
  919.                                         &closure);
  920. }
  921.  
  922. static void
  923. _cairo_path_fixed_offset_and_scale (cairo_path_fixed_t *path,
  924.                                     cairo_fixed_t offx,
  925.                                     cairo_fixed_t offy,
  926.                                     cairo_fixed_t scalex,
  927.                                     cairo_fixed_t scaley)
  928. {
  929.     cairo_path_buf_t *buf;
  930.     unsigned int i;
  931.  
  932.     if (path->maybe_fill_region) {
  933.         path->maybe_fill_region = _cairo_fixed_is_integer (offx) &&
  934.                                   _cairo_fixed_is_integer (offy) &&
  935.                                   _cairo_fixed_is_integer (scalex) &&
  936.                                   _cairo_fixed_is_integer (scaley);
  937.     }
  938.  
  939.     cairo_path_foreach_buf_start (buf, path) {
  940.          for (i = 0; i < buf->num_points; i++) {
  941.              if (scalex != CAIRO_FIXED_ONE)
  942.                  buf->points[i].x = _cairo_fixed_mul (buf->points[i].x, scalex);
  943.              buf->points[i].x += offx;
  944.  
  945.              if (scaley != CAIRO_FIXED_ONE)
  946.                  buf->points[i].y = _cairo_fixed_mul (buf->points[i].y, scaley);
  947.              buf->points[i].y += offy;
  948.          }
  949.     } cairo_path_foreach_buf_end (buf, path);
  950.  
  951.     path->extents.p1.x = _cairo_fixed_mul (scalex, path->extents.p1.x) + offx;
  952.     path->extents.p2.x = _cairo_fixed_mul (scalex, path->extents.p2.x) + offx;
  953.  
  954.     path->extents.p1.y = _cairo_fixed_mul (scaley, path->extents.p1.y) + offy;
  955.     path->extents.p2.y = _cairo_fixed_mul (scaley, path->extents.p2.y) + offy;
  956. }
  957.  
  958. void
  959. _cairo_path_fixed_translate (cairo_path_fixed_t *path,
  960.                              cairo_fixed_t offx,
  961.                              cairo_fixed_t offy)
  962. {
  963.     cairo_path_buf_t *buf;
  964.     unsigned int i;
  965.  
  966.     if (offx == 0 && offy == 0)
  967.         return;
  968.  
  969.     if (path->maybe_fill_region &&
  970.         ! (_cairo_fixed_is_integer (offx) && _cairo_fixed_is_integer (offy)))
  971.     {
  972.         path->maybe_fill_region = FALSE;
  973.     }
  974.  
  975.     path->last_move_point.x += offx;
  976.     path->last_move_point.y += offy;
  977.     path->current_point.x += offx;
  978.     path->current_point.y += offy;
  979.  
  980.     cairo_path_foreach_buf_start (buf, path) {
  981.          for (i = 0; i < buf->num_points; i++) {
  982.              buf->points[i].x += offx;
  983.              buf->points[i].y += offy;
  984.          }
  985.     } cairo_path_foreach_buf_end (buf, path);
  986.  
  987.     path->extents.p1.x += offx;
  988.     path->extents.p1.y += offy;
  989.     path->extents.p2.x += offx;
  990.     path->extents.p2.y += offy;
  991. }
  992.  
  993. /**
  994.  * _cairo_path_fixed_transform:
  995.  * @path: a #cairo_path_fixed_t to be transformed
  996.  * @matrix: a #cairo_matrix_t
  997.  *
  998.  * Transform the fixed-point path according to the given matrix.
  999.  * There is a fast path for the case where @matrix has no rotation
  1000.  * or shear.
  1001.  **/
  1002. void
  1003. _cairo_path_fixed_transform (cairo_path_fixed_t *path,
  1004.                              const cairo_matrix_t     *matrix)
  1005. {
  1006.     cairo_path_buf_t *buf;
  1007.     unsigned int i;
  1008.     double dx, dy;
  1009.  
  1010.     /* XXX current_point, last_move_to */
  1011.  
  1012.     if (matrix->yx == 0.0 && matrix->xy == 0.0) {
  1013.         /* Fast path for the common case of scale+transform */
  1014.          if (matrix->xx == 1. && matrix->yy == 1.) {
  1015.              _cairo_path_fixed_translate (path,
  1016.                                           _cairo_fixed_from_double (matrix->x0),
  1017.                                           _cairo_fixed_from_double (matrix->y0));
  1018.          } else {
  1019.              _cairo_path_fixed_offset_and_scale (path,
  1020.                                                  _cairo_fixed_from_double (matrix->x0),
  1021.                                                  _cairo_fixed_from_double (matrix->y0),
  1022.                                                  _cairo_fixed_from_double (matrix->xx),
  1023.                                                  _cairo_fixed_from_double (matrix->yy));
  1024.          }
  1025.         return;
  1026.     }
  1027.  
  1028.     path->extents.p1.x = path->extents.p1.y = INT_MAX;
  1029.     path->extents.p2.x = path->extents.p2.y = INT_MIN;
  1030.     path->maybe_fill_region = FALSE;
  1031.     cairo_path_foreach_buf_start (buf, path) {
  1032.          for (i = 0; i < buf->num_points; i++) {
  1033.             dx = _cairo_fixed_to_double (buf->points[i].x);
  1034.             dy = _cairo_fixed_to_double (buf->points[i].y);
  1035.  
  1036.             cairo_matrix_transform_point (matrix, &dx, &dy);
  1037.  
  1038.             buf->points[i].x = _cairo_fixed_from_double (dx);
  1039.             buf->points[i].y = _cairo_fixed_from_double (dy);
  1040.  
  1041.             /* XXX need to eliminate surplus move-to's? */
  1042.             _cairo_path_fixed_extents_add (path, &buf->points[i]);
  1043.          }
  1044.     } cairo_path_foreach_buf_end (buf, path);
  1045. }
  1046.  
  1047. cairo_bool_t
  1048. _cairo_path_fixed_is_equal (const cairo_path_fixed_t *path,
  1049.                             const cairo_path_fixed_t *other)
  1050. {
  1051.     const cairo_path_buf_t *path_buf, *other_buf;
  1052.  
  1053.     if (path->current_point.x != other->current_point.x ||
  1054.         path->current_point.y != other->current_point.y ||
  1055.         path->has_current_point != other->has_current_point ||
  1056.         path->has_curve_to != other->has_curve_to ||
  1057.         path->is_rectilinear != other->is_rectilinear ||
  1058.         path->maybe_fill_region != other->maybe_fill_region ||
  1059.         path->last_move_point.x != other->last_move_point.x ||
  1060.         path->last_move_point.y != other->last_move_point.y)
  1061.     {
  1062.         return FALSE;
  1063.     }
  1064.  
  1065.     other_buf = cairo_path_head (other);
  1066.     cairo_path_foreach_buf_start (path_buf, path) {
  1067.         if (path_buf->num_ops != other_buf->num_ops ||
  1068.             path_buf->num_points != other_buf->num_points ||
  1069.             memcmp (path_buf->op, other_buf->op,
  1070.                     sizeof (cairo_path_op_t) * path_buf->num_ops) != 0 ||
  1071.             memcmp (path_buf->points, other_buf->points,
  1072.                     sizeof (cairo_point_t) * path_buf->num_points) != 0)
  1073.         {
  1074.             return FALSE;
  1075.         }
  1076.         other_buf = cairo_path_buf_next (other_buf);
  1077.     } cairo_path_foreach_buf_end (path_buf, path);
  1078.  
  1079.     return TRUE;
  1080. }
  1081.  
  1082. /* Closure for path flattening */
  1083. typedef struct cairo_path_flattener {
  1084.     double tolerance;
  1085.     cairo_point_t current_point;
  1086.     cairo_path_fixed_move_to_func_t     *move_to;
  1087.     cairo_path_fixed_line_to_func_t     *line_to;
  1088.     cairo_path_fixed_close_path_func_t  *close_path;
  1089.     void *closure;
  1090. } cpf_t;
  1091.  
  1092. static cairo_status_t
  1093. _cpf_move_to (void *closure,
  1094.               const cairo_point_t *point)
  1095. {
  1096.     cpf_t *cpf = closure;
  1097.  
  1098.     cpf->current_point = *point;
  1099.  
  1100.     return cpf->move_to (cpf->closure, point);
  1101. }
  1102.  
  1103. static cairo_status_t
  1104. _cpf_line_to (void *closure,
  1105.               const cairo_point_t *point)
  1106. {
  1107.     cpf_t *cpf = closure;
  1108.  
  1109.     cpf->current_point = *point;
  1110.  
  1111.     return cpf->line_to (cpf->closure, point);
  1112. }
  1113.  
  1114. static cairo_status_t
  1115. _cpf_curve_to (void             *closure,
  1116.                const cairo_point_t      *p1,
  1117.                const cairo_point_t      *p2,
  1118.                const cairo_point_t      *p3)
  1119. {
  1120.     cpf_t *cpf = closure;
  1121.     cairo_spline_t spline;
  1122.  
  1123.     cairo_point_t *p0 = &cpf->current_point;
  1124.  
  1125.     if (! _cairo_spline_init (&spline,
  1126.                               cpf->line_to,
  1127.                               cpf->closure,
  1128.                               p0, p1, p2, p3))
  1129.     {
  1130.         return _cpf_line_to (closure, p3);
  1131.     }
  1132.  
  1133.     cpf->current_point = *p3;
  1134.  
  1135.     return _cairo_spline_decompose (&spline, cpf->tolerance);
  1136. }
  1137.  
  1138. static cairo_status_t
  1139. _cpf_close_path (void *closure)
  1140. {
  1141.     cpf_t *cpf = closure;
  1142.  
  1143.     return cpf->close_path (cpf->closure);
  1144. }
  1145.  
  1146. cairo_status_t
  1147. _cairo_path_fixed_interpret_flat (const cairo_path_fixed_t              *path,
  1148.                                   cairo_direction_t                     dir,
  1149.                                   cairo_path_fixed_move_to_func_t       *move_to,
  1150.                                   cairo_path_fixed_line_to_func_t       *line_to,
  1151.                                   cairo_path_fixed_close_path_func_t    *close_path,
  1152.                                   void                                  *closure,
  1153.                                   double                                tolerance)
  1154. {
  1155.     cpf_t flattener;
  1156.  
  1157.     if (! path->has_curve_to) {
  1158.         return _cairo_path_fixed_interpret (path, dir,
  1159.                                             move_to,
  1160.                                             line_to,
  1161.                                             NULL,
  1162.                                             close_path,
  1163.                                             closure);
  1164.     }
  1165.  
  1166.     flattener.tolerance = tolerance;
  1167.     flattener.move_to = move_to;
  1168.     flattener.line_to = line_to;
  1169.     flattener.close_path = close_path;
  1170.     flattener.closure = closure;
  1171.     return _cairo_path_fixed_interpret (path, dir,
  1172.                                         _cpf_move_to,
  1173.                                         _cpf_line_to,
  1174.                                         _cpf_curve_to,
  1175.                                         _cpf_close_path,
  1176.                                         &flattener);
  1177. }
  1178.  
  1179. static inline void
  1180. _canonical_box (cairo_box_t *box,
  1181.                 const cairo_point_t *p1,
  1182.                 const cairo_point_t *p2)
  1183. {
  1184.     if (p1->x <= p2->x) {
  1185.         box->p1.x = p1->x;
  1186.         box->p2.x = p2->x;
  1187.     } else {
  1188.         box->p1.x = p2->x;
  1189.         box->p2.x = p1->x;
  1190.     }
  1191.  
  1192.     if (p1->y <= p2->y) {
  1193.         box->p1.y = p1->y;
  1194.         box->p2.y = p2->y;
  1195.     } else {
  1196.         box->p1.y = p2->y;
  1197.         box->p2.y = p1->y;
  1198.     }
  1199. }
  1200.  
  1201. /*
  1202.  * Check whether the given path contains a single rectangle.
  1203.  */
  1204. cairo_bool_t
  1205. _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
  1206.                           cairo_box_t *box)
  1207. {
  1208.     const cairo_path_buf_t *buf = cairo_path_head (path);
  1209.  
  1210.     if (! path->is_rectilinear)
  1211.         return FALSE;
  1212.  
  1213.     /* Do we have the right number of ops? */
  1214.     if (buf->num_ops < 4 || buf->num_ops > 6)
  1215.         return FALSE;
  1216.  
  1217.     /* Check whether the ops are those that would be used for a rectangle */
  1218.     if (buf->op[0] != CAIRO_PATH_OP_MOVE_TO ||
  1219.         buf->op[1] != CAIRO_PATH_OP_LINE_TO ||
  1220.         buf->op[2] != CAIRO_PATH_OP_LINE_TO ||
  1221.         buf->op[3] != CAIRO_PATH_OP_LINE_TO)
  1222.     {
  1223.         return FALSE;
  1224.     }
  1225.  
  1226.     /* we accept an implicit close for filled paths */
  1227.     if (buf->num_ops > 4) {
  1228.         /* Now, there are choices. The rectangle might end with a LINE_TO
  1229.          * (to the original point), but this isn't required. If it
  1230.          * doesn't, then it must end with a CLOSE_PATH. */
  1231.         if (buf->op[4] == CAIRO_PATH_OP_LINE_TO) {
  1232.             if (buf->points[4].x != buf->points[0].x ||
  1233.                 buf->points[4].y != buf->points[0].y)
  1234.                 return FALSE;
  1235.         } else if (buf->op[4] != CAIRO_PATH_OP_CLOSE_PATH) {
  1236.             return FALSE;
  1237.         }
  1238.  
  1239.         if (buf->num_ops == 6) {
  1240.             /* A trailing CLOSE_PATH or MOVE_TO is ok */
  1241.             if (buf->op[5] != CAIRO_PATH_OP_MOVE_TO &&
  1242.                 buf->op[5] != CAIRO_PATH_OP_CLOSE_PATH)
  1243.                 return FALSE;
  1244.         }
  1245.     }
  1246.  
  1247.     /* Ok, we may have a box, if the points line up */
  1248.     if (buf->points[0].y == buf->points[1].y &&
  1249.         buf->points[1].x == buf->points[2].x &&
  1250.         buf->points[2].y == buf->points[3].y &&
  1251.         buf->points[3].x == buf->points[0].x)
  1252.     {
  1253.         _canonical_box (box, &buf->points[0], &buf->points[2]);
  1254.         return TRUE;
  1255.     }
  1256.  
  1257.     if (buf->points[0].x == buf->points[1].x &&
  1258.         buf->points[1].y == buf->points[2].y &&
  1259.         buf->points[2].x == buf->points[3].x &&
  1260.         buf->points[3].y == buf->points[0].y)
  1261.     {
  1262.         _canonical_box (box, &buf->points[0], &buf->points[2]);
  1263.         return TRUE;
  1264.     }
  1265.  
  1266.     return FALSE;
  1267. }
  1268.  
  1269. /*
  1270.  * Check whether the given path contains a single rectangle
  1271.  * that is logically equivalent to:
  1272.  * <informalexample><programlisting>
  1273.  *   cairo_move_to (cr, x, y);
  1274.  *   cairo_rel_line_to (cr, width, 0);
  1275.  *   cairo_rel_line_to (cr, 0, height);
  1276.  *   cairo_rel_line_to (cr, -width, 0);
  1277.  *   cairo_close_path (cr);
  1278.  * </programlisting></informalexample>
  1279.  */
  1280. cairo_bool_t
  1281. _cairo_path_fixed_is_rectangle (const cairo_path_fixed_t *path,
  1282.                                 cairo_box_t        *box)
  1283. {
  1284.     const cairo_path_buf_t *buf;
  1285.  
  1286.     if (! _cairo_path_fixed_is_box (path, box))
  1287.         return FALSE;
  1288.  
  1289.     buf = cairo_path_head (path);
  1290.     if (buf->points[0].y == buf->points[1].y)
  1291.         return TRUE;
  1292.  
  1293.     return FALSE;
  1294. }
  1295.  
  1296. void
  1297. _cairo_path_fixed_iter_init (cairo_path_fixed_iter_t *iter,
  1298.                              const cairo_path_fixed_t *path)
  1299. {
  1300.     iter->first = iter->buf = cairo_path_head (path);
  1301.     iter->n_op = 0;
  1302.     iter->n_point = 0;
  1303. }
  1304.  
  1305. static cairo_bool_t
  1306. _cairo_path_fixed_iter_next_op (cairo_path_fixed_iter_t *iter)
  1307. {
  1308.     if (++iter->n_op >= iter->buf->num_ops) {
  1309.         iter->buf = cairo_path_buf_next (iter->buf);
  1310.         if (iter->buf == iter->first) {
  1311.             iter->buf = NULL;
  1312.             return FALSE;
  1313.         }
  1314.  
  1315.         iter->n_op = 0;
  1316.         iter->n_point = 0;
  1317.     }
  1318.  
  1319.     return TRUE;
  1320. }
  1321.  
  1322. cairo_bool_t
  1323. _cairo_path_fixed_iter_is_fill_box (cairo_path_fixed_iter_t *_iter,
  1324.                                     cairo_box_t *box)
  1325. {
  1326.     cairo_point_t points[5];
  1327.     cairo_path_fixed_iter_t iter;
  1328.  
  1329.     if (_iter->buf == NULL)
  1330.         return FALSE;
  1331.  
  1332.     iter = *_iter;
  1333.  
  1334.     if (iter.n_op == iter.buf->num_ops &&
  1335.         ! _cairo_path_fixed_iter_next_op (&iter))
  1336.     {
  1337.         return FALSE;
  1338.     }
  1339.  
  1340.     /* Check whether the ops are those that would be used for a rectangle */
  1341.     if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_MOVE_TO)
  1342.         return FALSE;
  1343.     points[0] = iter.buf->points[iter.n_point++];
  1344.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1345.         return FALSE;
  1346.  
  1347.     if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
  1348.         return FALSE;
  1349.     points[1] = iter.buf->points[iter.n_point++];
  1350.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1351.         return FALSE;
  1352.  
  1353.     if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
  1354.         return FALSE;
  1355.     points[2] = iter.buf->points[iter.n_point++];
  1356.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1357.         return FALSE;
  1358.  
  1359.     if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
  1360.         return FALSE;
  1361.     points[3] = iter.buf->points[iter.n_point++];
  1362.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1363.         return FALSE;
  1364.  
  1365.     /* Now, there are choices. The rectangle might end with a LINE_TO
  1366.      * (to the original point), but this isn't required. If it
  1367.      * doesn't, then it must end with a CLOSE_PATH (which may be implicit). */
  1368.     if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_LINE_TO)
  1369.     {
  1370.         points[4] = iter.buf->points[iter.n_point++];
  1371.         if (points[4].x != points[0].x || points[4].y != points[0].y)
  1372.             return FALSE;
  1373.     }
  1374.     else if (! (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_CLOSE_PATH ||
  1375.                 iter.buf->op[iter.n_op] == CAIRO_PATH_OP_MOVE_TO))
  1376.     {
  1377.         return FALSE;
  1378.     }
  1379.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1380.         return FALSE;
  1381.  
  1382.     /* Ok, we may have a box, if the points line up */
  1383.     if (points[0].y == points[1].y &&
  1384.         points[1].x == points[2].x &&
  1385.         points[2].y == points[3].y &&
  1386.         points[3].x == points[0].x)
  1387.     {
  1388.         box->p1 = points[0];
  1389.         box->p2 = points[2];
  1390.         *_iter = iter;
  1391.         return TRUE;
  1392.     }
  1393.  
  1394.     if (points[0].x == points[1].x &&
  1395.         points[1].y == points[2].y &&
  1396.         points[2].x == points[3].x &&
  1397.         points[3].y == points[0].y)
  1398.     {
  1399.         box->p1 = points[1];
  1400.         box->p2 = points[3];
  1401.         *_iter = iter;
  1402.         return TRUE;
  1403.     }
  1404.  
  1405.     return FALSE;
  1406. }
  1407.  
  1408. cairo_bool_t
  1409. _cairo_path_fixed_iter_at_end (const cairo_path_fixed_iter_t *iter)
  1410. {
  1411.     if (iter->buf == NULL)
  1412.         return TRUE;
  1413.  
  1414.     if (iter->n_op == iter->buf->num_ops)
  1415.         return TRUE;
  1416.  
  1417.     if (iter->buf->op[iter->n_op] == CAIRO_PATH_OP_MOVE_TO &&
  1418.         iter->buf->num_ops == iter->n_op + 1)
  1419.     {
  1420.         return TRUE;
  1421.     }
  1422.  
  1423.     return FALSE;
  1424. }
  1425.