BigInteger.hpp
Go to the documentation of this file.
00001 /***************************************************************************** 00002 * Copyright (C) 2012 by Benjamin Hadorn (b_hadorn@bluewin.ch) 00003 ***************************************************************************** 00004 * Project : Zeus Base Library 00005 * Module : BigInteger 00006 * Package : Zeus.ZeusBase.System 00007 * Author : Benjamin Hadorn 00008 * Date : 08.01.2012 00009 * System : Zeus-Framework 00010 ***************************************************************************** 00011 * Licence: * 00012 * This library is free software; you can redistribute it and/or modify * 00013 * it under the terms of the GNU Lesser General Public License as * 00014 * published by the Free Software Foundation; either version * 00015 * 2.1 of the License, or (at your option) any later version. * 00016 * * 00017 * This library is distributed in the hope that it will be useful, * 00018 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00019 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 00020 * GNU Lesser General Public License for more details. * 00021 * * 00022 * You should have received a copy of the GNU Lesser General Public * 00023 * License along with this library; if not, write to the Free Software * 00024 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA * 00025 *****************************************************************************/ 00026 00027 /***************************************************************************** 00028 * Changes: 00029 *****************************************************************************/ 00030 00031 #ifndef BigIntegerHPP 00032 #define BigIntegerHPP 00033 00034 #include <zeusbase/System/BigIntegerBase.h> 00035 #include <zeusbase/System/BitCodedValue.h> 00036 #include <zeusbase/System/ByteArray.hpp> 00037 00038 BEGIN_NAMESPACE_Zeus 00039 00040 /***************************************************************************/ 00043 /***************************************************************************/ 00044 template <int N> class TBigInteger 00045 { 00046 public: 00047 /*************************************************************************/ 00050 /*************************************************************************/ 00051 inline TBigInteger() 00052 { 00053 ::memset(m_aui8Data, 0x00, N); 00054 } 00055 00056 /*************************************************************************/ 00060 /*************************************************************************/ 00061 inline TBigInteger(const TBigInteger<N>& rValue) 00062 { 00063 assign(rValue); 00064 } 00065 00066 /*************************************************************************/ 00071 /*************************************************************************/ 00072 inline TBigInteger(const IByteArray& rArray, Int iFromIndex = 0) 00073 { 00074 ::memset(m_aui8Data, 0x00, N); 00075 Int iCount = rArray.getCount() - iFromIndex; 00076 00077 if (iCount > 0) 00078 { 00079 if (iCount > N) 00080 { 00081 iCount = N; 00082 } 00083 ::memcpy(m_aui8Data, rArray.getArrayConst() + iFromIndex, iCount); 00084 } 00085 } 00086 00087 /*************************************************************************/ 00092 /*************************************************************************/ 00093 inline TBigInteger(const Uint8* pui8Array, Int iSize) 00094 { 00095 ::memset(m_aui8Data, 0x00, N); 00096 if (iSize > N) 00097 { 00098 iSize = N; 00099 } 00100 ::memcpy(m_aui8Data, pui8Array, iSize); 00101 } 00102 00103 /*************************************************************************/ 00107 /*************************************************************************/ 00108 inline TBigInteger(int iValue) 00109 { 00110 #if defined(__ZEUS32__) 00111 assign32bit((Uint32)iValue, iValue < 0); 00112 #elif defined(__ZEUS64__) 00113 assign64bit((Uint64)iValue, iValue < 0); 00114 #endif 00115 } 00116 00117 /*************************************************************************/ 00121 /*************************************************************************/ 00122 inline TBigInteger(unsigned int uiValue) 00123 { 00124 #if defined(__ZEUS32__) 00125 assign32bit((Uint32)uiValue, false); 00126 #elif defined(__ZEUS64__) 00127 assign64Uint((Uint64)uiValue, false); 00128 #endif 00129 } 00130 00131 /*************************************************************************/ 00135 /*************************************************************************/ 00136 inline TBigInteger(Uint32 ui32Value) 00137 { 00138 assign32bit(ui32Value, false); 00139 } 00140 00141 /*************************************************************************/ 00145 /*************************************************************************/ 00146 inline TBigInteger(Int32 i32Value) 00147 { 00148 assign32bit((Uint32)i32Value, i32Value < 0); 00149 } 00150 00151 /*************************************************************************/ 00155 /*************************************************************************/ 00156 inline TBigInteger(Uint64 ui64Value) 00157 { 00158 assign64bit(ui64Value, false); 00159 } 00160 00161 /*************************************************************************/ 00165 /*************************************************************************/ 00166 inline TBigInteger(Int64 i64Value) 00167 { 00168 assign64bit((Uint64)i64Value, i64Value < 0); 00169 } 00170 00171 //factory methods 00172 /*************************************************************************/ 00177 /*************************************************************************/ 00178 static inline TBigInteger<N> createFromHex(const TString& rHexString) 00179 { 00180 bool bError = false; 00181 TByteArray aValue; 00182 TBitCodedValue::convertHexToByteArray(rHexString, bError, aValue); 00183 return TBigInteger<N>(aValue); 00184 } 00185 00186 /*************************************************************************/ 00190 /*************************************************************************/ 00191 inline Int getBitSize() const { return N << 3; } 00192 00193 /*************************************************************************/ 00197 /*************************************************************************/ 00198 inline Int getByteSize() const { return N; } 00199 00200 /*************************************************************************/ 00204 /*************************************************************************/ 00205 inline Int getBitLength() const { return (getLastSignPos(m_aui8Data) + 1) * 8; } 00206 00207 /*************************************************************************/ 00212 /*************************************************************************/ 00213 inline bool isNegative() const 00214 { 00215 return (m_aui8Data[N-1] & 0x80); 00216 } 00217 00218 /*************************************************************************/ 00223 /*************************************************************************/ 00224 inline bool isZero() const 00225 { 00226 return TBigIntegerBase::isZero(m_aui8Data, N); 00227 } 00228 00229 //math. functions 00230 /*************************************************************************/ 00235 /*************************************************************************/ 00236 inline TBigInteger<N>& add(const TBigInteger<N>& rParam) 00237 { 00238 TBigIntegerBase::add(rParam.m_aui8Data, N, m_aui8Data, N); 00239 return *this; 00240 } 00241 00242 /*************************************************************************/ 00247 /*************************************************************************/ 00248 inline TBigInteger<N>& add(int iParam) 00249 { 00250 Uint8* pui8Buffer = (Uint8*)(&iParam); 00251 TBigIntegerBase::add(pui8Buffer, sizeof(int), m_aui8Data, N); 00252 return *this; 00253 } 00254 00255 /*************************************************************************/ 00260 /*************************************************************************/ 00261 inline TBigInteger<N>& add(unsigned int uiParam) 00262 { 00263 Uint8* pui8Buffer = (Uint8*)(&uiParam); 00264 add_internal(pui8Buffer, sizeof(unsigned int), m_aui8Data, N); 00265 return *this; 00266 } 00267 00268 /*************************************************************************/ 00272 /*************************************************************************/ 00273 inline void assign(const TBigInteger<N>& rParam) 00274 { 00275 ::memcpy(m_aui8Data, rParam.m_aui8Data, N); 00276 } 00277 00278 /*************************************************************************/ 00281 /*************************************************************************/ 00282 inline void clear() 00283 { 00284 ::memset(m_aui8Data, 0x00, N); 00285 } 00286 00287 /*************************************************************************/ 00295 /*************************************************************************/ 00296 inline Int compareTo(const TBigInteger<N>& rParam) const 00297 { 00298 return compareTo_internal(m_aui8Data, rParam.m_aui8Data); 00299 } 00300 00301 /*************************************************************************/ 00306 /*************************************************************************/ 00307 inline TBigInteger<N>& divide(const TBigInteger<N>& rParam) 00308 { 00309 TBigInteger<N> Modulo; 00310 divide_internal(rParam.m_aui8Data, m_aui8Data, Modulo.m_aui8Data); 00311 return *this; 00312 } 00313 00314 /*************************************************************************/ 00319 /*************************************************************************/ 00320 inline TBigInteger<N>& divideExt(const TBigInteger<N>& rParam, TBigInteger<N>& rModulo) 00321 { 00322 divide_internal(rParam.m_aui8Data, m_aui8Data, rModulo.m_aui8Data); 00323 return *this; 00324 } 00325 00326 /*************************************************************************/ 00331 /*************************************************************************/ 00332 inline TBigInteger<N> getNegated() const 00333 { 00334 TBigInteger<N> Value(*this); 00335 TBigIntegerBase::negate(Value.m_aui8Data, N); 00336 return Value; 00337 } 00338 00339 /*************************************************************************/ 00345 /*************************************************************************/ 00346 inline TBigInteger<N> getLeftShifted(Int iShift) const 00347 { 00348 TBigInteger<N> Value(*this); 00349 Value.shiftLeft_internal(Value.m_aui8Data, N, iShift); 00350 return Value; 00351 } 00352 00353 /*************************************************************************/ 00359 /*************************************************************************/ 00360 inline TBigInteger<N> getRightShifted(Int iShift) const 00361 { 00362 TBigInteger<N> Value(*this); 00363 Value.shiftRight_internal(Value.m_aui8Data, N, iShift); 00364 return Value; 00365 } 00366 00367 /*************************************************************************/ 00373 /*************************************************************************/ 00374 inline TBigInteger<N> getSubtracted(const TBigInteger<N>& rParam) const 00375 { 00376 TBigInteger<N> Value(*this); 00377 Value.subtract(rParam); 00378 return Value; 00379 } 00380 00381 /*************************************************************************/ 00386 /*************************************************************************/ 00387 inline TBigInteger<N>& mod(const TBigInteger<N>& rParam) 00388 { 00389 TBigInteger<N> Modulo; 00390 divide_internal(rParam.m_aui8Data, m_aui8Data, Modulo.m_aui8Data); 00391 this->assign(Modulo); 00392 00393 return *this; 00394 } 00395 00396 /*************************************************************************/ 00404 /*************************************************************************/ 00405 inline TBigInteger<N>& modpow(const TBigInteger<N>& rExp, 00406 const TBigInteger<N>& rMod) 00407 { 00408 TBigInteger<N> Base(*this); 00409 TBigInteger<N> Exp(rExp); 00410 *this = 1; 00411 00412 Uint8 aui8NegMod[N]; 00413 ::memcpy(aui8NegMod, rMod.m_aui8Data, N); 00414 TBigIntegerBase::negate(aui8NegMod, N); 00415 00416 00417 //register Int iLastSignChecked = N-1; 00418 //while(!TBigIntegerBase::isZeroEx(Exp.m_aui8Data, iLastSignChecked)) 00419 while(!Exp.isZero()) 00420 { 00421 if (Exp.m_aui8Data[0] & 1) 00422 { 00423 this->multiply(Base); 00424 mod_internal(rMod.m_aui8Data, aui8NegMod, m_aui8Data); //this->mod(rMod); 00425 } 00426 Base.multiply(Base); 00427 mod_internal(rMod.m_aui8Data, aui8NegMod, Base.m_aui8Data); //Base.mod(rMod); 00428 00429 TBigIntegerBase::shiftRight8Bit(Exp.m_aui8Data, N, 1); 00430 //Slower is Exp.divide(2); 00431 } 00432 return *this; 00433 } 00434 00435 /*************************************************************************/ 00439 /*************************************************************************/ 00440 inline TBigInteger<N>& negate() 00441 { 00442 TBigIntegerBase::negate(m_aui8Data, N); 00443 return *this; 00444 } 00445 00446 /*************************************************************************/ 00450 /*************************************************************************/ 00451 inline void shiftLeft(Int iShift) 00452 { 00453 TBigIntegerBase::shiftLeft(m_aui8Data, N, iShift); 00454 } 00455 00456 /*************************************************************************/ 00460 /*************************************************************************/ 00461 inline void shiftRight(Int iShift) 00462 { 00463 TBigIntegerBase::shiftRight(m_aui8Data, N, iShift); 00464 } 00465 00466 /*************************************************************************/ 00471 /*************************************************************************/ 00472 inline TBigInteger<N>& subtract(const TBigInteger<N>& rParam) 00473 { 00474 return this->add(rParam.getNegated()); 00475 } 00476 00477 /*************************************************************************/ 00482 /*************************************************************************/ 00483 inline TBigInteger<N>& multiply(const TBigInteger<N>& rParam) 00484 { 00485 multiply_internal(rParam.m_aui8Data, m_aui8Data); 00486 return *this; 00487 } 00488 00489 /*************************************************************************/ 00494 /*************************************************************************/ 00495 inline void toByteArray(IByteArray& rData, Int iSize = N) const 00496 { 00497 rData.clear(); 00498 rData.setArray((Int8*)m_aui8Data, iSize); 00499 } 00500 00501 /*************************************************************************/ 00507 /*************************************************************************/ 00508 inline void appendToByteArray(IByteArray& rData, Int iSize = N) const 00509 { 00510 rData.appendArray((Int8*)m_aui8Data, iSize); 00511 } 00512 00513 //operators 00514 /*************************************************************************/ 00517 /*************************************************************************/ 00518 inline TBigInteger<N>& operator=(const TBigInteger<N>& rParam) 00519 { 00520 this->assign(rParam); 00521 return *this; 00522 } 00523 00524 /*************************************************************************/ 00530 /*************************************************************************/ 00531 inline bool operator==(const TBigInteger<N>& rParam) const 00532 { 00533 return (compareTo(rParam) == 0); 00534 } 00535 00536 /*************************************************************************/ 00542 /*************************************************************************/ 00543 inline bool operator!=(const TBigInteger<N>& rParam) const 00544 { 00545 return (compareTo(rParam) != 0); 00546 } 00547 00548 /*************************************************************************/ 00554 /*************************************************************************/ 00555 inline bool operator<(const TBigInteger<N>& rParam) const 00556 { 00557 return (compareTo(rParam) < 0); 00558 } 00559 00560 /*************************************************************************/ 00566 /*************************************************************************/ 00567 inline bool operator>(const TBigInteger<N>& rParam) const 00568 { 00569 return (compareTo(rParam) > 0); 00570 } 00571 00572 /*************************************************************************/ 00575 /*************************************************************************/ 00576 inline TBigInteger<N> operator+(const TBigInteger<N>& rParam) 00577 { 00578 return TBigInteger<N>(*this).add(rParam); 00579 } 00580 00581 /*************************************************************************/ 00584 /*************************************************************************/ 00585 inline TBigInteger<N> operator-(const TBigInteger<N>& rParam) const 00586 { 00587 return TBigInteger<N>(*this).subtract(rParam); 00588 } 00589 00590 /*************************************************************************/ 00593 /*************************************************************************/ 00594 inline TBigInteger<N> operator-() 00595 { 00596 return getNegated(); 00597 } 00598 00599 /*************************************************************************/ 00602 /*************************************************************************/ 00603 inline TBigInteger<N> operator*(const TBigInteger<N>& rParam) const 00604 { 00605 return TBigInteger<N>(*this).multiply(rParam); 00606 } 00607 00608 /*************************************************************************/ 00611 /*************************************************************************/ 00612 inline TBigInteger<N> operator/(const TBigInteger<N>& rParam) const 00613 { 00614 return TBigInteger<N>(*this).divide(rParam); 00615 } 00616 00617 /*************************************************************************/ 00620 /*************************************************************************/ 00621 inline TBigInteger<N> operator%(const TBigInteger<N>& rParam) const 00622 { 00623 return TBigInteger<N>(*this).mod(rParam); 00624 } 00625 00626 protected: 00627 void assign32bit(Uint32 ui64Value, bool bNegative); 00628 void assign64bit(Uint64 ui64Value, bool bNegative); 00629 00630 static void divide_internal(const Uint8* pui8Divisor, 00631 Uint8* pui8Base, 00632 Uint8* pui8Modulo); 00633 static void mod_internal(const Uint8* pui8Divisor, 00634 const Uint8* pui8NegDivisor, 00635 Uint8* pui8Modulo); 00636 static void multiply_internal(const Uint8* pui8Data1, Uint8* pui8Data2); 00637 static void multiply_karatsuba(const Uint8* pui8Data1, 00638 const Uint8* pui8Data2, 00639 Uint8* pui8Result); 00640 static Int compareTo_internal(const Uint8* pui8Data1, const Uint8* pui8Data2); 00641 static Int compareTo_positive(const Uint8* pui8Data1, const Uint8* pui8Data2, Int iSize); 00642 00643 /*************************************************************************/ 00646 /*************************************************************************/ 00647 inline static Int getLastSignPos(const Uint8* pui8Data, Int iSize) 00648 { 00649 register Int iRetval = iSize-1; 00650 while (iRetval > 0 && pui8Data[iRetval] == 0x00) { iRetval--; } 00651 return iRetval; 00652 } 00653 00654 private: 00656 Uint8 m_aui8Data[N]; 00657 }; 00658 00659 //Type defines for large integers 00660 typedef TBigInteger<16> Int128; 00661 typedef TBigInteger<32> Int256; 00662 typedef TBigInteger<64> Int512; 00663 typedef TBigInteger<128> Int1024; 00664 typedef TBigInteger<256> Int2048; 00665 typedef TBigInteger<512> Int4096; 00666 00667 00668 /*****************************************************************************/ 00673 /*****************************************************************************/ 00674 template <int N> void TBigInteger<N>::assign32bit(Uint32 ui32Value, bool bNegative) 00675 { 00676 if (bNegative) 00677 { 00678 ::memset(m_aui8Data, 0xFF, N); 00679 } 00680 else 00681 { 00682 ::memset(m_aui8Data, 0x00, N); 00683 } 00684 00685 m_aui8Data[0] = (Uint8)((ui32Value & 0xFF)); 00686 m_aui8Data[1] = (Uint8)((ui32Value >> 8) & 0xFF); 00687 m_aui8Data[2] = (Uint8)((ui32Value >> 16) & 0xFF); 00688 m_aui8Data[3] = (Uint8)((ui32Value >> 24) & 0xFF); 00689 } 00690 00691 /*****************************************************************************/ 00696 /*****************************************************************************/ 00697 template <int N> void TBigInteger<N>::assign64bit(Uint64 ui64Value, bool bNegative) 00698 { 00699 if (bNegative) 00700 { 00701 ::memset(m_aui8Data, 0xFF, N); 00702 } 00703 else 00704 { 00705 ::memset(m_aui8Data, 0x00, N); 00706 } 00707 00708 m_aui8Data[0] = (Uint8)((ui64Value & 0xFF)); 00709 m_aui8Data[1] = (Uint8)((ui64Value >> 8) & 0xFF); 00710 m_aui8Data[2] = (Uint8)((ui64Value >> 16) & 0xFF); 00711 m_aui8Data[3] = (Uint8)((ui64Value >> 24) & 0xFF); 00712 m_aui8Data[4] = (Uint8)((ui64Value >> 32) & 0xFF); 00713 m_aui8Data[5] = (Uint8)((ui64Value >> 40) & 0xFF); 00714 m_aui8Data[6] = (Uint8)((ui64Value >> 48) & 0xFF); 00715 m_aui8Data[7] = (Uint8)((ui64Value >> 56) & 0xFF); 00716 } 00717 00718 /*************************************************************************/ 00726 /*************************************************************************/ 00727 /*static*/ template <int N> Int TBigInteger<N>::compareTo_internal(const Uint8* pui8Data1, const Uint8* pui8Data2) 00728 { 00729 register Int iRetval = 0; 00730 00731 Int iFactorA = TBigIntegerBase::isNegative(pui8Data1, N) ? -1 : 1; 00732 Int iFactorB = TBigIntegerBase::isNegative(pui8Data2, N) ? -1 : 1; 00733 00734 if (iFactorA < iFactorB) 00735 { 00736 iRetval = -1; 00737 } 00738 else if (iFactorA > iFactorB) 00739 { 00740 iRetval = 1; 00741 } 00742 else //iFactorA == iFactorB 00743 { 00744 //For negative numbers 00745 // calculates the complement of number 1 and 2 00746 if (iFactorA == -1) // then also iFactorB is -1 00747 { 00748 Uint8 aui8Buffer1[N]; 00749 Uint8 aui8Buffer2[N]; 00750 ::memcpy(aui8Buffer1, pui8Data1, N); 00751 ::memcpy(aui8Buffer2, pui8Data2, N); 00752 00753 TBigIntegerBase::negate(aui8Buffer1, N); 00754 TBigIntegerBase::negate(aui8Buffer2, N); 00755 00756 iRetval = compareTo_internal(aui8Buffer1, aui8Buffer2) * -1; 00757 } 00758 00759 // for positive numbers 00760 else 00761 { 00762 register Int i; 00763 for (i = N-1; iRetval == 0 && i >= 0; i--) 00764 { 00765 if (pui8Data1[i] < pui8Data2[i]) 00766 { 00767 iRetval = -1; 00768 } 00769 else if (pui8Data1[i] > pui8Data2[i]) 00770 { 00771 iRetval = 1; 00772 } 00773 } //end for 00774 } 00775 } //iFactorA == iFactorB 00776 00777 return iRetval; 00778 } 00779 00780 /*************************************************************************/ 00791 /*************************************************************************/ 00792 /*static*/ template <int N> Int TBigInteger<N>::compareTo_positive(const Uint8* pui8Data1, const Uint8* pui8Data2, Int iSize) 00793 { 00794 register Int iRetval = 0; 00795 register Int i; 00796 for (i = iSize-1; iRetval == 0 && i >= 0; i--) 00797 { 00798 if (pui8Data1[i] < pui8Data2[i]) 00799 { 00800 iRetval = -1; 00801 } 00802 else if (pui8Data1[i] > pui8Data2[i]) 00803 { 00804 iRetval = 1; 00805 } 00806 } //end for 00807 return iRetval; 00808 } 00809 00810 /*************************************************************************/ 00816 /*************************************************************************/ 00817 /*static*/ template <int N> void TBigInteger<N>::divide_internal(const Uint8* pui8Divisor, 00818 Uint8* pui8Base, 00819 Uint8* pui8Modulo) 00820 { 00821 if (!TBigIntegerBase::isZero(pui8Divisor, N)) 00822 { 00823 bool bNegativeDiv = TBigIntegerBase::isNegative(pui8Divisor, N); 00824 bool bNegativeBase = TBigIntegerBase::isNegative(pui8Base, N); 00825 00826 Uint8 aui8NegDiv[N]; 00827 ::memcpy(aui8NegDiv, pui8Divisor, N); 00828 TBigIntegerBase::negate(aui8NegDiv, N); 00829 00830 Uint8* pui8DivPos = (Uint8*)pui8Divisor; 00831 Uint8* pui8DivNeg = (Uint8*)&aui8NegDiv; 00832 if (bNegativeDiv) 00833 { 00834 pui8DivNeg = (Uint8*)pui8Divisor; 00835 pui8DivPos = (Uint8*)&aui8NegDiv; 00836 } 00837 00838 //fill the modulo with base 00839 ::memcpy(pui8Modulo, pui8Base, N); 00840 if (bNegativeBase) 00841 { 00842 TBigIntegerBase::negate(pui8Modulo, N); 00843 } 00844 00845 //clear base, and work with modulo 00846 memset(pui8Base, 0x00, N); 00847 00848 register Int iBN = getLastSignPos(pui8Modulo, N); 00849 register Int iDN = getLastSignPos(pui8DivPos, N); 00850 register Int iRN = iBN - iDN; 00851 register Int iCarry = 0; 00852 while(iDN <= iBN) 00853 { 00854 Uint8* pui8TempBase = pui8Modulo + iBN - iDN; 00855 00856 register Uint uiCount = 0; 00857 while(compareTo_positive(pui8DivPos, pui8TempBase, iDN + 1 + iCarry) <= 0) 00858 { 00859 TBigIntegerBase::add(pui8DivNeg, N, pui8TempBase, N - iBN + iDN); 00860 uiCount++; 00861 } 00862 pui8Base[iRN] = (Uint8)uiCount; 00863 iBN--; 00864 iRN--; 00865 00866 if (iCarry == 0) { iCarry = 1; } 00867 } 00868 00869 /* This code is VERY slow. 00870 Uint uiCount = 0; 00871 while(compareTo_internal(pui8DivPos, pui8Modulo) <= 0) 00872 { 00873 add_internal(pui8DivNeg, N, pui8Modulo); 00874 uiCount++; 00875 00876 if (uiCount == 0x0FFFFFFF) 00877 { 00878 add_internal((Uint8*)&uiCount, sizeof(Uint), pui8Base); 00879 uiCount = 0; 00880 } 00881 } 00882 add_internal((Uint8*)&uiCount, sizeof(Uint), pui8Base); 00883 */ 00884 00885 if ((!bNegativeDiv && bNegativeBase) || (bNegativeDiv && !bNegativeBase)) 00886 { 00887 TBigIntegerBase::negate(pui8Base, N); 00888 TBigIntegerBase::negate(pui8Modulo, N); 00889 00890 //make sure the modulo is not negative 00891 // -11 mod 4 = -3 00892 // -> -11 mod 4 = 1 00893 TBigIntegerBase::add(pui8Divisor, N, pui8Modulo, N); 00894 } 00895 } 00896 } 00897 00898 /*****************************************************************************/ 00907 /*****************************************************************************/ 00908 /*static*/ template <int N> void TBigInteger<N>::mod_internal(const Uint8* pui8Divisor, 00909 const Uint8* pui8NegDivisor, 00910 Uint8* pui8Modulo) 00911 { 00912 if (!TBigIntegerBase::isZero(pui8Divisor, N)) 00913 { 00914 bool bNegativeDiv = TBigIntegerBase::isNegative(pui8Divisor, N); 00915 bool bNegativeBase = TBigIntegerBase::isNegative(pui8Modulo, N); 00916 00917 Uint8* pui8DivPos = (Uint8*)pui8Divisor; 00918 Uint8* pui8DivNeg = (Uint8*)pui8NegDivisor; 00919 if (bNegativeDiv) 00920 { 00921 pui8DivNeg = (Uint8*)pui8Divisor; 00922 pui8DivPos = (Uint8*)pui8NegDivisor; 00923 } 00924 00925 if (bNegativeBase) 00926 { 00927 TBigIntegerBase::negate(pui8Modulo, N); 00928 } 00929 00930 register Int iBN = getLastSignPos(pui8Modulo, N); 00931 register Int iDN = getLastSignPos(pui8DivPos, N); 00932 register Int iRN = iBN - iDN; 00933 register Int iCarry = 0; 00934 while(iDN <= iBN) 00935 { 00936 Uint8* pui8TempBase = pui8Modulo + iBN - iDN; 00937 00938 while(compareTo_positive(pui8DivPos, pui8TempBase, iDN + 1 + iCarry) <= 0) 00939 { 00940 TBigIntegerBase::add(pui8DivNeg, N, pui8TempBase, N - iBN + iDN); 00941 } 00942 iBN--; 00943 iRN--; 00944 00945 if (iCarry == 0) { iCarry = 1; } 00946 } 00947 00948 if ((!bNegativeDiv && bNegativeBase) || (bNegativeDiv && !bNegativeBase)) 00949 { 00950 TBigIntegerBase::negate(pui8Modulo, N); 00951 } 00952 } 00953 } 00954 00955 /*************************************************************************/ 00960 /*************************************************************************/ 00961 /*static*/ template <int N> void TBigInteger<N>::multiply_internal(const Uint8* pui8Data1, 00962 Uint8* pui8Data2) 00963 { 00964 Uint8 aui8A[N]; 00965 Uint8 aui8B[N]; 00966 Uint8 aui8Temp[2*N]; 00967 00968 ::memcpy(aui8A, pui8Data1, N); 00969 ::memcpy(aui8B, pui8Data2, N); 00970 ::memset(aui8Temp, 0x00, 2*N); 00971 00972 //The following algorithm works only with positive numbers 00973 // therefore we have to get the complement of the negative values first 00974 Int iSign = 1; 00975 if (TBigIntegerBase::isNegative(aui8A, N)) 00976 { 00977 TBigIntegerBase::negate(aui8A, N); 00978 iSign *= -1; 00979 } 00980 if (TBigIntegerBase::isNegative(aui8B, N)) 00981 { 00982 TBigIntegerBase::negate(aui8B, N); 00983 iSign *= -1; 00984 } 00985 00986 register Int iLastPosA = getLastSignPos(aui8A, N); 00987 register Int iLastPosB = getLastSignPos(aui8B, N); 00988 00989 //for larger numbers than 3200 bits use karatsuba algorithm 00990 if (iLastPosA > 400 || iLastPosB > 400) 00991 { 00992 multiply_karatsuba(aui8A, aui8B, aui8Temp); 00993 } 00994 else 00995 { 00996 iLastPosA += 2; 00997 iLastPosB += 2; 00998 if (iLastPosA > N) 00999 { 01000 iLastPosA = N; 01001 } 01002 if (iLastPosB > N) 01003 { 01004 iLastPosB = N; 01005 } 01006 TBigIntegerBase::multiply(aui8A, iLastPosA, aui8B, iLastPosB, aui8Temp); 01007 } 01008 01009 if (iSign == -1) 01010 { 01011 TBigIntegerBase::negate(aui8Temp, N); 01012 } 01013 01014 ::memcpy(pui8Data2, aui8Temp, N); 01015 } 01016 01017 /*****************************************************************************/ 01029 /*****************************************************************************/ 01030 /*static*/ template <int N> void TBigInteger<N>::multiply_karatsuba(const Uint8* pui8Data1, 01031 const Uint8* pui8Data2, 01032 Uint8* pui8Result) 01033 { 01034 Int iSize1 = getLastSignPos(pui8Data1, N)+1; 01035 Int iSize2 = getLastSignPos(pui8Data2, N)+1; 01036 01037 //get the max size of the numbers 01038 register Int iN = iSize1 > iSize2 ? iSize1 : iSize2; 01039 01040 //If the number is smaller than 3200bits -> use the conventional 01041 // multiplication 01042 if (iN < 400) 01043 { 01044 iSize1++; 01045 iSize2++; 01046 TBigIntegerBase::multiply(pui8Data1, iSize1, pui8Data2, iSize2, pui8Result); 01047 } 01048 else 01049 { 01050 //convert to numbers of bits (*8) 01051 iN <<= 3; 01052 01053 // divide into two numbers: x = xH * b^n + xL , y = yH * b^n + yL 01054 iN /= 2; 01055 01056 // X value 01057 Uint8 pui8XH[N]; 01058 ::memcpy(pui8XH, pui8Data1, N); 01059 TBigIntegerBase::shiftRight(pui8XH, iSize1, iN); // only the size of pui8Data1 must be shift 01060 01061 Uint8 pui8XL[N]; 01062 ::memcpy(pui8XL, pui8XH, N); 01063 TBigIntegerBase::shiftLeft(pui8XL, N, iN); 01064 TBigIntegerBase::negate(pui8XL, N); 01065 TBigIntegerBase::add(pui8Data1, iSize1, pui8XL, N); // only the size of pui8Data1 must be added 01066 01067 // Y value 01068 Uint8 pui8YH[N]; 01069 ::memcpy(pui8YH, pui8Data2, N); 01070 TBigIntegerBase::shiftRight(pui8YH, iSize2, iN); // only the size of pui8Data2 must be shift 01071 01072 Uint8 pui8YL[N]; 01073 ::memcpy(pui8YL, pui8YH, N); 01074 TBigIntegerBase::shiftLeft(pui8YL, N, iN); 01075 TBigIntegerBase::negate(pui8YL, N); 01076 TBigIntegerBase::add(pui8Data2, iSize2, pui8YL, N); // only the size of pui8Data2 must be added 01077 01078 Uint8* pui8P1 = pui8Result; 01079 Uint8 pui8P2[2*N]; 01080 Uint8 pui8P3[2*N]; 01081 //::memset(pui8P1, 0x00, 2*N); 01082 ::memset(pui8P2, 0x00, 2*N); 01083 ::memset(pui8P3, 0x00, 2*N); 01084 01085 // calculate the single numbers 01086 multiply_karatsuba(pui8XH, pui8YH, pui8P1); 01087 multiply_karatsuba(pui8XL, pui8YL, pui8P2); 01088 01089 TBigIntegerBase::add(pui8XH, iSize1, pui8XL, N); 01090 TBigIntegerBase::add(pui8YH, iSize2, pui8YL, N); 01091 multiply_karatsuba(pui8XL, pui8YL, pui8P3); 01092 01093 01094 // Put them together 01095 Uint8 pui8P1_neg[N]; 01096 Uint8 pui8P2_neg[N]; 01097 ::memcpy(pui8P1_neg, pui8P1, N); 01098 ::memcpy(pui8P2_neg, pui8P2, N); 01099 TBigIntegerBase::negate(pui8P1_neg, N); 01100 TBigIntegerBase::negate(pui8P2_neg, N); 01101 01102 TBigIntegerBase::add(pui8P1_neg, N, pui8P3, N); 01103 TBigIntegerBase::add(pui8P2_neg, N, pui8P3, N); 01104 TBigIntegerBase::shiftLeft(pui8P3, N, iN); 01105 01106 TBigIntegerBase::shiftLeft(pui8P1, N, 2*iN); 01107 TBigIntegerBase::add(pui8P2, N, pui8P1, N); 01108 TBigIntegerBase::add(pui8P3, N, pui8P1, N); 01109 01110 //pui8P1 is the result. Because it points the the result buffer 01111 // we have to do nothing further here 01112 } 01113 } 01114 01115 END_NAMESPACE_Zeus 01116 01117 #endif 01118