qemu/pixman/pixman/pixman-matrix.c

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