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