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