Coverage Report

Created: 2025-07-07 10:01

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