cpp-bignumber/src/bigdecimal.cpp

//
//  bigdecimal.cpp
//  bigdecimal
//
//  Created by Sam Jaffe on 7/3/17.
//

#include "math/bigdecimal.h"

#include <cstdlib>

#include "bignum_helper.h"

using namespace math;

static int32_t add_scale(int32_t scale) {
  return scale / bigdecimal::SEG_DIGITS + (scale > 0 ? 1 : 0);
}

static size_t mul_scale(int32_t scale) {
  return scale < 0 ? 0 : size_t(add_scale(scale));
}

static bool all_zero(bigdecimal::data_type const & data, size_t from) {
  for (size_t i = from; i > 0; --i) {
    if (data[i - 1] != 0) return false;
  }
  return true;
}

static int compare(bigdecimal::data_type const & ldata,
                   bigdecimal::data_type const & rdata, size_t offset) {
  auto cmp = detail::compare(ldata, rdata, offset);
  if (cmp == 0) { return !all_zero(ldata, offset); }
  return cmp;
}

static int compare(bigdecimal::data_type const & ldata, int32_t lsteps,
                   bigdecimal::data_type const & rdata, int32_t rsteps) {
  return lsteps < rsteps ? -compare(rdata, ldata, size_t(rsteps - lsteps))
                         : compare(ldata, rdata, size_t(lsteps - rsteps));
}

static bool is_one(bigdecimal::data_type const & data, int32_t scale) {
  static bigdecimal::data_type ONE = {1};
  return compare(data, add_scale(scale), ONE, 0) == 0;
}

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

static void read_segment(bigdecimal::data_type & data, char const * number,
                         size_t len) {
  auto elems = len / bigdecimal::SEG_DIGITS;
  data.resize(elems);
  if (auto small = len - (elems * bigdecimal::SEG_DIGITS)) {
    read(*data.emplace(data.end()), number, small);
  }
  for (size_t idx = elems; idx > 0; --idx) {
    read(data[idx - 1], number, bigdecimal::SEG_DIGITS);
  }
}

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

bigdecimal::bigdecimal(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);
}

bigdecimal::bigdecimal(char const * number) : is_negative(number[0] == '-') {
  if (is_negative) { ++number; }
  if (auto p = strchr(number, '.')) {
    read_segment(data, number, size_t(p - number));
    number = p + 1;
    set_scale(int32_t(strlen(number)));
    size_t elems = size_t(scale() / SEG_DIGITS);
    data.insert(data.begin(), elems, 0);
    for (size_t idx = elems; idx > 0; --idx) {
      read(data[idx - 1], number, SEG_DIGITS);
    }
    if (auto l = strlen(number)) {
      data.insert(data.begin(), atoi(number) * detail::powers[SEG_DIGITS - l]);
    }
  } else {
    read_segment(data, number, strlen(number));
  }
}

void bigdecimal::set_value(bigdecimal const & other) {
  int32_t oscale = scale();
  operator=(other);
  rescale(oscale);
}

void bigdecimal::set_scale(int32_t nscale) {
  scale_ = nscale;
  steps_ = add_scale(nscale);
}

void bigdecimal::rescale(int32_t nscale) {
  auto const diff = steps_ - add_scale(nscale);
  if (diff > 0) {
    data.erase(data.begin(), data.begin() + diff);
    if (data.empty()) { data.push_back(0); }
  } else if (diff < 0) {
    data.insert(data.begin(), size_t(-diff), 0);
  }
  auto const idx = -nscale % SEG_DIGITS;
  if (scale() > nscale && nscale < 0 && idx) {
    data.front() /= detail::powers[idx];
    data.front() *= detail::powers[idx];
  }
  set_scale(nscale);
}

void bigdecimal::subtract_impl(bigdecimal const & lhs, bool is_sub) {
  size_t const offset = size_t(steps_ - lhs.steps_);
  auto cmp = detail::compare(data, lhs.data, offset);
  if (cmp == 0) {
    set_value(bigdecimal::ZERO);
  } else if (cmp > 0) {
    detail::subtract_nounderflow(data, lhs.data, offset);
  } else {
    bigdecimal tmp{lhs};
    tmp.is_negative = lhs.is_negative ^ is_sub;
    swap(*this, tmp);
    rescale(tmp.scale());
    detail::subtract_nounderflow(data, tmp.data);
  }
}

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

bigdecimal & math::operator+=(bigdecimal & rhs, bigdecimal const & lhs) {
  int32_t const new_scale = std::max(rhs.scale(), lhs.scale());
  rhs.rescale(new_scale);
  size_t const offset = size_t(rhs.steps_ - lhs.steps_);
  if (lhs == bigdecimal::ZERO) {
    return rhs;
  } else if (rhs == bigdecimal::ZERO) {
    rhs.set_value(lhs);
  } else if (rhs.is_negative == lhs.is_negative) {
    detail::add(rhs.data, lhs.data, offset);
  } else {
    rhs.subtract_impl(lhs, false);
  }
  return rhs;
}

bigdecimal & math::operator-=(bigdecimal & rhs, bigdecimal const & lhs) {
  int32_t const new_scale = std::max(rhs.scale(), lhs.scale());
  rhs.rescale(new_scale);
  size_t const offset = size_t(rhs.steps_ - lhs.steps_);
  if (lhs == bigdecimal::ZERO) {
    return rhs;
  } else if (rhs == bigdecimal::ZERO) {
    rhs.set_value(-lhs);
  } else if (rhs.is_negative != lhs.is_negative) {
    detail::add(rhs.data, lhs.data, offset);
  } else {
    rhs.subtract_impl(lhs, true);
  }
  return rhs;
}

bigdecimal & math::operator*=(bigdecimal & rhs, bigdecimal const & lhs) {
  int32_t const new_scale = rhs.scale() + lhs.scale();
  bool is_neg = rhs.is_negative != lhs.is_negative;
  if (rhs == bigdecimal::ZERO || lhs == bigdecimal::ZERO) {
    rhs = bigdecimal::ZERO;
  } else if (is_one(lhs.data, lhs.scale())) {
    rhs.is_negative = is_neg;
  } else if (is_one(rhs.data, rhs.scale())) {
    rhs = lhs;
    rhs.is_negative = is_neg;
  } else {
    detail::multiply(rhs.data, lhs.data);
    auto diff = add_scale(new_scale) - rhs.steps_ - lhs.steps_;
    if (diff < 0) { rhs.data.erase(rhs.data.begin(), rhs.data.begin() - diff); }
    rhs.set_scale(new_scale);
    return rhs;
  }
  rhs.rescale(new_scale);
  return rhs;
}

bigdecimal & math::operator/=(bigdecimal & rhs, bigdecimal const & lhs) {
  int32_t const new_scale = rhs.scale() - lhs.scale();
  rhs.is_negative ^= lhs.is_negative;
  if (lhs == bigdecimal::ZERO) {
    throw std::domain_error("cannot divide by 0");
  } else if (rhs == bigdecimal::ZERO) {
    rhs = bigdecimal::ZERO;
  } else if (!is_one(lhs.data, lhs.scale())) {
    if (rhs.scale() < new_scale) rhs.rescale(new_scale);
    auto cmp = detail::compare(rhs.data, lhs.data);
    if (cmp < 0) {
      rhs = bigdecimal::ZERO;
    } else if (cmp == 0) {
      return rhs = {1, new_scale};
    } else {
      rhs.data = detail::divide(rhs.data, lhs.data);
      auto diff = add_scale(new_scale) - rhs.steps_ - lhs.steps_;
      if (diff > 0) {
        rhs.data.erase(rhs.data.begin(), rhs.data.begin() + diff);
      }
      if (rhs.data.size() <= mul_scale(new_scale)) { rhs.data.push_back(0); }
      rhs.set_scale(new_scale);
      return rhs;
    }
  }
  rhs.rescale(new_scale);
  return rhs;
}

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

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

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

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

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

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

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

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

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

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

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

std::string bigdecimal::to_string(number_format const & fmt) const {
  size_t const decimal_split = size_t(std::max(0, steps_));
  int32_t const hidden = std::max(0, SEG_DIGITS * (-scale() / SEG_DIGITS));
  size_t const chars = SEG_DIGITS * data.size() + size_t(hidden);
  std::vector<char> output(chars + 3, '\0');
  char * ptr = output.data();
  if (is_negative) { *ptr++ = '-'; }
  ptr += sprintf(ptr, "%d", data.back());
  for (size_t i = data.size() - 1; i > decimal_split; --i) {
    ptr += sprintf(ptr, "%0.*d", SEG_DIGITS, data[i - 1]);
  }
  if (scale() > 0) {
    *ptr++ = '.';
    for (size_t i = decimal_split; i > 1; --i) {
      ptr += sprintf(ptr, "%0.*d", SEG_DIGITS, data[i - 1]);
    }
    int32_t const val = scale() % SEG_DIGITS;
    sprintf(ptr, "%0.*d", val, data[0] / detail::powers[SEG_DIGITS - val]);
  } else if (data.back()) {
    sprintf(ptr, "%0.*d", hidden, 0);
  }
  return detail::apply(fmt, output.data());
}