Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(184)

Side by Side Diff: third_party/WebKit/Source/wtf/dtoa/bignum.cc

Issue 2700123003: DO NOT COMMIT: Results of running old (current) clang-format on Blink (Closed)
Patch Set: Created 3 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 // Copyright 2010 the V8 project authors. All rights reserved. 1 // Copyright 2010 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without 2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are 3 // modification, are permitted provided that the following conditions are
4 // met: 4 // met:
5 // 5 //
6 // * Redistributions of source code must retain the above copyright 6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer. 7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above 8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following 9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided 10 // disclaimer in the documentation and/or other materials provided
(...skipping 15 matching lines...) Expand all
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 27
28 #include "bignum.h" 28 #include "bignum.h"
29 29
30 #include "utils.h" 30 #include "utils.h"
31 31
32 namespace WTF { 32 namespace WTF {
33 33
34 namespace double_conversion { 34 namespace double_conversion {
35 35
36 Bignum::Bignum() 36 Bignum::Bignum()
37 : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) { 37 : bigits_(bigits_buffer_, kBigitCapacity), used_digits_(0), exponent_(0) {
38 for (int i = 0; i < kBigitCapacity; ++i) { 38 for (int i = 0; i < kBigitCapacity; ++i) {
39 bigits_[i] = 0; 39 bigits_[i] = 0;
40 } 40 }
41 } 41 }
42 42
43 43 template <typename S>
44 template<typename S> 44 static int BitSize(S value) {
45 static int BitSize(S value) { 45 return 8 * sizeof(value);
46 return 8 * sizeof(value); 46 }
47 } 47
48 48 // Guaranteed to lie in one Bigit.
49 // Guaranteed to lie in one Bigit. 49 void Bignum::AssignUInt16(uint16_t value) {
50 void Bignum::AssignUInt16(uint16_t value) { 50 ASSERT(kBigitSize >= BitSize(value));
51 ASSERT(kBigitSize >= BitSize(value)); 51 Zero();
52 Zero(); 52 if (value == 0)
53 if (value == 0) return; 53 return;
54 54
55 EnsureCapacity(1); 55 EnsureCapacity(1);
56 bigits_[0] = value; 56 bigits_[0] = value;
57 used_digits_ = 1; 57 used_digits_ = 1;
58 } 58 }
59 59
60 60 void Bignum::AssignUInt64(uint64_t value) {
61 void Bignum::AssignUInt64(uint64_t value) { 61 const int kUInt64Size = 64;
62 const int kUInt64Size = 64; 62
63 63 Zero();
64 Zero(); 64 if (value == 0)
65 if (value == 0) return; 65 return;
66 66
67 int needed_bigits = kUInt64Size / kBigitSize + 1; 67 int needed_bigits = kUInt64Size / kBigitSize + 1;
68 EnsureCapacity(needed_bigits); 68 EnsureCapacity(needed_bigits);
69 for (int i = 0; i < needed_bigits; ++i) { 69 for (int i = 0; i < needed_bigits; ++i) {
70 bigits_[i] = (uint32_t)value & kBigitMask; 70 bigits_[i] = (uint32_t)value & kBigitMask;
71 value = value >> kBigitSize; 71 value = value >> kBigitSize;
72 } 72 }
73 used_digits_ = needed_bigits; 73 used_digits_ = needed_bigits;
74 Clamp(); 74 Clamp();
75 } 75 }
76 76
77 77 void Bignum::AssignBignum(const Bignum& other) {
78 void Bignum::AssignBignum(const Bignum& other) { 78 exponent_ = other.exponent_;
79 exponent_ = other.exponent_; 79 for (int i = 0; i < other.used_digits_; ++i) {
80 for (int i = 0; i < other.used_digits_; ++i) { 80 bigits_[i] = other.bigits_[i];
81 bigits_[i] = other.bigits_[i]; 81 }
82 } 82 // Clear the excess digits (if there were any).
83 // Clear the excess digits (if there were any). 83 for (int i = other.used_digits_; i < used_digits_; ++i) {
84 for (int i = other.used_digits_; i < used_digits_; ++i) { 84 bigits_[i] = 0;
85 bigits_[i] = 0; 85 }
86 } 86 used_digits_ = other.used_digits_;
87 used_digits_ = other.used_digits_; 87 }
88 } 88
89 89 static uint64_t ReadUInt64(Vector<const char> buffer,
90 90 int from,
91 static uint64_t ReadUInt64(Vector<const char> buffer, 91 int digits_to_read) {
92 int from, 92 uint64_t result = 0;
93 int digits_to_read) { 93 for (int i = from; i < from + digits_to_read; ++i) {
94 uint64_t result = 0; 94 int digit = buffer[i] - '0';
95 for (int i = from; i < from + digits_to_read; ++i) { 95 ASSERT(0 <= digit && digit <= 9);
96 int digit = buffer[i] - '0'; 96 result = result * 10 + digit;
97 ASSERT(0 <= digit && digit <= 9); 97 }
98 result = result * 10 + digit; 98 return result;
99 } 99 }
100 return result; 100
101 } 101 void Bignum::AssignDecimalString(Vector<const char> value) {
102 102 // 2^64 = 18446744073709551616 > 10^19
103 103 const int kMaxUint64DecimalDigits = 19;
104 void Bignum::AssignDecimalString(Vector<const char> value) { 104 Zero();
105 // 2^64 = 18446744073709551616 > 10^19 105 int length = value.length();
106 const int kMaxUint64DecimalDigits = 19; 106 int pos = 0;
107 Zero(); 107 // Let's just say that each digit needs 4 bits.
108 int length = value.length(); 108 while (length >= kMaxUint64DecimalDigits) {
109 int pos = 0; 109 uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits);
110 // Let's just say that each digit needs 4 bits. 110 pos += kMaxUint64DecimalDigits;
111 while (length >= kMaxUint64DecimalDigits) { 111 length -= kMaxUint64DecimalDigits;
112 uint64_t digits = ReadUInt64(value, pos, kMaxUint64DecimalDigits); 112 MultiplyByPowerOfTen(kMaxUint64DecimalDigits);
113 pos += kMaxUint64DecimalDigits; 113 AddUInt64(digits);
114 length -= kMaxUint64DecimalDigits; 114 }
115 MultiplyByPowerOfTen(kMaxUint64DecimalDigits); 115 uint64_t digits = ReadUInt64(value, pos, length);
116 AddUInt64(digits); 116 MultiplyByPowerOfTen(length);
117 } 117 AddUInt64(digits);
118 uint64_t digits = ReadUInt64(value, pos, length); 118 Clamp();
119 MultiplyByPowerOfTen(length); 119 }
120 AddUInt64(digits); 120
121 Clamp(); 121 static int HexCharValue(char c) {
122 } 122 if ('0' <= c && c <= '9')
123 123 return c - '0';
124 124 if ('a' <= c && c <= 'f')
125 static int HexCharValue(char c) { 125 return 10 + c - 'a';
126 if ('0' <= c && c <= '9') return c - '0'; 126 if ('A' <= c && c <= 'F')
127 if ('a' <= c && c <= 'f') return 10 + c - 'a'; 127 return 10 + c - 'A';
128 if ('A' <= c && c <= 'F') return 10 + c - 'A'; 128 UNREACHABLE();
129 UNREACHABLE(); 129 return 0; // To make compiler happy.
130 return 0; // To make compiler happy. 130 }
131 } 131
132 132 void Bignum::AssignHexString(Vector<const char> value) {
133 133 Zero();
134 void Bignum::AssignHexString(Vector<const char> value) { 134 int length = value.length();
135 Zero(); 135
136 int length = value.length(); 136 int needed_bigits = length * 4 / kBigitSize + 1;
137 137 EnsureCapacity(needed_bigits);
138 int needed_bigits = length * 4 / kBigitSize + 1; 138 int string_index = length - 1;
139 EnsureCapacity(needed_bigits); 139 for (int i = 0; i < needed_bigits - 1; ++i) {
140 int string_index = length - 1; 140 // These bigits are guaranteed to be "full".
141 for (int i = 0; i < needed_bigits - 1; ++i) { 141 Chunk current_bigit = 0;
142 // These bigits are guaranteed to be "full". 142 for (int j = 0; j < kBigitSize / 4; j++) {
143 Chunk current_bigit = 0; 143 current_bigit += HexCharValue(value[string_index--]) << (j * 4);
144 for (int j = 0; j < kBigitSize / 4; j++) { 144 }
145 current_bigit += HexCharValue(value[string_index--]) << (j * 4); 145 bigits_[i] = current_bigit;
146 } 146 }
147 bigits_[i] = current_bigit; 147 used_digits_ = needed_bigits - 1;
148 } 148
149 used_digits_ = needed_bigits - 1; 149 Chunk most_significant_bigit = 0; // Could be = 0;
150 150 for (int j = 0; j <= string_index; ++j) {
151 Chunk most_significant_bigit = 0; // Could be = 0; 151 most_significant_bigit <<= 4;
152 for (int j = 0; j <= string_index; ++j) { 152 most_significant_bigit += HexCharValue(value[j]);
153 most_significant_bigit <<= 4; 153 }
154 most_significant_bigit += HexCharValue(value[j]); 154 if (most_significant_bigit != 0) {
155 } 155 bigits_[used_digits_] = most_significant_bigit;
156 if (most_significant_bigit != 0) { 156 used_digits_++;
157 bigits_[used_digits_] = most_significant_bigit; 157 }
158 used_digits_++; 158 Clamp();
159 } 159 }
160 Clamp(); 160
161 } 161 void Bignum::AddUInt64(uint64_t operand) {
162 162 if (operand == 0)
163 163 return;
164 void Bignum::AddUInt64(uint64_t operand) { 164 Bignum other;
165 if (operand == 0) return; 165 other.AssignUInt64(operand);
166 Bignum other; 166 AddBignum(other);
167 other.AssignUInt64(operand); 167 }
168 AddBignum(other); 168
169 } 169 void Bignum::AddBignum(const Bignum& other) {
170 170 ASSERT(IsClamped());
171 171 ASSERT(other.IsClamped());
172 void Bignum::AddBignum(const Bignum& other) { 172
173 ASSERT(IsClamped()); 173 // If this has a greater exponent than other append zero-bigits to this.
174 ASSERT(other.IsClamped()); 174 // After this call exponent_ <= other.exponent_.
175 175 Align(other);
176 // If this has a greater exponent than other append zero-bigits to this. 176
177 // After this call exponent_ <= other.exponent_. 177 // There are two possibilities:
178 Align(other); 178 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent)
179 179 // bbbbb 00000000
180 // There are two possibilities: 180 // ----------------
181 // aaaaaaaaaaa 0000 (where the 0s represent a's exponent) 181 // ccccccccccc 0000
182 // bbbbb 00000000 182 // or
183 // ---------------- 183 // aaaaaaaaaa 0000
184 // ccccccccccc 0000 184 // bbbbbbbbb 0000000
185 // or 185 // -----------------
186 // aaaaaaaaaa 0000 186 // cccccccccccc 0000
187 // bbbbbbbbb 0000000 187 // In both cases we might need a carry bigit.
188 // ----------------- 188
189 // cccccccccccc 0000 189 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_);
190 // In both cases we might need a carry bigit. 190 Chunk carry = 0;
191 191 int bigit_pos = other.exponent_ - exponent_;
192 EnsureCapacity(1 + Max(BigitLength(), other.BigitLength()) - exponent_); 192 ASSERT(bigit_pos >= 0);
193 Chunk carry = 0; 193 for (int i = 0; i < other.used_digits_; ++i) {
194 int bigit_pos = other.exponent_ - exponent_; 194 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry;
195 ASSERT(bigit_pos >= 0); 195 bigits_[bigit_pos] = sum & kBigitMask;
196 for (int i = 0; i < other.used_digits_; ++i) { 196 carry = sum >> kBigitSize;
197 Chunk sum = bigits_[bigit_pos] + other.bigits_[i] + carry; 197 bigit_pos++;
198 bigits_[bigit_pos] = sum & kBigitMask; 198 }
199 carry = sum >> kBigitSize; 199
200 bigit_pos++; 200 while (carry != 0) {
201 } 201 Chunk sum = bigits_[bigit_pos] + carry;
202 202 bigits_[bigit_pos] = sum & kBigitMask;
203 while (carry != 0) { 203 carry = sum >> kBigitSize;
204 Chunk sum = bigits_[bigit_pos] + carry; 204 bigit_pos++;
205 bigits_[bigit_pos] = sum & kBigitMask; 205 }
206 carry = sum >> kBigitSize; 206 used_digits_ = Max(bigit_pos, used_digits_);
207 bigit_pos++; 207 ASSERT(IsClamped());
208 } 208 }
209 used_digits_ = Max(bigit_pos, used_digits_); 209
210 ASSERT(IsClamped()); 210 void Bignum::SubtractBignum(const Bignum& other) {
211 } 211 ASSERT(IsClamped());
212 212 ASSERT(other.IsClamped());
213 213 // We require this to be bigger than other.
214 void Bignum::SubtractBignum(const Bignum& other) { 214 ASSERT(LessEqual(other, *this));
215 ASSERT(IsClamped()); 215
216 ASSERT(other.IsClamped()); 216 Align(other);
217 // We require this to be bigger than other. 217
218 ASSERT(LessEqual(other, *this)); 218 int offset = other.exponent_ - exponent_;
219 219 Chunk borrow = 0;
220 Align(other); 220 int i;
221 221 for (i = 0; i < other.used_digits_; ++i) {
222 int offset = other.exponent_ - exponent_; 222 ASSERT((borrow == 0) || (borrow == 1));
223 Chunk borrow = 0; 223 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow;
224 int i; 224 bigits_[i + offset] = difference & kBigitMask;
225 for (i = 0; i < other.used_digits_; ++i) { 225 borrow = difference >> (kChunkSize - 1);
226 ASSERT((borrow == 0) || (borrow == 1)); 226 }
227 Chunk difference = bigits_[i + offset] - other.bigits_[i] - borrow; 227 while (borrow != 0) {
228 bigits_[i + offset] = difference & kBigitMask; 228 Chunk difference = bigits_[i + offset] - borrow;
229 borrow = difference >> (kChunkSize - 1); 229 bigits_[i + offset] = difference & kBigitMask;
230 } 230 borrow = difference >> (kChunkSize - 1);
231 while (borrow != 0) { 231 ++i;
232 Chunk difference = bigits_[i + offset] - borrow; 232 }
233 bigits_[i + offset] = difference & kBigitMask; 233 Clamp();
234 borrow = difference >> (kChunkSize - 1); 234 }
235 ++i; 235
236 } 236 void Bignum::ShiftLeft(int shift_amount) {
237 Clamp(); 237 if (used_digits_ == 0)
238 } 238 return;
239 239 exponent_ += shift_amount / kBigitSize;
240 240 int local_shift = shift_amount % kBigitSize;
241 void Bignum::ShiftLeft(int shift_amount) { 241 EnsureCapacity(used_digits_ + 1);
242 if (used_digits_ == 0) return; 242 BigitsShiftLeft(local_shift);
243 exponent_ += shift_amount / kBigitSize; 243 }
244 int local_shift = shift_amount % kBigitSize; 244
245 EnsureCapacity(used_digits_ + 1); 245 void Bignum::MultiplyByUInt32(uint32_t factor) {
246 BigitsShiftLeft(local_shift); 246 if (factor == 1)
247 } 247 return;
248 248 if (factor == 0) {
249 249 Zero();
250 void Bignum::MultiplyByUInt32(uint32_t factor) { 250 return;
251 if (factor == 1) return; 251 }
252 if (factor == 0) { 252 if (used_digits_ == 0)
253 Zero(); 253 return;
254 return; 254
255 } 255 // The product of a bigit with the factor is of size kBigitSize + 32.
256 if (used_digits_ == 0) return; 256 // Assert that this number + 1 (for the carry) fits into double chunk.
257 257 ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1);
258 // The product of a bigit with the factor is of size kBigitSize + 32. 258 DoubleChunk carry = 0;
259 // Assert that this number + 1 (for the carry) fits into double chunk. 259 for (int i = 0; i < used_digits_; ++i) {
260 ASSERT(kDoubleChunkSize >= kBigitSize + 32 + 1); 260 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry;
261 DoubleChunk carry = 0; 261 bigits_[i] = static_cast<Chunk>(product & kBigitMask);
262 for (int i = 0; i < used_digits_; ++i) { 262 carry = (product >> kBigitSize);
263 DoubleChunk product = static_cast<DoubleChunk>(factor) * bigits_[i] + carry; 263 }
264 bigits_[i] = static_cast<Chunk>(product & kBigitMask); 264 while (carry != 0) {
265 carry = (product >> kBigitSize); 265 EnsureCapacity(used_digits_ + 1);
266 } 266 bigits_[used_digits_] = (uint32_t)carry & kBigitMask;
267 while (carry != 0) { 267 used_digits_++;
268 EnsureCapacity(used_digits_ + 1); 268 carry >>= kBigitSize;
269 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; 269 }
270 used_digits_++; 270 }
271 carry >>= kBigitSize; 271
272 } 272 void Bignum::MultiplyByUInt64(uint64_t factor) {
273 } 273 if (factor == 1)
274 274 return;
275 275 if (factor == 0) {
276 void Bignum::MultiplyByUInt64(uint64_t factor) { 276 Zero();
277 if (factor == 1) return; 277 return;
278 if (factor == 0) { 278 }
279 Zero(); 279 ASSERT(kBigitSize < 32);
280 return; 280 uint64_t carry = 0;
281 } 281 uint64_t low = factor & 0xFFFFFFFF;
282 ASSERT(kBigitSize < 32); 282 uint64_t high = factor >> 32;
283 uint64_t carry = 0; 283 for (int i = 0; i < used_digits_; ++i) {
284 uint64_t low = factor & 0xFFFFFFFF; 284 uint64_t product_low = low * bigits_[i];
285 uint64_t high = factor >> 32; 285 uint64_t product_high = high * bigits_[i];
286 for (int i = 0; i < used_digits_; ++i) { 286 uint64_t tmp = (carry & kBigitMask) + product_low;
287 uint64_t product_low = low * bigits_[i]; 287 bigits_[i] = (uint32_t)tmp & kBigitMask;
288 uint64_t product_high = high * bigits_[i]; 288 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
289 uint64_t tmp = (carry & kBigitMask) + product_low;
290 bigits_[i] = (uint32_t)tmp & kBigitMask;
291 carry = (carry >> kBigitSize) + (tmp >> kBigitSize) +
292 (product_high << (32 - kBigitSize)); 289 (product_high << (32 - kBigitSize));
293 } 290 }
294 while (carry != 0) { 291 while (carry != 0) {
295 EnsureCapacity(used_digits_ + 1); 292 EnsureCapacity(used_digits_ + 1);
296 bigits_[used_digits_] = (uint32_t)carry & kBigitMask; 293 bigits_[used_digits_] = (uint32_t)carry & kBigitMask;
297 used_digits_++; 294 used_digits_++;
298 carry >>= kBigitSize; 295 carry >>= kBigitSize;
299 } 296 }
300 } 297 }
301 298
302 299 void Bignum::MultiplyByPowerOfTen(int exponent) {
303 void Bignum::MultiplyByPowerOfTen(int exponent) { 300 const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d);
304 const uint64_t kFive27 = UINT64_2PART_C(0x6765c793, fa10079d); 301 const uint16_t kFive1 = 5;
305 const uint16_t kFive1 = 5; 302 const uint16_t kFive2 = kFive1 * 5;
306 const uint16_t kFive2 = kFive1 * 5; 303 const uint16_t kFive3 = kFive2 * 5;
307 const uint16_t kFive3 = kFive2 * 5; 304 const uint16_t kFive4 = kFive3 * 5;
308 const uint16_t kFive4 = kFive3 * 5; 305 const uint16_t kFive5 = kFive4 * 5;
309 const uint16_t kFive5 = kFive4 * 5; 306 const uint16_t kFive6 = kFive5 * 5;
310 const uint16_t kFive6 = kFive5 * 5; 307 const uint32_t kFive7 = kFive6 * 5;
311 const uint32_t kFive7 = kFive6 * 5; 308 const uint32_t kFive8 = kFive7 * 5;
312 const uint32_t kFive8 = kFive7 * 5; 309 const uint32_t kFive9 = kFive8 * 5;
313 const uint32_t kFive9 = kFive8 * 5; 310 const uint32_t kFive10 = kFive9 * 5;
314 const uint32_t kFive10 = kFive9 * 5; 311 const uint32_t kFive11 = kFive10 * 5;
315 const uint32_t kFive11 = kFive10 * 5; 312 const uint32_t kFive12 = kFive11 * 5;
316 const uint32_t kFive12 = kFive11 * 5; 313 const uint32_t kFive13 = kFive12 * 5;
317 const uint32_t kFive13 = kFive12 * 5; 314 const uint32_t kFive1_to_12[] = {kFive1, kFive2, kFive3, kFive4,
318 const uint32_t kFive1_to_12[] = 315 kFive5, kFive6, kFive7, kFive8,
319 { kFive1, kFive2, kFive3, kFive4, kFive5, kFive6, 316 kFive9, kFive10, kFive11, kFive12};
320 kFive7, kFive8, kFive9, kFive10, kFive11, kFive12 }; 317
321 318 ASSERT(exponent >= 0);
322 ASSERT(exponent >= 0); 319 if (exponent == 0)
323 if (exponent == 0) return; 320 return;
324 if (used_digits_ == 0) return; 321 if (used_digits_ == 0)
325 322 return;
326 // We shift by exponent at the end just before returning. 323
327 int remaining_exponent = exponent; 324 // We shift by exponent at the end just before returning.
328 while (remaining_exponent >= 27) { 325 int remaining_exponent = exponent;
329 MultiplyByUInt64(kFive27); 326 while (remaining_exponent >= 27) {
330 remaining_exponent -= 27; 327 MultiplyByUInt64(kFive27);
331 } 328 remaining_exponent -= 27;
332 while (remaining_exponent >= 13) { 329 }
333 MultiplyByUInt32(kFive13); 330 while (remaining_exponent >= 13) {
334 remaining_exponent -= 13; 331 MultiplyByUInt32(kFive13);
335 } 332 remaining_exponent -= 13;
336 if (remaining_exponent > 0) { 333 }
337 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]); 334 if (remaining_exponent > 0) {
338 } 335 MultiplyByUInt32(kFive1_to_12[remaining_exponent - 1]);
339 ShiftLeft(exponent); 336 }
340 } 337 ShiftLeft(exponent);
341 338 }
342 339
343 void Bignum::Square() { 340 void Bignum::Square() {
344 ASSERT(IsClamped()); 341 ASSERT(IsClamped());
345 int product_length = 2 * used_digits_; 342 int product_length = 2 * used_digits_;
346 EnsureCapacity(product_length); 343 EnsureCapacity(product_length);
347 344
348 // Comba multiplication: compute each column separately. 345 // Comba multiplication: compute each column separately.
349 // Example: r = a2a1a0 * b2b1b0. 346 // Example: r = a2a1a0 * b2b1b0.
350 // r = 1 * a0b0 + 347 // r = 1 * a0b0 +
351 // 10 * (a1b0 + a0b1) + 348 // 10 * (a1b0 + a0b1) +
352 // 100 * (a2b0 + a1b1 + a0b2) + 349 // 100 * (a2b0 + a1b1 + a0b2) +
353 // 1000 * (a2b1 + a1b2) + 350 // 1000 * (a2b1 + a1b2) +
354 // 10000 * a2b2 351 // 10000 * a2b2
355 // 352 //
356 // In the worst case we have to accumulate nb-digits products of digit*d igit. 353 // In the worst case we have to accumulate nb-digits products of digit*digit.
357 // 354 //
358 // Assert that the additional number of bits in a DoubleChunk are enough to 355 // Assert that the additional number of bits in a DoubleChunk are enough to
359 // sum up used_digits of Bigit*Bigit. 356 // sum up used_digits of Bigit*Bigit.
360 if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) { 357 if ((1 << (2 * (kChunkSize - kBigitSize))) <= used_digits_) {
361 UNIMPLEMENTED(); 358 UNIMPLEMENTED();
362 } 359 }
363 DoubleChunk accumulator = 0; 360 DoubleChunk accumulator = 0;
364 // First shift the digits so we don't overwrite them. 361 // First shift the digits so we don't overwrite them.
365 int copy_offset = used_digits_; 362 int copy_offset = used_digits_;
366 for (int i = 0; i < used_digits_; ++i) { 363 for (int i = 0; i < used_digits_; ++i) {
367 bigits_[copy_offset + i] = bigits_[i]; 364 bigits_[copy_offset + i] = bigits_[i];
368 } 365 }
369 // We have two loops to avoid some 'if's in the loop. 366 // We have two loops to avoid some 'if's in the loop.
370 for (int i = 0; i < used_digits_; ++i) { 367 for (int i = 0; i < used_digits_; ++i) {
371 // Process temporary digit i with power i. 368 // Process temporary digit i with power i.
372 // The sum of the two indices must be equal to i. 369 // The sum of the two indices must be equal to i.
373 int bigit_index1 = i; 370 int bigit_index1 = i;
374 int bigit_index2 = 0; 371 int bigit_index2 = 0;
375 // Sum all of the sub-products. 372 // Sum all of the sub-products.
376 while (bigit_index1 >= 0) { 373 while (bigit_index1 >= 0) {
377 Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 374 Chunk chunk1 = bigits_[copy_offset + bigit_index1];
378 Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 375 Chunk chunk2 = bigits_[copy_offset + bigit_index2];
379 accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 376 accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
380 bigit_index1--; 377 bigit_index1--;
381 bigit_index2++; 378 bigit_index2++;
382 } 379 }
383 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 380 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
384 accumulator >>= kBigitSize; 381 accumulator >>= kBigitSize;
385 } 382 }
386 for (int i = used_digits_; i < product_length; ++i) { 383 for (int i = used_digits_; i < product_length; ++i) {
387 int bigit_index1 = used_digits_ - 1; 384 int bigit_index1 = used_digits_ - 1;
388 int bigit_index2 = i - bigit_index1; 385 int bigit_index2 = i - bigit_index1;
389 // Invariant: sum of both indices is again equal to i. 386 // Invariant: sum of both indices is again equal to i.
390 // Inner loop runs 0 times on last iteration, emptying accumulator. 387 // Inner loop runs 0 times on last iteration, emptying accumulator.
391 while (bigit_index2 < used_digits_) { 388 while (bigit_index2 < used_digits_) {
392 Chunk chunk1 = bigits_[copy_offset + bigit_index1]; 389 Chunk chunk1 = bigits_[copy_offset + bigit_index1];
393 Chunk chunk2 = bigits_[copy_offset + bigit_index2]; 390 Chunk chunk2 = bigits_[copy_offset + bigit_index2];
394 accumulator += static_cast<DoubleChunk>(chunk1) * chunk2; 391 accumulator += static_cast<DoubleChunk>(chunk1) * chunk2;
395 bigit_index1--; 392 bigit_index1--;
396 bigit_index2++; 393 bigit_index2++;
397 } 394 }
398 // The overwritten bigits_[i] will never be read in further loop ite rations, 395 // The overwritten bigits_[i] will never be read in further loop iterations,
399 // because bigit_index1 and bigit_index2 are always greater 396 // because bigit_index1 and bigit_index2 are always greater
400 // than i - used_digits_. 397 // than i - used_digits_.
401 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask; 398 bigits_[i] = static_cast<Chunk>(accumulator) & kBigitMask;
402 accumulator >>= kBigitSize; 399 accumulator >>= kBigitSize;
403 } 400 }
404 // Since the result was guaranteed to lie inside the number the 401 // Since the result was guaranteed to lie inside the number the
405 // accumulator must be 0 now. 402 // accumulator must be 0 now.
406 ASSERT(accumulator == 0); 403 ASSERT(accumulator == 0);
407 404
408 // Don't forget to update the used_digits and the exponent. 405 // Don't forget to update the used_digits and the exponent.
409 used_digits_ = product_length; 406 used_digits_ = product_length;
410 exponent_ *= 2; 407 exponent_ *= 2;
411 Clamp(); 408 Clamp();
412 } 409 }
413 410
414 411 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) {
415 void Bignum::AssignPowerUInt16(uint16_t base, int power_exponent) { 412 ASSERT(base != 0);
416 ASSERT(base != 0); 413 ASSERT(power_exponent >= 0);
417 ASSERT(power_exponent >= 0); 414 if (power_exponent == 0) {
418 if (power_exponent == 0) { 415 AssignUInt16(1);
419 AssignUInt16(1); 416 return;
420 return; 417 }
421 } 418 Zero();
422 Zero(); 419 int shifts = 0;
423 int shifts = 0; 420 // We expect base to be in range 2-32, and most often to be 10.
424 // We expect base to be in range 2-32, and most often to be 10. 421 // It does not make much sense to implement different algorithms for counting
425 // It does not make much sense to implement different algorithms for cou nting 422 // the bits.
426 // the bits. 423 while ((base & 1) == 0) {
427 while ((base & 1) == 0) { 424 base >>= 1;
428 base >>= 1; 425 shifts++;
429 shifts++; 426 }
430 } 427 int bit_size = 0;
431 int bit_size = 0; 428 int tmp_base = base;
432 int tmp_base = base; 429 while (tmp_base != 0) {
433 while (tmp_base != 0) { 430 tmp_base >>= 1;
434 tmp_base >>= 1; 431 bit_size++;
435 bit_size++; 432 }
436 } 433 int final_size = bit_size * power_exponent;
437 int final_size = bit_size * power_exponent; 434 // 1 extra bigit for the shifting, and one for rounded final_size.
438 // 1 extra bigit for the shifting, and one for rounded final_size. 435 EnsureCapacity(final_size / kBigitSize + 2);
439 EnsureCapacity(final_size / kBigitSize + 2); 436
440 437 // Left to Right exponentiation.
441 // Left to Right exponentiation. 438 int mask = 1;
442 int mask = 1; 439 while (power_exponent >= mask)
443 while (power_exponent >= mask) mask <<= 1; 440 mask <<= 1;
444 441
445 // The mask is now pointing to the bit above the most significant 1-bit of 442 // The mask is now pointing to the bit above the most significant 1-bit of
446 // power_exponent. 443 // power_exponent.
447 // Get rid of first 1-bit; 444 // Get rid of first 1-bit;
448 mask >>= 2; 445 mask >>= 2;
449 uint64_t this_value = base; 446 uint64_t this_value = base;
450 447
451 bool delayed_multipliciation = false; 448 bool delayed_multipliciation = false;
452 const uint64_t max_32bits = 0xFFFFFFFF; 449 const uint64_t max_32bits = 0xFFFFFFFF;
453 while (mask != 0 && this_value <= max_32bits) { 450 while (mask != 0 && this_value <= max_32bits) {
454 this_value = this_value * this_value; 451 this_value = this_value * this_value;
455 // Verify that there is enough space in this_value to perform the 452 // Verify that there is enough space in this_value to perform the
456 // multiplication. The first bit_size bits must be 0. 453 // multiplication. The first bit_size bits must be 0.
457 if ((power_exponent & mask) != 0) { 454 if ((power_exponent & mask) != 0) {
458 uint64_t base_bits_mask = 455 uint64_t base_bits_mask =
459 ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1); 456 ~((static_cast<uint64_t>(1) << (64 - bit_size)) - 1);
460 bool high_bits_zero = (this_value & base_bits_mask) == 0; 457 bool high_bits_zero = (this_value & base_bits_mask) == 0;
461 if (high_bits_zero) { 458 if (high_bits_zero) {
462 this_value *= base; 459 this_value *= base;
463 } else { 460 } else {
464 delayed_multipliciation = true; 461 delayed_multipliciation = true;
465 } 462 }
466 } 463 }
467 mask >>= 1; 464 mask >>= 1;
468 } 465 }
469 AssignUInt64(this_value); 466 AssignUInt64(this_value);
470 if (delayed_multipliciation) { 467 if (delayed_multipliciation) {
471 MultiplyByUInt32(base); 468 MultiplyByUInt32(base);
472 } 469 }
473 470
474 // Now do the same thing as a bignum. 471 // Now do the same thing as a bignum.
475 while (mask != 0) { 472 while (mask != 0) {
476 Square(); 473 Square();
477 if ((power_exponent & mask) != 0) { 474 if ((power_exponent & mask) != 0) {
478 MultiplyByUInt32(base); 475 MultiplyByUInt32(base);
479 } 476 }
480 mask >>= 1; 477 mask >>= 1;
481 } 478 }
482 479
483 // And finally add the saved shifts. 480 // And finally add the saved shifts.
484 ShiftLeft(shifts * power_exponent); 481 ShiftLeft(shifts * power_exponent);
485 } 482 }
486 483
487 484 // Precondition: this/other < 16bit.
488 // Precondition: this/other < 16bit. 485 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) {
489 uint16_t Bignum::DivideModuloIntBignum(const Bignum& other) { 486 ASSERT(IsClamped());
490 ASSERT(IsClamped()); 487 ASSERT(other.IsClamped());
491 ASSERT(other.IsClamped()); 488 ASSERT(other.used_digits_ > 0);
492 ASSERT(other.used_digits_ > 0); 489
493 490 // Easy case: if we have less digits than the divisor than the result is 0.
494 // Easy case: if we have less digits than the divisor than the result is 0. 491 // Note: this handles the case where this == 0, too.
495 // Note: this handles the case where this == 0, too. 492 if (BigitLength() < other.BigitLength()) {
496 if (BigitLength() < other.BigitLength()) { 493 return 0;
497 return 0; 494 }
498 } 495
499 496 Align(other);
500 Align(other); 497
501 498 uint16_t result = 0;
502 uint16_t result = 0; 499
503 500 // Start by removing multiples of 'other' until both numbers have the same
504 // Start by removing multiples of 'other' until both numbers have the sa me 501 // number of digits.
505 // number of digits. 502 while (BigitLength() > other.BigitLength()) {
506 while (BigitLength() > other.BigitLength()) { 503 // This naive approach is extremely inefficient if the this divided other
507 // This naive approach is extremely inefficient if the this divided other 504 // might be big. This function is implemented for doubleToString where
508 // might be big. This function is implemented for doubleToString whe re 505 // the result should be small (less than 10).
509 // the result should be small (less than 10). 506 ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16));
510 ASSERT(other.bigits_[other.used_digits_ - 1] >= ((1 << kBigitSize) / 16)); 507 // Remove the multiples of the first digit.
511 // Remove the multiples of the first digit. 508 // Example this = 23 and other equals 9. -> Remove 2 multiples.
512 // Example this = 23 and other equals 9. -> Remove 2 multiples. 509 result += static_cast<uint16_t>(bigits_[used_digits_ - 1]);
513 result += static_cast<uint16_t>(bigits_[used_digits_ - 1]); 510 SubtractTimes(other, bigits_[used_digits_ - 1]);
514 SubtractTimes(other, bigits_[used_digits_ - 1]); 511 }
515 } 512
516 513 ASSERT(BigitLength() == other.BigitLength());
517 ASSERT(BigitLength() == other.BigitLength()); 514
518 515 // Both bignums are at the same length now.
519 // Both bignums are at the same length now. 516 // Since other has more than 0 digits we know that the access to
520 // Since other has more than 0 digits we know that the access to 517 // bigits_[used_digits_ - 1] is safe.
521 // bigits_[used_digits_ - 1] is safe. 518 Chunk this_bigit = bigits_[used_digits_ - 1];
522 Chunk this_bigit = bigits_[used_digits_ - 1]; 519 Chunk other_bigit = other.bigits_[other.used_digits_ - 1];
523 Chunk other_bigit = other.bigits_[other.used_digits_ - 1]; 520
524 521 if (other.used_digits_ == 1) {
525 if (other.used_digits_ == 1) { 522 // Shortcut for easy (and common) case.
526 // Shortcut for easy (and common) case. 523 uint16_t quotient = static_cast<uint16_t>(this_bigit / other_bigit);
527 uint16_t quotient = static_cast<uint16_t>(this_bigit / other_bigit); 524 bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient;
528 bigits_[used_digits_ - 1] = this_bigit - other_bigit * quotient; 525 result += quotient;
529 result += quotient; 526 Clamp();
530 Clamp(); 527 return result;
531 return result; 528 }
532 } 529
533 530 uint16_t division_estimate =
534 uint16_t division_estimate = static_cast<uint16_t>(this_bigit / (other_b igit + 1)); 531 static_cast<uint16_t>(this_bigit / (other_bigit + 1));
535 result += division_estimate; 532 result += division_estimate;
536 SubtractTimes(other, division_estimate); 533 SubtractTimes(other, division_estimate);
537 534
538 if (other_bigit * (division_estimate + 1) > this_bigit) { 535 if (other_bigit * (division_estimate + 1) > this_bigit) {
539 // No need to even try to subtract. Even if other's remaining digits were 0 536 // No need to even try to subtract. Even if other's remaining digits were 0
540 // another subtraction would be too much. 537 // another subtraction would be too much.
541 return result; 538 return result;
542 } 539 }
543 540
544 while (LessEqual(other, *this)) { 541 while (LessEqual(other, *this)) {
545 SubtractBignum(other); 542 SubtractBignum(other);
546 result++; 543 result++;
547 } 544 }
548 return result; 545 return result;
549 } 546 }
550 547
551 548 template <typename S>
552 template<typename S> 549 static int SizeInHexChars(S number) {
553 static int SizeInHexChars(S number) { 550 ASSERT(number > 0);
554 ASSERT(number > 0); 551 int result = 0;
555 int result = 0; 552 while (number != 0) {
556 while (number != 0) { 553 number >>= 4;
557 number >>= 4; 554 result++;
558 result++; 555 }
559 } 556 return result;
560 return result; 557 }
561 } 558
562 559 static char HexCharOfValue(uint8_t value) {
563 560 ASSERT(0 <= value && value <= 16);
564 static char HexCharOfValue(uint8_t value) { 561 if (value < 10)
565 ASSERT(0 <= value && value <= 16); 562 return value + '0';
566 if (value < 10) return value + '0'; 563 return value - 10 + 'A';
567 return value - 10 + 'A'; 564 }
568 } 565
569 566 bool Bignum::ToHexString(char* buffer, int buffer_size) const {
570 567 ASSERT(IsClamped());
571 bool Bignum::ToHexString(char* buffer, int buffer_size) const { 568 // Each bigit must be printable as separate hex-character.
572 ASSERT(IsClamped()); 569 ASSERT(kBigitSize % 4 == 0);
573 // Each bigit must be printable as separate hex-character. 570 const int kHexCharsPerBigit = kBigitSize / 4;
574 ASSERT(kBigitSize % 4 == 0); 571
575 const int kHexCharsPerBigit = kBigitSize / 4; 572 if (used_digits_ == 0) {
576 573 if (buffer_size < 2)
577 if (used_digits_ == 0) { 574 return false;
578 if (buffer_size < 2) return false; 575 buffer[0] = '0';
579 buffer[0] = '0'; 576 buffer[1] = '\0';
580 buffer[1] = '\0'; 577 return true;
581 return true; 578 }
582 } 579 // We add 1 for the terminating '\0' character.
583 // We add 1 for the terminating '\0' character. 580 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit +
584 int needed_chars = (BigitLength() - 1) * kHexCharsPerBigit + 581 SizeInHexChars(bigits_[used_digits_ - 1]) + 1;
585 SizeInHexChars(bigits_[used_digits_ - 1]) + 1; 582 if (needed_chars > buffer_size)
586 if (needed_chars > buffer_size) return false; 583 return false;
587 int string_index = needed_chars - 1; 584 int string_index = needed_chars - 1;
588 buffer[string_index--] = '\0'; 585 buffer[string_index--] = '\0';
589 for (int i = 0; i < exponent_; ++i) { 586 for (int i = 0; i < exponent_; ++i) {
590 for (int j = 0; j < kHexCharsPerBigit; ++j) { 587 for (int j = 0; j < kHexCharsPerBigit; ++j) {
591 buffer[string_index--] = '0'; 588 buffer[string_index--] = '0';
592 } 589 }
593 } 590 }
594 for (int i = 0; i < used_digits_ - 1; ++i) { 591 for (int i = 0; i < used_digits_ - 1; ++i) {
595 Chunk current_bigit = bigits_[i]; 592 Chunk current_bigit = bigits_[i];
596 for (int j = 0; j < kHexCharsPerBigit; ++j) { 593 for (int j = 0; j < kHexCharsPerBigit; ++j) {
597 buffer[string_index--] = HexCharOfValue(current_bigit & 0xF); 594 buffer[string_index--] = HexCharOfValue(current_bigit & 0xF);
598 current_bigit >>= 4; 595 current_bigit >>= 4;
599 } 596 }
600 } 597 }
601 // And finally the last bigit. 598 // And finally the last bigit.
602 Chunk most_significant_bigit = bigits_[used_digits_ - 1]; 599 Chunk most_significant_bigit = bigits_[used_digits_ - 1];
603 while (most_significant_bigit != 0) { 600 while (most_significant_bigit != 0) {
604 buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF ); 601 buffer[string_index--] = HexCharOfValue(most_significant_bigit & 0xF);
605 most_significant_bigit >>= 4; 602 most_significant_bigit >>= 4;
606 } 603 }
607 return true; 604 return true;
608 } 605 }
609 606
610 607 Bignum::Chunk Bignum::BigitAt(int index) const {
611 Bignum::Chunk Bignum::BigitAt(int index) const { 608 if (index >= BigitLength())
612 if (index >= BigitLength()) return 0; 609 return 0;
613 if (index < exponent_) return 0; 610 if (index < exponent_)
614 return bigits_[index - exponent_]; 611 return 0;
615 } 612 return bigits_[index - exponent_];
616 613 }
617 614
618 int Bignum::Compare(const Bignum& a, const Bignum& b) { 615 int Bignum::Compare(const Bignum& a, const Bignum& b) {
619 ASSERT(a.IsClamped()); 616 ASSERT(a.IsClamped());
620 ASSERT(b.IsClamped()); 617 ASSERT(b.IsClamped());
621 int bigit_length_a = a.BigitLength(); 618 int bigit_length_a = a.BigitLength();
622 int bigit_length_b = b.BigitLength(); 619 int bigit_length_b = b.BigitLength();
623 if (bigit_length_a < bigit_length_b) return -1; 620 if (bigit_length_a < bigit_length_b)
624 if (bigit_length_a > bigit_length_b) return +1; 621 return -1;
625 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i ) { 622 if (bigit_length_a > bigit_length_b)
626 Chunk bigit_a = a.BigitAt(i); 623 return +1;
627 Chunk bigit_b = b.BigitAt(i); 624 for (int i = bigit_length_a - 1; i >= Min(a.exponent_, b.exponent_); --i) {
628 if (bigit_a < bigit_b) return -1; 625 Chunk bigit_a = a.BigitAt(i);
629 if (bigit_a > bigit_b) return +1; 626 Chunk bigit_b = b.BigitAt(i);
630 // Otherwise they are equal up to this digit. Try the next digit. 627 if (bigit_a < bigit_b)
631 } 628 return -1;
632 return 0; 629 if (bigit_a > bigit_b)
633 } 630 return +1;
634 631 // Otherwise they are equal up to this digit. Try the next digit.
635 632 }
636 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) { 633 return 0;
637 ASSERT(a.IsClamped()); 634 }
638 ASSERT(b.IsClamped()); 635
639 ASSERT(c.IsClamped()); 636 int Bignum::PlusCompare(const Bignum& a, const Bignum& b, const Bignum& c) {
640 if (a.BigitLength() < b.BigitLength()) { 637 ASSERT(a.IsClamped());
641 return PlusCompare(b, a, c); 638 ASSERT(b.IsClamped());
642 } 639 ASSERT(c.IsClamped());
643 if (a.BigitLength() + 1 < c.BigitLength()) return -1; 640 if (a.BigitLength() < b.BigitLength()) {
644 if (a.BigitLength() > c.BigitLength()) return +1; 641 return PlusCompare(b, a, c);
645 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' t han 642 }
646 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one 643 if (a.BigitLength() + 1 < c.BigitLength())
647 // of 'a'. 644 return -1;
648 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) { 645 if (a.BigitLength() > c.BigitLength())
649 return -1; 646 return +1;
650 } 647 // The exponent encodes 0-bigits. So if there are more 0-digits in 'a' than
651 648 // 'b' has digits, then the bigit-length of 'a'+'b' must be equal to the one
652 Chunk borrow = 0; 649 // of 'a'.
653 // Starting at min_exponent all digits are == 0. So no need to compare t hem. 650 if (a.exponent_ >= b.BigitLength() && a.BigitLength() < c.BigitLength()) {
654 int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_); 651 return -1;
655 for (int i = c.BigitLength() - 1; i >= min_exponent; --i) { 652 }
656 Chunk chunk_a = a.BigitAt(i); 653
657 Chunk chunk_b = b.BigitAt(i); 654 Chunk borrow = 0;
658 Chunk chunk_c = c.BigitAt(i); 655 // Starting at min_exponent all digits are == 0. So no need to compare them.
659 Chunk sum = chunk_a + chunk_b; 656 int min_exponent = Min(Min(a.exponent_, b.exponent_), c.exponent_);
660 if (sum > chunk_c + borrow) { 657 for (int i = c.BigitLength() - 1; i >= min_exponent; --i) {
661 return +1; 658 Chunk chunk_a = a.BigitAt(i);
662 } else { 659 Chunk chunk_b = b.BigitAt(i);
663 borrow = chunk_c + borrow - sum; 660 Chunk chunk_c = c.BigitAt(i);
664 if (borrow > 1) return -1; 661 Chunk sum = chunk_a + chunk_b;
665 borrow <<= kBigitSize; 662 if (sum > chunk_c + borrow) {
666 } 663 return +1;
667 } 664 } else {
668 if (borrow == 0) return 0; 665 borrow = chunk_c + borrow - sum;
666 if (borrow > 1)
669 return -1; 667 return -1;
670 } 668 borrow <<= kBigitSize;
671 669 }
672 670 }
673 void Bignum::Clamp() { 671 if (borrow == 0)
674 while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) { 672 return 0;
675 used_digits_--; 673 return -1;
676 } 674 }
677 if (used_digits_ == 0) { 675
678 // Zero. 676 void Bignum::Clamp() {
679 exponent_ = 0; 677 while (used_digits_ > 0 && bigits_[used_digits_ - 1] == 0) {
680 } 678 used_digits_--;
681 } 679 }
682 680 if (used_digits_ == 0) {
683 681 // Zero.
684 bool Bignum::IsClamped() const { 682 exponent_ = 0;
685 return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0; 683 }
686 } 684 }
687 685
688 686 bool Bignum::IsClamped() const {
689 void Bignum::Zero() { 687 return used_digits_ == 0 || bigits_[used_digits_ - 1] != 0;
690 for (int i = 0; i < used_digits_; ++i) { 688 }
691 bigits_[i] = 0; 689
692 } 690 void Bignum::Zero() {
693 used_digits_ = 0; 691 for (int i = 0; i < used_digits_; ++i) {
694 exponent_ = 0; 692 bigits_[i] = 0;
695 } 693 }
696 694 used_digits_ = 0;
697 695 exponent_ = 0;
698 void Bignum::Align(const Bignum& other) { 696 }
699 if (exponent_ > other.exponent_) { 697
700 // If "X" represents a "hidden" digit (by the exponent) then we are in the 698 void Bignum::Align(const Bignum& other) {
701 // following case (a == this, b == other): 699 if (exponent_ > other.exponent_) {
702 // a: aaaaaaXXXX or a: aaaaaXXX 700 // If "X" represents a "hidden" digit (by the exponent) then we are in the
703 // b: bbbbbbX b: bbbbbbbbXX 701 // following case (a == this, b == other):
704 // We replace some of the hidden digits (X) of a with 0 digits. 702 // a: aaaaaaXXXX or a: aaaaaXXX
705 // a: aaaaaa000X or a: aaaaa0XX 703 // b: bbbbbbX b: bbbbbbbbXX
706 int zero_digits = exponent_ - other.exponent_; 704 // We replace some of the hidden digits (X) of a with 0 digits.
707 EnsureCapacity(used_digits_ + zero_digits); 705 // a: aaaaaa000X or a: aaaaa0XX
708 for (int i = used_digits_ - 1; i >= 0; --i) { 706 int zero_digits = exponent_ - other.exponent_;
709 bigits_[i + zero_digits] = bigits_[i]; 707 EnsureCapacity(used_digits_ + zero_digits);
710 } 708 for (int i = used_digits_ - 1; i >= 0; --i) {
711 for (int i = 0; i < zero_digits; ++i) { 709 bigits_[i + zero_digits] = bigits_[i];
712 bigits_[i] = 0; 710 }
713 } 711 for (int i = 0; i < zero_digits; ++i) {
714 used_digits_ += zero_digits; 712 bigits_[i] = 0;
715 exponent_ -= zero_digits; 713 }
716 ASSERT(used_digits_ >= 0); 714 used_digits_ += zero_digits;
717 ASSERT(exponent_ >= 0); 715 exponent_ -= zero_digits;
718 } 716 ASSERT(used_digits_ >= 0);
719 } 717 ASSERT(exponent_ >= 0);
720 718 }
721 719 }
722 void Bignum::BigitsShiftLeft(int shift_amount) { 720
723 ASSERT(shift_amount < kBigitSize); 721 void Bignum::BigitsShiftLeft(int shift_amount) {
724 ASSERT(shift_amount >= 0); 722 ASSERT(shift_amount < kBigitSize);
725 Chunk carry = 0; 723 ASSERT(shift_amount >= 0);
726 for (int i = 0; i < used_digits_; ++i) { 724 Chunk carry = 0;
727 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount); 725 for (int i = 0; i < used_digits_; ++i) {
728 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask; 726 Chunk new_carry = bigits_[i] >> (kBigitSize - shift_amount);
729 carry = new_carry; 727 bigits_[i] = ((bigits_[i] << shift_amount) + carry) & kBigitMask;
730 } 728 carry = new_carry;
731 if (carry != 0) { 729 }
732 bigits_[used_digits_] = carry; 730 if (carry != 0) {
733 used_digits_++; 731 bigits_[used_digits_] = carry;
734 } 732 used_digits_++;
735 } 733 }
736 734 }
737 735
738 void Bignum::SubtractTimes(const Bignum& other, int factor) { 736 void Bignum::SubtractTimes(const Bignum& other, int factor) {
739 ASSERT(exponent_ <= other.exponent_); 737 ASSERT(exponent_ <= other.exponent_);
740 if (factor < 3) { 738 if (factor < 3) {
741 for (int i = 0; i < factor; ++i) { 739 for (int i = 0; i < factor; ++i) {
742 SubtractBignum(other); 740 SubtractBignum(other);
743 } 741 }
744 return; 742 return;
745 } 743 }
746 Chunk borrow = 0; 744 Chunk borrow = 0;
747 int exponent_diff = other.exponent_ - exponent_; 745 int exponent_diff = other.exponent_ - exponent_;
748 for (int i = 0; i < other.used_digits_; ++i) { 746 for (int i = 0; i < other.used_digits_; ++i) {
749 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigit s_[i]; 747 DoubleChunk product = static_cast<DoubleChunk>(factor) * other.bigits_[i];
750 DoubleChunk remove = borrow + product; 748 DoubleChunk remove = borrow + product;
751 Chunk difference = bigits_[i + exponent_diff] - ((uint32_t)remove & kBigitMask); 749 Chunk difference =
752 bigits_[i + exponent_diff] = difference & kBigitMask; 750 bigits_[i + exponent_diff] - ((uint32_t)remove & kBigitMask);
753 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) + 751 bigits_[i + exponent_diff] = difference & kBigitMask;
754 (remove >> kBigitSize)); 752 borrow = static_cast<Chunk>((difference >> (kChunkSize - 1)) +
755 } 753 (remove >> kBigitSize));
756 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) { 754 }
757 if (borrow == 0) return; 755 for (int i = other.used_digits_ + exponent_diff; i < used_digits_; ++i) {
758 Chunk difference = bigits_[i] - borrow; 756 if (borrow == 0)
759 bigits_[i] = difference & kBigitMask; 757 return;
760 borrow = difference >> (kChunkSize - 1); 758 Chunk difference = bigits_[i] - borrow;
761 } 759 bigits_[i] = difference & kBigitMask;
762 Clamp(); 760 borrow = difference >> (kChunkSize - 1);
763 } 761 }
764 762 Clamp();
763 }
765 764
766 } // namespace double_conversion 765 } // namespace double_conversion
767 766
768 } // namespace WTF 767 } // namespace WTF
OLDNEW
« no previous file with comments | « third_party/WebKit/Source/wtf/dtoa.cpp ('k') | third_party/WebKit/Source/wtf/dtoa/bignum-dtoa.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698