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