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  * Copyright © 1998 Keith Packard
  46  *
  47  * Permission to use, copy, modify, distribute, and sell this software and its
  48  * documentation for any purpose is hereby granted without fee, provided that
  49  * the above copyright notice appear in all copies and that both that
  50  * copyright notice and this permission notice appear in supporting
  51  * documentation, and that the name of Keith Packard not be used in
  52  * advertising or publicity pertaining to distribution of the software without
  53  * specific, written prior permission.  Keith Packard makes no
  54  * representations about the suitability of this software for any purpose.  It
  55  * is provided "as is" without express or implied warranty.
  56  *
  57  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  58  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  59  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  60  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  61  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  62  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  63  * PERFORMANCE OF THIS SOFTWARE.
  64  */
  65
  66 #include <stdlib.h>
  67 #include <limits.h>
  68 #include <string.h>
  69 #include <stdio.h>
  70 #include "pixman-private.h"
  71
  72 #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
  73 /* not a region */
  74 #define PIXREGION_NAR(reg)      ((reg)->data == pixman_broken_data)
  75 #define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
  76 #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
  77 #define PIXREGION_RECTS(reg) \
  78     ((reg)->data ? (box_type_t *)((reg)->data + 1) \
  79      : &(reg)->extents)
  80 #define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))
  81 #define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])
  82 #define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)
  83 #define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)
  84
  85 #define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)
  86 #define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2)
  87
  88 #ifdef DEBUG
  89
  90 #define GOOD(reg)                                                       \
  91     do                                                                  \
  92     {                                                                   \
  93         if (!PREFIX (_selfcheck (reg)))                                 \
  94             _pixman_log_error (FUNC, "Malformed region " # reg);        \
  95     } while (0)
  96
  97 #else
  98
  99 #define GOOD(reg)
 100
 101 #endif
 102
 103 static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };
 104 static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };
 105 #if defined (__llvm__) && !defined (__clang__)
 106 static const volatile region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
 107 #else
 108 static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
 109 #endif
 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         critical_if_fail (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         if (BAD_RECT (&region->extents))
 389             _pixman_log_error (FUNC, "Invalid rectangle passed");
 390         PREFIX (_init) (region);
 391         return;
 392     }
 393
 394     region->data = NULL;
 395 }
 396
 397 PIXMAN_EXPORT void
 398 PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents)
 399 {
 400     if (!GOOD_RECT (extents))
 401     {
 402         if (BAD_RECT (extents))
 403             _pixman_log_error (FUNC, "Invalid rectangle passed");
 404         PREFIX (_init) (region);
 405         return;
 406     }
 407     region->extents = *extents;
 408
 409     region->data = NULL;
 410 }
 411
 412 PIXMAN_EXPORT void
 413 PREFIX (_fini) (region_type_t *region)
 414 {
 415     GOOD (region);
 416     FREE_DATA (region);
 417 }
 418
 419 PIXMAN_EXPORT int
 420 PREFIX (_n_rects) (region_type_t *region)
 421 {
 422     return PIXREGION_NUMRECTS (region);
 423 }
 424
 425 PIXMAN_EXPORT box_type_t *
 426 PREFIX (_rectangles) (region_type_t *region,
 427                       int               *n_rects)
 428 {
 429     if (n_rects)
 430         *n_rects = PIXREGION_NUMRECTS (region);
 431
 432     return PIXREGION_RECTS (region);
 433 }
 434
 435 static pixman_bool_t
 436 pixman_break (region_type_t *region)
 437 {
 438     FREE_DATA (region);
 439
 440     region->extents = *pixman_region_empty_box;
 441     region->data = pixman_broken_data;
 442
 443     return FALSE;
 444 }
 445
 446 static pixman_bool_t
 447 pixman_rect_alloc (region_type_t * region,
 448                    int             n)
 449 {
 450     region_data_type_t *data;
 451
 452     if (!region->data)
 453     {
 454         n++;
 455         region->data = alloc_data (n);
 456
 457         if (!region->data)
 458             return pixman_break (region);
 459
 460         region->data->numRects = 1;
 461         *PIXREGION_BOXPTR (region) = region->extents;
 462     }
 463     else if (!region->data->size)
 464     {
 465         region->data = alloc_data (n);
 466
 467         if (!region->data)
 468             return pixman_break (region);
 469
 470         region->data->numRects = 0;
 471     }
 472     else
 473     {
 474         size_t data_size;
 475
 476         if (n == 1)
 477         {
 478             n = region->data->numRects;
 479             if (n > 500) /* XXX pick numbers out of a hat */
 480                 n = 250;
 481         }
 482
 483         n += region->data->numRects;
 484         data_size = PIXREGION_SZOF (n);
 485
 486         if (!data_size)
 487         {
 488             data = NULL;
 489         }
 490         else
 491         {
 492             data = (region_data_type_t *)
 493                 realloc (region->data, PIXREGION_SZOF (n));
 494         }
 495
 496         if (!data)
 497             return pixman_break (region);
 498
 499         region->data = data;
 500     }
 501
 502     region->data->size = n;
 503
 504     return TRUE;
 505 }
 506
 507 PIXMAN_EXPORT pixman_bool_t
 508 PREFIX (_copy) (region_type_t *dst, region_type_t *src)
 509 {
 510     GOOD (dst);
 511     GOOD (src);
 512
 513     if (dst == src)
 514         return TRUE;
 515
 516     dst->extents = src->extents;
 517
 518     if (!src->data || !src->data->size)
 519     {
 520         FREE_DATA (dst);
 521         dst->data = src->data;
 522         return TRUE;
 523     }
 524
 525     if (!dst->data || (dst->data->size < src->data->numRects))
 526     {
 527         FREE_DATA (dst);
 528
 529         dst->data = alloc_data (src->data->numRects);
 530
 531         if (!dst->data)
 532             return pixman_break (dst);
 533
 534         dst->data->size = src->data->numRects;
 535     }
 536
 537     dst->data->numRects = src->data->numRects;
 538
 539     memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),
 540              dst->data->numRects * sizeof(box_type_t));
 541
 542     return TRUE;
 543 }
 544
 545 /*======================================================================
 546  *          Generic Region Operator
 547  *====================================================================*/
 548
 549 /*-
 550  *-----------------------------------------------------------------------
 551  * pixman_coalesce --
 552  *      Attempt to merge the boxes in the current band with those in the
 553  *      previous one.  We are guaranteed that the current band extends to
 554  *      the end of the rects array.  Used only by pixman_op.
 555  *
 556  * Results:
 557  *      The new index for the previous band.
 558  *
 559  * Side Effects:
 560  *      If coalescing takes place:
 561  *          - rectangles in the previous band will have their y2 fields
 562  *            altered.
 563  *          - region->data->numRects will be decreased.
 564  *
 565  *-----------------------------------------------------------------------
 566  */
 567 static inline int
 568 pixman_coalesce (region_type_t * region,      /* Region to coalesce              */
 569                  int             prev_start,  /* Index of start of previous band */
 570                  int             cur_start)   /* Index of start of current band  */
 571 {
 572     box_type_t *prev_box;       /* Current box in previous band      */
 573     box_type_t *cur_box;        /* Current box in current band       */
 574     int numRects;               /* Number rectangles in both bands   */
 575     int y2;                     /* Bottom of current band            */
 576
 577     /*
 578      * Figure out how many rectangles are in the band.
 579      */
 580     numRects = cur_start - prev_start;
 581     critical_if_fail (numRects == region->data->numRects - cur_start);
 582
 583     if (!numRects) return cur_start;
 584
 585     /*
 586      * The bands may only be coalesced if the bottom of the previous
 587      * matches the top scanline of the current.
 588      */
 589     prev_box = PIXREGION_BOX (region, prev_start);
 590     cur_box = PIXREGION_BOX (region, cur_start);
 591     if (prev_box->y2 != cur_box->y1) return cur_start;
 592
 593     /*
 594      * Make sure the bands have boxes in the same places. This
 595      * assumes that boxes have been added in such a way that they
 596      * cover the most area possible. I.e. two boxes in a band must
 597      * have some horizontal space between them.
 598      */
 599     y2 = cur_box->y2;
 600
 601     do
 602     {
 603         if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2))
 604             return (cur_start);
 605
 606         prev_box++;
 607         cur_box++;
 608         numRects--;
 609     }
 610     while (numRects);
 611
 612     /*
 613      * The bands may be merged, so set the bottom y of each box
 614      * in the previous band to the bottom y of the current band.
 615      */
 616     numRects = cur_start - prev_start;
 617     region->data->numRects -= numRects;
 618
 619     do
 620     {
 621         prev_box--;
 622         prev_box->y2 = y2;
 623         numRects--;
 624     }
 625     while (numRects);
 626
 627     return prev_start;
 628 }
 629
 630 /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
 631
 632 #define COALESCE(new_reg, prev_band, cur_band)                          \
 633     do                                                                  \
 634     {                                                                   \
 635         if (cur_band - prev_band == new_reg->data->numRects - cur_band) \
 636             prev_band = pixman_coalesce (new_reg, prev_band, cur_band); \
 637         else                                                            \
 638             prev_band = cur_band;                                       \
 639     } while (0)
 640
 641 /*-
 642  *-----------------------------------------------------------------------
 643  * pixman_region_append_non_o --
 644  *      Handle a non-overlapping band for the union and subtract operations.
 645  *      Just adds the (top/bottom-clipped) rectangles into the region.
 646  *      Doesn't have to check for subsumption or anything.
 647  *
 648  * Results:
 649  *      None.
 650  *
 651  * Side Effects:
 652  *      region->data->numRects is incremented and the rectangles overwritten
 653  *      with the rectangles we're passed.
 654  *
 655  *-----------------------------------------------------------------------
 656  */
 657 static inline pixman_bool_t
 658 pixman_region_append_non_o (region_type_t * region,
 659                             box_type_t *    r,
 660                             box_type_t *    r_end,
 661                             int             y1,
 662                             int             y2)
 663 {
 664     box_type_t *next_rect;
 665     int new_rects;
 666
 667     new_rects = r_end - r;
 668
 669     critical_if_fail (y1 < y2);
 670     critical_if_fail (new_rects != 0);
 671
 672     /* Make sure we have enough space for all rectangles to be added */
 673     RECTALLOC (region, new_rects);
 674     next_rect = PIXREGION_TOP (region);
 675     region->data->numRects += new_rects;
 676
 677     do
 678     {
 679         critical_if_fail (r->x1 < r->x2);
 680         ADDRECT (next_rect, r->x1, y1, r->x2, y2);
 681         r++;
 682     }
 683     while (r != r_end);
 684
 685     return TRUE;
 686 }
 687
 688 #define FIND_BAND(r, r_band_end, r_end, ry1)                         \
 689     do                                                               \
 690     {                                                                \
 691         ry1 = r->y1;                                                 \
 692         r_band_end = r + 1;                                          \
 693         while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) {   \
 694             r_band_end++;                                            \
 695         }                                                            \
 696     } while (0)
 697
 698 #define APPEND_REGIONS(new_reg, r, r_end)                               \
 699     do                                                                  \
 700     {                                                                   \
 701         int new_rects;                                                  \
 702         if ((new_rects = r_end - r)) {                                  \
 703             RECTALLOC_BAIL (new_reg, new_rects, bail);                  \
 704             memmove ((char *)PIXREGION_TOP (new_reg), (char *)r,        \
 705                      new_rects * sizeof(box_type_t));                   \
 706             new_reg->data->numRects += new_rects;                       \
 707         }                                                               \
 708     } while (0)
 709
 710 /*-
 711  *-----------------------------------------------------------------------
 712  * pixman_op --
 713  *      Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
 714  *      pixman_region_subtract, pixman_region_intersect....  Both regions MUST have at least one
 715  *      rectangle, and cannot be the same object.
 716  *
 717  * Results:
 718  *      TRUE if successful.
 719  *
 720  * Side Effects:
 721  *      The new region is overwritten.
 722  *      overlap set to TRUE if overlap_func ever returns TRUE.
 723  *
 724  * Notes:
 725  *      The idea behind this function is to view the two regions as sets.
 726  *      Together they cover a rectangle of area that this function divides
 727  *      into horizontal bands where points are covered only by one region
 728  *      or by both. For the first case, the non_overlap_func is called with
 729  *      each the band and the band's upper and lower extents. For the
 730  *      second, the overlap_func is called to process the entire band. It
 731  *      is responsible for clipping the rectangles in the band, though
 732  *      this function provides the boundaries.
 733  *      At the end of each band, the new region is coalesced, if possible,
 734  *      to reduce the number of rectangles in the region.
 735  *
 736  *-----------------------------------------------------------------------
 737  */
 738
 739 typedef pixman_bool_t (*overlap_proc_ptr) (region_type_t *region,
 740                                            box_type_t *   r1,
 741                                            box_type_t *   r1_end,
 742                                            box_type_t *   r2,
 743                                            box_type_t *   r2_end,
 744                                            int            y1,
 745                                            int            y2,
 746                                            int *          overlap);
 747
 748 static pixman_bool_t
 749 pixman_op (region_type_t *  new_reg,               /* Place to store result         */
 750            region_type_t *  reg1,                  /* First region in operation     */
 751            region_type_t *  reg2,                  /* 2d region in operation        */
 752            overlap_proc_ptr overlap_func,          /* Function to call for over-
 753                                                     * lapping bands                 */
 754            int              append_non1,           /* Append non-overlapping bands
 755                                                     * in region 1 ?
 756                                                     */
 757            int              append_non2,           /* Append non-overlapping bands
 758                                                     * in region 2 ?
 759                                                     */
 760            int *            overlap)
 761 {
 762     box_type_t *r1;                 /* Pointer into first region     */
 763     box_type_t *r2;                 /* Pointer into 2d region        */
 764     box_type_t *r1_end;             /* End of 1st region             */
 765     box_type_t *r2_end;             /* End of 2d region              */
 766     int ybot;                       /* Bottom of intersection        */
 767     int ytop;                       /* Top of intersection           */
 768     region_data_type_t *old_data;   /* Old data for new_reg          */
 769     int prev_band;                  /* Index of start of
 770                                      * previous band in new_reg       */
 771     int cur_band;                   /* Index of start of current
 772                                      * band in new_reg               */
 773     box_type_t * r1_band_end;       /* End of current band in r1     */
 774     box_type_t * r2_band_end;       /* End of current band in r2     */
 775     int top;                        /* Top of non-overlapping band   */
 776     int bot;                        /* Bottom of non-overlapping band*/
 777     int r1y1;                       /* Temps for r1->y1 and r2->y1   */
 778     int r2y1;
 779     int new_size;
 780     int numRects;
 781
 782     /*
 783      * Break any region computed from a broken region
 784      */
 785     if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
 786         return pixman_break (new_reg);
 787
 788     /*
 789      * Initialization:
 790      *  set r1, r2, r1_end and r2_end appropriately, save the rectangles
 791      * of the destination region until the end in case it's one of
 792      * the two source regions, then mark the "new" region empty, allocating
 793      * another array of rectangles for it to use.
 794      */
 795
 796     r1 = PIXREGION_RECTS (reg1);
 797     new_size = PIXREGION_NUMRECTS (reg1);
 798     r1_end = r1 + new_size;
 799
 800     numRects = PIXREGION_NUMRECTS (reg2);
 801     r2 = PIXREGION_RECTS (reg2);
 802     r2_end = r2 + numRects;
 803
 804     critical_if_fail (r1 != r1_end);
 805     critical_if_fail (r2 != r2_end);
 806
 807     old_data = (region_data_type_t *)NULL;
 808
 809     if (((new_reg == reg1) && (new_size > 1)) ||
 810         ((new_reg == reg2) && (numRects > 1)))
 811     {
 812         old_data = new_reg->data;
 813         new_reg->data = pixman_region_empty_data;
 814     }
 815
 816     /* guess at new size */
 817     if (numRects > new_size)
 818         new_size = numRects;
 819
 820     new_size <<= 1;
 821
 822     if (!new_reg->data)
 823         new_reg->data = pixman_region_empty_data;
 824     else if (new_reg->data->size)
 825         new_reg->data->numRects = 0;
 826
 827     if (new_size > new_reg->data->size)
 828     {
 829         if (!pixman_rect_alloc (new_reg, new_size))
 830         {
 831             if (old_data)
 832                 free (old_data);
 833             return FALSE;
 834         }
 835     }
 836
 837     /*
 838      * Initialize ybot.
 839      * In the upcoming loop, ybot and ytop serve different functions depending
 840      * on whether the band being handled is an overlapping or non-overlapping
 841      * band.
 842      *  In the case of a non-overlapping band (only one of the regions
 843      * has points in the band), ybot is the bottom of the most recent
 844      * intersection and thus clips the top of the rectangles in that band.
 845      * ytop is the top of the next intersection between the two regions and
 846      * serves to clip the bottom of the rectangles in the current band.
 847      *  For an overlapping band (where the two regions intersect), ytop clips
 848      * the top of the rectangles of both regions and ybot clips the bottoms.
 849      */
 850
 851     ybot = MIN (r1->y1, r2->y1);
 852
 853     /*
 854      * prev_band serves to mark the start of the previous band so rectangles
 855      * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
 856      * In the beginning, there is no previous band, so prev_band == cur_band
 857      * (cur_band is set later on, of course, but the first band will always
 858      * start at index 0). prev_band and cur_band must be indices because of
 859      * the possible expansion, and resultant moving, of the new region's
 860      * array of rectangles.
 861      */
 862     prev_band = 0;
 863
 864     do
 865     {
 866         /*
 867          * This algorithm proceeds one source-band (as opposed to a
 868          * destination band, which is determined by where the two regions
 869          * intersect) at a time. r1_band_end and r2_band_end serve to mark the
 870          * rectangle after the last one in the current band for their
 871          * respective regions.
 872          */
 873         critical_if_fail (r1 != r1_end);
 874         critical_if_fail (r2 != r2_end);
 875
 876         FIND_BAND (r1, r1_band_end, r1_end, r1y1);
 877         FIND_BAND (r2, r2_band_end, r2_end, r2y1);
 878
 879         /*
 880          * First handle the band that doesn't intersect, if any.
 881          *
 882          * Note that attention is restricted to one band in the
 883          * non-intersecting region at once, so if a region has n
 884          * bands between the current position and the next place it overlaps
 885          * the other, this entire loop will be passed through n times.
 886          */
 887         if (r1y1 < r2y1)
 888         {
 889             if (append_non1)
 890             {
 891                 top = MAX (r1y1, ybot);
 892                 bot = MIN (r1->y2, r2y1);
 893                 if (top != bot)
 894                 {
 895                     cur_band = new_reg->data->numRects;
 896                     if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))
 897                         goto bail;
 898                     COALESCE (new_reg, prev_band, cur_band);
 899                 }
 900             }
 901             ytop = r2y1;
 902         }
 903         else if (r2y1 < r1y1)
 904         {
 905             if (append_non2)
 906             {
 907                 top = MAX (r2y1, ybot);
 908                 bot = MIN (r2->y2, r1y1);
 909
 910                 if (top != bot)
 911                 {
 912                     cur_band = new_reg->data->numRects;
 913
 914                     if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))
 915                         goto bail;
 916
 917                     COALESCE (new_reg, prev_band, cur_band);
 918                 }
 919             }
 920             ytop = r1y1;
 921         }
 922         else
 923         {
 924             ytop = r1y1;
 925         }
 926
 927         /*
 928          * Now see if we've hit an intersecting band. The two bands only
 929          * intersect if ybot > ytop
 930          */
 931         ybot = MIN (r1->y2, r2->y2);
 932         if (ybot > ytop)
 933         {
 934             cur_band = new_reg->data->numRects;
 935
 936             if (!(*overlap_func)(new_reg,
 937                                  r1, r1_band_end,
 938                                  r2, r2_band_end,
 939                                  ytop, ybot,
 940                                  overlap))
 941             {
 942                 goto bail;
 943             }
 944
 945             COALESCE (new_reg, prev_band, cur_band);
 946         }
 947
 948         /*
 949          * If we've finished with a band (y2 == ybot) we skip forward
 950          * in the region to the next band.
 951          */
 952         if (r1->y2 == ybot)
 953             r1 = r1_band_end;
 954
 955         if (r2->y2 == ybot)
 956             r2 = r2_band_end;
 957
 958     }
 959     while (r1 != r1_end && r2 != r2_end);
 960
 961     /*
 962      * Deal with whichever region (if any) still has rectangles left.
 963      *
 964      * We only need to worry about banding and coalescing for the very first
 965      * band left.  After that, we can just group all remaining boxes,
 966      * regardless of how many bands, into one final append to the list.
 967      */
 968
 969     if ((r1 != r1_end) && append_non1)
 970     {
 971         /* Do first non_overlap1Func call, which may be able to coalesce */
 972         FIND_BAND (r1, r1_band_end, r1_end, r1y1);
 973
 974         cur_band = new_reg->data->numRects;
 975
 976         if (!pixman_region_append_non_o (new_reg,
 977                                          r1, r1_band_end,
 978                                          MAX (r1y1, ybot), r1->y2))
 979         {
 980             goto bail;
 981         }
 982
 983         COALESCE (new_reg, prev_band, cur_band);
 984
 985         /* Just append the rest of the boxes  */
 986         APPEND_REGIONS (new_reg, r1_band_end, r1_end);
 987     }
 988     else if ((r2 != r2_end) && append_non2)
 989     {
 990         /* Do first non_overlap2Func call, which may be able to coalesce */
 991         FIND_BAND (r2, r2_band_end, r2_end, r2y1);
 992
 993         cur_band = new_reg->data->numRects;
 994
 995         if (!pixman_region_append_non_o (new_reg,
 996                                          r2, r2_band_end,
 997                                          MAX (r2y1, ybot), r2->y2))
 998         {
 999             goto bail;
1000         }
1001
1002         COALESCE (new_reg, prev_band, cur_band);
1003
1004         /* Append rest of boxes */
1005         APPEND_REGIONS (new_reg, r2_band_end, r2_end);
1006     }
1007
1008     if (old_data)
1009         free (old_data);
1010
1011     if (!(numRects = new_reg->data->numRects))
1012     {
1013         FREE_DATA (new_reg);
1014         new_reg->data = pixman_region_empty_data;
1015     }
1016     else if (numRects == 1)
1017     {
1018         new_reg->extents = *PIXREGION_BOXPTR (new_reg);
1019         FREE_DATA (new_reg);
1020         new_reg->data = (region_data_type_t *)NULL;
1021     }
1022     else
1023     {
1024         DOWNSIZE (new_reg, numRects);
1025     }
1026
1027     return TRUE;
1028
1029 bail:
1030     if (old_data)
1031         free (old_data);
1032
1033     return pixman_break (new_reg);
1034 }
1035
1036 /*-
1037  *-----------------------------------------------------------------------
1038  * pixman_set_extents --
1039  *      Reset the extents of a region to what they should be. Called by
1040  *      pixman_region_subtract and pixman_region_intersect as they can't
1041  *      figure it out along the way or do so easily, as pixman_region_union can.
1042  *
1043  * Results:
1044  *      None.
1045  *
1046  * Side Effects:
1047  *      The region's 'extents' structure is overwritten.
1048  *
1049  *-----------------------------------------------------------------------
1050  */
1051 static void
1052 pixman_set_extents (region_type_t *region)
1053 {
1054     box_type_t *box, *box_end;
1055
1056     if (!region->data)
1057         return;
1058
1059     if (!region->data->size)
1060     {
1061         region->extents.x2 = region->extents.x1;
1062         region->extents.y2 = region->extents.y1;
1063         return;
1064     }
1065
1066     box = PIXREGION_BOXPTR (region);
1067     box_end = PIXREGION_END (region);
1068
1069     /*
1070      * Since box is the first rectangle in the region, it must have the
1071      * smallest y1 and since box_end is the last rectangle in the region,
1072      * it must have the largest y2, because of banding. Initialize x1 and
1073      * x2 from  box and box_end, resp., as good things to initialize them
1074      * to...
1075      */
1076     region->extents.x1 = box->x1;
1077     region->extents.y1 = box->y1;
1078     region->extents.x2 = box_end->x2;
1079     region->extents.y2 = box_end->y2;
1080
1081     critical_if_fail (region->extents.y1 < region->extents.y2);
1082
1083     while (box <= box_end)
1084     {
1085         if (box->x1 < region->extents.x1)
1086             region->extents.x1 = box->x1;
1087         if (box->x2 > region->extents.x2)
1088             region->extents.x2 = box->x2;
1089         box++;
1090     }
1091
1092     critical_if_fail (region->extents.x1 < region->extents.x2);
1093 }
1094
1095 /*======================================================================
1096  *          Region Intersection
1097  *====================================================================*/
1098 /*-
1099  *-----------------------------------------------------------------------
1100  * pixman_region_intersect_o --
1101  *      Handle an overlapping band for pixman_region_intersect.
1102  *
1103  * Results:
1104  *      TRUE if successful.
1105  *
1106  * Side Effects:
1107  *      Rectangles may be added to the region.
1108  *
1109  *-----------------------------------------------------------------------
1110  */
1111 /*ARGSUSED*/
1112 static pixman_bool_t
1113 pixman_region_intersect_o (region_type_t *region,
1114                            box_type_t *   r1,
1115                            box_type_t *   r1_end,
1116                            box_type_t *   r2,
1117                            box_type_t *   r2_end,
1118                            int            y1,
1119                            int            y2,
1120                            int *          overlap)
1121 {
1122     int x1;
1123     int x2;
1124     box_type_t *        next_rect;
1125
1126     next_rect = PIXREGION_TOP (region);
1127
1128     critical_if_fail (y1 < y2);
1129     critical_if_fail (r1 != r1_end && r2 != r2_end);
1130
1131     do
1132     {
1133         x1 = MAX (r1->x1, r2->x1);
1134         x2 = MIN (r1->x2, r2->x2);
1135
1136         /*
1137          * If there's any overlap between the two rectangles, add that
1138          * overlap to the new region.
1139          */
1140         if (x1 < x2)
1141             NEWRECT (region, next_rect, x1, y1, x2, y2);
1142
1143         /*
1144          * Advance the pointer(s) with the leftmost right side, since the next
1145          * rectangle on that list may still overlap the other region's
1146          * current rectangle.
1147          */
1148         if (r1->x2 == x2)
1149         {
1150             r1++;
1151         }
1152         if (r2->x2 == x2)
1153         {
1154             r2++;
1155         }
1156     }
1157     while ((r1 != r1_end) && (r2 != r2_end));
1158
1159     return TRUE;
1160 }
1161
1162 PIXMAN_EXPORT pixman_bool_t
1163 PREFIX (_intersect) (region_type_t *     new_reg,
1164                      region_type_t *        reg1,
1165                      region_type_t *        reg2)
1166 {
1167     GOOD (reg1);
1168     GOOD (reg2);
1169     GOOD (new_reg);
1170
1171     /* check for trivial reject */
1172     if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||
1173         !EXTENTCHECK (&reg1->extents, &reg2->extents))
1174     {
1175         /* Covers about 20% of all cases */
1176         FREE_DATA (new_reg);
1177         new_reg->extents.x2 = new_reg->extents.x1;
1178         new_reg->extents.y2 = new_reg->extents.y1;
1179         if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
1180         {
1181             new_reg->data = pixman_broken_data;
1182             return FALSE;
1183         }
1184         else
1185         {
1186             new_reg->data = pixman_region_empty_data;
1187         }
1188     }
1189     else if (!reg1->data && !reg2->data)
1190     {
1191         /* Covers about 80% of cases that aren't trivially rejected */
1192         new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);
1193         new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);
1194         new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);
1195         new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);
1196
1197         FREE_DATA (new_reg);
1198
1199         new_reg->data = (region_data_type_t *)NULL;
1200     }
1201     else if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))
1202     {
1203         return PREFIX (_copy) (new_reg, reg1);
1204     }
1205     else if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))
1206     {
1207         return PREFIX (_copy) (new_reg, reg2);
1208     }
1209     else if (reg1 == reg2)
1210     {
1211         return PREFIX (_copy) (new_reg, reg1);
1212     }
1213     else
1214     {
1215         /* General purpose intersection */
1216         int overlap; /* result ignored */
1217
1218         if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE,
1219                         &overlap))
1220         {
1221             return FALSE;
1222         }
1223
1224         pixman_set_extents (new_reg);
1225     }
1226
1227     GOOD (new_reg);
1228     return(TRUE);
1229 }
1230
1231 #define MERGERECT(r)                                                    \
1232     do                                                                  \
1233     {                                                                   \
1234         if (r->x1 <= x2)                                                \
1235         {                                                               \
1236             /* Merge with current rectangle */                          \
1237             if (r->x1 < x2)                                             \
1238                 *overlap = TRUE;                                        \
1239                                                                         \
1240             if (x2 < r->x2)                                             \
1241                 x2 = r->x2;                                             \
1242         }                                                               \
1243         else                                                            \
1244         {                                                               \
1245             /* Add current rectangle, start new one */                  \
1246             NEWRECT (region, next_rect, x1, y1, x2, y2);                \
1247             x1 = r->x1;                                                 \
1248             x2 = r->x2;                                                 \
1249         }                                                               \
1250         r++;                                                            \
1251     } while (0)
1252
1253 /*======================================================================
1254  *          Region Union
1255  *====================================================================*/
1256
1257 /*-
1258  *-----------------------------------------------------------------------
1259  * pixman_region_union_o --
1260  *      Handle an overlapping band for the union operation. Picks the
1261  *      left-most rectangle each time and merges it into the region.
1262  *
1263  * Results:
1264  *      TRUE if successful.
1265  *
1266  * Side Effects:
1267  *      region is overwritten.
1268  *      overlap is set to TRUE if any boxes overlap.
1269  *
1270  *-----------------------------------------------------------------------
1271  */
1272 static pixman_bool_t
1273 pixman_region_union_o (region_type_t *region,
1274                        box_type_t *   r1,
1275                        box_type_t *   r1_end,
1276                        box_type_t *   r2,
1277                        box_type_t *   r2_end,
1278                        int            y1,
1279                        int            y2,
1280                        int *          overlap)
1281 {
1282     box_type_t *next_rect;
1283     int x1;            /* left and right side of current union */
1284     int x2;
1285
1286     critical_if_fail (y1 < y2);
1287     critical_if_fail (r1 != r1_end && r2 != r2_end);
1288
1289     next_rect = PIXREGION_TOP (region);
1290
1291     /* Start off current rectangle */
1292     if (r1->x1 < r2->x1)
1293     {
1294         x1 = r1->x1;
1295         x2 = r1->x2;
1296         r1++;
1297     }
1298     else
1299     {
1300         x1 = r2->x1;
1301         x2 = r2->x2;
1302         r2++;
1303     }
1304     while (r1 != r1_end && r2 != r2_end)
1305     {
1306         if (r1->x1 < r2->x1)
1307             MERGERECT (r1);
1308         else
1309             MERGERECT (r2);
1310     }
1311
1312     /* Finish off whoever (if any) is left */
1313     if (r1 != r1_end)
1314     {
1315         do
1316         {
1317             MERGERECT (r1);
1318         }
1319         while (r1 != r1_end);
1320     }
1321     else if (r2 != r2_end)
1322     {
1323         do
1324         {
1325             MERGERECT (r2);
1326         }
1327         while (r2 != r2_end);
1328     }
1329
1330     /* Add current rectangle */
1331     NEWRECT (region, next_rect, x1, y1, x2, y2);
1332
1333     return TRUE;
1334 }
1335
1336 PIXMAN_EXPORT pixman_bool_t
1337 PREFIX(_intersect_rect) (region_type_t *dest,
1338                          region_type_t *source,
1339                          int x, int y,
1340                          unsigned int width,
1341                          unsigned int height)
1342 {
1343     region_type_t region;
1344
1345     region.data = NULL;
1346     region.extents.x1 = x;
1347     region.extents.y1 = y;
1348     region.extents.x2 = x + width;
1349     region.extents.y2 = y + height;
1350
1351     return PREFIX(_intersect) (dest, source, &region);
1352 }
1353
1354 /* Convenience function for performing union of region with a
1355  * single rectangle
1356  */
1357 PIXMAN_EXPORT pixman_bool_t
1358 PREFIX (_union_rect) (region_type_t *dest,
1359                       region_type_t *source,
1360                       int            x,
1361                       int            y,
1362                       unsigned int   width,
1363                       unsigned int   height)
1364 {
1365     region_type_t region;
1366
1367     region.extents.x1 = x;
1368     region.extents.y1 = y;
1369     region.extents.x2 = x + width;
1370     region.extents.y2 = y + height;
1371
1372     if (!GOOD_RECT (&region.extents))
1373     {
1374         if (BAD_RECT (&region.extents))
1375             _pixman_log_error (FUNC, "Invalid rectangle passed");
1376         return PREFIX (_copy) (dest, source);
1377     }
1378
1379     region.data = NULL;
1380
1381     return PREFIX (_union) (dest, source, &region);
1382 }
1383
1384 PIXMAN_EXPORT pixman_bool_t
1385 PREFIX (_union) (region_type_t *new_reg,
1386                  region_type_t *reg1,
1387                  region_type_t *reg2)
1388 {
1389     int overlap; /* result ignored */
1390
1391     /* Return TRUE if some overlap
1392      * between reg1, reg2
1393      */
1394     GOOD (reg1);
1395     GOOD (reg2);
1396     GOOD (new_reg);
1397
1398     /*  checks all the simple cases */
1399
1400     /*
1401      * Region 1 and 2 are the same
1402      */
1403     if (reg1 == reg2)
1404         return PREFIX (_copy) (new_reg, reg1);
1405
1406     /*
1407      * Region 1 is empty
1408      */
1409     if (PIXREGION_NIL (reg1))
1410     {
1411         if (PIXREGION_NAR (reg1))
1412             return pixman_break (new_reg);
1413
1414         if (new_reg != reg2)
1415             return PREFIX (_copy) (new_reg, reg2);
1416
1417         return TRUE;
1418     }
1419
1420     /*
1421      * Region 2 is empty
1422      */
1423     if (PIXREGION_NIL (reg2))
1424     {
1425         if (PIXREGION_NAR (reg2))
1426             return pixman_break (new_reg);
1427
1428         if (new_reg != reg1)
1429             return PREFIX (_copy) (new_reg, reg1);
1430
1431         return TRUE;
1432     }
1433
1434     /*
1435      * Region 1 completely subsumes region 2
1436      */
1437     if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))
1438     {
1439         if (new_reg != reg1)
1440             return PREFIX (_copy) (new_reg, reg1);
1441
1442         return TRUE;
1443     }
1444
1445     /*
1446      * Region 2 completely subsumes region 1
1447      */
1448     if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))
1449     {
1450         if (new_reg != reg2)
1451             return PREFIX (_copy) (new_reg, reg2);
1452
1453         return TRUE;
1454     }
1455
1456     if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE, &overlap))
1457         return FALSE;
1458
1459     new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);
1460     new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);
1461     new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);
1462     new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);
1463
1464     GOOD (new_reg);
1465
1466     return TRUE;
1467 }
1468
1469 /*======================================================================
1470  *          Batch Rectangle Union
1471  *====================================================================*/
1472
1473 #define EXCHANGE_RECTS(a, b)    \
1474     {                           \
1475         box_type_t t;           \
1476         t = rects[a];           \
1477         rects[a] = rects[b];    \
1478         rects[b] = t;           \
1479     }
1480
1481 static void
1482 quick_sort_rects (
1483     box_type_t rects[],
1484     int        numRects)
1485 {
1486     int y1;
1487     int x1;
1488     int i, j;
1489     box_type_t *r;
1490
1491     /* Always called with numRects > 1 */
1492
1493     do
1494     {
1495         if (numRects == 2)
1496         {
1497             if (rects[0].y1 > rects[1].y1 ||
1498                 (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1499             {
1500                 EXCHANGE_RECTS (0, 1);
1501             }
1502
1503             return;
1504         }
1505
1506         /* Choose partition element, stick in location 0 */
1507         EXCHANGE_RECTS (0, numRects >> 1);
1508         y1 = rects[0].y1;
1509         x1 = rects[0].x1;
1510
1511         /* Partition array */
1512         i = 0;
1513         j = numRects;
1514
1515         do
1516         {
1517             r = &(rects[i]);
1518             do
1519             {
1520                 r++;
1521                 i++;
1522             }
1523
1524             while (i != numRects && (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)))
1525                 ;
1526
1527             r = &(rects[j]);
1528             do
1529             {
1530                 r--;
1531                 j--;
1532             }
1533             while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1534
1535             if (i < j)
1536                 EXCHANGE_RECTS (i, j);
1537         }
1538         while (i < j);
1539
1540         /* Move partition element back to middle */
1541         EXCHANGE_RECTS (0, j);
1542
1543         /* Recurse */
1544         if (numRects - j - 1 > 1)
1545             quick_sort_rects (&rects[j + 1], numRects - j - 1);
1546
1547         numRects = j;
1548     }
1549     while (numRects > 1);
1550 }
1551
1552 /*-
1553  *-----------------------------------------------------------------------
1554  * pixman_region_validate --
1555  *
1556  *      Take a ``region'' which is a non-y-x-banded random collection of
1557  *      rectangles, and compute a nice region which is the union of all the
1558  *      rectangles.
1559  *
1560  * Results:
1561  *      TRUE if successful.
1562  *
1563  * Side Effects:
1564  *      The passed-in ``region'' may be modified.
1565  *      overlap set to TRUE if any retangles overlapped,
1566  *      else FALSE;
1567  *
1568  * Strategy:
1569  *      Step 1. Sort the rectangles into ascending order with primary key y1
1570  *              and secondary key x1.
1571  *
1572  *      Step 2. Split the rectangles into the minimum number of proper y-x
1573  *              banded regions.  This may require horizontally merging
1574  *              rectangles, and vertically coalescing bands.  With any luck,
1575  *              this step in an identity transformation (ala the Box widget),
1576  *              or a coalescing into 1 box (ala Menus).
1577  *
1578  *      Step 3. Merge the separate regions down to a single region by calling
1579  *              pixman_region_union.  Maximize the work each pixman_region_union call does by using
1580  *              a binary merge.
1581  *
1582  *-----------------------------------------------------------------------
1583  */
1584
1585 static pixman_bool_t
1586 validate (region_type_t * badreg,
1587           int *           overlap)
1588 {
1589     /* Descriptor for regions under construction  in Step 2. */
1590     typedef struct
1591     {
1592         region_type_t reg;
1593         int prev_band;
1594         int cur_band;
1595     } region_info_t;
1596
1597     region_info_t stack_regions[64];
1598
1599     int numRects;                   /* Original numRects for badreg         */
1600     region_info_t *ri;              /* Array of current regions             */
1601     int num_ri;                     /* Number of entries used in ri         */
1602     int size_ri;                    /* Number of entries available in ri    */
1603     int i;                          /* Index into rects                     */
1604     int j;                          /* Index into ri                        */
1605     region_info_t *rit;             /* &ri[j]                               */
1606     region_type_t *reg;             /* ri[j].reg                            */
1607     box_type_t *box;                /* Current box in rects                 */
1608     box_type_t *ri_box;             /* Last box in ri[j].reg                */
1609     region_type_t *hreg;            /* ri[j_half].reg                       */
1610     pixman_bool_t ret = TRUE;
1611
1612     *overlap = FALSE;
1613     if (!badreg->data)
1614     {
1615         GOOD (badreg);
1616         return TRUE;
1617     }
1618
1619     numRects = badreg->data->numRects;
1620     if (!numRects)
1621     {
1622         if (PIXREGION_NAR (badreg))
1623             return FALSE;
1624         GOOD (badreg);
1625         return TRUE;
1626     }
1627
1628     if (badreg->extents.x1 < badreg->extents.x2)
1629     {
1630         if ((numRects) == 1)
1631         {
1632             FREE_DATA (badreg);
1633             badreg->data = (region_data_type_t *) NULL;
1634         }
1635         else
1636         {
1637             DOWNSIZE (badreg, numRects);
1638         }
1639
1640         GOOD (badreg);
1641
1642         return TRUE;
1643     }
1644
1645     /* Step 1: Sort the rects array into ascending (y1, x1) order */
1646     quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects);
1647
1648     /* Step 2: Scatter the sorted array into the minimum number of regions */
1649
1650     /* Set up the first region to be the first rectangle in badreg */
1651     /* Note that step 2 code will never overflow the ri[0].reg rects array */
1652     ri = stack_regions;
1653     size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]);
1654     num_ri = 1;
1655     ri[0].prev_band = 0;
1656     ri[0].cur_band = 0;
1657     ri[0].reg = *badreg;
1658     box = PIXREGION_BOXPTR (&ri[0].reg);
1659     ri[0].reg.extents = *box;
1660     ri[0].reg.data->numRects = 1;
1661     badreg->extents = *pixman_region_empty_box;
1662     badreg->data = pixman_region_empty_data;
1663
1664     /* Now scatter rectangles into the minimum set of valid regions.  If the
1665      * next rectangle to be added to a region would force an existing rectangle
1666      * in the region to be split up in order to maintain y-x banding, just
1667      * forget it.  Try the next region.  If it doesn't fit cleanly into any
1668      * region, make a new one.
1669      */
1670
1671     for (i = numRects; --i > 0;)
1672     {
1673         box++;
1674         /* Look for a region to append box to */
1675         for (j = num_ri, rit = ri; --j >= 0; rit++)
1676         {
1677             reg = &rit->reg;
1678             ri_box = PIXREGION_END (reg);
1679
1680             if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2)
1681             {
1682                 /* box is in same band as ri_box.  Merge or append it */
1683                 if (box->x1 <= ri_box->x2)
1684                 {
1685                     /* Merge it with ri_box */
1686                     if (box->x1 < ri_box->x2)
1687                         *overlap = TRUE;
1688
1689                     if (box->x2 > ri_box->x2)
1690                         ri_box->x2 = box->x2;
1691                 }
1692                 else
1693                 {
1694                     RECTALLOC_BAIL (reg, 1, bail);
1695                     *PIXREGION_TOP (reg) = *box;
1696                     reg->data->numRects++;
1697                 }
1698
1699                 goto next_rect;   /* So sue me */
1700             }
1701             else if (box->y1 >= ri_box->y2)
1702             {
1703                 /* Put box into new band */
1704                 if (reg->extents.x2 < ri_box->x2)
1705                     reg->extents.x2 = ri_box->x2;
1706
1707                 if (reg->extents.x1 > box->x1)
1708                     reg->extents.x1 = box->x1;
1709
1710                 COALESCE (reg, rit->prev_band, rit->cur_band);
1711                 rit->cur_band = reg->data->numRects;
1712                 RECTALLOC_BAIL (reg, 1, bail);
1713                 *PIXREGION_TOP (reg) = *box;
1714                 reg->data->numRects++;
1715
1716                 goto next_rect;
1717             }
1718             /* Well, this region was inappropriate.  Try the next one. */
1719         } /* for j */
1720
1721         /* Uh-oh.  No regions were appropriate.  Create a new one. */
1722         if (size_ri == num_ri)
1723         {
1724             size_t data_size;
1725
1726             /* Oops, allocate space for new region information */
1727             size_ri <<= 1;
1728
1729             data_size = size_ri * sizeof(region_info_t);
1730             if (data_size / size_ri != sizeof(region_info_t))
1731                 goto bail;
1732
1733             if (ri == stack_regions)
1734             {
1735                 rit = malloc (data_size);
1736                 if (!rit)
1737                     goto bail;
1738                 memcpy (rit, ri, num_ri * sizeof (region_info_t));
1739             }
1740             else
1741             {
1742                 rit = (region_info_t *) realloc (ri, data_size);
1743                 if (!rit)
1744                     goto bail;
1745             }
1746             ri = rit;
1747             rit = &ri[num_ri];
1748         }
1749         num_ri++;
1750         rit->prev_band = 0;
1751         rit->cur_band = 0;
1752         rit->reg.extents = *box;
1753         rit->reg.data = (region_data_type_t *)NULL;
1754
1755         /* MUST force allocation */
1756         if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri))
1757             goto bail;
1758
1759     next_rect: ;
1760     } /* for i */
1761
1762     /* Make a final pass over each region in order to COALESCE and set
1763      * extents.x2 and extents.y2
1764      */
1765     for (j = num_ri, rit = ri; --j >= 0; rit++)
1766     {
1767         reg = &rit->reg;
1768         ri_box = PIXREGION_END (reg);
1769         reg->extents.y2 = ri_box->y2;
1770
1771         if (reg->extents.x2 < ri_box->x2)
1772             reg->extents.x2 = ri_box->x2;
1773
1774         COALESCE (reg, rit->prev_band, rit->cur_band);
1775
1776         if (reg->data->numRects == 1) /* keep unions happy below */
1777         {
1778             FREE_DATA (reg);
1779             reg->data = (region_data_type_t *)NULL;
1780         }
1781     }
1782
1783     /* Step 3: Union all regions into a single region */
1784     while (num_ri > 1)
1785     {
1786         int half = num_ri / 2;
1787         for (j = num_ri & 1; j < (half + (num_ri & 1)); j++)
1788         {
1789             reg = &ri[j].reg;
1790             hreg = &ri[j + half].reg;
1791
1792             if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE, overlap))
1793                 ret = FALSE;
1794
1795             if (hreg->extents.x1 < reg->extents.x1)
1796                 reg->extents.x1 = hreg->extents.x1;
1797
1798             if (hreg->extents.y1 < reg->extents.y1)
1799                 reg->extents.y1 = hreg->extents.y1;
1800
1801             if (hreg->extents.x2 > reg->extents.x2)
1802                 reg->extents.x2 = hreg->extents.x2;
1803
1804             if (hreg->extents.y2 > reg->extents.y2)
1805                 reg->extents.y2 = hreg->extents.y2;
1806
1807             FREE_DATA (hreg);
1808         }
1809
1810         num_ri -= half;
1811
1812         if (!ret)
1813             goto bail;
1814     }
1815
1816     *badreg = ri[0].reg;
1817
1818     if (ri != stack_regions)
1819         free (ri);
1820
1821     GOOD (badreg);
1822     return ret;
1823
1824 bail:
1825     for (i = 0; i < num_ri; i++)
1826         FREE_DATA (&ri[i].reg);
1827
1828     if (ri != stack_regions)
1829         free (ri);
1830
1831     return pixman_break (badreg);
1832 }
1833
1834 /*======================================================================
1835  *                Region Subtraction
1836  *====================================================================*/
1837
1838 /*-
1839  *-----------------------------------------------------------------------
1840  * pixman_region_subtract_o --
1841  *      Overlapping band subtraction. x1 is the left-most point not yet
1842  *      checked.
1843  *
1844  * Results:
1845  *      TRUE if successful.
1846  *
1847  * Side Effects:
1848  *      region may have rectangles added to it.
1849  *
1850  *-----------------------------------------------------------------------
1851  */
1852 /*ARGSUSED*/
1853 static pixman_bool_t
1854 pixman_region_subtract_o (region_type_t * region,
1855                           box_type_t *    r1,
1856                           box_type_t *    r1_end,
1857                           box_type_t *    r2,
1858                           box_type_t *    r2_end,
1859                           int             y1,
1860                           int             y2,
1861                           int *           overlap)
1862 {
1863     box_type_t *        next_rect;
1864     int x1;
1865
1866     x1 = r1->x1;
1867
1868     critical_if_fail (y1 < y2);
1869     critical_if_fail (r1 != r1_end && r2 != r2_end);
1870
1871     next_rect = PIXREGION_TOP (region);
1872
1873     do
1874     {
1875         if (r2->x2 <= x1)
1876         {
1877             /*
1878              * Subtrahend entirely to left of minuend: go to next subtrahend.
1879              */
1880             r2++;
1881         }
1882         else if (r2->x1 <= x1)
1883         {
1884             /*
1885              * Subtrahend preceeds minuend: nuke left edge of minuend.
1886              */
1887             x1 = r2->x2;
1888             if (x1 >= r1->x2)
1889             {
1890                 /*
1891                  * Minuend completely covered: advance to next minuend and
1892                  * reset left fence to edge of new minuend.
1893                  */
1894                 r1++;
1895                 if (r1 != r1_end)
1896                     x1 = r1->x1;
1897             }
1898             else
1899             {
1900                 /*
1901                  * Subtrahend now used up since it doesn't extend beyond
1902                  * minuend
1903                  */
1904                 r2++;
1905             }
1906         }
1907         else if (r2->x1 < r1->x2)
1908         {
1909             /*
1910              * Left part of subtrahend covers part of minuend: add uncovered
1911              * part of minuend to region and skip to next subtrahend.
1912              */
1913             critical_if_fail (x1 < r2->x1);
1914             NEWRECT (region, next_rect, x1, y1, r2->x1, y2);
1915
1916             x1 = r2->x2;
1917             if (x1 >= r1->x2)
1918             {
1919                 /*
1920                  * Minuend used up: advance to new...
1921                  */
1922                 r1++;
1923                 if (r1 != r1_end)
1924                     x1 = r1->x1;
1925             }
1926             else
1927             {
1928                 /*
1929                  * Subtrahend used up
1930                  */
1931                 r2++;
1932             }
1933         }
1934         else
1935         {
1936             /*
1937              * Minuend used up: add any remaining piece before advancing.
1938              */
1939             if (r1->x2 > x1)
1940                 NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
1941
1942             r1++;
1943
1944             if (r1 != r1_end)
1945                 x1 = r1->x1;
1946         }
1947     }
1948     while ((r1 != r1_end) && (r2 != r2_end));
1949
1950     /*
1951      * Add remaining minuend rectangles to region.
1952      */
1953     while (r1 != r1_end)
1954     {
1955         critical_if_fail (x1 < r1->x2);
1956
1957         NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
1958
1959         r1++;
1960         if (r1 != r1_end)
1961             x1 = r1->x1;
1962     }
1963     return TRUE;
1964 }
1965
1966 /*-
1967  *-----------------------------------------------------------------------
1968  * pixman_region_subtract --
1969  *      Subtract reg_s from reg_m and leave the result in reg_d.
1970  *      S stands for subtrahend, M for minuend and D for difference.
1971  *
1972  * Results:
1973  *      TRUE if successful.
1974  *
1975  * Side Effects:
1976  *      reg_d is overwritten.
1977  *
1978  *-----------------------------------------------------------------------
1979  */
1980 PIXMAN_EXPORT pixman_bool_t
1981 PREFIX (_subtract) (region_type_t *reg_d,
1982                     region_type_t *reg_m,
1983                     region_type_t *reg_s)
1984 {
1985     int overlap; /* result ignored */
1986
1987     GOOD (reg_m);
1988     GOOD (reg_s);
1989     GOOD (reg_d);
1990
1991     /* check for trivial rejects */
1992     if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) ||
1993         !EXTENTCHECK (&reg_m->extents, &reg_s->extents))
1994     {
1995         if (PIXREGION_NAR (reg_s))
1996             return pixman_break (reg_d);
1997
1998         return PREFIX (_copy) (reg_d, reg_m);
1999     }
2000     else if (reg_m == reg_s)
2001     {
2002         FREE_DATA (reg_d);
2003         reg_d->extents.x2 = reg_d->extents.x1;
2004         reg_d->extents.y2 = reg_d->extents.y1;
2005         reg_d->data = pixman_region_empty_data;
2006
2007         return TRUE;
2008     }
2009
2010     /* Add those rectangles in region 1 that aren't in region 2,
2011        do yucky substraction for overlaps, and
2012        just throw away rectangles in region 2 that aren't in region 1 */
2013     if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE, &overlap))
2014         return FALSE;
2015
2016     /*
2017      * Can't alter reg_d's extents before we call pixman_op because
2018      * it might be one of the source regions and pixman_op depends
2019      * on the extents of those regions being unaltered. Besides, this
2020      * way there's no checking against rectangles that will be nuked
2021      * due to coalescing, so we have to examine fewer rectangles.
2022      */
2023     pixman_set_extents (reg_d);
2024     GOOD (reg_d);
2025     return TRUE;
2026 }
2027
2028 /*======================================================================
2029  *          Region Inversion
2030  *====================================================================*/
2031
2032 /*-
2033  *-----------------------------------------------------------------------
2034  * pixman_region_inverse --
2035  *      Take a region and a box and return a region that is everything
2036  *      in the box but not in the region. The careful reader will note
2037  *      that this is the same as subtracting the region from the box...
2038  *
2039  * Results:
2040  *      TRUE.
2041  *
2042  * Side Effects:
2043  *      new_reg is overwritten.
2044  *
2045  *-----------------------------------------------------------------------
2046  */
2047 pixman_bool_t
2048 PIXMAN_EXPORT PREFIX (_inverse) (region_type_t *new_reg,  /* Destination region */
2049                                  region_type_t *reg1,     /* Region to invert */
2050                                  box_type_t *   inv_rect) /* Bounding box for inversion */
2051 {
2052     region_type_t inv_reg; /* Quick and dirty region made from the
2053                             * bounding box */
2054     int overlap;           /* result ignored */
2055
2056     GOOD (reg1);
2057     GOOD (new_reg);
2058
2059     /* check for trivial rejects */
2060     if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, &reg1->extents))
2061     {
2062         if (PIXREGION_NAR (reg1))
2063             return pixman_break (new_reg);
2064
2065         new_reg->extents = *inv_rect;
2066         FREE_DATA (new_reg);
2067         new_reg->data = (region_data_type_t *)NULL;
2068
2069         return TRUE;
2070     }
2071
2072     /* Add those rectangles in region 1 that aren't in region 2,
2073      * do yucky substraction for overlaps, and
2074      * just throw away rectangles in region 2 that aren't in region 1
2075      */
2076     inv_reg.extents = *inv_rect;
2077     inv_reg.data = (region_data_type_t *)NULL;
2078     if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE, &overlap))
2079         return FALSE;
2080
2081     /*
2082      * Can't alter new_reg's extents before we call pixman_op because
2083      * it might be one of the source regions and pixman_op depends
2084      * on the extents of those regions being unaltered. Besides, this
2085      * way there's no checking against rectangles that will be nuked
2086      * due to coalescing, so we have to examine fewer rectangles.
2087      */
2088     pixman_set_extents (new_reg);
2089     GOOD (new_reg);
2090     return TRUE;
2091 }
2092
2093 /* In time O(log n), locate the first box whose y2 is greater than y.
2094  * Return @end if no such box exists.
2095  */
2096 static box_type_t *
2097 find_box_for_y (box_type_t *begin, box_type_t *end, int y)
2098 {
2099     box_type_t *mid;
2100
2101     if (end == begin)
2102         return end;
2103
2104     if (end - begin == 1)
2105     {
2106         if (begin->y2 > y)
2107             return begin;
2108         else
2109             return end;
2110     }
2111
2112     mid = begin + (end - begin) / 2;
2113     if (mid->y2 > y)
2114     {
2115         /* If no box is found in [begin, mid], the function
2116          * will return @mid, which is then known to be the
2117          * correct answer.
2118          */
2119         return find_box_for_y (begin, mid, y);
2120     }
2121     else
2122     {
2123         return find_box_for_y (mid, end, y);
2124     }
2125 }
2126
2127 /*
2128  *   rect_in(region, rect)
2129  *   This routine takes a pointer to a region and a pointer to a box
2130  *   and determines if the box is outside/inside/partly inside the region.
2131  *
2132  *   The idea is to travel through the list of rectangles trying to cover the
2133  *   passed box with them. Anytime a piece of the rectangle isn't covered
2134  *   by a band of rectangles, part_out is set TRUE. Any time a rectangle in
2135  *   the region covers part of the box, part_in is set TRUE. The process ends
2136  *   when either the box has been completely covered (we reached a band that
2137  *   doesn't overlap the box, part_in is TRUE and part_out is false), the
2138  *   box has been partially covered (part_in == part_out == TRUE -- because of
2139  *   the banding, the first time this is true we know the box is only
2140  *   partially in the region) or is outside the region (we reached a band
2141  *   that doesn't overlap the box at all and part_in is false)
2142  */
2143 pixman_region_overlap_t
2144 PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t *  region,
2145                                             box_type_t *     prect)
2146 {
2147     box_type_t *     pbox;
2148     box_type_t *     pbox_end;
2149     int part_in, part_out;
2150     int numRects;
2151     int x, y;
2152
2153     GOOD (region);
2154
2155     numRects = PIXREGION_NUMRECTS (region);
2156
2157     /* useful optimization */
2158     if (!numRects || !EXTENTCHECK (&region->extents, prect))
2159         return(PIXMAN_REGION_OUT);
2160
2161     if (numRects == 1)
2162     {
2163         /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
2164         if (SUBSUMES (&region->extents, prect))
2165             return(PIXMAN_REGION_IN);
2166         else
2167             return(PIXMAN_REGION_PART);
2168     }
2169
2170     part_out = FALSE;
2171     part_in = FALSE;
2172
2173     /* (x,y) starts at upper left of rect, moving to the right and down */
2174     x = prect->x1;
2175     y = prect->y1;
2176
2177     /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */
2178     for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
2179          pbox != pbox_end;
2180          pbox++)
2181     {
2182         /* getting up to speed or skipping remainder of band */
2183         if (pbox->y2 <= y)
2184         {
2185             if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end)
2186                 break;
2187         }
2188
2189         if (pbox->y1 > y)
2190         {
2191             part_out = TRUE;     /* missed part of rectangle above */
2192             if (part_in || (pbox->y1 >= prect->y2))
2193                 break;
2194             y = pbox->y1;       /* x guaranteed to be == prect->x1 */
2195         }
2196
2197         if (pbox->x2 <= x)
2198             continue;           /* not far enough over yet */
2199
2200         if (pbox->x1 > x)
2201         {
2202             part_out = TRUE;     /* missed part of rectangle to left */
2203             if (part_in)
2204                 break;
2205         }
2206
2207         if (pbox->x1 < prect->x2)
2208         {
2209             part_in = TRUE;      /* definitely overlap */
2210             if (part_out)
2211                 break;
2212         }
2213
2214         if (pbox->x2 >= prect->x2)
2215         {
2216             y = pbox->y2;       /* finished with this band */
2217             if (y >= prect->y2)
2218                 break;
2219             x = prect->x1;      /* reset x out to left again */
2220         }
2221         else
2222         {
2223             /*
2224              * Because boxes in a band are maximal width, if the first box
2225              * to overlap the rectangle doesn't completely cover it in that
2226              * band, the rectangle must be partially out, since some of it
2227              * will be uncovered in that band. part_in will have been set true
2228              * by now...
2229              */
2230             part_out = TRUE;
2231             break;
2232         }
2233     }
2234
2235     if (part_in)
2236     {
2237         if (y < prect->y2)
2238             return PIXMAN_REGION_PART;
2239         else
2240             return PIXMAN_REGION_IN;
2241     }
2242     else
2243     {
2244         return PIXMAN_REGION_OUT;
2245     }
2246 }
2247
2248 /* PREFIX(_translate) (region, x, y)
2249  * translates in place
2250  */
2251
2252 PIXMAN_EXPORT void
2253 PREFIX (_translate) (region_type_t *region, int x, int y)
2254 {
2255     overflow_int_t x1, x2, y1, y2;
2256     int nbox;
2257     box_type_t * pbox;
2258
2259     GOOD (region);
2260     region->extents.x1 = x1 = region->extents.x1 + x;
2261     region->extents.y1 = y1 = region->extents.y1 + y;
2262     region->extents.x2 = x2 = region->extents.x2 + x;
2263     region->extents.y2 = y2 = region->extents.y2 + y;
2264
2265     if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0)
2266     {
2267         if (region->data && (nbox = region->data->numRects))
2268         {
2269             for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
2270             {
2271                 pbox->x1 += x;
2272                 pbox->y1 += y;
2273                 pbox->x2 += x;
2274                 pbox->y2 += y;
2275             }
2276         }
2277         return;
2278     }
2279
2280     if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
2281     {
2282         region->extents.x2 = region->extents.x1;
2283         region->extents.y2 = region->extents.y1;
2284         FREE_DATA (region);
2285         region->data = pixman_region_empty_data;
2286         return;
2287     }
2288
2289     if (x1 < PIXMAN_REGION_MIN)
2290         region->extents.x1 = PIXMAN_REGION_MIN;
2291     else if (x2 > PIXMAN_REGION_MAX)
2292         region->extents.x2 = PIXMAN_REGION_MAX;
2293
2294     if (y1 < PIXMAN_REGION_MIN)
2295         region->extents.y1 = PIXMAN_REGION_MIN;
2296     else if (y2 > PIXMAN_REGION_MAX)
2297         region->extents.y2 = PIXMAN_REGION_MAX;
2298
2299     if (region->data && (nbox = region->data->numRects))
2300     {
2301         box_type_t * pbox_out;
2302
2303         for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
2304         {
2305             pbox_out->x1 = x1 = pbox->x1 + x;
2306             pbox_out->y1 = y1 = pbox->y1 + y;
2307             pbox_out->x2 = x2 = pbox->x2 + x;
2308             pbox_out->y2 = y2 = pbox->y2 + y;
2309
2310             if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) |
2311                  (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
2312             {
2313                 region->data->numRects--;
2314                 continue;
2315             }
2316
2317             if (x1 < PIXMAN_REGION_MIN)
2318                 pbox_out->x1 = PIXMAN_REGION_MIN;
2319             else if (x2 > PIXMAN_REGION_MAX)
2320                 pbox_out->x2 = PIXMAN_REGION_MAX;
2321
2322             if (y1 < PIXMAN_REGION_MIN)
2323                 pbox_out->y1 = PIXMAN_REGION_MIN;
2324             else if (y2 > PIXMAN_REGION_MAX)
2325                 pbox_out->y2 = PIXMAN_REGION_MAX;
2326
2327             pbox_out++;
2328         }
2329
2330         if (pbox_out != pbox)
2331         {
2332             if (region->data->numRects == 1)
2333             {
2334                 region->extents = *PIXREGION_BOXPTR (region);
2335                 FREE_DATA (region);
2336                 region->data = (region_data_type_t *)NULL;
2337             }
2338             else
2339             {
2340                 pixman_set_extents (region);
2341             }
2342         }
2343     }
2344
2345     GOOD (region);
2346 }
2347
2348 PIXMAN_EXPORT void
2349 PREFIX (_reset) (region_type_t *region, box_type_t *box)
2350 {
2351     GOOD (region);
2352
2353     critical_if_fail (GOOD_RECT (box));
2354
2355     region->extents = *box;
2356
2357     FREE_DATA (region);
2358
2359     region->data = NULL;
2360 }
2361
2362 /* box is "return" value */
2363 PIXMAN_EXPORT int
2364 PREFIX (_contains_point) (region_type_t * region,
2365                           int x, int y,
2366                           box_type_t * box)
2367 {
2368     box_type_t *pbox, *pbox_end;
2369     int numRects;
2370
2371     GOOD (region);
2372     numRects = PIXREGION_NUMRECTS (region);
2373
2374     if (!numRects || !INBOX (&region->extents, x, y))
2375         return(FALSE);
2376
2377     if (numRects == 1)
2378     {
2379         if (box)
2380             *box = region->extents;
2381
2382         return(TRUE);
2383     }
2384
2385     pbox = PIXREGION_BOXPTR (region);
2386     pbox_end = pbox + numRects;
2387
2388     pbox = find_box_for_y (pbox, pbox_end, y);
2389
2390     for (;pbox != pbox_end; pbox++)
2391     {
2392         if ((y < pbox->y1) || (x < pbox->x1))
2393             break;              /* missed it */
2394
2395         if (x >= pbox->x2)
2396             continue;           /* not there yet */
2397
2398         if (box)
2399             *box = *pbox;
2400
2401         return(TRUE);
2402     }
2403
2404     return(FALSE);
2405 }
2406
2407 PIXMAN_EXPORT int
2408 PREFIX (_not_empty) (region_type_t * region)
2409 {
2410     GOOD (region);
2411
2412     return(!PIXREGION_NIL (region));
2413 }
2414
2415 PIXMAN_EXPORT box_type_t *
2416 PREFIX (_extents) (region_type_t * region)
2417 {
2418     GOOD (region);
2419
2420     return(&region->extents);
2421 }
2422
2423 /*
2424  * Clip a list of scanlines to a region.  The caller has allocated the
2425  * space.  FSorted is non-zero if the scanline origins are in ascending order.
2426  *
2427  * returns the number of new, clipped scanlines.
2428  */
2429
2430 PIXMAN_EXPORT pixman_bool_t
2431 PREFIX (_selfcheck) (region_type_t *reg)
2432 {
2433     int i, numRects;
2434
2435     if ((reg->extents.x1 > reg->extents.x2) ||
2436         (reg->extents.y1 > reg->extents.y2))
2437     {
2438         return FALSE;
2439     }
2440
2441     numRects = PIXREGION_NUMRECTS (reg);
2442     if (!numRects)
2443     {
2444         return ((reg->extents.x1 == reg->extents.x2) &&
2445                 (reg->extents.y1 == reg->extents.y2) &&
2446                 (reg->data->size || (reg->data == pixman_region_empty_data)));
2447     }
2448     else if (numRects == 1)
2449     {
2450         return (!reg->data);
2451     }
2452     else
2453     {
2454         box_type_t * pbox_p, * pbox_n;
2455         box_type_t box;
2456
2457         pbox_p = PIXREGION_RECTS (reg);
2458         box = *pbox_p;
2459         box.y2 = pbox_p[numRects - 1].y2;
2460         pbox_n = pbox_p + 1;
2461
2462         for (i = numRects; --i > 0; pbox_p++, pbox_n++)
2463         {
2464             if ((pbox_n->x1 >= pbox_n->x2) ||
2465                 (pbox_n->y1 >= pbox_n->y2))
2466             {
2467                 return FALSE;
2468             }
2469
2470             if (pbox_n->x1 < box.x1)
2471                 box.x1 = pbox_n->x1;
2472
2473             if (pbox_n->x2 > box.x2)
2474                 box.x2 = pbox_n->x2;
2475
2476             if ((pbox_n->y1 < pbox_p->y1) ||
2477                 ((pbox_n->y1 == pbox_p->y1) &&
2478                  ((pbox_n->x1 < pbox_p->x2) || (pbox_n->y2 != pbox_p->y2))))
2479             {
2480                 return FALSE;
2481             }
2482         }
2483
2484         return ((box.x1 == reg->extents.x1) &&
2485                 (box.x2 == reg->extents.x2) &&
2486                 (box.y1 == reg->extents.y1) &&
2487                 (box.y2 == reg->extents.y2));
2488     }
2489 }
2490
2491 PIXMAN_EXPORT pixman_bool_t
2492 PREFIX (_init_rects) (region_type_t *region,
2493                       const box_type_t *boxes, int count)
2494 {
2495     box_type_t *rects;
2496     int displacement;
2497     int i;
2498
2499     /* if it's 1, then we just want to set the extents, so call
2500      * the existing method. */
2501     if (count == 1)
2502     {
2503         PREFIX (_init_rect) (region,
2504                              boxes[0].x1,
2505                              boxes[0].y1,
2506                              boxes[0].x2 - boxes[0].x1,
2507                              boxes[0].y2 - boxes[0].y1);
2508         return TRUE;
2509     }
2510
2511     PREFIX (_init) (region);
2512
2513     /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
2514      * a special case, and causing pixman_rect_alloc would cause
2515      * us to leak memory (because the 0-rect case should be the
2516      * static pixman_region_empty_data data).
2517      */
2518     if (count == 0)
2519         return TRUE;
2520
2521     if (!pixman_rect_alloc (region, count))
2522         return FALSE;
2523
2524     rects = PIXREGION_RECTS (region);
2525
2526     /* Copy in the rects */
2527     memcpy (rects, boxes, sizeof(box_type_t) * count);
2528     region->data->numRects = count;
2529
2530     /* Eliminate empty and malformed rectangles */
2531     displacement = 0;
2532
2533     for (i = 0; i < count; ++i)
2534     {
2535         box_type_t *box = &rects[i];
2536
2537         if (box->x1 >= box->x2 || box->y1 >= box->y2)
2538             displacement++;
2539         else if (displacement)
2540             rects[i - displacement] = rects[i];
2541     }
2542
2543     region->data->numRects -= displacement;
2544
2545     /* If eliminating empty rectangles caused there
2546      * to be only 0 or 1 rectangles, deal with that.
2547      */
2548     if (region->data->numRects == 0)
2549     {
2550         FREE_DATA (region);
2551         PREFIX (_init) (region);
2552
2553         return TRUE;
2554     }
2555
2556     if (region->data->numRects == 1)
2557     {
2558         region->extents = rects[0];
2559
2560         FREE_DATA (region);
2561         region->data = NULL;
2562
2563         GOOD (region);
2564
2565         return TRUE;
2566     }
2567
2568     /* Validate */
2569     region->extents.x1 = region->extents.x2 = 0;
2570
2571     return validate (region, &i);
2572 }
2573
2574 #define READ(_ptr) (*(_ptr))
2575
2576 static inline box_type_t *
2577 bitmap_addrect (region_type_t *reg,
2578                 box_type_t *r,
2579                 box_type_t **first_rect,
2580                 int rx1, int ry1,
2581                 int rx2, int ry2)
2582 {
2583     if ((rx1 < rx2) && (ry1 < ry2) &&
2584         (!(reg->data->numRects &&
2585            ((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) &&
2586            ((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2))))
2587     {
2588         if (reg->data->numRects == reg->data->size)
2589         {
2590             if (!pixman_rect_alloc (reg, 1))
2591                 return NULL;
2592             *first_rect = PIXREGION_BOXPTR(reg);
2593             r = *first_rect + reg->data->numRects;
2594         }
2595         r->x1 = rx1;
2596         r->y1 = ry1;
2597         r->x2 = rx2;
2598         r->y2 = ry2;
2599         reg->data->numRects++;
2600         if (r->x1 < reg->extents.x1)
2601             reg->extents.x1 = r->x1;
2602         if (r->x2 > reg->extents.x2)
2603             reg->extents.x2 = r->x2;
2604         r++;
2605     }
2606     return r;
2607 }
2608
2609 /* Convert bitmap clip mask into clipping region.
2610  * First, goes through each line and makes boxes by noting the transitions
2611  * from 0 to 1 and 1 to 0.
2612  * Then it coalesces the current line with the previous if they have boxes
2613  * at the same X coordinates.
2614  * Stride is in number of uint32_t per line.
2615  */
2616 PIXMAN_EXPORT void
2617 PREFIX (_init_from_image) (region_type_t *region,
2618                            pixman_image_t *image)
2619 {
2620     uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1);
2621     box_type_t *first_rect, *rects, *prect_line_start;
2622     box_type_t *old_rect, *new_rect;
2623     uint32_t *pw, w, *pw_line, *pw_line_end;
2624     int irect_prev_start, irect_line_start;
2625     int h, base, rx1 = 0, crects;
2626     int ib;
2627     pixman_bool_t in_box, same;
2628     int width, height, stride;
2629
2630     PREFIX(_init) (region);
2631
2632     critical_if_fail (region->data);
2633
2634     return_if_fail (image->type == BITS);
2635     return_if_fail (image->bits.format == PIXMAN_a1);
2636
2637     pw_line = pixman_image_get_data (image);
2638     width = pixman_image_get_width (image);
2639     height = pixman_image_get_height (image);
2640     stride = pixman_image_get_stride (image) / 4;
2641
2642     first_rect = PIXREGION_BOXPTR(region);
2643     rects = first_rect;
2644
2645     region->extents.x1 = width - 1;
2646     region->extents.x2 = 0;
2647     irect_prev_start = -1;
2648     for (h = 0; h < height; h++)
2649     {
2650         pw = pw_line;
2651         pw_line += stride;
2652         irect_line_start = rects - first_rect;
2653
2654         /* If the Screen left most bit of the word is set, we're starting in
2655          * a box */
2656         if (READ(pw) & mask0)
2657         {
2658             in_box = TRUE;
2659             rx1 = 0;
2660         }
2661         else
2662         {
2663             in_box = FALSE;
2664         }
2665
2666         /* Process all words which are fully in the pixmap */
2667         pw_line_end = pw + (width >> 5);
2668         for (base = 0; pw < pw_line_end; base += 32)
2669         {
2670             w = READ(pw++);
2671             if (in_box)
2672             {
2673                 if (!~w)
2674                     continue;
2675             }
2676             else
2677             {
2678                 if (!w)
2679                     continue;
2680             }
2681             for (ib = 0; ib < 32; ib++)
2682             {
2683                 /* If the Screen left most bit of the word is set, we're
2684                  * starting a box */
2685                 if (w & mask0)
2686                 {
2687                     if (!in_box)
2688                     {
2689                         rx1 = base + ib;
2690                         /* start new box */
2691                         in_box = TRUE;
2692                     }
2693                 }
2694                 else
2695                 {
2696                     if (in_box)
2697                     {
2698                         /* end box */
2699                         rects = bitmap_addrect (region, rects, &first_rect,
2700                                                 rx1, h, base + ib, h + 1);
2701                         if (rects == NULL)
2702                             goto error;
2703                         in_box = FALSE;
2704                     }
2705                 }
2706                 /* Shift the word VISUALLY left one. */
2707                 w = SCREEN_SHIFT_LEFT(w, 1);
2708             }
2709         }
2710
2711         if (width & 31)
2712         {
2713             /* Process final partial word on line */
2714              w = READ(pw++);
2715             for (ib = 0; ib < (width & 31); ib++)
2716             {
2717                 /* If the Screen left most bit of the word is set, we're
2718                  * starting a box */
2719                 if (w & mask0)
2720                 {
2721                     if (!in_box)
2722                     {
2723                         rx1 = base + ib;
2724                         /* start new box */
2725                         in_box = TRUE;
2726                     }
2727                 }
2728                 else
2729                 {
2730                     if (in_box)
2731                     {
2732                         /* end box */
2733                         rects = bitmap_addrect(region, rects, &first_rect,
2734                                                rx1, h, base + ib, h + 1);
2735                         if (rects == NULL)
2736                             goto error;
2737                         in_box = FALSE;
2738                     }
2739                 }
2740                 /* Shift the word VISUALLY left one. */
2741                 w = SCREEN_SHIFT_LEFT(w, 1);
2742             }
2743         }
2744         /* If scanline ended with last bit set, end the box */
2745         if (in_box)
2746         {
2747             rects = bitmap_addrect(region, rects, &first_rect,
2748                                    rx1, h, base + (width & 31), h + 1);
2749             if (rects == NULL)
2750                 goto error;
2751         }
2752         /* if all rectangles on this line have the same x-coords as
2753          * those on the previous line, then add 1 to all the previous  y2s and
2754          * throw away all the rectangles from this line
2755          */
2756         same = FALSE;
2757         if (irect_prev_start != -1)
2758         {
2759             crects = irect_line_start - irect_prev_start;
2760             if (crects != 0 &&
2761                 crects == ((rects - first_rect) - irect_line_start))
2762             {
2763                 old_rect = first_rect + irect_prev_start;
2764                 new_rect = prect_line_start = first_rect + irect_line_start;
2765                 same = TRUE;
2766                 while (old_rect < prect_line_start)
2767                 {
2768                     if ((old_rect->x1 != new_rect->x1) ||
2769                         (old_rect->x2 != new_rect->x2))
2770                     {
2771                           same = FALSE;
2772                           break;
2773                     }
2774                     old_rect++;
2775                     new_rect++;
2776                 }
2777                 if (same)
2778                 {
2779                     old_rect = first_rect + irect_prev_start;
2780                     while (old_rect < prect_line_start)
2781                     {
2782                         old_rect->y2 += 1;
2783                         old_rect++;
2784                     }
2785                     rects -= crects;
2786                     region->data->numRects -= crects;
2787                 }
2788             }
2789         }
2790         if(!same)
2791             irect_prev_start = irect_line_start;
2792     }
2793     if (!region->data->numRects)
2794     {
2795         region->extents.x1 = region->extents.x2 = 0;
2796     }
2797     else
2798     {
2799         region->extents.y1 = PIXREGION_BOXPTR(region)->y1;
2800         region->extents.y2 = PIXREGION_END(region)->y2;
2801         if (region->data->numRects == 1)
2802         {
2803             free (region->data);
2804             region->data = NULL;
2805         }
2806     }
2807
2808  error:
2809     return;
2810 }