Line data Source code
1 : /**
2 : Copyright (c) 2016-2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : // Integer formatting based on https://github.com/fmtlib/blob/master/fmt/include/fmt/format.h
25 : // See original license https://github.com/fmtlib/fmt/blob/master/LICENSE
26 : // Only base function and table data used
27 :
28 : // Double formatting from https://github.com/miloyip/dtoa-benchmark/tree/master
29 : // See original license https://github.com/miloyip/dtoa-benchmark/blob/master/license.txt
30 : // Implemented buffer usage counter and support for different char types
31 :
32 : #include "SPString.h"
33 : #include "SPUnicode.h"
34 :
35 : namespace STAPPLER_VERSIONIZED stappler::string {
36 :
37 : // Copies two characters from src to dst.
38 : template<typename Char>
39 3025440 : constexpr void copy2(Char *dst, const Char *src) {
40 3025440 : memcpy(dst, src, 2 * sizeof(Char));
41 3025440 : }
42 :
43 : // Converts value in the range [0, 100) to a string.
44 : template <typename Char>
45 3025440 : constexpr auto digits2(size_t value) -> const Char * {
46 : if constexpr (sizeof(Char) == sizeof(char)) {
47 : return &"0001020304050607080910111213141516171819"
48 : "2021222324252627282930313233343536373839"
49 : "4041424344454647484950515253545556575859"
50 : "6061626364656667686970717273747576777879"
51 3024790 : "8081828384858687888990919293949596979899"[value * 2];
52 : } else if constexpr (sizeof(Char) == sizeof(char16_t)) {
53 : return &u"0001020304050607080910111213141516171819"
54 : u"2021222324252627282930313233343536373839"
55 : u"4041424344454647484950515253545556575859"
56 : u"6061626364656667686970717273747576777879"
57 650 : u"8081828384858687888990919293949596979899"[value * 2];
58 : } else if constexpr (sizeof(Char) == sizeof(char32_t)) {
59 : return &U"0001020304050607080910111213141516171819"
60 : U"2021222324252627282930313233343536373839"
61 : U"4041424344454647484950515253545556575859"
62 : U"6061626364656667686970717273747576777879"
63 : U"8081828384858687888990919293949596979899"[value * 2];
64 : }
65 : return nullptr;
66 : }
67 :
68 : template <typename IntType, typename Char>
69 1412269 : inline size_t unsigned_to_decimal(Char *out, IntType value, size_t size) {
70 1412269 : out += size;
71 1412269 : Char *end = out;
72 3850244 : while (value >= 100) {
73 2437975 : out -= 2;
74 2437975 : copy2(out, digits2<Char>(static_cast<size_t>(value % 100)));
75 2437975 : value /= 100;
76 : }
77 1412269 : if (value < 10) {
78 824804 : *--out = static_cast<Char>('0' + value);
79 824804 : return end - out;
80 : }
81 587465 : out -= 2;
82 587465 : copy2(out, digits2<Char>(static_cast<size_t>(value)));
83 587465 : return end - out;
84 : }
85 :
86 : template <typename IntType>
87 1457113 : inline size_t unsigned_to_decimal_len(IntType value) {
88 1457113 : size_t ret = 0;
89 1686238 : while (value >= 100) {
90 229125 : ret += 2;
91 229125 : value /= 100;
92 : }
93 1457113 : if (value < 10) {
94 1373333 : return ret + 1;
95 : }
96 83780 : return ret + 2;
97 : }
98 :
99 : namespace dtoa {
100 :
101 : #if (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
102 : namespace gcc_ints {
103 : __extension__ typedef __int128 int128;
104 : __extension__ typedef unsigned __int128 uint128;
105 : }
106 : #endif
107 :
108 : #define UINT64_C2(h, l) ((static_cast<uint64_t>(h) << 32) | static_cast<uint64_t>(l))
109 :
110 : struct DiyFp {
111 25818538 : DiyFp() {}
112 :
113 109731774 : DiyFp(uint64_t f, int e) : f(f), e(e) {}
114 :
115 12909269 : DiyFp(double d) {
116 : union {
117 : double d;
118 : uint64_t u64;
119 12909269 : } u = { d };
120 :
121 12909269 : int biased_e = (u.u64 & kDpExponentMask) >> kDpSignificandSize;
122 12909269 : uint64_t significand = (u.u64 & kDpSignificandMask);
123 12909269 : if (biased_e != 0) {
124 12909269 : f = significand + kDpHiddenBit;
125 12909269 : e = biased_e - kDpExponentBias;
126 : }
127 : else {
128 0 : f = significand;
129 0 : e = kDpMinExponent + 1;
130 : }
131 12909269 : }
132 :
133 6457622 : DiyFp operator-(const DiyFp& rhs) const {
134 6457622 : assert(e == rhs.e);
135 6457622 : assert(f >= rhs.f);
136 6457622 : return DiyFp(f - rhs.f, e);
137 : }
138 :
139 38727807 : DiyFp operator*(const DiyFp& rhs) const {
140 : #if defined(_MSC_VER) && defined(_M_AMD64)
141 : uint64_t h;
142 : uint64_t l = _umul128(f, rhs.f, &h);
143 : if (l & (uint64_t(1) << 63)) // rounding
144 : h++;
145 : return DiyFp(h, e + rhs.e + 64);
146 : #elif (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
147 38727807 : gcc_ints::uint128 p = static_cast<gcc_ints::uint128>(f) * static_cast<gcc_ints::uint128>(rhs.f);
148 38727807 : uint64_t h = p >> 64;
149 38727807 : uint64_t l = static_cast<uint64_t>(p);
150 38727807 : if (l & (uint64_t(1) << 63)) // rounding
151 1307950 : h++;
152 38727807 : return DiyFp(h, e + rhs.e + 64);
153 : #else
154 : const uint64_t M32 = 0xFFFFFFFF;
155 : const uint64_t a = f >> 32;
156 : const uint64_t b = f & M32;
157 : const uint64_t c = rhs.f >> 32;
158 : const uint64_t d = rhs.f & M32;
159 : const uint64_t ac = a * c;
160 : const uint64_t bc = b * c;
161 : const uint64_t ad = a * d;
162 : const uint64_t bd = b * d;
163 : uint64_t tmp = (bd >> 32) + (ad & M32) + (bc & M32);
164 : tmp += 1U << 31; /// mult_round
165 : return DiyFp(ac + (ad >> 32) + (bc >> 32) + (tmp >> 32), e + rhs.e + 64);
166 : #endif
167 : }
168 :
169 12909269 : DiyFp Normalize() const {
170 : #if defined(_MSC_VER) && defined(_M_AMD64)
171 : unsigned long index;
172 : _BitScanReverse64(&index, f);
173 : return DiyFp(f << (63 - index), e - (63 - index));
174 : #elif defined(__GNUC__)
175 12909269 : int s = __builtin_clzll(f);
176 12909269 : return DiyFp(f << s, e - s);
177 : #else
178 : DiyFp res = *this;
179 : while (!(res.f & kDpHiddenBit)) {
180 : res.f <<= 1;
181 : res.e--;
182 : }
183 : res.f <<= (kDiySignificandSize - kDpSignificandSize - 1);
184 : res.e = res.e - (kDiySignificandSize - kDpSignificandSize - 1);
185 : return res;
186 : #endif
187 : }
188 :
189 12909269 : DiyFp NormalizeBoundary() const {
190 : #if defined(_MSC_VER) && defined(_M_AMD64)
191 : unsigned long index;
192 : _BitScanReverse64(&index, f);
193 : return DiyFp (f << (63 - index), e - (63 - index));
194 : #else
195 12909269 : DiyFp res = *this;
196 12909269 : while (!(res.f & (kDpHiddenBit << 1))) {
197 0 : res.f <<= 1;
198 0 : res.e--;
199 : }
200 12909269 : res.f <<= (kDiySignificandSize - kDpSignificandSize - 2);
201 12909269 : res.e = res.e - (kDiySignificandSize - kDpSignificandSize - 2);
202 12909269 : return res;
203 : #endif
204 : }
205 :
206 12909269 : void NormalizedBoundaries(DiyFp* minus, DiyFp* plus) const {
207 12909269 : DiyFp pl = DiyFp((f << 1) + 1, e - 1).NormalizeBoundary();
208 12909269 : DiyFp mi = (f == kDpHiddenBit) ? DiyFp((f << 2) - 1, e - 2) : DiyFp((f << 1) - 1, e - 1);
209 12909269 : mi.f <<= mi.e - pl.e;
210 12909269 : mi.e = pl.e;
211 12909269 : *plus = pl;
212 12909269 : *minus = mi;
213 12909269 : }
214 :
215 : static const int kDiySignificandSize = 64;
216 : static const int kDpSignificandSize = 52;
217 : static const int kDpExponentBias = 0x3FF + kDpSignificandSize;
218 : static const int kDpMinExponent = -kDpExponentBias;
219 : static const uint64_t kDpExponentMask = UINT64_C2(0x7FF00000, 0x00000000);
220 : static const uint64_t kDpSignificandMask = UINT64_C2(0x000FFFFF, 0xFFFFFFFF);
221 : static const uint64_t kDpHiddenBit = UINT64_C2(0x00100000, 0x00000000);
222 :
223 : uint64_t f;
224 : int e;
225 : };
226 :
227 12909269 : inline DiyFp GetCachedPower(int e, int* K) {
228 : // 10^-348, 10^-340, ..., 10^340
229 : static const uint64_t kCachedPowers_F[] = {
230 : UINT64_C2(0xfa8fd5a0, 0x081c0288), UINT64_C2(0xbaaee17f, 0xa23ebf76),
231 : UINT64_C2(0x8b16fb20, 0x3055ac76), UINT64_C2(0xcf42894a, 0x5dce35ea),
232 : UINT64_C2(0x9a6bb0aa, 0x55653b2d), UINT64_C2(0xe61acf03, 0x3d1a45df),
233 : UINT64_C2(0xab70fe17, 0xc79ac6ca), UINT64_C2(0xff77b1fc, 0xbebcdc4f),
234 : UINT64_C2(0xbe5691ef, 0x416bd60c), UINT64_C2(0x8dd01fad, 0x907ffc3c),
235 : UINT64_C2(0xd3515c28, 0x31559a83), UINT64_C2(0x9d71ac8f, 0xada6c9b5),
236 : UINT64_C2(0xea9c2277, 0x23ee8bcb), UINT64_C2(0xaecc4991, 0x4078536d),
237 : UINT64_C2(0x823c1279, 0x5db6ce57), UINT64_C2(0xc2109436, 0x4dfb5637),
238 : UINT64_C2(0x9096ea6f, 0x3848984f), UINT64_C2(0xd77485cb, 0x25823ac7),
239 : UINT64_C2(0xa086cfcd, 0x97bf97f4), UINT64_C2(0xef340a98, 0x172aace5),
240 : UINT64_C2(0xb23867fb, 0x2a35b28e), UINT64_C2(0x84c8d4df, 0xd2c63f3b),
241 : UINT64_C2(0xc5dd4427, 0x1ad3cdba), UINT64_C2(0x936b9fce, 0xbb25c996),
242 : UINT64_C2(0xdbac6c24, 0x7d62a584), UINT64_C2(0xa3ab6658, 0x0d5fdaf6),
243 : UINT64_C2(0xf3e2f893, 0xdec3f126), UINT64_C2(0xb5b5ada8, 0xaaff80b8),
244 : UINT64_C2(0x87625f05, 0x6c7c4a8b), UINT64_C2(0xc9bcff60, 0x34c13053),
245 : UINT64_C2(0x964e858c, 0x91ba2655), UINT64_C2(0xdff97724, 0x70297ebd),
246 : UINT64_C2(0xa6dfbd9f, 0xb8e5b88f), UINT64_C2(0xf8a95fcf, 0x88747d94),
247 : UINT64_C2(0xb9447093, 0x8fa89bcf), UINT64_C2(0x8a08f0f8, 0xbf0f156b),
248 : UINT64_C2(0xcdb02555, 0x653131b6), UINT64_C2(0x993fe2c6, 0xd07b7fac),
249 : UINT64_C2(0xe45c10c4, 0x2a2b3b06), UINT64_C2(0xaa242499, 0x697392d3),
250 : UINT64_C2(0xfd87b5f2, 0x8300ca0e), UINT64_C2(0xbce50864, 0x92111aeb),
251 : UINT64_C2(0x8cbccc09, 0x6f5088cc), UINT64_C2(0xd1b71758, 0xe219652c),
252 : UINT64_C2(0x9c400000, 0x00000000), UINT64_C2(0xe8d4a510, 0x00000000),
253 : UINT64_C2(0xad78ebc5, 0xac620000), UINT64_C2(0x813f3978, 0xf8940984),
254 : UINT64_C2(0xc097ce7b, 0xc90715b3), UINT64_C2(0x8f7e32ce, 0x7bea5c70),
255 : UINT64_C2(0xd5d238a4, 0xabe98068), UINT64_C2(0x9f4f2726, 0x179a2245),
256 : UINT64_C2(0xed63a231, 0xd4c4fb27), UINT64_C2(0xb0de6538, 0x8cc8ada8),
257 : UINT64_C2(0x83c7088e, 0x1aab65db), UINT64_C2(0xc45d1df9, 0x42711d9a),
258 : UINT64_C2(0x924d692c, 0xa61be758), UINT64_C2(0xda01ee64, 0x1a708dea),
259 : UINT64_C2(0xa26da399, 0x9aef774a), UINT64_C2(0xf209787b, 0xb47d6b85),
260 : UINT64_C2(0xb454e4a1, 0x79dd1877), UINT64_C2(0x865b8692, 0x5b9bc5c2),
261 : UINT64_C2(0xc83553c5, 0xc8965d3d), UINT64_C2(0x952ab45c, 0xfa97a0b3),
262 : UINT64_C2(0xde469fbd, 0x99a05fe3), UINT64_C2(0xa59bc234, 0xdb398c25),
263 : UINT64_C2(0xf6c69a72, 0xa3989f5c), UINT64_C2(0xb7dcbf53, 0x54e9bece),
264 : UINT64_C2(0x88fcf317, 0xf22241e2), UINT64_C2(0xcc20ce9b, 0xd35c78a5),
265 : UINT64_C2(0x98165af3, 0x7b2153df), UINT64_C2(0xe2a0b5dc, 0x971f303a),
266 : UINT64_C2(0xa8d9d153, 0x5ce3b396), UINT64_C2(0xfb9b7cd9, 0xa4a7443c),
267 : UINT64_C2(0xbb764c4c, 0xa7a44410), UINT64_C2(0x8bab8eef, 0xb6409c1a),
268 : UINT64_C2(0xd01fef10, 0xa657842c), UINT64_C2(0x9b10a4e5, 0xe9913129),
269 : UINT64_C2(0xe7109bfb, 0xa19c0c9d), UINT64_C2(0xac2820d9, 0x623bf429),
270 : UINT64_C2(0x80444b5e, 0x7aa7cf85), UINT64_C2(0xbf21e440, 0x03acdd2d),
271 : UINT64_C2(0x8e679c2f, 0x5e44ff8f), UINT64_C2(0xd433179d, 0x9c8cb841),
272 : UINT64_C2(0x9e19db92, 0xb4e31ba9), UINT64_C2(0xeb96bf6e, 0xbadf77d9),
273 : UINT64_C2(0xaf87023b, 0x9bf0ee6b)
274 : };
275 : static const int16_t kCachedPowers_E[] = {
276 : -1220, -1193, -1166, -1140, -1113, -1087, -1060, -1034, -1007, -980,
277 : -954, -927, -901, -874, -847, -821, -794, -768, -741, -715,
278 : -688, -661, -635, -608, -582, -555, -529, -502, -475, -449,
279 : -422, -396, -369, -343, -316, -289, -263, -236, -210, -183,
280 : -157, -130, -103, -77, -50, -24, 3, 30, 56, 83,
281 : 109, 136, 162, 189, 216, 242, 269, 295, 322, 348,
282 : 375, 402, 428, 455, 481, 508, 534, 561, 588, 614,
283 : 641, 667, 694, 720, 747, 774, 800, 827, 853, 880,
284 : 907, 933, 960, 986, 1013, 1039, 1066
285 : };
286 :
287 : //int k = static_cast<int>(ceil((-61 - e) * 0.30102999566398114)) + 374;
288 12909269 : double dk = (-61 - e) * 0.30102999566398114 + 347; // dk must be positive, so can do ceiling in positive
289 12909269 : int k = static_cast<int>(dk);
290 12909269 : if (dk - k > 0.0)
291 10513525 : k++;
292 :
293 12909269 : unsigned index = static_cast<unsigned>((k >> 3) + 1);
294 12909269 : *K = -(-348 + static_cast<int>(index << 3)); // decimal exponent no need lookup table
295 :
296 12909269 : assert(index < sizeof(kCachedPowers_F) / sizeof(kCachedPowers_F[0]));
297 12909269 : return DiyFp(kCachedPowers_F[index], kCachedPowers_E[index]);
298 : }
299 :
300 : template <typename Char>
301 6457622 : inline void GrisuRound(Char* buffer, int len, uint64_t delta, uint64_t rest, uint64_t ten_kappa, uint64_t wp_w) {
302 6457622 : while (rest < wp_w && delta - rest >= ten_kappa &&
303 61367 : (rest + ten_kappa < wp_w || /// closer
304 61367 : wp_w - rest > rest + ten_kappa - wp_w)) {
305 0 : buffer[len - 1]--;
306 0 : rest += ten_kappa;
307 : }
308 6457622 : }
309 :
310 12909269 : inline unsigned CountDecimalDigit32(uint32_t n) {
311 : // Simple pure C++ implementation was faster than __builtin_clz version in this situation.
312 12909269 : if (n < 10) return 1;
313 12909269 : if (n < 100) return 2;
314 12908394 : if (n < 1000) return 3;
315 12907383 : if (n < 10000) return 4;
316 12894892 : if (n < 100000) return 5;
317 8015261 : if (n < 1000000) return 6;
318 16794 : if (n < 10000000) return 7;
319 75 : if (n < 100000000) return 8;
320 50 : if (n < 1000000000) return 9;
321 0 : return 10;
322 : }
323 :
324 : template <typename Char>
325 6457622 : inline void DigitGen(const DiyFp& W, const DiyFp& Mp, uint64_t delta, Char* buffer, int* len, int* K) {
326 : static const uint32_t kPow10[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
327 6457622 : const DiyFp one(uint64_t(1) << -Mp.e, Mp.e);
328 6457622 : const DiyFp wp_w = Mp - W;
329 6457622 : uint32_t p1 = static_cast<uint32_t>(Mp.f >> -one.e);
330 6457622 : uint64_t p2 = Mp.f & (one.f - 1);
331 6457622 : int kappa = static_cast<int>(CountDecimalDigit32(p1));
332 6457622 : *len = 0;
333 :
334 22860596 : while (kappa > 0) {
335 : uint32_t d;
336 20420852 : switch (kappa) {
337 0 : case 10: d = p1 / 1000000000; p1 %= 1000000000; break;
338 50 : case 9: d = p1 / 100000000; p1 %= 100000000; break;
339 50 : case 8: d = p1 / 10000000; p1 %= 10000000; break;
340 8422 : case 7: d = p1 / 1000000; p1 %= 1000000; break;
341 4009343 : case 6: d = p1 / 100000; p1 %= 100000; break;
342 6136796 : case 5: d = p1 / 10000; p1 %= 10000; break;
343 2876754 : case 4: d = p1 / 1000; p1 %= 1000; break;
344 2509896 : case 3: d = p1 / 100; p1 %= 100; break;
345 2439796 : case 2: d = p1 / 10; p1 %= 10; break;
346 2439745 : case 1: d = p1; p1 = 0; break;
347 0 : default:
348 : #if defined(_MSC_VER)
349 : __assume(0);
350 : #elif __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)
351 0 : __builtin_unreachable();
352 : #else
353 : d = 0;
354 : #endif
355 : }
356 20420852 : if (d || *len)
357 20420852 : buffer[(*len)++] = '0' + static_cast<char>(d);
358 20420852 : kappa--;
359 20420852 : uint64_t tmp = (static_cast<uint64_t>(p1) << -one.e) + p2;
360 20420852 : if (tmp <= delta) {
361 4017878 : *K += kappa;
362 4017878 : GrisuRound(buffer, *len, delta, tmp, static_cast<uint64_t>(kPow10[kappa]) << -one.e, wp_w.f);
363 4017878 : return;
364 : }
365 : }
366 :
367 : // kappa = 0
368 24037613 : for (;;) {
369 26477357 : p2 *= 10;
370 26477357 : delta *= 10;
371 26477357 : char d = static_cast<char>(p2 >> -one.e);
372 26477357 : if (d || *len)
373 26477357 : buffer[(*len)++] = '0' + d;
374 26477357 : p2 &= one.f - 1;
375 26477357 : kappa--;
376 26477357 : if (p2 < delta) {
377 2439744 : *K += kappa;
378 2439744 : GrisuRound(buffer, *len, delta, p2, one.f, wp_w.f * kPow10[-kappa]);
379 2439744 : return;
380 : }
381 : }
382 : }
383 :
384 6451647 : inline void DigitGen_len(const DiyFp& W, const DiyFp& Mp, uint64_t delta, int* len, int* K) {
385 6451647 : const DiyFp one(uint64_t(1) << -Mp.e, Mp.e);
386 6451647 : uint32_t p1 = static_cast<uint32_t>(Mp.f >> -one.e);
387 6451647 : uint64_t p2 = Mp.f & (one.f - 1);
388 6451647 : int kappa = static_cast<int>(CountDecimalDigit32(p1));
389 6451647 : *len = 0;
390 :
391 22843746 : while (kappa > 0) {
392 : uint32_t d;
393 20404152 : switch (kappa) {
394 0 : case 10: d = p1 / 1000000000; p1 %= 1000000000; break;
395 0 : case 9: d = p1 / 100000000; p1 %= 100000000; break;
396 0 : case 8: d = p1 / 10000000; p1 %= 10000000; break;
397 8347 : case 7: d = p1 / 1000000; p1 %= 1000000; break;
398 4004993 : case 6: d = p1 / 100000; p1 %= 100000; break;
399 6130971 : case 5: d = p1 / 10000; p1 %= 10000; break;
400 2870929 : case 4: d = p1 / 1000; p1 %= 1000; break;
401 2509696 : case 3: d = p1 / 100; p1 %= 100; break;
402 2439621 : case 2: d = p1 / 10; p1 %= 10; break;
403 2439595 : case 1: d = p1; p1 = 0; break;
404 0 : default:
405 : #if defined(_MSC_VER)
406 : __assume(0);
407 : #elif __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 5)
408 0 : __builtin_unreachable();
409 : #else
410 : d = 0;
411 : #endif
412 : }
413 20404152 : if (d || *len)
414 20404152 : (*len)++;
415 20404152 : kappa--;
416 20404152 : uint64_t tmp = (static_cast<uint64_t>(p1) << -one.e) + p2;
417 20404152 : if (tmp <= delta) {
418 4012053 : *K += kappa;
419 4012053 : return;
420 : }
421 : }
422 :
423 : // kappa = 0
424 : for (;;) {
425 26476207 : p2 *= 10;
426 26476207 : delta *= 10;
427 26476207 : char d = static_cast<char>(p2 >> -one.e);
428 26476207 : if (d || *len)
429 26476207 : (*len)++;
430 26476207 : p2 &= one.f - 1;
431 26476207 : kappa--;
432 26476207 : if (p2 < delta) {
433 2439594 : *K += kappa;
434 2439594 : return;
435 : }
436 24036613 : }
437 : }
438 :
439 : template <typename Char>
440 6457622 : inline void Grisu2(double value, Char* buffer, int* length, int* K) {
441 6457622 : const DiyFp v(value);
442 6457622 : DiyFp w_m, w_p;
443 6457622 : v.NormalizedBoundaries(&w_m, &w_p);
444 :
445 6457622 : const DiyFp c_mk = GetCachedPower(w_p.e, K);
446 6457622 : const DiyFp W = v.Normalize() * c_mk;
447 6457622 : DiyFp Wp = w_p * c_mk;
448 6457622 : DiyFp Wm = w_m * c_mk;
449 6457622 : Wm.f++;
450 6457622 : Wp.f--;
451 6457622 : DigitGen(W, Wp, Wp.f - Wm.f, buffer, length, K);
452 6457622 : }
453 :
454 6451647 : inline void Grisu2_len(double value, int* length, int* K) {
455 6451647 : const DiyFp v(value);
456 6451647 : DiyFp w_m, w_p;
457 6451647 : v.NormalizedBoundaries(&w_m, &w_p);
458 :
459 6451647 : const DiyFp c_mk = GetCachedPower(w_p.e, K);
460 6451647 : const DiyFp W = v.Normalize() * c_mk;
461 6451647 : DiyFp Wp = w_p * c_mk;
462 6451647 : DiyFp Wm = w_m * c_mk;
463 6451647 : Wm.f++;
464 6451647 : Wp.f--;
465 6451647 : DigitGen_len(W, Wp, Wp.f - Wm.f, length, K);
466 6451647 : }
467 50 : inline const char* GetDigitsLut() {
468 : static const char cDigitsLut[200] = {
469 : '0', '0', '0', '1', '0', '2', '0', '3', '0', '4', '0', '5', '0', '6', '0', '7', '0', '8', '0', '9',
470 : '1', '0', '1', '1', '1', '2', '1', '3', '1', '4', '1', '5', '1', '6', '1', '7', '1', '8', '1', '9',
471 : '2', '0', '2', '1', '2', '2', '2', '3', '2', '4', '2', '5', '2', '6', '2', '7', '2', '8', '2', '9',
472 : '3', '0', '3', '1', '3', '2', '3', '3', '3', '4', '3', '5', '3', '6', '3', '7', '3', '8', '3', '9',
473 : '4', '0', '4', '1', '4', '2', '4', '3', '4', '4', '4', '5', '4', '6', '4', '7', '4', '8', '4', '9',
474 : '5', '0', '5', '1', '5', '2', '5', '3', '5', '4', '5', '5', '5', '6', '5', '7', '5', '8', '5', '9',
475 : '6', '0', '6', '1', '6', '2', '6', '3', '6', '4', '6', '5', '6', '6', '6', '7', '6', '8', '6', '9',
476 : '7', '0', '7', '1', '7', '2', '7', '3', '7', '4', '7', '5', '7', '6', '7', '7', '7', '8', '7', '9',
477 : '8', '0', '8', '1', '8', '2', '8', '3', '8', '4', '8', '5', '8', '6', '8', '7', '8', '8', '8', '9',
478 : '9', '0', '9', '1', '9', '2', '9', '3', '9', '4', '9', '5', '9', '6', '9', '7', '9', '8', '9', '9'
479 : };
480 50 : return cDigitsLut;
481 : }
482 :
483 : template <typename Char>
484 75 : inline size_t WriteExponent(int K, Char* buffer) {
485 75 : auto orig = buffer;
486 75 : if (K < 0) {
487 25 : *buffer++ = '-';
488 25 : K = -K;
489 : }
490 :
491 75 : if (K >= 100) {
492 25 : *buffer++ = '0' + static_cast<char>(K / 100);
493 25 : K %= 100;
494 25 : const char *d = GetDigitsLut() + K * 2;
495 25 : *buffer++ = d[0];
496 25 : *buffer++ = d[1];
497 50 : } else if (K >= 10) {
498 25 : const char *d = GetDigitsLut() + K * 2;
499 25 : *buffer++ = d[0];
500 25 : *buffer++ = d[1];
501 : } else {
502 25 : *buffer++ = '0' + static_cast<char>(K);
503 : }
504 :
505 75 : return buffer - orig;
506 : }
507 :
508 0 : inline size_t WriteExponent_len(int K) {
509 0 : size_t ret = 0;
510 0 : if (K < 0) {
511 0 : ++ ret;
512 0 : K = -K;
513 : }
514 :
515 0 : if (K >= 100) {
516 0 : ret += 3;
517 0 : K %= 100;
518 0 : } else if (K >= 10) {
519 0 : ret += 3;
520 : } else {
521 0 : ++ ret;
522 : }
523 0 : return ret;
524 : }
525 :
526 : template <typename Char>
527 6457622 : inline size_t Prettify(Char* buffer, int length, int k) {
528 6457622 : const int kk = length + k; // 10^(kk-1) <= v < 10^kk
529 :
530 6457622 : if (length <= kk && kk <= 21) {
531 : // 1234e7 -> 12340000000
532 3894025 : for (int i = length; i < kk; i++)
533 314125 : buffer[i] = '0';
534 3579900 : buffer[kk] = '.';
535 3579900 : buffer[kk + 1] = '0';
536 3579900 : return kk + 2;
537 2877722 : } else if (0 < kk && kk <= 21) {
538 : // 1234e-2 -> 12.34
539 2870421 : ::memmove(&buffer[kk + 1], &buffer[kk], (length - kk) * sizeof(Char));
540 2870421 : buffer[kk] = '.';
541 2870421 : return length + 1;
542 7301 : } else if (-6 < kk && kk <= 0) {
543 : // 1234e-6 -> 0.001234
544 7226 : const int offset = 2 - kk;
545 7226 : ::memmove(&buffer[offset], &buffer[0], length * sizeof(Char));
546 7226 : buffer[0] = '0';
547 7226 : buffer[1] = '.';
548 8669 : for (int i = 2; i < offset; i++)
549 1443 : buffer[i] = '0';
550 7226 : return length + offset;
551 75 : } else if (length == 1) {
552 : // 1e30
553 25 : buffer[1] = 'e';
554 25 : return 2 + WriteExponent(kk - 1, &buffer[2]);
555 : } else {
556 : // 1234e30 -> 1.234e33
557 50 : ::memmove(&buffer[2], &buffer[1], (length - 1) * sizeof(Char));
558 50 : buffer[1] = '.';
559 50 : buffer[length + 1] = 'e';
560 50 : return length + 2 + WriteExponent(kk - 1, &buffer[0 + length + 2]);
561 : }
562 : }
563 :
564 6451647 : inline size_t Prettify_len(int length, int k) {
565 6451647 : const int kk = length + k; // 10^(kk-1) <= v < 10^kk
566 :
567 6451647 : if (length <= kk && kk <= 21) {
568 : // 1234e7 -> 12340000000
569 3579800 : return kk + 2;
570 2871847 : } else if (0 < kk && kk <= 21) {
571 : // 1234e-2 -> 12.34
572 2864721 : return length + 1;
573 7126 : } else if (-6 < kk && kk <= 0) {
574 : // 1234e-6 -> 0.001234
575 7126 : const int offset = 2 - kk;
576 7126 : return length + offset;
577 0 : } else if (length == 1) {
578 0 : return 2 + WriteExponent_len(kk - 1);
579 : } else {
580 : // 1234e30 -> 1.234e33
581 0 : return length + 2 + WriteExponent_len(kk - 1);
582 : }
583 : }
584 :
585 : template <typename Char>
586 34125 : inline size_t dtoa_memcpy(Char *buffer, const Char *data, size_t size) {
587 34125 : memcpy(buffer, data, size * sizeof(Char));
588 34125 : return size;
589 : }
590 :
591 : template <typename Char>
592 6491747 : inline size_t dtoa_milo(double value, Char* buffer) {
593 6491747 : if (isnan(value)) {
594 : if constexpr (sizeof(Char) == sizeof(char)) {
595 175 : return dtoa_memcpy(buffer, "NaN", 3);
596 : } else if constexpr (sizeof(Char) == sizeof(char16_t)) {
597 0 : return dtoa_memcpy(buffer, u"NaN", 3);
598 : } else {
599 : return 0;
600 : }
601 6491572 : } else if (value == NumericLimits<double>::infinity()) {
602 : if constexpr (sizeof(Char) == sizeof(char)) {
603 175 : return dtoa_memcpy(buffer, "inf", 3);
604 : } else if constexpr (sizeof(Char) == sizeof(char16_t)) {
605 0 : return dtoa_memcpy(buffer, u"inf", 3);
606 : } else {
607 : return 0;
608 : }
609 6491397 : } else if (value == - NumericLimits<double>::infinity()) {
610 : if constexpr (sizeof(Char) == sizeof(char)) {
611 175 : return dtoa_memcpy(buffer, "-inf", 4);
612 : } else if constexpr (sizeof(Char) == sizeof(char16_t)) {
613 0 : return dtoa_memcpy(buffer, u"-inf", 4);
614 : } else {
615 : return 0;
616 : }
617 6491222 : } else if (value == 0) {
618 : if constexpr (sizeof(Char) == sizeof(char)) {
619 33600 : return dtoa_memcpy(buffer, "0.0", 3);
620 : } else if constexpr (sizeof(Char) == sizeof(char16_t)) {
621 0 : return dtoa_memcpy(buffer, u"0.0", 3);
622 : } else {
623 : return 0;
624 : }
625 : } else {
626 6457622 : if (value < 0) {
627 5175 : *buffer++ = '-';
628 5175 : value = -value;
629 : }
630 : int length, K;
631 6457622 : Grisu2(value, buffer, &length, &K);
632 6457622 : return Prettify(buffer, length, K);
633 : }
634 : }
635 :
636 6485197 : inline size_t dtoa_milo_len(double value) {
637 6485197 : if (isnan(value)) {
638 0 : return 3;
639 6485197 : } else if (value == NumericLimits<double>::infinity()) {
640 0 : return 3;
641 6485197 : } else if (value == - NumericLimits<double>::infinity()) {
642 0 : return 4;
643 6485197 : } else if (value == 0) {
644 33550 : return 3;
645 : } else {
646 6451647 : size_t ret = 0;
647 6451647 : if (value < 0) {
648 5125 : ++ ret;
649 5125 : value = -value;
650 : }
651 : int length, K;
652 6451647 : Grisu2_len(value, &length, &K);
653 6451647 : return Prettify_len(length, K);
654 : }
655 : }
656 :
657 : }
658 :
659 1343228 : size_t _itoa(int64_t number, char* buffer, size_t bufSize) {
660 1343228 : if (number < 0) {
661 5743 : auto ret = unsigned_to_decimal( buffer, uint64_t(-number), bufSize );
662 5743 : buffer[bufSize - ret - 1] = '-';
663 5743 : return ret + 1;
664 : } else {
665 1337485 : return unsigned_to_decimal( buffer, uint64_t(number), bufSize );
666 : }
667 : }
668 :
669 68866 : size_t _itoa(uint64_t number, char* buffer, size_t bufSize) {
670 68866 : return unsigned_to_decimal( buffer, uint64_t(number), bufSize );
671 : }
672 :
673 6491722 : size_t _dtoa(double number, char* buffer, size_t bufSize) {
674 6491722 : return dtoa::dtoa_milo(number, buffer);
675 : }
676 :
677 150 : size_t _itoa(int64_t number, char16_t* buffer, size_t bufSize) {
678 150 : if (number < 0) {
679 75 : auto ret = unsigned_to_decimal( buffer, uint64_t(-number), bufSize );
680 75 : buffer[bufSize - ret - 1] = '-';
681 75 : return ret + 1;
682 : } else {
683 75 : return unsigned_to_decimal( buffer, uint64_t(number), bufSize );
684 : }
685 : }
686 :
687 25 : size_t _itoa(uint64_t number, char16_t* buffer, size_t bufSize) {
688 25 : return unsigned_to_decimal( buffer, uint64_t(number), bufSize );
689 : }
690 :
691 762313 : size_t _itoa_len(int64_t number) {
692 762313 : if (number < 0) {
693 7436 : auto ret = unsigned_to_decimal_len( uint64_t(-number) );
694 7436 : return ret + 1;
695 : } else {
696 754877 : return unsigned_to_decimal_len( uint64_t(number) );
697 : }
698 : }
699 :
700 694800 : size_t _itoa_len(uint64_t number) {
701 694800 : return unsigned_to_decimal_len( uint64_t(number) );
702 : }
703 :
704 25 : size_t _dtoa(double number, char16_t* buffer, size_t bufSize) {
705 25 : return dtoa::dtoa_milo(number, buffer);
706 : }
707 :
708 6485197 : size_t _dtoa_len(double number) {
709 6485197 : return dtoa::dtoa_milo_len(number);
710 : }
711 :
712 : }
|
