/* -*- 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 <tools/fract.hxx>

#include <tools/debug.hxx>

#include <o3tl/hash_combine.hxx>

#include <o3tl/numeric.hxx>

#include <o3tl/safeint.hxx>

#include <sal/log.hxx>

#include <osl/diagnose.h>

#include <algorithm>

#include <bit>

#include <cmath>

#include <numeric>

#include <boost/rational.hpp>

static boost::rational<sal_Int32> rational_FromDouble(double dVal);

static void rational_ReduceInaccurate(boost::rational<sal_Int32>& rRational, unsigned nSignificantBits);

// Find the number of bits required to represent this number

static int impl_NumberOfBits(sal_uInt32 nNum) { return o3tl::number_of_bits(nNum); }

static boost::rational<sal_Int32> toRational(sal_Int32 n, sal_Int32 d)

{

    // https://github.com/boostorg/boost/issues/335 when these are std::numeric_limits<sal_Int32>::min

    if (n == d)

        return 1;

    // tdf#144319 avoid boost::bad_rational e.g. if numerator=-476741369, denominator=-2147483648

    if (d < -std::numeric_limits<sal_Int32>::max())

        return 0;

    return boost::rational<sal_Int32>(n, d);

}

static constexpr bool isOutOfRange(sal_Int64 nNum)

{

    return nNum < std::numeric_limits<sal_Int32>::min()

            || nNum > std::numeric_limits<sal_Int32>::max();

}

Fraction::Fraction( sal_Int64 nNum, sal_Int64 nDen ) : mnNumerator(nNum), mnDenominator(nDen)

{

    if ( isOutOfRange(nNum) || isOutOfRange(nDen) )

    {

        // tdf#143200

        if (const auto gcd = std::gcd(nNum, nDen); gcd > 1)

        {

            nNum /= gcd;

            nDen /= gcd;

        }

        SAL_WARN_IF(isOutOfRange(nNum) || isOutOfRange(nDen),

                    "tools.fraction", "values outside of range we can represent, doing reduction, which will reduce precision");

        while (isOutOfRange(nNum) || isOutOfRange(nDen))

        {

            nNum /= 2;

            nDen /= 2;

        }

        mnNumerator = nNum;

        mnDenominator = nDen;

    }

    if ( mnDenominator == 0 )

    {

        mbValid = false;

        SAL_WARN( "tools.fraction", "'Fraction(" << nNum << ",0)' invalid fraction created" );

        return;

    }

    else if ((nDen == -1 && nNum == std::numeric_limits<sal_Int32>::min()) ||

            (nNum == -1 && nDen == std::numeric_limits<sal_Int32>::min()))

    {

        mbValid = false;

        SAL_WARN("tools.fraction", "'Fraction(" << nNum << "," << nDen << ")' invalid fraction created");

        return;

    }

}

/**

 * only here to prevent passing of NaN

 */

Fraction::Fraction( double nNum, double nDen )

    : Fraction(sal_Int64(nNum), sal_Int64(nDen))

{}

Fraction::Fraction( double dVal )

{

    try

    {

        boost::rational<sal_Int32> v = rational_FromDouble( dVal );

        mnNumerator = v.numerator();

        mnDenominator = v.denominator();

    }

    catch (const boost::bad_rational&)

    {

        mbValid = false;

        SAL_WARN( "tools.fraction", "'Fraction(" << dVal << ")' invalid fraction created" );

    }

}

Fraction::operator double() const

{

    if (!mbValid)

    {

        SAL_WARN( "tools.fraction", "'double()' on invalid fraction" );

        return std::numeric_limits<double>::quiet_NaN();

    }

    return boost::rational_cast<double>(toRational(mnNumerator, mnDenominator));

}

// This methods first validates both values.

// If one of the arguments is invalid, the whole operation is invalid.

// After computation detect if result overflows a sal_Int32 value

// which cause the operation to be marked as invalid

Fraction& Fraction::operator += ( const Fraction& rVal )

{

    if ( !rVal.mbValid )

        mbValid = false;

    if ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator +=' with invalid fraction" );

        return *this;

    }

    boost::rational<sal_Int32> a = toRational(mnNumerator, mnDenominator);

    a += toRational(rVal.mnNumerator, rVal.mnDenominator);

    mnNumerator = a.numerator();

    mnDenominator = a.denominator();

    return *this;

}

Fraction& Fraction::operator -= ( const Fraction& rVal )

{

    if ( !rVal.mbValid )

        mbValid = false;

    if ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator -=' with invalid fraction" );

        return *this;

    }

    boost::rational<sal_Int32> a = toRational(mnNumerator, mnDenominator);

    a -= toRational(rVal.mnNumerator, rVal.mnDenominator);

    mnNumerator = a.numerator();

    mnDenominator = a.denominator();

    return *this;

}

