1 /*
2 * Copyright (C) 2006-2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "SkPoint.h"
18
rotateCW(SkIPoint * dst) const19 void SkIPoint::rotateCW(SkIPoint* dst) const {
20 SkASSERT(dst);
21
22 // use a tmp in case this == dst
23 int32_t tmp = fX;
24 dst->fX = -fY;
25 dst->fY = tmp;
26 }
27
rotateCCW(SkIPoint * dst) const28 void SkIPoint::rotateCCW(SkIPoint* dst) const {
29 SkASSERT(dst);
30
31 // use a tmp in case this == dst
32 int32_t tmp = fX;
33 dst->fX = fY;
34 dst->fY = -tmp;
35 }
36
37 ///////////////////////////////////////////////////////////////////////////////
38
rotateCW(SkPoint * dst) const39 void SkPoint::rotateCW(SkPoint* dst) const {
40 SkASSERT(dst);
41
42 // use a tmp in case this == dst
43 SkScalar tmp = fX;
44 dst->fX = -fY;
45 dst->fY = tmp;
46 }
47
rotateCCW(SkPoint * dst) const48 void SkPoint::rotateCCW(SkPoint* dst) const {
49 SkASSERT(dst);
50
51 // use a tmp in case this == dst
52 SkScalar tmp = fX;
53 dst->fX = fY;
54 dst->fY = -tmp;
55 }
56
scale(SkScalar scale,SkPoint * dst) const57 void SkPoint::scale(SkScalar scale, SkPoint* dst) const {
58 SkASSERT(dst);
59 dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale));
60 }
61
62 #define kNearlyZero (SK_Scalar1 / 8092)
63
normalize()64 bool SkPoint::normalize() {
65 return this->setLength(fX, fY, SK_Scalar1);
66 }
67
setNormalize(SkScalar x,SkScalar y)68 bool SkPoint::setNormalize(SkScalar x, SkScalar y) {
69 return this->setLength(x, y, SK_Scalar1);
70 }
71
setLength(SkScalar length)72 bool SkPoint::setLength(SkScalar length) {
73 return this->setLength(fX, fY, length);
74 }
75
76 #ifdef SK_SCALAR_IS_FLOAT
77
Length(SkScalar dx,SkScalar dy)78 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
79 return sk_float_sqrt(dx * dx + dy * dy);
80 }
81
setLength(float x,float y,float length)82 bool SkPoint::setLength(float x, float y, float length) {
83 float mag = sk_float_sqrt(x * x + y * y);
84 if (mag > kNearlyZero) {
85 length /= mag;
86 fX = x * length;
87 fY = y * length;
88 return true;
89 }
90 return false;
91 }
92
93 #else
94
95 #include "Sk64.h"
96
Length(SkScalar dx,SkScalar dy)97 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
98 Sk64 tmp1, tmp2;
99
100 tmp1.setMul(dx, dx);
101 tmp2.setMul(dy, dy);
102 tmp1.add(tmp2);
103
104 return tmp1.getSqrt();
105 }
106
107 #ifdef SK_DEBUGx
fixlen(SkFixed x,SkFixed y)108 static SkFixed fixlen(SkFixed x, SkFixed y) {
109 float fx = (float)x;
110 float fy = (float)y;
111
112 return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f);
113 }
114 #endif
115
squarefixed(unsigned x)116 static inline uint32_t squarefixed(unsigned x) {
117 x >>= 16;
118 return x*x;
119 }
120
121 #if 1 // Newton iter for setLength
122
invsqrt_iter(unsigned V,unsigned U)123 static inline unsigned invsqrt_iter(unsigned V, unsigned U) {
124 unsigned x = V * U >> 14;
125 x = x * U >> 14;
126 x = (3 << 14) - x;
127 x = (U >> 1) * x >> 14;
128 return x;
129 }
130
131 static const uint16_t gInvSqrt14GuessTable[] = {
132 0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061,
133 0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780,
134 0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235,
135 0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99,
136 0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee,
137 0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc,
138 0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830,
139 0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce
140 };
141
142 #define BUILD_INVSQRT_TABLEx
143 #ifdef BUILD_INVSQRT_TABLE
build_invsqrt14_guess_table()144 static void build_invsqrt14_guess_table() {
145 for (int i = 8; i <= 63; i++) {
146 unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25));
147 printf("0x%x, ", x);
148 }
149 printf("\n");
150 }
151 #endif
152
fast_invsqrt(uint32_t x)153 static unsigned fast_invsqrt(uint32_t x) {
154 #ifdef BUILD_INVSQRT_TABLE
155 unsigned top2 = x >> 25;
156 SkASSERT(top2 >= 8 && top2 <= 63);
157
158 static bool gOnce;
159 if (!gOnce) {
160 build_invsqrt14_guess_table();
161 gOnce = true;
162 }
163 #endif
164
165 unsigned V = x >> 14; // make V .14
166
167 unsigned top = x >> 25;
168 SkASSERT(top >= 8 && top <= 63);
169 SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable));
170 unsigned U = gInvSqrt14GuessTable[top - 8];
171
172 U = invsqrt_iter(V, U);
173 return invsqrt_iter(V, U);
174 }
175
176 /* We "normalize" x,y to be .14 values (so we can square them and stay 32bits.
177 Then we Newton-iterate this in .14 space to compute the invser-sqrt, and
178 scale by it at the end. The .14 space means we can execute our iterations
179 and stay in 32bits as well, making the multiplies much cheaper than calling
180 SkFixedMul.
181 */
setLength(SkFixed ox,SkFixed oy,SkFixed length)182 bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
183 if (ox == 0) {
184 if (oy == 0) {
185 return false;
186 }
187 this->set(0, SkApplySign(length, SkExtractSign(oy)));
188 return true;
189 }
190 if (oy == 0) {
191 this->set(SkApplySign(length, SkExtractSign(ox)), 0);
192 return true;
193 }
194
195 unsigned x = SkAbs32(ox);
196 unsigned y = SkAbs32(oy);
197 int zeros = SkCLZ(x | y);
198
199 // make x,y 1.14 values so our fast sqr won't overflow
200 if (zeros > 17) {
201 x <<= zeros - 17;
202 y <<= zeros - 17;
203 } else {
204 x >>= 17 - zeros;
205 y >>= 17 - zeros;
206 }
207 SkASSERT((x | y) <= 0x7FFF);
208
209 unsigned invrt = fast_invsqrt(x*x + y*y);
210
211 x = x * invrt >> 12;
212 y = y * invrt >> 12;
213
214 if (length != SK_Fixed1) {
215 x = SkFixedMul(x, length);
216 y = SkFixedMul(y, length);
217 }
218 this->set(SkApplySign(x, SkExtractSign(ox)),
219 SkApplySign(y, SkExtractSign(oy)));
220 return true;
221 }
222 #else
223 /*
224 Normalize x,y, and then scale them by length.
225
226 The obvious way to do this would be the following:
227 S64 tmp1, tmp2;
228 tmp1.setMul(x,x);
229 tmp2.setMul(y,y);
230 tmp1.add(tmp2);
231 len = tmp1.getSqrt();
232 x' = SkFixedDiv(x, len);
233 y' = SkFixedDiv(y, len);
234 This is fine, but slower than what we do below.
235
236 The present technique does not compute the starting length, but
237 rather fiddles with x,y iteratively, all the while checking its
238 magnitude^2 (avoiding a sqrt).
239
240 We normalize by first shifting x,y so that at least one of them
241 has bit 31 set (after taking the abs of them).
242 Then we loop, refining x,y by squaring them and comparing
243 against a very large 1.0 (1 << 28), and then adding or subtracting
244 a delta (which itself is reduced by half each time through the loop).
245 For speed we want the squaring to be with a simple integer mul. To keep
246 that from overflowing we shift our coordinates down until we are dealing
247 with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits)
248 When our square is close to 1.0, we shift x,y down into fixed range.
249 */
setLength(SkFixed ox,SkFixed oy,SkFixed length)250 bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
251 if (ox == 0) {
252 if (oy == 0)
253 return false;
254 this->set(0, SkApplySign(length, SkExtractSign(oy)));
255 return true;
256 }
257 if (oy == 0) {
258 this->set(SkApplySign(length, SkExtractSign(ox)), 0);
259 return true;
260 }
261
262 SkFixed x = SkAbs32(ox);
263 SkFixed y = SkAbs32(oy);
264
265 // shift x,y so that the greater of them is 15bits (1.14 fixed point)
266 {
267 int shift = SkCLZ(x | y);
268 // make them .30
269 x <<= shift - 1;
270 y <<= shift - 1;
271 }
272
273 SkFixed dx = x;
274 SkFixed dy = y;
275
276 for (int i = 0; i < 17; i++) {
277 dx >>= 1;
278 dy >>= 1;
279
280 U32 len2 = squarefixed(x) + squarefixed(y);
281 if (len2 >> 28) {
282 x -= dx;
283 y -= dy;
284 } else {
285 x += dx;
286 y += dy;
287 }
288 }
289 x >>= 14;
290 y >>= 14;
291
292 #ifdef SK_DEBUGx // measure how far we are from unit-length
293 {
294 static int gMaxError;
295 static int gMaxDiff;
296
297 SkFixed len = fixlen(x, y);
298 int err = len - SK_Fixed1;
299 err = SkAbs32(err);
300
301 if (err > gMaxError) {
302 gMaxError = err;
303 SkDebugf("gMaxError %d\n", err);
304 }
305
306 float fx = SkAbs32(ox)/65536.0f;
307 float fy = SkAbs32(oy)/65536.0f;
308 float mag = sqrtf(fx*fx + fy*fy);
309 fx /= mag;
310 fy /= mag;
311 SkFixed xx = (int)floorf(fx * 65536 + 0.5f);
312 SkFixed yy = (int)floorf(fy * 65536 + 0.5f);
313 err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y));
314 if (err > gMaxDiff) {
315 gMaxDiff = err;
316 SkDebugf("gMaxDiff %d\n", err);
317 }
318 }
319 #endif
320
321 x = SkApplySign(x, SkExtractSign(ox));
322 y = SkApplySign(y, SkExtractSign(oy));
323 if (length != SK_Fixed1) {
324 x = SkFixedMul(x, length);
325 y = SkFixedMul(y, length);
326 }
327
328 this->set(x, y);
329 return true;
330 }
331 #endif
332
333 #endif
334
335