// Integer - Integer class to support arbitrary number of bits
// Author: Ali Cehreli
// Started: July 29, 1999

/** \file
    Defines an large integer class that can have any number
    of bits that is set at compile-time.
*/

#ifndef INCLUDED_INTEGER_H
#define INCLUDED_INTEGER_H

#include <iosfwd>
#include <limits>
#include <cassert>

//  #define DEBUG_INTEGER_H
#ifdef DEBUG_INTEGER_H
#include <iostream>
using std::cout;
#endif


/** @name Ensures the implementation type used to instantiate Integer is unsigned.

    The following Ensure... template classes are provided to ensure that
    the implementation type chosen for Integer is unsigned.
    The compilation will break because EnsureUnsigned<false> doesn't have
    the default constructor implemented.
*/
//@{
template <bool Bounded> class EnsureUnsigned
{};

/// Cannot be compiled because the constructor is private. \see EnsureUnsignedType.
template <> class EnsureUnsigned<false>
{
private:
    EnsureUnsigned();
};

/// Doesn't allow any signed type to compile
template <class ImplType>
class EnsureUnsignedType : private EnsureUnsigned<!std::numeric_limits<ImplType>::is_signed>
{};
//@}


/// Only one of the following specializations will be used depending on the size of the implementation type

template <bool SmallImplType> inline unsigned int shiftInitValue(unsigned int value,
                                                                 unsigned int totalImplBits);

template <> inline unsigned int shiftInitValue<false>(unsigned int /* value */,
                                                      unsigned int /* totalImplBits */)
{
    // Our implementation type's size is greater than or equal to 'unsigned int's size.
    // All of the value is consumed at one shot.
    return 0;
}

template <> inline unsigned int shiftInitValue<true>(unsigned int value,
                                                     unsigned int totalImplBits)
{
    // Let's shift the actual value. We will need the upper bits to initialize
    // other words of the impementation array.
    return value >> totalImplBits;
}


/// Defines an integer class with arbitrary number of bits.
/**
   BitCount is the number of bits. ImplType is the type of the actual data.
   Integer will statically allocate an array of this type and use it as
   the underlying data.
   
   This implementation is big endian: data_[0] has the lowermost bits
*/
template <int BitCount, class ImplType = unsigned char>
class Integer : private EnsureUnsignedType<ImplType>
{
    typedef Integer<BitCount, ImplType> MyType;

    /// Number of bits in the implementation words.
    /**
       @warning Assumes that character has 8 bits.
    */
    enum { TOTAL_IMPL_BITS = sizeof (ImplType) * 8 };

    friend void divide<BitCount, ImplType>(MyType const & dividend, MyType const & divisor,
                                           MyType & quotient, MyType & remainder);
public:

    /// Returns the size of the implementation array
    enum { SIZE = (BitCount / TOTAL_IMPL_BITS) + ((BitCount % TOTAL_IMPL_BITS) != 0) };
    
private:

    enum
    {
        LAST_INDEX = SIZE - 1,
        BITS_USED_IN_UPPER_ENTRY = BitCount - (SIZE - 1) * TOTAL_IMPL_BITS,
        UNUSED_UPPER_BITS = TOTAL_IMPL_BITS * SIZE - BitCount
    };
    
    ImplType data_[SIZE];


    // This function may leave garbage in the upper unused bits
    void shiftLeftWords(int shift)
    {
        if (shift)
        {
            if (shift > SIZE) shift = SIZE;
            int upperZeroIdx = shift - 1;
            
            for (int i = LAST_INDEX; i >= 0; --i)
            {
                data_[i] = (i <= upperZeroIdx) ? 0 : data_[i - shift];
            }
        }
    }

    void shiftRightWords(int shift)
    {
        if (shift)
        {
            if (shift > SIZE) shift = SIZE;
            int lowerZeroIdx = SIZE - shift;

            for (int i = 0; i < SIZE; ++i)
            {
                data_[i] = (i >= lowerZeroIdx) ? 0 : data_[i + shift];
            }
        }
    }

    // This function may leave garbage in the upper unused bits
    void shiftLeftBits(int shift)
    {
        if (shift)
        {
            assert((shift >= 0) && (shift < TOTAL_IMPL_BITS));

            int shiftRightForCarry = TOTAL_IMPL_BITS - shift;
            int carriedUpperBits = 0;

            for (int i = 0; i < SIZE; ++i)
            {
                // No need to mask here. Our implementation type is unsigned
                int newUpperBits = data_[i] >> shiftRightForCarry;
            
                data_[i] <<= shift;
                data_[i] |= carriedUpperBits;

                carriedUpperBits = newUpperBits;
            }
        }
    }
    
    void shiftRightBits(int shift)
    {
        if (shift)
        {
            assert((shift >= 0) && (shift < TOTAL_IMPL_BITS));

            int shiftLeftForCarry = TOTAL_IMPL_BITS - shift;
            int carriedLowerBits = 0;

            for (int i = LAST_INDEX; i >= 0; --i)
            {
                int newLowerBits = data_[i] << shiftLeftForCarry;
            
                data_[i] >>= shift;
                data_[i] |= carriedLowerBits;

                carriedLowerBits = newLowerBits;
            }
        }
    }

    enum
    {
        totalHalfWords = SIZE * 2,
        halfWordSize = TOTAL_IMPL_BITS / 2,
        halfWordMask = (1 << halfWordSize) - 1
    };

    static ImplType getUpperHalf(ImplType word)
    {
        return (word >> halfWordSize) & halfWordMask;
    }

    static ImplType getLowerHalf(ImplType word)
    {
        return word & halfWordMask;
    }

    ImplType getHalfWord(int idx) const
    {
        assert((idx >= 0) && (idx < totalHalfWords));

#ifdef DEBUG_INTEGER_H
        cout << "getting " << idx << " .... ";
#endif

        ImplType word = (idx % 2) ? getUpperHalf(data_[idx / 2]) : getLowerHalf(data_[idx / 2]);

#ifdef DEBUG_INTEGER_H
        cout << word << '\n';
#endif        

        return word;
    }

    static void setUpperHalf(ImplType & word, ImplType data)
    {
        word &= halfWordMask;
        word |= (data << halfWordSize);
    }

    static void setLowerHalf(ImplType & word, ImplType data)
    {
        word &= (halfWordMask << halfWordSize);
        word |= (data & halfWordMask);
    }

    void setHalfWord(int idx, ImplType data)
    {
        assert((idx >= 0) && (idx < totalHalfWords));
        
#ifdef DEBUG_INTEGER_H
        cout << "setting " << idx << " to " << (data & halfWordMask) << '\n';
        cout << *this << '\n';
#endif        
        ImplType & word = data_[idx / 2];
        (idx % 2) ? setUpperHalf(word, data) : setLowerHalf(word, data);

#ifdef DEBUG_INTEGER_H
        cout << *this << '\n';
#endif        
    }    

    void reset()
    {
        for (int i = 0; i != SIZE; ++i)
        {
            data_[i] = 0;
        }
    }


    // Clears the unused upper bits of the upper word
    
    void clearUnusedBits_()
    {
        data_[LAST_INDEX] <<= UNUSED_UPPER_BITS;
        data_[LAST_INDEX] >>= UNUSED_UPPER_BITS;
    }

public:

    /*
    If you get an error message on the following line, indicating that
    EnsureUnsignedType<> doesn't have a default constructor; then you
    are providing a signed type as the implementation type.
    Integer works only with unsigned types as of this writing.
    */

    /// Initializes with 0
    Integer()
    {
        reset();
    }

    /// Initializes using an unsigned integer.
    /**
       This seems insufficient. Why 'unsigned int'?
       Seems like that's all we need so far.
    */
    Integer(unsigned int value)
    {
        for (int i = 0; i < SIZE; ++i)
        {
            data_[i] = value;

            if (value)
            {
                bool const implTypeIsShort = sizeof(value) > sizeof(ImplType);
                value = shiftInitValue<implTypeIsShort>(value, TOTAL_IMPL_BITS);
            }
        }

        clearUnusedBits_();
    }    

    /// Copy constructor from any Integer type.
    /**
       Works like native C types. We may be sliced in the end.
    */
    template <int FromBits> Integer(Integer<FromBits, ImplType> const & from)
    {
        int const mySize = SIZE;
        int const fromSize = Integer<FromBits, ImplType>::SIZE;

        int totalBytes = (mySize < fromSize) ? mySize : fromSize;

        for (int i = 0; i < mySize; ++i)
        {
            data_[i] = (i < totalBytes) ? from.representation_(i) : 0;
        }

        clearUnusedBits_();
    }    

