13fb3ca8c7ca439d408449a395897395c0faae8d1Ben Murdoch// Copyright 2011 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/bignum.h" 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/utils.h" 790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennernamespace v8 { 990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennernamespace internal { 1090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 1190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell BrennerBignum::Bignum() 1290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { 1390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < kBigitCapacity; ++i) { 1490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = 0; 1590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 1690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 1790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 1890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 1990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennertemplate<typename S> 2090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerstatic int BitSize(S value) { 2190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return 8 * sizeof(value); 2290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 2390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 2590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner// Guaranteed to lie in one Bigit. 2690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AssignUInt16(uint16_t value) { 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(kBigitSize >= BitSize(value)); 2890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Zero(); 2990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (value == 0) return; 3090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 3190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(1); 3290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[0] = value; 3390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ = 1; 3490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 3590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 3690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 3790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AssignUInt64(uint64_t value) { 3890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const int kUInt64Size = 64; 3990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 4090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Zero(); 4190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (value == 0) return; 4290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 4390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int needed_bigits = kUInt64Size / kBigitSize + 1; 4490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(needed_bigits); 4590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < needed_bigits; ++i) { 461e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bigits_[i] = static_cast<Chunk>(value & kBigitMask); 4790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner value = value >> kBigitSize; 4890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 4990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ = needed_bigits; 5090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Clamp(); 5190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 5290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 5390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 5490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AssignBignum(const Bignum& other) { 5590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner exponent_ = other.exponent_; 5690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < other.used_digits_; ++i) { 5790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = other.bigits_[i]; 5890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 5990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Clear the excess digits (if there were any). 6090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = other.used_digits_; i < used_digits_; ++i) { 6190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = 0; 6290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 6390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ = other.used_digits_; 6490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 6590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 6690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 6790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerstatic uint64_t ReadUInt64(Vector<const char> buffer, 6890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int from, 6990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int digits_to_read) { 7090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t result = 0; 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int to = from + digits_to_read; 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch for (int i = from; i < to; ++i) { 7490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int digit = buffer[i] - '0'; 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(0 <= digit && digit <= 9); 7690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner result = result * 10 + digit; 7790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 7890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return result; 7990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 8090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 8190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 8290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AssignDecimalString(Vector<const char> value) { 8390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 2^64 = 18446744073709551616 > 10^19 8490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const int kMaxUint64DecimalDigits = 19; 8590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Zero(); 8690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int length = value.length(); 8790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int pos = 0; 8890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Let's just say that each digit needs 4 bits. 8990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (length >= kMaxUint64DecimalDigits) { 9090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits); 9190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner pos += kMaxUint64DecimalDigits; 9290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner length -= kMaxUint64DecimalDigits; 9390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner MultiplyByPowerOfTen(kMaxUint64DecimalDigits); 9490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner AddUInt64(digits); 9590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 9690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t digits = ReadUInt64(value, pos, length); 9790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner MultiplyByPowerOfTen(length); 9890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner AddUInt64(digits); 9990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Clamp(); 10090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 10190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 10290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 10390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerstatic int HexCharValue(char c) { 10490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if ('0' <= c && c <= '9') return c - '0'; 10590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if ('a' <= c && c <= 'f') return 10 + c - 'a'; 10690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if ('A' <= c && c <= 'F') return 10 + c - 'A'; 10790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner UNREACHABLE(); 10890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return 0; // To make compiler happy. 10990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 11090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 11190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 11290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AssignHexString(Vector<const char> value) { 11390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Zero(); 11490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int length = value.length(); 11590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 11690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int needed_bigits = length * 4 / kBigitSize + 1; 11790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(needed_bigits); 11890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int string_index = length - 1; 11990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < needed_bigits - 1; ++i) { 12090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // These bigits are guaranteed to be "full". 12190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk current_bigit = 0; 12290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int j = 0; j < kBigitSize / 4; j++) { 12390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner current_bigit += HexCharValue(value[string_index--]) << (j * 4); 12490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 12590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = current_bigit; 12690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 12790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ = needed_bigits - 1; 12890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 12990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk most_significant_bigit = 0; // Could be = 0; 13090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int j = 0; j <= string_index; ++j) { 13190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner most_significant_bigit <<= 4; 13290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner most_significant_bigit += HexCharValue(value[j]); 13390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 13490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (most_significant_bigit != 0) { 13590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[used_digits_] = most_significant_bigit; 13690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_++; 13790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 13890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Clamp(); 13990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 14090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 14190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 14290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AddUInt64(uint64_t operand) { 14390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (operand == 0) return; 14490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Bignum other; 14590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner other.AssignUInt64(operand); 14690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner AddBignum(other); 14790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 14890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 14990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 15090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AddBignum(const Bignum& other) { 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsClamped()); 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(other.IsClamped()); 15390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 15490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // If this has a greater exponent than other append zero-bigits to this. 15590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // After this call exponent_ <= other.exponent_. 15690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Align(other); 15790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 15890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // There are two possibilities: 15990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) 16090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // bbbbb 00000000 16190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // ---------------- 16290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // ccccccccccc 0000 16390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // or 16490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // aaaaaaaaaa 0000 16590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // bbbbbbbbb 0000000 16690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // ----------------- 16790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // cccccccccccc 0000 16890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // In both cases we might need a carry bigit. 16990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 17090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); 17190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk carry = 0; 17290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bigit_pos = other.exponent_ - exponent_; 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(bigit_pos >= 0); 17490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < other.used_digits_; ++i) { 17590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; 17690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[bigit_pos] = sum & kBigitMask; 17790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner carry = sum >> kBigitSize; 17890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigit_pos++; 17990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 18090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 18190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (carry != 0) { 18290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk sum = bigits_[bigit_pos] + carry; 18390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[bigit_pos] = sum & kBigitMask; 18490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner carry = sum >> kBigitSize; 18590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigit_pos++; 18690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 18790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ = Max(bigit_pos, used_digits_); 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsClamped()); 18990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 19090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 19190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 19290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::SubtractBignum(const Bignum& other) { 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsClamped()); 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(other.IsClamped()); 19590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // We require this to be bigger than other. 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(LessEqual(other, *this)); 19790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 19890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Align(other); 19990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 20090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int offset = other.exponent_ - exponent_; 20190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk borrow = 0; 20290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int i; 20390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (i = 0; i < other.used_digits_; ++i) { 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK((borrow == 0) || (borrow == 1)); 20590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; 20690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i + offset] = difference & kBigitMask; 20790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner borrow = difference >> (kChunkSize - 1); 20890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 20990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (borrow != 0) { 21090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk difference = bigits_[i + offset] - borrow; 21190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i + offset] = difference & kBigitMask; 21290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner borrow = difference >> (kChunkSize - 1); 21390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner ++i; 21490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 21590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Clamp(); 21690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 21790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 21890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 21990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::ShiftLeft(int shift_amount) { 22090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (used_digits_ == 0) return; 22190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner exponent_ += shift_amount / kBigitSize; 22290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int local_shift = shift_amount % kBigitSize; 22390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(used_digits_ + 1); 22490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner BigitsShiftLeft(local_shift); 22590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 22690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 22790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 22890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::MultiplyByUInt32(uint32_t factor) { 22990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (factor == 1) return; 23090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (factor == 0) { 23190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Zero(); 23290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return; 23390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 23490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (used_digits_ == 0) return; 23590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 23690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // The product of a bigit with the factor is of size kBigitSize + 32. 23790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Assert that this number + 1 (for the carry) fits into double chunk. 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(kDoubleChunkSize >= kBigitSize + 32 + 1); 23990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner DoubleChunk carry = 0; 24090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < used_digits_; ++i) { 24190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry; 24290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = static_cast<Chunk>(product & kBigitMask); 24390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner carry = (product >> kBigitSize); 24490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 24590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (carry != 0) { 24690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(used_digits_ + 1); 2471e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask); 24890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_++; 24990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner carry >>= kBigitSize; 25090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 25190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 25290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 25390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 25490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::MultiplyByUInt64(uint64_t factor) { 25590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (factor == 1) return; 25690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (factor == 0) { 25790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Zero(); 25890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return; 25990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 260b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(kBigitSize < 32); 26190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t carry = 0; 26290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t low = factor & 0xFFFFFFFF; 26390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t high = factor >> 32; 26490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < used_digits_; ++i) { 26590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t product_low = low * bigits_[i]; 26690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t product_high = high * bigits_[i]; 26790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t tmp = (carry & kBigitMask) + product_low; 2681e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bigits_[i] = static_cast<Chunk>(tmp & kBigitMask); 26990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner carry = (carry >> kBigitSize) + (tmp >> kBigitSize) + 27090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner (product_high << (32 - kBigitSize)); 27190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 27290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (carry != 0) { 27390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(used_digits_ + 1); 2741e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bigits_[used_digits_] = static_cast<Chunk>(carry & kBigitMask); 27590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_++; 27690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner carry >>= kBigitSize; 27790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 27890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 27990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 28090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 28190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::MultiplyByPowerOfTen(int exponent) { 28290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint64_t kFive27 = V8_2PART_UINT64_C(0x6765c793, fa10079d); 28390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint16_t kFive1 = 5; 28490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint16_t kFive2 = kFive1 * 5; 28590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint16_t kFive3 = kFive2 * 5; 28690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint16_t kFive4 = kFive3 * 5; 28790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint16_t kFive5 = kFive4 * 5; 28890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint16_t kFive6 = kFive5 * 5; 28990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive7 = kFive6 * 5; 29090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive8 = kFive7 * 5; 29190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive9 = kFive8 * 5; 29290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive10 = kFive9 * 5; 29390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive11 = kFive10 * 5; 29490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive12 = kFive11 * 5; 29590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive13 = kFive12 * 5; 29690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint32_t kFive1_to_12[] = 29790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, 29890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; 29990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 300b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(exponent >= 0); 30190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (exponent == 0) return; 30290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (used_digits_ == 0) return; 30390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 30490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // We shift by exponent at the end just before returning. 30590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int remaining_exponent = exponent; 30690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (remaining_exponent >= 27) { 30790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner MultiplyByUInt64(kFive27); 30890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner remaining_exponent -= 27; 30990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 31090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (remaining_exponent >= 13) { 31190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner MultiplyByUInt32(kFive13); 31290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner remaining_exponent -= 13; 31390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 31490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (remaining_exponent > 0) { 31590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); 31690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 31790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner ShiftLeft(exponent); 31890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 31990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 32090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 32190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::Square() { 322b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsClamped()); 32390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int product_length = 2 * used_digits_; 32490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(product_length); 32590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 32690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Comba multiplication: compute each column separately. 32790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Example: r = a2a1a0 * b2b1b0. 32890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // r = 1 * a0b0 + 32990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 10 * (a1b0 + a0b1) + 33090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 100 * (a2b0 + a1b1 + a0b2) + 33190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 1000 * (a2b1 + a1b2) + 33290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 10000 * a2b2 33390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 33490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // In the worst case we have to accumulate nb-digits products of digit*digit. 33590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 33690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Assert that the additional number of bits in a DoubleChunk are enough to 33790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // sum up used_digits of Bigit*Bigit. 33890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { 33990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner UNIMPLEMENTED(); 34090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 34190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner DoubleChunk accumulator = 0; 34290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // First shift the digits so we don't overwrite them. 34390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int copy_offset = used_digits_; 34490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < used_digits_; ++i) { 34590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[copy_offset + i] = bigits_[i]; 34690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 34790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // We have two loops to avoid some 'if's in the loop. 34890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < used_digits_; ++i) { 34990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Process temporary digit i with power i. 35090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // The sum of the two indices must be equal to i. 35190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bigit_index1 = i; 35290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bigit_index2 = 0; 35390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Sum all of the sub-products. 35490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (bigit_index1 >= 0) { 35590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 35690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 35790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 35890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigit_index1--; 35990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigit_index2++; 36090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 36190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 36290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner accumulator >>= kBigitSize; 36390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 36490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = used_digits_; i < product_length; ++i) { 36590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bigit_index1 = used_digits_ - 1; 36690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bigit_index2 = i - bigit_index1; 36790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Invariant: sum of both indices is again equal to i. 36890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Inner loop runs 0 times on last iteration, emptying accumulator. 36990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (bigit_index2 < used_digits_) { 37090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 37190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 37290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 37390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigit_index1--; 37490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigit_index2++; 37590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 37690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // The overwritten bigits_[i] will never be read in further loop iterations, 37790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // because bigit_index1 and bigit_index2 are always greater 37890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // than i - used_digits_. 37990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 38090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner accumulator >>= kBigitSize; 38190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 38290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Since the result was guaranteed to lie inside the number the 38390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // accumulator must be 0 now. 384b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(accumulator == 0); 38590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 38690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Don't forget to update the used_digits and the exponent. 38790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ = product_length; 38890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner exponent_ *= 2; 38990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Clamp(); 39090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 39190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 39290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 39390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { 394b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(base != 0); 395b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(power_exponent >= 0); 39690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (power_exponent == 0) { 39790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner AssignUInt16(1); 39890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return; 39990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 40090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Zero(); 40190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int shifts = 0; 40290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // We expect base to be in range 2-32, and most often to be 10. 40390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // It does not make much sense to implement different algorithms for counting 40490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // the bits. 40590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while ((base & 1) == 0) { 40690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner base >>= 1; 40790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner shifts++; 40890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 40990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bit_size = 0; 41090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int tmp_base = base; 41190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (tmp_base != 0) { 41290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner tmp_base >>= 1; 41390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bit_size++; 41490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 41590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int final_size = bit_size * power_exponent; 41690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 1 extra bigit for the shifting, and one for rounded final_size. 41790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(final_size / kBigitSize + 2); 41890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 41990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Left to Right exponentiation. 42090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int mask = 1; 42190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (power_exponent >= mask) mask <<= 1; 42290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 42390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // The mask is now pointing to the bit above the most significant 1-bit of 42490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // power_exponent. 42590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Get rid of first 1-bit; 42690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner mask >>= 2; 42790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t this_value = base; 42890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 42990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bool delayed_multipliciation = false; 43090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const uint64_t max_32bits = 0xFFFFFFFF; 43190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (mask != 0 && this_value <= max_32bits) { 43290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner this_value = this_value * this_value; 43390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Verify that there is enough space in this_value to perform the 43490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // multiplication. The first bit_size bits must be 0. 43590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if ((power_exponent & mask) != 0) { 43690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint64_t base_bits_mask = 43790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); 43890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bool high_bits_zero = (this_value & base_bits_mask) == 0; 43990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (high_bits_zero) { 44090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner this_value *= base; 44190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } else { 44290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner delayed_multipliciation = true; 44390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 44490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 44590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner mask >>= 1; 44690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 44790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner AssignUInt64(this_value); 44890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (delayed_multipliciation) { 44990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner MultiplyByUInt32(base); 45090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 45190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 45290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Now do the same thing as a bignum. 45390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (mask != 0) { 45490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Square(); 45590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if ((power_exponent & mask) != 0) { 45690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner MultiplyByUInt32(base); 45790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 45890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner mask >>= 1; 45990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 46090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 46190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // And finally add the saved shifts. 46290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner ShiftLeft(shifts * power_exponent); 46390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 46490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 46590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 46690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner// Precondition: this/other < 16bit. 46790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenneruint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { 468b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsClamped()); 469b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(other.IsClamped()); 470b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(other.used_digits_ > 0); 47190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 47290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Easy case: if we have less digits than the divisor than the result is 0. 47390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Note: this handles the case where this == 0, too. 47490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (BigitLength() < other.BigitLength()) { 47590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return 0; 47690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 47790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 47890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Align(other); 47990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 48090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner uint16_t result = 0; 48190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 48290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Start by removing multiples of 'other' until both numbers have the same 48390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // number of digits. 48490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (BigitLength() > other.BigitLength()) { 48590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // This naive approach is extremely inefficient if the this divided other 48690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // might be big. This function is implemented for doubleToString where 48790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // the result should be small (less than 10). 488b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); 48990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Remove the multiples of the first digit. 49090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Example this = 23 and other equals 9. -> Remove 2 multiples. 49190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner result += bigits_[used_digits_ - 1]; 49290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner SubtractTimes(other, bigits_[used_digits_ - 1]); 49390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 49490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 495b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(BigitLength() == other.BigitLength()); 49690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 49790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Both bignums are at the same length now. 49890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Since other has more than 0 digits we know that the access to 49990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // bigits_[used_digits_ - 1] is safe. 50090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk this_bigit = bigits_[used_digits_ - 1]; 50190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; 50290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 50390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (other.used_digits_ == 1) { 50490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Shortcut for easy (and common) case. 50590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int quotient = this_bigit / other_bigit; 50690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; 50790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner result += quotient; 50890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Clamp(); 50990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return result; 51090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 51190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 51290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int division_estimate = this_bigit / (other_bigit + 1); 51390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner result += division_estimate; 51490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner SubtractTimes(other, division_estimate); 51590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 51690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (other_bigit * (division_estimate + 1) > this_bigit) { 51790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // No need to even try to subtract. Even if other's remaining digits were 0 51890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // another subtraction would be too much. 51990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return result; 52090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 52190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 52290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (LessEqual(other, *this)) { 52390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner SubtractBignum(other); 52490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner result++; 52590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 52690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return result; 52790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 52890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 52990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 53090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennertemplate<typename S> 53190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerstatic int SizeInHexChars(S number) { 532b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(number > 0); 53390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int result = 0; 53490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (number != 0) { 53590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner number >>= 4; 53690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner result++; 53790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 53890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return result; 53990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 54090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 54190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 54290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerbool Bignum::ToHexString(char* buffer, int buffer_size) const { 543b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(IsClamped()); 54490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Each bigit must be printable as separate hex-character. 545b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(kBigitSize % 4 == 0); 54690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner const int kHexCharsPerBigit = kBigitSize / 4; 54790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 54890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (used_digits_ == 0) { 54990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (buffer_size < 2) return false; 55090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner buffer[0] = '0'; 55190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner buffer[1] = '\0'; 55290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return true; 55390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 55490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // We add 1 for the terminating '\0' character. 55590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + 55690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner SizeInHexChars(bigits_[used_digits_ - 1]) + 1; 55790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (needed_chars > buffer_size) return false; 55890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int string_index = needed_chars - 1; 55990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner buffer[string_index--] = '\0'; 56090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < exponent_; ++i) { 56190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int j = 0; j < kHexCharsPerBigit; ++j) { 56290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner buffer[string_index--] = '0'; 56390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 56490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 56590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < used_digits_ - 1; ++i) { 56690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk current_bigit = bigits_[i]; 56790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int j = 0; j < kHexCharsPerBigit; ++j) { 56890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner buffer[string_index--] = HexCharOfValue(current_bigit & 0xF); 56990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner current_bigit >>= 4; 57090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 57190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 57290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // And finally the last bigit. 57390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk most_significant_bigit = bigits_[used_digits_ - 1]; 57490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (most_significant_bigit != 0) { 57590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF); 57690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner most_significant_bigit >>= 4; 57790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 57890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return true; 57990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 58090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 58190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 58290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell BrennerBignum::Chunk Bignum::BigitAt(int index) const { 58390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (index >= BigitLength()) return 0; 58490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (index < exponent_) return 0; 58590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return bigits_[index - exponent_]; 58690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 58790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 58890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 58990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerint Bignum::Compare(const Bignum& a, const Bignum& b) { 590b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(a.IsClamped()); 591b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(b.IsClamped()); 59290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bigit_length_a = a.BigitLength(); 59390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int bigit_length_b = b.BigitLength(); 59490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (bigit_length_a < bigit_length_b) return -1; 59590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (bigit_length_a > bigit_length_b) return +1; 59690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) { 59790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk bigit_a = a.BigitAt(i); 59890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk bigit_b = b.BigitAt(i); 59990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (bigit_a < bigit_b) return -1; 60090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (bigit_a > bigit_b) return +1; 60190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Otherwise they are equal up to this digit. Try the next digit. 60290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 60390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return 0; 60490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 60590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 60690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 60790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerint Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { 608b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(a.IsClamped()); 609b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(b.IsClamped()); 610b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(c.IsClamped()); 61190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (a.BigitLength() < b.BigitLength()) { 61290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return PlusCompare(b, a, c); 61390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 61490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (a.BigitLength() + 1 < c.BigitLength()) return -1; 61590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (a.BigitLength() > c.BigitLength()) return +1; 61690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than 61790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one 61890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // of 'a'. 61990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { 62090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return -1; 62190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 62290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 62390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk borrow = 0; 62490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Starting at min_exponent all digits are == 0. So no need to compare them. 62590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_); 62690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { 62790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk chunk_a = a.BigitAt(i); 62890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk chunk_b = b.BigitAt(i); 62990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk chunk_c = c.BigitAt(i); 63090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk sum = chunk_a + chunk_b; 63190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (sum > chunk_c + borrow) { 63290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return +1; 63390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } else { 63490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner borrow = chunk_c + borrow - sum; 63590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (borrow > 1) return -1; 63690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner borrow <<= kBigitSize; 63790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 63890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 63990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (borrow == 0) return 0; 64090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return -1; 64190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 64290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 64390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 64490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::Clamp() { 64590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { 64690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_--; 64790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 64890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (used_digits_ == 0) { 64990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // Zero. 65090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner exponent_ = 0; 65190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 65290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 65390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 65490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 65590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennerbool Bignum::IsClamped() const { 65690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; 65790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 65890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 65990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 66090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::Zero() { 66190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < used_digits_; ++i) { 66290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = 0; 66390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 66490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ = 0; 66590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner exponent_ = 0; 66690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 66790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 66890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 66990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::Align(const Bignum& other) { 67090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (exponent_ > other.exponent_) { 67190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // If "X" represents a "hidden" digit (by the exponent) then we are in the 67290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // following case (a == this, b == other): 67390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // a: aaaaaaXXXX or a: aaaaaXXX 67490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // b: bbbbbbX b: bbbbbbbbXX 67590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // We replace some of the hidden digits (X) of a with 0 digits. 67690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner // a: aaaaaa000X or a: aaaaa0XX 67790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int zero_digits = exponent_ - other.exponent_; 67890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner EnsureCapacity(used_digits_ + zero_digits); 67990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = used_digits_ - 1; i >= 0; --i) { 68090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i + zero_digits] = bigits_[i]; 68190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 68290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < zero_digits; ++i) { 68390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = 0; 68490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 68590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_ += zero_digits; 68690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner exponent_ -= zero_digits; 687b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(used_digits_ >= 0); 688b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(exponent_ >= 0); 68990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 69090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 69190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 69290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 69390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::BigitsShiftLeft(int shift_amount) { 694b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(shift_amount < kBigitSize); 695b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(shift_amount >= 0); 69690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk carry = 0; 69790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < used_digits_; ++i) { 69890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); 69990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; 70090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner carry = new_carry; 70190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 70290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (carry != 0) { 70390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[used_digits_] = carry; 70490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner used_digits_++; 70590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 70690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 70790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 70890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 70990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brennervoid Bignum::SubtractTimes(const Bignum& other, int factor) { 710b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifdef DEBUG 711b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Bignum a, b; 712b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch a.AssignBignum(*this); 713b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch b.AssignBignum(other); 714b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch b.MultiplyByUInt32(factor); 715b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch a.SubtractBignum(b); 716b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif 717b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(exponent_ <= other.exponent_); 71890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (factor < 3) { 71990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < factor; ++i) { 72090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner SubtractBignum(other); 72190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 72290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner return; 72390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 72490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk borrow = 0; 72590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner int exponent_diff = other.exponent_ - exponent_; 72690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = 0; i < other.used_digits_; ++i) { 72790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i]; 72890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner DoubleChunk remove = borrow + product; 7291e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block Chunk difference = 7301e0659c275bb392c045087af4f6b0d7565cb3d77Steve Block bigits_[i + exponent_diff] - static_cast<Chunk>(remove & kBigitMask); 73190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i + exponent_diff] = difference & kBigitMask; 73290bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + 73390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner (remove >> kBigitSize)); 73490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 73590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { 73690bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner if (borrow == 0) return; 73790bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Chunk difference = bigits_[i] - borrow; 73890bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner bigits_[i] = difference & kBigitMask; 73990bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner borrow = difference >> (kChunkSize - 1); 74090bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner } 74190bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner Clamp(); 742b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(Bignum::Equal(a, *this)); 74390bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner} 74490bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 74590bac256d9f48d4ee52d0e08bf0e5cad57b3c51cRussell Brenner 746014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 747014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 748