cBigInteger.h

Go to the documentation of this file.

//
//
#ifndef _INC_cBigInteger_H
#define _INC_cBigInteger_H
#ifndef NO_PRAGMA_ONCE
#pragma once
#endif
 
#include "cBigUnsigned.h"
 
namespace GrayLib
{
        UNITTEST2_PREDEF(cBigInteger);
 
        class GRAYLIB_LINK cBigInteger : public cBigUnsigned
        {
 
                typedef cBigUnsigned SUPER_t;
                typedef cBigInteger THIS_t;
 
        private:
                bool m_bNegative;       
 
        public:
                cBigInteger()
                        : m_bNegative(false)
                {
                }
                cBigInteger(const THIS_t& x)
                        : SUPER_t(x)
                        , m_bNegative(x.m_bNegative)
                {
                }
                cBigInteger(const cBigUnsigned& x, bool bNegative = false)
                        : SUPER_t(x)
                        , m_bNegative(bNegative)
                {
                        CheckNegativeZero();
                }
                cBigInteger(const char* pszStr, RADIX_t uRadix = 10)
                        : m_bNegative(false)
                {
                        SetStr(pszStr, uRadix);
                }
 
                cBigInteger(BLOCK_ENUM_t nBlocks, const BLOCK_t* pBlocks, bool bNegative)
                        : SUPER_t(nBlocks, pBlocks)
                        , m_bNegative(bNegative)
                {
                        ASSERT(!isStatic());
                }
                cBigInteger(BLOCK_ENUM_t nBlocks, const BLOCK_t* pBlocks, bool bStatic, bool bNegative)
                        : SUPER_t(nBlocks, pBlocks, bStatic)
                        , m_bNegative(bNegative)
                {
                        ASSERT(isStatic());
                }
 
                // Constructors from primitive integer types
                cBigInteger(UINTMAX_t x) { put_ValU(x); }
                cBigInteger(INTMAX_t x) { put_ValS(x); }
#if 1   // Stupid C++ compiler wont pick the correct one.
                cBigInteger(UINT32 x) { put_ValU(x); }
                cBigInteger(INT32 x) { put_ValS(x); }
#endif
 
                // Accessors
                bool isNegative() const
                {
                        ASSERT(!m_bNegative || !isZero());
                        return m_bNegative;
                }
                int get_Sign() const
                {
                        ASSERT(!m_bNegative || !isZero());
                        return m_bNegative ? (-1) : 1;
                }
                const cBigUnsigned& get_Magnitude() const
                {
                        return *this;
                }
 
                // Compares this to x like Perl's <=>
                COMPARE_t CompareU(BLOCK_t x) const
                {
                        if (isNegative())
                                return COMPARE_Less;
                        return SUPER_t::CompareU(x);
                }
                COMPARE_t CompareS(BLOCKI_t x) const;
                COMPARE_t Compare(const cBigInteger& x) const;
                COMPARE_t CompareMagnitude(const cBigUnsigned& x) const
                {
                        return SUPER_t::Compare(x);
                }
 
                bool IsEqual(const THIS_t& x) const
                {
                        return (m_bNegative == x.m_bNegative) && get_Magnitude().IsEqual(x.get_Magnitude());
                }
                bool IsEqual(BLOCKI_t x) const
                {
                        // AKA IsEqualS ?
                        if (get_BlocksUse() > 1)
                                return false;
                        BLOCK_t ux;
                        if (x < 0)
                        {
                                if (!m_bNegative)
                                        return false;
                                ux = (BLOCK_t)-x;
                        }
                        else
                        {
                                if (m_bNegative)
                                        return false;
                                ux = (BLOCK_t)x;
                        }
                        return GetBlock(0) == ux;
                }
 
                // Ordinary comparison operators
                bool operator ==(const THIS_t& x) const
                {
                        return IsEqual(x);
                }
                bool operator !=(const THIS_t& x) const
                {
                        return !IsEqual(x);
                }
                bool operator < (const THIS_t& x) const
                {
                        return Compare(x) < 0;
                }
                bool operator <=(const THIS_t& x) const
                {
                        return Compare(x) <= 0;
                }
                bool operator >=(const THIS_t& x) const
                {
                        return Compare(x) >= 0;
                }
                bool operator > (const THIS_t& x) const
                {
                        return Compare(x) > 0;
                }
 
                template <typename TYPE /*= BLOCK_t*/>
                TYPE get_ValS() const
                {
                        TYPE nVal = SUPER_t::get_ValS<TYPE>();
                        if (m_bNegative)
                                nVal = -nVal;
                        return nVal;
                }
                template <typename TYPE /*= BLOCK_t*/>
                TYPE get_Val() const
                {
                        return SUPER_t::get_ValUC<TYPE>();
                }
 
                StrLen_t GetStr(char* pszOut, StrLen_t iOutMax, RADIX_t uRadix = 10) const;
                cString GetStr(RADIX_t uRadix = 10) const;
 
                // Modifiers
                bool SetStr(const char* pszIn, RADIX_t uRadix = 10, const char** ppszEnd = nullptr);
 
                HRESULT SetBinaryBE(const BYTE* pData, size_t nSize, bool bByteSign);
                HRESULT SetBinaryBE(const cMemBlock& b, bool bByteSign)
                {
                        return SetBinaryBE(b.get_DataBytes(), b.get_DataSize(), bByteSign);
                }
 
                HRESULT GetBinaryBE(BYTE* pOut, size_t nSizeOut) const
                {
                        ASSERT(!isNegative());
                        return SUPER_t::GetBinaryBE(pOut, nSizeOut);
                }
 
                void SetCopyInt(const cBigInteger& x);
 
                HRESULT SetCopySecure(const THIS_t& val, bool assign)
                {
                        HRESULT hRes = SUPER_t::SetCopySecure(val, assign);
                        this->put_Sign(this->get_Sign() * (1 - assign) + val.get_Sign() * assign);
                        return hRes;
                }
                static HRESULT GRAYCALL SwapSecure(THIS_t& X, THIS_t& Y, bool swap) // static 
                {
                        HRESULT hRes = SUPER_t::SwapSecure(X, Y, swap);
                        int s = X.get_Sign();
                        X.put_Sign(X.get_Sign() * (1 - swap) + Y.get_Sign() * swap);
                        Y.put_Sign(Y.get_Sign() * (1 - swap) + s * swap);
                        return hRes;
                }
 
                void operator=(const THIS_t& x)
                {
                        SetCopyInt(x);
                }
 
                void SetZeroAll()
                {
                        m_bNegative = false;
                        SUPER_t::SetZeroAll();
                }
                void SetNullVal()
                {
                        m_bNegative = false;
                        SUPER_t::SetNullVal();
                }
 
                void put_ValU(UINTMAX_t n)
                {
                        m_bNegative = false;
                        SUPER_t::put_ValU(n);
                }
                void put_ValS(INTMAX_t n)
                {
                        m_bNegative = (n < 0);
                        SUPER_t::put_ValU((UINTMAX_t)(m_bNegative ? (-n) : n));
                }
                template <typename TYPE>
                void put_Val(TYPE n)
                {
                        return put_ValU(n);
                }
 
                void SetBlocksStatic(BLOCK_ENUM_t nBlocks, const BLOCK_t* pBlocks);
                void SetBlocksStatic(const cBitArrayStatic& b);
 
                // OPERATORS -- See the discussion in cBigUnsigned.hh.
                void OpAdd1(BLOCKI_t n);
                void OpSubtract1(BLOCKI_t n);
 
                void InitAdd(const cBigInteger& a, const cBigInteger& b);
                void InitAddU(const cBigUnsigned& a, const cBigUnsigned& b)
                {
                        this->put_Negative(false);
                        SUPER_t::InitAdd(a, b);
                }
                void InitSubtract(const cBigInteger& a, const cBigInteger& b);
                HRESULT InitSubU(const cBigUnsigned& a, const cBigUnsigned& b)
                {
                        this->put_Negative(false);
                        return SUPER_t::InitSubtract(a, b);
                }
                void OpSubtract(const THIS_t& b)
                {
                        InitSubtract(*this, b);
                }
                HRESULT OpSubtractU(const cBigUnsigned& a)
                {
                        return SUPER_t::OpSubtract(a);
                }
 
                void InitSubtract1(const THIS_t& a, BLOCKI_t n)
                {
                        if (this != &a)
                                SetCopyInt(a);
                        OpSubtract1(n);
                }
                void InitAdd1(const THIS_t& a, BLOCKI_t n)
                {
                        if (this != &a)
                                SetCopyInt(a);
                        OpAdd1(n);
                }
 
                void InitMultiply(const cBigInteger& a, const cBigInteger& b);
                HRESULT InitDivide(const cBigInteger& dividend, const cBigInteger& divisor, OUT cBigInteger& remainder);
                HRESULT InitDivide(const THIS_t& a, const cBigInteger& b)
                {
                        THIS_t rJunkRemainder;
                        return InitDivide(a, b, rJunkRemainder);
                }
                HRESULT InitModulus(const THIS_t& a, const THIS_t& b)
                {
                        THIS_t rJunkQuotient;
                        return rJunkQuotient.InitDivide(a, b, *this);
                }
                HRESULT InitModulusU(const THIS_t& a, const THIS_t& b);
 
