1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/cairo/libpixman/src/pixman-matrix.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1073 @@
1.4 +/*
1.5 + * Copyright © 2008 Keith Packard
1.6 + *
1.7 + * Permission to use, copy, modify, distribute, and sell this software and its
1.8 + * documentation for any purpose is hereby granted without fee, provided that
1.9 + * the above copyright notice appear in all copies and that both that copyright
1.10 + * notice and this permission notice appear in supporting documentation, and
1.11 + * that the name of the copyright holders not be used in advertising or
1.12 + * publicity pertaining to distribution of the software without specific,
1.13 + * written prior permission. The copyright holders make no representations
1.14 + * about the suitability of this software for any purpose. It is provided "as
1.15 + * is" without express or implied warranty.
1.16 + *
1.17 + * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
1.18 + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
1.19 + * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
1.20 + * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
1.21 + * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
1.22 + * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
1.23 + * OF THIS SOFTWARE.
1.24 + */
1.25 +
1.26 +/*
1.27 + * Matrix interfaces
1.28 + */
1.29 +
1.30 +#ifdef HAVE_CONFIG_H
1.31 +#include <config.h>
1.32 +#endif
1.33 +
1.34 +#include <math.h>
1.35 +#include <string.h>
1.36 +#include "pixman-private.h"
1.37 +
1.38 +#define F(x) pixman_int_to_fixed (x)
1.39 +
1.40 +static force_inline int
1.41 +count_leading_zeros (uint32_t x)
1.42 +{
1.43 +#ifdef __GNUC__
1.44 + return __builtin_clz (x);
1.45 +#else
1.46 + int n = 0;
1.47 + while (x)
1.48 + {
1.49 + n++;
1.50 + x >>= 1;
1.51 + }
1.52 + return 32 - n;
1.53 +#endif
1.54 +}
1.55 +
1.56 +/*
1.57 + * Large signed/unsigned integer division with rounding for the platforms with
1.58 + * only 64-bit integer data type supported (no 128-bit data type).
1.59 + *
1.60 + * Arguments:
1.61 + * hi, lo - high and low 64-bit parts of the dividend
1.62 + * div - 48-bit divisor
1.63 + *
1.64 + * Returns: lowest 64 bits of the result as a return value and highest 64
1.65 + * bits of the result to "result_hi" pointer
1.66 + */
1.67 +
1.68 +/* grade-school unsigned division (128-bit by 48-bit) with rounding to nearest */
1.69 +static force_inline uint64_t
1.70 +rounded_udiv_128_by_48 (uint64_t hi,
1.71 + uint64_t lo,
1.72 + uint64_t div,
1.73 + uint64_t *result_hi)
1.74 +{
1.75 + uint64_t tmp, remainder, result_lo;
1.76 + assert(div < ((uint64_t)1 << 48));
1.77 +
1.78 + remainder = hi % div;
1.79 + *result_hi = hi / div;
1.80 +
1.81 + tmp = (remainder << 16) + (lo >> 48);
1.82 + result_lo = tmp / div;
1.83 + remainder = tmp % div;
1.84 +
1.85 + tmp = (remainder << 16) + ((lo >> 32) & 0xFFFF);
1.86 + result_lo = (result_lo << 16) + (tmp / div);
1.87 + remainder = tmp % div;
1.88 +
1.89 + tmp = (remainder << 16) + ((lo >> 16) & 0xFFFF);
1.90 + result_lo = (result_lo << 16) + (tmp / div);
1.91 + remainder = tmp % div;
1.92 +
1.93 + tmp = (remainder << 16) + (lo & 0xFFFF);
1.94 + result_lo = (result_lo << 16) + (tmp / div);
1.95 + remainder = tmp % div;
1.96 +
1.97 + /* round to nearest */
1.98 + if (remainder * 2 >= div && ++result_lo == 0)
1.99 + *result_hi += 1;
1.100 +
1.101 + return result_lo;
1.102 +}
1.103 +
1.104 +/* signed division (128-bit by 49-bit) with rounding to nearest */
1.105 +static inline int64_t
1.106 +rounded_sdiv_128_by_49 (int64_t hi,
1.107 + uint64_t lo,
1.108 + int64_t div,
1.109 + int64_t *signed_result_hi)
1.110 +{
1.111 + uint64_t result_lo, result_hi;
1.112 + int sign = 0;
1.113 + if (div < 0)
1.114 + {
1.115 + div = -div;
1.116 + sign ^= 1;
1.117 + }
1.118 + if (hi < 0)
1.119 + {
1.120 + if (lo != 0)
1.121 + hi++;
1.122 + hi = -hi;
1.123 + lo = -lo;
1.124 + sign ^= 1;
1.125 + }
1.126 + result_lo = rounded_udiv_128_by_48 (hi, lo, div, &result_hi);
1.127 + if (sign)
1.128 + {
1.129 + if (result_lo != 0)
1.130 + result_hi++;
1.131 + result_hi = -result_hi;
1.132 + result_lo = -result_lo;
1.133 + }
1.134 + if (signed_result_hi)
1.135 + {
1.136 + *signed_result_hi = result_hi;
1.137 + }
1.138 + return result_lo;
1.139 +}
1.140 +
1.141 +/*
1.142 + * Multiply 64.16 fixed point value by (2^scalebits) and convert
1.143 + * to 128-bit integer.
1.144 + */
1.145 +static force_inline void
1.146 +fixed_64_16_to_int128 (int64_t hi,
1.147 + int64_t lo,
1.148 + int64_t *rhi,
1.149 + int64_t *rlo,
1.150 + int scalebits)
1.151 +{
1.152 + /* separate integer and fractional parts */
1.153 + hi += lo >> 16;
1.154 + lo &= 0xFFFF;
1.155 +
1.156 + if (scalebits <= 0)
1.157 + {
1.158 + *rlo = hi >> (-scalebits);
1.159 + *rhi = *rlo >> 63;
1.160 + }
1.161 + else
1.162 + {
1.163 + *rhi = hi >> (64 - scalebits);
1.164 + *rlo = (uint64_t)hi << scalebits;
1.165 + if (scalebits < 16)
1.166 + *rlo += lo >> (16 - scalebits);
1.167 + else
1.168 + *rlo += lo << (scalebits - 16);
1.169 + }
1.170 +}
1.171 +
1.172 +/*
1.173 + * Convert 112.16 fixed point value to 48.16 with clamping for the out
1.174 + * of range values.
1.175 + */
1.176 +static force_inline pixman_fixed_48_16_t
1.177 +fixed_112_16_to_fixed_48_16 (int64_t hi, int64_t lo, pixman_bool_t *clampflag)
1.178 +{
1.179 + if ((lo >> 63) != hi)
1.180 + {
1.181 + *clampflag = TRUE;
1.182 + return hi >= 0 ? INT64_MAX : INT64_MIN;
1.183 + }
1.184 + else
1.185 + {
1.186 + return lo;
1.187 + }
1.188 +}
1.189 +
1.190 +/*
1.191 + * Transform a point with 31.16 fixed point coordinates from the destination
1.192 + * space to a point with 48.16 fixed point coordinates in the source space.
1.193 + * No overflows are possible for affine transformations and the results are
1.194 + * accurate including the least significant bit. Projective transformations
1.195 + * may overflow, in this case the results are just clamped to return maximum
1.196 + * or minimum 48.16 values (so that the caller can at least handle the NONE
1.197 + * and PAD repeats correctly) and the return value is FALSE to indicate that
1.198 + * such clamping has happened.
1.199 + */
1.200 +PIXMAN_EXPORT pixman_bool_t
1.201 +pixman_transform_point_31_16 (const pixman_transform_t *t,
1.202 + const pixman_vector_48_16_t *v,
1.203 + pixman_vector_48_16_t *result)
1.204 +{
1.205 + pixman_bool_t clampflag = FALSE;
1.206 + int i;
1.207 + int64_t tmp[3][2], divint;
1.208 + uint16_t divfrac;
1.209 +
1.210 + /* input vector values must have no more than 31 bits (including sign)
1.211 + * in the integer part */
1.212 + assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.213 + assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.214 + assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.215 + assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.216 + assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.217 + assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.218 +
1.219 + for (i = 0; i < 3; i++)
1.220 + {
1.221 + tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
1.222 + tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
1.223 + tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
1.224 + tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
1.225 + tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
1.226 + tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF);
1.227 + }
1.228 +
1.229 + /*
1.230 + * separate 64-bit integer and 16-bit fractional parts for the divisor,
1.231 + * which is also scaled by 65536 after fixed point multiplication.
1.232 + */
1.233 + divint = tmp[2][0] + (tmp[2][1] >> 16);
1.234 + divfrac = tmp[2][1] & 0xFFFF;
1.235 +
1.236 + if (divint == pixman_fixed_1 && divfrac == 0)
1.237 + {
1.238 + /*
1.239 + * this is a simple affine transformation
1.240 + */
1.241 + result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
1.242 + result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
1.243 + result->v[2] = pixman_fixed_1;
1.244 + }
1.245 + else if (divint == 0 && divfrac == 0)
1.246 + {
1.247 + /*
1.248 + * handle zero divisor (if the values are non-zero, set the
1.249 + * results to maximum positive or minimum negative)
1.250 + */
1.251 + clampflag = TRUE;
1.252 +
1.253 + result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
1.254 + result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
1.255 +
1.256 + if (result->v[0] > 0)
1.257 + result->v[0] = INT64_MAX;
1.258 + else if (result->v[0] < 0)
1.259 + result->v[0] = INT64_MIN;
1.260 +
1.261 + if (result->v[1] > 0)
1.262 + result->v[1] = INT64_MAX;
1.263 + else if (result->v[1] < 0)
1.264 + result->v[1] = INT64_MIN;
1.265 + }
1.266 + else
1.267 + {
1.268 + /*
1.269 + * projective transformation, analyze the top 32 bits of the divisor
1.270 + */
1.271 + int32_t hi32divbits = divint >> 32;
1.272 + if (hi32divbits < 0)
1.273 + hi32divbits = ~hi32divbits;
1.274 +
1.275 + if (hi32divbits == 0)
1.276 + {
1.277 + /* the divisor is small, we can actually keep all the bits */
1.278 + int64_t hi, rhi, lo, rlo;
1.279 + int64_t div = (divint << 16) + divfrac;
1.280 +
1.281 + fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32);
1.282 + rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
1.283 + result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
1.284 +
1.285 + fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32);
1.286 + rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
1.287 + result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
1.288 + }
1.289 + else
1.290 + {
1.291 + /* the divisor needs to be reduced to 48 bits */
1.292 + int64_t hi, rhi, lo, rlo, div;
1.293 + int shift = 32 - count_leading_zeros (hi32divbits);
1.294 + fixed_64_16_to_int128 (divint, divfrac, &hi, &div, 16 - shift);
1.295 +
1.296 + fixed_64_16_to_int128 (tmp[0][0], tmp[0][1], &hi, &lo, 32 - shift);
1.297 + rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
1.298 + result->v[0] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
1.299 +
1.300 + fixed_64_16_to_int128 (tmp[1][0], tmp[1][1], &hi, &lo, 32 - shift);
1.301 + rlo = rounded_sdiv_128_by_49 (hi, lo, div, &rhi);
1.302 + result->v[1] = fixed_112_16_to_fixed_48_16 (rhi, rlo, &clampflag);
1.303 + }
1.304 + }
1.305 + result->v[2] = pixman_fixed_1;
1.306 + return !clampflag;
1.307 +}
1.308 +
1.309 +PIXMAN_EXPORT void
1.310 +pixman_transform_point_31_16_affine (const pixman_transform_t *t,
1.311 + const pixman_vector_48_16_t *v,
1.312 + pixman_vector_48_16_t *result)
1.313 +{
1.314 + int64_t hi0, lo0, hi1, lo1;
1.315 +
1.316 + /* input vector values must have no more than 31 bits (including sign)
1.317 + * in the integer part */
1.318 + assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.319 + assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.320 + assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.321 + assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.322 +
1.323 + hi0 = (int64_t)t->matrix[0][0] * (v->v[0] >> 16);
1.324 + lo0 = (int64_t)t->matrix[0][0] * (v->v[0] & 0xFFFF);
1.325 + hi0 += (int64_t)t->matrix[0][1] * (v->v[1] >> 16);
1.326 + lo0 += (int64_t)t->matrix[0][1] * (v->v[1] & 0xFFFF);
1.327 + hi0 += (int64_t)t->matrix[0][2];
1.328 +
1.329 + hi1 = (int64_t)t->matrix[1][0] * (v->v[0] >> 16);
1.330 + lo1 = (int64_t)t->matrix[1][0] * (v->v[0] & 0xFFFF);
1.331 + hi1 += (int64_t)t->matrix[1][1] * (v->v[1] >> 16);
1.332 + lo1 += (int64_t)t->matrix[1][1] * (v->v[1] & 0xFFFF);
1.333 + hi1 += (int64_t)t->matrix[1][2];
1.334 +
1.335 + result->v[0] = hi0 + ((lo0 + 0x8000) >> 16);
1.336 + result->v[1] = hi1 + ((lo1 + 0x8000) >> 16);
1.337 + result->v[2] = pixman_fixed_1;
1.338 +}
1.339 +
1.340 +PIXMAN_EXPORT void
1.341 +pixman_transform_point_31_16_3d (const pixman_transform_t *t,
1.342 + const pixman_vector_48_16_t *v,
1.343 + pixman_vector_48_16_t *result)
1.344 +{
1.345 + int i;
1.346 + int64_t tmp[3][2];
1.347 +
1.348 + /* input vector values must have no more than 31 bits (including sign)
1.349 + * in the integer part */
1.350 + assert (v->v[0] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.351 + assert (v->v[0] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.352 + assert (v->v[1] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.353 + assert (v->v[1] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.354 + assert (v->v[2] < ((pixman_fixed_48_16_t)1 << (30 + 16)));
1.355 + assert (v->v[2] >= -((pixman_fixed_48_16_t)1 << (30 + 16)));
1.356 +
1.357 + for (i = 0; i < 3; i++)
1.358 + {
1.359 + tmp[i][0] = (int64_t)t->matrix[i][0] * (v->v[0] >> 16);
1.360 + tmp[i][1] = (int64_t)t->matrix[i][0] * (v->v[0] & 0xFFFF);
1.361 + tmp[i][0] += (int64_t)t->matrix[i][1] * (v->v[1] >> 16);
1.362 + tmp[i][1] += (int64_t)t->matrix[i][1] * (v->v[1] & 0xFFFF);
1.363 + tmp[i][0] += (int64_t)t->matrix[i][2] * (v->v[2] >> 16);
1.364 + tmp[i][1] += (int64_t)t->matrix[i][2] * (v->v[2] & 0xFFFF);
1.365 + }
1.366 +
1.367 + result->v[0] = tmp[0][0] + ((tmp[0][1] + 0x8000) >> 16);
1.368 + result->v[1] = tmp[1][0] + ((tmp[1][1] + 0x8000) >> 16);
1.369 + result->v[2] = tmp[2][0] + ((tmp[2][1] + 0x8000) >> 16);
1.370 +}
1.371 +
1.372 +PIXMAN_EXPORT void
1.373 +pixman_transform_init_identity (struct pixman_transform *matrix)
1.374 +{
1.375 + int i;
1.376 +
1.377 + memset (matrix, '\0', sizeof (struct pixman_transform));
1.378 + for (i = 0; i < 3; i++)
1.379 + matrix->matrix[i][i] = F (1);
1.380 +}
1.381 +
1.382 +typedef pixman_fixed_32_32_t pixman_fixed_34_30_t;
1.383 +
1.384 +PIXMAN_EXPORT pixman_bool_t
1.385 +pixman_transform_point_3d (const struct pixman_transform *transform,
1.386 + struct pixman_vector * vector)
1.387 +{
1.388 + pixman_vector_48_16_t tmp;
1.389 + tmp.v[0] = vector->vector[0];
1.390 + tmp.v[1] = vector->vector[1];
1.391 + tmp.v[2] = vector->vector[2];
1.392 +
1.393 + pixman_transform_point_31_16_3d (transform, &tmp, &tmp);
1.394 +
1.395 + vector->vector[0] = tmp.v[0];
1.396 + vector->vector[1] = tmp.v[1];
1.397 + vector->vector[2] = tmp.v[2];
1.398 +
1.399 + return vector->vector[0] == tmp.v[0] &&
1.400 + vector->vector[1] == tmp.v[1] &&
1.401 + vector->vector[2] == tmp.v[2];
1.402 +}
1.403 +
1.404 +PIXMAN_EXPORT pixman_bool_t
1.405 +pixman_transform_point (const struct pixman_transform *transform,
1.406 + struct pixman_vector * vector)
1.407 +{
1.408 + pixman_vector_48_16_t tmp;
1.409 + tmp.v[0] = vector->vector[0];
1.410 + tmp.v[1] = vector->vector[1];
1.411 + tmp.v[2] = vector->vector[2];
1.412 +
1.413 + if (!pixman_transform_point_31_16 (transform, &tmp, &tmp))
1.414 + return FALSE;
1.415 +
1.416 + vector->vector[0] = tmp.v[0];
1.417 + vector->vector[1] = tmp.v[1];
1.418 + vector->vector[2] = tmp.v[2];
1.419 +
1.420 + return vector->vector[0] == tmp.v[0] &&
1.421 + vector->vector[1] == tmp.v[1] &&
1.422 + vector->vector[2] == tmp.v[2];
1.423 +}
1.424 +
1.425 +PIXMAN_EXPORT pixman_bool_t
1.426 +pixman_transform_multiply (struct pixman_transform * dst,
1.427 + const struct pixman_transform *l,
1.428 + const struct pixman_transform *r)
1.429 +{
1.430 + struct pixman_transform d;
1.431 + int dx, dy;
1.432 + int o;
1.433 +
1.434 + for (dy = 0; dy < 3; dy++)
1.435 + {
1.436 + for (dx = 0; dx < 3; dx++)
1.437 + {
1.438 + pixman_fixed_48_16_t v;
1.439 + pixman_fixed_32_32_t partial;
1.440 +
1.441 + v = 0;
1.442 + for (o = 0; o < 3; o++)
1.443 + {
1.444 + partial =
1.445 + (pixman_fixed_32_32_t) l->matrix[dy][o] *
1.446 + (pixman_fixed_32_32_t) r->matrix[o][dx];
1.447 +
1.448 + v += (partial + 0x8000) >> 16;
1.449 + }
1.450 +
1.451 + if (v > pixman_max_fixed_48_16 || v < pixman_min_fixed_48_16)
1.452 + return FALSE;
1.453 +
1.454 + d.matrix[dy][dx] = (pixman_fixed_t) v;
1.455 + }
1.456 + }
1.457 +
1.458 + *dst = d;
1.459 + return TRUE;
1.460 +}
1.461 +
1.462 +PIXMAN_EXPORT void
1.463 +pixman_transform_init_scale (struct pixman_transform *t,
1.464 + pixman_fixed_t sx,
1.465 + pixman_fixed_t sy)
1.466 +{
1.467 + memset (t, '\0', sizeof (struct pixman_transform));
1.468 +
1.469 + t->matrix[0][0] = sx;
1.470 + t->matrix[1][1] = sy;
1.471 + t->matrix[2][2] = F (1);
1.472 +}
1.473 +
1.474 +static pixman_fixed_t
1.475 +fixed_inverse (pixman_fixed_t x)
1.476 +{
1.477 + return (pixman_fixed_t) ((((pixman_fixed_48_16_t) F (1)) * F (1)) / x);
1.478 +}
1.479 +
1.480 +PIXMAN_EXPORT pixman_bool_t
1.481 +pixman_transform_scale (struct pixman_transform *forward,
1.482 + struct pixman_transform *reverse,
1.483 + pixman_fixed_t sx,
1.484 + pixman_fixed_t sy)
1.485 +{
1.486 + struct pixman_transform t;
1.487 +
1.488 + if (sx == 0 || sy == 0)
1.489 + return FALSE;
1.490 +
1.491 + if (forward)
1.492 + {
1.493 + pixman_transform_init_scale (&t, sx, sy);
1.494 + if (!pixman_transform_multiply (forward, &t, forward))
1.495 + return FALSE;
1.496 + }
1.497 +
1.498 + if (reverse)
1.499 + {
1.500 + pixman_transform_init_scale (&t, fixed_inverse (sx),
1.501 + fixed_inverse (sy));
1.502 + if (!pixman_transform_multiply (reverse, reverse, &t))
1.503 + return FALSE;
1.504 + }
1.505 +
1.506 + return TRUE;
1.507 +}
1.508 +
1.509 +PIXMAN_EXPORT void
1.510 +pixman_transform_init_rotate (struct pixman_transform *t,
1.511 + pixman_fixed_t c,
1.512 + pixman_fixed_t s)
1.513 +{
1.514 + memset (t, '\0', sizeof (struct pixman_transform));
1.515 +
1.516 + t->matrix[0][0] = c;
1.517 + t->matrix[0][1] = -s;
1.518 + t->matrix[1][0] = s;
1.519 + t->matrix[1][1] = c;
1.520 + t->matrix[2][2] = F (1);
1.521 +}
1.522 +
1.523 +PIXMAN_EXPORT pixman_bool_t
1.524 +pixman_transform_rotate (struct pixman_transform *forward,
1.525 + struct pixman_transform *reverse,
1.526 + pixman_fixed_t c,
1.527 + pixman_fixed_t s)
1.528 +{
1.529 + struct pixman_transform t;
1.530 +
1.531 + if (forward)
1.532 + {
1.533 + pixman_transform_init_rotate (&t, c, s);
1.534 + if (!pixman_transform_multiply (forward, &t, forward))
1.535 + return FALSE;
1.536 + }
1.537 +
1.538 + if (reverse)
1.539 + {
1.540 + pixman_transform_init_rotate (&t, c, -s);
1.541 + if (!pixman_transform_multiply (reverse, reverse, &t))
1.542 + return FALSE;
1.543 + }
1.544 +
1.545 + return TRUE;
1.546 +}
1.547 +
1.548 +PIXMAN_EXPORT void
1.549 +pixman_transform_init_translate (struct pixman_transform *t,
1.550 + pixman_fixed_t tx,
1.551 + pixman_fixed_t ty)
1.552 +{
1.553 + memset (t, '\0', sizeof (struct pixman_transform));
1.554 +
1.555 + t->matrix[0][0] = F (1);
1.556 + t->matrix[0][2] = tx;
1.557 + t->matrix[1][1] = F (1);
1.558 + t->matrix[1][2] = ty;
1.559 + t->matrix[2][2] = F (1);
1.560 +}
1.561 +
1.562 +PIXMAN_EXPORT pixman_bool_t
1.563 +pixman_transform_translate (struct pixman_transform *forward,
1.564 + struct pixman_transform *reverse,
1.565 + pixman_fixed_t tx,
1.566 + pixman_fixed_t ty)
1.567 +{
1.568 + struct pixman_transform t;
1.569 +
1.570 + if (forward)
1.571 + {
1.572 + pixman_transform_init_translate (&t, tx, ty);
1.573 +
1.574 + if (!pixman_transform_multiply (forward, &t, forward))
1.575 + return FALSE;
1.576 + }
1.577 +
1.578 + if (reverse)
1.579 + {
1.580 + pixman_transform_init_translate (&t, -tx, -ty);
1.581 +
1.582 + if (!pixman_transform_multiply (reverse, reverse, &t))
1.583 + return FALSE;
1.584 + }
1.585 + return TRUE;
1.586 +}
1.587 +
1.588 +PIXMAN_EXPORT pixman_bool_t
1.589 +pixman_transform_bounds (const struct pixman_transform *matrix,
1.590 + struct pixman_box16 * b)
1.591 +
1.592 +{
1.593 + struct pixman_vector v[4];
1.594 + int i;
1.595 + int x1, y1, x2, y2;
1.596 +
1.597 + v[0].vector[0] = F (b->x1);
1.598 + v[0].vector[1] = F (b->y1);
1.599 + v[0].vector[2] = F (1);
1.600 +
1.601 + v[1].vector[0] = F (b->x2);
1.602 + v[1].vector[1] = F (b->y1);
1.603 + v[1].vector[2] = F (1);
1.604 +
1.605 + v[2].vector[0] = F (b->x2);
1.606 + v[2].vector[1] = F (b->y2);
1.607 + v[2].vector[2] = F (1);
1.608 +
1.609 + v[3].vector[0] = F (b->x1);
1.610 + v[3].vector[1] = F (b->y2);
1.611 + v[3].vector[2] = F (1);
1.612 +
1.613 + for (i = 0; i < 4; i++)
1.614 + {
1.615 + if (!pixman_transform_point (matrix, &v[i]))
1.616 + return FALSE;
1.617 +
1.618 + x1 = pixman_fixed_to_int (v[i].vector[0]);
1.619 + y1 = pixman_fixed_to_int (v[i].vector[1]);
1.620 + x2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[0]));
1.621 + y2 = pixman_fixed_to_int (pixman_fixed_ceil (v[i].vector[1]));
1.622 +
1.623 + if (i == 0)
1.624 + {
1.625 + b->x1 = x1;
1.626 + b->y1 = y1;
1.627 + b->x2 = x2;
1.628 + b->y2 = y2;
1.629 + }
1.630 + else
1.631 + {
1.632 + if (x1 < b->x1) b->x1 = x1;
1.633 + if (y1 < b->y1) b->y1 = y1;
1.634 + if (x2 > b->x2) b->x2 = x2;
1.635 + if (y2 > b->y2) b->y2 = y2;
1.636 + }
1.637 + }
1.638 +
1.639 + return TRUE;
1.640 +}
1.641 +
1.642 +PIXMAN_EXPORT pixman_bool_t
1.643 +pixman_transform_invert (struct pixman_transform * dst,
1.644 + const struct pixman_transform *src)
1.645 +{
1.646 + struct pixman_f_transform m;
1.647 +
1.648 + pixman_f_transform_from_pixman_transform (&m, src);
1.649 +
1.650 + if (!pixman_f_transform_invert (&m, &m))
1.651 + return FALSE;
1.652 +
1.653 + if (!pixman_transform_from_pixman_f_transform (dst, &m))
1.654 + return FALSE;
1.655 +
1.656 + return TRUE;
1.657 +}
1.658 +
1.659 +static pixman_bool_t
1.660 +within_epsilon (pixman_fixed_t a,
1.661 + pixman_fixed_t b,
1.662 + pixman_fixed_t epsilon)
1.663 +{
1.664 + pixman_fixed_t t = a - b;
1.665 +
1.666 + if (t < 0)
1.667 + t = -t;
1.668 +
1.669 + return t <= epsilon;
1.670 +}
1.671 +
1.672 +#define EPSILON (pixman_fixed_t) (2)
1.673 +
1.674 +#define IS_SAME(a, b) (within_epsilon (a, b, EPSILON))
1.675 +#define IS_ZERO(a) (within_epsilon (a, 0, EPSILON))
1.676 +#define IS_ONE(a) (within_epsilon (a, F (1), EPSILON))
1.677 +#define IS_UNIT(a) \
1.678 + (within_epsilon (a, F (1), EPSILON) || \
1.679 + within_epsilon (a, F (-1), EPSILON) || \
1.680 + IS_ZERO (a))
1.681 +#define IS_INT(a) (IS_ZERO (pixman_fixed_frac (a)))
1.682 +
1.683 +PIXMAN_EXPORT pixman_bool_t
1.684 +pixman_transform_is_identity (const struct pixman_transform *t)
1.685 +{
1.686 + return (IS_SAME (t->matrix[0][0], t->matrix[1][1]) &&
1.687 + IS_SAME (t->matrix[0][0], t->matrix[2][2]) &&
1.688 + !IS_ZERO (t->matrix[0][0]) &&
1.689 + IS_ZERO (t->matrix[0][1]) &&
1.690 + IS_ZERO (t->matrix[0][2]) &&
1.691 + IS_ZERO (t->matrix[1][0]) &&
1.692 + IS_ZERO (t->matrix[1][2]) &&
1.693 + IS_ZERO (t->matrix[2][0]) &&
1.694 + IS_ZERO (t->matrix[2][1]));
1.695 +}
1.696 +
1.697 +PIXMAN_EXPORT pixman_bool_t
1.698 +pixman_transform_is_scale (const struct pixman_transform *t)
1.699 +{
1.700 + return (!IS_ZERO (t->matrix[0][0]) &&
1.701 + IS_ZERO (t->matrix[0][1]) &&
1.702 + IS_ZERO (t->matrix[0][2]) &&
1.703 +
1.704 + IS_ZERO (t->matrix[1][0]) &&
1.705 + !IS_ZERO (t->matrix[1][1]) &&
1.706 + IS_ZERO (t->matrix[1][2]) &&
1.707 +
1.708 + IS_ZERO (t->matrix[2][0]) &&
1.709 + IS_ZERO (t->matrix[2][1]) &&
1.710 + !IS_ZERO (t->matrix[2][2]));
1.711 +}
1.712 +
1.713 +PIXMAN_EXPORT pixman_bool_t
1.714 +pixman_transform_is_int_translate (const struct pixman_transform *t)
1.715 +{
1.716 + return (IS_ONE (t->matrix[0][0]) &&
1.717 + IS_ZERO (t->matrix[0][1]) &&
1.718 + IS_INT (t->matrix[0][2]) &&
1.719 +
1.720 + IS_ZERO (t->matrix[1][0]) &&
1.721 + IS_ONE (t->matrix[1][1]) &&
1.722 + IS_INT (t->matrix[1][2]) &&
1.723 +
1.724 + IS_ZERO (t->matrix[2][0]) &&
1.725 + IS_ZERO (t->matrix[2][1]) &&
1.726 + IS_ONE (t->matrix[2][2]));
1.727 +}
1.728 +
1.729 +PIXMAN_EXPORT pixman_bool_t
1.730 +pixman_transform_is_inverse (const struct pixman_transform *a,
1.731 + const struct pixman_transform *b)
1.732 +{
1.733 + struct pixman_transform t;
1.734 +
1.735 + if (!pixman_transform_multiply (&t, a, b))
1.736 + return FALSE;
1.737 +
1.738 + return pixman_transform_is_identity (&t);
1.739 +}
1.740 +
1.741 +PIXMAN_EXPORT void
1.742 +pixman_f_transform_from_pixman_transform (struct pixman_f_transform * ft,
1.743 + const struct pixman_transform *t)
1.744 +{
1.745 + int i, j;
1.746 +
1.747 + for (j = 0; j < 3; j++)
1.748 + {
1.749 + for (i = 0; i < 3; i++)
1.750 + ft->m[j][i] = pixman_fixed_to_double (t->matrix[j][i]);
1.751 + }
1.752 +}
1.753 +
1.754 +PIXMAN_EXPORT pixman_bool_t
1.755 +pixman_transform_from_pixman_f_transform (struct pixman_transform * t,
1.756 + const struct pixman_f_transform *ft)
1.757 +{
1.758 + int i, j;
1.759 +
1.760 + for (j = 0; j < 3; j++)
1.761 + {
1.762 + for (i = 0; i < 3; i++)
1.763 + {
1.764 + double d = ft->m[j][i];
1.765 + if (d < -32767.0 || d > 32767.0)
1.766 + return FALSE;
1.767 + d = d * 65536.0 + 0.5;
1.768 + t->matrix[j][i] = (pixman_fixed_t) floor (d);
1.769 + }
1.770 + }
1.771 +
1.772 + return TRUE;
1.773 +}
1.774 +
1.775 +PIXMAN_EXPORT pixman_bool_t
1.776 +pixman_f_transform_invert (struct pixman_f_transform * dst,
1.777 + const struct pixman_f_transform *src)
1.778 +{
1.779 + static const int a[3] = { 2, 2, 1 };
1.780 + static const int b[3] = { 1, 0, 0 };
1.781 + pixman_f_transform_t d;
1.782 + double det;
1.783 + int i, j;
1.784 +
1.785 + det = 0;
1.786 + for (i = 0; i < 3; i++)
1.787 + {
1.788 + double p;
1.789 + int ai = a[i];
1.790 + int bi = b[i];
1.791 + p = src->m[i][0] * (src->m[ai][2] * src->m[bi][1] -
1.792 + src->m[ai][1] * src->m[bi][2]);
1.793 + if (i == 1)
1.794 + p = -p;
1.795 + det += p;
1.796 + }
1.797 +
1.798 + if (det == 0)
1.799 + return FALSE;
1.800 +
1.801 + det = 1 / det;
1.802 + for (j = 0; j < 3; j++)
1.803 + {
1.804 + for (i = 0; i < 3; i++)
1.805 + {
1.806 + double p;
1.807 + int ai = a[i];
1.808 + int aj = a[j];
1.809 + int bi = b[i];
1.810 + int bj = b[j];
1.811 +
1.812 + p = (src->m[ai][aj] * src->m[bi][bj] -
1.813 + src->m[ai][bj] * src->m[bi][aj]);
1.814 +
1.815 + if (((i + j) & 1) != 0)
1.816 + p = -p;
1.817 +
1.818 + d.m[j][i] = det * p;
1.819 + }
1.820 + }
1.821 +
1.822 + *dst = d;
1.823 +
1.824 + return TRUE;
1.825 +}
1.826 +
1.827 +PIXMAN_EXPORT pixman_bool_t
1.828 +pixman_f_transform_point (const struct pixman_f_transform *t,
1.829 + struct pixman_f_vector * v)
1.830 +{
1.831 + struct pixman_f_vector result;
1.832 + int i, j;
1.833 + double a;
1.834 +
1.835 + for (j = 0; j < 3; j++)
1.836 + {
1.837 + a = 0;
1.838 + for (i = 0; i < 3; i++)
1.839 + a += t->m[j][i] * v->v[i];
1.840 + result.v[j] = a;
1.841 + }
1.842 +
1.843 + if (!result.v[2])
1.844 + return FALSE;
1.845 +
1.846 + for (j = 0; j < 2; j++)
1.847 + v->v[j] = result.v[j] / result.v[2];
1.848 +
1.849 + v->v[2] = 1;
1.850 +
1.851 + return TRUE;
1.852 +}
1.853 +
1.854 +PIXMAN_EXPORT void
1.855 +pixman_f_transform_point_3d (const struct pixman_f_transform *t,
1.856 + struct pixman_f_vector * v)
1.857 +{
1.858 + struct pixman_f_vector result;
1.859 + int i, j;
1.860 + double a;
1.861 +
1.862 + for (j = 0; j < 3; j++)
1.863 + {
1.864 + a = 0;
1.865 + for (i = 0; i < 3; i++)
1.866 + a += t->m[j][i] * v->v[i];
1.867 + result.v[j] = a;
1.868 + }
1.869 +
1.870 + *v = result;
1.871 +}
1.872 +
1.873 +PIXMAN_EXPORT void
1.874 +pixman_f_transform_multiply (struct pixman_f_transform * dst,
1.875 + const struct pixman_f_transform *l,
1.876 + const struct pixman_f_transform *r)
1.877 +{
1.878 + struct pixman_f_transform d;
1.879 + int dx, dy;
1.880 + int o;
1.881 +
1.882 + for (dy = 0; dy < 3; dy++)
1.883 + {
1.884 + for (dx = 0; dx < 3; dx++)
1.885 + {
1.886 + double v = 0;
1.887 + for (o = 0; o < 3; o++)
1.888 + v += l->m[dy][o] * r->m[o][dx];
1.889 + d.m[dy][dx] = v;
1.890 + }
1.891 + }
1.892 +
1.893 + *dst = d;
1.894 +}
1.895 +
1.896 +PIXMAN_EXPORT void
1.897 +pixman_f_transform_init_scale (struct pixman_f_transform *t,
1.898 + double sx,
1.899 + double sy)
1.900 +{
1.901 + t->m[0][0] = sx;
1.902 + t->m[0][1] = 0;
1.903 + t->m[0][2] = 0;
1.904 + t->m[1][0] = 0;
1.905 + t->m[1][1] = sy;
1.906 + t->m[1][2] = 0;
1.907 + t->m[2][0] = 0;
1.908 + t->m[2][1] = 0;
1.909 + t->m[2][2] = 1;
1.910 +}
1.911 +
1.912 +PIXMAN_EXPORT pixman_bool_t
1.913 +pixman_f_transform_scale (struct pixman_f_transform *forward,
1.914 + struct pixman_f_transform *reverse,
1.915 + double sx,
1.916 + double sy)
1.917 +{
1.918 + struct pixman_f_transform t;
1.919 +
1.920 + if (sx == 0 || sy == 0)
1.921 + return FALSE;
1.922 +
1.923 + if (forward)
1.924 + {
1.925 + pixman_f_transform_init_scale (&t, sx, sy);
1.926 + pixman_f_transform_multiply (forward, &t, forward);
1.927 + }
1.928 +
1.929 + if (reverse)
1.930 + {
1.931 + pixman_f_transform_init_scale (&t, 1 / sx, 1 / sy);
1.932 + pixman_f_transform_multiply (reverse, reverse, &t);
1.933 + }
1.934 +
1.935 + return TRUE;
1.936 +}
1.937 +
1.938 +PIXMAN_EXPORT void
1.939 +pixman_f_transform_init_rotate (struct pixman_f_transform *t,
1.940 + double c,
1.941 + double s)
1.942 +{
1.943 + t->m[0][0] = c;
1.944 + t->m[0][1] = -s;
1.945 + t->m[0][2] = 0;
1.946 + t->m[1][0] = s;
1.947 + t->m[1][1] = c;
1.948 + t->m[1][2] = 0;
1.949 + t->m[2][0] = 0;
1.950 + t->m[2][1] = 0;
1.951 + t->m[2][2] = 1;
1.952 +}
1.953 +
1.954 +PIXMAN_EXPORT pixman_bool_t
1.955 +pixman_f_transform_rotate (struct pixman_f_transform *forward,
1.956 + struct pixman_f_transform *reverse,
1.957 + double c,
1.958 + double s)
1.959 +{
1.960 + struct pixman_f_transform t;
1.961 +
1.962 + if (forward)
1.963 + {
1.964 + pixman_f_transform_init_rotate (&t, c, s);
1.965 + pixman_f_transform_multiply (forward, &t, forward);
1.966 + }
1.967 +
1.968 + if (reverse)
1.969 + {
1.970 + pixman_f_transform_init_rotate (&t, c, -s);
1.971 + pixman_f_transform_multiply (reverse, reverse, &t);
1.972 + }
1.973 +
1.974 + return TRUE;
1.975 +}
1.976 +
1.977 +PIXMAN_EXPORT void
1.978 +pixman_f_transform_init_translate (struct pixman_f_transform *t,
1.979 + double tx,
1.980 + double ty)
1.981 +{
1.982 + t->m[0][0] = 1;
1.983 + t->m[0][1] = 0;
1.984 + t->m[0][2] = tx;
1.985 + t->m[1][0] = 0;
1.986 + t->m[1][1] = 1;
1.987 + t->m[1][2] = ty;
1.988 + t->m[2][0] = 0;
1.989 + t->m[2][1] = 0;
1.990 + t->m[2][2] = 1;
1.991 +}
1.992 +
1.993 +PIXMAN_EXPORT pixman_bool_t
1.994 +pixman_f_transform_translate (struct pixman_f_transform *forward,
1.995 + struct pixman_f_transform *reverse,
1.996 + double tx,
1.997 + double ty)
1.998 +{
1.999 + struct pixman_f_transform t;
1.1000 +
1.1001 + if (forward)
1.1002 + {
1.1003 + pixman_f_transform_init_translate (&t, tx, ty);
1.1004 + pixman_f_transform_multiply (forward, &t, forward);
1.1005 + }
1.1006 +
1.1007 + if (reverse)
1.1008 + {
1.1009 + pixman_f_transform_init_translate (&t, -tx, -ty);
1.1010 + pixman_f_transform_multiply (reverse, reverse, &t);
1.1011 + }
1.1012 +
1.1013 + return TRUE;
1.1014 +}
1.1015 +
1.1016 +PIXMAN_EXPORT pixman_bool_t
1.1017 +pixman_f_transform_bounds (const struct pixman_f_transform *t,
1.1018 + struct pixman_box16 * b)
1.1019 +{
1.1020 + struct pixman_f_vector v[4];
1.1021 + int i;
1.1022 + int x1, y1, x2, y2;
1.1023 +
1.1024 + v[0].v[0] = b->x1;
1.1025 + v[0].v[1] = b->y1;
1.1026 + v[0].v[2] = 1;
1.1027 + v[1].v[0] = b->x2;
1.1028 + v[1].v[1] = b->y1;
1.1029 + v[1].v[2] = 1;
1.1030 + v[2].v[0] = b->x2;
1.1031 + v[2].v[1] = b->y2;
1.1032 + v[2].v[2] = 1;
1.1033 + v[3].v[0] = b->x1;
1.1034 + v[3].v[1] = b->y2;
1.1035 + v[3].v[2] = 1;
1.1036 +
1.1037 + for (i = 0; i < 4; i++)
1.1038 + {
1.1039 + if (!pixman_f_transform_point (t, &v[i]))
1.1040 + return FALSE;
1.1041 +
1.1042 + x1 = floor (v[i].v[0]);
1.1043 + y1 = floor (v[i].v[1]);
1.1044 + x2 = ceil (v[i].v[0]);
1.1045 + y2 = ceil (v[i].v[1]);
1.1046 +
1.1047 + if (i == 0)
1.1048 + {
1.1049 + b->x1 = x1;
1.1050 + b->y1 = y1;
1.1051 + b->x2 = x2;
1.1052 + b->y2 = y2;
1.1053 + }
1.1054 + else
1.1055 + {
1.1056 + if (x1 < b->x1) b->x1 = x1;
1.1057 + if (y1 < b->y1) b->y1 = y1;
1.1058 + if (x2 > b->x2) b->x2 = x2;
1.1059 + if (y2 > b->y2) b->y2 = y2;
1.1060 + }
1.1061 + }
1.1062 +
1.1063 + return TRUE;
1.1064 +}
1.1065 +
1.1066 +PIXMAN_EXPORT void
1.1067 +pixman_f_transform_init_identity (struct pixman_f_transform *t)
1.1068 +{
1.1069 + int i, j;
1.1070 +
1.1071 + for (j = 0; j < 3; j++)
1.1072 + {
1.1073 + for (i = 0; i < 3; i++)
1.1074 + t->m[j][i] = i == j ? 1 : 0;
1.1075 + }
1.1076 +}
