1// Copyright 2010 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef DOUBLE_CONVERSION_BIGNUM_H_
29#define DOUBLE_CONVERSION_BIGNUM_H_
30
31#include "utils.h"
32
33namespace WTF {
34
35namespace double_conversion {
36
37    class Bignum {
38    public:
39        // 3584 = 128 * 28. We can represent 2^3584 > 10^1000 accurately.
40        // This bignum can encode much bigger numbers, since it contains an
41        // exponent.
42        static const int kMaxSignificantBits = 3584;
43
44        Bignum();
45        void AssignUInt16(uint16_t value);
46        void AssignUInt64(uint64_t value);
47        void AssignBignum(const Bignum& other);
48
49        void AssignDecimalString(Vector<const char> value);
50        void AssignHexString(Vector<const char> value);
51
52        void AssignPowerUInt16(uint16_t base, int exponent);
53
54        void AddUInt16(uint16_t operand);
55        void AddUInt64(uint64_t operand);
56        void AddBignum(const Bignum& other);
57        // Precondition: this >= other.
58        void SubtractBignum(const Bignum& other);
59
60        void Square();
61        void ShiftLeft(int shift_amount);
62        void MultiplyByUInt32(uint32_t factor);
63        void MultiplyByUInt64(uint64_t factor);
64        void MultiplyByPowerOfTen(int exponent);
65        void Times10() { return MultiplyByUInt32(10); }
66        // Pseudocode:
67        //  int result = this / other;
68        //  this = this % other;
69        // In the worst case this function is in O(this/other).
70        uint16_t DivideModuloIntBignum(const Bignum& other);
71
72        bool ToHexString(char* buffer, int buffer_size) const;
73
74        static int Compare(const Bignum& a, const Bignum& b);
75        static bool Equal(const Bignum& a, const Bignum& b) {
76            return Compare(a, b) == 0;
77        }
78        static bool LessEqual(const Bignum& a, const Bignum& b) {
79            return Compare(a, b) <= 0;
80        }
81        static bool Less(const Bignum& a, const Bignum& b) {
82            return Compare(a, b) < 0;
83        }
84        // Returns Compare(a + b, c);
85        static int PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c);
86        // Returns a + b == c
87        static bool PlusEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
88            return PlusCompare(a, b, c) == 0;
89        }
90        // Returns a + b <= c
91        static bool PlusLessEqual(const Bignum& a, const Bignum& b, const Bignum& c) {
92            return PlusCompare(a, b, c) <= 0;
93        }
94        // Returns a + b < c
95        static bool PlusLess(const Bignum& a, const Bignum& b, const Bignum& c) {
96            return PlusCompare(a, b, c) < 0;
97        }
98    private:
99        typedef uint32_t Chunk;
100        typedef uint64_t DoubleChunk;
101
102        static const int kChunkSize = sizeof(Chunk) * 8;
103        static const int kDoubleChunkSize = sizeof(DoubleChunk) * 8;
104        // With bigit size of 28 we loose some bits, but a double still fits easily
105        // into two chunks, and more importantly we can use the Comba multiplication.
106        static const int kBigitSize = 28;
107        static const Chunk kBigitMask = (1 << kBigitSize) - 1;
108        // Every instance allocates kBigitLength chunks on the stack. Bignums cannot
109        // grow. There are no checks if the stack-allocated space is sufficient.
110        static const int kBigitCapacity = kMaxSignificantBits / kBigitSize;
111
112        void EnsureCapacity(int size) {
113            if (size > kBigitCapacity) {
114                UNREACHABLE();
115            }
116        }
117        void Align(const Bignum& other);
118        void Clamp();
119        bool IsClamped() const;
120        void Zero();
121        // Requires this to have enough capacity (no tests done).
122        // Updates used_digits_ if necessary.
123        // shift_amount must be < kBigitSize.
124        void BigitsShiftLeft(int shift_amount);
125        // BigitLength includes the "hidden" digits encoded in the exponent.
126        int BigitLength() const { return used_digits_ + exponent_; }
127        Chunk BigitAt(int index) const;
128        void SubtractTimes(const Bignum& other, int factor);
129
130        Chunk bigits_buffer_[kBigitCapacity];
131        // A vector backed by bigits_buffer_. This way accesses to the array are
132        // checked for out-of-bounds errors.
133        Vector<Chunk> bigits_;
134        int used_digits_;
135        // The Bignum's value equals value(bigits_) * 2^(exponent_ * kBigitSize).
136        int exponent_;
137
138        DISALLOW_COPY_AND_ASSIGN(Bignum);
139    };
140
141}  // namespace double_conversion
142
143} // namespace WTF
144
145#endif  // DOUBLE_CONVERSION_BIGNUM_H_
146