/*             ----> DO NOT REMOVE THE FOLLOWING NOTICE <----

                   Copyright (c) 2014-2015 Datalight, Inc.
                       All Rights Reserved Worldwide.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; use version 2 of the License.

    This program is distributed in the hope that it will be useful,
    but "AS-IS," WITHOUT ANY WARRANTY; without even the implied warranty
    of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
/*  Businesses and individuals that for commercial or other reasons cannot
    comply with the terms of the GPLv2 license may obtain a commercial license
    before incorporating Reliance Edge into proprietary software for
    distribution in any form.  Visit http://www.datalight.com/reliance-edge for
    more information.
*/
/** @file
    @brief Implements routines for certain 64-bit math operations and simulated
           floating point.

    RedUint64DivMod32() and RedUint64DivMod64() are derived from code at
    http://www.hackersdelight.org.  This web site states explicitly that "You
    are free to use, copy, and distribute any of the code on this web site,
    whether modified by you or not.  You need not give attribution."
*/
#include <redfs.h>
#include <redtestutils.h>


static uint32_t nlz64(uint64_t ullValue);


/** @brief Return a ratio value formatted as a floating point string accurate to
           the specified number of decimal places.

    The  function exists to provide floating point style output without using
    any actual floating point types.

    This function may scale the numbers down to avoid overflow at the high end.
    Likewise, potential divide-by-zero errors are internally avoided.  Here are
    some examples:

    Dividend | Divisor | DecPlaces | Result
    -------- | ------- | --------- | ------
    12133    | 28545   | 2         | "0.42"
    1539     | 506     | 2         | "3.04"

    To get a number formatted as a percentage, take the take the portion of the
    total (normally the smaller part), multiply it by 100, and pass it to this
    function as the Dividend, pass the "total" value to this function as the
    Divisor, and specify the desired number of decimal places.

    For example, if you have a disk format overhead value of N blocks out of a
    total of Y blocks on the disk, and you want to display the format overhead
    as a percentage, you would use a function call
    similar to:

    ~~~{.c}
    RedRatio(szBuffer, sizeof(szBuffer), N*100U, Y, 2U);
    ~~~

    If N=145, Y=4096, and decimal places is 2, the resulting output would be
    "3.54".

    The string returned will always be null-terminated, even if it means
    stomping on the least significant decimal digit.

    If either the dividend or divisor values are zero, the string "0.0" will be
    returned, with the prescribed number of decimal places.

    @note This function has "reasonable" limits which meet the needs of the
          various supplemental utilities which use this function.  Extremely
          large ratios, or using many decimal places may not function as
          desired.

    Parameters:
    @param pBuffer      A pointer to the buffer in which to store the null
                        terminated results.
    @param ulBufferLen  The length of the output buffer.
    @param ullDividend  The "total" value to divide.
    @param ullDivisor   The portion of ullDividend for which to calculate the
                        ratio (may be greater than ulDividend).
    @param ulDecPlaces  The number of decimal places to use, from 0 to 9.

    @return @p pBuffer.
*/
char *RedRatio(
    char       *pBuffer,
    uint32_t    ulBufferLen,
    uint64_t    ullDividend,
    uint64_t    ullDivisor,
    uint32_t    ulDecPlaces)
{
    REDASSERT(pBuffer != NULL);
    REDASSERT(ulBufferLen > 0U);
    REDASSERT(ulDecPlaces <= 9U);   /* arbitrary */

    if((ullDivisor > 0U) && (ullDividend > 0U))
    {
        uint32_t    ii;
        uint32_t    ulFactor = 1U;
        uint64_t    ullDecimal;
        uint64_t    ullTemp;

        for(ii = 1U; ii <= ulDecPlaces; ii++)
        {
            ulFactor *= 10U;
        }

        ullDecimal = RedMulDiv64(ullDividend, ulFactor, ullDivisor);

        /*  Shouldn't really be calling this function in a situation where we
            can overflow at this point...
        */
        REDASSERT(ullDecimal != UINT64_MAX);

        if(ullDivisor <= ullDividend)
        {
            uint32_t ulDecimal;

            (void)RedUint64DivMod32(ullDecimal, ulFactor, &ulDecimal);
            ullDecimal = ulDecimal;
        }

        ullTemp = RedUint64DivMod64(ullDividend, ullDivisor, NULL);

        if(ulDecPlaces > 0U)
        {
            RedSNPrintf(pBuffer, ulBufferLen, "%llu.%0*llu", (unsigned long long)ullTemp,
                (unsigned)ulDecPlaces, (unsigned long long)ullDecimal);
        }
        else
        {
            RedSNPrintf(pBuffer, ulBufferLen, "%llu", (unsigned long long)ullTemp);
        }
    }
    else
    {
        /*  If either the dividend or divisor is zero, then just output a "0.0"
            string with the prescribed number of decimal places.
        */
        if(ulDecPlaces > 0U)
        {
            RedSNPrintf(pBuffer, ulBufferLen, "0.%0*u", (unsigned)ulDecPlaces, 0U);
        }
        else
        {
            RedStrNCpy(pBuffer, "0", ulBufferLen);
        }
    }

    /*  Ensure the returned buffer is always null-terminated
    */
    pBuffer[ulBufferLen - 1U] = '\0';

    return pBuffer;
}


