cBigUnsigned.h

Go to the documentation of this file.

//
//
#ifndef _INC_cBigUnsigned_H
#define _INC_cBigUnsigned_H
#ifndef NO_PRAGMA_ONCE
#pragma once
#endif
 
#include "cBitArray.h"
#include "GrayCore/include/cString.h"
#include "GrayCore/include/cException.h"
#include "GrayCore/include/cThreadLock.h"
#include "GrayCore/include/HResult.h"
 
namespace GrayLib
{
        UNITTEST2_PREDEF(cBigUnsigned);
 
        class GRAYLIB_LINK cBigUnsigned : public cBitArray
        {
 
                typedef cBitArray SUPER_t;
                typedef cBigUnsigned THIS_t;
 
        public:
                cBigUnsigned()
                {
                }
                cBigUnsigned(const cBigUnsigned& x)
                        : SUPER_t(x)
                {
                }
 
                cBigUnsigned(BIT_ENUM_t nBits, BLOCK_t uValMask) // Creates a cBigUnsigned with a capacity; for internal use.
                        : SUPER_t(nBits, uValMask)
                {}
 
                cBigUnsigned(BLOCK_ENUM_t nBlocks, const BLOCK_t* pBlocks)
                        : SUPER_t(nBlocks, pBlocks)
                {
                }
                cBigUnsigned(BLOCK_ENUM_t nBlocks, const BLOCK_t* pBlocks, bool bStatic)
                        : SUPER_t(nBlocks, pBlocks, bStatic)
                {
                        ASSERT(bStatic);
                }
 
                explicit cBigUnsigned(const char* pszStr, RADIX_t nBaseRadix = 10)
                {
                        SetStr(pszStr, nBaseRadix);
                }
 
                ~cBigUnsigned()
                {
                }
 
                // Constructors from primitive integer types. "cTypes.tbl"
                cBigUnsigned(UINTMAX_t x) { put_ValU(x); }
                cBigUnsigned(INTMAX_t x) { put_ValS(x); }
#if 1 // Stupid C++ compiler wont pick the correct one.
                cBigUnsigned(UINT32 x) { put_ValU(x); }
                cBigUnsigned(INT32 x) { put_ValS(x); }
#endif
 
                void SetBlockSizeInit(BLOCK_ENUM_t nBlocks, const BLOCK_t* pBlocks);
 
                bool isZero() const
                {
                        return get_BlocksUse() == 0;
                }
                bool isOdd() const
                {
                        if (isZero())   // 0 is not odd.
                                return false;
                        return(GetBlockInt(0) & 1);
                }
 
                template <typename TYPE /*= BLOCK_t*/ >
                TYPE get_ValU() const
                {
                        size_t nSizeAvail = get_BlocksCap() * sizeof(BLOCK_t);
                        if (nSizeAvail <= 0)
                        {
                                return 0;
                        }
                        if (nSizeAvail < sizeof(TYPE))
                        {
                                TYPE uVal = 0;
                                ::memcpy(&uVal, get_BlockPtrC(), nSizeAvail);
                                return uVal;
                        }
                        // Its big enough. just cast it and return.
                        return(*((const TYPE*)get_BlockPtrC()));
                }
 
                template <typename TYPE /*= BLOCK_t*/>
                TYPE get_ValUC() const
                {
                        BIT_ENUM_t nBits = get_Highest1Bit();
                        size_t nBytes = cBits::GetSizeBytes(nBits);
                        if (sizeof(TYPE) < nBytes)
                        {
                                ReturnError(DISP_E_OVERFLOW, "cBigUnsigned::get_ValS: Value is too big to fit in the requested type");
                                return 0;
                        }
                        return get_ValU<TYPE>();
                }
                template <typename TYPE /*= BLOCK_t*/>
                TYPE get_ValS() const
                {
                        TYPE uVal = get_ValUC<TYPE>();
                        if (uVal < 0)   // Not enough room to hold the sign.
                        {
                                ReturnError(DISP_E_OVERFLOW, "cBigUnsigned::get_ValS: Value is too big to fit in the requested signed type");
                                return 0;
                        }
                        return uVal;
                }
                template <typename TYPE /*= BLOCK_t*/>
                TYPE get_Val() const
                {
                        return get_ValUC<TYPE>();
                }
 
                COMPARE_t CompareU(BLOCK_t x) const;
                bool operator == (BLOCK_t x) const { return CompareU(x) == COMPARE_Equal; }
                bool operator != (BLOCK_t x) const { return CompareU(x) != COMPARE_Equal; }
                bool operator < (BLOCK_t x) const { return CompareU(x) < 0; }
                bool operator <= (BLOCK_t x) const { return CompareU(x) <= COMPARE_Equal; }
                bool operator >= (BLOCK_t x) const { return CompareU(x) >= COMPARE_Equal; }
                bool operator > (BLOCK_t x) const { return CompareU(x) > 0; }
 
                COMPARE_t Compare(const cBigUnsigned& x) const;
                bool operator == (const cBigUnsigned& x) const { return IsEqual(x); }
                bool operator != (const cBigUnsigned& x) const { return !IsEqual(x); }
                bool operator < (const cBigUnsigned& x) const { return Compare(x) < 0; }
                bool operator <= (const cBigUnsigned& x) const { return Compare(x) <= COMPARE_Equal; }
                bool operator >= (const cBigUnsigned& x) const { return Compare(x) >= COMPARE_Equal; }
                bool operator > (const cBigUnsigned& x) const { return Compare(x) > 0; }
 
                StrLen_t GetStr(char* pszOut, StrLen_t iOutMax, RADIX_t nBaseRadix = 10) const;
                cString GetStr(RADIX_t nBaseRadix = 10) const;
                bool SetStr(const char* pszVal, RADIX_t nBaseRadix = 10, const char** ppszEnd = (const char**) nullptr);
 
                //*************************************************
                // Modifiers.
 
                void put_ValU(UINTMAX_t n);
                HRESULT put_ValS(INTMAX_t n);
 
                template <typename TYPE>
                void put_Val(TYPE n)
                {
                        return put_ValU(n);
                }
 
                void InitBitAnd(const cBigUnsigned& a, const cBigUnsigned& b);
                void InitBitOr(const cBigUnsigned& a, const cBigUnsigned& b);
                void InitBitXor(const cBigUnsigned& a, const cBigUnsigned& b);
 
                HRESULT InitBitShiftLeft(const cBigUnsigned& a, int b);
                HRESULT InitBitShiftRight(const cBigUnsigned& a, int b);
 
                void OpBitShiftLeft1(BLOCK_t nBitMask = 0);
                HRESULT OpBitShiftLeft(BIT_ENUM_t b)
                {
                        return InitBitShiftLeft(*this, b);
                }
                HRESULT OpBitShiftRight(BIT_ENUM_t b)
                {
                        return InitBitShiftRight(*this, b);
                }
 
                // Arguments are read-only operands, result is saved in *this.
                void OpAdd1(BLOCK_t nVal);
                HRESULT OpSubtract1(BLOCK_t nVal);
                void InitSubtract1(const THIS_t& a, BLOCK_t n)
                {
                        if (this != &a)
                                SetCopyBits(a);
                        OpSubtract1(n);
                }
 
                void InitAdd(const cBigUnsigned& a, const cBigUnsigned& b);
                HRESULT InitSubtract(const cBigUnsigned& a, const cBigUnsigned& b);
                HRESULT OpSubtract(const THIS_t& b)
                {
                        return InitSubtract(*this, b);
                }
 
                static void MultiplyHelper(BLOCK_t* pDst, BLOCK_ENUM_t nBlocks, const cBigUnsigned& rSrc, BLOCK_t nMult);
                void InitMultiply1(const cBigUnsigned& a, BLOCK_t b);
                void InitMultiplyH(const cBigUnsigned& a, BLOCKH_t b);
                void InitMultiply(const cBigUnsigned& a, const cBigUnsigned& b);
 
