fdo#81356: convert Fraction to boost::rational<long> - wip

* Added rational util functions used by Fraction class not
  available in the boost::rational class.
* Replaced usage of Fraction by boost::rational<long>
* Removed code that relies on:
  1. fraction.IsValid() -- rational only allow valid values, ie
     denominator() != 0
  2. rational.denominator() == 0 -- always false
  3. rational.denominator() < 0 -- always false but implementation
     detail: http://www.boost.org/doc/libs/release/libs/rational/rational.html#Internal%20representation
* Simplified code that relies on:
  1. rational.denominator() != 0 -- always true
* BUGS EXIST because Fraction allows the creation of invalid values but
  boost::rational throws the exception boost::bad_rational

Change-Id: I84970a4956afb3f91ac0c8f726547466319420f9
Reviewed-on: https://gerrit.libreoffice.org/11551
Reviewed-by: David Tardon <dtardon@redhat.com>
Tested-by: David Tardon <dtardon@redhat.com>

6 files changed, 275 insertions, 616 deletions

diff --git a/tools/CppunitTest_tools_test.mk b/tools/CppunitTest_tools_test.mk
index 48324de54c3c..e5fda5fc92b8 100644
--- a/tools/CppunitTest_tools_test.mk
+++ b/tools/CppunitTest_tools_test.mk
@@ -16,6 +16,7 @@ $(eval $(call gb_CppunitTest_use_external,tools_test,boost_headers))
 $(eval $(call gb_CppunitTest_add_exception_objects,tools_test, \
     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 856471bbf7ba..3ce2007a6e0f 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/fract \
+    tools/source/generic/rational \
     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
new file mode 100644
index 000000000000..e503c1c5d38d
--- /dev/null
+++ b/tools/qa/cppunit/test_rational.cxx
@@ -0,0 +1,101 @@
+/* -*- 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 <sal/types.h>
+#include <cppunit/TestFixture.h>
+#include <cppunit/extensions/HelperMacros.h>
+
+#include <rtl/math.hxx>
+#include <tools/rational.hxx>
+
+namespace tools
+{
+
+class RationalTest : public CppUnit::TestFixture
+{
+public:
+
+    void testReduceInaccurate()
+    {
+        const boost::rational<long> aFract(1082130431,1073741824);
+        CPPUNIT_ASSERT_MESSAGE( "Fraction #1 not approximately equal to 1.007812499068677",
+                                rtl::math::approxEqual(boost::rational_cast<double>(aFract),1.007812499068677) );
+
+        boost::rational<long> aFract2( aFract );
+        rational_ReduceInaccurate(aFract2, 8);
+        CPPUNIT_ASSERT_MESSAGE( "Fraction #2 not 1",
+                                aFract2.numerator() == 1 &&
+                                aFract2.denominator() == 1 );
+
+        boost::rational<long> 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<long> 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
deleted file mode 100644
index 198a42aa2639..000000000000
--- a/tools/source/generic/fract.cxx
+++ /dev/null
@@ -1,504 +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 <algorithm>
-
-#include <limits.h>
-#include <rtl/ustring.hxx>
-#include <tools/debug.hxx>
-#include <tools/fract.hxx>
-#include <tools/lineend.hxx>
-#include <tools/stream.hxx>
-#include <tools/bigint.hxx>
-
-/** 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
new file mode 100644
index 000000000000..30690bea2faa
--- /dev/null
+++ b/tools/source/generic/rational.cxx
@@ -0,0 +1,172 @@
+/* -*- 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 <tools/debug.hxx>
+#include <tools/rational.hxx>
+#include <tools/stream.hxx>
+
+// 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<long> 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>((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<long>& 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 = 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;
+    }
+
+    rRational.assign( bNeg? -long( nMul ): long( nMul ), nDiv );
+}
+
+SvStream& ReadFraction(SvStream& rIStream, boost::rational<long>& 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<long>& rRational)
+{
+    //fdo#39428 SvStream no longer supports operator<<(long)
+    rOStream.WriteInt32( sal::static_int_cast<sal_Int32>(rRational.numerator()) );
+    rOStream.WriteInt32( sal::static_int_cast<sal_Int32>(rRational.denominator()) );
+    return rOStream;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/tools/test/tests.cxx b/tools/test/tests.cxx
deleted file mode 100644
index 5e848c492cca..000000000000
--- a/tools/test/tests.cxx
+++ /dev/null
@@ -1,111 +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 <sal/types.h>
-#include <cppunit/TestFixture.h>
-#include <cppunit/extensions/HelperMacros.h>
-#include <cppunit/plugin/TestPlugIn.h>
-
-#include <rtl/math.hxx>
-#include <tools/fract.hxx>
-
-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: */