1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/double-conversion/bignum.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,145 @@
1.4 +// Copyright 2010 the V8 project authors. All rights reserved.
1.5 +// Redistribution and use in source and binary forms, with or without
1.6 +// modification, are permitted provided that the following conditions are
1.7 +// met:
1.8 +//
1.9 +// * Redistributions of source code must retain the above copyright
1.10 +// notice, this list of conditions and the following disclaimer.
1.11 +// * Redistributions in binary form must reproduce the above
1.12 +// copyright notice, this list of conditions and the following
1.13 +// disclaimer in the documentation and/or other materials provided
1.14 +// with the distribution.
1.15 +// * Neither the name of Google Inc. nor the names of its
1.16 +// contributors may be used to endorse or promote products derived
1.17 +// from this software without specific prior written permission.
1.18 +//
1.19 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.20 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.21 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.22 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.23 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.24 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.25 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.26 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.27 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.28 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.29 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.30 +
1.31 +#ifndef DOUBLE_CONVERSION_BIGNUM_H_
1.32 +#define DOUBLE_CONVERSION_BIGNUM_H_
1.33 +
1.34 +#include "utils.h"
1.35 +
1.36 +namespace double_conversion {
1.37 +
1.38 +class Bignum {
1.39 + public:
1.40 + // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.
1.41 + // This bignum can encode much bigger numbers, since it contains an
1.42 + // exponent.
1.43 + static const int kMaxSignificantBits = 3584;
1.44 +
1.45 + Bignum();
1.46 + void AssignUInt16(uint16_t value);
1.47 + void AssignUInt64(uint64_t value);
1.48 + void AssignBignum(const Bignum& other);
1.49 +
1.50 + void AssignDecimalString(Vector<const char> value);
1.51 + void AssignHexString(Vector<const char> value);
1.52 +
1.53 + void AssignPowerUInt16(uint16_t base, int exponent);
1.54 +
1.55 + void AddUInt16(uint16_t operand);
1.56 + void AddUInt64(uint64_t operand);
1.57 + void AddBignum(const Bignum& other);
1.58 + // Precondition: this >= other.
1.59 + void SubtractBignum(const Bignum& other);
1.60 +
1.61 + void Square();
1.62 + void ShiftLeft(int shift_amount);
1.63 + void MultiplyByUInt32(uint32_t factor);
1.64 + void MultiplyByUInt64(uint64_t factor);
1.65 + void MultiplyByPowerOfTen(int exponent);
1.66 + void Times10() { return MultiplyByUInt32(10); }
1.67 + // Pseudocode:
1.68 + // int result = this / other;
1.69 + // this = this % other;
1.70 + // In the worst case this function is in O(this/other).
1.71 + uint16_t DivideModuloIntBignum(const Bignum& other);
1.72 +
1.73 + bool ToHexString(char* buffer, int buffer_size) const;
1.74 +
1.75 + // Returns
1.76 + // -1 if a < b,
1.77 + // 0 if a == b, and
1.78 + // +1 if a > b.
1.79 + static int Compare(const Bignum& a, const Bignum& b);
1.80 + static bool Equal(const Bignum& a, const Bignum& b) {
1.81 + return Compare(a, b) == 0;
1.82 + }
1.83 + static bool LessEqual(const Bignum& a, const Bignum& b) {
1.84 + return Compare(a, b) <= 0;
1.85 + }
1.86 + static bool Less(const Bignum& a, const Bignum& b) {
1.87 + return Compare(a, b) < 0;
1.88 + }
1.89 + // Returns Compare(a + b, c);
1.90 + static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);
1.91 + // Returns a + b == c
1.92 + static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
1.93 + return PlusCompare(a, b, c) == 0;
1.94 + }
1.95 + // Returns a + b <= c
1.96 + static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
1.97 + return PlusCompare(a, b, c) <= 0;
1.98 + }
1.99 + // Returns a + b < c
1.100 + static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {
1.101 + return PlusCompare(a, b, c) < 0;
1.102 + }
1.103 + private:
1.104 + typedef uint32_t Chunk;
1.105 + typedef uint64_t DoubleChunk;
1.106 +
1.107 + static const int kChunkSize = sizeof(Chunk) * 8;
1.108 + static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;
1.109 + // With bigit size of 28 we loose some bits, but a double still fits easily
1.110 + // into two chunks, and more importantly we can use the Comba multiplication.
1.111 + static const int kBigitSize = 28;
1.112 + static const Chunk kBigitMask = (1 << kBigitSize) - 1;
1.113 + // Every instance allocates kBigitLength chunks on the stack. Bignums cannot
1.114 + // grow. There are no checks if the stack-allocated space is sufficient.
1.115 + static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;
1.116 +
1.117 + void EnsureCapacity(int size) {
1.118 + if (size > kBigitCapacity) {
1.119 + UNREACHABLE();
1.120 + }
1.121 + }
1.122 + void Align(const Bignum& other);
1.123 + void Clamp();
1.124 + bool IsClamped() const;
1.125 + void Zero();
1.126 + // Requires this to have enough capacity (no tests done).
1.127 + // Updates used_digits_ if necessary.
1.128 + // shift_amount must be < kBigitSize.
1.129 + void BigitsShiftLeft(int shift_amount);
1.130 + // BigitLength includes the "hidden" digits encoded in the exponent.
1.131 + int BigitLength() const { return used_digits_ + exponent_; }
1.132 + Chunk BigitAt(int index) const;
1.133 + void SubtractTimes(const Bignum& other, int factor);
1.134 +
1.135 + Chunk bigits_buffer_[kBigitCapacity];
1.136 + // A vector backed by bigits_buffer_. This way accesses to the array are
1.137 + // checked for out-of-bounds errors.
1.138 + Vector<Chunk> bigits_;
1.139 + int used_digits_;
1.140 + // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
1.141 + int exponent_;
1.142 +
1.143 + DISALLOW_COPY_AND_ASSIGN(Bignum);
1.144 +};
1.145 +
1.146 +} // namespace double_conversion
1.147 +
1.148 +#endif // DOUBLE_CONVERSION_BIGNUM_H_