                BLOCK_t GetModulusH(BLOCKH_t b) const;
                BLOCKH_t InitDivideH(const cBigUnsigned& a, BLOCKH_t b);
                HRESULT InitDivide(const cBigUnsigned& a, const cBigUnsigned& b, OUT cBigUnsigned& remainder);
                HRESULT InitDivide(const THIS_t& a, const THIS_t& b)
                {
                        cBigUnsigned rJunkRemainder;
                        return InitDivide(a, b, rJunkRemainder);
                }
                HRESULT InitModulus(const THIS_t& a, const THIS_t& b)
                {
                        cBigUnsigned rJunkQuotient;
                        return rJunkQuotient.InitDivide(a, b, *this);
                }
 
                static void GRAYCALL EuclideanAlgorithm(const cBigUnsigned& x, const cBigUnsigned& y, OUT cBigUnsigned& a, OUT cBigUnsigned& b, OUT cBigUnsigned& g);
                static cBigUnsigned GRAYCALL GetGreatestCommonDivisor(const cBigUnsigned& x, const cBigUnsigned& y);
                HRESULT InitModInv(const cBigUnsigned& A, const cBigUnsigned& N);
 
                HRESULT SetRandomBits2(BIT_ENUM_t nBits, IRandomNoise* pRandom = nullptr);
                HRESULT SetRandomBits(BIT_ENUM_t nBits, IRandomNoise* pRandom = nullptr);
 
                BLOCK_t get_MontgomeryInit() const;
                void SetMontMul(THIS_t& rDst, const THIS_t& B, const THIS_t& N, BLOCK_t mm);
                void SetMontRedux(THIS_t& rDst, const THIS_t& N, BLOCK_t mm);
 
                void SetPower(const THIS_t& base, const THIS_t& exponent);
                HRESULT SetPowerMod(const THIS_t& base, const THIS_t& exponent, const THIS_t& modulus, OUT THIS_t* pRR = nullptr);
 
                BITOP_TYPE TestPrimeSmall() const;
                HRESULT TestPrimeMiller(IRandomNoise* pRandom = nullptr) const;
                HRESULT TestPrimeFermat(IRandomNoise* pRandom = nullptr) const;
                HRESULT TestPrime(IRandomNoise* pRandom = nullptr) const;
 
                HRESULT SetPrimePrev(IRandomNoise* pRandom = nullptr, cThreadState* pCancel = nullptr);
                HRESULT SetPrimeBits(BIT_ENUM_t nBits, IRandomNoise* pRandom = nullptr, cThreadState* pCancel = nullptr);
                HRESULT SetPrimeBitsDH(BIT_ENUM_t nbits, IRandomNoise* pRandom = nullptr, cThreadState* pCancel = nullptr);
 
                cBigUnsigned operator +(const THIS_t& x) const
                {
                        cBigUnsigned ans;
                        ans.InitAdd(*this, x);
                        return ans;
                }
                cBigUnsigned operator +(BLOCK_t x) const
                {
                        cBigUnsigned ans(*this);
                        ans.OpAdd1(x);
                        return ans;
                }
                cBigUnsigned operator -(const THIS_t& x) const
                {
                        cBigUnsigned ans;
                        ans.InitSubtract(*this, x);
                        return ans;
                }
                cBigUnsigned operator -(BLOCK_t x) const
                {
                        cBigUnsigned ans(*this);
                        ans.OpSubtract1(x);
                        return ans;
                }
                cBigUnsigned operator *(const THIS_t& x) const
                {
                        cBigUnsigned ans;
                        ans.InitMultiply(*this, x);
                        return ans;
                }
                cBigUnsigned operator *(BLOCKH_t x) const
                {
                        cBigUnsigned ans;
                        ans.InitMultiplyH(*this, x);
                        return ans;
                }
                cBigUnsigned operator /(const THIS_t& x) const
                {
                        cBigUnsigned q;
                        q.InitDivide(*this, x);
                        return q;
                }
                cBigUnsigned operator /(BLOCKH_t n) const
                {
                        cBigUnsigned q;
                        (void)q.InitDivideH(*this, n);
                        return q;
                }
                cBigUnsigned operator %(const THIS_t& x) const
                {
                        cBigUnsigned r;
                        r.InitModulus(*this, x);
                        return r;
                }
                BLOCKH_t operator %(BLOCKH_t n) const
                {
                        cBigUnsigned qJunk;     // junk this.
                        return qJunk.InitDivideH(*this, n);
                }
 
