Standard Portable Library: spl/BigInteger.h Source File

00001 /*
00002  *   This file is part of the Standard Portable Library (SPL).
00003  *
00004  *   SPL is free software: you can redistribute it and/or modify
00005  *   it under the terms of the GNU General Public License as published by
00006  *   the Free Software Foundation, either version 3 of the License, or
00007  *   (at your option) any later version.
00008  *
00009  *   SPL is distributed in the hope that it will be useful,
00010  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  *   GNU General Public License for more details.
00013  *
00014  *   You should have received a copy of the GNU General Public License
00015  *   along with SPL.  If not, see <http://www.gnu.org/licenses/>.
00016  */
00017 #ifndef _BigInteger_h
00018 #define _BigInteger_h
00019 
00020 #include <spl/types.h>
00021 #include <spl/collection/Array.h>
00022 #include <spl/math/Random.h>
00023 #include <spl/RefCountPtr.h>
00024 #include <spl/String.h>
00025 
00032 #define BIGINTEGER_MAJIC 721            //< Majic number for ASSERT's in Compare and Convert
00033 
00034 class BigInteger;
00035 typedef RefCountPtr<BigInteger> BigIntegerPtr;
00036 typedef WeakReference<BigInteger, BigIntegerPtr> BigIntegerRef;
00037 
00038 REGISTER_TYPEOF( 550, BigIntegerPtr );
00039 REGISTER_TYPEOF( 552, BigIntegerRef );
00040 
00042 class BigInteger : public IComparable, public IMemoryValidate
00043 {
00044 // STATIC's
00045 private:
00046 
00047 #define BIGINTEGER_PRIMELIST_ROWS 52
00048 #define BIGINTEGER_PRIMELIST_COLS 9
00049 
00050         static const int m_primeLists[BIGINTEGER_PRIMELIST_ROWS][BIGINTEGER_PRIMELIST_COLS];
00051         static int m_primeProducts[BIGINTEGER_PRIMELIST_ROWS];
00052         static bool m_primeProductsInited;
00053 
00054         static const byte m_rndMask[];
00055 
00056 #define BIGINTEGER_IMASK ((int64)0xffffffffL)
00057 #define BIGINTEGER_UIMASK ((uint64)0xffffffffL)
00058 
00059         static const int m_chunk2; // TODO Parse 64 bits at a time
00060         static const int m_chunk10;
00061         static const int m_chunk16;
00062 
00063 #define BitsPerByte 8
00064 #define BitsPerInt 32
00065 #define BytesPerInt 4
00066 
00067         static Random m_randomSource;
00068         static BigIntegerPtr m_zero;
00069         static BigIntegerPtr m_one;
00070         static BigIntegerPtr m_two;
00071 
00072         static void Init2();
00073 
00074         inline static void Init()
00075         {
00076                 if (m_primeProductsInited)
00077                 {
00078                         return;
00079                 }
00080                 Init2();
00081         }
00082 
00083         static int GetByteLength(int nBits)
00084         {
00085                 return (nBits + BitsPerByte - 1) / BitsPerByte;
00086         }
00087 
00088         static BigIntegerPtr CreateUValueOf(uint64 value);
00089         static BigIntegerPtr CreateValueOf(int64 value);
00090 
00091         static RefCountPtr<Array<int32> > MakeMagnitude(const Array<byte>& bytes, int offset, int length);
00092 
00093         static int CompareNoLeadingZeroes(int xIndx, const Array<int32>& x, int yIndx, const Array<int32>& y);
00094 
00095         inline static int BitLen(int w)
00096         {
00097                 // Binary search - decision tree (5 tests, rarely 6)
00098                 return (w < 1 << 15 ? (w < 1 << 7
00099                         ? (w < 1 << 3 ? (w < 1 << 1
00100                         ? (w < 1 << 0 ? (w < 0 ? 32 : 0) : 1)
00101                         : (w < 1 << 2 ? 2 : 3)) : (w < 1 << 5
00102                         ? (w < 1 << 4 ? 4 : 5)
00103                         : (w < 1 << 6 ? 6 : 7)))
00104                         : (w < 1 << 11
00105                         ? (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9) : (w < 1 << 10 ? 10 : 11))
00106                         : (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13) : (w < 1 << 14 ? 14 : 15)))) : (w < 1 << 23 ? (w < 1 << 19
00107                         ? (w < 1 << 17 ? (w < 1 << 16 ? 16 : 17) : (w < 1 << 18 ? 18 : 19))
00108                         : (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21) : (w < 1 << 22 ? 22 : 23))) : (w < 1 << 27
00109                         ? (w < 1 << 25 ? (w < 1 << 24 ? 24 : 25) : (w < 1 << 26 ? 26 : 27))
00110                         : (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29) : (w < 1 << 30 ? 30 : 31)))));
00111         }
00112 
00113         static RefCountPtr<Array<int32> > DoSubBigLil(Array<int32>& bigMag, Array<int32>& lilMag);
00114 
00115         static void ShiftRightOneInPlace(int start, Array<int32>& mag);
00116         static void ShiftRightInPlace(int start, Array<int32>& mag, int n);
00117         static RefCountPtr<Array<int32> > ShiftLeft(Array<int32>& mag, int n);
00118 
00119         static void AddMagnitudes(Array<int32>& a, Array<int32>& b);
00120 
00121         static const BigInteger& Two();
00122 
00123         static void Subtract
00124         (
00125                 int xIndx,
00126                 Array<int32>& x,
00127                 int yIndx,
00128                 Array<int32>& y
00129         );
00130 
00131         static void Multiply
00132         (
00133                 Array<int32>&   x,
00134                 Array<int32>&   y,
00135                 Array<int32>&   z
00136         );
00137 
00138         static void MultiplyMonty
00139         (
00140                 Array<int32>&   a,
00141                 Array<int32>&   x,
00142                 Array<int32>&   y,
00143                 Array<int32>&   m,
00144                 int64                   mQuote
00145         );
00146 
00147         static uint32 MultiplyMontyNIsOne
00148         (
00149                 uint32  x,
00150                 uint32  y,
00151                 uint32  m,
00152                 uint64  mQuote
00153         );
00154 
00155         static int CompareTo
00156         (
00157                 int xIndx,
00158                 Array<int32>& x,
00159                 int yIndx,
00160                 Array<int32>& y
00161         );
00162 
00163         static RefCountPtr<Array<int32> > Square
00164         (
00165                 RefCountPtr<Array<int32> >      w,
00166                 RefCountPtr<Array<int32> >      x
00167         );
00168 
00169         static BigIntegerPtr ExtEuclid
00170         (
00171                 const BigInteger&       a,
00172                 const BigInteger&       b,
00173                 BigIntegerPtr u1Out,
00174                 BigIntegerPtr u2Out
00175         );
00176 
00177 // CLASS MEMBERS
00178 private:
00179         int32 m_sign;                           // -1 means -ve; +1 means +ve; 0 means 0;
00180         RefCountPtr<Array<int32> > m_magnitude; // array of ints with [0] being the most significant
00181         int32 m_nBits;                          // cache BitCount() value
00182         int32 m_nBitLength;                     // cache calcBitLength() value
00183         int64 m_mQuote;                         // -m^(-1) mod b, b = 2^32 (see Montgomery mult.)
00184 
00185         inline void ConstructCommon()
00186         {
00187                 Init();
00188                 m_nBits = -1;
00189                 m_nBitLength = -1;
00190                 m_mQuote = -1L;
00191         }
00192 
00193         inline bool QuickPow2Check() const
00194         {
00195                 return m_sign > 0 && m_nBits == 1;
00196         }
00197 
00198         BigInteger(int signNum, RefCountPtr<Array<int32> > mag, bool checkMag);
00199 
00200         void ConstructWith(int signNum, RefCountPtr<Array<int32> > mag, bool checkMag);
00201         void ConstructWith(Array<byte>& bytes, int offset, int length);
00202         void ConstructWith(int sign, Array<byte>& bytes, int offset, int length);
00203 
00204         int64 GetMQuote();
00205         bool CheckProbablePrime(int certainty, Random& random) const;
00206         bool RabinMillerTest(int certainty, Random& random) const;
00207 
00208         int CalcBitLength(int indx, const Array<int32>& mag) const;
00209         RefCountPtr<Array<int32> > LastNBits(int n) const;
00210 
00211         BigIntegerPtr AddToMagnitude(RefCountPtr<Array<int32> > magToAdd) const;
00212 
00213         int32 Remainder(int m) const;
00214         void Remainder(RefCountPtr<Array<int32> > x, RefCountPtr<Array<int32> > y) const;
00215 
00216         RefCountPtr<Array<int32> > Divide
00217         (
00218                 RefCountPtr<Array<int32> > x,
00219                 RefCountPtr<Array<int32> > y
00220         ) const;
00221 
00222         BigIntegerPtr Inc() const;
00223         BigIntegerPtr FlipExistingBit(int n) const;
00224 
00225         inline BigIntegerPtr AndNot(const BigInteger& val) const
00226         {
00227                 BigIntegerPtr tmp = val.Not();
00228                 return And(*tmp);
00229         }
00230 
00231         void ToByteArray(Array<byte>& a, bool isUnsigned) const;
00232 
00233 public:
00234         BigInteger();
00235         BigInteger(Array<byte>& bytes);
00236         BigInteger(Array<byte>& bytes, int offset, int length);
00237         BigInteger(int sign, Array<byte>& bytes, int offset, int length);
00238         BigInteger(int sign, Array<byte>& bytes);
00239         BigInteger(int sizeInBits, Random& random);
00240         BigInteger(int bitLength, int certainty, Random& random);
00241 
00242         BigInteger(const BigInteger& toCopy);
00243         BigInteger& operator =(const BigInteger& toAssign);
00244         BigInteger& operator =(const int64 i);
00245         virtual ~BigInteger();
00246 
00247         bool TestBit(int n) const;
00248 
00249         inline int GetBitLength() const
00250         {
00251                 return m_nBitLength;
00252         }
00253 
00254         int GetLowestSetBit() const;
00255 
00256         inline BigIntegerPtr Abs() const
00257         {
00258                 return m_sign >= 0 ? BigIntegerPtr(new BigInteger(*this)) : Negate();
00259         }
00260 
00261         inline BigIntegerPtr Not() const
00262         {
00263                 return Inc()->Negate();
00264         }
00265 
00266         BigIntegerPtr And(const BigInteger& value) const;
00267         BigIntegerPtr Or(const BigInteger& value) const;
00268         BigIntegerPtr Xor(const BigInteger& value) const;
00269         BigIntegerPtr SetBit(int n) const;
00270         BigIntegerPtr ClearBit(int n) const;
00271         BigIntegerPtr FlipBit(int n) const;
00272 
00273         inline BigIntegerPtr Negate() const
00274         {
00275                 if (m_sign == 0)
00276                         return BigIntegerPtr(new BigInteger(*this));
00277 
00278                 return BigIntegerPtr(new BigInteger(-m_sign, RefCountPtr<Array<int32> >(m_magnitude->Clone()), false));
00279         }
00280 
00281         BigIntegerPtr ShiftRight(int n) const;
00282         BigIntegerPtr ShiftLeft(int n) const;
00283 
00284         BigIntegerPtr Remainder(const BigInteger& n) const;
00285         BigIntegerPtr ModPow(const BigInteger& exponent, BigInteger& m);
00286         BigIntegerPtr Mod(const BigInteger &m) const;
00287         BigIntegerPtr ModInverse(const BigInteger& m) const;
00288 
00289         BigIntegerPtr Multiply(const BigInteger& val) const;
00290 
00291         BigIntegerPtr Divide(const BigInteger& val) const;
00292         Array<BigIntegerPtr> DivideAndRemainder(const BigInteger& val) const;
00293 
00294         BigIntegerPtr Add(const BigInteger& value) const;
00295         BigIntegerPtr Subtract(const BigInteger& n) const;
00296 
00297         BigIntegerPtr Gcd(const BigInteger& value) const;
00298         bool IsProbablePrime(int certainty) const;
00299 
00300         inline BigInteger& operator +=(const BigInteger& bi) { *this = *Add(bi); return *this; }
00301         inline BigInteger& operator -=(const BigInteger& bi) { *this = *Subtract(bi); return *this; }
00302         inline BigInteger& operator *=(const BigInteger& bi) { *this = *Multiply(bi); return *this; }
00303         inline BigInteger& operator /=(const BigInteger& bi) { *this = *Divide(bi); return *this; }
00304 
00305         inline BigInteger& operator <<=(int shiftVal) { *this = *ShiftLeft(shiftVal); return *this; }
00306         inline BigInteger& operator >>=(int shiftVal) { *this = *ShiftRight(shiftVal); return *this; }
00307 
00308         BigInteger& operator %=(const BigInteger& bi) { *this = *Mod(bi); return *this; }
00309         BigInteger& operator &=(const BigInteger& bi) { *this = *And(bi); return *this; }
00310         BigInteger& operator |=(const BigInteger& bi) { *this = *Or(bi); return *this; }
00311         BigInteger& operator ^=(const BigInteger& bi) { *this = *Xor(bi); return *this; }
00312 
00313         inline friend BigInteger operator +(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.Add(bi2); }
00314         inline friend BigInteger operator -(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.Subtract(bi2); }
00315         inline friend BigInteger operator *(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.Multiply(bi2); }
00316         inline friend BigInteger operator /(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.Divide(bi2); }
00317         inline friend BigInteger operator %(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.Mod(bi2); }
00318 
00319         inline friend BigInteger operator +(const BigInteger& bi1, int64 i) { BigInteger tmp = *ValueOf(i); return *bi1.Add(tmp); }
00320         inline friend BigInteger operator -(const BigInteger& bi1, int64 i) { BigInteger tmp = *ValueOf(i); return *bi1.Subtract(tmp); }
00321         inline friend BigInteger operator *(const BigInteger& bi1, int64 i) { BigInteger tmp = *ValueOf(i); return *bi1.Multiply(tmp); }
00322         inline friend BigInteger operator /(const BigInteger& bi1, int64 i) { BigInteger tmp = *ValueOf(i); return *bi1.Divide(tmp); }
00323         inline friend BigInteger operator %(const BigInteger& bi1, int64 i) { BigInteger tmp = *ValueOf(i); return *bi1.Mod(tmp); }
00324 
00325         inline friend BigInteger operator &(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.And(bi2); }
00326         inline friend BigInteger operator |(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.Or(bi2); }
00327         inline friend BigInteger operator ^(const BigInteger& bi1, const BigInteger& bi2) { return *bi1.Xor(bi2); }
00328         
00329         inline BigInteger operator <<(int shiftVal) const { return *ShiftLeft(shiftVal); }
00330         inline BigInteger operator >>(int shiftVal) const { return *ShiftRight(shiftVal); }
00331         
00332         inline friend BigInteger operator -(const BigInteger& bi) { return *bi.Negate(); }
00333         friend BigInteger operator ~(const BigInteger& bi);
00334         inline friend BigInteger operator !(const BigInteger& bi) { return *bi.Not(); }
00335 
00336         inline friend bool operator ==(const BigInteger& bi1, const BigInteger& bi2) { return bi1.Equals(bi2); }
00337         inline friend bool operator ==(const BigInteger& bi1, int64 i) { BigInteger tmp = *ValueOf(i); return bi1 == tmp; }
00338         inline friend bool operator !=(const BigInteger& bi1, const BigInteger& bi2) { return !bi1.Equals(bi2); }
00339         inline friend bool operator !=(const BigInteger& bi1, int64 i) { return bi1 != i; }
00340         inline friend bool operator >(const BigInteger& bi1, const BigInteger& bi2) { return bi1.Compare(bi2) > 0; }
00341         inline friend bool operator <(const BigInteger& bi1, const BigInteger& bi2) { return bi1.Compare(bi2) < 0; }
00342         inline friend bool operator >=(const BigInteger& bi1, const BigInteger& bi2) { return bi1.Compare(bi2) >= 0; }
00343         inline friend bool operator <=(const BigInteger& bi1, const BigInteger& bi2) { return bi1.Compare(bi2) <= 0; }
00344 
00345         inline friend bool operator &&(const BigInteger& bi1, const BigInteger& bi2) { BigInteger tmp = *bi1.And(bi2); return tmp != 0; }
00346         inline friend bool operator ||(const BigInteger& bi1, const BigInteger& bi2) { BigInteger tmp = *bi1.Or(bi2); return tmp != 0; }
00347 
00348         String ToString() const;
00349 
00350         inline Array<byte> ToByteArrayUnsigned() const
00351         {
00352                 Array<byte> a;
00353                 ToByteArray(a, true);
00354                 return a;
00355         }
00356 
00357         inline void ToByteArrayUnsigned(Array<byte>& a) const
00358         {
00359                 ToByteArray(a, true);
00360         }
00361 
00362         inline Array<byte> ToByteArray() const
00363         {
00364                 Array<byte> a;
00365                 ToByteArray(a, false);
00366                 return a;
00367         }
00368 
00369         inline void ToByteArray(Array<byte>& a) const
00370         {
00371                 ToByteArray(a, false);
00372         }
00373 
00374         inline int32 ToInt() const
00375         {
00376                 return m_sign == 0 ? 0
00377                         : m_sign > 0 ? (*m_magnitude)[m_magnitude->Length() - 1]
00378                         : -(*m_magnitude)[m_magnitude->Length() - 1];
00379         }
00380 
00381         inline int64 ToInt64() const
00382         {
00383                 if( m_sign == 0 )
00384                 {
00385                         return 0;
00386                 }
00387 
00388                 int64 i = (uint32)(*m_magnitude)[m_magnitude->Length() - 1];
00389                 if (m_magnitude->Count() > 1)
00390                 {
00391                         int64 i2 = (uint32)(*m_magnitude)[m_magnitude->Length() - 2];
00392                         i |= i2 << 32;
00393                 }
00394 
00395                 if (m_sign < 0)
00396                 {
00397                         return -i;
00398                 }
00399                 return i;
00400         }
00401 
00402         inline uint32 ToUInt() const
00403         {
00404                 return (*m_magnitude)[m_magnitude->Length() - 1];
00405         }
00406 
00407         virtual bool Equals( const IComparable *a ) const;
00408         virtual int Compare( const IComparable *a ) const;
00409         virtual bool Equals( const IComparable& a ) const;
00410         virtual int Compare( const IComparable& a ) const;
00411         bool Equals(int64 i) const;
00412 
00415         virtual int32 MajicNumber() const;
00416         virtual int32 HashCode() const;
00417 
00418         inline static BigIntegerPtr ValueOf(int64 i) { return CreateValueOf(i); }
00419         static const BigInteger& Zero();
00420         static BigIntegerPtr ZeroPtr();
00421         static const BigInteger& One();
00422         static BigIntegerPtr OnePtr();
00423 
00424 #if defined(DEBUG) || defined(_DEBUG)
00425         virtual void CheckMem() const;
00426         virtual void ValidateMem() const;
00427 
00428         static void CheckMemStatics();
00429         static void DebugClearStatics();
00430 #endif
00431 };
00432 
00433 inline void ValidateType(const BigInteger& b)
00434 {
00435 #ifdef DEBUG
00436         b.ValidateMem();
00437         b.CheckMem();
00438 #endif
00439 }
00440 
00441 inline void ValidateType(BigIntegerPtr b)
00442 {
00443 #ifdef DEBUG
00444         b.ValidateMem();
00445         b.CheckMem();
00446 #endif
00447 }
00448 
00449 REGISTER_TYPEOF( 554, BigInteger );
00450 
00453 #endif