src/third_party/skia/src/core/SkMatrix.cpp

   1 /*
   2  * Copyright 2006 The Android Open Source Project
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #include "SkMatrix.h"
   9 #include "Sk64.h"
  10 #include "SkFloatBits.h"
  11 #include "SkOnce.h"
  12 #include "SkScalarCompare.h"
  13 #include "SkString.h"
  14
  15 #ifdef SK_SCALAR_IS_FLOAT
  16     #define kMatrix22Elem   SK_Scalar1
  17
  18     static inline float SkDoubleToFloat(double x) {
  19         return static_cast<float>(x);
  20     }
  21 #else
  22     #define kMatrix22Elem   SK_Fract1
  23 #endif
  24
  25 /*      [scale-x    skew-x      trans-x]   [X]   [X']
  26         [skew-y     scale-y     trans-y] * [Y] = [Y']
  27         [persp-0    persp-1     persp-2]   [1]   [1 ]
  28 */
  29
  30 void SkMatrix::reset() {
  31     fMat[kMScaleX] = fMat[kMScaleY] = SK_Scalar1;
  32     fMat[kMSkewX]  = fMat[kMSkewY] =
  33     fMat[kMTransX] = fMat[kMTransY] =
  34     fMat[kMPersp0] = fMat[kMPersp1] = 0;
  35     fMat[kMPersp2] = kMatrix22Elem;
  36
  37     this->setTypeMask(kIdentity_Mask | kRectStaysRect_Mask);
  38 }
  39
  40 // this guy aligns with the masks, so we can compute a mask from a varaible 0/1
  41 enum {
  42     kTranslate_Shift,
  43     kScale_Shift,
  44     kAffine_Shift,
  45     kPerspective_Shift,
  46     kRectStaysRect_Shift
  47 };
  48
  49 #ifdef SK_SCALAR_IS_FLOAT
  50     static const int32_t kScalar1Int = 0x3f800000;
  51 #else
  52     #define scalarAsInt(x)  (x)
  53     static const int32_t kScalar1Int = (1 << 16);
  54     static const int32_t kPersp1Int  = (1 << 30);
  55 #endif
  56
  57 uint8_t SkMatrix::computePerspectiveTypeMask() const {
  58 #ifdef SK_SCALAR_SLOW_COMPARES
  59     if (SkScalarAs2sCompliment(fMat[kMPersp0]) |
  60             SkScalarAs2sCompliment(fMat[kMPersp1]) |
  61             (SkScalarAs2sCompliment(fMat[kMPersp2]) - kPersp1Int)) {
  62         return SkToU8(kORableMasks);
  63     }
  64 #else
  65     // Benchmarking suggests that replacing this set of SkScalarAs2sCompliment
  66     // is a win, but replacing those below is not. We don't yet understand
  67     // that result.
  68     if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 ||
  69         fMat[kMPersp2] != kMatrix22Elem) {
  70         // If this is a perspective transform, we return true for all other
  71         // transform flags - this does not disable any optimizations, respects
  72         // the rule that the type mask must be conservative, and speeds up
  73         // type mask computation.
  74         return SkToU8(kORableMasks);
  75     }
  76 #endif
  77
  78     return SkToU8(kOnlyPerspectiveValid_Mask | kUnknown_Mask);
  79 }
  80
  81 uint8_t SkMatrix::computeTypeMask() const {
  82     unsigned mask = 0;
  83
  84 #ifdef SK_SCALAR_SLOW_COMPARES
  85     if (SkScalarAs2sCompliment(fMat[kMPersp0]) |
  86             SkScalarAs2sCompliment(fMat[kMPersp1]) |
  87             (SkScalarAs2sCompliment(fMat[kMPersp2]) - kPersp1Int)) {
  88         return SkToU8(kORableMasks);
  89     }
  90
  91     if (SkScalarAs2sCompliment(fMat[kMTransX]) |
  92             SkScalarAs2sCompliment(fMat[kMTransY])) {
  93         mask |= kTranslate_Mask;
  94     }
  95 #else
  96     if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 ||
  97         fMat[kMPersp2] != kMatrix22Elem) {
  98         // Once it is determined that that this is a perspective transform,
  99         // all other flags are moot as far as optimizations are concerned.
 100         return SkToU8(kORableMasks);
 101     }
 102
 103     if (fMat[kMTransX] != 0 || fMat[kMTransY] != 0) {
 104         mask |= kTranslate_Mask;
 105     }
 106 #endif
 107
 108     int m00 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleX]);
 109     int m01 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewX]);
 110     int m10 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewY]);
 111     int m11 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleY]);
 112
 113     if (m01 | m10) {
 114         // The skew components may be scale-inducing, unless we are dealing
 115         // with a pure rotation.  Testing for a pure rotation is expensive,
 116         // so we opt for being conservative by always setting the scale bit.
 117         // along with affine.
 118         // By doing this, we are also ensuring that matrices have the same
 119         // type masks as their inverses.
 120         mask |= kAffine_Mask | kScale_Mask;
 121
 122         // For rectStaysRect, in the affine case, we only need check that
 123         // the primary diagonal is all zeros and that the secondary diagonal
 124         // is all non-zero.
 125
 126         // map non-zero to 1
 127         m01 = m01 != 0;
 128         m10 = m10 != 0;
 129
 130         int dp0 = 0 == (m00 | m11) ;  // true if both are 0
 131         int ds1 = m01 & m10;        // true if both are 1
 132
 133         mask |= (dp0 & ds1) << kRectStaysRect_Shift;
 134     } else {
 135         // Only test for scale explicitly if not affine, since affine sets the
 136         // scale bit.
 137         if ((m00 - kScalar1Int) | (m11 - kScalar1Int)) {
 138             mask |= kScale_Mask;
 139         }
 140
 141         // Not affine, therefore we already know secondary diagonal is
 142         // all zeros, so we just need to check that primary diagonal is
 143         // all non-zero.
 144
 145         // map non-zero to 1
 146         m00 = m00 != 0;
 147         m11 = m11 != 0;
 148
 149         // record if the (p)rimary diagonal is all non-zero
 150         mask |= (m00 & m11) << kRectStaysRect_Shift;
 151     }
 152
 153     return SkToU8(mask);
 154 }
 155
 156 ///////////////////////////////////////////////////////////////////////////////
 157
 158 #ifdef SK_SCALAR_IS_FLOAT
 159
 160 bool operator==(const SkMatrix& a, const SkMatrix& b) {
 161     const SkScalar* SK_RESTRICT ma = a.fMat;
 162     const SkScalar* SK_RESTRICT mb = b.fMat;
 163
 164     return  ma[0] == mb[0] && ma[1] == mb[1] && ma[2] == mb[2] &&
 165             ma[3] == mb[3] && ma[4] == mb[4] && ma[5] == mb[5] &&
 166             ma[6] == mb[6] && ma[7] == mb[7] && ma[8] == mb[8];
 167 }
 168
 169 #endif
 170
 171 ///////////////////////////////////////////////////////////////////////////////
 172
 173 // helper function to determine if upper-left 2x2 of matrix is degenerate
 174 static inline bool is_degenerate_2x2(SkScalar scaleX, SkScalar skewX,
 175                                      SkScalar skewY,  SkScalar scaleY) {
 176     SkScalar perp_dot = scaleX*scaleY - skewX*skewY;
 177     return SkScalarNearlyZero(perp_dot, SK_ScalarNearlyZero*SK_ScalarNearlyZero);
 178 }
 179
 180 ///////////////////////////////////////////////////////////////////////////////
 181
 182 bool SkMatrix::isSimilarity(SkScalar tol) const {
 183     // if identity or translate matrix
 184     TypeMask mask = this->getType();
 185     if (mask <= kTranslate_Mask) {
 186         return true;
 187     }
 188     if (mask & kPerspective_Mask) {
 189         return false;
 190     }
 191
 192     SkScalar mx = fMat[kMScaleX];
 193     SkScalar my = fMat[kMScaleY];
 194     // if no skew, can just compare scale factors
 195     if (!(mask & kAffine_Mask)) {
 196         return !SkScalarNearlyZero(mx) && SkScalarNearlyEqual(SkScalarAbs(mx), SkScalarAbs(my));
 197     }
 198     SkScalar sx = fMat[kMSkewX];
 199     SkScalar sy = fMat[kMSkewY];
 200
 201     if (is_degenerate_2x2(mx, sx, sy, my)) {
 202         return false;
 203     }
 204
 205     // it has scales and skews, but it could also be rotation, check it out.
 206     SkVector vec[2];
 207     vec[0].set(mx, sx);
 208     vec[1].set(sy, my);
 209
 210     return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
 211            SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
 212                                SkScalarSquare(tol));
 213 }
 214
 215 bool SkMatrix::preservesRightAngles(SkScalar tol) const {
 216     TypeMask mask = this->getType();
 217
 218     if (mask <= (SkMatrix::kTranslate_Mask | SkMatrix::kScale_Mask)) {
 219         // identity, translate and/or scale
 220         return true;
 221     }
 222     if (mask & kPerspective_Mask) {
 223         return false;
 224     }
 225
 226     SkASSERT(mask & kAffine_Mask);
 227
 228     SkScalar mx = fMat[kMScaleX];
 229     SkScalar my = fMat[kMScaleY];
 230     SkScalar sx = fMat[kMSkewX];
 231     SkScalar sy = fMat[kMSkewY];
 232
 233     if (is_degenerate_2x2(mx, sx, sy, my)) {
 234         return false;
 235     }
 236
 237     // it has scales and skews, but it could also be rotation, check it out.
 238     SkVector vec[2];
 239     vec[0].set(mx, sx);
 240     vec[1].set(sy, my);
 241
 242     return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
 243            SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
 244                                SkScalarSquare(tol));
 245 }
 246
 247 ///////////////////////////////////////////////////////////////////////////////
 248
 249 void SkMatrix::setTranslate(SkScalar dx, SkScalar dy) {
 250     if (SkScalarToCompareType(dx) || SkScalarToCompareType(dy)) {
 251         fMat[kMTransX] = dx;
 252         fMat[kMTransY] = dy;
 253
 254         fMat[kMScaleX] = fMat[kMScaleY] = SK_Scalar1;
 255         fMat[kMSkewX]  = fMat[kMSkewY] =
 256         fMat[kMPersp0] = fMat[kMPersp1] = 0;
 257         fMat[kMPersp2] = kMatrix22Elem;
 258
 259         this->setTypeMask(kTranslate_Mask | kRectStaysRect_Mask);
 260     } else {
 261         this->reset();
 262     }
 263 }
 264
 265 bool SkMatrix::preTranslate(SkScalar dx, SkScalar dy) {
 266     if (this->hasPerspective()) {
 267         SkMatrix    m;
 268         m.setTranslate(dx, dy);
 269         return this->preConcat(m);
 270     }
 271
 272     if (SkScalarToCompareType(dx) || SkScalarToCompareType(dy)) {
 273         fMat[kMTransX] += SkScalarMul(fMat[kMScaleX], dx) +
 274                           SkScalarMul(fMat[kMSkewX], dy);
 275         fMat[kMTransY] += SkScalarMul(fMat[kMSkewY], dx) +
 276                           SkScalarMul(fMat[kMScaleY], dy);
 277
 278         this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
 279     }
 280     return true;
 281 }
 282
 283 bool SkMatrix::postTranslate(SkScalar dx, SkScalar dy) {
 284     if (this->hasPerspective()) {
 285         SkMatrix    m;
 286         m.setTranslate(dx, dy);
 287         return this->postConcat(m);
 288     }
 289
 290     if (SkScalarToCompareType(dx) || SkScalarToCompareType(dy)) {
 291         fMat[kMTransX] += dx;
 292         fMat[kMTransY] += dy;
 293         this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
 294     }
 295     return true;
 296 }
 297
 298 ///////////////////////////////////////////////////////////////////////////////
 299
 300 void SkMatrix::setScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
 301     if (SK_Scalar1 == sx && SK_Scalar1 == sy) {
 302         this->reset();
 303     } else {
 304         fMat[kMScaleX] = sx;
 305         fMat[kMScaleY] = sy;
 306         fMat[kMTransX] = px - SkScalarMul(sx, px);
 307         fMat[kMTransY] = py - SkScalarMul(sy, py);
 308         fMat[kMPersp2] = kMatrix22Elem;
 309
 310         fMat[kMSkewX]  = fMat[kMSkewY] =
 311         fMat[kMPersp0] = fMat[kMPersp1] = 0;
 312
 313         this->setTypeMask(kScale_Mask | kTranslate_Mask | kRectStaysRect_Mask);
 314     }
 315 }
 316
 317 void SkMatrix::setScale(SkScalar sx, SkScalar sy) {
 318     if (SK_Scalar1 == sx && SK_Scalar1 == sy) {
 319         this->reset();
 320     } else {
 321         fMat[kMScaleX] = sx;
 322         fMat[kMScaleY] = sy;
 323         fMat[kMPersp2] = kMatrix22Elem;
 324
 325         fMat[kMTransX] = fMat[kMTransY] =
 326         fMat[kMSkewX]  = fMat[kMSkewY] =
 327         fMat[kMPersp0] = fMat[kMPersp1] = 0;
 328
 329         this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
 330     }
 331 }
 332
 333 bool SkMatrix::setIDiv(int divx, int divy) {
 334     if (!divx || !divy) {
 335         return false;
 336     }
 337     this->setScale(SK_Scalar1 / divx, SK_Scalar1 / divy);
 338     return true;
 339 }
 340
 341 bool SkMatrix::preScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
 342     SkMatrix    m;
 343     m.setScale(sx, sy, px, py);
 344     return this->preConcat(m);
 345 }
 346
 347 bool SkMatrix::preScale(SkScalar sx, SkScalar sy) {
 348     if (SK_Scalar1 == sx && SK_Scalar1 == sy) {
 349         return true;
 350     }
 351
 352 #ifdef SK_SCALAR_IS_FIXED
 353     SkMatrix    m;
 354     m.setScale(sx, sy);
 355     return this->preConcat(m);
 356 #else
 357     // the assumption is that these multiplies are very cheap, and that
 358     // a full concat and/or just computing the matrix type is more expensive.
 359     // Also, the fixed-point case checks for overflow, but the float doesn't,
 360     // so we can get away with these blind multiplies.
 361
 362     fMat[kMScaleX] = SkScalarMul(fMat[kMScaleX], sx);
 363     fMat[kMSkewY] = SkScalarMul(fMat[kMSkewY],   sx);
 364     fMat[kMPersp0] = SkScalarMul(fMat[kMPersp0], sx);
 365
 366     fMat[kMSkewX] = SkScalarMul(fMat[kMSkewX],   sy);
 367     fMat[kMScaleY] = SkScalarMul(fMat[kMScaleY], sy);
 368     fMat[kMPersp1] = SkScalarMul(fMat[kMPersp1], sy);
 369
 370     this->orTypeMask(kScale_Mask);
 371     return true;
 372 #endif
 373 }
 374
 375 bool SkMatrix::postScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
 376     if (SK_Scalar1 == sx && SK_Scalar1 == sy) {
 377         return true;
 378     }
 379     SkMatrix    m;
 380     m.setScale(sx, sy, px, py);
 381     return this->postConcat(m);
 382 }
 383
 384 bool SkMatrix::postScale(SkScalar sx, SkScalar sy) {
 385     if (SK_Scalar1 == sx && SK_Scalar1 == sy) {
 386         return true;
 387     }
 388     SkMatrix    m;
 389     m.setScale(sx, sy);
 390     return this->postConcat(m);
 391 }
 392
 393 #ifdef SK_SCALAR_IS_FIXED
 394     static inline SkFixed roundidiv(SkFixed numer, int denom) {
 395         int ns = numer >> 31;
 396         int ds = denom >> 31;
 397         numer = (numer ^ ns) - ns;
 398         denom = (denom ^ ds) - ds;
 399
 400         SkFixed answer = (numer + (denom >> 1)) / denom;
 401         int as = ns ^ ds;
 402         return (answer ^ as) - as;
 403     }
 404 #endif
 405
 406 // this guy perhaps can go away, if we have a fract/high-precision way to
 407 // scale matrices
 408 bool SkMatrix::postIDiv(int divx, int divy) {
 409     if (divx == 0 || divy == 0) {
 410         return false;
 411     }
 412
 413 #ifdef SK_SCALAR_IS_FIXED
 414     fMat[kMScaleX] = roundidiv(fMat[kMScaleX], divx);
 415     fMat[kMSkewX]  = roundidiv(fMat[kMSkewX],  divx);
 416     fMat[kMTransX] = roundidiv(fMat[kMTransX], divx);
 417
 418     fMat[kMScaleY] = roundidiv(fMat[kMScaleY], divy);
 419     fMat[kMSkewY]  = roundidiv(fMat[kMSkewY],  divy);
 420     fMat[kMTransY] = roundidiv(fMat[kMTransY], divy);
 421 #else
 422     const float invX = 1.f / divx;
 423     const float invY = 1.f / divy;
 424
 425     fMat[kMScaleX] *= invX;
 426     fMat[kMSkewX]  *= invX;
 427     fMat[kMTransX] *= invX;
 428
 429     fMat[kMScaleY] *= invY;
 430     fMat[kMSkewY]  *= invY;
 431     fMat[kMTransY] *= invY;
 432 #endif
 433
 434     this->setTypeMask(kUnknown_Mask);
 435     return true;
 436 }
 437
 438 ////////////////////////////////////////////////////////////////////////////////////
 439
 440 void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV,
 441                          SkScalar px, SkScalar py) {
 442     const SkScalar oneMinusCosV = SK_Scalar1 - cosV;
 443
 444     fMat[kMScaleX]  = cosV;
 445     fMat[kMSkewX]   = -sinV;
 446     fMat[kMTransX]  = SkScalarMul(sinV, py) + SkScalarMul(oneMinusCosV, px);
 447
 448     fMat[kMSkewY]   = sinV;
 449     fMat[kMScaleY]  = cosV;
 450     fMat[kMTransY]  = SkScalarMul(-sinV, px) + SkScalarMul(oneMinusCosV, py);
 451
 452     fMat[kMPersp0] = fMat[kMPersp1] = 0;
 453     fMat[kMPersp2] = kMatrix22Elem;
 454
 455     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
 456 }
 457
 458 void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV) {
 459     fMat[kMScaleX]  = cosV;
 460     fMat[kMSkewX]   = -sinV;
 461     fMat[kMTransX]  = 0;
 462
 463     fMat[kMSkewY]   = sinV;
 464     fMat[kMScaleY]  = cosV;
 465     fMat[kMTransY]  = 0;
 466
 467     fMat[kMPersp0] = fMat[kMPersp1] = 0;
 468     fMat[kMPersp2] = kMatrix22Elem;
 469
 470     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
 471 }
 472
 473 void SkMatrix::setRotate(SkScalar degrees, SkScalar px, SkScalar py) {
 474     SkScalar sinV, cosV;
 475     sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
 476     this->setSinCos(sinV, cosV, px, py);
 477 }
 478
 479 void SkMatrix::setRotate(SkScalar degrees) {
 480     SkScalar sinV, cosV;
 481     sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
 482     this->setSinCos(sinV, cosV);
 483 }
 484
 485 bool SkMatrix::preRotate(SkScalar degrees, SkScalar px, SkScalar py) {
 486     SkMatrix    m;
 487     m.setRotate(degrees, px, py);
 488     return this->preConcat(m);
 489 }
 490
 491 bool SkMatrix::preRotate(SkScalar degrees) {
 492     SkMatrix    m;
 493     m.setRotate(degrees);
 494     return this->preConcat(m);
 495 }
 496
 497 bool SkMatrix::postRotate(SkScalar degrees, SkScalar px, SkScalar py) {
 498     SkMatrix    m;
 499     m.setRotate(degrees, px, py);
 500     return this->postConcat(m);
 501 }
 502
 503 bool SkMatrix::postRotate(SkScalar degrees) {
 504     SkMatrix    m;
 505     m.setRotate(degrees);
 506     return this->postConcat(m);
 507 }
 508
 509 ////////////////////////////////////////////////////////////////////////////////////
 510
 511 void SkMatrix::setSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
 512     fMat[kMScaleX]  = SK_Scalar1;
 513     fMat[kMSkewX]   = sx;
 514     fMat[kMTransX]  = SkScalarMul(-sx, py);
 515
 516     fMat[kMSkewY]   = sy;
 517     fMat[kMScaleY]  = SK_Scalar1;
 518     fMat[kMTransY]  = SkScalarMul(-sy, px);
 519
 520     fMat[kMPersp0] = fMat[kMPersp1] = 0;
 521     fMat[kMPersp2] = kMatrix22Elem;
 522
 523     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
 524 }
 525
 526 void SkMatrix::setSkew(SkScalar sx, SkScalar sy) {
 527     fMat[kMScaleX]  = SK_Scalar1;
 528     fMat[kMSkewX]   = sx;
 529     fMat[kMTransX]  = 0;
 530
 531     fMat[kMSkewY]   = sy;
 532     fMat[kMScaleY]  = SK_Scalar1;
 533     fMat[kMTransY]  = 0;
 534
 535     fMat[kMPersp0] = fMat[kMPersp1] = 0;
 536     fMat[kMPersp2] = kMatrix22Elem;
 537
 538     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
 539 }
 540
 541 bool SkMatrix::preSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
 542     SkMatrix    m;
 543     m.setSkew(sx, sy, px, py);
 544     return this->preConcat(m);
 545 }
 546
 547 bool SkMatrix::preSkew(SkScalar sx, SkScalar sy) {
 548     SkMatrix    m;
 549     m.setSkew(sx, sy);
 550     return this->preConcat(m);
 551 }
 552
 553 bool SkMatrix::postSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
 554     SkMatrix    m;
 555     m.setSkew(sx, sy, px, py);
 556     return this->postConcat(m);
 557 }
 558
 559 bool SkMatrix::postSkew(SkScalar sx, SkScalar sy) {
 560     SkMatrix    m;
 561     m.setSkew(sx, sy);
 562     return this->postConcat(m);
 563 }
 564
 565 ///////////////////////////////////////////////////////////////////////////////
 566
 567 bool SkMatrix::setRectToRect(const SkRect& src, const SkRect& dst,
 568                              ScaleToFit align)
 569 {
 570     if (src.isEmpty()) {
 571         this->reset();
 572         return false;
 573     }
 574
 575     if (dst.isEmpty()) {
 576         sk_bzero(fMat, 8 * sizeof(SkScalar));
 577         this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
 578     } else {
 579         SkScalar    tx, sx = SkScalarDiv(dst.width(), src.width());
 580         SkScalar    ty, sy = SkScalarDiv(dst.height(), src.height());
 581         bool        xLarger = false;
 582
 583         if (align != kFill_ScaleToFit) {
 584             if (sx > sy) {
 585                 xLarger = true;
 586                 sx = sy;
 587             } else {
 588                 sy = sx;
 589             }
 590         }
 591
 592         tx = dst.fLeft - SkScalarMul(src.fLeft, sx);
 593         ty = dst.fTop - SkScalarMul(src.fTop, sy);
 594         if (align == kCenter_ScaleToFit || align == kEnd_ScaleToFit) {
 595             SkScalar diff;
 596
 597             if (xLarger) {
 598                 diff = dst.width() - SkScalarMul(src.width(), sy);
 599             } else {
 600                 diff = dst.height() - SkScalarMul(src.height(), sy);
 601             }
 602
 603             if (align == kCenter_ScaleToFit) {
 604                 diff = SkScalarHalf(diff);
 605             }
 606
 607             if (xLarger) {
 608                 tx += diff;
 609             } else {
 610                 ty += diff;
 611             }
 612         }
 613
 614         fMat[kMScaleX] = sx;
 615         fMat[kMScaleY] = sy;
 616         fMat[kMTransX] = tx;
 617         fMat[kMTransY] = ty;
 618         fMat[kMSkewX]  = fMat[kMSkewY] =
 619         fMat[kMPersp0] = fMat[kMPersp1] = 0;
 620
 621         unsigned mask = kRectStaysRect_Mask;
 622         if (sx != SK_Scalar1 || sy != SK_Scalar1) {
 623             mask |= kScale_Mask;
 624         }
 625         if (tx || ty) {
 626             mask |= kTranslate_Mask;
 627         }
 628         this->setTypeMask(mask);
 629     }
 630     // shared cleanup
 631     fMat[kMPersp2] = kMatrix22Elem;
 632     return true;
 633 }
 634
 635 ///////////////////////////////////////////////////////////////////////////////
 636
 637 #ifdef SK_SCALAR_IS_FLOAT
 638     static inline int fixmuladdmul(float a, float b, float c, float d,
 639                                    float* result) {
 640         *result = SkDoubleToFloat((double)a * b + (double)c * d);
 641         return true;
 642     }
 643
 644     static inline bool rowcol3(const float row[], const float col[],
 645                                float* result) {
 646         *result = row[0] * col[0] + row[1] * col[3] + row[2] * col[6];
 647         return true;
 648     }
 649
 650     static inline int negifaddoverflows(float& result, float a, float b) {
 651         result = a + b;
 652         return 0;
 653     }
 654 #else
 655     static inline bool fixmuladdmul(SkFixed a, SkFixed b, SkFixed c, SkFixed d,
 656                                     SkFixed* result) {
 657         Sk64    tmp1, tmp2;
 658         tmp1.setMul(a, b);
 659         tmp2.setMul(c, d);
 660         tmp1.add(tmp2);
 661         if (tmp1.isFixed()) {
 662             *result = tmp1.getFixed();
 663             return true;
 664         }
 665         return false;
 666     }
 667
 668     static inline SkFixed fracmuladdmul(SkFixed a, SkFract b, SkFixed c,
 669                                         SkFract d) {
 670         Sk64 tmp1, tmp2;
 671         tmp1.setMul(a, b);
 672         tmp2.setMul(c, d);
 673         tmp1.add(tmp2);
 674         return tmp1.getFract();
 675     }
 676
 677     static inline bool rowcol3(const SkFixed row[], const SkFixed col[],
 678                                SkFixed* result) {
 679         Sk64 tmp1, tmp2;
 680
 681         tmp1.setMul(row[0], col[0]);    // N * fixed
 682         tmp2.setMul(row[1], col[3]);    // N * fixed
 683         tmp1.add(tmp2);
 684
 685         tmp2.setMul(row[2], col[6]);    // N * fract
 686         tmp2.roundRight(14);            // make it fixed
 687         tmp1.add(tmp2);
 688
 689         if (tmp1.isFixed()) {
 690             *result = tmp1.getFixed();
 691             return true;
 692         }
 693         return false;
 694     }
 695
 696     static inline int negifaddoverflows(SkFixed& result, SkFixed a, SkFixed b) {
 697         SkFixed c = a + b;
 698         result = c;
 699         return (c ^ a) & (c ^ b);
 700     }
 701 #endif
 702
 703 static void normalize_perspective(SkScalar mat[9]) {
 704     if (SkScalarAbs(mat[SkMatrix::kMPersp2]) > kMatrix22Elem) {
 705         for (int i = 0; i < 9; i++)
 706             mat[i] = SkScalarHalf(mat[i]);
 707     }
 708 }
 709
 710 bool SkMatrix::setConcat(const SkMatrix& a, const SkMatrix& b) {
 711     TypeMask aType = a.getPerspectiveTypeMaskOnly();
 712     TypeMask bType = b.getPerspectiveTypeMaskOnly();
 713
 714     if (a.isTriviallyIdentity()) {
 715         *this = b;
 716     } else if (b.isTriviallyIdentity()) {
 717         *this = a;
 718     } else {
 719         SkMatrix tmp;
 720
 721         if ((aType | bType) & kPerspective_Mask) {
 722             if (!rowcol3(&a.fMat[0], &b.fMat[0], &tmp.fMat[kMScaleX])) {
 723                 return false;
 724             }
 725             if (!rowcol3(&a.fMat[0], &b.fMat[1], &tmp.fMat[kMSkewX])) {
 726                 return false;
 727             }
 728             if (!rowcol3(&a.fMat[0], &b.fMat[2], &tmp.fMat[kMTransX])) {
 729                 return false;
 730             }
 731
 732             if (!rowcol3(&a.fMat[3], &b.fMat[0], &tmp.fMat[kMSkewY])) {
 733                 return false;
 734             }
 735             if (!rowcol3(&a.fMat[3], &b.fMat[1], &tmp.fMat[kMScaleY])) {
 736                 return false;
 737             }
 738             if (!rowcol3(&a.fMat[3], &b.fMat[2], &tmp.fMat[kMTransY])) {
 739                 return false;
 740             }
 741
 742             if (!rowcol3(&a.fMat[6], &b.fMat[0], &tmp.fMat[kMPersp0])) {
 743                 return false;
 744             }
 745             if (!rowcol3(&a.fMat[6], &b.fMat[1], &tmp.fMat[kMPersp1])) {
 746                 return false;
 747             }
 748             if (!rowcol3(&a.fMat[6], &b.fMat[2], &tmp.fMat[kMPersp2])) {
 749                 return false;
 750             }
 751
 752             normalize_perspective(tmp.fMat);
 753             tmp.setTypeMask(kUnknown_Mask);
 754         } else {    // not perspective
 755             if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMScaleX],
 756                     a.fMat[kMSkewX], b.fMat[kMSkewY], &tmp.fMat[kMScaleX])) {
 757                 return false;
 758             }
 759             if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMSkewX],
 760                       a.fMat[kMSkewX], b.fMat[kMScaleY], &tmp.fMat[kMSkewX])) {
 761                 return false;
 762             }
 763             if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMTransX],
 764                       a.fMat[kMSkewX], b.fMat[kMTransY], &tmp.fMat[kMTransX])) {
 765                 return false;
 766             }
 767             if (negifaddoverflows(tmp.fMat[kMTransX], tmp.fMat[kMTransX],
 768                                   a.fMat[kMTransX]) < 0) {
 769                 return false;
 770             }
 771
 772             if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMScaleX],
 773                       a.fMat[kMScaleY], b.fMat[kMSkewY], &tmp.fMat[kMSkewY])) {
 774                 return false;
 775             }
 776             if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMSkewX],
 777                     a.fMat[kMScaleY], b.fMat[kMScaleY], &tmp.fMat[kMScaleY])) {
 778                 return false;
 779             }
 780             if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMTransX],
 781                      a.fMat[kMScaleY], b.fMat[kMTransY], &tmp.fMat[kMTransY])) {
 782                 return false;
 783             }
 784             if (negifaddoverflows(tmp.fMat[kMTransY], tmp.fMat[kMTransY],
 785                                   a.fMat[kMTransY]) < 0) {
 786                 return false;
 787             }
 788
 789             tmp.fMat[kMPersp0] = tmp.fMat[kMPersp1] = 0;
 790             tmp.fMat[kMPersp2] = kMatrix22Elem;
 791             //SkDebugf("Concat mat non-persp type: %d\n", tmp.getType());
 792             //SkASSERT(!(tmp.getType() & kPerspective_Mask));
 793             tmp.setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
 794         }
 795         *this = tmp;
 796     }
 797     return true;
 798 }
 799
 800 bool SkMatrix::preConcat(const SkMatrix& mat) {
 801     // check for identity first, so we don't do a needless copy of ourselves
 802     // to ourselves inside setConcat()
 803     return mat.isIdentity() || this->setConcat(*this, mat);
 804 }
 805
 806 bool SkMatrix::postConcat(const SkMatrix& mat) {
 807     // check for identity first, so we don't do a needless copy of ourselves
 808     // to ourselves inside setConcat()
 809     return mat.isIdentity() || this->setConcat(mat, *this);
 810 }
 811
 812 ///////////////////////////////////////////////////////////////////////////////
 813
 814 /*  Matrix inversion is very expensive, but also the place where keeping
 815     precision may be most important (here and matrix concat). Hence to avoid
 816     bitmap blitting artifacts when walking the inverse, we use doubles for
 817     the intermediate math, even though we know that is more expensive.
 818     The fixed counter part is us using Sk64 for temp calculations.
 819  */
 820
 821 #ifdef SK_SCALAR_IS_FLOAT
 822     typedef double SkDetScalar;
 823     #define SkPerspMul(a, b)            SkScalarMul(a, b)
 824     #define SkScalarMulShift(a, b, s)   SkDoubleToFloat((a) * (b))
 825     static double sk_inv_determinant(const float mat[9], int isPerspective,
 826                                     int* /* (only used in Fixed case) */) {
 827         double det;
 828
 829         if (isPerspective) {
 830             det =   mat[SkMatrix::kMScaleX] * ((double)mat[SkMatrix::kMScaleY] * mat[SkMatrix::kMPersp2] - (double)mat[SkMatrix::kMTransY] * mat[SkMatrix::kMPersp1]) +
 831                     mat[SkMatrix::kMSkewX] * ((double)mat[SkMatrix::kMTransY] * mat[SkMatrix::kMPersp0] - (double)mat[SkMatrix::kMSkewY] * mat[SkMatrix::kMPersp2]) +
 832                     mat[SkMatrix::kMTransX] * ((double)mat[SkMatrix::kMSkewY] * mat[SkMatrix::kMPersp1] - (double)mat[SkMatrix::kMScaleY] * mat[SkMatrix::kMPersp0]);
 833         } else {
 834             det =   (double)mat[SkMatrix::kMScaleX] * mat[SkMatrix::kMScaleY] - (double)mat[SkMatrix::kMSkewX] * mat[SkMatrix::kMSkewY];
 835         }
 836
 837         // Since the determinant is on the order of the cube of the matrix members,
 838         // compare to the cube of the default nearly-zero constant (although an
 839         // estimate of the condition number would be better if it wasn't so expensive).
 840         if (SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
 841             return 0;
 842         }
 843         return 1.0 / det;
 844     }
 845     // we declar a,b,c,d to all be doubles, because we want to perform
 846     // double-precision muls and subtract, even though the original values are
 847     // from the matrix, which are floats.
 848     static float inline mul_diff_scale(double a, double b, double c, double d,
 849                                        double scale) {
 850         return SkDoubleToFloat((a * b - c * d) * scale);
 851     }
 852 #else
 853     typedef SkFixed SkDetScalar;
 854     #define SkPerspMul(a, b)            SkFractMul(a, b)
 855     #define SkScalarMulShift(a, b, s)   SkMulShift(a, b, s)
 856     static void set_muladdmul(Sk64* dst, int32_t a, int32_t b, int32_t c,
 857                               int32_t d) {
 858         Sk64 tmp;
 859         dst->setMul(a, b);
 860         tmp.setMul(c, d);
 861         dst->add(tmp);
 862     }
 863
 864     static SkFixed sk_inv_determinant(const SkFixed mat[9], int isPerspective,
 865                                       int* shift) {
 866         Sk64    tmp1, tmp2;
 867
 868         if (isPerspective) {
 869             tmp1.setMul(mat[SkMatrix::kMScaleX], fracmuladdmul(mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp2], -mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp1]));
 870             tmp2.setMul(mat[SkMatrix::kMSkewX], fracmuladdmul(mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp0], -mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp2]));
 871             tmp1.add(tmp2);
 872             tmp2.setMul(mat[SkMatrix::kMTransX], fracmuladdmul(mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp1], -mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp0]));
 873             tmp1.add(tmp2);
 874         } else {
 875             tmp1.setMul(mat[SkMatrix::kMScaleX], mat[SkMatrix::kMScaleY]);
 876             tmp2.setMul(mat[SkMatrix::kMSkewX], mat[SkMatrix::kMSkewY]);
 877             tmp1.sub(tmp2);
 878         }
 879
 880         int s = tmp1.getClzAbs();
 881         *shift = s;
 882
 883         SkFixed denom;
 884         if (s <= 32) {
 885             denom = tmp1.getShiftRight(33 - s);
 886         } else {
 887             denom = (int32_t)tmp1.fLo << (s - 33);
 888         }
 889
 890         if (denom == 0) {
 891             return 0;
 892         }
 893         /** This could perhaps be a special fractdiv function, since both of its
 894             arguments are known to have bit 31 clear and bit 30 set (when they
 895             are made positive), thus eliminating the need for calling clz()
 896         */
 897         return SkFractDiv(SK_Fract1, denom);
 898     }
 899 #endif
 900
 901 void SkMatrix::SetAffineIdentity(SkScalar affine[6]) {
 902     affine[kAScaleX] = SK_Scalar1;
 903     affine[kASkewY] = 0;
 904     affine[kASkewX] = 0;
 905     affine[kAScaleY] = SK_Scalar1;
 906     affine[kATransX] = 0;
 907     affine[kATransY] = 0;
 908 }
 909
 910 bool SkMatrix::asAffine(SkScalar affine[6]) const {
 911     if (this->hasPerspective()) {
 912         return false;
 913     }
 914     if (affine) {
 915         affine[kAScaleX] = this->fMat[kMScaleX];
 916         affine[kASkewY] = this->fMat[kMSkewY];
 917         affine[kASkewX] = this->fMat[kMSkewX];
 918         affine[kAScaleY] = this->fMat[kMScaleY];
 919         affine[kATransX] = this->fMat[kMTransX];
 920         affine[kATransY] = this->fMat[kMTransY];
 921     }
 922     return true;
 923 }
 924
 925 bool SkMatrix::invertNonIdentity(SkMatrix* inv) const {
 926     SkASSERT(!this->isIdentity());
 927
 928     TypeMask mask = this->getType();
 929
 930     if (0 == (mask & ~(kScale_Mask | kTranslate_Mask))) {
 931         bool invertible = true;
 932         if (inv) {
 933             if (mask & kScale_Mask) {
 934                 SkScalar invX = fMat[kMScaleX];
 935                 SkScalar invY = fMat[kMScaleY];
 936                 if (0 == invX || 0 == invY) {
 937                     return false;
 938                 }
 939                 invX = SkScalarInvert(invX);
 940                 invY = SkScalarInvert(invY);
 941
 942                 // Must be careful when writing to inv, since it may be the
 943                 // same memory as this.
 944
 945                 inv->fMat[kMSkewX] = inv->fMat[kMSkewY] =
 946                 inv->fMat[kMPersp0] = inv->fMat[kMPersp1] = 0;
 947
 948                 inv->fMat[kMScaleX] = invX;
 949                 inv->fMat[kMScaleY] = invY;
 950                 inv->fMat[kMPersp2] = kMatrix22Elem;
 951                 inv->fMat[kMTransX] = -SkScalarMul(fMat[kMTransX], invX);
 952                 inv->fMat[kMTransY] = -SkScalarMul(fMat[kMTransY], invY);
 953
 954                 inv->setTypeMask(mask | kRectStaysRect_Mask);
 955             } else {
 956                 // translate only
 957                 inv->setTranslate(-fMat[kMTransX], -fMat[kMTransY]);
 958             }
 959         } else {    // inv is NULL, just check if we're invertible
 960             if (!fMat[kMScaleX] || !fMat[kMScaleY]) {
 961                 invertible = false;
 962             }
 963         }
 964         return invertible;
 965     }
 966
 967     int         isPersp = mask & kPerspective_Mask;
 968     int         shift;
 969     SkDetScalar scale = sk_inv_determinant(fMat, isPersp, &shift);
 970
 971     if (scale == 0) { // underflow
 972         return false;
 973     }
 974
 975     if (inv) {
 976         SkMatrix tmp;
 977         if (inv == this) {
 978             inv = &tmp;
 979         }
 980
 981         if (isPersp) {
 982             shift = 61 - shift;
 983             inv->fMat[kMScaleX] = SkScalarMulShift(SkPerspMul(fMat[kMScaleY], fMat[kMPersp2]) - SkPerspMul(fMat[kMTransY], fMat[kMPersp1]), scale, shift);
 984             inv->fMat[kMSkewX]  = SkScalarMulShift(SkPerspMul(fMat[kMTransX], fMat[kMPersp1]) - SkPerspMul(fMat[kMSkewX],  fMat[kMPersp2]), scale, shift);
 985             inv->fMat[kMTransX] = SkScalarMulShift(SkScalarMul(fMat[kMSkewX], fMat[kMTransY]) - SkScalarMul(fMat[kMTransX], fMat[kMScaleY]), scale, shift);
 986
 987             inv->fMat[kMSkewY]  = SkScalarMulShift(SkPerspMul(fMat[kMTransY], fMat[kMPersp0]) - SkPerspMul(fMat[kMSkewY],   fMat[kMPersp2]), scale, shift);
 988             inv->fMat[kMScaleY] = SkScalarMulShift(SkPerspMul(fMat[kMScaleX], fMat[kMPersp2]) - SkPerspMul(fMat[kMTransX],  fMat[kMPersp0]), scale, shift);
 989             inv->fMat[kMTransY] = SkScalarMulShift(SkScalarMul(fMat[kMTransX], fMat[kMSkewY]) - SkScalarMul(fMat[kMScaleX], fMat[kMTransY]), scale, shift);
 990
 991             inv->fMat[kMPersp0] = SkScalarMulShift(SkScalarMul(fMat[kMSkewY], fMat[kMPersp1]) - SkScalarMul(fMat[kMScaleY], fMat[kMPersp0]), scale, shift);
 992             inv->fMat[kMPersp1] = SkScalarMulShift(SkScalarMul(fMat[kMSkewX], fMat[kMPersp0]) - SkScalarMul(fMat[kMScaleX], fMat[kMPersp1]), scale, shift);
 993             inv->fMat[kMPersp2] = SkScalarMulShift(SkScalarMul(fMat[kMScaleX], fMat[kMScaleY]) - SkScalarMul(fMat[kMSkewX], fMat[kMSkewY]), scale, shift);
 994 #ifdef SK_SCALAR_IS_FIXED
 995             if (SkAbs32(inv->fMat[kMPersp2]) > SK_Fixed1) {
 996                 Sk64    tmp;
 997
 998                 tmp.set(SK_Fract1);
 999                 tmp.shiftLeft(16);
1000                 tmp.div(inv->fMat[kMPersp2], Sk64::kRound_DivOption);
1001
1002                 SkFract scale = tmp.get32();
1003
1004                 for (int i = 0; i < 9; i++) {
1005                     inv->fMat[i] = SkFractMul(inv->fMat[i], scale);
1006                 }
1007             }
1008             inv->fMat[kMPersp2] = SkFixedToFract(inv->fMat[kMPersp2]);
1009 #endif
1010         } else {   // not perspective
1011 #ifdef SK_SCALAR_IS_FIXED
1012             Sk64    tx, ty;
1013             int     clzNumer;
1014
1015             // check the 2x2 for overflow
1016             {
1017                 int32_t value = SkAbs32(fMat[kMScaleY]);
1018                 value |= SkAbs32(fMat[kMSkewX]);
1019                 value |= SkAbs32(fMat[kMScaleX]);
1020                 value |= SkAbs32(fMat[kMSkewY]);
1021                 clzNumer = SkCLZ(value);
1022                 if (shift - clzNumer > 31)
1023                     return false;   // overflow
1024             }
1025
1026             set_muladdmul(&tx, fMat[kMSkewX], fMat[kMTransY], -fMat[kMScaleY], fMat[kMTransX]);
1027             set_muladdmul(&ty, fMat[kMSkewY], fMat[kMTransX], -fMat[kMScaleX], fMat[kMTransY]);
1028             // check tx,ty for overflow
1029             clzNumer = SkCLZ(SkAbs32(tx.fHi) | SkAbs32(ty.fHi));
1030             if (shift - clzNumer > 14) {
1031                 return false;   // overflow
1032             }
1033
1034             int fixedShift = 61 - shift;
1035             int sk64shift = 44 - shift + clzNumer;
1036
1037             inv->fMat[kMScaleX] = SkMulShift(fMat[kMScaleY], scale, fixedShift);
1038             inv->fMat[kMSkewX]  = SkMulShift(-fMat[kMSkewX], scale, fixedShift);
1039             inv->fMat[kMTransX] = SkMulShift(tx.getShiftRight(33 - clzNumer), scale, sk64shift);
1040
1041             inv->fMat[kMSkewY]  = SkMulShift(-fMat[kMSkewY], scale, fixedShift);
1042             inv->fMat[kMScaleY] = SkMulShift(fMat[kMScaleX], scale, fixedShift);
1043             inv->fMat[kMTransY] = SkMulShift(ty.getShiftRight(33 - clzNumer), scale, sk64shift);
1044 #else
1045             inv->fMat[kMScaleX] = SkDoubleToFloat(fMat[kMScaleY] * scale);
1046             inv->fMat[kMSkewX] = SkDoubleToFloat(-fMat[kMSkewX] * scale);
1047             inv->fMat[kMTransX] = mul_diff_scale(fMat[kMSkewX], fMat[kMTransY],
1048                                      fMat[kMScaleY], fMat[kMTransX], scale);
1049
1050             inv->fMat[kMSkewY] = SkDoubleToFloat(-fMat[kMSkewY] * scale);
1051             inv->fMat[kMScaleY] = SkDoubleToFloat(fMat[kMScaleX] * scale);
1052             inv->fMat[kMTransY] = mul_diff_scale(fMat[kMSkewY], fMat[kMTransX],
1053                                         fMat[kMScaleX], fMat[kMTransY], scale);
1054 #endif
1055             inv->fMat[kMPersp0] = 0;
1056             inv->fMat[kMPersp1] = 0;
1057             inv->fMat[kMPersp2] = kMatrix22Elem;
1058
1059         }
1060
1061         inv->setTypeMask(fTypeMask);
1062
1063         if (inv == &tmp) {
1064             *(SkMatrix*)this = tmp;
1065         }
1066     }
1067     return true;
1068 }
1069
1070 ///////////////////////////////////////////////////////////////////////////////
1071
1072 void SkMatrix::Identity_pts(const SkMatrix& m, SkPoint dst[],
1073                             const SkPoint src[], int count) {
1074     SkASSERT(m.getType() == 0);
1075
1076     if (dst != src && count > 0)
1077         memcpy(dst, src, count * sizeof(SkPoint));
1078 }
1079
1080 void SkMatrix::Trans_pts(const SkMatrix& m, SkPoint dst[],
1081                          const SkPoint src[], int count) {
1082     SkASSERT(m.getType() == kTranslate_Mask);
1083
1084     if (count > 0) {
1085         SkScalar tx = m.fMat[kMTransX];
1086         SkScalar ty = m.fMat[kMTransY];
1087         do {
1088             dst->fY = src->fY + ty;
1089             dst->fX = src->fX + tx;
1090             src += 1;
1091             dst += 1;
1092         } while (--count);
1093     }
1094 }
1095
1096 void SkMatrix::Scale_pts(const SkMatrix& m, SkPoint dst[],
1097                          const SkPoint src[], int count) {
1098     SkASSERT(m.getType() == kScale_Mask);
1099
1100     if (count > 0) {
1101         SkScalar mx = m.fMat[kMScaleX];
1102         SkScalar my = m.fMat[kMScaleY];
1103         do {
1104             dst->fY = SkScalarMul(src->fY, my);
1105             dst->fX = SkScalarMul(src->fX, mx);
1106             src += 1;
1107             dst += 1;
1108         } while (--count);
1109     }
1110 }
1111
1112 void SkMatrix::ScaleTrans_pts(const SkMatrix& m, SkPoint dst[],
1113                               const SkPoint src[], int count) {
1114     SkASSERT(m.getType() == (kScale_Mask | kTranslate_Mask));
1115
1116     if (count > 0) {
1117         SkScalar mx = m.fMat[kMScaleX];
1118         SkScalar my = m.fMat[kMScaleY];
1119         SkScalar tx = m.fMat[kMTransX];
1120         SkScalar ty = m.fMat[kMTransY];
1121         do {
1122             dst->fY = SkScalarMulAdd(src->fY, my, ty);
1123             dst->fX = SkScalarMulAdd(src->fX, mx, tx);
1124             src += 1;
1125             dst += 1;
1126         } while (--count);
1127     }
1128 }
1129
1130 void SkMatrix::Rot_pts(const SkMatrix& m, SkPoint dst[],
1131                        const SkPoint src[], int count) {
1132     SkASSERT((m.getType() & (kPerspective_Mask | kTranslate_Mask)) == 0);
1133
1134     if (count > 0) {
1135         SkScalar mx = m.fMat[kMScaleX];
1136         SkScalar my = m.fMat[kMScaleY];
1137         SkScalar kx = m.fMat[kMSkewX];
1138         SkScalar ky = m.fMat[kMSkewY];
1139         do {
1140             SkScalar sy = src->fY;
1141             SkScalar sx = src->fX;
1142             src += 1;
1143             dst->fY = SkScalarMul(sx, ky) + SkScalarMul(sy, my);
1144             dst->fX = SkScalarMul(sx, mx) + SkScalarMul(sy, kx);
1145             dst += 1;
1146         } while (--count);
1147     }
1148 }
1149
1150 void SkMatrix::RotTrans_pts(const SkMatrix& m, SkPoint dst[],
1151                             const SkPoint src[], int count) {
1152     SkASSERT(!m.hasPerspective());
1153
1154     if (count > 0) {
1155         SkScalar mx = m.fMat[kMScaleX];
1156         SkScalar my = m.fMat[kMScaleY];
1157         SkScalar kx = m.fMat[kMSkewX];
1158         SkScalar ky = m.fMat[kMSkewY];
1159         SkScalar tx = m.fMat[kMTransX];
1160         SkScalar ty = m.fMat[kMTransY];
1161         do {
1162             SkScalar sy = src->fY;
1163             SkScalar sx = src->fX;
1164             src += 1;
1165             dst->fY = SkScalarMul(sx, ky) + SkScalarMulAdd(sy, my, ty);
1166             dst->fX = SkScalarMul(sx, mx) + SkScalarMulAdd(sy, kx, tx);
1167             dst += 1;
1168         } while (--count);
1169     }
1170 }
1171
1172 void SkMatrix::Persp_pts(const SkMatrix& m, SkPoint dst[],
1173                          const SkPoint src[], int count) {
1174     SkASSERT(m.hasPerspective());
1175
1176 #ifdef SK_SCALAR_IS_FIXED
1177     SkFixed persp2 = SkFractToFixed(m.fMat[kMPersp2]);
1178 #endif
1179
1180     if (count > 0) {
1181         do {
1182             SkScalar sy = src->fY;
1183             SkScalar sx = src->fX;
1184             src += 1;
1185
1186             SkScalar x = SkScalarMul(sx, m.fMat[kMScaleX]) +
1187                          SkScalarMul(sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1188             SkScalar y = SkScalarMul(sx, m.fMat[kMSkewY]) +
1189                          SkScalarMul(sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1190 #ifdef SK_SCALAR_IS_FIXED
1191             SkFixed z = SkFractMul(sx, m.fMat[kMPersp0]) +
1192                         SkFractMul(sy, m.fMat[kMPersp1]) + persp2;
1193 #else
1194             float z = SkScalarMul(sx, m.fMat[kMPersp0]) +
1195                       SkScalarMulAdd(sy, m.fMat[kMPersp1], m.fMat[kMPersp2]);
1196 #endif
1197             if (z) {
1198                 z = SkScalarFastInvert(z);
1199             }
1200
1201             dst->fY = SkScalarMul(y, z);
1202             dst->fX = SkScalarMul(x, z);
1203             dst += 1;
1204         } while (--count);
1205     }
1206 }
1207
1208 const SkMatrix::MapPtsProc SkMatrix::gMapPtsProcs[] = {
1209     SkMatrix::Identity_pts, SkMatrix::Trans_pts,
1210     SkMatrix::Scale_pts,    SkMatrix::ScaleTrans_pts,
1211     SkMatrix::Rot_pts,      SkMatrix::RotTrans_pts,
1212     SkMatrix::Rot_pts,      SkMatrix::RotTrans_pts,
1213     // repeat the persp proc 8 times
1214     SkMatrix::Persp_pts,    SkMatrix::Persp_pts,
1215     SkMatrix::Persp_pts,    SkMatrix::Persp_pts,
1216     SkMatrix::Persp_pts,    SkMatrix::Persp_pts,
1217     SkMatrix::Persp_pts,    SkMatrix::Persp_pts
1218 };
1219
1220 void SkMatrix::mapPoints(SkPoint dst[], const SkPoint src[], int count) const {
1221     SkASSERT((dst && src && count > 0) || 0 == count);
1222     // no partial overlap
1223     SkASSERT(src == dst || &dst[count] <= &src[0] || &src[count] <= &dst[0]);
1224
1225     this->getMapPtsProc()(*this, dst, src, count);
1226 }
1227
1228 ///////////////////////////////////////////////////////////////////////////////
1229
1230 void SkMatrix::mapHomogeneousPoints(SkScalar dst[], const SkScalar src[], int count) const {
1231     SkASSERT((dst && src && count > 0) || 0 == count);
1232     // no partial overlap
1233     SkASSERT(src == dst || SkAbs32((int32_t)(src - dst)) >= 3*count);
1234
1235     if (count > 0) {
1236         if (this->isIdentity()) {
1237             memcpy(dst, src, 3*count*sizeof(SkScalar));
1238             return;
1239         }
1240         do {
1241             SkScalar sx = src[0];
1242             SkScalar sy = src[1];
1243             SkScalar sw = src[2];
1244             src += 3;
1245
1246             SkScalar x = SkScalarMul(sx, fMat[kMScaleX]) +
1247                          SkScalarMul(sy, fMat[kMSkewX]) +
1248                          SkScalarMul(sw, fMat[kMTransX]);
1249             SkScalar y = SkScalarMul(sx, fMat[kMSkewY]) +
1250                          SkScalarMul(sy, fMat[kMScaleY]) +
1251                          SkScalarMul(sw, fMat[kMTransY]);
1252             SkScalar w = SkScalarMul(sx, fMat[kMPersp0]) +
1253                          SkScalarMul(sy, fMat[kMPersp1]) +
1254                          SkScalarMul(sw, fMat[kMPersp2]);
1255
1256             dst[0] = x;
1257             dst[1] = y;
1258             dst[2] = w;
1259             dst += 3;
1260         } while (--count);
1261     }
1262 }
1263
1264 ///////////////////////////////////////////////////////////////////////////////
1265
1266 void SkMatrix::mapVectors(SkPoint dst[], const SkPoint src[], int count) const {
1267     if (this->hasPerspective()) {
1268         SkPoint origin;
1269
1270         MapXYProc proc = this->getMapXYProc();
1271         proc(*this, 0, 0, &origin);
1272
1273         for (int i = count - 1; i >= 0; --i) {
1274             SkPoint tmp;
1275
1276             proc(*this, src[i].fX, src[i].fY, &tmp);
1277             dst[i].set(tmp.fX - origin.fX, tmp.fY - origin.fY);
1278         }
1279     } else {
1280         SkMatrix tmp = *this;
1281
1282         tmp.fMat[kMTransX] = tmp.fMat[kMTransY] = 0;
1283         tmp.clearTypeMask(kTranslate_Mask);
1284         tmp.mapPoints(dst, src, count);
1285     }
1286 }
1287
1288 bool SkMatrix::mapRect(SkRect* dst, const SkRect& src) const {
1289     SkASSERT(dst && &src);
1290
1291     if (this->rectStaysRect()) {
1292         this->mapPoints((SkPoint*)dst, (const SkPoint*)&src, 2);
1293         dst->sort();
1294         return true;
1295     } else {
1296         SkPoint quad[4];
1297
1298         src.toQuad(quad);
1299         this->mapPoints(quad, quad, 4);
1300         dst->set(quad, 4);
1301         return false;
1302     }
1303 }
1304
1305 SkScalar SkMatrix::mapRadius(SkScalar radius) const {
1306     SkVector    vec[2];
1307
1308     vec[0].set(radius, 0);
1309     vec[1].set(0, radius);
1310     this->mapVectors(vec, 2);
1311
1312     SkScalar d0 = vec[0].length();
1313     SkScalar d1 = vec[1].length();
1314
1315     return SkScalarMean(d0, d1);
1316 }
1317
1318 ///////////////////////////////////////////////////////////////////////////////
1319
1320 void SkMatrix::Persp_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1321                         SkPoint* pt) {
1322     SkASSERT(m.hasPerspective());
1323
1324     SkScalar x = SkScalarMul(sx, m.fMat[kMScaleX]) +
1325                  SkScalarMul(sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1326     SkScalar y = SkScalarMul(sx, m.fMat[kMSkewY]) +
1327                  SkScalarMul(sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1328 #ifdef SK_SCALAR_IS_FIXED
1329     SkFixed z = SkFractMul(sx, m.fMat[kMPersp0]) +
1330                 SkFractMul(sy, m.fMat[kMPersp1]) +
1331                 SkFractToFixed(m.fMat[kMPersp2]);
1332 #else
1333     float z = SkScalarMul(sx, m.fMat[kMPersp0]) +
1334               SkScalarMul(sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
1335 #endif
1336     if (z) {
1337         z = SkScalarFastInvert(z);
1338     }
1339     pt->fX = SkScalarMul(x, z);
1340     pt->fY = SkScalarMul(y, z);
1341 }
1342
1343 #ifdef SK_SCALAR_IS_FIXED
1344 static SkFixed fixmuladdmul(SkFixed a, SkFixed b, SkFixed c, SkFixed d) {
1345     Sk64    tmp, tmp1;
1346
1347     tmp.setMul(a, b);
1348     tmp1.setMul(c, d);
1349     return tmp.addGetFixed(tmp1);
1350 //  tmp.add(tmp1);
1351 //  return tmp.getFixed();
1352 }
1353 #endif
1354
1355 void SkMatrix::RotTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1356                            SkPoint* pt) {
1357     SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask)) == kAffine_Mask);
1358
1359 #ifdef SK_SCALAR_IS_FIXED
1360     pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) +
1361              m.fMat[kMTransX];
1362     pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) +
1363              m.fMat[kMTransY];
1364 #else
1365     pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) +
1366              SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]);
1367     pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) +
1368              SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]);
1369 #endif
1370 }
1371
1372 void SkMatrix::Rot_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1373                       SkPoint* pt) {
1374     SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask))== kAffine_Mask);
1375     SkASSERT(0 == m.fMat[kMTransX]);
1376     SkASSERT(0 == m.fMat[kMTransY]);
1377
1378 #ifdef SK_SCALAR_IS_FIXED
1379     pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]);
1380     pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]);
1381 #else
1382     pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) +
1383              SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]);
1384     pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) +
1385              SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]);
1386 #endif
1387 }
1388
1389 void SkMatrix::ScaleTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1390                              SkPoint* pt) {
1391     SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
1392              == kScale_Mask);
1393
1394     pt->fX = SkScalarMulAdd(sx, m.fMat[kMScaleX], m.fMat[kMTransX]);
1395     pt->fY = SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]);
1396 }
1397
1398 void SkMatrix::Scale_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1399                         SkPoint* pt) {
1400     SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
1401              == kScale_Mask);
1402     SkASSERT(0 == m.fMat[kMTransX]);
1403     SkASSERT(0 == m.fMat[kMTransY]);
1404
1405     pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]);
1406     pt->fY = SkScalarMul(sy, m.fMat[kMScaleY]);
1407 }
1408
1409 void SkMatrix::Trans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1410                         SkPoint* pt) {
1411     SkASSERT(m.getType() == kTranslate_Mask);
1412
1413     pt->fX = sx + m.fMat[kMTransX];
1414     pt->fY = sy + m.fMat[kMTransY];
1415 }
1416
1417 void SkMatrix::Identity_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1418                            SkPoint* pt) {
1419     SkASSERT(0 == m.getType());
1420
1421     pt->fX = sx;
1422     pt->fY = sy;
1423 }
1424
1425 const SkMatrix::MapXYProc SkMatrix::gMapXYProcs[] = {
1426     SkMatrix::Identity_xy, SkMatrix::Trans_xy,
1427     SkMatrix::Scale_xy,    SkMatrix::ScaleTrans_xy,
1428     SkMatrix::Rot_xy,      SkMatrix::RotTrans_xy,
1429     SkMatrix::Rot_xy,      SkMatrix::RotTrans_xy,
1430     // repeat the persp proc 8 times
1431     SkMatrix::Persp_xy,    SkMatrix::Persp_xy,
1432     SkMatrix::Persp_xy,    SkMatrix::Persp_xy,
1433     SkMatrix::Persp_xy,    SkMatrix::Persp_xy,
1434     SkMatrix::Persp_xy,    SkMatrix::Persp_xy
1435 };
1436
1437 ///////////////////////////////////////////////////////////////////////////////
1438
1439 // if its nearly zero (just made up 26, perhaps it should be bigger or smaller)
1440 #ifdef SK_SCALAR_IS_FIXED
1441     typedef SkFract             SkPerspElemType;
1442     #define PerspNearlyZero(x)  (SkAbs32(x) < (SK_Fract1 >> 26))
1443 #else
1444     typedef float               SkPerspElemType;
1445     #define PerspNearlyZero(x)  SkScalarNearlyZero(x, (1.0f / (1 << 26)))
1446 #endif
1447
1448 bool SkMatrix::fixedStepInX(SkScalar y, SkFixed* stepX, SkFixed* stepY) const {
1449     if (PerspNearlyZero(fMat[kMPersp0])) {
1450         if (stepX || stepY) {
1451             if (PerspNearlyZero(fMat[kMPersp1]) &&
1452                     PerspNearlyZero(fMat[kMPersp2] - kMatrix22Elem)) {
1453                 if (stepX) {
1454                     *stepX = SkScalarToFixed(fMat[kMScaleX]);
1455                 }
1456                 if (stepY) {
1457                     *stepY = SkScalarToFixed(fMat[kMSkewY]);
1458                 }
1459             } else {
1460 #ifdef SK_SCALAR_IS_FIXED
1461                 SkFixed z = SkFractMul(y, fMat[kMPersp1]) +
1462                             SkFractToFixed(fMat[kMPersp2]);
1463 #else
1464                 float z = y * fMat[kMPersp1] + fMat[kMPersp2];
1465 #endif
1466                 if (stepX) {
1467                     *stepX = SkScalarToFixed(SkScalarDiv(fMat[kMScaleX], z));
1468                 }
1469                 if (stepY) {
1470                     *stepY = SkScalarToFixed(SkScalarDiv(fMat[kMSkewY], z));
1471                 }
1472             }
1473         }
1474         return true;
1475     }
1476     return false;
1477 }
1478
1479 ///////////////////////////////////////////////////////////////////////////////
1480
1481 #include "SkPerspIter.h"
1482
1483 SkPerspIter::SkPerspIter(const SkMatrix& m, SkScalar x0, SkScalar y0, int count)
1484         : fMatrix(m), fSX(x0), fSY(y0), fCount(count) {
1485     SkPoint pt;
1486
1487     SkMatrix::Persp_xy(m, x0, y0, &pt);
1488     fX = SkScalarToFixed(pt.fX);
1489     fY = SkScalarToFixed(pt.fY);
1490 }
1491
1492 int SkPerspIter::next() {
1493     int n = fCount;
1494
1495     if (0 == n) {
1496         return 0;
1497     }
1498     SkPoint pt;
1499     SkFixed x = fX;
1500     SkFixed y = fY;
1501     SkFixed dx, dy;
1502
1503     if (n >= kCount) {
1504         n = kCount;
1505         fSX += SkIntToScalar(kCount);
1506         SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
1507         fX = SkScalarToFixed(pt.fX);
1508         fY = SkScalarToFixed(pt.fY);
1509         dx = (fX - x) >> kShift;
1510         dy = (fY - y) >> kShift;
1511     } else {
1512         fSX += SkIntToScalar(n);
1513         SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
1514         fX = SkScalarToFixed(pt.fX);
1515         fY = SkScalarToFixed(pt.fY);
1516         dx = (fX - x) / n;
1517         dy = (fY - y) / n;
1518     }
1519
1520     SkFixed* p = fStorage;
1521     for (int i = 0; i < n; i++) {
1522         *p++ = x; x += dx;
1523         *p++ = y; y += dy;
1524     }
1525
1526     fCount -= n;
1527     return n;
1528 }
1529
1530 ///////////////////////////////////////////////////////////////////////////////
1531
1532 #ifdef SK_SCALAR_IS_FIXED
1533
1534 static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) {
1535     SkFixed x = SK_Fixed1, y = SK_Fixed1;
1536     SkPoint pt1, pt2;
1537     Sk64    w1, w2;
1538
1539     if (count > 1) {
1540         pt1.fX = poly[1].fX - poly[0].fX;
1541         pt1.fY = poly[1].fY - poly[0].fY;
1542         y = SkPoint::Length(pt1.fX, pt1.fY);
1543         if (y == 0) {
1544             return false;
1545         }
1546         switch (count) {
1547             case 2:
1548                 break;
1549             case 3:
1550                 pt2.fX = poly[0].fY - poly[2].fY;
1551                 pt2.fY = poly[2].fX - poly[0].fX;
1552                 goto CALC_X;
1553             default:
1554                 pt2.fX = poly[0].fY - poly[3].fY;
1555                 pt2.fY = poly[3].fX - poly[0].fX;
1556             CALC_X:
1557                 w1.setMul(pt1.fX, pt2.fX);
1558                 w2.setMul(pt1.fY, pt2.fY);
1559                 w1.add(w2);
1560                 w1.div(y, Sk64::kRound_DivOption);
1561                 if (!w1.is32()) {
1562                     return false;
1563                 }
1564                 x = w1.get32();
1565                 break;
1566         }
1567     }
1568     pt->set(x, y);
1569     return true;
1570 }
1571
1572 bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst,
1573                          const SkPoint& scalePt) {
1574     // need to check if SkFixedDiv overflows...
1575
1576     const SkFixed scale = scalePt.fY;
1577     dst->fMat[kMScaleX] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale);
1578     dst->fMat[kMSkewY]  = SkFixedDiv(srcPt[0].fX - srcPt[1].fX, scale);
1579     dst->fMat[kMPersp0] = 0;
1580     dst->fMat[kMSkewX]  = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale);
1581     dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale);
1582     dst->fMat[kMPersp1] = 0;
1583     dst->fMat[kMTransX] = srcPt[0].fX;
1584     dst->fMat[kMTransY] = srcPt[0].fY;
1585     dst->fMat[kMPersp2] = SK_Fract1;
1586     dst->setTypeMask(kUnknown_Mask);
1587     return true;
1588 }
1589
1590 bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst,
1591                          const SkPoint& scale) {
1592     // really, need to check if SkFixedDiv overflow'd
1593
1594     dst->fMat[kMScaleX] = SkFixedDiv(srcPt[2].fX - srcPt[0].fX, scale.fX);
1595     dst->fMat[kMSkewY]  = SkFixedDiv(srcPt[2].fY - srcPt[0].fY, scale.fX);
1596     dst->fMat[kMPersp0] = 0;
1597     dst->fMat[kMSkewX]  = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale.fY);
1598     dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale.fY);
1599     dst->fMat[kMPersp1] = 0;
1600     dst->fMat[kMTransX] = srcPt[0].fX;
1601     dst->fMat[kMTransY] = srcPt[0].fY;
1602     dst->fMat[kMPersp2] = SK_Fract1;
1603     dst->setTypeMask(kUnknown_Mask);
1604     return true;
1605 }
1606
1607 bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst,
1608                          const SkPoint& scale) {
1609     SkFract a1, a2;
1610     SkFixed x0, y0, x1, y1, x2, y2;
1611
1612     x0 = srcPt[2].fX - srcPt[0].fX;
1613     y0 = srcPt[2].fY - srcPt[0].fY;
1614     x1 = srcPt[2].fX - srcPt[1].fX;
1615     y1 = srcPt[2].fY - srcPt[1].fY;
1616     x2 = srcPt[2].fX - srcPt[3].fX;
1617     y2 = srcPt[2].fY - srcPt[3].fY;
1618
1619     /* check if abs(x2) > abs(y2) */
1620     if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) {
1621         SkFixed denom = SkMulDiv(x1, y2, x2) - y1;
1622         if (0 == denom) {
1623             return false;
1624         }
1625         a1 = SkFractDiv(SkMulDiv(x0 - x1, y2, x2) - y0 + y1, denom);
1626     } else {
1627         SkFixed denom = x1 - SkMulDiv(y1, x2, y2);
1628         if (0 == denom) {
1629             return false;
1630         }
1631         a1 = SkFractDiv(x0 - x1 - SkMulDiv(y0 - y1, x2, y2), denom);
1632     }
1633
1634     /* check if abs(x1) > abs(y1) */
1635     if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) {
1636         SkFixed denom = y2 - SkMulDiv(x2, y1, x1);
1637         if (0 == denom) {
1638             return false;
1639         }
1640         a2 = SkFractDiv(y0 - y2 - SkMulDiv(x0 - x2, y1, x1), denom);
1641     } else {
1642         SkFixed denom = SkMulDiv(y2, x1, y1) - x2;
1643         if (0 == denom) {
1644             return false;
1645         }
1646         a2 = SkFractDiv(SkMulDiv(y0 - y2, x1, y1) - x0 + x2, denom);
1647     }
1648
1649     // need to check if SkFixedDiv overflows...
1650     dst->fMat[kMScaleX] = SkFixedDiv(SkFractMul(a2, srcPt[3].fX) +
1651                                      srcPt[3].fX - srcPt[0].fX, scale.fX);
1652     dst->fMat[kMSkewY]  = SkFixedDiv(SkFractMul(a2, srcPt[3].fY) +
1653                                      srcPt[3].fY - srcPt[0].fY, scale.fX);
1654     dst->fMat[kMPersp0] = SkFixedDiv(a2, scale.fX);
1655     dst->fMat[kMSkewX]  = SkFixedDiv(SkFractMul(a1, srcPt[1].fX) +
1656                                      srcPt[1].fX - srcPt[0].fX, scale.fY);
1657     dst->fMat[kMScaleY] = SkFixedDiv(SkFractMul(a1, srcPt[1].fY) +
1658                                      srcPt[1].fY - srcPt[0].fY, scale.fY);
1659     dst->fMat[kMPersp1] = SkFixedDiv(a1, scale.fY);
1660     dst->fMat[kMTransX] = srcPt[0].fX;
1661     dst->fMat[kMTransY] = srcPt[0].fY;
1662     dst->fMat[kMPersp2] = SK_Fract1;
1663     dst->setTypeMask(kUnknown_Mask);
1664     return true;
1665 }
1666
1667 #else   /* Scalar is float */
1668
1669 static inline bool checkForZero(float x) {
1670     return x*x == 0;
1671 }
1672
1673 static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) {
1674     float   x = 1, y = 1;
1675     SkPoint pt1, pt2;
1676
1677     if (count > 1) {
1678         pt1.fX = poly[1].fX - poly[0].fX;
1679         pt1.fY = poly[1].fY - poly[0].fY;
1680         y = SkPoint::Length(pt1.fX, pt1.fY);
1681         if (checkForZero(y)) {
1682             return false;
1683         }
1684         switch (count) {
1685             case 2:
1686                 break;
1687             case 3:
1688                 pt2.fX = poly[0].fY - poly[2].fY;
1689                 pt2.fY = poly[2].fX - poly[0].fX;
1690                 goto CALC_X;
1691             default:
1692                 pt2.fX = poly[0].fY - poly[3].fY;
1693                 pt2.fY = poly[3].fX - poly[0].fX;
1694             CALC_X:
1695                 x = SkScalarDiv(SkScalarMul(pt1.fX, pt2.fX) +
1696                                 SkScalarMul(pt1.fY, pt2.fY), y);
1697                 break;
1698         }
1699     }
1700     pt->set(x, y);
1701     return true;
1702 }
1703
1704 bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst,
1705                          const SkPoint& scale) {
1706     float invScale = 1 / scale.fY;
1707
1708     dst->fMat[kMScaleX] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1709     dst->fMat[kMSkewY] = (srcPt[0].fX - srcPt[1].fX) * invScale;
1710     dst->fMat[kMPersp0] = 0;
1711     dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
1712     dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1713     dst->fMat[kMPersp1] = 0;
1714     dst->fMat[kMTransX] = srcPt[0].fX;
1715     dst->fMat[kMTransY] = srcPt[0].fY;
1716     dst->fMat[kMPersp2] = 1;
1717     dst->setTypeMask(kUnknown_Mask);
1718     return true;
1719 }
1720
1721 bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst,
1722                          const SkPoint& scale) {
1723     float invScale = 1 / scale.fX;
1724     dst->fMat[kMScaleX] = (srcPt[2].fX - srcPt[0].fX) * invScale;
1725     dst->fMat[kMSkewY] = (srcPt[2].fY - srcPt[0].fY) * invScale;
1726     dst->fMat[kMPersp0] = 0;
1727
1728     invScale = 1 / scale.fY;
1729     dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
1730     dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1731     dst->fMat[kMPersp1] = 0;
1732
1733     dst->fMat[kMTransX] = srcPt[0].fX;
1734     dst->fMat[kMTransY] = srcPt[0].fY;
1735     dst->fMat[kMPersp2] = 1;
1736     dst->setTypeMask(kUnknown_Mask);
1737     return true;
1738 }
1739
1740 bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst,
1741                          const SkPoint& scale) {
1742     float   a1, a2;
1743     float   x0, y0, x1, y1, x2, y2;
1744
1745     x0 = srcPt[2].fX - srcPt[0].fX;
1746     y0 = srcPt[2].fY - srcPt[0].fY;
1747     x1 = srcPt[2].fX - srcPt[1].fX;
1748     y1 = srcPt[2].fY - srcPt[1].fY;
1749     x2 = srcPt[2].fX - srcPt[3].fX;
1750     y2 = srcPt[2].fY - srcPt[3].fY;
1751
1752     /* check if abs(x2) > abs(y2) */
1753     if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) {
1754         float denom = SkScalarMulDiv(x1, y2, x2) - y1;
1755         if (checkForZero(denom)) {
1756             return false;
1757         }
1758         a1 = SkScalarDiv(SkScalarMulDiv(x0 - x1, y2, x2) - y0 + y1, denom);
1759     } else {
1760         float denom = x1 - SkScalarMulDiv(y1, x2, y2);
1761         if (checkForZero(denom)) {
1762             return false;
1763         }
1764         a1 = SkScalarDiv(x0 - x1 - SkScalarMulDiv(y0 - y1, x2, y2), denom);
1765     }
1766
1767     /* check if abs(x1) > abs(y1) */
1768     if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) {
1769         float denom = y2 - SkScalarMulDiv(x2, y1, x1);
1770         if (checkForZero(denom)) {
1771             return false;
1772         }
1773         a2 = SkScalarDiv(y0 - y2 - SkScalarMulDiv(x0 - x2, y1, x1), denom);
1774     } else {
1775         float denom = SkScalarMulDiv(y2, x1, y1) - x2;
1776         if (checkForZero(denom)) {
1777             return false;
1778         }
1779         a2 = SkScalarDiv(SkScalarMulDiv(y0 - y2, x1, y1) - x0 + x2, denom);
1780     }
1781
1782     float invScale = 1 / scale.fX;
1783     dst->fMat[kMScaleX] = SkScalarMul(SkScalarMul(a2, srcPt[3].fX) +
1784                                       srcPt[3].fX - srcPt[0].fX, invScale);
1785     dst->fMat[kMSkewY] = SkScalarMul(SkScalarMul(a2, srcPt[3].fY) +
1786                                      srcPt[3].fY - srcPt[0].fY, invScale);
1787     dst->fMat[kMPersp0] = SkScalarMul(a2, invScale);
1788     invScale = 1 / scale.fY;
1789     dst->fMat[kMSkewX] = SkScalarMul(SkScalarMul(a1, srcPt[1].fX) +
1790                                      srcPt[1].fX - srcPt[0].fX, invScale);
1791     dst->fMat[kMScaleY] = SkScalarMul(SkScalarMul(a1, srcPt[1].fY) +
1792                                       srcPt[1].fY - srcPt[0].fY, invScale);
1793     dst->fMat[kMPersp1] = SkScalarMul(a1, invScale);
1794     dst->fMat[kMTransX] = srcPt[0].fX;
1795     dst->fMat[kMTransY] = srcPt[0].fY;
1796     dst->fMat[kMPersp2] = 1;
1797     dst->setTypeMask(kUnknown_Mask);
1798     return true;
1799 }
1800
1801 #endif
1802
1803 typedef bool (*PolyMapProc)(const SkPoint[], SkMatrix*, const SkPoint&);
1804
1805 /*  Taken from Rob Johnson's original sample code in QuickDraw GX
1806 */
1807 bool SkMatrix::setPolyToPoly(const SkPoint src[], const SkPoint dst[],
1808                              int count) {
1809     if ((unsigned)count > 4) {
1810         SkDebugf("--- SkMatrix::setPolyToPoly count out of range %d\n", count);
1811         return false;
1812     }
1813
1814     if (0 == count) {
1815         this->reset();
1816         return true;
1817     }
1818     if (1 == count) {
1819         this->setTranslate(dst[0].fX - src[0].fX, dst[0].fY - src[0].fY);
1820         return true;
1821     }
1822
1823     SkPoint scale;
1824     if (!poly_to_point(&scale, src, count) ||
1825             SkScalarNearlyZero(scale.fX) ||
1826             SkScalarNearlyZero(scale.fY)) {
1827         return false;
1828     }
1829
1830     static const PolyMapProc gPolyMapProcs[] = {
1831         SkMatrix::Poly2Proc, SkMatrix::Poly3Proc, SkMatrix::Poly4Proc
1832     };
1833     PolyMapProc proc = gPolyMapProcs[count - 2];
1834
1835     SkMatrix tempMap, result;
1836     tempMap.setTypeMask(kUnknown_Mask);
1837
1838     if (!proc(src, &tempMap, scale)) {
1839         return false;
1840     }
1841     if (!tempMap.invert(&result)) {
1842         return false;
1843     }
1844     if (!proc(dst, &tempMap, scale)) {
1845         return false;
1846     }
1847     if (!result.setConcat(tempMap, result)) {
1848         return false;
1849     }
1850     *this = result;
1851     return true;
1852 }
1853
1854 ///////////////////////////////////////////////////////////////////////////////
1855
1856 SkScalar SkMatrix::getMaxStretch() const {
1857     TypeMask mask = this->getType();
1858
1859     if (this->hasPerspective()) {
1860         return -SK_Scalar1;
1861     }
1862     if (this->isIdentity()) {
1863         return SK_Scalar1;
1864     }
1865     if (!(mask & kAffine_Mask)) {
1866         return SkMaxScalar(SkScalarAbs(fMat[kMScaleX]),
1867                            SkScalarAbs(fMat[kMScaleY]));
1868     }
1869     // ignore the translation part of the matrix, just look at 2x2 portion.
1870     // compute singular values, take largest abs value.
1871     // [a b; b c] = A^T*A
1872     SkScalar a = SkScalarMul(fMat[kMScaleX], fMat[kMScaleX]) +
1873                  SkScalarMul(fMat[kMSkewY],  fMat[kMSkewY]);
1874     SkScalar b = SkScalarMul(fMat[kMScaleX], fMat[kMSkewX]) +
1875                  SkScalarMul(fMat[kMScaleY], fMat[kMSkewY]);
1876     SkScalar c = SkScalarMul(fMat[kMSkewX],  fMat[kMSkewX]) +
1877                  SkScalarMul(fMat[kMScaleY], fMat[kMScaleY]);
1878     // eigenvalues of A^T*A are the squared singular values of A.
1879     // characteristic equation is det((A^T*A) - l*I) = 0
1880     // l^2 - (a + c)l + (ac-b^2)
1881     // solve using quadratic equation (divisor is non-zero since l^2 has 1 coeff
1882     // and roots are guaraunteed to be pos and real).
1883     SkScalar largerRoot;
1884     SkScalar bSqd = SkScalarMul(b,b);
1885     // if upper left 2x2 is orthogonal save some math
1886     if (bSqd <= SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
1887         largerRoot = SkMaxScalar(a, c);
1888     } else {
1889         SkScalar aminusc = a - c;
1890         SkScalar apluscdiv2 = SkScalarHalf(a + c);
1891         SkScalar x = SkScalarHalf(SkScalarSqrt(SkScalarMul(aminusc, aminusc) + 4 * bSqd));
1892         largerRoot = apluscdiv2 + x;
1893     }
1894     return SkScalarSqrt(largerRoot);
1895 }
1896
1897 static void reset_identity_matrix(SkMatrix* identity) {
1898     identity->reset();
1899 }
1900
1901 const SkMatrix& SkMatrix::I() {
1902     // If you can use C++11 now, you might consider replacing this with a constexpr constructor.
1903     static SkMatrix gIdentity;
1904     SK_DECLARE_STATIC_ONCE(once);
1905     SkOnce(&once, reset_identity_matrix, &gIdentity);
1906     return gIdentity;
1907 }
1908
1909 const SkMatrix& SkMatrix::InvalidMatrix() {
1910     static SkMatrix gInvalid;
1911     static bool gOnce;
1912     if (!gOnce) {
1913         gInvalid.setAll(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
1914                         SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
1915                         SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1916         gInvalid.getType(); // force the type to be computed
1917         gOnce = true;
1918     }
1919     return gInvalid;
1920 }
1921
1922 ///////////////////////////////////////////////////////////////////////////////
1923
1924 uint32_t SkMatrix::writeToMemory(void* buffer) const {
1925     // TODO write less for simple matrices
1926     if (buffer) {
1927         memcpy(buffer, fMat, 9 * sizeof(SkScalar));
1928     }
1929     return 9 * sizeof(SkScalar);
1930 }
1931
1932 uint32_t SkMatrix::readFromMemory(const void* buffer) {
1933     if (buffer) {
1934         memcpy(fMat, buffer, 9 * sizeof(SkScalar));
1935         this->setTypeMask(kUnknown_Mask);
1936     }
1937     return 9 * sizeof(SkScalar);
1938 }
1939
1940 #ifdef SK_DEVELOPER
1941 void SkMatrix::dump() const {
1942     SkString str;
1943     this->toString(&str);
1944     SkDebugf("%s\n", str.c_str());
1945 }
1946
1947 void SkMatrix::toString(SkString* str) const {
1948     str->appendf("[%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f]",
1949 #ifdef SK_SCALAR_IS_FLOAT
1950              fMat[0], fMat[1], fMat[2], fMat[3], fMat[4], fMat[5],
1951              fMat[6], fMat[7], fMat[8]);
1952 #else
1953     SkFixedToFloat(fMat[0]), SkFixedToFloat(fMat[1]), SkFixedToFloat(fMat[2]),
1954     SkFixedToFloat(fMat[3]), SkFixedToFloat(fMat[4]), SkFixedToFloat(fMat[5]),
1955     SkFractToFloat(fMat[6]), SkFractToFloat(fMat[7]), SkFractToFloat(fMat[8]));
1956 #endif
1957 }
1958 #endif
1959
1960 ///////////////////////////////////////////////////////////////////////////////
1961
1962 #include "SkMatrixUtils.h"
1963
1964 bool SkTreatAsSprite(const SkMatrix& mat, int width, int height,
1965                      unsigned subpixelBits) {
1966     // quick reject on affine or perspective
1967     if (mat.getType() & ~(SkMatrix::kScale_Mask | SkMatrix::kTranslate_Mask)) {
1968         return false;
1969     }
1970
1971     // quick success check
1972     if (!subpixelBits && !(mat.getType() & ~SkMatrix::kTranslate_Mask)) {
1973         return true;
1974     }
1975
1976     // mapRect supports negative scales, so we eliminate those first
1977     if (mat.getScaleX() < 0 || mat.getScaleY() < 0) {
1978         return false;
1979     }
1980
1981     SkRect dst;
1982     SkIRect isrc = { 0, 0, width, height };
1983
1984     {
1985         SkRect src;
1986         src.set(isrc);
1987         mat.mapRect(&dst, src);
1988     }
1989
1990     // just apply the translate to isrc
1991     isrc.offset(SkScalarRoundToInt(mat.getTranslateX()),
1992                 SkScalarRoundToInt(mat.getTranslateY()));
1993
1994     if (subpixelBits) {
1995         isrc.fLeft <<= subpixelBits;
1996         isrc.fTop <<= subpixelBits;
1997         isrc.fRight <<= subpixelBits;
1998         isrc.fBottom <<= subpixelBits;
1999
2000         const float scale = 1 << subpixelBits;
2001         dst.fLeft *= scale;
2002         dst.fTop *= scale;
2003         dst.fRight *= scale;
2004         dst.fBottom *= scale;
2005     }
2006
2007     SkIRect idst;
2008     dst.round(&idst);
2009     return isrc == idst;
2010 }
2011
2012 // A square matrix M can be decomposed (via polar decomposition) into two matrices --
2013 // an orthogonal matrix Q and a symmetric matrix S. In turn we can decompose S into U*W*U^T,
2014 // where U is another orthogonal matrix and W is a scale matrix. These can be recombined
2015 // to give M = (Q*U)*W*U^T, i.e., the product of two orthogonal matrices and a scale matrix.
2016 //
2017 // The one wrinkle is that traditionally Q may contain a reflection -- the
2018 // calculation has been rejiggered to put that reflection into W.
2019 bool SkDecomposeUpper2x2(const SkMatrix& matrix,
2020                          SkPoint* rotation1,
2021                          SkPoint* scale,
2022                          SkPoint* rotation2) {
2023
2024     SkScalar A = matrix[SkMatrix::kMScaleX];
2025     SkScalar B = matrix[SkMatrix::kMSkewX];
2026     SkScalar C = matrix[SkMatrix::kMSkewY];
2027     SkScalar D = matrix[SkMatrix::kMScaleY];
2028
2029     if (is_degenerate_2x2(A, B, C, D)) {
2030         return false;
2031     }
2032
2033     double w1, w2;
2034     SkScalar cos1, sin1;
2035     SkScalar cos2, sin2;
2036
2037     // do polar decomposition (M = Q*S)
2038     SkScalar cosQ, sinQ;
2039     double Sa, Sb, Sd;
2040     // if M is already symmetric (i.e., M = I*S)
2041     if (SkScalarNearlyEqual(B, C)) {
2042         cosQ = SK_Scalar1;
2043         sinQ = 0;
2044
2045         Sa = A;
2046         Sb = B;
2047         Sd = D;
2048     } else {
2049         cosQ = A + D;
2050         sinQ = C - B;
2051         SkScalar reciplen = SK_Scalar1/SkScalarSqrt(cosQ*cosQ + sinQ*sinQ);
2052         cosQ *= reciplen;
2053         sinQ *= reciplen;
2054
2055         // S = Q^-1*M
2056         // we don't calc Sc since it's symmetric
2057         Sa = A*cosQ + C*sinQ;
2058         Sb = B*cosQ + D*sinQ;
2059         Sd = -B*sinQ + D*cosQ;
2060     }
2061
2062     // Now we need to compute eigenvalues of S (our scale factors)
2063     // and eigenvectors (bases for our rotation)
2064     // From this, should be able to reconstruct S as U*W*U^T
2065     if (SkScalarNearlyZero(SkDoubleToScalar(Sb))) {
2066         // already diagonalized
2067         cos1 = SK_Scalar1;
2068         sin1 = 0;
2069         w1 = Sa;
2070         w2 = Sd;
2071         cos2 = cosQ;
2072         sin2 = sinQ;
2073     } else {
2074         double diff = Sa - Sd;
2075         double discriminant = sqrt(diff*diff + 4.0*Sb*Sb);
2076         double trace = Sa + Sd;
2077         if (diff > 0) {
2078             w1 = 0.5*(trace + discriminant);
2079             w2 = 0.5*(trace - discriminant);
2080         } else {
2081             w1 = 0.5*(trace - discriminant);
2082             w2 = 0.5*(trace + discriminant);
2083         }
2084
2085         cos1 = SkDoubleToScalar(Sb); sin1 = SkDoubleToScalar(w1 - Sa);
2086         SkScalar reciplen = SK_Scalar1/SkScalarSqrt(cos1*cos1 + sin1*sin1);
2087         cos1 *= reciplen;
2088         sin1 *= reciplen;
2089
2090         // rotation 2 is composition of Q and U
2091         cos2 = cos1*cosQ - sin1*sinQ;
2092         sin2 = sin1*cosQ + cos1*sinQ;
2093
2094         // rotation 1 is U^T
2095         sin1 = -sin1;
2096     }
2097
2098     if (NULL != scale) {
2099         scale->fX = SkDoubleToScalar(w1);
2100         scale->fY = SkDoubleToScalar(w2);
2101     }
2102     if (NULL != rotation1) {
2103         rotation1->fX = cos1;
2104         rotation1->fY = sin1;
2105     }
2106     if (NULL != rotation2) {
2107         rotation2->fX = cos2;
2108         rotation2->fY = sin2;
2109     }
2110
2111     return true;
2112 }