1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // Copyright (c) Microsoft Corporation. 10 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 11 12 // This implementation is dedicated to the memory of Mary and Thavatchai. 13 14 #ifndef _LIBCPP_SRC_INCLUDE_TO_CHARS_FLOATING_POINT_H 15 #define _LIBCPP_SRC_INCLUDE_TO_CHARS_FLOATING_POINT_H 16 17 // Avoid formatting to keep the changes with the original code minimal. 18 // clang-format off 19 20 #include "__algorithm/find.h" 21 #include "__algorithm/find_if.h" 22 #include "__algorithm/lower_bound.h" 23 #include "__algorithm/min.h" 24 #include "__config" 25 #include "__iterator/access.h" 26 #include "__iterator/size.h" 27 #include "bit" 28 #include "cfloat" 29 #include "climits" 30 #include "include/ryu/ryu.h" 31 32 _LIBCPP_BEGIN_NAMESPACE_STD 33 34 namespace __itoa { 35 inline constexpr char _Charconv_digits[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 36 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; 37 static_assert(_VSTD::size(_Charconv_digits) == 36); 38 } // __itoa 39 40 // vvvvvvvvvv DERIVED FROM corecrt_internal_fltintrn.h vvvvvvvvvv 41 42 template <class _FloatingType> 43 struct _Floating_type_traits; 44 45 template <> 46 struct _Floating_type_traits<float> { 47 static constexpr int32_t _Mantissa_bits = FLT_MANT_DIG; 48 static constexpr int32_t _Exponent_bits = sizeof(float) * CHAR_BIT - FLT_MANT_DIG; 49 50 static constexpr int32_t _Maximum_binary_exponent = FLT_MAX_EXP - 1; 51 static constexpr int32_t _Minimum_binary_exponent = FLT_MIN_EXP - 1; 52 53 static constexpr int32_t _Exponent_bias = 127; 54 55 static constexpr int32_t _Sign_shift = _Exponent_bits + _Mantissa_bits - 1; 56 static constexpr int32_t _Exponent_shift = _Mantissa_bits - 1; 57 58 using _Uint_type = uint32_t; 59 60 static constexpr uint32_t _Exponent_mask = (1u << _Exponent_bits) - 1; 61 static constexpr uint32_t _Normal_mantissa_mask = (1u << _Mantissa_bits) - 1; 62 static constexpr uint32_t _Denormal_mantissa_mask = (1u << (_Mantissa_bits - 1)) - 1; 63 static constexpr uint32_t _Special_nan_mantissa_mask = 1u << (_Mantissa_bits - 2); 64 static constexpr uint32_t _Shifted_sign_mask = 1u << _Sign_shift; 65 static constexpr uint32_t _Shifted_exponent_mask = _Exponent_mask << _Exponent_shift; 66 }; 67 68 template <> 69 struct _Floating_type_traits<double> { 70 static constexpr int32_t _Mantissa_bits = DBL_MANT_DIG; 71 static constexpr int32_t _Exponent_bits = sizeof(double) * CHAR_BIT - DBL_MANT_DIG; 72 73 static constexpr int32_t _Maximum_binary_exponent = DBL_MAX_EXP - 1; 74 static constexpr int32_t _Minimum_binary_exponent = DBL_MIN_EXP - 1; 75 76 static constexpr int32_t _Exponent_bias = 1023; 77 78 static constexpr int32_t _Sign_shift = _Exponent_bits + _Mantissa_bits - 1; 79 static constexpr int32_t _Exponent_shift = _Mantissa_bits - 1; 80 81 using _Uint_type = uint64_t; 82 83 static constexpr uint64_t _Exponent_mask = (1ULL << _Exponent_bits) - 1; 84 static constexpr uint64_t _Normal_mantissa_mask = (1ULL << _Mantissa_bits) - 1; 85 static constexpr uint64_t _Denormal_mantissa_mask = (1ULL << (_Mantissa_bits - 1)) - 1; 86 static constexpr uint64_t _Special_nan_mantissa_mask = 1ULL << (_Mantissa_bits - 2); 87 static constexpr uint64_t _Shifted_sign_mask = 1ULL << _Sign_shift; 88 static constexpr uint64_t _Shifted_exponent_mask = _Exponent_mask << _Exponent_shift; 89 }; 90 91 // ^^^^^^^^^^ DERIVED FROM corecrt_internal_fltintrn.h ^^^^^^^^^^ 92 93 // FUNCTION to_chars (FLOATING-POINT TO STRING) 94 template <class _Floating> 95 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 96 to_chars_result _Floating_to_chars_hex_precision( 97 char* _First, char* const _Last, const _Floating _Value, int _Precision) noexcept { 98 99 // * Determine the effective _Precision. 100 // * Later, we'll decrement _Precision when printing each hexit after the decimal point. 101 102 // The hexits after the decimal point correspond to the explicitly stored fraction bits. 103 // float explicitly stores 23 fraction bits. 23 / 4 == 5.75, which is 6 hexits. 104 // double explicitly stores 52 fraction bits. 52 / 4 == 13, which is 13 hexits. 105 constexpr int _Full_precision = _IsSame<_Floating, float>::value ? 6 : 13; 106 constexpr int _Adjusted_explicit_bits = _Full_precision * 4; 107 108 if (_Precision < 0) { 109 // C11 7.21.6.1 "The fprintf function"/5: "A negative precision argument is taken as if the precision were 110 // omitted." /8: "if the precision is missing and FLT_RADIX is a power of 2, then the precision is sufficient 111 // for an exact representation of the value" 112 _Precision = _Full_precision; 113 } 114 115 // * Extract the _Ieee_mantissa and _Ieee_exponent. 116 using _Traits = _Floating_type_traits<_Floating>; 117 using _Uint_type = typename _Traits::_Uint_type; 118 119 const _Uint_type _Uint_value = _VSTD::bit_cast<_Uint_type>(_Value); 120 const _Uint_type _Ieee_mantissa = _Uint_value & _Traits::_Denormal_mantissa_mask; 121 const int32_t _Ieee_exponent = static_cast<int32_t>(_Uint_value >> _Traits::_Exponent_shift); 122 123 // * Prepare the _Adjusted_mantissa. This is aligned to hexit boundaries, 124 // * with the implicit bit restored (0 for zero values and subnormal values, 1 for normal values). 125 // * Also calculate the _Unbiased_exponent. This unifies the processing of zero, subnormal, and normal values. 126 _Uint_type _Adjusted_mantissa; 127 128 if constexpr (_IsSame<_Floating, float>::value) { 129 _Adjusted_mantissa = _Ieee_mantissa << 1; // align to hexit boundary (23 isn't divisible by 4) 130 } else { 131 _Adjusted_mantissa = _Ieee_mantissa; // already aligned (52 is divisible by 4) 132 } 133 134 int32_t _Unbiased_exponent; 135 136 if (_Ieee_exponent == 0) { // zero or subnormal 137 // implicit bit is 0 138 139 if (_Ieee_mantissa == 0) { // zero 140 // C11 7.21.6.1 "The fprintf function"/8: "If the value is zero, the exponent is zero." 141 _Unbiased_exponent = 0; 142 } else { // subnormal 143 _Unbiased_exponent = 1 - _Traits::_Exponent_bias; 144 } 145 } else { // normal 146 _Adjusted_mantissa |= _Uint_type{1} << _Adjusted_explicit_bits; // implicit bit is 1 147 _Unbiased_exponent = _Ieee_exponent - _Traits::_Exponent_bias; 148 } 149 150 // _Unbiased_exponent is within [-126, 127] for float, [-1022, 1023] for double. 151 152 // * Decompose _Unbiased_exponent into _Sign_character and _Absolute_exponent. 153 char _Sign_character; 154 uint32_t _Absolute_exponent; 155 156 if (_Unbiased_exponent < 0) { 157 _Sign_character = '-'; 158 _Absolute_exponent = static_cast<uint32_t>(-_Unbiased_exponent); 159 } else { 160 _Sign_character = '+'; 161 _Absolute_exponent = static_cast<uint32_t>(_Unbiased_exponent); 162 } 163 164 // _Absolute_exponent is within [0, 127] for float, [0, 1023] for double. 165 166 // * Perform a single bounds check. 167 { 168 int32_t _Exponent_length; 169 170 if (_Absolute_exponent < 10) { 171 _Exponent_length = 1; 172 } else if (_Absolute_exponent < 100) { 173 _Exponent_length = 2; 174 } else if constexpr (_IsSame<_Floating, float>::value) { 175 _Exponent_length = 3; 176 } else if (_Absolute_exponent < 1000) { 177 _Exponent_length = 3; 178 } else { 179 _Exponent_length = 4; 180 } 181 182 // _Precision might be enormous; avoid integer overflow by testing it separately. 183 ptrdiff_t _Buffer_size = _Last - _First; 184 185 if (_Buffer_size < _Precision) { 186 return {_Last, errc::value_too_large}; 187 } 188 189 _Buffer_size -= _Precision; 190 191 const int32_t _Length_excluding_precision = 1 // leading hexit 192 + static_cast<int32_t>(_Precision > 0) // possible decimal point 193 // excluding `+ _Precision`, hexits after decimal point 194 + 2 // "p+" or "p-" 195 + _Exponent_length; // exponent 196 197 if (_Buffer_size < _Length_excluding_precision) { 198 return {_Last, errc::value_too_large}; 199 } 200 } 201 202 // * Perform rounding when we've been asked to omit hexits. 203 if (_Precision < _Full_precision) { 204 // _Precision is within [0, 5] for float, [0, 12] for double. 205 206 // _Dropped_bits is within [4, 24] for float, [4, 52] for double. 207 const int _Dropped_bits = (_Full_precision - _Precision) * 4; 208 209 // Perform rounding by adding an appropriately-shifted bit. 210 211 // This can propagate carries all the way into the leading hexit. Examples: 212 // "0.ff9" rounded to a precision of 2 is "1.00". 213 // "1.ff9" rounded to a precision of 2 is "2.00". 214 215 // Note that the leading hexit participates in the rounding decision. Examples: 216 // "0.8" rounded to a precision of 0 is "0". 217 // "1.8" rounded to a precision of 0 is "2". 218 219 // Reference implementation with suboptimal codegen: 220 // bool _Should_round_up(bool _Lsb_bit, bool _Round_bit, bool _Has_tail_bits) { 221 // // If there are no insignificant set bits, the value is exactly-representable and should not be rounded. 222 // // 223 // // If there are insignificant set bits, we need to round according to round_to_nearest. 224 // // We need to handle two cases: we round up if either [1] the value is slightly greater 225 // // than the midpoint between two exactly-representable values or [2] the value is exactly the midpoint 226 // // between two exactly-representable values and the greater of the two is even (this is "round-to-even"). 227 // return _Round_bit && (_Has_tail_bits || _Lsb_bit); 228 //} 229 // const bool _Lsb_bit = (_Adjusted_mantissa & (_Uint_type{1} << _Dropped_bits)) != 0; 230 // const bool _Round_bit = (_Adjusted_mantissa & (_Uint_type{1} << (_Dropped_bits - 1))) != 0; 231 // const bool _Has_tail_bits = (_Adjusted_mantissa & ((_Uint_type{1} << (_Dropped_bits - 1)) - 1)) != 0; 232 // const bool _Should_round = _Should_round_up(_Lsb_bit, _Round_bit, _Has_tail_bits); 233 // _Adjusted_mantissa += _Uint_type{_Should_round} << _Dropped_bits; 234 235 // Example for optimized implementation: Let _Dropped_bits be 8. 236 // Bit index: ...[8]76543210 237 // _Adjusted_mantissa: ...[L]RTTTTTTT (not depicting known details, like hexit alignment) 238 // By focusing on the bit at index _Dropped_bits, we can avoid unnecessary branching and shifting. 239 240 // Bit index: ...[8]76543210 241 // _Lsb_bit: ...[L]RTTTTTTT 242 const _Uint_type _Lsb_bit = _Adjusted_mantissa; 243 244 // Bit index: ...9[8]76543210 245 // _Round_bit: ...L[R]TTTTTTT0 246 const _Uint_type _Round_bit = _Adjusted_mantissa << 1; 247 248 // We can detect (without branching) whether any of the trailing bits are set. 249 // Due to _Should_round below, this computation will be used if and only if R is 1, so we can assume that here. 250 // Bit index: ...9[8]76543210 251 // _Round_bit: ...L[1]TTTTTTT0 252 // _Has_tail_bits: ....[H]........ 253 254 // If all of the trailing bits T are 0, then `_Round_bit - 1` will produce 0 for H (due to R being 1). 255 // If any of the trailing bits T are 1, then `_Round_bit - 1` will produce 1 for H (due to R being 1). 256 const _Uint_type _Has_tail_bits = _Round_bit - 1; 257 258 // Finally, we can use _Should_round_up() logic with bitwise-AND and bitwise-OR, 259 // selecting just the bit at index _Dropped_bits. This is the appropriately-shifted bit that we want. 260 const _Uint_type _Should_round = _Round_bit & (_Has_tail_bits | _Lsb_bit) & (_Uint_type{1} << _Dropped_bits); 261 262 // This rounding technique is dedicated to the memory of Peppermint. =^..^= 263 _Adjusted_mantissa += _Should_round; 264 } 265 266 // * Print the leading hexit, then mask it away. 267 { 268 const uint32_t _Nibble = static_cast<uint32_t>(_Adjusted_mantissa >> _Adjusted_explicit_bits); 269 _LIBCPP_ASSERT(_Nibble < 3, ""); 270 const char _Leading_hexit = static_cast<char>('0' + _Nibble); 271 272 *_First++ = _Leading_hexit; 273 274 constexpr _Uint_type _Mask = (_Uint_type{1} << _Adjusted_explicit_bits) - 1; 275 _Adjusted_mantissa &= _Mask; 276 } 277 278 // * Print the decimal point and trailing hexits. 279 280 // C11 7.21.6.1 "The fprintf function"/8: 281 // "if the precision is zero and the # flag is not specified, no decimal-point character appears." 282 if (_Precision > 0) { 283 *_First++ = '.'; 284 285 int32_t _Number_of_bits_remaining = _Adjusted_explicit_bits; // 24 for float, 52 for double 286 287 for (;;) { 288 _LIBCPP_ASSERT(_Number_of_bits_remaining >= 4, ""); 289 _LIBCPP_ASSERT(_Number_of_bits_remaining % 4 == 0, ""); 290 _Number_of_bits_remaining -= 4; 291 292 const uint32_t _Nibble = static_cast<uint32_t>(_Adjusted_mantissa >> _Number_of_bits_remaining); 293 _LIBCPP_ASSERT(_Nibble < 16, ""); 294 const char _Hexit = __itoa::_Charconv_digits[_Nibble]; 295 296 *_First++ = _Hexit; 297 298 // _Precision is the number of hexits that still need to be printed. 299 --_Precision; 300 if (_Precision == 0) { 301 break; // We're completely done with this phase. 302 } 303 // Otherwise, we need to keep printing hexits. 304 305 if (_Number_of_bits_remaining == 0) { 306 // We've finished printing _Adjusted_mantissa, so all remaining hexits are '0'. 307 _VSTD::memset(_First, '0', static_cast<size_t>(_Precision)); 308 _First += _Precision; 309 break; 310 } 311 312 // Mask away the hexit that we just printed, then keep looping. 313 // (We skip this when breaking out of the loop above, because _Adjusted_mantissa isn't used later.) 314 const _Uint_type _Mask = (_Uint_type{1} << _Number_of_bits_remaining) - 1; 315 _Adjusted_mantissa &= _Mask; 316 } 317 } 318 319 // * Print the exponent. 320 321 // C11 7.21.6.1 "The fprintf function"/8: "The exponent always contains at least one digit, and only as many more 322 // digits as necessary to represent the decimal exponent of 2." 323 324 // Performance note: We should take advantage of the known ranges of possible exponents. 325 326 *_First++ = 'p'; 327 *_First++ = _Sign_character; 328 329 // We've already printed '-' if necessary, so uint32_t _Absolute_exponent avoids testing that again. 330 return _VSTD::to_chars(_First, _Last, _Absolute_exponent); 331 } 332 333 template <class _Floating> 334 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 335 to_chars_result _Floating_to_chars_hex_shortest( 336 char* _First, char* const _Last, const _Floating _Value) noexcept { 337 338 // This prints "1.728p+0" instead of "2.e5p-1". 339 // This prints "0.000002p-126" instead of "1p-149" for float. 340 // This prints "0.0000000000001p-1022" instead of "1p-1074" for double. 341 // This prioritizes being consistent with printf's de facto behavior (and hex-precision's behavior) 342 // over minimizing the number of characters printed. 343 344 using _Traits = _Floating_type_traits<_Floating>; 345 using _Uint_type = typename _Traits::_Uint_type; 346 347 const _Uint_type _Uint_value = _VSTD::bit_cast<_Uint_type>(_Value); 348 349 if (_Uint_value == 0) { // zero detected; write "0p+0" and return 350 // C11 7.21.6.1 "The fprintf function"/8: "If the value is zero, the exponent is zero." 351 // Special-casing zero is necessary because of the exponent. 352 const char* const _Str = "0p+0"; 353 const size_t _Len = 4; 354 355 if (_Last - _First < static_cast<ptrdiff_t>(_Len)) { 356 return {_Last, errc::value_too_large}; 357 } 358 359 _VSTD::memcpy(_First, _Str, _Len); 360 361 return {_First + _Len, errc{}}; 362 } 363 364 const _Uint_type _Ieee_mantissa = _Uint_value & _Traits::_Denormal_mantissa_mask; 365 const int32_t _Ieee_exponent = static_cast<int32_t>(_Uint_value >> _Traits::_Exponent_shift); 366 367 char _Leading_hexit; // implicit bit 368 int32_t _Unbiased_exponent; 369 370 if (_Ieee_exponent == 0) { // subnormal 371 _Leading_hexit = '0'; 372 _Unbiased_exponent = 1 - _Traits::_Exponent_bias; 373 } else { // normal 374 _Leading_hexit = '1'; 375 _Unbiased_exponent = _Ieee_exponent - _Traits::_Exponent_bias; 376 } 377 378 // Performance note: Consider avoiding per-character bounds checking when there's plenty of space. 379 380 if (_First == _Last) { 381 return {_Last, errc::value_too_large}; 382 } 383 384 *_First++ = _Leading_hexit; 385 386 if (_Ieee_mantissa == 0) { 387 // The fraction bits are all 0. Trim them away, including the decimal point. 388 } else { 389 if (_First == _Last) { 390 return {_Last, errc::value_too_large}; 391 } 392 393 *_First++ = '.'; 394 395 // The hexits after the decimal point correspond to the explicitly stored fraction bits. 396 // float explicitly stores 23 fraction bits. 23 / 4 == 5.75, so we'll print at most 6 hexits. 397 // double explicitly stores 52 fraction bits. 52 / 4 == 13, so we'll print at most 13 hexits. 398 _Uint_type _Adjusted_mantissa; 399 int32_t _Number_of_bits_remaining; 400 401 if constexpr (_IsSame<_Floating, float>::value) { 402 _Adjusted_mantissa = _Ieee_mantissa << 1; // align to hexit boundary (23 isn't divisible by 4) 403 _Number_of_bits_remaining = 24; // 23 fraction bits + 1 alignment bit 404 } else { 405 _Adjusted_mantissa = _Ieee_mantissa; // already aligned (52 is divisible by 4) 406 _Number_of_bits_remaining = 52; // 52 fraction bits 407 } 408 409 // do-while: The condition _Adjusted_mantissa != 0 is initially true - we have nonzero fraction bits and we've 410 // printed the decimal point. Each iteration, we print a hexit, mask it away, and keep looping if we still have 411 // nonzero fraction bits. If there would be trailing '0' hexits, this trims them. If there wouldn't be trailing 412 // '0' hexits, the same condition works (as we print the final hexit and mask it away); we don't need to test 413 // _Number_of_bits_remaining. 414 do { 415 _LIBCPP_ASSERT(_Number_of_bits_remaining >= 4, ""); 416 _LIBCPP_ASSERT(_Number_of_bits_remaining % 4 == 0, ""); 417 _Number_of_bits_remaining -= 4; 418 419 const uint32_t _Nibble = static_cast<uint32_t>(_Adjusted_mantissa >> _Number_of_bits_remaining); 420 _LIBCPP_ASSERT(_Nibble < 16, ""); 421 const char _Hexit = __itoa::_Charconv_digits[_Nibble]; 422 423 if (_First == _Last) { 424 return {_Last, errc::value_too_large}; 425 } 426 427 *_First++ = _Hexit; 428 429 const _Uint_type _Mask = (_Uint_type{1} << _Number_of_bits_remaining) - 1; 430 _Adjusted_mantissa &= _Mask; 431 432 } while (_Adjusted_mantissa != 0); 433 } 434 435 // C11 7.21.6.1 "The fprintf function"/8: "The exponent always contains at least one digit, and only as many more 436 // digits as necessary to represent the decimal exponent of 2." 437 438 // Performance note: We should take advantage of the known ranges of possible exponents. 439 440 // float: _Unbiased_exponent is within [-126, 127]. 441 // double: _Unbiased_exponent is within [-1022, 1023]. 442 443 if (_Last - _First < 2) { 444 return {_Last, errc::value_too_large}; 445 } 446 447 *_First++ = 'p'; 448 449 if (_Unbiased_exponent < 0) { 450 *_First++ = '-'; 451 _Unbiased_exponent = -_Unbiased_exponent; 452 } else { 453 *_First++ = '+'; 454 } 455 456 // We've already printed '-' if necessary, so static_cast<uint32_t> avoids testing that again. 457 return _VSTD::to_chars(_First, _Last, static_cast<uint32_t>(_Unbiased_exponent)); 458 } 459 460 // For general precision, we can use lookup tables to avoid performing trial formatting. 461 462 // For a simple example, imagine counting the number of digits D in an integer, and needing to know 463 // whether D is less than 3, equal to 3/4/5/6, or greater than 6. We could use a lookup table: 464 // D | Largest integer with D digits 465 // 2 | 99 466 // 3 | 999 467 // 4 | 9'999 468 // 5 | 99'999 469 // 6 | 999'999 470 // 7 | table end 471 // Looking up an integer in this table with lower_bound() will work: 472 // * Too-small integers, like 7, 70, and 99, will cause lower_bound() to return the D == 2 row. (If all we care 473 // about is whether D is less than 3, then it's okay to smash the D == 1 and D == 2 cases together.) 474 // * Integers in [100, 999] will cause lower_bound() to return the D == 3 row, and so forth. 475 // * Too-large integers, like 1'000'000 and above, will cause lower_bound() to return the end of the table. If we 476 // compute D from that index, this will be considered D == 7, which will activate any "greater than 6" logic. 477 478 // Floating-point is slightly more complicated. 479 480 // The ordinary lookup tables are for X within [-5, 38] for float, and [-5, 308] for double. 481 // (-5 absorbs too-negative exponents, outside the P > X >= -4 criterion. 38 and 308 are the maximum exponents.) 482 // Due to the P > X condition, we can use a subset of the table for X within [-5, P - 1], suitably clamped. 483 484 // When P is small, rounding can affect X. For example: 485 // For P == 1, the largest double with X == 0 is: 9.4999999999999982236431605997495353221893310546875 486 // For P == 2, the largest double with X == 0 is: 9.949999999999999289457264239899814128875732421875 487 // For P == 3, the largest double with X == 0 is: 9.9949999999999992184029906638897955417633056640625 488 489 // Exponent adjustment is a concern for P within [1, 7] for float, and [1, 15] for double (determined via 490 // brute force). While larger values of P still perform rounding, they can't trigger exponent adjustment. 491 // This is because only values with repeated '9' digits can undergo exponent adjustment during rounding, 492 // and floating-point granularity limits the number of consecutive '9' digits that can appear. 493 494 // So, we need special lookup tables for small values of P. 495 // These tables have varying lengths due to the P > X >= -4 criterion. For example: 496 // For P == 1, need table entries for X: -5, -4, -3, -2, -1, 0 497 // For P == 2, need table entries for X: -5, -4, -3, -2, -1, 0, 1 498 // For P == 3, need table entries for X: -5, -4, -3, -2, -1, 0, 1, 2 499 // For P == 4, need table entries for X: -5, -4, -3, -2, -1, 0, 1, 2, 3 500 501 // We can concatenate these tables for compact storage, using triangular numbers to access them. 502 // The table for P begins at index (P - 1) * (P + 10) / 2 with length P + 5. 503 504 // For both the ordinary and special lookup tables, after an index I is returned by lower_bound(), X is I - 5. 505 506 // We need to special-case the floating-point value 0.0, which is considered to have X == 0. 507 // Otherwise, the lookup tables would consider it to have a highly negative X. 508 509 // Finally, because we're working with positive floating-point values, 510 // representation comparisons behave identically to floating-point comparisons. 511 512 // The following code generated the lookup tables for the scientific exponent X. Don't remove this code. 513 #if 0 514 // cl /EHsc /nologo /W4 /MT /O2 /std:c++17 generate_tables.cpp && generate_tables 515 516 #include <algorithm> 517 #include <assert.h> 518 #include <charconv> 519 #include <cmath> 520 #include <limits> 521 #include <map> 522 #include <stdint.h> 523 #include <stdio.h> 524 #include <system_error> 525 #include <type_traits> 526 #include <vector> 527 using namespace std; 528 529 template <typename UInt, typename Pred> 530 [[nodiscard]] UInt uint_partition_point(UInt first, const UInt last, Pred pred) { 531 // Find the beginning of the false partition in [first, last). 532 // [first, last) is partitioned when all of the true values occur before all of the false values. 533 534 static_assert(is_unsigned_v<UInt>); 535 assert(first <= last); 536 537 for (UInt n = last - first; n > 0;) { 538 const UInt n2 = n / 2; 539 const UInt mid = first + n2; 540 541 if (pred(mid)) { 542 first = mid + 1; 543 n = n - n2 - 1; 544 } else { 545 n = n2; 546 } 547 } 548 549 return first; 550 } 551 552 template <typename Floating> 553 [[nodiscard]] int scientific_exponent_X(const int P, const Floating flt) { 554 char buf[400]; // more than enough 555 556 // C11 7.21.6.1 "The fprintf function"/8 performs trial formatting with scientific precision P - 1. 557 const auto to_result = to_chars(buf, end(buf), flt, chars_format::scientific, P - 1); 558 assert(to_result.ec == errc{}); 559 560 const char* exp_ptr = find(buf, to_result.ptr, 'e'); 561 assert(exp_ptr != to_result.ptr); 562 563 ++exp_ptr; // advance past 'e' 564 565 if (*exp_ptr == '+') { 566 ++exp_ptr; // advance past '+' which from_chars() won't parse 567 } 568 569 int X; 570 const auto from_result = from_chars(exp_ptr, to_result.ptr, X); 571 assert(from_result.ec == errc{}); 572 return X; 573 } 574 575 template <typename UInt> 576 void print_table(const vector<UInt>& v, const char* const name) { 577 constexpr const char* UIntName = _IsSame<UInt, uint32_t>::value ? "uint32_t" : "uint64_t"; 578 579 printf("static constexpr %s %s[%zu] = {\n", UIntName, name, v.size()); 580 581 for (const auto& val : v) { 582 if constexpr (_IsSame<UInt, uint32_t>::value) { 583 printf("0x%08Xu,\n", val); 584 } else { 585 printf("0x%016llXu,\n", val); 586 } 587 } 588 589 printf("};\n"); 590 } 591 592 enum class Mode { Tables, Tests }; 593 594 template <typename Floating> 595 void generate_tables(const Mode mode) { 596 using Limits = numeric_limits<Floating>; 597 using UInt = conditional_t<_IsSame<Floating, float>::value, uint32_t, uint64_t>; 598 599 map<int, map<int, UInt>> P_X_LargestValWithX; 600 601 constexpr int MaxP = Limits::max_exponent10 + 1; // MaxP performs no rounding during trial formatting 602 603 for (int P = 1; P <= MaxP; ++P) { 604 for (int X = -5; X < P; ++X) { 605 constexpr Floating first = static_cast<Floating>(9e-5); // well below 9.5e-5, otherwise arbitrary 606 constexpr Floating last = Limits::infinity(); // one bit above Limits::max() 607 608 const UInt val_beyond_X = uint_partition_point(reinterpret_cast<const UInt&>(first), 609 reinterpret_cast<const UInt&>(last), 610 [P, X](const UInt u) { return scientific_exponent_X(P, reinterpret_cast<const Floating&>(u)) <= X; }); 611 612 P_X_LargestValWithX[P][X] = val_beyond_X - 1; 613 } 614 } 615 616 constexpr const char* FloatingName = _IsSame<Floating, float>::value ? "float" : "double"; 617 618 constexpr int MaxSpecialP = _IsSame<Floating, float>::value ? 7 : 15; // MaxSpecialP is affected by exponent adjustment 619 620 if (mode == Mode::Tables) { 621 printf("template <>\n"); 622 printf("struct _General_precision_tables<%s> {\n", FloatingName); 623 624 printf("static constexpr int _Max_special_P = %d;\n", MaxSpecialP); 625 626 vector<UInt> special; 627 628 for (int P = 1; P <= MaxSpecialP; ++P) { 629 for (int X = -5; X < P; ++X) { 630 const UInt val = P_X_LargestValWithX[P][X]; 631 special.push_back(val); 632 } 633 } 634 635 print_table(special, "_Special_X_table"); 636 637 for (int P = MaxSpecialP + 1; P < MaxP; ++P) { 638 for (int X = -5; X < P; ++X) { 639 const UInt val = P_X_LargestValWithX[P][X]; 640 assert(val == P_X_LargestValWithX[MaxP][X]); 641 } 642 } 643 644 printf("static constexpr int _Max_P = %d;\n", MaxP); 645 646 vector<UInt> ordinary; 647 648 for (int X = -5; X < MaxP; ++X) { 649 const UInt val = P_X_LargestValWithX[MaxP][X]; 650 ordinary.push_back(val); 651 } 652 653 print_table(ordinary, "_Ordinary_X_table"); 654 655 printf("};\n"); 656 } else { 657 printf("==========\n"); 658 printf("Test cases for %s:\n", FloatingName); 659 660 constexpr int Hexits = _IsSame<Floating, float>::value ? 6 : 13; 661 constexpr const char* Suffix = _IsSame<Floating, float>::value ? "f" : ""; 662 663 for (int P = 1; P <= MaxP; ++P) { 664 for (int X = -5; X < P; ++X) { 665 if (P <= MaxSpecialP || P == 25 || P == MaxP || X == P - 1) { 666 const UInt val1 = P_X_LargestValWithX[P][X]; 667 const Floating f1 = reinterpret_cast<const Floating&>(val1); 668 const UInt val2 = val1 + 1; 669 const Floating f2 = reinterpret_cast<const Floating&>(val2); 670 671 printf("{%.*a%s, chars_format::general, %d, \"%.*g\"},\n", Hexits, f1, Suffix, P, P, f1); 672 if (isfinite(f2)) { 673 printf("{%.*a%s, chars_format::general, %d, \"%.*g\"},\n", Hexits, f2, Suffix, P, P, f2); 674 } 675 } 676 } 677 } 678 } 679 } 680 681 int main() { 682 printf("template <class _Floating>\n"); 683 printf("struct _General_precision_tables;\n"); 684 generate_tables<float>(Mode::Tables); 685 generate_tables<double>(Mode::Tables); 686 generate_tables<float>(Mode::Tests); 687 generate_tables<double>(Mode::Tests); 688 } 689 #endif // 0 690 691 template <class _Floating> 692 struct _General_precision_tables; 693 694 template <> 695 struct _General_precision_tables<float> { 696 static constexpr int _Max_special_P = 7; 697 698 static constexpr uint32_t _Special_X_table[63] = {0x38C73ABCu, 0x3A79096Bu, 0x3C1BA5E3u, 0x3DC28F5Cu, 0x3F733333u, 699 0x4117FFFFu, 0x38D0AAA7u, 0x3A826AA8u, 0x3C230553u, 0x3DCBC6A7u, 0x3F7EB851u, 0x411F3333u, 0x42C6FFFFu, 700 0x38D19C3Fu, 0x3A8301A7u, 0x3C23C211u, 0x3DCCB295u, 0x3F7FDF3Bu, 0x411FEB85u, 0x42C7E666u, 0x4479DFFFu, 701 0x38D1B468u, 0x3A8310C1u, 0x3C23D4F1u, 0x3DCCCA2Du, 0x3F7FFCB9u, 0x411FFDF3u, 0x42C7FD70u, 0x4479FCCCu, 702 0x461C3DFFu, 0x38D1B6D2u, 0x3A831243u, 0x3C23D6D4u, 0x3DCCCC89u, 0x3F7FFFACu, 0x411FFFCBu, 0x42C7FFBEu, 703 0x4479FFAEu, 0x461C3FCCu, 0x47C34FBFu, 0x38D1B710u, 0x3A83126Au, 0x3C23D704u, 0x3DCCCCC6u, 0x3F7FFFF7u, 704 0x411FFFFAu, 0x42C7FFF9u, 0x4479FFF7u, 0x461C3FFAu, 0x47C34FF9u, 0x497423F7u, 0x38D1B716u, 0x3A83126Eu, 705 0x3C23D709u, 0x3DCCCCCCu, 0x3F7FFFFFu, 0x411FFFFFu, 0x42C7FFFFu, 0x4479FFFFu, 0x461C3FFFu, 0x47C34FFFu, 706 0x497423FFu, 0x4B18967Fu}; 707 708 static constexpr int _Max_P = 39; 709 710 static constexpr uint32_t _Ordinary_X_table[44] = {0x38D1B717u, 0x3A83126Eu, 0x3C23D70Au, 0x3DCCCCCCu, 0x3F7FFFFFu, 711 0x411FFFFFu, 0x42C7FFFFu, 0x4479FFFFu, 0x461C3FFFu, 0x47C34FFFu, 0x497423FFu, 0x4B18967Fu, 0x4CBEBC1Fu, 712 0x4E6E6B27u, 0x501502F8u, 0x51BA43B7u, 0x5368D4A5u, 0x551184E7u, 0x56B5E620u, 0x58635FA9u, 0x5A0E1BC9u, 713 0x5BB1A2BCu, 0x5D5E0B6Bu, 0x5F0AC723u, 0x60AD78EBu, 0x6258D726u, 0x64078678u, 0x65A96816u, 0x6753C21Bu, 714 0x69045951u, 0x6AA56FA5u, 0x6C4ECB8Fu, 0x6E013F39u, 0x6FA18F07u, 0x7149F2C9u, 0x72FC6F7Cu, 0x749DC5ADu, 715 0x76453719u, 0x77F684DFu, 0x799A130Bu, 0x7B4097CEu, 0x7CF0BDC2u, 0x7E967699u, 0x7F7FFFFFu}; 716 }; 717 718 template <> 719 struct _General_precision_tables<double> { 720 static constexpr int _Max_special_P = 15; 721 722 static constexpr uint64_t _Special_X_table[195] = {0x3F18E757928E0C9Du, 0x3F4F212D77318FC5u, 0x3F8374BC6A7EF9DBu, 723 0x3FB851EB851EB851u, 0x3FEE666666666666u, 0x4022FFFFFFFFFFFFu, 0x3F1A1554FBDAD751u, 0x3F504D551D68C692u, 724 0x3F8460AA64C2F837u, 0x3FB978D4FDF3B645u, 0x3FEFD70A3D70A3D7u, 0x4023E66666666666u, 0x4058DFFFFFFFFFFFu, 725 0x3F1A3387ECC8EB96u, 0x3F506034F3FD933Eu, 0x3F84784230FCF80Du, 0x3FB99652BD3C3611u, 0x3FEFFBE76C8B4395u, 726 0x4023FD70A3D70A3Du, 0x4058FCCCCCCCCCCCu, 0x408F3BFFFFFFFFFFu, 0x3F1A368D04E0BA6Au, 0x3F506218230C7482u, 727 0x3F847A9E2BCF91A3u, 0x3FB99945B6C3760Bu, 0x3FEFFF972474538Eu, 0x4023FFBE76C8B439u, 0x4058FFAE147AE147u, 728 0x408F3F9999999999u, 0x40C387BFFFFFFFFFu, 0x3F1A36DA54164F19u, 0x3F506248748DF16Fu, 0x3F847ADA91B16DCBu, 729 0x3FB99991361DC93Eu, 0x3FEFFFF583A53B8Eu, 0x4023FFF972474538u, 0x4058FFF7CED91687u, 0x408F3FF5C28F5C28u, 730 0x40C387F999999999u, 0x40F869F7FFFFFFFFu, 0x3F1A36E20F35445Du, 0x3F50624D49814ABAu, 0x3F847AE09BE19D69u, 731 0x3FB99998C2DA04C3u, 0x3FEFFFFEF39085F4u, 0x4023FFFF583A53B8u, 0x4058FFFF2E48E8A7u, 0x408F3FFEF9DB22D0u, 732 0x40C387FF5C28F5C2u, 0x40F869FF33333333u, 0x412E847EFFFFFFFFu, 0x3F1A36E2D51EC34Bu, 0x3F50624DC5333A0Eu, 733 0x3F847AE136800892u, 0x3FB9999984200AB7u, 0x3FEFFFFFE5280D65u, 0x4023FFFFEF39085Fu, 0x4058FFFFEB074A77u, 734 0x408F3FFFE5C91D14u, 0x40C387FFEF9DB22Du, 0x40F869FFEB851EB8u, 0x412E847FE6666666u, 0x416312CFEFFFFFFFu, 735 0x3F1A36E2E8E94FFCu, 0x3F50624DD191D1FDu, 0x3F847AE145F6467Du, 0x3FB999999773D81Cu, 0x3FEFFFFFFD50CE23u, 736 0x4023FFFFFE5280D6u, 0x4058FFFFFDE7210Bu, 0x408F3FFFFD60E94Eu, 0x40C387FFFE5C91D1u, 0x40F869FFFDF3B645u, 737 0x412E847FFD70A3D7u, 0x416312CFFE666666u, 0x4197D783FDFFFFFFu, 0x3F1A36E2EAE3F7A7u, 0x3F50624DD2CE7AC8u, 738 0x3F847AE14782197Bu, 0x3FB9999999629FD9u, 0x3FEFFFFFFFBB47D0u, 0x4023FFFFFFD50CE2u, 0x4058FFFFFFCA501Au, 739 0x408F3FFFFFBCE421u, 0x40C387FFFFD60E94u, 0x40F869FFFFCB923Au, 0x412E847FFFBE76C8u, 0x416312CFFFD70A3Du, 740 0x4197D783FFCCCCCCu, 0x41CDCD64FFBFFFFFu, 0x3F1A36E2EB16A205u, 0x3F50624DD2EE2543u, 0x3F847AE147A9AE94u, 741 0x3FB9999999941A39u, 0x3FEFFFFFFFF920C8u, 0x4023FFFFFFFBB47Du, 0x4058FFFFFFFAA19Cu, 0x408F3FFFFFF94A03u, 742 0x40C387FFFFFBCE42u, 0x40F869FFFFFAC1D2u, 0x412E847FFFF97247u, 0x416312CFFFFBE76Cu, 0x4197D783FFFAE147u, 743 0x41CDCD64FFF99999u, 0x4202A05F1FFBFFFFu, 0x3F1A36E2EB1BB30Fu, 0x3F50624DD2F14FE9u, 0x3F847AE147ADA3E3u, 744 0x3FB9999999990CDCu, 0x3FEFFFFFFFFF5014u, 0x4023FFFFFFFF920Cu, 0x4058FFFFFFFF768Fu, 0x408F3FFFFFFF5433u, 745 0x40C387FFFFFF94A0u, 0x40F869FFFFFF79C8u, 0x412E847FFFFF583Au, 0x416312CFFFFF9724u, 0x4197D783FFFF7CEDu, 746 0x41CDCD64FFFF5C28u, 0x4202A05F1FFF9999u, 0x42374876E7FF7FFFu, 0x3F1A36E2EB1C34C3u, 0x3F50624DD2F1A0FAu, 747 0x3F847AE147AE0938u, 0x3FB9999999998B86u, 0x3FEFFFFFFFFFEE68u, 0x4023FFFFFFFFF501u, 0x4058FFFFFFFFF241u, 748 0x408F3FFFFFFFEED1u, 0x40C387FFFFFFF543u, 0x40F869FFFFFFF294u, 0x412E847FFFFFEF39u, 0x416312CFFFFFF583u, 749 0x4197D783FFFFF2E4u, 0x41CDCD64FFFFEF9Du, 0x4202A05F1FFFF5C2u, 0x42374876E7FFF333u, 0x426D1A94A1FFEFFFu, 750 0x3F1A36E2EB1C41BBu, 0x3F50624DD2F1A915u, 0x3F847AE147AE135Au, 0x3FB9999999999831u, 0x3FEFFFFFFFFFFE3Du, 751 0x4023FFFFFFFFFEE6u, 0x4058FFFFFFFFFEA0u, 0x408F3FFFFFFFFE48u, 0x40C387FFFFFFFEEDu, 0x40F869FFFFFFFEA8u, 752 0x412E847FFFFFFE52u, 0x416312CFFFFFFEF3u, 0x4197D783FFFFFEB0u, 0x41CDCD64FFFFFE5Cu, 0x4202A05F1FFFFEF9u, 753 0x42374876E7FFFEB8u, 0x426D1A94A1FFFE66u, 0x42A2309CE53FFEFFu, 0x3F1A36E2EB1C4307u, 0x3F50624DD2F1A9E4u, 754 0x3F847AE147AE145Eu, 0x3FB9999999999975u, 0x3FEFFFFFFFFFFFD2u, 0x4023FFFFFFFFFFE3u, 0x4058FFFFFFFFFFDCu, 755 0x408F3FFFFFFFFFD4u, 0x40C387FFFFFFFFE4u, 0x40F869FFFFFFFFDDu, 0x412E847FFFFFFFD5u, 0x416312CFFFFFFFE5u, 756 0x4197D783FFFFFFDEu, 0x41CDCD64FFFFFFD6u, 0x4202A05F1FFFFFE5u, 0x42374876E7FFFFDFu, 0x426D1A94A1FFFFD7u, 757 0x42A2309CE53FFFE6u, 0x42D6BCC41E8FFFDFu, 0x3F1A36E2EB1C4328u, 0x3F50624DD2F1A9F9u, 0x3F847AE147AE1477u, 758 0x3FB9999999999995u, 0x3FEFFFFFFFFFFFFBu, 0x4023FFFFFFFFFFFDu, 0x4058FFFFFFFFFFFCu, 0x408F3FFFFFFFFFFBu, 759 0x40C387FFFFFFFFFDu, 0x40F869FFFFFFFFFCu, 0x412E847FFFFFFFFBu, 0x416312CFFFFFFFFDu, 0x4197D783FFFFFFFCu, 760 0x41CDCD64FFFFFFFBu, 0x4202A05F1FFFFFFDu, 0x42374876E7FFFFFCu, 0x426D1A94A1FFFFFBu, 0x42A2309CE53FFFFDu, 761 0x42D6BCC41E8FFFFCu, 0x430C6BF52633FFFBu}; 762 763 static constexpr int _Max_P = 309; 764 765 static constexpr uint64_t _Ordinary_X_table[314] = {0x3F1A36E2EB1C432Cu, 0x3F50624DD2F1A9FBu, 0x3F847AE147AE147Au, 766 0x3FB9999999999999u, 0x3FEFFFFFFFFFFFFFu, 0x4023FFFFFFFFFFFFu, 0x4058FFFFFFFFFFFFu, 0x408F3FFFFFFFFFFFu, 767 0x40C387FFFFFFFFFFu, 0x40F869FFFFFFFFFFu, 0x412E847FFFFFFFFFu, 0x416312CFFFFFFFFFu, 0x4197D783FFFFFFFFu, 768 0x41CDCD64FFFFFFFFu, 0x4202A05F1FFFFFFFu, 0x42374876E7FFFFFFu, 0x426D1A94A1FFFFFFu, 0x42A2309CE53FFFFFu, 769 0x42D6BCC41E8FFFFFu, 0x430C6BF52633FFFFu, 0x4341C37937E07FFFu, 0x4376345785D89FFFu, 0x43ABC16D674EC7FFu, 770 0x43E158E460913CFFu, 0x4415AF1D78B58C3Fu, 0x444B1AE4D6E2EF4Fu, 0x4480F0CF064DD591u, 0x44B52D02C7E14AF6u, 771 0x44EA784379D99DB4u, 0x45208B2A2C280290u, 0x4554ADF4B7320334u, 0x4589D971E4FE8401u, 0x45C027E72F1F1281u, 772 0x45F431E0FAE6D721u, 0x46293E5939A08CE9u, 0x465F8DEF8808B024u, 0x4693B8B5B5056E16u, 0x46C8A6E32246C99Cu, 773 0x46FED09BEAD87C03u, 0x4733426172C74D82u, 0x476812F9CF7920E2u, 0x479E17B84357691Bu, 0x47D2CED32A16A1B1u, 774 0x48078287F49C4A1Du, 0x483D6329F1C35CA4u, 0x48725DFA371A19E6u, 0x48A6F578C4E0A060u, 0x48DCB2D6F618C878u, 775 0x4911EFC659CF7D4Bu, 0x49466BB7F0435C9Eu, 0x497C06A5EC5433C6u, 0x49B18427B3B4A05Bu, 0x49E5E531A0A1C872u, 776 0x4A1B5E7E08CA3A8Fu, 0x4A511B0EC57E6499u, 0x4A8561D276DDFDC0u, 0x4ABABA4714957D30u, 0x4AF0B46C6CDD6E3Eu, 777 0x4B24E1878814C9CDu, 0x4B5A19E96A19FC40u, 0x4B905031E2503DA8u, 0x4BC4643E5AE44D12u, 0x4BF97D4DF19D6057u, 778 0x4C2FDCA16E04B86Du, 0x4C63E9E4E4C2F344u, 0x4C98E45E1DF3B015u, 0x4CCF1D75A5709C1Au, 0x4D03726987666190u, 779 0x4D384F03E93FF9F4u, 0x4D6E62C4E38FF872u, 0x4DA2FDBB0E39FB47u, 0x4DD7BD29D1C87A19u, 0x4E0DAC74463A989Fu, 780 0x4E428BC8ABE49F63u, 0x4E772EBAD6DDC73Cu, 0x4EACFA698C95390Bu, 0x4EE21C81F7DD43A7u, 0x4F16A3A275D49491u, 781 0x4F4C4C8B1349B9B5u, 0x4F81AFD6EC0E1411u, 0x4FB61BCCA7119915u, 0x4FEBA2BFD0D5FF5Bu, 0x502145B7E285BF98u, 782 0x50559725DB272F7Fu, 0x508AFCEF51F0FB5Eu, 0x50C0DE1593369D1Bu, 0x50F5159AF8044462u, 0x512A5B01B605557Au, 783 0x516078E111C3556Cu, 0x5194971956342AC7u, 0x51C9BCDFABC13579u, 0x5200160BCB58C16Cu, 0x52341B8EBE2EF1C7u, 784 0x526922726DBAAE39u, 0x529F6B0F092959C7u, 0x52D3A2E965B9D81Cu, 0x53088BA3BF284E23u, 0x533EAE8CAEF261ACu, 785 0x53732D17ED577D0Bu, 0x53A7F85DE8AD5C4Eu, 0x53DDF67562D8B362u, 0x5412BA095DC7701Du, 0x5447688BB5394C25u, 786 0x547D42AEA2879F2Eu, 0x54B249AD2594C37Cu, 0x54E6DC186EF9F45Cu, 0x551C931E8AB87173u, 0x5551DBF316B346E7u, 787 0x558652EFDC6018A1u, 0x55BBE7ABD3781ECAu, 0x55F170CB642B133Eu, 0x5625CCFE3D35D80Eu, 0x565B403DCC834E11u, 788 0x569108269FD210CBu, 0x56C54A3047C694FDu, 0x56FA9CBC59B83A3Du, 0x5730A1F5B8132466u, 0x5764CA732617ED7Fu, 789 0x5799FD0FEF9DE8DFu, 0x57D03E29F5C2B18Bu, 0x58044DB473335DEEu, 0x583961219000356Au, 0x586FB969F40042C5u, 790 0x58A3D3E2388029BBu, 0x58D8C8DAC6A0342Au, 0x590EFB1178484134u, 0x59435CEAEB2D28C0u, 0x59783425A5F872F1u, 791 0x59AE412F0F768FADu, 0x59E2E8BD69AA19CCu, 0x5A17A2ECC414A03Fu, 0x5A4D8BA7F519C84Fu, 0x5A827748F9301D31u, 792 0x5AB7151B377C247Eu, 0x5AECDA62055B2D9Du, 0x5B22087D4358FC82u, 0x5B568A9C942F3BA3u, 0x5B8C2D43B93B0A8Bu, 793 0x5BC19C4A53C4E697u, 0x5BF6035CE8B6203Du, 0x5C2B843422E3A84Cu, 0x5C6132A095CE492Fu, 0x5C957F48BB41DB7Bu, 794 0x5CCADF1AEA12525Au, 0x5D00CB70D24B7378u, 0x5D34FE4D06DE5056u, 0x5D6A3DE04895E46Cu, 0x5DA066AC2D5DAEC3u, 795 0x5DD4805738B51A74u, 0x5E09A06D06E26112u, 0x5E400444244D7CABu, 0x5E7405552D60DBD6u, 0x5EA906AA78B912CBu, 796 0x5EDF485516E7577Eu, 0x5F138D352E5096AFu, 0x5F48708279E4BC5Au, 0x5F7E8CA3185DEB71u, 0x5FB317E5EF3AB327u, 797 0x5FE7DDDF6B095FF0u, 0x601DD55745CBB7ECu, 0x6052A5568B9F52F4u, 0x60874EAC2E8727B1u, 0x60BD22573A28F19Du, 798 0x60F2357684599702u, 0x6126C2D4256FFCC2u, 0x615C73892ECBFBF3u, 0x6191C835BD3F7D78u, 0x61C63A432C8F5CD6u, 799 0x61FBC8D3F7B3340Bu, 0x62315D847AD00087u, 0x6265B4E5998400A9u, 0x629B221EFFE500D3u, 0x62D0F5535FEF2084u, 800 0x630532A837EAE8A5u, 0x633A7F5245E5A2CEu, 0x63708F936BAF85C1u, 0x63A4B378469B6731u, 0x63D9E056584240FDu, 801 0x64102C35F729689Eu, 0x6444374374F3C2C6u, 0x647945145230B377u, 0x64AF965966BCE055u, 0x64E3BDF7E0360C35u, 802 0x6518AD75D8438F43u, 0x654ED8D34E547313u, 0x6583478410F4C7ECu, 0x65B819651531F9E7u, 0x65EE1FBE5A7E7861u, 803 0x6622D3D6F88F0B3Cu, 0x665788CCB6B2CE0Cu, 0x668D6AFFE45F818Fu, 0x66C262DFEEBBB0F9u, 0x66F6FB97EA6A9D37u, 804 0x672CBA7DE5054485u, 0x6761F48EAF234AD3u, 0x679671B25AEC1D88u, 0x67CC0E1EF1A724EAu, 0x680188D357087712u, 805 0x6835EB082CCA94D7u, 0x686B65CA37FD3A0Du, 0x68A11F9E62FE4448u, 0x68D56785FBBDD55Au, 0x690AC1677AAD4AB0u, 806 0x6940B8E0ACAC4EAEu, 0x6974E718D7D7625Au, 0x69AA20DF0DCD3AF0u, 0x69E0548B68A044D6u, 0x6A1469AE42C8560Cu, 807 0x6A498419D37A6B8Fu, 0x6A7FE52048590672u, 0x6AB3EF342D37A407u, 0x6AE8EB0138858D09u, 0x6B1F25C186A6F04Cu, 808 0x6B537798F428562Fu, 0x6B88557F31326BBBu, 0x6BBE6ADEFD7F06AAu, 0x6BF302CB5E6F642Au, 0x6C27C37E360B3D35u, 809 0x6C5DB45DC38E0C82u, 0x6C9290BA9A38C7D1u, 0x6CC734E940C6F9C5u, 0x6CFD022390F8B837u, 0x6D3221563A9B7322u, 810 0x6D66A9ABC9424FEBu, 0x6D9C5416BB92E3E6u, 0x6DD1B48E353BCE6Fu, 0x6E0621B1C28AC20Bu, 0x6E3BAA1E332D728Eu, 811 0x6E714A52DFFC6799u, 0x6EA59CE797FB817Fu, 0x6EDB04217DFA61DFu, 0x6F10E294EEBC7D2Bu, 0x6F451B3A2A6B9C76u, 812 0x6F7A6208B5068394u, 0x6FB07D457124123Cu, 0x6FE49C96CD6D16CBu, 0x7019C3BC80C85C7Eu, 0x70501A55D07D39CFu, 813 0x708420EB449C8842u, 0x70B9292615C3AA53u, 0x70EF736F9B3494E8u, 0x7123A825C100DD11u, 0x7158922F31411455u, 814 0x718EB6BAFD91596Bu, 0x71C33234DE7AD7E2u, 0x71F7FEC216198DDBu, 0x722DFE729B9FF152u, 0x7262BF07A143F6D3u, 815 0x72976EC98994F488u, 0x72CD4A7BEBFA31AAu, 0x73024E8D737C5F0Au, 0x7336E230D05B76CDu, 0x736C9ABD04725480u, 816 0x73A1E0B622C774D0u, 0x73D658E3AB795204u, 0x740BEF1C9657A685u, 0x74417571DDF6C813u, 0x7475D2CE55747A18u, 817 0x74AB4781EAD1989Eu, 0x74E10CB132C2FF63u, 0x75154FDD7F73BF3Bu, 0x754AA3D4DF50AF0Au, 0x7580A6650B926D66u, 818 0x75B4CFFE4E7708C0u, 0x75EA03FDE214CAF0u, 0x7620427EAD4CFED6u, 0x7654531E58A03E8Bu, 0x768967E5EEC84E2Eu, 819 0x76BFC1DF6A7A61BAu, 0x76F3D92BA28C7D14u, 0x7728CF768B2F9C59u, 0x775F03542DFB8370u, 0x779362149CBD3226u, 820 0x77C83A99C3EC7EAFu, 0x77FE494034E79E5Bu, 0x7832EDC82110C2F9u, 0x7867A93A2954F3B7u, 0x789D9388B3AA30A5u, 821 0x78D27C35704A5E67u, 0x79071B42CC5CF601u, 0x793CE2137F743381u, 0x79720D4C2FA8A030u, 0x79A6909F3B92C83Du, 822 0x79DC34C70A777A4Cu, 0x7A11A0FC668AAC6Fu, 0x7A46093B802D578Bu, 0x7A7B8B8A6038AD6Eu, 0x7AB137367C236C65u, 823 0x7AE585041B2C477Eu, 0x7B1AE64521F7595Eu, 0x7B50CFEB353A97DAu, 0x7B8503E602893DD1u, 0x7BBA44DF832B8D45u, 824 0x7BF06B0BB1FB384Bu, 0x7C2485CE9E7A065Eu, 0x7C59A742461887F6u, 0x7C9008896BCF54F9u, 0x7CC40AABC6C32A38u, 825 0x7CF90D56B873F4C6u, 0x7D2F50AC6690F1F8u, 0x7D63926BC01A973Bu, 0x7D987706B0213D09u, 0x7DCE94C85C298C4Cu, 826 0x7E031CFD3999F7AFu, 0x7E37E43C8800759Bu, 0x7E6DDD4BAA009302u, 0x7EA2AA4F4A405BE1u, 0x7ED754E31CD072D9u, 827 0x7F0D2A1BE4048F90u, 0x7F423A516E82D9BAu, 0x7F76C8E5CA239028u, 0x7FAC7B1F3CAC7433u, 0x7FE1CCF385EBC89Fu, 828 0x7FEFFFFFFFFFFFFFu}; 829 }; 830 831 template <class _Floating> 832 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 833 to_chars_result _Floating_to_chars_general_precision( 834 char* _First, char* const _Last, const _Floating _Value, int _Precision) noexcept { 835 836 using _Traits = _Floating_type_traits<_Floating>; 837 using _Uint_type = typename _Traits::_Uint_type; 838 839 const _Uint_type _Uint_value = _VSTD::bit_cast<_Uint_type>(_Value); 840 841 if (_Uint_value == 0) { // zero detected; write "0" and return; _Precision is irrelevant due to zero-trimming 842 if (_First == _Last) { 843 return {_Last, errc::value_too_large}; 844 } 845 846 *_First++ = '0'; 847 848 return {_First, errc{}}; 849 } 850 851 // C11 7.21.6.1 "The fprintf function"/5: 852 // "A negative precision argument is taken as if the precision were omitted." 853 // /8: "g,G [...] Let P equal the precision if nonzero, 6 if the precision is omitted, 854 // or 1 if the precision is zero." 855 856 // Performance note: It's possible to rewrite this for branchless codegen, 857 // but profiling will be necessary to determine whether that's faster. 858 if (_Precision < 0) { 859 _Precision = 6; 860 } else if (_Precision == 0) { 861 _Precision = 1; 862 } else if (_Precision < 1'000'000) { 863 // _Precision is ok. 864 } else { 865 // Avoid integer overflow. 866 // Due to general notation's zero-trimming behavior, we can simply clamp _Precision. 867 // This is further clamped below. 868 _Precision = 1'000'000; 869 } 870 871 // _Precision is now the Standard's P. 872 873 // /8: "Then, if a conversion with style E would have an exponent of X: 874 // - if P > X >= -4, the conversion is with style f (or F) and precision P - (X + 1). 875 // - otherwise, the conversion is with style e (or E) and precision P - 1." 876 877 // /8: "Finally, [...] any trailing zeros are removed from the fractional portion of the result 878 // and the decimal-point character is removed if there is no fractional portion remaining." 879 880 using _Tables = _General_precision_tables<_Floating>; 881 882 const _Uint_type* _Table_begin; 883 const _Uint_type* _Table_end; 884 885 if (_Precision <= _Tables::_Max_special_P) { 886 _Table_begin = _Tables::_Special_X_table + (_Precision - 1) * (_Precision + 10) / 2; 887 _Table_end = _Table_begin + _Precision + 5; 888 } else { 889 _Table_begin = _Tables::_Ordinary_X_table; 890 _Table_end = _Table_begin + _VSTD::min(_Precision, _Tables::_Max_P) + 5; 891 } 892 893 // Profiling indicates that linear search is faster than binary search for small tables. 894 // Performance note: lambda captures may have a small performance cost. 895 const _Uint_type* const _Table_lower_bound = [=] { 896 if constexpr (!_IsSame<_Floating, float>::value) { 897 if (_Precision > 155) { // threshold determined via profiling 898 return _VSTD::lower_bound(_Table_begin, _Table_end, _Uint_value, less{}); 899 } 900 } 901 902 return _VSTD::find_if(_Table_begin, _Table_end, [=](const _Uint_type _Elem) { return _Uint_value <= _Elem; }); 903 }(); 904 905 const ptrdiff_t _Table_index = _Table_lower_bound - _Table_begin; 906 const int _Scientific_exponent_X = static_cast<int>(_Table_index - 5); 907 const bool _Use_fixed_notation = _Precision > _Scientific_exponent_X && _Scientific_exponent_X >= -4; 908 909 // Performance note: it might (or might not) be faster to modify Ryu Printf to perform zero-trimming. 910 // Such modifications would involve a fairly complicated state machine (notably, both '0' and '9' digits would 911 // need to be buffered, due to rounding), and that would have performance costs due to increased branching. 912 // Here, we're using a simpler approach: writing into a local buffer, manually zero-trimming, and then copying into 913 // the output range. The necessary buffer size is reasonably small, the zero-trimming logic is simple and fast, 914 // and the final copying is also fast. 915 916 constexpr int _Max_output_length = 917 _IsSame<_Floating, float>::value ? 117 : 773; // cases: 0x1.fffffep-126f and 0x1.fffffffffffffp-1022 918 constexpr int _Max_fixed_precision = 919 _IsSame<_Floating, float>::value ? 37 : 66; // cases: 0x1.fffffep-14f and 0x1.fffffffffffffp-14 920 constexpr int _Max_scientific_precision = 921 _IsSame<_Floating, float>::value ? 111 : 766; // cases: 0x1.fffffep-126f and 0x1.fffffffffffffp-1022 922 923 // Note that _Max_output_length is determined by scientific notation and is more than enough for fixed notation. 924 // 0x1.fffffep+127f is 39 digits, plus 1 for '.', plus _Max_fixed_precision for '0' digits, equals 77. 925 // 0x1.fffffffffffffp+1023 is 309 digits, plus 1 for '.', plus _Max_fixed_precision for '0' digits, equals 376. 926 927 char _Buffer[_Max_output_length]; 928 const char* const _Significand_first = _Buffer; // e.g. "1.234" 929 const char* _Significand_last = nullptr; 930 const char* _Exponent_first = nullptr; // e.g. "e-05" 931 const char* _Exponent_last = nullptr; 932 int _Effective_precision; // number of digits printed after the decimal point, before trimming 933 934 // Write into the local buffer. 935 // Clamping _Effective_precision allows _Buffer to be as small as possible, and increases efficiency. 936 if (_Use_fixed_notation) { 937 _Effective_precision = _VSTD::min(_Precision - (_Scientific_exponent_X + 1), _Max_fixed_precision); 938 const to_chars_result _Buf_result = 939 _Floating_to_chars_fixed_precision(_Buffer, _VSTD::end(_Buffer), _Value, _Effective_precision); 940 _LIBCPP_ASSERT(_Buf_result.ec == errc{}, ""); 941 _Significand_last = _Buf_result.ptr; 942 } else { 943 _Effective_precision = _VSTD::min(_Precision - 1, _Max_scientific_precision); 944 const to_chars_result _Buf_result = 945 _Floating_to_chars_scientific_precision(_Buffer, _VSTD::end(_Buffer), _Value, _Effective_precision); 946 _LIBCPP_ASSERT(_Buf_result.ec == errc{}, ""); 947 _Significand_last = _VSTD::find(_Buffer, _Buf_result.ptr, 'e'); 948 _Exponent_first = _Significand_last; 949 _Exponent_last = _Buf_result.ptr; 950 } 951 952 // If we printed a decimal point followed by digits, perform zero-trimming. 953 if (_Effective_precision > 0) { 954 while (_Significand_last[-1] == '0') { // will stop at '.' or a nonzero digit 955 --_Significand_last; 956 } 957 958 if (_Significand_last[-1] == '.') { 959 --_Significand_last; 960 } 961 } 962 963 // Copy the significand to the output range. 964 const ptrdiff_t _Significand_distance = _Significand_last - _Significand_first; 965 if (_Last - _First < _Significand_distance) { 966 return {_Last, errc::value_too_large}; 967 } 968 _VSTD::memcpy(_First, _Significand_first, static_cast<size_t>(_Significand_distance)); 969 _First += _Significand_distance; 970 971 // Copy the exponent to the output range. 972 if (!_Use_fixed_notation) { 973 const ptrdiff_t _Exponent_distance = _Exponent_last - _Exponent_first; 974 if (_Last - _First < _Exponent_distance) { 975 return {_Last, errc::value_too_large}; 976 } 977 _VSTD::memcpy(_First, _Exponent_first, static_cast<size_t>(_Exponent_distance)); 978 _First += _Exponent_distance; 979 } 980 981 return {_First, errc{}}; 982 } 983 984 enum class _Floating_to_chars_overload { _Plain, _Format_only, _Format_precision }; 985 986 template <_Floating_to_chars_overload _Overload, class _Floating> 987 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 988 to_chars_result _Floating_to_chars( 989 char* _First, char* const _Last, _Floating _Value, const chars_format _Fmt, const int _Precision) noexcept { 990 991 if constexpr (_Overload == _Floating_to_chars_overload::_Plain) { 992 _LIBCPP_ASSERT(_Fmt == chars_format{}, ""); // plain overload must pass chars_format{} internally 993 } else { 994 _LIBCPP_ASSERT(_Fmt == chars_format::general || _Fmt == chars_format::scientific || _Fmt == chars_format::fixed 995 || _Fmt == chars_format::hex, 996 "invalid format in to_chars()"); 997 } 998 999 using _Traits = _Floating_type_traits<_Floating>; 1000 using _Uint_type = typename _Traits::_Uint_type; 1001 1002 _Uint_type _Uint_value = _VSTD::bit_cast<_Uint_type>(_Value); 1003 1004 const bool _Was_negative = (_Uint_value & _Traits::_Shifted_sign_mask) != 0; 1005 1006 if (_Was_negative) { // sign bit detected; write minus sign and clear sign bit 1007 if (_First == _Last) { 1008 return {_Last, errc::value_too_large}; 1009 } 1010 1011 *_First++ = '-'; 1012 1013 _Uint_value &= ~_Traits::_Shifted_sign_mask; 1014 _Value = _VSTD::bit_cast<_Floating>(_Uint_value); 1015 } 1016 1017 if ((_Uint_value & _Traits::_Shifted_exponent_mask) == _Traits::_Shifted_exponent_mask) { 1018 // inf/nan detected; write appropriate string and return 1019 const char* _Str; 1020 size_t _Len; 1021 1022 const _Uint_type _Mantissa = _Uint_value & _Traits::_Denormal_mantissa_mask; 1023 1024 if (_Mantissa == 0) { 1025 _Str = "inf"; 1026 _Len = 3; 1027 } else if (_Was_negative && _Mantissa == _Traits::_Special_nan_mantissa_mask) { 1028 // When a NaN value has the sign bit set, the quiet bit set, and all other mantissa bits cleared, 1029 // the UCRT interprets it to mean "indeterminate", and indicates this by printing "-nan(ind)". 1030 _Str = "nan(ind)"; 1031 _Len = 8; 1032 } else if ((_Mantissa & _Traits::_Special_nan_mantissa_mask) != 0) { 1033 _Str = "nan"; 1034 _Len = 3; 1035 } else { 1036 _Str = "nan(snan)"; 1037 _Len = 9; 1038 } 1039 1040 if (_Last - _First < static_cast<ptrdiff_t>(_Len)) { 1041 return {_Last, errc::value_too_large}; 1042 } 1043 1044 _VSTD::memcpy(_First, _Str, _Len); 1045 1046 return {_First + _Len, errc{}}; 1047 } 1048 1049 if constexpr (_Overload == _Floating_to_chars_overload::_Plain) { 1050 return _Floating_to_chars_ryu(_First, _Last, _Value, chars_format{}); 1051 } else if constexpr (_Overload == _Floating_to_chars_overload::_Format_only) { 1052 if (_Fmt == chars_format::hex) { 1053 return _Floating_to_chars_hex_shortest(_First, _Last, _Value); 1054 } 1055 1056 return _Floating_to_chars_ryu(_First, _Last, _Value, _Fmt); 1057 } else if constexpr (_Overload == _Floating_to_chars_overload::_Format_precision) { 1058 switch (_Fmt) { 1059 case chars_format::scientific: 1060 return _Floating_to_chars_scientific_precision(_First, _Last, _Value, _Precision); 1061 case chars_format::fixed: 1062 return _Floating_to_chars_fixed_precision(_First, _Last, _Value, _Precision); 1063 case chars_format::general: 1064 return _Floating_to_chars_general_precision(_First, _Last, _Value, _Precision); 1065 case chars_format::hex: 1066 default: // avoid MSVC warning C4715: not all control paths return a value 1067 return _Floating_to_chars_hex_precision(_First, _Last, _Value, _Precision); 1068 } 1069 } 1070 } 1071 1072 // clang-format on 1073 1074 _LIBCPP_END_NAMESPACE_STD 1075 1076 #endif // _LIBCPP_SRC_INCLUDE_TO_CHARS_FLOATING_POINT_H 1077