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