/** @brief Multiply 64-bit and 32-bit numbers, and divide by a 64-bit number,
           returning a 64-bit result.

    @note This function may return an approximate value if multiplying
          @p ullBase and @p ulMultplier results in a number larger than 64-bits
          _and_ this cannot be avoided by scaling.

    @param ullBase      The base 64-bit number number.
    @param ulMultiplier The 32-bit number by which to multiply.
    @param ullDivisor   The 64-bit number by which to divide.

    @return The 64-bit unsigned integer result.  Always returns zero if either
            @p ullBase or @p ulMultiplier are zero (regardless what
            @p ullDivisor is).  Returns UINT64_MAX if an overflow condition
            occurred, or if @p ullDivisor is zero.
*/
uint64_t RedMulDiv64(
    uint64_t ullBase,
    uint32_t ulMultiplier,
    uint64_t ullDivisor)
{
    uint64_t ullTemp;

    /*  Result would always be zero if either of these are zero.  Specifically
        test this case before looking for a zero divisor.
    */
    if((ullBase == 0U) || (ulMultiplier == 0U))
    {
        return 0U;
    }

    if(ullDivisor == 0U)
    {
        return UINT64_MAX;
    }

    /*  Since we don't have the ability (yet) to use 128-bit numbers, we jump
        through the following hoops (in order) to try to determine the proper
        results without losing precision:

        1) Shift the divisor and one of the multiplicands as many times as is
           necessary to reduce the scale -- only if it can be done without
           losing precision.
        2) Divide one of the multiplicands by the divisor first, but only if it
           divides evenly, preserving precision.
        3) Same as #2, but try it for the other multiplicand.
        4) Last ditch, divide the larger multiplicand by the divisor first, then
           do the multiply.  This <WILL> lose precision.

        These solutions are identified as CODE-PATHs #1-4 which are used to
        identify the matching tests in dltmain.c.

        Note that execution might partially include CODE-PATH #1 up until
        shifting can no longer be done without losing precision.  In that case,
        one of the three remaining options will be used.
    */

    ullTemp = RedUint64DivMod32(UINT64_MAX, ulMultiplier, NULL);
    while(ullBase > ullTemp)
    {
        uint64_t ullMod;
        uint64_t ullBaseTemp;
        uint64_t ullWideMultiplier;

        /*  CODE-PATH #1
        */
        /*  So long as ulDivisor, and at least one of the other numbers, are
            evenly divisible by 2, we can scale the numbers so the result does
            not overflow the intermediate 64-bit value.
        */
        if((ullDivisor & 1U) == 0U)
        {
            if((ullBase & 1U) == 0U)
            {
                /*  CODE-PATH #1a
                */
                ullDivisor >>= 1U;
                ullBase >>= 1U;
                continue;
            }

            if(((ulMultiplier & 1U) == 0U) && ((ullTemp & UINT64_SUFFIX(0x8000000000000000)) == 0U))
            {
                /*  CODE-PATH #1b
                */
                ullDivisor >>= 1U;
                ulMultiplier >>= 1U;
                ullTemp <<= 1U;
                continue;
            }
        }

        /*  If we get to this point, the above method (#1) cannot be used
            because not enough of the numbers are even long enough to scale the
            operands down.  We'll see if either multiplicand is evenly divisble
            by ulDivisor, and if so, do the divide first, then the multiply.
            (Note that once we get to this point, we will never exercise the
            while{} loop anymore.)
        */

        /*  CODE-PATH #2
        */
        ullBaseTemp = RedUint64DivMod64(ullBase, ullDivisor, &ullMod);
        if(ullMod == 0U)
        {
            /*  Evenly divides, so check that we won't overflow, and finish up.
            */
            ullBase = ullBaseTemp;
            if(ullBase > ullTemp)
            {
                return UINT64_MAX;
            }
            else
            {
                /*  We've validated that this will not overflow.
                */
                ullBase *= ulMultiplier;
                return ullBase;
            }
        }

        /*  CODE-PATH #3
        */
        ullWideMultiplier = RedUint64DivMod64(ulMultiplier, ullDivisor, &ullMod);
        if(ullMod == 0U)
        {
            /*  Evenly divides, so check that we won't overflow, and finish up.
            */

            /*  Must recalculate ullTemp relative to ullBase
            */
            ullTemp = RedUint64DivMod64(UINT64_MAX, ullBase, NULL);
            if(ullWideMultiplier > ullTemp)
            {
                return UINT64_MAX;
            }
            else
            {
                uint32_t ulNarrowMultiplier = (uint32_t)ullWideMultiplier;

                /*  We've validated that this will not overflow.
                */
                ullBase *= ulNarrowMultiplier;
                return ullBase;
            }
        }

        /*  CODE-PATH #4

            Neither of the multipliers is evenly divisible by the divisor, so
            just punt and divide the larger number first, then do the final
            multiply.

            All the other attempts above would preserve precision -- this is the
            only case where precision may be lost.
        */

        /*  If necessary reverse the ullBase and ulMultiplier operands so that
            ullBase contains the larger of the two values.
        */
        if(ullBase < ulMultiplier)
        {
            uint32_t ulTemp = ulMultiplier;

            ulMultiplier = (uint32_t)ullBase;
            ullBase = ulTemp;
        }

        ullBase = RedUint64DivMod64(ullBase, ullDivisor, NULL);
        ullTemp = RedUint64DivMod32(UINT64_MAX, ulMultiplier, NULL);
        if(ullBase > ullTemp)
        {
            return UINT64_MAX;
        }
        else
        {
            ullBase *= ulMultiplier;
            return ullBase;
        }
    }

    /*  We only get to this point if either there was never any chance of
        overflow, or if the pure shifting mechanism succeeded in reducing
        the scale so overflow is not a problem.
    */

    ullBase *= ulMultiplier;
    ullBase = RedUint64DivMod64(ullBase, ullDivisor, NULL);

    return ullBase;
}


/** @brief Divide a 64-bit value by a 32-bit value, returning the quotient and
           the remainder.

    Essentially this function does the following:

    ~~~{.c}
    if(pulRemainder != NULL)
    {
        *pulRemainder = (uint32_t)(ullDividend % ulDivisor);
    }
    return ullDividend / ulDivisor;
    ~~~

    However, it does so without ever actually dividing/modulating a 64-bit
    value, since such operations are not allowed in all environments.

    @param ullDividend  The value to divide.
    @param ulDivisor    The value to divide by.
    @param pulRemainder Populated with the remainder; may be NULL.

    @return The quotient (result of the division).
*/
uint64_t RedUint64DivMod32(
    uint64_t    ullDividend,
    uint32_t    ulDivisor,
    uint32_t   *pulRemainder)
{
    uint64_t    ullQuotient;
    uint32_t    ulResultRemainder;

    /*  Check for divide by zero.
    */
    if(ulDivisor == 0U)
    {
        REDERROR();

        /*  Nonsense value if no asserts.
        */
        ullQuotient = UINT64_SUFFIX(0xFFFFFFFFFFFFFBAD);
        ulResultRemainder = 0xFFFFFBADU;
    }
    else if(ullDividend <= UINT32_MAX)
    {
        uint32_t ulDividend = (uint32_t)ullDividend;

        ullQuotient = ulDividend / ulDivisor;
        ulResultRemainder = ulDividend % ulDivisor;
    }
    else
    {
        uint32_t    ulResultHi;
        uint32_t    ulResultLo;
        uint32_t    ulRemainder;
        uint8_t     bIndex;
        uint32_t    ulThisDivision;
        uint32_t    ulMask;
        uint8_t     ucNextValue;
        uint32_t    ulInterimHi, ulInterimLo;
        uint32_t    ulLowDword = (uint32_t)ullDividend;
        uint32_t    ulHighDword = (uint32_t)(ullDividend >> 32U);

        /*  Compute the high part and get the remainder
        */
        ulResultHi = ulHighDword / ulDivisor;
        ulResultLo = 0U;
        ulRemainder = ulHighDword % ulDivisor;

        /*  Compute the low part
        */
        ulMask = 0xFF000000U;
        for(bIndex = 0U; bIndex < sizeof(uint32_t); bIndex++)
        {
            ucNextValue = (uint8_t)((ulLowDword & ulMask) >> ((sizeof(uint32_t) - 1U - bIndex) * 8U));
            ulInterimHi = ulRemainder >> 24U;
            ulInterimLo = (ulRemainder << 8U) | ucNextValue;
            ulThisDivision = 0U;
            while(ulInterimHi != 0U)
            {
                uint64_t ullInterim = ((uint64_t)ulInterimHi << 32U) + ulInterimLo;

                ullInterim -= ulDivisor;
                ulThisDivision++;

                ulInterimHi = (uint32_t)(ullInterim >> 32U);
                ulInterimLo = (uint32_t)ullInterim;
            }
            ulThisDivision += ulInterimLo / ulDivisor;
            ulRemainder = ulInterimLo % ulDivisor;
            ulResultLo <<= 8U;
            ulResultLo += ulThisDivision;
            ulMask >>= 8U;
        }

        ullQuotient = ((uint64_t)ulResultHi << 32U) + ulResultLo;
        ulResultRemainder = (uint32_t)(ullDividend - (ullQuotient * ulDivisor));
    }

    if(pulRemainder != NULL)
    {
        *pulRemainder = ulResultRemainder;
    }

    return ullQuotient;
}


/** @brief Divide a 64-bit value by a 64-bit value, returning the quotient and
           the remainder.

    Essentially this function does the following:

    ~~~{.c}
    if(pullRemainder != NULL)
    {
        *pullRemainder = ullDividend % ullDivisor;
    }
    return ullDividend / ullDivisor;
    ~~~

    However, it does so without ever actually dividing/modulating a 64-bit
    value, since such operations are not allowed in all environments.

    @param ullDividend   The value to divide.
    @param ullDivisor    The value to divide by.
    @param pullRemainder Populated with the remainder; may be NULL.

    @return The quotient (result of the division).
*/
uint64_t RedUint64DivMod64(
    uint64_t    ullDividend,
    uint64_t    ullDivisor,
    uint64_t   *pullRemainder)
{
    /*  The variables u0, u1, etc. take on only 32-bit values, but they are
        declared uint64_t to avoid some compiler warning messages and to avoid
        some unnecessary EXTRs that the compiler would put in, to convert
        uint64_ts to ints.
    */
    uint64_t    u0;
    uint64_t    u1;
    uint64_t    q0;
    uint64_t    q1;
    uint64_t    ullQuotient;

    /*  First the procedure takes care of the case in which the divisor is a
        32-bit quantity.  There are two subcases: (1) If the left half of the
        dividend is less than the divisor, one execution of RedUint64DivMod32()
        is all that is required (overflow is not possible). (2) Otherwise it
        does two divisions, using the grade school method.
    */

    if((ullDivisor >> 32U) == 0U)
    {
        if((ullDividend >> 32U) < ullDivisor)
        {
            /*  If ullDividend/ullDivisor cannot overflow, just do one division.
            */
            ullQuotient = RedUint64DivMod32(ullDividend, (uint32_t)ullDivisor, NULL);
        }
        else
        {
            uint32_t k;

            /*  If ullDividend/ullDivisor would overflow:
            */

            /*  Break ullDividend up into two halves.
            */
            u1 = ullDividend >> 32U;
            u0 = ullDividend & 0xFFFFFFFFU;

            /*  First quotient digit and first remainder.
            */
            q1 = RedUint64DivMod32(u1, (uint32_t)ullDivisor, &k);

            /*  2nd quot. digit.
            */
            q0 = RedUint64DivMod32(((uint64_t)k << 32U) + u0, (uint32_t)ullDivisor, NULL);

            ullQuotient = (q1 << 32U) + q0;
        }
    }
    else
    {
        uint64_t n;
        uint64_t v1;

        n = nlz64(ullDivisor);          /* 0 <= n <= 31. */
        v1 = (ullDivisor << n) >> 32U;  /* Normalize the divisor so its MSB is 1. */
        u1 = ullDividend >> 1U;         /* To ensure no overflow. */

        /*  Get quotient from divide unsigned insn.
        */
        q1 = RedUint64DivMod32(u1, (uint32_t)v1, NULL);

        q0 = (q1 << n) >> 31U;  /* Undo normalization and division of ullDividend by 2. */

        /*  Make q0 correct or too small by 1.
        */
        if(q0 != 0U)
        {
            q0--;
        }

        if((ullDividend - (q0 * ullDivisor)) >= ullDivisor)
        {
            q0++;   /* Now q0 is correct. */
        }

        ullQuotient = q0;
    }

    if(pullRemainder != NULL)
    {
        *pullRemainder = ullDividend - (ullQuotient * ullDivisor);
    }

    return ullQuotient;
}


