path: root/number.cpp

#include <iomanip>
#include <sstream>
#include "number.h"

number::number(std::uint64_t n)
{
    if (n == 0) {
        return;
    }

    _operands.push_back(n & UINT32_MAX);

    if (n > UINT32_MAX) {
        _operands.push_back(n >> 32);
    }
}

/* Type Conversion {{{ */

std::string
number::to_hex_string() const
{
    if (_operands.empty()) {
        return std::string("0x0");
    }

    std::ostringstream ss;

    ss << "0x" << std::hex;

    for (auto it = _operands.crbegin(); it != _operands.crend(); ++it) {
        ss << *it;

        /* If more operands are present, successive ones must be padded. */
        ss << std::setfill('0');
        ss << std::setw(8);
    }

    return ss.str();
}

std::string
number::to_dec_string() const
{
    if (_operands.empty()) {
        return std::string("0");
    }

    std::ostringstream ss;

    ss << std::dec;

    if (_operands.size() == 1) {
        ss << _operands.front();
    } else {
        /* TODO */
        ss << "[Not implemented]";
    }

    return ss.str();
}

std::uint32_t
number::to_uint32() const
{
    if (*this > UINT32_MAX) {
        throw std::out_of_range("> UINT32_MAX");
    }

    return (*this == 0) ? 0 : _operands.front();
}

std::uint64_t
number::to_uint64() const
{
    auto size = _operands.size();

    if (size > 2) {
        throw std::out_of_range("> UINT64_MAX");
    }

    std::uint64_t result = 0;

    for (auto it = _operands.crbegin(); it != _operands.crend(); ++it) {
        result <<= 32;

        result |= (*it);
    }

    return result;
}

number::operator bool() const
{
    return *this != 0;
}

/* }}} */
/* Operations {{{ */

number
number::operator+(const number &n) const
{
    number result;

    auto it = _operands.cbegin();
    auto it_n = n._operands.cbegin();

    bool carry = false;

    while (it != _operands.cend() || it_n != n._operands.cend()) {
        const auto n1 = (it != _operands.cend()) ? *it++ : 0;
        const auto n2 = (it_n != n._operands.cend()) ? *it_n++ : 0;

        result._operands.push_back(n1 + n2 + (carry ? 1 : 0));

        if (carry && (n1 == UINT32_MAX)) {
            carry = true;
        } else {
            carry = ((UINT32_MAX - n1 - (carry ? 1 : 0)) < n2);
        }
    }

    if (carry) {
        result._operands.push_back(1);
    }

    return result;
}

number
number::operator*(const number &n) const
{
    number result;

    if (n < UINT32_MAX && *this < UINT32_MAX) {
        return number(1ull * to_uint32() * n.to_uint32());
    }

    int level = 0;

    for (auto it_low: _operands) {
        number intermediate;

        std::uint32_t carry = 0;

        for (auto it_high: n._operands) {
            std::uint64_t tmp = 1ull * it_low * it_high + carry;

            intermediate._operands.push_back(tmp & UINT32_MAX);

            carry = tmp >> 32;
        }

        if (carry) {
            intermediate._operands.push_back(carry);
        }

        for (auto j = 0; j < level; ++j) {
            intermediate <<= 32;
        }

        result += intermediate;

        ++level;
    }

    return result;
}

number
number::operator<<(std::uint32_t shift) const
{
    if (*this == 0) {
        return 0;
    }

    number result(*this);

    /*
     * Since, internally, we store 32-bits-wide integers, we can just insert
     * "shift / 32" new integers at the beginning.
     */
    for (unsigned int i = 0; i < shift / 32; ++i) {
        result._operands.push_front(0);
    }

    shift %= 32;

    std::uint32_t carry = 0;

    for (auto &operand: result._operands) {
        std::uint32_t tmp = ((1ull * operand) << shift) + carry;

        carry = ((1ull * operand) >> (32 - shift));

        operand = tmp;
    }

    if (carry) {
        result._operands.push_back(carry);
    }

    return result;
}

number
number::operator>>(std::uint32_t shift) const
{
    number result(*this);

    /*
     * Since, internally, we store 32-bits-wide integers, we can just get rid
     * of "shift / 32" first integers.
     */
    for (unsigned int i = 0; i < shift / 32; ++i) {
        if (result == 0) {
            return 0;
        }

        result._operands.pop_front();
    }

    shift %= 32;

    std::uint32_t carry = 0;

    for (auto it = result._operands.rbegin(); it != result._operands.rend(); ++it) {
        auto &operand = *it;

        std::uint32_t tmp = ((1ull * operand) >> shift) | carry;

        carry = ((1ull * operand) << (32 - shift));

        operand = tmp;
    }

    result.shrink_to_fit();

    return result;
}

/* }}} */
/* Comparison operators {{{ */

bool
number::operator<(const number &n) const
{
    const auto size = this->_operands.size();

    if (size < n._operands.size()) {
        return true;
    }

    if (size > n._operands.size()) {
        return false;
    }

    /* Because first item is the least significant. */
    auto l1(this->_operands);
    auto l2(n._operands);

    l1.reverse();
    l2.reverse();

    return l1 < l2;
}

bool
number::operator>(const number &n) const
{
    return n.operator<(*this);
}

bool
number::operator<=(const number &n) const
{
    return operator<(n) || operator==(n);
}

bool
number::operator>=(const number &n) const
{
    return operator>(n) || operator==(n);
}

bool
number::operator==(const number &n) const
{
    return _operands == n._operands;
}

bool
number::operator!=(const number &n) const
{
    return _operands != n._operands;
}

bool
number::operator!() const
{
    return !static_cast<bool>(*this);
}

/* }}} */
/* Assignment operators {{{ */

number &
number::operator+=(const number &n)
{
    *this = *this + n;

    return *this;
}

number &
number::operator<<=(std::uint32_t n)
{
    *this = *this << n;

    return *this;
}

number &
number::operator>>=(std::uint32_t n)
{
    *this = *this >> n;

    return *this;
}

number &
number::operator++()
{
    *this = *this + 1;

    return *this;
}

/* }}} */

void
number::shrink_to_fit()
{
    while (_operands.back() == 0) {
        _operands.pop_back();
    }
}

std::ostream &
operator<<(std::ostream &os, const number &n)
{
    return os << n.to_hex_string();
}