1 /* 2 * ReactOS W32 Subsystem 3 * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 ReactOS Team 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License as published by 7 * the Free Software Foundation; either version 2 of the License, or 8 * (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License along 16 * with this program; if not, write to the Free Software Foundation, Inc., 17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 */ 19 20 /* 21 * GDI region objects. Shamelessly ripped out from the X11 distribution 22 * Thanks for the nice licence. 23 * 24 * Copyright 1993, 1994, 1995 Alexandre Julliard 25 * Modifications and additions: Copyright 1998 Huw Davies 26 * 1999 Alex Korobka 27 * 28 * This library is free software; you can redistribute it and/or 29 * modify it under the terms of the GNU Lesser General Public 30 * License as published by the Free Software Foundation; either 31 * version 2.1 of the License, or (at your option) any later version. 32 * 33 * This library is distributed in the hope that it will be useful, 34 * but WITHOUT ANY WARRANTY; without even the implied warranty of 35 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 36 * Lesser General Public License for more details. 37 * 38 * You should have received a copy of the GNU Lesser General Public 39 * License along with this library; if not, write to the Free Software 40 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 41 */ 42 43 /************************************************************************ 44 45 Copyright (c) 1987, 1988 X Consortium 46 47 Permission is hereby granted, free of charge, to any person obtaining a copy 48 of this software and associated documentation files (the "Software"), to deal 49 in the Software without restriction, including without limitation the rights 50 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 51 copies of the Software, and to permit persons to whom the Software is 52 furnished to do so, subject to the following conditions: 53 54 The above copyright notice and this permission notice shall be included in 55 all copies or substantial portions of the Software. 56 57 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 58 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 59 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 60 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 61 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 62 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 63 64 Except as contained in this notice, the name of the X Consortium shall not be 65 used in advertising or otherwise to promote the sale, use or other dealings 66 in this Software without prior written authorization from the X Consortium. 67 68 69 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts. 70 71 All Rights Reserved 72 73 Permission to use, copy, modify, and distribute this software and its 74 documentation for any purpose and without fee is hereby granted, 75 provided that the above copyright notice appear in all copies and that 76 both that copyright notice and this permission notice appear in 77 supporting documentation, and that the name of Digital not be 78 used in advertising or publicity pertaining to distribution of the 79 software without specific, written prior permission. 80 81 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING 82 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL 83 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR 84 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, 85 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 86 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS 87 SOFTWARE. 88 89 ************************************************************************/ 90 /* 91 * The functions in this file implement the Region abstraction, similar to one 92 * used in the X11 sample server. A Region is simply an area, as the name 93 * implies, and is implemented as a "y-x-banded" array of rectangles. To 94 * explain: Each Region is made up of a certain number of rectangles sorted 95 * by y coordinate first, and then by x coordinate. 96 * 97 * Furthermore, the rectangles are banded such that every rectangle with a 98 * given upper-left y coordinate (y1) will have the same lower-right y 99 * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it 100 * will span the entire vertical distance of the band. This means that some 101 * areas that could be merged into a taller rectangle will be represented as 102 * several shorter rectangles to account for shorter rectangles to its left 103 * or right but within its "vertical scope". 104 * 105 * An added constraint on the rectangles is that they must cover as much 106 * horizontal area as possible. E.g. no two rectangles in a band are allowed 107 * to touch. 108 * 109 * Whenever possible, bands will be merged together to cover a greater vertical 110 * distance (and thus reduce the number of rectangles). Two bands can be merged 111 * only if the bottom of one touches the top of the other and they have 112 * rectangles in the same places (of the same width, of course). This maintains 113 * the y-x-banding that's so nice to have... 114 */ 115 116 // X11 sources for ReactOS region processing. 117 // 118 // libX11/src/PolyReg.c 119 // libX11/src/Region.c 120 // 121 // 122 123 124 #include <win32k.h> 125 #include <suppress.h> 126 127 #define NDEBUG 128 #include <debug.h> 129 130 PREGION prgnDefault = NULL; 131 HRGN hrgnDefault = NULL; 132 133 // Internal Functions 134 135 #if 1 136 #define COPY_RECTS(dest, src, nRects) \ 137 do { \ 138 PRECTL xDest = (dest); \ 139 PRECTL xSrc = (src); \ 140 UINT xRects = (nRects); \ 141 while (xRects-- > 0) { \ 142 *(xDest++) = *(xSrc++); \ 143 } \ 144 } while (0) 145 #else 146 #define COPY_RECTS(dest, src, nRects) RtlCopyMemory(dest, src, (nRects) * sizeof(RECTL)) 147 #endif 148 149 #define EMPTY_REGION(pReg) { \ 150 (pReg)->rdh.nCount = 0; \ 151 (pReg)->rdh.rcBound.left = (pReg)->rdh.rcBound.top = 0; \ 152 (pReg)->rdh.rcBound.right = (pReg)->rdh.rcBound.bottom = 0; \ 153 (pReg)->rdh.iType = RDH_RECTANGLES; \ 154 } 155 156 #define REGION_NOT_EMPTY(pReg) pReg->rdh.nCount 157 158 #define INRECT(r, x, y) \ 159 ( ( ((r).right > x)) && \ 160 ( ((r).left <= x)) && \ 161 ( ((r).bottom > y)) && \ 162 ( ((r).top <= y)) ) 163 164 /* 1 if two RECTs overlap. 165 * 0 if two RECTs do not overlap. 166 */ 167 #define EXTENTCHECK(r1, r2) \ 168 ((r1)->right > (r2)->left && \ 169 (r1)->left < (r2)->right && \ 170 (r1)->bottom > (r2)->top && \ 171 (r1)->top < (r2)->bottom) 172 173 /* 174 * In scan converting polygons, we want to choose those pixels 175 * which are inside the polygon. Thus, we add .5 to the starting 176 * x coordinate for both left and right edges. Now we choose the 177 * first pixel which is inside the pgon for the left edge and the 178 * first pixel which is outside the pgon for the right edge. 179 * Draw the left pixel, but not the right. 180 * 181 * How to add .5 to the starting x coordinate: 182 * If the edge is moving to the right, then subtract dy from the 183 * error term from the general form of the algorithm. 184 * If the edge is moving to the left, then add dy to the error term. 185 * 186 * The reason for the difference between edges moving to the left 187 * and edges moving to the right is simple: If an edge is moving 188 * to the right, then we want the algorithm to flip immediately. 189 * If it is moving to the left, then we don't want it to flip until 190 * we traverse an entire pixel. 191 */ 192 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \ 193 int dx; /* Local storage */ \ 194 \ 195 /* \ 196 * If the edge is horizontal, then it is ignored \ 197 * and assumed not to be processed. Otherwise, do this stuff. \ 198 */ \ 199 if ((dy) != 0) { \ 200 xStart = (x1); \ 201 dx = (x2) - xStart; \ 202 if (dx < 0) { \ 203 m = dx / (dy); \ 204 m1 = m - 1; \ 205 incr1 = -2 * dx + 2 * (dy) * m1; \ 206 incr2 = -2 * dx + 2 * (dy) * m; \ 207 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \ 208 } else { \ 209 m = dx / (dy); \ 210 m1 = m + 1; \ 211 incr1 = 2 * dx - 2 * (dy) * m1; \ 212 incr2 = 2 * dx - 2 * (dy) * m; \ 213 d = -2 * m * (dy) + 2 * dx; \ 214 } \ 215 } \ 216 } 217 218 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \ 219 if (m1 > 0) { \ 220 if (d > 0) { \ 221 minval += m1; \ 222 d += incr1; \ 223 } \ 224 else { \ 225 minval += m; \ 226 d += incr2; \ 227 } \ 228 } else {\ 229 if (d >= 0) { \ 230 minval += m1; \ 231 d += incr1; \ 232 } \ 233 else { \ 234 minval += m; \ 235 d += incr2; \ 236 } \ 237 } \ 238 } 239 240 /* 241 * This structure contains all of the information needed 242 * to run the bresenham algorithm. 243 * The variables may be hardcoded into the declarations 244 * instead of using this structure to make use of 245 * register declarations. 246 */ 247 typedef struct 248 { 249 INT minor_axis; /* Minor axis */ 250 INT d; /* Decision variable */ 251 INT m, m1; /* Slope and slope+1 */ 252 INT incr1, incr2; /* Error increments */ 253 } BRESINFO; 254 255 256 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \ 257 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \ 258 bres.m, bres.m1, bres.incr1, bres.incr2) 259 260 #define BRESINCRPGONSTRUCT(bres) \ 261 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2) 262 263 264 265 /* 266 * These are the data structures needed to scan 267 * convert regions. Two different scan conversion 268 * methods are available -- the even-odd method, and 269 * the winding number method. 270 * The even-odd rule states that a point is inside 271 * the polygon if a ray drawn from that point in any 272 * direction will pass through an odd number of 273 * path segments. 274 * By the winding number rule, a point is decided 275 * to be inside the polygon if a ray drawn from that 276 * point in any direction passes through a different 277 * number of clockwise and counter-clockwise path 278 * segments. 279 * 280 * These data structures are adapted somewhat from 281 * the algorithm in (Foley/Van Dam) for scan converting 282 * polygons. 283 * The basic algorithm is to start at the top (smallest y) 284 * of the polygon, stepping down to the bottom of 285 * the polygon by incrementing the y coordinate. We 286 * keep a list of edges which the current scanline crosses, 287 * sorted by x. This list is called the Active Edge Table (AET) 288 * As we change the y-coordinate, we update each entry in 289 * in the active edge table to reflect the edges new xcoord. 290 * This list must be sorted at each scanline in case 291 * two edges intersect. 292 * We also keep a data structure known as the Edge Table (ET), 293 * which keeps track of all the edges which the current 294 * scanline has not yet reached. The ET is basically a 295 * list of SCANLINE_LIST structures containing a list of 296 * edges which are entered at a given scanline. There is one 297 * SCANLINE_LIST per scanline at which an edge is entered. 298 * When we enter a new edge, we move it from the ET to the AET. 299 * 300 * From the AET, we can implement the even-odd rule as in 301 * (Foley/Van Dam). 302 * The winding number rule is a little trickier. We also 303 * keep the EDGE_TABLEEntries in the AET linked by the 304 * nextWETE (winding EDGE_TABLE_ENTRY) link. This allows 305 * the edges to be linked just as before for updating 306 * purposes, but only uses the edges linked by the nextWETE 307 * link as edges representing spans of the polygon to 308 * drawn (as with the even-odd rule). 309 */ 310 311 /* 312 * For the winding number rule 313 */ 314 #define CLOCKWISE 1 315 #define COUNTERCLOCKWISE -1 316 317 typedef struct _EDGE_TABLE_ENTRY 318 { 319 INT ymax; /* ycoord at which we exit this edge. */ 320 BRESINFO bres; /* Bresenham info to run the edge */ 321 struct _EDGE_TABLE_ENTRY *next; /* Next in the list */ 322 struct _EDGE_TABLE_ENTRY *back; /* For insertion sort */ 323 struct _EDGE_TABLE_ENTRY *nextWETE; /* For winding num rule */ 324 INT ClockWise; /* Flag for winding number rule */ 325 } EDGE_TABLE_ENTRY; 326 327 328 typedef struct _SCANLINE_LIST 329 { 330 INT scanline; /* The scanline represented */ 331 EDGE_TABLE_ENTRY *edgelist; /* Header node */ 332 struct _SCANLINE_LIST *next; /* Next in the list */ 333 } SCANLINE_LIST; 334 335 336 typedef struct 337 { 338 INT ymax; /* ymax for the polygon */ 339 INT ymin; /* ymin for the polygon */ 340 SCANLINE_LIST scanlines; /* Header node */ 341 } EDGE_TABLE; 342 343 344 /* 345 * Here is a struct to help with storage allocation 346 * so we can allocate a big chunk at a time, and then take 347 * pieces from this heap when we need to. 348 */ 349 #define SLLSPERBLOCK 25 350 351 typedef struct _SCANLINE_LISTBLOCK 352 { 353 SCANLINE_LIST SLLs[SLLSPERBLOCK]; 354 struct _SCANLINE_LISTBLOCK *next; 355 } SCANLINE_LISTBLOCK; 356 357 358 /* 359 * A few macros for the inner loops of the fill code where 360 * performance considerations don't allow a procedure call. 361 * 362 * Evaluate the given edge at the given scanline. 363 * If the edge has expired, then we leave it and fix up 364 * the active edge table; otherwise, we increment the 365 * x value to be ready for the next scanline. 366 * The winding number rule is in effect, so we must notify 367 * the caller when the edge has been removed so he 368 * can reorder the Winding Active Edge Table. 369 */ 370 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \ 371 if (pAET->ymax == y) { /* Leaving this edge */ \ 372 pPrevAET->next = pAET->next; \ 373 pAET = pPrevAET->next; \ 374 fixWAET = 1; \ 375 if (pAET) \ 376 pAET->back = pPrevAET; \ 377 } \ 378 else { \ 379 BRESINCRPGONSTRUCT(pAET->bres); \ 380 pPrevAET = pAET; \ 381 pAET = pAET->next; \ 382 } \ 383 } 384 385 386 /* 387 * Evaluate the given edge at the given scanline. 388 * If the edge has expired, then we leave it and fix up 389 * the active edge table; otherwise, we increment the 390 * x value to be ready for the next scanline. 391 * The even-odd rule is in effect. 392 */ 393 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \ 394 if (pAET->ymax == y) { /* Leaving this edge */ \ 395 pPrevAET->next = pAET->next; \ 396 pAET = pPrevAET->next; \ 397 if (pAET) \ 398 pAET->back = pPrevAET; \ 399 } \ 400 else { \ 401 BRESINCRPGONSTRUCT(pAET->bres); \ 402 pPrevAET = pAET; \ 403 pAET = pAET->next; \ 404 } \ 405 } 406 407 /************************************************************************** 408 * 409 * Poly Regions 410 * 411 *************************************************************************/ 412 413 #define LARGE_COORDINATE INT_MAX 414 #define SMALL_COORDINATE INT_MIN 415 416 static 417 BOOL 418 REGION_bGrowBufferSize( 419 _Inout_ PREGION prgn, 420 _In_ UINT cRects) 421 { 422 ULONG cjNewSize; 423 PVOID pvBuffer; 424 NT_ASSERT(cRects > 0); 425 426 /* Make sure we don't overflow */ 427 if (cRects > MAXULONG / sizeof(RECTL)) 428 { 429 return FALSE; 430 } 431 432 /* Calculate new buffer size */ 433 cjNewSize = cRects * sizeof(RECTL); 434 435 /* Avoid allocating too often, by duplicating the old buffer size 436 Note: we don't do an overflow check, since the old size will never 437 get that large before running out of memory. */ 438 if (2 * prgn->rdh.nRgnSize > cjNewSize) 439 { 440 cjNewSize = 2 * prgn->rdh.nRgnSize; 441 } 442 443 /* Allocate the new buffer */ 444 pvBuffer = ExAllocatePoolWithTag(PagedPool, cjNewSize, TAG_REGION); 445 if (pvBuffer == NULL) 446 { 447 return FALSE; 448 } 449 450 /* Copy the rects into the new buffer */ 451 COPY_RECTS(pvBuffer, prgn->Buffer, prgn->rdh.nCount); 452 453 /* Free the old buffer */ 454 if (prgn->Buffer != &prgn->rdh.rcBound) 455 { 456 ExFreePoolWithTag(prgn->Buffer, TAG_REGION); 457 } 458 459 /* Set the new buffer */ 460 prgn->Buffer = pvBuffer; 461 prgn->rdh.nRgnSize = cjNewSize; 462 463 return TRUE; 464 } 465 466 static __inline 467 BOOL 468 REGION_bEnsureBufferSize( 469 _Inout_ PREGION prgn, 470 _In_ UINT cRects) 471 { 472 /* Check if the current region size is too small */ 473 if (cRects > prgn->rdh.nRgnSize / sizeof(RECTL)) 474 { 475 /* Allocate a new buffer */ 476 return REGION_bGrowBufferSize(prgn, cRects); 477 } 478 479 return TRUE; 480 } 481 482 FORCEINLINE 483 VOID 484 REGION_vAddRect( 485 _Inout_ PREGION prgn, 486 _In_ LONG left, 487 _In_ LONG top, 488 _In_ LONG right, 489 _In_ LONG bottom) 490 { 491 PRECTL prcl; 492 NT_ASSERT((prgn->rdh.nCount + 1) * sizeof(RECT) <= prgn->rdh.nRgnSize); 493 494 prcl = &prgn->Buffer[prgn->rdh.nCount]; 495 prcl->left = left; 496 prcl->top = top; 497 prcl->right = right; 498 prcl->bottom = bottom; 499 prgn->rdh.nCount++; 500 } 501 502 static __inline 503 BOOL 504 REGION_bAddRect( 505 _Inout_ PREGION prgn, 506 _In_ LONG left, 507 _In_ LONG top, 508 _In_ LONG right, 509 _In_ LONG bottom) 510 { 511 if (!REGION_bEnsureBufferSize(prgn, prgn->rdh.nCount + 1)) 512 { 513 return FALSE; 514 } 515 516 REGION_vAddRect(prgn, left, top, right, bottom); 517 return TRUE; 518 } 519 520 typedef BOOL (FASTCALL *overlapProcp)(PREGION, PRECT, PRECT, PRECT, PRECT, INT, INT); 521 typedef BOOL (FASTCALL *nonOverlapProcp)(PREGION, PRECT, PRECT, INT, INT); 522 523 // Number of points to buffer before sending them off to scanlines() : Must be an even number 524 #define NUMPTSTOBUFFER 200 525 526 #define RGN_DEFAULT_RECTS 2 527 528 // Used to allocate buffers for points and link the buffers together 529 typedef struct _POINTBLOCK 530 { 531 POINT pts[NUMPTSTOBUFFER]; 532 struct _POINTBLOCK *next; 533 } POINTBLOCK; 534 535 #ifndef NDEBUG 536 /* 537 * This function is left there for debugging purposes. 538 */ 539 VOID 540 FASTCALL 541 IntDumpRegion(HRGN hRgn) 542 { 543 PREGION Data; 544 545 Data = REGION_LockRgn(hRgn); 546 if (Data == NULL) 547 { 548 DbgPrint("IntDumpRegion called with invalid region!\n"); 549 return; 550 } 551 552 DbgPrint("IntDumpRegion(%x): %d,%d-%d,%d %d\n", 553 hRgn, 554 Data->rdh.rcBound.left, 555 Data->rdh.rcBound.top, 556 Data->rdh.rcBound.right, 557 Data->rdh.rcBound.bottom, 558 Data->rdh.iType); 559 560 REGION_UnlockRgn(Data); 561 } 562 #endif /* Not NDEBUG */ 563 564 565 INT 566 FASTCALL 567 REGION_Complexity(PREGION prgn) 568 { 569 if (prgn == NULL) 570 return NULLREGION; 571 572 DPRINT("Region Complexity -> %lu", prgn->rdh.nCount); 573 switch (prgn->rdh.nCount) 574 { 575 case 0: 576 return NULLREGION; 577 case 1: 578 return SIMPLEREGION; 579 default: 580 return COMPLEXREGION; 581 } 582 } 583 584 static 585 BOOL 586 FASTCALL 587 REGION_CopyRegion( 588 PREGION dst, 589 PREGION src) 590 { 591 /* Only copy if source and dest are not equal */ 592 if (dst != src) 593 { 594 /* Check if we need to increase our buffer */ 595 if (dst->rdh.nRgnSize < src->rdh.nCount * sizeof(RECT)) 596 { 597 PRECTL temp; 598 599 /* Allocate a new buffer */ 600 temp = ExAllocatePoolWithTag(PagedPool, 601 src->rdh.nCount * sizeof(RECT), 602 TAG_REGION); 603 if (temp == NULL) 604 return FALSE; 605 606 /* Free the old buffer */ 607 if ((dst->Buffer != NULL) && (dst->Buffer != &dst->rdh.rcBound)) 608 ExFreePoolWithTag(dst->Buffer, TAG_REGION); 609 610 /* Set the new buffer and the size */ 611 dst->Buffer = temp; 612 dst->rdh.nRgnSize = src->rdh.nCount * sizeof(RECT); 613 } 614 615 dst->rdh.nCount = src->rdh.nCount; 616 dst->rdh.rcBound.left = src->rdh.rcBound.left; 617 dst->rdh.rcBound.top = src->rdh.rcBound.top; 618 dst->rdh.rcBound.right = src->rdh.rcBound.right; 619 dst->rdh.rcBound.bottom = src->rdh.rcBound.bottom; 620 dst->rdh.iType = src->rdh.iType; 621 COPY_RECTS(dst->Buffer, src->Buffer, src->rdh.nCount); 622 } 623 624 return TRUE; 625 } 626 627 static 628 VOID 629 FASTCALL 630 REGION_SetExtents( 631 PREGION pReg) 632 { 633 RECTL *pRect, *pRectEnd, *pExtents; 634 635 /* Quick check for NULLREGION */ 636 if (pReg->rdh.nCount == 0) 637 { 638 pReg->rdh.rcBound.left = 0; 639 pReg->rdh.rcBound.top = 0; 640 pReg->rdh.rcBound.right = 0; 641 pReg->rdh.rcBound.bottom = 0; 642 pReg->rdh.iType = RDH_RECTANGLES; 643 return; 644 } 645 646 pExtents = &pReg->rdh.rcBound; 647 pRect = pReg->Buffer; 648 pRectEnd = pReg->Buffer + pReg->rdh.nCount - 1; 649 650 /* Since pRect is the first rectangle in the region, it must have the 651 * smallest top and since pRectEnd is the last rectangle in the region, 652 * it must have the largest bottom, because of banding. Initialize left and 653 * right from pRect and pRectEnd, resp., as good things to initialize them 654 * to... */ 655 pExtents->left = pRect->left; 656 pExtents->top = pRect->top; 657 pExtents->right = pRectEnd->right; 658 pExtents->bottom = pRectEnd->bottom; 659 660 while (pRect <= pRectEnd) 661 { 662 if (pRect->left < pExtents->left) 663 pExtents->left = pRect->left; 664 if (pRect->right > pExtents->right) 665 pExtents->right = pRect->right; 666 pRect++; 667 } 668 669 pReg->rdh.iType = RDH_RECTANGLES; 670 } 671 672 // FIXME: This function needs review and testing 673 /*********************************************************************** 674 * REGION_CropRegion 675 */ 676 INT 677 FASTCALL 678 REGION_CropRegion( 679 PREGION rgnDst, 680 PREGION rgnSrc, 681 const RECTL *rect) 682 { 683 PRECTL lpr, rpr; 684 ULONG i, j, clipa, clipb, nRgnSize; 685 INT left = MAXLONG; 686 INT right = MINLONG; 687 INT top = MAXLONG; 688 INT bottom = MINLONG; 689 690 if ((rect->left >= rect->right) || 691 (rect->top >= rect->bottom) || 692 (EXTENTCHECK(rect, &rgnSrc->rdh.rcBound) == 0)) 693 { 694 goto empty; 695 } 696 697 /* Skip all rects that are completely above our intersect rect */ 698 for (clipa = 0; clipa < rgnSrc->rdh.nCount; clipa++) 699 { 700 /* bottom is exclusive, so break when we go above it */ 701 if (rgnSrc->Buffer[clipa].bottom > rect->top) break; 702 } 703 704 /* Bail out, if there is nothing left */ 705 if (clipa == rgnSrc->rdh.nCount) goto empty; 706 707 /* Find the last rect that is still within the intersect rect (exclusive) */ 708 for (clipb = clipa; clipb < rgnSrc->rdh.nCount; clipb++) 709 { 710 /* bottom is exclusive, so stop, when we start at that y pos */ 711 if (rgnSrc->Buffer[clipb].top >= rect->bottom) break; 712 } 713 714 /* Bail out, if there is nothing left */ 715 if (clipb == clipa) goto empty; 716 717 // clipa - index of the first rect in the first intersecting band 718 // clipb - index of the last rect in the last intersecting band plus 1 719 720 /* Check if the buffer in the dest region is large enough, 721 otherwise allocate a new one */ 722 nRgnSize = (clipb - clipa) * sizeof(RECT); 723 if ((rgnDst != rgnSrc) && (rgnDst->rdh.nRgnSize < nRgnSize)) 724 { 725 PRECTL temp; 726 temp = ExAllocatePoolWithTag(PagedPool, nRgnSize, TAG_REGION); 727 if (temp == NULL) 728 return ERROR; 729 730 /* Free the old buffer */ 731 if (rgnDst->Buffer && (rgnDst->Buffer != &rgnDst->rdh.rcBound)) 732 ExFreePoolWithTag(rgnDst->Buffer, TAG_REGION); 733 734 rgnDst->Buffer = temp; 735 rgnDst->rdh.nCount = 0; 736 rgnDst->rdh.nRgnSize = nRgnSize; 737 rgnDst->rdh.iType = RDH_RECTANGLES; 738 } 739 740 /* Loop all rects within the intersect rect from the y perspective */ 741 for (i = clipa, j = 0; i < clipb ; i++) 742 { 743 /* i - src index, j - dst index, j is always <= i for obvious reasons */ 744 745 lpr = &rgnSrc->Buffer[i]; 746 747 /* Make sure the source rect is not retarded */ 748 ASSERT(lpr->bottom > lpr->top); 749 ASSERT(lpr->right > lpr->left); 750 751 /* We already checked above, this should hold true */ 752 ASSERT(lpr->bottom > rect->top); 753 ASSERT(lpr->top < rect->bottom); 754 755 /* Check if this rect is really inside the intersect rect */ 756 if ((lpr->left < rect->right) && (lpr->right > rect->left)) 757 { 758 rpr = &rgnDst->Buffer[j]; 759 760 /* Crop the rect with the intersect rect */ 761 rpr->top = max(lpr->top, rect->top); 762 rpr->bottom = min(lpr->bottom, rect->bottom); 763 rpr->left = max(lpr->left, rect->left); 764 rpr->right = min(lpr->right, rect->right); 765 766 /* Make sure the resulting rect is not retarded */ 767 ASSERT(rpr->bottom > rpr->top); 768 ASSERT(rpr->right > rpr->left); 769 770 /* Track new bounds */ 771 if (rpr->left < left) left = rpr->left; 772 if (rpr->right > right) right = rpr->right; 773 if (rpr->top < top) top = rpr->top; 774 if (rpr->bottom > bottom) bottom = rpr->bottom; 775 776 /* Next target rect */ 777 j++; 778 } 779 } 780 781 if (j == 0) goto empty; 782 783 /* Update the bounds rect */ 784 rgnDst->rdh.rcBound.left = left; 785 rgnDst->rdh.rcBound.right = right; 786 rgnDst->rdh.rcBound.top = top; 787 rgnDst->rdh.rcBound.bottom = bottom; 788 789 /* Set new rect count */ 790 rgnDst->rdh.nCount = j; 791 792 return REGION_Complexity(rgnDst); 793 794 empty: 795 if (rgnDst->Buffer == NULL) 796 { 797 rgnDst->Buffer = &rgnDst->rdh.rcBound; 798 } 799 800 EMPTY_REGION(rgnDst); 801 return NULLREGION; 802 } 803 804 805 /*! 806 * Attempt to merge the rects in the current band with those in the 807 * previous one. Used only by REGION_RegionOp. 808 * 809 * Results: 810 * The new index for the previous band. 811 * 812 * \note Side Effects: 813 * If coalescing takes place: 814 * - rectangles in the previous band will have their bottom fields 815 * altered. 816 * - pReg->numRects will be decreased. 817 * 818 */ 819 static 820 INT 821 FASTCALL 822 REGION_Coalesce( 823 PREGION pReg, /* Region to coalesce */ 824 INT prevStart, /* Index of start of previous band */ 825 INT curStart) /* Index of start of current band */ 826 { 827 RECTL *pPrevRect; /* Current rect in previous band */ 828 RECTL *pCurRect; /* Current rect in current band */ 829 RECTL *pRegEnd; /* End of region */ 830 INT curNumRects; /* Number of rectangles in current band */ 831 INT prevNumRects; /* Number of rectangles in previous band */ 832 INT bandtop; /* Top coordinate for current band */ 833 834 pRegEnd = pReg->Buffer + pReg->rdh.nCount; 835 pPrevRect = pReg->Buffer + prevStart; 836 prevNumRects = curStart - prevStart; 837 838 /* Figure out how many rectangles are in the current band. Have to do 839 * this because multiple bands could have been added in REGION_RegionOp 840 * at the end when one region has been exhausted. */ 841 pCurRect = pReg->Buffer + curStart; 842 bandtop = pCurRect->top; 843 for (curNumRects = 0; 844 (pCurRect != pRegEnd) && (pCurRect->top == bandtop); 845 curNumRects++) 846 { 847 pCurRect++; 848 } 849 850 if (pCurRect != pRegEnd) 851 { 852 /* If more than one band was added, we have to find the start 853 * of the last band added so the next coalescing job can start 854 * at the right place... (given when multiple bands are added, 855 * this may be pointless -- see above). */ 856 pRegEnd--; 857 while ((pRegEnd-1)->top == pRegEnd->top) 858 { 859 pRegEnd--; 860 } 861 862 curStart = pRegEnd - pReg->Buffer; 863 pRegEnd = pReg->Buffer + pReg->rdh.nCount; 864 } 865 866 if ((curNumRects == prevNumRects) && (curNumRects != 0)) 867 { 868 pCurRect -= curNumRects; 869 870 /* The bands may only be coalesced if the bottom of the previous 871 * matches the top scanline of the current. */ 872 if (pPrevRect->bottom == pCurRect->top) 873 { 874 /* Make sure the bands have rects in the same places. This 875 * assumes that rects have been added in such a way that they 876 * cover the most area possible. I.e. two rects in a band must 877 * have some horizontal space between them. */ 878 do 879 { 880 if ((pPrevRect->left != pCurRect->left) || 881 (pPrevRect->right != pCurRect->right)) 882 { 883 /* The bands don't line up so they can't be coalesced. */ 884 return (curStart); 885 } 886 887 pPrevRect++; 888 pCurRect++; 889 prevNumRects -= 1; 890 } 891 while (prevNumRects != 0); 892 893 pReg->rdh.nCount -= curNumRects; 894 pCurRect -= curNumRects; 895 pPrevRect -= curNumRects; 896 897 /* The bands may be merged, so set the bottom of each rect 898 * in the previous band to that of the corresponding rect in 899 * the current band. */ 900 do 901 { 902 pPrevRect->bottom = pCurRect->bottom; 903 pPrevRect++; 904 pCurRect++; 905 curNumRects -= 1; 906 } 907 while (curNumRects != 0); 908 909 /* If only one band was added to the region, we have to backup 910 * curStart to the start of the previous band. 911 * 912 * If more than one band was added to the region, copy the 913 * other bands down. The assumption here is that the other bands 914 * came from the same region as the current one and no further 915 * coalescing can be done on them since it's all been done 916 * already... curStart is already in the right place. */ 917 if (pCurRect == pRegEnd) 918 { 919 curStart = prevStart; 920 } 921 else 922 { 923 do 924 { 925 *pPrevRect++ = *pCurRect++; 926 } 927 while (pCurRect != pRegEnd); 928 } 929 } 930 } 931 932 return (curStart); 933 } 934 935 /*! 936 * Apply an operation to two regions. Called by REGION_Union, 937 * REGION_Inverse, REGION_Subtract, REGION_Intersect... 938 * 939 * Results: 940 * None. 941 * 942 * Side Effects: 943 * The new region is overwritten. 944 * 945 *\note The idea behind this function is to view the two regions as sets. 946 * Together they cover a rectangle of area that this function divides 947 * into horizontal bands where points are covered only by one region 948 * or by both. For the first case, the nonOverlapFunc is called with 949 * each the band and the band's upper and lower extents. For the 950 * second, the overlapFunc is called to process the entire band. It 951 * is responsible for clipping the rectangles in the band, though 952 * this function provides the boundaries. 953 * At the end of each band, the new region is coalesced, if possible, 954 * to reduce the number of rectangles in the region. 955 * 956 */ 957 static 958 BOOL 959 FASTCALL 960 REGION_RegionOp( 961 PREGION newReg, /* Place to store result */ 962 PREGION reg1, /* First region in operation */ 963 PREGION reg2, /* 2nd region in operation */ 964 overlapProcp overlapFunc, /* Function to call for over-lapping bands */ 965 nonOverlapProcp nonOverlap1Func, /* Function to call for non-overlapping bands in region 1 */ 966 nonOverlapProcp nonOverlap2Func) /* Function to call for non-overlapping bands in region 2 */ 967 { 968 RECTL *r1; /* Pointer into first region */ 969 RECTL *r2; /* Pointer into 2d region */ 970 RECTL *r1End; /* End of 1st region */ 971 RECTL *r2End; /* End of 2d region */ 972 INT ybot; /* Bottom of intersection */ 973 INT ytop; /* Top of intersection */ 974 RECTL *oldRects; /* Old rects for newReg */ 975 ULONG prevBand; /* Index of start of 976 * Previous band in newReg */ 977 ULONG curBand; /* Index of start of current band in newReg */ 978 RECTL *r1BandEnd; /* End of current band in r1 */ 979 RECTL *r2BandEnd; /* End of current band in r2 */ 980 ULONG top; /* Top of non-overlapping band */ 981 ULONG bot; /* Bottom of non-overlapping band */ 982 983 /* Initialization: 984 * set r1, r2, r1End and r2End appropriately, preserve the important 985 * parts of the destination region until the end in case it's one of 986 * the two source regions, then mark the "new" region empty, allocating 987 * another array of rectangles for it to use. */ 988 r1 = reg1->Buffer; 989 r2 = reg2->Buffer; 990 r1End = r1 + reg1->rdh.nCount; 991 r2End = r2 + reg2->rdh.nCount; 992 993 /* newReg may be one of the src regions so we can't empty it. We keep a 994 * note of its rects pointer (so that we can free them later), preserve its 995 * extents and simply set numRects to zero. */ 996 oldRects = newReg->Buffer; 997 newReg->rdh.nCount = 0; 998 999 /* Allocate a reasonable number of rectangles for the new region. The idea 1000 * is to allocate enough so the individual functions don't need to 1001 * reallocate and copy the array, which is time consuming, yet we don't 1002 * have to worry about using too much memory. I hope to be able to 1003 * nuke the Xrealloc() at the end of this function eventually. */ 1004 newReg->rdh.nRgnSize = max(reg1->rdh.nCount + 1, reg2->rdh.nCount) * 2 * sizeof(RECT); 1005 1006 newReg->Buffer = ExAllocatePoolWithTag(PagedPool, 1007 newReg->rdh.nRgnSize, 1008 TAG_REGION); 1009 if (newReg->Buffer == NULL) 1010 { 1011 newReg->rdh.nRgnSize = 0; 1012 return FALSE; 1013 } 1014 1015 /* Initialize ybot and ytop. 1016 * In the upcoming loop, ybot and ytop serve different functions depending 1017 * on whether the band being handled is an overlapping or non-overlapping 1018 * band. 1019 * In the case of a non-overlapping band (only one of the regions 1020 * has points in the band), ybot is the bottom of the most recent 1021 * intersection and thus clips the top of the rectangles in that band. 1022 * ytop is the top of the next intersection between the two regions and 1023 * serves to clip the bottom of the rectangles in the current band. 1024 * For an overlapping band (where the two regions intersect), ytop clips 1025 * the top of the rectangles of both regions and ybot clips the bottoms. */ 1026 if (reg1->rdh.rcBound.top < reg2->rdh.rcBound.top) 1027 ybot = reg1->rdh.rcBound.top; 1028 else 1029 ybot = reg2->rdh.rcBound.top; 1030 1031 /* prevBand serves to mark the start of the previous band so rectangles 1032 * can be coalesced into larger rectangles. qv. miCoalesce, above. 1033 * In the beginning, there is no previous band, so prevBand == curBand 1034 * (curBand is set later on, of course, but the first band will always 1035 * start at index 0). prevBand and curBand must be indices because of 1036 * the possible expansion, and resultant moving, of the new region's 1037 * array of rectangles. */ 1038 prevBand = 0; 1039 do 1040 { 1041 curBand = newReg->rdh.nCount; 1042 1043 /* This algorithm proceeds one source-band (as opposed to a 1044 * destination band, which is determined by where the two regions 1045 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the 1046 * rectangle after the last one in the current band for their 1047 * respective regions. */ 1048 r1BandEnd = r1; 1049 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) 1050 { 1051 r1BandEnd++; 1052 } 1053 1054 r2BandEnd = r2; 1055 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top)) 1056 { 1057 r2BandEnd++; 1058 } 1059 1060 /* First handle the band that doesn't intersect, if any. 1061 * 1062 * Note that attention is restricted to one band in the 1063 * non-intersecting region at once, so if a region has n 1064 * bands between the current position and the next place it overlaps 1065 * the other, this entire loop will be passed through n times. */ 1066 if (r1->top < r2->top) 1067 { 1068 top = max(r1->top,ybot); 1069 bot = min(r1->bottom,r2->top); 1070 1071 if ((top != bot) && (nonOverlap1Func != NULL)) 1072 { 1073 if (!(*nonOverlap1Func)(newReg, r1, r1BandEnd, top, bot)) return FALSE; 1074 } 1075 1076 ytop = r2->top; 1077 } 1078 else if (r2->top < r1->top) 1079 { 1080 top = max(r2->top,ybot); 1081 bot = min(r2->bottom,r1->top); 1082 1083 if ((top != bot) && (nonOverlap2Func != NULL)) 1084 { 1085 if (!(*nonOverlap2Func)(newReg, r2, r2BandEnd, top, bot) ) return FALSE; 1086 } 1087 1088 ytop = r1->top; 1089 } 1090 else 1091 { 1092 ytop = r1->top; 1093 } 1094 1095 /* If any rectangles got added to the region, try and coalesce them 1096 * with rectangles from the previous band. Note we could just do 1097 * this test in miCoalesce, but some machines incur a not 1098 * inconsiderable cost for function calls, so... */ 1099 if (newReg->rdh.nCount != curBand) 1100 { 1101 prevBand = REGION_Coalesce(newReg, prevBand, curBand); 1102 } 1103 1104 /* Now see if we've hit an intersecting band. The two bands only 1105 * intersect if ybot > ytop */ 1106 ybot = min(r1->bottom, r2->bottom); 1107 curBand = newReg->rdh.nCount; 1108 if (ybot > ytop) 1109 { 1110 if (!(*overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot)) return FALSE; 1111 } 1112 1113 if (newReg->rdh.nCount != curBand) 1114 { 1115 prevBand = REGION_Coalesce(newReg, prevBand, curBand); 1116 } 1117 1118 /* If we've finished with a band (bottom == ybot) we skip forward 1119 * in the region to the next band. */ 1120 if (r1->bottom == ybot) 1121 { 1122 r1 = r1BandEnd; 1123 } 1124 if (r2->bottom == ybot) 1125 { 1126 r2 = r2BandEnd; 1127 } 1128 } 1129 while ((r1 != r1End) && (r2 != r2End)); 1130 1131 /* Deal with whichever region still has rectangles left. */ 1132 curBand = newReg->rdh.nCount; 1133 if (r1 != r1End) 1134 { 1135 if (nonOverlap1Func != NULL) 1136 { 1137 do 1138 { 1139 r1BandEnd = r1; 1140 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top)) 1141 { 1142 r1BandEnd++; 1143 } 1144 1145 if (!(*nonOverlap1Func)(newReg, 1146 r1, 1147 r1BandEnd, 1148 max(r1->top,ybot), 1149 r1->bottom)) 1150 return FALSE; 1151 r1 = r1BandEnd; 1152 } 1153 while (r1 != r1End); 1154 } 1155 } 1156 else if ((r2 != r2End) && (nonOverlap2Func != NULL)) 1157 { 1158 do 1159 { 1160 r2BandEnd = r2; 1161 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top)) 1162 { 1163 r2BandEnd++; 1164 } 1165 1166 if (!(*nonOverlap2Func)(newReg, 1167 r2, 1168 r2BandEnd, 1169 max(r2->top,ybot), 1170 r2->bottom)) 1171 return FALSE; 1172 r2 = r2BandEnd; 1173 } 1174 while (r2 != r2End); 1175 } 1176 1177 if (newReg->rdh.nCount != curBand) 1178 { 1179 (VOID)REGION_Coalesce(newReg, prevBand, curBand); 1180 } 1181 1182 /* A bit of cleanup. To keep regions from growing without bound, 1183 * we shrink the array of rectangles to match the new number of 1184 * rectangles in the region. This never goes to 0, however... 1185 * 1186 * Only do this stuff if the number of rectangles allocated is more than 1187 * twice the number of rectangles in the region (a simple optimization...). */ 1188 if ((newReg->rdh.nRgnSize > (2 * newReg->rdh.nCount * sizeof(RECT))) && 1189 (newReg->rdh.nCount > 2)) 1190 { 1191 if (REGION_NOT_EMPTY(newReg)) 1192 { 1193 RECTL *prev_rects = newReg->Buffer; 1194 newReg->Buffer = ExAllocatePoolWithTag(PagedPool, 1195 newReg->rdh.nCount * sizeof(RECT), 1196 TAG_REGION); 1197 1198 if (newReg->Buffer == NULL) 1199 { 1200 newReg->Buffer = prev_rects; 1201 } 1202 else 1203 { 1204 newReg->rdh.nRgnSize = newReg->rdh.nCount*sizeof(RECT); 1205 COPY_RECTS(newReg->Buffer, prev_rects, newReg->rdh.nCount); 1206 if (prev_rects != &newReg->rdh.rcBound) 1207 ExFreePoolWithTag(prev_rects, TAG_REGION); 1208 } 1209 } 1210 else 1211 { 1212 /* No point in doing the extra work involved in an Xrealloc if 1213 * the region is empty */ 1214 newReg->rdh.nRgnSize = sizeof(RECT); 1215 if (newReg->Buffer != &newReg->rdh.rcBound) 1216 ExFreePoolWithTag(newReg->Buffer, TAG_REGION); 1217 1218 newReg->Buffer = ExAllocatePoolWithTag(PagedPool, 1219 sizeof(RECT), 1220 TAG_REGION); 1221 ASSERT(newReg->Buffer); 1222 } 1223 } 1224 1225 newReg->rdh.iType = RDH_RECTANGLES; 1226 1227 if (oldRects != &newReg->rdh.rcBound) 1228 ExFreePoolWithTag(oldRects, TAG_REGION); 1229 return TRUE; 1230 } 1231 1232 /*********************************************************************** 1233 * Region Intersection 1234 ***********************************************************************/ 1235 1236 1237 /*! 1238 * Handle an overlapping band for REGION_Intersect. 1239 * 1240 * Results: 1241 * None. 1242 * 1243 * \note Side Effects: 1244 * Rectangles may be added to the region. 1245 * 1246 */ 1247 static 1248 BOOL 1249 FASTCALL 1250 REGION_IntersectO( 1251 PREGION pReg, 1252 PRECTL r1, 1253 PRECTL r1End, 1254 PRECTL r2, 1255 PRECTL r2End, 1256 INT top, 1257 INT bottom) 1258 { 1259 INT left, right; 1260 1261 while ((r1 != r1End) && (r2 != r2End)) 1262 { 1263 left = max(r1->left, r2->left); 1264 right = min(r1->right, r2->right); 1265 1266 /* If there's any overlap between the two rectangles, add that 1267 * overlap to the new region. 1268 * There's no need to check for subsumption because the only way 1269 * such a need could arise is if some region has two rectangles 1270 * right next to each other. Since that should never happen... */ 1271 if (left < right) 1272 { 1273 if (!REGION_bAddRect(pReg, left, top, right, bottom)) 1274 { 1275 return FALSE; 1276 } 1277 } 1278 1279 /* Need to advance the pointers. Shift the one that extends 1280 * to the right the least, since the other still has a chance to 1281 * overlap with that region's next rectangle, if you see what I mean. */ 1282 if (r1->right < r2->right) 1283 { 1284 r1++; 1285 } 1286 else if (r2->right < r1->right) 1287 { 1288 r2++; 1289 } 1290 else 1291 { 1292 r1++; 1293 r2++; 1294 } 1295 } 1296 1297 return TRUE; 1298 } 1299 1300 /*********************************************************************** 1301 * REGION_IntersectRegion 1302 */ 1303 static 1304 BOOL 1305 FASTCALL 1306 REGION_IntersectRegion( 1307 PREGION newReg, 1308 PREGION reg1, 1309 PREGION reg2) 1310 { 1311 /* Check for trivial reject */ 1312 if ((reg1->rdh.nCount == 0) || 1313 (reg2->rdh.nCount == 0) || 1314 (EXTENTCHECK(®1->rdh.rcBound, ®2->rdh.rcBound) == 0)) 1315 { 1316 newReg->rdh.nCount = 0; 1317 } 1318 else 1319 { 1320 if (!REGION_RegionOp(newReg, 1321 reg1, 1322 reg2, 1323 REGION_IntersectO, 1324 NULL, 1325 NULL)) 1326 return FALSE; 1327 } 1328 1329 /* Can't alter newReg's extents before we call miRegionOp because 1330 * it might be one of the source regions and miRegionOp depends 1331 * on the extents of those regions being the same. Besides, this 1332 * way there's no checking against rectangles that will be nuked 1333 * due to coalescing, so we have to examine fewer rectangles. */ 1334 REGION_SetExtents(newReg); 1335 return TRUE; 1336 } 1337 1338 /*********************************************************************** 1339 * Region Union 1340 ***********************************************************************/ 1341 1342 /*! 1343 * Handle a non-overlapping band for the union operation. Just 1344 * Adds the rectangles into the region. Doesn't have to check for 1345 * subsumption or anything. 1346 * 1347 * Results: 1348 * None. 1349 * 1350 * \note Side Effects: 1351 * pReg->numRects is incremented and the final rectangles overwritten 1352 * with the rectangles we're passed. 1353 * 1354 */ 1355 static 1356 BOOL 1357 FASTCALL 1358 REGION_UnionNonO( 1359 PREGION pReg, 1360 PRECTL r, 1361 PRECTL rEnd, 1362 INT top, 1363 INT bottom) 1364 { 1365 if (r != rEnd) 1366 { 1367 if (!REGION_bEnsureBufferSize(pReg, pReg->rdh.nCount + (rEnd - r))) 1368 { 1369 return FALSE; 1370 } 1371 1372 do 1373 { 1374 REGION_vAddRect(pReg, r->left, top, r->right, bottom); 1375 r++; 1376 } 1377 while (r != rEnd); 1378 } 1379 1380 return TRUE; 1381 } 1382 1383 static __inline 1384 BOOL 1385 REGION_bMergeRect( 1386 _Inout_ PREGION prgn, 1387 _In_ LONG left, 1388 _In_ LONG top, 1389 _In_ LONG right, 1390 _In_ LONG bottom) 1391 { 1392 if ((prgn->rdh.nCount != 0) && 1393 (prgn->Buffer[prgn->rdh.nCount - 1].top == top) && 1394 (prgn->Buffer[prgn->rdh.nCount - 1].bottom == bottom) && 1395 (prgn->Buffer[prgn->rdh.nCount - 1].right >= left)) 1396 { 1397 if (prgn->Buffer[prgn->rdh.nCount - 1].right < right) 1398 { 1399 prgn->Buffer[prgn->rdh.nCount - 1].right = right; 1400 } 1401 } 1402 else 1403 { 1404 if (!REGION_bAddRect(prgn, left, top, right, bottom)) 1405 { 1406 return FALSE; 1407 } 1408 } 1409 1410 return TRUE; 1411 } 1412 1413 /*! 1414 * Handle an overlapping band for the union operation. Picks the 1415 * left-most rectangle each time and merges it into the region. 1416 * 1417 * Results: 1418 * None. 1419 * 1420 * \note Side Effects: 1421 * Rectangles are overwritten in pReg->rects and pReg->numRects will 1422 * be changed. 1423 * 1424 */ 1425 static 1426 BOOL 1427 FASTCALL 1428 REGION_UnionO ( 1429 PREGION pReg, 1430 PRECTL r1, 1431 PRECTL r1End, 1432 PRECTL r2, 1433 PRECTL r2End, 1434 INT top, 1435 INT bottom) 1436 { 1437 while ((r1 != r1End) && (r2 != r2End)) 1438 { 1439 if (r1->left < r2->left) 1440 { 1441 if (!REGION_bMergeRect(pReg, r1->left, top, r1->right, bottom)) return FALSE; 1442 r1++; 1443 } 1444 else 1445 { 1446 if (!REGION_bMergeRect(pReg, r2->left, top, r2->right, bottom)) return FALSE; 1447 r2++; 1448 } 1449 } 1450 1451 if (r1 != r1End) 1452 { 1453 do 1454 { 1455 if (!REGION_bMergeRect(pReg, r1->left, top, r1->right, bottom)) return FALSE; 1456 r1++; 1457 } 1458 while (r1 != r1End); 1459 } 1460 else 1461 { 1462 while (r2 != r2End) 1463 { 1464 if (!REGION_bMergeRect(pReg, r2->left, top, r2->right, bottom)) return FALSE; 1465 r2++; 1466 } 1467 } 1468 1469 return TRUE; 1470 } 1471 1472 /*********************************************************************** 1473 * REGION_UnionRegion 1474 */ 1475 static 1476 BOOL 1477 FASTCALL 1478 REGION_UnionRegion( 1479 PREGION newReg, 1480 PREGION reg1, 1481 PREGION reg2) 1482 { 1483 BOOL ret = TRUE; 1484 1485 /* Checks all the simple cases 1486 * Region 1 and 2 are the same or region 1 is empty */ 1487 if ((reg1 == reg2) || (reg1->rdh.nCount == 0) || 1488 (reg1->rdh.rcBound.right <= reg1->rdh.rcBound.left) || 1489 (reg1->rdh.rcBound.bottom <= reg1->rdh.rcBound.top)) 1490 { 1491 if (newReg != reg2) 1492 { 1493 ret = REGION_CopyRegion(newReg, reg2); 1494 } 1495 1496 return ret; 1497 } 1498 1499 /* If nothing to union (region 2 empty) */ 1500 if ((reg2->rdh.nCount == 0) || 1501 (reg2->rdh.rcBound.right <= reg2->rdh.rcBound.left) || 1502 (reg2->rdh.rcBound.bottom <= reg2->rdh.rcBound.top)) 1503 { 1504 if (newReg != reg1) 1505 { 1506 ret = REGION_CopyRegion(newReg, reg1); 1507 } 1508 1509 return ret; 1510 } 1511 1512 /* Region 1 completely subsumes region 2 */ 1513 if ((reg1->rdh.nCount == 1) && 1514 (reg1->rdh.rcBound.left <= reg2->rdh.rcBound.left) && 1515 (reg1->rdh.rcBound.top <= reg2->rdh.rcBound.top) && 1516 (reg2->rdh.rcBound.right <= reg1->rdh.rcBound.right) && 1517 (reg2->rdh.rcBound.bottom <= reg1->rdh.rcBound.bottom)) 1518 { 1519 if (newReg != reg1) 1520 { 1521 ret = REGION_CopyRegion(newReg, reg1); 1522 } 1523 1524 return ret; 1525 } 1526 1527 /* Region 2 completely subsumes region 1 */ 1528 if ((reg2->rdh.nCount == 1) && 1529 (reg2->rdh.rcBound.left <= reg1->rdh.rcBound.left) && 1530 (reg2->rdh.rcBound.top <= reg1->rdh.rcBound.top) && 1531 (reg1->rdh.rcBound.right <= reg2->rdh.rcBound.right) && 1532 (reg1->rdh.rcBound.bottom <= reg2->rdh.rcBound.bottom)) 1533 { 1534 if (newReg != reg2) 1535 { 1536 ret = REGION_CopyRegion(newReg, reg2); 1537 } 1538 1539 return ret; 1540 } 1541 1542 if ((ret = REGION_RegionOp(newReg, 1543 reg1, 1544 reg2, 1545 REGION_UnionO, 1546 REGION_UnionNonO, 1547 REGION_UnionNonO))) 1548 { 1549 newReg->rdh.rcBound.left = min(reg1->rdh.rcBound.left, reg2->rdh.rcBound.left); 1550 newReg->rdh.rcBound.top = min(reg1->rdh.rcBound.top, reg2->rdh.rcBound.top); 1551 newReg->rdh.rcBound.right = max(reg1->rdh.rcBound.right, reg2->rdh.rcBound.right); 1552 newReg->rdh.rcBound.bottom = max(reg1->rdh.rcBound.bottom, reg2->rdh.rcBound.bottom); 1553 } 1554 return ret; 1555 } 1556 1557 /*********************************************************************** 1558 * Region Subtraction 1559 ***********************************************************************/ 1560 1561 /*! 1562 * Deal with non-overlapping band for subtraction. Any parts from 1563 * region 2 we discard. Anything from region 1 we add to the region. 1564 * 1565 * Results: 1566 * None. 1567 * 1568 * \note Side Effects: 1569 * pReg may be affected. 1570 * 1571 */ 1572 static 1573 BOOL 1574 FASTCALL 1575 REGION_SubtractNonO1( 1576 PREGION pReg, 1577 PRECTL r, 1578 PRECTL rEnd, 1579 INT top, 1580 INT bottom) 1581 { 1582 if (r != rEnd) 1583 { 1584 if (!REGION_bEnsureBufferSize(pReg, pReg->rdh.nCount + (rEnd - r))) 1585 { 1586 return FALSE; 1587 } 1588 1589 do 1590 { 1591 REGION_vAddRect(pReg, r->left, top, r->right, bottom); 1592 r++; 1593 } 1594 while (r != rEnd); 1595 } 1596 1597 return TRUE; 1598 } 1599 1600 1601 /*! 1602 * Overlapping band subtraction. x1 is the left-most point not yet 1603 * checked. 1604 * 1605 * Results: 1606 * None. 1607 * 1608 * \note Side Effects: 1609 * pReg may have rectangles added to it. 1610 * 1611 */ 1612 static 1613 BOOL 1614 FASTCALL 1615 REGION_SubtractO( 1616 PREGION pReg, 1617 PRECTL r1, 1618 PRECTL r1End, 1619 PRECTL r2, 1620 PRECTL r2End, 1621 INT top, 1622 INT bottom) 1623 { 1624 INT left; 1625 1626 left = r1->left; 1627 1628 while ((r1 != r1End) && (r2 != r2End)) 1629 { 1630 if (r2->right <= left) 1631 { 1632 /* Subtrahend missed the boat: go to next subtrahend. */ 1633 r2++; 1634 } 1635 else if (r2->left <= left) 1636 { 1637 /* Subtrahend preceeds minuend: nuke left edge of minuend. */ 1638 left = r2->right; 1639 if (left >= r1->right) 1640 { 1641 /* Minuend completely covered: advance to next minuend and 1642 * reset left fence to edge of new minuend. */ 1643 r1++; 1644 if (r1 != r1End) 1645 left = r1->left; 1646 } 1647 else 1648 { 1649 /* Subtrahend now used up since it doesn't extend beyond 1650 * minuend */ 1651 r2++; 1652 } 1653 } 1654 else if (r2->left < r1->right) 1655 { 1656 /* Left part of subtrahend covers part of minuend: add uncovered 1657 * part of minuend to region and skip to next subtrahend. */ 1658 if (!REGION_bAddRect(pReg, left, top, r2->left, bottom)) 1659 { 1660 return FALSE; 1661 } 1662 1663 left = r2->right; 1664 if (left >= r1->right) 1665 { 1666 /* Minuend used up: advance to new... */ 1667 r1++; 1668 if (r1 != r1End) 1669 left = r1->left; 1670 } 1671 else 1672 { 1673 /* Subtrahend used up */ 1674 r2++; 1675 } 1676 } 1677 else 1678 { 1679 /* Minuend used up: add any remaining piece before advancing. */ 1680 if (r1->right > left) 1681 { 1682 if (!REGION_bAddRect(pReg, left, top, r1->right, bottom)) 1683 { 1684 return FALSE; 1685 } 1686 } 1687 1688 r1++; 1689 if (r1 != r1End) 1690 left = r1->left; 1691 } 1692 } 1693 1694 /* Make sure the buffer is large enough for all remaining operations */ 1695 if (r1 != r1End) 1696 { 1697 if (!REGION_bEnsureBufferSize(pReg, pReg->rdh.nCount + (r1End - r1))) 1698 { 1699 return FALSE; 1700 } 1701 1702 /* Add remaining minuend rectangles to region. */ 1703 do 1704 { 1705 REGION_vAddRect(pReg, left, top, r1->right, bottom); 1706 r1++; 1707 if (r1 != r1End) 1708 { 1709 left = r1->left; 1710 } 1711 } 1712 while (r1 != r1End); 1713 } 1714 1715 return TRUE; 1716 } 1717 1718 /*! 1719 * Subtract regS from regM and leave the result in regD. 1720 * S stands for subtrahend, M for minuend and D for difference. 1721 * 1722 * Results: 1723 * TRUE. 1724 * 1725 * \note Side Effects: 1726 * regD is overwritten. 1727 * 1728 */ 1729 static 1730 BOOL 1731 FASTCALL 1732 REGION_SubtractRegion( 1733 PREGION regD, 1734 PREGION regM, 1735 PREGION regS) 1736 { 1737 /* Check for trivial reject */ 1738 if ((regM->rdh.nCount == 0) || 1739 (regS->rdh.nCount == 0) || 1740 (EXTENTCHECK(®M->rdh.rcBound, ®S->rdh.rcBound) == 0)) 1741 { 1742 return REGION_CopyRegion(regD, regM); 1743 } 1744 1745 if (!REGION_RegionOp(regD, 1746 regM, 1747 regS, 1748 REGION_SubtractO, 1749 REGION_SubtractNonO1, 1750 NULL)) 1751 return FALSE; 1752 1753 /* Can't alter newReg's extents before we call miRegionOp because 1754 * it might be one of the source regions and miRegionOp depends 1755 * on the extents of those regions being the unaltered. Besides, this 1756 * way there's no checking against rectangles that will be nuked 1757 * due to coalescing, so we have to examine fewer rectangles. */ 1758 REGION_SetExtents(regD); 1759 return TRUE; 1760 } 1761 1762 /*********************************************************************** 1763 * REGION_XorRegion 1764 */ 1765 static 1766 BOOL 1767 FASTCALL 1768 REGION_XorRegion( 1769 PREGION dr, 1770 PREGION sra, 1771 PREGION srb) 1772 { 1773 HRGN htra, htrb; 1774 PREGION tra, trb; 1775 BOOL ret; 1776 1777 // FIXME: Don't use a handle 1778 tra = REGION_AllocRgnWithHandle(sra->rdh.nCount + 1); 1779 if (tra == NULL) 1780 { 1781 return FALSE; 1782 } 1783 htra = tra->BaseObject.hHmgr; 1784 1785 // FIXME: Don't use a handle 1786 trb = REGION_AllocRgnWithHandle(srb->rdh.nCount + 1); 1787 if (trb == NULL) 1788 { 1789 REGION_UnlockRgn(tra); 1790 GreDeleteObject(htra); 1791 return FALSE; 1792 } 1793 htrb = trb->BaseObject.hHmgr; 1794 1795 ret = REGION_SubtractRegion(tra, sra, srb) && 1796 REGION_SubtractRegion(trb, srb, sra) && 1797 REGION_UnionRegion(dr, tra, trb); 1798 REGION_UnlockRgn(tra); 1799 REGION_UnlockRgn(trb); 1800 1801 GreDeleteObject(htra); 1802 GreDeleteObject(htrb); 1803 return ret; 1804 } 1805 1806 1807 /*! 1808 * Adds a rectangle to a REGION 1809 */ 1810 BOOL 1811 FASTCALL 1812 REGION_UnionRectWithRgn( 1813 PREGION rgn, 1814 const RECTL *rect) 1815 { 1816 REGION region; 1817 1818 region.Buffer = ®ion.rdh.rcBound; 1819 region.rdh.nCount = 1; 1820 region.rdh.nRgnSize = sizeof(RECT); 1821 region.rdh.rcBound = *rect; 1822 return REGION_UnionRegion(rgn, rgn, ®ion); 1823 } 1824 1825 INT 1826 FASTCALL 1827 REGION_SubtractRectFromRgn( 1828 PREGION prgnDest, 1829 PREGION prgnSrc, 1830 const RECTL *prcl) 1831 { 1832 REGION rgnLocal; 1833 1834 rgnLocal.Buffer = &rgnLocal.rdh.rcBound; 1835 rgnLocal.rdh.nCount = 1; 1836 rgnLocal.rdh.nRgnSize = sizeof(RECT); 1837 rgnLocal.rdh.rcBound = *prcl; 1838 REGION_SubtractRegion(prgnDest, prgnSrc, &rgnLocal); 1839 return REGION_Complexity(prgnDest); 1840 } 1841 1842 BOOL 1843 FASTCALL 1844 REGION_bCopy( 1845 PREGION dst, 1846 PREGION src) 1847 { 1848 if ( !dst || !src ) return FALSE; 1849 return REGION_CopyRegion( dst, src); 1850 } 1851 1852 BOOL 1853 FASTCALL 1854 REGION_bIntersectRegion( 1855 PREGION newReg, 1856 PREGION reg1, 1857 PREGION reg2) 1858 { 1859 if ( !newReg || !reg1 || !reg2 ) return FALSE; 1860 return REGION_IntersectRegion( newReg, reg1, reg2); 1861 } 1862 1863 static 1864 BOOL 1865 REGION_bMakeSimpleFrameRgn( 1866 _Inout_ PREGION prgn, 1867 _In_ PRECTL prclSrc, 1868 _In_ INT cx, 1869 _In_ INT cy) 1870 { 1871 RECTL arcl[4]; 1872 UINT i; 1873 1874 NT_ASSERT((cx >= 0) && (cy >= 0)); 1875 NT_ASSERT((prclSrc->bottom > prclSrc->top) && 1876 (prclSrc->right > prclSrc->left)); 1877 1878 /* Start with an empty region */ 1879 EMPTY_REGION(prgn); 1880 1881 /* Check for the case where the frame covers the whole rect */ 1882 if (((prclSrc->bottom - prclSrc->top) <= cy * 2) || 1883 ((prclSrc->right - prclSrc->left) <= cx * 2)) 1884 { 1885 prgn->rdh.rcBound = *prclSrc; 1886 prgn->Buffer[0] = *prclSrc; 1887 prgn->rdh.nCount = 1; 1888 return TRUE; 1889 } 1890 1891 i = 0; 1892 1893 if (cy != 0) 1894 { 1895 /* Top rectangle */ 1896 arcl[i].left = prclSrc->left; 1897 arcl[i].top = prclSrc->top; 1898 arcl[i].right = prclSrc->right; 1899 arcl[i].bottom = prclSrc->top + cy; 1900 i++; 1901 } 1902 1903 if (cx != 0) 1904 { 1905 /* Left rectangle */ 1906 arcl[i].left = prclSrc->left; 1907 arcl[i].top = prclSrc->top + cy; 1908 arcl[i].right = prclSrc->left + cx; 1909 arcl[i].bottom = prclSrc->bottom - cy; 1910 i++; 1911 1912 /* Right rectangle */ 1913 arcl[i].left = prclSrc->right - cx; 1914 arcl[i].top = prclSrc->top + cy; 1915 arcl[i].right = prclSrc->right; 1916 arcl[i].bottom = prclSrc->bottom - cy; 1917 i++; 1918 } 1919 1920 if (cy != 0) 1921 { 1922 /* Bottom rectangle */ 1923 arcl[i].left = prclSrc->left; 1924 arcl[i].top = prclSrc->bottom - cy; 1925 arcl[i].right = prclSrc->right; 1926 arcl[i].bottom = prclSrc->bottom; 1927 i++; 1928 } 1929 1930 if (i != 0) 1931 { 1932 /* The frame results in a complex region. rcBounds remains 1933 the same, though. */ 1934 prgn->rdh.nCount = i; 1935 NT_ASSERT(prgn->rdh.nCount > 1); 1936 prgn->rdh.nRgnSize = prgn->rdh.nCount * sizeof(RECT); 1937 NT_ASSERT(prgn->Buffer == &prgn->rdh.rcBound); 1938 prgn->Buffer = ExAllocatePoolWithTag(PagedPool, 1939 prgn->rdh.nRgnSize, 1940 TAG_REGION); 1941 if (prgn->Buffer == NULL) 1942 { 1943 prgn->rdh.nRgnSize = 0; 1944 return FALSE; 1945 } 1946 1947 _PRAGMA_WARNING_SUPPRESS(__WARNING_MAYBE_UNINIT_VAR) // arcl is initialized 1948 COPY_RECTS(prgn->Buffer, arcl, prgn->rdh.nCount); 1949 } 1950 1951 return TRUE; 1952 } 1953 1954 static 1955 BOOL 1956 REGION_bMakeFrameRegion( 1957 _Inout_ PREGION prgnDest, 1958 _Inout_ PREGION prgnSrc, 1959 _In_ INT cx, 1960 _In_ INT cy) 1961 { 1962 /* Handle negative cx / cy */ 1963 cx = abs(cx); 1964 cy = abs(cy); 1965 1966 /* Check border size (the cast is necessary to catch cx/cy == INT_MIN!) */ 1967 if (((UINT)cx > MAX_COORD) || ((UINT)cy > MAX_COORD)) 1968 { 1969 return FALSE; 1970 } 1971 1972 /* Fail on empty source region */ 1973 if (!REGION_NOT_EMPTY(prgnSrc)) 1974 { 1975 return FALSE; 1976 } 1977 1978 /* Handle trivial case */ 1979 if ((cx == 0) && (cy == 0)) 1980 { 1981 EMPTY_REGION(prgnDest); 1982 return TRUE; 1983 } 1984 1985 /* Handle simple source region */ 1986 if (REGION_Complexity(prgnSrc) == SIMPLEREGION) 1987 { 1988 return REGION_bMakeSimpleFrameRgn(prgnDest, &prgnSrc->rdh.rcBound, cx, cy); 1989 } 1990 1991 /* Check if we can move the region to create the frame region */ 1992 if ((prgnSrc->rdh.rcBound.left < (MIN_COORD + cx)) || 1993 (prgnSrc->rdh.rcBound.top < (MIN_COORD + cy)) || 1994 (prgnSrc->rdh.rcBound.right > (MAX_COORD - cx)) || 1995 (prgnSrc->rdh.rcBound.bottom > (MAX_COORD - cy))) 1996 { 1997 return FALSE; 1998 } 1999 2000 /* Copy the source region */ 2001 if (!REGION_CopyRegion(prgnDest, prgnSrc)) 2002 { 2003 return FALSE; 2004 } 2005 2006 /* Move the source region to the bottom-right */ 2007 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, cx, cy)); 2008 2009 /* Intersect with the source region (this crops the top-left frame) */ 2010 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc); 2011 2012 /* Move the source region to the bottom-left */ 2013 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, -2 * cx, 0)); 2014 2015 /* Intersect with the source region (this crops the top-right frame) */ 2016 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc); 2017 2018 /* Move the source region to the top-left */ 2019 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, 0, -2 * cy)); 2020 2021 /* Intersect with the source region (this crops the bottom-right frame) */ 2022 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc); 2023 2024 /* Move the source region to the top-right */ 2025 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, 2 * cx, 0)); 2026 2027 /* Intersect with the source region (this crops the bottom-left frame) */ 2028 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc); 2029 2030 /* Move the source region back to the original position */ 2031 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, -cx, cy)); 2032 2033 /* Finally subtract the cropped region from the source */ 2034 REGION_SubtractRegion(prgnDest, prgnSrc, prgnDest); 2035 2036 return TRUE; 2037 } 2038 2039 HRGN 2040 FASTCALL 2041 GreCreateFrameRgn( 2042 HRGN hrgn, 2043 INT cx, 2044 INT cy) 2045 { 2046 PREGION prgnFrame, prgnSrc; 2047 HRGN hrgnFrame; 2048 2049 /* Allocate a new region */ 2050 prgnFrame = REGION_AllocUserRgnWithHandle(1); 2051 if (prgnFrame == NULL) 2052 { 2053 EngSetLastError(ERROR_NOT_ENOUGH_MEMORY); 2054 return NULL; 2055 } 2056 2057 /* Lock the source region */ 2058 prgnSrc = REGION_LockRgn(hrgn); 2059 if (prgnSrc == NULL) 2060 { 2061 REGION_Delete(prgnFrame); 2062 return FALSE; 2063 } 2064 2065 if (REGION_bMakeFrameRegion(prgnFrame, prgnSrc, cx, cy)) 2066 { 2067 hrgnFrame = prgnFrame->BaseObject.hHmgr; 2068 REGION_UnlockRgn(prgnFrame); 2069 } 2070 else 2071 { 2072 REGION_Delete(prgnFrame); 2073 hrgnFrame = NULL; 2074 } 2075 2076 REGION_UnlockRgn(prgnSrc); 2077 return hrgnFrame; 2078 } 2079 2080 BOOL 2081 FASTCALL 2082 REGION_bXformRgn( 2083 _Inout_ PREGION prgn, 2084 _In_ PMATRIX pmx) 2085 { 2086 XFORMOBJ xo; 2087 ULONG i, cjSize; 2088 PPOINT ppt; 2089 PULONG pcPoints; 2090 RECT rect; 2091 BOOL bResult; 2092 2093 /* Check for zero rectangles and return TRUE for translation only matrices */ 2094 if (prgn->rdh.nCount < 1) 2095 return (pmx->flAccel & XFORM_UNITY) != 0; 2096 2097 /* Check if this is a scaling only matrix (off-diagonal elements are 0 */ 2098 if (pmx->flAccel & XFORM_SCALE) 2099 { 2100 /* Check if this is a translation only matrix */ 2101 if (pmx->flAccel & XFORM_UNITY) 2102 { 2103 /* Just offset the region */ 2104 return REGION_bOffsetRgn(prgn, (pmx->fxDx + 8) / 16, (pmx->fxDy + 8) / 16); 2105 } 2106 else 2107 { 2108 /* Initialize the xform object */ 2109 XFORMOBJ_vInit(&xo, pmx); 2110 2111 /* Scaling can move the rects out of the coordinate space, so 2112 * we first need to check whether we can apply the transformation 2113 * on the bounds rect without modifying the region */ 2114 if (!XFORMOBJ_bApplyXform(&xo, XF_LTOL, 2, &prgn->rdh.rcBound, &rect)) 2115 { 2116 return FALSE; 2117 } 2118 2119 /* Apply the xform to the rects in the region */ 2120 if (!XFORMOBJ_bApplyXform(&xo, 2121 XF_LTOL, 2122 prgn->rdh.nCount * 2, 2123 prgn->Buffer, 2124 prgn->Buffer)) 2125 { 2126 /* This can not happen, since we already checked the bounds! */ 2127 NT_ASSERT(FALSE); 2128 } 2129 2130 /* Reset bounds */ 2131 RECTL_vSetEmptyRect(&prgn->rdh.rcBound); 2132 2133 /* Loop all rects in the region */ 2134 for (i = 0; i < prgn->rdh.nCount; i++) 2135 { 2136 /* Make sure the rect is well-ordered after the xform */ 2137 RECTL_vMakeWellOrdered(&prgn->Buffer[i]); 2138 2139 /* Update bounds */ 2140 if (!RECTL_bUnionRect(&prgn->rdh.rcBound, 2141 &prgn->rdh.rcBound, 2142 &prgn->Buffer[i])) 2143 { 2144 DPRINT1("NULL Set in Union Rects\n"); 2145 return FALSE; 2146 } 2147 } 2148 2149 /* Loop all rects in the region */ 2150 for (i = 0; i < prgn->rdh.nCount - 1; i++) 2151 { 2152 NT_ASSERT(prgn->Buffer[i].top <= prgn->Buffer[i].bottom); 2153 NT_ASSERT(prgn->Buffer[i + 1].top >= prgn->Buffer[i].top); 2154 } 2155 2156 return TRUE; 2157 } 2158 } 2159 else 2160 { 2161 /* Allocate a buffer for the polygons */ 2162 cjSize = prgn->rdh.nCount * (4 * sizeof(POINT) + sizeof(ULONG)); 2163 ppt = ExAllocatePoolWithTag(PagedPool, cjSize, GDITAG_REGION); 2164 if (ppt == NULL) 2165 { 2166 return FALSE; 2167 } 2168 2169 /* Fill the buffer with the rects */ 2170 pcPoints = (PULONG)&ppt[4 * prgn->rdh.nCount]; 2171 for (i = 0; i < prgn->rdh.nCount; i++) 2172 { 2173 /* Make sure the rect is within the legal range */ 2174 pcPoints[i] = 4; 2175 ppt[4 * i + 0].x = prgn->Buffer[i].left; 2176 ppt[4 * i + 0].y = prgn->Buffer[i].top; 2177 ppt[4 * i + 1].x = prgn->Buffer[i].right; 2178 ppt[4 * i + 1].y = prgn->Buffer[i].top; 2179 ppt[4 * i + 2].x = prgn->Buffer[i].right; 2180 ppt[4 * i + 2].y = prgn->Buffer[i].bottom; 2181 ppt[4 * i + 3].x = prgn->Buffer[i].left; 2182 ppt[4 * i + 3].y = prgn->Buffer[i].bottom; 2183 } 2184 2185 /* Initialize the xform object */ 2186 XFORMOBJ_vInit(&xo, pmx); 2187 2188 /* Apply the xform to the rects in the buffer */ 2189 if (!XFORMOBJ_bApplyXform(&xo, 2190 XF_LTOL, 2191 prgn->rdh.nCount * 2, 2192 ppt, 2193 ppt)) 2194 { 2195 /* This means, there were coordinates that would go outside of 2196 the coordinate space after the transformation */ 2197 ExFreePoolWithTag(ppt, GDITAG_REGION); 2198 return FALSE; 2199 } 2200 2201 /* Now use the polygons to create a polygon region */ 2202 bResult = REGION_SetPolyPolygonRgn(prgn, 2203 ppt, 2204 pcPoints, 2205 prgn->rdh.nCount, 2206 WINDING); 2207 2208 /* Free the polygon buffer */ 2209 ExFreePoolWithTag(ppt, GDITAG_REGION); 2210 2211 return bResult; 2212 } 2213 2214 } 2215 2216 2217 PREGION 2218 FASTCALL 2219 REGION_AllocRgnWithHandle( 2220 INT nReg) 2221 { 2222 //HRGN hReg; 2223 PREGION pReg; 2224 2225 pReg = (PREGION)GDIOBJ_AllocateObject(GDIObjType_RGN_TYPE, 2226 sizeof(REGION), 2227 BASEFLAG_LOOKASIDE); 2228 if (pReg == NULL) 2229 { 2230 DPRINT1("Could not allocate a palette.\n"); 2231 return NULL; 2232 } 2233 2234 //hReg = pReg->BaseObject.hHmgr; 2235 2236 if ((nReg == 0) || (nReg == 1)) 2237 { 2238 /* Testing shows that > 95% of all regions have only 1 rect. 2239 Including that here saves us from having to do another allocation */ 2240 pReg->Buffer = &pReg->rdh.rcBound; 2241 } 2242 else 2243 { 2244 pReg->Buffer = ExAllocatePoolWithTag(PagedPool, 2245 nReg * sizeof(RECT), 2246 TAG_REGION); 2247 if (pReg->Buffer == NULL) 2248 { 2249 DPRINT1("Could not allocate region buffer\n"); 2250 GDIOBJ_vDeleteObject(&pReg->BaseObject); 2251 return NULL; 2252 } 2253 } 2254 2255 EMPTY_REGION(pReg); 2256 pReg->rdh.dwSize = sizeof(RGNDATAHEADER); 2257 pReg->rdh.nCount = nReg; 2258 pReg->rdh.nRgnSize = nReg * sizeof(RECT); 2259 pReg->prgnattr = &pReg->rgnattr; 2260 2261 /* Initialize the region attribute */ 2262 pReg->rgnattr.AttrFlags = 0; 2263 pReg->rgnattr.iComplexity = SIMPLEREGION; 2264 pReg->rgnattr.Rect = pReg->rdh.rcBound; 2265 2266 /* Finally insert the region into the handle table */ 2267 if (!GDIOBJ_hInsertObject(&pReg->BaseObject, GDI_OBJ_HMGR_POWNED)) 2268 { 2269 DPRINT1("Could not insert palette into handle table.\n"); 2270 GDIOBJ_vFreeObject(&pReg->BaseObject); 2271 return NULL; 2272 } 2273 2274 return pReg; 2275 } 2276 2277 BOOL 2278 NTAPI 2279 REGION_bAllocRgnAttr( 2280 PREGION prgn) 2281 { 2282 PPROCESSINFO ppi; 2283 PRGN_ATTR prgnattr; 2284 2285 NT_ASSERT(prgn->prgnattr == &prgn->rgnattr); 2286 2287 ppi = PsGetCurrentProcessWin32Process(); 2288 ASSERT(ppi); 2289 2290 prgnattr = GdiPoolAllocate(ppi->pPoolRgnAttr); 2291 if (prgnattr == NULL) 2292 { 2293 DPRINT1("Could not allocate RGN attr\n"); 2294 return FALSE; 2295 } 2296 2297 /* Copy the current region attribute */ 2298 *prgnattr = prgn->rgnattr; 2299 2300 /* Set the object attribute in the handle table */ 2301 prgn->prgnattr = prgnattr; 2302 GDIOBJ_vSetObjectAttr(&prgn->BaseObject, prgnattr); 2303 2304 return TRUE; 2305 } 2306 2307 2308 // 2309 // Allocate User Space Region Handle. 2310 // 2311 PREGION 2312 FASTCALL 2313 REGION_AllocUserRgnWithHandle( 2314 INT nRgn) 2315 { 2316 PREGION prgn; 2317 2318 prgn = REGION_AllocRgnWithHandle(nRgn); 2319 if (prgn == NULL) 2320 { 2321 return NULL; 2322 } 2323 2324 if (!REGION_bAllocRgnAttr(prgn)) 2325 { 2326 ASSERT(FALSE); 2327 } 2328 2329 return prgn; 2330 } 2331 2332 static 2333 VOID 2334 REGION_vSyncRegion( 2335 _In_ PREGION prgn) 2336 { 2337 PRGN_ATTR prgnattr; 2338 2339 NT_ASSERT(prgn != NULL); 2340 NT_ASSERT(prgn->prgnattr != NULL); 2341 NT_ASSERT((prgn->prgnattr == &prgn->rgnattr) || 2342 (prgn->prgnattr->AttrFlags & ATTR_RGN_VALID)); 2343 2344 /* Get the region attribute and check if it's dirty (modified) */ 2345 prgnattr = prgn->prgnattr; 2346 if (prgnattr->AttrFlags & ATTR_RGN_DIRTY) 2347 { 2348 NT_ASSERT(GreGetObjectOwner(prgn->BaseObject.hHmgr) == GDI_OBJ_HMGR_POWNED); 2349 NT_ASSERT(prgnattr != &prgn->rgnattr); 2350 2351 if (prgnattr->iComplexity == NULLREGION) 2352 { 2353 EMPTY_REGION(prgn); 2354 } 2355 else if (prgnattr->iComplexity == SIMPLEREGION) 2356 { 2357 REGION_SetRectRgn(prgn, 2358 prgnattr->Rect.left, 2359 prgnattr->Rect.top, 2360 prgnattr->Rect.right, 2361 prgnattr->Rect.bottom); 2362 } 2363 else 2364 { 2365 /* Should not happen, region attribute is corrupted! */ 2366 DPRINT1("Region attribute is corrupted, ignoring\n"); 2367 NT_ASSERT(FALSE); 2368 } 2369 } 2370 2371 /* Reset the flags */ 2372 prgnattr->AttrFlags &= ~(ATTR_RGN_DIRTY | ATTR_RGN_VALID); 2373 } 2374 2375 PREGION 2376 FASTCALL 2377 REGION_LockRgn( 2378 _In_ HRGN hrgn) 2379 { 2380 PREGION prgn; 2381 2382 prgn = GDIOBJ_LockObject(hrgn, GDIObjType_RGN_TYPE); 2383 if (prgn == NULL) 2384 return NULL; 2385 2386 REGION_vSyncRegion(prgn); 2387 return prgn; 2388 } 2389 2390 VOID 2391 FASTCALL 2392 REGION_UnlockRgn( 2393 _In_ PREGION prgn) 2394 { 2395 PRGN_ATTR prgnattr; 2396 2397 NT_ASSERT(prgn != NULL); 2398 NT_ASSERT(prgn->prgnattr != NULL); 2399 2400 /* Get the region attribute and check if it's user mode */ 2401 prgnattr = prgn->prgnattr; 2402 if (prgnattr != &prgn->rgnattr) 2403 { 2404 NT_ASSERT(GreGetObjectOwner(prgn->BaseObject.hHmgr) == GDI_OBJ_HMGR_POWNED); 2405 prgnattr->iComplexity = REGION_Complexity(prgn); 2406 prgnattr->Rect.left = prgn->rdh.rcBound.left; 2407 prgnattr->Rect.top = prgn->rdh.rcBound.top; 2408 prgnattr->Rect.right = prgn->rdh.rcBound.right; 2409 prgnattr->Rect.bottom = prgn->rdh.rcBound.bottom; 2410 prgnattr->AttrFlags |= ATTR_RGN_VALID; 2411 } 2412 2413 GDIOBJ_vUnlockObject(&prgn->BaseObject); 2414 } 2415 2416 /* 2417 System Regions: 2418 These regions do not use attribute sections and when allocated, use gdiobj 2419 level functions. 2420 */ 2421 // 2422 // System Region Functions 2423 // 2424 PREGION 2425 FASTCALL 2426 IntSysCreateRectpRgn( 2427 INT LeftRect, 2428 INT TopRect, 2429 INT RightRect, 2430 INT BottomRect) 2431 { 2432 PREGION prgn; 2433 2434 /* Allocate a region, without a handle */ 2435 prgn = (PREGION)GDIOBJ_AllocateObject(GDIObjType_RGN_TYPE, sizeof(REGION), BASEFLAG_LOOKASIDE); 2436 if (prgn == NULL) 2437 { 2438 return NULL; 2439 } 2440 2441 /* Initialize it */ 2442 prgn->Buffer = &prgn->rdh.rcBound; 2443 prgn->prgnattr = &prgn->rgnattr; 2444 prgn->prgnattr->AttrFlags = ATTR_RGN_VALID; 2445 REGION_SetRectRgn(prgn, LeftRect, TopRect, RightRect, BottomRect); 2446 2447 return prgn; 2448 } 2449 2450 VOID 2451 NTAPI 2452 REGION_vCleanup(PVOID ObjectBody) 2453 { 2454 PREGION pRgn = (PREGION)ObjectBody; 2455 PPROCESSINFO ppi = PsGetCurrentProcessWin32Process(); 2456 ASSERT(ppi); 2457 2458 ASSERT(pRgn->prgnattr); 2459 if (pRgn->prgnattr != &pRgn->rgnattr) 2460 GdiPoolFree(ppi->pPoolRgnAttr, pRgn->prgnattr); 2461 2462 if (pRgn->Buffer && pRgn->Buffer != &pRgn->rdh.rcBound) 2463 ExFreePoolWithTag(pRgn->Buffer, TAG_REGION); 2464 } 2465 2466 VOID 2467 FASTCALL 2468 REGION_Delete(PREGION pRgn) 2469 { 2470 if (pRgn == prgnDefault) 2471 return; 2472 2473 GDIOBJ_vDeleteObject(&pRgn->BaseObject); 2474 } 2475 2476 BOOL 2477 FASTCALL 2478 IntGdiSetRegionOwner(HRGN hRgn, DWORD OwnerMask) 2479 { 2480 PREGION prgn; 2481 PRGN_ATTR prgnattr; 2482 PPROCESSINFO ppi; 2483 2484 prgn = REGION_LockRgn(hRgn); 2485 if (prgn == NULL) 2486 { 2487 return FALSE; 2488 } 2489 2490 prgnattr = prgn->prgnattr; 2491 if (prgnattr != &prgn->rgnattr) 2492 { 2493 GDIOBJ_vSetObjectAttr(&prgn->BaseObject, NULL); 2494 prgn->prgnattr = &prgn->rgnattr; 2495 ppi = PsGetCurrentProcessWin32Process(); 2496 GdiPoolFree(ppi->pPoolRgnAttr, prgnattr); 2497 } 2498 2499 REGION_UnlockRgn(prgn); 2500 2501 return GreSetObjectOwner(hRgn, OwnerMask); 2502 } 2503 2504 INT 2505 FASTCALL 2506 IntGdiCombineRgn( 2507 PREGION prgnDest, 2508 PREGION prgnSrc1, 2509 PREGION prgnSrc2, 2510 INT iCombineMode) 2511 { 2512 BOOL Ret = TRUE; 2513 2514 if (prgnDest == NULL) 2515 { 2516 DPRINT("IntGdiCombineRgn: hDest unavailable\n"); 2517 return ERROR; 2518 } 2519 2520 if (prgnSrc1 == NULL) 2521 { 2522 DPRINT("IntGdiCombineRgn: hSrc1 unavailable\n"); 2523 return ERROR; 2524 } 2525 2526 if (iCombineMode == RGN_COPY) 2527 { 2528 if (!REGION_CopyRegion(prgnDest, prgnSrc1)) 2529 return ERROR; 2530 2531 return REGION_Complexity(prgnDest); 2532 } 2533 2534 if (prgnSrc2 == NULL) 2535 { 2536 DPRINT1("IntGdiCombineRgn requires hSrc2 != NULL for combine mode %d!\n", iCombineMode); 2537 ASSERT(FALSE); 2538 return ERROR; 2539 } 2540 2541 switch (iCombineMode) 2542 { 2543 case RGN_AND: 2544 Ret = REGION_IntersectRegion(prgnDest, prgnSrc1, prgnSrc2); 2545 break; 2546 case RGN_OR: 2547 Ret = REGION_UnionRegion(prgnDest, prgnSrc1, prgnSrc2); 2548 break; 2549 case RGN_XOR: 2550 Ret = REGION_XorRegion(prgnDest, prgnSrc1, prgnSrc2); 2551 break; 2552 case RGN_DIFF: 2553 Ret = REGION_SubtractRegion(prgnDest, prgnSrc1, prgnSrc2); 2554 break; 2555 } 2556 2557 return Ret ? REGION_Complexity(prgnDest) : ERROR; 2558 } 2559 2560 INT 2561 FASTCALL 2562 REGION_GetRgnBox( 2563 PREGION Rgn, 2564 PRECTL pRect) 2565 { 2566 DWORD ret; 2567 2568 if (Rgn != NULL) 2569 { 2570 *pRect = Rgn->rdh.rcBound; 2571 ret = REGION_Complexity(Rgn); 2572 2573 return ret; 2574 } 2575 return 0; // If invalid region return zero 2576 } 2577 2578 INT 2579 APIENTRY 2580 IntGdiGetRgnBox( 2581 HRGN hRgn, 2582 PRECTL pRect) 2583 { 2584 PREGION Rgn; 2585 DWORD ret; 2586 2587 Rgn = REGION_LockRgn(hRgn); 2588 if (Rgn == NULL) 2589 { 2590 return ERROR; 2591 } 2592 2593 ret = REGION_GetRgnBox(Rgn, pRect); 2594 REGION_UnlockRgn(Rgn); 2595 2596 return ret; 2597 } 2598 2599 2600 BOOL 2601 FASTCALL 2602 REGION_PtInRegion( 2603 PREGION prgn, 2604 INT X, 2605 INT Y) 2606 { 2607 ULONG i; 2608 PRECT r; 2609 2610 if (prgn->rdh.nCount > 0 && INRECT(prgn->rdh.rcBound, X, Y)) 2611 { 2612 r = prgn->Buffer; 2613 for (i = 0; i < prgn->rdh.nCount; i++) 2614 { 2615 if (INRECT(r[i], X, Y)) 2616 return TRUE; 2617 } 2618 } 2619 2620 return FALSE; 2621 } 2622 2623 BOOL 2624 FASTCALL 2625 REGION_RectInRegion( 2626 PREGION Rgn, 2627 const RECTL *rect) 2628 { 2629 PRECTL pCurRect, pRectEnd; 2630 RECT rc; 2631 2632 /* Swap the coordinates to make right >= left and bottom >= top */ 2633 /* (region building rectangles are normalized the same way) */ 2634 if (rect->top > rect->bottom) 2635 { 2636 rc.top = rect->bottom; 2637 rc.bottom = rect->top; 2638 } 2639 else 2640 { 2641 rc.top = rect->top; 2642 rc.bottom = rect->bottom; 2643 } 2644 2645 if (rect->right < rect->left) 2646 { 2647 rc.right = rect->left; 2648 rc.left = rect->right; 2649 } 2650 else 2651 { 2652 rc.right = rect->right; 2653 rc.left = rect->left; 2654 } 2655 2656 /* This is (just) a useful optimization */ 2657 if ((Rgn->rdh.nCount > 0) && EXTENTCHECK(&Rgn->rdh.rcBound, &rc)) 2658 { 2659 for (pCurRect = Rgn->Buffer, pRectEnd = pCurRect + 2660 Rgn->rdh.nCount; pCurRect < pRectEnd; pCurRect++) 2661 { 2662 if (pCurRect->bottom <= rc.top) 2663 continue; /* Not far enough down yet */ 2664 2665 if (pCurRect->top >= rc.bottom) 2666 break; /* Too far down */ 2667 2668 if (pCurRect->right <= rc.left) 2669 continue; /* Not far enough over yet */ 2670 2671 if (pCurRect->left >= rc.right) 2672 { 2673 continue; 2674 } 2675 2676 return TRUE; 2677 } 2678 } 2679 2680 return FALSE; 2681 } 2682 2683 VOID 2684 FASTCALL 2685 REGION_SetRectRgn( 2686 PREGION rgn, 2687 INT LeftRect, 2688 INT TopRect, 2689 INT RightRect, 2690 INT BottomRect) 2691 { 2692 PRECTL firstRect; 2693 2694 if (LeftRect > RightRect) 2695 { 2696 INT tmp = LeftRect; 2697 LeftRect = RightRect; 2698 RightRect = tmp; 2699 } 2700 2701 if (TopRect > BottomRect) 2702 { 2703 INT tmp = TopRect; 2704 TopRect = BottomRect; 2705 BottomRect = tmp; 2706 } 2707 2708 if ((LeftRect != RightRect) && (TopRect != BottomRect)) 2709 { 2710 firstRect = rgn->Buffer; 2711 ASSERT(firstRect); 2712 firstRect->left = rgn->rdh.rcBound.left = LeftRect; 2713 firstRect->top = rgn->rdh.rcBound.top = TopRect; 2714 firstRect->right = rgn->rdh.rcBound.right = RightRect; 2715 firstRect->bottom = rgn->rdh.rcBound.bottom = BottomRect; 2716 rgn->rdh.nCount = 1; 2717 rgn->rdh.iType = RDH_RECTANGLES; 2718 } 2719 else 2720 { 2721 EMPTY_REGION(rgn); 2722 } 2723 } 2724 2725 BOOL 2726 FASTCALL 2727 REGION_bOffsetRgn( 2728 _Inout_ PREGION prgn, 2729 _In_ INT cx, 2730 _In_ INT cy) 2731 { 2732 PRECTL prcl; 2733 UINT i; 2734 2735 NT_ASSERT(prgn != NULL); 2736 2737 /* Check for trivial case */ 2738 if ((cx == 0) && (cy == 0)) 2739 { 2740 return TRUE; 2741 } 2742 2743 /* Check for empty regions, we ignore the offset values here */ 2744 if (prgn->rdh.nCount == 0) 2745 { 2746 return TRUE; 2747 } 2748 2749 /* Make sure the offset is within the legal range */ 2750 if ((cx > MAX_COORD) || (cx < MIN_COORD) || 2751 (cy > MAX_COORD) || (cy < MIN_COORD)) 2752 { 2753 return FALSE; 2754 } 2755 2756 /* Are we moving right? */ 2757 if (cx > 0) 2758 { 2759 /* Check if we stay inside the bounds on the right side */ 2760 if (prgn->rdh.rcBound.right > (MAX_COORD - cx)) 2761 { 2762 return FALSE; 2763 } 2764 } 2765 else 2766 { 2767 /* Check if we stay inside the bounds on the left side */ 2768 if (prgn->rdh.rcBound.left < (MIN_COORD - cx)) 2769 { 2770 return FALSE; 2771 } 2772 } 2773 2774 /* Are we moving down? */ 2775 if (cy > 0) 2776 { 2777 /* Check if we stay inside the bounds on the right side */ 2778 if (prgn->rdh.rcBound.bottom > (MAX_COORD - cy)) 2779 { 2780 return FALSE; 2781 } 2782 } 2783 else 2784 { 2785 /* Check if we stay inside the bounds on the left side */ 2786 if (prgn->rdh.rcBound.top < (MIN_COORD - cy)) 2787 { 2788 return FALSE; 2789 } 2790 } 2791 2792 /* Loop to move the rects */ 2793 prcl = prgn->Buffer; 2794 for (i = 0; i < prgn->rdh.nCount; i++) 2795 { 2796 prcl[i].left += cx; 2797 prcl[i].right += cx; 2798 prcl[i].top += cy; 2799 prcl[i].bottom += cy; 2800 } 2801 2802 /* Finally update the bounds rect */ 2803 if (prgn->Buffer != &prgn->rdh.rcBound) 2804 { 2805 prgn->rdh.rcBound.left += cx; 2806 prgn->rdh.rcBound.right += cx; 2807 prgn->rdh.rcBound.top += cy; 2808 prgn->rdh.rcBound.bottom += cy; 2809 } 2810 2811 return TRUE; 2812 } 2813 2814 /*********************************************************************** 2815 * REGION_InsertEdgeInET 2816 * 2817 * Insert the given edge into the edge table. 2818 * First we must find the correct bucket in the 2819 * Edge table, then find the right slot in the 2820 * bucket. Finally, we can insert it. 2821 * 2822 */ 2823 static 2824 VOID 2825 FASTCALL 2826 REGION_InsertEdgeInET( 2827 EDGE_TABLE *ET, 2828 EDGE_TABLE_ENTRY *ETE, 2829 INT scanline, 2830 SCANLINE_LISTBLOCK **SLLBlock, 2831 INT *iSLLBlock) 2832 { 2833 EDGE_TABLE_ENTRY *start, *prev; 2834 SCANLINE_LIST *pSLL, *pPrevSLL; 2835 SCANLINE_LISTBLOCK *tmpSLLBlock; 2836 2837 /* Find the right bucket to put the edge into */ 2838 pPrevSLL = &ET->scanlines; 2839 pSLL = pPrevSLL->next; 2840 while (pSLL && (pSLL->scanline < scanline)) 2841 { 2842 pPrevSLL = pSLL; 2843 pSLL = pSLL->next; 2844 } 2845 2846 /* Reassign pSLL (pointer to SCANLINE_LIST) if necessary */ 2847 if ((!pSLL) || (pSLL->scanline > scanline)) 2848 { 2849 if (*iSLLBlock > SLLSPERBLOCK-1) 2850 { 2851 tmpSLLBlock = ExAllocatePoolWithTag(PagedPool, 2852 sizeof(SCANLINE_LISTBLOCK), 2853 TAG_REGION); 2854 if (tmpSLLBlock == NULL) 2855 { 2856 DPRINT1("REGION_InsertEdgeInETL(): Can't alloc SLLB\n"); 2857 /* FIXME: Free resources? */ 2858 return; 2859 } 2860 2861 (*SLLBlock)->next = tmpSLLBlock; 2862 tmpSLLBlock->next = (SCANLINE_LISTBLOCK *)NULL; 2863 *SLLBlock = tmpSLLBlock; 2864 *iSLLBlock = 0; 2865 } 2866 2867 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); 2868 2869 pSLL->next = pPrevSLL->next; 2870 pSLL->edgelist = (EDGE_TABLE_ENTRY *)NULL; 2871 pPrevSLL->next = pSLL; 2872 } 2873 2874 pSLL->scanline = scanline; 2875 2876 /* Now insert the edge in the right bucket */ 2877 prev = (EDGE_TABLE_ENTRY *)NULL; 2878 start = pSLL->edgelist; 2879 while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) 2880 { 2881 prev = start; 2882 start = start->next; 2883 } 2884 2885 ETE->next = start; 2886 2887 if (prev) 2888 prev->next = ETE; 2889 else 2890 pSLL->edgelist = ETE; 2891 } 2892 2893 /*********************************************************************** 2894 * REGION_loadAET 2895 * 2896 * This routine moves EDGE_TABLEEntries from the 2897 * EDGE_TABLE into the Active Edge Table, 2898 * leaving them sorted by smaller x coordinate. 2899 * 2900 */ 2901 static 2902 VOID 2903 FASTCALL 2904 REGION_loadAET( 2905 EDGE_TABLE_ENTRY *AET, 2906 EDGE_TABLE_ENTRY *ETEs) 2907 { 2908 EDGE_TABLE_ENTRY *pPrevAET; 2909 EDGE_TABLE_ENTRY *tmp; 2910 2911 pPrevAET = AET; 2912 AET = AET->next; 2913 while (ETEs) 2914 { 2915 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis)) 2916 { 2917 pPrevAET = AET; 2918 AET = AET->next; 2919 } 2920 2921 tmp = ETEs->next; 2922 ETEs->next = AET; 2923 if (AET) 2924 AET->back = ETEs; 2925 2926 ETEs->back = pPrevAET; 2927 pPrevAET->next = ETEs; 2928 pPrevAET = ETEs; 2929 2930 ETEs = tmp; 2931 } 2932 } 2933 2934 /*********************************************************************** 2935 * REGION_computeWAET 2936 * 2937 * This routine links the AET by the 2938 * nextWETE (winding EDGE_TABLE_ENTRY) link for 2939 * use by the winding number rule. The final 2940 * Active Edge Table (AET) might look something 2941 * like: 2942 * 2943 * AET 2944 * ---------- --------- --------- 2945 * |ymax | |ymax | |ymax | 2946 * | ... | |... | |... | 2947 * |next |->|next |->|next |->... 2948 * |nextWETE| |nextWETE| |nextWETE| 2949 * --------- --------- ^-------- 2950 * | | | 2951 * V-------------------> V---> ... 2952 * 2953 */ 2954 static 2955 VOID 2956 FASTCALL 2957 REGION_computeWAET( 2958 EDGE_TABLE_ENTRY *AET) 2959 { 2960 register EDGE_TABLE_ENTRY *pWETE; 2961 register INT inside = 1; 2962 register INT isInside = 0; 2963 2964 AET->nextWETE = (EDGE_TABLE_ENTRY *)NULL; 2965 pWETE = AET; 2966 AET = AET->next; 2967 while (AET) 2968 { 2969 if (AET->ClockWise) 2970 isInside++; 2971 else 2972 isInside--; 2973 2974 if ((!inside && !isInside) || 2975 ( inside && isInside)) 2976 { 2977 pWETE->nextWETE = AET; 2978 pWETE = AET; 2979 inside = !inside; 2980 } 2981 AET = AET->next; 2982 } 2983 2984 pWETE->nextWETE = (EDGE_TABLE_ENTRY *)NULL; 2985 } 2986 2987 /*********************************************************************** 2988 * REGION_InsertionSort 2989 * 2990 * Just a simple insertion sort using 2991 * pointers and back pointers to sort the Active 2992 * Edge Table. 2993 * 2994 */ 2995 static 2996 BOOL 2997 FASTCALL 2998 REGION_InsertionSort( 2999 EDGE_TABLE_ENTRY *AET) 3000 { 3001 EDGE_TABLE_ENTRY *pETEchase; 3002 EDGE_TABLE_ENTRY *pETEinsert; 3003 EDGE_TABLE_ENTRY *pETEchaseBackTMP; 3004 BOOL changed = FALSE; 3005 3006 AET = AET->next; 3007 while (AET) 3008 { 3009 pETEinsert = AET; 3010 pETEchase = AET; 3011 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis) 3012 pETEchase = pETEchase->back; 3013 3014 AET = AET->next; 3015 if (pETEchase != pETEinsert) 3016 { 3017 pETEchaseBackTMP = pETEchase->back; 3018 pETEinsert->back->next = AET; 3019 if (AET) 3020 AET->back = pETEinsert->back; 3021 3022 pETEinsert->next = pETEchase; 3023 pETEchase->back->next = pETEinsert; 3024 pETEchase->back = pETEinsert; 3025 pETEinsert->back = pETEchaseBackTMP; 3026 changed = TRUE; 3027 } 3028 } 3029 3030 return changed; 3031 } 3032 3033 /*********************************************************************** 3034 * REGION_FreeStorage 3035 * 3036 * Clean up our act. 3037 */ 3038 static 3039 VOID 3040 FASTCALL 3041 REGION_FreeStorage( 3042 SCANLINE_LISTBLOCK *pSLLBlock) 3043 { 3044 SCANLINE_LISTBLOCK *tmpSLLBlock; 3045 3046 while (pSLLBlock) 3047 { 3048 tmpSLLBlock = pSLLBlock->next; 3049 ExFreePoolWithTag(pSLLBlock, TAG_REGION); 3050 pSLLBlock = tmpSLLBlock; 3051 } 3052 } 3053 3054 3055 /*********************************************************************** 3056 * REGION_PtsToRegion 3057 * 3058 * Create an array of rectangles from a list of points. 3059 */ 3060 static 3061 INT 3062 FASTCALL 3063 REGION_PtsToRegion( 3064 INT numFullPtBlocks, 3065 INT iCurPtBlock, 3066 POINTBLOCK *FirstPtBlock, 3067 PREGION reg) 3068 { 3069 RECTL *rects; 3070 POINT *pts; 3071 POINTBLOCK *CurPtBlock; 3072 INT i; 3073 RECTL *extents, *temp; 3074 INT numRects; 3075 3076 extents = ®->rdh.rcBound; 3077 3078 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1; 3079 3080 /* Make sure, we have at least one rect */ 3081 if (numRects == 0) 3082 { 3083 numRects = 1; 3084 } 3085 3086 temp = ExAllocatePoolWithTag(PagedPool, numRects * sizeof(RECT), TAG_REGION); 3087 if (temp == NULL) 3088 { 3089 return 0; 3090 } 3091 3092 if (reg->Buffer != NULL) 3093 { 3094 COPY_RECTS(temp, reg->Buffer, reg->rdh.nCount); 3095 if (reg->Buffer != ®->rdh.rcBound) 3096 ExFreePoolWithTag(reg->Buffer, TAG_REGION); 3097 } 3098 reg->Buffer = temp; 3099 3100 reg->rdh.nCount = numRects; 3101 CurPtBlock = FirstPtBlock; 3102 rects = reg->Buffer - 1; 3103 numRects = 0; 3104 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE; 3105 3106 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) 3107 { 3108 /* The loop uses 2 points per iteration */ 3109 i = NUMPTSTOBUFFER >> 1; 3110 if (numFullPtBlocks == 0) 3111 i = iCurPtBlock >> 1; 3112 3113 for (pts = CurPtBlock->pts; i--; pts += 2) 3114 { 3115 if (pts->x == pts[1].x) 3116 continue; 3117 3118 if ((numRects && pts->x == rects->left) && 3119 (pts->y == rects->bottom) && 3120 (pts[1].x == rects->right) && 3121 ((numRects == 1) || (rects[-1].top != rects->top)) && 3122 (i && pts[2].y > pts[1].y)) 3123 { 3124 rects->bottom = pts[1].y + 1; 3125 continue; 3126 } 3127 3128 numRects++; 3129 rects++; 3130 rects->left = pts->x; 3131 rects->top = pts->y; 3132 rects->right = pts[1].x; 3133 rects->bottom = pts[1].y + 1; 3134 3135 if (rects->left < extents->left) 3136 extents->left = rects->left; 3137 if (rects->right > extents->right) 3138 extents->right = rects->right; 3139 } 3140 3141 CurPtBlock = CurPtBlock->next; 3142 } 3143 3144 if (numRects) 3145 { 3146 extents->top = reg->Buffer->top; 3147 extents->bottom = rects->bottom; 3148 } 3149 else 3150 { 3151 extents->left = 0; 3152 extents->top = 0; 3153 extents->right = 0; 3154 extents->bottom = 0; 3155 } 3156 3157 reg->rdh.nCount = numRects; 3158 3159 return(TRUE); 3160 } 3161 3162 /*********************************************************************** 3163 * REGION_CreateETandAET 3164 * 3165 * This routine creates the edge table for 3166 * scan converting polygons. 3167 * The Edge Table (ET) looks like: 3168 * 3169 * EDGE_TABLE 3170 * -------- 3171 * | ymax | SCANLINE_LISTs 3172 * |scanline|-->------------>-------------->... 3173 * -------- |scanline| |scanline| 3174 * |edgelist| |edgelist| 3175 * --------- --------- 3176 * | | 3177 * | | 3178 * V V 3179 * list of ETEs list of ETEs 3180 * 3181 * where ETE is an EDGE_TABLE_ENTRY data structure, 3182 * and there is one SCANLINE_LIST per scanline at 3183 * which an edge is initially entered. 3184 * 3185 */ 3186 static 3187 VOID 3188 FASTCALL 3189 REGION_CreateETandAET( 3190 const ULONG *Count, 3191 INT nbpolygons, 3192 const POINT *pts, 3193 EDGE_TABLE *ET, 3194 EDGE_TABLE_ENTRY *AET, 3195 EDGE_TABLE_ENTRY *pETEs, 3196 SCANLINE_LISTBLOCK *pSLLBlock) 3197 { 3198 const POINT *top, *bottom; 3199 const POINT *PrevPt, *CurrPt, *EndPt; 3200 INT poly, count; 3201 INT iSLLBlock = 0; 3202 INT dy; 3203 3204 /* Initialize the Active Edge Table */ 3205 AET->next = (EDGE_TABLE_ENTRY *)NULL; 3206 AET->back = (EDGE_TABLE_ENTRY *)NULL; 3207 AET->nextWETE = (EDGE_TABLE_ENTRY *)NULL; 3208 AET->bres.minor_axis = SMALL_COORDINATE; 3209 3210 /* Initialize the Edge Table. */ 3211 ET->scanlines.next = (SCANLINE_LIST *)NULL; 3212 ET->ymax = SMALL_COORDINATE; 3213 ET->ymin = LARGE_COORDINATE; 3214 pSLLBlock->next = (SCANLINE_LISTBLOCK *)NULL; 3215 3216 EndPt = pts - 1; 3217 for (poly = 0; poly < nbpolygons; poly++) 3218 { 3219 count = Count[poly]; 3220 EndPt += count; 3221 if (count < 2) 3222 continue; 3223 3224 PrevPt = EndPt; 3225 3226 /* For each vertex in the array of points. 3227 * In this loop we are dealing with two vertices at 3228 * a time -- these make up one edge of the polygon. */ 3229 while (count--) 3230 { 3231 CurrPt = pts++; 3232 3233 /* Find out which point is above and which is below. */ 3234 if (PrevPt->y > CurrPt->y) 3235 { 3236 bottom = PrevPt, top = CurrPt; 3237 pETEs->ClockWise = 0; 3238 } 3239 else 3240 { 3241 bottom = CurrPt, top = PrevPt; 3242 pETEs->ClockWise = 1; 3243 } 3244 3245 /* Don't add horizontal edges to the Edge table. */ 3246 if (bottom->y != top->y) 3247 { 3248 /* -1 so we don't get last scanline */ 3249 pETEs->ymax = bottom->y - 1; 3250 3251 /* Initialize integer edge algorithm */ 3252 dy = bottom->y - top->y; 3253 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres); 3254 3255 REGION_InsertEdgeInET(ET, 3256 pETEs, 3257 top->y, 3258 &pSLLBlock, 3259 &iSLLBlock); 3260 3261 if (PrevPt->y > ET->ymax) 3262 ET->ymax = PrevPt->y; 3263 if (PrevPt->y < ET->ymin) 3264 ET->ymin = PrevPt->y; 3265 pETEs++; 3266 } 3267 3268 PrevPt = CurrPt; 3269 } 3270 } 3271 } 3272 3273 BOOL 3274 FASTCALL 3275 REGION_SetPolyPolygonRgn( 3276 _Inout_ PREGION prgn, 3277 _In_ const POINT *ppt, 3278 _In_ const ULONG *pcPoints, 3279 _In_ ULONG cPolygons, 3280 _In_ INT iMode) 3281 { 3282 EDGE_TABLE_ENTRY *pAET; /* Active Edge Table */ 3283 INT y; /* Current scanline */ 3284 INT iPts = 0; /* Number of pts in buffer */ 3285 EDGE_TABLE_ENTRY *pWETE; /* Winding Edge Table Entry */ 3286 SCANLINE_LIST *pSLL; /* Current SCANLINE_LIST */ 3287 POINT *pts; /* Output buffer */ 3288 EDGE_TABLE_ENTRY *pPrevAET; /* Pointer to previous AET */ 3289 EDGE_TABLE ET; /* Header node for ET */ 3290 EDGE_TABLE_ENTRY AET; /* Header node for AET */ 3291 EDGE_TABLE_ENTRY *pETEs; /* EDGE_TABLEEntries pool */ 3292 SCANLINE_LISTBLOCK SLLBlock; /* Header for SCANLINE_LIST */ 3293 INT fixWAET = FALSE; 3294 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */ 3295 POINTBLOCK *tmpPtBlock; 3296 UINT numFullPtBlocks = 0; 3297 UINT poly, total; 3298 BOOL bResult = FALSE; 3299 3300 /* Check if iMode is valid */ 3301 if ((iMode != ALTERNATE) && (iMode != WINDING)) 3302 { 3303 DPRINT1("Invalid iMode: %lu\n", iMode); 3304 return FALSE; 3305 } 3306 3307 /* Special case a rectangle */ 3308 if (((cPolygons == 1) && ((pcPoints[0] == 4) || 3309 ((pcPoints[0] == 5) && (ppt[4].x == ppt[0].x) && (ppt[4].y == ppt[0].y)))) && 3310 (((ppt[0].y == ppt[1].y) && 3311 (ppt[1].x == ppt[2].x) && 3312 (ppt[2].y == ppt[3].y) && 3313 (ppt[3].x == ppt[0].x)) || 3314 ((ppt[0].x == ppt[1].x) && 3315 (ppt[1].y == ppt[2].y) && 3316 (ppt[2].x == ppt[3].x) && 3317 (ppt[3].y == ppt[0].y)))) 3318 { 3319 REGION_SetRectRgn(prgn, 3320 min(ppt[0].x, ppt[2].x), 3321 min(ppt[0].y, ppt[2].y), 3322 max(ppt[0].x, ppt[2].x), 3323 max(ppt[0].y, ppt[2].y)); 3324 return TRUE; 3325 } 3326 3327 for (poly = total = 0; poly < cPolygons; poly++) 3328 total += pcPoints[poly]; 3329 3330 pETEs = ExAllocatePoolWithTag(PagedPool, 3331 sizeof(EDGE_TABLE_ENTRY) * total, 3332 TAG_REGION); 3333 if (pETEs == NULL) 3334 { 3335 DPRINT1("Failed to allocate %lu edge entries\n", total); 3336 return FALSE; 3337 } 3338 3339 pts = FirstPtBlock.pts; 3340 REGION_CreateETandAET(pcPoints, cPolygons, ppt, &ET, &AET, pETEs, &SLLBlock); 3341 pSLL = ET.scanlines.next; 3342 curPtBlock = &FirstPtBlock; 3343 3344 if (iMode != WINDING) 3345 { 3346 /* For each scanline */ 3347 for (y = ET.ymin; y < ET.ymax; y++) 3348 { 3349 /* Add a new edge to the active edge table when we 3350 * get to the next edge. */ 3351 if (pSLL != NULL && y == pSLL->scanline) 3352 { 3353 REGION_loadAET(&AET, pSLL->edgelist); 3354 pSLL = pSLL->next; 3355 } 3356 pPrevAET = &AET; 3357 pAET = AET.next; 3358 3359 /* For each active edge */ 3360 while (pAET) 3361 { 3362 pts->x = pAET->bres.minor_axis, pts->y = y; 3363 pts++, iPts++; 3364 3365 /* Send out the buffer */ 3366 if (iPts == NUMPTSTOBUFFER) 3367 { 3368 tmpPtBlock = ExAllocatePoolWithTag(PagedPool, 3369 sizeof(POINTBLOCK), 3370 TAG_REGION); 3371 if (tmpPtBlock == NULL) 3372 { 3373 DPRINT1("Can't alloc tmpPtBlock\n"); 3374 goto Cleanup; 3375 } 3376 3377 curPtBlock->next = tmpPtBlock; 3378 curPtBlock = tmpPtBlock; 3379 pts = curPtBlock->pts; 3380 numFullPtBlocks++; 3381 iPts = 0; 3382 } 3383 3384 EVALUATEEDGEEVENODD(pAET, pPrevAET, y); 3385 } 3386 3387 REGION_InsertionSort(&AET); 3388 } 3389 } 3390 else 3391 { 3392 /* For each scanline */ 3393 for (y = ET.ymin; y < ET.ymax; y++) 3394 { 3395 /* Add a new edge to the active edge table when we 3396 * get to the next edge. */ 3397 if (pSLL != NULL && y == pSLL->scanline) 3398 { 3399 REGION_loadAET(&AET, pSLL->edgelist); 3400 REGION_computeWAET(&AET); 3401 pSLL = pSLL->next; 3402 } 3403 3404 pPrevAET = &AET; 3405 pAET = AET.next; 3406 pWETE = pAET; 3407 3408 /* For each active edge */ 3409 while (pAET) 3410 { 3411 /* Add to the buffer only those edges that 3412 * are in the Winding active edge table. */ 3413 if (pWETE == pAET) 3414 { 3415 pts->x = pAET->bres.minor_axis; 3416 pts->y = y; 3417 pts++; 3418 iPts++; 3419 3420 /* Send out the buffer */ 3421 if (iPts == NUMPTSTOBUFFER) 3422 { 3423 tmpPtBlock = ExAllocatePoolWithTag(PagedPool, 3424 sizeof(POINTBLOCK), 3425 TAG_REGION); 3426 if (tmpPtBlock == NULL) 3427 { 3428 DPRINT1("Can't alloc tPB\n"); 3429 goto Cleanup; 3430 } 3431 curPtBlock->next = tmpPtBlock; 3432 curPtBlock = tmpPtBlock; 3433 pts = curPtBlock->pts; 3434 numFullPtBlocks++; 3435 iPts = 0; 3436 } 3437 3438 pWETE = pWETE->nextWETE; 3439 } 3440 3441 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); 3442 } 3443 3444 /* Recompute the winding active edge table if 3445 * we just resorted or have exited an edge. */ 3446 if (REGION_InsertionSort(&AET) || fixWAET) 3447 { 3448 REGION_computeWAET(&AET); 3449 fixWAET = FALSE; 3450 } 3451 } 3452 } 3453 3454 REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, prgn); 3455 bResult = TRUE; 3456 3457 Cleanup: 3458 REGION_FreeStorage(SLLBlock.next); 3459 3460 for (curPtBlock = FirstPtBlock.next; numFullPtBlocks-- > 0;) 3461 { 3462 tmpPtBlock = curPtBlock->next; 3463 ExFreePoolWithTag(curPtBlock, TAG_REGION); 3464 curPtBlock = tmpPtBlock; 3465 } 3466 3467 ExFreePoolWithTag(pETEs, TAG_REGION); 3468 return bResult; 3469 } 3470 3471 HRGN 3472 NTAPI 3473 GreCreatePolyPolygonRgn( 3474 _In_ const POINT *ppt, 3475 _In_ const ULONG *pcPoints, 3476 _In_ ULONG cPolygons, 3477 _In_ INT iMode) 3478 { 3479 PREGION prgn; 3480 HRGN hrgn; 3481 3482 /* Allocate a new region */ 3483 prgn = REGION_AllocUserRgnWithHandle(0); 3484 if (prgn == NULL) 3485 { 3486 EngSetLastError(ERROR_NOT_ENOUGH_MEMORY); 3487 return NULL; 3488 } 3489 3490 /* Call the internal function and check for success */ 3491 if (REGION_SetPolyPolygonRgn(prgn, ppt, pcPoints, cPolygons, iMode)) 3492 { 3493 /* Success, get the handle and unlock the region */ 3494 hrgn = prgn->BaseObject.hHmgr; 3495 REGION_UnlockRgn(prgn); 3496 } 3497 else 3498 { 3499 /* Failure, delete the region */ 3500 REGION_Delete(prgn); 3501 hrgn = NULL; 3502 } 3503 3504 return hrgn; 3505 } 3506 3507 BOOL 3508 FASTCALL 3509 IntRectInRegion( 3510 HRGN hRgn, 3511 LPRECTL rc) 3512 { 3513 PREGION Rgn; 3514 BOOL Ret; 3515 3516 Rgn = REGION_LockRgn(hRgn); 3517 if (Rgn == NULL) 3518 { 3519 return ERROR; 3520 } 3521 3522 Ret = REGION_RectInRegion(Rgn, rc); 3523 REGION_UnlockRgn(Rgn); 3524 return Ret; 3525 } 3526 3527 3528 // 3529 // NtGdi Exported Functions 3530 // 3531 INT 3532 APIENTRY 3533 NtGdiCombineRgn( 3534 IN HRGN hrgnDst, 3535 IN HRGN hrgnSrc1, 3536 IN HRGN hrgnSrc2, 3537 IN INT iMode) 3538 { 3539 HRGN ahrgn[3]; 3540 PREGION aprgn[3]; 3541 INT iResult; 3542 3543 /* Validate the combine mode */ 3544 if ((iMode < RGN_AND) || (iMode > RGN_COPY)) 3545 { 3546 return ERROR; 3547 } 3548 3549 /* Validate that we have the required regions */ 3550 if ((hrgnDst == NULL) || 3551 (hrgnSrc1 == NULL) || 3552 ((iMode != RGN_COPY) && (hrgnSrc2 == NULL))) 3553 { 3554 DPRINT1("NtGdiCombineRgn invalid parameters: %p, %p, %p, %d\n", 3555 hrgnDst, hrgnSrc1, hrgnSrc2, iMode); 3556 EngSetLastError(ERROR_INVALID_HANDLE); 3557 return ERROR; 3558 } 3559 3560 /* Lock all regions */ 3561 ahrgn[0] = hrgnDst; 3562 ahrgn[1] = hrgnSrc1; 3563 ahrgn[2] = iMode != RGN_COPY ? hrgnSrc2 : NULL; 3564 if (!GDIOBJ_bLockMultipleObjects(3, (HGDIOBJ*)ahrgn, (PVOID*)aprgn, GDIObjType_RGN_TYPE)) 3565 { 3566 DPRINT1("NtGdiCombineRgn failed to lock regions: %p, %p, %p, %d\n", 3567 hrgnDst, hrgnSrc1, hrgnSrc2, iMode); 3568 return ERROR; 3569 } 3570 3571 /* HACK: Sync usermode attributes */ 3572 REGION_vSyncRegion(aprgn[0]); 3573 if (aprgn[1] != aprgn[0]) 3574 REGION_vSyncRegion(aprgn[1]); 3575 if ((aprgn[2] != NULL) && (aprgn[2] != aprgn[0]) && (aprgn[2] != aprgn[1])) 3576 REGION_vSyncRegion(aprgn[2]); 3577 3578 /* Call the internal function */ 3579 iResult = IntGdiCombineRgn(aprgn[0], aprgn[1], aprgn[2], iMode); 3580 3581 /* Unlock and return */ 3582 REGION_UnlockRgn(aprgn[0]); 3583 REGION_UnlockRgn(aprgn[1]); 3584 if (aprgn[2] != NULL) 3585 REGION_UnlockRgn(aprgn[2]); 3586 3587 return iResult; 3588 } 3589 3590 HRGN 3591 APIENTRY 3592 NtGdiCreateEllipticRgn( 3593 INT Left, 3594 INT Top, 3595 INT Right, 3596 INT Bottom) 3597 { 3598 return NtGdiCreateRoundRectRgn(Left, 3599 Top, 3600 Right, Bottom, 3601 Right - Left, 3602 Bottom - Top); 3603 } 3604 3605 HRGN 3606 APIENTRY 3607 NtGdiCreateRectRgn( 3608 INT LeftRect, 3609 INT TopRect, 3610 INT RightRect, 3611 INT BottomRect) 3612 { 3613 PREGION pRgn; 3614 HRGN hRgn; 3615 3616 /* Allocate region data structure with space for 1 RECTL */ 3617 pRgn = REGION_AllocUserRgnWithHandle(1); 3618 if (pRgn == NULL) 3619 { 3620 EngSetLastError(ERROR_NOT_ENOUGH_MEMORY); 3621 return NULL; 3622 } 3623 3624 hRgn = pRgn->BaseObject.hHmgr; 3625 3626 REGION_SetRectRgn(pRgn, LeftRect, TopRect, RightRect, BottomRect); 3627 REGION_UnlockRgn(pRgn); 3628 3629 DPRINT("Returning %p.\n", hRgn); 3630 3631 return hRgn; 3632 } 3633 3634 HRGN 3635 APIENTRY 3636 NtGdiCreateRoundRectRgn( 3637 INT left, 3638 INT top, 3639 INT right, 3640 INT bottom, 3641 INT ellipse_width, 3642 INT ellipse_height) 3643 { 3644 PREGION obj; 3645 HRGN hrgn; 3646 int a, b, i, x, y; 3647 INT64 asq, bsq, dx, dy, err; 3648 RECT *rects; 3649 3650 /* Make the dimensions sensible */ 3651 if (left > right) 3652 { 3653 INT tmp = left; 3654 left = right; 3655 right = tmp; 3656 } 3657 3658 if (top > bottom) 3659 { 3660 INT tmp = top; 3661 top = bottom; 3662 bottom = tmp; 3663 } 3664 3665 /* the region is for the rectangle interior, but only at right and bottom for some reason */ 3666 right--; 3667 bottom--; 3668 3669 ellipse_width = min( right - left, abs( ellipse_width )); 3670 ellipse_height = min( bottom - top, abs( ellipse_height )); 3671 3672 /* Check if we can do a normal rectangle instead */ 3673 3674 if ((ellipse_width < 2) || (ellipse_height < 2)) 3675 return NtGdiCreateRectRgn(left, top, right, bottom); 3676 3677 obj = REGION_AllocUserRgnWithHandle( ellipse_height ); 3678 if (obj == NULL) 3679 return 0; 3680 3681 hrgn = obj->BaseObject.hHmgr; 3682 3683 obj->rdh.rcBound.left = left; 3684 obj->rdh.rcBound.top = top; 3685 obj->rdh.rcBound.right = right; 3686 obj->rdh.rcBound.bottom = bottom; 3687 rects = obj->Buffer; 3688 3689 /* based on an algorithm by Alois Zingl */ 3690 3691 a = ellipse_width - 1; 3692 b = ellipse_height - 1; 3693 asq = (INT64)8 * a * a; 3694 bsq = (INT64)8 * b * b; 3695 dx = (INT64)4 * b * b * (1 - a); 3696 dy = (INT64)4 * a * a * (1 + (b % 2)); 3697 err = dx + dy + a * a * (b % 2); 3698 3699 x = 0; 3700 y = ellipse_height / 2; 3701 3702 rects[y].left = left; 3703 rects[y].right = right; 3704 3705 while (x <= ellipse_width / 2) 3706 { 3707 INT64 e2 = 2 * err; 3708 if (e2 >= dx) 3709 { 3710 x++; 3711 err += dx += bsq; 3712 } 3713 if (e2 <= dy) 3714 { 3715 y++; 3716 err += dy += asq; 3717 rects[y].left = left + x; 3718 rects[y].right = right - x; 3719 } 3720 } 3721 for (i = 0; i < ellipse_height / 2; i++) 3722 { 3723 rects[i].left = rects[b - i].left; 3724 rects[i].right = rects[b - i].right; 3725 rects[i].top = top + i; 3726 rects[i].bottom = rects[i].top + 1; 3727 } 3728 for (; i < ellipse_height; i++) 3729 { 3730 rects[i].top = bottom - ellipse_height + i; 3731 rects[i].bottom = rects[i].top + 1; 3732 } 3733 rects[ellipse_height / 2].top = top + ellipse_height / 2; /* extend to top of rectangle */ 3734 3735 REGION_UnlockRgn(obj); 3736 return hrgn; 3737 } 3738 3739 BOOL 3740 APIENTRY 3741 NtGdiEqualRgn( 3742 HRGN hSrcRgn1, 3743 HRGN hSrcRgn2) 3744 { 3745 HRGN ahrgn[2]; 3746 PREGION aprgn[2]; 3747 PREGION rgn1, rgn2; 3748 PRECTL tRect1, tRect2; 3749 ULONG i; 3750 BOOL bRet = FALSE; 3751 3752 /* Check if we got 2 regions */ 3753 if ((hSrcRgn1 == NULL) || (hSrcRgn2 == NULL)) 3754 { 3755 return FALSE; 3756 } 3757 3758 /* Check if these are the same regions */ 3759 if (hSrcRgn1 == hSrcRgn2) 3760 { 3761 /* Make sure this region is valid */ 3762 if ((GDI_HANDLE_GET_TYPE(hSrcRgn1) == GDILoObjType_LO_REGION_TYPE) && 3763 GreIsHandleValid(hSrcRgn1)) 3764 { 3765 return TRUE; 3766 } 3767 return FALSE; 3768 } 3769 3770 /* Lock both regions */ 3771 ahrgn[0] = hSrcRgn1; 3772 ahrgn[1] = hSrcRgn2; 3773 if (!GDIOBJ_bLockMultipleObjects(2, (HGDIOBJ*)ahrgn, (PVOID*)aprgn, GDIObjType_RGN_TYPE)) 3774 { 3775 DPRINT1("NtGdiEqualRgn failed to lock regions: %p, %p\n", 3776 hSrcRgn1, hSrcRgn2); 3777 return FALSE; 3778 } 3779 3780 REGION_vSyncRegion(aprgn[0]); 3781 REGION_vSyncRegion(aprgn[1]); 3782 3783 rgn1 = aprgn[0]; 3784 rgn2 = aprgn[1]; 3785 3786 if (rgn1->rdh.nCount != rgn2->rdh.nCount) 3787 goto exit; 3788 3789 if (rgn1->rdh.nCount == 0) 3790 { 3791 bRet = TRUE; 3792 goto exit; 3793 } 3794 3795 if ((rgn1->rdh.rcBound.left != rgn2->rdh.rcBound.left) || 3796 (rgn1->rdh.rcBound.right != rgn2->rdh.rcBound.right) || 3797 (rgn1->rdh.rcBound.top != rgn2->rdh.rcBound.top) || 3798 (rgn1->rdh.rcBound.bottom != rgn2->rdh.rcBound.bottom)) 3799 goto exit; 3800 3801 tRect1 = rgn1->Buffer; 3802 tRect2 = rgn2->Buffer; 3803 3804 if ((tRect1 == NULL) || (tRect2 == NULL)) 3805 goto exit; 3806 3807 for (i=0; i < rgn1->rdh.nCount; i++) 3808 { 3809 if ((tRect1[i].left != tRect2[i].left) || 3810 (tRect1[i].right != tRect2[i].right) || 3811 (tRect1[i].top != tRect2[i].top) || 3812 (tRect1[i].bottom != tRect2[i].bottom)) 3813 goto exit; 3814 } 3815 3816 bRet = TRUE; 3817 3818 exit: 3819 REGION_UnlockRgn(rgn1); 3820 REGION_UnlockRgn(rgn2); 3821 return bRet; 3822 } 3823 3824 HRGN 3825 APIENTRY 3826 NtGdiExtCreateRegion( 3827 OPTIONAL LPXFORM Xform, 3828 DWORD Count, 3829 LPRGNDATA RgnData) 3830 { 3831 HRGN hRgn; 3832 PREGION Region; 3833 DWORD nCount = 0; 3834 DWORD iType = 0; 3835 DWORD dwSize = 0; 3836 UINT i; 3837 RECT* rects; 3838 NTSTATUS Status = STATUS_SUCCESS; 3839 MATRIX matrix; 3840 XFORMOBJ xo; 3841 3842 DPRINT("NtGdiExtCreateRegion\n"); 3843 _SEH2_TRY 3844 { 3845 ProbeForRead(RgnData, Count, 1); 3846 nCount = RgnData->rdh.nCount; 3847 iType = RgnData->rdh.iType; 3848 dwSize = RgnData->rdh.dwSize; 3849 rects = (RECT*)RgnData->Buffer; 3850 } 3851 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 3852 { 3853 Status = _SEH2_GetExceptionCode(); 3854 } 3855 _SEH2_END; 3856 3857 if (!NT_SUCCESS(Status)) 3858 { 3859 SetLastNtError(Status); 3860 return NULL; 3861 } 3862 3863 /* Check parameters, but don't set last error here */ 3864 if ((Count < sizeof(RGNDATAHEADER) + nCount * sizeof(RECT)) || 3865 (iType != RDH_RECTANGLES) || 3866 (dwSize != sizeof(RGNDATAHEADER))) 3867 { 3868 return NULL; 3869 } 3870 3871 Region = REGION_AllocUserRgnWithHandle(nCount); 3872 3873 if (Region == NULL) 3874 { 3875 EngSetLastError(ERROR_NOT_ENOUGH_MEMORY); 3876 return FALSE; 3877 } 3878 hRgn = Region->BaseObject.hHmgr; 3879 3880 _SEH2_TRY 3881 { 3882 /* Insert the rectangles one by one */ 3883 for(i=0; i<nCount; i++) 3884 { 3885 if ( rects[i].left < rects[i].right && rects[i].top < rects[i].bottom ) 3886 { 3887 if (!REGION_UnionRectWithRgn(Region, &rects[i])) 3888 { 3889 REGION_UnlockRgn(Region); 3890 GreDeleteObject(hRgn); 3891 hRgn = NULL; 3892 _SEH2_LEAVE; 3893 } 3894 } 3895 } 3896 3897 if (Xform != NULL) 3898 { 3899 ULONG ret; 3900 3901 /* Init the XFORMOBJ from the Xform struct */ 3902 Status = STATUS_INVALID_PARAMETER; 3903 XFORMOBJ_vInit(&xo, &matrix); 3904 ret = XFORMOBJ_iSetXform(&xo, (XFORML*)Xform); 3905 3906 /* Check for error */ 3907 if (ret != DDI_ERROR) 3908 { 3909 /* Apply the coordinate transformation on the rects */ 3910 if (XFORMOBJ_bApplyXform(&xo, 3911 XF_LTOL, 3912 Region->rdh.nCount * 2, 3913 Region->Buffer, 3914 Region->Buffer)) 3915 { 3916 Status = STATUS_SUCCESS; 3917 } 3918 } 3919 } 3920 } 3921 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 3922 { 3923 Status = _SEH2_GetExceptionCode(); 3924 } 3925 _SEH2_END; 3926 if (!NT_SUCCESS(Status)) 3927 { 3928 EngSetLastError(ERROR_INVALID_PARAMETER); 3929 REGION_UnlockRgn(Region); 3930 GreDeleteObject(hRgn); 3931 return NULL; 3932 } 3933 3934 if (hRgn) REGION_UnlockRgn(Region); 3935 3936 return hRgn; 3937 } 3938 3939 INT 3940 APIENTRY 3941 NtGdiGetRgnBox( 3942 HRGN hRgn, 3943 PRECTL pRect) 3944 { 3945 PREGION Rgn; 3946 RECTL SafeRect; 3947 DWORD ret; 3948 NTSTATUS Status = STATUS_SUCCESS; 3949 3950 Rgn = REGION_LockRgn(hRgn); 3951 if (Rgn == NULL) 3952 { 3953 return ERROR; 3954 } 3955 3956 ret = REGION_GetRgnBox(Rgn, &SafeRect); 3957 REGION_UnlockRgn(Rgn); 3958 if (ret == ERROR) 3959 { 3960 return ret; 3961 } 3962 3963 _SEH2_TRY 3964 { 3965 ProbeForWrite(pRect, sizeof(RECT), 1); 3966 *pRect = SafeRect; 3967 } 3968 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 3969 { 3970 Status = _SEH2_GetExceptionCode(); 3971 } 3972 _SEH2_END; 3973 if (!NT_SUCCESS(Status)) 3974 { 3975 return ERROR; 3976 } 3977 3978 return ret; 3979 } 3980 3981 INT 3982 APIENTRY 3983 NtGdiOffsetRgn( 3984 _In_ HRGN hrgn, 3985 _In_ INT cx, 3986 _In_ INT cy) 3987 { 3988 PREGION prgn; 3989 INT iResult; 3990 3991 DPRINT("NtGdiOffsetRgn: hrgn %p cx %d cy %d\n", hrgn, cx, cy); 3992 3993 /* Lock the region */ 3994 prgn = REGION_LockRgn(hrgn); 3995 if (prgn == NULL) 3996 { 3997 DPRINT1("NtGdiOffsetRgn: failed to lock region %p\n", hrgn); 3998 return ERROR; 3999 } 4000 4001 /* Call the internal function */ 4002 if (!REGION_bOffsetRgn(prgn, cx, cy)) 4003 { 4004 iResult = ERROR; 4005 } 4006 else 4007 { 4008 iResult = REGION_Complexity(prgn); 4009 } 4010 4011 /* Unlock and return the result */ 4012 REGION_UnlockRgn(prgn); 4013 return iResult; 4014 } 4015 4016 BOOL 4017 APIENTRY 4018 NtGdiPtInRegion( 4019 _In_ HRGN hrgn, 4020 _In_ INT x, 4021 _In_ INT y) 4022 { 4023 PREGION prgn; 4024 BOOL bResult; 4025 4026 /* Lock the region */ 4027 prgn = REGION_LockRgn(hrgn); 4028 if (prgn == NULL) 4029 { 4030 DPRINT1("NtGdiPtInRegion: hrgn error\n"); 4031 return FALSE; 4032 } 4033 4034 /* Call the internal function */ 4035 bResult = REGION_PtInRegion(prgn, x, y); 4036 4037 /* Unlock and return the result */ 4038 REGION_UnlockRgn(prgn); 4039 return bResult; 4040 } 4041 4042 __kernel_entry 4043 BOOL 4044 APIENTRY 4045 NtGdiRectInRegion( 4046 _In_ HRGN hrgn, 4047 _Inout_ LPRECT prclUnsafe) 4048 { 4049 RECTL rcTemp; 4050 4051 /* Probe and copy the rect */ 4052 _SEH2_TRY 4053 { 4054 ProbeForRead(prclUnsafe, sizeof(RECT), 1); 4055 rcTemp = *prclUnsafe; 4056 } 4057 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 4058 { 4059 DPRINT1("NtGdiRectInRegion: Exception accessing the rect\n"); 4060 return FALSE; 4061 } 4062 _SEH2_END; 4063 4064 /* Call the internal function */ 4065 return IntRectInRegion(hrgn, &rcTemp); 4066 } 4067 4068 BOOL 4069 APIENTRY 4070 NtGdiSetRectRgn( 4071 _In_ HRGN hrgn, 4072 _In_ INT xLeft, 4073 _In_ INT yTop, 4074 _In_ INT xRight, 4075 _In_ INT yBottom) 4076 { 4077 PREGION prgn; 4078 4079 /* Lock the region */ 4080 prgn = REGION_LockRgn(hrgn); 4081 if (prgn == NULL) 4082 { 4083 return FALSE; 4084 } 4085 4086 /* Call the internal API */ 4087 REGION_SetRectRgn(prgn, xLeft, yTop, xRight, yBottom); 4088 4089 /* Unlock the region and return success */ 4090 REGION_UnlockRgn(prgn); 4091 return TRUE; 4092 } 4093 4094 /*! 4095 * MSDN: GetRegionData, Return Values: 4096 * 4097 * "If the function succeeds and dwCount specifies an adequate number of bytes, 4098 * the return value is always dwCount. If dwCount is too small or the function 4099 * fails, the return value is 0. If lpRgnData is NULL, the return value is the 4100 * required number of bytes. 4101 * 4102 * If the function fails, the return value is zero." 4103 */ 4104 _Success_(return!=0) 4105 __kernel_entry 4106 ULONG 4107 APIENTRY 4108 NtGdiGetRegionData( 4109 _In_ HRGN hrgn, 4110 _In_ ULONG cjBuffer, 4111 _Out_writes_bytes_to_opt_(cjBuffer, return) LPRGNDATA lpRgnData) 4112 { 4113 ULONG cjRects, cjSize; 4114 PREGION prgn; 4115 4116 /* Lock the region */ 4117 prgn = REGION_LockRgn(hrgn); 4118 if (prgn == NULL) 4119 { 4120 EngSetLastError(ERROR_INVALID_HANDLE); 4121 return 0; 4122 } 4123 4124 /* Calculate the region sizes */ 4125 cjRects = prgn->rdh.nCount * sizeof(RECT); 4126 cjSize = cjRects + sizeof(RGNDATAHEADER); 4127 4128 /* Check if region data is requested */ 4129 if (lpRgnData) 4130 { 4131 /* Check if the buffer is large enough */ 4132 if (cjBuffer >= cjSize) 4133 { 4134 /* Probe the buffer and copy the data */ 4135 _SEH2_TRY 4136 { 4137 ProbeForWrite(lpRgnData, cjSize, sizeof(ULONG)); 4138 RtlCopyMemory(lpRgnData, &prgn->rdh, sizeof(RGNDATAHEADER)); 4139 RtlCopyMemory(lpRgnData->Buffer, prgn->Buffer, cjRects); 4140 lpRgnData->rdh.iType = RDH_RECTANGLES; 4141 lpRgnData->rdh.nRgnSize = cjRects; 4142 } 4143 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER) 4144 { 4145 EngSetLastError(ERROR_INVALID_PARAMETER); 4146 cjSize = 0; 4147 } 4148 _SEH2_END; 4149 } 4150 else 4151 { 4152 /* Buffer is too small */ 4153 EngSetLastError(ERROR_INVALID_PARAMETER); 4154 cjSize = 0; 4155 } 4156 } 4157 4158 /* Unlock the region and return the size */ 4159 REGION_UnlockRgn(prgn); 4160 return cjSize; 4161 } 4162 4163 /* EOF */ 4164