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