The Tor Browser / file comparison

comparison: gfx/cairo/libpixman/src/pixman-region.c

gfx/cairo/libpixman/src/pixman-region.c

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial