pixman/pixman-region.c

   1 /***********************************************************
   2
   3 Copyright 1987, 1988, 1989, 1998  The Open Group
   4
   5 Permission to use, copy, modify, distribute, and sell this software and its
   6 documentation for any purpose is hereby granted without fee, provided that
   7 the above copyright notice appear in all copies and that both that
   8 copyright notice and this permission notice appear in supporting
   9 documentation.
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  20
  21 Except as contained in this notice, the name of The Open Group shall not be
  22 used in advertising or otherwise to promote the sale, use or other dealings
  23 in this Software without prior written authorization from The Open Group.
  24
  25 Copyright 1987, 1988, 1989 by
  26 Digital Equipment Corporation, Maynard, Massachusetts.
  27
  28                         All Rights Reserved
  29
  30 Permission to use, copy, modify, and distribute this software and its
  31 documentation for any purpose and without fee is hereby granted,
  32 provided that the above copyright notice appear in all copies and that
  33 both that copyright notice and this permission notice appear in
  34 supporting documentation, and that the name of Digital not be
  35 used in advertising or publicity pertaining to distribution of the
  36 software without specific, written prior permission.
  37
  38 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  39 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  40 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  41 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  42 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  43 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  44 SOFTWARE.
  45
  46 ******************************************************************/
  47
  48 #ifdef HAVE_CONFIG_H
  49 #include <config.h>
  50 #endif
  51
  52 #include <stdlib.h>
  53 #include <limits.h>
  54 #include <string.h>
  55 #include <stdio.h>
  56
  57 #include "pixman-private.h"
  58
  59 typedef struct pixman_region16_point {
  60     int x, y;
  61 } pixman_region16_point_t;
  62
  63 #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
  64 /* not a region */
  65 #define PIXREGION_NAR(reg)      ((reg)->data == pixman_brokendata)
  66 #define PIXREGION_NUM_RECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
  67 #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
  68 #define PIXREGION_RECTS(reg) ((reg)->data ? (pixman_box16_t *)((reg)->data + 1) \
  69                                        : &(reg)->extents)
  70 #define PIXREGION_BOXPTR(reg) ((pixman_box16_t *)((reg)->data + 1))
  71 #define PIXREGION_BOX(reg,i) (&PIXREGION_BOXPTR(reg)[i])
  72 #define PIXREGION_TOP(reg) PIXREGION_BOX(reg, (reg)->data->numRects)
  73 #define PIXREGION_END(reg) PIXREGION_BOX(reg, (reg)->data->numRects - 1)
  74
  75
  76 #undef assert
  77 #ifdef DEBUG_PIXREGION
  78 #define assert(expr) {if (!(expr)) \
  79                 FatalError("Assertion failed file %s, line %d: expr\n", \
  80                         __FILE__, __LINE__); }
  81 #else
  82 #define assert(expr)
  83 #endif
  84
  85 #define PREFIX(x) x
  86
  87 #define good(reg) assert(PREFIX(pixman_region_selfcheck) (reg))
  88
  89 #undef MIN
  90 #define MIN(a,b) ((a) < (b) ? (a) : (b))
  91 #undef MAX
  92 #define MAX(a,b) ((a) > (b) ? (a) : (b))
  93
  94 static const pixman_box16_t _pixman_region_emptyBox = {0, 0, 0, 0};
  95 static const pixman_region16_data_t _pixman_region_emptyData = {0, 0};
  96 static const pixman_region16_data_t _pixman_brokendata = {0, 0};
  97
  98 static pixman_box16_t *pixman_region_emptyBox = (pixman_box16_t *)&_pixman_region_emptyBox;
  99 static pixman_region16_data_t *pixman_region_emptyData = (pixman_region16_data_t *)&_pixman_region_emptyData;
 100 static pixman_region16_data_t *pixman_brokendata = (pixman_region16_data_t *)&_pixman_brokendata;
 101
 102 /* This function exists only to make it possible to preserve the X ABI - it should
 103  * go away at first opportunity.
 104  *
 105  * The problem is that the X ABI exports the three structs and has used
 106  * them through macros. So the X server calls this function with
 107  * the addresses of those structs which makes the existing code continue to
 108  * work.
 109  */
 110 void
 111 PREFIX(pixman_region_set_static_pointers) (pixman_box16_t *empty_box,
 112                                    pixman_region16_data_t *empty_data,
 113                                    pixman_region16_data_t *broken_data)
 114 {
 115     pixman_region_emptyBox = empty_box;
 116     pixman_region_emptyData = empty_data;
 117     pixman_brokendata = broken_data;
 118 }
 119
 120 static pixman_bool_t
 121 pixman_break (pixman_region16_t *pReg);
 122
 123 /*
 124  * The functions in this file implement the Region abstraction used extensively
 125  * throughout the X11 sample server. A Region is simply a set of disjoint
 126  * (non-overlapping) rectangles, plus an "extent" rectangle which is the
 127  * smallest single rectangle that contains all the non-overlapping rectangles.
 128  *
 129  * A Region is implemented as a "y-x-banded" array of rectangles.  This array
 130  * imposes two degrees of order.  First, all rectangles are sorted by top side
 131  * y coordinate first (y1), and then by left side x coordinate (x1).
 132  *
 133  * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a
 134  * band has the same top y coordinate (y1), and each has the same bottom y
 135  * coordinate (y2).  Thus all rectangles in a band differ only in their left
 136  * and right side (x1 and x2).  Bands are implicit in the array of rectangles:
 137  * there is no separate list of band start pointers.
 138  *
 139  * The y-x band representation does not minimize rectangles.  In particular,
 140  * if a rectangle vertically crosses a band (the rectangle has scanlines in
 141  * the y1 to y2 area spanned by the band), then the rectangle may be broken
 142  * down into two or more smaller rectangles stacked one atop the other.
 143  *
 144  *  -----------                             -----------
 145  *  |         |                             |         |             band 0
 146  *  |         |  --------                   -----------  --------
 147  *  |         |  |      |  in y-x banded    |         |  |      |   band 1
 148  *  |         |  |      |  form is          |         |  |      |
 149  *  -----------  |      |                   -----------  --------
 150  *               |      |                                |      |   band 2
 151  *               --------                                --------
 152  *
 153  * An added constraint on the rectangles is that they must cover as much
 154  * horizontal area as possible: no two rectangles within a band are allowed
 155  * to touch.
 156  *
 157  * Whenever possible, bands will be merged together to cover a greater vertical
 158  * distance (and thus reduce the number of rectangles). Two bands can be merged
 159  * only if the bottom of one touches the top of the other and they have
 160  * rectangles in the same places (of the same width, of course).
 161  *
 162  * Adam de Boor wrote most of the original region code.  Joel McCormack
 163  * substantially modified or rewrote most of the core arithmetic routines, and
 164  * added pixman_region_validate in order to support several speed improvements to
 165  * pixman_region_validateTree.  Bob Scheifler changed the representation to be more
 166  * compact when empty or a single rectangle, and did a bunch of gratuitous
 167  * reformatting. Carl Worth did further gratuitous reformatting while re-merging
 168  * the server and client region code into libpixregion.
 169  */
 170
 171 /*  true iff two Boxes overlap */
 172 #define EXTENTCHECK(r1,r2) \
 173       (!( ((r1)->x2 <= (r2)->x1)  || \
 174           ((r1)->x1 >= (r2)->x2)  || \
 175           ((r1)->y2 <= (r2)->y1)  || \
 176           ((r1)->y1 >= (r2)->y2) ) )
 177
 178 /* true iff (x,y) is in Box */
 179 #define INBOX(r,x,y) \
 180       ( ((r)->x2 >  x) && \
 181         ((r)->x1 <= x) && \
 182         ((r)->y2 >  y) && \
 183         ((r)->y1 <= y) )
 184
 185 /* true iff Box r1 contains Box r2 */
 186 #define SUBSUMES(r1,r2) \
 187       ( ((r1)->x1 <= (r2)->x1) && \
 188         ((r1)->x2 >= (r2)->x2) && \
 189         ((r1)->y1 <= (r2)->y1) && \
 190         ((r1)->y2 >= (r2)->y2) )
 191
 192 static size_t
 193 PIXREGION_SZOF(size_t n)
 194 {
 195     size_t size = n * sizeof(pixman_box16_t);
 196     if (n > UINT32_MAX / sizeof(pixman_box16_t))
 197         return 0;
 198
 199     if (sizeof(pixman_region16_data_t) > UINT32_MAX - size)
 200         return 0;
 201
 202     return size + sizeof(pixman_region16_data_t);
 203 }
 204
 205 static void *
 206 allocData(size_t n)
 207 {
 208     size_t sz = PIXREGION_SZOF(n);
 209     if (!sz)
 210         return NULL;
 211
 212     return malloc(sz);
 213 }
 214
 215 #define freeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data)
 216
 217 #define RECTALLOC_BAIL(pReg,n,bail) \
 218 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
 219     if (!pixman_rect_alloc(pReg, n)) { goto bail; }
 220
 221 #define RECTALLOC(pReg,n) \
 222 if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
 223     if (!pixman_rect_alloc(pReg, n)) { return FALSE; }
 224
 225 #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2)      \
 226 {                                               \
 227     pNextRect->x1 = nx1;                        \
 228     pNextRect->y1 = ny1;                        \
 229     pNextRect->x2 = nx2;                        \
 230     pNextRect->y2 = ny2;                        \
 231     pNextRect++;                                \
 232 }
 233
 234 #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2)                 \
 235 {                                                                       \
 236     if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
 237     {                                                                   \
 238         if (!pixman_rect_alloc(pReg, 1))                                        \
 239             return FALSE;                                               \
 240         pNextRect = PIXREGION_TOP(pReg);                                        \
 241     }                                                                   \
 242     ADDRECT(pNextRect,nx1,ny1,nx2,ny2);                                 \
 243     pReg->data->numRects++;                                             \
 244     assert(pReg->data->numRects<=pReg->data->size);                     \
 245 }
 246
 247 #define DOWNSIZE(reg,numRects)                                          \
 248     if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
 249     {                                                                   \
 250         pixman_region16_data_t * NewData;                               \
 251         size_t data_size = PIXREGION_SZOF(numRects);                    \
 252         if (!data_size)                                                 \
 253             NewData = NULL;                                             \
 254         else                                                            \
 255             NewData = (pixman_region16_data_t *)realloc((reg)->data, data_size); \
 256         if (NewData)                                                    \
 257         {                                                               \
 258             NewData->size = (numRects);                                 \
 259             (reg)->data = NewData;                                      \
 260         }                                                               \
 261     }
 262
 263 pixman_bool_t
 264 PREFIX(pixman_region_equal) (reg1, reg2)
 265     pixman_region16_t * reg1;
 266     pixman_region16_t * reg2;
 267 {
 268     int i;
 269     pixman_box16_t *rects1;
 270     pixman_box16_t *rects2;
 271
 272     if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
 273     if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
 274     if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
 275     if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
 276     if (PIXREGION_NUM_RECTS(reg1) != PIXREGION_NUM_RECTS(reg2)) return FALSE;
 277
 278     rects1 = PIXREGION_RECTS(reg1);
 279     rects2 = PIXREGION_RECTS(reg2);
 280     for (i = 0; i != PIXREGION_NUM_RECTS(reg1); i++) {
 281         if (rects1[i].x1 != rects2[i].x1) return FALSE;
 282         if (rects1[i].x2 != rects2[i].x2) return FALSE;
 283         if (rects1[i].y1 != rects2[i].y1) return FALSE;
 284         if (rects1[i].y2 != rects2[i].y2) return FALSE;
 285     }
 286     return TRUE;
 287 }
 288
 289 int
 290 PREFIX(pixman_region16_print) (rgn)
 291     pixman_region16_t * rgn;
 292 {
 293     int num, size;
 294     int i;
 295     pixman_box16_t * rects;
 296
 297     num = PIXREGION_NUM_RECTS(rgn);
 298     size = PIXREGION_SIZE(rgn);
 299     rects = PIXREGION_RECTS(rgn);
 300     fprintf(stderr, "num: %d size: %d\n", num, size);
 301     fprintf(stderr, "extents: %d %d %d %d\n",
 302            rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
 303     for (i = 0; i < num; i++)
 304         fprintf(stderr, "%d %d %d %d \n",
 305                 rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
 306     fprintf(stderr, "\n");
 307     return(num);
 308 }
 309
 310
 311 void
 312 PREFIX(pixman_region_init) (pixman_region16_t *region)
 313 {
 314     region->extents = *pixman_region_emptyBox;
 315     region->data = pixman_region_emptyData;
 316 }
 317
 318 void
 319 PREFIX(pixman_region_init_rect) (pixman_region16_t *region,
 320                          int x, int y, unsigned int width, unsigned int height)
 321 {
 322     region->extents.x1 = x;
 323     region->extents.y1 = y;
 324     region->extents.x2 = x + width;
 325     region->extents.y2 = y + height;
 326     region->data = NULL;
 327 }
 328
 329 void
 330 PREFIX(pixman_region_init_with_extents) (pixman_region16_t *region, pixman_box16_t *extents)
 331 {
 332     region->extents = *extents;
 333     region->data = NULL;
 334 }
 335
 336 void
 337 PREFIX(pixman_region_fini) (pixman_region16_t *region)
 338 {
 339     good (region);
 340     freeData (region);
 341 }
 342
 343 int
 344 PREFIX(pixman_region_n_rects) (pixman_region16_t *region)
 345 {
 346     return PIXREGION_NUM_RECTS (region);
 347 }
 348
 349 pixman_box16_t *
 350 PREFIX(pixman_region_rects) (pixman_region16_t *region)
 351 {
 352     return PIXREGION_RECTS (region);
 353 }
 354
 355 pixman_box16_t *
 356 PREFIX(pixman_region_rectangles) (pixman_region16_t *region,
 357                                   int               *n_rects)
 358 {
 359     if (n_rects)
 360         *n_rects = PIXREGION_NUM_RECTS (region);
 361
 362     return PIXREGION_RECTS (region);
 363 }
 364
 365 static pixman_bool_t
 366 pixman_break (pixman_region16_t *region)
 367 {
 368     freeData (region);
 369     region->extents = *pixman_region_emptyBox;
 370     region->data = pixman_brokendata;
 371     return FALSE;
 372 }
 373
 374 static pixman_bool_t
 375 pixman_rect_alloc (pixman_region16_t * region, int n)
 376 {
 377     pixman_region16_data_t *data;
 378
 379     if (!region->data)
 380     {
 381         n++;
 382         region->data = allocData(n);
 383         if (!region->data)
 384             return pixman_break (region);
 385         region->data->numRects = 1;
 386         *PIXREGION_BOXPTR(region) = region->extents;
 387     }
 388     else if (!region->data->size)
 389     {
 390         region->data = allocData(n);
 391         if (!region->data)
 392             return pixman_break (region);
 393         region->data->numRects = 0;
 394     }
 395     else
 396     {
 397         size_t data_size;
 398         if (n == 1)
 399         {
 400             n = region->data->numRects;
 401             if (n > 500) /* XXX pick numbers out of a hat */
 402                 n = 250;
 403         }
 404         n += region->data->numRects;
 405         data_size = PIXREGION_SZOF(n);
 406         if (!data_size)
 407             data = NULL;
 408         else
 409             data = (pixman_region16_data_t *)realloc(region->data, PIXREGION_SZOF(n));
 410         if (!data)
 411             return pixman_break (region);
 412         region->data = data;
 413     }
 414     region->data->size = n;
 415     return TRUE;
 416 }
 417
 418 pixman_bool_t
 419 PREFIX(pixman_region_copy) (pixman_region16_t *dst, pixman_region16_t *src)
 420 {
 421     good(dst);
 422     good(src);
 423     if (dst == src)
 424         return TRUE;
 425     dst->extents = src->extents;
 426     if (!src->data || !src->data->size)
 427     {
 428         freeData(dst);
 429         dst->data = src->data;
 430         return TRUE;
 431     }
 432     if (!dst->data || (dst->data->size < src->data->numRects))
 433     {
 434         freeData(dst);
 435         dst->data = allocData(src->data->numRects);
 436         if (!dst->data)
 437             return pixman_break (dst);
 438         dst->data->size = src->data->numRects;
 439     }
 440     dst->data->numRects = src->data->numRects;
 441     memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src),
 442           dst->data->numRects * sizeof(pixman_box16_t));
 443     return TRUE;
 444 }
 445
 446 /*======================================================================
 447  *          Generic Region Operator
 448  *====================================================================*/
 449
 450 /*-
 451  *-----------------------------------------------------------------------
 452  * pixman_coalesce --
 453  *      Attempt to merge the boxes in the current band with those in the
 454  *      previous one.  We are guaranteed that the current band extends to
 455  *      the end of the rects array.  Used only by pixman_op.
 456  *
 457  * Results:
 458  *      The new index for the previous band.
 459  *
 460  * Side Effects:
 461  *      If coalescing takes place:
 462  *          - rectangles in the previous band will have their y2 fields
 463  *            altered.
 464  *          - region->data->numRects will be decreased.
 465  *
 466  *-----------------------------------------------------------------------
 467  */
 468 static inline int
 469 pixman_coalesce (
 470     pixman_region16_t * region,         /* Region to coalesce                */
 471     int                 prevStart,      /* Index of start of previous band   */
 472     int                 curStart)       /* Index of start of current band    */
 473 {
 474     pixman_box16_t *    pPrevBox;       /* Current box in previous band      */
 475     pixman_box16_t *    pCurBox;        /* Current box in current band       */
 476     int         numRects;       /* Number rectangles in both bands   */
 477     int y2;             /* Bottom of current band            */
 478     /*
 479      * Figure out how many rectangles are in the band.
 480      */
 481     numRects = curStart - prevStart;
 482     assert(numRects == region->data->numRects - curStart);
 483
 484     if (!numRects) return curStart;
 485
 486     /*
 487      * The bands may only be coalesced if the bottom of the previous
 488      * matches the top scanline of the current.
 489      */
 490     pPrevBox = PIXREGION_BOX(region, prevStart);
 491     pCurBox = PIXREGION_BOX(region, curStart);
 492     if (pPrevBox->y2 != pCurBox->y1) return curStart;
 493
 494     /*
 495      * Make sure the bands have boxes in the same places. This
 496      * assumes that boxes have been added in such a way that they
 497      * cover the most area possible. I.e. two boxes in a band must
 498      * have some horizontal space between them.
 499      */
 500     y2 = pCurBox->y2;
 501
 502     do {
 503         if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
 504             return (curStart);
 505         }
 506         pPrevBox++;
 507         pCurBox++;
 508         numRects--;
 509     } while (numRects);
 510
 511     /*
 512      * The bands may be merged, so set the bottom y of each box
 513      * in the previous band to the bottom y of the current band.
 514      */
 515     numRects = curStart - prevStart;
 516     region->data->numRects -= numRects;
 517     do {
 518         pPrevBox--;
 519         pPrevBox->y2 = y2;
 520         numRects--;
 521     } while (numRects);
 522     return prevStart;
 523 }
 524
 525 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
 526
 527 #define Coalesce(newReg, prevBand, curBand)                             \
 528     if (curBand - prevBand == newReg->data->numRects - curBand) {       \
 529         prevBand = pixman_coalesce(newReg, prevBand, curBand);          \
 530     } else {                                                            \
 531         prevBand = curBand;                                             \
 532     }
 533
 534 /*-
 535  *-----------------------------------------------------------------------
 536  * pixman_region_appendNonO --
 537  *      Handle a non-overlapping band for the union and subtract operations.
 538  *      Just adds the (top/bottom-clipped) rectangles into the region.
 539  *      Doesn't have to check for subsumption or anything.
 540  *
 541  * Results:
 542  *      None.
 543  *
 544  * Side Effects:
 545  *      region->data->numRects is incremented and the rectangles overwritten
 546  *      with the rectangles we're passed.
 547  *
 548  *-----------------------------------------------------------------------
 549  */
 550
 551 static inline pixman_bool_t
 552 pixman_region_appendNonO (
 553     pixman_region16_t * region,
 554     pixman_box16_t *    r,
 555     pixman_box16_t *            rEnd,
 556     int         y1,
 557     int         y2)
 558 {
 559     pixman_box16_t *    pNextRect;
 560     int newRects;
 561
 562     newRects = rEnd - r;
 563
 564     assert(y1 < y2);
 565     assert(newRects != 0);
 566
 567     /* Make sure we have enough space for all rectangles to be added */
 568     RECTALLOC(region, newRects);
 569     pNextRect = PIXREGION_TOP(region);
 570     region->data->numRects += newRects;
 571     do {
 572         assert(r->x1 < r->x2);
 573         ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
 574         r++;
 575     } while (r != rEnd);
 576
 577     return TRUE;
 578 }
 579
 580 #define FindBand(r, rBandEnd, rEnd, ry1)                    \
 581 {                                                           \
 582     ry1 = r->y1;                                            \
 583     rBandEnd = r+1;                                         \
 584     while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) {   \
 585         rBandEnd++;                                         \
 586     }                                                       \
 587 }
 588
 589 #define AppendRegions(newReg, r, rEnd)                                  \
 590 {                                                                       \
 591     int newRects;                                                       \
 592     if ((newRects = rEnd - r)) {                                        \
 593         RECTALLOC(newReg, newRects);                                    \
 594         memmove((char *)PIXREGION_TOP(newReg),(char *)r,                        \
 595               newRects * sizeof(pixman_box16_t));                               \
 596         newReg->data->numRects += newRects;                             \
 597     }                                                                   \
 598 }
 599
 600 /*-
 601  *-----------------------------------------------------------------------
 602  * pixman_op --
 603  *      Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
 604  *      pixman_region_subtract, pixman_region_intersect....  Both regions MUST have at least one
 605  *      rectangle, and cannot be the same object.
 606  *
 607  * Results:
 608  *      TRUE if successful.
 609  *
 610  * Side Effects:
 611  *      The new region is overwritten.
 612  *      pOverlap set to TRUE if overlapFunc ever returns TRUE.
 613  *
 614  * Notes:
 615  *      The idea behind this function is to view the two regions as sets.
 616  *      Together they cover a rectangle of area that this function divides
 617  *      into horizontal bands where points are covered only by one region
 618  *      or by both. For the first case, the nonOverlapFunc is called with
 619  *      each the band and the band's upper and lower extents. For the
 620  *      second, the overlapFunc is called to process the entire band. It
 621  *      is responsible for clipping the rectangles in the band, though
 622  *      this function provides the boundaries.
 623  *      At the end of each band, the new region is coalesced, if possible,
 624  *      to reduce the number of rectangles in the region.
 625  *
 626  *-----------------------------------------------------------------------
 627  */
 628
 629 typedef pixman_bool_t (*OverlapProcPtr)(
 630     pixman_region16_t    *region,
 631     pixman_box16_t *r1,
 632     pixman_box16_t *r1End,
 633     pixman_box16_t *r2,
 634     pixman_box16_t *r2End,
 635     short        y1,
 636     short        y2,
 637     int          *pOverlap);
 638
 639 static pixman_bool_t
 640 pixman_op(
 641     pixman_region16_t *newReg,              /* Place to store result         */
 642     pixman_region16_t *       reg1,                 /* First region in operation     */
 643     pixman_region16_t *       reg2,                 /* 2d region in operation        */
 644     OverlapProcPtr  overlapFunc,            /* Function to call for over-
 645                                              * lapping bands                 */
 646     int     appendNon1,             /* Append non-overlapping bands  */
 647                                             /* in region 1 ? */
 648     int     appendNon2,             /* Append non-overlapping bands  */
 649                                             /* in region 2 ? */
 650     int     *pOverlap)
 651 {
 652     pixman_box16_t * r1;                            /* Pointer into first region     */
 653     pixman_box16_t * r2;                            /* Pointer into 2d region        */
 654     pixman_box16_t *        r1End;                  /* End of 1st region             */
 655     pixman_box16_t *        r2End;                  /* End of 2d region              */
 656     short           ybot;                   /* Bottom of intersection        */
 657     short           ytop;                   /* Top of intersection           */
 658     pixman_region16_data_t *        oldData;                /* Old data for newReg           */
 659     int             prevBand;               /* Index of start of
 660                                              * previous band in newReg       */
 661     int             curBand;                /* Index of start of current
 662                                              * band in newReg                */
 663     pixman_box16_t * r1BandEnd;             /* End of current band in r1     */
 664     pixman_box16_t * r2BandEnd;             /* End of current band in r2     */
 665     short           top;                    /* Top of non-overlapping band   */
 666     short           bot;                    /* Bottom of non-overlapping band*/
 667     int    r1y1;                    /* Temps for r1->y1 and r2->y1   */
 668     int    r2y1;
 669     int             newSize;
 670     int             numRects;
 671
 672     /*
 673      * Break any region computed from a broken region
 674      */
 675     if (PIXREGION_NAR (reg1) || PIXREGION_NAR(reg2))
 676         return pixman_break (newReg);
 677
 678     /*
 679      * Initialization:
 680      *  set r1, r2, r1End and r2End appropriately, save the rectangles
 681      * of the destination region until the end in case it's one of
 682      * the two source regions, then mark the "new" region empty, allocating
 683      * another array of rectangles for it to use.
 684      */
 685
 686     r1 = PIXREGION_RECTS(reg1);
 687     newSize = PIXREGION_NUM_RECTS(reg1);
 688     r1End = r1 + newSize;
 689     numRects = PIXREGION_NUM_RECTS(reg2);
 690     r2 = PIXREGION_RECTS(reg2);
 691     r2End = r2 + numRects;
 692     assert(r1 != r1End);
 693     assert(r2 != r2End);
 694
 695     oldData = (pixman_region16_data_t *)NULL;
 696     if (((newReg == reg1) && (newSize > 1)) ||
 697         ((newReg == reg2) && (numRects > 1)))
 698     {
 699         oldData = newReg->data;
 700         newReg->data = pixman_region_emptyData;
 701     }
 702     /* guess at new size */
 703     if (numRects > newSize)
 704         newSize = numRects;
 705     newSize <<= 1;
 706     if (!newReg->data)
 707         newReg->data = pixman_region_emptyData;
 708     else if (newReg->data->size)
 709         newReg->data->numRects = 0;
 710     if (newSize > newReg->data->size) {
 711         if (!pixman_rect_alloc(newReg, newSize)) {
 712             if (oldData)
 713                 free (oldData);
 714             return FALSE;
 715         }
 716     }
 717
 718     /*
 719      * Initialize ybot.
 720      * In the upcoming loop, ybot and ytop serve different functions depending
 721      * on whether the band being handled is an overlapping or non-overlapping
 722      * band.
 723      *  In the case of a non-overlapping band (only one of the regions
 724      * has points in the band), ybot is the bottom of the most recent
 725      * intersection and thus clips the top of the rectangles in that band.
 726      * ytop is the top of the next intersection between the two regions and
 727      * serves to clip the bottom of the rectangles in the current band.
 728      *  For an overlapping band (where the two regions intersect), ytop clips
 729      * the top of the rectangles of both regions and ybot clips the bottoms.
 730      */
 731
 732     ybot = MIN(r1->y1, r2->y1);
 733
 734     /*
 735      * prevBand serves to mark the start of the previous band so rectangles
 736      * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
 737      * In the beginning, there is no previous band, so prevBand == curBand
 738      * (curBand is set later on, of course, but the first band will always
 739      * start at index 0). prevBand and curBand must be indices because of
 740      * the possible expansion, and resultant moving, of the new region's
 741      * array of rectangles.
 742      */
 743     prevBand = 0;
 744
 745     do {
 746         /*
 747          * This algorithm proceeds one source-band (as opposed to a
 748          * destination band, which is determined by where the two regions
 749          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
 750          * rectangle after the last one in the current band for their
 751          * respective regions.
 752          */
 753         assert(r1 != r1End);
 754         assert(r2 != r2End);
 755
 756         FindBand(r1, r1BandEnd, r1End, r1y1);
 757         FindBand(r2, r2BandEnd, r2End, r2y1);
 758
 759         /*
 760          * First handle the band that doesn't intersect, if any.
 761          *
 762          * Note that attention is restricted to one band in the
 763          * non-intersecting region at once, so if a region has n
 764          * bands between the current position and the next place it overlaps
 765          * the other, this entire loop will be passed through n times.
 766          */
 767         if (r1y1 < r2y1) {
 768             if (appendNon1) {
 769                 top = MAX(r1y1, ybot);
 770                 bot = MIN(r1->y2, r2y1);
 771                 if (top != bot) {
 772                     curBand = newReg->data->numRects;
 773                     pixman_region_appendNonO(newReg, r1, r1BandEnd, top, bot);
 774                     Coalesce(newReg, prevBand, curBand);
 775                 }
 776             }
 777             ytop = r2y1;
 778         } else if (r2y1 < r1y1) {
 779             if (appendNon2) {
 780                 top = MAX(r2y1, ybot);
 781                 bot = MIN(r2->y2, r1y1);
 782                 if (top != bot) {
 783                     curBand = newReg->data->numRects;
 784                     pixman_region_appendNonO(newReg, r2, r2BandEnd, top, bot);
 785                     Coalesce(newReg, prevBand, curBand);
 786                 }
 787             }
 788             ytop = r1y1;
 789         } else {
 790             ytop = r1y1;
 791         }
 792
 793         /*
 794          * Now see if we've hit an intersecting band. The two bands only
 795          * intersect if ybot > ytop
 796          */
 797         ybot = MIN(r1->y2, r2->y2);
 798         if (ybot > ytop) {
 799             curBand = newReg->data->numRects;
 800             (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
 801                             pOverlap);
 802             Coalesce(newReg, prevBand, curBand);
 803         }
 804
 805         /*
 806          * If we've finished with a band (y2 == ybot) we skip forward
 807          * in the region to the next band.
 808          */
 809         if (r1->y2 == ybot) r1 = r1BandEnd;
 810         if (r2->y2 == ybot) r2 = r2BandEnd;
 811
 812     } while (r1 != r1End && r2 != r2End);
 813
 814     /*
 815      * Deal with whichever region (if any) still has rectangles left.
 816      *
 817      * We only need to worry about banding and coalescing for the very first
 818      * band left.  After that, we can just group all remaining boxes,
 819      * regardless of how many bands, into one final append to the list.
 820      */
 821
 822     if ((r1 != r1End) && appendNon1) {
 823         /* Do first nonOverlap1Func call, which may be able to coalesce */
 824         FindBand(r1, r1BandEnd, r1End, r1y1);
 825         curBand = newReg->data->numRects;
 826         pixman_region_appendNonO(newReg, r1, r1BandEnd, MAX(r1y1, ybot), r1->y2);
 827         Coalesce(newReg, prevBand, curBand);
 828         /* Just append the rest of the boxes  */
 829         AppendRegions(newReg, r1BandEnd, r1End);
 830
 831     } else if ((r2 != r2End) && appendNon2) {
 832         /* Do first nonOverlap2Func call, which may be able to coalesce */
 833         FindBand(r2, r2BandEnd, r2End, r2y1);
 834         curBand = newReg->data->numRects;
 835         pixman_region_appendNonO(newReg, r2, r2BandEnd, MAX(r2y1, ybot), r2->y2);
 836         Coalesce(newReg, prevBand, curBand);
 837         /* Append rest of boxes */
 838         AppendRegions(newReg, r2BandEnd, r2End);
 839     }
 840
 841     if (oldData)
 842         free(oldData);
 843
 844     if (!(numRects = newReg->data->numRects))
 845     {
 846         freeData(newReg);
 847         newReg->data = pixman_region_emptyData;
 848     }
 849     else if (numRects == 1)
 850     {
 851         newReg->extents = *PIXREGION_BOXPTR(newReg);
 852         freeData(newReg);
 853         newReg->data = (pixman_region16_data_t *)NULL;
 854     }
 855     else
 856     {
 857         DOWNSIZE(newReg, numRects);
 858     }
 859
 860     return TRUE;
 861 }
 862
 863 /*-
 864  *-----------------------------------------------------------------------
 865  * pixman_set_extents --
 866  *      Reset the extents of a region to what they should be. Called by
 867  *      pixman_region_subtract and pixman_region_intersect as they can't figure it out along the
 868  *      way or do so easily, as pixman_region_union can.
 869  *
 870  * Results:
 871  *      None.
 872  *
 873  * Side Effects:
 874  *      The region's 'extents' structure is overwritten.
 875  *
 876  *-----------------------------------------------------------------------
 877  */
 878 static void
 879 pixman_set_extents (pixman_region16_t *region)
 880 {
 881     pixman_box16_t *box, *boxEnd;
 882
 883     if (!region->data)
 884         return;
 885     if (!region->data->size)
 886     {
 887         region->extents.x2 = region->extents.x1;
 888         region->extents.y2 = region->extents.y1;
 889         return;
 890     }
 891
 892     box = PIXREGION_BOXPTR(region);
 893     boxEnd = PIXREGION_END(region);
 894
 895     /*
 896      * Since box is the first rectangle in the region, it must have the
 897      * smallest y1 and since boxEnd is the last rectangle in the region,
 898      * it must have the largest y2, because of banding. Initialize x1 and
 899      * x2 from  box and boxEnd, resp., as good things to initialize them
 900      * to...
 901      */
 902     region->extents.x1 = box->x1;
 903     region->extents.y1 = box->y1;
 904     region->extents.x2 = boxEnd->x2;
 905     region->extents.y2 = boxEnd->y2;
 906
 907     assert(region->extents.y1 < region->extents.y2);
 908     while (box <= boxEnd) {
 909         if (box->x1 < region->extents.x1)
 910             region->extents.x1 = box->x1;
 911         if (box->x2 > region->extents.x2)
 912             region->extents.x2 = box->x2;
 913         box++;
 914     };
 915
 916     assert(region->extents.x1 < region->extents.x2);
 917 }
 918
 919 /*======================================================================
 920  *          Region Intersection
 921  *====================================================================*/
 922 /*-
 923  *-----------------------------------------------------------------------
 924  * pixman_region_intersectO --
 925  *      Handle an overlapping band for pixman_region_intersect.
 926  *
 927  * Results:
 928  *      TRUE if successful.
 929  *
 930  * Side Effects:
 931  *      Rectangles may be added to the region.
 932  *
 933  *-----------------------------------------------------------------------
 934  */
 935 /*ARGSUSED*/
 936 static pixman_bool_t
 937 pixman_region_intersectO (pixman_region16_t *region,
 938                           pixman_box16_t    *r1,
 939                           pixman_box16_t    *r1End,
 940                           pixman_box16_t    *r2,
 941                           pixman_box16_t    *r2End,
 942                           short              y1,
 943                           short              y2,
 944                           int               *pOverlap)
 945 {
 946     int         x1;
 947     int         x2;
 948     pixman_box16_t *    pNextRect;
 949
 950     pNextRect = PIXREGION_TOP(region);
 951
 952     assert(y1 < y2);
 953     assert(r1 != r1End && r2 != r2End);
 954
 955     do {
 956         x1 = MAX(r1->x1, r2->x1);
 957         x2 = MIN(r1->x2, r2->x2);
 958
 959         /*
 960          * If there's any overlap between the two rectangles, add that
 961          * overlap to the new region.
 962          */
 963         if (x1 < x2)
 964             NEWRECT(region, pNextRect, x1, y1, x2, y2);
 965
 966         /*
 967          * Advance the pointer(s) with the leftmost right side, since the next
 968          * rectangle on that list may still overlap the other region's
 969          * current rectangle.
 970          */
 971         if (r1->x2 == x2) {
 972             r1++;
 973         }
 974         if (r2->x2 == x2) {
 975             r2++;
 976         }
 977     } while ((r1 != r1End) && (r2 != r2End));
 978
 979     return TRUE;
 980 }
 981
 982 pixman_bool_t
 983 PREFIX(pixman_region_intersect) (pixman_region16_t *    newReg,
 984                          pixman_region16_t *    reg1,
 985                          pixman_region16_t *    reg2)
 986 {
 987     good(reg1);
 988     good(reg2);
 989     good(newReg);
 990    /* check for trivial reject */
 991     if (PIXREGION_NIL(reg1)  || PIXREGION_NIL(reg2) ||
 992         !EXTENTCHECK(&reg1->extents, &reg2->extents))
 993     {
 994         /* Covers about 20% of all cases */
 995         freeData(newReg);
 996         newReg->extents.x2 = newReg->extents.x1;
 997         newReg->extents.y2 = newReg->extents.y1;
 998         if (PIXREGION_NAR(reg1) || PIXREGION_NAR(reg2))
 999         {
1000             newReg->data = pixman_brokendata;
1001             return FALSE;
1002         }
1003         else
1004             newReg->data = pixman_region_emptyData;
1005     }
1006     else if (!reg1->data && !reg2->data)
1007     {
1008         /* Covers about 80% of cases that aren't trivially rejected */
1009         newReg->extents.x1 = MAX(reg1->extents.x1, reg2->extents.x1);
1010         newReg->extents.y1 = MAX(reg1->extents.y1, reg2->extents.y1);
1011         newReg->extents.x2 = MIN(reg1->extents.x2, reg2->extents.x2);
1012         newReg->extents.y2 = MIN(reg1->extents.y2, reg2->extents.y2);
1013         freeData(newReg);
1014         newReg->data = (pixman_region16_data_t *)NULL;
1015     }
1016     else if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
1017     {
1018         return PREFIX(pixman_region_copy) (newReg, reg1);
1019     }
1020     else if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
1021     {
1022         return PREFIX(pixman_region_copy) (newReg, reg2);
1023     }
1024     else if (reg1 == reg2)
1025     {
1026         return PREFIX(pixman_region_copy) (newReg, reg1);
1027     }
1028     else
1029     {
1030         /* General purpose intersection */
1031         int overlap; /* result ignored */
1032         if (!pixman_op(newReg, reg1, reg2, pixman_region_intersectO, FALSE, FALSE,
1033                         &overlap))
1034             return FALSE;
1035         pixman_set_extents(newReg);
1036     }
1037
1038     good(newReg);
1039     return(TRUE);
1040 }
1041
1042 #define MERGERECT(r)                                            \
1043 {                                                               \
1044     if (r->x1 <= x2) {                                          \
1045         /* Merge with current rectangle */                      \
1046         if (r->x1 < x2) *pOverlap = TRUE;                               \
1047         if (x2 < r->x2) x2 = r->x2;                             \
1048     } else {                                                    \
1049         /* Add current rectangle, start new one */              \
1050         NEWRECT(region, pNextRect, x1, y1, x2, y2);             \
1051         x1 = r->x1;                                             \
1052         x2 = r->x2;                                             \
1053     }                                                           \
1054     r++;                                                        \
1055 }
1056
1057 /*======================================================================
1058  *          Region Union
1059  *====================================================================*/
1060
1061 /*-
1062  *-----------------------------------------------------------------------
1063  * pixman_region_unionO --
1064  *      Handle an overlapping band for the union operation. Picks the
1065  *      left-most rectangle each time and merges it into the region.
1066  *
1067  * Results:
1068  *      TRUE if successful.
1069  *
1070  * Side Effects:
1071  *      region is overwritten.
1072  *      pOverlap is set to TRUE if any boxes overlap.
1073  *
1074  *-----------------------------------------------------------------------
1075  */
1076 static pixman_bool_t
1077 pixman_region_unionO (
1078     pixman_region16_t    *region,
1079     pixman_box16_t *r1,
1080     pixman_box16_t *r1End,
1081     pixman_box16_t *r2,
1082     pixman_box16_t *r2End,
1083     short         y1,
1084     short         y2,
1085     int           *pOverlap)
1086 {
1087     pixman_box16_t *     pNextRect;
1088     int        x1;     /* left and right side of current union */
1089     int        x2;
1090
1091     assert (y1 < y2);
1092     assert(r1 != r1End && r2 != r2End);
1093
1094     pNextRect = PIXREGION_TOP(region);
1095
1096     /* Start off current rectangle */
1097     if (r1->x1 < r2->x1)
1098     {
1099         x1 = r1->x1;
1100         x2 = r1->x2;
1101         r1++;
1102     }
1103     else
1104     {
1105         x1 = r2->x1;
1106         x2 = r2->x2;
1107         r2++;
1108     }
1109     while (r1 != r1End && r2 != r2End)
1110     {
1111         if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
1112     }
1113
1114     /* Finish off whoever (if any) is left */
1115     if (r1 != r1End)
1116     {
1117         do
1118         {
1119             MERGERECT(r1);
1120         } while (r1 != r1End);
1121     }
1122     else if (r2 != r2End)
1123     {
1124         do
1125         {
1126             MERGERECT(r2);
1127         } while (r2 != r2End);
1128     }
1129
1130     /* Add current rectangle */
1131     NEWRECT(region, pNextRect, x1, y1, x2, y2);
1132
1133     return TRUE;
1134 }
1135
1136 /* Convenience function for performing union of region with a
1137  * single rectangle
1138  */
1139 pixman_bool_t
1140 PREFIX(pixman_region_union_rect) (pixman_region16_t *dest,
1141                           pixman_region16_t *source,
1142                           int x, int y,
1143                           unsigned int width, unsigned int height)
1144 {
1145     pixman_region16_t region;
1146
1147     if (!width || !height)
1148         return PREFIX(pixman_region_copy) (dest, source);
1149     region.data = NULL;
1150     region.extents.x1 = x;
1151     region.extents.y1 = y;
1152     region.extents.x2 = x + width;
1153     region.extents.y2 = y + height;
1154
1155     return PREFIX(pixman_region_union) (dest, source, &region);
1156 }
1157
1158 pixman_bool_t
1159 PREFIX(pixman_region_union) (pixman_region16_t *newReg,
1160                      pixman_region16_t *reg1,
1161                      pixman_region16_t *reg2)
1162 {
1163     int overlap; /* result ignored */
1164
1165     /* Return TRUE if some overlap
1166      * between reg1, reg2
1167      */
1168     good(reg1);
1169     good(reg2);
1170     good(newReg);
1171     /*  checks all the simple cases */
1172
1173     /*
1174      * Region 1 and 2 are the same
1175      */
1176     if (reg1 == reg2)
1177     {
1178         return PREFIX(pixman_region_copy) (newReg, reg1);
1179     }
1180
1181     /*
1182      * Region 1 is empty
1183      */
1184     if (PIXREGION_NIL(reg1))
1185     {
1186         if (PIXREGION_NAR(reg1))
1187             return pixman_break (newReg);
1188         if (newReg != reg2)
1189             return PREFIX(pixman_region_copy) (newReg, reg2);
1190         return TRUE;
1191     }
1192
1193     /*
1194      * Region 2 is empty
1195      */
1196     if (PIXREGION_NIL(reg2))
1197     {
1198         if (PIXREGION_NAR(reg2))
1199             return pixman_break (newReg);
1200         if (newReg != reg1)
1201             return PREFIX(pixman_region_copy) (newReg, reg1);
1202         return TRUE;
1203     }
1204
1205     /*
1206      * Region 1 completely subsumes region 2
1207      */
1208     if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
1209     {
1210         if (newReg != reg1)
1211             return PREFIX(pixman_region_copy) (newReg, reg1);
1212         return TRUE;
1213     }
1214
1215     /*
1216      * Region 2 completely subsumes region 1
1217      */
1218     if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
1219     {
1220         if (newReg != reg2)
1221             return PREFIX(pixman_region_copy) (newReg, reg2);
1222         return TRUE;
1223     }
1224
1225     if (!pixman_op(newReg, reg1, reg2, pixman_region_unionO, TRUE, TRUE, &overlap))
1226         return FALSE;
1227
1228     newReg->extents.x1 = MIN(reg1->extents.x1, reg2->extents.x1);
1229     newReg->extents.y1 = MIN(reg1->extents.y1, reg2->extents.y1);
1230     newReg->extents.x2 = MAX(reg1->extents.x2, reg2->extents.x2);
1231     newReg->extents.y2 = MAX(reg1->extents.y2, reg2->extents.y2);
1232     good(newReg);
1233     return TRUE;
1234 }
1235
1236 /*======================================================================
1237  *          Batch Rectangle Union
1238  *====================================================================*/
1239
1240 /*-
1241  *-----------------------------------------------------------------------
1242  * pixman_region_append --
1243  *
1244  *      "Append" the rgn rectangles onto the end of dstrgn, maintaining
1245  *      knowledge of YX-banding when it's easy.  Otherwise, dstrgn just
1246  *      becomes a non-y-x-banded random collection of rectangles, and not
1247  *      yet a true region.  After a sequence of appends, the caller must
1248  *      call pixman_region_validate to ensure that a valid region is
1249  *      constructed.
1250  *
1251  * Results:
1252  *      TRUE if successful.
1253  *
1254  * Side Effects:
1255  *      dstrgn is modified if rgn has rectangles.
1256  *
1257  */
1258 pixman_bool_t
1259 PREFIX(pixman_region_append) (pixman_region16_t * dstrgn,
1260                       pixman_region16_t * rgn)
1261 {
1262     int numRects, dnumRects, size;
1263     pixman_box16_t *new, *old;
1264     int prepend;
1265
1266     if (PIXREGION_NAR(rgn))
1267         return pixman_break (dstrgn);
1268
1269     if (!rgn->data && (dstrgn->data == pixman_region_emptyData))
1270     {
1271         dstrgn->extents = rgn->extents;
1272         dstrgn->data = (pixman_region16_data_t *)NULL;
1273         return TRUE;
1274     }
1275
1276     numRects = PIXREGION_NUM_RECTS(rgn);
1277     if (!numRects)
1278         return TRUE;
1279     prepend = FALSE;
1280     size = numRects;
1281     dnumRects = PIXREGION_NUM_RECTS(dstrgn);
1282     if (!dnumRects && (size < 200))
1283         size = 200; /* XXX pick numbers out of a hat */
1284     RECTALLOC(dstrgn, size);
1285     old = PIXREGION_RECTS(rgn);
1286     if (!dnumRects)
1287         dstrgn->extents = rgn->extents;
1288     else if (dstrgn->extents.x2 > dstrgn->extents.x1)
1289     {
1290         pixman_box16_t *first, *last;
1291
1292         first = old;
1293         last = PIXREGION_BOXPTR(dstrgn) + (dnumRects - 1);
1294         if ((first->y1 > last->y2) ||
1295             ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1296              (first->x1 > last->x2)))
1297         {
1298             if (rgn->extents.x1 < dstrgn->extents.x1)
1299                 dstrgn->extents.x1 = rgn->extents.x1;
1300             if (rgn->extents.x2 > dstrgn->extents.x2)
1301                 dstrgn->extents.x2 = rgn->extents.x2;
1302             dstrgn->extents.y2 = rgn->extents.y2;
1303         }
1304         else
1305         {
1306             first = PIXREGION_BOXPTR(dstrgn);
1307             last = old + (numRects - 1);
1308             if ((first->y1 > last->y2) ||
1309                 ((first->y1 == last->y1) && (first->y2 == last->y2) &&
1310                  (first->x1 > last->x2)))
1311             {
1312                 prepend = TRUE;
1313                 if (rgn->extents.x1 < dstrgn->extents.x1)
1314                     dstrgn->extents.x1 = rgn->extents.x1;
1315                 if (rgn->extents.x2 > dstrgn->extents.x2)
1316                     dstrgn->extents.x2 = rgn->extents.x2;
1317                 dstrgn->extents.y1 = rgn->extents.y1;
1318             }
1319             else
1320                 dstrgn->extents.x2 = dstrgn->extents.x1;
1321         }
1322     }
1323     if (prepend)
1324     {
1325         new = PIXREGION_BOX(dstrgn, numRects);
1326         if (dnumRects == 1)
1327             *new = *PIXREGION_BOXPTR(dstrgn);
1328         else
1329             memmove((char *)new,(char *)PIXREGION_BOXPTR(dstrgn),
1330                   dnumRects * sizeof(pixman_box16_t));
1331         new = PIXREGION_BOXPTR(dstrgn);
1332     }
1333     else
1334         new = PIXREGION_BOXPTR(dstrgn) + dnumRects;
1335     if (numRects == 1)
1336         *new = *old;
1337     else
1338         memmove((char *)new, (char *)old, numRects * sizeof(pixman_box16_t));
1339     dstrgn->data->numRects += numRects;
1340     return TRUE;
1341 }
1342
1343 #define ExchangeRects(a, b) \
1344 {                           \
1345     pixman_box16_t     t;           \
1346     t = rects[a];           \
1347     rects[a] = rects[b];    \
1348     rects[b] = t;           \
1349 }
1350
1351 static void
1352 QuickSortRects(
1353     pixman_box16_t     rects[],
1354     int        numRects)
1355 {
1356     int y1;
1357     int x1;
1358     int        i, j;
1359     pixman_box16_t *r;
1360
1361     /* Always called with numRects > 1 */
1362
1363     do
1364     {
1365         if (numRects == 2)
1366         {
1367             if (rects[0].y1 > rects[1].y1 ||
1368                     (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1369                 ExchangeRects(0, 1);
1370             return;
1371         }
1372
1373         /* Choose partition element, stick in location 0 */
1374         ExchangeRects(0, numRects >> 1);
1375         y1 = rects[0].y1;
1376         x1 = rects[0].x1;
1377
1378         /* Partition array */
1379         i = 0;
1380         j = numRects;
1381         do
1382         {
1383             r = &(rects[i]);
1384             do
1385             {
1386                 r++;
1387                 i++;
1388             } while (i != numRects &&
1389                      (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1390             r = &(rects[j]);
1391             do
1392             {
1393                 r--;
1394                 j--;
1395             } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1396             if (i < j)
1397                 ExchangeRects(i, j);
1398         } while (i < j);
1399
1400         /* Move partition element back to middle */
1401         ExchangeRects(0, j);
1402
1403         /* Recurse */
1404         if (numRects-j-1 > 1)
1405             QuickSortRects(&rects[j+1], numRects-j-1);
1406         numRects = j;
1407     } while (numRects > 1);
1408 }
1409
1410 /*-
1411  *-----------------------------------------------------------------------
1412  * pixman_region_validate --
1413  *
1414  *      Take a ``region'' which is a non-y-x-banded random collection of
1415  *      rectangles, and compute a nice region which is the union of all the
1416  *      rectangles.
1417  *
1418  * Results:
1419  *      TRUE if successful.
1420  *
1421  * Side Effects:
1422  *      The passed-in ``region'' may be modified.
1423  *      pOverlap set to TRUE if any retangles overlapped,
1424  *      else FALSE;
1425  *
1426  * Strategy:
1427  *      Step 1. Sort the rectangles into ascending order with primary key y1
1428  *              and secondary key x1.
1429  *
1430  *      Step 2. Split the rectangles into the minimum number of proper y-x
1431  *              banded regions.  This may require horizontally merging
1432  *              rectangles, and vertically coalescing bands.  With any luck,
1433  *              this step in an identity transformation (ala the Box widget),
1434  *              or a coalescing into 1 box (ala Menus).
1435  *
1436  *      Step 3. Merge the separate regions down to a single region by calling
1437  *              pixman_region_union.  Maximize the work each pixman_region_union call does by using
1438  *              a binary merge.
1439  *
1440  *-----------------------------------------------------------------------
1441  */
1442
1443 pixman_bool_t
1444 PREFIX(pixman_region_validate) (pixman_region16_t * badreg,
1445                        int *pOverlap)
1446 {
1447     /* Descriptor for regions under construction  in Step 2. */
1448     typedef struct {
1449         pixman_region16_t   reg;
1450         int         prevBand;
1451         int         curBand;
1452     } RegionInfo;
1453
1454              int        numRects;   /* Original numRects for badreg         */
1455              RegionInfo *ri;        /* Array of current regions             */
1456              int        numRI;      /* Number of entries used in ri         */
1457              int        sizeRI;     /* Number of entries available in ri    */
1458              int        i;          /* Index into rects                     */
1459     int j;          /* Index into ri                        */
1460     RegionInfo *rit;       /* &ri[j]                                */
1461     pixman_region16_t *  reg;        /* ri[j].reg                           */
1462     pixman_box16_t *    box;        /* Current box in rects                 */
1463     pixman_box16_t *    riBox;      /* Last box in ri[j].reg                */
1464     pixman_region16_t *  hreg;       /* ri[j_half].reg                      */
1465     pixman_bool_t ret = TRUE;
1466
1467     *pOverlap = FALSE;
1468     if (!badreg->data)
1469     {
1470         good(badreg);
1471         return TRUE;
1472     }
1473     numRects = badreg->data->numRects;
1474     if (!numRects)
1475     {
1476         if (PIXREGION_NAR(badreg))
1477             return FALSE;
1478         good(badreg);
1479         return TRUE;
1480     }
1481     if (badreg->extents.x1 < badreg->extents.x2)
1482     {
1483         if ((numRects) == 1)
1484         {
1485             freeData(badreg);
1486             badreg->data = (pixman_region16_data_t *) NULL;
1487         }
1488         else
1489         {
1490             DOWNSIZE(badreg, numRects);
1491         }
1492         good(badreg);
1493         return TRUE;
1494     }
1495
1496     /* Step 1: Sort the rects array into ascending (y1, x1) order */
1497     QuickSortRects(PIXREGION_BOXPTR(badreg), numRects);
1498
1499     /* Step 2: Scatter the sorted array into the minimum number of regions */
1500
1501     /* Set up the first region to be the first rectangle in badreg */
1502     /* Note that step 2 code will never overflow the ri[0].reg rects array */
1503     ri = (RegionInfo *) pixman_malloc_ab (4, sizeof(RegionInfo));
1504     if (!ri)
1505         return pixman_break (badreg);
1506     sizeRI = 4;
1507     numRI = 1;
1508     ri[0].prevBand = 0;
1509     ri[0].curBand = 0;
1510     ri[0].reg = *badreg;
1511     box = PIXREGION_BOXPTR(&ri[0].reg);
1512     ri[0].reg.extents = *box;
1513     ri[0].reg.data->numRects = 1;
1514     badreg->extents = *pixman_region_emptyBox;
1515     badreg->data = pixman_region_emptyData;
1516
1517     /* Now scatter rectangles into the minimum set of valid regions.  If the
1518        next rectangle to be added to a region would force an existing rectangle
1519        in the region to be split up in order to maintain y-x banding, just
1520        forget it.  Try the next region.  If it doesn't fit cleanly into any
1521        region, make a new one. */
1522
1523     for (i = numRects; --i > 0;)
1524     {
1525         box++;
1526         /* Look for a region to append box to */
1527         for (j = numRI, rit = ri; --j >= 0; rit++)
1528         {
1529             reg = &rit->reg;
1530             riBox = PIXREGION_END(reg);
1531
1532             if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
1533             {
1534                 /* box is in same band as riBox.  Merge or append it */
1535                 if (box->x1 <= riBox->x2)
1536                 {
1537                     /* Merge it with riBox */
1538                     if (box->x1 < riBox->x2) *pOverlap = TRUE;
1539                     if (box->x2 > riBox->x2) riBox->x2 = box->x2;
1540                 }
1541                 else
1542                 {
1543                     RECTALLOC_BAIL(reg, 1, bail);
1544                     *PIXREGION_TOP(reg) = *box;
1545                     reg->data->numRects++;
1546                 }
1547                 goto NextRect;   /* So sue me */
1548             }
1549             else if (box->y1 >= riBox->y2)
1550             {
1551                 /* Put box into new band */
1552                 if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1553                 if (reg->extents.x1 > box->x1)   reg->extents.x1 = box->x1;
1554                 Coalesce(reg, rit->prevBand, rit->curBand);
1555                 rit->curBand = reg->data->numRects;
1556                 RECTALLOC_BAIL(reg, 1, bail);
1557                 *PIXREGION_TOP(reg) = *box;
1558                 reg->data->numRects++;
1559                 goto NextRect;
1560             }
1561             /* Well, this region was inappropriate.  Try the next one. */
1562         } /* for j */
1563
1564         /* Uh-oh.  No regions were appropriate.  Create a new one. */
1565         if (sizeRI == numRI)
1566         {
1567             size_t data_size;
1568
1569             /* Oops, allocate space for new region information */
1570             sizeRI <<= 1;
1571
1572             data_size = sizeRI * sizeof(RegionInfo);
1573             if (data_size / sizeRI != sizeof(RegionInfo))
1574                 goto bail;
1575             rit = (RegionInfo *) realloc(ri, data_size);
1576             if (!rit)
1577                 goto bail;
1578             ri = rit;
1579             rit = &ri[numRI];
1580         }
1581         numRI++;
1582         rit->prevBand = 0;
1583         rit->curBand = 0;
1584         rit->reg.extents = *box;
1585         rit->reg.data = (pixman_region16_data_t *)NULL;
1586         if (!pixman_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */
1587             goto bail;
1588 NextRect: ;
1589     } /* for i */
1590
1591     /* Make a final pass over each region in order to Coalesce and set
1592        extents.x2 and extents.y2 */
1593
1594     for (j = numRI, rit = ri; --j >= 0; rit++)
1595     {
1596         reg = &rit->reg;
1597         riBox = PIXREGION_END(reg);
1598         reg->extents.y2 = riBox->y2;
1599         if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
1600         Coalesce(reg, rit->prevBand, rit->curBand);
1601         if (reg->data->numRects == 1) /* keep unions happy below */
1602         {
1603             freeData(reg);
1604             reg->data = (pixman_region16_data_t *)NULL;
1605         }
1606     }
1607
1608     /* Step 3: Union all regions into a single region */
1609     while (numRI > 1)
1610     {
1611         int half = numRI/2;
1612         for (j = numRI & 1; j < (half + (numRI & 1)); j++)
1613         {
1614             reg = &ri[j].reg;
1615             hreg = &ri[j+half].reg;
1616             if (!pixman_op(reg, reg, hreg, pixman_region_unionO, TRUE, TRUE, pOverlap))
1617                 ret = FALSE;
1618             if (hreg->extents.x1 < reg->extents.x1)
1619                 reg->extents.x1 = hreg->extents.x1;
1620             if (hreg->extents.y1 < reg->extents.y1)
1621                 reg->extents.y1 = hreg->extents.y1;
1622             if (hreg->extents.x2 > reg->extents.x2)
1623                 reg->extents.x2 = hreg->extents.x2;
1624             if (hreg->extents.y2 > reg->extents.y2)
1625                 reg->extents.y2 = hreg->extents.y2;
1626             freeData(hreg);
1627         }
1628         numRI -= half;
1629         if (!ret)
1630             goto bail;
1631     }
1632     *badreg = ri[0].reg;
1633     free(ri);
1634     good(badreg);
1635     return ret;
1636 bail:
1637     for (i = 0; i < numRI; i++)
1638         freeData(&ri[i].reg);
1639     free (ri);
1640
1641     return pixman_break (badreg);
1642 }
1643
1644 /*======================================================================
1645  *                Region Subtraction
1646  *====================================================================*/
1647
1648 /*-
1649  *-----------------------------------------------------------------------
1650  * pixman_region_subtractO --
1651  *      Overlapping band subtraction. x1 is the left-most point not yet
1652  *      checked.
1653  *
1654  * Results:
1655  *      TRUE if successful.
1656  *
1657  * Side Effects:
1658  *      region may have rectangles added to it.
1659  *
1660  *-----------------------------------------------------------------------
1661  */
1662 /*ARGSUSED*/
1663 static pixman_bool_t
1664 pixman_region_subtractO (
1665     pixman_region16_t * region,
1666     pixman_box16_t *    r1,
1667     pixman_box16_t *            r1End,
1668     pixman_box16_t *    r2,
1669     pixman_box16_t *            r2End,
1670     short       y1,
1671              short      y2,
1672     int         *pOverlap)
1673 {
1674     pixman_box16_t *    pNextRect;
1675     int         x1;
1676
1677     x1 = r1->x1;
1678
1679     assert(y1<y2);
1680     assert(r1 != r1End && r2 != r2End);
1681
1682     pNextRect = PIXREGION_TOP(region);
1683
1684     do
1685     {
1686         if (r2->x2 <= x1)
1687         {
1688             /*
1689              * Subtrahend entirely to left of minuend: go to next subtrahend.
1690              */
1691             r2++;
1692         }
1693         else if (r2->x1 <= x1)
1694         {
1695             /*
1696              * Subtrahend preceeds minuend: nuke left edge of minuend.
1697              */
1698             x1 = r2->x2;
1699             if (x1 >= r1->x2)
1700             {
1701                 /*
1702                  * Minuend completely covered: advance to next minuend and
1703                  * reset left fence to edge of new minuend.
1704                  */
1705                 r1++;
1706                 if (r1 != r1End)
1707                     x1 = r1->x1;
1708             }
1709             else
1710             {
1711                 /*
1712                  * Subtrahend now used up since it doesn't extend beyond
1713                  * minuend
1714                  */
1715                 r2++;
1716             }
1717         }
1718         else if (r2->x1 < r1->x2)
1719         {
1720             /*
1721              * Left part of subtrahend covers part of minuend: add uncovered
1722              * part of minuend to region and skip to next subtrahend.
1723              */
1724             assert(x1<r2->x1);
1725             NEWRECT(region, pNextRect, x1, y1, r2->x1, y2);
1726
1727             x1 = r2->x2;
1728             if (x1 >= r1->x2)
1729             {
1730                 /*
1731                  * Minuend used up: advance to new...
1732                  */
1733                 r1++;
1734                 if (r1 != r1End)
1735                     x1 = r1->x1;
1736             }
1737             else
1738             {
1739                 /*
1740                  * Subtrahend used up
1741                  */
1742                 r2++;
1743             }
1744         }
1745         else
1746         {
1747             /*
1748              * Minuend used up: add any remaining piece before advancing.
1749              */
1750             if (r1->x2 > x1)
1751                 NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1752             r1++;
1753             if (r1 != r1End)
1754                 x1 = r1->x1;
1755         }
1756     } while ((r1 != r1End) && (r2 != r2End));
1757
1758     /*
1759      * Add remaining minuend rectangles to region.
1760      */
1761     while (r1 != r1End)
1762     {
1763         assert(x1<r1->x2);
1764         NEWRECT(region, pNextRect, x1, y1, r1->x2, y2);
1765         r1++;
1766         if (r1 != r1End)
1767             x1 = r1->x1;
1768     }
1769     return TRUE;
1770 }
1771
1772 /*-
1773  *-----------------------------------------------------------------------
1774  * pixman_region_subtract --
1775  *      Subtract regS from regM and leave the result in regD.
1776  *      S stands for subtrahend, M for minuend and D for difference.
1777  *
1778  * Results:
1779  *      TRUE if successful.
1780  *
1781  * Side Effects:
1782  *      regD is overwritten.
1783  *
1784  *-----------------------------------------------------------------------
1785  */
1786 pixman_bool_t
1787 PREFIX(pixman_region_subtract) (pixman_region16_t *     regD,
1788                        pixman_region16_t *      regM,
1789                        pixman_region16_t *      regS)
1790 {
1791     int overlap; /* result ignored */
1792
1793     good(regM);
1794     good(regS);
1795     good(regD);
1796    /* check for trivial rejects */
1797     if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) ||
1798         !EXTENTCHECK(&regM->extents, &regS->extents))
1799     {
1800         if (PIXREGION_NAR (regS))
1801             return pixman_break (regD);
1802         return PREFIX(pixman_region_copy) (regD, regM);
1803     }
1804     else if (regM == regS)
1805     {
1806         freeData(regD);
1807         regD->extents.x2 = regD->extents.x1;
1808         regD->extents.y2 = regD->extents.y1;
1809         regD->data = pixman_region_emptyData;
1810         return TRUE;
1811     }
1812
1813     /* Add those rectangles in region 1 that aren't in region 2,
1814        do yucky substraction for overlaps, and
1815        just throw away rectangles in region 2 that aren't in region 1 */
1816     if (!pixman_op(regD, regM, regS, pixman_region_subtractO, TRUE, FALSE, &overlap))
1817         return FALSE;
1818
1819     /*
1820      * Can't alter RegD's extents before we call pixman_op because
1821      * it might be one of the source regions and pixman_op depends
1822      * on the extents of those regions being unaltered. Besides, this
1823      * way there's no checking against rectangles that will be nuked
1824      * due to coalescing, so we have to examine fewer rectangles.
1825      */
1826     pixman_set_extents(regD);
1827     good(regD);
1828     return TRUE;
1829 }
1830
1831 /*======================================================================
1832  *          Region Inversion
1833  *====================================================================*/
1834
1835 /*-
1836  *-----------------------------------------------------------------------
1837  * pixman_region_inverse --
1838  *      Take a region and a box and return a region that is everything
1839  *      in the box but not in the region. The careful reader will note
1840  *      that this is the same as subtracting the region from the box...
1841  *
1842  * Results:
1843  *      TRUE.
1844  *
1845  * Side Effects:
1846  *      newReg is overwritten.
1847  *
1848  *-----------------------------------------------------------------------
1849  */
1850 pixman_bool_t
1851 PREFIX(pixman_region_inverse) (pixman_region16_t *        newReg,       /* Destination region */
1852                       pixman_region16_t *         reg1,         /* Region to invert */
1853                       pixman_box16_t *            invRect)      /* Bounding box for inversion */
1854 {
1855     pixman_region16_t     invReg;       /* Quick and dirty region made from the
1856                                  * bounding box */
1857     int   overlap;      /* result ignored */
1858
1859     good(reg1);
1860     good(newReg);
1861    /* check for trivial rejects */
1862     if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, &reg1->extents))
1863     {
1864         if (PIXREGION_NAR(reg1))
1865             return pixman_break (newReg);
1866         newReg->extents = *invRect;
1867         freeData(newReg);
1868         newReg->data = (pixman_region16_data_t *)NULL;
1869         return TRUE;
1870     }
1871
1872     /* Add those rectangles in region 1 that aren't in region 2,
1873        do yucky substraction for overlaps, and
1874        just throw away rectangles in region 2 that aren't in region 1 */
1875     invReg.extents = *invRect;
1876     invReg.data = (pixman_region16_data_t *)NULL;
1877     if (!pixman_op(newReg, &invReg, reg1, pixman_region_subtractO, TRUE, FALSE, &overlap))
1878         return FALSE;
1879
1880     /*
1881      * Can't alter newReg's extents before we call pixman_op because
1882      * it might be one of the source regions and pixman_op depends
1883      * on the extents of those regions being unaltered. Besides, this
1884      * way there's no checking against rectangles that will be nuked
1885      * due to coalescing, so we have to examine fewer rectangles.
1886      */
1887     pixman_set_extents(newReg);
1888     good(newReg);
1889     return TRUE;
1890 }
1891
1892 /*
1893  *   RectIn(region, rect)
1894  *   This routine takes a pointer to a region and a pointer to a box
1895  *   and determines if the box is outside/inside/partly inside the region.
1896  *
1897  *   The idea is to travel through the list of rectangles trying to cover the
1898  *   passed box with them. Anytime a piece of the rectangle isn't covered
1899  *   by a band of rectangles, partOut is set TRUE. Any time a rectangle in
1900  *   the region covers part of the box, partIn is set TRUE. The process ends
1901  *   when either the box has been completely covered (we reached a band that
1902  *   doesn't overlap the box, partIn is TRUE and partOut is false), the
1903  *   box has been partially covered (partIn == partOut == TRUE -- because of
1904  *   the banding, the first time this is true we know the box is only
1905  *   partially in the region) or is outside the region (we reached a band
1906  *   that doesn't overlap the box at all and partIn is false)
1907  */
1908
1909 pixman_region_overlap_t
1910 PREFIX(pixman_region_contains_rectangle) (pixman_region16_t *  region,
1911                                  pixman_box16_t *     prect)
1912 {
1913     int x;
1914     int y;
1915     pixman_box16_t *     pbox;
1916     pixman_box16_t *     pboxEnd;
1917     int                 partIn, partOut;
1918     int                 numRects;
1919
1920     good(region);
1921     numRects = PIXREGION_NUM_RECTS(region);
1922     /* useful optimization */
1923     if (!numRects || !EXTENTCHECK(&region->extents, prect))
1924         return(PIXMAN_REGION_OUT);
1925
1926     if (numRects == 1)
1927     {
1928         /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
1929         if (SUBSUMES(&region->extents, prect))
1930             return(PIXMAN_REGION_IN);
1931         else
1932             return(PIXMAN_REGION_PART);
1933     }
1934
1935     partOut = FALSE;
1936     partIn = FALSE;
1937
1938     /* (x,y) starts at upper left of rect, moving to the right and down */
1939     x = prect->x1;
1940     y = prect->y1;
1941
1942     /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1943     for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
1944          pbox != pboxEnd;
1945          pbox++)
1946     {
1947
1948         if (pbox->y2 <= y)
1949            continue;    /* getting up to speed or skipping remainder of band */
1950
1951         if (pbox->y1 > y)
1952         {
1953            partOut = TRUE;      /* missed part of rectangle above */
1954            if (partIn || (pbox->y1 >= prect->y2))
1955               break;
1956            y = pbox->y1;        /* x guaranteed to be == prect->x1 */
1957         }
1958
1959         if (pbox->x2 <= x)
1960            continue;            /* not far enough over yet */
1961
1962         if (pbox->x1 > x)
1963         {
1964            partOut = TRUE;      /* missed part of rectangle to left */
1965            if (partIn)
1966               break;
1967         }
1968
1969         if (pbox->x1 < prect->x2)
1970         {
1971             partIn = TRUE;      /* definitely overlap */
1972             if (partOut)
1973                break;
1974         }
1975
1976         if (pbox->x2 >= prect->x2)
1977         {
1978            y = pbox->y2;        /* finished with this band */
1979            if (y >= prect->y2)
1980               break;
1981            x = prect->x1;       /* reset x out to left again */
1982         }
1983         else
1984         {
1985             /*
1986              * Because boxes in a band are maximal width, if the first box
1987              * to overlap the rectangle doesn't completely cover it in that
1988              * band, the rectangle must be partially out, since some of it
1989              * will be uncovered in that band. partIn will have been set true
1990              * by now...
1991              */
1992             partOut = TRUE;
1993             break;
1994         }
1995     }
1996
1997     if (partIn)
1998     {
1999         if (y < prect->y2)
2000             return PIXMAN_REGION_PART;
2001         else
2002             return PIXMAN_REGION_IN;
2003     }
2004     else
2005     {
2006         return PIXMAN_REGION_OUT;
2007     }
2008 }
2009
2010 /* PREFIX(pixman_region_translate) (region, x, y)
2011    translates in place
2012 */
2013
2014 void
2015 PREFIX(pixman_region_translate) (pixman_region16_t * region, int x, int y)
2016 {
2017     int x1, x2, y1, y2;
2018     int nbox;
2019     pixman_box16_t * pbox;
2020
2021     good(region);
2022     region->extents.x1 = x1 = region->extents.x1 + x;
2023     region->extents.y1 = y1 = region->extents.y1 + y;
2024     region->extents.x2 = x2 = region->extents.x2 + x;
2025     region->extents.y2 = y2 = region->extents.y2 + y;
2026     if (((x1 - SHRT_MIN)|(y1 - SHRT_MIN)|(SHRT_MAX - x2)|(SHRT_MAX - y2)) >= 0)
2027     {
2028         if (region->data && (nbox = region->data->numRects))
2029         {
2030             for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
2031             {
2032                 pbox->x1 += x;
2033                 pbox->y1 += y;
2034                 pbox->x2 += x;
2035                 pbox->y2 += y;
2036             }
2037         }
2038         return;
2039     }
2040     if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|(SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
2041     {
2042         region->extents.x2 = region->extents.x1;
2043         region->extents.y2 = region->extents.y1;
2044         freeData(region);
2045         region->data = pixman_region_emptyData;
2046         return;
2047     }
2048     if (x1 < SHRT_MIN)
2049         region->extents.x1 = SHRT_MIN;
2050     else if (x2 > SHRT_MAX)
2051         region->extents.x2 = SHRT_MAX;
2052     if (y1 < SHRT_MIN)
2053         region->extents.y1 = SHRT_MIN;
2054     else if (y2 > SHRT_MAX)
2055         region->extents.y2 = SHRT_MAX;
2056     if (region->data && (nbox = region->data->numRects))
2057     {
2058         pixman_box16_t * pboxout;
2059
2060         for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++)
2061         {
2062             pboxout->x1 = x1 = pbox->x1 + x;
2063             pboxout->y1 = y1 = pbox->y1 + y;
2064             pboxout->x2 = x2 = pbox->x2 + x;
2065             pboxout->y2 = y2 = pbox->y2 + y;
2066             if (((x2 - SHRT_MIN)|(y2 - SHRT_MIN)|
2067                  (SHRT_MAX - x1)|(SHRT_MAX - y1)) <= 0)
2068             {
2069                 region->data->numRects--;
2070                 continue;
2071             }
2072             if (x1 < SHRT_MIN)
2073                 pboxout->x1 = SHRT_MIN;
2074             else if (x2 > SHRT_MAX)
2075                 pboxout->x2 = SHRT_MAX;
2076             if (y1 < SHRT_MIN)
2077                 pboxout->y1 = SHRT_MIN;
2078             else if (y2 > SHRT_MAX)
2079                 pboxout->y2 = SHRT_MAX;
2080             pboxout++;
2081         }
2082         if (pboxout != pbox)
2083         {
2084             if (region->data->numRects == 1)
2085             {
2086                 region->extents = *PIXREGION_BOXPTR(region);
2087                 freeData(region);
2088                 region->data = (pixman_region16_data_t *)NULL;
2089             }
2090             else
2091                 pixman_set_extents(region);
2092         }
2093     }
2094 }
2095
2096 /* XXX: Do we need this?
2097 static pixman_bool_t
2098 pixman_region16_data_copy(pixman_region16_t * dst, pixman_region16_t * src)
2099 {
2100     good(dst);
2101     good(src);
2102     if (dst->data)
2103         return TRUE;
2104     if (dst == src)
2105         return TRUE;
2106     if (!src->data || !src->data->size)
2107     {
2108         freeData(dst);
2109         dst->data = (pixman_region16_data_t *)NULL;
2110         return TRUE;
2111     }
2112     if (!dst->data || (dst->data->size < src->data->numRects))
2113     {
2114         freeData(dst);
2115         dst->data = allocData(src->data->numRects);
2116         if (!dst->data)
2117             return pixman_break (dst);
2118     }
2119     dst->data->size = src->data->size;
2120     dst->data->numRects = src->data->numRects;
2121     return TRUE;
2122 }
2123 */
2124
2125 void
2126 PREFIX(pixman_region_reset) (pixman_region16_t *region, pixman_box16_t *box)
2127 {
2128     good(region);
2129     assert(box->x1<=box->x2);
2130     assert(box->y1<=box->y2);
2131     region->extents = *box;
2132     freeData(region);
2133     region->data = (pixman_region16_data_t *)NULL;
2134 }
2135
2136 /* box is "return" value */
2137 int
2138 PREFIX(pixman_region_contains_point) (pixman_region16_t * region,
2139                              int x, int y,
2140                              pixman_box16_t * box)
2141 {
2142     pixman_box16_t *pbox, *pboxEnd;
2143     int numRects;
2144
2145     good(region);
2146     numRects = PIXREGION_NUM_RECTS(region);
2147     if (!numRects || !INBOX(&region->extents, x, y))
2148         return(FALSE);
2149     if (numRects == 1)
2150     {
2151         *box = region->extents;
2152         return(TRUE);
2153     }
2154     for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects;
2155          pbox != pboxEnd;
2156          pbox++)
2157     {
2158         if (y >= pbox->y2)
2159            continue;            /* not there yet */
2160         if ((y < pbox->y1) || (x < pbox->x1))
2161            break;               /* missed it */
2162         if (x >= pbox->x2)
2163            continue;            /* not there yet */
2164         *box = *pbox;
2165         return(TRUE);
2166     }
2167     return(FALSE);
2168 }
2169
2170 int
2171 PREFIX(pixman_region_not_empty) (pixman_region16_t * region)
2172 {
2173     good(region);
2174     return(!PIXREGION_NIL(region));
2175 }
2176
2177 /* XXX: Do we need this?
2178 static int
2179 pixman_region16_broken(pixman_region16_t * region)
2180 {
2181     good(region);
2182     return (PIXREGION_NAR(region));
2183 }
2184 */
2185
2186 void
2187 PREFIX(pixman_region_empty) (pixman_region16_t * region)
2188 {
2189     good(region);
2190     freeData(region);
2191     region->extents.x2 = region->extents.x1;
2192     region->extents.y2 = region->extents.y1;
2193     region->data = pixman_region_emptyData;
2194 }
2195
2196 pixman_box16_t *
2197 PREFIX(pixman_region_extents) (pixman_region16_t * region)
2198 {
2199     good(region);
2200     return(&region->extents);
2201 }
2202
2203 #define ExchangeSpans(a, b)                                 \
2204 {                                                           \
2205     pixman_region16_point_t tpt;                                            \
2206     int    tw;                                              \
2207                                                             \
2208     tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt;    \
2209     tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
2210 }
2211
2212 /* ||| I should apply the merge sort code to rectangle sorting above, and see
2213    if mapping time can be improved.  But right now I've been at work 12 hours,
2214    so forget it.
2215 */
2216
2217 static void QuickSortSpans(
2218     pixman_region16_point_t spans[],
2219     int     widths[],
2220     int     numSpans)
2221 {
2222     int     y;
2223     int     i, j, m;
2224     pixman_region16_point_t *r;
2225
2226     /* Always called with numSpans > 1 */
2227     /* Sorts only by y, doesn't bother to sort by x */
2228
2229     do
2230     {
2231         if (numSpans < 9)
2232         {
2233             /* Do insertion sort */
2234             int yprev;
2235
2236             yprev = spans[0].y;
2237             i = 1;
2238             do
2239             { /* while i != numSpans */
2240                 y = spans[i].y;
2241                 if (yprev > y)
2242                 {
2243                     /* spans[i] is out of order.  Move into proper location. */
2244                     pixman_region16_point_t tpt;
2245                     int     tw, k;
2246
2247                     for (j = 0; y >= spans[j].y; j++) {}
2248                     tpt = spans[i];
2249                     tw  = widths[i];
2250                     for (k = i; k != j; k--)
2251                     {
2252                         spans[k] = spans[k-1];
2253                         widths[k] = widths[k-1];
2254                     }
2255                     spans[j] = tpt;
2256                     widths[j] = tw;
2257                     y = spans[i].y;
2258                 } /* if out of order */
2259                 yprev = y;
2260                 i++;
2261             } while (i != numSpans);
2262             return;
2263         }
2264
2265         /* Choose partition element, stick in location 0 */
2266         m = numSpans / 2;
2267         if (spans[m].y > spans[0].y)            ExchangeSpans(m, 0);
2268         if (spans[m].y > spans[numSpans-1].y)   ExchangeSpans(m, numSpans-1);
2269         if (spans[m].y > spans[0].y)            ExchangeSpans(m, 0);
2270         y = spans[0].y;
2271
2272         /* Partition array */
2273         i = 0;
2274         j = numSpans;
2275         do
2276         {
2277             r = &(spans[i]);
2278             do
2279             {
2280                 r++;
2281                 i++;
2282             } while (i != numSpans && r->y < y);
2283             r = &(spans[j]);
2284             do
2285             {
2286                 r--;
2287                 j--;
2288             } while (y < r->y);
2289             if (i < j)
2290                 ExchangeSpans(i, j);
2291         } while (i < j);
2292
2293         /* Move partition element back to middle */
2294         ExchangeSpans(0, j);
2295
2296         /* Recurse */
2297         if (numSpans-j-1 > 1)
2298             QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
2299         numSpans = j;
2300     } while (numSpans > 1);
2301 }
2302
2303 #define NextBand()                                                  \
2304 {                                                                   \
2305     clipy1 = pboxBandStart->y1;                                     \
2306     clipy2 = pboxBandStart->y2;                                     \
2307     pboxBandEnd = pboxBandStart + 1;                                \
2308     while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) {  \
2309         pboxBandEnd++;                                              \
2310     }                                                               \
2311     for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
2312 }
2313
2314 /*
2315     Clip a list of scanlines to a region.  The caller has allocated the
2316     space.  FSorted is non-zero if the scanline origins are in ascending
2317     order.
2318     returns the number of new, clipped scanlines.
2319 */
2320
2321 #ifdef XXX_DO_WE_NEED_THIS
2322 static int
2323 pixman_region16_clip_spans(
2324     pixman_region16_t           *prgnDst,
2325     pixman_region16_point_t     *ppt,
2326     int                 *pwidth,
2327     int                 nspans,
2328     pixman_region16_point_t     *pptNew,
2329     int                 *pwidthNew,
2330     int                 fSorted)
2331 {
2332     pixman_region16_point_t     *pptLast;
2333     int                 *pwidthNewStart;        /* the vengeance of Xerox! */
2334     int y, x1, x2;
2335     int numRects;
2336
2337     good(prgnDst);
2338     pptLast = ppt + nspans;
2339     pwidthNewStart = pwidthNew;
2340
2341     if (!prgnDst->data)
2342     {
2343         /* Do special fast code with clip boundaries in registers(?) */
2344         /* It doesn't pay much to make use of fSorted in this case,
2345            so we lump everything together. */
2346
2347            int clipx1, clipx2, clipy1, clipy2;
2348
2349         clipx1 = prgnDst->extents.x1;
2350         clipy1 = prgnDst->extents.y1;
2351         clipx2 = prgnDst->extents.x2;
2352         clipy2 = prgnDst->extents.y2;
2353
2354         for (; ppt != pptLast; ppt++, pwidth++)
2355         {
2356             y = ppt->y;
2357             x1 = ppt->x;
2358             if (clipy1 <= y && y < clipy2)
2359             {
2360                 x2 = x1 + *pwidth;
2361                 if (x1 < clipx1)    x1 = clipx1;
2362                 if (x2 > clipx2)    x2 = clipx2;
2363                 if (x1 < x2)
2364                 {
2365                     /* part of span in clip rectangle */
2366                     pptNew->x = x1;
2367                     pptNew->y = y;
2368                     *pwidthNew = x2 - x1;
2369                     pptNew++;
2370                     pwidthNew++;
2371                 }
2372             }
2373         } /* end for */
2374
2375     }
2376     else if ((numRects = prgnDst->data->numRects))
2377     {
2378         /* Have to clip against many boxes */
2379         pixman_box16_t *pboxBandStart, *pboxBandEnd;
2380         pixman_box16_t *pbox;
2381         pixman_box16_t *pboxLast;
2382         int     clipy1, clipy2;
2383
2384         /* In this case, taking advantage of sorted spans gains more than
2385            the sorting costs. */
2386         if ((! fSorted) && (nspans > 1))
2387             QuickSortSpans(ppt, pwidth, nspans);
2388
2389         pboxBandStart = PIXREGION_BOXPTR(prgnDst);
2390         pboxLast = pboxBandStart + numRects;
2391
2392         NextBand();
2393
2394         for (; ppt != pptLast; )
2395         {
2396             y = ppt->y;
2397             if (y < clipy2)
2398             {
2399                 /* span is in the current band */
2400                 pbox = pboxBandStart;
2401                 x1 = ppt->x;
2402                 x2 = x1 + *pwidth;
2403                 do
2404                 { /* For each box in band */
2405                     int    newx1, newx2;
2406
2407                     newx1 = x1;
2408                     newx2 = x2;
2409                     if (newx1 < pbox->x1)   newx1 = pbox->x1;
2410                     if (newx2 > pbox->x2)   newx2 = pbox->x2;
2411                     if (newx1 < newx2)
2412                     {
2413                         /* Part of span in clip rectangle */
2414                         pptNew->x = newx1;
2415                         pptNew->y = y;
2416                         *pwidthNew = newx2 - newx1;
2417                         pptNew++;
2418                         pwidthNew++;
2419                     }
2420                     pbox++;
2421                 } while (pbox != pboxBandEnd);
2422                 ppt++;
2423                 pwidth++;
2424             }
2425             else
2426             {
2427                 /* Move to next band, adjust ppt as needed */
2428                 pboxBandStart = pboxBandEnd;
2429                 if (pboxBandStart == pboxLast)
2430                     break; /* We're completely done */
2431                 NextBand();
2432             }
2433         }
2434     }
2435     return (pwidthNew - pwidthNewStart);
2436 }
2437
2438 /* find the band in a region with the most rectangles */
2439 static int
2440 pixman_region16_find_max_band(pixman_region16_t * prgn)
2441 {
2442     int nbox;
2443     pixman_box16_t * pbox;
2444     int nThisBand;
2445     int nMaxBand = 0;
2446     short yThisBand;
2447
2448     good(prgn);
2449     nbox = PIXREGION_NUM_RECTS(prgn);
2450     pbox = PIXREGION_RECTS(prgn);
2451
2452     while(nbox > 0)
2453     {
2454         yThisBand = pbox->y1;
2455         nThisBand = 0;
2456         while((nbox > 0) && (pbox->y1 == yThisBand))
2457         {
2458             nbox--;
2459             pbox++;
2460             nThisBand++;
2461         }
2462         if (nThisBand > nMaxBand)
2463             nMaxBand = nThisBand;
2464     }
2465     return (nMaxBand);
2466 }
2467 #endif /* XXX_DO_WE_NEED_THIS */
2468
2469
2470 pixman_bool_t
2471 PREFIX(pixman_region_selfcheck) (reg)
2472     pixman_region16_t * reg;
2473 {
2474     int i, numRects;
2475
2476     if ((reg->extents.x1 > reg->extents.x2) ||
2477         (reg->extents.y1 > reg->extents.y2))
2478         return FALSE;
2479     numRects = PIXREGION_NUM_RECTS(reg);
2480     if (!numRects)
2481         return ((reg->extents.x1 == reg->extents.x2) &&
2482                 (reg->extents.y1 == reg->extents.y2) &&
2483                 (reg->data->size || (reg->data == pixman_region_emptyData)));
2484     else if (numRects == 1)
2485         return (!reg->data);
2486     else
2487     {
2488         pixman_box16_t * pboxP, * pboxN;
2489         pixman_box16_t box;
2490
2491         pboxP = PIXREGION_RECTS(reg);
2492         box = *pboxP;
2493         box.y2 = pboxP[numRects-1].y2;
2494         pboxN = pboxP + 1;
2495         for (i = numRects; --i > 0; pboxP++, pboxN++)
2496         {
2497             if ((pboxN->x1 >= pboxN->x2) ||
2498                 (pboxN->y1 >= pboxN->y2))
2499                 return FALSE;
2500             if (pboxN->x1 < box.x1)
2501                 box.x1 = pboxN->x1;
2502             if (pboxN->x2 > box.x2)
2503                 box.x2 = pboxN->x2;
2504             if ((pboxN->y1 < pboxP->y1) ||
2505                 ((pboxN->y1 == pboxP->y1) &&
2506                  ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
2507                 return FALSE;
2508         }
2509         return ((box.x1 == reg->extents.x1) &&
2510                 (box.x2 == reg->extents.x2) &&
2511                 (box.y1 == reg->extents.y1) &&
2512                 (box.y2 == reg->extents.y2));
2513     }
2514 }
2515
2516 pixman_bool_t
2517 PREFIX(pixman_region_init_rects) (pixman_region16_t *region,
2518                           pixman_box16_t *boxes, int count)
2519 {
2520     int overlap;
2521
2522     /* if it's 1, then we just want to set the extents, so call
2523      * the existing method. */
2524     if (count == 1) {
2525        PREFIX(pixman_region_init_rect) (region,
2526                                boxes[0].x1,
2527                                boxes[0].y1,
2528                                boxes[0].x2 - boxes[0].x1,
2529                                boxes[0].y2 - boxes[0].y1);
2530        return TRUE;
2531     }
2532
2533     PREFIX(pixman_region_init) (region);
2534
2535     /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
2536      * a special case, and causing pixman_rect_alloc would cause
2537      * us to leak memory (because the 0-rect case should be the
2538      * static pixman_region_emptyData data).
2539      */
2540     if (count == 0)
2541         return TRUE;
2542
2543     if (!pixman_rect_alloc(region, count))
2544         return FALSE;
2545
2546     /* Copy in the rects */
2547     memcpy (PIXREGION_RECTS(region), boxes, sizeof(pixman_box16_t) * count);
2548     region->data->numRects = count;
2549
2550     /* Validate */
2551     region->extents.x1 = region->extents.x2 = 0;
2552     return PREFIX(pixman_region_validate) (region, &overlap);
2553 }