WebSVN – Kolibri OS – Blame – /programs/develop/libraries/pixman/pixman-region.c

Rev	Author	Line No.	Line
1891	serge	1	/*
		2	* Copyright 1987, 1988, 1989, 1998 The Open Group
		3	*
		4	* Permission to use, copy, modify, distribute, and sell this software and its
		5	* documentation for any purpose is hereby granted without fee, provided that
		6	* the above copyright notice appear in all copies and that both that
		7	* copyright notice and this permission notice appear in supporting
		8	* documentation.
		9	*
		10	* The above copyright notice and this permission notice shall be included in
		11	* all copies or substantial portions of the Software.
		12	*
		13	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
		14	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
		15	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
		16	* OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
		17	* AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
		18	* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
		19	*
		20	* Except as contained in this notice, the name of The Open Group shall not be
		21	* used in advertising or otherwise to promote the sale, use or other dealings
		22	* in this Software without prior written authorization from The Open Group.
		23	*
		24	* Copyright 1987, 1988, 1989 by
		25	* Digital Equipment Corporation, Maynard, Massachusetts.
		26	*
		27	* All Rights Reserved
		28	*
		29	* Permission to use, copy, modify, and distribute this software and its
		30	* documentation for any purpose and without fee is hereby granted,
		31	* provided that the above copyright notice appear in all copies and that
		32	* both that copyright notice and this permission notice appear in
		33	* supporting documentation, and that the name of Digital not be
		34	* used in advertising or publicity pertaining to distribution of the
		35	* software without specific, written prior permission.
		36	*
		37	* DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
		38	* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
		39	* DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
		40	* ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
		41	* WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
		42	* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
		43	* SOFTWARE.
		44	*
		45	* Copyright © 1998 Keith Packard
		46	*
		47	* Permission to use, copy, modify, distribute, and sell this software and its
		48	* documentation for any purpose is hereby granted without fee, provided that
		49	* the above copyright notice appear in all copies and that both that
		50	* copyright notice and this permission notice appear in supporting
		51	* documentation, and that the name of Keith Packard not be used in
		52	* advertising or publicity pertaining to distribution of the software without
		53	* specific, written prior permission. Keith Packard makes no
		54	* representations about the suitability of this software for any purpose. It
		55	* is provided "as is" without express or implied warranty.
		56	*
		57	* KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
		58	* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
		59	* EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
		60	* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
		61	* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
		62	* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
		63	* PERFORMANCE OF THIS SOFTWARE.
		64	*/
		65
		66	#include
		67	#include
		68	#include
		69	#include
		70	#include "pixman-private.h"
		71
		72	#define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
		73	/* not a region */
		74	#define PIXREGION_NAR(reg) ((reg)->data == pixman_broken_data)
		75	#define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
		76	#define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
		77	#define PIXREGION_RECTS(reg) \
		78	((reg)->data ? (box_type_t *)((reg)->data + 1) \
		79	: &(reg)->extents)
		80	#define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))
		81	#define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])
		82	#define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)
		83	#define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)
		84
		85	#define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)
		86	#define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 \|\| (rect)->y1 > (rect)->y2)
		87
		88	#ifdef DEBUG
		89
		90	#define GOOD(reg) \
		91	do \
		92	{ \
		93	if (!PREFIX (_selfcheck (reg))) \
		94	_pixman_log_error (FUNC, "Malformed region " # reg); \
		95	} while (0)
		96
		97	#else
		98
		99	#define GOOD(reg)
		100
		101	#endif
		102
		103	static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };
		104	static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };
		105	static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
		106
		107	static box_type_t *pixman_region_empty_box =
		108	(box_type_t *)&PREFIX (_empty_box_);
		109	static region_data_type_t *pixman_region_empty_data =
		110	(region_data_type_t *)&PREFIX (_empty_data_);
		111	static region_data_type_t *pixman_broken_data =
		112	(region_data_type_t *)&PREFIX (_broken_data_);
		113
		114	static pixman_bool_t
		115	pixman_break (region_type_t *region);
		116
		117	/*
		118	* The functions in this file implement the Region abstraction used extensively
		119	* throughout the X11 sample server. A Region is simply a set of disjoint
		120	* (non-overlapping) rectangles, plus an "extent" rectangle which is the
		121	* smallest single rectangle that contains all the non-overlapping rectangles.
		122	*
		123	* A Region is implemented as a "y-x-banded" array of rectangles. This array
		124	* imposes two degrees of order. First, all rectangles are sorted by top side
		125	* y coordinate first (y1), and then by left side x coordinate (x1).
		126	*
		127	* Furthermore, the rectangles are grouped into "bands". Each rectangle in a
		128	* band has the same top y coordinate (y1), and each has the same bottom y
		129	* coordinate (y2). Thus all rectangles in a band differ only in their left
		130	* and right side (x1 and x2). Bands are implicit in the array of rectangles:
		131	* there is no separate list of band start pointers.
		132	*
		133	* The y-x band representation does not minimize rectangles. In particular,
		134	* if a rectangle vertically crosses a band (the rectangle has scanlines in
		135	* the y1 to y2 area spanned by the band), then the rectangle may be broken
		136	* down into two or more smaller rectangles stacked one atop the other.
		137	*
		138	* ----------- -----------
		139	* \| \| \| \| band 0
		140	* \| \| -------- ----------- --------
		141	* \| \| \| \| in y-x banded \| \| \| \| band 1
		142	* \| \| \| \| form is \| \| \| \|
		143	* ----------- \| \| ----------- --------
		144	* \| \| \| \| band 2
		145	* -------- --------
		146	*
		147	* An added constraint on the rectangles is that they must cover as much
		148	* horizontal area as possible: no two rectangles within a band are allowed
		149	* to touch.
		150	*
		151	* Whenever possible, bands will be merged together to cover a greater vertical
		152	* distance (and thus reduce the number of rectangles). Two bands can be merged
		153	* only if the bottom of one touches the top of the other and they have
		154	* rectangles in the same places (of the same width, of course).
		155	*
		156	* Adam de Boor wrote most of the original region code. Joel McCormack
		157	* substantially modified or rewrote most of the core arithmetic routines, and
		158	* added pixman_region_validate in order to support several speed improvements
		159	* to pixman_region_validate_tree. Bob Scheifler changed the representation
		160	* to be more compact when empty or a single rectangle, and did a bunch of
		161	* gratuitous reformatting. Carl Worth did further gratuitous reformatting
		162	* while re-merging the server and client region code into libpixregion.
		163	* Soren Sandmann did even more gratuitous reformatting.
		164	*/
		165
		166	/* true iff two Boxes overlap */
		167	#define EXTENTCHECK(r1, r2) \
		168	(!( ((r1)->x2 <= (r2)->x1) \|\| \
		169	((r1)->x1 >= (r2)->x2) \|\| \
		170	((r1)->y2 <= (r2)->y1) \|\| \
		171	((r1)->y1 >= (r2)->y2) ) )
		172
		173	/* true iff (x,y) is in Box */
		174	#define INBOX(r, x, y) \
		175	( ((r)->x2 > x) && \
		176	((r)->x1 <= x) && \
		177	((r)->y2 > y) && \
		178	((r)->y1 <= y) )
		179
		180	/* true iff Box r1 contains Box r2 */
		181	#define SUBSUMES(r1, r2) \
		182	( ((r1)->x1 <= (r2)->x1) && \
		183	((r1)->x2 >= (r2)->x2) && \
		184	((r1)->y1 <= (r2)->y1) && \
		185	((r1)->y2 >= (r2)->y2) )
		186
		187	static size_t
		188	PIXREGION_SZOF (size_t n)
		189	{
		190	size_t size = n * sizeof(box_type_t);
		191
		192	if (n > UINT32_MAX / sizeof(box_type_t))
		193	return 0;
		194
		195	if (sizeof(region_data_type_t) > UINT32_MAX - size)
		196	return 0;
		197
		198	return size + sizeof(region_data_type_t);
		199	}
		200
		201	static void *
		202	alloc_data (size_t n)
		203	{
		204	size_t sz = PIXREGION_SZOF (n);
		205
		206	if (!sz)
		207	return NULL;
		208
		209	return malloc (sz);
		210	}
		211
		212	#define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)
		213
		214	#define RECTALLOC_BAIL(region, n, bail) \
		215	do \
		216	{ \
		217	if (!(region)->data \|\| \
		218	(((region)->data->numRects + (n)) > (region)->data->size)) \
		219	{ \
		220	if (!pixman_rect_alloc (region, n)) \
		221	goto bail; \
		222	} \
		223	} while (0)
		224
		225	#define RECTALLOC(region, n) \
		226	do \
		227	{ \
		228	if (!(region)->data \|\| \
		229	(((region)->data->numRects + (n)) > (region)->data->size)) \
		230	{ \
		231	if (!pixman_rect_alloc (region, n)) { \
		232	return FALSE; \
		233	} \
		234	} \
		235	} while (0)
		236
		237	#define ADDRECT(next_rect, nx1, ny1, nx2, ny2) \
		238	do \
		239	{ \
		240	next_rect->x1 = nx1; \
		241	next_rect->y1 = ny1; \
		242	next_rect->x2 = nx2; \
		243	next_rect->y2 = ny2; \
		244	next_rect++; \
		245	} \
		246	while (0)
		247
		248	#define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2) \
		249	do \
		250	{ \
		251	if (!(region)->data \|\| \
		252	((region)->data->numRects == (region)->data->size)) \
		253	{ \
		254	if (!pixman_rect_alloc (region, 1)) \
		255	return FALSE; \
		256	next_rect = PIXREGION_TOP (region); \
		257	} \
		258	ADDRECT (next_rect, nx1, ny1, nx2, ny2); \
		259	region->data->numRects++; \
		260	critical_if_fail (region->data->numRects <= region->data->size); \
		261	} while (0)
		262
		263	#define DOWNSIZE(reg, numRects) \
		264	do \
		265	{ \
		266	if (((numRects) < ((reg)->data->size >> 1)) && \
		267	((reg)->data->size > 50)) \
		268	{ \
		269	region_data_type_t * new_data; \
		270	size_t data_size = PIXREGION_SZOF (numRects); \
		271	\
		272	if (!data_size) \
		273	{ \
		274	new_data = NULL; \
		275	} \
		276	else \
		277	{ \
		278	new_data = (region_data_type_t *) \
		279	realloc ((reg)->data, data_size); \
		280	} \
		281	\
		282	if (new_data) \
		283	{ \
		284	new_data->size = (numRects); \
		285	(reg)->data = new_data; \
		286	} \
		287	} \
		288	} while (0)
		289
		290	PIXMAN_EXPORT pixman_bool_t
		291	PREFIX (_equal) (region_type_t reg1, region_type_t reg2)
		292	{
		293	int i;
		294	box_type_t *rects1;
		295	box_type_t *rects2;
		296
		297	if (reg1->extents.x1 != reg2->extents.x1)
		298	return FALSE;
		299
		300	if (reg1->extents.x2 != reg2->extents.x2)
		301	return FALSE;
		302
		303	if (reg1->extents.y1 != reg2->extents.y1)
		304	return FALSE;
		305
		306	if (reg1->extents.y2 != reg2->extents.y2)
		307	return FALSE;
		308
		309	if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2))
		310	return FALSE;
		311
		312	rects1 = PIXREGION_RECTS (reg1);
		313	rects2 = PIXREGION_RECTS (reg2);
		314
		315	for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++)
		316	{
		317	if (rects1[i].x1 != rects2[i].x1)
		318	return FALSE;
		319
		320	if (rects1[i].x2 != rects2[i].x2)
		321	return FALSE;
		322
		323	if (rects1[i].y1 != rects2[i].y1)
		324	return FALSE;
		325
		326	if (rects1[i].y2 != rects2[i].y2)
		327	return FALSE;
		328	}
		329
		330	return TRUE;
		331	}
		332
		333	int
		334	PREFIX (_print) (region_type_t *rgn)
		335	{
		336	int num, size;
		337	int i;
		338	box_type_t * rects;
		339
		340	num = PIXREGION_NUMRECTS (rgn);
		341	size = PIXREGION_SIZE (rgn);
		342	rects = PIXREGION_RECTS (rgn);
		343
		344	fprintf (stderr, "num: %d size: %d\n", num, size);
		345	fprintf (stderr, "extents: %d %d %d %d\n",
		346	rgn->extents.x1,
		347	rgn->extents.y1,
		348	rgn->extents.x2,
		349	rgn->extents.y2);
		350
		351	for (i = 0; i < num; i++)
		352	{
		353	fprintf (stderr, "%d %d %d %d \n",
		354	rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
		355	}
		356
		357	fprintf (stderr, "\n");
		358
		359	return(num);
		360	}
		361
		362
		363	PIXMAN_EXPORT void
		364	PREFIX (_init) (region_type_t *region)
		365	{
		366	region->extents = *pixman_region_empty_box;
		367	region->data = pixman_region_empty_data;
		368	}
		369
		370	PIXMAN_EXPORT void
		371	PREFIX (_init_rect) (region_type_t * region,
		372	int x,
		373	int y,
		374	unsigned int width,
		375	unsigned int height)
		376	{
		377	region->extents.x1 = x;
		378	region->extents.y1 = y;
		379	region->extents.x2 = x + width;
		380	region->extents.y2 = y + height;
		381
		382	if (!GOOD_RECT (®ion->extents))
		383	{
		384	if (BAD_RECT (®ion->extents))
		385	_pixman_log_error (FUNC, "Invalid rectangle passed");
		386	PREFIX (_init) (region);
		387	return;
		388	}
		389
		390	region->data = NULL;
		391	}
		392
		393	PIXMAN_EXPORT void
		394	PREFIX (_init_with_extents) (region_type_t region, box_type_t extents)
		395	{
		396	if (!GOOD_RECT (extents))
		397	{
		398	if (BAD_RECT (extents))
		399	_pixman_log_error (FUNC, "Invalid rectangle passed");
		400	PREFIX (_init) (region);
		401	return;
		402	}
		403	region->extents = *extents;
		404
		405	region->data = NULL;
		406	}
		407
		408	PIXMAN_EXPORT void
		409	PREFIX (_fini) (region_type_t *region)
		410	{
		411	GOOD (region);
		412	FREE_DATA (region);
		413	}
		414
		415	PIXMAN_EXPORT int
		416	PREFIX (_n_rects) (region_type_t *region)
		417	{
		418	return PIXREGION_NUMRECTS (region);
		419	}
		420
		421	PIXMAN_EXPORT box_type_t *
		422	PREFIX (_rectangles) (region_type_t *region,
		423	int *n_rects)
		424	{
		425	if (n_rects)
		426	*n_rects = PIXREGION_NUMRECTS (region);
		427
		428	return PIXREGION_RECTS (region);
		429	}
		430
		431	static pixman_bool_t
		432	pixman_break (region_type_t *region)
		433	{
		434	FREE_DATA (region);
		435
		436	region->extents = *pixman_region_empty_box;
		437	region->data = pixman_broken_data;
		438
		439	return FALSE;
		440	}
		441
		442	static pixman_bool_t
		443	pixman_rect_alloc (region_type_t * region,
		444	int n)
		445	{
		446	region_data_type_t *data;
		447
		448	if (!region->data)
		449	{
		450	n++;
		451	region->data = alloc_data (n);
		452
		453	if (!region->data)
		454	return pixman_break (region);
		455
		456	region->data->numRects = 1;
		457	*PIXREGION_BOXPTR (region) = region->extents;
		458	}
		459	else if (!region->data->size)
		460	{
		461	region->data = alloc_data (n);
		462
		463	if (!region->data)
		464	return pixman_break (region);
		465
		466	region->data->numRects = 0;
		467	}
		468	else
		469	{
		470	size_t data_size;
		471
		472	if (n == 1)
		473	{
		474	n = region->data->numRects;
		475	if (n > 500) /* XXX pick numbers out of a hat */
		476	n = 250;
		477	}
		478
		479	n += region->data->numRects;
		480	data_size = PIXREGION_SZOF (n);
		481
		482	if (!data_size)
		483	{
		484	data = NULL;
		485	}
		486	else
		487	{
		488	data = (region_data_type_t *)
		489	realloc (region->data, PIXREGION_SZOF (n));
		490	}
		491
		492	if (!data)
		493	return pixman_break (region);
		494
		495	region->data = data;
		496	}
		497
		498	region->data->size = n;
		499
		500	return TRUE;
		501	}
		502
		503	PIXMAN_EXPORT pixman_bool_t
		504	PREFIX (_copy) (region_type_t dst, region_type_t src)
		505	{
		506	GOOD (dst);
		507	GOOD (src);
		508
		509	if (dst == src)
		510	return TRUE;
		511
		512	dst->extents = src->extents;
		513
		514	if (!src->data \|\| !src->data->size)
		515	{
		516	FREE_DATA (dst);
		517	dst->data = src->data;
		518	return TRUE;
		519	}
		520
		521	if (!dst->data \|\| (dst->data->size < src->data->numRects))
		522	{
		523	FREE_DATA (dst);
		524
		525	dst->data = alloc_data (src->data->numRects);
		526
		527	if (!dst->data)
		528	return pixman_break (dst);
		529
		530	dst->data->size = src->data->numRects;
		531	}
		532
		533	dst->data->numRects = src->data->numRects;
		534
		535	memmove ((char )PIXREGION_BOXPTR (dst), (char )PIXREGION_BOXPTR (src),
		536	dst->data->numRects * sizeof(box_type_t));
		537
		538	return TRUE;
		539	}
		540
		541	/*======================================================================
		542	* Generic Region Operator
		543	====================================================================/
		544
		545	/*-
		546	*-----------------------------------------------------------------------
		547	* pixman_coalesce --
		548	* Attempt to merge the boxes in the current band with those in the
		549	* previous one. We are guaranteed that the current band extends to
		550	* the end of the rects array. Used only by pixman_op.
		551	*
		552	* Results:
		553	* The new index for the previous band.
		554	*
		555	* Side Effects:
		556	* If coalescing takes place:
		557	* - rectangles in the previous band will have their y2 fields
		558	* altered.
		559	* - region->data->numRects will be decreased.
		560	*
		561	*-----------------------------------------------------------------------
		562	*/
		563	static inline int
		564	pixman_coalesce (region_type_t * region, /* Region to coalesce */
		565	int prev_start, /* Index of start of previous band */
		566	int cur_start) /* Index of start of current band */
		567	{
		568	box_type_t prev_box; / Current box in previous band */
		569	box_type_t cur_box; / Current box in current band */
		570	int numRects; /* Number rectangles in both bands */
		571	int y2; /* Bottom of current band */
		572
		573	/*
		574	* Figure out how many rectangles are in the band.
		575	*/
		576	numRects = cur_start - prev_start;
		577	critical_if_fail (numRects == region->data->numRects - cur_start);
		578
		579	if (!numRects) return cur_start;
		580
		581	/*
		582	* The bands may only be coalesced if the bottom of the previous
		583	* matches the top scanline of the current.
		584	*/
		585	prev_box = PIXREGION_BOX (region, prev_start);
		586	cur_box = PIXREGION_BOX (region, cur_start);
		587	if (prev_box->y2 != cur_box->y1) return cur_start;
		588
		589	/*
		590	* Make sure the bands have boxes in the same places. This
		591	* assumes that boxes have been added in such a way that they
		592	* cover the most area possible. I.e. two boxes in a band must
		593	* have some horizontal space between them.
		594	*/
		595	y2 = cur_box->y2;
		596
		597	do
		598	{
		599	if ((prev_box->x1 != cur_box->x1) \|\| (prev_box->x2 != cur_box->x2))
		600	return (cur_start);
		601
		602	prev_box++;
		603	cur_box++;
		604	numRects--;
		605	}
		606	while (numRects);
		607
		608	/*
		609	* The bands may be merged, so set the bottom y of each box
		610	* in the previous band to the bottom y of the current band.
		611	*/
		612	numRects = cur_start - prev_start;
		613	region->data->numRects -= numRects;
		614
		615	do
		616	{
		617	prev_box--;
		618	prev_box->y2 = y2;
		619	numRects--;
		620	}
		621	while (numRects);
		622
		623	return prev_start;
		624	}
		625
		626	/* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
		627
		628	#define COALESCE(new_reg, prev_band, cur_band) \
		629	do \
		630	{ \
		631	if (cur_band - prev_band == new_reg->data->numRects - cur_band) \
		632	prev_band = pixman_coalesce (new_reg, prev_band, cur_band); \
		633	else \
		634	prev_band = cur_band; \
		635	} while (0)
		636
		637	/*-
		638	*-----------------------------------------------------------------------
		639	* pixman_region_append_non_o --
		640	* Handle a non-overlapping band for the union and subtract operations.
		641	* Just adds the (top/bottom-clipped) rectangles into the region.
		642	* Doesn't have to check for subsumption or anything.
		643	*
		644	* Results:
		645	* None.
		646	*
		647	* Side Effects:
		648	* region->data->numRects is incremented and the rectangles overwritten
		649	* with the rectangles we're passed.
		650	*
		651	*-----------------------------------------------------------------------
		652	*/
		653	static inline pixman_bool_t
		654	pixman_region_append_non_o (region_type_t * region,
		655	box_type_t * r,
		656	box_type_t * r_end,
		657	int y1,
		658	int y2)
		659	{
		660	box_type_t *next_rect;
		661	int new_rects;
		662
		663	new_rects = r_end - r;
		664
		665	critical_if_fail (y1 < y2);
		666	critical_if_fail (new_rects != 0);
		667
		668	/* Make sure we have enough space for all rectangles to be added */
		669	RECTALLOC (region, new_rects);
		670	next_rect = PIXREGION_TOP (region);
		671	region->data->numRects += new_rects;
		672
		673	do
		674	{
		675	critical_if_fail (r->x1 < r->x2);
		676	ADDRECT (next_rect, r->x1, y1, r->x2, y2);
		677	r++;
		678	}
		679	while (r != r_end);
		680
		681	return TRUE;
		682	}
		683
		684	#define FIND_BAND(r, r_band_end, r_end, ry1) \
		685	do \
		686	{ \
		687	ry1 = r->y1; \
		688	r_band_end = r + 1; \
		689	while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) { \
		690	r_band_end++; \
		691	} \
		692	} while (0)
		693
		694	#define APPEND_REGIONS(new_reg, r, r_end) \
		695	do \
		696	{ \
		697	int new_rects; \
		698	if ((new_rects = r_end - r)) { \
		699	RECTALLOC_BAIL (new_reg, new_rects, bail); \
		700	memmove ((char )PIXREGION_TOP (new_reg), (char )r, \
		701	new_rects * sizeof(box_type_t)); \
		702	new_reg->data->numRects += new_rects; \
		703	} \
		704	} while (0)
		705
		706	/*-
		707	*-----------------------------------------------------------------------
		708	* pixman_op --
		709	* Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
		710	* pixman_region_subtract, pixman_region_intersect.... Both regions MUST have at least one
		711	* rectangle, and cannot be the same object.
		712	*
		713	* Results:
		714	* TRUE if successful.
		715	*
		716	* Side Effects:
		717	* The new region is overwritten.
		718	* overlap set to TRUE if overlap_func ever returns TRUE.
		719	*
		720	* Notes:
		721	* The idea behind this function is to view the two regions as sets.
		722	* Together they cover a rectangle of area that this function divides
		723	* into horizontal bands where points are covered only by one region
		724	* or by both. For the first case, the non_overlap_func is called with
		725	* each the band and the band's upper and lower extents. For the
		726	* second, the overlap_func is called to process the entire band. It
		727	* is responsible for clipping the rectangles in the band, though
		728	* this function provides the boundaries.
		729	* At the end of each band, the new region is coalesced, if possible,
		730	* to reduce the number of rectangles in the region.
		731	*
		732	*-----------------------------------------------------------------------
		733	*/
		734
		735	typedef pixman_bool_t (overlap_proc_ptr) (region_type_t region,
		736	box_type_t * r1,
		737	box_type_t * r1_end,
		738	box_type_t * r2,
		739	box_type_t * r2_end,
		740	int y1,
		741	int y2,
		742	int * overlap);
		743
		744	static pixman_bool_t
		745	pixman_op (region_type_t * new_reg, /* Place to store result */
		746	region_type_t * reg1, /* First region in operation */
		747	region_type_t * reg2, /* 2d region in operation */
		748	overlap_proc_ptr overlap_func, /* Function to call for over-
		749	* lapping bands */
		750	int append_non1, /* Append non-overlapping bands
		751	* in region 1 ?
		752	*/
		753	int append_non2, /* Append non-overlapping bands
		754	* in region 2 ?
		755	*/
		756	int * overlap)
		757	{
		758	box_type_t r1; / Pointer into first region */
		759	box_type_t r2; / Pointer into 2d region */
		760	box_type_t r1_end; / End of 1st region */
		761	box_type_t r2_end; / End of 2d region */
		762	int ybot; /* Bottom of intersection */
		763	int ytop; /* Top of intersection */
		764	region_data_type_t old_data; / Old data for new_reg */
		765	int prev_band; /* Index of start of
		766	* previous band in new_reg */
		767	int cur_band; /* Index of start of current
		768	* band in new_reg */
		769	box_type_t * r1_band_end; /* End of current band in r1 */
		770	box_type_t * r2_band_end; /* End of current band in r2 */
		771	int top; /* Top of non-overlapping band */
		772	int bot; /* Bottom of non-overlapping band*/
		773	int r1y1; /* Temps for r1->y1 and r2->y1 */
		774	int r2y1;
		775	int new_size;
		776	int numRects;
		777
		778	/*
		779	* Break any region computed from a broken region
		780	*/
		781	if (PIXREGION_NAR (reg1) \|\| PIXREGION_NAR (reg2))
		782	return pixman_break (new_reg);
		783
		784	/*
		785	* Initialization:
		786	* set r1, r2, r1_end and r2_end appropriately, save the rectangles
		787	* of the destination region until the end in case it's one of
		788	* the two source regions, then mark the "new" region empty, allocating
		789	* another array of rectangles for it to use.
		790	*/
		791
		792	r1 = PIXREGION_RECTS (reg1);
		793	new_size = PIXREGION_NUMRECTS (reg1);
		794	r1_end = r1 + new_size;
		795
		796	numRects = PIXREGION_NUMRECTS (reg2);
		797	r2 = PIXREGION_RECTS (reg2);
		798	r2_end = r2 + numRects;
		799
		800	critical_if_fail (r1 != r1_end);
		801	critical_if_fail (r2 != r2_end);
		802
		803	old_data = (region_data_type_t *)NULL;
		804
		805	if (((new_reg == reg1) && (new_size > 1)) \|\|
		806	((new_reg == reg2) && (numRects > 1)))
		807	{
		808	old_data = new_reg->data;
		809	new_reg->data = pixman_region_empty_data;
		810	}
		811
		812	/* guess at new size */
		813	if (numRects > new_size)
		814	new_size = numRects;
		815
		816	new_size <<= 1;
		817
		818	if (!new_reg->data)
		819	new_reg->data = pixman_region_empty_data;
		820	else if (new_reg->data->size)
		821	new_reg->data->numRects = 0;
		822
		823	if (new_size > new_reg->data->size)
		824	{
		825	if (!pixman_rect_alloc (new_reg, new_size))
		826	{
		827	if (old_data)
		828	free (old_data);
		829	return FALSE;
		830	}
		831	}
		832
		833	/*
		834	* Initialize ybot.
		835	* In the upcoming loop, ybot and ytop serve different functions depending
		836	* on whether the band being handled is an overlapping or non-overlapping
		837	* band.
		838	* In the case of a non-overlapping band (only one of the regions
		839	* has points in the band), ybot is the bottom of the most recent
		840	* intersection and thus clips the top of the rectangles in that band.
		841	* ytop is the top of the next intersection between the two regions and
		842	* serves to clip the bottom of the rectangles in the current band.
		843	* For an overlapping band (where the two regions intersect), ytop clips
		844	* the top of the rectangles of both regions and ybot clips the bottoms.
		845	*/
		846
		847	ybot = MIN (r1->y1, r2->y1);
		848
		849	/*
		850	* prev_band serves to mark the start of the previous band so rectangles
		851	* can be coalesced into larger rectangles. qv. pixman_coalesce, above.
		852	* In the beginning, there is no previous band, so prev_band == cur_band
		853	* (cur_band is set later on, of course, but the first band will always
		854	* start at index 0). prev_band and cur_band must be indices because of
		855	* the possible expansion, and resultant moving, of the new region's
		856	* array of rectangles.
		857	*/
		858	prev_band = 0;
		859
		860	do
		861	{
		862	/*
		863	* This algorithm proceeds one source-band (as opposed to a
		864	* destination band, which is determined by where the two regions
		865	* intersect) at a time. r1_band_end and r2_band_end serve to mark the
		866	* rectangle after the last one in the current band for their
		867	* respective regions.
		868	*/
		869	critical_if_fail (r1 != r1_end);
		870	critical_if_fail (r2 != r2_end);
		871
		872	FIND_BAND (r1, r1_band_end, r1_end, r1y1);
		873	FIND_BAND (r2, r2_band_end, r2_end, r2y1);
		874
		875	/*
		876	* First handle the band that doesn't intersect, if any.
		877	*
		878	* Note that attention is restricted to one band in the
		879	* non-intersecting region at once, so if a region has n
		880	* bands between the current position and the next place it overlaps
		881	* the other, this entire loop will be passed through n times.
		882	*/
		883	if (r1y1 < r2y1)
		884	{
		885	if (append_non1)
		886	{
		887	top = MAX (r1y1, ybot);
		888	bot = MIN (r1->y2, r2y1);
		889	if (top != bot)
		890	{
		891	cur_band = new_reg->data->numRects;
		892	if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))
		893	goto bail;
		894	COALESCE (new_reg, prev_band, cur_band);
		895	}
		896	}
		897	ytop = r2y1;
		898	}
		899	else if (r2y1 < r1y1)
		900	{
		901	if (append_non2)
		902	{
		903	top = MAX (r2y1, ybot);
		904	bot = MIN (r2->y2, r1y1);
		905
		906	if (top != bot)
		907	{
		908	cur_band = new_reg->data->numRects;
		909
		910	if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))
		911	goto bail;
		912
		913	COALESCE (new_reg, prev_band, cur_band);
		914	}
		915	}
		916	ytop = r1y1;
		917	}
		918	else
		919	{
		920	ytop = r1y1;
		921	}
		922
		923	/*
		924	* Now see if we've hit an intersecting band. The two bands only
		925	* intersect if ybot > ytop
		926	*/
		927	ybot = MIN (r1->y2, r2->y2);
		928	if (ybot > ytop)
		929	{
		930	cur_band = new_reg->data->numRects;
		931
		932	if (!(*overlap_func)(new_reg,
		933	r1, r1_band_end,
		934	r2, r2_band_end,
		935	ytop, ybot,
		936	overlap))
		937	{
		938	goto bail;
		939	}
		940
		941	COALESCE (new_reg, prev_band, cur_band);
		942	}
		943
		944	/*
		945	* If we've finished with a band (y2 == ybot) we skip forward
		946	* in the region to the next band.
		947	*/
		948	if (r1->y2 == ybot)
		949	r1 = r1_band_end;
		950
		951	if (r2->y2 == ybot)
		952	r2 = r2_band_end;
		953
		954	}
		955	while (r1 != r1_end && r2 != r2_end);
		956
		957	/*
		958	* Deal with whichever region (if any) still has rectangles left.
		959	*
		960	* We only need to worry about banding and coalescing for the very first
		961	* band left. After that, we can just group all remaining boxes,
		962	* regardless of how many bands, into one final append to the list.
		963	*/
		964
		965	if ((r1 != r1_end) && append_non1)
		966	{
		967	/* Do first non_overlap1Func call, which may be able to coalesce */
		968	FIND_BAND (r1, r1_band_end, r1_end, r1y1);
		969
		970	cur_band = new_reg->data->numRects;
		971
		972	if (!pixman_region_append_non_o (new_reg,
		973	r1, r1_band_end,
		974	MAX (r1y1, ybot), r1->y2))
		975	{
		976	goto bail;
		977	}
		978
		979	COALESCE (new_reg, prev_band, cur_band);
		980
		981	/* Just append the rest of the boxes */
		982	APPEND_REGIONS (new_reg, r1_band_end, r1_end);
		983	}
		984	else if ((r2 != r2_end) && append_non2)
		985	{
		986	/* Do first non_overlap2Func call, which may be able to coalesce */
		987	FIND_BAND (r2, r2_band_end, r2_end, r2y1);
		988
		989	cur_band = new_reg->data->numRects;
		990
		991	if (!pixman_region_append_non_o (new_reg,
		992	r2, r2_band_end,
		993	MAX (r2y1, ybot), r2->y2))
		994	{
		995	goto bail;
		996	}
		997
		998	COALESCE (new_reg, prev_band, cur_band);
		999
		1000	/* Append rest of boxes */
		1001	APPEND_REGIONS (new_reg, r2_band_end, r2_end);
		1002	}
		1003
		1004	if (old_data)
		1005	free (old_data);
		1006
		1007	if (!(numRects = new_reg->data->numRects))
		1008	{
		1009	FREE_DATA (new_reg);
		1010	new_reg->data = pixman_region_empty_data;
		1011	}
		1012	else if (numRects == 1)
		1013	{
		1014	new_reg->extents = *PIXREGION_BOXPTR (new_reg);
		1015	FREE_DATA (new_reg);
		1016	new_reg->data = (region_data_type_t *)NULL;
		1017	}
		1018	else
		1019	{
		1020	DOWNSIZE (new_reg, numRects);
		1021	}
		1022
		1023	return TRUE;
		1024
		1025	bail:
		1026	if (old_data)
		1027	free (old_data);
		1028
		1029	return pixman_break (new_reg);
		1030	}
		1031
		1032	/*-
		1033	*-----------------------------------------------------------------------
		1034	* pixman_set_extents --
		1035	* Reset the extents of a region to what they should be. Called by
		1036	* pixman_region_subtract and pixman_region_intersect as they can't
		1037	* figure it out along the way or do so easily, as pixman_region_union can.
		1038	*
		1039	* Results:
		1040	* None.
		1041	*
		1042	* Side Effects:
		1043	* The region's 'extents' structure is overwritten.
		1044	*
		1045	*-----------------------------------------------------------------------
		1046	*/
		1047	static void
		1048	pixman_set_extents (region_type_t *region)
		1049	{
		1050	box_type_t box, box_end;
		1051
		1052	if (!region->data)
		1053	return;
		1054
		1055	if (!region->data->size)
		1056	{
		1057	region->extents.x2 = region->extents.x1;
		1058	region->extents.y2 = region->extents.y1;
		1059	return;
		1060	}
		1061
		1062	box = PIXREGION_BOXPTR (region);
		1063	box_end = PIXREGION_END (region);
		1064
		1065	/*
		1066	* Since box is the first rectangle in the region, it must have the
		1067	* smallest y1 and since box_end is the last rectangle in the region,
		1068	* it must have the largest y2, because of banding. Initialize x1 and
		1069	* x2 from box and box_end, resp., as good things to initialize them
		1070	* to...
		1071	*/
		1072	region->extents.x1 = box->x1;
		1073	region->extents.y1 = box->y1;
		1074	region->extents.x2 = box_end->x2;
		1075	region->extents.y2 = box_end->y2;
		1076
		1077	critical_if_fail (region->extents.y1 < region->extents.y2);
		1078
		1079	while (box <= box_end)
		1080	{
		1081	if (box->x1 < region->extents.x1)
		1082	region->extents.x1 = box->x1;
		1083	if (box->x2 > region->extents.x2)
		1084	region->extents.x2 = box->x2;
		1085	box++;
		1086	}
		1087
		1088	critical_if_fail (region->extents.x1 < region->extents.x2);
		1089	}
		1090
		1091	/*======================================================================
		1092	* Region Intersection
		1093	====================================================================/
		1094	/*-
		1095	*-----------------------------------------------------------------------
		1096	* pixman_region_intersect_o --
		1097	* Handle an overlapping band for pixman_region_intersect.
		1098	*
		1099	* Results:
		1100	* TRUE if successful.
		1101	*
		1102	* Side Effects:
		1103	* Rectangles may be added to the region.
		1104	*
		1105	*-----------------------------------------------------------------------
		1106	*/
		1107	/ARGSUSED/
		1108	static pixman_bool_t
		1109	pixman_region_intersect_o (region_type_t *region,
		1110	box_type_t * r1,
		1111	box_type_t * r1_end,
		1112	box_type_t * r2,
		1113	box_type_t * r2_end,
		1114	int y1,
		1115	int y2,
		1116	int * overlap)
		1117	{
		1118	int x1;
		1119	int x2;
		1120	box_type_t * next_rect;
		1121
		1122	next_rect = PIXREGION_TOP (region);
		1123
		1124	critical_if_fail (y1 < y2);
		1125	critical_if_fail (r1 != r1_end && r2 != r2_end);
		1126
		1127	do
		1128	{
		1129	x1 = MAX (r1->x1, r2->x1);
		1130	x2 = MIN (r1->x2, r2->x2);
		1131
		1132	/*
		1133	* If there's any overlap between the two rectangles, add that
		1134	* overlap to the new region.
		1135	*/
		1136	if (x1 < x2)
		1137	NEWRECT (region, next_rect, x1, y1, x2, y2);
		1138
		1139	/*
		1140	* Advance the pointer(s) with the leftmost right side, since the next
		1141	* rectangle on that list may still overlap the other region's
		1142	* current rectangle.
		1143	*/
		1144	if (r1->x2 == x2)
		1145	{
		1146	r1++;
		1147	}
		1148	if (r2->x2 == x2)
		1149	{
		1150	r2++;
		1151	}
		1152	}
		1153	while ((r1 != r1_end) && (r2 != r2_end));
		1154
		1155	return TRUE;
		1156	}
		1157
		1158	PIXMAN_EXPORT pixman_bool_t
		1159	PREFIX (_intersect) (region_type_t * new_reg,
		1160	region_type_t * reg1,
		1161	region_type_t * reg2)
		1162	{
		1163	GOOD (reg1);
		1164	GOOD (reg2);
		1165	GOOD (new_reg);
		1166
		1167	/* check for trivial reject */
		1168	if (PIXREGION_NIL (reg1) \|\| PIXREGION_NIL (reg2) \|\|
		1169	!EXTENTCHECK (®1->extents, ®2->extents))
		1170	{
		1171	/* Covers about 20% of all cases */
		1172	FREE_DATA (new_reg);
		1173	new_reg->extents.x2 = new_reg->extents.x1;
		1174	new_reg->extents.y2 = new_reg->extents.y1;
		1175	if (PIXREGION_NAR (reg1) \|\| PIXREGION_NAR (reg2))
		1176	{
		1177	new_reg->data = pixman_broken_data;
		1178	return FALSE;
		1179	}
		1180	else
		1181	{
		1182	new_reg->data = pixman_region_empty_data;
		1183	}
		1184	}
		1185	else if (!reg1->data && !reg2->data)
		1186	{
		1187	/* Covers about 80% of cases that aren't trivially rejected */
		1188	new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);
		1189	new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);
		1190	new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);
		1191	new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);
		1192
		1193	FREE_DATA (new_reg);
		1194
		1195	new_reg->data = (region_data_type_t *)NULL;
		1196	}
		1197	else if (!reg2->data && SUBSUMES (®2->extents, ®1->extents))
		1198	{
		1199	return PREFIX (_copy) (new_reg, reg1);
		1200	}
		1201	else if (!reg1->data && SUBSUMES (®1->extents, ®2->extents))
		1202	{
		1203	return PREFIX (_copy) (new_reg, reg2);
		1204	}
		1205	else if (reg1 == reg2)
		1206	{
		1207	return PREFIX (_copy) (new_reg, reg1);
		1208	}
		1209	else
		1210	{
		1211	/* General purpose intersection */
		1212	int overlap; /* result ignored */
		1213
		1214	if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE,
		1215	&overlap))
		1216	{
		1217	return FALSE;
		1218	}
		1219
		1220	pixman_set_extents (new_reg);
		1221	}
		1222
		1223	GOOD (new_reg);
		1224	return(TRUE);
		1225	}
		1226
		1227	#define MERGERECT(r) \
		1228	do \
		1229	{ \
		1230	if (r->x1 <= x2) \
		1231	{ \
		1232	/* Merge with current rectangle */ \
		1233	if (r->x1 < x2) \
		1234	*overlap = TRUE; \
		1235	\
		1236	if (x2 < r->x2) \
		1237	x2 = r->x2; \
		1238	} \
		1239	else \
		1240	{ \
		1241	/* Add current rectangle, start new one */ \
		1242	NEWRECT (region, next_rect, x1, y1, x2, y2); \
		1243	x1 = r->x1; \
		1244	x2 = r->x2; \
		1245	} \
		1246	r++; \
		1247	} while (0)
		1248
		1249	/*======================================================================
		1250	* Region Union
		1251	====================================================================/
		1252
		1253	/*-
		1254	*-----------------------------------------------------------------------
		1255	* pixman_region_union_o --
		1256	* Handle an overlapping band for the union operation. Picks the
		1257	* left-most rectangle each time and merges it into the region.
		1258	*
		1259	* Results:
		1260	* TRUE if successful.
		1261	*
		1262	* Side Effects:
		1263	* region is overwritten.
		1264	* overlap is set to TRUE if any boxes overlap.
		1265	*
		1266	*-----------------------------------------------------------------------
		1267	*/
		1268	static pixman_bool_t
		1269	pixman_region_union_o (region_type_t *region,
		1270	box_type_t * r1,
		1271	box_type_t * r1_end,
		1272	box_type_t * r2,
		1273	box_type_t * r2_end,
		1274	int y1,
		1275	int y2,
		1276	int * overlap)
		1277	{
		1278	box_type_t *next_rect;
		1279	int x1; /* left and right side of current union */
		1280	int x2;
		1281
		1282	critical_if_fail (y1 < y2);
		1283	critical_if_fail (r1 != r1_end && r2 != r2_end);
		1284
		1285	next_rect = PIXREGION_TOP (region);
		1286
		1287	/* Start off current rectangle */
		1288	if (r1->x1 < r2->x1)
		1289	{
		1290	x1 = r1->x1;
		1291	x2 = r1->x2;
		1292	r1++;
		1293	}
		1294	else
		1295	{
		1296	x1 = r2->x1;
		1297	x2 = r2->x2;
		1298	r2++;
		1299	}
		1300	while (r1 != r1_end && r2 != r2_end)
		1301	{
		1302	if (r1->x1 < r2->x1)
		1303	MERGERECT (r1);
		1304	else
		1305	MERGERECT (r2);
		1306	}
		1307
		1308	/* Finish off whoever (if any) is left */
		1309	if (r1 != r1_end)
		1310	{
		1311	do
		1312	{
		1313	MERGERECT (r1);
		1314	}
		1315	while (r1 != r1_end);
		1316	}
		1317	else if (r2 != r2_end)
		1318	{
		1319	do
		1320	{
		1321	MERGERECT (r2);
		1322	}
		1323	while (r2 != r2_end);
		1324	}
		1325
		1326	/* Add current rectangle */
		1327	NEWRECT (region, next_rect, x1, y1, x2, y2);
		1328
		1329	return TRUE;
		1330	}
		1331
		1332	PIXMAN_EXPORT pixman_bool_t
		1333	PREFIX(_intersect_rect) (region_type_t *dest,
		1334	region_type_t *source,
		1335	int x, int y,
		1336	unsigned int width,
		1337	unsigned int height)
		1338	{
		1339	region_type_t region;
		1340
		1341	region.data = NULL;
		1342	region.extents.x1 = x;
		1343	region.extents.y1 = y;
		1344	region.extents.x2 = x + width;
		1345	region.extents.y2 = y + height;
		1346
		1347	return PREFIX(_intersect) (dest, source, ®ion);
		1348	}
		1349
		1350	/* Convenience function for performing union of region with a
		1351	* single rectangle
		1352	*/
		1353	PIXMAN_EXPORT pixman_bool_t
		1354	PREFIX (_union_rect) (region_type_t *dest,
		1355	region_type_t *source,
		1356	int x,
		1357	int y,
		1358	unsigned int width,
		1359	unsigned int height)
		1360	{
		1361	region_type_t region;
		1362
		1363	region.extents.x1 = x;
		1364	region.extents.y1 = y;
		1365	region.extents.x2 = x + width;
		1366	region.extents.y2 = y + height;
		1367
		1368	if (!GOOD_RECT (®ion.extents))
		1369	{
		1370	if (BAD_RECT (®ion.extents))
		1371	_pixman_log_error (FUNC, "Invalid rectangle passed");
		1372	return PREFIX (_copy) (dest, source);
		1373	}
		1374
		1375	region.data = NULL;
		1376
		1377	return PREFIX (_union) (dest, source, ®ion);
		1378	}
		1379
		1380	PIXMAN_EXPORT pixman_bool_t
		1381	PREFIX (_union) (region_type_t *new_reg,
		1382	region_type_t *reg1,
		1383	region_type_t *reg2)
		1384	{
		1385	int overlap; /* result ignored */
		1386
		1387	/* Return TRUE if some overlap
		1388	* between reg1, reg2
		1389	*/
		1390	GOOD (reg1);
		1391	GOOD (reg2);
		1392	GOOD (new_reg);
		1393
		1394	/* checks all the simple cases */
		1395
		1396	/*
		1397	* Region 1 and 2 are the same
		1398	*/
		1399	if (reg1 == reg2)
		1400	return PREFIX (_copy) (new_reg, reg1);
		1401
		1402	/*
		1403	* Region 1 is empty
		1404	*/
		1405	if (PIXREGION_NIL (reg1))
		1406	{
		1407	if (PIXREGION_NAR (reg1))
		1408	return pixman_break (new_reg);
		1409
		1410	if (new_reg != reg2)
		1411	return PREFIX (_copy) (new_reg, reg2);
		1412
		1413	return TRUE;
		1414	}
		1415
		1416	/*
		1417	* Region 2 is empty
		1418	*/
		1419	if (PIXREGION_NIL (reg2))
		1420	{
		1421	if (PIXREGION_NAR (reg2))
		1422	return pixman_break (new_reg);
		1423
		1424	if (new_reg != reg1)
		1425	return PREFIX (_copy) (new_reg, reg1);
		1426
		1427	return TRUE;
		1428	}
		1429
		1430	/*
		1431	* Region 1 completely subsumes region 2
		1432	*/
		1433	if (!reg1->data && SUBSUMES (®1->extents, ®2->extents))
		1434	{
		1435	if (new_reg != reg1)
		1436	return PREFIX (_copy) (new_reg, reg1);
		1437
		1438	return TRUE;
		1439	}
		1440
		1441	/*
		1442	* Region 2 completely subsumes region 1
		1443	*/
		1444	if (!reg2->data && SUBSUMES (®2->extents, ®1->extents))
		1445	{
		1446	if (new_reg != reg2)
		1447	return PREFIX (_copy) (new_reg, reg2);
		1448
		1449	return TRUE;
		1450	}
		1451
		1452	if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE, &overlap))
		1453	return FALSE;
		1454
		1455	new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);
		1456	new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);
		1457	new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);
		1458	new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);
		1459
		1460	GOOD (new_reg);
		1461
		1462	return TRUE;
		1463	}
		1464
		1465	/*======================================================================
		1466	* Batch Rectangle Union
		1467	====================================================================/
		1468
		1469	#define EXCHANGE_RECTS(a, b) \
		1470	{ \
		1471	box_type_t t; \
		1472	t = rects[a]; \
		1473	rects[a] = rects[b]; \
		1474	rects[b] = t; \
		1475	}
		1476
		1477	static void
		1478	quick_sort_rects (
		1479	box_type_t rects[],
		1480	int numRects)
		1481	{
		1482	int y1;
		1483	int x1;
		1484	int i, j;
		1485	box_type_t *r;
		1486
		1487	/* Always called with numRects > 1 */
		1488
		1489	do
		1490	{
		1491	if (numRects == 2)
		1492	{
		1493	if (rects[0].y1 > rects[1].y1 \|\|
		1494	(rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
		1495	{
		1496	EXCHANGE_RECTS (0, 1);
		1497	}
		1498
		1499	return;
		1500	}
		1501
		1502	/* Choose partition element, stick in location 0 */
		1503	EXCHANGE_RECTS (0, numRects >> 1);
		1504	y1 = rects[0].y1;
		1505	x1 = rects[0].x1;
		1506
		1507	/* Partition array */
		1508	i = 0;
		1509	j = numRects;
		1510
		1511	do
		1512	{
		1513	r = &(rects[i]);
		1514	do
		1515	{
		1516	r++;
		1517	i++;
		1518	}
		1519
		1520	while (i != numRects && (r->y1 < y1 \|\| (r->y1 == y1 && r->x1 < x1)))
		1521	;
		1522
		1523	r = &(rects[j]);
		1524	do
		1525	{
		1526	r--;
		1527	j--;
		1528	}
		1529	while (y1 < r->y1 \|\| (y1 == r->y1 && x1 < r->x1));
		1530
		1531	if (i < j)
		1532	EXCHANGE_RECTS (i, j);
		1533	}
		1534	while (i < j);
		1535
		1536	/* Move partition element back to middle */
		1537	EXCHANGE_RECTS (0, j);
		1538
		1539	/* Recurse */
		1540	if (numRects - j - 1 > 1)
		1541	quick_sort_rects (&rects[j + 1], numRects - j - 1);
		1542
		1543	numRects = j;
		1544	}
		1545	while (numRects > 1);
		1546	}
		1547
		1548	/*-
		1549	*-----------------------------------------------------------------------
		1550	* pixman_region_validate --
		1551	*
		1552	* Take a ``region'' which is a non-y-x-banded random collection of
		1553	* rectangles, and compute a nice region which is the union of all the
		1554	* rectangles.
		1555	*
		1556	* Results:
		1557	* TRUE if successful.
		1558	*
		1559	* Side Effects:
		1560	* The passed-in ``region'' may be modified.
		1561	* overlap set to TRUE if any retangles overlapped,
		1562	* else FALSE;
		1563	*
		1564	* Strategy:
		1565	* Step 1. Sort the rectangles into ascending order with primary key y1
		1566	* and secondary key x1.
		1567	*
		1568	* Step 2. Split the rectangles into the minimum number of proper y-x
		1569	* banded regions. This may require horizontally merging
		1570	* rectangles, and vertically coalescing bands. With any luck,
		1571	* this step in an identity transformation (ala the Box widget),
		1572	* or a coalescing into 1 box (ala Menus).
		1573	*
		1574	* Step 3. Merge the separate regions down to a single region by calling
		1575	* pixman_region_union. Maximize the work each pixman_region_union call does by using
		1576	* a binary merge.
		1577	*
		1578	*-----------------------------------------------------------------------
		1579	*/
		1580
		1581	static pixman_bool_t
		1582	validate (region_type_t * badreg,
		1583	int * overlap)
		1584	{
		1585	/* Descriptor for regions under construction in Step 2. */
		1586	typedef struct
		1587	{
		1588	region_type_t reg;
		1589	int prev_band;
		1590	int cur_band;
		1591	} region_info_t;
		1592
		1593	region_info_t stack_regions[64];
		1594
		1595	int numRects; /* Original numRects for badreg */
		1596	region_info_t ri; / Array of current regions */
		1597	int num_ri; /* Number of entries used in ri */
		1598	int size_ri; /* Number of entries available in ri */
		1599	int i; /* Index into rects */
		1600	int j; /* Index into ri */
		1601	region_info_t rit; / &ri[j] */
		1602	region_type_t reg; / ri[j].reg */
		1603	box_type_t box; / Current box in rects */
		1604	box_type_t ri_box; / Last box in ri[j].reg */
		1605	region_type_t hreg; / ri[j_half].reg */
		1606	pixman_bool_t ret = TRUE;
		1607
		1608	*overlap = FALSE;
		1609	if (!badreg->data)
		1610	{
		1611	GOOD (badreg);
		1612	return TRUE;
		1613	}
		1614
		1615	numRects = badreg->data->numRects;
		1616	if (!numRects)
		1617	{
		1618	if (PIXREGION_NAR (badreg))
		1619	return FALSE;
		1620	GOOD (badreg);
		1621	return TRUE;
		1622	}
		1623
		1624	if (badreg->extents.x1 < badreg->extents.x2)
		1625	{
		1626	if ((numRects) == 1)
		1627	{
		1628	FREE_DATA (badreg);
		1629	badreg->data = (region_data_type_t *) NULL;
		1630	}
		1631	else
		1632	{
		1633	DOWNSIZE (badreg, numRects);
		1634	}
		1635
		1636	GOOD (badreg);
		1637
		1638	return TRUE;
		1639	}
		1640
		1641	/* Step 1: Sort the rects array into ascending (y1, x1) order */
		1642	quick_sort_rects (PIXREGION_BOXPTR (badreg), numRects);
		1643
		1644	/* Step 2: Scatter the sorted array into the minimum number of regions */
		1645
		1646	/* Set up the first region to be the first rectangle in badreg */
		1647	/* Note that step 2 code will never overflow the ri[0].reg rects array */
		1648	ri = stack_regions;
		1649	size_ri = sizeof (stack_regions) / sizeof (stack_regions[0]);
		1650	num_ri = 1;
		1651	ri[0].prev_band = 0;
		1652	ri[0].cur_band = 0;
		1653	ri[0].reg = *badreg;
		1654	box = PIXREGION_BOXPTR (&ri[0].reg);
		1655	ri[0].reg.extents = *box;
		1656	ri[0].reg.data->numRects = 1;
		1657	badreg->extents = *pixman_region_empty_box;
		1658	badreg->data = pixman_region_empty_data;
		1659
		1660	/* Now scatter rectangles into the minimum set of valid regions. If the
		1661	* next rectangle to be added to a region would force an existing rectangle
		1662	* in the region to be split up in order to maintain y-x banding, just
		1663	* forget it. Try the next region. If it doesn't fit cleanly into any
		1664	* region, make a new one.
		1665	*/
		1666
		1667	for (i = numRects; --i > 0;)
		1668	{
		1669	box++;
		1670	/* Look for a region to append box to */
		1671	for (j = num_ri, rit = ri; --j >= 0; rit++)
		1672	{
		1673	reg = &rit->reg;
		1674	ri_box = PIXREGION_END (reg);
		1675
		1676	if (box->y1 == ri_box->y1 && box->y2 == ri_box->y2)
		1677	{
		1678	/* box is in same band as ri_box. Merge or append it */
		1679	if (box->x1 <= ri_box->x2)
		1680	{
		1681	/* Merge it with ri_box */
		1682	if (box->x1 < ri_box->x2)
		1683	*overlap = TRUE;
		1684
		1685	if (box->x2 > ri_box->x2)
		1686	ri_box->x2 = box->x2;
		1687	}
		1688	else
		1689	{
		1690	RECTALLOC_BAIL (reg, 1, bail);
		1691	PIXREGION_TOP (reg) = box;
		1692	reg->data->numRects++;
		1693	}
		1694
		1695	goto next_rect; /* So sue me */
		1696	}
		1697	else if (box->y1 >= ri_box->y2)
		1698	{
		1699	/* Put box into new band */
		1700	if (reg->extents.x2 < ri_box->x2)
		1701	reg->extents.x2 = ri_box->x2;
		1702
		1703	if (reg->extents.x1 > box->x1)
		1704	reg->extents.x1 = box->x1;
		1705
		1706	COALESCE (reg, rit->prev_band, rit->cur_band);
		1707	rit->cur_band = reg->data->numRects;
		1708	RECTALLOC_BAIL (reg, 1, bail);
		1709	PIXREGION_TOP (reg) = box;
		1710	reg->data->numRects++;
		1711
		1712	goto next_rect;
		1713	}
		1714	/* Well, this region was inappropriate. Try the next one. */
		1715	} /* for j */
		1716
		1717	/* Uh-oh. No regions were appropriate. Create a new one. */
		1718	if (size_ri == num_ri)
		1719	{
		1720	size_t data_size;
		1721
		1722	/* Oops, allocate space for new region information */
		1723	size_ri <<= 1;
		1724
		1725	data_size = size_ri * sizeof(region_info_t);
		1726	if (data_size / size_ri != sizeof(region_info_t))
		1727	goto bail;
		1728
		1729	if (ri == stack_regions)
		1730	{
		1731	rit = malloc (data_size);
		1732	if (!rit)
		1733	goto bail;
		1734	memcpy (rit, ri, num_ri * sizeof (region_info_t));
		1735	}
		1736	else
		1737	{
		1738	rit = (region_info_t *) realloc (ri, data_size);
		1739	if (!rit)
		1740	goto bail;
		1741	}
		1742	ri = rit;
		1743	rit = &ri[num_ri];
		1744	}
		1745	num_ri++;
		1746	rit->prev_band = 0;
		1747	rit->cur_band = 0;
		1748	rit->reg.extents = *box;
		1749	rit->reg.data = (region_data_type_t *)NULL;
		1750
		1751	/* MUST force allocation */
		1752	if (!pixman_rect_alloc (&rit->reg, (i + num_ri) / num_ri))
		1753	goto bail;
		1754
		1755	next_rect: ;
		1756	} /* for i */
		1757
		1758	/* Make a final pass over each region in order to COALESCE and set
		1759	* extents.x2 and extents.y2
		1760	*/
		1761	for (j = num_ri, rit = ri; --j >= 0; rit++)
		1762	{
		1763	reg = &rit->reg;
		1764	ri_box = PIXREGION_END (reg);
		1765	reg->extents.y2 = ri_box->y2;
		1766
		1767	if (reg->extents.x2 < ri_box->x2)
		1768	reg->extents.x2 = ri_box->x2;
		1769
		1770	COALESCE (reg, rit->prev_band, rit->cur_band);
		1771
		1772	if (reg->data->numRects == 1) /* keep unions happy below */
		1773	{
		1774	FREE_DATA (reg);
		1775	reg->data = (region_data_type_t *)NULL;
		1776	}
		1777	}
		1778
		1779	/* Step 3: Union all regions into a single region */
		1780	while (num_ri > 1)
		1781	{
		1782	int half = num_ri / 2;
		1783	for (j = num_ri & 1; j < (half + (num_ri & 1)); j++)
		1784	{
		1785	reg = &ri[j].reg;
		1786	hreg = &ri[j + half].reg;
		1787
		1788	if (!pixman_op (reg, reg, hreg, pixman_region_union_o, TRUE, TRUE, overlap))
		1789	ret = FALSE;
		1790
		1791	if (hreg->extents.x1 < reg->extents.x1)
		1792	reg->extents.x1 = hreg->extents.x1;
		1793
		1794	if (hreg->extents.y1 < reg->extents.y1)
		1795	reg->extents.y1 = hreg->extents.y1;
		1796
		1797	if (hreg->extents.x2 > reg->extents.x2)
		1798	reg->extents.x2 = hreg->extents.x2;
		1799
		1800	if (hreg->extents.y2 > reg->extents.y2)
		1801	reg->extents.y2 = hreg->extents.y2;
		1802
		1803	FREE_DATA (hreg);
		1804	}
		1805
		1806	num_ri -= half;
		1807
		1808	if (!ret)
		1809	goto bail;
		1810	}
		1811
		1812	*badreg = ri[0].reg;
		1813
		1814	if (ri != stack_regions)
		1815	free (ri);
		1816
		1817	GOOD (badreg);
		1818	return ret;
		1819
		1820	bail:
		1821	for (i = 0; i < num_ri; i++)
		1822	FREE_DATA (&ri[i].reg);
		1823
		1824	if (ri != stack_regions)
		1825	free (ri);
		1826
		1827	return pixman_break (badreg);
		1828	}
		1829
		1830	/*======================================================================
		1831	* Region Subtraction
		1832	====================================================================/
		1833
		1834	/*-
		1835	*-----------------------------------------------------------------------
		1836	* pixman_region_subtract_o --
		1837	* Overlapping band subtraction. x1 is the left-most point not yet
		1838	* checked.
		1839	*
		1840	* Results:
		1841	* TRUE if successful.
		1842	*
		1843	* Side Effects:
		1844	* region may have rectangles added to it.
		1845	*
		1846	*-----------------------------------------------------------------------
		1847	*/
		1848	/ARGSUSED/
		1849	static pixman_bool_t
		1850	pixman_region_subtract_o (region_type_t * region,
		1851	box_type_t * r1,
		1852	box_type_t * r1_end,
		1853	box_type_t * r2,
		1854	box_type_t * r2_end,
		1855	int y1,
		1856	int y2,
		1857	int * overlap)
		1858	{
		1859	box_type_t * next_rect;
		1860	int x1;
		1861
		1862	x1 = r1->x1;
		1863
		1864	critical_if_fail (y1 < y2);
		1865	critical_if_fail (r1 != r1_end && r2 != r2_end);
		1866
		1867	next_rect = PIXREGION_TOP (region);
		1868
		1869	do
		1870	{
		1871	if (r2->x2 <= x1)
		1872	{
		1873	/*
		1874	* Subtrahend entirely to left of minuend: go to next subtrahend.
		1875	*/
		1876	r2++;
		1877	}
		1878	else if (r2->x1 <= x1)
		1879	{
		1880	/*
		1881	* Subtrahend preceeds minuend: nuke left edge of minuend.
		1882	*/
		1883	x1 = r2->x2;
		1884	if (x1 >= r1->x2)
		1885	{
		1886	/*
		1887	* Minuend completely covered: advance to next minuend and
		1888	* reset left fence to edge of new minuend.
		1889	*/
		1890	r1++;
		1891	if (r1 != r1_end)
		1892	x1 = r1->x1;
		1893	}
		1894	else
		1895	{
		1896	/*
		1897	* Subtrahend now used up since it doesn't extend beyond
		1898	* minuend
		1899	*/
		1900	r2++;
		1901	}
		1902	}
		1903	else if (r2->x1 < r1->x2)
		1904	{
		1905	/*
		1906	* Left part of subtrahend covers part of minuend: add uncovered
		1907	* part of minuend to region and skip to next subtrahend.
		1908	*/
		1909	critical_if_fail (x1 < r2->x1);
		1910	NEWRECT (region, next_rect, x1, y1, r2->x1, y2);
		1911
		1912	x1 = r2->x2;
		1913	if (x1 >= r1->x2)
		1914	{
		1915	/*
		1916	* Minuend used up: advance to new...
		1917	*/
		1918	r1++;
		1919	if (r1 != r1_end)
		1920	x1 = r1->x1;
		1921	}
		1922	else
		1923	{
		1924	/*
		1925	* Subtrahend used up
		1926	*/
		1927	r2++;
		1928	}
		1929	}
		1930	else
		1931	{
		1932	/*
		1933	* Minuend used up: add any remaining piece before advancing.
		1934	*/
		1935	if (r1->x2 > x1)
		1936	NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
		1937
		1938	r1++;
		1939
		1940	if (r1 != r1_end)
		1941	x1 = r1->x1;
		1942	}
		1943	}
		1944	while ((r1 != r1_end) && (r2 != r2_end));
		1945
		1946	/*
		1947	* Add remaining minuend rectangles to region.
		1948	*/
		1949	while (r1 != r1_end)
		1950	{
		1951	critical_if_fail (x1 < r1->x2);
		1952
		1953	NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
		1954
		1955	r1++;
		1956	if (r1 != r1_end)
		1957	x1 = r1->x1;
		1958	}
		1959	return TRUE;
		1960	}
		1961
		1962	/*-
		1963	*-----------------------------------------------------------------------
		1964	* pixman_region_subtract --
		1965	* Subtract reg_s from reg_m and leave the result in reg_d.
		1966	* S stands for subtrahend, M for minuend and D for difference.
		1967	*
		1968	* Results:
		1969	* TRUE if successful.
		1970	*
		1971	* Side Effects:
		1972	* reg_d is overwritten.
		1973	*
		1974	*-----------------------------------------------------------------------
		1975	*/
		1976	PIXMAN_EXPORT pixman_bool_t
		1977	PREFIX (_subtract) (region_type_t *reg_d,
		1978	region_type_t *reg_m,
		1979	region_type_t *reg_s)
		1980	{
		1981	int overlap; /* result ignored */
		1982
		1983	GOOD (reg_m);
		1984	GOOD (reg_s);
		1985	GOOD (reg_d);
		1986
		1987	/* check for trivial rejects */
		1988	if (PIXREGION_NIL (reg_m) \|\| PIXREGION_NIL (reg_s) \|\|
		1989	!EXTENTCHECK (®_m->extents, ®_s->extents))
		1990	{
		1991	if (PIXREGION_NAR (reg_s))
		1992	return pixman_break (reg_d);
		1993
		1994	return PREFIX (_copy) (reg_d, reg_m);
		1995	}
		1996	else if (reg_m == reg_s)
		1997	{
		1998	FREE_DATA (reg_d);
		1999	reg_d->extents.x2 = reg_d->extents.x1;
		2000	reg_d->extents.y2 = reg_d->extents.y1;
		2001	reg_d->data = pixman_region_empty_data;
		2002
		2003	return TRUE;
		2004	}
		2005
		2006	/* Add those rectangles in region 1 that aren't in region 2,
		2007	do yucky substraction for overlaps, and
		2008	just throw away rectangles in region 2 that aren't in region 1 */
		2009	if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE, &overlap))
		2010	return FALSE;
		2011
		2012	/*
		2013	* Can't alter reg_d's extents before we call pixman_op because
		2014	* it might be one of the source regions and pixman_op depends
		2015	* on the extents of those regions being unaltered. Besides, this
		2016	* way there's no checking against rectangles that will be nuked
		2017	* due to coalescing, so we have to examine fewer rectangles.
		2018	*/
		2019	pixman_set_extents (reg_d);
		2020	GOOD (reg_d);
		2021	return TRUE;
		2022	}
		2023
		2024	/*======================================================================
		2025	* Region Inversion
		2026	====================================================================/
		2027
		2028	/*-
		2029	*-----------------------------------------------------------------------
		2030	* pixman_region_inverse --
		2031	* Take a region and a box and return a region that is everything
		2032	* in the box but not in the region. The careful reader will note
		2033	* that this is the same as subtracting the region from the box...
		2034	*
		2035	* Results:
		2036	* TRUE.
		2037	*
		2038	* Side Effects:
		2039	* new_reg is overwritten.
		2040	*
		2041	*-----------------------------------------------------------------------
		2042	*/
		2043	pixman_bool_t
		2044	PIXMAN_EXPORT PREFIX (_inverse) (region_type_t new_reg, / Destination region */
		2045	region_type_t reg1, / Region to invert */
		2046	box_type_t * inv_rect) /* Bounding box for inversion */
		2047	{
		2048	region_type_t inv_reg; /* Quick and dirty region made from the
		2049	* bounding box */
		2050	int overlap; /* result ignored */
		2051
		2052	GOOD (reg1);
		2053	GOOD (new_reg);
		2054
		2055	/* check for trivial rejects */
		2056	if (PIXREGION_NIL (reg1) \|\| !EXTENTCHECK (inv_rect, ®1->extents))
		2057	{
		2058	if (PIXREGION_NAR (reg1))
		2059	return pixman_break (new_reg);
		2060
		2061	new_reg->extents = *inv_rect;
		2062	FREE_DATA (new_reg);
		2063	new_reg->data = (region_data_type_t *)NULL;
		2064
		2065	return TRUE;
		2066	}
		2067
		2068	/* Add those rectangles in region 1 that aren't in region 2,
		2069	* do yucky substraction for overlaps, and
		2070	* just throw away rectangles in region 2 that aren't in region 1
		2071	*/
		2072	inv_reg.extents = *inv_rect;
		2073	inv_reg.data = (region_data_type_t *)NULL;
		2074	if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE, &overlap))
		2075	return FALSE;
		2076
		2077	/*
		2078	* Can't alter new_reg's extents before we call pixman_op because
		2079	* it might be one of the source regions and pixman_op depends
		2080	* on the extents of those regions being unaltered. Besides, this
		2081	* way there's no checking against rectangles that will be nuked
		2082	* due to coalescing, so we have to examine fewer rectangles.
		2083	*/
		2084	pixman_set_extents (new_reg);
		2085	GOOD (new_reg);
		2086	return TRUE;
		2087	}
		2088
		2089	/*
		2090	* rect_in(region, rect)
		2091	* This routine takes a pointer to a region and a pointer to a box
		2092	* and determines if the box is outside/inside/partly inside the region.
		2093	*
		2094	* The idea is to travel through the list of rectangles trying to cover the
		2095	* passed box with them. Anytime a piece of the rectangle isn't covered
		2096	* by a band of rectangles, part_out is set TRUE. Any time a rectangle in
		2097	* the region covers part of the box, part_in is set TRUE. The process ends
		2098	* when either the box has been completely covered (we reached a band that
		2099	* doesn't overlap the box, part_in is TRUE and part_out is false), the
		2100	* box has been partially covered (part_in == part_out == TRUE -- because of
		2101	* the banding, the first time this is true we know the box is only
		2102	* partially in the region) or is outside the region (we reached a band
		2103	* that doesn't overlap the box at all and part_in is false)
		2104	*/
		2105
		2106	pixman_region_overlap_t
		2107	PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t * region,
		2108	box_type_t * prect)
		2109	{
		2110	box_type_t * pbox;
		2111	box_type_t * pbox_end;
		2112	int part_in, part_out;
		2113	int numRects;
		2114	int x, y;
		2115
		2116	GOOD (region);
		2117
		2118	numRects = PIXREGION_NUMRECTS (region);
		2119
		2120	/* useful optimization */
		2121	if (!numRects \|\| !EXTENTCHECK (®ion->extents, prect))
		2122	return(PIXMAN_REGION_OUT);
		2123
		2124	if (numRects == 1)
		2125	{
		2126	/* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
		2127	if (SUBSUMES (®ion->extents, prect))
		2128	return(PIXMAN_REGION_IN);
		2129	else
		2130	return(PIXMAN_REGION_PART);
		2131	}
		2132
		2133	part_out = FALSE;
		2134	part_in = FALSE;
		2135
		2136	/* (x,y) starts at upper left of rect, moving to the right and down */
		2137	x = prect->x1;
		2138	y = prect->y1;
		2139
		2140	/* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */
		2141	for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
		2142	pbox != pbox_end;
		2143	pbox++)
		2144	{
		2145
		2146	if (pbox->y2 <= y)
		2147	continue; /* getting up to speed or skipping remainder of band */
		2148
		2149	if (pbox->y1 > y)
		2150	{
		2151	part_out = TRUE; /* missed part of rectangle above */
		2152	if (part_in \|\| (pbox->y1 >= prect->y2))
		2153	break;
		2154	y = pbox->y1; /* x guaranteed to be == prect->x1 */
		2155	}
		2156
		2157	if (pbox->x2 <= x)
		2158	continue; /* not far enough over yet */
		2159
		2160	if (pbox->x1 > x)
		2161	{
		2162	part_out = TRUE; /* missed part of rectangle to left */
		2163	if (part_in)
		2164	break;
		2165	}
		2166
		2167	if (pbox->x1 < prect->x2)
		2168	{
		2169	part_in = TRUE; /* definitely overlap */
		2170	if (part_out)
		2171	break;
		2172	}
		2173
		2174	if (pbox->x2 >= prect->x2)
		2175	{
		2176	y = pbox->y2; /* finished with this band */
		2177	if (y >= prect->y2)
		2178	break;
		2179	x = prect->x1; /* reset x out to left again */
		2180	}
		2181	else
		2182	{
		2183	/*
		2184	* Because boxes in a band are maximal width, if the first box
		2185	* to overlap the rectangle doesn't completely cover it in that
		2186	* band, the rectangle must be partially out, since some of it
		2187	* will be uncovered in that band. part_in will have been set true
		2188	* by now...
		2189	*/
		2190	part_out = TRUE;
		2191	break;
		2192	}
		2193	}
		2194
		2195	if (part_in)
		2196	{
		2197	if (y < prect->y2)
		2198	return PIXMAN_REGION_PART;
		2199	else
		2200	return PIXMAN_REGION_IN;
		2201	}
		2202	else
		2203	{
		2204	return PIXMAN_REGION_OUT;
		2205	}
		2206	}
		2207
		2208	/* PREFIX(_translate) (region, x, y)
		2209	* translates in place
		2210	*/
		2211
		2212	PIXMAN_EXPORT void
		2213	PREFIX (_translate) (region_type_t *region, int x, int y)
		2214	{
		2215	overflow_int_t x1, x2, y1, y2;
		2216	int nbox;
		2217	box_type_t * pbox;
		2218
		2219	GOOD (region);
		2220	region->extents.x1 = x1 = region->extents.x1 + x;
		2221	region->extents.y1 = y1 = region->extents.y1 + y;
		2222	region->extents.x2 = x2 = region->extents.x2 + x;
		2223	region->extents.y2 = y2 = region->extents.y2 + y;
		2224
		2225	if (((x1 - PIXMAN_REGION_MIN) \| (y1 - PIXMAN_REGION_MIN) \| (PIXMAN_REGION_MAX - x2) \| (PIXMAN_REGION_MAX - y2)) >= 0)
		2226	{
		2227	if (region->data && (nbox = region->data->numRects))
		2228	{
		2229	for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
		2230	{
		2231	pbox->x1 += x;
		2232	pbox->y1 += y;
		2233	pbox->x2 += x;
		2234	pbox->y2 += y;
		2235	}
		2236	}
		2237	return;
		2238	}
		2239
		2240	if (((x2 - PIXMAN_REGION_MIN) \| (y2 - PIXMAN_REGION_MIN) \| (PIXMAN_REGION_MAX - x1) \| (PIXMAN_REGION_MAX - y1)) <= 0)
		2241	{
		2242	region->extents.x2 = region->extents.x1;
		2243	region->extents.y2 = region->extents.y1;
		2244	FREE_DATA (region);
		2245	region->data = pixman_region_empty_data;
		2246	return;
		2247	}
		2248
		2249	if (x1 < PIXMAN_REGION_MIN)
		2250	region->extents.x1 = PIXMAN_REGION_MIN;
		2251	else if (x2 > PIXMAN_REGION_MAX)
		2252	region->extents.x2 = PIXMAN_REGION_MAX;
		2253
		2254	if (y1 < PIXMAN_REGION_MIN)
		2255	region->extents.y1 = PIXMAN_REGION_MIN;
		2256	else if (y2 > PIXMAN_REGION_MAX)
		2257	region->extents.y2 = PIXMAN_REGION_MAX;
		2258
		2259	if (region->data && (nbox = region->data->numRects))
		2260	{
		2261	box_type_t * pbox_out;
		2262
		2263	for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
		2264	{
		2265	pbox_out->x1 = x1 = pbox->x1 + x;
		2266	pbox_out->y1 = y1 = pbox->y1 + y;
		2267	pbox_out->x2 = x2 = pbox->x2 + x;
		2268	pbox_out->y2 = y2 = pbox->y2 + y;
		2269
		2270	if (((x2 - PIXMAN_REGION_MIN) \| (y2 - PIXMAN_REGION_MIN) \|
		2271	(PIXMAN_REGION_MAX - x1) \| (PIXMAN_REGION_MAX - y1)) <= 0)
		2272	{
		2273	region->data->numRects--;
		2274	continue;
		2275	}
		2276
		2277	if (x1 < PIXMAN_REGION_MIN)
		2278	pbox_out->x1 = PIXMAN_REGION_MIN;
		2279	else if (x2 > PIXMAN_REGION_MAX)
		2280	pbox_out->x2 = PIXMAN_REGION_MAX;
		2281
		2282	if (y1 < PIXMAN_REGION_MIN)
		2283	pbox_out->y1 = PIXMAN_REGION_MIN;
		2284	else if (y2 > PIXMAN_REGION_MAX)
		2285	pbox_out->y2 = PIXMAN_REGION_MAX;
		2286
		2287	pbox_out++;
		2288	}
		2289
		2290	if (pbox_out != pbox)
		2291	{
		2292	if (region->data->numRects == 1)
		2293	{
		2294	region->extents = *PIXREGION_BOXPTR (region);
		2295	FREE_DATA (region);
		2296	region->data = (region_data_type_t *)NULL;
		2297	}
		2298	else
		2299	{
		2300	pixman_set_extents (region);
		2301	}
		2302	}
		2303	}
		2304
		2305	GOOD (region);
		2306	}
		2307
		2308	PIXMAN_EXPORT void
		2309	PREFIX (_reset) (region_type_t region, box_type_t box)
		2310	{
		2311	GOOD (region);
		2312
		2313	critical_if_fail (GOOD_RECT (box));
		2314
		2315	region->extents = *box;
		2316
		2317	FREE_DATA (region);
		2318
		2319	region->data = NULL;
		2320	}
		2321
		2322	/* box is "return" value */
		2323	PIXMAN_EXPORT int
		2324	PREFIX (_contains_point) (region_type_t * region,
		2325	int x, int y,
		2326	box_type_t * box)
		2327	{
		2328	box_type_t pbox, pbox_end;
		2329	int numRects;
		2330
		2331	GOOD (region);
		2332	numRects = PIXREGION_NUMRECTS (region);
		2333
		2334	if (!numRects \|\| !INBOX (®ion->extents, x, y))
		2335	return(FALSE);
		2336
		2337	if (numRects == 1)
		2338	{
		2339	if (box)
		2340	*box = region->extents;
		2341
		2342	return(TRUE);
		2343	}
		2344
		2345	for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
		2346	pbox != pbox_end;
		2347	pbox++)
		2348	{
		2349	if (y >= pbox->y2)
		2350	continue; /* not there yet */
		2351
		2352	if ((y < pbox->y1) \|\| (x < pbox->x1))
		2353	break; /* missed it */
		2354
		2355	if (x >= pbox->x2)
		2356	continue; /* not there yet */
		2357
		2358	if (box)
		2359	box = pbox;
		2360
		2361	return(TRUE);
		2362	}
		2363
		2364	return(FALSE);
		2365	}
		2366
		2367	PIXMAN_EXPORT int
		2368	PREFIX (_not_empty) (region_type_t * region)
		2369	{
		2370	GOOD (region);
		2371
		2372	return(!PIXREGION_NIL (region));
		2373	}
		2374
		2375	PIXMAN_EXPORT box_type_t *
		2376	PREFIX (_extents) (region_type_t * region)
		2377	{
		2378	GOOD (region);
		2379
		2380	return(®ion->extents);
		2381	}
		2382
		2383	/*
		2384	* Clip a list of scanlines to a region. The caller has allocated the
		2385	* space. FSorted is non-zero if the scanline origins are in ascending order.
		2386	*
		2387	* returns the number of new, clipped scanlines.
		2388	*/
		2389
		2390	PIXMAN_EXPORT pixman_bool_t
		2391	PREFIX (_selfcheck) (region_type_t *reg)
		2392	{
		2393	int i, numRects;
		2394
		2395	if ((reg->extents.x1 > reg->extents.x2) \|\|
		2396	(reg->extents.y1 > reg->extents.y2))
		2397	{
		2398	return FALSE;
		2399	}
		2400
		2401	numRects = PIXREGION_NUMRECTS (reg);
		2402	if (!numRects)
		2403	{
		2404	return ((reg->extents.x1 == reg->extents.x2) &&
		2405	(reg->extents.y1 == reg->extents.y2) &&
		2406	(reg->data->size \|\| (reg->data == pixman_region_empty_data)));
		2407	}
		2408	else if (numRects == 1)
		2409	{
		2410	return (!reg->data);
		2411	}
		2412	else
		2413	{
		2414	box_type_t * pbox_p, * pbox_n;
		2415	box_type_t box;
		2416
		2417	pbox_p = PIXREGION_RECTS (reg);
		2418	box = *pbox_p;
		2419	box.y2 = pbox_p[numRects - 1].y2;
		2420	pbox_n = pbox_p + 1;
		2421
		2422	for (i = numRects; --i > 0; pbox_p++, pbox_n++)
		2423	{
		2424	if ((pbox_n->x1 >= pbox_n->x2) \|\|
		2425	(pbox_n->y1 >= pbox_n->y2))
		2426	{
		2427	return FALSE;
		2428	}
		2429
		2430	if (pbox_n->x1 < box.x1)
		2431	box.x1 = pbox_n->x1;
		2432
		2433	if (pbox_n->x2 > box.x2)
		2434	box.x2 = pbox_n->x2;
		2435
		2436	if ((pbox_n->y1 < pbox_p->y1) \|\|
		2437	((pbox_n->y1 == pbox_p->y1) &&
		2438	((pbox_n->x1 < pbox_p->x2) \|\| (pbox_n->y2 != pbox_p->y2))))
		2439	{
		2440	return FALSE;
		2441	}
		2442	}
		2443
		2444	return ((box.x1 == reg->extents.x1) &&
		2445	(box.x2 == reg->extents.x2) &&
		2446	(box.y1 == reg->extents.y1) &&
		2447	(box.y2 == reg->extents.y2));
		2448	}
		2449	}
		2450
		2451	PIXMAN_EXPORT pixman_bool_t
		2452	PREFIX (_init_rects) (region_type_t *region,
		2453	const box_type_t *boxes, int count)
		2454	{
		2455	box_type_t *rects;
		2456	int displacement;
		2457	int i;
		2458
		2459	/* if it's 1, then we just want to set the extents, so call
		2460	* the existing method. */
		2461	if (count == 1)
		2462	{
		2463	PREFIX (_init_rect) (region,
		2464	boxes[0].x1,
		2465	boxes[0].y1,
		2466	boxes[0].x2 - boxes[0].x1,
		2467	boxes[0].y2 - boxes[0].y1);
		2468	return TRUE;
		2469	}
		2470
		2471	PREFIX (_init) (region);
		2472
		2473	/* if it's 0, don't call pixman_rect_alloc -- 0 rectangles is
		2474	* a special case, and causing pixman_rect_alloc would cause
		2475	* us to leak memory (because the 0-rect case should be the
		2476	* static pixman_region_empty_data data).
		2477	*/
		2478	if (count == 0)
		2479	return TRUE;
		2480
		2481	if (!pixman_rect_alloc (region, count))
		2482	return FALSE;
		2483
		2484	rects = PIXREGION_RECTS (region);
		2485
		2486	/* Copy in the rects */
		2487	memcpy (rects, boxes, sizeof(box_type_t) * count);
		2488	region->data->numRects = count;
		2489
		2490	/* Eliminate empty and malformed rectangles */
		2491	displacement = 0;
		2492
		2493	for (i = 0; i < count; ++i)
		2494	{
		2495	box_type_t *box = &rects[i];
		2496
		2497	if (box->x1 >= box->x2 \|\| box->y1 >= box->y2)
		2498	displacement++;
		2499	else if (displacement)
		2500	rects[i - displacement] = rects[i];
		2501	}
		2502
		2503	region->data->numRects -= displacement;
		2504
		2505	/* If eliminating empty rectangles caused there
		2506	* to be only 0 or 1 rectangles, deal with that.
		2507	*/
		2508	if (region->data->numRects == 0)
		2509	{
		2510	FREE_DATA (region);
		2511	PREFIX (_init) (region);
		2512
		2513	return TRUE;
		2514	}
		2515
		2516	if (region->data->numRects == 1)
		2517	{
		2518	region->extents = rects[0];
		2519
		2520	FREE_DATA (region);
		2521	region->data = NULL;
		2522
		2523	GOOD (region);
		2524
		2525	return TRUE;
		2526	}
		2527
		2528	/* Validate */
		2529	region->extents.x1 = region->extents.x2 = 0;
		2530
		2531	return validate (region, &i);
		2532	}
		2533
		2534	#define READ(_ptr) (*(_ptr))
		2535
		2536	static inline box_type_t *
		2537	bitmap_addrect (region_type_t *reg,
		2538	box_type_t *r,
		2539	box_type_t **first_rect,
		2540	int rx1, int ry1,
		2541	int rx2, int ry2)
		2542	{
		2543	if ((rx1 < rx2) && (ry1 < ry2) &&
		2544	(!(reg->data->numRects &&
		2545	((r-1)->y1 == ry1) && ((r-1)->y2 == ry2) &&
		2546	((r-1)->x1 <= rx1) && ((r-1)->x2 >= rx2))))
		2547	{
		2548	if (!reg->data \|\|
		2549	reg->data->numRects == reg->data->size)
		2550	{
		2551	if (!pixman_rect_alloc (reg, 1))
		2552	return NULL;
		2553	*first_rect = PIXREGION_BOXPTR(reg);
		2554	r = *first_rect + reg->data->numRects;
		2555	}
		2556	r->x1 = rx1;
		2557	r->y1 = ry1;
		2558	r->x2 = rx2;
		2559	r->y2 = ry2;
		2560	reg->data->numRects++;
		2561	if (r->x1 < reg->extents.x1)
		2562	reg->extents.x1 = r->x1;
		2563	if (r->x2 > reg->extents.x2)
		2564	reg->extents.x2 = r->x2;
		2565	r++;
		2566	}
		2567	return r;
		2568	}
		2569
		2570	/* Convert bitmap clip mask into clipping region.
		2571	* First, goes through each line and makes boxes by noting the transitions
		2572	* from 0 to 1 and 1 to 0.
		2573	* Then it coalesces the current line with the previous if they have boxes
		2574	* at the same X coordinates.
		2575	* Stride is in number of uint32_t per line.
		2576	*/
		2577	PIXMAN_EXPORT void
		2578	PREFIX (_init_from_image) (region_type_t *region,
		2579	pixman_image_t *image)
		2580	{
		2581	uint32_t mask0 = 0xffffffff & ~SCREEN_SHIFT_RIGHT(0xffffffff, 1);
		2582	box_type_t first_rect, rects, *prect_line_start;
		2583	box_type_t old_rect, new_rect;
		2584	uint32_t pw, w, pw_line, *pw_line_end;
		2585	int irect_prev_start, irect_line_start;
		2586	int h, base, rx1 = 0, crects;
		2587	int ib;
		2588	pixman_bool_t in_box, same;
		2589	int width, height, stride;
		2590
		2591	PREFIX(_init) (region);
		2592
		2593	return_if_fail (image->type == BITS);
		2594	return_if_fail (image->bits.format == PIXMAN_a1);
		2595
		2596	pw_line = pixman_image_get_data (image);
		2597	width = pixman_image_get_width (image);
		2598	height = pixman_image_get_height (image);
		2599	stride = pixman_image_get_stride (image) / 4;
		2600
		2601	first_rect = PIXREGION_BOXPTR(region);
		2602	rects = first_rect;
		2603
		2604	region->extents.x1 = width - 1;
		2605	region->extents.x2 = 0;
		2606	irect_prev_start = -1;
		2607	for (h = 0; h < height; h++)
		2608	{
		2609	pw = pw_line;
		2610	pw_line += stride;
		2611	irect_line_start = rects - first_rect;
		2612
		2613	/* If the Screen left most bit of the word is set, we're starting in
		2614	* a box */
		2615	if (READ(pw) & mask0)
		2616	{
		2617	in_box = TRUE;
		2618	rx1 = 0;
		2619	}
		2620	else
		2621	{
		2622	in_box = FALSE;
		2623	}
		2624
		2625	/* Process all words which are fully in the pixmap */
		2626	pw_line_end = pw + (width >> 5);
		2627	for (base = 0; pw < pw_line_end; base += 32)
		2628	{
		2629	w = READ(pw++);
		2630	if (in_box)
		2631	{
		2632	if (!~w)
		2633	continue;
		2634	}
		2635	else
		2636	{
		2637	if (!w)
		2638	continue;
		2639	}
		2640	for (ib = 0; ib < 32; ib++)
		2641	{
		2642	/* If the Screen left most bit of the word is set, we're
		2643	* starting a box */
		2644	if (w & mask0)
		2645	{
		2646	if (!in_box)
		2647	{
		2648	rx1 = base + ib;
		2649	/* start new box */
		2650	in_box = TRUE;
		2651	}
		2652	}
		2653	else
		2654	{
		2655	if (in_box)
		2656	{
		2657	/* end box */
		2658	rects = bitmap_addrect (region, rects, &first_rect,
		2659	rx1, h, base + ib, h + 1);
		2660	if (rects == NULL)
		2661	goto error;
		2662	in_box = FALSE;
		2663	}
		2664	}
		2665	/* Shift the word VISUALLY left one. */
		2666	w = SCREEN_SHIFT_LEFT(w, 1);
		2667	}
		2668	}
		2669
		2670	if (width & 31)
		2671	{
		2672	/* Process final partial word on line */
		2673	w = READ(pw++);
		2674	for (ib = 0; ib < (width & 31); ib++)
		2675	{
		2676	/* If the Screen left most bit of the word is set, we're
		2677	* starting a box */
		2678	if (w & mask0)
		2679	{
		2680	if (!in_box)
		2681	{
		2682	rx1 = base + ib;
		2683	/* start new box */
		2684	in_box = TRUE;
		2685	}
		2686	}
		2687	else
		2688	{
		2689	if (in_box)
		2690	{
		2691	/* end box */
		2692	rects = bitmap_addrect(region, rects, &first_rect,
		2693	rx1, h, base + ib, h + 1);
		2694	if (rects == NULL)
		2695	goto error;
		2696	in_box = FALSE;
		2697	}
		2698	}
		2699	/* Shift the word VISUALLY left one. */
		2700	w = SCREEN_SHIFT_LEFT(w, 1);
		2701	}
		2702	}
		2703	/* If scanline ended with last bit set, end the box */
		2704	if (in_box)
		2705	{
		2706	rects = bitmap_addrect(region, rects, &first_rect,
		2707	rx1, h, base + (width & 31), h + 1);
		2708	if (rects == NULL)
		2709	goto error;
		2710	}
		2711	/* if all rectangles on this line have the same x-coords as
		2712	* those on the previous line, then add 1 to all the previous y2s and
		2713	* throw away all the rectangles from this line
		2714	*/
		2715	same = FALSE;
		2716	if (irect_prev_start != -1)
		2717	{
		2718	crects = irect_line_start - irect_prev_start;
		2719	if (crects != 0 &&
		2720	crects == ((rects - first_rect) - irect_line_start))
		2721	{
		2722	old_rect = first_rect + irect_prev_start;
		2723	new_rect = prect_line_start = first_rect + irect_line_start;
		2724	same = TRUE;
		2725	while (old_rect < prect_line_start)
		2726	{
		2727	if ((old_rect->x1 != new_rect->x1) \|\|
		2728	(old_rect->x2 != new_rect->x2))
		2729	{
		2730	same = FALSE;
		2731	break;
		2732	}
		2733	old_rect++;
		2734	new_rect++;
		2735	}
		2736	if (same)
		2737	{
		2738	old_rect = first_rect + irect_prev_start;
		2739	while (old_rect < prect_line_start)
		2740	{
		2741	old_rect->y2 += 1;
		2742	old_rect++;
		2743	}
		2744	rects -= crects;
		2745	region->data->numRects -= crects;
		2746	}
		2747	}
		2748	}
		2749	if(!same)
		2750	irect_prev_start = irect_line_start;
		2751	}
		2752	if (!region->data->numRects)
		2753	{
		2754	region->extents.x1 = region->extents.x2 = 0;
		2755	}
		2756	else
		2757	{
		2758	region->extents.y1 = PIXREGION_BOXPTR(region)->y1;
		2759	region->extents.y2 = PIXREGION_END(region)->y2;
		2760	if (region->data->numRects == 1)
		2761	{
		2762	free (region->data);
		2763	region->data = NULL;
		2764	}
		2765	}
		2766
		2767	error:
		2768	return;
		2769	}

Subversion Repositories Kolibri OS

(root)/programs/develop/libraries/pixman/pixman-region.c @ 1901 – Rev 1891