cpp-bignumber/src/biginteger.cpp

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

#include "math/biginteger.h"
#include "math/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(number_format fmt) 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();
}