| 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 |