//  ============================================================
//
//  add.cpp
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  Implementation functions for addition and subtraction.
//
//  To do:
//
//  Most of the scalar functions are written in terms of 'long'.
//  For most cases, this is OK, because most compilers implement
//  some kind of 'long long'.  Fo those that do not, we must use
//  'long' as our double digit type.  In this case, these
//  functions will break.
//  We need a way to abstract out this information, so that
//  these functions work whether or not the double digit type is
//  a long.  One way to do that might be to have these functions
//  check the digit size, and call smaller functions as needed.
//  It seems a waste to add that overhead to the general case.
//
//  ============================================================
#include <lnv3/ln3impl.h>


static compare_t subtractAbs( const Base *A, const Base *B, Base *Diff );
static compare_t subtractAbs( Base *A, long b );
static compare_t subtractAbs( Base *A, unsigned long b );


//  ============================================================  //


static void
__add( Base *A, long b )
//
//  Compute A = Abs( A ) + Abs( b )
//
{
    digit_t *a = A->digit;
    
    if( A->size == 0 )
        if( b == 0 )
            return;
        else
        {
            A->size = 1;
            *a = ( ( b > 0 ) ? b : ( 0 - b ) );
            return;
        }


    ddSplit_t accum;
    accum.all = (ddigit_t)*a + (ddigit_t)b;
    *a = accum.dd.low;

    const digit_t *end = a + A->size;
    for( a++ ; a < end ; a++ )
    {
        accum.all = (ddigit_t)*a + accum.dd.high;
        *a = accum.dd.low;
        if( ! accum.dd.high )
            break;
    }

    if( accum.dd.high )
    {
        *a = accum.dd.high;
        A->size++;
    }
}


//  ============================================================  //


static void
__add( Base *A, unsigned long b )
//
//  Compute A = Abs( A ) + Abs( b )
//
{
    digit_t *a = A->digit;
    
    if( A->size == 0 )
        if( b == 0 )
            return;
        else
        {
            A->size = 1;
            *a = b;
            return;
        }

    ddSplit_t accum;
    accum.all = (ddigit_t)*a + (ddigit_t)b;
    *a = accum.dd.low;

    const digit_t *end = a + A->size;
    for( a++ ; a < end ; a++ )
    {
        accum.all = (ddigit_t)*a + accum.dd.high;
        *a = accum.dd.low;
        if( ! accum.dd.high )
            break;
    }

    if( accum.dd.high )
    {
        *a = accum.dd.high;
        A->size++;
    }
}


//  ============================================================  //


static void
__add( const Base *A, const Base *B, Base *Sum )
//
//  Compute Abs( A ) + Abs( B )
//
{
    const digit_t *a;
    const digit_t *b;
    digit_t *s = Sum->digit;
    const digit_t *s1End, *s2End;

    //  WLOG, assume a.size > b.size
    if( B->size > A->size )
    {
        a = B->digit;
        b = A->digit;
        s1End = s + A->size;
        s2End = s + B->size;
        Sum->size = B->size;
    }
    else
    {
        a = A->digit;
        b = B->digit;
        s1End = s + B->size;
        s2End = s + A->size;
        Sum->size = A->size;
    }

    ddSplit_t accum; accum.all = 0;
    for( ; s < s1End ; a++, b++, s++ )
    {
        //
        //  highDigit( accum ) is the carry
        //
        accum.all = (ddigit_t)*a + (ddigit_t)*b + accum.dd.high;
        *s = accum.dd.low;
    }
    for( ; s < s2End ; a++, s++ )
    {
        accum.all = (ddigit_t)*a + accum.dd.high;
        *s = accum.dd.low;
    }

    if( accum.dd.high )
    {
        *s = accum.dd.high;
        Sum->size++;
    }
}


//  ============================================================  //


void
add( Base *A, long b )
//
//  Compute A = A + b;
//
//  =======================================================
//  A->sign    sign(b)    operation         Diff->sign
//  -------    -------    ---------    --------------------
//     +          +       add          +
//     +          -       subtract     + if abs(A) > abs(b)
//                                     + if abs(A) = abs(b)
//                                     - if abs(A) < abs(b)
//     -          +       subtract     - if abs(A) > abs(b)
//                                     + if abs(A) = abs(b)
//                                     + if abs(A) < abs(b)
//     -          -       add          -
//  =======================================================
//
{
    if( sizeof( long ) > sizeof( digit_t ) )
        ;  // do something.

    if( A->size == 0 )
        if( b == 0 )
            return;
        else if( b > 0 )
        {
            A->digit[0] = b;
            A->sign = positive;
            A->size = 1;
            return;
        }
        else // b < 0
        {
            A->digit[0] = ( 0 - b );
            A->sign = negative;
            A->size = 1;
            return;
        }

    if( ( A->sign == negative ) == ( b < 0 ) )
    {
        __add( A, ( (b<0) ? -b : b ) );
    }
    else
    {
        sign_t signA = A->sign;

        compare_t comp;
        comp = subtractAbs( A, b );

        if( ( signA == positive ) && ( comp == lessThan ) )
            A->sign = negative;
        else if( ( signA == negative ) && ( comp == greaterThan ) )
            A->sign = negative;
        else
            A->sign = positive;
    }
}


//  ============================================================  //


void
add( Base *A, unsigned long b )
//
//  Compute A = A + b;
//
//  Note: b >= 0
//
//  =======================================================
//  A->sign    sign(b)    operation         Diff->sign
//  -------    -------    ---------    --------------------
//     +          +       add          +
//     -          +       subtract     - if abs(A) > abs(b)
//                                     + if abs(A) = abs(b)
//                                     + if abs(A) < abs(b)
//  =======================================================
//
{
    if( sizeof( long ) > sizeof( digit_t ) )
        ;  // do something.

    if( A->size == 0 )
        if( b == 0 )
            return;
        else if( b > 0 )
        {
            A->digit[0] = b;
            A->sign = positive;
            A->size = 1;
            return;
        }

    if( A->sign == positive )
    {
        __add( A, b );
    }
    else
    {
        sign_t signA = A->sign;

        compare_t comp;
        comp = subtractAbs( A, b );

        if( ( signA == positive ) && ( comp == lessThan ) )
            A->sign = negative;
        else if( ( signA == negative ) && ( comp == greaterThan ) )
            A->sign = negative;
        else
            A->sign = positive;
    }
}


//  ============================================================  //


void
add( const Base *A, const Base *B, Base *Sum )
//
//  Compute Sum = A + B;
//
//  =======================================================
//  A->sign    B->sign    operation         Diff->sign
//  -------    -------    ---------    --------------------
//     +          +       add          +
//     +          -       subtract     + if abs(A) > abs(B)
//                                     + if abs(A) = abs(B)
//                                     - if abs(A) < abs(B)
//     -          +       subtract     - if abs(A) > abs(B)
//                                     + if abs(A) = abs(B)
//                                     + if abs(A) < abs(B)
//     -          -       add          -
//  =======================================================
//
{
    if( A->sign == B->sign )
    {
        __add( A, B, Sum );
        Sum->sign = A->sign;
    }
    else
    {
        compare_t comp;
        comp = subtractAbs( A, B, Sum );

        if( ( A->sign == positive ) && ( comp == lessThan ) )
            Sum->sign = negative;
        else if( ( A->sign == negative ) && ( comp == greaterThan ) )
            Sum->sign = negative;
        else
            Sum->sign = positive;
    }
}


//  ============================================================  //


