/*
%Z%  FILE: %M%  RELEASE: %I%  DATE: %G%, %U%
*/
/*******************************************************************************

File:

    VeryLong.cc


Author:    Alex Measday, ISI


Purpose:

    The VeryLong class implements multi-precision, signed integers.  The
    arithmetic, bit-wise, and relational operators are overloaded, thus
    allowing you to manipulate VeryLongs in the same fashion as int's and
    long's.  The following example computes N! using signed, 64-bit numbers:

        #include  "VeryLong.hh"		// Very long integers.

        VeryLong<64>  factorial (VeryLong<64> number) {
            if (number == 0)  return (1) ;
            return (number * factorial (number - 1)) ;
        }

    The number of bits of precision specified in the template instantiation
    is rounded up to the next multiple of the host machine's long precision.
    For example, a VeryLong<57> (or any precision between 33 and 63) would
    be instantiated with 64 bits of precision on a 32-bit processor; the
    VeryLong<57> type would still be distinct from the VeryLong<64> type
    as far as the compiler is concerned.


Public Methods (* have inline definitions):

    VeryLong() - creates an uninitialized VeryLong value.
    VeryLong() - creates an initialized VeryLong value.
    ~VeryLong() - destroys a VeryLong value.
    Decode() - decodes a VeryLong value from ASCII.
    Encode() - encodes a VeryLong value in ASCII.
  * ++() - increments a VeryLong value.
  * --() - decrements a VeryLong value.
  * (double)() - returns a VeryLong value as a real number.

Overloaded Operators (* have inline definitions):

    +() - returns the sum of two VeryLong values.
  * -() - returns the negation of a VeryLong value.
  * -() - returns the difference between two VeryLong values.
    *() - returns the product of two VeryLong values.
    /() - returns the quotient of two VeryLong values.
  * %() - returns the remainder from the division of two VeryLong values.
    &() - returns the bit-wise AND of two VeryLong values.
    |() - returns the bit-wise OR of two VeryLong values.
    ~() - returns the 1's-complement of a VeryLong value.
    <<() - returns the left-shifted value of a VeryLong value.
    >>() - returns the right-shifted value of a VeryLong value.
    ==() - compares two VeryLong values.
  * !=() - compares two VeryLong values.
    <() - compares two VeryLong values.
  * <=() - compares two VeryLong values.
    >() - compares two VeryLong values.
  * >=() - compares two VeryLong values.

I/O Operators (* have inline definitions):

    >>() - inputs a VeryLong value in ASCII.
  * <<() - outputs a VeryLong value in ASCII.

*******************************************************************************/


#include  <cerrno>			// System error definitions.
#include  <climits>			// Maximum/minimum value definitions.
#include  <cstdio>			// Standard I/O definitions.
#include  <iostream.h>			// I/O stream definitions.
#define  VeryLong_Implementation
#include  "VeryLong.hh"			// VeryLong class definition.


#define  NUMBITS  (NUMLONGS * sizeof (long) * 8)

#define  MSBit(longword)  ((longword < 0) ? 1 : 0)

#define  MOST  (NUMLONGS - 1)
#define  LEAST  0

#define  DoFromLeastToMost(index)  \
    for (int index = LEAST ;  index < (MOST + 1) ;  i++)
#define  DoFromLeastToNextMost(index)  \
    for (int index = LEAST ;  index < MOST ;  i++)
#define  DoFromMostToLeast(index)  \
    for (int index = MOST ;  index >= LEAST ;  i--)
#define  DoFromNextMostToLeast(index)  \
    for (int index = MOST-1 ;  index >= LEAST ;  i--)

/*******************************************************************************

Constructors:

    VeryLong ()

    Create a VeryLong Value.


Purpose:

    The VeryLong() constructors create instances of multi-precision,
    signed integers.


    Invocation (uninitialized value):

        VeryLong<precision> bigNumber () ;

    Invocation (initialized value):

        VeryLong<precision> bigNumber (initialValue) ;

    where

        <precision>	- I
            specifies the minimum width in bits of the VeryLong value.
        <initialValue>	- I
            is the initial value of the VeryLong value.
        <bigNumber>	- O
            is the VeryLong value created by the constructor.

*******************************************************************************/


