libs/corecg/Sk64.cpp

/* libs/corecg/Sk64.cpp
**
** Copyright 2006, Google Inc.
**
** 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 SK_CAN_USE_LONGLONG
    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 {
    S8  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 SK_CAN_USE_LONGLONG
    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 SK_CAN_USE_LONGLONG
    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_FLOAT
        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;
        SkASSERT(SkAbs32(diff) <= 1);
#endif
    }
#endif
#endif
}

#endif