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