cpp-bignumber/src/biginteger.cpp

//
//  biginteger.cpp
//  bigdecimal
//
//  Created by Sam Jaffe on 6/30/17.
//

#include "biginteger.h"
#include "bignum_helper.h"

#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace math;

static void read(int32_t & dst, char const * & str, size_t len) {
  char seg[biginteger::SEG_DIGITS+1] = "";
  strncpy(seg, str, len);
  dst = atoi(seg);
  str += len;
}

biginteger::biginteger()
: is_negative(false), data({0}) {}

biginteger::biginteger(char const * number)
: is_negative(number[0] == '-') {
  if (is_negative) ++number;
  auto len = strlen(number);
  auto elems = len/SEG_DIGITS;
  data.resize(elems);
  if (auto small = len-(elems*SEG_DIGITS)) {
    read(*data.insert(data.end(), 0), number, small);
  }
  for (data_type::size_type idx = elems; idx > 0; --idx) {
    read(data[idx-1], number, SEG_DIGITS);
  }
}

biginteger::biginteger(bool neg, uint64_t value) :
is_negative(neg) {
  uint64_t next{0};
  do {
    next = value / OVER_SEG;
    data.push_back(static_cast<int32_t>(value - (OVER_SEG * next)));
  } while ((value = next) > 0);
}

void biginteger::subtract_impl(biginteger const & lhs, bool is_sub) {
  auto cmp = detail::compare(data, lhs.data);
  if (cmp == 0) {
    *this = biginteger::ZERO;
  } else if (cmp > 0) {
    detail::subtract_nounderflow(data, lhs.data);
  } else {
    data_type tmp{lhs.data};
    is_negative = lhs.is_negative ^ is_sub;
    swap(data, tmp);
    detail::subtract_nounderflow(data, tmp);
  }
}

biginteger & math::operator+=(biginteger & rhs, biginteger const & lhs) {
  if (lhs == biginteger::ZERO) { return rhs; }
  else if (rhs == biginteger::ZERO) { rhs=lhs; }
  else if (rhs.is_negative == lhs.is_negative) {
    detail::add(rhs.data, lhs.data);
  } else {
    rhs.subtract_impl(lhs, false);
  }
  return rhs;
}

biginteger & math::operator-=(biginteger & rhs, biginteger const & lhs) {
  if (lhs == biginteger::ZERO) { return rhs; }
  else if (rhs == biginteger::ZERO) { rhs = -lhs; }
  else if (rhs.is_negative != lhs.is_negative) {
    detail::add(rhs.data, lhs.data);
  } else {
    rhs.subtract_impl(lhs, true);
  }
  return rhs;
}

biginteger & math::operator*=(biginteger & rhs, biginteger const & lhs) {
  bool is_neg = rhs.is_negative != lhs.is_negative;
  if (rhs == biginteger::ZERO || lhs == biginteger::ZERO) {
    rhs = biginteger::ZERO;
  } else if (detail::compare(lhs.data, biginteger::ONE.data) == 0) {
    rhs.is_negative = is_neg;
  } else if (detail::compare(rhs.data, biginteger::ONE.data) == 0) {
    rhs = lhs;
    rhs.is_negative = is_neg;
  } else {
    detail::multiply(rhs.data, lhs.data);
  }
  return rhs;
}

biginteger & math::operator/=(biginteger & rhs, biginteger const & lhs) {
  rhs.is_negative ^= lhs.is_negative;
  if (lhs == biginteger::ZERO) { throw std::domain_error("cannot divide by 0"); }
  else if (rhs == biginteger::ZERO) { rhs = biginteger::ZERO; }
  else if (detail::compare(lhs.data, biginteger::ONE.data) != 0) {
    auto cmp = detail::compare(rhs.data, lhs.data);
    if (cmp < 0) { rhs = biginteger::ZERO; }
    else if (cmp == 0) { rhs.data = {1}; }
    else { rhs.data = detail::divide(rhs.data, lhs.data); }
  }
  return rhs;
}

biginteger biginteger::operator-() const {
  return (*this) * NEGATIVE_ONE;
}

biginteger math::operator+(biginteger rhs, biginteger const & lhs) {
  return rhs += lhs;
}

biginteger math::operator-(biginteger rhs, biginteger const & lhs) {
  return rhs -= lhs;
}

biginteger math::operator*(biginteger rhs, biginteger const & lhs) {
  return rhs *= lhs;
}

biginteger math::operator/(biginteger rhs, biginteger const & lhs) {
  return rhs /= lhs;
}

biginteger math::operator%(biginteger rhs, biginteger const & lhs) {
  if (lhs == biginteger::ZERO) { throw std::domain_error("cannot divide by 0"); }
  else if (lhs == biginteger::ONE ||
           rhs == biginteger::ZERO) { return biginteger::ZERO; }
  else {
    auto cmp = detail::compare(rhs.data, lhs.data);
    if (cmp == 0) { return biginteger::ZERO; }
    else if (cmp > 0) {
      detail::divide(rhs.data, lhs.data);
      if (detail::compare(rhs.data, biginteger::ZERO.data) == 0) { return biginteger::ZERO; }
    }
    if (rhs.is_negative != lhs.is_negative) {
      rhs.is_negative = lhs.is_negative;
      auto tmp = lhs.data;
      swap(rhs.data, tmp);
      detail::subtract_nounderflow(rhs.data, tmp);
    }
    return rhs;
  }
}

bool math::operator==(biginteger const & rhs, biginteger const & lhs) {
  return rhs.is_negative == lhs.is_negative && detail::compare(rhs.data, lhs.data) == 0;
}

bool math::operator!=(biginteger const & rhs, biginteger const & lhs) {
  return !(rhs == lhs);
}

bool math::operator<=(biginteger const & rhs, biginteger const & lhs) {
  return !(rhs > lhs);
}

bool math::operator< (biginteger const & rhs, biginteger const & lhs) {
  if (rhs.is_negative != lhs.is_negative) { return rhs.is_negative; }
  else if (rhs.is_negative) { return detail::compare(rhs.data, lhs.data) > 0; }
  else { return detail::compare(rhs.data, lhs.data) < 0; }
}

bool math::operator>=(biginteger const & rhs, biginteger const & lhs) {
  return !(rhs < lhs);
}

bool math::operator> (biginteger const & rhs, biginteger const & lhs) {
  return lhs < rhs;
}

biginteger const biginteger::ZERO{0}, biginteger::ONE{1}, biginteger::NEGATIVE_ONE{-1};

std::string biginteger::to_string() const {
  std::vector<char> output(biginteger::SEG_DIGITS * data.size() + 2, '\0');
  std::ptrdiff_t idx = 0;
  if (is_negative) { output[0] = '-'; ++idx; }
  idx += sprintf(output.data() + idx, "%d", data[data.size()-1]);
  for (size_t i = data.size()-1; i > 0; --i, idx+=SEG_DIGITS) {
    sprintf(output.data() + idx, "%0.*d", SEG_DIGITS, data[i-1]);
  }
  return output.data();
}