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 <algorithm>
21 : #include <cmath>
22 :
23 : #include <limits.h>
24 : #include <rtl/ustring.hxx>
25 : #include <tools/debug.hxx>
26 : #include <tools/fract.hxx>
27 : #include <tools/lineend.hxx>
28 : #include <tools/stream.hxx>
29 :
30 : template<typename T>
31 : static boost::rational<T> rational_FromDouble(double dVal);
32 :
33 : template<typename T>
34 : static void rational_ReduceInaccurate(boost::rational<T>& rRational, unsigned nSignificantBits);
35 :
36 : // Initialized by setting nNum as nominator and nDen as denominator
37 : // Negative values in the denominator are invalid and cause the
38 : // inversion of both nominator and denominator signs
39 : // in order to return the correct value.
40 14243747 : Fraction::Fraction( long nNum, long nDen )
41 : {
42 14243747 : if ( nDen == 0 ) {
43 84 : valid = false;
44 : SAL_WARN( "tools.fraction", "'Fraction(" << nNum << ",0)' invalid fraction created" );
45 14243831 : return;
46 : }
47 14243663 : value.assign( nNum, nDen);
48 14243663 : valid = true;
49 : }
50 :
51 30384 : Fraction::Fraction( double dVal )
52 : {
53 : try {
54 30384 : value = rational_FromDouble<sal_Int64>( dVal );
55 30384 : if ( HasOverflowValue() )
56 0 : throw boost::bad_rational();
57 30384 : valid = true;
58 0 : } catch(const boost::bad_rational&) {
59 0 : valid = false;
60 : SAL_WARN( "tools.fraction", "'Fraction(" << dVal << ")' invalid fraction created" );
61 : }
62 30384 : }
63 :
64 6715518 : bool Fraction::HasOverflowValue()
65 : {
66 : //coverity[constant_expression_result]
67 13431036 : return value.numerator() < std::numeric_limits<long>::min() ||
68 13431036 : value.numerator() > std::numeric_limits<long>::max() ||
69 20146554 : value.denominator() < std::numeric_limits<long>::min() ||
70 13431036 : value.denominator() > std::numeric_limits<long>::max();
71 : }
72 :
73 370472 : Fraction::operator double() const
74 : {
75 370472 : if ( !valid ) {
76 : SAL_WARN( "tools.fraction", "'double()' on invalid fraction" );
77 0 : return 0.0;
78 : }
79 :
80 370472 : return boost::rational_cast<double>(value);
81 : }
82 :
83 : // This methods first validates both values.
84 : // If one of the arguments is invalid, the whole operation is invalid.
85 : // After computation detect if result overflows a long value
86 : // which cause the operation to be marked as invalid
87 20 : Fraction& Fraction::operator += ( const Fraction& rVal )
88 : {
89 20 : if ( !rVal.valid )
90 0 : valid = false;
91 20 : if ( !valid ) {
92 : SAL_WARN( "tools.fraction", "'operator +=' with invalid fraction" );
93 0 : return *this;
94 : }
95 :
96 20 : value += rVal.value;
97 :
98 20 : if ( HasOverflowValue() ) {
99 0 : valid = false;
100 : SAL_WARN( "tools.fraction", "'operator +=' detected overflow" );
101 : }
102 :
103 20 : return *this;
104 : }
105 :
106 20 : Fraction& Fraction::operator -= ( const Fraction& rVal )
107 : {
108 20 : if ( !rVal.valid )
109 0 : valid = false;
110 20 : if ( !valid ) {
111 : SAL_WARN( "tools.fraction", "'operator -=' with invalid fraction" );
112 0 : return *this;
113 : }
114 :
115 20 : value -= rVal.value;
116 :
117 20 : if ( HasOverflowValue() ) {
118 0 : valid = false;
119 : SAL_WARN( "tools.fraction", "'operator -=' detected overflow" );
120 : }
121 :
122 20 : return *this;
123 : }
124 :
125 6679562 : Fraction& Fraction::operator *= ( const Fraction& rVal )
126 : {
127 6679562 : if ( !rVal.valid )
128 0 : valid = false;
129 6679562 : if ( !valid ) {
130 : SAL_WARN( "tools.fraction", "'operator *=' with invalid fraction" );
131 0 : return *this;
132 : }
133 :
134 6679562 : value *= rVal.value;
135 :
136 6679562 : if ( HasOverflowValue() ) {
137 0 : valid = false;
138 : SAL_WARN( "tools.fraction", "'operator *=' detected overflow" );
139 : }
140 :
141 6679562 : return *this;
142 : }
143 :
144 5532 : Fraction& Fraction::operator /= ( const Fraction& rVal )
145 : {
146 5532 : if ( !rVal.valid )
147 0 : valid = false;
148 5532 : if ( !valid ) {
149 : SAL_WARN( "tools.fraction", "'operator /=' with invalid fraction" );
150 0 : return *this;
151 : }
152 :
153 5532 : value /= rVal.value;
154 :
155 5532 : if ( HasOverflowValue() ) {
156 0 : valid = false;
157 : SAL_WARN( "tools.fraction", "'operator /=' detected overflow" );
158 : }
159 :
160 5532 : return *this;
161 : }
162 :
163 : /** Inaccurate cancellation for a fraction.
164 :
165 : Clip both nominator and denominator to said number of bits. If
166 : either of those already have equal or less number of bits used,
167 : this method does nothing.
168 :
169 : @param nSignificantBits denotes, how many significant binary
170 : digits to maintain, in both nominator and denominator.
171 :
172 : @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
173 : largest error occurs with the following pair of values:
174 :
175 : binary 1000000011111111111111111111111b/1000000000000000000000000000000b
176 : = 1082130431/1073741824
177 : = approx. 1.007812499
178 :
179 : A ReduceInaccurate(8) yields 1/1.
180 : */
181 5520 : void Fraction::ReduceInaccurate( unsigned nSignificantBits )
182 : {
183 5520 : if ( !valid ) {
184 : SAL_WARN( "tools.fraction", "'ReduceInaccurate' on invalid fraction" );
185 0 : return;
186 : }
187 5520 : if ( !value.numerator() )
188 0 : return;
189 :
190 5520 : rational_ReduceInaccurate(value, nSignificantBits);
191 : }
192 :
193 427737 : bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )
194 : {
195 427737 : if ( !rVal1.valid || !rVal2.valid ) {
196 : SAL_WARN( "tools.fraction", "'operator ==' with an invalid fraction" );
197 0 : return false;
198 : }
199 :
200 427737 : return rVal1.value == rVal2.value;
201 : }
202 :
203 1100 : bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )
204 : {
205 1100 : if ( !rVal1.valid || !rVal2.valid ) {
206 : SAL_WARN( "tools.fraction", "'operator <' with an invalid fraction" );
207 0 : return false;
208 : }
209 :
210 1100 : return rVal1.value < rVal2.value;
211 : }
212 :
213 1100 : bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )
214 : {
215 1100 : if ( !rVal1.valid || !rVal2.valid ) {
216 : SAL_WARN( "tools.fraction", "'operator >' with an invalid fraction" );
217 0 : return false;
218 : }
219 :
220 1100 : return rVal1.value > rVal2.value;
221 : }
222 :
223 21000 : SvStream& ReadFraction( SvStream& rIStream, Fraction& rFract )
224 : {
225 21000 : sal_Int32 num(0), den(0);
226 21000 : rIStream.ReadInt32( num );
227 21000 : rIStream.ReadInt32( den );
228 21000 : if ( den <= 0 ) {
229 : SAL_WARN( "tools.fraction", "'ReadFraction()' read an invalid fraction" );
230 0 : rFract.valid = false;
231 : } else {
232 21000 : rFract.value.assign( num, den );
233 21000 : rFract.valid = true;
234 : }
235 21000 : return rIStream;
236 : }
237 :
238 22764 : SvStream& WriteFraction( SvStream& rOStream, const Fraction& rFract )
239 : {
240 22764 : if ( !rFract.valid ) {
241 : SAL_WARN( "tools.fraction", "'WriteFraction()' write an invalid fraction" );
242 0 : rOStream.WriteInt32( 0 );
243 0 : rOStream.WriteInt32( -1 );
244 : } else {
245 22764 : rOStream.WriteInt32( rFract.value.numerator() );
246 22764 : rOStream.WriteInt32( rFract.value.denominator() );
247 : }
248 22764 : return rOStream;
249 : }
250 :
251 : // If dVal > LONG_MAX or dVal < LONG_MIN, the rational throws a boost::bad_rational.
252 : // Otherwise, dVal and denominator are multiplied by 10, until one of them
253 : // is larger than (LONG_MAX / 10).
254 : //
255 : // NOTE: here we use 'long' due that only values in long range are valid.
256 : template<typename T>
257 30384 : static boost::rational<T> rational_FromDouble(double dVal)
258 : {
259 60768 : if ( dVal > std::numeric_limits<long>::max() ||
260 30384 : dVal < std::numeric_limits<long>::min() )
261 0 : throw boost::bad_rational();
262 :
263 30384 : const long nMAX = std::numeric_limits<long>::max() / 10;
264 30384 : long nDen = 1;
265 588036 : while ( std::abs( dVal ) < nMAX && nDen < nMAX ) {
266 527268 : dVal *= 10;
267 527268 : nDen *= 10;
268 : }
269 30384 : return boost::rational<T>( long(dVal), nDen );
270 : }
271 :
272 : // Similar to clz_table that can be googled
273 : const char nbits_table[32] =
274 : {
275 : 32, 1, 23, 2, 29, 24, 14, 3,
276 : 30, 27, 25, 18, 20, 15, 10, 4,
277 : 31, 22, 28, 13, 26, 17, 19, 9,
278 : 21, 12, 16, 8, 11, 7, 6, 5
279 : };
280 :
281 11040 : static int impl_NumberOfBits( unsigned long nNum )
282 : {
283 : // http://en.wikipedia.org/wiki/De_Bruijn_sequence
284 : // background paper: Using de Bruijn Sequences to Index a 1 in a
285 : // Computer Word (1998) Charles E. Leiserson,
286 : // Harald Prokop, Keith H. Randall
287 : // (e.g. http://citeseer.ist.psu.edu/leiserson98using.html)
288 11040 : const sal_uInt32 nDeBruijn = 0x7DCD629;
289 :
290 11040 : if ( nNum == 0 )
291 0 : return 0;
292 :
293 : // Get it to form like 0000001111111111b
294 11040 : nNum |= ( nNum >> 1 );
295 11040 : nNum |= ( nNum >> 2 );
296 11040 : nNum |= ( nNum >> 4 );
297 11040 : nNum |= ( nNum >> 8 );
298 11040 : nNum |= ( nNum >> 16 );
299 :
300 : sal_uInt32 nNumber;
301 11040 : int nBonus = 0;
302 :
303 : #if SAL_TYPES_SIZEOFLONG == 4
304 : nNumber = nNum;
305 : #elif SAL_TYPES_SIZEOFLONG == 8
306 11040 : nNum |= ( nNum >> 32 );
307 :
308 11040 : if ( nNum & 0x80000000 )
309 : {
310 10960 : nNumber = sal_uInt32( nNum >> 32 );
311 10960 : nBonus = 32;
312 :
313 10960 : if ( nNumber == 0 )
314 0 : return 32;
315 : }
316 : else
317 80 : nNumber = sal_uInt32( nNum & 0xFFFFFFFF );
318 : #else
319 : #error "Unknown size of long!"
320 : #endif
321 :
322 : // De facto shift left of nDeBruijn using multiplication (nNumber
323 : // is all ones from topmost bit, thus nDeBruijn + (nDeBruijn *
324 : // nNumber) => nDeBruijn * (nNumber+1) clears all those bits to
325 : // zero, sets the next bit to one, and thus effectively shift-left
326 : // nDeBruijn by lg2(nNumber+1). This generates a distinct 5bit
327 : // sequence in the msb for each distinct position of the last
328 : // leading 0 bit - that's the property of a de Bruijn number.
329 11040 : nNumber = nDeBruijn + ( nDeBruijn * nNumber );
330 :
331 : // 5-bit window indexes the result
332 11040 : return ( nbits_table[nNumber >> 27] ) + nBonus;
333 : }
334 :
335 : /** Inaccurate cancellation for a fraction.
336 :
337 : Clip both nominator and denominator to said number of bits. If
338 : either of those already have equal or less number of bits used,
339 : this method does nothing.
340 :
341 : @param nSignificantBits denotes, how many significant binary
342 : digits to maintain, in both nominator and denominator.
343 :
344 : @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
345 : largest error occurs with the following pair of values:
346 :
347 : binary 1000000011111111111111111111111b/1000000000000000000000000000000b
348 : = 1082130431/1073741824
349 : = approx. 1.007812499
350 :
351 : A ReduceInaccurate(8) yields 1/1.
352 : */
353 : template<typename T>
354 5520 : static void rational_ReduceInaccurate(boost::rational<T>& rRational, unsigned nSignificantBits)
355 : {
356 5520 : if ( !rRational )
357 2 : return;
358 :
359 : // http://www.boost.org/doc/libs/release/libs/rational/rational.html#Internal%20representation
360 5520 : const bool bNeg = ( rRational.numerator() < 0 );
361 5520 : T nMul = bNeg? -rRational.numerator(): rRational.numerator();
362 5520 : T nDiv = rRational.denominator();
363 :
364 : DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!");
365 :
366 : // How much bits can we lose?
367 5520 : const int nMulBitsToLose = std::max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 );
368 5520 : const int nDivBitsToLose = std::max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 );
369 :
370 5520 : const int nToLose = std::min( nMulBitsToLose, nDivBitsToLose );
371 :
372 : // Remove the bits
373 5520 : nMul >>= nToLose;
374 5520 : nDiv >>= nToLose;
375 :
376 5520 : if ( !nMul || !nDiv ) {
377 : // Return without reduction
378 : OSL_FAIL( "Oops, we reduced too much..." );
379 2 : return;
380 : }
381 :
382 5518 : rRational.assign( bNeg? -T( nMul ): T( nMul ), nDiv );
383 2556 : }
384 :
385 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
