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