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