/* 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);
}