Custom integer class for calculating crypto algorithms

Question

How can I improve upon this integer class that I wrote? I am/will be using this for some calculation intensive crypto algorithms, mainly POLY1305AES. I might even write RSA using this. I know that there are more efficient algorithms for at least the algebraic operators, but I will rewrite those when I learn them.

Right now, I am trying to find anything I might have missed while writing this.

1. Should I change my container?
2. Are can any of the algorithms be improved?
3. Is something running too many times?
4. Anything I should do dynamically?

Note that this code might not run if your compiler is too strict, like ideone.com's compiler (the errors are not caused by the lack of a main(); rather, it thinks some of the operators are ambiguous).

There are a lot of operators and I'm still missing many of them.

/*
integer.h
An integer type that does not have bit size restrictions
by Jason Lee @ calccrypto at yahoo dot com

NOTE: whether or not negative numbers will be implemented
      is yet to be determined
*/

#ifndef INTEGER_H
#define INTEGER_H

#include <cstdlib>
#include <deque>
#include <iostream>
#include <stdint.h>

// Checks platform bitsize using stdint.h
#ifndef BITS
    #define BITS 32
    #if INTPTR_MAX == INT64_MAX
        #undef BITS
        #define BITS 64
    #endif
#endif
// //////////////////////////////////////

class integer{
    private:
        void clean(){
            while ((value.begin() != value.end()) & !value.front())
                value.pop_front();
        }

        integer twos_complement(){
            return (~*this) + 1;
        }

    public:
        std::deque <uint8_t> value;
        // Constructors
        integer(){
            value.clear();
        }

        template <typename T>
        integer(T rhs){
            *this = rhs;
        }

        integer(std::deque <uint8_t> val){
            value = val;
            clean();
        }

        integer(const integer & rhs){
            value = rhs.value;
        }

        //  RHS input args only

        // Assignment Operator
        template <typename T> integer operator=(T rhs){
            value.clear();
            while (rhs > 0){
                value.push_front(rhs & 255);
                rhs >>= 8;
            }
            return *this;
        }

        integer operator=(integer rhs){
            value = rhs.value;
            return *this;
        }

        // Typecast Operators
        operator bool(){
            return (bool) value.size();
        }

        operator char(){
            return (char) value.back();
        }

        operator int(){
            int out = 0, count = 0;
            std::deque <uint8_t>::iterator i = value.end();
            while ((*this > 0) & (count < (BITS >> 3))){
                out += *(i++);
                count++;
            }
            return out;
        }

        operator uint8_t(){
            return value.back();
        }

        operator uint16_t(){
            std::deque <uint8_t>::iterator i = value.end();
            uint16_t out = value.back();
            out += *--i;
            return out;
        }

        operator uint32_t(){
            int out = 0, count = 0;
            std::deque <uint8_t>::iterator i = value.end();
            while ((*this > 0) && (count < 4))
                out += *(i++);
            return out;
        }

        operator uint64_t(){
            int out = 0, count = 0;
            std::deque <uint8_t>::iterator i = value.end();
            while ((*this > 0) && (count < 8))
                out += *(i++);
            return out;
        }

        // Bitwise Operators
        template <typename T> integer operator&(T rhs){
            return *this & integer(rhs);
        }

        integer operator&(integer rhs){
            std::deque <uint8_t> larger = value, smaller = rhs.value;
            if (value.size() < rhs.value.size())
                larger.swap(smaller);
            for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)
                *i &= *j;
            return integer(smaller);
        }

        template <typename T> integer operator|(T rhs){
            return *this | integer(rhs);
        }

        integer operator|(integer rhs){
            std::deque <uint8_t> larger = value, smaller = rhs.value;
            if (value.size() < rhs.value.size())
                larger.swap(smaller);
            while (smaller.size() < larger.size())
                smaller.push_front(0);
            for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)
                *j |= *i;
            return integer(larger);
        }

        template <typename T> integer operator^(T rhs){
            return *this ^ integer(rhs);
        }

        integer operator^(integer rhs){
            std::deque <uint8_t> larger = value, smaller = rhs.value;
            if (value.size() < rhs.value.size())
                larger.swap(smaller);
            while (smaller.size() < larger.size())
                smaller.push_front(0);
            for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)
                *j ^= *i;
            return integer(larger);
        }

        template <typename T> integer operator&=(T rhs){
            *this = *this & rhs;
            return *this;
        }

        integer operator&=(integer rhs){
            *this = *this & rhs;
            return *this;
        }

        template <typename T> integer operator|=(T rhs){
            *this = *this | rhs;
            return *this;
        }

        integer operator|=(integer rhs){
            *this = *this | rhs;
            return *this;
        }

        template <typename T> integer operator^=(T rhs){
            *this = *this ^ rhs;
            return *this;
        }

        integer operator^=(const integer rhs){
            *this = *this ^ rhs;
            return *this;
        }

        integer operator~(){
            std::deque <uint8_t> out = value;
            std::deque <uint8_t>::reverse_iterator i = out.rbegin(), j = out.rend();
            j--;
            for(i = i; i != j; i++)
                *i ^= 0xff;
            // get highest bit
            int8_t top = 8;
            while (!((1 << top) & *i))
                top--;
            for(top = top; top > -1; top--)
                *i ^= 1 << top;
            return integer(out);
        }

        // Bit Shift Operators
        integer operator<<(unsigned int shift){
            if (*this == 0)
                return *this;
            std::deque <uint8_t> out = value;
            for(unsigned int i = 0; i < (shift >> 3); i++)
                out.push_back(0);
            shift &= 7;
            if (shift){
                out.push_front(0);
                std::deque <uint8_t>::iterator i = out.begin(), j = out.end();
                i++; j--;
                for(; i != j; i++){
                    uint8_t temp = *i >> (8 - shift);
                    --i;
                    *i += temp;
                    i++;
                    *i = (uint8_t) (*i << shift);
                }
                uint8_t temp = *i >> (8 - shift);
                i--;
                *i += temp;
                i++;
                *i <<= shift;
            }
            return integer(out);
        }

        integer operator<<(integer shift){
            integer out = *this;
            for(integer i = 0; i < (shift >> 3); i++)
               out <<= 8;
            for(integer i = 0; i < (shift & 7); i++)
                out <<= 1;
            return out;
        }

        integer operator>>(unsigned int shift){
            if (shift >= bits())
                return integer(0);
            std::deque <uint8_t> out = value;
            for(unsigned int i = 0; i < (shift >> 3); i++)
                out.pop_back();
            shift &= 7;
            if (shift){
                std::deque <uint8_t>::reverse_iterator i = out.rbegin(), j = out.rend();
                j--;
                for(; i != j; i++){
                    *i >>= shift;
                    i++;
                    uint8_t temp = *i << (8 - shift);
                    i--;
                    *i += temp;
                }
                *j >>= shift;
            }
            return integer(out);
        }

        integer operator>>(integer shift){
            integer out = *this;
            for(integer i = 0; i < (shift >> 3); i++)
               out >>= 8;
            for(integer i = 0; i < (shift & 7); i++)
                out >>= 1;
            return out;
        }

        integer operator<<=(size_t shift){
            *this = *this << shift;
            return *this;
        }

        integer operator>>=(size_t shift){
            *this = *this >> shift;
            return *this;
        }

        integer operator<<=(integer shift){
            *this = *this << shift;
            return *this;
        }

        integer operator>>=(integer  shift){
            *this = *this >> shift;
            return *this;
        }

        // Logical Operators
        bool operator!(){
            return !(bool) *this;
        }

        template <typename T> bool operator&&(T rhs){
            return (bool) (*this && rhs);
        }

        template <typename T> bool operator&&(integer rhs){
            return (bool) *this && (bool) rhs;
        }

        template <typename T> bool operator||(T rhs){
            return ((bool) *this) || rhs;
        }

        template <typename T> bool operator||(integer rhs){
            return ((bool) *this) || (bool) rhs;
        }

        // Comparison Operators
        template <typename T> bool operator==(T rhs){
            return (value == integer(rhs).value);
        }

        bool operator==(integer rhs){
            return (value == rhs.value);
        }

        template <typename T> bool operator!=(T rhs){
            return !(*this == rhs);
        }

        bool operator!=(integer rhs){
            return !(*this == rhs);
        }

        template <typename T> bool operator>(T rhs){
            return (*this > integer(rhs));
        }

        bool operator>(integer rhs){
            if (bits() > rhs.bits())
                return true;
            if (bits() < rhs.bits())
                return false;
            if (value == rhs.value)
                return false;
            for(unsigned int i = 0; i < value.size(); i++)
                if (value[i] != rhs.value[i])
                    return value[i] > rhs.value[i];
            return false;
        }

        template <typename T> bool operator<(T rhs){
            return (*this < integer(rhs));
        }

        bool operator<(integer rhs){
            if (bits() < rhs.bits())
                return true;
            if (bits() > rhs.bits())
                return false;
            if (value == rhs.value)
                return false;
            for(unsigned int i = 0; i < value.size(); i++)
                if (value[i] != rhs.value[i])
                    return value[i] < rhs.value[i];
            return false;
        }

        template <typename T> bool operator>=(T rhs){
            return ((*this > rhs) | (*this == rhs));
        }

        bool operator>=(integer rhs){
            return ((*this > rhs) | (*this == rhs));
        }

        template <typename T> bool operator<=(T rhs){
            return ((*this < rhs) | (*this == rhs));
        }

        bool operator<=(integer rhs){
            return ((*this < rhs) | (*this == rhs));
        }

        // Arithmetic Operators
        template <typename T> integer operator+(T rhs){
            return *this + integer(rhs);
        }

        integer operator+(integer rhs){
            if (rhs == 0)
                return *this;
            if (*this == 0)
                return rhs;
            std::deque <uint8_t> top = value, bottom = rhs.value;
            if (value.size() < rhs.value.size())
                top.swap(bottom);
            top.push_front(0);
            while (bottom.size() + 1 < top.size())
                bottom.push_front(0);
            bool carry = false, next_carry;
            for(std::deque <uint8_t>::reverse_iterator i = top.rbegin(), j = bottom.rbegin(); j != bottom.rend(); i++, j++){
                next_carry = ((*i + *j + carry) > 255);
                *i += *j + carry;
                carry = next_carry;
            }
            if (carry)
                *top.begin() = 1;
            return integer(top);
        }

        template <typename T> integer operator+=(T rhs){
            *this = *this + rhs;
            return *this;
        }

        integer operator+=(integer rhs){
            *this = *this + rhs;
            return *this;
        }

        template <typename T> integer  operator-(T rhs){
            return *this - integer(rhs);
        }

        integer operator-(integer rhs){
            if (rhs == 0)
                return *this;
            if (*this == rhs)
                return integer(0);
            if (rhs > *this)
                exit(2);// to be worked on
            unsigned int old_b = rhs.bits();
            rhs = rhs.twos_complement();
            for(unsigned int i = old_b; i < bits(); i++)
                rhs ^= integer(1) << i;
            return (*this + rhs) & (~(integer(1) << bits()));   // Flip bits to get max of 1 << x
        }

        template <typename T> integer operator-=(T rhs){
            *this = *this - rhs;
            return *this;
        }

        integer operator-=(integer rhs){
            *this = *this - rhs;
            return *this;
        }

        template <typename T> integer operator*(T rhs){
            return *this * integer(rhs);
        }

        integer operator*(integer rhs){
            // long multiplication
            unsigned int zeros = 0;
            std::deque <uint8_t> row;
            std::deque <std::deque <uint8_t> > temp;
            integer out = 0;
            for(std::deque <uint8_t>::reverse_iterator i = value.rbegin(); i != value.rend(); i++){
                row = std::deque <uint8_t>(zeros++, 0); // zeros on the right hand side
                uint8_t carry = 0;
                for(std::deque <uint8_t>::reverse_iterator j = rhs.value.rbegin(); j != rhs.value.rend(); j++){
                    uint16_t prod = (uint16_t(*i) * uint16_t(*j)) + carry;// multiply through
                    row.push_front((uint8_t) prod);
                    carry = prod >> 8;
                }
                if (carry != 0)
                    row.push_front(carry);
                out += integer(row);
            }
            return out;
        }

        template <typename T> integer operator*=(T rhs){
            *this = *this * integer(rhs);
            return *this;
        }

        integer operator*=(integer rhs){
            *this = *this * rhs;
            return *this;
        }

        template <typename T> integer operator/(T rhs){
            return *this / integer(rhs);
        }

        integer operator/(integer rhs){
            if (rhs == 0){
                std::cout << "Error: division or modulus by zero" << std::endl;
                exit(1);
            }
            if (rhs == 1)
                return *this;
            if (*this == rhs)
                return integer(1);
            if ((*this == 0) | (*this < rhs))
                return integer(0);
            // Checks for divisors that are powers of two
            uint16_t s = 0;
            integer copyd(rhs);
            while ((copyd & 1) == 0){
                copyd >>= 1;
                s++;
            }
            if (copyd == 1)
                return *this >> s;
            ////////////////////////////////////////////////
            integer copyn(*this), quotient = 0;
            while (copyn >= rhs){
                copyd = rhs;
                integer temp(1);
                while ((copyn >> 1) > copyd){
                    copyd <<= 1;
                    temp <<= 1;
                }
                copyn -= copyd;
                quotient += temp;
            }
            return quotient;
        }

        template <typename T> integer operator/=(T rhs){
            *this = *this / integer(rhs);
            return *this;
        }

        integer operator/=(integer rhs){
            *this = *this / rhs;
            return *this;
        }

        template <typename T> integer operator%(T rhs){
            return *this - (integer(rhs) * (*this / integer(rhs)));
        }

        integer operator%(integer rhs){
            *this = *this - (*this / rhs) * rhs;
            return *this;
        }

        template <typename T> integer operator%=(T rhs){
            *this = *this % integer(rhs);
            return *this;
        }

        integer operator%=(integer rhs){
            *this = *this % rhs;
            return *this;
        }

        // Increment Operator
        integer operator++(){
            *this += 1;
            return *this;
        }

        integer operator++(int){
            integer temp(*this);
            ++*this;
            return temp;
        }

        // Decrement Operator
        integer operator--(){
            *this -= 1;
            return *this;
        }

        integer operator--(int){
            integer temp(*this);
            --*this;
            return temp;
        }

        // get private value
        unsigned int bits(){
            if (value.empty())
                return 0;
            unsigned int out = value.size() << 3;
            uint8_t top = 128;
            while (!(value.front() & top)){
                out--;
                top >>= 1;
            }
            return out;
        }

        std::deque <uint8_t> data(){
            return value;
        }
};
// lhs type T as first arguemnt

// Bitwise Operators
template <typename T> T operator&(T lhs, integer rhs){
    return (T) (rhs & lhs);
}

template <typename T> T operator|(T lhs, integer rhs){
    return (T) (rhs | lhs);
}

template <typename T> T operator^(T lhs, integer rhs){
    return (T) (lhs * rhs);
}

template <typename T> T operator&=(T & lhs, integer rhs){
    lhs = (T) (integer(lhs) & rhs);
    return lhs;
}

template <typename T> T operator|=(T & lhs, integer rhs){
    lhs = (T) (integer(lhs) | rhs);
    return lhs;
}

template <typename T> T operator^=(T & lhs, integer rhs){
    lhs = (T) (integer(lhs) ^ rhs);
    return lhs;
}

// Comparison Operators
template <typename T> bool operator==(T lhs, integer rhs){
    return (rhs == lhs);
}

template <typename T> bool operator!=(T lhs, integer rhs){
    return (rhs != lhs);
}

template <typename T> bool operator>(T lhs, integer rhs){
    return (rhs < lhs);
}

template <typename T> bool operator<(T lhs, integer rhs){
    return (rhs > lhs);
}

template <typename T> bool operator>=(T lhs, integer rhs){
    return (rhs <= lhs);
}

template <typename T> bool operator<=(T lhs, integer rhs){
    return (rhs >= lhs);
}

// Arithmetic Operators
template <typename T> T operator+(T lhs, integer rhs){
    return (T) (rhs + lhs);
}

template <typename T> T & operator+=(T & lhs, integer rhs){
    lhs = lhs + rhs;
    return lhs;
}

template <typename T> T operator-(T lhs, integer rhs){
    return (T) (integer(rhs) - lhs);
}

template <typename T> T & operator-=(T & lhs, integer rhs){
    lhs = lhs - rhs;
    return lhs;
}

template <typename T> T operator*(T lhs, integer rhs){
    return (T) (rhs * lhs);
}

template <typename T> T & operator*=(T & lhs, integer rhs){
    lhs = (T) (rhs * lhs);
    return lhs;
}

template <typename T> T operator/(T lhs, integer rhs){
    return (T) (integer(lhs) / rhs);
}

template <typename T> T & operator/=(T & lhs, integer rhs){
    lhs = lhs / rhs;
    return lhs;
}
template <typename T> T operator%(T lhs, integer rhs){
    return (T) (integer(lhs) % rhs);
}

template <typename T> T & operator%=(T & lhs, integer rhs){

    lhs = lhs % rhs;
    return lhs;
}

// IO Operator
std::ostream & operator<<(std::ostream & stream, integer rhs){
    std::string out = "";
    if (rhs == 0)
        out = "0";
    else {
        int div = 10;
        if (stream.flags() & stream.oct)
            div = 8;
        if (stream.flags() & stream.dec)
            div = 10;
        if (stream.flags() & stream.hex)
            div = 16;
        while (rhs > 0){
            out = "0123456789abcdef"[(rhs % div).data().back()] + out;
            rhs /= div;
        }
    }
    stream << out;
    return stream;
}

#endif // INTEGER_H

Answer 1

#define BITS 32
#if INTPTR_MAX == INT64_MAX
    #undef BITS
    #define BITS 64
#endif

#define it, and optionally #undefing it is ugly. Use an else block with parallel #defines instead.

    integer(){
        value.clear();
    }

value will be empty when the object is constructed, so there is no need to clear it.

    operator char(){
        return (char) value.back();
    }

Converting to a char by ignoring everything but one element strikes me as ill-advised.

   operator uint64_t(){
        int out = 0, count = 0;
        std::deque <uint8_t>::iterator i = value.end();
        while ((*this > 0) && (count < 8))
            out += *(i++);
        return out;
    }

Do you really need to convert to so many different integer types? You should probably assert/throw an error if the value cannot be stored in the output format type.

    integer operator|(integer rhs){
        std::deque <uint8_t> larger = value, smaller = rhs.value;

You make unnecessary copies of the data here.

        if (value.size() < rhs.value.size())
            larger.swap(smaller);
        while (smaller.size() < larger.size())
            smaller.push_front(0);
        for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)

Why are you using a reverse iterator?

            *j |= *i;
        return integer(larger);
    }

The & operator is very similar; they should be refactored to eliminate duplicate code.

    integer operator~(){
        std::deque <uint8_t> out = value;
        std::deque <uint8_t>::reverse_iterator i = out.rbegin(), j = out.rend();
        j--;

i and j are not very helpful names.

        for(i = i; i != j; i++)
            *i ^= 0xff;
        // get highest bit
        int8_t top = 8;
        while (!((1 << top) & *i))
            top--;
        for(top = top; top > -1; top--)
            *i ^= 1 << top;
        return integer(out);
    }

Can't you just apply ~ to all of the elements? At any rate, some comments as to why you are doing what you are doing here would be useful.

Answer 2

For here:

while ((value.begin() != value.end()) & !value.front())

You should use logical && instead of &.

Answer 3

• You should also be using <cstdint> instead of <stdint.h>. Stick to just the C++ equivalent libraries that are all incorporated in the std namespace.

• The class name integer should be capitalized to Integer. In general, class names, being the name of a type, should be named differently from functions and objects.

• For error outputs, use std::cerr instead of std::cout.

  You can also give a comment at the top, stating that <iostream> is included only for this purpose, considering that this class doesn't primarily deal with I/O operations.

• With so many overloaded operators, it may be beneficial to move the class implementation to a separate .cpp file. The templated functions would best stay in the header file, but they can also be moved outside of the class declaration and placed after it. That way, it would be easier to see the actual declarations in case just those need to be maintained.