Line data Source code
1 : // Copyright 2020-2023 Junekey Jeon
2 : // Copyright 2022 Peter Dimov
3 : // Copyright 2023 Matt Borland
4 : // Distributed under the Boost Software License, Version 1.0.
5 : // https://www.boost.org/LICENSE_1_0.txt
6 :
7 : #include <boost/json/detail/format.hpp>
8 : #include <boost/json/detail/dragonbox/to_chars_integer_impl.hpp>
9 : #include <limits>
10 : #include <cstring>
11 : #include <cstdio>
12 : #include <cstdint>
13 : #include <cmath>
14 :
15 : namespace boost {
16 : namespace json {
17 : namespace detail {
18 : namespace to_chars_detail {
19 :
20 : #ifdef BOOST_MSVC
21 : # pragma warning(push)
22 : # pragma warning(disable: 4127) // Conditional expression is constant (e.g. BOOST_IF_CONSTEXPR statements)
23 : #endif
24 :
25 : // These "//"'s are to prevent clang-format to ruin this nice alignment.
26 : // Thanks to reddit user u/mcmcc:
27 : // https://www.reddit.com/r/cpp/comments/so3wx9/dragonbox_110_is_released_a_fast_floattostring/hw8z26r/?context=3
28 : static constexpr char radix_100_head_table[] = {
29 : '0', '.', '1', '.', '2', '.', '3', '.', '4', '.', //
30 : '5', '.', '6', '.', '7', '.', '8', '.', '9', '.', //
31 : '1', '.', '1', '.', '1', '.', '1', '.', '1', '.', //
32 : '1', '.', '1', '.', '1', '.', '1', '.', '1', '.', //
33 : '2', '.', '2', '.', '2', '.', '2', '.', '2', '.', //
34 : '2', '.', '2', '.', '2', '.', '2', '.', '2', '.', //
35 : '3', '.', '3', '.', '3', '.', '3', '.', '3', '.', //
36 : '3', '.', '3', '.', '3', '.', '3', '.', '3', '.', //
37 : '4', '.', '4', '.', '4', '.', '4', '.', '4', '.', //
38 : '4', '.', '4', '.', '4', '.', '4', '.', '4', '.', //
39 : '5', '.', '5', '.', '5', '.', '5', '.', '5', '.', //
40 : '5', '.', '5', '.', '5', '.', '5', '.', '5', '.', //
41 : '6', '.', '6', '.', '6', '.', '6', '.', '6', '.', //
42 : '6', '.', '6', '.', '6', '.', '6', '.', '6', '.', //
43 : '7', '.', '7', '.', '7', '.', '7', '.', '7', '.', //
44 : '7', '.', '7', '.', '7', '.', '7', '.', '7', '.', //
45 : '8', '.', '8', '.', '8', '.', '8', '.', '8', '.', //
46 : '8', '.', '8', '.', '8', '.', '8', '.', '8', '.', //
47 : '9', '.', '9', '.', '9', '.', '9', '.', '9', '.', //
48 : '9', '.', '9', '.', '9', '.', '9', '.', '9', '.' //
49 : };
50 :
51 22 : static void print_1_digit(std::uint32_t n, char* buffer) noexcept
52 : {
53 22 : *buffer = char('0' + n);
54 22 : }
55 :
56 334 : static void print_2_digits(std::uint32_t n, char* buffer) noexcept
57 : {
58 334 : std::memcpy(buffer, radix_table + n * 2, 2);
59 334 : }
60 :
61 : // These digit generation routines are inspired by James Anhalt's itoa algorithm:
62 : // https://github.com/jeaiii/itoa
63 : // The main idea is for given n, find y such that floor(10^k * y / 2^32) = n holds,
64 : // where k is an appropriate integer depending on the length of n.
65 : // For example, if n = 1234567, we set k = 6. In this case, we have
66 : // floor(y / 2^32) = 1,
67 : // floor(10^2 * ((10^0 * y) mod 2^32) / 2^32) = 23,
68 : // floor(10^2 * ((10^2 * y) mod 2^32) / 2^32) = 45, and
69 : // floor(10^2 * ((10^4 * y) mod 2^32) / 2^32) = 67.
70 : // See https://jk-jeon.github.io/posts/2022/02/jeaiii-algorithm/ for more explanation.
71 :
72 : BOOST_FORCEINLINE static void print_9_digits(std::uint32_t s32, int& exponent,
73 : char*& buffer) noexcept
74 : {
75 : // -- IEEE-754 binary32
76 : // Since we do not cut trailing zeros in advance, s32 must be of 6~9 digits
77 : // unless the original input was subnormal.
78 : // In particular, when it is of 9 digits it shouldn't have any trailing zeros.
79 : // -- IEEE-754 binary64
80 : // In this case, s32 must be of 7~9 digits unless the input is subnormal,
81 : // and it shouldn't have any trailing zeros if it is of 9 digits.
82 440 : if (s32 >= 100000000)
83 : {
84 : // 9 digits.
85 : // 1441151882 = ceil(2^57 / 1'0000'0000) + 1
86 0 : auto prod = s32 * std::uint64_t(1441151882);
87 0 : prod >>= 25;
88 0 : std::memcpy(buffer, radix_100_head_table + std::uint32_t(prod >> 32) * 2, 2);
89 :
90 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
91 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
92 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
93 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 4);
94 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
95 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 6);
96 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
97 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 8);
98 :
99 0 : exponent += 8;
100 0 : buffer += 10;
101 : }
102 440 : else if (s32 >= 1000000)
103 : {
104 : // 7 or 8 digits.
105 : // 281474978 = ceil(2^48 / 100'0000) + 1
106 0 : auto prod = s32 * std::uint64_t(281474978);
107 0 : prod >>= 16;
108 0 : const auto head_digits = std::uint32_t(prod >> 32);
109 : // If s32 is of 8 digits, increase the exponent by 7.
110 : // Otherwise, increase it by 6.
111 0 : exponent += static_cast<int>(6 + unsigned(head_digits >= 10));
112 :
113 : // Write the first digit and the decimal point.
114 0 : std::memcpy(buffer, radix_100_head_table + head_digits * 2, 2);
115 : // This third character may be overwritten later, but we don't care.
116 0 : buffer[2] = radix_table[head_digits * 2 + 1];
117 :
118 : // Remaining 6 digits are all zero?
119 0 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 1000000))
120 : {
121 : // The number of characters actually need to be written is:
122 : // 1, if only the first digit is nonzero, which means that either s32 is of 7
123 : // digits or it is of 8 digits but the second digit is zero, or
124 : // 3, otherwise.
125 : // Note that buffer[2] is never '0' if s32 is of 7 digits, because the input is
126 : // never zero.
127 0 : buffer += (1 + (unsigned(head_digits >= 10) & unsigned(buffer[2] > '0')) * 2);
128 : }
129 : else
130 : {
131 : // At least one of the remaining 6 digits are nonzero.
132 : // After this adjustment, now the first destination becomes buffer + 2.
133 0 : buffer += unsigned(head_digits >= 10);
134 :
135 : // Obtain the next two digits.
136 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
137 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
138 :
139 : // Remaining 4 digits are all zero?
140 0 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 10000))
141 : {
142 0 : buffer += (3 + unsigned(buffer[3] > '0'));
143 : }
144 : else
145 : {
146 : // At least one of the remaining 4 digits are nonzero.
147 :
148 : // Obtain the next two digits.
149 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
150 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 4);
151 :
152 : // Remaining 2 digits are all zero?
153 0 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 100))
154 : {
155 0 : buffer += (5 + unsigned(buffer[5] > '0'));
156 : }
157 : else
158 : {
159 : // Obtain the last two digits.
160 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
161 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 6);
162 :
163 0 : buffer += (7 + unsigned(buffer[7] > '0'));
164 : }
165 : }
166 : }
167 : }
168 440 : else if (s32 >= 10000)
169 : {
170 : // 5 or 6 digits.
171 : // 429497 = ceil(2^32 / 1'0000)
172 0 : auto prod = s32 * std::uint64_t(429497);
173 0 : const auto head_digits = std::uint32_t(prod >> 32);
174 :
175 : // If s32 is of 6 digits, increase the exponent by 5.
176 : // Otherwise, increase it by 4.
177 0 : exponent += static_cast<int>(4 + unsigned(head_digits >= 10));
178 :
179 : // Write the first digit and the decimal point.
180 0 : std::memcpy(buffer, radix_100_head_table + head_digits * 2, 2);
181 : // This third character may be overwritten later but we don't care.
182 0 : buffer[2] = radix_table[head_digits * 2 + 1];
183 :
184 : // Remaining 4 digits are all zero?
185 0 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 10000))
186 : {
187 : // The number of characters actually written is 1 or 3, similarly to the case of
188 : // 7 or 8 digits.
189 0 : buffer += (1 + (unsigned(head_digits >= 10) & unsigned(buffer[2] > '0')) * 2);
190 : }
191 : else
192 : {
193 : // At least one of the remaining 4 digits are nonzero.
194 : // After this adjustment, now the first destination becomes buffer + 2.
195 0 : buffer += unsigned(head_digits >= 10);
196 :
197 : // Obtain the next two digits.
198 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
199 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
200 :
201 : // Remaining 2 digits are all zero?
202 0 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 100))
203 : {
204 0 : buffer += (3 + unsigned(buffer[3] > '0'));
205 : }
206 : else
207 : {
208 : // Obtain the last two digits.
209 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
210 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 4);
211 :
212 0 : buffer += (5 + unsigned(buffer[5] > '0'));
213 : }
214 : }
215 : }
216 440 : else if (s32 >= 100)
217 : {
218 : // 3 or 4 digits.
219 : // 42949673 = ceil(2^32 / 100)
220 14 : auto prod = s32 * std::uint64_t(42949673);
221 14 : const auto head_digits = std::uint32_t(prod >> 32);
222 :
223 : // If s32 is of 4 digits, increase the exponent by 3.
224 : // Otherwise, increase it by 2.
225 14 : exponent += (2 + int(head_digits >= 10));
226 :
227 : // Write the first digit and the decimal point.
228 14 : std::memcpy(buffer, radix_100_head_table + head_digits * 2, 2);
229 : // This third character may be overwritten later but we don't care.
230 14 : buffer[2] = radix_table[head_digits * 2 + 1];
231 :
232 : // Remaining 2 digits are all zero?
233 14 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 100))
234 : {
235 : // The number of characters actually written is 1 or 3, similarly to the case of
236 : // 7 or 8 digits.
237 0 : buffer += (1 + (unsigned(head_digits >= 10) & unsigned(buffer[2] > '0')) * 2);
238 : }
239 : else
240 : {
241 : // At least one of the remaining 2 digits are nonzero.
242 : // After this adjustment, now the first destination becomes buffer + 2.
243 14 : buffer += unsigned(head_digits >= 10);
244 :
245 : // Obtain the last two digits.
246 14 : prod = std::uint32_t(prod) * std::uint64_t(100);
247 14 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
248 :
249 14 : buffer += (3 + unsigned(buffer[3] > '0'));
250 : }
251 : }
252 : else
253 : {
254 : // 1 or 2 digits.
255 : // If s32 is of 2 digits, increase the exponent by 1.
256 426 : exponent += int(s32 >= 10);
257 :
258 : // Write the first digit and the decimal point.
259 426 : std::memcpy(buffer, radix_100_head_table + s32 * 2, 2);
260 : // This third character may be overwritten later but we don't care.
261 426 : buffer[2] = radix_table[s32 * 2 + 1];
262 :
263 : // The number of characters actually written is 1 or 3, similarly to the case of
264 : // 7 or 8 digits.
265 426 : buffer += (1 + (unsigned(s32 >= 10) & unsigned(buffer[2] > '0')) * 2);
266 : }
267 440 : }
268 :
269 444 : std::size_t dragon_box_print_chars(const std::uint64_t significand, int exponent, char* first, char* last) noexcept
270 : {
271 444 : BOOST_ASSERT( detail::max_number_chars >= std::size_t(last - first) );
272 :
273 444 : auto buffer = first;
274 : // Print significand by decomposing it into a 9-digit block and a 8-digit block.
275 : std::uint32_t first_block;
276 444 : std::uint32_t second_block {};
277 : bool no_second_block;
278 :
279 444 : if (significand >= 100000000)
280 : {
281 4 : first_block = std::uint32_t(significand / 100000000);
282 4 : second_block = std::uint32_t(significand) - first_block * 100000000;
283 4 : exponent += 8;
284 4 : no_second_block = (second_block == 0);
285 : }
286 : else
287 : {
288 440 : first_block = std::uint32_t(significand);
289 440 : no_second_block = true;
290 : }
291 :
292 444 : if (no_second_block)
293 : {
294 : print_9_digits(first_block, exponent, buffer);
295 : }
296 : else
297 : {
298 : // We proceed similarly to print_9_digits(), but since we do not need to remove
299 : // trailing zeros, the procedure is a bit simpler.
300 4 : if (first_block >= 100000000)
301 : {
302 : // The input is of 17 digits, thus there should be no trailing zero at all.
303 : // The first block is of 9 digits.
304 : // 1441151882 = ceil(2^57 / 1'0000'0000) + 1
305 1 : auto prod = first_block * std::uint64_t(1441151882);
306 1 : prod >>= 25;
307 1 : std::memcpy(buffer, radix_100_head_table + std::uint32_t(prod >> 32) * 2, 2);
308 1 : prod = std::uint32_t(prod) * std::uint64_t(100);
309 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
310 1 : prod = std::uint32_t(prod) * std::uint64_t(100);
311 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 4);
312 1 : prod = std::uint32_t(prod) * std::uint64_t(100);
313 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 6);
314 1 : prod = std::uint32_t(prod) * std::uint64_t(100);
315 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 8);
316 :
317 : // The second block is of 8 digits.
318 : // 281474978 = ceil(2^48 / 100'0000) + 1
319 1 : prod = second_block * std::uint64_t(281474978);
320 1 : prod >>= 16;
321 1 : prod += 1;
322 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 10);
323 1 : prod = std::uint32_t(prod) * std::uint64_t(100);
324 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 12);
325 1 : prod = std::uint32_t(prod) * std::uint64_t(100);
326 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 14);
327 1 : prod = std::uint32_t(prod) * std::uint64_t(100);
328 1 : print_2_digits(std::uint32_t(prod >> 32), buffer + 16);
329 :
330 1 : exponent += 8;
331 1 : buffer += 18;
332 : }
333 : else
334 : {
335 3 : if (first_block >= 1000000)
336 : {
337 : // 7 or 8 digits.
338 : // 281474978 = ceil(2^48 / 100'0000) + 1
339 3 : auto prod = first_block * std::uint64_t(281474978);
340 3 : prod >>= 16;
341 3 : const auto head_digits = std::uint32_t(prod >> 32);
342 :
343 3 : std::memcpy(buffer, radix_100_head_table + head_digits * 2, 2);
344 3 : buffer[2] = radix_table[head_digits * 2 + 1];
345 :
346 3 : exponent += static_cast<int>(6 + unsigned(head_digits >= 10));
347 3 : buffer += unsigned(head_digits >= 10);
348 :
349 : // Print remaining 6 digits.
350 3 : prod = std::uint32_t(prod) * std::uint64_t(100);
351 3 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
352 3 : prod = std::uint32_t(prod) * std::uint64_t(100);
353 3 : print_2_digits(std::uint32_t(prod >> 32), buffer + 4);
354 3 : prod = std::uint32_t(prod) * std::uint64_t(100);
355 3 : print_2_digits(std::uint32_t(prod >> 32), buffer + 6);
356 :
357 3 : buffer += 8;
358 : }
359 0 : else if (first_block >= 10000)
360 : {
361 : // 5 or 6 digits.
362 : // 429497 = ceil(2^32 / 1'0000)
363 0 : auto prod = first_block * std::uint64_t(429497);
364 0 : const auto head_digits = std::uint32_t(prod >> 32);
365 :
366 0 : std::memcpy(buffer, radix_100_head_table + head_digits * 2, 2);
367 0 : buffer[2] = radix_table[head_digits * 2 + 1];
368 :
369 0 : exponent += static_cast<int>(4 + unsigned(head_digits >= 10));
370 0 : buffer += unsigned(head_digits >= 10);
371 :
372 : // Print remaining 4 digits.
373 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
374 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
375 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
376 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 4);
377 :
378 0 : buffer += 6;
379 : }
380 0 : else if (first_block >= 100)
381 : {
382 : // 3 or 4 digits.
383 : // 42949673 = ceil(2^32 / 100)
384 0 : auto prod = first_block * std::uint64_t(42949673);
385 0 : const auto head_digits = std::uint32_t(prod >> 32);
386 :
387 0 : std::memcpy(buffer, radix_100_head_table + head_digits * 2, 2);
388 0 : buffer[2] = radix_table[head_digits * 2 + 1];
389 :
390 0 : exponent += static_cast<int>(2 + unsigned(head_digits >= 10));
391 0 : buffer += unsigned(head_digits >= 10);
392 :
393 : // Print remaining 2 digits.
394 0 : prod = std::uint32_t(prod) * std::uint64_t(100);
395 0 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
396 :
397 0 : buffer += 4;
398 : }
399 : else
400 : {
401 : // 1 or 2 digits.
402 0 : std::memcpy(buffer, radix_100_head_table + first_block * 2, 2);
403 0 : buffer[2] = radix_table[first_block * 2 + 1];
404 :
405 0 : exponent += (first_block >= 10);
406 0 : buffer += (2 + unsigned(first_block >= 10));
407 : }
408 :
409 : // Next, print the second block.
410 : // The second block is of 8 digits, but we may have trailing zeros.
411 : // 281474978 = ceil(2^48 / 100'0000) + 1
412 3 : auto prod = second_block * std::uint64_t(281474978);
413 3 : prod >>= 16;
414 3 : prod += 1;
415 3 : print_2_digits(std::uint32_t(prod >> 32), buffer);
416 :
417 : // Remaining 6 digits are all zero?
418 3 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 1000000))
419 : {
420 0 : buffer += (1 + unsigned(buffer[1] > '0'));
421 : }
422 : else
423 : {
424 : // Obtain the next two digits.
425 3 : prod = std::uint32_t(prod) * std::uint64_t(100);
426 3 : print_2_digits(std::uint32_t(prod >> 32), buffer + 2);
427 :
428 : // Remaining 4 digits are all zero?
429 3 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 10000))
430 : {
431 0 : buffer += (3 + unsigned(buffer[3] > '0'));
432 : }
433 : else
434 : {
435 : // Obtain the next two digits.
436 3 : prod = std::uint32_t(prod) * std::uint64_t(100);
437 3 : print_2_digits(std::uint32_t(prod >> 32), buffer + 4);
438 :
439 : // Remaining 2 digits are all zero?
440 3 : if (std::uint32_t(prod) <= std::uint32_t((std::uint64_t(1) << 32) / 100))
441 : {
442 0 : buffer += (5 + unsigned(buffer[5] > '0'));
443 : }
444 : else
445 : {
446 : // Obtain the last two digits.
447 3 : prod = std::uint32_t(prod) * std::uint64_t(100);
448 3 : print_2_digits(std::uint32_t(prod >> 32), buffer + 6);
449 3 : buffer += (7 + unsigned(buffer[7] > '0'));
450 : }
451 : }
452 : }
453 : }
454 : }
455 444 : if (exponent < 0)
456 : {
457 85 : std::memcpy(buffer, "E-", 2);
458 85 : buffer += 2;
459 85 : exponent = -exponent;
460 : }
461 359 : else if (exponent == 0)
462 : {
463 153 : std::memcpy(buffer, "E0", 2);
464 153 : return 2 + (buffer - first);
465 : }
466 : else
467 : {
468 206 : std::memcpy(buffer, "E+", 2);
469 206 : buffer += 2;
470 : }
471 :
472 291 : if (exponent >= 100)
473 : {
474 : // d1 = exponent / 10; d2 = exponent % 10;
475 : // 6554 = ceil(2^16 / 10)
476 22 : auto prod = std::uint32_t(exponent) * std::uint32_t(6554);
477 22 : auto d1 = prod >> 16;
478 22 : prod = std::uint16_t(prod) * std::uint32_t(5); // * 10
479 22 : auto d2 = prod >> 15; // >> 16
480 22 : print_2_digits(d1, buffer);
481 22 : print_1_digit(d2, buffer + 2);
482 22 : buffer += 3;
483 : }
484 : else
485 : {
486 269 : print_2_digits(static_cast<std::uint32_t>(exponent), buffer);
487 269 : buffer += 2;
488 : }
489 :
490 291 : return buffer - first;
491 : }
492 :
493 : #ifdef BOOST_MSVC
494 : # pragma warning(pop)
495 : #endif
496 :
497 : } // namespace to_chars_detail
498 : } // namespace detail
499 : } // namespace json
500 : } // namespace boost
|
