76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <2geom/coord.h>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <stdint.h>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <cstdlib>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <cassert>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <cstring>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <climits>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <cstdarg>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#include <cmath>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#ifndef ASSERT

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define ASSERT(condition) \

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński assert(condition);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#ifndef UNIMPLEMENTED

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define UNIMPLEMENTED() (abort())

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#ifndef UNREACHABLE

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define UNREACHABLE() (abort())

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define UINT64_2PART_C(a, b) (((static_cast<uint64_t>(a) << 32) + 0x##b##u))

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#ifndef ARRAY_SIZE

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define ARRAY_SIZE(a) \

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ((sizeof(a) / sizeof(*(a))) / \

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static_cast<size_t>(!(sizeof(a) % sizeof(*(a)))))

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#ifndef DISALLOW_COPY_AND_ASSIGN

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define DISALLOW_COPY_AND_ASSIGN(TypeName) \

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński TypeName(const TypeName&); \

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void operator=(const TypeName&)

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#ifndef DISALLOW_IMPLICIT_CONSTRUCTORS

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define DISALLOW_IMPLICIT_CONSTRUCTORS(TypeName) \

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński TypeName(); \

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DISALLOW_COPY_AND_ASSIGN(TypeName)

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#if defined(__GNUC__)

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define DOUBLE_CONVERSION_UNUSED __attribute__((unused))

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#else

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#define DOUBLE_CONVERSION_UNUSED

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskinamespace Geom {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskinamespace {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiinline int StrLength(const char* string) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński size_t length = strlen(string);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(length == static_cast<size_t>(static_cast<int>(length)));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return static_cast<int>(length);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate <typename T>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiclass Vector {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński public:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Vector() : start_(NULL), length_(0) {}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Vector(T* data, int length) : start_(data), length_(length) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(length == 0 || (length > 0 && data != NULL));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Vector<T> SubVector(int from, int to) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(to <= length_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(from < to);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(0 <= from);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Vector<T>(start() + from, to - from);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int length() const { return length_; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool is_empty() const { return length_ == 0; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński T* start() const { return start_; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński T& operator[](int index) const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(0 <= index && index < length_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return start_[index];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński T& first() { return start_[0]; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński T& last() { return start_[length_ - 1]; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński private:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński T* start_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int length_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński};

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate <class Dest, class Source>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiinline Dest BitCast(const Source& source) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DOUBLE_CONVERSION_UNUSED

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński typedef char VerifySizesAreEqual[sizeof(Dest) == sizeof(Source) ? 1 : -1];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Dest dest;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński memmove(&dest, &source, sizeof(dest));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return dest;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate <class Dest, class Source>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiinline Dest BitCast(Source* source) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return BitCast<Dest>(reinterpret_cast<uintptr_t>(source));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic uint64_t double_to_uint64(double d) { return BitCast<uint64_t>(d); }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic double uint64_to_double(uint64_t d64) { return BitCast<double>(d64); }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiclass DiyFp {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński public:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kSignificandSize = 64;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp() : f_(0), e_(0) {}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp(uint64_t f, int e) : f_(f), e_(e) {}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Subtract(const DiyFp& other) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(e_ == other.e_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(f_ >= other.f_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński f_ -= other.f_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static DiyFp Minus(const DiyFp& a, const DiyFp& b) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp result = a;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result.Subtract(b);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Multiply(const DiyFp& other) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint64_t kM32 = 0xFFFFFFFFU;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t a = f_ >> 32;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t b = f_ & kM32;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t c = other.f_ >> 32;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d = other.f_ & kM32;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t ac = a * c;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t bc = b * c;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t ad = a * d;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t bd = b * d;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t tmp = (bd >> 32) + (ad & kM32) + (bc & kM32);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // By adding 1U << 31 to tmp we round the final result.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Halfway cases will be round up.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński tmp += 1U << 31;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t result_f = ac + (ad >> 32) + (bc >> 32) + (tmp >> 32);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński e_ += other.e_ + 64;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński f_ = result_f;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static DiyFp Times(const DiyFp& a, const DiyFp& b) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp result = a;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result.Multiply(b);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Normalize() {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(f_ != 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t f = f_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int e = e_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint64_t k10MSBits = UINT64_2PART_C(0xFFC00000, 00000000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while ((f & k10MSBits) == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński f <<= 10;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński e -= 10;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while ((f & kUint64MSB) == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński f <<= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński e--;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński f_ = f;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński e_ = e;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static DiyFp Normalize(const DiyFp& a) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp result = a;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result.Normalize();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t f() const { return f_; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int e() const { return e_; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void set_f(uint64_t new_value) { f_ = new_value; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void set_e(int new_value) { e_ = new_value; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński private:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const uint64_t kUint64MSB = UINT64_2PART_C(0x80000000, 00000000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t f_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int e_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński};

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiclass Double {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński public:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const uint64_t kSignMask = UINT64_2PART_C(0x80000000, 00000000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const uint64_t kExponentMask = UINT64_2PART_C(0x7FF00000, 00000000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const uint64_t kSignificandMask = UINT64_2PART_C(0x000FFFFF, FFFFFFFF);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const uint64_t kHiddenBit = UINT64_2PART_C(0x00100000, 00000000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kPhysicalSignificandSize = 52; // Excludes the hidden bit.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kSignificandSize = 53;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Double() : d64_(0) {}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński explicit Double(double d) : d64_(double_to_uint64(d)) {}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński explicit Double(uint64_t d64) : d64_(d64) {}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński explicit Double(DiyFp diy_fp)

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński : d64_(DiyFpToUint64(diy_fp)) {}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp AsDiyFp() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(Sign() > 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(!IsSpecial());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return DiyFp(Significand(), Exponent());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp AsNormalizedDiyFp() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(value() > 0.0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t f = Significand();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int e = Exponent();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // The current double could be a denormal.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while ((f & kHiddenBit) == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński f <<= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński e--;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Do the final shifts in one go.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński f <<= DiyFp::kSignificandSize - kSignificandSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński e -= DiyFp::kSignificandSize - kSignificandSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return DiyFp(f, e);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t AsUint64() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return d64_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński double NextDouble() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (d64_ == kInfinity) return Double(kInfinity).value();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (Sign() < 0 && Significand() == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // -0.0

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return 0.0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (Sign() < 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Double(d64_ - 1).value();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński } else {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Double(d64_ + 1).value();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński double PreviousDouble() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (d64_ == (kInfinity | kSignMask)) return -Double::Infinity();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (Sign() < 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Double(d64_ + 1).value();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński } else {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (Significand() == 0) return -0.0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Double(d64_ - 1).value();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int Exponent() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (IsDenormal()) return kDenormalExponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d64 = AsUint64();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int biased_e =

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static_cast<int>((d64 & kExponentMask) >> kPhysicalSignificandSize);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return biased_e - kExponentBias;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t Significand() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d64 = AsUint64();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t significand = d64 & kSignificandMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (!IsDenormal()) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return significand + kHiddenBit;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński } else {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return significand;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool IsDenormal() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d64 = AsUint64();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return (d64 & kExponentMask) == 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // We consider denormals not to be special.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Hence only Infinity and NaN are special.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool IsSpecial() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d64 = AsUint64();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return (d64 & kExponentMask) == kExponentMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool IsNan() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d64 = AsUint64();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return ((d64 & kExponentMask) == kExponentMask) &&

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ((d64 & kSignificandMask) != 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool IsInfinite() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d64 = AsUint64();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return ((d64 & kExponentMask) == kExponentMask) &&

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ((d64 & kSignificandMask) == 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int Sign() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t d64 = AsUint64();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return (d64 & kSignMask) == 0? 1: -1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp UpperBoundary() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(Sign() > 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return DiyFp(Significand() * 2 + 1, Exponent() - 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void NormalizedBoundaries(DiyFp* out_m_minus, DiyFp* out_m_plus) const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(value() > 0.0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp v = this->AsDiyFp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp m_plus = DiyFp::Normalize(DiyFp((v.f() << 1) + 1, v.e() - 1));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp m_minus;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (LowerBoundaryIsCloser()) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński m_minus = DiyFp((v.f() << 2) - 1, v.e() - 2);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński } else {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński m_minus = DiyFp((v.f() << 1) - 1, v.e() - 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński m_minus.set_f(m_minus.f() << (m_minus.e() - m_plus.e()));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński m_minus.set_e(m_plus.e());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński *out_m_plus = m_plus;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński *out_m_minus = m_minus;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool LowerBoundaryIsCloser() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool physical_significand_is_zero = ((AsUint64() & kSignificandMask) == 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return physical_significand_is_zero && (Exponent() != kDenormalExponent);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński double value() const { return uint64_to_double(d64_); }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static int SignificandSizeForOrderOfMagnitude(int order) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (order >= (kDenormalExponent + kSignificandSize)) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return kSignificandSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (order <= kDenormalExponent) return 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return order - kDenormalExponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static double Infinity() {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Double(kInfinity).value();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static double NaN() {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Double(kNaN).value();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński private:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kExponentBias = 0x3FF + kPhysicalSignificandSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kDenormalExponent = -kExponentBias + 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kMaxExponent = 0x7FF - kExponentBias;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const uint64_t kInfinity = UINT64_2PART_C(0x7FF00000, 00000000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const uint64_t kNaN = UINT64_2PART_C(0x7FF80000, 00000000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint64_t d64_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static uint64_t DiyFpToUint64(DiyFp diy_fp) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t significand = diy_fp.f();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int exponent = diy_fp.e();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (significand > kHiddenBit + kSignificandMask) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński significand >>= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (exponent >= kMaxExponent) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return kInfinity;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (exponent < kDenormalExponent) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (exponent > kDenormalExponent && (significand & kHiddenBit) == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński significand <<= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent--;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t biased_exponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (exponent == kDenormalExponent && (significand & kHiddenBit) == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński biased_exponent = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński } else {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński biased_exponent = static_cast<uint64_t>(exponent + kExponentBias);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return (significand & kSignificandMask) |

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński (biased_exponent << kPhysicalSignificandSize);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DISALLOW_COPY_AND_ASSIGN(Double);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński};

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate<typename S>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic int BitSize(S value) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński (void) value; // Mark variable as used.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return 8 * sizeof(value);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiclass Bignum {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński public:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // This bignum can encode much bigger numbers, since it contains an

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // exponent.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kMaxSignificantBits = 3584;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Bignum()

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0)

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < kBigitCapacity; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AssignUInt16(uint16_t value) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(kBigitSize >= BitSize(value));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (value == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[0] = value;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ = 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AssignUInt64(uint64_t value) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const int kUInt64Size = 64;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (value == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int needed_bigits = kUInt64Size / kBigitSize + 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(needed_bigits);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < needed_bigits; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = value & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński value = value >> kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ = needed_bigits;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AssignBignum(const Bignum& other) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent_ = other.exponent_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < other.used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = other.bigits_[i];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Clear the excess digits (if there were any).

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = other.used_digits_; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ = other.used_digits_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AssignDecimalString(Vector<const char> value);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AssignHexString(Vector<const char> value);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AssignPowerUInt16(uint16_t base, int exponent);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AddUInt16(uint16_t operand);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AddUInt64(uint64_t operand);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void AddBignum(const Bignum& other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Precondition: this >= other.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void SubtractBignum(const Bignum& other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Square();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void ShiftLeft(int shift_amount);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void MultiplyByUInt32(uint32_t factor);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void MultiplyByUInt64(uint64_t factor);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void MultiplyByPowerOfTen(int exponent);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Times10() { return MultiplyByUInt32(10); }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Pseudocode:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // int result = this / other;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // this = this % other;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // In the worst case this function is in O(this/other).

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint16_t DivideModuloIntBignum(const Bignum& other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool ToHexString(char* buffer, int buffer_size) const;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Returns

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // -1 if a < b,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // 0 if a == b, and

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // +1 if a > b.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static int Compare(const Bignum& a, const Bignum& b);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static bool Equal(const Bignum& a, const Bignum& b) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Compare(a, b) == 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static bool LessEqual(const Bignum& a, const Bignum& b) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Compare(a, b) <= 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static bool Less(const Bignum& a, const Bignum& b) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return Compare(a, b) < 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Returns Compare(a + b, c);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Returns a + b == c

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return PlusCompare(a, b, c) == 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Returns a + b <= c

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return PlusCompare(a, b, c) <= 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Returns a + b < c

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return PlusCompare(a, b, c) < 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński private:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński typedef uint32_t Chunk;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński typedef uint64_t DoubleChunk;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kChunkSize = sizeof(Chunk) * 8;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // With bigit size of 28 we loose some bits, but a double still fits easily

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // into two chunks, and more importantly we can use the Comba multiplication.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kBigitSize = 28;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const Chunk kBigitMask = (1 << kBigitSize) - 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Every instance allocates kBigitLength chunks on the stack. Bignums cannot

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // grow. There are no checks if the stack-allocated space is sufficient.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void EnsureCapacity(int size) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (size > kBigitCapacity) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński UNREACHABLE();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Align(const Bignum& other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool IsClamped() const;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Requires this to have enough capacity (no tests done).

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Updates used_digits_ if necessary.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // shift_amount must be < kBigitSize.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void BigitsShiftLeft(int shift_amount);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // BigitLength includes the "hidden" digits encoded in the exponent.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int BigitLength() const { return used_digits_ + exponent_; }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk BigitAt(int index) const;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void SubtractTimes(const Bignum& other, int factor);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk bigits_buffer_[kBigitCapacity];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // A vector backed by bigits_buffer_. This way accesses to the array are

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // checked for out-of-bounds errors.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Vector<Chunk> bigits_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int used_digits_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int exponent_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DISALLOW_COPY_AND_ASSIGN(Bignum);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński};

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic uint64_t ReadUInt64(Vector<const char> buffer,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int from,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int digits_to_read) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t result = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = from; i < from + digits_to_read; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int digit = buffer[i] - '0';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(0 <= digit && digit <= 9);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result = result * 10 + digit;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::AssignDecimalString(Vector<const char> value) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // 2^64 = 18446744073709551616 > 10^19

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const int kMaxUint64DecimalDigits = 19;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int length = value.length();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int pos = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Let's just say that each digit needs 4 bits.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (length >= kMaxUint64DecimalDigits) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński pos += kMaxUint64DecimalDigits;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński length -= kMaxUint64DecimalDigits;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński MultiplyByPowerOfTen(kMaxUint64DecimalDigits);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński AddUInt64(digits);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t digits = ReadUInt64(value, pos, length);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński MultiplyByPowerOfTen(length);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński AddUInt64(digits);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic int HexCharValue(char c) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if ('0' <= c && c <= '9') return c - '0';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if ('a' <= c && c <= 'f') return 10 + c - 'a';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT('A' <= c && c <= 'F');

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return 10 + c - 'A';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::AssignHexString(Vector<const char> value) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int length = value.length();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int needed_bigits = length * 4 / kBigitSize + 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(needed_bigits);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int string_index = length - 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < needed_bigits - 1; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // These bigits are guaranteed to be "full".

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk current_bigit = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int j = 0; j < kBigitSize / 4; j++) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński current_bigit += HexCharValue(value[string_index--]) << (j * 4);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = current_bigit;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ = needed_bigits - 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk most_significant_bigit = 0; // Could be = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int j = 0; j <= string_index; ++j) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński most_significant_bigit <<= 4;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński most_significant_bigit += HexCharValue(value[j]);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (most_significant_bigit != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[used_digits_] = most_significant_bigit;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::AddUInt64(uint64_t operand) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (operand == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Bignum other;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński other.AssignUInt64(operand);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński AddBignum(other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::AddBignum(const Bignum& other) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(other.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Align(other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(1 + std::max(BigitLength(), other.BigitLength()) - exponent_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk carry = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bigit_pos = other.exponent_ - exponent_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(bigit_pos >= 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < other.used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[bigit_pos] = sum & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński carry = sum >> kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigit_pos++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (carry != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk sum = bigits_[bigit_pos] + carry;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[bigit_pos] = sum & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński carry = sum >> kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigit_pos++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ = std::max(bigit_pos, used_digits_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::SubtractBignum(const Bignum& other) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(other.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // We require this to be bigger than other.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(LessEqual(other, *this));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Align(other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int offset = other.exponent_ - exponent_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk borrow = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int i;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (i = 0; i < other.used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT((borrow == 0) || (borrow == 1));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i + offset] = difference & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński borrow = difference >> (kChunkSize - 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (borrow != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk difference = bigits_[i + offset] - borrow;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i + offset] = difference & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński borrow = difference >> (kChunkSize - 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ++i;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::ShiftLeft(int shift_amount) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (used_digits_ == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent_ += shift_amount / kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int local_shift = shift_amount % kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(used_digits_ + 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński BigitsShiftLeft(local_shift);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::MultiplyByUInt32(uint32_t factor) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (factor == 1) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (factor == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (used_digits_ == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DoubleChunk carry = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = static_cast<Chunk>(product & kBigitMask);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński carry = (product >> kBigitSize);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (carry != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(used_digits_ + 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[used_digits_] = carry & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński carry >>= kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::MultiplyByUInt64(uint64_t factor) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (factor == 1) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (factor == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(kBigitSize < 32);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t carry = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t low = factor & 0xFFFFFFFF;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t high = factor >> 32;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t product_low = low * bigits_[i];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t product_high = high * bigits_[i];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t tmp = (carry & kBigitMask) + product_low;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = tmp & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński (product_high << (32 - kBigitSize));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (carry != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(used_digits_ + 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[used_digits_] = carry & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński carry >>= kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::MultiplyByPowerOfTen(int exponent) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint16_t kFive1 = 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint16_t kFive2 = kFive1 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint16_t kFive3 = kFive2 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint16_t kFive4 = kFive3 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint16_t kFive5 = kFive4 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint16_t kFive6 = kFive5 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive7 = kFive6 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive8 = kFive7 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive9 = kFive8 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive10 = kFive9 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive11 = kFive10 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive12 = kFive11 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive13 = kFive12 * 5;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint32_t kFive1_to_12[] =

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(exponent >= 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (exponent == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (used_digits_ == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int remaining_exponent = exponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (remaining_exponent >= 27) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński MultiplyByUInt64(kFive27);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński remaining_exponent -= 27;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (remaining_exponent >= 13) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński MultiplyByUInt32(kFive13);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński remaining_exponent -= 13;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (remaining_exponent > 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ShiftLeft(exponent);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::Square() {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int product_length = 2 * used_digits_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(product_length);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński UNIMPLEMENTED();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DoubleChunk accumulator = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // First shift the digits so we don't overwrite them.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int copy_offset = used_digits_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[copy_offset + i] = bigits_[i];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // We have two loops to avoid some 'if's in the loop.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Process temporary digit i with power i.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // The sum of the two indices must be equal to i.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bigit_index1 = i;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bigit_index2 = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Sum all of the sub-products.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (bigit_index1 >= 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk chunk1 = bigits_[copy_offset + bigit_index1];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk chunk2 = bigits_[copy_offset + bigit_index2];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigit_index1--;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigit_index2++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński accumulator >>= kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = used_digits_; i < product_length; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bigit_index1 = used_digits_ - 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bigit_index2 = i - bigit_index1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (bigit_index2 < used_digits_) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk chunk1 = bigits_[copy_offset + bigit_index1];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk chunk2 = bigits_[copy_offset + bigit_index2];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigit_index1--;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigit_index2++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński accumulator >>= kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(accumulator == 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ = product_length;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent_ *= 2;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(base != 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(power_exponent >= 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (power_exponent == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński AssignUInt16(1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Zero();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int shifts = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while ((base & 1) == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński base >>= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński shifts++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bit_size = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int tmp_base = base;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (tmp_base != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński tmp_base >>= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bit_size++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int final_size = bit_size * power_exponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(final_size / kBigitSize + 2);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Left to Right exponentiation.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int mask = 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (power_exponent >= mask) mask <<= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński mask >>= 2;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t this_value = base;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool delayed_multipliciation = false;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const uint64_t max_32bits = 0xFFFFFFFF;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (mask != 0 && this_value <= max_32bits) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński this_value = this_value * this_value;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Verify that there is enough space in this_value to perform the

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // multiplication. The first bit_size bits must be 0.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if ((power_exponent & mask) != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t base_bits_mask =

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bool high_bits_zero = (this_value & base_bits_mask) == 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (high_bits_zero) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński this_value *= base;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński } else {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński delayed_multipliciation = true;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński mask >>= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński AssignUInt64(this_value);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (delayed_multipliciation) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński MultiplyByUInt32(base);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Now do the same thing as a bignum.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (mask != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Square();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if ((power_exponent & mask) != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński MultiplyByUInt32(base);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński mask >>= 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // And finally add the saved shifts.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ShiftLeft(shifts * power_exponent);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiuint16_t Bignum::DivideModuloIntBignum(const Bignum& other) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(other.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(other.used_digits_ > 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (BigitLength() < other.BigitLength()) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Align(other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint16_t result = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (BigitLength() > other.BigitLength()) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(bigits_[used_digits_ - 1] < 0x10000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result += static_cast<uint16_t>(bigits_[used_digits_ - 1]);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński SubtractTimes(other, bigits_[used_digits_ - 1]);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(BigitLength() == other.BigitLength());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk this_bigit = bigits_[used_digits_ - 1];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk other_bigit = other.bigits_[other.used_digits_ - 1];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (other.used_digits_ == 1) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int quotient = this_bigit / other_bigit;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(quotient < 0x10000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result += static_cast<uint16_t>(quotient);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int division_estimate = this_bigit / (other_bigit + 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(division_estimate < 0x10000);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result += static_cast<uint16_t>(division_estimate);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński SubtractTimes(other, division_estimate);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (other_bigit * (division_estimate + 1) > this_bigit) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (LessEqual(other, *this)) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński SubtractBignum(other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate<typename S>

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic int SizeInHexChars(S number) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(number > 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int result = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (number != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński number >>= 4;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński result++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return result;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic char HexCharOfValue(int value) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(0 <= value && value <= 16);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (value < 10) return static_cast<char>(value + '0');

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return static_cast<char>(value - 10 + 'A');

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskibool Bignum::ToHexString(char* buffer, int buffer_size) const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Each bigit must be printable as separate hex-character.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(kBigitSize % 4 == 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński const int kHexCharsPerBigit = kBigitSize / 4;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (used_digits_ == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (buffer_size < 2) return false;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński buffer[0] = '0';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński buffer[1] = '\0';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return true;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // We add 1 for the terminating '\0' character.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński SizeInHexChars(bigits_[used_digits_ - 1]) + 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (needed_chars > buffer_size) return false;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int string_index = needed_chars - 1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński buffer[string_index--] = '\0';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < exponent_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int j = 0; j < kHexCharsPerBigit; ++j) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński buffer[string_index--] = '0';

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < used_digits_ - 1; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk current_bigit = bigits_[i];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int j = 0; j < kHexCharsPerBigit; ++j) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński current_bigit >>= 4;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // And finally the last bigit.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk most_significant_bigit = bigits_[used_digits_ - 1];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (most_significant_bigit != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński most_significant_bigit >>= 4;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return true;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof KosińskiBignum::Chunk Bignum::BigitAt(int index) const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (index >= BigitLength()) return 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (index < exponent_) return 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return bigits_[index - exponent_];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiint Bignum::Compare(const Bignum& a, const Bignum& b) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(a.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(b.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bigit_length_a = a.BigitLength();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int bigit_length_b = b.BigitLength();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (bigit_length_a < bigit_length_b) return -1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (bigit_length_a > bigit_length_b) return +1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = bigit_length_a - 1; i >= std::min(a.exponent_, b.exponent_); --i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk bigit_a = a.BigitAt(i);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk bigit_b = b.BigitAt(i);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (bigit_a < bigit_b) return -1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (bigit_a > bigit_b) return +1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiint Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(a.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(b.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(c.IsClamped());

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (a.BigitLength() < b.BigitLength()) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return PlusCompare(b, a, c);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (a.BigitLength() + 1 < c.BigitLength()) return -1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (a.BigitLength() > c.BigitLength()) return +1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return -1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk borrow = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Starting at min_exponent all digits are == 0. So no need to compare them.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int min_exponent = std::min(std::min(a.exponent_, b.exponent_), c.exponent_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk chunk_a = a.BigitAt(i);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk chunk_b = b.BigitAt(i);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk chunk_c = c.BigitAt(i);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk sum = chunk_a + chunk_b;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (sum > chunk_c + borrow) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return +1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński } else {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński borrow = chunk_c + borrow - sum;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (borrow > 1) return -1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński borrow <<= kBigitSize;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (borrow == 0) return 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return -1;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::Clamp() {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_--;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (used_digits_ == 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // Zero.

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent_ = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskibool Bignum::IsClamped() const {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::Zero() {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent_ = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::Align(const Bignum& other) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (exponent_ > other.exponent_) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int zero_digits = exponent_ - other.exponent_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński EnsureCapacity(used_digits_ + zero_digits);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = used_digits_ - 1; i >= 0; --i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i + zero_digits] = bigits_[i];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < zero_digits; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_ += zero_digits;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński exponent_ -= zero_digits;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(used_digits_ >= 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(exponent_ >= 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::BigitsShiftLeft(int shift_amount) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(shift_amount < kBigitSize);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(shift_amount >= 0);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk carry = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński carry = new_carry;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (carry != 0) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[used_digits_] = carry;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński used_digits_++;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskivoid Bignum::SubtractTimes(const Bignum& other, int factor) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński ASSERT(exponent_ <= other.exponent_);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (factor < 3) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < factor; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński SubtractBignum(other);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk borrow = 0;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int exponent_diff = other.exponent_ - exponent_;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = 0; i < other.used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DoubleChunk remove = borrow + product;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk difference = bigits_[i + exponent_diff] - (remove & kBigitMask);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i + exponent_diff] = difference & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński (remove >> kBigitSize));

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński if (borrow == 0) return;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Chunk difference = bigits_[i] - borrow;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński bigits_[i] = difference & kBigitMask;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński borrow = difference >> (kChunkSize - 1);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński }

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Clamp();

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński}

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskiclass PowersOfTenCache {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskipublic:

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kDecimalExponentDistance;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kMinDecimalExponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static const int kMaxDecimalExponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static void GetCachedPowerForBinaryExponentRange(int min_exponent,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int max_exponent,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp* power,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int* decimal_exponent);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static void GetCachedPowerForDecimalExponent(int requested_exponent,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński DiyFp* power,

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int* found_exponent);

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński};

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistruct CachedPower {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński uint64_t significand;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int16_t binary_exponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński int16_t decimal_exponent;

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński};

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskistatic const CachedPower kCachedPowers[] = {

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xfa8fd5a0, 081c0288), -1220, -348},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xbaaee17f, a23ebf76), -1193, -340},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x8b16fb20, 3055ac76), -1166, -332},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xcf42894a, 5dce35ea), -1140, -324},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x9a6bb0aa, 55653b2d), -1113, -316},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xe61acf03, 3d1a45df), -1087, -308},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xab70fe17, c79ac6ca), -1060, -300},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xff77b1fc, bebcdc4f), -1034, -292},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xbe5691ef, 416bd60c), -1007, -284},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x8dd01fad, 907ffc3c), -980, -276},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xd3515c28, 31559a83), -954, -268},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x9d71ac8f, ada6c9b5), -927, -260},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xea9c2277, 23ee8bcb), -901, -252},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xaecc4991, 4078536d), -874, -244},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x823c1279, 5db6ce57), -847, -236},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xc2109436, 4dfb5637), -821, -228},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x9096ea6f, 3848984f), -794, -220},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xd77485cb, 25823ac7), -768, -212},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xa086cfcd, 97bf97f4), -741, -204},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xef340a98, 172aace5), -715, -196},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xb23867fb, 2a35b28e), -688, -188},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x84c8d4df, d2c63f3b), -661, -180},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xc5dd4427, 1ad3cdba), -635, -172},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0x936b9fce, bb25c996), -608, -164},

76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński {UINT64_2PART_C(0xdbac6c24, 7d62a584), -582, -156},