Branch data 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 <tools/tools.h>
23 : : #include <tools/bigint.hxx>
24 : : #include <tools/string.hxx>
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 : 638546 : void BigInt::MakeBigInt( const BigInt& rVal )
43 : : {
44 [ + + ]: 638546 : if ( rVal.bIsBig )
45 : : {
46 : 1232 : memcpy( (void*)this, (const void*)&rVal, sizeof( BigInt ) );
47 [ + - ][ - + ]: 1232 : while ( nLen > 1 && nNum[nLen-1] == 0 )
[ - + ]
48 : 0 : nLen--;
49 : : }
50 : : else
51 : : {
52 : 637314 : long nTmp = rVal.nVal;
53 : :
54 : 637314 : nVal = rVal.nVal;
55 : 637314 : bIsBig = sal_True;
56 [ - + ]: 637314 : if ( nTmp < 0 )
57 : : {
58 : 0 : bIsNeg = sal_True;
59 : 0 : nTmp = -nTmp;
60 : : }
61 : : else
62 : 637314 : bIsNeg = sal_False;
63 : :
64 : 637314 : nNum[0] = (sal_uInt16)(nTmp & 0xffffL);
65 : 637314 : nNum[1] = (sal_uInt16)(nTmp >> 16);
66 [ + + ]: 637314 : if ( nTmp & 0xffff0000L )
67 : 318236 : nLen = 2;
68 : : else
69 : 319078 : nLen = 1;
70 : : }
71 : 638546 : }
72 : :
73 : 318941 : void BigInt::Normalize()
74 : : {
75 [ + - ]: 318941 : if ( bIsBig )
76 : : {
77 [ + + ][ + + ]: 538392 : while ( nLen > 1 && nNum[nLen-1] == 0 )
[ + + ]
78 : 219451 : nLen--;
79 : :
80 [ + + ]: 318941 : if ( nLen < 3 )
81 : : {
82 [ + + ]: 219615 : if ( nLen < 2 )
83 : 805 : nVal = nNum[0];
84 [ + + ]: 218810 : else if ( nNum[1] & 0x8000 )
85 : 318941 : return;
86 : : else
87 : 198341 : nVal = ((long)nNum[1] << 16) + nNum[0];
88 : :
89 : 199146 : bIsBig = sal_False;
90 : :
91 [ - + ]: 199146 : if ( bIsNeg )
92 : 0 : 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 : 380 : void BigInt::Mult( const BigInt &rVal, sal_uInt16 nMul )
104 : : {
105 : 380 : sal_uInt16 nK = 0;
106 [ + + ]: 1452 : for ( int i = 0; i < rVal.nLen; i++ )
107 : : {
108 : 1072 : sal_uInt32 nTmp = (sal_uInt32)rVal.nNum[i] * (sal_uInt32)nMul + nK;
109 : 1072 : nK = (sal_uInt16)(nTmp >> 16);
110 : 1072 : nNum[i] = (sal_uInt16)nTmp;
111 : : }
112 : :
113 [ + + ]: 380 : if ( nK )
114 : : {
115 : 86 : nNum[rVal.nLen] = nK;
116 : 86 : nLen = rVal.nLen + 1;
117 : : }
118 : : else
119 : 294 : nLen = rVal.nLen;
120 : :
121 : 380 : bIsBig = sal_True;
122 : 380 : bIsNeg = rVal.bIsNeg;
123 : 380 : }
124 : :
125 : 104 : void BigInt::Div( sal_uInt16 nDiv, sal_uInt16& rRem )
126 : : {
127 : 104 : sal_uInt32 nK = 0;
128 [ + + ]: 416 : for ( int i = nLen - 1; i >= 0; i-- )
129 : : {
130 : 312 : sal_uInt32 nTmp = (sal_uInt32)nNum[i] + (nK << 16);
131 : 312 : nNum[i] = (sal_uInt16)(nTmp / nDiv);
132 : 312 : nK = nTmp % nDiv;
133 : : }
134 : 104 : rRem = (sal_uInt16)nK;
135 : :
136 [ - + ]: 104 : if ( nNum[nLen-1] == 0 )
137 : 0 : nLen -= 1;
138 : 104 : }
139 : :
140 : 0 : sal_Bool BigInt::IsLess( const BigInt& rVal ) const
141 : : {
142 [ # # ]: 0 : if ( rVal.nLen < nLen)
143 : 0 : return sal_True;
144 [ # # ]: 0 : if ( rVal.nLen > nLen )
145 : 0 : return sal_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 : 190 : void BigInt::AddLong( BigInt& rB, BigInt& rErg )
155 : : {
156 [ + - ]: 190 : 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 [ + - ]: 190 : if (nLen >= rB.nLen)
164 : : {
165 : 190 : len = nLen;
166 [ + + ]: 294 : for (i = rB.nLen; i < len; i++)
167 : 104 : 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 : 190 : long nZ = 0;
179 [ + + ]: 778 : for (i = 0, k = 0; i < len; i++) {
180 : 588 : nZ = (long)nNum[i] + (long)rB.nNum[i] + k;
181 [ + + ]: 588 : if (nZ & 0xff0000L)
182 : 100 : k = 1;
183 : : else
184 : 488 : k = 0;
185 : 588 : rErg.nNum[i] = (sal_uInt16)(nZ & 0xffffL);
186 : : }
187 : : // If an overflow occured, add to solution
188 [ - + ]: 190 : if (nZ & 0xff0000L) // or if(k)
189 : : {
190 : 0 : rErg.nNum[i] = 1;
191 : 0 : len++;
192 : : }
193 : : // Set length and sign
194 : 190 : rErg.nLen = len;
195 [ - + ][ # # ]: 190 : rErg.bIsNeg = bIsNeg && rB.bIsNeg;
196 : 190 : rErg.bIsBig = sal_True;
197 : : }
198 : : // If one of the values is negative, perform substraction instead
199 [ # # ]: 0 : else if (bIsNeg)
200 : : {
201 : 0 : bIsNeg = sal_False;
202 : 0 : rB.SubLong(*this, rErg);
203 : 0 : bIsNeg = sal_True;
204 : : }
205 : : else
206 : : {
207 : 0 : rB.bIsNeg = sal_False;
208 : 0 : SubLong(rB, rErg);
209 : 0 : rB.bIsNeg = sal_True;
210 : : }
211 : 190 : }
212 : :
213 : 0 : void BigInt::SubLong( BigInt& rB, BigInt& rErg )
214 : : {
215 [ # # ]: 0 : 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 = sal_True;
265 : : }
266 : : // If one of the values is negative, perform addition instead
267 [ # # ]: 0 : else if (bIsNeg)
268 : : {
269 : 0 : bIsNeg = sal_False;
270 : 0 : AddLong(rB, rErg);
271 : 0 : bIsNeg = sal_True;
272 : 0 : rErg.bIsNeg = sal_True;
273 : : }
274 : : else
275 : : {
276 : 0 : rB.bIsNeg = sal_False;
277 : 0 : AddLong(rB, rErg);
278 : 0 : rB.bIsNeg = sal_True;
279 : 0 : rErg.bIsNeg = sal_False;
280 : : }
281 : 0 : }
282 : :
283 : 318457 : void BigInt::MultLong( const BigInt& rB, BigInt& rErg ) const
284 : : {
285 : : int i, j;
286 : : sal_uInt32 nZ, k;
287 : :
288 : 318457 : rErg.bIsNeg = bIsNeg != rB.bIsNeg;
289 : 318457 : rErg.bIsBig = sal_True;
290 : 318457 : rErg.nLen = nLen + rB.nLen;
291 : :
292 [ + + ]: 1273317 : for (i = 0; i < rErg.nLen; i++)
293 : 954860 : rErg.nNum[i] = 0;
294 : :
295 [ + + ]: 637818 : for (j = 0; j < rB.nLen; j++)
296 : : {
297 [ + + ]: 955764 : for (i = 0, k = 0; i < nLen; i++)
298 : : {
299 : 1272806 : nZ = (sal_uInt32)nNum[i] * (sal_uInt32)rB.nNum[j] +
300 : 1272806 : (sal_uInt32)rErg.nNum[i + j] + k;
301 : 636403 : rErg.nNum[i + j] = (sal_uInt16)(nZ & 0xffffUL);
302 : 636403 : k = nZ >> 16;
303 : : }
304 : 319361 : rErg.nNum[i + j] = (sal_uInt16)k;
305 : : }
306 : 318457 : }
307 : :
308 : 190 : void BigInt::DivLong( const BigInt& rB, BigInt& rErg ) const
309 : : {
310 : : int i, j;
311 : : long nTmp;
312 : : sal_uInt16 nK, nQ, nMult;
313 : 190 : short nLenB = rB.nLen;
314 : 190 : short nLenB1 = rB.nLen - 1;
315 [ + - ][ + - ]: 190 : BigInt aTmpA, aTmpB;
316 : :
317 : 190 : nMult = (sal_uInt16)(0x10000L / ((long)rB.nNum[nLenB1] + 1));
318 : :
319 : 190 : aTmpA.Mult( *this, nMult );
320 [ + + ]: 190 : if ( aTmpA.nLen == nLen )
321 : : {
322 : 104 : aTmpA.nNum[aTmpA.nLen] = 0;
323 : 104 : aTmpA.nLen++;
324 : : }
325 : :
326 : 190 : aTmpB.Mult( rB, nMult );
327 : :
328 [ + + ]: 484 : for (j = aTmpA.nLen - 1; j >= nLenB; j--)
329 : : { // guess divisor
330 : 294 : nTmp = ( (long)aTmpA.nNum[j] << 16 ) + aTmpA.nNum[j - 1];
331 [ - + ]: 294 : if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
332 : 0 : nQ = 0xFFFF;
333 : : else
334 : 294 : nQ = (sal_uInt16)(((sal_uInt32)nTmp) / aTmpB.nNum[nLenB1]);
335 : :
336 [ - + ]: 294 : if ( ((sal_uInt32)aTmpB.nNum[nLenB1 - 1] * nQ) >
337 : 588 : ((((sal_uInt32)nTmp) - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
338 : 0 : nQ--;
339 : : // Start division
340 : 294 : nK = 0;
341 : 294 : nTmp = 0;
342 [ + + ]: 1086 : for (i = 0; i < nLenB; i++)
343 : : {
344 : 792 : nTmp = (long)aTmpA.nNum[j - nLenB + i]
345 : 792 : - ((long)aTmpB.nNum[i] * nQ)
346 : 1584 : - nK;
347 : 792 : aTmpA.nNum[j - nLenB + i] = (sal_uInt16)nTmp;
348 : 792 : nK = (sal_uInt16) (nTmp >> 16);
349 [ + + ]: 792 : if ( nK )
350 : 484 : nK = (sal_uInt16)(0x10000UL - nK);
351 : : }
352 : 294 : unsigned short& rNum( aTmpA.nNum[j - nLenB + i] );
353 : 294 : rNum = rNum - nK; // MSVC yields a warning on -= here, so don't use it
354 [ + - ]: 294 : if (aTmpA.nNum[j - nLenB + i] == 0)
355 : 294 : 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 : 190 : rErg.bIsNeg = bIsNeg != rB.bIsNeg;
373 : 190 : rErg.bIsBig = sal_True;
374 : 190 : rErg.nLen = nLen - rB.nLen + 1;
375 : 190 : }
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 : 190 : sal_Bool BigInt::ABS_IsLess( const BigInt& rB ) const
445 : : {
446 [ - + ][ # # ]: 190 : if (bIsBig || rB.bIsBig)
447 : : {
448 [ + - ][ + - ]: 190 : BigInt nA, nB;
449 : 190 : nA.MakeBigInt( *this );
450 : 190 : nB.MakeBigInt( rB );
451 [ + + ]: 190 : if (nA.nLen == nB.nLen)
452 : : {
453 : : int i;
454 [ + - ][ - + ]: 86 : for (i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i--)
[ - + ]
455 : : {
456 : : }
457 : 86 : return nA.nNum[i] < nB.nNum[i];
458 : : }
459 : : else
460 : 190 : 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 : 190 : return nVal < rB.nVal;
472 : : }
473 : :
474 : 5160 : BigInt::BigInt( const BigInt& rBigInt )
475 : : {
476 [ + + ]: 5160 : if ( rBigInt.bIsBig )
477 : 104 : memcpy( (void*)this, (const void*)&rBigInt, sizeof( BigInt ) );
478 : : else
479 : : {
480 : 5056 : bIsSet = rBigInt.bIsSet;
481 : 5056 : bIsBig = sal_False;
482 : 5056 : nVal = rBigInt.nVal;
483 : : }
484 : 5160 : }
485 : :
486 : 0 : BigInt::BigInt( const rtl::OUString& rString )
487 : : {
488 : 0 : bIsSet = sal_True;
489 : 0 : bIsNeg = sal_False;
490 : 0 : bIsBig = sal_False;
491 : 0 : nVal = 0;
492 : :
493 : 0 : sal_Bool bNeg = sal_False;
494 : 0 : const sal_Unicode* p = rString.getStr();
495 [ # # ]: 0 : if ( *p == '-' )
496 : : {
497 : 0 : bNeg = sal_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;
508 [ # # ]: 0 : else if( bNeg )
509 : 0 : nVal = -nVal;
510 : 0 : }
511 : :
512 : 0 : BigInt::BigInt( double nValue )
513 : : {
514 : 0 : bIsSet = sal_True;
515 : :
516 [ # # ]: 0 : if ( nValue < 0 )
517 : : {
518 : 0 : nValue *= -1;
519 : 0 : bIsNeg = sal_True;
520 : : }
521 : : else
522 : : {
523 : 0 : bIsNeg = sal_False;
524 : : }
525 : :
526 [ # # ]: 0 : if ( nValue < 1 )
527 : : {
528 : 0 : bIsBig = sal_False;
529 : 0 : nVal = 0;
530 : : }
531 : : else
532 : : {
533 : 0 : bIsBig = sal_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 : 738 : BigInt::BigInt( sal_uInt32 nValue )
555 : : {
556 : 738 : bIsSet = sal_True;
557 [ + + ]: 738 : if ( nValue & 0x80000000UL )
558 : : {
559 : 246 : bIsBig = sal_True;
560 : 246 : bIsNeg = sal_False;
561 : 246 : nNum[0] = (sal_uInt16)(nValue & 0xffffUL);
562 : 246 : nNum[1] = (sal_uInt16)(nValue >> 16);
563 : 246 : nLen = 2;
564 : : }
565 : : else
566 : : {
567 : 492 : bIsBig = sal_False;
568 : 492 : nVal = nValue;
569 : : }
570 : 738 : }
571 : :
572 : 246 : BigInt::operator sal_uIntPtr() const
573 : : {
574 [ + - ]: 246 : if ( !bIsBig )
575 : 246 : 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 : 246 : 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 : rtl::OUString BigInt::GetString() const
610 : : {
611 [ # # ]: 0 : String aString;
612 : :
613 [ # # ]: 0 : if ( !bIsBig )
614 [ # # ][ # # ]: 0 : aString = String::CreateFromInt32( nVal );
[ # # ]
615 : : else
616 : : {
617 [ # # ]: 0 : BigInt aTmp( *this );
618 [ # # ]: 0 : BigInt a1000000000( 1000000000L );
619 [ # # ]: 0 : aTmp.Abs();
620 : :
621 [ # # ]: 0 : do
622 : : {
623 [ # # ]: 0 : BigInt a = aTmp;
624 [ # # ]: 0 : a %= a1000000000;
625 [ # # ]: 0 : aTmp /= a1000000000;
626 : :
627 [ # # ]: 0 : String aStr = aString;
628 [ # # ]: 0 : if ( a.nVal < 100000000L )
629 : : { // leading 0s
630 [ # # ][ # # ]: 0 : aString = String::CreateFromInt32( a.nVal + 1000000000L );
[ # # ]
631 [ # # ]: 0 : aString.Erase(0,1);
632 : : }
633 : : else
634 [ # # ][ # # ]: 0 : aString = String::CreateFromInt32( a.nVal );
[ # # ]
635 [ # # ][ # # ]: 0 : aString += aStr;
636 : : }
637 : : while( aTmp.bIsBig );
638 : :
639 [ # # ]: 0 : String aStr = aString;
640 [ # # ]: 0 : if ( bIsNeg )
641 [ # # ][ # # ]: 0 : aString = String::CreateFromInt32( -aTmp.nVal );
[ # # ]
642 : : else
643 [ # # ][ # # ]: 0 : aString = String::CreateFromInt32( aTmp.nVal );
[ # # ]
644 [ # # ][ # # ]: 0 : aString += aStr;
645 : : }
646 : :
647 [ # # ][ # # ]: 0 : return aString;
648 : : }
649 : :
650 : 2952 : BigInt& BigInt::operator=( const BigInt& rBigInt )
651 : : {
652 [ - + ]: 2952 : if ( rBigInt.bIsBig )
653 : 0 : memcpy( (void*)this, (const void*)&rBigInt, sizeof( BigInt ) );
654 : : else
655 : : {
656 : 2952 : bIsSet = rBigInt.bIsSet;
657 : 2952 : bIsBig = sal_False;
658 : 2952 : nVal = rBigInt.nVal;
659 : : }
660 : 2952 : return *this;
661 : : }
662 : :
663 : 335533 : BigInt& BigInt::operator+=( const BigInt& rVal )
664 : : {
665 [ + + ][ + - ]: 335533 : if ( !bIsBig && !rVal.bIsBig )
666 : : {
667 [ + - ][ + - ]: 335343 : if( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG
[ + - ][ + - ]
668 : : && nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
669 : : { // No overflows may occur here
670 : 335343 : nVal += rVal.nVal;
671 : 335343 : return *this;
672 : : }
673 : :
674 [ # # ]: 0 : if( (nVal < 0) != (rVal.nVal < 0) )
675 : : { // No overflows may occur here
676 : 0 : nVal += rVal.nVal;
677 : 0 : return *this;
678 : : }
679 : : }
680 : :
681 [ + - ][ + - ]: 190 : BigInt aTmp1, aTmp2;
682 : 190 : aTmp1.MakeBigInt( *this );
683 : 190 : aTmp2.MakeBigInt( rVal );
684 [ + - ]: 190 : aTmp1.AddLong( aTmp2, *this );
685 : 190 : Normalize();
686 : 335533 : return *this;
687 : : }
688 : :
689 : 50 : BigInt& BigInt::operator-=( const BigInt& rVal )
690 : : {
691 [ + - ][ + - ]: 50 : if ( !bIsBig && !rVal.bIsBig )
692 : : {
693 [ + - ][ + - ]: 50 : if ( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG &&
[ + - ][ + - ]
694 : : nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
695 : : { // No overflows may occur here
696 : 50 : nVal -= rVal.nVal;
697 : 50 : return *this;
698 : : }
699 : :
700 [ # # ]: 0 : if ( (nVal < 0) == (rVal.nVal < 0) )
701 : : { // No overflows may occur here
702 : 0 : nVal -= rVal.nVal;
703 : 0 : return *this;
704 : : }
705 : : }
706 : :
707 [ # # ][ # # ]: 0 : BigInt aTmp1, aTmp2;
708 : 0 : aTmp1.MakeBigInt( *this );
709 : 0 : aTmp2.MakeBigInt( rVal );
710 [ # # ]: 0 : aTmp1.SubLong( aTmp2, *this );
711 : 0 : Normalize();
712 : 50 : return *this;
713 : : }
714 : :
715 : 3573277 : BigInt& BigInt::operator*=( const BigInt& rVal )
716 : : {
717 [ + + ][ + - ]: 3573277 : if ( !bIsBig && !rVal.bIsBig
[ + + ][ + + ]
[ + - ][ + - ]
718 : : && nVal <= MY_MAXSHORT && rVal.nVal <= MY_MAXSHORT
719 : : && nVal >= MY_MINSHORT && rVal.nVal >= MY_MINSHORT )
720 : : // TODO: not optimal !!! W.P.
721 : : { // No overflows may occur here
722 : 3254820 : nVal *= rVal.nVal;
723 : : }
724 : : else
725 : : {
726 [ + - ][ + - ]: 318457 : BigInt aTmp1, aTmp2;
727 : 318457 : aTmp1.MakeBigInt( rVal );
728 : 318457 : aTmp2.MakeBigInt( *this );
729 : 318457 : aTmp1.MultLong(aTmp2, *this);
730 : 318457 : Normalize();
731 : : }
732 : 3573277 : return *this;
733 : : }
734 : :
735 : 336535 : BigInt& BigInt::operator/=( const BigInt& rVal )
736 : : {
737 [ + + ]: 336535 : if ( !rVal.bIsBig )
738 : : {
739 [ - + ]: 336431 : if ( rVal.nVal == 0 )
740 : : {
741 : : OSL_FAIL( "BigInt::operator/ --> divide by zero" );
742 : 0 : return *this;
743 : : }
744 : :
745 [ + + ]: 336431 : if ( !bIsBig )
746 : : {
747 : : // No overflows may occur here
748 : 336241 : nVal /= rVal.nVal;
749 : 336241 : return *this;
750 : : }
751 : :
752 [ - + ]: 190 : if ( rVal.nVal == 1 )
753 : 0 : return *this;
754 : :
755 [ - + ]: 190 : if ( rVal.nVal == -1 )
756 : : {
757 : 0 : bIsNeg = !bIsNeg;
758 : 0 : return *this;
759 : : }
760 : :
761 [ + + ][ + - ]: 190 : if ( rVal.nVal <= (long)0xFFFF && rVal.nVal >= -(long)0xFFFF )
762 : : {
763 : : // Divide BigInt with an sal_uInt16
764 : : sal_uInt16 nTmp;
765 [ - + ]: 104 : if ( rVal.nVal < 0 )
766 : : {
767 : 0 : nTmp = (sal_uInt16) -rVal.nVal;
768 : 0 : bIsNeg = !bIsNeg;
769 : : }
770 : : else
771 : 104 : nTmp = (sal_uInt16) rVal.nVal;
772 : :
773 : 104 : Div( nTmp, nTmp );
774 : 104 : Normalize();
775 : 104 : return *this;
776 : : }
777 : : }
778 : :
779 [ + - ][ - + ]: 190 : if ( ABS_IsLess( rVal ) )
780 : : {
781 [ # # ][ # # ]: 0 : *this = BigInt( (long)0 );
782 : 0 : return *this;
783 : : }
784 : :
785 : : // Divide BigInt with BigInt
786 [ + - ][ + - ]: 190 : BigInt aTmp1, aTmp2;
787 : 190 : aTmp1.MakeBigInt( *this );
788 : 190 : aTmp2.MakeBigInt( rVal );
789 [ + - ]: 190 : aTmp1.DivLong(aTmp2, *this);
790 : 190 : Normalize();
791 : 336535 : return *this;
792 : : }
793 : :
794 : 0 : BigInt& BigInt::operator%=( const BigInt& rVal )
795 : : {
796 [ # # ]: 0 : if ( !rVal.bIsBig )
797 : : {
798 [ # # ]: 0 : if ( rVal.nVal == 0 )
799 : : {
800 : : OSL_FAIL( "BigInt::operator/ --> divide by zero" );
801 : 0 : return *this;
802 : : }
803 : :
804 [ # # ]: 0 : if ( !bIsBig )
805 : : {
806 : : // No overflows may occur here
807 : 0 : nVal %= rVal.nVal;
808 : 0 : return *this;
809 : : }
810 : :
811 [ # # ][ # # ]: 0 : if ( rVal.nVal <= (long)0xFFFF && rVal.nVal >= -(long)0xFFFF )
812 : : {
813 : : // Divide Bigint by short
814 : : sal_uInt16 nTmp;
815 [ # # ]: 0 : if ( rVal.nVal < 0 )
816 : : {
817 : 0 : nTmp = (sal_uInt16) -rVal.nVal;
818 : 0 : bIsNeg = !bIsNeg;
819 : : }
820 : : else
821 : 0 : nTmp = (sal_uInt16) rVal.nVal;
822 : :
823 : 0 : Div( nTmp, nTmp );
824 [ # # ][ # # ]: 0 : *this = BigInt( (long)nTmp );
825 : 0 : return *this;
826 : : }
827 : : }
828 : :
829 [ # # ][ # # ]: 0 : if ( ABS_IsLess( rVal ) )
830 : 0 : return *this;
831 : :
832 : : // Divide BigInt with BigInt
833 [ # # ][ # # ]: 0 : BigInt aTmp1, aTmp2;
834 : 0 : aTmp1.MakeBigInt( *this );
835 : 0 : aTmp2.MakeBigInt( rVal );
836 [ # # ]: 0 : aTmp1.ModLong(aTmp2, *this);
837 : 0 : Normalize();
838 : 0 : return *this;
839 : : }
840 : :
841 : 0 : sal_Bool operator==( const BigInt& rVal1, const BigInt& rVal2 )
842 : : {
843 [ # # ][ # # ]: 0 : if ( rVal1.bIsBig || rVal2.bIsBig )
844 : : {
845 [ # # ][ # # ]: 0 : BigInt nA, nB;
846 : 0 : nA.MakeBigInt( rVal1 );
847 : 0 : nB.MakeBigInt( rVal2 );
848 [ # # ]: 0 : if ( nA.bIsNeg == nB.bIsNeg )
849 : : {
850 [ # # ]: 0 : if ( nA.nLen == nB.nLen )
851 : : {
852 : : int i;
853 [ # # ][ # # ]: 0 : for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
[ # # ]
854 : : {
855 : : }
856 : :
857 : 0 : return nA.nNum[i] == nB.nNum[i];
858 : : }
859 : 0 : return sal_False;
860 : : }
861 : 0 : return sal_False;
862 : : }
863 : 0 : return rVal1.nVal == rVal2.nVal;
864 : : }
865 : :
866 : 895 : sal_Bool operator<( const BigInt& rVal1, const BigInt& rVal2 )
867 : : {
868 [ + - ][ + + ]: 895 : if ( rVal1.bIsBig || rVal2.bIsBig )
869 : : {
870 [ + - ][ + - ]: 246 : BigInt nA, nB;
871 : 246 : nA.MakeBigInt( rVal1 );
872 : 246 : nB.MakeBigInt( rVal2 );
873 [ + - ]: 246 : if ( nA.bIsNeg == nB.bIsNeg )
874 : : {
875 [ + + ]: 246 : if ( nA.nLen == nB.nLen )
876 : : {
877 : : int i;
878 [ + - ][ - + ]: 240 : for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
[ - + ]
879 : : {
880 : : }
881 : :
882 [ - + ]: 240 : if ( nA.bIsNeg )
883 : 0 : return nA.nNum[i] > nB.nNum[i];
884 : : else
885 : 240 : return nA.nNum[i] < nB.nNum[i];
886 : : }
887 [ - + ]: 6 : if ( nA.bIsNeg )
888 : 0 : return nA.nLen > nB.nLen;
889 : : else
890 : 6 : return nA.nLen < nB.nLen;
891 : : }
892 : 246 : return !nB.bIsNeg;
893 : : }
894 : 895 : return rVal1.nVal < rVal2.nVal;
895 : : }
896 : :
897 : 458 : sal_Bool operator >(const BigInt& rVal1, const BigInt& rVal2 )
898 : : {
899 [ + - ][ - + ]: 458 : if ( rVal1.bIsBig || rVal2.bIsBig )
900 : : {
901 [ # # ][ # # ]: 0 : BigInt nA, nB;
902 : 0 : nA.MakeBigInt( rVal1 );
903 : 0 : nB.MakeBigInt( rVal2 );
904 [ # # ]: 0 : if ( nA.bIsNeg == nB.bIsNeg )
905 : : {
906 [ # # ]: 0 : if ( nA.nLen == nB.nLen )
907 : : {
908 : : int i;
909 [ # # ][ # # ]: 0 : for ( i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i-- )
[ # # ]
910 : : {
911 : : }
912 : :
913 [ # # ]: 0 : if ( nA.bIsNeg )
914 : 0 : return nA.nNum[i] < nB.nNum[i];
915 : : else
916 : 0 : return nA.nNum[i] > nB.nNum[i];
917 : : }
918 [ # # ]: 0 : if ( nA.bIsNeg )
919 : 0 : return nA.nLen < nB.nLen;
920 : : else
921 : 0 : return nA.nLen > nB.nLen;
922 : : }
923 : 0 : return !nA.bIsNeg;
924 : : }
925 : :
926 : 458 : return rVal1.nVal > rVal2.nVal;
927 : : }
928 : :
929 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
