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      ptrdiff_t __i = 0;
429      while (__i < __len && __first[__i] == '0')
430	++__i;
431      const ptrdiff_t __leading_zeroes = __i;
432
433      while (__i < __len)
434	{
435	  const unsigned char __c = (unsigned)__first[__i] - '0';
436	  if (__c < 2)
437	    __val = (__val << 1) | __c;
438	  else
439	    break;
440	  __i++;
441	}
442      __first += __i;
443      return (__i - __leading_zeroes) <= (sizeof(_Tp) * __CHAR_BIT__);
444    }
445
446  /// std::from_chars implementation for integers in bases 3 to 10.
447  template<typename _Tp>
448    bool
449    __from_chars_digit(const char*& __first, const char* __last, _Tp& __val,
450		       int __base)
451    {
452      static_assert(is_integral<_Tp>::value, "implementation bug");
453      static_assert(is_unsigned<_Tp>::value, "implementation bug");
454
455      auto __matches = [__base](char __c) {
456	  return '0' <= __c && __c <= ('0' + (__base - 1));
457      };
458
459      while (__first != __last)
460	{
461	  const char __c = *__first;
462	  if (__matches(__c))
463	  {
464	    if (!__raise_and_add(__val, __base, __c - '0'))
465	      {
466		while (++__first != __last && __matches(*__first))
467		  ;
468		return false;
469	      }
470	    __first++;
471	  }
472	  else
473	    return true;
474	}
475      return true;
476    }
477
478  constexpr unsigned char
479  __from_chars_alpha_to_num(char __c)
480  {
481    switch (__c)
482    {
483    case 'a':
484    case 'A':
485      return 10;
486    case 'b':
487    case 'B':
488      return 11;
489    case 'c':
490    case 'C':
491      return 12;
492    case 'd':
493    case 'D':
494      return 13;
495    case 'e':
496    case 'E':
497      return 14;
498    case 'f':
499    case 'F':
500      return 15;
501    case 'g':
502    case 'G':
503      return 16;
504    case 'h':
505    case 'H':
506      return 17;
507    case 'i':
508    case 'I':
509      return 18;
510    case 'j':
511    case 'J':
512      return 19;
513    case 'k':
514    case 'K':
515      return 20;
516    case 'l':
517    case 'L':
518      return 21;
519    case 'm':
520    case 'M':
521      return 22;
522    case 'n':
523    case 'N':
524      return 23;
525    case 'o':
526    case 'O':
527      return 24;
528    case 'p':
529    case 'P':
530      return 25;
531    case 'q':
532    case 'Q':
533      return 26;
534    case 'r':
535    case 'R':
536      return 27;
537    case 's':
538    case 'S':
539      return 28;
540    case 't':
541    case 'T':
542      return 29;
543    case 'u':
544    case 'U':
545      return 30;
546    case 'v':
547    case 'V':
548      return 31;
549    case 'w':
550    case 'W':
551      return 32;
552    case 'x':
553    case 'X':
554      return 33;
555    case 'y':
556    case 'Y':
557      return 34;
558    case 'z':
559    case 'Z':
560      return 35;
561    }
562    return std::numeric_limits<unsigned char>::max();
563  }
564
565  /// std::from_chars implementation for integers in bases 11 to 26.
566  template<typename _Tp>
567    bool
568    __from_chars_alnum(const char*& __first, const char* __last, _Tp& __val,
569		       int __base)
570    {
571      bool __valid = true;
572      while (__first != __last)
573	{
574	  unsigned char __c = *__first;
575	  if (std::isdigit(__c))
576	    __c -= '0';
577	  else
578	    {
579	      __c = __from_chars_alpha_to_num(__c);
580	      if (__c >= __base)
581		break;
582	    }
583
584	  if (__builtin_expect(__valid, 1))
585	    __valid = __raise_and_add(__val, __base, __c);
586	  __first++;
587	}
588      return __valid;
589    }
590
591  template<typename _Tp>
592    using __integer_from_chars_result_type
593      = enable_if_t<__is_int_to_chars_type<_Tp>::value, from_chars_result>;
594
595} // namespace __detail
596
597  /// std::from_chars for integral types.
598  template<typename _Tp>
599    __detail::__integer_from_chars_result_type<_Tp>
600    from_chars(const char* __first, const char* __last, _Tp& __value,
601	       int __base = 10)
602    {
603      __glibcxx_assert(2 <= __base && __base <= 36);
604
605      from_chars_result __res{__first, {}};
606
607      int __sign = 1;
608      if _GLIBCXX17_CONSTEXPR (std::is_signed<_Tp>::value)
609	if (__first != __last && *__first == '-')
610	  {
611	    __sign = -1;
612	    ++__first;
613	  }
614
615      using _Up = __detail::__unsigned_least_t<_Tp>;
616      _Up __val = 0;
617
618      const auto __start = __first;
619      bool __valid;
620      if (__base == 2)
621	__valid = __detail::__from_chars_binary(__first, __last, __val);
622      else if (__base <= 10)
623	__valid = __detail::__from_chars_digit(__first, __last, __val, __base);
624      else
625	__valid = __detail::__from_chars_alnum(__first, __last, __val, __base);
626
627      if (__builtin_expect(__first == __start, 0))
628	__res.ec = errc::invalid_argument;
629      else
630	{
631	  __res.ptr = __first;
632	  if (!__valid)
633	    __res.ec = errc::result_out_of_range;
634	  else
635	    {
636	      if _GLIBCXX17_CONSTEXPR (std::is_signed<_Tp>::value)
637		{
638		  _Tp __tmp;
639		  if (__builtin_mul_overflow(__val, __sign, &__tmp))
640		    __res.ec = errc::result_out_of_range;
641		  else
642		    __value = __tmp;
643		}
644	      else
645		{
646		  if _GLIBCXX17_CONSTEXPR
647		    (numeric_limits<_Up>::max() > numeric_limits<_Tp>::max())
648		    {
649		      if (__val > numeric_limits<_Tp>::max())
650			__res.ec = errc::result_out_of_range;
651		      else
652			__value = __val;
653		    }
654		  else
655		    __value = __val;
656		}
657	    }
658	}
659      return __res;
660    }
661
662_GLIBCXX_END_NAMESPACE_VERSION
663} // namespace std
664#endif // C++14
665#endif // _GLIBCXX_CHARCONV
666