1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * This file is part of the LibreOffice project.
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/.
9 * This file incorporates work covered by the following license notice:
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 .
22 #include <osl/diagnose.h>
23 #include <tools/bigint.hxx>
29 * The range in which we can perform add/sub without fear of overflow
31 const sal_Int32 MY_MAXLONG
= 0x3fffffff;
32 const sal_Int32 MY_MINLONG
= -MY_MAXLONG
;
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.
41 // TODO: Needs conversion to sal_uInt16/INT16/sal_uInt32/sal_Int32
42 void BigInt::MakeBigInt( const BigInt
& rVal
)
46 memcpy( static_cast<void*>(this), static_cast<const void*>(&rVal
), sizeof( BigInt
) );
47 while ( nLen
> 1 && nNum
[nLen
-1] == 0 )
57 nTmp
= -static_cast<sal_Int64
>(nVal
);
65 nNum
[0] = static_cast<sal_uInt16
>(nTmp
& 0xffffL
);
66 nNum
[1] = static_cast<sal_uInt16
>(nTmp
>> 16);
67 if ( nTmp
& 0xffff0000L
)
74 void BigInt::Normalize()
78 while ( nLen
> 1 && nNum
[nLen
-1] == 0 )
86 else if ( nNum
[1] & 0x8000 )
89 newVal
= (static_cast<sal_Int32
>(nNum
[1]) << 16) + nNum
[0];
97 // else nVal is undefined !!! W.P.
99 // why? nVal is undefined ??? W.P.
100 else if ( nVal
& 0xFFFF0000L
)
106 void BigInt::Mult( const BigInt
&rVal
, sal_uInt16 nMul
)
109 for ( int i
= 0; i
< rVal
.nLen
; i
++ )
111 sal_uInt32 nTmp
= static_cast<sal_uInt32
>(rVal
.nNum
[i
]) * static_cast<sal_uInt32
>(nMul
) + nK
;
112 nK
= static_cast<sal_uInt16
>(nTmp
>> 16);
113 nNum
[i
] = static_cast<sal_uInt16
>(nTmp
);
118 nNum
[rVal
.nLen
] = nK
;
119 nLen
= rVal
.nLen
+ 1;
124 bIsNeg
= rVal
.bIsNeg
;
127 void BigInt::Div( sal_uInt16 nDiv
, sal_uInt16
& rRem
)
130 for ( int i
= nLen
- 1; i
>= 0; i
-- )
132 sal_uInt32 nTmp
= static_cast<sal_uInt32
>(nNum
[i
]) + (nK
<< 16);
133 nNum
[i
] = static_cast<sal_uInt16
>(nTmp
/ nDiv
);
136 rRem
= static_cast<sal_uInt16
>(nK
);
138 if ( nNum
[nLen
-1] == 0 )
142 bool BigInt::IsLess( const BigInt
& rVal
) const
144 if ( rVal
.nLen
< nLen
)
146 if ( rVal
.nLen
> nLen
)
150 for ( i
= nLen
- 1; i
> 0 && nNum
[i
] == rVal
.nNum
[i
]; i
-- )
153 return rVal
.nNum
[i
] < nNum
[i
];
156 void BigInt::AddLong( BigInt
& rB
, BigInt
& rErg
)
158 if ( bIsNeg
== rB
.bIsNeg
)
163 // if length of the two values differ, fill remaining positions
164 // of the smaller value with zeros.
168 for (i
= rB
.nLen
; i
< len
; i
++)
174 for (i
= nLen
; i
< len
; i
++)
178 // Add numerals, starting from the back
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
;
187 rErg
.nNum
[i
] = static_cast<sal_uInt16
>(nZ
& 0xffffL
);
189 // If an overflow occurred, add to solution
190 if (nZ
& 0xff0000L
) // or if(k)
195 // Set length and sign
197 rErg
.bIsNeg
= bIsNeg
&& rB
.bIsNeg
;
199 // If one of the values is negative, perform subtraction instead
203 rB
.SubLong(*this, rErg
);
214 void BigInt::SubLong( BigInt
& rB
, BigInt
& rErg
)
216 if ( bIsNeg
== rB
.bIsNeg
)
222 // if length of the two values differ, fill remaining positions
223 // of the smaller value with zeros.
227 for (i
= rB
.nLen
; i
< len
; i
++)
233 for (i
= nLen
; i
< len
; i
++)
239 for (i
= 0, k
= 0; i
< len
; i
++)
241 nZ
= static_cast<sal_Int32
>(nNum
[i
]) - static_cast<sal_Int32
>(rB
.nNum
[i
]) + k
;
246 rErg
.nNum
[i
] = static_cast<sal_uInt16
>(nZ
& 0xffffL
);
248 rErg
.bIsNeg
= bIsNeg
;
252 for (i
= 0, k
= 0; i
< len
; i
++)
254 nZ
= static_cast<sal_Int32
>(rB
.nNum
[i
]) - static_cast<sal_Int32
>(nNum
[i
]) + k
;
259 rErg
.nNum
[i
] = static_cast<sal_uInt16
>(nZ
& 0xffffL
);
261 // if a < b, revert sign
262 rErg
.bIsNeg
= !bIsNeg
;
266 // If one of the values is negative, perform addition instead
283 void BigInt::MultLong( const BigInt
& rB
, BigInt
& rErg
) const
288 rErg
.bIsNeg
= bIsNeg
!= rB
.bIsNeg
;
289 rErg
.nLen
= nLen
+ rB
.nLen
;
291 for (i
= 0; i
< rErg
.nLen
; i
++)
294 for (j
= 0; j
< rB
.nLen
; j
++)
296 for (i
= 0, k
= 0; i
< nLen
; i
++)
298 nZ
= static_cast<sal_uInt32
>(nNum
[i
]) * static_cast<sal_uInt32
>(rB
.nNum
[j
]) +
299 static_cast<sal_uInt32
>(rErg
.nNum
[i
+ j
]) + k
;
300 rErg
.nNum
[i
+ j
] = static_cast<sal_uInt16
>(nZ
& 0xffffU
);
303 rErg
.nNum
[i
+ j
] = static_cast<sal_uInt16
>(k
);
307 void BigInt::DivLong( const BigInt
& rB
, BigInt
& rErg
) const
310 sal_uInt16 nK
, nQ
, nMult
;
311 sal_uInt16 nLenB
= rB
.nLen
;
312 sal_uInt16 nLenB1
= rB
.nLen
- 1;
315 nMult
= static_cast<sal_uInt16
>(0x10000L
/ (static_cast<sal_Int32
>(rB
.nNum
[nLenB1
]) + 1));
317 aTmpA
.Mult( *this, nMult
);
318 if ( aTmpA
.nLen
== nLen
)
320 aTmpA
.nNum
[aTmpA
.nLen
] = 0;
324 aTmpB
.Mult( rB
, nMult
);
326 for (j
= aTmpA
.nLen
- 1; j
>= nLenB
; j
--)
328 sal_uInt32 nTmp
= ( static_cast<sal_uInt32
>(aTmpA
.nNum
[j
]) << 16 ) + aTmpA
.nNum
[j
- 1];
329 if (aTmpA
.nNum
[j
] == aTmpB
.nNum
[nLenB1
])
332 nQ
= static_cast<sal_uInt16
>(nTmp
/ aTmpB
.nNum
[nLenB1
]);
334 if ( (static_cast<sal_uInt32
>(aTmpB
.nNum
[nLenB1
- 1]) * nQ
) >
335 ((nTmp
- static_cast<sal_uInt32
>(aTmpB
.nNum
[nLenB1
]) * nQ
) << 16) + aTmpA
.nNum
[j
- 2])
339 for (i
= 0; i
< nLenB
; i
++)
341 nTmp
= static_cast<sal_uInt32
>(aTmpA
.nNum
[j
- nLenB
+ i
])
342 - (static_cast<sal_uInt32
>(aTmpB
.nNum
[i
]) * nQ
)
344 aTmpA
.nNum
[j
- nLenB
+ i
] = static_cast<sal_uInt16
>(nTmp
);
345 nK
= static_cast<sal_uInt16
>(nTmp
>> 16);
347 nK
= static_cast<sal_uInt16
>(0x10000U
- nK
);
349 sal_uInt16
& rNum( aTmpA
.nNum
[j
- nLenB
+ i
] );
351 if (aTmpA
.nNum
[j
- nLenB
+ i
] == 0)
352 rErg
.nNum
[j
- nLenB
] = nQ
;
355 rErg
.nNum
[j
- nLenB
] = nQ
- 1;
357 for (i
= 0; i
< nLenB
; i
++)
359 nTmp
= aTmpA
.nNum
[j
- nLenB
+ i
] + aTmpB
.nNum
[i
] + nK
;
360 aTmpA
.nNum
[j
- nLenB
+ i
] = static_cast<sal_uInt16
>(nTmp
& 0xFFFFL
);
361 if (nTmp
& 0xFFFF0000L
)
369 rErg
.bIsNeg
= bIsNeg
!= rB
.bIsNeg
;
370 rErg
.nLen
= nLen
- rB
.nLen
+ 1;
373 void BigInt::ModLong( const BigInt
& rB
, BigInt
& rErg
) const
376 sal_uInt16 nK
, nQ
, nMult
;
377 sal_Int16 nLenB
= rB
.nLen
;
378 sal_Int16 nLenB1
= rB
.nLen
- 1;
381 nMult
= static_cast<sal_uInt16
>(0x10000L
/ (static_cast<sal_Int32
>(rB
.nNum
[nLenB1
]) + 1));
383 aTmpA
.Mult( *this, nMult
);
384 if ( aTmpA
.nLen
== nLen
)
386 aTmpA
.nNum
[aTmpA
.nLen
] = 0;
390 aTmpB
.Mult( rB
, nMult
);
392 for (j
= aTmpA
.nLen
- 1; j
>= nLenB
; j
--)
394 sal_uInt32 nTmp
= ( static_cast<sal_uInt32
>(aTmpA
.nNum
[j
]) << 16 ) + aTmpA
.nNum
[j
- 1];
395 if (aTmpA
.nNum
[j
] == aTmpB
.nNum
[nLenB1
])
398 nQ
= static_cast<sal_uInt16
>(nTmp
/ aTmpB
.nNum
[nLenB1
]);
400 if ( (static_cast<sal_uInt32
>(aTmpB
.nNum
[nLenB1
- 1]) * nQ
) >
401 ((nTmp
- aTmpB
.nNum
[nLenB1
] * nQ
) << 16) + aTmpA
.nNum
[j
- 2])
405 for (i
= 0; i
< nLenB
; i
++)
407 nTmp
= static_cast<sal_uInt32
>(aTmpA
.nNum
[j
- nLenB
+ i
])
408 - (static_cast<sal_uInt32
>(aTmpB
.nNum
[i
]) * nQ
)
410 aTmpA
.nNum
[j
- nLenB
+ i
] = static_cast<sal_uInt16
>(nTmp
);
411 nK
= static_cast<sal_uInt16
>(nTmp
>> 16);
413 nK
= static_cast<sal_uInt16
>(0x10000U
- nK
);
415 sal_uInt16
& rNum( aTmpA
.nNum
[j
- nLenB
+ i
] );
417 if (aTmpA
.nNum
[j
- nLenB
+ i
] == 0)
418 rErg
.nNum
[j
- nLenB
] = nQ
;
421 rErg
.nNum
[j
- nLenB
] = nQ
- 1;
423 for (i
= 0; i
< nLenB
; i
++) {
424 nTmp
= aTmpA
.nNum
[j
- nLenB
+ i
] + aTmpB
.nNum
[i
] + nK
;
425 aTmpA
.nNum
[j
- nLenB
+ i
] = static_cast<sal_uInt16
>(nTmp
& 0xFFFFL
);
426 if (nTmp
& 0xFFFF0000L
)
435 rErg
.Div( nMult
, nQ
);
438 bool BigInt::ABS_IsLess( const BigInt
& rB
) const
440 if (nLen
!= 0 || rB
.nLen
!= 0)
443 nA
.MakeBigInt( *this );
445 if (nA
.nLen
== nB
.nLen
)
448 for (i
= nA
.nLen
- 1; i
> 0 && nA
.nNum
[i
] == nB
.nNum
[i
]; i
--)
451 return nA
.nNum
[i
] < nB
.nNum
[i
];
454 return nA
.nLen
< nB
.nLen
;
458 return nVal
> rB
.nVal
;
460 return nVal
> -rB
.nVal
;
463 return nVal
< -rB
.nVal
;
465 return nVal
< rB
.nVal
;
468 BigInt::BigInt( const BigInt
& rBigInt
)
472 if ( rBigInt
.nLen
!= 0 )
473 memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt
), sizeof( BigInt
) );
478 BigInt::BigInt( const OUString
& rString
)
485 const sal_Unicode
* p
= rString
.getStr();
491 while( *p
>= '0' && *p
<= '9' )
503 BigInt::BigInt( double nValue
)
525 while ( ( nValue
> 65536.0 ) && ( i
< MAX_DIGITS
) )
527 nNum
[i
] = static_cast<sal_uInt16
>(fmod( nValue
, 65536.0 ));
532 if ( i
< MAX_DIGITS
)
533 nNum
[i
++] = static_cast<sal_uInt16
>(nValue
);
542 BigInt::BigInt( sal_uInt32 nValue
)
545 if ( nValue
& 0x80000000U
)
548 nNum
[0] = static_cast<sal_uInt16
>(nValue
& 0xffffU
);
549 nNum
[1] = static_cast<sal_uInt16
>(nValue
>> 16);
560 BigInt::BigInt( sal_Int64 nValue
)
566 if ((nValue
>= SAL_MIN_INT32
) && (nValue
<= SAL_MAX_INT32
))
568 nVal
= static_cast<sal_Int32
>(nValue
);
572 sal_uInt64 nUValue
= static_cast<sal_uInt64
>(bIsNeg
? -nValue
: nValue
);
573 for (int i
= 0; (i
!= sizeof(sal_uInt64
) / 2) && (nUValue
!= 0); ++i
)
575 nNum
[i
] = static_cast<sal_uInt16
>(nUValue
& 0xffffUL
);
576 nUValue
= nUValue
>> 16;
582 BigInt::operator double() const
585 return static_cast<double>(nVal
);
589 double nRet
= static_cast<double>(static_cast<sal_uInt32
>(nNum
[i
]));
595 nRet
+= static_cast<double>(static_cast<sal_uInt32
>(nNum
[i
]));
605 BigInt
& BigInt::operator=( const BigInt
& rBigInt
)
607 if (this == &rBigInt
)
610 if ( rBigInt
.nLen
!= 0 )
611 memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt
), sizeof( BigInt
) );
620 BigInt
& BigInt::operator+=( const BigInt
& rVal
)
622 if ( nLen
== 0 && rVal
.nLen
== 0 )
624 if( nVal
<= MY_MAXLONG
&& rVal
.nVal
<= MY_MAXLONG
625 && nVal
>= MY_MINLONG
&& rVal
.nVal
>= MY_MINLONG
)
626 { // No overflows may occur here
631 if( (nVal
< 0) != (rVal
.nVal
< 0) )
632 { // No overflows may occur here
639 aTmp1
.MakeBigInt( *this );
640 aTmp2
.MakeBigInt( rVal
);
641 aTmp1
.AddLong( aTmp2
, *this );
646 BigInt
& BigInt::operator-=( const BigInt
& rVal
)
648 if ( nLen
== 0 && rVal
.nLen
== 0 )
650 if ( nVal
<= MY_MAXLONG
&& rVal
.nVal
<= MY_MAXLONG
&&
651 nVal
>= MY_MINLONG
&& rVal
.nVal
>= MY_MINLONG
)
652 { // No overflows may occur here
657 if ( (nVal
< 0) == (rVal
.nVal
< 0) )
658 { // No overflows may occur here
665 aTmp1
.MakeBigInt( *this );
666 aTmp2
.MakeBigInt( rVal
);
667 aTmp1
.SubLong( aTmp2
, *this );
672 BigInt
& BigInt::operator*=( const BigInt
& rVal
)
674 static const sal_Int32 MY_MAXSHORT
= 0x00007fff;
675 static const sal_Int32 MY_MINSHORT
= -MY_MAXSHORT
;
677 if ( nLen
== 0 && rVal
.nLen
== 0
678 && nVal
<= MY_MAXSHORT
&& rVal
.nVal
<= MY_MAXSHORT
679 && nVal
>= MY_MINSHORT
&& rVal
.nVal
>= MY_MINSHORT
)
680 // TODO: not optimal !!! W.P.
681 { // No overflows may occur here
687 aTmp1
.MakeBigInt( rVal
);
688 aTmp2
.MakeBigInt( *this );
689 aTmp1
.MultLong(aTmp2
, *this);
695 BigInt
& BigInt::operator/=( const BigInt
& rVal
)
697 if ( rVal
.nLen
== 0 )
699 if ( rVal
.nVal
== 0 )
701 OSL_FAIL( "BigInt::operator/ --> divide by zero" );
707 // No overflows may occur here
712 if ( rVal
.nVal
== 1 )
715 if ( rVal
.nVal
== -1 )
721 if ( rVal
.nVal
<= 0xFFFF && rVal
.nVal
>= -0xFFFF )
723 // Divide BigInt with an sal_uInt16
727 nTmp
= static_cast<sal_uInt16
>(-rVal
.nVal
);
731 nTmp
= static_cast<sal_uInt16
>(rVal
.nVal
);
739 if ( ABS_IsLess( rVal
) )
745 // Divide BigInt with BigInt
747 aTmp1
.MakeBigInt( *this );
748 aTmp2
.MakeBigInt( rVal
);
749 aTmp1
.DivLong(aTmp2
, *this);
754 BigInt
& BigInt::operator%=( const BigInt
& rVal
)
756 if ( rVal
.nLen
== 0 )
758 if ( rVal
.nVal
== 0 )
760 OSL_FAIL( "BigInt::operator/ --> divide by zero" );
766 // No overflows may occur here
771 if ( rVal
.nVal
<= 0xFFFF && rVal
.nVal
>= -0xFFFF )
773 // Divide Bigint by int16
777 nTmp
= static_cast<sal_uInt16
>(-rVal
.nVal
);
781 nTmp
= static_cast<sal_uInt16
>(rVal
.nVal
);
784 *this = BigInt( nTmp
);
789 if ( ABS_IsLess( rVal
) )
792 // Divide BigInt with BigInt
794 aTmp1
.MakeBigInt( *this );
795 aTmp2
.MakeBigInt( rVal
);
796 aTmp1
.ModLong(aTmp2
, *this);
801 bool operator==( const BigInt
& rVal1
, const BigInt
& rVal2
)
803 if (rVal1
.nLen
== 0 && rVal2
.nLen
== 0)
804 return rVal1
.nVal
== rVal2
.nVal
;
807 nA
.MakeBigInt(rVal1
);
808 nB
.MakeBigInt(rVal2
);
809 return nA
.bIsNeg
== nB
.bIsNeg
&& nA
.nLen
== nB
.nLen
810 && std::equal(nA
.nNum
, nA
.nNum
+ nA
.nLen
, nB
.nNum
);
813 bool operator<( const BigInt
& rVal1
, const BigInt
& rVal2
)
815 if (rVal1
.nLen
== 0 && rVal2
.nLen
== 0)
816 return rVal1
.nVal
< rVal2
.nVal
;
819 nA
.MakeBigInt(rVal1
);
820 nB
.MakeBigInt(rVal2
);
821 if (nA
.bIsNeg
!= nB
.bIsNeg
)
823 if (nA
.nLen
!= nB
.nLen
)
824 return nA
.bIsNeg
? (nA
.nLen
> nB
.nLen
) : (nA
.nLen
< nB
.nLen
);
826 while (i
> 0 && nA
.nNum
[i
] == nB
.nNum
[i
])
828 return nA
.bIsNeg
? (nA
.nNum
[i
] > nB
.nNum
[i
]) : (nA
.nNum
[i
] < nB
.nNum
[i
]);
831 tools::Long
BigInt::Scale( tools::Long nVal
, tools::Long nMul
, tools::Long nDiv
)
837 if ( aVal
.IsNeg() != ( nDiv
< 0 ) )
838 aVal
-= nDiv
/ 2; // for correct rounding
840 aVal
+= nDiv
/ 2; // for correct rounding
844 return tools::Long( aVal
);
847 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */