• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
PIXREGION_SZOF(size_t n)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 *
alloc_data(size_t n)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
PREFIX(_equal)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
PREFIX(_print)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
PREFIX(_init)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
PREFIX(_init_rect)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
PREFIX(_init_with_extents)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
PREFIX(_fini)413 PREFIX (_fini) (region_type_t *region)
414 {
415     GOOD (region);
416     FREE_DATA (region);
417 }
418 
419 PIXMAN_EXPORT int
PREFIX(_n_rects)420 PREFIX (_n_rects) (region_type_t *region)
421 {
422     return PIXREGION_NUMRECTS (region);
423 }
424 
425 PIXMAN_EXPORT box_type_t *
PREFIX(_rectangles)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
pixman_break(region_type_t * region)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
pixman_rect_alloc(region_type_t * region,int n)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
PREFIX(_copy)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
pixman_coalesce(region_type_t * region,int prev_start,int cur_start)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
pixman_region_append_non_o(region_type_t * region,box_type_t * r,box_type_t * r_end,int y1,int y2)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
pixman_op(region_type_t * new_reg,region_type_t * reg1,region_type_t * reg2,overlap_proc_ptr overlap_func,int append_non1,int append_non2)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
pixman_set_extents(region_type_t * region)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
pixman_region_intersect_o(region_type_t * region,box_type_t * r1,box_type_t * r1_end,box_type_t * r2,box_type_t * r2_end,int y1,int y2)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
PREFIX(_intersect)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
pixman_region_union_o(region_type_t * region,box_type_t * r1,box_type_t * r1_end,box_type_t * r2,box_type_t * r2_end,int y1,int y2)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
PREFIX(_intersect_rect)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
PREFIX(_union_rect)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
PREFIX(_union)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
quick_sort_rects(box_type_t rects[],int numRects)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
validate(region_type_t * badreg)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
pixman_region_subtract_o(region_type_t * region,box_type_t * r1,box_type_t * r1_end,box_type_t * r2,box_type_t * r2_end,int y1,int y2)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 precedes 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
PREFIX(_subtract)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 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))
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
PREFIX(_inverse)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 subtraction 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 *
find_box_for_y(box_type_t * begin,box_type_t * end,int y)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
PREFIX(_contains_rectangle)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
PREFIX(_translate)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
PREFIX(_reset)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
PREFIX(_clear)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
PREFIX(_contains_point)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
PREFIX(_not_empty)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 *
PREFIX(_extents)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
PREFIX(_selfcheck)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
PREFIX(_init_rects)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 *
bitmap_addrect(region_type_t * reg,box_type_t * r,box_type_t ** first_rect,int rx1,int ry1,int rx2,int ry2)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
PREFIX(_init_from_image)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 }
2793