Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/source/fitz/path.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 // Copyright (C) 2004-2025 Artifex Software, Inc.
2 //
3 // This file is part of MuPDF.
4 //
5 // MuPDF is free software: you can redistribute it and/or modify it under the
6 // terms of the GNU Affero General Public License as published by the Free
7 // Software Foundation, either version 3 of the License, or (at your option)
8 // any later version.
9 //
10 // MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Affero General Public License
16 // along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
17 //
18 // Alternative licensing terms are available from the licensor.
19 // For commercial licensing, see <https://www.artifex.com/> or contact
20 // Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
21 // CA 94129, USA, for further information.
22
23 #include "mupdf/fitz.h"
24
25 #include <string.h>
26 #include <assert.h>
27
28 // Thoughts for further optimisations:
29 // All paths start with MoveTo. We could probably avoid most cases where
30 // we store that. The next thing after a close must be a move.
31 // Commands are MOVE, LINE, HORIZ, VERT, DEGEN, CURVE, CURVEV, CURVEY, QUAD, RECT.
32 // We'd need to drop 2 to get us down to 3 bits.
33 // Commands can be followed by CLOSE. Use 1 bit for close.
34 // PDF 'RECT' implies close according to the spec, but I suspect
35 // we can ignore this as filling closes implicitly.
36 // We use a single bit in the path header to tell us whether we have
37 // a trailing move. Trailing moves can always be stripped when path
38 // construction completes.
39
40 typedef enum
41 {
42 FZ_MOVETO = 'M',
43 FZ_LINETO = 'L',
44 FZ_DEGENLINETO = 'D',
45 FZ_CURVETO = 'C',
46 FZ_CURVETOV = 'V',
47 FZ_CURVETOY = 'Y',
48 FZ_HORIZTO = 'H',
49 FZ_VERTTO = 'I',
50 FZ_QUADTO = 'Q',
51 FZ_RECTTO = 'R',
52 FZ_MOVETOCLOSE = 'm',
53 FZ_LINETOCLOSE = 'l',
54 FZ_DEGENLINETOCLOSE = 'd',
55 FZ_CURVETOCLOSE = 'c',
56 FZ_CURVETOVCLOSE = 'v',
57 FZ_CURVETOYCLOSE = 'y',
58 FZ_HORIZTOCLOSE = 'h',
59 FZ_VERTTOCLOSE = 'i',
60 FZ_QUADTOCLOSE = 'q',
61 } fz_path_item_kind;
62
63 struct fz_path
64 {
65 int8_t refs;
66 uint8_t packed;
67 int cmd_len, cmd_cap;
68 unsigned char *cmds;
69 int coord_len, coord_cap;
70 float *coords;
71 fz_point current;
72 fz_point begin;
73 };
74
75 typedef struct
76 {
77 int8_t refs;
78 uint8_t packed;
79 uint8_t coord_len;
80 uint8_t cmd_len;
81 } fz_packed_path;
82
83 /*
84 Paths are created UNPACKED. That means we have a fz_path
85 structure with coords and cmds pointing to malloced blocks.
86
87 After they have been completely constructed, callers may choose
88 to 'pack' them into some target block of memory. If if coord_len
89 and cmd_len are both < 256, then they are PACKED_FLAT into an
90 fz_packed_path with the coords and cmds in the bytes afterwards,
91 all inside the target block. If they cannot be accommodated in
92 that way, then they are PACKED_OPEN, where an fz_path is put
93 into the target block, and cmds and coords remain pointers to
94 allocated blocks.
95 */
96 enum
97 {
98 FZ_PATH_UNPACKED = 0,
99 FZ_PATH_PACKED_FLAT = 1,
100 FZ_PATH_PACKED_OPEN = 2
101 };
102
103 #define LAST_CMD(path) ((path)->cmd_len > 0 ? (path)->cmds[(path)->cmd_len-1] : 0)
104
105 fz_path *
106 fz_new_path(fz_context *ctx)
107 {
108 fz_path *path;
109
110 path = fz_malloc_struct(ctx, fz_path);
111 path->refs = 1;
112 path->packed = FZ_PATH_UNPACKED;
113 path->current.x = 0;
114 path->current.y = 0;
115 path->begin.x = 0;
116 path->begin.y = 0;
117
118 return path;
119 }
120
121 /*
122 Take an additional reference to
123 a path.
124
125 No modifications should be carried out on a path
126 to which more than one reference is held, as
127 this can cause race conditions.
128 */
129 fz_path *
130 fz_keep_path(fz_context *ctx, const fz_path *pathc)
131 {
132 fz_path *path = (fz_path *)pathc; /* Explicit cast away of const */
133 int trimmable = 0;
134
135 if (path == NULL)
136 return NULL;
137 fz_lock(ctx, FZ_LOCK_ALLOC);
138 /* Technically, we should only access ->refs with the lock held,
139 * so do that here. We can't actually do the trimming here, because
140 * to do so would do memory accesses with the ALLOC lock held. */
141 if (path->refs == 1 && path->packed == FZ_PATH_UNPACKED)
142 trimmable = 1;
143 fz_keep_imp8_locked(ctx, path, &path->refs);
144 fz_unlock(ctx, FZ_LOCK_ALLOC);
145
146 /* This is thread safe, because we know that the only person
147 * holding a reference to this thread is us. */
148 if (trimmable)
149 fz_trim_path(ctx, path);
150
151 return path;
152 }
153
154 void
155 fz_drop_path(fz_context *ctx, const fz_path *pathc)
156 {
157 fz_path *path = (fz_path *)pathc; /* Explicit cast away of const */
158
159 if (fz_drop_imp8(ctx, path, &path->refs))
160 {
161 if (path->packed != FZ_PATH_PACKED_FLAT)
162 {
163 fz_free(ctx, path->cmds);
164 fz_free(ctx, path->coords);
165 }
166 if (path->packed == FZ_PATH_UNPACKED)
167 fz_free(ctx, path);
168 }
169 }
170
171 int fz_packed_path_size(const fz_path *path)
172 {
173 switch (path->packed)
174 {
175 case FZ_PATH_UNPACKED:
176 if (path->cmd_len > 255 || path->coord_len > 255)
177 return sizeof(fz_path);
178 return sizeof(fz_packed_path) + sizeof(float) * path->coord_len + sizeof(uint8_t) * path->cmd_len;
179 case FZ_PATH_PACKED_OPEN:
180 return sizeof(fz_path);
181 case FZ_PATH_PACKED_FLAT:
182 {
183 fz_packed_path *pack = (fz_packed_path *)path;
184 return sizeof(fz_packed_path) + sizeof(float) * pack->coord_len + sizeof(uint8_t) * pack->cmd_len;
185 }
186 default:
187 assert("This never happens" == NULL);
188 return 0;
189 }
190 }
191
192 size_t
193 fz_pack_path(fz_context *ctx, uint8_t *pack_, const fz_path *path)
194 {
195 uint8_t *ptr;
196 size_t size;
197
198 if (path->packed == FZ_PATH_PACKED_FLAT)
199 {
200 fz_packed_path *pack = (fz_packed_path *)path;
201 fz_packed_path *out = (fz_packed_path *)pack_;
202 size = sizeof(fz_packed_path) + sizeof(float) * pack->coord_len + sizeof(uint8_t) * pack->cmd_len;
203
204 if (out)
205 {
206 out->refs = 1;
207 out->packed = FZ_PATH_PACKED_FLAT;
208 out->coord_len = pack->coord_len;
209 out->cmd_len = pack->cmd_len;
210 memcpy(&out[1], &pack[1], size - sizeof(*out));
211 }
212 return size;
213 }
214
215 size = sizeof(fz_packed_path) + sizeof(float) * path->coord_len + sizeof(uint8_t) * path->cmd_len;
216
217 /* If the path can't be packed flat, then pack it open */
218 if (path->cmd_len > 255 || path->coord_len > 255)
219 {
220 fz_path *pack = (fz_path *)pack_;
221
222 if (pack != NULL)
223 {
224 pack->refs = 1;
225 pack->packed = FZ_PATH_PACKED_OPEN;
226 pack->current.x = 0;
227 pack->current.y = 0;
228 pack->begin.x = 0;
229 pack->begin.y = 0;
230 pack->coord_cap = path->coord_len;
231 pack->coord_len = path->coord_len;
232 pack->cmd_cap = path->cmd_len;
233 pack->cmd_len = path->cmd_len;
234 pack->coords = Memento_label(fz_malloc_array(ctx, path->coord_len, float), "path_packed_coords");
235 fz_try(ctx)
236 {
237 pack->cmds = Memento_label(fz_malloc_array(ctx, path->cmd_len, uint8_t), "path_packed_cmds");
238 }
239 fz_catch(ctx)
240 {
241 fz_free(ctx, pack->coords);
242 fz_rethrow(ctx);
243 }
244 memcpy(pack->coords, path->coords, sizeof(float) * path->coord_len);
245 memcpy(pack->cmds, path->cmds, sizeof(uint8_t) * path->cmd_len);
246 }
247 return sizeof(fz_path);
248 }
249 else
250 {
251 fz_packed_path *pack = (fz_packed_path *)pack_;
252
253 if (pack != NULL)
254 {
255 pack->refs = 1;
256 pack->packed = FZ_PATH_PACKED_FLAT;
257 pack->cmd_len = path->cmd_len;
258 pack->coord_len = path->coord_len;
259 ptr = (uint8_t *)&pack[1];
260 memcpy(ptr, path->coords, sizeof(float) * path->coord_len);
261 ptr += sizeof(float) * path->coord_len;
262 memcpy(ptr, path->cmds, sizeof(uint8_t) * path->cmd_len);
263 }
264
265 return size;
266 }
267 }
268
269 static void
270 push_cmd(fz_context *ctx, fz_path *path, int cmd)
271 {
272 if (path->refs != 1)
273 fz_throw(ctx, FZ_ERROR_ARGUMENT, "cannot modify shared paths");
274
275 if (path->cmd_len + 1 >= path->cmd_cap)
276 {
277 int new_cmd_cap = fz_maxi(16, path->cmd_cap * 2);
278 path->cmds = fz_realloc_array(ctx, path->cmds, new_cmd_cap, unsigned char);
279 path->cmd_cap = new_cmd_cap;
280 }
281
282 path->cmds[path->cmd_len++] = cmd;
283 }
284
285 static void
286 push_coord(fz_context *ctx, fz_path *path, float x, float y)
287 {
288 if (path->coord_len + 2 >= path->coord_cap)
289 {
290 int new_coord_cap = fz_maxi(32, path->coord_cap * 2);
291 path->coords = fz_realloc_array(ctx, path->coords, new_coord_cap, float);
292 path->coord_cap = new_coord_cap;
293 }
294
295 path->coords[path->coord_len++] = x;
296 path->coords[path->coord_len++] = y;
297
298 path->current.x = x;
299 path->current.y = y;
300 }
301
302 static void
303 push_ord(fz_context *ctx, fz_path *path, float xy, int isx)
304 {
305 if (path->coord_len + 1 >= path->coord_cap)
306 {
307 int new_coord_cap = fz_maxi(32, path->coord_cap * 2);
308 path->coords = fz_realloc_array(ctx, path->coords, new_coord_cap, float);
309 path->coord_cap = new_coord_cap;
310 }
311
312 path->coords[path->coord_len++] = xy;
313
314 if (isx)
315 path->current.x = xy;
316 else
317 path->current.y = xy;
318 }
319
320 fz_point
321 fz_currentpoint(fz_context *ctx, fz_path *path)
322 {
323 return path->current;
324 }
325
326 void
327 fz_moveto(fz_context *ctx, fz_path *path, float x, float y)
328 {
329 if (path->packed)
330 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
331
332 if (path->cmd_len > 0 && LAST_CMD(path) == FZ_MOVETO)
333 {
334 /* Collapse moveto followed by moveto. */
335 path->coords[path->coord_len-2] = x;
336 path->coords[path->coord_len-1] = y;
337 path->current.x = x;
338 path->current.y = y;
339 path->begin = path->current;
340 return;
341 }
342
343 push_cmd(ctx, path, FZ_MOVETO);
344 push_coord(ctx, path, x, y);
345
346 path->begin = path->current;
347 }
348
349 void
350 fz_lineto(fz_context *ctx, fz_path *path, float x, float y)
351 {
352 float x0, y0;
353
354 if (path->packed)
355 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
356
357 x0 = path->current.x;
358 y0 = path->current.y;
359
360 if (path->cmd_len == 0)
361 {
362 fz_warn(ctx, "lineto with no current point");
363 return;
364 }
365
366 /* (Anything other than MoveTo) followed by (LineTo the same place) is a nop */
367 if (LAST_CMD(path) != FZ_MOVETO && x0 == x && y0 == y)
368 return;
369
370 if (x0 == x)
371 {
372 if (y0 == y)
373 {
374 if (LAST_CMD(path) != FZ_MOVETO)
375 return;
376 push_cmd(ctx, path, FZ_DEGENLINETO);
377 }
378 else
379 {
380 push_cmd(ctx, path, FZ_VERTTO);
381 push_ord(ctx, path, y, 0);
382 }
383 }
384 else if (y0 == y)
385 {
386 push_cmd(ctx, path, FZ_HORIZTO);
387 push_ord(ctx, path, x, 1);
388 }
389 else
390 {
391 push_cmd(ctx, path, FZ_LINETO);
392 push_coord(ctx, path, x, y);
393 }
394 }
395
396 void
397 fz_curveto(fz_context *ctx, fz_path *path,
398 float x1, float y1,
399 float x2, float y2,
400 float x3, float y3)
401 {
402 float x0, y0;
403
404 if (path->packed)
405 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
406
407 x0 = path->current.x;
408 y0 = path->current.y;
409
410 if (path->cmd_len == 0)
411 {
412 fz_warn(ctx, "curveto with no current point");
413 return;
414 }
415
416 /* Check for degenerate cases: */
417 if (x0 == x1 && y0 == y1)
418 {
419 if (x2 == x3 && y2 == y3)
420 {
421 /* If (x1,y1)==(x2,y2) and prev wasn't a moveto, then skip */
422 if (x1 == x2 && y1 == y2 && LAST_CMD(path) != FZ_MOVETO)
423 return;
424 /* Otherwise a line will suffice */
425 fz_lineto(ctx, path, x3, y3);
426 }
427 else if (x1 == x2 && y1 == y2)
428 {
429 /* A line will suffice */
430 fz_lineto(ctx, path, x3, y3);
431 }
432 else
433 fz_curvetov(ctx, path, x2, y2, x3, y3);
434 return;
435 }
436 else if (x2 == x3 && y2 == y3)
437 {
438 if (x1 == x2 && y1 == y2)
439 {
440 /* A line will suffice */
441 fz_lineto(ctx, path, x3, y3);
442 }
443 else
444 fz_curvetoy(ctx, path, x1, y1, x3, y3);
445 return;
446 }
447
448 push_cmd(ctx, path, FZ_CURVETO);
449 push_coord(ctx, path, x1, y1);
450 push_coord(ctx, path, x2, y2);
451 push_coord(ctx, path, x3, y3);
452 }
453
454 void
455 fz_quadto(fz_context *ctx, fz_path *path,
456 float x1, float y1,
457 float x2, float y2)
458 {
459 float x0, y0;
460
461 if (path->packed)
462 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
463
464 x0 = path->current.x;
465 y0 = path->current.y;
466
467 if (path->cmd_len == 0)
468 {
469 fz_warn(ctx, "quadto with no current point");
470 return;
471 }
472
473 /* Check for degenerate cases: */
474 if ((x0 == x1 && y0 == y1) || (x1 == x2 && y1 == y2))
475 {
476 if (x0 == x2 && y0 == y2 && LAST_CMD(path) != FZ_MOVETO)
477 return;
478 /* A line will suffice */
479 fz_lineto(ctx, path, x2, y2);
480 return;
481 }
482
483 push_cmd(ctx, path, FZ_QUADTO);
484 push_coord(ctx, path, x1, y1);
485 push_coord(ctx, path, x2, y2);
486 }
487
488 void
489 fz_curvetov(fz_context *ctx, fz_path *path, float x2, float y2, float x3, float y3)
490 {
491 float x0, y0;
492
493 if (path->packed)
494 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
495
496 x0 = path->current.x;
497 y0 = path->current.y;
498
499 if (path->cmd_len == 0)
500 {
501 fz_warn(ctx, "curveto with no current point");
502 return;
503 }
504
505 /* Check for degenerate cases: */
506 if (x2 == x3 && y2 == y3)
507 {
508 /* If (x0,y0)==(x2,y2) and prev wasn't a moveto, then skip */
509 if (x0 == x2 && y0 == y2 && LAST_CMD(path) != FZ_MOVETO)
510 return;
511 /* Otherwise a line will suffice */
512 fz_lineto(ctx, path, x3, y3);
513 }
514 else if (x0 == x2 && y0 == y2)
515 {
516 /* A line will suffice */
517 fz_lineto(ctx, path, x3, y3);
518 }
519
520 push_cmd(ctx, path, FZ_CURVETOV);
521 push_coord(ctx, path, x2, y2);
522 push_coord(ctx, path, x3, y3);
523 }
524
525 void
526 fz_curvetoy(fz_context *ctx, fz_path *path, float x1, float y1, float x3, float y3)
527 {
528 float x0, y0;
529
530 if (path->packed)
531 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
532
533 x0 = path->current.x;
534 y0 = path->current.y;
535
536 if (path->cmd_len == 0)
537 {
538 fz_warn(ctx, "curveto with no current point");
539 return;
540 }
541
542 /* Check for degenerate cases: */
543 if (x1 == x3 && y1 == y3)
544 {
545 /* If (x0,y0)==(x1,y1) and prev wasn't a moveto, then skip */
546 if (x0 == x1 && y0 == y1 && LAST_CMD(path) != FZ_MOVETO)
547 return;
548 /* Otherwise a line will suffice */
549 fz_lineto(ctx, path, x3, y3);
550 }
551
552 push_cmd(ctx, path, FZ_CURVETOY);
553 push_coord(ctx, path, x1, y1);
554 push_coord(ctx, path, x3, y3);
555 }
556
557 void
558 fz_closepath(fz_context *ctx, fz_path *path)
559 {
560 uint8_t rep;
561
562 if (path->packed)
563 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
564
565 if (path->cmd_len == 0)
566 {
567 fz_warn(ctx, "closepath with no current point");
568 return;
569 }
570
571 switch(LAST_CMD(path))
572 {
573 case FZ_MOVETO:
574 rep = FZ_MOVETOCLOSE;
575 break;
576 case FZ_LINETO:
577 rep = FZ_LINETOCLOSE;
578 break;
579 case FZ_DEGENLINETO:
580 rep = FZ_DEGENLINETOCLOSE;
581 break;
582 case FZ_CURVETO:
583 rep = FZ_CURVETOCLOSE;
584 break;
585 case FZ_CURVETOV:
586 rep = FZ_CURVETOVCLOSE;
587 break;
588 case FZ_CURVETOY:
589 rep = FZ_CURVETOYCLOSE;
590 break;
591 case FZ_HORIZTO:
592 rep = FZ_HORIZTOCLOSE;
593 break;
594 case FZ_VERTTO:
595 rep = FZ_VERTTOCLOSE;
596 break;
597 case FZ_QUADTO:
598 rep = FZ_QUADTOCLOSE;
599 break;
600 case FZ_RECTTO:
601 /* RectTo implies close */
602 return;
603 case FZ_MOVETOCLOSE:
604 case FZ_LINETOCLOSE:
605 case FZ_DEGENLINETOCLOSE:
606 case FZ_CURVETOCLOSE:
607 case FZ_CURVETOVCLOSE:
608 case FZ_CURVETOYCLOSE:
609 case FZ_HORIZTOCLOSE:
610 case FZ_VERTTOCLOSE:
611 case FZ_QUADTOCLOSE:
612 /* CLOSE following a CLOSE is a NOP */
613 return;
614 default: /* default never happens */
615 case 0:
616 /* Closing an empty path is a NOP */
617 return;
618 }
619
620 path->cmds[path->cmd_len-1] = rep;
621
622 path->current = path->begin;
623 }
624
625 void
626 fz_rectto(fz_context *ctx, fz_path *path, float x1, float y1, float x2, float y2)
627 {
628 if (path->packed)
629 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot modify a packed path");
630
631 if (path->cmd_len > 0 && LAST_CMD(path) == FZ_MOVETO)
632 {
633 /* Collapse moveto followed by rectto. */
634 path->coord_len -= 2;
635 path->cmd_len--;
636 }
637
638 push_cmd(ctx, path, FZ_RECTTO);
639 push_coord(ctx, path, x1, y1);
640 push_coord(ctx, path, x2, y2);
641
642 path->current = path->begin;
643 }
644
645 static inline void bound_expand(fz_rect *r, fz_point p)
646 {
647 if (p.x < r->x0) r->x0 = p.x;
648 if (p.y < r->y0) r->y0 = p.y;
649 if (p.x > r->x1) r->x1 = p.x;
650 if (p.y > r->y1) r->y1 = p.y;
651 }
652
653 void fz_walk_path(fz_context *ctx, const fz_path *path, const fz_path_walker *proc, void *arg)
654 {
655 int i, k, cmd_len;
656 float x=0, y=0, sx=0, sy=0;
657 uint8_t *cmds;
658 float *coords;
659
660 switch (path->packed)
661 {
662 case FZ_PATH_UNPACKED:
663 case FZ_PATH_PACKED_OPEN:
664 cmd_len = path->cmd_len;
665 coords = path->coords;
666 cmds = path->cmds;
667 break;
668 case FZ_PATH_PACKED_FLAT:
669 cmd_len = ((fz_packed_path *)path)->cmd_len;
670 coords = (float *)&((fz_packed_path *)path)[1];
671 cmds = (uint8_t *)&coords[((fz_packed_path *)path)->coord_len];
672 break;
673 default:
674 assert("This never happens" == NULL);
675 return;
676 }
677
678 if (cmd_len == 0)
679 return;
680
681 for (k=0, i = 0; i < cmd_len; i++)
682 {
683 uint8_t cmd = cmds[i];
684
685 switch (cmd)
686 {
687 case FZ_CURVETO:
688 case FZ_CURVETOCLOSE:
689 proc->curveto(ctx, arg,
690 coords[k],
691 coords[k+1],
692 coords[k+2],
693 coords[k+3],
694 x = coords[k+4],
695 y = coords[k+5]);
696 k += 6;
697 if (cmd == FZ_CURVETOCLOSE)
698 {
699 if (proc->closepath)
700 proc->closepath(ctx, arg);
701 x = sx;
702 y = sy;
703 }
704 break;
705 case FZ_CURVETOV:
706 case FZ_CURVETOVCLOSE:
707 if (proc->curvetov)
708 proc->curvetov(ctx, arg,
709 coords[k],
710 coords[k+1],
711 x = coords[k+2],
712 y = coords[k+3]);
713 else
714 {
715 proc->curveto(ctx, arg,
716 x,
717 y,
718 coords[k],
719 coords[k+1],
720 coords[k+2],
721 coords[k+3]);
722 x = coords[k+2];
723 y = coords[k+3];
724 }
725 k += 4;
726 if (cmd == FZ_CURVETOVCLOSE)
727 {
728 if (proc->closepath)
729 proc->closepath(ctx, arg);
730 x = sx;
731 y = sy;
732 }
733 break;
734 case FZ_CURVETOY:
735 case FZ_CURVETOYCLOSE:
736 if (proc->curvetoy)
737 proc->curvetoy(ctx, arg,
738 coords[k],
739 coords[k+1],
740 x = coords[k+2],
741 y = coords[k+3]);
742 else
743 proc->curveto(ctx, arg,
744 coords[k],
745 coords[k+1],
746 coords[k+2],
747 coords[k+3],
748 x = coords[k+2],
749 y = coords[k+3]);
750 k += 4;
751 if (cmd == FZ_CURVETOYCLOSE)
752 {
753 if (proc->closepath)
754 proc->closepath(ctx, arg);
755 x = sx;
756 y = sy;
757 }
758 break;
759 case FZ_QUADTO:
760 case FZ_QUADTOCLOSE:
761 if (proc->quadto)
762 proc->quadto(ctx, arg,
763 coords[k],
764 coords[k+1],
765 x = coords[k+2],
766 y = coords[k+3]);
767 else
768 {
769 float c2x = coords[k] * 2;
770 float c2y = coords[k+1] * 2;
771 float c1x = (x + c2x) / 3;
772 float c1y = (y + c2y) / 3;
773 x = coords[k+2];
774 y = coords[k+3];
775 c2x = (c2x + x) / 3;
776 c2y = (c2y + y) / 3;
777
778 proc->curveto(ctx, arg,
779 c1x,
780 c1y,
781 c2x,
782 c2y,
783 x,
784 y);
785 }
786 k += 4;
787 if (cmd == FZ_QUADTOCLOSE)
788 {
789 if (proc->closepath)
790 proc->closepath(ctx, arg);
791 x = sx;
792 y = sy;
793 }
794 break;
795 case FZ_MOVETO:
796 case FZ_MOVETOCLOSE:
797 proc->moveto(ctx, arg,
798 x = coords[k],
799 y = coords[k+1]);
800 k += 2;
801 sx = x;
802 sy = y;
803 if (cmd == FZ_MOVETOCLOSE)
804 {
805 if (proc->closepath)
806 proc->closepath(ctx, arg);
807 x = sx;
808 y = sy;
809 }
810 break;
811 case FZ_LINETO:
812 case FZ_LINETOCLOSE:
813 proc->lineto(ctx, arg,
814 x = coords[k],
815 y = coords[k+1]);
816 k += 2;
817 if (cmd == FZ_LINETOCLOSE)
818 {
819 if (proc->closepath)
820 proc->closepath(ctx, arg);
821 x = sx;
822 y = sy;
823 }
824 break;
825 case FZ_HORIZTO:
826 case FZ_HORIZTOCLOSE:
827 proc->lineto(ctx, arg,
828 x = coords[k],
829 y);
830 k += 1;
831 if (cmd == FZ_HORIZTOCLOSE)
832 {
833 if (proc->closepath)
834 proc->closepath(ctx, arg);
835 x = sx;
836 y = sy;
837 }
838 break;
839 case FZ_VERTTO:
840 case FZ_VERTTOCLOSE:
841 proc->lineto(ctx, arg,
842 x,
843 y = coords[k]);
844 k += 1;
845 if (cmd == FZ_VERTTOCLOSE)
846 {
847 if (proc->closepath)
848 proc->closepath(ctx, arg);
849 x = sx;
850 y = sy;
851 }
852 break;
853 case FZ_DEGENLINETO:
854 case FZ_DEGENLINETOCLOSE:
855 proc->lineto(ctx, arg,
856 x,
857 y);
858 if (cmd == FZ_DEGENLINETOCLOSE)
859 {
860 if (proc->closepath)
861 proc->closepath(ctx, arg);
862 x = sx;
863 y = sy;
864 }
865 break;
866 case FZ_RECTTO:
867 if (proc->rectto)
868 {
869 proc->rectto(ctx, arg,
870 x = coords[k],
871 y = coords[k+1],
872 coords[k+2],
873 coords[k+3]);
874 }
875 else
876 {
877 proc->moveto(ctx, arg,
878 x = coords[k],
879 y = coords[k+1]);
880 proc->lineto(ctx, arg,
881 coords[k+2],
882 coords[k+1]);
883 proc->lineto(ctx, arg,
884 coords[k+2],
885 coords[k+3]);
886 proc->lineto(ctx, arg,
887 coords[k],
888 coords[k+3]);
889 if (proc->closepath)
890 proc->closepath(ctx, arg);
891 }
892 sx = x;
893 sy = y;
894 k += 4;
895 break;
896 }
897 }
898 }
899
900 /*
901 A couple of notes about the path bounding algorithm.
902
903 Firstly, we don't expand the bounds immediately on a move, because
904 a sequence of moves together will only actually use the last one,
905 and trailing moves are ignored. This is achieved using 'trailing_move'.
906
907 Secondly, we watch for paths that are entirely rectilinear (all segments
908 move left/right/up/down only, with no curves). Such "only_right_angles"
909 paths can be bounded with us ignoring any mitre limit. This is a really
910 common case that can otherwise bloats simple boxes far more than is
911 useful. This is particular annoying during table recognition!
912 */
913 typedef struct
914 {
915 fz_matrix ctm;
916 fz_rect rect;
917 fz_point move;
918 int trailing_move;
919 int first;
920 int only_right_angles;
921 fz_point prev;
922 } bound_path_arg;
923
924 static void
925 bound_moveto(fz_context *ctx, void *arg_, float x, float y)
926 {
927 bound_path_arg *arg = (bound_path_arg *)arg_;
928 arg->move = arg->prev = fz_transform_point_xy(x, y, arg->ctm);
929 arg->trailing_move = 1;
930 }
931
932 static inline int
933 eq0(float x)
934 {
935 return x >= -0.001 && x <= 0.001;
936 }
937
938 static void
939 bound_lineto(fz_context *ctx, void *arg_, float x, float y)
940 {
941 bound_path_arg *arg = (bound_path_arg *)arg_;
942 fz_point p = fz_transform_point_xy(x, y, arg->ctm);
943 if (arg->first)
944 {
945 arg->rect.x0 = arg->rect.x1 = p.x;
946 arg->rect.y0 = arg->rect.y1 = p.y;
947 arg->first = 0;
948 }
949 else
950 bound_expand(&arg->rect, p);
951 if (arg->trailing_move)
952 {
953 arg->trailing_move = 0;
954 bound_expand(&arg->rect, arg->move);
955 }
956 if (arg->only_right_angles && !eq0(arg->prev.x - p.x) && !eq0(arg->prev.y - p.y))
957 arg->only_right_angles = 0;
958 arg->prev = p;
959 }
960
961 static void
962 bound_curveto(fz_context *ctx, void *arg_, float x1, float y1, float x2, float y2, float x3, float y3)
963 {
964 bound_path_arg *arg = (bound_path_arg *)arg_;
965 fz_point p = fz_transform_point_xy(x1, y1, arg->ctm);
966 if (arg->first)
967 {
968 arg->rect.x0 = arg->rect.x1 = p.x;
969 arg->rect.y0 = arg->rect.y1 = p.y;
970 arg->first = 0;
971 }
972 else
973 bound_expand(&arg->rect, p);
974 bound_expand(&arg->rect, fz_transform_point_xy(x2, y2, arg->ctm));
975 bound_expand(&arg->rect, fz_transform_point_xy(x3, y3, arg->ctm));
976 if (arg->trailing_move)
977 {
978 arg->trailing_move = 0;
979 bound_expand(&arg->rect, arg->move);
980 }
981 arg->only_right_angles = 0;
982 arg->prev = p;
983 }
984
985 static const fz_path_walker bound_path_walker =
986 {
987 bound_moveto,
988 bound_lineto,
989 bound_curveto,
990 NULL
991 };
992
993 static fz_rect
994 adjust_rect_for_stroke(fz_context *ctx, fz_rect r, const fz_stroke_state *stroke, fz_matrix ctm, int no_mitre)
995 {
996 float expand;
997
998 if (!stroke)
999 return r;
1000
1001 expand = stroke->linewidth/2;
1002 if (expand == 0)
1003 expand = 0.5f;
1004 if (r.x1 == r.x0 || r.y1 == r.y0)
1005 {
1006 /* Mitring can't apply in this case. */
1007 }
1008 else if (!no_mitre && stroke->linejoin == FZ_LINEJOIN_MITER && stroke->miterlimit > 0.5f)
1009 {
1010 /* miter limit is expressed in terms of the linewidth, not half the line width. */
1011 expand *= stroke->miterlimit * 2;
1012 }
1013 else if (!no_mitre && stroke->linejoin == FZ_LINEJOIN_MITER_XPS && stroke->miterlimit > 1.0f)
1014 {
1015 /* for xps, miter limit is expressed in terms of half the linewidth. */
1016 expand *= stroke->miterlimit;
1017 }
1018
1019 expand *= fz_matrix_max_expansion(ctm);
1020
1021 r.x0 -= expand;
1022 r.y0 -= expand;
1023 r.x1 += expand;
1024 r.y1 += expand;
1025 return r;
1026 }
1027
1028 fz_rect
1029 fz_bound_path(fz_context *ctx, const fz_path *path, const fz_stroke_state *stroke, fz_matrix ctm)
1030 {
1031 bound_path_arg arg;
1032
1033 arg.ctm = ctm;
1034 arg.rect = fz_empty_rect;
1035 arg.trailing_move = 0;
1036 arg.first = 1;
1037 arg.only_right_angles = 1;
1038
1039 fz_walk_path(ctx, path, &bound_path_walker, &arg);
1040
1041 if (!arg.first && stroke)
1042 {
1043 arg.rect = adjust_rect_for_stroke(ctx, arg.rect, stroke, ctm, arg.only_right_angles);
1044 }
1045
1046 return arg.rect;
1047 }
1048
1049 fz_rect
1050 fz_adjust_rect_for_stroke(fz_context *ctx, fz_rect r, const fz_stroke_state *stroke, fz_matrix ctm)
1051 {
1052 return adjust_rect_for_stroke(ctx, r, stroke, ctm, 0);
1053 }
1054
1055 void
1056 fz_transform_path(fz_context *ctx, fz_path *path, fz_matrix ctm)
1057 {
1058 int i, k, n;
1059 fz_point p, p1, p2, p3, q, s;
1060
1061 if (path->packed)
1062 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Cannot transform a packed path");
1063
1064 if (ctm.b == 0 && ctm.c == 0)
1065 {
1066 /* Simple, in place transform */
1067 i = 0;
1068 k = 0;
1069 while (i < path->cmd_len)
1070 {
1071 uint8_t cmd = path->cmds[i];
1072
1073 switch (cmd)
1074 {
1075 case FZ_MOVETO:
1076 case FZ_LINETO:
1077 case FZ_MOVETOCLOSE:
1078 case FZ_LINETOCLOSE:
1079 n = 1;
1080 break;
1081 case FZ_DEGENLINETO:
1082 case FZ_DEGENLINETOCLOSE:
1083 n = 0;
1084 break;
1085 case FZ_CURVETO:
1086 case FZ_CURVETOCLOSE:
1087 n = 3;
1088 break;
1089 case FZ_RECTTO:
1090 s.x = path->coords[k];
1091 s.y = path->coords[k+1];
1092 n = 2;
1093 break;
1094 case FZ_CURVETOV:
1095 case FZ_CURVETOY:
1096 case FZ_QUADTO:
1097 case FZ_CURVETOVCLOSE:
1098 case FZ_CURVETOYCLOSE:
1099 case FZ_QUADTOCLOSE:
1100 n = 2;
1101 break;
1102 case FZ_HORIZTO:
1103 case FZ_HORIZTOCLOSE:
1104 q.x = path->coords[k];
1105 p = fz_transform_point(q, ctm);
1106 path->coords[k++] = p.x;
1107 n = 0;
1108 break;
1109 case FZ_VERTTO:
1110 case FZ_VERTTOCLOSE:
1111 q.y = path->coords[k];
1112 p = fz_transform_point(q, ctm);
1113 path->coords[k++] = p.y;
1114 n = 0;
1115 break;
1116 default:
1117 assert("Unknown path cmd" == NULL);
1118 }
1119 while (n > 0)
1120 {
1121 q.x = path->coords[k];
1122 q.y = path->coords[k+1];
1123 p = fz_transform_point(q, ctm);
1124 path->coords[k++] = p.x;
1125 path->coords[k++] = p.y;
1126 n--;
1127 }
1128 switch (cmd)
1129 {
1130 case FZ_MOVETO:
1131 case FZ_MOVETOCLOSE:
1132 s = q;
1133 break;
1134 case FZ_LINETOCLOSE:
1135 case FZ_DEGENLINETOCLOSE:
1136 case FZ_CURVETOCLOSE:
1137 case FZ_CURVETOVCLOSE:
1138 case FZ_CURVETOYCLOSE:
1139 case FZ_QUADTOCLOSE:
1140 case FZ_HORIZTOCLOSE:
1141 case FZ_VERTTOCLOSE:
1142 case FZ_RECTTO:
1143 q = s;
1144 break;
1145 }
1146 i++;
1147 }
1148 }
1149 else if (ctm.a == 0 && ctm.d == 0)
1150 {
1151 /* In place transform with command rewriting */
1152 i = 0;
1153 k = 0;
1154 while (i < path->cmd_len)
1155 {
1156 uint8_t cmd = path->cmds[i];
1157
1158 switch (cmd)
1159 {
1160 case FZ_MOVETO:
1161 case FZ_LINETO:
1162 case FZ_MOVETOCLOSE:
1163 case FZ_LINETOCLOSE:
1164 n = 1;
1165 break;
1166 case FZ_DEGENLINETO:
1167 case FZ_DEGENLINETOCLOSE:
1168 n = 0;
1169 break;
1170 case FZ_CURVETO:
1171 case FZ_CURVETOCLOSE:
1172 n = 3;
1173 break;
1174 case FZ_RECTTO:
1175 s.x = path->coords[k];
1176 s.y = path->coords[k+1];
1177 n = 2;
1178 break;
1179 case FZ_CURVETOV:
1180 case FZ_CURVETOY:
1181 case FZ_QUADTO:
1182 case FZ_CURVETOVCLOSE:
1183 case FZ_CURVETOYCLOSE:
1184 case FZ_QUADTOCLOSE:
1185 n = 2;
1186 break;
1187 case FZ_HORIZTO:
1188 q.x = path->coords[k];
1189 p = fz_transform_point(q, ctm);
1190 path->coords[k++] = p.y;
1191 path->cmds[i] = FZ_VERTTO;
1192 n = 0;
1193 break;
1194 case FZ_HORIZTOCLOSE:
1195 q.x = path->coords[k];
1196 p = fz_transform_point(q, ctm);
1197 path->coords[k++] = p.y;
1198 path->cmds[i] = FZ_VERTTOCLOSE;
1199 n = 0;
1200 break;
1201 case FZ_VERTTO:
1202 q.y = path->coords[k];
1203 p = fz_transform_point(q, ctm);
1204 path->coords[k++] = p.x;
1205 path->cmds[i] = FZ_HORIZTO;
1206 n = 0;
1207 break;
1208 case FZ_VERTTOCLOSE:
1209 q.y = path->coords[k];
1210 p = fz_transform_point(q, ctm);
1211 path->coords[k++] = p.x;
1212 path->cmds[i] = FZ_HORIZTOCLOSE;
1213 n = 0;
1214 break;
1215 default:
1216 assert("Unknown path cmd" == NULL);
1217 }
1218 while (n > 0)
1219 {
1220 q.x = path->coords[k];
1221 q.y = path->coords[k+1];
1222 p = fz_transform_point(q, ctm);
1223 path->coords[k++] = p.x;
1224 path->coords[k++] = p.y;
1225 n--;
1226 }
1227 switch (cmd)
1228 {
1229 case FZ_MOVETO:
1230 case FZ_MOVETOCLOSE:
1231 s = q;
1232 break;
1233 case FZ_LINETOCLOSE:
1234 case FZ_DEGENLINETOCLOSE:
1235 case FZ_CURVETOCLOSE:
1236 case FZ_CURVETOVCLOSE:
1237 case FZ_CURVETOYCLOSE:
1238 case FZ_QUADTOCLOSE:
1239 case FZ_HORIZTOCLOSE:
1240 case FZ_VERTTOCLOSE:
1241 case FZ_RECTTO:
1242 q = s;
1243 break;
1244 }
1245 i++;
1246 }
1247 }
1248 else
1249 {
1250 int extra_coord = 0;
1251 int extra_cmd = 0;
1252 int coord_read, coord_write, cmd_read, cmd_write;
1253
1254 /* General case. Have to allow for rects/horiz/verts
1255 * becoming non-rects/horiz/verts. */
1256 for (i = 0; i < path->cmd_len; i++)
1257 {
1258 uint8_t cmd = path->cmds[i];
1259 switch (cmd)
1260 {
1261 case FZ_HORIZTO:
1262 case FZ_VERTTO:
1263 case FZ_HORIZTOCLOSE:
1264 case FZ_VERTTOCLOSE:
1265 extra_coord += 1;
1266 break;
1267 case FZ_RECTTO:
1268 extra_coord += 2;
1269 extra_cmd += 3;
1270 break;
1271 default:
1272 /* Do nothing */
1273 break;
1274 }
1275 }
1276 if (path->cmd_len + extra_cmd < path->cmd_cap)
1277 {
1278 path->cmds = fz_realloc_array(ctx, path->cmds, path->cmd_len + extra_cmd, unsigned char);
1279 path->cmd_cap = path->cmd_len + extra_cmd;
1280 }
1281 if (path->coord_len + extra_coord < path->coord_cap)
1282 {
1283 path->coords = fz_realloc_array(ctx, path->coords, path->coord_len + extra_coord, float);
1284 path->coord_cap = path->coord_len + extra_coord;
1285 }
1286 memmove(path->cmds + extra_cmd, path->cmds, path->cmd_len * sizeof(unsigned char));
1287 path->cmd_len += extra_cmd;
1288 memmove(path->coords + extra_coord, path->coords, path->coord_len * sizeof(float));
1289 path->coord_len += extra_coord;
1290
1291 for (cmd_write = 0, cmd_read = extra_cmd, coord_write = 0, coord_read = extra_coord; cmd_read < path->cmd_len; i += 2)
1292 {
1293 uint8_t cmd = path->cmds[cmd_write++] = path->cmds[cmd_read++];
1294
1295 switch (cmd)
1296 {
1297 case FZ_MOVETO:
1298 case FZ_LINETO:
1299 case FZ_MOVETOCLOSE:
1300 case FZ_LINETOCLOSE:
1301 n = 1;
1302 break;
1303 case FZ_DEGENLINETO:
1304 case FZ_DEGENLINETOCLOSE:
1305 n = 0;
1306 break;
1307 case FZ_CURVETO:
1308 case FZ_CURVETOCLOSE:
1309 n = 3;
1310 break;
1311 case FZ_CURVETOV:
1312 case FZ_CURVETOY:
1313 case FZ_QUADTO:
1314 case FZ_CURVETOVCLOSE:
1315 case FZ_CURVETOYCLOSE:
1316 case FZ_QUADTOCLOSE:
1317 n = 2;
1318 break;
1319 case FZ_RECTTO:
1320 p.x = path->coords[coord_read++];
1321 p.y = path->coords[coord_read++];
1322 p2.x = path->coords[coord_read++];
1323 p2.y = path->coords[coord_read++];
1324 p1.x = p2.x;
1325 p1.y = p.y;
1326 p3.x = p.x;
1327 p3.y = p2.y;
1328 s = p;
1329 p = fz_transform_point(p, ctm);
1330 p1 = fz_transform_point(p1, ctm);
1331 p2 = fz_transform_point(p2, ctm);
1332 p3 = fz_transform_point(p3, ctm);
1333 path->coords[coord_write++] = p.x;
1334 path->coords[coord_write++] = p.y;
1335 path->coords[coord_write++] = p1.x;
1336 path->coords[coord_write++] = p1.y;
1337 path->coords[coord_write++] = p2.x;
1338 path->coords[coord_write++] = p2.y;
1339 path->coords[coord_write++] = p3.x;
1340 path->coords[coord_write++] = p3.y;
1341 path->cmds[cmd_write-1] = FZ_MOVETO;
1342 path->cmds[cmd_write++] = FZ_LINETO;
1343 path->cmds[cmd_write++] = FZ_LINETO;
1344 path->cmds[cmd_write++] = FZ_LINETOCLOSE;
1345 n = 0;
1346 break;
1347 case FZ_HORIZTO:
1348 q.x = path->coords[coord_read++];
1349 p = fz_transform_point(q, ctm);
1350 path->coords[coord_write++] = p.x;
1351 path->coords[coord_write++] = p.y;
1352 path->cmds[cmd_write-1] = FZ_LINETO;
1353 n = 0;
1354 break;
1355 case FZ_HORIZTOCLOSE:
1356 p.x = path->coords[coord_read++];
1357 p.y = q.y;
1358 p = fz_transform_point(p, ctm);
1359 path->coords[coord_write++] = p.x;
1360 path->coords[coord_write++] = p.y;
1361 path->cmds[cmd_write-1] = FZ_LINETOCLOSE;
1362 q = s;
1363 n = 0;
1364 break;
1365 case FZ_VERTTO:
1366 q.y = path->coords[coord_read++];
1367 p = fz_transform_point(q, ctm);
1368 path->coords[coord_write++] = p.x;
1369 path->coords[coord_write++] = p.y;
1370 path->cmds[cmd_write-1] = FZ_LINETO;
1371 n = 0;
1372 break;
1373 case FZ_VERTTOCLOSE:
1374 p.x = q.x;
1375 p.y = path->coords[coord_read++];
1376 p = fz_transform_point(p, ctm);
1377 path->coords[coord_write++] = p.x;
1378 path->coords[coord_write++] = p.y;
1379 path->cmds[cmd_write-1] = FZ_LINETOCLOSE;
1380 q = s;
1381 n = 0;
1382 break;
1383 default:
1384 assert("Unknown path cmd" == NULL);
1385 }
1386 while (n > 0)
1387 {
1388 q.x = path->coords[coord_read++];
1389 q.y = path->coords[coord_read++];
1390 p = fz_transform_point(q, ctm);
1391 path->coords[coord_write++] = p.x;
1392 path->coords[coord_write++] = p.y;
1393 n--;
1394 }
1395 switch (cmd)
1396 {
1397 case FZ_MOVETO:
1398 case FZ_MOVETOCLOSE:
1399 s = q;
1400 break;
1401 case FZ_LINETOCLOSE:
1402 case FZ_DEGENLINETOCLOSE:
1403 case FZ_CURVETOCLOSE:
1404 case FZ_CURVETOYCLOSE:
1405 case FZ_CURVETOVCLOSE:
1406 case FZ_QUADTOCLOSE:
1407 case FZ_HORIZTOCLOSE:
1408 case FZ_VERTTOCLOSE:
1409 case FZ_RECTTO:
1410 q = s;
1411 break;
1412 }
1413 }
1414 }
1415 }
1416
1417 void fz_trim_path(fz_context *ctx, fz_path *path)
1418 {
1419 if (path->packed)
1420 fz_throw(ctx, FZ_ERROR_ARGUMENT, "Can't trim a packed path");
1421 if (path->cmd_cap > path->cmd_len)
1422 {
1423 path->cmds = fz_realloc_array(ctx, path->cmds, path->cmd_len, unsigned char);
1424 path->cmd_cap = path->cmd_len;
1425 }
1426 if (path->coord_cap > path->coord_len)
1427 {
1428 path->coords = fz_realloc_array(ctx, path->coords, path->coord_len, float);
1429 path->coord_cap = path->coord_len;
1430 }
1431 }
1432
1433 const fz_stroke_state fz_default_stroke_state = {
1434 -2, /* -2 is the magic number we use when we have stroke states stored on the stack */
1435 FZ_LINECAP_BUTT, FZ_LINECAP_BUTT, FZ_LINECAP_BUTT,
1436 FZ_LINEJOIN_MITER,
1437 1, 10,
1438 0, 0, { 0 }
1439 };
1440
1441 fz_stroke_state *
1442 fz_keep_stroke_state(fz_context *ctx, const fz_stroke_state *strokec)
1443 {
1444 fz_stroke_state *stroke = (fz_stroke_state *)strokec; /* Explicit cast away of const */
1445
1446 if (!stroke)
1447 return NULL;
1448
1449 /* -2 is the magic number we use when we have stroke states stored on the stack */
1450 if (stroke->refs == -2)
1451 return fz_clone_stroke_state(ctx, stroke);
1452
1453 return fz_keep_imp(ctx, stroke, &stroke->refs);
1454 }
1455
1456 int
1457 fz_stroke_state_eq(fz_context *ctx, const fz_stroke_state *a, const fz_stroke_state *b)
1458 {
1459 int i;
1460
1461 if (a == NULL && b == NULL) return 1;
1462
1463 if (a == NULL && b != NULL) return 0;
1464 if (a != NULL && b == NULL) return 0;
1465
1466 if (a->start_cap != b->start_cap) return 0;
1467 if (a->dash_cap != b->dash_cap) return 0;
1468 if (a->end_cap != b->end_cap) return 0;
1469 if (a->linejoin != b->linejoin) return 0;
1470 if (a->linewidth != b->linewidth) return 0;
1471 if (a->miterlimit != b->miterlimit) return 0;
1472 if (a->dash_phase != b->dash_phase) return 0;
1473 if (a->dash_len != b->dash_len) return 0;
1474
1475 for (i = 0; i < a->dash_len; i++)
1476 if (a->dash_list[i] != b->dash_list[i]) return 0;
1477
1478 return 1;
1479 }
1480
1481 void
1482 fz_drop_stroke_state(fz_context *ctx, const fz_stroke_state *strokec)
1483 {
1484 fz_stroke_state *stroke = (fz_stroke_state *)strokec; /* Explicit cast away of const */
1485
1486 if (fz_drop_imp(ctx, stroke, &stroke->refs))
1487 fz_free(ctx, stroke);
1488 }
1489
1490 fz_stroke_state *
1491 fz_new_stroke_state_with_dash_len(fz_context *ctx, int len)
1492 {
1493 fz_stroke_state *state;
1494
1495 if (len < 0)
1496 len = 0;
1497
1498 state = fz_malloc_flexible(ctx, fz_stroke_state, dash_list, len);
1499 state->refs = 1;
1500 state->start_cap = FZ_LINECAP_BUTT;
1501 state->dash_cap = FZ_LINECAP_BUTT;
1502 state->end_cap = FZ_LINECAP_BUTT;
1503 state->linejoin = FZ_LINEJOIN_MITER;
1504 state->linewidth = 1;
1505 state->miterlimit = 10;
1506 state->dash_phase = 0;
1507 state->dash_len = 0;
1508
1509 return state;
1510 }
1511
1512 fz_stroke_state *
1513 fz_new_stroke_state(fz_context *ctx)
1514 {
1515 return fz_new_stroke_state_with_dash_len(ctx, 0);
1516 }
1517
1518 fz_linecap
1519 fz_linecap_from_string(const char *str)
1520 {
1521 if (!strcmp(str, "Round"))
1522 return FZ_LINECAP_ROUND;
1523 if (!strcmp(str, "Square"))
1524 return FZ_LINECAP_SQUARE;
1525 if (!strcmp(str, "Triangle"))
1526 return FZ_LINECAP_TRIANGLE;
1527 return FZ_LINECAP_BUTT;
1528 }
1529
1530 const char *
1531 fz_string_from_linecap(fz_linecap cap)
1532 {
1533 switch (cap) {
1534 default:
1535 case FZ_LINECAP_BUTT: return "Butt";
1536 case FZ_LINECAP_ROUND: return "Round";
1537 case FZ_LINECAP_SQUARE: return "Square";
1538 case FZ_LINECAP_TRIANGLE: return "Triangle";
1539 }
1540 }
1541
1542 fz_linejoin
1543 fz_linejoin_from_string(const char *str)
1544 {
1545 if (!strcmp(str, "Round"))
1546 return FZ_LINEJOIN_ROUND;
1547 if (!strcmp(str, "Bevel"))
1548 return FZ_LINEJOIN_BEVEL;
1549 if (!strcmp(str, "MiterXPS"))
1550 return FZ_LINEJOIN_MITER_XPS;
1551 return FZ_LINEJOIN_MITER;
1552 }
1553
1554 const char *
1555 fz_string_from_linejoin(fz_linejoin join)
1556 {
1557 switch (join) {
1558 default:
1559 case FZ_LINEJOIN_MITER: return "Miter";
1560 case FZ_LINEJOIN_ROUND: return "Round";
1561 case FZ_LINEJOIN_BEVEL: return "Bevel";
1562 case FZ_LINEJOIN_MITER_XPS: return "MiterXPS";
1563 }
1564 }
1565
1566 fz_stroke_state *
1567 fz_clone_stroke_state(fz_context *ctx, const fz_stroke_state *stroke)
1568 {
1569 fz_stroke_state *clone = fz_new_stroke_state_with_dash_len(ctx, stroke->dash_len);
1570 size_t size = offsetof(fz_stroke_state, dash_list) + sizeof(float) * stroke->dash_len;
1571 memcpy(clone, stroke, size);
1572 clone->refs = 1;
1573 return clone;
1574 }
1575
1576 fz_stroke_state *
1577 fz_unshare_stroke_state_with_dash_len(fz_context *ctx, fz_stroke_state *shared, int len)
1578 {
1579 int single;
1580 fz_stroke_state *unshared;
1581
1582 fz_lock(ctx, FZ_LOCK_ALLOC);
1583 single = (shared->refs == 1);
1584 fz_unlock(ctx, FZ_LOCK_ALLOC);
1585
1586 if (single && len == shared->dash_len)
1587 return shared;
1588
1589 unshared = fz_new_stroke_state_with_dash_len(ctx, len);
1590 if (shared->dash_len >= len)
1591 memcpy(unshared, shared, offsetof(fz_stroke_state, dash_list) + sizeof(float) * len);
1592 else
1593 memcpy(unshared, shared, offsetof(fz_stroke_state, dash_list));
1594 unshared->refs = 1;
1595 unshared->dash_len = len;
1596
1597 if (fz_drop_imp(ctx, shared, &shared->refs))
1598 fz_free(ctx, shared);
1599 return unshared;
1600 }
1601
1602 fz_stroke_state *
1603 fz_unshare_stroke_state(fz_context *ctx, fz_stroke_state *shared)
1604 {
1605 return fz_unshare_stroke_state_with_dash_len(ctx, shared, shared->dash_len);
1606 }
1607
1608 static void *
1609 clone_block(fz_context *ctx, void *block, size_t len)
1610 {
1611 void *target;
1612
1613 if (len == 0 || block == NULL)
1614 return NULL;
1615
1616 target = fz_malloc(ctx, len);
1617 memcpy(target, block, len);
1618 return target;
1619 }
1620
1621 fz_path *
1622 fz_clone_path(fz_context *ctx, fz_path *path)
1623 {
1624 fz_path *new_path;
1625
1626 assert(ctx != NULL);
1627
1628 if (path == NULL)
1629 return NULL;
1630
1631 new_path = fz_malloc_struct(ctx, fz_path);
1632 new_path->refs = 1;
1633 new_path->packed = FZ_PATH_UNPACKED;
1634 fz_try(ctx)
1635 {
1636 switch(path->packed)
1637 {
1638 case FZ_PATH_UNPACKED:
1639 case FZ_PATH_PACKED_OPEN:
1640 new_path->cmd_len = path->cmd_len;
1641 new_path->cmd_cap = path->cmd_cap;
1642 new_path->cmds = Memento_label(clone_block(ctx, path->cmds, path->cmd_cap), "path_cmds");
1643 new_path->coord_len = path->coord_len;
1644 new_path->coord_cap = path->coord_cap;
1645 new_path->coords = Memento_label(clone_block(ctx, path->coords, sizeof(float)*path->coord_cap), "path_coords");
1646 new_path->current = path->current;
1647 new_path->begin = path->begin;
1648 break;
1649 case FZ_PATH_PACKED_FLAT:
1650 {
1651 uint8_t *data;
1652 float *xy;
1653 int i;
1654 fz_packed_path *ppath = (fz_packed_path *)path;
1655
1656 new_path->cmd_len = ppath->cmd_len;
1657 new_path->cmd_cap = ppath->cmd_len;
1658 new_path->coord_len = ppath->coord_len;
1659 new_path->coord_cap = ppath->coord_len;
1660 data = (uint8_t *)&ppath[1];
1661 new_path->coords = Memento_label(clone_block(ctx, data, sizeof(float)*path->coord_cap), "path_coords");
1662 data += sizeof(float) * path->coord_cap;
1663 new_path->cmds = Memento_label(clone_block(ctx, data, path->cmd_cap), "path_cmds");
1664 xy = new_path->coords;
1665 for (i = 0; i < new_path->cmd_len; i++)
1666 {
1667 switch (new_path->cmds[i])
1668 {
1669 case FZ_MOVETOCLOSE:
1670 case FZ_MOVETO:
1671 new_path->current.x = *xy++;
1672 new_path->current.y = *xy++;
1673 new_path->begin.x = new_path->current.x;
1674 new_path->begin.y = new_path->current.y;
1675 break;
1676 case FZ_CURVETO:
1677 xy += 2;
1678 /* fallthrough */
1679 case FZ_CURVETOV:
1680 case FZ_CURVETOY:
1681 case FZ_QUADTO:
1682 /* fallthrough */
1683 xy += 2;
1684 case FZ_LINETO:
1685 new_path->current.x = *xy++;
1686 new_path->current.y = *xy++;
1687 break;
1688 case FZ_DEGENLINETO:
1689 break;
1690 case FZ_HORIZTO:
1691 new_path->current.x = *xy++;
1692 break;
1693 case FZ_VERTTO:
1694 new_path->current.y = *xy++;
1695 break;
1696 case FZ_RECTTO:
1697 xy += 2;
1698 break;
1699 case FZ_CURVETOCLOSE:
1700 xy += 2;
1701 /* fallthrough */
1702 case FZ_CURVETOVCLOSE:
1703 case FZ_CURVETOYCLOSE:
1704 case FZ_QUADTOCLOSE:
1705 case FZ_LINETOCLOSE:
1706 xy++;
1707 /* fallthrough */
1708 case FZ_HORIZTOCLOSE:
1709 case FZ_VERTTOCLOSE:
1710 xy++;
1711 /* fallthrough */
1712 case FZ_DEGENLINETOCLOSE:
1713 new_path->current.x = new_path->begin.x;
1714 new_path->current.y = new_path->begin.y;
1715 break;
1716 }
1717 }
1718 }
1719 default:
1720 assert(!"Unknown packing method found in path");
1721 }
1722 }
1723 fz_catch(ctx)
1724 {
1725 fz_free(ctx, new_path->coords);
1726 fz_free(ctx, new_path->cmds);
1727 fz_free(ctx, new_path);
1728 fz_rethrow(ctx);
1729 }
1730 return new_path;
1731 }
1732
1733 typedef struct
1734 {
1735 fz_matrix ctm;
1736 fz_point p[4];
1737 int count;
1738 int trailing_move;
1739 } rect_path_arg;
1740
1741 static void
1742 rect_moveto(fz_context *ctx, void *arg_, float x, float y)
1743 {
1744 rect_path_arg *arg = (rect_path_arg *)arg_;
1745 fz_point p = fz_transform_point_xy(x, y, arg->ctm);
1746
1747 /* If we've already decided that it's not a rectangle. Just exit. */
1748 if (arg->count < 0)
1749 return;
1750
1751 /* We should never get multiple successive moves, by construction. */
1752
1753 /* If we're starting out... */
1754 if (arg->count == 0)
1755 {
1756 arg->p[0] = p;
1757 arg->count = 1;
1758 return;
1759 }
1760
1761 /* Otherwise, any move is fine, as long as it's not followed by another line... */
1762 arg->trailing_move = 1;
1763 }
1764
1765 static void
1766 rect_lineto(fz_context *ctx, void *arg_, float x, float y)
1767 {
1768 rect_path_arg *arg = (rect_path_arg *)arg_;
1769 fz_point p = fz_transform_point_xy(x, y, arg->ctm);
1770
1771 /* If we've already decided that it's not a rectangle. Just exit. */
1772 if (arg->count < 0)
1773 return;
1774
1775 if (arg->trailing_move)
1776 {
1777 arg->count = -1;
1778 return;
1779 }
1780
1781 /* Watch for pesky lines back to the same place. */
1782 if (arg->p[arg->count-1].x == p.x && arg->p[arg->count-1].y == p.y)
1783 return;
1784
1785 if (arg->count < 4)
1786 {
1787 arg->p[arg->count++] = p;
1788 return;
1789 }
1790
1791 /* Allow for lines back to the start. */
1792 if (arg->count == 4)
1793 {
1794 if (arg->p[0].x == p.x && arg->p[0].y == p.y)
1795 {
1796 arg->count++;
1797 return;
1798 }
1799 }
1800
1801 arg->count = -1;
1802 }
1803
1804 static void
1805 rect_curveto(fz_context *ctx, void *arg_, float x1, float y1, float x2, float y2, float x3, float y3)
1806 {
1807 rect_path_arg *arg = (rect_path_arg *)arg_;
1808
1809 arg->count = -1;
1810 }
1811
1812 static const fz_path_walker rect_path_walker =
1813 {
1814 rect_moveto,
1815 rect_lineto,
1816 rect_curveto,
1817 NULL
1818 };
1819
1820 int
1821 fz_path_is_rect(fz_context *ctx, const fz_path *path, fz_matrix ctm)
1822 {
1823 return fz_path_is_rect_with_bounds(ctx, path, ctm, NULL);
1824 }
1825
1826 int
1827 fz_path_is_rect_with_bounds(fz_context *ctx, const fz_path *path, fz_matrix ctm, fz_rect *bounds)
1828 {
1829 rect_path_arg arg;
1830
1831 arg.ctm = ctm;
1832 arg.trailing_move = 0;
1833 arg.count = 0;
1834
1835 fz_walk_path(ctx, path, &rect_path_walker, &arg);
1836
1837 if (arg.count < 0)
1838 return 0;
1839
1840 /* 3 entries are bad, unless the last one returns the first. */
1841 if (arg.count == 3 && (arg.p[0].x != arg.p[2].x || arg.p[0].y != arg.p[2].y))
1842 {
1843 return 0;
1844 }
1845 if (arg.count == 2 || arg.count == 3)
1846 {
1847 if (arg.p[0].x == arg.p[1].x || arg.p[0].y == arg.p[1].y)
1848 {
1849 if (bounds)
1850 {
1851 bounds->x0 = fz_min(arg.p[0].x, arg.p[1].x);
1852 bounds->x1 = fz_max(arg.p[0].x, arg.p[1].x);
1853 bounds->y0 = fz_min(arg.p[0].y, arg.p[1].y);
1854 bounds->y1 = fz_max(arg.p[0].y, arg.p[1].y);
1855 }
1856 return 1;
1857 }
1858 }
1859 /* All that's left are 4 entry ones */
1860 if (arg.count != 4)
1861 return 0;
1862
1863 if (arg.p[0].x == arg.p[1].x)
1864 {
1865 /* p[0] p[3]
1866 * p[1] p[2]
1867 */
1868 if (arg.p[1].y == arg.p[2].y && arg.p[0].y == arg.p[3].y && arg.p[2].x == arg.p[3].x)
1869 {
1870 if (bounds)
1871 {
1872 bounds->x0 = fz_min(arg.p[0].x, arg.p[3].x);
1873 bounds->x1 = fz_max(arg.p[0].x, arg.p[3].x);
1874 bounds->y0 = fz_min(arg.p[0].y, arg.p[1].y);
1875 bounds->y1 = fz_max(arg.p[0].y, arg.p[1].y);
1876 }
1877 return 1;
1878 }
1879 }
1880 if (arg.p[0].y == arg.p[1].y)
1881 {
1882 /* p[0] p[1]
1883 * p[3] p[2]
1884 */
1885 if (arg.p[1].x == arg.p[2].x && arg.p[0].x == arg.p[3].x && arg.p[2].y == arg.p[3].y)
1886 {
1887 if (bounds)
1888 {
1889 bounds->x0 = fz_min(arg.p[0].x, arg.p[1].x);
1890 bounds->x1 = fz_max(arg.p[0].x, arg.p[1].x);
1891 bounds->y0 = fz_min(arg.p[0].y, arg.p[3].y);
1892 bounds->y1 = fz_max(arg.p[0].y, arg.p[3].y);
1893 }
1894 return 1;
1895 }
1896 }
1897 return 0;
1898 }