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