[WIN32K] -NtGdiGetRegionData: prgn->rdh.nRgnSize is the size of kernel mode buffer...
[reactos.git] / reactos / win32ss / gdi / ntgdi / region.c
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 #include <win32k.h>
117 #include <suppress.h>
118
119 #define NDEBUG
120 #include <debug.h>
121
122 PREGION prgnDefault = NULL;
123 HRGN hrgnDefault = NULL;
124
125 // Internal Functions
126
127 #if 1
128 #define COPY_RECTS(dest, src, nRects) \
129 do { \
130 PRECTL xDest = (dest); \
131 PRECTL xSrc = (src); \
132 UINT xRects = (nRects); \
133 while (xRects-- > 0) { \
134 *(xDest++) = *(xSrc++); \
135 } \
136 } while (0)
137 #else
138 #define COPY_RECTS(dest, src, nRects) RtlCopyMemory(dest, src, (nRects) * sizeof(RECTL))
139 #endif
140
141 #define EMPTY_REGION(pReg) { \
142 (pReg)->rdh.nCount = 0; \
143 (pReg)->rdh.rcBound.left = (pReg)->rdh.rcBound.top = 0; \
144 (pReg)->rdh.rcBound.right = (pReg)->rdh.rcBound.bottom = 0; \
145 (pReg)->rdh.iType = RDH_RECTANGLES; \
146 }
147
148 #define REGION_NOT_EMPTY(pReg) pReg->rdh.nCount
149
150 #define INRECT(r, x, y) \
151 ( ( ((r).right > x)) && \
152 ( ((r).left <= x)) && \
153 ( ((r).bottom > y)) && \
154 ( ((r).top <= y)) )
155
156 /* 1 if two RECTs overlap.
157 * 0 if two RECTs do not overlap.
158 */
159 #define EXTENTCHECK(r1, r2) \
160 ((r1)->right > (r2)->left && \
161 (r1)->left < (r2)->right && \
162 (r1)->bottom > (r2)->top && \
163 (r1)->top < (r2)->bottom)
164
165 /*
166 * In scan converting polygons, we want to choose those pixels
167 * which are inside the polygon. Thus, we add .5 to the starting
168 * x coordinate for both left and right edges. Now we choose the
169 * first pixel which is inside the pgon for the left edge and the
170 * first pixel which is outside the pgon for the right edge.
171 * Draw the left pixel, but not the right.
172 *
173 * How to add .5 to the starting x coordinate:
174 * If the edge is moving to the right, then subtract dy from the
175 * error term from the general form of the algorithm.
176 * If the edge is moving to the left, then add dy to the error term.
177 *
178 * The reason for the difference between edges moving to the left
179 * and edges moving to the right is simple: If an edge is moving
180 * to the right, then we want the algorithm to flip immediately.
181 * If it is moving to the left, then we don't want it to flip until
182 * we traverse an entire pixel.
183 */
184 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
185 int dx; /* Local storage */ \
186 \
187 /* \
188 * If the edge is horizontal, then it is ignored \
189 * and assumed not to be processed. Otherwise, do this stuff. \
190 */ \
191 if ((dy) != 0) { \
192 xStart = (x1); \
193 dx = (x2) - xStart; \
194 if (dx < 0) { \
195 m = dx / (dy); \
196 m1 = m - 1; \
197 incr1 = -2 * dx + 2 * (dy) * m1; \
198 incr2 = -2 * dx + 2 * (dy) * m; \
199 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
200 } else { \
201 m = dx / (dy); \
202 m1 = m + 1; \
203 incr1 = 2 * dx - 2 * (dy) * m1; \
204 incr2 = 2 * dx - 2 * (dy) * m; \
205 d = -2 * m * (dy) + 2 * dx; \
206 } \
207 } \
208 }
209
210 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
211 if (m1 > 0) { \
212 if (d > 0) { \
213 minval += m1; \
214 d += incr1; \
215 } \
216 else { \
217 minval += m; \
218 d += incr2; \
219 } \
220 } else {\
221 if (d >= 0) { \
222 minval += m1; \
223 d += incr1; \
224 } \
225 else { \
226 minval += m; \
227 d += incr2; \
228 } \
229 } \
230 }
231
232 /*
233 * This structure contains all of the information needed
234 * to run the bresenham algorithm.
235 * The variables may be hardcoded into the declarations
236 * instead of using this structure to make use of
237 * register declarations.
238 */
239 typedef struct
240 {
241 INT minor_axis; /* Minor axis */
242 INT d; /* Decision variable */
243 INT m, m1; /* Slope and slope+1 */
244 INT incr1, incr2; /* Error increments */
245 } BRESINFO;
246
247
248 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
249 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
250 bres.m, bres.m1, bres.incr1, bres.incr2)
251
252 #define BRESINCRPGONSTRUCT(bres) \
253 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
254
255
256
257 /*
258 * These are the data structures needed to scan
259 * convert regions. Two different scan conversion
260 * methods are available -- the even-odd method, and
261 * the winding number method.
262 * The even-odd rule states that a point is inside
263 * the polygon if a ray drawn from that point in any
264 * direction will pass through an odd number of
265 * path segments.
266 * By the winding number rule, a point is decided
267 * to be inside the polygon if a ray drawn from that
268 * point in any direction passes through a different
269 * number of clockwise and counter-clockwise path
270 * segments.
271 *
272 * These data structures are adapted somewhat from
273 * the algorithm in (Foley/Van Dam) for scan converting
274 * polygons.
275 * The basic algorithm is to start at the top (smallest y)
276 * of the polygon, stepping down to the bottom of
277 * the polygon by incrementing the y coordinate. We
278 * keep a list of edges which the current scanline crosses,
279 * sorted by x. This list is called the Active Edge Table (AET)
280 * As we change the y-coordinate, we update each entry in
281 * in the active edge table to reflect the edges new xcoord.
282 * This list must be sorted at each scanline in case
283 * two edges intersect.
284 * We also keep a data structure known as the Edge Table (ET),
285 * which keeps track of all the edges which the current
286 * scanline has not yet reached. The ET is basically a
287 * list of SCANLINE_LIST structures containing a list of
288 * edges which are entered at a given scanline. There is one
289 * SCANLINE_LIST per scanline at which an edge is entered.
290 * When we enter a new edge, we move it from the ET to the AET.
291 *
292 * From the AET, we can implement the even-odd rule as in
293 * (Foley/Van Dam).
294 * The winding number rule is a little trickier. We also
295 * keep the EDGE_TABLEEntries in the AET linked by the
296 * nextWETE (winding EDGE_TABLE_ENTRY) link. This allows
297 * the edges to be linked just as before for updating
298 * purposes, but only uses the edges linked by the nextWETE
299 * link as edges representing spans of the polygon to
300 * drawn (as with the even-odd rule).
301 */
302
303 /*
304 * For the winding number rule
305 */
306 #define CLOCKWISE 1
307 #define COUNTERCLOCKWISE -1
308
309 typedef struct _EDGE_TABLE_ENTRY
310 {
311 INT ymax; /* ycoord at which we exit this edge. */
312 BRESINFO bres; /* Bresenham info to run the edge */
313 struct _EDGE_TABLE_ENTRY *next; /* Next in the list */
314 struct _EDGE_TABLE_ENTRY *back; /* For insertion sort */
315 struct _EDGE_TABLE_ENTRY *nextWETE; /* For winding num rule */
316 INT ClockWise; /* Flag for winding number rule */
317 } EDGE_TABLE_ENTRY;
318
319
320 typedef struct _SCANLINE_LIST
321 {
322 INT scanline; /* The scanline represented */
323 EDGE_TABLE_ENTRY *edgelist; /* Header node */
324 struct _SCANLINE_LIST *next; /* Next in the list */
325 } SCANLINE_LIST;
326
327
328 typedef struct
329 {
330 INT ymax; /* ymax for the polygon */
331 INT ymin; /* ymin for the polygon */
332 SCANLINE_LIST scanlines; /* Header node */
333 } EDGE_TABLE;
334
335
336 /*
337 * Here is a struct to help with storage allocation
338 * so we can allocate a big chunk at a time, and then take
339 * pieces from this heap when we need to.
340 */
341 #define SLLSPERBLOCK 25
342
343 typedef struct _SCANLINE_LISTBLOCK
344 {
345 SCANLINE_LIST SLLs[SLLSPERBLOCK];
346 struct _SCANLINE_LISTBLOCK *next;
347 } SCANLINE_LISTBLOCK;
348
349
350 /*
351 * A few macros for the inner loops of the fill code where
352 * performance considerations don't allow a procedure call.
353 *
354 * Evaluate the given edge at the given scanline.
355 * If the edge has expired, then we leave it and fix up
356 * the active edge table; otherwise, we increment the
357 * x value to be ready for the next scanline.
358 * The winding number rule is in effect, so we must notify
359 * the caller when the edge has been removed so he
360 * can reorder the Winding Active Edge Table.
361 */
362 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
363 if (pAET->ymax == y) { /* Leaving this edge */ \
364 pPrevAET->next = pAET->next; \
365 pAET = pPrevAET->next; \
366 fixWAET = 1; \
367 if (pAET) \
368 pAET->back = pPrevAET; \
369 } \
370 else { \
371 BRESINCRPGONSTRUCT(pAET->bres); \
372 pPrevAET = pAET; \
373 pAET = pAET->next; \
374 } \
375 }
376
377
378 /*
379 * Evaluate the given edge at the given scanline.
380 * If the edge has expired, then we leave it and fix up
381 * the active edge table; otherwise, we increment the
382 * x value to be ready for the next scanline.
383 * The even-odd rule is in effect.
384 */
385 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
386 if (pAET->ymax == y) { /* Leaving this edge */ \
387 pPrevAET->next = pAET->next; \
388 pAET = pPrevAET->next; \
389 if (pAET) \
390 pAET->back = pPrevAET; \
391 } \
392 else { \
393 BRESINCRPGONSTRUCT(pAET->bres); \
394 pPrevAET = pAET; \
395 pAET = pAET->next; \
396 } \
397 }
398
399 /**************************************************************************
400 *
401 * Poly Regions
402 *
403 *************************************************************************/
404
405 #define LARGE_COORDINATE 0x7fffffff /* FIXME */
406 #define SMALL_COORDINATE 0x80000000
407
408 static
409 BOOL
410 REGION_bGrowBufferSize(
411 _Inout_ PREGION prgn,
412 _In_ UINT cRects)
413 {
414 ULONG cjNewSize;
415 PVOID pvBuffer;
416 NT_ASSERT(cRects > 0);
417
418 /* Make sure we don't overflow */
419 if (cRects > MAXULONG / sizeof(RECTL))
420 {
421 return FALSE;
422 }
423
424 /* Calculate new buffer size */
425 cjNewSize = cRects * sizeof(RECTL);
426
427 /* Avoid allocating too often, by duplicating the old buffer size
428 Note: we don't do an overflow check, since the old size will never
429 get that large before running out of memory. */
430 if (2 * prgn->rdh.nRgnSize > cjNewSize)
431 {
432 cjNewSize = 2 * prgn->rdh.nRgnSize;
433 }
434
435 /* Allocate the new buffer */
436 pvBuffer = ExAllocatePoolWithTag(PagedPool, cjNewSize, TAG_REGION);
437 if (pvBuffer == NULL)
438 {
439 return FALSE;
440 }
441
442 /* Copy the rects into the new buffer */
443 COPY_RECTS(pvBuffer, prgn->Buffer, prgn->rdh.nCount);
444
445 /* Free the old buffer */
446 if (prgn->Buffer != &prgn->rdh.rcBound)
447 {
448 ExFreePoolWithTag(prgn->Buffer, TAG_REGION);
449 }
450
451 /* Set the new buffer */
452 prgn->Buffer = pvBuffer;
453 prgn->rdh.nRgnSize = cjNewSize;
454
455 return TRUE;
456 }
457
458 static __inline
459 BOOL
460 REGION_bEnsureBufferSize(
461 _Inout_ PREGION prgn,
462 _In_ UINT cRects)
463 {
464 /* Check if the current region size is too small */
465 if (cRects > prgn->rdh.nRgnSize / sizeof(RECTL))
466 {
467 /* Allocate a new buffer */
468 return REGION_bGrowBufferSize(prgn, cRects);
469 }
470
471 return TRUE;
472 }
473
474 FORCEINLINE
475 VOID
476 REGION_vAddRect(
477 _Inout_ PREGION prgn,
478 _In_ LONG left,
479 _In_ LONG top,
480 _In_ LONG right,
481 _In_ LONG bottom)
482 {
483 PRECTL prcl;
484 NT_ASSERT((prgn->rdh.nCount + 1) * sizeof(RECT) <= prgn->rdh.nRgnSize);
485
486 prcl = &prgn->Buffer[prgn->rdh.nCount];
487 prcl->left = left;
488 prcl->top = top;
489 prcl->right = right;
490 prcl->bottom = bottom;
491 prgn->rdh.nCount++;
492 }
493
494 static __inline
495 BOOL
496 REGION_bAddRect(
497 _Inout_ PREGION prgn,
498 _In_ LONG left,
499 _In_ LONG top,
500 _In_ LONG right,
501 _In_ LONG bottom)
502 {
503 if (!REGION_bEnsureBufferSize(prgn, prgn->rdh.nCount + 1))
504 {
505 return FALSE;
506 }
507
508 REGION_vAddRect(prgn, left, top, right, bottom);
509 return TRUE;
510 }
511
512 typedef VOID (FASTCALL *overlapProcp)(PREGION, PRECT, PRECT, PRECT, PRECT, INT, INT);
513 typedef VOID (FASTCALL *nonOverlapProcp)(PREGION, PRECT, PRECT, INT, INT);
514
515 // Number of points to buffer before sending them off to scanlines() : Must be an even number
516 #define NUMPTSTOBUFFER 200
517
518 #define RGN_DEFAULT_RECTS 2
519
520 // Used to allocate buffers for points and link the buffers together
521 typedef struct _POINTBLOCK
522 {
523 POINT pts[NUMPTSTOBUFFER];
524 struct _POINTBLOCK *next;
525 } POINTBLOCK;
526
527 #ifndef NDEBUG
528 /*
529 * This function is left there for debugging purposes.
530 */
531 VOID
532 FASTCALL
533 IntDumpRegion(HRGN hRgn)
534 {
535 PREGION Data;
536
537 Data = REGION_LockRgn(hRgn);
538 if (Data == NULL)
539 {
540 DbgPrint("IntDumpRegion called with invalid region!\n");
541 return;
542 }
543
544 DbgPrint("IntDumpRegion(%x): %d,%d-%d,%d %d\n",
545 hRgn,
546 Data->rdh.rcBound.left,
547 Data->rdh.rcBound.top,
548 Data->rdh.rcBound.right,
549 Data->rdh.rcBound.bottom,
550 Data->rdh.iType);
551
552 REGION_UnlockRgn(Data);
553 }
554 #endif /* Not NDEBUG */
555
556
557 INT
558 FASTCALL
559 REGION_Complexity(PREGION prgn)
560 {
561 if (prgn == NULL)
562 return NULLREGION;
563
564 DPRINT("Region Complexity -> %lu", prgn->rdh.nCount);
565 switch (prgn->rdh.nCount)
566 {
567 case 0:
568 return NULLREGION;
569 case 1:
570 return SIMPLEREGION;
571 default:
572 return COMPLEXREGION;
573 }
574 }
575
576 static
577 BOOL
578 FASTCALL
579 REGION_CopyRegion(
580 PREGION dst,
581 PREGION src)
582 {
583 /* Only copy if source and dest are not equal */
584 if (dst != src)
585 {
586 /* Check if we need to increase our buffer */
587 if (dst->rdh.nRgnSize < src->rdh.nCount * sizeof(RECT))
588 {
589 PRECTL temp;
590
591 /* Allocate a new buffer */
592 temp = ExAllocatePoolWithTag(PagedPool,
593 src->rdh.nCount * sizeof(RECT),
594 TAG_REGION);
595 if (temp == NULL)
596 return FALSE;
597
598 /* Free the old buffer */
599 if ((dst->Buffer != NULL) && (dst->Buffer != &dst->rdh.rcBound))
600 ExFreePoolWithTag(dst->Buffer, TAG_REGION);
601
602 /* Set the new buffer and the size */
603 dst->Buffer = temp;
604 dst->rdh.nRgnSize = src->rdh.nCount * sizeof(RECT);
605 }
606
607 dst->rdh.nCount = src->rdh.nCount;
608 dst->rdh.rcBound.left = src->rdh.rcBound.left;
609 dst->rdh.rcBound.top = src->rdh.rcBound.top;
610 dst->rdh.rcBound.right = src->rdh.rcBound.right;
611 dst->rdh.rcBound.bottom = src->rdh.rcBound.bottom;
612 dst->rdh.iType = src->rdh.iType;
613 COPY_RECTS(dst->Buffer, src->Buffer, src->rdh.nCount);
614 }
615
616 return TRUE;
617 }
618
619 static
620 VOID
621 FASTCALL
622 REGION_SetExtents(
623 PREGION pReg)
624 {
625 RECTL *pRect, *pRectEnd, *pExtents;
626
627 /* Quick check for NULLREGION */
628 if (pReg->rdh.nCount == 0)
629 {
630 pReg->rdh.rcBound.left = 0;
631 pReg->rdh.rcBound.top = 0;
632 pReg->rdh.rcBound.right = 0;
633 pReg->rdh.rcBound.bottom = 0;
634 pReg->rdh.iType = RDH_RECTANGLES;
635 return;
636 }
637
638 pExtents = &pReg->rdh.rcBound;
639 pRect = pReg->Buffer;
640 pRectEnd = pReg->Buffer + pReg->rdh.nCount - 1;
641
642 /* Since pRect is the first rectangle in the region, it must have the
643 * smallest top and since pRectEnd is the last rectangle in the region,
644 * it must have the largest bottom, because of banding. Initialize left and
645 * right from pRect and pRectEnd, resp., as good things to initialize them
646 * to... */
647 pExtents->left = pRect->left;
648 pExtents->top = pRect->top;
649 pExtents->right = pRectEnd->right;
650 pExtents->bottom = pRectEnd->bottom;
651
652 while (pRect <= pRectEnd)
653 {
654 if (pRect->left < pExtents->left)
655 pExtents->left = pRect->left;
656 if (pRect->right > pExtents->right)
657 pExtents->right = pRect->right;
658 pRect++;
659 }
660
661 pReg->rdh.iType = RDH_RECTANGLES;
662 }
663
664 // FIXME: This function needs review and testing
665 /***********************************************************************
666 * REGION_CropRegion
667 */
668 INT
669 FASTCALL
670 REGION_CropRegion(
671 PREGION rgnDst,
672 PREGION rgnSrc,
673 const RECTL *rect)
674 {
675 PRECTL lpr, rpr;
676 ULONG i, j, clipa, clipb, nRgnSize;
677 INT left = MAXLONG;
678 INT right = MINLONG;
679 INT top = MAXLONG;
680 INT bottom = MINLONG;
681
682 if ((rect->left >= rect->right) ||
683 (rect->top >= rect->bottom) ||
684 (EXTENTCHECK(rect, &rgnSrc->rdh.rcBound) == 0))
685 {
686 goto empty;
687 }
688
689 /* Skip all rects that are completely above our intersect rect */
690 for (clipa = 0; clipa < rgnSrc->rdh.nCount; clipa++)
691 {
692 /* bottom is exclusive, so break when we go above it */
693 if (rgnSrc->Buffer[clipa].bottom > rect->top) break;
694 }
695
696 /* Bail out, if there is nothing left */
697 if (clipa == rgnSrc->rdh.nCount) goto empty;
698
699 /* Find the last rect that is still within the intersect rect (exclusive) */
700 for (clipb = clipa; clipb < rgnSrc->rdh.nCount; clipb++)
701 {
702 /* bottom is exclusive, so stop, when we start at that y pos */
703 if (rgnSrc->Buffer[clipb].top >= rect->bottom) break;
704 }
705
706 /* Bail out, if there is nothing left */
707 if (clipb == clipa) goto empty;
708
709 // clipa - index of the first rect in the first intersecting band
710 // clipb - index of the last rect in the last intersecting band plus 1
711
712 /* Check if the buffer in the dest region is large enough,
713 otherwise allocate a new one */
714 nRgnSize = (clipb - clipa) * sizeof(RECT);
715 if ((rgnDst != rgnSrc) && (rgnDst->rdh.nRgnSize < nRgnSize))
716 {
717 PRECTL temp;
718 temp = ExAllocatePoolWithTag(PagedPool, nRgnSize, TAG_REGION);
719 if (temp == NULL)
720 return ERROR;
721
722 /* Free the old buffer */
723 if (rgnDst->Buffer && (rgnDst->Buffer != &rgnDst->rdh.rcBound))
724 ExFreePoolWithTag(rgnDst->Buffer, TAG_REGION);
725
726 rgnDst->Buffer = temp;
727 rgnDst->rdh.nCount = 0;
728 rgnDst->rdh.nRgnSize = nRgnSize;
729 rgnDst->rdh.iType = RDH_RECTANGLES;
730 }
731
732 /* Loop all rects within the intersect rect from the y perspective */
733 for (i = clipa, j = 0; i < clipb ; i++)
734 {
735 /* i - src index, j - dst index, j is always <= i for obvious reasons */
736
737 lpr = &rgnSrc->Buffer[i];
738
739 /* Make sure the source rect is not retarded */
740 ASSERT(lpr->bottom > lpr->top);
741 ASSERT(lpr->right > lpr->left);
742
743 /* We already checked above, this should hold true */
744 ASSERT(lpr->bottom > rect->top);
745 ASSERT(lpr->top < rect->bottom);
746
747 /* Check if this rect is really inside the intersect rect */
748 if ((lpr->left < rect->right) && (lpr->right > rect->left))
749 {
750 rpr = &rgnDst->Buffer[j];
751
752 /* Crop the rect with the intersect rect */
753 rpr->top = max(lpr->top, rect->top);
754 rpr->bottom = min(lpr->bottom, rect->bottom);
755 rpr->left = max(lpr->left, rect->left);
756 rpr->right = min(lpr->right, rect->right);
757
758 /* Make sure the resulting rect is not retarded */
759 ASSERT(rpr->bottom > rpr->top);
760 ASSERT(rpr->right > rpr->left);
761
762 /* Track new bounds */
763 if (rpr->left < left) left = rpr->left;
764 if (rpr->right > right) right = rpr->right;
765 if (rpr->top < top) top = rpr->top;
766 if (rpr->bottom > bottom) bottom = rpr->bottom;
767
768 /* Next target rect */
769 j++;
770 }
771 }
772
773 if (j == 0) goto empty;
774
775 /* Update the bounds rect */
776 rgnDst->rdh.rcBound.left = left;
777 rgnDst->rdh.rcBound.right = right;
778 rgnDst->rdh.rcBound.top = top;
779 rgnDst->rdh.rcBound.bottom = bottom;
780
781 /* Set new rect count */
782 rgnDst->rdh.nCount = j;
783
784 return REGION_Complexity(rgnDst);
785
786 empty:
787 if (rgnDst->Buffer == NULL)
788 {
789 rgnDst->Buffer = &rgnDst->rdh.rcBound;
790 }
791
792 EMPTY_REGION(rgnDst);
793 return NULLREGION;
794 }
795
796
797 /*!
798 * Attempt to merge the rects in the current band with those in the
799 * previous one. Used only by REGION_RegionOp.
800 *
801 * Results:
802 * The new index for the previous band.
803 *
804 * \note Side Effects:
805 * If coalescing takes place:
806 * - rectangles in the previous band will have their bottom fields
807 * altered.
808 * - pReg->numRects will be decreased.
809 *
810 */
811 static
812 INT
813 FASTCALL
814 REGION_Coalesce(
815 PREGION pReg, /* Region to coalesce */
816 INT prevStart, /* Index of start of previous band */
817 INT curStart) /* Index of start of current band */
818 {
819 RECTL *pPrevRect; /* Current rect in previous band */
820 RECTL *pCurRect; /* Current rect in current band */
821 RECTL *pRegEnd; /* End of region */
822 INT curNumRects; /* Number of rectangles in current band */
823 INT prevNumRects; /* Number of rectangles in previous band */
824 INT bandtop; /* Top coordinate for current band */
825
826 pRegEnd = pReg->Buffer + pReg->rdh.nCount;
827 pPrevRect = pReg->Buffer + prevStart;
828 prevNumRects = curStart - prevStart;
829
830 /* Figure out how many rectangles are in the current band. Have to do
831 * this because multiple bands could have been added in REGION_RegionOp
832 * at the end when one region has been exhausted. */
833 pCurRect = pReg->Buffer + curStart;
834 bandtop = pCurRect->top;
835 for (curNumRects = 0;
836 (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
837 curNumRects++)
838 {
839 pCurRect++;
840 }
841
842 if (pCurRect != pRegEnd)
843 {
844 /* If more than one band was added, we have to find the start
845 * of the last band added so the next coalescing job can start
846 * at the right place... (given when multiple bands are added,
847 * this may be pointless -- see above). */
848 pRegEnd--;
849 while ((pRegEnd-1)->top == pRegEnd->top)
850 {
851 pRegEnd--;
852 }
853
854 curStart = pRegEnd - pReg->Buffer;
855 pRegEnd = pReg->Buffer + pReg->rdh.nCount;
856 }
857
858 if ((curNumRects == prevNumRects) && (curNumRects != 0))
859 {
860 pCurRect -= curNumRects;
861
862 /* The bands may only be coalesced if the bottom of the previous
863 * matches the top scanline of the current. */
864 if (pPrevRect->bottom == pCurRect->top)
865 {
866 /* Make sure the bands have rects in the same places. This
867 * assumes that rects have been added in such a way that they
868 * cover the most area possible. I.e. two rects in a band must
869 * have some horizontal space between them. */
870 do
871 {
872 if ((pPrevRect->left != pCurRect->left) ||
873 (pPrevRect->right != pCurRect->right))
874 {
875 /* The bands don't line up so they can't be coalesced. */
876 return (curStart);
877 }
878
879 pPrevRect++;
880 pCurRect++;
881 prevNumRects -= 1;
882 }
883 while (prevNumRects != 0);
884
885 pReg->rdh.nCount -= curNumRects;
886 pCurRect -= curNumRects;
887 pPrevRect -= curNumRects;
888
889 /* The bands may be merged, so set the bottom of each rect
890 * in the previous band to that of the corresponding rect in
891 * the current band. */
892 do
893 {
894 pPrevRect->bottom = pCurRect->bottom;
895 pPrevRect++;
896 pCurRect++;
897 curNumRects -= 1;
898 }
899 while (curNumRects != 0);
900
901 /* If only one band was added to the region, we have to backup
902 * curStart to the start of the previous band.
903 *
904 * If more than one band was added to the region, copy the
905 * other bands down. The assumption here is that the other bands
906 * came from the same region as the current one and no further
907 * coalescing can be done on them since it's all been done
908 * already... curStart is already in the right place. */
909 if (pCurRect == pRegEnd)
910 {
911 curStart = prevStart;
912 }
913 else
914 {
915 do
916 {
917 *pPrevRect++ = *pCurRect++;
918 }
919 while (pCurRect != pRegEnd);
920 }
921 }
922 }
923
924 return (curStart);
925 }
926
927 /*!
928 * Apply an operation to two regions. Called by REGION_Union,
929 * REGION_Inverse, REGION_Subtract, REGION_Intersect...
930 *
931 * Results:
932 * None.
933 *
934 * Side Effects:
935 * The new region is overwritten.
936 *
937 *\note The idea behind this function is to view the two regions as sets.
938 * Together they cover a rectangle of area that this function divides
939 * into horizontal bands where points are covered only by one region
940 * or by both. For the first case, the nonOverlapFunc is called with
941 * each the band and the band's upper and lower extents. For the
942 * second, the overlapFunc is called to process the entire band. It
943 * is responsible for clipping the rectangles in the band, though
944 * this function provides the boundaries.
945 * At the end of each band, the new region is coalesced, if possible,
946 * to reduce the number of rectangles in the region.
947 *
948 */
949 static
950 VOID
951 FASTCALL
952 REGION_RegionOp(
953 PREGION newReg, /* Place to store result */
954 PREGION reg1, /* First region in operation */
955 PREGION reg2, /* 2nd region in operation */
956 overlapProcp overlapFunc, /* Function to call for over-lapping bands */
957 nonOverlapProcp nonOverlap1Func, /* Function to call for non-overlapping bands in region 1 */
958 nonOverlapProcp nonOverlap2Func) /* Function to call for non-overlapping bands in region 2 */
959 {
960 RECTL *r1; /* Pointer into first region */
961 RECTL *r2; /* Pointer into 2d region */
962 RECTL *r1End; /* End of 1st region */
963 RECTL *r2End; /* End of 2d region */
964 INT ybot; /* Bottom of intersection */
965 INT ytop; /* Top of intersection */
966 RECTL *oldRects; /* Old rects for newReg */
967 ULONG prevBand; /* Index of start of
968 * Previous band in newReg */
969 ULONG curBand; /* Index of start of current band in newReg */
970 RECTL *r1BandEnd; /* End of current band in r1 */
971 RECTL *r2BandEnd; /* End of current band in r2 */
972 ULONG top; /* Top of non-overlapping band */
973 ULONG bot; /* Bottom of non-overlapping band */
974
975 /* Initialization:
976 * set r1, r2, r1End and r2End appropriately, preserve the important
977 * parts of the destination region until the end in case it's one of
978 * the two source regions, then mark the "new" region empty, allocating
979 * another array of rectangles for it to use. */
980 r1 = reg1->Buffer;
981 r2 = reg2->Buffer;
982 r1End = r1 + reg1->rdh.nCount;
983 r2End = r2 + reg2->rdh.nCount;
984
985 /* newReg may be one of the src regions so we can't empty it. We keep a
986 * note of its rects pointer (so that we can free them later), preserve its
987 * extents and simply set numRects to zero. */
988 oldRects = newReg->Buffer;
989 newReg->rdh.nCount = 0;
990
991 /* Allocate a reasonable number of rectangles for the new region. The idea
992 * is to allocate enough so the individual functions don't need to
993 * reallocate and copy the array, which is time consuming, yet we don't
994 * have to worry about using too much memory. I hope to be able to
995 * nuke the Xrealloc() at the end of this function eventually. */
996 newReg->rdh.nRgnSize = max(reg1->rdh.nCount + 1, reg2->rdh.nCount) * 2 * sizeof(RECT);
997
998 newReg->Buffer = ExAllocatePoolWithTag(PagedPool,
999 newReg->rdh.nRgnSize,
1000 TAG_REGION);
1001 if (newReg->Buffer == NULL)
1002 {
1003 newReg->rdh.nRgnSize = 0;
1004 return;
1005 }
1006
1007 /* Initialize ybot and ytop.
1008 * In the upcoming loop, ybot and ytop serve different functions depending
1009 * on whether the band being handled is an overlapping or non-overlapping
1010 * band.
1011 * In the case of a non-overlapping band (only one of the regions
1012 * has points in the band), ybot is the bottom of the most recent
1013 * intersection and thus clips the top of the rectangles in that band.
1014 * ytop is the top of the next intersection between the two regions and
1015 * serves to clip the bottom of the rectangles in the current band.
1016 * For an overlapping band (where the two regions intersect), ytop clips
1017 * the top of the rectangles of both regions and ybot clips the bottoms. */
1018 if (reg1->rdh.rcBound.top < reg2->rdh.rcBound.top)
1019 ybot = reg1->rdh.rcBound.top;
1020 else
1021 ybot = reg2->rdh.rcBound.top;
1022
1023 /* prevBand serves to mark the start of the previous band so rectangles
1024 * can be coalesced into larger rectangles. qv. miCoalesce, above.
1025 * In the beginning, there is no previous band, so prevBand == curBand
1026 * (curBand is set later on, of course, but the first band will always
1027 * start at index 0). prevBand and curBand must be indices because of
1028 * the possible expansion, and resultant moving, of the new region's
1029 * array of rectangles. */
1030 prevBand = 0;
1031 do
1032 {
1033 curBand = newReg->rdh.nCount;
1034
1035 /* This algorithm proceeds one source-band (as opposed to a
1036 * destination band, which is determined by where the two regions
1037 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1038 * rectangle after the last one in the current band for their
1039 * respective regions. */
1040 r1BandEnd = r1;
1041 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1042 {
1043 r1BandEnd++;
1044 }
1045
1046 r2BandEnd = r2;
1047 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1048 {
1049 r2BandEnd++;
1050 }
1051
1052 /* First handle the band that doesn't intersect, if any.
1053 *
1054 * Note that attention is restricted to one band in the
1055 * non-intersecting region at once, so if a region has n
1056 * bands between the current position and the next place it overlaps
1057 * the other, this entire loop will be passed through n times. */
1058 if (r1->top < r2->top)
1059 {
1060 top = max(r1->top,ybot);
1061 bot = min(r1->bottom,r2->top);
1062
1063 if ((top != bot) && (nonOverlap1Func != NULL))
1064 {
1065 (*nonOverlap1Func)(newReg, r1, r1BandEnd, top, bot);
1066 }
1067
1068 ytop = r2->top;
1069 }
1070 else if (r2->top < r1->top)
1071 {
1072 top = max(r2->top,ybot);
1073 bot = min(r2->bottom,r1->top);
1074
1075 if ((top != bot) && (nonOverlap2Func != NULL))
1076 {
1077 (*nonOverlap2Func)(newReg, r2, r2BandEnd, top, bot);
1078 }
1079
1080 ytop = r1->top;
1081 }
1082 else
1083 {
1084 ytop = r1->top;
1085 }
1086
1087 /* If any rectangles got added to the region, try and coalesce them
1088 * with rectangles from the previous band. Note we could just do
1089 * this test in miCoalesce, but some machines incur a not
1090 * inconsiderable cost for function calls, so... */
1091 if (newReg->rdh.nCount != curBand)
1092 {
1093 prevBand = REGION_Coalesce(newReg, prevBand, curBand);
1094 }
1095
1096 /* Now see if we've hit an intersecting band. The two bands only
1097 * intersect if ybot > ytop */
1098 ybot = min(r1->bottom, r2->bottom);
1099 curBand = newReg->rdh.nCount;
1100 if (ybot > ytop)
1101 {
1102 (*overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1103 }
1104
1105 if (newReg->rdh.nCount != curBand)
1106 {
1107 prevBand = REGION_Coalesce(newReg, prevBand, curBand);
1108 }
1109
1110 /* If we've finished with a band (bottom == ybot) we skip forward
1111 * in the region to the next band. */
1112 if (r1->bottom == ybot)
1113 {
1114 r1 = r1BandEnd;
1115 }
1116 if (r2->bottom == ybot)
1117 {
1118 r2 = r2BandEnd;
1119 }
1120 }
1121 while ((r1 != r1End) && (r2 != r2End));
1122
1123 /* Deal with whichever region still has rectangles left. */
1124 curBand = newReg->rdh.nCount;
1125 if (r1 != r1End)
1126 {
1127 if (nonOverlap1Func != NULL)
1128 {
1129 do
1130 {
1131 r1BandEnd = r1;
1132 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1133 {
1134 r1BandEnd++;
1135 }
1136
1137 (*nonOverlap1Func)(newReg,
1138 r1,
1139 r1BandEnd,
1140 max(r1->top,ybot),
1141 r1->bottom);
1142 r1 = r1BandEnd;
1143 }
1144 while (r1 != r1End);
1145 }
1146 }
1147 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1148 {
1149 do
1150 {
1151 r2BandEnd = r2;
1152 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1153 {
1154 r2BandEnd++;
1155 }
1156
1157 (*nonOverlap2Func)(newReg,
1158 r2,
1159 r2BandEnd,
1160 max(r2->top,ybot),
1161 r2->bottom);
1162 r2 = r2BandEnd;
1163 }
1164 while (r2 != r2End);
1165 }
1166
1167 if (newReg->rdh.nCount != curBand)
1168 {
1169 (VOID)REGION_Coalesce(newReg, prevBand, curBand);
1170 }
1171
1172 /* A bit of cleanup. To keep regions from growing without bound,
1173 * we shrink the array of rectangles to match the new number of
1174 * rectangles in the region. This never goes to 0, however...
1175 *
1176 * Only do this stuff if the number of rectangles allocated is more than
1177 * twice the number of rectangles in the region (a simple optimization...). */
1178 if ((newReg->rdh.nRgnSize > (2 * newReg->rdh.nCount * sizeof(RECT))) &&
1179 (newReg->rdh.nCount > 2))
1180 {
1181 if (REGION_NOT_EMPTY(newReg))
1182 {
1183 RECTL *prev_rects = newReg->Buffer;
1184 newReg->Buffer = ExAllocatePoolWithTag(PagedPool,
1185 newReg->rdh.nCount * sizeof(RECT),
1186 TAG_REGION);
1187
1188 if (newReg->Buffer == NULL)
1189 {
1190 newReg->Buffer = prev_rects;
1191 }
1192 else
1193 {
1194 newReg->rdh.nRgnSize = newReg->rdh.nCount*sizeof(RECT);
1195 COPY_RECTS(newReg->Buffer, prev_rects, newReg->rdh.nCount);
1196 if (prev_rects != &newReg->rdh.rcBound)
1197 ExFreePoolWithTag(prev_rects, TAG_REGION);
1198 }
1199 }
1200 else
1201 {
1202 /* No point in doing the extra work involved in an Xrealloc if
1203 * the region is empty */
1204 newReg->rdh.nRgnSize = sizeof(RECT);
1205 if (newReg->Buffer != &newReg->rdh.rcBound)
1206 ExFreePoolWithTag(newReg->Buffer, TAG_REGION);
1207
1208 newReg->Buffer = ExAllocatePoolWithTag(PagedPool,
1209 sizeof(RECT),
1210 TAG_REGION);
1211 ASSERT(newReg->Buffer);
1212 }
1213 }
1214
1215 newReg->rdh.iType = RDH_RECTANGLES;
1216
1217 if (oldRects != &newReg->rdh.rcBound)
1218 ExFreePoolWithTag(oldRects, TAG_REGION);
1219 return;
1220 }
1221
1222 /***********************************************************************
1223 * Region Intersection
1224 ***********************************************************************/
1225
1226
1227 /*!
1228 * Handle an overlapping band for REGION_Intersect.
1229 *
1230 * Results:
1231 * None.
1232 *
1233 * \note Side Effects:
1234 * Rectangles may be added to the region.
1235 *
1236 */
1237 static
1238 VOID
1239 FASTCALL
1240 REGION_IntersectO(
1241 PREGION pReg,
1242 PRECTL r1,
1243 PRECTL r1End,
1244 PRECTL r2,
1245 PRECTL r2End,
1246 INT top,
1247 INT bottom)
1248 {
1249 INT left, right;
1250
1251 while ((r1 != r1End) && (r2 != r2End))
1252 {
1253 left = max(r1->left, r2->left);
1254 right = min(r1->right, r2->right);
1255
1256 /* If there's any overlap between the two rectangles, add that
1257 * overlap to the new region.
1258 * There's no need to check for subsumption because the only way
1259 * such a need could arise is if some region has two rectangles
1260 * right next to each other. Since that should never happen... */
1261 if (left < right)
1262 {
1263 if (!REGION_bAddRect(pReg, left, top, right, bottom))
1264 {
1265 return;
1266 }
1267 }
1268
1269 /* Need to advance the pointers. Shift the one that extends
1270 * to the right the least, since the other still has a chance to
1271 * overlap with that region's next rectangle, if you see what I mean. */
1272 if (r1->right < r2->right)
1273 {
1274 r1++;
1275 }
1276 else if (r2->right < r1->right)
1277 {
1278 r2++;
1279 }
1280 else
1281 {
1282 r1++;
1283 r2++;
1284 }
1285 }
1286
1287 return;
1288 }
1289
1290 /***********************************************************************
1291 * REGION_IntersectRegion
1292 */
1293 static
1294 VOID
1295 FASTCALL
1296 REGION_IntersectRegion(
1297 PREGION newReg,
1298 PREGION reg1,
1299 PREGION reg2)
1300 {
1301 /* Check for trivial reject */
1302 if ((reg1->rdh.nCount == 0) ||
1303 (reg2->rdh.nCount == 0) ||
1304 (EXTENTCHECK(&reg1->rdh.rcBound, &reg2->rdh.rcBound) == 0))
1305 {
1306 newReg->rdh.nCount = 0;
1307 }
1308 else
1309 {
1310 REGION_RegionOp(newReg,
1311 reg1,
1312 reg2,
1313 REGION_IntersectO,
1314 NULL,
1315 NULL);
1316 }
1317
1318 /* Can't alter newReg's extents before we call miRegionOp because
1319 * it might be one of the source regions and miRegionOp depends
1320 * on the extents of those regions being the same. Besides, this
1321 * way there's no checking against rectangles that will be nuked
1322 * due to coalescing, so we have to examine fewer rectangles. */
1323 REGION_SetExtents(newReg);
1324 }
1325
1326 /***********************************************************************
1327 * Region Union
1328 ***********************************************************************/
1329
1330 /*!
1331 * Handle a non-overlapping band for the union operation. Just
1332 * Adds the rectangles into the region. Doesn't have to check for
1333 * subsumption or anything.
1334 *
1335 * Results:
1336 * None.
1337 *
1338 * \note Side Effects:
1339 * pReg->numRects is incremented and the final rectangles overwritten
1340 * with the rectangles we're passed.
1341 *
1342 */
1343 static
1344 VOID
1345 FASTCALL
1346 REGION_UnionNonO(
1347 PREGION pReg,
1348 PRECTL r,
1349 PRECTL rEnd,
1350 INT top,
1351 INT bottom)
1352 {
1353 if (r != rEnd)
1354 {
1355 if (!REGION_bEnsureBufferSize(pReg, pReg->rdh.nCount + (rEnd - r)))
1356 {
1357 return;
1358 }
1359
1360 do
1361 {
1362 REGION_vAddRect(pReg, r->left, top, r->right, bottom);
1363 r++;
1364 }
1365 while (r != rEnd);
1366 }
1367
1368 return;
1369 }
1370
1371 static __inline
1372 BOOL
1373 REGION_bMergeRect(
1374 _Inout_ PREGION prgn,
1375 _In_ LONG left,
1376 _In_ LONG top,
1377 _In_ LONG right,
1378 _In_ LONG bottom)
1379 {
1380 if ((prgn->rdh.nCount != 0) &&
1381 (prgn->Buffer[prgn->rdh.nCount - 1].top == top) &&
1382 (prgn->Buffer[prgn->rdh.nCount - 1].bottom == bottom) &&
1383 (prgn->Buffer[prgn->rdh.nCount - 1].right >= left))
1384 {
1385 if (prgn->Buffer[prgn->rdh.nCount - 1].right < right)
1386 {
1387 prgn->Buffer[prgn->rdh.nCount - 1].right = right;
1388 }
1389 }
1390 else
1391 {
1392 if (!REGION_bAddRect(prgn, left, top, right, bottom))
1393 {
1394 return FALSE;
1395 }
1396 }
1397
1398 return TRUE;
1399 }
1400
1401 /*!
1402 * Handle an overlapping band for the union operation. Picks the
1403 * left-most rectangle each time and merges it into the region.
1404 *
1405 * Results:
1406 * None.
1407 *
1408 * \note Side Effects:
1409 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1410 * be changed.
1411 *
1412 */
1413 static
1414 VOID
1415 FASTCALL
1416 REGION_UnionO (
1417 PREGION pReg,
1418 PRECTL r1,
1419 PRECTL r1End,
1420 PRECTL r2,
1421 PRECTL r2End,
1422 INT top,
1423 INT bottom)
1424 {
1425 while ((r1 != r1End) && (r2 != r2End))
1426 {
1427 if (r1->left < r2->left)
1428 {
1429 REGION_bMergeRect(pReg, r1->left, top, r1->right, bottom);
1430 r1++;
1431 }
1432 else
1433 {
1434 REGION_bMergeRect(pReg, r2->left, top, r2->right, bottom);
1435 r2++;
1436 }
1437 }
1438
1439 if (r1 != r1End)
1440 {
1441 do
1442 {
1443 REGION_bMergeRect(pReg, r1->left, top, r1->right, bottom);
1444 r1++;
1445 }
1446 while (r1 != r1End);
1447 }
1448 else
1449 {
1450 while (r2 != r2End)
1451 {
1452 REGION_bMergeRect(pReg, r2->left, top, r2->right, bottom);
1453 r2++;
1454 }
1455 }
1456
1457 return;
1458 }
1459
1460 /***********************************************************************
1461 * REGION_UnionRegion
1462 */
1463 static
1464 VOID
1465 FASTCALL
1466 REGION_UnionRegion(
1467 PREGION newReg,
1468 PREGION reg1,
1469 PREGION reg2)
1470 {
1471 /* Checks all the simple cases
1472 * Region 1 and 2 are the same or region 1 is empty */
1473 if ((reg1 == reg2) || (reg1->rdh.nCount == 0) ||
1474 (reg1->rdh.rcBound.right <= reg1->rdh.rcBound.left) ||
1475 (reg1->rdh.rcBound.bottom <= reg1->rdh.rcBound.top))
1476 {
1477 if (newReg != reg2)
1478 {
1479 REGION_CopyRegion(newReg, reg2);
1480 }
1481
1482 return;
1483 }
1484
1485 /* If nothing to union (region 2 empty) */
1486 if ((reg2->rdh.nCount == 0) ||
1487 (reg2->rdh.rcBound.right <= reg2->rdh.rcBound.left) ||
1488 (reg2->rdh.rcBound.bottom <= reg2->rdh.rcBound.top))
1489 {
1490 if (newReg != reg1)
1491 {
1492 REGION_CopyRegion(newReg, reg1);
1493 }
1494
1495 return;
1496 }
1497
1498 /* Region 1 completely subsumes region 2 */
1499 if ((reg1->rdh.nCount == 1) &&
1500 (reg1->rdh.rcBound.left <= reg2->rdh.rcBound.left) &&
1501 (reg1->rdh.rcBound.top <= reg2->rdh.rcBound.top) &&
1502 (reg2->rdh.rcBound.right <= reg1->rdh.rcBound.right) &&
1503 (reg2->rdh.rcBound.bottom <= reg1->rdh.rcBound.bottom))
1504 {
1505 if (newReg != reg1)
1506 {
1507 REGION_CopyRegion(newReg, reg1);
1508 }
1509
1510 return;
1511 }
1512
1513 /* Region 2 completely subsumes region 1 */
1514 if ((reg2->rdh.nCount == 1) &&
1515 (reg2->rdh.rcBound.left <= reg1->rdh.rcBound.left) &&
1516 (reg2->rdh.rcBound.top <= reg1->rdh.rcBound.top) &&
1517 (reg1->rdh.rcBound.right <= reg2->rdh.rcBound.right) &&
1518 (reg1->rdh.rcBound.bottom <= reg2->rdh.rcBound.bottom))
1519 {
1520 if (newReg != reg2)
1521 {
1522 REGION_CopyRegion(newReg, reg2);
1523 }
1524
1525 return;
1526 }
1527
1528 REGION_RegionOp(newReg,
1529 reg1,
1530 reg2,
1531 REGION_UnionO,
1532 REGION_UnionNonO,
1533 REGION_UnionNonO);
1534
1535 newReg->rdh.rcBound.left = min(reg1->rdh.rcBound.left, reg2->rdh.rcBound.left);
1536 newReg->rdh.rcBound.top = min(reg1->rdh.rcBound.top, reg2->rdh.rcBound.top);
1537 newReg->rdh.rcBound.right = max(reg1->rdh.rcBound.right, reg2->rdh.rcBound.right);
1538 newReg->rdh.rcBound.bottom = max(reg1->rdh.rcBound.bottom, reg2->rdh.rcBound.bottom);
1539 }
1540
1541 /***********************************************************************
1542 * Region Subtraction
1543 ***********************************************************************/
1544
1545 /*!
1546 * Deal with non-overlapping band for subtraction. Any parts from
1547 * region 2 we discard. Anything from region 1 we add to the region.
1548 *
1549 * Results:
1550 * None.
1551 *
1552 * \note Side Effects:
1553 * pReg may be affected.
1554 *
1555 */
1556 static
1557 VOID
1558 FASTCALL
1559 REGION_SubtractNonO1(
1560 PREGION pReg,
1561 PRECTL r,
1562 PRECTL rEnd,
1563 INT top,
1564 INT bottom)
1565 {
1566 if (r != rEnd)
1567 {
1568 if (!REGION_bEnsureBufferSize(pReg, pReg->rdh.nCount + (rEnd - r)))
1569 {
1570 return;
1571 }
1572
1573 do
1574 {
1575 REGION_vAddRect(pReg, r->left, top, r->right, bottom);
1576 r++;
1577 }
1578 while (r != rEnd);
1579 }
1580
1581 return;
1582 }
1583
1584
1585 /*!
1586 * Overlapping band subtraction. x1 is the left-most point not yet
1587 * checked.
1588 *
1589 * Results:
1590 * None.
1591 *
1592 * \note Side Effects:
1593 * pReg may have rectangles added to it.
1594 *
1595 */
1596 static
1597 VOID
1598 FASTCALL
1599 REGION_SubtractO(
1600 PREGION pReg,
1601 PRECTL r1,
1602 PRECTL r1End,
1603 PRECTL r2,
1604 PRECTL r2End,
1605 INT top,
1606 INT bottom)
1607 {
1608 INT left;
1609
1610 left = r1->left;
1611
1612 while ((r1 != r1End) && (r2 != r2End))
1613 {
1614 if (r2->right <= left)
1615 {
1616 /* Subtrahend missed the boat: go to next subtrahend. */
1617 r2++;
1618 }
1619 else if (r2->left <= left)
1620 {
1621 /* Subtrahend preceeds minuend: nuke left edge of minuend. */
1622 left = r2->right;
1623 if (left >= r1->right)
1624 {
1625 /* Minuend completely covered: advance to next minuend and
1626 * reset left fence to edge of new minuend. */
1627 r1++;
1628 if (r1 != r1End)
1629 left = r1->left;
1630 }
1631 else
1632 {
1633 /* Subtrahend now used up since it doesn't extend beyond
1634 * minuend */
1635 r2++;
1636 }
1637 }
1638 else if (r2->left < r1->right)
1639 {
1640 /* Left part of subtrahend covers part of minuend: add uncovered
1641 * part of minuend to region and skip to next subtrahend. */
1642 if (!REGION_bAddRect(pReg, left, top, r2->left, bottom))
1643 {
1644 return;
1645 }
1646
1647 left = r2->right;
1648 if (left >= r1->right)
1649 {
1650 /* Minuend used up: advance to new... */
1651 r1++;
1652 if (r1 != r1End)
1653 left = r1->left;
1654 }
1655 else
1656 {
1657 /* Subtrahend used up */
1658 r2++;
1659 }
1660 }
1661 else
1662 {
1663 /* Minuend used up: add any remaining piece before advancing. */
1664 if (r1->right > left)
1665 {
1666 if (!REGION_bAddRect(pReg, left, top, r1->right, bottom))
1667 {
1668 return;
1669 }
1670 }
1671
1672 r1++;
1673 if (r1 != r1End)
1674 left = r1->left;
1675 }
1676 }
1677
1678 /* Make sure the buffer is large enough for all remaining operations */
1679 if (r1 != r1End)
1680 {
1681 if (!REGION_bEnsureBufferSize(pReg, pReg->rdh.nCount + (r1End - r1)))
1682 {
1683 return;
1684 }
1685
1686 /* Add remaining minuend rectangles to region. */
1687 do
1688 {
1689 REGION_vAddRect(pReg, left, top, r1->right, bottom);
1690 r1++;
1691 if (r1 != r1End)
1692 {
1693 left = r1->left;
1694 }
1695 }
1696 while (r1 != r1End);
1697 }
1698
1699 return;
1700 }
1701
1702 /*!
1703 * Subtract regS from regM and leave the result in regD.
1704 * S stands for subtrahend, M for minuend and D for difference.
1705 *
1706 * Results:
1707 * TRUE.
1708 *
1709 * \note Side Effects:
1710 * regD is overwritten.
1711 *
1712 */
1713 static
1714 VOID
1715 FASTCALL
1716 REGION_SubtractRegion(
1717 PREGION regD,
1718 PREGION regM,
1719 PREGION regS)
1720 {
1721 /* Check for trivial reject */
1722 if ((regM->rdh.nCount == 0) ||
1723 (regS->rdh.nCount == 0) ||
1724 (EXTENTCHECK(&regM->rdh.rcBound, &regS->rdh.rcBound) == 0))
1725 {
1726 REGION_CopyRegion(regD, regM);
1727 return;
1728 }
1729
1730 REGION_RegionOp(regD,
1731 regM,
1732 regS,
1733 REGION_SubtractO,
1734 REGION_SubtractNonO1,
1735 NULL);
1736
1737 /* Can't alter newReg's extents before we call miRegionOp because
1738 * it might be one of the source regions and miRegionOp depends
1739 * on the extents of those regions being the unaltered. Besides, this
1740 * way there's no checking against rectangles that will be nuked
1741 * due to coalescing, so we have to examine fewer rectangles. */
1742 REGION_SetExtents(regD);
1743 }
1744
1745 /***********************************************************************
1746 * REGION_XorRegion
1747 */
1748 static
1749 VOID
1750 FASTCALL
1751 REGION_XorRegion(
1752 PREGION dr,
1753 PREGION sra,
1754 PREGION srb)
1755 {
1756 HRGN htra, htrb;
1757 PREGION tra, trb;
1758
1759 // FIXME: Don't use a handle
1760 tra = REGION_AllocRgnWithHandle(sra->rdh.nCount + 1);
1761 if (tra == NULL)
1762 {
1763 return;
1764 }
1765 htra = tra->BaseObject.hHmgr;
1766
1767 // FIXME: Don't use a handle
1768 trb = REGION_AllocRgnWithHandle(srb->rdh.nCount + 1);
1769 if (trb == NULL)
1770 {
1771 REGION_UnlockRgn(tra);
1772 GreDeleteObject(htra);
1773 return;
1774 }
1775 htrb = trb->BaseObject.hHmgr;
1776
1777 REGION_SubtractRegion(tra, sra, srb);
1778 REGION_SubtractRegion(trb, srb, sra);
1779 REGION_UnionRegion(dr, tra, trb);
1780 REGION_UnlockRgn(tra);
1781 REGION_UnlockRgn(trb);
1782
1783 GreDeleteObject(htra);
1784 GreDeleteObject(htrb);
1785 return;
1786 }
1787
1788
1789 /*!
1790 * Adds a rectangle to a REGION
1791 */
1792 VOID
1793 FASTCALL
1794 REGION_UnionRectWithRgn(
1795 PREGION rgn,
1796 const RECTL *rect)
1797 {
1798 REGION region;
1799
1800 region.Buffer = &region.rdh.rcBound;
1801 region.rdh.nCount = 1;
1802 region.rdh.nRgnSize = sizeof(RECT);
1803 region.rdh.rcBound = *rect;
1804 REGION_UnionRegion(rgn, rgn, &region);
1805 }
1806
1807 INT
1808 FASTCALL
1809 REGION_SubtractRectFromRgn(
1810 PREGION prgnDest,
1811 PREGION prgnSrc,
1812 const RECTL *prcl)
1813 {
1814 REGION rgnLocal;
1815
1816 rgnLocal.Buffer = &rgnLocal.rdh.rcBound;
1817 rgnLocal.rdh.nCount = 1;
1818 rgnLocal.rdh.nRgnSize = sizeof(RECT);
1819 rgnLocal.rdh.rcBound = *prcl;
1820 REGION_SubtractRegion(prgnDest, prgnSrc, &rgnLocal);
1821 return REGION_Complexity(prgnDest);
1822 }
1823
1824 static
1825 BOOL
1826 REGION_bMakeSimpleFrameRgn(
1827 _Inout_ PREGION prgn,
1828 _In_ PRECTL prclSrc,
1829 _In_ INT cx,
1830 _In_ INT cy)
1831 {
1832 RECTL arcl[4];
1833 UINT i;
1834
1835 NT_ASSERT((cx >= 0) && (cy >= 0));
1836 NT_ASSERT((prclSrc->bottom > prclSrc->top) &&
1837 (prclSrc->right > prclSrc->left));
1838
1839 /* Start with an empty region */
1840 EMPTY_REGION(prgn);
1841
1842 /* Check for the case where the frame covers the whole rect */
1843 if (((prclSrc->bottom - prclSrc->top) <= cy * 2) ||
1844 ((prclSrc->right - prclSrc->left) <= cx * 2))
1845 {
1846 prgn->rdh.rcBound = *prclSrc;
1847 prgn->Buffer[0] = *prclSrc;
1848 prgn->rdh.nCount = 1;
1849 return TRUE;
1850 }
1851
1852 i = 0;
1853
1854 if (cy != 0)
1855 {
1856 /* Top rectangle */
1857 arcl[i].left = prclSrc->left;
1858 arcl[i].top = prclSrc->top;
1859 arcl[i].right = prclSrc->right;
1860 arcl[i].bottom = prclSrc->top + cy;
1861 i++;
1862 }
1863
1864 if (cx != 0)
1865 {
1866 /* Left rectangle */
1867 arcl[i].left = prclSrc->left;
1868 arcl[i].top = prclSrc->top + cy;
1869 arcl[i].right = prclSrc->left + cx;
1870 arcl[i].bottom = prclSrc->bottom - cy;
1871 i++;
1872
1873 /* Right rectangle */
1874 arcl[i].left = prclSrc->right - cx;
1875 arcl[i].top = prclSrc->top + cy;
1876 arcl[i].right = prclSrc->right;
1877 arcl[i].bottom = prclSrc->bottom - cy;
1878 i++;
1879 }
1880
1881 if (cy != 0)
1882 {
1883 /* Bottom rectangle */
1884 arcl[i].left = prclSrc->left;
1885 arcl[i].top = prclSrc->bottom - cy;
1886 arcl[i].right = prclSrc->right;
1887 arcl[i].bottom = prclSrc->bottom;
1888 i++;
1889 }
1890
1891 if (i != 0)
1892 {
1893 /* The frame results in a complex region. rcBounds remains
1894 the same, though. */
1895 prgn->rdh.nCount = i;
1896 NT_ASSERT(prgn->rdh.nCount > 1);
1897 prgn->rdh.nRgnSize = prgn->rdh.nCount * sizeof(RECT);
1898 NT_ASSERT(prgn->Buffer == &prgn->rdh.rcBound);
1899 prgn->Buffer = ExAllocatePoolWithTag(PagedPool,
1900 prgn->rdh.nRgnSize,
1901 TAG_REGION);
1902 if (prgn->Buffer == NULL)
1903 {
1904 prgn->rdh.nRgnSize = 0;
1905 return FALSE;
1906 }
1907
1908 _PRAGMA_WARNING_SUPPRESS(__WARNING_MAYBE_UNINIT_VAR) // arcl is initialized
1909 COPY_RECTS(prgn->Buffer, arcl, prgn->rdh.nCount);
1910 }
1911
1912 return TRUE;
1913 }
1914
1915 static
1916 BOOL
1917 REGION_bMakeFrameRegion(
1918 _Inout_ PREGION prgnDest,
1919 _Inout_ PREGION prgnSrc,
1920 _In_ INT cx,
1921 _In_ INT cy)
1922 {
1923 /* Handle negative cx / cy */
1924 cx = abs(cx);
1925 cy = abs(cy);
1926
1927 /* Check border size (the cast is necessary to catch cx/cy == INT_MIN!) */
1928 if (((UINT)cx > MAX_COORD) || ((UINT)cy > MAX_COORD))
1929 {
1930 return FALSE;
1931 }
1932
1933 /* Fail on empty source region */
1934 if (!REGION_NOT_EMPTY(prgnSrc))
1935 {
1936 return FALSE;
1937 }
1938
1939 /* Handle trivial case */
1940 if ((cx == 0) && (cy == 0))
1941 {
1942 EMPTY_REGION(prgnDest);
1943 return TRUE;
1944 }
1945
1946 /* Handle simple source region */
1947 if (REGION_Complexity(prgnSrc) == SIMPLEREGION)
1948 {
1949 return REGION_bMakeSimpleFrameRgn(prgnDest, &prgnSrc->rdh.rcBound, cx, cy);
1950 }
1951
1952 /* Check if we can move the region to create the frame region */
1953 if ((prgnSrc->rdh.rcBound.left < (MIN_COORD + cx)) ||
1954 (prgnSrc->rdh.rcBound.top < (MIN_COORD + cy)) ||
1955 (prgnSrc->rdh.rcBound.right > (MAX_COORD - cx)) ||
1956 (prgnSrc->rdh.rcBound.bottom > (MAX_COORD - cy)))
1957 {
1958 return FALSE;
1959 }
1960
1961 /* Copy the source region */
1962 if (!REGION_CopyRegion(prgnDest, prgnSrc))
1963 {
1964 return FALSE;
1965 }
1966
1967 /* Move the source region to the bottom-right */
1968 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, cx, cy));
1969
1970 /* Intersect with the source region (this crops the top-left frame) */
1971 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc);
1972
1973 /* Move the source region to the bottom-left */
1974 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, -2 * cx, 0));
1975
1976 /* Intersect with the source region (this crops the top-right frame) */
1977 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc);
1978
1979 /* Move the source region to the top-left */
1980 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, 0, -2 * cy));
1981
1982 /* Intersect with the source region (this crops the bottom-right frame) */
1983 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc);
1984
1985 /* Move the source region to the top-right */
1986 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, 2 * cx, 0));
1987
1988 /* Intersect with the source region (this crops the bottom-left frame) */
1989 REGION_IntersectRegion(prgnDest, prgnDest, prgnSrc);
1990
1991 /* Move the source region back to the original position */
1992 NT_VERIFY(REGION_bOffsetRgn(prgnSrc, -cx, cy));
1993
1994 /* Finally subtract the cropped region from the source */
1995 REGION_SubtractRegion(prgnDest, prgnSrc, prgnDest);
1996
1997 return TRUE;
1998 }
1999
2000 HRGN
2001 FASTCALL
2002 GreCreateFrameRgn(
2003 HRGN hrgn,
2004 INT cx,
2005 INT cy)
2006 {
2007 PREGION prgnFrame, prgnSrc;
2008 HRGN hrgnFrame;
2009
2010 /* Allocate a new region */
2011 prgnFrame = REGION_AllocUserRgnWithHandle(1);
2012 if (prgnFrame == NULL)
2013 {
2014 EngSetLastError(ERROR_NOT_ENOUGH_MEMORY);
2015 return NULL;
2016 }
2017
2018 /* Lock the source region */
2019 prgnSrc = REGION_LockRgn(hrgn);
2020 if (prgnSrc == NULL)
2021 {
2022 REGION_Delete(prgnFrame);
2023 return FALSE;
2024 }
2025
2026 if (REGION_bMakeFrameRegion(prgnFrame, prgnSrc, cx, cy))
2027 {
2028 hrgnFrame = prgnFrame->BaseObject.hHmgr;
2029 REGION_UnlockRgn(prgnFrame);
2030 }
2031 else
2032 {
2033 REGION_Delete(prgnFrame);
2034 hrgnFrame = NULL;
2035 }
2036
2037 REGION_UnlockRgn(prgnSrc);
2038 return hrgnFrame;
2039 }
2040
2041 BOOL
2042 FASTCALL
2043 REGION_bXformRgn(
2044 _Inout_ PREGION prgn,
2045 _In_ PMATRIX pmx)
2046 {
2047 XFORMOBJ xo;
2048 ULONG i, j, cjSize;
2049 PPOINT ppt;
2050 PULONG pcPoints;
2051 RECT rect;
2052 BOOL bResult;
2053
2054 /* Check for zero rectangles and return TRUE for translation only matrices */
2055 if (prgn->rdh.nCount < 1)
2056 return (pmx->flAccel & XFORM_UNITY) != 0;
2057
2058 /* Check if this is a scaling only matrix (off-diagonal elements are 0 */
2059 if (pmx->flAccel & XFORM_SCALE)
2060 {
2061 /* Check if this is a translation only matrix */
2062 if (pmx->flAccel & XFORM_UNITY)
2063 {
2064 /* Just offset the region */
2065 return REGION_bOffsetRgn(prgn, (pmx->fxDx + 8) / 16, (pmx->fxDy + 8) / 16);
2066 }
2067 else
2068 {
2069 /* Initialize the xform object */
2070 XFORMOBJ_vInit(&xo, pmx);
2071
2072 /* Scaling can move the rects out of the coordinate space, so
2073 * we first need to check whether we can apply the transformation
2074 * on the bounds rect without modifying the region */
2075 if (!XFORMOBJ_bApplyXform(&xo, XF_LTOL, 2, &prgn->rdh.rcBound, &rect))
2076 {
2077 return FALSE;
2078 }
2079
2080 /* Apply the xform to the rects in the region */
2081 if (!XFORMOBJ_bApplyXform(&xo,
2082 XF_LTOL,
2083 prgn->rdh.nCount * 2,
2084 prgn->Buffer,
2085 prgn->Buffer))
2086 {
2087 /* This can not happen, since we already checked the bounds! */
2088 NT_ASSERT(FALSE);
2089 }
2090
2091 /* Reset bounds */
2092 RECTL_vSetEmptyRect(&prgn->rdh.rcBound);
2093
2094 /* Loop all rects in the region */
2095 for (i = 0; i < prgn->rdh.nCount; i++)
2096 {
2097 /* Make sure the rect is well-ordered after the xform */
2098 RECTL_vMakeWellOrdered(&prgn->Buffer[i]);
2099
2100 /* Update bounds */
2101 RECTL_bUnionRect(&prgn->rdh.rcBound,
2102 &prgn->rdh.rcBound,
2103 &prgn->Buffer[i]);
2104 }
2105
2106 /* Loop all rects in the region */
2107 for (i = 0; i < prgn->rdh.nCount - 1; i++)
2108 {
2109 for (j = i; i < prgn->rdh.nCount; i++)
2110 {
2111 NT_ASSERT(prgn->Buffer[i].top < prgn->Buffer[i].bottom);
2112 NT_ASSERT(prgn->Buffer[j].top >= prgn->Buffer[i].top);
2113 }
2114 }
2115
2116 return TRUE;
2117 }
2118 }
2119 else
2120 {
2121 /* Allocate a buffer for the polygons */
2122 cjSize = prgn->rdh.nCount * (4 * sizeof(POINT) + sizeof(ULONG));
2123 ppt = ExAllocatePoolWithTag(PagedPool, cjSize, GDITAG_REGION);
2124 if (ppt == NULL)
2125 {
2126 return FALSE;
2127 }
2128
2129 /* Fill the buffer with the rects */
2130 pcPoints = (PULONG)&ppt[4 * prgn->rdh.nCount];
2131 for (i = 0; i < prgn->rdh.nCount; i++)
2132 {
2133 /* Make sure the rect is within the legal range */
2134 pcPoints[i] = 4;
2135 ppt[4 * i + 0].x = prgn->Buffer[i].left;
2136 ppt[4 * i + 0].y = prgn->Buffer[i].top;
2137 ppt[4 * i + 1].x = prgn->Buffer[i].right;
2138 ppt[4 * i + 1].y = prgn->Buffer[i].top;
2139 ppt[4 * i + 2].x = prgn->Buffer[i].right;
2140 ppt[4 * i + 2].y = prgn->Buffer[i].bottom;
2141 ppt[4 * i + 3].x = prgn->Buffer[i].left;
2142 ppt[4 * i + 3].y = prgn->Buffer[i].bottom;
2143 }
2144
2145 /* Initialize the xform object */
2146 XFORMOBJ_vInit(&xo, pmx);
2147
2148 /* Apply the xform to the rects in the buffer */
2149 if (!XFORMOBJ_bApplyXform(&xo,
2150 XF_LTOL,
2151 prgn->rdh.nCount * 2,
2152 ppt,
2153 ppt))
2154 {
2155 /* This means, there were coordinates that would go outside of
2156 the coordinate space after the transformation */
2157 ExFreePoolWithTag(ppt, GDITAG_REGION);
2158 return FALSE;
2159 }
2160
2161 /* Now use the polygons to create a polygon region */
2162 bResult = REGION_SetPolyPolygonRgn(prgn,
2163 ppt,
2164 pcPoints,
2165 prgn->rdh.nCount,
2166 WINDING);
2167
2168 /* Free the polygon buffer */
2169 ExFreePoolWithTag(ppt, GDITAG_REGION);
2170
2171 return bResult;
2172 }
2173
2174 }
2175
2176
2177 PREGION
2178 FASTCALL
2179 REGION_AllocRgnWithHandle(
2180 INT nReg)
2181 {
2182 //HRGN hReg;
2183 PREGION pReg;
2184
2185 pReg = (PREGION)GDIOBJ_AllocateObject(GDIObjType_RGN_TYPE,
2186 sizeof(REGION),
2187 BASEFLAG_LOOKASIDE);
2188 if (pReg == NULL)
2189 {
2190 DPRINT1("Could not allocate a palette.\n");
2191 return NULL;
2192 }
2193
2194 //hReg = pReg->BaseObject.hHmgr;
2195
2196 if ((nReg == 0) || (nReg == 1))
2197 {
2198 /* Testing shows that > 95% of all regions have only 1 rect.
2199 Including that here saves us from having to do another allocation */
2200 pReg->Buffer = &pReg->rdh.rcBound;
2201 }
2202 else
2203 {
2204 pReg->Buffer = ExAllocatePoolWithTag(PagedPool,
2205 nReg * sizeof(RECT),
2206 TAG_REGION);
2207 if (pReg->Buffer == NULL)
2208 {
2209 DPRINT1("Could not allocate region buffer\n");
2210 GDIOBJ_vDeleteObject(&pReg->BaseObject);
2211 return NULL;
2212 }
2213 }
2214
2215 EMPTY_REGION(pReg);
2216 pReg->rdh.dwSize = sizeof(RGNDATAHEADER);
2217 pReg->rdh.nCount = nReg;
2218 pReg->rdh.nRgnSize = nReg * sizeof(RECT);
2219 pReg->prgnattr = &pReg->rgnattr;
2220
2221 /* Initialize the region attribute */
2222 pReg->rgnattr.AttrFlags = 0;
2223 pReg->rgnattr.iComplexity = SIMPLEREGION;
2224 pReg->rgnattr.Rect = pReg->rdh.rcBound;
2225
2226 /* Finally insert the region into the handle table */
2227 if (!GDIOBJ_hInsertObject(&pReg->BaseObject, GDI_OBJ_HMGR_POWNED))
2228 {
2229 DPRINT1("Could not insert palette into handle table.\n");
2230 GDIOBJ_vFreeObject(&pReg->BaseObject);
2231 return NULL;
2232 }
2233
2234 return pReg;
2235 }
2236
2237 BOOL
2238 NTAPI
2239 REGION_bAllocRgnAttr(
2240 PREGION prgn)
2241 {
2242 PPROCESSINFO ppi;
2243 PRGN_ATTR prgnattr;
2244
2245 NT_ASSERT(prgn->prgnattr == &prgn->rgnattr);
2246
2247 ppi = PsGetCurrentProcessWin32Process();
2248 ASSERT(ppi);
2249
2250 prgnattr = GdiPoolAllocate(ppi->pPoolRgnAttr);
2251 if (prgnattr == NULL)
2252 {
2253 DPRINT1("Could not allocate RGN attr\n");
2254 return FALSE;
2255 }
2256
2257 /* Copy the current region attribute */
2258 *prgnattr = prgn->rgnattr;
2259
2260 /* Set the object attribute in the handle table */
2261 prgn->prgnattr = prgnattr;
2262 GDIOBJ_vSetObjectAttr(&prgn->BaseObject, prgnattr);
2263
2264 return TRUE;
2265 }
2266
2267
2268 //
2269 // Allocate User Space Region Handle.
2270 //
2271 PREGION
2272 FASTCALL
2273 REGION_AllocUserRgnWithHandle(
2274 INT nRgn)
2275 {
2276 PREGION prgn;
2277
2278 prgn = REGION_AllocRgnWithHandle(nRgn);
2279 if (prgn == NULL)
2280 {
2281 return NULL;
2282 }
2283
2284 if (!REGION_bAllocRgnAttr(prgn))
2285 {
2286 ASSERT(FALSE);
2287 }
2288
2289 return prgn;
2290 }
2291
2292 static
2293 VOID
2294 REGION_vSyncRegion(
2295 _In_ PREGION prgn)
2296 {
2297 PRGN_ATTR prgnattr;
2298
2299 NT_ASSERT(prgn != NULL);
2300 NT_ASSERT(prgn->prgnattr != NULL);
2301 NT_ASSERT((prgn->prgnattr == &prgn->rgnattr) ||
2302 (prgn->prgnattr->AttrFlags & ATTR_RGN_VALID));
2303
2304 /* Get the region attribute and check if it's dirty (modified) */
2305 prgnattr = prgn->prgnattr;
2306 if (prgnattr->AttrFlags & ATTR_RGN_DIRTY)
2307 {
2308 NT_ASSERT(GreGetObjectOwner(prgn->BaseObject.hHmgr) == GDI_OBJ_HMGR_POWNED);
2309 NT_ASSERT(prgnattr != &prgn->rgnattr);
2310
2311 if (prgnattr->iComplexity == NULLREGION)
2312 {
2313 EMPTY_REGION(prgn);
2314 }
2315 else if (prgnattr->iComplexity == SIMPLEREGION)
2316 {
2317 REGION_SetRectRgn(prgn,
2318 prgnattr->Rect.left,
2319 prgnattr->Rect.top,
2320 prgnattr->Rect.right,
2321 prgnattr->Rect.bottom);
2322 }
2323 else
2324 {
2325 /* Should not happen, region attribute is corrupted! */
2326 DPRINT1("Region attribute is corrupted, ignoring\n");
2327 NT_ASSERT(FALSE);
2328 }
2329 }
2330
2331 /* Reset the flags */
2332 prgnattr->AttrFlags &= ~(ATTR_RGN_DIRTY | ATTR_RGN_VALID);
2333 }
2334
2335 PREGION
2336 FASTCALL
2337 REGION_LockRgn(
2338 _In_ HRGN hrgn)
2339 {
2340 PREGION prgn;
2341
2342 prgn = GDIOBJ_LockObject(hrgn, GDIObjType_RGN_TYPE);
2343 if (prgn == NULL)
2344 return NULL;
2345
2346 REGION_vSyncRegion(prgn);
2347 return prgn;
2348 }
2349
2350 VOID
2351 FASTCALL
2352 REGION_UnlockRgn(
2353 _In_ PREGION prgn)
2354 {
2355 PRGN_ATTR prgnattr;
2356
2357 NT_ASSERT(prgn != NULL);
2358 NT_ASSERT(prgn->prgnattr != NULL);
2359
2360 /* Get the region attribute and check if it's user mode */
2361 prgnattr = prgn->prgnattr;
2362 if (prgnattr != &prgn->rgnattr)
2363 {
2364 NT_ASSERT(GreGetObjectOwner(prgn->BaseObject.hHmgr) == GDI_OBJ_HMGR_POWNED);
2365 prgnattr->iComplexity = REGION_Complexity(prgn);
2366 prgnattr->Rect.left = prgn->rdh.rcBound.left;
2367 prgnattr->Rect.top = prgn->rdh.rcBound.top;
2368 prgnattr->Rect.right = prgn->rdh.rcBound.right;
2369 prgnattr->Rect.bottom = prgn->rdh.rcBound.bottom;
2370 prgnattr->AttrFlags |= ATTR_RGN_VALID;
2371 }
2372
2373 GDIOBJ_vUnlockObject(&prgn->BaseObject);
2374 }
2375
2376 /*
2377 System Regions:
2378 These regions do not use attribute sections and when allocated, use gdiobj
2379 level functions.
2380 */
2381 //
2382 // System Region Functions
2383 //
2384 PREGION
2385 FASTCALL
2386 IntSysCreateRectpRgn(
2387 INT LeftRect,
2388 INT TopRect,
2389 INT RightRect,
2390 INT BottomRect)
2391 {
2392 PREGION prgn;
2393
2394 /* Allocate a region, without a handle */
2395 prgn = (PREGION)GDIOBJ_AllocateObject(GDIObjType_RGN_TYPE, sizeof(REGION), BASEFLAG_LOOKASIDE);
2396 if (prgn == NULL)
2397 {
2398 return NULL;
2399 }
2400
2401 /* Initialize it */
2402 prgn->Buffer = &prgn->rdh.rcBound;
2403 prgn->prgnattr = &prgn->rgnattr;
2404 prgn->prgnattr->AttrFlags = ATTR_RGN_VALID;
2405 REGION_SetRectRgn(prgn, LeftRect, TopRect, RightRect, BottomRect);
2406
2407 return prgn;
2408 }
2409
2410 VOID
2411 NTAPI
2412 REGION_vCleanup(PVOID ObjectBody)
2413 {
2414 PREGION pRgn = (PREGION)ObjectBody;
2415 PPROCESSINFO ppi = PsGetCurrentProcessWin32Process();
2416 ASSERT(ppi);
2417
2418 ASSERT(pRgn->prgnattr);
2419 if (pRgn->prgnattr != &pRgn->rgnattr)
2420 GdiPoolFree(ppi->pPoolRgnAttr, pRgn->prgnattr);
2421
2422 if (pRgn->Buffer && pRgn->Buffer != &pRgn->rdh.rcBound)
2423 ExFreePoolWithTag(pRgn->Buffer, TAG_REGION);
2424 }
2425
2426 VOID
2427 FASTCALL
2428 REGION_Delete(PREGION pRgn)
2429 {
2430 if (pRgn == prgnDefault)
2431 return;
2432
2433 GDIOBJ_vDeleteObject(&pRgn->BaseObject);
2434 }
2435
2436 BOOL
2437 FASTCALL
2438 IntGdiSetRegionOwner(HRGN hRgn, DWORD OwnerMask)
2439 {
2440 PREGION prgn;
2441 PRGN_ATTR prgnattr;
2442 PPROCESSINFO ppi;
2443
2444 prgn = REGION_LockRgn(hRgn);
2445 if (prgn == NULL)
2446 {
2447 return FALSE;
2448 }
2449
2450 prgnattr = prgn->prgnattr;
2451 if (prgnattr != &prgn->rgnattr)
2452 {
2453 GDIOBJ_vSetObjectAttr(&prgn->BaseObject, NULL);
2454 prgn->prgnattr = &prgn->rgnattr;
2455 ppi = PsGetCurrentProcessWin32Process();
2456 GdiPoolFree(ppi->pPoolRgnAttr, prgnattr);
2457 }
2458
2459 REGION_UnlockRgn(prgn);
2460
2461 return GreSetObjectOwner(hRgn, OwnerMask);
2462 }
2463
2464 INT
2465 FASTCALL
2466 IntGdiCombineRgn(
2467 PREGION prgnDest,
2468 PREGION prgnSrc1,
2469 PREGION prgnSrc2,
2470 INT iCombineMode)
2471 {
2472
2473 if (prgnDest == NULL)
2474 {
2475 DPRINT("IntGdiCombineRgn: hDest unavailable\n");
2476 return ERROR;
2477 }
2478
2479 if (prgnSrc1 == NULL)
2480 {
2481 DPRINT("IntGdiCombineRgn: hSrc1 unavailable\n");
2482 return ERROR;
2483 }
2484
2485 if (iCombineMode == RGN_COPY)
2486 {
2487 if (!REGION_CopyRegion(prgnDest, prgnSrc1))
2488 return ERROR;
2489
2490 return REGION_Complexity(prgnDest);
2491 }
2492
2493 if (prgnSrc2 == NULL)
2494 {
2495 DPRINT1("IntGdiCombineRgn requires hSrc2 != NULL for combine mode %d!\n", iCombineMode);
2496 ASSERT(FALSE);
2497 return ERROR;
2498 }
2499
2500 switch (iCombineMode)
2501 {
2502 case RGN_AND:
2503 REGION_IntersectRegion(prgnDest, prgnSrc1, prgnSrc2);
2504 break;
2505 case RGN_OR:
2506 REGION_UnionRegion(prgnDest, prgnSrc1, prgnSrc2);
2507 break;
2508 case RGN_XOR:
2509 REGION_XorRegion(prgnDest, prgnSrc1, prgnSrc2);
2510 break;
2511 case RGN_DIFF:
2512 REGION_SubtractRegion(prgnDest, prgnSrc1, prgnSrc2);
2513 break;
2514 }
2515
2516 return REGION_Complexity(prgnDest);
2517 }
2518
2519 INT
2520 FASTCALL
2521 REGION_GetRgnBox(
2522 PREGION Rgn,
2523 PRECTL pRect)
2524 {
2525 DWORD ret;
2526
2527 if (Rgn != NULL)
2528 {
2529 *pRect = Rgn->rdh.rcBound;
2530 ret = REGION_Complexity(Rgn);
2531
2532 return ret;
2533 }
2534 return 0; // If invalid region return zero
2535 }
2536
2537 INT
2538 APIENTRY
2539 IntGdiGetRgnBox(
2540 HRGN hRgn,
2541 PRECTL pRect)
2542 {
2543 PREGION Rgn;
2544 DWORD ret;
2545
2546 Rgn = REGION_LockRgn(hRgn);
2547 if (Rgn == NULL)
2548 {
2549 return ERROR;
2550 }
2551
2552 ret = REGION_GetRgnBox(Rgn, pRect);
2553 REGION_UnlockRgn(Rgn);
2554
2555 return ret;
2556 }
2557
2558
2559 BOOL
2560 FASTCALL
2561 REGION_PtInRegion(
2562 PREGION prgn,
2563 INT X,
2564 INT Y)
2565 {
2566 ULONG i;
2567 PRECT r;
2568
2569 if (prgn->rdh.nCount > 0 && INRECT(prgn->rdh.rcBound, X, Y))
2570 {
2571 r = prgn->Buffer;
2572 for (i = 0; i < prgn->rdh.nCount; i++)
2573 {
2574 if (INRECT(r[i], X, Y))
2575 return TRUE;
2576 }
2577 }
2578
2579 return FALSE;
2580 }
2581
2582 BOOL
2583 FASTCALL
2584 REGION_RectInRegion(
2585 PREGION Rgn,
2586 const RECTL *rect)
2587 {
2588 PRECTL pCurRect, pRectEnd;
2589 RECT rc;
2590
2591 /* Swap the coordinates to make right >= left and bottom >= top */
2592 /* (region building rectangles are normalized the same way) */
2593 if (rect->top > rect->bottom)
2594 {
2595 rc.top = rect->bottom;
2596 rc.bottom = rect->top;
2597 }
2598 else
2599 {
2600 rc.top = rect->top;
2601 rc.bottom = rect->bottom;
2602 }
2603
2604 if (rect->right < rect->left)
2605 {
2606 rc.right = rect->left;
2607 rc.left = rect->right;
2608 }
2609 else
2610 {
2611 rc.right = rect->right;
2612 rc.left = rect->left;
2613 }
2614
2615 /* This is (just) a useful optimization */
2616 if ((Rgn->rdh.nCount > 0) && EXTENTCHECK(&Rgn->rdh.rcBound, &rc))
2617 {
2618 for (pCurRect = Rgn->Buffer, pRectEnd = pCurRect +
2619 Rgn->rdh.nCount; pCurRect < pRectEnd; pCurRect++)
2620 {
2621 if (pCurRect->bottom <= rc.top)
2622 continue; /* Not far enough down yet */
2623
2624 if (pCurRect->top >= rc.bottom)
2625 break; /* Too far down */
2626
2627 if (pCurRect->right <= rc.left)
2628 continue; /* Not far enough over yet */
2629
2630 if (pCurRect->left >= rc.right)
2631 {
2632 continue;
2633 }
2634
2635 return TRUE;
2636 }
2637 }
2638
2639 return FALSE;
2640 }
2641
2642 VOID
2643 FASTCALL
2644 REGION_SetRectRgn(
2645 PREGION rgn,
2646 INT LeftRect,
2647 INT TopRect,
2648 INT RightRect,
2649 INT BottomRect)
2650 {
2651 PRECTL firstRect;
2652
2653 if (LeftRect > RightRect)
2654 {
2655 INT tmp = LeftRect;
2656 LeftRect = RightRect;
2657 RightRect = tmp;
2658 }
2659
2660 if (TopRect > BottomRect)
2661 {
2662 INT tmp = TopRect;
2663 TopRect = BottomRect;
2664 BottomRect = tmp;
2665 }
2666
2667 if ((LeftRect != RightRect) && (TopRect != BottomRect))
2668 {
2669 firstRect = rgn->Buffer;
2670 ASSERT(firstRect);
2671 firstRect->left = rgn->rdh.rcBound.left = LeftRect;
2672 firstRect->top = rgn->rdh.rcBound.top = TopRect;
2673 firstRect->right = rgn->rdh.rcBound.right = RightRect;
2674 firstRect->bottom = rgn->rdh.rcBound.bottom = BottomRect;
2675 rgn->rdh.nCount = 1;
2676 rgn->rdh.iType = RDH_RECTANGLES;
2677 }
2678 else
2679 {
2680 EMPTY_REGION(rgn);
2681 }
2682 }
2683
2684 BOOL
2685 FASTCALL
2686 REGION_bOffsetRgn(
2687 _Inout_ PREGION prgn,
2688 _In_ INT cx,
2689 _In_ INT cy)
2690 {
2691 PRECTL prcl;
2692 UINT i;
2693
2694 NT_ASSERT(prgn != NULL);
2695
2696 /* Check for trivial case */
2697 if ((cx == 0) && (cy == 0))
2698 {
2699 return TRUE;
2700 }
2701
2702 /* Check for empty regions, we ignore the offset values here */
2703 if (prgn->rdh.nCount == 0)
2704 {
2705 return TRUE;
2706 }
2707
2708 /* Make sure the offset is within the legal range */
2709 if ((cx > MAX_COORD) || (cx < MIN_COORD) ||
2710 (cy > MAX_COORD) || (cy < MIN_COORD))
2711 {
2712 return FALSE;
2713 }
2714
2715 /* Are we moving right? */
2716 if (cx > 0)
2717 {
2718 /* Check if we stay inside the bounds on the right side */
2719 if (prgn->rdh.rcBound.right > (MAX_COORD - cx))
2720 {
2721 return FALSE;
2722 }
2723 }
2724 else
2725 {
2726 /* Check if we stay inside the bounds on the left side */
2727 if (prgn->rdh.rcBound.left < (MIN_COORD - cx))
2728 {
2729 return FALSE;
2730 }
2731 }
2732
2733 /* Are we moving down? */
2734 if (cy > 0)
2735 {
2736 /* Check if we stay inside the bounds on the right side */
2737 if (prgn->rdh.rcBound.bottom > (MAX_COORD - cy))
2738 {
2739 return FALSE;
2740 }
2741 }
2742 else
2743 {
2744 /* Check if we stay inside the bounds on the left side */
2745 if (prgn->rdh.rcBound.top < (MIN_COORD - cy))
2746 {
2747 return FALSE;
2748 }
2749 }
2750
2751 /* Loop to move the rects */
2752 prcl = prgn->Buffer;
2753 for (i = 0; i < prgn->rdh.nCount; i++)
2754 {
2755 prcl[i].left += cx;
2756 prcl[i].right += cx;
2757 prcl[i].top += cy;
2758 prcl[i].bottom += cy;
2759 }
2760
2761 /* Finally update the bounds rect */
2762 if (prgn->Buffer != &prgn->rdh.rcBound)
2763 {
2764 prgn->rdh.rcBound.left += cx;
2765 prgn->rdh.rcBound.right += cx;
2766 prgn->rdh.rcBound.top += cy;
2767 prgn->rdh.rcBound.bottom += cy;
2768 }
2769
2770 return TRUE;
2771 }
2772
2773 /***********************************************************************
2774 * REGION_InsertEdgeInET
2775 *
2776 * Insert the given edge into the edge table.
2777 * First we must find the correct bucket in the
2778 * Edge table, then find the right slot in the
2779 * bucket. Finally, we can insert it.
2780 *
2781 */
2782 static
2783 VOID
2784 FASTCALL
2785 REGION_InsertEdgeInET(
2786 EDGE_TABLE *ET,
2787 EDGE_TABLE_ENTRY *ETE,
2788 INT scanline,
2789 SCANLINE_LISTBLOCK **SLLBlock,
2790 INT *iSLLBlock)
2791 {
2792 EDGE_TABLE_ENTRY *start, *prev;
2793 SCANLINE_LIST *pSLL, *pPrevSLL;
2794 SCANLINE_LISTBLOCK *tmpSLLBlock;
2795
2796 /* Find the right bucket to put the edge into */
2797 pPrevSLL = &ET->scanlines;
2798 pSLL = pPrevSLL->next;
2799 while (pSLL && (pSLL->scanline < scanline))
2800 {
2801 pPrevSLL = pSLL;
2802 pSLL = pSLL->next;
2803 }
2804
2805 /* Reassign pSLL (pointer to SCANLINE_LIST) if necessary */
2806 if ((!pSLL) || (pSLL->scanline > scanline))
2807 {
2808 if (*iSLLBlock > SLLSPERBLOCK-1)
2809 {
2810 tmpSLLBlock = ExAllocatePoolWithTag(PagedPool,
2811 sizeof(SCANLINE_LISTBLOCK),
2812 TAG_REGION);
2813 if (tmpSLLBlock == NULL)
2814 {
2815 DPRINT1("REGION_InsertEdgeInETL(): Can't alloc SLLB\n");
2816 /* FIXME: Free resources? */
2817 return;
2818 }
2819
2820 (*SLLBlock)->next = tmpSLLBlock;
2821 tmpSLLBlock->next = (SCANLINE_LISTBLOCK *)NULL;
2822 *SLLBlock = tmpSLLBlock;
2823 *iSLLBlock = 0;
2824 }
2825
2826 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2827
2828 pSLL->next = pPrevSLL->next;
2829 pSLL->edgelist = (EDGE_TABLE_ENTRY *)NULL;
2830 pPrevSLL->next = pSLL;
2831 }
2832
2833 pSLL->scanline = scanline;
2834
2835 /* Now insert the edge in the right bucket */
2836 prev = (EDGE_TABLE_ENTRY *)NULL;
2837 start = pSLL->edgelist;
2838 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2839 {
2840 prev = start;
2841 start = start->next;
2842 }
2843
2844 ETE->next = start;
2845
2846 if (prev)
2847 prev->next = ETE;
2848 else
2849 pSLL->edgelist = ETE;
2850 }
2851
2852 /***********************************************************************
2853 * REGION_loadAET
2854 *
2855 * This routine moves EDGE_TABLEEntries from the
2856 * EDGE_TABLE into the Active Edge Table,
2857 * leaving them sorted by smaller x coordinate.
2858 *
2859 */
2860 static
2861 VOID
2862 FASTCALL
2863 REGION_loadAET(
2864 EDGE_TABLE_ENTRY *AET,
2865 EDGE_TABLE_ENTRY *ETEs)
2866 {
2867 EDGE_TABLE_ENTRY *pPrevAET;
2868 EDGE_TABLE_ENTRY *tmp;
2869
2870 pPrevAET = AET;
2871 AET = AET->next;
2872 while (ETEs)
2873 {
2874 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2875 {
2876 pPrevAET = AET;
2877 AET = AET->next;
2878 }
2879
2880 tmp = ETEs->next;
2881 ETEs->next = AET;
2882 if (AET)
2883 AET->back = ETEs;
2884
2885 ETEs->back = pPrevAET;
2886 pPrevAET->next = ETEs;
2887 pPrevAET = ETEs;
2888
2889 ETEs = tmp;
2890 }
2891 }
2892
2893 /***********************************************************************
2894 * REGION_computeWAET
2895 *
2896 * This routine links the AET by the
2897 * nextWETE (winding EDGE_TABLE_ENTRY) link for
2898 * use by the winding number rule. The final
2899 * Active Edge Table (AET) might look something
2900 * like:
2901 *
2902 * AET
2903 * ---------- --------- ---------
2904 * |ymax | |ymax | |ymax |
2905 * | ... | |... | |... |
2906 * |next |->|next |->|next |->...
2907 * |nextWETE| |nextWETE| |nextWETE|
2908 * --------- --------- ^--------
2909 * | | |
2910 * V-------------------> V---> ...
2911 *
2912 */
2913 static
2914 VOID
2915 FASTCALL
2916 REGION_computeWAET(
2917 EDGE_TABLE_ENTRY *AET)
2918 {
2919 register EDGE_TABLE_ENTRY *pWETE;
2920 register INT inside = 1;
2921 register INT isInside = 0;
2922
2923 AET->nextWETE = (EDGE_TABLE_ENTRY *)NULL;
2924 pWETE = AET;
2925 AET = AET->next;
2926 while (AET)
2927 {
2928 if (AET->ClockWise)
2929 isInside++;
2930 else
2931 isInside--;
2932
2933 if ((!inside && !isInside) ||
2934 ( inside && isInside))
2935 {
2936 pWETE->nextWETE = AET;
2937 pWETE = AET;
2938 inside = !inside;
2939 }
2940 AET = AET->next;
2941 }
2942
2943 pWETE->nextWETE = (EDGE_TABLE_ENTRY *)NULL;
2944 }
2945
2946 /***********************************************************************
2947 * REGION_InsertionSort
2948 *
2949 * Just a simple insertion sort using
2950 * pointers and back pointers to sort the Active
2951 * Edge Table.
2952 *
2953 */
2954 static
2955 BOOL
2956 FASTCALL
2957 REGION_InsertionSort(
2958 EDGE_TABLE_ENTRY *AET)
2959 {
2960 EDGE_TABLE_ENTRY *pETEchase;
2961 EDGE_TABLE_ENTRY *pETEinsert;
2962 EDGE_TABLE_ENTRY *pETEchaseBackTMP;
2963 BOOL changed = FALSE;
2964
2965 AET = AET->next;
2966 while (AET)
2967 {
2968 pETEinsert = AET;
2969 pETEchase = AET;
2970 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2971 pETEchase = pETEchase->back;
2972
2973 AET = AET->next;
2974 if (pETEchase != pETEinsert)
2975 {
2976 pETEchaseBackTMP = pETEchase->back;
2977 pETEinsert->back->next = AET;
2978 if (AET)
2979 AET->back = pETEinsert->back;
2980
2981 pETEinsert->next = pETEchase;
2982 pETEchase->back->next = pETEinsert;
2983 pETEchase->back = pETEinsert;
2984 pETEinsert->back = pETEchaseBackTMP;
2985 changed = TRUE;
2986 }
2987 }
2988
2989 return changed;
2990 }
2991
2992 /***********************************************************************
2993 * REGION_FreeStorage
2994 *
2995 * Clean up our act.
2996 */
2997 static
2998 VOID
2999 FASTCALL
3000 REGION_FreeStorage(
3001 SCANLINE_LISTBLOCK *pSLLBlock)
3002 {
3003 SCANLINE_LISTBLOCK *tmpSLLBlock;
3004
3005 while (pSLLBlock)
3006 {
3007 tmpSLLBlock = pSLLBlock->next;
3008 ExFreePoolWithTag(pSLLBlock, TAG_REGION);
3009 pSLLBlock = tmpSLLBlock;
3010 }
3011 }
3012
3013
3014 /***********************************************************************
3015 * REGION_PtsToRegion
3016 *
3017 * Create an array of rectangles from a list of points.
3018 */
3019 static
3020 INT
3021 FASTCALL
3022 REGION_PtsToRegion(
3023 INT numFullPtBlocks,
3024 INT iCurPtBlock,
3025 POINTBLOCK *FirstPtBlock,
3026 PREGION reg)
3027 {
3028 RECTL *rects;
3029 POINT *pts;
3030 POINTBLOCK *CurPtBlock;
3031 INT i;
3032 RECTL *extents, *temp;
3033 INT numRects;
3034
3035 extents = &reg->rdh.rcBound;
3036
3037 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
3038
3039 /* Make sure, we have at least one rect */
3040 if (numRects == 0)
3041 {
3042 numRects = 1;
3043 }
3044
3045 temp = ExAllocatePoolWithTag(PagedPool, numRects * sizeof(RECT), TAG_REGION);
3046 if (temp == NULL)
3047 {
3048 return 0;
3049 }
3050
3051 if (reg->Buffer != NULL)
3052 {
3053 COPY_RECTS(temp, reg->Buffer, reg->rdh.nCount);
3054 if (reg->Buffer != &reg->rdh.rcBound)
3055 ExFreePoolWithTag(reg->Buffer, TAG_REGION);
3056 }
3057 reg->Buffer = temp;
3058
3059 reg->rdh.nCount = numRects;
3060 CurPtBlock = FirstPtBlock;
3061 rects = reg->Buffer - 1;
3062 numRects = 0;
3063 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
3064
3065 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--)
3066 {
3067 /* The loop uses 2 points per iteration */
3068 i = NUMPTSTOBUFFER >> 1;
3069 if (numFullPtBlocks == 0)
3070 i = iCurPtBlock >> 1;
3071
3072 for (pts = CurPtBlock->pts; i--; pts += 2)
3073 {
3074 if (pts->x == pts[1].x)
3075 continue;
3076
3077 if ((numRects && pts->x == rects->left) &&
3078 (pts->y == rects->bottom) &&
3079 (pts[1].x == rects->right) &&
3080 ((numRects == 1) || (rects[-1].top != rects->top)) &&
3081 (i && pts[2].y > pts[1].y))
3082 {
3083 rects->bottom = pts[1].y + 1;
3084 continue;
3085 }
3086
3087 numRects++;
3088 rects++;
3089 rects->left = pts->x;
3090 rects->top = pts->y;
3091 rects->right = pts[1].x;
3092 rects->bottom = pts[1].y + 1;
3093
3094 if (rects->left < extents->left)
3095 extents->left = rects->left;
3096 if (rects->right > extents->right)
3097 extents->right = rects->right;
3098 }
3099
3100 CurPtBlock = CurPtBlock->next;
3101 }
3102
3103 if (numRects)
3104 {
3105 extents->top = reg->Buffer->top;
3106 extents->bottom = rects->bottom;
3107 }
3108 else
3109 {
3110 extents->left = 0;
3111 extents->top = 0;
3112 extents->right = 0;
3113 extents->bottom = 0;
3114 }
3115
3116 reg->rdh.nCount = numRects;
3117
3118 return(TRUE);
3119 }
3120
3121 /***********************************************************************
3122 * REGION_CreateETandAET
3123 *
3124 * This routine creates the edge table for
3125 * scan converting polygons.
3126 * The Edge Table (ET) looks like:
3127 *
3128 * EDGE_TABLE
3129 * --------
3130 * | ymax | SCANLINE_LISTs
3131 * |scanline|-->------------>-------------->...
3132 * -------- |scanline| |scanline|
3133 * |edgelist| |edgelist|
3134 * --------- ---------
3135 * | |
3136 * | |
3137 * V V
3138 * list of ETEs list of ETEs
3139 *
3140 * where ETE is an EDGE_TABLE_ENTRY data structure,
3141 * and there is one SCANLINE_LIST per scanline at
3142 * which an edge is initially entered.
3143 *
3144 */
3145 static
3146 VOID
3147 FASTCALL
3148 REGION_CreateETandAET(
3149 const ULONG *Count,
3150 INT nbpolygons,
3151 const POINT *pts,
3152 EDGE_TABLE *ET,
3153 EDGE_TABLE_ENTRY *AET,
3154 EDGE_TABLE_ENTRY *pETEs,
3155 SCANLINE_LISTBLOCK *pSLLBlock)
3156 {
3157 const POINT *top, *bottom;
3158 const POINT *PrevPt, *CurrPt, *EndPt;
3159 INT poly, count;
3160 INT iSLLBlock = 0;
3161 INT dy;
3162
3163 /* Initialize the Active Edge Table */
3164 AET->next = (EDGE_TABLE_ENTRY *)NULL;
3165 AET->back = (EDGE_TABLE_ENTRY *)NULL;
3166 AET->nextWETE = (EDGE_TABLE_ENTRY *)NULL;
3167 AET->bres.minor_axis = SMALL_COORDINATE;
3168
3169 /* Initialize the Edge Table. */
3170 ET->scanlines.next = (SCANLINE_LIST *)NULL;
3171 ET->ymax = SMALL_COORDINATE;
3172 ET->ymin = LARGE_COORDINATE;
3173 pSLLBlock->next = (SCANLINE_LISTBLOCK *)NULL;
3174
3175 EndPt = pts - 1;
3176 for (poly = 0; poly < nbpolygons; poly++)
3177 {
3178 count = Count[poly];
3179 EndPt += count;
3180 if (count < 2)
3181 continue;
3182
3183 PrevPt = EndPt;
3184
3185 /* For each vertex in the array of points.
3186 * In this loop we are dealing with two vertices at
3187 * a time -- these make up one edge of the polygon. */
3188 while (count--)
3189 {
3190 CurrPt = pts++;
3191
3192 /* Find out which point is above and which is below. */
3193 if (PrevPt->y > CurrPt->y)
3194 {
3195 bottom = PrevPt, top = CurrPt;
3196 pETEs->ClockWise = 0;
3197 }
3198 else
3199 {
3200 bottom = CurrPt, top = PrevPt;
3201 pETEs->ClockWise = 1;
3202 }
3203
3204 /* Don't add horizontal edges to the Edge table. */
3205 if (bottom->y != top->y)
3206 {
3207 /* -1 so we don't get last scanline */
3208 pETEs->ymax = bottom->y - 1;
3209
3210 /* Initialize integer edge algorithm */
3211 dy = bottom->y - top->y;
3212 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
3213
3214 REGION_InsertEdgeInET(ET,
3215 pETEs,
3216 top->y,
3217 &pSLLBlock,
3218 &iSLLBlock);
3219
3220 if (PrevPt->y > ET->ymax)
3221 ET->ymax = PrevPt->y;
3222 if (PrevPt->y < ET->ymin)
3223 ET->ymin = PrevPt->y;
3224 pETEs++;
3225 }
3226
3227 PrevPt = CurrPt;
3228 }
3229 }
3230 }
3231
3232 BOOL
3233 FASTCALL
3234 REGION_SetPolyPolygonRgn(
3235 _Inout_ PREGION prgn,
3236 _In_ const POINT *ppt,
3237 _In_ const ULONG *pcPoints,
3238 _In_ ULONG cPolygons,
3239 _In_ INT iMode)
3240 {
3241 EDGE_TABLE_ENTRY *pAET; /* Active Edge Table */
3242 INT y; /* Current scanline */
3243 INT iPts = 0; /* Number of pts in buffer */
3244 EDGE_TABLE_ENTRY *pWETE; /* Winding Edge Table Entry */
3245 SCANLINE_LIST *pSLL; /* Current SCANLINE_LIST */
3246 POINT *pts; /* Output buffer */
3247 EDGE_TABLE_ENTRY *pPrevAET; /* Pointer to previous AET */
3248 EDGE_TABLE ET; /* Header node for ET */
3249 EDGE_TABLE_ENTRY AET; /* Header node for AET */
3250 EDGE_TABLE_ENTRY *pETEs; /* EDGE_TABLEEntries pool */
3251 SCANLINE_LISTBLOCK SLLBlock; /* Header for SCANLINE_LIST */
3252 INT fixWAET = FALSE;
3253 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
3254 POINTBLOCK *tmpPtBlock;
3255 UINT numFullPtBlocks = 0;
3256 UINT poly, total;
3257
3258 /* Check if iMode is valid */
3259 if ((iMode != ALTERNATE) && (iMode != WINDING))
3260 {
3261 DPRINT1("Invalid iMode: %lu\n", iMode);
3262 return FALSE;
3263 }
3264
3265 /* Special case a rectangle */
3266 if (((cPolygons == 1) && ((pcPoints[0] == 4) ||
3267 ((pcPoints[0] == 5) && (ppt[4].x == ppt[0].x) && (ppt[4].y == ppt[0].y)))) &&
3268 (((ppt[0].y == ppt[1].y) &&
3269 (ppt[1].x == ppt[2].x) &&
3270 (ppt[2].y == ppt[3].y) &&
3271 (ppt[3].x == ppt[0].x)) ||
3272 ((ppt[0].x == ppt[1].x) &&
3273 (ppt[1].y == ppt[2].y) &&
3274 (ppt[2].x == ppt[3].x) &&
3275 (ppt[3].y == ppt[0].y))))
3276 {
3277 REGION_SetRectRgn(prgn,
3278 min(ppt[0].x, ppt[2].x),
3279 min(ppt[0].y, ppt[2].y),
3280 max(ppt[0].x, ppt[2].x),
3281 max(ppt[0].y, ppt[2].y));
3282 return TRUE;
3283 }
3284
3285 for (poly = total = 0; poly < cPolygons; poly++)
3286 total += pcPoints[poly];
3287
3288 pETEs = ExAllocatePoolWithTag(PagedPool,
3289 sizeof(EDGE_TABLE_ENTRY) * total,
3290 TAG_REGION);
3291 if (pETEs == NULL)
3292 {
3293 DPRINT1("Failed to allocate %lu edge entries\n", total);
3294 return FALSE;
3295 }
3296
3297 pts = FirstPtBlock.pts;
3298 REGION_CreateETandAET(pcPoints, cPolygons, ppt, &ET, &AET, pETEs, &SLLBlock);
3299 pSLL = ET.scanlines.next;
3300 curPtBlock = &FirstPtBlock;
3301
3302 if (iMode != WINDING)
3303 {
3304 /* For each scanline */
3305 for (y = ET.ymin; y < ET.ymax; y++)
3306 {
3307 /* Add a new edge to the active edge table when we
3308 * get to the next edge. */
3309 if (pSLL != NULL && y == pSLL->scanline)
3310 {
3311 REGION_loadAET(&AET, pSLL->edgelist);
3312 pSLL = pSLL->next;
3313 }
3314 pPrevAET = &AET;
3315 pAET = AET.next;
3316
3317 /* For each active edge */
3318 while (pAET)
3319 {
3320 pts->x = pAET->bres.minor_axis, pts->y = y;
3321 pts++, iPts++;
3322
3323 /* Send out the buffer */
3324 if (iPts == NUMPTSTOBUFFER)
3325 {
3326 tmpPtBlock = ExAllocatePoolWithTag(PagedPool,
3327 sizeof(POINTBLOCK),
3328 TAG_REGION);
3329 if (tmpPtBlock == NULL)
3330 {
3331 DPRINT1("Can't alloc tmpPtBlock\n");
3332 ExFreePoolWithTag(pETEs, TAG_REGION);
3333 return FALSE;
3334 }
3335
3336 curPtBlock->next = tmpPtBlock;
3337 curPtBlock = tmpPtBlock;
3338 pts = curPtBlock->pts;
3339 numFullPtBlocks++;
3340 iPts = 0;
3341 }
3342
3343 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
3344 }
3345
3346 REGION_InsertionSort(&AET);
3347 }
3348 }
3349 else
3350 {
3351 /* For each scanline */
3352 for (y = ET.ymin; y < ET.ymax; y++)
3353 {
3354 /* Add a new edge to the active edge table when we
3355 * get to the next edge. */
3356 if (pSLL != NULL && y == pSLL->scanline)
3357 {
3358 REGION_loadAET(&AET, pSLL->edgelist);
3359 REGION_computeWAET(&AET);
3360 pSLL = pSLL->next;
3361 }
3362
3363 pPrevAET = &AET;
3364 pAET = AET.next;
3365 pWETE = pAET;
3366
3367 /* For each active edge */
3368 while (pAET)
3369 {
3370 /* Add to the buffer only those edges that
3371 * are in the Winding active edge table. */
3372 if (pWETE == pAET)
3373 {
3374 pts->x = pAET->bres.minor_axis;
3375 pts->y = y;
3376 pts++;
3377 iPts++;
3378
3379 /* Send out the buffer */
3380 if (iPts == NUMPTSTOBUFFER)
3381 {
3382 tmpPtBlock = ExAllocatePoolWithTag(PagedPool,
3383 sizeof(POINTBLOCK),
3384 TAG_REGION);
3385 if (tmpPtBlock == NULL)
3386 {
3387