"L. Spiro Engine"
|
00001 00020 #ifndef __LSSTD_LARGEINTEGER_H__ 00021 #define __LSSTD_LARGEINTEGER_H__ 00022 00023 #include "../LSSTDStandardLib.h" 00024 00025 #pragma warning( push ) 00026 00027 // warning C4127: conditional expression is constant 00028 #pragma warning( disable : 4127 ) 00029 00030 namespace lsstd { 00031 00035 enum LSSTD_LARGE_INTEGER_EXCEPTIONS { 00036 LSSTD_LIE_OVERFLOW, 00037 LSSTD_LIE_DIVISIONBYZERO, 00038 LSSTD_LIE_INVALIDCONVERSION, 00039 }; 00040 00051 template <unsigned _uMaxDigits = 1024UL> 00052 class CLargeInteger { 00053 public : 00054 // == Various constructors. 00058 LSE_CALL CLargeInteger() : 00059 m_ui32UsedDigits( 1UL ) { 00060 CStd::MemSet( m_ui32Digits, 0, sizeof( m_ui32Digits ) ); 00061 } 00062 00068 LSE_CALL CLargeInteger( const CLargeInteger<_uMaxDigits> &_liOther ) : 00069 m_ui32UsedDigits( _liOther.m_ui32UsedDigits ) { 00070 CStd::MemCpy( m_ui32Digits, _liOther.m_ui32Digits, sizeof( m_ui32Digits ) ); 00071 } 00072 00078 LSE_CALL CLargeInteger( LSINT64 _i64Value ) { 00079 LSUINT32 ui32Pos = 0UL; 00080 while ( _i64Value && ui32Pos < _uMaxDigits ) { 00081 m_ui32Digits[ui32Pos++] = static_cast<LSUINT32>(_i64Value & 0xFFFFFFFFULL); 00082 _i64Value >>= 32ULL; 00083 } 00084 m_ui32UsedDigits = ui32Pos; 00085 // Fill the rest of our buffer with 0's. 00086 for ( ; ui32Pos < _uMaxDigits; ++ui32Pos ) { 00087 m_ui32Digits[ui32Pos] = 0; 00088 } 00089 00090 if ( m_ui32UsedDigits == 0UL ) { 00091 m_ui32UsedDigits = 1UL; 00092 } 00093 } 00094 00100 LSE_CALL CLargeInteger( LSUINT64 _ui64Value ) { 00101 LSUINT32 ui32Pos = 0UL; 00102 while ( _ui64Value ) { 00103 m_ui32Digits[ui32Pos++] = static_cast<LSUINT32>(_ui64Value & 0xFFFFFFFFULL); 00104 _ui64Value >>= 32ULL; 00105 } 00106 m_ui32UsedDigits = ui32Pos; 00107 // Fill the rest of our buffer with 0's. 00108 for ( ; ui32Pos < _uMaxDigits; ++ui32Pos ) { 00109 m_ui32Digits[ui32Pos] = 0; 00110 } 00111 00112 if ( m_ui32UsedDigits == 0UL ) { 00113 m_ui32UsedDigits = 1UL; 00114 } 00115 } 00116 00122 LSE_CALL CLargeInteger( LSINT32 _i32Value ) { 00123 LSUINT32 ui32Pos = 0UL; 00124 LSINT64 i64Val = _i32Value; 00125 while ( i64Val && ui32Pos < _uMaxDigits ) { 00126 m_ui32Digits[ui32Pos++] = static_cast<LSUINT32>(i64Val & 0xFFFFFFFFULL); 00127 i64Val >>= 32LL; 00128 } 00129 m_ui32UsedDigits = ui32Pos; 00130 // Fill the rest of our buffer with 0's. 00131 for ( ; ui32Pos < _uMaxDigits; ++ui32Pos ) { 00132 m_ui32Digits[ui32Pos] = 0UL; 00133 } 00134 00135 if ( m_ui32UsedDigits == 0UL ) { 00136 m_ui32UsedDigits = 1UL; 00137 } 00138 } 00139 00145 LSE_CALL CLargeInteger( LSUINT32 _ui32Value ) { 00146 LSUINT32 ui32Pos = 0UL; 00147 00148 m_ui32Digits[ui32Pos++] = static_cast<LSUINT32>(_ui32Value & 0xFFFFFFFFULL); 00149 m_ui32UsedDigits = ui32Pos; 00150 // Fill the rest of our buffer with 0's. 00151 for ( ; ui32Pos < _uMaxDigits; ++ui32Pos ) { 00152 m_ui32Digits[ui32Pos] = 0; 00153 } 00154 } 00155 00162 LSE_CALL CLargeInteger( const LSUINT32 * _pui8Array, LSUINT32 _ui32Length ) : 00163 m_ui32UsedDigits( _ui32Length ) { 00164 if ( m_ui32UsedDigits > _uMaxDigits ) { 00165 throw LSSTD_LIE_OVERFLOW; 00166 } 00167 00168 for ( LSINT32 I = static_cast<LSINT32>(m_ui32UsedDigits) - 1, J = 0; I >= 0; --I, ++J ) { 00169 m_ui32Digits[J] = _pui8Array[I]; 00170 } 00171 while ( m_ui32UsedDigits > 1UL && m_ui32Digits[m_ui32UsedDigits-1UL] == 0 ) { 00172 --m_ui32UsedDigits; 00173 } 00174 for ( LSUINT32 I = m_ui32UsedDigits; I < _uMaxDigits; ++I ) { 00175 m_ui32Digits[I] = 0; 00176 } 00177 } 00178 00179 00180 // == Operators. 00188 CLargeInteger<_uMaxDigits> LSE_CALL operator + ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00189 CLargeInteger<_uMaxDigits> liReturn; 00190 Add( (*this), _liOp, liReturn ); 00191 00192 return liReturn; 00193 } 00194 00202 CLargeInteger<_uMaxDigits> LSE_CALL operator - ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00203 CLargeInteger<_uMaxDigits> liReturn; 00204 Subtract( (*this), _liOp, liReturn ); 00205 00206 return liReturn; 00207 } 00208 00216 CLargeInteger<_uMaxDigits> LSE_CALL operator * ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00217 CLargeInteger<_uMaxDigits> liReturn; 00218 Multiply( (*this), _liOp, liReturn ); 00219 00220 return liReturn; 00221 } 00222 00230 CLargeInteger<_uMaxDigits> LSE_CALL operator *= ( const CLargeInteger<_uMaxDigits> &_liOp ) { 00231 CLargeInteger<_uMaxDigits> liReturn; 00232 Multiply( (*this), _liOp, liReturn ); 00233 (*this) = liReturn; 00234 00235 return (*this); 00236 } 00237 00245 CLargeInteger<_uMaxDigits> LSE_CALL operator / ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00246 CLargeInteger<_uMaxDigits> liReturn; 00247 Divide( (*this), _liOp, liReturn ); 00248 00249 return liReturn; 00250 } 00251 00259 CLargeInteger<_uMaxDigits> LSE_CALL operator /= ( const CLargeInteger<_uMaxDigits> &_liOp ) { 00260 CLargeInteger<_uMaxDigits> liReturn; 00261 Divide( (*this), _liOp, liReturn ); 00262 (*this) = liReturn; 00263 00264 return (*this); 00265 } 00266 00274 CLargeInteger<_uMaxDigits> LSE_CALL operator % ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00275 CLargeInteger<_uMaxDigits> liReturn; 00276 Modulus( (*this), _liOp, liReturn ); 00277 00278 return liReturn; 00279 } 00280 00286 CLargeInteger<_uMaxDigits> LSE_CALL operator - () const { 00287 CLargeInteger<_uMaxDigits> liReturn; 00288 Negate( (*this), liReturn ); 00289 00290 return liReturn; 00291 } 00292 00299 CLargeInteger<_uMaxDigits> LSE_CALL operator = ( const CLargeInteger<_uMaxDigits> &_liOp ) { 00300 m_ui32UsedDigits = _liOp.m_ui32UsedDigits; 00301 CStd::MemCpy( m_ui32Digits, _liOp.m_ui32Digits, sizeof( m_ui32Digits ) ); 00302 00303 return (*this); 00304 } 00305 00312 CLargeInteger<_uMaxDigits> LSE_CALL operator << ( LSUINT32 _ui32Shift ) const { 00313 CLargeInteger<_uMaxDigits> liReturn( (*this) ); 00314 liReturn.m_ui32UsedDigits = ShiftLeft( liReturn.GetBytes(), liReturn.m_ui32UsedDigits, _ui32Shift ); 00315 00316 return liReturn; 00317 } 00318 00325 CLargeInteger<_uMaxDigits> & LSE_CALL operator <<= ( LSUINT32 _ui32Shift ) { 00326 m_ui32UsedDigits = ShiftLeft( GetBytes(), m_ui32UsedDigits, _ui32Shift ); 00327 00328 return (*this); 00329 } 00330 00337 CLargeInteger<_uMaxDigits> LSE_CALL operator >> ( LSUINT32 _ui32Shift ) const { 00338 CLargeInteger<_uMaxDigits> liReturn( (*this) ); 00339 liReturn.m_ui32UsedDigits = ShiftRight( liReturn.GetBytes(), liReturn.m_ui32UsedDigits, _ui32Shift ); 00340 liReturn.m_ui32UsedDigits = CStd::Max<LSUINT32>( liReturn.m_ui32UsedDigits, 1UL ); 00341 00342 // Fix sign bits on negative numbers. 00343 if ( m_ui32Digits[_uMaxDigits-1UL] & 0x80000000UL ) { 00344 for ( LSUINT32 I = _uMaxDigits - 1UL; I >= liReturn.m_ui32UsedDigits; --I ) { 00345 liReturn.m_ui32Digits[I] = 0xFFFFFFFF; 00346 } 00347 00348 LSUINT32 ui32Mask = 0x80000000UL; 00349 for ( LSUINT32 I = 0UL; I < 32UL; ++I ) { 00350 if ( liReturn.m_ui32Digits[liReturn.m_ui32UsedDigits-1] & ui32Mask ) { 00351 break; 00352 } 00353 liReturn.m_ui32Digits[liReturn.m_ui32UsedDigits-1] |= ui32Mask; 00354 ui32Mask >>= 1UL; 00355 } 00356 liReturn.m_ui32UsedDigits = _uMaxDigits; 00357 } 00358 00359 return liReturn; 00360 } 00361 00368 CLargeInteger<_uMaxDigits> & LSE_CALL operator >>= ( LSUINT32 _ui32Shift ) { 00369 m_ui32UsedDigits = ShiftRight( GetBytes(), m_ui32UsedDigits, _ui32Shift ); 00370 m_ui32UsedDigits = CStd::Max<LSUINT32>( m_ui32UsedDigits, 1UL ); 00371 00372 // Fix sign bits on negative numbers. 00373 if ( m_ui32Digits[_uMaxDigits-1UL] & 0x80000000UL ) { 00374 for ( LSUINT32 I = _uMaxDigits - 1UL; I >= m_ui32UsedDigits; --I ) { 00375 m_ui32Digits[I] = 0xFFFFFFFF; 00376 } 00377 00378 LSUINT32 ui32Mask = 0x80000000UL; 00379 for ( LSUINT32 I = 0UL; I < 32UL; ++I ) { 00380 if ( m_ui32Digits[m_ui32UsedDigits-1] & ui32Mask ) { 00381 break; 00382 } 00383 m_ui32Digits[m_ui32UsedDigits-1] |= ui32Mask; 00384 ui32Mask >>= 1UL; 00385 } 00386 m_ui32UsedDigits = _uMaxDigits; 00387 } 00388 00389 return (*this); 00390 } 00391 00398 CLargeInteger<_uMaxDigits> LSE_CALL operator & ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00399 CLargeInteger<_uMaxDigits> liResult; 00400 liResult.m_ui32UsedDigits = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00401 for ( LSUINT32 I = liResult.m_ui32UsedDigits; I--; ) { 00402 liResult.m_ui32Digits[I] = m_ui32Digits[I] & _liOp.m_ui32Digits[I]; 00403 } 00404 00405 // Remove opening 0's. 00406 while ( liResult.m_ui32UsedDigits > 1UL && liResult.m_ui32Digits[liResult.m_ui32UsedDigits-1UL] == 0 ) { 00407 --liResult.m_ui32UsedDigits; 00408 } 00409 return liResult; 00410 } 00411 00418 CLargeInteger<_uMaxDigits> & LSE_CALL operator &= ( const CLargeInteger<_uMaxDigits> &_liOp ) { 00419 m_ui32UsedDigits = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00420 for ( LSUINT32 I = m_ui32UsedDigits; I--; ) { 00421 m_ui32Digits[I] = m_ui32Digits[I] & _liOp.m_ui32Digits[I]; 00422 } 00423 00424 // Remove opening 0's. 00425 while ( m_ui32UsedDigits > 1UL && m_ui32Digits[m_ui32UsedDigits-1UL] == 0 ) { 00426 --m_ui32UsedDigits; 00427 } 00428 return (*this); 00429 } 00430 00437 CLargeInteger<_uMaxDigits> LSE_CALL operator | ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00438 CLargeInteger<_uMaxDigits> liResult; 00439 liResult.m_ui32UsedDigits = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00440 for ( LSUINT32 I = liResult.m_ui32UsedDigits; I--; ) { 00441 liResult.m_ui32Digits[I] = m_ui32Digits[I] | _liOp.m_ui32Digits[I]; 00442 } 00443 00444 // Remove opening 0's. 00445 while ( liResult.m_ui32UsedDigits > 1UL && liResult.m_ui32Digits[liResult.m_ui32UsedDigits-1UL] == 0 ) { 00446 --liResult.m_ui32UsedDigits; 00447 } 00448 return liResult; 00449 } 00450 00457 CLargeInteger<_uMaxDigits> & LSE_CALL operator |= ( const CLargeInteger<_uMaxDigits> &_liOp ) { 00458 m_ui32UsedDigits = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00459 for ( LSUINT32 I = m_ui32UsedDigits; I--; ) { 00460 m_ui32Digits[I] = m_ui32Digits[I] | _liOp.m_ui32Digits[I]; 00461 } 00462 00463 // Remove opening 0's. 00464 while ( m_ui32UsedDigits > 1UL && m_ui32Digits[m_ui32UsedDigits-1UL] == 0 ) { 00465 --m_ui32UsedDigits; 00466 } 00467 return (*this); 00468 } 00469 00476 CLargeInteger<_uMaxDigits> LSE_CALL operator ^ ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00477 CLargeInteger<_uMaxDigits> liResult; 00478 liResult.m_ui32UsedDigits = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00479 for ( LSUINT32 I = liResult.m_ui32UsedDigits; I--; ) { 00480 liResult.m_ui32Digits[I] = m_ui32Digits[I] ^ _liOp.m_ui32Digits[I]; 00481 } 00482 00483 // Remove opening 0's. 00484 while ( liResult.m_ui32UsedDigits > 1UL && liResult.m_ui32Digits[liResult.m_ui32UsedDigits-1UL] == 0 ) { 00485 --liResult.m_ui32UsedDigits; 00486 } 00487 return liResult; 00488 } 00489 00496 CLargeInteger<_uMaxDigits> & LSE_CALL operator ^= ( const CLargeInteger<_uMaxDigits> &_liOp ) { 00497 m_ui32UsedDigits = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00498 for ( LSUINT32 I = m_ui32UsedDigits; I--; ) { 00499 m_ui32Digits[I] = m_ui32Digits[I] ^ _liOp.m_ui32Digits[I]; 00500 } 00501 00502 // Remove opening 0's. 00503 while ( m_ui32UsedDigits > 1UL && m_ui32Digits[m_ui32UsedDigits-1UL] == 0 ) { 00504 --m_ui32UsedDigits; 00505 } 00506 return (*this); 00507 } 00508 00515 bool LSE_CALL operator > ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00516 LSINT32 i32Pos = _uMaxDigits - 1; 00517 00518 if ( (m_ui32Digits[i32Pos] & 0x80000000UL) && !(_liOp.m_ui32Digits[i32Pos] & 0x80000000UL) ) { 00519 return false; 00520 } 00521 if ( !(m_ui32Digits[i32Pos] & 0x80000000UL) && (_liOp.m_ui32Digits[i32Pos] & 0x80000000UL) ) { 00522 return true; 00523 } 00524 00525 LSUINT32 ui32Len = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00526 // Skip past all digits that are the same. 00527 for ( i32Pos = static_cast<LSINT32>(ui32Len) - 1; i32Pos >= 0 && m_ui32Digits[i32Pos] == _liOp.m_ui32Digits[i32Pos]; --i32Pos ) {} 00528 00529 // If we found a different digit. 00530 if ( i32Pos >= 0 ) { 00531 return m_ui32Digits[i32Pos] > _liOp.m_ui32Digits[i32Pos]; 00532 } 00533 00534 // They are the same. 00535 return false; 00536 } 00537 00544 bool LSE_CALL operator < ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00545 LSINT32 i32Pos = _uMaxDigits - 1; 00546 00547 if ( (m_ui32Digits[i32Pos] & 0x80000000UL) && !(_liOp.m_ui32Digits[i32Pos] & 0x80000000UL) ) { 00548 return true; 00549 } 00550 if ( !(m_ui32Digits[i32Pos] & 0x80000000UL) && (_liOp.m_ui32Digits[i32Pos] & 0x80000000UL) ) { 00551 return false; 00552 } 00553 00554 LSUINT32 ui32Len = CStd::Max( m_ui32UsedDigits, _liOp.m_ui32UsedDigits ); 00555 // Skip past all digits that are the same. 00556 for ( i32Pos = static_cast<LSINT32>(ui32Len) - 1; i32Pos >= 0 && m_ui32Digits[i32Pos] == _liOp.m_ui32Digits[i32Pos]; --i32Pos ) {} 00557 00558 // If we found a different digit. 00559 if ( i32Pos >= 0 ) { 00560 return m_ui32Digits[i32Pos] < _liOp.m_ui32Digits[i32Pos]; 00561 } 00562 00563 // They are the same. 00564 return false; 00565 } 00566 00573 bool LSE_CALL operator == ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00574 if ( m_ui32UsedDigits != _liOp.m_ui32UsedDigits ) { return false; } 00575 return CStd::MemCmpF( m_ui32Digits, _liOp.m_ui32Digits, sizeof( m_ui32Digits[0] ) * m_ui32UsedDigits ) != 0; 00576 } 00577 00584 bool LSE_CALL operator != ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00585 if ( m_ui32UsedDigits != _liOp.m_ui32UsedDigits ) { return true; } 00586 return !CStd::MemCmpF( m_ui32Digits, _liOp.m_ui32Digits, sizeof( m_ui32Digits[0] ) * m_ui32UsedDigits ); 00587 } 00588 00595 bool LSE_CALL operator >= ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00596 return (*this) > _liOp || (*this) == _liOp; 00597 } 00598 00605 bool LSE_CALL operator <= ( const CLargeInteger<_uMaxDigits> &_liOp ) const { 00606 return (*this) < _liOp || (*this) == _liOp; 00607 } 00608 00609 00610 // == Functions. 00617 LSUINT64 LSE_CALL GetAs64bitUInt() const { 00618 if ( m_ui32UsedDigits > sizeof( LSUINT64 ) ) { 00619 throw LSSTD_LIE_INVALIDCONVERSION; 00620 } 00621 LSUINT64 ui64Ret = 0ULL; 00622 CStd::MemCpy( &ui64Ret, m_ui32Digits, CStd::Min( sizeof( ui64Ret ), m_ui32UsedDigits * sizeof( LSUINT32 ) ) ); 00623 return ui64Ret; 00624 } 00625 00632 LSUINT32 LSE_CALL GetAs32bitUInt() const { 00633 if ( m_ui32UsedDigits > sizeof( LSUINT32 ) ) { 00634 throw LSSTD_LIE_INVALIDCONVERSION; 00635 } 00636 LSUINT32 ui32Ret = 0UL; 00637 CStd::MemCpy( &ui32Ret, m_ui32Digits, CStd::Min<LSUINT32>( sizeof( ui32Ret ), m_ui32UsedDigits * sizeof( LSUINT32 ) ) ); 00638 return ui32Ret; 00639 } 00640 00646 LSUINT32 * LSE_CALL GetBytes() { 00647 return m_ui32Digits; 00648 } 00649 00655 LSUINT32 LSE_CALL GetLength() const { 00656 return m_ui32UsedDigits; 00657 } 00658 00664 LSVOID LSE_CALL SetLength( LSUINT32 _ui32Length ) { 00665 m_ui32UsedDigits = _ui32Length; 00666 } 00667 00678 template <typename _tType> 00679 LSUINT32 LSE_CALL ToString( _tType * _ptString, LSUINT32 _ui32MaxLen, LSUINT32 _ui32Radix ) { 00680 if ( _ptString && !_ui32MaxLen ) { 00681 // There is a string but there is no room to put anything into it. 00682 return 0UL; 00683 } 00684 LSBOOL bNegative = (m_ui32Digits[_uMaxDigits-1UL] & 0x80000000UL) != 0; 00685 00686 CLargeInteger<_uMaxDigits> liNewVal = bNegative ? -(*this) : (*this); 00687 00688 if ( bNegative ) { 00689 if ( _ptString ) { 00690 // Sanity check was done above. 00691 (*_ptString++) = '-'; 00692 --_ui32MaxLen; 00693 } 00694 } 00695 00696 00697 // Get the actual number of digits. There is always at least one. 00698 LSUINT32 ui32Len = 0; 00699 CLargeInteger<_uMaxDigits> liNewValCopy = liNewVal; 00700 while ( true ) { 00701 liNewValCopy /= _ui32Radix; 00702 if ( liNewValCopy == 0ULL ) { break; } 00703 ++ui32Len; 00704 } 00705 00706 // Sanity check. 00707 if ( !_ptString ) { 00708 // We only need to return the length of the string needed, including the NULL terminator. 00709 return (ui32Len + 1UL) + static_cast<LSUINT32>(bNegative) + 1UL; 00710 } 00711 00712 // Copy the characters from the end to the front. 00713 liNewValCopy = liNewVal; 00714 LSUINT32 ui32ThisLen = ui32Len; 00715 for ( LSUINT32 I = 0; I <= ui32Len; ++I ) { 00716 LSUINT32 ui32This = (liNewValCopy % _ui32Radix).GetAs32bitUInt(); 00717 _tType tThisChar = static_cast<_tType>(ui32This + '0'); 00718 if ( tThisChar > '9' ) { 00719 // Radix and number are both greater than 10. 00720 tThisChar = static_cast<_tType>((ui32This - 10) + 'A'); 00721 } 00722 if ( ui32ThisLen < _ui32MaxLen ) { 00723 _ptString[ui32ThisLen--] = tThisChar; 00724 } 00725 liNewValCopy /= _ui32Radix; 00726 } 00727 00728 00729 return CStd::Min<LSUINT32>( (ui32Len + 1UL) + static_cast<LSUINT32>(bNegative), _ui32MaxLen ); 00730 } 00731 00740 static LSVOID LSE_CALL Add( const CLargeInteger<_uMaxDigits> &_liLeft, 00741 const CLargeInteger<_uMaxDigits> &_liRight, 00742 CLargeInteger<_uMaxDigits> &_liResult ) { 00743 const LSUINT32 ui32LastPos = _uMaxDigits - 1UL; 00744 00745 // Store the sign bits. 00746 LSUINT32 ui32SignLeft = (_liLeft.m_ui32Digits[ui32LastPos] & 0x80000000UL); 00747 LSUINT32 ui32SignRight = (_liRight.m_ui32Digits[ui32LastPos] & 0x80000000UL); 00748 00749 _liResult.m_ui32UsedDigits = CStd::Max( _liLeft.m_ui32UsedDigits, _liRight.m_ui32UsedDigits ); 00750 LSUINT64 ui64Carry = 0ULL; 00751 for ( LSUINT32 I = 0UL; I < _liResult.m_ui32UsedDigits; ++I ) { 00752 LSUINT64 ui64Sum = static_cast<LSUINT64>(_liLeft.m_ui32Digits[I]) + static_cast<LSUINT64>(_liRight.m_ui32Digits[I]) + ui64Carry; 00753 ui64Carry = ui64Sum >> 32ULL; 00754 _liResult.m_ui32Digits[I] = static_cast<LSUINT32>(ui64Sum & 0xFFFFFFFF); 00755 } 00756 00757 // Add any remaining carries. 00758 if ( ui64Carry ) { 00759 if ( _liResult.m_ui32UsedDigits == _uMaxDigits ) { 00760 throw LSSTD_LIE_OVERFLOW; 00761 } 00762 else { 00763 _liResult.m_ui32Digits[_liResult.m_ui32UsedDigits++] = static_cast<LSUINT32>(ui64Carry); 00764 } 00765 } 00766 00767 // Remove opening 0's. 00768 while ( _liResult.m_ui32UsedDigits > 1UL && _liResult.m_ui32Digits[_liResult.m_ui32UsedDigits-1UL] == 0 ) { 00769 --_liResult.m_ui32UsedDigits; 00770 } 00771 00772 // Check for overflow. 00773 if ( ui32SignLeft == ui32SignRight && 00774 (_liResult.m_ui32Digits[ui32LastPos] & 0x80000000UL) != ui32SignLeft ) { 00775 throw LSSTD_LIE_OVERFLOW; 00776 } 00777 } 00778 00787 static LSVOID LSE_CALL Subtract( const CLargeInteger<_uMaxDigits> &_liLeft, 00788 const CLargeInteger<_uMaxDigits> &_liRight, 00789 CLargeInteger<_uMaxDigits> &_liResult ) { 00790 const LSUINT32 ui32LastPos = _uMaxDigits - 1UL; 00791 00792 // Store the sign bits. 00793 LSUINT32 ui32SignLeft = (_liLeft.m_ui32Digits[ui32LastPos] & 0x80000000UL); 00794 LSUINT32 ui32SignRight = (_liRight.m_ui32Digits[ui32LastPos] & 0x80000000UL); 00795 00796 _liResult.m_ui32UsedDigits = CStd::Max( _liLeft.m_ui32UsedDigits, _liRight.m_ui32UsedDigits ); 00797 LSINT64 i64Carry = 0; 00798 LSUINT32 I; 00799 for ( I = 0UL; I < _liResult.m_ui32UsedDigits; ++I ) { 00800 LSINT64 i64Dif = static_cast<LSINT64>(_liLeft.m_ui32Digits[I]) - static_cast<LSINT64>(_liRight.m_ui32Digits[I]) - i64Carry; 00801 _liResult.m_ui32Digits[I] = static_cast<LSUINT32>(i64Dif & 0xFFFFFFFF); 00802 00803 if ( i64Dif < 0 ) { 00804 i64Carry = 1; 00805 } 00806 else { 00807 i64Carry = 0; 00808 } 00809 } 00810 00811 if ( i64Carry ) { 00812 for ( ; I < _uMaxDigits; ++I ) { 00813 _liResult.m_ui32Digits[I] = 0xFFFFFFFFUL; 00814 } 00815 _liResult.m_ui32UsedDigits = _uMaxDigits; 00816 } 00817 00818 // Check for overflow. 00819 if ( ui32SignLeft != ui32SignRight && 00820 (_liResult.m_ui32Digits[ui32LastPos] & 0x80000000UL) != ui32SignLeft ) { 00821 throw LSSTD_LIE_OVERFLOW; 00822 } 00823 } 00824 00833 static LSVOID LSE_CALL Multiply( const CLargeInteger<_uMaxDigits> &_liLeft, 00834 const CLargeInteger<_uMaxDigits> &_liRight, 00835 CLargeInteger<_uMaxDigits> &_liResult ) { 00836 const LSUINT32 ui32LastPos = _uMaxDigits - 1UL; 00837 00838 // We work on positive values only, then negate at the end. 00839 LSBOOL bLeftNeg = false, bRightNeg = false; 00840 00841 CLargeInteger<_uMaxDigits> liLeftAbs( _liLeft ); 00842 CLargeInteger<_uMaxDigits> liRightAbs( _liRight ); 00843 00844 if ( _liLeft.m_ui32Digits[ui32LastPos] & 0x80000000UL ) { 00845 bLeftNeg = true; 00846 liLeftAbs = -_liLeft; 00847 } 00848 if ( _liRight.m_ui32Digits[ui32LastPos] & 0x80000000UL ) { 00849 bRightNeg = true; 00850 liRightAbs = -_liRight; 00851 } 00852 00853 // Clear the return. 00854 _liResult = CLargeInteger<_uMaxDigits>(); 00855 00856 00857 // Multiply. 00858 for ( LSUINT32 I = 0UL; I < liLeftAbs.m_ui32UsedDigits; ++I ) { 00859 if ( liLeftAbs.m_ui32Digits[I] == 0 ) { continue; } 00860 LSUINT64 ui64Carry = 0ULL; 00861 for ( LSUINT32 J = 0UL, K = I; J < liRightAbs.m_ui32UsedDigits; ++J, ++K ) { 00862 LSUINT64 ui64Value = static_cast<LSUINT64>(liLeftAbs.m_ui32Digits[I]) * static_cast<LSUINT64>(liRightAbs.m_ui32Digits[J]) + 00863 static_cast<LSUINT64>(_liResult.m_ui32Digits[K]) + ui64Carry; 00864 00865 _liResult.m_ui32Digits[K] = static_cast<LSUINT32>(ui64Value & 0xFFFFFFFF); 00866 00867 ui64Carry = ui64Value >> 32UL; 00868 } 00869 if ( ui64Carry ) { 00870 _liResult.m_ui32Digits[I+liRightAbs.m_ui32UsedDigits] = static_cast<LSUINT32>(ui64Carry); 00871 } 00872 } 00873 00874 _liResult.m_ui32UsedDigits = liLeftAbs.m_ui32UsedDigits + liRightAbs.m_ui32UsedDigits; 00875 _liResult.m_ui32UsedDigits = static_cast<LSUINT32>(CStd::Min<LSUINT32>( _liResult.m_ui32UsedDigits, _uMaxDigits )); 00876 // Remove opening 0's. 00877 while ( _liResult.m_ui32UsedDigits > 1UL && _liResult.m_ui32Digits[_liResult.m_ui32UsedDigits-1UL] == 0 ) { 00878 --_liResult.m_ui32UsedDigits; 00879 } 00880 00881 // Check for overflow. 00882 if ( _liResult.m_ui32Digits[ui32LastPos] & 0x80000000UL ) { 00883 if ( bLeftNeg != bRightNeg && _liResult.m_ui32Digits[ui32LastPos] == 0x80000000UL ) { 00884 // Handle the special case in which multiplication results in a maximum negative 00885 // number in 2's compliment. 00886 if ( _liResult.m_ui32UsedDigits == 1UL ) { 00887 return; 00888 } 00889 LSBOOL bMaxNeg = true; 00890 for ( LSUINT32 I = 0UL; I < _liResult.m_ui32UsedDigits - 1; ++I ) { 00891 if ( _liResult.m_ui32Digits[I] != 0 ) { 00892 bMaxNeg = false; 00893 break; 00894 } 00895 } 00896 if ( bMaxNeg ) { 00897 return; 00898 } 00899 } 00900 throw LSSTD_LIE_OVERFLOW; 00901 } 00902 00903 // Reverse the signs if necessary. 00904 if ( bLeftNeg != bRightNeg ) { 00905 Negate( _liResult, _liResult ); 00906 } 00907 } 00908 00917 static LSVOID LSE_CALL Divide( const CLargeInteger<_uMaxDigits> &_liLeft, 00918 const CLargeInteger<_uMaxDigits> &_liRight, 00919 CLargeInteger<_uMaxDigits> &_liResult ) { 00920 if ( _liRight.m_ui32UsedDigits == 1UL && _liRight.m_ui32Digits[0] == 0x00000000UL ) { 00921 throw LSSTD_LIE_DIVISIONBYZERO; 00922 } 00923 const LSUINT32 ui32LastPos = _uMaxDigits - 1UL; 00924 00925 00926 00927 CLargeInteger<_uMaxDigits> * pliNewLeft = new CLargeInteger<_uMaxDigits>( _liLeft ); 00928 CLargeInteger<_uMaxDigits> * pliNewRight = new CLargeInteger<_uMaxDigits>( _liRight ); 00929 00930 LSBOOL bDivisorNeg = false, bDividendNeg = false; 00931 if ( _liLeft.m_ui32Digits[ui32LastPos] & 0x80000000UL ) { 00932 bDividendNeg = true; 00933 (*pliNewLeft) = -(*pliNewLeft); 00934 } 00935 if ( _liRight.m_ui32Digits[ui32LastPos] & 0x80000000UL ) { 00936 bDivisorNeg = true; 00937 (*pliNewRight) = -(*pliNewRight); 00938 } 00939 00940 if ( (*pliNewLeft) < (*pliNewRight) ) { 00941 _liResult = CLargeInteger<_uMaxDigits>( 0ULL ); 00942 delete pliNewLeft; 00943 delete pliNewRight; 00944 return; 00945 } 00946 00947 // Hold the results. 00948 CLargeInteger<_uMaxDigits> * pliRem = new CLargeInteger<_uMaxDigits>(); 00949 if ( (*pliNewRight).m_ui32UsedDigits == 1UL ) { 00950 DivideS( (*pliNewLeft), (*pliNewRight), 00951 _liResult, (*pliRem) ); 00952 } 00953 else { 00954 DivideM( (*pliNewLeft), (*pliNewRight), 00955 _liResult, (*pliRem) ); 00956 } 00957 00958 if ( bDivisorNeg != bDividendNeg ) { 00959 // Flip the sign. 00960 _liResult = -_liResult; 00961 } 00962 00963 delete pliRem; 00964 delete pliNewLeft; 00965 delete pliNewRight; 00966 } 00967 00976 static LSVOID LSE_CALL Modulus( const CLargeInteger<_uMaxDigits> &_liLeft, 00977 const CLargeInteger<_uMaxDigits> &_liRight, 00978 CLargeInteger<_uMaxDigits> &_liResult ) { 00979 if ( _liRight.m_ui32UsedDigits == 1UL && _liRight.m_ui32Digits[0] == 0x00000000UL ) { 00980 throw LSSTD_LIE_DIVISIONBYZERO; 00981 } 00982 const LSUINT32 ui32LastPos = _uMaxDigits - 1UL; 00983 00984 00985 00986 CLargeInteger<_uMaxDigits> * pliNewLeft = new CLargeInteger<_uMaxDigits>( _liLeft ); 00987 CLargeInteger<_uMaxDigits> * pliNewRight = new CLargeInteger<_uMaxDigits>( _liRight ); 00988 00989 LSBOOL bDividendNeg = false; 00990 if ( _liLeft.m_ui32Digits[ui32LastPos] & 0x80000000UL ) { 00991 bDividendNeg = true; 00992 (*pliNewLeft) = -(*pliNewLeft); 00993 } 00994 if ( _liRight.m_ui32Digits[ui32LastPos] & 0x80000000UL ) { 00995 (*pliNewRight) = -(*pliNewRight); 00996 } 00997 00998 if ( (*pliNewLeft) < (*pliNewRight) ) { 00999 _liResult = _liLeft; 01000 delete pliNewLeft; 01001 delete pliNewRight; 01002 return; 01003 } 01004 01005 // Hold the results. 01006 CLargeInteger<_uMaxDigits> * pliRes = new CLargeInteger<_uMaxDigits>(); 01007 if ( (*pliNewRight).m_ui32UsedDigits == 1UL ) { 01008 DivideS( (*pliNewLeft), (*pliNewRight), 01009 (*pliRes), _liResult ); 01010 } 01011 else { 01012 DivideM( (*pliNewLeft), (*pliNewRight), 01013 (*pliRes), _liResult ); 01014 } 01015 01016 if ( bDividendNeg ) { 01017 // Flip the sign. 01018 _liResult = -_liResult; 01019 } 01020 01021 delete pliRes; 01022 delete pliNewLeft; 01023 delete pliNewRight; 01024 } 01025 01032 static LSVOID LSE_CALL Negate( const CLargeInteger<_uMaxDigits> &_liValue, 01033 CLargeInteger<_uMaxDigits> &_liResult ) { 01034 // Handle negation of 0 manually. 01035 if ( _liValue.m_ui32UsedDigits == 0UL && _liValue.m_ui32Digits[0] == 0 ) { 01036 for ( LSINT32 I = _uMaxDigits; --I >= 0; ) { 01037 _liResult.m_ui32Digits[I] = 0; 01038 } 01039 _liResult.m_ui32UsedDigits = 1UL; 01040 return; 01041 } 01042 01043 // Store the sign bit before processing. 01044 LSUINT32 ui32SignBit = (_liValue.m_ui32Digits[_uMaxDigits-1UL] & 0x80000000UL); 01045 01046 // Perform 1's compliment. 01047 for ( LSINT32 I = _uMaxDigits; --I >= 0; ) { 01048 _liResult.m_ui32Digits[I] = ~_liValue.m_ui32Digits[I]; 01049 } 01050 01051 // Add 1 to the result. 01052 LSUINT64 ui64Value, ui64Carry = 1UL; 01053 for ( LSUINT32 I = 0; ui64Carry && I < _uMaxDigits; ++I ) { 01054 ui64Value = _liResult.m_ui32Digits[I] + 1ULL; 01055 _liResult.m_ui32Digits[I] = static_cast<LSUINT32>(ui64Value & 0xFFFFFFFF); 01056 ui64Carry = ui64Value >> 32UL; 01057 } 01058 01059 // Check for overflow. 01060 if ( ui32SignBit == (_liResult.m_ui32Digits[_uMaxDigits-1UL] & 0x80000000UL) ) { 01061 throw LSSTD_LIE_OVERFLOW; 01062 } 01063 01064 _liResult.m_ui32UsedDigits = _uMaxDigits; 01065 // Remove opening 0's. 01066 while ( _liResult.m_ui32UsedDigits > 1UL && _liResult.m_ui32Digits[_liResult.m_ui32UsedDigits-1UL] == 0 ) { 01067 --_liResult.m_ui32UsedDigits; 01068 } 01069 } 01070 01079 static LSUINT32 LSE_CALL ShiftLeft( LSUINT32 * _pui32Data, LSUINT32 _ui32Len, 01080 LSUINT32 _ui32Amount ) { 01081 01082 LSUINT32 ui32ShiftAmt = 32UL; 01083 LSUINT32 ui32Used = _ui32Len; 01084 01085 while ( ui32Used > 1UL && _pui32Data[ui32Used-1] == 0 ) { 01086 --ui32Used; 01087 } 01088 01089 01090 for ( LSUINT32 I = _ui32Amount; I > 0UL; ) { 01091 if ( I < ui32ShiftAmt ) { 01092 ui32ShiftAmt = I; 01093 } 01094 01095 LSUINT64 ui64Carry = 0ULL; 01096 01097 for ( LSUINT32 J = 0UL; J < ui32Used; ++J ) { 01098 LSUINT64 ui64Value = static_cast<LSUINT64>(_pui32Data[J]) << ui32ShiftAmt; 01099 ui64Value |= ui64Carry; 01100 01101 _pui32Data[J] = static_cast<LSUINT32>(ui64Value); 01102 ui64Carry = ui64Value >> 32ULL; 01103 } 01104 01105 if ( ui64Carry ) { 01106 if ( ui32Used + 1UL <= _ui32Len ) { 01107 _pui32Data[ui32Used++] = static_cast<LSUINT32>(ui64Carry); 01108 } 01109 } 01110 01111 I -= ui32ShiftAmt; 01112 } 01113 return ui32Used; 01114 } 01115 01124 static LSUINT32 LSE_CALL ShiftRight( LSUINT32 * _pui32Data, LSUINT32 _ui32Len, 01125 LSUINT32 _ui32Amount ) { 01126 01127 LSUINT32 ui32ShiftAmt = 32ULL; 01128 LSUINT32 ui32InvShift = 0UL; 01129 LSUINT32 ui32Used = _ui32Len; 01130 01131 while ( ui32Used > 1UL && _pui32Data[ui32Used-1] == 0 ) { 01132 --ui32Used; 01133 } 01134 01135 01136 for ( LSUINT32 I = _ui32Amount; I > 0UL; ) { 01137 if ( I < ui32ShiftAmt ) { 01138 ui32ShiftAmt = I; 01139 ui32InvShift = 32ULL - ui32ShiftAmt; 01140 } 01141 01142 LSUINT64 ui64Carry = 0ULL; 01143 01144 for ( LSINT32 J = static_cast<LSINT32>(ui32Used - 1UL); J >= 0; --J ) { 01145 LSUINT64 ui64Value = static_cast<LSUINT64>(_pui32Data[J]) >> static_cast<LSUINT64>(ui32ShiftAmt); 01146 ui64Value |= ui64Carry; 01147 01148 ui64Carry = _pui32Data[J] << ui32InvShift; 01149 _pui32Data[J] = static_cast<LSUINT32>(ui64Value); 01150 } 01151 01152 I -= ui32ShiftAmt; 01153 } 01154 01155 // Remove opening 0's. 01156 while ( ui32Used > 1UL && _pui32Data[ui32Used-1UL] == 0 ) { 01157 --ui32Used; 01158 } 01159 01160 return ui32Used; 01161 } 01162 01163 01164 protected : 01165 // == Members. 01166 // The digits we maintain. 01167 LSUINT32 m_ui32Digits[_uMaxDigits]; 01168 01169 // Number of digits we actually use. 01170 LSUINT32 m_ui32UsedDigits; 01171 01172 private : 01182 static LSVOID LSE_CALL DivideM( const CLargeInteger<_uMaxDigits> &_liLeft, 01183 const CLargeInteger<_uMaxDigits> &_liRight, 01184 CLargeInteger<_uMaxDigits> &_liQuotient, 01185 CLargeInteger<_uMaxDigits> &_liRemainder ) { 01186 01187 // Allocate on the heap to help avoid stack overflow. 01188 // A bit slower, but division is slow, and this is not a high-performance routine. 01189 CLargeInteger<_uMaxDigits> * pliResult = new CLargeInteger<_uMaxDigits>(); 01190 CLargeInteger<_uMaxDigits+1UL> * pliRemainder = new CLargeInteger<_uMaxDigits+1UL>(); 01191 01192 LSUINT32 ui32Mask = 0x80000000UL; 01193 LSUINT32 ui32Value = _liRight.m_ui32Digits[_liRight.m_ui32UsedDigits-1UL]; 01194 LSUINT32 ui32Shift = 0UL, ui32ResPos = 0UL; 01195 while ( ui32Mask && (ui32Value & ui32Mask) == 0 ) { 01196 ++ui32Shift; 01197 ui32Mask >>= 1UL; 01198 } 01199 01200 for ( LSUINT32 I = _liLeft.m_ui32UsedDigits; I--; ) { 01201 pliRemainder->GetBytes()[I] = _liLeft.m_ui32Digits[I]; 01202 } 01203 pliRemainder->SetLength( _liLeft.m_ui32UsedDigits + 1 ); 01204 01205 ShiftLeft( pliRemainder->GetBytes(), pliRemainder->GetLength(), ui32Shift ); 01206 CLargeInteger<_uMaxDigits> liNewRight = _liRight << ui32Shift; 01207 01208 LSUINT32 ui32J = pliRemainder->GetLength() - liNewRight.m_ui32UsedDigits; 01209 LSUINT32 ui32Pos = pliRemainder->GetLength() - 1UL; 01210 01211 LSUINT32 ui32FirstDivisorByte = liNewRight.m_ui32Digits[liNewRight.m_ui32UsedDigits-1UL]; 01212 LSUINT32 ui32SecondDivisorByte = liNewRight.m_ui32Digits[liNewRight.m_ui32UsedDigits-2UL]; 01213 01214 LSUINT32 ui32DivisorLen = liNewRight.m_ui32UsedDigits + 1UL; 01215 LSUINT32 * pui32DividendPart = new LSUINT32[ui32DivisorLen]; 01216 01217 for ( ; ui32J > 0UL; --ui32J ) { 01218 LSUINT64 ui64Dividend = (static_cast<LSUINT64>(pliRemainder->GetBytes()[ui32Pos]) << 32ULL) + pliRemainder->GetBytes()[ui32Pos-1UL]; 01219 01220 LSUINT64 ui64Q = ui64Dividend / ui32FirstDivisorByte; 01221 LSUINT64 ui64R = ui64Dividend % ui32FirstDivisorByte; 01222 01223 LSBOOL bDone = false; 01224 while ( !bDone ) { 01225 bDone = true; 01226 01227 if ( ui64Q == 0x100000000ULL || 01228 (ui64Q * ui32SecondDivisorByte) > ((ui64R << 32UL) + pliRemainder->GetBytes()[ui32Pos-2UL]) ) { 01229 --ui64Q; 01230 ui64R += ui32FirstDivisorByte; 01231 if ( ui64R < 0x100000000ULL ) { 01232 bDone = false; 01233 } 01234 } 01235 } 01236 01237 for ( LSUINT32 I = 0UL; I < ui32DivisorLen; ++I ) { 01238 pui32DividendPart[I] = pliRemainder->GetBytes()[ui32Pos-I]; 01239 } 01240 01241 // Again on the heap instead of on the stack. 01242 CLargeInteger<_uMaxDigits> * pliK = new CLargeInteger<_uMaxDigits>( pui32DividendPart, ui32DivisorLen ); 01243 CLargeInteger<_uMaxDigits> liS( liNewRight * CLargeInteger<_uMaxDigits>( static_cast<LSINT64>(ui64Q) ) ); 01244 01245 while ( liS > (*pliK) ) { 01246 --ui64Q; 01247 liS = liS - liNewRight; 01248 } 01249 01250 CLargeInteger<_uMaxDigits> liY = (*pliK) - liS; 01251 for ( LSUINT32 I = 0UL; I < ui32DivisorLen; ++I ) { 01252 pliRemainder->GetBytes()[ui32Pos-I] = liY.m_ui32Digits[liNewRight.m_ui32UsedDigits-I]; 01253 } 01254 01255 delete pliK; 01256 01257 pliResult->m_ui32Digits[ui32ResPos++] = static_cast<LSUINT32>(ui64Q); 01258 --ui32Pos; 01259 } 01260 01261 _liQuotient.m_ui32UsedDigits = ui32ResPos; 01262 01263 LSUINT32 Y = 0UL; 01264 for ( LSINT32 X = static_cast<LSINT32>(_liQuotient.m_ui32UsedDigits) - 1; X >= 0; --X, ++Y ) { 01265 _liQuotient.m_ui32Digits[Y] = pliResult->m_ui32Digits[X]; 01266 } 01267 01268 for ( ; Y < _uMaxDigits; ++Y ) { 01269 _liQuotient.m_ui32Digits[Y] = 0UL; 01270 } 01271 01272 while ( _liQuotient.m_ui32UsedDigits > 1 && _liQuotient.m_ui32Digits[_liQuotient.m_ui32UsedDigits-1] == 0UL ) { 01273 --_liQuotient.m_ui32UsedDigits; 01274 } 01275 01276 _liQuotient.m_ui32UsedDigits = CStd::Max<LSUINT32>( _liQuotient.m_ui32UsedDigits, 1UL ); 01277 01278 _liRemainder.m_ui32UsedDigits = ShiftRight( pliRemainder->GetBytes(), pliRemainder->GetLength(), ui32Shift ); 01279 CStd::MemCpy( _liRemainder.m_ui32Digits, pliRemainder->GetBytes(), sizeof( _liRemainder.m_ui32Digits[0UL] ) * _liRemainder.m_ui32UsedDigits ); 01280 for ( Y = _liRemainder.m_ui32UsedDigits; Y < _uMaxDigits; ++Y ) { 01281 _liRemainder.m_ui32Digits[Y] = 0UL; 01282 } 01283 01284 delete pui32DividendPart; 01285 delete pliRemainder; 01286 delete pliResult; 01287 } 01288 01298 static LSVOID LSE_CALL DivideS( const CLargeInteger<_uMaxDigits> &_liLeft, 01299 const CLargeInteger<_uMaxDigits> &_liRight, 01300 CLargeInteger<_uMaxDigits> &_liQuotient, 01301 CLargeInteger<_uMaxDigits> &_liRemainder ) { 01302 01303 CLargeInteger<_uMaxDigits> liResult; 01304 LSUINT32 ui32ResPos = 0UL; 01305 01306 // Copy dividend to remainder. 01307 _liRemainder = _liLeft; 01308 01309 // Remove opening 0's. 01310 while ( _liRemainder.m_ui32UsedDigits > 1UL && _liRemainder.m_ui32Digits[_liRemainder.m_ui32UsedDigits-1UL] == 0 ) { 01311 --_liRemainder.m_ui32UsedDigits; 01312 } 01313 01314 LSUINT64 ui64Divisor = _liRight.m_ui32Digits[0UL]; 01315 LSINT32 i32Pos = static_cast<LSINT32>(_liRemainder.m_ui32UsedDigits - 1UL); 01316 LSUINT64 ui64Dividend = _liRemainder.m_ui32Digits[i32Pos]; 01317 01318 if ( ui64Dividend >= ui64Divisor ) { 01319 LSUINT64 ui64Quotient = ui64Dividend / ui64Divisor; 01320 liResult.m_ui32Digits[ui32ResPos++] = static_cast<LSUINT32>(ui64Quotient); 01321 _liRemainder.m_ui32Digits[i32Pos] = static_cast<LSUINT32>(ui64Dividend % ui64Divisor); 01322 } 01323 --i32Pos; 01324 01325 while ( i32Pos >= 0 ) { 01326 ui64Dividend = (static_cast<LSUINT64>(_liRemainder.m_ui32Digits[i32Pos+1]) << 32ULL) + _liRemainder.m_ui32Digits[i32Pos]; 01327 LSUINT64 ui64Quotient = ui64Dividend / ui64Divisor; 01328 liResult.m_ui32Digits[ui32ResPos++] = static_cast<LSUINT32>(ui64Quotient); 01329 01330 _liRemainder.m_ui32Digits[i32Pos+1] = 0; 01331 _liRemainder.m_ui32Digits[i32Pos--] = static_cast<LSUINT32>(ui64Dividend % ui64Divisor); 01332 } 01333 01334 // Copy the result over the output quotient. 01335 _liQuotient.m_ui32UsedDigits = ui32ResPos; 01336 01337 LSUINT32 J = 0UL; 01338 for ( LSINT32 I = static_cast<LSINT32>(_liQuotient.m_ui32UsedDigits) - 1; I >= 0; --I, ++J ) { 01339 _liQuotient.m_ui32Digits[J] = liResult.m_ui32Digits[I]; 01340 } 01341 01342 for ( ; J < _uMaxDigits; ++J ) { 01343 _liQuotient.m_ui32Digits[J] = 0; 01344 } 01345 01346 // Fix it. 01347 while ( _liQuotient.m_ui32UsedDigits > 1 && _liQuotient.m_ui32Digits[_liQuotient.m_ui32UsedDigits-1] == 0 ) { 01348 --_liQuotient.m_ui32UsedDigits; 01349 } 01350 _liQuotient.m_ui32UsedDigits = CStd::Max<LSUINT32>( _liQuotient.m_ui32UsedDigits, 1UL ); 01351 01352 while ( _liRemainder.m_ui32UsedDigits > 1 && _liRemainder.m_ui32Digits[_liRemainder.m_ui32UsedDigits-1] == 0 ) { 01353 --_liRemainder.m_ui32UsedDigits; 01354 } 01355 01356 } 01357 }; 01358 01359 } // namespace lsstd 01360 01361 #pragma warning( pop ) 01362 01363 #endif // __LSSTD_LARGEINTEGER_H__