Audacity  3.0.3
Classes | Functions | Variables
internal::dtoa_impl Namespace Reference

Classes

struct  boundaries
 
struct  cached_power
 
struct  diyfp
 

Functions

template<typename Target , typename Source >
Target reinterpret_bits (const Source source)
 
template<typename FloatType >
boundaries compute_boundaries (FloatType value)
 
cached_power get_cached_power_for_binary_exponent (int e)
 
int find_largest_pow10 (const std::uint32_t n, std::uint32_t &pow10)
 
void grisu2_round (char *buf, int len, std::uint64_t dist, std::uint64_t delta, std::uint64_t rest, std::uint64_t ten_k)
 
bool grisu2_digit_gen (char *buffer, char *last, int &length, int &decimal_exponent, diyfp M_minus, diyfp w, diyfp M_plus)
 
bool grisu2 (char *buf, char *last, int &len, int &decimal_exponent, diyfp m_minus, diyfp v, diyfp m_plus)
 
template<typename FloatType >
bool grisu2 (char *buf, char *last, int &len, int &decimal_exponent, FloatType value)
 
ToCharsResult append_exponent (char *buf, char *last, int e)
 appends a decimal representation of e to buf More...
 
ToCharsResult format_buffer (char *buf, char *last, int len, int decimal_exponent, int min_exp, int max_exp)
 prettify v = buf * 10^decimal_exponent If v is in the range [10^min_exp, 10^max_exp) it will be printed in fixed-point notation. Otherwise it will be printed in exponential notation. More...
 

Variables

constexpr int kAlpha = -60
 
constexpr int kGamma = -32
 

Function Documentation

◆ append_exponent()

ToCharsResult internal::dtoa_impl::append_exponent ( char *  buf,
char *  last,
int  e 
)
inline

appends a decimal representation of e to buf

Returns
a pointer to the element following the exponent.
Precondition
-1000 < e < 1000

Definition at line 1021 of file ToChars.cpp.

1022 {
1023  if (buf >= last)
1024  return { last, std::errc::value_too_large };
1025 
1026  if (e < 0)
1027  {
1028  e = -e;
1029  *buf++ = '-';
1030  }
1031  else
1032  {
1033  *buf++ = '+';
1034  }
1035 
1036  auto k = static_cast<std::uint32_t>(e);
1037 
1038  const int requiredSymbolsCount = k < 100 ? 2 : 3;
1039  char* requiredLast = buf + requiredSymbolsCount + 1;
1040 
1041  if (requiredLast > last)
1042  return { last, std::errc::value_too_large };
1043 
1044  if (k < 10)
1045  {
1046  // Always print at least two digits in the exponent.
1047  // This is for compatibility with printf("%g").
1048  *buf++ = '0';
1049  *buf++ = static_cast<char>('0' + k);
1050  }
1051  else if (k < 100)
1052  {
1053  *buf++ = static_cast<char>('0' + k / 10);
1054  k %= 10;
1055  *buf++ = static_cast<char>('0' + k);
1056  }
1057  else
1058  {
1059  *buf++ = static_cast<char>('0' + k / 100);
1060  k %= 100;
1061  *buf++ = static_cast<char>('0' + k / 10);
1062  k %= 10;
1063  *buf++ = static_cast<char>('0' + k);
1064  }
1065 
1066  return { buf, std::errc() };
1067 }

Referenced by format_buffer().

Here is the caller graph for this function:

◆ compute_boundaries()

template<typename FloatType >
boundaries internal::dtoa_impl::compute_boundaries ( FloatType  value)

Compute the (normalized) diyfp representing the input number 'value' and its boundaries.

Precondition
value must be finite and positive

Definition at line 316 of file ToChars.cpp.

