tools/source/generic/bigint.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: bigint.cxx,v $
  10  * $Revision: 1.8 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_tools.hxx"
  33
  34 #include <math.h>
  35 #include <tools/tools.h>
  36
  37 #include <tools/bigint.hxx>
  38 #include <tools/string.hxx>
  39 #include <tools/debug.hxx>
  40
  41 #include <string.h>
  42 #include <ctype.h>
  43
  44 static const long MY_MAXLONG  = 0x3fffffff;
  45 static const long MY_MINLONG  = -MY_MAXLONG;
  46 static const long MY_MAXSHORT = 0x00007fff;
  47 static const long MY_MINSHORT = -MY_MAXSHORT;
  48
  49 /* Die ganzen Algorithmen zur Addition, Subtraktion, Multiplikation und
  50  * Division von langen Zahlen stammen aus SEMINUMERICAL ALGORITHMS von
  51  * DONALD E. KNUTH aus der Reihe The Art of Computer Programming. Zu finden
  52  * sind diese Algorithmen im Kapitel 4.3.1. The Classical Algorithms.
  53  */
  54
  55 // Muss auf UINT16/INT16/UINT32/INT32 umgestellt werden !!! W.P.
  56
  57 // -----------------------------------------------------------------------
  58
  59 void BigInt::MakeBigInt( const BigInt& rVal )
  60 {
  61     if ( rVal.bIsBig )
  62     {
  63         memcpy( (void*)this, (const void*)&rVal, sizeof( BigInt ) );
  64         while ( nLen > 1 && nNum[nLen-1] == 0 )
  65             nLen--;
  66     }
  67     else
  68     {
  69         long nTmp = rVal.nVal;
  70
  71         nVal   = rVal.nVal;
  72         bIsBig = sal_True;
  73         if ( nTmp < 0 )
  74         {
  75             bIsNeg = sal_True;
  76             nTmp = -nTmp;
  77         }
  78         else
  79             bIsNeg = sal_False;
  80
  81         nNum[0] = (sal_uInt16)(nTmp & 0xffffL);
  82         nNum[1] = (sal_uInt16)(nTmp >> 16);
  83 #ifndef _WIN16
  84         if ( nTmp & 0xffff0000L )
  85 #else
  86         long l = 0xffff0000L;
  87         if ( nTmp & l )
  88 #endif
  89             nLen = 2;
  90         else
  91             nLen = 1;
  92     }
  93 }
  94
  95 // -----------------------------------------------------------------------
  96
  97 void BigInt::Normalize()
  98 {
  99     if ( bIsBig )
 100     {
 101         while ( nLen > 1 && nNum[nLen-1] == 0 )
 102             nLen--;
 103
 104         if ( nLen < 3 )
 105         {
 106             if ( nLen < 2 )
 107                 nVal = nNum[0];
 108             else if ( nNum[1] & 0x8000 )
 109                 return;
 110             else
 111                 nVal = ((long)nNum[1] << 16) + nNum[0];
 112
 113             bIsBig = sal_False;
 114
 115             if ( bIsNeg )
 116                 nVal = -nVal;
 117         }
 118         // else ist nVal undefiniert !!! W.P.
 119     }
 120     // wozu, nLen ist doch undefiniert ??? W.P.
 121     else if ( nVal & 0xFFFF0000L )
 122         nLen = 2;
 123     else
 124         nLen = 1;
 125 }
 126
 127 // -----------------------------------------------------------------------
 128
 129 void BigInt::Mult( const BigInt &rVal, sal_uInt16 nMul )
 130 {
 131     sal_uInt16 nK = 0;
 132     for ( int i = 0; i < rVal.nLen; i++ )
 133     {
 134         sal_uInt32 nTmp = (sal_uInt32)rVal.nNum[i] * (sal_uInt32)nMul + nK;
 135         nK            = (sal_uInt16)(nTmp >> 16);
 136         nNum[i] = (sal_uInt16)nTmp;
 137     }
 138
 139     if ( nK )
 140     {
 141         nNum[rVal.nLen] = nK;
 142         nLen = rVal.nLen + 1;
 143     }
 144     else
 145         nLen = rVal.nLen;
 146
 147     bIsBig = sal_True;
 148     bIsNeg = rVal.bIsNeg;
 149 }
 150
 151 // -----------------------------------------------------------------------
 152
 153 void BigInt::Div( sal_uInt16 nDiv, sal_uInt16& rRem )
 154 {
 155     sal_uInt32 nK = 0;
 156     for ( int i = nLen - 1; i >= 0; i-- )
 157     {
 158         sal_uInt32 nTmp = (sal_uInt32)nNum[i] + (nK << 16);
 159         nNum[i] = (sal_uInt16)(nTmp / nDiv);
 160         nK            = nTmp % nDiv;
 161     }
 162     rRem = (sal_uInt16)nK;
 163
 164     if ( nNum[nLen-1] == 0 )
 165         nLen -= 1;
 166 }
 167
 168 // -----------------------------------------------------------------------
 169
 170 sal_Bool BigInt::IsLess( const BigInt& rVal ) const
 171 {
 172     if ( rVal.nLen < nLen)
 173         return sal_True;
 174     if ( rVal.nLen > nLen )
 175         return sal_False;
 176
 177     int i;
 178     for ( i = nLen - 1; i > 0 && nNum[i] == rVal.nNum[i]; i-- )
 179     {
 180     }
 181     return rVal.nNum[i] < nNum[i];
 182 }
 183
 184 // -----------------------------------------------------------------------
 185
 186 void BigInt::AddLong( BigInt& rB, BigInt& rErg )
 187 {
 188     if ( bIsNeg == rB.bIsNeg )
 189     {
 190         int  i;
 191         char len;
 192
 193         // wenn die Zahlen unterschiedlich lang sind, sollte zunaechst bei
 194         // der kleineren Zahl die fehlenden Ziffern mit 0 initialisert werden
 195         if (nLen >= rB.nLen)
 196         {
 197             len = nLen;
 198             for (i = rB.nLen; i < len; i++)
 199                 rB.nNum[i] = 0;
 200         }
 201         else
 202         {
 203             len = rB.nLen;
 204             for (i = nLen; i < len; i++)
 205                 nNum[i] = 0;
 206         }
 207
 208         // Die Ziffern werden von hinten nach vorne addiert
 209         long k;
 210         long nZ = 0;
 211         for (i = 0, k = 0; i < len; i++) {
 212             nZ = (long)nNum[i] + (long)rB.nNum[i] + k;
 213             if (nZ & 0xff0000L)
 214                 k = 1;
 215             else
 216                 k = 0;
 217             rErg.nNum[i] = (sal_uInt16)(nZ & 0xffffL);
 218         }
 219         // Trat nach der letzten Addition ein Ueberlauf auf, muss dieser
 220         // noch ins Ergebis uebernommen werden
 221         if (nZ & 0xff0000L) // oder if(k)
 222         {
 223             rErg.nNum[i] = 1;
 224             len++;
 225         }
 226         // Die Laenge und das Vorzeichen setzen
 227         rErg.nLen   = len;
 228         rErg.bIsNeg = bIsNeg && rB.bIsNeg;
 229         rErg.bIsBig = sal_True;
 230     }
 231     // Wenn nur einer der beiden Operanten negativ ist, wird aus der
 232     // Addition eine Subtaktion
 233     else if (bIsNeg)
 234     {
 235         bIsNeg = sal_False;
 236         rB.SubLong(*this, rErg);
 237         bIsNeg = sal_True;
 238     }
 239     else
 240     {
 241         rB.bIsNeg = sal_False;
 242         SubLong(rB, rErg);
 243         rB.bIsNeg = sal_True;
 244     }
 245 }
 246
 247 // -----------------------------------------------------------------------
 248
 249 void BigInt::SubLong( BigInt& rB, BigInt& rErg )
 250 {
 251     if ( bIsNeg == rB.bIsNeg )
 252     {
 253         int  i;
 254         char len;
 255         long nZ, k;
 256
 257         // wenn die Zahlen unterschiedlich lang sind, sollte zunaechst bei
 258         // der kleineren Zahl die fehlenden Ziffern mit 0 initialisert werden
 259         if (nLen >= rB.nLen)
 260         {
 261             len = nLen;
 262             for (i = rB.nLen; i < len; i++)
 263                 rB.nNum[i] = 0;
 264         }
 265         else
 266         {
 267             len = rB.nLen;
 268             for (i = nLen; i < len; i++)
 269                 nNum[i] = 0;
 270         }
 271
 272         if ( IsLess(rB) )
 273         {
 274             for (i = 0, k = 0; i < len; i++)
 275             {
 276                 nZ = (long)nNum[i] - (long)rB.nNum[i] + k;
 277                 if (nZ < 0)
 278                     k = -1;
 279                 else
 280                     k = 0;
 281                 rErg.nNum[i] = (sal_uInt16)(nZ & 0xffffL);
 282             }
 283             rErg.bIsNeg = bIsNeg;
 284         }
 285         else
 286         {
 287             for (i = 0, k = 0; i < len; i++)
 288             {
 289                 nZ = (long)rB.nNum[i] - (long)nNum[i] + k;
 290                 if (nZ < 0)
 291                     k = -1;
 292                 else
 293                     k = 0;
 294                 rErg.nNum[i] = (sal_uInt16)(nZ & 0xffffL);
 295             }
 296             // wenn a < b, dann Vorzeichen vom Ergebnis umdrehen
 297             rErg.bIsNeg = !bIsNeg;
 298         }
 299         rErg.nLen   = len;
 300         rErg.bIsBig = sal_True;
 301     }
 302     // Wenn nur einer der beiden Operanten negativ ist, wird aus der
 303     // Subtaktion eine Addition
 304     else if (bIsNeg)
 305     {
 306         bIsNeg = sal_False;
 307         AddLong(rB, rErg);
 308         bIsNeg = sal_True;
 309         rErg.bIsNeg = sal_True;
 310     }
 311     else
 312     {
 313         rB.bIsNeg = sal_False;
 314         AddLong(rB, rErg);
 315         rB.bIsNeg = sal_True;
 316         rErg.bIsNeg = sal_False;
 317     }
 318 }
 319
 320 // -----------------------------------------------------------------------
 321
 322 void BigInt::MultLong( const BigInt& rB, BigInt& rErg ) const
 323 {
 324     int    i, j;
 325     sal_uInt32  nZ, k;
 326
 327     rErg.bIsNeg = bIsNeg != rB.bIsNeg;
 328     rErg.bIsBig = sal_True;
 329     rErg.nLen   = nLen + rB.nLen;
 330
 331     for (i = 0; i < rErg.nLen; i++)
 332         rErg.nNum[i] = 0;
 333
 334     for (j = 0; j < rB.nLen; j++)
 335     {
 336         for (i = 0, k = 0; i < nLen; i++)
 337         {
 338             nZ = (sal_uInt32)nNum[i] * (sal_uInt32)rB.nNum[j] +
 339                  (sal_uInt32)rErg.nNum[i + j] + k;
 340             rErg.nNum[i + j] = (sal_uInt16)(nZ & 0xffffUL);
 341             k = nZ >> 16;
 342         }
 343         rErg.nNum[i + j] = (sal_uInt16)k;
 344     }
 345 }
 346
 347 // -----------------------------------------------------------------------
 348
 349 void BigInt::DivLong( const BigInt& rB, BigInt& rErg ) const
 350 {
 351     int    i, j;
 352     long   nTmp;
 353     sal_uInt16 nK, nQ, nMult;
 354     short  nLenB  = rB.nLen;
 355     short  nLenB1 = rB.nLen - 1;
 356     BigInt aTmpA, aTmpB;
 357
 358     nMult = (sal_uInt16)(0x10000L / ((long)rB.nNum[nLenB1] + 1));
 359
 360     aTmpA.Mult( *this, nMult );
 361     if ( aTmpA.nLen == nLen )
 362     {
 363         aTmpA.nNum[aTmpA.nLen] = 0;
 364         aTmpA.nLen++;
 365     }
 366
 367     aTmpB.Mult( rB, nMult );
 368
 369     for (j = aTmpA.nLen - 1; j >= nLenB; j--)
 370     { // Raten des Divisors
 371         nTmp = ( (long)aTmpA.nNum[j] << 16 ) + aTmpA.nNum[j - 1];
 372         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 373             nQ = 0xFFFF;
 374         else
 375             nQ = (sal_uInt16)(((sal_uInt32)nTmp) / aTmpB.nNum[nLenB1]);
 376
 377         if ( ((sal_uInt32)aTmpB.nNum[nLenB1 - 1] * nQ) >
 378             ((((sal_uInt32)nTmp) - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
 379             nQ--;
 380         // Und hier faengt das Teilen an
 381         nK = 0;
 382         nTmp = 0;
 383         for (i = 0; i < nLenB; i++)
 384         {
 385             nTmp = (long)aTmpA.nNum[j - nLenB + i]
 386                    - ((long)aTmpB.nNum[i] * nQ)
 387                    - nK;
 388             aTmpA.nNum[j - nLenB + i] = (sal_uInt16)nTmp;
 389             nK = (sal_uInt16) (nTmp >> 16);
 390             if ( nK )
 391                 nK = (sal_uInt16)(0x10000UL - nK);
 392         }
 393         unsigned short& rNum( aTmpA.nNum[j - nLenB + i] );
 394         rNum = rNum - nK;   // MSVC yields a warning on -= here, so don't use it
 395         if (aTmpA.nNum[j - nLenB + i] == 0)
 396             rErg.nNum[j - nLenB] = nQ;
 397         else
 398         {
 399             rErg.nNum[j - nLenB] = nQ - 1;
 400             nK = 0;
 401             for (i = 0; i < nLenB; i++)
 402             {
 403                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 404                 aTmpA.nNum[j - nLenB + i] = (sal_uInt16)(nTmp & 0xFFFFL);
 405                 if (nTmp & 0xFFFF0000L)
 406                     nK = 1;
 407                 else
 408                     nK = 0;
 409             }
 410         }
 411     }
 412
 413     rErg.bIsNeg = bIsNeg != rB.bIsNeg;
 414     rErg.bIsBig = sal_True;
 415     rErg.nLen   = nLen - rB.nLen + 1;
 416 }
 417
 418 // -----------------------------------------------------------------------
 419
 420 void BigInt::ModLong( const BigInt& rB, BigInt& rErg ) const
 421 {
 422     short  i, j;
 423     long   nTmp;
 424     sal_uInt16 nK, nQ, nMult;
 425     short  nLenB  = rB.nLen;
 426     short  nLenB1 = rB.nLen - 1;
 427     BigInt aTmpA, aTmpB;
 428
 429     nMult = (sal_uInt16)(0x10000L / ((long)rB.nNum[nLenB1] + 1));
 430
 431     aTmpA.Mult( *this, nMult);
 432     if ( aTmpA.nLen == nLen )
 433     {
 434         aTmpA.nNum[aTmpA.nLen] = 0;
 435         aTmpA.nLen++;
 436     }
 437
 438     aTmpB.Mult( rB, nMult);
 439
 440     for (j = aTmpA.nLen - 1; j >= nLenB; j--)
 441     { // Raten des Divisors
 442         nTmp = ( (long)aTmpA.nNum[j] << 16 ) + aTmpA.nNum[j - 1];
 443         if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
 444             nQ = 0xFFFF;
 445         else
 446             nQ = (sal_uInt16)(((sal_uInt32)nTmp) / aTmpB.nNum[nLenB1]);
 447
 448         if ( ((sal_uInt32)aTmpB.nNum[nLenB1 - 1] * nQ) >
 449             ((((sal_uInt32)nTmp) - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
 450             nQ--;
 451         // Und hier faengt das Teilen an
 452         nK = 0;
 453         nTmp = 0;
 454         for (i = 0; i < nLenB; i++)
 455         {
 456             nTmp = (long)aTmpA.nNum[j - nLenB + i]
 457                    - ((long)aTmpB.nNum[i] * nQ)
 458                    - nK;
 459             aTmpA.nNum[j - nLenB + i] = (sal_uInt16)nTmp;
 460             nK = (sal_uInt16) (nTmp >> 16);
 461             if ( nK )
 462                 nK = (sal_uInt16)(0x10000UL - nK);
 463         }
 464         unsigned short& rNum( aTmpA.nNum[j - nLenB + i] );
 465         rNum = rNum - nK;
 466         if (aTmpA.nNum[j - nLenB + i] == 0)
 467             rErg.nNum[j - nLenB] = nQ;
 468         else
 469         {
 470             rErg.nNum[j - nLenB] = nQ - 1;
 471             nK = 0;
 472             for (i = 0; i < nLenB; i++) {
 473                 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
 474                 aTmpA.nNum[j - nLenB + i] = (sal_uInt16)(nTmp & 0xFFFFL);
 475                 if (nTmp & 0xFFFF0000L)
 476                     nK = 1;
 477                 else
 478                     nK = 0;
 479             }
 480         }
 481     }
 482
 483     rErg = aTmpA;
 484     rErg.Div( nMult, nQ );
 485 }
 486
 487 // -----------------------------------------------------------------------
 488
 489 sal_Bool BigInt::ABS_IsLess( const BigInt& rB ) const
 490 {
 491     if (bIsBig || rB.bIsBig)
 492     {
 493         BigInt nA, nB;
 494         nA.MakeBigInt( *this );
 495         nB.MakeBigInt( rB );
 496         if (nA.nLen == nB.nLen)
 497         {
 498             int i;
 499             for (i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i--)
 500             {
 501             }
 502             return nA.nNum[i] < nB.nNum[i];
 503         }
 504         else
 505             return nA.nLen < nB.nLen;
 506     }
 507     if ( nVal < 0 )
 508         if ( rB.nVal < 0 )
 509             return nVal > rB.nVal;
 510         else
 511             return nVal > -rB.nVal;
 512     else
 513         if ( rB.nVal < 0 )
 514             return nVal < -rB.nVal;
 515         else
 516             return nVal < rB.nVal;
 517 }
 518
 519 // -----------------------------------------------------------------------
 520
 521 BigInt::BigInt( const BigInt& rBigInt )
 522 {
 523     if ( rBigInt.bIsBig )
 524         memcpy( (void*)this, (const void*)&rBigInt, sizeof( BigInt ) );
 525     else
 526     {
 527         bIsSet = rBigInt.bIsSet;
 528         bIsBig = sal_False;
 529         nVal   = rBigInt.nVal;
 530     }
 531 }
 532
 533 // -----------------------------------------------------------------------
 534
 535 BigInt::BigInt( const ByteString& rString )
 536 {
 537     bIsSet = sal_True;
 538     bIsNeg = sal_False;
 539     bIsBig = sal_False;
 540     nVal   = 0;
 541
 542     sal_Bool bNeg = sal_False;
 543     const sal_Char* p = rString.GetBuffer();
 544     if ( *p == '-' )
 545     {
 546         bNeg = sal_True;
 547         p++;
 548     }
 549     while( *p >= '0' && *p <= '9' )
 550     {
 551         *this *= 10;
 552         *this += *p - '0';
 553         p++;
 554     }
 555     if ( bIsBig )
 556         bIsNeg = bNeg;
 557     else if( bNeg )
 558         nVal = -nVal;
 559 }
 560
 561 // -----------------------------------------------------------------------
 562
 563 BigInt::BigInt( const UniString& rString )
 564 {
 565     bIsSet = sal_True;
 566     bIsNeg = sal_False;
 567     bIsBig = sal_False;
 568     nVal   = 0;
 569
 570     sal_Bool bNeg = sal_False;
 571     const sal_Unicode* p = rString.GetBuffer();
 572     if ( *p == '-' )
 573     {
 574         bNeg = sal_True;
 575         p++;
 576     }
 577     while( *p >= '0' && *p <= '9' )
 578     {
 579         *this *= 10;
 580         *this += *p - '0';
 581         p++;
 582     }
 583     if ( bIsBig )
 584         bIsNeg = bNeg;
 585     else if( bNeg )
 586         nVal = -nVal;
 587 }
 588
 589 // -----------------------------------------------------------------------
 590
 591 BigInt::BigInt( double nValue )
 592 {
 593     bIsSet = sal_True;
 594
 595     if ( nValue < 0 )
 596     {
 597         nValue *= -1;
 598         bIsNeg  = sal_True;
 599     }
 600     else
 601     {
 602         bIsNeg  = sal_False;
 603     }
 604
 605     if ( nValue < 1 )
 606     {
 607         bIsBig = sal_False;
 608         nVal   = 0;
 609     }
 610     else
 611     {
 612         bIsBig = sal_True;
 613
 614         int i=0;
 615
 616         while ( ( nValue > 65536.0 ) && ( i < MAX_DIGITS ) )
 617         {
 618             nNum[i] = (sal_uInt16) fmod( nValue, 65536.0 );
 619             nValue -= nNum[i];
 620             nValue /= 65536.0;
 621             i++;
 622         }
 623         if ( i < MAX_DIGITS )
 624             nNum[i++] = (sal_uInt16) nValue;
 625
 626         nLen = i;
 627
 628         if ( i < 3 )
 629             Normalize();
 630     }
 631 }
 632
 633 // -----------------------------------------------------------------------
 634
 635 BigInt::BigInt( sal_uInt32 nValue )
 636 {
 637     bIsSet  = sal_True;
 638     if ( nValue & 0x80000000UL )
 639     {
 640         bIsBig  = sal_True;
 641         bIsNeg  = sal_False;
 642         nNum[0] = (sal_uInt16)(nValue & 0xffffUL);
 643         nNum[1] = (sal_uInt16)(nValue >> 16);
 644         nLen    = 2;
 645     }
 646     else
 647     {
 648         bIsBig = sal_False;
 649         nVal   = nValue;
 650     }
 651 }
 652
 653 // -----------------------------------------------------------------------
 654
 655 BigInt::operator ULONG() const
 656 {
 657     if ( !bIsBig )
 658         return (sal_uInt32)nVal;
 659     else if ( nLen == 2 )
 660     {
 661         sal_uInt32 nRet;
 662         nRet  = ((sal_uInt32)nNum[1]) << 16;
 663         nRet += nNum[0];
 664         return nRet;
 665     }
 666     return 0;
 667 }
 668
 669 // -----------------------------------------------------------------------
 670
 671 BigInt::operator double() const
 672 {
 673     if ( !bIsBig )
 674         return (double) nVal;
 675     else
 676     {
 677         int     i = nLen-1;
 678         double  nRet = (double) ((sal_uInt32)nNum[i]);
 679
 680         while ( i )
 681         {
 682             nRet *= 65536.0;
 683             i--;
 684             nRet += (double) ((sal_uInt32)nNum[i]);
 685         }
 686
 687         if ( bIsNeg )
 688             nRet *= -1;
 689
 690         return nRet;
 691     }
 692 }
 693
 694 // -----------------------------------------------------------------------
 695
 696 ByteString BigInt::GetByteString() const
 697 {
 698     ByteString aString;
 699
 700     if ( !bIsBig )
 701         aString = ByteString::CreateFromInt32( nVal );
 702     else
 703     {
 704         BigInt aTmp( *this );
 705         BigInt a1000000000( 1000000000L );
 706         aTmp.Abs();
 707
 708         do
 709         {
 710             BigInt a = aTmp;
 711             a    %= a1000000000;
 712             aTmp /= a1000000000;
 713
 714             ByteString aStr = aString;
 715             if ( a.nVal < 100000000L )
 716             { // leading 0s
 717                 aString = ByteString::CreateFromInt32( a.nVal + 1000000000L );
 718                 aString.Erase( 0, 1 );
 719             }
 720             else
 721                 aString = ByteString::CreateFromInt32( a.nVal );
 722             aString += aStr;
 723         }
 724         while( aTmp.bIsBig );
 725
 726         ByteString aStr = aString;
 727         if ( bIsNeg )
 728             aString = ByteString::CreateFromInt32( -aTmp.nVal );
 729         else
 730             aString = ByteString::CreateFromInt32( aTmp.nVal );
 731         aString += aStr;
 732     }
 733
 734     return aString;
 735 }
 736
 737 // -----------------------------------------------------------------------
 738
 739 UniString BigInt::GetString() const
 740 {
 741     UniString aString;
 742
 743     if ( !bIsBig )
 744         aString = UniString::CreateFromInt32( nVal );
 745     else
 746     {
 747         BigInt aTmp( *this );
 748         BigInt a1000000000( 1000000000L );
 749         aTmp.Abs();
 750
 751         do
 752         {
 753             BigInt a = aTmp;
 754             a    %= a1000000000;
 755             aTmp /= a1000000000;
 756
 757             UniString aStr = aString;
 758             if ( a.nVal < 100000000L )
 759             { // leading 0s
 760                 aString = UniString::CreateFromInt32( a.nVal + 1000000000L );
 761                 aString.Erase(0,1);
 762             }
 763             else
 764                 aString = UniString::CreateFromInt32( a.nVal );
 765             aString += aStr;
 766         }
 767         while( aTmp.bIsBig );
 768
 769         UniString aStr = aString;
 770         if ( bIsNeg )
 771             aString = UniString::CreateFromInt32( -aTmp.nVal );
 772         else
 773             aString = UniString::CreateFromInt32( aTmp.nVal );
 774         aString += aStr;
 775     }
 776
 777     return aString;
 778 }
 779
 780 // -----------------------------------------------------------------------
 781
 782 BigInt& BigInt::operator=( const BigInt& rBigInt )
 783 {
 784     if ( rBigInt.bIsBig )
 785         memcpy( (void*)this, (const void*)&rBigInt, sizeof( BigInt ) );
 786     else
 787     {
 788         bIsSet = rBigInt.bIsSet;
 789         bIsBig = sal_False;
 790         nVal   = rBigInt.nVal;
 791     }
 792     return *this;
 793 }
 794
 795 // -----------------------------------------------------------------------
 796
 797 BigInt& BigInt::operator+=( const BigInt& rVal )
 798 {
 799     if ( !bIsBig && !rVal.bIsBig )
 800     {
 801         if( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG
 802             && nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 803         { // wir bewegen uns im ungefaehrlichem Bereich
 804             nVal += rVal.nVal;
 805             return *this;
 806         }
 807
 808         if( (nVal < 0) != (rVal.nVal < 0) )
 809         { // wir bewegen uns im ungefaehrlichem Bereich
 810             nVal += rVal.nVal;
 811             return *this;
 812         }
 813     }
 814
 815     BigInt aTmp1, aTmp2;
 816     aTmp1.MakeBigInt( *this );
 817     aTmp2.MakeBigInt( rVal );
 818     aTmp1.AddLong( aTmp2, *this );
 819     Normalize();
 820     return *this;
 821 }
 822
 823 // -----------------------------------------------------------------------
 824
 825 BigInt& BigInt::operator-=( const BigInt& rVal )
 826 {
 827     if ( !bIsBig && !rVal.bIsBig )
 828     {
 829         if ( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG &&
 830              nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
 831         { // wir bewegen uns im ungefaehrlichem Bereich
 832             nVal -= rVal.nVal;
 833             return *this;
 834         }
 835
 836         if ( (nVal < 0) == (rVal.nVal < 0) )
 837         { // wir bewegen uns im ungefaehrlichem Bereich
 838             nVal -= rVal.nVal;
 839             return *this;
 840         }
 841     }
 842
 843     BigInt aTmp1, aTmp2;
 844     aTmp1.MakeBigInt( *this );
 845     aTmp2.MakeBigInt( rVal );
 846     aTmp1.SubLong( aTmp2, *this );
 847     Normalize();
 848     return *this;
 849 }
 850
 851 // -----------------------------------------------------------------------
 852
 853 BigInt& BigInt::operator*=( const BigInt& rVal )
 854 {
 855     if ( !bIsBig && !rVal.bIsBig
 856          && nVal <= MY_MAXSHORT && rVal.nVal <= MY_MAXSHORT
 857          && nVal >= MY_MINSHORT && rVal.nVal >= MY_MINSHORT )
 858          // nicht optimal !!! W.P.
 859     { // wir bewegen uns im ungefaehrlichem Bereich
 860         nVal *= rVal.nVal;
 861     }
 862     else
 863     {
 864         BigInt aTmp1, aTmp2;
 865         aTmp1.MakeBigInt( rVal );
 866         aTmp2.MakeBigInt( *this );
 867         aTmp1.MultLong(aTmp2, *this);
 868         Normalize();
 869     }
 870     return *this;
 871 }
 872
 873 // -----------------------------------------------------------------------
 874
 875 BigInt& BigInt::operator/=( const BigInt& rVal )
 876 {
 877     if ( !rVal.bIsBig )
 878     {
 879         if ( rVal.nVal == 0 )
 880         {
 881             DBG_ERROR( "BigInt::operator/ --> divide by zero" );
 882             return *this;
 883         }
 884
 885         if ( !bIsBig )
 886         {
 887             // wir bewegen uns im ungefaehrlichem Bereich
 888             nVal /= rVal.nVal;
 889             return *this;
 890         }
 891
 892         if ( rVal.nVal == 1 )
 893             return *this;
 894
 895         if ( rVal.nVal == -1 )
 896         {
 897             bIsNeg = !bIsNeg;
 898             return *this;
 899         }
 900
 901         if ( rVal.nVal <= (long)0xFFFF && rVal.nVal >= -(long)0xFFFF )
 902         {
 903             // ein BigInt durch ein sal_uInt16 teilen
 904             sal_uInt16 nTmp;
 905             if ( rVal.nVal < 0 )
 906             {
 907                 nTmp = (sal_uInt16) -rVal.nVal;
 908                 bIsNeg = !bIsNeg;
 909             }
 910             else
 911                 nTmp = (sal_uInt16) rVal.nVal;
 912
 913             Div( nTmp, nTmp );
 914             Normalize();
 915             return *this;
 916         }
 917     }
 918
 919     if ( ABS_IsLess( rVal ) )
 920     {
 921         *this = BigInt( (long)0 );
 922         return *this;
 923     }
 924
 925     // BigInt durch BigInt teilen
 926     BigInt aTmp1, aTmp2;
 927     aTmp1.MakeBigInt( *this );
 928     aTmp2.MakeBigInt( rVal );
 929     aTmp1.DivLong(aTmp2, *this);
 930     Normalize();
 931     return *this;
 932 }
 933
 934 // -----------------------------------------------------------------------
 935
 936 void BigInt::DivMod( const BigInt& rVal, BigInt& rMod )
 937 {
 938     if ( !rVal.bIsBig )
 939     {
 940         if ( rVal.nVal == 0 )
 941         {
 942             DBG_ERROR( "BigInt::operator/ --> divide by zero" );
 943             return;
 944         }
 945
 946         if ( !bIsBig )
 947         {
 948             // wir bewegen uns im ungefaehrlichem Bereich
 949             rMod  = BigInt( nVal % rVal.nVal );
 950             nVal /= rVal.nVal;
 951             return;
 952         }
 953
 954         if ( rVal.nVal == 1 )
 955         {
 956             rMod = BigInt( (long)0 );
 957             return;
 958         }
 959
 960         if ( rVal.nVal == -1 )
 961         {
 962             rMod = BigInt( (long)0 );
 963             bIsNeg = !bIsNeg;
 964             return;
 965         }
 966
 967         if ( rVal.nVal <= (long)0xFFFF && rVal.nVal >= -(long)0xFFFF )
 968         {
 969             // ein BigInt durch ein sal_uInt16 teilen
 970             sal_uInt16 nTmp;
 971             if ( rVal.nVal < 0 )
 972             {
 973                 nTmp = (sal_uInt16) -rVal.nVal;
 974                 bIsNeg = !bIsNeg;
 975             }
 976             else
 977                 nTmp = (sal_uInt16) rVal.nVal;
 978
 979             Div( nTmp, nTmp );
 980             rMod = BigInt( (long)nTmp );
 981             Normalize();
 982             return;
 983         }
 984     }
 985
 986     if ( ABS_IsLess( rVal ) )
 987     {
 988         rMod  = *this;
 989         *this = BigInt( (long)0 );
 990         return;
 991     }
 992
 993     // BigInt durch BigInt teilen
 994     BigInt aTmp1, aTmp2;
 995     aTmp1.MakeBigInt( *this );
 996     aTmp2.MakeBigInt( rVal );
 997     aTmp1.DivLong(aTmp2, *this);
 998     Normalize();
 999     aTmp1.ModLong(aTmp2, rMod); // nicht optimal
1000     rMod.Normalize();
1001 }
1002
1003 // -----------------------------------------------------------------------
1004
1005 BigInt& BigInt::operator%=( const BigInt& rVal )
1006 {
1007     if ( !rVal.bIsBig )
1008     {
1009         if ( rVal.nVal == 0 )
1010         {
1011             DBG_ERROR( "BigInt::operator/ --> divide by zero" );
1012             return *this;
1013         }
1014
1015         if ( !bIsBig )
1016         {
1017             // wir bewegen uns im ungefaehrlichem Bereich
1018             nVal %= rVal.nVal;
1019             return *this;
1020         }
1021
1022         if ( rVal.nVal <= (long)0xFFFF && rVal.nVal >= -(long)0xFFFF )
1023         {
1024             // ein BigInt durch ein short teilen
1025             sal_uInt16 nTmp;
1026             if ( rVal.nVal < 0 )
1027             {
1028                 nTmp = (sal_uInt16) -rVal.nVal;
1029                 bIsNeg = !bIsNeg;
1030             }
1031             else
1032                 nTmp = (sal_uInt16) rVal.nVal;
1033
1034             Div( nTmp, nTmp );
1035             *this = BigInt( (long)nTmp );
1036             return *this;
1037         }
1038     }
1039
1040     if ( ABS_IsLess( rVal ) )
1041         return *this;
1042
1043     // BigInt durch BigInt teilen
1044     BigInt aTmp1, aTmp2;
1045     aTmp1.MakeBigInt( *this );
1046     aTmp2.MakeBigInt( rVal );
1047     aTmp1.ModLong(aTmp2, *this);
1048     Normalize();
1049     return *this;
1050 }
1051
1052 // -----------------------------------------------------------------------
1053
1054 sal_Bool operator==( const BigInt& rVal1, const BigInt& rVal2 )
1055 {
1056     if ( rVal1.bIsBig || rVal2.bIsBig )
1057     {
1058         BigInt nA, nB;
1059         nA.MakeBigInt( rVal1 );
1060         nB.MakeBigInt( rVal2 );
1061         if ( nA.bIsNeg == nB.bIsNeg )
1062         {
1063             if ( nA.nLen == nB.nLen )
1064             {
1065                 int i;
1066                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
1067                 {
1068                 }
1069
1070                 return nA.nNum[i] == nB.nNum[i];
1071             }
1072             return sal_False;
1073         }
1074         return sal_False;
1075     }
1076     return rVal1.nVal == rVal2.nVal;
1077 }
1078
1079 // -----------------------------------------------------------------------
1080
1081 sal_Bool operator<( const BigInt& rVal1, const BigInt& rVal2 )
1082 {
1083     if ( rVal1.bIsBig || rVal2.bIsBig )
1084     {
1085         BigInt nA, nB;
1086         nA.MakeBigInt( rVal1 );
1087         nB.MakeBigInt( rVal2 );
1088         if ( nA.bIsNeg == nB.bIsNeg )
1089         {
1090             if ( nA.nLen == nB.nLen )
1091             {
1092                 int i;
1093                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
1094                 {
1095                 }
1096
1097                 if ( nA.bIsNeg )
1098                     return nA.nNum[i] > nB.nNum[i];
1099                 else
1100                     return nA.nNum[i] < nB.nNum[i];
1101             }
1102             if ( nA.bIsNeg )
1103                 return nA.nLen > nB.nLen;
1104             else
1105                 return nA.nLen < nB.nLen;
1106         }
1107         return !nB.bIsNeg;
1108     }
1109     return rVal1.nVal < rVal2.nVal;
1110 }
1111
1112 // -----------------------------------------------------------------------
1113
1114 sal_Bool operator >(const BigInt& rVal1, const BigInt& rVal2 )
1115 {
1116     if ( rVal1.bIsBig || rVal2.bIsBig )
1117     {
1118         BigInt nA, nB;
1119         nA.MakeBigInt( rVal1 );
1120         nB.MakeBigInt( rVal2 );
1121         if ( nA.bIsNeg == nB.bIsNeg )
1122         {
1123             if ( nA.nLen == nB.nLen )
1124             {
1125                 int i;
1126                 for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
1127                 {
1128                 }
1129
1130                 if ( nA.bIsNeg )
1131                     return nA.nNum[i] < nB.nNum[i];
1132                 else
1133                     return nA.nNum[i] > nB.nNum[i];
1134             }
1135             if ( nA.bIsNeg )
1136                 return nA.nLen < nB.nLen;
1137             else
1138                 return nA.nLen > nB.nLen;
1139         }
1140         return !nA.bIsNeg;
1141     }
1142
1143     return rVal1.nVal > rVal2.nVal;
1144 }