From cf6ab6bb2b800fae859ccc735f398d22a7336a00 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Sun, 24 Sep 2017 08:20:48 -0700 Subject: Changes imported from Abseil "staging" branch: - b527a3e4b36b644ac424e3c525b1cd393f6f6c40 Fix some typos in the usage examples by Jorg Brown - 82be4a9adf3bb0ddafc0d46274969c99afffe870 Fix typo in optional.h comment. by Abseil Team - d6ee63bf8fc51fba074c23b33cebc28c808d7f07 Remove internal-only identifiers from code. by Daniel Katz - f9c3ad2f0d73f53b21603638af8b4bed636e79f4 Use easier understandable names for absl::StartsWith and ... by Abseil Team - 7c16c14fefee89c927b8789d6043c4691bcffc9b Add -Wno-missing-prototypes back to the LLVM copts. by Derek Mauro - 2f4b7d2e50c7023240242f1e15db60ccd7e8768d IWYU | absl/strings by Juemin Yang - a99cbcc1daa34a2d6a2bb26de275e05173cc77e9 IWYU | absl/type by Juemin Yang - 12e1146d0fc76c071d7e0ebaabb62f0a984fae66 Use LLVM_FLAGS and LLVM_TEST_FLAGS when --compiler=llvm. by Derek Mauro - cd6bea616abda558d0bace5bd77455662a233688 IWYU | absl/debugging by Juemin Yang - d9a7382e59d46a8581b6b7a31cd5a48bb89326e9 IWYU | absl/synchronization by Juemin Yang - 07ec7d6d5a4a666f4183c5d0ed9c342baa7b24bc IWYU | absl/numeric by Juemin Yang - 12bfe40051f4270f8707e191af5652f83f2f750c Remove the RoundTrip{Float,Double}ToBuffer routines from ... by Jorg Brown - eeb4fd67c9d97f66cb9475c3c5e51ab132f1c810 Adds conversion functions for converting between absl/tim... by Greg Miller - 59a2108d05d4ea85dc5cc11e49b2cd2335d4295a Change Substitute to use %.6g formatting rather than 15/1... by Jorg Brown - 394becb48e0fcd161642cdaac5120d32567e0ef8 IWYU | absl/meta by Juemin Yang - 1e5da6e8da336699b2469dcf6dda025b9b0ec4c9 Rewrite atomic_hook.h to not use std::atomic under Wi... by Greg Falcon GitOrigin-RevId: b527a3e4b36b644ac424e3c525b1cd393f6f6c40 Change-Id: I14e331d91c956ef045ac7927091a9f179716de0c --- absl/strings/numbers.cc | 387 +----------------------------------------------- 1 file changed, 4 insertions(+), 383 deletions(-) (limited to 'absl/strings/numbers.cc') diff --git a/absl/strings/numbers.cc b/absl/strings/numbers.cc index 3b093b9..ac73f53 100644 --- a/absl/strings/numbers.cc +++ b/absl/strings/numbers.cc @@ -3,19 +3,20 @@ #include "absl/strings/numbers.h" +#include #include -#include #include // for DBL_DIG and FLT_DIG #include // for HUGE_VAL +#include #include #include #include +#include #include #include -#include +#include #include "absl/base/internal/raw_logging.h" -#include "absl/numeric/int128.h" #include "absl/strings/ascii.h" #include "absl/strings/internal/memutil.h" #include "absl/strings/str_cat.h" @@ -291,386 +292,6 @@ char* numbers_internal::FastInt64ToBuffer(int64_t i, char* buffer) { return numbers_internal::FastUInt64ToBuffer(u, buffer); } -// Although DBL_DIG is typically 15, DBL_MAX is normally represented with 17 -// digits of precision. When converted to a std::string value with fewer digits -// of precision using strtod(), the result can be bigger than DBL_MAX due to -// a rounding error. Converting this value back to a double will produce an -// Inf which will trigger a SIGFPE if FP exceptions are enabled. We skip -// the precision check for sufficiently large values to avoid the SIGFPE. -static const double kDoublePrecisionCheckMax = DBL_MAX / 1.000000000000001; - -char* numbers_internal::RoundTripDoubleToBuffer(double d, char* buffer) { - // DBL_DIG is 15 for IEEE-754 doubles, which are used on almost all - // platforms these days. Just in case some system exists where DBL_DIG - // is significantly larger -- and risks overflowing our buffer -- we have - // this assert. - static_assert(DBL_DIG < 20, "DBL_DIG is too big"); - - bool full_precision_needed = true; - if (std::abs(d) <= kDoublePrecisionCheckMax) { - int snprintf_result = snprintf(buffer, numbers_internal::kFastToBufferSize, - "%.*g", DBL_DIG, d); - - // The snprintf should never overflow because the buffer is significantly - // larger than the precision we asked for. - assert(snprintf_result > 0 && - snprintf_result < numbers_internal::kFastToBufferSize); - (void)snprintf_result; - - full_precision_needed = strtod(buffer, nullptr) != d; - } - - if (full_precision_needed) { - int snprintf_result = snprintf(buffer, numbers_internal::kFastToBufferSize, - "%.*g", DBL_DIG + 2, d); - - // Should never overflow; see above. - assert(snprintf_result > 0 && - snprintf_result < numbers_internal::kFastToBufferSize); - (void)snprintf_result; - } - return buffer; -} -// This table is used to quickly calculate the base-ten exponent of a given -// float, and then to provide a multiplier to bring that number into the -// range 1-999,999,999, that is, into uint32_t range. Finally, the exp -// std::string is made available so there is one less int-to-std::string conversion -// to be done. - -struct Spec { - double min_range; - double multiplier; - const char expstr[5]; -}; -const Spec neg_exp_table[] = { - {1.4e-45f, 1e+55, "e-45"}, // - {1e-44f, 1e+54, "e-44"}, // - {1e-43f, 1e+53, "e-43"}, // - {1e-42f, 1e+52, "e-42"}, // - {1e-41f, 1e+51, "e-41"}, // - {1e-40f, 1e+50, "e-40"}, // - {1e-39f, 1e+49, "e-39"}, // - {1e-38f, 1e+48, "e-38"}, // - {1e-37f, 1e+47, "e-37"}, // - {1e-36f, 1e+46, "e-36"}, // - {1e-35f, 1e+45, "e-35"}, // - {1e-34f, 1e+44, "e-34"}, // - {1e-33f, 1e+43, "e-33"}, // - {1e-32f, 1e+42, "e-32"}, // - {1e-31f, 1e+41, "e-31"}, // - {1e-30f, 1e+40, "e-30"}, // - {1e-29f, 1e+39, "e-29"}, // - {1e-28f, 1e+38, "e-28"}, // - {1e-27f, 1e+37, "e-27"}, // - {1e-26f, 1e+36, "e-26"}, // - {1e-25f, 1e+35, "e-25"}, // - {1e-24f, 1e+34, "e-24"}, // - {1e-23f, 1e+33, "e-23"}, // - {1e-22f, 1e+32, "e-22"}, // - {1e-21f, 1e+31, "e-21"}, // - {1e-20f, 1e+30, "e-20"}, // - {1e-19f, 1e+29, "e-19"}, // - {1e-18f, 1e+28, "e-18"}, // - {1e-17f, 1e+27, "e-17"}, // - {1e-16f, 1e+26, "e-16"}, // - {1e-15f, 1e+25, "e-15"}, // - {1e-14f, 1e+24, "e-14"}, // - {1e-13f, 1e+23, "e-13"}, // - {1e-12f, 1e+22, "e-12"}, // - {1e-11f, 1e+21, "e-11"}, // - {1e-10f, 1e+20, "e-10"}, // - {1e-09f, 1e+19, "e-09"}, // - {1e-08f, 1e+18, "e-08"}, // - {1e-07f, 1e+17, "e-07"}, // - {1e-06f, 1e+16, "e-06"}, // - {1e-05f, 1e+15, "e-05"}, // - {1e-04f, 1e+14, "e-04"}, // -}; - -const Spec pos_exp_table[] = { - {1e+08f, 1e+02, "e+08"}, // - {1e+09f, 1e+01, "e+09"}, // - {1e+10f, 1e+00, "e+10"}, // - {1e+11f, 1e-01, "e+11"}, // - {1e+12f, 1e-02, "e+12"}, // - {1e+13f, 1e-03, "e+13"}, // - {1e+14f, 1e-04, "e+14"}, // - {1e+15f, 1e-05, "e+15"}, // - {1e+16f, 1e-06, "e+16"}, // - {1e+17f, 1e-07, "e+17"}, // - {1e+18f, 1e-08, "e+18"}, // - {1e+19f, 1e-09, "e+19"}, // - {1e+20f, 1e-10, "e+20"}, // - {1e+21f, 1e-11, "e+21"}, // - {1e+22f, 1e-12, "e+22"}, // - {1e+23f, 1e-13, "e+23"}, // - {1e+24f, 1e-14, "e+24"}, // - {1e+25f, 1e-15, "e+25"}, // - {1e+26f, 1e-16, "e+26"}, // - {1e+27f, 1e-17, "e+27"}, // - {1e+28f, 1e-18, "e+28"}, // - {1e+29f, 1e-19, "e+29"}, // - {1e+30f, 1e-20, "e+30"}, // - {1e+31f, 1e-21, "e+31"}, // - {1e+32f, 1e-22, "e+32"}, // - {1e+33f, 1e-23, "e+33"}, // - {1e+34f, 1e-24, "e+34"}, // - {1e+35f, 1e-25, "e+35"}, // - {1e+36f, 1e-26, "e+36"}, // - {1e+37f, 1e-27, "e+37"}, // - {1e+38f, 1e-28, "e+38"}, // - {1e+39, 1e-29, "e+39"}, // -}; - -struct ExpCompare { - bool operator()(const Spec& spec, double d) const { - return spec.min_range < d; - } -}; - -// Utility routine(s) for RoundTripFloatToBuffer: -// OutputNecessaryDigits takes two 11-digit numbers, whose integer portion -// represents the fractional part of a floating-point number, and outputs a -// number that is in-between them, with the fewest digits possible. For -// instance, given 12345678900 and 12345876900, it would output "0123457". -// When there are multiple final digits that would satisfy this requirement, -// this routine attempts to use a digit that would represent the average of -// lower_double and upper_double. -// -// Although the routine works using integers, all callers use doubles, so -// for their convenience this routine accepts doubles. -static char* OutputNecessaryDigits(double lower_double, double upper_double, - char* out) { - assert(lower_double > 0); - assert(lower_double < upper_double - 10); - assert(upper_double < 100000000000.0); - - // Narrow the range a bit; without this bias, an input of lower=87654320010.0 - // and upper=87654320100.0 would produce an output of 876543201 - // - // We do this in three steps: first, we lower the upper bound and truncate it - // to an integer. Then, we increase the lower bound by exactly the amount we - // just decreased the upper bound by - at that point, the midpoint is exactly - // where it used to be. Then we truncate the lower bound. - - uint64_t upper64 = upper_double - (1.0 / 1024); - double shrink = upper_double - upper64; - uint64_t lower64 = lower_double + shrink; - - // Theory of operation: we convert the lower number to ascii representation, - // two digits at a time. As we go, we remove the same digits from the upper - // number. When we see the upper number does not share those same digits, we - // know we can stop converting. When we stop, the last digit we output is - // taken from the average of upper and lower values, rounded up. - char buf[2]; - uint32_t lodigits = - static_cast(lower64 / 1000000000); // 1,000,000,000 - uint64_t mul64 = lodigits * uint64_t{1000000000}; - - PutTwoDigits(lodigits, out); - out += 2; - if (upper64 - mul64 >= 1000000000) { // digit mismatch! - PutTwoDigits(upper64 / 1000000000, buf); - if (out[-2] != buf[0]) { - out[-2] = '0' + (upper64 + lower64 + 10000000000) / 20000000000; - --out; - } else { - PutTwoDigits((upper64 + lower64 + 1000000000) / 2000000000, out - 2); - } - *out = '\0'; - return out; - } - uint32_t lower = static_cast(lower64 - mul64); - uint32_t upper = static_cast(upper64 - mul64); - - lodigits = lower / 10000000; // 10,000,000 - uint32_t mul = lodigits * 10000000; - PutTwoDigits(lodigits, out); - out += 2; - if (upper - mul >= 10000000) { // digit mismatch! - PutTwoDigits(upper / 10000000, buf); - if (out[-2] != buf[0]) { - out[-2] = '0' + (upper + lower + 100000000) / 200000000; - --out; - } else { - PutTwoDigits((upper + lower + 10000000) / 20000000, out - 2); - } - *out = '\0'; - return out; - } - lower -= mul; - upper -= mul; - - lodigits = lower / 100000; // 100,000 - mul = lodigits * 100000; - PutTwoDigits(lodigits, out); - out += 2; - if (upper - mul >= 100000) { // digit mismatch! - PutTwoDigits(upper / 100000, buf); - if (out[-2] != buf[0]) { - out[-2] = '0' + (upper + lower + 1000000) / 2000000; - --out; - } else { - PutTwoDigits((upper + lower + 100000) / 200000, out - 2); - } - *out = '\0'; - return out; - } - lower -= mul; - upper -= mul; - - lodigits = lower / 1000; - mul = lodigits * 1000; - PutTwoDigits(lodigits, out); - out += 2; - if (upper - mul >= 1000) { // digit mismatch! - PutTwoDigits(upper / 1000, buf); - if (out[-2] != buf[0]) { - out[-2] = '0' + (upper + lower + 10000) / 20000; - --out; - } else { - PutTwoDigits((upper + lower + 1000) / 2000, out - 2); - } - *out = '\0'; - return out; - } - lower -= mul; - upper -= mul; - - PutTwoDigits(lower / 10, out); - out += 2; - PutTwoDigits(upper / 10, buf); - if (out[-2] != buf[0]) { - out[-2] = '0' + (upper + lower + 100) / 200; - --out; - } else { - PutTwoDigits((upper + lower + 10) / 20, out - 2); - } - *out = '\0'; - return out; -} - -// RoundTripFloatToBuffer converts the given float into a std::string which, if -// passed to strtof, will produce the exact same original float. It does this -// by computing the range of possible doubles which map to the given float, and -// then examining the digits of the doubles in that range. If all the doubles -// in the range start with "2.37", then clearly our float does, too. As soon as -// they diverge, only one more digit is needed. -char* numbers_internal::RoundTripFloatToBuffer(float f, char* buffer) { - static_assert(std::numeric_limits::is_iec559, - "IEEE-754/IEC-559 support only"); - - char* out = buffer; // we write data to out, incrementing as we go, but - // FloatToBuffer always returns the address of the buffer - // passed in. - - if (std::isnan(f)) { - strcpy(out, "nan"); // NOLINT(runtime/printf) - return buffer; - } - if (f == 0) { // +0 and -0 are handled here - if (std::signbit(f)) { - strcpy(out, "-0"); // NOLINT(runtime/printf) - } else { - strcpy(out, "0"); // NOLINT(runtime/printf) - } - return buffer; - } - if (f < 0) { - *out++ = '-'; - f = -f; - } - if (std::isinf(f)) { - strcpy(out, "inf"); // NOLINT(runtime/printf) - return buffer; - } - - double next_lower = nextafterf(f, 0.0f); - // For all doubles in the range lower_bound < f < upper_bound, the - // nearest float is f. - double lower_bound = (f + next_lower) * 0.5; - double upper_bound = f + (f - lower_bound); - // Note: because std::nextafter is slow, we calculate upper_bound - // assuming that it is the same distance from f as lower_bound is. - // For exact powers of two, upper_bound is actually twice as far - // from f as lower_bound is, but this turns out not to matter. - - // Most callers pass floats that are either 0 or within the - // range 0.0001 through 100,000,000, so handle those first, - // since they don't need exponential notation. - const Spec* spec = nullptr; - if (f < 1.0) { - if (f >= 0.0001f) { - // for fractional values, we set up the multiplier at the same - // time as we output the leading "0." / "0.0" / "0.00" / "0.000" - double multiplier = 1e+11; - *out++ = '0'; - *out++ = '.'; - if (f < 0.1f) { - multiplier = 1e+12; - *out++ = '0'; - if (f < 0.01f) { - multiplier = 1e+13; - *out++ = '0'; - if (f < 0.001f) { - multiplier = 1e+14; - *out++ = '0'; - } - } - } - OutputNecessaryDigits(lower_bound * multiplier, upper_bound * multiplier, - out); - return buffer; - } - spec = std::lower_bound(std::begin(neg_exp_table), std::end(neg_exp_table), - double{f}, ExpCompare()); - if (spec == std::end(neg_exp_table)) --spec; - } else if (f < 1e8) { - // Handling non-exponential format greater than 1.0 is similar to the above, - // but instead of 0.0 / 0.00 / 0.000, the prefix is simply the truncated - // integer part of f. - int32_t as_int = f; - out = numbers_internal::FastUInt32ToBuffer(as_int, out); - // Easy: if the integer part is within (lower_bound, upper_bound), then we - // are already done. - if (as_int > lower_bound && as_int < upper_bound) { - return buffer; - } - *out++ = '.'; - OutputNecessaryDigits((lower_bound - as_int) * 1e11, - (upper_bound - as_int) * 1e11, out); - return buffer; - } else { - spec = std::lower_bound(std::begin(pos_exp_table), - std::end(pos_exp_table), - double{f}, ExpCompare()); - if (spec == std::end(pos_exp_table)) --spec; - } - // Exponential notation from here on. "spec" was computed using lower_bound, - // which means it's the first spec from the table where min_range is greater - // or equal to f. - // Unfortunately that's not quite what we want; we want a min_range that is - // less or equal. So first thing, if it was greater, back up one entry. - if (spec->min_range > f) --spec; - - // The digits might be "237000123", but we want "2.37000123", - // so we output the digits one character later, and then move the first - // digit back so we can stick the "." in. - char* start = out; - out = OutputNecessaryDigits(lower_bound * spec->multiplier, - upper_bound * spec->multiplier, start + 1); - start[0] = start[1]; - start[1] = '.'; - - // If it turns out there was only one digit output, then back up over the '.' - if (out == &start[2]) --out; - - // Now add the "e+NN" part. - memcpy(out, spec->expstr, 4); - out[4] = '\0'; - return buffer; -} - // Returns the number of leading 0 bits in a 64-bit value. // TODO(jorg): Replace with builtin_clzll if available. // Are we shipping util/bits in absl? -- cgit v1.2.3