Quellcode-Bibliothek pixman-region.c

/*
 * 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) \
     : (box_type_t *)&(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) (const region_type_t *reg1, const 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 (®ion->extents))
    {
        if (BAD_RECT (®ion->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, const 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) (const region_type_t *region)
{
    return PIXREGION_NUMRECTS (region);
}

PIXMAN_EXPORT box_type_t *
PREFIX (_rectangles) (const 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, const 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     */
    const region_type_t *  reg1,                  /* First region in operation     */
    const 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,
                     const region_type_t *        reg1,
                     const region_type_t *        reg2)
{
    GOOD (reg1);
    GOOD (reg2);
    GOOD (new_reg);

    /* check for trivial reject */
    if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||
        !EXTENTCHECK (®1->extents, ®2->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 (®2->extents, ®1->extents))
    {
        return PREFIX (_copy) (new_reg, reg1);
    }
    else if (!reg1->data && SUBSUMES (®1->extents, ®2->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,
    const 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, ®ion);
}

/* Convenience function for performing union of region with a
 * single rectangle
 */
PIXMAN_EXPORT pixman_bool_t
PREFIX (_union_rect) (region_type_t *dest,
                      const 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 (®ion.extents))
    {
        if (BAD_RECT (®ion.extents))
            _pixman_log_error (FUNC, "Invalid rectangle passed");
 return PREFIX (_copy) (dest, source);
    }

    region.data = NULL;

    return PREFIX (_union) (dest, source, ®ion);
}

PIXMAN_EXPORT pixman_bool_t
PREFIX (_union) (region_type_t *      new_reg,
                 const region_type_t *reg1,
                 const 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 (®1->extents, ®2->extents))
    {
        if (new_reg != reg1)
     return PREFIX (_copy) (new_reg, reg1);

 return TRUE;
    }

    /*
     * Region 2 completely subsumes region 1
     */
    if (!reg2->data && SUBSUMES (®2->extents, ®1->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 precedes 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,
                    const region_type_t *reg_m,
                    const 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 (®_m->extents, ®_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 subtraction 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 */
     const region_type_t *reg1,     /* Region to invert */
     const 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, ®1->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 subtraction 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) (const region_type_t *  region,
         const 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 (®ion->extents, prect))
 return(PIXMAN_REGION_OUT);

    if (numRects == 1)
    {
        /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
        if (SUBSUMES (®ion->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);

    if (x == 0 && y == 0)
        return;

    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, const 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) (const 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 (®ion->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 (_empty) (const region_type_t * region)
{
    GOOD (region);

    return(PIXREGION_NIL (region));
}

PIXMAN_EXPORT int
PREFIX (_not_empty) (const region_type_t * region)
{
    GOOD (region);

    return(!PIXREGION_NIL (region));
}

PIXMAN_EXPORT box_type_t *
PREFIX (_extents) (const region_type_t * region)
{
    GOOD (region);

    return(box_type_t *)(®ion->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;
        }

        /* Process all words which are fully in the pixmap */
        pw_line_end = pw + (width >> 5);
        for (base = 0; pw < pw_line_end; base += 32)
        {
            w = READ(pw++);
            if (in_box)
            {
                if (!~w)
                    continue;
            }
            else
            {
                if (!w)
                    continue;
            }
            for (ib = 0; ib < 32; ib++)
            {
                /* If the Screen left most bit of the word is set, we're
                 * starting a box */
                if (w & mask0)
                {
                    if (!in_box)
                    {
                        rx1 = base + ib;
                        /* start new box */
                        in_box = TRUE;
                    }
                }
                else
                {
                    if (in_box)
                    {
                        /* end box */
                        rects = bitmap_addrect (region, rects, &first_rect,
                                                rx1, h, base + ib, h + 1);
                        if (rects == NULL)
                            goto error;
                        in_box = FALSE;
                    }
                }
                /* Shift the word VISUALLY left one. */
                w = SCREEN_SHIFT_LEFT(w, 1);
            }
        }

        if (width & 31)
        {
            /* Process final partial word on line */
             w = READ(pw++);
            for (ib = 0; ib < (width & 31); ib++)
            {
                /* If the Screen left most bit of the word is set, we're
                 * starting a box */
                if (w & mask0)
                {
                    if (!in_box)
                    {
                        rx1 = base + ib;
                        /* start new box */
                        in_box = TRUE;
                    }
                }
                else
                {
                    if (in_box)
                    {
                        /* end box */
                        rects = bitmap_addrect(region, rects, &first_rect,
            rx1, h, base + ib, h + 1);
   if (rects == NULL)
       goto error;
                        in_box = FALSE;
                    }
                }
                /* Shift the word VISUALLY left one. */
                w = SCREEN_SHIFT_LEFT(w, 1);
            }
        }
        /* If scanline ended with last bit set, end the box */
        if (in_box)
        {
            rects = bitmap_addrect(region, rects, &first_rect,
       rx1, h, base + (width & 31), h + 1);
     if (rects == NULL)
  goto error;
        }
        /* if all rectangles on this line have the same x-coords as
         * those on the previous line, then add 1 to all the previous  y2s and
         * throw away all the rectangles from this line
         */
        same = FALSE;
        if (irect_prev_start != -1)
        {
            crects = irect_line_start - irect_prev_start;
            if (crects != 0 &&
                crects == ((rects - first_rect) - irect_line_start))
            {
                old_rect = first_rect + irect_prev_start;
                new_rect = prect_line_start = first_rect + irect_line_start;
                same = TRUE;
                while (old_rect < prect_line_start)
                {
                    if ((old_rect->x1 != new_rect->x1) ||
                        (old_rect->x2 != new_rect->x2))
                    {
                          same = FALSE;
                          break;
                    }
                    old_rect++;
                    new_rect++;
                }
                if (same)
                {
                    old_rect = first_rect + irect_prev_start;
                    while (old_rect < prect_line_start)
                    {
                        old_rect->y2 += 1;
                        old_rect++;
                    }
                    rects -= crects;
                    region->data->numRects -= crects;
                }
            }
        }
        if(!same)
            irect_prev_start = irect_line_start;
    }
    if (!region->data->numRects)
    {
        region->extents.x1 = region->extents.x2 = 0;
    }
    else
    {
        region->extents.y1 = PIXREGION_BOXPTR(region)->y1;
        region->extents.y2 = PIXREGION_END(region)->y2;
        if (region->data->numRects == 1)
        {
            free (region->data);
            region->data = NULL;
        }
    }

 error:
    return;
}