string_number_conversions_internal.h (8917B)
1 // Copyright 2020 The Chromium Authors 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_STRINGS_STRING_NUMBER_CONVERSIONS_INTERNAL_H_ 6 #define BASE_STRINGS_STRING_NUMBER_CONVERSIONS_INTERNAL_H_ 7 8 #include <errno.h> 9 #include <stdlib.h> 10 11 #include <limits> 12 13 #include "base/check.h" 14 #include "base/logging.h" 15 #include "base/numerics/safe_math.h" 16 #include "base/strings/string_util.h" 17 #include "double-conversion/double-conversion.h" 18 #include "third_party/abseil-cpp/absl/types/optional.h" 19 20 namespace base { 21 22 namespace internal { 23 24 template <typename STR, typename INT> 25 static STR IntToStringT(INT value) { 26 // log10(2) ~= 0.3 bytes needed per bit or per byte log10(2**8) ~= 2.4. 27 // So round up to allocate 3 output characters per byte, plus 1 for '-'. 28 const size_t kOutputBufSize = 29 3 * sizeof(INT) + std::numeric_limits<INT>::is_signed; 30 31 // Create the string in a temporary buffer, write it back to front, and 32 // then return the substr of what we ended up using. 33 using CHR = typename STR::value_type; 34 CHR outbuf[kOutputBufSize]; 35 36 // The ValueOrDie call below can never fail, because UnsignedAbs is valid 37 // for all valid inputs. 38 std::make_unsigned_t<INT> res = 39 CheckedNumeric<INT>(value).UnsignedAbs().ValueOrDie(); 40 41 CHR* end = outbuf + kOutputBufSize; 42 CHR* i = end; 43 do { 44 --i; 45 DCHECK(i != outbuf); 46 *i = static_cast<CHR>((res % 10) + '0'); 47 res /= 10; 48 } while (res != 0); 49 if (IsValueNegative(value)) { 50 --i; 51 DCHECK(i != outbuf); 52 *i = static_cast<CHR>('-'); 53 } 54 return STR(i, end); 55 } 56 57 // Utility to convert a character to a digit in a given base 58 template <int BASE, typename CHAR> 59 absl::optional<uint8_t> CharToDigit(CHAR c) { 60 static_assert(1 <= BASE && BASE <= 36, "BASE needs to be in [1, 36]"); 61 if (c >= '0' && c < '0' + std::min(BASE, 10)) 62 return static_cast<uint8_t>(c - '0'); 63 64 if (c >= 'a' && c < 'a' + BASE - 10) 65 return static_cast<uint8_t>(c - 'a' + 10); 66 67 if (c >= 'A' && c < 'A' + BASE - 10) 68 return static_cast<uint8_t>(c - 'A' + 10); 69 70 return absl::nullopt; 71 } 72 73 template <typename Number, int kBase> 74 class StringToNumberParser { 75 public: 76 struct Result { 77 Number value = 0; 78 bool valid = false; 79 }; 80 81 static constexpr Number kMin = std::numeric_limits<Number>::min(); 82 static constexpr Number kMax = std::numeric_limits<Number>::max(); 83 84 // Sign provides: 85 // - a static function, CheckBounds, that determines whether the next digit 86 // causes an overflow/underflow 87 // - a static function, Increment, that appends the next digit appropriately 88 // according to the sign of the number being parsed. 89 template <typename Sign> 90 class Base { 91 public: 92 template <typename Iter> 93 static Result Invoke(Iter begin, Iter end) { 94 Number value = 0; 95 96 if (begin == end) { 97 return {value, false}; 98 } 99 100 // Note: no performance difference was found when using template 101 // specialization to remove this check in bases other than 16 102 if (kBase == 16 && end - begin > 2 && *begin == '0' && 103 (*(begin + 1) == 'x' || *(begin + 1) == 'X')) { 104 begin += 2; 105 } 106 107 for (Iter current = begin; current != end; ++current) { 108 absl::optional<uint8_t> new_digit = CharToDigit<kBase>(*current); 109 110 if (!new_digit) { 111 return {value, false}; 112 } 113 114 if (current != begin) { 115 Result result = Sign::CheckBounds(value, *new_digit); 116 if (!result.valid) 117 return result; 118 119 value *= kBase; 120 } 121 122 value = Sign::Increment(value, *new_digit); 123 } 124 return {value, true}; 125 } 126 }; 127 128 class Positive : public Base<Positive> { 129 public: 130 static Result CheckBounds(Number value, uint8_t new_digit) { 131 if (value > static_cast<Number>(kMax / kBase) || 132 (value == static_cast<Number>(kMax / kBase) && 133 new_digit > kMax % kBase)) { 134 return {kMax, false}; 135 } 136 return {value, true}; 137 } 138 static Number Increment(Number lhs, uint8_t rhs) { return lhs + rhs; } 139 }; 140 141 class Negative : public Base<Negative> { 142 public: 143 static Result CheckBounds(Number value, uint8_t new_digit) { 144 if (value < kMin / kBase || 145 (value == kMin / kBase && new_digit > 0 - kMin % kBase)) { 146 return {kMin, false}; 147 } 148 return {value, true}; 149 } 150 static Number Increment(Number lhs, uint8_t rhs) { return lhs - rhs; } 151 }; 152 }; 153 154 template <typename Number, int kBase, typename CharT> 155 auto StringToNumber(BasicStringPiece<CharT> input) { 156 using Parser = StringToNumberParser<Number, kBase>; 157 using Result = typename Parser::Result; 158 159 bool has_leading_whitespace = false; 160 auto begin = input.begin(); 161 auto end = input.end(); 162 163 while (begin != end && IsAsciiWhitespace(*begin)) { 164 has_leading_whitespace = true; 165 ++begin; 166 } 167 168 if (begin != end && *begin == '-') { 169 if (!std::numeric_limits<Number>::is_signed) { 170 return Result{0, false}; 171 } 172 173 Result result = Parser::Negative::Invoke(begin + 1, end); 174 result.valid &= !has_leading_whitespace; 175 return result; 176 } 177 178 if (begin != end && *begin == '+') { 179 ++begin; 180 } 181 182 Result result = Parser::Positive::Invoke(begin, end); 183 result.valid &= !has_leading_whitespace; 184 return result; 185 } 186 187 template <typename T, typename VALUE, typename CharT = typename T::value_type> 188 bool StringToIntImpl(T input, VALUE& output) { 189 auto result = StringToNumber<VALUE, 10, CharT>(input); 190 output = result.value; 191 return result.valid; 192 } 193 194 template <typename T, typename VALUE, typename CharT = typename T::value_type> 195 bool HexStringToIntImpl(T input, VALUE& output) { 196 auto result = StringToNumber<VALUE, 16, CharT>(input); 197 output = result.value; 198 return result.valid; 199 } 200 201 static const double_conversion::DoubleToStringConverter* 202 GetDoubleToStringConverter() { 203 static double_conversion::DoubleToStringConverter converter( 204 double_conversion::DoubleToStringConverter::EMIT_POSITIVE_EXPONENT_SIGN, 205 nullptr, nullptr, 'e', -6, 12, 0, 0); 206 return &converter; 207 } 208 209 // Converts a given (data, size) pair to a desired string type. For 210 // performance reasons, this dispatches to a different constructor if the 211 // passed-in data matches the string's value_type. 212 template <typename StringT> 213 StringT ToString(const typename StringT::value_type* data, size_t size) { 214 return StringT(data, size); 215 } 216 217 template <typename StringT, typename CharT> 218 StringT ToString(const CharT* data, size_t size) { 219 return StringT(data, data + size); 220 } 221 222 template <typename StringT> 223 StringT DoubleToStringT(double value) { 224 char buffer[32]; 225 double_conversion::StringBuilder builder(buffer, sizeof(buffer)); 226 GetDoubleToStringConverter()->ToShortest(value, &builder); 227 return ToString<StringT>(buffer, static_cast<size_t>(builder.position())); 228 } 229 230 template <typename STRING, typename CHAR> 231 bool StringToDoubleImpl(STRING input, const CHAR* data, double& output) { 232 static double_conversion::StringToDoubleConverter converter( 233 double_conversion::StringToDoubleConverter::ALLOW_LEADING_SPACES | 234 double_conversion::StringToDoubleConverter::ALLOW_TRAILING_JUNK, 235 0.0, 0, nullptr, nullptr); 236 237 int processed_characters_count; 238 output = converter.StringToDouble(data, checked_cast<int>(input.size()), 239 &processed_characters_count); 240 241 // Cases to return false: 242 // - If the input string is empty, there was nothing to parse. 243 // - If the value saturated to HUGE_VAL. 244 // - If the entire string was not processed, there are either characters 245 // remaining in the string after a parsed number, or the string does not 246 // begin with a parseable number. 247 // - If the first character is a space, there was leading whitespace. Note 248 // that this checks using IsWhitespace(), which behaves differently for 249 // wide and narrow characters -- that is intentional and matches the 250 // behavior of the double_conversion library's whitespace-skipping 251 // algorithm. 252 return !input.empty() && output != HUGE_VAL && output != -HUGE_VAL && 253 static_cast<size_t>(processed_characters_count) == input.size() && 254 !IsWhitespace(input[0]); 255 } 256 257 template <typename Char, typename OutIter> 258 static bool HexStringToByteContainer(StringPiece input, OutIter output) { 259 size_t count = input.size(); 260 if (count == 0 || (count % 2) != 0) 261 return false; 262 for (uintptr_t i = 0; i < count / 2; ++i) { 263 // most significant 4 bits 264 absl::optional<uint8_t> msb = CharToDigit<16>(input[i * 2]); 265 // least significant 4 bits 266 absl::optional<uint8_t> lsb = CharToDigit<16>(input[i * 2 + 1]); 267 if (!msb || !lsb) { 268 return false; 269 } 270 *(output++) = static_cast<Char>((*msb << 4) | *lsb); 271 } 272 return true; 273 } 274 275 } // namespace internal 276 277 } // namespace base 278 279 #endif // BASE_STRINGS_STRING_NUMBER_CONVERSIONS_INTERNAL_H_