3f6fd1ba65f962702753c4ad284b588e59689a23Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <2geom/coord.h>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <stdint.h>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <cstdlib>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <cassert>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <cstring>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <climits>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <cstdarg>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#include <cmath>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#ifndef ASSERT

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define ASSERT(condition) \

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering assert(condition);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#endif

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#ifndef UNIMPLEMENTED

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define UNIMPLEMENTED() (abort())

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#endif

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#ifndef UNREACHABLE

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define UNREACHABLE() (abort())

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#endif

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define UINT64_2PART_C(a, b) (((static_cast<uint64_t>(a) << 32) + 0x##b##u))

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#ifndef ARRAY_SIZE

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define ARRAY_SIZE(a) \

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ((sizeof(a) / sizeof(*(a))) / \

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static_cast<size_t>(!(sizeof(a) % sizeof(*(a)))))

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#endif

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#ifndef DISALLOW_COPY_AND_ASSIGN

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define DISALLOW_COPY_AND_ASSIGN(TypeName) \

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering TypeName(const TypeName&); \

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering void operator=(const TypeName&)

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#endif

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#ifndef DISALLOW_IMPLICIT_CONSTRUCTORS

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define DISALLOW_IMPLICIT_CONSTRUCTORS(TypeName) \

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering TypeName(); \

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DISALLOW_COPY_AND_ASSIGN(TypeName)

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#endif

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#if defined(__GNUC__)

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define DOUBLE_CONVERSION_UNUSED __attribute__((unused))

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#else

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#define DOUBLE_CONVERSION_UNUSED

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering#endif

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringnamespace Geom {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringnamespace {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringinline int StrLength(const char* string) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering size_t length = strlen(string);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(length == static_cast<size_t>(static_cast<int>(length)));

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return static_cast<int>(length);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringtemplate <typename T>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringclass Vector {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering public:

72c0a2c255b172ebbb2a2b7dab7c9aec4c9582d9Lennart Poettering Vector() : start_(NULL), length_(0) {}

72c0a2c255b172ebbb2a2b7dab7c9aec4c9582d9Lennart Poettering Vector(T* data, int length) : start_(data), length_(length) {

72c0a2c255b172ebbb2a2b7dab7c9aec4c9582d9Lennart Poettering ASSERT(length == 0 || (length > 0 && data != NULL));

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering Vector<T> SubVector(int from, int to) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(to <= length_);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(from < to);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(0 <= from);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return Vector<T>(start() + from, to - from);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int length() const { return length_; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering bool is_empty() const { return length_ == 0; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering T* start() const { return start_; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering T& operator[](int index) const {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(0 <= index && index < length_);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return start_[index];

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering T& first() { return start_[0]; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering T& last() { return start_[length_ - 1]; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering private:

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering T* start_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int length_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering};

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringtemplate <class Dest, class Source>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringinline Dest BitCast(const Source& source) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DOUBLE_CONVERSION_UNUSED

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering typedef char VerifySizesAreEqual[sizeof(Dest) == sizeof(Source) ? 1 : -1];

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering Dest dest;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering memmove(&dest, &source, sizeof(dest));

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return dest;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringtemplate <class Dest, class Source>

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringinline Dest BitCast(Source* source) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return BitCast<Dest>(reinterpret_cast<uintptr_t>(source));

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringstatic uint64_t double_to_uint64(double d) { return BitCast<uint64_t>(d); }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringstatic double uint64_to_double(uint64_t d64) { return BitCast<double>(d64); }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringclass DiyFp {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering public:

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const int kSignificandSize = 64;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DiyFp() : f_(0), e_(0) {}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DiyFp(uint64_t f, int e) : f_(f), e_(e) {}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering void Subtract(const DiyFp& other) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(e_ == other.e_);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(f_ >= other.f_);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering f_ -= other.f_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static DiyFp Minus(const DiyFp& a, const DiyFp& b) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DiyFp result = a;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering result.Subtract(b);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return result;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering void Multiply(const DiyFp& other) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering const uint64_t kM32 = 0xFFFFFFFFU;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t a = f_ >> 32;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t b = f_ & kM32;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t c = other.f_ >> 32;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t d = other.f_ & kM32;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t ac = a * c;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t bc = b * c;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t ad = a * d;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t bd = b * d;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t tmp = (bd >> 32) + (ad & kM32) + (bc & kM32);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering // By adding 1U << 31 to tmp we round the final result.

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering // Halfway cases will be round up.

72c0a2c255b172ebbb2a2b7dab7c9aec4c9582d9Lennart Poettering tmp += 1U << 31;

72c0a2c255b172ebbb2a2b7dab7c9aec4c9582d9Lennart Poettering uint64_t result_f = ac + (ad >> 32) + (bc >> 32) + (tmp >> 32);

72c0a2c255b172ebbb2a2b7dab7c9aec4c9582d9Lennart Poettering e_ += other.e_ + 64;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering f_ = result_f;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static DiyFp Times(const DiyFp& a, const DiyFp& b) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DiyFp result = a;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering result.Multiply(b);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return result;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering void Normalize() {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(f_ != 0);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t f = f_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int e = e_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering const uint64_t k10MSBits = UINT64_2PART_C(0xFFC00000, 00000000);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering while ((f & k10MSBits) == 0) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering f <<= 10;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering e -= 10;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering while ((f & kUint64MSB) == 0) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering f <<= 1;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering e--;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering f_ = f;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering e_ = e;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static DiyFp Normalize(const DiyFp& a) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DiyFp result = a;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering result.Normalize();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return result;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t f() const { return f_; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int e() const { return e_; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering void set_f(uint64_t new_value) { f_ = new_value; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering void set_e(int new_value) { e_ = new_value; }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering private:

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const uint64_t kUint64MSB = UINT64_2PART_C(0x80000000, 00000000);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t f_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int e_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering};

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poetteringclass Double {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering public:

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const uint64_t kSignMask = UINT64_2PART_C(0x80000000, 00000000);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const uint64_t kExponentMask = UINT64_2PART_C(0x7FF00000, 00000000);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const uint64_t kSignificandMask = UINT64_2PART_C(0x000FFFFF, FFFFFFFF);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const uint64_t kHiddenBit = UINT64_2PART_C(0x00100000, 00000000);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const int kPhysicalSignificandSize = 52; // Excludes the hidden bit.

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static const int kSignificandSize = 53;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering Double() : d64_(0) {}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering explicit Double(double d) : d64_(double_to_uint64(d)) {}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering explicit Double(uint64_t d64) : d64_(d64) {}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering explicit Double(DiyFp diy_fp)

3f6fd1ba65f962702753c4ad284b588e59689a23Lennart Poettering : d64_(DiyFpToUint64(diy_fp)) {}

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DiyFp AsDiyFp() const {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(Sign() > 0);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(!IsSpecial());

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return DiyFp(Significand(), Exponent());

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering DiyFp AsNormalizedDiyFp() const {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering ASSERT(value() > 0.0);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t f = Significand();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int e = Exponent();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering // The current double could be a denormal.

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering while ((f & kHiddenBit) == 0) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering f <<= 1;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering e--;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering // Do the final shifts in one go.

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering f <<= DiyFp::kSignificandSize - kSignificandSize;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering e -= DiyFp::kSignificandSize - kSignificandSize;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return DiyFp(f, e);

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t AsUint64() const {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return d64_;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering double NextDouble() const {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering if (d64_ == kInfinity) return Double(kInfinity).value();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering if (Sign() < 0 && Significand() == 0) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering // -0.0

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return 0.0;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering if (Sign() < 0) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return Double(d64_ - 1).value();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering } else {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return Double(d64_ + 1).value();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering double PreviousDouble() const {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering if (d64_ == (kInfinity | kSignMask)) return -Double::Infinity();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering if (Sign() < 0) {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return Double(d64_ + 1).value();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering } else {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering if (Significand() == 0) return -0.0;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering return Double(d64_ - 1).value();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering }

ce30c8dcb41dfe9264f79f30c7f51c0e74576638Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int Exponent() const {

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering if (IsDenormal()) return kDenormalExponent;

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering uint64_t d64 = AsUint64();

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering int biased_e =

587fec427c80b6c34dcf1d7570f891fcb652a7c5Lennart Poettering static_cast<int>((d64 & kExponentMask) >> kPhysicalSignificandSize);

return biased_e - kExponentBias;

}

uint64_t Significand() const {

uint64_t d64 = AsUint64();

uint64_t significand = d64 & kSignificandMask;

if (!IsDenormal()) {

return significand + kHiddenBit;

} else {

return significand;

}

}

bool IsDenormal() const {

uint64_t d64 = AsUint64();

return (d64 & kExponentMask) == 0;

}

// We consider denormals not to be special.

// Hence only Infinity and NaN are special.

bool IsSpecial() const {

uint64_t d64 = AsUint64();

return (d64 & kExponentMask) == kExponentMask;

}

bool IsNan() const {

uint64_t d64 = AsUint64();

return ((d64 & kExponentMask) == kExponentMask) &&

((d64 & kSignificandMask) != 0);

}

bool IsInfinite() const {

uint64_t d64 = AsUint64();

return ((d64 & kExponentMask) == kExponentMask) &&

((d64 & kSignificandMask) == 0);

}

int Sign() const {

uint64_t d64 = AsUint64();

return (d64 & kSignMask) == 0? 1: -1;

}

DiyFp UpperBoundary() const {

ASSERT(Sign() > 0);

return DiyFp(Significand() * 2 + 1, Exponent() - 1);

}

void NormalizedBoundaries(DiyFp* out_m_minus, DiyFp* out_m_plus) const {

ASSERT(value() > 0.0);

DiyFp v = this->AsDiyFp();

DiyFp m_plus = DiyFp::Normalize(DiyFp((v.f() << 1) + 1, v.e() - 1));

DiyFp m_minus;

if (LowerBoundaryIsCloser()) {

m_minus = DiyFp((v.f() << 2) - 1, v.e() - 2);

} else {

m_minus = DiyFp((v.f() << 1) - 1, v.e() - 1);

}

m_minus.set_f(m_minus.f() << (m_minus.e() - m_plus.e()));

m_minus.set_e(m_plus.e());

*out_m_plus = m_plus;

*out_m_minus = m_minus;

}

bool LowerBoundaryIsCloser() const {

bool physical_significand_is_zero = ((AsUint64() & kSignificandMask) == 0);

return physical_significand_is_zero && (Exponent() != kDenormalExponent);

}

double value() const { return uint64_to_double(d64_); }

static int SignificandSizeForOrderOfMagnitude(int order) {

if (order >= (kDenormalExponent + kSignificandSize)) {

return kSignificandSize;

}

if (order <= kDenormalExponent) return 0;

return order - kDenormalExponent;

}

static double Infinity() {

return Double(kInfinity).value();

}

static double NaN() {

return Double(kNaN).value();

}

private:

static const int kExponentBias = 0x3FF + kPhysicalSignificandSize;

static const int kDenormalExponent = -kExponentBias + 1;

static const int kMaxExponent = 0x7FF - kExponentBias;

static const uint64_t kInfinity = UINT64_2PART_C(0x7FF00000, 00000000);

static const uint64_t kNaN = UINT64_2PART_C(0x7FF80000, 00000000);

const uint64_t d64_;

static uint64_t DiyFpToUint64(DiyFp diy_fp) {

uint64_t significand = diy_fp.f();

int exponent = diy_fp.e();

while (significand > kHiddenBit + kSignificandMask) {

significand >>= 1;

exponent++;

}

if (exponent >= kMaxExponent) {

return kInfinity;

}

if (exponent < kDenormalExponent) {

return 0;

}

while (exponent > kDenormalExponent && (significand & kHiddenBit) == 0) {

significand <<= 1;

exponent--;

}

uint64_t biased_exponent;

if (exponent == kDenormalExponent && (significand & kHiddenBit) == 0) {

biased_exponent = 0;

} else {

biased_exponent = static_cast<uint64_t>(exponent + kExponentBias);

}

return (significand & kSignificandMask) |

(biased_exponent << kPhysicalSignificandSize);

}

DISALLOW_COPY_AND_ASSIGN(Double);

};

template<typename S>

static int BitSize(S value) {

(void) value; // Mark variable as used.

return 8 * sizeof(value);

}

class Bignum {

public:

// 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.

// This bignum can encode much bigger numbers, since it contains an

// exponent.

static const int kMaxSignificantBits = 3584;

Bignum()

: bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0)

{

for (int i = 0; i < kBigitCapacity; ++i) {

bigits_[i] = 0;

}

}

void AssignUInt16(uint16_t value) {

ASSERT(kBigitSize >= BitSize(value));

Zero();

if (value == 0) return;

EnsureCapacity(1);

bigits_[0] = value;

used_digits_ = 1;

}

void AssignUInt64(uint64_t value) {

const int kUInt64Size = 64;

Zero();

if (value == 0) return;

int needed_bigits = kUInt64Size / kBigitSize + 1;

EnsureCapacity(needed_bigits);

for (int i = 0; i < needed_bigits; ++i) {

bigits_[i] = value & kBigitMask;

value = value >> kBigitSize;

}

used_digits_ = needed_bigits;

Clamp();

}

void AssignBignum(const Bignum& other) {

exponent_ = other.exponent_;

for (int i = 0; i < other.used_digits_; ++i) {

bigits_[i] = other.bigits_[i];

}

// Clear the excess digits (if there were any).

for (int i = other.used_digits_; i < used_digits_; ++i) {

bigits_[i] = 0;

}

used_digits_ = other.used_digits_;

}

void AssignDecimalString(Vector<const char> value);

void AssignHexString(Vector<const char> value);

void AssignPowerUInt16(uint16_t base, int exponent);

void AddUInt16(uint16_t operand);

void AddUInt64(uint64_t operand);

void AddBignum(const Bignum& other);

// Precondition: this >= other.

void SubtractBignum(const Bignum& other);

void Square();

void ShiftLeft(int shift_amount);

void MultiplyByUInt32(uint32_t factor);

void MultiplyByUInt64(uint64_t factor);

void MultiplyByPowerOfTen(int exponent);

void Times10() { return MultiplyByUInt32(10); }

// Pseudocode:

// int result = this / other;

// this = this % other;

// In the worst case this function is in O(this/other).

uint16_t DivideModuloIntBignum(const Bignum& other);

bool ToHexString(char* buffer, int buffer_size) const;

// Returns

// -1 if a < b,

// 0 if a == b, and

// +1 if a > b.

static int Compare(const Bignum& a, const Bignum& b);

static bool Equal(const Bignum& a, const Bignum& b) {

return Compare(a, b) == 0;

}

static bool LessEqual(const Bignum& a, const Bignum& b) {

return Compare(a, b) <= 0;

}

static bool Less(const Bignum& a, const Bignum& b) {

return Compare(a, b) < 0;

}

// Returns Compare(a + b, c);

static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);

// Returns a + b == c

static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {

return PlusCompare(a, b, c) == 0;

}

// Returns a + b <= c

static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {

return PlusCompare(a, b, c) <= 0;

}

// Returns a + b < c

static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {

return PlusCompare(a, b, c) < 0;

}

private:

typedef uint32_t Chunk;

typedef uint64_t DoubleChunk;

static const int kChunkSize = sizeof(Chunk) * 8;

static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;

// With bigit size of 28 we loose some bits, but a double still fits easily

// into two chunks, and more importantly we can use the Comba multiplication.

static const int kBigitSize = 28;

static const Chunk kBigitMask = (1 << kBigitSize) - 1;

// Every instance allocates kBigitLength chunks on the stack. Bignums cannot

// grow. There are no checks if the stack-allocated space is sufficient.

static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;

void EnsureCapacity(int size) {

if (size > kBigitCapacity) {

UNREACHABLE();

}

}

void Align(const Bignum& other);

void Clamp();

bool IsClamped() const;

void Zero();

// Requires this to have enough capacity (no tests done).

// Updates used_digits_ if necessary.

// shift_amount must be < kBigitSize.

void BigitsShiftLeft(int shift_amount);

// BigitLength includes the "hidden" digits encoded in the exponent.

int BigitLength() const { return used_digits_ + exponent_; }

Chunk BigitAt(int index) const;

void SubtractTimes(const Bignum& other, int factor);

Chunk bigits_buffer_[kBigitCapacity];

// A vector backed by bigits_buffer_. This way accesses to the array are

// checked for out-of-bounds errors.

Vector<Chunk> bigits_;

int used_digits_;

// The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).

int exponent_;

DISALLOW_COPY_AND_ASSIGN(Bignum);

};

static uint64_t ReadUInt64(Vector<const char> buffer,

int from,

int digits_to_read) {

uint64_t result = 0;

for (int i = from; i < from + digits_to_read; ++i) {

int digit = buffer[i] - '0';

ASSERT(0 <= digit && digit <= 9);

result = result * 10 + digit;

}

return result;

}

void Bignum::AssignDecimalString(Vector<const char> value) {

// 2^64 = 18446744073709551616 > 10^19

const int kMaxUint64DecimalDigits = 19;

Zero();

int length = value.length();

int pos = 0;

// Let's just say that each digit needs 4 bits.

while (length >= kMaxUint64DecimalDigits) {

uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);

pos += kMaxUint64DecimalDigits;

length -= kMaxUint64DecimalDigits;

MultiplyByPowerOfTen(kMaxUint64DecimalDigits);

AddUInt64(digits);

}

uint64_t digits = ReadUInt64(value, pos, length);

MultiplyByPowerOfTen(length);

AddUInt64(digits);

Clamp();

}

static int HexCharValue(char c) {

if ('0' <= c && c <= '9') return c - '0';

if ('a' <= c && c <= 'f') return 10 + c - 'a';

ASSERT('A' <= c && c <= 'F');

return 10 + c - 'A';

}

void Bignum::AssignHexString(Vector<const char> value) {

Zero();

int length = value.length();

int needed_bigits = length * 4 / kBigitSize + 1;

EnsureCapacity(needed_bigits);

int string_index = length - 1;

for (int i = 0; i < needed_bigits - 1; ++i) {

// These bigits are guaranteed to be "full".

Chunk current_bigit = 0;

for (int j = 0; j < kBigitSize / 4; j++) {

current_bigit += HexCharValue(value[string_index--]) << (j * 4);

}

bigits_[i] = current_bigit;

}

used_digits_ = needed_bigits - 1;

Chunk most_significant_bigit = 0; // Could be = 0;

for (int j = 0; j <= string_index; ++j) {

most_significant_bigit <<= 4;

most_significant_bigit += HexCharValue(value[j]);

}

if (most_significant_bigit != 0) {

bigits_[used_digits_] = most_significant_bigit;

used_digits_++;

}

Clamp();

}

void Bignum::AddUInt64(uint64_t operand) {

if (operand == 0) return;

Bignum other;

other.AssignUInt64(operand);

AddBignum(other);

}

void Bignum::AddBignum(const Bignum& other) {

ASSERT(IsClamped());

ASSERT(other.IsClamped());

Align(other);

EnsureCapacity(1 + std::max(BigitLength(), other.BigitLength()) - exponent_);

Chunk carry = 0;

int bigit_pos = other.exponent_ - exponent_;

ASSERT(bigit_pos >= 0);

for (int i = 0; i < other.used_digits_; ++i) {

Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;

bigits_[bigit_pos] = sum & kBigitMask;

carry = sum >> kBigitSize;

bigit_pos++;

}

while (carry != 0) {

Chunk sum = bigits_[bigit_pos] + carry;

bigits_[bigit_pos] = sum & kBigitMask;

carry = sum >> kBigitSize;

bigit_pos++;

}

used_digits_ = std::max(bigit_pos, used_digits_);

ASSERT(IsClamped());

}

void Bignum::SubtractBignum(const Bignum& other) {

ASSERT(IsClamped());

ASSERT(other.IsClamped());

// We require this to be bigger than other.

ASSERT(LessEqual(other, *this));

Align(other);

int offset = other.exponent_ - exponent_;

Chunk borrow = 0;

int i;

for (i = 0; i < other.used_digits_; ++i) {

ASSERT((borrow == 0) || (borrow == 1));

Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;

bigits_[i + offset] = difference & kBigitMask;

borrow = difference >> (kChunkSize - 1);

}

while (borrow != 0) {

Chunk difference = bigits_[i + offset] - borrow;

bigits_[i + offset] = difference & kBigitMask;

borrow = difference >> (kChunkSize - 1);

++i;

}

Clamp();

}

void Bignum::ShiftLeft(int shift_amount) {

if (used_digits_ == 0) return;

exponent_ += shift_amount / kBigitSize;

int local_shift = shift_amount % kBigitSize;

EnsureCapacity(used_digits_ + 1);

BigitsShiftLeft(local_shift);

}

void Bignum::MultiplyByUInt32(uint32_t factor) {

if (factor == 1) return;

if (factor == 0) {

Zero();

return;

}

if (used_digits_ == 0) return;

ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);

DoubleChunk carry = 0;

for (int i = 0; i < used_digits_; ++i) {

DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;

bigits_[i] = static_cast<Chunk>(product & kBigitMask);

carry = (product >> kBigitSize);

}

while (carry != 0) {

EnsureCapacity(used_digits_ + 1);

bigits_[used_digits_] = carry & kBigitMask;

used_digits_++;

carry >>= kBigitSize;

}

}

void Bignum::MultiplyByUInt64(uint64_t factor) {

if (factor == 1) return;

if (factor == 0) {

Zero();

return;

}

ASSERT(kBigitSize < 32);

uint64_t carry = 0;

uint64_t low = factor & 0xFFFFFFFF;

uint64_t high = factor >> 32;

for (int i = 0; i < used_digits_; ++i) {

uint64_t product_low = low * bigits_[i];

uint64_t product_high = high * bigits_[i];

uint64_t tmp = (carry & kBigitMask) + product_low;

bigits_[i] = tmp & kBigitMask;

carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +

(product_high << (32 - kBigitSize));

}

while (carry != 0) {

EnsureCapacity(used_digits_ + 1);

bigits_[used_digits_] = carry & kBigitMask;

used_digits_++;

carry >>= kBigitSize;

}

}

void Bignum::MultiplyByPowerOfTen(int exponent) {

const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d);

const uint16_t kFive1 = 5;

const uint16_t kFive2 = kFive1 * 5;

const uint16_t kFive3 = kFive2 * 5;

const uint16_t kFive4 = kFive3 * 5;

const uint16_t kFive5 = kFive4 * 5;

const uint16_t kFive6 = kFive5 * 5;

const uint32_t kFive7 = kFive6 * 5;

const uint32_t kFive8 = kFive7 * 5;

const uint32_t kFive9 = kFive8 * 5;

const uint32_t kFive10 = kFive9 * 5;

const uint32_t kFive11 = kFive10 * 5;

const uint32_t kFive12 = kFive11 * 5;

const uint32_t kFive13 = kFive12 * 5;

const uint32_t kFive1_to_12[] =

{ kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,

kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };

ASSERT(exponent >= 0);

if (exponent == 0) return;

if (used_digits_ == 0) return;

int remaining_exponent = exponent;

while (remaining_exponent >= 27) {

MultiplyByUInt64(kFive27);

remaining_exponent -= 27;

}

while (remaining_exponent >= 13) {

MultiplyByUInt32(kFive13);

remaining_exponent -= 13;

}

if (remaining_exponent > 0) {

MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);

}

ShiftLeft(exponent);

}

void Bignum::Square() {

ASSERT(IsClamped());

int product_length = 2 * used_digits_;

EnsureCapacity(product_length);

if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {

UNIMPLEMENTED();

}

DoubleChunk accumulator = 0;

// First shift the digits so we don't overwrite them.

int copy_offset = used_digits_;

for (int i = 0; i < used_digits_; ++i) {

bigits_[copy_offset + i] = bigits_[i];

}

// We have two loops to avoid some 'if's in the loop.

for (int i = 0; i < used_digits_; ++i) {

// Process temporary digit i with power i.

// The sum of the two indices must be equal to i.

int bigit_index1 = i;

int bigit_index2 = 0;

// Sum all of the sub-products.

while (bigit_index1 >= 0) {

Chunk chunk1 = bigits_[copy_offset + bigit_index1];

Chunk chunk2 = bigits_[copy_offset + bigit_index2];

accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;

bigit_index1--;

bigit_index2++;

}

bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;

accumulator >>= kBigitSize;

}

for (int i = used_digits_; i < product_length; ++i) {

int bigit_index1 = used_digits_ - 1;

int bigit_index2 = i - bigit_index1;

while (bigit_index2 < used_digits_) {

Chunk chunk1 = bigits_[copy_offset + bigit_index1];

Chunk chunk2 = bigits_[copy_offset + bigit_index2];

accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;

bigit_index1--;

bigit_index2++;

}

bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;

accumulator >>= kBigitSize;

}

ASSERT(accumulator == 0);

used_digits_ = product_length;

exponent_ *= 2;

Clamp();

}

void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {

ASSERT(base != 0);

ASSERT(power_exponent >= 0);

if (power_exponent == 0) {

AssignUInt16(1);

return;

}

Zero();

int shifts = 0;

while ((base & 1) == 0) {

base >>= 1;

shifts++;

}

int bit_size = 0;

int tmp_base = base;

while (tmp_base != 0) {

tmp_base >>= 1;

bit_size++;

}

int final_size = bit_size * power_exponent;

EnsureCapacity(final_size / kBigitSize + 2);

// Left to Right exponentiation.

int mask = 1;

while (power_exponent >= mask) mask <<= 1;

mask >>= 2;

uint64_t this_value = base;

bool delayed_multipliciation = false;

const uint64_t max_32bits = 0xFFFFFFFF;

while (mask != 0 && this_value <= max_32bits) {

this_value = this_value * this_value;

// Verify that there is enough space in this_value to perform the

// multiplication. The first bit_size bits must be 0.

if ((power_exponent & mask) != 0) {

uint64_t base_bits_mask =

~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);

bool high_bits_zero = (this_value & base_bits_mask) == 0;

if (high_bits_zero) {

this_value *= base;

} else {

delayed_multipliciation = true;

}

}

mask >>= 1;

}

AssignUInt64(this_value);

if (delayed_multipliciation) {

MultiplyByUInt32(base);

}

// Now do the same thing as a bignum.

while (mask != 0) {

Square();

if ((power_exponent & mask) != 0) {

MultiplyByUInt32(base);

}

mask >>= 1;

}

// And finally add the saved shifts.

ShiftLeft(shifts * power_exponent);

}

uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) {

ASSERT(IsClamped());

ASSERT(other.IsClamped());

ASSERT(other.used_digits_ > 0);

if (BigitLength() < other.BigitLength()) {

return 0;

}

Align(other);

uint16_t result = 0;

while (BigitLength() > other.BigitLength()) {

ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));

ASSERT(bigits_[used_digits_ - 1] < 0x10000);

result += static_cast<uint16_t>(bigits_[used_digits_ - 1]);

SubtractTimes(other, bigits_[used_digits_ - 1]);

}

ASSERT(BigitLength() == other.BigitLength());

Chunk this_bigit = bigits_[used_digits_ - 1];

Chunk other_bigit = other.bigits_[other.used_digits_ - 1];

if (other.used_digits_ == 1) {

int quotient = this_bigit / other_bigit;

bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;

ASSERT(quotient < 0x10000);

result += static_cast<uint16_t>(quotient);

Clamp();

return result;

}

int division_estimate = this_bigit / (other_bigit + 1);

ASSERT(division_estimate < 0x10000);

result += static_cast<uint16_t>(division_estimate);

SubtractTimes(other, division_estimate);

if (other_bigit * (division_estimate + 1) > this_bigit) {

return result;

}

while (LessEqual(other, *this)) {

SubtractBignum(other);

result++;

}

return result;

}

template<typename S>

static int SizeInHexChars(S number) {

ASSERT(number > 0);

int result = 0;

while (number != 0) {

number >>= 4;

result++;

}

return result;

}

static char HexCharOfValue(int value) {

ASSERT(0 <= value && value <= 16);

if (value < 10) return static_cast<char>(value + '0');

return static_cast<char>(value - 10 + 'A');

}

bool Bignum::ToHexString(char* buffer, int buffer_size) const {

ASSERT(IsClamped());

// Each bigit must be printable as separate hex-character.

ASSERT(kBigitSize % 4 == 0);

const int kHexCharsPerBigit = kBigitSize / 4;

if (used_digits_ == 0) {

if (buffer_size < 2) return false;

buffer[0] = '0';

buffer[1] = '\0';

return true;

}

// We add 1 for the terminating '\0' character.

int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +

SizeInHexChars(bigits_[used_digits_ - 1]) + 1;

if (needed_chars > buffer_size) return false;

int string_index = needed_chars - 1;

buffer[string_index--] = '\0';

for (int i = 0; i < exponent_; ++i) {

for (int j = 0; j < kHexCharsPerBigit; ++j) {

buffer[string_index--] = '0';

}

}

for (int i = 0; i < used_digits_ - 1; ++i) {

Chunk current_bigit = bigits_[i];

for (int j = 0; j < kHexCharsPerBigit; ++j) {

buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);

current_bigit >>= 4;

}

}

// And finally the last bigit.

Chunk most_significant_bigit = bigits_[used_digits_ - 1];

while (most_significant_bigit != 0) {

buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);

most_significant_bigit >>= 4;

}

return true;

}

Bignum::Chunk Bignum::BigitAt(int index) const {

if (index >= BigitLength()) return 0;

if (index < exponent_) return 0;

return bigits_[index - exponent_];

}

int Bignum::Compare(const Bignum& a, const Bignum& b) {

ASSERT(a.IsClamped());

ASSERT(b.IsClamped());

int bigit_length_a = a.BigitLength();

int bigit_length_b = b.BigitLength();

if (bigit_length_a < bigit_length_b) return -1;

if (bigit_length_a > bigit_length_b) return +1;

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

Chunk bigit_a = a.BigitAt(i);

Chunk bigit_b = b.BigitAt(i);

if (bigit_a < bigit_b) return -1;

if (bigit_a > bigit_b) return +1;

}

return 0;

}

int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {

ASSERT(a.IsClamped());

ASSERT(b.IsClamped());

ASSERT(c.IsClamped());

if (a.BigitLength() < b.BigitLength()) {

return PlusCompare(b, a, c);

}

if (a.BigitLength() + 1 < c.BigitLength()) return -1;

if (a.BigitLength() > c.BigitLength()) return +1;

if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {

return -1;

}

Chunk borrow = 0;

// Starting at min_exponent all digits are == 0. So no need to compare them.

int min_exponent = std::min(std::min(a.exponent_, b.exponent_), c.exponent_);

for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {

Chunk chunk_a = a.BigitAt(i);

Chunk chunk_b = b.BigitAt(i);

Chunk chunk_c = c.BigitAt(i);

Chunk sum = chunk_a + chunk_b;

if (sum > chunk_c + borrow) {

return +1;

} else {

borrow = chunk_c + borrow - sum;

if (borrow > 1) return -1;

borrow <<= kBigitSize;

}

}

if (borrow == 0) return 0;

return -1;

}

void Bignum::Clamp() {

while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {

used_digits_--;

}

if (used_digits_ == 0) {

// Zero.

exponent_ = 0;

}

}

bool Bignum::IsClamped() const {

return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;

}

void Bignum::Zero() {

for (int i = 0; i < used_digits_; ++i) {

bigits_[i] = 0;

}

used_digits_ = 0;

exponent_ = 0;

}

void Bignum::Align(const Bignum& other) {

if (exponent_ > other.exponent_) {

int zero_digits = exponent_ - other.exponent_;

EnsureCapacity(used_digits_ + zero_digits);

for (int i = used_digits_ - 1; i >= 0; --i) {

bigits_[i + zero_digits] = bigits_[i];

}

for (int i = 0; i < zero_digits; ++i) {

bigits_[i] = 0;

}

used_digits_ += zero_digits;

exponent_ -= zero_digits;

ASSERT(used_digits_ >= 0);

ASSERT(exponent_ >= 0);

}

}

void Bignum::BigitsShiftLeft(int shift_amount) {

ASSERT(shift_amount < kBigitSize);

ASSERT(shift_amount >= 0);

Chunk carry = 0;

for (int i = 0; i < used_digits_; ++i) {

Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);

bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;

carry = new_carry;

}

if (carry != 0) {

bigits_[used_digits_] = carry;

used_digits_++;

}

}

void Bignum::SubtractTimes(const Bignum& other, int factor) {

ASSERT(exponent_ <= other.exponent_);

if (factor < 3) {

for (int i = 0; i < factor; ++i) {

SubtractBignum(other);

}

return;

}

Chunk borrow = 0;

int exponent_diff = other.exponent_ - exponent_;

for (int i = 0; i < other.used_digits_; ++i) {

DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];

DoubleChunk remove = borrow + product;

Chunk difference = bigits_[i + exponent_diff] - (remove & kBigitMask);

bigits_[i + exponent_diff] = difference & kBigitMask;

borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +

(remove >> kBigitSize));

}

for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {

if (borrow == 0) return;

Chunk difference = bigits_[i] - borrow;

bigits_[i] = difference & kBigitMask;

borrow = difference >> (kChunkSize - 1);

}

Clamp();

}

class PowersOfTenCache {

public:

static const int kDecimalExponentDistance;

static const int kMinDecimalExponent;

static const int kMaxDecimalExponent;

static void GetCachedPowerForBinaryExponentRange(int min_exponent,

int max_exponent,

DiyFp* power,

int* decimal_exponent);

static void GetCachedPowerForDecimalExponent(int requested_exponent,

DiyFp* power,

int* found_exponent);

};

struct CachedPower {

uint64_t significand;

int16_t binary_exponent;

int16_t decimal_exponent;

};

static const CachedPower kCachedPowers[] = {

{UINT64_2PART_C(0xfa8fd5a0, 081c0288), -1220, -348},

{UINT64_2PART_C(0xbaaee17f, a23ebf76), -1193, -340},

{UINT64_2PART_C(0x8b16fb20, 3055ac76), -1166, -332},

{UINT64_2PART_C(0xcf42894a, 5dce35ea), -1140, -324},

{UINT64_2PART_C(0x9a6bb0aa, 55653b2d), -1113, -316},

{UINT64_2PART_C(0xe61acf03, 3d1a45df), -1087, -308},

{UINT64_2PART_C(0xab70fe17, c79ac6ca), -1060, -300},

{UINT64_2PART_C(0xff77b1fc, bebcdc4f), -1034, -292},

{UINT64_2PART_C(0xbe5691ef, 416bd60c), -1007, -284},

{UINT64_2PART_C(0x8dd01fad, 907ffc3c), -980, -276},

{UINT64_2PART_C(0xd3515c28, 31559a83), -954, -268},

{UINT64_2PART_C(0x9d71ac8f, ada6c9b5), -927, -260},

{UINT64_2PART_C(0xea9c2277, 23ee8bcb), -901, -252},

{UINT64_2PART_C(0xaecc4991, 4078536d), -874, -244},

{UINT64_2PART_C(0x823c1279, 5db6ce57), -847, -236},

{UINT64_2PART_C(0xc2109436, 4dfb5637), -821, -228},

{UINT64_2PART_C(0x9096ea6f, 3848984f), -794, -220},

{UINT64_2PART_C(0xd77485cb, 25823ac7), -768, -212},

{UINT64_2PART_C(0xa086cfcd, 97bf97f4), -741, -204},

{UINT64_2PART_C(0xef340a98, 172aace5), -715, -196},

{UINT64_2PART_C(0xb23867fb, 2a35b28e), -688, -188},

{UINT64_2PART_C(0x84c8d4df, d2c63f3b), -661, -180},

{UINT64_2PART_C(0xc5dd4427, 1ad3cdba), -635, -172},

{UINT64_2PART_C(0x936b9fce, bb25c996), -608, -164},

{UINT64_2PART_C(0xdbac6c24, 7d62a584), -582, -156},