36Bignum::Chunk& Bignum::RawBigit(
const int index) {
38 return bigits_buffer_[index];
42const Bignum::Chunk& Bignum::RawBigit(
const int index)
const {
44 return bigits_buffer_[index];
51 return 8 *
sizeof(
value);
67 for(
int i = 0;
value > 0; ++i) {
68 RawBigit(i) =
value & kBigitMask;
76 exponent_ = other.exponent_;
77 for (
int i = 0; i < other.used_bigits_; ++i) {
78 RawBigit(i) = other.RawBigit(i);
80 used_bigits_ = other.used_bigits_;
86 const int digits_to_read) {
88 for (
int i = from; i < from + digits_to_read; ++i) {
89 const int digit =
buffer[i] -
'0';
119 if (
'0' <= c && c <=
'9') {
122 if (
'a' <= c && c <=
'f') {
135 EnsureCapacity(((
value.length() * 4) + kBigitSize - 1) / kBigitSize);
140 for (
int cnt = 0; !
value.is_empty();
value.pop_back()) {
142 if ((cnt += 4) >= kBigitSize) {
143 RawBigit(used_bigits_++) = (tmp & kBigitMask);
150 RawBigit(used_bigits_++) =
static_cast<Bignum::Chunk
>(tmp & kBigitMask);
186 EnsureCapacity(1 + (std::max)(BigitLength(), other.BigitLength()) - exponent_);
188 int bigit_pos = other.exponent_ - exponent_;
190 for (
int i = used_bigits_; i < bigit_pos; ++i) {
193 for (
int i = 0; i < other.used_bigits_; ++i) {
194 const Chunk my = (bigit_pos < used_bigits_) ? RawBigit(bigit_pos) : 0;
195 const Chunk sum = my + other.RawBigit(i) + carry;
196 RawBigit(bigit_pos) = sum & kBigitMask;
197 carry = sum >> kBigitSize;
201 const Chunk my = (bigit_pos < used_bigits_) ? RawBigit(bigit_pos) : 0;
202 const Chunk sum = my + carry;
203 RawBigit(bigit_pos) = sum & kBigitMask;
204 carry = sum >> kBigitSize;
207 used_bigits_ =
static_cast<int16_t
>(std::max(bigit_pos,
static_cast<int>(used_bigits_)));
220 const int offset = other.exponent_ - exponent_;
223 for (i = 0; i < other.used_bigits_; ++i) {
229 while (borrow != 0) {
240 if (used_bigits_ == 0) {
243 exponent_ +=
static_cast<int16_t
>(shift_amount / kBigitSize);
244 const int local_shift = shift_amount % kBigitSize;
245 EnsureCapacity(used_bigits_ + 1);
246 BigitsShiftLeft(local_shift);
258 if (used_bigits_ == 0) {
264 DoubleChunk carry = 0;
265 for (
int i = 0; i < used_bigits_; ++i) {
266 const DoubleChunk product =
static_cast<DoubleChunk
>(factor) * RawBigit(i) + carry;
267 RawBigit(i) =
static_cast<Chunk
>(product & kBigitMask);
268 carry = (product >> kBigitSize);
271 EnsureCapacity(used_bigits_ + 1);
272 RawBigit(used_bigits_) = carry & kBigitMask;
274 carry >>= kBigitSize;
287 if (used_bigits_ == 0) {
292 const uint64_t low = factor & 0xFFFFFFFF;
293 const uint64_t high = factor >> 32;
294 for (
int i = 0; i < used_bigits_; ++i) {
295 const uint64_t product_low = low * RawBigit(i);
296 const uint64_t product_high = high * RawBigit(i);
297 const uint64_t tmp = (carry & kBigitMask) + product_low;
298 RawBigit(i) = tmp & kBigitMask;
299 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
300 (product_high << (32 - kBigitSize));
303 EnsureCapacity(used_bigits_ + 1);
304 RawBigit(used_bigits_) = carry & kBigitMask;
306 carry >>= kBigitSize;
313 static const uint16_t kFive1 = 5;
314 static const uint16_t kFive2 = kFive1 * 5;
315 static const uint16_t kFive3 = kFive2 * 5;
316 static const uint16_t kFive4 = kFive3 * 5;
317 static const uint16_t kFive5 = kFive4 * 5;
318 static const uint16_t kFive6 = kFive5 * 5;
319 static const uint32_t kFive7 = kFive6 * 5;
320 static const uint32_t kFive8 = kFive7 * 5;
321 static const uint32_t kFive9 = kFive8 * 5;
322 static const uint32_t kFive10 = kFive9 * 5;
323 static const uint32_t kFive11 = kFive10 * 5;
324 static const uint32_t kFive12 = kFive11 * 5;
325 static const uint32_t kFive13 = kFive12 * 5;
326 static const uint32_t kFive1_to_12[] =
327 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6,
328 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 };
335 if (used_bigits_ == 0) {
339 int remaining_exponent = exponent;
340 while (remaining_exponent >= 27) {
342 remaining_exponent -= 27;
344 while (remaining_exponent >= 13) {
346 remaining_exponent -= 13;
348 if (remaining_exponent > 0) {
357 const int product_length = 2 * used_bigits_;
358 EnsureCapacity(product_length);
372 if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_bigits_) {
375 DoubleChunk accumulator = 0;
377 const int copy_offset = used_bigits_;
378 for (
int i = 0; i < used_bigits_; ++i) {
379 RawBigit(copy_offset + i) = RawBigit(i);
382 for (
int i = 0; i < used_bigits_; ++i) {
385 int bigit_index1 = i;
386 int bigit_index2 = 0;
388 while (bigit_index1 >= 0) {
389 const Chunk chunk1 = RawBigit(copy_offset + bigit_index1);
390 const Chunk chunk2 = RawBigit(copy_offset + bigit_index2);
391 accumulator +=
static_cast<DoubleChunk
>(chunk1) * chunk2;
395 RawBigit(i) =
static_cast<Chunk
>(accumulator) & kBigitMask;
396 accumulator >>= kBigitSize;
398 for (
int i = used_bigits_; i < product_length; ++i) {
399 int bigit_index1 = used_bigits_ - 1;
400 int bigit_index2 = i - bigit_index1;
403 while (bigit_index2 < used_bigits_) {
404 const Chunk chunk1 = RawBigit(copy_offset + bigit_index1);
405 const Chunk chunk2 = RawBigit(copy_offset + bigit_index2);
406 accumulator +=
static_cast<DoubleChunk
>(chunk1) * chunk2;
413 RawBigit(i) =
static_cast<Chunk
>(accumulator) & kBigitMask;
414 accumulator >>= kBigitSize;
421 used_bigits_ =
static_cast<int16_t
>(product_length);
430 if (power_exponent == 0) {
439 while ((
base & 1) == 0) {
445 while (tmp_base != 0) {
449 const int final_size = bit_size * power_exponent;
451 EnsureCapacity(final_size / kBigitSize + 2);
455 while (power_exponent >= mask) mask <<= 1;
461 uint64_t this_value =
base;
463 bool delayed_multiplication =
false;
464 const uint64_t max_32bits = 0xFFFFFFFF;
465 while (mask != 0 && this_value <= max_32bits) {
466 this_value = this_value * this_value;
469 if ((power_exponent & mask) != 0) {
471 const uint64_t base_bits_mask =
472 ~((
static_cast<uint64_t
>(1) << (64 - bit_size)) - 1);
473 const bool high_bits_zero = (this_value & base_bits_mask) == 0;
474 if (high_bits_zero) {
477 delayed_multiplication =
true;
483 if (delayed_multiplication) {
490 if ((power_exponent & mask) != 0) {
509 if (BigitLength() < other.BigitLength()) {
519 while (BigitLength() > other.BigitLength()) {
527 result +=
static_cast<uint16_t
>(RawBigit(used_bigits_ - 1));
528 SubtractTimes(other, RawBigit(used_bigits_ - 1));
536 const Chunk this_bigit = RawBigit(used_bigits_ - 1);
537 const Chunk other_bigit = other.RawBigit(other.used_bigits_ - 1);
539 if (other.used_bigits_ == 1) {
541 int quotient = this_bigit / other_bigit;
542 RawBigit(used_bigits_ - 1) = this_bigit - other_bigit * quotient;
544 result +=
static_cast<uint16_t
>(quotient);
549 const int division_estimate = this_bigit / (other_bigit + 1);
551 result +=
static_cast<uint16_t
>(division_estimate);
552 SubtractTimes(other, division_estimate);
554 if (other_bigit * (division_estimate + 1) > this_bigit) {
572 while (number != 0) {
583 return static_cast<char>(
value +
'0');
585 return static_cast<char>(
value - 10 +
'A');
593 static const int kHexCharsPerBigit = kBigitSize / 4;
595 if (used_bigits_ == 0) {
604 const int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
609 int string_index = needed_chars - 1;
610 buffer[string_index--] =
'\0';
611 for (
int i = 0; i < exponent_; ++i) {
612 for (
int j = 0; j < kHexCharsPerBigit; ++j) {
613 buffer[string_index--] =
'0';
616 for (
int i = 0; i < used_bigits_ - 1; ++i) {
617 Chunk current_bigit = RawBigit(i);
618 for (
int j = 0; j < kHexCharsPerBigit; ++j) {
624 Chunk most_significant_bigit = RawBigit(used_bigits_ - 1);
625 while (most_significant_bigit != 0) {
627 most_significant_bigit >>= 4;
633Bignum::Chunk Bignum::BigitOrZero(
const int index)
const {
634 if (index >= BigitLength()) {
637 if (index < exponent_) {
640 return RawBigit(index - exponent_);
647 const int bigit_length_a =
a.BigitLength();
648 const int bigit_length_b =
b.BigitLength();
649 if (bigit_length_a < bigit_length_b) {
652 if (bigit_length_a > bigit_length_b) {
655 for (
int i = bigit_length_a - 1; i >= (std::min)(
a.exponent_,
b.exponent_); --i) {
656 const Chunk bigit_a =
a.BigitOrZero(i);
657 const Chunk bigit_b =
b.BigitOrZero(i);
658 if (bigit_a < bigit_b) {
661 if (bigit_a > bigit_b) {
674 if (
a.BigitLength() <
b.BigitLength()) {
677 if (
a.BigitLength() + 1 < c.BigitLength()) {
680 if (
a.BigitLength() > c.BigitLength()) {
686 if (
a.exponent_ >=
b.BigitLength() &&
a.BigitLength() < c.BigitLength()) {
692 const int min_exponent = (std::min)((std::min)(
a.exponent_,
b.exponent_), c.exponent_);
693 for (
int i = c.BigitLength() - 1; i >= min_exponent; --i) {
694 const Chunk chunk_a =
a.BigitOrZero(i);
695 const Chunk chunk_b =
b.BigitOrZero(i);
696 const Chunk chunk_c = c.BigitOrZero(i);
697 const Chunk sum = chunk_a + chunk_b;
698 if (sum > chunk_c + borrow) {
701 borrow = chunk_c + borrow - sum;
705 borrow <<= kBigitSize;
715void Bignum::Clamp() {
716 while (used_bigits_ > 0 && RawBigit(used_bigits_ - 1) == 0) {
719 if (used_bigits_ == 0) {
726void Bignum::Align(
const Bignum& other) {
727 if (exponent_ > other.exponent_) {
734 const int zero_bigits = exponent_ - other.exponent_;
735 EnsureCapacity(used_bigits_ + zero_bigits);
736 for (
int i = used_bigits_ - 1; i >= 0; --i) {
737 RawBigit(i + zero_bigits) = RawBigit(i);
739 for (
int i = 0; i < zero_bigits; ++i) {
742 used_bigits_ +=
static_cast<int16_t
>(zero_bigits);
743 exponent_ -=
static_cast<int16_t
>(zero_bigits);
751void Bignum::BigitsShiftLeft(
const int shift_amount) {
755 for (
int i = 0; i < used_bigits_; ++i) {
756 const Chunk new_carry = RawBigit(i) >> (kBigitSize - shift_amount);
757 RawBigit(i) = ((RawBigit(i) << shift_amount) + carry) & kBigitMask;
761 RawBigit(used_bigits_) = carry;
767void Bignum::SubtractTimes(
const Bignum& other,
const int factor) {
770 for (
int i = 0; i < factor; ++i) {
776 const int exponent_diff = other.exponent_ - exponent_;
777 for (
int i = 0; i < other.used_bigits_; ++i) {
778 const DoubleChunk product =
static_cast<DoubleChunk
>(factor) * other.RawBigit(i);
779 const DoubleChunk
remove = borrow + product;
780 const Chunk
difference = RawBigit(i + exponent_diff) - (
remove & kBigitMask);
781 RawBigit(i + exponent_diff) =
difference & kBigitMask;
782 borrow =
static_cast<Chunk
>((
difference >> (kChunkSize - 1)) +
785 for (
int i = other.used_bigits_ + exponent_diff; i < used_bigits_; ++i) {
789 const Chunk
difference = RawBigit(i) - borrow;
static uint32_t buffer_size(uint32_t offset, uint32_t maxAlignment)
static size_t difference(size_t minuend, size_t subtrahend)
static int Compare(const Bignum &a, const Bignum &b)
void AssignBignum(const Bignum &other)
void ShiftLeft(const int shift_amount)
void AssignDecimalString(const Vector< const char > value)
void MultiplyByPowerOfTen(const int exponent)
void AddUInt64(const uint64_t operand)
void AssignUInt64(uint64_t value)
uint16_t DivideModuloIntBignum(const Bignum &other)
static bool LessEqual(const Bignum &a, const Bignum &b)
void AssignPowerUInt16(uint16_t base, const int exponent)
void MultiplyByUInt32(const uint32_t factor)
void SubtractBignum(const Bignum &other)
void AssignUInt16(const uint16_t value)
void MultiplyByUInt64(const uint64_t factor)
void AddBignum(const Bignum &other)
void AssignHexString(const Vector< const char > value)
static int PlusCompare(const Bignum &a, const Bignum &b, const Bignum &c)
bool ToHexString(char *buffer, const int buffer_size) const
static const uint8_t buffer[]
static int SizeInHexChars(S number)
static int BitSize(const S value)
static uint64_t HexCharValue(const int c)
static char HexCharOfValue(const int value)
static uint64_t ReadUInt64(const Vector< const char > buffer, const int from, const int digits_to_read)
static const int kMaxUint64DecimalDigits
#define DOUBLE_CONVERSION_ASSERT(condition)
#define DOUBLE_CONVERSION_UNIMPLEMENTED()
#define DOUBLE_CONVERSION_UINT64_2PART_C(a, b)