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