From 31af61ea091cc895b893c849f2130aa35792b7db Mon Sep 17 00:00:00 2001 From: Jan Holesovsky Date: Thu, 23 Oct 2014 17:41:47 +0200 Subject: Fraction: Revert "fdo#81356: convert Fraction to boost::rational - wip" This reverts commit 47a2d7642d249d70b5da0c330a73f3a0032e4bba. Conflicts: cui/source/tabpages/transfrm.cxx svx/source/svdraw/svdedtv1.cxx svx/source/svdraw/svdibrow.cxx sw/source/filter/ww1/w1filter.cxx tools/source/generic/rational.cxx Change-Id: I4849916f5f277a4afef0e279b0135c76b36b9d15 --- tools/CppunitTest_tools_test.mk | 1 - tools/Library_tl.mk | 2 +- tools/qa/cppunit/test_rational.cxx | 101 -------- tools/source/generic/fract.cxx | 504 +++++++++++++++++++++++++++++++++++++ tools/source/generic/rational.cxx | 173 ------------- tools/test/tests.cxx | 111 ++++++++ 6 files changed, 616 insertions(+), 276 deletions(-) delete mode 100644 tools/qa/cppunit/test_rational.cxx create mode 100644 tools/source/generic/fract.cxx delete mode 100644 tools/source/generic/rational.cxx create mode 100644 tools/test/tests.cxx (limited to 'tools') diff --git a/tools/CppunitTest_tools_test.mk b/tools/CppunitTest_tools_test.mk index 87abf590a8db..bd514b516517 100644 --- a/tools/CppunitTest_tools_test.mk +++ b/tools/CppunitTest_tools_test.mk @@ -17,7 +17,6 @@ $(eval $(call gb_CppunitTest_add_exception_objects,tools_test, \ tools/qa/cppunit/test_bigint \ tools/qa/cppunit/test_inetmime \ tools/qa/cppunit/test_pathutils \ - tools/qa/cppunit/test_rational \ tools/qa/cppunit/test_reversemap \ tools/qa/cppunit/test_stream \ tools/qa/cppunit/test_urlobj \ diff --git a/tools/Library_tl.mk b/tools/Library_tl.mk index 3ce2007a6e0f..856471bbf7ba 100644 --- a/tools/Library_tl.mk +++ b/tools/Library_tl.mk @@ -55,7 +55,7 @@ $(eval $(call gb_Library_add_exception_objects,tl,\ tools/source/generic/bigint \ tools/source/generic/color \ tools/source/generic/config \ - tools/source/generic/rational \ + tools/source/generic/fract \ tools/source/generic/gen \ tools/source/generic/line \ tools/source/generic/link \ diff --git a/tools/qa/cppunit/test_rational.cxx b/tools/qa/cppunit/test_rational.cxx deleted file mode 100644 index e503c1c5d38d..000000000000 --- a/tools/qa/cppunit/test_rational.cxx +++ /dev/null @@ -1,101 +0,0 @@ -/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ -/* - * This file is part of the LibreOffice project. - * - * This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. - * - * This file incorporates work covered by the following license notice: - * - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed - * with this work for additional information regarding copyright - * ownership. The ASF licenses this file to you under the Apache - * License, Version 2.0 (the "License"); you may not use this file - * except in compliance with the License. You may obtain a copy of - * the License at http://www.apache.org/licenses/LICENSE-2.0 . - */ - -#include -#include -#include - -#include -#include - -namespace tools -{ - -class RationalTest : public CppUnit::TestFixture -{ -public: - - void testReduceInaccurate() - { - const boost::rational aFract(1082130431,1073741824); - CPPUNIT_ASSERT_MESSAGE( "Fraction #1 not approximately equal to 1.007812499068677", - rtl::math::approxEqual(boost::rational_cast(aFract),1.007812499068677) ); - - boost::rational aFract2( aFract ); - rational_ReduceInaccurate(aFract2, 8); - CPPUNIT_ASSERT_MESSAGE( "Fraction #2 not 1", - aFract2.numerator() == 1 && - aFract2.denominator() == 1 ); - - boost::rational aFract3( 0x7AAAAAAA, 0x35555555 ); - CPPUNIT_ASSERT_MESSAGE( "Fraction #3 cancellation wrong", - aFract3.numerator() == 0x7AAAAAAA && - aFract3.denominator() == 0x35555555 ); - rational_ReduceInaccurate(aFract3, 30); - CPPUNIT_ASSERT_MESSAGE( "Fraction #3 ReduceInaccurate errorneously cut precision", - aFract3.numerator() == 0x7AAAAAAA && - aFract3.denominator() == 0x35555555 ); - - rational_ReduceInaccurate(aFract3, 29); - CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 29 bits failed", - aFract3.numerator() == 0x3D555555 && - aFract3.denominator() == 0x1AAAAAAA ); - - rational_ReduceInaccurate(aFract3, 9); - CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 9 bits failed", - aFract3.numerator() == 0x0147 && - aFract3.denominator() == 0x008E ); - - rational_ReduceInaccurate(aFract3, 1); - CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 1 bit failed", - aFract3.numerator() == 2 && - aFract3.denominator() == 1 ); - - rational_ReduceInaccurate(aFract3, 0); - CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 0 bits failed", - aFract3.numerator() == 2 && - aFract3.denominator() == 1 ); - -#if SAL_TYPES_SIZEOFLONG == 8 - boost::rational aFract4(0x7AAAAAAAAAAAAAAA, 0x3555555555555555); - CPPUNIT_ASSERT_MESSAGE( "Fraction #4 cancellation wrong", - aFract4.numerator() == 0x7AAAAAAAAAAAAAAA && - aFract4.denominator() == 0x3555555555555555 ); - rational_ReduceInaccurate(aFract4, 62); - CPPUNIT_ASSERT_MESSAGE( "Fraction #4 ReduceInaccurate errorneously cut precision", - aFract4.numerator() == 0x7AAAAAAAAAAAAAAA && - aFract4.denominator() == 0x3555555555555555 ); - - rational_ReduceInaccurate(aFract4, 61); - CPPUNIT_ASSERT_MESSAGE( "Fraction #4 ReduceInaccurate reduce to 61 bit failed", - aFract4.numerator() == 0x3D55555555555555 && - aFract4.denominator() == 0x1AAAAAAAAAAAAAAA ); -#endif - } - - CPPUNIT_TEST_SUITE(RationalTest); - CPPUNIT_TEST(testReduceInaccurate); - CPPUNIT_TEST_SUITE_END(); -}; - - -CPPUNIT_TEST_SUITE_REGISTRATION(RationalTest); -} // namespace tools - -/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/tools/source/generic/fract.cxx b/tools/source/generic/fract.cxx new file mode 100644 index 000000000000..198a42aa2639 --- /dev/null +++ b/tools/source/generic/fract.cxx @@ -0,0 +1,504 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +#include + +#include +#include +#include +#include +#include +#include +#include + +/** Compute greates common divisor using Euclidian algorithm + + As the algorithm works on positive values only, the absolute value + of each parameter is used. + + @param nVal1 + @param nVal2 + + @note: If one parameter is {0,1}, GetGGT returns 1. +*/ +static long GetGGT( long nVal1, long nVal2 ) +{ + nVal1 = std::abs( nVal1 ); + nVal2 = std::abs( nVal2 ); + + if ( nVal1 <= 1 || nVal2 <= 1 ) + return 1; + + while ( nVal1 != nVal2 ) + { + if ( nVal1 > nVal2 ) + { + nVal1 %= nVal2; + if ( nVal1 == 0 ) + return nVal2; + } + else + { + nVal2 %= nVal1; + if ( nVal2 == 0 ) + return nVal1; + } + } + return nVal1; +} + +static void Reduce( BigInt &rVal1, BigInt &rVal2 ) +{ + BigInt nA( rVal1 ); + BigInt nB( rVal2 ); + nA.Abs(); + nB.Abs(); + + if ( nA.IsOne() || nB.IsOne() || nA.IsZero() || nB.IsZero() ) + return; + + while ( nA != nB ) + { + if ( nA > nB ) + { + nA %= nB; + if ( nA.IsZero() ) + { + rVal1 /= nB; + rVal2 /= nB; + return; + } + } + else + { + nB %= nA; + if ( nB.IsZero() ) + { + rVal1 /= nA; + rVal2 /= nA; + return; + } + } + } + + rVal1 /= nA; + rVal2 /= nB; +} + +// Initialized by setting nNum as nominator and nDen as denominator +// Negative values in the denominator are invalid and cause the +// inversion of both nominator and denominator signs +// in order to return the correct value. +Fraction::Fraction( long nNum, long nDen ) +{ + nNumerator = nNum; + nDenominator = nDen; + if ( nDenominator < 0 ) + { + nDenominator = -nDenominator; + nNumerator = -nNumerator; + } + + // Reduce through GCD + long n = GetGGT( nNumerator, nDenominator ); + nNumerator /= n; + nDenominator /= n; +} + +// If dVal > LONG_MAX, the fraction is set as invalid. +// Otherwise, dVal and denominator are multiplied with 10, until one of them +// is larger than (LONG_MAX / 10) and the fraction is reduced with GCD +Fraction::Fraction( double dVal ) +{ + long nDen = 1; + long nMAX = LONG_MAX / 10; + + if ( dVal > LONG_MAX || dVal < LONG_MIN ) + { + nNumerator = 0; + nDenominator = -1; + return; + } + + while ( std::abs( (long)dVal ) < nMAX && nDen < nMAX ) + { + dVal *= 10; + nDen *= 10; + } + nNumerator = (long)dVal; + nDenominator = nDen; + + // Reduce through GCD + long n = GetGGT( nNumerator, nDenominator ); + nNumerator /= n; + nDenominator /= n; +} + +Fraction::operator double() const +{ + if ( nDenominator > 0 ) + return (double)nNumerator / (double)nDenominator; + else + return (double)0; +} + +// This methods first validates both values. +// If one of the arguments is invalid, the whole operation is invalid. +// For addition both fractions are extended to match the denominator, +// then nominators are added and reduced (through GCD). +// Internal datatype for computation is SLong to detect overflows, +// which cause the operation to be marked as invalid +Fraction& Fraction::operator += ( const Fraction& rVal ) +{ + if ( !rVal.IsValid() ) + { + nNumerator = 0; + nDenominator = -1; + } + if ( !IsValid() ) + return *this; + + // (a/b) + (c/d) = ( (a*d) + (c*b) ) / (b*d) + BigInt nN( nNumerator ); + nN *= BigInt( rVal.nDenominator ); + BigInt nW1Temp( nDenominator ); + nW1Temp *= BigInt( rVal.nNumerator ); + nN += nW1Temp; + + BigInt nD( nDenominator ); + nD *= BigInt( rVal.nDenominator ); + + Reduce( nN, nD ); + + if ( nN.bIsBig || nD.bIsBig ) + { + nNumerator = 0; + nDenominator = -1; + } + else + { + nNumerator = (long)nN, + nDenominator = (long)nD; + } + + return *this; +} + +// This methods first validates both values. +// If one of the arguments is invalid, the whole operation is invalid. +// For substraction, both fractions are extended to match the denominator, +// then nominators are substracted and reduced (through GCD). +// Internal datatype for computation is SLong to detect overflows, +// which cause the operation to be marked as invalid +Fraction& Fraction::operator -= ( const Fraction& rVal ) +{ + if ( !rVal.IsValid() ) + { + nNumerator = 0; + nDenominator = -1; + } + if ( !IsValid() ) + return *this; + + // (a/b) - (c/d) = ( (a*d) - (c*b) ) / (b*d) + BigInt nN( nNumerator ); + nN *= BigInt( rVal.nDenominator ); + BigInt nW1Temp( nDenominator ); + nW1Temp *= BigInt( rVal.nNumerator ); + nN -= nW1Temp; + + BigInt nD( nDenominator ); + nD *= BigInt( rVal.nDenominator ); + + Reduce( nN, nD ); + + if ( nN.bIsBig || nD.bIsBig ) + { + nNumerator = 0; + nDenominator = -1; + } + else + { + nNumerator = (long)nN, + nDenominator = (long)nD; + } + + return *this; +} + +// This methods first validates both values. +// If one of the arguments is invalid, the whole operation is invalid. +// For mutliplication, nominator and denominators are first reduced +// (through GCD), and then multiplied. +// Internal datatype for computation is BigInt to detect overflows, +// which cause the operation to be marked as invalid +Fraction& Fraction::operator *= ( const Fraction& rVal ) +{ + if ( !rVal.IsValid() ) + { + nNumerator = 0; + nDenominator = -1; + } + if ( !IsValid() ) + return *this; + + long nGGT1 = GetGGT( nNumerator, rVal.nDenominator ); + long nGGT2 = GetGGT( rVal.nNumerator, nDenominator ); + BigInt nN( nNumerator / nGGT1 ); + nN *= BigInt( rVal.nNumerator / nGGT2 ); + BigInt nD( nDenominator / nGGT2 ); + nD *= BigInt( rVal.nDenominator / nGGT1 ); + + if ( nN.bIsBig || nD.bIsBig ) + { + nNumerator = 0; + nDenominator = -1; + } + else + { + nNumerator = (long)nN, + nDenominator = (long)nD; + } + + return *this; +} + +// This methods first validates both values. +// If one of the arguments is invalid, the whole operation is invalid. +// For dividing a/b, we multiply a with the inverse of b. +// To avoid overflows, we first reduce both fractions with GCD. +// Internal datatype for computation is BigInt to detect overflows, +// which cause the operation to be marked as invalid +Fraction& Fraction::operator /= ( const Fraction& rVal ) +{ + if ( !rVal.IsValid() ) + { + nNumerator = 0; + nDenominator = -1; + } + if ( !IsValid() ) + return *this; + + long nGGT1 = GetGGT( nNumerator, rVal.nNumerator ); + long nGGT2 = GetGGT( rVal.nDenominator, nDenominator ); + BigInt nN( nNumerator / nGGT1 ); + nN *= BigInt( rVal.nDenominator / nGGT2 ); + BigInt nD( nDenominator / nGGT2 ); + nD *= BigInt( rVal.nNumerator / nGGT1 ); + + if ( nN.bIsBig || nD.bIsBig ) + { + nNumerator = 0; + nDenominator = -1; + } + else + { + nNumerator = (long)nN, + nDenominator = (long)nD; + if ( nDenominator < 0 ) + { + nDenominator = -nDenominator; + nNumerator = -nNumerator; + } + } + + return *this; +} + +// Similar to clz_table that can be googled +const char nbits_table[32] = +{ + 32, 1, 23, 2, 29, 24, 14, 3, + 30, 27, 25, 18, 20, 15, 10, 4, + 31, 22, 28, 13, 26, 17, 19, 9, + 21, 12, 16, 8, 11, 7, 6, 5 +}; + +static int impl_NumberOfBits( unsigned long nNum ) +{ + // http://en.wikipedia.org/wiki/De_Bruijn_sequence + // background paper: Using de Bruijn Sequences to Index a 1 in a + // Computer Word (1998) Charles E. Leiserson, + // Harald Prokop, Keith H. Randall + // (e.g. http://citeseer.ist.psu.edu/leiserson98using.html) + const sal_uInt32 nDeBruijn = 0x7DCD629; + + if ( nNum == 0 ) + return 0; + + // Get it to form like 0000001111111111b + nNum |= ( nNum >> 1 ); + nNum |= ( nNum >> 2 ); + nNum |= ( nNum >> 4 ); + nNum |= ( nNum >> 8 ); + nNum |= ( nNum >> 16 ); + + sal_uInt32 nNumber; + int nBonus = 0; + +#if SAL_TYPES_SIZEOFLONG == 4 + nNumber = nNum; +#elif SAL_TYPES_SIZEOFLONG == 8 + nNum |= ( nNum >> 32 ); + + if ( nNum & 0x80000000 ) + { + nNumber = sal_uInt32( nNum >> 32 ); + nBonus = 32; + + if ( nNumber == 0 ) + return 32; + } + else + nNumber = sal_uInt32( nNum & 0xFFFFFFFF ); +#else +#error "Unknown size of long!" +#endif + + // De facto shift left of nDeBruijn using multiplication (nNumber + // is all ones from topmost bit, thus nDeBruijn + (nDeBruijn * + // nNumber) => nDeBruijn * (nNumber+1) clears all those bits to + // zero, sets the next bit to one, and thus effectively shift-left + // nDeBruijn by lg2(nNumber+1). This generates a distinct 5bit + // sequence in the msb for each distinct position of the last + // leading 0 bit - that's the property of a de Bruijn number. + nNumber = nDeBruijn + ( nDeBruijn * nNumber ); + + // 5-bit window indexes the result + return ( nbits_table[nNumber >> 27] ) + nBonus; +} + +/** Inaccurate cancellation for a fraction. + + Clip both nominator and denominator to said number of bits. If + either of those already have equal or less number of bits used, + this method does nothing. + + @param nSignificantBits denotes, how many significant binary + digits to maintain, in both nominator and denominator. + + @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the + largest error occurs with the following pair of values: + + binary 1000000011111111111111111111111b/1000000000000000000000000000000b + = 1082130431/1073741824 + = approx. 1.007812499 + + A ReduceInaccurate(8) yields 1/1. +*/ +void Fraction::ReduceInaccurate( unsigned nSignificantBits ) +{ + if ( !nNumerator || !nDenominator ) + return; + + // Count with unsigned longs only + const bool bNeg = ( nNumerator < 0 ); + unsigned long nMul = (unsigned long)( bNeg? -nNumerator: nNumerator ); + unsigned long nDiv = (unsigned long)( nDenominator ); + + DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!"); + + // How much bits can we lose? + const int nMulBitsToLose = std::max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 ); + const int nDivBitsToLose = std::max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 ); + + const int nToLose = std::min( nMulBitsToLose, nDivBitsToLose ); + + // Remove the bits + nMul >>= nToLose; + nDiv >>= nToLose; + + if ( !nMul || !nDiv ) + { + // Return without reduction + OSL_FAIL( "Oops, we reduced too much..." ); + return; + } + + // Reduce + long n1 = GetGGT( nMul, nDiv ); + if ( n1 != 1 ) + { + nMul /= n1; + nDiv /= n1; + } + + nNumerator = bNeg? -long( nMul ): long( nMul ); + nDenominator = nDiv; +} + +bool operator == ( const Fraction& rVal1, const Fraction& rVal2 ) +{ + if ( !rVal1.IsValid() || !rVal2.IsValid() ) + return false; + + return rVal1.nNumerator == rVal2.nNumerator + && rVal1.nDenominator == rVal2.nDenominator; +} + +// This methods first validates and reduces both values. +// To compare (a/b) with (c/d), extend denominators (b*d), then return +// the result of comparing the nominators (a < c) +bool operator < ( const Fraction& rVal1, const Fraction& rVal2 ) +{ + if ( !rVal1.IsValid() || !rVal2.IsValid() ) + return false; + + BigInt nN( rVal1.nNumerator ); + nN *= BigInt( rVal2.nDenominator ); + BigInt nD( rVal1.nDenominator ); + nD *= BigInt( rVal2.nNumerator ); + + return nN < nD; +} + +// This methods first validates and reduces both values. +// To compare (a/b) with (c/d), extend denominators (b*d), then return +// the result of comparing nominators (a > c) +bool operator > ( const Fraction& rVal1, const Fraction& rVal2 ) +{ + if ( !rVal1.IsValid() || !rVal2.IsValid() ) + return false; + + BigInt nN( rVal1.nNumerator ); + nN *= BigInt( rVal2.nDenominator ); + BigInt nD( rVal1.nDenominator); + nD *= BigInt( rVal2.nNumerator ); + + return nN > nD; +} + +SvStream& ReadFraction( SvStream& rIStream, Fraction& rFract ) +{ + sal_Int32 nTmp(0); + rIStream.ReadInt32( nTmp ); + rFract.nNumerator = nTmp; + rIStream.ReadInt32( nTmp ); + rFract.nDenominator = nTmp; + return rIStream; +} + +SvStream& WriteFraction( SvStream& rOStream, const Fraction& rFract ) +{ + rOStream.WriteInt32( rFract.nNumerator ); + rOStream.WriteInt32( rFract.nDenominator ); + return rOStream; +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/tools/source/generic/rational.cxx b/tools/source/generic/rational.cxx deleted file mode 100644 index 6222265b87f3..000000000000 --- a/tools/source/generic/rational.cxx +++ /dev/null @@ -1,173 +0,0 @@ -/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ -/* - * This file is part of the LibreOffice project. - * - * This Source Code Form is subject to the terms of the Mozilla Public - * License, v. 2.0. If a copy of the MPL was not distributed with this - * file, You can obtain one at http://mozilla.org/MPL/2.0/. - * - */ - -#include -#include -#include - -// If dVal > LONG_MAX or dVal < LONG_MIN, the rational throws a boost::bad_rational. -// Otherwise, dVal and denominator are multiplied with 10, until one of them -// is larger than (LONG_MAX / 10). -boost::rational rational_FromDouble(double dVal) -{ - long nDen = 1; - long nMAX = LONG_MAX / 10; - - if ( dVal > LONG_MAX || dVal < LONG_MIN ) - { - throw boost::bad_rational(); - } - - while ( std::abs( (long)dVal ) < nMAX && nDen < nMAX ) - { - dVal *= 10; - nDen *= 10; - } - return boost::rational((long) dVal, nDen); -} - -// Similar to clz_table that can be googled -const char nbits_table[32] = -{ - 32, 1, 23, 2, 29, 24, 14, 3, - 30, 27, 25, 18, 20, 15, 10, 4, - 31, 22, 28, 13, 26, 17, 19, 9, - 21, 12, 16, 8, 11, 7, 6, 5 -}; - -static int impl_NumberOfBits( unsigned long nNum ) -{ - // http://en.wikipedia.org/wiki/De_Bruijn_sequence - // background paper: Using de Bruijn Sequences to Index a 1 in a - // Computer Word (1998) Charles E. Leiserson, - // Harald Prokop, Keith H. Randall - // (e.g. http://citeseer.ist.psu.edu/leiserson98using.html) - const sal_uInt32 nDeBruijn = 0x7DCD629; - - if ( nNum == 0 ) - return 0; - - // Get it to form like 0000001111111111b - nNum |= ( nNum >> 1 ); - nNum |= ( nNum >> 2 ); - nNum |= ( nNum >> 4 ); - nNum |= ( nNum >> 8 ); - nNum |= ( nNum >> 16 ); - - sal_uInt32 nNumber; - int nBonus = 0; - -#if SAL_TYPES_SIZEOFLONG == 4 - nNumber = nNum; -#elif SAL_TYPES_SIZEOFLONG == 8 - nNum |= ( nNum >> 32 ); - - if ( nNum & 0x80000000 ) - { - nNumber = sal_uInt32( nNum >> 32 ); - nBonus = 32; - - if ( nNumber == 0 ) - return 32; - } - else - nNumber = sal_uInt32( nNum & 0xFFFFFFFF ); -#else -#error "Unknown size of long!" -#endif - - // De facto shift left of nDeBruijn using multiplication (nNumber - // is all ones from topmost bit, thus nDeBruijn + (nDeBruijn * - // nNumber) => nDeBruijn * (nNumber+1) clears all those bits to - // zero, sets the next bit to one, and thus effectively shift-left - // nDeBruijn by lg2(nNumber+1). This generates a distinct 5bit - // sequence in the msb for each distinct position of the last - // leading 0 bit - that's the property of a de Bruijn number. - nNumber = nDeBruijn + ( nDeBruijn * nNumber ); - - // 5-bit window indexes the result - return ( nbits_table[nNumber >> 27] ) + nBonus; -} - -/** Inaccurate cancellation for a fraction. - - Clip both nominator and denominator to said number of bits. If - either of those already have equal or less number of bits used, - this method does nothing. - - @param nSignificantBits denotes, how many significant binary - digits to maintain, in both nominator and denominator. - - @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the - largest error occurs with the following pair of values: - - binary 1000000011111111111111111111111b/1000000000000000000000000000000b - = 1082130431/1073741824 - = approx. 1.007812499 - - A ReduceInaccurate(8) yields 1/1. -*/ -void rational_ReduceInaccurate(boost::rational& rRational, unsigned nSignificantBits) -{ - if ( !rRational.numerator() || !rRational.denominator() ) - return; - - // Count with unsigned longs only - // http://www.boost.org/doc/libs/release/libs/rational/rational.html#Internal%20representation - const bool bNeg = ( rRational.numerator() < 0 ); - unsigned long nMul = (unsigned long)( bNeg? -rRational.numerator(): rRational.numerator() ); - unsigned long nDiv = (unsigned long)( rRational.denominator() ); - - DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!"); - - // How much bits can we lose? - const int nMulBitsToLose = impl_NumberOfBits( nMul ) - int( nSignificantBits ); - const int nDivBitsToLose = impl_NumberOfBits( nDiv ) - int( nSignificantBits ); - - int nToLose = nMulBitsToLose < nDivBitsToLose ? nMulBitsToLose : nDivBitsToLose; - nToLose = nToLose < 0 ? 0 : nToLose; - - // Remove the bits - nMul >>= nToLose; - nDiv >>= nToLose; - - if ( !nMul || !nDiv ) - { - // Return without reduction - OSL_FAIL( "Oops, we reduced too much..." ); - return; - } - - rRational.assign( bNeg? -long( nMul ): long( nMul ), nDiv ); -} - -SvStream& ReadFraction(SvStream& rIStream, boost::rational& rRational) -{ - sal_Int32 nTmpNumerator(0), nTmpDenominator(0); - rIStream.ReadInt32( nTmpNumerator ); - rIStream.ReadInt32( nTmpDenominator ); - // NOTE: use rational zero for invalid rationals - avoid boost::bad_rational() exception - if (nTmpDenominator == 0) { - nTmpNumerator = 0; - nTmpDenominator = 1; - } - rRational.assign( nTmpNumerator, nTmpDenominator ); - return rIStream; -} - -SvStream& WriteFraction(SvStream& rOStream, const boost::rational& rRational) -{ - //fdo#39428 SvStream no longer supports operator<<(long) - rOStream.WriteInt32( sal::static_int_cast(rRational.numerator()) ); - rOStream.WriteInt32( sal::static_int_cast(rRational.denominator()) ); - return rOStream; -} - -/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/tools/test/tests.cxx b/tools/test/tests.cxx new file mode 100644 index 000000000000..5e848c492cca --- /dev/null +++ b/tools/test/tests.cxx @@ -0,0 +1,111 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +#include +#include +#include +#include + +#include +#include + +namespace tools +{ + +class FractionTest : public CppUnit::TestFixture +{ +public: + void setUp() + { + } + + void tearDown() + { + } + + void testFraction() + { + const Fraction aFract(1082130431,1073741824); + CPPUNIT_ASSERT_MESSAGE( "Fraction #1 not approximately equal to 1.007812499068677", + rtl::math::approxEqual((double)aFract,1.007812499068677) ); + + Fraction aFract2( aFract ); + aFract2.ReduceInaccurate(8); + CPPUNIT_ASSERT_MESSAGE( "Fraction #2 not 1", + aFract2.GetNumerator() == 1 && + aFract2.GetDenominator() == 1 ); + + Fraction aFract3( 0x7AAAAAAA, 0x35555555 ); + CPPUNIT_ASSERT_MESSAGE( "Fraction #3 cancellation wrong", + aFract3.GetNumerator() == 0x7AAAAAAA && + aFract3.GetDenominator() == 0x35555555 ); + aFract3.ReduceInaccurate(30); + CPPUNIT_ASSERT_MESSAGE( "Fraction #3 ReduceInaccurate errorneously cut precision", + aFract3.GetNumerator() == 0x7AAAAAAA && + aFract3.GetDenominator() == 0x35555555 ); + + aFract3.ReduceInaccurate(29); + CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 29 bits failed", + aFract3.GetNumerator() == 0x3D555555 && + aFract3.GetDenominator() == 0x1AAAAAAA ); + + aFract3.ReduceInaccurate(9); + CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 9 bits failed", + aFract3.GetNumerator() == 0x0147 && + aFract3.GetDenominator() == 0x008E ); + + aFract3.ReduceInaccurate(1); + CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 1 bit failed", + aFract3.GetNumerator() == 2 && + aFract3.GetDenominator() == 1 ); + + aFract3.ReduceInaccurate(0); + CPPUNIT_ASSERT_MESSAGE( "Fraction #3 reduce to 0 bits failed", + aFract3.GetNumerator() == 2 && + aFract3.GetDenominator() == 1 ); + +#if SAL_TYPES_SIZEOFLONG == 8 + Fraction aFract4(0x7AAAAAAAAAAAAAAA, 0x3555555555555555); + CPPUNIT_ASSERT_MESSAGE( "Fraction #4 cancellation wrong", + aFract4.GetNumerator() == 0x7AAAAAAAAAAAAAAA && + aFract4.GetDenominator() == 0x3555555555555555 ); + aFract4.ReduceInaccurate(62); + CPPUNIT_ASSERT_MESSAGE( "Fraction #4 ReduceInaccurate errorneously cut precision", + aFract4.GetNumerator() == 0x7AAAAAAAAAAAAAAA && + aFract4.GetDenominator() == 0x3555555555555555 ); + + aFract4.ReduceInaccurate(61); + CPPUNIT_ASSERT_MESSAGE( "Fraction #4 ReduceInaccurate reduce to 61 bit failed", + aFract4.GetNumerator() == 0x3D55555555555555 && + aFract4.GetDenominator() == 0x1AAAAAAAAAAAAAAA ); +#endif + } + + CPPUNIT_TEST_SUITE(FractionTest); + CPPUNIT_TEST(testFraction); + CPPUNIT_TEST_SUITE_END(); +}; + + +CPPUNIT_TEST_SUITE_REGISTRATION(FractionTest); +} // namespace tools + +CPPUNIT_PLUGIN_IMPLEMENT(); + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ -- cgit