integer.cpp

一个不错的关于手机模块程序This page contains everything that has changed in the history of DC++. Read this to fin

    return 0;
}

static word Increment(word *A, unsigned int N, word B=1)
{
    assert(N);
    word t = A[0];
    A[0] = t+B;
    if (A[0] >= t)
        return 0;
    for (unsigned i=1; i<N; i++)
        if (++A[i])
            return 0;
    return 1;
}

static word Decrement(word *A, unsigned int N, word B=1)
{
    assert(N);
    word t = A[0];
    A[0] = t-B;
    if (A[0] <= t)
        return 0;
    for (unsigned i=1; i<N; i++)
        if (A[i]--)
            return 0;
    return 1;
}

static void TwosComplement(word *A, unsigned int N)
{
    Decrement(A, N);
    for (unsigned i=0; i<N; i++)
        A[i] = ~A[i];
}


static word LinearMultiply(word *C, const word *A, word B, unsigned int N)
{
    word carry=0;
    for(unsigned i=0; i<N; i++)
    {
        DWord p = DWord::MultiplyAndAdd(A[i], B, carry);
        C[i] = p.GetLowHalf();
        carry = p.GetHighHalf();
    }
    return carry;
}


static word AtomicInverseModPower2(word A)
{
    assert(A%2==1);

    word R=A%8;

    for (unsigned i=3; i<WORD_BITS; i*=2)
        R = R*(2-R*A);

    assert(R*A==1);
    return R;
}


// ********************************************************

class Portable
{
public:
    static word Add(word *C, const word *A, const word *B, unsigned int N);
    static word Subtract(word *C, const word *A, const word*B, unsigned int N);

    static void Multiply2(word *C, const word *A, const word *B);
    static word Multiply2Add(word *C, const word *A, const word *B);
    static void Multiply4(word *C, const word *A, const word *B);
    static void Multiply8(word *C, const word *A, const word *B);
    static unsigned int MultiplyRecursionLimit() {return 8;}

    static void Multiply2Bottom(word *C, const word *A, const word *B);
    static void Multiply4Bottom(word *C, const word *A, const word *B);
    static void Multiply8Bottom(word *C, const word *A, const word *B);
    static unsigned int MultiplyBottomRecursionLimit() {return 8;}

    static void Square2(word *R, const word *A);
    static void Square4(word *R, const word *A);
    static void Square8(word *R, const word *A) {assert(false);}
    static unsigned int SquareRecursionLimit() {return 4;}
};

word Portable::Add(word *C, const word *A, const word *B, unsigned int N)
{
    assert (N%2 == 0);

    DWord u(0, 0);
    for (unsigned int i = 0; i < N; i+=2)
    {
        u = DWord(A[i]) + B[i] + u.GetHighHalf();
        C[i] = u.GetLowHalf();
        u = DWord(A[i+1]) + B[i+1] + u.GetHighHalf();
        C[i+1] = u.GetLowHalf();
    }
    return u.GetHighHalf();
}

word Portable::Subtract(word *C, const word *A, const word *B, unsigned int N)
{
    assert (N%2 == 0);

    DWord u(0, 0);
    for (unsigned int i = 0; i < N; i+=2)
    {
        u = (DWord) A[i] - B[i] - u.GetHighHalfAsBorrow();
        C[i] = u.GetLowHalf();
        u = (DWord) A[i+1] - B[i+1] - u.GetHighHalfAsBorrow();
        C[i+1] = u.GetLowHalf();
    }
    return 0-u.GetHighHalf();
}

void Portable::Multiply2(word *C, const word *A, const word *B)
{
/*
    word s;
    dword d;

    if (A1 >= A0)
        if (B0 >= B1)
        {
            s = 0;
            d = (dword)(A1-A0)*(B0-B1);
        }
        else
        {
            s = (A1-A0);
            d = (dword)s*(word)(B0-B1);
        }
    else
        if (B0 > B1)
        {
            s = (B0-B1);
            d = (word)(A1-A0)*(dword)s;
        }
        else
        {
            s = 0;
            d = (dword)(A0-A1)*(B1-B0);
        }
*/
    // this segment is the branchless equivalent of above
    word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
    unsigned int ai = A[1] < A[0];
    unsigned int bi = B[0] < B[1];
    unsigned int di = ai & bi;
    DWord d = DWord::Multiply(D[di], D[di+2]);
    D[1] = D[3] = 0;
    unsigned int si = ai + !bi;
    word s = D[si];

    DWord A0B0 = DWord::Multiply(A[0], B[0]);
    C[0] = A0B0.GetLowHalf();

    DWord A1B1 = DWord::Multiply(A[1], B[1]);
    DWord t = (DWord) A0B0.GetHighHalf() + A0B0.GetLowHalf() + d.GetLowHalf()
                       + A1B1.GetLowHalf();
    C[1] = t.GetLowHalf();

    t = A1B1 + t.GetHighHalf() + A0B0.GetHighHalf() + d.GetHighHalf()
             + A1B1.GetHighHalf() - s;
    C[2] = t.GetLowHalf();
    C[3] = t.GetHighHalf();
}

