integer.cpp

这是linux下运行的mysql软件包,可用于linux 下安装 php + mysql + apach 的网络配置

            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 inline void Multiply2(word *C, const word *A, const word *B);
    static inline 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 inline unsigned int MultiplyRecursionLimit() {return 8;}

    static inline 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 inline 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 inline 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();
}

inline 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);

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


#undef MulAcc
#undef SaveMulAcc
#undef SquAcc
#undef SaveSquAcc

// optimized

#ifdef TAOCRYPT_X86ASM_AVAILABLE

// ************** x86 feature detection ***************

static bool s_sse2Enabled = true;

static void CpuId(word32 input, word32 *output)
{
#ifdef __GNUC__
    __asm__
    (
        // save ebx in case -fPIC is being used
        "push %%ebx; cpuid; mov %%ebx, %%edi; pop %%ebx"
        : "=a" (output[0]), "=D" (output[1]), "=c" (output[2]), "=d"(output[3])
        : "a" (input)
    );
#else
    __asm
    {
        mov eax, input
        cpuid
        mov edi, output
        mov [edi], eax
        mov [edi+4], ebx
        mov [edi+8], ecx
        mov [edi+12], edx
    }
#endif
}

#ifdef SSE2_INTRINSICS_AVAILABLE
#ifndef _MSC_VER
static jmp_buf s_env;
static void SigIllHandler(int)
{
    longjmp(s_env, 1);
}