server/region.c

   1 /*
   2  * Server-side region objects. Based on the X11 implementation.
   3  *
   4  * Copyright 1993, 1994, 1995, 2004 Alexandre Julliard
   5  * Modifications and additions: Copyright 1998 Huw Davies
   6  *                                        1999 Alex Korobka
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  *
  22  * Note:
  23  *  This is a simplified version of the code, without all the explanations.
  24  *  Check the equivalent GDI code to make sense of it.
  25  */
  26
  27 /************************************************************************
  28
  29 Copyright (c) 1987, 1988  X Consortium
  30
  31 Permission is hereby granted, free of charge, to any person obtaining a copy
  32 of this software and associated documentation files (the "Software"), to deal
  33 in the Software without restriction, including without limitation the rights
  34 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  35 copies of the Software, and to permit persons to whom the Software is
  36 furnished to do so, subject to the following conditions:
  37
  38 The above copyright notice and this permission notice shall be included in
  39 all copies or substantial portions of the Software.
  40
  41 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  42 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  43 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  44 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  45 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  46 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  47
  48 Except as contained in this notice, the name of the X Consortium shall not be
  49 used in advertising or otherwise to promote the sale, use or other dealings
  50 in this Software without prior written authorization from the X Consortium.
  51
  52
  53 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
  54
  55                         All Rights Reserved
  56
  57 Permission to use, copy, modify, and distribute this software and its
  58 documentation for any purpose and without fee is hereby granted,
  59 provided that the above copyright notice appear in all copies and that
  60 both that copyright notice and this permission notice appear in
  61 supporting documentation, and that the name of Digital not be
  62 used in advertising or publicity pertaining to distribution of the
  63 software without specific, written prior permission.
  64
  65 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  66 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  67 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  68 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  69 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  70 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  71 SOFTWARE.
  72
  73 ************************************************************************/
  74
  75 #include <stdarg.h>
  76 #include <stdlib.h>
  77 #include <string.h>
  78 #include "ntstatus.h"
  79 #define WIN32_NO_STATUS
  80 #include "winternl.h"
  81 #include "request.h"
  82 #include "user.h"
  83
  84 struct region
  85 {
  86     int size;
  87     int num_rects;
  88     rectangle_t *rects;
  89     rectangle_t extents;
  90 };
  91
  92
  93 #define RGN_DEFAULT_RECTS 2
  94
  95 #define EXTENTCHECK(r1, r2) \
  96     ((r1)->right > (r2)->left && \
  97     (r1)->left < (r2)->right && \
  98     (r1)->bottom > (r2)->top && \
  99     (r1)->top < (r2)->bottom)
 100
 101 typedef int (*overlap_func_t)( struct region *reg, const rectangle_t *r1, const rectangle_t *r1End,
 102                                const rectangle_t *r2, const rectangle_t *r2End, int top, int bottom );
 103 typedef int (*non_overlap_func_t)( struct region *reg, const rectangle_t *r,
 104                                    const rectangle_t *rEnd, int top, int bottom );
 105
 106 static const rectangle_t empty_rect;  /* all-zero rectangle for empty regions */
 107
 108 /* add a rectangle to a region */
 109 static inline rectangle_t *add_rect( struct region *reg )
 110 {
 111     if (reg->num_rects >= reg->size - 1)
 112     {
 113         rectangle_t *new_rect = realloc( reg->rects, 2 * sizeof(rectangle_t) * reg->size );
 114         if (!new_rect)
 115         {
 116             set_error( STATUS_NO_MEMORY );
 117             return NULL;
 118         }
 119         reg->rects = new_rect;
 120         reg->size *= 2;
 121     }
 122     return reg->rects + reg->num_rects++;
 123 }
 124
 125 /* make sure all the rectangles are valid and that the region is properly y-x-banded */
 126 static inline int validate_rectangles( const rectangle_t *rects, unsigned int nb_rects )
 127 {
 128     const rectangle_t *ptr, *end;
 129
 130     for (ptr = rects, end = rects + nb_rects; ptr < end; ptr++)
 131     {
 132         if (ptr->left >= ptr->right || ptr->top >= ptr->bottom) return 0;  /* empty rectangle */
 133         if (ptr == end - 1) break;
 134         if (ptr[0].top == ptr[1].top)  /* same band */
 135         {
 136             if (ptr[0].bottom != ptr[1].bottom) return 0;  /* not same y extent */
 137             if (ptr[0].right >= ptr[1].left) return 0;  /* not properly x ordered */
 138         }
 139         else  /* new band */
 140         {
 141             if (ptr[0].bottom > ptr[1].top) return 0;  /* not properly y ordered */
 142         }
 143     }
 144     return 1;
 145 }
 146
 147 /* attempt to merge the rects in the current band with those in the */
 148 /* previous one. Used only by region_op. */
 149 static int coalesce_region( struct region *pReg, int prevStart, int curStart )
 150 {
 151     int curNumRects;
 152     rectangle_t *pRegEnd = &pReg->rects[pReg->num_rects];
 153     rectangle_t *pPrevRect = &pReg->rects[prevStart];
 154     rectangle_t *pCurRect = &pReg->rects[curStart];
 155     int prevNumRects = curStart - prevStart;
 156     int bandtop = pCurRect->top;
 157
 158     for (curNumRects = 0;
 159          (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
 160          curNumRects++)
 161     {
 162         pCurRect++;
 163     }
 164
 165     if (pCurRect != pRegEnd)
 166     {
 167         pRegEnd--;
 168         while (pRegEnd[-1].top == pRegEnd->top) pRegEnd--;
 169         curStart = pRegEnd - pReg->rects;
 170         pRegEnd = pReg->rects + pReg->num_rects;
 171     }
 172
 173     if ((curNumRects == prevNumRects) && (curNumRects != 0))
 174     {
 175         pCurRect -= curNumRects;
 176         if (pPrevRect->bottom == pCurRect->top)
 177         {
 178             do
 179             {
 180                 if ((pPrevRect->left != pCurRect->left) ||
 181                     (pPrevRect->right != pCurRect->right)) return curStart;
 182                 pPrevRect++;
 183                 pCurRect++;
 184                 prevNumRects -= 1;
 185             } while (prevNumRects != 0);
 186
 187             pReg->num_rects -= curNumRects;
 188             pCurRect -= curNumRects;
 189             pPrevRect -= curNumRects;
 190
 191             do
 192             {
 193                 pPrevRect->bottom = pCurRect->bottom;
 194                 pPrevRect++;
 195                 pCurRect++;
 196                 curNumRects -= 1;
 197             } while (curNumRects != 0);
 198
 199             if (pCurRect == pRegEnd) curStart = prevStart;
 200             else do { *pPrevRect++ = *pCurRect++; } while (pCurRect != pRegEnd);
 201
 202         }
 203     }
 204     return curStart;
 205 }
 206
 207 /* apply an operation to two regions */
 208 /* check the GDI version of the code for explanations */
 209 static int region_op( struct region *newReg, const struct region *reg1, const struct region *reg2,
 210                       overlap_func_t overlap_func,
 211                       non_overlap_func_t non_overlap1_func,
 212                       non_overlap_func_t non_overlap2_func )
 213 {
 214     int ybot, ytop, top, bot, prevBand, curBand;
 215     const rectangle_t *r1BandEnd, *r2BandEnd;
 216
 217     const rectangle_t *r1 = reg1->rects;
 218     const rectangle_t *r2 = reg2->rects;
 219     const rectangle_t *r1End = r1 + reg1->num_rects;
 220     const rectangle_t *r2End = r2 + reg2->num_rects;
 221
 222     rectangle_t *new_rects, *old_rects = newReg->rects;
 223     int new_size, ret = 0;
 224
 225     new_size = max( reg1->num_rects, reg2->num_rects ) * 2;
 226     if (!(new_rects = mem_alloc( new_size * sizeof(*newReg->rects) ))) return 0;
 227
 228     newReg->size = new_size;
 229     newReg->rects = new_rects;
 230     newReg->num_rects = 0;
 231
 232     if (reg1->extents.top < reg2->extents.top)
 233         ybot = reg1->extents.top;
 234     else
 235         ybot = reg2->extents.top;
 236
 237     prevBand = 0;
 238
 239     do
 240     {
 241         curBand = newReg->num_rects;
 242
 243         r1BandEnd = r1;
 244         while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 245
 246         r2BandEnd = r2;
 247         while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 248
 249         if (r1->top < r2->top)
 250         {
 251             top = max(r1->top,ybot);
 252             bot = min(r1->bottom,r2->top);
 253
 254             if ((top != bot) && non_overlap1_func)
 255             {
 256                 if (!non_overlap1_func( newReg, r1, r1BandEnd, top, bot )) goto done;
 257             }
 258
 259             ytop = r2->top;
 260         }
 261         else if (r2->top < r1->top)
 262         {
 263             top = max(r2->top,ybot);
 264             bot = min(r2->bottom,r1->top);
 265
 266             if ((top != bot) && non_overlap2_func)
 267             {
 268                 if (!non_overlap2_func( newReg, r2, r2BandEnd, top, bot )) goto done;
 269             }
 270
 271             ytop = r1->top;
 272         }
 273         else
 274         {
 275             ytop = r1->top;
 276         }
 277
 278         if (newReg->num_rects != curBand)
 279             prevBand = coalesce_region(newReg, prevBand, curBand);
 280
 281         ybot = min(r1->bottom, r2->bottom);
 282         curBand = newReg->num_rects;
 283         if (ybot > ytop)
 284         {
 285             if (!overlap_func( newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot )) goto done;
 286         }
 287
 288         if (newReg->num_rects != curBand)
 289             prevBand = coalesce_region(newReg, prevBand, curBand);
 290
 291         if (r1->bottom == ybot) r1 = r1BandEnd;
 292         if (r2->bottom == ybot) r2 = r2BandEnd;
 293     } while ((r1 != r1End) && (r2 != r2End));
 294
 295     curBand = newReg->num_rects;
 296     if (r1 != r1End)
 297     {
 298         if (non_overlap1_func)
 299         {
 300             do
 301             {
 302                 r1BandEnd = r1;
 303                 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 304                 if (!non_overlap1_func( newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom ))
 305                     goto done;
 306                 r1 = r1BandEnd;
 307             } while (r1 != r1End);
 308         }
 309     }
 310     else if ((r2 != r2End) && non_overlap2_func)
 311     {
 312         do
 313         {
 314             r2BandEnd = r2;
 315             while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 316             if (!non_overlap2_func( newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom ))
 317                 goto done;
 318             r2 = r2BandEnd;
 319         } while (r2 != r2End);
 320     }
 321
 322     if (newReg->num_rects != curBand) coalesce_region(newReg, prevBand, curBand);
 323
 324     if ((newReg->num_rects < (newReg->size / 2)) && (newReg->size > 2))
 325     {
 326         new_size = max( newReg->num_rects, RGN_DEFAULT_RECTS );
 327         if ((new_rects = realloc( newReg->rects, sizeof(*newReg->rects) * new_size )))
 328         {
 329             newReg->rects = new_rects;
 330             newReg->size = new_size;
 331         }
 332     }
 333     ret = 1;
 334 done:
 335     free( old_rects );
 336     return ret;
 337 }
 338
 339 /* recalculate the extents of a region */
 340 static void set_region_extents( struct region *region )
 341 {
 342     rectangle_t *pRect, *pRectEnd;
 343
 344     if (region->num_rects == 0)
 345     {
 346         region->extents.left = 0;
 347         region->extents.top = 0;
 348         region->extents.right = 0;
 349         region->extents.bottom = 0;
 350         return;
 351     }
 352
 353     pRect = region->rects;
 354     pRectEnd = &pRect[region->num_rects - 1];
 355
 356     region->extents.left = pRect->left;
 357     region->extents.top = pRect->top;
 358     region->extents.right = pRectEnd->right;
 359     region->extents.bottom = pRectEnd->bottom;
 360
 361     while (pRect <= pRectEnd)
 362     {
 363         if (pRect->left < region->extents.left) region->extents.left = pRect->left;
 364         if (pRect->right > region->extents.right) region->extents.right = pRect->right;
 365         pRect++;
 366     }
 367 }
 368
 369 /* handle an overlapping band for intersect_region */
 370 static int intersect_overlapping( struct region *pReg,
 371                                   const rectangle_t *r1, const rectangle_t *r1End,
 372                                   const rectangle_t *r2, const rectangle_t *r2End,
 373                                   int top, int bottom )
 374
 375 {
 376     int left, right;
 377
 378     while ((r1 != r1End) && (r2 != r2End))
 379     {
 380         left = max(r1->left, r2->left);
 381         right = min(r1->right, r2->right);
 382
 383         if (left < right)
 384         {
 385             rectangle_t *rect = add_rect( pReg );
 386             if (!rect) return 0;
 387             rect->left = left;
 388             rect->top = top;
 389             rect->right = right;
 390             rect->bottom = bottom;
 391         }
 392
 393         if (r1->right < r2->right) r1++;
 394         else if (r2->right < r1->right) r2++;
 395         else
 396         {
 397             r1++;
 398             r2++;
 399         }
 400     }
 401     return 1;
 402 }
 403
 404 /* handle a non-overlapping band for subtract_region */
 405 static int subtract_non_overlapping( struct region *pReg, const rectangle_t *r,
 406                                   const rectangle_t *rEnd, int top, int bottom )
 407 {
 408     while (r != rEnd)
 409     {
 410         rectangle_t *rect = add_rect( pReg );
 411         if (!rect) return 0;
 412         rect->left = r->left;
 413         rect->top = top;
 414         rect->right = r->right;
 415         rect->bottom = bottom;
 416         r++;
 417     }
 418     return 1;
 419 }
 420
 421 /* handle an overlapping band for subtract_region */
 422 static int subtract_overlapping( struct region *pReg,
 423                                  const rectangle_t *r1, const rectangle_t *r1End,
 424                                  const rectangle_t *r2, const rectangle_t *r2End,
 425                                  int top, int bottom )
 426 {
 427     int left = r1->left;
 428
 429     while ((r1 != r1End) && (r2 != r2End))
 430     {
 431         if (r2->right <= left) r2++;
 432         else if (r2->left <= left)
 433         {
 434             left = r2->right;
 435             if (left >= r1->right)
 436             {
 437                 r1++;
 438                 if (r1 != r1End)
 439                     left = r1->left;
 440             }
 441             else r2++;
 442         }
 443         else if (r2->left < r1->right)
 444         {
 445             rectangle_t *rect = add_rect( pReg );
 446             if (!rect) return 0;
 447             rect->left = left;
 448             rect->top = top;
 449             rect->right = r2->left;
 450             rect->bottom = bottom;
 451             left = r2->right;
 452             if (left >= r1->right)
 453             {
 454                 r1++;
 455                 if (r1 != r1End)
 456                     left = r1->left;
 457             }
 458             else r2++;
 459         }
 460         else
 461         {
 462             if (r1->right > left)
 463             {
 464                 rectangle_t *rect = add_rect( pReg );
 465                 if (!rect) return 0;
 466                 rect->left = left;
 467                 rect->top = top;
 468                 rect->right = r1->right;
 469                 rect->bottom = bottom;
 470             }
 471             r1++;
 472             left = r1->left;
 473         }
 474     }
 475
 476     while (r1 != r1End)
 477     {
 478         rectangle_t *rect = add_rect( pReg );
 479         if (!rect) return 0;
 480         rect->left = left;
 481         rect->top = top;
 482         rect->right = r1->right;
 483         rect->bottom = bottom;
 484         r1++;
 485         if (r1 != r1End) left = r1->left;
 486     }
 487     return 1;
 488 }
 489
 490 /* handle a non-overlapping band for union_region */
 491 static int union_non_overlapping( struct region *pReg, const rectangle_t *r,
 492                                   const rectangle_t *rEnd, int top, int bottom )
 493 {
 494     while (r != rEnd)
 495     {
 496         rectangle_t *rect = add_rect( pReg );
 497         if (!rect) return 0;
 498         rect->left = r->left;
 499         rect->top = top;
 500         rect->right = r->right;
 501         rect->bottom = bottom;
 502         r++;
 503     }
 504     return 1;
 505 }
 506
 507 /* handle an overlapping band for union_region */
 508 static int union_overlapping( struct region *pReg,
 509                               const rectangle_t *r1, const rectangle_t *r1End,
 510                               const rectangle_t *r2, const rectangle_t *r2End,
 511                               int top, int bottom )
 512 {
 513 #define MERGERECT(r) \
 514     if ((pReg->num_rects != 0) &&  \
 515         (pReg->rects[pReg->num_rects-1].top == top) &&  \
 516         (pReg->rects[pReg->num_rects-1].bottom == bottom) &&  \
 517         (pReg->rects[pReg->num_rects-1].right >= r->left))  \
 518     {  \
 519         if (pReg->rects[pReg->num_rects-1].right < r->right)  \
 520         {  \
 521             pReg->rects[pReg->num_rects-1].right = r->right;  \
 522         }  \
 523     }  \
 524     else  \
 525     {  \
 526         rectangle_t *rect = add_rect( pReg ); \
 527         if (!rect) return 0; \
 528         rect->top = top;  \
 529         rect->bottom = bottom;  \
 530         rect->left = r->left;  \
 531         rect->right = r->right;  \
 532     }  \
 533     r++;
 534
 535     while ((r1 != r1End) && (r2 != r2End))
 536     {
 537         if (r1->left < r2->left)
 538         {
 539             MERGERECT(r1);
 540         }
 541         else
 542         {
 543             MERGERECT(r2);
 544         }
 545     }
 546
 547     if (r1 != r1End)
 548     {
 549         do
 550         {
 551             MERGERECT(r1);
 552         } while (r1 != r1End);
 553     }
 554     else while (r2 != r2End)
 555     {
 556         MERGERECT(r2);
 557     }
 558     return 1;
 559 #undef MERGERECT
 560 }
 561
 562
 563 /* create an empty region */
 564 struct region *create_empty_region(void)
 565 {
 566     struct region *region;
 567
 568     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
 569     if (!(region->rects = mem_alloc( RGN_DEFAULT_RECTS * sizeof(*region->rects) )))
 570     {
 571         free( region );
 572         return NULL;
 573     }
 574     region->size = RGN_DEFAULT_RECTS;
 575     region->num_rects = 0;
 576     region->extents.left = 0;
 577     region->extents.top = 0;
 578     region->extents.right = 0;
 579     region->extents.bottom = 0;
 580     return region;
 581 }
 582
 583 /* create a region from request data */
 584 struct region *create_region_from_req_data( const void *data, size_t size )
 585 {
 586     unsigned int alloc_rects;
 587     struct region *region;
 588     const rectangle_t *rects = data;
 589     int nb_rects = size / sizeof(rectangle_t);
 590
 591     /* special case: empty region can be specified by a single all-zero rectangle */
 592     if (nb_rects == 1 && !memcmp( rects, &empty_rect, sizeof(empty_rect) )) nb_rects = 0;
 593
 594     if (!validate_rectangles( rects, nb_rects ))
 595     {
 596         set_error( STATUS_INVALID_PARAMETER );
 597         return NULL;
 598     }
 599
 600     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
 601
 602     alloc_rects = max( nb_rects, RGN_DEFAULT_RECTS );
 603     if (!(region->rects = mem_alloc( alloc_rects * sizeof(*region->rects) )))
 604     {
 605         free( region );
 606         return NULL;
 607     }
 608     region->size = alloc_rects;
 609     region->num_rects = nb_rects;
 610     memcpy( region->rects, rects, nb_rects * sizeof(*rects) );
 611     set_region_extents( region );
 612     return region;
 613 }
 614
 615 /* free a region */
 616 void free_region( struct region *region )
 617 {
 618     free( region->rects );
 619     free( region );
 620 }
 621
 622 /* set region to a simple rectangle */
 623 void set_region_rect( struct region *region, const rectangle_t *rect )
 624 {
 625     if (rect->left < rect->right && rect->top < rect->bottom)
 626     {
 627         region->num_rects = 1;
 628         region->rects[0] = region->extents = *rect;
 629     }
 630     else
 631     {
 632         region->num_rects = 0;
 633         region->extents.left = 0;
 634         region->extents.top = 0;
 635         region->extents.right = 0;
 636         region->extents.bottom = 0;
 637     }
 638 }
 639
 640 /* retrieve the region data for sending to the client */
 641 rectangle_t *get_region_data( const struct region *region, size_t max_size, size_t *total_size )
 642 {
 643     const rectangle_t *data = region->rects;
 644
 645     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 646     {
 647         /* return a single empty rect for empty regions */
 648         *total_size = sizeof(empty_rect);
 649         data = &empty_rect;
 650     }
 651     if (max_size >= *total_size) return memdup( data, *total_size );
 652     set_error( STATUS_BUFFER_OVERFLOW );
 653     return NULL;
 654 }
 655
 656 /* retrieve the region data for sending to the client and free the region at the same time */
 657 rectangle_t *get_region_data_and_free( struct region *region, size_t max_size, size_t *total_size )
 658 {
 659     rectangle_t *ret = region->rects;
 660
 661     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 662     {
 663         /* return a single empty rect for empty regions */
 664         *total_size = sizeof(empty_rect);
 665         if (max_size >= sizeof(empty_rect))
 666         {
 667             ret = memdup( &empty_rect, sizeof(empty_rect) );
 668             free( region->rects );
 669         }
 670     }
 671
 672     if (max_size < *total_size)
 673     {
 674         free( region->rects );
 675         set_error( STATUS_BUFFER_OVERFLOW );
 676         ret = NULL;
 677     }
 678     free( region );
 679     return ret;
 680 }
 681
 682 /* check if a given region is empty */
 683 int is_region_empty( const struct region *region )
 684 {
 685     return region->num_rects == 0;
 686 }
 687
 688
 689 /* get the extents rect of a region */
 690 void get_region_extents( const struct region *region, rectangle_t *rect )
 691 {
 692     *rect = region->extents;
 693 }
 694
 695 /* add an offset to a region */
 696 void offset_region( struct region *region, int x, int y )
 697 {
 698     rectangle_t *rect, *end;
 699
 700     if (!region->num_rects) return;
 701     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
 702     {
 703         rect->left += x;
 704         rect->right += x;
 705         rect->top += y;
 706         rect->bottom += y;
 707     }
 708     region->extents.left += x;
 709     region->extents.right += x;
 710     region->extents.top += y;
 711     region->extents.bottom += y;
 712 }
 713
 714 /* make a copy of a region; returns dst or NULL on error */
 715 struct region *copy_region( struct region *dst, const struct region *src )
 716 {
 717     if (dst == src) return dst;
 718
 719     if (dst->size < src->num_rects)
 720     {
 721         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
 722         if (!rect)
 723         {
 724             set_error( STATUS_NO_MEMORY );
 725             return NULL;
 726         }
 727         dst->rects = rect;
 728         dst->size = src->num_rects;
 729     }
 730     dst->num_rects = src->num_rects;
 731     dst->extents = src->extents;
 732     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
 733     return dst;
 734 }
 735
 736 /* compute the intersection of two regions into dst, which can be one of the source regions */
 737 struct region *intersect_region( struct region *dst, const struct region *src1,
 738                                  const struct region *src2 )
 739 {
 740     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 741     {
 742         dst->num_rects = 0;
 743         dst->extents.left = 0;
 744         dst->extents.top = 0;
 745         dst->extents.right = 0;
 746         dst->extents.bottom = 0;
 747         return dst;
 748     }
 749     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
 750     set_region_extents( dst );
 751     return dst;
 752 }
 753
 754 /* compute the subtraction of two regions into dst, which can be one of the source regions */
 755 struct region *subtract_region( struct region *dst, const struct region *src1,
 756                                 const struct region *src2 )
 757 {
 758     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 759         return copy_region( dst, src1 );
 760
 761     if (!region_op( dst, src1, src2, subtract_overlapping,
 762                     subtract_non_overlapping, NULL )) return NULL;
 763     set_region_extents( dst );
 764     return dst;
 765 }
 766
 767 /* compute the union of two regions into dst, which can be one of the source regions */
 768 struct region *union_region( struct region *dst, const struct region *src1,
 769                              const struct region *src2 )
 770 {
 771     if (src1 == src2) return copy_region( dst, src1 );
 772     if (!src1->num_rects) return copy_region( dst, src2 );
 773     if (!src2->num_rects) return copy_region( dst, src1 );
 774
 775     if ((src1->num_rects == 1) &&
 776         (src1->extents.left <= src2->extents.left) &&
 777         (src1->extents.top <= src2->extents.top) &&
 778         (src1->extents.right >= src2->extents.right) &&
 779         (src1->extents.bottom >= src2->extents.bottom))
 780         return copy_region( dst, src1 );
 781
 782     if ((src2->num_rects == 1) &&
 783         (src2->extents.left <= src1->extents.left) &&
 784         (src2->extents.top <= src1->extents.top) &&
 785         (src2->extents.right >= src1->extents.right) &&
 786         (src2->extents.bottom >= src1->extents.bottom))
 787         return copy_region( dst, src2 );
 788
 789     if (!region_op( dst, src1, src2, union_overlapping,
 790                     union_non_overlapping, union_non_overlapping )) return NULL;
 791
 792     dst->extents.left = min(src1->extents.left, src2->extents.left);
 793     dst->extents.top = min(src1->extents.top, src2->extents.top);
 794     dst->extents.right = max(src1->extents.right, src2->extents.right);
 795     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
 796     return dst;
 797 }
 798
 799 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
 800 struct region *xor_region( struct region *dst, const struct region *src1,
 801                            const struct region *src2 )
 802 {
 803     struct region *tmp = create_empty_region();
 804
 805     if (!tmp) return NULL;
 806
 807     if (!subtract_region( tmp, src1, src2 ) ||
 808         !subtract_region( dst, src2, src1 ) ||
 809         !union_region( dst, dst, tmp ))
 810         dst = NULL;
 811
 812     free_region( tmp );
 813     return dst;
 814 }
 815
 816 /* check if the given point is inside the region */
 817 int point_in_region( struct region *region, int x, int y )
 818 {
 819     const rectangle_t *ptr, *end;
 820
 821     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 822     {
 823         if (ptr->top > y) return 0;
 824         if (ptr->bottom <= y) continue;
 825         /* now we are in the correct band */
 826         if (ptr->left > x) return 0;
 827         if (ptr->right <= x) continue;
 828         return 1;
 829     }
 830     return 0;
 831 }
 832
 833 /* check if the given rectangle is (at least partially) inside the region */
 834 int rect_in_region( struct region *region, const rectangle_t *rect )
 835 {
 836     const rectangle_t *ptr, *end;
 837
 838     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 839     {
 840         if (ptr->top >= rect->bottom) return 0;
 841         if (ptr->bottom <= rect->top) continue;
 842         if (ptr->left >= rect->right) continue;
 843         if (ptr->right <= rect->left) continue;
 844         return 1;
 845     }
 846     return 0;
 847 }