void Portable::Multiply2Bottom(word *C, const word *A, const word *B)
{
    DWord t = DWord::Multiply(A[0], B[0]);
    C[0] = t.GetLowHalf();
    C[1] = t.GetHighHalf() + A[0]*B[1] + A[1]*B[0];
}

word Portable::Multiply2Add(word *C, const word *A, const word *B)
{
    word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
    unsigned int ai = A[1] < A[0];
    unsigned int bi = B[0] < B[1];
    unsigned int di = ai & bi;
    DWord d = DWord::Multiply(D[di], D[di+2]);
    D[1] = D[3] = 0;
    unsigned int si = ai + !bi;
    word s = D[si];

    DWord A0B0 = DWord::Multiply(A[0], B[0]);
    DWord t = A0B0 + C[0];
    C[0] = t.GetLowHalf();

    DWord A1B1 = DWord::Multiply(A[1], B[1]);
    t = (DWord) t.GetHighHalf() + A0B0.GetLowHalf() + d.GetLowHalf() +
        A1B1.GetLowHalf() + C[1];
    C[1] = t.GetLowHalf();

    t = (DWord) t.GetHighHalf() + A1B1.GetLowHalf() + A0B0.GetHighHalf() +
        d.GetHighHalf() + A1B1.GetHighHalf() - s + C[2];
    C[2] = t.GetLowHalf();

    t = (DWord) t.GetHighHalf() + A1B1.GetHighHalf() + C[3];
    C[3] = t.GetLowHalf();
    return t.GetHighHalf();
}


#define MulAcc(x, y)                                \
    p = DWord::MultiplyAndAdd(A[x], B[y], c);       \
    c = p.GetLowHalf();                             \
    p = (DWord) d + p.GetHighHalf();                \
    d = p.GetLowHalf();                             \
    e += p.GetHighHalf();

#define SaveMulAcc(s, x, y)                         \
    R[s] = c;                                       \
    p = DWord::MultiplyAndAdd(A[x], B[y], d);       \
    c = p.GetLowHalf();                             \
    p = (DWord) e + p.GetHighHalf();                \
    d = p.GetLowHalf();                             \
    e = p.GetHighHalf();

#define SquAcc(x, y)                                \
    q = DWord::Multiply(A[x], A[y]);                \
    p = q + c;                                      \
    c = p.GetLowHalf();                             \
    p = (DWord) d + p.GetHighHalf();                \
    d = p.GetLowHalf();                             \
    e += p.GetHighHalf();                           \
    p = q + c;                                      \
    c = p.GetLowHalf();                             \
    p = (DWord) d + p.GetHighHalf();                \
    d = p.GetLowHalf();                             \
    e += p.GetHighHalf();

#define SaveSquAcc(s, x, y)                         \
    R[s] = c;                                       \
    q = DWord::Multiply(A[x], A[y]);                \
    p = q + d;                                      \
    c = p.GetLowHalf();                             \
    p = (DWord) e + p.GetHighHalf();                \
    d = p.GetLowHalf();                             \
    e = p.GetHighHalf();                            \
    p = q + c;                                      \
    c = p.GetLowHalf();                             \
    p = (DWord) d + p.GetHighHalf();                \
    d = p.GetLowHalf();                             \
    e += p.GetHighHalf();


void Portable::Multiply4(word *R, const word *A, const word *B)
{
    DWord p;
    word c, d, e;

    p = DWord::Multiply(A[0], B[0]);
    R[0] = p.GetLowHalf();
    c = p.GetHighHalf();
    d = e = 0;

    MulAcc(0, 1);
    MulAcc(1, 0);

    SaveMulAcc(1, 2, 0);
    MulAcc(1, 1);
    MulAcc(0, 2);

    SaveMulAcc(2, 0, 3);
    MulAcc(1, 2);
    MulAcc(2, 1);
    MulAcc(3, 0);

    SaveMulAcc(3, 3, 1);
    MulAcc(2, 2);
    MulAcc(1, 3);

    SaveMulAcc(4, 2, 3);
    MulAcc(3, 2);

    R[5] = c;
    p = DWord::MultiplyAndAdd(A[3], B[3], d);
    R[6] = p.GetLowHalf();
    R[7] = e + p.GetHighHalf();
}

void Portable::Square2(word *R, const word *A)
{
    DWord p, q;
    word c, d, e;

    p = DWord::Multiply(A[0], A[0]);
    R[0] = p.GetLowHalf();
    c = p.GetHighHalf();
    d = e = 0;

    SquAcc(0, 1);

    R[1] = c;
    p = DWord::MultiplyAndAdd(A[1], A[1], d);
    R[2] = p.GetLowHalf();
    R[3] = e + p.GetHighHalf();
}

