| OLD | NEW |
|---|
| (Empty) |
| 1 /* libs/corecg/Sk64.cpp | |
| 2 ** | |
| 3 ** Copyright 2006, The Android Open Source Project | |
| 4 ** | |
| 5 ** Licensed under the Apache License, Version 2.0 (the "License"); | |
| 6 ** you may not use this file except in compliance with the License. | |
| 7 ** You may obtain a copy of the License at | |
| 8 ** | |
| 9 ** http://www.apache.org/licenses/LICENSE-2.0 | |
| 10 ** | |
| 11 ** Unless required by applicable law or agreed to in writing, software | |
| 12 ** distributed under the License is distributed on an "AS IS" BASIS, | |
| 13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| 14 ** See the License for the specific language governing permissions and | |
| 15 ** limitations under the License. | |
| 16 */ | |
| 17 | |
| 18 #include "Sk64.h" | |
| 19 | |
| 20 #define shift_left(hi, lo) \ | |
| 21 hi = (hi << 1) | (lo >> 31); \ | |
| 22 lo <<= 1 | |
| 23 | |
| 24 #define shift_left_bits(hi, lo, bits) \ | |
| 25 SkASSERT((unsigned)(bits) < 31); \ | |
| 26 hi = (hi << (bits)) | (lo >> (32 - (bits))); \ | |
| 27 lo <<= (bits) | |
| 28 | |
| 29 ////////////////////////////////////////////////////////////////////// | |
| 30 | |
| 31 int Sk64::getClzAbs() const | |
| 32 { | |
| 33 int32_t hi = fHi; | |
| 34 uint32_t lo = fLo; | |
| 35 | |
| 36 // get abs | |
| 37 if (hi < 0) | |
| 38 { | |
| 39 hi = -hi - Sk32ToBool(lo); | |
| 40 lo = 0 - lo; | |
| 41 } | |
| 42 return hi ? SkCLZ(hi) : SkCLZ(lo) + 32; | |
| 43 } | |
| 44 | |
| 45 void Sk64::shiftLeft(unsigned bits) | |
| 46 { | |
| 47 SkASSERT(bits <= 63); | |
| 48 if (bits == 0) | |
| 49 return; | |
| 50 | |
| 51 if (bits >= 32) | |
| 52 { | |
| 53 fHi = fLo << (bits - 32); | |
| 54 fLo = 0; | |
| 55 } | |
| 56 else | |
| 57 { | |
| 58 fHi = (fHi << bits) | (fLo >> (32 - bits)); | |
| 59 fLo <<= bits; | |
| 60 } | |
| 61 } | |
| 62 | |
| 63 int32_t Sk64::getShiftRight(unsigned bits) const | |
| 64 { | |
| 65 SkASSERT(bits <= 63); | |
| 66 | |
| 67 if (bits == 0) | |
| 68 return fLo; | |
| 69 | |
| 70 if (bits >= 32) | |
| 71 return fHi >> (bits - 32); | |
| 72 else | |
| 73 { | |
| 74 #ifdef SK_DEBUG | |
| 75 int32_t tmp = fHi >> bits; | |
| 76 SkASSERT(tmp == 0 || tmp == -1); | |
| 77 #endif | |
| 78 return (fHi << (32 - bits)) | (fLo >> bits); | |
| 79 } | |
| 80 } | |
| 81 | |
| 82 void Sk64::shiftRight(unsigned bits) | |
| 83 { | |
| 84 SkASSERT(bits <= 63); | |
| 85 if (bits == 0) | |
| 86 return; | |
| 87 | |
| 88 if (bits >= 32) | |
| 89 { | |
| 90 fLo = fHi >> (bits - 32); | |
| 91 fHi >>= 31; | |
| 92 } | |
| 93 else | |
| 94 { | |
| 95 fLo = (fHi << (32 - bits)) | (fLo >> bits); | |
| 96 fHi >>= bits; | |
| 97 } | |
| 98 } | |
| 99 | |
| 100 void Sk64::roundRight(unsigned bits) | |
| 101 { | |
| 102 SkASSERT(bits <= 63); | |
| 103 if (bits) | |
| 104 { | |
| 105 Sk64 one; | |
| 106 one.set(1); | |
| 107 one.shiftLeft(bits - 1); | |
| 108 this->add(one); | |
| 109 this->shiftRight(bits); | |
| 110 } | |
| 111 } | |
| 112 | |
| 113 int Sk64::shiftToMake32() const | |
| 114 { | |
| 115 int32_t hi = fHi; | |
| 116 uint32_t lo = fLo; | |
| 117 | |
| 118 if (hi < 0) // make it positive | |
| 119 { | |
| 120 hi = -hi - Sk32ToBool(lo); | |
| 121 lo = 0 - lo; | |
| 122 } | |
| 123 | |
| 124 if (hi == 0) | |
| 125 return lo >> 31; | |
| 126 else | |
| 127 return 33 - SkCLZ(hi); | |
| 128 } | |
| 129 | |
| 130 void Sk64::negate() | |
| 131 { | |
| 132 fHi = -fHi - Sk32ToBool(fLo); | |
| 133 fLo = 0 - fLo; | |
| 134 } | |
| 135 | |
| 136 void Sk64::abs() | |
| 137 { | |
| 138 if (fHi < 0) | |
| 139 { | |
| 140 fHi = -fHi - Sk32ToBool(fLo); | |
| 141 fLo = 0 - fLo; | |
| 142 } | |
| 143 } | |
| 144 | |
| 145 //////////////////////////////////////////////////////////////// | |
| 146 | |
| 147 static inline int32_t round_right_16(int32_t hi, uint32_t lo) | |
| 148 { | |
| 149 uint32_t sum = lo + (1 << 15); | |
| 150 hi += (sum < lo); | |
| 151 return (hi << 16) | (sum >> 16); | |
| 152 } | |
| 153 | |
| 154 SkBool Sk64::isFixed() const | |
| 155 { | |
| 156 Sk64 tmp = *this; | |
| 157 tmp.roundRight(16); | |
| 158 return tmp.is32(); | |
| 159 } | |
| 160 | |
| 161 SkFract Sk64::getFract() const | |
| 162 { | |
| 163 Sk64 tmp = *this; | |
| 164 tmp.roundRight(30); | |
| 165 return tmp.get32(); | |
| 166 } | |
| 167 | |
| 168 void Sk64::sub(const Sk64& a) | |
| 169 { | |
| 170 fHi = fHi - a.fHi - (fLo < a.fLo); | |
| 171 fLo = fLo - a.fLo; | |
| 172 } | |
| 173 | |
| 174 void Sk64::rsub(const Sk64& a) | |
| 175 { | |
| 176 fHi = a.fHi - fHi - (a.fLo < fLo); | |
| 177 fLo = a.fLo - fLo; | |
| 178 } | |
| 179 | |
| 180 void Sk64::setMul(int32_t a, int32_t b) | |
| 181 { | |
| 182 int sa = a >> 31; | |
| 183 int sb = b >> 31; | |
| 184 // now make them positive | |
| 185 a = (a ^ sa) - sa; | |
| 186 b = (b ^ sb) - sb; | |
| 187 | |
| 188 uint32_t ah = a >> 16; | |
| 189 uint32_t al = a & 0xFFFF; | |
| 190 uint32_t bh = b >> 16; | |
| 191 uint32_t bl = b & 0xFFFF; | |
| 192 | |
| 193 uint32_t A = ah * bh; | |
| 194 uint32_t B = ah * bl + al * bh; | |
| 195 uint32_t C = al * bl; | |
| 196 | |
| 197 /* [ A ] | |
| 198 [ B ] | |
| 199 [ C ] | |
| 200 */ | |
| 201 fLo = C + (B << 16); | |
| 202 fHi = A + (B >>16) + (fLo < C); | |
| 203 | |
| 204 if (sa != sb) | |
| 205 this->negate(); | |
| 206 } | |
| 207 | |
| 208 void Sk64::div(int32_t denom, DivOptions option) | |
| 209 { | |
| 210 SkASSERT(denom); | |
| 211 | |
| 212 int32_t hi = fHi; | |
| 213 uint32_t lo = fLo; | |
| 214 int sign = denom ^ hi; | |
| 215 | |
| 216 denom = SkAbs32(denom); | |
| 217 if (hi < 0) | |
| 218 { | |
| 219 hi = -hi - Sk32ToBool(lo); | |
| 220 lo = 0 - lo; | |
| 221 } | |
| 222 | |
| 223 if (option == kRound_DivOption) // add denom/2 | |
| 224 { | |
| 225 uint32_t newLo = lo + (denom >> 1); | |
| 226 hi += (newLo < lo); | |
| 227 lo = newLo; | |
| 228 } | |
| 229 | |
| 230 if (hi == 0) // fast-case | |
| 231 { | |
| 232 if (lo < (uint32_t)denom) | |
| 233 this->set(0, 0); | |
| 234 else | |
| 235 { | |
| 236 this->set(0, lo / denom); | |
| 237 if (sign < 0) | |
| 238 this->negate(); | |
| 239 } | |
| 240 return; | |
| 241 } | |
| 242 | |
| 243 int bits; | |
| 244 | |
| 245 { | |
| 246 int dbits = SkCLZ(denom); | |
| 247 int nbits = SkCLZ(hi); | |
| 248 | |
| 249 bits = 32 + dbits - nbits; | |
| 250 SkASSERT(bits <= 63); | |
| 251 if (bits <= 0) | |
| 252 { | |
| 253 this->set(0, 0); | |
| 254 return; | |
| 255 } | |
| 256 denom <<= (dbits - 1); | |
| 257 shift_left_bits(hi, lo, nbits - 1); | |
| 258 } | |
| 259 | |
| 260 int32_t rhi = 0; | |
| 261 uint32_t rlo = 0; | |
| 262 | |
| 263 do { | |
| 264 shift_left(rhi, rlo); | |
| 265 #ifdef SK_CPU_HAS_CONDITIONAL_INSTR | |
| 266 if ((uint32_t)denom <= (uint32_t)hi) | |
| 267 { | |
| 268 hi -= denom; | |
| 269 rlo |= 1; | |
| 270 } | |
| 271 #else | |
| 272 int32_t diff = (denom - hi - 1) >> 31; | |
| 273 hi -= denom & diff; | |
| 274 rlo -= diff; | |
| 275 #endif | |
| 276 shift_left(hi, lo); | |
| 277 } while (--bits >= 0); | |
| 278 SkASSERT(rhi >= 0); | |
| 279 | |
| 280 fHi = rhi; | |
| 281 fLo = rlo; | |
| 282 if (sign < 0) | |
| 283 this->negate(); | |
| 284 } | |
| 285 | |
| 286 #define shift_left_2(a, b, c) \ | |
| 287 a = (a << 2) | (b >> 30); \ | |
| 288 b = (b << 2) | (c >> 30); \ | |
| 289 c <<= 2 | |
| 290 | |
| 291 int32_t Sk64::getSqrt() const | |
| 292 { | |
| 293 SkASSERT(!this->isNeg()); | |
| 294 | |
| 295 uint32_t hi = fHi; | |
| 296 uint32_t lo = fLo; | |
| 297 uint32_t sqr = 0; | |
| 298 uint32_t root = 0; | |
| 299 int count = 31; | |
| 300 | |
| 301 do { | |
| 302 root <<= 1; | |
| 303 shift_left_2(sqr, hi, lo); | |
| 304 | |
| 305 uint32_t testDiv = (root << 1) + 1; | |
| 306 if (sqr >= testDiv) | |
| 307 { | |
| 308 sqr -= testDiv; | |
| 309 root++; | |
| 310 } | |
| 311 } while (--count >= 0); | |
| 312 SkASSERT((int32_t)root >= 0); | |
| 313 | |
| 314 return root; | |
| 315 } | |
| 316 | |
| 317 #ifdef SkLONGLONG | |
| 318 SkLONGLONG Sk64::getLongLong() const | |
| 319 { | |
| 320 SkLONGLONG value = fHi; | |
| 321 value <<= 32; | |
| 322 return value | fLo; | |
| 323 } | |
| 324 #endif | |
| 325 | |
| 326 SkFixed Sk64::getFixedDiv(const Sk64& denom) const | |
| 327 { | |
| 328 Sk64 N = *this; | |
| 329 Sk64 D = denom; | |
| 330 int32_t sign = SkExtractSign(N.fHi ^ D.fHi); | |
| 331 SkFixed result; | |
| 332 | |
| 333 N.abs(); | |
| 334 D.abs(); | |
| 335 | |
| 336 // need to knock D down to just 31 bits | |
| 337 // either by rounding it to the right, or shifting N to the left | |
| 338 // then we can just call 64/32 div | |
| 339 | |
| 340 int nclz = N.fHi ? SkCLZ(N.fHi) : 32; | |
| 341 int dclz = D.fHi ? SkCLZ(D.fHi) : (33 - (D.fLo >> 31)); | |
| 342 | |
| 343 int shiftN = nclz - 1; | |
| 344 SkASSERT(shiftN >= 0); | |
| 345 int shiftD = 33 - dclz; | |
| 346 SkASSERT(shiftD >= 0); | |
| 347 | |
| 348 if (shiftD + shiftN < 16) | |
| 349 shiftD = 16 - shiftN; | |
| 350 else | |
| 351 shiftN = 16 - shiftD; | |
| 352 | |
| 353 D.roundRight(shiftD); | |
| 354 if (D.isZero()) | |
| 355 result = SK_MaxS32; | |
| 356 else | |
| 357 { | |
| 358 if (shiftN >= 0) | |
| 359 N.shiftLeft(shiftN); | |
| 360 else | |
| 361 N.roundRight(-shiftN); | |
| 362 N.div(D.get32(), Sk64::kTrunc_DivOption); | |
| 363 if (N.is32()) | |
| 364 result = N.get32(); | |
| 365 else | |
| 366 result = SK_MaxS32; | |
| 367 } | |
| 368 return SkApplySign(result, sign); | |
| 369 } | |
| 370 | |
| 371 /////////////////////////////////////////////////////////////////////// | |
| 372 | |
| 373 #ifdef SK_DEBUG | |
| 374 | |
| 375 #include "SkRandom.h" | |
| 376 #include <math.h> | |
| 377 | |
| 378 #ifdef SK_SUPPORT_UNITTEST | |
| 379 struct BoolTable { | |
| 380 int8_t zero, pos, neg, toBool, sign; | |
| 381 }; | |
| 382 | |
| 383 static void bool_table_test(const Sk64& a, const BoolTable& table) | |
| 384 { | |
| 385 SkASSERT(a.isZero() != a.nonZero()); | |
| 386 | |
| 387 SkASSERT(!a.isZero() == !table.zero); | |
| 388 SkASSERT(!a.isPos() == !table.pos); | |
| 389 SkASSERT(!a.isNeg() == !table.neg); | |
| 390 SkASSERT(a.sign() == table.sign); | |
| 391 } | |
| 392 | |
| 393 #ifdef SkLONGLONG | |
| 394 static SkLONGLONG asLL(const Sk64& a) | |
| 395 { | |
| 396 return ((SkLONGLONG)a.fHi << 32) | a.fLo; | |
| 397 } | |
| 398 #endif | |
| 399 #endif | |
| 400 | |
| 401 void Sk64::UnitTest() | |
| 402 { | |
| 403 #ifdef SK_SUPPORT_UNITTEST | |
| 404 enum BoolTests { | |
| 405 kZero_BoolTest, | |
| 406 kPos_BoolTest, | |
| 407 kNeg_BoolTest | |
| 408 }; | |
| 409 static const BoolTable gBoolTable[] = { | |
| 410 { 1, 0, 0, 0, 0 }, | |
| 411 { 0, 1, 0, 1, 1 }, | |
| 412 { 0, 0, 1, 1, -1 } | |
| 413 }; | |
| 414 | |
| 415 Sk64 a, b, c; | |
| 416 | |
| 417 a.fHi = a.fLo = 0; | |
| 418 b.set(0); | |
| 419 c.setZero(); | |
| 420 SkASSERT(a == b); | |
| 421 SkASSERT(a == c); | |
| 422 bool_table_test(a, gBoolTable[kZero_BoolTest]); | |
| 423 | |
| 424 a.fHi = 0; a.fLo = 5; | |
| 425 b.set(5); | |
| 426 SkASSERT(a == b); | |
| 427 SkASSERT(a.is32() && a.get32() == 5 && !a.is64()); | |
| 428 bool_table_test(a, gBoolTable[kPos_BoolTest]); | |
| 429 | |
| 430 a.fHi = -1; a.fLo = (uint32_t)-5; | |
| 431 b.set(-5); | |
| 432 SkASSERT(a == b); | |
| 433 SkASSERT(a.is32() && a.get32() == -5 && !a.is64()); | |
| 434 bool_table_test(a, gBoolTable[kNeg_BoolTest]); | |
| 435 | |
| 436 a.setZero(); | |
| 437 b.set(6); | |
| 438 c.set(-6); | |
| 439 SkASSERT(a != b && b != c && a != c); | |
| 440 SkASSERT(!(a == b) && !(a == b) && !(a == b)); | |
| 441 SkASSERT(a < b && b > a && a <= b && b >= a); | |
| 442 SkASSERT(c < a && a > c && c <= a && a >= c); | |
| 443 SkASSERT(c < b && b > c && c <= b && b >= c); | |
| 444 | |
| 445 // Now test add/sub | |
| 446 | |
| 447 SkRandom rand; | |
| 448 int i; | |
| 449 | |
| 450 for (i = 0; i < 1000; i++) | |
| 451 { | |
| 452 int aa = rand.nextS() >> 1; | |
| 453 int bb = rand.nextS() >> 1; | |
| 454 a.set(aa); | |
| 455 b.set(bb); | |
| 456 SkASSERT(a.get32() == aa && b.get32() == bb); | |
| 457 c = a; c.add(bb); | |
| 458 SkASSERT(c.get32() == aa + bb); | |
| 459 c = a; c.add(-bb); | |
| 460 SkASSERT(c.get32() == aa - bb); | |
| 461 c = a; c.add(b); | |
| 462 SkASSERT(c.get32() == aa + bb); | |
| 463 c = a; c.sub(b); | |
| 464 SkASSERT(c.get32() == aa - bb); | |
| 465 } | |
| 466 | |
| 467 #ifdef SkLONGLONG | |
| 468 for (i = 0; i < 1000; i++) | |
| 469 { | |
| 470 rand.next64(&a); //a.fHi >>= 1; // avoid overflow | |
| 471 rand.next64(&b); //b.fHi >>= 1; // avoid overflow | |
| 472 | |
| 473 if (!(i & 3)) // want to explicitly test these cases | |
| 474 { | |
| 475 a.fLo = 0; | |
| 476 b.fLo = 0; | |
| 477 } | |
| 478 else if (!(i & 7)) // want to explicitly test these cases | |
| 479 { | |
| 480 a.fHi = 0; | |
| 481 b.fHi = 0; | |
| 482 } | |
| 483 | |
| 484 SkLONGLONG aa = asLL(a); | |
| 485 SkLONGLONG bb = asLL(b); | |
| 486 | |
| 487 SkASSERT((a < b) == (aa < bb)); | |
| 488 SkASSERT((a <= b) == (aa <= bb)); | |
| 489 SkASSERT((a > b) == (aa > bb)); | |
| 490 SkASSERT((a >= b) == (aa >= bb)); | |
| 491 SkASSERT((a == b) == (aa == bb)); | |
| 492 SkASSERT((a != b) == (aa != bb)); | |
| 493 | |
| 494 c = a; c.add(b); | |
| 495 SkASSERT(asLL(c) == aa + bb); | |
| 496 c = a; c.sub(b); | |
| 497 SkASSERT(asLL(c) == aa - bb); | |
| 498 c = a; c.rsub(b); | |
| 499 SkASSERT(asLL(c) == bb - aa); | |
| 500 c = a; c.negate(); | |
| 501 SkASSERT(asLL(c) == -aa); | |
| 502 | |
| 503 int bits = rand.nextU() & 63; | |
| 504 c = a; c.shiftLeft(bits); | |
| 505 SkASSERT(asLL(c) == (aa << bits)); | |
| 506 c = a; c.shiftRight(bits); | |
| 507 SkASSERT(asLL(c) == (aa >> bits)); | |
| 508 c = a; c.roundRight(bits); | |
| 509 | |
| 510 SkLONGLONG tmp; | |
| 511 | |
| 512 tmp = aa; | |
| 513 if (bits > 0) | |
| 514 tmp += (SkLONGLONG)1 << (bits - 1); | |
| 515 SkASSERT(asLL(c) == (tmp >> bits)); | |
| 516 | |
| 517 c.setMul(a.fHi, b.fHi); | |
| 518 tmp = (SkLONGLONG)a.fHi * b.fHi; | |
| 519 SkASSERT(asLL(c) == tmp); | |
| 520 } | |
| 521 | |
| 522 | |
| 523 for (i = 0; i < 100000; i++) | |
| 524 { | |
| 525 Sk64 wide; | |
| 526 int32_t denom = rand.nextS(); | |
| 527 | |
| 528 while (denom == 0) | |
| 529 denom = rand.nextS(); | |
| 530 wide.setMul(rand.nextS(), rand.nextS()); | |
| 531 SkLONGLONG check = wide.getLongLong(); | |
| 532 | |
| 533 wide.div(denom, Sk64::kTrunc_DivOption); | |
| 534 check /= denom; | |
| 535 SkLONGLONG w = wide.getLongLong(); | |
| 536 | |
| 537 SkASSERT(check == w); | |
| 538 | |
| 539 #ifdef SK_CAN_USE_FLOATx | |
| 540 wide.setMul(rand.nextS(), rand.nextS()); | |
| 541 wide.abs(); | |
| 542 denom = wide.getSqrt(); | |
| 543 int32_t ck = (int32_t)sqrt((double)wide.getLongLong()); | |
| 544 int diff = denom - ck; | |
| 545 SkASSERT(SkAbs32(diff) <= 1); | |
| 546 | |
| 547 wide.setMul(rand.nextS(), rand.nextS()); | |
| 548 Sk64 dwide; | |
| 549 dwide.setMul(rand.nextS(), rand.nextS()); | |
| 550 SkFixed fixdiv = wide.getFixedDiv(dwide); | |
| 551 double dnumer = (double)wide.getLongLong(); | |
| 552 double ddenom = (double)dwide.getLongLong(); | |
| 553 double ddiv = dnumer / ddenom; | |
| 554 SkFixed dfixdiv; | |
| 555 if (ddiv >= (double)SK_MaxS32 / (double)SK_Fixed1) | |
| 556 dfixdiv = SK_MaxS32; | |
| 557 else if (ddiv <= -(double)SK_MaxS32 / (double)SK_Fixed1) | |
| 558 dfixdiv = SK_MinS32; | |
| 559 else | |
| 560 dfixdiv = SkFloatToFixed(dnumer / ddenom); | |
| 561 diff = fixdiv - dfixdiv; | |
| 562 | |
| 563 if (SkAbs32(diff) > 1) { | |
| 564 SkDebugf(" %d === numer %g denom %g div %g xdiv %x fxdiv %x\n", | |
| 565 i, dnumer, ddenom, ddiv, dfixdiv, fixdiv); | |
| 566 } | |
| 567 // SkASSERT(SkAbs32(diff) <= 1); | |
| 568 #endif | |
| 569 } | |
| 570 #endif | |
| 571 #endif | |
| 572 } | |
| 573 | |
| 574 #endif | |
| 575 | |
| 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/