1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/cairo/libpixman/src/pixman-region.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,2792 @@
1.4 +/*
1.5 + * Copyright 1987, 1988, 1989, 1998 The Open Group
1.6 + *
1.7 + * Permission to use, copy, modify, distribute, and sell this software and its
1.8 + * documentation for any purpose is hereby granted without fee, provided that
1.9 + * the above copyright notice appear in all copies and that both that
1.10 + * copyright notice and this permission notice appear in supporting
1.11 + * documentation.
1.12 + *
1.13 + * The above copyright notice and this permission notice shall be included in
1.14 + * all copies or substantial portions of the Software.
1.15 + *
1.16 + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1.17 + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1.18 + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1.19 + * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1.20 + * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1.21 + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1.22 + *
1.23 + * Except as contained in this notice, the name of The Open Group shall not be
1.24 + * used in advertising or otherwise to promote the sale, use or other dealings
1.25 + * in this Software without prior written authorization from The Open Group.
1.26 + *
1.27 + * Copyright 1987, 1988, 1989 by
1.28 + * Digital Equipment Corporation, Maynard, Massachusetts.
1.29 + *
1.30 + * All Rights Reserved
1.31 + *
1.32 + * Permission to use, copy, modify, and distribute this software and its
1.33 + * documentation for any purpose and without fee is hereby granted,
1.34 + * provided that the above copyright notice appear in all copies and that
1.35 + * both that copyright notice and this permission notice appear in
1.36 + * supporting documentation, and that the name of Digital not be
1.37 + * used in advertising or publicity pertaining to distribution of the
1.38 + * software without specific, written prior permission.
1.39 + *
1.40 + * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1.41 + * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1.42 + * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1.43 + * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1.44 + * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1.45 + * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1.46 + * SOFTWARE.
1.47 + *
1.48 + * Copyright © 1998 Keith Packard
1.49 + *
1.50 + * Permission to use, copy, modify, distribute, and sell this software and its
1.51 + * documentation for any purpose is hereby granted without fee, provided that
1.52 + * the above copyright notice appear in all copies and that both that
1.53 + * copyright notice and this permission notice appear in supporting
1.54 + * documentation, and that the name of Keith Packard not be used in
1.55 + * advertising or publicity pertaining to distribution of the software without
1.56 + * specific, written prior permission. Keith Packard makes no
1.57 + * representations about the suitability of this software for any purpose. It
1.58 + * is provided "as is" without express or implied warranty.
1.59 + *
1.60 + * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
1.61 + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
1.62 + * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
1.63 + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
1.64 + * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
1.65 + * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
1.66 + * PERFORMANCE OF THIS SOFTWARE.
1.67 + */
1.68 +
1.69 +#include <stdlib.h>
1.70 +#include <limits.h>
1.71 +#include <string.h>
1.72 +#include <stdio.h>
1.73 +#include "pixman-private.h"
1.74 +
1.75 +#define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
1.76 +/* not a region */
1.77 +#define PIXREGION_NAR(reg) ((reg)->data == pixman_broken_data)
1.78 +#define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
1.79 +#define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
1.80 +#define PIXREGION_RECTS(reg) \
1.81 + ((reg)->data ? (box_type_t *)((reg)->data + 1) \
1.82 + : &(reg)->extents)
1.83 +#define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))
1.84 +#define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])
1.85 +#define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)
1.86 +#define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)
1.87 +
1.88 +#define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)
1.89 +#define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2)
1.90 +
1.91 +#ifdef DEBUG
1.92 +
1.93 +#define GOOD(reg) \
1.94 + do \
1.95 + { \
1.96 + if (!PREFIX (_selfcheck (reg))) \
1.97 + _pixman_log_error (FUNC, "Malformed region " # reg); \
1.98 + } while (0)
1.99 +
1.100 +#else
1.101 +
1.102 +#define GOOD(reg)
1.103 +
1.104 +#endif
1.105 +
1.106 +static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };
1.107 +static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };
1.108 +#if defined (__llvm__) && !defined (__clang__)
1.109 +static const volatile region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
1.110 +#else
1.111 +static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
1.112 +#endif
1.113 +
1.114 +static box_type_t *pixman_region_empty_box =
1.115 + (box_type_t *)&PREFIX (_empty_box_);
1.116 +static region_data_type_t *pixman_region_empty_data =
1.117 + (region_data_type_t *)&PREFIX (_empty_data_);
1.118 +static region_data_type_t *pixman_broken_data =
1.119 + (region_data_type_t *)&PREFIX (_broken_data_);
1.120 +
1.121 +static pixman_bool_t
1.122 +pixman_break (region_type_t *region);
1.123 +
1.124 +/*
1.125 + * The functions in this file implement the Region abstraction used extensively
1.126 + * throughout the X11 sample server. A Region is simply a set of disjoint
1.127 + * (non-overlapping) rectangles, plus an "extent" rectangle which is the
1.128 + * smallest single rectangle that contains all the non-overlapping rectangles.
1.129 + *
1.130 + * A Region is implemented as a "y-x-banded" array of rectangles. This array
1.131 + * imposes two degrees of order. First, all rectangles are sorted by top side
1.132 + * y coordinate first (y1), and then by left side x coordinate (x1).
1.133 + *
1.134 + * Furthermore, the rectangles are grouped into "bands". Each rectangle in a
1.135 + * band has the same top y coordinate (y1), and each has the same bottom y
1.136 + * coordinate (y2). Thus all rectangles in a band differ only in their left
1.137 + * and right side (x1 and x2). Bands are implicit in the array of rectangles:
1.138 + * there is no separate list of band start pointers.
1.139 + *
1.140 + * The y-x band representation does not minimize rectangles. In particular,
1.141 + * if a rectangle vertically crosses a band (the rectangle has scanlines in
1.142 + * the y1 to y2 area spanned by the band), then the rectangle may be broken
1.143 + * down into two or more smaller rectangles stacked one atop the other.
1.144 + *
1.145 + * ----------- -----------
1.146 + * | | | | band 0
1.147 + * | | -------- ----------- --------
1.148 + * | | | | in y-x banded | | | | band 1
1.149 + * | | | | form is | | | |
1.150 + * ----------- | | ----------- --------
1.151 + * | | | | band 2
1.152 + * -------- --------
1.153 + *
1.154 + * An added constraint on the rectangles is that they must cover as much
1.155 + * horizontal area as possible: no two rectangles within a band are allowed
1.156 + * to touch.
1.157 + *
1.158 + * Whenever possible, bands will be merged together to cover a greater vertical
1.159 + * distance (and thus reduce the number of rectangles). Two bands can be merged
1.160 + * only if the bottom of one touches the top of the other and they have
1.161 + * rectangles in the same places (of the same width, of course).
1.162 + *
1.163 + * Adam de Boor wrote most of the original region code. Joel McCormack
1.164 + * substantially modified or rewrote most of the core arithmetic routines, and
1.165 + * added pixman_region_validate in order to support several speed improvements
1.166 + * to pixman_region_validate_tree. Bob Scheifler changed the representation
1.167 + * to be more compact when empty or a single rectangle, and did a bunch of
1.168 + * gratuitous reformatting. Carl Worth did further gratuitous reformatting
1.169 + * while re-merging the server and client region code into libpixregion.
1.170 + * Soren Sandmann did even more gratuitous reformatting.
1.171 + */
1.172 +
1.173 +/* true iff two Boxes overlap */
1.174 +#define EXTENTCHECK(r1, r2) \
1.175 + (!( ((r1)->x2 <= (r2)->x1) || \
1.176 + ((r1)->x1 >= (r2)->x2) || \
1.177 + ((r1)->y2 <= (r2)->y1) || \
1.178 + ((r1)->y1 >= (r2)->y2) ) )
1.179 +
1.180 +/* true iff (x,y) is in Box */
1.181 +#define INBOX(r, x, y) \
1.182 + ( ((r)->x2 > x) && \
1.183 + ((r)->x1 <= x) && \
1.184 + ((r)->y2 > y) && \
1.185 + ((r)->y1 <= y) )
1.186 +
1.187 +/* true iff Box r1 contains Box r2 */
1.188 +#define SUBSUMES(r1, r2) \
1.189 + ( ((r1)->x1 <= (r2)->x1) && \
1.190 + ((r1)->x2 >= (r2)->x2) && \
1.191 + ((r1)->y1 <= (r2)->y1) && \
1.192 + ((r1)->y2 >= (r2)->y2) )
1.193 +
1.194 +static size_t
1.195 +PIXREGION_SZOF (size_t n)
1.196 +{
1.197 + size_t size = n * sizeof(box_type_t);
1.198 +
1.199 + if (n > UINT32_MAX / sizeof(box_type_t))
1.200 + return 0;
1.201 +
1.202 + if (sizeof(region_data_type_t) > UINT32_MAX - size)
1.203 + return 0;
1.204 +
1.205 + return size + sizeof(region_data_type_t);
1.206 +}
1.207 +
1.208 +static region_data_type_t *
1.209 +alloc_data (size_t n)
1.210 +{
1.211 + size_t sz = PIXREGION_SZOF (n);
1.212 +
1.213 + if (!sz)
1.214 + return NULL;
1.215 +
1.216 + return malloc (sz);
1.217 +}
1.218 +
1.219 +#define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)
1.220 +
1.221 +#define RECTALLOC_BAIL(region, n, bail) \
1.222 + do \
1.223 + { \
1.224 + if (!(region)->data || \
1.225 + (((region)->data->numRects + (n)) > (region)->data->size)) \
1.226 + { \
1.227 + if (!pixman_rect_alloc (region, n)) \
1.228 + goto bail; \
1.229 + } \
1.230 + } while (0)
1.231 +
1.232 +#define RECTALLOC(region, n) \
1.233 + do \
1.234 + { \
1.235 + if (!(region)->data || \
1.236 + (((region)->data->numRects + (n)) > (region)->data->size)) \
1.237 + { \
1.238 + if (!pixman_rect_alloc (region, n)) { \
1.239 + return FALSE; \
1.240 + } \
1.241 + } \
1.242 + } while (0)
1.243 +
1.244 +#define ADDRECT(next_rect, nx1, ny1, nx2, ny2) \
1.245 + do \
1.246 + { \
1.247 + next_rect->x1 = nx1; \
1.248 + next_rect->y1 = ny1; \
1.249 + next_rect->x2 = nx2; \
1.250 + next_rect->y2 = ny2; \
1.251 + next_rect++; \
1.252 + } \
1.253 + while (0)
1.254 +
1.255 +#define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2) \
1.256 + do \
1.257 + { \
1.258 + if (!(region)->data || \
1.259 + ((region)->data->numRects == (region)->data->size)) \
1.260 + { \
1.261 + if (!pixman_rect_alloc (region, 1)) \
1.262 + return FALSE; \
1.263 + next_rect = PIXREGION_TOP (region); \
1.264 + } \
1.265 + ADDRECT (next_rect, nx1, ny1, nx2, ny2); \
1.266 + region->data->numRects++; \
1.267 + critical_if_fail (region->data->numRects <= region->data->size); \
1.268 + } while (0)
1.269 +
1.270 +#define DOWNSIZE(reg, numRects) \
1.271 + do \
1.272 + { \
1.273 + if (((numRects) < ((reg)->data->size >> 1)) && \
1.274 + ((reg)->data->size > 50)) \
1.275 + { \
1.276 + region_data_type_t * new_data; \
1.277 + size_t data_size = PIXREGION_SZOF (numRects); \
1.278 + \
1.279 + if (!data_size) \
1.280 + { \
1.281 + new_data = NULL; \
1.282 + } \
1.283 + else \
1.284 + { \
1.285 + new_data = (region_data_type_t *) \
1.286 + realloc ((reg)->data, data_size); \
1.287 + } \
1.288 + \
1.289 + if (new_data) \
1.290 + { \
1.291 + new_data->size = (numRects); \
1.292 + (reg)->data = new_data; \
1.293 + } \
1.294 + } \
1.295 + } while (0)
1.296 +
1.297 +PIXMAN_EXPORT pixman_bool_t
1.298 +PREFIX (_equal) (region_type_t *reg1, region_type_t *reg2)
1.299 +{
1.300 + int i;
1.301 + box_type_t *rects1;
1.302 + box_type_t *rects2;
1.303 +
1.304 + if (reg1->extents.x1 != reg2->extents.x1)
1.305 + return FALSE;
1.306 +
1.307 + if (reg1->extents.x2 != reg2->extents.x2)
1.308 + return FALSE;
1.309 +
1.310 + if (reg1->extents.y1 != reg2->extents.y1)
1.311 + return FALSE;
1.312 +
1.313 + if (reg1->extents.y2 != reg2->extents.y2)
1.314 + return FALSE;
1.315 +
1.316 + if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2))
1.317 + return FALSE;
1.318 +
1.319 + rects1 = PIXREGION_RECTS (reg1);
1.320 + rects2 = PIXREGION_RECTS (reg2);
1.321 +
1.322 + for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++)
1.323 + {
1.324 + if (rects1[i].x1 != rects2[i].x1)
1.325 + return FALSE;
1.326 +
1.327 + if (rects1[i].x2 != rects2[i].x2)
1.328 + return FALSE;
1.329 +
1.330 + if (rects1[i].y1 != rects2[i].y1)
1.331 + return FALSE;
1.332 +
1.333 + if (rects1[i].y2 != rects2[i].y2)
1.334 + return FALSE;
1.335 + }
1.336 +
1.337 + return TRUE;
1.338 +}
1.339 +
1.340 +int
1.341 +PREFIX (_print) (region_type_t *rgn)
1.342 +{
1.343 + int num, size;
1.344 + int i;
1.345 + box_type_t * rects;
1.346 +
1.347 + num = PIXREGION_NUMRECTS (rgn);
1.348 + size = PIXREGION_SIZE (rgn);
1.349 + rects = PIXREGION_RECTS (rgn);
1.350 +
1.351 + fprintf (stderr, "num: %d size: %d\n", num, size);
1.352 + fprintf (stderr, "extents: %d %d %d %d\n",
1.353 + rgn->extents.x1,
1.354 + rgn->extents.y1,
1.355 + rgn->extents.x2,
1.356 + rgn->extents.y2);
1.357 +
1.358 + for (i = 0; i < num; i++)
1.359 + {
1.360 + fprintf (stderr, "%d %d %d %d \n",
1.361 + rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
1.362 + }
1.363 +
1.364 + fprintf (stderr, "\n");
1.365 +
1.366 + return(num);
1.367 +}
1.368 +
1.369 +
1.370 +PIXMAN_EXPORT void
1.371 +PREFIX (_init) (region_type_t *region)
1.372 +{
1.373 + region->extents = *pixman_region_empty_box;
1.374 + region->data = pixman_region_empty_data;
1.375 +}
1.376 +
1.377 +PIXMAN_EXPORT void
1.378 +PREFIX (_init_rect) (region_type_t * region,
1.379 + int x,
1.380 + int y,
1.381 + unsigned int width,
1.382 + unsigned int height)
1.383 +{
1.384 + region->extents.x1 = x;
1.385 + region->extents.y1 = y;
1.386 + region->extents.x2 = x + width;
1.387 + region->extents.y2 = y + height;
1.388 +
1.389 + if (!GOOD_RECT (®ion->extents))
1.390 + {
1.391 + if (BAD_RECT (®ion->extents))
1.392 + _pixman_log_error (FUNC, "Invalid rectangle passed");
1.393 + PREFIX (_init) (region);
1.394 + return;
1.395 + }
1.396 +
1.397 + region->data = NULL;
1.398 +}
1.399 +
1.400 +PIXMAN_EXPORT void
1.401 +PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents)
1.402 +{
1.403 + if (!GOOD_RECT (extents))
1.404 + {
1.405 + if (BAD_RECT (extents))
1.406 + _pixman_log_error (FUNC, "Invalid rectangle passed");
1.407 + PREFIX (_init) (region);
1.408 + return;
1.409 + }
1.410 + region->extents = *extents;
1.411 +
1.412 + region->data = NULL;
1.413 +}
1.414 +
1.415 +PIXMAN_EXPORT void
1.416 +PREFIX (_fini) (region_type_t *region)
1.417 +{
1.418 + GOOD (region);
1.419 + FREE_DATA (region);
1.420 +}
1.421 +
1.422 +PIXMAN_EXPORT int
1.423 +PREFIX (_n_rects) (region_type_t *region)
1.424 +{
1.425 + return PIXREGION_NUMRECTS (region);
1.426 +}
1.427 +
1.428 +PIXMAN_EXPORT box_type_t *
1.429 +PREFIX (_rectangles) (region_type_t *region,
1.430 + int *n_rects)
1.431 +{
1.432 + if (n_rects)
1.433 + *n_rects = PIXREGION_NUMRECTS (region);
1.434 +
1.435 + return PIXREGION_RECTS (region);
1.436 +}
1.437 +
1.438 +static pixman_bool_t
1.439 +pixman_break (region_type_t *region)
1.440 +{
1.441 + FREE_DATA (region);
1.442 +
1.443 + region->extents = *pixman_region_empty_box;
1.444 + region->data = pixman_broken_data;
1.445 +
1.446 + return FALSE;
1.447 +}
1.448 +
1.449 +static pixman_bool_t
1.450 +pixman_rect_alloc (region_type_t * region,
1.451 + int n)
1.452 +{
1.453 + region_data_type_t *data;
1.454 +
1.455 + if (!region->data)
1.456 + {
1.457 + n++;
1.458 + region->data = alloc_data (n);
1.459 +
1.460 + if (!region->data)
1.461 + return pixman_break (region);
1.462 +
1.463 + region->data->numRects = 1;
1.464 + *PIXREGION_BOXPTR (region) = region->extents;
1.465 + }
1.466 + else if (!region->data->size)
1.467 + {
1.468 + region->data = alloc_data (n);
1.469 +
1.470 + if (!region->data)
1.471 + return pixman_break (region);
1.472 +
1.473 + region->data->numRects = 0;
1.474 + }
1.475 + else
1.476 + {
1.477 + size_t data_size;
1.478 +
1.479 + if (n == 1)
1.480 + {
1.481 + n = region->data->numRects;
1.482 + if (n > 500) /* XXX pick numbers out of a hat */
1.483 + n = 250;
1.484 + }
1.485 +
1.486 + n += region->data->numRects;
1.487 + data_size = PIXREGION_SZOF (n);
1.488 +
1.489 + if (!data_size)
1.490 + {
1.491 + data = NULL;
1.492 + }
1.493 + else
1.494 + {
1.495 + data = (region_data_type_t *)
1.496 + realloc (region->data, PIXREGION_SZOF (n));
1.497 + }
1.498 +
1.499 + if (!data)
1.500 + return pixman_break (region);
1.501 +
1.502 + region->data = data;
1.503 + }
1.504 +
1.505 + region->data->size = n;
1.506 +
1.507 + return TRUE;
1.508 +}
1.509 +
1.510 +PIXMAN_EXPORT pixman_bool_t
1.511 +PREFIX (_copy) (region_type_t *dst, region_type_t *src)
1.512 +{
1.513 + GOOD (dst);
1.514 + GOOD (src);
1.515 +
1.516 + if (dst == src)
1.517 + return TRUE;
1.518 +
1.519 + dst->extents = src->extents;
1.520 +
1.521 + if (!src->data || !src->data->size)
1.522 + {
1.523 + FREE_DATA (dst);
1.524 + dst->data = src->data;
1.525 + return TRUE;
1.526 + }
1.527 +
1.528 + if (!dst->data || (dst->data->size < src->data->numRects))
1.529 + {
1.530 + FREE_DATA (dst);
1.531 +
1.532 + dst->data = alloc_data (src->data->numRects);
1.533 +
1.534 + if (!dst->data)
1.535 + return pixman_break (dst);
1.536 +
1.537 + dst->data->size = src->data->numRects;
1.538 + }
1.539 +
1.540 + dst->data->numRects = src->data->numRects;
1.541 +
1.542 + memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),
1.543 + dst->data->numRects * sizeof(box_type_t));
1.544 +
1.545 + return TRUE;
1.546 +}
1.547 +
1.548 +/*======================================================================
1.549 + * Generic Region Operator
1.550 + *====================================================================*/
1.551 +
1.552 +/*-
1.553 + *-----------------------------------------------------------------------
1.554 + * pixman_coalesce --
1.555 + * Attempt to merge the boxes in the current band with those in the
1.556 + * previous one. We are guaranteed that the current band extends to
1.557 + * the end of the rects array. Used only by pixman_op.
1.558 + *
1.559 + * Results:
1.560 + * The new index for the previous band.
1.561 + *
1.562 + * Side Effects:
1.563 + * If coalescing takes place:
1.564 + * - rectangles in the previous band will have their y2 fields
1.565 + * altered.
1.566 + * - region->data->numRects will be decreased.
1.567 + *
1.568 + *-----------------------------------------------------------------------
1.569 + */
1.570 +static inline int
1.571 +pixman_coalesce (region_type_t * region, /* Region to coalesce */
1.572 + int prev_start, /* Index of start of previous band */
1.573 + int cur_start) /* Index of start of current band */
1.574 +{
1.575 + box_type_t *prev_box; /* Current box in previous band */
1.576 + box_type_t *cur_box; /* Current box in current band */
1.577 + int numRects; /* Number rectangles in both bands */
1.578 + int y2; /* Bottom of current band */
1.579 +
1.580 + /*
1.581 + * Figure out how many rectangles are in the band.
1.582 + */
1.583 + numRects = cur_start - prev_start;
1.584 + critical_if_fail (numRects == region->data->numRects - cur_start);
1.585 +
1.586 + if (!numRects) return cur_start;
1.587 +
1.588 + /*
1.589 + * The bands may only be coalesced if the bottom of the previous
1.590 + * matches the top scanline of the current.
1.591 + */
1.592 + prev_box = PIXREGION_BOX (region, prev_start);
1.593 + cur_box = PIXREGION_BOX (region, cur_start);
1.594 + if (prev_box->y2 != cur_box->y1) return cur_start;
1.595 +
1.596 + /*
1.597 + * Make sure the bands have boxes in the same places. This
1.598 + * assumes that boxes have been added in such a way that they
1.599 + * cover the most area possible. I.e. two boxes in a band must
1.600 + * have some horizontal space between them.
1.601 + */
1.602 + y2 = cur_box->y2;
1.603 +
1.604 + do
1.605 + {
1.606 + if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2))
1.607 + return (cur_start);
1.608 +
1.609 + prev_box++;
1.610 + cur_box++;
1.611 + numRects--;
1.612 + }
1.613 + while (numRects);
1.614 +
1.615 + /*
1.616 + * The bands may be merged, so set the bottom y of each box
1.617 + * in the previous band to the bottom y of the current band.
1.618 + */
1.619 + numRects = cur_start - prev_start;
1.620 + region->data->numRects -= numRects;
1.621 +
1.622 + do
1.623 + {
1.624 + prev_box--;
1.625 + prev_box->y2 = y2;
1.626 + numRects--;
1.627 + }
1.628 + while (numRects);
1.629 +
1.630 + return prev_start;
1.631 +}
1.632 +
1.633 +/* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
1.634 +
1.635 +#define COALESCE(new_reg, prev_band, cur_band) \
1.636 + do \
1.637 + { \
1.638 + if (cur_band - prev_band == new_reg->data->numRects - cur_band) \
1.639 + prev_band = pixman_coalesce (new_reg, prev_band, cur_band); \
1.640 + else \
1.641 + prev_band = cur_band; \
1.642 + } while (0)
1.643 +
1.644 +/*-
1.645 + *-----------------------------------------------------------------------
1.646 + * pixman_region_append_non_o --
1.647 + * Handle a non-overlapping band for the union and subtract operations.
1.648 + * Just adds the (top/bottom-clipped) rectangles into the region.
1.649 + * Doesn't have to check for subsumption or anything.
1.650 + *
1.651 + * Results:
1.652 + * None.
1.653 + *
1.654 + * Side Effects:
1.655 + * region->data->numRects is incremented and the rectangles overwritten
1.656 + * with the rectangles we're passed.
1.657 + *
1.658 + *-----------------------------------------------------------------------
1.659 + */
1.660 +static inline pixman_bool_t
1.661 +pixman_region_append_non_o (region_type_t * region,
1.662 + box_type_t * r,
1.663 + box_type_t * r_end,
1.664 + int y1,
1.665 + int y2)
1.666 +{
1.667 + box_type_t *next_rect;
1.668 + int new_rects;
1.669 +
1.670 + new_rects = r_end - r;
1.671 +
1.672 + critical_if_fail (y1 < y2);
1.673 + critical_if_fail (new_rects != 0);
1.674 +
1.675 + /* Make sure we have enough space for all rectangles to be added */
1.676 + RECTALLOC (region, new_rects);
1.677 + next_rect = PIXREGION_TOP (region);
1.678 + region->data->numRects += new_rects;
1.679 +
1.680 + do
1.681 + {
1.682 + critical_if_fail (r->x1 < r->x2);
1.683 + ADDRECT (next_rect, r->x1, y1, r->x2, y2);
1.684 + r++;
1.685 + }
1.686 + while (r != r_end);
1.687 +
1.688 + return TRUE;
1.689 +}
1.690 +
1.691 +#define FIND_BAND(r, r_band_end, r_end, ry1) \
1.692 + do \
1.693 + { \
1.694 + ry1 = r->y1; \
1.695 + r_band_end = r + 1; \
1.696 + while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) { \
1.697 + r_band_end++; \
1.698 + } \
1.699 + } while (0)
1.700 +
1.701 +#define APPEND_REGIONS(new_reg, r, r_end) \
1.702 + do \
1.703 + { \
1.704 + int new_rects; \
1.705 + if ((new_rects = r_end - r)) { \
1.706 + RECTALLOC_BAIL (new_reg, new_rects, bail); \
1.707 + memmove ((char *)PIXREGION_TOP (new_reg), (char *)r, \
1.708 + new_rects * sizeof(box_type_t)); \
1.709 + new_reg->data->numRects += new_rects; \
1.710 + } \
1.711 + } while (0)
1.712 +
1.713 +/*-
1.714 + *-----------------------------------------------------------------------
1.715 + * pixman_op --
1.716 + * Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
1.717 + * pixman_region_subtract, pixman_region_intersect.... Both regions MUST have at least one
1.718 + * rectangle, and cannot be the same object.
1.719 + *
1.720 + * Results:
1.721 + * TRUE if successful.
1.722 + *
1.723 + * Side Effects:
1.724 + * The new region is overwritten.
1.725 + * overlap set to TRUE if overlap_func ever returns TRUE.
1.726 + *
1.727 + * Notes:
1.728 + * The idea behind this function is to view the two regions as sets.
1.729 + * Together they cover a rectangle of area that this function divides
1.730 + * into horizontal bands where points are covered only by one region
1.731 + * or by both. For the first case, the non_overlap_func is called with
1.732 + * each the band and the band's upper and lower extents. For the
1.733 + * second, the overlap_func is called to process the entire band. It
1.734 + * is responsible for clipping the rectangles in the band, though
1.735 + * this function provides the boundaries.
1.736 + * At the end of each band, the new region is coalesced, if possible,
1.737 + * to reduce the number of rectangles in the region.
1.738 + *
1.739 + *-----------------------------------------------------------------------
1.740 + */
1.741 +
1.742 +typedef pixman_bool_t (*overlap_proc_ptr) (region_type_t *region,
1.743 + box_type_t * r1,
1.744 + box_type_t * r1_end,
1.745 + box_type_t * r2,
1.746 + box_type_t * r2_end,
1.747 + int y1,
1.748 + int y2);
1.749 +
1.750 +static pixman_bool_t
1.751 +pixman_op (region_type_t * new_reg, /* Place to store result */
1.752 + region_type_t * reg1, /* First region in operation */
1.753 + region_type_t * reg2, /* 2d region in operation */
1.754 + overlap_proc_ptr overlap_func, /* Function to call for over-
1.755 + * lapping bands */
1.756 + int append_non1, /* Append non-overlapping bands
1.757 + * in region 1 ?
1.758 + */
1.759 + int append_non2 /* Append non-overlapping bands
1.760 + * in region 2 ?
1.761 + */
1.762 + )
1.763 +{
1.764 + box_type_t *r1; /* Pointer into first region */
1.765 + box_type_t *r2; /* Pointer into 2d region */
1.766 + box_type_t *r1_end; /* End of 1st region */
1.767 + box_type_t *r2_end; /* End of 2d region */
1.768 + int ybot; /* Bottom of intersection */
1.769 + int ytop; /* Top of intersection */
1.770 + region_data_type_t *old_data; /* Old data for new_reg */
1.771 + int prev_band; /* Index of start of
1.772 + * previous band in new_reg */
1.773 + int cur_band; /* Index of start of current
1.774 + * band in new_reg */
1.775 + box_type_t * r1_band_end; /* End of current band in r1 */
1.776 + box_type_t * r2_band_end; /* End of current band in r2 */
1.777 + int top; /* Top of non-overlapping band */
1.778 + int bot; /* Bottom of non-overlapping band*/
1.779 + int r1y1; /* Temps for r1->y1 and r2->y1 */
1.780 + int r2y1;
1.781 + int new_size;
1.782 + int numRects;
1.783 +
1.784 + /*
1.785 + * Break any region computed from a broken region
1.786 + */
1.787 + if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
1.788 + return pixman_break (new_reg);
1.789 +
1.790 + /*
1.791 + * Initialization:
1.792 + * set r1, r2, r1_end and r2_end appropriately, save the rectangles
1.793 + * of the destination region until the end in case it's one of
1.794 + * the two source regions, then mark the "new" region empty, allocating
1.795 + * another array of rectangles for it to use.
1.796 + */
1.797 +
1.798 + r1 = PIXREGION_RECTS (reg1);
1.799 + new_size = PIXREGION_NUMRECTS (reg1);
1.800 + r1_end = r1 + new_size;
1.801 +
1.802 + numRects = PIXREGION_NUMRECTS (reg2);
1.803 + r2 = PIXREGION_RECTS (reg2);
1.804 + r2_end = r2 + numRects;
1.805 +
1.806 + critical_if_fail (r1 != r1_end);
1.807 + critical_if_fail (r2 != r2_end);
1.808 +
1.809 + old_data = (region_data_type_t *)NULL;
1.810 +
1.811 + if (((new_reg == reg1) && (new_size > 1)) ||
1.812 + ((new_reg == reg2) && (numRects > 1)))
1.813 + {
1.814 + old_data = new_reg->data;
1.815 + new_reg->data = pixman_region_empty_data;
1.816 + }
1.817 +
1.818 + /* guess at new size */
1.819 + if (numRects > new_size)
1.820 + new_size = numRects;
1.821 +
1.822 + new_size <<= 1;
1.823 +
1.824 + if (!new_reg->data)
1.825 + new_reg->data = pixman_region_empty_data;
1.826 + else if (new_reg->data->size)
1.827 + new_reg->data->numRects = 0;
1.828 +
1.829 + if (new_size > new_reg->data->size)
1.830 + {
1.831 + if (!pixman_rect_alloc (new_reg, new_size))
1.832 + {
1.833 + free (old_data);
1.834 + return FALSE;
1.835 + }
1.836 + }
1.837 +
1.838 + /*
1.839 + * Initialize ybot.
1.840 + * In the upcoming loop, ybot and ytop serve different functions depending
1.841 + * on whether the band being handled is an overlapping or non-overlapping
1.842 + * band.
1.843 + * In the case of a non-overlapping band (only one of the regions
1.844 + * has points in the band), ybot is the bottom of the most recent
1.845 + * intersection and thus clips the top of the rectangles in that band.
1.846 + * ytop is the top of the next intersection between the two regions and
1.847 + * serves to clip the bottom of the rectangles in the current band.
1.848 + * For an overlapping band (where the two regions intersect), ytop clips
1.849 + * the top of the rectangles of both regions and ybot clips the bottoms.
1.850 + */
1.851 +
1.852 + ybot = MIN (r1->y1, r2->y1);
1.853 +
1.854 + /*
1.855 + * prev_band serves to mark the start of the previous band so rectangles
1.856 + * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
1.857 + * In the beginning, there is no previous band, so prev_band == cur_band
1.858 + * (cur_band is set later on, of course, but the first band will always
1.859 + * start at index 0). prev_band and cur_band must be indices because of
1.860 + * the possible expansion, and resultant moving, of the new region's
1.861 + * array of rectangles.
1.862 + */
1.863 + prev_band = 0;
1.864 +
1.865 + do
1.866 + {
1.867 + /*
1.868 + * This algorithm proceeds one source-band (as opposed to a
1.869 + * destination band, which is determined by where the two regions
1.870 + * intersect) at a time. r1_band_end and r2_band_end serve to mark the
1.871 + * rectangle after the last one in the current band for their
1.872 + * respective regions.
1.873 + */
1.874 + critical_if_fail (r1 != r1_end);
1.875 + critical_if_fail (r2 != r2_end);
1.876 +
1.877 + FIND_BAND (r1, r1_band_end, r1_end, r1y1);
1.878 + FIND_BAND (r2, r2_band_end, r2_end, r2y1);
1.879 +
1.880 + /*
1.881 + * First handle the band that doesn't intersect, if any.
1.882 + *
1.883 + * Note that attention is restricted to one band in the
1.884 + * non-intersecting region at once, so if a region has n
1.885 + * bands between the current position and the next place it overlaps
1.886 + * the other, this entire loop will be passed through n times.
1.887 + */
1.888 + if (r1y1 < r2y1)
1.889 + {
1.890 + if (append_non1)
1.891 + {
1.892 + top = MAX (r1y1, ybot);
1.893 + bot = MIN (r1->y2, r2y1);
1.894 + if (top != bot)
1.895 + {
1.896 + cur_band = new_reg->data->numRects;
1.897 + if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))
1.898 + goto bail;
1.899 + COALESCE (new_reg, prev_band, cur_band);
1.900 + }
1.901 + }
1.902 + ytop = r2y1;
1.903 + }
1.904 + else if (r2y1 < r1y1)
1.905 + {
1.906 + if (append_non2)
1.907 + {
1.908 + top = MAX (r2y1, ybot);
1.909 + bot = MIN (r2->y2, r1y1);
1.910 +
1.911 + if (top != bot)
1.912 + {
1.913 + cur_band = new_reg->data->numRects;
1.914 +
1.915 + if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))
1.916 + goto bail;
1.917 +
1.918 + COALESCE (new_reg, prev_band, cur_band);
1.919 + }
1.920 + }
1.921 + ytop = r1y1;
1.922 + }
1.923 + else
1.924 + {
1.925 + ytop = r1y1;
1.926 + }
1.927 +
1.928 + /*
1.929 + * Now see if we've hit an intersecting band. The two bands only
1.930 + * intersect if ybot > ytop
1.931 + */
1.932 + ybot = MIN (r1->y2, r2->y2);
1.933 + if (ybot > ytop)
1.934 + {
1.935 + cur_band = new_reg->data->numRects;
1.936 +
1.937 + if (!(*overlap_func)(new_reg,
1.938 + r1, r1_band_end,
1.939 + r2, r2_band_end,
1.940 + ytop, ybot))
1.941 + {
1.942 + goto bail;
1.943 + }
1.944 +
1.945 + COALESCE (new_reg, prev_band, cur_band);
1.946 + }
1.947 +
1.948 + /*
1.949 + * If we've finished with a band (y2 == ybot) we skip forward
1.950 + * in the region to the next band.
1.951 + */
1.952 + if (r1->y2 == ybot)
1.953 + r1 = r1_band_end;
1.954 +
1.955 + if (r2->y2 == ybot)
1.956 + r2 = r2_band_end;
1.957 +
1.958 + }
1.959 + while (r1 != r1_end && r2 != r2_end);
1.960 +
1.961 + /*
1.962 + * Deal with whichever region (if any) still has rectangles left.
1.963 + *
1.964 + * We only need to worry about banding and coalescing for the very first
1.965 + * band left. After that, we can just group all remaining boxes,
1.966 + * regardless of how many bands, into one final append to the list.
1.967 + */
1.968 +
1.969 + if ((r1 != r1_end) && append_non1)
1.970 + {
1.971 + /* Do first non_overlap1Func call, which may be able to coalesce */
1.972 + FIND_BAND (r1, r1_band_end, r1_end, r1y1);
1.973 +
1.974 + cur_band = new_reg->data->numRects;
1.975 +
1.976 + if (!pixman_region_append_non_o (new_reg,
1.977 + r1, r1_band_end,
1.978 + MAX (r1y1, ybot), r1->y2))
1.979 + {
1.980 + goto bail;
1.981 + }
1.982 +
1.983 + COALESCE (new_reg, prev_band, cur_band);
1.984 +
1.985 + /* Just append the rest of the boxes */
1.986 + APPEND_REGIONS (new_reg, r1_band_end, r1_end);
1.987 + }
1.988 + else if ((r2 != r2_end) && append_non2)
1.989 + {
1.990 + /* Do first non_overlap2Func call, which may be able to coalesce */
1.991 + FIND_BAND (r2, r2_band_end, r2_end, r2y1);
1.992 +
1.993 + cur_band = new_reg->data->numRects;
1.994 +
1.995 + if (!pixman_region_append_non_o (new_reg,
1.996 + r2, r2_band_end,
1.997 + MAX (r2y1, ybot), r2->y2))
1.998 + {
1.999 + goto bail;
1.1000 + }
1.1001 +
1.1002 + COALESCE (new_reg, prev_band, cur_band);
1.1003 +
1.1004 + /* Append rest of boxes */
1.1005 + APPEND_REGIONS (new_reg, r2_band_end, r2_end);
1.1006 + }
1.1007 +
1.1008 + free (old_data);
1.1009 +
1.1010 + if (!(numRects = new_reg->data->numRects))
1.1011 + {
1.1012 + FREE_DATA (new_reg);
1.1013 + new_reg->data = pixman_region_empty_data;
1.1014 + }
1.1015 + else if (numRects == 1)
1.1016 + {
1.1017 + new_reg->extents = *PIXREGION_BOXPTR (new_reg);
1.1018 + FREE_DATA (new_reg);
1.1019 + new_reg->data = (region_data_type_t *)NULL;
1.1020 + }
1.1021 + else
1.1022 + {
1.1023 + DOWNSIZE (new_reg, numRects);
1.1024 + }
1.1025 +
1.1026 + return TRUE;
1.1027 +
1.1028 +bail:
1.1029 + free (old_data);
1.1030 +
1.1031 + return pixman_break (new_reg);
1.1032 +}
1.1033 +
1.1034 +/*-
1.1035 + *-----------------------------------------------------------------------
1.1036 + * pixman_set_extents --
1.1037 + * Reset the extents of a region to what they should be. Called by
1.1038 + * pixman_region_subtract and pixman_region_intersect as they can't
1.1039 + * figure it out along the way or do so easily, as pixman_region_union can.
1.1040 + *
1.1041 + * Results:
1.1042 + * None.
1.1043 + *
1.1044 + * Side Effects:
1.1045 + * The region's 'extents' structure is overwritten.
1.1046 + *
1.1047 + *-----------------------------------------------------------------------
1.1048 + */
1.1049 +static void
1.1050 +pixman_set_extents (region_type_t *region)
1.1051 +{
1.1052 + box_type_t *box, *box_end;
1.1053 +
1.1054 + if (!region->data)
1.1055 + return;
1.1056 +
1.1057 + if (!region->data->size)
1.1058 + {
1.1059 + region->extents.x2 = region->extents.x1;
1.1060 + region->extents.y2 = region->extents.y1;
1.1061 + return;
1.1062 + }
1.1063 +
1.1064 + box = PIXREGION_BOXPTR (region);
1.1065 + box_end = PIXREGION_END (region);
1.1066 +
1.1067 + /*
1.1068 + * Since box is the first rectangle in the region, it must have the
1.1069 + * smallest y1 and since box_end is the last rectangle in the region,
1.1070 + * it must have the largest y2, because of banding. Initialize x1 and
1.1071 + * x2 from box and box_end, resp., as good things to initialize them
1.1072 + * to...
1.1073 + */
1.1074 + region->extents.x1 = box->x1;
1.1075 + region->extents.y1 = box->y1;
1.1076 + region->extents.x2 = box_end->x2;
1.1077 + region->extents.y2 = box_end->y2;
1.1078 +
1.1079 + critical_if_fail (region->extents.y1 < region->extents.y2);
1.1080 +
1.1081 + while (box <= box_end)
1.1082 + {
1.1083 + if (box->x1 < region->extents.x1)
1.1084 + region->extents.x1 = box->x1;
1.1085 + if (box->x2 > region->extents.x2)
1.1086 + region->extents.x2 = box->x2;
1.1087 + box++;
1.1088 + }
1.1089 +
1.1090 + critical_if_fail (region->extents.x1 < region->extents.x2);
1.1091 +}
1.1092 +
1.1093 +/*======================================================================
1.1094 + * Region Intersection
1.1095 + *====================================================================*/
1.1096 +/*-
1.1097 + *-----------------------------------------------------------------------
1.1098 + * pixman_region_intersect_o --
1.1099 + * Handle an overlapping band for pixman_region_intersect.
1.1100 + *
1.1101 + * Results:
1.1102 + * TRUE if successful.
1.1103 + *
1.1104 + * Side Effects:
1.1105 + * Rectangles may be added to the region.
1.1106 + *
1.1107 + *-----------------------------------------------------------------------
1.1108 + */
1.1109 +/*ARGSUSED*/
1.1110 +static pixman_bool_t
1.1111 +pixman_region_intersect_o (region_type_t *region,
1.1112 + box_type_t * r1,
1.1113 + box_type_t * r1_end,
1.1114 + box_type_t * r2,
1.1115 + box_type_t * r2_end,
1.1116 + int y1,
1.1117 + int y2)
1.1118 +{
1.1119 + int x1;
1.1120 + int x2;
1.1121 + box_type_t * next_rect;
1.1122 +
1.1123 + next_rect = PIXREGION_TOP (region);
1.1124 +
1.1125 + critical_if_fail (y1 < y2);
1.1126 + critical_if_fail (r1 != r1_end && r2 != r2_end);
1.1127 +
1.1128 + do
1.1129 + {
1.1130 + x1 = MAX (r1->x1, r2->x1);
1.1131 + x2 = MIN (r1->x2, r2->x2);
1.1132 +
1.1133 + /*
1.1134 + * If there's any overlap between the two rectangles, add that
1.1135 + * overlap to the new region.
1.1136 + */
1.1137 + if (x1 < x2)
1.1138 + NEWRECT (region, next_rect, x1, y1, x2, y2);
1.1139 +
1.1140 + /*
1.1141 + * Advance the pointer(s) with the leftmost right side, since the next
1.1142 + * rectangle on that list may still overlap the other region's
1.1143 + * current rectangle.
1.1144 + */
1.1145 + if (r1->x2 == x2)
1.1146 + {
1.1147 + r1++;
1.1148 + }
1.1149 + if (r2->x2 == x2)
1.1150 + {
1.1151 + r2++;
1.1152 + }
1.1153 + }
1.1154 + while ((r1 != r1_end) && (r2 != r2_end));
1.1155 +
1.1156 + return TRUE;
1.1157 +}
1.1158 +
1.1159 +PIXMAN_EXPORT pixman_bool_t
1.1160 +PREFIX (_intersect) (region_type_t * new_reg,
1.1161 + region_type_t * reg1,
1.1162 + region_type_t * reg2)
1.1163 +{
1.1164 + GOOD (reg1);
1.1165 + GOOD (reg2);
1.1166 + GOOD (new_reg);
1.1167 +
1.1168 + /* check for trivial reject */
1.1169 + if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||
1.1170 + !EXTENTCHECK (®1->extents, ®2->extents))
1.1171 + {
1.1172 + /* Covers about 20% of all cases */
1.1173 + FREE_DATA (new_reg);
1.1174 + new_reg->extents.x2 = new_reg->extents.x1;
1.1175 + new_reg->extents.y2 = new_reg->extents.y1;
1.1176 + if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
1.1177 + {
1.1178 + new_reg->data = pixman_broken_data;
1.1179 + return FALSE;
1.1180 + }
1.1181 + else
1.1182 + {
1.1183 + new_reg->data = pixman_region_empty_data;
1.1184 + }
1.1185 + }
1.1186 + else if (!reg1->data && !reg2->data)
1.1187 + {
1.1188 + /* Covers about 80% of cases that aren't trivially rejected */
1.1189 + new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);
1.1190 + new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);
1.1191 + new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);
1.1192 + new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);
1.1193 +
1.1194 + FREE_DATA (new_reg);
1.1195 +
1.1196 + new_reg->data = (region_data_type_t *)NULL;
1.1197 + }
1.1198 + else if (!reg2->data && SUBSUMES (®2->extents, ®1->extents))
1.1199 + {
1.1200 + return PREFIX (_copy) (new_reg, reg1);
1.1201 + }
1.1202 + else if (!reg1->data && SUBSUMES (®1->extents, ®2->extents))
1.1203 + {
1.1204 + return PREFIX (_copy) (new_reg, reg2);
1.1205 + }
1.1206 + else if (reg1 == reg2)
1.1207 + {
1.1208 + return PREFIX (_copy) (new_reg, reg1);
1.1209 + }
1.1210 + else
1.1211 + {
1.1212 + /* General purpose intersection */
1.1213 +
1.1214 + if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE))
1.1215 + return FALSE;
1.1216 +
1.1217 + pixman_set_extents (new_reg);
1.1218 + }
1.1219 +
1.1220 + GOOD (new_reg);
1.1221 + return(TRUE);
1.1222 +}
1.1223 +
1.1224 +#define MERGERECT(r) \
1.1225 + do \
1.1226 + { \
1.1227 + if (r->x1 <= x2) \
1.1228 + { \
1.1229 + /* Merge with current rectangle */ \
1.1230 + if (x2 < r->x2) \
1.1231 + x2 = r->x2; \
1.1232 + } \
1.1233 + else \
1.1234 + { \
1.1235 + /* Add current rectangle, start new one */ \
1.1236 + NEWRECT (region, next_rect, x1, y1, x2, y2); \
1.1237 + x1 = r->x1; \
1.1238 + x2 = r->x2; \
1.1239 + } \
1.1240 + r++; \
1.1241 + } while (0)
1.1242 +
1.1243 +/*======================================================================
1.1244 + * Region Union
1.1245 + *====================================================================*/
1.1246 +
1.1247 +/*-
1.1248 + *-----------------------------------------------------------------------
1.1249 + * pixman_region_union_o --
1.1250 + * Handle an overlapping band for the union operation. Picks the
1.1251 + * left-most rectangle each time and merges it into the region.
1.1252 + *
1.1253 + * Results:
1.1254 + * TRUE if successful.
1.1255 + *
1.1256 + * Side Effects:
1.1257 + * region is overwritten.
1.1258 + * overlap is set to TRUE if any boxes overlap.
1.1259 + *
1.1260 + *-----------------------------------------------------------------------
1.1261 + */
1.1262 +static pixman_bool_t
1.1263 +pixman_region_union_o (region_type_t *region,
1.1264 + box_type_t * r1,
1.1265 + box_type_t * r1_end,
1.1266 + box_type_t * r2,
1.1267 + box_type_t * r2_end,
1.1268 + int y1,
1.1269 + int y2)
1.1270 +{
1.1271 + box_type_t *next_rect;
1.1272 + int x1; /* left and right side of current union */
1.1273 + int x2;
1.1274 +
1.1275 + critical_if_fail (y1 < y2);
1.1276 + critical_if_fail (r1 != r1_end && r2 != r2_end);
1.1277 +
1.1278 + next_rect = PIXREGION_TOP (region);
1.1279 +
1.1280 + /* Start off current rectangle */
1.1281 + if (r1->x1 < r2->x1)
1.1282 + {
1.1283 + x1 = r1->x1;
1.1284 + x2 = r1->x2;
1.1285 + r1++;
1.1286 + }
1.1287 + else
1.1288 + {
1.1289 + x1 = r2->x1;
1.1290 + x2 = r2->x2;
1.1291 + r2++;
1.1292 + }
1.1293 + while (r1 != r1_end && r2 != r2_end)
1.1294 + {
1.1295 + if (r1->x1 < r2->x1)
1.1296 + MERGERECT (r1);
1.1297 + else
1.1298 + MERGERECT (r2);
1.1299 + }
1.1300 +
1.1301 + /* Finish off whoever (if any) is left */
1.1302 + if (r1 != r1_end)
1.1303 + {
1.1304 + do
1.1305 + {
1.1306 + MERGERECT (r1);
1.1307 + }
1.1308 + while (r1 != r1_end);
1.1309 + }
1.1310 + else if (r2 != r2_end)
1.1311 + {
1.1312 + do
1.1313 + {
1.1314 + MERGERECT (r2);
1.1315 + }
1.1316 + while (r2 != r2_end);
1.1317 + }
1.1318 +
1.1319 + /* Add current rectangle */
1.1320 + NEWRECT (region, next_rect, x1, y1, x2, y2);
1.1321 +
1.1322 + return TRUE;
1.1323 +}
1.1324 +
1.1325 +PIXMAN_EXPORT pixman_bool_t
1.1326 +PREFIX(_intersect_rect) (region_type_t *dest,
1.1327 + region_type_t *source,
1.1328 + int x, int y,
1.1329 + unsigned int width,
1.1330 + unsigned int height)
1.1331 +{
1.1332 + region_type_t region;
1.1333 +
1.1334 + region.data = NULL;
1.1335 + region.extents.x1 = x;
1.1336 + region.extents.y1 = y;
1.1337 + region.extents.x2 = x + width;
1.1338 + region.extents.y2 = y + height;
1.1339 +
1.1340 + return PREFIX(_intersect) (dest, source, ®ion);
1.1341 +}
1.1342 +
1.1343 +/* Convenience function for performing union of region with a
1.1344 + * single rectangle
1.1345 + */
1.1346 +PIXMAN_EXPORT pixman_bool_t
1.1347 +PREFIX (_union_rect) (region_type_t *dest,
1.1348 + region_type_t *source,
1.1349 + int x,
1.1350 + int y,
1.1351 + unsigned int width,
1.1352 + unsigned int height)
1.1353 +{
1.1354 + region_type_t region;
1.1355 +
1.1356 + region.extents.x1 = x;
1.1357 + region.extents.y1 = y;
1.1358 + region.extents.x2 = x + width;
1.1359 + region.extents.y2 = y + height;
1.1360 +
1.1361 + if (!GOOD_RECT (®ion.extents))
1.1362 + {
1.1363 + if (BAD_RECT (®ion.extents))
1.1364 + _pixman_log_error (FUNC, "Invalid rectangle passed");
1.1365 + return PREFIX (_copy) (dest, source);
1.1366 + }
1.1367 +
1.1368 + region.data = NULL;
1.1369 +
1.1370 + return PREFIX (_union) (dest, source, ®ion);
1.1371 +}
1.1372 +
1.1373 +PIXMAN_EXPORT pixman_bool_t
1.1374 +PREFIX (_union) (region_type_t *new_reg,
1.1375 + region_type_t *reg1,
1.1376 + region_type_t *reg2)
1.1377 +{
1.1378 + /* Return TRUE if some overlap
1.1379 + * between reg1, reg2
1.1380 + */
1.1381 + GOOD (reg1);
1.1382 + GOOD (reg2);
1.1383 + GOOD (new_reg);
1.1384 +
1.1385 + /* checks all the simple cases */
1.1386 +
1.1387 + /*
1.1388 + * Region 1 and 2 are the same
1.1389 + */
1.1390 + if (reg1 == reg2)
1.1391 + return PREFIX (_copy) (new_reg, reg1);
1.1392 +
1.1393 + /*
1.1394 + * Region 1 is empty
1.1395 + */
1.1396 + if (PIXREGION_NIL (reg1))
1.1397 + {
1.1398 + if (PIXREGION_NAR (reg1))
1.1399 + return pixman_break (new_reg);
1.1400 +
1.1401 + if (new_reg != reg2)
1.1402 + return PREFIX (_copy) (new_reg, reg2);
1.1403 +
1.1404 + return TRUE;
1.1405 + }
1.1406 +
1.1407 + /*
1.1408 + * Region 2 is empty
1.1409 + */
1.1410 + if (PIXREGION_NIL (reg2))
1.1411 + {
1.1412 + if (PIXREGION_NAR (reg2))
1.1413 + return pixman_break (new_reg);
1.1414 +
1.1415 + if (new_reg != reg1)
1.1416 + return PREFIX (_copy) (new_reg, reg1);
1.1417 +
1.1418 + return TRUE;
1.1419 + }
1.1420 +
1.1421 + /*
1.1422 + * Region 1 completely subsumes region 2
1.1423 + */
1.1424 + if (!reg1->data && SUBSUMES (®1->extents, ®2->extents))
1.1425 + {
1.1426 + if (new_reg != reg1)
1.1427 + return PREFIX (_copy) (new_reg, reg1);
1.1428 +
1.1429 + return TRUE;
1.1430 + }
1.1431 +
1.1432 + /*
1.1433 + * Region 2 completely subsumes region 1
1.1434 + */
1.1435 + if (!reg2->data && SUBSUMES (®2->extents, ®1->extents))
1.1436 + {
1.1437 + if (new_reg != reg2)
1.1438 + return PREFIX (_copy) (new_reg, reg2);
1.1439 +
1.1440 + return TRUE;
1.1441 + }
1.1442 +
1.1443 + if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE))
1.1444 + return FALSE;
1.1445 +
1.1446 + new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);
1.1447 + new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);
1.1448 + new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);
1.1449 + new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);
1.1450 +
1.1451 + GOOD (new_reg);
1.1452 +
1.1453 + return TRUE;
1.1454 +}
1.1455 +
1.1456 +/*======================================================================
1.1457 + * Batch Rectangle Union
1.1458 + *====================================================================*/
1.1459 +
1.1460 +#define EXCHANGE_RECTS(a, b) \
1.1461 + { \
1.1462 + box_type_t t; \
1.1463 + t = rects[a]; \
1.1464 + rects[a] = rects[b]; \
1.1465 + rects[b] = t; \
1.1466 + }
1.1467 +
1.1468 +static void
1.1469 +quick_sort_rects (
1.1470 + box_type_t rects[],
1.1471 + int numRects)
1.1472 +{
1.1473 + int y1;
1.1474 + int x1;
1.1475 + int i, j;
1.1476 + box_type_t *r;
1.1477 +
1.1478 + /* Always called with numRects > 1 */
1.1479 +
1.1480 + do
1.1481 + {
1.1482 + if (numRects == 2)
1.1483 + {
1.1484 + if (rects[0].y1 > rects[1].y1 ||
1.1485 + (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
1.1486 + {
1.1487 + EXCHANGE_RECTS (0, 1);
1.1488 + }
1.1489 +
1.1490 + return;
1.1491 + }
1.1492 +
1.1493 + /* Choose partition element, stick in location 0 */
1.1494 + EXCHANGE_RECTS (0, numRects >> 1);
1.1495 + y1 = rects[0].y1;
1.1496 + x1 = rects[0].x1;
1.1497 +
1.1498 + /* Partition array */
1.1499 + i = 0;
1.1500 + j = numRects;
1.1501 +
1.1502 + do
1.1503 + {
1.1504 + r = &(rects[i]);
1.1505 + do
1.1506 + {
1.1507 + r++;
1.1508 + i++;
1.1509 + }
1.1510 + while (i != numRects && (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
1.1511 +
1.1512 + r = &(rects[j]);
1.1513 + do
1.1514 + {
1.1515 + r--;
1.1516 + j--;
1.1517 + }
1.1518 + while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
1.1519 +
1.1520 + if (i < j)
1.1521 + EXCHANGE_RECTS (i, j);
1.1522 + }
1.1523 + while (i < j);
1.1524 +
1.1525 + /* Move partition element back to middle */
1.1526 + EXCHANGE_RECTS (0, j);
1.1527 +
1.1528 + /* Recurse */
1.1529 + if (numRects - j - 1 > 1)
1.1530 + quick_sort_rects (&rects[j + 1], numRects - j - 1);
1.1531 +
1.1532 + numRects = j;
1.1533 + }
1.1534 + while (numRects > 1);
1.1535 +}
1.1536 +
1.1537 +/*-
1.1538 + *-----------------------------------------------------------------------
1.1539 + * pixman_region_validate --
1.1540 + *
1.1541 + * Take a ``region'' which is a non-y-x-banded random collection of
1.1542 + * rectangles, and compute a nice region which is the union of all the
1.1543 + * rectangles.
1.1544 + *
1.1545 + * Results:
1.1546 + * TRUE if successful.
1.1547 + *
1.1548 + * Side Effects:
1.1549 + * The passed-in ``region'' may be modified.
1.1550 + * overlap set to TRUE if any retangles overlapped,
1.1551 + * else FALSE;
1.1552 + *
1.1553 + * Strategy:
1.1554 + * Step 1. Sort the rectangles into ascending order with primary key y1
1.1555 + * and secondary key x1.
1.1556 + *
1.1557 + * Step 2. Split the rectangles into the minimum number of proper y-x
1.1558 + * banded regions. This may require horizontally merging
1.1559 + * rectangles, and vertically coalescing bands. With any luck,
1.1560 + * this step in an identity transformation (ala the Box widget),
1.1561 + * or a coalescing into 1 box (ala Menus).
1.1562 + *
1.1563 + * Step 3. Merge the separate regions down to a single region by calling
1.1564 + * pixman_region_union. Maximize the work each pixman_region_union call does by using
1.1565 + * a binary merge.
1.1566 + *
1.1567 + *-----------------------------------------------------------------------
1.1568 + */
1.1569 +
1.1570 +static pixman_bool_t
1.1571 +validate (region_type_t * badreg)
1.1572 +{
1.1573 + /* Descriptor for regions under construction in Step 2. */
1.1574 + typedef struct
1.1575 + {
1.1576 + region_type_t reg;
1.1577 + int prev_band;
1.1578 + int cur_band;
1.1579 + } region_info_t;
1.1580 +
1.1581 + region_info_t stack_regions[64];
1.1582 +
1.1583 + int numRects; /* Original numRects for badreg */
1.1584 + region_info_t *ri; /* Array of current regions */
1.1585 + int num_ri; /* Number of entries used in ri */
1.1586 + int size_ri; /* Number of entries available in ri */
1.1587 + int i; /* Index into rects */
1.1588 + int j; /* Index into ri */
1.1589 + region_info_t *rit; /* &ri[j] */
1.1590 + region_type_t *reg; /* ri[j].reg */
1.1591 + box_type_t *box; /* Current box in rects */
1.1592 + box_type_t *ri_box; /* Last box in ri[j].reg */
1.1593 + region_type_t *hreg; /* ri[j_half].reg */
1.1594 + pixman_bool_t ret = TRUE;
1.1595 +
1.1596 + if (!badreg->data)
1.1597 + {
1.1598 + GOOD (badreg);
1.1599 + return TRUE;
1.1600 + }
1.1601 +
1.1602 + numRects = badreg->data->numRects;
1.1603 + if (!numRects)
1.1604 + {
1.1605 + if (PIXREGION_NAR (badreg))
1.1606 + return FALSE;
1.1607 + GOOD (badreg);
1.1608 + return TRUE;
1.1609 + }
1.1610 +
1.1611 + if (badreg->extents.x1 < badreg->extents.x2)
1.1612 + {
1.1613 + if ((numRects) == 1)
1.1614 + {
1.1615 + FREE_DATA (badreg);
1.1616 + badreg->data = (region_data_type_t *) NULL;
1.1617 + }
1.1618 + else
1.1619 + {
1.1620 + DOWNSIZE (badreg, numRects);
1.1621 + }
1.1622 +
1.1623 + GOOD (badreg);
1.1624 +
1.1625 + return TRUE;
1.1626 + }
1.1627 +
1.1628 + /* Step 1: Sort the rects array into ascending (y1, x1) order */
1.1629 + quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects);
1.1630 +
1.1631 + /* Step 2: Scatter the sorted array into the minimum number of regions */
1.1632 +
1.1633 + /* Set up the first region to be the first rectangle in badreg */
1.1634 + /* Note that step 2 code will never overflow the ri[0].reg rects array */
1.1635 + ri = stack_regions;
1.1636 + size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]);
1.1637 + num_ri = 1;
1.1638 + ri[0].prev_band = 0;
1.1639 + ri[0].cur_band = 0;
1.1640 + ri[0].reg = *badreg;
1.1641 + box = PIXREGION_BOXPTR (&ri[0].reg);
1.1642 + ri[0].reg.extents = *box;
1.1643 + ri[0].reg.data->numRects = 1;
1.1644 + badreg->extents = *pixman_region_empty_box;
1.1645 + badreg->data = pixman_region_empty_data;
1.1646 +
1.1647 + /* Now scatter rectangles into the minimum set of valid regions. If the
1.1648 + * next rectangle to be added to a region would force an existing rectangle
1.1649 + * in the region to be split up in order to maintain y-x banding, just
1.1650 + * forget it. Try the next region. If it doesn't fit cleanly into any
1.1651 + * region, make a new one.
1.1652 + */
1.1653 +
1.1654 + for (i = numRects; --i > 0;)
1.1655 + {
1.1656 + box++;
1.1657 + /* Look for a region to append box to */
1.1658 + for (j = num_ri, rit = ri; --j >= 0; rit++)
1.1659 + {
1.1660 + reg = &rit->reg;
1.1661 + ri_box = PIXREGION_END (reg);
1.1662 +
1.1663 + if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2)
1.1664 + {
1.1665 + /* box is in same band as ri_box. Merge or append it */
1.1666 + if (box->x1 <= ri_box->x2)
1.1667 + {
1.1668 + /* Merge it with ri_box */
1.1669 + if (box->x2 > ri_box->x2)
1.1670 + ri_box->x2 = box->x2;
1.1671 + }
1.1672 + else
1.1673 + {
1.1674 + RECTALLOC_BAIL (reg, 1, bail);
1.1675 + *PIXREGION_TOP (reg) = *box;
1.1676 + reg->data->numRects++;
1.1677 + }
1.1678 +
1.1679 + goto next_rect; /* So sue me */
1.1680 + }
1.1681 + else if (box->y1 >= ri_box->y2)
1.1682 + {
1.1683 + /* Put box into new band */
1.1684 + if (reg->extents.x2 < ri_box->x2)
1.1685 + reg->extents.x2 = ri_box->x2;
1.1686 +
1.1687 + if (reg->extents.x1 > box->x1)
1.1688 + reg->extents.x1 = box->x1;
1.1689 +
1.1690 + COALESCE (reg, rit->prev_band, rit->cur_band);
1.1691 + rit->cur_band = reg->data->numRects;
1.1692 + RECTALLOC_BAIL (reg, 1, bail);
1.1693 + *PIXREGION_TOP (reg) = *box;
1.1694 + reg->data->numRects++;
1.1695 +
1.1696 + goto next_rect;
1.1697 + }
1.1698 + /* Well, this region was inappropriate. Try the next one. */
1.1699 + } /* for j */
1.1700 +
1.1701 + /* Uh-oh. No regions were appropriate. Create a new one. */
1.1702 + if (size_ri == num_ri)
1.1703 + {
1.1704 + size_t data_size;
1.1705 +
1.1706 + /* Oops, allocate space for new region information */
1.1707 + size_ri <<= 1;
1.1708 +
1.1709 + data_size = size_ri * sizeof(region_info_t);
1.1710 + if (data_size / size_ri != sizeof(region_info_t))
1.1711 + goto bail;
1.1712 +
1.1713 + if (ri == stack_regions)
1.1714 + {
1.1715 + rit = malloc (data_size);
1.1716 + if (!rit)
1.1717 + goto bail;
1.1718 + memcpy (rit, ri, num_ri * sizeof (region_info_t));
1.1719 + }
1.1720 + else
1.1721 + {
1.1722 + rit = (region_info_t *) realloc (ri, data_size);
1.1723 + if (!rit)
1.1724 + goto bail;
1.1725 + }
1.1726 + ri = rit;
1.1727 + rit = &ri[num_ri];
1.1728 + }
1.1729 + num_ri++;
1.1730 + rit->prev_band = 0;
1.1731 + rit->cur_band = 0;
1.1732 + rit->reg.extents = *box;
1.1733 + rit->reg.data = (region_data_type_t *)NULL;
1.1734 +
1.1735 + /* MUST force allocation */
1.1736 + if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri))
1.1737 + goto bail;
1.1738 +
1.1739 + next_rect: ;
1.1740 + } /* for i */
1.1741 +
1.1742 + /* Make a final pass over each region in order to COALESCE and set
1.1743 + * extents.x2 and extents.y2
1.1744 + */
1.1745 + for (j = num_ri, rit = ri; --j >= 0; rit++)
1.1746 + {
1.1747 + reg = &rit->reg;
1.1748 + ri_box = PIXREGION_END (reg);
1.1749 + reg->extents.y2 = ri_box->y2;
1.1750 +
1.1751 + if (reg->extents.x2 < ri_box->x2)
1.1752 + reg->extents.x2 = ri_box->x2;
1.1753 +
1.1754 + COALESCE (reg, rit->prev_band, rit->cur_band);
1.1755 +
1.1756 + if (reg->data->numRects == 1) /* keep unions happy below */
1.1757 + {
1.1758 + FREE_DATA (reg);
1.1759 + reg->data = (region_data_type_t *)NULL;
1.1760 + }
1.1761 + }
1.1762 +
1.1763 + /* Step 3: Union all regions into a single region */
1.1764 + while (num_ri > 1)
1.1765 + {
1.1766 + int half = num_ri / 2;
1.1767 + for (j = num_ri & 1; j < (half + (num_ri & 1)); j++)
1.1768 + {
1.1769 + reg = &ri[j].reg;
1.1770 + hreg = &ri[j + half].reg;
1.1771 +
1.1772 + if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE))
1.1773 + ret = FALSE;
1.1774 +
1.1775 + if (hreg->extents.x1 < reg->extents.x1)
1.1776 + reg->extents.x1 = hreg->extents.x1;
1.1777 +
1.1778 + if (hreg->extents.y1 < reg->extents.y1)
1.1779 + reg->extents.y1 = hreg->extents.y1;
1.1780 +
1.1781 + if (hreg->extents.x2 > reg->extents.x2)
1.1782 + reg->extents.x2 = hreg->extents.x2;
1.1783 +
1.1784 + if (hreg->extents.y2 > reg->extents.y2)
1.1785 + reg->extents.y2 = hreg->extents.y2;
1.1786 +
1.1787 + FREE_DATA (hreg);
1.1788 + }
1.1789 +
1.1790 + num_ri -= half;
1.1791 +
1.1792 + if (!ret)
1.1793 + goto bail;
1.1794 + }
1.1795 +
1.1796 + *badreg = ri[0].reg;
1.1797 +
1.1798 + if (ri != stack_regions)
1.1799 + free (ri);
1.1800 +
1.1801 + GOOD (badreg);
1.1802 + return ret;
1.1803 +
1.1804 +bail:
1.1805 + for (i = 0; i < num_ri; i++)
1.1806 + FREE_DATA (&ri[i].reg);
1.1807 +
1.1808 + if (ri != stack_regions)
1.1809 + free (ri);
1.1810 +
1.1811 + return pixman_break (badreg);
1.1812 +}
1.1813 +
1.1814 +/*======================================================================
1.1815 + * Region Subtraction
1.1816 + *====================================================================*/
1.1817 +
1.1818 +/*-
1.1819 + *-----------------------------------------------------------------------
1.1820 + * pixman_region_subtract_o --
1.1821 + * Overlapping band subtraction. x1 is the left-most point not yet
1.1822 + * checked.
1.1823 + *
1.1824 + * Results:
1.1825 + * TRUE if successful.
1.1826 + *
1.1827 + * Side Effects:
1.1828 + * region may have rectangles added to it.
1.1829 + *
1.1830 + *-----------------------------------------------------------------------
1.1831 + */
1.1832 +/*ARGSUSED*/
1.1833 +static pixman_bool_t
1.1834 +pixman_region_subtract_o (region_type_t * region,
1.1835 + box_type_t * r1,
1.1836 + box_type_t * r1_end,
1.1837 + box_type_t * r2,
1.1838 + box_type_t * r2_end,
1.1839 + int y1,
1.1840 + int y2)
1.1841 +{
1.1842 + box_type_t * next_rect;
1.1843 + int x1;
1.1844 +
1.1845 + x1 = r1->x1;
1.1846 +
1.1847 + critical_if_fail (y1 < y2);
1.1848 + critical_if_fail (r1 != r1_end && r2 != r2_end);
1.1849 +
1.1850 + next_rect = PIXREGION_TOP (region);
1.1851 +
1.1852 + do
1.1853 + {
1.1854 + if (r2->x2 <= x1)
1.1855 + {
1.1856 + /*
1.1857 + * Subtrahend entirely to left of minuend: go to next subtrahend.
1.1858 + */
1.1859 + r2++;
1.1860 + }
1.1861 + else if (r2->x1 <= x1)
1.1862 + {
1.1863 + /*
1.1864 + * Subtrahend preceeds minuend: nuke left edge of minuend.
1.1865 + */
1.1866 + x1 = r2->x2;
1.1867 + if (x1 >= r1->x2)
1.1868 + {
1.1869 + /*
1.1870 + * Minuend completely covered: advance to next minuend and
1.1871 + * reset left fence to edge of new minuend.
1.1872 + */
1.1873 + r1++;
1.1874 + if (r1 != r1_end)
1.1875 + x1 = r1->x1;
1.1876 + }
1.1877 + else
1.1878 + {
1.1879 + /*
1.1880 + * Subtrahend now used up since it doesn't extend beyond
1.1881 + * minuend
1.1882 + */
1.1883 + r2++;
1.1884 + }
1.1885 + }
1.1886 + else if (r2->x1 < r1->x2)
1.1887 + {
1.1888 + /*
1.1889 + * Left part of subtrahend covers part of minuend: add uncovered
1.1890 + * part of minuend to region and skip to next subtrahend.
1.1891 + */
1.1892 + critical_if_fail (x1 < r2->x1);
1.1893 + NEWRECT (region, next_rect, x1, y1, r2->x1, y2);
1.1894 +
1.1895 + x1 = r2->x2;
1.1896 + if (x1 >= r1->x2)
1.1897 + {
1.1898 + /*
1.1899 + * Minuend used up: advance to new...
1.1900 + */
1.1901 + r1++;
1.1902 + if (r1 != r1_end)
1.1903 + x1 = r1->x1;
1.1904 + }
1.1905 + else
1.1906 + {
1.1907 + /*
1.1908 + * Subtrahend used up
1.1909 + */
1.1910 + r2++;
1.1911 + }
1.1912 + }
1.1913 + else
1.1914 + {
1.1915 + /*
1.1916 + * Minuend used up: add any remaining piece before advancing.
1.1917 + */
1.1918 + if (r1->x2 > x1)
1.1919 + NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
1.1920 +
1.1921 + r1++;
1.1922 +
1.1923 + if (r1 != r1_end)
1.1924 + x1 = r1->x1;
1.1925 + }
1.1926 + }
1.1927 + while ((r1 != r1_end) && (r2 != r2_end));
1.1928 +
1.1929 + /*
1.1930 + * Add remaining minuend rectangles to region.
1.1931 + */
1.1932 + while (r1 != r1_end)
1.1933 + {
1.1934 + critical_if_fail (x1 < r1->x2);
1.1935 +
1.1936 + NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
1.1937 +
1.1938 + r1++;
1.1939 + if (r1 != r1_end)
1.1940 + x1 = r1->x1;
1.1941 + }
1.1942 + return TRUE;
1.1943 +}
1.1944 +
1.1945 +/*-
1.1946 + *-----------------------------------------------------------------------
1.1947 + * pixman_region_subtract --
1.1948 + * Subtract reg_s from reg_m and leave the result in reg_d.
1.1949 + * S stands for subtrahend, M for minuend and D for difference.
1.1950 + *
1.1951 + * Results:
1.1952 + * TRUE if successful.
1.1953 + *
1.1954 + * Side Effects:
1.1955 + * reg_d is overwritten.
1.1956 + *
1.1957 + *-----------------------------------------------------------------------
1.1958 + */
1.1959 +PIXMAN_EXPORT pixman_bool_t
1.1960 +PREFIX (_subtract) (region_type_t *reg_d,
1.1961 + region_type_t *reg_m,
1.1962 + region_type_t *reg_s)
1.1963 +{
1.1964 + GOOD (reg_m);
1.1965 + GOOD (reg_s);
1.1966 + GOOD (reg_d);
1.1967 +
1.1968 + /* check for trivial rejects */
1.1969 + if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) ||
1.1970 + !EXTENTCHECK (®_m->extents, ®_s->extents))
1.1971 + {
1.1972 + if (PIXREGION_NAR (reg_s))
1.1973 + return pixman_break (reg_d);
1.1974 +
1.1975 + return PREFIX (_copy) (reg_d, reg_m);
1.1976 + }
1.1977 + else if (reg_m == reg_s)
1.1978 + {
1.1979 + FREE_DATA (reg_d);
1.1980 + reg_d->extents.x2 = reg_d->extents.x1;
1.1981 + reg_d->extents.y2 = reg_d->extents.y1;
1.1982 + reg_d->data = pixman_region_empty_data;
1.1983 +
1.1984 + return TRUE;
1.1985 + }
1.1986 +
1.1987 + /* Add those rectangles in region 1 that aren't in region 2,
1.1988 + do yucky substraction for overlaps, and
1.1989 + just throw away rectangles in region 2 that aren't in region 1 */
1.1990 + if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE))
1.1991 + return FALSE;
1.1992 +
1.1993 + /*
1.1994 + * Can't alter reg_d's extents before we call pixman_op because
1.1995 + * it might be one of the source regions and pixman_op depends
1.1996 + * on the extents of those regions being unaltered. Besides, this
1.1997 + * way there's no checking against rectangles that will be nuked
1.1998 + * due to coalescing, so we have to examine fewer rectangles.
1.1999 + */
1.2000 + pixman_set_extents (reg_d);
1.2001 + GOOD (reg_d);
1.2002 + return TRUE;
1.2003 +}
1.2004 +
1.2005 +/*======================================================================
1.2006 + * Region Inversion
1.2007 + *====================================================================*/
1.2008 +
1.2009 +/*-
1.2010 + *-----------------------------------------------------------------------
1.2011 + * pixman_region_inverse --
1.2012 + * Take a region and a box and return a region that is everything
1.2013 + * in the box but not in the region. The careful reader will note
1.2014 + * that this is the same as subtracting the region from the box...
1.2015 + *
1.2016 + * Results:
1.2017 + * TRUE.
1.2018 + *
1.2019 + * Side Effects:
1.2020 + * new_reg is overwritten.
1.2021 + *
1.2022 + *-----------------------------------------------------------------------
1.2023 + */
1.2024 +PIXMAN_EXPORT pixman_bool_t
1.2025 +PREFIX (_inverse) (region_type_t *new_reg, /* Destination region */
1.2026 + region_type_t *reg1, /* Region to invert */
1.2027 + box_type_t * inv_rect) /* Bounding box for inversion */
1.2028 +{
1.2029 + region_type_t inv_reg; /* Quick and dirty region made from the
1.2030 + * bounding box */
1.2031 + GOOD (reg1);
1.2032 + GOOD (new_reg);
1.2033 +
1.2034 + /* check for trivial rejects */
1.2035 + if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, ®1->extents))
1.2036 + {
1.2037 + if (PIXREGION_NAR (reg1))
1.2038 + return pixman_break (new_reg);
1.2039 +
1.2040 + new_reg->extents = *inv_rect;
1.2041 + FREE_DATA (new_reg);
1.2042 + new_reg->data = (region_data_type_t *)NULL;
1.2043 +
1.2044 + return TRUE;
1.2045 + }
1.2046 +
1.2047 + /* Add those rectangles in region 1 that aren't in region 2,
1.2048 + * do yucky substraction for overlaps, and
1.2049 + * just throw away rectangles in region 2 that aren't in region 1
1.2050 + */
1.2051 + inv_reg.extents = *inv_rect;
1.2052 + inv_reg.data = (region_data_type_t *)NULL;
1.2053 + if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE))
1.2054 + return FALSE;
1.2055 +
1.2056 + /*
1.2057 + * Can't alter new_reg's extents before we call pixman_op because
1.2058 + * it might be one of the source regions and pixman_op depends
1.2059 + * on the extents of those regions being unaltered. Besides, this
1.2060 + * way there's no checking against rectangles that will be nuked
1.2061 + * due to coalescing, so we have to examine fewer rectangles.
1.2062 + */
1.2063 + pixman_set_extents (new_reg);
1.2064 + GOOD (new_reg);
1.2065 + return TRUE;
1.2066 +}
1.2067 +
1.2068 +/* In time O(log n), locate the first box whose y2 is greater than y.
1.2069 + * Return @end if no such box exists.
1.2070 + */
1.2071 +static box_type_t *
1.2072 +find_box_for_y (box_type_t *begin, box_type_t *end, int y)
1.2073 +{
1.2074 + box_type_t *mid;
1.2075 +
1.2076 + if (end == begin)
1.2077 + return end;
1.2078 +
1.2079 + if (end - begin == 1)
1.2080 + {
1.2081 + if (begin->y2 > y)
1.2082 + return begin;
1.2083 + else
1.2084 + return end;
1.2085 + }
1.2086 +
1.2087 + mid = begin + (end - begin) / 2;
1.2088 + if (mid->y2 > y)
1.2089 + {
1.2090 + /* If no box is found in [begin, mid], the function
1.2091 + * will return @mid, which is then known to be the
1.2092 + * correct answer.
1.2093 + */
1.2094 + return find_box_for_y (begin, mid, y);
1.2095 + }
1.2096 + else
1.2097 + {
1.2098 + return find_box_for_y (mid, end, y);
1.2099 + }
1.2100 +}
1.2101 +
1.2102 +/*
1.2103 + * rect_in(region, rect)
1.2104 + * This routine takes a pointer to a region and a pointer to a box
1.2105 + * and determines if the box is outside/inside/partly inside the region.
1.2106 + *
1.2107 + * The idea is to travel through the list of rectangles trying to cover the
1.2108 + * passed box with them. Anytime a piece of the rectangle isn't covered
1.2109 + * by a band of rectangles, part_out is set TRUE. Any time a rectangle in
1.2110 + * the region covers part of the box, part_in is set TRUE. The process ends
1.2111 + * when either the box has been completely covered (we reached a band that
1.2112 + * doesn't overlap the box, part_in is TRUE and part_out is false), the
1.2113 + * box has been partially covered (part_in == part_out == TRUE -- because of
1.2114 + * the banding, the first time this is true we know the box is only
1.2115 + * partially in the region) or is outside the region (we reached a band
1.2116 + * that doesn't overlap the box at all and part_in is false)
1.2117 + */
1.2118 +PIXMAN_EXPORT pixman_region_overlap_t
1.2119 +PREFIX (_contains_rectangle) (region_type_t * region,
1.2120 + box_type_t * prect)
1.2121 +{
1.2122 + box_type_t * pbox;
1.2123 + box_type_t * pbox_end;
1.2124 + int part_in, part_out;
1.2125 + int numRects;
1.2126 + int x, y;
1.2127 +
1.2128 + GOOD (region);
1.2129 +
1.2130 + numRects = PIXREGION_NUMRECTS (region);
1.2131 +
1.2132 + /* useful optimization */
1.2133 + if (!numRects || !EXTENTCHECK (®ion->extents, prect))
1.2134 + return(PIXMAN_REGION_OUT);
1.2135 +
1.2136 + if (numRects == 1)
1.2137 + {
1.2138 + /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
1.2139 + if (SUBSUMES (®ion->extents, prect))
1.2140 + return(PIXMAN_REGION_IN);
1.2141 + else
1.2142 + return(PIXMAN_REGION_PART);
1.2143 + }
1.2144 +
1.2145 + part_out = FALSE;
1.2146 + part_in = FALSE;
1.2147 +
1.2148 + /* (x,y) starts at upper left of rect, moving to the right and down */
1.2149 + x = prect->x1;
1.2150 + y = prect->y1;
1.2151 +
1.2152 + /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */
1.2153 + for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
1.2154 + pbox != pbox_end;
1.2155 + pbox++)
1.2156 + {
1.2157 + /* getting up to speed or skipping remainder of band */
1.2158 + if (pbox->y2 <= y)
1.2159 + {
1.2160 + if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end)
1.2161 + break;
1.2162 + }
1.2163 +
1.2164 + if (pbox->y1 > y)
1.2165 + {
1.2166 + part_out = TRUE; /* missed part of rectangle above */
1.2167 + if (part_in || (pbox->y1 >= prect->y2))
1.2168 + break;
1.2169 + y = pbox->y1; /* x guaranteed to be == prect->x1 */
1.2170 + }
1.2171 +
1.2172 + if (pbox->x2 <= x)
1.2173 + continue; /* not far enough over yet */
1.2174 +
1.2175 + if (pbox->x1 > x)
1.2176 + {
1.2177 + part_out = TRUE; /* missed part of rectangle to left */
1.2178 + if (part_in)
1.2179 + break;
1.2180 + }
1.2181 +
1.2182 + if (pbox->x1 < prect->x2)
1.2183 + {
1.2184 + part_in = TRUE; /* definitely overlap */
1.2185 + if (part_out)
1.2186 + break;
1.2187 + }
1.2188 +
1.2189 + if (pbox->x2 >= prect->x2)
1.2190 + {
1.2191 + y = pbox->y2; /* finished with this band */
1.2192 + if (y >= prect->y2)
1.2193 + break;
1.2194 + x = prect->x1; /* reset x out to left again */
1.2195 + }
1.2196 + else
1.2197 + {
1.2198 + /*
1.2199 + * Because boxes in a band are maximal width, if the first box
1.2200 + * to overlap the rectangle doesn't completely cover it in that
1.2201 + * band, the rectangle must be partially out, since some of it
1.2202 + * will be uncovered in that band. part_in will have been set true
1.2203 + * by now...
1.2204 + */
1.2205 + part_out = TRUE;
1.2206 + break;
1.2207 + }
1.2208 + }
1.2209 +
1.2210 + if (part_in)
1.2211 + {
1.2212 + if (y < prect->y2)
1.2213 + return PIXMAN_REGION_PART;
1.2214 + else
1.2215 + return PIXMAN_REGION_IN;
1.2216 + }
1.2217 + else
1.2218 + {
1.2219 + return PIXMAN_REGION_OUT;
1.2220 + }
1.2221 +}
1.2222 +
1.2223 +/* PREFIX(_translate) (region, x, y)
1.2224 + * translates in place
1.2225 + */
1.2226 +
1.2227 +PIXMAN_EXPORT void
1.2228 +PREFIX (_translate) (region_type_t *region, int x, int y)
1.2229 +{
1.2230 + overflow_int_t x1, x2, y1, y2;
1.2231 + int nbox;
1.2232 + box_type_t * pbox;
1.2233 +
1.2234 + GOOD (region);
1.2235 + region->extents.x1 = x1 = region->extents.x1 + x;
1.2236 + region->extents.y1 = y1 = region->extents.y1 + y;
1.2237 + region->extents.x2 = x2 = region->extents.x2 + x;
1.2238 + region->extents.y2 = y2 = region->extents.y2 + y;
1.2239 +
1.2240 + if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0)
1.2241 + {
1.2242 + if (region->data && (nbox = region->data->numRects))
1.2243 + {
1.2244 + for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
1.2245 + {
1.2246 + pbox->x1 += x;
1.2247 + pbox->y1 += y;
1.2248 + pbox->x2 += x;
1.2249 + pbox->y2 += y;
1.2250 + }
1.2251 + }
1.2252 + return;
1.2253 + }
1.2254 +
1.2255 + if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
1.2256 + {
1.2257 + region->extents.x2 = region->extents.x1;
1.2258 + region->extents.y2 = region->extents.y1;
1.2259 + FREE_DATA (region);
1.2260 + region->data = pixman_region_empty_data;
1.2261 + return;
1.2262 + }
1.2263 +
1.2264 + if (x1 < PIXMAN_REGION_MIN)
1.2265 + region->extents.x1 = PIXMAN_REGION_MIN;
1.2266 + else if (x2 > PIXMAN_REGION_MAX)
1.2267 + region->extents.x2 = PIXMAN_REGION_MAX;
1.2268 +
1.2269 + if (y1 < PIXMAN_REGION_MIN)
1.2270 + region->extents.y1 = PIXMAN_REGION_MIN;
1.2271 + else if (y2 > PIXMAN_REGION_MAX)
1.2272 + region->extents.y2 = PIXMAN_REGION_MAX;
1.2273 +
1.2274 + if (region->data && (nbox = region->data->numRects))
1.2275 + {
1.2276 + box_type_t * pbox_out;
1.2277 +
1.2278 + for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
1.2279 + {
1.2280 + pbox_out->x1 = x1 = pbox->x1 + x;
1.2281 + pbox_out->y1 = y1 = pbox->y1 + y;
1.2282 + pbox_out->x2 = x2 = pbox->x2 + x;
1.2283 + pbox_out->y2 = y2 = pbox->y2 + y;
1.2284 +
1.2285 + if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) |
1.2286 + (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
1.2287 + {
1.2288 + region->data->numRects--;
1.2289 + continue;
1.2290 + }
1.2291 +
1.2292 + if (x1 < PIXMAN_REGION_MIN)
1.2293 + pbox_out->x1 = PIXMAN_REGION_MIN;
1.2294 + else if (x2 > PIXMAN_REGION_MAX)
1.2295 + pbox_out->x2 = PIXMAN_REGION_MAX;
1.2296 +
1.2297 + if (y1 < PIXMAN_REGION_MIN)
1.2298 + pbox_out->y1 = PIXMAN_REGION_MIN;
1.2299 + else if (y2 > PIXMAN_REGION_MAX)
1.2300 + pbox_out->y2 = PIXMAN_REGION_MAX;
1.2301 +
1.2302 + pbox_out++;
1.2303 + }
1.2304 +
1.2305 + if (pbox_out != pbox)
1.2306 + {
1.2307 + if (region->data->numRects == 1)
1.2308 + {
1.2309 + region->extents = *PIXREGION_BOXPTR (region);
1.2310 + FREE_DATA (region);
1.2311 + region->data = (region_data_type_t *)NULL;
1.2312 + }
1.2313 + else
1.2314 + {
1.2315 + pixman_set_extents (region);
1.2316 + }
1.2317 + }
1.2318 + }
1.2319 +
1.2320 + GOOD (region);
1.2321 +}
1.2322 +
1.2323 +PIXMAN_EXPORT void
1.2324 +PREFIX (_reset) (region_type_t *region, box_type_t *box)
1.2325 +{
1.2326 + GOOD (region);
1.2327 +
1.2328 + critical_if_fail (GOOD_RECT (box));
1.2329 +
1.2330 + region->extents = *box;
1.2331 +
1.2332 + FREE_DATA (region);
1.2333 +
1.2334 + region->data = NULL;
1.2335 +}
1.2336 +
1.2337 +PIXMAN_EXPORT void
1.2338 +PREFIX (_clear) (region_type_t *region)
1.2339 +{
1.2340 + GOOD (region);
1.2341 + FREE_DATA (region);
1.2342 +
1.2343 + region->extents = *pixman_region_empty_box;
1.2344 + region->data = pixman_region_empty_data;
1.2345 +}
1.2346 +
1.2347 +/* box is "return" value */
1.2348 +PIXMAN_EXPORT int
1.2349 +PREFIX (_contains_point) (region_type_t * region,
1.2350 + int x, int y,
1.2351 + box_type_t * box)
1.2352 +{
1.2353 + box_type_t *pbox, *pbox_end;
1.2354 + int numRects;
1.2355 +
1.2356 + GOOD (region);
1.2357 + numRects = PIXREGION_NUMRECTS (region);
1.2358 +
1.2359 + if (!numRects || !INBOX (®ion->extents, x, y))
1.2360 + return(FALSE);
1.2361 +
1.2362 + if (numRects == 1)
1.2363 + {
1.2364 + if (box)
1.2365 + *box = region->extents;
1.2366 +
1.2367 + return(TRUE);
1.2368 + }
1.2369 +
1.2370 + pbox = PIXREGION_BOXPTR (region);
1.2371 + pbox_end = pbox + numRects;
1.2372 +
1.2373 + pbox = find_box_for_y (pbox, pbox_end, y);
1.2374 +
1.2375 + for (;pbox != pbox_end; pbox++)
1.2376 + {
1.2377 + if ((y < pbox->y1) || (x < pbox->x1))
1.2378 + break; /* missed it */
1.2379 +
1.2380 + if (x >= pbox->x2)
1.2381 + continue; /* not there yet */
1.2382 +
1.2383 + if (box)
1.2384 + *box = *pbox;
1.2385 +
1.2386 + return(TRUE);
1.2387 + }
1.2388 +
1.2389 + return(FALSE);
1.2390 +}
1.2391 +
1.2392 +PIXMAN_EXPORT int
1.2393 +PREFIX (_not_empty) (region_type_t * region)
1.2394 +{
1.2395 + GOOD (region);
1.2396 +
1.2397 + return(!PIXREGION_NIL (region));
1.2398 +}
1.2399 +
1.2400 +PIXMAN_EXPORT box_type_t *
1.2401 +PREFIX (_extents) (region_type_t * region)
1.2402 +{
1.2403 + GOOD (region);
1.2404 +
1.2405 + return(®ion->extents);
1.2406 +}
1.2407 +
1.2408 +/*
1.2409 + * Clip a list of scanlines to a region. The caller has allocated the
1.2410 + * space. FSorted is non-zero if the scanline origins are in ascending order.
1.2411 + *
1.2412 + * returns the number of new, clipped scanlines.
1.2413 + */
1.2414 +
1.2415 +PIXMAN_EXPORT pixman_bool_t
1.2416 +PREFIX (_selfcheck) (region_type_t *reg)
1.2417 +{
1.2418 + int i, numRects;
1.2419 +
1.2420 + if ((reg->extents.x1 > reg->extents.x2) ||
1.2421 + (reg->extents.y1 > reg->extents.y2))
1.2422 + {
1.2423 + return FALSE;
1.2424 + }
1.2425 +
1.2426 + numRects = PIXREGION_NUMRECTS (reg);
1.2427 + if (!numRects)
1.2428 + {
1.2429 + return ((reg->extents.x1 == reg->extents.x2) &&
1.2430 + (reg->extents.y1 == reg->extents.y2) &&
1.2431 + (reg->data->size || (reg->data == pixman_region_empty_data)));
1.2432 + }
1.2433 + else if (numRects == 1)
1.2434 + {
1.2435 + return (!reg->data);
1.2436 + }
1.2437 + else
1.2438 + {
1.2439 + box_type_t * pbox_p, * pbox_n;
1.2440 + box_type_t box;
1.2441 +
1.2442 + pbox_p = PIXREGION_RECTS (reg);
1.2443 + box = *pbox_p;
1.2444 + box.y2 = pbox_p[numRects - 1].y2;
1.2445 + pbox_n = pbox_p + 1;
1.2446 +
1.2447 + for (i = numRects; --i > 0; pbox_p++, pbox_n++)
1.2448 + {
1.2449 + if ((pbox_n->x1 >= pbox_n->x2) ||
1.2450 + (pbox_n->y1 >= pbox_n->y2))
1.2451 + {
1.2452 + return FALSE;
1.2453 + }
1.2454 +
1.2455 + if (pbox_n->x1 < box.x1)
1.2456 + box.x1 = pbox_n->x1;
1.2457 +
1.2458 + if (pbox_n->x2 > box.x2)
1.2459 + box.x2 = pbox_n->x2;
1.2460 +
1.2461 + if ((pbox_n->y1 < pbox_p->y1) ||
1.2462 + ((pbox_n->y1 == pbox_p->y1) &&
1.2463 + ((pbox_n->x1 < pbox_p->x2) || (pbox_n->y2 != pbox_p->y2))))
1.2464 + {
1.2465 + return FALSE;
1.2466 + }
1.2467 + }
1.2468 +
1.2469 + return ((box.x1 == reg->extents.x1) &&
1.2470 + (box.x2 == reg->extents.x2) &&
1.2471 + (box.y1 == reg->extents.y1) &&
1.2472 + (box.y2 == reg->extents.y2));
1.2473 + }
1.2474 +}
1.2475 +
1.2476 +PIXMAN_EXPORT pixman_bool_t
1.2477 +PREFIX (_init_rects) (region_type_t *region,
1.2478 + const box_type_t *boxes, int count)
1.2479 +{
1.2480 + box_type_t *rects;
1.2481 + int displacement;
1.2482 + int i;
1.2483 +
1.2484 + /* if it's 1, then we just want to set the extents, so call
1.2485 + * the existing method. */
1.2486 + if (count == 1)
1.2487 + {
1.2488 + PREFIX (_init_rect) (region,
1.2489 + boxes[0].x1,
1.2490 + boxes[0].y1,
1.2491 + boxes[0].x2 - boxes[0].x1,
1.2492 + boxes[0].y2 - boxes[0].y1);
1.2493 + return TRUE;
1.2494 + }
1.2495 +
1.2496 + PREFIX (_init) (region);
1.2497 +
1.2498 + /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
1.2499 + * a special case, and causing pixman_rect_alloc would cause
1.2500 + * us to leak memory (because the 0-rect case should be the
1.2501 + * static pixman_region_empty_data data).
1.2502 + */
1.2503 + if (count == 0)
1.2504 + return TRUE;
1.2505 +
1.2506 + if (!pixman_rect_alloc (region, count))
1.2507 + return FALSE;
1.2508 +
1.2509 + rects = PIXREGION_RECTS (region);
1.2510 +
1.2511 + /* Copy in the rects */
1.2512 + memcpy (rects, boxes, sizeof(box_type_t) * count);
1.2513 + region->data->numRects = count;
1.2514 +
1.2515 + /* Eliminate empty and malformed rectangles */
1.2516 + displacement = 0;
1.2517 +
1.2518 + for (i = 0; i < count; ++i)
1.2519 + {
1.2520 + box_type_t *box = &rects[i];
1.2521 +
1.2522 + if (box->x1 >= box->x2 || box->y1 >= box->y2)
1.2523 + displacement++;
1.2524 + else if (displacement)
1.2525 + rects[i - displacement] = rects[i];
1.2526 + }
1.2527 +
1.2528 + region->data->numRects -= displacement;
1.2529 +
1.2530 + /* If eliminating empty rectangles caused there
1.2531 + * to be only 0 or 1 rectangles, deal with that.
1.2532 + */
1.2533 + if (region->data->numRects == 0)
1.2534 + {
1.2535 + FREE_DATA (region);
1.2536 + PREFIX (_init) (region);
1.2537 +
1.2538 + return TRUE;
1.2539 + }
1.2540 +
1.2541 + if (region->data->numRects == 1)
1.2542 + {
1.2543 + region->extents = rects[0];
1.2544 +
1.2545 + FREE_DATA (region);
1.2546 + region->data = NULL;
1.2547 +
1.2548 + GOOD (region);
1.2549 +
1.2550 + return TRUE;
1.2551 + }
1.2552 +
1.2553 + /* Validate */
1.2554 + region->extents.x1 = region->extents.x2 = 0;
1.2555 +
1.2556 + return validate (region);
1.2557 +}
1.2558 +
1.2559 +#define READ(_ptr) (*(_ptr))
1.2560 +
1.2561 +static inline box_type_t *
1.2562 +bitmap_addrect (region_type_t *reg,
1.2563 + box_type_t *r,
1.2564 + box_type_t **first_rect,
1.2565 + int rx1, int ry1,
1.2566 + int rx2, int ry2)
1.2567 +{
1.2568 + if ((rx1 < rx2) && (ry1 < ry2) &&
1.2569 + (!(reg->data->numRects &&
1.2570 + ((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) &&
1.2571 + ((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2))))
1.2572 + {
1.2573 + if (reg->data->numRects == reg->data->size)
1.2574 + {
1.2575 + if (!pixman_rect_alloc (reg, 1))
1.2576 + return NULL;
1.2577 + *first_rect = PIXREGION_BOXPTR(reg);
1.2578 + r = *first_rect + reg->data->numRects;
1.2579 + }
1.2580 + r->x1 = rx1;
1.2581 + r->y1 = ry1;
1.2582 + r->x2 = rx2;
1.2583 + r->y2 = ry2;
1.2584 + reg->data->numRects++;
1.2585 + if (r->x1 < reg->extents.x1)
1.2586 + reg->extents.x1 = r->x1;
1.2587 + if (r->x2 > reg->extents.x2)
1.2588 + reg->extents.x2 = r->x2;
1.2589 + r++;
1.2590 + }
1.2591 + return r;
1.2592 +}
1.2593 +
1.2594 +/* Convert bitmap clip mask into clipping region.
1.2595 + * First, goes through each line and makes boxes by noting the transitions
1.2596 + * from 0 to 1 and 1 to 0.
1.2597 + * Then it coalesces the current line with the previous if they have boxes
1.2598 + * at the same X coordinates.
1.2599 + * Stride is in number of uint32_t per line.
1.2600 + */
1.2601 +PIXMAN_EXPORT void
1.2602 +PREFIX (_init_from_image) (region_type_t *region,
1.2603 + pixman_image_t *image)
1.2604 +{
1.2605 + uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1);
1.2606 + box_type_t *first_rect, *rects, *prect_line_start;
1.2607 + box_type_t *old_rect, *new_rect;
1.2608 + uint32_t *pw, w, *pw_line, *pw_line_end;
1.2609 + int irect_prev_start, irect_line_start;
1.2610 + int h, base, rx1 = 0, crects;
1.2611 + int ib;
1.2612 + pixman_bool_t in_box, same;
1.2613 + int width, height, stride;
1.2614 +
1.2615 + PREFIX(_init) (region);
1.2616 +
1.2617 + critical_if_fail (region->data);
1.2618 +
1.2619 + return_if_fail (image->type == BITS);
1.2620 + return_if_fail (image->bits.format == PIXMAN_a1);
1.2621 +
1.2622 + pw_line = pixman_image_get_data (image);
1.2623 + width = pixman_image_get_width (image);
1.2624 + height = pixman_image_get_height (image);
1.2625 + stride = pixman_image_get_stride (image) / 4;
1.2626 +
1.2627 + first_rect = PIXREGION_BOXPTR(region);
1.2628 + rects = first_rect;
1.2629 +
1.2630 + region->extents.x1 = width - 1;
1.2631 + region->extents.x2 = 0;
1.2632 + irect_prev_start = -1;
1.2633 + for (h = 0; h < height; h++)
1.2634 + {
1.2635 + pw = pw_line;
1.2636 + pw_line += stride;
1.2637 + irect_line_start = rects - first_rect;
1.2638 +
1.2639 + /* If the Screen left most bit of the word is set, we're starting in
1.2640 + * a box */
1.2641 + if (READ(pw) & mask0)
1.2642 + {
1.2643 + in_box = TRUE;
1.2644 + rx1 = 0;
1.2645 + }
1.2646 + else
1.2647 + {
1.2648 + in_box = FALSE;
1.2649 + }
1.2650 +
1.2651 + /* Process all words which are fully in the pixmap */
1.2652 + pw_line_end = pw + (width >> 5);
1.2653 + for (base = 0; pw < pw_line_end; base += 32)
1.2654 + {
1.2655 + w = READ(pw++);
1.2656 + if (in_box)
1.2657 + {
1.2658 + if (!~w)
1.2659 + continue;
1.2660 + }
1.2661 + else
1.2662 + {
1.2663 + if (!w)
1.2664 + continue;
1.2665 + }
1.2666 + for (ib = 0; ib < 32; ib++)
1.2667 + {
1.2668 + /* If the Screen left most bit of the word is set, we're
1.2669 + * starting a box */
1.2670 + if (w & mask0)
1.2671 + {
1.2672 + if (!in_box)
1.2673 + {
1.2674 + rx1 = base + ib;
1.2675 + /* start new box */
1.2676 + in_box = TRUE;
1.2677 + }
1.2678 + }
1.2679 + else
1.2680 + {
1.2681 + if (in_box)
1.2682 + {
1.2683 + /* end box */
1.2684 + rects = bitmap_addrect (region, rects, &first_rect,
1.2685 + rx1, h, base + ib, h + 1);
1.2686 + if (rects == NULL)
1.2687 + goto error;
1.2688 + in_box = FALSE;
1.2689 + }
1.2690 + }
1.2691 + /* Shift the word VISUALLY left one. */
1.2692 + w = SCREEN_SHIFT_LEFT(w, 1);
1.2693 + }
1.2694 + }
1.2695 +
1.2696 + if (width & 31)
1.2697 + {
1.2698 + /* Process final partial word on line */
1.2699 + w = READ(pw++);
1.2700 + for (ib = 0; ib < (width & 31); ib++)
1.2701 + {
1.2702 + /* If the Screen left most bit of the word is set, we're
1.2703 + * starting a box */
1.2704 + if (w & mask0)
1.2705 + {
1.2706 + if (!in_box)
1.2707 + {
1.2708 + rx1 = base + ib;
1.2709 + /* start new box */
1.2710 + in_box = TRUE;
1.2711 + }
1.2712 + }
1.2713 + else
1.2714 + {
1.2715 + if (in_box)
1.2716 + {
1.2717 + /* end box */
1.2718 + rects = bitmap_addrect(region, rects, &first_rect,
1.2719 + rx1, h, base + ib, h + 1);
1.2720 + if (rects == NULL)
1.2721 + goto error;
1.2722 + in_box = FALSE;
1.2723 + }
1.2724 + }
1.2725 + /* Shift the word VISUALLY left one. */
1.2726 + w = SCREEN_SHIFT_LEFT(w, 1);
1.2727 + }
1.2728 + }
1.2729 + /* If scanline ended with last bit set, end the box */
1.2730 + if (in_box)
1.2731 + {
1.2732 + rects = bitmap_addrect(region, rects, &first_rect,
1.2733 + rx1, h, base + (width & 31), h + 1);
1.2734 + if (rects == NULL)
1.2735 + goto error;
1.2736 + }
1.2737 + /* if all rectangles on this line have the same x-coords as
1.2738 + * those on the previous line, then add 1 to all the previous y2s and
1.2739 + * throw away all the rectangles from this line
1.2740 + */
1.2741 + same = FALSE;
1.2742 + if (irect_prev_start != -1)
1.2743 + {
1.2744 + crects = irect_line_start - irect_prev_start;
1.2745 + if (crects != 0 &&
1.2746 + crects == ((rects - first_rect) - irect_line_start))
1.2747 + {
1.2748 + old_rect = first_rect + irect_prev_start;
1.2749 + new_rect = prect_line_start = first_rect + irect_line_start;
1.2750 + same = TRUE;
1.2751 + while (old_rect < prect_line_start)
1.2752 + {
1.2753 + if ((old_rect->x1 != new_rect->x1) ||
1.2754 + (old_rect->x2 != new_rect->x2))
1.2755 + {
1.2756 + same = FALSE;
1.2757 + break;
1.2758 + }
1.2759 + old_rect++;
1.2760 + new_rect++;
1.2761 + }
1.2762 + if (same)
1.2763 + {
1.2764 + old_rect = first_rect + irect_prev_start;
1.2765 + while (old_rect < prect_line_start)
1.2766 + {
1.2767 + old_rect->y2 += 1;
1.2768 + old_rect++;
1.2769 + }
1.2770 + rects -= crects;
1.2771 + region->data->numRects -= crects;
1.2772 + }
1.2773 + }
1.2774 + }
1.2775 + if(!same)
1.2776 + irect_prev_start = irect_line_start;
1.2777 + }
1.2778 + if (!region->data->numRects)
1.2779 + {
1.2780 + region->extents.x1 = region->extents.x2 = 0;
1.2781 + }
1.2782 + else
1.2783 + {
1.2784 + region->extents.y1 = PIXREGION_BOXPTR(region)->y1;
1.2785 + region->extents.y2 = PIXREGION_END(region)->y2;
1.2786 + if (region->data->numRects == 1)
1.2787 + {
1.2788 + free (region->data);
1.2789 + region->data = NULL;
1.2790 + }
1.2791 + }
1.2792 +
1.2793 + error:
1.2794 + return;
1.2795 +}
