Subversion Repositories Kolibri OS

Rev

Rev 1892 | 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-box-inline.h"
  42. #include "cairo-error-private.h"
  43. #include "cairo-list-inline.h"
  44. #include "cairo-path-fixed-private.h"
  45. #include "cairo-slope-private.h"
  46.  
  47. static cairo_status_t
  48. _cairo_path_fixed_add (cairo_path_fixed_t  *path,
  49.                        cairo_path_op_t      op,
  50.                        const cairo_point_t *points,
  51.                        int                  num_points);
  52.  
  53. static void
  54. _cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
  55.                            cairo_path_buf_t   *buf);
  56.  
  57. static cairo_path_buf_t *
  58. _cairo_path_buf_create (int size_ops, int size_points);
  59.  
  60. static void
  61. _cairo_path_buf_destroy (cairo_path_buf_t *buf);
  62.  
  63. static void
  64. _cairo_path_buf_add_op (cairo_path_buf_t *buf,
  65.                         cairo_path_op_t   op);
  66.  
  67. static void
  68. _cairo_path_buf_add_points (cairo_path_buf_t       *buf,
  69.                             const cairo_point_t    *points,
  70.                             int                     num_points);
  71.  
  72. void
  73. _cairo_path_fixed_init (cairo_path_fixed_t *path)
  74. {
  75.     VG (VALGRIND_MAKE_MEM_UNDEFINED (path, sizeof (cairo_path_fixed_t)));
  76.  
  77.     cairo_list_init (&path->buf.base.link);
  78.  
  79.     path->buf.base.num_ops = 0;
  80.     path->buf.base.num_points = 0;
  81.     path->buf.base.size_ops = ARRAY_LENGTH (path->buf.op);
  82.     path->buf.base.size_points = ARRAY_LENGTH (path->buf.points);
  83.     path->buf.base.op = path->buf.op;
  84.     path->buf.base.points = path->buf.points;
  85.  
  86.     path->current_point.x = 0;
  87.     path->current_point.y = 0;
  88.     path->last_move_point = path->current_point;
  89.  
  90.     path->has_current_point = FALSE;
  91.     path->needs_move_to = TRUE;
  92.     path->has_extents = FALSE;
  93.     path->has_curve_to = FALSE;
  94.     path->stroke_is_rectilinear = TRUE;
  95.     path->fill_is_rectilinear = TRUE;
  96.     path->fill_maybe_region = TRUE;
  97.     path->fill_is_empty = TRUE;
  98.  
  99.     path->extents.p1.x = path->extents.p1.y = 0;
  100.     path->extents.p2.x = path->extents.p2.y = 0;
  101. }
  102.  
  103. cairo_status_t
  104. _cairo_path_fixed_init_copy (cairo_path_fixed_t *path,
  105.                              const cairo_path_fixed_t *other)
  106. {
  107.     cairo_path_buf_t *buf, *other_buf;
  108.     unsigned int num_points, num_ops;
  109.  
  110.     VG (VALGRIND_MAKE_MEM_UNDEFINED (path, sizeof (cairo_path_fixed_t)));
  111.  
  112.     cairo_list_init (&path->buf.base.link);
  113.  
  114.     path->buf.base.op = path->buf.op;
  115.     path->buf.base.points = path->buf.points;
  116.     path->buf.base.size_ops = ARRAY_LENGTH (path->buf.op);
  117.     path->buf.base.size_points = ARRAY_LENGTH (path->buf.points);
  118.  
  119.     path->current_point = other->current_point;
  120.     path->last_move_point = other->last_move_point;
  121.  
  122.     path->has_current_point = other->has_current_point;
  123.     path->needs_move_to = other->needs_move_to;
  124.     path->has_extents = other->has_extents;
  125.     path->has_curve_to = other->has_curve_to;
  126.     path->stroke_is_rectilinear = other->stroke_is_rectilinear;
  127.     path->fill_is_rectilinear = other->fill_is_rectilinear;
  128.     path->fill_maybe_region = other->fill_maybe_region;
  129.     path->fill_is_empty = other->fill_is_empty;
  130.  
  131.     path->extents = other->extents;
  132.  
  133.     path->buf.base.num_ops = other->buf.base.num_ops;
  134.     path->buf.base.num_points = other->buf.base.num_points;
  135.     memcpy (path->buf.op, other->buf.base.op,
  136.             other->buf.base.num_ops * sizeof (other->buf.op[0]));
  137.     memcpy (path->buf.points, other->buf.points,
  138.             other->buf.base.num_points * sizeof (other->buf.points[0]));
  139.  
  140.     num_points = num_ops = 0;
  141.     for (other_buf = cairo_path_buf_next (cairo_path_head (other));
  142.          other_buf != cairo_path_head (other);
  143.          other_buf = cairo_path_buf_next (other_buf))
  144.     {
  145.         num_ops    += other_buf->num_ops;
  146.         num_points += other_buf->num_points;
  147.     }
  148.  
  149.     if (num_ops) {
  150.         buf = _cairo_path_buf_create (num_ops, num_points);
  151.         if (unlikely (buf == NULL)) {
  152.             _cairo_path_fixed_fini (path);
  153.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  154.         }
  155.  
  156.         for (other_buf = cairo_path_buf_next (cairo_path_head (other));
  157.              other_buf != cairo_path_head (other);
  158.              other_buf = cairo_path_buf_next (other_buf))
  159.         {
  160.             memcpy (buf->op + buf->num_ops, other_buf->op,
  161.                     other_buf->num_ops * sizeof (buf->op[0]));
  162.             buf->num_ops += other_buf->num_ops;
  163.  
  164.             memcpy (buf->points + buf->num_points, other_buf->points,
  165.                     other_buf->num_points * sizeof (buf->points[0]));
  166.             buf->num_points += other_buf->num_points;
  167.         }
  168.  
  169.         _cairo_path_fixed_add_buf (path, buf);
  170.     }
  171.  
  172.     return CAIRO_STATUS_SUCCESS;
  173. }
  174.  
  175. unsigned long
  176. _cairo_path_fixed_hash (const cairo_path_fixed_t *path)
  177. {
  178.     unsigned long hash = _CAIRO_HASH_INIT_VALUE;
  179.     const cairo_path_buf_t *buf;
  180.     unsigned int count;
  181.  
  182.     count = 0;
  183.     cairo_path_foreach_buf_start (buf, path) {
  184.         hash = _cairo_hash_bytes (hash, buf->op,
  185.                                   buf->num_ops * sizeof (buf->op[0]));
  186.         count += buf->num_ops;
  187.     } cairo_path_foreach_buf_end (buf, path);
  188.     hash = _cairo_hash_bytes (hash, &count, sizeof (count));
  189.  
  190.     count = 0;
  191.     cairo_path_foreach_buf_start (buf, path) {
  192.         hash = _cairo_hash_bytes (hash, buf->points,
  193.                                   buf->num_points * sizeof (buf->points[0]));
  194.         count += buf->num_points;
  195.     } cairo_path_foreach_buf_end (buf, path);
  196.     hash = _cairo_hash_bytes (hash, &count, sizeof (count));
  197.  
  198.     return hash;
  199. }
  200.  
  201. unsigned long
  202. _cairo_path_fixed_size (const cairo_path_fixed_t *path)
  203. {
  204.     const cairo_path_buf_t *buf;
  205.     int num_points, num_ops;
  206.  
  207.     num_ops = num_points = 0;
  208.     cairo_path_foreach_buf_start (buf, path) {
  209.         num_ops    += buf->num_ops;
  210.         num_points += buf->num_points;
  211.     } cairo_path_foreach_buf_end (buf, path);
  212.  
  213.     return num_ops * sizeof (buf->op[0]) +
  214.            num_points * sizeof (buf->points[0]);
  215. }
  216.  
  217. cairo_bool_t
  218. _cairo_path_fixed_equal (const cairo_path_fixed_t *a,
  219.                          const cairo_path_fixed_t *b)
  220. {
  221.     const cairo_path_buf_t *buf_a, *buf_b;
  222.     const cairo_path_op_t *ops_a, *ops_b;
  223.     const cairo_point_t *points_a, *points_b;
  224.     int num_points_a, num_ops_a;
  225.     int num_points_b, num_ops_b;
  226.  
  227.     if (a == b)
  228.         return TRUE;
  229.  
  230.     /* use the flags to quickly differentiate based on contents */
  231.     if (a->has_curve_to != b->has_curve_to)
  232.     {
  233.         return FALSE;
  234.     }
  235.  
  236.     if (a->extents.p1.x != b->extents.p1.x ||
  237.         a->extents.p1.y != b->extents.p1.y ||
  238.         a->extents.p2.x != b->extents.p2.x ||
  239.         a->extents.p2.y != b->extents.p2.y)
  240.     {
  241.         return FALSE;
  242.     }
  243.  
  244.     num_ops_a = num_points_a = 0;
  245.     cairo_path_foreach_buf_start (buf_a, a) {
  246.         num_ops_a    += buf_a->num_ops;
  247.         num_points_a += buf_a->num_points;
  248.     } cairo_path_foreach_buf_end (buf_a, a);
  249.  
  250.     num_ops_b = num_points_b = 0;
  251.     cairo_path_foreach_buf_start (buf_b, b) {
  252.         num_ops_b    += buf_b->num_ops;
  253.         num_points_b += buf_b->num_points;
  254.     } cairo_path_foreach_buf_end (buf_b, b);
  255.  
  256.     if (num_ops_a == 0 && num_ops_b == 0)
  257.         return TRUE;
  258.  
  259.     if (num_ops_a != num_ops_b || num_points_a != num_points_b)
  260.         return FALSE;
  261.  
  262.     buf_a = cairo_path_head (a);
  263.     num_points_a = buf_a->num_points;
  264.     num_ops_a = buf_a->num_ops;
  265.     ops_a = buf_a->op;
  266.     points_a = buf_a->points;
  267.  
  268.     buf_b = cairo_path_head (b);
  269.     num_points_b = buf_b->num_points;
  270.     num_ops_b = buf_b->num_ops;
  271.     ops_b = buf_b->op;
  272.     points_b = buf_b->points;
  273.  
  274.     while (TRUE) {
  275.         int num_ops = MIN (num_ops_a, num_ops_b);
  276.         int num_points = MIN (num_points_a, num_points_b);
  277.  
  278.         if (memcmp (ops_a, ops_b, num_ops * sizeof (cairo_path_op_t)))
  279.             return FALSE;
  280.         if (memcmp (points_a, points_b, num_points * sizeof (cairo_point_t)))
  281.             return FALSE;
  282.  
  283.         num_ops_a -= num_ops;
  284.         ops_a += num_ops;
  285.         num_points_a -= num_points;
  286.         points_a += num_points;
  287.         if (num_ops_a == 0 || num_points_a == 0) {
  288.             if (num_ops_a || num_points_a)
  289.                 return FALSE;
  290.  
  291.             buf_a = cairo_path_buf_next (buf_a);
  292.             if (buf_a == cairo_path_head (a))
  293.                 break;
  294.  
  295.             num_points_a = buf_a->num_points;
  296.             num_ops_a = buf_a->num_ops;
  297.             ops_a = buf_a->op;
  298.             points_a = buf_a->points;
  299.         }
  300.  
  301.         num_ops_b -= num_ops;
  302.         ops_b += num_ops;
  303.         num_points_b -= num_points;
  304.         points_b += num_points;
  305.         if (num_ops_b == 0 || num_points_b == 0) {
  306.             if (num_ops_b || num_points_b)
  307.                 return FALSE;
  308.  
  309.             buf_b = cairo_path_buf_next (buf_b);
  310.             if (buf_b == cairo_path_head (b))
  311.                 break;
  312.  
  313.             num_points_b = buf_b->num_points;
  314.             num_ops_b = buf_b->num_ops;
  315.             ops_b = buf_b->op;
  316.             points_b = buf_b->points;
  317.         }
  318.     }
  319.  
  320.     return TRUE;
  321. }
  322.  
  323. cairo_path_fixed_t *
  324. _cairo_path_fixed_create (void)
  325. {
  326.     cairo_path_fixed_t  *path;
  327.  
  328.     path = malloc (sizeof (cairo_path_fixed_t));
  329.     if (!path) {
  330.         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
  331.         return NULL;
  332.     }
  333.  
  334.     _cairo_path_fixed_init (path);
  335.     return path;
  336. }
  337.  
  338. void
  339. _cairo_path_fixed_fini (cairo_path_fixed_t *path)
  340. {
  341.     cairo_path_buf_t *buf;
  342.  
  343.     buf = cairo_path_buf_next (cairo_path_head (path));
  344.     while (buf != cairo_path_head (path)) {
  345.         cairo_path_buf_t *this = buf;
  346.         buf = cairo_path_buf_next (buf);
  347.         _cairo_path_buf_destroy (this);
  348.     }
  349.  
  350.     VG (VALGRIND_MAKE_MEM_NOACCESS (path, sizeof (cairo_path_fixed_t)));
  351. }
  352.  
  353. void
  354. _cairo_path_fixed_destroy (cairo_path_fixed_t *path)
  355. {
  356.     _cairo_path_fixed_fini (path);
  357.     free (path);
  358. }
  359.  
  360. static cairo_path_op_t
  361. _cairo_path_fixed_last_op (cairo_path_fixed_t *path)
  362. {
  363.     cairo_path_buf_t *buf;
  364.  
  365.     buf = cairo_path_tail (path);
  366.     assert (buf->num_ops != 0);
  367.  
  368.     return buf->op[buf->num_ops - 1];
  369. }
  370.  
  371. static inline const cairo_point_t *
  372. _cairo_path_fixed_penultimate_point (cairo_path_fixed_t *path)
  373. {
  374.     cairo_path_buf_t *buf;
  375.  
  376.     buf = cairo_path_tail (path);
  377.     if (likely (buf->num_points >= 2)) {
  378.         return &buf->points[buf->num_points - 2];
  379.     } else {
  380.         cairo_path_buf_t *prev_buf = cairo_path_buf_prev (buf);
  381.  
  382.         assert (prev_buf->num_points >= 2 - buf->num_points);
  383.         return &prev_buf->points[prev_buf->num_points - (2 - buf->num_points)];
  384.     }
  385. }
  386.  
  387. static void
  388. _cairo_path_fixed_drop_line_to (cairo_path_fixed_t *path)
  389. {
  390.     cairo_path_buf_t *buf;
  391.  
  392.     assert (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO);
  393.  
  394.     buf = cairo_path_tail (path);
  395.     buf->num_points--;
  396.     buf->num_ops--;
  397. }
  398.  
  399. cairo_status_t
  400. _cairo_path_fixed_move_to (cairo_path_fixed_t  *path,
  401.                            cairo_fixed_t        x,
  402.                            cairo_fixed_t        y)
  403. {
  404.     _cairo_path_fixed_new_sub_path (path);
  405.  
  406.     path->has_current_point = TRUE;
  407.     path->current_point.x = x;
  408.     path->current_point.y = y;
  409.     path->last_move_point = path->current_point;
  410.  
  411.     return CAIRO_STATUS_SUCCESS;
  412. }
  413.  
  414. static cairo_status_t
  415. _cairo_path_fixed_move_to_apply (cairo_path_fixed_t  *path)
  416. {
  417.     if (likely (! path->needs_move_to))
  418.         return CAIRO_STATUS_SUCCESS;
  419.  
  420.     path->needs_move_to = FALSE;
  421.  
  422.     if (path->has_extents) {
  423.         _cairo_box_add_point (&path->extents, &path->current_point);
  424.     } else {
  425.         _cairo_box_set (&path->extents, &path->current_point, &path->current_point);
  426.         path->has_extents = TRUE;
  427.     }
  428.  
  429.     if (path->fill_maybe_region) {
  430.         path->fill_maybe_region = _cairo_fixed_is_integer (path->current_point.x) &&
  431.                                   _cairo_fixed_is_integer (path->current_point.y);
  432.     }
  433.  
  434.     path->last_move_point = path->current_point;
  435.  
  436.     return _cairo_path_fixed_add (path, CAIRO_PATH_OP_MOVE_TO, &path->current_point, 1);
  437. }
  438.  
  439. void
  440. _cairo_path_fixed_new_sub_path (cairo_path_fixed_t *path)
  441. {
  442.     if (! path->needs_move_to) {
  443.         /* If the current subpath doesn't need_move_to, it contains at least one command */
  444.         if (path->fill_is_rectilinear) {
  445.             /* Implicitly close for fill */
  446.             path->fill_is_rectilinear = path->current_point.x == path->last_move_point.x ||
  447.                                         path->current_point.y == path->last_move_point.y;
  448.             path->fill_maybe_region &= path->fill_is_rectilinear;
  449.         }
  450.         path->needs_move_to = TRUE;
  451.     }
  452.  
  453.     path->has_current_point = FALSE;
  454. }
  455.  
  456. cairo_status_t
  457. _cairo_path_fixed_rel_move_to (cairo_path_fixed_t *path,
  458.                                cairo_fixed_t       dx,
  459.                                cairo_fixed_t       dy)
  460. {
  461.     if (unlikely (! path->has_current_point))
  462.         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
  463.  
  464.     return _cairo_path_fixed_move_to (path,
  465.                                       path->current_point.x + dx,
  466.                                       path->current_point.y + dy);
  467.  
  468. }
  469.  
  470. cairo_status_t
  471. _cairo_path_fixed_line_to (cairo_path_fixed_t *path,
  472.                            cairo_fixed_t        x,
  473.                            cairo_fixed_t        y)
  474. {
  475.     cairo_status_t status;
  476.     cairo_point_t point;
  477.  
  478.     point.x = x;
  479.     point.y = y;
  480.  
  481.     /* When there is not yet a current point, the line_to operation
  482.      * becomes a move_to instead. Note: We have to do this by
  483.      * explicitly calling into _cairo_path_fixed_move_to to ensure
  484.      * that the last_move_point state is updated properly.
  485.      */
  486.     if (! path->has_current_point)
  487.         return _cairo_path_fixed_move_to (path, point.x, point.y);
  488.  
  489.     status = _cairo_path_fixed_move_to_apply (path);
  490.     if (unlikely (status))
  491.         return status;
  492.  
  493.     /* If the previous op was but the initial MOVE_TO and this segment
  494.      * is degenerate, then we can simply skip this point. Note that
  495.      * a move-to followed by a degenerate line-to is a valid path for
  496.      * stroking, but at all other times is simply a degenerate segment.
  497.      */
  498.     if (_cairo_path_fixed_last_op (path) != CAIRO_PATH_OP_MOVE_TO) {
  499.         if (x == path->current_point.x && y == path->current_point.y)
  500.             return CAIRO_STATUS_SUCCESS;
  501.     }
  502.  
  503.     /* If the previous op was also a LINE_TO with the same gradient,
  504.      * then just change its end-point rather than adding a new op.
  505.      */
  506.     if (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO) {
  507.         const cairo_point_t *p;
  508.  
  509.         p = _cairo_path_fixed_penultimate_point (path);
  510.         if (p->x == path->current_point.x && p->y == path->current_point.y) {
  511.             /* previous line element was degenerate, replace */
  512.             _cairo_path_fixed_drop_line_to (path);
  513.         } else {
  514.             cairo_slope_t prev, self;
  515.  
  516.             _cairo_slope_init (&prev, p, &path->current_point);
  517.             _cairo_slope_init (&self, &path->current_point, &point);
  518.             if (_cairo_slope_equal (&prev, &self) &&
  519.                 /* cannot trim anti-parallel segments whilst stroking */
  520.                 ! _cairo_slope_backwards (&prev, &self))
  521.             {
  522.                 _cairo_path_fixed_drop_line_to (path);
  523.                 /* In this case the flags might be more restrictive than
  524.                  * what we actually need.
  525.                  * When changing the flags definition we should check if
  526.                  * changing the line_to point can affect them.
  527.                 */
  528.             }
  529.         }
  530.     }
  531.  
  532.     if (path->stroke_is_rectilinear) {
  533.         path->stroke_is_rectilinear = path->current_point.x == x ||
  534.                                       path->current_point.y == y;
  535.         path->fill_is_rectilinear &= path->stroke_is_rectilinear;
  536.         path->fill_maybe_region &= path->fill_is_rectilinear;
  537.         if (path->fill_maybe_region) {
  538.             path->fill_maybe_region = _cairo_fixed_is_integer (x) &&
  539.                                       _cairo_fixed_is_integer (y);
  540.         }
  541.         if (path->fill_is_empty) {
  542.             path->fill_is_empty = path->current_point.x == x &&
  543.                                   path->current_point.y == y;
  544.         }
  545.     }
  546.  
  547.     path->current_point = point;
  548.  
  549.     _cairo_box_add_point (&path->extents, &point);
  550.  
  551.     return _cairo_path_fixed_add (path, CAIRO_PATH_OP_LINE_TO, &point, 1);
  552. }
  553.  
  554. cairo_status_t
  555. _cairo_path_fixed_rel_line_to (cairo_path_fixed_t *path,
  556.                                cairo_fixed_t       dx,
  557.                                cairo_fixed_t       dy)
  558. {
  559.     if (unlikely (! path->has_current_point))
  560.         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
  561.  
  562.     return _cairo_path_fixed_line_to (path,
  563.                                       path->current_point.x + dx,
  564.                                       path->current_point.y + dy);
  565. }
  566.  
  567. cairo_status_t
  568. _cairo_path_fixed_curve_to (cairo_path_fixed_t  *path,
  569.                             cairo_fixed_t x0, cairo_fixed_t y0,
  570.                             cairo_fixed_t x1, cairo_fixed_t y1,
  571.                             cairo_fixed_t x2, cairo_fixed_t y2)
  572. {
  573.     cairo_status_t status;
  574.     cairo_point_t point[3];
  575.  
  576.     /* If this curves does not move, replace it with a line-to.
  577.      * This frequently happens with rounded-rectangles and r==0.
  578.     */
  579.     if (path->current_point.x == x2 && path->current_point.y == y2) {
  580.         if (x1 == x2 && x0 == x2 && y1 == y2 && y0 == y2)
  581.             return _cairo_path_fixed_line_to (path, x2, y2);
  582.  
  583.         /* We may want to check for the absence of a cusp, in which case
  584.          * we can also replace the curve-to with a line-to.
  585.          */
  586.     }
  587.  
  588.     /* make sure subpaths are started properly */
  589.     if (! path->has_current_point) {
  590.         status = _cairo_path_fixed_move_to (path, x0, y0);
  591.         assert (status == CAIRO_STATUS_SUCCESS);
  592.     }
  593.  
  594.     status = _cairo_path_fixed_move_to_apply (path);
  595.     if (unlikely (status))
  596.         return status;
  597.  
  598.     /* If the previous op was a degenerate LINE_TO, drop it. */
  599.     if (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO) {
  600.         const cairo_point_t *p;
  601.  
  602.         p = _cairo_path_fixed_penultimate_point (path);
  603.         if (p->x == path->current_point.x && p->y == path->current_point.y) {
  604.             /* previous line element was degenerate, replace */
  605.             _cairo_path_fixed_drop_line_to (path);
  606.         }
  607.     }
  608.  
  609.     point[0].x = x0; point[0].y = y0;
  610.     point[1].x = x1; point[1].y = y1;
  611.     point[2].x = x2; point[2].y = y2;
  612.  
  613.     _cairo_box_add_curve_to (&path->extents, &path->current_point,
  614.                              &point[0], &point[1], &point[2]);
  615.  
  616.     path->current_point = point[2];
  617.     path->has_curve_to = TRUE;
  618.     path->stroke_is_rectilinear = FALSE;
  619.     path->fill_is_rectilinear = FALSE;
  620.     path->fill_maybe_region = FALSE;
  621.     path->fill_is_empty = FALSE;
  622.  
  623.     return _cairo_path_fixed_add (path, CAIRO_PATH_OP_CURVE_TO, point, 3);
  624. }
  625.  
  626. cairo_status_t
  627. _cairo_path_fixed_rel_curve_to (cairo_path_fixed_t *path,
  628.                                 cairo_fixed_t dx0, cairo_fixed_t dy0,
  629.                                 cairo_fixed_t dx1, cairo_fixed_t dy1,
  630.                                 cairo_fixed_t dx2, cairo_fixed_t dy2)
  631. {
  632.     if (unlikely (! path->has_current_point))
  633.         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
  634.  
  635.     return _cairo_path_fixed_curve_to (path,
  636.                                        path->current_point.x + dx0,
  637.                                        path->current_point.y + dy0,
  638.  
  639.                                        path->current_point.x + dx1,
  640.                                        path->current_point.y + dy1,
  641.  
  642.                                        path->current_point.x + dx2,
  643.                                        path->current_point.y + dy2);
  644. }
  645.  
  646. cairo_status_t
  647. _cairo_path_fixed_close_path (cairo_path_fixed_t *path)
  648. {
  649.     cairo_status_t status;
  650.  
  651.     if (! path->has_current_point)
  652.         return CAIRO_STATUS_SUCCESS;
  653.  
  654.     /*
  655.      * Add a line_to, to compute flags and solve any degeneracy.
  656.      * It will be removed later (if it was actually added).
  657.      */
  658.     status = _cairo_path_fixed_line_to (path,
  659.                                         path->last_move_point.x,
  660.                                         path->last_move_point.y);
  661.     if (unlikely (status))
  662.         return status;
  663.  
  664.     /*
  665.      * If the command used to close the path is a line_to, drop it.
  666.      * We must check that last command is actually a line_to,
  667.      * because the path could have been closed with a curve_to (and
  668.      * the previous line_to not added as it would be degenerate).
  669.      */
  670.     if (_cairo_path_fixed_last_op (path) == CAIRO_PATH_OP_LINE_TO)
  671.             _cairo_path_fixed_drop_line_to (path);
  672.  
  673.     path->needs_move_to = TRUE; /* After close_path, add an implicit move_to */
  674.  
  675.     return _cairo_path_fixed_add (path, CAIRO_PATH_OP_CLOSE_PATH, NULL, 0);
  676. }
  677.  
  678. cairo_bool_t
  679. _cairo_path_fixed_get_current_point (cairo_path_fixed_t *path,
  680.                                      cairo_fixed_t      *x,
  681.                                      cairo_fixed_t      *y)
  682. {
  683.     if (! path->has_current_point)
  684.         return FALSE;
  685.  
  686.     *x = path->current_point.x;
  687.     *y = path->current_point.y;
  688.  
  689.     return TRUE;
  690. }
  691.  
  692. static cairo_status_t
  693. _cairo_path_fixed_add (cairo_path_fixed_t   *path,
  694.                        cairo_path_op_t       op,
  695.                        const cairo_point_t  *points,
  696.                        int                   num_points)
  697. {
  698.     cairo_path_buf_t *buf = cairo_path_tail (path);
  699.  
  700.     if (buf->num_ops + 1 > buf->size_ops ||
  701.         buf->num_points + num_points > buf->size_points)
  702.     {
  703.         buf = _cairo_path_buf_create (buf->num_ops * 2, buf->num_points * 2);
  704.         if (unlikely (buf == NULL))
  705.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  706.  
  707.         _cairo_path_fixed_add_buf (path, buf);
  708.     }
  709.  
  710.     if (WATCH_PATH) {
  711.         const char *op_str[] = {
  712.             "move-to",
  713.             "line-to",
  714.             "curve-to",
  715.             "close-path",
  716.         };
  717.         char buf[1024];
  718.         int len = 0;
  719.         int i;
  720.  
  721.         len += snprintf (buf + len, sizeof (buf), "[");
  722.         for (i = 0; i < num_points; i++) {
  723.             if (i != 0)
  724.                 len += snprintf (buf + len, sizeof (buf), " ");
  725.             len += snprintf (buf + len, sizeof (buf), "(%f, %f)",
  726.                              _cairo_fixed_to_double (points[i].x),
  727.                              _cairo_fixed_to_double (points[i].y));
  728.         }
  729.         len += snprintf (buf + len, sizeof (buf), "]");
  730.  
  731. #define STRINGIFYFLAG(x)  (path->x ? #x " " : "")
  732.         fprintf (stderr,
  733.                  "_cairo_path_fixed_add (%s, %s) [%s%s%s%s%s%s%s%s]\n",
  734.                  op_str[(int) op], buf,
  735.                  STRINGIFYFLAG(has_current_point),
  736.                  STRINGIFYFLAG(needs_move_to),
  737.                  STRINGIFYFLAG(has_extents),
  738.                  STRINGIFYFLAG(has_curve_to),
  739.                  STRINGIFYFLAG(stroke_is_rectilinear),
  740.                  STRINGIFYFLAG(fill_is_rectilinear),
  741.                  STRINGIFYFLAG(fill_is_empty),
  742.                  STRINGIFYFLAG(fill_maybe_region)
  743.                  );
  744. #undef STRINGIFYFLAG
  745.     }
  746.  
  747.     _cairo_path_buf_add_op (buf, op);
  748.     _cairo_path_buf_add_points (buf, points, num_points);
  749.  
  750.     return CAIRO_STATUS_SUCCESS;
  751. }
  752.  
  753. static void
  754. _cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
  755.                            cairo_path_buf_t   *buf)
  756. {
  757.     cairo_list_add_tail (&buf->link, &cairo_path_head (path)->link);
  758. }
  759.  
  760. COMPILE_TIME_ASSERT (sizeof (cairo_path_op_t) == 1);
  761. static cairo_path_buf_t *
  762. _cairo_path_buf_create (int size_ops, int size_points)
  763. {
  764.     cairo_path_buf_t *buf;
  765.  
  766.     /* adjust size_ops to ensure that buf->points is naturally aligned */
  767.     size_ops += sizeof (double) - ((sizeof (cairo_path_buf_t) + size_ops) % sizeof (double));
  768.     buf = _cairo_malloc_ab_plus_c (size_points, sizeof (cairo_point_t), size_ops + sizeof (cairo_path_buf_t));
  769.     if (buf) {
  770.         buf->num_ops = 0;
  771.         buf->num_points = 0;
  772.         buf->size_ops = size_ops;
  773.         buf->size_points = size_points;
  774.  
  775.         buf->op = (cairo_path_op_t *) (buf + 1);
  776.         buf->points = (cairo_point_t *) (buf->op + size_ops);
  777.     }
  778.  
  779.     return buf;
  780. }
  781.  
  782. static void
  783. _cairo_path_buf_destroy (cairo_path_buf_t *buf)
  784. {
  785.     free (buf);
  786. }
  787.  
  788. static void
  789. _cairo_path_buf_add_op (cairo_path_buf_t *buf,
  790.                         cairo_path_op_t   op)
  791. {
  792.     buf->op[buf->num_ops++] = op;
  793. }
  794.  
  795. static void
  796. _cairo_path_buf_add_points (cairo_path_buf_t       *buf,
  797.                             const cairo_point_t    *points,
  798.                             int                     num_points)
  799. {
  800.     if (num_points == 0)
  801.         return;
  802.  
  803.     memcpy (buf->points + buf->num_points,
  804.             points,
  805.             sizeof (points[0]) * num_points);
  806.     buf->num_points += num_points;
  807. }
  808.  
  809. cairo_status_t
  810. _cairo_path_fixed_interpret (const cairo_path_fixed_t           *path,
  811.                              cairo_path_fixed_move_to_func_t    *move_to,
  812.                              cairo_path_fixed_line_to_func_t    *line_to,
  813.                              cairo_path_fixed_curve_to_func_t   *curve_to,
  814.                              cairo_path_fixed_close_path_func_t *close_path,
  815.                              void                               *closure)
  816. {
  817.     const cairo_path_buf_t *buf;
  818.     cairo_status_t status;
  819.  
  820.     cairo_path_foreach_buf_start (buf, path) {
  821.         const cairo_point_t *points = buf->points;
  822.         unsigned int i;
  823.  
  824.         for (i = 0; i < buf->num_ops; i++) {
  825.             switch (buf->op[i]) {
  826.             case CAIRO_PATH_OP_MOVE_TO:
  827.                 status = (*move_to) (closure, &points[0]);
  828.                 points += 1;
  829.                 break;
  830.             case CAIRO_PATH_OP_LINE_TO:
  831.                 status = (*line_to) (closure, &points[0]);
  832.                 points += 1;
  833.                 break;
  834.             case CAIRO_PATH_OP_CURVE_TO:
  835.                 status = (*curve_to) (closure, &points[0], &points[1], &points[2]);
  836.                 points += 3;
  837.                 break;
  838.             default:
  839.                 ASSERT_NOT_REACHED;
  840.             case CAIRO_PATH_OP_CLOSE_PATH:
  841.                 status = (*close_path) (closure);
  842.                 break;
  843.             }
  844.  
  845.             if (unlikely (status))
  846.                 return status;
  847.         }
  848.     } cairo_path_foreach_buf_end (buf, path);
  849.  
  850.     return CAIRO_STATUS_SUCCESS;
  851. }
  852.  
  853. typedef struct _cairo_path_fixed_append_closure {
  854.     cairo_point_t           offset;
  855.     cairo_path_fixed_t      *path;
  856. } cairo_path_fixed_append_closure_t;
  857.  
  858. static cairo_status_t
  859. _append_move_to (void            *abstract_closure,
  860.                  const cairo_point_t  *point)
  861. {
  862.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  863.  
  864.     return _cairo_path_fixed_move_to (closure->path,
  865.                                       point->x + closure->offset.x,
  866.                                       point->y + closure->offset.y);
  867. }
  868.  
  869. static cairo_status_t
  870. _append_line_to (void            *abstract_closure,
  871.                  const cairo_point_t *point)
  872. {
  873.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  874.  
  875.     return _cairo_path_fixed_line_to (closure->path,
  876.                                       point->x + closure->offset.x,
  877.                                       point->y + closure->offset.y);
  878. }
  879.  
  880. static cairo_status_t
  881. _append_curve_to (void    *abstract_closure,
  882.                   const cairo_point_t *p0,
  883.                   const cairo_point_t *p1,
  884.                   const cairo_point_t *p2)
  885. {
  886.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  887.  
  888.     return _cairo_path_fixed_curve_to (closure->path,
  889.                                        p0->x + closure->offset.x,
  890.                                        p0->y + closure->offset.y,
  891.                                        p1->x + closure->offset.x,
  892.                                        p1->y + closure->offset.y,
  893.                                        p2->x + closure->offset.x,
  894.                                        p2->y + closure->offset.y);
  895. }
  896.  
  897. static cairo_status_t
  898. _append_close_path (void *abstract_closure)
  899. {
  900.     cairo_path_fixed_append_closure_t   *closure = abstract_closure;
  901.  
  902.     return _cairo_path_fixed_close_path (closure->path);
  903. }
  904.  
  905. cairo_status_t
  906. _cairo_path_fixed_append (cairo_path_fixed_t                *path,
  907.                           const cairo_path_fixed_t          *other,
  908.                           cairo_fixed_t                      tx,
  909.                           cairo_fixed_t                      ty)
  910. {
  911.     cairo_path_fixed_append_closure_t closure;
  912.  
  913.     closure.path = path;
  914.     closure.offset.x = tx;
  915.     closure.offset.y = ty;
  916.  
  917.     return _cairo_path_fixed_interpret (other,
  918.                                         _append_move_to,
  919.                                         _append_line_to,
  920.                                         _append_curve_to,
  921.                                         _append_close_path,
  922.                                         &closure);
  923. }
  924.  
  925. static void
  926. _cairo_path_fixed_offset_and_scale (cairo_path_fixed_t *path,
  927.                                     cairo_fixed_t offx,
  928.                                     cairo_fixed_t offy,
  929.                                     cairo_fixed_t scalex,
  930.                                     cairo_fixed_t scaley)
  931. {
  932.     cairo_path_buf_t *buf;
  933.     unsigned int i;
  934.  
  935.     if (scalex == CAIRO_FIXED_ONE && scaley == CAIRO_FIXED_ONE) {
  936.         _cairo_path_fixed_translate (path, offx, offy);
  937.         return;
  938.     }
  939.  
  940.     path->last_move_point.x = _cairo_fixed_mul (scalex, path->last_move_point.x) + offx;
  941.     path->last_move_point.y = _cairo_fixed_mul (scaley, path->last_move_point.y) + offy;
  942.     path->current_point.x   = _cairo_fixed_mul (scalex, path->current_point.x) + offx;
  943.     path->current_point.y   = _cairo_fixed_mul (scaley, path->current_point.y) + offy;
  944.  
  945.     path->fill_maybe_region = TRUE;
  946.  
  947.     cairo_path_foreach_buf_start (buf, path) {
  948.          for (i = 0; i < buf->num_points; i++) {
  949.              if (scalex != CAIRO_FIXED_ONE)
  950.                  buf->points[i].x = _cairo_fixed_mul (buf->points[i].x, scalex);
  951.              buf->points[i].x += offx;
  952.  
  953.              if (scaley != CAIRO_FIXED_ONE)
  954.                  buf->points[i].y = _cairo_fixed_mul (buf->points[i].y, scaley);
  955.              buf->points[i].y += offy;
  956.  
  957.             if (path->fill_maybe_region) {
  958.                 path->fill_maybe_region = _cairo_fixed_is_integer (buf->points[i].x) &&
  959.                                           _cairo_fixed_is_integer (buf->points[i].y);
  960.             }
  961.          }
  962.     } cairo_path_foreach_buf_end (buf, path);
  963.  
  964.     path->fill_maybe_region &= path->fill_is_rectilinear;
  965.  
  966.     path->extents.p1.x = _cairo_fixed_mul (scalex, path->extents.p1.x) + offx;
  967.     path->extents.p2.x = _cairo_fixed_mul (scalex, path->extents.p2.x) + offx;
  968.     if (scalex < 0) {
  969.         cairo_fixed_t t = path->extents.p1.x;
  970.         path->extents.p1.x = path->extents.p2.x;
  971.         path->extents.p2.x = t;
  972.     }
  973.  
  974.     path->extents.p1.y = _cairo_fixed_mul (scaley, path->extents.p1.y) + offy;
  975.     path->extents.p2.y = _cairo_fixed_mul (scaley, path->extents.p2.y) + offy;
  976.     if (scaley < 0) {
  977.         cairo_fixed_t t = path->extents.p1.y;
  978.         path->extents.p1.y = path->extents.p2.y;
  979.         path->extents.p2.y = t;
  980.     }
  981. }
  982.  
  983. void
  984. _cairo_path_fixed_translate (cairo_path_fixed_t *path,
  985.                              cairo_fixed_t offx,
  986.                              cairo_fixed_t offy)
  987. {
  988.     cairo_path_buf_t *buf;
  989.     unsigned int i;
  990.  
  991.     if (offx == 0 && offy == 0)
  992.         return;
  993.  
  994.     path->last_move_point.x += offx;
  995.     path->last_move_point.y += offy;
  996.     path->current_point.x += offx;
  997.     path->current_point.y += offy;
  998.  
  999.     path->fill_maybe_region = TRUE;
  1000.  
  1001.     cairo_path_foreach_buf_start (buf, path) {
  1002.         for (i = 0; i < buf->num_points; i++) {
  1003.             buf->points[i].x += offx;
  1004.             buf->points[i].y += offy;
  1005.  
  1006.             if (path->fill_maybe_region) {
  1007.                 path->fill_maybe_region = _cairo_fixed_is_integer (buf->points[i].x) &&
  1008.                                           _cairo_fixed_is_integer (buf->points[i].y);
  1009.             }
  1010.          }
  1011.     } cairo_path_foreach_buf_end (buf, path);
  1012.  
  1013.     path->fill_maybe_region &= path->fill_is_rectilinear;
  1014.  
  1015.     path->extents.p1.x += offx;
  1016.     path->extents.p1.y += offy;
  1017.     path->extents.p2.x += offx;
  1018.     path->extents.p2.y += offy;
  1019. }
  1020.  
  1021.  
  1022. static inline void
  1023. _cairo_path_fixed_transform_point (cairo_point_t *p,
  1024.                                    const cairo_matrix_t *matrix)
  1025. {
  1026.     double dx, dy;
  1027.  
  1028.     dx = _cairo_fixed_to_double (p->x);
  1029.     dy = _cairo_fixed_to_double (p->y);
  1030.     cairo_matrix_transform_point (matrix, &dx, &dy);
  1031.     p->x = _cairo_fixed_from_double (dx);
  1032.     p->y = _cairo_fixed_from_double (dy);
  1033. }
  1034.  
  1035. /**
  1036.  * _cairo_path_fixed_transform:
  1037.  * @path: a #cairo_path_fixed_t to be transformed
  1038.  * @matrix: a #cairo_matrix_t
  1039.  *
  1040.  * Transform the fixed-point path according to the given matrix.
  1041.  * There is a fast path for the case where @matrix has no rotation
  1042.  * or shear.
  1043.  **/
  1044. void
  1045. _cairo_path_fixed_transform (cairo_path_fixed_t *path,
  1046.                              const cairo_matrix_t     *matrix)
  1047. {
  1048.     cairo_box_t extents;
  1049.     cairo_point_t point;
  1050.     cairo_path_buf_t *buf;
  1051.     unsigned int i;
  1052.  
  1053.     if (matrix->yx == 0.0 && matrix->xy == 0.0) {
  1054.         /* Fast path for the common case of scale+transform */
  1055.         _cairo_path_fixed_offset_and_scale (path,
  1056.                                             _cairo_fixed_from_double (matrix->x0),
  1057.                                             _cairo_fixed_from_double (matrix->y0),
  1058.                                             _cairo_fixed_from_double (matrix->xx),
  1059.                                             _cairo_fixed_from_double (matrix->yy));
  1060.         return;
  1061.     }
  1062.  
  1063.     _cairo_path_fixed_transform_point (&path->last_move_point, matrix);
  1064.     _cairo_path_fixed_transform_point (&path->current_point, matrix);
  1065.  
  1066.     buf = cairo_path_head (path);
  1067.     if (buf->num_points == 0)
  1068.         return;
  1069.  
  1070.     extents = path->extents;
  1071.     point = buf->points[0];
  1072.     _cairo_path_fixed_transform_point (&point, matrix);
  1073.     _cairo_box_set (&path->extents, &point, &point);
  1074.  
  1075.     cairo_path_foreach_buf_start (buf, path) {
  1076.         for (i = 0; i < buf->num_points; i++) {
  1077.             _cairo_path_fixed_transform_point (&buf->points[i], matrix);
  1078.             _cairo_box_add_point (&path->extents, &buf->points[i]);
  1079.         }
  1080.     } cairo_path_foreach_buf_end (buf, path);
  1081.  
  1082.     if (path->has_curve_to) {
  1083.         cairo_bool_t is_tight;
  1084.  
  1085.         _cairo_matrix_transform_bounding_box_fixed (matrix, &extents, &is_tight);
  1086.         if (!is_tight) {
  1087.             cairo_bool_t has_extents;
  1088.  
  1089.             has_extents = _cairo_path_bounder_extents (path, &extents);
  1090.             assert (has_extents);
  1091.         }
  1092.         path->extents = extents;
  1093.     }
  1094.  
  1095.     /* flags might become more strict than needed */
  1096.     path->stroke_is_rectilinear = FALSE;
  1097.     path->fill_is_rectilinear = FALSE;
  1098.     path->fill_is_empty = FALSE;
  1099.     path->fill_maybe_region = FALSE;
  1100. }
  1101.  
  1102. /* Closure for path flattening */
  1103. typedef struct cairo_path_flattener {
  1104.     double tolerance;
  1105.     cairo_point_t current_point;
  1106.     cairo_path_fixed_move_to_func_t     *move_to;
  1107.     cairo_path_fixed_line_to_func_t     *line_to;
  1108.     cairo_path_fixed_close_path_func_t  *close_path;
  1109.     void *closure;
  1110. } cpf_t;
  1111.  
  1112. static cairo_status_t
  1113. _cpf_move_to (void *closure,
  1114.               const cairo_point_t *point)
  1115. {
  1116.     cpf_t *cpf = closure;
  1117.  
  1118.     cpf->current_point = *point;
  1119.  
  1120.     return cpf->move_to (cpf->closure, point);
  1121. }
  1122.  
  1123. static cairo_status_t
  1124. _cpf_line_to (void *closure,
  1125.               const cairo_point_t *point)
  1126. {
  1127.     cpf_t *cpf = closure;
  1128.  
  1129.     cpf->current_point = *point;
  1130.  
  1131.     return cpf->line_to (cpf->closure, point);
  1132. }
  1133.  
  1134. static cairo_status_t
  1135. _cpf_curve_to (void             *closure,
  1136.                const cairo_point_t      *p1,
  1137.                const cairo_point_t      *p2,
  1138.                const cairo_point_t      *p3)
  1139. {
  1140.     cpf_t *cpf = closure;
  1141.     cairo_spline_t spline;
  1142.  
  1143.     cairo_point_t *p0 = &cpf->current_point;
  1144.  
  1145.     if (! _cairo_spline_init (&spline,
  1146.                               (cairo_spline_add_point_func_t)cpf->line_to,
  1147.                               cpf->closure,
  1148.                               p0, p1, p2, p3))
  1149.     {
  1150.         return _cpf_line_to (closure, p3);
  1151.     }
  1152.  
  1153.     cpf->current_point = *p3;
  1154.  
  1155.     return _cairo_spline_decompose (&spline, cpf->tolerance);
  1156. }
  1157.  
  1158. static cairo_status_t
  1159. _cpf_close_path (void *closure)
  1160. {
  1161.     cpf_t *cpf = closure;
  1162.  
  1163.     return cpf->close_path (cpf->closure);
  1164. }
  1165.  
  1166. cairo_status_t
  1167. _cairo_path_fixed_interpret_flat (const cairo_path_fixed_t              *path,
  1168.                                   cairo_path_fixed_move_to_func_t       *move_to,
  1169.                                   cairo_path_fixed_line_to_func_t       *line_to,
  1170.                                   cairo_path_fixed_close_path_func_t    *close_path,
  1171.                                   void                                  *closure,
  1172.                                   double                                tolerance)
  1173. {
  1174.     cpf_t flattener;
  1175.  
  1176.     if (! path->has_curve_to) {
  1177.         return _cairo_path_fixed_interpret (path,
  1178.                                             move_to,
  1179.                                             line_to,
  1180.                                             NULL,
  1181.                                             close_path,
  1182.                                             closure);
  1183.     }
  1184.  
  1185.     flattener.tolerance = tolerance;
  1186.     flattener.move_to = move_to;
  1187.     flattener.line_to = line_to;
  1188.     flattener.close_path = close_path;
  1189.     flattener.closure = closure;
  1190.     return _cairo_path_fixed_interpret (path,
  1191.                                         _cpf_move_to,
  1192.                                         _cpf_line_to,
  1193.                                         _cpf_curve_to,
  1194.                                         _cpf_close_path,
  1195.                                         &flattener);
  1196. }
  1197.  
  1198. static inline void
  1199. _canonical_box (cairo_box_t *box,
  1200.                 const cairo_point_t *p1,
  1201.                 const cairo_point_t *p2)
  1202. {
  1203.     if (p1->x <= p2->x) {
  1204.         box->p1.x = p1->x;
  1205.         box->p2.x = p2->x;
  1206.     } else {
  1207.         box->p1.x = p2->x;
  1208.         box->p2.x = p1->x;
  1209.     }
  1210.  
  1211.     if (p1->y <= p2->y) {
  1212.         box->p1.y = p1->y;
  1213.         box->p2.y = p2->y;
  1214.     } else {
  1215.         box->p1.y = p2->y;
  1216.         box->p2.y = p1->y;
  1217.     }
  1218. }
  1219.  
  1220. static inline cairo_bool_t
  1221. _path_is_quad (const cairo_path_fixed_t *path)
  1222. {
  1223.     const cairo_path_buf_t *buf = cairo_path_head (path);
  1224.  
  1225.     /* Do we have the right number of ops? */
  1226.     if (buf->num_ops < 4 || buf->num_ops > 6)
  1227.         return FALSE;
  1228.  
  1229.     /* Check whether the ops are those that would be used for a rectangle */
  1230.     if (buf->op[0] != CAIRO_PATH_OP_MOVE_TO ||
  1231.         buf->op[1] != CAIRO_PATH_OP_LINE_TO ||
  1232.         buf->op[2] != CAIRO_PATH_OP_LINE_TO ||
  1233.         buf->op[3] != CAIRO_PATH_OP_LINE_TO)
  1234.     {
  1235.         return FALSE;
  1236.     }
  1237.  
  1238.     /* we accept an implicit close for filled paths */
  1239.     if (buf->num_ops > 4) {
  1240.         /* Now, there are choices. The rectangle might end with a LINE_TO
  1241.          * (to the original point), but this isn't required. If it
  1242.          * doesn't, then it must end with a CLOSE_PATH. */
  1243.         if (buf->op[4] == CAIRO_PATH_OP_LINE_TO) {
  1244.             if (buf->points[4].x != buf->points[0].x ||
  1245.                 buf->points[4].y != buf->points[0].y)
  1246.                 return FALSE;
  1247.         } else if (buf->op[4] != CAIRO_PATH_OP_CLOSE_PATH) {
  1248.             return FALSE;
  1249.         }
  1250.  
  1251.         if (buf->num_ops == 6) {
  1252.             /* A trailing CLOSE_PATH or MOVE_TO is ok */
  1253.             if (buf->op[5] != CAIRO_PATH_OP_MOVE_TO &&
  1254.                 buf->op[5] != CAIRO_PATH_OP_CLOSE_PATH)
  1255.                 return FALSE;
  1256.         }
  1257.     }
  1258.  
  1259.     return TRUE;
  1260. }
  1261.  
  1262. static inline cairo_bool_t
  1263. _points_form_rect (const cairo_point_t *points)
  1264. {
  1265.     if (points[0].y == points[1].y &&
  1266.         points[1].x == points[2].x &&
  1267.         points[2].y == points[3].y &&
  1268.         points[3].x == points[0].x)
  1269.         return TRUE;
  1270.     if (points[0].x == points[1].x &&
  1271.         points[1].y == points[2].y &&
  1272.         points[2].x == points[3].x &&
  1273.         points[3].y == points[0].y)
  1274.         return TRUE;
  1275.     return FALSE;
  1276. }
  1277.  
  1278. /*
  1279.  * Check whether the given path contains a single rectangle.
  1280.  */
  1281. cairo_bool_t
  1282. _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
  1283.                           cairo_box_t *box)
  1284. {
  1285.     const cairo_path_buf_t *buf;
  1286.  
  1287.     if (! path->fill_is_rectilinear)
  1288.         return FALSE;
  1289.  
  1290.     if (! _path_is_quad (path))
  1291.         return FALSE;
  1292.  
  1293.     buf = cairo_path_head (path);
  1294.     if (_points_form_rect (buf->points)) {
  1295.         _canonical_box (box, &buf->points[0], &buf->points[2]);
  1296.         return TRUE;
  1297.     }
  1298.  
  1299.     return FALSE;
  1300. }
  1301.  
  1302. /* Determine whether two lines A->B and C->D intersect based on the
  1303.  * algorithm described here: http://paulbourke.net/geometry/pointlineplane/ */
  1304. static inline cairo_bool_t
  1305. _lines_intersect_or_are_coincident (cairo_point_t a,
  1306.                                     cairo_point_t b,
  1307.                                     cairo_point_t c,
  1308.                                     cairo_point_t d)
  1309. {
  1310.     cairo_int64_t numerator_a, numerator_b, denominator;
  1311.     cairo_bool_t denominator_negative;
  1312.  
  1313.     denominator = _cairo_int64_sub (_cairo_int32x32_64_mul (d.y - c.y, b.x - a.x),
  1314.                                     _cairo_int32x32_64_mul (d.x - c.x, b.y - a.y));
  1315.     numerator_a = _cairo_int64_sub (_cairo_int32x32_64_mul (d.x - c.x, a.y - c.y),
  1316.                                     _cairo_int32x32_64_mul (d.y - c.y, a.x - c.x));
  1317.     numerator_b = _cairo_int64_sub (_cairo_int32x32_64_mul (b.x - a.x, a.y - c.y),
  1318.                                     _cairo_int32x32_64_mul (b.y - a.y, a.x - c.x));
  1319.  
  1320.     if (_cairo_int64_is_zero (denominator)) {
  1321.         /* If the denominator and numerators are both zero,
  1322.          * the lines are coincident. */
  1323.         if (_cairo_int64_is_zero (numerator_a) && _cairo_int64_is_zero (numerator_b))
  1324.             return TRUE;
  1325.  
  1326.         /* Otherwise, a zero denominator indicates the lines are
  1327.         *  parallel and never intersect. */
  1328.         return FALSE;
  1329.     }
  1330.  
  1331.     /* The lines intersect if both quotients are between 0 and 1 (exclusive). */
  1332.  
  1333.      /* We first test whether either quotient is a negative number. */
  1334.     denominator_negative = _cairo_int64_negative (denominator);
  1335.     if (_cairo_int64_negative (numerator_a) ^ denominator_negative)
  1336.         return FALSE;
  1337.     if (_cairo_int64_negative (numerator_b) ^ denominator_negative)
  1338.         return FALSE;
  1339.  
  1340.     /* A zero quotient indicates an "intersection" at an endpoint, which
  1341.      * we aren't considering a true intersection. */
  1342.     if (_cairo_int64_is_zero (numerator_a) || _cairo_int64_is_zero (numerator_b))
  1343.         return FALSE;
  1344.  
  1345.     /* If the absolute value of the numerator is larger than or equal to the
  1346.      * denominator the result of the division would be greater than or equal
  1347.      * to one. */
  1348.     if (! denominator_negative) {
  1349.         if (! _cairo_int64_lt (numerator_a, denominator) ||
  1350.             ! _cairo_int64_lt (numerator_b, denominator))
  1351.             return FALSE;
  1352.     } else {
  1353.         if (! _cairo_int64_lt (denominator, numerator_a) ||
  1354.             ! _cairo_int64_lt (denominator, numerator_b))
  1355.             return FALSE;
  1356.     }
  1357.  
  1358.     return TRUE;
  1359. }
  1360.  
  1361. cairo_bool_t
  1362. _cairo_path_fixed_is_simple_quad (const cairo_path_fixed_t *path)
  1363. {
  1364.     const cairo_point_t *points;
  1365.  
  1366.     if (! _path_is_quad (path))
  1367.         return FALSE;
  1368.  
  1369.     points = cairo_path_head (path)->points;
  1370.     if (_points_form_rect (points))
  1371.         return TRUE;
  1372.  
  1373.     if (_lines_intersect_or_are_coincident (points[0], points[1],
  1374.                                             points[3], points[2]))
  1375.         return FALSE;
  1376.  
  1377.     if (_lines_intersect_or_are_coincident (points[0], points[3],
  1378.                                             points[1], points[2]))
  1379.         return FALSE;
  1380.  
  1381.     return TRUE;
  1382. }
  1383.  
  1384. cairo_bool_t
  1385. _cairo_path_fixed_is_stroke_box (const cairo_path_fixed_t *path,
  1386.                                  cairo_box_t *box)
  1387. {
  1388.     const cairo_path_buf_t *buf = cairo_path_head (path);
  1389.  
  1390.     if (! path->fill_is_rectilinear)
  1391.         return FALSE;
  1392.  
  1393.     /* Do we have the right number of ops? */
  1394.     if (buf->num_ops != 5)
  1395.         return FALSE;
  1396.  
  1397.     /* Check whether the ops are those that would be used for a rectangle */
  1398.     if (buf->op[0] != CAIRO_PATH_OP_MOVE_TO ||
  1399.         buf->op[1] != CAIRO_PATH_OP_LINE_TO ||
  1400.         buf->op[2] != CAIRO_PATH_OP_LINE_TO ||
  1401.         buf->op[3] != CAIRO_PATH_OP_LINE_TO ||
  1402.         buf->op[4] != CAIRO_PATH_OP_CLOSE_PATH)
  1403.     {
  1404.         return FALSE;
  1405.     }
  1406.  
  1407.     /* Ok, we may have a box, if the points line up */
  1408.     if (buf->points[0].y == buf->points[1].y &&
  1409.         buf->points[1].x == buf->points[2].x &&
  1410.         buf->points[2].y == buf->points[3].y &&
  1411.         buf->points[3].x == buf->points[0].x)
  1412.     {
  1413.         _canonical_box (box, &buf->points[0], &buf->points[2]);
  1414.         return TRUE;
  1415.     }
  1416.  
  1417.     if (buf->points[0].x == buf->points[1].x &&
  1418.         buf->points[1].y == buf->points[2].y &&
  1419.         buf->points[2].x == buf->points[3].x &&
  1420.         buf->points[3].y == buf->points[0].y)
  1421.     {
  1422.         _canonical_box (box, &buf->points[0], &buf->points[2]);
  1423.         return TRUE;
  1424.     }
  1425.  
  1426.     return FALSE;
  1427. }
  1428.  
  1429. /*
  1430.  * Check whether the given path contains a single rectangle
  1431.  * that is logically equivalent to:
  1432.  * <informalexample><programlisting>
  1433.  *   cairo_move_to (cr, x, y);
  1434.  *   cairo_rel_line_to (cr, width, 0);
  1435.  *   cairo_rel_line_to (cr, 0, height);
  1436.  *   cairo_rel_line_to (cr, -width, 0);
  1437.  *   cairo_close_path (cr);
  1438.  * </programlisting></informalexample>
  1439.  */
  1440. cairo_bool_t
  1441. _cairo_path_fixed_is_rectangle (const cairo_path_fixed_t *path,
  1442.                                 cairo_box_t        *box)
  1443. {
  1444.     const cairo_path_buf_t *buf;
  1445.  
  1446.     if (! _cairo_path_fixed_is_box (path, box))
  1447.         return FALSE;
  1448.  
  1449.     /* This check is valid because the current implementation of
  1450.      * _cairo_path_fixed_is_box () only accepts rectangles like:
  1451.      * move,line,line,line[,line|close[,close|move]]. */
  1452.     buf = cairo_path_head (path);
  1453.     if (buf->num_ops > 4)
  1454.         return TRUE;
  1455.  
  1456.     return FALSE;
  1457. }
  1458.  
  1459. void
  1460. _cairo_path_fixed_iter_init (cairo_path_fixed_iter_t *iter,
  1461.                              const cairo_path_fixed_t *path)
  1462. {
  1463.     iter->first = iter->buf = cairo_path_head (path);
  1464.     iter->n_op = 0;
  1465.     iter->n_point = 0;
  1466. }
  1467.  
  1468. static cairo_bool_t
  1469. _cairo_path_fixed_iter_next_op (cairo_path_fixed_iter_t *iter)
  1470. {
  1471.     if (++iter->n_op >= iter->buf->num_ops) {
  1472.         iter->buf = cairo_path_buf_next (iter->buf);
  1473.         if (iter->buf == iter->first) {
  1474.             iter->buf = NULL;
  1475.             return FALSE;
  1476.         }
  1477.  
  1478.         iter->n_op = 0;
  1479.         iter->n_point = 0;
  1480.     }
  1481.  
  1482.     return TRUE;
  1483. }
  1484.  
  1485. cairo_bool_t
  1486. _cairo_path_fixed_iter_is_fill_box (cairo_path_fixed_iter_t *_iter,
  1487.                                     cairo_box_t *box)
  1488. {
  1489.     cairo_point_t points[5];
  1490.     cairo_path_fixed_iter_t iter;
  1491.  
  1492.     if (_iter->buf == NULL)
  1493.         return FALSE;
  1494.  
  1495.     iter = *_iter;
  1496.  
  1497.     if (iter.n_op == iter.buf->num_ops && ! _cairo_path_fixed_iter_next_op (&iter))
  1498.         return FALSE;
  1499.  
  1500.     /* Check whether the ops are those that would be used for a rectangle */
  1501.     if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_MOVE_TO)
  1502.         return FALSE;
  1503.     points[0] = iter.buf->points[iter.n_point++];
  1504.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1505.         return FALSE;
  1506.  
  1507.     if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
  1508.         return FALSE;
  1509.     points[1] = iter.buf->points[iter.n_point++];
  1510.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1511.         return FALSE;
  1512.  
  1513.     /* a horizontal/vertical closed line is also a degenerate rectangle */
  1514.     switch (iter.buf->op[iter.n_op]) {
  1515.     case CAIRO_PATH_OP_CLOSE_PATH:
  1516.         _cairo_path_fixed_iter_next_op (&iter);
  1517.     case CAIRO_PATH_OP_MOVE_TO: /* implicit close */
  1518.         box->p1 = box->p2 = points[0];
  1519.         *_iter = iter;
  1520.         return TRUE;
  1521.     default:
  1522.         return FALSE;
  1523.     case CAIRO_PATH_OP_LINE_TO:
  1524.         break;
  1525.     }
  1526.  
  1527.     points[2] = iter.buf->points[iter.n_point++];
  1528.     if (! _cairo_path_fixed_iter_next_op (&iter))
  1529.         return FALSE;
  1530.  
  1531.     if (iter.buf->op[iter.n_op] != CAIRO_PATH_OP_LINE_TO)
  1532.         return FALSE;
  1533.     points[3] = iter.buf->points[iter.n_point++];
  1534.  
  1535.     /* Now, there are choices. The rectangle might end with a LINE_TO
  1536.      * (to the original point), but this isn't required. If it
  1537.      * doesn't, then it must end with a CLOSE_PATH (which may be implicit). */
  1538.     if (! _cairo_path_fixed_iter_next_op (&iter)) {
  1539.         /* implicit close due to fill */
  1540.     } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_LINE_TO) {
  1541.         points[4] = iter.buf->points[iter.n_point++];
  1542.         if (points[4].x != points[0].x || points[4].y != points[0].y)
  1543.             return FALSE;
  1544.         _cairo_path_fixed_iter_next_op (&iter);
  1545.     } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_CLOSE_PATH) {
  1546.         _cairo_path_fixed_iter_next_op (&iter);
  1547.     } else if (iter.buf->op[iter.n_op] == CAIRO_PATH_OP_MOVE_TO) {
  1548.         /* implicit close-path due to new-sub-path */
  1549.     } else {
  1550.         return FALSE;
  1551.     }
  1552.  
  1553.     /* Ok, we may have a box, if the points line up */
  1554.     if (points[0].y == points[1].y &&
  1555.         points[1].x == points[2].x &&
  1556.         points[2].y == points[3].y &&
  1557.         points[3].x == points[0].x)
  1558.     {
  1559.         box->p1 = points[0];
  1560.         box->p2 = points[2];
  1561.         *_iter = iter;
  1562.         return TRUE;
  1563.     }
  1564.  
  1565.     if (points[0].x == points[1].x &&
  1566.         points[1].y == points[2].y &&
  1567.         points[2].x == points[3].x &&
  1568.         points[3].y == points[0].y)
  1569.     {
  1570.         box->p1 = points[1];
  1571.         box->p2 = points[3];
  1572.         *_iter = iter;
  1573.         return TRUE;
  1574.     }
  1575.  
  1576.     return FALSE;
  1577. }
  1578.  
  1579. cairo_bool_t
  1580. _cairo_path_fixed_iter_at_end (const cairo_path_fixed_iter_t *iter)
  1581. {
  1582.     if (iter->buf == NULL)
  1583.         return TRUE;
  1584.  
  1585.     return iter->n_op == iter->buf->num_ops;
  1586. }
  1587.