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