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