subsys/win32k/objects/region.c

   1 #undef WIN32_LEAN_AND_MEAN
   2 #include <windows.h>
   3 #include <ddk/ntddk.h>
   4 #include <internal/safe.h>
   5 #include <win32k/float.h>
   6 #include <win32k/dc.h>
   7 #include <win32k/bitmaps.h>
   8 #include <win32k/region.h>
   9 #include <win32k/cliprgn.h>
  10 #include <win32k/brush.h>
  11 #include <include/rect.h>
  12
  13
  14 #define NDEBUG
  15 #include <win32k/debug1.h>
  16
  17 BOOL STDCALL
  18 IntEngPaint(IN SURFOBJ *Surface,IN CLIPOBJ *ClipRegion,IN BRUSHOBJ *Brush,IN POINTL *BrushOrigin,
  19          IN MIX  Mix);
  20
  21 // Internal Functions
  22
  23 #define EMPTY_REGION(pReg) { \
  24   (pReg)->rdh.nCount = 0; \
  25   (pReg)->rdh.rcBound.left = (pReg)->rdh.rcBound.top = 0; \
  26   (pReg)->rdh.rcBound.right = (pReg)->rdh.rcBound.bottom = 0; \
  27   (pReg)->rdh.iType = NULLREGION; \
  28 }
  29
  30 #define REGION_NOT_EMPTY(pReg) pReg->rdh.nCount
  31
  32 #define INRECT(r, x, y) \
  33       ( ( ((r).right >  x)) && \
  34         ( ((r).left <= x)) && \
  35         ( ((r).bottom >  y)) && \
  36         ( ((r).top <= y)) )
  37
  38 /*  1 if two RECTs overlap.
  39  *  0 if two RECTs do not overlap.
  40  */
  41 #define EXTENTCHECK(r1, r2) \
  42         ((r1)->right > (r2)->left && \
  43          (r1)->left < (r2)->right && \
  44          (r1)->bottom > (r2)->top && \
  45          (r1)->top < (r2)->bottom)
  46
  47 /*
  48  *   Check to see if there is enough memory in the present region.
  49  */
  50 static inline int xmemcheck(ROSRGNDATA *reg, LPRECT *rect, LPRECT *firstrect ) {
  51         if ( (reg->rdh.nCount+1)*sizeof( RECT ) >= reg->rdh.nRgnSize ) {
  52                 PRECT temp;
  53                 temp = ExAllocatePool( PagedPool, (2 * (reg->rdh.nRgnSize)));
  54
  55                 if (temp == 0)
  56                     return 0;
  57                 RtlCopyMemory( temp, *firstrect, reg->rdh.nRgnSize );
  58                 reg->rdh.nRgnSize *= 2;
  59                 ExFreePool( *firstrect );
  60                 *firstrect = temp;
  61                 *rect = (*firstrect)+reg->rdh.nCount;
  62     }
  63     return 1;
  64 }
  65
  66 #define MEMCHECK(reg, rect, firstrect) xmemcheck(reg,&(rect),&(firstrect))
  67
  68 typedef void (*voidProcp)();
  69
  70 // Number of points to buffer before sending them off to scanlines() :  Must be an even number
  71 #define NUMPTSTOBUFFER 200
  72
  73 #define RGN_DEFAULT_RECTS       2
  74
  75 // used to allocate buffers for points and link the buffers together
  76
  77 typedef struct _POINTBLOCK {
  78   POINT pts[NUMPTSTOBUFFER];
  79   struct _POINTBLOCK *next;
  80 } POINTBLOCK;
  81
  82 static BOOL REGION_CopyRegion(PROSRGNDATA dst, PROSRGNDATA src)
  83 {
  84   if(dst != src) //  don't want to copy to itself
  85   {
  86     if (dst->rdh.nRgnSize < src->rdh.nCount * sizeof(RECT))
  87     {
  88           PCHAR temp;
  89
  90           temp = ExAllocatePool(PagedPool, src->rdh.nCount * sizeof(RECT) );
  91           if( !temp )
  92                 return FALSE;
  93
  94           if( dst->Buffer )
  95                 ExFreePool( dst->Buffer );      //free the old buffer
  96           dst->Buffer = temp;
  97       dst->rdh.nRgnSize = src->rdh.nCount * sizeof(RECT);  //size of region buffer
  98     }
  99     dst->rdh.nCount = src->rdh.nCount;                 //number of rectangles present in Buffer
 100     dst->rdh.rcBound.left = src->rdh.rcBound.left;
 101     dst->rdh.rcBound.top = src->rdh.rcBound.top;
 102     dst->rdh.rcBound.right = src->rdh.rcBound.right;
 103     dst->rdh.rcBound.bottom = src->rdh.rcBound.bottom;
 104     dst->rdh.iType = src->rdh.iType;
 105     RtlCopyMemory(dst->Buffer, src->Buffer, (int)(src->rdh.nCount * sizeof(RECT)));
 106   }
 107   return TRUE;
 108 }
 109
 110 static void REGION_SetExtents (ROSRGNDATA *pReg)
 111 {
 112     RECT *pRect, *pRectEnd, *pExtents;
 113
 114     if (pReg->rdh.nCount == 0)
 115     {
 116                 pReg->rdh.rcBound.left = 0;
 117                 pReg->rdh.rcBound.top = 0;
 118                 pReg->rdh.rcBound.right = 0;
 119                 pReg->rdh.rcBound.bottom = 0;
 120                 return;
 121     }
 122
 123     pExtents = &pReg->rdh.rcBound;
 124     pRect = (PRECT)pReg->Buffer;
 125     pRectEnd = (PRECT)pReg->Buffer + pReg->rdh.nCount - 1;
 126
 127     /*
 128      * Since pRect is the first rectangle in the region, it must have the
 129      * smallest top and since pRectEnd is the last rectangle in the region,
 130      * it must have the largest bottom, because of banding. Initialize left and
 131      * right from pRect and pRectEnd, resp., as good things to initialize them
 132      * to...
 133      */
 134     pExtents->left = pRect->left;
 135     pExtents->top = pRect->top;
 136     pExtents->right = pRectEnd->right;
 137     pExtents->bottom = pRectEnd->bottom;
 138
 139     while (pRect <= pRectEnd)
 140     {
 141                 if (pRect->left < pExtents->left)
 142                     pExtents->left = pRect->left;
 143                 if (pRect->right > pExtents->right)
 144                     pExtents->right = pRect->right;
 145                 pRect++;
 146     }
 147 }
 148
 149
 150 /***********************************************************************
 151  *           REGION_CropAndOffsetRegion
 152  */
 153 static BOOL REGION_CropAndOffsetRegion(const PPOINT off, const PRECT rect, PROSRGNDATA rgnSrc, PROSRGNDATA rgnDst)
 154 {
 155   if(!rect) // just copy and offset
 156   {
 157     PRECT xrect;
 158     if(rgnDst == rgnSrc)
 159     {
 160       if(off->x || off->y)
 161         xrect = (PRECT)rgnDst->Buffer;
 162       else
 163         return TRUE;
 164     }
 165     else{
 166       xrect = ExAllocatePool(PagedPool, rgnSrc->rdh.nCount * sizeof(RECT));
 167           if( rgnDst->Buffer )
 168                 ExFreePool( rgnDst->Buffer ); //free the old buffer. will be assigned to xrect below.
 169         }
 170
 171     if(xrect)
 172     {
 173       INT i;
 174
 175       if(rgnDst != rgnSrc)
 176                 RtlCopyMemory(rgnDst, rgnSrc, sizeof(ROSRGNDATA));
 177
 178       if(off->x || off->y)
 179       {
 180         for(i = 0; i < rgnDst->rdh.nCount; i++)
 181         {
 182           xrect[i].left = ((PRECT)rgnSrc->Buffer + i)->left + off->x;
 183           xrect[i].right = ((PRECT)rgnSrc->Buffer + i)->right + off->x;
 184           xrect[i].top = ((PRECT)rgnSrc->Buffer + i)->top + off->y;
 185           xrect[i].bottom = ((PRECT)rgnSrc->Buffer + i)->bottom + off->y;
 186         }
 187         rgnDst->rdh.rcBound.left   += off->x;
 188         rgnDst->rdh.rcBound.right  += off->x;
 189         rgnDst->rdh.rcBound.top    += off->y;
 190         rgnDst->rdh.rcBound.bottom += off->y;
 191       }
 192       else
 193         RtlCopyMemory(xrect, rgnSrc->Buffer, rgnDst->rdh.nCount * sizeof(RECT));
 194
 195           rgnDst->Buffer = (char*)xrect;
 196     } else
 197       return FALSE;
 198   }
 199   else if ((rect->left >= rect->right) ||
 200            (rect->top >= rect->bottom) ||
 201             !EXTENTCHECK(rect, &rgnSrc->rdh.rcBound))
 202   {
 203         goto empty;
 204   }
 205   else // region box and clipping rect appear to intersect
 206   {
 207     PRECT lpr, rpr;
 208     INT i, j, clipa, clipb;
 209     INT left = rgnSrc->rdh.rcBound.right + off->x;
 210     INT right = rgnSrc->rdh.rcBound.left + off->x;
 211
 212     for(clipa = 0; ((PRECT)rgnSrc->Buffer + clipa)->bottom <= rect->top; clipa++)
 213         //region and rect intersect so we stop before clipa > rgnSrc->rdh.nCount
 214       ; // skip bands above the clipping rectangle
 215
 216     for(clipb = clipa; clipb < rgnSrc->rdh.nCount; clipb++)
 217       if(((PRECT)rgnSrc->Buffer + clipb)->top >= rect->bottom)
 218         break;    // and below it
 219
 220     // clipa - index of the first rect in the first intersecting band
 221     // clipb - index of the last rect in the last intersecting band
 222
 223     if((rgnDst != rgnSrc) && (rgnDst->rdh.nCount < (i = (clipb - clipa))))
 224     {
 225           PCHAR temp;
 226           temp = ExAllocatePool( PagedPool, i * sizeof(RECT) );
 227       if(!temp)
 228               return FALSE;
 229
 230           if( rgnDst->Buffer )
 231                 ExFreePool( rgnDst->Buffer ); //free the old buffer
 232       (PRECT)rgnDst->Buffer = temp;
 233       rgnDst->rdh.nCount = i;
 234           rgnDst->rdh.nRgnSize = i * sizeof(RECT);
 235     }
 236
 237     for(i = clipa, j = 0; i < clipb ; i++)
 238     {
 239       // i - src index, j - dst index, j is always <= i for obvious reasons
 240
 241       lpr = (PRECT)rgnSrc->Buffer + i;
 242
 243       if(lpr->left < rect->right && lpr->right > rect->left)
 244       {
 245             rpr = (PRECT)rgnDst->Buffer + j;
 246
 247         rpr->top = lpr->top + off->y;
 248         rpr->bottom = lpr->bottom + off->y;
 249         rpr->left = ((lpr->left > rect->left) ? lpr->left : rect->left) + off->x;
 250         rpr->right = ((lpr->right < rect->right) ? lpr->right : rect->right) + off->x;
 251
 252         if(rpr->left < left) left = rpr->left;
 253         if(rpr->right > right) right = rpr->right;
 254
 255         j++;
 256       }
 257     }
 258
 259     if(j == 0) goto empty;
 260
 261     rgnDst->rdh.rcBound.left = left;
 262     rgnDst->rdh.rcBound.right = right;
 263
 264     left = rect->top + off->y;
 265     right = rect->bottom + off->y;
 266
 267     rgnDst->rdh.nCount = j--;
 268     for(i = 0; i <= j; i++) // fixup top band
 269       if(((PRECT)rgnDst->Buffer + i)->top < left)
 270         ((PRECT)rgnDst->Buffer + i)->top = left;
 271       else
 272         break;
 273
 274     for(i = j; i >= 0; i--) // fixup bottom band
 275       if(((PRECT)rgnDst->Buffer + i)->bottom > right)
 276         ((PRECT)rgnDst->Buffer + i)->bottom = right;
 277       else
 278         break;
 279
 280     rgnDst->rdh.rcBound.top = ((PRECT)rgnDst->Buffer)->top;
 281     rgnDst->rdh.rcBound.bottom = ((PRECT)rgnDst->Buffer + j)->bottom;
 282
 283     rgnDst->rdh.iType = (j >= 1) ? COMPLEXREGION : SIMPLEREGION;
 284   }
 285
 286   return TRUE;
 287
 288 empty:
 289         if(!rgnDst->Buffer)
 290         {
 291           rgnDst->Buffer = (char*)ExAllocatePool(PagedPool, RGN_DEFAULT_RECTS * sizeof(RECT));
 292           if(rgnDst->Buffer){
 293             rgnDst->rdh.nCount = RGN_DEFAULT_RECTS;
 294                 rgnDst->rdh.nRgnSize = RGN_DEFAULT_RECTS * sizeof(RECT);
 295           }
 296           else
 297             return FALSE;
 298         }
 299         EMPTY_REGION(rgnDst);
 300         return TRUE;
 301 }
 302
 303 /*!
 304  * \param
 305  * hSrc:        Region to crop and offset.
 306  * lpRect:      Clipping rectangle. Can be NULL (no clipping).
 307  * lpPt:        Points to offset the cropped region. Can be NULL (no offset).
 308  *
 309  * hDst: Region to hold the result (a new region is created if it's 0).
 310  *       Allowed to be the same region as hSrc in which case everything
 311  *       will be done in place, with no memory reallocations.
 312  *
 313  * \return      hDst if success, 0 otherwise.
 314  */
 315 HRGN REGION_CropRgn(HRGN hDst, HRGN hSrc, const PRECT lpRect, PPOINT lpPt)
 316 {
 317   PROSRGNDATA objSrc, rgnDst;
 318   HRGN hNewDst, hRet = NULL;
 319   GDIMULTILOCK Lock[2] = {{hDst, 0, GO_REGION_MAGIC}, {hSrc, 0, GO_REGION_MAGIC}};
 320
 321   if( !hDst ){
 322           if( !( hNewDst = RGNDATA_AllocRgn(1) ) ){
 323                 return 0;
 324           }
 325           Lock[0].hObj = hNewDst;
 326   }
 327
 328   GDIOBJ_LockMultipleObj( &Lock, 2 );
 329   rgnDst = Lock[0].pObj;
 330   objSrc = Lock[1].pObj;
 331
 332   if( objSrc && rgnDst )
 333   {
 334     if(rgnDst)
 335     {
 336       POINT pt = { 0, 0 };
 337
 338           if(!lpPt)
 339                 lpPt = &pt;
 340
 341       if(REGION_CropAndOffsetRegion(lpPt, lpRect, objSrc, rgnDst) == FALSE)
 342           { // ve failed cleanup and return
 343                 hRet = NULL;
 344       }
 345       else{ // ve are fine. unlock the correct pointer and return correct handle
 346                 hRet = Lock[0].hObj;
 347           }
 348     }
 349   }
 350   GDIOBJ_UnlockMultipleObj( &Lock, 2 );
 351   return hRet;
 352 }
 353
 354 /*!
 355  *      Attempt to merge the rects in the current band with those in the
 356  *      previous one. Used only by REGION_RegionOp.
 357  *
 358  * Results:
 359  *      The new index for the previous band.
 360  *
 361  * \note Side Effects:
 362  *      If coalescing takes place:
 363  *          - rectangles in the previous band will have their bottom fields
 364  *            altered.
 365  *          - pReg->numRects will be decreased.
 366  *
 367  */
 368 static INT REGION_Coalesce (
 369              PROSRGNDATA pReg, /* Region to coalesce */
 370              INT prevStart,  /* Index of start of previous band */
 371              INT curStart    /* Index of start of current band */
 372 ) {
 373     RECT *pPrevRect;          /* Current rect in previous band */
 374     RECT *pCurRect;           /* Current rect in current band */
 375     RECT *pRegEnd;            /* End of region */
 376     INT curNumRects;          /* Number of rectangles in current band */
 377     INT prevNumRects;         /* Number of rectangles in previous band */
 378     INT bandtop;               /* top coordinate for current band */
 379
 380     pRegEnd = (PRECT)pReg->Buffer + pReg->rdh.nCount;
 381     pPrevRect = (PRECT)pReg->Buffer + prevStart;
 382     prevNumRects = curStart - prevStart;
 383
 384     /*
 385      * Figure out how many rectangles are in the current band. Have to do
 386      * this because multiple bands could have been added in REGION_RegionOp
 387      * at the end when one region has been exhausted.
 388      */
 389     pCurRect = (PRECT)pReg->Buffer + curStart;
 390     bandtop = pCurRect->top;
 391     for (curNumRects = 0;
 392          (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
 393          curNumRects++)
 394     {
 395                 pCurRect++;
 396     }
 397
 398     if (pCurRect != pRegEnd)
 399     {
 400                 /*
 401                  * If more than one band was added, we have to find the start
 402                  * of the last band added so the next coalescing job can start
 403                  * at the right place... (given when multiple bands are added,
 404                  * this may be pointless -- see above).
 405                  */
 406                 pRegEnd--;
 407                 while ((pRegEnd-1)->top == pRegEnd->top)
 408                 {
 409                     pRegEnd--;
 410                 }
 411                 curStart = pRegEnd - (PRECT)pReg->Buffer;
 412                 pRegEnd = (PRECT)pReg->Buffer + pReg->rdh.nCount;
 413     }
 414
 415     if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
 416                 pCurRect -= curNumRects;
 417                 /*
 418                  * The bands may only be coalesced if the bottom of the previous
 419                  * matches the top scanline of the current.
 420                  */
 421                 if (pPrevRect->bottom == pCurRect->top)
 422                 {
 423                     /*
 424                      * Make sure the bands have rects in the same places. This
 425                      * assumes that rects have been added in such a way that they
 426                      * cover the most area possible. I.e. two rects in a band must
 427                      * have some horizontal space between them.
 428                      */
 429                     do
 430                     {
 431                                 if ((pPrevRect->left != pCurRect->left) ||
 432                                     (pPrevRect->right != pCurRect->right))
 433                                 {
 434                                     /*
 435                                      * The bands don't line up so they can't be coalesced.
 436                                      */
 437                                     return (curStart);
 438                                 }
 439                                 pPrevRect++;
 440                                 pCurRect++;
 441                                 prevNumRects -= 1;
 442                     } while (prevNumRects != 0);
 443
 444                     pReg->rdh.nCount -= curNumRects;
 445                     pCurRect -= curNumRects;
 446                     pPrevRect -= curNumRects;
 447
 448                     /*
 449                      * The bands may be merged, so set the bottom of each rect
 450                      * in the previous band to that of the corresponding rect in
 451                      * the current band.
 452                      */
 453                     do
 454                     {
 455                                 pPrevRect->bottom = pCurRect->bottom;
 456                                 pPrevRect++;
 457                                 pCurRect++;
 458                                 curNumRects -= 1;
 459                     } while (curNumRects != 0);
 460
 461                     /*
 462                      * If only one band was added to the region, we have to backup
 463                      * curStart to the start of the previous band.
 464                      *
 465                      * If more than one band was added to the region, copy the
 466                      * other bands down. The assumption here is that the other bands
 467                      * came from the same region as the current one and no further
 468                      * coalescing can be done on them since it's all been done
 469                      * already... curStart is already in the right place.
 470                      */
 471                     if (pCurRect == pRegEnd)
 472                     {
 473                                 curStart = prevStart;
 474                     }
 475                     else
 476                     {
 477                                 do
 478                                 {
 479                                     *pPrevRect++ = *pCurRect++;
 480                                 } while (pCurRect != pRegEnd);
 481                     }
 482                 }
 483     }
 484     return (curStart);
 485 }
 486
 487 /*!
 488  *      Apply an operation to two regions. Called by REGION_Union,
 489  *      REGION_Inverse, REGION_Subtract, REGION_Intersect...
 490  *
 491  * Results:
 492  *      None.
 493  *
 494  * Side Effects:
 495  *      The new region is overwritten.
 496  *
 497  *\note The idea behind this function is to view the two regions as sets.
 498  *      Together they cover a rectangle of area that this function divides
 499  *      into horizontal bands where points are covered only by one region
 500  *      or by both. For the first case, the nonOverlapFunc is called with
 501  *      each the band and the band's upper and lower extents. For the
 502  *      second, the overlapFunc is called to process the entire band. It
 503  *      is responsible for clipping the rectangles in the band, though
 504  *      this function provides the boundaries.
 505  *      At the end of each band, the new region is coalesced, if possible,
 506  *      to reduce the number of rectangles in the region.
 507  *
 508  */
 509 static void REGION_RegionOp(
 510             ROSRGNDATA *newReg, /* Place to store result */
 511             ROSRGNDATA *reg1,   /* First region in operation */
 512         ROSRGNDATA *reg2,   /* 2nd region in operation */
 513             void (*overlapFunc)(),     /* Function to call for over-lapping bands */
 514             void (*nonOverlap1Func)(), /* Function to call for non-overlapping bands in region 1 */
 515             void (*nonOverlap2Func)()  /* Function to call for non-overlapping bands in region 2 */
 516 ) {
 517     RECT *r1;                         /* Pointer into first region */
 518     RECT *r2;                         /* Pointer into 2d region */
 519     RECT *r1End;                      /* End of 1st region */
 520     RECT *r2End;                      /* End of 2d region */
 521     INT ybot;                         /* Bottom of intersection */
 522     INT ytop;                         /* Top of intersection */
 523     RECT *oldRects;                   /* Old rects for newReg */
 524     INT prevBand;                     /* Index of start of
 525                                                  * previous band in newReg */
 526     INT curBand;                      /* Index of start of current
 527                                                  * band in newReg */
 528     RECT *r1BandEnd;                  /* End of current band in r1 */
 529     RECT *r2BandEnd;                  /* End of current band in r2 */
 530     INT top;                          /* Top of non-overlapping band */
 531     INT bot;                          /* Bottom of non-overlapping band */
 532
 533     /*
 534      * Initialization:
 535      *  set r1, r2, r1End and r2End appropriately, preserve the important
 536      * parts of the destination region until the end in case it's one of
 537      * the two source regions, then mark the "new" region empty, allocating
 538      * another array of rectangles for it to use.
 539      */
 540     r1 = (PRECT)reg1->Buffer;
 541     r2 = (PRECT)reg2->Buffer;
 542     r1End = r1 + reg1->rdh.nCount;
 543     r2End = r2 + reg2->rdh.nCount;
 544
 545
 546     /*
 547      * newReg may be one of the src regions so we can't empty it. We keep a
 548      * note of its rects pointer (so that we can free them later), preserve its
 549      * extents and simply set numRects to zero.
 550      */
 551
 552     oldRects = (PRECT)newReg->Buffer;
 553     newReg->rdh.nCount = 0;
 554
 555     /*
 556      * Allocate a reasonable number of rectangles for the new region. The idea
 557      * is to allocate enough so the individual functions don't need to
 558      * reallocate and copy the array, which is time consuming, yet we don't
 559      * have to worry about using too much memory. I hope to be able to
 560      * nuke the Xrealloc() at the end of this function eventually.
 561      */
 562     newReg->rdh.nRgnSize = max(reg1->rdh.nCount,reg2->rdh.nCount) * 2 * sizeof(RECT);
 563
 564     if (! (newReg->Buffer = ExAllocatePool( PagedPool, newReg->rdh.nRgnSize )))
 565     {
 566                 newReg->rdh.nRgnSize = 0;
 567                 return;
 568     }
 569
 570     /*
 571      * Initialize ybot and ytop.
 572      * In the upcoming loop, ybot and ytop serve different functions depending
 573      * on whether the band being handled is an overlapping or non-overlapping
 574      * band.
 575      *  In the case of a non-overlapping band (only one of the regions
 576      * has points in the band), ybot is the bottom of the most recent
 577      * intersection and thus clips the top of the rectangles in that band.
 578      * ytop is the top of the next intersection between the two regions and
 579      * serves to clip the bottom of the rectangles in the current band.
 580      *  For an overlapping band (where the two regions intersect), ytop clips
 581      * the top of the rectangles of both regions and ybot clips the bottoms.
 582      */
 583     if (reg1->rdh.rcBound.top < reg2->rdh.rcBound.top)
 584                 ybot = reg1->rdh.rcBound.top;
 585     else
 586                 ybot = reg2->rdh.rcBound.top;
 587
 588     /*
 589      * prevBand serves to mark the start of the previous band so rectangles
 590      * can be coalesced into larger rectangles. qv. miCoalesce, above.
 591      * In the beginning, there is no previous band, so prevBand == curBand
 592      * (curBand is set later on, of course, but the first band will always
 593      * start at index 0). prevBand and curBand must be indices because of
 594      * the possible expansion, and resultant moving, of the new region's
 595      * array of rectangles.
 596      */
 597     prevBand = 0;
 598
 599     do
 600     {
 601                 curBand = newReg->rdh.nCount;
 602
 603                 /*
 604                  * This algorithm proceeds one source-band (as opposed to a
 605                  * destination band, which is determined by where the two regions
 606                  * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
 607                  * rectangle after the last one in the current band for their
 608                  * respective regions.
 609                  */
 610                 r1BandEnd = r1;
 611                 while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top))
 612                 {
 613                     r1BandEnd++;
 614                 }
 615
 616                 r2BandEnd = r2;
 617                 while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top))
 618                 {
 619                     r2BandEnd++;
 620                 }
 621
 622                 /*
 623                  * First handle the band that doesn't intersect, if any.
 624                  *
 625                  * Note that attention is restricted to one band in the
 626                  * non-intersecting region at once, so if a region has n
 627                  * bands between the current position and the next place it overlaps
 628                  * the other, this entire loop will be passed through n times.
 629                  */
 630                 if (r1->top < r2->top)
 631                 {
 632                     top = max(r1->top,ybot);
 633                     bot = min(r1->bottom,r2->top);
 634
 635                     if ((top != bot) && (nonOverlap1Func != (void (*)())NULL))
 636                     {
 637                                 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
 638                     }
 639
 640                     ytop = r2->top;
 641                 }
 642                 else if (r2->top < r1->top)
 643                 {
 644                     top = max(r2->top,ybot);
 645                     bot = min(r2->bottom,r1->top);
 646
 647                     if ((top != bot) && (nonOverlap2Func != (void (*)())NULL))
 648                     {
 649                                 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
 650                     }
 651
 652                     ytop = r1->top;
 653                 }
 654                 else
 655                 {
 656                     ytop = r1->top;
 657                 }
 658
 659                 /*
 660                  * If any rectangles got added to the region, try and coalesce them
 661                  * with rectangles from the previous band. Note we could just do
 662                  * this test in miCoalesce, but some machines incur a not
 663                  * inconsiderable cost for function calls, so...
 664                  */
 665                 if (newReg->rdh.nCount != curBand)
 666                 {
 667                     prevBand = REGION_Coalesce (newReg, prevBand, curBand);
 668                 }
 669
 670                 /*
 671                  * Now see if we've hit an intersecting band. The two bands only
 672                  * intersect if ybot > ytop
 673                  */
 674                 ybot = min(r1->bottom, r2->bottom);
 675                 curBand = newReg->rdh.nCount;
 676                 if (ybot > ytop)
 677                 {
 678                     (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
 679                 }
 680
 681                 if (newReg->rdh.nCount != curBand)
 682                 {
 683                     prevBand = REGION_Coalesce (newReg, prevBand, curBand);
 684                 }
 685
 686                 /*
 687                  * If we've finished with a band (bottom == ybot) we skip forward
 688                  * in the region to the next band.
 689                  */
 690                 if (r1->bottom == ybot)
 691                 {
 692                     r1 = r1BandEnd;
 693                 }
 694                 if (r2->bottom == ybot)
 695                 {
 696                     r2 = r2BandEnd;
 697                 }
 698     } while ((r1 != r1End) && (r2 != r2End));
 699
 700     /*
 701      * Deal with whichever region still has rectangles left.
 702      */
 703     curBand = newReg->rdh.nCount;
 704     if (r1 != r1End)
 705     {
 706                 if (nonOverlap1Func != (void (*)())NULL)
 707                 {
 708                     do
 709                     {
 710                                 r1BandEnd = r1;
 711                                 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top))
 712                                 {
 713                                     r1BandEnd++;
 714                                 }
 715                                 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
 716                                                      max(r1->top,ybot), r1->bottom);
 717                                 r1 = r1BandEnd;
 718                     } while (r1 != r1End);
 719                 }
 720     }
 721     else if ((r2 != r2End) && (nonOverlap2Func != (void (*)())NULL))
 722     {
 723                 do
 724                 {
 725                     r2BandEnd = r2;
 726                     while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top))
 727                     {
 728                          r2BandEnd++;
 729                     }
 730                     (* nonOverlap2Func) (newReg, r2, r2BandEnd,
 731                                         max(r2->top,ybot), r2->bottom);
 732                     r2 = r2BandEnd;
 733                 } while (r2 != r2End);
 734     }
 735
 736     if (newReg->rdh.nCount != curBand)
 737     {
 738                 (void) REGION_Coalesce (newReg, prevBand, curBand);
 739     }
 740
 741     /*
 742      * A bit of cleanup. To keep regions from growing without bound,
 743      * we shrink the array of rectangles to match the new number of
 744      * rectangles in the region. This never goes to 0, however...
 745      *
 746      * Only do this stuff if the number of rectangles allocated is more than
 747      * twice the number of rectangles in the region (a simple optimization...).
 748      */
 749     if ((newReg->rdh.nCount*sizeof(RECT) < 2*newReg->rdh.nRgnSize && (newReg->rdh.nCount > 2)))
 750     {
 751                 if (REGION_NOT_EMPTY(newReg))
 752                 {
 753                     RECT *prev_rects = (PRECT)newReg->Buffer;
 754                     newReg->Buffer = ExAllocatePool( PagedPool, newReg->rdh.nCount*sizeof(RECT) );
 755
 756                     if (! newReg->Buffer)
 757                                 newReg->Buffer = (char*)prev_rects;
 758                         else{
 759                                 newReg->rdh.nRgnSize = newReg->rdh.nCount*sizeof(RECT);
 760                                 RtlCopyMemory( newReg->Buffer, prev_rects, newReg->rdh.nRgnSize );
 761                                 ExFreePool( prev_rects );
 762                         }
 763                 }
 764                 else
 765                 {
 766                     /*
 767                      * No point in doing the extra work involved in an Xrealloc if
 768                      * the region is empty
 769                      */
 770                     newReg->rdh.nRgnSize = sizeof(RECT);
 771                     ExFreePool( newReg->Buffer );
 772                     newReg->Buffer = ExAllocatePool( PagedPool, sizeof(RECT) );
 773                         ASSERT( newReg->Buffer );
 774                 }
 775     }
 776
 777         if( newReg->rdh.nCount == 0 )
 778                 newReg->rdh.iType = NULLREGION;
 779         else
 780                 newReg->rdh.iType = (newReg->rdh.nCount > 1)? COMPLEXREGION : SIMPLEREGION;
 781
 782         ExFreePool( oldRects );
 783     return;
 784 }
 785
 786 /***********************************************************************
 787  *          Region Intersection
 788  ***********************************************************************/
 789
 790
 791 /*!
 792  * Handle an overlapping band for REGION_Intersect.
 793  *
 794  * Results:
 795  *      None.
 796  *
 797  * \note Side Effects:
 798  *      Rectangles may be added to the region.
 799  *
 800  */
 801 static void REGION_IntersectO(ROSRGNDATA *pReg,  RECT *r1, RECT *r1End,
 802                 RECT *r2, RECT *r2End, INT top, INT bottom)
 803
 804 {
 805     INT       left, right;
 806     RECT      *pNextRect;
 807
 808     pNextRect = (PRECT)pReg->Buffer + pReg->rdh.nCount;
 809
 810     while ((r1 != r1End) && (r2 != r2End))
 811     {
 812                 left = max(r1->left, r2->left);
 813                 right = min(r1->right, r2->right);
 814
 815                 /*
 816                  * If there's any overlap between the two rectangles, add that
 817                  * overlap to the new region.
 818                  * There's no need to check for subsumption because the only way
 819                  * such a need could arise is if some region has two rectangles
 820                  * right next to each other. Since that should never happen...
 821                  */
 822                 if (left < right)
 823                 {
 824                     MEMCHECK(pReg, pNextRect, pReg->Buffer);
 825                     pNextRect->left = left;
 826                     pNextRect->top = top;
 827                     pNextRect->right = right;
 828                     pNextRect->bottom = bottom;
 829                     pReg->rdh.nCount += 1;
 830                     pNextRect++;
 831                 }
 832
 833                 /*
 834                  * Need to advance the pointers. Shift the one that extends
 835                  * to the right the least, since the other still has a chance to
 836                  * overlap with that region's next rectangle, if you see what I mean.
 837                  */
 838                 if (r1->right < r2->right)
 839                 {
 840                     r1++;
 841                 }
 842                 else if (r2->right < r1->right)
 843                 {
 844                     r2++;
 845                 }
 846                 else
 847                 {
 848                     r1++;
 849                     r2++;
 850                 }
 851     }
 852     return;
 853 }
 854
 855 /***********************************************************************
 856  *           REGION_IntersectRegion
 857  */
 858 static void REGION_IntersectRegion(ROSRGNDATA *newReg, ROSRGNDATA *reg1,
 859                                    ROSRGNDATA *reg2)
 860 {
 861    /* check for trivial reject */
 862     if ( (!(reg1->rdh.nCount)) || (!(reg2->rdh.nCount))  ||
 863                 (!EXTENTCHECK(&reg1->rdh.rcBound, &reg2->rdh.rcBound)))
 864                 newReg->rdh.nCount = 0;
 865     else
 866                 REGION_RegionOp (newReg, reg1, reg2,
 867                         (voidProcp) REGION_IntersectO, (voidProcp) NULL, (voidProcp) NULL);
 868
 869     /*
 870      * Can't alter newReg's extents before we call miRegionOp because
 871      * it might be one of the source regions and miRegionOp depends
 872      * on the extents of those regions being the same. Besides, this
 873      * way there's no checking against rectangles that will be nuked
 874      * due to coalescing, so we have to examine fewer rectangles.
 875      */
 876
 877     REGION_SetExtents(newReg);
 878 }
 879
 880 /***********************************************************************
 881  *           Region Union
 882  ***********************************************************************/
 883
 884 /*!
 885  *      Handle a non-overlapping band for the union operation. Just
 886  *      Adds the rectangles into the region. Doesn't have to check for
 887  *      subsumption or anything.
 888  *
 889  * Results:
 890  *      None.
 891  *
 892  * \note Side Effects:
 893  *      pReg->numRects is incremented and the final rectangles overwritten
 894  *      with the rectangles we're passed.
 895  *
 896  */
 897 static void REGION_UnionNonO (ROSRGNDATA *pReg, RECT *r, RECT *rEnd,
 898                               INT top, INT bottom)
 899 {
 900     RECT *pNextRect;
 901
 902     pNextRect = (PRECT)pReg->Buffer + pReg->rdh.nCount;
 903
 904     while (r != rEnd)
 905     {
 906                 MEMCHECK(pReg, pNextRect, pReg->Buffer);
 907                 pNextRect->left = r->left;
 908                 pNextRect->top = top;
 909                 pNextRect->right = r->right;
 910                 pNextRect->bottom = bottom;
 911                 pReg->rdh.nCount += 1;
 912                 pNextRect++;
 913                 r++;
 914     }
 915     return;
 916 }
 917
 918 /*!
 919  *      Handle an overlapping band for the union operation. Picks the
 920  *      left-most rectangle each time and merges it into the region.
 921  *
 922  * Results:
 923  *      None.
 924  *
 925  * \note Side Effects:
 926  *      Rectangles are overwritten in pReg->rects and pReg->numRects will
 927  *      be changed.
 928  *
 929  */
 930 static void REGION_UnionO (ROSRGNDATA *pReg, RECT *r1, RECT *r1End,
 931                            RECT *r2, RECT *r2End, INT top, INT bottom)
 932 {
 933     RECT *pNextRect;
 934
 935     pNextRect = (PRECT)pReg->Buffer + pReg->rdh.nCount;
 936
 937 #define MERGERECT(r) \
 938     if ((pReg->rdh.nCount != 0) &&  \
 939                 ((pNextRect-1)->top == top) &&  \
 940                 ((pNextRect-1)->bottom == bottom) &&  \
 941                 ((pNextRect-1)->right >= r->left))  \
 942     {  \
 943                 if ((pNextRect-1)->right < r->right)  \
 944                 {  \
 945                     (pNextRect-1)->right = r->right;  \
 946                 }  \
 947     }  \
 948     else  \
 949     {  \
 950                 MEMCHECK(pReg, pNextRect, pReg->Buffer);  \
 951                 pNextRect->top = top;  \
 952                 pNextRect->bottom = bottom;  \
 953                 pNextRect->left = r->left;  \
 954                 pNextRect->right = r->right;  \
 955                 pReg->rdh.nCount += 1;  \
 956                 pNextRect += 1;  \
 957     }  \
 958     r++;
 959
 960     while ((r1 != r1End) && (r2 != r2End))
 961     {
 962                 if (r1->left < r2->left)
 963                 {
 964                     MERGERECT(r1);
 965                 }
 966                 else
 967                 {
 968                     MERGERECT(r2);
 969                 }
 970     }
 971
 972     if (r1 != r1End)
 973     {
 974                 do
 975                 {
 976                     MERGERECT(r1);
 977                 } while (r1 != r1End);
 978     }
 979     else while (r2 != r2End)
 980     {
 981                 MERGERECT(r2);
 982     }
 983     return;
 984 }
 985
 986 /***********************************************************************
 987  *           REGION_UnionRegion
 988  */
 989 static void REGION_UnionRegion(ROSRGNDATA *newReg, ROSRGNDATA *reg1,
 990                                ROSRGNDATA *reg2)
 991 {
 992     /*  checks all the simple cases */
 993
 994     /*
 995      * Region 1 and 2 are the same or region 1 is empty
 996      */
 997     if ( (reg1 == reg2) || (!(reg1->rdh.nCount)) )
 998     {
 999                 if (newReg != reg2)
1000                     REGION_CopyRegion(newReg, reg2);
1001                 return;
1002     }
1003
1004     /*
1005      * if nothing to union (region 2 empty)
1006      */
1007     if (!(reg2->rdh.nCount))
1008     {
1009                 if (newReg != reg1)
1010                     REGION_CopyRegion(newReg, reg1);
1011                 return;
1012     }
1013
1014     /*
1015      * Region 1 completely subsumes region 2
1016      */
1017     if ((reg1->rdh.nCount == 1) &&
1018                 (reg1->rdh.rcBound.left <= reg2->rdh.rcBound.left) &&
1019                 (reg1->rdh.rcBound.top <= reg2->rdh.rcBound.top) &&
1020                 (reg1->rdh.rcBound.right >= reg2->rdh.rcBound.right) &&
1021                 (reg1->rdh.rcBound.bottom >= reg2->rdh.rcBound.bottom))
1022     {
1023                 if (newReg != reg1)
1024                     REGION_CopyRegion(newReg, reg1);
1025                 return;
1026     }
1027
1028     /*
1029      * Region 2 completely subsumes region 1
1030      */
1031     if ((reg2->rdh.nCount == 1) &&
1032                 (reg2->rdh.rcBound.left <= reg1->rdh.rcBound.left) &&
1033                 (reg2->rdh.rcBound.top <= reg1->rdh.rcBound.top) &&
1034                 (reg2->rdh.rcBound.right >= reg1->rdh.rcBound.right) &&
1035                 (reg2->rdh.rcBound.bottom >= reg1->rdh.rcBound.bottom))
1036     {
1037                 if (newReg != reg2)
1038                     REGION_CopyRegion(newReg, reg2);
1039                 return;
1040     }
1041
1042     REGION_RegionOp (newReg, reg1, reg2, (voidProcp) REGION_UnionO,
1043                 (voidProcp) REGION_UnionNonO, (voidProcp) REGION_UnionNonO);
1044     newReg->rdh.rcBound.left = min(reg1->rdh.rcBound.left, reg2->rdh.rcBound.left);
1045     newReg->rdh.rcBound.top = min(reg1->rdh.rcBound.top, reg2->rdh.rcBound.top);
1046     newReg->rdh.rcBound.right = max(reg1->rdh.rcBound.right, reg2->rdh.rcBound.right);
1047     newReg->rdh.rcBound.bottom = max(reg1->rdh.rcBound.bottom, reg2->rdh.rcBound.bottom);
1048 }
1049
1050 /***********************************************************************
1051  *           Region Subtraction
1052  ***********************************************************************/
1053
1054 /*!
1055  *      Deal with non-overlapping band for subtraction. Any parts from
1056  *      region 2 we discard. Anything from region 1 we add to the region.
1057  *
1058  * Results:
1059  *      None.
1060  *
1061  * \note Side Effects:
1062  *      pReg may be affected.
1063  *
1064  */
1065 static void REGION_SubtractNonO1 (ROSRGNDATA *pReg, RECT *r, RECT *rEnd,
1066                 INT top, INT bottom)
1067 {
1068     RECT *pNextRect;
1069
1070     pNextRect = (PRECT)pReg->Buffer + pReg->rdh.nCount;
1071
1072     while (r != rEnd)
1073     {
1074                 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1075                 pNextRect->left = r->left;
1076                 pNextRect->top = top;
1077                 pNextRect->right = r->right;
1078                 pNextRect->bottom = bottom;
1079                 pReg->rdh.nCount += 1;
1080                 pNextRect++;
1081                 r++;
1082     }
1083     return;
1084 }
1085
1086
1087 /*!
1088  *      Overlapping band subtraction. x1 is the left-most point not yet
1089  *      checked.
1090  *
1091  * Results:
1092  *      None.
1093  *
1094  * \note Side Effects:
1095  *      pReg may have rectangles added to it.
1096  *
1097  */
1098 static void REGION_SubtractO (ROSRGNDATA *pReg, RECT *r1, RECT *r1End,
1099                 RECT *r2, RECT *r2End, INT top, INT bottom)
1100 {
1101     RECT *pNextRect;
1102     INT left;
1103
1104     left = r1->left;
1105     pNextRect = (PRECT)pReg->Buffer + pReg->rdh.nCount;
1106
1107     while ((r1 != r1End) && (r2 != r2End))
1108     {
1109                 if (r2->right <= left)
1110                 {
1111                     /*
1112                      * Subtrahend missed the boat: go to next subtrahend.
1113                      */
1114                     r2++;
1115                 }
1116                 else if (r2->left <= left)
1117                 {
1118                     /*
1119                      * Subtrahend preceeds minuend: nuke left edge of minuend.
1120                      */
1121                     left = r2->right;
1122                     if (left >= r1->right)
1123                     {
1124                         /*
1125                          * Minuend completely covered: advance to next minuend and
1126                          * reset left fence to edge of new minuend.
1127                          */
1128                         r1++;
1129                         if (r1 != r1End)
1130                             left = r1->left;
1131                     }
1132                     else
1133                     {
1134                         /*
1135                          * Subtrahend now used up since it doesn't extend beyond
1136                          * minuend
1137                          */
1138                         r2++;
1139                     }
1140                 }
1141                 else if (r2->left < r1->right)
1142                 {
1143                     /*
1144                      * Left part of subtrahend covers part of minuend: add uncovered
1145                      * part of minuend to region and skip to next subtrahend.
1146                      */
1147                     MEMCHECK(pReg, pNextRect, pReg->Buffer);
1148                     pNextRect->left = left;
1149                     pNextRect->top = top;
1150                     pNextRect->right = r2->left;
1151                     pNextRect->bottom = bottom;
1152                     pReg->rdh.nCount += 1;
1153                     pNextRect++;
1154                     left = r2->right;
1155                     if (left >= r1->right)
1156                     {
1157                         /*
1158                          * Minuend used up: advance to new...
1159                          */
1160                         r1++;
1161                         if (r1 != r1End)
1162                             left = r1->left;
1163                     }
1164                     else
1165                     {
1166                         /*
1167                          * Subtrahend used up
1168                          */
1169                         r2++;
1170                     }
1171                 }
1172                 else
1173                 {
1174                     /*
1175                      * Minuend used up: add any remaining piece before advancing.
1176                      */
1177                     if (r1->right > left)
1178                     {
1179                                 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1180                                 pNextRect->left = left;
1181                                 pNextRect->top = top;
1182                                 pNextRect->right = r1->right;
1183                                 pNextRect->bottom = bottom;
1184                                 pReg->rdh.nCount += 1;
1185                                 pNextRect++;
1186                     }
1187                     r1++;
1188                     left = r1->left;
1189                 }
1190     }
1191
1192     /*
1193      * Add remaining minuend rectangles to region.
1194      */
1195     while (r1 != r1End)
1196     {
1197                 MEMCHECK(pReg, pNextRect, pReg->Buffer);
1198                 pNextRect->left = left;
1199                 pNextRect->top = top;
1200                 pNextRect->right = r1->right;
1201                 pNextRect->bottom = bottom;
1202                 pReg->rdh.nCount += 1;
1203                 pNextRect++;
1204                 r1++;
1205                 if (r1 != r1End)
1206                 {
1207                     left = r1->left;
1208                 }
1209     }
1210     return;
1211 }
1212
1213 /*!
1214  *      Subtract regS from regM and leave the result in regD.
1215  *      S stands for subtrahend, M for minuend and D for difference.
1216  *
1217  * Results:
1218  *      TRUE.
1219  *
1220  * \note Side Effects:
1221  *      regD is overwritten.
1222  *
1223  */
1224 static void REGION_SubtractRegion(ROSRGNDATA *regD, ROSRGNDATA *regM,
1225                                                        ROSRGNDATA *regS )
1226 {
1227    /* check for trivial reject */
1228     if ( (!(regM->rdh.nCount)) || (!(regS->rdh.nCount))  ||
1229                 (!EXTENTCHECK(&regM->rdh.rcBound, &regS->rdh.rcBound)) )
1230     {
1231                 REGION_CopyRegion(regD, regM);
1232                 return;
1233     }
1234
1235     REGION_RegionOp (regD, regM, regS, (voidProcp) REGION_SubtractO,
1236                 (voidProcp) REGION_SubtractNonO1, (voidProcp) NULL);
1237
1238     /*
1239      * Can't alter newReg's extents before we call miRegionOp because
1240      * it might be one of the source regions and miRegionOp depends
1241      * on the extents of those regions being the unaltered. Besides, this
1242      * way there's no checking against rectangles that will be nuked
1243      * due to coalescing, so we have to examine fewer rectangles.
1244      */
1245     REGION_SetExtents (regD);
1246 }
1247
1248 /***********************************************************************
1249  *           REGION_XorRegion
1250  */
1251 static void REGION_XorRegion(ROSRGNDATA *dr, ROSRGNDATA *sra,
1252                                                         ROSRGNDATA *srb)
1253 {
1254         HRGN htra, htrb;
1255     ROSRGNDATA *tra, *trb;
1256
1257     if ((! (htra = RGNDATA_AllocRgn(sra->rdh.nCount + 1))) ||
1258                 (! (htrb = RGNDATA_AllocRgn(srb->rdh.nCount + 1))))
1259         return;
1260         tra = RGNDATA_LockRgn( htra );
1261         if( !tra ){
1262                 W32kDeleteObject( htra );
1263                 W32kDeleteObject( htrb );
1264                 return;
1265         }
1266
1267         trb = RGNDATA_LockRgn( htrb );
1268         if( !trb ){
1269                 RGNDATA_UnlockRgn( htra );
1270                 W32kDeleteObject( htra );
1271                 W32kDeleteObject( htrb );
1272                 return;
1273         }
1274
1275     REGION_SubtractRegion(tra,sra,srb);
1276     REGION_SubtractRegion(trb,srb,sra);
1277     REGION_UnionRegion(dr,tra,trb);
1278         RGNDATA_UnlockRgn( htra );
1279         RGNDATA_UnlockRgn( htrb );
1280
1281     W32kDeleteObject( htra );
1282     W32kDeleteObject( htrb );
1283     return;
1284 }
1285
1286
1287 /*!
1288  * Adds a rectangle to a REGION
1289  */
1290 static void REGION_UnionRectWithRegion(const RECT *rect, ROSRGNDATA *rgn)
1291 {
1292     ROSRGNDATA region;
1293
1294     region.Buffer = (char*)(&(region.rdh.rcBound));
1295     region.rdh.nCount = 1;
1296     region.rdh.nRgnSize = sizeof( RECT );
1297     region.rdh.rcBound = *rect;
1298     REGION_UnionRegion(rgn, rgn, &region);
1299 }
1300
1301
1302 BOOL REGION_LPTODP(HDC hdc, HRGN hDest, HRGN hSrc)
1303 {
1304   RECT *pCurRect, *pEndRect;
1305   PROSRGNDATA srcObj = NULL;
1306   PROSRGNDATA destObj = NULL;
1307
1308   DC * dc = DC_HandleToPtr(hdc);
1309   RECT tmpRect;
1310   BOOL ret = FALSE;
1311
1312   if(!dc)
1313     return ret;
1314
1315   if(dc->w.MapMode == MM_TEXT) // Requires only a translation
1316   {
1317     if(W32kCombineRgn(hDest, hSrc, 0, RGN_COPY) == ERROR)
1318           goto done;
1319
1320     W32kOffsetRgn(hDest, dc->vportOrgX - dc->wndOrgX, dc->vportOrgY - dc->wndOrgY);
1321     ret = TRUE;
1322     goto done;
1323   }
1324
1325   if(!( srcObj = (PROSRGNDATA) RGNDATA_LockRgn( hSrc ) ))
1326         goto done;
1327   if(!( destObj = (PROSRGNDATA) RGNDATA_LockRgn( hDest ) ))
1328   {
1329     RGNDATA_UnlockRgn( hSrc );
1330     goto done;
1331   }
1332   EMPTY_REGION(destObj);
1333
1334   pEndRect = (PRECT)srcObj->Buffer + srcObj->rdh.nCount;
1335   for(pCurRect = (PRECT)srcObj->Buffer; pCurRect < pEndRect; pCurRect++)
1336   {
1337     tmpRect = *pCurRect;
1338     tmpRect.left = XLPTODP(dc, tmpRect.left);
1339     tmpRect.top = YLPTODP(dc, tmpRect.top);
1340     tmpRect.right = XLPTODP(dc, tmpRect.right);
1341     tmpRect.bottom = YLPTODP(dc, tmpRect.bottom);
1342
1343     if(tmpRect.left > tmpRect.right)
1344       { INT tmp = tmpRect.left; tmpRect.left = tmpRect.right; tmpRect.right = tmp; }
1345     if(tmpRect.top > tmpRect.bottom)
1346       { INT tmp = tmpRect.top; tmpRect.top = tmpRect.bottom; tmpRect.bottom = tmp; }
1347
1348     REGION_UnionRectWithRegion(&tmpRect, destObj);
1349   }
1350   ret = TRUE;
1351
1352   RGNDATA_UnlockRgn( hSrc );
1353   RGNDATA_UnlockRgn( hDest );
1354
1355 done:
1356   DC_ReleasePtr( hdc );
1357   return ret;
1358 }
1359
1360 HRGN RGNDATA_AllocRgn(INT n)
1361 {
1362   HRGN hReg;
1363   PROSRGNDATA pReg;
1364   BOOL bRet;
1365
1366   if((hReg = (HRGN)GDIOBJ_AllocObj(sizeof(ROSRGNDATA), GO_REGION_MAGIC))){
1367         if( (pReg = GDIOBJ_LockObj( hReg, GO_REGION_MAGIC )) ){
1368
1369       if ((pReg->Buffer = ExAllocatePool(PagedPool, n * sizeof(RECT)))){
1370         EMPTY_REGION(pReg);
1371         pReg->rdh.dwSize = sizeof(RGNDATAHEADER);
1372         pReg->rdh.nCount = n;
1373         pReg->rdh.nRgnSize = n*sizeof(RECT);
1374
1375         bRet = GDIOBJ_UnlockObj( hReg, GO_REGION_MAGIC );
1376         ASSERT(bRet);
1377
1378         return hReg;
1379           }
1380
1381         }
1382         else
1383                 GDIOBJ_FreeObj( hReg, GO_REGION_MAGIC, GDIOBJFLAG_DEFAULT );
1384   }
1385   return NULL;
1386 }
1387
1388 BOOL RGNDATA_InternalDelete( PROSRGNDATA pRgn )
1389 {
1390   ASSERT(pRgn);
1391   if(pRgn->Buffer)
1392     ExFreePool(pRgn->Buffer);
1393   return TRUE;
1394 }
1395
1396 // W32k Exported Functions
1397 INT
1398 STDCALL
1399 W32kCombineRgn(HRGN  hDest,
1400                     HRGN  hSrc1,
1401                     HRGN  hSrc2,
1402                     INT  CombineMode)
1403 {
1404   INT result = ERROR;
1405   GDIMULTILOCK Lock[3] = {{hDest, 0, GO_REGION_MAGIC}, {hSrc1, 0, GO_REGION_MAGIC}, {hSrc2, 0, GO_REGION_MAGIC}};
1406   PROSRGNDATA destRgn, src1Rgn, src2Rgn;
1407
1408   GDIOBJ_LockMultipleObj( &Lock, 3 );
1409
1410   destRgn = (PROSRGNDATA) Lock[0].pObj;
1411   src1Rgn = (PROSRGNDATA) Lock[1].pObj;
1412   src2Rgn = (PROSRGNDATA) Lock[2].pObj;
1413
1414   if( destRgn ){
1415         if( src1Rgn ){
1416                 if (CombineMode == RGN_COPY)
1417                 {
1418                   if( !REGION_CopyRegion(destRgn, src1Rgn) )
1419                                 return ERROR;
1420                   result = destRgn->rdh.iType;
1421                 }
1422                 else
1423                 {
1424                   if( src2Rgn ){
1425                           switch (CombineMode)
1426                           {
1427                             case RGN_AND:
1428                               REGION_IntersectRegion(destRgn, src1Rgn, src2Rgn);
1429                               break;
1430                             case RGN_OR:
1431                               REGION_UnionRegion(destRgn, src1Rgn, src2Rgn);
1432                               break;
1433                             case RGN_XOR:
1434                               REGION_XorRegion(destRgn, src1Rgn, src2Rgn);
1435                               break;
1436                             case RGN_DIFF:
1437                               REGION_SubtractRegion(destRgn, src1Rgn, src2Rgn);
1438                               break;
1439                           }
1440                           result = destRgn->rdh.iType;
1441                   }
1442                 }
1443         }
1444   }
1445   else{
1446       DPRINT("W32kCombineRgn: hDest unavailable\n");
1447           result = ERROR;
1448   }
1449   GDIOBJ_UnlockMultipleObj( &Lock, 3 );
1450   return result;
1451 }
1452
1453 HRGN
1454 STDCALL
1455 W32kCreateEllipticRgn(INT  LeftRect,
1456                             INT  TopRect,
1457                             INT  RightRect,
1458                             INT  BottomRect)
1459 {
1460   UNIMPLEMENTED;
1461 }
1462
1463 HRGN
1464 STDCALL
1465 W32kCreateEllipticRgnIndirect(CONST PRECT  rc)
1466 {
1467   UNIMPLEMENTED;
1468 }
1469
1470 HRGN
1471 STDCALL
1472 W32kCreatePolygonRgn(CONST PPOINT  pt,
1473                            INT  Count,
1474                            INT  PolyFillMode)
1475 {
1476   UNIMPLEMENTED;
1477 }
1478
1479 HRGN
1480 STDCALL
1481 W32kCreatePolyPolygonRgn(CONST PPOINT  pt,
1482                                CONST PINT  PolyCounts,
1483                                INT  Count,
1484                                INT  PolyFillMode)
1485 {
1486   UNIMPLEMENTED;
1487 }
1488
1489 HRGN
1490 STDCALL
1491 W32kCreateRectRgn(INT  LeftRect,
1492                         INT  TopRect,
1493                         INT  RightRect,
1494                         INT  BottomRect)
1495 {
1496   HRGN hRgn;
1497   PROSRGNDATA pRgnData;
1498   PRECT pRect;
1499
1500   // Allocate region data structure with space for 1 RECT
1501   if( ( hRgn = RGNDATA_AllocRgn(1) ) ){
1502         if( ( pRgnData = RGNDATA_LockRgn( hRgn ) ) ){
1503         pRect = (PRECT)pRgnData->Buffer;
1504         ASSERT(pRect);
1505
1506         // Fill in the region data header
1507         pRgnData->rdh.iType = SIMPLEREGION;
1508         W32kSetRect(&(pRgnData->rdh.rcBound), LeftRect, TopRect, RightRect, BottomRect);
1509
1510         // use W32kCopyRect when implemented
1511         W32kSetRect(pRect, LeftRect, TopRect, RightRect, BottomRect);
1512                 RGNDATA_UnlockRgn( hRgn );
1513
1514         return hRgn;
1515         }
1516         W32kDeleteObject( hRgn );
1517   }
1518   DPRINT("W32kCreateRectRgn: can't allocate region\n");
1519   return NULL;
1520 }
1521
1522 HRGN STDCALL
1523 W32kCreateRectRgnIndirect(CONST PRECT rc)
1524 {
1525   RECT SafeRc;
1526   NTSTATUS Status;
1527
1528   Status = MmCopyFromCaller(&SafeRc, rc, sizeof(RECT));
1529   if (!NT_SUCCESS(Status))
1530     {
1531       return(NULL);
1532     }
1533   return(UnsafeW32kCreateRectRgnIndirect(&SafeRc));
1534 }
1535
1536 HRGN STDCALL
1537 UnsafeW32kCreateRectRgnIndirect(CONST PRECT  rc)
1538 {
1539   return(W32kCreateRectRgn(rc->left, rc->top, rc->right, rc->bottom));
1540 }
1541
1542 HRGN
1543 STDCALL
1544 W32kCreateRoundRectRgn(INT  LeftRect,
1545                              INT  TopRect,
1546                              INT  RightRect,
1547                              INT  BottomRect,
1548                              INT  WidthEllipse,
1549                              INT  HeightEllipse)
1550 {
1551   UNIMPLEMENTED;
1552 }
1553
1554 BOOL
1555 STDCALL
1556 W32kEqualRgn(HRGN  hSrcRgn1,
1557                    HRGN  hSrcRgn2)
1558 {
1559   PROSRGNDATA rgn1, rgn2;
1560   PRECT tRect1, tRect2;
1561   int i;
1562   BOOL bRet = FALSE;
1563
1564   if( !(rgn1 = RGNDATA_LockRgn(hSrcRgn1)))
1565         return ERROR;
1566
1567   if( !(rgn2 = RGNDATA_LockRgn(hSrcRgn2))){
1568         RGNDATA_UnlockRgn( hSrcRgn1 );
1569         return ERROR;
1570   }
1571
1572   if(rgn1->rdh.nCount != rgn2->rdh.nCount ||
1573         rgn1->rdh.nCount == 0 ||
1574         rgn1->rdh.rcBound.left   != rgn2->rdh.rcBound.left ||
1575         rgn1->rdh.rcBound.right  != rgn2->rdh.rcBound.right ||
1576         rgn1->rdh.rcBound.top    != rgn2->rdh.rcBound.top ||
1577         rgn1->rdh.rcBound.bottom != rgn2->rdh.rcBound.bottom)
1578         goto exit;
1579
1580   tRect1 = (PRECT)rgn1->Buffer;
1581   tRect2 = (PRECT)rgn2->Buffer;
1582
1583   if( !tRect1 || !tRect2 )
1584         goto exit;
1585
1586   for(i=0; i < rgn1->rdh.nCount; i++)
1587   {
1588     if(tRect1[i].left   != tRect2[i].left ||
1589         tRect1[i].right  != tRect2[i].right ||
1590         tRect1[i].top    != tRect2[i].top ||
1591         tRect1[i].bottom != tRect2[i].bottom)
1592            goto exit;;
1593   }
1594   bRet = TRUE;
1595
1596 exit:
1597   RGNDATA_UnlockRgn( hSrcRgn1 );
1598   RGNDATA_UnlockRgn( hSrcRgn2 );
1599   return bRet;
1600 }
1601
1602 HRGN
1603 STDCALL
1604 W32kExtCreateRegion(CONST PXFORM  Xform,
1605                           DWORD  Count,
1606                           CONST PROSRGNDATA  RgnData)
1607 {
1608   HRGN hRgn;
1609
1610   // FIXME: Apply Xform transformation to the regional data
1611   if(Xform != NULL) {
1612
1613   }
1614
1615   return hRgn;
1616 }
1617
1618 BOOL
1619 STDCALL
1620 W32kFillRgn(HDC  hDC,
1621                   HRGN  hRgn,
1622                   HBRUSH  hBrush)
1623 {
1624   UNIMPLEMENTED;
1625 }
1626
1627 BOOL
1628 STDCALL
1629 W32kFrameRgn(HDC  hDC,
1630                    HRGN  hRgn,
1631                    HBRUSH  hBrush,
1632                    INT  Width,
1633                    INT  Height)
1634 {
1635   UNIMPLEMENTED;
1636 }
1637
1638 INT STDCALL
1639 UnsafeW32kGetRgnBox(HRGN  hRgn,
1640                     LPRECT  pRect)
1641 {
1642   PROSRGNDATA rgn = RGNDATA_LockRgn(hRgn);
1643   DWORD ret;
1644
1645   if (rgn)
1646     {
1647       *pRect = rgn->rdh.rcBound;
1648       ret = rgn->rdh.iType;
1649       RGNDATA_UnlockRgn( hRgn );
1650
1651       return ret;
1652     }
1653   return 0; //if invalid region return zero
1654 }
1655
1656
1657 INT STDCALL
1658 W32kGetRgnBox(HRGN  hRgn,
1659               LPRECT  pRect)
1660 {
1661   PROSRGNDATA rgn = RGNDATA_LockRgn(hRgn);
1662   DWORD ret;
1663
1664   if (rgn)
1665     {
1666       RECT SafeRect;
1667       SafeRect.left = rgn->rdh.rcBound.left;
1668       SafeRect.top = rgn->rdh.rcBound.top;
1669       SafeRect.right = rgn->rdh.rcBound.right;
1670       SafeRect.bottom = rgn->rdh.rcBound.bottom;
1671       ret = rgn->rdh.iType;
1672       RGNDATA_UnlockRgn( hRgn );
1673
1674       if(!NT_SUCCESS(MmCopyToCaller(pRect, &SafeRect, sizeof(RECT))))
1675         return 0;
1676
1677       return ret;
1678     }
1679   return 0; //if invalid region return zero
1680 }
1681
1682 BOOL
1683 STDCALL
1684 W32kInvertRgn(HDC  hDC,
1685                     HRGN  hRgn)
1686 {
1687   UNIMPLEMENTED;
1688 }
1689
1690 INT
1691 STDCALL
1692 W32kOffsetRgn(HRGN  hRgn,
1693                    INT  XOffset,
1694                    INT  YOffset)
1695 {
1696   PROSRGNDATA rgn = RGNDATA_LockRgn(hRgn);
1697   INT ret;
1698
1699   DPRINT("W32kOffsetRgn: hRgn %d Xoffs %d Yoffs %d rgn %x\n", hRgn, XOffset, YOffset, rgn );
1700
1701   if( !rgn ){
1702           DPRINT("W32kOffsetRgn: hRgn error\n");
1703           return ERROR;
1704   }
1705
1706   if(XOffset || YOffset) {
1707     int nbox = rgn->rdh.nCount;
1708         PRECT pbox = (PRECT)rgn->Buffer;
1709
1710     if(nbox && pbox) {
1711       while(nbox--) {
1712         pbox->left += XOffset;
1713         pbox->right += XOffset;
1714         pbox->top += YOffset;
1715         pbox->bottom += YOffset;
1716         pbox++;
1717       }
1718       rgn->rdh.rcBound.left += XOffset;
1719       rgn->rdh.rcBound.right += XOffset;
1720       rgn->rdh.rcBound.top += YOffset;
1721       rgn->rdh.rcBound.bottom += YOffset;
1722     }
1723   }
1724   ret = rgn->rdh.iType;
1725   RGNDATA_UnlockRgn( hRgn );
1726   return ret;
1727 }
1728
1729 BOOL
1730 STDCALL
1731 W32kPaintRgn(HDC  hDC,
1732                    HRGN  hRgn)
1733 {
1734   RECT box;
1735   HRGN tmpVisRgn, prevVisRgn;
1736   DC *dc = DC_HandleToPtr(hDC);
1737   PROSRGNDATA visrgn;
1738   CLIPOBJ* ClipRegion;
1739   BOOL bRet = FALSE;
1740   PBRUSHOBJ pBrush;
1741   POINTL BrushOrigin;
1742   SURFOBJ       *SurfObj;
1743
1744   if( !dc )
1745         return FALSE;
1746
1747   if(!(tmpVisRgn = W32kCreateRectRgn(0, 0, 0, 0))){
1748         DC_ReleasePtr( hDC );
1749         return FALSE;
1750   }
1751
1752 /* ei enable later
1753   // Transform region into device co-ords
1754   if(!REGION_LPTODP(hDC, tmpVisRgn, hRgn) || W32kOffsetRgn(tmpVisRgn, dc->w.DCOrgX, dc->w.DCOrgY) == ERROR) {
1755     W32kDeleteObject( tmpVisRgn );
1756         DC_ReleasePtr( hDC );
1757     return FALSE;
1758   }
1759 */
1760   /* enable when clipping is implemented
1761   W32kCombineRgn(tmpVisRgn, tmpVisRgn, dc->w.hGCClipRgn, RGN_AND);
1762   */
1763
1764   //visrgn = RGNDATA_LockRgn(tmpVisRgn);
1765   visrgn = RGNDATA_LockRgn(hRgn);
1766
1767   ClipRegion = IntEngCreateClipRegion( visrgn->rdh.nCount, visrgn->Buffer, visrgn->rdh.rcBound );
1768   ASSERT( ClipRegion );
1769   pBrush = BRUSHOBJ_LockBrush(dc->w.hBrush);
1770   ASSERT(pBrush);
1771   BrushOrigin.x = dc->w.brushOrgX;
1772   BrushOrigin.y = dc->w.brushOrgY;
1773   SurfObj = (SURFOBJ*)AccessUserObject(dc->Surface);
1774
1775   bRet = IntEngPaint(SurfObj,
1776          ClipRegion,
1777          pBrush,
1778          &BrushOrigin,
1779          0xFFFF);//don't know what to put here
1780
1781   RGNDATA_UnlockRgn( tmpVisRgn );
1782
1783   // Fill the region
1784   DC_ReleasePtr( hDC );
1785   return TRUE;
1786 }
1787
1788 BOOL
1789 STDCALL
1790 W32kPtInRegion(HRGN  hRgn,
1791                      INT  X,
1792                      INT  Y)
1793 {
1794   PROSRGNDATA rgn;
1795   int i;
1796
1797   if( (rgn = RGNDATA_LockRgn(hRgn) ) )
1798           return FALSE;
1799
1800   if(rgn->rdh.nCount > 0 && INRECT(rgn->rdh.rcBound, X, Y)){
1801     for(i = 0; i < rgn->rdh.nCount; i++) {
1802       if(INRECT(*(PRECT)&rgn->Buffer[i], X, Y)){
1803                 RGNDATA_UnlockRgn(hRgn);
1804                 return TRUE;
1805           }
1806     }
1807   }
1808   RGNDATA_UnlockRgn(hRgn);
1809   return FALSE;
1810 }
1811
1812 BOOL
1813 STDCALL
1814 W32kRectInRegion(HRGN  hRgn,
1815                        CONST LPRECT  unsaferc)
1816 {
1817   PROSRGNDATA rgn;
1818   PRECT pCurRect, pRectEnd;
1819   PRECT rc;
1820   BOOL bRet = FALSE;
1821
1822   if( !NT_SUCCESS( MmCopyFromCaller( rc, unsaferc, sizeof( RECT ) ) ) ){
1823         DPRINT("W32kRectInRegion: bogus rc\n");
1824         return ERROR;
1825   }
1826
1827   if( !( rgn  = RGNDATA_LockRgn(hRgn) ) )
1828         return ERROR;
1829
1830   // this is (just) a useful optimization
1831   if((rgn->rdh.nCount > 0) && EXTENTCHECK(&rgn->rdh.rcBound, rc))
1832   {
1833     for (pCurRect = (PRECT)rgn->Buffer, pRectEnd = pCurRect + rgn->rdh.nCount; pCurRect < pRectEnd; pCurRect++)
1834     {
1835       if (pCurRect->bottom <= rc->top) continue; // not far enough down yet
1836       if (pCurRect->top >= rc->bottom) break;    // too far down
1837       if (pCurRect->right <= rc->left) continue; // not far enough over yet
1838       if (pCurRect->left >= rc->right) continue;
1839       bRet = TRUE;
1840       break;
1841     }
1842   }
1843   RGNDATA_UnlockRgn(hRgn);
1844   return bRet;
1845 }
1846
1847 BOOL
1848 STDCALL
1849 W32kSetRectRgn(HRGN  hRgn,
1850                      INT  LeftRect,
1851                      INT  TopRect,
1852                      INT  RightRect,
1853                      INT  BottomRect)
1854 {
1855   PROSRGNDATA rgn;
1856   PRECT firstRect;
1857
1858
1859
1860   if( !( rgn = RGNDATA_LockRgn(hRgn) ) )
1861           return 0; //per documentation
1862
1863   if (LeftRect > RightRect) { INT tmp = LeftRect; LeftRect = RightRect; RightRect = tmp; }
1864   if (TopRect > BottomRect) { INT tmp = TopRect; TopRect = BottomRect; BottomRect = tmp; }
1865
1866   if((LeftRect != RightRect) && (TopRect != BottomRect))
1867   {
1868     firstRect = (PRECT)rgn->Buffer;
1869         ASSERT( firstRect );
1870         firstRect->left = rgn->rdh.rcBound.left = LeftRect;
1871     firstRect->top = rgn->rdh.rcBound.top = TopRect;
1872     firstRect->right = rgn->rdh.rcBound.right = RightRect;
1873     firstRect->bottom = rgn->rdh.rcBound.bottom = BottomRect;
1874     rgn->rdh.nCount = 1;
1875     rgn->rdh.iType = SIMPLEREGION;
1876   } else
1877     EMPTY_REGION(rgn);
1878
1879   RGNDATA_UnlockRgn( hRgn );
1880   return TRUE;
1881 }
1882
1883 HRGN STDCALL
1884 W32kUnionRectWithRgn(HRGN hDest, const RECT* unsafeRect)
1885 {
1886         PRECT pRect;
1887         PROSRGNDATA pRgn;
1888
1889         if( !NT_SUCCESS( MmCopyFromCaller( pRect, unsafeRect, sizeof( RECT ) ) ) )
1890                 return NULL;
1891
1892         if( !(pRgn = RGNDATA_LockRgn( hDest ) ) )
1893                 return NULL;
1894
1895         REGION_UnionRectWithRegion( pRect, pRgn );
1896         RGNDATA_UnlockRgn( hDest );
1897         return hDest;
1898 }
1899
1900 /*!
1901  * MSDN: GetRegionData, Return Values:
1902  *
1903  * "If the function succeeds and dwCount specifies an adequate number of bytes,
1904  * the return value is always dwCount. If dwCount is too small or the function
1905  * fails, the return value is 0. If lpRgnData is NULL, the return value is the
1906  * required number of bytes.
1907  *
1908  * If the function fails, the return value is zero."
1909  */
1910 DWORD STDCALL W32kGetRegionData(HRGN hrgn, DWORD count, LPRGNDATA rgndata)
1911 {
1912     DWORD size;
1913     PROSRGNDATA obj = RGNDATA_LockRgn( hrgn );
1914
1915     if(!obj)
1916                 return 0;
1917
1918     size = obj->rdh.nCount * sizeof(RECT);
1919     if(count < (size + sizeof(RGNDATAHEADER)) || rgndata == NULL)
1920     {
1921         RGNDATA_UnlockRgn( hrgn );
1922                 if (rgndata) /* buffer is too small, signal it by return 0 */
1923                     return 0;
1924                 else            /* user requested buffer size with rgndata NULL */
1925                     return size + sizeof(RGNDATAHEADER);
1926     }
1927
1928         //first we copy the header then we copy buffer
1929         if( !NT_SUCCESS( MmCopyToCaller( rgndata, obj, sizeof( RGNDATAHEADER )))){
1930                 RGNDATA_UnlockRgn( hrgn );
1931                 return 0;
1932         }
1933         if( !NT_SUCCESS( MmCopyToCaller( (char*)rgndata+sizeof( RGNDATAHEADER ), obj->Buffer, size ))){
1934                 RGNDATA_UnlockRgn( hrgn );
1935                 return 0;
1936         }
1937
1938     RGNDATA_UnlockRgn( hrgn );
1939     return size + sizeof(RGNDATAHEADER);
1940 }
1941