138032Speter//===----------------------------------------------------------------------===// 264565Sgshapiro// 364565Sgshapiro// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 438032Speter// See https://llvm.org/LICENSE.txt for license information. 538032Speter// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 638032Speter// 738032Speter//===----------------------------------------------------------------------===// 838032Speter 938032Speter// Copyright (c) Microsoft Corporation. 1038032Speter// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 1138032Speter 1238032Speter// Copyright 2018 Ulf Adams 1338032Speter// Copyright (c) Microsoft Corporation. All rights reserved. 1438032Speter 1571348Sgshapiro// Boost Software License - Version 1.0 - August 17th, 2003 1664565Sgshapiro 1738032Speter// Permission is hereby granted, free of charge, to any person or organization 1864565Sgshapiro// obtaining a copy of the software and accompanying documentation covered by 1964565Sgshapiro// this license (the "Software") to use, reproduce, display, distribute, 2064565Sgshapiro// execute, and transmit the Software, and to prepare derivative works of the 2164565Sgshapiro// Software, and to permit third-parties to whom the Software is furnished to 2264565Sgshapiro// do so, all subject to the following: 2364565Sgshapiro 2464565Sgshapiro// The copyright notices in the Software and this entire statement, including 2564565Sgshapiro// the above license grant, this restriction and the following disclaimer, 2664565Sgshapiro// must be included in all copies of the Software, in whole or in part, and 2738032Speter// all derivative works of the Software, unless such copies or derivative 2838032Speter// works are solely in the form of machine-executable object code generated by 2964565Sgshapiro// a source language processor. 3064565Sgshapiro 3164565Sgshapiro// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 3264565Sgshapiro// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 3364565Sgshapiro// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 3464565Sgshapiro// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 3564565Sgshapiro// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 3638032Speter// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 3738032Speter// DEALINGS IN THE SOFTWARE. 3838032Speter 3938032Speter// Avoid formatting to keep the changes with the original code minimal. 4038032Speter// clang-format off 4138032Speter 4238032Speter#include <__assert> 4338032Speter#include <__config> 4438032Speter#include <charconv> 4538032Speter 4638032Speter#include "include/ryu/common.h" 4738032Speter#include "include/ryu/d2fixed.h" 4838032Speter#include "include/ryu/d2s_intrinsics.h" 4938032Speter#include "include/ryu/digit_table.h" 5038032Speter#include "include/ryu/f2s.h" 5138032Speter#include "include/ryu/ryu.h" 5238032Speter 5338032Speter_LIBCPP_BEGIN_NAMESPACE_STD 5438032Speter 5538032Speterinline constexpr int __FLOAT_MANTISSA_BITS = 23; 5638032Speterinline constexpr int __FLOAT_EXPONENT_BITS = 8; 5738032Speterinline constexpr int __FLOAT_BIAS = 127; 5838032Speter 5938032Speterinline constexpr int __FLOAT_POW5_INV_BITCOUNT = 59; 6038032Speterinline constexpr uint64_t __FLOAT_POW5_INV_SPLIT[31] = { 6138032Speter 576460752303423489u, 461168601842738791u, 368934881474191033u, 295147905179352826u, 6238032Speter 472236648286964522u, 377789318629571618u, 302231454903657294u, 483570327845851670u, 6338032Speter 386856262276681336u, 309485009821345069u, 495176015714152110u, 396140812571321688u, 6438032Speter 316912650057057351u, 507060240091291761u, 405648192073033409u, 324518553658426727u, 6538032Speter 519229685853482763u, 415383748682786211u, 332306998946228969u, 531691198313966350u, 6638032Speter 425352958651173080u, 340282366920938464u, 544451787073501542u, 435561429658801234u, 6764565Sgshapiro 348449143727040987u, 557518629963265579u, 446014903970612463u, 356811923176489971u, 6838032Speter 570899077082383953u, 456719261665907162u, 365375409332725730u 6938032Speter}; 7038032Speterinline constexpr int __FLOAT_POW5_BITCOUNT = 61; 7138032Speterinline constexpr uint64_t __FLOAT_POW5_SPLIT[47] = { 7238032Speter 1152921504606846976u, 1441151880758558720u, 1801439850948198400u, 2251799813685248000u, 7338032Speter 1407374883553280000u, 1759218604441600000u, 2199023255552000000u, 1374389534720000000u, 7438032Speter 1717986918400000000u, 2147483648000000000u, 1342177280000000000u, 1677721600000000000u, 7538032Speter 2097152000000000000u, 1310720000000000000u, 1638400000000000000u, 2048000000000000000u, 7638032Speter 1280000000000000000u, 1600000000000000000u, 2000000000000000000u, 1250000000000000000u, 7738032Speter 1562500000000000000u, 1953125000000000000u, 1220703125000000000u, 1525878906250000000u, 7838032Speter 1907348632812500000u, 1192092895507812500u, 1490116119384765625u, 1862645149230957031u, 7938032Speter 1164153218269348144u, 1455191522836685180u, 1818989403545856475u, 2273736754432320594u, 8038032Speter 1421085471520200371u, 1776356839400250464u, 2220446049250313080u, 1387778780781445675u, 8138032Speter 1734723475976807094u, 2168404344971008868u, 1355252715606880542u, 1694065894508600678u, 8238032Speter 2117582368135750847u, 1323488980084844279u, 1654361225106055349u, 2067951531382569187u, 8338032Speter 1292469707114105741u, 1615587133892632177u, 2019483917365790221u 8438032Speter}; 8538032Speter 8638032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __pow5Factor(uint32_t __value) { 8738032Speter uint32_t __count = 0; 8838032Speter for (;;) { 8938032Speter _LIBCPP_ASSERT_INTERNAL(__value != 0, ""); 9038032Speter const uint32_t __q = __value / 5; 9138032Speter const uint32_t __r = __value % 5; 9238032Speter if (__r != 0) { 9338032Speter break; 9438032Speter } 9538032Speter __value = __q; 9638032Speter ++__count; 9738032Speter } 9838032Speter return __count; 9938032Speter} 10038032Speter 10138032Speter// Returns true if __value is divisible by 5^__p. 10238032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline bool __multipleOfPowerOf5(const uint32_t __value, const uint32_t __p) { 10338032Speter return __pow5Factor(__value) >= __p; 10438032Speter} 10538032Speter 10638032Speter// Returns true if __value is divisible by 2^__p. 10738032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline bool __multipleOfPowerOf2(const uint32_t __value, const uint32_t __p) { 10838032Speter _LIBCPP_ASSERT_INTERNAL(__value != 0, ""); 10938032Speter _LIBCPP_ASSERT_INTERNAL(__p < 32, ""); 11038032Speter // __builtin_ctz doesn't appear to be faster here. 11164565Sgshapiro return (__value & ((1u << __p) - 1)) == 0; 11264565Sgshapiro} 11364565Sgshapiro 11438032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __mulShift(const uint32_t __m, const uint64_t __factor, const int32_t __shift) { 11538032Speter _LIBCPP_ASSERT_INTERNAL(__shift > 32, ""); 11664565Sgshapiro 11764565Sgshapiro // The casts here help MSVC to avoid calls to the __allmul library 11838032Speter // function. 11938032Speter const uint32_t __factorLo = static_cast<uint32_t>(__factor); 12038032Speter const uint32_t __factorHi = static_cast<uint32_t>(__factor >> 32); 12138032Speter const uint64_t __bits0 = static_cast<uint64_t>(__m) * __factorLo; 12238032Speter const uint64_t __bits1 = static_cast<uint64_t>(__m) * __factorHi; 12338032Speter 12438032Speter#ifndef _LIBCPP_64_BIT 12538032Speter // On 32-bit platforms we can avoid a 64-bit shift-right since we only 12638032Speter // need the upper 32 bits of the result and the shift value is > 32. 12738032Speter const uint32_t __bits0Hi = static_cast<uint32_t>(__bits0 >> 32); 12838032Speter uint32_t __bits1Lo = static_cast<uint32_t>(__bits1); 12938032Speter uint32_t __bits1Hi = static_cast<uint32_t>(__bits1 >> 32); 13038032Speter __bits1Lo += __bits0Hi; 13138032Speter __bits1Hi += (__bits1Lo < __bits0Hi); 13238032Speter const int32_t __s = __shift - 32; 13338032Speter return (__bits1Hi << (32 - __s)) | (__bits1Lo >> __s); 13438032Speter#else // ^^^ 32-bit ^^^ / vvv 64-bit vvv 13538032Speter const uint64_t __sum = (__bits0 >> 32) + __bits1; 13638032Speter const uint64_t __shiftedSum = __sum >> (__shift - 32); 13738032Speter _LIBCPP_ASSERT_INTERNAL(__shiftedSum <= UINT32_MAX, ""); 13838032Speter return static_cast<uint32_t>(__shiftedSum); 13938032Speter#endif // ^^^ 64-bit ^^^ 14038032Speter} 14138032Speter 14238032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __mulPow5InvDivPow2(const uint32_t __m, const uint32_t __q, const int32_t __j) { 14338032Speter return __mulShift(__m, __FLOAT_POW5_INV_SPLIT[__q], __j); 14438032Speter} 14538032Speter 14638032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline uint32_t __mulPow5divPow2(const uint32_t __m, const uint32_t __i, const int32_t __j) { 14738032Speter return __mulShift(__m, __FLOAT_POW5_SPLIT[__i], __j); 14838032Speter} 14938032Speter 15038032Speter// A floating decimal representing m * 10^e. 15164565Sgshapirostruct __floating_decimal_32 { 15264565Sgshapiro uint32_t __mantissa; 15338032Speter int32_t __exponent; 15438032Speter}; 15538032Speter 15638032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline __floating_decimal_32 __f2d(const uint32_t __ieeeMantissa, const uint32_t __ieeeExponent) { 15738032Speter int32_t __e2; 15838032Speter uint32_t __m2; 15938032Speter if (__ieeeExponent == 0) { 16038032Speter // We subtract 2 so that the bounds computation has 2 additional bits. 16138032Speter __e2 = 1 - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS - 2; 16238032Speter __m2 = __ieeeMantissa; 16338032Speter } else { 16438032Speter __e2 = static_cast<int32_t>(__ieeeExponent) - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS - 2; 16564565Sgshapiro __m2 = (1u << __FLOAT_MANTISSA_BITS) | __ieeeMantissa; 16664565Sgshapiro } 16764565Sgshapiro const bool __even = (__m2 & 1) == 0; 16864565Sgshapiro const bool __acceptBounds = __even; 16964565Sgshapiro 17038032Speter // Step 2: Determine the interval of valid decimal representations. 17164565Sgshapiro const uint32_t __mv = 4 * __m2; 17238032Speter const uint32_t __mp = 4 * __m2 + 2; 17364565Sgshapiro // Implicit bool -> int conversion. True is 1, false is 0. 17464565Sgshapiro const uint32_t __mmShift = __ieeeMantissa != 0 || __ieeeExponent <= 1; 17538032Speter const uint32_t __mm = 4 * __m2 - 1 - __mmShift; 17638032Speter 17738032Speter // Step 3: Convert to a decimal power base using 64-bit arithmetic. 17838032Speter uint32_t __vr, __vp, __vm; 17938032Speter int32_t __e10; 18038032Speter bool __vmIsTrailingZeros = false; 18138032Speter bool __vrIsTrailingZeros = false; 18238032Speter uint8_t __lastRemovedDigit = 0; 18338032Speter if (__e2 >= 0) { 18438032Speter const uint32_t __q = __log10Pow2(__e2); 18538032Speter __e10 = static_cast<int32_t>(__q); 18638032Speter const int32_t __k = __FLOAT_POW5_INV_BITCOUNT + __pow5bits(static_cast<int32_t>(__q)) - 1; 18738032Speter const int32_t __i = -__e2 + static_cast<int32_t>(__q) + __k; 18838032Speter __vr = __mulPow5InvDivPow2(__mv, __q, __i); 18938032Speter __vp = __mulPow5InvDivPow2(__mp, __q, __i); 19038032Speter __vm = __mulPow5InvDivPow2(__mm, __q, __i); 19138032Speter if (__q != 0 && (__vp - 1) / 10 <= __vm / 10) { 19238032Speter // We need to know one removed digit even if we are not going to loop below. We could use 19338032Speter // __q = X - 1 above, except that would require 33 bits for the result, and we've found that 19438032Speter // 32-bit arithmetic is faster even on 64-bit machines. 19538032Speter const int32_t __l = __FLOAT_POW5_INV_BITCOUNT + __pow5bits(static_cast<int32_t>(__q - 1)) - 1; 19638032Speter __lastRemovedDigit = static_cast<uint8_t>(__mulPow5InvDivPow2(__mv, __q - 1, 19738032Speter -__e2 + static_cast<int32_t>(__q) - 1 + __l) % 10); 19838032Speter } 19938032Speter if (__q <= 9) { 20064565Sgshapiro // The largest power of 5 that fits in 24 bits is 5^10, but __q <= 9 seems to be safe as well. 20138032Speter // Only one of __mp, __mv, and __mm can be a multiple of 5, if any. 20238032Speter if (__mv % 5 == 0) { 20338032Speter __vrIsTrailingZeros = __multipleOfPowerOf5(__mv, __q); 20438032Speter } else if (__acceptBounds) { 20538032Speter __vmIsTrailingZeros = __multipleOfPowerOf5(__mm, __q); 20638032Speter } else { 20738032Speter __vp -= __multipleOfPowerOf5(__mp, __q); 20838032Speter } 20938032Speter } 21038032Speter } else { 21138032Speter const uint32_t __q = __log10Pow5(-__e2); 21238032Speter __e10 = static_cast<int32_t>(__q) + __e2; 21338032Speter const int32_t __i = -__e2 - static_cast<int32_t>(__q); 21438032Speter const int32_t __k = __pow5bits(__i) - __FLOAT_POW5_BITCOUNT; 21538032Speter int32_t __j = static_cast<int32_t>(__q) - __k; 21638032Speter __vr = __mulPow5divPow2(__mv, static_cast<uint32_t>(__i), __j); 21738032Speter __vp = __mulPow5divPow2(__mp, static_cast<uint32_t>(__i), __j); 21864565Sgshapiro __vm = __mulPow5divPow2(__mm, static_cast<uint32_t>(__i), __j); 21938032Speter if (__q != 0 && (__vp - 1) / 10 <= __vm / 10) { 22038032Speter __j = static_cast<int32_t>(__q) - 1 - (__pow5bits(__i + 1) - __FLOAT_POW5_BITCOUNT); 22138032Speter __lastRemovedDigit = static_cast<uint8_t>(__mulPow5divPow2(__mv, static_cast<uint32_t>(__i + 1), __j) % 10); 22238032Speter } 22364565Sgshapiro if (__q <= 1) { 22464565Sgshapiro // {__vr,__vp,__vm} is trailing zeros if {__mv,__mp,__mm} has at least __q trailing 0 bits. 22564565Sgshapiro // __mv = 4 * __m2, so it always has at least two trailing 0 bits. 22638032Speter __vrIsTrailingZeros = true; 22764565Sgshapiro if (__acceptBounds) { 22838032Speter // __mm = __mv - 1 - __mmShift, so it has 1 trailing 0 bit iff __mmShift == 1. 22938032Speter __vmIsTrailingZeros = __mmShift == 1; 23038032Speter } else { 23138032Speter // __mp = __mv + 2, so it always has at least one trailing 0 bit. 23238032Speter --__vp; 23338032Speter } 23438032Speter } else if (__q < 31) { // TRANSITION(ulfjack): Use a tighter bound here. 23538032Speter __vrIsTrailingZeros = __multipleOfPowerOf2(__mv, __q - 1); 23638032Speter } 23738032Speter } 23864565Sgshapiro 23938032Speter // Step 4: Find the shortest decimal representation in the interval of valid representations. 24064565Sgshapiro int32_t __removed = 0; 24138032Speter uint32_t _Output; 24238032Speter if (__vmIsTrailingZeros || __vrIsTrailingZeros) { 24364565Sgshapiro // General case, which happens rarely (~4.0%). 24438032Speter while (__vp / 10 > __vm / 10) { 24538032Speter#ifdef __clang__ // TRANSITION, LLVM-23106 24664565Sgshapiro __vmIsTrailingZeros &= __vm - (__vm / 10) * 10 == 0; 24738032Speter#else 24864565Sgshapiro __vmIsTrailingZeros &= __vm % 10 == 0; 24938032Speter#endif 25038032Speter __vrIsTrailingZeros &= __lastRemovedDigit == 0; 25138032Speter __lastRemovedDigit = static_cast<uint8_t>(__vr % 10); 25238032Speter __vr /= 10; 25338032Speter __vp /= 10; 25438032Speter __vm /= 10; 25538032Speter ++__removed; 25638032Speter } 25738032Speter if (__vmIsTrailingZeros) { 25838032Speter while (__vm % 10 == 0) { 25938032Speter __vrIsTrailingZeros &= __lastRemovedDigit == 0; 26038032Speter __lastRemovedDigit = static_cast<uint8_t>(__vr % 10); 26138032Speter __vr /= 10; 26238032Speter __vp /= 10; 26338032Speter __vm /= 10; 26438032Speter ++__removed; 26538032Speter } 26638032Speter } 26738032Speter if (__vrIsTrailingZeros && __lastRemovedDigit == 5 && __vr % 2 == 0) { 26838032Speter // Round even if the exact number is .....50..0. 26938032Speter __lastRemovedDigit = 4; 27038032Speter } 27138032Speter // We need to take __vr + 1 if __vr is outside bounds or we need to round up. 27238032Speter _Output = __vr + ((__vr == __vm && (!__acceptBounds || !__vmIsTrailingZeros)) || __lastRemovedDigit >= 5); 27338032Speter } else { 27438032Speter // Specialized for the common case (~96.0%). Percentages below are relative to this. 27538032Speter // Loop iterations below (approximately): 27638032Speter // 0: 13.6%, 1: 70.7%, 2: 14.1%, 3: 1.39%, 4: 0.14%, 5+: 0.01% 27738032Speter while (__vp / 10 > __vm / 10) { 27838032Speter __lastRemovedDigit = static_cast<uint8_t>(__vr % 10); 27971348Sgshapiro __vr /= 10; 28038032Speter __vp /= 10; 28138032Speter __vm /= 10; 28271348Sgshapiro ++__removed; 28338032Speter } 28438032Speter // We need to take __vr + 1 if __vr is outside bounds or we need to round up. 28538032Speter _Output = __vr + (__vr == __vm || __lastRemovedDigit >= 5); 28638032Speter } 28738032Speter const int32_t __exp = __e10 + __removed; 28838032Speter 28938032Speter __floating_decimal_32 __fd; 29038032Speter __fd.__exponent = __exp; 29138032Speter __fd.__mantissa = _Output; 29238032Speter return __fd; 29338032Speter} 29438032Speter 29538032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline to_chars_result _Large_integer_to_chars(char* const _First, char* const _Last, 29638032Speter const uint32_t _Mantissa2, const int32_t _Exponent2) { 29738032Speter 29838032Speter // Print the integer _Mantissa2 * 2^_Exponent2 exactly. 29938032Speter 30064565Sgshapiro // For nonzero integers, _Exponent2 >= -23. (The minimum value occurs when _Mantissa2 * 2^_Exponent2 is 1. 30164565Sgshapiro // In that case, _Mantissa2 is the implicit 1 bit followed by 23 zeros, so _Exponent2 is -23 to shift away 30238032Speter // the zeros.) The dense range of exactly representable integers has negative or zero exponents 30338032Speter // (as positive exponents make the range non-dense). For that dense range, Ryu will always be used: 30438032Speter // every digit is necessary to uniquely identify the value, so Ryu must print them all. 30538032Speter 30638032Speter // Positive exponents are the non-dense range of exactly representable integers. 30771348Sgshapiro // This contains all of the values for which Ryu can't be used (and a few Ryu-friendly values). 30864565Sgshapiro 30938032Speter // Performance note: Long division appears to be faster than losslessly widening float to double and calling 31038032Speter // __d2fixed_buffered_n(). If __f2fixed_buffered_n() is implemented, it might be faster than long division. 31138032Speter 31264565Sgshapiro _LIBCPP_ASSERT_INTERNAL(_Exponent2 > 0, ""); 31364565Sgshapiro _LIBCPP_ASSERT_INTERNAL(_Exponent2 <= 104, ""); // because __ieeeExponent <= 254 31464565Sgshapiro 31564565Sgshapiro // Manually represent _Mantissa2 * 2^_Exponent2 as a large integer. _Mantissa2 is always 24 bits 31664565Sgshapiro // (due to the implicit bit), while _Exponent2 indicates a shift of at most 104 bits. 31764565Sgshapiro // 24 + 104 equals 128 equals 4 * 32, so we need exactly 4 32-bit elements. 31864565Sgshapiro // We use a little-endian representation, visualized like this: 31964565Sgshapiro 32038032Speter // << left shift << 32138032Speter // most significant 32264565Sgshapiro // _Data[3] _Data[2] _Data[1] _Data[0] 32364565Sgshapiro // least significant 32438032Speter // >> right shift >> 32538032Speter 32638032Speter constexpr uint32_t _Data_size = 4; 32738032Speter uint32_t _Data[_Data_size]{}; 32838032Speter 32938032Speter // _Maxidx is the index of the most significant nonzero element. 33038032Speter uint32_t _Maxidx = ((24 + static_cast<uint32_t>(_Exponent2) + 31) / 32) - 1; 33138032Speter _LIBCPP_ASSERT_INTERNAL(_Maxidx < _Data_size, ""); 33264565Sgshapiro 33338032Speter const uint32_t _Bit_shift = static_cast<uint32_t>(_Exponent2) % 32; 33438032Speter if (_Bit_shift <= 8) { // _Mantissa2's 24 bits don't cross an element boundary 33538032Speter _Data[_Maxidx] = _Mantissa2 << _Bit_shift; 33638032Speter } else { // _Mantissa2's 24 bits cross an element boundary 33738032Speter _Data[_Maxidx - 1] = _Mantissa2 << _Bit_shift; 33838032Speter _Data[_Maxidx] = _Mantissa2 >> (32 - _Bit_shift); 33938032Speter } 34038032Speter 34138032Speter // If Ryu hasn't determined the total output length, we need to buffer the digits generated from right to left 34238032Speter // by long division. The largest possible float is: 340'282346638'528859811'704183484'516925440 34338032Speter uint32_t _Blocks[4]; 34438032Speter int32_t _Filled_blocks = 0; 34538032Speter // From left to right, we're going to print: 34638032Speter // _Data[0] will be [1, 10] digits. 34738032Speter // Then if _Filled_blocks > 0: 34838032Speter // _Blocks[_Filled_blocks - 1], ..., _Blocks[0] will be 0-filled 9-digit blocks. 34938032Speter 35038032Speter if (_Maxidx != 0) { // If the integer is actually large, perform long division. 35138032Speter // Otherwise, skip to printing _Data[0]. 35238032Speter for (;;) { 35338032Speter // Loop invariant: _Maxidx != 0 (i.e. the integer is actually large) 35438032Speter 35538032Speter const uint32_t _Most_significant_elem = _Data[_Maxidx]; 35638032Speter const uint32_t _Initial_remainder = _Most_significant_elem % 1000000000; 35738032Speter const uint32_t _Initial_quotient = _Most_significant_elem / 1000000000; 35838032Speter _Data[_Maxidx] = _Initial_quotient; 35938032Speter uint64_t _Remainder = _Initial_remainder; 36064565Sgshapiro 36138032Speter // Process less significant elements. 36264565Sgshapiro uint32_t _Idx = _Maxidx; 36338032Speter do { 36438032Speter --_Idx; // Initially, _Remainder is at most 10^9 - 1. 36538032Speter 36638032Speter // Now, _Remainder is at most (10^9 - 1) * 2^32 + 2^32 - 1, simplified to 10^9 * 2^32 - 1. 36738032Speter _Remainder = (_Remainder << 32) | _Data[_Idx]; 36838032Speter 36938032Speter // floor((10^9 * 2^32 - 1) / 10^9) == 2^32 - 1, so uint32_t _Quotient is lossless. 37038032Speter const uint32_t _Quotient = static_cast<uint32_t>(__div1e9(_Remainder)); 37138032Speter 37238032Speter // _Remainder is at most 10^9 - 1 again. 37338032Speter // For uint32_t truncation, see the __mod1e9() comment in d2s_intrinsics.h. 37438032Speter _Remainder = static_cast<uint32_t>(_Remainder) - 1000000000u * _Quotient; 37538032Speter 37638032Speter _Data[_Idx] = _Quotient; 37738032Speter } while (_Idx != 0); 37838032Speter 37964565Sgshapiro // Store a 0-filled 9-digit block. 38064565Sgshapiro _Blocks[_Filled_blocks++] = static_cast<uint32_t>(_Remainder); 38164565Sgshapiro 38264565Sgshapiro if (_Initial_quotient == 0) { // Is the large integer shrinking? 38364565Sgshapiro --_Maxidx; // log2(10^9) is 29.9, so we can't shrink by more than one element. 38464565Sgshapiro if (_Maxidx == 0) { 38564565Sgshapiro break; // We've finished long division. Now we need to print _Data[0]. 38664565Sgshapiro } 38764565Sgshapiro } 38864565Sgshapiro } 38964565Sgshapiro } 39071348Sgshapiro 39164565Sgshapiro _LIBCPP_ASSERT_INTERNAL(_Data[0] != 0, ""); 39264565Sgshapiro for (uint32_t _Idx = 1; _Idx < _Data_size; ++_Idx) { 39364565Sgshapiro _LIBCPP_ASSERT_INTERNAL(_Data[_Idx] == 0, ""); 39464565Sgshapiro } 39564565Sgshapiro 39664565Sgshapiro const uint32_t _Data_olength = _Data[0] >= 1000000000 ? 10 : __decimalLength9(_Data[0]); 39764565Sgshapiro const uint32_t _Total_fixed_length = _Data_olength + 9 * _Filled_blocks; 39864565Sgshapiro 39964565Sgshapiro if (_Last - _First < static_cast<ptrdiff_t>(_Total_fixed_length)) { 40064565Sgshapiro return { _Last, errc::value_too_large }; 40164565Sgshapiro } 40238032Speter 40338032Speter char* _Result = _First; 40438032Speter 40538032Speter // Print _Data[0]. While it's up to 10 digits, 40638032Speter // which is more than Ryu generates, the code below can handle this. 40738032Speter __append_n_digits(_Data_olength, _Data[0], _Result); 40838032Speter _Result += _Data_olength; 40938032Speter 41038032Speter // Print 0-filled 9-digit blocks. 41138032Speter for (int32_t _Idx = _Filled_blocks - 1; _Idx >= 0; --_Idx) { 41238032Speter __append_nine_digits(_Blocks[_Idx], _Result); 41338032Speter _Result += 9; 41438032Speter } 41538032Speter 41638032Speter return { _Result, errc{} }; 41738032Speter} 41838032Speter 41938032Speter[[nodiscard]] _LIBCPP_HIDE_FROM_ABI inline to_chars_result __to_chars(char* const _First, char* const _Last, const __floating_decimal_32 __v, 42038032Speter chars_format _Fmt, const uint32_t __ieeeMantissa, const uint32_t __ieeeExponent) { 42138032Speter // Step 5: Print the decimal representation. 42238032Speter uint32_t _Output = __v.__mantissa; 42338032Speter int32_t _Ryu_exponent = __v.__exponent; 42438032Speter const uint32_t __olength = __decimalLength9(_Output); 42538032Speter int32_t _Scientific_exponent = _Ryu_exponent + static_cast<int32_t>(__olength) - 1; 42638032Speter 42738032Speter if (_Fmt == chars_format{}) { 42838032Speter int32_t _Lower; 42938032Speter int32_t _Upper; 43038032Speter 43138032Speter if (__olength == 1) { 43238032Speter // Value | Fixed | Scientific 43338032Speter // 1e-3 | "0.001" | "1e-03" 43438032Speter // 1e4 | "10000" | "1e+04" 43538032Speter _Lower = -3; 43638032Speter _Upper = 4; 43738032Speter } else { 43838032Speter // Value | Fixed | Scientific 43938032Speter // 1234e-7 | "0.0001234" | "1.234e-04" 44038032Speter // 1234e5 | "123400000" | "1.234e+08" 44138032Speter _Lower = -static_cast<int32_t>(__olength + 3); 44238032Speter _Upper = 5; 44338032Speter } 44438032Speter 44538032Speter if (_Lower <= _Ryu_exponent && _Ryu_exponent <= _Upper) { 44638032Speter _Fmt = chars_format::fixed; 44738032Speter } else { 44838032Speter _Fmt = chars_format::scientific; 44938032Speter } 45064565Sgshapiro } else if (_Fmt == chars_format::general) { 45138032Speter // C11 7.21.6.1 "The fprintf function"/8: 45238032Speter // "Let P equal [...] 6 if the precision is omitted [...]. 45338032Speter // Then, if a conversion with style E would have an exponent of X: 45438032Speter // - if P > X >= -4, the conversion is with style f [...]. 45538032Speter // - otherwise, the conversion is with style e [...]." 45638032Speter if (-4 <= _Scientific_exponent && _Scientific_exponent < 6) { 45738032Speter _Fmt = chars_format::fixed; 45838032Speter } else { 45938032Speter _Fmt = chars_format::scientific; 46038032Speter } 46138032Speter } 46238032Speter 46338032Speter if (_Fmt == chars_format::fixed) { 46438032Speter // Example: _Output == 1729, __olength == 4 46538032Speter 46638032Speter // _Ryu_exponent | Printed | _Whole_digits | _Total_fixed_length | Notes 46771348Sgshapiro // --------------|----------|---------------|----------------------|--------------------------------------- 46838032Speter // 2 | 172900 | 6 | _Whole_digits | Ryu can't be used for printing 46938032Speter // 1 | 17290 | 5 | (sometimes adjusted) | when the trimmed digits are nonzero. 47038032Speter // --------------|----------|---------------|----------------------|--------------------------------------- 47138032Speter // 0 | 1729 | 4 | _Whole_digits | Unified length cases. 47238032Speter // --------------|----------|---------------|----------------------|--------------------------------------- 47338032Speter // -1 | 172.9 | 3 | __olength + 1 | This case can't happen for 47438032Speter // -2 | 17.29 | 2 | | __olength == 1, but no additional 47538032Speter // -3 | 1.729 | 1 | | code is needed to avoid it. 47638032Speter // --------------|----------|---------------|----------------------|--------------------------------------- 47738032Speter // -4 | 0.1729 | 0 | 2 - _Ryu_exponent | C11 7.21.6.1 "The fprintf function"/8: 47838032Speter // -5 | 0.01729 | -1 | | "If a decimal-point character appears, 47938032Speter // -6 | 0.001729 | -2 | | at least one digit appears before it." 48038032Speter 48138032Speter const int32_t _Whole_digits = static_cast<int32_t>(__olength) + _Ryu_exponent; 48240498Sbde 48340498Sbde uint32_t _Total_fixed_length; 48440498Sbde if (_Ryu_exponent >= 0) { // cases "172900" and "1729" 48538032Speter _Total_fixed_length = static_cast<uint32_t>(_Whole_digits); 48638032Speter if (_Output == 1) { 48738032Speter // Rounding can affect the number of digits. 48838032Speter // For example, 1e11f is exactly "99999997952" which is 11 digits instead of 12. 48938032Speter // We can use a lookup table to detect this and adjust the total length. 49038032Speter static constexpr uint8_t _Adjustment[39] = { 49164565Sgshapiro 0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,1,1,0,0,1,0,1,1,0,1,1,1 }; 49238032Speter _Total_fixed_length -= _Adjustment[_Ryu_exponent]; 49338032Speter // _Whole_digits doesn't need to be adjusted because these cases won't refer to it later. 49438032Speter } 49538032Speter } else if (_Whole_digits > 0) { // case "17.29" 49638032Speter _Total_fixed_length = __olength + 1; 49738032Speter } else { // case "0.001729" 49838032Speter _Total_fixed_length = static_cast<uint32_t>(2 - _Ryu_exponent); 49938032Speter } 50038032Speter 50138032Speter if (_Last - _First < static_cast<ptrdiff_t>(_Total_fixed_length)) { 50238032Speter return { _Last, errc::value_too_large }; 50338032Speter } 50438032Speter 50538032Speter char* _Mid; 50638032Speter if (_Ryu_exponent > 0) { // case "172900" 50738032Speter bool _Can_use_ryu; 50838032Speter 50938032Speter if (_Ryu_exponent > 10) { // 10^10 is the largest power of 10 that's exactly representable as a float. 51064565Sgshapiro _Can_use_ryu = false; 51138032Speter } else { 51238032Speter // Ryu generated X: __v.__mantissa * 10^_Ryu_exponent 51338032Speter // __v.__mantissa == 2^_Trailing_zero_bits * (__v.__mantissa >> _Trailing_zero_bits) 51438032Speter // 10^_Ryu_exponent == 2^_Ryu_exponent * 5^_Ryu_exponent 51538032Speter 51638032Speter // _Trailing_zero_bits is [0, 29] (aside: because 2^29 is the largest power of 2 51738032Speter // with 9 decimal digits, which is float's round-trip limit.) 51838032Speter // _Ryu_exponent is [1, 10]. 51938032Speter // Normalization adds [2, 23] (aside: at least 2 because the pre-normalized mantissa is at least 5). 52038032Speter // This adds up to [3, 62], which is well below float's maximum binary exponent 127. 52138032Speter 52238032Speter // Therefore, we just need to consider (__v.__mantissa >> _Trailing_zero_bits) * 5^_Ryu_exponent. 52338032Speter 52438032Speter // If that product would exceed 24 bits, then X can't be exactly represented as a float. 52538032Speter // (That's not a problem for round-tripping, because X is close enough to the original float, 52638032Speter // but X isn't mathematically equal to the original float.) This requires a high-precision fallback. 52738032Speter 52838032Speter // If the product is 24 bits or smaller, then X can be exactly represented as a float (and we don't 52938032Speter // need to re-synthesize it; the original float must have been X, because Ryu wouldn't produce the 53038032Speter // same output for two different floats X and Y). This allows Ryu's output to be used (zero-filled). 53138032Speter 53238032Speter // (2^24 - 1) / 5^0 (for indexing), (2^24 - 1) / 5^1, ..., (2^24 - 1) / 5^10 53338032Speter static constexpr uint32_t _Max_shifted_mantissa[11] = { 53438032Speter 16777215, 3355443, 671088, 134217, 26843, 5368, 1073, 214, 42, 8, 1 }; 53538032Speter 53638032Speter unsigned long _Trailing_zero_bits; 53738032Speter (void) _BitScanForward(&_Trailing_zero_bits, __v.__mantissa); // __v.__mantissa is guaranteed nonzero 53838032Speter const uint32_t _Shifted_mantissa = __v.__mantissa >> _Trailing_zero_bits; 53938032Speter _Can_use_ryu = _Shifted_mantissa <= _Max_shifted_mantissa[_Ryu_exponent]; 54038032Speter } 54138032Speter 54238032Speter if (!_Can_use_ryu) { 54338032Speter const uint32_t _Mantissa2 = __ieeeMantissa | (1u << __FLOAT_MANTISSA_BITS); // restore implicit bit 54438032Speter const int32_t _Exponent2 = static_cast<int32_t>(__ieeeExponent) 54538032Speter - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS; // bias and normalization 54638032Speter 54738032Speter // Performance note: We've already called Ryu, so this will redundantly perform buffering and bounds checking. 54838032Speter return _Large_integer_to_chars(_First, _Last, _Mantissa2, _Exponent2); 54938032Speter } 55038032Speter 55138032Speter // _Can_use_ryu 55238032Speter // Print the decimal digits, left-aligned within [_First, _First + _Total_fixed_length). 55338032Speter _Mid = _First + __olength; 55438032Speter } else { // cases "1729", "17.29", and "0.001729" 55538032Speter // Print the decimal digits, right-aligned within [_First, _First + _Total_fixed_length). 55638032Speter _Mid = _First + _Total_fixed_length; 55738032Speter } 55838032Speter 55942580Speter while (_Output >= 10000) { 56038032Speter#ifdef __clang__ // TRANSITION, LLVM-38217 56138032Speter const uint32_t __c = _Output - 10000 * (_Output / 10000); 56238032Speter#else 56338032Speter const uint32_t __c = _Output % 10000; 56438032Speter#endif 56538032Speter _Output /= 10000; 56638032Speter const uint32_t __c0 = (__c % 100) << 1; 56738032Speter const uint32_t __c1 = (__c / 100) << 1; 56838032Speter std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c0, 2); 56938032Speter std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c1, 2); 57038032Speter } 57138032Speter if (_Output >= 100) { 57238032Speter const uint32_t __c = (_Output % 100) << 1; 57364565Sgshapiro _Output /= 100; 57438032Speter std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c, 2); 57538032Speter } 57638032Speter if (_Output >= 10) { 57738032Speter const uint32_t __c = _Output << 1; 57838032Speter std::memcpy(_Mid -= 2, __DIGIT_TABLE + __c, 2); 57938032Speter } else { 58038032Speter *--_Mid = static_cast<char>('0' + _Output); 58138032Speter } 58238032Speter 58338032Speter if (_Ryu_exponent > 0) { // case "172900" with _Can_use_ryu 58464565Sgshapiro // Performance note: it might be more efficient to do this immediately after setting _Mid. 58538032Speter std::memset(_First + __olength, '0', static_cast<size_t>(_Ryu_exponent)); 58638032Speter } else if (_Ryu_exponent == 0) { // case "1729" 58738032Speter // Done! 58838032Speter } else if (_Whole_digits > 0) { // case "17.29" 58938032Speter // Performance note: moving digits might not be optimal. 59038032Speter std::memmove(_First, _First + 1, static_cast<size_t>(_Whole_digits)); 59138032Speter _First[_Whole_digits] = '.'; 59238032Speter } else { // case "0.001729" 59338032Speter // Performance note: a larger memset() followed by overwriting '.' might be more efficient. 59464565Sgshapiro _First[0] = '0'; 59538032Speter _First[1] = '.'; 59638032Speter std::memset(_First + 2, '0', static_cast<size_t>(-_Whole_digits)); 59738032Speter } 59864565Sgshapiro 59938032Speter return { _First + _Total_fixed_length, errc{} }; 60064565Sgshapiro } 60138032Speter 60238032Speter const uint32_t _Total_scientific_length = 60338032Speter __olength + (__olength > 1) + 4; // digits + possible decimal point + scientific exponent 60438032Speter if (_Last - _First < static_cast<ptrdiff_t>(_Total_scientific_length)) { 60538032Speter return { _Last, errc::value_too_large }; 60664565Sgshapiro } 60738032Speter char* const __result = _First; 60838032Speter 60938032Speter // Print the decimal digits. 61038032Speter uint32_t __i = 0; 61138032Speter while (_Output >= 10000) { 61238032Speter#ifdef __clang__ // TRANSITION, LLVM-38217 61364565Sgshapiro const uint32_t __c = _Output - 10000 * (_Output / 10000); 61464565Sgshapiro#else 61538032Speter const uint32_t __c = _Output % 10000; 61638032Speter#endif 61738032Speter _Output /= 10000; 61838032Speter const uint32_t __c0 = (__c % 100) << 1; 61938032Speter const uint32_t __c1 = (__c / 100) << 1; 62038032Speter std::memcpy(__result + __olength - __i - 1, __DIGIT_TABLE + __c0, 2); 62164565Sgshapiro std::memcpy(__result + __olength - __i - 3, __DIGIT_TABLE + __c1, 2); 62238032Speter __i += 4; 62338032Speter } 62438032Speter if (_Output >= 100) { 62538032Speter const uint32_t __c = (_Output % 100) << 1; 62638032Speter _Output /= 100; 62738032Speter std::memcpy(__result + __olength - __i - 1, __DIGIT_TABLE + __c, 2); 62838032Speter __i += 2; 62938032Speter } 63038032Speter if (_Output >= 10) { 63138032Speter const uint32_t __c = _Output << 1; 63238032Speter // We can't use memcpy here: the decimal dot goes between these two digits. 63364565Sgshapiro __result[2] = __DIGIT_TABLE[__c + 1]; 63464565Sgshapiro __result[0] = __DIGIT_TABLE[__c]; 63564565Sgshapiro } else { 63638032Speter __result[0] = static_cast<char>('0' + _Output); 63738032Speter } 63838032Speter 63938032Speter // Print decimal point if needed. 64038032Speter uint32_t __index; 64138032Speter if (__olength > 1) { 64264565Sgshapiro __result[1] = '.'; 64338032Speter __index = __olength + 1; 64438032Speter } else { 64564565Sgshapiro __index = 1; 64638032Speter } 64738032Speter 64838032Speter // Print the exponent. 64938032Speter __result[__index++] = 'e'; 65038032Speter if (_Scientific_exponent < 0) { 65138032Speter __result[__index++] = '-'; 65238032Speter _Scientific_exponent = -_Scientific_exponent; 65338032Speter } else { 65438032Speter __result[__index++] = '+'; 65538032Speter } 65638032Speter 65738032Speter std::memcpy(__result + __index, __DIGIT_TABLE + 2 * _Scientific_exponent, 2); 65838032Speter __index += 2; 65938032Speter 66038032Speter return { _First + _Total_scientific_length, errc{} }; 66138032Speter} 66238032Speter 66338032Speter[[nodiscard]] to_chars_result __f2s_buffered_n(char* const _First, char* const _Last, const float __f, 66438032Speter const chars_format _Fmt) { 66564565Sgshapiro 66638032Speter // Step 1: Decode the floating-point number, and unify normalized and subnormal cases. 66738032Speter const uint32_t __bits = __float_to_bits(__f); 66838032Speter 66938032Speter // Case distinction; exit early for the easy cases. 67064565Sgshapiro if (__bits == 0) { 67138032Speter if (_Fmt == chars_format::scientific) { 67238032Speter if (_Last - _First < 5) { 67338032Speter return { _Last, errc::value_too_large }; 67438032Speter } 67538032Speter 67638032Speter std::memcpy(_First, "0e+00", 5); 67738032Speter 67838032Speter return { _First + 5, errc{} }; 67938032Speter } 68064565Sgshapiro 68138032Speter // Print "0" for chars_format::fixed, chars_format::general, and chars_format{}. 68238032Speter if (_First == _Last) { 68338032Speter return { _Last, errc::value_too_large }; 68438032Speter } 68564565Sgshapiro 68638032Speter *_First = '0'; 68738032Speter 68838032Speter return { _First + 1, errc{} }; 68938032Speter } 69038032Speter 69138032Speter // Decode __bits into mantissa and exponent. 69264565Sgshapiro const uint32_t __ieeeMantissa = __bits & ((1u << __FLOAT_MANTISSA_BITS) - 1); 69338032Speter const uint32_t __ieeeExponent = __bits >> __FLOAT_MANTISSA_BITS; 69438032Speter 69538032Speter // When _Fmt == chars_format::fixed and the floating-point number is a large integer, 69664565Sgshapiro // it's faster to skip Ryu and immediately print the integer exactly. 69738032Speter if (_Fmt == chars_format::fixed) { 69838032Speter const uint32_t _Mantissa2 = __ieeeMantissa | (1u << __FLOAT_MANTISSA_BITS); // restore implicit bit 69942580Speter const int32_t _Exponent2 = static_cast<int32_t>(__ieeeExponent) 70038032Speter - __FLOAT_BIAS - __FLOAT_MANTISSA_BITS; // bias and normalization 70138032Speter 70238032Speter // Normal values are equal to _Mantissa2 * 2^_Exponent2. 70338032Speter // (Subnormals are different, but they'll be rejected by the _Exponent2 test here, so they can be ignored.) 70438032Speter 70538032Speter if (_Exponent2 > 0) { 70638032Speter return _Large_integer_to_chars(_First, _Last, _Mantissa2, _Exponent2); 70738032Speter } 70838032Speter } 70938032Speter 71038032Speter const __floating_decimal_32 __v = __f2d(__ieeeMantissa, __ieeeExponent); 71138032Speter return __to_chars(_First, _Last, __v, _Fmt, __ieeeMantissa, __ieeeExponent); 71238032Speter} 71364565Sgshapiro 71438032Speter_LIBCPP_END_NAMESPACE_STD 71538032Speter 71638032Speter// clang-format on 71764565Sgshapiro