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