1// Primitive numeric conversions (to_chars and from_chars) -*- C++ -*-
2
3// Copyright (C) 2017-2019 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file include/charconv
26 *  This is a Standard C++ Library header.
27 */
28
29#ifndef _GLIBCXX_CHARCONV
30#define _GLIBCXX_CHARCONV 1
31
32#pragma GCC system_header
33
34#if __cplusplus >= 201402L
35
36#include <type_traits>
37#include <limits>
38#include <cctype>
39#include <bits/error_constants.h> // for std::errc
40
41namespace std _GLIBCXX_VISIBILITY(default)
42{
43_GLIBCXX_BEGIN_NAMESPACE_VERSION
44
45  /// Result type of std::to_chars
46  struct to_chars_result
47  {
48    char* ptr;
49    errc ec;
50  };
51
52  /// Result type of std::from_chars
53  struct from_chars_result
54  {
55    const char* ptr;
56    errc ec;
57  };
58
59namespace __detail
60{
61  template<typename _Tp, typename... _Types>
62    using __is_one_of = __or_<is_same<_Tp, _Types>...>;
63
64  template<typename _Tp>
65    using __is_int_to_chars_type = __and_<is_integral<_Tp>,
66	  __not_<__is_one_of<_Tp, bool, char16_t, char32_t
67#if _GLIBCXX_USE_WCHAR_T
68	  , wchar_t
69#endif
70#if _GLIBCXX_USE_CHAR8_T
71	  , char8_t
72#endif
73	    >>>;
74
75  template<typename _Tp>
76    using __integer_to_chars_result_type
77      = enable_if_t<__is_int_to_chars_type<_Tp>::value, to_chars_result>;
78
79  template<typename _Tp>
80    using __unsigned_least_t
81      = conditional_t<(sizeof(_Tp) <= sizeof(int)), unsigned int,
82	conditional_t<(sizeof(_Tp) <= sizeof(long)), unsigned long,
83	conditional_t<(sizeof(_Tp) <= sizeof(long long)), unsigned long long,
84#if _GLIBCXX_USE_INT128
85	conditional_t<(sizeof(_Tp) <= sizeof(__int128)), unsigned __int128,
86#endif
87	void
88#if _GLIBCXX_USE_INT128
89	>
90#endif
91	>>>;
92
93  // Generic implementation for arbitrary bases.
94  template<typename _Tp>
95    constexpr unsigned
96    __to_chars_len(_Tp __value, int __base = 10) noexcept
97    {
98      static_assert(is_integral<_Tp>::value, "implementation bug");
99      static_assert(is_unsigned<_Tp>::value, "implementation bug");
100
101      unsigned __n = 1;
102      const int __b2 = __base  * __base;
103      const int __b3 = __b2 * __base;
104      const int __b4 = __b3 * __base;
105      for (;;)
106	{
107	  if (__value < __base) return __n;
108	  if (__value < __b2) return __n + 1;
109	  if (__value < __b3) return __n + 2;
110	  if (__value < __b4) return __n + 3;
111	  __value /= (unsigned)__b4;
112	  __n += 4;
113	}
114    }
115
116  template<typename _Tp>
117    constexpr unsigned
118    __to_chars_len_2(_Tp __value) noexcept
119    {
120      static_assert(is_integral<_Tp>::value, "implementation bug");
121      static_assert(is_unsigned<_Tp>::value, "implementation bug");
122
123      constexpr size_t __nbits = __CHAR_BIT__ * sizeof(_Tp);
124
125      // N.B. __builtin_clzll is undefined if __value == 0, but std::to_chars
126      // handles zero values directly.
127
128      // For sizeof(_Tp) > 1 this is an order of magnitude faster than
129      // the generic __to_chars_len.
130      return __nbits
131	- (__builtin_clzll(__value)
132	    - ((__CHAR_BIT__ * sizeof(long long)) - __nbits));
133    }
134
135  template<typename _Tp>
136    constexpr unsigned
137    __to_chars_len_8(_Tp __value) noexcept
138    {
139      static_assert(is_integral<_Tp>::value, "implementation bug");
140      static_assert(is_unsigned<_Tp>::value, "implementation bug");
141
142      constexpr size_t __nbits = __CHAR_BIT__ * sizeof(_Tp);
143
144      if _GLIBCXX17_CONSTEXPR (__nbits <= 16)
145	{
146	  return __value > 077777u ? 6u
147	    : __value > 07777u ? 5u
148	    : __value > 0777u ? 4u
149	    : __value > 077u ? 3u
150	    : __value > 07u ? 2u
151	    : 1u;
152	}
153      else
154	return __to_chars_len(__value, 8);
155    }
156
157  // Generic implementation for arbitrary bases.
158  template<typename _Tp>
159    to_chars_result
160    __to_chars(char* __first, char* __last, _Tp __val, int __base) noexcept
161    {
162      static_assert(is_integral<_Tp>::value, "implementation bug");
163      static_assert(is_unsigned<_Tp>::value, "implementation bug");
164
165      to_chars_result __res;
166
167      const unsigned __len = __to_chars_len(__val, __base);
168
169      if (__builtin_expect((__last - __first) < __len, 0))
170	{
171	  __res.ptr = __last;
172	  __res.ec = errc::value_too_large;
173	  return __res;
174	}
175
176      unsigned __pos = __len - 1;
177
178      static constexpr char __digits[]
179	= "0123456789abcdefghijklmnopqrstuvwxyz";
180
181      while (__val >= __base)
182	{
183	  auto const __quo = __val / __base;
184	  auto const __rem = __val % __base;
185	  __first[__pos--] = __digits[__rem];
186	  __val = __quo;
187	}
188      *__first = __digits[__val];
189
190      __res.ptr = __first + __len;
191      __res.ec = {};
192      return __res;
193    }
194
195  template<typename _Tp>
196    __integer_to_chars_result_type<_Tp>
197    __to_chars_16(char* __first, char* __last, _Tp __val) noexcept
198    {
199      static_assert(is_integral<_Tp>::value, "implementation bug");
200      static_assert(is_unsigned<_Tp>::value, "implementation bug");
201
202      to_chars_result __res;
203
204      const unsigned __len = __to_chars_len(__val, 0x10);
205
206      if (__builtin_expect((__last - __first) < __len, 0))
207	{
208	  __res.ptr = __last;
209	  __res.ec = errc::value_too_large;
210	  return __res;
211	}
212
213      static constexpr char __digits[513] =
214	"000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f"
215	"202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f"
216	"404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f"
217	"606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f"
218	"808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9f"
219	"a0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebf"
220	"c0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedf"
221	"e0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff";
222      unsigned __pos = __len - 1;
223      while (__val >= 0x100)
224	{
225	  auto const __num = (__val % 0x100) * 2;
226	  __val /= 0x100;
227	  __first[__pos] = __digits[__num + 1];
228	  __first[__pos - 1] = __digits[__num];
229	  __pos -= 2;
230	}
231      if (__val >= 0x10)
232	{
233	  auto const __num = __val * 2;
234	  __first[__pos] = __digits[__num + 1];
235	  __first[__pos - 1] = __digits[__num];
236	}
237      else
238	__first[__pos] = "0123456789abcdef"[__val];
239      __res.ptr = __first + __len;
240      __res.ec = {};
241      return __res;
242    }
243
244  template<typename _Tp>
245    __integer_to_chars_result_type<_Tp>
246    __to_chars_10(char* __first, char* __last, _Tp __val) noexcept
247    {
248      static_assert(is_integral<_Tp>::value, "implementation bug");
249      static_assert(is_unsigned<_Tp>::value, "implementation bug");
250
251      to_chars_result __res;
252
253      const unsigned __len = __to_chars_len(__val, 10);
254
255      if (__builtin_expect((__last - __first) < __len, 0))
256	{
257	  __res.ptr = __last;
258	  __res.ec = errc::value_too_large;
259	  return __res;
260	}
261
262      static constexpr char __digits[201] =
263	"0001020304050607080910111213141516171819"
264	"2021222324252627282930313233343536373839"
265	"4041424344454647484950515253545556575859"
266	"6061626364656667686970717273747576777879"
267	"8081828384858687888990919293949596979899";
268      unsigned __pos = __len - 1;
269      while (__val >= 100)
270	{
271	  auto const __num = (__val % 100) * 2;
272	  __val /= 100;
273	  __first[__pos] = __digits[__num + 1];
274	  __first[__pos - 1] = __digits[__num];
275	  __pos -= 2;
276	}
277      if (__val >= 10)
278	{
279	  auto const __num = __val * 2;
280	  __first[__pos] = __digits[__num + 1];
281	  __first[__pos - 1] = __digits[__num];
282	}
283      else
284	__first[__pos] = '0' + __val;
285      __res.ptr = __first + __len;
286      __res.ec = {};
287      return __res;
288    }
289
290  template<typename _Tp>
291    __integer_to_chars_result_type<_Tp>
292    __to_chars_8(char* __first, char* __last, _Tp __val) noexcept
293    {
294      static_assert(is_integral<_Tp>::value, "implementation bug");
295      static_assert(is_unsigned<_Tp>::value, "implementation bug");
296
297      to_chars_result __res;
298
299      const unsigned __len = __to_chars_len_8(__val);
300
301      if (__builtin_expect((__last - __first) < __len, 0))
302	{
303	  __res.ptr = __last;
304	  __res.ec = errc::value_too_large;
305	  return __res;
306	}
307
308      static constexpr char __digits[129] =
309	"00010203040506071011121314151617"
310	"20212223242526273031323334353637"
311	"40414243444546475051525354555657"
312	"60616263646566677071727374757677";
313      unsigned __pos = __len - 1;
314      while (__val >= 0100)
315	{
316	  auto const __num = (__val % 0100) * 2;
317	  __val /= 0100;
318	  __first[__pos] = __digits[__num + 1];
319	  __first[__pos - 1] = __digits[__num];
320	  __pos -= 2;
321	}
322      if (__val >= 010)
323	{
324	  auto const __num = __val * 2;
325	  __first[__pos] = __digits[__num + 1];
326	  __first[__pos - 1] = __digits[__num];
327	}
328      else
329	__first[__pos] = '0' + __val;
330      __res.ptr = __first + __len;
331      __res.ec = {};
332      return __res;
333    }
334
335  template<typename _Tp>
336    __integer_to_chars_result_type<_Tp>
337    __to_chars_2(char* __first, char* __last, _Tp __val) noexcept
338    {
339      static_assert(is_integral<_Tp>::value, "implementation bug");
340      static_assert(is_unsigned<_Tp>::value, "implementation bug");
341
342      to_chars_result __res;
343
344      const unsigned __len = __to_chars_len_2(__val);
345
346      if (__builtin_expect((__last - __first) < __len, 0))
347	{
348	  __res.ptr = __last;
349	  __res.ec = errc::value_too_large;
350	  return __res;
351	}
352
353      unsigned __pos = __len - 1;
354
355      while (__pos)
356	{
357	  __first[__pos--] = '0' + (__val & 1);
358	  __val >>= 1;
359	}
360      *__first = '0' + (__val & 1);
361
362      __res.ptr = __first + __len;
363      __res.ec = {};
364      return __res;
365    }
366
367} // namespace __detail
368
369  template<typename _Tp>
370    __detail::__integer_to_chars_result_type<_Tp>
371    to_chars(char* __first, char* __last, _Tp __value, int __base = 10)
372    {
373      __glibcxx_assert(2 <= __base && __base <= 36);
374
375      using _Up = __detail::__unsigned_least_t<_Tp>;
376      _Up __unsigned_val = __value;
377
378      if (__value == 0 && __first != __last)
379	{
380	  *__first = '0';
381	  return { __first + 1, errc{} };
382	}
383
384      if _GLIBCXX17_CONSTEXPR (std::is_signed<_Tp>::value)
385	if (__value < 0)
386	  {
387	    if (__builtin_expect(__first != __last, 1))
388	      *__first++ = '-';
389	    __unsigned_val = _Up(~__value) + _Up(1);
390	  }
391
392      switch (__base)
393      {
394      case 16:
395	return __detail::__to_chars_16(__first, __last, __unsigned_val);
396      case 10:
397	return __detail::__to_chars_10(__first, __last, __unsigned_val);
398      case 8:
399	return __detail::__to_chars_8(__first, __last, __unsigned_val);
400      case 2:
401	return __detail::__to_chars_2(__first, __last, __unsigned_val);
402      default:
403	return __detail::__to_chars(__first, __last, __unsigned_val, __base);
404      }
405    }
406
407namespace __detail
408{
409  template<typename _Tp>
410    bool
411    __raise_and_add(_Tp& __val, int __base, unsigned char __c)
412    {
413      if (__builtin_mul_overflow(__val, __base, &__val)
414	  || __builtin_add_overflow(__val, __c, &__val))
415	return false;
416      return true;
417    }
418
419  /// std::from_chars implementation for integers in base 2.
420  template<typename _Tp>
421    bool
422    __from_chars_binary(const char*& __first, const char* __last, _Tp& __val)
423    {
424      static_assert(is_integral<_Tp>::value, "implementation bug");
425      static_assert(is_unsigned<_Tp>::value, "implementation bug");
426
427      const ptrdiff_t __len = __last - __first;
428      int __i = 0;
429      while (__i < __len)
430	{
431	  const unsigned char __c = (unsigned)__first[__i] - '0';
432	  if (__c < 2)
433	    __val = (__val << 1) | __c;
434	  else
435	    break;
436	  __i++;
437	}
438      __first += __i;
439      return __i <= (sizeof(_Tp) * __CHAR_BIT__);
440    }
441
442  /// std::from_chars implementation for integers in bases 3 to 10.
443  template<typename _Tp>
444    bool
445    __from_chars_digit(const char*& __first, const char* __last, _Tp& __val,
446		       int __base)
447    {
448      static_assert(is_integral<_Tp>::value, "implementation bug");
449      static_assert(is_unsigned<_Tp>::value, "implementation bug");
450
451      auto __matches = [__base](char __c) {
452	  return '0' <= __c && __c <= ('0' + (__base - 1));
453      };
454
455      while (__first != __last)
456	{
457	  const char __c = *__first;
458	  if (__matches(__c))
459	  {
460	    if (!__raise_and_add(__val, __base, __c - '0'))
461	      {
462		while (++__first != __last && __matches(*__first))
463		  ;
464		return false;
465	      }
466	    __first++;
467	  }
468	  else
469	    return true;
470	}
471      return true;
472    }
473
474  constexpr unsigned char
475  __from_chars_alpha_to_num(char __c)
476  {
477    switch (__c)
478    {
479    case 'a':
480    case 'A':
481      return 10;
482    case 'b':
483    case 'B':
484      return 11;
485    case 'c':
486    case 'C':
487      return 12;
488    case 'd':
489    case 'D':
490      return 13;
491    case 'e':
492    case 'E':
493      return 14;
494    case 'f':
495    case 'F':
496      return 15;
497    case 'g':
498    case 'G':
499      return 16;
500    case 'h':
501    case 'H':
502      return 17;
503    case 'i':
504    case 'I':
505      return 18;
506    case 'j':
507    case 'J':
508      return 19;
509    case 'k':
510    case 'K':
511      return 20;
512    case 'l':
513    case 'L':
514      return 21;
515    case 'm':
516    case 'M':
517      return 22;
518    case 'n':
519    case 'N':
520      return 23;
521    case 'o':
522    case 'O':
523      return 24;
524    case 'p':
525    case 'P':
526      return 25;
527    case 'q':
528    case 'Q':
529      return 26;
530    case 'r':
531    case 'R':
532      return 27;
533    case 's':
534    case 'S':
535      return 28;
536    case 't':
537    case 'T':
538      return 29;
539    case 'u':
540    case 'U':
541      return 30;
542    case 'v':
543    case 'V':
544      return 31;
545    case 'w':
546    case 'W':
547      return 32;
548    case 'x':
549    case 'X':
550      return 33;
551    case 'y':
552    case 'Y':
553      return 34;
554    case 'z':
555    case 'Z':
556      return 35;
557    }
558    return std::numeric_limits<unsigned char>::max();
559  }
560
561  /// std::from_chars implementation for integers in bases 11 to 26.
562  template<typename _Tp>
563    bool
564    __from_chars_alnum(const char*& __first, const char* __last, _Tp& __val,
565		       int __base)
566    {
567      bool __valid = true;
568      while (__first != __last)
569	{
570	  unsigned char __c = *__first;
571	  if (std::isdigit(__c))
572	    __c -= '0';
573	  else
574	    {
575	      __c = __from_chars_alpha_to_num(__c);
576	      if (__c >= __base)
577		break;
578	    }
579
580	  if (__builtin_expect(__valid, 1))
581	    __valid = __raise_and_add(__val, __base, __c);
582	  __first++;
583	}
584      return __valid;
585    }
586
587  template<typename _Tp>
588    using __integer_from_chars_result_type
589      = enable_if_t<__is_int_to_chars_type<_Tp>::value, from_chars_result>;
590
591} // namespace __detail
592
593  /// std::from_chars for integral types.
594  template<typename _Tp>
595    __detail::__integer_from_chars_result_type<_Tp>
596    from_chars(const char* __first, const char* __last, _Tp& __value,
597	       int __base = 10)
598    {
599      __glibcxx_assert(2 <= __base && __base <= 36);
600
601      from_chars_result __res{__first, {}};
602
603      int __sign = 1;
604      if _GLIBCXX17_CONSTEXPR (std::is_signed<_Tp>::value)
605	if (__first != __last && *__first == '-')
606	  {
607	    __sign = -1;
608	    ++__first;
609	  }
610
611      using _Up = __detail::__unsigned_least_t<_Tp>;
612      _Up __val = 0;
613
614      const auto __start = __first;
615      bool __valid;
616      if (__base == 2)
617	__valid = __detail::__from_chars_binary(__first, __last, __val);
618      else if (__base <= 10)
619	__valid = __detail::__from_chars_digit(__first, __last, __val, __base);
620      else
621	__valid = __detail::__from_chars_alnum(__first, __last, __val, __base);
622
623      if (__builtin_expect(__first == __start, 0))
624	__res.ec = errc::invalid_argument;
625      else
626	{
627	  __res.ptr = __first;
628	  if (!__valid)
629	    __res.ec = errc::result_out_of_range;
630	  else
631	    {
632	      if _GLIBCXX17_CONSTEXPR (std::is_signed<_Tp>::value)
633		{
634		  _Tp __tmp;
635		  if (__builtin_mul_overflow(__val, __sign, &__tmp))
636		    __res.ec = errc::result_out_of_range;
637		  else
638		    __value = __tmp;
639		}
640	      else
641		{
642		  if _GLIBCXX17_CONSTEXPR
643		    (numeric_limits<_Up>::max() > numeric_limits<_Tp>::max())
644		    {
645		      if (__val > numeric_limits<_Tp>::max())
646			__res.ec = errc::result_out_of_range;
647		      else
648			__value = __val;
649		    }
650		  else
651		    __value = __val;
652		}
653	    }
654	}
655      return __res;
656    }
657
658_GLIBCXX_END_NAMESPACE_VERSION
659} // namespace std
660#endif // C++14
661#endif // _GLIBCXX_CHARCONV
662