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