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_INTERNAL( 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_INTERNAL(__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