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