    /// Output function
    /** @warning Incomplete code!!!
        Works only when the ostream is in hex mode. It should check
        the state of the ostream and output accordingly.
    */
    std::ostream & dump(std::ostream & os, bool withSpaces = true) const
    {
        int width = (BITS_USED_IN_UPPER_ENTRY + 3) / 4;

        for (int i = LAST_INDEX; i >= 0; --i)
        {
            os.width(width);
            os << static_cast<int>(data_[i]);
            if (withSpaces) os << ' ';
            width = sizeof (ImplType) * 2;
        }

        return os;
    }

    /** @name Functions that make Integer behave like an int
     */
    //@{
    MyType & operator<<= (int shift)
    {
        shiftLeftWords(shift / TOTAL_IMPL_BITS);
        shiftLeftBits(shift % TOTAL_IMPL_BITS);

        clearUnusedBits_();

        return *this;
    }

    MyType & operator>>= (int shift)
    {
        shiftRightWords(shift / TOTAL_IMPL_BITS);
        shiftRightBits(shift % TOTAL_IMPL_BITS);

        return *this;
    }

    MyType & operator|= (const MyType & rhs)
    {
        for (int i = 0; i < SIZE; ++i) data_[i] |= rhs.data_[i];
        return *this;
    }

    MyType & operator^= (const MyType & rhs)
    {
        for (int i = 0; i < SIZE; ++i) data_[i] ^= rhs.data_[i];
        return *this;
    }

    MyType & operator&= (const MyType & rhs)
    {
        for (int i = 0; i < SIZE; ++i) data_[i] &= rhs.data_[i];
        return *this;
    }

    MyType operator~ () const
    {
        MyType temp(*this);
        
        for (int i = 0; i < SIZE; ++i) temp.data_[i] = ~temp.data_[i];
        
        return temp;
    }    

    bool operator== (const MyType & rhs) const
    {
        int i;
        for (i = 0; i < SIZE; ++i)
        {
            if (data_[i] != rhs.data_[i]) break;
        }
        
        return i == SIZE;
    }

    bool operator!= (const MyType & rhs) const
    {
        return !( *this == rhs);
    }

    MyType & operator+= (const MyType & rhs)
    {
        ImplType carry = 0;

        for (int i = 0; i < SIZE; ++i)
        {
            ImplType oldData = data_[i];
            
            data_[i] += rhs.data_[i] + carry;
            ImplType newCarry = data_[i] < oldData;

            carry = newCarry;
        }

        clearUnusedBits_();
        
        return *this;
    }

    MyType & operator-= (const MyType & rhs)
    {
        ImplType carry = 0;

        for (int i = 0; i < SIZE; ++i)
        {
            ImplType oldData = data_[i];

            if (carry) --data_[i];
            data_[i] -= rhs.data_[i];
            carry = (carry && (oldData == 0)) || (data_[i] > oldData);
        }

        clearUnusedBits_();

        return *this;
    }

    MyType & operator*= (MyType const & rhs)
    {
        // !! Early return statemens:
        if (*this == 0)
        {
#ifdef DEBUG_INTEGER_H
            cout << "early return: this is zero\n";
#endif
            return *this;
        }

        if (rhs == 0)
        {
#ifdef DEBUG_INTEGER_H
            cout << "early return: rhs is zero\n";
#endif
            reset();
            return *this;
        }

        if (*this == 1)
        {
#ifdef DEBUG_INTEGER_H
            cout << "early return: this is one\n";
#endif
            *this = rhs;
            return *this;
        }

        if (rhs == 1)
        {
#ifdef DEBUG_INTEGER_H
            cout << "early return: rhs is one\n";
#endif
            return *this;
        }
        
        MyType result;
        
        for (int i = 0; i < totalHalfWords; ++i)
        {
            ImplType leftVal = getHalfWord(i);
            
            if (leftVal != 0)
            {
                MyType partial;
                ImplType carry = 0;

                int jRange = totalHalfWords - i;
                
                for (int j = 0; j != jRange ; ++j)
                {
#ifdef DEBUG_INTEGER_H
                    cout << "multiplying " << i << " with " << j << '\n';
#endif                    
                    ImplType rightVal = rhs.getHalfWord(j);

                    if (rightVal == 0)
                    {
                        if (carry != 0)
                        {
                            partial.setHalfWord(i + j, carry);
                            carry = 0;
                        }
                    }
                    else
                    {
                        ImplType value = leftVal * rightVal + carry;
                        carry = getUpperHalf(value);

                        partial.setHalfWord(i + j, value);

#ifdef DEBUG_INTEGER_H
                        cout << "carry: " << carry << '\n';
#endif                        
                    }
                }

                result += partial;

#ifdef DEBUG_INTEGER_H
                cout << "result: " << result << '\n';
#endif                
            }
        }

        clearUnusedBits_();

        *this = result;
        return *this;
    }