void Portable::Square4(word *R, const word *A)
{
#ifdef _MSC_VER
    // VC60 workaround: MSVC 6.0 has an optimization bug that makes
    // (dword)A*B where either A or B has been cast to a dword before
    // very expensive. Revisit this function when this
    // bug is fixed.
    Multiply4(R, A, A);
#else
    const word *B = A;
    DWord p, q;
    word c, d, e;

    p = DWord::Multiply(A[0], A[0]);
    R[0] = p.GetLowHalf();
    c = p.GetHighHalf();
    d = e = 0;

    SquAcc(0, 1);

    SaveSquAcc(1, 2, 0);
    MulAcc(1, 1);

    SaveSquAcc(2, 0, 3);
    SquAcc(1, 2);

    SaveSquAcc(3, 3, 1);
    MulAcc(2, 2);

    SaveSquAcc(4, 2, 3);

    R[5] = c;
    p = DWord::MultiplyAndAdd(A[3], A[3], d);
    R[6] = p.GetLowHalf();
    R[7] = e + p.GetHighHalf();
#endif
}

void Portable::Multiply8(word *R, const word *A, const word *B)
{
    DWord p;
    word c, d, e;

    p = DWord::Multiply(A[0], B[0]);
    R[0] = p.GetLowHalf();
    c = p.GetHighHalf();
    d = e = 0;

    MulAcc(0, 1);
    MulAcc(1, 0);

    SaveMulAcc(1, 2, 0);
    MulAcc(1, 1);
    MulAcc(0, 2);

    SaveMulAcc(2, 0, 3);
    MulAcc(1, 2);
    MulAcc(2, 1);
    MulAcc(3, 0);

    SaveMulAcc(3, 0, 4);
    MulAcc(1, 3);
    MulAcc(2, 2);
    MulAcc(3, 1);
    MulAcc(4, 0);

    SaveMulAcc(4, 0, 5);
    MulAcc(1, 4);
    MulAcc(2, 3);
    MulAcc(3, 2);
    MulAcc(4, 1);
    MulAcc(5, 0);

    SaveMulAcc(5, 0, 6);
    MulAcc(1, 5);
    MulAcc(2, 4);
    MulAcc(3, 3);
    MulAcc(4, 2);
    MulAcc(5, 1);
    MulAcc(6, 0);

    SaveMulAcc(6, 0, 7);
    MulAcc(1, 6);
    MulAcc(2, 5);
    MulAcc(3, 4);
    MulAcc(4, 3);
    MulAcc(5, 2);
    MulAcc(6, 1);
    MulAcc(7, 0);

    SaveMulAcc(7, 1, 7);
    MulAcc(2, 6);
    MulAcc(3, 5);
    MulAcc(4, 4);
    MulAcc(5, 3);
    MulAcc(6, 2);
    MulAcc(7, 1);

    SaveMulAcc(8, 2, 7);
    MulAcc(3, 6);
    MulAcc(4, 5);
    MulAcc(5, 4);
    MulAcc(6, 3);
    MulAcc(7, 2);

    SaveMulAcc(9, 3, 7);
    MulAcc(4, 6);
    MulAcc(5, 5);
    MulAcc(6, 4);
    MulAcc(7, 3);

    SaveMulAcc(10, 4, 7);
    MulAcc(5, 6);
    MulAcc(6, 5);
    MulAcc(7, 4);

    SaveMulAcc(11, 5, 7);
    MulAcc(6, 6);
    MulAcc(7, 5);

    SaveMulAcc(12, 6, 7);
    MulAcc(7, 6);

    R[13] = c;
    p = DWord::MultiplyAndAdd(A[7], B[7], d);
    R[14] = p.GetLowHalf();
    R[15] = e + p.GetHighHalf();
}

void Portable::Multiply4Bottom(word *R, const word *A, const word *B)
{
    DWord p;
    word c, d, e;

    p = DWord::Multiply(A[0], B[0]);
    R[0] = p.GetLowHalf();
    c = p.GetHighHalf();
    d = e = 0;

    MulAcc(0, 1);
    MulAcc(1, 0);

    SaveMulAcc(1, 2, 0);
    MulAcc(1, 1);
    MulAcc(0, 2);

    R[2] = c;
    R[3] = d + A[0] * B[3] + A[1] * B[2] + A[2] * B[1] + A[3] * B[0];
}

void Portable::Multiply8Bottom(word *R, const word *A, const word *B)
{
    DWord p;
    word c, d, e;

    p = DWord::Multiply(A[0], B[0]);
    R[0] = p.GetLowHalf();
    c = p.GetHighHalf();
    d = e = 0;

    MulAcc(0, 1);
    MulAcc(1, 0);

    SaveMulAcc(1, 2, 0);
    MulAcc(1, 1);
    MulAcc(0, 2);

    SaveMulAcc(2, 0, 3);
    MulAcc(1, 2);
    MulAcc(2, 1);
    MulAcc(3, 0);

    SaveMulAcc(3, 0, 4);
    MulAcc(1, 3);
    MulAcc(2, 2);
    MulAcc(3, 1);
    MulAcc(4, 0);

    SaveMulAcc(4, 0, 5);
    MulAcc(1, 4);
    MulAcc(2, 3);
    MulAcc(3, 2);
    MulAcc(4, 1);
    MulAcc(5, 0);

    SaveMulAcc(5, 0, 6);
    MulAcc(1, 5);
    MulAcc(2, 4);
    MulAcc(3, 3);
    MulAcc(4, 2);
    MulAcc(5, 1);
    MulAcc(6, 0);