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 <math.h>
  21
  22 #include <osl/diagnose.h>
  23 #include <tools/bigint.hxx>
  24
  25
  26 #include <string.h>
  27
  28 /**
  29  * The range in which we can perform add/sub without fear of overflow
  30  */
  31 static const sal_Int32 MY_MAXLONG  = 0x3fffffff;
  32 static const sal_Int32 MY_MINLONG  = -MY_MAXLONG;
  33
  34 /*
  35  * The algorithms for Addition, Subtraction, Multiplication and Division
  36  * of large numbers originate from SEMINUMERICAL ALGORITHMS by
  37  * DONALD E. KNUTH in the series The Art of Computer Programming:
  38  * chapter 4.3.1. The Classical Algorithms.
  39  */
  40
  41 // TODO: Needs conversion to sal_uInt16/INT16/sal_uInt32/sal_Int32
  42 void BigInt::MakeBigInt( const BigInt& rVal )
  43 {
  44     if ( rVal.bIsBig )
  45     {
  46         memcpy( static_cast<void*>(this), static_cast<const void*>(&rVal), sizeof( BigInt ) );
  47         while ( nLen > 1 && nNum[nLen-1] == 0 )
  48             nLen--;
  49     }
  50     else
  51     {
  52         nVal = rVal.nVal;
  53         bIsBig = true;
  54         sal_uInt32 nTmp;
  55         if (nVal < 0)
  56         {
  57             bIsNeg = true;
  58             nTmp = -static_cast<sal_Int64>(nVal);
  59         }
  60         else
  61         {
  62             bIsNeg = false;
  63             nTmp = nVal;
  64         }
  65
  66         nNum[0] = static_cast<sal_uInt16>(nTmp & 0xffffL);
  67         nNum[1] = static_cast<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 = (static_cast<sal_Int32>(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 = static_cast<sal_uInt32>(rVal.nNum[i]) * static_cast<sal_uInt32>(nMul) + nK;
 111         nK            = static_cast<sal_uInt16>(nTmp >> 16);
 112         nNum[i] = static_cast<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 = static_cast<sal_uInt32>(nNum[i]) + (nK << 16);
 133         nNum[i] = static_cast<sal_uInt16>(nTmp / nDiv);
 134         nK            = nTmp % nDiv;
 135     }
 136     rRem = static_cast<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         sal_Int32 k;
 180         sal_Int32 nZ = 0;
 181         for (i = 0, k = 0; i < len; i++) {
 182             nZ = static_cast<sal_Int32>(nNum[i]) + static_cast<sal_Int32>(rB.nNum[i]) + k;
 183             if (nZ & 0xff0000L)
 184                 k = 1;
 185             else
 186                 k = 0;
 187             rErg.nNum[i] = static_cast<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         sal_Int32 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 = static_cast<sal_Int32>(nNum[i]) - static_cast<sal_Int32>(rB.nNum[i]) + k;
 243                 if (nZ < 0)
 244                     k = -1;
 245                 else
 246                     k = 0;
 247                 rErg.nNum[i] = static_cast<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 = static_cast<sal_Int32>(rB.nNum[i]) - static_cast<sal_Int32>(nNum[i]) + k;
 256                 if (nZ < 0)
 257                     k = -1;
 258                 else
 259                     k = 0;
 260                 rErg.nNum[i] = static_cast<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 = static_cast<sal_uInt32>(nNum[i]) * static_cast<sal_uInt32>(rB.nNum[j]) +
 302                  static_cast<sal_uInt32>(rErg.nNum[i + j]) + k;
 303             rErg.nNum[i + j] = static_cast<sal_uInt16>(nZ & 0xffffU);
 304             k = nZ >> 16;
 305         }
 306         rErg.nNum[i + j] = static_cast<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     sal_uInt16  nLenB  = rB.nLen;
 315     sal_uInt16  nLenB1 = rB.nLen - 1;
 316     BigInt aTmpA, aTmpB;
 317
 318     nMult = static_cast<sal_uInt16>(0x10000L / (static_cast<sal_Int32>(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         sal_uInt32 nTmp = ( static_cast<sal_uInt32>(aTmpA.nNum[j]) << 16 ) + aTmpA.nNum[j - 1];
 332         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 333             nQ = 0xFFFF;
 334         else
 335             nQ = static_cast<sal_uInt16>(nTmp / aTmpB.nNum[nLenB1]);
 336
 337         if ( (static_cast<sal_uInt32>(aTmpB.nNum[nLenB1 - 1]) * nQ) >
 338             ((nTmp - static_cast<sal_uInt32>(aTmpB.nNum[nLenB1]) * nQ) << 16) + aTmpA.nNum[j - 2])
 339             nQ--;
 340         // Start division
 341         nK = 0;
 342         for (i = 0; i < nLenB; i++)
 343         {
 344             nTmp = static_cast<sal_uInt32>(aTmpA.nNum[j - nLenB + i])
 345                    - (static_cast<sal_uInt32>(aTmpB.nNum[i]) * nQ)
 346                    - nK;
 347             aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp);
 348             nK = static_cast<sal_uInt16>(nTmp >> 16);
 349             if ( nK )
 350                 nK = static_cast<sal_uInt16>(0x10000U - nK);
 351         }
 352         sal_uInt16& rNum( aTmpA.nNum[j - nLenB + i] );
 353         rNum -= nK;
 354         if (aTmpA.nNum[j - nLenB + i] == 0)
 355             rErg.nNum[j - nLenB] = nQ;
 356         else
 357         {
 358             rErg.nNum[j - nLenB] = nQ - 1;
 359             nK = 0;
 360             for (i = 0; i < nLenB; i++)
 361             {
 362                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 363                 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp & 0xFFFFL);
 364                 if (nTmp & 0xFFFF0000L)
 365                     nK = 1;
 366                 else
 367                     nK = 0;
 368             }
 369         }
 370     }
 371
 372     rErg.bIsNeg = bIsNeg != rB.bIsNeg;
 373     rErg.bIsBig = true;
 374     rErg.nLen   = nLen - rB.nLen + 1;
 375 }
 376
 377 void BigInt::ModLong( const BigInt& rB, BigInt& rErg ) const
 378 {
 379     sal_uInt16 i, j;
 380     sal_uInt16 nK, nQ, nMult;
 381     sal_Int16  nLenB  = rB.nLen;
 382     sal_Int16  nLenB1 = rB.nLen - 1;
 383     BigInt aTmpA, aTmpB;
 384
 385     nMult = static_cast<sal_uInt16>(0x10000L / (static_cast<sal_Int32>(rB.nNum[nLenB1]) + 1));
 386
 387     aTmpA.Mult( *this, nMult);
 388     if ( aTmpA.nLen == nLen )
 389     {
 390         aTmpA.nNum[aTmpA.nLen] = 0;
 391         aTmpA.nLen++;
 392     }
 393
 394     aTmpB.Mult( rB, nMult);
 395
 396     for (j = aTmpA.nLen - 1; j >= nLenB; j--)
 397     { // Guess divisor
 398         sal_uInt32 nTmp = ( static_cast<sal_uInt32>(aTmpA.nNum[j]) << 16 ) + aTmpA.nNum[j - 1];
 399         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 400             nQ = 0xFFFF;
 401         else
 402             nQ = static_cast<sal_uInt16>(nTmp / aTmpB.nNum[nLenB1]);
 403
 404         if ( (static_cast<sal_uInt32>(aTmpB.nNum[nLenB1 - 1]) * nQ) >
 405             ((nTmp - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
 406             nQ--;
 407         // Start division
 408         nK = 0;
 409         for (i = 0; i < nLenB; i++)
 410         {
 411             nTmp = static_cast<sal_uInt32>(aTmpA.nNum[j - nLenB + i])
 412                    - (static_cast<sal_uInt32>(aTmpB.nNum[i]) * nQ)
 413                    - nK;
 414             aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp);
 415             nK = static_cast<sal_uInt16>(nTmp >> 16);
 416             if ( nK )
 417                 nK = static_cast<sal_uInt16>(0x10000U - nK);
 418         }
 419         sal_uInt16& rNum( aTmpA.nNum[j - nLenB + i] );
 420         rNum = rNum - nK;
 421         if (aTmpA.nNum[j - nLenB + i] == 0)
 422             rErg.nNum[j - nLenB] = nQ;
 423         else
 424         {
 425             rErg.nNum[j - nLenB] = nQ - 1;
 426             nK = 0;
 427             for (i = 0; i < nLenB; i++) {
 428                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 429                 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp & 0xFFFFL);
 430                 if (nTmp & 0xFFFF0000L)
 431                     nK = 1;
 432                 else
 433                     nK = 0;
 434             }
 435         }
 436     }
 437
 438     rErg = aTmpA;
 439     rErg.Div( nMult, nQ );
 440 }
 441
 442 bool BigInt::ABS_IsLess( const BigInt& rB ) const
 443 {
 444     if (bIsBig || rB.bIsBig)
 445     {
 446         BigInt nA, nB;
 447         nA.MakeBigInt( *this );
 448         nB.MakeBigInt( rB );
 449         if (nA.nLen == nB.nLen)
 450         {
 451             int i;
 452             for (i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i--)
 453             {
 454             }
 455             return nA.nNum[i] < nB.nNum[i];
 456         }
 457         else
 458             return nA.nLen < nB.nLen;
 459     }
 460     if ( nVal < 0 )
 461         if ( rB.nVal < 0 )
 462             return nVal > rB.nVal;
 463         else
 464             return nVal > -rB.nVal;
 465     else
 466         if ( rB.nVal < 0 )
 467             return nVal < -rB.nVal;
 468         else
 469             return nVal < rB.nVal;
 470 }
 471
 472 BigInt::BigInt( const BigInt& rBigInt )
 473     : nLen(0)
 474     , bIsNeg(false)
 475 {
 476     if ( rBigInt.bIsBig )
 477         memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt), sizeof( BigInt ) );
 478     else
 479     {
 480         bIsSet = rBigInt.bIsSet;
 481         bIsBig = false;
 482         nVal   = rBigInt.nVal;
 483     }
 484 }
 485
 486 BigInt::BigInt( const OUString& rString )
 487     : nLen(0)
 488 {
 489     bIsSet = true;
 490     bIsNeg = false;
 491     bIsBig = false;
 492     nVal   = 0;
 493
 494     bool bNeg = false;
 495     const sal_Unicode* p = rString.getStr();
 496     if ( *p == '-' )
 497     {
 498         bNeg = true;
 499         p++;
 500     }
 501     while( *p >= '0' && *p <= '9' )
 502     {
 503         *this *= 10;
 504         *this += *p - '0';
 505         p++;
 506     }
 507     if ( bIsBig )
 508         bIsNeg = bNeg;
 509     else if( bNeg )
 510         nVal = -nVal;
 511 }
 512
 513 BigInt::BigInt( double nValue )
 514     : nVal(0)
 515 {
 516     bIsSet = true;
 517
 518     if ( nValue < 0 )
 519     {
 520         nValue *= -1;
 521         bIsNeg  = true;
 522     }
 523     else
 524     {
 525         bIsNeg  = false;
 526     }
 527
 528     if ( nValue < 1 )
 529     {
 530         bIsBig = false;
 531         nVal   = 0;
 532         nLen   = 0;
 533     }
 534     else
 535     {
 536         bIsBig = true;
 537
 538         int i=0;
 539
 540         while ( ( nValue > 65536.0 ) && ( i < MAX_DIGITS ) )
 541         {
 542             nNum[i] = static_cast<sal_uInt16>(fmod( nValue, 65536.0 ));
 543             nValue -= nNum[i];
 544             nValue /= 65536.0;
 545             i++;
 546         }
 547         if ( i < MAX_DIGITS )
 548             nNum[i++] = static_cast<sal_uInt16>(nValue);
 549
 550         nLen = i;
 551
 552         if ( i < 3 )
 553             Normalize();
 554     }
 555 }
 556
 557 BigInt::BigInt( sal_uInt32 nValue )
 558     : nVal(0)
 559 {
 560     bIsSet  = true;
 561     if ( nValue & 0x80000000U )
 562     {
 563         bIsBig  = true;
 564         bIsNeg  = false;
 565         nNum[0] = static_cast<sal_uInt16>(nValue & 0xffffU);
 566         nNum[1] = static_cast<sal_uInt16>(nValue >> 16);
 567         nLen    = 2;
 568     }
 569     else
 570     {
 571         bIsBig = false;
 572         bIsNeg = false;
 573         nVal   = nValue;
 574         nLen   = 0;
 575     }
 576 }
 577
 578 BigInt::BigInt( sal_Int64 nValue )
 579     : nVal(0)
 580 {
 581     bIsSet = true;
 582     bIsNeg = nValue < 0;
 583     nLen = 0;
 584
 585     if ((nValue >= SAL_MIN_INT32) && (nValue <= SAL_MAX_INT32))
 586     {
 587         bIsBig = false;
 588         nVal   = static_cast<sal_Int32>(nValue);
 589     }
 590     else
 591     {
 592         bIsBig  = true;
 593         sal_uInt64 nUValue = static_cast<sal_uInt64>(bIsNeg ? -nValue : nValue);
 594         for (int i = 0; (i != sizeof(sal_uInt64) / 2) && (nUValue != 0); ++i)
 595         {
 596             nNum[i] = static_cast<sal_uInt16>(nUValue & 0xffffUL);
 597             nUValue = nUValue >> 16;
 598             ++nLen;
 599         }
 600     }
 601 }
 602
 603 BigInt::operator double() const
 604 {
 605     if ( !bIsBig )
 606         return static_cast<double>(nVal);
 607     else
 608     {
 609         int     i = nLen-1;
 610         double  nRet = static_cast<double>(static_cast<sal_uInt32>(nNum[i]));
 611
 612         while ( i )
 613         {
 614             nRet *= 65536.0;
 615             i--;
 616             nRet += static_cast<double>(static_cast<sal_uInt32>(nNum[i]));
 617         }
 618
 619         if ( bIsNeg )
 620             nRet *= -1;
 621
 622         return nRet;
 623     }
 624 }
 625
 626 BigInt& BigInt::operator=( const BigInt& rBigInt )
 627 {
 628     if (this == &rBigInt)
 629         return *this;
 630
 631     if ( rBigInt.bIsBig )
 632         memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt), sizeof( BigInt ) );
 633     else
 634     {
 635         bIsSet = rBigInt.bIsSet;
 636         bIsBig = false;
 637         nVal   = rBigInt.nVal;
 638     }
 639     return *this;
 640 }
 641
 642 BigInt& BigInt::operator+=( const BigInt& rVal )
 643 {
 644     if ( !bIsBig && !rVal.bIsBig )
 645     {
 646         if( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG
 647             && nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 648         { // No overflows may occur here
 649             nVal += rVal.nVal;
 650             return *this;
 651         }
 652
 653         if( (nVal < 0) != (rVal.nVal < 0) )
 654         { // No overflows may occur here
 655             nVal += rVal.nVal;
 656             return *this;
 657         }
 658     }
 659
 660     BigInt aTmp1, aTmp2;
 661     aTmp1.MakeBigInt( *this );
 662     aTmp2.MakeBigInt( rVal );
 663     aTmp1.AddLong( aTmp2, *this );
 664     Normalize();
 665     return *this;
 666 }
 667
 668 BigInt& BigInt::operator-=( const BigInt& rVal )
 669 {
 670     if ( !bIsBig && !rVal.bIsBig )
 671     {
 672         if ( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG &&
 673              nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 674         { // No overflows may occur here
 675             nVal -= rVal.nVal;
 676             return *this;
 677         }
 678
 679         if ( (nVal < 0) == (rVal.nVal < 0) )
 680         { // No overflows may occur here
 681             nVal -= rVal.nVal;
 682             return *this;
 683         }
 684     }
 685
 686     BigInt aTmp1, aTmp2;
 687     aTmp1.MakeBigInt( *this );
 688     aTmp2.MakeBigInt( rVal );
 689     aTmp1.SubLong( aTmp2, *this );
 690     Normalize();
 691     return *this;
 692 }
 693
 694 BigInt& BigInt::operator*=( const BigInt& rVal )
 695 {
 696     static const sal_Int32 MY_MAXSHORT = 0x00007fff;
 697     static const sal_Int32 MY_MINSHORT = -MY_MAXSHORT;
 698
 699     if ( !bIsBig && !rVal.bIsBig
 700          && nVal <= MY_MAXSHORT && rVal.nVal <= MY_MAXSHORT
 701          && nVal >= MY_MINSHORT && rVal.nVal >= MY_MINSHORT )
 702          // TODO: not optimal !!! W.P.
 703     { // No overflows may occur here
 704         nVal *= rVal.nVal;
 705     }
 706     else
 707     {
 708         BigInt aTmp1, aTmp2;
 709         aTmp1.MakeBigInt( rVal );
 710         aTmp2.MakeBigInt( *this );
 711         aTmp1.MultLong(aTmp2, *this);
 712         Normalize();
 713     }
 714     return *this;
 715 }
 716
 717 BigInt& BigInt::operator/=( const BigInt& rVal )
 718 {
 719     if ( !rVal.bIsBig )
 720     {
 721         if ( rVal.nVal == 0 )
 722         {
 723             OSL_FAIL( "BigInt::operator/ --> divide by zero" );
 724             return *this;
 725         }
 726
 727         if ( !bIsBig )
 728         {
 729             // No overflows may occur here
 730             nVal /= rVal.nVal;
 731             return *this;
 732         }
 733
 734         if ( rVal.nVal == 1 )
 735             return *this;
 736
 737         if ( rVal.nVal == -1 )
 738         {
 739             bIsNeg = !bIsNeg;
 740             return *this;
 741         }
 742
 743         if ( rVal.nVal <= 0xFFFF && rVal.nVal >= -0xFFFF )
 744         {
 745             // Divide BigInt with an sal_uInt16
 746             sal_uInt16 nTmp;
 747             if ( rVal.nVal < 0 )
 748             {
 749                 nTmp = static_cast<sal_uInt16>(-rVal.nVal);
 750                 bIsNeg = !bIsNeg;
 751             }
 752             else
 753                 nTmp = static_cast<sal_uInt16>(rVal.nVal);
 754
 755             Div( nTmp, nTmp );
 756             Normalize();
 757             return *this;
 758         }
 759     }
 760
 761     if ( ABS_IsLess( rVal ) )
 762     {
 763         *this = BigInt( 0 );
 764         return *this;
 765     }
 766
 767     // Divide BigInt with BigInt
 768     BigInt aTmp1, aTmp2;
 769     aTmp1.MakeBigInt( *this );
 770     aTmp2.MakeBigInt( rVal );
 771     aTmp1.DivLong(aTmp2, *this);
 772     Normalize();
 773     return *this;
 774 }
 775
 776 BigInt& BigInt::operator%=( const BigInt& rVal )
 777 {
 778     if ( !rVal.bIsBig )
 779     {
 780         if ( rVal.nVal == 0 )
 781         {
 782             OSL_FAIL( "BigInt::operator/ --> divide by zero" );
 783             return *this;
 784         }
 785
 786         if ( !bIsBig )
 787         {
 788             // No overflows may occur here
 789             nVal %= rVal.nVal;
 790             return *this;
 791         }
 792
 793         if ( rVal.nVal <= 0xFFFF && rVal.nVal >= -0xFFFF )
 794         {
 795             // Divide Bigint by int16
 796             sal_uInt16 nTmp;
 797             if ( rVal.nVal < 0 )
 798             {
 799                 nTmp = static_cast<sal_uInt16>(-rVal.nVal);
 800                 bIsNeg = !bIsNeg;
 801             }
 802             else
 803                 nTmp = static_cast<sal_uInt16>(rVal.nVal);
 804
 805             Div( nTmp, nTmp );
 806             *this = BigInt( nTmp );
 807             return *this;
 808         }
 809     }
 810
 811     if ( ABS_IsLess( rVal ) )
 812         return *this;
 813
 814     // Divide BigInt with BigInt
 815     BigInt aTmp1, aTmp2;
 816     aTmp1.MakeBigInt( *this );
 817     aTmp2.MakeBigInt( rVal );
 818     aTmp1.ModLong(aTmp2, *this);
 819     Normalize();
 820     return *this;
 821 }
 822
 823 bool operator==( const BigInt& rVal1, const BigInt& rVal2 )
 824 {
 825     if ( rVal1.bIsBig || rVal2.bIsBig )
 826     {
 827         BigInt nA, nB;
 828         nA.MakeBigInt( rVal1 );
 829         nB.MakeBigInt( rVal2 );
 830         if ( nA.bIsNeg == nB.bIsNeg )
 831         {
 832             if ( nA.nLen == nB.nLen )
 833             {
 834                 int i;
 835                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
 836                 {
 837                 }
 838
 839                 return nA.nNum[i] == nB.nNum[i];
 840             }
 841             return false;
 842         }
 843         return false;
 844     }
 845     return rVal1.nVal == rVal2.nVal;
 846 }
 847
 848 bool operator<( const BigInt& rVal1, const BigInt& rVal2 )
 849 {
 850     if ( rVal1.bIsBig || rVal2.bIsBig )
 851     {
 852         BigInt nA, nB;
 853         nA.MakeBigInt( rVal1 );
 854         nB.MakeBigInt( rVal2 );
 855         if ( nA.bIsNeg == nB.bIsNeg )
 856         {
 857             if ( nA.nLen == nB.nLen )
 858             {
 859                 int i;
 860                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
 861                 {
 862                 }
 863
 864                 if ( nA.bIsNeg )
 865                     return nA.nNum[i] > nB.nNum[i];
 866                 else
 867                     return nA.nNum[i] < nB.nNum[i];
 868             }
 869             if ( nA.bIsNeg )
 870                 return nA.nLen > nB.nLen;
 871             else
 872                 return nA.nLen < nB.nLen;
 873         }
 874         return !nB.bIsNeg;
 875     }
 876     return rVal1.nVal < rVal2.nVal;
 877 }
 878
 879 bool operator >(const BigInt& rVal1, const BigInt& rVal2 )
 880 {
 881     if ( rVal1.bIsBig || rVal2.bIsBig )
 882     {
 883         BigInt nA, nB;
 884         nA.MakeBigInt( rVal1 );
 885         nB.MakeBigInt( rVal2 );
 886         if ( nA.bIsNeg == nB.bIsNeg )
 887         {
 888             if ( nA.nLen == nB.nLen )
 889             {
 890                 int i;
 891                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
 892                 {
 893                 }
 894
 895                 if ( nA.bIsNeg )
 896                     return nA.nNum[i] < nB.nNum[i];
 897                 else
 898                     return nA.nNum[i] > nB.nNum[i];
 899             }
 900             if ( nA.bIsNeg )
 901                 return nA.nLen < nB.nLen;
 902             else
 903                 return nA.nLen > nB.nLen;
 904         }
 905         return !nA.bIsNeg;
 906     }
 907
 908     return rVal1.nVal > rVal2.nVal;
 909 }
 910
 911 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */