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