[CMAKE]
[reactos.git] / subsystems / win32 / win32k / objects / 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
118 #define NDEBUG
119 #include <debug.h>
120
121 PROSRGNDATA prgnDefault = NULL;
122 HRGN hrgnDefault = NULL;
123
124 // Internal Functions
125
126 #if 1
127 #define COPY_RECTS(dest, src, nRects) \
128 do { \
129 PRECTL xDest = (dest); \
130 PRECTL xSrc = (src); \
131 UINT xRects = (nRects); \
132 while(xRects-- > 0) { \
133 *(xDest++) = *(xSrc++); \
134 } \
135 } while(0)
136 #else
137 #define COPY_RECTS(dest, src, nRects) RtlCopyMemory(dest, src, (nRects) * sizeof(RECTL))
138 #endif
139
140 #define EMPTY_REGION(pReg) { \
141 (pReg)->rdh.nCount = 0; \
142 (pReg)->rdh.rcBound.left = (pReg)->rdh.rcBound.top = 0; \
143 (pReg)->rdh.rcBound.right = (pReg)->rdh.rcBound.bottom = 0; \
144 (pReg)->rdh.iType = RDH_RECTANGLES; \
145 }
146
147 #define REGION_NOT_EMPTY(pReg) pReg->rdh.nCount
148
149 #define INRECT(r, x, y) \
150 ( ( ((r).right > x)) && \
151 ( ((r).left <= x)) && \
152 ( ((r).bottom > y)) && \
153 ( ((r).top <= y)) )
154
155 /* 1 if two RECTs overlap.
156 * 0 if two RECTs do not overlap.
157 */
158 #define EXTENTCHECK(r1, r2) \
159 ((r1)->right > (r2)->left && \
160 (r1)->left < (r2)->right && \
161 (r1)->bottom > (r2)->top && \
162 (r1)->top < (r2)->bottom)
163
164 /*
165 * In scan converting polygons, we want to choose those pixels
166 * which are inside the polygon. Thus, we add .5 to the starting
167 * x coordinate for both left and right edges. Now we choose the
168 * first pixel which is inside the pgon for the left edge and the
169 * first pixel which is outside the pgon for the right edge.
170 * Draw the left pixel, but not the right.
171 *
172 * How to add .5 to the starting x coordinate:
173 * If the edge is moving to the right, then subtract dy from the
174 * error term from the general form of the algorithm.
175 * If the edge is moving to the left, then add dy to the error term.
176 *
177 * The reason for the difference between edges moving to the left
178 * and edges moving to the right is simple: If an edge is moving
179 * to the right, then we want the algorithm to flip immediately.
180 * If it is moving to the left, then we don't want it to flip until
181 * we traverse an entire pixel.
182 */
183 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
184 int dx; /* local storage */ \
185 \
186 /* \
187 * if the edge is horizontal, then it is ignored \
188 * and assumed not to be processed. Otherwise, do this stuff. \
189 */ \
190 if ((dy) != 0) { \
191 xStart = (x1); \
192 dx = (x2) - xStart; \
193 if (dx < 0) { \
194 m = dx / (dy); \
195 m1 = m - 1; \
196 incr1 = -2 * dx + 2 * (dy) * m1; \
197 incr2 = -2 * dx + 2 * (dy) * m; \
198 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
199 } else { \
200 m = dx / (dy); \
201 m1 = m + 1; \
202 incr1 = 2 * dx - 2 * (dy) * m1; \
203 incr2 = 2 * dx - 2 * (dy) * m; \
204 d = -2 * m * (dy) + 2 * dx; \
205 } \
206 } \
207 }
208
209 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
210 if (m1 > 0) { \
211 if (d > 0) { \
212 minval += m1; \
213 d += incr1; \
214 } \
215 else { \
216 minval += m; \
217 d += incr2; \
218 } \
219 } else {\
220 if (d >= 0) { \
221 minval += m1; \
222 d += incr1; \
223 } \
224 else { \
225 minval += m; \
226 d += incr2; \
227 } \
228 } \
229 }
230
231 /*
232 * This structure contains all of the information needed
233 * to run the bresenham algorithm.
234 * The variables may be hardcoded into the declarations
235 * instead of using this structure to make use of
236 * register declarations.
237 */
238 typedef struct
239 {
240 INT minor_axis; /* minor axis */
241 INT d; /* decision variable */
242 INT m, m1; /* slope and slope+1 */
243 INT incr1, incr2; /* error increments */
244 } BRESINFO;
245
246
247 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
248 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
249 bres.m, bres.m1, bres.incr1, bres.incr2)
250
251 #define BRESINCRPGONSTRUCT(bres) \
252 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
253
254
255
256 /*
257 * These are the data structures needed to scan
258 * convert regions. Two different scan conversion
259 * methods are available -- the even-odd method, and
260 * the winding number method.
261 * The even-odd rule states that a point is inside
262 * the polygon if a ray drawn from that point in any
263 * direction will pass through an odd number of
264 * path segments.
265 * By the winding number rule, a point is decided
266 * to be inside the polygon if a ray drawn from that
267 * point in any direction passes through a different
268 * number of clockwise and counter-clockwise path
269 * segments.
270 *
271 * These data structures are adapted somewhat from
272 * the algorithm in (Foley/Van Dam) for scan converting
273 * polygons.
274 * The basic algorithm is to start at the top (smallest y)
275 * of the polygon, stepping down to the bottom of
276 * the polygon by incrementing the y coordinate. We
277 * keep a list of edges which the current scanline crosses,
278 * sorted by x. This list is called the Active Edge Table (AET)
279 * As we change the y-coordinate, we update each entry in
280 * in the active edge table to reflect the edges new xcoord.
281 * This list must be sorted at each scanline in case
282 * two edges intersect.
283 * We also keep a data structure known as the Edge Table (ET),
284 * which keeps track of all the edges which the current
285 * scanline has not yet reached. The ET is basically a
286 * list of ScanLineList structures containing a list of
287 * edges which are entered at a given scanline. There is one
288 * ScanLineList per scanline at which an edge is entered.
289 * When we enter a new edge, we move it from the ET to the AET.
290 *
291 * From the AET, we can implement the even-odd rule as in
292 * (Foley/Van Dam).
293 * The winding number rule is a little trickier. We also
294 * keep the EdgeTableEntries in the AET linked by the
295 * nextWETE (winding EdgeTableEntry) link. This allows
296 * the edges to be linked just as before for updating
297 * purposes, but only uses the edges linked by the nextWETE
298 * link as edges representing spans of the polygon to
299 * drawn (as with the even-odd rule).
300 */
301
302 /*
303 * for the winding number rule
304 */
305 #define CLOCKWISE 1
306 #define COUNTERCLOCKWISE -1
307
308 typedef struct _EdgeTableEntry
309 {
310 INT ymax; /* ycoord at which we exit this edge. */
311 BRESINFO bres; /* Bresenham info to run the edge */
312 struct _EdgeTableEntry *next; /* next in the list */
313 struct _EdgeTableEntry *back; /* for insertion sort */
314 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
315 int ClockWise; /* flag for winding number rule */
316 } EdgeTableEntry;
317
318
319 typedef struct _ScanLineList
320 {
321 INT scanline; /* the scanline represented */
322 EdgeTableEntry *edgelist; /* header node */
323 struct _ScanLineList *next; /* next in the list */
324 } ScanLineList;
325
326
327 typedef struct
328 {
329 INT ymax; /* ymax for the polygon */
330 INT ymin; /* ymin for the polygon */
331 ScanLineList scanlines; /* header node */
332 } EdgeTable;
333
334
335 /*
336 * Here is a struct to help with storage allocation
337 * so we can allocate a big chunk at a time, and then take
338 * pieces from this heap when we need to.
339 */
340 #define SLLSPERBLOCK 25
341
342 typedef struct _ScanLineListBlock
343 {
344 ScanLineList SLLs[SLLSPERBLOCK];
345 struct _ScanLineListBlock *next;
346 } ScanLineListBlock;
347
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( PROSRGNDATA obj )
493 {
494 if (!obj) return NULLREGION;
495 switch(obj->rdh.nCount)
496 {
497 DPRINT("Region Complexity -> %d",obj->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 BOOL FASTCALL
585 REGION_CropAndOffsetRegion(
586 PROSRGNDATA rgnDst,
587 PROSRGNDATA rgnSrc,
588 const RECTL *rect,
589 const POINTL *offset
590 )
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 TRUE;
606 }
607 else
608 {
609 xrect = ExAllocatePoolWithTag(PagedPool, rgnSrc->rdh.nCount * sizeof(RECT), TAG_REGION);
610 if(!xrect)
611 return FALSE;
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 FALSE;
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 TRUE;
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 FALSE;
743 }
744 EMPTY_REGION(rgnDst);
745 return TRUE;
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,reg2->rdh.nCount) * 2 * sizeof(RECT);
965
966 if (! (newReg->Buffer = ExAllocatePoolWithTag(PagedPool, newReg->rdh.nRgnSize, TAG_REGION)))
967 {
968 newReg->rdh.nRgnSize = 0;
969 return;
970 }
971
972 /*
973 * Initialize ybot and ytop.
974 * In the upcoming loop, ybot and ytop serve different functions depending
975 * on whether the band being handled is an overlapping or non-overlapping
976 * band.
977 * In the case of a non-overlapping band (only one of the regions
978 * has points in the band), ybot is the bottom of the most recent
979 * intersection and thus clips the top of the rectangles in that band.
980 * ytop is the top of the next intersection between the two regions and
981 * serves to clip the bottom of the rectangles in the current band.
982 * For an overlapping band (where the two regions intersect), ytop clips
983 * the top of the rectangles of both regions and ybot clips the bottoms.
984 */
985 if (reg1->rdh.rcBound.top < reg2->rdh.rcBound.top)
986 ybot = reg1->rdh.rcBound.top;
987 else
988 ybot = reg2->rdh.rcBound.top;
989
990 /*
991 * prevBand serves to mark the start of the previous band so rectangles
992 * can be coalesced into larger rectangles. qv. miCoalesce, above.
993 * In the beginning, there is no previous band, so prevBand == curBand
994 * (curBand is set later on, of course, but the first band will always
995 * start at index 0). prevBand and curBand must be indices because of
996 * the possible expansion, and resultant moving, of the new region's
997 * array of rectangles.
998 */
999 prevBand = 0;
1000
1001 do
1002 {
1003 curBand = newReg->rdh.nCount;
1004
1005 /*
1006 * This algorithm proceeds one source-band (as opposed to a
1007 * destination band, which is determined by where the two regions
1008 * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1009 * rectangle after the last one in the current band for their
1010 * respective regions.
1011 */
1012 r1BandEnd = r1;
1013 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1014 {
1015 r1BandEnd++;
1016 }
1017
1018 r2BandEnd = r2;
1019 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1020 {
1021 r2BandEnd++;
1022 }
1023
1024 /*
1025 * First handle the band that doesn't intersect, if any.
1026 *
1027 * Note that attention is restricted to one band in the
1028 * non-intersecting region at once, so if a region has n
1029 * bands between the current position and the next place it overlaps
1030 * the other, this entire loop will be passed through n times.
1031 */
1032 if (r1->top < r2->top)
1033 {
1034 top = max(r1->top,ybot);
1035 bot = min(r1->bottom,r2->top);
1036
1037 if ((top != bot) && (nonOverlap1Func != NULL))
1038 {
1039 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1040 }
1041
1042 ytop = r2->top;
1043 }
1044 else if (r2->top < r1->top)
1045 {
1046 top = max(r2->top,ybot);
1047 bot = min(r2->bottom,r1->top);
1048
1049 if ((top != bot) && (nonOverlap2Func != NULL))
1050 {
1051 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1052 }
1053
1054 ytop = r1->top;
1055 }
1056 else
1057 {
1058 ytop = r1->top;
1059 }
1060
1061 /*
1062 * If any rectangles got added to the region, try and coalesce them
1063 * with rectangles from the previous band. Note we could just do
1064 * this test in miCoalesce, but some machines incur a not
1065 * inconsiderable cost for function calls, so...
1066 */
1067 if (newReg->rdh.nCount != curBand)
1068 {
1069 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1070 }
1071
1072 /*
1073 * Now see if we've hit an intersecting band. The two bands only
1074 * intersect if ybot > ytop
1075 */
1076 ybot = min(r1->bottom, r2->bottom);
1077 curBand = newReg->rdh.nCount;
1078 if (ybot > ytop)
1079 {
1080 (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1081 }
1082
1083 if (newReg->rdh.nCount != curBand)
1084 {
1085 prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1086 }
1087
1088 /*
1089 * If we've finished with a band (bottom == ybot) we skip forward
1090 * in the region to the next band.
1091 */
1092 if (r1->bottom == ybot)
1093 {
1094 r1 = r1BandEnd;
1095 }
1096 if (r2->bottom == ybot)
1097 {
1098 r2 = r2BandEnd;
1099 }
1100 }
1101 while ((r1 != r1End) && (r2 != r2End));
1102
1103 /*
1104 * Deal with whichever region still has rectangles left.
1105 */
1106 curBand = newReg->rdh.nCount;
1107 if (r1 != r1End)
1108 {
1109 if (nonOverlap1Func != NULL)
1110 {
1111 do
1112 {
1113 r1BandEnd = r1;
1114 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1115 {
1116 r1BandEnd++;
1117 }
1118 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1119 max(r1->top,ybot), r1->bottom);
1120 r1 = r1BandEnd;
1121 }
1122 while (r1 != r1End);
1123 }
1124 }
1125 else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1126 {
1127 do
1128 {
1129 r2BandEnd = r2;
1130 while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1131 {
1132 r2BandEnd++;
1133 }
1134 (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1135 max(r2->top,ybot), r2->bottom);
1136 r2 = r2BandEnd;
1137 }
1138 while (r2 != r2End);
1139 }
1140
1141 if (newReg->rdh.nCount != curBand)
1142 {
1143 (void) REGION_Coalesce (newReg, prevBand, curBand);
1144 }
1145
1146 /*
1147 * A bit of cleanup. To keep regions from growing without bound,
1148 * we shrink the array of rectangles to match the new number of
1149 * rectangles in the region. This never goes to 0, however...
1150 *
1151 * Only do this stuff if the number of rectangles allocated is more than
1152 * twice the number of rectangles in the region (a simple optimization...).
1153 */
1154 if ((2 * newReg->rdh.nCount*sizeof(RECT) < newReg->rdh.nRgnSize && (newReg->rdh.nCount > 2)))
1155 {
1156 if (REGION_NOT_EMPTY(newReg))
1157 {
1158 RECTL *prev_rects = newReg->Buffer;
1159 newReg->Buffer = ExAllocatePoolWithTag(PagedPool, newReg->rdh.nCount*sizeof(RECT), TAG_REGION);
1160
1161 if (! newReg->Buffer)
1162 newReg->Buffer = prev_rects;
1163 else
1164 {
1165 newReg->rdh.nRgnSize = newReg->rdh.nCount*sizeof(RECT);
1166 COPY_RECTS(newReg->Buffer, prev_rects, newReg->rdh.nCount);
1167 if (prev_rects != &newReg->rdh.rcBound)
1168 ExFreePoolWithTag(prev_rects, TAG_REGION);
1169 }
1170 }
1171 else
1172 {
1173 /*
1174 * No point in doing the extra work involved in an Xrealloc if
1175 * the region is empty
1176 */
1177 newReg->rdh.nRgnSize = sizeof(RECT);
1178 if (newReg->Buffer != &newReg->rdh.rcBound)
1179 ExFreePoolWithTag(newReg->Buffer, TAG_REGION);
1180 newReg->Buffer = ExAllocatePoolWithTag(PagedPool, sizeof(RECT), TAG_REGION);
1181 ASSERT(newReg->Buffer);
1182 }
1183 }
1184 newReg->rdh.iType = RDH_RECTANGLES;
1185
1186 if (oldRects != &newReg->rdh.rcBound)
1187 ExFreePoolWithTag(oldRects, TAG_REGION);
1188 return;
1189 }
1190
1191 /***********************************************************************
1192 * Region Intersection
1193 ***********************************************************************/
1194
1195
1196 /*!
1197 * Handle an overlapping band for REGION_Intersect.
1198 *
1199 * Results:
1200 * None.
1201 *
1202 * \note Side Effects:
1203 * Rectangles may be added to the region.
1204 *
1205 */
1206 static void FASTCALL
1207 REGION_IntersectO(
1208 PROSRGNDATA pReg,
1209 PRECTL r1,
1210 PRECTL r1End,
1211 PRECTL r2,
1212 PRECTL r2End,
1213 INT top,
1214 INT bottom
1215 )
1216 {
1217 INT left, right;
1218 RECTL *pNextRect;
1219
1220 pNextRect = pReg->Buffer + pReg->rdh.nCount;
1221
1222 while ((r1 != r1End) && (r2 != r2End))
1223 {
1224 left = max(r1->left, r2->left);
1225 right = min(r1->right, r2->right);
1226
1227 /*
1228 * If there's any overlap between the two rectangles, add that
1229 * overlap to the new region.
1230 * There's no need to check for subsumption because the only way
1231 * such a need could arise is if some region has two rectangles
1232 * right next to each other. Since that should never happen...
1233 */
1234 if (left < right)
1235 {
1236 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1237 pNextRect->left = left;
1238 pNextRect->top = top;
1239 pNextRect->right = right;
1240 pNextRect->bottom = bottom;
1241 pReg->rdh.nCount += 1;
1242 pNextRect++;
1243 }
1244
1245 /*
1246 * Need to advance the pointers. Shift the one that extends
1247 * to the right the least, since the other still has a chance to
1248 * overlap with that region's next rectangle, if you see what I mean.
1249 */
1250 if (r1->right < r2->right)
1251 {
1252 r1++;
1253 }
1254 else if (r2->right < r1->right)
1255 {
1256 r2++;
1257 }
1258 else
1259 {
1260 r1++;
1261 r2++;
1262 }
1263 }
1264 return;
1265 }
1266
1267 /***********************************************************************
1268 * REGION_IntersectRegion
1269 */
1270 static void FASTCALL
1271 REGION_IntersectRegion(
1272 ROSRGNDATA *newReg,
1273 ROSRGNDATA *reg1,
1274 ROSRGNDATA *reg2
1275 )
1276 {
1277 /* check for trivial reject */
1278 if ( (!(reg1->rdh.nCount)) || (!(reg2->rdh.nCount)) ||
1279 (!EXTENTCHECK(&reg1->rdh.rcBound, &reg2->rdh.rcBound)) )
1280 newReg->rdh.nCount = 0;
1281 else
1282 REGION_RegionOp (newReg, reg1, reg2,
1283 REGION_IntersectO, NULL, NULL);
1284
1285 /*
1286 * Can't alter newReg's extents before we call miRegionOp because
1287 * it might be one of the source regions and miRegionOp depends
1288 * on the extents of those regions being the same. Besides, this
1289 * way there's no checking against rectangles that will be nuked
1290 * due to coalescing, so we have to examine fewer rectangles.
1291 */
1292
1293 REGION_SetExtents(newReg);
1294 }
1295
1296 /***********************************************************************
1297 * Region Union
1298 ***********************************************************************/
1299
1300 /*!
1301 * Handle a non-overlapping band for the union operation. Just
1302 * Adds the rectangles into the region. Doesn't have to check for
1303 * subsumption or anything.
1304 *
1305 * Results:
1306 * None.
1307 *
1308 * \note Side Effects:
1309 * pReg->numRects is incremented and the final rectangles overwritten
1310 * with the rectangles we're passed.
1311 *
1312 */
1313 static void FASTCALL
1314 REGION_UnionNonO (
1315 PROSRGNDATA pReg,
1316 PRECTL r,
1317 PRECTL rEnd,
1318 INT top,
1319 INT bottom
1320 )
1321 {
1322 RECTL *pNextRect;
1323
1324 pNextRect = pReg->Buffer + pReg->rdh.nCount;
1325
1326 while (r != rEnd)
1327 {
1328 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1329 pNextRect->left = r->left;
1330 pNextRect->top = top;
1331 pNextRect->right = r->right;
1332 pNextRect->bottom = bottom;
1333 pReg->rdh.nCount += 1;
1334 pNextRect++;
1335 r++;
1336 }
1337 return;
1338 }
1339
1340 /*!
1341 * Handle an overlapping band for the union operation. Picks the
1342 * left-most rectangle each time and merges it into the region.
1343 *
1344 * Results:
1345 * None.
1346 *
1347 * \note Side Effects:
1348 * Rectangles are overwritten in pReg->rects and pReg->numRects will
1349 * be changed.
1350 *
1351 */
1352 static void FASTCALL
1353 REGION_UnionO (
1354 PROSRGNDATA pReg,
1355 PRECTL r1,
1356 PRECTL r1End,
1357 PRECTL r2,
1358 PRECTL r2End,
1359 INT top,
1360 INT bottom
1361 )
1362 {
1363 RECTL *pNextRect;
1364
1365 pNextRect = pReg->Buffer + pReg->rdh.nCount;
1366
1367 #define MERGERECT(r) \
1368 if ((pReg->rdh.nCount != 0) && \
1369 ((pNextRect-1)->top == top) && \
1370 ((pNextRect-1)->bottom == bottom) && \
1371 ((pNextRect-1)->right >= r->left)) \
1372 { \
1373 if ((pNextRect-1)->right < r->right) \
1374 { \
1375 (pNextRect-1)->right = r->right; \
1376 } \
1377 } \
1378 else \
1379 { \
1380 MEMCHECK(pReg, pNextRect, pReg->Buffer); \
1381 pNextRect->top = top; \
1382 pNextRect->bottom = bottom; \
1383 pNextRect->left = r->left; \
1384 pNextRect->right = r->right; \
1385 pReg->rdh.nCount += 1; \
1386 pNextRect += 1; \
1387 } \
1388 r++;
1389
1390 while ((r1 != r1End) && (r2 != r2End))
1391 {
1392 if (r1->left < r2->left)
1393 {
1394 MERGERECT(r1);
1395 }
1396 else
1397 {
1398 MERGERECT(r2);
1399 }
1400 }
1401
1402 if (r1 != r1End)
1403 {
1404 do
1405 {
1406 MERGERECT(r1);
1407 }
1408 while (r1 != r1End);
1409 }
1410 else while (r2 != r2End)
1411 {
1412 MERGERECT(r2);
1413 }
1414 return;
1415 }
1416
1417 /***********************************************************************
1418 * REGION_UnionRegion
1419 */
1420 static void FASTCALL
1421 REGION_UnionRegion(
1422 ROSRGNDATA *newReg,
1423 ROSRGNDATA *reg1,
1424 ROSRGNDATA *reg2
1425 )
1426 {
1427 /* checks all the simple cases */
1428
1429 /*
1430 * Region 1 and 2 are the same or region 1 is empty
1431 */
1432 if (reg1 == reg2 || 0 == reg1->rdh.nCount ||
1433 reg1->rdh.rcBound.right <= reg1->rdh.rcBound.left ||
1434 reg1->rdh.rcBound.bottom <= reg1->rdh.rcBound.top)
1435 {
1436 if (newReg != reg2)
1437 {
1438 REGION_CopyRegion(newReg, reg2);
1439 }
1440 return;
1441 }
1442
1443 /*
1444 * if nothing to union (region 2 empty)
1445 */
1446 if (0 == reg2->rdh.nCount ||
1447 reg2->rdh.rcBound.right <= reg2->rdh.rcBound.left ||
1448 reg2->rdh.rcBound.bottom <= reg2->rdh.rcBound.top)
1449 {
1450 if (newReg != reg1)
1451 {
1452 REGION_CopyRegion(newReg, reg1);
1453 }
1454 return;
1455 }
1456
1457 /*
1458 * Region 1 completely subsumes region 2
1459 */
1460 if (1 == reg1->rdh.nCount &&
1461 reg1->rdh.rcBound.left <= reg2->rdh.rcBound.left &&
1462 reg1->rdh.rcBound.top <= reg2->rdh.rcBound.top &&
1463 reg2->rdh.rcBound.right <= reg1->rdh.rcBound.right &&
1464 reg2->rdh.rcBound.bottom <= reg1->rdh.rcBound.bottom)
1465 {
1466 if (newReg != reg1)
1467 {
1468 REGION_CopyRegion(newReg, reg1);
1469 }
1470 return;
1471 }
1472
1473 /*
1474 * Region 2 completely subsumes region 1
1475 */
1476 if (1 == reg2->rdh.nCount &&
1477 reg2->rdh.rcBound.left <= reg1->rdh.rcBound.left &&
1478 reg2->rdh.rcBound.top <= reg1->rdh.rcBound.top &&
1479 reg1->rdh.rcBound.right <= reg2->rdh.rcBound.right &&
1480 reg1->rdh.rcBound.bottom <= reg2->rdh.rcBound.bottom)
1481 {
1482 if (newReg != reg2)
1483 {
1484 REGION_CopyRegion(newReg, reg2);
1485 }
1486 return;
1487 }
1488
1489 REGION_RegionOp (newReg, reg1, reg2, REGION_UnionO,
1490 REGION_UnionNonO, REGION_UnionNonO);
1491 newReg->rdh.rcBound.left = min(reg1->rdh.rcBound.left, reg2->rdh.rcBound.left);
1492 newReg->rdh.rcBound.top = min(reg1->rdh.rcBound.top, reg2->rdh.rcBound.top);
1493 newReg->rdh.rcBound.right = max(reg1->rdh.rcBound.right, reg2->rdh.rcBound.right);
1494 newReg->rdh.rcBound.bottom = max(reg1->rdh.rcBound.bottom, reg2->rdh.rcBound.bottom);
1495 }
1496
1497 /***********************************************************************
1498 * Region Subtraction
1499 ***********************************************************************/
1500
1501 /*!
1502 * Deal with non-overlapping band for subtraction. Any parts from
1503 * region 2 we discard. Anything from region 1 we add to the region.
1504 *
1505 * Results:
1506 * None.
1507 *
1508 * \note Side Effects:
1509 * pReg may be affected.
1510 *
1511 */
1512 static void FASTCALL
1513 REGION_SubtractNonO1(
1514 PROSRGNDATA pReg,
1515 PRECTL r,
1516 PRECTL rEnd,
1517 INT top,
1518 INT bottom
1519 )
1520 {
1521 RECTL *pNextRect;
1522
1523 pNextRect = pReg->Buffer + pReg->rdh.nCount;
1524
1525 while (r != rEnd)
1526 {
1527 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1528 pNextRect->left = r->left;
1529 pNextRect->top = top;
1530 pNextRect->right = r->right;
1531 pNextRect->bottom = bottom;
1532 pReg->rdh.nCount += 1;
1533 pNextRect++;
1534 r++;
1535 }
1536 return;
1537 }
1538
1539
1540 /*!
1541 * Overlapping band subtraction. x1 is the left-most point not yet
1542 * checked.
1543 *
1544 * Results:
1545 * None.
1546 *
1547 * \note Side Effects:
1548 * pReg may have rectangles added to it.
1549 *
1550 */
1551 static void FASTCALL
1552 REGION_SubtractO(
1553 PROSRGNDATA pReg,
1554 PRECTL r1,
1555 PRECTL r1End,
1556 PRECTL r2,
1557 PRECTL r2End,
1558 INT top,
1559 INT bottom
1560 )
1561 {
1562 RECTL *pNextRect;
1563 INT left;
1564
1565 left = r1->left;
1566 pNextRect = pReg->Buffer + pReg->rdh.nCount;
1567
1568 while ((r1 != r1End) && (r2 != r2End))
1569 {
1570 if (r2->right <= left)
1571 {
1572 /*
1573 * Subtrahend missed the boat: go to next subtrahend.
1574 */
1575 r2++;
1576 }
1577 else if (r2->left <= left)
1578 {
1579 /*
1580 * Subtrahend preceeds minuend: nuke left edge of minuend.
1581 */
1582 left = r2->right;
1583 if (left >= r1->right)
1584 {
1585 /*
1586 * Minuend completely covered: advance to next minuend and
1587 * reset left fence to edge of new minuend.
1588 */
1589 r1++;
1590 if (r1 != r1End)
1591 left = r1->left;
1592 }
1593 else
1594 {
1595 /*
1596 * Subtrahend now used up since it doesn't extend beyond
1597 * minuend
1598 */
1599 r2++;
1600 }
1601 }
1602 else if (r2->left < r1->right)
1603 {
1604 /*
1605 * Left part of subtrahend covers part of minuend: add uncovered
1606 * part of minuend to region and skip to next subtrahend.
1607 */
1608 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1609 pNextRect->left = left;
1610 pNextRect->top = top;
1611 pNextRect->right = r2->left;
1612 pNextRect->bottom = bottom;
1613 pReg->rdh.nCount += 1;
1614 pNextRect++;
1615 left = r2->right;
1616 if (left >= r1->right)
1617 {
1618 /*
1619 * Minuend used up: advance to new...
1620 */
1621 r1++;
1622 if (r1 != r1End)
1623 left = r1->left;
1624 }
1625 else
1626 {
1627 /*
1628 * Subtrahend used up
1629 */
1630 r2++;
1631 }
1632 }
1633 else
1634 {
1635 /*
1636 * Minuend used up: add any remaining piece before advancing.
1637 */
1638 if (r1->right > left)
1639 {
1640 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1641 pNextRect->left = left;
1642 pNextRect->top = top;
1643 pNextRect->right = r1->right;
1644 pNextRect->bottom = bottom;
1645 pReg->rdh.nCount += 1;
1646 pNextRect++;
1647 }
1648 r1++;
1649 if (r1 != r1End)
1650 left = r1->left;
1651 }
1652 }
1653
1654 /*
1655 * Add remaining minuend rectangles to region.
1656 */
1657 while (r1 != r1End)
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 r1++;
1667 if (r1 != r1End)
1668 {
1669 left = r1->left;
1670 }
1671 }
1672 return;
1673 }
1674
1675 /*!
1676 * Subtract regS from regM and leave the result in regD.
1677 * S stands for subtrahend, M for minuend and D for difference.
1678 *
1679 * Results:
1680 * TRUE.
1681 *
1682 * \note Side Effects:
1683 * regD is overwritten.
1684 *
1685 */
1686 static void FASTCALL
1687 REGION_SubtractRegion(
1688 ROSRGNDATA *regD,
1689 ROSRGNDATA *regM,
1690 ROSRGNDATA *regS
1691 )
1692 {
1693 /* check for trivial reject */
1694 if ( (!(regM->rdh.nCount)) || (!(regS->rdh.nCount)) ||
1695 (!EXTENTCHECK(&regM->rdh.rcBound, &regS->rdh.rcBound)) )
1696 {
1697 REGION_CopyRegion(regD, regM);
1698 return;
1699 }
1700
1701 REGION_RegionOp (regD, regM, regS, REGION_SubtractO,
1702 REGION_SubtractNonO1, NULL);
1703
1704 /*
1705 * Can't alter newReg's extents before we call miRegionOp because
1706 * it might be one of the source regions and miRegionOp depends
1707 * on the extents of those regions being the unaltered. Besides, this
1708 * way there's no checking against rectangles that will be nuked
1709 * due to coalescing, so we have to examine fewer rectangles.
1710 */
1711 REGION_SetExtents (regD);
1712 }
1713
1714 /***********************************************************************
1715 * REGION_XorRegion
1716 */
1717 static void FASTCALL
1718 REGION_XorRegion(
1719 ROSRGNDATA *dr,
1720 ROSRGNDATA *sra,
1721 ROSRGNDATA *srb
1722 )
1723 {
1724 HRGN htra, htrb;
1725 ROSRGNDATA *tra, *trb;
1726
1727 // FIXME: don't use a handle
1728 tra = REGION_AllocRgnWithHandle(sra->rdh.nCount + 1);
1729 if (!tra )
1730 {
1731 return;
1732 }
1733 htra = tra->BaseObject.hHmgr;
1734
1735 // FIXME: don't use a handle
1736 trb = REGION_AllocRgnWithHandle(srb->rdh.nCount + 1);
1737 if (!trb)
1738 {
1739 RGNOBJAPI_Unlock(tra);
1740 GreDeleteObject(htra);
1741 return;
1742 }
1743 htrb = trb->BaseObject.hHmgr;
1744
1745 REGION_SubtractRegion(tra, sra, srb);
1746 REGION_SubtractRegion(trb, srb, sra);
1747 REGION_UnionRegion(dr, tra, trb);
1748 RGNOBJAPI_Unlock(tra);
1749 RGNOBJAPI_Unlock(trb);
1750
1751 GreDeleteObject(htra);
1752 GreDeleteObject(htrb);
1753 return;
1754 }
1755
1756
1757 /*!
1758 * Adds a rectangle to a REGION
1759 */
1760 VOID FASTCALL
1761 REGION_UnionRectWithRgn(
1762 ROSRGNDATA *rgn,
1763 const RECTL *rect
1764 )
1765 {
1766 ROSRGNDATA region;
1767
1768 region.Buffer = &region.rdh.rcBound;
1769 region.rdh.nCount = 1;
1770 region.rdh.nRgnSize = sizeof(RECT);
1771 region.rdh.rcBound = *rect;
1772 REGION_UnionRegion(rgn, rgn, &region);
1773 }
1774
1775 BOOL FASTCALL
1776 REGION_CreateSimpleFrameRgn(
1777 PROSRGNDATA rgn,
1778 INT x,
1779 INT y
1780 )
1781 {
1782 RECTL rc[4];
1783 PRECTL prc;
1784
1785 if (x != 0 || y != 0)
1786 {
1787 prc = rc;
1788
1789 if (rgn->rdh.rcBound.bottom - rgn->rdh.rcBound.top > y * 2 &&
1790 rgn->rdh.rcBound.right - rgn->rdh.rcBound.left > x * 2)
1791 {
1792 if (y != 0)
1793 {
1794 /* top rectangle */
1795 prc->left = rgn->rdh.rcBound.left;
1796 prc->top = rgn->rdh.rcBound.top;
1797 prc->right = rgn->rdh.rcBound.right;
1798 prc->bottom = prc->top + y;
1799 prc++;
1800 }
1801
1802 if (x != 0)
1803 {
1804 /* left rectangle */
1805 prc->left = rgn->rdh.rcBound.left;
1806 prc->top = rgn->rdh.rcBound.top + y;
1807 prc->right = prc->left + x;
1808 prc->bottom = rgn->rdh.rcBound.bottom - y;
1809 prc++;
1810
1811 /* right rectangle */
1812 prc->left = rgn->rdh.rcBound.right - x;
1813 prc->top = rgn->rdh.rcBound.top + y;
1814 prc->right = rgn->rdh.rcBound.right;
1815 prc->bottom = rgn->rdh.rcBound.bottom - y;
1816 prc++;
1817 }
1818
1819 if (y != 0)
1820 {
1821 /* bottom rectangle */
1822 prc->left = rgn->rdh.rcBound.left;
1823 prc->top = rgn->rdh.rcBound.bottom - y;
1824 prc->right = rgn->rdh.rcBound.right;
1825 prc->bottom = rgn->rdh.rcBound.bottom;
1826 prc++;
1827 }
1828 }
1829
1830 if (prc != rc)
1831 {
1832 /* The frame results in a complex region. rcBounds remains
1833 the same, though. */
1834 rgn->rdh.nCount = (DWORD)(prc - rc);
1835 ASSERT(rgn->rdh.nCount > 1);
1836 rgn->rdh.nRgnSize = rgn->rdh.nCount * sizeof(RECT);
1837 rgn->Buffer = ExAllocatePoolWithTag(PagedPool, rgn->rdh.nRgnSize, TAG_REGION);
1838 if (!rgn->Buffer)
1839 {
1840 rgn->rdh.nRgnSize = 0;
1841 return FALSE;
1842 }
1843
1844 COPY_RECTS(rgn->Buffer, rc, rgn->rdh.nCount);
1845 }
1846 }
1847
1848 return TRUE;
1849 }
1850
1851 BOOL FASTCALL
1852 REGION_CreateFrameRgn(
1853 HRGN hDest,
1854 HRGN hSrc,
1855 INT x,
1856 INT y
1857 )
1858 {
1859 PROSRGNDATA srcObj, destObj;
1860 PRECTL rc;
1861 ULONG i;
1862
1863 if (!(srcObj = RGNOBJAPI_Lock(hSrc, NULL)))
1864 {
1865 return FALSE;
1866 }
1867 if (!REGION_NOT_EMPTY(srcObj))
1868 {
1869 RGNOBJAPI_Unlock(srcObj);
1870 return FALSE;
1871 }
1872 if (!(destObj = RGNOBJAPI_Lock(hDest, NULL)))
1873 {
1874 RGNOBJAPI_Unlock(srcObj);
1875 return FALSE;
1876 }
1877
1878 EMPTY_REGION(destObj);
1879 if (!REGION_CopyRegion(destObj, srcObj))
1880 {
1881 RGNOBJAPI_Unlock(destObj);
1882 RGNOBJAPI_Unlock(srcObj);
1883 return FALSE;
1884 }
1885
1886 if (REGION_Complexity(srcObj) == SIMPLEREGION)
1887 {
1888 if (!REGION_CreateSimpleFrameRgn(destObj, x, y))
1889 {
1890 EMPTY_REGION(destObj);
1891 RGNOBJAPI_Unlock(destObj);
1892 RGNOBJAPI_Unlock(srcObj);
1893 return FALSE;
1894 }
1895 }
1896 else
1897 {
1898 /* Original region moved to right */
1899 rc = srcObj->Buffer;
1900 for (i = 0; i < srcObj->rdh.nCount; i++)
1901 {
1902 rc->left += x;
1903 rc->right += x;
1904 rc++;
1905 }
1906 REGION_IntersectRegion(destObj, destObj, srcObj);
1907
1908 /* Original region moved to left */
1909 rc = srcObj->Buffer;
1910 for (i = 0; i < srcObj->rdh.nCount; i++)
1911 {
1912 rc->left -= 2 * x;
1913 rc->right -= 2 * x;
1914 rc++;
1915 }
1916 REGION_IntersectRegion(destObj, destObj, srcObj);
1917
1918 /* Original region moved down */
1919 rc = srcObj->Buffer;
1920 for (i = 0; i < srcObj->rdh.nCount; i++)
1921 {
1922 rc->left += x;
1923 rc->right += x;
1924 rc->top += y;
1925 rc->bottom += y;
1926 rc++;
1927 }
1928 REGION_IntersectRegion(destObj, destObj, srcObj);
1929
1930 /* Original region moved up */
1931 rc = srcObj->Buffer;
1932 for (i = 0; i < srcObj->rdh.nCount; i++)
1933 {
1934 rc->top -= 2 * y;
1935 rc->bottom -= 2 * y;
1936 rc++;
1937 }
1938 REGION_IntersectRegion(destObj, destObj, srcObj);
1939
1940 /* Restore the original region */
1941 rc = srcObj->Buffer;
1942 for (i = 0; i < srcObj->rdh.nCount; i++)
1943 {
1944 rc->top += y;
1945 rc->bottom += y;
1946 rc++;
1947 }
1948 REGION_SubtractRegion(destObj, srcObj, destObj);
1949 }
1950
1951 RGNOBJAPI_Unlock(destObj);
1952 RGNOBJAPI_Unlock(srcObj);
1953 return TRUE;
1954 }
1955
1956
1957 BOOL FASTCALL
1958 REGION_LPTODP(
1959 PDC dc,
1960 HRGN hDest,
1961 HRGN hSrc)
1962 {
1963 RECTL *pCurRect, *pEndRect;
1964 PROSRGNDATA srcObj = NULL;
1965 PROSRGNDATA destObj = NULL;
1966
1967 RECTL tmpRect;
1968 BOOL ret = FALSE;
1969 PDC_ATTR pdcattr;
1970
1971 if (!dc)
1972 return ret;
1973 pdcattr = dc->pdcattr;
1974
1975 if (pdcattr->iMapMode == MM_TEXT) // Requires only a translation
1976 {
1977 if (NtGdiCombineRgn(hDest, hSrc, 0, RGN_COPY) == ERROR)
1978 goto done;
1979
1980 NtGdiOffsetRgn(hDest, pdcattr->ptlViewportOrg.x - pdcattr->ptlWindowOrg.x,
1981 pdcattr->ptlViewportOrg.y - pdcattr->ptlWindowOrg.y);
1982 ret = TRUE;
1983 goto done;
1984 }
1985
1986 if ( !(srcObj = RGNOBJAPI_Lock(hSrc, NULL)) )
1987 goto done;
1988 if ( !(destObj = RGNOBJAPI_Lock(hDest, NULL)) )
1989 {
1990 RGNOBJAPI_Unlock(srcObj);
1991 goto done;
1992 }
1993 EMPTY_REGION(destObj);
1994
1995 pEndRect = srcObj->Buffer + srcObj->rdh.nCount;
1996 for (pCurRect = srcObj->Buffer; pCurRect < pEndRect; pCurRect++)
1997 {
1998 tmpRect = *pCurRect;
1999 tmpRect.left = XLPTODP(pdcattr, tmpRect.left);
2000 tmpRect.top = YLPTODP(pdcattr, tmpRect.top);
2001 tmpRect.right = XLPTODP(pdcattr, tmpRect.right);
2002 tmpRect.bottom = YLPTODP(pdcattr, tmpRect.bottom);
2003
2004 if (tmpRect.left > tmpRect.right)
2005 {
2006 INT tmp = tmpRect.left;
2007 tmpRect.left = tmpRect.right;
2008 tmpRect.right = tmp;
2009 }
2010 if (tmpRect.top > tmpRect.bottom)
2011 {
2012 INT tmp = tmpRect.top;
2013 tmpRect.top = tmpRect.bottom;
2014 tmpRect.bottom = tmp;
2015 }
2016
2017 REGION_UnionRectWithRgn(destObj, &tmpRect);
2018 }
2019 ret = TRUE;
2020
2021 RGNOBJAPI_Unlock(srcObj);
2022 RGNOBJAPI_Unlock(destObj);
2023
2024 done:
2025 return ret;
2026 }
2027
2028 PROSRGNDATA
2029 FASTCALL
2030 REGION_AllocRgnWithHandle(INT nReg)
2031 {
2032 HRGN hReg;
2033 PROSRGNDATA pReg;
2034
2035 pReg = (PROSRGNDATA)GDIOBJ_AllocateObject(GDIObjType_RGN_TYPE,
2036 sizeof(REGION),
2037 BASEFLAG_LOOKASIDE);
2038 if (!pReg)
2039 {
2040 DPRINT1("Could not allocate a palette.\n");
2041 return NULL;
2042 }
2043
2044 if (!GDIOBJ_hInsertObject(&pReg->BaseObject, GDI_OBJ_HMGR_POWNED))
2045 {
2046 DPRINT1("Could not insert palette into handle table.\n");
2047 GDIOBJ_vFreeObject(&pReg->BaseObject);
2048 return NULL;
2049 }
2050
2051 hReg = pReg->BaseObject.hHmgr;
2052
2053 if (nReg == 0 || nReg == 1)
2054 {
2055 /* Testing shows that > 95% of all regions have only 1 rect.
2056 Including that here saves us from having to do another allocation */
2057 pReg->Buffer = &pReg->rdh.rcBound;
2058 }
2059 else
2060 {
2061 pReg->Buffer = ExAllocatePoolWithTag(PagedPool, nReg * sizeof(RECT), TAG_REGION);
2062 if (!pReg->Buffer)
2063 {
2064 DPRINT1("Could not allocate region buffer\n");
2065 GDIOBJ_vDeleteObject(&pReg->BaseObject);
2066 return NULL;
2067 }
2068 }
2069
2070 EMPTY_REGION(pReg);
2071 pReg->rdh.dwSize = sizeof(RGNDATAHEADER);
2072 pReg->rdh.nCount = nReg;
2073 pReg->rdh.nRgnSize = nReg * sizeof(RECT);
2074 pReg->prgnattr = &pReg->rgnattr;
2075
2076 return pReg;
2077 }
2078
2079 BOOL
2080 NTAPI
2081 REGION_bAllocRgnAttr(PREGION prgn)
2082 {
2083 PPROCESSINFO ppi;
2084 PRGN_ATTR prgnattr;
2085
2086 ppi = PsGetCurrentProcessWin32Process();
2087 ASSERT(ppi);
2088
2089 prgnattr = GdiPoolAllocate(ppi->pPoolRgnAttr);
2090 if (!prgnattr)
2091 {
2092 DPRINT1("Could not allocate RGN attr\n");
2093 return FALSE;
2094 }
2095
2096 /* Set the object attribute in the handle table */
2097 prgn->prgnattr = prgnattr;
2098 GDIOBJ_vSetObjectAttr(&prgn->BaseObject, prgnattr);
2099
2100 return TRUE;
2101 }
2102
2103
2104 //
2105 // Allocate User Space Region Handle.
2106 //
2107 PROSRGNDATA
2108 FASTCALL
2109 REGION_AllocUserRgnWithHandle(INT nRgn)
2110 {
2111 PREGION prgn;
2112
2113 prgn = REGION_AllocRgnWithHandle(nRgn);
2114 if (!prgn)
2115 {
2116 return NULL;
2117 }
2118
2119 if (!REGION_bAllocRgnAttr(prgn))
2120 {
2121 ASSERT(FALSE);
2122 }
2123
2124 return prgn;
2125 }
2126
2127 VOID
2128 NTAPI
2129 REGION_vSyncRegion(PREGION pRgn)
2130 {
2131 PRGN_ATTR pRgn_Attr = NULL;
2132
2133 if (pRgn && pRgn->prgnattr != &pRgn->rgnattr)
2134 {
2135 pRgn_Attr = GDIOBJ_pvGetObjectAttr(&pRgn->BaseObject);
2136
2137 if ( pRgn_Attr )
2138 {
2139 _SEH2_TRY
2140 {
2141 if ( !(pRgn_Attr->AttrFlags & ATTR_CACHED) )
2142 {
2143 if ( pRgn_Attr->AttrFlags & (ATTR_RGN_VALID|ATTR_RGN_DIRTY) )
2144 {
2145 switch (pRgn_Attr->Flags)
2146 {
2147 case NULLREGION:
2148 EMPTY_REGION( pRgn );
2149 break;
2150
2151 case SIMPLEREGION:
2152 REGION_SetRectRgn( pRgn,
2153 pRgn_Attr->Rect.left,
2154 pRgn_Attr->Rect.top,
2155 pRgn_Attr->Rect.right,
2156 pRgn_Attr->Rect.bottom );
2157 break;
2158 }
2159 pRgn_Attr->AttrFlags &= ~ATTR_RGN_DIRTY;
2160 }
2161 }
2162 }
2163 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
2164 {
2165 }
2166 _SEH2_END;
2167 }
2168 }
2169
2170 }
2171
2172 PROSRGNDATA
2173 FASTCALL
2174 RGNOBJAPI_Lock(HRGN hRgn, PRGN_ATTR *ppRgn_Attr)
2175 {
2176 PROSRGNDATA pRgn = NULL;
2177
2178 pRgn = REGION_LockRgn(hRgn);
2179
2180 REGION_vSyncRegion(pRgn);
2181
2182 if (ppRgn_Attr)
2183 *ppRgn_Attr = pRgn->prgnattr;
2184
2185 return pRgn;
2186 }
2187
2188 VOID
2189 FASTCALL
2190 RGNOBJAPI_Unlock(PROSRGNDATA pRgn)
2191 {
2192 PRGN_ATTR pRgn_Attr;
2193
2194 if (pRgn && GreGetObjectOwner(pRgn->BaseObject.hHmgr) == GDI_OBJ_HMGR_POWNED)
2195 {
2196 pRgn_Attr = GDIOBJ_pvGetObjectAttr(&pRgn->BaseObject);
2197
2198 if ( pRgn_Attr )
2199 {
2200 _SEH2_TRY
2201 {
2202 if ( pRgn_Attr->AttrFlags & ATTR_RGN_VALID )
2203 {
2204 pRgn_Attr->Flags = REGION_Complexity( pRgn );
2205 pRgn_Attr->Rect.left = pRgn->rdh.rcBound.left;
2206 pRgn_Attr->Rect.top = pRgn->rdh.rcBound.top;
2207 pRgn_Attr->Rect.right = pRgn->rdh.rcBound.right;
2208 pRgn_Attr->Rect.bottom = pRgn->rdh.rcBound.bottom;
2209 }
2210 }
2211 _SEH2_EXCEPT(EXCEPTION_EXECUTE_HANDLER)
2212 {
2213 }
2214 _SEH2_END;
2215 }
2216 }
2217 REGION_UnlockRgn(pRgn);
2218 }
2219
2220 /*
2221 System Regions:
2222 These regions do not use attribute sections and when allocated, use gdiobj
2223 level functions.
2224 */
2225 //
2226 // System Region Functions
2227 //
2228 PROSRGNDATA
2229 FASTCALL
2230 IntSysCreateRectpRgn(INT LeftRect, INT TopRect, INT RightRect, INT BottomRect)
2231 {
2232 PREGION prgn;
2233
2234 /* Allocate a region, witout a handle */
2235 prgn = (PREGION)GDIOBJ_AllocateObject(GDIObjType_RGN_TYPE, sizeof(REGION), 0);
2236 if (!prgn)
2237 {
2238 return NULL;
2239 }
2240
2241 /* Initialize it */
2242 prgn->Buffer = &prgn->rdh.rcBound;
2243 prgn->prgnattr = &prgn->rgnattr;
2244 REGION_SetRectRgn(prgn, LeftRect, TopRect, RightRect, BottomRect);
2245
2246 return prgn;
2247 }
2248
2249 HRGN
2250 FASTCALL
2251 IntSysCreateRectRgn(INT LeftRect, INT TopRect, INT RightRect, INT BottomRect)
2252 {
2253 PREGION prgn;
2254 HRGN hrgn;
2255
2256 /* Allocate a region, witout a handle */
2257 prgn = (PREGION)GDIOBJ_AllocObjWithHandle(GDI_OBJECT_TYPE_REGION, sizeof(REGION));
2258 if (!prgn)
2259 {
2260 return NULL;
2261 }
2262
2263 /* Initialize it */
2264 prgn->Buffer = &prgn->rdh.rcBound;
2265 REGION_SetRectRgn(prgn, LeftRect, TopRect, RightRect, BottomRect);
2266 hrgn = prgn->BaseObject.hHmgr;
2267 prgn->prgnattr = &prgn->rgnattr;
2268
2269 REGION_UnlockRgn(prgn);
2270
2271 return hrgn;
2272 }
2273
2274 BOOL INTERNAL_CALL
2275 REGION_Cleanup(PVOID ObjectBody)
2276 {
2277 PROSRGNDATA pRgn = (PROSRGNDATA)ObjectBody;
2278 PPROCESSINFO ppi = PsGetCurrentProcessWin32Process();
2279 ASSERT(ppi);
2280
2281 ASSERT(pRgn->prgnattr);
2282 if (pRgn->prgnattr != &pRgn->rgnattr)
2283 GdiPoolFree(ppi->pPoolRgnAttr, pRgn->prgnattr);
2284
2285 if (pRgn->Buffer && pRgn->Buffer != &pRgn->rdh.rcBound)
2286 ExFreePoolWithTag(pRgn->Buffer, TAG_REGION);
2287 return TRUE;
2288 }
2289
2290 VOID FASTCALL
2291 REGION_Delete(PROSRGNDATA pRgn)
2292 {
2293 if ( pRgn == prgnDefault) return;
2294 GDIOBJ_vDeleteObject(&pRgn->BaseObject);
2295 }
2296
2297 VOID FASTCALL
2298 IntGdiReleaseRaoRgn(PDC pDC)
2299 {
2300 INT Index = GDI_HANDLE_GET_INDEX(pDC->BaseObject.hHmgr);
2301 PGDI_TABLE_ENTRY Entry = &GdiHandleTable->Entries[Index];
2302 pDC->fs |= DC_FLAG_DIRTY_RAO;
2303 Entry->Flags |= GDI_ENTRY_VALIDATE_VIS;
2304 RECTL_vSetEmptyRect(&pDC->erclClip);
2305 }
2306
2307 VOID FASTCALL
2308 IntGdiReleaseVisRgn(PDC pDC)
2309 {
2310 INT Index = GDI_HANDLE_GET_INDEX(pDC->BaseObject.hHmgr);
2311 PGDI_TABLE_ENTRY Entry = &GdiHandleTable->Entries[Index];
2312 pDC->fs |= DC_FLAG_DIRTY_RAO;
2313 Entry->Flags |= GDI_ENTRY_VALIDATE_VIS;
2314 RECTL_vSetEmptyRect(&pDC->erclClip);
2315 REGION_Delete(pDC->prgnVis);
2316 pDC->prgnVis = prgnDefault;
2317 }
2318
2319 VOID FASTCALL
2320 IntUpdateVisRectRgn(PDC pDC, PROSRGNDATA pRgn)
2321 {
2322 INT Index = GDI_HANDLE_GET_INDEX(pDC->BaseObject.hHmgr);
2323 PGDI_TABLE_ENTRY Entry = &GdiHandleTable->Entries[Index];
2324 PDC_ATTR pdcattr;
2325 RECTL rcl;
2326
2327 if (Entry->Flags & GDI_ENTRY_VALIDATE_VIS)
2328 {
2329 pdcattr = pDC->pdcattr;
2330
2331 pdcattr->VisRectRegion.Flags = REGION_Complexity(pRgn);
2332
2333 if (pRgn && pdcattr->VisRectRegion.Flags != NULLREGION)
2334 {
2335 rcl.left = pRgn->rdh.rcBound.left;
2336 rcl.top = pRgn->rdh.rcBound.top;
2337 rcl.right = pRgn->rdh.rcBound.right;
2338 rcl.bottom = pRgn->rdh.rcBound.bottom;
2339
2340 rcl.left -= pDC->erclWindow.left;
2341 rcl.top -= pDC->erclWindow.top;
2342 rcl.right -= pDC->erclWindow.left;
2343 rcl.bottom -= pDC->erclWindow.top;
2344 }
2345 else
2346 RECTL_vSetEmptyRect(&rcl);
2347
2348 pdcattr->VisRectRegion.Rect = rcl;
2349
2350 Entry->Flags &= ~GDI_ENTRY_VALIDATE_VIS;
2351 }
2352 }
2353
2354 BOOL
2355 FASTCALL
2356 IntGdiSetRegionOwner(HRGN hRgn, DWORD OwnerMask)
2357 {
2358 PREGION prgn;
2359 PRGN_ATTR prgnattr;
2360 PPROCESSINFO ppi;
2361
2362 prgn = REGION_LockRgn(hRgn);
2363 if (!prgn)
2364 {
2365 return FALSE;
2366 }
2367
2368 prgnattr = GDIOBJ_pvGetObjectAttr(&prgn->BaseObject);
2369 if (prgnattr)
2370 {
2371 GDIOBJ_vSetObjectAttr(&prgn->BaseObject, NULL);
2372 prgn->prgnattr = NULL;
2373 ppi = PsGetCurrentProcessWin32Process();
2374 GdiPoolFree(ppi->pPoolRgnAttr, prgnattr);
2375 }
2376 RGNOBJAPI_Unlock(prgn);
2377
2378 return GreSetObjectOwner(hRgn, OwnerMask);
2379 }
2380
2381 INT
2382 FASTCALL
2383 IntGdiCombineRgn(PROSRGNDATA destRgn,
2384 PROSRGNDATA src1Rgn,
2385 PROSRGNDATA src2Rgn,
2386 INT CombineMode)
2387 {
2388 INT result = ERROR;
2389
2390 if (destRgn)
2391 {
2392 if (src1Rgn)
2393 {
2394 if (CombineMode == RGN_COPY)
2395 {
2396 if ( !REGION_CopyRegion(destRgn, src1Rgn) )
2397 return ERROR;
2398 result = REGION_Complexity(destRgn);
2399 }
2400 else
2401 {
2402 if (src2Rgn)
2403 {
2404 switch (CombineMode)
2405 {
2406 case RGN_AND:
2407 REGION_IntersectRegion(destRgn, src1Rgn, src2Rgn);
2408 break;
2409 case RGN_OR:
2410 REGION_UnionRegion(destRgn, src1Rgn, src2Rgn);
2411 break;
2412 case RGN_XOR:
2413 REGION_XorRegion(destRgn, src1Rgn, src2Rgn);
2414 break;
2415 case RGN_DIFF:
2416 REGION_SubtractRegion(destRgn, src1Rgn, src2Rgn);
2417 break;
2418 }
2419 result = REGION_Complexity(destRgn);
2420 }
2421 else if (src2Rgn == NULL)
2422 {
2423 DPRINT1("IntGdiCombineRgn requires hSrc2 != NULL for combine mode %d!\n", CombineMode);
2424 EngSetLastError(ERROR_INVALID_HANDLE);
2425 ASSERT(FALSE);
2426 }
2427 }
2428 }
2429 else
2430 {
2431 DPRINT("IntGdiCombineRgn: hSrc1 unavailable\n");
2432 EngSetLastError(ERROR_INVALID_HANDLE);
2433 }
2434 }
2435 else
2436 {
2437 DPRINT("IntGdiCombineRgn: hDest unavailable\n");
2438 EngSetLastError(ERROR_INVALID_HANDLE);
2439 }
2440 return result;
2441 }
2442
2443 INT FASTCALL
2444 REGION_GetRgnBox(
2445 PROSRGNDATA Rgn,
2446 PRECTL pRect
2447 )
2448 {
2449 DWORD ret;
2450
2451 if (Rgn)
2452 {
2453 *pRect = Rgn->rdh.rcBound;
2454 ret = REGION_Complexity(Rgn);
2455
2456 return ret;
2457 }
2458 return 0; //if invalid region return zero
2459 }
2460
2461 INT APIENTRY
2462 IntGdiGetRgnBox(
2463 HRGN hRgn,
2464 PRECTL pRect
2465 )
2466 {
2467 PROSRGNDATA Rgn;
2468 DWORD ret;
2469
2470 if (!(Rgn = RGNOBJAPI_Lock(hRgn, NULL)))
2471 {
2472 return ERROR;
2473 }
2474
2475 ret = REGION_GetRgnBox(Rgn, pRect);
2476 RGNOBJAPI_Unlock(Rgn);
2477
2478 return ret;
2479 }
2480
2481 BOOL
2482 FASTCALL
2483 IntGdiPaintRgn(
2484 PDC dc,
2485 HRGN hRgn
2486 )
2487 {
2488 HRGN tmpVisRgn;
2489 PROSRGNDATA visrgn;
2490 CLIPOBJ* ClipRegion;
2491 BOOL bRet = FALSE;
2492 POINTL BrushOrigin;
2493 SURFACE *psurf;
2494 PDC_ATTR pdcattr;
2495
2496 if (!dc) return FALSE;
2497 pdcattr = dc->pdcattr;
2498
2499 ASSERT(!(pdcattr->ulDirty_ & (DIRTY_FILL | DC_BRUSH_DIRTY)));
2500
2501 if (!(tmpVisRgn = IntSysCreateRectRgn(0, 0, 0, 0))) return FALSE;
2502
2503 // Transform region into device co-ords
2504 if (!REGION_LPTODP(dc, tmpVisRgn, hRgn) ||
2505 NtGdiOffsetRgn(tmpVisRgn, dc->ptlDCOrig.x, dc->ptlDCOrig.y) == ERROR)
2506 {
2507 GreDeleteObject(tmpVisRgn);
2508 return FALSE;
2509 }
2510
2511 NtGdiCombineRgn(tmpVisRgn, tmpVisRgn, dc->rosdc.hGCClipRgn, RGN_AND);
2512
2513 visrgn = RGNOBJAPI_Lock(tmpVisRgn, NULL);
2514 if (visrgn == NULL)
2515 {
2516 GreDeleteObject(tmpVisRgn);
2517 return FALSE;
2518 }
2519
2520 ClipRegion = IntEngCreateClipRegion(visrgn->rdh.nCount,
2521 visrgn->Buffer,
2522 &visrgn->rdh.rcBound );
2523 ASSERT(ClipRegion);
2524
2525 BrushOrigin.x = pdcattr->ptlBrushOrigin.x;
2526 BrushOrigin.y = pdcattr->ptlBrushOrigin.y;
2527 psurf = dc->dclevel.pSurface;
2528 /* FIXME - Handle psurf == NULL !!!! */
2529
2530 bRet = IntEngPaint(&psurf->SurfObj,
2531 ClipRegion,
2532 &dc->eboFill.BrushObject,
2533 &BrushOrigin,
2534 0xFFFF);//FIXME:don't know what to put here
2535
2536 RGNOBJAPI_Unlock(visrgn);
2537 GreDeleteObject(tmpVisRgn);
2538
2539 // Fill the region
2540 return bRet;
2541 }
2542
2543 BOOL
2544 FASTCALL
2545 REGION_RectInRegion(
2546 PROSRGNDATA Rgn,
2547 const RECTL *rect
2548 )
2549 {
2550 PRECTL pCurRect, pRectEnd;
2551 RECT rc;
2552
2553 /* swap the coordinates to make right >= left and bottom >= top */
2554 /* (region building rectangles are normalized the same way) */
2555 if( rect->top > rect->bottom) {
2556 rc.top = rect->bottom;
2557 rc.bottom = rect->top;
2558 } else {
2559 rc.top = rect->top;
2560 rc.bottom = rect->bottom;
2561 }
2562 if( rect->right < rect->left) {
2563 rc.right = rect->left;
2564 rc.left = rect->right;
2565 } else {
2566 rc.right = rect->right;
2567 rc.left = rect->left;
2568 }
2569
2570 /* this is (just) a useful optimization */
2571 if ((Rgn->rdh.nCount > 0) && EXTENTCHECK(&Rgn->rdh.rcBound, &rc))
2572 {
2573 for (pCurRect = Rgn->Buffer, pRectEnd = pCurRect +
2574 Rgn->rdh.nCount; pCurRect < pRectEnd; pCurRect++)
2575 {
2576 if (pCurRect->bottom <= rc.top)
2577 continue; /* not far enough down yet */
2578
2579 if (pCurRect->top >= rc.bottom)
2580 break; /* too far down */
2581
2582 if (pCurRect->right <= rc.left)
2583 continue; /* not far enough over yet */
2584
2585 if (pCurRect->left >= rc.right) {
2586 continue;
2587 }
2588
2589 return TRUE;
2590 }
2591 }
2592 return FALSE;
2593 }
2594
2595 VOID
2596 FASTCALL
2597 REGION_SetRectRgn(
2598 PROSRGNDATA rgn,
2599 INT LeftRect,
2600 INT TopRect,
2601 INT RightRect,
2602 INT BottomRect
2603 )
2604 {
2605 PRECTL firstRect;
2606
2607 if (LeftRect > RightRect)
2608 {
2609 INT tmp = LeftRect;
2610 LeftRect = RightRect;
2611 RightRect = tmp;
2612 }
2613 if (TopRect > BottomRect)
2614 {
2615 INT tmp = TopRect;
2616 TopRect = BottomRect;
2617 BottomRect = tmp;
2618 }
2619
2620 if ((LeftRect != RightRect) && (TopRect != BottomRect))
2621 {
2622 firstRect = rgn->Buffer;
2623 ASSERT(firstRect);
2624 firstRect->left = rgn->rdh.rcBound.left = LeftRect;
2625 firstRect->top = rgn->rdh.rcBound.top = TopRect;
2626 firstRect->right = rgn->rdh.rcBound.right = RightRect;
2627 firstRect->bottom = rgn->rdh.rcBound.bottom = BottomRect;
2628 rgn->rdh.nCount = 1;
2629 rgn->rdh.iType = RDH_RECTANGLES;
2630 }
2631 else
2632 {
2633 EMPTY_REGION(rgn);
2634 }
2635 }
2636
2637 INT
2638 FASTCALL
2639 IntGdiOffsetRgn(
2640 PROSRGNDATA rgn,
2641 INT XOffset,
2642 INT YOffset )
2643 {
2644 if (XOffset || YOffset)
2645 {
2646 int nbox = rgn->rdh.nCount;
2647 PRECTL pbox = rgn->Buffer;
2648
2649 if (nbox && pbox)
2650 {
2651 while (nbox--)
2652 {
2653 pbox->left += XOffset;
2654 pbox->right += XOffset;
2655 pbox->top += YOffset;
2656 pbox->bottom += YOffset;
2657 pbox++;
2658 }
2659 if (rgn->Buffer != &rgn->rdh.rcBound)
2660 {
2661 rgn->rdh.rcBound.left += XOffset;
2662 rgn->rdh.rcBound.right += XOffset;
2663 rgn->rdh.rcBound.top += YOffset;
2664 rgn->rdh.rcBound.bottom += YOffset;
2665 }
2666 }
2667 }
2668 return REGION_Complexity(rgn);
2669 }
2670
2671 /***********************************************************************
2672 * REGION_InsertEdgeInET
2673 *
2674 * Insert the given edge into the edge table.
2675 * First we must find the correct bucket in the
2676 * Edge table, then find the right slot in the
2677 * bucket. Finally, we can insert it.
2678 *
2679 */
2680 static void FASTCALL
2681 REGION_InsertEdgeInET(
2682 EdgeTable *ET,
2683 EdgeTableEntry *ETE,
2684 INT scanline,
2685 ScanLineListBlock **SLLBlock,
2686 INT *iSLLBlock
2687 )
2688 {
2689 EdgeTableEntry *start, *prev;
2690 ScanLineList *pSLL, *pPrevSLL;
2691 ScanLineListBlock *tmpSLLBlock;
2692
2693 /*
2694 * find the right bucket to put the edge into
2695 */
2696 pPrevSLL = &ET->scanlines;
2697 pSLL = pPrevSLL->next;
2698 while (pSLL && (pSLL->scanline < scanline))
2699 {
2700 pPrevSLL = pSLL;
2701 pSLL = pSLL->next;
2702 }
2703
2704 /*
2705 * reassign pSLL (pointer to ScanLineList) if necessary
2706 */
2707 if ((!pSLL) || (pSLL->scanline > scanline))
2708 {
2709 if (*iSLLBlock > SLLSPERBLOCK-1)
2710 {
2711 tmpSLLBlock = ExAllocatePoolWithTag(PagedPool, sizeof(ScanLineListBlock), TAG_REGION);
2712 if (!tmpSLLBlock)
2713 {
2714 DPRINT1("REGION_InsertEdgeInETL(): Can't alloc SLLB\n");
2715 /* FIXME - free resources? */
2716 return;
2717 }
2718 (*SLLBlock)->next = tmpSLLBlock;
2719 tmpSLLBlock->next = (ScanLineListBlock *)NULL;
2720 *SLLBlock = tmpSLLBlock;
2721 *iSLLBlock = 0;
2722 }
2723 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2724
2725 pSLL->next = pPrevSLL->next;
2726 pSLL->edgelist = (EdgeTableEntry *)NULL;
2727 pPrevSLL->next = pSLL;
2728 }
2729 pSLL->scanline = scanline;
2730
2731 /*
2732 * now insert the edge in the right bucket
2733 */
2734 prev = (EdgeTableEntry *)NULL;
2735 start = pSLL->edgelist;
2736 while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2737 {
2738 prev = start;
2739 start = start->next;
2740 }
2741 ETE->next = start;
2742
2743 if (prev)
2744 prev->next = ETE;
2745 else
2746 pSLL->edgelist = ETE;
2747 }
2748
2749 /***********************************************************************
2750 * REGION_loadAET
2751 *
2752 * This routine moves EdgeTableEntries from the
2753 * EdgeTable into the Active Edge Table,
2754 * leaving them sorted by smaller x coordinate.
2755 *
2756 */
2757 static void FASTCALL
2758 REGION_loadAET(
2759 EdgeTableEntry *AET,
2760 EdgeTableEntry *ETEs
2761 )
2762 {
2763 EdgeTableEntry *pPrevAET;
2764 EdgeTableEntry *tmp;
2765
2766 pPrevAET = AET;
2767 AET = AET->next;
2768 while (ETEs)
2769 {
2770 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2771 {
2772 pPrevAET = AET;
2773 AET = AET->next;
2774 }
2775 tmp = ETEs->next;
2776 ETEs->next = AET;
2777 if (AET)
2778 AET->back = ETEs;
2779 ETEs->back = pPrevAET;
2780 pPrevAET->next = ETEs;
2781 pPrevAET = ETEs;
2782
2783 ETEs = tmp;
2784 }
2785 }
2786
2787 /***********************************************************************
2788 * REGION_computeWAET
2789 *
2790 * This routine links the AET by the
2791 * nextWETE (winding EdgeTableEntry) link for
2792 * use by the winding number rule. The final
2793 * Active Edge Table (AET) might look something
2794 * like:
2795 *
2796 * AET
2797 * ---------- --------- ---------
2798 * |ymax | |ymax | |ymax |
2799 * | ... | |... | |... |
2800 * |next |->|next |->|next |->...
2801 * |nextWETE| |nextWETE| |nextWETE|
2802 * --------- --------- ^--------
2803 * | | |
2804 * V-------------------> V---> ...
2805 *
2806 */
2807 static void FASTCALL
2808 REGION_computeWAET(EdgeTableEntry *AET)
2809 {
2810 register EdgeTableEntry *pWETE;
2811 register int inside = 1;
2812 register int isInside = 0;
2813
2814 AET->nextWETE = (EdgeTableEntry *)NULL;
2815 pWETE = AET;
2816 AET = AET->next;
2817 while (AET)
2818 {
2819 if (AET->ClockWise)
2820 isInside++;
2821 else
2822 isInside--;
2823
2824 if ( (!inside && !isInside) ||
2825 ( inside && isInside) )
2826 {
2827 pWETE->nextWETE = AET;
2828 pWETE = AET;
2829 inside = !inside;
2830 }
2831 AET = AET->next;
2832 }
2833 pWETE->nextWETE = (EdgeTableEntry *)NULL;
2834 }
2835
2836 /***********************************************************************
2837 * REGION_InsertionSort
2838 *
2839 * Just a simple insertion sort using
2840 * pointers and back pointers to sort the Active
2841 * Edge Table.
2842 *
2843 */
2844 static BOOL FASTCALL
2845 REGION_InsertionSort(EdgeTableEntry *AET)
2846 {
2847 EdgeTableEntry *pETEchase;
2848 EdgeTableEntry *pETEinsert;
2849 EdgeTableEntry *pETEchaseBackTMP;
2850 BOOL changed = FALSE;
2851
2852 AET = AET->next;
2853 while (AET)
2854 {
2855 pETEinsert = AET;
2856 pETEchase = AET;
2857 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2858 pETEchase = pETEchase->back;
2859
2860 AET = AET->next;
2861 if (pETEchase != pETEinsert)
2862 {
2863 pETEchaseBackTMP = pETEchase->back;
2864 pETEinsert->back->next = AET;
2865 if (AET)
2866 AET->back = pETEinsert->back;
2867 pETEinsert->next = pETEchase;
2868 pETEchase->back->next = pETEinsert;
2869 pETEchase->back = pETEinsert;
2870 pETEinsert->back = pETEchaseBackTMP;
2871 changed = TRUE;
2872 }
2873 }
2874 return changed;
2875 }
2876
2877 /***********************************************************************
2878 * REGION_FreeStorage
2879 *
2880 * Clean up our act.
2881 */
2882 static void FASTCALL
2883 REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2884 {
2885 ScanLineListBlock *tmpSLLBlock;
2886
2887 while (pSLLBlock)
2888 {
2889 tmpSLLBlock = pSLLBlock->next;
2890 ExFreePool(pSLLBlock);
2891 pSLLBlock = tmpSLLBlock;
2892 }
2893 }
2894
2895
2896 /***********************************************************************
2897 * REGION_PtsToRegion
2898 *
2899 * Create an array of rectangles from a list of points.
2900 */
2901 static int FASTCALL
2902 REGION_PtsToRegion(
2903 int numFullPtBlocks,
2904 int iCurPtBlock,
2905 POINTBLOCK *FirstPtBlock,
2906 ROSRGNDATA *reg)
2907 {
2908 RECTL *rects;
2909 POINT *pts;
2910 POINTBLOCK *CurPtBlock;
2911 int i;
2912 RECTL *extents, *temp;
2913 INT numRects;
2914
2915 extents = &reg->rdh.rcBound;
2916
2917 numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2918
2919 if (!(temp = ExAllocatePoolWithTag(PagedPool, numRects * sizeof(RECT), TAG_REGION)))
2920 {
2921 return 0;
2922 }
2923 if (reg->Buffer != NULL)
2924 {
2925 COPY_RECTS(temp, reg->Buffer, reg->rdh.nCount);
2926 if (reg->Buffer != &reg->rdh.rcBound)
2927 ExFreePoolWithTag(reg->Buffer, TAG_REGION);
2928 }
2929 reg->Buffer = temp;
2930
2931 reg->rdh.nCount = numRects;
2932 CurPtBlock = FirstPtBlock;
2933 rects = reg->Buffer - 1;
2934 numRects = 0;
2935 extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
2936
2937 for ( ; numFullPtBlocks >= 0; numFullPtBlocks--)
2938 {
2939 /* the loop uses 2 points per iteration */
2940 i = NUMPTSTOBUFFER >> 1;
2941 if (!numFullPtBlocks)
2942 i = iCurPtBlock >> 1;
2943 for (pts = CurPtBlock->pts; i--; pts += 2)
2944 {
2945 if (pts->x == pts[1].x)
2946 continue;
2947 if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2948 pts[1].x == rects->right &&
2949 (numRects == 1 || rects[-1].top != rects->top) &&
2950 (i && pts[2].y > pts[1].y))
2951 {
2952 rects->bottom = pts[1].y + 1;
2953 continue;
2954 }
2955 numRects++;
2956 rects++;
2957 rects->left = pts->x;
2958 rects->top = pts->y;
2959 rects->right = pts[1].x;
2960 rects->bottom = pts[1].y + 1;
2961 if (rects->left < extents->left)
2962 extents->left = rects->left;
2963 if (rects->right > extents->right)
2964 extents->right = rects->right;
2965 }
2966 CurPtBlock = CurPtBlock->next;
2967 }
2968
2969 if (numRects)
2970 {
2971 extents->top = reg->Buffer->top;
2972 extents->bottom = rects->bottom;
2973 }
2974 else
2975 {
2976 extents->left = 0;
2977 extents->top = 0;
2978 extents->right = 0;
2979 extents->bottom = 0;
2980 }
2981 reg->rdh.nCount = numRects;
2982
2983 return(TRUE);
2984 }
2985
2986 /***********************************************************************
2987 * REGION_CreateEdgeTable
2988 *
2989 * This routine creates the edge table for
2990 * scan converting polygons.
2991 * The Edge Table (ET) looks like:
2992 *
2993 * EdgeTable
2994 * --------
2995 * | ymax | ScanLineLists
2996 * |scanline|-->------------>-------------->...
2997 * -------- |scanline| |scanline|
2998 * |edgelist| |edgelist|
2999 * --------- ---------
3000 * | |
3001 * | |
3002 * V V
3003 * list of ETEs list of ETEs
3004 *
3005 * where ETE is an EdgeTableEntry data structure,
3006 * and there is one ScanLineList per scanline at
3007 * which an edge is initially entered.
3008 *
3009 */
3010 static void FASTCALL
3011 REGION_CreateETandAET(
3012 const ULONG *Count,
3013 INT nbpolygons,
3014 const POINT *pts,
3015 EdgeTable *ET,
3016 EdgeTableEntry *AET,
3017 EdgeTableEntry *pETEs,
3018 ScanLineListBlock *pSLLBlock
3019 )
3020 {
3021 const POINT *top, *bottom;
3022 const POINT *PrevPt, *CurrPt, *EndPt;
3023 INT poly, count;
3024 int iSLLBlock = 0;
3025 int dy;
3026
3027
3028 /*
3029 * initialize the Active Edge Table
3030 */
3031 AET->next = (EdgeTableEntry *)NULL;
3032 AET->back = (EdgeTableEntry *)NULL;
3033 AET->nextWETE = (EdgeTableEntry *)NULL;
3034 AET->bres.minor_axis = SMALL_COORDINATE;
3035
3036 /*
3037 * initialize the Edge Table.
3038 */
3039 ET->scanlines.next = (ScanLineList *)NULL;
3040 ET->ymax = SMALL_COORDINATE;
3041 ET->ymin = LARGE_COORDINATE;
3042 pSLLBlock->next = (ScanLineListBlock *)NULL;
3043
3044 EndPt = pts - 1;
3045 for (poly = 0; poly < nbpolygons; poly++)
3046 {
3047 count = Count[poly];
3048 EndPt += count;
3049 if (count < 2)
3050 continue;
3051
3052 PrevPt = EndPt;
3053
3054 /*
3055 * for each vertex in the array of points.
3056 * In this loop we are dealing with two vertices at
3057 * a time -- these make up one edge of the polygon.
3058 */
3059 while (count--)
3060 {
3061 CurrPt = pts++;
3062
3063 /*
3064 * find out which point is above and which is below.
3065 */
3066 if (PrevPt->y > CurrPt->y)
3067 {
3068 bottom = PrevPt, top = CurrPt;
3069 pETEs->ClockWise = 0;
3070 }
3071 else
3072 {
3073 bottom = CurrPt, top = PrevPt;
3074 pETEs->ClockWise = 1;
3075 }
3076
3077 /*
3078 * don't add horizontal edges to the Edge table.
3079 */
3080 if (bottom->y != top->y)
3081 {
3082 pETEs->ymax = bottom->y-1;
3083 /* -1 so we don't get last scanline */
3084
3085 /*
3086 * initialize integer edge algorithm
3087 */
3088 dy = bottom->y - top->y;
3089 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
3090
3091 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
3092 &iSLLBlock);
3093
3094 if (PrevPt->y > ET->ymax)
3095 ET->ymax = PrevPt->y;
3096 if (PrevPt->y < ET->ymin)
3097 ET->ymin = PrevPt->y;
3098 pETEs++;
3099 }
3100
3101 PrevPt = CurrPt;
3102 }
3103 }
3104 }
3105
3106 HRGN FASTCALL
3107 IntCreatePolyPolygonRgn(
3108 POINT *Pts,
3109 PULONG Count,
3110 INT nbpolygons,
3111 INT mode
3112 )
3113 {
3114 HRGN hrgn;
3115 ROSRGNDATA *region;
3116 EdgeTableEntry *pAET; /* Active Edge Table */
3117 INT y; /* current scanline */
3118 int iPts = 0; /* number of pts in buffer */
3119 EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
3120 ScanLineList *pSLL; /* current scanLineList */
3121 POINT *pts; /* output buffer */
3122 EdgeTableEntry *pPrevAET; /* ptr to previous AET */
3123 EdgeTable ET; /* header node for ET */
3124 EdgeTableEntry AET; /* header node for AET */
3125 EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
3126 ScanLineListBlock SLLBlock; /* header for scanlinelist */
3127 int fixWAET = FALSE;
3128 POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
3129 POINTBLOCK *tmpPtBlock;
3130 int numFullPtBlocks = 0;
3131 INT poly, total;
3132
3133 if (mode == 0 || mode > 2) return 0;
3134
3135 if (!(region = REGION_AllocUserRgnWithHandle(nbpolygons)))
3136 return 0;
3137 hrgn = region->BaseObject.hHmgr;
3138
3139 /* special case a rectangle */
3140
3141 if (((nbpolygons == 1) && ((*Count == 4) ||
3142 ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
3143 (((Pts[0].y == Pts[1].y) &&
3144 (Pts[1].x == Pts[2].x) &&
3145 (Pts[2].y == Pts[3].y) &&
3146 (Pts[3].x == Pts[0].x)) ||
3147 ((Pts[0].x == Pts[1].x) &&
3148 (Pts[1].y == Pts[2].y) &&
3149 (Pts[2].x == Pts[3].x) &&
3150 (Pts[3].y == Pts[0].y))))
3151 {
3152 RGNOBJAPI_Unlock(region);
3153 NtGdiSetRectRgn(hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
3154 max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y));
3155 return hrgn;
3156 }
3157
3158 for (poly = total = 0; poly < nbpolygons; poly++)
3159 total += Count[poly];
3160 if (! (pETEs = ExAllocatePoolWithTag(PagedPool, sizeof(EdgeTableEntry) * total, TAG_REGION)) )
3161 {
3162 GreDeleteObject(hrgn);
3163 return 0;
3164 }
3165 pts = FirstPtBlock.pts;
3166 REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
3167 pSLL = ET.scanlines.next;
3168 curPtBlock = &FirstPtBlock;
3169
3170 if (mode != WINDING)
3171 {
3172 /*
3173 * for each scanline
3174 */
3175 for (y = ET.ymin; y < ET.ymax; y++)
3176 {
3177 /*
3178 * Add a new edge to the active edge table when we
3179 * get to the next edge.
3180 */
3181 if (pSLL != NULL && y == pSLL->scanline)
3182 {
3183 REGION_loadAET(&AET, pSLL->edgelist);
3184 pSLL = pSLL->next;
3185 }
3186 pPrevAET = &AET;
3187 pAET = AET.next;
3188
3189 /*
3190 * for each active edge
3191 */
3192 while (pAET)
3193 {
3194 pts->x = pAET->bres.minor_axis, pts->y = y;
3195 pts++, iPts++;
3196
3197 /*
3198 * send out the buffer
3199 */
3200 if (iPts == NUMPTSTOBUFFER)
3201 {
3202 tmpPtBlock = ExAllocatePoolWithTag(PagedPool, sizeof(POINTBLOCK), TAG_REGION);
3203 if (!tmpPtBlock)
3204 {
3205 DPRINT1("Can't alloc tPB\n");
3206 ExFreePoolWithTag(pETEs, TAG_REGION);
3207 return 0;
3208 }
3209 curPtBlock->next = tmpPtBlock;
3210 curPtBlock = tmpPtBlock;
3211 pts = curPtBlock->pts;
3212 numFullPtBlocks++;
3213 iPts = 0;
3214 }
3215 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
3216 }
3217 REGION_InsertionSort(&AET);
3218 }
3219 }
3220 else
3221 {
3222 /*
3223 * for each scanline
3224 */
3225 for (y = ET.ymin; y < ET.ymax; y++)
3226 {
3227 /*
3228 * Add a new edge to the active edge table when we
3229 * get to the next edge.
3230 */
3231 if (pSLL != NULL && y == pSLL->scanline)
3232 {
3233 REGION_loadAET(&AET, pSLL->edgelist);
3234 REGION_computeWAET(&AET);
3235 pSLL = pSLL->next;
3236 }
3237 pPrevAET = &AET;
3238 pAET = AET.next;
3239 pWETE = pAET;
3240
3241 /*
3242 * for each active edge
3243 */
3244 while (pAET)
3245 {
3246 /*
3247 * add to the buffer only those edges that
3248 * are in the Winding active edge table.
3249 */
3250 if (pWETE == pAET)
3251 {
3252 pts->x = pAET->bres.minor_axis, pts->y = y;
3253 pts++, iPts++;
3254
3255 /*
3256 * send out the buffer
3257 */
3258 if (iPts == NUMPTSTOBUFFER)
3259 {
3260 tmpPtBlock = ExAllocatePoolWithTag(PagedPool,
3261 sizeof(POINTBLOCK), TAG_REGION);
3262 if (!tmpPtBlock)
3263 {
3264 DPRINT1("Can't alloc tPB\n");
3265 ExFreePoolWithTag(pETEs, TAG_REGION);
3266 GreDeleteObject(hrgn);
3267 return 0;
3268 }
3269 curPtBlock->next = tmpPtBlock;
3270 curPtBlock = tmpPtBlock;
3271 pts = curPtBlock->pts;
3272 numFullPtBlocks++;
3273 iPts = 0;
3274 }
3275 pWETE = pWETE->nextWETE;
3276 }
3277 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
3278 }
3279
3280 /*
3281 * recompute the winding active edge table if
3282 * we just resorted or have exited an edge.
3283 */
3284 if (REGION_InsertionSort(&AET) || fixWAET)
3285 {
3286 REGION_computeWAET(&AET);
3287 fixWAET = FALSE;
3288 }
3289 }
3290 }
3291 REGION_FreeStorage(SLLBlock.next);
329