compare_t
subtractAbs( const Base *A, const Base *B, Base *Diff )
//
//  Returns AbsCompare( A, B )
//
{
    const digit_t *a, *b, *end1, *end2;

    compare_t comp = AbsCompare( A, B );
    if( comp == equalTo )
    {
        Diff->size = 0;
        Diff->sign = positive;
        return comp;
    }
    else if( comp == greaterThan ) // A > B
    {
        a = A->digit;
        b = B->digit;
        end1 = B->digit + B->size;
        end2 = A->digit + A->size;
    }
    else // B > A
    { 
        a = B->digit;
        b = A->digit;
        end1 = A->digit + A->size;
        end2 = B->digit + B->size;
    }
    digit_t *diff = Diff->digit;

    digit_t *lastNonZero = 0;

    sddSplit_t temp; temp.all = 0;

    unsigned short borrow = 0, prevBorrow = 0;
    for( ; b<end1 ; a++, b++, diff++ )  //  only loop through smallest, not largest!
    {
        //( *a < *b ) ? borrow = 1 : borrow = 0;
        //highDigit( temp ) = borrow;
        //lowDigit( temp ) = *a;
        //temp = temp - *b - prevBorrow;

        ( *a < prevBorrow ) ? borrow = 1 : borrow = 0;
        temp.dd.high = borrow;
        temp.dd.low  = *a;
        temp.all -= prevBorrow;
        if( temp.all < *b )
        {
            borrow = 1;
            temp.dd.high = borrow;
        }
        temp.all -= *b;

        prevBorrow = borrow;

        *diff = temp.dd.low;
        if( *diff )
            lastNonZero = diff;
    }

    //  propagate carry.
    for( ; a<end2 ; a++, diff++ )
    {
        ( *a < prevBorrow ) ? borrow = 1 : borrow = 0;
        temp.dd.high = borrow;
        temp.dd.low  = *a;
        temp.all     = temp.all - prevBorrow;

        prevBorrow = borrow;

        *diff = temp.dd.low;
        if( *diff )
            lastNonZero = diff;
    }

    Diff->size = lastNonZero - Diff->digit + 1;
    Diff->sign = positive;

    return comp;
}


//  ============================================================  //


static compare_t
subtractAbs( Base *A, long b )
//
//  Compute A = abs( abs(A) - abs(b) )
//
//  Returns AbsCompare( A, b )
//
{
    if( A->size == 0 )
        if( b == 0 )
        {
            return equalTo;
        }
        else if( b > 0 )
        {
            A->digit[0] = b;
            A->size = 1;
            A->sign = positive;
            return lessThan;
        }
        else // b < 0
        {
            A->digit[0] = -b;
            A->size = 1;
            A->sign = positive;
            return lessThan;
        }

    compare_t comp = CompareAbs( A, b );
    if( comp == equalTo )
    {
        A->size = 0;
        A->sign = positive;
        return comp;
    }

    if( b < 0 )
        b = 0 - b;

    if( comp == lessThan )
    {
        A->digit[0] = b - A->digit[0];
        A->size = 1;
        return comp;
    }

    //  A > b
    digit_t *a = A->digit;
    const digit_t *end = A->digit + A->size;

    unsigned short borrow = 0;
    ( *a < (unsigned long)b ) ? borrow = 1 : borrow = 0;

    sddSplit_t temp;
    temp.dd.high = borrow;
    temp.dd.low  = *a;
    temp.all     = temp.all - b;
    *a = temp.dd.low;

    unsigned short prevBorrow = borrow;
    for( a++ ; prevBorrow && ( a<end ) ; a++ )
    {
        ( *a < prevBorrow ) ? borrow = 1 : borrow = 0;
        temp.dd.high = borrow;
        temp.dd.low  = *a;
        temp.all = temp.all - prevBorrow;

        prevBorrow = borrow;

        *a = temp.dd.low;
    }

    if( A->digit[ A->size - 1 ] == 0 )
        (A->size)--;

    return comp;
}


//  ============================================================  //


static compare_t
subtractAbs( Base *A, unsigned long b )
//
//  Compute A = abs( abs(A) - abs(b) )
//
//  Returns AbsCompare( A, b )
//
{
    if( A->size == 0 )
        if( b == 0 )
        {
            return equalTo;
        }
        else
        {
            A->digit[0] = b;
            A->size = 1;
            A->sign = positive;
            return lessThan;
        }

    compare_t comp = CompareAbs( A, b );
    if( comp == equalTo )
    {
        A->size = 0;
        A->sign = positive;
        return comp;
    }

    if( comp == lessThan )
    {
        A->digit[0] = b - A->digit[0];
        A->size = 1;
        return comp;
    }

    //  A > b
    digit_t *a = A->digit;
    const digit_t *end = A->digit + A->size;

    unsigned short borrow = 0;
    ( *a < b ) ? borrow = 1 : borrow = 0;

    sddSplit_t temp;
    temp.dd.high = borrow;
    temp.dd.low  = *a;
    temp.all     = temp.all - b;
    *a = temp.dd.low;

    unsigned short prevBorrow = borrow;
    for( a++ ; prevBorrow && ( a<end ) ; a++ )
    {
        ( *a < prevBorrow ) ? borrow = 1 : borrow = 0;
        temp.dd.high = borrow;
        temp.dd.low  = *a;
        temp.all     = temp.all - prevBorrow;

        prevBorrow = borrow;

        *a = temp.dd.low;
    }

    if( A->digit[ A->size - 1 ] == 0 )
        (A->size)--;

    return comp;
}


