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

Rev	Author	Line No.	Line
1891	serge	1	/*
		2	* Copyright © 2008 Keith Packard
		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 copyright
		7	* notice and this permission notice appear in supporting documentation, and
		8	* that the name of the copyright holders not be used in advertising or
		9	* publicity pertaining to distribution of the software without specific,
		10	* written prior permission. The copyright holders make no representations
		11	* about the suitability of this software for any purpose. It is provided "as
		12	* is" without express or implied warranty.
		13	*
		14	* THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
		15	* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
		16	* EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
		17	* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
		18	* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
		19	* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
		20	* OF THIS SOFTWARE.
		21	*/
		22
		23	/*
		24	* Matrix interfaces
		25	*/
		26
		27	#ifdef HAVE_CONFIG_H
3931	Serge	28	#include
1891	serge	29	#endif
		30
		31	#include
		32	#include
		33	#include "pixman-private.h"
		34
		35	#define F(x) pixman_int_to_fixed (x)
		36
3931	Serge	37	static force_inline int
		38	count_leading_zeros (uint32_t x)
		39	{
		40	#ifdef __GNUC__
		41	return __builtin_clz (x);
		42	#else
		43	int n = 0;
		44	while (x)
		45	{
		46	n++;
		47	x >>= 1;
		48	}
		49	return 32 - n;
		50	#endif
		51	}
		52
		53	/*
		54	* Large signed/unsigned integer division with rounding for the platforms with
		55	* only 64-bit integer data type supported (no 128-bit data type).
		56	*
		57	* Arguments:
		58	* hi, lo - high and low 64-bit parts of the dividend
		59	* div - 48-bit divisor
		60	*
		61	* Returns: lowest 64 bits of the result as a return value and highest 64
		62	* bits of the result to "result_hi" pointer
		63	*/
		64
		65	/* grade-school unsigned division (128-bit by 48-bit) with rounding to nearest */
		66	static force_inline uint64_t
		67	rounded_udiv_128_by_48 (uint64_t hi,
		68	uint64_t lo,
		69	uint64_t div,
		70	uint64_t *result_hi)
		71	{
		72	uint64_t tmp, remainder, result_lo;
		73	assert(div < ((uint64_t)1 << 48));
		74
		75	remainder = hi % div;
		76	*result_hi = hi / div;
		77
		78	tmp = (remainder << 16) + (lo >> 48);
		79	result_lo = tmp / div;
		80	remainder = tmp % div;
		81
		82	tmp = (remainder << 16) + ((lo >> 32) & 0xFFFF);
		83	result_lo = (result_lo << 16) + (tmp / div);
		84	remainder = tmp % div;
		85
		86	tmp = (remainder << 16) + ((lo >> 16) & 0xFFFF);
		87	result_lo = (result_lo << 16) + (tmp / div);
		88	remainder = tmp % div;
		89
		90	tmp = (remainder << 16) + (lo & 0xFFFF);
		91	result_lo = (result_lo << 16) + (tmp / div);
		92	remainder = tmp % div;
		93
		94	/* round to nearest */
		95	if (remainder * 2 >= div && ++result_lo == 0)
		96	*result_hi += 1;
		97
		98	return result_lo;
		99	}
		100
		101	/* signed division (128-bit by 49-bit) with rounding to nearest */
		102	static inline int64_t
		103	rounded_sdiv_128_by_49 (int64_t hi,
		104	uint64_t lo,
		105	int64_t div,
		106	int64_t *signed_result_hi)
		107	{
		108	uint64_t result_lo, result_hi;
		109	int sign = 0;
		110	if (div < 0)
		111	{
		112	div = -div;
		113	sign ^= 1;
		114	}
		115	if (hi < 0)
		116	{
		117	if (lo != 0)
		118	hi++;
		119	hi = -hi;
		120	lo = -lo;
		121	sign ^= 1;
		122	}
		123	result_lo = rounded_udiv_128_by_48 (hi, lo, div, &result_hi);
		124	if (sign)
		125	{
		126	if (result_lo != 0)
		127	result_hi++;
		128	result_hi = -result_hi;
		129	result_lo = -result_lo;
		130	}
		131	if (signed_result_hi)
		132	{
		133	*signed_result_hi = result_hi;
		134	}
		135	return result_lo;
		136	}
		137
		138	/*
		139	* Multiply 64.16 fixed point value by (2^scalebits) and convert
		140	* to 128-bit integer.
		141	*/
		142	static force_inline void
		143	fixed_64_16_to_int128 (int64_t hi,
		144	int64_t lo,
		145	int64_t *rhi,
		146	int64_t *rlo,
		147	int scalebits)
		148	{
		149	/* separate integer and fractional parts */
		150	hi += lo >> 16;
		151	lo &= 0xFFFF;
		152
		153	if (scalebits <= 0)
		154	{
		155	*rlo = hi >> (-scalebits);
		156	rhi = rlo >> 63;
		157	}
		158	else
		159	{
		160	*rhi = hi >> (64 - scalebits);
		161	*rlo = (uint64_t)hi << scalebits;
		162	if (scalebits < 16)
		163	*rlo += lo >> (16 - scalebits);
		164	else
		165	*rlo += lo << (scalebits - 16);
		166	}
		167	}
		168
		169	/*
		170	* Convert 112.16 fixed point value to 48.16 with clamping for the out
		171	* of range values.
		172	*/
		173	static force_inline pixman_fixed_48_16_t
		174	fixed_112_16_to_fixed_48_16 (int64_t hi, int64_t lo, pixman_bool_t *clampflag)
		175	{
		176	if ((lo >> 63) != hi)
		177	{
		178	*clampflag = TRUE;
		179	return hi >= 0 ? INT64_MAX : INT64_MIN;
		180	}
		181	else
		182	{
		183	return lo;
		184	}
		185	}
		186
		187	/*
		188	* Transform a point with 31.16 fixed point coordinates from the destination
		189	* space to a point with 48.16 fixed point coordinates in the source space.
		190	* No overflows are possible for affine transformations and the results are
		191	* accurate including the least significant bit. Projective transformations
		192	* may overflow, in this case the results are just clamped to return maximum
		193	* or minimum 48.16 values (so that the caller can at least handle the NONE
		194	* and PAD repeats correctly) and the return value is FALSE to indicate that
		195	* such clamping has happened.
		196	*/
		197	PIXMAN_EXPORT pixman_bool_t
		198	pixman_transform_point_31_16 (const pixman_transform_t *t,
		199	const pixman_vector_48_16_t *v,
		200	pixman_vector_48_16_t *result)
		201	{
		202	pixman_bool_t clampflag = FALSE;
		203	int i;
		204	int64_t tmp[3][2], divint;
		205	uint16_t divfrac;
		206
		207	/* input vector values must have no more than 31 bits (including sign)
		208	* in the integer part */
		209	assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		210	assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		211	assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		212	assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		213	assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		214	assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		215
		216	for (i = 0; i < 3; i++)
		217	{
		218	tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
		219	tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
		220	tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
		221	tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
		222	tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
		223	tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF);
		224	}
		225
		226	/*
		227	* separate 64-bit integer and 16-bit fractional parts for the divisor,
		228	* which is also scaled by 65536 after fixed point multiplication.
		229	*/
		230	divint = tmp[2][0] + (tmp[2][1] >> 16);
		231	divfrac = tmp[2][1] & 0xFFFF;
		232
		233	if (divint == pixman_fixed_1 && divfrac == 0)
		234	{
		235	/*
		236	* this is a simple affine transformation
		237	*/
		238	result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
		239	result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
		240	result->v[2] = pixman_fixed_1;
		241	}
		242	else if (divint == 0 && divfrac == 0)
		243	{
		244	/*
		245	* handle zero divisor (if the values are non-zero, set the
		246	* results to maximum positive or minimum negative)
		247	*/
		248	clampflag = TRUE;
		249
		250	result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
		251	result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
		252
		253	if (result->v[0] > 0)
		254	result->v[0] = INT64_MAX;
		255	else if (result->v[0] < 0)
		256	result->v[0] = INT64_MIN;
		257
		258	if (result->v[1] > 0)
		259	result->v[1] = INT64_MAX;
		260	else if (result->v[1] < 0)
		261	result->v[1] = INT64_MIN;
		262	}
		263	else
		264	{
		265	/*
		266	* projective transformation, analyze the top 32 bits of the divisor
		267	*/
		268	int32_t hi32divbits = divint >> 32;
		269	if (hi32divbits < 0)
		270	hi32divbits = ~hi32divbits;
		271
		272	if (hi32divbits == 0)
		273	{
		274	/* the divisor is small, we can actually keep all the bits */
		275	int64_t hi, rhi, lo, rlo;
		276	int64_t div = (divint << 16) + divfrac;
		277
		278	fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32);
		279	rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
		280	result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
		281
		282	fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32);
		283	rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
		284	result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
		285	}
		286	else
		287	{
		288	/* the divisor needs to be reduced to 48 bits */
		289	int64_t hi, rhi, lo, rlo, div;
		290	int shift = 32 - count_leading_zeros (hi32divbits);
		291	fixed_64_16_to_int128 (divint, divfrac, &hi, &div, 16 - shift);
		292
		293	fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32 - shift);
		294	rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
		295	result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
		296
		297	fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32 - shift);
		298	rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
		299	result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
		300	}
		301	}
		302	result->v[2] = pixman_fixed_1;
		303	return !clampflag;
		304	}
		305
