pixman/pixman-matrix.c - third_party/pixman - Git at Google

 /*
  * Copyright © 2008 Keith Packard
  *
  * Permission to use, copy, modify, distribute, and sell this software and its
  * documentation for any purpose is hereby granted without fee, provided that
  * the above copyright notice appear in all copies and that both that copyright
  * notice and this permission notice appear in supporting documentation, and
  * that the name of the copyright holders not be used in advertising or
  * publicity pertaining to distribution of the software without specific,
  * written prior permission.  The copyright holders make no representations
  * about the suitability of this software for any purpose.  It is provided "as
  * is" without express or implied warranty.
  *
  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
  * OF THIS SOFTWARE.
  */

 /*
  * Matrix interfaces
  */

 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif

 #include <math.h>
 #include <string.h>
 #include "pixman-private.h"

 #define F(x)	pixman_int_to_fixed(x)

 PIXMAN_EXPORT void
 pixman_transform_init_identity(struct pixman_transform *matrix)
 {
 	int	i;

 	memset(matrix, '\0', sizeof (struct pixman_transform));
 	for (i = 0; i < 3; i++)
 		matrix->matrix[i][i] = F(1);
 }

 typedef pixman_fixed_32_32_t	pixman_fixed_34_30_t;

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_point_3d(const struct pixman_transform *transform,
 			  struct pixman_vector *vector)
 {
 	struct pixman_vector result;
 	pixman_fixed_32_32_t partial;
 	pixman_fixed_48_16_t v;
 	int i, j;

 	for (j = 0; j < 3; j++)
 	{
 		v = 0;
 		for (i = 0; i < 3; i++)
 		{
 			partial = ((pixman_fixed_48_16_t) transform->matrix[j][i] *
 				   (pixman_fixed_48_16_t) vector->vector[i]);
 			v += partial >> 16;
 		}
 		if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
 			return FALSE;
 		result.vector[j] = (pixman_fixed_t) v;
 	}
 	*vector = result;
 	if (!result.vector[2])
 		return FALSE;
 	return TRUE;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_point(const struct pixman_transform *transform,
 		       struct pixman_vector *vector)
 {
 	pixman_fixed_32_32_t partial;
 	pixman_fixed_34_30_t v[3];
 	pixman_fixed_48_16_t quo;
 	int i, j;

 	for (j = 0; j < 3; j++)
 	{
 		v[j] = 0;
 		for (i = 0; i < 3; i++)
 		{
 			partial = ((pixman_fixed_32_32_t) transform->matrix[j][i] *
 				   (pixman_fixed_32_32_t) vector->vector[i]);
 			v[j] += partial >> 2;
 		}
 	}
 	if (!(v[2] >> 16))
 		return FALSE;
 	for (j = 0; j < 2; j++)
 	{
 		quo = v[j] / (v[2] >> 16);
 		if (quo > pixman_max_fixed_48_16 || quo < pixman_min_fixed_48_16)
 			return FALSE;
 		vector->vector[j] = (pixman_fixed_t) quo;
 	}
 	vector->vector[2] = pixman_fixed_1;
 	return TRUE;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_multiply (struct pixman_transform *dst,
 			   const struct pixman_transform *l,
 			   const struct pixman_transform *r)
 {
 	struct pixman_transform d;
 	int dx, dy;
 	int o;

 	for (dy = 0; dy < 3; dy++)
 		for (dx = 0; dx < 3; dx++) {
 			pixman_fixed_48_16_t    v;
 			pixman_fixed_32_32_t    partial;
 			v = 0;
 			for (o = 0; o < 3; o++) {
 				partial = (pixman_fixed_32_32_t) l->matrix[dy][o] * (pixman_fixed_32_32_t) r->matrix[o][dx];
 				v += partial >> 16;
 			}
 			if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
 				return FALSE;
 			d.matrix[dy][dx] = (pixman_fixed_t) v;
 		}
 	*dst = d;
 	return TRUE;
 }

 PIXMAN_EXPORT void
 pixman_transform_init_scale (struct pixman_transform *t,
 			     pixman_fixed_t sx,
 			     pixman_fixed_t sy)
 {
 	memset (t, '\0', sizeof (struct pixman_transform));
 	t->matrix[0][0] = sx;
 	t->matrix[1][1] = sy;
 	t->matrix[2][2] = F (1);
 }

 static pixman_fixed_t
 fixed_inverse(pixman_fixed_t x)
 {
 	return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F(1)) * F(1)) / x);
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_scale(struct pixman_transform *forward,
 		       struct pixman_transform *reverse,
 		       pixman_fixed_t sx, pixman_fixed_t sy)
 {
 	struct pixman_transform   t;

 	if (sx == 0 || sy == 0)
 		return FALSE;

 	if (forward) {
 		pixman_transform_init_scale (&t, sx, sy);
 		if (!pixman_transform_multiply (forward, &t, forward))
 			return FALSE;
 	}
 	if (reverse) {
 		pixman_transform_init_scale (&t, fixed_inverse (sx),
 					     fixed_inverse (sy));
 		if (!pixman_transform_multiply (reverse, reverse, &t))
 			return FALSE;
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT void
 pixman_transform_init_rotate(struct pixman_transform *t,
 			     pixman_fixed_t c,
 			     pixman_fixed_t s)
 {
 	memset(t, '\0', sizeof (struct pixman_transform));
 	t->matrix[0][0] = c;
 	t->matrix[0][1] = -s;
 	t->matrix[1][0] = s;
 	t->matrix[1][1] = c;
 	t->matrix[2][2] = F (1);
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_rotate(struct pixman_transform *forward,
 			struct pixman_transform *reverse,
 			pixman_fixed_t c, pixman_fixed_t s)
 {
 	struct pixman_transform   t;

 	if (forward) {
 		pixman_transform_init_rotate(&t, c, s);
 		if (!pixman_transform_multiply(forward, &t, forward))
 			return FALSE;
 	}

 	if (reverse) {
 		pixman_transform_init_rotate(&t, c, -s);
 		if (!pixman_transform_multiply (reverse, reverse, &t))
 			return FALSE;
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT void
 pixman_transform_init_translate(struct pixman_transform *t,
 				pixman_fixed_t tx, pixman_fixed_t ty)
 {
 	memset(t, '\0', sizeof (struct pixman_transform));
 	t->matrix[0][0] = F (1);
 	t->matrix[0][2] = tx;
 	t->matrix[1][1] = F (1);
 	t->matrix[1][2] = ty;
 	t->matrix[2][2] = F (1);
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_translate(struct pixman_transform *forward,
 			   struct pixman_transform *reverse,
 			   pixman_fixed_t tx, pixman_fixed_t ty)
 {
 	struct pixman_transform   t;

 	if (forward) {
 		pixman_transform_init_translate(&t, tx, ty);
 		if (!pixman_transform_multiply(forward, &t, forward))
 			return FALSE;
 	}

 	if (reverse) {
 		pixman_transform_init_translate(&t, -tx, -ty);
 		if (!pixman_transform_multiply(reverse, reverse, &t))
 			return FALSE;
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_bounds(const struct pixman_transform *matrix,
 			struct pixman_box16 *b)

 {
 	struct pixman_vector v[4];
 	int i;
 	int x1, y1, x2, y2;

 	v[0].vector[0] = F (b->x1);    v[0].vector[1] = F (b->y1);	v[0].vector[2] = F(1);
 	v[1].vector[0] = F (b->x2);    v[1].vector[1] = F (b->y1);	v[1].vector[2] = F(1);
 	v[2].vector[0] = F (b->x2);    v[2].vector[1] = F (b->y2);	v[2].vector[2] = F(1);
 	v[3].vector[0] = F (b->x1);    v[3].vector[1] = F (b->y2);	v[3].vector[2] = F(1);
 	for (i = 0; i < 4; i++)
 	{
 		if (!pixman_transform_point(matrix, &v[i]))
 			return FALSE;
 		x1 = pixman_fixed_to_int(v[i].vector[0]);
 		y1 = pixman_fixed_to_int(v[i].vector[1]);
 		x2 = pixman_fixed_to_int(pixman_fixed_ceil (v[i].vector[0]));
 		y2 = pixman_fixed_to_int(pixman_fixed_ceil (v[i].vector[1]));
 		if (i == 0)
 		{
 			b->x1 = x1; b->y1 = y1;
 			b->x2 = x2; b->y2 = y2;
 		}
 		else
 		{
 			if (x1 < b->x1) b->x1 = x1;
 			if (y1 < b->y1) b->y1 = y1;
 			if (x2 > b->x2) b->x2 = x2;
 			if (y2 > b->y2) b->y2 = y2;
 		}
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_invert (struct pixman_transform *dst,
 			 const struct pixman_transform *src)
 {
 	struct pixman_f_transform m, r;

 	pixman_f_transform_from_pixman_transform (&m, src);
 	if (!pixman_f_transform_invert (&r, &m))
 		return FALSE;
 	if (!pixman_transform_from_pixman_f_transform (dst, &r))
 		return FALSE;
 	return TRUE;
 }

 static pixman_bool_t
 within_epsilon(pixman_fixed_t a, pixman_fixed_t b, pixman_fixed_t epsilon)
 {
 	pixman_fixed_t  t = a - b;
 	if (t < 0) t = -t;
 	return t <= epsilon;
 }

 #define epsilon	(pixman_fixed_t) (2)

 #define is_same(a,b) (within_epsilon(a, b, epsilon))
 #define is_zero(a)   (within_epsilon(a, 0, epsilon))
 #define is_one(a)    (within_epsilon(a, F(1), epsilon))
 #define is_unit(a)   (within_epsilon(a, F( 1), epsilon) || \
 		      within_epsilon(a, F(-1), epsilon) || \
 		      is_zero(a))
 #define is_int(a)    (is_zero(pixman_fixed_frac(a)))

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_is_identity(const struct pixman_transform *t)
 {
 	return ( is_same(t->matrix[0][0], t->matrix[1][1]) &&
 		 is_same(t->matrix[0][0], t->matrix[2][2]) &&
 		!is_zero(t->matrix[0][0]) &&
 		 is_zero(t->matrix[0][1]) &&
 		 is_zero(t->matrix[0][2]) &&
 		 is_zero(t->matrix[1][0]) &&
 		 is_zero(t->matrix[1][2]) &&
 		 is_zero(t->matrix[2][0]) &&
 		 is_zero(t->matrix[2][1]));
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_is_scale(const struct pixman_transform *t)
 {
 	return (!is_zero(t->matrix[0][0]) &&
 		 is_zero(t->matrix[0][1]) &&
 		 is_zero(t->matrix[0][2]) &&

 		 is_zero(t->matrix[1][0]) &&
 		!is_zero(t->matrix[1][1]) &&
 		 is_zero(t->matrix[1][2]) &&

 		 is_zero(t->matrix[2][0]) &&
 		 is_zero(t->matrix[2][1]) &&
 		!is_zero(t->matrix[2][2]));
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_is_int_translate(const struct pixman_transform *t)
 {
 	return (is_one (t->matrix[0][0]) &&
 		is_zero(t->matrix[0][1]) &&
 		is_int (t->matrix[0][2]) &&

 		is_zero(t->matrix[1][0]) &&
 		is_one (t->matrix[1][1]) &&
 		is_int (t->matrix[1][2]) &&

 		is_zero(t->matrix[2][0]) &&
 		is_zero(t->matrix[2][1]) &&
 		is_one (t->matrix[2][2]));
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_is_inverse(const struct pixman_transform *a,
 			    const struct pixman_transform *b)
 {
 	struct pixman_transform   t;

 	pixman_transform_multiply(&t, a, b);
 	return pixman_transform_is_identity(&t);
 }

 PIXMAN_EXPORT void
 pixman_f_transform_from_pixman_transform (struct pixman_f_transform *ft,
 					  const struct pixman_transform *t)
 {
 	int	i, j;

 	for (j = 0; j < 3; j++)
 		for (i = 0; i < 3; i++)
 			ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]);
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_transform_from_pixman_f_transform (struct pixman_transform *t,
 					  const struct pixman_f_transform *ft)
 {
 	int	i, j;

 	for (j = 0; j < 3; j++)
 		for (i = 0; i < 3; i++)
 		{
 			double  d = ft->m[j][i];
 			if (d < -32767.0 || d > 32767.0)
 				return FALSE;
 			d = d * 65536.0 + 0.5;
 			t->matrix[j][i] = (pixman_fixed_t) floor (d);
 		}
 	return TRUE;
 }

 static const int	a[3] = { 3, 3, 2 };
 static const int	b[3] = { 2, 1, 1 };

 PIXMAN_EXPORT pixman_bool_t
 pixman_f_transform_invert(struct pixman_f_transform *dst,
 			  const struct pixman_f_transform *src)
 {
 	double  det;
 	int	    i, j;
 	static int	a[3] = { 2, 2, 1 };
 	static int	b[3] = { 1, 0, 0 };

 	det = 0;
 	for (i = 0; i < 3; i++) {
 		double	p;
 		int	ai = a[i];
 		int	bi = b[i];
 		p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] -
 				    src->m[ai][1] * src->m[bi][2]);
 		if (i == 1)
 			p = -p;
 		det += p;
 	}
 	if (det == 0)
 		return FALSE;
 	det = 1/det;
 	for (j = 0; j < 3; j++) {
 		for (i = 0; i < 3; i++) {
 			double  p;
 			int	    ai = a[i];
 			int	    aj = a[j];
 			int	    bi = b[i];
 			int	    bj = b[j];

 			p = (src->m[ai][aj] * src->m[bi][bj] -
 			     src->m[ai][bj] * src->m[bi][aj]);
 			if (((i + j) & 1) != 0)
 				p = -p;
 			dst->m[j][i] = det * p;
 		}
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_f_transform_point(const struct pixman_f_transform *t,
 			 struct pixman_f_vector *v)
 {
 	struct pixman_f_vector    result;
 	int			    i, j;
 	double		    a;

 	for (j = 0; j < 3; j++)
 	{
 		a = 0;
 		for (i = 0; i < 3; i++)
 			a += t->m[j][i] * v->v[i];
 		result.v[j] = a;
 	}
 	if (!result.v[2])
 		return FALSE;
 	for (j = 0; j < 2; j++)
 		v->v[j] = result.v[j] / result.v[2];
 	v->v[2] = 1;
 	return TRUE;
 }

 PIXMAN_EXPORT void
 pixman_f_transform_point_3d(const struct pixman_f_transform *t,
 			    struct pixman_f_vector *v)
 {
 	struct pixman_f_vector    result;
 	int			    i, j;
 	double		    a;

 	for (j = 0; j < 3; j++)
 	{
 		a = 0;
 		for (i = 0; i < 3; i++)
 			a += t->m[j][i] * v->v[i];
 		result.v[j] = a;
 	}
 	*v = result;
 }

 PIXMAN_EXPORT void
 pixman_f_transform_multiply(struct pixman_f_transform *dst,
 			    const struct pixman_f_transform *l,
 			    const struct pixman_f_transform *r)
 {
 	struct pixman_f_transform d;
 	int			    dx, dy;
 	int			    o;

 	for (dy = 0; dy < 3; dy++)
 		for (dx = 0; dx < 3; dx++)
 		{
 			double v = 0;
 			for (o = 0; o < 3; o++)
 				v += l->m[dy][o] * r->m[o][dx];
 			d.m[dy][dx] = v;
 		}
 	*dst = d;
 }

 PIXMAN_EXPORT void
 pixman_f_transform_init_scale (struct pixman_f_transform *t, double sx, double sy)
 {
 	t->m[0][0] = sx;	t->m[0][1] = 0;	    t->m[0][2] = 0;
 	t->m[1][0] = 0;	t->m[1][1] = sy;    t->m[1][2] = 0;
 	t->m[2][0] = 0;	t->m[2][1] = 0;	    t->m[2][2] = 1;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_f_transform_scale (struct pixman_f_transform *forward,
 			  struct pixman_f_transform *reverse,
 			  double sx, double sy)
 {
 	struct pixman_f_transform t;

 	if (sx == 0 || sy == 0)
 		return FALSE;

 	if (forward) {
 		pixman_f_transform_init_scale (&t, sx, sy);
 		pixman_f_transform_multiply (forward, &t, forward);
 	}
 	if (reverse) {
 		pixman_f_transform_init_scale (&t, 1/sx, 1/sy);
 		pixman_f_transform_multiply (reverse, reverse, &t);
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT void
 pixman_f_transform_init_rotate (struct pixman_f_transform *t, double c, double s)
 {
 	t->m[0][0] = c;	t->m[0][1] = -s;    t->m[0][2] = 0;
 	t->m[1][0] = s;	t->m[1][1] = c;	    t->m[1][2] = 0;
 	t->m[2][0] = 0;	t->m[2][1] = 0;	    t->m[2][2] = 1;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_f_transform_rotate (struct pixman_f_transform *forward,
 			   struct pixman_f_transform *reverse,
 			   double c, double s)
 {
 	struct pixman_f_transform t;

 	if (forward) {
 		pixman_f_transform_init_rotate (&t, c, s);
 		pixman_f_transform_multiply (forward, &t, forward);
 	}
 	if (reverse) {
 		pixman_f_transform_init_rotate (&t, c, -s);
 		pixman_f_transform_multiply (reverse, reverse, &t);
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT void
 pixman_f_transform_init_translate (struct pixman_f_transform *t, double tx, double ty)
 {
 	t->m[0][0] = 1;	t->m[0][1] = 0;	    t->m[0][2] = tx;
 	t->m[1][0] = 0;	t->m[1][1] = 1;	    t->m[1][2] = ty;
 	t->m[2][0] = 0;	t->m[2][1] = 0;	    t->m[2][2] = 1;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_f_transform_translate (struct pixman_f_transform *forward,
 			      struct pixman_f_transform *reverse,
 			      double tx, double ty)
 {
 	struct pixman_f_transform t;

 	if (forward) {
 		pixman_f_transform_init_translate (&t, tx, ty);
 		pixman_f_transform_multiply (forward, &t, forward);
 	}
 	if (reverse) {
 		pixman_f_transform_init_translate (&t, -tx, -ty);
 		pixman_f_transform_multiply (reverse, reverse, &t);
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT pixman_bool_t
 pixman_f_transform_bounds(const struct pixman_f_transform *t, struct pixman_box16 *b)
 {
 	struct pixman_f_vector    v[4];
 	int			    i;
 	int			    x1, y1, x2, y2;

 	v[0].v[0] = b->x1;    v[0].v[1] = b->y1;	v[0].v[2] = 1;
 	v[1].v[0] = b->x2;    v[1].v[1] = b->y1;	v[1].v[2] = 1;
 	v[2].v[0] = b->x2;    v[2].v[1] = b->y2;	v[2].v[2] = 1;
 	v[3].v[0] = b->x1;    v[3].v[1] = b->y2;	v[3].v[2] = 1;
 	for (i = 0; i < 4; i++)
 	{
 		if (!pixman_f_transform_point (t, &v[i]))
 			return FALSE;
 		x1 = floor (v[i].v[0]);
 		y1 = floor (v[i].v[1]);
 		x2 = ceil (v[i].v[0]);
 		y2 = ceil (v[i].v[1]);
 		if (i == 0)
 		{
 			b->x1 = x1; b->y1 = y1;
 			b->x2 = x2; b->y2 = y2;
 		}
 		else
 		{
 			if (x1 < b->x1) b->x1 = x1;
 			if (y1 < b->y1) b->y1 = y1;
 			if (x2 > b->x2) b->x2 = x2;
 			if (y2 > b->y2) b->y2 = y2;
 		}
 	}
 	return TRUE;
 }

 PIXMAN_EXPORT void
 pixman_f_transform_init_identity (struct pixman_f_transform *t)
 {
 	int	i, j;

 	for (j = 0; j < 3; j++)
 		for (i = 0; i < 3; i++)
 			t->m[j][i] = i == j ? 1 : 0;
 }
	/*
	* Copyright © 2008 Keith Packard
	*
	* Permission to use, copy, modify, distribute, and sell this software and its
	* documentation for any purpose is hereby granted without fee, provided that
	* the above copyright notice appear in all copies and that both that copyright
	* notice and this permission notice appear in supporting documentation, and
	* that the name of the copyright holders not be used in advertising or
	* publicity pertaining to distribution of the software without specific,
	* written prior permission. The copyright holders make no representations
	* about the suitability of this software for any purpose. It is provided "as
	* is" without express or implied warranty.
	*
	* THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
	* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
	* EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
	* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
	* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
	* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
	* OF THIS SOFTWARE.
	*/

	/*
	* Matrix interfaces
	*/

	#ifdef HAVE_CONFIG_H
	#include "config.h"
	#endif

	#include <math.h>
	#include <string.h>
	#include "pixman-private.h"

	#define F(x) pixman_int_to_fixed(x)

	PIXMAN_EXPORT void
	pixman_transform_init_identity(struct pixman_transform *matrix)
	{
	int i;

	memset(matrix, '\0', sizeof (struct pixman_transform));
	for (i = 0; i < 3; i++)
	matrix->matrix[i][i] = F(1);
	}

	typedef pixman_fixed_32_32_t pixman_fixed_34_30_t;

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_point_3d(const struct pixman_transform *transform,
	struct pixman_vector *vector)
	{
	struct pixman_vector result;
	pixman_fixed_32_32_t partial;
	pixman_fixed_48_16_t v;
	int i, j;

	for (j = 0; j < 3; j++)
	{
	v = 0;
	for (i = 0; i < 3; i++)
	{
	partial = ((pixman_fixed_48_16_t) transform->matrix[j][i] *
	(pixman_fixed_48_16_t) vector->vector[i]);
	v += partial >> 16;
	}
	if (v > pixman_max_fixed_48_16 \|\| v < pixman_min_fixed_48_16)
	return FALSE;
	result.vector[j] = (pixman_fixed_t) v;
	}
	*vector = result;
	if (!result.vector[2])
	return FALSE;
	return TRUE;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_point(const struct pixman_transform *transform,
	struct pixman_vector *vector)
	{
	pixman_fixed_32_32_t partial;
	pixman_fixed_34_30_t v[3];
	pixman_fixed_48_16_t quo;
	int i, j;

	for (j = 0; j < 3; j++)
	{
	v[j] = 0;
	for (i = 0; i < 3; i++)
	{
	partial = ((pixman_fixed_32_32_t) transform->matrix[j][i] *
	(pixman_fixed_32_32_t) vector->vector[i]);
	v[j] += partial >> 2;
	}
	}
	if (!(v[2] >> 16))
	return FALSE;
	for (j = 0; j < 2; j++)
	{
	quo = v[j] / (v[2] >> 16);
	if (quo > pixman_max_fixed_48_16 \|\| quo < pixman_min_fixed_48_16)
	return FALSE;
	vector->vector[j] = (pixman_fixed_t) quo;
	}
	vector->vector[2] = pixman_fixed_1;
	return TRUE;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_multiply (struct pixman_transform *dst,
	const struct pixman_transform *l,
	const struct pixman_transform *r)
	{
	struct pixman_transform d;
	int dx, dy;
	int o;

	for (dy = 0; dy < 3; dy++)
	for (dx = 0; dx < 3; dx++) {
	pixman_fixed_48_16_t v;
	pixman_fixed_32_32_t partial;
	v = 0;
	for (o = 0; o < 3; o++) {
	partial = (pixman_fixed_32_32_t) l->matrix[dy][o] * (pixman_fixed_32_32_t) r->matrix[o][dx];
	v += partial >> 16;
	}
	if (v > pixman_max_fixed_48_16 \|\| v < pixman_min_fixed_48_16)
	return FALSE;
	d.matrix[dy][dx] = (pixman_fixed_t) v;
	}
	*dst = d;
	return TRUE;
	}

	PIXMAN_EXPORT void
	pixman_transform_init_scale (struct pixman_transform *t,
	pixman_fixed_t sx,
	pixman_fixed_t sy)
	{
	memset (t, '\0', sizeof (struct pixman_transform));
	t->matrix[0][0] = sx;
	t->matrix[1][1] = sy;
	t->matrix[2][2] = F (1);
	}

	static pixman_fixed_t
	fixed_inverse(pixman_fixed_t x)
	{
	return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F(1)) * F(1)) / x);
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_scale(struct pixman_transform *forward,
	struct pixman_transform *reverse,
	pixman_fixed_t sx, pixman_fixed_t sy)
	{
	struct pixman_transform t;

	if (sx == 0 \|\| sy == 0)
	return FALSE;

	if (forward) {
	pixman_transform_init_scale (&t, sx, sy);
	if (!pixman_transform_multiply (forward, &t, forward))
	return FALSE;
	}
	if (reverse) {
	pixman_transform_init_scale (&t, fixed_inverse (sx),
	fixed_inverse (sy));
	if (!pixman_transform_multiply (reverse, reverse, &t))
	return FALSE;
	}
	return TRUE;
	}

	PIXMAN_EXPORT void
	pixman_transform_init_rotate(struct pixman_transform *t,
	pixman_fixed_t c,
	pixman_fixed_t s)
	{
	memset(t, '\0', sizeof (struct pixman_transform));
	t->matrix[0][0] = c;
	t->matrix[0][1] = -s;
	t->matrix[1][0] = s;
	t->matrix[1][1] = c;
	t->matrix[2][2] = F (1);
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_rotate(struct pixman_transform *forward,
	struct pixman_transform *reverse,
	pixman_fixed_t c, pixman_fixed_t s)
	{
	struct pixman_transform t;

	if (forward) {
	pixman_transform_init_rotate(&t, c, s);
	if (!pixman_transform_multiply(forward, &t, forward))
	return FALSE;
	}

	if (reverse) {
	pixman_transform_init_rotate(&t, c, -s);
	if (!pixman_transform_multiply (reverse, reverse, &t))
	return FALSE;
	}
	return TRUE;
	}

	PIXMAN_EXPORT void
	pixman_transform_init_translate(struct pixman_transform *t,
	pixman_fixed_t tx, pixman_fixed_t ty)
	{
	memset(t, '\0', sizeof (struct pixman_transform));
	t->matrix[0][0] = F (1);
	t->matrix[0][2] = tx;
	t->matrix[1][1] = F (1);
	t->matrix[1][2] = ty;
	t->matrix[2][2] = F (1);
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_translate(struct pixman_transform *forward,
	struct pixman_transform *reverse,
	pixman_fixed_t tx, pixman_fixed_t ty)
	{
	struct pixman_transform t;

	if (forward) {
	pixman_transform_init_translate(&t, tx, ty);
	if (!pixman_transform_multiply(forward, &t, forward))
	return FALSE;
	}

	if (reverse) {
	pixman_transform_init_translate(&t, -tx, -ty);
	if (!pixman_transform_multiply(reverse, reverse, &t))
	return FALSE;
	}
	return TRUE;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_bounds(const struct pixman_transform *matrix,
	struct pixman_box16 *b)

	{
	struct pixman_vector v[4];
	int i;
	int x1, y1, x2, y2;

	v[0].vector[0] = F (b->x1); v[0].vector[1] = F (b->y1); v[0].vector[2] = F(1);
	v[1].vector[0] = F (b->x2); v[1].vector[1] = F (b->y1); v[1].vector[2] = F(1);
	v[2].vector[0] = F (b->x2); v[2].vector[1] = F (b->y2); v[2].vector[2] = F(1);
	v[3].vector[0] = F (b->x1); v[3].vector[1] = F (b->y2); v[3].vector[2] = F(1);
	for (i = 0; i < 4; i++)
	{
	if (!pixman_transform_point(matrix, &v[i]))
	return FALSE;
	x1 = pixman_fixed_to_int(v[i].vector[0]);
	y1 = pixman_fixed_to_int(v[i].vector[1]);
	x2 = pixman_fixed_to_int(pixman_fixed_ceil (v[i].vector[0]));
	y2 = pixman_fixed_to_int(pixman_fixed_ceil (v[i].vector[1]));
	if (i == 0)
	{
	b->x1 = x1; b->y1 = y1;
	b->x2 = x2; b->y2 = y2;
	}
	else
	{
	if (x1 < b->x1) b->x1 = x1;
	if (y1 < b->y1) b->y1 = y1;
	if (x2 > b->x2) b->x2 = x2;
	if (y2 > b->y2) b->y2 = y2;
	}
	}
	return TRUE;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_invert (struct pixman_transform *dst,
	const struct pixman_transform *src)
	{
	struct pixman_f_transform m, r;

	pixman_f_transform_from_pixman_transform (&m, src);
	if (!pixman_f_transform_invert (&r, &m))
	return FALSE;
	if (!pixman_transform_from_pixman_f_transform (dst, &r))
	return FALSE;
	return TRUE;
	}

	static pixman_bool_t
	within_epsilon(pixman_fixed_t a, pixman_fixed_t b, pixman_fixed_t epsilon)
	{
	pixman_fixed_t t = a - b;
	if (t < 0) t = -t;
	return t <= epsilon;
	}

	#define epsilon (pixman_fixed_t) (2)

	#define is_same(a,b) (within_epsilon(a, b, epsilon))
	#define is_zero(a) (within_epsilon(a, 0, epsilon))
	#define is_one(a) (within_epsilon(a, F(1), epsilon))
	#define is_unit(a) (within_epsilon(a, F( 1), epsilon) \|\| \
	within_epsilon(a, F(-1), epsilon) \|\| \
	is_zero(a))
	#define is_int(a) (is_zero(pixman_fixed_frac(a)))

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_is_identity(const struct pixman_transform *t)
	{
	return ( is_same(t->matrix[0][0], t->matrix[1][1]) &&
	is_same(t->matrix[0][0], t->matrix[2][2]) &&
	!is_zero(t->matrix[0][0]) &&
	is_zero(t->matrix[0][1]) &&
	is_zero(t->matrix[0][2]) &&
	is_zero(t->matrix[1][0]) &&
	is_zero(t->matrix[1][2]) &&
	is_zero(t->matrix[2][0]) &&
	is_zero(t->matrix[2][1]));
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_is_scale(const struct pixman_transform *t)
	{
	return (!is_zero(t->matrix[0][0]) &&
	is_zero(t->matrix[0][1]) &&
	is_zero(t->matrix[0][2]) &&

	is_zero(t->matrix[1][0]) &&
	!is_zero(t->matrix[1][1]) &&
	is_zero(t->matrix[1][2]) &&

	is_zero(t->matrix[2][0]) &&
	is_zero(t->matrix[2][1]) &&
	!is_zero(t->matrix[2][2]));
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_is_int_translate(const struct pixman_transform *t)
	{
	return (is_one (t->matrix[0][0]) &&
	is_zero(t->matrix[0][1]) &&
	is_int (t->matrix[0][2]) &&

	is_zero(t->matrix[1][0]) &&
	is_one (t->matrix[1][1]) &&
	is_int (t->matrix[1][2]) &&

	is_zero(t->matrix[2][0]) &&
	is_zero(t->matrix[2][1]) &&
	is_one (t->matrix[2][2]));
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_is_inverse(const struct pixman_transform *a,
	const struct pixman_transform *b)
	{
	struct pixman_transform t;

	pixman_transform_multiply(&t, a, b);
	return pixman_transform_is_identity(&t);
	}

	PIXMAN_EXPORT void
	pixman_f_transform_from_pixman_transform (struct pixman_f_transform *ft,
	const struct pixman_transform *t)
	{
	int i, j;

	for (j = 0; j < 3; j++)
	for (i = 0; i < 3; i++)
	ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]);
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_transform_from_pixman_f_transform (struct pixman_transform *t,
	const struct pixman_f_transform *ft)
	{
	int i, j;

	for (j = 0; j < 3; j++)
	for (i = 0; i < 3; i++)
	{
	double d = ft->m[j][i];
	if (d < -32767.0 \|\| d > 32767.0)
	return FALSE;
	d = d * 65536.0 + 0.5;
	t->matrix[j][i] = (pixman_fixed_t) floor (d);
	}
	return TRUE;
	}

	static const int a[3] = { 3, 3, 2 };
	static const int b[3] = { 2, 1, 1 };

	PIXMAN_EXPORT pixman_bool_t
	pixman_f_transform_invert(struct pixman_f_transform *dst,
	const struct pixman_f_transform *src)
	{
	double det;
	int i, j;
	static int a[3] = { 2, 2, 1 };
	static int b[3] = { 1, 0, 0 };

	det = 0;
	for (i = 0; i < 3; i++) {
	double p;
	int ai = a[i];
	int bi = b[i];
	p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] -
	src->m[ai][1] * src->m[bi][2]);
	if (i == 1)
	p = -p;
	det += p;
	}
	if (det == 0)
	return FALSE;
	det = 1/det;
	for (j = 0; j < 3; j++) {
	for (i = 0; i < 3; i++) {
	double p;
	int ai = a[i];
	int aj = a[j];
	int bi = b[i];
	int bj = b[j];

	p = (src->m[ai][aj] * src->m[bi][bj] -
	src->m[ai][bj] * src->m[bi][aj]);
	if (((i + j) & 1) != 0)
	p = -p;
	dst->m[j][i] = det * p;
	}
	}
	return TRUE;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_f_transform_point(const struct pixman_f_transform *t,
	struct pixman_f_vector *v)
	{
	struct pixman_f_vector result;
	int i, j;
	double a;

	for (j = 0; j < 3; j++)
	{
	a = 0;
	for (i = 0; i < 3; i++)
	a += t->m[j][i] * v->v[i];
	result.v[j] = a;
	}
	if (!result.v[2])
	return FALSE;
	for (j = 0; j < 2; j++)
	v->v[j] = result.v[j] / result.v[2];
	v->v[2] = 1;
	return TRUE;
	}

	PIXMAN_EXPORT void
	pixman_f_transform_point_3d(const struct pixman_f_transform *t,
	struct pixman_f_vector *v)
	{
	struct pixman_f_vector result;
	int i, j;
	double a;

	for (j = 0; j < 3; j++)
	{
	a = 0;
	for (i = 0; i < 3; i++)
	a += t->m[j][i] * v->v[i];
	result.v[j] = a;
	}
	*v = result;
	}

	PIXMAN_EXPORT void
	pixman_f_transform_multiply(struct pixman_f_transform *dst,
	const struct pixman_f_transform *l,
	const struct pixman_f_transform *r)
	{
	struct pixman_f_transform d;
	int dx, dy;
	int o;

	for (dy = 0; dy < 3; dy++)
	for (dx = 0; dx < 3; dx++)
	{
	double v = 0;
	for (o = 0; o < 3; o++)
	v += l->m[dy][o] * r->m[o][dx];
	d.m[dy][dx] = v;
	}
	*dst = d;
	}

	PIXMAN_EXPORT void
	pixman_f_transform_init_scale (struct pixman_f_transform *t, double sx, double sy)
	{
	t->m[0][0] = sx; t->m[0][1] = 0; t->m[0][2] = 0;
	t->m[1][0] = 0; t->m[1][1] = sy; t->m[1][2] = 0;
	t->m[2][0] = 0; t->m[2][1] = 0; t->m[2][2] = 1;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_f_transform_scale (struct pixman_f_transform *forward,
	struct pixman_f_transform *reverse,
	double sx, double sy)
	{
	struct pixman_f_transform t;

	if (sx == 0 \|\| sy == 0)
	return FALSE;

	if (forward) {
	pixman_f_transform_init_scale (&t, sx, sy);
	pixman_f_transform_multiply (forward, &t, forward);
	}
	if (reverse) {
	pixman_f_transform_init_scale (&t, 1/sx, 1/sy);
	pixman_f_transform_multiply (reverse, reverse, &t);
	}
	return TRUE;
	}

	PIXMAN_EXPORT void
	pixman_f_transform_init_rotate (struct pixman_f_transform *t, double c, double s)
	{
	t->m[0][0] = c; t->m[0][1] = -s; t->m[0][2] = 0;
	t->m[1][0] = s; t->m[1][1] = c; t->m[1][2] = 0;
	t->m[2][0] = 0; t->m[2][1] = 0; t->m[2][2] = 1;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_f_transform_rotate (struct pixman_f_transform *forward,
	struct pixman_f_transform *reverse,
	double c, double s)
	{
	struct pixman_f_transform t;

	if (forward) {
	pixman_f_transform_init_rotate (&t, c, s);
	pixman_f_transform_multiply (forward, &t, forward);
	}
	if (reverse) {
	pixman_f_transform_init_rotate (&t, c, -s);
	pixman_f_transform_multiply (reverse, reverse, &t);
	}
	return TRUE;
	}

	PIXMAN_EXPORT void
	pixman_f_transform_init_translate (struct pixman_f_transform *t, double tx, double ty)
	{
	t->m[0][0] = 1; t->m[0][1] = 0; t->m[0][2] = tx;
	t->m[1][0] = 0; t->m[1][1] = 1; t->m[1][2] = ty;
	t->m[2][0] = 0; t->m[2][1] = 0; t->m[2][2] = 1;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_f_transform_translate (struct pixman_f_transform *forward,
	struct pixman_f_transform *reverse,
	double tx, double ty)
	{
	struct pixman_f_transform t;

	if (forward) {
	pixman_f_transform_init_translate (&t, tx, ty);
	pixman_f_transform_multiply (forward, &t, forward);
	}
	if (reverse) {
	pixman_f_transform_init_translate (&t, -tx, -ty);
	pixman_f_transform_multiply (reverse, reverse, &t);
	}
	return TRUE;
	}

	PIXMAN_EXPORT pixman_bool_t
	pixman_f_transform_bounds(const struct pixman_f_transform t, struct pixman_box16 b)
	{
	struct pixman_f_vector v[4];
	int i;
	int x1, y1, x2, y2;

	v[0].v[0] = b->x1; v[0].v[1] = b->y1; v[0].v[2] = 1;
	v[1].v[0] = b->x2; v[1].v[1] = b->y1; v[1].v[2] = 1;
	v[2].v[0] = b->x2; v[2].v[1] = b->y2; v[2].v[2] = 1;
	v[3].v[0] = b->x1; v[3].v[1] = b->y2; v[3].v[2] = 1;
	for (i = 0; i < 4; i++)
	{
	if (!pixman_f_transform_point (t, &v[i]))
	return FALSE;
	x1 = floor (v[i].v[0]);
	y1 = floor (v[i].v[1]);
	x2 = ceil (v[i].v[0]);
	y2 = ceil (v[i].v[1]);
	if (i == 0)
	{
	b->x1 = x1; b->y1 = y1;
	b->x2 = x2; b->y2 = y2;
	}
	else
	{
	if (x1 < b->x1) b->x1 = x1;
	if (y1 < b->y1) b->y1 = y1;
	if (x2 > b->x2) b->x2 = x2;
	if (y2 > b->y2) b->y2 = y2;
	}
	}
	return TRUE;
	}

	PIXMAN_EXPORT void
	pixman_f_transform_init_identity (struct pixman_f_transform *t)
	{
	int i, j;

	for (j = 0; j < 3; j++)
	for (i = 0; i < 3; i++)
	t->m[j][i] = i == j ? 1 : 0;
	}