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