                // NOTE: NO unary minus allowed
                cBigUnsigned operator &(const THIS_t& x) const
                {
                        cBigUnsigned ans;
                        ans.InitBitAnd(*this, x);
                        return ans;
                }
                cBigUnsigned operator |(const THIS_t& x) const
                {
                        cBigUnsigned ans;
                        ans.InitBitOr(*this, x);
                        return ans;
                }
                cBigUnsigned operator ^(const THIS_t& x) const
                {
                        cBigUnsigned ans;
                        ans.InitBitXor(*this, x);
                        return ans;
                }
                cBigUnsigned operator <<(int b) const
                {
                        cBigUnsigned ans;
                        ans.InitBitShiftLeft(*this, b);
                        return ans;
                }
                cBigUnsigned operator >> (int b) const
                {
                        cBigUnsigned ans;
                        ans.InitBitShiftRight(*this, b);
                        return ans;
                }
 
                // Overloaded assignment operators
                void operator +=(const THIS_t& x)
                {
                        InitAdd(*this, x);
                }
                void operator +=(BLOCK_t x)
                {
                        OpAdd1(x);
                }
                void operator -=(const THIS_t& x)
                {
                        InitSubtract(*this, x);
                }
                void operator -= (BLOCK_t x)
                {
                        OpSubtract1(x);
                }
                void operator *= (const THIS_t& x)
                {
                        InitMultiply(*this, x);
                }
                void operator *= (BLOCKH_t x)
                {
                        InitMultiplyH(*this, x);
                }
 
                void operator /= (const THIS_t& x)
                {
                        cBigUnsigned d = *this;
                        InitDivide(d, x);
                }
                void operator /= (BLOCKH_t n)
                {
                        (void)InitDivideH(*this, n);
                }
                inline void operator %=(const THIS_t& x)
                {
                        cBigUnsigned d = *this;
                        InitModulus(d, x);
                }
                void operator %= (BLOCKH_t n)
                {
                        // use *this as intermediate value as well.
                        put_ValU(InitDivideH(*this, n));
                }
                void operator &=(const THIS_t& x)
                {
                        InitBitAnd(*this, x);
                }
                void operator |=(const THIS_t& x)
                {
                        InitBitOr(*this, x);
                }
                void operator ^=(const THIS_t& x)
                {
                        InitBitXor(*this, x);
                }
                void operator <<=(int b)
                {
                        OpBitShiftLeft(b);
                }
                void operator >>=(int b)
                {
                        OpBitShiftRight(b);
                }
 
                // Increment/Decrement operators
                // To discourage messy coding, these do not return *this, so prefix and postfix behave the same.
                void operator ++()
                {
                        OpAdd1(1);
                }
                void operator ++(int)
                {
                        OpAdd1(1);
                }
                void operator --()
                {
                        OpSubtract1(1);
                }
                void operator --(int)
                {
                        OpSubtract1(1);
                }
 
                UNITTEST_FRIEND(cBigUnsigned);
        };
 
#ifdef USE_INT64
        template <>     inline INT64 cBigUnsigned::get_Val() const
        {
                return get_ValS<INT64>();
        }
#endif
#ifndef USE_LONG_AS_INT64
        template <>     inline long cBigUnsigned::get_Val() const
        {
                return get_ValS<long>();
        }
#endif
        template <> inline int cBigUnsigned::get_Val() const
        {
                return get_ValS<int>();
        }
        template <> inline short cBigUnsigned::get_Val() const
        {
                return get_ValS<short>();
        }
 
#ifdef USE_INT64
        template <>     inline void cBigUnsigned::put_Val(INT64 n)
        {
                put_ValS(n);
        }
#endif
#ifndef USE_LONG_AS_INT64
        template <>     inline void cBigUnsigned::put_Val(long n)
        {
                put_ValS(n);
        }
#endif
        template <> inline void cBigUnsigned::put_Val(int n)
        {
                put_ValS(n);
        }
        template <> inline void cBigUnsigned::put_Val(short n)
        {
                put_ValS(n);
        }
};
#endif