OLD | NEW |
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 18 matching lines...) Expand all Loading... |
29 | 29 |
30 #include "bignum.h" | 30 #include "bignum.h" |
31 #include "double.h" | 31 #include "double.h" |
32 #include <math.h> | 32 #include <math.h> |
33 | 33 |
34 namespace WTF { | 34 namespace WTF { |
35 | 35 |
36 namespace double_conversion { | 36 namespace double_conversion { |
37 | 37 |
38 static int NormalizedExponent(uint64_t significand, int exponent) { | 38 static int NormalizedExponent(uint64_t significand, int exponent) { |
39 ASSERT(significand != 0); | 39 DCHECK_NE(significand, 0u); |
40 while ((significand & Double::kHiddenBit) == 0) { | 40 while ((significand & Double::kHiddenBit) == 0) { |
41 significand = significand << 1; | 41 significand = significand << 1; |
42 exponent = exponent - 1; | 42 exponent = exponent - 1; |
43 } | 43 } |
44 return exponent; | 44 return exponent; |
45 } | 45 } |
46 | 46 |
47 | 47 |
48 // Forward declarations: | 48 // Forward declarations: |
49 // Returns an estimation of k such that 10^(k-1) <= v < 10^k. | 49 // Returns an estimation of k such that 10^(k-1) <= v < 10^k. |
(...skipping 30 matching lines...) Expand all Loading... |
80 // Once 'count' digits have been produced rounds the result depending on the | 80 // Once 'count' digits have been produced rounds the result depending on the |
81 // remainder (remainders of exactly .5 round upwards). Might update the | 81 // remainder (remainders of exactly .5 round upwards). Might update the |
82 // decimal_point when rounding up (for example for 0.9999). | 82 // decimal_point when rounding up (for example for 0.9999). |
83 static void GenerateCountedDigits(int count, int* decimal_point, | 83 static void GenerateCountedDigits(int count, int* decimal_point, |
84 Bignum* numerator, Bignum* denominator, | 84 Bignum* numerator, Bignum* denominator, |
85 Vector<char>(buffer), int* length); | 85 Vector<char>(buffer), int* length); |
86 | 86 |
87 | 87 |
88 void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits, | 88 void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits, |
89 Vector<char> buffer, int* length, int* decimal_point) { | 89 Vector<char> buffer, int* length, int* decimal_point) { |
90 ASSERT(v > 0); | 90 DCHECK_GT(v, 0); |
91 DCHECK(!Double(v).IsSpecial()); | 91 DCHECK(!Double(v).IsSpecial()); |
92 uint64_t significand = Double(v).Significand(); | 92 uint64_t significand = Double(v).Significand(); |
93 bool is_even = (significand & 1) == 0; | 93 bool is_even = (significand & 1) == 0; |
94 int exponent = Double(v).Exponent(); | 94 int exponent = Double(v).Exponent(); |
95 int normalized_exponent = NormalizedExponent(significand, exponent); | 95 int normalized_exponent = NormalizedExponent(significand, exponent); |
96 // estimated_power might be too low by 1. | 96 // estimated_power might be too low by 1. |
97 int estimated_power = EstimatePower(normalized_exponent); | 97 int estimated_power = EstimatePower(normalized_exponent); |
98 | 98 |
99 // Shortcut for Fixed. | 99 // Shortcut for Fixed. |
100 // The requested digits correspond to the digits after the point. If the | 100 // The requested digits correspond to the digits after the point. If the |
(...skipping 10 matching lines...) Expand all Loading... |
111 } | 111 } |
112 | 112 |
113 Bignum numerator; | 113 Bignum numerator; |
114 Bignum denominator; | 114 Bignum denominator; |
115 Bignum delta_minus; | 115 Bignum delta_minus; |
116 Bignum delta_plus; | 116 Bignum delta_plus; |
117 // Make sure the bignum can grow large enough. The smallest double equal
s | 117 // Make sure the bignum can grow large enough. The smallest double equal
s |
118 // 4e-324. In this case the denominator needs fewer than 324*4 binary di
gits. | 118 // 4e-324. In this case the denominator needs fewer than 324*4 binary di
gits. |
119 // The maximum double is 1.7976931348623157e308 which needs fewer than | 119 // The maximum double is 1.7976931348623157e308 which needs fewer than |
120 // 308*4 binary digits. | 120 // 308*4 binary digits. |
121 ASSERT(Bignum::kMaxSignificantBits >= 324*4); | 121 DCHECK_GE(Bignum::kMaxSignificantBits, 324*4); |
122 bool need_boundary_deltas = (mode == BIGNUM_DTOA_SHORTEST); | 122 bool need_boundary_deltas = (mode == BIGNUM_DTOA_SHORTEST); |
123 InitialScaledStartValues(v, estimated_power, need_boundary_deltas, | 123 InitialScaledStartValues(v, estimated_power, need_boundary_deltas, |
124 &numerator, &denominator, | 124 &numerator, &denominator, |
125 &delta_minus, &delta_plus); | 125 &delta_minus, &delta_plus); |
126 // We now have v = (numerator / denominator) * 10^estimated_power. | 126 // We now have v = (numerator / denominator) * 10^estimated_power. |
127 FixupMultiply10(estimated_power, is_even, decimal_point, | 127 FixupMultiply10(estimated_power, is_even, decimal_point, |
128 &numerator, &denominator, | 128 &numerator, &denominator, |
129 &delta_minus, &delta_plus); | 129 &delta_minus, &delta_plus); |
130 // We now have v = (numerator / denominator) * 10^(decimal_point-1), and | 130 // We now have v = (numerator / denominator) * 10^(decimal_point-1), and |
131 // 1 <= (numerator + delta_plus) / denominator < 10 | 131 // 1 <= (numerator + delta_plus) / denominator < 10 |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
171 Vector<char> buffer, int* length) { | 171 Vector<char> buffer, int* length) { |
172 // Small optimization: if delta_minus and delta_plus are the same just r
euse | 172 // Small optimization: if delta_minus and delta_plus are the same just r
euse |
173 // one of the two bignums. | 173 // one of the two bignums. |
174 if (Bignum::Equal(*delta_minus, *delta_plus)) { | 174 if (Bignum::Equal(*delta_minus, *delta_plus)) { |
175 delta_plus = delta_minus; | 175 delta_plus = delta_minus; |
176 } | 176 } |
177 *length = 0; | 177 *length = 0; |
178 while (true) { | 178 while (true) { |
179 uint16_t digit; | 179 uint16_t digit; |
180 digit = numerator->DivideModuloIntBignum(*denominator); | 180 digit = numerator->DivideModuloIntBignum(*denominator); |
181 ASSERT(digit <= 9); // digit is a uint16_t and therefore always pos
itive. | 181 DCHECK_LE(digit, 9u); // digit is a uint16_t and therefore always p
ositive. |
182 // digit = numerator / denominator (integer division). | 182 // digit = numerator / denominator (integer division). |
183 // numerator = numerator % denominator. | 183 // numerator = numerator % denominator. |
184 buffer[(*length)++] = static_cast<char>(digit + '0'); | 184 buffer[(*length)++] = static_cast<char>(digit + '0'); |
185 | 185 |
186 // Can we stop already? | 186 // Can we stop already? |
187 // If the remainder of the division is less than the distance to the
lower | 187 // If the remainder of the division is less than the distance to the
lower |
188 // boundary we can stop. In this case we simply round down (discardi
ng the | 188 // boundary we can stop. In this case we simply round down (discardi
ng the |
189 // remainder). | 189 // remainder). |
190 // Similarly we test if we can round up (using the upper boundary). | 190 // Similarly we test if we can round up (using the upper boundary). |
191 bool in_delta_room_minus; | 191 bool in_delta_room_minus; |
(...skipping 25 matching lines...) Expand all Loading... |
217 // If yes, then the next digit would be < 5 and we can round dow
n. | 217 // If yes, then the next digit would be < 5 and we can round dow
n. |
218 int compare = Bignum::PlusCompare(*numerator, *numerator, *denom
inator); | 218 int compare = Bignum::PlusCompare(*numerator, *numerator, *denom
inator); |
219 if (compare < 0) { | 219 if (compare < 0) { |
220 // Remaining digits are less than .5. -> Round down (== do n
othing). | 220 // Remaining digits are less than .5. -> Round down (== do n
othing). |
221 } else if (compare > 0) { | 221 } else if (compare > 0) { |
222 // Remaining digits are more than .5 of denominator. -> Roun
d up. | 222 // Remaining digits are more than .5 of denominator. -> Roun
d up. |
223 // Note that the last digit could not be a '9' as otherwise
the whole | 223 // Note that the last digit could not be a '9' as otherwise
the whole |
224 // loop would have stopped earlier. | 224 // loop would have stopped earlier. |
225 // We still have an assert here in case the preconditions we
re not | 225 // We still have an assert here in case the preconditions we
re not |
226 // satisfied. | 226 // satisfied. |
227 ASSERT(buffer[(*length) - 1] != '9'); | 227 DCHECK_NE(buffer[(*length) - 1], '9'); |
228 buffer[(*length) - 1]++; | 228 buffer[(*length) - 1]++; |
229 } else { | 229 } else { |
230 // Halfway case. | 230 // Halfway case. |
231 // TODO(floitsch): need a way to solve half-way cases. | 231 // TODO(floitsch): need a way to solve half-way cases. |
232 // For now let's round towards even (since this is what Ga
y seems to | 232 // For now let's round towards even (since this is what Ga
y seems to |
233 // do). | 233 // do). |
234 | 234 |
235 if ((buffer[(*length) - 1] - '0') % 2 == 0) { | 235 if ((buffer[(*length) - 1] - '0') % 2 == 0) { |
236 // Round down => Do nothing. | 236 // Round down => Do nothing. |
237 } else { | 237 } else { |
238 ASSERT(buffer[(*length) - 1] != '9'); | 238 DCHECK_NE(buffer[(*length) - 1], '9'); |
239 buffer[(*length) - 1]++; | 239 buffer[(*length) - 1]++; |
240 } | 240 } |
241 } | 241 } |
242 return; | 242 return; |
243 } else if (in_delta_room_minus) { | 243 } else if (in_delta_room_minus) { |
244 // Round down (== do nothing). | 244 // Round down (== do nothing). |
245 return; | 245 return; |
246 } else { // in_delta_room_plus | 246 } else { // in_delta_room_plus |
247 // Round up. | 247 // Round up. |
248 // Note again that the last digit could not be '9' since this wo
uld have | 248 // Note again that the last digit could not be '9' since this wo
uld have |
249 // stopped the loop earlier. | 249 // stopped the loop earlier. |
250 // We still have an ASSERT here, in case the preconditions were
not | 250 // We still have an ASSERT here, in case the preconditions were
not |
251 // satisfied. | 251 // satisfied. |
252 ASSERT(buffer[(*length) -1] != '9'); | 252 DCHECK_NE(buffer[(*length) -1], '9'); |
253 buffer[(*length) - 1]++; | 253 buffer[(*length) - 1]++; |
254 return; | 254 return; |
255 } | 255 } |
256 } | 256 } |
257 } | 257 } |
258 | 258 |
259 | 259 |
260 // Let v = numerator / denominator < 10. | 260 // Let v = numerator / denominator < 10. |
261 // Then we generate 'count' digits of d = x.xxxxx... (without the decimal po
int) | 261 // Then we generate 'count' digits of d = x.xxxxx... (without the decimal po
int) |
262 // from left to right. Once 'count' digits have been produced we decide weth
er | 262 // from left to right. Once 'count' digits have been produced we decide weth
er |
263 // to round up or down. Remainders of exactly .5 round upwards. Numbers such | 263 // to round up or down. Remainders of exactly .5 round upwards. Numbers such |
264 // as 9.999999 propagate a carry all the way, and change the | 264 // as 9.999999 propagate a carry all the way, and change the |
265 // exponent (decimal_point), when rounding upwards. | 265 // exponent (decimal_point), when rounding upwards. |
266 static void GenerateCountedDigits(int count, int* decimal_point, | 266 static void GenerateCountedDigits(int count, int* decimal_point, |
267 Bignum* numerator, Bignum* denominator, | 267 Bignum* numerator, Bignum* denominator, |
268 Vector<char>(buffer), int* length) { | 268 Vector<char>(buffer), int* length) { |
269 ASSERT(count >= 0); | 269 DCHECK_GE(count, 0); |
270 for (int i = 0; i < count - 1; ++i) { | 270 for (int i = 0; i < count - 1; ++i) { |
271 uint16_t digit; | 271 uint16_t digit; |
272 digit = numerator->DivideModuloIntBignum(*denominator); | 272 digit = numerator->DivideModuloIntBignum(*denominator); |
273 ASSERT(digit <= 9); // digit is a uint16_t and therefore always pos
itive. | 273 DCHECK_LE(digit, 9u); // digit is a uint16_t and therefore always p
ositive. |
274 // digit = numerator / denominator (integer division). | 274 // digit = numerator / denominator (integer division). |
275 // numerator = numerator % denominator. | 275 // numerator = numerator % denominator. |
276 buffer[i] = static_cast<char>(digit + '0'); | 276 buffer[i] = static_cast<char>(digit + '0'); |
277 // Prepare for next iteration. | 277 // Prepare for next iteration. |
278 numerator->Times10(); | 278 numerator->Times10(); |
279 } | 279 } |
280 // Generate the last digit. | 280 // Generate the last digit. |
281 uint16_t digit; | 281 uint16_t digit; |
282 digit = numerator->DivideModuloIntBignum(*denominator); | 282 digit = numerator->DivideModuloIntBignum(*denominator); |
283 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { | 283 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
316 // Ex: 0.001 with requested_digits == 1. | 316 // Ex: 0.001 with requested_digits == 1. |
317 // Set decimal-point to -requested_digits. This is what Gay does. | 317 // Set decimal-point to -requested_digits. This is what Gay does. |
318 // Note that it should not have any effect anyways since the string
is | 318 // Note that it should not have any effect anyways since the string
is |
319 // empty. | 319 // empty. |
320 *decimal_point = -requested_digits; | 320 *decimal_point = -requested_digits; |
321 *length = 0; | 321 *length = 0; |
322 return; | 322 return; |
323 } else if (-(*decimal_point) == requested_digits) { | 323 } else if (-(*decimal_point) == requested_digits) { |
324 // We only need to verify if the number rounds down or up. | 324 // We only need to verify if the number rounds down or up. |
325 // Ex: 0.04 and 0.06 with requested_digits == 1. | 325 // Ex: 0.04 and 0.06 with requested_digits == 1. |
326 ASSERT(*decimal_point == -requested_digits); | 326 DCHECK_EQ(*decimal_point, -requested_digits); |
327 // Initially the fraction lies in range (1, 10]. Multiply the denomi
nator | 327 // Initially the fraction lies in range (1, 10]. Multiply the denomi
nator |
328 // by 10 so that we can compare more easily. | 328 // by 10 so that we can compare more easily. |
329 denominator->Times10(); | 329 denominator->Times10(); |
330 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0)
{ | 330 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0)
{ |
331 // If the fraction is >= 0.5 then we have to include the rounded | 331 // If the fraction is >= 0.5 then we have to include the rounded |
332 // digit. | 332 // digit. |
333 buffer[0] = '1'; | 333 buffer[0] = '1'; |
334 *length = 1; | 334 *length = 1; |
335 (*decimal_point)++; | 335 (*decimal_point)++; |
336 } else { | 336 } else { |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
395 return static_cast<int>(estimate); | 395 return static_cast<int>(estimate); |
396 } | 396 } |
397 | 397 |
398 | 398 |
399 // See comments for InitialScaledStartValues. | 399 // See comments for InitialScaledStartValues. |
400 static void InitialScaledStartValuesPositiveExponent( | 400 static void InitialScaledStartValuesPositiveExponent( |
401 double v, int estimated
_power, bool need_boundary_deltas, | 401 double v, int estimated
_power, bool need_boundary_deltas, |
402 Bignum* numerator, Bign
um* denominator, | 402 Bignum* numerator, Bign
um* denominator, |
403 Bignum* delta_minus, Bi
gnum* delta_plus) { | 403 Bignum* delta_minus, Bi
gnum* delta_plus) { |
404 // A positive exponent implies a positive power. | 404 // A positive exponent implies a positive power. |
405 ASSERT(estimated_power >= 0); | 405 DCHECK_GE(estimated_power, 0); |
406 // Since the estimated_power is positive we simply multiply the denomina
tor | 406 // Since the estimated_power is positive we simply multiply the denomina
tor |
407 // by 10^estimated_power. | 407 // by 10^estimated_power. |
408 | 408 |
409 // numerator = v. | 409 // numerator = v. |
410 numerator->AssignUInt64(Double(v).Significand()); | 410 numerator->AssignUInt64(Double(v).Significand()); |
411 numerator->ShiftLeft(Double(v).Exponent()); | 411 numerator->ShiftLeft(Double(v).Exponent()); |
412 // denominator = 10^estimated_power. | 412 // denominator = 10^estimated_power. |
413 denominator->AssignPowerUInt16(10, estimated_power); | 413 denominator->AssignPowerUInt16(10, estimated_power); |
414 | 414 |
415 if (need_boundary_deltas) { | 415 if (need_boundary_deltas) { |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
514 // delta_plus = delta_minus = 10^estimated_power | 514 // delta_plus = delta_minus = 10^estimated_power |
515 delta_plus->AssignBignum(*power_ten); | 515 delta_plus->AssignBignum(*power_ten); |
516 delta_minus->AssignBignum(*power_ten); | 516 delta_minus->AssignBignum(*power_ten); |
517 } | 517 } |
518 | 518 |
519 // numerator = significand * 2 * 10^-estimated_power | 519 // numerator = significand * 2 * 10^-estimated_power |
520 // since v = significand * 2^exponent this is equivalent to | 520 // since v = significand * 2^exponent this is equivalent to |
521 // numerator = v * 10^-estimated_power * 2 * 2^-exponent. | 521 // numerator = v * 10^-estimated_power * 2 * 2^-exponent. |
522 // Remember: numerator has been abused as power_ten. So no need to assig
n it | 522 // Remember: numerator has been abused as power_ten. So no need to assig
n it |
523 // to itself. | 523 // to itself. |
524 ASSERT(numerator == power_ten); | 524 DCHECK_EQ(numerator, power_ten); |
525 numerator->MultiplyByUInt64(significand); | 525 numerator->MultiplyByUInt64(significand); |
526 | 526 |
527 // denominator = 2 * 2^-exponent with exponent < 0. | 527 // denominator = 2 * 2^-exponent with exponent < 0. |
528 denominator->AssignUInt16(1); | 528 denominator->AssignUInt16(1); |
529 denominator->ShiftLeft(-exponent); | 529 denominator->ShiftLeft(-exponent); |
530 | 530 |
531 if (need_boundary_deltas) { | 531 if (need_boundary_deltas) { |
532 // Introduce a common denominator so that the deltas to the boundari
es are | 532 // Introduce a common denominator so that the deltas to the boundari
es are |
533 // integers. | 533 // integers. |
534 numerator->ShiftLeft(1); | 534 numerator->ShiftLeft(1); |
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
648 } else { | 648 } else { |
649 delta_minus->Times10(); | 649 delta_minus->Times10(); |
650 delta_plus->Times10(); | 650 delta_plus->Times10(); |
651 } | 651 } |
652 } | 652 } |
653 } | 653 } |
654 | 654 |
655 } // namespace double_conversion | 655 } // namespace double_conversion |
656 | 656 |
657 } // namespace WTF | 657 } // namespace WTF |
OLD | NEW |