                BLOCK_t GetModulusH(BLOCKH_t b) const
                {
                        BLOCK_t nVal = SUPER_t::GetModulusH(b);
                        // If this is negative, then the current nVal represents a negative value.
                        // Flipping it to the positive side.
                        if (this->isNegative() && nVal != 0)
                                nVal = b - nVal;
                        return nVal;
                }
 
                cBigInteger operator +(const THIS_t& x) const
                {
                        cBigInteger ans;
                        ans.InitAdd(*this, x);
                        return ans;
                }
                cBigInteger operator -(const THIS_t& x) const
                {
                        cBigInteger ans;
                        ans.InitSubtract(*this, x);
                        return ans;
                }
                cBigInteger operator *(const THIS_t& x) const
                {
                        cBigInteger ans;
                        ans.InitMultiply(*this, x);
                        return ans;
                }
                cBigInteger operator /(const THIS_t& x) const
                {
                        cBigInteger q;
                        q.InitDivide(*this, x);
                        return q;
                }
                cBigInteger operator %(const THIS_t& x) const
                {
                        cBigInteger r;
                        r.InitModulus(*this, x);
                        return r;
                }
                cBigInteger operator -() const
                {
                        cBigInteger ans;
                        ans.SetCopyInt(*this);
                        ans.FlipSign();
                        return ans;
                }
 
                void operator +=(const THIS_t& x)
                {
                        InitAdd(*this, x);
                }
                void operator -=(const THIS_t& x)
                {
                        InitSubtract(*this, x);
                }
                void operator *=(const THIS_t& x)
                {
                        InitMultiply(*this, x);
                }
                void operator /=(const THIS_t& x)
                {
                        cBigInteger d = *this;
                        InitDivide(d, x);
                }
                inline void operator %=(const THIS_t& x)
                {
                        cBigInteger d = *this;
                        InitModulus(d, x);
                }
 
                void CheckNegativeZero()
                {
                        if (m_bNegative && isZero())
                                m_bNegative = false;
                }
                void put_Negative(bool b = true)
                {
                        m_bNegative = b;
                        CheckNegativeZero();
                }
                void put_Sign(int nSign)
                {
                        m_bNegative = (nSign < 0);
                        CheckNegativeZero();
                }
                inline void FlipSign()
                {
                        if (isZero())
                        {
                                m_bNegative = false;
                                return;
                        }
                        m_bNegative = !m_bNegative;
                }
 
                // INCREMENT/DECREMENT OPERATORS
                void operator ++()
                {
                        OpAdd1(1);
                }
                void operator ++(int)
                {
                        OpAdd1(1);
                }
                void operator --()
                {
                        OpSubtract1(1);
                }
                void operator --(int)
                {
                        OpSubtract1(1);
                }
 
                void InitGreatestCommonDivisor(const cBigInteger& a, const cBigInteger& b);
                static HRESULT GRAYCALL ExtendedEuclidean(const cBigUnsigned& m, const cBigUnsigned& n, cBigUnsigned& g, cBigInteger& r, cBigInteger& s);
                HRESULT InitModInv(const cBigInteger& A, const cBigInteger& N);
                HRESULT SetPowerMod(const THIS_t& base, const THIS_t& exponent, const THIS_t& modulus, OUT cBigUnsigned* pRR);
 
                UNITTEST_FRIEND(cBigInteger);
        };
 
        // overloads to get signed value correctly.
        template <> inline INT64 cBigInteger::get_Val() const
        {
                return get_ValS<INT64>();
        }
#ifndef USE_LONG_AS_INT64
        template <>     inline long cBigInteger::get_Val() const
        {
                return get_ValS<long>();
        }
#endif
        template <> inline int cBigInteger::get_Val() const
        {
                return get_ValS<int>();
        }
        template <> inline short cBigInteger::get_Val() const
        {
                return get_ValS<short>();
        }
 
#ifdef USE_INT64
        template <>     inline void cBigInteger::put_Val(INT64 n)
        {
                put_ValS(n);
        }
#endif
#ifndef USE_LONG_AS_INT64
        template <>     inline void cBigInteger::put_Val(long n)
        {
                put_ValS(n);
        }
#endif
        template <> inline void cBigInteger::put_Val(int n)
        {
                put_ValS(n);
        }
        template <> inline void cBigInteger::put_Val(short n)
        {
                put_ValS(n);
        }
};
#endif