317 {
318 
319  // Convert the IEEE representation into a diyfp.
320  //
321  // If v is denormal:
322  // value = 0.F * 2^(1 - bias) = ( F) * 2^(1 - bias - (p-1))
323  // If v is normalized:
324  // value = 1.F * 2^(E - bias) = (2^(p-1) + F) * 2^(E - bias - (p-1))
325 
326  static_assert(
327  std::numeric_limits<FloatType>::is_iec559,
328  "internal error: dtoa_short requires an IEEE-754 "
329  "floating-point implementation");
330 
331  constexpr int kPrecision =
332  std::numeric_limits<FloatType>::digits; // = p (includes the hidden bit)
333  constexpr int kBias =
334  std::numeric_limits<FloatType>::max_exponent - 1 + (kPrecision - 1);
335  constexpr int kMinExp = 1 - kBias;
336  constexpr std::uint64_t kHiddenBit = std::uint64_t { 1 }
337  << (kPrecision - 1); // = 2^(p-1)
338 
339  using bits_type = typename std::conditional<
340  kPrecision == 24, std::uint32_t, std::uint64_t>::type;
341 
342  const std::uint64_t bits = reinterpret_bits<bits_type>(value);
343  const std::uint64_t E = bits >> (kPrecision - 1);
344  const std::uint64_t F = bits & (kHiddenBit - 1);
345 
346  const bool is_denormal = E == 0;
347  const diyfp v = is_denormal ?
348  diyfp(F, kMinExp) :
349  diyfp(F + kHiddenBit, static_cast<int>(E) - kBias);
350 
351  // Compute the boundaries m- and m+ of the floating-point value
352  // v = f * 2^e.
353  //
354  // Determine v- and v+, the floating-point predecessor and successor if v,
355  // respectively.
356  //
357  // v- = v - 2^e if f != 2^(p-1) or e == e_min (A)
358  // = v - 2^(e-1) if f == 2^(p-1) and e > e_min (B)
359  //
360  // v+ = v + 2^e
361  //
362  // Let m- = (v- + v) / 2 and m+ = (v + v+) / 2. All real numbers _strictly_
363  // between m- and m+ round to v, regardless of how the input rounding
364  // algorithm breaks ties.
365  //
366  // ---+-------------+-------------+-------------+-------------+--- (A)
367  // v- m- v m+ v+
368  //
369  // -----------------+------+------+-------------+-------------+--- (B)
370  // v- m- v m+ v+
371 
372  const bool lower_boundary_is_closer = F == 0 && E > 1;
373  const diyfp m_plus = diyfp(2 * v.f + 1, v.e - 1);
374  const diyfp m_minus = lower_boundary_is_closer ?
375  diyfp(4 * v.f - 1, v.e - 2) // (B)
376  :
377  diyfp(2 * v.f - 1, v.e - 1); // (A)
378 
379  // Determine the normalized w+ = m+.
380  const diyfp w_plus = diyfp::normalize(m_plus);
381 
382  // Determine w- = m- such that e_(w-) = e_(w+).
383  const diyfp w_minus = diyfp::normalize_to(m_minus, w_plus.e);
384 
385  return { diyfp::normalize(v), w_minus, w_plus };
386 }

References internal::dtoa_impl::diyfp::e, internal::dtoa_impl::diyfp::f, internal::dtoa_impl::diyfp::normalize(), and internal::dtoa_impl::diyfp::normalize_to().

Referenced by grisu2().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ find_largest_pow10()

int internal::dtoa_impl::find_largest_pow10 ( const std::uint32_t  n,
std::uint32_t &  pow10 
)
inline

For n != 0, returns k, such that pow10 := 10^(k-1) <= n < 10^k. For n == 0, returns 1 and sets pow10 := 1.

Definition at line 577 of file ToChars.cpp.

578 {
579  // LCOV_EXCL_START
580  if (n >= 1000000000)
581  {
582  pow10 = 1000000000;
583  return 10;
584  }
585  // LCOV_EXCL_STOP
586  else if (n >= 100000000)
587  {
588  pow10 = 100000000;
589  return 9;
590  }
591  else if (n >= 10000000)
592  {
593  pow10 = 10000000;
594  return 8;
595  }
596  else if (n >= 1000000)
597  {
598  pow10 = 1000000;
599  return 7;
600  }
601  else if (n >= 100000)
602  {
603  pow10 = 100000;
604  return 6;
605  }
606  else if (n >= 10000)
607  {
608  pow10 = 10000;
609  return 5;
610  }
611  else if (n >= 1000)
612  {
613  pow10 = 1000;
614  return 4;
615  }
616  else if (n >= 100)
617  {
618  pow10 = 100;
619  return 3;
620  }
621  else if (n >= 10)
622  {
623  pow10 = 10;
624  return 2;
625  }
626  else
627  {
628  pow10 = 1;
629  return 1;
630  }
631 }

Referenced by grisu2_digit_gen().

Here is the caller graph for this function:

◆ format_buffer()

ToCharsResult internal::dtoa_impl::format_buffer ( char *  buf,
char *  last,
int  len,
int  decimal_exponent,
int  min_exp,
int  max_exp 
)
inline

prettify v = buf * 10^decimal_exponent If v is in the range [10^min_exp, 10^max_exp) it will be printed in fixed-point notation. Otherwise it will be printed in exponential notation.

Precondition
min_exp < 0
max_exp > 0

Definition at line 1076 of file ToChars.cpp.

1078 {
1079  const int k = len;
1080  const int n = len + decimal_exponent;
1081 
1082  // v = buf * 10^(n-k)
1083  // k is the length of the buffer (number of decimal digits)
1084  // n is the position of the decimal point relative to the start of the
1085  // buffer.
1086 
1087  if (k <= n && n <= max_exp)
1088  {
1089  char* requiredLast = buf + (static_cast<size_t>(n));
1090  if (requiredLast > last)
1091  return { last, std::errc::value_too_large };
1092  // digits[000]
1093  // len <= max_exp + 2
1094 
1095  std::memset(
1096  buf + k, '0', static_cast<size_t>(n) - static_cast<size_t>(k));
1097  // Make it look like a floating-point number (#362, #378)
1098  // buf[n + 0] = '.';
1099  // buf[n + 1] = '0';
1100  return { requiredLast, std::errc() };
1101  }
1102 
1103  if (0 < n && n <= max_exp)
1104  {
1105  char* requiredLast = buf + (static_cast<size_t>(k) + 1U);
1106 
1107  if (requiredLast > last)
1108  return { last, std::errc::value_too_large };
1109  // dig.its
1110  // len <= max_digits10 + 1
1111  std::memmove(
1112  buf + (static_cast<size_t>(n) + 1), buf + n,
1113  static_cast<size_t>(k) - static_cast<size_t>(n));
1114  buf[n] = '.';
1115 
1116  return { requiredLast, std::errc() };
1117  }
1118 
1119  if (min_exp < n && n <= 0)
1120  {
1121  char* requiredLast =
1122  buf + (2U + static_cast<size_t>(-n) + static_cast<size_t>(k));
1123 
1124  if (requiredLast > last)
1125  return { last, std::errc::value_too_large };
1126  // 0.[000]digits
1127  // len <= 2 + (-min_exp - 1) + max_digits10
1128 
1129  std::memmove(
1130  buf + (2 + static_cast<size_t>(-n)), buf, static_cast<size_t>(k));
1131  buf[0] = '0';
1132  buf[1] = '.';
1133  std::memset(buf + 2, '0', static_cast<size_t>(-n));
1134 
1135  return { requiredLast, std::errc() };
1136  }
1137 
1138  if (k == 1)
1139  {
1140  char* requiredLast = buf + 1;
1141 
1142  if (requiredLast > last)
1143  return { last, std::errc::value_too_large };
1144  // dE+123
1145  // len <= 1 + 5
1146 
1147  buf += 1;
1148  }
1149  else
1150  {
1151  char* requiredLast = buf + 1 + static_cast<size_t>(k);
1152 
1153  if (requiredLast > last)
1154  return { last, std::errc::value_too_large };
1155  // d.igitsE+123
1156  // len <= max_digits10 + 1 + 5
1157 
1158  std::memmove(buf + 2, buf + 1, static_cast<size_t>(k) - 1);
1159 
1160  buf[1] = '.';
1161  buf += 1 + static_cast<size_t>(k);
1162  }
1163 
1164  *buf++ = 'e';
1165  return append_exponent(buf, last, n - 1);
1166 }

References append_exponent().

Referenced by internal::float_to_chars().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ get_cached_power_for_binary_exponent()

cached_power internal::dtoa_impl::get_cached_power_for_binary_exponent ( int  e)
inline

For a normalized diyfp w = f * 2^e, this function returns a (normalized) cached power-of-ten c = f_c * 2^e_c, such that the exponent of the product w * c satisfies (Definition 3.2 from [1]) alpha <= e_c + e + q <= gamma.

Definition at line 459 of file ToChars.cpp.

