From 2b226c598f7d358b173541abc2b35f60693a9765 Mon Sep 17 00:00:00 2001 From: "floitschV8@gmail.com" Date: Thu, 14 Oct 2010 13:47:48 +0000 Subject: [PATCH] Weed out extreme exponents in strtod. If a decimal exponent is less than -309 return 0.0. If a decimal exponent is greater than +324 return +infinity. BUG= TEST= Review URL: http://codereview.chromium.org/3519017 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@5623 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/conversions.cc | 4 +- src/strtod.cc | 55 ++++++++++++++++++++----- src/strtod.h | 2 +- test/cctest/test-strtod.cc | 84 +++++++++++++++++++++++++++++--------- 4 files changed, 113 insertions(+), 32 deletions(-) diff --git a/src/conversions.cc b/src/conversions.cc index a7a086766..790e807ae 100644 --- a/src/conversions.cc +++ b/src/conversions.cc @@ -353,7 +353,7 @@ static double InternalStringToInt(Iterator current, EndMark end, int radix) { ASSERT(buffer_pos < kBufferSize); buffer[buffer_pos] = '\0'; - Vector buffer_vector(buffer, buffer_pos); + Vector buffer_vector(buffer, buffer_pos); return sign ? -Strtod(buffer_vector, 0) : Strtod(buffer_vector, 0); } @@ -653,7 +653,7 @@ static double InternalStringToDouble(Iterator current, ASSERT(buffer_pos < kBufferSize); buffer[buffer_pos] = '\0'; - double converted = Strtod(Vector(buffer, buffer_pos), exponent); + double converted = Strtod(Vector(buffer, buffer_pos), exponent); return sign? -converted: converted; } diff --git a/src/strtod.cc b/src/strtod.cc index bfbb5db7b..68444fc85 100644 --- a/src/strtod.cc +++ b/src/strtod.cc @@ -43,6 +43,14 @@ static const int kMaxExactDoubleIntegerDecimalDigits = 15; // 2^64 = 18446744073709551616 // Any integer with at most 19 digits will hence fit into a 64bit datatype. static const int kMaxUint64DecimalDigits = 19; +// Max double: 1.7976931348623157 x 10^308 +// Min non-zero double: 4.9406564584124654 x 10^-324 +// Any x >= 10^309 is interpreted as +infinity. +// Any x <= 10^-324 is interpreted as 0. +// Note that 2.5e-324 (despite being smaller than the min double) will be read +// as non-zero (equal to the min non-zero double). +static const int kMaxDecimalPower = 309; +static const int kMinDecimalPower = -324; static const double exact_powers_of_ten[] = { 1.0, // 10^0 @@ -76,26 +84,50 @@ static const int kExactPowersOfTenSize = ARRAY_SIZE(exact_powers_of_ten); extern "C" double gay_strtod(const char* s00, const char** se); -static double old_strtod(Vector buffer, int exponent) { +static double old_strtod(Vector buffer, int exponent) { char gay_buffer[1024]; Vector gay_buffer_vector(gay_buffer, sizeof(gay_buffer)); - buffer.start()[buffer.length()] = '\0'; - OS::SNPrintF(gay_buffer_vector, "%se%d", buffer.start(), exponent); + int pos = 0; + for (int i = 0; i < buffer.length(); ++i) { + gay_buffer_vector[pos++] = buffer[i]; + } + gay_buffer_vector[pos++] = 'e'; + if (exponent < 0) { + gay_buffer_vector[pos++] = '-'; + exponent = -exponent; + } + const int kNumberOfExponentDigits = 5; + for (int i = kNumberOfExponentDigits - 1; i >= 0; i--) { + gay_buffer_vector[pos + i] = exponent % 10 + '0'; + exponent /= 10; + } + pos += kNumberOfExponentDigits; + gay_buffer_vector[pos] = '\0'; return gay_strtod(gay_buffer, NULL); } -static Vector TrimTrailingZeros(Vector buffer) { +static Vector TrimLeadingZeros(Vector buffer) { + for (int i = 0; i < buffer.length(); i++) { + if (buffer[i] != '0') { + return Vector(buffer.start() + i, buffer.length() - i); + } + } + return Vector(buffer.start(), 0); +} + + +static Vector TrimTrailingZeros(Vector buffer) { for (int i = buffer.length() - 1; i >= 0; --i) { if (buffer[i] != '0') { - return Vector(buffer.start(), i + 1); + return Vector(buffer.start(), i + 1); } } - return Vector(buffer.start(), 0); + return Vector(buffer.start(), 0); } -uint64_t ReadUint64(Vector buffer) { +uint64_t ReadUint64(Vector buffer) { ASSERT(buffer.length() <= kMaxUint64DecimalDigits); uint64_t result = 0; for (int i = 0; i < buffer.length(); ++i) { @@ -107,10 +139,13 @@ uint64_t ReadUint64(Vector buffer) { } -double Strtod(Vector buffer, int exponent) { - Vector trimmed = TrimTrailingZeros(buffer); +double Strtod(Vector buffer, int exponent) { + Vector left_trimmed = TrimLeadingZeros(buffer); + Vector trimmed = TrimTrailingZeros(left_trimmed); + exponent += left_trimmed.length() - trimmed.length(); if (trimmed.length() == 0) return 0.0; - exponent += buffer.length() - trimmed.length(); + if (exponent + trimmed.length() - 1 >= kMaxDecimalPower) return V8_INFINITY; + if (exponent + trimmed.length() <= kMinDecimalPower) return 0.0; if (trimmed.length() <= kMaxExactDoubleIntegerDecimalDigits) { // The trimmed input fits into a double. // If the 10^exponent (resp. 10^-exponent) fits into a double too then we diff --git a/src/strtod.h b/src/strtod.h index 4d256baf2..1a5a96c8e 100644 --- a/src/strtod.h +++ b/src/strtod.h @@ -33,7 +33,7 @@ namespace internal { // The buffer must only contain digits in the range [0-9]. It must not // contain a dot or a sign. It must not start with '0', and must not be empty. -double Strtod(Vector buffer, int exponent); +double Strtod(Vector buffer, int exponent); } } // namespace v8::internal diff --git a/test/cctest/test-strtod.cc b/test/cctest/test-strtod.cc index 85a7dbdc3..1eefb7fd2 100644 --- a/test/cctest/test-strtod.cc +++ b/test/cctest/test-strtod.cc @@ -4,30 +4,32 @@ #include "v8.h" -#include "platform.h" #include "cctest.h" #include "strtod.h" using namespace v8::internal; -static const int kBufferSize = 100; +static Vector StringToVector(const char* str) { + return Vector(str, StrLength(str)); +} + + +static double StrtodChar(const char* str, int exponent) { + return Strtod(StringToVector(str), exponent); +} TEST(Strtod) { - char buffer_array[kBufferSize]; - Vector buffer(buffer_array, kBufferSize); - Vector vector; + Vector vector; - OS::StrNCpy(buffer, "0", kBufferSize); - vector = Vector(buffer_array, strlen(buffer_array)); + vector = StringToVector("0"); CHECK_EQ(0.0, Strtod(vector, 1)); CHECK_EQ(0.0, Strtod(vector, 2)); CHECK_EQ(0.0, Strtod(vector, -2)); CHECK_EQ(0.0, Strtod(vector, -999)); CHECK_EQ(0.0, Strtod(vector, +999)); - OS::StrNCpy(buffer, "1", kBufferSize); - vector = Vector(buffer_array, strlen(buffer_array)); + vector = StringToVector("1"); CHECK_EQ(1.0, Strtod(vector, 0)); CHECK_EQ(10.0, Strtod(vector, 1)); CHECK_EQ(100.0, Strtod(vector, 2)); @@ -46,8 +48,7 @@ TEST(Strtod) { CHECK_EQ(1e-25, Strtod(vector, -25)); CHECK_EQ(1e-39, Strtod(vector, -39)); - OS::StrNCpy(buffer, "2", kBufferSize); - vector = Vector(buffer_array, strlen(buffer_array)); + vector = StringToVector("2"); CHECK_EQ(2.0, Strtod(vector, 0)); CHECK_EQ(20.0, Strtod(vector, 1)); CHECK_EQ(200.0, Strtod(vector, 2)); @@ -66,8 +67,7 @@ TEST(Strtod) { CHECK_EQ(2e-25, Strtod(vector, -25)); CHECK_EQ(2e-39, Strtod(vector, -39)); - OS::StrNCpy(buffer, "9", kBufferSize); - vector = Vector(buffer_array, strlen(buffer_array)); + vector = StringToVector("9"); CHECK_EQ(9.0, Strtod(vector, 0)); CHECK_EQ(90.0, Strtod(vector, 1)); CHECK_EQ(900.0, Strtod(vector, 2)); @@ -86,8 +86,7 @@ TEST(Strtod) { CHECK_EQ(9e-25, Strtod(vector, -25)); CHECK_EQ(9e-39, Strtod(vector, -39)); - OS::StrNCpy(buffer, "12345", kBufferSize); - vector = Vector(buffer_array, strlen(buffer_array)); + vector = StringToVector("12345"); CHECK_EQ(12345.0, Strtod(vector, 0)); CHECK_EQ(123450.0, Strtod(vector, 1)); CHECK_EQ(1234500.0, Strtod(vector, 2)); @@ -109,8 +108,7 @@ TEST(Strtod) { CHECK_EQ(12345e-25, Strtod(vector, -25)); CHECK_EQ(12345e-39, Strtod(vector, -39)); - OS::StrNCpy(buffer, "12345678901234", kBufferSize); - vector = Vector(buffer_array, strlen(buffer_array)); + vector = StringToVector("12345678901234"); CHECK_EQ(12345678901234.0, Strtod(vector, 0)); CHECK_EQ(123456789012340.0, Strtod(vector, 1)); CHECK_EQ(1234567890123400.0, Strtod(vector, 2)); @@ -132,8 +130,7 @@ TEST(Strtod) { CHECK_EQ(12345678901234e-25, Strtod(vector, -25)); CHECK_EQ(12345678901234e-39, Strtod(vector, -39)); - OS::StrNCpy(buffer, "123456789012345", kBufferSize); - vector = Vector(buffer_array, strlen(buffer_array)); + vector = StringToVector("123456789012345"); CHECK_EQ(123456789012345.0, Strtod(vector, 0)); CHECK_EQ(1234567890123450.0, Strtod(vector, 1)); CHECK_EQ(12345678901234500.0, Strtod(vector, 2)); @@ -152,4 +149,53 @@ TEST(Strtod) { CHECK_EQ(123456789012345e-23, Strtod(vector, -23)); CHECK_EQ(123456789012345e-25, Strtod(vector, -25)); CHECK_EQ(123456789012345e-39, Strtod(vector, -39)); + + CHECK_EQ(0.0, StrtodChar("0", 12345)); + CHECK_EQ(0.0, StrtodChar("", 1324)); + CHECK_EQ(0.0, StrtodChar("000000000", 123)); + CHECK_EQ(0.0, StrtodChar("2", -324)); + CHECK_EQ(3e-324, StrtodChar("3", -324)); + // It would be more readable to put non-zero literals on the left side (i.e. + // CHECK_EQ(1e-325, StrtodChar("1", -325))), but then Gcc complains that + // they are truncated to zero. + CHECK_EQ(0.0, StrtodChar("1", -325)); + CHECK_EQ(0.0, StrtodChar("1", -325)); + CHECK_EQ(0.0, StrtodChar("20000", -328)); + CHECK_EQ(30000e-328, StrtodChar("30000", -328)); + CHECK_EQ(0.0, StrtodChar("10000", -329)); + CHECK_EQ(0.0, StrtodChar("90000", -329)); + CHECK_EQ(0.0, StrtodChar("000000001", -325)); + CHECK_EQ(0.0, StrtodChar("000000001", -325)); + CHECK_EQ(0.0, StrtodChar("0000000020000", -328)); + CHECK_EQ(30000e-328, StrtodChar("00000030000", -328)); + CHECK_EQ(0.0, StrtodChar("0000000010000", -329)); + CHECK_EQ(0.0, StrtodChar("0000000090000", -329)); + + // It would be more readable to put the literals (and not V8_INFINITY) on the + // left side (i.e. CHECK_EQ(1e309, StrtodChar("1", 309))), but then Gcc + // complains that the floating constant exceeds range of 'double'. + CHECK_EQ(V8_INFINITY, StrtodChar("1", 309)); + CHECK_EQ(1e308, StrtodChar("1", 308)); + CHECK_EQ(1234e305, StrtodChar("1234", 305)); + CHECK_EQ(1234e304, StrtodChar("1234", 304)); + CHECK_EQ(V8_INFINITY, StrtodChar("18", 307)); + CHECK_EQ(17e307, StrtodChar("17", 307)); + CHECK_EQ(V8_INFINITY, StrtodChar("0000001", 309)); + CHECK_EQ(1e308, StrtodChar("00000001", 308)); + CHECK_EQ(1234e305, StrtodChar("00000001234", 305)); + CHECK_EQ(1234e304, StrtodChar("000000001234", 304)); + CHECK_EQ(V8_INFINITY, StrtodChar("0000000018", 307)); + CHECK_EQ(17e307, StrtodChar("0000000017", 307)); + CHECK_EQ(V8_INFINITY, StrtodChar("1000000", 303)); + CHECK_EQ(1e308, StrtodChar("100000", 303)); + CHECK_EQ(1234e305, StrtodChar("123400000", 300)); + CHECK_EQ(1234e304, StrtodChar("123400000", 299)); + CHECK_EQ(V8_INFINITY, StrtodChar("180000000", 300)); + CHECK_EQ(17e307, StrtodChar("170000000", 300)); + CHECK_EQ(V8_INFINITY, StrtodChar("00000001000000", 303)); + CHECK_EQ(1e308, StrtodChar("000000000000100000", 303)); + CHECK_EQ(1234e305, StrtodChar("00000000123400000", 300)); + CHECK_EQ(1234e304, StrtodChar("0000000123400000", 299)); + CHECK_EQ(V8_INFINITY, StrtodChar("00000000180000000", 300)); + CHECK_EQ(17e307, StrtodChar("00000000170000000", 300)); } -- 2.34.1