1891	serge	306	PIXMAN_EXPORT void
3931	Serge	307	pixman_transform_point_31_16_affine (const pixman_transform_t *t,
		308	const pixman_vector_48_16_t *v,
		309	pixman_vector_48_16_t *result)
		310	{
		311	int64_t hi0, lo0, hi1, lo1;
		312
		313	/* input vector values must have no more than 31 bits (including sign)
		314	* in the integer part */
		315	assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		316	assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		317	assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		318	assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		319
		320	hi0 = (int64_t)t->matrix[0][0] * (v->v[0] >> 16);
		321	lo0 = (int64_t)t->matrix[0][0] * (v->v[0] & 0xFFFF);
		322	hi0 += (int64_t)t->matrix[0][1] * (v->v[1] >> 16);
		323	lo0 += (int64_t)t->matrix[0][1] * (v->v[1] & 0xFFFF);
		324	hi0 += (int64_t)t->matrix[0][2];
		325
		326	hi1 = (int64_t)t->matrix[1][0] * (v->v[0] >> 16);
		327	lo1 = (int64_t)t->matrix[1][0] * (v->v[0] & 0xFFFF);
		328	hi1 += (int64_t)t->matrix[1][1] * (v->v[1] >> 16);
		329	lo1 += (int64_t)t->matrix[1][1] * (v->v[1] & 0xFFFF);
		330	hi1 += (int64_t)t->matrix[1][2];
		331
		332	result->v[0] = hi0 + ((lo0 + 0x8000) >> 16);
		333	result->v[1] = hi1 + ((lo1 + 0x8000) >> 16);
		334	result->v[2] = pixman_fixed_1;
		335	}
		336
		337	PIXMAN_EXPORT void
		338	pixman_transform_point_31_16_3d (const pixman_transform_t *t,
		339	const pixman_vector_48_16_t *v,
		340	pixman_vector_48_16_t *result)
		341	{
		342	int i;
		343	int64_t tmp[3][2];
		344
		345	/* input vector values must have no more than 31 bits (including sign)
		346	* in the integer part */
		347	assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		348	assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		349	assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		350	assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		351	assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
		352	assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
		353
		354	for (i = 0; i < 3; i++)
		355	{
		356	tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
		357	tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
		358	tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
		359	tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
		360	tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
		361	tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF);
		362	}
		363
		364	result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
		365	result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
		366	result->v[2] = tmp[2][0] + ((tmp[2][1] + 0x8000) >> 16);
		367	}
		368
		369	PIXMAN_EXPORT void
