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 "request.h"
  79 #include "user.h"
  80
  81 struct region
  82 {
  83     int size;
  84     int num_rects;
  85     rectangle_t *rects;
  86     rectangle_t extents;
  87 };
  88
  89
  90 #define RGN_DEFAULT_RECTS 2
  91
  92 #define EXTENTCHECK(r1, r2) \
  93     ((r1)->right > (r2)->left && \
  94     (r1)->left < (r2)->right && \
  95     (r1)->bottom > (r2)->top && \
  96     (r1)->top < (r2)->bottom)
  97
  98 typedef int (*overlap_func_t)( struct region *reg, const rectangle_t *r1, const rectangle_t *r1End,
  99                                const rectangle_t *r2, const rectangle_t *r2End, int top, int bottom );
 100 typedef int (*non_overlap_func_t)( struct region *reg, const rectangle_t *r,
 101                                    const rectangle_t *rEnd, int top, int bottom );
 102
 103 static const rectangle_t empty_rect;  /* all-zero rectangle for empty regions */
 104
 105 /* add a rectangle to a region */
 106 static inline rectangle_t *add_rect( struct region *reg )
 107 {
 108     if (reg->num_rects >= reg->size - 1)
 109     {
 110         rectangle_t *new_rect = realloc( reg->rects, 2 * sizeof(rectangle_t) * reg->size );
 111         if (!new_rect)
 112         {
 113             set_error( STATUS_NO_MEMORY );
 114             return NULL;
 115         }
 116         reg->rects = new_rect;
 117         reg->size *= 2;
 118     }
 119     return reg->rects + reg->num_rects++;
 120 }
 121
 122 /* make sure all the rectangles are valid and that the region is properly y-x-banded */
 123 static inline int validate_rectangles( const rectangle_t *rects, unsigned int nb_rects )
 124 {
 125     const rectangle_t *ptr, *end;
 126
 127     for (ptr = rects, end = rects + nb_rects; ptr < end; ptr++)
 128     {
 129         if (ptr->left >= ptr->right || ptr->top >= ptr->bottom) return 0;  /* empty rectangle */
 130         if (ptr == end - 1) break;
 131         if (ptr[0].top == ptr[1].top)  /* same band */
 132         {
 133             if (ptr[0].bottom != ptr[1].bottom) return 0;  /* not same y extent */
 134             if (ptr[0].right >= ptr[1].left) return 0;  /* not properly x ordered */
 135         }
 136         else  /* new band */
 137         {
 138             if (ptr[0].bottom > ptr[1].top) return 0;  /* not properly y ordered */
 139         }
 140     }
 141     return 1;
 142 }
 143
 144 /* attempt to merge the rects in the current band with those in the */
 145 /* previous one. Used only by region_op. */
 146 static int coalesce_region( struct region *pReg, int prevStart, int curStart )
 147 {
 148     int curNumRects;
 149     rectangle_t *pRegEnd = &pReg->rects[pReg->num_rects];
 150     rectangle_t *pPrevRect = &pReg->rects[prevStart];
 151     rectangle_t *pCurRect = &pReg->rects[curStart];
 152     int prevNumRects = curStart - prevStart;
 153     int bandtop = pCurRect->top;
 154
 155     for (curNumRects = 0;
 156          (pCurRect != pRegEnd) && (pCurRect->top == bandtop);
 157          curNumRects++)
 158     {
 159         pCurRect++;
 160     }
 161
 162     if (pCurRect != pRegEnd)
 163     {
 164         pRegEnd--;
 165         while (pRegEnd[-1].top == pRegEnd->top) pRegEnd--;
 166         curStart = pRegEnd - pReg->rects;
 167         pRegEnd = pReg->rects + pReg->num_rects;
 168     }
 169
 170     if ((curNumRects == prevNumRects) && (curNumRects != 0))
 171     {
 172         pCurRect -= curNumRects;
 173         if (pPrevRect->bottom == pCurRect->top)
 174         {
 175             do
 176             {
 177                 if ((pPrevRect->left != pCurRect->left) ||
 178                     (pPrevRect->right != pCurRect->right)) return curStart;
 179                 pPrevRect++;
 180                 pCurRect++;
 181                 prevNumRects -= 1;
 182             } while (prevNumRects != 0);
 183
 184             pReg->num_rects -= curNumRects;
 185             pCurRect -= curNumRects;
 186             pPrevRect -= curNumRects;
 187
 188             do
 189             {
 190                 pPrevRect->bottom = pCurRect->bottom;
 191                 pPrevRect++;
 192                 pCurRect++;
 193                 curNumRects -= 1;
 194             } while (curNumRects != 0);
 195
 196             if (pCurRect == pRegEnd) curStart = prevStart;
 197             else do { *pPrevRect++ = *pCurRect++; } while (pCurRect != pRegEnd);
 198
 199         }
 200     }
 201     return curStart;
 202 }
 203
 204 /* apply an operation to two regions */
 205 /* check the GDI version of the code for explanations */
 206 static int region_op( struct region *newReg, const struct region *reg1, const struct region *reg2,
 207                       overlap_func_t overlap_func,
 208                       non_overlap_func_t non_overlap1_func,
 209                       non_overlap_func_t non_overlap2_func )
 210 {
 211     int ybot, ytop, top, bot, prevBand, curBand;
 212     const rectangle_t *r1BandEnd, *r2BandEnd;
 213
 214     const rectangle_t *r1 = reg1->rects;
 215     const rectangle_t *r2 = reg2->rects;
 216     const rectangle_t *r1End = r1 + reg1->num_rects;
 217     const rectangle_t *r2End = r2 + reg2->num_rects;
 218
 219     rectangle_t *new_rects, *old_rects = newReg->rects;
 220     int new_size, ret = 0;
 221
 222     new_size = max( reg1->num_rects, reg2->num_rects ) * 2;
 223     if (!(new_rects = mem_alloc( new_size * sizeof(*newReg->rects) ))) return 0;
 224
 225     newReg->size = new_size;
 226     newReg->rects = new_rects;
 227     newReg->num_rects = 0;
 228
 229     if (reg1->extents.top < reg2->extents.top)
 230         ybot = reg1->extents.top;
 231     else
 232         ybot = reg2->extents.top;
 233
 234     prevBand = 0;
 235
 236     do
 237     {
 238         curBand = newReg->num_rects;
 239
 240         r1BandEnd = r1;
 241         while ((r1BandEnd != r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 242
 243         r2BandEnd = r2;
 244         while ((r2BandEnd != r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 245
 246         if (r1->top < r2->top)
 247         {
 248             top = max(r1->top,ybot);
 249             bot = min(r1->bottom,r2->top);
 250
 251             if ((top != bot) && non_overlap1_func)
 252             {
 253                 if (!non_overlap1_func( newReg, r1, r1BandEnd, top, bot )) goto done;
 254             }
 255
 256             ytop = r2->top;
 257         }
 258         else if (r2->top < r1->top)
 259         {
 260             top = max(r2->top,ybot);
 261             bot = min(r2->bottom,r1->top);
 262
 263             if ((top != bot) && non_overlap2_func)
 264             {
 265                 if (!non_overlap2_func( newReg, r2, r2BandEnd, top, bot )) goto done;
 266             }
 267
 268             ytop = r1->top;
 269         }
 270         else
 271         {
 272             ytop = r1->top;
 273         }
 274
 275         if (newReg->num_rects != curBand)
 276             prevBand = coalesce_region(newReg, prevBand, curBand);
 277
 278         ybot = min(r1->bottom, r2->bottom);
 279         curBand = newReg->num_rects;
 280         if (ybot > ytop)
 281         {
 282             if (!overlap_func( newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot )) goto done;
 283         }
 284
 285         if (newReg->num_rects != curBand)
 286             prevBand = coalesce_region(newReg, prevBand, curBand);
 287
 288         if (r1->bottom == ybot) r1 = r1BandEnd;
 289         if (r2->bottom == ybot) r2 = r2BandEnd;
 290     } while ((r1 != r1End) && (r2 != r2End));
 291
 292     curBand = newReg->num_rects;
 293     if (r1 != r1End)
 294     {
 295         if (non_overlap1_func)
 296         {
 297             do
 298             {
 299                 r1BandEnd = r1;
 300                 while ((r1BandEnd < r1End) && (r1BandEnd->top == r1->top)) r1BandEnd++;
 301                 if (!non_overlap1_func( newReg, r1, r1BandEnd, max(r1->top,ybot), r1->bottom ))
 302                     goto done;
 303                 r1 = r1BandEnd;
 304             } while (r1 != r1End);
 305         }
 306     }
 307     else if ((r2 != r2End) && non_overlap2_func)
 308     {
 309         do
 310         {
 311             r2BandEnd = r2;
 312             while ((r2BandEnd < r2End) && (r2BandEnd->top == r2->top)) r2BandEnd++;
 313             if (!non_overlap2_func( newReg, r2, r2BandEnd, max(r2->top,ybot), r2->bottom ))
 314                 goto done;
 315             r2 = r2BandEnd;
 316         } while (r2 != r2End);
 317     }
 318
 319     if (newReg->num_rects != curBand) coalesce_region(newReg, prevBand, curBand);
 320
 321     if ((newReg->num_rects < (newReg->size / 2)) && (newReg->size > 2))
 322     {
 323         new_size = max( newReg->num_rects, RGN_DEFAULT_RECTS );
 324         if ((new_rects = realloc( newReg->rects, sizeof(*newReg->rects) * new_size )))
 325         {
 326             newReg->rects = new_rects;
 327             newReg->size = new_size;
 328         }
 329     }
 330     ret = 1;
 331 done:
 332     free( old_rects );
 333     return ret;
 334 }
 335
 336 /* recalculate the extents of a region */
 337 static void set_region_extents( struct region *region )
 338 {
 339     rectangle_t *pRect, *pRectEnd;
 340
 341     if (region->num_rects == 0)
 342     {
 343         region->extents.left = 0;
 344         region->extents.top = 0;
 345         region->extents.right = 0;
 346         region->extents.bottom = 0;
 347         return;
 348     }
 349
 350     pRect = region->rects;
 351     pRectEnd = &pRect[region->num_rects - 1];
 352
 353     region->extents.left = pRect->left;
 354     region->extents.top = pRect->top;
 355     region->extents.right = pRectEnd->right;
 356     region->extents.bottom = pRectEnd->bottom;
 357
 358     while (pRect <= pRectEnd)
 359     {
 360         if (pRect->left < region->extents.left) region->extents.left = pRect->left;
 361         if (pRect->right > region->extents.right) region->extents.right = pRect->right;
 362         pRect++;
 363     }
 364 }
 365
 366 /* handle an overlapping band for intersect_region */
 367 static int intersect_overlapping( struct region *pReg,
 368                                   const rectangle_t *r1, const rectangle_t *r1End,
 369                                   const rectangle_t *r2, const rectangle_t *r2End,
 370                                   int top, int bottom )
 371
 372 {
 373     int left, right;
 374
 375     while ((r1 != r1End) && (r2 != r2End))
 376     {
 377         left = max(r1->left, r2->left);
 378         right = min(r1->right, r2->right);
 379
 380         if (left < right)
 381         {
 382             rectangle_t *rect = add_rect( pReg );
 383             if (!rect) return 0;
 384             rect->left = left;
 385             rect->top = top;
 386             rect->right = right;
 387             rect->bottom = bottom;
 388         }
 389
 390         if (r1->right < r2->right) r1++;
 391         else if (r2->right < r1->right) r2++;
 392         else
 393         {
 394             r1++;
 395             r2++;
 396         }
 397     }
 398     return 1;
 399 }
 400
 401 /* handle a non-overlapping band for subtract_region */
 402 static int subtract_non_overlapping( struct region *pReg, const rectangle_t *r,
 403                                   const rectangle_t *rEnd, int top, int bottom )
 404 {
 405     while (r != rEnd)
 406     {
 407         rectangle_t *rect = add_rect( pReg );
 408         if (!rect) return 0;
 409         rect->left = r->left;
 410         rect->top = top;
 411         rect->right = r->right;
 412         rect->bottom = bottom;
 413         r++;
 414     }
 415     return 1;
 416 }
 417
 418 /* handle an overlapping band for subtract_region */
 419 static int subtract_overlapping( struct region *pReg,
 420                                  const rectangle_t *r1, const rectangle_t *r1End,
 421                                  const rectangle_t *r2, const rectangle_t *r2End,
 422                                  int top, int bottom )
 423 {
 424     int left = r1->left;
 425
 426     while ((r1 != r1End) && (r2 != r2End))
 427     {
 428         if (r2->right <= left) r2++;
 429         else if (r2->left <= left)
 430         {
 431             left = r2->right;
 432             if (left >= r1->right)
 433             {
 434                 r1++;
 435                 if (r1 != r1End)
 436                     left = r1->left;
 437             }
 438             else r2++;
 439         }
 440         else if (r2->left < r1->right)
 441         {
 442             rectangle_t *rect = add_rect( pReg );
 443             if (!rect) return 0;
 444             rect->left = left;
 445             rect->top = top;
 446             rect->right = r2->left;
 447             rect->bottom = bottom;
 448             left = r2->right;
 449             if (left >= r1->right)
 450             {
 451                 r1++;
 452                 if (r1 != r1End)
 453                     left = r1->left;
 454             }
 455             else r2++;
 456         }
 457         else
 458         {
 459             if (r1->right > left)
 460             {
 461                 rectangle_t *rect = add_rect( pReg );
 462                 if (!rect) return 0;
 463                 rect->left = left;
 464                 rect->top = top;
 465                 rect->right = r1->right;
 466                 rect->bottom = bottom;
 467             }
 468             r1++;
 469             left = r1->left;
 470         }
 471     }
 472
 473     while (r1 != r1End)
 474     {
 475         rectangle_t *rect = add_rect( pReg );
 476         if (!rect) return 0;
 477         rect->left = left;
 478         rect->top = top;
 479         rect->right = r1->right;
 480         rect->bottom = bottom;
 481         r1++;
 482         if (r1 != r1End) left = r1->left;
 483     }
 484     return 1;
 485 }
 486
 487 /* handle a non-overlapping band for union_region */
 488 static int union_non_overlapping( struct region *pReg, const rectangle_t *r,
 489                                   const rectangle_t *rEnd, int top, int bottom )
 490 {
 491     while (r != rEnd)
 492     {
 493         rectangle_t *rect = add_rect( pReg );
 494         if (!rect) return 0;
 495         rect->left = r->left;
 496         rect->top = top;
 497         rect->right = r->right;
 498         rect->bottom = bottom;
 499         r++;
 500     }
 501     return 1;
 502 }
 503
 504 /* handle an overlapping band for union_region */
 505 static int union_overlapping( struct region *pReg,
 506                               const rectangle_t *r1, const rectangle_t *r1End,
 507                               const rectangle_t *r2, const rectangle_t *r2End,
 508                               int top, int bottom )
 509 {
 510 #define MERGERECT(r) \
 511     if ((pReg->num_rects != 0) &&  \
 512         (pReg->rects[pReg->num_rects-1].top == top) &&  \
 513         (pReg->rects[pReg->num_rects-1].bottom == bottom) &&  \
 514         (pReg->rects[pReg->num_rects-1].right >= r->left))  \
 515     {  \
 516         if (pReg->rects[pReg->num_rects-1].right < r->right)  \
 517         {  \
 518             pReg->rects[pReg->num_rects-1].right = r->right;  \
 519         }  \
 520     }  \
 521     else  \
 522     {  \
 523         rectangle_t *rect = add_rect( pReg ); \
 524         if (!rect) return 0; \
 525         rect->top = top;  \
 526         rect->bottom = bottom;  \
 527         rect->left = r->left;  \
 528         rect->right = r->right;  \
 529     }  \
 530     r++;
 531
 532     while ((r1 != r1End) && (r2 != r2End))
 533     {
 534         if (r1->left < r2->left)
 535         {
 536             MERGERECT(r1);
 537         }
 538         else
 539         {
 540             MERGERECT(r2);
 541         }
 542     }
 543
 544     if (r1 != r1End)
 545     {
 546         do
 547         {
 548             MERGERECT(r1);
 549         } while (r1 != r1End);
 550     }
 551     else while (r2 != r2End)
 552     {
 553         MERGERECT(r2);
 554     }
 555     return 1;
 556 #undef MERGERECT
 557 }
 558
 559
 560 /* create an empty region */
 561 struct region *create_empty_region(void)
 562 {
 563     struct region *region;
 564
 565     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
 566     if (!(region->rects = mem_alloc( RGN_DEFAULT_RECTS * sizeof(*region->rects) )))
 567     {
 568         free( region );
 569         return NULL;
 570     }
 571     region->size = RGN_DEFAULT_RECTS;
 572     region->num_rects = 0;
 573     region->extents.left = 0;
 574     region->extents.top = 0;
 575     region->extents.right = 0;
 576     region->extents.bottom = 0;
 577     return region;
 578 }
 579
 580 /* create a region from request data */
 581 struct region *create_region_from_req_data( const void *data, size_t size )
 582 {
 583     unsigned int alloc_rects;
 584     struct region *region;
 585     const rectangle_t *rects = data;
 586     int nb_rects = size / sizeof(rectangle_t);
 587
 588     /* special case: empty region can be specified by a single all-zero rectangle */
 589     if (nb_rects == 1 && !memcmp( rects, &empty_rect, sizeof(empty_rect) )) nb_rects = 0;
 590
 591     if (!validate_rectangles( rects, nb_rects ))
 592     {
 593         set_error( STATUS_INVALID_PARAMETER );
 594         return NULL;
 595     }
 596
 597     if (!(region = mem_alloc( sizeof(*region) ))) return NULL;
 598
 599     alloc_rects = max( nb_rects, RGN_DEFAULT_RECTS );
 600     if (!(region->rects = mem_alloc( alloc_rects * sizeof(*region->rects) )))
 601     {
 602         free( region );
 603         return NULL;
 604     }
 605     region->size = alloc_rects;
 606     region->num_rects = nb_rects;
 607     memcpy( region->rects, rects, nb_rects * sizeof(*rects) );
 608     set_region_extents( region );
 609     return region;
 610 }
 611
 612 /* free a region */
 613 void free_region( struct region *region )
 614 {
 615     free( region->rects );
 616     free( region );
 617 }
 618
 619 /* set region to a simple rectangle */
 620 void set_region_rect( struct region *region, const rectangle_t *rect )
 621 {
 622     if (rect->left < rect->right && rect->top < rect->bottom)
 623     {
 624         region->num_rects = 1;
 625         region->rects[0] = region->extents = *rect;
 626     }
 627     else
 628     {
 629         region->num_rects = 0;
 630         region->extents.left = 0;
 631         region->extents.top = 0;
 632         region->extents.right = 0;
 633         region->extents.bottom = 0;
 634     }
 635 }
 636
 637 /* retrieve the region data for sending to the client */
 638 rectangle_t *get_region_data( const struct region *region, size_t max_size, size_t *total_size )
 639 {
 640     const rectangle_t *data = region->rects;
 641
 642     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 643     {
 644         /* return a single empty rect for empty regions */
 645         *total_size = sizeof(empty_rect);
 646         data = &empty_rect;
 647     }
 648     if (max_size >= *total_size) return memdup( data, *total_size );
 649     set_error( STATUS_BUFFER_OVERFLOW );
 650     return NULL;
 651 }
 652
 653 /* retrieve the region data for sending to the client and free the region at the same time */
 654 rectangle_t *get_region_data_and_free( struct region *region, size_t max_size, size_t *total_size )
 655 {
 656     rectangle_t *ret = region->rects;
 657
 658     if (!(*total_size = region->num_rects * sizeof(rectangle_t)))
 659     {
 660         /* return a single empty rect for empty regions */
 661         *total_size = sizeof(empty_rect);
 662         if (max_size >= sizeof(empty_rect))
 663         {
 664             ret = memdup( &empty_rect, sizeof(empty_rect) );
 665             free( region->rects );
 666         }
 667     }
 668
 669     if (max_size < *total_size)
 670     {
 671         free( region->rects );
 672         set_error( STATUS_BUFFER_OVERFLOW );
 673         ret = NULL;
 674     }
 675     free( region );
 676     return ret;
 677 }
 678
 679 /* check if a given region is empty */
 680 int is_region_empty( const struct region *region )
 681 {
 682     return region->num_rects == 0;
 683 }
 684
 685
 686 /* get the extents rect of a region */
 687 void get_region_extents( const struct region *region, rectangle_t *rect )
 688 {
 689     *rect = region->extents;
 690 }
 691
 692 /* add an offset to a region */
 693 void offset_region( struct region *region, int x, int y )
 694 {
 695     rectangle_t *rect, *end;
 696
 697     if (!region->num_rects) return;
 698     for (rect = region->rects, end = rect + region->num_rects; rect < end; rect++)
 699     {
 700         rect->left += x;
 701         rect->right += x;
 702         rect->top += y;
 703         rect->bottom += y;
 704     }
 705     region->extents.left += x;
 706     region->extents.right += x;
 707     region->extents.top += y;
 708     region->extents.bottom += y;
 709 }
 710
 711 /* make a copy of a region; returns dst or NULL on error */
 712 struct region *copy_region( struct region *dst, const struct region *src )
 713 {
 714     if (dst == src) return dst;
 715
 716     if (dst->size < src->num_rects)
 717     {
 718         rectangle_t *rect = realloc( dst->rects, src->num_rects * sizeof(*rect) );
 719         if (!rect)
 720         {
 721             set_error( STATUS_NO_MEMORY );
 722             return NULL;
 723         }
 724         dst->rects = rect;
 725         dst->size = src->num_rects;
 726     }
 727     dst->num_rects = src->num_rects;
 728     dst->extents = src->extents;
 729     memcpy( dst->rects, src->rects, src->num_rects * sizeof(*dst->rects) );
 730     return dst;
 731 }
 732
 733 /* compute the intersection of two regions into dst, which can be one of the source regions */
 734 struct region *intersect_region( struct region *dst, const struct region *src1,
 735                                  const struct region *src2 )
 736 {
 737     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 738     {
 739         dst->num_rects = 0;
 740         dst->extents.left = 0;
 741         dst->extents.top = 0;
 742         dst->extents.right = 0;
 743         dst->extents.bottom = 0;
 744         return dst;
 745     }
 746     if (!region_op( dst, src1, src2, intersect_overlapping, NULL, NULL )) return NULL;
 747     set_region_extents( dst );
 748     return dst;
 749 }
 750
 751 /* compute the subtraction of two regions into dst, which can be one of the source regions */
 752 struct region *subtract_region( struct region *dst, const struct region *src1,
 753                                 const struct region *src2 )
 754 {
 755     if (!src1->num_rects || !src2->num_rects || !EXTENTCHECK(&src1->extents, &src2->extents))
 756         return copy_region( dst, src1 );
 757
 758     if (!region_op( dst, src1, src2, subtract_overlapping,
 759                     subtract_non_overlapping, NULL )) return NULL;
 760     set_region_extents( dst );
 761     return dst;
 762 }
 763
 764 /* compute the union of two regions into dst, which can be one of the source regions */
 765 struct region *union_region( struct region *dst, const struct region *src1,
 766                              const struct region *src2 )
 767 {
 768     if (src1 == src2) return copy_region( dst, src1 );
 769     if (!src1->num_rects) return copy_region( dst, src2 );
 770     if (!src2->num_rects) return copy_region( dst, src1 );
 771
 772     if ((src1->num_rects == 1) &&
 773         (src1->extents.left <= src2->extents.left) &&
 774         (src1->extents.top <= src2->extents.top) &&
 775         (src1->extents.right >= src2->extents.right) &&
 776         (src1->extents.bottom >= src2->extents.bottom))
 777         return copy_region( dst, src1 );
 778
 779     if ((src2->num_rects == 1) &&
 780         (src2->extents.left <= src1->extents.left) &&
 781         (src2->extents.top <= src1->extents.top) &&
 782         (src2->extents.right >= src1->extents.right) &&
 783         (src2->extents.bottom >= src1->extents.bottom))
 784         return copy_region( dst, src2 );
 785
 786     if (!region_op( dst, src1, src2, union_overlapping,
 787                     union_non_overlapping, union_non_overlapping )) return NULL;
 788
 789     dst->extents.left = min(src1->extents.left, src2->extents.left);
 790     dst->extents.top = min(src1->extents.top, src2->extents.top);
 791     dst->extents.right = max(src1->extents.right, src2->extents.right);
 792     dst->extents.bottom = max(src1->extents.bottom, src2->extents.bottom);
 793     return dst;
 794 }
 795
 796 /* compute the exclusive or of two regions into dst, which can be one of the source regions */
 797 struct region *xor_region( struct region *dst, const struct region *src1,
 798                            const struct region *src2 )
 799 {
 800     struct region *tmp = create_empty_region();
 801
 802     if (!tmp) return NULL;
 803
 804     if (!subtract_region( tmp, src1, src2 ) ||
 805         !subtract_region( dst, src2, src1 ) ||
 806         !union_region( dst, dst, tmp ))
 807         dst = NULL;
 808
 809     free_region( tmp );
 810     return dst;
 811 }
 812
 813 /* check if the given point is inside the region */
 814 int point_in_region( struct region *region, int x, int y )
 815 {
 816     const rectangle_t *ptr, *end;
 817
 818     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 819     {
 820         if (ptr->top > y) return 0;
 821         if (ptr->bottom <= y) continue;
 822         /* now we are in the correct band */
 823         if (ptr->left > x) return 0;
 824         if (ptr->right <= x) continue;
 825         return 1;
 826     }
 827     return 0;
 828 }
 829
 830 /* check if the given rectangle is (at least partially) inside the region */
 831 int rect_in_region( struct region *region, const rectangle_t *rect )
 832 {
 833     const rectangle_t *ptr, *end;
 834
 835     for (ptr = region->rects, end = region->rects + region->num_rects; ptr < end; ptr++)
 836     {
 837         if (ptr->top >= rect->bottom) return 0;
 838         if (ptr->bottom <= rect->top) continue;
 839         if (ptr->left >= rect->right) continue;
 840         if (ptr->right <= rect->left) continue;
 841         return 1;
 842     }
 843     return 0;
 844 }