• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
SkDoubleToFloat(double x)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 
reset()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 
computePerspectiveTypeMask() const58 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 
computeTypeMask() const73 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 
operator ==(const SkMatrix & a,const SkMatrix & b)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
is_degenerate_2x2(SkScalar scaleX,SkScalar skewX,SkScalar skewY,SkScalar scaleY)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 
isSimilarity(SkScalar tol) const156 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 
preservesRightAngles(SkScalar tol) const185 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 
sdot(SkScalar a,SkScalar b,SkScalar c,SkScalar d)217 static inline SkScalar sdot(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
218     return a * b + c * d;
219 }
220 
sdot(SkScalar a,SkScalar b,SkScalar c,SkScalar d,SkScalar e,SkScalar f)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 
scross(SkScalar a,SkScalar b,SkScalar c,SkScalar d)226 static inline SkScalar scross(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
227     return a * b - c * d;
228 }
229 
setTranslate(SkScalar dx,SkScalar dy)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 
preTranslate(SkScalar dx,SkScalar dy)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 
postTranslate(SkScalar dx,SkScalar dy)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 
setScale(SkScalar sx,SkScalar sy,SkScalar px,SkScalar py)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 
setScale(SkScalar sx,SkScalar sy)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 
setIDiv(int divx,int divy)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 
preScale(SkScalar sx,SkScalar sy,SkScalar px,SkScalar py)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 
preScale(SkScalar sx,SkScalar sy)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 
postScale(SkScalar sx,SkScalar sy,SkScalar px,SkScalar py)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 
postScale(SkScalar sx,SkScalar sy)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
postIDiv(int divx,int divy)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 
setSinCos(SkScalar sinV,SkScalar cosV,SkScalar px,SkScalar py)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 
setSinCos(SkScalar sinV,SkScalar cosV)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 
setRotate(SkScalar degrees,SkScalar px,SkScalar py)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 
setRotate(SkScalar degrees)432 void SkMatrix::setRotate(SkScalar degrees) {
433     SkScalar sinV, cosV;
434     sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
435     this->setSinCos(sinV, cosV);
436 }
437 
preRotate(SkScalar degrees,SkScalar px,SkScalar py)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 
preRotate(SkScalar degrees)444 void SkMatrix::preRotate(SkScalar degrees) {
445     SkMatrix    m;
446     m.setRotate(degrees);
447     this->preConcat(m);
448 }
449 
postRotate(SkScalar degrees,SkScalar px,SkScalar py)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 
postRotate(SkScalar degrees)456 void SkMatrix::postRotate(SkScalar degrees) {
457     SkMatrix    m;
458     m.setRotate(degrees);
459     this->postConcat(m);
460 }
461 
462 ////////////////////////////////////////////////////////////////////////////////////
463 
setSkew(SkScalar sx,SkScalar sy,SkScalar px,SkScalar py)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 
setSkew(SkScalar sx,SkScalar sy)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 
preSkew(SkScalar sx,SkScalar sy,SkScalar px,SkScalar py)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 
preSkew(SkScalar sx,SkScalar sy)500 void SkMatrix::preSkew(SkScalar sx, SkScalar sy) {
501     SkMatrix    m;
502     m.setSkew(sx, sy);
503     this->preConcat(m);
504 }
505 
postSkew(SkScalar sx,SkScalar sy,SkScalar px,SkScalar py)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 
postSkew(SkScalar sx,SkScalar sy)512 void SkMatrix::postSkew(SkScalar sx, SkScalar sy) {
513     SkMatrix    m;
514     m.setSkew(sx, sy);
515     this->postConcat(m);
516 }
517 
518 ///////////////////////////////////////////////////////////////////////////////
519 
setRectToRect(const SkRect & src,const SkRect & dst,ScaleToFit align)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 
muladdmul(float a,float b,float c,float d)590 static inline float muladdmul(float a, float b, float c, float d) {
591     return SkDoubleToFloat((double)a * b + (double)c * d);
592 }
593 
rowcol3(const float row[],const float col[])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 
normalize_perspective(SkScalar mat[9])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 
setConcat(const SkMatrix & a,const SkMatrix & b)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 
preConcat(const SkMatrix & mat)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 
postConcat(const SkMatrix & mat)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 
scross_dscale(SkScalar a,SkScalar b,SkScalar c,SkScalar d,double scale)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 
dcross(double a,double b,double c,double d)702 static inline double dcross(double a, double b, double c, double d) {
703     return a * b - c * d;
704 }
705 
dcross_dscale(double a,double b,double c,double d,double scale)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 
sk_inv_determinant(const float mat[9],int isPerspective)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 
SetAffineIdentity(SkScalar affine[6])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 
asAffine(SkScalar affine[6]) const749 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 
invertNonIdentity(SkMatrix * inv) const764 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 
Identity_pts(const SkMatrix & m,SkPoint dst[],const SkPoint src[],int count)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 
Trans_pts(const SkMatrix & m,SkPoint dst[],const SkPoint src[],int count)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 
Scale_pts(const SkMatrix & m,SkPoint dst[],const SkPoint src[],int count)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 
ScaleTrans_pts(const SkMatrix & m,SkPoint dst[],const SkPoint src[],int count)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 
Rot_pts(const SkMatrix & m,SkPoint dst[],const SkPoint src[],int count)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 
RotTrans_pts(const SkMatrix & m,SkPoint dst[],const SkPoint src[],int count)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 
Persp_pts(const SkMatrix & m,SkPoint dst[],const SkPoint src[],int count)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 
mapPoints(SkPoint dst[],const SkPoint src[],int count) const1001 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 
mapHomogeneousPoints(SkScalar dst[],const SkScalar src[],int count) const1011 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 
mapVectors(SkPoint dst[],const SkPoint src[],int count) const1041 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 
mapRect(SkRect * dst,const SkRect & src) const1063 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 
mapRadius(SkScalar radius) const1080 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 
Persp_xy(const SkMatrix & m,SkScalar sx,SkScalar sy,SkPoint * pt)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 
RotTrans_xy(const SkMatrix & m,SkScalar sx,SkScalar sy,SkPoint * pt)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 
Rot_xy(const SkMatrix & m,SkScalar sx,SkScalar sy,SkPoint * pt)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 
ScaleTrans_xy(const SkMatrix & m,SkScalar sx,SkScalar sy,SkPoint * pt)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 
Scale_xy(const SkMatrix & m,SkScalar sx,SkScalar sy,SkPoint * pt)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 
Trans_xy(const SkMatrix & m,SkScalar sx,SkScalar sy,SkPoint * pt)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 
Identity_xy(const SkMatrix & m,SkScalar sx,SkScalar sy,SkPoint * pt)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 
fixedStepInX(SkScalar y,SkFixed * stepX,SkFixed * stepY) const1191 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 
SkPerspIter(const SkMatrix & m,SkScalar x0,SkScalar y0,int count)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 
next()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 
checkForZero(float x)1270 static inline bool checkForZero(float x) {
1271     return x*x == 0;
1272 }
1273 
poly_to_point(SkPoint * pt,const SkPoint poly[],int count)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 
Poly2Proc(const SkPoint srcPt[],SkMatrix * dst,const SkPoint & scale)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 
Poly3Proc(const SkPoint srcPt[],SkMatrix * dst,const SkPoint & scale)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 
Poly4Proc(const SkPoint srcPt[],SkMatrix * dst,const SkPoint & scale)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 */
setPolyToPoly(const SkPoint src[],const SkPoint dst[],int count)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 
get_scale_factor(SkMatrix::TypeMask typeMask,const SkScalar m[9],SkScalar results[])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 
getMinScale() const1534 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 
getMaxScale() const1543 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 
getMinMaxScales(SkScalar scaleFactors[2]) const1552 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 
asSkMatrix__anonfa07d34e0211::PODMatrix1562     const SkMatrix& asSkMatrix() const { return *reinterpret_cast<const SkMatrix*>(this); }
1563 };
1564 SK_COMPILE_ASSERT(sizeof(PODMatrix) == sizeof(SkMatrix), PODMatrixSizeMismatch);
1565 
1566 }  // namespace
1567 
I()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 
InvalidMatrix()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 
writeToMemory(void * buffer) const1594 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 
readFromMemory(const void * buffer,size_t length)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
dump() const1616 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
toString(SkString * str) const1624 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 
SkTreatAsSprite(const SkMatrix & mat,int width,int height,unsigned subpixelBits)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.
SkDecomposeUpper2x2(const SkMatrix & matrix,SkPoint * rotation1,SkPoint * scale,SkPoint * rotation2)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 }
1784