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