Line data Source code
1 : /*
2 : * Copyright 1987, 1988, 1989, 1998 The Open Group
3 : *
4 : * Permission to use, copy, modify, distribute, and sell this software and its
5 : * documentation for any purpose is hereby granted without fee, provided that
6 : * the above copyright notice appear in all copies and that both that
7 : * copyright notice and this permission notice appear in supporting
8 : * documentation.
9 : *
10 : * The above copyright notice and this permission notice shall be included in
11 : * all copies or substantial portions of the Software.
12 : *
13 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 : * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
17 : * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
18 : * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19 : *
20 : * Except as contained in this notice, the name of The Open Group shall not be
21 : * used in advertising or otherwise to promote the sale, use or other dealings
22 : * in this Software without prior written authorization from The Open Group.
23 : *
24 : * Copyright 1987, 1988, 1989 by
25 : * Digital Equipment Corporation, Maynard, Massachusetts.
26 : *
27 : * All Rights Reserved
28 : *
29 : * Permission to use, copy, modify, and distribute this software and its
30 : * documentation for any purpose and without fee is hereby granted,
31 : * provided that the above copyright notice appear in all copies and that
32 : * both that copyright notice and this permission notice appear in
33 : * supporting documentation, and that the name of Digital not be
34 : * used in advertising or publicity pertaining to distribution of the
35 : * software without specific, written prior permission.
36 : *
37 : * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
38 : * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
39 : * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
40 : * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
41 : * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
42 : * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
43 : * SOFTWARE.
44 : *
45 : * Copyright © 1998 Keith Packard
46 : *
47 : * Permission to use, copy, modify, distribute, and sell this software and its
48 : * documentation for any purpose is hereby granted without fee, provided that
49 : * the above copyright notice appear in all copies and that both that
50 : * copyright notice and this permission notice appear in supporting
51 : * documentation, and that the name of Keith Packard not be used in
52 : * advertising or publicity pertaining to distribution of the software without
53 : * specific, written prior permission. Keith Packard makes no
54 : * representations about the suitability of this software for any purpose. It
55 : * is provided "as is" without express or implied warranty.
56 : *
57 : * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
58 : * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
59 : * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
60 : * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
61 : * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
62 : * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
63 : * PERFORMANCE OF THIS SOFTWARE.
64 : */
65 :
66 : #include <stdlib.h>
67 : #include <limits.h>
68 : #include <string.h>
69 : #include <stdio.h>
70 : #include "pixman-private.h"
71 :
72 : #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
73 : /* not a region */
74 : #define PIXREGION_NAR(reg) ((reg)->data == pixman_broken_data)
75 : #define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
76 : #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
77 : #define PIXREGION_RECTS(reg) \
78 : ((reg)->data ? (box_type_t *)((reg)->data + 1) \
79 : : &(reg)->extents)
80 : #define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))
81 : #define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])
82 : #define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)
83 : #define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)
84 :
85 : #define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)
86 : #define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2)
87 :
88 : #ifdef DEBUG
89 :
90 : #define GOOD(reg) \
91 : do \
92 : { \
93 : if (!PREFIX (_selfcheck (reg))) \
94 : _pixman_log_error (FUNC, "Malformed region " # reg); \
95 : } while (0)
96 :
97 : #else
98 :
99 : #define GOOD(reg)
100 :
101 : #endif
102 :
103 : static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };
104 : static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };
105 : #if defined (__llvm__) && !defined (__clang__)
106 : static const volatile region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
107 : #else
108 : static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
109 : #endif
110 :
111 : static box_type_t *pixman_region_empty_box =
112 : (box_type_t *)&PREFIX (_empty_box_);
113 : static region_data_type_t *pixman_region_empty_data =
114 : (region_data_type_t *)&PREFIX (_empty_data_);
115 : static region_data_type_t *pixman_broken_data =
116 : (region_data_type_t *)&PREFIX (_broken_data_);
117 :
118 : static pixman_bool_t
119 : pixman_break (region_type_t *region);
120 :
121 : /*
122 : * The functions in this file implement the Region abstraction used extensively
123 : * throughout the X11 sample server. A Region is simply a set of disjoint
124 : * (non-overlapping) rectangles, plus an "extent" rectangle which is the
125 : * smallest single rectangle that contains all the non-overlapping rectangles.
126 : *
127 : * A Region is implemented as a "y-x-banded" array of rectangles. This array
128 : * imposes two degrees of order. First, all rectangles are sorted by top side
129 : * y coordinate first (y1), and then by left side x coordinate (x1).
130 : *
131 : * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
132 : * band has the same top y coordinate (y1), and each has the same bottom y
133 : * coordinate (y2). Thus all rectangles in a band differ only in their left
134 : * and right side (x1 and x2). Bands are implicit in the array of rectangles:
135 : * there is no separate list of band start pointers.
136 : *
137 : * The y-x band representation does not minimize rectangles. In particular,
138 : * if a rectangle vertically crosses a band (the rectangle has scanlines in
139 : * the y1 to y2 area spanned by the band), then the rectangle may be broken
140 : * down into two or more smaller rectangles stacked one atop the other.
141 : *
142 : * ----------- -----------
143 : * | | | | band 0
144 : * | | -------- ----------- --------
145 : * | | | | in y-x banded | | | | band 1
146 : * | | | | form is | | | |
147 : * ----------- | | ----------- --------
148 : * | | | | band 2
149 : * -------- --------
150 : *
151 : * An added constraint on the rectangles is that they must cover as much
152 : * horizontal area as possible: no two rectangles within a band are allowed
153 : * to touch.
154 : *
155 : * Whenever possible, bands will be merged together to cover a greater vertical
156 : * distance (and thus reduce the number of rectangles). Two bands can be merged
157 : * only if the bottom of one touches the top of the other and they have
158 : * rectangles in the same places (of the same width, of course).
159 : *
160 : * Adam de Boor wrote most of the original region code. Joel McCormack
161 : * substantially modified or rewrote most of the core arithmetic routines, and
162 : * added pixman_region_validate in order to support several speed improvements
163 : * to pixman_region_validate_tree. Bob Scheifler changed the representation
164 : * to be more compact when empty or a single rectangle, and did a bunch of
165 : * gratuitous reformatting. Carl Worth did further gratuitous reformatting
166 : * while re-merging the server and client region code into libpixregion.
167 : * Soren Sandmann did even more gratuitous reformatting.
168 : */
169 :
170 : /* true iff two Boxes overlap */
171 : #define EXTENTCHECK(r1, r2) \
172 : (!( ((r1)->x2 <= (r2)->x1) || \
173 : ((r1)->x1 >= (r2)->x2) || \
174 : ((r1)->y2 <= (r2)->y1) || \
175 : ((r1)->y1 >= (r2)->y2) ) )
176 :
177 : /* true iff (x,y) is in Box */
178 : #define INBOX(r, x, y) \
179 : ( ((r)->x2 > x) && \
180 : ((r)->x1 <= x) && \
181 : ((r)->y2 > y) && \
182 : ((r)->y1 <= y) )
183 :
184 : /* true iff Box r1 contains Box r2 */
185 : #define SUBSUMES(r1, r2) \
186 : ( ((r1)->x1 <= (r2)->x1) && \
187 : ((r1)->x2 >= (r2)->x2) && \
188 : ((r1)->y1 <= (r2)->y1) && \
189 : ((r1)->y2 >= (r2)->y2) )
190 :
191 : static size_t
192 3743 : PIXREGION_SZOF (size_t n)
193 : {
194 3743 : size_t size = n * sizeof(box_type_t);
195 :
196 3743 : if (n > UINT32_MAX / sizeof(box_type_t))
197 0 : return 0;
198 :
199 3743 : if (sizeof(region_data_type_t) > UINT32_MAX - size)
200 0 : return 0;
201 :
202 3743 : return size + sizeof(region_data_type_t);
203 : }
204 :
205 : static region_data_type_t *
206 3465 : alloc_data (size_t n)
207 : {
208 3465 : size_t sz = PIXREGION_SZOF (n);
209 :
210 3465 : if (!sz)
211 0 : return NULL;
212 :
213 3465 : return malloc (sz);
214 : }
215 :
216 : #define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)
217 :
218 : #define RECTALLOC_BAIL(region, n, bail) \
219 : do \
220 : { \
221 : if (!(region)->data || \
222 : (((region)->data->numRects + (n)) > (region)->data->size)) \
223 : { \
224 : if (!pixman_rect_alloc (region, n)) \
225 : goto bail; \
226 : } \
227 : } while (0)
228 :
229 : #define RECTALLOC(region, n) \
230 : do \
231 : { \
232 : if (!(region)->data || \
233 : (((region)->data->numRects + (n)) > (region)->data->size)) \
234 : { \
235 : if (!pixman_rect_alloc (region, n)) { \
236 : return FALSE; \
237 : } \
238 : } \
239 : } while (0)
240 :
241 : #define ADDRECT(next_rect, nx1, ny1, nx2, ny2) \
242 : do \
243 : { \
244 : next_rect->x1 = nx1; \
245 : next_rect->y1 = ny1; \
246 : next_rect->x2 = nx2; \
247 : next_rect->y2 = ny2; \
248 : next_rect++; \
249 : } \
250 : while (0)
251 :
252 : #define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2) \
253 : do \
254 : { \
255 : if (!(region)->data || \
256 : ((region)->data->numRects == (region)->data->size)) \
257 : { \
258 : if (!pixman_rect_alloc (region, 1)) \
259 : return FALSE; \
260 : next_rect = PIXREGION_TOP (region); \
261 : } \
262 : ADDRECT (next_rect, nx1, ny1, nx2, ny2); \
263 : region->data->numRects++; \
264 : critical_if_fail (region->data->numRects <= region->data->size); \
265 : } while (0)
266 :
267 : #define DOWNSIZE(reg, numRects) \
268 : do \
269 : { \
270 : if (((numRects) < ((reg)->data->size >> 1)) && \
271 : ((reg)->data->size > 50)) \
272 : { \
273 : region_data_type_t * new_data; \
274 : size_t data_size = PIXREGION_SZOF (numRects); \
275 : \
276 : if (!data_size) \
277 : { \
278 : new_data = NULL; \
279 : } \
280 : else \
281 : { \
282 : new_data = (region_data_type_t *) \
283 : realloc ((reg)->data, data_size); \
284 : } \
285 : \
286 : if (new_data) \
287 : { \
288 : new_data->size = (numRects); \
289 : (reg)->data = new_data; \
290 : } \
291 : } \
292 : } while (0)
293 :
294 : PIXMAN_EXPORT pixman_bool_t
295 1717 : PREFIX (_equal) (region_type_t *reg1, region_type_t *reg2)
296 : {
297 : int i;
298 : box_type_t *rects1;
299 : box_type_t *rects2;
300 :
301 : /*
302 : * If the region is empty the extents are undefined so we need to check
303 : * for empty before comparing the extents.
304 : */
305 1717 : if (PIXREGION_NIL (reg1) && PIXREGION_NIL(reg2))
306 1083 : return TRUE;
307 :
308 634 : if (reg1->extents.x1 != reg2->extents.x1)
309 105 : return FALSE;
310 :
311 529 : if (reg1->extents.x2 != reg2->extents.x2)
312 101 : return FALSE;
313 :
314 428 : if (reg1->extents.y1 != reg2->extents.y1)
315 0 : return FALSE;
316 :
317 428 : if (reg1->extents.y2 != reg2->extents.y2)
318 0 : return FALSE;
319 :
320 428 : if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2))
321 0 : return FALSE;
322 :
323 428 : rects1 = PIXREGION_RECTS (reg1);
324 428 : rects2 = PIXREGION_RECTS (reg2);
325 :
326 888 : for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++)
327 : {
328 466 : if (rects1[i].x1 != rects2[i].x1)
329 6 : return FALSE;
330 :
331 460 : if (rects1[i].x2 != rects2[i].x2)
332 0 : return FALSE;
333 :
334 460 : if (rects1[i].y1 != rects2[i].y1)
335 0 : return FALSE;
336 :
337 460 : if (rects1[i].y2 != rects2[i].y2)
338 0 : return FALSE;
339 : }
340 :
341 422 : return TRUE;
342 : }
343 :
344 : int
345 0 : PREFIX (_print) (region_type_t *rgn)
346 : {
347 : int num, size;
348 : int i;
349 : box_type_t * rects;
350 :
351 0 : num = PIXREGION_NUMRECTS (rgn);
352 0 : size = PIXREGION_SIZE (rgn);
353 0 : rects = PIXREGION_RECTS (rgn);
354 :
355 0 : fprintf (stderr, "num: %d size: %d\n", num, size);
356 0 : fprintf (stderr, "extents: %d %d %d %d\n",
357 0 : rgn->extents.x1,
358 0 : rgn->extents.y1,
359 0 : rgn->extents.x2,
360 0 : rgn->extents.y2);
361 :
362 0 : for (i = 0; i < num; i++)
363 : {
364 0 : fprintf (stderr, "%d %d %d %d \n",
365 0 : rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
366 : }
367 :
368 0 : fprintf (stderr, "\n");
369 :
370 0 : return(num);
371 : }
372 :
373 :
374 : PIXMAN_EXPORT void
375 42460 : PREFIX (_init) (region_type_t *region)
376 : {
377 42460 : region->extents = *pixman_region_empty_box;
378 42460 : region->data = pixman_region_empty_data;
379 42460 : }
380 :
381 : PIXMAN_EXPORT void
382 3736 : PREFIX (_init_rect) (region_type_t * region,
383 : int x,
384 : int y,
385 : unsigned int width,
386 : unsigned int height)
387 : {
388 3736 : region->extents.x1 = x;
389 3736 : region->extents.y1 = y;
390 3736 : region->extents.x2 = x + width;
391 3736 : region->extents.y2 = y + height;
392 :
393 3736 : if (!GOOD_RECT (®ion->extents))
394 : {
395 468 : if (BAD_RECT (®ion->extents))
396 : _pixman_log_error (FUNC, "Invalid rectangle passed");
397 468 : PREFIX (_init) (region);
398 468 : return;
399 : }
400 :
401 3268 : region->data = NULL;
402 : }
403 :
404 : PIXMAN_EXPORT void
405 0 : PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents)
406 : {
407 0 : if (!GOOD_RECT (extents))
408 : {
409 0 : if (BAD_RECT (extents))
410 : _pixman_log_error (FUNC, "Invalid rectangle passed");
411 0 : PREFIX (_init) (region);
412 0 : return;
413 : }
414 0 : region->extents = *extents;
415 :
416 0 : region->data = NULL;
417 : }
418 :
419 : PIXMAN_EXPORT void
420 44982 : PREFIX (_fini) (region_type_t *region)
421 : {
422 : GOOD (region);
423 44982 : FREE_DATA (region);
424 44982 : }
425 :
426 : PIXMAN_EXPORT int
427 3787 : PREFIX (_n_rects) (region_type_t *region)
428 : {
429 3787 : return PIXREGION_NUMRECTS (region);
430 : }
431 :
432 : PIXMAN_EXPORT box_type_t *
433 9207 : PREFIX (_rectangles) (region_type_t *region,
434 : int *n_rects)
435 : {
436 9207 : if (n_rects)
437 9207 : *n_rects = PIXREGION_NUMRECTS (region);
438 :
439 9207 : return PIXREGION_RECTS (region);
440 : }
441 :
442 : static pixman_bool_t
443 0 : pixman_break (region_type_t *region)
444 : {
445 0 : FREE_DATA (region);
446 :
447 0 : region->extents = *pixman_region_empty_box;
448 0 : region->data = pixman_broken_data;
449 :
450 0 : return FALSE;
451 : }
452 :
453 : static pixman_bool_t
454 2913 : pixman_rect_alloc (region_type_t * region,
455 : int n)
456 : {
457 : region_data_type_t *data;
458 :
459 2913 : if (!region->data)
460 : {
461 36 : n++;
462 36 : region->data = alloc_data (n);
463 :
464 36 : if (!region->data)
465 0 : return pixman_break (region);
466 :
467 36 : region->data->numRects = 1;
468 36 : *PIXREGION_BOXPTR (region) = region->extents;
469 : }
470 2877 : else if (!region->data->size)
471 : {
472 2738 : region->data = alloc_data (n);
473 :
474 2738 : if (!region->data)
475 0 : return pixman_break (region);
476 :
477 2738 : region->data->numRects = 0;
478 : }
479 : else
480 : {
481 : size_t data_size;
482 :
483 139 : if (n == 1)
484 : {
485 137 : n = region->data->numRects;
486 137 : if (n > 500) /* XXX pick numbers out of a hat */
487 0 : n = 250;
488 : }
489 :
490 139 : n += region->data->numRects;
491 139 : data_size = PIXREGION_SZOF (n);
492 :
493 139 : if (!data_size)
494 : {
495 0 : data = NULL;
496 : }
497 : else
498 : {
499 139 : data = (region_data_type_t *)
500 139 : realloc (region->data, PIXREGION_SZOF (n));
501 : }
502 :
503 139 : if (!data)
504 0 : return pixman_break (region);
505 :
506 139 : region->data = data;
507 : }
508 :
509 2913 : region->data->size = n;
510 :
511 2913 : return TRUE;
512 : }
513 :
514 : PIXMAN_EXPORT pixman_bool_t
515 20573 : PREFIX (_copy) (region_type_t *dst, region_type_t *src)
516 : {
517 : GOOD (dst);
518 : GOOD (src);
519 :
520 20573 : if (dst == src)
521 1295 : return TRUE;
522 :
523 19278 : dst->extents = src->extents;
524 :
525 19278 : if (!src->data || !src->data->size)
526 : {
527 18391 : FREE_DATA (dst);
528 18391 : dst->data = src->data;
529 18391 : return TRUE;
530 : }
531 :
532 887 : if (!dst->data || (dst->data->size < src->data->numRects))
533 : {
534 691 : FREE_DATA (dst);
535 :
536 691 : dst->data = alloc_data (src->data->numRects);
537 :
538 691 : if (!dst->data)
539 0 : return pixman_break (dst);
540 :
541 691 : dst->data->size = src->data->numRects;
542 : }
543 :
544 887 : dst->data->numRects = src->data->numRects;
545 :
546 887 : memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),
547 887 : dst->data->numRects * sizeof(box_type_t));
548 :
549 887 : return TRUE;
550 : }
551 :
552 : /*======================================================================
553 : * Generic Region Operator
554 : *====================================================================*/
555 :
556 : /*-
557 : *-----------------------------------------------------------------------
558 : * pixman_coalesce --
559 : * Attempt to merge the boxes in the current band with those in the
560 : * previous one. We are guaranteed that the current band extends to
561 : * the end of the rects array. Used only by pixman_op.
562 : *
563 : * Results:
564 : * The new index for the previous band.
565 : *
566 : * Side Effects:
567 : * If coalescing takes place:
568 : * - rectangles in the previous band will have their y2 fields
569 : * altered.
570 : * - region->data->numRects will be decreased.
571 : *
572 : *-----------------------------------------------------------------------
573 : */
574 : static inline int
575 3257 : pixman_coalesce (region_type_t * region, /* Region to coalesce */
576 : int prev_start, /* Index of start of previous band */
577 : int cur_start) /* Index of start of current band */
578 : {
579 : box_type_t *prev_box; /* Current box in previous band */
580 : box_type_t *cur_box; /* Current box in current band */
581 : int numRects; /* Number rectangles in both bands */
582 : int y2; /* Bottom of current band */
583 :
584 : /*
585 : * Figure out how many rectangles are in the band.
586 : */
587 3257 : numRects = cur_start - prev_start;
588 : critical_if_fail (numRects == region->data->numRects - cur_start);
589 :
590 3257 : if (!numRects) return cur_start;
591 :
592 : /*
593 : * The bands may only be coalesced if the bottom of the previous
594 : * matches the top scanline of the current.
595 : */
596 2503 : prev_box = PIXREGION_BOX (region, prev_start);
597 2503 : cur_box = PIXREGION_BOX (region, cur_start);
598 2503 : if (prev_box->y2 != cur_box->y1) return cur_start;
599 :
600 : /*
601 : * Make sure the bands have boxes in the same places. This
602 : * assumes that boxes have been added in such a way that they
603 : * cover the most area possible. I.e. two boxes in a band must
604 : * have some horizontal space between them.
605 : */
606 1959 : y2 = cur_box->y2;
607 :
608 : do
609 : {
610 2075 : if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2))
611 1201 : return (cur_start);
612 :
613 874 : prev_box++;
614 874 : cur_box++;
615 874 : numRects--;
616 : }
617 874 : while (numRects);
618 :
619 : /*
620 : * The bands may be merged, so set the bottom y of each box
621 : * in the previous band to the bottom y of the current band.
622 : */
623 758 : numRects = cur_start - prev_start;
624 758 : region->data->numRects -= numRects;
625 :
626 : do
627 : {
628 796 : prev_box--;
629 796 : prev_box->y2 = y2;
630 796 : numRects--;
631 : }
632 796 : while (numRects);
633 :
634 758 : return prev_start;
635 : }
636 :
637 : /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
638 :
639 : #define COALESCE(new_reg, prev_band, cur_band) \
640 : do \
641 : { \
642 : if (cur_band - prev_band == new_reg->data->numRects - cur_band) \
643 : prev_band = pixman_coalesce (new_reg, prev_band, cur_band); \
644 : else \
645 : prev_band = cur_band; \
646 : } while (0)
647 :
648 : /*-
649 : *-----------------------------------------------------------------------
650 : * pixman_region_append_non_o --
651 : * Handle a non-overlapping band for the union and subtract operations.
652 : * Just adds the (top/bottom-clipped) rectangles into the region.
653 : * Doesn't have to check for subsumption or anything.
654 : *
655 : * Results:
656 : * None.
657 : *
658 : * Side Effects:
659 : * region->data->numRects is incremented and the rectangles overwritten
660 : * with the rectangles we're passed.
661 : *
662 : *-----------------------------------------------------------------------
663 : */
664 : static inline pixman_bool_t
665 2866 : pixman_region_append_non_o (region_type_t * region,
666 : box_type_t * r,
667 : box_type_t * r_end,
668 : int y1,
669 : int y2)
670 : {
671 : box_type_t *next_rect;
672 : int new_rects;
673 :
674 2866 : new_rects = r_end - r;
675 :
676 : critical_if_fail (y1 < y2);
677 : critical_if_fail (new_rects != 0);
678 :
679 : /* Make sure we have enough space for all rectangles to be added */
680 2866 : RECTALLOC (region, new_rects);
681 2866 : next_rect = PIXREGION_TOP (region);
682 2866 : region->data->numRects += new_rects;
683 :
684 : do
685 : {
686 : critical_if_fail (r->x1 < r->x2);
687 3426 : ADDRECT (next_rect, r->x1, y1, r->x2, y2);
688 3426 : r++;
689 : }
690 3426 : while (r != r_end);
691 :
692 2866 : return TRUE;
693 : }
694 :
695 : #define FIND_BAND(r, r_band_end, r_end, ry1) \
696 : do \
697 : { \
698 : ry1 = r->y1; \
699 : r_band_end = r + 1; \
700 : while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) { \
701 : r_band_end++; \
702 : } \
703 : } while (0)
704 :
705 : #define APPEND_REGIONS(new_reg, r, r_end) \
706 : do \
707 : { \
708 : int new_rects; \
709 : if ((new_rects = r_end - r)) { \
710 : RECTALLOC_BAIL (new_reg, new_rects, bail); \
711 : memmove ((char *)PIXREGION_TOP (new_reg), (char *)r, \
712 : new_rects * sizeof(box_type_t)); \
713 : new_reg->data->numRects += new_rects; \
714 : } \
715 : } while (0)
716 :
717 : /*-
718 : *-----------------------------------------------------------------------
719 : * pixman_op --
720 : * Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
721 : * pixman_region_subtract, pixman_region_intersect.... Both regions MUST have at least one
722 : * rectangle, and cannot be the same object.
723 : *
724 : * Results:
725 : * TRUE if successful.
726 : *
727 : * Side Effects:
728 : * The new region is overwritten.
729 : * overlap set to TRUE if overlap_func ever returns TRUE.
730 : *
731 : * Notes:
732 : * The idea behind this function is to view the two regions as sets.
733 : * Together they cover a rectangle of area that this function divides
734 : * into horizontal bands where points are covered only by one region
735 : * or by both. For the first case, the non_overlap_func is called with
736 : * each the band and the band's upper and lower extents. For the
737 : * second, the overlap_func is called to process the entire band. It
738 : * is responsible for clipping the rectangles in the band, though
739 : * this function provides the boundaries.
740 : * At the end of each band, the new region is coalesced, if possible,
741 : * to reduce the number of rectangles in the region.
742 : *
743 : *-----------------------------------------------------------------------
744 : */
745 :
746 : typedef pixman_bool_t (*overlap_proc_ptr) (region_type_t *region,
747 : box_type_t * r1,
748 : box_type_t * r1_end,
749 : box_type_t * r2,
750 : box_type_t * r2_end,
751 : int y1,
752 : int y2);
753 :
754 : static pixman_bool_t
755 2552 : pixman_op (region_type_t * new_reg, /* Place to store result */
756 : region_type_t * reg1, /* First region in operation */
757 : region_type_t * reg2, /* 2d region in operation */
758 : overlap_proc_ptr overlap_func, /* Function to call for over-
759 : * lapping bands */
760 : int append_non1, /* Append non-overlapping bands
761 : * in region 1 ?
762 : */
763 : int append_non2 /* Append non-overlapping bands
764 : * in region 2 ?
765 : */
766 : )
767 : {
768 : box_type_t *r1; /* Pointer into first region */
769 : box_type_t *r2; /* Pointer into 2d region */
770 : box_type_t *r1_end; /* End of 1st region */
771 : box_type_t *r2_end; /* End of 2d region */
772 : int ybot; /* Bottom of intersection */
773 : int ytop; /* Top of intersection */
774 : region_data_type_t *old_data; /* Old data for new_reg */
775 : int prev_band; /* Index of start of
776 : * previous band in new_reg */
777 : int cur_band; /* Index of start of current
778 : * band in new_reg */
779 : box_type_t * r1_band_end; /* End of current band in r1 */
780 : box_type_t * r2_band_end; /* End of current band in r2 */
781 : int top; /* Top of non-overlapping band */
782 : int bot; /* Bottom of non-overlapping band*/
783 : int r1y1; /* Temps for r1->y1 and r2->y1 */
784 : int r2y1;
785 : int new_size;
786 : int numRects;
787 :
788 : /*
789 : * Break any region computed from a broken region
790 : */
791 2552 : if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
792 0 : return pixman_break (new_reg);
793 :
794 : /*
795 : * Initialization:
796 : * set r1, r2, r1_end and r2_end appropriately, save the rectangles
797 : * of the destination region until the end in case it's one of
798 : * the two source regions, then mark the "new" region empty, allocating
799 : * another array of rectangles for it to use.
800 : */
801 :
802 2552 : r1 = PIXREGION_RECTS (reg1);
803 2552 : new_size = PIXREGION_NUMRECTS (reg1);
804 2552 : r1_end = r1 + new_size;
805 :
806 2552 : numRects = PIXREGION_NUMRECTS (reg2);
807 2552 : r2 = PIXREGION_RECTS (reg2);
808 2552 : r2_end = r2 + numRects;
809 :
810 : critical_if_fail (r1 != r1_end);
811 : critical_if_fail (r2 != r2_end);
812 :
813 2552 : old_data = (region_data_type_t *)NULL;
814 :
815 2552 : if (((new_reg == reg1) && (new_size > 1)) ||
816 0 : ((new_reg == reg2) && (numRects > 1)))
817 : {
818 1279 : old_data = new_reg->data;
819 1279 : new_reg->data = pixman_region_empty_data;
820 : }
821 :
822 : /* guess at new size */
823 2552 : if (numRects > new_size)
824 33 : new_size = numRects;
825 :
826 2552 : new_size <<= 1;
827 :
828 2552 : if (!new_reg->data)
829 554 : new_reg->data = pixman_region_empty_data;
830 1998 : else if (new_reg->data->size)
831 0 : new_reg->data->numRects = 0;
832 :
833 2552 : if (new_size > new_reg->data->size)
834 : {
835 2552 : if (!pixman_rect_alloc (new_reg, new_size))
836 : {
837 0 : free (old_data);
838 0 : return FALSE;
839 : }
840 : }
841 :
842 : /*
843 : * Initialize ybot.
844 : * In the upcoming loop, ybot and ytop serve different functions depending
845 : * on whether the band being handled is an overlapping or non-overlapping
846 : * band.
847 : * In the case of a non-overlapping band (only one of the regions
848 : * has points in the band), ybot is the bottom of the most recent
849 : * intersection and thus clips the top of the rectangles in that band.
850 : * ytop is the top of the next intersection between the two regions and
851 : * serves to clip the bottom of the rectangles in the current band.
852 : * For an overlapping band (where the two regions intersect), ytop clips
853 : * the top of the rectangles of both regions and ybot clips the bottoms.
854 : */
855 :
856 2552 : ybot = MIN (r1->y1, r2->y1);
857 :
858 : /*
859 : * prev_band serves to mark the start of the previous band so rectangles
860 : * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
861 : * In the beginning, there is no previous band, so prev_band == cur_band
862 : * (cur_band is set later on, of course, but the first band will always
863 : * start at index 0). prev_band and cur_band must be indices because of
864 : * the possible expansion, and resultant moving, of the new region's
865 : * array of rectangles.
866 : */
867 2552 : prev_band = 0;
868 :
869 : do
870 : {
871 : /*
872 : * This algorithm proceeds one source-band (as opposed to a
873 : * destination band, which is determined by where the two regions
874 : * intersect) at a time. r1_band_end and r2_band_end serve to mark the
875 : * rectangle after the last one in the current band for their
876 : * respective regions.
877 : */
878 : critical_if_fail (r1 != r1_end);
879 : critical_if_fail (r2 != r2_end);
880 :
881 5241 : FIND_BAND (r1, r1_band_end, r1_end, r1y1);
882 5241 : FIND_BAND (r2, r2_band_end, r2_end, r2y1);
883 :
884 : /*
885 : * First handle the band that doesn't intersect, if any.
886 : *
887 : * Note that attention is restricted to one band in the
888 : * non-intersecting region at once, so if a region has n
889 : * bands between the current position and the next place it overlaps
890 : * the other, this entire loop will be passed through n times.
891 : */
892 5241 : if (r1y1 < r2y1)
893 : {
894 2301 : if (append_non1)
895 : {
896 1812 : top = MAX (r1y1, ybot);
897 1812 : bot = MIN (r1->y2, r2y1);
898 1812 : if (top != bot)
899 : {
900 1726 : cur_band = new_reg->data->numRects;
901 1726 : if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))
902 0 : goto bail;
903 1726 : COALESCE (new_reg, prev_band, cur_band);
904 : }
905 : }
906 2301 : ytop = r2y1;
907 : }
908 2940 : else if (r2y1 < r1y1)
909 : {
910 1276 : if (append_non2)
911 : {
912 779 : top = MAX (r2y1, ybot);
913 779 : bot = MIN (r2->y2, r1y1);
914 :
915 779 : if (top != bot)
916 : {
917 96 : cur_band = new_reg->data->numRects;
918 :
919 96 : if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))
920 0 : goto bail;
921 :
922 96 : COALESCE (new_reg, prev_band, cur_band);
923 : }
924 : }
925 1276 : ytop = r1y1;
926 : }
927 : else
928 : {
929 1664 : ytop = r1y1;
930 : }
931 :
932 : /*
933 : * Now see if we've hit an intersecting band. The two bands only
934 : * intersect if ybot > ytop
935 : */
936 5241 : ybot = MIN (r1->y2, r2->y2);
937 5241 : if (ybot > ytop)
938 : {
939 3641 : cur_band = new_reg->data->numRects;
940 :
941 3641 : if (!(*overlap_func)(new_reg,
942 : r1, r1_band_end,
943 : r2, r2_band_end,
944 : ytop, ybot))
945 : {
946 0 : goto bail;
947 : }
948 :
949 3641 : COALESCE (new_reg, prev_band, cur_band);
950 : }
951 :
952 : /*
953 : * If we've finished with a band (y2 == ybot) we skip forward
954 : * in the region to the next band.
955 : */
956 5241 : if (r1->y2 == ybot)
957 4552 : r1 = r1_band_end;
958 :
959 5241 : if (r2->y2 == ybot)
960 2302 : r2 = r2_band_end;
961 :
962 : }
963 5241 : while (r1 != r1_end && r2 != r2_end);
964 :
965 : /*
966 : * Deal with whichever region (if any) still has rectangles left.
967 : *
968 : * We only need to worry about banding and coalescing for the very first
969 : * band left. After that, we can just group all remaining boxes,
970 : * regardless of how many bands, into one final append to the list.
971 : */
972 :
973 2552 : if ((r1 != r1_end) && append_non1)
974 : {
975 : /* Do first non_overlap1Func call, which may be able to coalesce */
976 763 : FIND_BAND (r1, r1_band_end, r1_end, r1y1);
977 :
978 763 : cur_band = new_reg->data->numRects;
979 :
980 763 : if (!pixman_region_append_non_o (new_reg,
981 : r1, r1_band_end,
982 0 : MAX (r1y1, ybot), r1->y2))
983 : {
984 0 : goto bail;
985 : }
986 :
987 763 : COALESCE (new_reg, prev_band, cur_band);
988 :
989 : /* Just append the rest of the boxes */
990 763 : APPEND_REGIONS (new_reg, r1_band_end, r1_end);
991 : }
992 1789 : else if ((r2 != r2_end) && append_non2)
993 : {
994 : /* Do first non_overlap2Func call, which may be able to coalesce */
995 281 : FIND_BAND (r2, r2_band_end, r2_end, r2y1);
996 :
997 281 : cur_band = new_reg->data->numRects;
998 :
999 281 : if (!pixman_region_append_non_o (new_reg,
1000 : r2, r2_band_end,
1001 0 : MAX (r2y1, ybot), r2->y2))
1002 : {
1003 0 : goto bail;
1004 : }
1005 :
1006 281 : COALESCE (new_reg, prev_band, cur_band);
1007 :
1008 : /* Append rest of boxes */
1009 281 : APPEND_REGIONS (new_reg, r2_band_end, r2_end);
1010 : }
1011 :
1012 2552 : free (old_data);
1013 :
1014 2552 : if (!(numRects = new_reg->data->numRects))
1015 : {
1016 465 : FREE_DATA (new_reg);
1017 465 : new_reg->data = pixman_region_empty_data;
1018 : }
1019 2087 : else if (numRects == 1)
1020 : {
1021 382 : new_reg->extents = *PIXREGION_BOXPTR (new_reg);
1022 382 : FREE_DATA (new_reg);
1023 382 : new_reg->data = (region_data_type_t *)NULL;
1024 : }
1025 : else
1026 : {
1027 1705 : DOWNSIZE (new_reg, numRects);
1028 : }
1029 :
1030 2552 : return TRUE;
1031 :
1032 : bail:
1033 0 : free (old_data);
1034 :
1035 0 : return pixman_break (new_reg);
1036 : }
1037 :
1038 : /*-
1039 : *-----------------------------------------------------------------------
1040 : * pixman_set_extents --
1041 : * Reset the extents of a region to what they should be. Called by
1042 : * pixman_region_subtract and pixman_region_intersect as they can't
1043 : * figure it out along the way or do so easily, as pixman_region_union can.
1044 : *
1045 : * Results:
1046 : * None.
1047 : *
1048 : * Side Effects:
1049 : * The region's 'extents' structure is overwritten.
1050 : *
1051 : *-----------------------------------------------------------------------
1052 : */
1053 : static void
1054 845 : pixman_set_extents (region_type_t *region)
1055 : {
1056 : box_type_t *box, *box_end;
1057 :
1058 845 : if (!region->data)
1059 261 : return;
1060 :
1061 584 : if (!region->data->size)
1062 : {
1063 465 : region->extents.x2 = region->extents.x1;
1064 465 : region->extents.y2 = region->extents.y1;
1065 465 : return;
1066 : }
1067 :
1068 119 : box = PIXREGION_BOXPTR (region);
1069 119 : box_end = PIXREGION_END (region);
1070 :
1071 : /*
1072 : * Since box is the first rectangle in the region, it must have the
1073 : * smallest y1 and since box_end is the last rectangle in the region,
1074 : * it must have the largest y2, because of banding. Initialize x1 and
1075 : * x2 from box and box_end, resp., as good things to initialize them
1076 : * to...
1077 : */
1078 119 : region->extents.x1 = box->x1;
1079 119 : region->extents.y1 = box->y1;
1080 119 : region->extents.x2 = box_end->x2;
1081 119 : region->extents.y2 = box_end->y2;
1082 :
1083 : critical_if_fail (region->extents.y1 < region->extents.y2);
1084 :
1085 754 : while (box <= box_end)
1086 : {
1087 516 : if (box->x1 < region->extents.x1)
1088 21 : region->extents.x1 = box->x1;
1089 516 : if (box->x2 > region->extents.x2)
1090 40 : region->extents.x2 = box->x2;
1091 516 : box++;
1092 : }
1093 :
1094 : critical_if_fail (region->extents.x1 < region->extents.x2);
1095 : }
1096 :
1097 : /*======================================================================
1098 : * Region Intersection
1099 : *====================================================================*/
1100 : /*-
1101 : *-----------------------------------------------------------------------
1102 : * pixman_region_intersect_o --
1103 : * Handle an overlapping band for pixman_region_intersect.
1104 : *
1105 : * Results:
1106 : * TRUE if successful.
1107 : *
1108 : * Side Effects:
1109 : * Rectangles may be added to the region.
1110 : *
1111 : *-----------------------------------------------------------------------
1112 : */
1113 : /*ARGSUSED*/
1114 : static pixman_bool_t
1115 468 : pixman_region_intersect_o (region_type_t *region,
1116 : box_type_t * r1,
1117 : box_type_t * r1_end,
1118 : box_type_t * r2,
1119 : box_type_t * r2_end,
1120 : int y1,
1121 : int y2)
1122 : {
1123 : int x1;
1124 : int x2;
1125 : box_type_t * next_rect;
1126 :
1127 468 : next_rect = PIXREGION_TOP (region);
1128 :
1129 : critical_if_fail (y1 < y2);
1130 : critical_if_fail (r1 != r1_end && r2 != r2_end);
1131 :
1132 : do
1133 : {
1134 628 : x1 = MAX (r1->x1, r2->x1);
1135 628 : x2 = MIN (r1->x2, r2->x2);
1136 :
1137 : /*
1138 : * If there's any overlap between the two rectangles, add that
1139 : * overlap to the new region.
1140 : */
1141 628 : if (x1 < x2)
1142 515 : NEWRECT (region, next_rect, x1, y1, x2, y2);
1143 :
1144 : /*
1145 : * Advance the pointer(s) with the leftmost right side, since the next
1146 : * rectangle on that list may still overlap the other region's
1147 : * current rectangle.
1148 : */
1149 628 : if (r1->x2 == x2)
1150 : {
1151 360 : r1++;
1152 : }
1153 628 : if (r2->x2 == x2)
1154 : {
1155 336 : r2++;
1156 : }
1157 : }
1158 628 : while ((r1 != r1_end) && (r2 != r2_end));
1159 :
1160 468 : return TRUE;
1161 : }
1162 :
1163 : PIXMAN_EXPORT pixman_bool_t
1164 4285 : PREFIX (_intersect) (region_type_t * new_reg,
1165 : region_type_t * reg1,
1166 : region_type_t * reg2)
1167 : {
1168 : GOOD (reg1);
1169 : GOOD (reg2);
1170 : GOOD (new_reg);
1171 :
1172 : /* check for trivial reject */
1173 5912 : if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||
1174 3090 : !EXTENTCHECK (®1->extents, ®2->extents))
1175 : {
1176 : /* Covers about 20% of all cases */
1177 3054 : FREE_DATA (new_reg);
1178 3054 : new_reg->extents.x2 = new_reg->extents.x1;
1179 3054 : new_reg->extents.y2 = new_reg->extents.y1;
1180 6108 : if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
1181 : {
1182 0 : new_reg->data = pixman_broken_data;
1183 0 : return FALSE;
1184 : }
1185 : else
1186 : {
1187 3054 : new_reg->data = pixman_region_empty_data;
1188 : }
1189 : }
1190 1231 : else if (!reg1->data && !reg2->data)
1191 : {
1192 : /* Covers about 80% of cases that aren't trivially rejected */
1193 884 : new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);
1194 884 : new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);
1195 884 : new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);
1196 884 : new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);
1197 :
1198 884 : FREE_DATA (new_reg);
1199 :
1200 884 : new_reg->data = (region_data_type_t *)NULL;
1201 : }
1202 347 : else if (!reg2->data && SUBSUMES (®2->extents, ®1->extents))
1203 : {
1204 61 : return PREFIX (_copy) (new_reg, reg1);
1205 : }
1206 286 : else if (!reg1->data && SUBSUMES (®1->extents, ®2->extents))
1207 : {
1208 7 : return PREFIX (_copy) (new_reg, reg2);
1209 : }
1210 279 : else if (reg1 == reg2)
1211 : {
1212 0 : return PREFIX (_copy) (new_reg, reg1);
1213 : }
1214 : else
1215 : {
1216 : /* General purpose intersection */
1217 :
1218 279 : if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE))
1219 0 : return FALSE;
1220 :
1221 279 : pixman_set_extents (new_reg);
1222 : }
1223 :
1224 : GOOD (new_reg);
1225 4217 : return(TRUE);
1226 : }
1227 :
1228 : #define MERGERECT(r) \
1229 : do \
1230 : { \
1231 : if (r->x1 <= x2) \
1232 : { \
1233 : /* Merge with current rectangle */ \
1234 : if (x2 < r->x2) \
1235 : x2 = r->x2; \
1236 : } \
1237 : else \
1238 : { \
1239 : /* Add current rectangle, start new one */ \
1240 : NEWRECT (region, next_rect, x1, y1, x2, y2); \
1241 : x1 = r->x1; \
1242 : x2 = r->x2; \
1243 : } \
1244 : r++; \
1245 : } while (0)
1246 :
1247 : /*======================================================================
1248 : * Region Union
1249 : *====================================================================*/
1250 :
1251 : /*-
1252 : *-----------------------------------------------------------------------
1253 : * pixman_region_union_o --
1254 : * Handle an overlapping band for the union operation. Picks the
1255 : * left-most rectangle each time and merges it into the region.
1256 : *
1257 : * Results:
1258 : * TRUE if successful.
1259 : *
1260 : * Side Effects:
1261 : * region is overwritten.
1262 : * overlap is set to TRUE if any boxes overlap.
1263 : *
1264 : *-----------------------------------------------------------------------
1265 : */
1266 : static pixman_bool_t
1267 2269 : pixman_region_union_o (region_type_t *region,
1268 : box_type_t * r1,
1269 : box_type_t * r1_end,
1270 : box_type_t * r2,
1271 : box_type_t * r2_end,
1272 : int y1,
1273 : int y2)
1274 : {
1275 : box_type_t *next_rect;
1276 : int x1; /* left and right side of current union */
1277 : int x2;
1278 :
1279 : critical_if_fail (y1 < y2);
1280 : critical_if_fail (r1 != r1_end && r2 != r2_end);
1281 :
1282 2269 : next_rect = PIXREGION_TOP (region);
1283 :
1284 : /* Start off current rectangle */
1285 2269 : if (r1->x1 < r2->x1)
1286 : {
1287 1387 : x1 = r1->x1;
1288 1387 : x2 = r1->x2;
1289 1387 : r1++;
1290 : }
1291 : else
1292 : {
1293 882 : x1 = r2->x1;
1294 882 : x2 = r2->x2;
1295 882 : r2++;
1296 : }
1297 5070 : while (r1 != r1_end && r2 != r2_end)
1298 : {
1299 532 : if (r1->x1 < r2->x1)
1300 339 : MERGERECT (r1);
1301 : else
1302 193 : MERGERECT (r2);
1303 : }
1304 :
1305 : /* Finish off whoever (if any) is left */
1306 2269 : if (r1 != r1_end)
1307 : {
1308 : do
1309 : {
1310 1284 : MERGERECT (r1);
1311 : }
1312 1284 : while (r1 != r1_end);
1313 : }
1314 1207 : else if (r2 != r2_end)
1315 : {
1316 : do
1317 : {
1318 1210 : MERGERECT (r2);
1319 : }
1320 1210 : while (r2 != r2_end);
1321 : }
1322 :
1323 : /* Add current rectangle */
1324 2269 : NEWRECT (region, next_rect, x1, y1, x2, y2);
1325 :
1326 2269 : return TRUE;
1327 : }
1328 :
1329 : PIXMAN_EXPORT pixman_bool_t
1330 3266 : PREFIX(_intersect_rect) (region_type_t *dest,
1331 : region_type_t *source,
1332 : int x, int y,
1333 : unsigned int width,
1334 : unsigned int height)
1335 : {
1336 : region_type_t region;
1337 :
1338 3266 : region.data = NULL;
1339 3266 : region.extents.x1 = x;
1340 3266 : region.extents.y1 = y;
1341 3266 : region.extents.x2 = x + width;
1342 3266 : region.extents.y2 = y + height;
1343 :
1344 3266 : if (!GOOD_RECT (®ion.extents))
1345 : {
1346 318 : if (BAD_RECT (®ion.extents))
1347 : _pixman_log_error (FUNC, "Invalid rectangle passed");
1348 318 : FREE_DATA (dest);
1349 318 : PREFIX (_init) (dest);
1350 318 : return TRUE;
1351 : }
1352 :
1353 2948 : return PREFIX(_intersect) (dest, source, ®ion);
1354 : }
1355 :
1356 : /* Convenience function for performing union of region with a
1357 : * single rectangle
1358 : */
1359 : PIXMAN_EXPORT pixman_bool_t
1360 7179 : PREFIX (_union_rect) (region_type_t *dest,
1361 : region_type_t *source,
1362 : int x,
1363 : int y,
1364 : unsigned int width,
1365 : unsigned int height)
1366 : {
1367 : region_type_t region;
1368 :
1369 7179 : region.extents.x1 = x;
1370 7179 : region.extents.y1 = y;
1371 7179 : region.extents.x2 = x + width;
1372 7179 : region.extents.y2 = y + height;
1373 :
1374 7179 : if (!GOOD_RECT (®ion.extents))
1375 : {
1376 1184 : if (BAD_RECT (®ion.extents))
1377 : _pixman_log_error (FUNC, "Invalid rectangle passed");
1378 1184 : return PREFIX (_copy) (dest, source);
1379 : }
1380 :
1381 5995 : region.data = NULL;
1382 :
1383 5995 : return PREFIX (_union) (dest, source, ®ion);
1384 : }
1385 :
1386 : PIXMAN_EXPORT pixman_bool_t
1387 11959 : PREFIX (_union) (region_type_t *new_reg,
1388 : region_type_t *reg1,
1389 : region_type_t *reg2)
1390 : {
1391 : /* Return TRUE if some overlap
1392 : * between reg1, reg2
1393 : */
1394 : GOOD (reg1);
1395 : GOOD (reg2);
1396 : GOOD (new_reg);
1397 :
1398 : /* checks all the simple cases */
1399 :
1400 : /*
1401 : * Region 1 and 2 are the same
1402 : */
1403 11959 : if (reg1 == reg2)
1404 0 : return PREFIX (_copy) (new_reg, reg1);
1405 :
1406 : /*
1407 : * Region 1 is empty
1408 : */
1409 11959 : if (PIXREGION_NIL (reg1))
1410 : {
1411 6192 : if (PIXREGION_NAR (reg1))
1412 0 : return pixman_break (new_reg);
1413 :
1414 6192 : if (new_reg != reg2)
1415 6192 : return PREFIX (_copy) (new_reg, reg2);
1416 :
1417 0 : return TRUE;
1418 : }
1419 :
1420 : /*
1421 : * Region 2 is empty
1422 : */
1423 5767 : if (PIXREGION_NIL (reg2))
1424 : {
1425 622 : if (PIXREGION_NAR (reg2))
1426 0 : return pixman_break (new_reg);
1427 :
1428 622 : if (new_reg != reg1)
1429 3 : return PREFIX (_copy) (new_reg, reg1);
1430 :
1431 619 : return TRUE;
1432 : }
1433 :
1434 : /*
1435 : * Region 1 completely subsumes region 2
1436 : */
1437 5145 : if (!reg1->data && SUBSUMES (®1->extents, ®2->extents))
1438 : {
1439 3353 : if (new_reg != reg1)
1440 26 : return PREFIX (_copy) (new_reg, reg1);
1441 :
1442 3327 : return TRUE;
1443 : }
1444 :
1445 : /*
1446 : * Region 2 completely subsumes region 1
1447 : */
1448 1792 : if (!reg2->data && SUBSUMES (®2->extents, ®1->extents))
1449 : {
1450 121 : if (new_reg != reg2)
1451 121 : return PREFIX (_copy) (new_reg, reg2);
1452 :
1453 0 : return TRUE;
1454 : }
1455 :
1456 1671 : if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE))
1457 0 : return FALSE;
1458 :
1459 1671 : new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);
1460 1671 : new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);
1461 1671 : new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);
1462 1671 : new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);
1463 :
1464 : GOOD (new_reg);
1465 :
1466 1671 : return TRUE;
1467 : }
1468 :
1469 : /*======================================================================
1470 : * Batch Rectangle Union
1471 : *====================================================================*/
1472 :
1473 : #define EXCHANGE_RECTS(a, b) \
1474 : { \
1475 : box_type_t t; \
1476 : t = rects[a]; \
1477 : rects[a] = rects[b]; \
1478 : rects[b] = t; \
1479 : }
1480 :
1481 : static void
1482 906 : quick_sort_rects (
1483 : box_type_t rects[],
1484 : int numRects)
1485 : {
1486 : int y1;
1487 : int x1;
1488 : int i, j;
1489 : box_type_t *r;
1490 :
1491 : /* Always called with numRects > 1 */
1492 :
1493 : do
1494 : {
1495 906 : if (numRects == 2)
1496 : {
1497 615 : if (rects[0].y1 > rects[1].y1 ||
1498 437 : (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1499 : {
1500 13 : EXCHANGE_RECTS (0, 1);
1501 : }
1502 :
1503 314 : return;
1504 : }
1505 :
1506 : /* Choose partition element, stick in location 0 */
1507 592 : EXCHANGE_RECTS (0, numRects >> 1);
1508 592 : y1 = rects[0].y1;
1509 592 : x1 = rects[0].x1;
1510 :
1511 : /* Partition array */
1512 592 : i = 0;
1513 592 : j = numRects;
1514 :
1515 : do
1516 : {
1517 597 : r = &(rects[i]);
1518 : do
1519 : {
1520 3131 : r++;
1521 3131 : i++;
1522 : }
1523 3131 : while (i != numRects && (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1524 :
1525 597 : r = &(rects[j]);
1526 : do
1527 : {
1528 2879 : r--;
1529 2879 : j--;
1530 : }
1531 2879 : while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1532 :
1533 597 : if (i < j)
1534 5 : EXCHANGE_RECTS (i, j);
1535 : }
1536 597 : while (i < j);
1537 :
1538 : /* Move partition element back to middle */
1539 592 : EXCHANGE_RECTS (0, j);
1540 :
1541 : /* Recurse */
1542 592 : if (numRects - j - 1 > 1)
1543 301 : quick_sort_rects (&rects[j + 1], numRects - j - 1);
1544 :
1545 592 : numRects = j;
1546 : }
1547 592 : while (numRects > 1);
1548 : }
1549 :
1550 : /*-
1551 : *-----------------------------------------------------------------------
1552 : * pixman_region_validate --
1553 : *
1554 : * Take a ``region'' which is a non-y-x-banded random collection of
1555 : * rectangles, and compute a nice region which is the union of all the
1556 : * rectangles.
1557 : *
1558 : * Results:
1559 : * TRUE if successful.
1560 : *
1561 : * Side Effects:
1562 : * The passed-in ``region'' may be modified.
1563 : * overlap set to TRUE if any retangles overlapped,
1564 : * else FALSE;
1565 : *
1566 : * Strategy:
1567 : * Step 1. Sort the rectangles into ascending order with primary key y1
1568 : * and secondary key x1.
1569 : *
1570 : * Step 2. Split the rectangles into the minimum number of proper y-x
1571 : * banded regions. This may require horizontally merging
1572 : * rectangles, and vertically coalescing bands. With any luck,
1573 : * this step in an identity transformation (ala the Box widget),
1574 : * or a coalescing into 1 box (ala Menus).
1575 : *
1576 : * Step 3. Merge the separate regions down to a single region by calling
1577 : * pixman_region_union. Maximize the work each pixman_region_union call does by using
1578 : * a binary merge.
1579 : *
1580 : *-----------------------------------------------------------------------
1581 : */
1582 :
1583 : static pixman_bool_t
1584 186 : validate (region_type_t * badreg)
1585 : {
1586 : /* Descriptor for regions under construction in Step 2. */
1587 : typedef struct
1588 : {
1589 : region_type_t reg;
1590 : int prev_band;
1591 : int cur_band;
1592 : } region_info_t;
1593 :
1594 : region_info_t stack_regions[64];
1595 :
1596 : int numRects; /* Original numRects for badreg */
1597 : region_info_t *ri; /* Array of current regions */
1598 : int num_ri; /* Number of entries used in ri */
1599 : int size_ri; /* Number of entries available in ri */
1600 : int i; /* Index into rects */
1601 : int j; /* Index into ri */
1602 : region_info_t *rit; /* &ri[j] */
1603 : region_type_t *reg; /* ri[j].reg */
1604 : box_type_t *box; /* Current box in rects */
1605 : box_type_t *ri_box; /* Last box in ri[j].reg */
1606 : region_type_t *hreg; /* ri[j_half].reg */
1607 186 : pixman_bool_t ret = TRUE;
1608 :
1609 186 : if (!badreg->data)
1610 : {
1611 : GOOD (badreg);
1612 0 : return TRUE;
1613 : }
1614 :
1615 186 : numRects = badreg->data->numRects;
1616 186 : if (!numRects)
1617 : {
1618 0 : if (PIXREGION_NAR (badreg))
1619 0 : return FALSE;
1620 : GOOD (badreg);
1621 0 : return TRUE;
1622 : }
1623 :
1624 186 : if (badreg->extents.x1 < badreg->extents.x2)
1625 : {
1626 0 : if ((numRects) == 1)
1627 : {
1628 0 : FREE_DATA (badreg);
1629 0 : badreg->data = (region_data_type_t *) NULL;
1630 : }
1631 : else
1632 : {
1633 0 : DOWNSIZE (badreg, numRects);
1634 : }
1635 :
1636 : GOOD (badreg);
1637 :
1638 0 : return TRUE;
1639 : }
1640 :
1641 : /* Step 1: Sort the rects array into ascending (y1, x1) order */
1642 186 : quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects);
1643 :
1644 : /* Step 2: Scatter the sorted array into the minimum number of regions */
1645 :
1646 : /* Set up the first region to be the first rectangle in badreg */
1647 : /* Note that step 2 code will never overflow the ri[0].reg rects array */
1648 186 : ri = stack_regions;
1649 186 : size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]);
1650 186 : num_ri = 1;
1651 186 : ri[0].prev_band = 0;
1652 186 : ri[0].cur_band = 0;
1653 186 : ri[0].reg = *badreg;
1654 186 : box = PIXREGION_BOXPTR (&ri[0].reg);
1655 186 : ri[0].reg.extents = *box;
1656 186 : ri[0].reg.data->numRects = 1;
1657 186 : badreg->extents = *pixman_region_empty_box;
1658 186 : badreg->data = pixman_region_empty_data;
1659 :
1660 : /* Now scatter rectangles into the minimum set of valid regions. If the
1661 : * next rectangle to be added to a region would force an existing rectangle
1662 : * in the region to be split up in order to maintain y-x banding, just
1663 : * forget it. Try the next region. If it doesn't fit cleanly into any
1664 : * region, make a new one.
1665 : */
1666 :
1667 1856 : for (i = numRects; --i > 0;)
1668 : {
1669 1484 : box++;
1670 : /* Look for a region to append box to */
1671 1554 : for (j = num_ri, rit = ri; --j >= 0; rit++)
1672 : {
1673 1518 : reg = &rit->reg;
1674 1518 : ri_box = PIXREGION_END (reg);
1675 :
1676 1518 : if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2)
1677 : {
1678 : /* box is in same band as ri_box. Merge or append it */
1679 1112 : if (box->x1 <= ri_box->x2)
1680 : {
1681 : /* Merge it with ri_box */
1682 1058 : if (box->x2 > ri_box->x2)
1683 1058 : ri_box->x2 = box->x2;
1684 : }
1685 : else
1686 : {
1687 54 : RECTALLOC_BAIL (reg, 1, bail);
1688 54 : *PIXREGION_TOP (reg) = *box;
1689 54 : reg->data->numRects++;
1690 : }
1691 :
1692 1112 : goto next_rect; /* So sue me */
1693 : }
1694 406 : else if (box->y1 >= ri_box->y2)
1695 : {
1696 : /* Put box into new band */
1697 336 : if (reg->extents.x2 < ri_box->x2)
1698 88 : reg->extents.x2 = ri_box->x2;
1699 :
1700 336 : if (reg->extents.x1 > box->x1)
1701 33 : reg->extents.x1 = box->x1;
1702 :
1703 336 : COALESCE (reg, rit->prev_band, rit->cur_band);
1704 336 : rit->cur_band = reg->data->numRects;
1705 336 : RECTALLOC_BAIL (reg, 1, bail);
1706 336 : *PIXREGION_TOP (reg) = *box;
1707 336 : reg->data->numRects++;
1708 :
1709 336 : goto next_rect;
1710 : }
1711 : /* Well, this region was inappropriate. Try the next one. */
1712 : } /* for j */
1713 :
1714 : /* Uh-oh. No regions were appropriate. Create a new one. */
1715 36 : if (size_ri == num_ri)
1716 : {
1717 : size_t data_size;
1718 :
1719 : /* Oops, allocate space for new region information */
1720 0 : size_ri <<= 1;
1721 :
1722 0 : data_size = size_ri * sizeof(region_info_t);
1723 0 : if (data_size / size_ri != sizeof(region_info_t))
1724 0 : goto bail;
1725 :
1726 0 : if (ri == stack_regions)
1727 : {
1728 0 : rit = malloc (data_size);
1729 0 : if (!rit)
1730 0 : goto bail;
1731 0 : memcpy (rit, ri, num_ri * sizeof (region_info_t));
1732 : }
1733 : else
1734 : {
1735 0 : rit = (region_info_t *) realloc (ri, data_size);
1736 0 : if (!rit)
1737 0 : goto bail;
1738 : }
1739 0 : ri = rit;
1740 0 : rit = &ri[num_ri];
1741 : }
1742 36 : num_ri++;
1743 36 : rit->prev_band = 0;
1744 36 : rit->cur_band = 0;
1745 36 : rit->reg.extents = *box;
1746 36 : rit->reg.data = (region_data_type_t *)NULL;
1747 :
1748 : /* MUST force allocation */
1749 36 : if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri))
1750 0 : goto bail;
1751 :
1752 : next_rect: ;
1753 : } /* for i */
1754 :
1755 : /* Make a final pass over each region in order to COALESCE and set
1756 : * extents.x2 and extents.y2
1757 : */
1758 408 : for (j = num_ri, rit = ri; --j >= 0; rit++)
1759 : {
1760 222 : reg = &rit->reg;
1761 222 : ri_box = PIXREGION_END (reg);
1762 222 : reg->extents.y2 = ri_box->y2;
1763 :
1764 222 : if (reg->extents.x2 < ri_box->x2)
1765 49 : reg->extents.x2 = ri_box->x2;
1766 :
1767 222 : COALESCE (reg, rit->prev_band, rit->cur_band);
1768 :
1769 222 : if (reg->data->numRects == 1) /* keep unions happy below */
1770 : {
1771 88 : FREE_DATA (reg);
1772 88 : reg->data = (region_data_type_t *)NULL;
1773 : }
1774 : }
1775 :
1776 : /* Step 3: Union all regions into a single region */
1777 408 : while (num_ri > 1)
1778 : {
1779 36 : int half = num_ri / 2;
1780 72 : for (j = num_ri & 1; j < (half + (num_ri & 1)); j++)
1781 : {
1782 36 : reg = &ri[j].reg;
1783 36 : hreg = &ri[j + half].reg;
1784 :
1785 36 : if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE))
1786 0 : ret = FALSE;
1787 :
1788 36 : if (hreg->extents.x1 < reg->extents.x1)
1789 5 : reg->extents.x1 = hreg->extents.x1;
1790 :
1791 36 : if (hreg->extents.y1 < reg->extents.y1)
1792 0 : reg->extents.y1 = hreg->extents.y1;
1793 :
1794 36 : if (hreg->extents.x2 > reg->extents.x2)
1795 28 : reg->extents.x2 = hreg->extents.x2;
1796 :
1797 36 : if (hreg->extents.y2 > reg->extents.y2)
1798 0 : reg->extents.y2 = hreg->extents.y2;
1799 :
1800 36 : FREE_DATA (hreg);
1801 : }
1802 :
1803 36 : num_ri -= half;
1804 :
1805 36 : if (!ret)
1806 0 : goto bail;
1807 : }
1808 :
1809 186 : *badreg = ri[0].reg;
1810 :
1811 186 : if (ri != stack_regions)
1812 0 : free (ri);
1813 :
1814 : GOOD (badreg);
1815 186 : return ret;
1816 :
1817 : bail:
1818 0 : for (i = 0; i < num_ri; i++)
1819 0 : FREE_DATA (&ri[i].reg);
1820 :
1821 0 : if (ri != stack_regions)
1822 0 : free (ri);
1823 :
1824 0 : return pixman_break (badreg);
1825 : }
1826 :
1827 : /*======================================================================
1828 : * Region Subtraction
1829 : *====================================================================*/
1830 :
1831 : /*-
1832 : *-----------------------------------------------------------------------
1833 : * pixman_region_subtract_o --
1834 : * Overlapping band subtraction. x1 is the left-most point not yet
1835 : * checked.
1836 : *
1837 : * Results:
1838 : * TRUE if successful.
1839 : *
1840 : * Side Effects:
1841 : * region may have rectangles added to it.
1842 : *
1843 : *-----------------------------------------------------------------------
1844 : */
1845 : /*ARGSUSED*/
1846 : static pixman_bool_t
1847 904 : pixman_region_subtract_o (region_type_t * region,
1848 : box_type_t * r1,
1849 : box_type_t * r1_end,
1850 : box_type_t * r2,
1851 : box_type_t * r2_end,
1852 : int y1,
1853 : int y2)
1854 : {
1855 : box_type_t * next_rect;
1856 : int x1;
1857 :
1858 904 : x1 = r1->x1;
1859 :
1860 : critical_if_fail (y1 < y2);
1861 : critical_if_fail (r1 != r1_end && r2 != r2_end);
1862 :
1863 904 : next_rect = PIXREGION_TOP (region);
1864 :
1865 : do
1866 : {
1867 1131 : if (r2->x2 <= x1)
1868 : {
1869 : /*
1870 : * Subtrahend entirely to left of minuend: go to next subtrahend.
1871 : */
1872 61 : r2++;
1873 : }
1874 1070 : else if (r2->x1 <= x1)
1875 : {
1876 : /*
1877 : * Subtrahend preceeds minuend: nuke left edge of minuend.
1878 : */
1879 955 : x1 = r2->x2;
1880 955 : if (x1 >= r1->x2)
1881 : {
1882 : /*
1883 : * Minuend completely covered: advance to next minuend and
1884 : * reset left fence to edge of new minuend.
1885 : */
1886 865 : r1++;
1887 865 : if (r1 != r1_end)
1888 116 : x1 = r1->x1;
1889 : }
1890 : else
1891 : {
1892 : /*
1893 : * Subtrahend now used up since it doesn't extend beyond
1894 : * minuend
1895 : */
1896 90 : r2++;
1897 : }
1898 : }
1899 115 : else if (r2->x1 < r1->x2)
1900 : {
1901 : /*
1902 : * Left part of subtrahend covers part of minuend: add uncovered
1903 : * part of minuend to region and skip to next subtrahend.
1904 : */
1905 : critical_if_fail (x1 < r2->x1);
1906 111 : NEWRECT (region, next_rect, x1, y1, r2->x1, y2);
1907 :
1908 111 : x1 = r2->x2;
1909 111 : if (x1 >= r1->x2)
1910 : {
1911 : /*
1912 : * Minuend used up: advance to new...
1913 : */
1914 46 : r1++;
1915 46 : if (r1 != r1_end)
1916 1 : x1 = r1->x1;
1917 : }
1918 : else
1919 : {
1920 : /*
1921 : * Subtrahend used up
1922 : */
1923 65 : r2++;
1924 : }
1925 : }
1926 : else
1927 : {
1928 : /*
1929 : * Minuend used up: add any remaining piece before advancing.
1930 : */
1931 4 : if (r1->x2 > x1)
1932 4 : NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
1933 :
1934 4 : r1++;
1935 :
1936 4 : if (r1 != r1_end)
1937 4 : x1 = r1->x1;
1938 : }
1939 : }
1940 1131 : while ((r1 != r1_end) && (r2 != r2_end));
1941 :
1942 : /*
1943 : * Add remaining minuend rectangles to region.
1944 : */
1945 1922 : while (r1 != r1_end)
1946 : {
1947 : critical_if_fail (x1 < r1->x2);
1948 :
1949 114 : NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
1950 :
1951 114 : r1++;
1952 114 : if (r1 != r1_end)
1953 4 : x1 = r1->x1;
1954 : }
1955 904 : return TRUE;
1956 : }
1957 :
1958 : /*-
1959 : *-----------------------------------------------------------------------
1960 : * pixman_region_subtract --
1961 : * Subtract reg_s from reg_m and leave the result in reg_d.
1962 : * S stands for subtrahend, M for minuend and D for difference.
1963 : *
1964 : * Results:
1965 : * TRUE if successful.
1966 : *
1967 : * Side Effects:
1968 : * reg_d is overwritten.
1969 : *
1970 : *-----------------------------------------------------------------------
1971 : */
1972 : PIXMAN_EXPORT pixman_bool_t
1973 1648 : PREFIX (_subtract) (region_type_t *reg_d,
1974 : region_type_t *reg_m,
1975 : region_type_t *reg_s)
1976 : {
1977 : GOOD (reg_m);
1978 : GOOD (reg_s);
1979 : GOOD (reg_d);
1980 :
1981 : /* check for trivial rejects */
1982 2221 : if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) ||
1983 1144 : !EXTENTCHECK (®_m->extents, ®_s->extents))
1984 : {
1985 1082 : if (PIXREGION_NAR (reg_s))
1986 0 : return pixman_break (reg_d);
1987 :
1988 1082 : return PREFIX (_copy) (reg_d, reg_m);
1989 : }
1990 566 : else if (reg_m == reg_s)
1991 : {
1992 0 : FREE_DATA (reg_d);
1993 0 : reg_d->extents.x2 = reg_d->extents.x1;
1994 0 : reg_d->extents.y2 = reg_d->extents.y1;
1995 0 : reg_d->data = pixman_region_empty_data;
1996 :
1997 0 : return TRUE;
1998 : }
1999 :
2000 : /* Add those rectangles in region 1 that aren't in region 2,
2001 : do yucky substraction for overlaps, and
2002 : just throw away rectangles in region 2 that aren't in region 1 */
2003 566 : if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE))
2004 0 : return FALSE;
2005 :
2006 : /*
2007 : * Can't alter reg_d's extents before we call pixman_op because
2008 : * it might be one of the source regions and pixman_op depends
2009 : * on the extents of those regions being unaltered. Besides, this
2010 : * way there's no checking against rectangles that will be nuked
2011 : * due to coalescing, so we have to examine fewer rectangles.
2012 : */
2013 566 : pixman_set_extents (reg_d);
2014 : GOOD (reg_d);
2015 566 : return TRUE;
2016 : }
2017 :
2018 : /*======================================================================
2019 : * Region Inversion
2020 : *====================================================================*/
2021 :
2022 : /*-
2023 : *-----------------------------------------------------------------------
2024 : * pixman_region_inverse --
2025 : * Take a region and a box and return a region that is everything
2026 : * in the box but not in the region. The careful reader will note
2027 : * that this is the same as subtracting the region from the box...
2028 : *
2029 : * Results:
2030 : * TRUE.
2031 : *
2032 : * Side Effects:
2033 : * new_reg is overwritten.
2034 : *
2035 : *-----------------------------------------------------------------------
2036 : */
2037 : PIXMAN_EXPORT pixman_bool_t
2038 0 : PREFIX (_inverse) (region_type_t *new_reg, /* Destination region */
2039 : region_type_t *reg1, /* Region to invert */
2040 : box_type_t * inv_rect) /* Bounding box for inversion */
2041 : {
2042 : region_type_t inv_reg; /* Quick and dirty region made from the
2043 : * bounding box */
2044 : GOOD (reg1);
2045 : GOOD (new_reg);
2046 :
2047 : /* check for trivial rejects */
2048 0 : if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, ®1->extents))
2049 : {
2050 0 : if (PIXREGION_NAR (reg1))
2051 0 : return pixman_break (new_reg);
2052 :
2053 0 : new_reg->extents = *inv_rect;
2054 0 : FREE_DATA (new_reg);
2055 0 : new_reg->data = (region_data_type_t *)NULL;
2056 :
2057 0 : return TRUE;
2058 : }
2059 :
2060 : /* Add those rectangles in region 1 that aren't in region 2,
2061 : * do yucky substraction for overlaps, and
2062 : * just throw away rectangles in region 2 that aren't in region 1
2063 : */
2064 0 : inv_reg.extents = *inv_rect;
2065 0 : inv_reg.data = (region_data_type_t *)NULL;
2066 0 : if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE))
2067 0 : return FALSE;
2068 :
2069 : /*
2070 : * Can't alter new_reg's extents before we call pixman_op because
2071 : * it might be one of the source regions and pixman_op depends
2072 : * on the extents of those regions being unaltered. Besides, this
2073 : * way there's no checking against rectangles that will be nuked
2074 : * due to coalescing, so we have to examine fewer rectangles.
2075 : */
2076 0 : pixman_set_extents (new_reg);
2077 : GOOD (new_reg);
2078 0 : return TRUE;
2079 : }
2080 :
2081 : /* In time O(log n), locate the first box whose y2 is greater than y.
2082 : * Return @end if no such box exists.
2083 : */
2084 : static box_type_t *
2085 0 : find_box_for_y (box_type_t *begin, box_type_t *end, int y)
2086 : {
2087 : box_type_t *mid;
2088 :
2089 0 : if (end == begin)
2090 0 : return end;
2091 :
2092 0 : if (end - begin == 1)
2093 : {
2094 0 : if (begin->y2 > y)
2095 0 : return begin;
2096 : else
2097 0 : return end;
2098 : }
2099 :
2100 0 : mid = begin + (end - begin) / 2;
2101 0 : if (mid->y2 > y)
2102 : {
2103 : /* If no box is found in [begin, mid], the function
2104 : * will return @mid, which is then known to be the
2105 : * correct answer.
2106 : */
2107 0 : return find_box_for_y (begin, mid, y);
2108 : }
2109 : else
2110 : {
2111 0 : return find_box_for_y (mid, end, y);
2112 : }
2113 : }
2114 :
2115 : /*
2116 : * rect_in(region, rect)
2117 : * This routine takes a pointer to a region and a pointer to a box
2118 : * and determines if the box is outside/inside/partly inside the region.
2119 : *
2120 : * The idea is to travel through the list of rectangles trying to cover the
2121 : * passed box with them. Anytime a piece of the rectangle isn't covered
2122 : * by a band of rectangles, part_out is set TRUE. Any time a rectangle in
2123 : * the region covers part of the box, part_in is set TRUE. The process ends
2124 : * when either the box has been completely covered (we reached a band that
2125 : * doesn't overlap the box, part_in is TRUE and part_out is false), the
2126 : * box has been partially covered (part_in == part_out == TRUE -- because of
2127 : * the banding, the first time this is true we know the box is only
2128 : * partially in the region) or is outside the region (we reached a band
2129 : * that doesn't overlap the box at all and part_in is false)
2130 : */
2131 : PIXMAN_EXPORT pixman_region_overlap_t
2132 2969 : PREFIX (_contains_rectangle) (region_type_t * region,
2133 : box_type_t * prect)
2134 : {
2135 : box_type_t * pbox;
2136 : box_type_t * pbox_end;
2137 : int part_in, part_out;
2138 : int numRects;
2139 : int x, y;
2140 :
2141 : GOOD (region);
2142 :
2143 2969 : numRects = PIXREGION_NUMRECTS (region);
2144 :
2145 : /* useful optimization */
2146 2969 : if (!numRects || !EXTENTCHECK (®ion->extents, prect))
2147 460 : return(PIXMAN_REGION_OUT);
2148 :
2149 2509 : if (numRects == 1)
2150 : {
2151 : /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
2152 2509 : if (SUBSUMES (®ion->extents, prect))
2153 2324 : return(PIXMAN_REGION_IN);
2154 : else
2155 185 : return(PIXMAN_REGION_PART);
2156 : }
2157 :
2158 0 : part_out = FALSE;
2159 0 : part_in = FALSE;
2160 :
2161 : /* (x,y) starts at upper left of rect, moving to the right and down */
2162 0 : x = prect->x1;
2163 0 : y = prect->y1;
2164 :
2165 : /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */
2166 0 : for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
2167 : pbox != pbox_end;
2168 0 : pbox++)
2169 : {
2170 : /* getting up to speed or skipping remainder of band */
2171 0 : if (pbox->y2 <= y)
2172 : {
2173 0 : if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end)
2174 0 : break;
2175 : }
2176 :
2177 0 : if (pbox->y1 > y)
2178 : {
2179 0 : part_out = TRUE; /* missed part of rectangle above */
2180 0 : if (part_in || (pbox->y1 >= prect->y2))
2181 : break;
2182 0 : y = pbox->y1; /* x guaranteed to be == prect->x1 */
2183 : }
2184 :
2185 0 : if (pbox->x2 <= x)
2186 0 : continue; /* not far enough over yet */
2187 :
2188 0 : if (pbox->x1 > x)
2189 : {
2190 0 : part_out = TRUE; /* missed part of rectangle to left */
2191 0 : if (part_in)
2192 0 : break;
2193 : }
2194 :
2195 0 : if (pbox->x1 < prect->x2)
2196 : {
2197 0 : part_in = TRUE; /* definitely overlap */
2198 0 : if (part_out)
2199 0 : break;
2200 : }
2201 :
2202 0 : if (pbox->x2 >= prect->x2)
2203 : {
2204 0 : y = pbox->y2; /* finished with this band */
2205 0 : if (y >= prect->y2)
2206 0 : break;
2207 0 : x = prect->x1; /* reset x out to left again */
2208 : }
2209 : else
2210 : {
2211 : /*
2212 : * Because boxes in a band are maximal width, if the first box
2213 : * to overlap the rectangle doesn't completely cover it in that
2214 : * band, the rectangle must be partially out, since some of it
2215 : * will be uncovered in that band. part_in will have been set true
2216 : * by now...
2217 : */
2218 0 : part_out = TRUE;
2219 0 : break;
2220 : }
2221 : }
2222 :
2223 0 : if (part_in)
2224 : {
2225 0 : if (y < prect->y2)
2226 0 : return PIXMAN_REGION_PART;
2227 : else
2228 0 : return PIXMAN_REGION_IN;
2229 : }
2230 : else
2231 : {
2232 0 : return PIXMAN_REGION_OUT;
2233 : }
2234 : }
2235 :
2236 : /* PREFIX(_translate) (region, x, y)
2237 : * translates in place
2238 : */
2239 :
2240 : PIXMAN_EXPORT void
2241 2939 : PREFIX (_translate) (region_type_t *region, int x, int y)
2242 : {
2243 : overflow_int_t x1, x2, y1, y2;
2244 : int nbox;
2245 : box_type_t * pbox;
2246 :
2247 : GOOD (region);
2248 2939 : region->extents.x1 = x1 = region->extents.x1 + x;
2249 2939 : region->extents.y1 = y1 = region->extents.y1 + y;
2250 2939 : region->extents.x2 = x2 = region->extents.x2 + x;
2251 2939 : region->extents.y2 = y2 = region->extents.y2 + y;
2252 :
2253 2939 : if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0)
2254 : {
2255 2939 : if (region->data && (nbox = region->data->numRects))
2256 : {
2257 186 : for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
2258 : {
2259 132 : pbox->x1 += x;
2260 132 : pbox->y1 += y;
2261 132 : pbox->x2 += x;
2262 132 : pbox->y2 += y;
2263 : }
2264 : }
2265 2939 : return;
2266 : }
2267 :
2268 0 : if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
2269 : {
2270 0 : region->extents.x2 = region->extents.x1;
2271 0 : region->extents.y2 = region->extents.y1;
2272 0 : FREE_DATA (region);
2273 0 : region->data = pixman_region_empty_data;
2274 0 : return;
2275 : }
2276 :
2277 0 : if (x1 < PIXMAN_REGION_MIN)
2278 0 : region->extents.x1 = PIXMAN_REGION_MIN;
2279 0 : else if (x2 > PIXMAN_REGION_MAX)
2280 0 : region->extents.x2 = PIXMAN_REGION_MAX;
2281 :
2282 0 : if (y1 < PIXMAN_REGION_MIN)
2283 0 : region->extents.y1 = PIXMAN_REGION_MIN;
2284 0 : else if (y2 > PIXMAN_REGION_MAX)
2285 0 : region->extents.y2 = PIXMAN_REGION_MAX;
2286 :
2287 0 : if (region->data && (nbox = region->data->numRects))
2288 : {
2289 : box_type_t * pbox_out;
2290 :
2291 0 : for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
2292 : {
2293 0 : pbox_out->x1 = x1 = pbox->x1 + x;
2294 0 : pbox_out->y1 = y1 = pbox->y1 + y;
2295 0 : pbox_out->x2 = x2 = pbox->x2 + x;
2296 0 : pbox_out->y2 = y2 = pbox->y2 + y;
2297 :
2298 0 : if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) |
2299 0 : (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
2300 : {
2301 0 : region->data->numRects--;
2302 0 : continue;
2303 : }
2304 :
2305 0 : if (x1 < PIXMAN_REGION_MIN)
2306 0 : pbox_out->x1 = PIXMAN_REGION_MIN;
2307 0 : else if (x2 > PIXMAN_REGION_MAX)
2308 0 : pbox_out->x2 = PIXMAN_REGION_MAX;
2309 :
2310 0 : if (y1 < PIXMAN_REGION_MIN)
2311 0 : pbox_out->y1 = PIXMAN_REGION_MIN;
2312 0 : else if (y2 > PIXMAN_REGION_MAX)
2313 0 : pbox_out->y2 = PIXMAN_REGION_MAX;
2314 :
2315 0 : pbox_out++;
2316 : }
2317 :
2318 0 : if (pbox_out != pbox)
2319 : {
2320 0 : if (region->data->numRects == 1)
2321 : {
2322 0 : region->extents = *PIXREGION_BOXPTR (region);
2323 0 : FREE_DATA (region);
2324 0 : region->data = (region_data_type_t *)NULL;
2325 : }
2326 : else
2327 : {
2328 0 : pixman_set_extents (region);
2329 : }
2330 : }
2331 : }
2332 :
2333 : GOOD (region);
2334 : }
2335 :
2336 : PIXMAN_EXPORT void
2337 1454 : PREFIX (_reset) (region_type_t *region, box_type_t *box)
2338 : {
2339 : GOOD (region);
2340 :
2341 : critical_if_fail (GOOD_RECT (box));
2342 :
2343 1454 : region->extents = *box;
2344 :
2345 1454 : FREE_DATA (region);
2346 :
2347 1454 : region->data = NULL;
2348 1454 : }
2349 :
2350 : PIXMAN_EXPORT void
2351 1921 : PREFIX (_clear) (region_type_t *region)
2352 : {
2353 : GOOD (region);
2354 1921 : FREE_DATA (region);
2355 :
2356 1921 : region->extents = *pixman_region_empty_box;
2357 1921 : region->data = pixman_region_empty_data;
2358 1921 : }
2359 :
2360 : /* box is "return" value */
2361 : PIXMAN_EXPORT int
2362 46 : PREFIX (_contains_point) (region_type_t * region,
2363 : int x, int y,
2364 : box_type_t * box)
2365 : {
2366 : box_type_t *pbox, *pbox_end;
2367 : int numRects;
2368 :
2369 : GOOD (region);
2370 46 : numRects = PIXREGION_NUMRECTS (region);
2371 :
2372 46 : if (!numRects || !INBOX (®ion->extents, x, y))
2373 31 : return(FALSE);
2374 :
2375 15 : if (numRects == 1)
2376 : {
2377 15 : if (box)
2378 0 : *box = region->extents;
2379 :
2380 15 : return(TRUE);
2381 : }
2382 :
2383 0 : pbox = PIXREGION_BOXPTR (region);
2384 0 : pbox_end = pbox + numRects;
2385 :
2386 0 : pbox = find_box_for_y (pbox, pbox_end, y);
2387 :
2388 0 : for (;pbox != pbox_end; pbox++)
2389 : {
2390 0 : if ((y < pbox->y1) || (x < pbox->x1))
2391 : break; /* missed it */
2392 :
2393 0 : if (x >= pbox->x2)
2394 0 : continue; /* not there yet */
2395 :
2396 0 : if (box)
2397 0 : *box = *pbox;
2398 :
2399 0 : return(TRUE);
2400 : }
2401 :
2402 0 : return(FALSE);
2403 : }
2404 :
2405 : PIXMAN_EXPORT int
2406 14838 : PREFIX (_not_empty) (region_type_t * region)
2407 : {
2408 : GOOD (region);
2409 :
2410 14838 : return(!PIXREGION_NIL (region));
2411 : }
2412 :
2413 : PIXMAN_EXPORT box_type_t *
2414 22 : PREFIX (_extents) (region_type_t * region)
2415 : {
2416 : GOOD (region);
2417 :
2418 22 : return(®ion->extents);
2419 : }
2420 :
2421 : /*
2422 : * Clip a list of scanlines to a region. The caller has allocated the
2423 : * space. FSorted is non-zero if the scanline origins are in ascending order.
2424 : *
2425 : * returns the number of new, clipped scanlines.
2426 : */
2427 :
2428 : PIXMAN_EXPORT pixman_bool_t
2429 0 : PREFIX (_selfcheck) (region_type_t *reg)
2430 : {
2431 : int i, numRects;
2432 :
2433 0 : if ((reg->extents.x1 > reg->extents.x2) ||
2434 0 : (reg->extents.y1 > reg->extents.y2))
2435 : {
2436 0 : return FALSE;
2437 : }
2438 :
2439 0 : numRects = PIXREGION_NUMRECTS (reg);
2440 0 : if (!numRects)
2441 : {
2442 0 : return ((reg->extents.x1 == reg->extents.x2) &&
2443 0 : (reg->extents.y1 == reg->extents.y2) &&
2444 0 : (reg->data->size || (reg->data == pixman_region_empty_data)));
2445 : }
2446 0 : else if (numRects == 1)
2447 : {
2448 0 : return (!reg->data);
2449 : }
2450 : else
2451 : {
2452 : box_type_t * pbox_p, * pbox_n;
2453 : box_type_t box;
2454 :
2455 0 : pbox_p = PIXREGION_RECTS (reg);
2456 0 : box = *pbox_p;
2457 0 : box.y2 = pbox_p[numRects - 1].y2;
2458 0 : pbox_n = pbox_p + 1;
2459 :
2460 0 : for (i = numRects; --i > 0; pbox_p++, pbox_n++)
2461 : {
2462 0 : if ((pbox_n->x1 >= pbox_n->x2) ||
2463 0 : (pbox_n->y1 >= pbox_n->y2))
2464 : {
2465 0 : return FALSE;
2466 : }
2467 :
2468 0 : if (pbox_n->x1 < box.x1)
2469 0 : box.x1 = pbox_n->x1;
2470 :
2471 0 : if (pbox_n->x2 > box.x2)
2472 0 : box.x2 = pbox_n->x2;
2473 :
2474 0 : if ((pbox_n->y1 < pbox_p->y1) ||
2475 0 : ((pbox_n->y1 == pbox_p->y1) &&
2476 0 : ((pbox_n->x1 < pbox_p->x2) || (pbox_n->y2 != pbox_p->y2))))
2477 : {
2478 0 : return FALSE;
2479 : }
2480 : }
2481 :
2482 0 : return ((box.x1 == reg->extents.x1) &&
2483 0 : (box.x2 == reg->extents.x2) &&
2484 0 : (box.y1 == reg->extents.y1) &&
2485 0 : (box.y2 == reg->extents.y2));
2486 : }
2487 : }
2488 :
2489 : PIXMAN_EXPORT pixman_bool_t
2490 2656 : PREFIX (_init_rects) (region_type_t *region,
2491 : const box_type_t *boxes, int count)
2492 : {
2493 : box_type_t *rects;
2494 : int displacement;
2495 : int i;
2496 :
2497 : /* if it's 1, then we just want to set the extents, so call
2498 : * the existing method. */
2499 2656 : if (count == 1)
2500 : {
2501 1776 : PREFIX (_init_rect) (region,
2502 0 : boxes[0].x1,
2503 0 : boxes[0].y1,
2504 888 : boxes[0].x2 - boxes[0].x1,
2505 888 : boxes[0].y2 - boxes[0].y1);
2506 888 : return TRUE;
2507 : }
2508 :
2509 1768 : PREFIX (_init) (region);
2510 :
2511 : /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
2512 : * a special case, and causing pixman_rect_alloc would cause
2513 : * us to leak memory (because the 0-rect case should be the
2514 : * static pixman_region_empty_data data).
2515 : */
2516 1768 : if (count == 0)
2517 1582 : return TRUE;
2518 :
2519 186 : if (!pixman_rect_alloc (region, count))
2520 0 : return FALSE;
2521 :
2522 186 : rects = PIXREGION_RECTS (region);
2523 :
2524 : /* Copy in the rects */
2525 186 : memcpy (rects, boxes, sizeof(box_type_t) * count);
2526 186 : region->data->numRects = count;
2527 :
2528 : /* Eliminate empty and malformed rectangles */
2529 186 : displacement = 0;
2530 :
2531 1856 : for (i = 0; i < count; ++i)
2532 : {
2533 1670 : box_type_t *box = &rects[i];
2534 :
2535 1670 : if (box->x1 >= box->x2 || box->y1 >= box->y2)
2536 0 : displacement++;
2537 1670 : else if (displacement)
2538 0 : rects[i - displacement] = rects[i];
2539 : }
2540 :
2541 186 : region->data->numRects -= displacement;
2542 :
2543 : /* If eliminating empty rectangles caused there
2544 : * to be only 0 or 1 rectangles, deal with that.
2545 : */
2546 186 : if (region->data->numRects == 0)
2547 : {
2548 0 : FREE_DATA (region);
2549 0 : PREFIX (_init) (region);
2550 :
2551 0 : return TRUE;
2552 : }
2553 :
2554 186 : if (region->data->numRects == 1)
2555 : {
2556 0 : region->extents = rects[0];
2557 :
2558 0 : FREE_DATA (region);
2559 0 : region->data = NULL;
2560 :
2561 : GOOD (region);
2562 :
2563 0 : return TRUE;
2564 : }
2565 :
2566 : /* Validate */
2567 186 : region->extents.x1 = region->extents.x2 = 0;
2568 :
2569 186 : return validate (region);
2570 : }
2571 :
2572 : #define READ(_ptr) (*(_ptr))
2573 :
2574 : static inline box_type_t *
2575 0 : bitmap_addrect (region_type_t *reg,
2576 : box_type_t *r,
2577 : box_type_t **first_rect,
2578 : int rx1, int ry1,
2579 : int rx2, int ry2)
2580 : {
2581 0 : if ((rx1 < rx2) && (ry1 < ry2) &&
2582 0 : (!(reg->data->numRects &&
2583 0 : ((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) &&
2584 0 : ((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2))))
2585 : {
2586 0 : if (reg->data->numRects == reg->data->size)
2587 : {
2588 0 : if (!pixman_rect_alloc (reg, 1))
2589 0 : return NULL;
2590 0 : *first_rect = PIXREGION_BOXPTR(reg);
2591 0 : r = *first_rect + reg->data->numRects;
2592 : }
2593 0 : r->x1 = rx1;
2594 0 : r->y1 = ry1;
2595 0 : r->x2 = rx2;
2596 0 : r->y2 = ry2;
2597 0 : reg->data->numRects++;
2598 0 : if (r->x1 < reg->extents.x1)
2599 0 : reg->extents.x1 = r->x1;
2600 0 : if (r->x2 > reg->extents.x2)
2601 0 : reg->extents.x2 = r->x2;
2602 0 : r++;
2603 : }
2604 0 : return r;
2605 : }
2606 :
2607 : /* Convert bitmap clip mask into clipping region.
2608 : * First, goes through each line and makes boxes by noting the transitions
2609 : * from 0 to 1 and 1 to 0.
2610 : * Then it coalesces the current line with the previous if they have boxes
2611 : * at the same X coordinates.
2612 : * Stride is in number of uint32_t per line.
2613 : */
2614 : PIXMAN_EXPORT void
2615 0 : PREFIX (_init_from_image) (region_type_t *region,
2616 : pixman_image_t *image)
2617 : {
2618 0 : uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1);
2619 : box_type_t *first_rect, *rects, *prect_line_start;
2620 : box_type_t *old_rect, *new_rect;
2621 : uint32_t *pw, w, *pw_line, *pw_line_end;
2622 : int irect_prev_start, irect_line_start;
2623 0 : int h, base, rx1 = 0, crects;
2624 : int ib;
2625 : pixman_bool_t in_box, same;
2626 : int width, height, stride;
2627 :
2628 0 : PREFIX(_init) (region);
2629 :
2630 : critical_if_fail (region->data);
2631 :
2632 0 : return_if_fail (image->type == BITS);
2633 0 : return_if_fail (image->bits.format == PIXMAN_a1);
2634 :
2635 0 : pw_line = pixman_image_get_data (image);
2636 0 : width = pixman_image_get_width (image);
2637 0 : height = pixman_image_get_height (image);
2638 0 : stride = pixman_image_get_stride (image) / 4;
2639 :
2640 0 : first_rect = PIXREGION_BOXPTR(region);
2641 0 : rects = first_rect;
2642 :
2643 0 : region->extents.x1 = width - 1;
2644 0 : region->extents.x2 = 0;
2645 0 : irect_prev_start = -1;
2646 0 : for (h = 0; h < height; h++)
2647 : {
2648 0 : pw = pw_line;
2649 0 : pw_line += stride;
2650 0 : irect_line_start = rects - first_rect;
2651 :
2652 : /* If the Screen left most bit of the word is set, we're starting in
2653 : * a box */
2654 0 : if (READ(pw) & mask0)
2655 : {
2656 0 : in_box = TRUE;
2657 0 : rx1 = 0;
2658 : }
2659 : else
2660 : {
2661 0 : in_box = FALSE;
2662 : }
2663 :
2664 : /* Process all words which are fully in the pixmap */
2665 0 : pw_line_end = pw + (width >> 5);
2666 0 : for (base = 0; pw < pw_line_end; base += 32)
2667 : {
2668 0 : w = READ(pw++);
2669 0 : if (in_box)
2670 : {
2671 0 : if (!~w)
2672 0 : continue;
2673 : }
2674 : else
2675 : {
2676 0 : if (!w)
2677 0 : continue;
2678 : }
2679 0 : for (ib = 0; ib < 32; ib++)
2680 : {
2681 : /* If the Screen left most bit of the word is set, we're
2682 : * starting a box */
2683 0 : if (w & mask0)
2684 : {
2685 0 : if (!in_box)
2686 : {
2687 0 : rx1 = base + ib;
2688 : /* start new box */
2689 0 : in_box = TRUE;
2690 : }
2691 : }
2692 : else
2693 : {
2694 0 : if (in_box)
2695 : {
2696 : /* end box */
2697 0 : rects = bitmap_addrect (region, rects, &first_rect,
2698 : rx1, h, base + ib, h + 1);
2699 0 : if (rects == NULL)
2700 0 : goto error;
2701 0 : in_box = FALSE;
2702 : }
2703 : }
2704 : /* Shift the word VISUALLY left one. */
2705 0 : w = SCREEN_SHIFT_LEFT(w, 1);
2706 : }
2707 : }
2708 :
2709 0 : if (width & 31)
2710 : {
2711 : /* Process final partial word on line */
2712 0 : w = READ(pw++);
2713 0 : for (ib = 0; ib < (width & 31); ib++)
2714 : {
2715 : /* If the Screen left most bit of the word is set, we're
2716 : * starting a box */
2717 0 : if (w & mask0)
2718 : {
2719 0 : if (!in_box)
2720 : {
2721 0 : rx1 = base + ib;
2722 : /* start new box */
2723 0 : in_box = TRUE;
2724 : }
2725 : }
2726 : else
2727 : {
2728 0 : if (in_box)
2729 : {
2730 : /* end box */
2731 0 : rects = bitmap_addrect(region, rects, &first_rect,
2732 : rx1, h, base + ib, h + 1);
2733 0 : if (rects == NULL)
2734 0 : goto error;
2735 0 : in_box = FALSE;
2736 : }
2737 : }
2738 : /* Shift the word VISUALLY left one. */
2739 0 : w = SCREEN_SHIFT_LEFT(w, 1);
2740 : }
2741 : }
2742 : /* If scanline ended with last bit set, end the box */
2743 0 : if (in_box)
2744 : {
2745 0 : rects = bitmap_addrect(region, rects, &first_rect,
2746 0 : rx1, h, base + (width & 31), h + 1);
2747 0 : if (rects == NULL)
2748 0 : goto error;
2749 : }
2750 : /* if all rectangles on this line have the same x-coords as
2751 : * those on the previous line, then add 1 to all the previous y2s and
2752 : * throw away all the rectangles from this line
2753 : */
2754 0 : same = FALSE;
2755 0 : if (irect_prev_start != -1)
2756 : {
2757 0 : crects = irect_line_start - irect_prev_start;
2758 0 : if (crects != 0 &&
2759 0 : crects == ((rects - first_rect) - irect_line_start))
2760 : {
2761 0 : old_rect = first_rect + irect_prev_start;
2762 0 : new_rect = prect_line_start = first_rect + irect_line_start;
2763 0 : same = TRUE;
2764 0 : while (old_rect < prect_line_start)
2765 : {
2766 0 : if ((old_rect->x1 != new_rect->x1) ||
2767 0 : (old_rect->x2 != new_rect->x2))
2768 : {
2769 0 : same = FALSE;
2770 0 : break;
2771 : }
2772 0 : old_rect++;
2773 0 : new_rect++;
2774 : }
2775 0 : if (same)
2776 : {
2777 0 : old_rect = first_rect + irect_prev_start;
2778 0 : while (old_rect < prect_line_start)
2779 : {
2780 0 : old_rect->y2 += 1;
2781 0 : old_rect++;
2782 : }
2783 0 : rects -= crects;
2784 0 : region->data->numRects -= crects;
2785 : }
2786 : }
2787 : }
2788 0 : if(!same)
2789 0 : irect_prev_start = irect_line_start;
2790 : }
2791 0 : if (!region->data->numRects)
2792 : {
2793 0 : region->extents.x1 = region->extents.x2 = 0;
2794 : }
2795 : else
2796 : {
2797 0 : region->extents.y1 = PIXREGION_BOXPTR(region)->y1;
2798 0 : region->extents.y2 = PIXREGION_END(region)->y2;
2799 0 : if (region->data->numRects == 1)
2800 : {
2801 0 : free (region->data);
2802 0 : region->data = NULL;
2803 : }
2804 : }
2805 :
2806 : error:
2807 0 : return;
2808 : }
|
