pixman/pixman-region.c

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