diff options
Diffstat (limited to 'src/core/Sk64.cpp')
| -rw-r--r-- | src/core/Sk64.cpp | 575 |
1 files changed, 575 insertions, 0 deletions
diff --git a/src/core/Sk64.cpp b/src/core/Sk64.cpp new file mode 100644 index 0000000000..6013bd7411 --- /dev/null +++ b/src/core/Sk64.cpp @@ -0,0 +1,575 @@ +/* libs/corecg/Sk64.cpp +** +** Copyright 2006, The Android Open Source Project +** +** Licensed under the Apache License, Version 2.0 (the "License"); +** you may not use this file except in compliance with the License. +** You may obtain a copy of the License at +** +** http://www.apache.org/licenses/LICENSE-2.0 +** +** Unless required by applicable law or agreed to in writing, software +** distributed under the License is distributed on an "AS IS" BASIS, +** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +** See the License for the specific language governing permissions and +** limitations under the License. +*/ + +#include "Sk64.h" + +#define shift_left(hi, lo) \ + hi = (hi << 1) | (lo >> 31); \ + lo <<= 1 + +#define shift_left_bits(hi, lo, bits) \ + SkASSERT((unsigned)(bits) < 31); \ + hi = (hi << (bits)) | (lo >> (32 - (bits))); \ + lo <<= (bits) + +////////////////////////////////////////////////////////////////////// + +int Sk64::getClzAbs() const +{ + int32_t hi = fHi; + uint32_t lo = fLo; + + // get abs + if (hi < 0) + { + hi = -hi - Sk32ToBool(lo); + lo = 0 - lo; + } + return hi ? SkCLZ(hi) : SkCLZ(lo) + 32; +} + +void Sk64::shiftLeft(unsigned bits) +{ + SkASSERT(bits <= 63); + if (bits == 0) + return; + + if (bits >= 32) + { + fHi = fLo << (bits - 32); + fLo = 0; + } + else + { + fHi = (fHi << bits) | (fLo >> (32 - bits)); + fLo <<= bits; + } +} + +int32_t Sk64::getShiftRight(unsigned bits) const +{ + SkASSERT(bits <= 63); + + if (bits == 0) + return fLo; + + if (bits >= 32) + return fHi >> (bits - 32); + else + { +#ifdef SK_DEBUG + int32_t tmp = fHi >> bits; + SkASSERT(tmp == 0 || tmp == -1); +#endif + return (fHi << (32 - bits)) | (fLo >> bits); + } +} + +void Sk64::shiftRight(unsigned bits) +{ + SkASSERT(bits <= 63); + if (bits == 0) + return; + + if (bits >= 32) + { + fLo = fHi >> (bits - 32); + fHi >>= 31; + } + else + { + fLo = (fHi << (32 - bits)) | (fLo >> bits); + fHi >>= bits; + } +} + +void Sk64::roundRight(unsigned bits) +{ + SkASSERT(bits <= 63); + if (bits) + { + Sk64 one; + one.set(1); + one.shiftLeft(bits - 1); + this->add(one); + this->shiftRight(bits); + } +} + +int Sk64::shiftToMake32() const +{ + int32_t hi = fHi; + uint32_t lo = fLo; + + if (hi < 0) // make it positive + { + hi = -hi - Sk32ToBool(lo); + lo = 0 - lo; + } + + if (hi == 0) + return lo >> 31; + else + return 33 - SkCLZ(hi); +} + +void Sk64::negate() +{ + fHi = -fHi - Sk32ToBool(fLo); + fLo = 0 - fLo; +} + +void Sk64::abs() +{ + if (fHi < 0) + { + fHi = -fHi - Sk32ToBool(fLo); + fLo = 0 - fLo; + } +} + +//////////////////////////////////////////////////////////////// + +static inline int32_t round_right_16(int32_t hi, uint32_t lo) +{ + uint32_t sum = lo + (1 << 15); + hi += (sum < lo); + return (hi << 16) | (sum >> 16); +} + +SkBool Sk64::isFixed() const +{ + Sk64 tmp = *this; + tmp.roundRight(16); + return tmp.is32(); +} + +SkFract Sk64::getFract() const +{ + Sk64 tmp = *this; + tmp.roundRight(30); + return tmp.get32(); +} + +void Sk64::sub(const Sk64& a) +{ + fHi = fHi - a.fHi - (fLo < a.fLo); + fLo = fLo - a.fLo; +} + +void Sk64::rsub(const Sk64& a) +{ + fHi = a.fHi - fHi - (a.fLo < fLo); + fLo = a.fLo - fLo; +} + +void Sk64::setMul(int32_t a, int32_t b) +{ + int sa = a >> 31; + int sb = b >> 31; + // now make them positive + a = (a ^ sa) - sa; + b = (b ^ sb) - sb; + + uint32_t ah = a >> 16; + uint32_t al = a & 0xFFFF; + uint32_t bh = b >> 16; + uint32_t bl = b & 0xFFFF; + + uint32_t A = ah * bh; + uint32_t B = ah * bl + al * bh; + uint32_t C = al * bl; + + /* [ A ] + [ B ] + [ C ] + */ + fLo = C + (B << 16); + fHi = A + (B >>16) + (fLo < C); + + if (sa != sb) + this->negate(); +} + +void Sk64::div(int32_t denom, DivOptions option) +{ + SkASSERT(denom); + + int32_t hi = fHi; + uint32_t lo = fLo; + int sign = denom ^ hi; + + denom = SkAbs32(denom); + if (hi < 0) + { + hi = -hi - Sk32ToBool(lo); + lo = 0 - lo; + } + + if (option == kRound_DivOption) // add denom/2 + { + uint32_t newLo = lo + (denom >> 1); + hi += (newLo < lo); + lo = newLo; + } + + if (hi == 0) // fast-case + { + if (lo < (uint32_t)denom) + this->set(0, 0); + else + { + this->set(0, lo / denom); + if (sign < 0) + this->negate(); + } + return; + } + + int bits; + + { + int dbits = SkCLZ(denom); + int nbits = SkCLZ(hi); + + bits = 32 + dbits - nbits; + SkASSERT(bits <= 63); + if (bits <= 0) + { + this->set(0, 0); + return; + } + denom <<= (dbits - 1); + shift_left_bits(hi, lo, nbits - 1); + } + + int32_t rhi = 0; + uint32_t rlo = 0; + + do { + shift_left(rhi, rlo); +#ifdef SK_CPU_HAS_CONDITIONAL_INSTR + if ((uint32_t)denom <= (uint32_t)hi) + { + hi -= denom; + rlo |= 1; + } +#else + int32_t diff = (denom - hi - 1) >> 31; + hi -= denom & diff; + rlo -= diff; +#endif + shift_left(hi, lo); + } while (--bits >= 0); + SkASSERT(rhi >= 0); + + fHi = rhi; + fLo = rlo; + if (sign < 0) + this->negate(); +} + +#define shift_left_2(a, b, c) \ + a = (a << 2) | (b >> 30); \ + b = (b << 2) | (c >> 30); \ + c <<= 2 + +int32_t Sk64::getSqrt() const +{ + SkASSERT(!this->isNeg()); + + uint32_t hi = fHi; + uint32_t lo = fLo; + uint32_t sqr = 0; + uint32_t root = 0; + int count = 31; + + do { + root <<= 1; + shift_left_2(sqr, hi, lo); + + uint32_t testDiv = (root << 1) + 1; + if (sqr >= testDiv) + { + sqr -= testDiv; + root++; + } + } while (--count >= 0); + SkASSERT((int32_t)root >= 0); + + return root; +} + +#ifdef SkLONGLONG + SkLONGLONG Sk64::getLongLong() const + { + SkLONGLONG value = fHi; + value <<= 32; + return value | fLo; + } +#endif + +SkFixed Sk64::getFixedDiv(const Sk64& denom) const +{ + Sk64 N = *this; + Sk64 D = denom; + int32_t sign = SkExtractSign(N.fHi ^ D.fHi); + SkFixed result; + + N.abs(); + D.abs(); + + // need to knock D down to just 31 bits + // either by rounding it to the right, or shifting N to the left + // then we can just call 64/32 div + + int nclz = N.fHi ? SkCLZ(N.fHi) : 32; + int dclz = D.fHi ? SkCLZ(D.fHi) : (33 - (D.fLo >> 31)); + + int shiftN = nclz - 1; + SkASSERT(shiftN >= 0); + int shiftD = 33 - dclz; + SkASSERT(shiftD >= 0); + + if (shiftD + shiftN < 16) + shiftD = 16 - shiftN; + else + shiftN = 16 - shiftD; + + D.roundRight(shiftD); + if (D.isZero()) + result = SK_MaxS32; + else + { + if (shiftN >= 0) + N.shiftLeft(shiftN); + else + N.roundRight(-shiftN); + N.div(D.get32(), Sk64::kTrunc_DivOption); + if (N.is32()) + result = N.get32(); + else + result = SK_MaxS32; + } + return SkApplySign(result, sign); +} + +/////////////////////////////////////////////////////////////////////// + +#ifdef SK_DEBUG + +#include "SkRandom.h" +#include <math.h> + +#ifdef SK_SUPPORT_UNITTEST +struct BoolTable { + int8_t zero, pos, neg, toBool, sign; +}; + +static void bool_table_test(const Sk64& a, const BoolTable& table) +{ + SkASSERT(a.isZero() != a.nonZero()); + + SkASSERT(!a.isZero() == !table.zero); + SkASSERT(!a.isPos() == !table.pos); + SkASSERT(!a.isNeg() == !table.neg); + SkASSERT(a.sign() == table.sign); +} + +#ifdef SkLONGLONG + static SkLONGLONG asLL(const Sk64& a) + { + return ((SkLONGLONG)a.fHi << 32) | a.fLo; + } +#endif +#endif + +void Sk64::UnitTest() +{ +#ifdef SK_SUPPORT_UNITTEST + enum BoolTests { + kZero_BoolTest, + kPos_BoolTest, + kNeg_BoolTest + }; + static const BoolTable gBoolTable[] = { + { 1, 0, 0, 0, 0 }, + { 0, 1, 0, 1, 1 }, + { 0, 0, 1, 1, -1 } + }; + + Sk64 a, b, c; + + a.fHi = a.fLo = 0; + b.set(0); + c.setZero(); + SkASSERT(a == b); + SkASSERT(a == c); + bool_table_test(a, gBoolTable[kZero_BoolTest]); + + a.fHi = 0; a.fLo = 5; + b.set(5); + SkASSERT(a == b); + SkASSERT(a.is32() && a.get32() == 5 && !a.is64()); + bool_table_test(a, gBoolTable[kPos_BoolTest]); + + a.fHi = -1; a.fLo = (uint32_t)-5; + b.set(-5); + SkASSERT(a == b); + SkASSERT(a.is32() && a.get32() == -5 && !a.is64()); + bool_table_test(a, gBoolTable[kNeg_BoolTest]); + + a.setZero(); + b.set(6); + c.set(-6); + SkASSERT(a != b && b != c && a != c); + SkASSERT(!(a == b) && !(a == b) && !(a == b)); + SkASSERT(a < b && b > a && a <= b && b >= a); + SkASSERT(c < a && a > c && c <= a && a >= c); + SkASSERT(c < b && b > c && c <= b && b >= c); + + // Now test add/sub + + SkRandom rand; + int i; + + for (i = 0; i < 1000; i++) + { + int aa = rand.nextS() >> 1; + int bb = rand.nextS() >> 1; + a.set(aa); + b.set(bb); + SkASSERT(a.get32() == aa && b.get32() == bb); + c = a; c.add(bb); + SkASSERT(c.get32() == aa + bb); + c = a; c.add(-bb); + SkASSERT(c.get32() == aa - bb); + c = a; c.add(b); + SkASSERT(c.get32() == aa + bb); + c = a; c.sub(b); + SkASSERT(c.get32() == aa - bb); + } + +#ifdef SkLONGLONG + for (i = 0; i < 1000; i++) + { + rand.next64(&a); //a.fHi >>= 1; // avoid overflow + rand.next64(&b); //b.fHi >>= 1; // avoid overflow + + if (!(i & 3)) // want to explicitly test these cases + { + a.fLo = 0; + b.fLo = 0; + } + else if (!(i & 7)) // want to explicitly test these cases + { + a.fHi = 0; + b.fHi = 0; + } + + SkLONGLONG aa = asLL(a); + SkLONGLONG bb = asLL(b); + + SkASSERT((a < b) == (aa < bb)); + SkASSERT((a <= b) == (aa <= bb)); + SkASSERT((a > b) == (aa > bb)); + SkASSERT((a >= b) == (aa >= bb)); + SkASSERT((a == b) == (aa == bb)); + SkASSERT((a != b) == (aa != bb)); + + c = a; c.add(b); + SkASSERT(asLL(c) == aa + bb); + c = a; c.sub(b); + SkASSERT(asLL(c) == aa - bb); + c = a; c.rsub(b); + SkASSERT(asLL(c) == bb - aa); + c = a; c.negate(); + SkASSERT(asLL(c) == -aa); + + int bits = rand.nextU() & 63; + c = a; c.shiftLeft(bits); + SkASSERT(asLL(c) == (aa << bits)); + c = a; c.shiftRight(bits); + SkASSERT(asLL(c) == (aa >> bits)); + c = a; c.roundRight(bits); + + SkLONGLONG tmp; + + tmp = aa; + if (bits > 0) + tmp += (SkLONGLONG)1 << (bits - 1); + SkASSERT(asLL(c) == (tmp >> bits)); + + c.setMul(a.fHi, b.fHi); + tmp = (SkLONGLONG)a.fHi * b.fHi; + SkASSERT(asLL(c) == tmp); + } + + + for (i = 0; i < 100000; i++) + { + Sk64 wide; + int32_t denom = rand.nextS(); + + while (denom == 0) + denom = rand.nextS(); + wide.setMul(rand.nextS(), rand.nextS()); + SkLONGLONG check = wide.getLongLong(); + + wide.div(denom, Sk64::kTrunc_DivOption); + check /= denom; + SkLONGLONG w = wide.getLongLong(); + + SkASSERT(check == w); + +#ifdef SK_CAN_USE_FLOATx + wide.setMul(rand.nextS(), rand.nextS()); + wide.abs(); + denom = wide.getSqrt(); + int32_t ck = (int32_t)sqrt((double)wide.getLongLong()); + int diff = denom - ck; + SkASSERT(SkAbs32(diff) <= 1); + + wide.setMul(rand.nextS(), rand.nextS()); + Sk64 dwide; + dwide.setMul(rand.nextS(), rand.nextS()); + SkFixed fixdiv = wide.getFixedDiv(dwide); + double dnumer = (double)wide.getLongLong(); + double ddenom = (double)dwide.getLongLong(); + double ddiv = dnumer / ddenom; + SkFixed dfixdiv; + if (ddiv >= (double)SK_MaxS32 / (double)SK_Fixed1) + dfixdiv = SK_MaxS32; + else if (ddiv <= -(double)SK_MaxS32 / (double)SK_Fixed1) + dfixdiv = SK_MinS32; + else + dfixdiv = SkFloatToFixed(dnumer / ddenom); + diff = fixdiv - dfixdiv; + + if (SkAbs32(diff) > 1) { + SkDebugf(" %d === numer %g denom %g div %g xdiv %x fxdiv %x\n", + i, dnumer, ddenom, ddiv, dfixdiv, fixdiv); + } +// SkASSERT(SkAbs32(diff) <= 1); +#endif + } +#endif +#endif +} + +#endif + |