1891	serge	370	pixman_transform_init_identity (struct pixman_transform *matrix)
		371	{
		372	int i;
		373
		374	memset (matrix, '\0', sizeof (struct pixman_transform));
		375	for (i = 0; i < 3; i++)
		376	matrix->matrix[i][i] = F (1);
		377	}
		378
		379	typedef pixman_fixed_32_32_t pixman_fixed_34_30_t;
		380
		381	PIXMAN_EXPORT pixman_bool_t
		382	pixman_transform_point_3d (const struct pixman_transform *transform,
		383	struct pixman_vector * vector)
		384	{
3931	Serge	385	pixman_vector_48_16_t tmp;
		386	tmp.v[0] = vector->vector[0];
		387	tmp.v[1] = vector->vector[1];
		388	tmp.v[2] = vector->vector[2];
1891	serge	389
3931	Serge	390	pixman_transform_point_31_16_3d (transform, &tmp, &tmp);
1891	serge	391
3931	Serge	392	vector->vector[0] = tmp.v[0];
		393	vector->vector[1] = tmp.v[1];
		394	vector->vector[2] = tmp.v[2];
1891	serge	395
3931	Serge	396	return vector->vector[0] == tmp.v[0] &&
		397	vector->vector[1] == tmp.v[1] &&
		398	vector->vector[2] == tmp.v[2];
1891	serge	399	}
		400
		401	PIXMAN_EXPORT pixman_bool_t
		402	pixman_transform_point (const struct pixman_transform *transform,
		403	struct pixman_vector * vector)
		404	{
3931	Serge	405	pixman_vector_48_16_t tmp;
		406	tmp.v[0] = vector->vector[0];
		407	tmp.v[1] = vector->vector[1];
		408	tmp.v[2] = vector->vector[2];
1891	serge	409
3931	Serge	410	if (!pixman_transform_point_31_16 (transform, &tmp, &tmp))
		411	return FALSE;
1891	serge	412
3931	Serge	413	vector->vector[0] = tmp.v[0];
		414	vector->vector[1] = tmp.v[1];
		415	vector->vector[2] = tmp.v[2];
		416
		417	return vector->vector[0] == tmp.v[0] &&
		418	vector->vector[1] == tmp.v[1] &&
		419	vector->vector[2] == tmp.v[2];
1891	serge	420	}
		421
		422	PIXMAN_EXPORT pixman_bool_t
		423	pixman_transform_multiply (struct pixman_transform * dst,
		424	const struct pixman_transform *l,
		425	const struct pixman_transform *r)
		426	{
		427	struct pixman_transform d;
		428	int dx, dy;
		429	int o;
		430
		431	for (dy = 0; dy < 3; dy++)
		432	{
		433	for (dx = 0; dx < 3; dx++)
		434	{
		435	pixman_fixed_48_16_t v;
		436	pixman_fixed_32_32_t partial;
		437
		438	v = 0;
		439	for (o = 0; o < 3; o++)
		440	{
		441	partial =
		442	(pixman_fixed_32_32_t) l->matrix[dy][o] *
		443	(pixman_fixed_32_32_t) r->matrix[o][dx];
		444
3931	Serge	445	v += (partial + 0x8000) >> 16;
1891	serge	446	}
		447
		448	if (v > pixman_max_fixed_48_16 \|\| v < pixman_min_fixed_48_16)
		449	return FALSE;
		450
		451	d.matrix[dy][dx] = (pixman_fixed_t) v;
		452	}
		453	}
		454
		455	*dst = d;
		456	return TRUE;
		457	}
		458
		459	PIXMAN_EXPORT void
		460	pixman_transform_init_scale (struct pixman_transform *t,
		461	pixman_fixed_t sx,
		462	pixman_fixed_t sy)
		463	{
		464	memset (t, '\0', sizeof (struct pixman_transform));
		465
		466	t->matrix[0][0] = sx;
		467	t->matrix[1][1] = sy;
		468	t->matrix[2][2] = F (1);
		469	}
		470
		471	static pixman_fixed_t
		472	fixed_inverse (pixman_fixed_t x)
		473	{
		474	return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F (1)) * F (1)) / x);
		475	}
		476
		477	PIXMAN_EXPORT pixman_bool_t
		478	pixman_transform_scale (struct pixman_transform *forward,
		479	struct pixman_transform *reverse,
		480	pixman_fixed_t sx,
		481	pixman_fixed_t sy)
		482	{
		483	struct pixman_transform t;
		484
		485	if (sx == 0 \|\| sy == 0)
		486	return FALSE;
		487
		488	if (forward)
		489	{
		490	pixman_transform_init_scale (&t, sx, sy);
		491	if (!pixman_transform_multiply (forward, &t, forward))
		492	return FALSE;
		493	}
		494
		495	if (reverse)
		496	{
		497	pixman_transform_init_scale (&t, fixed_inverse (sx),
		498	fixed_inverse (sy));
		499	if (!pixman_transform_multiply (reverse, reverse, &t))
		500	return FALSE;
		501	}
		502
		503	return TRUE;
		504	}
		505
		506	PIXMAN_EXPORT void
		507	pixman_transform_init_rotate (struct pixman_transform *t,
		508	pixman_fixed_t c,
		509	pixman_fixed_t s)
		510	{
		511	memset (t, '\0', sizeof (struct pixman_transform));
		512
		513	t->matrix[0][0] = c;
		514	t->matrix[0][1] = -s;
		515	t->matrix[1][0] = s;
		516	t->matrix[1][1] = c;
		517	t->matrix[2][2] = F (1);
		518	}
		519
		520	PIXMAN_EXPORT pixman_bool_t
		521	pixman_transform_rotate (struct pixman_transform *forward,
		522	struct pixman_transform *reverse,
		523	pixman_fixed_t c,
		524	pixman_fixed_t s)
		525	{
		526	struct pixman_transform t;
		527
		528	if (forward)
		529	{
		530	pixman_transform_init_rotate (&t, c, s);
		531	if (!pixman_transform_multiply (forward, &t, forward))
		532	return FALSE;
		533	}
		534
		535	if (reverse)
		536	{
		537	pixman_transform_init_rotate (&t, c, -s);
		538	if (!pixman_transform_multiply (reverse, reverse, &t))
		539	return FALSE;
		540	}
		541
		542	return TRUE;
		543	}
		544
		545	PIXMAN_EXPORT void
		546	pixman_transform_init_translate (struct pixman_transform *t,
		547	pixman_fixed_t tx,
		548	pixman_fixed_t ty)
		549	{
		550	memset (t, '\0', sizeof (struct pixman_transform));
		551
		552	t->matrix[0][0] = F (1);
		553	t->matrix[0][2] = tx;
		554	t->matrix[1][1] = F (1);
		555	t->matrix[1][2] = ty;
		556	t->matrix[2][2] = F (1);
		557	}
		558
		559	PIXMAN_EXPORT pixman_bool_t
		560	pixman_transform_translate (struct pixman_transform *forward,
		561	struct pixman_transform *reverse,
		562	pixman_fixed_t tx,
		563	pixman_fixed_t ty)
		564	{
		565	struct pixman_transform t;
		566
		567	if (forward)
		568	{
		569	pixman_transform_init_translate (&t, tx, ty);
		570
		571	if (!pixman_transform_multiply (forward, &t, forward))
		572	return FALSE;
		573	}
		574
		575	if (reverse)
		576	{
		577	pixman_transform_init_translate (&t, -tx, -ty);
		578
		579	if (!pixman_transform_multiply (reverse, reverse, &t))
		580	return FALSE;
		581	}
		582	return TRUE;
		583	}
		584
		585	PIXMAN_EXPORT pixman_bool_t
		586	pixman_transform_bounds (const struct pixman_transform *matrix,
		587	struct pixman_box16 * b)
		588
		589	{
		590	struct pixman_vector v[4];
		591	int i;
		592	int x1, y1, x2, y2;
		593
		594	v[0].vector[0] = F (b->x1);
		595	v[0].vector[1] = F (b->y1);
		596	v[0].vector[2] = F (1);
		597
		598	v[1].vector[0] = F (b->x2);
		599	v[1].vector[1] = F (b->y1);
		600	v[1].vector[2] = F (1);
		601
		602	v[2].vector[0] = F (b->x2);
		603	v[2].vector[1] = F (b->y2);
		604	v[2].vector[2] = F (1);
		605
		606	v[3].vector[0] = F (b->x1);
		607	v[3].vector[1] = F (b->y2);
		608	v[3].vector[2] = F (1);
		609
		610	for (i = 0; i < 4; i++)
		611	{
		612	if (!pixman_transform_point (matrix, &v[i]))
		613	return FALSE;
		614
		615	x1 = pixman_fixed_to_int (v[i].vector[0]);
		616	y1 = pixman_fixed_to_int (v[i].vector[1]);
		617	x2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[0]));
		618	y2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[1]));
		619
		620	if (i == 0)
		621	{
		622	b->x1 = x1;
		623	b->y1 = y1;
		624	b->x2 = x2;
		625	b->y2 = y2;
		626	}
		627	else
		628	{
		629	if (x1 < b->x1) b->x1 = x1;
		630	if (y1 < b->y1) b->y1 = y1;
		631	if (x2 > b->x2) b->x2 = x2;
		632	if (y2 > b->y2) b->y2 = y2;
		633	}
		634	}
		635
		636	return TRUE;
		637	}
		638
		639	PIXMAN_EXPORT pixman_bool_t
		640	pixman_transform_invert (struct pixman_transform * dst,
		641	const struct pixman_transform *src)
		642	{
3931	Serge	643	struct pixman_f_transform m;
1891	serge	644
		645	pixman_f_transform_from_pixman_transform (&m, src);
		646
3931	Serge	647	if (!pixman_f_transform_invert (&m, &m))
1891	serge	648	return FALSE;
		649
3931	Serge	650	if (!pixman_transform_from_pixman_f_transform (dst, &m))
1891	serge	651	return FALSE;
		652
		653	return TRUE;
		654	}
		655
		656	static pixman_bool_t
		657	within_epsilon (pixman_fixed_t a,
		658	pixman_fixed_t b,
		659	pixman_fixed_t epsilon)
		660	{
		661	pixman_fixed_t t = a - b;
		662
		663	if (t < 0)
		664	t = -t;
		665
		666	return t <= epsilon;
		667	}
		668
		669	#define EPSILON (pixman_fixed_t) (2)
		670
		671	#define IS_SAME(a, b) (within_epsilon (a, b, EPSILON))
		672	#define IS_ZERO(a) (within_epsilon (a, 0, EPSILON))
		673	#define IS_ONE(a) (within_epsilon (a, F (1), EPSILON))
		674	#define IS_UNIT(a) \
		675	(within_epsilon (a, F (1), EPSILON) \|\| \
		676	within_epsilon (a, F (-1), EPSILON) \|\| \
		677	IS_ZERO (a))
		678	#define IS_INT(a) (IS_ZERO (pixman_fixed_frac (a)))
		679
		680	PIXMAN_EXPORT pixman_bool_t
		681	pixman_transform_is_identity (const struct pixman_transform *t)
		682	{
		683	return (IS_SAME (t->matrix[0][0], t->matrix[1][1]) &&
		684	IS_SAME (t->matrix[0][0], t->matrix[2][2]) &&
		685	!IS_ZERO (t->matrix[0][0]) &&
		686	IS_ZERO (t->matrix[0][1]) &&
		687	IS_ZERO (t->matrix[0][2]) &&
		688	IS_ZERO (t->matrix[1][0]) &&
		689	IS_ZERO (t->matrix[1][2]) &&
		690	IS_ZERO (t->matrix[2][0]) &&
		691	IS_ZERO (t->matrix[2][1]));
		692	}
		693
		694	PIXMAN_EXPORT pixman_bool_t
		695	pixman_transform_is_scale (const struct pixman_transform *t)
		696	{
		697	return (!IS_ZERO (t->matrix[0][0]) &&
		698	IS_ZERO (t->matrix[0][1]) &&
		699	IS_ZERO (t->matrix[0][2]) &&
		700
		701	IS_ZERO (t->matrix[1][0]) &&
		702	!IS_ZERO (t->matrix[1][1]) &&
		703	IS_ZERO (t->matrix[1][2]) &&
		704
		705	IS_ZERO (t->matrix[2][0]) &&
		706	IS_ZERO (t->matrix[2][1]) &&
		707	!IS_ZERO (t->matrix[2][2]));
		708	}
		709
		710	PIXMAN_EXPORT pixman_bool_t
		711	pixman_transform_is_int_translate (const struct pixman_transform *t)
		712	{
		713	return (IS_ONE (t->matrix[0][0]) &&
		714	IS_ZERO (t->matrix[0][1]) &&
		715	IS_INT (t->matrix[0][2]) &&
		716
		717	IS_ZERO (t->matrix[1][0]) &&
		718	IS_ONE (t->matrix[1][1]) &&
		719	IS_INT (t->matrix[1][2]) &&
		720
		721	IS_ZERO (t->matrix[2][0]) &&
		722	IS_ZERO (t->matrix[2][1]) &&
		723	IS_ONE (t->matrix[2][2]));
		724	}
		725
		726	PIXMAN_EXPORT pixman_bool_t
		727	pixman_transform_is_inverse (const struct pixman_transform *a,
		728	const struct pixman_transform *b)
		729	{
		730	struct pixman_transform t;
		731
3931	Serge	732	if (!pixman_transform_multiply (&t, a, b))
		733	return FALSE;
1891	serge	734
		735	return pixman_transform_is_identity (&t);
		736	}
		737
		738	PIXMAN_EXPORT void
		739	pixman_f_transform_from_pixman_transform (struct pixman_f_transform * ft,
		740	const struct pixman_transform *t)
		741	{
		742	int i, j;
		743
		744	for (j = 0; j < 3; j++)
		745	{
		746	for (i = 0; i < 3; i++)
		747	ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]);
		748	}
		749	}
		750
		751	PIXMAN_EXPORT pixman_bool_t
		752	pixman_transform_from_pixman_f_transform (struct pixman_transform * t,
		753	const struct pixman_f_transform *ft)
		754	{
		755	int i, j;
		756
		757	for (j = 0; j < 3; j++)
		758	{
		759	for (i = 0; i < 3; i++)
		760	{
		761	double d = ft->m[j][i];
		762	if (d < -32767.0 \|\| d > 32767.0)
		763	return FALSE;
		764	d = d * 65536.0 + 0.5;
		765	t->matrix[j][i] = (pixman_fixed_t) floor (d);
		766	}
		767	}
		768
		769	return TRUE;
		770	}
		771
		772	PIXMAN_EXPORT pixman_bool_t
		773	pixman_f_transform_invert (struct pixman_f_transform * dst,
		774	const struct pixman_f_transform *src)
		775	{
3931	Serge	776	static const int a[3] = { 2, 2, 1 };
		777	static const int b[3] = { 1, 0, 0 };
		778	pixman_f_transform_t d;
1891	serge	779	double det;
		780	int i, j;
		781
		782	det = 0;
		783	for (i = 0; i < 3; i++)
		784	{
		785	double p;
		786	int ai = a[i];
		787	int bi = b[i];
		788	p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] -
		789	src->m[ai][1] * src->m[bi][2]);
		790	if (i == 1)
		791	p = -p;
		792	det += p;
		793	}
		794
		795	if (det == 0)
		796	return FALSE;
		797
		798	det = 1 / det;
		799	for (j = 0; j < 3; j++)
		800	{
		801	for (i = 0; i < 3; i++)
		802	{
		803	double p;
		804	int ai = a[i];
		805	int aj = a[j];
		806	int bi = b[i];
		807	int bj = b[j];
		808
		809	p = (src->m[ai][aj] * src->m[bi][bj] -
		810	src->m[ai][bj] * src->m[bi][aj]);
		811
		812	if (((i + j) & 1) != 0)
		813	p = -p;
		814
3931	Serge	815	d.m[j][i] = det * p;
1891	serge	816	}
		817	}
		818
