tools/source/generic/bigint.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <limits>
  21 #include <math.h>
  22
  23 #include <rtl/ustrbuf.hxx>
  24 #include <osl/diagnose.h>
  25 #include <tools/bigint.hxx>
  26
  27
  28 #include <string.h>
  29 #include <ctype.h>
  30
  31 static const long MY_MAXLONG  = 0x3fffffff;
  32 static const long MY_MINLONG  = -MY_MAXLONG;
  33 static const long MY_MAXSHORT = 0x00007fff;
  34 static const long MY_MINSHORT = -MY_MAXSHORT;
  35
  36 /*
  37  * The algorithms for Addition, Subtraction, Multiplication and Division
  38  * of large numbers originate from SEMINUMERICAL ALGORITHMS by
  39  * DONALD E. KNUTH in the series The Art of Computer Programming:
  40  * chapter 4.3.1. The Classical Algorithms.
  41  */
  42
  43 // TODO: Needs conversion to sal_uInt16/INT16/sal_uInt32/sal_Int32
  44 void BigInt::MakeBigInt( const BigInt& rVal )
  45 {
  46     if ( rVal.bIsBig )
  47     {
  48         memcpy( (void*)this, (const void*)&rVal, sizeof( BigInt ) );
  49         while ( nLen > 1 && nNum[nLen-1] == 0 )
  50             nLen--;
  51     }
  52     else
  53     {
  54         long nTmp = rVal.nVal;
  55
  56         nVal   = rVal.nVal;
  57         bIsBig = true;
  58         if ( nTmp < 0 )
  59         {
  60             bIsNeg = true;
  61             nTmp = -nTmp;
  62         }
  63         else
  64             bIsNeg = false;
  65
  66         nNum[0] = (sal_uInt16)(nTmp & 0xffffL);
  67         nNum[1] = (sal_uInt16)(nTmp >> 16);
  68         if ( nTmp & 0xffff0000L )
  69             nLen = 2;
  70         else
  71             nLen = 1;
  72     }
  73 }
  74
  75 void BigInt::Normalize()
  76 {
  77     if ( bIsBig )
  78     {
  79         while ( nLen > 1 && nNum[nLen-1] == 0 )
  80             nLen--;
  81
  82         if ( nLen < 3 )
  83         {
  84             if ( nLen < 2 )
  85                 nVal = nNum[0];
  86             else if ( nNum[1] & 0x8000 )
  87                 return;
  88             else
  89                 nVal = ((long)nNum[1] << 16) + nNum[0];
  90
  91             bIsBig = false;
  92
  93             if ( bIsNeg )
  94                 nVal = -nVal;
  95         }
  96         // else nVal is undefined !!! W.P.
  97     }
  98     // why? nVal is undefined ??? W.P.
  99     else if ( nVal & 0xFFFF0000L )
 100         nLen = 2;
 101     else
 102         nLen = 1;
 103 }
 104
 105 void BigInt::Mult( const BigInt &rVal, sal_uInt16 nMul )
 106 {
 107     sal_uInt16 nK = 0;
 108     for ( int i = 0; i < rVal.nLen; i++ )
 109     {
 110         sal_uInt32 nTmp = (sal_uInt32)rVal.nNum[i] * (sal_uInt32)nMul + nK;
 111         nK            = (sal_uInt16)(nTmp >> 16);
 112         nNum[i] = (sal_uInt16)nTmp;
 113     }
 114
 115     if ( nK )
 116     {
 117         nNum[rVal.nLen] = nK;
 118         nLen = rVal.nLen + 1;
 119     }
 120     else
 121         nLen = rVal.nLen;
 122
 123     bIsBig = true;
 124     bIsNeg = rVal.bIsNeg;
 125 }
 126
 127 void BigInt::Div( sal_uInt16 nDiv, sal_uInt16& rRem )
 128 {
 129     sal_uInt32 nK = 0;
 130     for ( int i = nLen - 1; i >= 0; i-- )
 131     {
 132         sal_uInt32 nTmp = (sal_uInt32)nNum[i] + (nK << 16);
 133         nNum[i] = (sal_uInt16)(nTmp / nDiv);
 134         nK            = nTmp % nDiv;
 135     }
 136     rRem = (sal_uInt16)nK;
 137
 138     if ( nNum[nLen-1] == 0 )
 139         nLen -= 1;
 140 }
 141
 142 bool BigInt::IsLess( const BigInt& rVal ) const
 143 {
 144     if ( rVal.nLen < nLen)
 145         return true;
 146     if ( rVal.nLen > nLen )
 147         return false;
 148
 149     int i;
 150     for ( i = nLen - 1; i > 0 && nNum[i] == rVal.nNum[i]; i-- )
 151     {
 152     }
 153     return rVal.nNum[i] < nNum[i];
 154 }
 155
 156 void BigInt::AddLong( BigInt& rB, BigInt& rErg )
 157 {
 158     if ( bIsNeg == rB.bIsNeg )
 159     {
 160         int  i;
 161         char len;
 162
 163         // if length of the two values differ, fill remaining positions
 164         // of the smaller value with zeros.
 165         if (nLen >= rB.nLen)
 166         {
 167             len = nLen;
 168             for (i = rB.nLen; i < len; i++)
 169                 rB.nNum[i] = 0;
 170         }
 171         else
 172         {
 173             len = rB.nLen;
 174             for (i = nLen; i < len; i++)
 175                 nNum[i] = 0;
 176         }
 177
 178         // Add numerals, starting from the back
 179         long k;
 180         long nZ = 0;
 181         for (i = 0, k = 0; i < len; i++) {
 182             nZ = (long)nNum[i] + (long)rB.nNum[i] + k;
 183             if (nZ & 0xff0000L)
 184                 k = 1;
 185             else
 186                 k = 0;
 187             rErg.nNum[i] = (sal_uInt16)(nZ & 0xffffL);
 188         }
 189         // If an overflow occurred, add to solution
 190         if (nZ & 0xff0000L) // or if(k)
 191         {
 192             rErg.nNum[i] = 1;
 193             len++;
 194         }
 195         // Set length and sign
 196         rErg.nLen   = len;
 197         rErg.bIsNeg = bIsNeg && rB.bIsNeg;
 198         rErg.bIsBig = true;
 199     }
 200     // If one of the values is negative, perform subtraction instead
 201     else if (bIsNeg)
 202     {
 203         bIsNeg = false;
 204         rB.SubLong(*this, rErg);
 205         bIsNeg = true;
 206     }
 207     else
 208     {
 209         rB.bIsNeg = false;
 210         SubLong(rB, rErg);
 211         rB.bIsNeg = true;
 212     }
 213 }
 214
 215 void BigInt::SubLong( BigInt& rB, BigInt& rErg )
 216 {
 217     if ( bIsNeg == rB.bIsNeg )
 218     {
 219         int  i;
 220         char len;
 221         long nZ, k;
 222
 223         // if length of the two values differ, fill remaining positions
 224         // of the smaller value with zeros.
 225         if (nLen >= rB.nLen)
 226         {
 227             len = nLen;
 228             for (i = rB.nLen; i < len; i++)
 229                 rB.nNum[i] = 0;
 230         }
 231         else
 232         {
 233             len = rB.nLen;
 234             for (i = nLen; i < len; i++)
 235                 nNum[i] = 0;
 236         }
 237
 238         if ( IsLess(rB) )
 239         {
 240             for (i = 0, k = 0; i < len; i++)
 241             {
 242                 nZ = (long)nNum[i] - (long)rB.nNum[i] + k;
 243                 if (nZ < 0)
 244                     k = -1;
 245                 else
 246                     k = 0;
 247                 rErg.nNum[i] = (sal_uInt16)(nZ & 0xffffL);
 248             }
 249             rErg.bIsNeg = bIsNeg;
 250         }
 251         else
 252         {
 253             for (i = 0, k = 0; i < len; i++)
 254             {
 255                 nZ = (long)rB.nNum[i] - (long)nNum[i] + k;
 256                 if (nZ < 0)
 257                     k = -1;
 258                 else
 259                     k = 0;
 260                 rErg.nNum[i] = (sal_uInt16)(nZ & 0xffffL);
 261             }
 262             // if a < b, revert sign
 263             rErg.bIsNeg = !bIsNeg;
 264         }
 265         rErg.nLen   = len;
 266         rErg.bIsBig = true;
 267     }
 268     // If one of the values is negative, perform addition instead
 269     else if (bIsNeg)
 270     {
 271         bIsNeg = false;
 272         AddLong(rB, rErg);
 273         bIsNeg = true;
 274         rErg.bIsNeg = true;
 275     }
 276     else
 277     {
 278         rB.bIsNeg = false;
 279         AddLong(rB, rErg);
 280         rB.bIsNeg = true;
 281         rErg.bIsNeg = false;
 282     }
 283 }
 284
 285 void BigInt::MultLong( const BigInt& rB, BigInt& rErg ) const
 286 {
 287     int    i, j;
 288     sal_uInt32  nZ, k;
 289
 290     rErg.bIsNeg = bIsNeg != rB.bIsNeg;
 291     rErg.bIsBig = true;
 292     rErg.nLen   = nLen + rB.nLen;
 293
 294     for (i = 0; i < rErg.nLen; i++)
 295         rErg.nNum[i] = 0;
 296
 297     for (j = 0; j < rB.nLen; j++)
 298     {
 299         for (i = 0, k = 0; i < nLen; i++)
 300         {
 301             nZ = (sal_uInt32)nNum[i] * (sal_uInt32)rB.nNum[j] +
 302                  (sal_uInt32)rErg.nNum[i + j] + k;
 303             rErg.nNum[i + j] = (sal_uInt16)(nZ & 0xffffUL);
 304             k = nZ >> 16;
 305         }
 306         rErg.nNum[i + j] = (sal_uInt16)k;
 307     }
 308 }
 309
 310 void BigInt::DivLong( const BigInt& rB, BigInt& rErg ) const
 311 {
 312     int    i, j;
 313     sal_uInt16 nK, nQ, nMult;
 314     short  nLenB  = rB.nLen;
 315     short  nLenB1 = rB.nLen - 1;
 316     BigInt aTmpA, aTmpB;
 317
 318     nMult = (sal_uInt16)(0x10000L / ((long)rB.nNum[nLenB1] + 1));
 319
 320     aTmpA.Mult( *this, nMult );
 321     if ( aTmpA.nLen == nLen )
 322     {
 323         aTmpA.nNum[aTmpA.nLen] = 0;
 324         aTmpA.nLen++;
 325     }
 326
 327     aTmpB.Mult( rB, nMult );
 328
 329     for (j = aTmpA.nLen - 1; j >= nLenB; j--)
 330     { // guess divisor
 331         long nTmp = ( (long)aTmpA.nNum[j] << 16 ) + aTmpA.nNum[j - 1];
 332         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 333             nQ = 0xFFFF;
 334         else
 335             nQ = (sal_uInt16)(((sal_uInt32)nTmp) / aTmpB.nNum[nLenB1]);
 336
 337         if ( ((sal_uInt32)aTmpB.nNum[nLenB1 - 1] * nQ) >
 338             ((((sal_uInt32)nTmp) - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
 339             nQ--;
 340         // Start division
 341         nK = 0;
 342         nTmp = 0;
 343         for (i = 0; i < nLenB; i++)
 344         {
 345             nTmp = (long)aTmpA.nNum[j - nLenB + i]
 346                    - ((long)aTmpB.nNum[i] * nQ)
 347                    - nK;
 348             aTmpA.nNum[j - nLenB + i] = (sal_uInt16)nTmp;
 349             nK = (sal_uInt16) (nTmp >> 16);
 350             if ( nK )
 351                 nK = (sal_uInt16)(0x10000UL - nK);
 352         }
 353         unsigned short& rNum( aTmpA.nNum[j - nLenB + i] );
 354         rNum = rNum - nK;   // MSVC yields a warning on -= here, so don't use it
 355         if (aTmpA.nNum[j - nLenB + i] == 0)
 356             rErg.nNum[j - nLenB] = nQ;
 357         else
 358         {
 359             rErg.nNum[j - nLenB] = nQ - 1;
 360             nK = 0;
 361             for (i = 0; i < nLenB; i++)
 362             {
 363                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 364                 aTmpA.nNum[j - nLenB + i] = (sal_uInt16)(nTmp & 0xFFFFL);
 365                 if (nTmp & 0xFFFF0000L)
 366                     nK = 1;
 367                 else
 368                     nK = 0;
 369             }
 370         }
 371     }
 372
 373     rErg.bIsNeg = bIsNeg != rB.bIsNeg;
 374     rErg.bIsBig = true;
 375     rErg.nLen   = nLen - rB.nLen + 1;
 376 }
 377
 378 void BigInt::ModLong( const BigInt& rB, BigInt& rErg ) const
 379 {
 380     short  i, j;
 381     sal_uInt16 nK, nQ, nMult;
 382     short  nLenB  = rB.nLen;
 383     short  nLenB1 = rB.nLen - 1;
 384     BigInt aTmpA, aTmpB;
 385
 386     nMult = (sal_uInt16)(0x10000L / ((long)rB.nNum[nLenB1] + 1));
 387
 388     aTmpA.Mult( *this, nMult);
 389     if ( aTmpA.nLen == nLen )
 390     {
 391         aTmpA.nNum[aTmpA.nLen] = 0;
 392         aTmpA.nLen++;
 393     }
 394
 395     aTmpB.Mult( rB, nMult);
 396
 397     for (j = aTmpA.nLen - 1; j >= nLenB; j--)
 398     { // Guess divisor
 399         long nTmp = ( (long)aTmpA.nNum[j] << 16 ) + aTmpA.nNum[j - 1];
 400         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 401             nQ = 0xFFFF;
 402         else
 403             nQ = (sal_uInt16)(((sal_uInt32)nTmp) / aTmpB.nNum[nLenB1]);
 404
 405         if ( ((sal_uInt32)aTmpB.nNum[nLenB1 - 1] * nQ) >
 406             ((((sal_uInt32)nTmp) - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
 407             nQ--;
 408         // Start division
 409         nK = 0;
 410         nTmp = 0;
 411         for (i = 0; i < nLenB; i++)
 412         {
 413             nTmp = (long)aTmpA.nNum[j - nLenB + i]
 414                    - ((long)aTmpB.nNum[i] * nQ)
 415                    - nK;
 416             aTmpA.nNum[j - nLenB + i] = (sal_uInt16)nTmp;
 417             nK = (sal_uInt16) (nTmp >> 16);
 418             if ( nK )
 419                 nK = (sal_uInt16)(0x10000UL - nK);
 420         }
 421         unsigned short& rNum( aTmpA.nNum[j - nLenB + i] );
 422         rNum = rNum - nK;
 423         if (aTmpA.nNum[j - nLenB + i] == 0)
 424             rErg.nNum[j - nLenB] = nQ;
 425         else
 426         {
 427             rErg.nNum[j - nLenB] = nQ - 1;
 428             nK = 0;
 429             for (i = 0; i < nLenB; i++) {
 430                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 431                 aTmpA.nNum[j - nLenB + i] = (sal_uInt16)(nTmp & 0xFFFFL);
 432                 if (nTmp & 0xFFFF0000L)
 433                     nK = 1;
 434                 else
 435                     nK = 0;
 436             }
 437         }
 438     }
 439
 440     rErg = aTmpA;
 441     rErg.Div( nMult, nQ );
 442 }
 443
 444 bool BigInt::ABS_IsLess( const BigInt& rB ) const
 445 {
 446     if (bIsBig || rB.bIsBig)
 447     {
 448         BigInt nA, nB;
 449         nA.MakeBigInt( *this );
 450         nB.MakeBigInt( rB );
 451         if (nA.nLen == nB.nLen)
 452         {
 453             int i;
 454             for (i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i--)
 455             {
 456             }
 457             return nA.nNum[i] < nB.nNum[i];
 458         }
 459         else
 460             return nA.nLen < nB.nLen;
 461     }
 462     if ( nVal < 0 )
 463         if ( rB.nVal < 0 )
 464             return nVal > rB.nVal;
 465         else
 466             return nVal > -rB.nVal;
 467     else
 468         if ( rB.nVal < 0 )
 469             return nVal < -rB.nVal;
 470         else
 471             return nVal < rB.nVal;
 472 }
 473
 474 BigInt::BigInt( const BigInt& rBigInt )
 475     : nLen(0)
 476     , bIsNeg(false)
 477 {
 478     if ( rBigInt.bIsBig )
 479         memcpy( (void*)this, (const void*)&rBigInt, sizeof( BigInt ) );
 480     else
 481     {
 482         bIsSet = rBigInt.bIsSet;
 483         bIsBig = false;
 484         nVal   = rBigInt.nVal;
 485     }
 486 }
 487
 488 BigInt::BigInt( const OUString& rString )
 489     : nLen(0)
 490 {
 491     bIsSet = true;
 492     bIsNeg = false;
 493     bIsBig = false;
 494     nVal   = 0;
 495
 496     bool bNeg = false;
 497     const sal_Unicode* p = rString.getStr();
 498     if ( *p == '-' )
 499     {
 500         bNeg = true;
 501         p++;
 502     }
 503     while( *p >= '0' && *p <= '9' )
 504     {
 505         *this *= 10;
 506         *this += *p - '0';
 507         p++;
 508     }
 509     if ( bIsBig )
 510         bIsNeg = bNeg;
 511     else if( bNeg )
 512         nVal = -nVal;
 513 }
 514
 515 BigInt::BigInt( double nValue )
 516     : nVal(0)
 517 {
 518     bIsSet = true;
 519
 520     if ( nValue < 0 )
 521     {
 522         nValue *= -1;
 523         bIsNeg  = true;
 524     }
 525     else
 526     {
 527         bIsNeg  = false;
 528     }
 529
 530     if ( nValue < 1 )
 531     {
 532         bIsBig = false;
 533         nVal   = 0;
 534         nLen   = 0;
 535     }
 536     else
 537     {
 538         bIsBig = true;
 539
 540         int i=0;
 541
 542         while ( ( nValue > 65536.0 ) && ( i < MAX_DIGITS ) )
 543         {
 544             nNum[i] = (sal_uInt16) fmod( nValue, 65536.0 );
 545             nValue -= nNum[i];
 546             nValue /= 65536.0;
 547             i++;
 548         }
 549         if ( i < MAX_DIGITS )
 550             nNum[i++] = (sal_uInt16) nValue;
 551
 552         nLen = i;
 553
 554         if ( i < 3 )
 555             Normalize();
 556     }
 557 }
 558
 559 BigInt::BigInt( sal_uInt32 nValue )
 560     : nVal(0)
 561 {
 562     bIsSet  = true;
 563     if ( nValue & 0x80000000UL )
 564     {
 565         bIsBig  = true;
 566         bIsNeg  = false;
 567         nNum[0] = (sal_uInt16)(nValue & 0xffffUL);
 568         nNum[1] = (sal_uInt16)(nValue >> 16);
 569         nLen    = 2;
 570     }
 571     else
 572     {
 573         bIsBig = false;
 574         bIsNeg = false;
 575         nVal   = nValue;
 576         nLen   = 0;
 577     }
 578 }
 579
 580 #if SAL_TYPES_SIZEOFLONG < SAL_TYPES_SIZEOFLONGLONG
 581 BigInt::BigInt( long long nValue )
 582     : nVal(0)
 583 {
 584     bIsSet = true;
 585     bIsNeg = nValue < 0;
 586     nLen = 0;
 587
 588     if ((nValue >= std::numeric_limits<long>::min()) && (nValue <= std::numeric_limits<long>::max()))
 589     {
 590         bIsBig = false;
 591         nVal   = static_cast<long>(nValue);
 592     }
 593     else
 594     {
 595         bIsBig  = true;
 596         unsigned long long nUValue = static_cast<unsigned long long>(bIsNeg ? -nValue : nValue);
 597         for (int i = 0; (i != sizeof(unsigned long long) / 2) && (nUValue != 0); ++i)
 598         {
 599             nNum[i] = static_cast<sal_uInt16>(nUValue & 0xffffUL);
 600             nUValue = nUValue >> 16;
 601             ++nLen;
 602         }
 603     }
 604 }
 605 #endif
 606
 607 BigInt::operator sal_uIntPtr() const
 608 {
 609     if ( !bIsBig )
 610         return (sal_uInt32)nVal;
 611     else if ( nLen == 2 )
 612     {
 613         sal_uInt32 nRet;
 614         nRet  = ((sal_uInt32)nNum[1]) << 16;
 615         nRet += nNum[0];
 616         return nRet;
 617     }
 618     return 0;
 619 }
 620
 621 BigInt::operator double() const
 622 {
 623     if ( !bIsBig )
 624         return (double) nVal;
 625     else
 626     {
 627         int     i = nLen-1;
 628         double  nRet = (double) ((sal_uInt32)nNum[i]);
 629
 630         while ( i )
 631         {
 632             nRet *= 65536.0;
 633             i--;
 634             nRet += (double) ((sal_uInt32)nNum[i]);
 635         }
 636
 637         if ( bIsNeg )
 638             nRet *= -1;
 639
 640         return nRet;
 641     }
 642 }
 643
 644 BigInt& BigInt::operator=( const BigInt& rBigInt )
 645 {
 646     if (this == &rBigInt)
 647         return *this;
 648
 649     if ( rBigInt.bIsBig )
 650         memcpy( (void*)this, (const void*)&rBigInt, sizeof( BigInt ) );
 651     else
 652     {
 653         bIsSet = rBigInt.bIsSet;
 654         bIsBig = false;
 655         nVal   = rBigInt.nVal;
 656     }
 657     return *this;
 658 }
 659
 660 BigInt& BigInt::operator+=( const BigInt& rVal )
 661 {
 662     if ( !bIsBig && !rVal.bIsBig )
 663     {
 664         if( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG
 665             && nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 666         { // No overflows may occur here
 667             nVal += rVal.nVal;
 668             return *this;
 669         }
 670
 671         if( (nVal < 0) != (rVal.nVal < 0) )
 672         { // No overflows may occur here
 673             nVal += rVal.nVal;
 674             return *this;
 675         }
 676     }
 677
 678     BigInt aTmp1, aTmp2;
 679     aTmp1.MakeBigInt( *this );
 680     aTmp2.MakeBigInt( rVal );
 681     aTmp1.AddLong( aTmp2, *this );
 682     Normalize();
 683     return *this;
 684 }
 685
 686 BigInt& BigInt::operator-=( const BigInt& rVal )
 687 {
 688     if ( !bIsBig && !rVal.bIsBig )
 689     {
 690         if ( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG &&
 691              nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 692         { // No overflows may occur here
 693             nVal -= rVal.nVal;
 694             return *this;
 695         }
 696
 697         if ( (nVal < 0) == (rVal.nVal < 0) )
 698         { // No overflows may occur here
 699             nVal -= rVal.nVal;
 700             return *this;
 701         }
 702     }
 703
 704     BigInt aTmp1, aTmp2;
 705     aTmp1.MakeBigInt( *this );
 706     aTmp2.MakeBigInt( rVal );
 707     aTmp1.SubLong( aTmp2, *this );
 708     Normalize();
 709     return *this;
 710 }
 711
 712 BigInt& BigInt::operator*=( const BigInt& rVal )
 713 {
 714     if ( !bIsBig && !rVal.bIsBig
 715          && nVal <= MY_MAXSHORT && rVal.nVal <= MY_MAXSHORT
 716          && nVal >= MY_MINSHORT && rVal.nVal >= MY_MINSHORT )
 717          // TODO: not optimal !!! W.P.
 718     { // No overflows may occur here
 719         nVal *= rVal.nVal;
 720     }
 721     else
 722     {
 723         BigInt aTmp1, aTmp2;
 724         aTmp1.MakeBigInt( rVal );
 725         aTmp2.MakeBigInt( *this );
 726         aTmp1.MultLong(aTmp2, *this);
 727         Normalize();
 728     }
 729     return *this;
 730 }
 731
 732 BigInt& BigInt::operator/=( const BigInt& rVal )
 733 {
 734     if ( !rVal.bIsBig )
 735     {
 736         if ( rVal.nVal == 0 )
 737         {
 738             OSL_FAIL( "BigInt::operator/ --> divide by zero" );
 739             return *this;
 740         }
 741
 742         if ( !bIsBig )
 743         {
 744             // No overflows may occur here
 745             nVal /= rVal.nVal;
 746             return *this;
 747         }
 748
 749         if ( rVal.nVal == 1 )
 750             return *this;
 751
 752         if ( rVal.nVal == -1 )
 753         {
 754             bIsNeg = !bIsNeg;
 755             return *this;
 756         }
 757
 758         if ( rVal.nVal <= (long)0xFFFF && rVal.nVal >= -(long)0xFFFF )
 759         {
 760             // Divide BigInt with an sal_uInt16
 761             sal_uInt16 nTmp;
 762             if ( rVal.nVal < 0 )
 763             {
 764                 nTmp = (sal_uInt16) -rVal.nVal;
 765                 bIsNeg = !bIsNeg;
 766             }
 767             else
 768                 nTmp = (sal_uInt16) rVal.nVal;
 769
 770             Div( nTmp, nTmp );
 771             Normalize();
 772             return *this;
 773         }
 774     }
 775
 776     if ( ABS_IsLess( rVal ) )
 777     {
 778         *this = BigInt( (long)0 );
 779         return *this;
 780     }
 781
 782     // Divide BigInt with BigInt
 783     BigInt aTmp1, aTmp2;
 784     aTmp1.MakeBigInt( *this );
 785     aTmp2.MakeBigInt( rVal );
 786     aTmp1.DivLong(aTmp2, *this);
 787     Normalize();
 788     return *this;
 789 }
 790
 791 BigInt& BigInt::operator%=( const BigInt& rVal )
 792 {
 793     if ( !rVal.bIsBig )
 794     {
 795         if ( rVal.nVal == 0 )
 796         {
 797             OSL_FAIL( "BigInt::operator/ --> divide by zero" );
 798             return *this;
 799         }
 800
 801         if ( !bIsBig )
 802         {
 803             // No overflows may occur here
 804             nVal %= rVal.nVal;
 805             return *this;
 806         }
 807
 808         if ( rVal.nVal <= (long)0xFFFF && rVal.nVal >= -(long)0xFFFF )
 809         {
 810             // Divide Bigint by short
 811             sal_uInt16 nTmp;
 812             if ( rVal.nVal < 0 )
 813             {
 814                 nTmp = (sal_uInt16) -rVal.nVal;
 815                 bIsNeg = !bIsNeg;
 816             }
 817             else
 818                 nTmp = (sal_uInt16) rVal.nVal;
 819
 820             Div( nTmp, nTmp );
 821             *this = BigInt( (long)nTmp );
 822             return *this;
 823         }
 824     }
 825
 826     if ( ABS_IsLess( rVal ) )
 827         return *this;
 828
 829     // Divide BigInt with BigInt
 830     BigInt aTmp1, aTmp2;
 831     aTmp1.MakeBigInt( *this );
 832     aTmp2.MakeBigInt( rVal );
 833     aTmp1.ModLong(aTmp2, *this);
 834     Normalize();
 835     return *this;
 836 }
 837
 838 bool operator==( const BigInt& rVal1, const BigInt& rVal2 )
 839 {
 840     if ( rVal1.bIsBig || rVal2.bIsBig )
 841     {
 842         BigInt nA, nB;
 843         nA.MakeBigInt( rVal1 );
 844         nB.MakeBigInt( rVal2 );
 845         if ( nA.bIsNeg == nB.bIsNeg )
 846         {
 847             if ( nA.nLen == nB.nLen )
 848             {
 849                 int i;
 850                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
 851                 {
 852                 }
 853
 854                 return nA.nNum[i] == nB.nNum[i];
 855             }
 856             return false;
 857         }
 858         return false;
 859     }
 860     return rVal1.nVal == rVal2.nVal;
 861 }
 862
 863 bool operator<( const BigInt& rVal1, const BigInt& rVal2 )
 864 {
 865     if ( rVal1.bIsBig || rVal2.bIsBig )
 866     {
 867         BigInt nA, nB;
 868         nA.MakeBigInt( rVal1 );
 869         nB.MakeBigInt( rVal2 );
 870         if ( nA.bIsNeg == nB.bIsNeg )
 871         {
 872             if ( nA.nLen == nB.nLen )
 873             {
 874                 int i;
 875                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
 876                 {
 877                 }
 878
 879                 if ( nA.bIsNeg )
 880                     return nA.nNum[i] > nB.nNum[i];
 881                 else
 882                     return nA.nNum[i] < nB.nNum[i];
 883             }
 884             if ( nA.bIsNeg )
 885                 return nA.nLen > nB.nLen;
 886             else
 887                 return nA.nLen < nB.nLen;
 888         }
 889         return !nB.bIsNeg;
 890     }
 891     return rVal1.nVal < rVal2.nVal;
 892 }
 893
 894 bool operator >(const BigInt& rVal1, const BigInt& rVal2 )
 895 {
 896     if ( rVal1.bIsBig || rVal2.bIsBig )
 897     {
 898         BigInt nA, nB;
 899         nA.MakeBigInt( rVal1 );
 900         nB.MakeBigInt( rVal2 );
 901         if ( nA.bIsNeg == nB.bIsNeg )
 902         {
 903             if ( nA.nLen == nB.nLen )
 904             {
 905                 int i;
 906                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
 907                 {
 908                 }
 909
 910                 if ( nA.bIsNeg )
 911                     return nA.nNum[i] < nB.nNum[i];
 912                 else
 913                     return nA.nNum[i] > nB.nNum[i];
 914             }
 915             if ( nA.bIsNeg )
 916                 return nA.nLen < nB.nLen;
 917             else
 918                 return nA.nLen > nB.nLen;
 919         }
 920         return !nA.bIsNeg;
 921     }
 922
 923     return rVal1.nVal > rVal2.nVal;
 924 }
 925
 926 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */