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 #include <algorithm>
  26 #include <string.h>
  27
  28 /**
  29  * The range in which we can perform add/sub without fear of overflow
  30  */
  31 const sal_Int32 MY_MAXLONG  = 0x3fffffff;
  32 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.nLen != 0 )
  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         sal_uInt32 nTmp;
  54         if (nVal < 0)
  55         {
  56             bIsNeg = true;
  57             nTmp = -static_cast<sal_Int64>(nVal);
  58         }
  59         else
  60         {
  61             bIsNeg = false;
  62             nTmp = nVal;
  63         }
  64
  65         nNum[0] = static_cast<sal_uInt16>(nTmp & 0xffffL);
  66         nNum[1] = static_cast<sal_uInt16>(nTmp >> 16);
  67         if ( nTmp & 0xffff0000L )
  68             nLen = 2;
  69         else
  70             nLen = 1;
  71     }
  72 }
  73
  74 void BigInt::Normalize()
  75 {
  76     if ( nLen != 0 )
  77     {
  78         while ( nLen > 1 && nNum[nLen-1] == 0 )
  79             nLen--;
  80
  81         if ( nLen < 3 )
  82         {
  83             sal_Int32 newVal;
  84             if ( nLen < 2 )
  85                 newVal = nNum[0];
  86             else if ( nNum[1] & 0x8000 )
  87                 return;
  88             else
  89                 newVal = (static_cast<sal_Int32>(nNum[1]) << 16) + nNum[0];
  90
  91             nLen = 0;
  92             nVal = newVal;
  93
  94             if ( bIsNeg )
  95                 nVal = -nVal;
  96         }
  97         // else nVal is undefined !!! W.P.
  98     }
  99     // why? nVal is undefined ??? W.P.
 100     else if ( nVal & 0xFFFF0000L )
 101         nLen = 2;
 102     else
 103         nLen = 1;
 104 }
 105
 106 void BigInt::Mult( const BigInt &rVal, sal_uInt16 nMul )
 107 {
 108     sal_uInt16 nK = 0;
 109     for ( int i = 0; i < rVal.nLen; i++ )
 110     {
 111         sal_uInt32 nTmp = static_cast<sal_uInt32>(rVal.nNum[i]) * static_cast<sal_uInt32>(nMul) + nK;
 112         nK            = static_cast<sal_uInt16>(nTmp >> 16);
 113         nNum[i] = static_cast<sal_uInt16>(nTmp);
 114     }
 115
 116     if ( nK )
 117     {
 118         nNum[rVal.nLen] = nK;
 119         nLen = rVal.nLen + 1;
 120     }
 121     else
 122         nLen = rVal.nLen;
 123
 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     }
 199     // If one of the values is negative, perform subtraction instead
 200     else if (bIsNeg)
 201     {
 202         bIsNeg = false;
 203         rB.SubLong(*this, rErg);
 204         bIsNeg = true;
 205     }
 206     else
 207     {
 208         rB.bIsNeg = false;
 209         SubLong(rB, rErg);
 210         rB.bIsNeg = true;
 211     }
 212 }
 213
 214 void BigInt::SubLong( BigInt& rB, BigInt& rErg )
 215 {
 216     if ( bIsNeg == rB.bIsNeg )
 217     {
 218         int  i;
 219         char len;
 220         sal_Int32 nZ, k;
 221
 222         // if length of the two values differ, fill remaining positions
 223         // of the smaller value with zeros.
 224         if (nLen >= rB.nLen)
 225         {
 226             len = nLen;
 227             for (i = rB.nLen; i < len; i++)
 228                 rB.nNum[i] = 0;
 229         }
 230         else
 231         {
 232             len = rB.nLen;
 233             for (i = nLen; i < len; i++)
 234                 nNum[i] = 0;
 235         }
 236
 237         if ( IsLess(rB) )
 238         {
 239             for (i = 0, k = 0; i < len; i++)
 240             {
 241                 nZ = static_cast<sal_Int32>(nNum[i]) - static_cast<sal_Int32>(rB.nNum[i]) + k;
 242                 if (nZ < 0)
 243                     k = -1;
 244                 else
 245                     k = 0;
 246                 rErg.nNum[i] = static_cast<sal_uInt16>(nZ & 0xffffL);
 247             }
 248             rErg.bIsNeg = bIsNeg;
 249         }
 250         else
 251         {
 252             for (i = 0, k = 0; i < len; i++)
 253             {
 254                 nZ = static_cast<sal_Int32>(rB.nNum[i]) - static_cast<sal_Int32>(nNum[i]) + k;
 255                 if (nZ < 0)
 256                     k = -1;
 257                 else
 258                     k = 0;
 259                 rErg.nNum[i] = static_cast<sal_uInt16>(nZ & 0xffffL);
 260             }
 261             // if a < b, revert sign
 262             rErg.bIsNeg = !bIsNeg;
 263         }
 264         rErg.nLen   = len;
 265     }
 266     // If one of the values is negative, perform addition instead
 267     else if (bIsNeg)
 268     {
 269         bIsNeg = false;
 270         AddLong(rB, rErg);
 271         bIsNeg = true;
 272         rErg.bIsNeg = true;
 273     }
 274     else
 275     {
 276         rB.bIsNeg = false;
 277         AddLong(rB, rErg);
 278         rB.bIsNeg = true;
 279         rErg.bIsNeg = false;
 280     }
 281 }
 282
 283 void BigInt::MultLong( const BigInt& rB, BigInt& rErg ) const
 284 {
 285     int        i, j;
 286     sal_uInt32 nZ, k;
 287
 288     rErg.bIsNeg = bIsNeg != rB.bIsNeg;
 289     rErg.nLen   = nLen + rB.nLen;
 290
 291     for (i = 0; i < rErg.nLen; i++)
 292         rErg.nNum[i] = 0;
 293
 294     for (j = 0; j < rB.nLen; j++)
 295     {
 296         for (i = 0, k = 0; i < nLen; i++)
 297         {
 298             nZ = static_cast<sal_uInt32>(nNum[i]) * static_cast<sal_uInt32>(rB.nNum[j]) +
 299                  static_cast<sal_uInt32>(rErg.nNum[i + j]) + k;
 300             rErg.nNum[i + j] = static_cast<sal_uInt16>(nZ & 0xffffU);
 301             k = nZ >> 16;
 302         }
 303         rErg.nNum[i + j] = static_cast<sal_uInt16>(k);
 304     }
 305 }
 306
 307 void BigInt::DivLong( const BigInt& rB, BigInt& rErg ) const
 308 {
 309     int    i, j;
 310     sal_uInt16 nK, nQ, nMult;
 311     sal_uInt16  nLenB  = rB.nLen;
 312     sal_uInt16  nLenB1 = rB.nLen - 1;
 313     BigInt aTmpA, aTmpB;
 314
 315     nMult = static_cast<sal_uInt16>(0x10000L / (static_cast<sal_Int32>(rB.nNum[nLenB1]) + 1));
 316
 317     aTmpA.Mult( *this, nMult );
 318     if ( aTmpA.nLen == nLen )
 319     {
 320         aTmpA.nNum[aTmpA.nLen] = 0;
 321         aTmpA.nLen++;
 322     }
 323
 324     aTmpB.Mult( rB, nMult );
 325
 326     for (j = aTmpA.nLen - 1; j >= nLenB; j--)
 327     { // guess divisor
 328         sal_uInt32 nTmp = ( static_cast<sal_uInt32>(aTmpA.nNum[j]) << 16 ) + aTmpA.nNum[j - 1];
 329         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 330             nQ = 0xFFFF;
 331         else
 332             nQ = static_cast<sal_uInt16>(nTmp / aTmpB.nNum[nLenB1]);
 333
 334         if ( (static_cast<sal_uInt32>(aTmpB.nNum[nLenB1 - 1]) * nQ) >
 335             ((nTmp - static_cast<sal_uInt32>(aTmpB.nNum[nLenB1]) * nQ) << 16) + aTmpA.nNum[j - 2])
 336             nQ--;
 337         // Start division
 338         nK = 0;
 339         for (i = 0; i < nLenB; i++)
 340         {
 341             nTmp = static_cast<sal_uInt32>(aTmpA.nNum[j - nLenB + i])
 342                    - (static_cast<sal_uInt32>(aTmpB.nNum[i]) * nQ)
 343                    - nK;
 344             aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp);
 345             nK = static_cast<sal_uInt16>(nTmp >> 16);
 346             if ( nK )
 347                 nK = static_cast<sal_uInt16>(0x10000U - nK);
 348         }
 349         sal_uInt16& rNum( aTmpA.nNum[j - nLenB + i] );
 350         rNum -= nK;
 351         if (aTmpA.nNum[j - nLenB + i] == 0)
 352             rErg.nNum[j - nLenB] = nQ;
 353         else
 354         {
 355             rErg.nNum[j - nLenB] = nQ - 1;
 356             nK = 0;
 357             for (i = 0; i < nLenB; i++)
 358             {
 359                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 360                 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp & 0xFFFFL);
 361                 if (nTmp & 0xFFFF0000L)
 362                     nK = 1;
 363                 else
 364                     nK = 0;
 365             }
 366         }
 367     }
 368
 369     rErg.bIsNeg = bIsNeg != rB.bIsNeg;
 370     rErg.nLen   = nLen - rB.nLen + 1;
 371 }
 372
 373 void BigInt::ModLong( const BigInt& rB, BigInt& rErg ) const
 374 {
 375     sal_uInt16 i, j;
 376     sal_uInt16 nK, nQ, nMult;
 377     sal_Int16  nLenB  = rB.nLen;
 378     sal_Int16  nLenB1 = rB.nLen - 1;
 379     BigInt aTmpA, aTmpB;
 380
 381     nMult = static_cast<sal_uInt16>(0x10000L / (static_cast<sal_Int32>(rB.nNum[nLenB1]) + 1));
 382
 383     aTmpA.Mult( *this, nMult);
 384     if ( aTmpA.nLen == nLen )
 385     {
 386         aTmpA.nNum[aTmpA.nLen] = 0;
 387         aTmpA.nLen++;
 388     }
 389
 390     aTmpB.Mult( rB, nMult);
 391
 392     for (j = aTmpA.nLen - 1; j >= nLenB; j--)
 393     { // Guess divisor
 394         sal_uInt32 nTmp = ( static_cast<sal_uInt32>(aTmpA.nNum[j]) << 16 ) + aTmpA.nNum[j - 1];
 395         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 396             nQ = 0xFFFF;
 397         else
 398             nQ = static_cast<sal_uInt16>(nTmp / aTmpB.nNum[nLenB1]);
 399
 400         if ( (static_cast<sal_uInt32>(aTmpB.nNum[nLenB1 - 1]) * nQ) >
 401             ((nTmp - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
 402             nQ--;
 403         // Start division
 404         nK = 0;
 405         for (i = 0; i < nLenB; i++)
 406         {
 407             nTmp = static_cast<sal_uInt32>(aTmpA.nNum[j - nLenB + i])
 408                    - (static_cast<sal_uInt32>(aTmpB.nNum[i]) * nQ)
 409                    - nK;
 410             aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp);
 411             nK = static_cast<sal_uInt16>(nTmp >> 16);
 412             if ( nK )
 413                 nK = static_cast<sal_uInt16>(0x10000U - nK);
 414         }
 415         sal_uInt16& rNum( aTmpA.nNum[j - nLenB + i] );
 416         rNum = rNum - nK;
 417         if (aTmpA.nNum[j - nLenB + i] == 0)
 418             rErg.nNum[j - nLenB] = nQ;
 419         else
 420         {
 421             rErg.nNum[j - nLenB] = nQ - 1;
 422             nK = 0;
 423             for (i = 0; i < nLenB; i++) {
 424                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 425                 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp & 0xFFFFL);
 426                 if (nTmp & 0xFFFF0000L)
 427                     nK = 1;
 428                 else
 429                     nK = 0;
 430             }
 431         }
 432     }
 433
 434     rErg = aTmpA;
 435     rErg.Div( nMult, nQ );
 436 }
 437
 438 bool BigInt::ABS_IsLess( const BigInt& rB ) const
 439 {
 440     if (nLen != 0 || rB.nLen != 0)
 441     {
 442         BigInt nA, nB;
 443         nA.MakeBigInt( *this );
 444         nB.MakeBigInt( rB );
 445         if (nA.nLen == nB.nLen)
 446         {
 447             int i;
 448             for (i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i--)
 449             {
 450             }
 451             return nA.nNum[i] < nB.nNum[i];
 452         }
 453         else
 454             return nA.nLen < nB.nLen;
 455     }
 456     if ( nVal < 0 )
 457         if ( rB.nVal < 0 )
 458             return nVal > rB.nVal;
 459         else
 460             return nVal > -rB.nVal;
 461     else
 462         if ( rB.nVal < 0 )
 463             return nVal < -rB.nVal;
 464         else
 465             return nVal < rB.nVal;
 466 }
 467
 468 BigInt::BigInt( const BigInt& rBigInt )
 469     : nLen(0)
 470     , bIsNeg(false)
 471 {
 472     if ( rBigInt.nLen != 0 )
 473         memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt), sizeof( BigInt ) );
 474     else
 475         nVal = rBigInt.nVal;
 476 }
 477
 478 BigInt::BigInt( std::u16string_view rString )
 479     : nLen(0)
 480 {
 481     bIsNeg = false;
 482     nVal   = 0;
 483
 484     bool bNeg = false;
 485     auto p = rString.begin();
 486     auto pEnd = rString.end();
 487     if (p == pEnd)
 488         return;
 489     if ( *p == '-' )
 490     {
 491         bNeg = true;
 492         p++;
 493     }
 494     if (p == pEnd)
 495         return;
 496     while( p != pEnd && *p >= '0' && *p <= '9' )
 497     {
 498         *this *= 10;
 499         *this += *p - '0';
 500         p++;
 501     }
 502     if ( nLen != 0 )
 503         bIsNeg = bNeg;
 504     else if( bNeg )
 505         nVal = -nVal;
 506 }
 507
 508 BigInt::BigInt( double nValue )
 509     : nVal(0)
 510 {
 511     if ( nValue < 0 )
 512     {
 513         nValue *= -1;
 514         bIsNeg  = true;
 515     }
 516     else
 517     {
 518         bIsNeg  = false;
 519     }
 520
 521     if ( nValue < 1 )
 522     {
 523         nVal   = 0;
 524         nLen   = 0;
 525     }
 526     else
 527     {
 528         int i=0;
 529
 530         while ( ( nValue > 65536.0 ) && ( i < MAX_DIGITS ) )
 531         {
 532             nNum[i] = static_cast<sal_uInt16>(fmod( nValue, 65536.0 ));
 533             nValue -= nNum[i];
 534             nValue /= 65536.0;
 535             i++;
 536         }
 537         if ( i < MAX_DIGITS )
 538             nNum[i++] = static_cast<sal_uInt16>(nValue);
 539
 540         nLen = i;
 541
 542         if ( i < 3 )
 543             Normalize();
 544     }
 545 }
 546
 547 BigInt::BigInt( sal_uInt32 nValue )
 548     : nVal(0)
 549 {
 550     if ( nValue & 0x80000000U )
 551     {
 552         bIsNeg  = false;
 553         nNum[0] = static_cast<sal_uInt16>(nValue & 0xffffU);
 554         nNum[1] = static_cast<sal_uInt16>(nValue >> 16);
 555         nLen    = 2;
 556     }
 557     else
 558     {
 559         bIsNeg = false;
 560         nVal   = nValue;
 561         nLen   = 0;
 562     }
 563 }
 564
 565 BigInt::BigInt( sal_Int64 nValue )
 566     : nVal(0)
 567 {
 568     bIsNeg = nValue < 0;
 569     nLen = 0;
 570
 571     if ((nValue >= SAL_MIN_INT32) && (nValue <= SAL_MAX_INT32))
 572     {
 573         nVal = static_cast<sal_Int32>(nValue);
 574     }
 575     else
 576     {
 577         sal_uInt64 nUValue = static_cast<sal_uInt64>(bIsNeg ? -nValue : nValue);
 578         for (int i = 0; (i != sizeof(sal_uInt64) / 2) && (nUValue != 0); ++i)
 579         {
 580             nNum[i] = static_cast<sal_uInt16>(nUValue & 0xffffUL);
 581             nUValue = nUValue >> 16;
 582             ++nLen;
 583         }
 584     }
 585 }
 586
 587 BigInt::operator double() const
 588 {
 589     if ( nLen == 0 )
 590         return static_cast<double>(nVal);
 591     else
 592     {
 593         int     i = nLen-1;
 594         double  nRet = static_cast<double>(static_cast<sal_uInt32>(nNum[i]));
 595
 596         while ( i )
 597         {
 598             nRet *= 65536.0;
 599             i--;
 600             nRet += static_cast<double>(static_cast<sal_uInt32>(nNum[i]));
 601         }
 602
 603         if ( bIsNeg )
 604             nRet *= -1;
 605
 606         return nRet;
 607     }
 608 }
 609
 610 BigInt& BigInt::operator=( const BigInt& rBigInt )
 611 {
 612     if (this == &rBigInt)
 613         return *this;
 614
 615     if ( rBigInt.nLen != 0 )
 616         memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt), sizeof( BigInt ) );
 617     else
 618     {
 619         nLen = 0;
 620         nVal = rBigInt.nVal;
 621     }
 622     return *this;
 623 }
 624
 625 BigInt& BigInt::operator+=( const BigInt& rVal )
 626 {
 627     if ( nLen == 0 && rVal.nLen == 0 )
 628     {
 629         if( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG
 630             && nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 631         { // No overflows may occur here
 632             nVal += rVal.nVal;
 633             return *this;
 634         }
 635
 636         if( (nVal < 0) != (rVal.nVal < 0) )
 637         { // No overflows may occur here
 638             nVal += rVal.nVal;
 639             return *this;
 640         }
 641     }
 642
 643     BigInt aTmp1, aTmp2;
 644     aTmp1.MakeBigInt( *this );
 645     aTmp2.MakeBigInt( rVal );
 646     aTmp1.AddLong( aTmp2, *this );
 647     Normalize();
 648     return *this;
 649 }
 650
 651 BigInt& BigInt::operator-=( const BigInt& rVal )
 652 {
 653     if ( nLen == 0 && rVal.nLen == 0 )
 654     {
 655         if ( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG &&
 656              nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 657         { // No overflows may occur here
 658             nVal -= rVal.nVal;
 659             return *this;
 660         }
 661
 662         if ( (nVal < 0) == (rVal.nVal < 0) )
 663         { // No overflows may occur here
 664             nVal -= rVal.nVal;
 665             return *this;
 666         }
 667     }
 668
 669     BigInt aTmp1, aTmp2;
 670     aTmp1.MakeBigInt( *this );
 671     aTmp2.MakeBigInt( rVal );
 672     aTmp1.SubLong( aTmp2, *this );
 673     Normalize();
 674     return *this;
 675 }
 676
 677 BigInt& BigInt::operator*=( const BigInt& rVal )
 678 {
 679     static const sal_Int32 MY_MAXSHORT = 0x00007fff;
 680     static const sal_Int32 MY_MINSHORT = -MY_MAXSHORT;
 681
 682     if ( nLen == 0 && rVal.nLen == 0
 683          && nVal <= MY_MAXSHORT && rVal.nVal <= MY_MAXSHORT
 684          && nVal >= MY_MINSHORT && rVal.nVal >= MY_MINSHORT )
 685          // TODO: not optimal !!! W.P.
 686     { // No overflows may occur here
 687         nVal *= rVal.nVal;
 688     }
 689     else
 690     {
 691         BigInt aTmp1, aTmp2;
 692         aTmp1.MakeBigInt( rVal );
 693         aTmp2.MakeBigInt( *this );
 694         aTmp1.MultLong(aTmp2, *this);
 695         Normalize();
 696     }
 697     return *this;
 698 }
 699
 700 BigInt& BigInt::operator/=( const BigInt& rVal )
 701 {
 702     if ( rVal.nLen == 0 )
 703     {
 704         if ( rVal.nVal == 0 )
 705         {
 706             OSL_FAIL( "BigInt::operator/ --> divide by zero" );
 707             return *this;
 708         }
 709
 710         if ( nLen == 0 )
 711         {
 712             // No overflows may occur here
 713             nVal /= rVal.nVal;
 714             return *this;
 715         }
 716
 717         if ( rVal.nVal == 1 )
 718             return *this;
 719
 720         if ( rVal.nVal == -1 )
 721         {
 722             bIsNeg = !bIsNeg;
 723             return *this;
 724         }
 725
 726         if ( rVal.nVal <= 0xFFFF && rVal.nVal >= -0xFFFF )
 727         {
 728             // Divide BigInt with an sal_uInt16
 729             sal_uInt16 nTmp;
 730             if ( rVal.nVal < 0 )
 731             {
 732                 nTmp = static_cast<sal_uInt16>(-rVal.nVal);
 733                 bIsNeg = !bIsNeg;
 734             }
 735             else
 736                 nTmp = static_cast<sal_uInt16>(rVal.nVal);
 737
 738             Div( nTmp, nTmp );
 739             Normalize();
 740             return *this;
 741         }
 742     }
 743
 744     if ( ABS_IsLess( rVal ) )
 745     {
 746         *this = BigInt( 0 );
 747         return *this;
 748     }
 749
 750     // Divide BigInt with BigInt
 751     BigInt aTmp1, aTmp2;
 752     aTmp1.MakeBigInt( *this );
 753     aTmp2.MakeBigInt( rVal );
 754     aTmp1.DivLong(aTmp2, *this);
 755     Normalize();
 756     return *this;
 757 }
 758
 759 BigInt& BigInt::operator%=( const BigInt& rVal )
 760 {
 761     if ( rVal.nLen == 0 )
 762     {
 763         if ( rVal.nVal == 0 )
 764         {
 765             OSL_FAIL( "BigInt::operator/ --> divide by zero" );
 766             return *this;
 767         }
 768
 769         if ( nLen == 0 )
 770         {
 771             // No overflows may occur here
 772             nVal %= rVal.nVal;
 773             return *this;
 774         }
 775
 776         if ( rVal.nVal <= 0xFFFF && rVal.nVal >= -0xFFFF )
 777         {
 778             // Divide Bigint by int16
 779             sal_uInt16 nTmp;
 780             if ( rVal.nVal < 0 )
 781             {
 782                 nTmp = static_cast<sal_uInt16>(-rVal.nVal);
 783                 bIsNeg = !bIsNeg;
 784             }
 785             else
 786                 nTmp = static_cast<sal_uInt16>(rVal.nVal);
 787
 788             Div( nTmp, nTmp );
 789             *this = BigInt( nTmp );
 790             return *this;
 791         }
 792     }
 793
 794     if ( ABS_IsLess( rVal ) )
 795         return *this;
 796
 797     // Divide BigInt with BigInt
 798     BigInt aTmp1, aTmp2;
 799     aTmp1.MakeBigInt( *this );
 800     aTmp2.MakeBigInt( rVal );
 801     aTmp1.ModLong(aTmp2, *this);
 802     Normalize();
 803     return *this;
 804 }
 805
 806 bool operator==( const BigInt& rVal1, const BigInt& rVal2 )
 807 {
 808     if (rVal1.nLen == 0 && rVal2.nLen == 0)
 809         return rVal1.nVal == rVal2.nVal;
 810
 811     BigInt nA, nB;
 812     nA.MakeBigInt(rVal1);
 813     nB.MakeBigInt(rVal2);
 814     return nA.bIsNeg == nB.bIsNeg && nA.nLen == nB.nLen
 815            && std::equal(nA.nNum, nA.nNum + nA.nLen, nB.nNum);
 816 }
 817
 818 bool operator<( const BigInt& rVal1, const BigInt& rVal2 )
 819 {
 820     if (rVal1.nLen == 0 && rVal2.nLen == 0)
 821         return rVal1.nVal < rVal2.nVal;
 822
 823     BigInt nA, nB;
 824     nA.MakeBigInt(rVal1);
 825     nB.MakeBigInt(rVal2);
 826     if (nA.bIsNeg != nB.bIsNeg)
 827         return !nB.bIsNeg;
 828     if (nA.nLen != nB.nLen)
 829         return nA.bIsNeg ? (nA.nLen > nB.nLen) : (nA.nLen < nB.nLen);
 830     int i = nA.nLen - 1;
 831     while (i > 0 && nA.nNum[i] == nB.nNum[i])
 832         --i;
 833     return nA.bIsNeg ? (nA.nNum[i] > nB.nNum[i]) : (nA.nNum[i] < nB.nNum[i]);
 834 }
 835
 836 tools::Long BigInt::Scale( tools::Long nVal, tools::Long nMul, tools::Long nDiv )
 837 {
 838     BigInt aVal( nVal );
 839
 840     aVal *= nMul;
 841
 842     if ( aVal.IsNeg() != ( nDiv < 0 ) )
 843         aVal -= nDiv / 2; // for correct rounding
 844     else
 845         aVal += nDiv / 2; // for correct rounding
 846
 847     aVal /= nDiv;
 848
 849     return tools::Long( aVal );
 850 }
 851
 852 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */