string_number_conversions_internal.h 9.2 KB

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