//  ============================================================  //


void
Subtract( const Base *A, const Base *B, Base *Diff )
//
//  Compute Diff = A - B;
//
//  =======================================================
//  A->sign    B->sign    operation         Diff->sign
//  -------    -------    ---------    --------------------
//     +          +       subtract     + if abs(A) > abs(B)
//                                     + if abs(A) = abs(B)
//                                     - if abs(A) < abs(B)
//     +          -       add          +
//     -          +       add          -
//     -          -       subtract     - if abs(A) > abs(B)
//                                     + if abs(A) = abs(B)
//                                     + if abs(A) < abs(B)
//  =======================================================
//
{
    if( A->sign != B->sign )
    {
        __add( A, B, Diff );
        Diff->sign = A->sign;
    }
    else // A->sign == B->sign
    {
        compare_t comp;
        comp = subtractAbs( A, B, Diff );
        if( A->sign == positive )
            if( comp == lessThan ) // abs( A ) < abs( B )
                Diff->sign = negative;
            else
                Diff->sign = positive;
        else //  A->sign == negative
            if( comp == greaterThan ) // abs( A ) > abs( B )
                Diff->sign = negative;
            else
                Diff->sign = positive;
    }
}


//  ============================================================  //


void
Subtract( Base *A, long b )
//
//  Compute A = A - b;
//
//  =======================================================
//  A->sign    B->sign    operation         Diff->sign
//  -------    -------    ---------    --------------------
//     +          +       subtract     + if abs(A) > abs(b)
//                                     + if abs(A) = abs(b)
//                                     - if abs(A) < abs(b)
//     +          -       add          +
//     -          +       add          -
//     -          -       subtract     - if abs(A) > abs(b)
//                                     + if abs(A) = abs(b)
//                                     + if abs(A) < abs(b)
//  =======================================================
//
{
    if( A->size == 0 )
        if( b == 0 )
            return;
        else if( b > 0 )
        {
            A->digit[0] = b;
            A->size = 1;
            A->sign = negative;
            return;
        }
        else // b < 0
        {
            A->digit[0] = -b;
            A->size = 1;
            A->sign = positive;
            return;
        }

    if( A->sign != sign( b ) )
    {
        sign_t saveSign = A->sign;
        __add( A, b );
        A->sign = saveSign;
    }
    else // A->sign == B->sign
    {
        compare_t comp;
        comp = subtractAbs( A, b );
        if( A->sign == positive )
            if( comp == lessThan ) // abs( A ) < abs( b )
                A->sign = negative;
            else
                A->sign = positive;
        else //  A->sign == negative
            if( comp == greaterThan ) // abs( A ) > abs( b )
                A->sign = negative;
            else
                A->sign = positive;
    }
}


//  ============================================================  //


void
Subtract( Base *A, unsigned long b )
//
//  Compute A = A - b;
//
//  Note:  b > 0
//
//  =======================================================
//  A->sign    B->sign    operation         Diff->sign
//  -------    -------    ---------    --------------------
//     +          +       subtract     + if abs(A) > abs(b)
//                                     + if abs(A) = abs(b)
//                                     - if abs(A) < abs(b)
//     -          +       add          -
//  =======================================================
//
{
    if( A->size == 0 )
        if( b == 0 )
            return;
        else // b > 0
        {
            A->digit[0] = b;
            A->size = 1;
            A->sign = negative;
            return;
        }

    if( A->sign == negative )
    {
        __add( A, b );
        A->sign = negative;
    }
    else // A->sign == B->sign
    {
        compare_t comp;
        comp = subtractAbs( A, b );
        if( A->sign == positive )
            if( comp == lessThan ) // abs( A ) < abs( b )
                A->sign = negative;
            else
                A->sign = positive;
        else //  A->sign == negative
            if( comp == greaterThan ) // abs( A ) > abs( b )
                A->sign = negative;
            else
                A->sign = positive;
    }
}