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
Normalize(SkPoint * pt)82 SkScalar SkPoint::Normalize(SkPoint* pt) {
83 float mag = SkPoint::Length(pt->fX, pt->fY);
84 if (mag > kNearlyZero) {
85 float scale = 1 / mag;
86 pt->fX *= scale;
87 pt->fY *= scale;
88 return mag;
89 }
90 return 0;
91 }
92
setLength(float x,float y,float length)93 bool SkPoint::setLength(float x, float y, float length) {
94 float mag = sk_float_sqrt(x * x + y * y);
95 if (mag > kNearlyZero) {
96 length /= mag;
97 fX = x * length;
98 fY = y * length;
99 return true;
100 }
101 return false;
102 }
103
104 #else
105
106 #include "Sk64.h"
107
Length(SkScalar dx,SkScalar dy)108 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
109 Sk64 tmp1, tmp2;
110
111 tmp1.setMul(dx, dx);
112 tmp2.setMul(dy, dy);
113 tmp1.add(tmp2);
114
115 return tmp1.getSqrt();
116 }
117
118 #ifdef SK_DEBUGx
fixlen(SkFixed x,SkFixed y)119 static SkFixed fixlen(SkFixed x, SkFixed y) {
120 float fx = (float)x;
121 float fy = (float)y;
122
123 return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f);
124 }
125 #endif
126
squarefixed(unsigned x)127 static inline uint32_t squarefixed(unsigned x) {
128 x >>= 16;
129 return x*x;
130 }
131
132 #if 1 // Newton iter for setLength
133
invsqrt_iter(unsigned V,unsigned U)134 static inline unsigned invsqrt_iter(unsigned V, unsigned U) {
135 unsigned x = V * U >> 14;
136 x = x * U >> 14;
137 x = (3 << 14) - x;
138 x = (U >> 1) * x >> 14;
139 return x;
140 }
141
142 static const uint16_t gInvSqrt14GuessTable[] = {
143 0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061,
144 0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780,
145 0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235,
146 0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99,
147 0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee,
148 0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc,
149 0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830,
150 0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce
151 };
152
153 #define BUILD_INVSQRT_TABLEx
154 #ifdef BUILD_INVSQRT_TABLE
build_invsqrt14_guess_table()155 static void build_invsqrt14_guess_table() {
156 for (int i = 8; i <= 63; i++) {
157 unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25));
158 printf("0x%x, ", x);
159 }
160 printf("\n");
161 }
162 #endif
163
fast_invsqrt(uint32_t x)164 static unsigned fast_invsqrt(uint32_t x) {
165 #ifdef BUILD_INVSQRT_TABLE
166 unsigned top2 = x >> 25;
167 SkASSERT(top2 >= 8 && top2 <= 63);
168
169 static bool gOnce;
170 if (!gOnce) {
171 build_invsqrt14_guess_table();
172 gOnce = true;
173 }
174 #endif
175
176 unsigned V = x >> 14; // make V .14
177
178 unsigned top = x >> 25;
179 SkASSERT(top >= 8 && top <= 63);
180 SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable));
181 unsigned U = gInvSqrt14GuessTable[top - 8];
182
183 U = invsqrt_iter(V, U);
184 return invsqrt_iter(V, U);
185 }
186
187 /* We "normalize" x,y to be .14 values (so we can square them and stay 32bits.
188 Then we Newton-iterate this in .14 space to compute the invser-sqrt, and
189 scale by it at the end. The .14 space means we can execute our iterations
190 and stay in 32bits as well, making the multiplies much cheaper than calling
191 SkFixedMul.
192 */
setLength(SkFixed ox,SkFixed oy,SkFixed length)193 bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
194 if (ox == 0) {
195 if (oy == 0) {
196 return false;
197 }
198 this->set(0, SkApplySign(length, SkExtractSign(oy)));
199 return true;
200 }
201 if (oy == 0) {
202 this->set(SkApplySign(length, SkExtractSign(ox)), 0);
203 return true;
204 }
205
206 unsigned x = SkAbs32(ox);
207 unsigned y = SkAbs32(oy);
208 int zeros = SkCLZ(x | y);
209
210 // make x,y 1.14 values so our fast sqr won't overflow
211 if (zeros > 17) {
212 x <<= zeros - 17;
213 y <<= zeros - 17;
214 } else {
215 x >>= 17 - zeros;
216 y >>= 17 - zeros;
217 }
218 SkASSERT((x | y) <= 0x7FFF);
219
220 unsigned invrt = fast_invsqrt(x*x + y*y);
221
222 x = x * invrt >> 12;
223 y = y * invrt >> 12;
224
225 if (length != SK_Fixed1) {
226 x = SkFixedMul(x, length);
227 y = SkFixedMul(y, length);
228 }
229 this->set(SkApplySign(x, SkExtractSign(ox)),
230 SkApplySign(y, SkExtractSign(oy)));
231 return true;
232 }
233 #else
234 /*
235 Normalize x,y, and then scale them by length.
236
237 The obvious way to do this would be the following:
238 S64 tmp1, tmp2;
239 tmp1.setMul(x,x);
240 tmp2.setMul(y,y);
241 tmp1.add(tmp2);
242 len = tmp1.getSqrt();
243 x' = SkFixedDiv(x, len);
244 y' = SkFixedDiv(y, len);
245 This is fine, but slower than what we do below.
246
247 The present technique does not compute the starting length, but
248 rather fiddles with x,y iteratively, all the while checking its
249 magnitude^2 (avoiding a sqrt).
250
251 We normalize by first shifting x,y so that at least one of them
252 has bit 31 set (after taking the abs of them).
253 Then we loop, refining x,y by squaring them and comparing
254 against a very large 1.0 (1 << 28), and then adding or subtracting
255 a delta (which itself is reduced by half each time through the loop).
256 For speed we want the squaring to be with a simple integer mul. To keep
257 that from overflowing we shift our coordinates down until we are dealing
258 with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits)
259 When our square is close to 1.0, we shift x,y down into fixed range.
260 */
setLength(SkFixed ox,SkFixed oy,SkFixed length)261 bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
262 if (ox == 0) {
263 if (oy == 0)
264 return false;
265 this->set(0, SkApplySign(length, SkExtractSign(oy)));
266 return true;
267 }
268 if (oy == 0) {
269 this->set(SkApplySign(length, SkExtractSign(ox)), 0);
270 return true;
271 }
272
273 SkFixed x = SkAbs32(ox);
274 SkFixed y = SkAbs32(oy);
275
276 // shift x,y so that the greater of them is 15bits (1.14 fixed point)
277 {
278 int shift = SkCLZ(x | y);
279 // make them .30
280 x <<= shift - 1;
281 y <<= shift - 1;
282 }
283
284 SkFixed dx = x;
285 SkFixed dy = y;
286
287 for (int i = 0; i < 17; i++) {
288 dx >>= 1;
289 dy >>= 1;
290
291 U32 len2 = squarefixed(x) + squarefixed(y);
292 if (len2 >> 28) {
293 x -= dx;
294 y -= dy;
295 } else {
296 x += dx;
297 y += dy;
298 }
299 }
300 x >>= 14;
301 y >>= 14;
302
303 #ifdef SK_DEBUGx // measure how far we are from unit-length
304 {
305 static int gMaxError;
306 static int gMaxDiff;
307
308 SkFixed len = fixlen(x, y);
309 int err = len - SK_Fixed1;
310 err = SkAbs32(err);
311
312 if (err > gMaxError) {
313 gMaxError = err;
314 SkDebugf("gMaxError %d\n", err);
315 }
316
317 float fx = SkAbs32(ox)/65536.0f;
318 float fy = SkAbs32(oy)/65536.0f;
319 float mag = sqrtf(fx*fx + fy*fy);
320 fx /= mag;
321 fy /= mag;
322 SkFixed xx = (int)floorf(fx * 65536 + 0.5f);
323 SkFixed yy = (int)floorf(fy * 65536 + 0.5f);
324 err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y));
325 if (err > gMaxDiff) {
326 gMaxDiff = err;
327 SkDebugf("gMaxDiff %d\n", err);
328 }
329 }
330 #endif
331
332 x = SkApplySign(x, SkExtractSign(ox));
333 y = SkApplySign(y, SkExtractSign(oy));
334 if (length != SK_Fixed1) {
335 x = SkFixedMul(x, length);
336 y = SkFixedMul(y, length);
337 }
338
339 this->set(x, y);
340 return true;
341 }
342 #endif
343
344 #endif
345
346