| #include "strings/numbers.h" |
| |
| #include <float.h> // for FLT_DIG |
| #include <cassert> |
| #include <memory> |
| |
| #include "strings/ascii_ctype.h" |
| |
| namespace dynamic_depth { |
| namespace strings { |
| namespace { |
| |
| // Represents integer values of digits. |
| // Uses 36 to indicate an invalid character since we support |
| // bases up to 36. |
| static const int8 kAsciiToInt[256] = { |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, // 16 36s. |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 0, 1, 2, 3, 4, 5, |
| 6, 7, 8, 9, 36, 36, 36, 36, 36, 36, 36, 10, 11, 12, 13, 14, 15, 16, 17, |
| 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, |
| 36, 36, 36, 36, 36, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, |
| 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, |
| 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36}; |
| |
| // Parse the sign and optional hex or oct prefix in text. |
| inline bool safe_parse_sign_and_base(string* text /*inout*/, |
| int* base_ptr /*inout*/, |
| bool* negative_ptr /*output*/) { |
| if (text->data() == NULL) { |
| return false; |
| } |
| |
| const char* start = text->data(); |
| const char* end = start + text->size(); |
| int base = *base_ptr; |
| |
| // Consume whitespace. |
| while (start < end && ascii_isspace(start[0])) { |
| ++start; |
| } |
| while (start < end && ascii_isspace(end[-1])) { |
| --end; |
| } |
| if (start >= end) { |
| return false; |
| } |
| |
| // Consume sign. |
| *negative_ptr = (start[0] == '-'); |
| if (*negative_ptr || start[0] == '+') { |
| ++start; |
| if (start >= end) { |
| return false; |
| } |
| } |
| |
| // Consume base-dependent prefix. |
| // base 0: "0x" -> base 16, "0" -> base 8, default -> base 10 |
| // base 16: "0x" -> base 16 |
| // Also validate the base. |
| if (base == 0) { |
| if (end - start >= 2 && start[0] == '0' && |
| (start[1] == 'x' || start[1] == 'X')) { |
| base = 16; |
| start += 2; |
| if (start >= end) { |
| // "0x" with no digits after is invalid. |
| return false; |
| } |
| } else if (end - start >= 1 && start[0] == '0') { |
| base = 8; |
| start += 1; |
| } else { |
| base = 10; |
| } |
| } else if (base == 16) { |
| if (end - start >= 2 && start[0] == '0' && |
| (start[1] == 'x' || start[1] == 'X')) { |
| start += 2; |
| if (start >= end) { |
| // "0x" with no digits after is invalid. |
| return false; |
| } |
| } |
| } else if (base >= 2 && base <= 36) { |
| // okay |
| } else { |
| return false; |
| } |
| text->assign(start, end - start); |
| *base_ptr = base; |
| return true; |
| } |
| |
| // Consume digits. |
| // |
| // The classic loop: |
| // |
| // for each digit |
| // value = value * base + digit |
| // value *= sign |
| // |
| // The classic loop needs overflow checking. It also fails on the most |
| // negative integer, -2147483648 in 32-bit two's complement representation. |
| // |
| // My improved loop: |
| // |
| // if (!negative) |
| // for each digit |
| // value = value * base |
| // value = value + digit |
| // else |
| // for each digit |
| // value = value * base |
| // value = value - digit |
| // |
| // Overflow checking becomes simple. |
| |
| // Lookup tables per IntType: |
| // vmax/base and vmin/base are precomputed because division costs at least 8ns. |
| // TODO(junyer): Doing this per base instead (i.e. an array of structs, not a |
| // struct of arrays) would probably be better in terms of d-cache for the most |
| // commonly used bases. |
| template <typename IntType> |
| struct LookupTables { |
| static const IntType kVmaxOverBase[]; |
| static const IntType kVminOverBase[]; |
| }; |
| |
| // An array initializer macro for X/base where base in [0, 36]. |
| // However, note that lookups for base in [0, 1] should never happen because |
| // base has been validated to be in [2, 36] by safe_parse_sign_and_base(). |
| #define X_OVER_BASE_INITIALIZER(X) \ |
| { \ |
| 0, 0, X / 2, X / 3, X / 4, X / 5, X / 6, X / 7, \ |
| X / 8, X / 9, X / 10, X / 11, X / 12, X / 13, X / 14, X / 15, \ |
| X / 16, X / 17, X / 18, X / 19, X / 20, X / 21, X / 22, X / 23, \ |
| X / 24, X / 25, X / 26, X / 27, X / 28, X / 29, X / 30, X / 31, \ |
| X / 32, X / 33, X / 34, X / 35, X / 36, \ |
| }; |
| |
| template <typename IntType> |
| const IntType LookupTables<IntType>::kVmaxOverBase[] = |
| X_OVER_BASE_INITIALIZER(std::numeric_limits<IntType>::max()); |
| |
| template <typename IntType> |
| const IntType LookupTables<IntType>::kVminOverBase[] = |
| X_OVER_BASE_INITIALIZER(std::numeric_limits<IntType>::min()); |
| |
| #undef X_OVER_BASE_INITIALIZER |
| |
| template <typename IntType> |
| inline bool safe_parse_positive_int(const string& text, int base, |
| IntType* value_p) { |
| IntType value = 0; |
| const IntType vmax = std::numeric_limits<IntType>::max(); |
| assert(vmax > 0); |
| assert(vmax >= base); |
| const IntType vmax_over_base = LookupTables<IntType>::kVmaxOverBase[base]; |
| const char* start = text.data(); |
| const char* end = start + text.size(); |
| // loop over digits |
| for (; start < end; ++start) { |
| unsigned char c = static_cast<unsigned char>(start[0]); |
| int digit = kAsciiToInt[c]; |
| if (digit >= base) { |
| *value_p = value; |
| return false; |
| } |
| if (value > vmax_over_base) { |
| *value_p = vmax; |
| return false; |
| } |
| value *= base; |
| if (value > vmax - digit) { |
| *value_p = vmax; |
| return false; |
| } |
| value += digit; |
| } |
| *value_p = value; |
| return true; |
| } |
| |
| template <typename IntType> |
| inline bool safe_parse_negative_int(const string& text, int base, |
| IntType* value_p) { |
| IntType value = 0; |
| const IntType vmin = std::numeric_limits<IntType>::min(); |
| assert(vmin < 0); |
| assert(vmin <= 0 - base); |
| IntType vmin_over_base = LookupTables<IntType>::kVminOverBase[base]; |
| // 2003 c++ standard [expr.mul] |
| // "... the sign of the remainder is implementation-defined." |
| // Although (vmin/base)*base + vmin%base is always vmin. |
| // 2011 c++ standard tightens the spec but we cannot rely on it. |
| // TODO(junyer): Handle this in the lookup table generation. |
| if (vmin % base > 0) { |
| vmin_over_base += 1; |
| } |
| const char* start = text.data(); |
| const char* end = start + text.size(); |
| // loop over digits |
| for (; start < end; ++start) { |
| unsigned char c = static_cast<unsigned char>(start[0]); |
| int digit = kAsciiToInt[c]; |
| if (digit >= base) { |
| *value_p = value; |
| return false; |
| } |
| if (value < vmin_over_base) { |
| *value_p = vmin; |
| return false; |
| } |
| value *= base; |
| if (value < vmin + digit) { |
| *value_p = vmin; |
| return false; |
| } |
| value -= digit; |
| } |
| *value_p = value; |
| return true; |
| } |
| |
| // Input format based on POSIX.1-2008 strtol |
| // http://pubs.opengroup.org/onlinepubs/9699919799/functions/strtol.html |
| template <typename IntType> |
| inline bool safe_int_internal(const string& text, IntType* value_p, int base) { |
| *value_p = 0; |
| bool negative; |
| string text_copy(text); |
| if (!safe_parse_sign_and_base(&text_copy, &base, &negative)) { |
| return false; |
| } |
| if (!negative) { |
| return safe_parse_positive_int(text_copy, base, value_p); |
| } else { |
| return safe_parse_negative_int(text_copy, base, value_p); |
| } |
| } |
| |
| template <typename IntType> |
| inline bool safe_uint_internal(const string& text, IntType* value_p, int base) { |
| *value_p = 0; |
| bool negative; |
| string text_copy(text); |
| if (!safe_parse_sign_and_base(&text_copy, &base, &negative) || negative) { |
| return false; |
| } |
| return safe_parse_positive_int(text_copy, base, value_p); |
| } |
| |
| // Writes a two-character representation of 'i' to 'buf'. 'i' must be in the |
| // range 0 <= i < 100, and buf must have space for two characters. Example: |
| // char buf[2]; |
| // PutTwoDigits(42, buf); |
| // // buf[0] == '4' |
| // // buf[1] == '2' |
| inline void PutTwoDigits(size_t i, char* buf) { |
| static const char two_ASCII_digits[100][2] = { |
| {'0', '0'}, {'0', '1'}, {'0', '2'}, {'0', '3'}, {'0', '4'}, {'0', '5'}, |
| {'0', '6'}, {'0', '7'}, {'0', '8'}, {'0', '9'}, {'1', '0'}, {'1', '1'}, |
| {'1', '2'}, {'1', '3'}, {'1', '4'}, {'1', '5'}, {'1', '6'}, {'1', '7'}, |
| {'1', '8'}, {'1', '9'}, {'2', '0'}, {'2', '1'}, {'2', '2'}, {'2', '3'}, |
| {'2', '4'}, {'2', '5'}, {'2', '6'}, {'2', '7'}, {'2', '8'}, {'2', '9'}, |
| {'3', '0'}, {'3', '1'}, {'3', '2'}, {'3', '3'}, {'3', '4'}, {'3', '5'}, |
| {'3', '6'}, {'3', '7'}, {'3', '8'}, {'3', '9'}, {'4', '0'}, {'4', '1'}, |
| {'4', '2'}, {'4', '3'}, {'4', '4'}, {'4', '5'}, {'4', '6'}, {'4', '7'}, |
| {'4', '8'}, {'4', '9'}, {'5', '0'}, {'5', '1'}, {'5', '2'}, {'5', '3'}, |
| {'5', '4'}, {'5', '5'}, {'5', '6'}, {'5', '7'}, {'5', '8'}, {'5', '9'}, |
| {'6', '0'}, {'6', '1'}, {'6', '2'}, {'6', '3'}, {'6', '4'}, {'6', '5'}, |
| {'6', '6'}, {'6', '7'}, {'6', '8'}, {'6', '9'}, {'7', '0'}, {'7', '1'}, |
| {'7', '2'}, {'7', '3'}, {'7', '4'}, {'7', '5'}, {'7', '6'}, {'7', '7'}, |
| {'7', '8'}, {'7', '9'}, {'8', '0'}, {'8', '1'}, {'8', '2'}, {'8', '3'}, |
| {'8', '4'}, {'8', '5'}, {'8', '6'}, {'8', '7'}, {'8', '8'}, {'8', '9'}, |
| {'9', '0'}, {'9', '1'}, {'9', '2'}, {'9', '3'}, {'9', '4'}, {'9', '5'}, |
| {'9', '6'}, {'9', '7'}, {'9', '8'}, {'9', '9'}}; |
| assert(i < 100); |
| memcpy(buf, two_ASCII_digits[i], 2); |
| } |
| |
| } // anonymous namespace |
| |
| // ---------------------------------------------------------------------- |
| // FastInt32ToBufferLeft() |
| // FastUInt32ToBufferLeft() |
| // FastInt64ToBufferLeft() |
| // FastUInt64ToBufferLeft() |
| // |
| // Like the Fast*ToBuffer() functions above, these are intended for speed. |
| // Unlike the Fast*ToBuffer() functions, however, these functions write |
| // their output to the beginning of the buffer (hence the name, as the |
| // output is left-aligned). The caller is responsible for ensuring that |
| // the buffer has enough space to hold the output. |
| // |
| // Returns a pointer to the end of the string (i.e. the null character |
| // terminating the string). |
| // ---------------------------------------------------------------------- |
| |
| // Used to optimize printing a decimal number's final digit. |
| const char one_ASCII_final_digits[10][2]{ |
| {'0', 0}, {'1', 0}, {'2', 0}, {'3', 0}, {'4', 0}, |
| {'5', 0}, {'6', 0}, {'7', 0}, {'8', 0}, {'9', 0}, |
| }; |
| |
| char* FastUInt32ToBufferLeft(uint32 u, char* buffer) { |
| uint32 digits; |
| // The idea of this implementation is to trim the number of divides to as few |
| // as possible, and also reducing memory stores and branches, by going in |
| // steps of two digits at a time rather than one whenever possible. |
| // The huge-number case is first, in the hopes that the compiler will output |
| // that case in one branch-free block of code, and only output conditional |
| // branches into it from below. |
| if (u >= 1000000000) { // >= 1,000,000,000 |
| digits = u / 100000000; // 100,000,000 |
| u -= digits * 100000000; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| lt100_000_000: |
| digits = u / 1000000; // 1,000,000 |
| u -= digits * 1000000; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| lt1_000_000: |
| digits = u / 10000; // 10,000 |
| u -= digits * 10000; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| lt10_000: |
| digits = u / 100; |
| u -= digits * 100; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| lt100: |
| digits = u; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| *buffer = 0; |
| return buffer; |
| } |
| |
| if (u < 100) { |
| digits = u; |
| if (u >= 10) goto lt100; |
| memcpy(buffer, one_ASCII_final_digits[u], 2); |
| return buffer + 1; |
| } |
| if (u < 10000) { // 10,000 |
| if (u >= 1000) goto lt10_000; |
| digits = u / 100; |
| u -= digits * 100; |
| *buffer++ = '0' + digits; |
| goto lt100; |
| } |
| if (u < 1000000) { // 1,000,000 |
| if (u >= 100000) goto lt1_000_000; |
| digits = u / 10000; // 10,000 |
| u -= digits * 10000; |
| *buffer++ = '0' + digits; |
| goto lt10_000; |
| } |
| if (u < 100000000) { // 100,000,000 |
| if (u >= 10000000) goto lt100_000_000; |
| digits = u / 1000000; // 1,000,000 |
| u -= digits * 1000000; |
| *buffer++ = '0' + digits; |
| goto lt1_000_000; |
| } |
| // we already know that u < 1,000,000,000 |
| digits = u / 100000000; // 100,000,000 |
| u -= digits * 100000000; |
| *buffer++ = '0' + digits; |
| goto lt100_000_000; |
| } |
| |
| char* FastInt32ToBufferLeft(int32 i, char* buffer) { |
| uint32 u = i; |
| if (i < 0) { |
| *buffer++ = '-'; |
| // We need to do the negation in modular (i.e., "unsigned") |
| // arithmetic; MSVC++ apprently warns for plain "-u", so |
| // we write the equivalent expression "0 - u" instead. |
| u = 0 - u; |
| } |
| return FastUInt32ToBufferLeft(u, buffer); |
| } |
| |
| char* FastUInt64ToBufferLeft(uint64 u64, char* buffer) { |
| uint32 u32 = static_cast<uint32>(u64); |
| if (u32 == u64) return FastUInt32ToBufferLeft(u32, buffer); |
| |
| // Here we know u64 has at least 10 decimal digits. |
| uint64 top_1to11 = u64 / 1000000000; |
| u32 = static_cast<uint32>(u64 - top_1to11 * 1000000000); |
| uint32 top_1to11_32 = static_cast<uint32>(top_1to11); |
| |
| if (top_1to11_32 == top_1to11) { |
| buffer = FastUInt32ToBufferLeft(top_1to11_32, buffer); |
| } else { |
| // top_1to11 has more than 32 bits too; print it in two steps. |
| uint32 top_8to9 = static_cast<uint32>(top_1to11 / 100); |
| uint32 mid_2 = static_cast<uint32>(top_1to11 - top_8to9 * 100); |
| buffer = FastUInt32ToBufferLeft(top_8to9, buffer); |
| PutTwoDigits(mid_2, buffer); |
| buffer += 2; |
| } |
| |
| // We have only 9 digits now, again the maximum uint32 can handle fully. |
| uint32 digits = u32 / 10000000; // 10,000,000 |
| u32 -= digits * 10000000; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| digits = u32 / 100000; // 100,000 |
| u32 -= digits * 100000; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| digits = u32 / 1000; // 1,000 |
| u32 -= digits * 1000; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| digits = u32 / 10; |
| u32 -= digits * 10; |
| PutTwoDigits(digits, buffer); |
| buffer += 2; |
| memcpy(buffer, one_ASCII_final_digits[u32], 2); |
| return buffer + 1; |
| } |
| |
| char* FastInt64ToBufferLeft(int64 i, char* buffer) { |
| uint64 u = i; |
| if (i < 0) { |
| *buffer++ = '-'; |
| u = 0 - u; |
| } |
| return FastUInt64ToBufferLeft(u, buffer); |
| } |
| |
| bool safe_strto32_base(const string& text, int32* value, int base) { |
| return safe_int_internal<int32>(text, value, base); |
| } |
| |
| bool safe_strto64_base(const string& text, int64* value, int base) { |
| return safe_int_internal<int64>(text, value, base); |
| } |
| |
| bool safe_strtou32_base(const string& text, uint32* value, int base) { |
| return safe_uint_internal<uint32>(text, value, base); |
| } |
| |
| bool safe_strtou64_base(const string& text, uint64* value, int base) { |
| return safe_uint_internal<uint64>(text, value, base); |
| } |
| |
| bool safe_strtof(const string& piece, float* value) { |
| *value = 0.0; |
| if (piece.empty()) return false; |
| char buf[32]; |
| std::unique_ptr<char[]> bigbuf; |
| char* str = buf; |
| if (piece.size() > sizeof(buf) - 1) { |
| bigbuf.reset(new char[piece.size() + 1]); |
| str = bigbuf.get(); |
| } |
| memcpy(str, piece.data(), piece.size()); |
| str[piece.size()] = '\0'; |
| |
| char* endptr; |
| #ifdef COMPILER_MSVC // has no strtof() |
| *value = strtod(str, &endptr); |
| #else |
| *value = strtof(str, &endptr); |
| #endif |
| if (endptr != str) { |
| while (ascii_isspace(*endptr)) ++endptr; |
| } |
| // Ignore range errors from strtod/strtof. |
| // The values it returns on underflow and |
| // overflow are the right fallback in a |
| // robust setting. |
| return *str != '\0' && *endptr == '\0'; |
| } |
| |
| bool safe_strtod(const string& piece, double* value) { |
| *value = 0.0; |
| if (piece.empty()) return false; |
| char buf[32]; |
| std::unique_ptr<char[]> bigbuf; |
| char* str = buf; |
| if (piece.size() > sizeof(buf) - 1) { |
| bigbuf.reset(new char[piece.size() + 1]); |
| str = bigbuf.get(); |
| } |
| memcpy(str, piece.data(), piece.size()); |
| str[piece.size()] = '\0'; |
| |
| char* endptr; |
| *value = strtod(str, &endptr); |
| if (endptr != str) { |
| while (ascii_isspace(*endptr)) ++endptr; |
| } |
| // Ignore range errors from strtod. The values it |
| // returns on underflow and overflow are the right |
| // fallback in a robust setting. |
| return *str != '\0' && *endptr == '\0'; |
| } |
| |
| string SimpleFtoa(float value) { |
| char buffer[kFastToBufferSize]; |
| return FloatToBuffer(value, buffer); |
| } |
| |
| char* FloatToBuffer(float value, char* buffer) { |
| // FLT_DIG is 6 for IEEE-754 floats, which are used on almost all |
| // platforms these days. Just in case some system exists where FLT_DIG |
| // is significantly larger -- and risks overflowing our buffer -- we have |
| // this assert. |
| assert(FLT_DIG < 10); |
| |
| int snprintf_result = |
| snprintf(buffer, kFastToBufferSize, "%.*g", FLT_DIG, value); |
| |
| // The snprintf should never overflow because the buffer is significantly |
| // larger than the precision we asked for. |
| assert(snprintf_result > 0 && snprintf_result < kFastToBufferSize); |
| |
| float parsed_value; |
| if (!safe_strtof(buffer, &parsed_value) || parsed_value != value) { |
| snprintf_result = |
| snprintf(buffer, kFastToBufferSize, "%.*g", FLT_DIG + 2, value); |
| |
| // Should never overflow; see above. |
| assert(snprintf_result > 0 && snprintf_result < kFastToBufferSize); |
| } |
| return buffer; |
| } |
| |
| } // namespace strings |
| } // namespace dynamic_depth |