michael@0: /* michael@0: * Copyright 1987, 1988, 1989, 1998 The Open Group michael@0: * michael@0: * Permission to use, copy, modify, distribute, and sell this software and its michael@0: * documentation for any purpose is hereby granted without fee, provided that michael@0: * the above copyright notice appear in all copies and that both that michael@0: * copyright notice and this permission notice appear in supporting michael@0: * documentation. michael@0: * michael@0: * The above copyright notice and this permission notice shall be included in michael@0: * all copies or substantial portions of the Software. michael@0: * michael@0: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR michael@0: * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, michael@0: * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE michael@0: * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN michael@0: * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN michael@0: * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. michael@0: * michael@0: * Except as contained in this notice, the name of The Open Group shall not be michael@0: * used in advertising or otherwise to promote the sale, use or other dealings michael@0: * in this Software without prior written authorization from The Open Group. michael@0: * michael@0: * Copyright 1987, 1988, 1989 by michael@0: * Digital Equipment Corporation, Maynard, Massachusetts. michael@0: * michael@0: * All Rights Reserved michael@0: * michael@0: * Permission to use, copy, modify, and distribute this software and its michael@0: * documentation for any purpose and without fee is hereby granted, michael@0: * provided that the above copyright notice appear in all copies and that michael@0: * both that copyright notice and this permission notice appear in michael@0: * supporting documentation, and that the name of Digital not be michael@0: * used in advertising or publicity pertaining to distribution of the michael@0: * software without specific, written prior permission. michael@0: * michael@0: * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING michael@0: * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL michael@0: * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR michael@0: * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, michael@0: * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, michael@0: * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS michael@0: * SOFTWARE. michael@0: * michael@0: * Copyright © 1998 Keith Packard michael@0: * michael@0: * Permission to use, copy, modify, distribute, and sell this software and its michael@0: * documentation for any purpose is hereby granted without fee, provided that michael@0: * the above copyright notice appear in all copies and that both that michael@0: * copyright notice and this permission notice appear in supporting michael@0: * documentation, and that the name of Keith Packard not be used in michael@0: * advertising or publicity pertaining to distribution of the software without michael@0: * specific, written prior permission. Keith Packard makes no michael@0: * representations about the suitability of this software for any purpose. It michael@0: * is provided "as is" without express or implied warranty. michael@0: * michael@0: * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, michael@0: * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO michael@0: * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR michael@0: * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, michael@0: * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER michael@0: * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR michael@0: * PERFORMANCE OF THIS SOFTWARE. michael@0: */ michael@0: michael@0: #include michael@0: #include michael@0: #include michael@0: #include michael@0: #include "pixman-private.h" michael@0: michael@0: #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects) michael@0: /* not a region */ michael@0: #define PIXREGION_NAR(reg) ((reg)->data == pixman_broken_data) michael@0: #define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1) michael@0: #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0) michael@0: #define PIXREGION_RECTS(reg) \ michael@0: ((reg)->data ? (box_type_t *)((reg)->data + 1) \ michael@0: : &(reg)->extents) michael@0: #define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1)) michael@0: #define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i]) michael@0: #define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects) michael@0: #define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1) michael@0: michael@0: #define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2) michael@0: #define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2) michael@0: michael@0: #ifdef DEBUG michael@0: michael@0: #define GOOD(reg) \ michael@0: do \ michael@0: { \ michael@0: if (!PREFIX (_selfcheck (reg))) \ michael@0: _pixman_log_error (FUNC, "Malformed region " # reg); \ michael@0: } while (0) michael@0: michael@0: #else michael@0: michael@0: #define GOOD(reg) michael@0: michael@0: #endif michael@0: michael@0: static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 }; michael@0: static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 }; michael@0: #if defined (__llvm__) && !defined (__clang__) michael@0: static const volatile region_data_type_t PREFIX (_broken_data_) = { 0, 0 }; michael@0: #else michael@0: static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 }; michael@0: #endif michael@0: michael@0: static box_type_t *pixman_region_empty_box = michael@0: (box_type_t *)&PREFIX (_empty_box_); michael@0: static region_data_type_t *pixman_region_empty_data = michael@0: (region_data_type_t *)&PREFIX (_empty_data_); michael@0: static region_data_type_t *pixman_broken_data = michael@0: (region_data_type_t *)&PREFIX (_broken_data_); michael@0: michael@0: static pixman_bool_t michael@0: pixman_break (region_type_t *region); michael@0: michael@0: /* michael@0: * The functions in this file implement the Region abstraction used extensively michael@0: * throughout the X11 sample server. A Region is simply a set of disjoint michael@0: * (non-overlapping) rectangles, plus an "extent" rectangle which is the michael@0: * smallest single rectangle that contains all the non-overlapping rectangles. michael@0: * michael@0: * A Region is implemented as a "y-x-banded" array of rectangles. This array michael@0: * imposes two degrees of order. First, all rectangles are sorted by top side michael@0: * y coordinate first (y1), and then by left side x coordinate (x1). michael@0: * michael@0: * Furthermore, the rectangles are grouped into "bands". Each rectangle in a michael@0: * band has the same top y coordinate (y1), and each has the same bottom y michael@0: * coordinate (y2). Thus all rectangles in a band differ only in their left michael@0: * and right side (x1 and x2). Bands are implicit in the array of rectangles: michael@0: * there is no separate list of band start pointers. michael@0: * michael@0: * The y-x band representation does not minimize rectangles. In particular, michael@0: * if a rectangle vertically crosses a band (the rectangle has scanlines in michael@0: * the y1 to y2 area spanned by the band), then the rectangle may be broken michael@0: * down into two or more smaller rectangles stacked one atop the other. michael@0: * michael@0: * ----------- ----------- michael@0: * | | | | band 0 michael@0: * | | -------- ----------- -------- michael@0: * | | | | in y-x banded | | | | band 1 michael@0: * | | | | form is | | | | michael@0: * ----------- | | ----------- -------- michael@0: * | | | | band 2 michael@0: * -------- -------- michael@0: * michael@0: * An added constraint on the rectangles is that they must cover as much michael@0: * horizontal area as possible: no two rectangles within a band are allowed michael@0: * to touch. michael@0: * michael@0: * Whenever possible, bands will be merged together to cover a greater vertical michael@0: * distance (and thus reduce the number of rectangles). Two bands can be merged michael@0: * only if the bottom of one touches the top of the other and they have michael@0: * rectangles in the same places (of the same width, of course). michael@0: * michael@0: * Adam de Boor wrote most of the original region code. Joel McCormack michael@0: * substantially modified or rewrote most of the core arithmetic routines, and michael@0: * added pixman_region_validate in order to support several speed improvements michael@0: * to pixman_region_validate_tree. Bob Scheifler changed the representation michael@0: * to be more compact when empty or a single rectangle, and did a bunch of michael@0: * gratuitous reformatting. Carl Worth did further gratuitous reformatting michael@0: * while re-merging the server and client region code into libpixregion. michael@0: * Soren Sandmann did even more gratuitous reformatting. michael@0: */ michael@0: michael@0: /* true iff two Boxes overlap */ michael@0: #define EXTENTCHECK(r1, r2) \ michael@0: (!( ((r1)->x2 <= (r2)->x1) || \ michael@0: ((r1)->x1 >= (r2)->x2) || \ michael@0: ((r1)->y2 <= (r2)->y1) || \ michael@0: ((r1)->y1 >= (r2)->y2) ) ) michael@0: michael@0: /* true iff (x,y) is in Box */ michael@0: #define INBOX(r, x, y) \ michael@0: ( ((r)->x2 > x) && \ michael@0: ((r)->x1 <= x) && \ michael@0: ((r)->y2 > y) && \ michael@0: ((r)->y1 <= y) ) michael@0: michael@0: /* true iff Box r1 contains Box r2 */ michael@0: #define SUBSUMES(r1, r2) \ michael@0: ( ((r1)->x1 <= (r2)->x1) && \ michael@0: ((r1)->x2 >= (r2)->x2) && \ michael@0: ((r1)->y1 <= (r2)->y1) && \ michael@0: ((r1)->y2 >= (r2)->y2) ) michael@0: michael@0: static size_t michael@0: PIXREGION_SZOF (size_t n) michael@0: { michael@0: size_t size = n * sizeof(box_type_t); michael@0: michael@0: if (n > UINT32_MAX / sizeof(box_type_t)) michael@0: return 0; michael@0: michael@0: if (sizeof(region_data_type_t) > UINT32_MAX - size) michael@0: return 0; michael@0: michael@0: return size + sizeof(region_data_type_t); michael@0: } michael@0: michael@0: static region_data_type_t * michael@0: alloc_data (size_t n) michael@0: { michael@0: size_t sz = PIXREGION_SZOF (n); michael@0: michael@0: if (!sz) michael@0: return NULL; michael@0: michael@0: return malloc (sz); michael@0: } michael@0: michael@0: #define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data) michael@0: michael@0: #define RECTALLOC_BAIL(region, n, bail) \ michael@0: do \ michael@0: { \ michael@0: if (!(region)->data || \ michael@0: (((region)->data->numRects + (n)) > (region)->data->size)) \ michael@0: { \ michael@0: if (!pixman_rect_alloc (region, n)) \ michael@0: goto bail; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define RECTALLOC(region, n) \ michael@0: do \ michael@0: { \ michael@0: if (!(region)->data || \ michael@0: (((region)->data->numRects + (n)) > (region)->data->size)) \ michael@0: { \ michael@0: if (!pixman_rect_alloc (region, n)) { \ michael@0: return FALSE; \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define ADDRECT(next_rect, nx1, ny1, nx2, ny2) \ michael@0: do \ michael@0: { \ michael@0: next_rect->x1 = nx1; \ michael@0: next_rect->y1 = ny1; \ michael@0: next_rect->x2 = nx2; \ michael@0: next_rect->y2 = ny2; \ michael@0: next_rect++; \ michael@0: } \ michael@0: while (0) michael@0: michael@0: #define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2) \ michael@0: do \ michael@0: { \ michael@0: if (!(region)->data || \ michael@0: ((region)->data->numRects == (region)->data->size)) \ michael@0: { \ michael@0: if (!pixman_rect_alloc (region, 1)) \ michael@0: return FALSE; \ michael@0: next_rect = PIXREGION_TOP (region); \ michael@0: } \ michael@0: ADDRECT (next_rect, nx1, ny1, nx2, ny2); \ michael@0: region->data->numRects++; \ michael@0: critical_if_fail (region->data->numRects <= region->data->size); \ michael@0: } while (0) michael@0: michael@0: #define DOWNSIZE(reg, numRects) \ michael@0: do \ michael@0: { \ michael@0: if (((numRects) < ((reg)->data->size >> 1)) && \ michael@0: ((reg)->data->size > 50)) \ michael@0: { \ michael@0: region_data_type_t * new_data; \ michael@0: size_t data_size = PIXREGION_SZOF (numRects); \ michael@0: \ michael@0: if (!data_size) \ michael@0: { \ michael@0: new_data = NULL; \ michael@0: } \ michael@0: else \ michael@0: { \ michael@0: new_data = (region_data_type_t *) \ michael@0: realloc ((reg)->data, data_size); \ michael@0: } \ michael@0: \ michael@0: if (new_data) \ michael@0: { \ michael@0: new_data->size = (numRects); \ michael@0: (reg)->data = new_data; \ michael@0: } \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_equal) (region_type_t *reg1, region_type_t *reg2) michael@0: { michael@0: int i; michael@0: box_type_t *rects1; michael@0: box_type_t *rects2; michael@0: michael@0: if (reg1->extents.x1 != reg2->extents.x1) michael@0: return FALSE; michael@0: michael@0: if (reg1->extents.x2 != reg2->extents.x2) michael@0: return FALSE; michael@0: michael@0: if (reg1->extents.y1 != reg2->extents.y1) michael@0: return FALSE; michael@0: michael@0: if (reg1->extents.y2 != reg2->extents.y2) michael@0: return FALSE; michael@0: michael@0: if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2)) michael@0: return FALSE; michael@0: michael@0: rects1 = PIXREGION_RECTS (reg1); michael@0: rects2 = PIXREGION_RECTS (reg2); michael@0: michael@0: for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++) michael@0: { michael@0: if (rects1[i].x1 != rects2[i].x1) michael@0: return FALSE; michael@0: michael@0: if (rects1[i].x2 != rects2[i].x2) michael@0: return FALSE; michael@0: michael@0: if (rects1[i].y1 != rects2[i].y1) michael@0: return FALSE; michael@0: michael@0: if (rects1[i].y2 != rects2[i].y2) michael@0: return FALSE; michael@0: } michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: int michael@0: PREFIX (_print) (region_type_t *rgn) michael@0: { michael@0: int num, size; michael@0: int i; michael@0: box_type_t * rects; michael@0: michael@0: num = PIXREGION_NUMRECTS (rgn); michael@0: size = PIXREGION_SIZE (rgn); michael@0: rects = PIXREGION_RECTS (rgn); michael@0: michael@0: fprintf (stderr, "num: %d size: %d\n", num, size); michael@0: fprintf (stderr, "extents: %d %d %d %d\n", michael@0: rgn->extents.x1, michael@0: rgn->extents.y1, michael@0: rgn->extents.x2, michael@0: rgn->extents.y2); michael@0: michael@0: for (i = 0; i < num; i++) michael@0: { michael@0: fprintf (stderr, "%d %d %d %d \n", michael@0: rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2); michael@0: } michael@0: michael@0: fprintf (stderr, "\n"); michael@0: michael@0: return(num); michael@0: } michael@0: michael@0: michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_init) (region_type_t *region) michael@0: { michael@0: region->extents = *pixman_region_empty_box; michael@0: region->data = pixman_region_empty_data; michael@0: } michael@0: michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_init_rect) (region_type_t * region, michael@0: int x, michael@0: int y, michael@0: unsigned int width, michael@0: unsigned int height) michael@0: { michael@0: region->extents.x1 = x; michael@0: region->extents.y1 = y; michael@0: region->extents.x2 = x + width; michael@0: region->extents.y2 = y + height; michael@0: michael@0: if (!GOOD_RECT (®ion->extents)) michael@0: { michael@0: if (BAD_RECT (®ion->extents)) michael@0: _pixman_log_error (FUNC, "Invalid rectangle passed"); michael@0: PREFIX (_init) (region); michael@0: return; michael@0: } michael@0: michael@0: region->data = NULL; michael@0: } michael@0: michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents) michael@0: { michael@0: if (!GOOD_RECT (extents)) michael@0: { michael@0: if (BAD_RECT (extents)) michael@0: _pixman_log_error (FUNC, "Invalid rectangle passed"); michael@0: PREFIX (_init) (region); michael@0: return; michael@0: } michael@0: region->extents = *extents; michael@0: michael@0: region->data = NULL; michael@0: } michael@0: michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_fini) (region_type_t *region) michael@0: { michael@0: GOOD (region); michael@0: FREE_DATA (region); michael@0: } michael@0: michael@0: PIXMAN_EXPORT int michael@0: PREFIX (_n_rects) (region_type_t *region) michael@0: { michael@0: return PIXREGION_NUMRECTS (region); michael@0: } michael@0: michael@0: PIXMAN_EXPORT box_type_t * michael@0: PREFIX (_rectangles) (region_type_t *region, michael@0: int *n_rects) michael@0: { michael@0: if (n_rects) michael@0: *n_rects = PIXREGION_NUMRECTS (region); michael@0: michael@0: return PIXREGION_RECTS (region); michael@0: } michael@0: michael@0: static pixman_bool_t michael@0: pixman_break (region_type_t *region) michael@0: { michael@0: FREE_DATA (region); michael@0: michael@0: region->extents = *pixman_region_empty_box; michael@0: region->data = pixman_broken_data; michael@0: michael@0: return FALSE; michael@0: } michael@0: michael@0: static pixman_bool_t michael@0: pixman_rect_alloc (region_type_t * region, michael@0: int n) michael@0: { michael@0: region_data_type_t *data; michael@0: michael@0: if (!region->data) michael@0: { michael@0: n++; michael@0: region->data = alloc_data (n); michael@0: michael@0: if (!region->data) michael@0: return pixman_break (region); michael@0: michael@0: region->data->numRects = 1; michael@0: *PIXREGION_BOXPTR (region) = region->extents; michael@0: } michael@0: else if (!region->data->size) michael@0: { michael@0: region->data = alloc_data (n); michael@0: michael@0: if (!region->data) michael@0: return pixman_break (region); michael@0: michael@0: region->data->numRects = 0; michael@0: } michael@0: else michael@0: { michael@0: size_t data_size; michael@0: michael@0: if (n == 1) michael@0: { michael@0: n = region->data->numRects; michael@0: if (n > 500) /* XXX pick numbers out of a hat */ michael@0: n = 250; michael@0: } michael@0: michael@0: n += region->data->numRects; michael@0: data_size = PIXREGION_SZOF (n); michael@0: michael@0: if (!data_size) michael@0: { michael@0: data = NULL; michael@0: } michael@0: else michael@0: { michael@0: data = (region_data_type_t *) michael@0: realloc (region->data, PIXREGION_SZOF (n)); michael@0: } michael@0: michael@0: if (!data) michael@0: return pixman_break (region); michael@0: michael@0: region->data = data; michael@0: } michael@0: michael@0: region->data->size = n; michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_copy) (region_type_t *dst, region_type_t *src) michael@0: { michael@0: GOOD (dst); michael@0: GOOD (src); michael@0: michael@0: if (dst == src) michael@0: return TRUE; michael@0: michael@0: dst->extents = src->extents; michael@0: michael@0: if (!src->data || !src->data->size) michael@0: { michael@0: FREE_DATA (dst); michael@0: dst->data = src->data; michael@0: return TRUE; michael@0: } michael@0: michael@0: if (!dst->data || (dst->data->size < src->data->numRects)) michael@0: { michael@0: FREE_DATA (dst); michael@0: michael@0: dst->data = alloc_data (src->data->numRects); michael@0: michael@0: if (!dst->data) michael@0: return pixman_break (dst); michael@0: michael@0: dst->data->size = src->data->numRects; michael@0: } michael@0: michael@0: dst->data->numRects = src->data->numRects; michael@0: michael@0: memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src), michael@0: dst->data->numRects * sizeof(box_type_t)); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /*====================================================================== michael@0: * Generic Region Operator michael@0: *====================================================================*/ michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_coalesce -- michael@0: * Attempt to merge the boxes in the current band with those in the michael@0: * previous one. We are guaranteed that the current band extends to michael@0: * the end of the rects array. Used only by pixman_op. michael@0: * michael@0: * Results: michael@0: * The new index for the previous band. michael@0: * michael@0: * Side Effects: michael@0: * If coalescing takes place: michael@0: * - rectangles in the previous band will have their y2 fields michael@0: * altered. michael@0: * - region->data->numRects will be decreased. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: static inline int michael@0: pixman_coalesce (region_type_t * region, /* Region to coalesce */ michael@0: int prev_start, /* Index of start of previous band */ michael@0: int cur_start) /* Index of start of current band */ michael@0: { michael@0: box_type_t *prev_box; /* Current box in previous band */ michael@0: box_type_t *cur_box; /* Current box in current band */ michael@0: int numRects; /* Number rectangles in both bands */ michael@0: int y2; /* Bottom of current band */ michael@0: michael@0: /* michael@0: * Figure out how many rectangles are in the band. michael@0: */ michael@0: numRects = cur_start - prev_start; michael@0: critical_if_fail (numRects == region->data->numRects - cur_start); michael@0: michael@0: if (!numRects) return cur_start; michael@0: michael@0: /* michael@0: * The bands may only be coalesced if the bottom of the previous michael@0: * matches the top scanline of the current. michael@0: */ michael@0: prev_box = PIXREGION_BOX (region, prev_start); michael@0: cur_box = PIXREGION_BOX (region, cur_start); michael@0: if (prev_box->y2 != cur_box->y1) return cur_start; michael@0: michael@0: /* michael@0: * Make sure the bands have boxes in the same places. This michael@0: * assumes that boxes have been added in such a way that they michael@0: * cover the most area possible. I.e. two boxes in a band must michael@0: * have some horizontal space between them. michael@0: */ michael@0: y2 = cur_box->y2; michael@0: michael@0: do michael@0: { michael@0: if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2)) michael@0: return (cur_start); michael@0: michael@0: prev_box++; michael@0: cur_box++; michael@0: numRects--; michael@0: } michael@0: while (numRects); michael@0: michael@0: /* michael@0: * The bands may be merged, so set the bottom y of each box michael@0: * in the previous band to the bottom y of the current band. michael@0: */ michael@0: numRects = cur_start - prev_start; michael@0: region->data->numRects -= numRects; michael@0: michael@0: do michael@0: { michael@0: prev_box--; michael@0: prev_box->y2 = y2; michael@0: numRects--; michael@0: } michael@0: while (numRects); michael@0: michael@0: return prev_start; michael@0: } michael@0: michael@0: /* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */ michael@0: michael@0: #define COALESCE(new_reg, prev_band, cur_band) \ michael@0: do \ michael@0: { \ michael@0: if (cur_band - prev_band == new_reg->data->numRects - cur_band) \ michael@0: prev_band = pixman_coalesce (new_reg, prev_band, cur_band); \ michael@0: else \ michael@0: prev_band = cur_band; \ michael@0: } while (0) michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_region_append_non_o -- michael@0: * Handle a non-overlapping band for the union and subtract operations. michael@0: * Just adds the (top/bottom-clipped) rectangles into the region. michael@0: * Doesn't have to check for subsumption or anything. michael@0: * michael@0: * Results: michael@0: * None. michael@0: * michael@0: * Side Effects: michael@0: * region->data->numRects is incremented and the rectangles overwritten michael@0: * with the rectangles we're passed. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: static inline pixman_bool_t michael@0: pixman_region_append_non_o (region_type_t * region, michael@0: box_type_t * r, michael@0: box_type_t * r_end, michael@0: int y1, michael@0: int y2) michael@0: { michael@0: box_type_t *next_rect; michael@0: int new_rects; michael@0: michael@0: new_rects = r_end - r; michael@0: michael@0: critical_if_fail (y1 < y2); michael@0: critical_if_fail (new_rects != 0); michael@0: michael@0: /* Make sure we have enough space for all rectangles to be added */ michael@0: RECTALLOC (region, new_rects); michael@0: next_rect = PIXREGION_TOP (region); michael@0: region->data->numRects += new_rects; michael@0: michael@0: do michael@0: { michael@0: critical_if_fail (r->x1 < r->x2); michael@0: ADDRECT (next_rect, r->x1, y1, r->x2, y2); michael@0: r++; michael@0: } michael@0: while (r != r_end); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: #define FIND_BAND(r, r_band_end, r_end, ry1) \ michael@0: do \ michael@0: { \ michael@0: ry1 = r->y1; \ michael@0: r_band_end = r + 1; \ michael@0: while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) { \ michael@0: r_band_end++; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: #define APPEND_REGIONS(new_reg, r, r_end) \ michael@0: do \ michael@0: { \ michael@0: int new_rects; \ michael@0: if ((new_rects = r_end - r)) { \ michael@0: RECTALLOC_BAIL (new_reg, new_rects, bail); \ michael@0: memmove ((char *)PIXREGION_TOP (new_reg), (char *)r, \ michael@0: new_rects * sizeof(box_type_t)); \ michael@0: new_reg->data->numRects += new_rects; \ michael@0: } \ michael@0: } while (0) michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_op -- michael@0: * Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse, michael@0: * pixman_region_subtract, pixman_region_intersect.... Both regions MUST have at least one michael@0: * rectangle, and cannot be the same object. michael@0: * michael@0: * Results: michael@0: * TRUE if successful. michael@0: * michael@0: * Side Effects: michael@0: * The new region is overwritten. michael@0: * overlap set to TRUE if overlap_func ever returns TRUE. michael@0: * michael@0: * Notes: michael@0: * The idea behind this function is to view the two regions as sets. michael@0: * Together they cover a rectangle of area that this function divides michael@0: * into horizontal bands where points are covered only by one region michael@0: * or by both. For the first case, the non_overlap_func is called with michael@0: * each the band and the band's upper and lower extents. For the michael@0: * second, the overlap_func is called to process the entire band. It michael@0: * is responsible for clipping the rectangles in the band, though michael@0: * this function provides the boundaries. michael@0: * At the end of each band, the new region is coalesced, if possible, michael@0: * to reduce the number of rectangles in the region. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: michael@0: typedef pixman_bool_t (*overlap_proc_ptr) (region_type_t *region, michael@0: box_type_t * r1, michael@0: box_type_t * r1_end, michael@0: box_type_t * r2, michael@0: box_type_t * r2_end, michael@0: int y1, michael@0: int y2); michael@0: michael@0: static pixman_bool_t michael@0: pixman_op (region_type_t * new_reg, /* Place to store result */ michael@0: region_type_t * reg1, /* First region in operation */ michael@0: region_type_t * reg2, /* 2d region in operation */ michael@0: overlap_proc_ptr overlap_func, /* Function to call for over- michael@0: * lapping bands */ michael@0: int append_non1, /* Append non-overlapping bands michael@0: * in region 1 ? michael@0: */ michael@0: int append_non2 /* Append non-overlapping bands michael@0: * in region 2 ? michael@0: */ michael@0: ) michael@0: { michael@0: box_type_t *r1; /* Pointer into first region */ michael@0: box_type_t *r2; /* Pointer into 2d region */ michael@0: box_type_t *r1_end; /* End of 1st region */ michael@0: box_type_t *r2_end; /* End of 2d region */ michael@0: int ybot; /* Bottom of intersection */ michael@0: int ytop; /* Top of intersection */ michael@0: region_data_type_t *old_data; /* Old data for new_reg */ michael@0: int prev_band; /* Index of start of michael@0: * previous band in new_reg */ michael@0: int cur_band; /* Index of start of current michael@0: * band in new_reg */ michael@0: box_type_t * r1_band_end; /* End of current band in r1 */ michael@0: box_type_t * r2_band_end; /* End of current band in r2 */ michael@0: int top; /* Top of non-overlapping band */ michael@0: int bot; /* Bottom of non-overlapping band*/ michael@0: int r1y1; /* Temps for r1->y1 and r2->y1 */ michael@0: int r2y1; michael@0: int new_size; michael@0: int numRects; michael@0: michael@0: /* michael@0: * Break any region computed from a broken region michael@0: */ michael@0: if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2)) michael@0: return pixman_break (new_reg); michael@0: michael@0: /* michael@0: * Initialization: michael@0: * set r1, r2, r1_end and r2_end appropriately, save the rectangles michael@0: * of the destination region until the end in case it's one of michael@0: * the two source regions, then mark the "new" region empty, allocating michael@0: * another array of rectangles for it to use. michael@0: */ michael@0: michael@0: r1 = PIXREGION_RECTS (reg1); michael@0: new_size = PIXREGION_NUMRECTS (reg1); michael@0: r1_end = r1 + new_size; michael@0: michael@0: numRects = PIXREGION_NUMRECTS (reg2); michael@0: r2 = PIXREGION_RECTS (reg2); michael@0: r2_end = r2 + numRects; michael@0: michael@0: critical_if_fail (r1 != r1_end); michael@0: critical_if_fail (r2 != r2_end); michael@0: michael@0: old_data = (region_data_type_t *)NULL; michael@0: michael@0: if (((new_reg == reg1) && (new_size > 1)) || michael@0: ((new_reg == reg2) && (numRects > 1))) michael@0: { michael@0: old_data = new_reg->data; michael@0: new_reg->data = pixman_region_empty_data; michael@0: } michael@0: michael@0: /* guess at new size */ michael@0: if (numRects > new_size) michael@0: new_size = numRects; michael@0: michael@0: new_size <<= 1; michael@0: michael@0: if (!new_reg->data) michael@0: new_reg->data = pixman_region_empty_data; michael@0: else if (new_reg->data->size) michael@0: new_reg->data->numRects = 0; michael@0: michael@0: if (new_size > new_reg->data->size) michael@0: { michael@0: if (!pixman_rect_alloc (new_reg, new_size)) michael@0: { michael@0: free (old_data); michael@0: return FALSE; michael@0: } michael@0: } michael@0: michael@0: /* michael@0: * Initialize ybot. michael@0: * In the upcoming loop, ybot and ytop serve different functions depending michael@0: * on whether the band being handled is an overlapping or non-overlapping michael@0: * band. michael@0: * In the case of a non-overlapping band (only one of the regions michael@0: * has points in the band), ybot is the bottom of the most recent michael@0: * intersection and thus clips the top of the rectangles in that band. michael@0: * ytop is the top of the next intersection between the two regions and michael@0: * serves to clip the bottom of the rectangles in the current band. michael@0: * For an overlapping band (where the two regions intersect), ytop clips michael@0: * the top of the rectangles of both regions and ybot clips the bottoms. michael@0: */ michael@0: michael@0: ybot = MIN (r1->y1, r2->y1); michael@0: michael@0: /* michael@0: * prev_band serves to mark the start of the previous band so rectangles michael@0: * can be coalesced into larger rectangles. qv. pixman_coalesce, above. michael@0: * In the beginning, there is no previous band, so prev_band == cur_band michael@0: * (cur_band is set later on, of course, but the first band will always michael@0: * start at index 0). prev_band and cur_band must be indices because of michael@0: * the possible expansion, and resultant moving, of the new region's michael@0: * array of rectangles. michael@0: */ michael@0: prev_band = 0; michael@0: michael@0: do michael@0: { michael@0: /* michael@0: * This algorithm proceeds one source-band (as opposed to a michael@0: * destination band, which is determined by where the two regions michael@0: * intersect) at a time. r1_band_end and r2_band_end serve to mark the michael@0: * rectangle after the last one in the current band for their michael@0: * respective regions. michael@0: */ michael@0: critical_if_fail (r1 != r1_end); michael@0: critical_if_fail (r2 != r2_end); michael@0: michael@0: FIND_BAND (r1, r1_band_end, r1_end, r1y1); michael@0: FIND_BAND (r2, r2_band_end, r2_end, r2y1); michael@0: michael@0: /* michael@0: * First handle the band that doesn't intersect, if any. michael@0: * michael@0: * Note that attention is restricted to one band in the michael@0: * non-intersecting region at once, so if a region has n michael@0: * bands between the current position and the next place it overlaps michael@0: * the other, this entire loop will be passed through n times. michael@0: */ michael@0: if (r1y1 < r2y1) michael@0: { michael@0: if (append_non1) michael@0: { michael@0: top = MAX (r1y1, ybot); michael@0: bot = MIN (r1->y2, r2y1); michael@0: if (top != bot) michael@0: { michael@0: cur_band = new_reg->data->numRects; michael@0: if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot)) michael@0: goto bail; michael@0: COALESCE (new_reg, prev_band, cur_band); michael@0: } michael@0: } michael@0: ytop = r2y1; michael@0: } michael@0: else if (r2y1 < r1y1) michael@0: { michael@0: if (append_non2) michael@0: { michael@0: top = MAX (r2y1, ybot); michael@0: bot = MIN (r2->y2, r1y1); michael@0: michael@0: if (top != bot) michael@0: { michael@0: cur_band = new_reg->data->numRects; michael@0: michael@0: if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot)) michael@0: goto bail; michael@0: michael@0: COALESCE (new_reg, prev_band, cur_band); michael@0: } michael@0: } michael@0: ytop = r1y1; michael@0: } michael@0: else michael@0: { michael@0: ytop = r1y1; michael@0: } michael@0: michael@0: /* michael@0: * Now see if we've hit an intersecting band. The two bands only michael@0: * intersect if ybot > ytop michael@0: */ michael@0: ybot = MIN (r1->y2, r2->y2); michael@0: if (ybot > ytop) michael@0: { michael@0: cur_band = new_reg->data->numRects; michael@0: michael@0: if (!(*overlap_func)(new_reg, michael@0: r1, r1_band_end, michael@0: r2, r2_band_end, michael@0: ytop, ybot)) michael@0: { michael@0: goto bail; michael@0: } michael@0: michael@0: COALESCE (new_reg, prev_band, cur_band); michael@0: } michael@0: michael@0: /* michael@0: * If we've finished with a band (y2 == ybot) we skip forward michael@0: * in the region to the next band. michael@0: */ michael@0: if (r1->y2 == ybot) michael@0: r1 = r1_band_end; michael@0: michael@0: if (r2->y2 == ybot) michael@0: r2 = r2_band_end; michael@0: michael@0: } michael@0: while (r1 != r1_end && r2 != r2_end); michael@0: michael@0: /* michael@0: * Deal with whichever region (if any) still has rectangles left. michael@0: * michael@0: * We only need to worry about banding and coalescing for the very first michael@0: * band left. After that, we can just group all remaining boxes, michael@0: * regardless of how many bands, into one final append to the list. michael@0: */ michael@0: michael@0: if ((r1 != r1_end) && append_non1) michael@0: { michael@0: /* Do first non_overlap1Func call, which may be able to coalesce */ michael@0: FIND_BAND (r1, r1_band_end, r1_end, r1y1); michael@0: michael@0: cur_band = new_reg->data->numRects; michael@0: michael@0: if (!pixman_region_append_non_o (new_reg, michael@0: r1, r1_band_end, michael@0: MAX (r1y1, ybot), r1->y2)) michael@0: { michael@0: goto bail; michael@0: } michael@0: michael@0: COALESCE (new_reg, prev_band, cur_band); michael@0: michael@0: /* Just append the rest of the boxes */ michael@0: APPEND_REGIONS (new_reg, r1_band_end, r1_end); michael@0: } michael@0: else if ((r2 != r2_end) && append_non2) michael@0: { michael@0: /* Do first non_overlap2Func call, which may be able to coalesce */ michael@0: FIND_BAND (r2, r2_band_end, r2_end, r2y1); michael@0: michael@0: cur_band = new_reg->data->numRects; michael@0: michael@0: if (!pixman_region_append_non_o (new_reg, michael@0: r2, r2_band_end, michael@0: MAX (r2y1, ybot), r2->y2)) michael@0: { michael@0: goto bail; michael@0: } michael@0: michael@0: COALESCE (new_reg, prev_band, cur_band); michael@0: michael@0: /* Append rest of boxes */ michael@0: APPEND_REGIONS (new_reg, r2_band_end, r2_end); michael@0: } michael@0: michael@0: free (old_data); michael@0: michael@0: if (!(numRects = new_reg->data->numRects)) michael@0: { michael@0: FREE_DATA (new_reg); michael@0: new_reg->data = pixman_region_empty_data; michael@0: } michael@0: else if (numRects == 1) michael@0: { michael@0: new_reg->extents = *PIXREGION_BOXPTR (new_reg); michael@0: FREE_DATA (new_reg); michael@0: new_reg->data = (region_data_type_t *)NULL; michael@0: } michael@0: else michael@0: { michael@0: DOWNSIZE (new_reg, numRects); michael@0: } michael@0: michael@0: return TRUE; michael@0: michael@0: bail: michael@0: free (old_data); michael@0: michael@0: return pixman_break (new_reg); michael@0: } michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_set_extents -- michael@0: * Reset the extents of a region to what they should be. Called by michael@0: * pixman_region_subtract and pixman_region_intersect as they can't michael@0: * figure it out along the way or do so easily, as pixman_region_union can. michael@0: * michael@0: * Results: michael@0: * None. michael@0: * michael@0: * Side Effects: michael@0: * The region's 'extents' structure is overwritten. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: static void michael@0: pixman_set_extents (region_type_t *region) michael@0: { michael@0: box_type_t *box, *box_end; michael@0: michael@0: if (!region->data) michael@0: return; michael@0: michael@0: if (!region->data->size) michael@0: { michael@0: region->extents.x2 = region->extents.x1; michael@0: region->extents.y2 = region->extents.y1; michael@0: return; michael@0: } michael@0: michael@0: box = PIXREGION_BOXPTR (region); michael@0: box_end = PIXREGION_END (region); michael@0: michael@0: /* michael@0: * Since box is the first rectangle in the region, it must have the michael@0: * smallest y1 and since box_end is the last rectangle in the region, michael@0: * it must have the largest y2, because of banding. Initialize x1 and michael@0: * x2 from box and box_end, resp., as good things to initialize them michael@0: * to... michael@0: */ michael@0: region->extents.x1 = box->x1; michael@0: region->extents.y1 = box->y1; michael@0: region->extents.x2 = box_end->x2; michael@0: region->extents.y2 = box_end->y2; michael@0: michael@0: critical_if_fail (region->extents.y1 < region->extents.y2); michael@0: michael@0: while (box <= box_end) michael@0: { michael@0: if (box->x1 < region->extents.x1) michael@0: region->extents.x1 = box->x1; michael@0: if (box->x2 > region->extents.x2) michael@0: region->extents.x2 = box->x2; michael@0: box++; michael@0: } michael@0: michael@0: critical_if_fail (region->extents.x1 < region->extents.x2); michael@0: } michael@0: michael@0: /*====================================================================== michael@0: * Region Intersection michael@0: *====================================================================*/ michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_region_intersect_o -- michael@0: * Handle an overlapping band for pixman_region_intersect. michael@0: * michael@0: * Results: michael@0: * TRUE if successful. michael@0: * michael@0: * Side Effects: michael@0: * Rectangles may be added to the region. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: /*ARGSUSED*/ michael@0: static pixman_bool_t michael@0: pixman_region_intersect_o (region_type_t *region, michael@0: box_type_t * r1, michael@0: box_type_t * r1_end, michael@0: box_type_t * r2, michael@0: box_type_t * r2_end, michael@0: int y1, michael@0: int y2) michael@0: { michael@0: int x1; michael@0: int x2; michael@0: box_type_t * next_rect; michael@0: michael@0: next_rect = PIXREGION_TOP (region); michael@0: michael@0: critical_if_fail (y1 < y2); michael@0: critical_if_fail (r1 != r1_end && r2 != r2_end); michael@0: michael@0: do michael@0: { michael@0: x1 = MAX (r1->x1, r2->x1); michael@0: x2 = MIN (r1->x2, r2->x2); michael@0: michael@0: /* michael@0: * If there's any overlap between the two rectangles, add that michael@0: * overlap to the new region. michael@0: */ michael@0: if (x1 < x2) michael@0: NEWRECT (region, next_rect, x1, y1, x2, y2); michael@0: michael@0: /* michael@0: * Advance the pointer(s) with the leftmost right side, since the next michael@0: * rectangle on that list may still overlap the other region's michael@0: * current rectangle. michael@0: */ michael@0: if (r1->x2 == x2) michael@0: { michael@0: r1++; michael@0: } michael@0: if (r2->x2 == x2) michael@0: { michael@0: r2++; michael@0: } michael@0: } michael@0: while ((r1 != r1_end) && (r2 != r2_end)); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_intersect) (region_type_t * new_reg, michael@0: region_type_t * reg1, michael@0: region_type_t * reg2) michael@0: { michael@0: GOOD (reg1); michael@0: GOOD (reg2); michael@0: GOOD (new_reg); michael@0: michael@0: /* check for trivial reject */ michael@0: if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) || michael@0: !EXTENTCHECK (®1->extents, ®2->extents)) michael@0: { michael@0: /* Covers about 20% of all cases */ michael@0: FREE_DATA (new_reg); michael@0: new_reg->extents.x2 = new_reg->extents.x1; michael@0: new_reg->extents.y2 = new_reg->extents.y1; michael@0: if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2)) michael@0: { michael@0: new_reg->data = pixman_broken_data; michael@0: return FALSE; michael@0: } michael@0: else michael@0: { michael@0: new_reg->data = pixman_region_empty_data; michael@0: } michael@0: } michael@0: else if (!reg1->data && !reg2->data) michael@0: { michael@0: /* Covers about 80% of cases that aren't trivially rejected */ michael@0: new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1); michael@0: new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1); michael@0: new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2); michael@0: new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2); michael@0: michael@0: FREE_DATA (new_reg); michael@0: michael@0: new_reg->data = (region_data_type_t *)NULL; michael@0: } michael@0: else if (!reg2->data && SUBSUMES (®2->extents, ®1->extents)) michael@0: { michael@0: return PREFIX (_copy) (new_reg, reg1); michael@0: } michael@0: else if (!reg1->data && SUBSUMES (®1->extents, ®2->extents)) michael@0: { michael@0: return PREFIX (_copy) (new_reg, reg2); michael@0: } michael@0: else if (reg1 == reg2) michael@0: { michael@0: return PREFIX (_copy) (new_reg, reg1); michael@0: } michael@0: else michael@0: { michael@0: /* General purpose intersection */ michael@0: michael@0: if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE)) michael@0: return FALSE; michael@0: michael@0: pixman_set_extents (new_reg); michael@0: } michael@0: michael@0: GOOD (new_reg); michael@0: return(TRUE); michael@0: } michael@0: michael@0: #define MERGERECT(r) \ michael@0: do \ michael@0: { \ michael@0: if (r->x1 <= x2) \ michael@0: { \ michael@0: /* Merge with current rectangle */ \ michael@0: if (x2 < r->x2) \ michael@0: x2 = r->x2; \ michael@0: } \ michael@0: else \ michael@0: { \ michael@0: /* Add current rectangle, start new one */ \ michael@0: NEWRECT (region, next_rect, x1, y1, x2, y2); \ michael@0: x1 = r->x1; \ michael@0: x2 = r->x2; \ michael@0: } \ michael@0: r++; \ michael@0: } while (0) michael@0: michael@0: /*====================================================================== michael@0: * Region Union michael@0: *====================================================================*/ michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_region_union_o -- michael@0: * Handle an overlapping band for the union operation. Picks the michael@0: * left-most rectangle each time and merges it into the region. michael@0: * michael@0: * Results: michael@0: * TRUE if successful. michael@0: * michael@0: * Side Effects: michael@0: * region is overwritten. michael@0: * overlap is set to TRUE if any boxes overlap. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: static pixman_bool_t michael@0: pixman_region_union_o (region_type_t *region, michael@0: box_type_t * r1, michael@0: box_type_t * r1_end, michael@0: box_type_t * r2, michael@0: box_type_t * r2_end, michael@0: int y1, michael@0: int y2) michael@0: { michael@0: box_type_t *next_rect; michael@0: int x1; /* left and right side of current union */ michael@0: int x2; michael@0: michael@0: critical_if_fail (y1 < y2); michael@0: critical_if_fail (r1 != r1_end && r2 != r2_end); michael@0: michael@0: next_rect = PIXREGION_TOP (region); michael@0: michael@0: /* Start off current rectangle */ michael@0: if (r1->x1 < r2->x1) michael@0: { michael@0: x1 = r1->x1; michael@0: x2 = r1->x2; michael@0: r1++; michael@0: } michael@0: else michael@0: { michael@0: x1 = r2->x1; michael@0: x2 = r2->x2; michael@0: r2++; michael@0: } michael@0: while (r1 != r1_end && r2 != r2_end) michael@0: { michael@0: if (r1->x1 < r2->x1) michael@0: MERGERECT (r1); michael@0: else michael@0: MERGERECT (r2); michael@0: } michael@0: michael@0: /* Finish off whoever (if any) is left */ michael@0: if (r1 != r1_end) michael@0: { michael@0: do michael@0: { michael@0: MERGERECT (r1); michael@0: } michael@0: while (r1 != r1_end); michael@0: } michael@0: else if (r2 != r2_end) michael@0: { michael@0: do michael@0: { michael@0: MERGERECT (r2); michael@0: } michael@0: while (r2 != r2_end); michael@0: } michael@0: michael@0: /* Add current rectangle */ michael@0: NEWRECT (region, next_rect, x1, y1, x2, y2); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX(_intersect_rect) (region_type_t *dest, michael@0: region_type_t *source, michael@0: int x, int y, michael@0: unsigned int width, michael@0: unsigned int height) michael@0: { michael@0: region_type_t region; michael@0: michael@0: region.data = NULL; michael@0: region.extents.x1 = x; michael@0: region.extents.y1 = y; michael@0: region.extents.x2 = x + width; michael@0: region.extents.y2 = y + height; michael@0: michael@0: return PREFIX(_intersect) (dest, source, ®ion); michael@0: } michael@0: michael@0: /* Convenience function for performing union of region with a michael@0: * single rectangle michael@0: */ michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_union_rect) (region_type_t *dest, michael@0: region_type_t *source, michael@0: int x, michael@0: int y, michael@0: unsigned int width, michael@0: unsigned int height) michael@0: { michael@0: region_type_t region; michael@0: michael@0: region.extents.x1 = x; michael@0: region.extents.y1 = y; michael@0: region.extents.x2 = x + width; michael@0: region.extents.y2 = y + height; michael@0: michael@0: if (!GOOD_RECT (®ion.extents)) michael@0: { michael@0: if (BAD_RECT (®ion.extents)) michael@0: _pixman_log_error (FUNC, "Invalid rectangle passed"); michael@0: return PREFIX (_copy) (dest, source); michael@0: } michael@0: michael@0: region.data = NULL; michael@0: michael@0: return PREFIX (_union) (dest, source, ®ion); michael@0: } michael@0: michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_union) (region_type_t *new_reg, michael@0: region_type_t *reg1, michael@0: region_type_t *reg2) michael@0: { michael@0: /* Return TRUE if some overlap michael@0: * between reg1, reg2 michael@0: */ michael@0: GOOD (reg1); michael@0: GOOD (reg2); michael@0: GOOD (new_reg); michael@0: michael@0: /* checks all the simple cases */ michael@0: michael@0: /* michael@0: * Region 1 and 2 are the same michael@0: */ michael@0: if (reg1 == reg2) michael@0: return PREFIX (_copy) (new_reg, reg1); michael@0: michael@0: /* michael@0: * Region 1 is empty michael@0: */ michael@0: if (PIXREGION_NIL (reg1)) michael@0: { michael@0: if (PIXREGION_NAR (reg1)) michael@0: return pixman_break (new_reg); michael@0: michael@0: if (new_reg != reg2) michael@0: return PREFIX (_copy) (new_reg, reg2); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /* michael@0: * Region 2 is empty michael@0: */ michael@0: if (PIXREGION_NIL (reg2)) michael@0: { michael@0: if (PIXREGION_NAR (reg2)) michael@0: return pixman_break (new_reg); michael@0: michael@0: if (new_reg != reg1) michael@0: return PREFIX (_copy) (new_reg, reg1); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /* michael@0: * Region 1 completely subsumes region 2 michael@0: */ michael@0: if (!reg1->data && SUBSUMES (®1->extents, ®2->extents)) michael@0: { michael@0: if (new_reg != reg1) michael@0: return PREFIX (_copy) (new_reg, reg1); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /* michael@0: * Region 2 completely subsumes region 1 michael@0: */ michael@0: if (!reg2->data && SUBSUMES (®2->extents, ®1->extents)) michael@0: { michael@0: if (new_reg != reg2) michael@0: return PREFIX (_copy) (new_reg, reg2); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE)) michael@0: return FALSE; michael@0: michael@0: new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1); michael@0: new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1); michael@0: new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2); michael@0: new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2); michael@0: michael@0: GOOD (new_reg); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /*====================================================================== michael@0: * Batch Rectangle Union michael@0: *====================================================================*/ michael@0: michael@0: #define EXCHANGE_RECTS(a, b) \ michael@0: { \ michael@0: box_type_t t; \ michael@0: t = rects[a]; \ michael@0: rects[a] = rects[b]; \ michael@0: rects[b] = t; \ michael@0: } michael@0: michael@0: static void michael@0: quick_sort_rects ( michael@0: box_type_t rects[], michael@0: int numRects) michael@0: { michael@0: int y1; michael@0: int x1; michael@0: int i, j; michael@0: box_type_t *r; michael@0: michael@0: /* Always called with numRects > 1 */ michael@0: michael@0: do michael@0: { michael@0: if (numRects == 2) michael@0: { michael@0: if (rects[0].y1 > rects[1].y1 || michael@0: (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1)) michael@0: { michael@0: EXCHANGE_RECTS (0, 1); michael@0: } michael@0: michael@0: return; michael@0: } michael@0: michael@0: /* Choose partition element, stick in location 0 */ michael@0: EXCHANGE_RECTS (0, numRects >> 1); michael@0: y1 = rects[0].y1; michael@0: x1 = rects[0].x1; michael@0: michael@0: /* Partition array */ michael@0: i = 0; michael@0: j = numRects; michael@0: michael@0: do michael@0: { michael@0: r = &(rects[i]); michael@0: do michael@0: { michael@0: r++; michael@0: i++; michael@0: } michael@0: while (i != numRects && (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1))); michael@0: michael@0: r = &(rects[j]); michael@0: do michael@0: { michael@0: r--; michael@0: j--; michael@0: } michael@0: while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1)); michael@0: michael@0: if (i < j) michael@0: EXCHANGE_RECTS (i, j); michael@0: } michael@0: while (i < j); michael@0: michael@0: /* Move partition element back to middle */ michael@0: EXCHANGE_RECTS (0, j); michael@0: michael@0: /* Recurse */ michael@0: if (numRects - j - 1 > 1) michael@0: quick_sort_rects (&rects[j + 1], numRects - j - 1); michael@0: michael@0: numRects = j; michael@0: } michael@0: while (numRects > 1); michael@0: } michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_region_validate -- michael@0: * michael@0: * Take a ``region'' which is a non-y-x-banded random collection of michael@0: * rectangles, and compute a nice region which is the union of all the michael@0: * rectangles. michael@0: * michael@0: * Results: michael@0: * TRUE if successful. michael@0: * michael@0: * Side Effects: michael@0: * The passed-in ``region'' may be modified. michael@0: * overlap set to TRUE if any retangles overlapped, michael@0: * else FALSE; michael@0: * michael@0: * Strategy: michael@0: * Step 1. Sort the rectangles into ascending order with primary key y1 michael@0: * and secondary key x1. michael@0: * michael@0: * Step 2. Split the rectangles into the minimum number of proper y-x michael@0: * banded regions. This may require horizontally merging michael@0: * rectangles, and vertically coalescing bands. With any luck, michael@0: * this step in an identity transformation (ala the Box widget), michael@0: * or a coalescing into 1 box (ala Menus). michael@0: * michael@0: * Step 3. Merge the separate regions down to a single region by calling michael@0: * pixman_region_union. Maximize the work each pixman_region_union call does by using michael@0: * a binary merge. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: michael@0: static pixman_bool_t michael@0: validate (region_type_t * badreg) michael@0: { michael@0: /* Descriptor for regions under construction in Step 2. */ michael@0: typedef struct michael@0: { michael@0: region_type_t reg; michael@0: int prev_band; michael@0: int cur_band; michael@0: } region_info_t; michael@0: michael@0: region_info_t stack_regions[64]; michael@0: michael@0: int numRects; /* Original numRects for badreg */ michael@0: region_info_t *ri; /* Array of current regions */ michael@0: int num_ri; /* Number of entries used in ri */ michael@0: int size_ri; /* Number of entries available in ri */ michael@0: int i; /* Index into rects */ michael@0: int j; /* Index into ri */ michael@0: region_info_t *rit; /* &ri[j] */ michael@0: region_type_t *reg; /* ri[j].reg */ michael@0: box_type_t *box; /* Current box in rects */ michael@0: box_type_t *ri_box; /* Last box in ri[j].reg */ michael@0: region_type_t *hreg; /* ri[j_half].reg */ michael@0: pixman_bool_t ret = TRUE; michael@0: michael@0: if (!badreg->data) michael@0: { michael@0: GOOD (badreg); michael@0: return TRUE; michael@0: } michael@0: michael@0: numRects = badreg->data->numRects; michael@0: if (!numRects) michael@0: { michael@0: if (PIXREGION_NAR (badreg)) michael@0: return FALSE; michael@0: GOOD (badreg); michael@0: return TRUE; michael@0: } michael@0: michael@0: if (badreg->extents.x1 < badreg->extents.x2) michael@0: { michael@0: if ((numRects) == 1) michael@0: { michael@0: FREE_DATA (badreg); michael@0: badreg->data = (region_data_type_t *) NULL; michael@0: } michael@0: else michael@0: { michael@0: DOWNSIZE (badreg, numRects); michael@0: } michael@0: michael@0: GOOD (badreg); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /* Step 1: Sort the rects array into ascending (y1, x1) order */ michael@0: quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects); michael@0: michael@0: /* Step 2: Scatter the sorted array into the minimum number of regions */ michael@0: michael@0: /* Set up the first region to be the first rectangle in badreg */ michael@0: /* Note that step 2 code will never overflow the ri[0].reg rects array */ michael@0: ri = stack_regions; michael@0: size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]); michael@0: num_ri = 1; michael@0: ri[0].prev_band = 0; michael@0: ri[0].cur_band = 0; michael@0: ri[0].reg = *badreg; michael@0: box = PIXREGION_BOXPTR (&ri[0].reg); michael@0: ri[0].reg.extents = *box; michael@0: ri[0].reg.data->numRects = 1; michael@0: badreg->extents = *pixman_region_empty_box; michael@0: badreg->data = pixman_region_empty_data; michael@0: michael@0: /* Now scatter rectangles into the minimum set of valid regions. If the michael@0: * next rectangle to be added to a region would force an existing rectangle michael@0: * in the region to be split up in order to maintain y-x banding, just michael@0: * forget it. Try the next region. If it doesn't fit cleanly into any michael@0: * region, make a new one. michael@0: */ michael@0: michael@0: for (i = numRects; --i > 0;) michael@0: { michael@0: box++; michael@0: /* Look for a region to append box to */ michael@0: for (j = num_ri, rit = ri; --j >= 0; rit++) michael@0: { michael@0: reg = &rit->reg; michael@0: ri_box = PIXREGION_END (reg); michael@0: michael@0: if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2) michael@0: { michael@0: /* box is in same band as ri_box. Merge or append it */ michael@0: if (box->x1 <= ri_box->x2) michael@0: { michael@0: /* Merge it with ri_box */ michael@0: if (box->x2 > ri_box->x2) michael@0: ri_box->x2 = box->x2; michael@0: } michael@0: else michael@0: { michael@0: RECTALLOC_BAIL (reg, 1, bail); michael@0: *PIXREGION_TOP (reg) = *box; michael@0: reg->data->numRects++; michael@0: } michael@0: michael@0: goto next_rect; /* So sue me */ michael@0: } michael@0: else if (box->y1 >= ri_box->y2) michael@0: { michael@0: /* Put box into new band */ michael@0: if (reg->extents.x2 < ri_box->x2) michael@0: reg->extents.x2 = ri_box->x2; michael@0: michael@0: if (reg->extents.x1 > box->x1) michael@0: reg->extents.x1 = box->x1; michael@0: michael@0: COALESCE (reg, rit->prev_band, rit->cur_band); michael@0: rit->cur_band = reg->data->numRects; michael@0: RECTALLOC_BAIL (reg, 1, bail); michael@0: *PIXREGION_TOP (reg) = *box; michael@0: reg->data->numRects++; michael@0: michael@0: goto next_rect; michael@0: } michael@0: /* Well, this region was inappropriate. Try the next one. */ michael@0: } /* for j */ michael@0: michael@0: /* Uh-oh. No regions were appropriate. Create a new one. */ michael@0: if (size_ri == num_ri) michael@0: { michael@0: size_t data_size; michael@0: michael@0: /* Oops, allocate space for new region information */ michael@0: size_ri <<= 1; michael@0: michael@0: data_size = size_ri * sizeof(region_info_t); michael@0: if (data_size / size_ri != sizeof(region_info_t)) michael@0: goto bail; michael@0: michael@0: if (ri == stack_regions) michael@0: { michael@0: rit = malloc (data_size); michael@0: if (!rit) michael@0: goto bail; michael@0: memcpy (rit, ri, num_ri * sizeof (region_info_t)); michael@0: } michael@0: else michael@0: { michael@0: rit = (region_info_t *) realloc (ri, data_size); michael@0: if (!rit) michael@0: goto bail; michael@0: } michael@0: ri = rit; michael@0: rit = &ri[num_ri]; michael@0: } michael@0: num_ri++; michael@0: rit->prev_band = 0; michael@0: rit->cur_band = 0; michael@0: rit->reg.extents = *box; michael@0: rit->reg.data = (region_data_type_t *)NULL; michael@0: michael@0: /* MUST force allocation */ michael@0: if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri)) michael@0: goto bail; michael@0: michael@0: next_rect: ; michael@0: } /* for i */ michael@0: michael@0: /* Make a final pass over each region in order to COALESCE and set michael@0: * extents.x2 and extents.y2 michael@0: */ michael@0: for (j = num_ri, rit = ri; --j >= 0; rit++) michael@0: { michael@0: reg = &rit->reg; michael@0: ri_box = PIXREGION_END (reg); michael@0: reg->extents.y2 = ri_box->y2; michael@0: michael@0: if (reg->extents.x2 < ri_box->x2) michael@0: reg->extents.x2 = ri_box->x2; michael@0: michael@0: COALESCE (reg, rit->prev_band, rit->cur_band); michael@0: michael@0: if (reg->data->numRects == 1) /* keep unions happy below */ michael@0: { michael@0: FREE_DATA (reg); michael@0: reg->data = (region_data_type_t *)NULL; michael@0: } michael@0: } michael@0: michael@0: /* Step 3: Union all regions into a single region */ michael@0: while (num_ri > 1) michael@0: { michael@0: int half = num_ri / 2; michael@0: for (j = num_ri & 1; j < (half + (num_ri & 1)); j++) michael@0: { michael@0: reg = &ri[j].reg; michael@0: hreg = &ri[j + half].reg; michael@0: michael@0: if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE)) michael@0: ret = FALSE; michael@0: michael@0: if (hreg->extents.x1 < reg->extents.x1) michael@0: reg->extents.x1 = hreg->extents.x1; michael@0: michael@0: if (hreg->extents.y1 < reg->extents.y1) michael@0: reg->extents.y1 = hreg->extents.y1; michael@0: michael@0: if (hreg->extents.x2 > reg->extents.x2) michael@0: reg->extents.x2 = hreg->extents.x2; michael@0: michael@0: if (hreg->extents.y2 > reg->extents.y2) michael@0: reg->extents.y2 = hreg->extents.y2; michael@0: michael@0: FREE_DATA (hreg); michael@0: } michael@0: michael@0: num_ri -= half; michael@0: michael@0: if (!ret) michael@0: goto bail; michael@0: } michael@0: michael@0: *badreg = ri[0].reg; michael@0: michael@0: if (ri != stack_regions) michael@0: free (ri); michael@0: michael@0: GOOD (badreg); michael@0: return ret; michael@0: michael@0: bail: michael@0: for (i = 0; i < num_ri; i++) michael@0: FREE_DATA (&ri[i].reg); michael@0: michael@0: if (ri != stack_regions) michael@0: free (ri); michael@0: michael@0: return pixman_break (badreg); michael@0: } michael@0: michael@0: /*====================================================================== michael@0: * Region Subtraction michael@0: *====================================================================*/ michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_region_subtract_o -- michael@0: * Overlapping band subtraction. x1 is the left-most point not yet michael@0: * checked. michael@0: * michael@0: * Results: michael@0: * TRUE if successful. michael@0: * michael@0: * Side Effects: michael@0: * region may have rectangles added to it. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: /*ARGSUSED*/ michael@0: static pixman_bool_t michael@0: pixman_region_subtract_o (region_type_t * region, michael@0: box_type_t * r1, michael@0: box_type_t * r1_end, michael@0: box_type_t * r2, michael@0: box_type_t * r2_end, michael@0: int y1, michael@0: int y2) michael@0: { michael@0: box_type_t * next_rect; michael@0: int x1; michael@0: michael@0: x1 = r1->x1; michael@0: michael@0: critical_if_fail (y1 < y2); michael@0: critical_if_fail (r1 != r1_end && r2 != r2_end); michael@0: michael@0: next_rect = PIXREGION_TOP (region); michael@0: michael@0: do michael@0: { michael@0: if (r2->x2 <= x1) michael@0: { michael@0: /* michael@0: * Subtrahend entirely to left of minuend: go to next subtrahend. michael@0: */ michael@0: r2++; michael@0: } michael@0: else if (r2->x1 <= x1) michael@0: { michael@0: /* michael@0: * Subtrahend preceeds minuend: nuke left edge of minuend. michael@0: */ michael@0: x1 = r2->x2; michael@0: if (x1 >= r1->x2) michael@0: { michael@0: /* michael@0: * Minuend completely covered: advance to next minuend and michael@0: * reset left fence to edge of new minuend. michael@0: */ michael@0: r1++; michael@0: if (r1 != r1_end) michael@0: x1 = r1->x1; michael@0: } michael@0: else michael@0: { michael@0: /* michael@0: * Subtrahend now used up since it doesn't extend beyond michael@0: * minuend michael@0: */ michael@0: r2++; michael@0: } michael@0: } michael@0: else if (r2->x1 < r1->x2) michael@0: { michael@0: /* michael@0: * Left part of subtrahend covers part of minuend: add uncovered michael@0: * part of minuend to region and skip to next subtrahend. michael@0: */ michael@0: critical_if_fail (x1 < r2->x1); michael@0: NEWRECT (region, next_rect, x1, y1, r2->x1, y2); michael@0: michael@0: x1 = r2->x2; michael@0: if (x1 >= r1->x2) michael@0: { michael@0: /* michael@0: * Minuend used up: advance to new... michael@0: */ michael@0: r1++; michael@0: if (r1 != r1_end) michael@0: x1 = r1->x1; michael@0: } michael@0: else michael@0: { michael@0: /* michael@0: * Subtrahend used up michael@0: */ michael@0: r2++; michael@0: } michael@0: } michael@0: else michael@0: { michael@0: /* michael@0: * Minuend used up: add any remaining piece before advancing. michael@0: */ michael@0: if (r1->x2 > x1) michael@0: NEWRECT (region, next_rect, x1, y1, r1->x2, y2); michael@0: michael@0: r1++; michael@0: michael@0: if (r1 != r1_end) michael@0: x1 = r1->x1; michael@0: } michael@0: } michael@0: while ((r1 != r1_end) && (r2 != r2_end)); michael@0: michael@0: /* michael@0: * Add remaining minuend rectangles to region. michael@0: */ michael@0: while (r1 != r1_end) michael@0: { michael@0: critical_if_fail (x1 < r1->x2); michael@0: michael@0: NEWRECT (region, next_rect, x1, y1, r1->x2, y2); michael@0: michael@0: r1++; michael@0: if (r1 != r1_end) michael@0: x1 = r1->x1; michael@0: } michael@0: return TRUE; michael@0: } michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_region_subtract -- michael@0: * Subtract reg_s from reg_m and leave the result in reg_d. michael@0: * S stands for subtrahend, M for minuend and D for difference. michael@0: * michael@0: * Results: michael@0: * TRUE if successful. michael@0: * michael@0: * Side Effects: michael@0: * reg_d is overwritten. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_subtract) (region_type_t *reg_d, michael@0: region_type_t *reg_m, michael@0: region_type_t *reg_s) michael@0: { michael@0: GOOD (reg_m); michael@0: GOOD (reg_s); michael@0: GOOD (reg_d); michael@0: michael@0: /* check for trivial rejects */ michael@0: if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) || michael@0: !EXTENTCHECK (®_m->extents, ®_s->extents)) michael@0: { michael@0: if (PIXREGION_NAR (reg_s)) michael@0: return pixman_break (reg_d); michael@0: michael@0: return PREFIX (_copy) (reg_d, reg_m); michael@0: } michael@0: else if (reg_m == reg_s) michael@0: { michael@0: FREE_DATA (reg_d); michael@0: reg_d->extents.x2 = reg_d->extents.x1; michael@0: reg_d->extents.y2 = reg_d->extents.y1; michael@0: reg_d->data = pixman_region_empty_data; michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /* Add those rectangles in region 1 that aren't in region 2, michael@0: do yucky substraction for overlaps, and michael@0: just throw away rectangles in region 2 that aren't in region 1 */ michael@0: if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE)) michael@0: return FALSE; michael@0: michael@0: /* michael@0: * Can't alter reg_d's extents before we call pixman_op because michael@0: * it might be one of the source regions and pixman_op depends michael@0: * on the extents of those regions being unaltered. Besides, this michael@0: * way there's no checking against rectangles that will be nuked michael@0: * due to coalescing, so we have to examine fewer rectangles. michael@0: */ michael@0: pixman_set_extents (reg_d); michael@0: GOOD (reg_d); michael@0: return TRUE; michael@0: } michael@0: michael@0: /*====================================================================== michael@0: * Region Inversion michael@0: *====================================================================*/ michael@0: michael@0: /*- michael@0: *----------------------------------------------------------------------- michael@0: * pixman_region_inverse -- michael@0: * Take a region and a box and return a region that is everything michael@0: * in the box but not in the region. The careful reader will note michael@0: * that this is the same as subtracting the region from the box... michael@0: * michael@0: * Results: michael@0: * TRUE. michael@0: * michael@0: * Side Effects: michael@0: * new_reg is overwritten. michael@0: * michael@0: *----------------------------------------------------------------------- michael@0: */ michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_inverse) (region_type_t *new_reg, /* Destination region */ michael@0: region_type_t *reg1, /* Region to invert */ michael@0: box_type_t * inv_rect) /* Bounding box for inversion */ michael@0: { michael@0: region_type_t inv_reg; /* Quick and dirty region made from the michael@0: * bounding box */ michael@0: GOOD (reg1); michael@0: GOOD (new_reg); michael@0: michael@0: /* check for trivial rejects */ michael@0: if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, ®1->extents)) michael@0: { michael@0: if (PIXREGION_NAR (reg1)) michael@0: return pixman_break (new_reg); michael@0: michael@0: new_reg->extents = *inv_rect; michael@0: FREE_DATA (new_reg); michael@0: new_reg->data = (region_data_type_t *)NULL; michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /* Add those rectangles in region 1 that aren't in region 2, michael@0: * do yucky substraction for overlaps, and michael@0: * just throw away rectangles in region 2 that aren't in region 1 michael@0: */ michael@0: inv_reg.extents = *inv_rect; michael@0: inv_reg.data = (region_data_type_t *)NULL; michael@0: if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE)) michael@0: return FALSE; michael@0: michael@0: /* michael@0: * Can't alter new_reg's extents before we call pixman_op because michael@0: * it might be one of the source regions and pixman_op depends michael@0: * on the extents of those regions being unaltered. Besides, this michael@0: * way there's no checking against rectangles that will be nuked michael@0: * due to coalescing, so we have to examine fewer rectangles. michael@0: */ michael@0: pixman_set_extents (new_reg); michael@0: GOOD (new_reg); michael@0: return TRUE; michael@0: } michael@0: michael@0: /* In time O(log n), locate the first box whose y2 is greater than y. michael@0: * Return @end if no such box exists. michael@0: */ michael@0: static box_type_t * michael@0: find_box_for_y (box_type_t *begin, box_type_t *end, int y) michael@0: { michael@0: box_type_t *mid; michael@0: michael@0: if (end == begin) michael@0: return end; michael@0: michael@0: if (end - begin == 1) michael@0: { michael@0: if (begin->y2 > y) michael@0: return begin; michael@0: else michael@0: return end; michael@0: } michael@0: michael@0: mid = begin + (end - begin) / 2; michael@0: if (mid->y2 > y) michael@0: { michael@0: /* If no box is found in [begin, mid], the function michael@0: * will return @mid, which is then known to be the michael@0: * correct answer. michael@0: */ michael@0: return find_box_for_y (begin, mid, y); michael@0: } michael@0: else michael@0: { michael@0: return find_box_for_y (mid, end, y); michael@0: } michael@0: } michael@0: michael@0: /* michael@0: * rect_in(region, rect) michael@0: * This routine takes a pointer to a region and a pointer to a box michael@0: * and determines if the box is outside/inside/partly inside the region. michael@0: * michael@0: * The idea is to travel through the list of rectangles trying to cover the michael@0: * passed box with them. Anytime a piece of the rectangle isn't covered michael@0: * by a band of rectangles, part_out is set TRUE. Any time a rectangle in michael@0: * the region covers part of the box, part_in is set TRUE. The process ends michael@0: * when either the box has been completely covered (we reached a band that michael@0: * doesn't overlap the box, part_in is TRUE and part_out is false), the michael@0: * box has been partially covered (part_in == part_out == TRUE -- because of michael@0: * the banding, the first time this is true we know the box is only michael@0: * partially in the region) or is outside the region (we reached a band michael@0: * that doesn't overlap the box at all and part_in is false) michael@0: */ michael@0: PIXMAN_EXPORT pixman_region_overlap_t michael@0: PREFIX (_contains_rectangle) (region_type_t * region, michael@0: box_type_t * prect) michael@0: { michael@0: box_type_t * pbox; michael@0: box_type_t * pbox_end; michael@0: int part_in, part_out; michael@0: int numRects; michael@0: int x, y; michael@0: michael@0: GOOD (region); michael@0: michael@0: numRects = PIXREGION_NUMRECTS (region); michael@0: michael@0: /* useful optimization */ michael@0: if (!numRects || !EXTENTCHECK (®ion->extents, prect)) michael@0: return(PIXMAN_REGION_OUT); michael@0: michael@0: if (numRects == 1) michael@0: { michael@0: /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */ michael@0: if (SUBSUMES (®ion->extents, prect)) michael@0: return(PIXMAN_REGION_IN); michael@0: else michael@0: return(PIXMAN_REGION_PART); michael@0: } michael@0: michael@0: part_out = FALSE; michael@0: part_in = FALSE; michael@0: michael@0: /* (x,y) starts at upper left of rect, moving to the right and down */ michael@0: x = prect->x1; michael@0: y = prect->y1; michael@0: michael@0: /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */ michael@0: for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects; michael@0: pbox != pbox_end; michael@0: pbox++) michael@0: { michael@0: /* getting up to speed or skipping remainder of band */ michael@0: if (pbox->y2 <= y) michael@0: { michael@0: if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end) michael@0: break; michael@0: } michael@0: michael@0: if (pbox->y1 > y) michael@0: { michael@0: part_out = TRUE; /* missed part of rectangle above */ michael@0: if (part_in || (pbox->y1 >= prect->y2)) michael@0: break; michael@0: y = pbox->y1; /* x guaranteed to be == prect->x1 */ michael@0: } michael@0: michael@0: if (pbox->x2 <= x) michael@0: continue; /* not far enough over yet */ michael@0: michael@0: if (pbox->x1 > x) michael@0: { michael@0: part_out = TRUE; /* missed part of rectangle to left */ michael@0: if (part_in) michael@0: break; michael@0: } michael@0: michael@0: if (pbox->x1 < prect->x2) michael@0: { michael@0: part_in = TRUE; /* definitely overlap */ michael@0: if (part_out) michael@0: break; michael@0: } michael@0: michael@0: if (pbox->x2 >= prect->x2) michael@0: { michael@0: y = pbox->y2; /* finished with this band */ michael@0: if (y >= prect->y2) michael@0: break; michael@0: x = prect->x1; /* reset x out to left again */ michael@0: } michael@0: else michael@0: { michael@0: /* michael@0: * Because boxes in a band are maximal width, if the first box michael@0: * to overlap the rectangle doesn't completely cover it in that michael@0: * band, the rectangle must be partially out, since some of it michael@0: * will be uncovered in that band. part_in will have been set true michael@0: * by now... michael@0: */ michael@0: part_out = TRUE; michael@0: break; michael@0: } michael@0: } michael@0: michael@0: if (part_in) michael@0: { michael@0: if (y < prect->y2) michael@0: return PIXMAN_REGION_PART; michael@0: else michael@0: return PIXMAN_REGION_IN; michael@0: } michael@0: else michael@0: { michael@0: return PIXMAN_REGION_OUT; michael@0: } michael@0: } michael@0: michael@0: /* PREFIX(_translate) (region, x, y) michael@0: * translates in place michael@0: */ michael@0: michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_translate) (region_type_t *region, int x, int y) michael@0: { michael@0: overflow_int_t x1, x2, y1, y2; michael@0: int nbox; michael@0: box_type_t * pbox; michael@0: michael@0: GOOD (region); michael@0: region->extents.x1 = x1 = region->extents.x1 + x; michael@0: region->extents.y1 = y1 = region->extents.y1 + y; michael@0: region->extents.x2 = x2 = region->extents.x2 + x; michael@0: region->extents.y2 = y2 = region->extents.y2 + y; michael@0: michael@0: if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0) michael@0: { michael@0: if (region->data && (nbox = region->data->numRects)) michael@0: { michael@0: for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++) michael@0: { michael@0: pbox->x1 += x; michael@0: pbox->y1 += y; michael@0: pbox->x2 += x; michael@0: pbox->y2 += y; michael@0: } michael@0: } michael@0: return; michael@0: } michael@0: michael@0: if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0) michael@0: { michael@0: region->extents.x2 = region->extents.x1; michael@0: region->extents.y2 = region->extents.y1; michael@0: FREE_DATA (region); michael@0: region->data = pixman_region_empty_data; michael@0: return; michael@0: } michael@0: michael@0: if (x1 < PIXMAN_REGION_MIN) michael@0: region->extents.x1 = PIXMAN_REGION_MIN; michael@0: else if (x2 > PIXMAN_REGION_MAX) michael@0: region->extents.x2 = PIXMAN_REGION_MAX; michael@0: michael@0: if (y1 < PIXMAN_REGION_MIN) michael@0: region->extents.y1 = PIXMAN_REGION_MIN; michael@0: else if (y2 > PIXMAN_REGION_MAX) michael@0: region->extents.y2 = PIXMAN_REGION_MAX; michael@0: michael@0: if (region->data && (nbox = region->data->numRects)) michael@0: { michael@0: box_type_t * pbox_out; michael@0: michael@0: for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++) michael@0: { michael@0: pbox_out->x1 = x1 = pbox->x1 + x; michael@0: pbox_out->y1 = y1 = pbox->y1 + y; michael@0: pbox_out->x2 = x2 = pbox->x2 + x; michael@0: pbox_out->y2 = y2 = pbox->y2 + y; michael@0: michael@0: if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | michael@0: (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0) michael@0: { michael@0: region->data->numRects--; michael@0: continue; michael@0: } michael@0: michael@0: if (x1 < PIXMAN_REGION_MIN) michael@0: pbox_out->x1 = PIXMAN_REGION_MIN; michael@0: else if (x2 > PIXMAN_REGION_MAX) michael@0: pbox_out->x2 = PIXMAN_REGION_MAX; michael@0: michael@0: if (y1 < PIXMAN_REGION_MIN) michael@0: pbox_out->y1 = PIXMAN_REGION_MIN; michael@0: else if (y2 > PIXMAN_REGION_MAX) michael@0: pbox_out->y2 = PIXMAN_REGION_MAX; michael@0: michael@0: pbox_out++; michael@0: } michael@0: michael@0: if (pbox_out != pbox) michael@0: { michael@0: if (region->data->numRects == 1) michael@0: { michael@0: region->extents = *PIXREGION_BOXPTR (region); michael@0: FREE_DATA (region); michael@0: region->data = (region_data_type_t *)NULL; michael@0: } michael@0: else michael@0: { michael@0: pixman_set_extents (region); michael@0: } michael@0: } michael@0: } michael@0: michael@0: GOOD (region); michael@0: } michael@0: michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_reset) (region_type_t *region, box_type_t *box) michael@0: { michael@0: GOOD (region); michael@0: michael@0: critical_if_fail (GOOD_RECT (box)); michael@0: michael@0: region->extents = *box; michael@0: michael@0: FREE_DATA (region); michael@0: michael@0: region->data = NULL; michael@0: } michael@0: michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_clear) (region_type_t *region) michael@0: { michael@0: GOOD (region); michael@0: FREE_DATA (region); michael@0: michael@0: region->extents = *pixman_region_empty_box; michael@0: region->data = pixman_region_empty_data; michael@0: } michael@0: michael@0: /* box is "return" value */ michael@0: PIXMAN_EXPORT int michael@0: PREFIX (_contains_point) (region_type_t * region, michael@0: int x, int y, michael@0: box_type_t * box) michael@0: { michael@0: box_type_t *pbox, *pbox_end; michael@0: int numRects; michael@0: michael@0: GOOD (region); michael@0: numRects = PIXREGION_NUMRECTS (region); michael@0: michael@0: if (!numRects || !INBOX (®ion->extents, x, y)) michael@0: return(FALSE); michael@0: michael@0: if (numRects == 1) michael@0: { michael@0: if (box) michael@0: *box = region->extents; michael@0: michael@0: return(TRUE); michael@0: } michael@0: michael@0: pbox = PIXREGION_BOXPTR (region); michael@0: pbox_end = pbox + numRects; michael@0: michael@0: pbox = find_box_for_y (pbox, pbox_end, y); michael@0: michael@0: for (;pbox != pbox_end; pbox++) michael@0: { michael@0: if ((y < pbox->y1) || (x < pbox->x1)) michael@0: break; /* missed it */ michael@0: michael@0: if (x >= pbox->x2) michael@0: continue; /* not there yet */ michael@0: michael@0: if (box) michael@0: *box = *pbox; michael@0: michael@0: return(TRUE); michael@0: } michael@0: michael@0: return(FALSE); michael@0: } michael@0: michael@0: PIXMAN_EXPORT int michael@0: PREFIX (_not_empty) (region_type_t * region) michael@0: { michael@0: GOOD (region); michael@0: michael@0: return(!PIXREGION_NIL (region)); michael@0: } michael@0: michael@0: PIXMAN_EXPORT box_type_t * michael@0: PREFIX (_extents) (region_type_t * region) michael@0: { michael@0: GOOD (region); michael@0: michael@0: return(®ion->extents); michael@0: } michael@0: michael@0: /* michael@0: * Clip a list of scanlines to a region. The caller has allocated the michael@0: * space. FSorted is non-zero if the scanline origins are in ascending order. michael@0: * michael@0: * returns the number of new, clipped scanlines. michael@0: */ michael@0: michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_selfcheck) (region_type_t *reg) michael@0: { michael@0: int i, numRects; michael@0: michael@0: if ((reg->extents.x1 > reg->extents.x2) || michael@0: (reg->extents.y1 > reg->extents.y2)) michael@0: { michael@0: return FALSE; michael@0: } michael@0: michael@0: numRects = PIXREGION_NUMRECTS (reg); michael@0: if (!numRects) michael@0: { michael@0: return ((reg->extents.x1 == reg->extents.x2) && michael@0: (reg->extents.y1 == reg->extents.y2) && michael@0: (reg->data->size || (reg->data == pixman_region_empty_data))); michael@0: } michael@0: else if (numRects == 1) michael@0: { michael@0: return (!reg->data); michael@0: } michael@0: else michael@0: { michael@0: box_type_t * pbox_p, * pbox_n; michael@0: box_type_t box; michael@0: michael@0: pbox_p = PIXREGION_RECTS (reg); michael@0: box = *pbox_p; michael@0: box.y2 = pbox_p[numRects - 1].y2; michael@0: pbox_n = pbox_p + 1; michael@0: michael@0: for (i = numRects; --i > 0; pbox_p++, pbox_n++) michael@0: { michael@0: if ((pbox_n->x1 >= pbox_n->x2) || michael@0: (pbox_n->y1 >= pbox_n->y2)) michael@0: { michael@0: return FALSE; michael@0: } michael@0: michael@0: if (pbox_n->x1 < box.x1) michael@0: box.x1 = pbox_n->x1; michael@0: michael@0: if (pbox_n->x2 > box.x2) michael@0: box.x2 = pbox_n->x2; michael@0: michael@0: if ((pbox_n->y1 < pbox_p->y1) || michael@0: ((pbox_n->y1 == pbox_p->y1) && michael@0: ((pbox_n->x1 < pbox_p->x2) || (pbox_n->y2 != pbox_p->y2)))) michael@0: { michael@0: return FALSE; michael@0: } michael@0: } michael@0: michael@0: return ((box.x1 == reg->extents.x1) && michael@0: (box.x2 == reg->extents.x2) && michael@0: (box.y1 == reg->extents.y1) && michael@0: (box.y2 == reg->extents.y2)); michael@0: } michael@0: } michael@0: michael@0: PIXMAN_EXPORT pixman_bool_t michael@0: PREFIX (_init_rects) (region_type_t *region, michael@0: const box_type_t *boxes, int count) michael@0: { michael@0: box_type_t *rects; michael@0: int displacement; michael@0: int i; michael@0: michael@0: /* if it's 1, then we just want to set the extents, so call michael@0: * the existing method. */ michael@0: if (count == 1) michael@0: { michael@0: PREFIX (_init_rect) (region, michael@0: boxes[0].x1, michael@0: boxes[0].y1, michael@0: boxes[0].x2 - boxes[0].x1, michael@0: boxes[0].y2 - boxes[0].y1); michael@0: return TRUE; michael@0: } michael@0: michael@0: PREFIX (_init) (region); michael@0: michael@0: /* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is michael@0: * a special case, and causing pixman_rect_alloc would cause michael@0: * us to leak memory (because the 0-rect case should be the michael@0: * static pixman_region_empty_data data). michael@0: */ michael@0: if (count == 0) michael@0: return TRUE; michael@0: michael@0: if (!pixman_rect_alloc (region, count)) michael@0: return FALSE; michael@0: michael@0: rects = PIXREGION_RECTS (region); michael@0: michael@0: /* Copy in the rects */ michael@0: memcpy (rects, boxes, sizeof(box_type_t) * count); michael@0: region->data->numRects = count; michael@0: michael@0: /* Eliminate empty and malformed rectangles */ michael@0: displacement = 0; michael@0: michael@0: for (i = 0; i < count; ++i) michael@0: { michael@0: box_type_t *box = &rects[i]; michael@0: michael@0: if (box->x1 >= box->x2 || box->y1 >= box->y2) michael@0: displacement++; michael@0: else if (displacement) michael@0: rects[i - displacement] = rects[i]; michael@0: } michael@0: michael@0: region->data->numRects -= displacement; michael@0: michael@0: /* If eliminating empty rectangles caused there michael@0: * to be only 0 or 1 rectangles, deal with that. michael@0: */ michael@0: if (region->data->numRects == 0) michael@0: { michael@0: FREE_DATA (region); michael@0: PREFIX (_init) (region); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: if (region->data->numRects == 1) michael@0: { michael@0: region->extents = rects[0]; michael@0: michael@0: FREE_DATA (region); michael@0: region->data = NULL; michael@0: michael@0: GOOD (region); michael@0: michael@0: return TRUE; michael@0: } michael@0: michael@0: /* Validate */ michael@0: region->extents.x1 = region->extents.x2 = 0; michael@0: michael@0: return validate (region); michael@0: } michael@0: michael@0: #define READ(_ptr) (*(_ptr)) michael@0: michael@0: static inline box_type_t * michael@0: bitmap_addrect (region_type_t *reg, michael@0: box_type_t *r, michael@0: box_type_t **first_rect, michael@0: int rx1, int ry1, michael@0: int rx2, int ry2) michael@0: { michael@0: if ((rx1 < rx2) && (ry1 < ry2) && michael@0: (!(reg->data->numRects && michael@0: ((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) && michael@0: ((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2)))) michael@0: { michael@0: if (reg->data->numRects == reg->data->size) michael@0: { michael@0: if (!pixman_rect_alloc (reg, 1)) michael@0: return NULL; michael@0: *first_rect = PIXREGION_BOXPTR(reg); michael@0: r = *first_rect + reg->data->numRects; michael@0: } michael@0: r->x1 = rx1; michael@0: r->y1 = ry1; michael@0: r->x2 = rx2; michael@0: r->y2 = ry2; michael@0: reg->data->numRects++; michael@0: if (r->x1 < reg->extents.x1) michael@0: reg->extents.x1 = r->x1; michael@0: if (r->x2 > reg->extents.x2) michael@0: reg->extents.x2 = r->x2; michael@0: r++; michael@0: } michael@0: return r; michael@0: } michael@0: michael@0: /* Convert bitmap clip mask into clipping region. michael@0: * First, goes through each line and makes boxes by noting the transitions michael@0: * from 0 to 1 and 1 to 0. michael@0: * Then it coalesces the current line with the previous if they have boxes michael@0: * at the same X coordinates. michael@0: * Stride is in number of uint32_t per line. michael@0: */ michael@0: PIXMAN_EXPORT void michael@0: PREFIX (_init_from_image) (region_type_t *region, michael@0: pixman_image_t *image) michael@0: { michael@0: uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1); michael@0: box_type_t *first_rect, *rects, *prect_line_start; michael@0: box_type_t *old_rect, *new_rect; michael@0: uint32_t *pw, w, *pw_line, *pw_line_end; michael@0: int irect_prev_start, irect_line_start; michael@0: int h, base, rx1 = 0, crects; michael@0: int ib; michael@0: pixman_bool_t in_box, same; michael@0: int width, height, stride; michael@0: michael@0: PREFIX(_init) (region); michael@0: michael@0: critical_if_fail (region->data); michael@0: michael@0: return_if_fail (image->type == BITS); michael@0: return_if_fail (image->bits.format == PIXMAN_a1); michael@0: michael@0: pw_line = pixman_image_get_data (image); michael@0: width = pixman_image_get_width (image); michael@0: height = pixman_image_get_height (image); michael@0: stride = pixman_image_get_stride (image) / 4; michael@0: michael@0: first_rect = PIXREGION_BOXPTR(region); michael@0: rects = first_rect; michael@0: michael@0: region->extents.x1 = width - 1; michael@0: region->extents.x2 = 0; michael@0: irect_prev_start = -1; michael@0: for (h = 0; h < height; h++) michael@0: { michael@0: pw = pw_line; michael@0: pw_line += stride; michael@0: irect_line_start = rects - first_rect; michael@0: michael@0: /* If the Screen left most bit of the word is set, we're starting in michael@0: * a box */ michael@0: if (READ(pw) & mask0) michael@0: { michael@0: in_box = TRUE; michael@0: rx1 = 0; michael@0: } michael@0: else michael@0: { michael@0: in_box = FALSE; michael@0: } michael@0: michael@0: /* Process all words which are fully in the pixmap */ michael@0: pw_line_end = pw + (width >> 5); michael@0: for (base = 0; pw < pw_line_end; base += 32) michael@0: { michael@0: w = READ(pw++); michael@0: if (in_box) michael@0: { michael@0: if (!~w) michael@0: continue; michael@0: } michael@0: else michael@0: { michael@0: if (!w) michael@0: continue; michael@0: } michael@0: for (ib = 0; ib < 32; ib++) michael@0: { michael@0: /* If the Screen left most bit of the word is set, we're michael@0: * starting a box */ michael@0: if (w & mask0) michael@0: { michael@0: if (!in_box) michael@0: { michael@0: rx1 = base + ib; michael@0: /* start new box */ michael@0: in_box = TRUE; michael@0: } michael@0: } michael@0: else michael@0: { michael@0: if (in_box) michael@0: { michael@0: /* end box */ michael@0: rects = bitmap_addrect (region, rects, &first_rect, michael@0: rx1, h, base + ib, h + 1); michael@0: if (rects == NULL) michael@0: goto error; michael@0: in_box = FALSE; michael@0: } michael@0: } michael@0: /* Shift the word VISUALLY left one. */ michael@0: w = SCREEN_SHIFT_LEFT(w, 1); michael@0: } michael@0: } michael@0: michael@0: if (width & 31) michael@0: { michael@0: /* Process final partial word on line */ michael@0: w = READ(pw++); michael@0: for (ib = 0; ib < (width & 31); ib++) michael@0: { michael@0: /* If the Screen left most bit of the word is set, we're michael@0: * starting a box */ michael@0: if (w & mask0) michael@0: { michael@0: if (!in_box) michael@0: { michael@0: rx1 = base + ib; michael@0: /* start new box */ michael@0: in_box = TRUE; michael@0: } michael@0: } michael@0: else michael@0: { michael@0: if (in_box) michael@0: { michael@0: /* end box */ michael@0: rects = bitmap_addrect(region, rects, &first_rect, michael@0: rx1, h, base + ib, h + 1); michael@0: if (rects == NULL) michael@0: goto error; michael@0: in_box = FALSE; michael@0: } michael@0: } michael@0: /* Shift the word VISUALLY left one. */ michael@0: w = SCREEN_SHIFT_LEFT(w, 1); michael@0: } michael@0: } michael@0: /* If scanline ended with last bit set, end the box */ michael@0: if (in_box) michael@0: { michael@0: rects = bitmap_addrect(region, rects, &first_rect, michael@0: rx1, h, base + (width & 31), h + 1); michael@0: if (rects == NULL) michael@0: goto error; michael@0: } michael@0: /* if all rectangles on this line have the same x-coords as michael@0: * those on the previous line, then add 1 to all the previous y2s and michael@0: * throw away all the rectangles from this line michael@0: */ michael@0: same = FALSE; michael@0: if (irect_prev_start != -1) michael@0: { michael@0: crects = irect_line_start - irect_prev_start; michael@0: if (crects != 0 && michael@0: crects == ((rects - first_rect) - irect_line_start)) michael@0: { michael@0: old_rect = first_rect + irect_prev_start; michael@0: new_rect = prect_line_start = first_rect + irect_line_start; michael@0: same = TRUE; michael@0: while (old_rect < prect_line_start) michael@0: { michael@0: if ((old_rect->x1 != new_rect->x1) || michael@0: (old_rect->x2 != new_rect->x2)) michael@0: { michael@0: same = FALSE; michael@0: break; michael@0: } michael@0: old_rect++; michael@0: new_rect++; michael@0: } michael@0: if (same) michael@0: { michael@0: old_rect = first_rect + irect_prev_start; michael@0: while (old_rect < prect_line_start) michael@0: { michael@0: old_rect->y2 += 1; michael@0: old_rect++; michael@0: } michael@0: rects -= crects; michael@0: region->data->numRects -= crects; michael@0: } michael@0: } michael@0: } michael@0: if(!same) michael@0: irect_prev_start = irect_line_start; michael@0: } michael@0: if (!region->data->numRects) michael@0: { michael@0: region->extents.x1 = region->extents.x2 = 0; michael@0: } michael@0: else michael@0: { michael@0: region->extents.y1 = PIXREGION_BOXPTR(region)->y1; michael@0: region->extents.y2 = PIXREGION_END(region)->y2; michael@0: if (region->data->numRects == 1) michael@0: { michael@0: free (region->data); michael@0: region->data = NULL; michael@0: } michael@0: } michael@0: michael@0: error: michael@0: return; michael@0: }