2 * Copyright 1987, 1988, 1989, 1998 The Open Group
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
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
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.
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.
24 * Copyright 1987, 1988, 1989 by
25 * Digital Equipment Corporation, Maynard, Massachusetts.
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.
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
45 * Copyright © 1998 Keith Packard
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.
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.
70 #include "pixman-private.h"
72 #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
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) \
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)
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)
93 if (!PREFIX (_selfcheck (reg))) \
94 _pixman_log_error (FUNC, "Malformed region " # reg); \
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 };
108 static const region_data_type_t
PREFIX (_broken_data_
) = { 0, 0 };
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_
);
119 pixman_break (region_type_t
*region
);
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.
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).
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.
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.
142 * ----------- -----------
144 * | | -------- ----------- --------
145 * | | | | in y-x banded | | | | band 1
146 * | | | | form is | | | |
147 * ----------- | | ----------- --------
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
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).
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.
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) ) )
177 /* true iff (x,y) is in Box */
178 #define INBOX(r, x, y) \
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) )
192 PIXREGION_SZOF (size_t n
)
194 size_t size
= n
* sizeof(box_type_t
);
196 if (n
> UINT32_MAX
/ sizeof(box_type_t
))
199 if (sizeof(region_data_type_t
) > UINT32_MAX
- size
)
202 return size
+ sizeof(region_data_type_t
);
205 static region_data_type_t
*
206 alloc_data (size_t n
)
208 size_t sz
= PIXREGION_SZOF (n
);
216 #define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)
218 #define RECTALLOC_BAIL(region, n, bail) \
221 if (!(region)->data || \
222 (((region)->data->numRects + (n)) > (region)->data->size)) \
224 if (!pixman_rect_alloc (region, n)) \
229 #define RECTALLOC(region, n) \
232 if (!(region)->data || \
233 (((region)->data->numRects + (n)) > (region)->data->size)) \
235 if (!pixman_rect_alloc (region, n)) { \
241 #define ADDRECT(next_rect, nx1, ny1, nx2, ny2) \
244 next_rect->x1 = nx1; \
245 next_rect->y1 = ny1; \
246 next_rect->x2 = nx2; \
247 next_rect->y2 = ny2; \
252 #define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2) \
255 if (!(region)->data || \
256 ((region)->data->numRects == (region)->data->size)) \
258 if (!pixman_rect_alloc (region, 1)) \
260 next_rect = PIXREGION_TOP (region); \
262 ADDRECT (next_rect, nx1, ny1, nx2, ny2); \
263 region->data->numRects++; \
264 critical_if_fail (region->data->numRects <= region->data->size); \
267 #define DOWNSIZE(reg, numRects) \
270 if (((numRects) < ((reg)->data->size >> 1)) && \
271 ((reg)->data->size > 50)) \
273 region_data_type_t * new_data; \
274 size_t data_size = PIXREGION_SZOF (numRects); \
282 new_data = (region_data_type_t *) \
283 realloc ((reg)->data, data_size); \
288 new_data->size = (numRects); \
289 (reg)->data = new_data; \
294 PIXMAN_EXPORT pixman_bool_t
295 PREFIX (_equal
) (region_type_t
*reg1
, region_type_t
*reg2
)
301 if (reg1
->extents
.x1
!= reg2
->extents
.x1
)
304 if (reg1
->extents
.x2
!= reg2
->extents
.x2
)
307 if (reg1
->extents
.y1
!= reg2
->extents
.y1
)
310 if (reg1
->extents
.y2
!= reg2
->extents
.y2
)
313 if (PIXREGION_NUMRECTS (reg1
) != PIXREGION_NUMRECTS (reg2
))
316 rects1
= PIXREGION_RECTS (reg1
);
317 rects2
= PIXREGION_RECTS (reg2
);
319 for (i
= 0; i
!= PIXREGION_NUMRECTS (reg1
); i
++)
321 if (rects1
[i
].x1
!= rects2
[i
].x1
)
324 if (rects1
[i
].x2
!= rects2
[i
].x2
)
327 if (rects1
[i
].y1
!= rects2
[i
].y1
)
330 if (rects1
[i
].y2
!= rects2
[i
].y2
)
338 PREFIX (_print
) (region_type_t
*rgn
)
344 num
= PIXREGION_NUMRECTS (rgn
);
345 size
= PIXREGION_SIZE (rgn
);
346 rects
= PIXREGION_RECTS (rgn
);
348 fprintf (stderr
, "num: %d size: %d\n", num
, size
);
349 fprintf (stderr
, "extents: %d %d %d %d\n",
355 for (i
= 0; i
< num
; i
++)
357 fprintf (stderr
, "%d %d %d %d \n",
358 rects
[i
].x1
, rects
[i
].y1
, rects
[i
].x2
, rects
[i
].y2
);
361 fprintf (stderr
, "\n");
368 PREFIX (_init
) (region_type_t
*region
)
370 region
->extents
= *pixman_region_empty_box
;
371 region
->data
= pixman_region_empty_data
;
375 PREFIX (_init_rect
) (region_type_t
* region
,
381 region
->extents
.x1
= x
;
382 region
->extents
.y1
= y
;
383 region
->extents
.x2
= x
+ width
;
384 region
->extents
.y2
= y
+ height
;
386 if (!GOOD_RECT (®ion
->extents
))
388 if (BAD_RECT (®ion
->extents
))
389 _pixman_log_error (FUNC
, "Invalid rectangle passed");
390 PREFIX (_init
) (region
);
398 PREFIX (_init_with_extents
) (region_type_t
*region
, box_type_t
*extents
)
400 if (!GOOD_RECT (extents
))
402 if (BAD_RECT (extents
))
403 _pixman_log_error (FUNC
, "Invalid rectangle passed");
404 PREFIX (_init
) (region
);
407 region
->extents
= *extents
;
413 PREFIX (_fini
) (region_type_t
*region
)
420 PREFIX (_n_rects
) (region_type_t
*region
)
422 return PIXREGION_NUMRECTS (region
);
425 PIXMAN_EXPORT box_type_t
*
426 PREFIX (_rectangles
) (region_type_t
*region
,
430 *n_rects
= PIXREGION_NUMRECTS (region
);
432 return PIXREGION_RECTS (region
);
436 pixman_break (region_type_t
*region
)
440 region
->extents
= *pixman_region_empty_box
;
441 region
->data
= pixman_broken_data
;
447 pixman_rect_alloc (region_type_t
* region
,
450 region_data_type_t
*data
;
455 region
->data
= alloc_data (n
);
458 return pixman_break (region
);
460 region
->data
->numRects
= 1;
461 *PIXREGION_BOXPTR (region
) = region
->extents
;
463 else if (!region
->data
->size
)
465 region
->data
= alloc_data (n
);
468 return pixman_break (region
);
470 region
->data
->numRects
= 0;
478 n
= region
->data
->numRects
;
479 if (n
> 500) /* XXX pick numbers out of a hat */
483 n
+= region
->data
->numRects
;
484 data_size
= PIXREGION_SZOF (n
);
492 data
= (region_data_type_t
*)
493 realloc (region
->data
, PIXREGION_SZOF (n
));
497 return pixman_break (region
);
502 region
->data
->size
= n
;
507 PIXMAN_EXPORT pixman_bool_t
508 PREFIX (_copy
) (region_type_t
*dst
, region_type_t
*src
)
516 dst
->extents
= src
->extents
;
518 if (!src
->data
|| !src
->data
->size
)
521 dst
->data
= src
->data
;
525 if (!dst
->data
|| (dst
->data
->size
< src
->data
->numRects
))
529 dst
->data
= alloc_data (src
->data
->numRects
);
532 return pixman_break (dst
);
534 dst
->data
->size
= src
->data
->numRects
;
537 dst
->data
->numRects
= src
->data
->numRects
;
539 memmove ((char *)PIXREGION_BOXPTR (dst
), (char *)PIXREGION_BOXPTR (src
),
540 dst
->data
->numRects
* sizeof(box_type_t
));
545 /*======================================================================
546 * Generic Region Operator
547 *====================================================================*/
550 *-----------------------------------------------------------------------
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.
557 * The new index for the previous band.
560 * If coalescing takes place:
561 * - rectangles in the previous band will have their y2 fields
563 * - region->data->numRects will be decreased.
565 *-----------------------------------------------------------------------
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 */
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 */
578 * Figure out how many rectangles are in the band.
580 numRects
= cur_start
- prev_start
;
581 critical_if_fail (numRects
== region
->data
->numRects
- cur_start
);
583 if (!numRects
) return cur_start
;
586 * The bands may only be coalesced if the bottom of the previous
587 * matches the top scanline of the current.
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
;
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.
603 if ((prev_box
->x1
!= cur_box
->x1
) || (prev_box
->x2
!= cur_box
->x2
))
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.
616 numRects
= cur_start
- prev_start
;
617 region
->data
->numRects
-= numRects
;
630 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
632 #define COALESCE(new_reg, prev_band, cur_band) \
635 if (cur_band - prev_band == new_reg->data->numRects - cur_band) \
636 prev_band = pixman_coalesce (new_reg, prev_band, cur_band); \
638 prev_band = cur_band; \
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.
652 * region->data->numRects is incremented and the rectangles overwritten
653 * with the rectangles we're passed.
655 *-----------------------------------------------------------------------
657 static inline pixman_bool_t
658 pixman_region_append_non_o (region_type_t
* region
,
664 box_type_t
*next_rect
;
667 new_rects
= r_end
- r
;
669 critical_if_fail (y1
< y2
);
670 critical_if_fail (new_rects
!= 0);
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
;
679 critical_if_fail (r
->x1
< r
->x2
);
680 ADDRECT (next_rect
, r
->x1
, y1
, r
->x2
, y2
);
688 #define FIND_BAND(r, r_band_end, r_end, ry1) \
692 r_band_end = r + 1; \
693 while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) { \
698 #define APPEND_REGIONS(new_reg, r, r_end) \
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; \
711 *-----------------------------------------------------------------------
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.
718 * TRUE if successful.
721 * The new region is overwritten.
722 * overlap set to TRUE if overlap_func ever returns TRUE.
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.
736 *-----------------------------------------------------------------------
739 typedef pixman_bool_t (*overlap_proc_ptr
) (region_type_t
*region
,
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-
753 int append_non1
, /* Append non-overlapping bands
756 int append_non2
/* Append non-overlapping bands
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
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 */
782 * Break any region computed from a broken region
784 if (PIXREGION_NAR (reg1
) || PIXREGION_NAR (reg2
))
785 return pixman_break (new_reg
);
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.
795 r1
= PIXREGION_RECTS (reg1
);
796 new_size
= PIXREGION_NUMRECTS (reg1
);
797 r1_end
= r1
+ new_size
;
799 numRects
= PIXREGION_NUMRECTS (reg2
);
800 r2
= PIXREGION_RECTS (reg2
);
801 r2_end
= r2
+ numRects
;
803 critical_if_fail (r1
!= r1_end
);
804 critical_if_fail (r2
!= r2_end
);
806 old_data
= (region_data_type_t
*)NULL
;
808 if (((new_reg
== reg1
) && (new_size
> 1)) ||
809 ((new_reg
== reg2
) && (numRects
> 1)))
811 old_data
= new_reg
->data
;
812 new_reg
->data
= pixman_region_empty_data
;
815 /* guess at new size */
816 if (numRects
> new_size
)
822 new_reg
->data
= pixman_region_empty_data
;
823 else if (new_reg
->data
->size
)
824 new_reg
->data
->numRects
= 0;
826 if (new_size
> new_reg
->data
->size
)
828 if (!pixman_rect_alloc (new_reg
, new_size
))
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
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.
849 ybot
= MIN (r1
->y1
, r2
->y1
);
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.
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.
871 critical_if_fail (r1
!= r1_end
);
872 critical_if_fail (r2
!= r2_end
);
874 FIND_BAND (r1
, r1_band_end
, r1_end
, r1y1
);
875 FIND_BAND (r2
, r2_band_end
, r2_end
, r2y1
);
878 * First handle the band that doesn't intersect, if any.
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.
889 top
= MAX (r1y1
, ybot
);
890 bot
= MIN (r1
->y2
, r2y1
);
893 cur_band
= new_reg
->data
->numRects
;
894 if (!pixman_region_append_non_o (new_reg
, r1
, r1_band_end
, top
, bot
))
896 COALESCE (new_reg
, prev_band
, cur_band
);
901 else if (r2y1
< r1y1
)
905 top
= MAX (r2y1
, ybot
);
906 bot
= MIN (r2
->y2
, r1y1
);
910 cur_band
= new_reg
->data
->numRects
;
912 if (!pixman_region_append_non_o (new_reg
, r2
, r2_band_end
, top
, bot
))
915 COALESCE (new_reg
, prev_band
, cur_band
);
926 * Now see if we've hit an intersecting band. The two bands only
927 * intersect if ybot > ytop
929 ybot
= MIN (r1
->y2
, r2
->y2
);
932 cur_band
= new_reg
->data
->numRects
;
934 if (!(*overlap_func
)(new_reg
,
942 COALESCE (new_reg
, prev_band
, cur_band
);
946 * If we've finished with a band (y2 == ybot) we skip forward
947 * in the region to the next band.
956 while (r1
!= r1_end
&& r2
!= r2_end
);
959 * Deal with whichever region (if any) still has rectangles left.
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.
966 if ((r1
!= r1_end
) && append_non1
)
968 /* Do first non_overlap1Func call, which may be able to coalesce */
969 FIND_BAND (r1
, r1_band_end
, r1_end
, r1y1
);
971 cur_band
= new_reg
->data
->numRects
;
973 if (!pixman_region_append_non_o (new_reg
,
975 MAX (r1y1
, ybot
), r1
->y2
))
980 COALESCE (new_reg
, prev_band
, cur_band
);
982 /* Just append the rest of the boxes */
983 APPEND_REGIONS (new_reg
, r1_band_end
, r1_end
);
985 else if ((r2
!= r2_end
) && append_non2
)
987 /* Do first non_overlap2Func call, which may be able to coalesce */
988 FIND_BAND (r2
, r2_band_end
, r2_end
, r2y1
);
990 cur_band
= new_reg
->data
->numRects
;
992 if (!pixman_region_append_non_o (new_reg
,
994 MAX (r2y1
, ybot
), r2
->y2
))
999 COALESCE (new_reg
, prev_band
, cur_band
);
1001 /* Append rest of boxes */
1002 APPEND_REGIONS (new_reg
, r2_band_end
, r2_end
);
1007 if (!(numRects
= new_reg
->data
->numRects
))
1009 FREE_DATA (new_reg
);
1010 new_reg
->data
= pixman_region_empty_data
;
1012 else if (numRects
== 1)
1014 new_reg
->extents
= *PIXREGION_BOXPTR (new_reg
);
1015 FREE_DATA (new_reg
);
1016 new_reg
->data
= (region_data_type_t
*)NULL
;
1020 DOWNSIZE (new_reg
, numRects
);
1028 return pixman_break (new_reg
);
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.
1042 * The region's 'extents' structure is overwritten.
1044 *-----------------------------------------------------------------------
1047 pixman_set_extents (region_type_t
*region
)
1049 box_type_t
*box
, *box_end
;
1054 if (!region
->data
->size
)
1056 region
->extents
.x2
= region
->extents
.x1
;
1057 region
->extents
.y2
= region
->extents
.y1
;
1061 box
= PIXREGION_BOXPTR (region
);
1062 box_end
= PIXREGION_END (region
);
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
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
;
1076 critical_if_fail (region
->extents
.y1
< region
->extents
.y2
);
1078 while (box
<= box_end
)
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
;
1087 critical_if_fail (region
->extents
.x1
< region
->extents
.x2
);
1090 /*======================================================================
1091 * Region Intersection
1092 *====================================================================*/
1094 *-----------------------------------------------------------------------
1095 * pixman_region_intersect_o --
1096 * Handle an overlapping band for pixman_region_intersect.
1099 * TRUE if successful.
1102 * Rectangles may be added to the region.
1104 *-----------------------------------------------------------------------
1107 static pixman_bool_t
1108 pixman_region_intersect_o (region_type_t
*region
,
1110 box_type_t
* r1_end
,
1112 box_type_t
* r2_end
,
1118 box_type_t
* next_rect
;
1120 next_rect
= PIXREGION_TOP (region
);
1122 critical_if_fail (y1
< y2
);
1123 critical_if_fail (r1
!= r1_end
&& r2
!= r2_end
);
1127 x1
= MAX (r1
->x1
, r2
->x1
);
1128 x2
= MIN (r1
->x2
, r2
->x2
);
1131 * If there's any overlap between the two rectangles, add that
1132 * overlap to the new region.
1135 NEWRECT (region
, next_rect
, x1
, y1
, x2
, y2
);
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.
1151 while ((r1
!= r1_end
) && (r2
!= r2_end
));
1156 PIXMAN_EXPORT pixman_bool_t
1157 PREFIX (_intersect
) (region_type_t
* new_reg
,
1158 region_type_t
* reg1
,
1159 region_type_t
* reg2
)
1165 /* check for trivial reject */
1166 if (PIXREGION_NIL (reg1
) || PIXREGION_NIL (reg2
) ||
1167 !EXTENTCHECK (®1
->extents
, ®2
->extents
))
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
))
1175 new_reg
->data
= pixman_broken_data
;
1180 new_reg
->data
= pixman_region_empty_data
;
1183 else if (!reg1
->data
&& !reg2
->data
)
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
);
1191 FREE_DATA (new_reg
);
1193 new_reg
->data
= (region_data_type_t
*)NULL
;
1195 else if (!reg2
->data
&& SUBSUMES (®2
->extents
, ®1
->extents
))
1197 return PREFIX (_copy
) (new_reg
, reg1
);
1199 else if (!reg1
->data
&& SUBSUMES (®1
->extents
, ®2
->extents
))
1201 return PREFIX (_copy
) (new_reg
, reg2
);
1203 else if (reg1
== reg2
)
1205 return PREFIX (_copy
) (new_reg
, reg1
);
1209 /* General purpose intersection */
1211 if (!pixman_op (new_reg
, reg1
, reg2
, pixman_region_intersect_o
, FALSE
, FALSE
))
1214 pixman_set_extents (new_reg
);
1221 #define MERGERECT(r) \
1226 /* Merge with current rectangle */ \
1232 /* Add current rectangle, start new one */ \
1233 NEWRECT (region, next_rect, x1, y1, x2, y2); \
1240 /*======================================================================
1242 *====================================================================*/
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.
1251 * TRUE if successful.
1254 * region is overwritten.
1255 * overlap is set to TRUE if any boxes overlap.
1257 *-----------------------------------------------------------------------
1259 static pixman_bool_t
1260 pixman_region_union_o (region_type_t
*region
,
1262 box_type_t
* r1_end
,
1264 box_type_t
* r2_end
,
1268 box_type_t
*next_rect
;
1269 int x1
; /* left and right side of current union */
1272 critical_if_fail (y1
< y2
);
1273 critical_if_fail (r1
!= r1_end
&& r2
!= r2_end
);
1275 next_rect
= PIXREGION_TOP (region
);
1277 /* Start off current rectangle */
1278 if (r1
->x1
< r2
->x1
)
1290 while (r1
!= r1_end
&& r2
!= r2_end
)
1292 if (r1
->x1
< r2
->x1
)
1298 /* Finish off whoever (if any) is left */
1305 while (r1
!= r1_end
);
1307 else if (r2
!= r2_end
)
1313 while (r2
!= r2_end
);
1316 /* Add current rectangle */
1317 NEWRECT (region
, next_rect
, x1
, y1
, x2
, y2
);
1322 PIXMAN_EXPORT pixman_bool_t
1323 PREFIX(_intersect_rect
) (region_type_t
*dest
,
1324 region_type_t
*source
,
1327 unsigned int height
)
1329 region_type_t region
;
1332 region
.extents
.x1
= x
;
1333 region
.extents
.y1
= y
;
1334 region
.extents
.x2
= x
+ width
;
1335 region
.extents
.y2
= y
+ height
;
1337 return PREFIX(_intersect
) (dest
, source
, ®ion
);
1340 /* Convenience function for performing union of region with a
1343 PIXMAN_EXPORT pixman_bool_t
1344 PREFIX (_union_rect
) (region_type_t
*dest
,
1345 region_type_t
*source
,
1349 unsigned int height
)
1351 region_type_t region
;
1353 region
.extents
.x1
= x
;
1354 region
.extents
.y1
= y
;
1355 region
.extents
.x2
= x
+ width
;
1356 region
.extents
.y2
= y
+ height
;
1358 if (!GOOD_RECT (®ion
.extents
))
1360 if (BAD_RECT (®ion
.extents
))
1361 _pixman_log_error (FUNC
, "Invalid rectangle passed");
1362 return PREFIX (_copy
) (dest
, source
);
1367 return PREFIX (_union
) (dest
, source
, ®ion
);
1370 PIXMAN_EXPORT pixman_bool_t
1371 PREFIX (_union
) (region_type_t
*new_reg
,
1372 region_type_t
*reg1
,
1373 region_type_t
*reg2
)
1375 /* Return TRUE if some overlap
1376 * between reg1, reg2
1382 /* checks all the simple cases */
1385 * Region 1 and 2 are the same
1388 return PREFIX (_copy
) (new_reg
, reg1
);
1393 if (PIXREGION_NIL (reg1
))
1395 if (PIXREGION_NAR (reg1
))
1396 return pixman_break (new_reg
);
1398 if (new_reg
!= reg2
)
1399 return PREFIX (_copy
) (new_reg
, reg2
);
1407 if (PIXREGION_NIL (reg2
))
1409 if (PIXREGION_NAR (reg2
))
1410 return pixman_break (new_reg
);
1412 if (new_reg
!= reg1
)
1413 return PREFIX (_copy
) (new_reg
, reg1
);
1419 * Region 1 completely subsumes region 2
1421 if (!reg1
->data
&& SUBSUMES (®1
->extents
, ®2
->extents
))
1423 if (new_reg
!= reg1
)
1424 return PREFIX (_copy
) (new_reg
, reg1
);
1430 * Region 2 completely subsumes region 1
1432 if (!reg2
->data
&& SUBSUMES (®2
->extents
, ®1
->extents
))
1434 if (new_reg
!= reg2
)
1435 return PREFIX (_copy
) (new_reg
, reg2
);
1440 if (!pixman_op (new_reg
, reg1
, reg2
, pixman_region_union_o
, TRUE
, TRUE
))
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
);
1453 /*======================================================================
1454 * Batch Rectangle Union
1455 *====================================================================*/
1457 #define EXCHANGE_RECTS(a, b) \
1461 rects[a] = rects[b]; \
1475 /* Always called with numRects > 1 */
1481 if (rects
[0].y1
> rects
[1].y1
||
1482 (rects
[0].y1
== rects
[1].y1
&& rects
[0].x1
> rects
[1].x1
))
1484 EXCHANGE_RECTS (0, 1);
1490 /* Choose partition element, stick in location 0 */
1491 EXCHANGE_RECTS (0, numRects
>> 1);
1495 /* Partition array */
1507 while (i
!= numRects
&& (r
->y1
< y1
|| (r
->y1
== y1
&& r
->x1
< x1
)));
1515 while (y1
< r
->y1
|| (y1
== r
->y1
&& x1
< r
->x1
));
1518 EXCHANGE_RECTS (i
, j
);
1522 /* Move partition element back to middle */
1523 EXCHANGE_RECTS (0, j
);
1526 if (numRects
- j
- 1 > 1)
1527 quick_sort_rects (&rects
[j
+ 1], numRects
- j
- 1);
1531 while (numRects
> 1);
1535 *-----------------------------------------------------------------------
1536 * pixman_region_validate --
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
1543 * TRUE if successful.
1546 * The passed-in ``region'' may be modified.
1547 * overlap set to TRUE if any retangles overlapped,
1551 * Step 1. Sort the rectangles into ascending order with primary key y1
1552 * and secondary key x1.
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).
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
1564 *-----------------------------------------------------------------------
1567 static pixman_bool_t
1568 validate (region_type_t
* badreg
)
1570 /* Descriptor for regions under construction in Step 2. */
1578 region_info_t stack_regions
[64];
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
;
1599 numRects
= badreg
->data
->numRects
;
1602 if (PIXREGION_NAR (badreg
))
1608 if (badreg
->extents
.x1
< badreg
->extents
.x2
)
1610 if ((numRects
) == 1)
1613 badreg
->data
= (region_data_type_t
*) NULL
;
1617 DOWNSIZE (badreg
, numRects
);
1625 /* Step 1: Sort the rects array into ascending (y1, x1) order */
1626 quick_sort_rects (PIXREGION_BOXPTR (badreg
), numRects
);
1628 /* Step 2: Scatter the sorted array into the minimum number of regions */
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 */
1633 size_ri
= sizeof (stack_regions
) / sizeof (stack_regions
[0]);
1635 ri
[0].prev_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
;
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.
1651 for (i
= numRects
; --i
> 0;)
1654 /* Look for a region to append box to */
1655 for (j
= num_ri
, rit
= ri
; --j
>= 0; rit
++)
1658 ri_box
= PIXREGION_END (reg
);
1660 if (box
->y1
== ri_box
->y1
&& box
->y2
== ri_box
->y2
)
1662 /* box is in same band as ri_box. Merge or append it */
1663 if (box
->x1
<= ri_box
->x2
)
1665 /* Merge it with ri_box */
1666 if (box
->x2
> ri_box
->x2
)
1667 ri_box
->x2
= box
->x2
;
1671 RECTALLOC_BAIL (reg
, 1, bail
);
1672 *PIXREGION_TOP (reg
) = *box
;
1673 reg
->data
->numRects
++;
1676 goto next_rect
; /* So sue me */
1678 else if (box
->y1
>= ri_box
->y2
)
1680 /* Put box into new band */
1681 if (reg
->extents
.x2
< ri_box
->x2
)
1682 reg
->extents
.x2
= ri_box
->x2
;
1684 if (reg
->extents
.x1
> box
->x1
)
1685 reg
->extents
.x1
= box
->x1
;
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
++;
1695 /* Well, this region was inappropriate. Try the next one. */
1698 /* Uh-oh. No regions were appropriate. Create a new one. */
1699 if (size_ri
== num_ri
)
1703 /* Oops, allocate space for new region information */
1706 data_size
= size_ri
* sizeof(region_info_t
);
1707 if (data_size
/ size_ri
!= sizeof(region_info_t
))
1710 if (ri
== stack_regions
)
1712 rit
= malloc (data_size
);
1715 memcpy (rit
, ri
, num_ri
* sizeof (region_info_t
));
1719 rit
= (region_info_t
*) realloc (ri
, data_size
);
1729 rit
->reg
.extents
= *box
;
1730 rit
->reg
.data
= (region_data_type_t
*)NULL
;
1732 /* MUST force allocation */
1733 if (!pixman_rect_alloc (&rit
->reg
, (i
+ num_ri
) / num_ri
))
1739 /* Make a final pass over each region in order to COALESCE and set
1740 * extents.x2 and extents.y2
1742 for (j
= num_ri
, rit
= ri
; --j
>= 0; rit
++)
1745 ri_box
= PIXREGION_END (reg
);
1746 reg
->extents
.y2
= ri_box
->y2
;
1748 if (reg
->extents
.x2
< ri_box
->x2
)
1749 reg
->extents
.x2
= ri_box
->x2
;
1751 COALESCE (reg
, rit
->prev_band
, rit
->cur_band
);
1753 if (reg
->data
->numRects
== 1) /* keep unions happy below */
1756 reg
->data
= (region_data_type_t
*)NULL
;
1760 /* Step 3: Union all regions into a single region */
1763 int half
= num_ri
/ 2;
1764 for (j
= num_ri
& 1; j
< (half
+ (num_ri
& 1)); j
++)
1767 hreg
= &ri
[j
+ half
].reg
;
1769 if (!pixman_op (reg
, reg
, hreg
, pixman_region_union_o
, TRUE
, TRUE
))
1772 if (hreg
->extents
.x1
< reg
->extents
.x1
)
1773 reg
->extents
.x1
= hreg
->extents
.x1
;
1775 if (hreg
->extents
.y1
< reg
->extents
.y1
)
1776 reg
->extents
.y1
= hreg
->extents
.y1
;
1778 if (hreg
->extents
.x2
> reg
->extents
.x2
)
1779 reg
->extents
.x2
= hreg
->extents
.x2
;
1781 if (hreg
->extents
.y2
> reg
->extents
.y2
)
1782 reg
->extents
.y2
= hreg
->extents
.y2
;
1793 *badreg
= ri
[0].reg
;
1795 if (ri
!= stack_regions
)
1802 for (i
= 0; i
< num_ri
; i
++)
1803 FREE_DATA (&ri
[i
].reg
);
1805 if (ri
!= stack_regions
)
1808 return pixman_break (badreg
);
1811 /*======================================================================
1812 * Region Subtraction
1813 *====================================================================*/
1816 *-----------------------------------------------------------------------
1817 * pixman_region_subtract_o --
1818 * Overlapping band subtraction. x1 is the left-most point not yet
1822 * TRUE if successful.
1825 * region may have rectangles added to it.
1827 *-----------------------------------------------------------------------
1830 static pixman_bool_t
1831 pixman_region_subtract_o (region_type_t
* region
,
1833 box_type_t
* r1_end
,
1835 box_type_t
* r2_end
,
1839 box_type_t
* next_rect
;
1844 critical_if_fail (y1
< y2
);
1845 critical_if_fail (r1
!= r1_end
&& r2
!= r2_end
);
1847 next_rect
= PIXREGION_TOP (region
);
1854 * Subtrahend entirely to left of minuend: go to next subtrahend.
1858 else if (r2
->x1
<= x1
)
1861 * Subtrahend precedes minuend: nuke left edge of minuend.
1867 * Minuend completely covered: advance to next minuend and
1868 * reset left fence to edge of new minuend.
1877 * Subtrahend now used up since it doesn't extend beyond
1883 else if (r2
->x1
< r1
->x2
)
1886 * Left part of subtrahend covers part of minuend: add uncovered
1887 * part of minuend to region and skip to next subtrahend.
1889 critical_if_fail (x1
< r2
->x1
);
1890 NEWRECT (region
, next_rect
, x1
, y1
, r2
->x1
, y2
);
1896 * Minuend used up: advance to new...
1905 * Subtrahend used up
1913 * Minuend used up: add any remaining piece before advancing.
1916 NEWRECT (region
, next_rect
, x1
, y1
, r1
->x2
, y2
);
1924 while ((r1
!= r1_end
) && (r2
!= r2_end
));
1927 * Add remaining minuend rectangles to region.
1929 while (r1
!= r1_end
)
1931 critical_if_fail (x1
< r1
->x2
);
1933 NEWRECT (region
, next_rect
, x1
, y1
, r1
->x2
, y2
);
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.
1949 * TRUE if successful.
1952 * reg_d is overwritten.
1954 *-----------------------------------------------------------------------
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
)
1965 /* check for trivial rejects */
1966 if (PIXREGION_NIL (reg_m
) || PIXREGION_NIL (reg_s
) ||
1967 !EXTENTCHECK (®_m
->extents
, ®_s
->extents
))
1969 if (PIXREGION_NAR (reg_s
))
1970 return pixman_break (reg_d
);
1972 return PREFIX (_copy
) (reg_d
, reg_m
);
1974 else if (reg_m
== reg_s
)
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
;
1984 /* Add those rectangles in region 1 that aren't in region 2,
1985 do yucky subtraction 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
))
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.
1997 pixman_set_extents (reg_d
);
2002 /*======================================================================
2004 *====================================================================*/
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...
2017 * new_reg is overwritten.
2019 *-----------------------------------------------------------------------
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 */
2026 region_type_t inv_reg
; /* Quick and dirty region made from the
2031 /* check for trivial rejects */
2032 if (PIXREGION_NIL (reg1
) || !EXTENTCHECK (inv_rect
, ®1
->extents
))
2034 if (PIXREGION_NAR (reg1
))
2035 return pixman_break (new_reg
);
2037 new_reg
->extents
= *inv_rect
;
2038 FREE_DATA (new_reg
);
2039 new_reg
->data
= (region_data_type_t
*)NULL
;
2044 /* Add those rectangles in region 1 that aren't in region 2,
2045 * do yucky subtraction for overlaps, and
2046 * just throw away rectangles in region 2 that aren't in region 1
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
))
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.
2060 pixman_set_extents (new_reg
);
2065 /* In time O(log n), locate the first box whose y2 is greater than y.
2066 * Return @end if no such box exists.
2069 find_box_for_y (box_type_t
*begin
, box_type_t
*end
, int y
)
2076 if (end
- begin
== 1)
2084 mid
= begin
+ (end
- begin
) / 2;
2087 /* If no box is found in [begin, mid], the function
2088 * will return @mid, which is then known to be the
2091 return find_box_for_y (begin
, mid
, y
);
2095 return find_box_for_y (mid
, end
, y
);
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.
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)
2115 PIXMAN_EXPORT pixman_region_overlap_t
2116 PREFIX (_contains_rectangle
) (region_type_t
* region
,
2120 box_type_t
* pbox_end
;
2121 int part_in
, part_out
;
2127 numRects
= PIXREGION_NUMRECTS (region
);
2129 /* useful optimization */
2130 if (!numRects
|| !EXTENTCHECK (®ion
->extents
, prect
))
2131 return(PIXMAN_REGION_OUT
);
2135 /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
2136 if (SUBSUMES (®ion
->extents
, prect
))
2137 return(PIXMAN_REGION_IN
);
2139 return(PIXMAN_REGION_PART
);
2145 /* (x,y) starts at upper left of rect, moving to the right and down */
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
;
2154 /* getting up to speed or skipping remainder of band */
2157 if ((pbox
= find_box_for_y (pbox
, pbox_end
, y
)) == pbox_end
)
2163 part_out
= TRUE
; /* missed part of rectangle above */
2164 if (part_in
|| (pbox
->y1
>= prect
->y2
))
2166 y
= pbox
->y1
; /* x guaranteed to be == prect->x1 */
2170 continue; /* not far enough over yet */
2174 part_out
= TRUE
; /* missed part of rectangle to left */
2179 if (pbox
->x1
< prect
->x2
)
2181 part_in
= TRUE
; /* definitely overlap */
2186 if (pbox
->x2
>= prect
->x2
)
2188 y
= pbox
->y2
; /* finished with this band */
2191 x
= prect
->x1
; /* reset x out to left again */
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
2210 return PIXMAN_REGION_PART
;
2212 return PIXMAN_REGION_IN
;
2216 return PIXMAN_REGION_OUT
;
2220 /* PREFIX(_translate) (region, x, y)
2221 * translates in place
2225 PREFIX (_translate
) (region_type_t
*region
, int x
, int y
)
2227 overflow_int_t x1
, x2
, y1
, y2
;
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
;
2237 if (((x1
- PIXMAN_REGION_MIN
) | (y1
- PIXMAN_REGION_MIN
) | (PIXMAN_REGION_MAX
- x2
) | (PIXMAN_REGION_MAX
- y2
)) >= 0)
2239 if (region
->data
&& (nbox
= region
->data
->numRects
))
2241 for (pbox
= PIXREGION_BOXPTR (region
); nbox
--; pbox
++)
2252 if (((x2
- PIXMAN_REGION_MIN
) | (y2
- PIXMAN_REGION_MIN
) | (PIXMAN_REGION_MAX
- x1
) | (PIXMAN_REGION_MAX
- y1
)) <= 0)
2254 region
->extents
.x2
= region
->extents
.x1
;
2255 region
->extents
.y2
= region
->extents
.y1
;
2257 region
->data
= pixman_region_empty_data
;
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
;
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
;
2271 if (region
->data
&& (nbox
= region
->data
->numRects
))
2273 box_type_t
* pbox_out
;
2275 for (pbox_out
= pbox
= PIXREGION_BOXPTR (region
); nbox
--; pbox
++)
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
;
2282 if (((x2
- PIXMAN_REGION_MIN
) | (y2
- PIXMAN_REGION_MIN
) |
2283 (PIXMAN_REGION_MAX
- x1
) | (PIXMAN_REGION_MAX
- y1
)) <= 0)
2285 region
->data
->numRects
--;
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
;
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
;
2302 if (pbox_out
!= pbox
)
2304 if (region
->data
->numRects
== 1)
2306 region
->extents
= *PIXREGION_BOXPTR (region
);
2308 region
->data
= (region_data_type_t
*)NULL
;
2312 pixman_set_extents (region
);
2321 PREFIX (_reset
) (region_type_t
*region
, box_type_t
*box
)
2325 critical_if_fail (GOOD_RECT (box
));
2327 region
->extents
= *box
;
2331 region
->data
= NULL
;
2335 PREFIX (_clear
) (region_type_t
*region
)
2340 region
->extents
= *pixman_region_empty_box
;
2341 region
->data
= pixman_region_empty_data
;
2344 /* box is "return" value */
2346 PREFIX (_contains_point
) (region_type_t
* region
,
2350 box_type_t
*pbox
, *pbox_end
;
2354 numRects
= PIXREGION_NUMRECTS (region
);
2356 if (!numRects
|| !INBOX (®ion
->extents
, x
, y
))
2362 *box
= region
->extents
;
2367 pbox
= PIXREGION_BOXPTR (region
);
2368 pbox_end
= pbox
+ numRects
;
2370 pbox
= find_box_for_y (pbox
, pbox_end
, y
);
2372 for (;pbox
!= pbox_end
; pbox
++)
2374 if ((y
< pbox
->y1
) || (x
< pbox
->x1
))
2375 break; /* missed it */
2378 continue; /* not there yet */
2390 PREFIX (_not_empty
) (region_type_t
* region
)
2394 return(!PIXREGION_NIL (region
));
2397 PIXMAN_EXPORT box_type_t
*
2398 PREFIX (_extents
) (region_type_t
* region
)
2402 return(®ion
->extents
);
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.
2409 * returns the number of new, clipped scanlines.
2412 PIXMAN_EXPORT pixman_bool_t
2413 PREFIX (_selfcheck
) (region_type_t
*reg
)
2417 if ((reg
->extents
.x1
> reg
->extents
.x2
) ||
2418 (reg
->extents
.y1
> reg
->extents
.y2
))
2423 numRects
= PIXREGION_NUMRECTS (reg
);
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
)));
2430 else if (numRects
== 1)
2432 return (!reg
->data
);
2436 box_type_t
* pbox_p
, * pbox_n
;
2439 pbox_p
= PIXREGION_RECTS (reg
);
2441 box
.y2
= pbox_p
[numRects
- 1].y2
;
2442 pbox_n
= pbox_p
+ 1;
2444 for (i
= numRects
; --i
> 0; pbox_p
++, pbox_n
++)
2446 if ((pbox_n
->x1
>= pbox_n
->x2
) ||
2447 (pbox_n
->y1
>= pbox_n
->y2
))
2452 if (pbox_n
->x1
< box
.x1
)
2453 box
.x1
= pbox_n
->x1
;
2455 if (pbox_n
->x2
> box
.x2
)
2456 box
.x2
= pbox_n
->x2
;
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
))))
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
));
2473 PIXMAN_EXPORT pixman_bool_t
2474 PREFIX (_init_rects
) (region_type_t
*region
,
2475 const box_type_t
*boxes
, int count
)
2481 /* if it's 1, then we just want to set the extents, so call
2482 * the existing method. */
2485 PREFIX (_init_rect
) (region
,
2488 boxes
[0].x2
- boxes
[0].x1
,
2489 boxes
[0].y2
- boxes
[0].y1
);
2493 PREFIX (_init
) (region
);
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).
2503 if (!pixman_rect_alloc (region
, count
))
2506 rects
= PIXREGION_RECTS (region
);
2508 /* Copy in the rects */
2509 memcpy (rects
, boxes
, sizeof(box_type_t
) * count
);
2510 region
->data
->numRects
= count
;
2512 /* Eliminate empty and malformed rectangles */
2515 for (i
= 0; i
< count
; ++i
)
2517 box_type_t
*box
= &rects
[i
];
2519 if (box
->x1
>= box
->x2
|| box
->y1
>= box
->y2
)
2521 else if (displacement
)
2522 rects
[i
- displacement
] = rects
[i
];
2525 region
->data
->numRects
-= displacement
;
2527 /* If eliminating empty rectangles caused there
2528 * to be only 0 or 1 rectangles, deal with that.
2530 if (region
->data
->numRects
== 0)
2533 PREFIX (_init
) (region
);
2538 if (region
->data
->numRects
== 1)
2540 region
->extents
= rects
[0];
2543 region
->data
= NULL
;
2551 region
->extents
.x1
= region
->extents
.x2
= 0;
2553 return validate (region
);
2556 #define READ(_ptr) (*(_ptr))
2558 static inline box_type_t
*
2559 bitmap_addrect (region_type_t
*reg
,
2561 box_type_t
**first_rect
,
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
))))
2570 if (reg
->data
->numRects
== reg
->data
->size
)
2572 if (!pixman_rect_alloc (reg
, 1))
2574 *first_rect
= PIXREGION_BOXPTR(reg
);
2575 r
= *first_rect
+ reg
->data
->numRects
;
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
;
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.
2599 PREFIX (_init_from_image
) (region_type_t
*region
,
2600 pixman_image_t
*image
)
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
;
2609 pixman_bool_t in_box
, same
;
2610 int width
, height
, stride
;
2612 PREFIX(_init
) (region
);
2614 critical_if_fail (region
->data
);
2616 return_if_fail (image
->type
== BITS
);
2617 return_if_fail (image
->bits
.format
== PIXMAN_a1
);
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;
2624 first_rect
= PIXREGION_BOXPTR(region
);
2627 region
->extents
.x1
= width
- 1;
2628 region
->extents
.x2
= 0;
2629 irect_prev_start
= -1;
2630 for (h
= 0; h
< height
; h
++)
2634 irect_line_start
= rects
- first_rect
;
2636 /* If the Screen left most bit of the word is set, we're starting in
2638 if (READ(pw
) & mask0
)
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)
2663 for (ib
= 0; ib
< 32; ib
++)
2665 /* If the Screen left most bit of the word is set, we're
2681 rects
= bitmap_addrect (region
, rects
, &first_rect
,
2682 rx1
, h
, base
+ ib
, h
+ 1);
2688 /* Shift the word VISUALLY left one. */
2689 w
= SCREEN_SHIFT_LEFT(w
, 1);
2695 /* Process final partial word on line */
2697 for (ib
= 0; ib
< (width
& 31); ib
++)
2699 /* If the Screen left most bit of the word is set, we're
2715 rects
= bitmap_addrect(region
, rects
, &first_rect
,
2716 rx1
, h
, base
+ ib
, h
+ 1);
2722 /* Shift the word VISUALLY left one. */
2723 w
= SCREEN_SHIFT_LEFT(w
, 1);
2726 /* If scanline ended with last bit set, end the box */
2729 rects
= bitmap_addrect(region
, rects
, &first_rect
,
2730 rx1
, h
, base
+ (width
& 31), h
+ 1);
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
2739 if (irect_prev_start
!= -1)
2741 crects
= irect_line_start
- irect_prev_start
;
2743 crects
== ((rects
- first_rect
) - irect_line_start
))
2745 old_rect
= first_rect
+ irect_prev_start
;
2746 new_rect
= prect_line_start
= first_rect
+ irect_line_start
;
2748 while (old_rect
< prect_line_start
)
2750 if ((old_rect
->x1
!= new_rect
->x1
) ||
2751 (old_rect
->x2
!= new_rect
->x2
))
2761 old_rect
= first_rect
+ irect_prev_start
;
2762 while (old_rect
< prect_line_start
)
2768 region
->data
->numRects
-= crects
;
2773 irect_prev_start
= irect_line_start
;
2775 if (!region
->data
->numRects
)
2777 region
->extents
.x1
= region
->extents
.x2
= 0;
2781 region
->extents
.y1
= PIXREGION_BOXPTR(region
)->y1
;
2782 region
->extents
.y2
= PIXREGION_END(region
)->y2
;
2783 if (region
->data
->numRects
== 1)
2785 free (region
->data
);
2786 region
->data
= NULL
;