numbers.h 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456
  1. // Copyright 2017 The Abseil Authors.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain a copy of the License at
  6. //
  7. // https://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS IS" BASIS,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. //
  15. // -----------------------------------------------------------------------------
  16. // File: numbers.h
  17. // -----------------------------------------------------------------------------
  18. //
  19. // This package contains functions for converting strings to numbers. For
  20. // converting numbers to strings, use `StrCat()` or `StrAppend()` in str_cat.h,
  21. // which automatically detect and convert most number values appropriately.
  22. #ifndef ABSL_STRINGS_NUMBERS_H_
  23. #define ABSL_STRINGS_NUMBERS_H_
  24. #ifdef __SSSE3__
  25. #include <tmmintrin.h>
  26. #endif
  27. #ifdef _MSC_VER
  28. #include <intrin.h>
  29. #endif
  30. #include <cstddef>
  31. #include <cstdint>
  32. #include <cstdlib>
  33. #include <cstring>
  34. #include <ctime>
  35. #include <limits>
  36. #include <string>
  37. #include <type_traits>
  38. #include "absl/base/attributes.h"
  39. #include "absl/base/config.h"
  40. #include "absl/base/internal/endian.h"
  41. #include "absl/base/macros.h"
  42. #include "absl/base/nullability.h"
  43. #include "absl/base/optimization.h"
  44. #include "absl/base/port.h"
  45. #include "absl/numeric/bits.h"
  46. #include "absl/numeric/int128.h"
  47. #include "absl/strings/string_view.h"
  48. namespace absl {
  49. ABSL_NAMESPACE_BEGIN
  50. // SimpleAtoi()
  51. //
  52. // Converts the given string (optionally followed or preceded by ASCII
  53. // whitespace) into an integer value, returning `true` if successful. The string
  54. // must reflect a base-10 integer whose value falls within the range of the
  55. // integer type (optionally preceded by a `+` or `-`). If any errors are
  56. // encountered, this function returns `false`, leaving `out` in an unspecified
  57. // state.
  58. template <typename int_type>
  59. ABSL_MUST_USE_RESULT bool SimpleAtoi(absl::string_view str,
  60. absl::Nonnull<int_type*> out);
  61. // SimpleAtof()
  62. //
  63. // Converts the given string (optionally followed or preceded by ASCII
  64. // whitespace) into a float, which may be rounded on overflow or underflow,
  65. // returning `true` if successful.
  66. // See https://en.cppreference.com/w/c/string/byte/strtof for details about the
  67. // allowed formats for `str`, except SimpleAtof() is locale-independent and will
  68. // always use the "C" locale. If any errors are encountered, this function
  69. // returns `false`, leaving `out` in an unspecified state.
  70. ABSL_MUST_USE_RESULT bool SimpleAtof(absl::string_view str,
  71. absl::Nonnull<float*> out);
  72. // SimpleAtod()
  73. //
  74. // Converts the given string (optionally followed or preceded by ASCII
  75. // whitespace) into a double, which may be rounded on overflow or underflow,
  76. // returning `true` if successful.
  77. // See https://en.cppreference.com/w/c/string/byte/strtof for details about the
  78. // allowed formats for `str`, except SimpleAtod is locale-independent and will
  79. // always use the "C" locale. If any errors are encountered, this function
  80. // returns `false`, leaving `out` in an unspecified state.
  81. ABSL_MUST_USE_RESULT bool SimpleAtod(absl::string_view str,
  82. absl::Nonnull<double*> out);
  83. // SimpleAtob()
  84. //
  85. // Converts the given string into a boolean, returning `true` if successful.
  86. // The following case-insensitive strings are interpreted as boolean `true`:
  87. // "true", "t", "yes", "y", "1". The following case-insensitive strings
  88. // are interpreted as boolean `false`: "false", "f", "no", "n", "0". If any
  89. // errors are encountered, this function returns `false`, leaving `out` in an
  90. // unspecified state.
  91. ABSL_MUST_USE_RESULT bool SimpleAtob(absl::string_view str,
  92. absl::Nonnull<bool*> out);
  93. // SimpleHexAtoi()
  94. //
  95. // Converts a hexadecimal string (optionally followed or preceded by ASCII
  96. // whitespace) to an integer, returning `true` if successful. Only valid base-16
  97. // hexadecimal integers whose value falls within the range of the integer type
  98. // (optionally preceded by a `+` or `-`) can be converted. A valid hexadecimal
  99. // value may include both upper and lowercase character symbols, and may
  100. // optionally include a leading "0x" (or "0X") number prefix, which is ignored
  101. // by this function. If any errors are encountered, this function returns
  102. // `false`, leaving `out` in an unspecified state.
  103. template <typename int_type>
  104. ABSL_MUST_USE_RESULT bool SimpleHexAtoi(absl::string_view str,
  105. absl::Nonnull<int_type*> out);
  106. // Overloads of SimpleHexAtoi() for 128 bit integers.
  107. ABSL_MUST_USE_RESULT inline bool SimpleHexAtoi(
  108. absl::string_view str, absl::Nonnull<absl::int128*> out);
  109. ABSL_MUST_USE_RESULT inline bool SimpleHexAtoi(
  110. absl::string_view str, absl::Nonnull<absl::uint128*> out);
  111. ABSL_NAMESPACE_END
  112. } // namespace absl
  113. // End of public API. Implementation details follow.
  114. namespace absl {
  115. ABSL_NAMESPACE_BEGIN
  116. namespace numbers_internal {
  117. // Digit conversion.
  118. ABSL_DLL extern const char kHexChar[17]; // 0123456789abcdef
  119. ABSL_DLL extern const char
  120. kHexTable[513]; // 000102030405060708090a0b0c0d0e0f1011...
  121. // Writes a two-character representation of 'i' to 'buf'. 'i' must be in the
  122. // range 0 <= i < 100, and buf must have space for two characters. Example:
  123. // char buf[2];
  124. // PutTwoDigits(42, buf);
  125. // // buf[0] == '4'
  126. // // buf[1] == '2'
  127. void PutTwoDigits(uint32_t i, absl::Nonnull<char*> buf);
  128. // safe_strto?() functions for implementing SimpleAtoi()
  129. bool safe_strto32_base(absl::string_view text, absl::Nonnull<int32_t*> value,
  130. int base);
  131. bool safe_strto64_base(absl::string_view text, absl::Nonnull<int64_t*> value,
  132. int base);
  133. bool safe_strto128_base(absl::string_view text,
  134. absl::Nonnull<absl::int128*> value, int base);
  135. bool safe_strtou32_base(absl::string_view text, absl::Nonnull<uint32_t*> value,
  136. int base);
  137. bool safe_strtou64_base(absl::string_view text, absl::Nonnull<uint64_t*> value,
  138. int base);
  139. bool safe_strtou128_base(absl::string_view text,
  140. absl::Nonnull<absl::uint128*> value, int base);
  141. static const int kFastToBufferSize = 32;
  142. static const int kSixDigitsToBufferSize = 16;
  143. template <class T>
  144. std::enable_if_t<!std::is_unsigned<T>::value, bool> IsNegative(const T& v) {
  145. return v < T();
  146. }
  147. template <class T>
  148. std::enable_if_t<std::is_unsigned<T>::value, std::false_type> IsNegative(
  149. const T&) {
  150. // The integer is unsigned, so return a compile-time constant.
  151. // This can help the optimizer avoid having to prove bool to be false later.
  152. return std::false_type();
  153. }
  154. template <class T>
  155. std::enable_if_t<std::is_unsigned<std::decay_t<T>>::value, T&&>
  156. UnsignedAbsoluteValue(T&& v ABSL_ATTRIBUTE_LIFETIME_BOUND) {
  157. // The value is unsigned; just return the original.
  158. return std::forward<T>(v);
  159. }
  160. template <class T>
  161. ABSL_ATTRIBUTE_CONST_FUNCTION
  162. std::enable_if_t<!std::is_unsigned<T>::value, std::make_unsigned_t<T>>
  163. UnsignedAbsoluteValue(T v) {
  164. using U = std::make_unsigned_t<T>;
  165. return IsNegative(v) ? U() - static_cast<U>(v) : static_cast<U>(v);
  166. }
  167. // Returns the number of base-10 digits in the given number.
  168. // Note that this strictly counts digits. It does not count the sign.
  169. // The `initial_digits` parameter is the starting point, which is normally equal
  170. // to 1 because the number of digits in 0 is 1 (a special case).
  171. // However, callers may e.g. wish to change it to 2 to account for the sign.
  172. template <typename T>
  173. std::enable_if_t<std::is_unsigned<T>::value, uint32_t> Base10Digits(
  174. T v, const uint32_t initial_digits = 1) {
  175. uint32_t r = initial_digits;
  176. // If code size becomes an issue, the 'if' stage can be removed for a minor
  177. // performance loss.
  178. for (;;) {
  179. if (ABSL_PREDICT_TRUE(v < 10 * 10)) {
  180. r += (v >= 10);
  181. break;
  182. }
  183. if (ABSL_PREDICT_TRUE(v < 1000 * 10)) {
  184. r += (v >= 1000) + 2;
  185. break;
  186. }
  187. if (ABSL_PREDICT_TRUE(v < 100000 * 10)) {
  188. r += (v >= 100000) + 4;
  189. break;
  190. }
  191. r += 6;
  192. v = static_cast<T>(v / 1000000);
  193. }
  194. return r;
  195. }
  196. template <typename T>
  197. std::enable_if_t<std::is_signed<T>::value, uint32_t> Base10Digits(
  198. T v, uint32_t r = 1) {
  199. // Branchlessly add 1 to account for a minus sign.
  200. r += static_cast<uint32_t>(IsNegative(v));
  201. return Base10Digits(UnsignedAbsoluteValue(v), r);
  202. }
  203. // These functions return the number of base-10 digits, but multiplied by -1 if
  204. // the input itself is negative. This is handy and efficient for later usage,
  205. // since the bitwise complement of the result becomes equal to the number of
  206. // characters required.
  207. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  208. signed char v);
  209. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  210. unsigned char v);
  211. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  212. short v); // NOLINT
  213. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  214. unsigned short v); // NOLINT
  215. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(int v);
  216. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  217. unsigned int v);
  218. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  219. long v); // NOLINT
  220. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  221. unsigned long v); // NOLINT
  222. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  223. long long v); // NOLINT
  224. ABSL_ATTRIBUTE_CONST_FUNCTION int GetNumDigitsOrNegativeIfNegative(
  225. unsigned long long v); // NOLINT
  226. // Helper function for fast formatting of floating-point values.
  227. // The result is the same as printf's "%g", a.k.a. "%.6g"; that is, six
  228. // significant digits are returned, trailing zeros are removed, and numbers
  229. // outside the range 0.0001-999999 are output using scientific notation
  230. // (1.23456e+06). This routine is heavily optimized.
  231. // Required buffer size is `kSixDigitsToBufferSize`.
  232. size_t SixDigitsToBuffer(double d, absl::Nonnull<char*> buffer);
  233. // All of these functions take an output buffer
  234. // as an argument and return a pointer to the last byte they wrote, which is the
  235. // terminating '\0'. At most `kFastToBufferSize` bytes are written.
  236. absl::Nonnull<char*> FastIntToBuffer(int32_t i, absl::Nonnull<char*> buffer);
  237. absl::Nonnull<char*> FastIntToBuffer(uint32_t i, absl::Nonnull<char*> buffer);
  238. absl::Nonnull<char*> FastIntToBuffer(int64_t i, absl::Nonnull<char*> buffer);
  239. absl::Nonnull<char*> FastIntToBuffer(uint64_t i, absl::Nonnull<char*> buffer);
  240. // For enums and integer types that are not an exact match for the types above,
  241. // use templates to call the appropriate one of the four overloads above.
  242. template <typename int_type>
  243. absl::Nonnull<char*> FastIntToBuffer(int_type i, absl::Nonnull<char*> buffer) {
  244. static_assert(sizeof(i) <= 64 / 8,
  245. "FastIntToBuffer works only with 64-bit-or-less integers.");
  246. // TODO(jorg): This signed-ness check is used because it works correctly
  247. // with enums, and it also serves to check that int_type is not a pointer.
  248. // If one day something like std::is_signed<enum E> works, switch to it.
  249. // These conditions are constexpr bools to suppress MSVC warning C4127.
  250. constexpr bool kIsSigned = static_cast<int_type>(1) - 2 < 0;
  251. constexpr bool kUse64Bit = sizeof(i) > 32 / 8;
  252. if (kIsSigned) {
  253. if (kUse64Bit) {
  254. return FastIntToBuffer(static_cast<int64_t>(i), buffer);
  255. } else {
  256. return FastIntToBuffer(static_cast<int32_t>(i), buffer);
  257. }
  258. } else {
  259. if (kUse64Bit) {
  260. return FastIntToBuffer(static_cast<uint64_t>(i), buffer);
  261. } else {
  262. return FastIntToBuffer(static_cast<uint32_t>(i), buffer);
  263. }
  264. }
  265. }
  266. // These functions do NOT add any null-terminator.
  267. // They return a pointer to the beginning of the written string.
  268. // The digit counts provided must *exactly* match the number of base-10 digits
  269. // in the number, or the behavior is undefined.
  270. // (i.e. do NOT count the minus sign, or over- or under-count the digits.)
  271. absl::Nonnull<char*> FastIntToBufferBackward(int32_t i,
  272. absl::Nonnull<char*> buffer_end,
  273. uint32_t exact_digit_count);
  274. absl::Nonnull<char*> FastIntToBufferBackward(uint32_t i,
  275. absl::Nonnull<char*> buffer_end,
  276. uint32_t exact_digit_count);
  277. absl::Nonnull<char*> FastIntToBufferBackward(int64_t i,
  278. absl::Nonnull<char*> buffer_end,
  279. uint32_t exact_digit_count);
  280. absl::Nonnull<char*> FastIntToBufferBackward(uint64_t i,
  281. absl::Nonnull<char*> buffer_end,
  282. uint32_t exact_digit_count);
  283. // For enums and integer types that are not an exact match for the types above,
  284. // use templates to call the appropriate one of the four overloads above.
  285. template <typename int_type>
  286. absl::Nonnull<char*> FastIntToBufferBackward(int_type i,
  287. absl::Nonnull<char*> buffer_end,
  288. uint32_t exact_digit_count) {
  289. static_assert(
  290. sizeof(i) <= 64 / 8,
  291. "FastIntToBufferBackward works only with 64-bit-or-less integers.");
  292. // This signed-ness check is used because it works correctly
  293. // with enums, and it also serves to check that int_type is not a pointer.
  294. // If one day something like std::is_signed<enum E> works, switch to it.
  295. // These conditions are constexpr bools to suppress MSVC warning C4127.
  296. constexpr bool kIsSigned = static_cast<int_type>(1) - 2 < 0;
  297. constexpr bool kUse64Bit = sizeof(i) > 32 / 8;
  298. if (kIsSigned) {
  299. if (kUse64Bit) {
  300. return FastIntToBufferBackward(static_cast<int64_t>(i), buffer_end,
  301. exact_digit_count);
  302. } else {
  303. return FastIntToBufferBackward(static_cast<int32_t>(i), buffer_end,
  304. exact_digit_count);
  305. }
  306. } else {
  307. if (kUse64Bit) {
  308. return FastIntToBufferBackward(static_cast<uint64_t>(i), buffer_end,
  309. exact_digit_count);
  310. } else {
  311. return FastIntToBufferBackward(static_cast<uint32_t>(i), buffer_end,
  312. exact_digit_count);
  313. }
  314. }
  315. }
  316. // Implementation of SimpleAtoi, generalized to support arbitrary base (used
  317. // with base different from 10 elsewhere in Abseil implementation).
  318. template <typename int_type>
  319. ABSL_MUST_USE_RESULT bool safe_strtoi_base(absl::string_view s,
  320. absl::Nonnull<int_type*> out,
  321. int base) {
  322. static_assert(sizeof(*out) == 4 || sizeof(*out) == 8,
  323. "SimpleAtoi works only with 32-bit or 64-bit integers.");
  324. static_assert(!std::is_floating_point<int_type>::value,
  325. "Use SimpleAtof or SimpleAtod instead.");
  326. bool parsed;
  327. // TODO(jorg): This signed-ness check is used because it works correctly
  328. // with enums, and it also serves to check that int_type is not a pointer.
  329. // If one day something like std::is_signed<enum E> works, switch to it.
  330. // These conditions are constexpr bools to suppress MSVC warning C4127.
  331. constexpr bool kIsSigned = static_cast<int_type>(1) - 2 < 0;
  332. constexpr bool kUse64Bit = sizeof(*out) == 64 / 8;
  333. if (kIsSigned) {
  334. if (kUse64Bit) {
  335. int64_t val;
  336. parsed = numbers_internal::safe_strto64_base(s, &val, base);
  337. *out = static_cast<int_type>(val);
  338. } else {
  339. int32_t val;
  340. parsed = numbers_internal::safe_strto32_base(s, &val, base);
  341. *out = static_cast<int_type>(val);
  342. }
  343. } else {
  344. if (kUse64Bit) {
  345. uint64_t val;
  346. parsed = numbers_internal::safe_strtou64_base(s, &val, base);
  347. *out = static_cast<int_type>(val);
  348. } else {
  349. uint32_t val;
  350. parsed = numbers_internal::safe_strtou32_base(s, &val, base);
  351. *out = static_cast<int_type>(val);
  352. }
  353. }
  354. return parsed;
  355. }
  356. // FastHexToBufferZeroPad16()
  357. //
  358. // Outputs `val` into `out` as if by `snprintf(out, 17, "%016x", val)` but
  359. // without the terminating null character. Thus `out` must be of length >= 16.
  360. // Returns the number of non-pad digits of the output (it can never be zero
  361. // since 0 has one digit).
  362. inline size_t FastHexToBufferZeroPad16(uint64_t val, absl::Nonnull<char*> out) {
  363. #ifdef ABSL_INTERNAL_HAVE_SSSE3
  364. uint64_t be = absl::big_endian::FromHost64(val);
  365. const auto kNibbleMask = _mm_set1_epi8(0xf);
  366. const auto kHexDigits = _mm_setr_epi8('0', '1', '2', '3', '4', '5', '6', '7',
  367. '8', '9', 'a', 'b', 'c', 'd', 'e', 'f');
  368. auto v = _mm_loadl_epi64(reinterpret_cast<__m128i*>(&be)); // load lo dword
  369. auto v4 = _mm_srli_epi64(v, 4); // shift 4 right
  370. auto il = _mm_unpacklo_epi8(v4, v); // interleave bytes
  371. auto m = _mm_and_si128(il, kNibbleMask); // mask out nibbles
  372. auto hexchars = _mm_shuffle_epi8(kHexDigits, m); // hex chars
  373. _mm_storeu_si128(reinterpret_cast<__m128i*>(out), hexchars);
  374. #else
  375. for (int i = 0; i < 8; ++i) {
  376. auto byte = (val >> (56 - 8 * i)) & 0xFF;
  377. auto* hex = &absl::numbers_internal::kHexTable[byte * 2];
  378. std::memcpy(out + 2 * i, hex, 2);
  379. }
  380. #endif
  381. // | 0x1 so that even 0 has 1 digit.
  382. return 16 - static_cast<size_t>(countl_zero(val | 0x1) / 4);
  383. }
  384. } // namespace numbers_internal
  385. template <typename int_type>
  386. ABSL_MUST_USE_RESULT bool SimpleAtoi(absl::string_view str,
  387. absl::Nonnull<int_type*> out) {
  388. return numbers_internal::safe_strtoi_base(str, out, 10);
  389. }
  390. ABSL_MUST_USE_RESULT inline bool SimpleAtoi(absl::string_view str,
  391. absl::Nonnull<absl::int128*> out) {
  392. return numbers_internal::safe_strto128_base(str, out, 10);
  393. }
  394. ABSL_MUST_USE_RESULT inline bool SimpleAtoi(absl::string_view str,
  395. absl::Nonnull<absl::uint128*> out) {
  396. return numbers_internal::safe_strtou128_base(str, out, 10);
  397. }
  398. template <typename int_type>
  399. ABSL_MUST_USE_RESULT bool SimpleHexAtoi(absl::string_view str,
  400. absl::Nonnull<int_type*> out) {
  401. return numbers_internal::safe_strtoi_base(str, out, 16);
  402. }
  403. ABSL_MUST_USE_RESULT inline bool SimpleHexAtoi(
  404. absl::string_view str, absl::Nonnull<absl::int128*> out) {
  405. return numbers_internal::safe_strto128_base(str, out, 16);
  406. }
  407. ABSL_MUST_USE_RESULT inline bool SimpleHexAtoi(
  408. absl::string_view str, absl::Nonnull<absl::uint128*> out) {
  409. return numbers_internal::safe_strtou128_base(str, out, 16);
  410. }
  411. ABSL_NAMESPACE_END
  412. } // namespace absl
  413. #endif // ABSL_STRINGS_NUMBERS_H_