//******************************************************************************
//    Constructor to create an uninitialized value.
//******************************************************************************

template <
    unsigned  int  precision>

VeryLong<precision>::VeryLong ()

{
    state = Uninitialized ;
    DoFromLeastToMost (i)
        value[i] = 0 ;
}



//******************************************************************************
//    Constructor to create an initialized value.
//******************************************************************************

template <
    unsigned  int  precision>

VeryLong<precision>::VeryLong (

    long  leastSignificant)

{
    state = Valid ;
    DoFromLeastToMost (i)
        value[i] = (leastSignificant < 0) ? ~0 : 0 ;
    value[LEAST] = leastSignificant ;
}



//******************************************************************************
//    Constructor to create an initialized value.
//******************************************************************************

/*******************************************************************************

template <
    unsigned  int  precision>

VeryLong<precision>::VeryLong (

    long  mostSignificant,
    ...)

{    // Local variables.
    va_list  ap ;

    state = Valid ;
    value[MOST] = mostSignificant ;
    va_start (ap, mostSignificant) ;
    DoFromNextMostToLeast (i)
        value[i] = va_arg (ap, long) ;
    va_end (ap) ;
}
*******************************************************************************/

/*******************************************************************************

Destructor:

    ~VeryLong ()

    Destroy a VeryLong Value.


Purpose:

    The ~VeryLong() destructor destroys a VeryLong value.


    Invocation:

        ~VeryLong<precision> () ;

    where

        <precision>	- I
            specifies the minimum width in bits of the VeryLong value.

*******************************************************************************/


template <
    unsigned  int  precision>

VeryLong<precision>::~VeryLong ()

{
    cout << "(~VeryLong) Deleting: " << this->Encode () << endl ;
}

/*******************************************************************************

Method:

    Encode ()

    Encode a VeryLong Value in ASCII.


Purpose:

    The Encode() function returns a printable (ASCII) representation of
    the VeryLong value.


    Invocation:

        asciiValue = bigNumber.Encode () ;

    where

        <bigNumber>	- I
            is the VeryLong value.
        <asciiValue>	- O
            returns a pointer to a string which contains the VeryLong
            value formatted in ASCII: "0vXXXXX..XXX", where the 'X's
            are 1 or more hexadecimal digits.  The ASCII string is
            stored in memory local to Encode();  the string should
            be used or duplicated before calling Encode() again.

*******************************************************************************/


template <
    unsigned  int  precision>

const  char  *VeryLong<precision>::Encode () const

{    // Local variables.
    static  char  asciiValue[(NUMLONGS * sizeof (unsigned long) * 2) + 1] ;



    strcpy (asciiValue, "0v") ;

    DoFromMostToLeast (i) {
        char  *s = asciiValue + strlen (asciiValue) ;
        sprintf (s, "%0*X", sizeof (long) * 2, value[i]) ;
    }

    return (asciiValue) ;

}

/*******************************************************************************

Friend:

    Operator+ ()

    Add Two VeryLong Values.


Purpose:

    Overloaded operator+() returns the sum of two VeryLong values.


    Invocation:

        sum = augend + addend ;

    where

        <augend>	- I
        <addend>	- I
            are the two VeryLong values being added.
        <sum>		- O
            returns the sum of the two VeryLong values.

*******************************************************************************/


template <
    unsigned  int  precision>

VeryLong<precision>  operator+ (

    const  VeryLong<precision>&  augend,
    const  VeryLong<precision>&  addend)

