OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include <cmath> | 5 #include <cmath> |
6 | 6 |
7 #include "include/v8stdint.h" | 7 #include "include/v8stdint.h" |
8 #include "src/base/logging.h" | 8 #include "src/base/logging.h" |
9 #include "src/utils.h" | 9 #include "src/utils.h" |
10 | 10 |
11 #include "src/bignum-dtoa.h" | 11 #include "src/bignum-dtoa.h" |
12 | 12 |
13 #include "src/bignum.h" | 13 #include "src/bignum.h" |
14 #include "src/double.h" | 14 #include "src/double.h" |
15 | 15 |
16 namespace v8 { | 16 namespace v8 { |
17 namespace internal { | 17 namespace internal { |
18 | 18 |
19 static int NormalizedExponent(uint64_t significand, int exponent) { | 19 static int NormalizedExponent(uint64_t significand, int exponent) { |
20 ASSERT(significand != 0); | 20 DCHECK(significand != 0); |
21 while ((significand & Double::kHiddenBit) == 0) { | 21 while ((significand & Double::kHiddenBit) == 0) { |
22 significand = significand << 1; | 22 significand = significand << 1; |
23 exponent = exponent - 1; | 23 exponent = exponent - 1; |
24 } | 24 } |
25 return exponent; | 25 return exponent; |
26 } | 26 } |
27 | 27 |
28 | 28 |
29 // Forward declarations: | 29 // Forward declarations: |
30 // Returns an estimation of k such that 10^(k-1) <= v < 10^k. | 30 // Returns an estimation of k such that 10^(k-1) <= v < 10^k. |
(...skipping 30 matching lines...) Expand all Loading... |
61 // Once 'count' digits have been produced rounds the result depending on the | 61 // Once 'count' digits have been produced rounds the result depending on the |
62 // remainder (remainders of exactly .5 round upwards). Might update the | 62 // remainder (remainders of exactly .5 round upwards). Might update the |
63 // decimal_point when rounding up (for example for 0.9999). | 63 // decimal_point when rounding up (for example for 0.9999). |
64 static void GenerateCountedDigits(int count, int* decimal_point, | 64 static void GenerateCountedDigits(int count, int* decimal_point, |
65 Bignum* numerator, Bignum* denominator, | 65 Bignum* numerator, Bignum* denominator, |
66 Vector<char>(buffer), int* length); | 66 Vector<char>(buffer), int* length); |
67 | 67 |
68 | 68 |
69 void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits, | 69 void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits, |
70 Vector<char> buffer, int* length, int* decimal_point) { | 70 Vector<char> buffer, int* length, int* decimal_point) { |
71 ASSERT(v > 0); | 71 DCHECK(v > 0); |
72 ASSERT(!Double(v).IsSpecial()); | 72 DCHECK(!Double(v).IsSpecial()); |
73 uint64_t significand = Double(v).Significand(); | 73 uint64_t significand = Double(v).Significand(); |
74 bool is_even = (significand & 1) == 0; | 74 bool is_even = (significand & 1) == 0; |
75 int exponent = Double(v).Exponent(); | 75 int exponent = Double(v).Exponent(); |
76 int normalized_exponent = NormalizedExponent(significand, exponent); | 76 int normalized_exponent = NormalizedExponent(significand, exponent); |
77 // estimated_power might be too low by 1. | 77 // estimated_power might be too low by 1. |
78 int estimated_power = EstimatePower(normalized_exponent); | 78 int estimated_power = EstimatePower(normalized_exponent); |
79 | 79 |
80 // Shortcut for Fixed. | 80 // Shortcut for Fixed. |
81 // The requested digits correspond to the digits after the point. If the | 81 // The requested digits correspond to the digits after the point. If the |
82 // number is much too small, then there is no need in trying to get any | 82 // number is much too small, then there is no need in trying to get any |
83 // digits. | 83 // digits. |
84 if (mode == BIGNUM_DTOA_FIXED && -estimated_power - 1 > requested_digits) { | 84 if (mode == BIGNUM_DTOA_FIXED && -estimated_power - 1 > requested_digits) { |
85 buffer[0] = '\0'; | 85 buffer[0] = '\0'; |
86 *length = 0; | 86 *length = 0; |
87 // Set decimal-point to -requested_digits. This is what Gay does. | 87 // Set decimal-point to -requested_digits. This is what Gay does. |
88 // Note that it should not have any effect anyways since the string is | 88 // Note that it should not have any effect anyways since the string is |
89 // empty. | 89 // empty. |
90 *decimal_point = -requested_digits; | 90 *decimal_point = -requested_digits; |
91 return; | 91 return; |
92 } | 92 } |
93 | 93 |
94 Bignum numerator; | 94 Bignum numerator; |
95 Bignum denominator; | 95 Bignum denominator; |
96 Bignum delta_minus; | 96 Bignum delta_minus; |
97 Bignum delta_plus; | 97 Bignum delta_plus; |
98 // Make sure the bignum can grow large enough. The smallest double equals | 98 // Make sure the bignum can grow large enough. The smallest double equals |
99 // 4e-324. In this case the denominator needs fewer than 324*4 binary digits. | 99 // 4e-324. In this case the denominator needs fewer than 324*4 binary digits. |
100 // The maximum double is 1.7976931348623157e308 which needs fewer than | 100 // The maximum double is 1.7976931348623157e308 which needs fewer than |
101 // 308*4 binary digits. | 101 // 308*4 binary digits. |
102 ASSERT(Bignum::kMaxSignificantBits >= 324*4); | 102 DCHECK(Bignum::kMaxSignificantBits >= 324*4); |
103 bool need_boundary_deltas = (mode == BIGNUM_DTOA_SHORTEST); | 103 bool need_boundary_deltas = (mode == BIGNUM_DTOA_SHORTEST); |
104 InitialScaledStartValues(v, estimated_power, need_boundary_deltas, | 104 InitialScaledStartValues(v, estimated_power, need_boundary_deltas, |
105 &numerator, &denominator, | 105 &numerator, &denominator, |
106 &delta_minus, &delta_plus); | 106 &delta_minus, &delta_plus); |
107 // We now have v = (numerator / denominator) * 10^estimated_power. | 107 // We now have v = (numerator / denominator) * 10^estimated_power. |
108 FixupMultiply10(estimated_power, is_even, decimal_point, | 108 FixupMultiply10(estimated_power, is_even, decimal_point, |
109 &numerator, &denominator, | 109 &numerator, &denominator, |
110 &delta_minus, &delta_plus); | 110 &delta_minus, &delta_plus); |
111 // We now have v = (numerator / denominator) * 10^(decimal_point-1), and | 111 // We now have v = (numerator / denominator) * 10^(decimal_point-1), and |
112 // 1 <= (numerator + delta_plus) / denominator < 10 | 112 // 1 <= (numerator + delta_plus) / denominator < 10 |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
152 Vector<char> buffer, int* length) { | 152 Vector<char> buffer, int* length) { |
153 // Small optimization: if delta_minus and delta_plus are the same just reuse | 153 // Small optimization: if delta_minus and delta_plus are the same just reuse |
154 // one of the two bignums. | 154 // one of the two bignums. |
155 if (Bignum::Equal(*delta_minus, *delta_plus)) { | 155 if (Bignum::Equal(*delta_minus, *delta_plus)) { |
156 delta_plus = delta_minus; | 156 delta_plus = delta_minus; |
157 } | 157 } |
158 *length = 0; | 158 *length = 0; |
159 while (true) { | 159 while (true) { |
160 uint16_t digit; | 160 uint16_t digit; |
161 digit = numerator->DivideModuloIntBignum(*denominator); | 161 digit = numerator->DivideModuloIntBignum(*denominator); |
162 ASSERT(digit <= 9); // digit is a uint16_t and therefore always positive. | 162 DCHECK(digit <= 9); // digit is a uint16_t and therefore always positive. |
163 // digit = numerator / denominator (integer division). | 163 // digit = numerator / denominator (integer division). |
164 // numerator = numerator % denominator. | 164 // numerator = numerator % denominator. |
165 buffer[(*length)++] = digit + '0'; | 165 buffer[(*length)++] = digit + '0'; |
166 | 166 |
167 // Can we stop already? | 167 // Can we stop already? |
168 // If the remainder of the division is less than the distance to the lower | 168 // If the remainder of the division is less than the distance to the lower |
169 // boundary we can stop. In this case we simply round down (discarding the | 169 // boundary we can stop. In this case we simply round down (discarding the |
170 // remainder). | 170 // remainder). |
171 // Similarly we test if we can round up (using the upper boundary). | 171 // Similarly we test if we can round up (using the upper boundary). |
172 bool in_delta_room_minus; | 172 bool in_delta_room_minus; |
(...skipping 25 matching lines...) Expand all Loading... |
198 // If yes, then the next digit would be < 5 and we can round down. | 198 // If yes, then the next digit would be < 5 and we can round down. |
199 int compare = Bignum::PlusCompare(*numerator, *numerator, *denominator); | 199 int compare = Bignum::PlusCompare(*numerator, *numerator, *denominator); |
200 if (compare < 0) { | 200 if (compare < 0) { |
201 // Remaining digits are less than .5. -> Round down (== do nothing). | 201 // Remaining digits are less than .5. -> Round down (== do nothing). |
202 } else if (compare > 0) { | 202 } else if (compare > 0) { |
203 // Remaining digits are more than .5 of denominator. -> Round up. | 203 // Remaining digits are more than .5 of denominator. -> Round up. |
204 // Note that the last digit could not be a '9' as otherwise the whole | 204 // Note that the last digit could not be a '9' as otherwise the whole |
205 // loop would have stopped earlier. | 205 // loop would have stopped earlier. |
206 // We still have an assert here in case the preconditions were not | 206 // We still have an assert here in case the preconditions were not |
207 // satisfied. | 207 // satisfied. |
208 ASSERT(buffer[(*length) - 1] != '9'); | 208 DCHECK(buffer[(*length) - 1] != '9'); |
209 buffer[(*length) - 1]++; | 209 buffer[(*length) - 1]++; |
210 } else { | 210 } else { |
211 // Halfway case. | 211 // Halfway case. |
212 // TODO(floitsch): need a way to solve half-way cases. | 212 // TODO(floitsch): need a way to solve half-way cases. |
213 // For now let's round towards even (since this is what Gay seems to | 213 // For now let's round towards even (since this is what Gay seems to |
214 // do). | 214 // do). |
215 | 215 |
216 if ((buffer[(*length) - 1] - '0') % 2 == 0) { | 216 if ((buffer[(*length) - 1] - '0') % 2 == 0) { |
217 // Round down => Do nothing. | 217 // Round down => Do nothing. |
218 } else { | 218 } else { |
219 ASSERT(buffer[(*length) - 1] != '9'); | 219 DCHECK(buffer[(*length) - 1] != '9'); |
220 buffer[(*length) - 1]++; | 220 buffer[(*length) - 1]++; |
221 } | 221 } |
222 } | 222 } |
223 return; | 223 return; |
224 } else if (in_delta_room_minus) { | 224 } else if (in_delta_room_minus) { |
225 // Round down (== do nothing). | 225 // Round down (== do nothing). |
226 return; | 226 return; |
227 } else { // in_delta_room_plus | 227 } else { // in_delta_room_plus |
228 // Round up. | 228 // Round up. |
229 // Note again that the last digit could not be '9' since this would have | 229 // Note again that the last digit could not be '9' since this would have |
230 // stopped the loop earlier. | 230 // stopped the loop earlier. |
231 // We still have an ASSERT here, in case the preconditions were not | 231 // We still have an DCHECK here, in case the preconditions were not |
232 // satisfied. | 232 // satisfied. |
233 ASSERT(buffer[(*length) -1] != '9'); | 233 DCHECK(buffer[(*length) -1] != '9'); |
234 buffer[(*length) - 1]++; | 234 buffer[(*length) - 1]++; |
235 return; | 235 return; |
236 } | 236 } |
237 } | 237 } |
238 } | 238 } |
239 | 239 |
240 | 240 |
241 // Let v = numerator / denominator < 10. | 241 // Let v = numerator / denominator < 10. |
242 // Then we generate 'count' digits of d = x.xxxxx... (without the decimal point) | 242 // Then we generate 'count' digits of d = x.xxxxx... (without the decimal point) |
243 // from left to right. Once 'count' digits have been produced we decide wether | 243 // from left to right. Once 'count' digits have been produced we decide wether |
244 // to round up or down. Remainders of exactly .5 round upwards. Numbers such | 244 // to round up or down. Remainders of exactly .5 round upwards. Numbers such |
245 // as 9.999999 propagate a carry all the way, and change the | 245 // as 9.999999 propagate a carry all the way, and change the |
246 // exponent (decimal_point), when rounding upwards. | 246 // exponent (decimal_point), when rounding upwards. |
247 static void GenerateCountedDigits(int count, int* decimal_point, | 247 static void GenerateCountedDigits(int count, int* decimal_point, |
248 Bignum* numerator, Bignum* denominator, | 248 Bignum* numerator, Bignum* denominator, |
249 Vector<char>(buffer), int* length) { | 249 Vector<char>(buffer), int* length) { |
250 ASSERT(count >= 0); | 250 DCHECK(count >= 0); |
251 for (int i = 0; i < count - 1; ++i) { | 251 for (int i = 0; i < count - 1; ++i) { |
252 uint16_t digit; | 252 uint16_t digit; |
253 digit = numerator->DivideModuloIntBignum(*denominator); | 253 digit = numerator->DivideModuloIntBignum(*denominator); |
254 ASSERT(digit <= 9); // digit is a uint16_t and therefore always positive. | 254 DCHECK(digit <= 9); // digit is a uint16_t and therefore always positive. |
255 // digit = numerator / denominator (integer division). | 255 // digit = numerator / denominator (integer division). |
256 // numerator = numerator % denominator. | 256 // numerator = numerator % denominator. |
257 buffer[i] = digit + '0'; | 257 buffer[i] = digit + '0'; |
258 // Prepare for next iteration. | 258 // Prepare for next iteration. |
259 numerator->Times10(); | 259 numerator->Times10(); |
260 } | 260 } |
261 // Generate the last digit. | 261 // Generate the last digit. |
262 uint16_t digit; | 262 uint16_t digit; |
263 digit = numerator->DivideModuloIntBignum(*denominator); | 263 digit = numerator->DivideModuloIntBignum(*denominator); |
264 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { | 264 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
297 // Ex: 0.001 with requested_digits == 1. | 297 // Ex: 0.001 with requested_digits == 1. |
298 // Set decimal-point to -requested_digits. This is what Gay does. | 298 // Set decimal-point to -requested_digits. This is what Gay does. |
299 // Note that it should not have any effect anyways since the string is | 299 // Note that it should not have any effect anyways since the string is |
300 // empty. | 300 // empty. |
301 *decimal_point = -requested_digits; | 301 *decimal_point = -requested_digits; |
302 *length = 0; | 302 *length = 0; |
303 return; | 303 return; |
304 } else if (-(*decimal_point) == requested_digits) { | 304 } else if (-(*decimal_point) == requested_digits) { |
305 // We only need to verify if the number rounds down or up. | 305 // We only need to verify if the number rounds down or up. |
306 // Ex: 0.04 and 0.06 with requested_digits == 1. | 306 // Ex: 0.04 and 0.06 with requested_digits == 1. |
307 ASSERT(*decimal_point == -requested_digits); | 307 DCHECK(*decimal_point == -requested_digits); |
308 // Initially the fraction lies in range (1, 10]. Multiply the denominator | 308 // Initially the fraction lies in range (1, 10]. Multiply the denominator |
309 // by 10 so that we can compare more easily. | 309 // by 10 so that we can compare more easily. |
310 denominator->Times10(); | 310 denominator->Times10(); |
311 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { | 311 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { |
312 // If the fraction is >= 0.5 then we have to include the rounded | 312 // If the fraction is >= 0.5 then we have to include the rounded |
313 // digit. | 313 // digit. |
314 buffer[0] = '1'; | 314 buffer[0] = '1'; |
315 *length = 1; | 315 *length = 1; |
316 (*decimal_point)++; | 316 (*decimal_point)++; |
317 } else { | 317 } else { |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
376 return static_cast<int>(estimate); | 376 return static_cast<int>(estimate); |
377 } | 377 } |
378 | 378 |
379 | 379 |
380 // See comments for InitialScaledStartValues. | 380 // See comments for InitialScaledStartValues. |
381 static void InitialScaledStartValuesPositiveExponent( | 381 static void InitialScaledStartValuesPositiveExponent( |
382 double v, int estimated_power, bool need_boundary_deltas, | 382 double v, int estimated_power, bool need_boundary_deltas, |
383 Bignum* numerator, Bignum* denominator, | 383 Bignum* numerator, Bignum* denominator, |
384 Bignum* delta_minus, Bignum* delta_plus) { | 384 Bignum* delta_minus, Bignum* delta_plus) { |
385 // A positive exponent implies a positive power. | 385 // A positive exponent implies a positive power. |
386 ASSERT(estimated_power >= 0); | 386 DCHECK(estimated_power >= 0); |
387 // Since the estimated_power is positive we simply multiply the denominator | 387 // Since the estimated_power is positive we simply multiply the denominator |
388 // by 10^estimated_power. | 388 // by 10^estimated_power. |
389 | 389 |
390 // numerator = v. | 390 // numerator = v. |
391 numerator->AssignUInt64(Double(v).Significand()); | 391 numerator->AssignUInt64(Double(v).Significand()); |
392 numerator->ShiftLeft(Double(v).Exponent()); | 392 numerator->ShiftLeft(Double(v).Exponent()); |
393 // denominator = 10^estimated_power. | 393 // denominator = 10^estimated_power. |
394 denominator->AssignPowerUInt16(10, estimated_power); | 394 denominator->AssignPowerUInt16(10, estimated_power); |
395 | 395 |
396 if (need_boundary_deltas) { | 396 if (need_boundary_deltas) { |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
495 // delta_plus = delta_minus = 10^estimated_power | 495 // delta_plus = delta_minus = 10^estimated_power |
496 delta_plus->AssignBignum(*power_ten); | 496 delta_plus->AssignBignum(*power_ten); |
497 delta_minus->AssignBignum(*power_ten); | 497 delta_minus->AssignBignum(*power_ten); |
498 } | 498 } |
499 | 499 |
500 // numerator = significand * 2 * 10^-estimated_power | 500 // numerator = significand * 2 * 10^-estimated_power |
501 // since v = significand * 2^exponent this is equivalent to | 501 // since v = significand * 2^exponent this is equivalent to |
502 // numerator = v * 10^-estimated_power * 2 * 2^-exponent. | 502 // numerator = v * 10^-estimated_power * 2 * 2^-exponent. |
503 // Remember: numerator has been abused as power_ten. So no need to assign it | 503 // Remember: numerator has been abused as power_ten. So no need to assign it |
504 // to itself. | 504 // to itself. |
505 ASSERT(numerator == power_ten); | 505 DCHECK(numerator == power_ten); |
506 numerator->MultiplyByUInt64(significand); | 506 numerator->MultiplyByUInt64(significand); |
507 | 507 |
508 // denominator = 2 * 2^-exponent with exponent < 0. | 508 // denominator = 2 * 2^-exponent with exponent < 0. |
509 denominator->AssignUInt16(1); | 509 denominator->AssignUInt16(1); |
510 denominator->ShiftLeft(-exponent); | 510 denominator->ShiftLeft(-exponent); |
511 | 511 |
512 if (need_boundary_deltas) { | 512 if (need_boundary_deltas) { |
513 // Introduce a common denominator so that the deltas to the boundaries are | 513 // Introduce a common denominator so that the deltas to the boundaries are |
514 // integers. | 514 // integers. |
515 numerator->ShiftLeft(1); | 515 numerator->ShiftLeft(1); |
(...skipping 111 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
627 delta_minus->Times10(); | 627 delta_minus->Times10(); |
628 delta_plus->AssignBignum(*delta_minus); | 628 delta_plus->AssignBignum(*delta_minus); |
629 } else { | 629 } else { |
630 delta_minus->Times10(); | 630 delta_minus->Times10(); |
631 delta_plus->Times10(); | 631 delta_plus->Times10(); |
632 } | 632 } |
633 } | 633 } |
634 } | 634 } |
635 | 635 |
636 } } // namespace v8::internal | 636 } } // namespace v8::internal |
OLD | NEW |