Return value of ExtSelectClipRgn should consider visible region.
[wine] / objects / region.c
1 /*
2  * GDI region objects. Shamelessly ripped out from the X11 distribution
3  * Thanks for the nice licence.
4  *
5  * Copyright 1993, 1994, 1995 Alexandre Julliard
6  * Modifications and additions: Copyright 1998 Huw Davies
7  *                                        1999 Alex Korobka
8  *
9  * This library is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU Lesser General Public
11  * License as published by the Free Software Foundation; either
12  * version 2.1 of the License, or (at your option) any later version.
13  *
14  * This library is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17  * Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public
20  * License along with this library; if not, write to the Free Software
21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
22  */
23
24 /************************************************************************
25
26 Copyright (c) 1987, 1988  X Consortium
27
28 Permission is hereby granted, free of charge, to any person obtaining a copy
29 of this software and associated documentation files (the "Software"), to deal
30 in the Software without restriction, including without limitation the rights
31 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
32 copies of the Software, and to permit persons to whom the Software is
33 furnished to do so, subject to the following conditions:
34
35 The above copyright notice and this permission notice shall be included in
36 all copies or substantial portions of the Software.
37
38 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
39 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
40 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
41 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
42 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
43 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
44
45 Except as contained in this notice, the name of the X Consortium shall not be
46 used in advertising or otherwise to promote the sale, use or other dealings
47 in this Software without prior written authorization from the X Consortium.
48
49
50 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
51
52                         All Rights Reserved
53
54 Permission to use, copy, modify, and distribute this software and its
55 documentation for any purpose and without fee is hereby granted,
56 provided that the above copyright notice appear in all copies and that
57 both that copyright notice and this permission notice appear in
58 supporting documentation, and that the name of Digital not be
59 used in advertising or publicity pertaining to distribution of the
60 software without specific, written prior permission.
61
62 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
63 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
64 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
65 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
66 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
67 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
68 SOFTWARE.
69
70 ************************************************************************/
71 /*
72  * The functions in this file implement the Region abstraction, similar to one
73  * used in the X11 sample server. A Region is simply an area, as the name
74  * implies, and is implemented as a "y-x-banded" array of rectangles. To
75  * explain: Each Region is made up of a certain number of rectangles sorted
76  * by y coordinate first, and then by x coordinate.
77  *
78  * Furthermore, the rectangles are banded such that every rectangle with a
79  * given upper-left y coordinate (y1) will have the same lower-right y
80  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
81  * will span the entire vertical distance of the band. This means that some
82  * areas that could be merged into a taller rectangle will be represented as
83  * several shorter rectangles to account for shorter rectangles to its left
84  * or right but within its "vertical scope".
85  *
86  * An added constraint on the rectangles is that they must cover as much
87  * horizontal area as possible. E.g. no two rectangles in a band are allowed
88  * to touch.
89  *
90  * Whenever possible, bands will be merged together to cover a greater vertical
91  * distance (and thus reduce the number of rectangles). Two bands can be merged
92  * only if the bottom of one touches the top of the other and they have
93  * rectangles in the same places (of the same width, of course). This maintains
94  * the y-x-banding that's so nice to have...
95  */
96
97 #include <stdlib.h>
98 #include <string.h>
99 #include "windef.h"
100 #include "wingdi.h"
101 #include "gdi.h"
102 #include "wine/debug.h"
103
104 WINE_DEFAULT_DEBUG_CHANNEL(region);
105
106 typedef struct {
107     INT size;
108     INT numRects;
109     RECT *rects;
110     RECT extents;
111 } WINEREGION;
112
113   /* GDI logical region object */
114 typedef struct
115 {
116     GDIOBJHDR   header;
117     WINEREGION  *rgn;
118 } RGNOBJ;
119
120
121 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, void *obj, HDC hdc );
122 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj );
123
124 static const struct gdi_obj_funcs region_funcs =
125 {
126     REGION_SelectObject,  /* pSelectObject */
127     NULL,                 /* pGetObject16 */
128     NULL,                 /* pGetObjectA */
129     NULL,                 /* pGetObjectW */
130     NULL,                 /* pUnrealizeObject */
131     REGION_DeleteObject   /* pDeleteObject */
132 };
133
134 /*  1 if two RECTs overlap.
135  *  0 if two RECTs do not overlap.
136  */
137 #define EXTENTCHECK(r1, r2) \
138         ((r1)->right > (r2)->left && \
139          (r1)->left < (r2)->right && \
140          (r1)->bottom > (r2)->top && \
141          (r1)->top < (r2)->bottom)
142
143 /*
144  *   Check to see if there is enough memory in the present region.
145  */
146
147 static inline int xmemcheck(WINEREGION *reg, LPRECT *rect, LPRECT *firstrect ) {
148     if (reg->numRects >= (reg->size - 1)) {
149         *firstrect = HeapReAlloc( GetProcessHeap(), 0, *firstrect, (2 * (sizeof(RECT)) * (reg->size)));
150         if (*firstrect == 0)
151             return 0;
152         reg->size *= 2;
153         *rect = (*firstrect)+reg->numRects;
154     }
155     return 1;
156 }
157
158 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
159
160 #define EMPTY_REGION(pReg) { \
161     (pReg)->numRects = 0; \
162     (pReg)->extents.left = (pReg)->extents.top = 0; \
163     (pReg)->extents.right = (pReg)->extents.bottom = 0; \
164  }
165
166 #define REGION_NOT_EMPTY(pReg) pReg->numRects
167
168 #define INRECT(r, x, y) \
169       ( ( ((r).right >  x)) && \
170         ( ((r).left <= x)) && \
171         ( ((r).bottom >  y)) && \
172         ( ((r).top <= y)) )
173
174
175 /*
176  * number of points to buffer before sending them off
177  * to scanlines() :  Must be an even number
178  */
179 #define NUMPTSTOBUFFER 200
180
181 /*
182  * used to allocate buffers for points and link
183  * the buffers together
184  */
185
186 typedef struct _POINTBLOCK {
187     POINT pts[NUMPTSTOBUFFER];
188     struct _POINTBLOCK *next;
189 } POINTBLOCK;
190
191
192
193 /*
194  *     This file contains a few macros to help track
195  *     the edge of a filled object.  The object is assumed
196  *     to be filled in scanline order, and thus the
197  *     algorithm used is an extension of Bresenham's line
198  *     drawing algorithm which assumes that y is always the
199  *     major axis.
200  *     Since these pieces of code are the same for any filled shape,
201  *     it is more convenient to gather the library in one
202  *     place, but since these pieces of code are also in
203  *     the inner loops of output primitives, procedure call
204  *     overhead is out of the question.
205  *     See the author for a derivation if needed.
206  */
207
208
209 /*
210  *  In scan converting polygons, we want to choose those pixels
211  *  which are inside the polygon.  Thus, we add .5 to the starting
212  *  x coordinate for both left and right edges.  Now we choose the
213  *  first pixel which is inside the pgon for the left edge and the
214  *  first pixel which is outside the pgon for the right edge.
215  *  Draw the left pixel, but not the right.
216  *
217  *  How to add .5 to the starting x coordinate:
218  *      If the edge is moving to the right, then subtract dy from the
219  *  error term from the general form of the algorithm.
220  *      If the edge is moving to the left, then add dy to the error term.
221  *
222  *  The reason for the difference between edges moving to the left
223  *  and edges moving to the right is simple:  If an edge is moving
224  *  to the right, then we want the algorithm to flip immediately.
225  *  If it is moving to the left, then we don't want it to flip until
226  *  we traverse an entire pixel.
227  */
228 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
229     int dx;      /* local storage */ \
230 \
231     /* \
232      *  if the edge is horizontal, then it is ignored \
233      *  and assumed not to be processed.  Otherwise, do this stuff. \
234      */ \
235     if ((dy) != 0) { \
236         xStart = (x1); \
237         dx = (x2) - xStart; \
238         if (dx < 0) { \
239             m = dx / (dy); \
240             m1 = m - 1; \
241             incr1 = -2 * dx + 2 * (dy) * m1; \
242             incr2 = -2 * dx + 2 * (dy) * m; \
243             d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
244         } else { \
245             m = dx / (dy); \
246             m1 = m + 1; \
247             incr1 = 2 * dx - 2 * (dy) * m1; \
248             incr2 = 2 * dx - 2 * (dy) * m; \
249             d = -2 * m * (dy) + 2 * dx; \
250         } \
251     } \
252 }
253
254 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
255     if (m1 > 0) { \
256         if (d > 0) { \
257             minval += m1; \
258             d += incr1; \
259         } \
260         else { \
261             minval += m; \
262             d += incr2; \
263         } \
264     } else {\
265         if (d >= 0) { \
266             minval += m1; \
267             d += incr1; \
268         } \
269         else { \
270             minval += m; \
271             d += incr2; \
272         } \
273     } \
274 }
275
276 /*
277  *     This structure contains all of the information needed
278  *     to run the bresenham algorithm.
279  *     The variables may be hardcoded into the declarations
280  *     instead of using this structure to make use of
281  *     register declarations.
282  */
283 typedef struct {
284     INT minor_axis;     /* minor axis        */
285     INT d;              /* decision variable */
286     INT m, m1;          /* slope and slope+1 */
287     INT incr1, incr2;   /* error increments */
288 } BRESINFO;
289
290
291 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
292         BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
293                      bres.m, bres.m1, bres.incr1, bres.incr2)
294
295 #define BRESINCRPGONSTRUCT(bres) \
296         BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
297
298
299
300 /*
301  *     These are the data structures needed to scan
302  *     convert regions.  Two different scan conversion
303  *     methods are available -- the even-odd method, and
304  *     the winding number method.
305  *     The even-odd rule states that a point is inside
306  *     the polygon if a ray drawn from that point in any
307  *     direction will pass through an odd number of
308  *     path segments.
309  *     By the winding number rule, a point is decided
310  *     to be inside the polygon if a ray drawn from that
311  *     point in any direction passes through a different
312  *     number of clockwise and counter-clockwise path
313  *     segments.
314  *
315  *     These data structures are adapted somewhat from
316  *     the algorithm in (Foley/Van Dam) for scan converting
317  *     polygons.
318  *     The basic algorithm is to start at the top (smallest y)
319  *     of the polygon, stepping down to the bottom of
320  *     the polygon by incrementing the y coordinate.  We
321  *     keep a list of edges which the current scanline crosses,
322  *     sorted by x.  This list is called the Active Edge Table (AET)
323  *     As we change the y-coordinate, we update each entry in
324  *     in the active edge table to reflect the edges new xcoord.
325  *     This list must be sorted at each scanline in case
326  *     two edges intersect.
327  *     We also keep a data structure known as the Edge Table (ET),
328  *     which keeps track of all the edges which the current
329  *     scanline has not yet reached.  The ET is basically a
330  *     list of ScanLineList structures containing a list of
331  *     edges which are entered at a given scanline.  There is one
332  *     ScanLineList per scanline at which an edge is entered.
333  *     When we enter a new edge, we move it from the ET to the AET.
334  *
335  *     From the AET, we can implement the even-odd rule as in
336  *     (Foley/Van Dam).
337  *     The winding number rule is a little trickier.  We also
338  *     keep the EdgeTableEntries in the AET linked by the
339  *     nextWETE (winding EdgeTableEntry) link.  This allows
340  *     the edges to be linked just as before for updating
341  *     purposes, but only uses the edges linked by the nextWETE
342  *     link as edges representing spans of the polygon to
343  *     drawn (as with the even-odd rule).
344  */
345
346 /*
347  * for the winding number rule
348  */
349 #define CLOCKWISE          1
350 #define COUNTERCLOCKWISE  -1
351
352 typedef struct _EdgeTableEntry {
353      INT ymax;           /* ycoord at which we exit this edge. */
354      BRESINFO bres;        /* Bresenham info to run the edge     */
355      struct _EdgeTableEntry *next;       /* next in the list     */
356      struct _EdgeTableEntry *back;       /* for insertion sort   */
357      struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
358      int ClockWise;        /* flag for winding number rule       */
359 } EdgeTableEntry;
360
361
362 typedef struct _ScanLineList{
363      INT scanline;            /* the scanline represented */
364      EdgeTableEntry *edgelist;  /* header node              */
365      struct _ScanLineList *next;  /* next in the list       */
366 } ScanLineList;
367
368
369 typedef struct {
370      INT ymax;               /* ymax for the polygon     */
371      INT ymin;               /* ymin for the polygon     */
372      ScanLineList scanlines;   /* header node              */
373 } EdgeTable;
374
375
376 /*
377  * Here is a struct to help with storage allocation
378  * so we can allocate a big chunk at a time, and then take
379  * pieces from this heap when we need to.
380  */
381 #define SLLSPERBLOCK 25
382
383 typedef struct _ScanLineListBlock {
384      ScanLineList SLLs[SLLSPERBLOCK];
385      struct _ScanLineListBlock *next;
386 } ScanLineListBlock;
387
388
389 /*
390  *
391  *     a few macros for the inner loops of the fill code where
392  *     performance considerations don't allow a procedure call.
393  *
394  *     Evaluate the given edge at the given scanline.
395  *     If the edge has expired, then we leave it and fix up
396  *     the active edge table; otherwise, we increment the
397  *     x value to be ready for the next scanline.
398  *     The winding number rule is in effect, so we must notify
399  *     the caller when the edge has been removed so he
400  *     can reorder the Winding Active Edge Table.
401  */
402 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
403    if (pAET->ymax == y) {          /* leaving this edge */ \
404       pPrevAET->next = pAET->next; \
405       pAET = pPrevAET->next; \
406       fixWAET = 1; \
407       if (pAET) \
408          pAET->back = pPrevAET; \
409    } \
410    else { \
411       BRESINCRPGONSTRUCT(pAET->bres); \
412       pPrevAET = pAET; \
413       pAET = pAET->next; \
414    } \
415 }
416
417
418 /*
419  *     Evaluate the given edge at the given scanline.
420  *     If the edge has expired, then we leave it and fix up
421  *     the active edge table; otherwise, we increment the
422  *     x value to be ready for the next scanline.
423  *     The even-odd rule is in effect.
424  */
425 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
426    if (pAET->ymax == y) {          /* leaving this edge */ \
427       pPrevAET->next = pAET->next; \
428       pAET = pPrevAET->next; \
429       if (pAET) \
430          pAET->back = pPrevAET; \
431    } \
432    else { \
433       BRESINCRPGONSTRUCT(pAET->bres); \
434       pPrevAET = pAET; \
435       pAET = pAET->next; \
436    } \
437 }
438
439 typedef void (*voidProcp)();
440
441 /* Note the parameter order is different from the X11 equivalents */
442
443 static void REGION_CopyRegion(WINEREGION *d, WINEREGION *s);
444 static void REGION_IntersectRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
445 static void REGION_UnionRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
446 static void REGION_SubtractRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
447 static void REGION_XorRegion(WINEREGION *d, WINEREGION *s1, WINEREGION *s2);
448 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn);
449
450 #define RGN_DEFAULT_RECTS       2
451
452
453 /***********************************************************************
454  *            get_region_type
455  */
456 inline static INT get_region_type( const RGNOBJ *obj )
457 {
458     switch(obj->rgn->numRects)
459     {
460     case 0:  return NULLREGION;
461     case 1:  return SIMPLEREGION;
462     default: return COMPLEXREGION;
463     }
464 }
465
466
467 /***********************************************************************
468  *            REGION_DumpRegion
469  *            Outputs the contents of a WINEREGION
470  */
471 static void REGION_DumpRegion(WINEREGION *pReg)
472 {
473     RECT *pRect, *pRectEnd = pReg->rects + pReg->numRects;
474
475     TRACE("Region %p: %ld,%ld - %ld,%ld %d rects\n", pReg,
476             pReg->extents.left, pReg->extents.top,
477             pReg->extents.right, pReg->extents.bottom, pReg->numRects);
478     for(pRect = pReg->rects; pRect < pRectEnd; pRect++)
479         TRACE("\t%ld,%ld - %ld,%ld\n", pRect->left, pRect->top,
480                        pRect->right, pRect->bottom);
481     return;
482 }
483
484
485 /***********************************************************************
486  *            REGION_AllocWineRegion
487  *            Create a new empty WINEREGION.
488  */
489 static WINEREGION *REGION_AllocWineRegion( INT n )
490 {
491     WINEREGION *pReg;
492
493     if ((pReg = HeapAlloc(GetProcessHeap(), 0, sizeof( WINEREGION ))))
494     {
495         if ((pReg->rects = HeapAlloc(GetProcessHeap(), 0, n * sizeof( RECT ))))
496         {
497             pReg->size = n;
498             EMPTY_REGION(pReg);
499             return pReg;
500         }
501         HeapFree(GetProcessHeap(), 0, pReg);
502     }
503     return NULL;
504 }
505
506
507 /***********************************************************************
508  *          REGION_CreateRegion
509  *          Create a new empty region.
510  */
511 static HRGN REGION_CreateRegion( INT n )
512 {
513     HRGN hrgn;
514     RGNOBJ *obj;
515
516     if(!(obj = GDI_AllocObject( sizeof(RGNOBJ), REGION_MAGIC, (HGDIOBJ *)&hrgn,
517                                 &region_funcs ))) return 0;
518     if(!(obj->rgn = REGION_AllocWineRegion(n))) {
519         GDI_FreeObject( hrgn, obj );
520         return 0;
521     }
522     GDI_ReleaseObj( hrgn );
523     return hrgn;
524 }
525
526 /***********************************************************************
527  *           REGION_DestroyWineRegion
528  */
529 static void REGION_DestroyWineRegion( WINEREGION* pReg )
530 {
531     HeapFree( GetProcessHeap(), 0, pReg->rects );
532     HeapFree( GetProcessHeap(), 0, pReg );
533 }
534
535 /***********************************************************************
536  *           REGION_DeleteObject
537  */
538 static BOOL REGION_DeleteObject( HGDIOBJ handle, void *obj )
539 {
540     RGNOBJ *rgn = obj;
541
542     TRACE(" %p\n", handle );
543
544     REGION_DestroyWineRegion( rgn->rgn );
545     return GDI_FreeObject( handle, obj );
546 }
547
548 /***********************************************************************
549  *           REGION_SelectObject
550  */
551 static HGDIOBJ REGION_SelectObject( HGDIOBJ handle, void *obj, HDC hdc )
552 {
553     return (HGDIOBJ)SelectClipRgn( hdc, handle );
554 }
555
556
557 /***********************************************************************
558  *           OffsetRgn   (GDI32.@)
559  */
560 INT WINAPI OffsetRgn( HRGN hrgn, INT x, INT y )
561 {
562     RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
563     INT ret;
564
565     TRACE("%p %d,%d\n", hrgn, x, y);
566
567     if (!obj)
568         return ERROR;
569
570     if(x || y) {
571         int nbox = obj->rgn->numRects;
572         RECT *pbox = obj->rgn->rects;
573
574         if(nbox) {
575             while(nbox--) {
576                 pbox->left += x;
577                 pbox->right += x;
578                 pbox->top += y;
579                 pbox->bottom += y;
580                 pbox++;
581             }
582             obj->rgn->extents.left += x;
583             obj->rgn->extents.right += x;
584             obj->rgn->extents.top += y;
585             obj->rgn->extents.bottom += y;
586         }
587     }
588     ret = get_region_type( obj );
589     GDI_ReleaseObj( hrgn );
590     return ret;
591 }
592
593
594 /***********************************************************************
595  *           GetRgnBox    (GDI32.@)
596  */
597 INT WINAPI GetRgnBox( HRGN hrgn, LPRECT rect )
598 {
599     RGNOBJ * obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
600     if (obj)
601     {
602         INT ret;
603         TRACE(" %p\n", hrgn );
604         rect->left = obj->rgn->extents.left;
605         rect->top = obj->rgn->extents.top;
606         rect->right = obj->rgn->extents.right;
607         rect->bottom = obj->rgn->extents.bottom;
608         ret = get_region_type( obj );
609         GDI_ReleaseObj(hrgn);
610         return ret;
611     }
612     return ERROR;
613 }
614
615
616 /***********************************************************************
617  *           CreateRectRgn   (GDI32.@)
618  */
619 HRGN WINAPI CreateRectRgn(INT left, INT top, INT right, INT bottom)
620 {
621     HRGN hrgn;
622
623     /* Allocate 2 rects by default to reduce the number of reallocs */
624
625     if (!(hrgn = REGION_CreateRegion(RGN_DEFAULT_RECTS)))
626         return 0;
627     TRACE("\n");
628     SetRectRgn(hrgn, left, top, right, bottom);
629     return hrgn;
630 }
631
632
633 /***********************************************************************
634  *           CreateRectRgnIndirect    (GDI32.@)
635  */
636 HRGN WINAPI CreateRectRgnIndirect( const RECT* rect )
637 {
638     return CreateRectRgn( rect->left, rect->top, rect->right, rect->bottom );
639 }
640
641
642 /***********************************************************************
643  *           SetRectRgn    (GDI32.@)
644  *
645  * Allows either or both left and top to be greater than right or bottom.
646  */
647 BOOL WINAPI SetRectRgn( HRGN hrgn, INT left, INT top,
648                           INT right, INT bottom )
649 {
650     RGNOBJ * obj;
651
652     TRACE("%p %d,%d-%d,%d\n", hrgn, left, top, right, bottom );
653
654     if (!(obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return FALSE;
655
656     if (left > right) { INT tmp = left; left = right; right = tmp; }
657     if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
658
659     if((left != right) && (top != bottom))
660     {
661         obj->rgn->rects->left = obj->rgn->extents.left = left;
662         obj->rgn->rects->top = obj->rgn->extents.top = top;
663         obj->rgn->rects->right = obj->rgn->extents.right = right;
664         obj->rgn->rects->bottom = obj->rgn->extents.bottom = bottom;
665         obj->rgn->numRects = 1;
666     }
667     else
668         EMPTY_REGION(obj->rgn);
669
670     GDI_ReleaseObj( hrgn );
671     return TRUE;
672 }
673
674
675 /***********************************************************************
676  *           CreateRoundRectRgn    (GDI32.@)
677  */
678 HRGN WINAPI CreateRoundRectRgn( INT left, INT top,
679                                     INT right, INT bottom,
680                                     INT ellipse_width, INT ellipse_height )
681 {
682     RGNOBJ * obj;
683     HRGN hrgn;
684     int asq, bsq, d, xd, yd;
685     RECT rect;
686
687       /* Make the dimensions sensible */
688
689     if (left > right) { INT tmp = left; left = right; right = tmp; }
690     if (top > bottom) { INT tmp = top; top = bottom; bottom = tmp; }
691
692     ellipse_width = abs(ellipse_width);
693     ellipse_height = abs(ellipse_height);
694
695       /* Check parameters */
696
697     if (ellipse_width > right-left) ellipse_width = right-left;
698     if (ellipse_height > bottom-top) ellipse_height = bottom-top;
699
700       /* Check if we can do a normal rectangle instead */
701
702     if ((ellipse_width < 2) || (ellipse_height < 2))
703         return CreateRectRgn( left, top, right, bottom );
704
705       /* Create region */
706
707     d = (ellipse_height < 128) ? ((3 * ellipse_height) >> 2) : 64;
708     if (!(hrgn = REGION_CreateRegion(d))) return 0;
709     if (!(obj = GDI_GetObjPtr( hrgn, REGION_MAGIC ))) return 0;
710     TRACE("(%d,%d-%d,%d %dx%d): ret=%p\n",
711           left, top, right, bottom, ellipse_width, ellipse_height, hrgn );
712
713       /* Ellipse algorithm, based on an article by K. Porter */
714       /* in DDJ Graphics Programming Column, 8/89 */
715
716     asq = ellipse_width * ellipse_width / 4;        /* a^2 */
717     bsq = ellipse_height * ellipse_height / 4;      /* b^2 */
718     d = bsq - asq * ellipse_height / 2 + asq / 4;   /* b^2 - a^2b + a^2/4 */
719     xd = 0;
720     yd = asq * ellipse_height;                      /* 2a^2b */
721
722     rect.left   = left + ellipse_width / 2;
723     rect.right  = right - ellipse_width / 2;
724
725       /* Loop to draw first half of quadrant */
726
727     while (xd < yd)
728     {
729         if (d > 0)  /* if nearest pixel is toward the center */
730         {
731               /* move toward center */
732             rect.top = top++;
733             rect.bottom = rect.top + 1;
734             REGION_UnionRectWithRegion( &rect, obj->rgn );
735             rect.top = --bottom;
736             rect.bottom = rect.top + 1;
737             REGION_UnionRectWithRegion( &rect, obj->rgn );
738             yd -= 2*asq;
739             d  -= yd;
740         }
741         rect.left--;        /* next horiz point */
742         rect.right++;
743         xd += 2*bsq;
744         d  += bsq + xd;
745     }
746
747       /* Loop to draw second half of quadrant */
748
749     d += (3 * (asq-bsq) / 2 - (xd+yd)) / 2;
750     while (yd >= 0)
751     {
752           /* next vertical point */
753         rect.top = top++;
754         rect.bottom = rect.top + 1;
755         REGION_UnionRectWithRegion( &rect, obj->rgn );
756         rect.top = --bottom;
757         rect.bottom = rect.top + 1;
758         REGION_UnionRectWithRegion( &rect, obj->rgn );
759         if (d < 0)   /* if nearest pixel is outside ellipse */
760         {
761             rect.left--;     /* move away from center */
762             rect.right++;
763             xd += 2*bsq;
764             d  += xd;
765         }
766         yd -= 2*asq;
767         d  += asq - yd;
768     }
769
770       /* Add the inside rectangle */
771
772     if (top <= bottom)
773     {
774         rect.top = top;
775         rect.bottom = bottom;
776         REGION_UnionRectWithRegion( &rect, obj->rgn );
777     }
778     GDI_ReleaseObj( hrgn );
779     return hrgn;
780 }
781
782
783 /***********************************************************************
784  *           CreateEllipticRgn    (GDI32.@)
785  */
786 HRGN WINAPI CreateEllipticRgn( INT left, INT top,
787                                    INT right, INT bottom )
788 {
789     return CreateRoundRectRgn( left, top, right, bottom,
790                                  right-left, bottom-top );
791 }
792
793
794 /***********************************************************************
795  *           CreateEllipticRgnIndirect    (GDI32.@)
796  */
797 HRGN WINAPI CreateEllipticRgnIndirect( const RECT *rect )
798 {
799     return CreateRoundRectRgn( rect->left, rect->top, rect->right,
800                                  rect->bottom, rect->right - rect->left,
801                                  rect->bottom - rect->top );
802 }
803
804 /***********************************************************************
805  *           GetRegionData   (GDI32.@)
806  *
807  * MSDN: GetRegionData, Return Values:
808  *
809  * "If the function succeeds and dwCount specifies an adequate number of bytes,
810  * the return value is always dwCount. If dwCount is too small or the function
811  * fails, the return value is 0. If lpRgnData is NULL, the return value is the
812  * required number of bytes.
813  *
814  * If the function fails, the return value is zero."
815  */
816 DWORD WINAPI GetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
817 {
818     DWORD size;
819     RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
820
821     TRACE(" %p count = %ld, rgndata = %p\n", hrgn, count, rgndata);
822
823     if(!obj) return 0;
824
825     size = obj->rgn->numRects * sizeof(RECT);
826     if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
827     {
828         GDI_ReleaseObj( hrgn );
829         if (rgndata) /* buffer is too small, signal it by return 0 */
830             return 0;
831         else            /* user requested buffer size with rgndata NULL */
832             return size + sizeof(RGNDATAHEADER);
833     }
834
835     rgndata->rdh.dwSize = sizeof(RGNDATAHEADER);
836     rgndata->rdh.iType = RDH_RECTANGLES;
837     rgndata->rdh.nCount = obj->rgn->numRects;
838     rgndata->rdh.nRgnSize = size;
839     rgndata->rdh.rcBound.left = obj->rgn->extents.left;
840     rgndata->rdh.rcBound.top = obj->rgn->extents.top;
841     rgndata->rdh.rcBound.right = obj->rgn->extents.right;
842     rgndata->rdh.rcBound.bottom = obj->rgn->extents.bottom;
843
844     memcpy( rgndata->Buffer, obj->rgn->rects, size );
845
846     GDI_ReleaseObj( hrgn );
847     return size + sizeof(RGNDATAHEADER);
848 }
849
850
851 /***********************************************************************
852  *           ExtCreateRegion   (GDI32.@)
853  *
854  */
855 HRGN WINAPI ExtCreateRegion( const XFORM* lpXform, DWORD dwCount, const RGNDATA* rgndata)
856 {
857     HRGN hrgn;
858
859     TRACE(" %p %ld %p = ", lpXform, dwCount, rgndata );
860
861     if( lpXform )
862         WARN("(Xform not implemented - ignored)\n");
863
864     if( rgndata->rdh.iType != RDH_RECTANGLES )
865     {
866         /* FIXME: We can use CreatePolyPolygonRgn() here
867          *        for trapezoidal data */
868
869         WARN("(Unsupported region data)\n");
870         goto fail;
871     }
872
873     if( (hrgn = REGION_CreateRegion( rgndata->rdh.nCount )) )
874     {
875         RECT *pCurRect, *pEndRect;
876         RGNOBJ *obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
877
878         if (obj) {
879             pEndRect = (RECT *)rgndata->Buffer + rgndata->rdh.nCount;
880             for(pCurRect = (RECT *)rgndata->Buffer; pCurRect < pEndRect; pCurRect++)
881                 REGION_UnionRectWithRegion( pCurRect, obj->rgn );
882             GDI_ReleaseObj( hrgn );
883
884             TRACE("%p\n", hrgn );
885             return hrgn;
886         }
887         else ERR("Could not get pointer to newborn Region!\n");
888     }
889 fail:
890     WARN("Failed\n");
891     return 0;
892 }
893
894
895 /***********************************************************************
896  *           PtInRegion    (GDI32.@)
897  */
898 BOOL WINAPI PtInRegion( HRGN hrgn, INT x, INT y )
899 {
900     RGNOBJ * obj;
901     BOOL ret = FALSE;
902
903     if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
904     {
905         int i;
906
907         if (obj->rgn->numRects > 0 && INRECT(obj->rgn->extents, x, y))
908             for (i = 0; i < obj->rgn->numRects; i++)
909                 if (INRECT (obj->rgn->rects[i], x, y))
910                 {
911                     ret = TRUE;
912                     break;
913                 }
914         GDI_ReleaseObj( hrgn );
915     }
916     return ret;
917 }
918
919
920 /***********************************************************************
921  *           RectInRegion    (GDI32.@)
922  *
923  * Returns TRUE if rect is at least partly inside hrgn
924  */
925 BOOL WINAPI RectInRegion( HRGN hrgn, const RECT *rect )
926 {
927     RGNOBJ * obj;
928     BOOL ret = FALSE;
929
930     if ((obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC )))
931     {
932         RECT *pCurRect, *pRectEnd;
933
934     /* this is (just) a useful optimization */
935         if ((obj->rgn->numRects > 0) && EXTENTCHECK(&obj->rgn->extents,
936                                                       rect))
937         {
938             for (pCurRect = obj->rgn->rects, pRectEnd = pCurRect +
939              obj->rgn->numRects; pCurRect < pRectEnd; pCurRect++)
940             {
941                 if (pCurRect->bottom <= rect->top)
942                     continue;             /* not far enough down yet */
943
944                 if (pCurRect->top >= rect->bottom)
945                     break;                /* too far down */
946
947                 if (pCurRect->right <= rect->left)
948                     continue;              /* not far enough over yet */
949
950                 if (pCurRect->left >= rect->right) {
951                     continue;
952                 }
953
954                 ret = TRUE;
955                 break;
956             }
957         }
958         GDI_ReleaseObj(hrgn);
959     }
960     return ret;
961 }
962
963 /***********************************************************************
964  *           EqualRgn    (GDI32.@)
965  */
966 BOOL WINAPI EqualRgn( HRGN hrgn1, HRGN hrgn2 )
967 {
968     RGNOBJ *obj1, *obj2;
969     BOOL ret = FALSE;
970
971     if ((obj1 = (RGNOBJ *) GDI_GetObjPtr( hrgn1, REGION_MAGIC )))
972     {
973         if ((obj2 = (RGNOBJ *) GDI_GetObjPtr( hrgn2, REGION_MAGIC )))
974         {
975             int i;
976
977             if ( obj1->rgn->numRects != obj2->rgn->numRects ) goto done;
978             if ( obj1->rgn->numRects == 0 )
979             {
980                 ret = TRUE;
981                 goto done;
982
983             }
984             if (obj1->rgn->extents.left   != obj2->rgn->extents.left) goto done;
985             if (obj1->rgn->extents.right  != obj2->rgn->extents.right) goto done;
986             if (obj1->rgn->extents.top    != obj2->rgn->extents.top) goto done;
987             if (obj1->rgn->extents.bottom != obj2->rgn->extents.bottom) goto done;
988             for( i = 0; i < obj1->rgn->numRects; i++ )
989             {
990                 if (obj1->rgn->rects[i].left   != obj2->rgn->rects[i].left) goto done;
991                 if (obj1->rgn->rects[i].right  != obj2->rgn->rects[i].right) goto done;
992                 if (obj1->rgn->rects[i].top    != obj2->rgn->rects[i].top) goto done;
993                 if (obj1->rgn->rects[i].bottom != obj2->rgn->rects[i].bottom) goto done;
994             }
995             ret = TRUE;
996         done:
997             GDI_ReleaseObj(hrgn2);
998         }
999         GDI_ReleaseObj(hrgn1);
1000     }
1001     return ret;
1002 }
1003
1004 /***********************************************************************
1005  *           REGION_UnionRectWithRegion
1006  *           Adds a rectangle to a WINEREGION
1007  */
1008 static void REGION_UnionRectWithRegion(const RECT *rect, WINEREGION *rgn)
1009 {
1010     WINEREGION region;
1011
1012     region.rects = &region.extents;
1013     region.numRects = 1;
1014     region.size = 1;
1015     region.extents = *rect;
1016     REGION_UnionRegion(rgn, rgn, &region);
1017 }
1018
1019
1020 /***********************************************************************
1021  *           REGION_CreateFrameRgn
1022  *
1023  * Create a region that is a frame around another region.
1024  * Expand all rectangles by +/- x and y, then subtract original region.
1025  */
1026 BOOL REGION_FrameRgn( HRGN hDest, HRGN hSrc, INT x, INT y )
1027 {
1028     BOOL bRet;
1029     RGNOBJ *srcObj = (RGNOBJ*) GDI_GetObjPtr( hSrc, REGION_MAGIC );
1030
1031     if (!srcObj) return FALSE;
1032     if (srcObj->rgn->numRects != 0)
1033     {
1034         RGNOBJ* destObj = (RGNOBJ*) GDI_GetObjPtr( hDest, REGION_MAGIC );
1035         RECT *pRect, *pEndRect;
1036         RECT tempRect;
1037
1038         EMPTY_REGION( destObj->rgn );
1039
1040         pEndRect = srcObj->rgn->rects + srcObj->rgn->numRects;
1041         for(pRect = srcObj->rgn->rects; pRect < pEndRect; pRect++)
1042         {
1043             tempRect.left = pRect->left - x;
1044             tempRect.top = pRect->top - y;
1045             tempRect.right = pRect->right + x;
1046             tempRect.bottom = pRect->bottom + y;
1047             REGION_UnionRectWithRegion( &tempRect, destObj->rgn );
1048         }
1049         REGION_SubtractRegion( destObj->rgn, destObj->rgn, srcObj->rgn );
1050         GDI_ReleaseObj ( hDest );
1051         bRet = TRUE;
1052     }
1053     else
1054         bRet = FALSE;
1055     GDI_ReleaseObj( hSrc );
1056     return bRet;
1057 }
1058
1059
1060 /***********************************************************************
1061  *           CombineRgn   (GDI32.@)
1062  *
1063  * Note: The behavior is correct even if src and dest regions are the same.
1064  */
1065 INT WINAPI CombineRgn(HRGN hDest, HRGN hSrc1, HRGN hSrc2, INT mode)
1066 {
1067     RGNOBJ *destObj = (RGNOBJ *) GDI_GetObjPtr( hDest, REGION_MAGIC);
1068     INT result = ERROR;
1069
1070     TRACE(" %p,%p -> %p mode=%x\n", hSrc1, hSrc2, hDest, mode );
1071     if (destObj)
1072     {
1073         RGNOBJ *src1Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc1, REGION_MAGIC);
1074
1075         if (src1Obj)
1076         {
1077             TRACE("dump src1Obj:\n");
1078             if(TRACE_ON(region))
1079               REGION_DumpRegion(src1Obj->rgn);
1080             if (mode == RGN_COPY)
1081             {
1082                 REGION_CopyRegion( destObj->rgn, src1Obj->rgn );
1083                 result = get_region_type( destObj );
1084             }
1085             else
1086             {
1087                 RGNOBJ *src2Obj = (RGNOBJ *) GDI_GetObjPtr( hSrc2, REGION_MAGIC);
1088
1089                 if (src2Obj)
1090                 {
1091                     TRACE("dump src2Obj:\n");
1092                     if(TRACE_ON(region))
1093                         REGION_DumpRegion(src2Obj->rgn);
1094                     switch (mode)
1095                     {
1096                     case RGN_AND:
1097                         REGION_IntersectRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn);
1098                         break;
1099                     case RGN_OR:
1100                         REGION_UnionRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1101                         break;
1102                     case RGN_XOR:
1103                         REGION_XorRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1104                         break;
1105                     case RGN_DIFF:
1106                         REGION_SubtractRegion( destObj->rgn, src1Obj->rgn, src2Obj->rgn );
1107                         break;
1108                     }
1109                     result = get_region_type( destObj );
1110                     GDI_ReleaseObj( hSrc2 );
1111                 }
1112             }
1113             GDI_ReleaseObj( hSrc1 );
1114         }
1115         TRACE("dump destObj:\n");
1116         if(TRACE_ON(region))
1117           REGION_DumpRegion(destObj->rgn);
1118
1119         GDI_ReleaseObj( hDest );
1120     } else {
1121        ERR("Invalid rgn=%p\n", hDest);
1122     }
1123     return result;
1124 }
1125
1126 /***********************************************************************
1127  *           REGION_SetExtents
1128  *           Re-calculate the extents of a region
1129  */
1130 static void REGION_SetExtents (WINEREGION *pReg)
1131 {
1132     RECT *pRect, *pRectEnd, *pExtents;
1133
1134     if (pReg->numRects == 0)
1135     {
1136         pReg->extents.left = 0;
1137         pReg->extents.top = 0;
1138         pReg->extents.right = 0;
1139         pReg->extents.bottom = 0;
1140         return;
1141     }
1142
1143     pExtents = &pReg->extents;
1144     pRect = pReg->rects;
1145     pRectEnd = &pRect[pReg->numRects - 1];
1146
1147     /*
1148      * Since pRect is the first rectangle in the region, it must have the
1149      * smallest top and since pRectEnd is the last rectangle in the region,
1150      * it must have the largest bottom, because of banding. Initialize left and
1151      * right from pRect and pRectEnd, resp., as good things to initialize them
1152      * to...
1153      */
1154     pExtents->left = pRect->left;
1155     pExtents->top = pRect->top;
1156     pExtents->right = pRectEnd->right;
1157     pExtents->bottom = pRectEnd->bottom;
1158
1159     while (pRect <= pRectEnd)
1160     {
1161         if (pRect->left < pExtents->left)
1162             pExtents->left = pRect->left;
1163         if (pRect->right > pExtents->right)
1164             pExtents->right = pRect->right;
1165         pRect++;
1166     }
1167 }
1168
1169 /***********************************************************************
1170  *           REGION_CopyRegion
1171  */
1172 static void REGION_CopyRegion(WINEREGION *dst, WINEREGION *src)
1173 {
1174     if (dst != src) /*  don't want to copy to itself */
1175     {
1176         if (dst->size < src->numRects)
1177         {
1178             if (! (dst->rects = HeapReAlloc( GetProcessHeap(), 0, dst->rects,
1179                                 src->numRects * sizeof(RECT) )))
1180                 return;
1181             dst->size = src->numRects;
1182         }
1183         dst->numRects = src->numRects;
1184         dst->extents.left = src->extents.left;
1185         dst->extents.top = src->extents.top;
1186         dst->extents.right = src->extents.right;
1187         dst->extents.bottom = src->extents.bottom;
1188         memcpy((char *) dst->rects, (char *) src->rects,
1189                (int) (src->numRects * sizeof(RECT)));
1190     }
1191     return;
1192 }
1193
1194 /***********************************************************************
1195  *           REGION_Coalesce
1196  *
1197  *      Attempt to merge the rects in the current band with those in the
1198  *      previous one. Used only by REGION_RegionOp.
1199  *
1200  * Results:
1201  *      The new index for the previous band.
1202  *
1203  * Side Effects:
1204  *      If coalescing takes place:
1205  *          - rectangles in the previous band will have their bottom fields
1206  *            altered.
1207  *          - pReg->numRects will be decreased.
1208  *
1209  */
1210 static INT REGION_Coalesce (
1211              WINEREGION *pReg, /* Region to coalesce */
1212              INT prevStart,  /* Index of start of previous band */
1213              INT curStart    /* Index of start of current band */
1214 ) {
1215     RECT *pPrevRect;          /* Current rect in previous band */
1216     RECT *pCurRect;           /* Current rect in current band */
1217     RECT *pRegEnd;            /* End of region */
1218     INT curNumRects;          /* Number of rectangles in current band */
1219     INT prevNumRects;         /* Number of rectangles in previous band */
1220     INT bandtop;               /* top coordinate for current band */
1221
1222     pRegEnd = &pReg->rects[pReg->numRects];
1223
1224     pPrevRect = &pReg->rects[prevStart];
1225     prevNumRects = curStart - prevStart;
1226
1227     /*
1228      * Figure out how many rectangles are in the current band. Have to do
1229      * this because multiple bands could have been added in REGION_RegionOp
1230      * at the end when one region has been exhausted.
1231      */
1232     pCurRect = &pReg->rects[curStart];
1233     bandtop = pCurRect->top;
1234     for (curNumRects = 0;
1235          (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
1236          curNumRects++)
1237     {
1238         pCurRect++;
1239     }
1240
1241     if (pCurRect != pRegEnd)
1242     {
1243         /*
1244          * If more than one band was added, we have to find the start
1245          * of the last band added so the next coalescing job can start
1246          * at the right place... (given when multiple bands are added,
1247          * this may be pointless -- see above).
1248          */
1249         pRegEnd--;
1250         while (pRegEnd[-1].top == pRegEnd->top)
1251         {
1252             pRegEnd--;
1253         }
1254         curStart = pRegEnd - pReg->rects;
1255         pRegEnd = pReg->rects + pReg->numRects;
1256     }
1257
1258     if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
1259         pCurRect -= curNumRects;
1260         /*
1261          * The bands may only be coalesced if the bottom of the previous
1262          * matches the top scanline of the current.
1263          */
1264         if (pPrevRect->bottom == pCurRect->top)
1265         {
1266             /*
1267              * Make sure the bands have rects in the same places. This
1268              * assumes that rects have been added in such a way that they
1269              * cover the most area possible. I.e. two rects in a band must
1270              * have some horizontal space between them.
1271              */
1272             do
1273             {
1274                 if ((pPrevRect->left != pCurRect->left) ||
1275                     (pPrevRect->right != pCurRect->right))
1276                 {
1277                     /*
1278                      * The bands don't line up so they can't be coalesced.
1279                      */
1280                     return (curStart);
1281                 }
1282                 pPrevRect++;
1283                 pCurRect++;
1284                 prevNumRects -= 1;
1285             } while (prevNumRects != 0);
1286
1287             pReg->numRects -= curNumRects;
1288             pCurRect -= curNumRects;
1289             pPrevRect -= curNumRects;
1290
1291             /*
1292              * The bands may be merged, so set the bottom of each rect
1293              * in the previous band to that of the corresponding rect in
1294              * the current band.
1295              */
1296             do
1297             {
1298                 pPrevRect->bottom = pCurRect->bottom;
1299                 pPrevRect++;
1300                 pCurRect++;
1301                 curNumRects -= 1;
1302             } while (curNumRects != 0);
1303
1304             /*
1305              * If only one band was added to the region, we have to backup
1306              * curStart to the start of the previous band.
1307              *
1308              * If more than one band was added to the region, copy the
1309              * other bands down. The assumption here is that the other bands
1310              * came from the same region as the current one and no further
1311              * coalescing can be done on them since it's all been done
1312              * already... curStart is already in the right place.
1313              */
1314             if (pCurRect == pRegEnd)
1315             {
1316                 curStart = prevStart;
1317             }
1318             else
1319             {
1320                 do
1321                 {
1322                     *pPrevRect++ = *pCurRect++;
1323                 } while (pCurRect != pRegEnd);
1324             }
1325
1326         }
1327     }
1328     return (curStart);
1329 }
1330
1331 /***********************************************************************
1332  *           REGION_RegionOp
1333  *
1334  *      Apply an operation to two regions. Called by REGION_Union,
1335  *      REGION_Inverse, REGION_Subtract, REGION_Intersect...
1336  *
1337  * Results:
1338  *      None.
1339  *
1340  * Side Effects:
1341  *      The new region is overwritten.
1342  *
1343  * Notes:
1344  *      The idea behind this function is to view the two regions as sets.
1345  *      Together they cover a rectangle of area that this function divides
1346  *      into horizontal bands where points are covered only by one region
1347  *      or by both. For the first case, the nonOverlapFunc is called with
1348  *      each the band and the band's upper and lower extents. For the
1349  *      second, the overlapFunc is called to process the entire band. It
1350  *      is responsible for clipping the rectangles in the band, though
1351  *      this function provides the boundaries.
1352  *      At the end of each band, the new region is coalesced, if possible,
1353  *      to reduce the number of rectangles in the region.
1354  *
1355  */
1356 static void REGION_RegionOp(
1357             WINEREGION *newReg, /* Place to store result */
1358             WINEREGION *reg1,   /* First region in operation */
1359             WINEREGION *reg2,   /* 2nd region in operation */
1360             void (*overlapFunc)(),     /* Function to call for over-lapping bands */
1361             void (*nonOverlap1Func)(), /* Function to call for non-overlapping bands in region 1 */
1362             void (*nonOverlap2Func)()  /* Function to call for non-overlapping bands in region 2 */
1363 ) {
1364     RECT *r1;                         /* Pointer into first region */
1365     RECT *r2;                         /* Pointer into 2d region */
1366     RECT *r1End;                      /* End of 1st region */
1367     RECT *r2End;                      /* End of 2d region */
1368     INT ybot;                         /* Bottom of intersection */
1369     INT ytop;                         /* Top of intersection */
1370     RECT *oldRects;                   /* Old rects for newReg */
1371     INT prevBand;                     /* Index of start of
1372                                                  * previous band in newReg */
1373     INT curBand;                      /* Index of start of current
1374                                                  * band in newReg */
1375     RECT *r1BandEnd;                  /* End of current band in r1 */
1376     RECT *r2BandEnd;                  /* End of current band in r2 */
1377     INT top;                          /* Top of non-overlapping band */
1378     INT bot;                          /* Bottom of non-overlapping band */
1379
1380     /*
1381      * Initialization:
1382      *  set r1, r2, r1End and r2End appropriately, preserve the important
1383      * parts of the destination region until the end in case it's one of
1384      * the two source regions, then mark the "new" region empty, allocating
1385      * another array of rectangles for it to use.
1386      */
1387     r1 = reg1->rects;
1388     r2 = reg2->rects;
1389     r1End = r1 + reg1->numRects;
1390     r2End = r2 + reg2->numRects;
1391
1392
1393     /*
1394      * newReg may be one of the src regions so we can't empty it. We keep a
1395      * note of its rects pointer (so that we can free them later), preserve its
1396      * extents and simply set numRects to zero.
1397      */
1398
1399     oldRects = newReg->rects;
1400     newReg->numRects = 0;
1401
1402     /*
1403      * Allocate a reasonable number of rectangles for the new region. The idea
1404      * is to allocate enough so the individual functions don't need to
1405      * reallocate and copy the array, which is time consuming, yet we don't
1406      * have to worry about using too much memory. I hope to be able to
1407      * nuke the Xrealloc() at the end of this function eventually.
1408      */
1409     newReg->size = max(reg1->numRects,reg2->numRects) * 2;
1410
1411     if (! (newReg->rects = HeapAlloc( GetProcessHeap(), 0,
1412                                   sizeof(RECT) * newReg->size )))
1413     {
1414         newReg->size = 0;
1415         return;
1416     }
1417
1418     /*
1419      * Initialize ybot and ytop.
1420      * In the upcoming loop, ybot and ytop serve different functions depending
1421      * on whether the band being handled is an overlapping or non-overlapping
1422      * band.
1423      *  In the case of a non-overlapping band (only one of the regions
1424      * has points in the band), ybot is the bottom of the most recent
1425      * intersection and thus clips the top of the rectangles in that band.
1426      * ytop is the top of the next intersection between the two regions and
1427      * serves to clip the bottom of the rectangles in the current band.
1428      *  For an overlapping band (where the two regions intersect), ytop clips
1429      * the top of the rectangles of both regions and ybot clips the bottoms.
1430      */
1431     if (reg1->extents.top < reg2->extents.top)
1432         ybot = reg1->extents.top;
1433     else
1434         ybot = reg2->extents.top;
1435
1436     /*
1437      * prevBand serves to mark the start of the previous band so rectangles
1438      * can be coalesced into larger rectangles. qv. miCoalesce, above.
1439      * In the beginning, there is no previous band, so prevBand == curBand
1440      * (curBand is set later on, of course, but the first band will always
1441      * start at index 0). prevBand and curBand must be indices because of
1442      * the possible expansion, and resultant moving, of the new region's
1443      * array of rectangles.
1444      */
1445     prevBand = 0;
1446
1447     do
1448     {
1449         curBand = newReg->numRects;
1450
1451         /*
1452          * This algorithm proceeds one source-band (as opposed to a
1453          * destination band, which is determined by where the two regions
1454          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1455          * rectangle after the last one in the current band for their
1456          * respective regions.
1457          */
1458         r1BandEnd = r1;
1459         while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
1460         {
1461             r1BandEnd++;
1462         }
1463
1464         r2BandEnd = r2;
1465         while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
1466         {
1467             r2BandEnd++;
1468         }
1469
1470         /*
1471          * First handle the band that doesn't intersect, if any.
1472          *
1473          * Note that attention is restricted to one band in the
1474          * non-intersecting region at once, so if a region has n
1475          * bands between the current position and the next place it overlaps
1476          * the other, this entire loop will be passed through n times.
1477          */
1478         if (r1->top < r2->top)
1479         {
1480             top = max(r1->top,ybot);
1481             bot = min(r1->bottom,r2->top);
1482
1483             if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
1484             {
1485                 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1486             }
1487
1488             ytop = r2->top;
1489         }
1490         else if (r2->top < r1->top)
1491         {
1492             top = max(r2->top,ybot);
1493             bot = min(r2->bottom,r1->top);
1494
1495             if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
1496             {
1497                 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1498             }
1499
1500             ytop = r1->top;
1501         }
1502         else
1503         {
1504             ytop = r1->top;
1505         }
1506
1507         /*
1508          * If any rectangles got added to the region, try and coalesce them
1509          * with rectangles from the previous band. Note we could just do
1510          * this test in miCoalesce, but some machines incur a not
1511          * inconsiderable cost for function calls, so...
1512          */
1513         if (newReg->numRects != curBand)
1514         {
1515             prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1516         }
1517
1518         /*
1519          * Now see if we've hit an intersecting band. The two bands only
1520          * intersect if ybot > ytop
1521          */
1522         ybot = min(r1->bottom, r2->bottom);
1523         curBand = newReg->numRects;
1524         if (ybot > ytop)
1525         {
1526             (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1527
1528         }
1529
1530         if (newReg->numRects != curBand)
1531         {
1532             prevBand = REGION_Coalesce (newReg, prevBand, curBand);
1533         }
1534
1535         /*
1536          * If we've finished with a band (bottom == ybot) we skip forward
1537          * in the region to the next band.
1538          */
1539         if (r1->bottom == ybot)
1540         {
1541             r1 = r1BandEnd;
1542         }
1543         if (r2->bottom == ybot)
1544         {
1545             r2 = r2BandEnd;
1546         }
1547     } while ((r1 != r1End) && (r2 != r2End));
1548
1549     /*
1550      * Deal with whichever region still has rectangles left.
1551      */
1552     curBand = newReg->numRects;
1553     if (r1 != r1End)
1554     {
1555         if (nonOverlap1Func != (void (*)())NULL)
1556         {
1557             do
1558             {
1559                 r1BandEnd = r1;
1560                 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
1561                 {
1562                     r1BandEnd++;
1563                 }
1564                 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1565                                      max(r1->top,ybot), r1->bottom);
1566                 r1 = r1BandEnd;
1567             } while (r1 != r1End);
1568         }
1569     }
1570     else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
1571     {
1572         do
1573         {
1574             r2BandEnd = r2;
1575             while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
1576             {
1577                  r2BandEnd++;
1578             }
1579             (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1580                                 max(r2->top,ybot), r2->bottom);
1581             r2 = r2BandEnd;
1582         } while (r2 != r2End);
1583     }
1584
1585     if (newReg->numRects != curBand)
1586     {
1587         (void) REGION_Coalesce (newReg, prevBand, curBand);
1588     }
1589
1590     /*
1591      * A bit of cleanup. To keep regions from growing without bound,
1592      * we shrink the array of rectangles to match the new number of
1593      * rectangles in the region. This never goes to 0, however...
1594      *
1595      * Only do this stuff if the number of rectangles allocated is more than
1596      * twice the number of rectangles in the region (a simple optimization...).
1597      */
1598     if ((newReg->numRects < (newReg->size >> 1)) && (newReg->numRects > 2))
1599     {
1600         if (REGION_NOT_EMPTY(newReg))
1601         {
1602             RECT *prev_rects = newReg->rects;
1603             newReg->size = newReg->numRects;
1604             newReg->rects = HeapReAlloc( GetProcessHeap(), 0, newReg->rects,
1605                                    sizeof(RECT) * newReg->size );
1606             if (! newReg->rects)
1607                 newReg->rects = prev_rects;
1608         }
1609         else
1610         {
1611             /*
1612              * No point in doing the extra work involved in an Xrealloc if
1613              * the region is empty
1614              */
1615             newReg->size = 1;
1616             HeapFree( GetProcessHeap(), 0, newReg->rects );
1617             newReg->rects = HeapAlloc( GetProcessHeap(), 0, sizeof(RECT) );
1618         }
1619     }
1620     HeapFree( GetProcessHeap(), 0, oldRects );
1621     return;
1622 }
1623
1624 /***********************************************************************
1625  *          Region Intersection
1626  ***********************************************************************/
1627
1628
1629 /***********************************************************************
1630  *           REGION_IntersectO
1631  *
1632  * Handle an overlapping band for REGION_Intersect.
1633  *
1634  * Results:
1635  *      None.
1636  *
1637  * Side Effects:
1638  *      Rectangles may be added to the region.
1639  *
1640  */
1641 static void REGION_IntersectO(WINEREGION *pReg,  RECT *r1, RECT *r1End,
1642                 RECT *r2, RECT *r2End, INT top, INT bottom)
1643
1644 {
1645     INT       left, right;
1646     RECT      *pNextRect;
1647
1648     pNextRect = &pReg->rects[pReg->numRects];
1649
1650     while ((r1 != r1End) && (r2 != r2End))
1651     {
1652         left = max(r1->left, r2->left);
1653         right = min(r1->right, r2->right);
1654
1655         /*
1656          * If there's any overlap between the two rectangles, add that
1657          * overlap to the new region.
1658          * There's no need to check for subsumption because the only way
1659          * such a need could arise is if some region has two rectangles
1660          * right next to each other. Since that should never happen...
1661          */
1662         if (left < right)
1663         {
1664             MEMCHECK(pReg, pNextRect, pReg->rects);
1665             pNextRect->left = left;
1666             pNextRect->top = top;
1667             pNextRect->right = right;
1668             pNextRect->bottom = bottom;
1669             pReg->numRects += 1;
1670             pNextRect++;
1671         }
1672
1673         /*
1674          * Need to advance the pointers. Shift the one that extends
1675          * to the right the least, since the other still has a chance to
1676          * overlap with that region's next rectangle, if you see what I mean.
1677          */
1678         if (r1->right < r2->right)
1679         {
1680             r1++;
1681         }
1682         else if (r2->right < r1->right)
1683         {
1684             r2++;
1685         }
1686         else
1687         {
1688             r1++;
1689             r2++;
1690         }
1691     }
1692     return;
1693 }
1694
1695 /***********************************************************************
1696  *           REGION_IntersectRegion
1697  */
1698 static void REGION_IntersectRegion(WINEREGION *newReg, WINEREGION *reg1,
1699                                    WINEREGION *reg2)
1700 {
1701    /* check for trivial reject */
1702     if ( (!(reg1->numRects)) || (!(reg2->numRects))  ||
1703         (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
1704         newReg->numRects = 0;
1705     else
1706         REGION_RegionOp (newReg, reg1, reg2,
1707          (voidProcp) REGION_IntersectO, (voidProcp) NULL, (voidProcp) NULL);
1708
1709     /*
1710      * Can't alter newReg's extents before we call miRegionOp because
1711      * it might be one of the source regions and miRegionOp depends
1712      * on the extents of those regions being the same. Besides, this
1713      * way there's no checking against rectangles that will be nuked
1714      * due to coalescing, so we have to examine fewer rectangles.
1715      */
1716     REGION_SetExtents(newReg);
1717 }
1718
1719 /***********************************************************************
1720  *           Region Union
1721  ***********************************************************************/
1722
1723 /***********************************************************************
1724  *           REGION_UnionNonO
1725  *
1726  *      Handle a non-overlapping band for the union operation. Just
1727  *      Adds the rectangles into the region. Doesn't have to check for
1728  *      subsumption or anything.
1729  *
1730  * Results:
1731  *      None.
1732  *
1733  * Side Effects:
1734  *      pReg->numRects is incremented and the final rectangles overwritten
1735  *      with the rectangles we're passed.
1736  *
1737  */
1738 static void REGION_UnionNonO (WINEREGION *pReg, RECT *r, RECT *rEnd,
1739                               INT top, INT bottom)
1740 {
1741     RECT *pNextRect;
1742
1743     pNextRect = &pReg->rects[pReg->numRects];
1744
1745     while (r != rEnd)
1746     {
1747         MEMCHECK(pReg, pNextRect, pReg->rects);
1748         pNextRect->left = r->left;
1749         pNextRect->top = top;
1750         pNextRect->right = r->right;
1751         pNextRect->bottom = bottom;
1752         pReg->numRects += 1;
1753         pNextRect++;
1754         r++;
1755     }
1756     return;
1757 }
1758
1759 /***********************************************************************
1760  *           REGION_UnionO
1761  *
1762  *      Handle an overlapping band for the union operation. Picks the
1763  *      left-most rectangle each time and merges it into the region.
1764  *
1765  * Results:
1766  *      None.
1767  *
1768  * Side Effects:
1769  *      Rectangles are overwritten in pReg->rects and pReg->numRects will
1770  *      be changed.
1771  *
1772  */
1773 static void REGION_UnionO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1774                            RECT *r2, RECT *r2End, INT top, INT bottom)
1775 {
1776     RECT *pNextRect;
1777
1778     pNextRect = &pReg->rects[pReg->numRects];
1779
1780 #define MERGERECT(r) \
1781     if ((pReg->numRects != 0) &&  \
1782         (pNextRect[-1].top == top) &&  \
1783         (pNextRect[-1].bottom == bottom) &&  \
1784         (pNextRect[-1].right >= r->left))  \
1785     {  \
1786         if (pNextRect[-1].right < r->right)  \
1787         {  \
1788             pNextRect[-1].right = r->right;  \
1789         }  \
1790     }  \
1791     else  \
1792     {  \
1793         MEMCHECK(pReg, pNextRect, pReg->rects);  \
1794         pNextRect->top = top;  \
1795         pNextRect->bottom = bottom;  \
1796         pNextRect->left = r->left;  \
1797         pNextRect->right = r->right;  \
1798         pReg->numRects += 1;  \
1799         pNextRect += 1;  \
1800     }  \
1801     r++;
1802
1803     while ((r1 != r1End) && (r2 != r2End))
1804     {
1805         if (r1->left < r2->left)
1806         {
1807             MERGERECT(r1);
1808         }
1809         else
1810         {
1811             MERGERECT(r2);
1812         }
1813     }
1814
1815     if (r1 != r1End)
1816     {
1817         do
1818         {
1819             MERGERECT(r1);
1820         } while (r1 != r1End);
1821     }
1822     else while (r2 != r2End)
1823     {
1824         MERGERECT(r2);
1825     }
1826     return;
1827 }
1828
1829 /***********************************************************************
1830  *           REGION_UnionRegion
1831  */
1832 static void REGION_UnionRegion(WINEREGION *newReg, WINEREGION *reg1,
1833                                WINEREGION *reg2)
1834 {
1835     /*  checks all the simple cases */
1836
1837     /*
1838      * Region 1 and 2 are the same or region 1 is empty
1839      */
1840     if ( (reg1 == reg2) || (!(reg1->numRects)) )
1841     {
1842         if (newReg != reg2)
1843             REGION_CopyRegion(newReg, reg2);
1844         return;
1845     }
1846
1847     /*
1848      * if nothing to union (region 2 empty)
1849      */
1850     if (!(reg2->numRects))
1851     {
1852         if (newReg != reg1)
1853             REGION_CopyRegion(newReg, reg1);
1854         return;
1855     }
1856
1857     /*
1858      * Region 1 completely subsumes region 2
1859      */
1860     if ((reg1->numRects == 1) &&
1861         (reg1->extents.left <= reg2->extents.left) &&
1862         (reg1->extents.top <= reg2->extents.top) &&
1863         (reg1->extents.right >= reg2->extents.right) &&
1864         (reg1->extents.bottom >= reg2->extents.bottom))
1865     {
1866         if (newReg != reg1)
1867             REGION_CopyRegion(newReg, reg1);
1868         return;
1869     }
1870
1871     /*
1872      * Region 2 completely subsumes region 1
1873      */
1874     if ((reg2->numRects == 1) &&
1875         (reg2->extents.left <= reg1->extents.left) &&
1876         (reg2->extents.top <= reg1->extents.top) &&
1877         (reg2->extents.right >= reg1->extents.right) &&
1878         (reg2->extents.bottom >= reg1->extents.bottom))
1879     {
1880         if (newReg != reg2)
1881             REGION_CopyRegion(newReg, reg2);
1882         return;
1883     }
1884
1885     REGION_RegionOp (newReg, reg1, reg2, (voidProcp) REGION_UnionO,
1886                 (voidProcp) REGION_UnionNonO, (voidProcp) REGION_UnionNonO);
1887
1888     newReg->extents.left = min(reg1->extents.left, reg2->extents.left);
1889     newReg->extents.top = min(reg1->extents.top, reg2->extents.top);
1890     newReg->extents.right = max(reg1->extents.right, reg2->extents.right);
1891     newReg->extents.bottom = max(reg1->extents.bottom, reg2->extents.bottom);
1892 }
1893
1894 /***********************************************************************
1895  *           Region Subtraction
1896  ***********************************************************************/
1897
1898 /***********************************************************************
1899  *           REGION_SubtractNonO1
1900  *
1901  *      Deal with non-overlapping band for subtraction. Any parts from
1902  *      region 2 we discard. Anything from region 1 we add to the region.
1903  *
1904  * Results:
1905  *      None.
1906  *
1907  * Side Effects:
1908  *      pReg may be affected.
1909  *
1910  */
1911 static void REGION_SubtractNonO1 (WINEREGION *pReg, RECT *r, RECT *rEnd,
1912                 INT top, INT bottom)
1913 {
1914     RECT *pNextRect;
1915
1916     pNextRect = &pReg->rects[pReg->numRects];
1917
1918     while (r != rEnd)
1919     {
1920         MEMCHECK(pReg, pNextRect, pReg->rects);
1921         pNextRect->left = r->left;
1922         pNextRect->top = top;
1923         pNextRect->right = r->right;
1924         pNextRect->bottom = bottom;
1925         pReg->numRects += 1;
1926         pNextRect++;
1927         r++;
1928     }
1929     return;
1930 }
1931
1932
1933 /***********************************************************************
1934  *           REGION_SubtractO
1935  *
1936  *      Overlapping band subtraction. x1 is the left-most point not yet
1937  *      checked.
1938  *
1939  * Results:
1940  *      None.
1941  *
1942  * Side Effects:
1943  *      pReg may have rectangles added to it.
1944  *
1945  */
1946 static void REGION_SubtractO (WINEREGION *pReg, RECT *r1, RECT *r1End,
1947                 RECT *r2, RECT *r2End, INT top, INT bottom)
1948 {
1949     RECT *pNextRect;
1950     INT left;
1951
1952     left = r1->left;
1953     pNextRect = &pReg->rects[pReg->numRects];
1954
1955     while ((r1 != r1End) && (r2 != r2End))
1956     {
1957         if (r2->right <= left)
1958         {
1959             /*
1960              * Subtrahend missed the boat: go to next subtrahend.
1961              */
1962             r2++;
1963         }
1964         else if (r2->left <= left)
1965         {
1966             /*
1967              * Subtrahend preceeds minuend: nuke left edge of minuend.
1968              */
1969             left = r2->right;
1970             if (left >= r1->right)
1971             {
1972                 /*
1973                  * Minuend completely covered: advance to next minuend and
1974                  * reset left fence to edge of new minuend.
1975                  */
1976                 r1++;
1977                 if (r1 != r1End)
1978                     left = r1->left;
1979             }
1980             else
1981             {
1982                 /*
1983                  * Subtrahend now used up since it doesn't extend beyond
1984                  * minuend
1985                  */
1986                 r2++;
1987             }
1988         }
1989         else if (r2->left < r1->right)
1990         {
1991             /*
1992              * Left part of subtrahend covers part of minuend: add uncovered
1993              * part of minuend to region and skip to next subtrahend.
1994              */
1995             MEMCHECK(pReg, pNextRect, pReg->rects);
1996             pNextRect->left = left;
1997             pNextRect->top = top;
1998             pNextRect->right = r2->left;
1999             pNextRect->bottom = bottom;
2000             pReg->numRects += 1;
2001             pNextRect++;
2002             left = r2->right;
2003             if (left >= r1->right)
2004             {
2005                 /*
2006                  * Minuend used up: advance to new...
2007                  */
2008                 r1++;
2009                 if (r1 != r1End)
2010                     left = r1->left;
2011             }
2012             else
2013             {
2014                 /*
2015                  * Subtrahend used up
2016                  */
2017                 r2++;
2018             }
2019         }
2020         else
2021         {
2022             /*
2023              * Minuend used up: add any remaining piece before advancing.
2024              */
2025             if (r1->right > left)
2026             {
2027                 MEMCHECK(pReg, pNextRect, pReg->rects);
2028                 pNextRect->left = left;
2029                 pNextRect->top = top;
2030                 pNextRect->right = r1->right;
2031                 pNextRect->bottom = bottom;
2032                 pReg->numRects += 1;
2033                 pNextRect++;
2034             }
2035             r1++;
2036             left = r1->left;
2037         }
2038     }
2039
2040     /*
2041      * Add remaining minuend rectangles to region.
2042      */
2043     while (r1 != r1End)
2044     {
2045         MEMCHECK(pReg, pNextRect, pReg->rects);
2046         pNextRect->left = left;
2047         pNextRect->top = top;
2048         pNextRect->right = r1->right;
2049         pNextRect->bottom = bottom;
2050         pReg->numRects += 1;
2051         pNextRect++;
2052         r1++;
2053         if (r1 != r1End)
2054         {
2055             left = r1->left;
2056         }
2057     }
2058     return;
2059 }
2060
2061 /***********************************************************************
2062  *           REGION_SubtractRegion
2063  *
2064  *      Subtract regS from regM and leave the result in regD.
2065  *      S stands for subtrahend, M for minuend and D for difference.
2066  *
2067  * Results:
2068  *      TRUE.
2069  *
2070  * Side Effects:
2071  *      regD is overwritten.
2072  *
2073  */
2074 static void REGION_SubtractRegion(WINEREGION *regD, WINEREGION *regM,
2075                                                        WINEREGION *regS )
2076 {
2077    /* check for trivial reject */
2078     if ( (!(regM->numRects)) || (!(regS->numRects))  ||
2079         (!EXTENTCHECK(&regM->extents, &regS->extents)) )
2080     {
2081         REGION_CopyRegion(regD, regM);
2082         return;
2083     }
2084
2085     REGION_RegionOp (regD, regM, regS, (voidProcp) REGION_SubtractO,
2086                 (voidProcp) REGION_SubtractNonO1, (voidProcp) NULL);
2087
2088     /*
2089      * Can't alter newReg's extents before we call miRegionOp because
2090      * it might be one of the source regions and miRegionOp depends
2091      * on the extents of those regions being the unaltered. Besides, this
2092      * way there's no checking against rectangles that will be nuked
2093      * due to coalescing, so we have to examine fewer rectangles.
2094      */
2095     REGION_SetExtents (regD);
2096 }
2097
2098 /***********************************************************************
2099  *           REGION_XorRegion
2100  */
2101 static void REGION_XorRegion(WINEREGION *dr, WINEREGION *sra,
2102                                                         WINEREGION *srb)
2103 {
2104     WINEREGION *tra, *trb;
2105
2106     if ((! (tra = REGION_AllocWineRegion(sra->numRects + 1))) ||
2107         (! (trb = REGION_AllocWineRegion(srb->numRects + 1))))
2108         return;
2109     REGION_SubtractRegion(tra,sra,srb);
2110     REGION_SubtractRegion(trb,srb,sra);
2111     REGION_UnionRegion(dr,tra,trb);
2112     REGION_DestroyWineRegion(tra);
2113     REGION_DestroyWineRegion(trb);
2114     return;
2115 }
2116
2117 /**************************************************************************
2118  *
2119  *    Poly Regions
2120  *
2121  *************************************************************************/
2122
2123 #define LARGE_COORDINATE  0x7fffffff /* FIXME */
2124 #define SMALL_COORDINATE  0x80000000
2125
2126 /***********************************************************************
2127  *     REGION_InsertEdgeInET
2128  *
2129  *     Insert the given edge into the edge table.
2130  *     First we must find the correct bucket in the
2131  *     Edge table, then find the right slot in the
2132  *     bucket.  Finally, we can insert it.
2133  *
2134  */
2135 static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
2136                 INT scanline, ScanLineListBlock **SLLBlock, INT *iSLLBlock)
2137
2138 {
2139     EdgeTableEntry *start, *prev;
2140     ScanLineList *pSLL, *pPrevSLL;
2141     ScanLineListBlock *tmpSLLBlock;
2142
2143     /*
2144      * find the right bucket to put the edge into
2145      */
2146     pPrevSLL = &ET->scanlines;
2147     pSLL = pPrevSLL->next;
2148     while (pSLL && (pSLL->scanline < scanline))
2149     {
2150         pPrevSLL = pSLL;
2151         pSLL = pSLL->next;
2152     }
2153
2154     /*
2155      * reassign pSLL (pointer to ScanLineList) if necessary
2156      */
2157     if ((!pSLL) || (pSLL->scanline > scanline))
2158     {
2159         if (*iSLLBlock > SLLSPERBLOCK-1)
2160         {
2161             tmpSLLBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(ScanLineListBlock));
2162             if(!tmpSLLBlock)
2163             {
2164                 WARN("Can't alloc SLLB\n");
2165                 return;
2166             }
2167             (*SLLBlock)->next = tmpSLLBlock;
2168             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
2169             *SLLBlock = tmpSLLBlock;
2170             *iSLLBlock = 0;
2171         }
2172         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
2173
2174         pSLL->next = pPrevSLL->next;
2175         pSLL->edgelist = (EdgeTableEntry *)NULL;
2176         pPrevSLL->next = pSLL;
2177     }
2178     pSLL->scanline = scanline;
2179
2180     /*
2181      * now insert the edge in the right bucket
2182      */
2183     prev = (EdgeTableEntry *)NULL;
2184     start = pSLL->edgelist;
2185     while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
2186     {
2187         prev = start;
2188         start = start->next;
2189     }
2190     ETE->next = start;
2191
2192     if (prev)
2193         prev->next = ETE;
2194     else
2195         pSLL->edgelist = ETE;
2196 }
2197
2198 /***********************************************************************
2199  *     REGION_CreateEdgeTable
2200  *
2201  *     This routine creates the edge table for
2202  *     scan converting polygons.
2203  *     The Edge Table (ET) looks like:
2204  *
2205  *    EdgeTable
2206  *     --------
2207  *    |  ymax  |        ScanLineLists
2208  *    |scanline|-->------------>-------------->...
2209  *     --------   |scanline|   |scanline|
2210  *                |edgelist|   |edgelist|
2211  *                ---------    ---------
2212  *                    |             |
2213  *                    |             |
2214  *                    V             V
2215  *              list of ETEs   list of ETEs
2216  *
2217  *     where ETE is an EdgeTableEntry data structure,
2218  *     and there is one ScanLineList per scanline at
2219  *     which an edge is initially entered.
2220  *
2221  */
2222 static void REGION_CreateETandAET(const INT *Count, INT nbpolygons,
2223             const POINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
2224             EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
2225 {
2226     const POINT *top, *bottom;
2227     const POINT *PrevPt, *CurrPt, *EndPt;
2228     INT poly, count;
2229     int iSLLBlock = 0;
2230     int dy;
2231
2232
2233     /*
2234      *  initialize the Active Edge Table
2235      */
2236     AET->next = (EdgeTableEntry *)NULL;
2237     AET->back = (EdgeTableEntry *)NULL;
2238     AET->nextWETE = (EdgeTableEntry *)NULL;
2239     AET->bres.minor_axis = SMALL_COORDINATE;
2240
2241     /*
2242      *  initialize the Edge Table.
2243      */
2244     ET->scanlines.next = (ScanLineList *)NULL;
2245     ET->ymax = SMALL_COORDINATE;
2246     ET->ymin = LARGE_COORDINATE;
2247     pSLLBlock->next = (ScanLineListBlock *)NULL;
2248
2249     EndPt = pts - 1;
2250     for(poly = 0; poly < nbpolygons; poly++)
2251     {
2252         count = Count[poly];
2253         EndPt += count;
2254         if(count < 2)
2255             continue;
2256
2257         PrevPt = EndPt;
2258
2259     /*
2260      *  for each vertex in the array of points.
2261      *  In this loop we are dealing with two vertices at
2262      *  a time -- these make up one edge of the polygon.
2263      */
2264         while (count--)
2265         {
2266             CurrPt = pts++;
2267
2268         /*
2269          *  find out which point is above and which is below.
2270          */
2271             if (PrevPt->y > CurrPt->y)
2272             {
2273                 bottom = PrevPt, top = CurrPt;
2274                 pETEs->ClockWise = 0;
2275             }
2276             else
2277             {
2278                 bottom = CurrPt, top = PrevPt;
2279                 pETEs->ClockWise = 1;
2280             }
2281
2282         /*
2283          * don't add horizontal edges to the Edge table.
2284          */
2285             if (bottom->y != top->y)
2286             {
2287                 pETEs->ymax = bottom->y-1;
2288                                 /* -1 so we don't get last scanline */
2289
2290             /*
2291              *  initialize integer edge algorithm
2292              */
2293                 dy = bottom->y - top->y;
2294                 BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
2295
2296                 REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
2297                                                                 &iSLLBlock);
2298
2299                 if (PrevPt->y > ET->ymax)
2300                   ET->ymax = PrevPt->y;
2301                 if (PrevPt->y < ET->ymin)
2302                   ET->ymin = PrevPt->y;
2303                 pETEs++;
2304             }
2305
2306             PrevPt = CurrPt;
2307         }
2308     }
2309 }
2310
2311 /***********************************************************************
2312  *     REGION_loadAET
2313  *
2314  *     This routine moves EdgeTableEntries from the
2315  *     EdgeTable into the Active Edge Table,
2316  *     leaving them sorted by smaller x coordinate.
2317  *
2318  */
2319 static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
2320 {
2321     EdgeTableEntry *pPrevAET;
2322     EdgeTableEntry *tmp;
2323
2324     pPrevAET = AET;
2325     AET = AET->next;
2326     while (ETEs)
2327     {
2328         while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
2329         {
2330             pPrevAET = AET;
2331             AET = AET->next;
2332         }
2333         tmp = ETEs->next;
2334         ETEs->next = AET;
2335         if (AET)
2336             AET->back = ETEs;
2337         ETEs->back = pPrevAET;
2338         pPrevAET->next = ETEs;
2339         pPrevAET = ETEs;
2340
2341         ETEs = tmp;
2342     }
2343 }
2344
2345 /***********************************************************************
2346  *     REGION_computeWAET
2347  *
2348  *     This routine links the AET by the
2349  *     nextWETE (winding EdgeTableEntry) link for
2350  *     use by the winding number rule.  The final
2351  *     Active Edge Table (AET) might look something
2352  *     like:
2353  *
2354  *     AET
2355  *     ----------  ---------   ---------
2356  *     |ymax    |  |ymax    |  |ymax    |
2357  *     | ...    |  |...     |  |...     |
2358  *     |next    |->|next    |->|next    |->...
2359  *     |nextWETE|  |nextWETE|  |nextWETE|
2360  *     ---------   ---------   ^--------
2361  *         |                   |       |
2362  *         V------------------->       V---> ...
2363  *
2364  */
2365 static void REGION_computeWAET(EdgeTableEntry *AET)
2366 {
2367     register EdgeTableEntry *pWETE;
2368     register int inside = 1;
2369     register int isInside = 0;
2370
2371     AET->nextWETE = (EdgeTableEntry *)NULL;
2372     pWETE = AET;
2373     AET = AET->next;
2374     while (AET)
2375     {
2376         if (AET->ClockWise)
2377             isInside++;
2378         else
2379             isInside--;
2380
2381         if ((!inside && !isInside) ||
2382             ( inside &&  isInside))
2383         {
2384             pWETE->nextWETE = AET;
2385             pWETE = AET;
2386             inside = !inside;
2387         }
2388         AET = AET->next;
2389     }
2390     pWETE->nextWETE = (EdgeTableEntry *)NULL;
2391 }
2392
2393 /***********************************************************************
2394  *     REGION_InsertionSort
2395  *
2396  *     Just a simple insertion sort using
2397  *     pointers and back pointers to sort the Active
2398  *     Edge Table.
2399  *
2400  */
2401 static BOOL REGION_InsertionSort(EdgeTableEntry *AET)
2402 {
2403     EdgeTableEntry *pETEchase;
2404     EdgeTableEntry *pETEinsert;
2405     EdgeTableEntry *pETEchaseBackTMP;
2406     BOOL changed = FALSE;
2407
2408     AET = AET->next;
2409     while (AET)
2410     {
2411         pETEinsert = AET;
2412         pETEchase = AET;
2413         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
2414             pETEchase = pETEchase->back;
2415
2416         AET = AET->next;
2417         if (pETEchase != pETEinsert)
2418         {
2419             pETEchaseBackTMP = pETEchase->back;
2420             pETEinsert->back->next = AET;
2421             if (AET)
2422                 AET->back = pETEinsert->back;
2423             pETEinsert->next = pETEchase;
2424             pETEchase->back->next = pETEinsert;
2425             pETEchase->back = pETEinsert;
2426             pETEinsert->back = pETEchaseBackTMP;
2427             changed = TRUE;
2428         }
2429     }
2430     return changed;
2431 }
2432
2433 /***********************************************************************
2434  *     REGION_FreeStorage
2435  *
2436  *     Clean up our act.
2437  */
2438 static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
2439 {
2440     ScanLineListBlock   *tmpSLLBlock;
2441
2442     while (pSLLBlock)
2443     {
2444         tmpSLLBlock = pSLLBlock->next;
2445         HeapFree( GetProcessHeap(), 0, pSLLBlock );
2446         pSLLBlock = tmpSLLBlock;
2447     }
2448 }
2449
2450
2451 /***********************************************************************
2452  *     REGION_PtsToRegion
2453  *
2454  *     Create an array of rectangles from a list of points.
2455  */
2456 static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
2457                        POINTBLOCK *FirstPtBlock, WINEREGION *reg)
2458 {
2459     RECT *rects;
2460     POINT *pts;
2461     POINTBLOCK *CurPtBlock;
2462     int i;
2463     RECT *extents;
2464     INT numRects;
2465
2466     extents = &reg->extents;
2467
2468     numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
2469
2470     if (!(reg->rects = HeapReAlloc( GetProcessHeap(), 0, reg->rects,
2471                            sizeof(RECT) * numRects )))
2472         return(0);
2473
2474     reg->size = numRects;
2475     CurPtBlock = FirstPtBlock;
2476     rects = reg->rects - 1;
2477     numRects = 0;
2478     extents->left = LARGE_COORDINATE,  extents->right = SMALL_COORDINATE;
2479
2480     for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
2481         /* the loop uses 2 points per iteration */
2482         i = NUMPTSTOBUFFER >> 1;
2483         if (!numFullPtBlocks)
2484             i = iCurPtBlock >> 1;
2485         for (pts = CurPtBlock->pts; i--; pts += 2) {
2486             if (pts->x == pts[1].x)
2487                 continue;
2488             if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
2489                 pts[1].x == rects->right &&
2490                 (numRects == 1 || rects[-1].top != rects->top) &&
2491                 (i && pts[2].y > pts[1].y)) {
2492                 rects->bottom = pts[1].y + 1;
2493                 continue;
2494             }
2495             numRects++;
2496             rects++;
2497             rects->left = pts->x;  rects->top = pts->y;
2498             rects->right = pts[1].x;  rects->bottom = pts[1].y + 1;
2499             if (rects->left < extents->left)
2500                 extents->left = rects->left;
2501             if (rects->right > extents->right)
2502                 extents->right = rects->right;
2503         }
2504         CurPtBlock = CurPtBlock->next;
2505     }
2506
2507     if (numRects) {
2508         extents->top = reg->rects->top;
2509         extents->bottom = rects->bottom;
2510     } else {
2511         extents->left = 0;
2512         extents->top = 0;
2513         extents->right = 0;
2514         extents->bottom = 0;
2515     }
2516     reg->numRects = numRects;
2517
2518     return(TRUE);
2519 }
2520
2521 /***********************************************************************
2522  *           CreatePolyPolygonRgn    (GDI32.@)
2523  */
2524 HRGN WINAPI CreatePolyPolygonRgn(const POINT *Pts, const INT *Count,
2525                       INT nbpolygons, INT mode)
2526 {
2527     HRGN hrgn;
2528     RGNOBJ *obj;
2529     WINEREGION *region;
2530     register EdgeTableEntry *pAET;   /* Active Edge Table       */
2531     register INT y;                /* current scanline        */
2532     register int iPts = 0;           /* number of pts in buffer */
2533     register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
2534     register ScanLineList *pSLL;     /* current scanLineList    */
2535     register POINT *pts;           /* output buffer           */
2536     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
2537     EdgeTable ET;                    /* header node for ET      */
2538     EdgeTableEntry AET;              /* header node for AET     */
2539     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
2540     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
2541     int fixWAET = FALSE;
2542     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
2543     POINTBLOCK *tmpPtBlock;
2544     int numFullPtBlocks = 0;
2545     INT poly, total;
2546
2547     if(!(hrgn = REGION_CreateRegion(nbpolygons)))
2548         return 0;
2549     obj = (RGNOBJ *) GDI_GetObjPtr( hrgn, REGION_MAGIC );
2550     region = obj->rgn;
2551
2552     /* special case a rectangle */
2553
2554     if (((nbpolygons == 1) && ((*Count == 4) ||
2555        ((*Count == 5) && (Pts[4].x == Pts[0].x) && (Pts[4].y == Pts[0].y)))) &&
2556         (((Pts[0].y == Pts[1].y) &&
2557           (Pts[1].x == Pts[2].x) &&
2558           (Pts[2].y == Pts[3].y) &&
2559           (Pts[3].x == Pts[0].x)) ||
2560          ((Pts[0].x == Pts[1].x) &&
2561           (Pts[1].y == Pts[2].y) &&
2562           (Pts[2].x == Pts[3].x) &&
2563           (Pts[3].y == Pts[0].y))))
2564     {
2565         SetRectRgn( hrgn, min(Pts[0].x, Pts[2].x), min(Pts[0].y, Pts[2].y),
2566                             max(Pts[0].x, Pts[2].x), max(Pts[0].y, Pts[2].y) );
2567         GDI_ReleaseObj( hrgn );
2568         return hrgn;
2569     }
2570
2571     for(poly = total = 0; poly < nbpolygons; poly++)
2572         total += Count[poly];
2573     if (! (pETEs = HeapAlloc( GetProcessHeap(), 0, sizeof(EdgeTableEntry) * total )))
2574     {
2575         REGION_DeleteObject( hrgn, obj );
2576         return 0;
2577     }
2578     pts = FirstPtBlock.pts;
2579     REGION_CreateETandAET(Count, nbpolygons, Pts, &ET, &AET, pETEs, &SLLBlock);
2580     pSLL = ET.scanlines.next;
2581     curPtBlock = &FirstPtBlock;
2582
2583     if (mode != WINDING) {
2584         /*
2585          *  for each scanline
2586          */
2587         for (y = ET.ymin; y < ET.ymax; y++) {
2588             /*
2589              *  Add a new edge to the active edge table when we
2590              *  get to the next edge.
2591              */
2592             if (pSLL != NULL && y == pSLL->scanline) {
2593                 REGION_loadAET(&AET, pSLL->edgelist);
2594                 pSLL = pSLL->next;
2595             }
2596             pPrevAET = &AET;
2597             pAET = AET.next;
2598
2599             /*
2600              *  for each active edge
2601              */
2602             while (pAET) {
2603                 pts->x = pAET->bres.minor_axis,  pts->y = y;
2604                 pts++, iPts++;
2605
2606                 /*
2607                  *  send out the buffer
2608                  */
2609                 if (iPts == NUMPTSTOBUFFER) {
2610                     tmpPtBlock = HeapAlloc( GetProcessHeap(), 0, sizeof(POINTBLOCK));
2611                     if(!tmpPtBlock) {
2612                         WARN("Can't alloc tPB\n");
2613                         return 0;
2614                     }
2615                     curPtBlock->next = tmpPtBlock;
2616                     curPtBlock = tmpPtBlock;
2617                     pts = curPtBlock->pts;
2618                     numFullPtBlocks++;
2619                     iPts = 0;
2620                 }
2621                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
2622             }
2623             REGION_InsertionSort(&AET);
2624         }
2625     }
2626     else {
2627         /*
2628          *  for each scanline
2629          */
2630         for (y = ET.ymin; y < ET.ymax; y++) {
2631             /*
2632              *  Add a new edge to the active edge table when we
2633              *  get to the next edge.
2634              */
2635             if (pSLL != NULL && y == pSLL->scanline) {
2636                 REGION_loadAET(&AET, pSLL->edgelist);
2637                 REGION_computeWAET(&AET);
2638                 pSLL = pSLL->next;
2639             }
2640             pPrevAET = &AET;
2641             pAET = AET.next;
2642             pWETE = pAET;
2643
2644             /*
2645              *  for each active edge
2646              */
2647             while (pAET) {
2648                 /*
2649                  *  add to the buffer only those edges that
2650                  *  are in the Winding active edge table.
2651                  */
2652                 if (pWETE == pAET) {
2653                     pts->x = pAET->bres.minor_axis,  pts->y = y;
2654                     pts++, iPts++;
2655
2656                     /*
2657                      *  send out the buffer
2658                      */
2659                     if (iPts == NUMPTSTOBUFFER) {
2660                         tmpPtBlock = HeapAlloc( GetProcessHeap(), 0,
2661                                                sizeof(POINTBLOCK) );
2662                         if(!tmpPtBlock) {
2663                             WARN("Can't alloc tPB\n");
2664                             REGION_DeleteObject( hrgn, obj );
2665                             return 0;
2666                         }
2667                         curPtBlock->next = tmpPtBlock;
2668                         curPtBlock = tmpPtBlock;
2669                         pts = curPtBlock->pts;
2670                         numFullPtBlocks++;    iPts = 0;
2671                     }
2672                     pWETE = pWETE->nextWETE;
2673                 }
2674                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
2675             }
2676
2677             /*
2678              *  recompute the winding active edge table if
2679              *  we just resorted or have exited an edge.
2680              */
2681             if (REGION_InsertionSort(&AET) || fixWAET) {
2682                 REGION_computeWAET(&AET);
2683                 fixWAET = FALSE;
2684             }
2685         }
2686     }
2687     REGION_FreeStorage(SLLBlock.next);
2688     REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
2689
2690     for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
2691         tmpPtBlock = curPtBlock->next;
2692         HeapFree( GetProcessHeap(), 0, curPtBlock );
2693         curPtBlock = tmpPtBlock;
2694     }
2695     HeapFree( GetProcessHeap(), 0, pETEs );
2696     GDI_ReleaseObj( hrgn );
2697     return hrgn;
2698 }
2699
2700
2701 /***********************************************************************
2702  *           CreatePolygonRgn    (GDI32.@)
2703  */
2704 HRGN WINAPI CreatePolygonRgn( const POINT *points, INT count,
2705                                   INT mode )
2706 {
2707     return CreatePolyPolygonRgn( points, &count, 1, mode );
2708 }
2709
2710
2711 /***********************************************************************
2712  * GetRandomRgn [GDI32.@]
2713  *
2714  * NOTES
2715  *     This function is documented in MSDN online
2716  */
2717 INT WINAPI GetRandomRgn(HDC hDC, HRGN hRgn, DWORD dwCode)
2718 {
2719     switch (dwCode)
2720     {
2721         case 4: /* == SYSRGN ? */
2722         {
2723             DC *dc = DC_GetDCPtr (hDC);
2724             OSVERSIONINFOA vi;
2725             POINT org;
2726
2727             if (!dc) return -1;
2728             CombineRgn (hRgn, dc->hVisRgn, 0, RGN_COPY);
2729             /*
2730              *     On Windows NT/2000,
2731              *           the region returned is in screen coordinates.
2732              *     On Windows 95/98,
2733              *           the region returned is in window coordinates
2734              */
2735             vi.dwOSVersionInfoSize = sizeof(vi);
2736             if (GetVersionExA( &vi ) && vi.dwPlatformId == VER_PLATFORM_WIN32_NT)
2737                 GetDCOrgEx(hDC, &org);
2738             else
2739                 org.x = org.y = 0;
2740             OffsetRgn (hRgn, org.x, org.y);
2741             GDI_ReleaseObj( hDC );
2742             return 1;
2743         }
2744 /*      case 1:
2745             return GetClipRgn (hDC, hRgn);
2746 */
2747         default:
2748             WARN("Unknown dwCode %ld\n", dwCode);
2749             return -1;
2750     }
2751
2752     return -1;
2753 }
2754
2755
2756 /***********************************************************************
2757  *           GetMetaRgn    (GDI32.@)
2758  */
2759 INT WINAPI GetMetaRgn( HDC hdc, HRGN hRgn )
2760 {
2761   FIXME( "stub\n" );
2762
2763   return 0;
2764 }
2765
2766
2767 /***********************************************************************
2768  *           SetMetaRgn    (GDI32.@)
2769  */
2770 INT WINAPI SetMetaRgn( HDC hdc )
2771 {
2772   FIXME( "stub\n" );
2773
2774   return ERROR;
2775 }