1 /* Copyright (C) 2001-2012 Artifex Software, Inc.
2 All Rights Reserved.
3
4 This software is provided AS-IS with no warranty, either express or
5 implied.
6
7 This software is distributed under license and may not be copied,
8 modified or distributed except as expressly authorized under the terms
9 of the license contained in the file LICENSE in this distribution.
10
11 Refer to licensing information at http://www.artifex.com or contact
12 Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134, San Rafael,
13 CA 94903, U.S.A., +1(415)492-9861, for further information.
14 */
15
16
17 /* Implementation of clipping paths, other than actual clipping */
18 #include "gx.h"
19 #include "gserrors.h"
20 #include "gsstruct.h"
21 #include "gsutil.h"
22 #include "gsline.h"
23 #include "gxdevice.h"
24 #include "gxfixed.h"
25 #include "gxpaint.h"
26 #include "gscoord.h" /* needs gsmatrix.h */
27 #include "gxistate.h"
28 #include "gzpath.h"
29 #include "gzcpath.h"
30 #include "gzacpath.h"
31
32 /* Forward references */
33 static void gx_clip_list_from_rectangle(gx_clip_list *, gs_fixed_rect *);
34
35 /* Other structure types */
36 public_st_clip_rect();
37 public_st_clip_list();
38 public_st_clip_path();
39 private_st_clip_rect_list();
40 public_st_device_clip();
41 private_st_cpath_enum();
42 private_st_cpath_path_list();
43
44 /* GC procedures for gx_clip_path */
45 static
46 ENUM_PTRS_WITH(clip_path_enum_ptrs, gx_clip_path *cptr) return ENUM_USING(st_path, &cptr->path, sizeof(cptr->path), index - 2);
47
48 case 0:
49 return ENUM_OBJ((cptr->rect_list == &cptr->local_list ? 0 :
50 cptr->rect_list));
51 case 1:
52 return ENUM_OBJ(cptr->path_list);
53 ENUM_PTRS_END
54 static
RELOC_PTRS_WITH(clip_path_reloc_ptrs,gx_clip_path * cptr)55 RELOC_PTRS_WITH(clip_path_reloc_ptrs, gx_clip_path *cptr)
56 {
57 if (cptr->rect_list != &cptr->local_list)
58 RELOC_VAR(cptr->rect_list);
59 RELOC_VAR(cptr->path_list);
60 RELOC_USING(st_path, &cptr->path, sizeof(gx_path));
61 }
62 RELOC_PTRS_END
63
64 /* GC procedures for gx_device_clip */
65 static
ENUM_PTRS_WITH(device_clip_enum_ptrs,gx_device_clip * cptr)66 ENUM_PTRS_WITH(device_clip_enum_ptrs, gx_device_clip *cptr)
67 {
68 if (index < st_clip_list_max_ptrs + 1)
69 return ENUM_USING(st_clip_list, &cptr->list,
70 sizeof(gx_clip_list), index - 1);
71 return ENUM_USING(st_device_forward, vptr,
72 sizeof(gx_device_forward),
73 index - (st_clip_list_max_ptrs + 1));
74 }
75 case 0:
76 ENUM_RETURN((cptr->current == &cptr->list.single ? NULL :
77 (void *)cptr->current));
78 ENUM_PTRS_END
79 static
RELOC_PTRS_WITH(device_clip_reloc_ptrs,gx_device_clip * cptr)80 RELOC_PTRS_WITH(device_clip_reloc_ptrs, gx_device_clip *cptr)
81 {
82 if (cptr->current == &cptr->list.single)
83 cptr->current = &((gx_device_clip *)RELOC_OBJ(vptr))->list.single;
84 else
85 RELOC_PTR(gx_device_clip, current);
86 RELOC_USING(st_clip_list, &cptr->list, sizeof(gx_clip_list));
87 RELOC_USING(st_device_forward, vptr, sizeof(gx_device_forward));
88 }
89 RELOC_PTRS_END
90
91 /* Define an empty clip list. */
92 static const gx_clip_list clip_list_empty = {
93 {
94 0, /* next */
95 0, /* prev */
96 min_int, /* ymin */
97 max_int, /* ymax */
98 0, /* xmin */
99 0, /* xmax */
100 0 /* to_visit */
101 }, /* single */
102 0, /* head */
103 0, /* tail */
104 0, /* insert */
105 0, /* xmin */
106 0, /* xmax */
107 0 /* count */
108 };
109
110 /* ------ Clipping path memory management ------ */
111
112 static rc_free_proc(rc_free_cpath_list);
113 static rc_free_proc(rc_free_cpath_list_local);
114 static rc_free_proc(rc_free_cpath_path_list);
115
116 /*
117 * Initialize those parts of the contents of a clip path that aren't
118 * part of the path.
119 */
120 static void
cpath_init_rectangle(gx_clip_path * pcpath,gs_fixed_rect * pbox)121 cpath_init_rectangle(gx_clip_path * pcpath, gs_fixed_rect * pbox)
122 {
123 gx_clip_list_from_rectangle(&pcpath->rect_list->list, pbox);
124 pcpath->inner_box = *pbox;
125 pcpath->path_valid = false;
126 pcpath->path.bbox = *pbox;
127 gx_cpath_set_outer_box(pcpath);
128 pcpath->id = gs_next_ids(pcpath->path.memory, 1); /* path changed => change id */
129 }
130 static void
cpath_init_own_contents(gx_clip_path * pcpath)131 cpath_init_own_contents(gx_clip_path * pcpath)
132 { /* We could make null_rect static, but then it couldn't be const. */
133 gs_fixed_rect null_rect;
134
135 null_rect.p.x = null_rect.p.y = null_rect.q.x = null_rect.q.y = 0;
136 cpath_init_rectangle(pcpath, &null_rect);
137 pcpath->path_list = NULL;
138 }
139 static void
cpath_share_own_contents(gx_clip_path * pcpath,const gx_clip_path * shared)140 cpath_share_own_contents(gx_clip_path * pcpath, const gx_clip_path * shared)
141 {
142 pcpath->inner_box = shared->inner_box;
143 pcpath->path_valid = shared->path_valid;
144 pcpath->outer_box = shared->outer_box;
145 pcpath->id = shared->id;
146 }
147
148 /* Allocate only the segments of a clipping path on the heap. */
149 static int
cpath_alloc_list(gx_clip_rect_list ** prlist,gs_memory_t * mem,client_name_t cname)150 cpath_alloc_list(gx_clip_rect_list ** prlist, gs_memory_t * mem,
151 client_name_t cname)
152 {
153 rc_alloc_struct_1(*prlist, gx_clip_rect_list, &st_clip_rect_list, mem,
154 return_error(gs_error_VMerror), cname);
155 (*prlist)->rc.free = rc_free_cpath_list;
156 return 0;
157 }
158 int
gx_cpath_init_contained_shared(gx_clip_path * pcpath,const gx_clip_path * shared,gs_memory_t * mem,client_name_t cname)159 gx_cpath_init_contained_shared(gx_clip_path * pcpath,
160 const gx_clip_path * shared, gs_memory_t * mem, client_name_t cname)
161 {
162 if (shared) {
163 if (shared->path.segments == &shared->path.local_segments) {
164 lprintf1("Attempt to share (local) segments of clip path 0x%lx!\n",
165 (ulong) shared);
166 return_error(gs_error_Fatal);
167 }
168 *pcpath = *shared;
169 pcpath->path.memory = mem;
170 pcpath->path.allocation = path_allocated_contained;
171 rc_increment(pcpath->path.segments);
172 rc_increment(pcpath->rect_list);
173 rc_increment(pcpath->path_list);
174 } else {
175 int code = cpath_alloc_list(&pcpath->rect_list, mem, cname);
176
177 if (code < 0)
178 return code;
179 code = gx_path_alloc_contained(&pcpath->path, mem, cname);
180 if (code < 0) {
181 gs_free_object(mem, pcpath->rect_list, cname);
182 pcpath->rect_list = 0;
183 return code;
184 }
185 cpath_init_own_contents(pcpath);
186 }
187 return 0;
188 }
189 #define gx_cpath_alloc_contents(pcpath, shared, mem, cname)\
190 gx_cpath_init_contained_shared(pcpath, shared, mem, cname)
191
192 /* Allocate all of a clipping path on the heap. */
193 gx_clip_path *
gx_cpath_alloc_shared(const gx_clip_path * shared,gs_memory_t * mem,client_name_t cname)194 gx_cpath_alloc_shared(const gx_clip_path * shared, gs_memory_t * mem,
195 client_name_t cname)
196 {
197 gx_clip_path *pcpath =
198 gs_alloc_struct(mem, gx_clip_path, &st_clip_path, cname);
199 int code;
200
201 if (pcpath == 0)
202 return 0;
203 code = gx_cpath_alloc_contents(pcpath, shared, mem, cname);
204 if (code < 0) {
205 gs_free_object(mem, pcpath, cname);
206 return 0;
207 }
208 pcpath->path.allocation = path_allocated_on_heap;
209 return pcpath;
210 }
211
212 /* Initialize a stack-allocated clipping path. */
213 int
gx_cpath_init_local_shared_nested(gx_clip_path * pcpath,const gx_clip_path * shared,gs_memory_t * mem,bool safely_nested)214 gx_cpath_init_local_shared_nested(gx_clip_path * pcpath,
215 const gx_clip_path * shared,
216 gs_memory_t * mem,
217 bool safely_nested)
218 {
219 if (shared) {
220 if ((shared->path.segments == &shared->path.local_segments) &&
221 !safely_nested) {
222 lprintf1("Attempt to share (local) segments of clip path 0x%lx!\n",
223 (ulong) shared);
224 return_error(gs_error_Fatal);
225 }
226 pcpath->path = shared->path;
227 pcpath->path.allocation = path_allocated_on_stack;
228 rc_increment(pcpath->path.segments);
229 pcpath->rect_list = shared->rect_list;
230 rc_increment(pcpath->rect_list);
231 pcpath->path_list = shared->path_list;
232 rc_increment(pcpath->path_list);
233 cpath_share_own_contents(pcpath, shared);
234 pcpath->rule = shared->rule;
235 } else {
236 gx_path_init_local(&pcpath->path, mem);
237 rc_init_free(&pcpath->local_list, mem, 1, rc_free_cpath_list_local);
238 pcpath->rect_list = &pcpath->local_list;
239 cpath_init_own_contents(pcpath);
240 }
241 return 0;
242 }
243
244 int
gx_cpath_init_local_shared(gx_clip_path * pcpath,const gx_clip_path * shared,gs_memory_t * mem)245 gx_cpath_init_local_shared(gx_clip_path * pcpath, const gx_clip_path * shared,
246 gs_memory_t * mem)
247 {
248 return gx_cpath_init_local_shared_nested(pcpath, shared, mem, 0);
249 }
250
251 /* Unshare a clipping path. */
252 int
gx_cpath_unshare(gx_clip_path * pcpath)253 gx_cpath_unshare(gx_clip_path * pcpath)
254 {
255 int code = gx_path_unshare(&pcpath->path);
256 gx_clip_rect_list *rlist = pcpath->rect_list;
257
258 if (code < 0)
259 return code;
260 if (rlist->rc.ref_count > 1) {
261 int code = cpath_alloc_list(&pcpath->rect_list, pcpath->path.memory,
262 "gx_cpath_unshare");
263
264 if (code < 0)
265 return code;
266 /* Copy the rectangle list. */
267 /**************** NYI ****************/
268 rc_decrement(rlist, "gx_cpath_unshare");
269 }
270 return code;
271 }
272
273 /* Free a clipping path. */
274 void
gx_cpath_free(gx_clip_path * pcpath,client_name_t cname)275 gx_cpath_free(gx_clip_path * pcpath, client_name_t cname)
276 {
277 if (pcpath == 0L)
278 return;
279
280 rc_decrement(pcpath->rect_list, cname);
281 rc_decrement(pcpath->path_list, cname);
282 /* Clean up pointers for GC. */
283 pcpath->rect_list = 0;
284 pcpath->path_list = 0;
285 {
286 gx_path_allocation_t alloc = pcpath->path.allocation;
287
288 if (alloc == path_allocated_on_heap) {
289 pcpath->path.allocation = path_allocated_contained;
290 gx_path_free(&pcpath->path, cname);
291 gs_free_object(pcpath->path.memory, pcpath, cname);
292 } else
293 gx_path_free(&pcpath->path, cname);
294 }
295 }
296
297 /* Assign a clipping path, preserving the source. */
298 int
gx_cpath_assign_preserve(gx_clip_path * pcpto,gx_clip_path * pcpfrom)299 gx_cpath_assign_preserve(gx_clip_path * pcpto, gx_clip_path * pcpfrom)
300 {
301 int code = gx_path_assign_preserve(&pcpto->path, &pcpfrom->path);
302 gx_clip_rect_list *fromlist = pcpfrom->rect_list;
303 gx_clip_rect_list *tolist = pcpto->rect_list;
304 gx_path path;
305
306 if (code < 0)
307 return 0;
308 if (fromlist == &pcpfrom->local_list) {
309 /* We can't use pcpfrom's list object. */
310 if (tolist == &pcpto->local_list || tolist->rc.ref_count > 1) {
311 /* We can't use pcpto's list either. Allocate a new one. */
312 int code = cpath_alloc_list(&tolist, tolist->rc.memory,
313 "gx_cpath_assign");
314
315 if (code < 0)
316 return code;
317 rc_decrement(pcpto->rect_list, "gx_cpath_assign");
318 } else {
319 /* Use pcpto's list object. */
320 rc_free_cpath_list_local(tolist->rc.memory, tolist,
321 "gx_cpath_assign");
322 }
323 tolist->list = fromlist->list;
324 pcpfrom->rect_list = tolist;
325 rc_increment(tolist);
326 } else {
327 /* We can use pcpfrom's list object. */
328 rc_increment(fromlist);
329 rc_decrement(pcpto->rect_list, "gx_cpath_assign");
330 }
331 rc_increment(pcpfrom->path_list);
332 path = pcpto->path, *pcpto = *pcpfrom, pcpto->path = path;
333 return 0;
334 }
335
336 /* Assign a clipping path, releasing the source. */
337 int
gx_cpath_assign_free(gx_clip_path * pcpto,gx_clip_path * pcpfrom)338 gx_cpath_assign_free(gx_clip_path * pcpto, gx_clip_path * pcpfrom)
339 { /* For right now, just do assign + free. */
340 int code = gx_cpath_assign_preserve(pcpto, pcpfrom);
341
342 if (code < 0)
343 return 0;
344 gx_cpath_free(pcpfrom, "gx_cpath_assign_free");
345 return 0;
346 }
347
348 /* Free the clipping list when its reference count goes to zero. */
349 static void
rc_free_cpath_list_local(gs_memory_t * mem,void * vrlist,client_name_t cname)350 rc_free_cpath_list_local(gs_memory_t * mem, void *vrlist,
351 client_name_t cname)
352 {
353 gx_clip_rect_list *rlist = (gx_clip_rect_list *) vrlist;
354
355 gx_clip_list_free(&rlist->list, mem);
356 }
357 static void
rc_free_cpath_list(gs_memory_t * mem,void * vrlist,client_name_t cname)358 rc_free_cpath_list(gs_memory_t * mem, void *vrlist, client_name_t cname)
359 {
360 rc_free_cpath_list_local(mem, vrlist, cname);
361 gs_free_object(mem, vrlist, cname);
362 }
363
364 static void
rc_free_cpath_path_list(gs_memory_t * mem,void * vplist,client_name_t cname)365 rc_free_cpath_path_list(gs_memory_t * mem, void *vplist, client_name_t cname)
366 {
367 gx_cpath_path_list *plist = (gx_cpath_path_list *)vplist;
368 rc_decrement(plist->next, cname);
369 gx_path_free(&plist->path, cname);
370 gs_free_object(plist->path.memory, plist, cname);
371 }
372
373 /* Allocate a new clip path list node. The created node has a ref count
374 of 1, and "steals" the reference to next (i.e. does not increment
375 its reference count). */
376 static int
gx_cpath_path_list_new(gs_memory_t * mem,gx_clip_path * pcpath,int rule,gx_path * ppfrom,gx_cpath_path_list * next,gx_cpath_path_list ** pnew)377 gx_cpath_path_list_new(gs_memory_t *mem, gx_clip_path *pcpath, int rule,
378 gx_path *ppfrom, gx_cpath_path_list *next, gx_cpath_path_list **pnew)
379 {
380 int code;
381 client_name_t cname = "gx_cpath_path_list_new";
382 gx_cpath_path_list *pcplist = gs_alloc_struct(mem, gx_cpath_path_list,
383 &st_cpath_path_list, cname);
384
385 if (pcplist == 0)
386 return_error(gs_error_VMerror);
387 rc_init_free(pcplist, mem, 1, rc_free_cpath_path_list);
388 if (pcpath!=NULL && !pcpath->path_valid) {
389 code = gx_path_init_contained_shared(&pcplist->path, NULL, mem, cname);
390 if (code < 0)
391 return code;
392 code = gx_cpath_to_path(pcpath, &pcplist->path);
393 } else {
394 gx_path_init_local(&pcplist->path, mem);
395 code = gx_path_assign_preserve(&pcplist->path, ppfrom);
396 }
397 if (code < 0)
398 return code;
399 pcplist->next = next;
400 pcplist->rule = rule;
401 *pnew = pcplist;
402 return 0;
403 }
404
405 /* ------ Clipping path accessing ------ */
406
407 /* Synthesize a path from a clipping path. */
408 int
gx_cpath_to_path_synthesize(const gx_clip_path * pcpath,gx_path * ppath)409 gx_cpath_to_path_synthesize(const gx_clip_path * pcpath, gx_path * ppath)
410 {
411 /* Synthesize a path. */
412 gs_cpath_enum cenum;
413 gs_fixed_point pts[3];
414 int code;
415
416 gx_cpath_enum_init(&cenum, pcpath);
417 while ((code = gx_cpath_enum_next(&cenum, pts)) != 0) {
418 switch (code) {
419 case gs_pe_moveto:
420 code = gx_path_add_point(ppath, pts[0].x, pts[0].y);
421 break;
422 case gs_pe_lineto:
423 code = gx_path_add_line_notes(ppath, pts[0].x, pts[0].y,
424 gx_cpath_enum_notes(&cenum));
425 break;
426 case gs_pe_gapto:
427 code = gx_path_add_gap_notes(ppath, pts[0].x, pts[0].y,
428 gx_cpath_enum_notes(&cenum));
429 break;
430 case gs_pe_curveto:
431 code = gx_path_add_curve_notes(ppath, pts[0].x, pts[0].y,
432 pts[1].x, pts[1].y,
433 pts[2].x, pts[2].y,
434 gx_cpath_enum_notes(&cenum));
435 break;
436 case gs_pe_closepath:
437 code = gx_path_close_subpath_notes(ppath,
438 gx_cpath_enum_notes(&cenum));
439 break;
440 default:
441 if (code >= 0)
442 code = gs_note_error(gs_error_unregistered);
443 }
444 if (code < 0)
445 break;
446 }
447 return 0;
448 }
449
450 /* Return the path of a clipping path. */
451 int
gx_cpath_to_path(gx_clip_path * pcpath,gx_path * ppath)452 gx_cpath_to_path(gx_clip_path * pcpath, gx_path * ppath)
453 {
454 if (!pcpath->path_valid) {
455 gx_path rpath;
456 int code;
457
458 gx_path_init_local(&rpath, pcpath->path.memory);
459 code = gx_cpath_to_path_synthesize(pcpath, &rpath);
460 if (code < 0) {
461 gx_path_free(&rpath, "gx_cpath_to_path error");
462 return code;
463 }
464 code = gx_path_assign_free(&pcpath->path, &rpath);
465 if (code < 0)
466 return code;
467 pcpath->path_valid = true;
468 }
469 return gx_path_assign_preserve(ppath, &pcpath->path);
470 }
471 /* Return the inner and outer check rectangles for a clipping path. */
472 /* Return true iff the path is a rectangle. */
473 bool
gx_cpath_inner_box(const gx_clip_path * pcpath,gs_fixed_rect * pbox)474 gx_cpath_inner_box(const gx_clip_path * pcpath, gs_fixed_rect * pbox)
475 {
476 *pbox = pcpath->inner_box;
477 return clip_list_is_rectangle(gx_cpath_list(pcpath));
478 }
479 bool
gx_cpath_outer_box(const gx_clip_path * pcpath,gs_fixed_rect * pbox)480 gx_cpath_outer_box(const gx_clip_path * pcpath, gs_fixed_rect * pbox)
481 {
482 *pbox = pcpath->outer_box;
483 return clip_list_is_rectangle(gx_cpath_list(pcpath));
484 }
485
486 /* Test if a clipping path includes a rectangle. */
487 /* The rectangle need not be oriented correctly, i.e. x0 > x1 is OK. */
488 bool
gx_cpath_includes_rectangle(register const gx_clip_path * pcpath,fixed x0,fixed y0,fixed x1,fixed y1)489 gx_cpath_includes_rectangle(register const gx_clip_path * pcpath,
490 fixed x0, fixed y0, fixed x1, fixed y1)
491 {
492 return
493 (x0 <= x1 ?
494 (pcpath->inner_box.p.x <= x0 && x1 <= pcpath->inner_box.q.x) :
495 (pcpath->inner_box.p.x <= x1 && x0 <= pcpath->inner_box.q.x)) &&
496 (y0 <= y1 ?
497 (pcpath->inner_box.p.y <= y0 && y1 <= pcpath->inner_box.q.y) :
498 (pcpath->inner_box.p.y <= y1 && y0 <= pcpath->inner_box.q.y));
499 }
500
501 /* Set the outer clipping box to the path bounding box, */
502 /* expanded to pixel boundaries. */
503 void
gx_cpath_set_outer_box(gx_clip_path * pcpath)504 gx_cpath_set_outer_box(gx_clip_path * pcpath)
505 {
506 pcpath->outer_box.p.x = fixed_floor(pcpath->path.bbox.p.x);
507 pcpath->outer_box.p.y = fixed_floor(pcpath->path.bbox.p.y);
508 pcpath->outer_box.q.x = fixed_ceiling(pcpath->path.bbox.q.x);
509 pcpath->outer_box.q.y = fixed_ceiling(pcpath->path.bbox.q.y);
510 }
511
512 /* Return the rectangle list of a clipping path (for local use only). */
513 const gx_clip_list *
gx_cpath_list(const gx_clip_path * pcpath)514 gx_cpath_list(const gx_clip_path *pcpath)
515 {
516 return &pcpath->rect_list->list;
517 }
518 /* Internal non-const version of the same accessor. */
519 static inline gx_clip_list *
gx_cpath_list_private(const gx_clip_path * pcpath)520 gx_cpath_list_private(const gx_clip_path *pcpath)
521 {
522 return &pcpath->rect_list->list;
523 }
524
525 /* ------ Clipping path setting ------ */
526
527 /* Create a rectangular clipping path. */
528 /* The supplied rectangle may not be oriented correctly, */
529 /* but it will be oriented correctly upon return. */
530 static int
cpath_set_rectangle(gx_clip_path * pcpath,gs_fixed_rect * pbox)531 cpath_set_rectangle(gx_clip_path * pcpath, gs_fixed_rect * pbox)
532 {
533 gx_clip_rect_list *rlist = pcpath->rect_list;
534
535 if (rlist->rc.ref_count <= 1)
536 gx_clip_list_free(&rlist->list, rlist->rc.memory);
537 else {
538 int code = cpath_alloc_list(&pcpath->rect_list, pcpath->path.memory,
539 "gx_cpath_from_rectangle");
540
541 if (code < 0)
542 return code;
543 rc_decrement(rlist, "gx_cpath_from_rectangle");
544 rlist = pcpath->rect_list;
545 }
546 cpath_init_rectangle(pcpath, pbox);
547 return 0;
548 }
549 int
gx_cpath_from_rectangle(gx_clip_path * pcpath,gs_fixed_rect * pbox)550 gx_cpath_from_rectangle(gx_clip_path * pcpath, gs_fixed_rect * pbox)
551 {
552 int code = gx_path_new(&pcpath->path);
553
554 if (code < 0)
555 return code;
556 return cpath_set_rectangle(pcpath, pbox);
557 }
558 int
gx_cpath_reset(gx_clip_path * pcpath)559 gx_cpath_reset(gx_clip_path * pcpath)
560 {
561 gs_fixed_rect null_rect;
562
563 null_rect.p.x = null_rect.p.y = null_rect.q.x = null_rect.q.y = 0;
564 return gx_cpath_from_rectangle(pcpath, &null_rect);
565 }
566
567 /* If a clipping path is a rectangle, return the rectangle. */
568 const gs_fixed_rect *
cpath_is_rectangle(const gx_clip_path * pcpath)569 cpath_is_rectangle(const gx_clip_path * pcpath)
570 {
571 if (pcpath->path_valid)
572 return NULL;
573 if (pcpath->inner_box.p.x != pcpath->path.bbox.p.x ||
574 pcpath->inner_box.p.y != pcpath->path.bbox.p.y ||
575 pcpath->inner_box.q.x != pcpath->path.bbox.q.x ||
576 pcpath->inner_box.q.y != pcpath->path.bbox.q.y)
577 return NULL;
578 return &pcpath->inner_box;
579 }
580
581 /* Intersect a new clipping path with an old one. */
582 /* Flatten the new path first (in a copy) if necessary. */
583 int
gx_cpath_clip(gs_state * pgs,gx_clip_path * pcpath,gx_path * ppath_orig,int rule)584 gx_cpath_clip(gs_state *pgs, gx_clip_path *pcpath,
585 /*const*/ gx_path *ppath_orig, int rule)
586 {
587 return gx_cpath_intersect(pcpath, ppath_orig, rule,
588 (gs_imager_state *)pgs);
589 }
590
591 int
gx_cpath_intersect_with_params(gx_clip_path * pcpath,gx_path * ppath_orig,int rule,gs_imager_state * pis,const gx_fill_params * params)592 gx_cpath_intersect_with_params(gx_clip_path *pcpath, /*const*/ gx_path *ppath_orig,
593 int rule, gs_imager_state *pis, const gx_fill_params * params)
594 {
595 gx_path fpath;
596 /*const*/ gx_path *ppath = ppath_orig;
597 gs_fixed_rect old_box, new_box;
598 int code;
599
600 /* Flatten the path if necessary. */
601 if (gx_path_has_curves_inline(ppath)) {
602 gx_path_init_local(&fpath, pis->memory);
603 code = gx_path_add_flattened_accurate(ppath, &fpath,
604 gs_currentflat_inline(pis),
605 pis->accurate_curves);
606 if (code < 0)
607 return code;
608 ppath = &fpath;
609 }
610
611 if (gx_cpath_inner_box(pcpath, &old_box) &&
612 ((code = gx_path_is_rectangle(ppath, &new_box)) ||
613 gx_path_is_void(ppath))
614 ) {
615 int changed = 0;
616
617 if (!code) {
618 /* The new path is void. */
619 if (gx_path_current_point(ppath, &new_box.p) < 0) {
620 /* Use the user space origin (arbitrarily). */
621 new_box.p.x = float2fixed(pis->ctm.tx);
622 new_box.p.y = float2fixed(pis->ctm.ty);
623 }
624 new_box.q = new_box.p;
625 changed = 1;
626 } else {
627 if (params != NULL) {
628 /* Called from gx_default_fill_path for converting
629 a filling path into a clipping path.
630 Apply same adjustment as for filling the path. */
631 gs_fixed_point adjust = params->adjust;
632 fixed adjust_xl, adjust_xu, adjust_yl, adjust_yu;
633
634 if (adjust.x == -1)
635 adjust_xl = adjust_xu = adjust_yl = adjust_yu = 0;
636 else {
637 adjust_xl = (adjust.x == fixed_half ? fixed_half - fixed_epsilon : adjust.x);
638 adjust_yl = (adjust.y == fixed_half ? fixed_half - fixed_epsilon : adjust.y);
639 adjust_xu = adjust.x;
640 adjust_yu = adjust.y;
641 }
642 new_box.p.x = int2fixed(fixed2int_pixround(new_box.p.x - adjust_xl));
643 new_box.p.y = int2fixed(fixed2int_pixround(new_box.p.y - adjust_yl));
644 new_box.q.x = int2fixed(fixed2int_pixround(new_box.q.x + adjust_xu));
645 new_box.q.y = int2fixed(fixed2int_pixround(new_box.q.y + adjust_yu));
646 }
647 /* Intersect the two rectangles if necessary. */
648 if (old_box.p.x > new_box.p.x)
649 new_box.p.x = old_box.p.x, ++changed;
650 if (old_box.p.y > new_box.p.y)
651 new_box.p.y = old_box.p.y, ++changed;
652 if (old_box.q.x < new_box.q.x)
653 new_box.q.x = old_box.q.x, ++changed;
654 if (old_box.q.y < new_box.q.y)
655 new_box.q.y = old_box.q.y, ++changed;
656 /* Check for a degenerate rectangle. */
657 if (new_box.q.x < new_box.p.x || new_box.q.y < new_box.p.y)
658 new_box.p = new_box.q, changed = 1;
659 }
660 if (changed == 4) {
661 /* The new box/path is the same as the old. */
662 return 0;
663 }
664 /* Release the existing path. */
665 rc_decrement(pcpath->path_list, "gx_cpath_intersect");
666 pcpath->path_list = NULL;
667 gx_path_new(&pcpath->path);
668 ppath->bbox = new_box;
669 cpath_set_rectangle(pcpath, &new_box);
670 if (changed == 0) {
671 /* The path is valid; otherwise, defer constructing it. */
672 gx_path_assign_preserve(&pcpath->path, ppath);
673 pcpath->path_valid = true;
674 }
675 } else {
676 /* New clip path is nontrivial. Intersect the slow way. */
677 gx_cpath_path_list *next = pcpath->path_list;
678 bool path_valid =
679 gx_cpath_inner_box(pcpath, &old_box) &&
680 gx_path_bbox(ppath, &new_box) >= 0 &&
681 gx_cpath_includes_rectangle(pcpath,
682 new_box.p.x, new_box.p.y,
683 new_box.q.x, new_box.q.y);
684
685 if (!path_valid && next == NULL) {
686 code = gx_cpath_path_list_new(pcpath->path.memory, pcpath, pcpath->rule,
687 &pcpath->path, NULL, &next);
688 if (code < 0)
689 goto ex;
690 }
691 code = gx_cpath_intersect_path_slow(pcpath, (params != NULL ? ppath_orig : ppath),
692 rule, pis, params);
693 if (code < 0)
694 goto ex;
695 if (path_valid) {
696 gx_path_assign_preserve(&pcpath->path, ppath_orig);
697 pcpath->path_valid = true;
698 pcpath->rule = rule;
699 } else {
700 code = gx_cpath_path_list_new(pcpath->path.memory, NULL, rule,
701 ppath_orig, next, &pcpath->path_list);
702 }
703 }
704 ex:
705 if (ppath != ppath_orig)
706 gx_path_free(ppath, "gx_cpath_clip");
707 return code;
708 }
709 int
gx_cpath_intersect(gx_clip_path * pcpath,gx_path * ppath_orig,int rule,gs_imager_state * pis)710 gx_cpath_intersect(gx_clip_path *pcpath, /*const*/ gx_path *ppath_orig,
711 int rule, gs_imager_state *pis)
712 {
713 return gx_cpath_intersect_with_params(pcpath, ppath_orig,
714 rule, pis, NULL);
715 }
716
717 /* Scale a clipping path by a power of 2. */
718 int
gx_cpath_scale_exp2_shared(gx_clip_path * pcpath,int log2_scale_x,int log2_scale_y,bool list_shared,bool segments_shared)719 gx_cpath_scale_exp2_shared(gx_clip_path * pcpath, int log2_scale_x,
720 int log2_scale_y, bool list_shared,
721 bool segments_shared)
722 {
723 int code =
724 (pcpath->path_valid ?
725 gx_path_scale_exp2_shared(&pcpath->path, log2_scale_x, log2_scale_y,
726 segments_shared) :
727 0);
728 gx_clip_list *list = gx_cpath_list_private(pcpath);
729 gx_clip_rect *pr;
730
731 if (code < 0)
732 return code;
733 /* Scale the fixed entries. */
734 gx_rect_scale_exp2(&pcpath->inner_box, log2_scale_x, log2_scale_y);
735 gx_rect_scale_exp2(&pcpath->outer_box, log2_scale_x, log2_scale_y);
736 if (!list_shared) {
737 /* Scale the clipping list. */
738 pr = list->head;
739 if (pr == 0)
740 pr = &list->single;
741 for (; pr != 0; pr = pr->next)
742 if (pr != list->head && pr != list->tail) {
743
744 #define SCALE_V(v, s)\
745 if ( pr->v != min_int && pr->v != max_int )\
746 pr->v = (s >= 0 ? pr->v << s : pr->v >> -s)
747
748 SCALE_V(xmin, log2_scale_x);
749 SCALE_V(xmax, log2_scale_x);
750 SCALE_V(ymin, log2_scale_y);
751 SCALE_V(ymax, log2_scale_y);
752 #undef SCALE_V
753 }
754 if (log2_scale_x > 0) {
755 list->xmin <<= log2_scale_x;
756 list->xmax <<= log2_scale_x;
757 } else {
758 list->xmin = arith_rshift(list->xmin, -log2_scale_x);
759 list->xmax = arith_rshift(list->xmax, -log2_scale_x);
760 }
761 }
762 pcpath->id = gs_next_ids(pcpath->path.memory, 1); /* path changed => change id */
763 return 0;
764 }
765
766 /* ------ Clipping list routines ------ */
767
768 /* Initialize a clip list. */
769 void
gx_clip_list_init(gx_clip_list * clp)770 gx_clip_list_init(gx_clip_list * clp)
771 {
772 *clp = clip_list_empty;
773 }
774
775 /* Initialize a clip list to a rectangle. */
776 /* The supplied rectangle may not be oriented correctly, */
777 /* but it will be oriented correctly upon return. */
778 static void
gx_clip_list_from_rectangle(register gx_clip_list * clp,register gs_fixed_rect * rp)779 gx_clip_list_from_rectangle(register gx_clip_list * clp,
780 register gs_fixed_rect * rp)
781 {
782 gx_clip_list_init(clp);
783 if (rp->p.x > rp->q.x) {
784 fixed t = rp->p.x;
785
786 rp->p.x = rp->q.x;
787 rp->q.x = t;
788 }
789 if (rp->p.y > rp->q.y) {
790 fixed t = rp->p.y;
791
792 rp->p.y = rp->q.y;
793 rp->q.y = t;
794 }
795 clp->single.xmin = clp->xmin = fixed2int_var(rp->p.x);
796 clp->single.ymin = fixed2int_var(rp->p.y);
797 /* Handle degenerate rectangles specially. */
798 clp->single.xmax = clp->xmax =
799 (rp->q.x == rp->p.x ? clp->single.xmin :
800 fixed2int_var_ceiling(rp->q.x));
801 clp->single.ymax =
802 (rp->q.y == rp->p.y ? clp->single.ymin :
803 fixed2int_var_ceiling(rp->q.y));
804 clp->count = 1;
805 }
806
807 /* Start enumerating a clipping path. */
808 int
gx_cpath_enum_init(gs_cpath_enum * penum,const gx_clip_path * pcpath)809 gx_cpath_enum_init(gs_cpath_enum * penum, const gx_clip_path * pcpath)
810 {
811 if ((penum->using_path = pcpath->path_valid)) {
812 gx_path_enum_init(&penum->path_enum, &pcpath->path);
813 penum->rp = penum->visit = 0;
814 penum->first_visit = visit_left;
815 } else {
816 gx_path empty_path;
817 gx_clip_list *clp = gx_cpath_list_private(pcpath);
818 gx_clip_rect *head = (clp->count <= 1 ? &clp->single : clp->head);
819 gx_clip_rect *rp;
820
821 /* Initialize the pointers in the path_enum properly. */
822 gx_path_init_local(&empty_path, pcpath->path.memory);
823 gx_path_enum_init(&penum->path_enum, &empty_path);
824 penum->first_visit = visit_left;
825 penum->visit = head;
826 for (rp = head; rp != 0; rp = rp->next)
827 rp->to_visit =
828 (rp->xmin < rp->xmax && rp->ymin < rp->ymax ?
829 visit_left | visit_right : 0);
830 penum->rp = 0; /* scan will initialize */
831 penum->any_rectangles = false;
832 penum->state = cpe_scan;
833 penum->have_line = false;
834 }
835 return 0;
836 }
837
838 /* Enumerate the next segment of a clipping path. */
839 /* In general, this produces a path made up of zillions of tiny lines. */
840 int
gx_cpath_enum_next(gs_cpath_enum * penum,gs_fixed_point pts[3])841 gx_cpath_enum_next(gs_cpath_enum * penum, gs_fixed_point pts[3])
842 {
843 if (penum->using_path)
844 return gx_path_enum_next(&penum->path_enum, pts);
845 #define set_pt(xi, yi)\
846 (pts[0].x = int2fixed(xi), pts[0].y = int2fixed(yi))
847 #define set_line(xi, yi)\
848 (penum->line_end.x = (xi), penum->line_end.y = (yi), penum->have_line = true)
849 if (penum->have_line) {
850 set_pt(penum->line_end.x, penum->line_end.y);
851 penum->have_line = false;
852 return gs_pe_lineto;
853 } {
854 gx_clip_rect *visit = penum->visit;
855 gx_clip_rect *rp = penum->rp;
856 cpe_visit_t first_visit = penum->first_visit;
857 cpe_state_t state = penum->state;
858 gx_clip_rect *look;
859 int code;
860
861 switch (state) {
862
863 case cpe_scan:
864 /* Look for the start of an edge to trace. */
865 for (; visit != 0; visit = visit->next) {
866 if (visit->to_visit & visit_left) {
867 set_pt(visit->xmin, visit->ymin);
868 first_visit = visit_left;
869 state = cpe_left;
870 } else if (visit->to_visit & visit_right) {
871 set_pt(visit->xmax, visit->ymax);
872 first_visit = visit_right;
873 state = cpe_right;
874 } else
875 continue;
876 rp = visit;
877 code = gs_pe_moveto;
878 penum->any_rectangles = true;
879 goto out;
880 }
881 /* We've enumerated all the edges. */
882 state = cpe_done;
883 if (!penum->any_rectangles) {
884 /* We didn't have any rectangles. */
885 set_pt(fixed_0, fixed_0);
886 code = gs_pe_moveto;
887 break;
888 }
889 /* falls through */
890
891 case cpe_done:
892 /* All done. */
893 code = 0;
894 break;
895
896 /* We can't use the BEGIN ... END hack here: we need to be able to break. */
897 #define return_line(px, py)\
898 set_pt(px, py); code = gs_pe_lineto; break
899
900 case cpe_left:
901
902 left: /* Trace upward along a left edge. */
903 /* We're at the lower left corner of rp. */
904 rp->to_visit &= ~visit_left;
905 /* Look for an adjacent rectangle above rp. */
906 for (look = rp;
907 (look = look->next) != 0 &&
908 (look->ymin == rp->ymin ||
909 (look->ymin == rp->ymax && look->xmax <= rp->xmin));
910 );
911 /* Now we know look->ymin >= rp->ymax. */
912 if (look == 0 || look->ymin > rp->ymax ||
913 look->xmin >= rp->xmax
914 ) { /* No adjacent rectangle, switch directions. */
915 state =
916 (rp == visit && first_visit == visit_right ? cpe_close :
917 (set_line(rp->xmax, rp->ymax), cpe_right));
918 return_line(rp->xmin, rp->ymax);
919 }
920 /* We found an adjacent rectangle. */
921 /* See if it also adjoins a rectangle to the left of rp. */
922 {
923 gx_clip_rect *prev = rp->prev;
924 gx_clip_rect *cur = rp;
925
926 if (prev != 0 && prev->ymax == rp->ymax &&
927 look->xmin < prev->xmax
928 ) { /* There's an adjoining rectangle as well. */
929 /* Switch directions. */
930 rp = prev;
931 state =
932 (rp == visit && first_visit == visit_right ? cpe_close :
933 (set_line(prev->xmax, prev->ymax), cpe_right));
934 return_line(cur->xmin, cur->ymax);
935 }
936 rp = look;
937 if (rp == visit && first_visit == visit_left)
938 state = cpe_close;
939 else if (rp->xmin == cur->xmin)
940 goto left;
941 else
942 set_line(rp->xmin, rp->ymin);
943 return_line(cur->xmin, cur->ymax);
944 }
945
946 case cpe_right:
947
948 right: /* Trace downward along a right edge. */
949 /* We're at the upper right corner of rp. */
950 rp->to_visit &= ~visit_right;
951 /* Look for an adjacent rectangle below rp. */
952 for (look = rp;
953 (look = look->prev) != 0 &&
954 (look->ymax == rp->ymax ||
955 (look->ymax == rp->ymin && look->xmin >= rp->xmax));
956 );
957 /* Now we know look->ymax <= rp->ymin. */
958 if (look == 0 || look->ymax < rp->ymin ||
959 look->xmax <= rp->xmin
960 ) { /* No adjacent rectangle, switch directions. */
961 state =
962 (rp == visit && first_visit == visit_left ? cpe_close :
963 (set_line(rp->xmin, rp->ymin), cpe_left));
964 return_line(rp->xmax, rp->ymin);
965 }
966 /* We found an adjacent rectangle. */
967 /* See if it also adjoins a rectangle to the right of rp. */
968 {
969 gx_clip_rect *next = rp->next;
970 gx_clip_rect *cur = rp;
971
972 if (next != 0 && next->ymin == rp->ymin &&
973 look->xmax > next->xmin
974 ) { /* There's an adjoining rectangle as well. */
975 /* Switch directions. */
976 rp = next;
977 state =
978 (rp == visit && first_visit == visit_left ? cpe_close :
979 (set_line(next->xmin, next->ymin), cpe_left));
980 return_line(cur->xmax, cur->ymin);
981 }
982 rp = look;
983 if (rp == visit && first_visit == visit_right)
984 state = cpe_close;
985 else if (rp->xmax == cur->xmax)
986 goto right;
987 else
988 set_line(rp->xmax, rp->ymax);
989 return_line(cur->xmax, cur->ymin);
990 }
991
992 #undef return_line
993
994 case cpe_close:
995 /* We've gone all the way around an edge. */
996 code = gs_pe_closepath;
997 state = cpe_scan;
998 break;
999
1000 default:
1001 return_error(gs_error_unknownerror);
1002 }
1003
1004 out: /* Store the state before exiting. */
1005 penum->visit = visit;
1006 penum->rp = rp;
1007 penum->first_visit = first_visit;
1008 penum->state = state;
1009 return code;
1010 }
1011 #undef set_pt
1012 #undef set_line
1013 }
1014 segment_notes
gx_cpath_enum_notes(const gs_cpath_enum * penum)1015 gx_cpath_enum_notes(const gs_cpath_enum * penum)
1016 {
1017 return sn_none;
1018 }
1019
1020 /* Free a clip list. */
1021 void
gx_clip_list_free(gx_clip_list * clp,gs_memory_t * mem)1022 gx_clip_list_free(gx_clip_list * clp, gs_memory_t * mem)
1023 {
1024 gx_clip_rect *rp = clp->tail;
1025
1026 while (rp != 0) {
1027 gx_clip_rect *prev = rp->prev;
1028
1029 gs_free_object(mem, rp, "gx_clip_list_free");
1030 rp = prev;
1031 }
1032 gx_clip_list_init(clp);
1033 }
1034
1035 /* Check whether a rectangle has a non-empty intersection with a clipping patch. */
1036 bool
gx_cpath_rect_visible(gx_clip_path * pcpath,gs_int_rect * prect)1037 gx_cpath_rect_visible(gx_clip_path * pcpath, gs_int_rect *prect)
1038 {
1039 const gx_clip_rect *pr;
1040 const gx_clip_list *list = &pcpath->rect_list->list;
1041
1042 switch (list->count) {
1043 case 0:
1044 return false;
1045 case 1:
1046 pr = &list->single;
1047 break;
1048 default:
1049 pr = list->head;
1050 }
1051 for (; pr != 0; pr = pr->next) {
1052 if (pr->xmin > prect->q.x)
1053 continue;
1054 if (pr->xmax < prect->p.x)
1055 continue;
1056 if (pr->ymin > prect->q.y)
1057 continue;
1058 if (pr->ymax < prect->p.y)
1059 continue;
1060 return true;
1061 }
1062 return false;
1063 }
1064
1065 int
gx_cpath_copy(const gx_clip_path * from,gx_clip_path * pcpath)1066 gx_cpath_copy(const gx_clip_path * from, gx_clip_path * pcpath)
1067 { /* *pcpath must be initialized. */
1068 gx_clip_rect *r, *s;
1069 gx_clip_list *l = &pcpath->rect_list->list;
1070
1071 pcpath->path_valid = false;
1072 /* NOTE: pcpath->path still contains the old path. */
1073 if (pcpath->path_list)
1074 rc_decrement(pcpath->path_list, "gx_cpath_copy");
1075 pcpath->path_list = NULL;
1076 pcpath->rule = from->rule;
1077 pcpath->outer_box = from->outer_box;
1078 pcpath->inner_box = from->inner_box;
1079 l->single = from->rect_list->list.single;
1080 for (r = from->rect_list->list.head; r != NULL; r = r->next) {
1081 s = gs_alloc_struct(from->rect_list->rc.memory, gx_clip_rect, &st_clip_rect, "gx_cpath_copy");
1082 if (s == NULL)
1083 return_error(gs_error_VMerror);
1084 *s = *r;
1085 s->next = NULL;
1086 if (l->tail) {
1087 s->prev = l->tail;
1088 l->tail->next = s;
1089 } else {
1090 l->head = s;
1091 s->prev = NULL;
1092 }
1093 l->tail = s;
1094 }
1095 l->count = from->rect_list->list.count;
1096 return 0;
1097 }
1098
1099 /* ------ Debugging printout ------ */
1100
1101 #ifdef DEBUG
1102
1103 /* Print a clipping list. */
1104 static void
gx_clip_list_print(const gx_clip_list * list)1105 gx_clip_list_print(const gx_clip_list *list)
1106 {
1107 const gx_clip_rect *pr;
1108
1109 dlprintf3(" list count=%d xmin=%d xmax=%d\n",
1110 list->count, list->xmin, list->xmax);
1111 switch (list->count) {
1112 case 0:
1113 pr = 0;
1114 break;
1115 case 1:
1116 pr = &list->single;
1117 break;
1118 default:
1119 pr = list->head;
1120 }
1121 for (; pr != 0; pr = pr->next)
1122 dlprintf4(" rect: (%d,%d),(%d,%d)\n",
1123 pr->xmin, pr->ymin, pr->xmax, pr->ymax);
1124 }
1125
1126 /* Print a clipping path */
1127 void
gx_cpath_print(const gx_clip_path * pcpath)1128 gx_cpath_print(const gx_clip_path * pcpath)
1129 {
1130 if (pcpath->path_valid)
1131 gx_path_print(&pcpath->path);
1132 else
1133 dlputs(" (path not valid)\n");
1134 dlprintf4(" inner_box=(%g,%g),(%g,%g)\n",
1135 fixed2float(pcpath->inner_box.p.x),
1136 fixed2float(pcpath->inner_box.p.y),
1137 fixed2float(pcpath->inner_box.q.x),
1138 fixed2float(pcpath->inner_box.q.y));
1139 dlprintf4(" outer_box=(%g,%g),(%g,%g)",
1140 fixed2float(pcpath->outer_box.p.x),
1141 fixed2float(pcpath->outer_box.p.y),
1142 fixed2float(pcpath->outer_box.q.x),
1143 fixed2float(pcpath->outer_box.q.y));
1144 dprintf2(" rule=%d list.refct=%ld\n",
1145 pcpath->rule, pcpath->rect_list->rc.ref_count);
1146 gx_clip_list_print(gx_cpath_list(pcpath));
1147 }
1148
1149 #endif /* DEBUG */
1150