integer.cpp

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

/* integer.cpp                                
 *
 * Copyright (C) 2003 Sawtooth Consulting Ltd.
 *
 * This file is part of yaSSL.
 *
 * yaSSL is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * yaSSL is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 */



/* based on Wei Dai's integer.cpp from CryptoPP */

#include "runtime.hpp"
#include "integer.hpp"
#include "modarith.hpp"
#include "asn.hpp"



#ifdef __DECCXX
    #include <c_asm.h>  // for asm overflow assembly
#endif


// 64bit multiply overflow intrinsic
#if defined(_MSC_VER) && defined(_WIN64) && !defined(__INTEL_COMPILER) && \
   !defined(TAOCRYPT_NATIVE_DWORD_AVAILABLE)
    #ifdef __ia64__
        #define myUMULH __UMULH
    #elif  __x86_64__
        #define myUMULH __umulh
    #else
        #error unknown 64bit windows
    #endif

extern "C" word myUMULH(word, word); 

#pragma intrinsic (myUMULH)
#endif


#ifdef SSE2_INTRINSICS_AVAILABLE
    #ifdef __GNUC__
        #include <xmmintrin.h>
        #include <signal.h>
        #include <setjmp.h>
        #ifdef TAOCRYPT_MEMALIGN_AVAILABLE
            #include <malloc.h>
        #else
            #include <stdlib.h>
        #endif
    #else
        #include <emmintrin.h>
    #endif
#elif defined(_MSC_VER) && defined(_M_IX86)
    #pragma message("You do not seem to have the Visual C++ Processor Pack ")
    #pragma message("installed, so use of SSE2 intrinsics will be disabled.")
#elif defined(__GNUC__) && defined(__i386__)
/*   #warning You do not have GCC 3.3 or later, or did not specify the -msse2 \
             compiler option. Use of SSE2 intrinsics will be disabled.
*/
#endif


namespace TaoCrypt {


#ifdef SSE2_INTRINSICS_AVAILABLE

template <class T>
CPP_TYPENAME AllocatorBase<T>::pointer AlignedAllocator<T>::allocate(
                                           size_type n, const void *)
{
    CheckSize(n);
    if (n == 0)
        return 0;
    if (n >= 4)
    {
        void* p;
    #ifdef TAOCRYPT_MM_MALLOC_AVAILABLE
        p = _mm_malloc(sizeof(T)*n, 16);
    #elif defined(TAOCRYPT_MEMALIGN_AVAILABLE)
        p = memalign(16, sizeof(T)*n);
    #elif defined(TAOCRYPT_MALLOC_ALIGNMENT_IS_16)
        p = malloc(sizeof(T)*n);
    #else
        p = (byte *)malloc(sizeof(T)*n + 8);
        // assume malloc alignment is at least 8
    #endif

    #ifdef TAOCRYPT_NO_ALIGNED_ALLOC
        assert(m_pBlock == 0);
        m_pBlock = p;
        if (!IsAlignedOn(p, 16))
        {
            assert(IsAlignedOn(p, 8));
            p = (byte *)p + 8;
        }
    #endif

        assert(IsAlignedOn(p, 16));
        return (T*)p;
    }
    return NEW_TC T[n];
}


template <class T>
void AlignedAllocator<T>::deallocate(void* p, size_type n)
{
    memset(p, 0, n*sizeof(T));
    if (n >= 4)
    {
        #ifdef TAOCRYPT_MM_MALLOC_AVAILABLE
            _mm_free(p);
        #elif defined(TAOCRYPT_NO_ALIGNED_ALLOC)
            assert(m_pBlock == p || (byte*)m_pBlock+8 == p);
            free(m_pBlock);
            m_pBlock = 0;
        #else
            free(p);
        #endif
    }
    else
        tcArrayDelete((T *)p);
}

#endif  // SSE2


// ********  start of integer needs

// start 5.2.1 adds DWord and Word ********

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

class DWord {
public:
DWord() {}

#ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
    explicit DWord(word low)
    {
        whole_ = low;
    }
#else
    explicit DWord(word low)
    {
        halfs_.low = low;
        halfs_.high = 0;
    }
#endif

