DAW JSON Link
Loading...
Searching...
No Matches
daw_json_parse_real.h
Go to the documentation of this file.
1// Copyright (c) Darrell Wright
2//
3// Distributed under the Boost Software License, Version 1.0. (See accompanying
4// file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
5//
6// Official repository: https://github.com/beached/daw_json_link
7//
8
9#pragma once
10
12
22
23#include <daw/daw_cxmath.h>
24#include <daw/daw_likely.h>
25#include <daw/daw_not_null.h>
26#include <daw/daw_restrict.h>
27#include <daw/daw_utility.h>
28
29#include <cstddef>
30#include <cstdint>
31#include <limits>
32#include <type_traits>
33
34namespace daw::json {
35 inline namespace DAW_JSON_VER {
36 namespace json_details {
37 template<bool skip_end_check, typename Unsigned>
38 DAW_ATTRIB_FLATINLINE constexpr void
39 parse_digits_until_last( daw::not_null<char const *> first,
40 daw::not_null<char const *> const last,
41 Unsigned &DAW_RESTRICT v ) {
42 auto value = v;
43 if constexpr( skip_end_check ) {
44 auto dig = parse_digit( *first );
45 while( dig < 10U ) {
46 value *= 10U;
47 value += dig;
48 ++first;
49 dig = parse_digit( *first );
50 }
51 } else {
52 while( DAW_LIKELY( first < last ) ) {
53 value *= 10U;
54 value += parse_digit( *first );
55 ++first;
56 }
57 }
58 v = value;
59 }
60
61 template<typename Unsigned>
62 constexpr std::size_t count_digits( Unsigned value ) {
63 if( DAW_LIKELY( value == 0 ) ) {
64 DAW_LIKELY_BRANCH
65 return 0;
66 }
67 if constexpr( sizeof( Unsigned ) <= sizeof( std::uint64_t ) ) {
68 if( value >= 10000000000000000000ULL ) {
69 return 20;
70 }
71 if( value >= 1000000000000000000ULL ) {
72 return 19;
73 }
74 if( value >= 100000000000000000ULL ) {
75 return 18;
76 }
77 if( value >= 10000000000000000ULL ) {
78 return 17;
79 }
80 if( value >= 1000000000000000ULL ) {
81 return 16;
82 }
83 if( value >= 100000000000000ULL ) {
84 return 15;
85 }
86 if( value >= 10000000000000ULL ) {
87 return 14;
88 }
89 if( value >= 1000000000000ULL ) {
90 return 13;
91 }
92 if( value >= 100000000000ULL ) {
93 return 12;
94 }
95 if( value >= 10000000000ULL ) {
96 return 11;
97 }
98 if( value >= 1000000000ULL ) {
99 return 10;
100 }
101 if( value >= 100000000ULL ) {
102 return 9;
103 }
104 if( value >= 10000000ULL ) {
105 return 8;
106 }
107 if( value >= 1000000ULL ) {
108 return 7;
109 }
110 if( value >= 100000ULL ) {
111 return 6;
112 }
113 if( value >= 10000ULL ) {
114 return 5;
115 }
116 if( value >= 1000ULL ) {
117 return 4;
118 }
119 if( value >= 100ULL ) {
120 return 3;
121 }
122 if( value >= 10ULL ) {
123 return 2;
124 }
125 return 1;
126 } else {
127 std::size_t count = 1;
128 value /= Unsigned{ 10U };
129 while( value > 0 ) {
130 ++count;
131 value /= Unsigned{ 10U };
132 }
133 return count;
134 }
135 }
136
137 template<typename Unsigned>
138 [[nodiscard]] DAW_ATTRIB_FLATINLINE constexpr daw::not_null<char const *>
139 parse_digits_while_number( daw::not_null<char const *> first,
140 daw::not_null<char const *> const last,
141 Unsigned &DAW_RESTRICT v ) {
142
143 if( DAW_UNLIKELY( first >= last ) ) {
144 DAW_UNLIKELY_BRANCH
145 return first;
146 }
147 auto const sig_dig_in_use = count_digits( v );
148
149 auto const last_pos =
150 (std::min)( { std::distance( first, last ),
151 static_cast<std::ptrdiff_t>( daw::digits10<Unsigned> -
152 sig_dig_in_use ) } );
153 daw::not_null const new_last = std::next( first.get( ), last_pos );
154
155 auto value = v;
156
157 unsigned dig = 10U;
158 do {
159 dig = parse_digit( *first );
160 if( dig >= 10U ) {
161 break;
162 }
163 value *= 10U;
164 value += dig;
165 ++first;
166 } while( first < new_last );
167 if( first < last and dig < 10U ) {
168 ++first;
169 }
170 while( first < last ) {
171 dig = parse_digit( *first );
172 if( dig >= 10U ) {
173 break;
174 }
175 ++first;
176 }
177 v = value;
178 return first;
179 }
180
183 template<typename ParseState, typename Result,
184 typename max_storage_digits>
185 [[nodiscard]] constexpr bool should_use_fallback(
186 [[maybe_unused]] daw::not_null<char const *> whole_first,
187 [[maybe_unused]] daw::not_null<char const *> const whole_last,
188 [[maybe_unused]] char const *fract_first,
189 [[maybe_unused]] char const *fract_last ) {
190 if constexpr( std::is_floating_point_v<Result> and
191 ParseState::precise_ieee754 ) {
192 return DAW_UNLIKELY(
193 ( ( whole_last - whole_first ) +
194 ( fract_first ? fract_last - fract_first : 0 ) ) >
195 max_storage_digits::value );
196 } else {
197 return false;
198 }
199 }
200
201 inline constexpr std::size_t eisellemire_max_digits = 19;
202
203 template<typename Signed>
204 [[nodiscard]] constexpr bool
205 append_discarded_digits( char const *first, char const *last,
206 std::uint64_t &significant_digits,
207 Signed &exponent ) {
208 if( first == nullptr ) {
209 return false;
210 }
211
212 auto retained_digits = count_digits( significant_digits );
213 bool discarded_nonzero = false;
214 while( first < last ) {
215 auto const digit = parse_digit( *first );
216 if( digit >= 10U ) {
217 break;
218 }
219 ++first;
220 if( retained_digits < eisellemire_max_digits ) {
221 significant_digits =
222 significant_digits * std::uint64_t{ 10 } + digit;
223 // Leading zeroes do not consume significant-digit capacity.
224 if( significant_digits != 0 ) {
225 ++retained_digits;
226 }
227 if( exponent > std::numeric_limits<Signed>::lowest( ) ) {
228 --exponent;
229 }
230 } else {
231 discarded_nonzero |= digit != 0;
232 }
233 }
234 return discarded_nonzero;
235 }
236
237 template<typename Result, typename Signed>
238 [[nodiscard]] constexpr Result parse_truncated_lemire(
239 bool negative, Signed exponent, std::uint64_t significant_digits,
240 bool discarded_nonzero, daw::not_null<char const *> number_first,
241 daw::not_null<char const *> number_last ) {
242 auto const lower = json_details::parse_real_eisellemire<Result>(
243 negative, exponent, significant_digits );
244 if( not discarded_nonzero ) {
245 return lower;
246 }
247
248 // significant_digits contains at most 19 decimal digits, so adding
249 // one cannot overflow a uint64_t.
250 auto const upper = json_details::parse_real_eisellemire<Result>(
251 negative, exponent, significant_digits + std::uint64_t{ 1 } );
252 if( lower == upper ) {
253 return lower;
254 }
255
256 return json_details::parse_json_real_exact<Result>(
257 negative, number_first, number_last );
258 }
259
260 template<typename Result, typename ParseState>
261 [[nodiscard]] DAW_ATTRIB_INLINE static constexpr Result
262 parse_real_known( ParseState &parse_state ) {
263 // [-]WHOLE[.FRACTION][(e|E)[+|-]EXPONENT]
265 parse_state.has_more( ) and
266 parse_policy_details::is_number_start( parse_state.front( ) ),
267 ErrorReason::InvalidNumberStart,
268 parse_state );
269
270 daw::not_null<char const *> whole_first = parse_state.first;
271 char const *whole_last = parse_state.class_first
272 ? parse_state.class_first
273 : parse_state.class_last;
274 char const *fract_first =
275 parse_state.class_first ? parse_state.class_first + 1 : nullptr;
276 char const *fract_last = parse_state.class_last;
277 char const *exp_first =
278 parse_state.class_last ? parse_state.class_last + 1 : nullptr;
279 daw::not_null<char const *> const exp_last = parse_state.last;
280
281 if( parse_state.class_first == nullptr ) {
282 if( parse_state.class_last == nullptr ) {
283 whole_last = parse_state.last;
284 } else {
285 whole_last = parse_state.class_last;
286 }
287 } else if( parse_state.class_last == nullptr ) {
288 fract_last = parse_state.last;
289 }
290 char const *const all_whole_last = whole_last;
291 char const *const all_fract_first = fract_first;
292 char const *const all_fract_last = fract_last;
293
294 using max_storage_digits = daw::constant<static_cast<std::ptrdiff_t>(
295 daw::digits10<std::uint64_t> )>;
296
297 Result const sign = [&] {
298 if( *whole_first == '-' ) {
299 ++whole_first;
300 return static_cast<Result>( -1.0 );
301 }
302 return static_cast<Result>( 1.0 );
303 }( );
304
305 bool use_fallback =
306 should_use_fallback<ParseState, Result, max_storage_digits>(
307 whole_first, whole_last, fract_first, fract_last );
308
309 using max_exponent = daw::constant<static_cast<std::ptrdiff_t>(
310 daw::max_digits10<Result> + 1 )>;
311 using unsigned_t =
312 daw::conditional_t<max_storage_digits::value >= max_exponent::value,
313 std::uint64_t,
314 Result>;
315
316 using signed_t =
317 typename daw::conditional_t<std::is_floating_point_v<unsigned_t>,
318 daw::traits::identity<unsigned_t>,
319 std::make_signed<unsigned_t>>::type;
320 std::intmax_t whole_exponent_available = whole_last - whole_first;
321 std::intmax_t fract_exponent_available =
322 fract_first ? fract_last - fract_first : 0;
323 signed_t exponent = 0;
324
325 if( whole_exponent_available > max_exponent::value ) {
326 whole_last = whole_first + max_exponent::value;
327 whole_exponent_available -= max_exponent::value;
328 fract_exponent_available = 0;
329 fract_first = nullptr;
330 exponent = whole_exponent_available;
331 } else {
332 whole_exponent_available =
333 max_exponent::value - whole_exponent_available;
334 if constexpr( ParseState::precise_ieee754 ) {
335 use_fallback |= DAW_UNLIKELY( fract_exponent_available >
336 whole_exponent_available );
337 }
338 if( whole_exponent_available < fract_exponent_available ) {
339 fract_exponent_available = whole_exponent_available;
340 }
341 exponent = -fract_exponent_available;
342 fract_last = fract_first + fract_exponent_available;
343 }
344
345 unsigned_t significant_digits = 0;
346 parse_digits_until_last<( ParseState::is_zero_terminated_string or
347 ParseState::is_unchecked_input )>(
348 whole_first, whole_last, significant_digits );
349 if( fract_first ) {
350 parse_digits_until_last<( ParseState::is_zero_terminated_string or
351 ParseState::is_unchecked_input )>(
352 fract_first, fract_last, significant_digits );
353 }
354
355 if( exp_first and ( exp_last - exp_first ) > 0 ) {
356 signed_t const exp_sign = [&] {
357 switch( *exp_first ) {
358 case '-':
359 ++exp_first;
361 exp_first < exp_last and parse_digit( *exp_first ) < 10U,
362 ErrorReason::InvalidNumber );
363 return -1;
364 case '+':
365 ++exp_first;
367 exp_first < exp_last and parse_digit( *exp_first ) < 10U,
368 ErrorReason::InvalidNumber );
369 return 1;
370 default:
371 daw_json_assert_weak( parse_digit( *exp_first ) < 10U,
372 ErrorReason::InvalidNumber );
373 return 1;
374 }
375 }( );
376 exponent += to_signed(
377 [&] {
378 unsigned_t exp_result = 0;
379 if constexpr( ParseState::is_zero_terminated_string ) {
380 auto dig = parse_digit( *exp_first );
381 while( dig < 10U ) {
382 ++exp_first;
383 exp_result *= 10U;
384 exp_result += dig;
385 dig = parse_digit( *exp_first );
386 }
387 } else {
388 if( exp_first < exp_last ) {
389 auto dig = parse_digit( *exp_first );
390 do {
391 if( dig >= 10U ) {
392 break;
393 }
394 ++exp_first;
395 exp_result *= 10U;
396 exp_result += dig;
397 if( exp_first >= exp_last ) {
398 break;
399 }
400 dig = parse_digit( *exp_first );
401 } while( true );
402 }
403 }
404 return exp_result;
405 }( ),
406 exp_sign );
407 }
408 if constexpr( std::is_floating_point_v<Result> and
409 ParseState::precise_ieee754 ) {
410 // On std floating point types, check for conditions that cannot be
411 // precisely calculated using the normal method and use the fallback
412 // method(usually strtod/from_chars)
413 use_fallback |= exponent > 22;
414 use_fallback |= exponent < -22;
415 if constexpr( std::is_same_v<Result, float> or
416 std::is_same_v<Result, double> ) {
417 use_fallback |=
418 significant_digits >
419 ( std::uint64_t{ 1 } << std::numeric_limits<Result>::digits );
420 }
421 if( std::is_same_v<Result, long double> or
422 DAW_UNLIKELY( use_fallback ) ) {
423 if constexpr( std::is_same_v<Result, float> or
424 std::is_same_v<Result, double> ) {
425 bool discarded_nonzero = append_discarded_digits(
426 whole_last, all_whole_last, significant_digits, exponent );
427 if( all_fract_first != nullptr ) {
428 auto const *discarded_fract_first =
429 fract_first == nullptr ? all_fract_first : fract_last;
430 discarded_nonzero |=
431 append_discarded_digits( discarded_fract_first,
432 all_fract_last,
433 significant_digits,
434 exponent );
435 }
436 return parse_truncated_lemire<Result>( sign < Result{ 0 },
437 exponent,
438 significant_digits,
439 discarded_nonzero,
440 parse_state.first,
441 parse_state.last );
442 } else {
443 static_assert( std::is_same_v<Result, long double> );
444 return json_details::parse_with_strtod<Result>(
445 parse_state.first, parse_state.last );
446 }
447 }
448 }
449 return sign *
450 power10<Result>( ParseState::exec_tag,
451 static_cast<Result>( significant_digits ),
452 exponent );
453 }
454
455 template<typename Result, typename ParseState>
456 [[nodiscard]] DAW_ATTRIB_INLINE static constexpr Result
457 parse_real_unknown( ParseState &parse_state ) {
458 // [-]WHOLE[.FRACTION][(e|E)[+|-]EXPONENT]
460 parse_state.has_more( ) and
461 parse_policy_details::is_number_start( parse_state.front( ) ),
462 ErrorReason::InvalidNumberStart,
463 parse_state );
464
465 [[maybe_unused]] daw::not_null<char const *> const orig_first =
466 parse_state.first;
467
468 auto const sign = static_cast<Result>(
469 parse_policy_details::validate_signed_first( parse_state ) );
470
471 using max_storage_digits = daw::constant<static_cast<std::int64_t>(
472 daw::digits10<std::uint64_t> )>;
473 using max_exponent = daw::constant<static_cast<std::int64_t>(
474 daw::max_digits10<Result> + 1 )>;
475 using unsigned_t =
476 daw::conditional_t<max_storage_digits::value >= max_exponent::value,
477 std::uint64_t,
478 Result>;
479 using signed_t =
480 daw::conditional_t<max_storage_digits::value >= max_exponent::value,
481 std::int64_t,
482 Result>;
483
484 daw::not_null<char const *> first = parse_state.first;
485 daw::not_null<char const *> const last = parse_state.last;
486 daw::not_null<char const *> const whole_last =
487 parse_state.first +
488 (std::min)( { parse_state.last - parse_state.first,
489 static_cast<std::ptrdiff_t>( max_exponent::value ) } );
490
491 unsigned_t significant_digits = 0;
492 char const *discarded_whole_first = nullptr;
493 char const *discarded_whole_last = nullptr;
494 char const *discarded_fract_first = nullptr;
495 char const *discarded_fract_last = nullptr;
496 daw::not_null<char const *> last_char = parse_digits_while_number(
497 first.get( ), whole_last.get( ), significant_digits );
498 auto const sig_digit_count = last_char - parse_state.first;
499 bool use_strtod =
500 std::is_floating_point_v<Result> and ParseState::precise_ieee754 and
501 DAW_UNLIKELY( sig_digit_count > max_storage_digits::value );
502 signed_t exponent_p1 = [&] {
503 if( DAW_UNLIKELY( last_char >= whole_last ) ) {
504 if constexpr( std::is_floating_point_v<Result> and
505 ParseState::precise_ieee754 ) {
506 use_strtod = true;
507 }
508 // We have sig digits we cannot parse because there isn't enough
509 // room in a std::uint64_t
510 daw::not_null<char const *> ptr =
511 skip_digits<( ParseState::is_zero_terminated_string or
512 ParseState::is_unchecked_input )>( last_char,
513 last );
514 discarded_whole_first = last_char.get( );
515 discarded_whole_last = ptr.get( );
516 auto const diff = ptr - last_char;
517
518 last_char = ptr;
519 if( significant_digits == 0 ) {
520 return signed_t{ 0 };
521 }
522 return static_cast<signed_t>( diff );
523 }
524 return signed_t{ 0 };
525 }( );
526
527 first = last_char;
528 if( ( ParseState::is_zero_terminated_string or
529 ParseState::is_unchecked_input or
530 DAW_LIKELY( first < parse_state.last ) ) and
531 *first == '.' ) {
532 ++first;
533 if( exponent_p1 != 0 ) {
534 if( first < parse_state.last ) {
535 auto const discarded_first = first;
536 first =
537 skip_digits<( ParseState::is_zero_terminated_string or
538 ParseState::is_unchecked_input )>( first, last );
539 discarded_fract_first = discarded_first.get( );
540 discarded_fract_last = first.get( );
541 }
542 } else {
543 daw::not_null<char const *> fract_last =
544 first + (std::min)( parse_state.last - first,
545 static_cast<std::ptrdiff_t>(
546 max_exponent::value -
547 ( first - parse_state.first ) ) );
548
549 last_char = parse_digits_while_number(
550 first.get( ), fract_last.get( ), significant_digits );
551 exponent_p1 -= static_cast<signed_t>( last_char - first );
552 first = last_char;
553 if( daw::nsc_and( first >= fract_last, first < last ) ) {
554 auto new_first =
555 skip_digits<( ParseState::is_zero_terminated_string or
556 ParseState::is_unchecked_input )>( first, last );
557 discarded_fract_first = first.get( );
558 discarded_fract_last = new_first.get( );
559 if constexpr( std::is_floating_point_v<Result> and
560 ParseState::precise_ieee754 ) {
561 use_strtod |= new_first > first;
562 }
563 first = new_first;
564 }
565 }
566 }
567
568 signed_t const exponent_p2 = [&] {
569 if( ( ParseState::is_unchecked_input or first < parse_state.last ) and
570 ( ( *first | 0x20 ) == 'e' ) ) {
571 ++first;
572 signed_t const exp_sign = [&] {
573 daw_json_assert_weak( ( ParseState::is_zero_terminated_string or
574 first < parse_state.last ),
575 ErrorReason::UnexpectedEndOfData,
576 parse_state.copy( first ) );
577 switch( *first ) {
578 case '+':
579 ++first;
580 daw_json_assert_weak( ( first < parse_state.last ) and
581 ( parse_digit( *first ) < 10U ),
582 ErrorReason::InvalidNumber );
583 return signed_t{ 1 };
584 case '-':
585 ++first;
586 daw_json_assert_weak( first < parse_state.last and
587 parse_digit( *first ) < 10U,
588 ErrorReason::InvalidNumber );
589 return signed_t{ -1 };
590 default:
591 daw_json_assert_weak( parse_policy_details::is_number( *first ),
592 ErrorReason::InvalidNumber );
593 return signed_t{ 1 };
594 }
595 }( );
596 daw_json_assert_weak( first < parse_state.last,
597 ErrorReason::UnexpectedEndOfData,
598 parse_state );
599 unsigned_t exp_tmp = 0;
600 last_char =
601 parse_digits_while_number( first.get( ), last.get( ), exp_tmp );
602 first = last_char;
603 return to_signed( exp_tmp, exp_sign );
604 }
605 return signed_t{ 0 };
606 }( );
607 auto exponent = [&] {
608 if constexpr( ParseState::is_unchecked_input or
609 not std::is_floating_point_v<Result> ) {
610 return exponent_p1 + exponent_p2;
611 } else {
612 if( bool const matching_signs =
613 ( ( exponent_p1 < 0 ) == ( exponent_p2 < 0 ) );
614 not matching_signs ) {
615
616 return exponent_p1 + exponent_p2;
617 }
618 auto const s = exponent_p1 < 0 ? signed_t{ -1 } : signed_t{ 1 };
619 if( s < 0 ) {
620 if( DAW_UNLIKELY( ( daw::min_value<signed_t> - exponent_p1 ) >
621 exponent_p2 ) ) {
622 // We don't have inf, but we can just saturate it to min as it
623 // will be 0 anyways for the other result
624 return daw::min_value<signed_t>;
625 }
626 return exponent_p1 + exponent_p2;
627 }
628 auto const r = static_cast<unsigned_t>( exponent_p1 ) +
629 static_cast<unsigned_t>( exponent_p2 );
630 if( DAW_UNLIKELY(
631 r > static_cast<unsigned_t>( daw::max_value<signed_t> ) ) ) {
632 return daw::max_value<signed_t>;
633 }
634 return static_cast<signed_t>( r );
635 }
636 }( );
637 parse_state.first = first;
638
639 if constexpr( std::is_floating_point_v<Result> and
640 ParseState::precise_ieee754 ) {
641 use_strtod |= DAW_UNLIKELY( exponent > 22 );
642 use_strtod |= DAW_UNLIKELY( exponent < -22 );
643 if constexpr( std::is_same_v<Result, float> or
644 std::is_same_v<Result, double> ) {
645 use_strtod |= DAW_UNLIKELY(
646 significant_digits >
647 ( std::uint64_t{ 1 } << std::numeric_limits<Result>::digits ) );
648 }
649 if( DAW_UNLIKELY( use_strtod ) ) {
650 if constexpr( std::is_same_v<Result, float> or
651 std::is_same_v<Result, double> ) {
652 bool discarded_nonzero =
653 append_discarded_digits( discarded_whole_first,
654 discarded_whole_last,
655 significant_digits,
656 exponent );
657 discarded_nonzero |=
658 append_discarded_digits( discarded_fract_first,
659 discarded_fract_last,
660 significant_digits,
661 exponent );
662 return parse_truncated_lemire<Result>( sign < Result{ 0 },
663 exponent,
664 significant_digits,
665 discarded_nonzero,
666 orig_first,
667 first );
668 } else {
669 static_assert( std::is_same_v<Result, long double> );
670 return json_details::parse_with_strtod<Result>( orig_first,
671 first );
672 }
673 }
674 }
675 return sign *
676 power10<Result>( ParseState::exec_tag,
677 static_cast<Result>( significant_digits ),
678 exponent );
679 }
680
681 template<typename Result, bool KnownRange, typename ParseState>
682 [[nodiscard]] constexpr Result parse_real( ParseState &parse_state ) {
683 if constexpr( KnownRange ) {
684 return parse_real_known<Result>( parse_state );
685 } else {
686 return parse_real_unknown<Result>( parse_state );
687 }
688 }
689 } // namespace json_details
690 } // namespace DAW_JSON_VER
691} // namespace daw::json
#define daw_json_assert_weak(Bool,...)
Assert that Bool is true when in Checked Input mode If false pass rest of args to daw_json_error.
Customization point traits.
#define DAW_JSON_VER
The version string used in namespace definitions. Must be a valid namespace name.
Definition version.h:20