460 {
461  // Now
462  //
463  // alpha <= e_c + e + q <= gamma (1)
464  // ==> f_c * 2^alpha <= c * 2^e * 2^q
465  //
466  // and since the c's are normalized, 2^(q-1) <= f_c,
467  //
468  // ==> 2^(q - 1 + alpha) <= c * 2^(e + q)
469  // ==> 2^(alpha - e - 1) <= c
470  //
471  // If c were an exact power of ten, i.e. c = 10^k, one may determine k as
472  //
473  // k = ceil( log_10( 2^(alpha - e - 1) ) )
474  // = ceil( (alpha - e - 1) * log_10(2) )
475  //
476  // From the paper:
477  // "In theory the result of the procedure could be wrong since c is rounded,
478  // and the computation itself is approximated [...]. In practice, however,
479  // this simple function is sufficient."
480  //
481  // For IEEE double precision floating-point numbers converted into
482  // normalized diyfp's w = f * 2^e, with q = 64,
483  //
484  // e >= -1022 (min IEEE exponent)
485  // -52 (p - 1)
486  // -52 (p - 1, possibly normalize denormal IEEE numbers)
487  // -11 (normalize the diyfp)
488  // = -1137
489  //
490  // and
491  //
492  // e <= +1023 (max IEEE exponent)
493  // -52 (p - 1)
494  // -11 (normalize the diyfp)
495  // = 960
496  //
497  // This binary exponent range [-1137,960] results in a decimal exponent
498  // range [-307,324]. One does not need to store a cached power for each
499  // k in this range. For each such k it suffices to find a cached power
500  // such that the exponent of the product lies in [alpha,gamma].
501  // This implies that the difference of the decimal exponents of adjacent
502  // table entries must be less than or equal to
503  //
504  // floor( (gamma - alpha) * log_10(2) ) = 8.
505  //
506  // (A smaller distance gamma-alpha would require a larger table.)
507 
508  // NB:
509  // Actually this function returns c, such that -60 <= e_c + e + 64 <= -34.
510 
511  constexpr int kCachedPowersMinDecExp = -300;
512  constexpr int kCachedPowersDecStep = 8;
513 
514  static constexpr std::array<cached_power, 79> kCachedPowers = { {
515  { 0xAB70FE17C79AC6CA, -1060, -300 }, { 0xFF77B1FCBEBCDC4F, -1034, -292 },
516  { 0xBE5691EF416BD60C, -1007, -284 }, { 0x8DD01FAD907FFC3C, -980, -276 },
517  { 0xD3515C2831559A83, -954, -268 }, { 0x9D71AC8FADA6C9B5, -927, -260 },
518  { 0xEA9C227723EE8BCB, -901, -252 }, { 0xAECC49914078536D, -874, -244 },
519  { 0x823C12795DB6CE57, -847, -236 }, { 0xC21094364DFB5637, -821, -228 },
520  { 0x9096EA6F3848984F, -794, -220 }, { 0xD77485CB25823AC7, -768, -212 },
521  { 0xA086CFCD97BF97F4, -741, -204 }, { 0xEF340A98172AACE5, -715, -196 },
522  { 0xB23867FB2A35B28E, -688, -188 }, { 0x84C8D4DFD2C63F3B, -661, -180 },
523  { 0xC5DD44271AD3CDBA, -635, -172 }, { 0x936B9FCEBB25C996, -608, -164 },
524  { 0xDBAC6C247D62A584, -582, -156 }, { 0xA3AB66580D5FDAF6, -555, -148 },
525  { 0xF3E2F893DEC3F126, -529, -140 }, { 0xB5B5ADA8AAFF80B8, -502, -132 },
526  { 0x87625F056C7C4A8B, -475, -124 }, { 0xC9BCFF6034C13053, -449, -116 },
527  { 0x964E858C91BA2655, -422, -108 }, { 0xDFF9772470297EBD, -396, -100 },
528  { 0xA6DFBD9FB8E5B88F, -369, -92 }, { 0xF8A95FCF88747D94, -343, -84 },
529  { 0xB94470938FA89BCF, -316, -76 }, { 0x8A08F0F8BF0F156B, -289, -68 },
530  { 0xCDB02555653131B6, -263, -60 }, { 0x993FE2C6D07B7FAC, -236, -52 },
531  { 0xE45C10C42A2B3B06, -210, -44 }, { 0xAA242499697392D3, -183, -36 },
532  { 0xFD87B5F28300CA0E, -157, -28 }, { 0xBCE5086492111AEB, -130, -20 },
533  { 0x8CBCCC096F5088CC, -103, -12 }, { 0xD1B71758E219652C, -77, -4 },
534  { 0x9C40000000000000, -50, 4 }, { 0xE8D4A51000000000, -24, 12 },
535  { 0xAD78EBC5AC620000, 3, 20 }, { 0x813F3978F8940984, 30, 28 },
536  { 0xC097CE7BC90715B3, 56, 36 }, { 0x8F7E32CE7BEA5C70, 83, 44 },
537  { 0xD5D238A4ABE98068, 109, 52 }, { 0x9F4F2726179A2245, 136, 60 },
538  { 0xED63A231D4C4FB27, 162, 68 }, { 0xB0DE65388CC8ADA8, 189, 76 },
539  { 0x83C7088E1AAB65DB, 216, 84 }, { 0xC45D1DF942711D9A, 242, 92 },
540  { 0x924D692CA61BE758, 269, 100 }, { 0xDA01EE641A708DEA, 295, 108 },
541  { 0xA26DA3999AEF774A, 322, 116 }, { 0xF209787BB47D6B85, 348, 124 },
542  { 0xB454E4A179DD1877, 375, 132 }, { 0x865B86925B9BC5C2, 402, 140 },
543  { 0xC83553C5C8965D3D, 428, 148 }, { 0x952AB45CFA97A0B3, 455, 156 },
544  { 0xDE469FBD99A05FE3, 481, 164 }, { 0xA59BC234DB398C25, 508, 172 },
545  { 0xF6C69A72A3989F5C, 534, 180 }, { 0xB7DCBF5354E9BECE, 561, 188 },
546  { 0x88FCF317F22241E2, 588, 196 }, { 0xCC20CE9BD35C78A5, 614, 204 },
547  { 0x98165AF37B2153DF, 641, 212 }, { 0xE2A0B5DC971F303A, 667, 220 },
548  { 0xA8D9D1535CE3B396, 694, 228 }, { 0xFB9B7CD9A4A7443C, 720, 236 },
549  { 0xBB764C4CA7A44410, 747, 244 }, { 0x8BAB8EEFB6409C1A, 774, 252 },
550  { 0xD01FEF10A657842C, 800, 260 }, { 0x9B10A4E5E9913129, 827, 268 },
551  { 0xE7109BFBA19C0C9D, 853, 276 }, { 0xAC2820D9623BF429, 880, 284 },
552  { 0x80444B5E7AA7CF85, 907, 292 }, { 0xBF21E44003ACDD2D, 933, 300 },
553  { 0x8E679C2F5E44FF8F, 960, 308 }, { 0xD433179D9C8CB841, 986, 316 },
554  { 0x9E19DB92B4E31BA9, 1013, 324 },
555  } };
556 
557  // This computation gives exactly the same results for k as
558  // k = ceil((kAlpha - e - 1) * 0.30102999566398114)
559  // for |e| <= 1500, but doesn't require floating-point operations.
560  // NB: log_10(2) ~= 78913 / 2^18
561  const int f = kAlpha - e - 1;
562  const int k = (f * 78913) / (1 << 18) + static_cast<int>(f > 0);
563 
564  const int index =
565  (-kCachedPowersMinDecExp + k + (kCachedPowersDecStep - 1)) /
566  kCachedPowersDecStep;
567 
568  const cached_power cached = kCachedPowers[static_cast<std::size_t>(index)];
569 
570  return cached;
571 }

References kAlpha.

Referenced by grisu2().

Here is the caller graph for this function:

◆ grisu2() [1/2]

bool internal::dtoa_impl::grisu2 ( char *  buf,
char *  last,
int &  len,
int &  decimal_exponent,
diyfp  m_minus,
diyfp  v,
diyfp  m_plus 
)
inline

v = buf * 10^decimal_exponent len is the length of the buffer (number of decimal digits) The buffer must be large enough, i.e. >= max_digits10.

Definition at line 923 of file ToChars.cpp.

926 {
927 
928  // --------(-----------------------+-----------------------)-------- (A)
929  // m- v m+
930  //
931  // --------------------(-----------+-----------------------)-------- (B)
932  // m- v m+
933  //
934  // First scale v (and m- and m+) such that the exponent is in the range
935  // [alpha, gamma].
936 
937  const cached_power cached = get_cached_power_for_binary_exponent(m_plus.e);
938 
939  const diyfp c_minus_k(cached.f, cached.e); // = c ~= 10^-k
940 
941  // The exponent of the products is = v.e + c_minus_k.e + q and is in the
942  // range [alpha,gamma]
943  const diyfp w = diyfp::mul(v, c_minus_k);
944  const diyfp w_minus = diyfp::mul(m_minus, c_minus_k);
945  const diyfp w_plus = diyfp::mul(m_plus, c_minus_k);
946 
947  // ----(---+---)---------------(---+---)---------------(---+---)----
948  // w- w w+
949  // = c*m- = c*v = c*m+
950  //
951  // diyfp::mul rounds its result and c_minus_k is approximated too. w, w- and
952  // w+ are now off by a small amount.
953  // In fact:
954  //
955  // w - v * 10^k < 1 ulp
956  //
957  // To account for this inaccuracy, add resp. subtract 1 ulp.
958  //
959  // --------+---[---------------(---+---)---------------]---+--------
960  // w- M- w M+ w+
961  //
962  // Now any number in [M-, M+] (bounds included) will round to w when input,
963  // regardless of how the input rounding algorithm breaks ties.
964  //
965  // And digit_gen generates the shortest possible such number in [M-, M+].
966  // Note that this does not mean that Grisu2 always generates the shortest
967  // possible number in the interval (m-, m+).
968  const diyfp M_minus(w_minus.f + 1, w_minus.e);
969  const diyfp M_plus(w_plus.f - 1, w_plus.e);
970 
971  decimal_exponent = -cached.k; // = -(-k) = k
972 
973  return grisu2_digit_gen(buf, last, len, decimal_exponent, M_minus, w, M_plus);
974 }

References internal::dtoa_impl::diyfp::e, internal::dtoa_impl::cached_power::e, internal::dtoa_impl::diyfp::f, internal::dtoa_impl::cached_power::f, get_cached_power_for_binary_exponent(), grisu2_digit_gen(), internal::dtoa_impl::cached_power::k, and internal::dtoa_impl::diyfp::mul().

Referenced by internal::float_to_chars(), and grisu2().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ grisu2() [2/2]

template<typename FloatType >
bool internal::dtoa_impl::grisu2 ( char *  buf,
char *  last,
int &  len,
int &  decimal_exponent,
FloatType  value 
)

v = buf * 10^decimal_exponent len is the length of the buffer (number of decimal digits) The buffer must be large enough, i.e. >= max_digits10.

Definition at line 982 of file ToChars.cpp.

983 {
984  static_assert(
985  diyfp::kPrecision >= std::numeric_limits<FloatType>::digits + 3,
986  "internal error: not enough precision");
987 
988  // If the neighbors (and boundaries) of 'value' are always computed for
989  // double-precision numbers, all float's can be recovered using strtod (and
990  // strtof). However, the resulting decimal representations are not exactly
991  // "short".
992  //
993  // The documentation for 'std::to_chars'
994  // (https://en.cppreference.com/w/cpp/utility/to_chars) says "value is
995  // converted to a string as if by std::sprintf in the default ("C") locale"
996  // and since sprintf promotes float's to double's, I think this is exactly
997  // what 'std::to_chars' does. On the other hand, the documentation for
998  // 'std::to_chars' requires that "parsing the representation using the
999  // corresponding std::from_chars function recovers value exactly". That
1000  // indicates that single precision floating-point numbers should be recovered
1001  // using 'std::strtof'.
1002  //
1003  // NB: If the neighbors are computed for single-precision numbers, there is a
1004  // single float
1005  // (7.0385307e-26f) which can't be recovered using strtod. The resulting
1006  // double precision value is off by 1 ulp.
1007 #if 0
1008  const boundaries w = compute_boundaries(static_cast<double>(value));
1009 #else
1010  const boundaries w = compute_boundaries(value);
1011 #endif
1012 
1013  return grisu2(buf, last, len, decimal_exponent, w.minus, w.w, w.plus);
1014 }

References compute_boundaries(), grisu2(), internal::dtoa_impl::diyfp::kPrecision, internal::dtoa_impl::boundaries::minus, internal::dtoa_impl::boundaries::plus, and internal::dtoa_impl::boundaries::w.

Here is the call graph for this function:

◆ grisu2_digit_gen()

bool internal::dtoa_impl::grisu2_digit_gen ( char *  buffer,
char *  last,
int &  length,
int &  decimal_exponent,
diyfp  M_minus,
diyfp  w,
diyfp  M_plus 
)
inline

Generates V = buffer * 10^decimal_exponent, such that M- <= V <= M+. M- and M+ must be normalized and share the same exponent -60 <= e <= -32.

Definition at line 669 of file ToChars.cpp.

672 {
673  static_assert(kAlpha >= -60, "internal error");
674  static_assert(kGamma <= -32, "internal error");
675 
676  const int max_length = static_cast<int>(last - buffer);
677 
678  // Generates the digits (and the exponent) of a decimal floating-point
679  // number V = buffer * 10^decimal_exponent in the range [M-, M+]. The diyfp's
680  // w, M- and M+ share the same exponent e, which satisfies alpha <= e <=
681  // gamma.
682  //
683  // <--------------------------- delta ---->
684  // <---- dist --------->
685  // --------------[------------------+-------------------]--------------
686  // M- w M+
687  //
688  // Grisu2 generates the digits of M+ from left to right and stops as soon as
689  // V is in [M-,M+].
690 
691  std::uint64_t delta =
692  diyfp::sub(M_plus, M_minus)
693  .f; // (significand of (M+ - M-), implicit exponent is e)
694  std::uint64_t dist =
695  diyfp::sub(M_plus, w)
696  .f; // (significand of (M+ - w ), implicit exponent is e)
697 
698  // Split M+ = f * 2^e into two parts p1 and p2 (note: e < 0):
699  //
700  // M+ = f * 2^e
701  // = ((f div 2^-e) * 2^-e + (f mod 2^-e)) * 2^e
702  // = ((p1 ) * 2^-e + (p2 )) * 2^e
703  // = p1 + p2 * 2^e
704 
705  const diyfp one(std::uint64_t { 1 } << -M_plus.e, M_plus.e);
706 
707  auto p1 = static_cast<std::uint32_t>(
708  M_plus.f >>
709  -one.e); // p1 = f div 2^-e (Since -e >= 32, p1 fits into a 32-bit int.)
710  std::uint64_t p2 = M_plus.f & (one.f - 1); // p2 = f mod 2^-e
711 
712  // 1)
713  //
714  // Generate the digits of the integral part p1 = d[n-1]...d[1]d[0]
715 
716  std::uint32_t pow10;
717  const int k = find_largest_pow10(p1, pow10);
718 
719  // 10^(k-1) <= p1 < 10^k, pow10 = 10^(k-1)
720  //
721  // p1 = (p1 div 10^(k-1)) * 10^(k-1) + (p1 mod 10^(k-1))
722  // = (d[k-1] ) * 10^(k-1) + (p1 mod 10^(k-1))
723  //
724  // M+ = p1 + p2 * 2^e
725  // = d[k-1] * 10^(k-1) + (p1 mod 10^(k-1)) + p2 * 2^e
726  // = d[k-1] * 10^(k-1) + ((p1 mod 10^(k-1)) * 2^-e + p2) * 2^e
727  // = d[k-1] * 10^(k-1) + ( rest) * 2^e
728  //
729  // Now generate the digits d[n] of p1 from left to right (n = k-1,...,0)
730  //
731  // p1 = d[k-1]...d[n] * 10^n + d[n-1]...d[0]
732  //
733  // but stop as soon as
734  //
735  // rest * 2^e = (d[n-1]...d[0] * 2^-e + p2) * 2^e <= delta * 2^e
736 
737  int n = k;
738  while (n > 0)
739  {
740  // Check that we are able to write the next symbol into the buffer
741  if (length >= max_length)
742  return false;
743 
744  // Invariants:
745  // M+ = buffer * 10^n + (p1 + p2 * 2^e) (buffer = 0 for n = k)
746  // pow10 = 10^(n-1) <= p1 < 10^n
747  //
748  const std::uint32_t d = p1 / pow10; // d = p1 div 10^(n-1)
749  const std::uint32_t r = p1 % pow10; // r = p1 mod 10^(n-1)
750  //
751  // M+ = buffer * 10^n + (d * 10^(n-1) + r) + p2 * 2^e
752  // = (buffer * 10 + d) * 10^(n-1) + (r + p2 * 2^e)
753  //
754  buffer[length++] =
755  static_cast<char>('0' + d); // buffer := buffer * 10 + d
756  //
757  // M+ = buffer * 10^(n-1) + (r + p2 * 2^e)
758  //
759  p1 = r;
760  n--;
761  //
762  // M+ = buffer * 10^n + (p1 + p2 * 2^e)
763  // pow10 = 10^n
764  //
765 
766  // Now check if enough digits have been generated.
767  // Compute
768  //
769  // p1 + p2 * 2^e = (p1 * 2^-e + p2) * 2^e = rest * 2^e
770  //
771  // Note:
772  // Since rest and delta share the same exponent e, it suffices to
773  // compare the significands.
774  const std::uint64_t rest = (std::uint64_t { p1 } << -one.e) + p2;
775  if (rest <= delta)
776  {
777  // V = buffer * 10^n, with M- <= V <= M+.
778 
779  decimal_exponent += n;
780 
781  // We may now just stop. But instead look if the buffer could be
782  // decremented to bring V closer to w.
783  //
784  // pow10 = 10^n is now 1 ulp in the decimal representation V.
785  // The rounding procedure works with diyfp's with an implicit
786  // exponent of e.
787  //
788  // 10^n = (10^n * 2^-e) * 2^e = ulp * 2^e
789  //
790  const std::uint64_t ten_n = std::uint64_t { pow10 } << -one.e;
791  grisu2_round(buffer, length, dist, delta, rest, ten_n);
792 
793  return true;
794  }
795 
796  pow10 /= 10;
797  //
798  // pow10 = 10^(n-1) <= p1 < 10^n
799  // Invariants restored.
800  }
801 
802  // 2)
803  //
804  // The digits of the integral part have been generated:
805  //
806  // M+ = d[k-1]...d[1]d[0] + p2 * 2^e
807  // = buffer + p2 * 2^e
808  //
809  // Now generate the digits of the fractional part p2 * 2^e.
810  //
811  // Note:
812  // No decimal point is generated: the exponent is adjusted instead.
813  //
814  // p2 actually represents the fraction
815  //
816  // p2 * 2^e
817  // = p2 / 2^-e
818  // = d[-1] / 10^1 + d[-2] / 10^2 + ...
819  //
820  // Now generate the digits d[-m] of p1 from left to right (m = 1,2,...)
821  //
822  // p2 * 2^e = d[-1]d[-2]...d[-m] * 10^-m
823  // + 10^-m * (d[-m-1] / 10^1 + d[-m-2] / 10^2 + ...)
824  //
825  // using
826  //
827  // 10^m * p2 = ((10^m * p2) div 2^-e) * 2^-e + ((10^m * p2) mod 2^-e)
828  // = ( d) * 2^-e + ( r)
829  //
830  // or
831  // 10^m * p2 * 2^e = d + r * 2^e
832  //
833  // i.e.
834  //
835  // M+ = buffer + p2 * 2^e
836  // = buffer + 10^-m * (d + r * 2^e)
837  // = (buffer * 10^m + d) * 10^-m + 10^-m * r * 2^e
838  //
839  // and stop as soon as 10^-m * r * 2^e <= delta * 2^e
840 
841  int m = 0;
842  for (;;)
843  {
844  // Check that we are able to write the next symbol into the buffer
845  if (length >= max_length)
846  return false;
847  // Invariant:
848  // M+ = buffer * 10^-m + 10^-m * (d[-m-1] / 10 + d[-m-2] / 10^2 +
849  // ...)
850  // * 2^e
851  // = buffer * 10^-m + 10^-m * (p2 )
852  // * 2^e = buffer * 10^-m + 10^-m * (1/10 * (10 * p2) ) * 2^e =
853  // buffer * 10^-m + 10^-m * (1/10 * ((10*p2 div 2^-e) * 2^-e +
854  // (10*p2 mod 2^-e)) * 2^e
855  //
856  p2 *= 10;
857  const std::uint64_t d = p2 >> -one.e; // d = (10 * p2) div 2^-e
858  const std::uint64_t r = p2 & (one.f - 1); // r = (10 * p2) mod 2^-e
859  //
860  // M+ = buffer * 10^-m + 10^-m * (1/10 * (d * 2^-e + r) * 2^e
861  // = buffer * 10^-m + 10^-m * (1/10 * (d + r * 2^e))
862  // = (buffer * 10 + d) * 10^(-m-1) + 10^(-m-1) * r * 2^e
863  //
864  buffer[length++] =
865  static_cast<char>('0' + d); // buffer := buffer * 10 + d
866  //
867  // M+ = buffer * 10^(-m-1) + 10^(-m-1) * r * 2^e
868  //
869  p2 = r;
870  m++;
871  //
872  // M+ = buffer * 10^-m + 10^-m * p2 * 2^e
873  // Invariant restored.
874 
875  // Check if enough digits have been generated.
876  //
877  // 10^-m * p2 * 2^e <= delta * 2^e
878  // p2 * 2^e <= 10^m * delta * 2^e
879  // p2 <= 10^m * delta
880  delta *= 10;
881  dist *= 10;
882  if (p2 <= delta)
883  {
884  break;
885  }
886  }
887 
888  // V = buffer * 10^-m, with M- <= V <= M+.
889 
890  decimal_exponent -= m;
891 
892  // 1 ulp in the decimal representation is now 10^-m.
893  // Since delta and dist are now scaled by 10^m, we need to do the
894  // same with ulp in order to keep the units in sync.
895  //
896  // 10^m * 10^-m = 1 = 2^-e * 2^e = ten_m * 2^e
897  //
898  const std::uint64_t ten_m = one.f;
899  grisu2_round(buffer, length, dist, delta, p2, ten_m);
900 
901  // By construction this algorithm generates the shortest possible decimal
902  // number (Loitsch, Theorem 6.2) which rounds back to w.
903  // For an input number of precision p, at least
904  //
905  // N = 1 + ceil(p * log_10(2))
906  //
907  // decimal digits are sufficient to identify all binary floating-point
908  // numbers (Matula, "In-and-Out conversions").
909  // This implies that the algorithm does not produce more than N decimal
910  // digits.
911  //
912  // N = 17 for p = 53 (IEEE double precision)
913  // N = 9 for p = 24 (IEEE single precision)
914 
915  return true;
916 }

References internal::dtoa_impl::diyfp::e, internal::dtoa_impl::diyfp::f, find_largest_pow10(), grisu2_round(), kAlpha, kGamma, and internal::dtoa_impl::diyfp::sub().

Referenced by grisu2().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ grisu2_round()

void internal::dtoa_impl::grisu2_round ( char *  buf,
int  len,
std::uint64_t  dist,
std::uint64_t  delta,
std::uint64_t  rest,
std::uint64_t  ten_k 
)
inline

Definition at line 633 of file ToChars.cpp.

636 {
637 
638  // <--------------------------- delta ---->
639  // <---- dist --------->
640  // --------------[------------------+-------------------]--------------
641  // M- w M+
642  //
643  // ten_k
644  // <------>
645  // <---- rest ---->
646  // --------------[------------------+----+--------------]--------------
647  // w V
648  // = buf * 10^k
649  //
650  // ten_k represents a unit-in-the-last-place in the decimal representation
651  // stored in buf.
652  // Decrement buf by ten_k while this takes buf closer to w.
653 
654  // The tests are written in this order to avoid overflow in unsigned
655  // integer arithmetic.
656 
657  while (rest < dist && delta - rest >= ten_k &&
658  (rest + ten_k < dist || dist - rest > rest + ten_k - dist))
659  {
660  buf[len - 1]--;
661  rest += ten_k;
662  }
663 }

Referenced by grisu2_digit_gen().

Here is the caller graph for this function:

◆ reinterpret_bits()

template<typename Target , typename Source >
Target internal::dtoa_impl::reinterpret_bits ( const Source  source)

Definition at line 154 of file ToChars.cpp.

155 {
156  static_assert(sizeof(Target) == sizeof(Source), "size mismatch");
157 
158  Target target;
159  std::memcpy(&target, &source, sizeof(Source));
160  return target;
161 }

Variable Documentation

◆ kAlpha

constexpr int internal::dtoa_impl::kAlpha = -60
constexpr

Definition at line 443 of file ToChars.cpp.

Referenced by get_cached_power_for_binary_exponent(), and grisu2_digit_gen().

◆ kGamma

constexpr int internal::dtoa_impl::kGamma = -32
constexpr

Definition at line 444 of file ToChars.cpp.

Referenced by grisu2_digit_gen().

internal::dtoa_impl::kGamma
constexpr int kGamma
Definition: ToChars.cpp:444
internal::dtoa_impl::grisu2_round
void grisu2_round(char *buf, int len, std::uint64_t dist, std::uint64_t delta, std::uint64_t rest, std::uint64_t ten_k)
Definition: ToChars.cpp:633
internal::dtoa_impl::kAlpha
constexpr int kAlpha
Definition: ToChars.cpp:443
internal::dtoa_impl::compute_boundaries
boundaries compute_boundaries(FloatType value)
Definition: ToChars.cpp:316
internal::dtoa_impl::find_largest_pow10
int find_largest_pow10(const std::uint32_t n, std::uint32_t &pow10)
Definition: ToChars.cpp:577
internal::dtoa_impl::get_cached_power_for_binary_exponent
cached_power get_cached_power_for_binary_exponent(int e)
Definition: ToChars.cpp:459
internal::dtoa_impl::grisu2_digit_gen
bool grisu2_digit_gen(char *buffer, char *last, int &length, int &decimal_exponent, diyfp M_minus, diyfp w, diyfp M_plus)
Definition: ToChars.cpp:669
internal::dtoa_impl::append_exponent
ToCharsResult append_exponent(char *buf, char *last, int e)
appends a decimal representation of e to buf
Definition: ToChars.cpp:1021
internal::dtoa_impl::grisu2
bool grisu2(char *buf, char *last, int &len, int &decimal_exponent, FloatType value)
Definition: ToChars.cpp:982