pixman/pixman-region.c

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