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