src/cairo-path-fixed.c

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