/** @brief Compute the number of leading zeroes in a 64-bit value.

    @param ullValue The value for which to compute the NLZ.

    @return The number of leading zeroes in @p ullValue.
*/
static uint32_t nlz64(
    uint64_t    ullValue)
{
    uint32_t    n;

    if(ullValue == 0U)
    {
        n = 64U;
    }
    else
    {
        uint64_t x = ullValue;

        n = 0U;

        if(x <= UINT64_SUFFIX(0x00000000FFFFFFFF))
        {
            n += 32U;
            x <<= 32U;
        }

        if(x <= UINT64_SUFFIX(0x0000FFFFFFFFFFFF))
        {
            n += 16U;
            x <<= 16U;
        }

        if(x <= UINT64_SUFFIX(0x00FFFFFFFFFFFFFF))
        {
            n += 8U;
            x <<= 8U;
        }

        if(x <= UINT64_SUFFIX(0x0FFFFFFFFFFFFFFF))
        {
            n += 4U;
            x <<= 4U;
        }

        if(x <= UINT64_SUFFIX(0x3FFFFFFFFFFFFFFF))
        {
            n += 2U;
            x <<= 2U;
        }

        if(x <= UINT64_SUFFIX(0x7FFFFFFFFFFFFFFF))
        {
            n += 1;
        }
    }

    return n;
}