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