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