    MyType & operator/= (MyType const & divisor)
    {
        MyType dividend(*this);
        MyType remainder;

        divide(dividend, divisor, *this, remainder);
        
        return *this;
    }

    MyType & operator%= (MyType const & divisor)
    {
        MyType dividend(*this);
        MyType quotient;
        
        divide(dividend, divisor, quotient, *this);
        
        return *this;
    }

    Integer & operator++ ()
    {
        if (std::numeric_limits<ImplType>::is_bounded &&
            (data_[0] < std::numeric_limits<ImplType>::max()))
        {
            ++data_[0];
        }
        else
        {
            operator+= (1);
        }

        // no need to call clearUnusedBits_(); taken care of by
        // one of the upper branches

        return *this;
    }

    Integer & operator-- ()
    {
        if (std::numeric_limits<ImplType>::is_bounded &&
            (data_[0] > std::numeric_limits<ImplType>::min()))
        {
            --data_[0];
        }
        else
        {
            operator-= (1);
        }

        // no need to call clearUnusedBits_(); taken care of by
        // one of the upper branches

        return *this;
    }

    bool operator < (MyType const & rhs) const
    {
        bool isLess = false;
        
        for (int i = LAST_INDEX; i >= 0; --i)
        {
            if (data_[i] > rhs.data_[i])
            {
                break;
            }
            else if (data_[i] < rhs.data_[i])
            {
                isLess = true;
                break;
            }
        }

        return isLess;
    }

    bool operator > (MyType const & rhs) const
    {
        return !(operator<(rhs)) && !(operator==(rhs));
    }
    //@}

    /// Returns the value as an int.
    /**
       @warning There may be severe loss of data. Safe to use only when the
       value is known to fit in an integer.
    */
    int asInt() const
    {
        int value = 0;

        const int totalPositions = (sizeof (int) < sizeof (ImplType))
            ? 1 : sizeof (int) / sizeof (ImplType);

        int shift = 0;
        for (int i = 0; i < totalPositions; ++i)
        {
            value |= (data_[i] << shift);
            shift += sizeof (ImplType) * 8;
        }

        return value;
    }

    /// Bad! Allows access to the internals.
    /**
       This function is needed due to a limitation of gcc
       or a limitation of Ali's understanding of template friends.
       This function should not be called by client code.
       The problem was that Ali couldn't declare the following:
     
       template <int FromBits> friend class Integer<FromBits, ImplType>;
    
       And the error was: partial specialization `Integer<FromBits,ImplType>'
       declared `friend'
    */
    ImplType const & representation_(int idx) const
    {
        return data_[idx];
    }

};




/// Division algorithm
/**
   The following function is based on the source found at
   http:\\www.bearcave.com\software\divide.htm


   Copyright stuff

   Use of this program, for any purpose, is granted the author,
   Ian Kaplan, as long as this copyright notice is included in
   the source code or any source code derived from this program.
   The user assumes all responsibility for using this code.

   Ian Kaplan, October 1996
*/

