michael@0: /*
michael@0:  * Copyright © 2008 Keith Packard
michael@0:  *
michael@0:  * Permission to use, copy, modify, distribute, and sell this software and its
michael@0:  * documentation for any purpose is hereby granted without fee, provided that
michael@0:  * the above copyright notice appear in all copies and that both that copyright
michael@0:  * notice and this permission notice appear in supporting documentation, and
michael@0:  * that the name of the copyright holders not be used in advertising or
michael@0:  * publicity pertaining to distribution of the software without specific,
michael@0:  * written prior permission.  The copyright holders make no representations
michael@0:  * about the suitability of this software for any purpose.  It is provided "as
michael@0:  * is" without express or implied warranty.
michael@0:  *
michael@0:  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
michael@0:  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
michael@0:  * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
michael@0:  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
michael@0:  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
michael@0:  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
michael@0:  * OF THIS SOFTWARE.
michael@0:  */
michael@0: 
michael@0: /*
michael@0:  * Matrix interfaces
michael@0:  */
michael@0: 
michael@0: #ifdef HAVE_CONFIG_H
michael@0: #include <config.h>
michael@0: #endif
michael@0: 
michael@0: #include <math.h>
michael@0: #include <string.h>
michael@0: #include "pixman-private.h"
michael@0: 
michael@0: #define F(x)    pixman_int_to_fixed (x)
michael@0: 
michael@0: static force_inline int
michael@0: count_leading_zeros (uint32_t x)
michael@0: {
michael@0: #ifdef __GNUC__
michael@0:     return __builtin_clz (x);
michael@0: #else
michael@0:     int n = 0;
michael@0:     while (x)
michael@0:     {
michael@0:         n++;
michael@0:         x >>= 1;
michael@0:     }
michael@0:     return 32 - n;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Large signed/unsigned integer division with rounding for the platforms with
michael@0:  * only 64-bit integer data type supported (no 128-bit data type).
michael@0:  *
michael@0:  * Arguments:
michael@0:  *     hi, lo - high and low 64-bit parts of the dividend
michael@0:  *     div    - 48-bit divisor
michael@0:  *
michael@0:  * Returns: lowest 64 bits of the result as a return value and highest 64
michael@0:  *          bits of the result to "result_hi" pointer
michael@0:  */
michael@0: 
michael@0: /* grade-school unsigned division (128-bit by 48-bit) with rounding to nearest */
michael@0: static force_inline uint64_t
michael@0: rounded_udiv_128_by_48 (uint64_t  hi,
michael@0:                         uint64_t  lo,
michael@0:                         uint64_t  div,
michael@0:                         uint64_t *result_hi)
michael@0: {
michael@0:     uint64_t tmp, remainder, result_lo;
michael@0:     assert(div < ((uint64_t)1 << 48));
michael@0: 
michael@0:     remainder = hi % div;
michael@0:     *result_hi = hi / div;
michael@0: 
michael@0:     tmp = (remainder << 16) + (lo >> 48);
michael@0:     result_lo = tmp / div;
michael@0:     remainder = tmp % div;
michael@0: 
michael@0:     tmp = (remainder << 16) + ((lo >> 32) & 0xFFFF);
michael@0:     result_lo = (result_lo << 16) + (tmp / div);
michael@0:     remainder = tmp % div;
michael@0: 
michael@0:     tmp = (remainder << 16) + ((lo >> 16) & 0xFFFF);
michael@0:     result_lo = (result_lo << 16) + (tmp / div);
michael@0:     remainder = tmp % div;
michael@0: 
michael@0:     tmp = (remainder << 16) + (lo & 0xFFFF);
michael@0:     result_lo = (result_lo << 16) + (tmp / div);
michael@0:     remainder = tmp % div;
michael@0: 
michael@0:     /* round to nearest */
michael@0:     if (remainder * 2 >= div && ++result_lo == 0)
michael@0:         *result_hi += 1;
michael@0: 
michael@0:     return result_lo;
michael@0: }
michael@0: 
michael@0: /* signed division (128-bit by 49-bit) with rounding to nearest */
michael@0: static inline int64_t
michael@0: rounded_sdiv_128_by_49 (int64_t   hi,
michael@0:                         uint64_t  lo,
michael@0:                         int64_t   div,
michael@0:                         int64_t  *signed_result_hi)
michael@0: {
michael@0:     uint64_t result_lo, result_hi;
michael@0:     int sign = 0;
michael@0:     if (div < 0)
michael@0:     {
michael@0:         div = -div;
michael@0:         sign ^= 1;
michael@0:     }
michael@0:     if (hi < 0)
michael@0:     {
michael@0:         if (lo != 0)
michael@0:             hi++;
michael@0:         hi = -hi;
michael@0:         lo = -lo;
michael@0:         sign ^= 1;
michael@0:     }
michael@0:     result_lo = rounded_udiv_128_by_48 (hi, lo, div, &result_hi);
michael@0:     if (sign)
michael@0:     {
michael@0:         if (result_lo != 0)
michael@0:             result_hi++;
michael@0:         result_hi = -result_hi;
michael@0:         result_lo = -result_lo;
michael@0:     }
michael@0:     if (signed_result_hi)
michael@0:     {
michael@0:         *signed_result_hi = result_hi;
michael@0:     }
michael@0:     return result_lo;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Multiply 64.16 fixed point value by (2^scalebits) and convert
michael@0:  * to 128-bit integer.
michael@0:  */
michael@0: static force_inline void
michael@0: fixed_64_16_to_int128 (int64_t  hi,
michael@0:                        int64_t  lo,
michael@0:                        int64_t *rhi,
michael@0:                        int64_t *rlo,
michael@0:                        int      scalebits)
michael@0: {
michael@0:     /* separate integer and fractional parts */
michael@0:     hi += lo >> 16;
michael@0:     lo &= 0xFFFF;
michael@0: 
michael@0:     if (scalebits <= 0)
michael@0:     {
michael@0:         *rlo = hi >> (-scalebits);
michael@0:         *rhi = *rlo >> 63;
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         *rhi = hi >> (64 - scalebits);
michael@0:         *rlo = (uint64_t)hi << scalebits;
michael@0:         if (scalebits < 16)
michael@0:             *rlo += lo >> (16 - scalebits);
michael@0:         else
michael@0:             *rlo += lo << (scalebits - 16);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Convert 112.16 fixed point value to 48.16 with clamping for the out
michael@0:  * of range values.
michael@0:  */
michael@0: static force_inline pixman_fixed_48_16_t
michael@0: fixed_112_16_to_fixed_48_16 (int64_t hi, int64_t lo, pixman_bool_t *clampflag)
michael@0: {
michael@0:     if ((lo >> 63) != hi)
michael@0:     {
michael@0:         *clampflag = TRUE;
michael@0:         return hi >= 0 ? INT64_MAX : INT64_MIN;
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         return lo;
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Transform a point with 31.16 fixed point coordinates from the destination
michael@0:  * space to a point with 48.16 fixed point coordinates in the source space.
michael@0:  * No overflows are possible for affine transformations and the results are
michael@0:  * accurate including the least significant bit. Projective transformations
michael@0:  * may overflow, in this case the results are just clamped to return maximum
michael@0:  * or minimum 48.16 values (so that the caller can at least handle the NONE
michael@0:  * and PAD repeats correctly) and the return value is FALSE to indicate that
michael@0:  * such clamping has happened.
michael@0:  */
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_point_31_16 (const pixman_transform_t    *t,
michael@0:                               const pixman_vector_48_16_t *v,
michael@0:                               pixman_vector_48_16_t       *result)
michael@0: {
michael@0:     pixman_bool_t clampflag = FALSE;
michael@0:     int i;
michael@0:     int64_t tmp[3][2], divint;
michael@0:     uint16_t divfrac;
michael@0: 
michael@0:     /* input vector values must have no more than 31 bits (including sign)
michael@0:      * in the integer part */
michael@0:     assert (v->v[0] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[1] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[2] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0: 
michael@0:     for (i = 0; i < 3; i++)
michael@0:     {
michael@0:         tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
michael@0:         tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
michael@0:         tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
michael@0:         tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
michael@0:         tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
michael@0:         tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * separate 64-bit integer and 16-bit fractional parts for the divisor,
michael@0:      * which is also scaled by 65536 after fixed point multiplication.
michael@0:      */
michael@0:     divint  = tmp[2][0] + (tmp[2][1] >> 16);
michael@0:     divfrac = tmp[2][1] & 0xFFFF;
michael@0: 
michael@0:     if (divint == pixman_fixed_1 && divfrac == 0)
michael@0:     {
michael@0:         /*
michael@0:          * this is a simple affine transformation
michael@0:          */
michael@0:         result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
michael@0:         result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
michael@0:         result->v[2] = pixman_fixed_1;
michael@0:     }
michael@0:     else if (divint == 0 && divfrac == 0)
michael@0:     {
michael@0:         /*
michael@0:          * handle zero divisor (if the values are non-zero, set the
michael@0:          * results to maximum positive or minimum negative)
michael@0:          */
michael@0:         clampflag = TRUE;
michael@0: 
michael@0:         result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
michael@0:         result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
michael@0: 
michael@0:         if (result->v[0] > 0)
michael@0:             result->v[0] = INT64_MAX;
michael@0:         else if (result->v[0] < 0)
michael@0:             result->v[0] = INT64_MIN;
michael@0: 
michael@0:         if (result->v[1] > 0)
michael@0:             result->v[1] = INT64_MAX;
michael@0:         else if (result->v[1] < 0)
michael@0:             result->v[1] = INT64_MIN;
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         /*
michael@0:          * projective transformation, analyze the top 32 bits of the divisor
michael@0:          */
michael@0:         int32_t hi32divbits = divint >> 32;
michael@0:         if (hi32divbits < 0)
michael@0:             hi32divbits = ~hi32divbits;
michael@0: 
michael@0:         if (hi32divbits == 0)
michael@0:         {
michael@0:             /* the divisor is small, we can actually keep all the bits */
michael@0:             int64_t hi, rhi, lo, rlo;
michael@0:             int64_t div = (divint << 16) + divfrac;
michael@0: 
michael@0:             fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32);
michael@0:             rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
michael@0:             result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
michael@0: 
michael@0:             fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32);
michael@0:             rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
michael@0:             result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
michael@0:         }
michael@0:         else
michael@0:         {
michael@0:             /* the divisor needs to be reduced to 48 bits */
michael@0:             int64_t hi, rhi, lo, rlo, div;
michael@0:             int shift = 32 - count_leading_zeros (hi32divbits);
michael@0:             fixed_64_16_to_int128 (divint, divfrac, &hi, &div, 16 - shift);
michael@0: 
michael@0:             fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32 - shift);
michael@0:             rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
michael@0:             result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
michael@0: 
michael@0:             fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32 - shift);
michael@0:             rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
michael@0:             result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
michael@0:         }
michael@0:     }
michael@0:     result->v[2] = pixman_fixed_1;
michael@0:     return !clampflag;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_transform_point_31_16_affine (const pixman_transform_t    *t,
michael@0:                                      const pixman_vector_48_16_t *v,
michael@0:                                      pixman_vector_48_16_t       *result)
michael@0: {
michael@0:     int64_t hi0, lo0, hi1, lo1;
michael@0: 
michael@0:     /* input vector values must have no more than 31 bits (including sign)
michael@0:      * in the integer part */
michael@0:     assert (v->v[0] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[1] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0: 
michael@0:     hi0  = (int64_t)t->matrix[0][0] * (v->v[0] >> 16);
michael@0:     lo0  = (int64_t)t->matrix[0][0] * (v->v[0] & 0xFFFF);
michael@0:     hi0 += (int64_t)t->matrix[0][1] * (v->v[1] >> 16);
michael@0:     lo0 += (int64_t)t->matrix[0][1] * (v->v[1] & 0xFFFF);
michael@0:     hi0 += (int64_t)t->matrix[0][2];
michael@0: 
michael@0:     hi1  = (int64_t)t->matrix[1][0] * (v->v[0] >> 16);
michael@0:     lo1  = (int64_t)t->matrix[1][0] * (v->v[0] & 0xFFFF);
michael@0:     hi1 += (int64_t)t->matrix[1][1] * (v->v[1] >> 16);
michael@0:     lo1 += (int64_t)t->matrix[1][1] * (v->v[1] & 0xFFFF);
michael@0:     hi1 += (int64_t)t->matrix[1][2];
michael@0: 
michael@0:     result->v[0] = hi0 + ((lo0 + 0x8000) >> 16);
michael@0:     result->v[1] = hi1 + ((lo1 + 0x8000) >> 16);
michael@0:     result->v[2] = pixman_fixed_1;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_transform_point_31_16_3d (const pixman_transform_t    *t,
michael@0:                                  const pixman_vector_48_16_t *v,
michael@0:                                  pixman_vector_48_16_t       *result)
michael@0: {
michael@0:     int i;
michael@0:     int64_t tmp[3][2];
michael@0: 
michael@0:     /* input vector values must have no more than 31 bits (including sign)
michael@0:      * in the integer part */
michael@0:     assert (v->v[0] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[1] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[2] <   ((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0:     assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
michael@0: 
michael@0:     for (i = 0; i < 3; i++)
michael@0:     {
michael@0:         tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
michael@0:         tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
michael@0:         tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
michael@0:         tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
michael@0:         tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
michael@0:         tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF);
michael@0:     }
michael@0: 
michael@0:     result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
michael@0:     result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
michael@0:     result->v[2] = tmp[2][0] + ((tmp[2][1] + 0x8000) >> 16);
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_transform_init_identity (struct pixman_transform *matrix)
michael@0: {
michael@0:     int i;
michael@0: 
michael@0:     memset (matrix, '\0', sizeof (struct pixman_transform));
michael@0:     for (i = 0; i < 3; i++)
michael@0: 	matrix->matrix[i][i] = F (1);
michael@0: }
michael@0: 
michael@0: typedef pixman_fixed_32_32_t pixman_fixed_34_30_t;
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_point_3d (const struct pixman_transform *transform,
michael@0:                            struct pixman_vector *         vector)
michael@0: {
michael@0:     pixman_vector_48_16_t tmp;
michael@0:     tmp.v[0] = vector->vector[0];
michael@0:     tmp.v[1] = vector->vector[1];
michael@0:     tmp.v[2] = vector->vector[2];
michael@0: 
michael@0:     pixman_transform_point_31_16_3d (transform, &tmp, &tmp);
michael@0: 
michael@0:     vector->vector[0] = tmp.v[0];
michael@0:     vector->vector[1] = tmp.v[1];
michael@0:     vector->vector[2] = tmp.v[2];
michael@0: 
michael@0:     return vector->vector[0] == tmp.v[0] &&
michael@0:            vector->vector[1] == tmp.v[1] &&
michael@0:            vector->vector[2] == tmp.v[2];
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_point (const struct pixman_transform *transform,
michael@0:                         struct pixman_vector *         vector)
michael@0: {
michael@0:     pixman_vector_48_16_t tmp;
michael@0:     tmp.v[0] = vector->vector[0];
michael@0:     tmp.v[1] = vector->vector[1];
michael@0:     tmp.v[2] = vector->vector[2];
michael@0: 
michael@0:     if (!pixman_transform_point_31_16 (transform, &tmp, &tmp))
michael@0:         return FALSE;
michael@0: 
michael@0:     vector->vector[0] = tmp.v[0];
michael@0:     vector->vector[1] = tmp.v[1];
michael@0:     vector->vector[2] = tmp.v[2];
michael@0: 
michael@0:     return vector->vector[0] == tmp.v[0] &&
michael@0:            vector->vector[1] == tmp.v[1] &&
michael@0:            vector->vector[2] == tmp.v[2];
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_multiply (struct pixman_transform *      dst,
michael@0:                            const struct pixman_transform *l,
michael@0:                            const struct pixman_transform *r)
michael@0: {
michael@0:     struct pixman_transform d;
michael@0:     int dx, dy;
michael@0:     int o;
michael@0: 
michael@0:     for (dy = 0; dy < 3; dy++)
michael@0:     {
michael@0: 	for (dx = 0; dx < 3; dx++)
michael@0: 	{
michael@0: 	    pixman_fixed_48_16_t v;
michael@0: 	    pixman_fixed_32_32_t partial;
michael@0: 	    
michael@0: 	    v = 0;
michael@0: 	    for (o = 0; o < 3; o++)
michael@0: 	    {
michael@0: 		partial =
michael@0: 		    (pixman_fixed_32_32_t) l->matrix[dy][o] *
michael@0: 		    (pixman_fixed_32_32_t) r->matrix[o][dx];
michael@0: 
michael@0: 		v += (partial + 0x8000) >> 16;
michael@0: 	    }
michael@0: 
michael@0: 	    if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
michael@0: 		return FALSE;
michael@0: 	    
michael@0: 	    d.matrix[dy][dx] = (pixman_fixed_t) v;
michael@0: 	}
michael@0:     }
michael@0: 
michael@0:     *dst = d;
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_transform_init_scale (struct pixman_transform *t,
michael@0:                              pixman_fixed_t           sx,
michael@0:                              pixman_fixed_t           sy)
michael@0: {
michael@0:     memset (t, '\0', sizeof (struct pixman_transform));
michael@0: 
michael@0:     t->matrix[0][0] = sx;
michael@0:     t->matrix[1][1] = sy;
michael@0:     t->matrix[2][2] = F (1);
michael@0: }
michael@0: 
michael@0: static pixman_fixed_t
michael@0: fixed_inverse (pixman_fixed_t x)
michael@0: {
michael@0:     return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F (1)) * F (1)) / x);
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_scale (struct pixman_transform *forward,
michael@0:                         struct pixman_transform *reverse,
michael@0:                         pixman_fixed_t           sx,
michael@0:                         pixman_fixed_t           sy)
michael@0: {
michael@0:     struct pixman_transform t;
michael@0: 
michael@0:     if (sx == 0 || sy == 0)
michael@0: 	return FALSE;
michael@0: 
michael@0:     if (forward)
michael@0:     {
michael@0: 	pixman_transform_init_scale (&t, sx, sy);
michael@0: 	if (!pixman_transform_multiply (forward, &t, forward))
michael@0: 	    return FALSE;
michael@0:     }
michael@0:     
michael@0:     if (reverse)
michael@0:     {
michael@0: 	pixman_transform_init_scale (&t, fixed_inverse (sx),
michael@0: 	                             fixed_inverse (sy));
michael@0: 	if (!pixman_transform_multiply (reverse, reverse, &t))
michael@0: 	    return FALSE;
michael@0:     }
michael@0:     
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_transform_init_rotate (struct pixman_transform *t,
michael@0:                               pixman_fixed_t           c,
michael@0:                               pixman_fixed_t           s)
michael@0: {
michael@0:     memset (t, '\0', sizeof (struct pixman_transform));
michael@0: 
michael@0:     t->matrix[0][0] = c;
michael@0:     t->matrix[0][1] = -s;
michael@0:     t->matrix[1][0] = s;
michael@0:     t->matrix[1][1] = c;
michael@0:     t->matrix[2][2] = F (1);
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_rotate (struct pixman_transform *forward,
michael@0:                          struct pixman_transform *reverse,
michael@0:                          pixman_fixed_t           c,
michael@0:                          pixman_fixed_t           s)
michael@0: {
michael@0:     struct pixman_transform t;
michael@0: 
michael@0:     if (forward)
michael@0:     {
michael@0: 	pixman_transform_init_rotate (&t, c, s);
michael@0: 	if (!pixman_transform_multiply (forward, &t, forward))
michael@0: 	    return FALSE;
michael@0:     }
michael@0: 
michael@0:     if (reverse)
michael@0:     {
michael@0: 	pixman_transform_init_rotate (&t, c, -s);
michael@0: 	if (!pixman_transform_multiply (reverse, reverse, &t))
michael@0: 	    return FALSE;
michael@0:     }
michael@0:     
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_transform_init_translate (struct pixman_transform *t,
michael@0:                                  pixman_fixed_t           tx,
michael@0:                                  pixman_fixed_t           ty)
michael@0: {
michael@0:     memset (t, '\0', sizeof (struct pixman_transform));
michael@0: 
michael@0:     t->matrix[0][0] = F (1);
michael@0:     t->matrix[0][2] = tx;
michael@0:     t->matrix[1][1] = F (1);
michael@0:     t->matrix[1][2] = ty;
michael@0:     t->matrix[2][2] = F (1);
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_translate (struct pixman_transform *forward,
michael@0:                             struct pixman_transform *reverse,
michael@0:                             pixman_fixed_t           tx,
michael@0:                             pixman_fixed_t           ty)
michael@0: {
michael@0:     struct pixman_transform t;
michael@0: 
michael@0:     if (forward)
michael@0:     {
michael@0: 	pixman_transform_init_translate (&t, tx, ty);
michael@0: 
michael@0: 	if (!pixman_transform_multiply (forward, &t, forward))
michael@0: 	    return FALSE;
michael@0:     }
michael@0: 
michael@0:     if (reverse)
michael@0:     {
michael@0: 	pixman_transform_init_translate (&t, -tx, -ty);
michael@0: 
michael@0: 	if (!pixman_transform_multiply (reverse, reverse, &t))
michael@0: 	    return FALSE;
michael@0:     }
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_bounds (const struct pixman_transform *matrix,
michael@0:                          struct pixman_box16 *          b)
michael@0: 
michael@0: {
michael@0:     struct pixman_vector v[4];
michael@0:     int i;
michael@0:     int x1, y1, x2, y2;
michael@0: 
michael@0:     v[0].vector[0] = F (b->x1);
michael@0:     v[0].vector[1] = F (b->y1);
michael@0:     v[0].vector[2] = F (1);
michael@0: 
michael@0:     v[1].vector[0] = F (b->x2);
michael@0:     v[1].vector[1] = F (b->y1);
michael@0:     v[1].vector[2] = F (1);
michael@0: 
michael@0:     v[2].vector[0] = F (b->x2);
michael@0:     v[2].vector[1] = F (b->y2);
michael@0:     v[2].vector[2] = F (1);
michael@0: 
michael@0:     v[3].vector[0] = F (b->x1);
michael@0:     v[3].vector[1] = F (b->y2);
michael@0:     v[3].vector[2] = F (1);
michael@0: 
michael@0:     for (i = 0; i < 4; i++)
michael@0:     {
michael@0: 	if (!pixman_transform_point (matrix, &v[i]))
michael@0: 	    return FALSE;
michael@0: 
michael@0: 	x1 = pixman_fixed_to_int (v[i].vector[0]);
michael@0: 	y1 = pixman_fixed_to_int (v[i].vector[1]);
michael@0: 	x2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[0]));
michael@0: 	y2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[1]));
michael@0: 
michael@0: 	if (i == 0)
michael@0: 	{
michael@0: 	    b->x1 = x1;
michael@0: 	    b->y1 = y1;
michael@0: 	    b->x2 = x2;
michael@0: 	    b->y2 = y2;
michael@0: 	}
michael@0: 	else
michael@0: 	{
michael@0: 	    if (x1 < b->x1) b->x1 = x1;
michael@0: 	    if (y1 < b->y1) b->y1 = y1;
michael@0: 	    if (x2 > b->x2) b->x2 = x2;
michael@0: 	    if (y2 > b->y2) b->y2 = y2;
michael@0: 	}
michael@0:     }
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_invert (struct pixman_transform *      dst,
michael@0:                          const struct pixman_transform *src)
michael@0: {
michael@0:     struct pixman_f_transform m;
michael@0: 
michael@0:     pixman_f_transform_from_pixman_transform (&m, src);
michael@0: 
michael@0:     if (!pixman_f_transform_invert (&m, &m))
michael@0: 	return FALSE;
michael@0: 
michael@0:     if (!pixman_transform_from_pixman_f_transform (dst, &m))
michael@0: 	return FALSE;
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: static pixman_bool_t
michael@0: within_epsilon (pixman_fixed_t a,
michael@0:                 pixman_fixed_t b,
michael@0:                 pixman_fixed_t epsilon)
michael@0: {
michael@0:     pixman_fixed_t t = a - b;
michael@0: 
michael@0:     if (t < 0)
michael@0: 	t = -t;
michael@0: 
michael@0:     return t <= epsilon;
michael@0: }
michael@0: 
michael@0: #define EPSILON (pixman_fixed_t) (2)
michael@0: 
michael@0: #define IS_SAME(a, b) (within_epsilon (a, b, EPSILON))
michael@0: #define IS_ZERO(a)    (within_epsilon (a, 0, EPSILON))
michael@0: #define IS_ONE(a)     (within_epsilon (a, F (1), EPSILON))
michael@0: #define IS_UNIT(a)			    \
michael@0:     (within_epsilon (a, F (1), EPSILON) ||  \
michael@0:      within_epsilon (a, F (-1), EPSILON) || \
michael@0:      IS_ZERO (a))
michael@0: #define IS_INT(a)    (IS_ZERO (pixman_fixed_frac (a)))
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_is_identity (const struct pixman_transform *t)
michael@0: {
michael@0:     return (IS_SAME (t->matrix[0][0], t->matrix[1][1]) &&
michael@0: 	    IS_SAME (t->matrix[0][0], t->matrix[2][2]) &&
michael@0: 	    !IS_ZERO (t->matrix[0][0]) &&
michael@0: 	    IS_ZERO (t->matrix[0][1]) &&
michael@0: 	    IS_ZERO (t->matrix[0][2]) &&
michael@0: 	    IS_ZERO (t->matrix[1][0]) &&
michael@0: 	    IS_ZERO (t->matrix[1][2]) &&
michael@0: 	    IS_ZERO (t->matrix[2][0]) &&
michael@0: 	    IS_ZERO (t->matrix[2][1]));
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_is_scale (const struct pixman_transform *t)
michael@0: {
michael@0:     return (!IS_ZERO (t->matrix[0][0]) &&
michael@0:             IS_ZERO (t->matrix[0][1]) &&
michael@0:             IS_ZERO (t->matrix[0][2]) &&
michael@0: 
michael@0:             IS_ZERO (t->matrix[1][0]) &&
michael@0:             !IS_ZERO (t->matrix[1][1]) &&
michael@0:             IS_ZERO (t->matrix[1][2]) &&
michael@0: 
michael@0:             IS_ZERO (t->matrix[2][0]) &&
michael@0:             IS_ZERO (t->matrix[2][1]) &&
michael@0:             !IS_ZERO (t->matrix[2][2]));
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_is_int_translate (const struct pixman_transform *t)
michael@0: {
michael@0:     return (IS_ONE (t->matrix[0][0]) &&
michael@0:             IS_ZERO (t->matrix[0][1]) &&
michael@0:             IS_INT (t->matrix[0][2]) &&
michael@0: 
michael@0:             IS_ZERO (t->matrix[1][0]) &&
michael@0:             IS_ONE (t->matrix[1][1]) &&
michael@0:             IS_INT (t->matrix[1][2]) &&
michael@0: 
michael@0:             IS_ZERO (t->matrix[2][0]) &&
michael@0:             IS_ZERO (t->matrix[2][1]) &&
michael@0:             IS_ONE (t->matrix[2][2]));
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_is_inverse (const struct pixman_transform *a,
michael@0:                              const struct pixman_transform *b)
michael@0: {
michael@0:     struct pixman_transform t;
michael@0: 
michael@0:     if (!pixman_transform_multiply (&t, a, b))
michael@0: 	return FALSE;
michael@0: 
michael@0:     return pixman_transform_is_identity (&t);
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_f_transform_from_pixman_transform (struct pixman_f_transform *    ft,
michael@0:                                           const struct pixman_transform *t)
michael@0: {
michael@0:     int i, j;
michael@0: 
michael@0:     for (j = 0; j < 3; j++)
michael@0:     {
michael@0: 	for (i = 0; i < 3; i++)
michael@0: 	    ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]);
michael@0:     }
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_transform_from_pixman_f_transform (struct pixman_transform *        t,
michael@0:                                           const struct pixman_f_transform *ft)
michael@0: {
michael@0:     int i, j;
michael@0: 
michael@0:     for (j = 0; j < 3; j++)
michael@0:     {
michael@0: 	for (i = 0; i < 3; i++)
michael@0: 	{
michael@0: 	    double d = ft->m[j][i];
michael@0: 	    if (d < -32767.0 || d > 32767.0)
michael@0: 		return FALSE;
michael@0: 	    d = d * 65536.0 + 0.5;
michael@0: 	    t->matrix[j][i] = (pixman_fixed_t) floor (d);
michael@0: 	}
michael@0:     }
michael@0:     
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_f_transform_invert (struct pixman_f_transform *      dst,
michael@0:                            const struct pixman_f_transform *src)
michael@0: {
michael@0:     static const int a[3] = { 2, 2, 1 };
michael@0:     static const int b[3] = { 1, 0, 0 };
michael@0:     pixman_f_transform_t d;
michael@0:     double det;
michael@0:     int i, j;
michael@0: 
michael@0:     det = 0;
michael@0:     for (i = 0; i < 3; i++)
michael@0:     {
michael@0: 	double p;
michael@0: 	int ai = a[i];
michael@0: 	int bi = b[i];
michael@0: 	p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] -
michael@0: 	                    src->m[ai][1] * src->m[bi][2]);
michael@0: 	if (i == 1)
michael@0: 	    p = -p;
michael@0: 	det += p;
michael@0:     }
michael@0:     
michael@0:     if (det == 0)
michael@0: 	return FALSE;
michael@0:     
michael@0:     det = 1 / det;
michael@0:     for (j = 0; j < 3; j++)
michael@0:     {
michael@0: 	for (i = 0; i < 3; i++)
michael@0: 	{
michael@0: 	    double p;
michael@0: 	    int ai = a[i];
michael@0: 	    int aj = a[j];
michael@0: 	    int bi = b[i];
michael@0: 	    int bj = b[j];
michael@0: 
michael@0: 	    p = (src->m[ai][aj] * src->m[bi][bj] -
michael@0: 	         src->m[ai][bj] * src->m[bi][aj]);
michael@0: 	    
michael@0: 	    if (((i + j) & 1) != 0)
michael@0: 		p = -p;
michael@0: 	    
michael@0: 	    d.m[j][i] = det * p;
michael@0: 	}
michael@0:     }
michael@0: 
michael@0:     *dst = d;
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_f_transform_point (const struct pixman_f_transform *t,
michael@0:                           struct pixman_f_vector *         v)
michael@0: {
michael@0:     struct pixman_f_vector result;
michael@0:     int i, j;
michael@0:     double a;
michael@0: 
michael@0:     for (j = 0; j < 3; j++)
michael@0:     {
michael@0: 	a = 0;
michael@0: 	for (i = 0; i < 3; i++)
michael@0: 	    a += t->m[j][i] * v->v[i];
michael@0: 	result.v[j] = a;
michael@0:     }
michael@0:     
michael@0:     if (!result.v[2])
michael@0: 	return FALSE;
michael@0: 
michael@0:     for (j = 0; j < 2; j++)
michael@0: 	v->v[j] = result.v[j] / result.v[2];
michael@0: 
michael@0:     v->v[2] = 1;
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_f_transform_point_3d (const struct pixman_f_transform *t,
michael@0:                              struct pixman_f_vector *         v)
michael@0: {
michael@0:     struct pixman_f_vector result;
michael@0:     int i, j;
michael@0:     double a;
michael@0: 
michael@0:     for (j = 0; j < 3; j++)
michael@0:     {
michael@0: 	a = 0;
michael@0: 	for (i = 0; i < 3; i++)
michael@0: 	    a += t->m[j][i] * v->v[i];
michael@0: 	result.v[j] = a;
michael@0:     }
michael@0:     
michael@0:     *v = result;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_f_transform_multiply (struct pixman_f_transform *      dst,
michael@0:                              const struct pixman_f_transform *l,
michael@0:                              const struct pixman_f_transform *r)
michael@0: {
michael@0:     struct pixman_f_transform d;
michael@0:     int dx, dy;
michael@0:     int o;
michael@0: 
michael@0:     for (dy = 0; dy < 3; dy++)
michael@0:     {
michael@0: 	for (dx = 0; dx < 3; dx++)
michael@0: 	{
michael@0: 	    double v = 0;
michael@0: 	    for (o = 0; o < 3; o++)
michael@0: 		v += l->m[dy][o] * r->m[o][dx];
michael@0: 	    d.m[dy][dx] = v;
michael@0: 	}
michael@0:     }
michael@0:     
michael@0:     *dst = d;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_f_transform_init_scale (struct pixman_f_transform *t,
michael@0:                                double                     sx,
michael@0:                                double                     sy)
michael@0: {
michael@0:     t->m[0][0] = sx;
michael@0:     t->m[0][1] = 0;
michael@0:     t->m[0][2] = 0;
michael@0:     t->m[1][0] = 0;
michael@0:     t->m[1][1] = sy;
michael@0:     t->m[1][2] = 0;
michael@0:     t->m[2][0] = 0;
michael@0:     t->m[2][1] = 0;
michael@0:     t->m[2][2] = 1;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_f_transform_scale (struct pixman_f_transform *forward,
michael@0:                           struct pixman_f_transform *reverse,
michael@0:                           double                     sx,
michael@0:                           double                     sy)
michael@0: {
michael@0:     struct pixman_f_transform t;
michael@0: 
michael@0:     if (sx == 0 || sy == 0)
michael@0: 	return FALSE;
michael@0: 
michael@0:     if (forward)
michael@0:     {
michael@0: 	pixman_f_transform_init_scale (&t, sx, sy);
michael@0: 	pixman_f_transform_multiply (forward, &t, forward);
michael@0:     }
michael@0:     
michael@0:     if (reverse)
michael@0:     {
michael@0: 	pixman_f_transform_init_scale (&t, 1 / sx, 1 / sy);
michael@0: 	pixman_f_transform_multiply (reverse, reverse, &t);
michael@0:     }
michael@0:     
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_f_transform_init_rotate (struct pixman_f_transform *t,
michael@0:                                 double                     c,
michael@0:                                 double                     s)
michael@0: {
michael@0:     t->m[0][0] = c;
michael@0:     t->m[0][1] = -s;
michael@0:     t->m[0][2] = 0;
michael@0:     t->m[1][0] = s;
michael@0:     t->m[1][1] = c;
michael@0:     t->m[1][2] = 0;
michael@0:     t->m[2][0] = 0;
michael@0:     t->m[2][1] = 0;
michael@0:     t->m[2][2] = 1;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_f_transform_rotate (struct pixman_f_transform *forward,
michael@0:                            struct pixman_f_transform *reverse,
michael@0:                            double                     c,
michael@0:                            double                     s)
michael@0: {
michael@0:     struct pixman_f_transform t;
michael@0: 
michael@0:     if (forward)
michael@0:     {
michael@0: 	pixman_f_transform_init_rotate (&t, c, s);
michael@0: 	pixman_f_transform_multiply (forward, &t, forward);
michael@0:     }
michael@0:     
michael@0:     if (reverse)
michael@0:     {
michael@0: 	pixman_f_transform_init_rotate (&t, c, -s);
michael@0: 	pixman_f_transform_multiply (reverse, reverse, &t);
michael@0:     }
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_f_transform_init_translate (struct pixman_f_transform *t,
michael@0:                                    double                     tx,
michael@0:                                    double                     ty)
michael@0: {
michael@0:     t->m[0][0] = 1;
michael@0:     t->m[0][1] = 0;
michael@0:     t->m[0][2] = tx;
michael@0:     t->m[1][0] = 0;
michael@0:     t->m[1][1] = 1;
michael@0:     t->m[1][2] = ty;
michael@0:     t->m[2][0] = 0;
michael@0:     t->m[2][1] = 0;
michael@0:     t->m[2][2] = 1;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_f_transform_translate (struct pixman_f_transform *forward,
michael@0:                               struct pixman_f_transform *reverse,
michael@0:                               double                     tx,
michael@0:                               double                     ty)
michael@0: {
michael@0:     struct pixman_f_transform t;
michael@0: 
michael@0:     if (forward)
michael@0:     {
michael@0: 	pixman_f_transform_init_translate (&t, tx, ty);
michael@0: 	pixman_f_transform_multiply (forward, &t, forward);
michael@0:     }
michael@0: 
michael@0:     if (reverse)
michael@0:     {
michael@0: 	pixman_f_transform_init_translate (&t, -tx, -ty);
michael@0: 	pixman_f_transform_multiply (reverse, reverse, &t);
michael@0:     }
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT pixman_bool_t
michael@0: pixman_f_transform_bounds (const struct pixman_f_transform *t,
michael@0:                            struct pixman_box16 *            b)
michael@0: {
michael@0:     struct pixman_f_vector v[4];
michael@0:     int i;
michael@0:     int x1, y1, x2, y2;
michael@0: 
michael@0:     v[0].v[0] = b->x1;
michael@0:     v[0].v[1] = b->y1;
michael@0:     v[0].v[2] = 1;
michael@0:     v[1].v[0] = b->x2;
michael@0:     v[1].v[1] = b->y1;
michael@0:     v[1].v[2] = 1;
michael@0:     v[2].v[0] = b->x2;
michael@0:     v[2].v[1] = b->y2;
michael@0:     v[2].v[2] = 1;
michael@0:     v[3].v[0] = b->x1;
michael@0:     v[3].v[1] = b->y2;
michael@0:     v[3].v[2] = 1;
michael@0: 
michael@0:     for (i = 0; i < 4; i++)
michael@0:     {
michael@0: 	if (!pixman_f_transform_point (t, &v[i]))
michael@0: 	    return FALSE;
michael@0: 
michael@0: 	x1 = floor (v[i].v[0]);
michael@0: 	y1 = floor (v[i].v[1]);
michael@0: 	x2 = ceil (v[i].v[0]);
michael@0: 	y2 = ceil (v[i].v[1]);
michael@0: 
michael@0: 	if (i == 0)
michael@0: 	{
michael@0: 	    b->x1 = x1;
michael@0: 	    b->y1 = y1;
michael@0: 	    b->x2 = x2;
michael@0: 	    b->y2 = y2;
michael@0: 	}
michael@0: 	else
michael@0: 	{
michael@0: 	    if (x1 < b->x1) b->x1 = x1;
michael@0: 	    if (y1 < b->y1) b->y1 = y1;
michael@0: 	    if (x2 > b->x2) b->x2 = x2;
michael@0: 	    if (y2 > b->y2) b->y2 = y2;
michael@0: 	}
michael@0:     }
michael@0: 
michael@0:     return TRUE;
michael@0: }
michael@0: 
michael@0: PIXMAN_EXPORT void
michael@0: pixman_f_transform_init_identity (struct pixman_f_transform *t)
michael@0: {
michael@0:     int i, j;
michael@0: 
michael@0:     for (j = 0; j < 3; j++)
michael@0:     {
michael@0: 	for (i = 0; i < 3; i++)
michael@0: 	    t->m[j][i] = i == j ? 1 : 0;
michael@0:     }
michael@0: }