{    // Local variables.
    int  bitSum, carry = 0 ;
    VeryLong  sum (0) ;




// Add the longwords that make up the VeryLong values.

    DoFromLeastToMost (i) {
        sum.value[i] = carry + augend.value[i] + addend.value[i] ;
        bitSum = MSBit (augend.value[i]) + MSBit (addend.value[i]) ;
        if (bitSum == 2)
            carry = 1 ;
        else if ((bitSum == 1) && (MSBit (sum.value[i]) == 0))
            carry = 1 ;
        else
            carry = 0 ;
    }

// Examine the most significant longword to determine if overflow occurred.

    sum.value[MOST] = carry + augend.value[MOST] + addend.value[MOST] ;
    if ((bitSum == 0) && (sum.value[MOST] < 0))
        sum.state = VeryLong::Overflow ;	// In the positive direction.
    else if ((bitSum == 2) && (sum.value[MOST] >= 0))
        sum.state = VeryLong::Overflow ;	// In the negative direction.
    else
        sum.state = VeryLong::Valid ;

    return (sum) ;

}

/*******************************************************************************

Friend:

    Operator* ()

    Multiply Two VeryLong Values.


Purpose:

    Overloaded operator*() returns the product of two VeryLong values.


    Invocation:

        product = multiplicand * multiplier ;

    where

        <multiplicand>	- I
        <multiplier>	- I
            are the two VeryLong values being multiplied.
        <product>	- O
            returns the product of the two VeryLong values.

*******************************************************************************/


template <
    unsigned  int  precision>

VeryLong<precision>  operator* (

    const  VeryLong<precision>&  lhs,
    const  VeryLong<precision>&  rhs)

{    // Local variables.
    VeryLong  multiplicand (lhs), multiplier (rhs), product (0) ;




// The multiplier must be positive, so, if the multiplier is negative,
// negate both the multiplier and the multiplicand; i.e., A*B = (-A)*(-B).

    if (multiplier < 0) {
        multiplicand = -multiplicand ;
        multiplier = -multiplier ;
    }

// Bit by bit, accumulate the product.

    while (multiplier != 0) {
        if (multiplier.value[LEAST] & 1)  product = product + multiplicand ;
        multiplicand = multiplicand << 1 ;	// Shift multiplicand left.
        multiplier = multiplier >> 1 ;		// Shift multiplier right.

    }

    return (product) ;

}

/*******************************************************************************

Friend:

    Operator/ ()

    Divide Two VeryLong Values.


Purpose:

    Overloaded operator/() returns the quotient of two VeryLong values.


    Invocation:

        quotient = dividend / divisor ;

    where

        <dividend>	- I
        <divisor>	- I
            are the two VeryLong values being divided.
        <quotient>	- O
            returns the quotient of the two VeryLong values.

*******************************************************************************/


template <
    unsigned  int  precision>

VeryLong<precision>  operator/ (

    const  VeryLong<precision>&  lhs,
    const  VeryLong<precision>&  rhs)

{    // Local variables.
    int  bitShift, isNegative ;
    VeryLong  dividend (lhs), divisor (rhs), msBit, quotient, remainder ;




// Determine the sign of the quotient and convert both the dividend and
// divisor to positive numbers.

    isNegative = 0 ;
    if (dividend < 0) {
        isNegative = 1 ;
        dividend = -dividend ;
    }
    if (divisor < 0) {
        isNegative = isNegative ? 0 : 1 ;
        divisor = -divisor ;
    }

// Align the most significant bit of the divisor with the most
// significant bit of the dividend.

    bitShift = 0 ;
    if (dividend > divisor) {
        msBit = VeryLong (1) << (NUMBITS - 1) ;
        while ((msBit & dividend) == 0)
            msBit = msBit >> 1 ;
        while ((msBit & divisor) == 0) {
            divisor = divisor << 1 ;  bitShift++ ;
        }
    }

// Perform base-2 long division!

    remainder = dividend ;  quotient = 0 ;
    while (bitShift-- >= 0) {
        quotient = quotient << 1 ;
        if (remainder >= divisor) {
            quotient = quotient | 1 ;
            remainder = remainder - divisor ;
        }
        divisor = divisor >> 1 ;
    }

// Take the sign of the result into account.

    if (isNegative)  quotient = -quotient ;

    return (quotient) ;

}

/*******************************************************************************

Friend:

    Bitwise Operators.


Purpose:

    The overloaded bitwise operators perform bitwise manipulation of
    VeryLong values.


    Invocation:

        result = bigNumber1 & bigNumber2 ;
        result = bigNumber1 | bigNumber2 ;
        result = ~bigNumber1 ;

    where

        <bigNumber1>	- I
        <bigNumber2>	- I
            are the two VeryLong values being manipulated.
        <result>	- O
            returns the result of the specified bitwise operation.

*******************************************************************************/



//******************************************************************************
//    Bitwise AND operator.
//******************************************************************************

template <
    unsigned  int  precision>

int  operator& (

    const  VeryLong<precision>&  lhs,
    const  VeryLong<precision>&  rhs)

{    // Local variables.
    VeryLong<precision>  result = lhs ;


    DoFromLeastToMost (i)
        result.value[i] &= rhs.value[i] ;

    return (result) ;

}



//******************************************************************************
//    Bitwise OR operator.
//******************************************************************************

template <
    unsigned  int  precision>

int  operator| (

    const  VeryLong<precision>&  lhs,
    const  VeryLong<precision>&  rhs)

{    // Local variables.
    VeryLong<precision>  result = lhs ;


    DoFromLeastToMost (i)
        result.value[i] |= rhs.value[i] ;

    return (result) ;

}



//******************************************************************************
//    1's-complement operator.
//******************************************************************************

template <
    unsigned  int  precision>

VeryLong<precision>  operator~ (

    const  VeryLong<precision>&  lhs)

{    // Local variables.
    VeryLong<precision>  result = lhs ;


    DoFromLeastToMost (i)
        result.value[i] = ~result.value[i] ;

    return (result) ;

}

/*******************************************************************************

Friend:

    Operator<< ()

    Shift a VeryLong Value to the Left.


Purpose:

    Overloaded operator<<() returns a VeryLong value shifted N bits
    to the left.


    Invocation:

        shiftedNumber = bigNumber << numBitsToShift ;

    where

        <bigNumber>		- I
            is the VeryLong value being shifted.
        <numBitsToShift>	- I
            specifies how many to bits to the left the value will be shifted.
        <shiftedNumber>		- O
            returns the shifted value.

*******************************************************************************/


template <
    unsigned  int  precision>

VeryLong<precision>  operator<< (

    const  VeryLong<precision>&  bigNumber,
    unsigned  int  numBitsToShift)

{    // Local variables.
    int  isNegative = (bigNumber < 0) ;
    VeryLong  result (bigNumber) ;




    while (numBitsToShift-- > 0) {

// Check for overflow.

        if (isNegative && (result >= 0))
            result.state = VeryLong::Overflow ;	// In the negative direction.
        else if (!isNegative && (result < 0))
            result.state = VeryLong::Overflow ;	// In the positive direction.

// Shift the value 1 bit to the left.

        result.value[MOST] = result.value[MOST] << 1 ;
        DoFromNextMostToLeast (i) {
            if (MSBit (result.value[i]) == 1)
                result.value[i+1] = result.value[i+1] | 1 ;
            result.value[i] = result.value[i] << 1 ;
        }

    }

    return (result) ;

}

/*******************************************************************************

Friend:

    Operator>> ()

    Shift a VeryLong Value to the Right.


Purpose:

    Overloaded operator>>() returns a VeryLong value shifted N bits
    to the right.


    Invocation:

        shiftedNumber = bigNumber << numBitsToShift ;

    where

        <bigNumber>		- I
            is the VeryLong value being shifted.
        <numBitsToShift>	- I
            specifies how many to bits to the right the value will be shifted.
        <shiftedNumber>		- O
            returns the shifted value.

*******************************************************************************/


template <
    unsigned  int  precision>

VeryLong<precision>  operator>> (

    const  VeryLong<precision>&  bigNumber,
    unsigned  int  numBitsToShift)

{    // Local variables.
    VeryLong  result (bigNumber) ;




    while (numBitsToShift-- > 0) {

// Check for underflow.

        if ((result == 1) ||		// Positive value shifted too far?
            (result == -1)) {		// Negative value shifted too far?
            result.state = VeryLong::Underflow ;
        }

// Shift the value 1 bit to the right.

        DoFromLeastToNextMost (i) {
            result.value[i] = (result.value[i] >> 1) & LONG_MAX ;
            if ((result.value[i+1] & 1) == 1)  result.value[i] |= LONG_MIN ;
        }
        result.value[MOST] = result.value[MOST] >> 1 ;

    }

    return (result) ;

}

/*******************************************************************************

Friend:

    Relational Operators.


Purpose:

    The overloaded relational operators compare two VeryLong values.


    Invocation:

        truth = (bigNumber1 == bigNumber2) ;
        truth = (bigNumber1 < bigNumber2) ;
        truth = (bigNumber1 > bigNumber2) ;

    where

        <bigNumber1>	- I
        <bigNumber2>	- I
            are the two VeryLong values being compared.
        <truth>		- O
            returns true if the numbers are in the specified relation to
            each other and false otherwise.

*******************************************************************************/



//******************************************************************************
//    Equals operator.
//******************************************************************************

template <
    unsigned  int  precision>

int  operator== (

    const  VeryLong<precision>&  lhs,
    const  VeryLong<precision>&  rhs)

{
    DoFromLeastToMost (i)
        if (lhs.value[i] != rhs.value[i])  return (0) ;
    return (1) ;
}



//******************************************************************************
//    Less-than operator.
//******************************************************************************

template <
    unsigned  int  precision>

int  operator< (

    const  VeryLong<precision>&  lhs,
    const  VeryLong<precision>&  rhs)

{

// Do a signed comparison on the most significant longwords.

    if (lhs.value[MOST] > rhs.value[MOST])  return (0) ;
    if (lhs.value[MOST] < rhs.value[MOST])  return (1) ;

// Do an unsigned comparison on the remaining longwords.

    DoFromNextMostToLeast (i) {
        if ((unsigned long) lhs.value[i] >
            (unsigned long) rhs.value[i])  return (0) ;
        if ((unsigned long) lhs.value[i] <
            (unsigned long) rhs.value[i])  return (1) ;
    }

    return (0) ;

}



//******************************************************************************
//    Greater-than operator.
//******************************************************************************

template <
    unsigned  int  precision>

int  operator> (

    const  VeryLong<precision>&  lhs,
    const  VeryLong<precision>&  rhs)

{

// Do a signed comparison on the most significant longwords.

    if (lhs.value[MOST] < rhs.value[MOST])  return (0) ;
    if (lhs.value[MOST] > rhs.value[MOST])  return (1) ;

// Do an unsigned comparison on the remaining longwords.

    DoFromNextMostToLeast (i) {
        if ((unsigned long) lhs.value[i] <
            (unsigned long) rhs.value[i])  return (0) ;
        if ((unsigned long) lhs.value[i] >
            (unsigned long) rhs.value[i])  return (1) ;
    }

    return (0) ;

}

/*******************************************************************************

Friend:

    Operator>> ()

    Input a VeryLong Value.


Purpose:

    Overloaded operator>>() decodes a VeryLong value from an input stream.


    Invocation:

        stream >> bigNumber ;

    where

        <stream>	- I
            is the input stream.
        <bigNumber>	- O
            is the variable into which the VeryLong value is read.

*******************************************************************************/


template <
    unsigned  int  precision>

istream&  operator>> (

    istream&  stream,
    VeryLong<precision>&  bigNumber)

{

    stream >> "0v" ;

    DoFromMostToLeast (i) {
        stream >> bigNumber.value[i] ;
    }

    bigNumber.state = VeryLong::Valid ;

    return (stream) ;

}