LCOV - code coverage report
Current view: top level - tools/source/generic - fract.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 207 0.0 %
Date: 2014-04-14 Functions: 0 16 0.0 %
Legend: Lines: hit not hit

          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 <limits.h>
      21             : #include <rtl/ustring.hxx>
      22             : #include <tools/debug.hxx>
      23             : #include <tools/fract.hxx>
      24             : #include <tools/lineend.hxx>
      25             : #include <tools/stream.hxx>
      26             : #include <tools/bigint.hxx>
      27             : 
      28             : /** Compute greates common divisor using Euclidian algorithm
      29             : 
      30             :     As the algorithm works on positive values only, the absolute value
      31             :     of each parameter is used.
      32             : 
      33             :     @param nVal1
      34             :     @param nVal2
      35             : 
      36             :     @note: If one parameter is {0,1}, GetGGT returns 1.
      37             : */
      38           0 : static long GetGGT( long nVal1, long nVal2 )
      39             : {
      40           0 :     nVal1 = std::abs( nVal1 );
      41           0 :     nVal2 = std::abs( nVal2 );
      42             : 
      43           0 :     if ( nVal1 <= 1 || nVal2 <= 1 )
      44           0 :         return 1;
      45             : 
      46           0 :     while ( nVal1 != nVal2 )
      47             :     {
      48           0 :         if ( nVal1 > nVal2 )
      49             :         {
      50           0 :             nVal1 %= nVal2;
      51           0 :             if ( nVal1 == 0 )
      52           0 :                 return nVal2;
      53             :         }
      54             :         else
      55             :         {
      56           0 :             nVal2 %= nVal1;
      57           0 :             if ( nVal2 == 0 )
      58           0 :                 return nVal1;
      59             :         }
      60             :     }
      61           0 :     return nVal1;
      62             : }
      63             : 
      64           0 : static void Reduce( BigInt &rVal1, BigInt &rVal2 )
      65             : {
      66           0 :     BigInt nA( rVal1 );
      67           0 :     BigInt nB( rVal2 );
      68           0 :     nA.Abs();
      69           0 :     nB.Abs();
      70             : 
      71           0 :     if ( nA.IsOne() || nB.IsOne() || nA.IsZero() || nB.IsZero() )
      72           0 :         return;
      73             : 
      74           0 :     while ( nA != nB )
      75             :     {
      76           0 :         if ( nA > nB )
      77             :         {
      78           0 :             nA %= nB;
      79           0 :             if ( nA.IsZero() )
      80             :             {
      81           0 :                 rVal1 /= nB;
      82           0 :                 rVal2 /= nB;
      83           0 :                 return;
      84             :             }
      85             :         }
      86             :         else
      87             :         {
      88           0 :             nB %= nA;
      89           0 :             if ( nB.IsZero() )
      90             :             {
      91           0 :                 rVal1 /= nA;
      92           0 :                 rVal2 /= nA;
      93           0 :                 return;
      94             :             }
      95             :         }
      96             :     }
      97             : 
      98           0 :     rVal1 /= nA;
      99           0 :     rVal2 /= nB;
     100             : }
     101             : 
     102             : // Initialized by setting nNum as nominator and nDen as denominator
     103             : // Negative values in the denominator are invalid and cause the
     104             : // inversion of both nominator and denominator signs
     105             : // in order to return the correct value.
     106           0 : Fraction::Fraction( long nNum, long nDen )
     107             : {
     108           0 :     nNumerator = nNum;
     109           0 :     nDenominator = nDen;
     110           0 :     if ( nDenominator < 0 )
     111             :     {
     112           0 :         nDenominator = -nDenominator;
     113           0 :         nNumerator   = -nNumerator;
     114             :     }
     115             : 
     116             :     // Reduce through GCD
     117           0 :     long n = GetGGT( nNumerator, nDenominator );
     118           0 :     nNumerator   /= n;
     119           0 :     nDenominator /= n;
     120           0 : }
     121             : 
     122             : // If dVal > LONG_MAX, the fraction is set as invalid.
     123             : // Otherwise, dVal and denominator are multiplied with 10, until one of them
     124             : // is larger than (LONG_MAX / 10) and the fraction is reduced with GCD
     125           0 : Fraction::Fraction( double dVal )
     126             : {
     127           0 :     long nDen = 1;
     128           0 :     long nMAX = LONG_MAX / 10;
     129             : 
     130           0 :     if ( dVal > LONG_MAX || dVal < LONG_MIN )
     131             :     {
     132           0 :         nNumerator   = 0;
     133           0 :         nDenominator = -1;
     134           0 :         return;
     135             :     }
     136             : 
     137           0 :     while ( std::abs( (long)dVal ) < nMAX && nDen < nMAX )
     138             :     {
     139           0 :         dVal *= 10;
     140           0 :         nDen *= 10;
     141             :     }
     142           0 :     nNumerator   = (long)dVal;
     143           0 :     nDenominator = nDen;
     144             : 
     145             :     // Reduce through GCD
     146           0 :     long n = GetGGT( nNumerator, nDenominator );
     147           0 :     nNumerator   /= n;
     148           0 :     nDenominator /= n;
     149             : }
     150             : 
     151           0 : Fraction::operator double() const
     152             : {
     153           0 :     if ( nDenominator > 0 )
     154           0 :         return (double)nNumerator / (double)nDenominator;
     155             :     else
     156           0 :         return (double)0;
     157             : }
     158             : 
     159             : // This methods first validates both values.
     160             : // If one of the arguments is invalid, the whole operation is invalid.
     161             : // For addition both fractions are extended to match the denominator,
     162             : // then nominators are added and reduced (through GCD).
     163             : // Internal datatype for computation is SLong to detect overflows,
     164             : // which cause the operation to be marked as invalid
     165           0 : Fraction& Fraction::operator += ( const Fraction& rVal )
     166             : {
     167           0 :     if ( !rVal.IsValid() )
     168             :     {
     169           0 :         nNumerator   = 0;
     170           0 :         nDenominator = -1;
     171             :     }
     172           0 :     if ( !IsValid() )
     173           0 :         return *this;
     174             : 
     175             :     // (a/b) + (c/d) = ( (a*d) + (c*b) ) / (b*d)
     176           0 :     BigInt nN( nNumerator );
     177           0 :     nN *= BigInt( rVal.nDenominator );
     178           0 :     BigInt nW1Temp( nDenominator );
     179           0 :     nW1Temp *= BigInt( rVal.nNumerator );
     180           0 :     nN += nW1Temp;
     181             : 
     182           0 :     BigInt nD( nDenominator );
     183           0 :     nD *= BigInt( rVal.nDenominator );
     184             : 
     185           0 :     Reduce( nN, nD );
     186             : 
     187           0 :     if ( nN.bIsBig || nD.bIsBig )
     188             :     {
     189           0 :         nNumerator   = 0;
     190           0 :         nDenominator = -1;
     191             :     }
     192             :     else
     193             :     {
     194           0 :         nNumerator   = (long)nN,
     195           0 :         nDenominator = (long)nD;
     196             :     }
     197             : 
     198           0 :     return *this;
     199             : }
     200             : 
     201             : // This methods first validates both values.
     202             : // If one of the arguments is invalid, the whole operation is invalid.
     203             : // For substraction, both fractions are extended to match the denominator,
     204             : // then nominators are substracted and reduced (through GCD).
     205             : // Internal datatype for computation is SLong to detect overflows,
     206             : // which cause the operation to be marked as invalid
     207           0 : Fraction& Fraction::operator -= ( const Fraction& rVal )
     208             : {
     209           0 :     if ( !rVal.IsValid() )
     210             :     {
     211           0 :         nNumerator   = 0;
     212           0 :         nDenominator = -1;
     213             :     }
     214           0 :     if ( !IsValid() )
     215           0 :         return *this;
     216             : 
     217             :     // (a/b) - (c/d) = ( (a*d) - (c*b) ) / (b*d)
     218           0 :     BigInt nN( nNumerator );
     219           0 :     nN *= BigInt( rVal.nDenominator );
     220           0 :     BigInt nW1Temp( nDenominator );
     221           0 :     nW1Temp *= BigInt( rVal.nNumerator );
     222           0 :     nN -= nW1Temp;
     223             : 
     224           0 :     BigInt nD( nDenominator );
     225           0 :     nD *= BigInt( rVal.nDenominator );
     226             : 
     227           0 :     Reduce( nN, nD );
     228             : 
     229           0 :     if ( nN.bIsBig || nD.bIsBig )
     230             :     {
     231           0 :         nNumerator   = 0;
     232           0 :         nDenominator = -1;
     233             :     }
     234             :     else
     235             :     {
     236           0 :         nNumerator   = (long)nN,
     237           0 :         nDenominator = (long)nD;
     238             :     }
     239             : 
     240           0 :     return *this;
     241             : }
     242             : 
     243             : // This methods first validates both values.
     244             : // If one of the arguments is invalid, the whole operation is invalid.
     245             : // For mutliplication, nominator and denominators are first reduced
     246             : // (through GCD), and then multiplied.
     247             : // Internal datatype for computation is BigInt to detect overflows,
     248             : // which cause the operation to be marked as invalid
     249           0 : Fraction& Fraction::operator *= ( const Fraction& rVal )
     250             : {
     251           0 :     if ( !rVal.IsValid() )
     252             :     {
     253           0 :         nNumerator   = 0;
     254           0 :         nDenominator = -1;
     255             :     }
     256           0 :     if ( !IsValid() )
     257           0 :         return *this;
     258             : 
     259           0 :     long nGGT1 = GetGGT( nNumerator, rVal.nDenominator );
     260           0 :     long nGGT2 = GetGGT( rVal.nNumerator, nDenominator );
     261           0 :     BigInt nN( nNumerator / nGGT1 );
     262           0 :     nN *= BigInt( rVal.nNumerator / nGGT2 );
     263           0 :     BigInt nD( nDenominator / nGGT2 );
     264           0 :     nD *= BigInt( rVal.nDenominator / nGGT1 );
     265             : 
     266           0 :     if ( nN.bIsBig || nD.bIsBig )
     267             :     {
     268           0 :         nNumerator   = 0;
     269           0 :         nDenominator = -1;
     270             :     }
     271             :     else
     272             :     {
     273           0 :         nNumerator   = (long)nN,
     274           0 :         nDenominator = (long)nD;
     275             :     }
     276             : 
     277           0 :     return *this;
     278             : }
     279             : 
     280             : // This methods first validates both values.
     281             : // If one of the arguments is invalid, the whole operation is invalid.
     282             : // For dividing a/b, we multiply a with the inverse of b.
     283             : // To avoid overflows, we first reduce both fractions with GCD.
     284             : // Internal datatype for computation is BigInt to detect overflows,
     285             : // which cause the operation to be marked as invalid
     286           0 : Fraction& Fraction::operator /= ( const Fraction& rVal )
     287             : {
     288           0 :     if ( !rVal.IsValid() )
     289             :     {
     290           0 :         nNumerator   = 0;
     291           0 :         nDenominator = -1;
     292             :     }
     293           0 :     if ( !IsValid() )
     294           0 :         return *this;
     295             : 
     296           0 :     long nGGT1 = GetGGT( nNumerator, rVal.nNumerator );
     297           0 :     long nGGT2 = GetGGT( rVal.nDenominator, nDenominator );
     298           0 :     BigInt nN( nNumerator / nGGT1 );
     299           0 :     nN *= BigInt( rVal.nDenominator / nGGT2 );
     300           0 :     BigInt nD( nDenominator / nGGT2 );
     301           0 :     nD *= BigInt( rVal.nNumerator / nGGT1 );
     302             : 
     303           0 :     if ( nN.bIsBig || nD.bIsBig )
     304             :     {
     305           0 :         nNumerator   = 0;
     306           0 :         nDenominator = -1;
     307             :     }
     308             :     else
     309             :     {
     310           0 :         nNumerator   = (long)nN,
     311           0 :         nDenominator = (long)nD;
     312           0 :         if ( nDenominator < 0 )
     313             :         {
     314           0 :             nDenominator = -nDenominator;
     315           0 :             nNumerator   = -nNumerator;
     316             :         }
     317             :     }
     318             : 
     319           0 :     return *this;
     320             : }
     321             : 
     322             : // Similar to clz_table that can be googled
     323             : const char nbits_table[32] =
     324             : {
     325             :     32,  1, 23,  2, 29, 24, 14,  3,
     326             :     30, 27, 25, 18, 20, 15, 10,  4,
     327             :     31, 22, 28, 13, 26, 17, 19,  9,
     328             :     21, 12, 16,  8, 11,  7,  6,  5
     329             : };
     330             : 
     331           0 : static int impl_NumberOfBits( unsigned long nNum )
     332             : {
     333             :     // http://en.wikipedia.org/wiki/De_Bruijn_sequence
     334             :     // background paper: Using de Bruijn Sequences to Index a 1 in a
     335             :     // Computer Word (1998) Charles E. Leiserson,
     336             :     // Harald Prokop, Keith H. Randall
     337             :     // (e.g. http://citeseer.ist.psu.edu/leiserson98using.html)
     338           0 :     const sal_uInt32 nDeBruijn = 0x7DCD629;
     339             : 
     340           0 :     if ( nNum == 0 )
     341           0 :         return 0;
     342             : 
     343             :     // Get it to form like 0000001111111111b
     344           0 :     nNum |= ( nNum >>  1 );
     345           0 :     nNum |= ( nNum >>  2 );
     346           0 :     nNum |= ( nNum >>  4 );
     347           0 :     nNum |= ( nNum >>  8 );
     348           0 :     nNum |= ( nNum >> 16 );
     349             : 
     350             :     sal_uInt32 nNumber;
     351           0 :     int nBonus = 0;
     352             : 
     353             : #if SAL_TYPES_SIZEOFLONG == 4
     354           0 :     nNumber = nNum;
     355             : #elif SAL_TYPES_SIZEOFLONG == 8
     356             :     nNum |= ( nNum >> 32 );
     357             : 
     358             :     if ( nNum & 0x80000000 )
     359             :     {
     360             :         nNumber = sal_uInt32( nNum >> 32 );
     361             :         nBonus = 32;
     362             : 
     363             :         if ( nNumber == 0 )
     364             :             return 32;
     365             :     }
     366             :     else
     367             :         nNumber = sal_uInt32( nNum & 0xFFFFFFFF );
     368             : #else
     369             : #error "Unknown size of long!"
     370             : #endif
     371             : 
     372             :     // De facto shift left of nDeBruijn using multiplication (nNumber
     373             :     // is all ones from topmost bit, thus nDeBruijn + (nDeBruijn *
     374             :     // nNumber) => nDeBruijn * (nNumber+1) clears all those bits to
     375             :     // zero, sets the next bit to one, and thus effectively shift-left
     376             :     // nDeBruijn by lg2(nNumber+1). This generates a distinct 5bit
     377             :     // sequence in the msb for each distinct position of the last
     378             :     // leading 0 bit - that's the property of a de Bruijn number.
     379           0 :     nNumber = nDeBruijn + ( nDeBruijn * nNumber );
     380             : 
     381             :     // 5-bit window indexes the result
     382           0 :     return ( nbits_table[nNumber >> 27] ) + nBonus;
     383             : }
     384             : 
     385             : /** Inaccurate cancellation for a fraction.
     386             : 
     387             :     Clip both nominator and denominator to said number of bits. If
     388             :     either of those already have equal or less number of bits used,
     389             :     this method does nothing.
     390             : 
     391             :     @param nSignificantBits denotes, how many significant binary
     392             :     digits to maintain, in both nominator and denominator.
     393             : 
     394             :     @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
     395             :     largest error occurs with the following pair of values:
     396             : 
     397             :     binary    1000000011111111111111111111111b/1000000000000000000000000000000b
     398             :     =         1082130431/1073741824
     399             :     = approx. 1.007812499
     400             : 
     401             :     A ReduceInaccurate(8) yields 1/1.
     402             : */
     403           0 : void Fraction::ReduceInaccurate( unsigned nSignificantBits )
     404             : {
     405           0 :     if ( !nNumerator || !nDenominator )
     406           0 :         return;
     407             : 
     408             :     // Count with unsigned longs only
     409           0 :     const bool bNeg = ( nNumerator < 0 );
     410           0 :     unsigned long nMul = (unsigned long)( bNeg? -nNumerator: nNumerator );
     411           0 :     unsigned long nDiv = (unsigned long)( nDenominator );
     412             : 
     413             :     DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!");
     414             : 
     415             :     // How much bits can we lose?
     416           0 :     const int nMulBitsToLose = std::max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 );
     417           0 :     const int nDivBitsToLose = std::max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 );
     418             : 
     419           0 :     const int nToLose = std::min( nMulBitsToLose, nDivBitsToLose );
     420             : 
     421             :     // Remove the bits
     422           0 :     nMul >>= nToLose;
     423           0 :     nDiv >>= nToLose;
     424             : 
     425           0 :     if ( !nMul || !nDiv )
     426             :     {
     427             :         // Return without reduction
     428             :         OSL_FAIL( "Oops, we reduced too much..." );
     429           0 :         return;
     430             :     }
     431             : 
     432             :     // Reduce
     433           0 :     long n1 = GetGGT( nMul, nDiv );
     434           0 :     if ( n1 != 1 )
     435             :     {
     436           0 :         nMul /= n1;
     437           0 :         nDiv /= n1;
     438             :     }
     439             : 
     440           0 :     nNumerator = bNeg? -long( nMul ): long( nMul );
     441           0 :     nDenominator = nDiv;
     442             : }
     443             : 
     444           0 : bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )
     445             : {
     446           0 :     if ( !rVal1.IsValid() || !rVal2.IsValid() )
     447           0 :         return false;
     448             : 
     449           0 :     return rVal1.nNumerator == rVal2.nNumerator
     450           0 :            && rVal1.nDenominator == rVal2.nDenominator;
     451             : }
     452             : 
     453             : // This methods first validates and reduces both values.
     454             : // To compare (a/b) with (c/d), extend denominators (b*d), then return
     455             : // the result of comparing the nominators (a < c)
     456           0 : bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )
     457             : {
     458           0 :     if ( !rVal1.IsValid() || !rVal2.IsValid() )
     459           0 :         return false;
     460             : 
     461           0 :     BigInt nN( rVal1.nNumerator );
     462           0 :     nN *= BigInt( rVal2.nDenominator );
     463           0 :     BigInt nD( rVal1.nDenominator );
     464           0 :     nD *= BigInt( rVal2.nNumerator );
     465             : 
     466           0 :     return nN < nD;
     467             : }
     468             : 
     469             : // This methods first validates and reduces both values.
     470             : // To compare (a/b) with (c/d), extend denominators (b*d), then return
     471             : // the result of comparing nominators (a > c)
     472           0 : bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )
     473             : {
     474           0 :     if ( !rVal1.IsValid() || !rVal2.IsValid() )
     475           0 :         return false;
     476             : 
     477           0 :     BigInt nN( rVal1.nNumerator );
     478           0 :     nN *= BigInt( rVal2.nDenominator );
     479           0 :     BigInt nD( rVal1.nDenominator);
     480           0 :     nD *= BigInt( rVal2.nNumerator );
     481             : 
     482           0 :     return nN > nD;
     483             : }
     484             : 
     485           0 : SvStream& ReadFraction( SvStream& rIStream, Fraction& rFract )
     486             : {
     487             :     //fdo#39428 SvStream no longer supports operator>>(long&)
     488           0 :     sal_Int32 nTmp(0);
     489           0 :     rIStream.ReadInt32( nTmp );
     490           0 :     rFract.nNumerator = nTmp;
     491           0 :     rIStream.ReadInt32( nTmp );
     492           0 :     rFract.nDenominator = nTmp;
     493           0 :     return rIStream;
     494             : }
     495             : 
     496           0 : SvStream& WriteFraction( SvStream& rOStream, const Fraction& rFract )
     497             : {
     498             :     //fdo#39428 SvStream no longer supports operator<<(long)
     499           0 :     rOStream.WriteInt32( sal::static_int_cast<sal_Int32>(rFract.nNumerator) );
     500           0 :     rOStream.WriteInt32( sal::static_int_cast<sal_Int32>(rFract.nDenominator) );
     501           0 :     return rOStream;
     502             : }
     503             : 
     504             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10