1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
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>
32 #include <boost/rational.hpp>
33 #include <boost/noncopyable.hpp>
36 static boost::rational
<T
> rational_FromDouble(double dVal
);
39 static void rational_ReduceInaccurate(boost::rational
<T
>& rRational
, unsigned nSignificantBits
);
41 struct Fraction::Impl
: boost::noncopyable
44 boost::rational
<sal_Int64
> value
;
47 Fraction::Fraction() : mpImpl(new Impl
)
52 Fraction::Fraction( const Fraction
& rFrac
) : mpImpl(new Impl
)
54 mpImpl
->valid
= rFrac
.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
)
67 mpImpl
->valid
= false;
68 SAL_WARN( "tools.fraction", "'Fraction(" << nNum
<< ",0)' invalid fraction created" );
71 mpImpl
->value
.assign( nNum
, nDen
);
75 Fraction::Fraction( double dVal
) : mpImpl(new Impl
)
79 mpImpl
->value
= rational_FromDouble
<sal_Int64
>( dVal
);
80 if ( HasOverflowValue() )
81 throw boost::bad_rational();
84 catch (const boost::bad_rational
&)
86 mpImpl
->valid
= false;
87 SAL_WARN( "tools.fraction", "'Fraction(" << dVal
<< ")' invalid fraction created" );
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
109 SAL_WARN( "tools.fraction", "'double()' on invalid fraction" );
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" );
131 mpImpl
->value
+= rVal
.mpImpl
->value
;
133 if ( HasOverflowValue() )
135 mpImpl
->valid
= false;
136 SAL_WARN( "tools.fraction", "'operator +=' detected overflow" );
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" );
153 mpImpl
->value
-= rVal
.mpImpl
->value
;
155 if ( HasOverflowValue() )
157 mpImpl
->valid
= false;
158 SAL_WARN( "tools.fraction", "'operator -=' detected overflow" );
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" );
175 mpImpl
->value
*= rVal
.mpImpl
->value
;
177 if ( HasOverflowValue() )
179 mpImpl
->valid
= false;
180 SAL_WARN( "tools.fraction", "'operator *=' detected overflow" );
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" );
197 mpImpl
->value
/= rVal
.mpImpl
->value
;
199 if ( HasOverflowValue() )
201 mpImpl
->valid
= false;
202 SAL_WARN( "tools.fraction", "'operator /=' detected overflow" );
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" );
234 if ( !mpImpl
->value
.numerator() )
237 rational_ReduceInaccurate(mpImpl
->value
, nSignificantBits
);
240 long Fraction::GetNumerator() const
242 if ( !mpImpl
->valid
)
244 SAL_WARN( "tools.fraction", "'GetNumerator()' on invalid fraction" );
247 return mpImpl
->value
.numerator();
250 long Fraction::GetDenominator() const
252 if ( !mpImpl
->valid
)
254 SAL_WARN( "tools.fraction", "'GetDenominator()' on invalid fraction" );
257 return mpImpl
->value
.denominator();
260 Fraction
& Fraction::operator=( const Fraction
& rFrac
)
266 std::swap(mpImpl
, tmp
.mpImpl
);
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" );
282 return boost::rational_cast
<long>(mpImpl
->value
);
285 Fraction
operator+( const Fraction
& rVal1
, const Fraction
& rVal2
)
287 Fraction
aErg( rVal1
);
292 Fraction
operator-( const Fraction
& rVal1
, const Fraction
& rVal2
)
294 Fraction
aErg( rVal1
);
299 Fraction
operator*( const Fraction
& rVal1
, const Fraction
& rVal2
)
301 Fraction
aErg( rVal1
);
306 Fraction
operator/( const Fraction
& rVal1
, const Fraction
& rVal2
)
308 Fraction
aErg( rVal1
);
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" );
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" );
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" );
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
);
368 SAL_WARN( "tools.fraction", "'ReadFraction()' read an invalid fraction" );
369 rFract
.mpImpl
->valid
= false;
373 rFract
.mpImpl
->value
.assign( num
, den
);
374 rFract
.mpImpl
->valid
= true;
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 );
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!");
393 rOStream
.WriteInt32( rFract
.mpImpl
->value
.numerator() );
394 rOStream
.WriteInt32( rFract
.mpImpl
->value
.denominator() );
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.
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;
413 while ( std::abs( dVal
) < nMAX
&& nDen
< nMAX
) {
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;
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 );
451 #if SAL_TYPES_SIZEOFLONG == 4
453 #elif SAL_TYPES_SIZEOFLONG == 8
454 nNum
|= ( nNum
>> 32 );
456 if ( nNum
& 0x80000000 )
458 nNumber
= sal_uInt32( nNum
>> 32 );
465 nNumber
= sal_uInt32( nNum
& 0xFFFFFFFF );
467 #error "Unknown size of long!"
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.
502 static void rational_ReduceInaccurate(boost::rational
<T
>& rRational
, unsigned nSignificantBits
)
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
);
524 if ( !nMul
|| !nDiv
) {
525 // Return without reduction
526 OSL_FAIL( "Oops, we reduced too much..." );
530 rRational
.assign( bNeg
? -T( nMul
): T( nMul
), nDiv
);
533 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */