fix baseline build (old cairo) - 'cairo_rectangle_int_t' does not name a type
[LibreOffice.git] / tools / source / generic / fract.cxx
blob72ce43d954f8e51552a02da059c40e1d70d19ab5
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
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 .
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>
28 #include <limits.h>
29 #include <algorithm>
30 #include <cmath>
32 #include <boost/rational.hpp>
33 #include <boost/noncopyable.hpp>
35 template<typename T>
36 static boost::rational<T> rational_FromDouble(double dVal);
38 template<typename T>
39 static void rational_ReduceInaccurate(boost::rational<T>& rRational, unsigned nSignificantBits);
41 struct Fraction::Impl : boost::noncopyable
43 bool valid;
44 boost::rational<sal_Int64> value;
47 Fraction::Fraction() : mpImpl(new Impl)
49 mpImpl->valid = true;
52 Fraction::Fraction( const Fraction& rFrac ) : mpImpl(new Impl)
54 mpImpl->valid = rFrac.mpImpl->valid;
55 if (mpImpl->valid)
56 mpImpl->value.assign( rFrac.mpImpl->value.numerator(), rFrac.mpImpl->value.denominator() );
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 Fraction::Fraction( long nNum, long nDen ) : mpImpl(new Impl)
65 if ( nDen == 0 )
67 mpImpl->valid = false;
68 SAL_WARN( "tools.fraction", "'Fraction(" << nNum << ",0)' invalid fraction created" );
69 return;
71 mpImpl->value.assign( nNum, nDen);
72 mpImpl->valid = true;
75 Fraction::Fraction( double dVal ) : mpImpl(new Impl)
77 try
79 mpImpl->value = rational_FromDouble<sal_Int64>( dVal );
80 if ( HasOverflowValue() )
81 throw boost::bad_rational();
82 mpImpl->valid = true;
84 catch (const boost::bad_rational&)
86 mpImpl->valid = false;
87 SAL_WARN( "tools.fraction", "'Fraction(" << dVal << ")' invalid fraction created" );
91 Fraction::~Fraction()
93 delete mpImpl;
96 bool Fraction::HasOverflowValue()
98 //coverity[result_independent_of_operands]
99 return mpImpl->value.numerator() < std::numeric_limits<long>::min() ||
100 mpImpl->value.numerator() > std::numeric_limits<long>::max() ||
101 mpImpl->value.denominator() < std::numeric_limits<long>::min() ||
102 mpImpl->value.denominator() > std::numeric_limits<long>::max();
105 Fraction::operator double() const
107 if (!mpImpl->valid)
109 SAL_WARN( "tools.fraction", "'double()' on invalid fraction" );
110 return 0.0;
113 return boost::rational_cast<double>(mpImpl->value);
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 Fraction& Fraction::operator += ( const Fraction& rVal )
122 if ( !rVal.mpImpl->valid )
123 mpImpl->valid = false;
125 if ( !mpImpl->valid )
127 SAL_WARN( "tools.fraction", "'operator +=' with invalid fraction" );
128 return *this;
131 mpImpl->value += rVal.mpImpl->value;
133 if ( HasOverflowValue() )
135 mpImpl->valid = false;
136 SAL_WARN( "tools.fraction", "'operator +=' detected overflow" );
139 return *this;
142 Fraction& Fraction::operator -= ( const Fraction& rVal )
144 if ( !rVal.mpImpl->valid )
145 mpImpl->valid = false;
147 if ( !mpImpl->valid )
149 SAL_WARN( "tools.fraction", "'operator -=' with invalid fraction" );
150 return *this;
153 mpImpl->value -= rVal.mpImpl->value;
155 if ( HasOverflowValue() )
157 mpImpl->valid = false;
158 SAL_WARN( "tools.fraction", "'operator -=' detected overflow" );
161 return *this;
164 Fraction& Fraction::operator *= ( const Fraction& rVal )
166 if ( !rVal.mpImpl->valid )
167 mpImpl->valid = false;
169 if ( !mpImpl->valid )
171 SAL_WARN( "tools.fraction", "'operator *=' with invalid fraction" );
172 return *this;
175 mpImpl->value *= rVal.mpImpl->value;
177 if ( HasOverflowValue() )
179 mpImpl->valid = false;
180 SAL_WARN( "tools.fraction", "'operator *=' detected overflow" );
183 return *this;
186 Fraction& Fraction::operator /= ( const Fraction& rVal )
188 if ( !rVal.mpImpl->valid )
189 mpImpl->valid = false;
191 if ( !mpImpl->valid )
193 SAL_WARN( "tools.fraction", "'operator /=' with invalid fraction" );
194 return *this;
197 mpImpl->value /= rVal.mpImpl->value;
199 if ( HasOverflowValue() )
201 mpImpl->valid = false;
202 SAL_WARN( "tools.fraction", "'operator /=' detected overflow" );
205 return *this;
208 /** Inaccurate cancellation for a fraction.
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.
214 @param nSignificantBits denotes, how many significant binary
215 digits to maintain, in both nominator and denominator.
217 @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
218 largest error occurs with the following pair of values:
220 binary 1000000011111111111111111111111b/1000000000000000000000000000000b
221 = 1082130431/1073741824
222 = approx. 1.007812499
224 A ReduceInaccurate(8) yields 1/1.
226 void Fraction::ReduceInaccurate( unsigned nSignificantBits )
228 if ( !mpImpl->valid )
230 SAL_WARN( "tools.fraction", "'ReduceInaccurate' on invalid fraction" );
231 return;
234 if ( !mpImpl->value.numerator() )
235 return;
237 rational_ReduceInaccurate(mpImpl->value, nSignificantBits);
240 long Fraction::GetNumerator() const
242 if ( !mpImpl->valid )
244 SAL_WARN( "tools.fraction", "'GetNumerator()' on invalid fraction" );
245 return 0;
247 return mpImpl->value.numerator();
250 long Fraction::GetDenominator() const
252 if ( !mpImpl->valid )
254 SAL_WARN( "tools.fraction", "'GetDenominator()' on invalid fraction" );
255 return -1;
257 return mpImpl->value.denominator();
260 Fraction& Fraction::operator=( const Fraction& rFrac )
262 if (this == &rFrac)
263 return *this;
265 Fraction tmp(rFrac);
266 std::swap(mpImpl, tmp.mpImpl);
267 return *this;
270 bool Fraction::IsValid() const
272 return mpImpl->valid;
275 Fraction::operator long() const
277 if ( !mpImpl->valid )
279 SAL_WARN( "tools.fraction", "'operator long()' on invalid fraction" );
280 return 0;
282 return boost::rational_cast<long>(mpImpl->value);
285 Fraction operator+( const Fraction& rVal1, const Fraction& rVal2 )
287 Fraction aErg( rVal1 );
288 aErg += rVal2;
289 return aErg;
292 Fraction operator-( const Fraction& rVal1, const Fraction& rVal2 )
294 Fraction aErg( rVal1 );
295 aErg -= rVal2;
296 return aErg;
299 Fraction operator*( const Fraction& rVal1, const Fraction& rVal2 )
301 Fraction aErg( rVal1 );
302 aErg *= rVal2;
303 return aErg;
306 Fraction operator/( const Fraction& rVal1, const Fraction& rVal2 )
308 Fraction aErg( rVal1 );
309 aErg /= rVal2;
310 return aErg;
313 bool operator !=( const Fraction& rVal1, const Fraction& rVal2 )
315 return !(rVal1 == rVal2);
318 bool operator <=( const Fraction& rVal1, const Fraction& rVal2 )
320 return !(rVal1 > rVal2);
323 bool operator >=( const Fraction& rVal1, const Fraction& rVal2 )
325 return !(rVal1 < rVal2);
328 bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )
330 if ( !rVal1.mpImpl->valid || !rVal2.mpImpl->valid )
332 SAL_WARN( "tools.fraction", "'operator ==' with an invalid fraction" );
333 return false;
336 return rVal1.mpImpl->value == rVal2.mpImpl->value;
339 bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )
341 if ( !rVal1.mpImpl->valid || !rVal2.mpImpl->valid )
343 SAL_WARN( "tools.fraction", "'operator <' with an invalid fraction" );
344 return false;
347 return rVal1.mpImpl->value < rVal2.mpImpl->value;
350 bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )
352 if ( !rVal1.mpImpl->valid || !rVal2.mpImpl->valid )
354 SAL_WARN( "tools.fraction", "'operator >' with an invalid fraction" );
355 return false;
358 return rVal1.mpImpl->value > rVal2.mpImpl->value;
361 SvStream& ReadFraction( SvStream& rIStream, Fraction& rFract )
363 sal_Int32 num(0), den(0);
364 rIStream.ReadInt32( num );
365 rIStream.ReadInt32( den );
366 if ( den <= 0 )
368 SAL_WARN( "tools.fraction", "'ReadFraction()' read an invalid fraction" );
369 rFract.mpImpl->valid = false;
371 else
373 rFract.mpImpl->value.assign( num, den );
374 rFract.mpImpl->valid = true;
376 return rIStream;
379 SvStream& WriteFraction( SvStream& rOStream, const Fraction& rFract )
381 if ( !rFract.mpImpl->valid )
383 SAL_WARN( "tools.fraction", "'WriteFraction()' write an invalid fraction" );
384 rOStream.WriteInt32( 0 );
385 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 rOStream.WriteInt32( rFract.mpImpl->value.numerator() );
394 rOStream.WriteInt32( rFract.mpImpl->value.denominator() );
396 return rOStream;
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).
403 // NOTE: here we use 'long' due that only values in long range are valid.
404 template<typename T>
405 static boost::rational<T> rational_FromDouble(double dVal)
407 if ( dVal > std::numeric_limits<long>::max() ||
408 dVal < std::numeric_limits<long>::min() )
409 throw boost::bad_rational();
411 const long nMAX = std::numeric_limits<long>::max() / 10;
412 long nDen = 1;
413 while ( std::abs( dVal ) < nMAX && nDen < nMAX ) {
414 dVal *= 10;
415 nDen *= 10;
417 return boost::rational<T>( long(dVal), nDen );
420 // Similar to clz_table that can be googled
421 const char nbits_table[32] =
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
429 static int impl_NumberOfBits( unsigned long nNum )
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 const sal_uInt32 nDeBruijn = 0x7DCD629;
438 if ( nNum == 0 )
439 return 0;
441 // Get it to form like 0000001111111111b
442 nNum |= ( nNum >> 1 );
443 nNum |= ( nNum >> 2 );
444 nNum |= ( nNum >> 4 );
445 nNum |= ( nNum >> 8 );
446 nNum |= ( nNum >> 16 );
448 sal_uInt32 nNumber;
449 int nBonus = 0;
451 #if SAL_TYPES_SIZEOFLONG == 4
452 nNumber = nNum;
453 #elif SAL_TYPES_SIZEOFLONG == 8
454 nNum |= ( nNum >> 32 );
456 if ( nNum & 0x80000000 )
458 nNumber = sal_uInt32( nNum >> 32 );
459 nBonus = 32;
461 if ( nNumber == 0 )
462 return 32;
464 else
465 nNumber = sal_uInt32( nNum & 0xFFFFFFFF );
466 #else
467 #error "Unknown size of long!"
468 #endif
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 nNumber = nDeBruijn + ( nDeBruijn * nNumber );
479 // 5-bit window indexes the result
480 return ( nbits_table[nNumber >> 27] ) + nBonus;
483 /** Inaccurate cancellation for a fraction.
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.
489 @param nSignificantBits denotes, how many significant binary
490 digits to maintain, in both nominator and denominator.
492 @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
493 largest error occurs with the following pair of values:
495 binary 1000000011111111111111111111111b/1000000000000000000000000000000b
496 = 1082130431/1073741824
497 = approx. 1.007812499
499 A ReduceInaccurate(8) yields 1/1.
501 template<typename T>
502 static void rational_ReduceInaccurate(boost::rational<T>& rRational, unsigned nSignificantBits)
504 if ( !rRational )
505 return;
507 // http://www.boost.org/doc/libs/release/libs/rational/rational.html#Internal%20representation
508 const bool bNeg = ( rRational.numerator() < 0 );
509 T nMul = bNeg? -rRational.numerator(): rRational.numerator();
510 T nDiv = rRational.denominator();
512 DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!");
514 // How much bits can we lose?
515 const int nMulBitsToLose = std::max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 );
516 const int nDivBitsToLose = std::max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 );
518 const int nToLose = std::min( nMulBitsToLose, nDivBitsToLose );
520 // Remove the bits
521 nMul >>= nToLose;
522 nDiv >>= nToLose;
524 if ( !nMul || !nDiv ) {
525 // Return without reduction
526 OSL_FAIL( "Oops, we reduced too much..." );
527 return;
530 rRational.assign( bNeg? -T( nMul ): T( nMul ), nDiv );
533 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */