Improving a custom integer class

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. should i change my container? are can any of the algorithms be improved? is something running too many times? 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)

sorry for the long code, but there are a lot of operators. and im still missing many of them

/*
integer.h
An integer type that does not have bit size restrictions
by Jason Lee @ [email protected]

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
#if INTPTR_MAX == INT32_MAX
    #define BITS 32
#elif INTPTR_MAX == INT64_MAX
    #define BITS 64
#else
    #error "Environment not 32 or 64-bit."
#endif
// //////////////////////////////////////

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

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

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

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

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


        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>::iterator i = smaller.begin(), j = larger.begin(); i != smaller.end(); 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>::iterator i = smaller.begin(), j = larger.begin(); i != smaller.end(); 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 != j; i++)
                *i ^= 0xff;
            // get highest bit
            int8_t top = 8;
            while (!((1 << top) & *i))
                top--;
            // flip existing bits only, not all 8 bits
            for(; 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;
}

std::string makebin(integer value, unsigned int size = 0){
    // Changes a value into its binary string
    std::string out = "";
    while (value){
        out = "01"[value.data().back() & 1] + out;
        value >>= 1;
    }
    while (out.size() < size)
        out = "0" + out;
    return out;
}

std::string makehex(integer value, unsigned int size = 0){
    // Changes a value into its binary string
    std::string out = "";
    while (value){
        out = "0123456789abcdef"[value.data().back() & 15] + out;
        value >>= 4;
    }
    while (out.size() < size)
        out = "0" + out;
    return out;
}

integer hextointeger(std::string hex_str){
    integer out = 0;
    const std::string num = "0123456789abcdef";
    for(unsigned int x = 0; x < hex_str.size(); x++)
        out += integer(num.find((int) (uint8_t) hex_str[x])) << (integer(hex_str.size() - x - 1) << 2);
    return out;
}

#endif // INTEGER_H

edit: I fixed some of the stuff as per suggestions.

Winston Ewert · Accepted Answer · 2011-07-01 08:47:03Z

#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, 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 unneccesary 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 similiar, 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.

i changed the reverse iterators for | and ^, but i think it works better for &, since any bits over the smaller number will become 0. and how do i reduce the copying? i want to operate on one set of the data, without knowing which one the value, and which is rhs.value without changing value. also, i think that operator char is the same as the standard integer to char cast, so what do you think i should change it to? return a string? — calccrypto, Jul 1 '11 at 14:27

Keith Nicholas · Answer 2 · 2011-07-01 03:34:14Z

up vote 2 down vote

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

should use logical &&

answered Jul 1 '11 at 3:34

Keith Nicholas
96028

add comment

asked	2 years ago
viewed	446 times
active	2 years ago

Explore our sites

Improving a custom integer class

2 Answers

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ integer or ask your own question.

Linked

Hot Network Questions

Explore our sites

Improving a custom integer class

2 Answers

Your Answer

Sign up or login

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ integer or ask your own question.

Linked

Related

Hot Network Questions