The Tor Browser / file revision

 /*

  * Copyright 1987, 1988, 1989, 1998  The Open Group

  * 

  * Permission to use, copy, modify, distribute, and sell this software and its

  * documentation for any purpose is hereby granted without fee, provided that

  * the above copyright notice appear in all copies and that both that

  * copyright notice and this permission notice appear in supporting

  * documentation.

  * 

  * The above copyright notice and this permission notice shall be included in

  * all copies or substantial portions of the Software.

  * 

  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE

  * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN

  * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

  * 

  * Except as contained in this notice, the name of The Open Group shall not be

  * used in advertising or otherwise to promote the sale, use or other dealings

  * in this Software without prior written authorization from The Open Group.

  * 

  * Copyright 1987, 1988, 1989 by

  * Digital Equipment Corporation, Maynard, Massachusetts.

  * 

  *                    All Rights Reserved

  * 

  * Permission to use, copy, modify, and distribute this software and its

  * documentation for any purpose and without fee is hereby granted,

  * provided that the above copyright notice appear in all copies and that

  * both that copyright notice and this permission notice appear in

  * supporting documentation, and that the name of Digital not be

  * used in advertising or publicity pertaining to distribution of the

  * software without specific, written prior permission.

  * 

  * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING

  * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL

  * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR

  * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,

  * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,

  * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS

  * SOFTWARE.

  *

  * Copyright © 1998 Keith Packard

  *

  * Permission to use, copy, modify, distribute, and sell this software and its

  * documentation for any purpose is hereby granted without fee, provided that

  * the above copyright notice appear in all copies and that both that

  * copyright notice and this permission notice appear in supporting

  * documentation, and that the name of Keith Packard not be used in

  * advertising or publicity pertaining to distribution of the software without

  * specific, written prior permission.  Keith Packard makes no

  * representations about the suitability of this software for any purpose.  It

  * is provided "as is" without express or implied warranty.

  *

  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,

  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO

  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR

  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,

  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER

  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR

  * PERFORMANCE OF THIS SOFTWARE.

  */

 #include <stdlib.h>

 #include <limits.h>

 #include <string.h>

 #include <stdio.h>

 #include "pixman-private.h"

 #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)

 /* not a region */

 #define PIXREGION_NAR(reg)      ((reg)->data == pixman_broken_data)

 #define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)

 #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)

 #define PIXREGION_RECTS(reg) \

     ((reg)->data ? (box_type_t *)((reg)->data + 1) \

      : &(reg)->extents)

 #define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))

 #define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])

 #define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)

 #define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)

 #define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)

 #define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2)

 #ifdef DEBUG

 #define GOOD(reg)							\

     do									\

     {									\

 	if (!PREFIX (_selfcheck (reg)))					\

 	    _pixman_log_error (FUNC, "Malformed region " # reg);	\

     } while (0)

 #else

 #define GOOD(reg)

 #endif

 static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };

 static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };

 #if defined (__llvm__) && !defined (__clang__)

 static const volatile region_data_type_t PREFIX (_broken_data_) = { 0, 0 };

 #else

 static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };

 #endif

 static box_type_t *pixman_region_empty_box =

     (box_type_t *)&PREFIX (_empty_box_);

 static region_data_type_t *pixman_region_empty_data =

     (region_data_type_t *)&PREFIX (_empty_data_);

 static region_data_type_t *pixman_broken_data =

     (region_data_type_t *)&PREFIX (_broken_data_);

 static pixman_bool_t

 pixman_break (region_type_t *region);

 /*

  * The functions in this file implement the Region abstraction used extensively

  * throughout the X11 sample server. A Region is simply a set of disjoint

  * (non-overlapping) rectangles, plus an "extent" rectangle which is the

  * smallest single rectangle that contains all the non-overlapping rectangles.

  *

  * A Region is implemented as a "y-x-banded" array of rectangles.  This array

  * imposes two degrees of order.  First, all rectangles are sorted by top side

  * y coordinate first (y1), and then by left side x coordinate (x1).

  *

  * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a

  * band has the same top y coordinate (y1), and each has the same bottom y

  * coordinate (y2).  Thus all rectangles in a band differ only in their left

  * and right side (x1 and x2).  Bands are implicit in the array of rectangles:

  * there is no separate list of band start pointers.

  *

  * The y-x band representation does not minimize rectangles.  In particular,

  * if a rectangle vertically crosses a band (the rectangle has scanlines in

  * the y1 to y2 area spanned by the band), then the rectangle may be broken

  * down into two or more smaller rectangles stacked one atop the other.

  *

  *  -----------				    -----------

  *  |         |				    |         |		    band 0

  *  |         |  --------		    -----------  --------

  *  |         |  |      |  in y-x banded    |         |  |      |   band 1

  *  |         |  |      |  form is	    |         |  |      |

  *  -----------  |      |		    -----------  --------

  *               |      |				 |      |   band 2

  *               --------				 --------

  *

  * An added constraint on the rectangles is that they must cover as much

  * horizontal area as possible: no two rectangles within a band are allowed

  * to touch.

  *

  * Whenever possible, bands will be merged together to cover a greater vertical

  * distance (and thus reduce the number of rectangles). Two bands can be merged

  * only if the bottom of one touches the top of the other and they have

  * rectangles in the same places (of the same width, of course).

  *

  * Adam de Boor wrote most of the original region code.  Joel McCormack

  * substantially modified or rewrote most of the core arithmetic routines, and

  * added pixman_region_validate in order to support several speed improvements

  * to pixman_region_validate_tree.  Bob Scheifler changed the representation

  * to be more compact when empty or a single rectangle, and did a bunch of

  * gratuitous reformatting. Carl Worth did further gratuitous reformatting

  * while re-merging the server and client region code into libpixregion.

  * Soren Sandmann did even more gratuitous reformatting.

  */

 /*  true iff two Boxes overlap */

 #define EXTENTCHECK(r1, r2)	   \

     (!( ((r1)->x2 <= (r2)->x1)  || \

         ((r1)->x1 >= (r2)->x2)  || \

         ((r1)->y2 <= (r2)->y1)  || \

         ((r1)->y1 >= (r2)->y2) ) )

 /* true iff (x,y) is in Box */

 #define INBOX(r, x, y)	\

     ( ((r)->x2 >  x) && \

       ((r)->x1 <= x) && \

       ((r)->y2 >  y) && \

       ((r)->y1 <= y) )

 /* true iff Box r1 contains Box r2 */

 #define SUBSUMES(r1, r2)	\

     ( ((r1)->x1 <= (r2)->x1) && \

       ((r1)->x2 >= (r2)->x2) && \

       ((r1)->y1 <= (r2)->y1) && \

       ((r1)->y2 >= (r2)->y2) )

 static size_t

 PIXREGION_SZOF (size_t n)

 {

     size_t size = n * sizeof(box_type_t);

     if (n > UINT32_MAX / sizeof(box_type_t))

 	return 0;

     if (sizeof(region_data_type_t) > UINT32_MAX - size)

 	return 0;

     return size + sizeof(region_data_type_t);

 }

 static region_data_type_t *

 alloc_data (size_t n)

 {

     size_t sz = PIXREGION_SZOF (n);

     if (!sz)

 	return NULL;

     return malloc (sz);

 }

 #define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)

 #define RECTALLOC_BAIL(region, n, bail)					\

     do									\

     {									\

 	if (!(region)->data ||						\

 	    (((region)->data->numRects + (n)) > (region)->data->size))	\

 	{								\

 	    if (!pixman_rect_alloc (region, n))				\

 		goto bail;						\

 	}								\

     } while (0)

 #define RECTALLOC(region, n)						\

     do									\

     {									\

 	if (!(region)->data ||						\

 	    (((region)->data->numRects + (n)) > (region)->data->size))	\

 	{								\

 	    if (!pixman_rect_alloc (region, n)) {			\

 		return FALSE;						\

 	    }								\

 	}								\

     } while (0)

 #define ADDRECT(next_rect, nx1, ny1, nx2, ny2)      \

     do						    \

     {						    \

 	next_rect->x1 = nx1;                        \

 	next_rect->y1 = ny1;                        \

 	next_rect->x2 = nx2;                        \

 	next_rect->y2 = ny2;                        \

 	next_rect++;                                \

     }						    \

     while (0)

 #define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2)			\

     do									\

     {									\

 	if (!(region)->data ||						\

 	    ((region)->data->numRects == (region)->data->size))		\

 	{								\

 	    if (!pixman_rect_alloc (region, 1))				\

 		return FALSE;						\

 	    next_rect = PIXREGION_TOP (region);				\

 	}								\

 	ADDRECT (next_rect, nx1, ny1, nx2, ny2);			\

 	region->data->numRects++;					\

 	critical_if_fail (region->data->numRects <= region->data->size);		\

     } while (0)

 #define DOWNSIZE(reg, numRects)						\

     do									\

     {									\

 	if (((numRects) < ((reg)->data->size >> 1)) &&			\

 	    ((reg)->data->size > 50))					\

 	{								\

 	    region_data_type_t * new_data;				\

 	    size_t data_size = PIXREGION_SZOF (numRects);		\

 									\

 	    if (!data_size)						\

 	    {								\

 		new_data = NULL;					\

 	    }								\

 	    else							\

 	    {								\

 		new_data = (region_data_type_t *)			\

 		    realloc ((reg)->data, data_size);			\

 	    }								\

 									\

 	    if (new_data)						\

 	    {								\

 		new_data->size = (numRects);				\

 		(reg)->data = new_data;					\

 	    }								\

 	}								\

     } while (0)

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_equal) (region_type_t *reg1, region_type_t *reg2)

 {

     int i;

     box_type_t *rects1;

     box_type_t *rects2;

     if (reg1->extents.x1 != reg2->extents.x1)

 	return FALSE;

     if (reg1->extents.x2 != reg2->extents.x2)

 	return FALSE;

     if (reg1->extents.y1 != reg2->extents.y1)

 	return FALSE;

     if (reg1->extents.y2 != reg2->extents.y2)

 	return FALSE;

     if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2))

 	return FALSE;

     rects1 = PIXREGION_RECTS (reg1);

     rects2 = PIXREGION_RECTS (reg2);

     for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++)

     {

 	if (rects1[i].x1 != rects2[i].x1)

 	    return FALSE;

 	if (rects1[i].x2 != rects2[i].x2)

 	    return FALSE;

 	if (rects1[i].y1 != rects2[i].y1)

 	    return FALSE;

 	if (rects1[i].y2 != rects2[i].y2)

 	    return FALSE;

     }

     return TRUE;

 }

 int

 PREFIX (_print) (region_type_t *rgn)

 {

     int num, size;

     int i;

     box_type_t * rects;

     num = PIXREGION_NUMRECTS (rgn);

     size = PIXREGION_SIZE (rgn);

     rects = PIXREGION_RECTS (rgn);

     fprintf (stderr, "num: %d size: %d\n", num, size);

     fprintf (stderr, "extents: %d %d %d %d\n",

              rgn->extents.x1,

 	     rgn->extents.y1,

 	     rgn->extents.x2,

 	     rgn->extents.y2);

     for (i = 0; i < num; i++)

     {

 	fprintf (stderr, "%d %d %d %d \n",

 	         rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);

     }

     fprintf (stderr, "\n");

     return(num);

 }

 PIXMAN_EXPORT void

 PREFIX (_init) (region_type_t *region)

 {

     region->extents = *pixman_region_empty_box;

     region->data = pixman_region_empty_data;

 }

 PIXMAN_EXPORT void

 PREFIX (_init_rect) (region_type_t *	region,

                      int		x,

 		     int		y,

 		     unsigned int	width,

 		     unsigned int	height)

 {

     region->extents.x1 = x;

     region->extents.y1 = y;

     region->extents.x2 = x + width;

     region->extents.y2 = y + height;

     if (!GOOD_RECT (&region->extents))

     {

         if (BAD_RECT (&region->extents))

             _pixman_log_error (FUNC, "Invalid rectangle passed");

         PREFIX (_init) (region);

         return;

     }

     region->data = NULL;

 }

 PIXMAN_EXPORT void

 PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents)

 {

     if (!GOOD_RECT (extents))

     {

         if (BAD_RECT (extents))

             _pixman_log_error (FUNC, "Invalid rectangle passed");

         PREFIX (_init) (region);

         return;

     }

     region->extents = *extents;

     region->data = NULL;

 }

 PIXMAN_EXPORT void

 PREFIX (_fini) (region_type_t *region)

 {

     GOOD (region);

     FREE_DATA (region);

 }

 PIXMAN_EXPORT int

 PREFIX (_n_rects) (region_type_t *region)

 {

     return PIXREGION_NUMRECTS (region);

 }

 PIXMAN_EXPORT box_type_t *

 PREFIX (_rectangles) (region_type_t *region,

                       int               *n_rects)

 {

     if (n_rects)

 	*n_rects = PIXREGION_NUMRECTS (region);

     return PIXREGION_RECTS (region);

 }

 static pixman_bool_t

 pixman_break (region_type_t *region)

 {

     FREE_DATA (region);

     region->extents = *pixman_region_empty_box;

     region->data = pixman_broken_data;

     return FALSE;

 }

 static pixman_bool_t

 pixman_rect_alloc (region_type_t * region,

                    int             n)

 {

     region_data_type_t *data;

     if (!region->data)

     {

 	n++;

 	region->data = alloc_data (n);

 	if (!region->data)

 	    return pixman_break (region);

 	region->data->numRects = 1;

 	*PIXREGION_BOXPTR (region) = region->extents;

     }

     else if (!region->data->size)

     {

 	region->data = alloc_data (n);

 	if (!region->data)

 	    return pixman_break (region);

 	region->data->numRects = 0;

     }

     else

     {

 	size_t data_size;

 	if (n == 1)

 	{

 	    n = region->data->numRects;

 	    if (n > 500) /* XXX pick numbers out of a hat */

 		n = 250;

 	}

 	n += region->data->numRects;

 	data_size = PIXREGION_SZOF (n);

 	if (!data_size)

 	{

 	    data = NULL;

 	}

 	else

 	{

 	    data = (region_data_type_t *)

 		realloc (region->data, PIXREGION_SZOF (n));

 	}

 	if (!data)

 	    return pixman_break (region);

 	region->data = data;

     }

     region->data->size = n;

     return TRUE;

 }

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_copy) (region_type_t *dst, region_type_t *src)

 {

     GOOD (dst);

     GOOD (src);

     if (dst == src)

 	return TRUE;

     dst->extents = src->extents;

     if (!src->data || !src->data->size)

     {

 	FREE_DATA (dst);

 	dst->data = src->data;

 	return TRUE;

     }

     if (!dst->data || (dst->data->size < src->data->numRects))

     {

 	FREE_DATA (dst);

 	dst->data = alloc_data (src->data->numRects);

 	if (!dst->data)

 	    return pixman_break (dst);

 	dst->data->size = src->data->numRects;

     }

     dst->data->numRects = src->data->numRects;

     memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),

              dst->data->numRects * sizeof(box_type_t));

     return TRUE;

 }

 /*======================================================================

  *	    Generic Region Operator

  *====================================================================*/

 /*-

  *-----------------------------------------------------------------------

  * pixman_coalesce --

  *	Attempt to merge the boxes in the current band with those in the

  *	previous one.  We are guaranteed that the current band extends to

  *      the end of the rects array.  Used only by pixman_op.

  *

  * Results:

  *	The new index for the previous band.

  *

  * Side Effects:

  *	If coalescing takes place:

  *	    - rectangles in the previous band will have their y2 fields

  *	      altered.

  *	    - region->data->numRects will be decreased.

  *

  *-----------------------------------------------------------------------

  */

 static inline int

 pixman_coalesce (region_type_t * region,      /* Region to coalesce		 */

 		 int             prev_start,  /* Index of start of previous band */

 		 int             cur_start)   /* Index of start of current band  */

 {

     box_type_t *prev_box;       /* Current box in previous band	     */

     box_type_t *cur_box;        /* Current box in current band       */

     int numRects;               /* Number rectangles in both bands   */

     int y2;                     /* Bottom of current band	     */

     /*

      * Figure out how many rectangles are in the band.

      */

     numRects = cur_start - prev_start;

     critical_if_fail (numRects == region->data->numRects - cur_start);

     if (!numRects) return cur_start;

     /*

      * The bands may only be coalesced if the bottom of the previous

      * matches the top scanline of the current.

      */

     prev_box = PIXREGION_BOX (region, prev_start);

     cur_box = PIXREGION_BOX (region, cur_start);

     if (prev_box->y2 != cur_box->y1) return cur_start;

     /*

      * Make sure the bands have boxes in the same places. This

      * assumes that boxes have been added in such a way that they

      * cover the most area possible. I.e. two boxes in a band must

      * have some horizontal space between them.

      */

     y2 = cur_box->y2;

     do

     {

 	if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2))

 	    return (cur_start);

 	prev_box++;

 	cur_box++;

 	numRects--;

     }

     while (numRects);

     /*

      * The bands may be merged, so set the bottom y of each box

      * in the previous band to the bottom y of the current band.

      */

     numRects = cur_start - prev_start;

     region->data->numRects -= numRects;

     do

     {

 	prev_box--;

 	prev_box->y2 = y2;

 	numRects--;

     }

     while (numRects);

     return prev_start;

 }

 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */

 #define COALESCE(new_reg, prev_band, cur_band)                          \

     do									\

     {									\

 	if (cur_band - prev_band == new_reg->data->numRects - cur_band)	\

 	    prev_band = pixman_coalesce (new_reg, prev_band, cur_band);	\

 	else								\

 	    prev_band = cur_band;					\

     } while (0)

 /*-

  *-----------------------------------------------------------------------

  * pixman_region_append_non_o --

  *	Handle a non-overlapping band for the union and subtract operations.

  *      Just adds the (top/bottom-clipped) rectangles into the region.

  *      Doesn't have to check for subsumption or anything.

  *

  * Results:

  *	None.

  *

  * Side Effects:

  *	region->data->numRects is incremented and the rectangles overwritten

  *	with the rectangles we're passed.

  *

  *-----------------------------------------------------------------------

  */

 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)

 {

     box_type_t *next_rect;

     int new_rects;

     new_rects = r_end - r;

     critical_if_fail (y1 < y2);

     critical_if_fail (new_rects != 0);

     /* Make sure we have enough space for all rectangles to be added */

     RECTALLOC (region, new_rects);

     next_rect = PIXREGION_TOP (region);

     region->data->numRects += new_rects;

     do

     {

 	critical_if_fail (r->x1 < r->x2);

 	ADDRECT (next_rect, r->x1, y1, r->x2, y2);

 	r++;

     }

     while (r != r_end);

     return TRUE;

 }

 #define FIND_BAND(r, r_band_end, r_end, ry1)			     \

     do								     \

     {								     \

 	ry1 = r->y1;						     \

 	r_band_end = r + 1;					     \

 	while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) {   \

 	    r_band_end++;					     \

 	}							     \

     } while (0)

 #define APPEND_REGIONS(new_reg, r, r_end)				\

     do									\

     {									\

 	int new_rects;							\

 	if ((new_rects = r_end - r)) {					\

 	    RECTALLOC_BAIL (new_reg, new_rects, bail);			\

 	    memmove ((char *)PIXREGION_TOP (new_reg), (char *)r,	\

 		     new_rects * sizeof(box_type_t));			\

 	    new_reg->data->numRects += new_rects;			\

 	}								\

     } while (0)

 /*-

  *-----------------------------------------------------------------------

  * pixman_op --

  *	Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,

  *	pixman_region_subtract, pixman_region_intersect....  Both regions MUST have at least one

  *      rectangle, and cannot be the same object.

  *

  * Results:

  *	TRUE if successful.

  *

  * Side Effects:

  *	The new region is overwritten.

  *	overlap set to TRUE if overlap_func ever returns TRUE.

  *

  * Notes:

  *	The idea behind this function is to view the two regions as sets.

  *	Together they cover a rectangle of area that this function divides

  *	into horizontal bands where points are covered only by one region

  *	or by both. For the first case, the non_overlap_func is called with

  *	each the band and the band's upper and lower extents. For the

  *	second, the overlap_func is called to process the entire band. It

  *	is responsible for clipping the rectangles in the band, though

  *	this function provides the boundaries.

  *	At the end of each band, the new region is coalesced, if possible,

  *	to reduce the number of rectangles in the region.

  *

  *-----------------------------------------------------------------------

  */

 typedef pixman_bool_t (*overlap_proc_ptr) (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);

 static pixman_bool_t

 pixman_op (region_type_t *  new_reg,               /* Place to store result	    */

 	   region_type_t *  reg1,                  /* First region in operation     */

 	   region_type_t *  reg2,                  /* 2d region in operation        */

 	   overlap_proc_ptr overlap_func,          /* Function to call for over-

 						    * lapping bands		    */

 	   int              append_non1,           /* Append non-overlapping bands  

 						    * in region 1 ?

 						    */

 	   int              append_non2            /* Append non-overlapping bands

 						    * in region 2 ?

 						    */

     )

 {

     box_type_t *r1;                 /* Pointer into first region     */

     box_type_t *r2;                 /* Pointer into 2d region	     */

     box_type_t *r1_end;             /* End of 1st region	     */

     box_type_t *r2_end;             /* End of 2d region		     */

     int ybot;                       /* Bottom of intersection	     */

     int ytop;                       /* Top of intersection	     */

     region_data_type_t *old_data;   /* Old data for new_reg	     */

     int prev_band;                  /* Index of start of

 				     * previous band in new_reg       */

     int cur_band;                   /* Index of start of current

 				     * band in new_reg		     */

     box_type_t * r1_band_end;       /* End of current band in r1     */

     box_type_t * r2_band_end;       /* End of current band in r2     */

     int top;                        /* Top of non-overlapping band   */

     int bot;                        /* Bottom of non-overlapping band*/

     int r1y1;                       /* Temps for r1->y1 and r2->y1   */

     int r2y1;

     int new_size;

     int numRects;

     /*

      * Break any region computed from a broken region

      */

     if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))

 	return pixman_break (new_reg);

     /*

      * Initialization:

      *	set r1, r2, r1_end and r2_end appropriately, save the rectangles

      * of the destination region until the end in case it's one of

      * the two source regions, then mark the "new" region empty, allocating

      * another array of rectangles for it to use.

      */

     r1 = PIXREGION_RECTS (reg1);

     new_size = PIXREGION_NUMRECTS (reg1);

     r1_end = r1 + new_size;

     numRects = PIXREGION_NUMRECTS (reg2);

     r2 = PIXREGION_RECTS (reg2);

     r2_end = r2 + numRects;

     critical_if_fail (r1 != r1_end);

     critical_if_fail (r2 != r2_end);

     old_data = (region_data_type_t *)NULL;

     if (((new_reg == reg1) && (new_size > 1)) ||

         ((new_reg == reg2) && (numRects > 1)))

     {

         old_data = new_reg->data;

         new_reg->data = pixman_region_empty_data;

     }

     /* guess at new size */

     if (numRects > new_size)

 	new_size = numRects;

     new_size <<= 1;

     if (!new_reg->data)

 	new_reg->data = pixman_region_empty_data;

     else if (new_reg->data->size)

 	new_reg->data->numRects = 0;

     if (new_size > new_reg->data->size)

     {

         if (!pixman_rect_alloc (new_reg, new_size))

         {

             free (old_data);

             return FALSE;

 	}

     }

     /*

      * Initialize ybot.

      * In the upcoming loop, ybot and ytop serve different functions depending

      * on whether the band being handled is an overlapping or non-overlapping

      * band.

      *  In the case of a non-overlapping band (only one of the regions

      * has points in the band), ybot is the bottom of the most recent

      * intersection and thus clips the top of the rectangles in that band.

      * ytop is the top of the next intersection between the two regions and

      * serves to clip the bottom of the rectangles in the current band.

      *	For an overlapping band (where the two regions intersect), ytop clips

      * the top of the rectangles of both regions and ybot clips the bottoms.

      */

     ybot = MIN (r1->y1, r2->y1);

     /*

      * prev_band serves to mark the start of the previous band so rectangles

      * can be coalesced into larger rectangles. qv. pixman_coalesce, above.

      * In the beginning, there is no previous band, so prev_band == cur_band

      * (cur_band is set later on, of course, but the first band will always

      * start at index 0). prev_band and cur_band must be indices because of

      * the possible expansion, and resultant moving, of the new region's

      * array of rectangles.

      */

     prev_band = 0;

     do

     {

         /*

 	 * This algorithm proceeds one source-band (as opposed to a

 	 * destination band, which is determined by where the two regions

 	 * intersect) at a time. r1_band_end and r2_band_end serve to mark the

 	 * rectangle after the last one in the current band for their

 	 * respective regions.

 	 */

         critical_if_fail (r1 != r1_end);

         critical_if_fail (r2 != r2_end);

         FIND_BAND (r1, r1_band_end, r1_end, r1y1);

         FIND_BAND (r2, r2_band_end, r2_end, r2y1);

         /*

 	 * First handle the band that doesn't intersect, if any.

 	 *

 	 * Note that attention is restricted to one band in the

 	 * non-intersecting region at once, so if a region has n

 	 * bands between the current position and the next place it overlaps

 	 * the other, this entire loop will be passed through n times.

 	 */

         if (r1y1 < r2y1)

         {

             if (append_non1)

             {

                 top = MAX (r1y1, ybot);

                 bot = MIN (r1->y2, r2y1);

                 if (top != bot)

                 {

                     cur_band = new_reg->data->numRects;

                     if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))

 			goto bail;

                     COALESCE (new_reg, prev_band, cur_band);

 		}

 	    }

             ytop = r2y1;

 	}

         else if (r2y1 < r1y1)

         {

             if (append_non2)

             {

                 top = MAX (r2y1, ybot);

                 bot = MIN (r2->y2, r1y1);

                 if (top != bot)

                 {

                     cur_band = new_reg->data->numRects;

                     if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))

 			goto bail;

                     COALESCE (new_reg, prev_band, cur_band);

 		}

 	    }

             ytop = r1y1;

 	}

         else

         {

             ytop = r1y1;

 	}

         /*

 	 * Now see if we've hit an intersecting band. The two bands only

 	 * intersect if ybot > ytop

 	 */

         ybot = MIN (r1->y2, r2->y2);

         if (ybot > ytop)

         {

             cur_band = new_reg->data->numRects;

             if (!(*overlap_func)(new_reg,

                                  r1, r1_band_end,

                                  r2, r2_band_end,

                                  ytop, ybot))

 	    {

 		goto bail;

 	    }

             COALESCE (new_reg, prev_band, cur_band);

 	}

         /*

 	 * If we've finished with a band (y2 == ybot) we skip forward

 	 * in the region to the next band.

 	 */

         if (r1->y2 == ybot)

 	    r1 = r1_band_end;

         if (r2->y2 == ybot)

 	    r2 = r2_band_end;

     }

     while (r1 != r1_end && r2 != r2_end);

     /*

      * Deal with whichever region (if any) still has rectangles left.

      *

      * We only need to worry about banding and coalescing for the very first

      * band left.  After that, we can just group all remaining boxes,

      * regardless of how many bands, into one final append to the list.

      */

     if ((r1 != r1_end) && append_non1)

     {

         /* Do first non_overlap1Func call, which may be able to coalesce */

         FIND_BAND (r1, r1_band_end, r1_end, r1y1);

         cur_band = new_reg->data->numRects;

         if (!pixman_region_append_non_o (new_reg,

                                          r1, r1_band_end,

                                          MAX (r1y1, ybot), r1->y2))

 	{

 	    goto bail;

 	}

         COALESCE (new_reg, prev_band, cur_band);

         /* Just append the rest of the boxes  */

         APPEND_REGIONS (new_reg, r1_band_end, r1_end);

     }

     else if ((r2 != r2_end) && append_non2)

     {

         /* Do first non_overlap2Func call, which may be able to coalesce */

         FIND_BAND (r2, r2_band_end, r2_end, r2y1);

 	cur_band = new_reg->data->numRects;

         if (!pixman_region_append_non_o (new_reg,

                                          r2, r2_band_end,

                                          MAX (r2y1, ybot), r2->y2))

 	{

 	    goto bail;

 	}

         COALESCE (new_reg, prev_band, cur_band);

         /* Append rest of boxes */

         APPEND_REGIONS (new_reg, r2_band_end, r2_end);

     }

     free (old_data);

     if (!(numRects = new_reg->data->numRects))

     {

         FREE_DATA (new_reg);

         new_reg->data = pixman_region_empty_data;

     }

     else if (numRects == 1)

     {

         new_reg->extents = *PIXREGION_BOXPTR (new_reg);

         FREE_DATA (new_reg);

         new_reg->data = (region_data_type_t *)NULL;

     }

     else

     {

         DOWNSIZE (new_reg, numRects);

     }

     return TRUE;

 bail:

     free (old_data);

     return pixman_break (new_reg);

 }

 /*-

  *-----------------------------------------------------------------------

  * pixman_set_extents --

  *	Reset the extents of a region to what they should be. Called by

  *	pixman_region_subtract and pixman_region_intersect as they can't

  *      figure it out along the way or do so easily, as pixman_region_union can.

  *

  * Results:

  *	None.

  *

  * Side Effects:

  *	The region's 'extents' structure is overwritten.

  *

  *-----------------------------------------------------------------------

  */

 static void

 pixman_set_extents (region_type_t *region)

 {

     box_type_t *box, *box_end;

     if (!region->data)

 	return;

     if (!region->data->size)

     {

         region->extents.x2 = region->extents.x1;

         region->extents.y2 = region->extents.y1;

         return;

     }

     box = PIXREGION_BOXPTR (region);

     box_end = PIXREGION_END (region);

     /*

      * Since box is the first rectangle in the region, it must have the

      * smallest y1 and since box_end is the last rectangle in the region,

      * it must have the largest y2, because of banding. Initialize x1 and

      * x2 from  box and box_end, resp., as good things to initialize them

      * to...

      */

     region->extents.x1 = box->x1;

     region->extents.y1 = box->y1;

     region->extents.x2 = box_end->x2;

     region->extents.y2 = box_end->y2;

     critical_if_fail (region->extents.y1 < region->extents.y2);

     while (box <= box_end)

     {

         if (box->x1 < region->extents.x1)

 	    region->extents.x1 = box->x1;

         if (box->x2 > region->extents.x2)

 	    region->extents.x2 = box->x2;

         box++;

     }

     critical_if_fail (region->extents.x1 < region->extents.x2);

 }

 /*======================================================================

  *	    Region Intersection

  *====================================================================*/

 /*-

  *-----------------------------------------------------------------------

  * pixman_region_intersect_o --

  *	Handle an overlapping band for pixman_region_intersect.

  *

  * Results:

  *	TRUE if successful.

  *

  * Side Effects:

  *	Rectangles may be added to the region.

  *

  *-----------------------------------------------------------------------

  */

 /*ARGSUSED*/

 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)

 {

     int x1;

     int x2;

     box_type_t *        next_rect;

     next_rect = PIXREGION_TOP (region);

     critical_if_fail (y1 < y2);

     critical_if_fail (r1 != r1_end && r2 != r2_end);

     do

     {

         x1 = MAX (r1->x1, r2->x1);

         x2 = MIN (r1->x2, r2->x2);

         /*

 	 * If there's any overlap between the two rectangles, add that

 	 * overlap to the new region.

 	 */

         if (x1 < x2)

 	    NEWRECT (region, next_rect, x1, y1, x2, y2);

         /*

 	 * Advance the pointer(s) with the leftmost right side, since the next

 	 * rectangle on that list may still overlap the other region's

 	 * current rectangle.

 	 */

         if (r1->x2 == x2)

         {

             r1++;

 	}

         if (r2->x2 == x2)

         {

             r2++;

 	}

     }

     while ((r1 != r1_end) && (r2 != r2_end));

     return TRUE;

 }

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_intersect) (region_type_t *     new_reg,

                      region_type_t *        reg1,

                      region_type_t *        reg2)

 {

     GOOD (reg1);

     GOOD (reg2);

     GOOD (new_reg);

     /* check for trivial reject */

     if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||

         !EXTENTCHECK (&reg1->extents, &reg2->extents))

     {

         /* Covers about 20% of all cases */

         FREE_DATA (new_reg);

         new_reg->extents.x2 = new_reg->extents.x1;

         new_reg->extents.y2 = new_reg->extents.y1;

         if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))

         {

             new_reg->data = pixman_broken_data;

             return FALSE;

 	}

         else

 	{

 	    new_reg->data = pixman_region_empty_data;

 	}

     }

     else if (!reg1->data && !reg2->data)

     {

         /* Covers about 80% of cases that aren't trivially rejected */

         new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);

         new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);

         new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);

         new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);

         FREE_DATA (new_reg);

 	new_reg->data = (region_data_type_t *)NULL;

     }

     else if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))

     {

         return PREFIX (_copy) (new_reg, reg1);

     }

     else if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))

     {

         return PREFIX (_copy) (new_reg, reg2);

     }

     else if (reg1 == reg2)

     {

         return PREFIX (_copy) (new_reg, reg1);

     }

     else

     {

         /* General purpose intersection */

         if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE))

 	    return FALSE;

         pixman_set_extents (new_reg);

     }

     GOOD (new_reg);

     return(TRUE);

 }

 #define MERGERECT(r)							\

     do									\

     {									\

         if (r->x1 <= x2)						\

 	{								\

             /* Merge with current rectangle */				\

             if (x2 < r->x2)						\

 		x2 = r->x2;						\

 	}								\

 	else								\

 	{								\

             /* Add current rectangle, start new one */			\

             NEWRECT (region, next_rect, x1, y1, x2, y2);		\

             x1 = r->x1;							\

             x2 = r->x2;							\

 	}								\

         r++;								\

     } while (0)

 /*======================================================================

  *	    Region Union

  *====================================================================*/

 /*-

  *-----------------------------------------------------------------------

  * pixman_region_union_o --

  *	Handle an overlapping band for the union operation. Picks the

  *	left-most rectangle each time and merges it into the region.

  *

  * Results:

  *	TRUE if successful.

  *

  * Side Effects:

  *	region is overwritten.

  *	overlap is set to TRUE if any boxes overlap.

  *

  *-----------------------------------------------------------------------

  */

 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)

 {

     box_type_t *next_rect;

     int x1;            /* left and right side of current union */

     int x2;

     critical_if_fail (y1 < y2);

     critical_if_fail (r1 != r1_end && r2 != r2_end);

     next_rect = PIXREGION_TOP (region);

     /* Start off current rectangle */

     if (r1->x1 < r2->x1)

     {

         x1 = r1->x1;

         x2 = r1->x2;

         r1++;

     }

     else

     {

         x1 = r2->x1;

         x2 = r2->x2;

         r2++;

     }

     while (r1 != r1_end && r2 != r2_end)

     {

         if (r1->x1 < r2->x1)

 	    MERGERECT (r1);

 	else

 	    MERGERECT (r2);

     }

     /* Finish off whoever (if any) is left */

     if (r1 != r1_end)

     {

         do

         {

             MERGERECT (r1);

 	}

         while (r1 != r1_end);

     }

     else if (r2 != r2_end)

     {

         do

         {

             MERGERECT (r2);

 	}

         while (r2 != r2_end);

     }

     /* Add current rectangle */

     NEWRECT (region, next_rect, x1, y1, x2, y2);

     return TRUE;

 }

 PIXMAN_EXPORT pixman_bool_t

 PREFIX(_intersect_rect) (region_type_t *dest,

 			 region_type_t *source,

 			 int x, int y,

 			 unsigned int width,

 			 unsigned int height)

 {

     region_type_t region;

     region.data = NULL;

     region.extents.x1 = x;

     region.extents.y1 = y;

     region.extents.x2 = x + width;

     region.extents.y2 = y + height;

     return PREFIX(_intersect) (dest, source, &region);

 }

 /* Convenience function for performing union of region with a

  * single rectangle

  */

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_union_rect) (region_type_t *dest,

                       region_type_t *source,

                       int            x,

 		      int            y,

                       unsigned int   width,

 		      unsigned int   height)

 {

     region_type_t region;

     region.extents.x1 = x;

     region.extents.y1 = y;

     region.extents.x2 = x + width;

     region.extents.y2 = y + height;

     if (!GOOD_RECT (&region.extents))

     {

         if (BAD_RECT (&region.extents))

             _pixman_log_error (FUNC, "Invalid rectangle passed");

 	return PREFIX (_copy) (dest, source);

     }

     region.data = NULL;

     return PREFIX (_union) (dest, source, &region);

 }

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_union) (region_type_t *new_reg,

                  region_type_t *reg1,

                  region_type_t *reg2)

 {

     /* Return TRUE if some overlap

      * between reg1, reg2

      */

     GOOD (reg1);

     GOOD (reg2);

     GOOD (new_reg);

     /*  checks all the simple cases */

     /*

      * Region 1 and 2 are the same

      */

     if (reg1 == reg2)

         return PREFIX (_copy) (new_reg, reg1);

     /*

      * Region 1 is empty

      */

     if (PIXREGION_NIL (reg1))

     {

         if (PIXREGION_NAR (reg1))

 	    return pixman_break (new_reg);

         if (new_reg != reg2)

 	    return PREFIX (_copy) (new_reg, reg2);

 	return TRUE;

     }

     /*

      * Region 2 is empty

      */

     if (PIXREGION_NIL (reg2))

     {

         if (PIXREGION_NAR (reg2))

 	    return pixman_break (new_reg);

 	if (new_reg != reg1)

 	    return PREFIX (_copy) (new_reg, reg1);

 	return TRUE;

     }

     /*

      * Region 1 completely subsumes region 2

      */

     if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))

     {

         if (new_reg != reg1)

 	    return PREFIX (_copy) (new_reg, reg1);

 	return TRUE;

     }

     /*

      * Region 2 completely subsumes region 1

      */

     if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))

     {

         if (new_reg != reg2)

 	    return PREFIX (_copy) (new_reg, reg2);

 	return TRUE;

     }

     if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE))

 	return FALSE;

     new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);

     new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);

     new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);

     new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);

     GOOD (new_reg);

     return TRUE;

 }

 /*======================================================================

  *	    Batch Rectangle Union

  *====================================================================*/

 #define EXCHANGE_RECTS(a, b)	\

     {                           \

         box_type_t t;		\

         t = rects[a];           \

         rects[a] = rects[b];    \

         rects[b] = t;           \

     }

 static void

 quick_sort_rects (

     box_type_t rects[],

     int        numRects)

 {

     int y1;

     int x1;

     int i, j;

     box_type_t *r;

     /* Always called with numRects > 1 */

     do

     {

         if (numRects == 2)

         {

             if (rects[0].y1 > rects[1].y1 ||

                 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))

 	    {

 		EXCHANGE_RECTS (0, 1);

 	    }

             return;

 	}

         /* Choose partition element, stick in location 0 */

         EXCHANGE_RECTS (0, numRects >> 1);

         y1 = rects[0].y1;

         x1 = rects[0].x1;

         /* Partition array */

         i = 0;

         j = numRects;

         do

         {

             r = &(rects[i]);

             do

             {

                 r++;

                 i++;

 	    }

 	    while (i != numRects && (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));

 	    r = &(rects[j]);

             do

             {

                 r--;

                 j--;

 	    }

             while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));

             if (i < j)

 		EXCHANGE_RECTS (i, j);

 	}

         while (i < j);

         /* Move partition element back to middle */

         EXCHANGE_RECTS (0, j);

         /* Recurse */

         if (numRects - j - 1 > 1)

 	    quick_sort_rects (&rects[j + 1], numRects - j - 1);

         numRects = j;

     }

     while (numRects > 1);

 }

 /*-

  *-----------------------------------------------------------------------

  * pixman_region_validate --

  *

  *      Take a ``region'' which is a non-y-x-banded random collection of

  *      rectangles, and compute a nice region which is the union of all the

  *      rectangles.

  *

  * Results:

  *	TRUE if successful.

  *

  * Side Effects:

  *      The passed-in ``region'' may be modified.

  *	overlap set to TRUE if any retangles overlapped,

  *      else FALSE;

  *

  * Strategy:

  *      Step 1. Sort the rectangles into ascending order with primary key y1

  *		and secondary key x1.

  *

  *      Step 2. Split the rectangles into the minimum number of proper y-x

  *		banded regions.  This may require horizontally merging

  *		rectangles, and vertically coalescing bands.  With any luck,

  *		this step in an identity transformation (ala the Box widget),

  *		or a coalescing into 1 box (ala Menus).

  *

  *	Step 3. Merge the separate regions down to a single region by calling

  *		pixman_region_union.  Maximize the work each pixman_region_union call does by using

  *		a binary merge.

  *

  *-----------------------------------------------------------------------

  */

 static pixman_bool_t

 validate (region_type_t * badreg)

 {

     /* Descriptor for regions under construction  in Step 2. */

     typedef struct

     {

         region_type_t reg;

         int prev_band;

         int cur_band;

     } region_info_t;

     region_info_t stack_regions[64];

     int numRects;                   /* Original numRects for badreg	    */

     region_info_t *ri;              /* Array of current regions		    */

     int num_ri;                     /* Number of entries used in ri	    */

     int size_ri;                    /* Number of entries available in ri    */

     int i;                          /* Index into rects			    */

     int j;                          /* Index into ri			    */

     region_info_t *rit;             /* &ri[j]				    */

     region_type_t *reg;             /* ri[j].reg			    */

     box_type_t *box;                /* Current box in rects		    */

     box_type_t *ri_box;             /* Last box in ri[j].reg		    */

     region_type_t *hreg;            /* ri[j_half].reg			    */

     pixman_bool_t ret = TRUE;

     if (!badreg->data)

     {

         GOOD (badreg);

         return TRUE;

     }

     numRects = badreg->data->numRects;

     if (!numRects)

     {

         if (PIXREGION_NAR (badreg))

 	    return FALSE;

         GOOD (badreg);

         return TRUE;

     }

     if (badreg->extents.x1 < badreg->extents.x2)

     {

         if ((numRects) == 1)

         {

             FREE_DATA (badreg);

             badreg->data = (region_data_type_t *) NULL;

 	}

         else

         {

             DOWNSIZE (badreg, numRects);

 	}

         GOOD (badreg);

 	return TRUE;

     }

     /* Step 1: Sort the rects array into ascending (y1, x1) order */

     quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects);

     /* Step 2: Scatter the sorted array into the minimum number of regions */

     /* Set up the first region to be the first rectangle in badreg */

     /* Note that step 2 code will never overflow the ri[0].reg rects array */

     ri = stack_regions;

     size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]);

     num_ri = 1;

     ri[0].prev_band = 0;

     ri[0].cur_band = 0;

     ri[0].reg = *badreg;

     box = PIXREGION_BOXPTR (&ri[0].reg);

     ri[0].reg.extents = *box;

     ri[0].reg.data->numRects = 1;

     badreg->extents = *pixman_region_empty_box;

     badreg->data = pixman_region_empty_data;

     /* Now scatter rectangles into the minimum set of valid regions.  If the

      * next rectangle to be added to a region would force an existing rectangle

      * in the region to be split up in order to maintain y-x banding, just

      * forget it.  Try the next region.  If it doesn't fit cleanly into any

      * region, make a new one.

      */

     for (i = numRects; --i > 0;)

     {

         box++;

         /* Look for a region to append box to */

         for (j = num_ri, rit = ri; --j >= 0; rit++)

         {

             reg = &rit->reg;

             ri_box = PIXREGION_END (reg);

             if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2)

             {

                 /* box is in same band as ri_box.  Merge or append it */

                 if (box->x1 <= ri_box->x2)

                 {

                     /* Merge it with ri_box */

                     if (box->x2 > ri_box->x2)

 			ri_box->x2 = box->x2;

 		}

                 else

                 {

                     RECTALLOC_BAIL (reg, 1, bail);

                     *PIXREGION_TOP (reg) = *box;

                     reg->data->numRects++;

 		}

                 goto next_rect;   /* So sue me */

 	    }

             else if (box->y1 >= ri_box->y2)

             {

                 /* Put box into new band */

                 if (reg->extents.x2 < ri_box->x2)

 		    reg->extents.x2 = ri_box->x2;

                 if (reg->extents.x1 > box->x1)

 		    reg->extents.x1 = box->x1;

                 COALESCE (reg, rit->prev_band, rit->cur_band);

                 rit->cur_band = reg->data->numRects;

                 RECTALLOC_BAIL (reg, 1, bail);

                 *PIXREGION_TOP (reg) = *box;

                 reg->data->numRects++;

                 goto next_rect;

 	    }

             /* Well, this region was inappropriate.  Try the next one. */

 	} /* for j */

         /* Uh-oh.  No regions were appropriate.  Create a new one. */

         if (size_ri == num_ri)

         {

             size_t data_size;

             /* Oops, allocate space for new region information */

             size_ri <<= 1;

             data_size = size_ri * sizeof(region_info_t);

             if (data_size / size_ri != sizeof(region_info_t))

 		goto bail;

             if (ri == stack_regions)

             {

                 rit = malloc (data_size);

                 if (!rit)

 		    goto bail;

                 memcpy (rit, ri, num_ri * sizeof (region_info_t));

 	    }

             else

             {

                 rit = (region_info_t *) realloc (ri, data_size);

                 if (!rit)

 		    goto bail;

 	    }

             ri = rit;

             rit = &ri[num_ri];

 	}

         num_ri++;

         rit->prev_band = 0;

         rit->cur_band = 0;

         rit->reg.extents = *box;

         rit->reg.data = (region_data_type_t *)NULL;

 	/* MUST force allocation */

         if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri))

 	    goto bail;

     next_rect: ;

     } /* for i */

     /* Make a final pass over each region in order to COALESCE and set

      * extents.x2 and extents.y2

      */

     for (j = num_ri, rit = ri; --j >= 0; rit++)

     {

         reg = &rit->reg;

         ri_box = PIXREGION_END (reg);

         reg->extents.y2 = ri_box->y2;

         if (reg->extents.x2 < ri_box->x2)

 	    reg->extents.x2 = ri_box->x2;

         COALESCE (reg, rit->prev_band, rit->cur_band);

 	if (reg->data->numRects == 1) /* keep unions happy below */

         {

             FREE_DATA (reg);

             reg->data = (region_data_type_t *)NULL;

 	}

     }

     /* Step 3: Union all regions into a single region */

     while (num_ri > 1)

     {

         int half = num_ri / 2;

         for (j = num_ri & 1; j < (half + (num_ri & 1)); j++)

         {

             reg = &ri[j].reg;

             hreg = &ri[j + half].reg;

             if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE))

 		ret = FALSE;

             if (hreg->extents.x1 < reg->extents.x1)

 		reg->extents.x1 = hreg->extents.x1;

             if (hreg->extents.y1 < reg->extents.y1)

 		reg->extents.y1 = hreg->extents.y1;

             if (hreg->extents.x2 > reg->extents.x2)

 		reg->extents.x2 = hreg->extents.x2;

             if (hreg->extents.y2 > reg->extents.y2)

 		reg->extents.y2 = hreg->extents.y2;

             FREE_DATA (hreg);

 	}

         num_ri -= half;

 	if (!ret)

 	    goto bail;

     }

     *badreg = ri[0].reg;

     if (ri != stack_regions)

 	free (ri);

     GOOD (badreg);

     return ret;

 bail:

     for (i = 0; i < num_ri; i++)

 	FREE_DATA (&ri[i].reg);

     if (ri != stack_regions)

 	free (ri);

     return pixman_break (badreg);

 }

 /*======================================================================

  *                Region Subtraction

  *====================================================================*/

 /*-

  *-----------------------------------------------------------------------

  * pixman_region_subtract_o --

  *	Overlapping band subtraction. x1 is the left-most point not yet

  *	checked.

  *

  * Results:

  *	TRUE if successful.

  *

  * Side Effects:

  *	region may have rectangles added to it.

  *

  *-----------------------------------------------------------------------

  */

 /*ARGSUSED*/

 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)

 {

     box_type_t *        next_rect;

     int x1;

     x1 = r1->x1;

     critical_if_fail (y1 < y2);

     critical_if_fail (r1 != r1_end && r2 != r2_end);

     next_rect = PIXREGION_TOP (region);

     do

     {

         if (r2->x2 <= x1)

         {

             /*

 	     * Subtrahend entirely to left of minuend: go to next subtrahend.

 	     */

             r2++;

 	}

         else if (r2->x1 <= x1)

         {

             /*

 	     * Subtrahend preceeds minuend: nuke left edge of minuend.

 	     */

             x1 = r2->x2;

             if (x1 >= r1->x2)

             {

                 /*

 		 * Minuend completely covered: advance to next minuend and

 		 * reset left fence to edge of new minuend.

 		 */

                 r1++;

                 if (r1 != r1_end)

 		    x1 = r1->x1;

 	    }

             else

             {

                 /*

 		 * Subtrahend now used up since it doesn't extend beyond

 		 * minuend

 		 */

                 r2++;

 	    }

 	}

         else if (r2->x1 < r1->x2)

         {

             /*

 	     * Left part of subtrahend covers part of minuend: add uncovered

 	     * part of minuend to region and skip to next subtrahend.

 	     */

             critical_if_fail (x1 < r2->x1);

             NEWRECT (region, next_rect, x1, y1, r2->x1, y2);

             x1 = r2->x2;

             if (x1 >= r1->x2)

             {

                 /*

 		 * Minuend used up: advance to new...

 		 */

                 r1++;

                 if (r1 != r1_end)

 		    x1 = r1->x1;

 	    }

             else

             {

                 /*

 		 * Subtrahend used up

 		 */

                 r2++;

 	    }

 	}

         else

         {

             /*

 	     * Minuend used up: add any remaining piece before advancing.

 	     */

             if (r1->x2 > x1)

 		NEWRECT (region, next_rect, x1, y1, r1->x2, y2);

             r1++;

 	    if (r1 != r1_end)

 		x1 = r1->x1;

 	}

     }

     while ((r1 != r1_end) && (r2 != r2_end));

     /*

      * Add remaining minuend rectangles to region.

      */

     while (r1 != r1_end)

     {

         critical_if_fail (x1 < r1->x2);

         NEWRECT (region, next_rect, x1, y1, r1->x2, y2);

         r1++;

         if (r1 != r1_end)

 	    x1 = r1->x1;

     }

     return TRUE;

 }

 /*-

  *-----------------------------------------------------------------------

  * pixman_region_subtract --

  *	Subtract reg_s from reg_m and leave the result in reg_d.

  *	S stands for subtrahend, M for minuend and D for difference.

  *

  * Results:

  *	TRUE if successful.

  *

  * Side Effects:

  *	reg_d is overwritten.

  *

  *-----------------------------------------------------------------------

  */

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_subtract) (region_type_t *reg_d,

                     region_type_t *reg_m,

                     region_type_t *reg_s)

 {

     GOOD (reg_m);

     GOOD (reg_s);

     GOOD (reg_d);

     /* check for trivial rejects */

     if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) ||

         !EXTENTCHECK (&reg_m->extents, &reg_s->extents))

     {

         if (PIXREGION_NAR (reg_s))

 	    return pixman_break (reg_d);

         return PREFIX (_copy) (reg_d, reg_m);

     }

     else if (reg_m == reg_s)

     {

         FREE_DATA (reg_d);

         reg_d->extents.x2 = reg_d->extents.x1;

         reg_d->extents.y2 = reg_d->extents.y1;

         reg_d->data = pixman_region_empty_data;

         return TRUE;

     }

     /* Add those rectangles in region 1 that aren't in region 2,

        do yucky substraction for overlaps, and

        just throw away rectangles in region 2 that aren't in region 1 */

     if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE))

 	return FALSE;

     /*

      * Can't alter reg_d's extents before we call pixman_op because

      * it might be one of the source regions and pixman_op depends

      * on the extents of those regions being unaltered. Besides, this

      * way there's no checking against rectangles that will be nuked

      * due to coalescing, so we have to examine fewer rectangles.

      */

     pixman_set_extents (reg_d);

     GOOD (reg_d);

     return TRUE;

 }

 /*======================================================================

  *	    Region Inversion

  *====================================================================*/

 /*-

  *-----------------------------------------------------------------------

  * pixman_region_inverse --

  *	Take a region and a box and return a region that is everything

  *	in the box but not in the region. The careful reader will note

  *	that this is the same as subtracting the region from the box...

  *

  * Results:

  *	TRUE.

  *

  * Side Effects:

  *	new_reg is overwritten.

  *

  *-----------------------------------------------------------------------

  */

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_inverse) (region_type_t *new_reg,  /* Destination region */

 		   region_type_t *reg1,     /* Region to invert */

 		   box_type_t *   inv_rect) /* Bounding box for inversion */

 {

     region_type_t inv_reg; /* Quick and dirty region made from the

 			    * bounding box */

     GOOD (reg1);

     GOOD (new_reg);

     /* check for trivial rejects */

     if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, &reg1->extents))

     {

         if (PIXREGION_NAR (reg1))

 	    return pixman_break (new_reg);

         new_reg->extents = *inv_rect;

         FREE_DATA (new_reg);

         new_reg->data = (region_data_type_t *)NULL;

         return TRUE;

     }

     /* Add those rectangles in region 1 that aren't in region 2,

      * do yucky substraction for overlaps, and

      * just throw away rectangles in region 2 that aren't in region 1

      */

     inv_reg.extents = *inv_rect;

     inv_reg.data = (region_data_type_t *)NULL;

     if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE))

 	return FALSE;

     /*

      * Can't alter new_reg's extents before we call pixman_op because

      * it might be one of the source regions and pixman_op depends

      * on the extents of those regions being unaltered. Besides, this

      * way there's no checking against rectangles that will be nuked

      * due to coalescing, so we have to examine fewer rectangles.

      */

     pixman_set_extents (new_reg);

     GOOD (new_reg);

     return TRUE;

 }

 /* In time O(log n), locate the first box whose y2 is greater than y.

  * Return @end if no such box exists.

  */

 static box_type_t *

 find_box_for_y (box_type_t *begin, box_type_t *end, int y)

 {

     box_type_t *mid;

     if (end == begin)

 	return end;

     if (end - begin == 1)

     {

 	if (begin->y2 > y)

 	    return begin;

 	else

 	    return end;

     }

     mid = begin + (end - begin) / 2;

     if (mid->y2 > y)

     {

 	/* If no box is found in [begin, mid], the function

 	 * will return @mid, which is then known to be the

 	 * correct answer.

 	 */

 	return find_box_for_y (begin, mid, y);

     }

     else

     {

 	return find_box_for_y (mid, end, y);

     }

 }

 /*

  *   rect_in(region, rect)

  *   This routine takes a pointer to a region and a pointer to a box

  *   and determines if the box is outside/inside/partly inside the region.

  *

  *   The idea is to travel through the list of rectangles trying to cover the

  *   passed box with them. Anytime a piece of the rectangle isn't covered

  *   by a band of rectangles, part_out is set TRUE. Any time a rectangle in

  *   the region covers part of the box, part_in is set TRUE. The process ends

  *   when either the box has been completely covered (we reached a band that

  *   doesn't overlap the box, part_in is TRUE and part_out is false), the

  *   box has been partially covered (part_in == part_out == TRUE -- because of

  *   the banding, the first time this is true we know the box is only

  *   partially in the region) or is outside the region (we reached a band

  *   that doesn't overlap the box at all and part_in is false)

  */

 PIXMAN_EXPORT pixman_region_overlap_t

 PREFIX (_contains_rectangle) (region_type_t *  region,

 			      box_type_t *     prect)

 {

     box_type_t *     pbox;

     box_type_t *     pbox_end;

     int part_in, part_out;

     int numRects;

     int x, y;

     GOOD (region);

     numRects = PIXREGION_NUMRECTS (region);

     /* useful optimization */

     if (!numRects || !EXTENTCHECK (&region->extents, prect))

 	return(PIXMAN_REGION_OUT);

     if (numRects == 1)

     {

         /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */

         if (SUBSUMES (&region->extents, prect))

 	    return(PIXMAN_REGION_IN);

         else

 	    return(PIXMAN_REGION_PART);

     }

     part_out = FALSE;

     part_in = FALSE;

     /* (x,y) starts at upper left of rect, moving to the right and down */

     x = prect->x1;

     y = prect->y1;

     /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */

     for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;

 	 pbox != pbox_end;

 	 pbox++)

     {

 	/* getting up to speed or skipping remainder of band */

 	if (pbox->y2 <= y)

 	{

 	    if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end)

 		break;

 	}

         if (pbox->y1 > y)

         {

             part_out = TRUE;     /* missed part of rectangle above */

             if (part_in || (pbox->y1 >= prect->y2))

 		break;

             y = pbox->y1;       /* x guaranteed to be == prect->x1 */

 	}

         if (pbox->x2 <= x)

 	    continue;           /* not far enough over yet */

         if (pbox->x1 > x)

         {

             part_out = TRUE;     /* missed part of rectangle to left */

             if (part_in)

 		break;

 	}

         if (pbox->x1 < prect->x2)

         {

             part_in = TRUE;      /* definitely overlap */

             if (part_out)

 		break;

 	}

         if (pbox->x2 >= prect->x2)

         {

             y = pbox->y2;       /* finished with this band */

             if (y >= prect->y2)

 		break;

             x = prect->x1;      /* reset x out to left again */

 	}

         else

         {

             /*

 	     * Because boxes in a band are maximal width, if the first box

 	     * to overlap the rectangle doesn't completely cover it in that

 	     * band, the rectangle must be partially out, since some of it

 	     * will be uncovered in that band. part_in will have been set true

 	     * by now...

 	     */

             part_out = TRUE;

             break;

 	}

     }

     if (part_in)

     {

         if (y < prect->y2)

 	    return PIXMAN_REGION_PART;

         else

 	    return PIXMAN_REGION_IN;

     }

     else

     {

         return PIXMAN_REGION_OUT;

     }

 }

 /* PREFIX(_translate) (region, x, y)

  * translates in place

  */

 PIXMAN_EXPORT void

 PREFIX (_translate) (region_type_t *region, int x, int y)

 {

     overflow_int_t x1, x2, y1, y2;

     int nbox;

     box_type_t * pbox;

     GOOD (region);

     region->extents.x1 = x1 = region->extents.x1 + x;

     region->extents.y1 = y1 = region->extents.y1 + y;

     region->extents.x2 = x2 = region->extents.x2 + x;

     region->extents.y2 = y2 = region->extents.y2 + y;

     if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0)

     {

         if (region->data && (nbox = region->data->numRects))

         {

             for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)

             {

                 pbox->x1 += x;

                 pbox->y1 += y;

                 pbox->x2 += x;

                 pbox->y2 += y;

 	    }

 	}

         return;

     }

     if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)

     {

         region->extents.x2 = region->extents.x1;

         region->extents.y2 = region->extents.y1;

         FREE_DATA (region);

         region->data = pixman_region_empty_data;

         return;

     }

     if (x1 < PIXMAN_REGION_MIN)

 	region->extents.x1 = PIXMAN_REGION_MIN;

     else if (x2 > PIXMAN_REGION_MAX)

 	region->extents.x2 = PIXMAN_REGION_MAX;

     if (y1 < PIXMAN_REGION_MIN)

 	region->extents.y1 = PIXMAN_REGION_MIN;

     else if (y2 > PIXMAN_REGION_MAX)

 	region->extents.y2 = PIXMAN_REGION_MAX;

     if (region->data && (nbox = region->data->numRects))

     {

         box_type_t * pbox_out;

         for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)

         {

             pbox_out->x1 = x1 = pbox->x1 + x;

             pbox_out->y1 = y1 = pbox->y1 + y;

             pbox_out->x2 = x2 = pbox->x2 + x;

             pbox_out->y2 = y2 = pbox->y2 + y;

             if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) |

                  (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)

             {

                 region->data->numRects--;

                 continue;

 	    }

             if (x1 < PIXMAN_REGION_MIN)

 		pbox_out->x1 = PIXMAN_REGION_MIN;

             else if (x2 > PIXMAN_REGION_MAX)

 		pbox_out->x2 = PIXMAN_REGION_MAX;

             if (y1 < PIXMAN_REGION_MIN)

 		pbox_out->y1 = PIXMAN_REGION_MIN;

             else if (y2 > PIXMAN_REGION_MAX)

 		pbox_out->y2 = PIXMAN_REGION_MAX;

             pbox_out++;

 	}

         if (pbox_out != pbox)

         {

             if (region->data->numRects == 1)

             {

                 region->extents = *PIXREGION_BOXPTR (region);

                 FREE_DATA (region);

                 region->data = (region_data_type_t *)NULL;

 	    }

             else

 	    {

 		pixman_set_extents (region);

 	    }

 	}

     }

     GOOD (region);

 }

 PIXMAN_EXPORT void

 PREFIX (_reset) (region_type_t *region, box_type_t *box)

 {

     GOOD (region);

     critical_if_fail (GOOD_RECT (box));

     region->extents = *box;

     FREE_DATA (region);

     region->data = NULL;

 }

 PIXMAN_EXPORT void

 PREFIX (_clear) (region_type_t *region)

 {

     GOOD (region);

     FREE_DATA (region);

     region->extents = *pixman_region_empty_box;

     region->data = pixman_region_empty_data;

 }

 /* box is "return" value */

 PIXMAN_EXPORT int

 PREFIX (_contains_point) (region_type_t * region,

                           int x, int y,

                           box_type_t * box)

 {

     box_type_t *pbox, *pbox_end;

     int numRects;

     GOOD (region);

     numRects = PIXREGION_NUMRECTS (region);

     if (!numRects || !INBOX (&region->extents, x, y))

 	return(FALSE);

     if (numRects == 1)

     {

         if (box)

 	    *box = region->extents;

         return(TRUE);

     }

     pbox = PIXREGION_BOXPTR (region);

     pbox_end = pbox + numRects;

     pbox = find_box_for_y (pbox, pbox_end, y);

     for (;pbox != pbox_end; pbox++)

     {

         if ((y < pbox->y1) || (x < pbox->x1))

 	    break;              /* missed it */

         if (x >= pbox->x2)

 	    continue;           /* not there yet */

         if (box)

 	    *box = *pbox;

         return(TRUE);

     }

     return(FALSE);

 }

 PIXMAN_EXPORT int

 PREFIX (_not_empty) (region_type_t * region)

 {

     GOOD (region);

     return(!PIXREGION_NIL (region));

 }

 PIXMAN_EXPORT box_type_t *

 PREFIX (_extents) (region_type_t * region)

 {

     GOOD (region);

     return(&region->extents);

 }

 /*

  * Clip a list of scanlines to a region.  The caller has allocated the

  * space.  FSorted is non-zero if the scanline origins are in ascending order.

  *

  * returns the number of new, clipped scanlines.

  */

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_selfcheck) (region_type_t *reg)

 {

     int i, numRects;

     if ((reg->extents.x1 > reg->extents.x2) ||

         (reg->extents.y1 > reg->extents.y2))

     {

 	return FALSE;

     }

     numRects = PIXREGION_NUMRECTS (reg);

     if (!numRects)

     {

 	return ((reg->extents.x1 == reg->extents.x2) &&

 	        (reg->extents.y1 == reg->extents.y2) &&

 	        (reg->data->size || (reg->data == pixman_region_empty_data)));

     }

     else if (numRects == 1)

     {

 	return (!reg->data);

     }

     else

     {

         box_type_t * pbox_p, * pbox_n;

         box_type_t box;

         pbox_p = PIXREGION_RECTS (reg);

         box = *pbox_p;

         box.y2 = pbox_p[numRects - 1].y2;

         pbox_n = pbox_p + 1;

         for (i = numRects; --i > 0; pbox_p++, pbox_n++)

         {

             if ((pbox_n->x1 >= pbox_n->x2) ||

                 (pbox_n->y1 >= pbox_n->y2))

 	    {

 		return FALSE;

 	    }

             if (pbox_n->x1 < box.x1)

 		box.x1 = pbox_n->x1;

             if (pbox_n->x2 > box.x2)

 		box.x2 = pbox_n->x2;

             if ((pbox_n->y1 < pbox_p->y1) ||

                 ((pbox_n->y1 == pbox_p->y1) &&

                  ((pbox_n->x1 < pbox_p->x2) || (pbox_n->y2 != pbox_p->y2))))

 	    {

 		return FALSE;

 	    }

 	}

         return ((box.x1 == reg->extents.x1) &&

                 (box.x2 == reg->extents.x2) &&

                 (box.y1 == reg->extents.y1) &&

                 (box.y2 == reg->extents.y2));

     }

 }

 PIXMAN_EXPORT pixman_bool_t

 PREFIX (_init_rects) (region_type_t *region,

                       const box_type_t *boxes, int count)

 {

     box_type_t *rects;

     int displacement;

     int i;

     /* if it's 1, then we just want to set the extents, so call

      * the existing method. */

     if (count == 1)

     {

         PREFIX (_init_rect) (region,

                              boxes[0].x1,

                              boxes[0].y1,

                              boxes[0].x2 - boxes[0].x1,

                              boxes[0].y2 - boxes[0].y1);

         return TRUE;

     }

     PREFIX (_init) (region);

     /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is

      * a special case, and causing pixman_rect_alloc would cause

      * us to leak memory (because the 0-rect case should be the

      * static pixman_region_empty_data data).

      */

     if (count == 0)

 	return TRUE;

     if (!pixman_rect_alloc (region, count))

 	return FALSE;

     rects = PIXREGION_RECTS (region);

     /* Copy in the rects */

     memcpy (rects, boxes, sizeof(box_type_t) * count);

     region->data->numRects = count;

     /* Eliminate empty and malformed rectangles */

     displacement = 0;

     for (i = 0; i < count; ++i)

     {

         box_type_t *box = &rects[i];

         if (box->x1 >= box->x2 || box->y1 >= box->y2)

 	    displacement++;

         else if (displacement)

 	    rects[i - displacement] = rects[i];

     }

     region->data->numRects -= displacement;

     /* If eliminating empty rectangles caused there

      * to be only 0 or 1 rectangles, deal with that.

      */

     if (region->data->numRects == 0)

     {

         FREE_DATA (region);

         PREFIX (_init) (region);

         return TRUE;

     }

     if (region->data->numRects == 1)

     {

         region->extents = rects[0];

         FREE_DATA (region);

         region->data = NULL;

         GOOD (region);

         return TRUE;

     }

     /* Validate */

     region->extents.x1 = region->extents.x2 = 0;

     return validate (region);

 }

 #define READ(_ptr) (*(_ptr))

 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)

 {

     if ((rx1 < rx2) && (ry1 < ry2) &&

 	(!(reg->data->numRects &&

 	   ((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) &&

 	   ((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2))))

     {

 	if (reg->data->numRects == reg->data->size)

 	{

 	    if (!pixman_rect_alloc (reg, 1))

 		return NULL;

 	    *first_rect = PIXREGION_BOXPTR(reg);

 	    r = *first_rect + reg->data->numRects;

 	}

 	r->x1 = rx1;

 	r->y1 = ry1;

 	r->x2 = rx2;

 	r->y2 = ry2;

 	reg->data->numRects++;

 	if (r->x1 < reg->extents.x1)

 	    reg->extents.x1 = r->x1;

 	if (r->x2 > reg->extents.x2)

 	    reg->extents.x2 = r->x2;

 	r++;

     }

     return r;

 }

 /* Convert bitmap clip mask into clipping region.

  * First, goes through each line and makes boxes by noting the transitions

  * from 0 to 1 and 1 to 0.

  * Then it coalesces the current line with the previous if they have boxes

  * at the same X coordinates.

  * Stride is in number of uint32_t per line.

  */

 PIXMAN_EXPORT void

 PREFIX (_init_from_image) (region_type_t *region,

                            pixman_image_t *image)

 {

     uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1);

     box_type_t *first_rect, *rects, *prect_line_start;

     box_type_t *old_rect, *new_rect;

     uint32_t *pw, w, *pw_line, *pw_line_end;

     int	irect_prev_start, irect_line_start;

     int	h, base, rx1 = 0, crects;

     int	ib;

     pixman_bool_t in_box, same;

     int width, height, stride;

     PREFIX(_init) (region);

     critical_if_fail (region->data);

     return_if_fail (image->type == BITS);

     return_if_fail (image->bits.format == PIXMAN_a1);

     pw_line = pixman_image_get_data (image);

     width = pixman_image_get_width (image);

     height = pixman_image_get_height (image);

     stride = pixman_image_get_stride (image) / 4;

     first_rect = PIXREGION_BOXPTR(region);

     rects = first_rect;

     region->extents.x1 = width - 1;

     region->extents.x2 = 0;

     irect_prev_start = -1;

     for (h = 0; h < height; h++)

     {

         pw = pw_line;

         pw_line += stride;

         irect_line_start = rects - first_rect;

         /* If the Screen left most bit of the word is set, we're starting in

          * a box */

         if (READ(pw) & mask0)

         {

             in_box = TRUE;

             rx1 = 0;

         }

         else

         {

             in_box = FALSE;

         }