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

Subversion Repositories Kolibri OS

(root)/programs/develop/libraries/pixman/pixman-region.c – Rev 3931