template <int BitCount, class ImplType>
void divide(Integer<BitCount, ImplType> const & dividend_in,    // used as a temporary variable
            Integer<BitCount, ImplType> const & divisor,
            Integer<BitCount, ImplType> & quotient,
            Integer<BitCount, ImplType> & remainder )
{
    // !! Early return statements:
    if (divisor == 0)
    {
        assert(0);
    }

    if (divisor > dividend_in)
    {
        quotient = 0;
        remainder = dividend_in;
        return;
    }

    if (divisor == dividend_in)
    {
        quotient = 1;
        remainder = 0;
        return;
    }

    typedef Integer<BitCount, ImplType> MyType;
    int const LAST_INDEX = MyType::LAST_INDEX;
    int const BITS_USED_IN_UPPER_ENTRY = MyType::BITS_USED_IN_UPPER_ENTRY;

    MyType dividend(dividend_in);
    
    quotient = 0;
    remainder = 0;

    int num_bits = BitCount;

    ImplType const upperBitSelector = 1 << (BITS_USED_IN_UPPER_ENTRY - 1);

    MyType lastDividend = 0;
    while (remainder < divisor)
    {
        ImplType bit = (dividend.data_[LAST_INDEX] & upperBitSelector) ? 1 : 0;
        remainder <<= 1;
        remainder.data_[0] |= bit;
        
        lastDividend = dividend;
        dividend <<= 1;
        --num_bits;

#ifdef DEBUG_INTEGER_H
        cout << "numbits " << num_bits << '\n'
             << "remainder " << remainder << '\n'
             << "dividend  " << dividend << '\n';
#endif
    }

    /* The loop, above, always goes one iteration too far.
       To avoid inserting an "if" statement inside the loop
       the last iteration is simply reversed. */

    dividend = lastDividend;
    remainder >>= 1;
    ++num_bits;

    for (int i = 0; i < num_bits; ++i)
    {
        ImplType bit = (dividend.data_[LAST_INDEX] & upperBitSelector) ? 1 : 0;

        remainder <<= 1;
        remainder.data_[0] |= bit;

        MyType t = remainder - divisor;
        ImplType q = (t.data_[LAST_INDEX] & upperBitSelector) ? 0 : 1;
        dividend <<= 1;

        quotient <<= 1;
        quotient.data_[0] |= q;

#ifdef DEBUG_INTEGER_H
        cout << "i " << i << '\n'
             << "remainder " << remainder << '\n'
             << "quotient  " << quotient << '\n';
#endif
        if (q)
        {
            remainder = t;
        }
    }
}

/** @name Non-member functions completing the Integer interface
 */
//@{
template <int BitCount, class ImplType>
bool operator < (Integer<BitCount, ImplType> const & lhs, Integer<BitCount, ImplType> const & rhs)
{
    return lhs.operator<(rhs);
}

template <int BitCount, class ImplType>
bool operator > (Integer<BitCount, ImplType> const & lhs, Integer<BitCount, ImplType> const & rhs)
{
    return lhs.operator>(rhs);
}



template <int BitCount, class ImplType>
std::ostream & operator<< (std::ostream & os, const Integer<BitCount, ImplType> & integer)
{
    return integer.dump(os, false);
}

template <int BitCount, class ImplType>
const Integer<BitCount, ImplType> operator+
(const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType>(lhs) += rhs;
}

template <int BitCount, class ImplType>
const Integer<BitCount, ImplType> operator-
(const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType>(lhs) -= rhs;
}

template <int BitCount, class ImplType>
const Integer<BitCount, ImplType> operator*
(const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType>(lhs) *= rhs;
}

template <int BitCount, class ImplType>
const Integer<BitCount, ImplType> operator/
(const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType>(lhs) /= rhs;
}

template <int BitCount, class ImplType>
const Integer<BitCount, ImplType> operator%
(const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType>(lhs) %= rhs;
}

template <int BitCount, class ImplType>
Integer<BitCount, ImplType> operator| (const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType> (lhs) |= rhs;
}

template <int BitCount, class ImplType>
Integer<BitCount, ImplType> operator& (const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType> (lhs) &= rhs;
}

template <int BitCount, class ImplType>
Integer<BitCount, ImplType> operator>> (const Integer<BitCount, ImplType> & lhs, int shift)
{
    return Integer<BitCount, ImplType>(lhs) >>= shift;
}

template <int BitCount, class ImplType>
Integer<BitCount, ImplType> operator<< (const Integer<BitCount, ImplType> & lhs, int shift)
{
    return Integer<BitCount, ImplType>(lhs) <<= shift;
}

template <int BitCount, class ImplType>
Integer<BitCount, ImplType> operator^ (const Integer<BitCount, ImplType> & lhs, const Integer<BitCount, ImplType> & rhs)
{
    return Integer<BitCount, ImplType> (lhs) ^= rhs;
}
//@}

#endif // INCLUDED_INTEGER_H