| OLD | NEW |
|---|
| (Empty) |
| 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 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 | |
| 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 */ | |
| 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 */ | |
| 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 113827:
Remove the remainder of the skia source code from the Chromium repo.... (Closed)
Base URL: svn://chrome-svn/chrome/trunk/src/