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