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