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 <limits.h>
21 : : #include <tools/debug.hxx>
22 : : #include <tools/fract.hxx>
23 : : #include <tools/stream.hxx>
24 : : #include <tools/bigint.hxx>
25 : :
26 : : /** Compute greates common divisor using Euclidian algorithm
27 : :
28 : : As the algorithm works on positive values only, the absolute value
29 : : of each parameter is used.
30 : :
31 : : @param nVal1
32 : : @param nVal2
33 : :
34 : : @note: If one parameter is {0,1}, GetGGT returns 1.
35 : : */
36 : 6980723 : static long GetGGT( long nVal1, long nVal2 )
37 : : {
38 : 6980723 : nVal1 = Abs( nVal1 );
39 : 6980723 : nVal2 = Abs( nVal2 );
40 : :
41 [ + + ][ + + ]: 6980723 : if ( nVal1 <= 1 || nVal2 <= 1 )
42 : 6057523 : return 1;
43 : :
44 [ + + ]: 5931969 : while ( nVal1 != nVal2 )
45 : : {
46 [ + + ]: 5870946 : if ( nVal1 > nVal2 )
47 : : {
48 : 2909161 : nVal1 %= nVal2;
49 [ + + ]: 2909161 : if ( nVal1 == 0 )
50 : 549691 : return nVal2;
51 : : }
52 : : else
53 : : {
54 : 2961785 : nVal2 %= nVal1;
55 [ + + ]: 2961785 : if ( nVal2 == 0 )
56 : 312486 : return nVal1;
57 : : }
58 : : }
59 : 6980723 : return nVal1;
60 : : }
61 : :
62 : 0 : static void Reduce( BigInt &rVal1, BigInt &rVal2 )
63 : : {
64 [ # # ]: 0 : BigInt nA( rVal1 );
65 [ # # ]: 0 : BigInt nB( rVal2 );
66 [ # # ]: 0 : nA.Abs();
67 [ # # ]: 0 : nB.Abs();
68 : :
69 [ # # ][ # # ]: 0 : if ( nA.IsOne() || nB.IsOne() || nA.IsZero() || nB.IsZero() )
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ]
70 : : return;
71 : :
72 [ # # ][ # # ]: 0 : while ( nA != nB )
73 : : {
74 [ # # ][ # # ]: 0 : if ( nA > nB )
75 : : {
76 [ # # ]: 0 : nA %= nB;
77 [ # # ][ # # ]: 0 : if ( nA.IsZero() )
78 : : {
79 [ # # ]: 0 : rVal1 /= nB;
80 [ # # ]: 0 : rVal2 /= nB;
81 : : return;
82 : : }
83 : : }
84 : : else
85 : : {
86 [ # # ]: 0 : nB %= nA;
87 [ # # ][ # # ]: 0 : if ( nB.IsZero() )
88 : : {
89 [ # # ]: 0 : rVal1 /= nA;
90 [ # # ]: 0 : rVal2 /= nA;
91 : : return;
92 : : }
93 : : }
94 : : }
95 : :
96 [ # # ]: 0 : rVal1 /= nA;
97 [ # # ]: 0 : rVal2 /= nB;
98 : : }
99 : :
100 : : // Initialized by setting nNum as nominator and nDen as denominator
101 : : // Negative values in the denominator are invalid and cause the
102 : : // inversion of both nominator and denominator signs
103 : : // in order to return the correct value.
104 : 3719577 : Fraction::Fraction( long nNum, long nDen )
105 : : {
106 : 3719577 : nNumerator = nNum;
107 : 3719577 : nDenominator = nDen;
108 [ + + ]: 3719577 : if ( nDenominator < 0 )
109 : : {
110 : 138982 : nDenominator = -nDenominator;
111 : 138982 : nNumerator = -nNumerator;
112 : : }
113 : :
114 : : // Reduce through GCD
115 : 3719577 : long n = GetGGT( nNumerator, nDenominator );
116 : 3719577 : nNumerator /= n;
117 : 3719577 : nDenominator /= n;
118 : 3719577 : }
119 : :
120 : : // If dVal > LONG_MAX, the fraction is set as invalid.
121 : : // Otherwise, dVal and denominator are multiplied with 10, until one of them
122 : : // is larger than (LONG_MAX / 10) and the fraction is reduced with GCD
123 : 22478 : Fraction::Fraction( double dVal )
124 : : {
125 : 22478 : long nDen = 1;
126 : 22478 : long nMAX = LONG_MAX / 10;
127 : :
128 [ + - ][ - + ]: 22478 : if ( dVal > LONG_MAX || dVal < LONG_MIN )
129 : : {
130 : 0 : nNumerator = 0;
131 : 0 : nDenominator = -1;
132 : 22478 : return;
133 : : }
134 : :
135 [ + + ][ + + ]: 224700 : while ( Abs( (long)dVal ) < nMAX && nDen < nMAX )
[ + + ]
136 : : {
137 : 202222 : dVal *= 10;
138 : 202222 : nDen *= 10;
139 : : }
140 : 22478 : nNumerator = (long)dVal;
141 : 22478 : nDenominator = nDen;
142 : :
143 : : // Reduce through GCD
144 : 22478 : long n = GetGGT( nNumerator, nDenominator );
145 : 22478 : nNumerator /= n;
146 : 22478 : nDenominator /= n;
147 : : }
148 : :
149 : 217814 : Fraction::operator double() const
150 : : {
151 [ + - ]: 217814 : if ( nDenominator > 0 )
152 : 217814 : return (double)nNumerator / (double)nDenominator;
153 : : else
154 : 217814 : return (double)0;
155 : : }
156 : :
157 : : // This methods first validates both values.
158 : : // If one of the arguments is invalid, the whole operation is invalid.
159 : : // For addition both fractions are extended to match the denominator,
160 : : // then nominators are added and reduced (through GCD).
161 : : // Internal datatype for computation is SLong to detect overflows,
162 : : // which cause the operation to be marked as invalid
163 : 0 : Fraction& Fraction::operator += ( const Fraction& rVal )
164 : : {
165 [ # # ][ # # ]: 0 : if ( !rVal.IsValid() )
166 : : {
167 : 0 : nNumerator = 0;
168 : 0 : nDenominator = -1;
169 : : }
170 [ # # ][ # # ]: 0 : if ( !IsValid() )
171 : 0 : return *this;
172 : :
173 : : // (a/b) + (c/d) = ( (a*d) + (c*b) ) / (b*d)
174 [ # # ]: 0 : BigInt nN( nNumerator );
175 [ # # ][ # # ]: 0 : nN *= BigInt( rVal.nDenominator );
176 [ # # ]: 0 : BigInt nW1Temp( nDenominator );
177 [ # # ][ # # ]: 0 : nW1Temp *= BigInt( rVal.nNumerator );
178 [ # # ]: 0 : nN += nW1Temp;
179 : :
180 [ # # ]: 0 : BigInt nD( nDenominator );
181 [ # # ][ # # ]: 0 : nD *= BigInt( rVal.nDenominator );
182 : :
183 [ # # ]: 0 : Reduce( nN, nD );
184 : :
185 [ # # ][ # # ]: 0 : if ( nN.bIsBig || nD.bIsBig )
186 : : {
187 : 0 : nNumerator = 0;
188 : 0 : nDenominator = -1;
189 : : }
190 : : else
191 : : {
192 [ # # ]: 0 : nNumerator = (long)nN,
193 [ # # ]: 0 : nDenominator = (long)nD;
194 : : }
195 : :
196 : 0 : return *this;
197 : : }
198 : :
199 : : // This methods first validates both values.
200 : : // If one of the arguments is invalid, the whole operation is invalid.
201 : : // For substraction, both fractions are extended to match the denominator,
202 : : // then nominators are substracted and reduced (through GCD).
203 : : // Internal datatype for computation is SLong to detect overflows,
204 : : // which cause the operation to be marked as invalid
205 : 0 : Fraction& Fraction::operator -= ( const Fraction& rVal )
206 : : {
207 [ # # ][ # # ]: 0 : if ( !rVal.IsValid() )
208 : : {
209 : 0 : nNumerator = 0;
210 : 0 : nDenominator = -1;
211 : : }
212 [ # # ][ # # ]: 0 : if ( !IsValid() )
213 : 0 : return *this;
214 : :
215 : : // (a/b) - (c/d) = ( (a*d) - (c*b) ) / (b*d)
216 [ # # ]: 0 : BigInt nN( nNumerator );
217 [ # # ][ # # ]: 0 : nN *= BigInt( rVal.nDenominator );
218 [ # # ]: 0 : BigInt nW1Temp( nDenominator );
219 [ # # ][ # # ]: 0 : nW1Temp *= BigInt( rVal.nNumerator );
220 [ # # ]: 0 : nN -= nW1Temp;
221 : :
222 [ # # ]: 0 : BigInt nD( nDenominator );
223 [ # # ][ # # ]: 0 : nD *= BigInt( rVal.nDenominator );
224 : :
225 [ # # ]: 0 : Reduce( nN, nD );
226 : :
227 [ # # ][ # # ]: 0 : if ( nN.bIsBig || nD.bIsBig )
228 : : {
229 : 0 : nNumerator = 0;
230 : 0 : nDenominator = -1;
231 : : }
232 : : else
233 : : {
234 [ # # ]: 0 : nNumerator = (long)nN,
235 [ # # ]: 0 : nDenominator = (long)nD;
236 : : }
237 : :
238 : 0 : return *this;
239 : : }
240 : :
241 : : // This methods first validates both values.
242 : : // If one of the arguments is invalid, the whole operation is invalid.
243 : : // For mutliplication, nominator and denominators are first reduced
244 : : // (through GCD), and then multiplied.
245 : : // Internal datatype for computation is BigInt to detect overflows,
246 : : // which cause the operation to be marked as invalid
247 : 1615367 : Fraction& Fraction::operator *= ( const Fraction& rVal )
248 : : {
249 [ + - ][ - + ]: 1615367 : if ( !rVal.IsValid() )
250 : : {
251 : 0 : nNumerator = 0;
252 : 0 : nDenominator = -1;
253 : : }
254 [ + - ][ - + ]: 1615367 : if ( !IsValid() )
255 : 0 : return *this;
256 : :
257 [ + - ]: 1615367 : long nGGT1 = GetGGT( nNumerator, rVal.nDenominator );
258 [ + - ]: 1615367 : long nGGT2 = GetGGT( rVal.nNumerator, nDenominator );
259 [ + - ]: 1615367 : BigInt nN( nNumerator / nGGT1 );
260 [ + - ][ + - ]: 1615367 : nN *= BigInt( rVal.nNumerator / nGGT2 );
261 [ + - ]: 1615367 : BigInt nD( nDenominator / nGGT2 );
262 [ + - ][ + - ]: 1615367 : nD *= BigInt( rVal.nDenominator / nGGT1 );
263 : :
264 [ + - ][ + + ]: 1615367 : if ( nN.bIsBig || nD.bIsBig )
265 : : {
266 : 119103 : nNumerator = 0;
267 : 119103 : nDenominator = -1;
268 : : }
269 : : else
270 : : {
271 [ + - ]: 1496264 : nNumerator = (long)nN,
272 [ + - ]: 1496264 : nDenominator = (long)nD;
273 : : }
274 : :
275 : 1615367 : return *this;
276 : : }
277 : :
278 : : // This methods first validates both values.
279 : : // If one of the arguments is invalid, the whole operation is invalid.
280 : : // For dividing a/b, we multiply a with the inverse of b.
281 : : // To avoid overflows, we first reduce both fractions with GCD.
282 : : // Internal datatype for computation is BigInt to detect overflows,
283 : : // which cause the operation to be marked as invalid
284 : 2884 : Fraction& Fraction::operator /= ( const Fraction& rVal )
285 : : {
286 [ + - ][ - + ]: 2884 : if ( !rVal.IsValid() )
287 : : {
288 : 0 : nNumerator = 0;
289 : 0 : nDenominator = -1;
290 : : }
291 [ + - ][ - + ]: 2884 : if ( !IsValid() )
292 : 0 : return *this;
293 : :
294 [ + - ]: 2884 : long nGGT1 = GetGGT( nNumerator, rVal.nNumerator );
295 [ + - ]: 2884 : long nGGT2 = GetGGT( rVal.nDenominator, nDenominator );
296 [ + - ]: 2884 : BigInt nN( nNumerator / nGGT1 );
297 [ + - ][ + - ]: 2884 : nN *= BigInt( rVal.nDenominator / nGGT2 );
298 [ + - ]: 2884 : BigInt nD( nDenominator / nGGT2 );
299 [ + - ][ + - ]: 2884 : nD *= BigInt( rVal.nNumerator / nGGT1 );
300 : :
301 [ + - ][ - + ]: 2884 : if ( nN.bIsBig || nD.bIsBig )
302 : : {
303 : 0 : nNumerator = 0;
304 : 0 : nDenominator = -1;
305 : : }
306 : : else
307 : : {
308 [ + - ]: 2884 : nNumerator = (long)nN,
309 [ + - ]: 2884 : nDenominator = (long)nD;
310 [ - + ]: 2884 : if ( nDenominator < 0 )
311 : : {
312 : 0 : nDenominator = -nDenominator;
313 : 0 : nNumerator = -nNumerator;
314 : : }
315 : : }
316 : :
317 : 2884 : return *this;
318 : : }
319 : :
320 : : // Similar to clz_table that can be googled
321 : : const char nbits_table[32] =
322 : : {
323 : : 32, 1, 23, 2, 29, 24, 14, 3,
324 : : 30, 27, 25, 18, 20, 15, 10, 4,
325 : : 31, 22, 28, 13, 26, 17, 19, 9,
326 : : 21, 12, 16, 8, 11, 7, 6, 5
327 : : };
328 : :
329 : 4332 : static int impl_NumberOfBits( unsigned long nNum )
330 : : {
331 : : // http://en.wikipedia.org/wiki/De_Bruijn_sequence
332 : : // background paper: Using de Bruijn Sequences to Index a 1 in a
333 : : // Computer Word (1998) Charles E. Leiserson,
334 : : // Harald Prokop, Keith H. Randall
335 : : // (e.g. http://citeseer.ist.psu.edu/leiserson98using.html)
336 : 4332 : const sal_uInt32 nDeBruijn = 0x7DCD629;
337 : :
338 [ - + ]: 4332 : if ( nNum == 0 )
339 : 0 : return 0;
340 : :
341 : : // Get it to form like 0000001111111111b
342 : 4332 : nNum |= ( nNum >> 1 );
343 : 4332 : nNum |= ( nNum >> 2 );
344 : 4332 : nNum |= ( nNum >> 4 );
345 : 4332 : nNum |= ( nNum >> 8 );
346 : 4332 : nNum |= ( nNum >> 16 );
347 : :
348 : : sal_uInt32 nNumber;
349 : 4332 : int nBonus = 0;
350 : :
351 : : #if SAL_TYPES_SIZEOFLONG == 4
352 : 4332 : nNumber = nNum;
353 : : #elif SAL_TYPES_SIZEOFLONG == 8
354 : : nNum |= ( nNum >> 32 );
355 : :
356 : : if ( nNum & 0x80000000 )
357 : : {
358 : : nNumber = sal_uInt32( nNum >> 32 );
359 : : nBonus = 32;
360 : :
361 : : if ( nNumber == 0 )
362 : : return 32;
363 : : }
364 : : else
365 : : nNumber = sal_uInt32( nNum & 0xFFFFFFFF );
366 : : #else
367 : : #error "Unknown size of long!"
368 : : #endif
369 : :
370 : : // De facto shift left of nDeBruijn using multiplication (nNumber
371 : : // is all ones from topmost bit, thus nDeBruijn + (nDeBruijn *
372 : : // nNumber) => nDeBruijn * (nNumber+1) clears all those bits to
373 : : // zero, sets the next bit to one, and thus effectively shift-left
374 : : // nDeBruijn by lg2(nNumber+1). This generates a distinct 5bit
375 : : // sequence in the msb for each distinct position of the last
376 : : // leading 0 bit - that's the property of a de Bruijn number.
377 : 4332 : nNumber = nDeBruijn + ( nDeBruijn * nNumber );
378 : :
379 : : // 5-bit window indexes the result
380 : 4332 : return ( nbits_table[nNumber >> 27] ) + nBonus;
381 : : }
382 : :
383 : : /** Inaccurate cancellation for a fraction.
384 : :
385 : : Clip both nominator and denominator to said number of bits. If
386 : : either of those already have equal or less number of bits used,
387 : : this method does nothing.
388 : :
389 : : @param nSignificantBits denotes, how many significant binary
390 : : digits to maintain, in both nominator and denominator.
391 : :
392 : : @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
393 : : largest error occurs with the following pair of values:
394 : :
395 : : binary 1000000011111111111111111111111b/1000000000000000000000000000000b
396 : : = 1082130431/1073741824
397 : : = approx. 1.007812499
398 : :
399 : : A ReduceInaccurate(8) yields 1/1.
400 : : */
401 : 2166 : void Fraction::ReduceInaccurate( unsigned nSignificantBits )
402 : : {
403 [ + - ][ - + ]: 2166 : if ( !nNumerator || !nDenominator )
404 : 0 : return;
405 : :
406 : : // Count with unsigned longs only
407 : 2166 : const bool bNeg = ( nNumerator < 0 );
408 [ - + ]: 2166 : unsigned long nMul = (unsigned long)( bNeg? -nNumerator: nNumerator );
409 : 2166 : unsigned long nDiv = (unsigned long)( nDenominator );
410 : :
411 : : DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!");
412 : :
413 : : // How much bits can we lose?
414 : 2166 : const int nMulBitsToLose = Max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 );
415 : 2166 : const int nDivBitsToLose = Max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 );
416 : :
417 : 2166 : const int nToLose = Min( nMulBitsToLose, nDivBitsToLose );
418 : :
419 : : // Remove the bits
420 : 2166 : nMul >>= nToLose;
421 : 2166 : nDiv >>= nToLose;
422 : :
423 [ - + ][ + - ]: 2166 : if ( !nMul || !nDiv )
424 : : {
425 : : // Return without reduction
426 : : OSL_FAIL( "Oops, we reduced too much..." );
427 : 0 : return;
428 : : }
429 : :
430 : : // Reduce
431 : 2166 : long n1 = GetGGT( nMul, nDiv );
432 [ + + ]: 2166 : if ( n1 != 1 )
433 : : {
434 : 959 : nMul /= n1;
435 : 959 : nDiv /= n1;
436 : : }
437 : :
438 [ - + ]: 2166 : nNumerator = bNeg? -long( nMul ): long( nMul );
439 : 2166 : nDenominator = nDiv;
440 : : }
441 : :
442 : 199845 : bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )
443 : : {
444 [ + - ][ - + ]: 199845 : if ( !rVal1.IsValid() || !rVal2.IsValid() )
[ - + ]
445 : 0 : return false;
446 : :
447 : : return rVal1.nNumerator == rVal2.nNumerator
448 [ + + ][ + + ]: 199845 : && rVal1.nDenominator == rVal2.nDenominator;
449 : : }
450 : :
451 : : // This methods first validates and reduces both values.
452 : : // To compare (a/b) with (c/d), extend denominators (b*d), then return
453 : : // the result of comparing the nominators (a < c)
454 : 458 : bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )
455 : : {
456 [ + - ][ + - ]: 458 : if ( !rVal1.IsValid() || !rVal2.IsValid() )
[ + - ][ - + ]
[ - + ]
457 : 0 : return false;
458 : :
459 [ + - ]: 458 : BigInt nN( rVal1.nNumerator );
460 [ + - ][ + - ]: 458 : nN *= BigInt( rVal2.nDenominator );
461 [ + - ]: 458 : BigInt nD( rVal1.nDenominator );
462 [ + - ][ + - ]: 458 : nD *= BigInt( rVal2.nNumerator );
463 : :
464 [ + - ]: 458 : return nN < nD;
465 : : }
466 : :
467 : : // This methods first validates and reduces both values.
468 : : // To compare (a/b) with (c/d), extend denominators (b*d), then return
469 : : // the result of comparing nominators (a > c)
470 : 458 : bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )
471 : : {
472 [ + - ][ + - ]: 458 : if ( !rVal1.IsValid() || !rVal2.IsValid() )
[ + - ][ - + ]
[ - + ]
473 : 0 : return false;
474 : :
475 [ + - ]: 458 : BigInt nN( rVal1.nNumerator );
476 [ + - ][ + - ]: 458 : nN *= BigInt( rVal2.nDenominator );
477 [ + - ]: 458 : BigInt nD( rVal1.nDenominator);
478 [ + - ][ + - ]: 458 : nD *= BigInt( rVal2.nNumerator );
479 : :
480 [ + - ]: 458 : return nN > nD;
481 : : }
482 : :
483 : 17690 : SvStream& operator >> ( SvStream& rIStream, Fraction& rFract )
484 : : {
485 : : //fdo#39428 SvStream no longer supports operator>>(long&)
486 : 17690 : sal_Int32 nTmp(0);
487 [ + - ]: 17690 : rIStream >> nTmp;
488 : 17690 : rFract.nNumerator = nTmp;
489 [ + - ]: 17690 : rIStream >> nTmp;
490 : 17690 : rFract.nDenominator = nTmp;
491 : 17690 : return rIStream;
492 : : }
493 : :
494 : 18844 : SvStream& operator << ( SvStream& rOStream, const Fraction& rFract )
495 : : {
496 : : //fdo#39428 SvStream no longer supports operator<<(long)
497 : 18844 : rOStream << sal::static_int_cast<sal_Int32>(rFract.nNumerator);
498 : 18844 : rOStream << sal::static_int_cast<sal_Int32>(rFract.nDenominator);
499 : 18844 : return rOStream;
500 : : }
501 : :
502 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
