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 19 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 28 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 39 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 48 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 57 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 64 bool SkPoint::normalize() { 65 return this->setLength(fX, fY, SK_Scalar1); 66 } 67 68 bool SkPoint::setNormalize(SkScalar x, SkScalar y) { 69 return this->setLength(x, y, SK_Scalar1); 70 } 71 72 bool SkPoint::setLength(SkScalar length) { 73 return this->setLength(fX, fY, length); 74 } 75 76 #ifdef SK_SCALAR_IS_FLOAT 77 78 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { 79 return sk_float_sqrt(dx * dx + dy * dy); 80 } 81 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 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 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 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 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 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 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 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 */ 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 */ 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