3931	Serge	819	*dst = d;
		820
1891	serge	821	return TRUE;
		822	}
		823
		824	PIXMAN_EXPORT pixman_bool_t
		825	pixman_f_transform_point (const struct pixman_f_transform *t,
		826	struct pixman_f_vector * v)
		827	{
		828	struct pixman_f_vector result;
		829	int i, j;
		830	double a;
		831
		832	for (j = 0; j < 3; j++)
		833	{
		834	a = 0;
		835	for (i = 0; i < 3; i++)
		836	a += t->m[j][i] * v->v[i];
		837	result.v[j] = a;
		838	}
		839
		840	if (!result.v[2])
		841	return FALSE;
		842
		843	for (j = 0; j < 2; j++)
		844	v->v[j] = result.v[j] / result.v[2];
		845
		846	v->v[2] = 1;
		847
		848	return TRUE;
		849	}
		850
		851	PIXMAN_EXPORT void
		852	pixman_f_transform_point_3d (const struct pixman_f_transform *t,
		853	struct pixman_f_vector * v)
		854	{
		855	struct pixman_f_vector result;
		856	int i, j;
		857	double a;
		858
		859	for (j = 0; j < 3; j++)
		860	{
		861	a = 0;
		862	for (i = 0; i < 3; i++)
		863	a += t->m[j][i] * v->v[i];
		864	result.v[j] = a;
		865	}
		866
		867	*v = result;
		868	}
		869
		870	PIXMAN_EXPORT void
		871	pixman_f_transform_multiply (struct pixman_f_transform * dst,
		872	const struct pixman_f_transform *l,
		873	const struct pixman_f_transform *r)
		874	{
		875	struct pixman_f_transform d;
		876	int dx, dy;
		877	int o;
		878
		879	for (dy = 0; dy < 3; dy++)
		880	{
		881	for (dx = 0; dx < 3; dx++)
		882	{
		883	double v = 0;
		884	for (o = 0; o < 3; o++)
		885	v += l->m[dy][o] * r->m[o][dx];
		886	d.m[dy][dx] = v;
		887	}
		888	}
		889
		890	*dst = d;
		891	}
		892
		893	PIXMAN_EXPORT void
		894	pixman_f_transform_init_scale (struct pixman_f_transform *t,
		895	double sx,
		896	double sy)
		897	{
		898	t->m[0][0] = sx;
		899	t->m[0][1] = 0;
		900	t->m[0][2] = 0;
		901	t->m[1][0] = 0;
		902	t->m[1][1] = sy;
		903	t->m[1][2] = 0;
		904	t->m[2][0] = 0;
		905	t->m[2][1] = 0;
		906	t->m[2][2] = 1;
		907	}
		908
		909	PIXMAN_EXPORT pixman_bool_t
		910	pixman_f_transform_scale (struct pixman_f_transform *forward,
		911	struct pixman_f_transform *reverse,
		912	double sx,
		913	double sy)
		914	{
		915	struct pixman_f_transform t;
		916
		917	if (sx == 0 \|\| sy == 0)
		918	return FALSE;
		919
		920	if (forward)
		921	{
		922	pixman_f_transform_init_scale (&t, sx, sy);
		923	pixman_f_transform_multiply (forward, &t, forward);
		924	}
		925
		926	if (reverse)
		927	{
		928	pixman_f_transform_init_scale (&t, 1 / sx, 1 / sy);
		929	pixman_f_transform_multiply (reverse, reverse, &t);
		930	}
		931
		932	return TRUE;
		933	}
		934
		935	PIXMAN_EXPORT void
		936	pixman_f_transform_init_rotate (struct pixman_f_transform *t,
		937	double c,
		938	double s)
		939	{
		940	t->m[0][0] = c;
		941	t->m[0][1] = -s;
		942	t->m[0][2] = 0;
		943	t->m[1][0] = s;
		944	t->m[1][1] = c;
		945	t->m[1][2] = 0;
		946	t->m[2][0] = 0;
		947	t->m[2][1] = 0;
		948	t->m[2][2] = 1;
		949	}
		950
		951	PIXMAN_EXPORT pixman_bool_t
		952	pixman_f_transform_rotate (struct pixman_f_transform *forward,
		953	struct pixman_f_transform *reverse,
		954	double c,
		955	double s)
		956	{
		957	struct pixman_f_transform t;
		958
		959	if (forward)
		960	{
		961	pixman_f_transform_init_rotate (&t, c, s);
		962	pixman_f_transform_multiply (forward, &t, forward);
		963	}
		964
		965	if (reverse)
		966	{
		967	pixman_f_transform_init_rotate (&t, c, -s);
		968	pixman_f_transform_multiply (reverse, reverse, &t);
		969	}
		970
		971	return TRUE;
		972	}
		973
		974	PIXMAN_EXPORT void
		975	pixman_f_transform_init_translate (struct pixman_f_transform *t,
		976	double tx,
		977	double ty)
		978	{
		979	t->m[0][0] = 1;
		980	t->m[0][1] = 0;
		981	t->m[0][2] = tx;
		982	t->m[1][0] = 0;
		983	t->m[1][1] = 1;
		984	t->m[1][2] = ty;
		985	t->m[2][0] = 0;
		986	t->m[2][1] = 0;
		987	t->m[2][2] = 1;
		988	}
		989
		990	PIXMAN_EXPORT pixman_bool_t
		991	pixman_f_transform_translate (struct pixman_f_transform *forward,
		992	struct pixman_f_transform *reverse,
		993	double tx,
		994	double ty)
		995	{
		996	struct pixman_f_transform t;
		997
		998	if (forward)
		999	{
		1000	pixman_f_transform_init_translate (&t, tx, ty);
		1001	pixman_f_transform_multiply (forward, &t, forward);
		1002	}
		1003
		1004	if (reverse)
		1005	{
		1006	pixman_f_transform_init_translate (&t, -tx, -ty);
		1007	pixman_f_transform_multiply (reverse, reverse, &t);
		1008	}
		1009
		1010	return TRUE;
		1011	}
		1012
		1013	PIXMAN_EXPORT pixman_bool_t
		1014	pixman_f_transform_bounds (const struct pixman_f_transform *t,
		1015	struct pixman_box16 * b)
		1016	{
		1017	struct pixman_f_vector v[4];
		1018	int i;
		1019	int x1, y1, x2, y2;
		1020
		1021	v[0].v[0] = b->x1;
		1022	v[0].v[1] = b->y1;
		1023	v[0].v[2] = 1;
		1024	v[1].v[0] = b->x2;
		1025	v[1].v[1] = b->y1;
		1026	v[1].v[2] = 1;
		1027	v[2].v[0] = b->x2;
		1028	v[2].v[1] = b->y2;
		1029	v[2].v[2] = 1;
		1030	v[3].v[0] = b->x1;
		1031	v[3].v[1] = b->y2;
		1032	v[3].v[2] = 1;
		1033
		1034	for (i = 0; i < 4; i++)
		1035	{
		1036	if (!pixman_f_transform_point (t, &v[i]))
		1037	return FALSE;
		1038
		1039	x1 = floor (v[i].v[0]);
		1040	y1 = floor (v[i].v[1]);
		1041	x2 = ceil (v[i].v[0]);
		1042	y2 = ceil (v[i].v[1]);
		1043
		1044	if (i == 0)
		1045	{
		1046	b->x1 = x1;
		1047	b->y1 = y1;
		1048	b->x2 = x2;
		1049	b->y2 = y2;
		1050	}
		1051	else
		1052	{
		1053	if (x1 < b->x1) b->x1 = x1;
		1054	if (y1 < b->y1) b->y1 = y1;
		1055	if (x2 > b->x2) b->x2 = x2;
		1056	if (y2 > b->y2) b->y2 = y2;
		1057	}
		1058	}
		1059
		1060	return TRUE;
		1061	}
		1062
		1063	PIXMAN_EXPORT void
		1064	pixman_f_transform_init_identity (struct pixman_f_transform *t)
		1065	{
		1066	int i, j;
		1067
		1068	for (j = 0; j < 3; j++)
		1069	{
		1070	for (i = 0; i < 3; i++)
		1071	t->m[j][i] = i == j ? 1 : 0;
		1072	}
		1073	}

Subversion Repositories Kolibri OS

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