785 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// Copyright (c) Microsoft Corporation.10// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception11 12// Copyright 2018 Ulf Adams13// Copyright (c) Microsoft Corporation. All rights reserved.14 15// Boost Software License - Version 1.0 - August 17th, 200316 17// Permission is hereby granted, free of charge, to any person or organization18// obtaining a copy of the software and accompanying documentation covered by19// this license (the "Software") to use, reproduce, display, distribute,20// execute, and transmit the Software, and to prepare derivative works of the21// Software, and to permit third-parties to whom the Software is furnished to22// do so, all subject to the following:23 24// The copyright notices in the Software and this entire statement, including25// the above license grant, this restriction and the following disclaimer,26// must be included in all copies of the Software, in whole or in part, and27// all derivative works of the Software, unless such copies or derivative28// works are solely in the form of machine-executable object code generated by29// a source language processor.30 31// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR32// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,33// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT34// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE35// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,36// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER37// DEALINGS IN THE SOFTWARE.38 39// Avoid formatting to keep the changes with the original code minimal.40// clang-format off41 42#include <__assert>43#include <__config>44#include <charconv>45#include <cstddef>46 47#include "include/ryu/common.h"48#include "include/ryu/d2fixed.h"49#include "include/ryu/d2s.h"50#include "include/ryu/d2s_full_table.h"51#include "include/ryu/d2s_intrinsics.h"52#include "include/ryu/digit_table.h"53#include "include/ryu/ryu.h"54 55_LIBCPP_BEGIN_NAMESPACE_STD56 57// We need a 64x128-bit multiplication and a subsequent 128-bit shift.58// Multiplication:59// The 64-bit factor is variable and passed in, the 128-bit factor comes60// from a lookup table. We know that the 64-bit factor only has 5561// significant bits (i.e., the 9 topmost bits are zeros). The 128-bit62// factor only has 124 significant bits (i.e., the 4 topmost bits are63// zeros).64// Shift:65// In principle, the multiplication result requires 55 + 124 = 179 bits to66// represent. However, we then shift this value to the right by __j, which is67// at least __j >= 115, so the result is guaranteed to fit into 179 - 115 = 6468// bits. This means that we only need the topmost 64 significant bits of69// the 64x128-bit multiplication.70//71// There are several ways to do this:72// 1. Best case: the compiler exposes a 128-bit type.73// We perform two 64x64-bit multiplications, add the higher 64 bits of the74// lower result to the higher result, and shift by __j - 64 bits.75//76// We explicitly cast from 64-bit to 128-bit, so the compiler can tell77// that these are only 64-bit inputs, and can map these to the best78// possible sequence of assembly instructions.79// x64 machines happen to have matching assembly instructions for80// 64x64-bit multiplications and 128-bit shifts.81//82// 2. Second best case: the compiler exposes intrinsics for the x64 assembly83// instructions mentioned in 1.84//85// 3. We only have 64x64 bit instructions that return the lower 64 bits of86// the result, i.e., we have to use plain C.87// Our inputs are less than the full width, so we have three options:88// a. Ignore this fact and just implement the intrinsics manually.89// b. Split both into 31-bit pieces, which guarantees no internal overflow,90// but requires extra work upfront (unless we change the lookup table).91// c. Split only the first factor into 31-bit pieces, which also guarantees92// no internal overflow, but requires extra work since the intermediate93// results are not perfectly aligned.94#ifdef _LIBCPP_INTRINSIC12895 96[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint64_t __mulShift(const uint64_t __m, const uint64_t* const __mul, const int32_t __j) {97 // __m is maximum 55 bits98 uint64_t __high1; // 12899 const uint64_t __low1 = __ryu_umul128(__m, __mul[1], &__high1); // 64100 uint64_t __high0; // 64101 (void) __ryu_umul128(__m, __mul[0], &__high0); // 0102 const uint64_t __sum = __high0 + __low1;103 if (__sum < __high0) {104 ++__high1; // overflow into __high1105 }106 return __ryu_shiftright128(__sum, __high1, static_cast<uint32_t>(__j - 64));107}108 109[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint64_t __mulShiftAll(const uint64_t __m, const uint64_t* const __mul, const int32_t __j,110 uint64_t* const __vp, uint64_t* const __vm, const uint32_t __mmShift) {111 *__vp = __mulShift(4 * __m + 2, __mul, __j);112 *__vm = __mulShift(4 * __m - 1 - __mmShift, __mul, __j);113 return __mulShift(4 * __m, __mul, __j);114}115 116#else // ^^^ intrinsics available ^^^ / vvv intrinsics unavailable vvv117 118[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_ALWAYS_INLINE uint64_t __mulShiftAll(uint64_t __m, const uint64_t* const __mul, const int32_t __j,119 uint64_t* const __vp, uint64_t* const __vm, const uint32_t __mmShift) { // TRANSITION, VSO-634761120 __m <<= 1;121 // __m is maximum 55 bits122 uint64_t __tmp;123 const uint64_t __lo = __ryu_umul128(__m, __mul[0], &__tmp);124 uint64_t __hi;125 const uint64_t __mid = __tmp + __ryu_umul128(__m, __mul[1], &__hi);126 __hi += __mid < __tmp; // overflow into __hi127 128 const uint64_t __lo2 = __lo + __mul[0];129 const uint64_t __mid2 = __mid + __mul[1] + (__lo2 < __lo);130 const uint64_t __hi2 = __hi + (__mid2 < __mid);131 *__vp = __ryu_shiftright128(__mid2, __hi2, static_cast<uint32_t>(__j - 64 - 1));132 133 if (__mmShift == 1) {134 const uint64_t __lo3 = __lo - __mul[0];135 const uint64_t __mid3 = __mid - __mul[1] - (__lo3 > __lo);136 const uint64_t __hi3 = __hi - (__mid3 > __mid);137 *__vm = __ryu_shiftright128(__mid3, __hi3, static_cast<uint32_t>(__j - 64 - 1));138 } else {139 const uint64_t __lo3 = __lo + __lo;140 const uint64_t __mid3 = __mid + __mid + (__lo3 < __lo);141 const uint64_t __hi3 = __hi + __hi + (__mid3 < __mid);142 const uint64_t __lo4 = __lo3 - __mul[0];143 const uint64_t __mid4 = __mid3 - __mul[1] - (__lo4 > __lo3);144 const uint64_t __hi4 = __hi3 - (__mid4 > __mid3);145 *__vm = __ryu_shiftright128(__mid4, __hi4, static_cast<uint32_t>(__j - 64));146 }147 148 return __ryu_shiftright128(__mid, __hi, static_cast<uint32_t>(__j - 64 - 1));149}150 151#endif // ^^^ intrinsics unavailable ^^^152 153[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __decimalLength17(const uint64_t __v) {154 // This is slightly faster than a loop.155 // The average output length is 16.38 digits, so we check high-to-low.156 // Function precondition: __v is not an 18, 19, or 20-digit number.157 // (17 digits are sufficient for round-tripping.)158 _LIBCPP_ASSERT_INTERNAL(__v < 100000000000000000u, "");159 if (__v >= 10000000000000000u) { return 17; }160 if (__v >= 1000000000000000u) { return 16; }161 if (__v >= 100000000000000u) { return 15; }162 if (__v >= 10000000000000u) { return 14; }163 if (__v >= 1000000000000u) { return 13; }164 if (__v >= 100000000000u) { return 12; }165 if (__v >= 10000000000u) { return 11; }166 if (__v >= 1000000000u) { return 10; }167 if (__v >= 100000000u) { return 9; }168 if (__v >= 10000000u) { return 8; }169 if (__v >= 1000000u) { return 7; }170 if (__v >= 100000u) { return 6; }171 if (__v >= 10000u) { return 5; }172 if (__v >= 1000u) { return 4; }173 if (__v >= 100u) { return 3; }174 if (__v >= 10u) { return 2; }175 return 1;176}177 178// A floating decimal representing m * 10^e.179struct __floating_decimal_64 {180 uint64_t __mantissa;181 int32_t __exponent;182};183 184[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline __floating_decimal_64 __d2d(const uint64_t __ieeeMantissa, const uint32_t __ieeeExponent) {185 int32_t __e2;186 uint64_t __m2;187 if (__ieeeExponent == 0) {188 // We subtract 2 so that the bounds computation has 2 additional bits.189 __e2 = 1 - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS - 2;190 __m2 = __ieeeMantissa;191 } else {192 __e2 = static_cast<int32_t>(__ieeeExponent) - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS - 2;193 __m2 = (1ull << __DOUBLE_MANTISSA_BITS) | __ieeeMantissa;194 }195 const bool __even = (__m2 & 1) == 0;196 const bool __acceptBounds = __even;197 198 // Step 2: Determine the interval of valid decimal representations.199 const uint64_t __mv = 4 * __m2;200 // Implicit bool -> int conversion. True is 1, false is 0.201 const uint32_t __mmShift = __ieeeMantissa != 0 || __ieeeExponent <= 1;202 // We would compute __mp and __mm like this:203 // uint64_t __mp = 4 * __m2 + 2;204 // uint64_t __mm = __mv - 1 - __mmShift;205 206 // Step 3: Convert to a decimal power base using 128-bit arithmetic.207 uint64_t __vr, __vp, __vm;208 int32_t __e10;209 bool __vmIsTrailingZeros = false;210 bool __vrIsTrailingZeros = false;211 if (__e2 >= 0) {212 // I tried special-casing __q == 0, but there was no effect on performance.213 // This expression is slightly faster than max(0, __log10Pow2(__e2) - 1).214 const uint32_t __q = __log10Pow2(__e2) - (__e2 > 3);215 __e10 = static_cast<int32_t>(__q);216 const int32_t __k = __DOUBLE_POW5_INV_BITCOUNT + __pow5bits(static_cast<int32_t>(__q)) - 1;217 const int32_t __i = -__e2 + static_cast<int32_t>(__q) + __k;218 __vr = __mulShiftAll(__m2, __DOUBLE_POW5_INV_SPLIT[__q], __i, &__vp, &__vm, __mmShift);219 if (__q <= 21) {220 // This should use __q <= 22, but I think 21 is also safe. Smaller values221 // may still be safe, but it's more difficult to reason about them.222 // Only one of __mp, __mv, and __mm can be a multiple of 5, if any.223 const uint32_t __mvMod5 = static_cast<uint32_t>(__mv) - 5 * static_cast<uint32_t>(__div5(__mv));224 if (__mvMod5 == 0) {225 __vrIsTrailingZeros = __multipleOfPowerOf5(__mv, __q);226 } else if (__acceptBounds) {227 // Same as min(__e2 + (~__mm & 1), __pow5Factor(__mm)) >= __q228 // <=> __e2 + (~__mm & 1) >= __q && __pow5Factor(__mm) >= __q229 // <=> true && __pow5Factor(__mm) >= __q, since __e2 >= __q.230 __vmIsTrailingZeros = __multipleOfPowerOf5(__mv - 1 - __mmShift, __q);231 } else {232 // Same as min(__e2 + 1, __pow5Factor(__mp)) >= __q.233 __vp -= __multipleOfPowerOf5(__mv + 2, __q);234 }235 }236 } else {237 // This expression is slightly faster than max(0, __log10Pow5(-__e2) - 1).238 const uint32_t __q = __log10Pow5(-__e2) - (-__e2 > 1);239 __e10 = static_cast<int32_t>(__q) + __e2;240 const int32_t __i = -__e2 - static_cast<int32_t>(__q);241 const int32_t __k = __pow5bits(__i) - __DOUBLE_POW5_BITCOUNT;242 const int32_t __j = static_cast<int32_t>(__q) - __k;243 __vr = __mulShiftAll(__m2, __DOUBLE_POW5_SPLIT[__i], __j, &__vp, &__vm, __mmShift);244 if (__q <= 1) {245 // {__vr,__vp,__vm} is trailing zeros if {__mv,__mp,__mm} has at least __q trailing 0 bits.246 // __mv = 4 * __m2, so it always has at least two trailing 0 bits.247 __vrIsTrailingZeros = true;248 if (__acceptBounds) {249 // __mm = __mv - 1 - __mmShift, so it has 1 trailing 0 bit iff __mmShift == 1.250 __vmIsTrailingZeros = __mmShift == 1;251 } else {252 // __mp = __mv + 2, so it always has at least one trailing 0 bit.253 --__vp;254 }255 } else if (__q < 63) { // TRANSITION(ulfjack): Use a tighter bound here.256 // We need to compute min(ntz(__mv), __pow5Factor(__mv) - __e2) >= __q - 1257 // <=> ntz(__mv) >= __q - 1 && __pow5Factor(__mv) - __e2 >= __q - 1258 // <=> ntz(__mv) >= __q - 1 (__e2 is negative and -__e2 >= __q)259 // <=> (__mv & ((1 << (__q - 1)) - 1)) == 0260 // We also need to make sure that the left shift does not overflow.261 __vrIsTrailingZeros = __multipleOfPowerOf2(__mv, __q - 1);262 }263 }264 265 // Step 4: Find the shortest decimal representation in the interval of valid representations.266 int32_t __removed = 0;267 uint8_t __lastRemovedDigit = 0;268 uint64_t _Output;269 // On average, we remove ~2 digits.270 if (__vmIsTrailingZeros || __vrIsTrailingZeros) {271 // General case, which happens rarely (~0.7%).272 for (;;) {273 const uint64_t __vpDiv10 = __div10(__vp);274 const uint64_t __vmDiv10 = __div10(__vm);275 if (__vpDiv10 <= __vmDiv10) {276 break;277 }278 const uint32_t __vmMod10 = static_cast<uint32_t>(__vm) - 10 * static_cast<uint32_t>(__vmDiv10);279 const uint64_t __vrDiv10 = __div10(__vr);280 const uint32_t __vrMod10 = static_cast<uint32_t>(__vr) - 10 * static_cast<uint32_t>(__vrDiv10);281 __vmIsTrailingZeros &= __vmMod10 == 0;282 __vrIsTrailingZeros &= __lastRemovedDigit == 0;283 __lastRemovedDigit = static_cast<uint8_t>(__vrMod10);284 __vr = __vrDiv10;285 __vp = __vpDiv10;286 __vm = __vmDiv10;287 ++__removed;288 }289 if (__vmIsTrailingZeros) {290 for (;;) {291 const uint64_t __vmDiv10 = __div10(__vm);292 const uint32_t __vmMod10 = static_cast<uint32_t>(__vm) - 10 * static_cast<uint32_t>(__vmDiv10);293 if (__vmMod10 != 0) {294 break;295 }296 const uint64_t __vpDiv10 = __div10(__vp);297 const uint64_t __vrDiv10 = __div10(__vr);298 const uint32_t __vrMod10 = static_cast<uint32_t>(__vr) - 10 * static_cast<uint32_t>(__vrDiv10);299 __vrIsTrailingZeros &= __lastRemovedDigit == 0;300 __lastRemovedDigit = static_cast<uint8_t>(__vrMod10);301 __vr = __vrDiv10;302 __vp = __vpDiv10;303 __vm = __vmDiv10;304 ++__removed;305 }306 }307 if (__vrIsTrailingZeros && __lastRemovedDigit == 5 && __vr % 2 == 0) {308 // Round even if the exact number is .....50..0.309 __lastRemovedDigit = 4;310 }311 // We need to take __vr + 1 if __vr is outside bounds or we need to round up.312 _Output = __vr + ((__vr == __vm && (!__acceptBounds || !__vmIsTrailingZeros)) || __lastRemovedDigit >= 5);313 } else {314 // Specialized for the common case (~99.3%). Percentages below are relative to this.315 bool __roundUp = false;316 const uint64_t __vpDiv100 = __div100(__vp);317 const uint64_t __vmDiv100 = __div100(__vm);318 if (__vpDiv100 > __vmDiv100) { // Optimization: remove two digits at a time (~86.2%).319 const uint64_t __vrDiv100 = __div100(__vr);320 const uint32_t __vrMod100 = static_cast<uint32_t>(__vr) - 100 * static_cast<uint32_t>(__vrDiv100);321 __roundUp = __vrMod100 >= 50;322 __vr = __vrDiv100;323 __vp = __vpDiv100;324 __vm = __vmDiv100;325 __removed += 2;326 }327 // Loop iterations below (approximately), without optimization above:328 // 0: 0.03%, 1: 13.8%, 2: 70.6%, 3: 14.0%, 4: 1.40%, 5: 0.14%, 6+: 0.02%329 // Loop iterations below (approximately), with optimization above:330 // 0: 70.6%, 1: 27.8%, 2: 1.40%, 3: 0.14%, 4+: 0.02%331 for (;;) {332 const uint64_t __vpDiv10 = __div10(__vp);333 const uint64_t __vmDiv10 = __div10(__vm);334 if (__vpDiv10 <= __vmDiv10) {335 break;336 }337 const uint64_t __vrDiv10 = __div10(__vr);338 const uint32_t __vrMod10 = static_cast<uint32_t>(__vr) - 10 * static_cast<uint32_t>(__vrDiv10);339 __roundUp = __vrMod10 >= 5;340 __vr = __vrDiv10;341 __vp = __vpDiv10;342 __vm = __vmDiv10;343 ++__removed;344 }345 // We need to take __vr + 1 if __vr is outside bounds or we need to round up.346 _Output = __vr + (__vr == __vm || __roundUp);347 }348 const int32_t __exp = __e10 + __removed;349 350 __floating_decimal_64 __fd;351 __fd.__exponent = __exp;352 __fd.__mantissa = _Output;353 return __fd;354}355 356[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline to_chars_result __to_chars(char* const _First, char* const _Last, const __floating_decimal_64 __v,357 chars_format _Fmt, const double __f) {358 // Step 5: Print the decimal representation.359 uint64_t _Output = __v.__mantissa;360 int32_t _Ryu_exponent = __v.__exponent;361 const uint32_t __olength = __decimalLength17(_Output);362 int32_t _Scientific_exponent = _Ryu_exponent + static_cast<int32_t>(__olength) - 1;363 364 if (_Fmt == chars_format{}) {365 int32_t _Lower;366 int32_t _Upper;367 368 if (__olength == 1) {369 // Value | Fixed | Scientific370 // 1e-3 | "0.001" | "1e-03"371 // 1e4 | "10000" | "1e+04"372 _Lower = -3;373 _Upper = 4;374 } else {375 // Value | Fixed | Scientific376 // 1234e-7 | "0.0001234" | "1.234e-04"377 // 1234e5 | "123400000" | "1.234e+08"378 _Lower = -static_cast<int32_t>(__olength + 3);379 _Upper = 5;380 }381 382 if (_Lower <= _Ryu_exponent && _Ryu_exponent <= _Upper) {383 _Fmt = chars_format::fixed;384 } else {385 _Fmt = chars_format::scientific;386 }387 } else if (_Fmt == chars_format::general) {388 // C11 7.21.6.1 "The fprintf function"/8:389 // "Let P equal [...] 6 if the precision is omitted [...].390 // Then, if a conversion with style E would have an exponent of X:391 // - if P > X >= -4, the conversion is with style f [...].392 // - otherwise, the conversion is with style e [...]."393 if (-4 <= _Scientific_exponent && _Scientific_exponent < 6) {394 _Fmt = chars_format::fixed;395 } else {396 _Fmt = chars_format::scientific;397 }398 }399 400 if (_Fmt == chars_format::fixed) {401 // Example: _Output == 1729, __olength == 4402 403 // _Ryu_exponent | Printed | _Whole_digits | _Total_fixed_length | Notes404 // --------------|----------|---------------|----------------------|---------------------------------------405 // 2 | 172900 | 6 | _Whole_digits | Ryu can't be used for printing406 // 1 | 17290 | 5 | (sometimes adjusted) | when the trimmed digits are nonzero.407 // --------------|----------|---------------|----------------------|---------------------------------------408 // 0 | 1729 | 4 | _Whole_digits | Unified length cases.409 // --------------|----------|---------------|----------------------|---------------------------------------410 // -1 | 172.9 | 3 | __olength + 1 | This case can't happen for411 // -2 | 17.29 | 2 | | __olength == 1, but no additional412 // -3 | 1.729 | 1 | | code is needed to avoid it.413 // --------------|----------|---------------|----------------------|---------------------------------------414 // -4 | 0.1729 | 0 | 2 - _Ryu_exponent | C11 7.21.6.1 "The fprintf function"/8:415 // -5 | 0.01729 | -1 | | "If a decimal-point character appears,416 // -6 | 0.001729 | -2 | | at least one digit appears before it."417 418 const int32_t _Whole_digits = static_cast<int32_t>(__olength) + _Ryu_exponent;419 420 uint32_t _Total_fixed_length;421 if (_Ryu_exponent >= 0) { // cases "172900" and "1729"422 _Total_fixed_length = static_cast<uint32_t>(_Whole_digits);423 if (_Output == 1) {424 // Rounding can affect the number of digits.425 // For example, 1e23 is exactly "99999999999999991611392" which is 23 digits instead of 24.426 // We can use a lookup table to detect this and adjust the total length.427 static constexpr uint8_t _Adjustment[309] = {428 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,1,1,0,0,0,0,0,429 1,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,1,0,1,0,1,1,0,0,0,0,1,1,1,430 1,0,0,0,0,0,0,0,1,1,0,1,1,0,0,1,0,1,0,1,0,1,1,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,1,431 1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,0,0,1,1,1,1,0,0,1,1,0,1,1,0,1,1,0,1,0,0,0,1,0,0,0,1,432 0,1,0,1,0,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,1,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,0,1,433 1,1,0,1,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,1,1,0,0,1,1,1,0,0,0,1,0,1,0,0,0,0,0,1,1,0,434 0,1,0,1,1,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,0,0,0,0,1,1,0,1,0 };435 _Total_fixed_length -= _Adjustment[_Ryu_exponent];436 // _Whole_digits doesn't need to be adjusted because these cases won't refer to it later.437 }438 } else if (_Whole_digits > 0) { // case "17.29"439 _Total_fixed_length = __olength + 1;440 } else { // case "0.001729"441 _Total_fixed_length = static_cast<uint32_t>(2 - _Ryu_exponent);442 }443 444 if (_Last - _First < static_cast<ptrdiff_t>(_Total_fixed_length)) {445 return { _Last, errc::value_too_large };446 }447 448 char* _Mid;449 if (_Ryu_exponent > 0) { // case "172900"450 bool _Can_use_ryu;451 452 if (_Ryu_exponent > 22) { // 10^22 is the largest power of 10 that's exactly representable as a double.453 _Can_use_ryu = false;454 } else {455 // Ryu generated X: __v.__mantissa * 10^_Ryu_exponent456 // __v.__mantissa == 2^_Trailing_zero_bits * (__v.__mantissa >> _Trailing_zero_bits)457 // 10^_Ryu_exponent == 2^_Ryu_exponent * 5^_Ryu_exponent458 459 // _Trailing_zero_bits is [0, 56] (aside: because 2^56 is the largest power of 2460 // with 17 decimal digits, which is double's round-trip limit.)461 // _Ryu_exponent is [1, 22].462 // Normalization adds [2, 52] (aside: at least 2 because the pre-normalized mantissa is at least 5).463 // This adds up to [3, 130], which is well below double's maximum binary exponent 1023.464 465 // Therefore, we just need to consider (__v.__mantissa >> _Trailing_zero_bits) * 5^_Ryu_exponent.466 467 // If that product would exceed 53 bits, then X can't be exactly represented as a double.468 // (That's not a problem for round-tripping, because X is close enough to the original double,469 // but X isn't mathematically equal to the original double.) This requires a high-precision fallback.470 471 // If the product is 53 bits or smaller, then X can be exactly represented as a double (and we don't472 // need to re-synthesize it; the original double must have been X, because Ryu wouldn't produce the473 // same output for two different doubles X and Y). This allows Ryu's output to be used (zero-filled).474 475 // (2^53 - 1) / 5^0 (for indexing), (2^53 - 1) / 5^1, ..., (2^53 - 1) / 5^22476 static constexpr uint64_t _Max_shifted_mantissa[23] = {477 9007199254740991u, 1801439850948198u, 360287970189639u, 72057594037927u, 14411518807585u,478 2882303761517u, 576460752303u, 115292150460u, 23058430092u, 4611686018u, 922337203u, 184467440u,479 36893488u, 7378697u, 1475739u, 295147u, 59029u, 11805u, 2361u, 472u, 94u, 18u, 3u };480 481 unsigned long _Trailing_zero_bits;482#if _LIBCPP_HAS_BITSCAN64483 (void) _BitScanForward64(&_Trailing_zero_bits, __v.__mantissa); // __v.__mantissa is guaranteed nonzero484#else // ^^^ 64-bit ^^^ / vvv 32-bit vvv485 const uint32_t _Low_mantissa = static_cast<uint32_t>(__v.__mantissa);486 if (_Low_mantissa != 0) {487 (void) _BitScanForward(&_Trailing_zero_bits, _Low_mantissa);488 } else {489 const uint32_t _High_mantissa = static_cast<uint32_t>(__v.__mantissa >> 32); // nonzero here490 (void) _BitScanForward(&_Trailing_zero_bits, _High_mantissa);491 _Trailing_zero_bits += 32;492 }493#endif // ^^^ 32-bit ^^^494 const uint64_t _Shifted_mantissa = __v.__mantissa >> _Trailing_zero_bits;495 _Can_use_ryu = _Shifted_mantissa <= _Max_shifted_mantissa[_Ryu_exponent];496 }497 498 if (!_Can_use_ryu) {499 // Print the integer exactly.500 // Performance note: This will redundantly perform bounds checking.501 // Performance note: This will redundantly decompose the IEEE representation.502 return __d2fixed_buffered_n(_First, _Last, __f, 0);503 }504 505 // _Can_use_ryu506 // Print the decimal digits, left-aligned within [_First, _First + _Total_fixed_length).507 _Mid = _First + __olength;508 } else { // cases "1729", "17.29", and "0.001729"509 // Print the decimal digits, right-aligned within [_First, _First + _Total_fixed_length).510 _Mid = _First + _Total_fixed_length;511 }512 513 // We prefer 32-bit operations, even on 64-bit platforms.514 // We have at most 17 digits, and uint32_t can store 9 digits.515 // If _Output doesn't fit into uint32_t, we cut off 8 digits,516 // so the rest will fit into uint32_t.517 if ((_Output >> 32) != 0) {518 // Expensive 64-bit division.519 const uint64_t __q = __div1e8(_Output);520 uint32_t __output2 = static_cast<uint32_t>(_Output - 100000000 * __q);521 _Output = __q;522 523 const uint32_t __c = __output2 % 10000;524 __output2 /= 10000;525 const uint32_t __d = __output2 % 10000;526 const uint32_t __c0 = (__c % 100) << 1;527 const uint32_t __c1 = (__c / 100) << 1;528 const uint32_t __d0 = (__d % 100) << 1;529 const uint32_t __d1 = (__d / 100) << 1;530 531 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c0, 2);532 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c1, 2);533 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __d0, 2);534 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __d1, 2);535 }536 uint32_t __output2 = static_cast<uint32_t>(_Output);537 while (__output2 >= 10000) {538#ifdef __clang__ // TRANSITION, LLVM-38217539 const uint32_t __c = __output2 - 10000 * (__output2 / 10000);540#else541 const uint32_t __c = __output2 % 10000;542#endif543 __output2 /= 10000;544 const uint32_t __c0 = (__c % 100) << 1;545 const uint32_t __c1 = (__c / 100) << 1;546 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c0, 2);547 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c1, 2);548 }549 if (__output2 >= 100) {550 const uint32_t __c = (__output2 % 100) << 1;551 __output2 /= 100;552 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c, 2);553 }554 if (__output2 >= 10) {555 const uint32_t __c = __output2 << 1;556 std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c, 2);557 } else {558 *--_Mid = static_cast<char>('0' + __output2);559 }560 561 if (_Ryu_exponent > 0) { // case "172900" with _Can_use_ryu562 // Performance note: it might be more efficient to do this immediately after setting _Mid.563 std::memset(_First + __olength, '0', static_cast<size_t>(_Ryu_exponent));564 } else if (_Ryu_exponent == 0) { // case "1729"565 // Done!566 } else if (_Whole_digits > 0) { // case "17.29"567 // Performance note: moving digits might not be optimal.568 std::memmove(_First, _First + 1, static_cast<size_t>(_Whole_digits));569 _First[_Whole_digits] = '.';570 } else { // case "0.001729"571 // Performance note: a larger memset() followed by overwriting '.' might be more efficient.572 _First[0] = '0';573 _First[1] = '.';574 std::memset(_First + 2, '0', static_cast<size_t>(-_Whole_digits));575 }576 577 return { _First + _Total_fixed_length, errc{} };578 }579 580 const uint32_t _Total_scientific_length = __olength + (__olength > 1) // digits + possible decimal point581 + (-100 < _Scientific_exponent && _Scientific_exponent < 100 ? 4 : 5); // + scientific exponent582 if (_Last - _First < static_cast<ptrdiff_t>(_Total_scientific_length)) {583 return { _Last, errc::value_too_large };584 }585 char* const __result = _First;586 587 // Print the decimal digits.588 uint32_t __i = 0;589 // We prefer 32-bit operations, even on 64-bit platforms.590 // We have at most 17 digits, and uint32_t can store 9 digits.591 // If _Output doesn't fit into uint32_t, we cut off 8 digits,592 // so the rest will fit into uint32_t.593 if ((_Output >> 32) != 0) {594 // Expensive 64-bit division.595 const uint64_t __q = __div1e8(_Output);596 uint32_t __output2 = static_cast<uint32_t>(_Output) - 100000000 * static_cast<uint32_t>(__q);597 _Output = __q;598 599 const uint32_t __c = __output2 % 10000;600 __output2 /= 10000;601 const uint32_t __d = __output2 % 10000;602 const uint32_t __c0 = (__c % 100) << 1;603 const uint32_t __c1 = (__c / 100) << 1;604 const uint32_t __d0 = (__d % 100) << 1;605 const uint32_t __d1 = (__d / 100) << 1;606 std::memcpy(__result + __olength - __i - 1, __DIGIT_TABLE + __c0, 2);607 std::memcpy(__result + __olength - __i - 3, __DIGIT_TABLE + __c1, 2);608 std::memcpy(__result + __olength - __i - 5, __DIGIT_TABLE + __d0, 2);609 std::memcpy(__result + __olength - __i - 7, __DIGIT_TABLE + __d1, 2);610 __i += 8;611 }612 uint32_t __output2 = static_cast<uint32_t>(_Output);613 while (__output2 >= 10000) {614#ifdef __clang__ // TRANSITION, LLVM-38217615 const uint32_t __c = __output2 - 10000 * (__output2 / 10000);616#else617 const uint32_t __c = __output2 % 10000;618#endif619 __output2 /= 10000;620 const uint32_t __c0 = (__c % 100) << 1;621 const uint32_t __c1 = (__c / 100) << 1;622 std::memcpy(__result + __olength - __i - 1, __DIGIT_TABLE + __c0, 2);623 std::memcpy(__result + __olength - __i - 3, __DIGIT_TABLE + __c1, 2);624 __i += 4;625 }626 if (__output2 >= 100) {627 const uint32_t __c = (__output2 % 100) << 1;628 __output2 /= 100;629 std::memcpy(__result + __olength - __i - 1, __DIGIT_TABLE + __c, 2);630 __i += 2;631 }632 if (__output2 >= 10) {633 const uint32_t __c = __output2 << 1;634 // We can't use memcpy here: the decimal dot goes between these two digits.635 __result[2] = __DIGIT_TABLE[__c + 1];636 __result[0] = __DIGIT_TABLE[__c];637 } else {638 __result[0] = static_cast<char>('0' + __output2);639 }640 641 // Print decimal point if needed.642 uint32_t __index;643 if (__olength > 1) {644 __result[1] = '.';645 __index = __olength + 1;646 } else {647 __index = 1;648 }649 650 // Print the exponent.651 __result[__index++] = 'e';652 if (_Scientific_exponent < 0) {653 __result[__index++] = '-';654 _Scientific_exponent = -_Scientific_exponent;655 } else {656 __result[__index++] = '+';657 }658 659 if (_Scientific_exponent >= 100) {660 const int32_t __c = _Scientific_exponent % 10;661 std::memcpy(__result + __index, __DIGIT_TABLE + 2 * (_Scientific_exponent / 10), 2);662 __result[__index + 2] = static_cast<char>('0' + __c);663 __index += 3;664 } else {665 std::memcpy(__result + __index, __DIGIT_TABLE + 2 * _Scientific_exponent, 2);666 __index += 2;667 }668 669 return { _First + _Total_scientific_length, errc{} };670}671 672[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline bool __d2d_small_int(const uint64_t __ieeeMantissa, const uint32_t __ieeeExponent,673 __floating_decimal_64* const __v) {674 const uint64_t __m2 = (1ull << __DOUBLE_MANTISSA_BITS) | __ieeeMantissa;675 const int32_t __e2 = static_cast<int32_t>(__ieeeExponent) - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS;676 677 if (__e2 > 0) {678 // f = __m2 * 2^__e2 >= 2^53 is an integer.679 // Ignore this case for now.680 return false;681 }682 683 if (__e2 < -52) {684 // f < 1.685 return false;686 }687 688 // Since 2^52 <= __m2 < 2^53 and 0 <= -__e2 <= 52: 1 <= f = __m2 / 2^-__e2 < 2^53.689 // Test if the lower -__e2 bits of the significand are 0, i.e. whether the fraction is 0.690 const uint64_t __mask = (1ull << -__e2) - 1;691 const uint64_t __fraction = __m2 & __mask;692 if (__fraction != 0) {693 return false;694 }695 696 // f is an integer in the range [1, 2^53).697 // Note: __mantissa might contain trailing (decimal) 0's.698 // Note: since 2^53 < 10^16, there is no need to adjust __decimalLength17().699 __v->__mantissa = __m2 >> -__e2;700 __v->__exponent = 0;701 return true;702}703 704[[nodiscard]] to_chars_result __d2s_buffered_n(char* const _First, char* const _Last, const double __f,705 const chars_format _Fmt) {706 707 // Step 1: Decode the floating-point number, and unify normalized and subnormal cases.708 const uint64_t __bits = __double_to_bits(__f);709 710 // Case distinction; exit early for the easy cases.711 if (__bits == 0) {712 if (_Fmt == chars_format::scientific) {713 if (_Last - _First < 5) {714 return { _Last, errc::value_too_large };715 }716 717 std::memcpy(_First, "0e+00", 5);718 719 return { _First + 5, errc{} };720 }721 722 // Print "0" for chars_format::fixed, chars_format::general, and chars_format{}.723 if (_First == _Last) {724 return { _Last, errc::value_too_large };725 }726 727 *_First = '0';728 729 return { _First + 1, errc{} };730 }731 732 // Decode __bits into mantissa and exponent.733 const uint64_t __ieeeMantissa = __bits & ((1ull << __DOUBLE_MANTISSA_BITS) - 1);734 const uint32_t __ieeeExponent = static_cast<uint32_t>(__bits >> __DOUBLE_MANTISSA_BITS);735 736 if (_Fmt == chars_format::fixed) {737 // const uint64_t _Mantissa2 = __ieeeMantissa | (1ull << __DOUBLE_MANTISSA_BITS); // restore implicit bit738 const int32_t _Exponent2 = static_cast<int32_t>(__ieeeExponent)739 - __DOUBLE_BIAS - __DOUBLE_MANTISSA_BITS; // bias and normalization740 741 // Normal values are equal to _Mantissa2 * 2^_Exponent2.742 // (Subnormals are different, but they'll be rejected by the _Exponent2 test here, so they can be ignored.)743 744 // For nonzero integers, _Exponent2 >= -52. (The minimum value occurs when _Mantissa2 * 2^_Exponent2 is 1.745 // In that case, _Mantissa2 is the implicit 1 bit followed by 52 zeros, so _Exponent2 is -52 to shift away746 // the zeros.) The dense range of exactly representable integers has negative or zero exponents747 // (as positive exponents make the range non-dense). For that dense range, Ryu will always be used:748 // every digit is necessary to uniquely identify the value, so Ryu must print them all.749 750 // Positive exponents are the non-dense range of exactly representable integers. This contains all of the values751 // for which Ryu can't be used (and a few Ryu-friendly values). We can save time by detecting positive752 // exponents here and skipping Ryu. Calling __d2fixed_buffered_n() with precision 0 is valid for all integers753 // (so it's okay if we call it with a Ryu-friendly value).754 if (_Exponent2 > 0) {755 return __d2fixed_buffered_n(_First, _Last, __f, 0);756 }757 }758 759 __floating_decimal_64 __v;760 const bool __isSmallInt = __d2d_small_int(__ieeeMantissa, __ieeeExponent, &__v);761 if (__isSmallInt) {762 // For small integers in the range [1, 2^53), __v.__mantissa might contain trailing (decimal) zeros.763 // For scientific notation we need to move these zeros into the exponent.764 // (This is not needed for fixed-point notation, so it might be beneficial to trim765 // trailing zeros in __to_chars only if needed - once fixed-point notation output is implemented.)766 for (;;) {767 const uint64_t __q = __div10(__v.__mantissa);768 const uint32_t __r = static_cast<uint32_t>(__v.__mantissa) - 10 * static_cast<uint32_t>(__q);769 if (__r != 0) {770 break;771 }772 __v.__mantissa = __q;773 ++__v.__exponent;774 }775 } else {776 __v = __d2d(__ieeeMantissa, __ieeeExponent);777 }778 779 return __to_chars(_First, _Last, __v, _Fmt, __f);780}781 782_LIBCPP_END_NAMESPACE_STD783 784// clang-format on785