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