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 <tools/fract.hxx>
21 : #include <tools/debug.hxx>
22 : #include <tools/lineend.hxx>
23 : #include <tools/stream.hxx>
24 : #include <rtl/ustring.hxx>
25 : #include <sal/log.hxx>
26 : #include <osl/diagnose.h>
27 :
28 : #include <limits.h>
29 : #include <algorithm>
30 : #include <cmath>
31 :
32 : #include <boost/rational.hpp>
33 : #include <boost/noncopyable.hpp>
34 :
35 : template<typename T>
36 : static boost::rational<T> rational_FromDouble(double dVal);
37 :
38 : template<typename T>
39 : static void rational_ReduceInaccurate(boost::rational<T>& rRational, unsigned nSignificantBits);
40 :
41 20666670 : struct Fraction::Impl : boost::noncopyable
42 : {
43 : bool valid;
44 : boost::rational<sal_Int64> value;
45 : };
46 :
47 385990 : Fraction::Fraction() : mpImpl(new Impl)
48 : {
49 385990 : mpImpl->valid = true;
50 385990 : }
51 :
52 12228664 : Fraction::Fraction( const Fraction& rFrac ) : mpImpl(new Impl)
53 : {
54 12228664 : mpImpl->valid = rFrac.mpImpl->valid;
55 12228664 : if (mpImpl->valid)
56 12228500 : mpImpl->value.assign( rFrac.mpImpl->value.numerator(), rFrac.mpImpl->value.denominator() );
57 12228664 : }
58 :
59 : // Initialized by setting nNum as nominator and nDen as denominator
60 : // Negative values in the denominator are invalid and cause the
61 : // inversion of both nominator and denominator signs
62 : // in order to return the correct value.
63 8016583 : Fraction::Fraction( long nNum, long nDen ) : mpImpl(new Impl)
64 : {
65 8016583 : if ( nDen == 0 )
66 : {
67 34 : mpImpl->valid = false;
68 : SAL_WARN( "tools.fraction", "'Fraction(" << nNum << ",0)' invalid fraction created" );
69 8016617 : return;
70 : }
71 8016549 : mpImpl->value.assign( nNum, nDen);
72 8016549 : mpImpl->valid = true;
73 : }
74 :
75 35433 : Fraction::Fraction( double dVal ) : mpImpl(new Impl)
76 : {
77 : try
78 : {
79 35433 : mpImpl->value = rational_FromDouble<sal_Int64>( dVal );
80 35433 : if ( HasOverflowValue() )
81 0 : throw boost::bad_rational();
82 35433 : mpImpl->valid = true;
83 : }
84 0 : catch (const boost::bad_rational&)
85 : {
86 0 : mpImpl->valid = false;
87 : SAL_WARN( "tools.fraction", "'Fraction(" << dVal << ")' invalid fraction created" );
88 : }
89 35433 : }
90 :
91 20662101 : Fraction::~Fraction()
92 : {
93 20662101 : delete mpImpl;
94 20662101 : }
95 :
96 3675452 : bool Fraction::HasOverflowValue()
97 : {
98 : //coverity[result_independent_of_operands]
99 7350904 : return mpImpl->value.numerator() < std::numeric_limits<long>::min() ||
100 7350904 : mpImpl->value.numerator() > std::numeric_limits<long>::max() ||
101 11026356 : mpImpl->value.denominator() < std::numeric_limits<long>::min() ||
102 7350904 : mpImpl->value.denominator() > std::numeric_limits<long>::max();
103 : }
104 :
105 1001782 : Fraction::operator double() const
106 : {
107 1001782 : if (!mpImpl->valid)
108 : {
109 : SAL_WARN( "tools.fraction", "'double()' on invalid fraction" );
110 0 : return 0.0;
111 : }
112 :
113 1001782 : return boost::rational_cast<double>(mpImpl->value);
114 : }
115 :
116 : // This methods first validates both values.
117 : // If one of the arguments is invalid, the whole operation is invalid.
118 : // After computation detect if result overflows a long value
119 : // which cause the operation to be marked as invalid
120 10 : Fraction& Fraction::operator += ( const Fraction& rVal )
121 : {
122 10 : if ( !rVal.mpImpl->valid )
123 0 : mpImpl->valid = false;
124 :
125 10 : if ( !mpImpl->valid )
126 : {
127 : SAL_WARN( "tools.fraction", "'operator +=' with invalid fraction" );
128 0 : return *this;
129 : }
130 :
131 10 : mpImpl->value += rVal.mpImpl->value;
132 :
133 10 : if ( HasOverflowValue() )
134 : {
135 0 : mpImpl->valid = false;
136 : SAL_WARN( "tools.fraction", "'operator +=' detected overflow" );
137 : }
138 :
139 10 : return *this;
140 : }
141 :
142 10 : Fraction& Fraction::operator -= ( const Fraction& rVal )
143 : {
144 10 : if ( !rVal.mpImpl->valid )
145 0 : mpImpl->valid = false;
146 :
147 10 : if ( !mpImpl->valid )
148 : {
149 : SAL_WARN( "tools.fraction", "'operator -=' with invalid fraction" );
150 0 : return *this;
151 : }
152 :
153 10 : mpImpl->value -= rVal.mpImpl->value;
154 :
155 10 : if ( HasOverflowValue() )
156 : {
157 0 : mpImpl->valid = false;
158 : SAL_WARN( "tools.fraction", "'operator -=' detected overflow" );
159 : }
160 :
161 10 : return *this;
162 : }
163 :
164 3637353 : Fraction& Fraction::operator *= ( const Fraction& rVal )
165 : {
166 3637353 : if ( !rVal.mpImpl->valid )
167 0 : mpImpl->valid = false;
168 :
169 3637353 : if ( !mpImpl->valid )
170 : {
171 : SAL_WARN( "tools.fraction", "'operator *=' with invalid fraction" );
172 0 : return *this;
173 : }
174 :
175 3637353 : mpImpl->value *= rVal.mpImpl->value;
176 :
177 3637353 : if ( HasOverflowValue() )
178 : {
179 0 : mpImpl->valid = false;
180 : SAL_WARN( "tools.fraction", "'operator *=' detected overflow" );
181 : }
182 :
183 3637353 : return *this;
184 : }
185 :
186 2646 : Fraction& Fraction::operator /= ( const Fraction& rVal )
187 : {
188 2646 : if ( !rVal.mpImpl->valid )
189 0 : mpImpl->valid = false;
190 :
191 2646 : if ( !mpImpl->valid )
192 : {
193 : SAL_WARN( "tools.fraction", "'operator /=' with invalid fraction" );
194 0 : return *this;
195 : }
196 :
197 2646 : mpImpl->value /= rVal.mpImpl->value;
198 :
199 2646 : if ( HasOverflowValue() )
200 : {
201 0 : mpImpl->valid = false;
202 : SAL_WARN( "tools.fraction", "'operator /=' detected overflow" );
203 : }
204 :
205 2646 : return *this;
206 : }
207 :
208 : /** Inaccurate cancellation for a fraction.
209 :
210 : Clip both nominator and denominator to said number of bits. If
211 : either of those already have equal or less number of bits used,
212 : this method does nothing.
213 :
214 : @param nSignificantBits denotes, how many significant binary
215 : digits to maintain, in both nominator and denominator.
216 :
217 : @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
218 : largest error occurs with the following pair of values:
219 :
220 : binary 1000000011111111111111111111111b/1000000000000000000000000000000b
221 : = 1082130431/1073741824
222 : = approx. 1.007812499
223 :
224 : A ReduceInaccurate(8) yields 1/1.
225 : */
226 3807996 : void Fraction::ReduceInaccurate( unsigned nSignificantBits )
227 : {
228 3807996 : if ( !mpImpl->valid )
229 : {
230 : SAL_WARN( "tools.fraction", "'ReduceInaccurate' on invalid fraction" );
231 0 : return;
232 : }
233 :
234 3807996 : if ( !mpImpl->value.numerator() )
235 0 : return;
236 :
237 3807996 : rational_ReduceInaccurate(mpImpl->value, nSignificantBits);
238 : }
239 :
240 12480650 : long Fraction::GetNumerator() const
241 : {
242 12480650 : if ( !mpImpl->valid )
243 : {
244 : SAL_WARN( "tools.fraction", "'GetNumerator()' on invalid fraction" );
245 136 : return 0;
246 : }
247 12480514 : return mpImpl->value.numerator();
248 : }
249 :
250 12477973 : long Fraction::GetDenominator() const
251 : {
252 12477973 : if ( !mpImpl->valid )
253 : {
254 : SAL_WARN( "tools.fraction", "'GetDenominator()' on invalid fraction" );
255 68 : return -1;
256 : }
257 12477905 : return mpImpl->value.denominator();
258 : }
259 :
260 587161 : Fraction& Fraction::operator=( const Fraction& rFrac )
261 : {
262 587161 : if (this == &rFrac)
263 0 : return *this;
264 :
265 587161 : Fraction tmp(rFrac);
266 587161 : std::swap(mpImpl, tmp.mpImpl);
267 587161 : return *this;
268 : }
269 :
270 4118652 : bool Fraction::IsValid() const
271 : {
272 4118652 : return mpImpl->valid;
273 : }
274 :
275 24046 : Fraction::operator long() const
276 : {
277 24046 : if ( !mpImpl->valid )
278 : {
279 : SAL_WARN( "tools.fraction", "'operator long()' on invalid fraction" );
280 0 : return 0;
281 : }
282 24046 : return boost::rational_cast<long>(mpImpl->value);
283 : }
284 :
285 10 : Fraction operator+( const Fraction& rVal1, const Fraction& rVal2 )
286 : {
287 10 : Fraction aErg( rVal1 );
288 10 : aErg += rVal2;
289 10 : return aErg;
290 : }
291 :
292 10 : Fraction operator-( const Fraction& rVal1, const Fraction& rVal2 )
293 : {
294 10 : Fraction aErg( rVal1 );
295 10 : aErg -= rVal2;
296 10 : return aErg;
297 : }
298 :
299 3613704 : Fraction operator*( const Fraction& rVal1, const Fraction& rVal2 )
300 : {
301 3613704 : Fraction aErg( rVal1 );
302 3613704 : aErg *= rVal2;
303 3613704 : return aErg;
304 : }
305 :
306 2624 : Fraction operator/( const Fraction& rVal1, const Fraction& rVal2 )
307 : {
308 2624 : Fraction aErg( rVal1 );
309 2624 : aErg /= rVal2;
310 2624 : return aErg;
311 : }
312 :
313 70659 : bool operator !=( const Fraction& rVal1, const Fraction& rVal2 )
314 : {
315 70659 : return !(rVal1 == rVal2);
316 : }
317 :
318 0 : bool operator <=( const Fraction& rVal1, const Fraction& rVal2 )
319 : {
320 0 : return !(rVal1 > rVal2);
321 : }
322 :
323 0 : bool operator >=( const Fraction& rVal1, const Fraction& rVal2 )
324 : {
325 0 : return !(rVal1 < rVal2);
326 : }
327 :
328 316699 : bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )
329 : {
330 316699 : if ( !rVal1.mpImpl->valid || !rVal2.mpImpl->valid )
331 : {
332 : SAL_WARN( "tools.fraction", "'operator ==' with an invalid fraction" );
333 0 : return false;
334 : }
335 :
336 316699 : return rVal1.mpImpl->value == rVal2.mpImpl->value;
337 : }
338 :
339 0 : bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )
340 : {
341 0 : if ( !rVal1.mpImpl->valid || !rVal2.mpImpl->valid )
342 : {
343 : SAL_WARN( "tools.fraction", "'operator <' with an invalid fraction" );
344 0 : return false;
345 : }
346 :
347 0 : return rVal1.mpImpl->value < rVal2.mpImpl->value;
348 : }
349 :
350 0 : bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )
351 : {
352 0 : if ( !rVal1.mpImpl->valid || !rVal2.mpImpl->valid )
353 : {
354 : SAL_WARN( "tools.fraction", "'operator >' with an invalid fraction" );
355 0 : return false;
356 : }
357 :
358 0 : return rVal1.mpImpl->value > rVal2.mpImpl->value;
359 : }
360 :
361 10994 : SvStream& ReadFraction( SvStream& rIStream, Fraction& rFract )
362 : {
363 10994 : sal_Int32 num(0), den(0);
364 10994 : rIStream.ReadInt32( num );
365 10994 : rIStream.ReadInt32( den );
366 10994 : if ( den <= 0 )
367 : {
368 : SAL_WARN( "tools.fraction", "'ReadFraction()' read an invalid fraction" );
369 0 : rFract.mpImpl->valid = false;
370 : }
371 : else
372 : {
373 10994 : rFract.mpImpl->value.assign( num, den );
374 10994 : rFract.mpImpl->valid = true;
375 : }
376 10994 : return rIStream;
377 : }
378 :
379 12222 : SvStream& WriteFraction( SvStream& rOStream, const Fraction& rFract )
380 : {
381 12222 : if ( !rFract.mpImpl->valid )
382 : {
383 : SAL_WARN( "tools.fraction", "'WriteFraction()' write an invalid fraction" );
384 0 : rOStream.WriteInt32( 0 );
385 0 : rOStream.WriteInt32( -1 );
386 : } else {
387 : #if OSL_DEBUG_LEVEL > 0
388 : // can only write 32 bits - check that no data is lost!
389 : boost::rational<sal_Int64> copy(rFract.mpImpl->value);
390 : rational_ReduceInaccurate(copy, 32);
391 : assert(copy == rFract.mpImpl->value && "data loss in WriteFraction!");
392 : #endif
393 12222 : rOStream.WriteInt32( rFract.mpImpl->value.numerator() );
394 12222 : rOStream.WriteInt32( rFract.mpImpl->value.denominator() );
395 : }
396 12222 : return rOStream;
397 : }
398 :
399 : // If dVal > LONG_MAX or dVal < LONG_MIN, the rational throws a boost::bad_rational.
400 : // Otherwise, dVal and denominator are multiplied by 10, until one of them
401 : // is larger than (LONG_MAX / 10).
402 : //
403 : // NOTE: here we use 'long' due that only values in long range are valid.
404 : template<typename T>
405 35433 : static boost::rational<T> rational_FromDouble(double dVal)
406 : {
407 70866 : if ( dVal > std::numeric_limits<long>::max() ||
408 35433 : dVal < std::numeric_limits<long>::min() )
409 0 : throw boost::bad_rational();
410 :
411 35433 : const long nMAX = std::numeric_limits<long>::max() / 10;
412 35433 : long nDen = 1;
413 698475 : while ( std::abs( dVal ) < nMAX && nDen < nMAX ) {
414 627609 : dVal *= 10;
415 627609 : nDen *= 10;
416 : }
417 35433 : return boost::rational<T>( long(dVal), nDen );
418 : }
419 :
420 : // Similar to clz_table that can be googled
421 : const char nbits_table[32] =
422 : {
423 : 32, 1, 23, 2, 29, 24, 14, 3,
424 : 30, 27, 25, 18, 20, 15, 10, 4,
425 : 31, 22, 28, 13, 26, 17, 19, 9,
426 : 21, 12, 16, 8, 11, 7, 6, 5
427 : };
428 :
429 7615992 : static int impl_NumberOfBits( unsigned long nNum )
430 : {
431 : // http://en.wikipedia.org/wiki/De_Bruijn_sequence
432 : // background paper: Using de Bruijn Sequences to Index a 1 in a
433 : // Computer Word (1998) Charles E. Leiserson,
434 : // Harald Prokop, Keith H. Randall
435 : // (e.g. http://citeseer.ist.psu.edu/leiserson98using.html)
436 7615992 : const sal_uInt32 nDeBruijn = 0x7DCD629;
437 :
438 7615992 : if ( nNum == 0 )
439 0 : return 0;
440 :
441 : // Get it to form like 0000001111111111b
442 7615992 : nNum |= ( nNum >> 1 );
443 7615992 : nNum |= ( nNum >> 2 );
444 7615992 : nNum |= ( nNum >> 4 );
445 7615992 : nNum |= ( nNum >> 8 );
446 7615992 : nNum |= ( nNum >> 16 );
447 :
448 : sal_uInt32 nNumber;
449 7615992 : int nBonus = 0;
450 :
451 : #if SAL_TYPES_SIZEOFLONG == 4
452 : nNumber = nNum;
453 : #elif SAL_TYPES_SIZEOFLONG == 8
454 7615992 : nNum |= ( nNum >> 32 );
455 :
456 7615992 : if ( nNum & 0x80000000 )
457 : {
458 67391 : nNumber = sal_uInt32( nNum >> 32 );
459 67391 : nBonus = 32;
460 :
461 67391 : if ( nNumber == 0 )
462 2254 : return 32;
463 : }
464 : else
465 7548601 : nNumber = sal_uInt32( nNum & 0xFFFFFFFF );
466 : #else
467 : #error "Unknown size of long!"
468 : #endif
469 :
470 : // De facto shift left of nDeBruijn using multiplication (nNumber
471 : // is all ones from topmost bit, thus nDeBruijn + (nDeBruijn *
472 : // nNumber) => nDeBruijn * (nNumber+1) clears all those bits to
473 : // zero, sets the next bit to one, and thus effectively shift-left
474 : // nDeBruijn by lg2(nNumber+1). This generates a distinct 5bit
475 : // sequence in the msb for each distinct position of the last
476 : // leading 0 bit - that's the property of a de Bruijn number.
477 7613738 : nNumber = nDeBruijn + ( nDeBruijn * nNumber );
478 :
479 : // 5-bit window indexes the result
480 7613738 : return ( nbits_table[nNumber >> 27] ) + nBonus;
481 : }
482 :
483 : /** Inaccurate cancellation for a fraction.
484 :
485 : Clip both nominator and denominator to said number of bits. If
486 : either of those already have equal or less number of bits used,
487 : this method does nothing.
488 :
489 : @param nSignificantBits denotes, how many significant binary
490 : digits to maintain, in both nominator and denominator.
491 :
492 : @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
493 : largest error occurs with the following pair of values:
494 :
495 : binary 1000000011111111111111111111111b/1000000000000000000000000000000b
496 : = 1082130431/1073741824
497 : = approx. 1.007812499
498 :
499 : A ReduceInaccurate(8) yields 1/1.
500 : */
501 : template<typename T>
502 3807996 : static void rational_ReduceInaccurate(boost::rational<T>& rRational, unsigned nSignificantBits)
503 : {
504 3807996 : if ( !rRational )
505 1 : return;
506 :
507 : // http://www.boost.org/doc/libs/release/libs/rational/rational.html#Internal%20representation
508 3807996 : const bool bNeg = ( rRational.numerator() < 0 );
509 3807996 : T nMul = bNeg? -rRational.numerator(): rRational.numerator();
510 3807996 : T nDiv = rRational.denominator();
511 :
512 : DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!");
513 :
514 : // How much bits can we lose?
515 3807996 : const int nMulBitsToLose = std::max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 );
516 3807996 : const int nDivBitsToLose = std::max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 );
517 :
518 3807996 : const int nToLose = std::min( nMulBitsToLose, nDivBitsToLose );
519 :
520 : // Remove the bits
521 3807996 : nMul >>= nToLose;
522 3807996 : nDiv >>= nToLose;
523 :
524 3807996 : if ( !nMul || !nDiv ) {
525 : // Return without reduction
526 : OSL_FAIL( "Oops, we reduced too much..." );
527 1 : return;
528 : }
529 :
530 3807995 : rRational.assign( bNeg? -T( nMul ): T( nMul ), nDiv );
531 2100 : }
532 :
533 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
