1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef _LIBCPP___CHARCONV_TRAITS
11 #define _LIBCPP___CHARCONV_TRAITS
12 
13 #include <__bit/countl.h>
14 #include <__charconv/tables.h>
15 #include <__charconv/to_chars_base_10.h>
16 #include <__config>
17 #include <__type_traits/enable_if.h>
18 #include <__type_traits/is_unsigned.h>
19 #include <cstdint>
20 #include <limits>
21 
22 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
23 #  pragma GCC system_header
24 #endif
25 
26 _LIBCPP_PUSH_MACROS
27 #include <__undef_macros>
28 
29 _LIBCPP_BEGIN_NAMESPACE_STD
30 
31 #if _LIBCPP_STD_VER >= 17
32 
33 namespace __itoa {
34 
35 template <typename _Tp, typename = void>
36 struct _LIBCPP_HIDDEN __traits_base;
37 
38 template <typename _Tp>
39 struct _LIBCPP_HIDDEN __traits_base<_Tp, __enable_if_t<sizeof(_Tp) <= sizeof(uint32_t)>> {
40   using type = uint32_t;
41 
42   /// The width estimation using a log10 algorithm.
43   ///
44   /// The algorithm is based on
45   /// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
46   /// Instead of using IntegerLogBase2 it uses __libcpp_clz. Since that
47   /// function requires its input to have at least one bit set the value of
48   /// zero is set to one. This means the first element of the lookup table is
49   /// zero.
50   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI int __width(_Tp __v) {
51     auto __t = (32 - std::__libcpp_clz(static_cast<type>(__v | 1))) * 1233 >> 12;
52     return __t - (__v < __itoa::__pow10_32[__t]) + 1;
53   }
54 
55   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char* __convert(char* __p, _Tp __v) {
56     return __itoa::__base_10_u32(__p, __v);
57   }
58 
59   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI decltype(__pow10_32)& __pow() {
60     return __itoa::__pow10_32;
61   }
62 };
63 
64 template <typename _Tp>
65 struct _LIBCPP_HIDDEN __traits_base<_Tp, __enable_if_t<sizeof(_Tp) == sizeof(uint64_t)>> {
66   using type = uint64_t;
67 
68   /// The width estimation using a log10 algorithm.
69   ///
70   /// The algorithm is based on
71   /// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
72   /// Instead of using IntegerLogBase2 it uses __libcpp_clz. Since that
73   /// function requires its input to have at least one bit set the value of
74   /// zero is set to one. This means the first element of the lookup table is
75   /// zero.
76   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI int __width(_Tp __v) {
77     auto __t = (64 - std::__libcpp_clz(static_cast<type>(__v | 1))) * 1233 >> 12;
78     return __t - (__v < __itoa::__pow10_64[__t]) + 1;
79   }
80 
81   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char* __convert(char* __p, _Tp __v) {
82     return __itoa::__base_10_u64(__p, __v);
83   }
84 
85   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI decltype(__pow10_64)& __pow() {
86     return __itoa::__pow10_64;
87   }
88 };
89 
90 #  ifndef _LIBCPP_HAS_NO_INT128
91 template <typename _Tp>
92 struct _LIBCPP_HIDDEN __traits_base<_Tp, __enable_if_t<sizeof(_Tp) == sizeof(__uint128_t)> > {
93   using type = __uint128_t;
94 
95   /// The width estimation using a log10 algorithm.
96   ///
97   /// The algorithm is based on
98   /// http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
99   /// Instead of using IntegerLogBase2 it uses __libcpp_clz. Since that
100   /// function requires its input to have at least one bit set the value of
101   /// zero is set to one. This means the first element of the lookup table is
102   /// zero.
103   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI int __width(_Tp __v) {
104     _LIBCPP_ASSERT_UNCATEGORIZED(
105         __v > numeric_limits<uint64_t>::max(), "The optimizations for this algorithm fail when this isn't true.");
106     // There's always a bit set in the upper 64-bits.
107     auto __t = (128 - std::__libcpp_clz(static_cast<uint64_t>(__v >> 64))) * 1233 >> 12;
108     _LIBCPP_ASSERT_UNCATEGORIZED(__t >= __itoa::__pow10_128_offset, "Index out of bounds");
109     // __t is adjusted since the lookup table misses the lower entries.
110     return __t - (__v < __itoa::__pow10_128[__t - __itoa::__pow10_128_offset]) + 1;
111   }
112 
113   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char* __convert(char* __p, _Tp __v) {
114     return __itoa::__base_10_u128(__p, __v);
115   }
116 
117   // TODO FMT This pow function should get an index.
118   // By moving this to its own header it can be reused by the pow function in to_chars_base_10.
119   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI decltype(__pow10_128)& __pow() {
120     return __itoa::__pow10_128;
121   }
122 };
123 #  endif
124 
125 template <typename _Tp>
126 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI bool
127 __mul_overflowed(unsigned char __a, _Tp __b, unsigned char& __r) {
128   auto __c = __a * __b;
129   __r      = __c;
130   return __c > numeric_limits<unsigned char>::max();
131 }
132 
133 template <typename _Tp>
134 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI bool
135 __mul_overflowed(unsigned short __a, _Tp __b, unsigned short& __r) {
136   auto __c = __a * __b;
137   __r      = __c;
138   return __c > numeric_limits<unsigned short>::max();
139 }
140 
141 template <typename _Tp>
142 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI bool __mul_overflowed(_Tp __a, _Tp __b, _Tp& __r) {
143   static_assert(is_unsigned<_Tp>::value, "");
144   return __builtin_mul_overflow(__a, __b, &__r);
145 }
146 
147 template <typename _Tp, typename _Up>
148 inline _LIBCPP_HIDE_FROM_ABI bool _LIBCPP_CONSTEXPR_SINCE_CXX23 __mul_overflowed(_Tp __a, _Up __b, _Tp& __r) {
149   return __itoa::__mul_overflowed(__a, static_cast<_Tp>(__b), __r);
150 }
151 
152 template <typename _Tp>
153 struct _LIBCPP_HIDDEN __traits : __traits_base<_Tp> {
154   static constexpr int digits = numeric_limits<_Tp>::digits10 + 1;
155   using __traits_base<_Tp>::__pow;
156   using typename __traits_base<_Tp>::type;
157 
158   // precondition: at least one non-zero character available
159   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI char const*
160   __read(char const* __p, char const* __ep, type& __a, type& __b) {
161     type __cprod[digits];
162     int __j = digits - 1;
163     int __i = digits;
164     do {
165       if (*__p < '0' || *__p > '9')
166         break;
167       __cprod[--__i] = *__p++ - '0';
168     } while (__p != __ep && __i != 0);
169 
170     __a = __inner_product(__cprod + __i + 1, __cprod + __j, __pow() + 1, __cprod[__i]);
171     if (__itoa::__mul_overflowed(__cprod[__j], __pow()[__j - __i], __b))
172       --__p;
173     return __p;
174   }
175 
176   template <typename _It1, typename _It2, class _Up>
177   static _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI _Up
178   __inner_product(_It1 __first1, _It1 __last1, _It2 __first2, _Up __init) {
179     for (; __first1 < __last1; ++__first1, ++__first2)
180       __init = __init + *__first1 * *__first2;
181     return __init;
182   }
183 };
184 
185 } // namespace __itoa
186 
187 template <typename _Tp>
188 inline _LIBCPP_CONSTEXPR_SINCE_CXX23 _LIBCPP_HIDE_FROM_ABI _Tp __complement(_Tp __x) {
189   static_assert(is_unsigned<_Tp>::value, "cast to unsigned first");
190   return _Tp(~__x + 1);
191 }
192 
193 #endif // _LIBCPP_STD_VER >= 17
194 
195 _LIBCPP_END_NAMESPACE_STD
196 
197 _LIBCPP_POP_MACROS
198 
199 #endif // _LIBCPP___CHARCONV_TRAITS
200