/src/boost/boost/json/detail/charconv/detail/fast_float/digit_comparison.hpp

Source (jump to first uncovered line)
// Copyright 2020-2023 Daniel Lemire
// Copyright 2023 Matt Borland
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt
//
// Derivative of: https://github.com/fastfloat/fast_float

#ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_DIGIT_COMPARISON_HPP
#define BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_DIGIT_COMPARISON_HPP

#include <boost/json/detail/charconv/detail/fast_float/float_common.hpp>
#include <boost/json/detail/charconv/detail/fast_float/bigint.hpp>
#include <boost/json/detail/charconv/detail/fast_float/ascii_number.hpp>
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <iterator>

namespace boost { namespace json { namespace detail { namespace charconv { namespace detail { namespace fast_float {

// 1e0 to 1e19
constexpr static uint64_t powers_of_ten_uint64[] = {
    1UL, 10UL, 100UL, 1000UL, 10000UL, 100000UL, 1000000UL, 10000000UL, 100000000UL,
    1000000000UL, 10000000000UL, 100000000000UL, 1000000000000UL, 10000000000000UL,
    100000000000000UL, 1000000000000000UL, 10000000000000000UL, 100000000000000000UL,
    1000000000000000000UL, 10000000000000000000UL};

// calculate the exponent, in scientific notation, of the number.
// this algorithm is not even close to optimized, but it has no practical
// effect on performance: in order to have a faster algorithm, we'd need
// to slow down performance for faster algorithms, and this is still fast.
template <typename UC>
BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
int32_t scientific_exponent(parsed_number_string_t<UC> & num) noexcept {
  uint64_t mantissa = num.mantissa;
  int32_t exponent = int32_t(num.exponent);
  while (mantissa >= 10000) {
    mantissa /= 10000;
    exponent += 4;
  }
  while (mantissa >= 100) {
    mantissa /= 100;
    exponent += 2;
  }
  while (mantissa >= 10) {
    mantissa /= 10;
    exponent += 1;
  }
  return exponent;
}

// this converts a native floating-point number to an extended-precision float.
template <typename T>
BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
adjusted_mantissa to_extended(T value) noexcept {
  using equiv_uint = typename binary_format<T>::equiv_uint;
  constexpr equiv_uint exponent_mask = binary_format<T>::exponent_mask();
  constexpr equiv_uint mantissa_mask = binary_format<T>::mantissa_mask();
  constexpr equiv_uint hidden_bit_mask = binary_format<T>::hidden_bit_mask();

  adjusted_mantissa am;
  int32_t bias = binary_format<T>::mantissa_explicit_bits() - binary_format<T>::minimum_exponent();
  equiv_uint bits;
#ifdef BOOST_JSON_HAS_BIT_CAST
  bits = std::bit_cast<equiv_uint>(value);
#else
  ::memcpy(&bits, &value, sizeof(T));
#endif
  if ((bits & exponent_mask) == 0) {
    // denormal
    am.power2 = 1 - bias;
    am.mantissa = bits & mantissa_mask;
  } else {
    // normal
    am.power2 = int32_t((bits & exponent_mask) >> binary_format<T>::mantissa_explicit_bits());
    am.power2 -= bias;
    am.mantissa = (bits & mantissa_mask) | hidden_bit_mask;
  }

  return am;
}

// get the extended precision value of the halfway point between b and b+u.
// we are given a native float that represents b, so we need to adjust it
// halfway between b and b+u.
template <typename T>
BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
adjusted_mantissa to_extended_halfway(T value) noexcept {
  adjusted_mantissa am = to_extended(value);
  am.mantissa <<= 1;
  am.mantissa += 1;
  am.power2 -= 1;
  return am;
}

// round an extended-precision float to the nearest machine float.
template <typename T, typename callback>
BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
void round(adjusted_mantissa& am, callback cb) noexcept {
  int32_t mantissa_shift = 64 - binary_format<T>::mantissa_explicit_bits() - 1;
  if (-am.power2 >= mantissa_shift) {
    // have a denormal float
    int32_t shift = -am.power2 + 1;
    cb(am, std::min<int32_t>(shift, 64));
    // check for round-up: if rounding-nearest carried us to the hidden bit.
    am.power2 = (am.mantissa < (uint64_t(1) << binary_format<T>::mantissa_explicit_bits())) ? 0 : 1;
    return;
  }

  // have a normal float, use the default shift.
  cb(am, mantissa_shift);

  // check for carry
  if (am.mantissa >= (uint64_t(2) << binary_format<T>::mantissa_explicit_bits())) {
    am.mantissa = (uint64_t(1) << binary_format<T>::mantissa_explicit_bits());
    am.power2++;
  }

  // check for infinite: we could have carried to an infinite power
  am.mantissa &= ~(uint64_t(1) << binary_format<T>::mantissa_explicit_bits());
  if (am.power2 >= binary_format<T>::infinite_power()) {
    am.power2 = binary_format<T>::infinite_power();
    am.mantissa = 0;
  }
}

template <typename callback>
BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
void round_nearest_tie_even(adjusted_mantissa& am, int32_t shift, callback cb) noexcept {
  const uint64_t mask
  = (shift == 64)
    ? UINT64_MAX
    : (uint64_t(1) << shift) - 1;
  const uint64_t halfway
  = (shift == 0)
    ? 0
    : uint64_t(1) << (shift - 1);
  uint64_t truncated_bits = am.mantissa & mask;
  bool is_above = truncated_bits > halfway;
  bool is_halfway = truncated_bits == halfway;

  // shift digits into position
  if (shift == 64) {
    am.mantissa = 0;
  } else {
    am.mantissa >>= shift;
  }
  am.power2 += shift;

  bool is_odd = (am.mantissa & 1) == 1;
  am.mantissa += uint64_t(cb(is_odd, is_halfway, is_above));
}

BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
void round_down(adjusted_mantissa& am, int32_t shift) noexcept {
  if (shift == 64) {
    am.mantissa = 0;
  } else {
    am.mantissa >>= shift;
  }
  am.power2 += shift;
}
template <typename UC>
BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
void skip_zeros(UC const * & first, UC const * last) noexcept {
  uint64_t val;
  while (!cpp20_and_in_constexpr() && std::distance(first, last) >= int_cmp_len<UC>()) {
    ::memcpy(&val, first, sizeof(uint64_t));
    if (val != int_cmp_zeros<UC>()) {
      break;
    }
    first += int_cmp_len<UC>();
  }
  while (first != last) {
    if (*first != UC('0')) {
      break;
    }
    first++;
  }
}

// determine if any non-zero digits were truncated.
// all characters must be valid digits.
template <typename UC>
BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
bool is_truncated(UC const * first, UC const * last) noexcept {
  // do 8-bit optimizations, can just compare to 8 literal 0s.
  uint64_t val;
  while (!cpp20_and_in_constexpr() && std::distance(first, last) >= int_cmp_len<UC>()) {
    ::memcpy(&val, first, sizeof(uint64_t));
    if (val != int_cmp_zeros<UC>()) {
      return true;
    }
    first += int_cmp_len<UC>();
  }
  while (first != last) {
    if (*first != UC('0')) {
      return true;
    }
    ++first;
  }
  return false;
}
template <typename UC>
BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
bool is_truncated(span<const UC> s) noexcept {
  return is_truncated(s.ptr, s.ptr + s.len());
}

BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
void parse_eight_digits(const char16_t*& , limb& , size_t& , size_t& ) noexcept {
  // currently unused
}

BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
void parse_eight_digits(const char32_t*& , limb& , size_t& , size_t& ) noexcept {
  // currently unused
}

BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
void parse_eight_digits(const char*& p, limb& value, size_t& counter, size_t& count) noexcept {
  value = value * 100000000 + parse_eight_digits_unrolled(p);
  p += 8;
  counter += 8;
  count += 8;
}

template <typename UC>
BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
void parse_one_digit(UC const *& p, limb& value, size_t& counter, size_t& count) noexcept {
  value = value * 10 + limb(*p - UC('0'));
  p++;
  counter++;
  count++;
}

BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
void add_native(bigint& big, limb power, limb value) noexcept {
  big.mul(power);
  big.add(value);
}

BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
void round_up_bigint(bigint& big, size_t& count) noexcept {
  // need to round-up the digits, but need to avoid rounding
  // ....9999 to ...10000, which could cause a false halfway point.
  add_native(big, 10, 1);
  count++;
}

// parse the significant digits into a big integer
template <typename UC>
inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
void parse_mantissa(bigint& result, parsed_number_string_t<UC>& num, size_t max_digits, size_t& digits) noexcept {
  // try to minimize the number of big integer and scalar multiplication.
  // therefore, try to parse 8 digits at a time, and multiply by the largest
  // scalar value (9 or 19 digits) for each step.
  size_t counter = 0;
  digits = 0;
  limb value = 0;
#ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
  constexpr size_t step = 19;
#else
  constexpr size_t step = 9;
#endif

  // process all integer digits.
  UC const * p = num.integer.ptr;
  UC const * pend = p + num.integer.len();
  skip_zeros(p, pend);
  // process all digits, in increments of step per loop
  while (p != pend) {
    if (std::is_same<UC,char>::value) {
      while ((std::distance(p, pend) >= 8) && (step - counter >= 8) && (max_digits - digits >= 8)) {
        parse_eight_digits(p, value, counter, digits);
      }
    }
    while (counter < step && p != pend && digits < max_digits) {
      parse_one_digit(p, value, counter, digits);
    }
    if (digits == max_digits) {
      // add the temporary value, then check if we've truncated any digits
      add_native(result, limb(powers_of_ten_uint64[counter]), value);
      bool truncated = is_truncated(p, pend);
      if (num.fraction.ptr != nullptr) {
        truncated |= is_truncated(num.fraction);
      }
      if (truncated) {
        round_up_bigint(result, digits);
      }
      return;
    } else {
      add_native(result, limb(powers_of_ten_uint64[counter]), value);
      counter = 0;
      value = 0;
    }
  }

  // add our fraction digits, if they're available.
  if (num.fraction.ptr != nullptr) {
    p = num.fraction.ptr;
    pend = p + num.fraction.len();
    if (digits == 0) {
      skip_zeros(p, pend);
    }
    // process all digits, in increments of step per loop
    while (p != pend) {
      if (std::is_same<UC,char>::value) {
        while ((std::distance(p, pend) >= 8) && (step - counter >= 8) && (max_digits - digits >= 8)) {
          parse_eight_digits(p, value, counter, digits);
        }
      }
      while (counter < step && p != pend && digits < max_digits) {
        parse_one_digit(p, value, counter, digits);
      }
      if (digits == max_digits) {
        // add the temporary value, then check if we've truncated any digits
        add_native(result, limb(powers_of_ten_uint64[counter]), value);
        bool truncated = is_truncated(p, pend);
        if (truncated) {
          round_up_bigint(result, digits);
        }
        return;
      } else {
        add_native(result, limb(powers_of_ten_uint64[counter]), value);
        counter = 0;
        value = 0;
      }
    }
  }

  if (counter != 0) {
    add_native(result, limb(powers_of_ten_uint64[counter]), value);
  }
}

template <typename T>
inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
adjusted_mantissa positive_digit_comp(bigint& bigmant, int32_t exponent) noexcept {
  bigmant.pow10(uint32_t(exponent));
  adjusted_mantissa answer;
  bool truncated;
  answer.mantissa = bigmant.hi64(truncated);
  int bias = binary_format<T>::mantissa_explicit_bits() - binary_format<T>::minimum_exponent();
  answer.power2 = bigmant.bit_length() - 64 + bias;

  round<T>(answer, [truncated](adjusted_mantissa& a, int32_t shift) {
    round_nearest_tie_even(a, shift, [truncated](bool is_odd, bool is_halfway, bool is_above) -> bool {
      return is_above || (is_halfway && truncated) || (is_odd && is_halfway);
    });
  });

  return answer;
}

// the scaling here is quite simple: we have, for the real digits `m * 10^e`,
// and for the theoretical digits `n * 2^f`. Since `e` is always negative,
// to scale them identically, we do `n * 2^f * 5^-f`, so we now have `m * 2^e`.
// we then need to scale by `2^(f- e)`, and then the two significant digits
// are of the same magnitude.
template <typename T>
inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
adjusted_mantissa negative_digit_comp(bigint& bigmant, adjusted_mantissa am, int32_t exponent) noexcept {
  bigint& real_digits = bigmant;
  int32_t real_exp = exponent;

  // get the value of `b`, rounded down, and get a bigint representation of b+h
  adjusted_mantissa am_b = am;
  // gcc7 buf: use a lambda to remove the noexcept qualifier bug with -Wnoexcept-type.
  round<T>(am_b, [](adjusted_mantissa&a, int32_t shift) { round_down(a, shift); });
  T b;
  to_float(false, am_b, b);
  adjusted_mantissa theor = to_extended_halfway(b);
  bigint theor_digits(theor.mantissa);
  int32_t theor_exp = theor.power2;

  // scale real digits and theor digits to be same power.
  int32_t pow2_exp = theor_exp - real_exp;
  uint32_t pow5_exp = uint32_t(-real_exp);
  if (pow5_exp != 0) {
    theor_digits.pow5(pow5_exp);
  }
  if (pow2_exp > 0) {
    theor_digits.pow2(uint32_t(pow2_exp));
  } else if (pow2_exp < 0) {
    real_digits.pow2(uint32_t(-pow2_exp));
  }

  // compare digits, and use it to director rounding
  int ord = real_digits.compare(theor_digits);
  adjusted_mantissa answer = am;
  round<T>(answer, [ord](adjusted_mantissa& a, int32_t shift) {
    round_nearest_tie_even(a, shift, [ord](bool is_odd, bool, bool) -> bool {
      if (ord > 0) {
        return true;
      } else if (ord < 0) {
        return false;
      } else {
        return is_odd;
      }
    });
  });

  return answer;
}

// parse the significant digits as a big integer to unambiguously round
// the significant digits. here, we are trying to determine how to round
// an extended float representation close to `b+h`, halfway between `b`
// (the float rounded-down) and `b+u`, the next positive float. this
// algorithm is always correct, and uses one of two approaches. when
// the exponent is positive relative to the significant digits (such as
// 1234), we create a big-integer representation, get the high 64-bits,
// determine if any lower bits are truncated, and use that to direct
// rounding. in case of a negative exponent relative to the significant
// digits (such as 1.2345), we create a theoretical representation of
// `b` as a big-integer type, scaled to the same binary exponent as
// the actual digits. we then compare the big integer representations
// of both, and use that to direct rounding.
template <typename T, typename UC>
inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
adjusted_mantissa digit_comp(parsed_number_string_t<UC>& num, adjusted_mantissa am) noexcept {
  // remove the invalid exponent bias
  am.power2 -= invalid_am_bias;

  int32_t sci_exp = scientific_exponent(num);
  size_t max_digits = binary_format<T>::max_digits();
  size_t digits = 0;
  bigint bigmant;
  parse_mantissa(bigmant, num, max_digits, digits);
  // can't underflow, since digits is at most max_digits.
  int32_t exponent = sci_exp + 1 - int32_t(digits);
  if (exponent >= 0) {
    return positive_digit_comp<T>(bigmant, exponent);
  } else {
    return negative_digit_comp<T>(bigmant, am, exponent);
  }
}

}}}}}} // namespace fast_float

#endif

Coverage Report

Created: 2023-11-19 06:56

Line	Count	Source (jump to first uncovered line)
1		// Copyright 2020-2023 Daniel Lemire
2		// Copyright 2023 Matt Borland
3		// Distributed under the Boost Software License, Version 1.0.
4		// https://www.boost.org/LICENSE_1_0.txt
5		//
6		// Derivative of: https://github.com/fastfloat/fast_float
7
8		#ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_DIGIT_COMPARISON_HPP
9		#define BOOST_JSON_DETAIL_CHARCONV_DETAIL_FASTFLOAT_DIGIT_COMPARISON_HPP
10
11		#include <boost/json/detail/charconv/detail/fast_float/float_common.hpp>
12		#include <boost/json/detail/charconv/detail/fast_float/bigint.hpp>
13		#include <boost/json/detail/charconv/detail/fast_float/ascii_number.hpp>
14		#include <algorithm>
15		#include <cstdint>
16		#include <cstring>
17		#include <iterator>
18
19		namespace boost { namespace json { namespace detail { namespace charconv { namespace detail { namespace fast_float {
20
21		// 1e0 to 1e19
22		constexpr static uint64_t powers_of_ten_uint64[] = {
23		1UL, 10UL, 100UL, 1000UL, 10000UL, 100000UL, 1000000UL, 10000000UL, 100000000UL,
24		1000000000UL, 10000000000UL, 100000000000UL, 1000000000000UL, 10000000000000UL,
25		100000000000000UL, 1000000000000000UL, 10000000000000000UL, 100000000000000000UL,
26		1000000000000000000UL, 10000000000000000000UL};
27
28		// calculate the exponent, in scientific notation, of the number.
29		// this algorithm is not even close to optimized, but it has no practical
30		// effect on performance: in order to have a faster algorithm, we'd need
31		// to slow down performance for faster algorithms, and this is still fast.
32		template <typename UC>
33		BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
34	0	int32_t scientific_exponent(parsed_number_string_t<UC> & num) noexcept {
35	0	uint64_t mantissa = num.mantissa;
36	0	int32_t exponent = int32_t(num.exponent);
37	0	while (mantissa >= 10000) {
38	0	mantissa /= 10000;
39	0	exponent += 4;
40	0	}
41	0	while (mantissa >= 100) {
42	0	mantissa /= 100;
43	0	exponent += 2;
44	0	}
45	0	while (mantissa >= 10) {
46	0	mantissa /= 10;
47	0	exponent += 1;
48	0	}
49	0	return exponent;
50	0	}
51
52		// this converts a native floating-point number to an extended-precision float.
53		template <typename T>
54		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
55	0	adjusted_mantissa to_extended(T value) noexcept {
56	0	using equiv_uint = typename binary_format<T>::equiv_uint;
57	0	constexpr equiv_uint exponent_mask = binary_format<T>::exponent_mask();
58	0	constexpr equiv_uint mantissa_mask = binary_format<T>::mantissa_mask();
59	0	constexpr equiv_uint hidden_bit_mask = binary_format<T>::hidden_bit_mask();
60
61	0	adjusted_mantissa am;
62	0	int32_t bias = binary_format<T>::mantissa_explicit_bits() - binary_format<T>::minimum_exponent();
63	0	equiv_uint bits;
64		#ifdef BOOST_JSON_HAS_BIT_CAST
65		bits = std::bit_cast<equiv_uint>(value);
66		#else
67	0	::memcpy(&bits, &value, sizeof(T));
68	0	#endif
69	0	if ((bits & exponent_mask) == 0) {
70		// denormal
71	0	am.power2 = 1 - bias;
72	0	am.mantissa = bits & mantissa_mask;
73	0	} else {
74		// normal
75	0	am.power2 = int32_t((bits & exponent_mask) >> binary_format<T>::mantissa_explicit_bits());
76	0	am.power2 -= bias;
77	0	am.mantissa = (bits & mantissa_mask) \| hidden_bit_mask;
78	0	}
79
80	0	return am;
81	0	}
82
83		// get the extended precision value of the halfway point between b and b+u.
84		// we are given a native float that represents b, so we need to adjust it
85		// halfway between b and b+u.
86		template <typename T>
87		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
88	0	adjusted_mantissa to_extended_halfway(T value) noexcept {
89	0	adjusted_mantissa am = to_extended(value);
90	0	am.mantissa <<= 1;
91	0	am.mantissa += 1;
92	0	am.power2 -= 1;
93	0	return am;
94	0	}
95
96		// round an extended-precision float to the nearest machine float.
97		template <typename T, typename callback>
98		BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
99	0	void round(adjusted_mantissa& am, callback cb) noexcept {
100	0	int32_t mantissa_shift = 64 - binary_format<T>::mantissa_explicit_bits() - 1;
101	0	if (-am.power2 >= mantissa_shift) {
102		// have a denormal float
103	0	int32_t shift = -am.power2 + 1;
104	0	cb(am, std::min<int32_t>(shift, 64));
105		// check for round-up: if rounding-nearest carried us to the hidden bit.
106	0	am.power2 = (am.mantissa < (uint64_t(1) << binary_format<T>::mantissa_explicit_bits())) ? 0 : 1;
107	0	return;
108	0	}
109
110		// have a normal float, use the default shift.
111	0	cb(am, mantissa_shift);
112
113		// check for carry
114	0	if (am.mantissa >= (uint64_t(2) << binary_format<T>::mantissa_explicit_bits())) {
115	0	am.mantissa = (uint64_t(1) << binary_format<T>::mantissa_explicit_bits());
116	0	am.power2++;
117	0	}
118
119		// check for infinite: we could have carried to an infinite power
120	0	am.mantissa &= ~(uint64_t(1) << binary_format<T>::mantissa_explicit_bits());
121	0	if (am.power2 >= binary_format<T>::infinite_power()) {
122	0	am.power2 = binary_format<T>::infinite_power();
123	0	am.mantissa = 0;
124	0	}
125	0	} Unexecuted instantiation: void boost::json::detail::charconv::detail::fast_float::round<double, boost::json::detail::charconv::detail::fast_float::positive_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#1}>(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, boost::json::detail::charconv::detail::fast_float::positive_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#1}) Unexecuted instantiation: void boost::json::detail::charconv::detail::fast_float::round<double, boost::json::detail::charconv::detail::fast_float::negative_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, boost::json::detail::charconv::detail::fast_float::adjusted_mantissa, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#1}>(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, boost::json::detail::charconv::detail::fast_float::negative_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, boost::json::detail::charconv::detail::fast_float::adjusted_mantissa, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#1}) Unexecuted instantiation: void boost::json::detail::charconv::detail::fast_float::round<double, boost::json::detail::charconv::detail::fast_float::negative_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, boost::json::detail::charconv::detail::fast_float::adjusted_mantissa, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#2}>(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, boost::json::detail::charconv::detail::fast_float::negative_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, boost::json::detail::charconv::detail::fast_float::adjusted_mantissa, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#2})
126
127		template <typename callback>
128		BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
129	0	void round_nearest_tie_even(adjusted_mantissa& am, int32_t shift, callback cb) noexcept {
130	0	const uint64_t mask
131	0	= (shift == 64)
132	0	? UINT64_MAX
133	0	: (uint64_t(1) << shift) - 1;
134	0	const uint64_t halfway
135	0	= (shift == 0)
136	0	? 0
137	0	: uint64_t(1) << (shift - 1);
138	0	uint64_t truncated_bits = am.mantissa & mask;
139	0	bool is_above = truncated_bits > halfway;
140	0	bool is_halfway = truncated_bits == halfway;
141
142		// shift digits into position
143	0	if (shift == 64) {
144	0	am.mantissa = 0;
145	0	} else {
146	0	am.mantissa >>= shift;
147	0	}
148	0	am.power2 += shift;
149
150	0	bool is_odd = (am.mantissa & 1) == 1;
151	0	am.mantissa += uint64_t(cb(is_odd, is_halfway, is_above));
152	0	} Unexecuted instantiation: void boost::json::detail::charconv::detail::fast_float::round_nearest_tie_even<boost::json::detail::charconv::detail::fast_float::positive_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#1}::operator()(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int) const::{lambda(bool, bool, bool)#1}>(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int, boost::json::detail::charconv::detail::fast_float::positive_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#1}::operator()(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int) const::{lambda(bool, bool, bool)#1}) Unexecuted instantiation: void boost::json::detail::charconv::detail::fast_float::round_nearest_tie_even<boost::json::detail::charconv::detail::fast_float::negative_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, boost::json::detail::charconv::detail::fast_float::adjusted_mantissa, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#2}::operator()(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int) const::{lambda(bool, bool, bool)#1}>(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int, boost::json::detail::charconv::detail::fast_float::negative_digit_comp<double>(boost::json::detail::charconv::detail::fast_float::bigint&, boost::json::detail::charconv::detail::fast_float::adjusted_mantissa, int)::{lambda(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int)#2}::operator()(boost::json::detail::charconv::detail::fast_float::adjusted_mantissa&, int) const::{lambda(bool, bool, bool)#1})
153
154		BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
155	0	void round_down(adjusted_mantissa& am, int32_t shift) noexcept {
156	0	if (shift == 64) {
157	0	am.mantissa = 0;
158	0	} else {
159	0	am.mantissa >>= shift;
160	0	}
161	0	am.power2 += shift;
162	0	}
163		template <typename UC>
164		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
165	0	void skip_zeros(UC const * & first, UC const * last) noexcept {
166	0	uint64_t val;
167	0	while (!cpp20_and_in_constexpr() && std::distance(first, last) >= int_cmp_len<UC>()) {
168	0	::memcpy(&val, first, sizeof(uint64_t));
169	0	if (val != int_cmp_zeros<UC>()) {
170	0	break;
171	0	}
172	0	first += int_cmp_len<UC>();
173	0	}
174	0	while (first != last) {
175	0	if (*first != UC('0')) {
176	0	break;
177	0	}
178	0	first++;
179	0	}
180	0	}
181
182		// determine if any non-zero digits were truncated.
183		// all characters must be valid digits.
184		template <typename UC>
185		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
186	0	bool is_truncated(UC const * first, UC const * last) noexcept {
187		// do 8-bit optimizations, can just compare to 8 literal 0s.
188	0	uint64_t val;
189	0	while (!cpp20_and_in_constexpr() && std::distance(first, last) >= int_cmp_len<UC>()) {
190	0	::memcpy(&val, first, sizeof(uint64_t));
191	0	if (val != int_cmp_zeros<UC>()) {
192	0	return true;
193	0	}
194	0	first += int_cmp_len<UC>();
195	0	}
196	0	while (first != last) {
197	0	if (*first != UC('0')) {
198	0	return true;
199	0	}
200	0	++first;
201	0	}
202	0	return false;
203	0	}
204		template <typename UC>
205		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
206	0	bool is_truncated(span<const UC> s) noexcept {
207	0	return is_truncated(s.ptr, s.ptr + s.len());
208	0	}
209
210		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
211	0	void parse_eight_digits(const char16_t*& , limb& , size_t& , size_t& ) noexcept {
212	0	// currently unused
213	0	}
214
215		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
216	0	void parse_eight_digits(const char32_t*& , limb& , size_t& , size_t& ) noexcept {
217	0	// currently unused
218	0	}
219
220		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
221	0	void parse_eight_digits(const char*& p, limb& value, size_t& counter, size_t& count) noexcept {
222	0	value = value * 100000000 + parse_eight_digits_unrolled(p);
223	0	p += 8;
224	0	counter += 8;
225	0	count += 8;
226	0	}
227
228		template <typename UC>
229		BOOST_FORCEINLINE BOOST_JSON_CXX14_CONSTEXPR_NO_INLINE
230	0	void parse_one_digit(UC const *& p, limb& value, size_t& counter, size_t& count) noexcept {
231	0	value = value * 10 + limb(*p - UC('0'));
232	0	p++;
233	0	counter++;
234	0	count++;
235	0	}
236
237		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
238	0	void add_native(bigint& big, limb power, limb value) noexcept {
239	0	big.mul(power);
240	0	big.add(value);
241	0	}
242
243		BOOST_FORCEINLINE BOOST_JSON_FASTFLOAT_CONSTEXPR20
244	0	void round_up_bigint(bigint& big, size_t& count) noexcept {
245		// need to round-up the digits, but need to avoid rounding
246		// ....9999 to ...10000, which could cause a false halfway point.
247	0	add_native(big, 10, 1);
248	0	count++;
249	0	}
250
251		// parse the significant digits into a big integer
252		template <typename UC>
253		inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
254	0	void parse_mantissa(bigint& result, parsed_number_string_t<UC>& num, size_t max_digits, size_t& digits) noexcept {
255		// try to minimize the number of big integer and scalar multiplication.
256		// therefore, try to parse 8 digits at a time, and multiply by the largest
257		// scalar value (9 or 19 digits) for each step.
258	0	size_t counter = 0;
259	0	digits = 0;
260	0	limb value = 0;
261	0	#ifdef BOOST_JSON_FASTFLOAT_64BIT_LIMB
262	0	constexpr size_t step = 19;
263		#else
264		constexpr size_t step = 9;
265		#endif
266
267		// process all integer digits.
268	0	UC const * p = num.integer.ptr;
269	0	UC const * pend = p + num.integer.len();
270	0	skip_zeros(p, pend);
271		// process all digits, in increments of step per loop
272	0	while (p != pend) {
273	0	if (std::is_same<UC,char>::value) {
274	0	while ((std::distance(p, pend) >= 8) && (step - counter >= 8) && (max_digits - digits >= 8)) {
275	0	parse_eight_digits(p, value, counter, digits);
276	0	}
277	0	}
278	0	while (counter < step && p != pend && digits < max_digits) {
279	0	parse_one_digit(p, value, counter, digits);
280	0	}
281	0	if (digits == max_digits) {
282		// add the temporary value, then check if we've truncated any digits
283	0	add_native(result, limb(powers_of_ten_uint64[counter]), value);
284	0	bool truncated = is_truncated(p, pend);
285	0	if (num.fraction.ptr != nullptr) {
286	0	truncated \|= is_truncated(num.fraction);
287	0	}
288	0	if (truncated) {
289	0	round_up_bigint(result, digits);
290	0	}
291	0	return;
292	0	} else {
293	0	add_native(result, limb(powers_of_ten_uint64[counter]), value);
294	0	counter = 0;
295	0	value = 0;
296	0	}
297	0	}
298
299		// add our fraction digits, if they're available.
300	0	if (num.fraction.ptr != nullptr) {
301	0	p = num.fraction.ptr;
302	0	pend = p + num.fraction.len();
303	0	if (digits == 0) {
304	0	skip_zeros(p, pend);
305	0	}
306		// process all digits, in increments of step per loop
307	0	while (p != pend) {
308	0	if (std::is_same<UC,char>::value) {
309	0	while ((std::distance(p, pend) >= 8) && (step - counter >= 8) && (max_digits - digits >= 8)) {
310	0	parse_eight_digits(p, value, counter, digits);
311	0	}
312	0	}
313	0	while (counter < step && p != pend && digits < max_digits) {
314	0	parse_one_digit(p, value, counter, digits);
315	0	}
316	0	if (digits == max_digits) {
317		// add the temporary value, then check if we've truncated any digits
318	0	add_native(result, limb(powers_of_ten_uint64[counter]), value);
319	0	bool truncated = is_truncated(p, pend);
320	0	if (truncated) {
321	0	round_up_bigint(result, digits);
322	0	}
323	0	return;
324	0	} else {
325	0	add_native(result, limb(powers_of_ten_uint64[counter]), value);
326	0	counter = 0;
327	0	value = 0;
328	0	}
329	0	}
330	0	}
331
332	0	if (counter != 0) {
333	0	add_native(result, limb(powers_of_ten_uint64[counter]), value);
334	0	}
335	0	}
336
337		template <typename T>
338		inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
339	0	adjusted_mantissa positive_digit_comp(bigint& bigmant, int32_t exponent) noexcept {
340	0	bigmant.pow10(uint32_t(exponent));
341	0	adjusted_mantissa answer;
342	0	bool truncated;
343	0	answer.mantissa = bigmant.hi64(truncated);
344	0	int bias = binary_format<T>::mantissa_explicit_bits() - binary_format<T>::minimum_exponent();
345	0	answer.power2 = bigmant.bit_length() - 64 + bias;
346
347	0	round<T>(answer, [truncated](adjusted_mantissa& a, int32_t shift) {
348	0	round_nearest_tie_even(a, shift, [truncated](bool is_odd, bool is_halfway, bool is_above) -> bool {
349	0	return is_above \|\| (is_halfway && truncated) \|\| (is_odd && is_halfway);
350	0	});
351	0	});
352
353	0	return answer;
354	0	}
355
356		// the scaling here is quite simple: we have, for the real digits `m * 10^e`,
357		// and for the theoretical digits `n * 2^f`. Since `e` is always negative,
358		// to scale them identically, we do `n * 2^f * 5^-f`, so we now have `m * 2^e`.
359		// we then need to scale by `2^(f- e)`, and then the two significant digits
360		// are of the same magnitude.
361		template <typename T>
362		inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
363	0	adjusted_mantissa negative_digit_comp(bigint& bigmant, adjusted_mantissa am, int32_t exponent) noexcept {
364	0	bigint& real_digits = bigmant;
365	0	int32_t real_exp = exponent;
366
367		// get the value of `b`, rounded down, and get a bigint representation of b+h
368	0	adjusted_mantissa am_b = am;
369		// gcc7 buf: use a lambda to remove the noexcept qualifier bug with -Wnoexcept-type.
370	0	round<T>(am_b, [](adjusted_mantissa&a, int32_t shift) { round_down(a, shift); });
371	0	T b;
372	0	to_float(false, am_b, b);
373	0	adjusted_mantissa theor = to_extended_halfway(b);
374	0	bigint theor_digits(theor.mantissa);
375	0	int32_t theor_exp = theor.power2;
376
377		// scale real digits and theor digits to be same power.
378	0	int32_t pow2_exp = theor_exp - real_exp;
379	0	uint32_t pow5_exp = uint32_t(-real_exp);
380	0	if (pow5_exp != 0) {
381	0	theor_digits.pow5(pow5_exp);
382	0	}
383	0	if (pow2_exp > 0) {
384	0	theor_digits.pow2(uint32_t(pow2_exp));
385	0	} else if (pow2_exp < 0) {
386	0	real_digits.pow2(uint32_t(-pow2_exp));
387	0	}
388
389		// compare digits, and use it to director rounding
390	0	int ord = real_digits.compare(theor_digits);
391	0	adjusted_mantissa answer = am;
392	0	round<T>(answer, [ord](adjusted_mantissa& a, int32_t shift) {
393	0	round_nearest_tie_even(a, shift, [ord](bool is_odd, bool, bool) -> bool {
394	0	if (ord > 0) {
395	0	return true;
396	0	} else if (ord < 0) {
397	0	return false;
398	0	} else {
399	0	return is_odd;
400	0	}
401	0	});
402	0	});
403
404	0	return answer;
405	0	}
406
407		// parse the significant digits as a big integer to unambiguously round
408		// the significant digits. here, we are trying to determine how to round
409		// an extended float representation close to `b+h`, halfway between `b`
410		// (the float rounded-down) and `b+u`, the next positive float. this
411		// algorithm is always correct, and uses one of two approaches. when
412		// the exponent is positive relative to the significant digits (such as
413		// 1234), we create a big-integer representation, get the high 64-bits,
414		// determine if any lower bits are truncated, and use that to direct
415		// rounding. in case of a negative exponent relative to the significant
416		// digits (such as 1.2345), we create a theoretical representation of
417		// `b` as a big-integer type, scaled to the same binary exponent as
418		// the actual digits. we then compare the big integer representations
419		// of both, and use that to direct rounding.
420		template <typename T, typename UC>
421		inline BOOST_JSON_FASTFLOAT_CONSTEXPR20
422	0	adjusted_mantissa digit_comp(parsed_number_string_t<UC>& num, adjusted_mantissa am) noexcept {
423		// remove the invalid exponent bias
424	0	am.power2 -= invalid_am_bias;
425
426	0	int32_t sci_exp = scientific_exponent(num);
427	0	size_t max_digits = binary_format<T>::max_digits();
428	0	size_t digits = 0;
429	0	bigint bigmant;
430	0	parse_mantissa(bigmant, num, max_digits, digits);
431		// can't underflow, since digits is at most max_digits.
432	0	int32_t exponent = sci_exp + 1 - int32_t(digits);
433	0	if (exponent >= 0) {
434	0	return positive_digit_comp<T>(bigmant, exponent);
435	0	} else {
436	0	return negative_digit_comp<T>(bigmant, am, exponent);
437	0	}
438	0	}
439
440		}}}}}} // namespace fast_float
441
442		#endif