namespace

{

    bool checked_multiply_by(boost::rational<sal_Int32>& i, const boost::rational<sal_Int32>& r)

    {

        // Protect against self-modification

        sal_Int32 num = r.numerator();

        sal_Int32 den = r.denominator();

        // Fast-path if the number of bits in input is < the number of bits in the output, overflow cannot happen

        // This is considerably faster than repeated std::gcd() operations

        if ((impl_NumberOfBits(std::abs(i.numerator())) + impl_NumberOfBits(std::abs(r.numerator()))) < 32 &&

            (impl_NumberOfBits(std::abs(i.denominator())) + impl_NumberOfBits(std::abs(r.denominator()))) < 32)

        {

            i *= r;

            return false;

        }

        // Avoid overflow and preserve normalization

        sal_Int32 gcd1 = std::gcd(i.numerator(), den);

        sal_Int32 gcd2 = std::gcd(num, i.denominator());

        if (!gcd1 || !gcd2)

            return true;

        bool fail = false;

        fail |= o3tl::checked_multiply(i.numerator() / gcd1, num / gcd2, num);

        fail |= o3tl::checked_multiply(i.denominator() / gcd2, den / gcd1, den);

        if (!fail)

            i.assign(num, den);

        return fail;

    }

}

Fraction& Fraction::operator *= ( const Fraction& rVal )

{

    if ( !rVal.mbValid )

        mbValid = false;

    if ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator *=' with invalid fraction" );

        return *this;

    }

    boost::rational<sal_Int32> a = toRational(mnNumerator, mnDenominator);

    boost::rational<sal_Int32> b = toRational(rVal.mnNumerator, rVal.mnDenominator);

    bool bFail = checked_multiply_by(a, b);

    mnNumerator = a.numerator();

    mnDenominator = a.denominator();

    if (bFail)

    {

        mbValid = false;

    }

    return *this;

}

Fraction& Fraction::operator /= ( const Fraction& rVal )

{

    if ( !rVal.mbValid )

        mbValid = false;

    if ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator /=' with invalid fraction" );

        return *this;

    }

    boost::rational<sal_Int32> a = toRational(mnNumerator, mnDenominator);

    a /= toRational(rVal.mnNumerator, rVal.mnDenominator);

    mnNumerator = a.numerator();

    mnDenominator = a.denominator();

    return *this;

}

/** 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 ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'ReduceInaccurate' on invalid fraction" );

        return;

    }

    if ( !mnNumerator )

        return;

    auto a = toRational(mnNumerator, mnDenominator);

    rational_ReduceInaccurate(a, nSignificantBits);

    mnNumerator = a.numerator();

    mnDenominator = a.denominator();

}

sal_Int32 Fraction::GetNumerator() const

{

    if ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'GetNumerator()' on invalid fraction" );

        return 0;

    }

    return mnNumerator;

}

sal_Int32 Fraction::GetDenominator() const

{

    if ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'GetDenominator()' on invalid fraction" );

        return -1;

    }

    return mnDenominator;

}

Fraction::operator sal_Int32() const

{

    if ( !mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator sal_Int32()' on invalid fraction" );

        return 0;

    }

    return boost::rational_cast<sal_Int32>(toRational(mnNumerator, mnDenominator));

}

Fraction operator+( const Fraction& rVal1, const Fraction& rVal2 )

{

    Fraction aErg( rVal1 );

    aErg += rVal2;

    return aErg;

}

Fraction operator-( const Fraction& rVal1, const Fraction& rVal2 )

{

    Fraction aErg( rVal1 );

    aErg -= rVal2;

    return aErg;

}

Fraction operator*( const Fraction& rVal1, const Fraction& rVal2 )

{

    Fraction aErg( rVal1 );

    aErg *= rVal2;

    return aErg;

}

Fraction operator/( const Fraction& rVal1, const Fraction& rVal2 )

{

    Fraction aErg( rVal1 );

    aErg /= rVal2;

    return aErg;

}

bool operator !=( const Fraction& rVal1, const Fraction& rVal2 )

{

    return !(rVal1 == rVal2);

}

bool operator <=( const Fraction& rVal1, const Fraction& rVal2 )

{

    return !(rVal1 > rVal2);

}

bool operator >=( const Fraction& rVal1, const Fraction& rVal2 )

{

    return !(rVal1 < rVal2);

}

bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )

{

    if ( !rVal1.mbValid || !rVal2.mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator ==' with an invalid fraction" );

        return false;

    }

    return toRational(rVal1.mnNumerator, rVal1.mnDenominator) == toRational(rVal2.mnNumerator, rVal2.mnDenominator);

}

bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )

{

    if ( !rVal1.mbValid || !rVal2.mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator <' with an invalid fraction" );

        return false;

    }

    return toRational(rVal1.mnNumerator, rVal1.mnDenominator) < toRational(rVal2.mnNumerator, rVal2.mnDenominator);

}

bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )

{

    if ( !rVal1.mbValid || !rVal2.mbValid )

    {

        SAL_WARN( "tools.fraction", "'operator >' with an invalid fraction" );

        return false;

    }

    return toRational(rVal1.mnNumerator, rVal1.mnDenominator) > toRational(rVal2.mnNumerator, rVal2.mnDenominator);

}

// If dVal > LONG_MAX or dVal < LONG_MIN, the rational throws a boost::bad_rational.

// Otherwise, dVal and denominator are multiplied by 10, until one of them

// is larger than (LONG_MAX / 10).

//

// NOTE: here we use 'sal_Int32' due that only values in sal_Int32 range are valid.

static boost::rational<sal_Int32> rational_FromDouble(double dVal)

{

    if ( dVal > std::numeric_limits<sal_Int32>::max() ||

         dVal < std::numeric_limits<sal_Int32>::min() ||

         std::isnan(dVal) )

        throw boost::bad_rational();

    const sal_Int32 nMAX = std::numeric_limits<sal_Int32>::max() / 10;

    sal_Int32 nDen = 1;

    while ( std::abs( dVal ) < nMAX && nDen < nMAX ) {

        dVal *= 10;

        nDen *= 10;

    }

    return boost::rational<sal_Int32>( sal_Int32(dVal), nDen );

}

/** 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.

*/

static void rational_ReduceInaccurate(boost::rational<sal_Int32>& rRational, unsigned nSignificantBits)

{

    if ( !rRational )

        return;

    // http://www.boost.org/doc/libs/release/libs/rational/rational.html#Internal%20representation

    sal_Int32 nMul = rRational.numerator();

    if (nMul == std::numeric_limits<sal_Int32>::min())

    {

        // ofz#32973 Integer-overflow

        return;

    }

    const bool bNeg = nMul < 0;

    if (bNeg)

        nMul = -nMul;

    sal_Int32 nDiv = 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 ? -nMul : nMul, nDiv );

}

size_t Fraction::GetHashValue() const

{

    size_t hash = 0;

    o3tl::hash_combine( hash, mnNumerator );

    o3tl::hash_combine( hash, mnDenominator );

    o3tl::hash_combine( hash, mbValid );

    return hash;

}

Fraction Fraction::MakeFraction( tools::Long nN1, tools::Long nN2, tools::Long nD1, tools::Long nD2 )

{

    if( nD1 == 0 || nD2 == 0 ) //under these bad circumstances the following while loop will be endless

    {

        SAL_WARN("tools.fraction", "Invalid parameter for ImplMakeFraction");

        return Fraction( 1, 1 );

    }

    tools::Long i = 1;

    if ( nN1 < 0 ) { i = -i; nN1 = -nN1; }

    if ( nN2 < 0 ) { i = -i; nN2 = -nN2; }

    if ( nD1 < 0 ) { i = -i; nD1 = -nD1; }

    if ( nD2 < 0 ) { i = -i; nD2 = -nD2; }

    // all positive; i sign

    assert( nN1 >= std::numeric_limits<sal_Int32>::min() );

    assert( nN1 <= std::numeric_limits<sal_Int32>::max( ));

    assert( nD1 >= std::numeric_limits<sal_Int32>::min() );

    assert( nD1 <= std::numeric_limits<sal_Int32>::max( ));

    assert( nN2 >= std::numeric_limits<sal_Int32>::min() );

    assert( nN2 <= std::numeric_limits<sal_Int32>::max( ));

    assert( nD2 >= std::numeric_limits<sal_Int32>::min() );

    assert( nD2 <= std::numeric_limits<sal_Int32>::max( ));

    boost::rational<sal_Int32> a = toRational(i*nN1, nD1);

    boost::rational<sal_Int32> b = toRational(nN2, nD2);

    bool bFail = checked_multiply_by(a, b);

    while ( bFail ) {

        if ( nN1 > nN2 )

            nN1 = (nN1 + 1) / 2;

        else

            nN2 = (nN2 + 1) / 2;

        if ( nD1 > nD2 )

            nD1 = (nD1 + 1) / 2;

        else

            nD2 = (nD2 + 1) / 2;

        a = toRational(i*nN1, nD1);

        b = toRational(nN2, nD2);

        bFail = checked_multiply_by(a, b);

    }

    return Fraction(a.numerator(), a.denominator());

}

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */