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 "base/third_party/double_conversion/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>
IntToStringT(INT value)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>
CharToDigit(CHAR c)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>
Invoke(Iter begin,Iter end)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:
CheckBounds(Number value,uint8_t new_digit)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 }
Increment(Number lhs,uint8_t rhs)138 static Number Increment(Number lhs, uint8_t rhs) { return lhs + rhs; }
139 };
140
141 class Negative : public Base<Negative> {
142 public:
CheckBounds(Number value,uint8_t new_digit)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 }
Increment(Number lhs,uint8_t rhs)150 static Number Increment(Number lhs, uint8_t rhs) { return lhs - rhs; }
151 };
152 };
153
154 template <typename Number, int kBase, typename CharT>
StringToNumber(BasicStringPiece<CharT> input)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>
StringToIntImpl(T input,VALUE & output)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>
HexStringToIntImpl(T input,VALUE & output)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*
GetDoubleToStringConverter()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>
ToString(const typename StringT::value_type * data,size_t size)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>
ToString(const CharT * data,size_t size)218 StringT ToString(const CharT* data, size_t size) {
219 return StringT(data, data + size);
220 }
221
222 template <typename StringT>
DoubleToStringT(double value)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>
StringToDoubleImpl(STRING input,const CHAR * data,double & output)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>
HexStringToByteContainer(StringPiece input,OutIter output)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_
280