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