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 712397 : static long GetGGT( long nVal1, long nVal2 )
37 : {
38 712397 : nVal1 = Abs( nVal1 );
39 712397 : nVal2 = Abs( nVal2 );
40 :
41 712397 : if ( nVal1 <= 1 || nVal2 <= 1 )
42 669261 : return 1;
43 :
44 184240 : while ( nVal1 != nVal2 )
45 : {
46 131563 : if ( nVal1 > nVal2 )
47 : {
48 66981 : nVal1 %= nVal2;
49 66981 : if ( nVal1 == 0 )
50 25350 : return nVal2;
51 : }
52 : else
53 : {
54 64582 : nVal2 %= nVal1;
55 64582 : if ( nVal2 == 0 )
56 8245 : return nVal1;
57 : }
58 : }
59 9541 : 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 370825 : Fraction::Fraction( long nNum, long nDen )
105 : {
106 370825 : nNumerator = nNum;
107 370825 : nDenominator = nDen;
108 370825 : if ( nDenominator < 0 )
109 : {
110 5504 : nDenominator = -nDenominator;
111 5504 : nNumerator = -nNumerator;
112 : }
113 :
114 : // Reduce through GCD
115 370825 : long n = GetGGT( nNumerator, nDenominator );
116 370825 : nNumerator /= n;
117 370825 : nDenominator /= n;
118 370825 : }
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 12 : Fraction::Fraction( double dVal )
124 : {
125 12 : long nDen = 1;
126 12 : long nMAX = LONG_MAX / 10;
127 :
128 12 : if ( dVal > LONG_MAX || dVal < LONG_MIN )
129 : {
130 0 : nNumerator = 0;
131 0 : nDenominator = -1;
132 12 : return;
133 : }
134 :
135 114 : while ( Abs( (long)dVal ) < nMAX && nDen < nMAX )
136 : {
137 90 : dVal *= 10;
138 90 : nDen *= 10;
139 : }
140 12 : nNumerator = (long)dVal;
141 12 : nDenominator = nDen;
142 :
143 : // Reduce through GCD
144 12 : long n = GetGGT( nNumerator, nDenominator );
145 12 : nNumerator /= n;
146 12 : nDenominator /= n;
147 : }
148 :
149 6740 : Fraction::operator double() const
150 : {
151 6740 : if ( nDenominator > 0 )
152 6740 : return (double)nNumerator / (double)nDenominator;
153 : else
154 0 : 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 169802 : Fraction& Fraction::operator *= ( const Fraction& rVal )
248 : {
249 169802 : if ( !rVal.IsValid() )
250 : {
251 0 : nNumerator = 0;
252 0 : nDenominator = -1;
253 : }
254 169802 : if ( !IsValid() )
255 0 : return *this;
256 :
257 169802 : long nGGT1 = GetGGT( nNumerator, rVal.nDenominator );
258 169802 : long nGGT2 = GetGGT( rVal.nNumerator, nDenominator );
259 169802 : BigInt nN( nNumerator / nGGT1 );
260 169802 : nN *= BigInt( rVal.nNumerator / nGGT2 );
261 169802 : BigInt nD( nDenominator / nGGT2 );
262 169802 : nD *= BigInt( rVal.nDenominator / nGGT1 );
263 :
264 169802 : if ( nN.bIsBig || nD.bIsBig )
265 : {
266 0 : nNumerator = 0;
267 0 : nDenominator = -1;
268 : }
269 : else
270 : {
271 169802 : nNumerator = (long)nN,
272 169802 : nDenominator = (long)nD;
273 : }
274 :
275 169802 : 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 978 : Fraction& Fraction::operator /= ( const Fraction& rVal )
285 : {
286 978 : if ( !rVal.IsValid() )
287 : {
288 0 : nNumerator = 0;
289 0 : nDenominator = -1;
290 : }
291 978 : if ( !IsValid() )
292 0 : return *this;
293 :
294 978 : long nGGT1 = GetGGT( nNumerator, rVal.nNumerator );
295 978 : long nGGT2 = GetGGT( rVal.nDenominator, nDenominator );
296 978 : BigInt nN( nNumerator / nGGT1 );
297 978 : nN *= BigInt( rVal.nDenominator / nGGT2 );
298 978 : BigInt nD( nDenominator / nGGT2 );
299 978 : nD *= BigInt( rVal.nNumerator / nGGT1 );
300 :
301 978 : if ( nN.bIsBig || nD.bIsBig )
302 : {
303 0 : nNumerator = 0;
304 0 : nDenominator = -1;
305 : }
306 : else
307 : {
308 978 : nNumerator = (long)nN,
309 978 : nDenominator = (long)nD;
310 978 : if ( nDenominator < 0 )
311 : {
312 0 : nDenominator = -nDenominator;
313 0 : nNumerator = -nNumerator;
314 : }
315 : }
316 :
317 978 : 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 0 : 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 0 : const sal_uInt32 nDeBruijn = 0x7DCD629;
337 :
338 0 : if ( nNum == 0 )
339 0 : return 0;
340 :
341 : // Get it to form like 0000001111111111b
342 0 : nNum |= ( nNum >> 1 );
343 0 : nNum |= ( nNum >> 2 );
344 0 : nNum |= ( nNum >> 4 );
345 0 : nNum |= ( nNum >> 8 );
346 0 : nNum |= ( nNum >> 16 );
347 :
348 : sal_uInt32 nNumber;
349 0 : int nBonus = 0;
350 :
351 : #if SAL_TYPES_SIZEOFLONG == 4
352 0 : 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 0 : nNumber = nDeBruijn + ( nDeBruijn * nNumber );
378 :
379 : // 5-bit window indexes the result
380 0 : 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 0 : void Fraction::ReduceInaccurate( unsigned nSignificantBits )
402 : {
403 0 : if ( !nNumerator || !nDenominator )
404 0 : return;
405 :
406 : // Count with unsigned longs only
407 0 : const bool bNeg = ( nNumerator < 0 );
408 0 : unsigned long nMul = (unsigned long)( bNeg? -nNumerator: nNumerator );
409 0 : 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 0 : const int nMulBitsToLose = Max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 );
415 0 : const int nDivBitsToLose = Max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 );
416 :
417 0 : const int nToLose = Min( nMulBitsToLose, nDivBitsToLose );
418 :
419 : // Remove the bits
420 0 : nMul >>= nToLose;
421 0 : nDiv >>= nToLose;
422 :
423 0 : if ( !nMul || !nDiv )
424 : {
425 : // Return without reduction
426 : OSL_FAIL( "Oops, we reduced too much..." );
427 0 : return;
428 : }
429 :
430 : // Reduce
431 0 : long n1 = GetGGT( nMul, nDiv );
432 0 : if ( n1 != 1 )
433 : {
434 0 : nMul /= n1;
435 0 : nDiv /= n1;
436 : }
437 :
438 0 : nNumerator = bNeg? -long( nMul ): long( nMul );
439 0 : nDenominator = nDiv;
440 : }
441 :
442 19459 : bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )
443 : {
444 19459 : if ( !rVal1.IsValid() || !rVal2.IsValid() )
445 0 : return false;
446 :
447 : return rVal1.nNumerator == rVal2.nNumerator
448 19459 : && 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 0 : bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )
455 : {
456 0 : if ( !rVal1.IsValid() || !rVal2.IsValid() )
457 0 : return false;
458 :
459 0 : BigInt nN( rVal1.nNumerator );
460 0 : nN *= BigInt( rVal2.nDenominator );
461 0 : BigInt nD( rVal1.nDenominator );
462 0 : nD *= BigInt( rVal2.nNumerator );
463 :
464 0 : 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 0 : bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )
471 : {
472 0 : if ( !rVal1.IsValid() || !rVal2.IsValid() )
473 0 : return false;
474 :
475 0 : BigInt nN( rVal1.nNumerator );
476 0 : nN *= BigInt( rVal2.nDenominator );
477 0 : BigInt nD( rVal1.nDenominator);
478 0 : nD *= BigInt( rVal2.nNumerator );
479 :
480 0 : return nN > nD;
481 : }
482 :
483 4578 : SvStream& operator >> ( SvStream& rIStream, Fraction& rFract )
484 : {
485 : //fdo#39428 SvStream no longer supports operator>>(long&)
486 4578 : sal_Int32 nTmp(0);
487 4578 : rIStream >> nTmp;
488 4578 : rFract.nNumerator = nTmp;
489 4578 : rIStream >> nTmp;
490 4578 : rFract.nDenominator = nTmp;
491 4578 : return rIStream;
492 : }
493 :
494 4908 : SvStream& operator << ( SvStream& rOStream, const Fraction& rFract )
495 : {
496 : //fdo#39428 SvStream no longer supports operator<<(long)
497 4908 : rOStream << sal::static_int_cast<sal_Int32>(rFract.nNumerator);
498 4908 : rOStream << sal::static_int_cast<sal_Int32>(rFract.nDenominator);
499 4908 : return rOStream;
500 : }
501 :
502 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