    DWord(word low, word high)
    {
        halfs_.low = low;
        halfs_.high = high;
    }

    static DWord Multiply(word a, word b)
    {
        DWord r;

        #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
            r.whole_ = (dword)a * b;

        #elif defined(_MSC_VER)
            r.halfs_.low = a*b;
            r.halfs_.high = myUMULH(a,b);

        #elif defined(__alpha__)
            r.halfs_.low = a*b;
            #ifdef __GNUC__
                __asm__("umulh %1,%2,%0" : "=r" (r.halfs_.high)
                    : "r" (a), "r" (b));
            #elif defined(__DECCXX)
                r.halfs_.high = asm("umulh %a0, %a1, %v0", a, b);
            #else
                #error unknown alpha compiler
            #endif

        #elif defined(__ia64__)
            r.halfs_.low = a*b;
            __asm__("xmpy.hu %0=%1,%2" : "=f" (r.halfs_.high)
                : "f" (a), "f" (b));

        #elif defined(_ARCH_PPC64)
            r.halfs_.low = a*b;
            __asm__("mulhdu %0,%1,%2" : "=r" (r.halfs_.high)
                : "r" (a), "r" (b) : "cc");

        #elif defined(__x86_64__)
            __asm__("mulq %3" : "=d" (r.halfs_.high), "=a" (r.halfs_.low) :
                "a" (a), "rm" (b) : "cc");

        #elif defined(__mips64)
            __asm__("dmultu %2,%3" : "=h" (r.halfs_.high), "=l" (r.halfs_.low)
                : "r" (a), "r" (b));

        #elif defined(_M_IX86)
            // for testing
            word64 t = (word64)a * b;
            r.halfs_.high = ((word32 *)(&t))[1];
            r.halfs_.low = (word32)t;
        #else
            #error can not implement DWord
        #endif

        return r;
    }

    static DWord MultiplyAndAdd(word a, word b, word c)
    {
        DWord r = Multiply(a, b);
        return r += c;
    }

    DWord & operator+=(word a)
    {
        #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
            whole_ = whole_ + a;
        #else
            halfs_.low += a;
            halfs_.high += (halfs_.low < a);
        #endif
        return *this;
    }

    DWord operator+(word a)
    {
        DWord r;
        #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
            r.whole_ = whole_ + a;
        #else
            r.halfs_.low = halfs_.low + a;
            r.halfs_.high = halfs_.high + (r.halfs_.low < a);
        #endif
        return r;
    }

    DWord operator-(DWord a)
    {
        DWord r;
        #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
            r.whole_ = whole_ - a.whole_;
        #else
            r.halfs_.low = halfs_.low - a.halfs_.low;
            r.halfs_.high = halfs_.high - a.halfs_.high -
                             (r.halfs_.low > halfs_.low);
        #endif
        return r;
    }

    DWord operator-(word a)
    {
        DWord r;
        #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
            r.whole_ = whole_ - a;
        #else
            r.halfs_.low = halfs_.low - a;
            r.halfs_.high = halfs_.high - (r.halfs_.low > halfs_.low);
        #endif
        return r;
    }

    // returns quotient, which must fit in a word
    word operator/(word divisor);

    word operator%(word a);

    bool operator!() const
    {
    #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
        return !whole_;
    #else
        return !halfs_.high && !halfs_.low;
    #endif
    }

    word GetLowHalf() const {return halfs_.low;}
    word GetHighHalf() const {return halfs_.high;}
    word GetHighHalfAsBorrow() const {return 0-halfs_.high;}

private:
    union
    {
    #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
        dword whole_;
    #endif
        struct
        {
        #ifdef LITTLE_ENDIAN_ORDER
            word low;
            word high;
        #else
            word high;
            word low;
        #endif
        } halfs_;
    };
};


class Word {
public:
    Word() {}

    Word(word value)
    {
        whole_ = value;
    }

    Word(hword low, hword high)
    {
        whole_ = low | (word(high) << (WORD_BITS/2));
    }

    static Word Multiply(hword a, hword b)
    {
        Word r;
        r.whole_ = (word)a * b;
        return r;
    }

    Word operator-(Word a)
    {
        Word r;
        r.whole_ = whole_ - a.whole_;
        return r;
    }

    Word operator-(hword a)
    {
        Word r;
        r.whole_ = whole_ - a;
        return r;
    }

    // returns quotient, which must fit in a word
    hword operator/(hword divisor)
    {
        return hword(whole_ / divisor);
    }

    bool operator!() const
    {
        return !whole_;
    }

    word GetWhole() const {return whole_;}
    hword GetLowHalf() const {return hword(whole_);}
    hword GetHighHalf() const {return hword(whole_>>(WORD_BITS/2));}
    hword GetHighHalfAsBorrow() const {return 0-hword(whole_>>(WORD_BITS/2));}

private:
    word whole_;
};


// dummy is VC60 compiler bug workaround
// do a 3 word by 2 word divide, returns quotient and leaves remainder in A
template <class S, class D>
S DivideThreeWordsByTwo(S* A, S B0, S B1, D* dummy_VC6_WorkAround = 0)
{
    // assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a S
    assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));

    // estimate the quotient: do a 2 S by 1 S divide
    S Q;
    if (S(B1+1) == 0)
        Q = A[2];
    else
        Q = D(A[1], A[2]) / S(B1+1);

    // now subtract Q*B from A
    D p = D::Multiply(B0, Q);
    D u = (D) A[0] - p.GetLowHalf();
    A[0] = u.GetLowHalf();
    u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - 
            D::Multiply(B1, Q);
    A[1] = u.GetLowHalf();
    A[2] += u.GetHighHalf();

    // Q <= actual quotient, so fix it
    while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
    {
        u = (D) A[0] - B0;
        A[0] = u.GetLowHalf();
        u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
        A[1] = u.GetLowHalf();
        A[2] += u.GetHighHalf();
        Q++;
        assert(Q);	// shouldn't overflow
    }

    return Q;
}


// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1
template <class S, class D>
inline D DivideFourWordsByTwo(S *T, const D &Al, const D &Ah, const D &B)
{
    if (!B) // if divisor is 0, we assume divisor==2**(2*WORD_BITS)
        return D(Ah.GetLowHalf(), Ah.GetHighHalf());
    else
    {
        S Q[2];
        T[0] = Al.GetLowHalf();
        T[1] = Al.GetHighHalf(); 
        T[2] = Ah.GetLowHalf();
        T[3] = Ah.GetHighHalf();
        Q[1] = DivideThreeWordsByTwo<S, D>(T+1, B.GetLowHalf(),
                                                B.GetHighHalf());
        Q[0] = DivideThreeWordsByTwo<S, D>(T, B.GetLowHalf(), B.GetHighHalf());
        return D(Q[0], Q[1]);
    }
}


// returns quotient, which must fit in a word
inline word DWord::operator/(word a)
{
    #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
        return word(whole_ / a);
    #else
        hword r[4];
        return DivideFourWordsByTwo<hword, Word>(r, halfs_.low,
                                                    halfs_.high, a).GetWhole();
    #endif
}

inline word DWord::operator%(word a)
{
    #ifdef TAOCRYPT_NATIVE_DWORD_AVAILABLE
        return word(whole_ % a);
    #else
        if (a < (word(1) << (WORD_BITS/2)))
        {
            hword h = hword(a);
            word r = halfs_.high % h;
            r = ((halfs_.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h;
            return hword((hword(halfs_.low) + (r << (WORD_BITS/2))) % h);
        }
        else
        {
            hword r[4];
            DivideFourWordsByTwo<hword, Word>(r, halfs_.low, halfs_.high, a);
            return Word(r[0], r[1]).GetWhole();
        }
    #endif
}



// end 5.2.1 DWord and Word adds





static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};

static inline unsigned int RoundupSize(unsigned int n)
{
    if (n<=8)
        return RoundupSizeTable[n];
    else if (n<=16)
        return 16;
    else if (n<=32)
        return 32;
    else if (n<=64)
        return 64;
    else return 1U << BitPrecision(n-1);
}


static int Compare(const word *A, const word *B, unsigned int N)
{
    while (N--)
        if (A[N] > B[N])
            return 1;
        else if (A[N] < B[N])
            return -1;