summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTanner Gooding <tagoo@outlook.com>2019-02-01 11:58:35 -0800
committerGitHub <noreply@github.com>2019-02-01 11:58:35 -0800
commita21b1513db19eb6e77ab71843b8f0e046eb88933 (patch)
treeff67c0e47b901d2a2cc85108e081c4847543ba38
parentd7c49329ad75e160460ddb32f18d150c072a8002 (diff)
downloadcoreclr-a21b1513db19eb6e77ab71843b8f0e046eb88933.tar.gz
coreclr-a21b1513db19eb6e77ab71843b8f0e046eb88933.tar.bz2
coreclr-a21b1513db19eb6e77ab71843b8f0e046eb88933.zip
Update the double/float formatters to return the shortest roundtrippable string. (#22040)
* Updating Number.Formatting to always compute a round-trippable number by default. * Adding a third-party notice entry for the Grisu3 reference implementation * Fixing up the Grisu3 algorithm to better match the reference implementation (including comments, etc) * Porting the Grisu3 implementation that generates the shortest roundtrippable sequence. * Updating the Dragon4 algorithm to support printing the shortest roundtrippable string. * Fixing the double/float formatters to ignore precision specifiers for 'R' * Fixing the double/float formatters to handle +0.0 and -0.0 * Fix the casing of `point` in THIRD-PARTY-NOTICES Co-Authored-By: tannergooding <tagoo@outlook.com> * Fixing the double/float formatting code to consider a precision specifier of 0 to be the same as default. * Fixing the double/float formatter so that nMaxDigits is set appropriately. * Changing the double/float formatting logic to account for the format when determining the correct precision to request. * Updating the double/float formatter to take the format specifier into account when determining the number of digits to request. * Fixing the double/float formatting code to continue handling zero correctly. * Disabling some outdated CoreFX tests. * Responding to various feedback from the PR
-rw-r--r--THIRD-PARTY-NOTICES.TXT34
-rw-r--r--src/System.Private.CoreLib/shared/System/Number.BigInteger.cs85
-rw-r--r--src/System.Private.CoreLib/shared/System/Number.DiyFp.cs201
-rw-r--r--src/System.Private.CoreLib/shared/System/Number.Dragon4.cs566
-rw-r--r--src/System.Private.CoreLib/shared/System/Number.Formatting.cs370
-rw-r--r--src/System.Private.CoreLib/shared/System/Number.Grisu3.cs971
-rw-r--r--tests/CoreFX/CoreFX.issues.json167
7 files changed, 1634 insertions, 760 deletions
diff --git a/THIRD-PARTY-NOTICES.TXT b/THIRD-PARTY-NOTICES.TXT
index 4a8002db25..831105f181 100644
--- a/THIRD-PARTY-NOTICES.TXT
+++ b/THIRD-PARTY-NOTICES.TXT
@@ -197,7 +197,9 @@ LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-License notice for the Printing Floating-Point Numbers
+License notice for Printing Floating-Point Numbers (Dragon4)
+------------------------------------------------------------
+
/******************************************************************************
Copyright (c) 2014 Ryan Juckett
http://www.ryanjuckett.com/
@@ -222,6 +224,36 @@ License notice for the Printing Floating-Point Numbers
distribution.
******************************************************************************/
+License notice for Printing Floating-point Numbers (Grisu3)
+-----------------------------------------------------------
+
+Copyright 2012 the V8 project authors. All rights reserved.
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the above
+ copyright notice, this list of conditions and the following
+ disclaimer in the documentation and/or other materials provided
+ with the distribution.
+ * Neither the name of Google Inc. nor the names of its
+ contributors may be used to endorse or promote products derived
+ from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
License notice for xxHash
-------------------------
diff --git a/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs b/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs
index 2d61d53285..0521e2c53d 100644
--- a/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs
+++ b/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs
@@ -372,6 +372,59 @@ namespace System
}
}
+ public static void Add(ref BigInteger lhs, ref BigInteger rhs, out BigInteger result)
+ {
+ // determine which operand has the smaller length
+ ref BigInteger large = ref (lhs._length < rhs._length) ? ref rhs : ref lhs;
+ ref BigInteger small = ref (lhs._length < rhs._length) ? ref lhs : ref rhs;
+
+ int largeLength = large._length;
+ int smallLength = small._length;
+
+ // The output will be at least as long as the largest input
+ result = new BigInteger(0);
+ result._length = largeLength;
+
+ // Add each block and add carry the overflow to the next block
+ ulong carry = 0;
+
+ int largeIndex = 0;
+ int smallIndex = 0;
+ int resultIndex = 0;
+
+ while (smallIndex < smallLength)
+ {
+ ulong sum = carry + large._blocks[largeIndex] + small._blocks[smallIndex];
+ carry = sum >> 32;
+ result._blocks[resultIndex] = (uint)(sum);
+
+ largeIndex++;
+ smallIndex++;
+ resultIndex++;
+ }
+
+ // Add the carry to any blocks that only exist in the large operand
+ while (largeIndex < largeLength)
+ {
+ ulong sum = carry + large._blocks[largeIndex];
+ carry = sum >> 32;
+ result._blocks[resultIndex] = (uint)(sum);
+
+ largeIndex++;
+ resultIndex++;
+ }
+
+ // If there's still a carry, append a new block
+ if (carry != 0)
+ {
+ Debug.Assert(carry == 1);
+ Debug.Assert((resultIndex == largeLength) && (largeLength < MaxBlockCount));
+
+ result._blocks[resultIndex] = 1;
+ result._length += 1;
+ }
+ }
+
public static int Compare(ref BigInteger lhs, ref BigInteger rhs)
{
Debug.Assert(unchecked((uint)(lhs._length)) <= MaxBlockCount);
@@ -849,6 +902,12 @@ namespace System
}
}
+ public static void Pow2(uint exponent, out BigInteger result)
+ {
+ result = new BigInteger(0);
+ ShiftLeft(1, exponent, ref result);
+ }
+
public static void Pow10(uint exponent, out BigInteger result)
{
// We leverage two arrays - s_Pow10UInt32Table and s_Pow10BigNumTable to speed up the Pow10 calculation.
@@ -917,27 +976,6 @@ namespace System
result.SetValue(ref lhs);
}
- public static void PrepareHeuristicDivide(ref BigInteger dividend, ref BigInteger divisor)
- {
- uint hiBlock = divisor._blocks[divisor._length - 1];
-
- if ((hiBlock < 8) || (hiBlock > 429496729))
- {
- // Inspired by http://www.ryanjuckett.com/programming/printing-floating-point-numbers/
- // Perform a bit shift on all values to get the highest block of the divisor into
- // the range [8,429496729]. We are more likely to make accurate quotient estimations
- // in heuristicDivide() with higher divisor values so
- // we shift the divisor to place the highest bit at index 27 of the highest block.
- // This is safe because (2^28 - 1) = 268435455 which is less than 429496729. This means
- // that all values with a highest bit at index 27 are within range.
- uint hiBlockLog2 = LogBase2(hiBlock);
- uint shift = (59 - hiBlockLog2) % 32;
-
- divisor.ShiftLeft(shift);
- dividend.ShiftLeft(shift);
- }
- }
-
public static void ShiftLeft(ulong input, uint shift, ref BigInteger output)
{
if (shift == 0)
@@ -1111,6 +1149,11 @@ namespace System
return _blocks[index];
}
+ public int GetLength()
+ {
+ return _length;
+ }
+
public bool IsOne()
{
return (_length == 1)
diff --git a/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs b/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs
index c6cab0d0b4..5e20b8e9f4 100644
--- a/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs
+++ b/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs
@@ -8,110 +8,84 @@ namespace System
{
internal static partial class Number
{
- // An exteneded floating-point data structure which is required by Grisu3 algorithm.
- // It defines a 64-bit significand and a 32-bit exponent,
- // which is EXTENDED compare to IEEE double precision floating-point number (53 bits significand and 11 bits exponent).
- //
- // Original Grisu algorithm produces suboptimal results. To shorten the output (which is part of Grisu2/Grisu3's job),
- // we need additional 11 bits of the significand f and larger exponent e (A larger exponent range is used to avoid overflow. A 32-bit exponent is far big enough).
- // To fully understand how Grisu3 uses this data structure to get better result, please read http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf
- internal struct DiyFp
+ // This is a port of the `DiyFp` implementation here: https://github.com/google/double-conversion/blob/a711666ddd063eb1e4b181a6cb981d39a1fc8bac/double-conversion/diy-fp.h
+ // The backing structure and how it is used is described in more detail here: http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf
+
+ // This "Do It Yourself Floating Point" class implements a floating-point number with a ulong significand and an int exponent.
+ // Normalized DiyFp numbers will have the most significant bit of the significand set.
+ // Multiplication and Subtraction do not normalize their results.
+ // DiyFp are not designed to contain special doubles (NaN and Infinity).
+ internal readonly ref struct DiyFp
{
- public const int SignificandLength = 64;
-
- // Extended significand.
- // IEEE 754 double-precision numbers only require 53 bits significand.
- // However, in Grisu3 we need additional 11 bits so we declare _f as ulong.
- // Please note _f does not include sign bit.
- private ulong _f;
-
- // Extended exponent.
- // IEEE 754 double-precision numbers only require 11 bits exponent.
- // However, in Grisu3 we need extra space to avoid overflow so we declare _e as int.
- // Please note _e is a biased exponent if the DiyFp instance is generated by GenerateNormalizedDiyFp().
- private int _e;
-
- public DiyFp(ulong f, int e)
+ public const int DoubleImplicitBitIndex = 52;
+ public const int SingleImplicitBitIndex = 23;
+
+ public const int SignificandSize = 64;
+
+ public readonly ulong f;
+ public readonly int e;
+
+ // Computes the two boundaries of value.
+ //
+ // The bigger boundary (mPlus) is normalized.
+ // The lower boundary has the same exponent as mPlus.
+ //
+ // Precondition:
+ // The value encoded by value must be greater than 0.
+ public static DiyFp CreateAndGetBoundaries(double value, out DiyFp mMinus, out DiyFp mPlus)
{
- _f = f;
- _e = e;
- }
-
- public ulong f
- {
- get
- {
- return _f;
- }
-
- set
- {
- _f = value;
- }
+ var result = new DiyFp(value);
+ result.GetBoundaries(DoubleImplicitBitIndex, out mMinus, out mPlus);
+ return result;
}
- public int e
+ // Computes the two boundaries of value.
+ //
+ // The bigger boundary (mPlus) is normalized.
+ // The lower boundary has the same exponent as mPlus.
+ //
+ // Precondition:
+ // The value encoded by value must be greater than 0.
+ public static DiyFp CreateAndGetBoundaries(float value, out DiyFp mMinus, out DiyFp mPlus)
{
- get
- {
- return _e;
- }
-
- set
- {
- _e = value;
- }
+ var result = new DiyFp(value);
+ result.GetBoundaries(SingleImplicitBitIndex, out mMinus, out mPlus);
+ return result;
}
- public static void GenerateNormalizedDiyFp(double value, out DiyFp result)
+ public DiyFp(double value)
{
+ Debug.Assert(double.IsFinite(value));
Debug.Assert(value > 0.0);
-
- long f = ExtractFractionAndBiasedExponent(value, out int e);
-
- while ((f & (1L << 52)) == 0)
- {
- f <<= 1;
- e--;
- }
-
- int lengthDelta = (SignificandLength - 53);
- f <<= lengthDelta;
- e -= lengthDelta;
-
- result = new DiyFp((ulong)(f), e);
- }
-
- public static void Minus(ref DiyFp lhs, ref DiyFp rhs, out DiyFp result)
- {
- result = lhs;
- result.Minus(ref rhs);
+ f = ExtractFractionAndBiasedExponent(value, out e);
}
- public static void Multiply(ref DiyFp lhs, ref DiyFp rhs, out DiyFp result)
+ public DiyFp(float value)
{
- result = lhs;
- result.Multiply(ref rhs);
+ Debug.Assert(float.IsFinite(value));
+ Debug.Assert(value > 0.0f);
+ f = ExtractFractionAndBiasedExponent(value, out e);
}
- public void Minus(ref DiyFp rhs)
+ public DiyFp(ulong f, int e)
{
- Debug.Assert(_e == rhs._e);
- Debug.Assert(_f >= rhs._f);
-
- _f -= rhs._f;
+ this.f = f;
+ this.e = e;
}
- public void Multiply(ref DiyFp rhs)
+ public DiyFp Multiply(in DiyFp other)
{
- ulong lf = _f;
- ulong rf = rhs._f;
+ // Simply "emulates" a 128-bit multiplication
+ //
+ // However: the resulting number only contains 64-bits. The least
+ // signficant 64-bits are only used for rounding the most significant
+ // 64-bits.
- uint a = (uint)(lf >> 32);
- uint b = (uint)(lf);
+ uint a = (uint)(f >> 32);
+ uint b = (uint)(f);
- uint c = (uint)(rf >> 32);
- uint d = (uint)(rf);
+ uint c = (uint)(other.f >> 32);
+ uint d = (uint)(other.f);
ulong ac = ((ulong)(a) * c);
ulong bc = ((ulong)(b) * c);
@@ -119,10 +93,63 @@ namespace System
ulong bd = ((ulong)(b) * d);
ulong tmp = (bd >> 32) + (uint)(ad) + (uint)(bc);
- tmp += (1UL << 31);
- _f = ac + (ad >> 32) + (bc >> 32) + (tmp >> 32);
- _e += (rhs._e + SignificandLength);
+ // By adding (1UL << 31) to tmp, we round the final result.
+ // Halfway cases will be rounded up.
+
+ tmp += (1U << 31);
+
+ return new DiyFp((ac + (ad >> 32) + (bc >> 32) + (tmp >> 32)), (e + other.e + SignificandSize));
+ }
+
+ public DiyFp Normalize()
+ {
+ // This method is mainly called for normalizing boundaries.
+ //
+ // We deviate from the reference implementation by just using
+ // our LeadingZeroCount function so that we only need to shift
+ // and subtract once.
+
+ Debug.Assert(f != 0);
+ int lzcnt = (int)(BigInteger.LeadingZeroCount(f));
+ return new DiyFp((f << lzcnt), (e - lzcnt));
+ }
+
+ // The exponents of both numbers must be the same.
+ // The significand of 'this' must be bigger than the significand of 'other'.
+ // The result will not be normalized.
+ public DiyFp Subtract(in DiyFp other)
+ {
+ Debug.Assert(e == other.e);
+ Debug.Assert(f >= other.f);
+ return new DiyFp((f - other.f), e);
+ }
+
+ private void GetBoundaries(int implicitBitIndex, out DiyFp mMinus, out DiyFp mPlus)
+ {
+ mPlus = new DiyFp(((f << 1) + 1), (e - 1)).Normalize();
+
+ // The boundary is closer if the sigificand is of the form:
+ // f == 2^p-1
+ //
+ // Think of v = 1000e10 and v- = 9999e9
+ // Then the boundary == (v - v-) / 2 is not just at a distance of 1e9 but at a distance of 1e8.
+ // The only exception is for the smallest normal, where the largest denormal is at the same distance as its successor.
+ //
+ // Note: denormals have the same exponent as the smallest normals.
+
+ // We deviate from the reference implementation by just checking if the significand has only the implicit bit set.
+ // In this scenario, we know that all the explicit bits are 0 and that the unbiased exponent is non-zero.
+ if (f == (1UL << implicitBitIndex))
+ {
+ mMinus = new DiyFp(((f << 2) - 1), (e - 2));
+ }
+ else
+ {
+ mMinus = new DiyFp(((f << 1) - 1), (e - 1));
+ }
+
+ mMinus = new DiyFp((mMinus.f << (mMinus.e - mPlus.e)), mPlus.e);
}
}
}
diff --git a/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs b/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs
index 67c9082216..5fa812c8f5 100644
--- a/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs
+++ b/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs
@@ -2,253 +2,453 @@
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
+using System.Diagnostics;
+using Internal.Runtime.CompilerServices;
+
namespace System
{
+ // This is a port of the `Dragon4` implementation here: http://www.ryanjuckett.com/programming/printing-floating-point-numbers/part-2/
+ // The backing algorithm and the proofs behind it are described in more detail here: https://www.cs.indiana.edu/~dyb/pubs/FP-Printing-PLDI96.pdf
internal static partial class Number
{
- private static unsafe void Dragon4(double value, int precision, ref NumberBuffer number)
+ public static void Dragon4Double(double value, int cutoffNumber, bool isSignificantDigits, ref NumberBuffer number)
{
- const double Log10V2 = 0.30102999566398119521373889472449;
+ double v = double.IsNegative(value) ? -value : value;
- // DriftFactor = 1 - Log10V2 - epsilon (a small number account for drift of floating point multiplication)
- const double DriftFactor = 0.69;
+ Debug.Assert(v > 0);
+ Debug.Assert(double.IsFinite(v));
- // ========================================================================================================================================
- // This implementation is based on the paper: https://www.cs.indiana.edu/~dyb/pubs/FP-Printing-PLDI96.pdf
- // Besides the paper, some of the code and ideas are modified from http://www.ryanjuckett.com/programming/printing-floating-point-numbers/
- // You must read these two materials to fully understand the code.
- //
- // Note: we only support fixed format input.
- // ========================================================================================================================================
- //
- // Overview:
- //
- // The input double number can be represented as:
- // value = f * 2^e = r / s.
- //
- // f: the output mantissa. Note: f is not the 52 bits mantissa of the input double number.
- // e: biased exponent.
- // r: numerator.
- // s: denominator.
- // k: value = d0.d1d2 . . . dn * 10^k
-
- // Step 1:
- // Extract meta data from the input double value.
- //
- // Refer to IEEE double precision floating point format.
- ulong f = (ulong)(ExtractFractionAndBiasedExponent(value, out int e));
- int mantissaHighBitIndex = (e == -1074) ? (int)(BigInteger.LogBase2(f)) : 52;
+ ulong mantissa = ExtractFractionAndBiasedExponent(value, out int exponent);
- // Step 2:
- // Estimate k. We'll verify it and fix any error later.
- //
- // This is an improvement of the estimation in the original paper.
- // Inspired by http://www.ryanjuckett.com/programming/printing-floating-point-numbers/
- //
- // LOG10V2 = 0.30102999566398119521373889472449
- // DRIFT_FACTOR = 0.69 = 1 - log10V2 - epsilon (a small number account for drift of floating point multiplication)
- int k = (int)(Math.Ceiling(((mantissaHighBitIndex + e) * Log10V2) - DriftFactor));
+ uint mantissaHighBitIdx = 0;
+ bool hasUnequalMargins = false;
- // Step 3:
- // Store the input double value in BigInteger format.
- //
- // To keep the precision, we represent the double value as r/s.
- // We have several optimization based on following table in the paper.
- //
- // ----------------------------------------------------------------------------------------------------------
- // | e >= 0 | e < 0 |
- // ----------------------------------------------------------------------------------------------------------
- // | f != b^(P - 1) | f = b^(P - 1) | e = min exp or f != b^(P - 1) | e > min exp and f = b^(P - 1) |
- // --------------------------------------------------------------------------------------------------------------
- // | r | f * b^e * 2 | f * b^(e + 1) * 2 | f * 2 | f * b * 2 |
- // --------------------------------------------------------------------------------------------------------------
- // | s | 2 | b * 2 | b^(-e) * 2 | b^(-e + 1) * 2 |
- // --------------------------------------------------------------------------------------------------------------
- //
- // Note, we do not need m+ and m- because we only support fixed format input here.
- // m+ and m- are used for free format input, which need to determine the exact range of values
- // that would round to value when input so that we can generate the shortest correct number.digits.
- //
- // In our case, we just output number.digits until reaching the expected precision.
+ if ((mantissa >> DiyFp.DoubleImplicitBitIndex) != 0)
+ {
+ mantissaHighBitIdx = DiyFp.DoubleImplicitBitIndex;
+ hasUnequalMargins = (mantissa == (1UL << DiyFp.DoubleImplicitBitIndex));
+ }
+ else
+ {
+ mantissaHighBitIdx = BigInteger.LogBase2(mantissa);
+ }
+
+ int length = (int)(Dragon4(mantissa, exponent, mantissaHighBitIdx, hasUnequalMargins, cutoffNumber, isSignificantDigits, number.Digits, out int decimalExponent));
- var r = new BigInteger(f);
- var s = new BigInteger(0);
+ number.Scale = decimalExponent + 1;
+ number.Digits[length] = (byte)('\0');
+ number.DigitsCount = length;
+ }
+
+ public static unsafe void Dragon4Single(float value, int cutoffNumber, bool isSignificantDigits, ref NumberBuffer number)
+ {
+ float v = float.IsNegative(value) ? -value : value;
- if (e >= 0)
+ Debug.Assert(v > 0);
+ Debug.Assert(float.IsFinite(v));
+
+ uint mantissa = ExtractFractionAndBiasedExponent(value, out int exponent);
+
+ uint mantissaHighBitIdx = 0;
+ bool hasUnequalMargins = false;
+
+ if ((mantissa >> DiyFp.SingleImplicitBitIndex) != 0)
{
- // When f != b^(P - 1):
- // r = f * b^e * 2
- // s = 2
- // value = r / s = f * b^e * 2 / 2 = f * b^e / 1
- //
- // When f = b^(P - 1):
- // r = f * b^(e + 1) * 2
- // s = b * 2
- // value = r / s = f * b^(e + 1) * 2 / b * 2 = f * b^e / 1
- //
- // Therefore, we can simply say that when e >= 0:
- // r = f * b^e = f * 2^e
- // s = 1
+ mantissaHighBitIdx = DiyFp.SingleImplicitBitIndex;
+ hasUnequalMargins = (mantissa == (1U << DiyFp.SingleImplicitBitIndex));
+ }
+ else
+ {
+ mantissaHighBitIdx = BigInteger.LogBase2(mantissa);
+ }
+
+ int length = (int)(Dragon4(mantissa, exponent, mantissaHighBitIdx, hasUnequalMargins, cutoffNumber, isSignificantDigits, number.Digits, out int decimalExponent));
+
+ number.Scale = decimalExponent + 1;
+ number.Digits[length] = (byte)('\0');
+ number.DigitsCount = length;
+ }
- r.ShiftLeft((uint)(e));
- s.SetUInt64(1);
+ // This is an implementation of the Dragon4 algorithm to convert a binary number in floating-point format to a decimal number in string format.
+ // The function returns the number of digits written to the output buffer and the output is not NUL terminated.
+ //
+ // The floating point input value is (mantissa * 2^exponent).
+ //
+ // See the following papers for more information on the algorithm:
+ // "How to Print Floating-Point Numbers Accurately"
+ // Steele and White
+ // http://kurtstephens.com/files/p372-steele.pdf
+ // "Printing Floating-Point Numbers Quickly and Accurately"
+ // Burger and Dybvig
+ // http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4656&rep=rep1&type=pdf
+ private static unsafe uint Dragon4(ulong mantissa, int exponent, uint mantissaHighBitIdx, bool hasUnequalMargins, int cutoffNumber, bool isSignificantDigits, Span<byte> buffer, out int decimalExponent)
+ {
+ int curDigit = 0;
+
+ Debug.Assert(buffer.Length > 0);
+
+ // We deviate from the original algorithm and just assert that the mantissa
+ // is not zero. Comparing to zero is fine since the caller should have set
+ // the implicit bit of the mantissa, meaning it would only ever be zero if
+ // the extracted exponent was also zero. And the assertion is fine since we
+ // require that the DoubleToNumber handle zero itself.
+ Debug.Assert(mantissa != 0);
+
+ // Compute the initial state in integral form such that
+ // value = scaledValue / scale
+ // marginLow = scaledMarginLow / scale
+
+ BigInteger scale; // positive scale applied to value and margin such that they can be represented as whole numbers
+ BigInteger scaledValue; // scale * mantissa
+ BigInteger scaledMarginLow; // scale * 0.5 * (distance between this floating-point number and its immediate lower value)
+
+ // For normalized IEEE floating-point values, each time the exponent is incremented the margin also doubles.
+ // That creates a subset of transition numbers where the high margin is twice the size of the low margin.
+ BigInteger* pScaledMarginHigh;
+ BigInteger optionalMarginHigh;
+
+ if (hasUnequalMargins)
+ {
+ if (exponent > 0) // We have no fractional component
+ {
+ // 1) Expand the input value by multiplying out the mantissa and exponent.
+ // This represents the input value in its whole number representation.
+ // 2) Apply an additional scale of 2 such that later comparisons against the margin values are simplified.
+ // 3) Set the margin value to the loweset mantissa bit's scale.
+
+ // scaledValue = 2 * 2 * mantissa * 2^exponent
+ scaledValue = new BigInteger(4 * mantissa);
+ scaledValue.ShiftLeft((uint)(exponent));
+
+ // scale = 2 * 2 * 1
+ scale = new BigInteger(4);
+
+ // scaledMarginLow = 2 * 2^(exponent - 1)
+ BigInteger.Pow2((uint)(exponent), out scaledMarginLow);
+
+ // scaledMarginHigh = 2 * 2 * 2^(exponent + 1)
+ BigInteger.Pow2((uint)(exponent + 1), out optionalMarginHigh);
+ }
+ else // We have a fractional exponent
+ {
+ // In order to track the mantissa data as an integer, we store it as is with a large scale
+
+ // scaledValue = 2 * 2 * mantissa
+ scaledValue = new BigInteger(4 * mantissa);
+
+ // scale = 2 * 2 * 2^(-exponent)
+ BigInteger.Pow2((uint)(-exponent + 2), out scale);
+
+ // scaledMarginLow = 2 * 2^(-1)
+ scaledMarginLow = new BigInteger(1);
+
+ // scaledMarginHigh = 2 * 2 * 2^(-1)
+ optionalMarginHigh = new BigInteger(2);
+ }
+
+ // The high and low margins are different
+ pScaledMarginHigh = &optionalMarginHigh;
}
else
{
- // When e = min exp or f != b^(P - 1):
- // r = f * 2
- // s = b^(-e) * 2
- // value = r / s = f * 2 / b^(-e) * 2 = f / b^(-e)
- //
- // When e > min exp and f = b^(P - 1):
- // r = f * b * 2
- // s = b^(-e + 1) * 2
- // value = r / s = f * b * 2 / b^(-e + 1) * 2 = f / b^(-e)
- //
- // Therefore, we can simply say that when e < 0:
- // r = f
- // s = b^(-e) = 2^(-e)
+ if (exponent > 0) // We have no fractional component
+ {
+ // 1) Expand the input value by multiplying out the mantissa and exponent.
+ // This represents the input value in its whole number representation.
+ // 2) Apply an additional scale of 2 such that later comparisons against the margin values are simplified.
+ // 3) Set the margin value to the lowest mantissa bit's scale.
+
+ // scaledValue = 2 * mantissa*2^exponent
+ scaledValue = new BigInteger(2 * mantissa);
+ scaledValue.ShiftLeft((uint)(exponent));
+
+ // scale = 2 * 1
+ scale = new BigInteger(2);
- BigInteger.ShiftLeft(1, (uint)(-e), ref s);
+ // scaledMarginLow = 2 * 2^(exponent-1)
+ BigInteger.Pow2((uint)(exponent), out scaledMarginLow);
+ }
+ else // We have a fractional exponent
+ {
+ // In order to track the mantissa data as an integer, we store it as is with a large scale
+
+ // scaledValue = 2 * mantissa
+ scaledValue = new BigInteger(2 * mantissa);
+
+ // scale = 2 * 2^(-exponent)
+ BigInteger.Pow2((uint)(-exponent + 1), out scale);
+
+ // scaledMarginLow = 2 * 2^(-1)
+ scaledMarginLow = new BigInteger(1);
+ }
+
+ // The high and low margins are equal
+ pScaledMarginHigh = &scaledMarginLow;
}
- // According to the paper, we should use k >= 0 instead of k > 0 here.
- // However, if k = 0, both r and s won't be changed, we don't need to do any operation.
+ // Compute an estimate for digitExponent that will be correct or undershoot by one.
//
- // Following are the Scheme code from the paper:
- // --------------------------------------------------------------------------------
- // (if (>= est 0)
- // (fixup r (* s (exptt B est)) m+ m− est B low-ok? high-ok? )
- // (let ([scale (exptt B (− est))])
- // (fixup (* r scale) s (* m+ scale) (* m− scale) est B low-ok? high-ok? ))))
- // --------------------------------------------------------------------------------
+ // This optimization is based on the paper "Printing Floating-Point Numbers Quickly and Accurately" by Burger and Dybvig http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.72.4656&rep=rep1&type=pdf
//
- // If est is 0, (* s (exptt B est)) = s, (* r scale) = (* r (exptt B (− est)))) = r.
+ // We perform an additional subtraction of 0.69 to increase the frequency of a failed estimate because that lets us take a faster branch in the code.
+ // 0.69 is chosen because 0.69 + log10(2) is less than one by a reasonable epsilon that will account for any floating point error.
//
- // So we just skip when k = 0.
+ // We want to set digitExponent to floor(log10(v)) + 1
+ // v = mantissa * 2^exponent
+ // log2(v) = log2(mantissa) + exponent;
+ // log10(v) = log2(v) * log10(2)
+ // floor(log2(v)) = mantissaHighBitIdx + exponent;
+ // log10(v) - log10(2) < (mantissaHighBitIdx + exponent) * log10(2) <= log10(v)
+ // log10(v) < (mantissaHighBitIdx + exponent) * log10(2) + log10(2) <= log10(v) + log10(2)
+ // floor(log10(v)) < ceil((mantissaHighBitIdx + exponent) * log10(2)) <= floor(log10(v)) + 1
+ const double Log10V2 = 0.30102999566398119521373889472449;
+ int digitExponent = (int)(Math.Ceiling(((int)(mantissaHighBitIdx) + exponent) * Log10V2 - 0.69));
- if (k > 0)
+ // Divide value by 10^digitExponent.
+ if (digitExponent > 0)
{
- s.MultiplyPow10((uint)(k));
+ // The exponent is positive creating a division so we multiply up the scale.
+ scale.MultiplyPow10((uint)(digitExponent));
}
- else if (k < 0)
+ else if (digitExponent < 0)
{
- r.MultiplyPow10((uint)(-k));
+ // The exponent is negative creating a multiplication so we multiply up the scaledValue, scaledMarginLow and scaledMarginHigh.
+
+ BigInteger.Pow10((uint)(-digitExponent), out BigInteger pow10);
+
+ scaledValue.Multiply(ref pow10);
+ scaledMarginLow.Multiply(ref pow10);
+
+ if (pScaledMarginHigh != &scaledMarginLow)
+ {
+ BigInteger.Multiply(ref scaledMarginLow, 2, ref *pScaledMarginHigh);
+ }
}
- if (BigInteger.Compare(ref r, ref s) >= 0)
+ // If (value >= 1), our estimate for digitExponent was too low
+ if (BigInteger.Compare(ref scaledValue, ref scale) >= 0)
{
- // The estimation was incorrect. Fix the error by increasing 1.
- k += 1;
+ // The exponent estimate was incorrect.
+ // Increment the exponent and don't perform the premultiply needed for the first loop iteration.
+ digitExponent = digitExponent + 1;
}
else
{
- r.Multiply10();
- }
-
- number.Scale = (k - 1);
+ // The exponent estimate was correct.
+ // Multiply larger by the output base to prepare for the first loop iteration.
+ scaledValue.Multiply10();
+ scaledMarginLow.Multiply10();
- // This the prerequisite of calling BigInteger.HeuristicDivide().
- BigInteger.PrepareHeuristicDivide(ref r, ref s);
-
- // Step 4:
- // Calculate number.digits.
- //
- // Output number.digits until reaching the last but one precision or the numerator becomes zero.
+ if (pScaledMarginHigh != &scaledMarginLow)
+ {
+ BigInteger.Multiply(ref scaledMarginLow, 2, ref *pScaledMarginHigh);
+ }
+ }
- int digitsNum = 0;
- int currentDigit = 0;
+ // Compute the cutoff exponent (the exponent of the final digit to print).
+ // Default to the maximum size of the output buffer.
+ int cutoffExponent = digitExponent - buffer.Length;
- while (true)
+ if (cutoffNumber != -1)
{
- currentDigit = (int)(BigInteger.HeuristicDivide(ref r, ref s));
+ int desiredCutoffExponent = 0;
- if (r.IsZero() || ((digitsNum + 1) == precision))
+ if (isSignificantDigits)
{
- break;
+ // We asked for a specific number of significant digits.
+ Debug.Assert(cutoffNumber > 0);
+ desiredCutoffExponent = digitExponent - cutoffNumber;
+ }
+ else
+ {
+ // We asked for a specific number of fractional digits.
+ Debug.Assert(cutoffNumber >= 0);
+ desiredCutoffExponent = -cutoffNumber;
}
- number.Digits[digitsNum] = (byte)('0' + currentDigit);
- digitsNum++;
-
- r.Multiply10();
+ if (desiredCutoffExponent > cutoffExponent)
+ {
+ // Only select the new cutoffExponent if it won't overflow the destination buffer.
+ cutoffExponent = desiredCutoffExponent;
+ }
}
- // Step 5:
- // Set the last digit.
- //
- // We round to the closest digit by comparing value with 0.5:
- // compare( value, 0.5 )
- // = compare( r / s, 0.5 )
- // = compare( r, 0.5 * s)
- // = compare(2 * r, s)
- // = compare(r << 1, s)
+ // Output the exponent of the first digit we will print
+ decimalExponent = digitExponent - 1;
+
+ // In preparation for calling BigInteger.HeuristicDivie(), we need to scale up our values such that the highest block of the denominator is greater than or equal to 8.
+ // We also need to guarantee that the numerator can never have a length greater than the denominator after each loop iteration.
+ // This requires the highest block of the denominator to be less than or equal to 429496729 which is the highest number that can be multiplied by 10 without overflowing to a new block.
- r.ShiftLeft(1);
- int compareResult = BigInteger.Compare(ref r, ref s);
- bool isRoundDown = compareResult < 0;
+ Debug.Assert(scale.GetLength() > 0);
+ uint hiBlock = scale.GetBlock((uint)(scale.GetLength() - 1));
- // We are in the middle, round towards the even digit (i.e. IEEE rouding rules)
- if (compareResult == 0)
+ if ((hiBlock < 8) || (hiBlock > 429496729))
{
- isRoundDown = (currentDigit & 1) == 0;
+ // Perform a bit shift on all values to get the highest block of the denominator into the range [8,429496729].
+ // We are more likely to make accurate quotient estimations in BigInteger.HeuristicDivide() with higher denominator values so we shift the denominator to place the highest bit at index 27 of the highest block.
+ // This is safe because (2^28 - 1) = 268435455 which is less than 429496729.
+ // This means that all values with a highest bit at index 27 are within range.
+ uint hiBlockLog2 = BigInteger.LogBase2(hiBlock);
+ Debug.Assert((hiBlockLog2 < 3) || (hiBlockLog2 > 27));
+ uint shift = (32 + 27 - hiBlockLog2) % 32;
+
+ scale.ShiftLeft(shift);
+ scaledValue.ShiftLeft(shift);
+ scaledMarginLow.ShiftLeft(shift);
+
+ if (pScaledMarginHigh != &scaledMarginLow)
+ {
+ BigInteger.Multiply(ref scaledMarginLow, 2, ref *pScaledMarginHigh);
+ }
}
- if (isRoundDown)
+ // These values are used to inspect why the print loop terminated so we can properly round the final digit.
+ bool low; // did the value get within marginLow distance from zero
+ bool high; // did the value get within marginHigh distance from one
+ uint outputDigit; // current digit being output
+
+ if (cutoffNumber == -1)
{
- number.Digits[digitsNum] = (byte)('0' + currentDigit);
- digitsNum++;
+ Debug.Assert(isSignificantDigits);
+
+ // For the unique cutoff mode, we will try to print until we have reached a level of precision that uniquely distinguishes this value from its neighbors.
+ // If we run out of space in the output buffer, we terminate early.
+
+ while (true)
+ {
+ digitExponent = digitExponent - 1;
+
+ // divide out the scale to extract the digit
+ outputDigit = BigInteger.HeuristicDivide(ref scaledValue, ref scale);
+ Debug.Assert(outputDigit < 10);
+
+ // update the high end of the value
+ BigInteger.Add(ref scaledValue, ref *pScaledMarginHigh, out BigInteger scaledValueHigh);
+
+ // stop looping if we are far enough away from our neighboring values or if we have reached the cutoff digit
+ low = BigInteger.Compare(ref scaledValue, ref scaledMarginLow) < 0;
+ high = BigInteger.Compare(ref scaledValueHigh, ref scale) > 0;
+
+ if (low || high || (digitExponent == cutoffExponent))
+ {
+ break;
+ }
+
+ // store the output digit
+ buffer[curDigit] = (byte)('0' + outputDigit);
+ curDigit += 1;
+
+ // multiply larger by the output base
+ scaledValue.Multiply10();
+ scaledMarginLow.Multiply10();
+
+ if (pScaledMarginHigh != &scaledMarginLow)
+ {
+ BigInteger.Multiply(ref scaledMarginLow, 2, ref *pScaledMarginHigh);
+ }
+ }
}
else
{
- byte* pCurrentDigit = (number.GetDigitsPointer() + digitsNum);
+ Debug.Assert((cutoffNumber > 0) || ((cutoffNumber == 0) && !isSignificantDigits));
+
+ // For length based cutoff modes, we will try to print until we have exhausted all precision (i.e. all remaining digits are zeros) or until we reach the desired cutoff digit.
+ low = false;
+ high = false;
- // Rounding up for 9 is special.
- if (currentDigit == 9)
+ while (true)
{
- // find the first non-nine prior digit
- while (true)
+ digitExponent = digitExponent - 1;
+
+ // divide out the scale to extract the digit
+ outputDigit = BigInteger.HeuristicDivide(ref scaledValue, ref scale);
+ Debug.Assert(outputDigit < 10);
+
+ if (scaledValue.IsZero() || (digitExponent <= cutoffExponent))
{
- // If we are at the first digit
- if (pCurrentDigit == number.GetDigitsPointer())
- {
- // Output 1 at the next highest exponent
- *pCurrentDigit = (byte)('1');
- digitsNum++;
- number.Scale += 1;
- break;
- }
-
- pCurrentDigit--;
- digitsNum--;
-
- if (*pCurrentDigit != '9')
- {
- // increment the digit
- *pCurrentDigit += 1;
- digitsNum++;
- break;
- }
+ break;
}
+
+ // store the output digit
+ buffer[curDigit] = (byte)('0' + outputDigit);
+ curDigit += 1;
+
+ // multiply larger by the output base
+ scaledValue.Multiply10();
}
- else
+ }
+
+ // round off the final digit
+ // default to rounding down if value got too close to 0
+ bool roundDown = low;
+
+ if (low == high) // is it legal to round up and down
+ {
+ // round to the closest digit by comparing value with 0.5.
+ //
+ // To do this we need to convert the inequality to large integer values.
+ // compare(value, 0.5)
+ // compare(scale * value, scale * 0.5)
+ // compare(2 * scale * value, scale)
+ scaledValue.Multiply(2);
+ int compare = BigInteger.Compare(ref scaledValue, ref scale);
+ roundDown = compare < 0;
+
+ // if we are directly in the middle, round towards the even digit (i.e. IEEE rouding rules)
+ if (compare == 0)
{
- // It's simple if the digit is not 9.
- *pCurrentDigit = (byte)('0' + currentDigit + 1);
- digitsNum++;
+ roundDown = (outputDigit & 1) == 0;
}
}
- while (digitsNum < precision)
+ // print the rounded digit
+ if (roundDown)
{
- number.Digits[digitsNum] = (byte)('0');
- digitsNum++;
+ buffer[curDigit] = (byte)('0' + outputDigit);
+ curDigit += 1;
}
+ else if (outputDigit == 9) // handle rounding up
+ {
+ // find the first non-nine prior digit
+ while (true)
+ {
+ // if we are at the first digit
+ if (curDigit == 0)
+ {
+ // output 1 at the next highest exponent
+
+ buffer[curDigit] = (byte)('1');
+ curDigit += 1;
+ decimalExponent += 1;
- number.Digits[precision] = (byte)('\0');
+ break;
+ }
+
+ curDigit -= 1;
+
+ if (buffer[curDigit] != '9')
+ {
+ // increment the digit
+
+ buffer[curDigit] += 1;
+ curDigit += 1;
+
+ break;
+ }
+ }
+ }
+ else
+ {
+ // values in the range [0,8] can perform a simple round up
+ buffer[curDigit] = (byte)('0' + outputDigit + 1);
+ curDigit += 1;
+ }
- number.Scale++;
- number.IsNegative = double.IsNegative(value);
+ // return the number of digits output
+ uint outputLen = (uint)(curDigit);
+ Debug.Assert(outputLen <= buffer.Length);
+ return outputLen;
}
}
}
diff --git a/src/System.Private.CoreLib/shared/System/Number.Formatting.cs b/src/System.Private.CoreLib/shared/System/Number.Formatting.cs
index 26045d5cd4..b4f6e92d7a 100644
--- a/src/System.Private.CoreLib/shared/System/Number.Formatting.cs
+++ b/src/System.Private.CoreLib/shared/System/Number.Formatting.cs
@@ -243,8 +243,15 @@ namespace System
internal static partial class Number
{
internal const int DecimalPrecision = 29; // Decimal.DecCalc also uses this value
- private const int SinglePrecision = 7;
- private const int DoublePrecision = 15;
+
+ // SinglePrecision and DoublePrecision represent the maximum number of digits required
+ // to guarantee that any given Single or Double can roundtrip. Some numbers may require
+ // less, but none will require more.
+ private const int SinglePrecision = 9;
+ private const int DoublePrecision = 17;
+
+ private const int DefaultPrecisionExponentialFormat = 6;
+
private const int ScaleNAN = unchecked((int)0x80000000);
private const int ScaleINF = 0x7FFFFFFF;
private const int MaxUInt32DecDigits = 10;
@@ -378,92 +385,186 @@ namespace System
sb.TryCopyTo(destination, out charsWritten);
}
- /// <summary>Formats the specified value according to the specified format and info.</summary>
- /// <returns>
- /// Non-null if an existing string can be returned, in which case the builder will be unmodified.
- /// Null if no existing string was returned, in which case the formatted output is in the builder.
- /// </returns>
- private static unsafe string FormatDouble(ref ValueStringBuilder sb, double value, ReadOnlySpan<char> format, NumberFormatInfo info)
+ private static int GetFloatingPointMaxDigitsAndPrecision(char fmt, ref int precision, NumberFormatInfo info, out bool isSignificantDigits)
{
- char fmt = ParseFormatSpecifier(format, out int digits);
- int precision = DoublePrecision;
+ if (fmt == 0)
+ {
+ isSignificantDigits = true;
+ return precision;
+ }
- byte* pDigits = stackalloc byte[DoubleNumberBufferLength];
- NumberBuffer number = new NumberBuffer(NumberBufferKind.FloatingPoint, pDigits, DoubleNumberBufferLength);
+ int maxDigits = precision;
switch (fmt)
{
- case 'R':
- case 'r':
+ case 'C':
+ case 'c':
{
- // In order to give numbers that are both friendly to display and round-trippable, we parse the
- // number using 15 digits and then determine if it round trips to the same value. If it does, we
- // convert that NUMBER to a string, otherwise we reparse using 17 digits and display that.
- DoubleToNumber(value, DoublePrecision, ref number);
+ // The currency format uses the precision specifier to indicate the number of
+ // decimal digits to format. This defaults to NumberFormatInfo.CurrencyDecimalDigits.
- if (number.Scale == ScaleNAN)
- {
- return info.NaNSymbol;
- }
- else if (number.Scale == ScaleINF)
+ if (precision == -1)
{
- return number.IsNegative ? info.NegativeInfinitySymbol : info.PositiveInfinitySymbol;
+ precision = info.CurrencyDecimalDigits;
}
+ isSignificantDigits = false;
+
+ break;
+ }
- double roundTrip = NumberToDouble(ref number);
+ case 'E':
+ case 'e':
+ {
+ // The exponential format uses the precision specifier to indicate the number of
+ // decimal digits to format. This defaults to 6. However, the exponential format
+ // also always formats a single integral digit, so we need to increase the precision
+ // specifier and treat it as the number of significant digits to account for this.
- if (roundTrip == value)
+ if (precision == -1)
{
- NumberToString(ref sb, ref number, 'G', DoublePrecision, info);
- }
- else
- {
- DoubleToNumber(value, 17, ref number);
- NumberToString(ref sb, ref number, 'G', 17, info);
+ precision = DefaultPrecisionExponentialFormat;
}
- return null;
+ precision++;
+ isSignificantDigits = true;
+
+ break;
}
- case 'E':
- case 'e':
- // Round values less than E14 to 15 digits
- if (digits > 14)
+ case 'F':
+ case 'f':
+ case 'N':
+ case 'n':
+ {
+ // The fixed-point and number formats use the precision specifier to indicate the number
+ // of decimal digits to format. This defaults to NumberFormatInfo.NumberDecimalDigits.
+
+ if (precision == -1)
{
- precision = 17;
+ precision = info.NumberDecimalDigits;
}
+ isSignificantDigits = false;
+
break;
+ }
case 'G':
case 'g':
- // Round values less than G15 to 15 digits. G16 and G17 will not be touched.
- if (digits > 15)
+ {
+ // The general format uses the precision specifier to indicate the number of significant
+ // digits to format. This defaults to the shortest roundtrippable string. Additionally,
+ // given that we can't return zero significant digits, we treat 0 as returning the shortest
+ // roundtrippable string as well.
+
+ if (precision == 0)
+ {
+ precision = -1;
+ }
+ isSignificantDigits = true;
+
+ break;
+ }
+
+ case 'P':
+ case 'p':
+ {
+ // The percent format uses the precision specifier to indicate the number of
+ // decimal digits to format. This defaults to NumberFormatInfo.PercentDecimalDigits.
+ // However, the percent format also always multiplies the number by 100, so we need
+ // to increase the precision specifier to ensure we get the appropriate number of digits.
+
+ if (precision == -1)
{
- precision = 17;
+ precision = info.PercentDecimalDigits;
}
+
+ precision += 2;
+ isSignificantDigits = false;
+
break;
+ }
+
+ case 'R':
+ case 'r':
+ {
+ // The roundtrip format ignores the precision specifier and always returns the shortest
+ // roundtrippable string.
+
+ precision = -1;
+ isSignificantDigits = true;
+
+ break;
+ }
+
+ default:
+ {
+ throw new FormatException(SR.Argument_BadFormatSpecifier);
+ }
}
- DoubleToNumber(value, precision, ref number);
+ return maxDigits;
+ }
- if (number.Scale == ScaleNAN)
+ /// <summary>Formats the specified value according to the specified format and info.</summary>
+ /// <returns>
+ /// Non-null if an existing string can be returned, in which case the builder will be unmodified.
+ /// Null if no existing string was returned, in which case the formatted output is in the builder.
+ /// </returns>
+ private static unsafe string FormatDouble(ref ValueStringBuilder sb, double value, ReadOnlySpan<char> format, NumberFormatInfo info)
+ {
+ if (!double.IsFinite(value))
{
- return info.NaNSymbol;
+ if (double.IsNaN(value))
+ {
+ return info.NaNSymbol;
+ }
+
+ return double.IsNegative(value) ? info.NegativeInfinitySymbol : info.PositiveInfinitySymbol;
}
- else if (number.Scale == ScaleINF)
+
+ char fmt = ParseFormatSpecifier(format, out int precision);
+ byte* pDigits = stackalloc byte[DoubleNumberBufferLength];
+
+ NumberBuffer number = new NumberBuffer(NumberBufferKind.FloatingPoint, pDigits, DoubleNumberBufferLength);
+ number.IsNegative = double.IsNegative(value);
+
+ // We need to track the original precision requested since some formats
+ // accept values like 0 and others may require additional fixups.
+ int nMaxDigits = GetFloatingPointMaxDigitsAndPrecision(fmt, ref precision, info, out bool isSignificantDigits);
+
+ if ((value != 0.0) && (!isSignificantDigits || !Grisu3.TryRunDouble(value, precision, ref number)))
{
- return number.IsNegative ? info.NegativeInfinitySymbol : info.PositiveInfinitySymbol;
+ Dragon4Double(value, precision, isSignificantDigits, ref number);
}
+ number.CheckConsistency();
+
+ // When the number is known to be roundtrippable (either because we requested it be, or
+ // because we know we have enough digits to satisfy roundtrippability), we should validate
+ // that the number actually roundtrips back to the original result.
+
+ Debug.Assert(((precision != -1) && (precision < DoublePrecision)) || (BitConverter.DoubleToInt64Bits(value) == BitConverter.DoubleToInt64Bits(NumberToDouble(ref number))));
+
if (fmt != 0)
{
- NumberToString(ref sb, ref number, fmt, digits, info);
+ if (precision == -1)
+ {
+ Debug.Assert((fmt == 'G') || (fmt == 'g') || (fmt == 'R') || (fmt == 'r'));
+
+ // For the roundtrip and general format specifiers, when returning the shortest roundtrippable
+ // string, we need to update the maximum number of digits to be the greater of number.DigitsCount
+ // or DoublePrecision. This ensures that we continue returning "pretty" strings for values with
+ // less digits. One example this fixes is "-60", which would otherwise be formatted as "-6E+01"
+ // since DigitsCount would be 1 and the formatter would almost immediately switch to scientific notation.
+
+ nMaxDigits = Math.Max(number.DigitsCount, DoublePrecision);
+ }
+ NumberToString(ref sb, ref number, fmt, nMaxDigits, info);
}
else
{
NumberToStringFormat(ref sb, ref number, format, info);
}
-
return null;
}
@@ -491,78 +592,54 @@ namespace System
/// </returns>
private static unsafe string FormatSingle(ref ValueStringBuilder sb, float value, ReadOnlySpan<char> format, NumberFormatInfo info)
{
- char fmt = ParseFormatSpecifier(format, out int digits);
- int precision = SinglePrecision;
-
- byte* pDigits = stackalloc byte[SingleNumberBufferLength];
- NumberBuffer number = new NumberBuffer(NumberBufferKind.FloatingPoint, pDigits, SingleNumberBufferLength);
-
- switch (fmt)
+ if (!float.IsFinite(value))
{
- case 'R':
- case 'r':
+ if (float.IsNaN(value))
{
- // In order to give numbers that are both friendly to display and round-trippable, we parse the
- // number using 7 digits and then determine if it round trips to the same value. If it does, we
- // convert that NUMBER to a string, otherwise we reparse using 9 digits and display that.
- DoubleToNumber(value, SinglePrecision, ref number);
+ return info.NaNSymbol;
+ }
- if (number.Scale == ScaleNAN)
- {
- return info.NaNSymbol;
- }
- else if (number.Scale == ScaleINF)
- {
- return number.IsNegative ? info.NegativeInfinitySymbol : info.PositiveInfinitySymbol;
- }
+ return float.IsNegative(value) ? info.NegativeInfinitySymbol : info.PositiveInfinitySymbol;
+ }
- float roundTrip = NumberToSingle(ref number);
+ char fmt = ParseFormatSpecifier(format, out int precision);
+ byte* pDigits = stackalloc byte[SingleNumberBufferLength];
- if (roundTrip == value)
- {
- NumberToString(ref sb, ref number, 'G', SinglePrecision, info);
- }
- else
- {
- DoubleToNumber(value, 9, ref number);
- NumberToString(ref sb, ref number, 'G', 9, info);
- }
- return null;
- }
+ NumberBuffer number = new NumberBuffer(NumberBufferKind.FloatingPoint, pDigits, SingleNumberBufferLength);
+ number.IsNegative = float.IsNegative(value);
- case 'E':
- case 'e':
- // Round values less than E14 to 15 digits.
- if (digits > 6)
- {
- precision = 9;
- }
- break;
+ // We need to track the original precision requested since some formats
+ // accept values like 0 and others may require additional fixups.
+ int nMaxDigits = GetFloatingPointMaxDigitsAndPrecision(fmt, ref precision, info, out bool isSignificantDigits);
- case 'G':
- case 'g':
- // Round values less than G15 to 15 digits. G16 and G17 will not be touched.
- if (digits > 7)
- {
- precision = 9;
- }
- break;
+ if ((value != 0.0f) && (!isSignificantDigits || !Grisu3.TryRunSingle(value, precision, ref number)))
+ {
+ Dragon4Single(value, precision, isSignificantDigits, ref number);
}
- DoubleToNumber(value, precision, ref number);
+ number.CheckConsistency();
- if (number.Scale == ScaleNAN)
- {
- return info.NaNSymbol;
- }
- else if (number.Scale == ScaleINF)
- {
- return number.IsNegative ? info.NegativeInfinitySymbol : info.PositiveInfinitySymbol;
- }
+ // When the number is known to be roundtrippable (either because we requested it be, or
+ // because we know we have enough digits to satisfy roundtrippability), we should validate
+ // that the number actually roundtrips back to the original result.
+
+ Debug.Assert(((precision != -1) && (precision < SinglePrecision)) || (BitConverter.SingleToInt32Bits(value) == BitConverter.SingleToInt32Bits(NumberToSingle(ref number))));
if (fmt != 0)
{
- NumberToString(ref sb, ref number, fmt, digits, info);
+ if (precision == -1)
+ {
+ Debug.Assert((fmt == 'G') || (fmt == 'g') || (fmt == 'R') || (fmt == 'r'));
+
+ // For the roundtrip and general format specifiers, when returning the shortest roundtrippable
+ // string, we need to update the maximum number of digits to be the greater of number.DigitsCount
+ // or SinglePrecision. This ensures that we continue returning "pretty" strings for values with
+ // less digits. One example this fixes is "-60", which would otherwise be formatted as "-6E+01"
+ // since DigitsCount would be 1 and the formatter would almost immediately switch to scientific notation.
+
+ nMaxDigits = Math.Max(number.DigitsCount, SinglePrecision);
+ }
+ NumberToString(ref sb, ref number, fmt, nMaxDigits, info);
}
else
{
@@ -1554,7 +1631,7 @@ namespace System
case 'e':
{
if (nMaxDigits < 0)
- nMaxDigits = 6;
+ nMaxDigits = DefaultPrecisionExponentialFormat;
nMaxDigits++;
RoundNumber(ref number, nMaxDigits);
@@ -1618,6 +1695,14 @@ namespace System
break;
}
+ case 'R':
+ case 'r':
+ {
+ format = (char)(format - ('R' - 'G'));
+ Debug.Assert((format == 'G') || (format == 'g'));
+ goto case 'G';
+ }
+
default:
throw new FormatException(SR.Argument_BadFormatSpecifier);
}
@@ -2348,38 +2433,11 @@ namespace System
return rem;
}
- private static unsafe void DoubleToNumber(double value, int precision, ref NumberBuffer number)
- {
- if (!double.IsFinite(value))
- {
- number.Scale = double.IsNaN(value) ? ScaleNAN : ScaleINF;
- number.IsNegative = double.IsNegative(value);
- number.Digits[0] = (byte)('\0');
- }
- else if (value == 0.0)
- {
- number.Scale = 0;
- number.IsNegative = double.IsNegative(value);
- number.Digits[0] = (byte)('\0');
- }
- else
- {
- number.DigitsCount = precision;
-
- if (!Grisu3.Run(value, precision, ref number))
- {
- Dragon4(value, precision, ref number);
- }
- }
-
- number.CheckConsistency();
- }
-
- private static long ExtractFractionAndBiasedExponent(double value, out int exponent)
+ private static ulong ExtractFractionAndBiasedExponent(double value, out int exponent)
{
- var bits = BitConverter.DoubleToInt64Bits(value);
- long fraction = (bits & 0xFFFFFFFFFFFFF);
- exponent = (int)((bits >> 52) & 0x7FF);
+ ulong bits = (ulong)(BitConverter.DoubleToInt64Bits(value));
+ ulong fraction = (bits & 0xFFFFFFFFFFFFF);
+ exponent = ((int)(bits >> 52) & 0x7FF);
if (exponent != 0)
{
@@ -2390,7 +2448,7 @@ namespace System
//
// So f = (2^52 + mantissa), e = exp - 1075;
- fraction |= ((long)(1) << 52);
+ fraction |= (1UL << 52);
exponent -= 1075;
}
else
@@ -2406,5 +2464,37 @@ namespace System
return fraction;
}
+
+ private static uint ExtractFractionAndBiasedExponent(float value, out int exponent)
+ {
+ uint bits = (uint)(BitConverter.SingleToInt32Bits(value));
+ uint fraction = (bits & 0x7FFFFF);
+ exponent = ((int)(bits >> 23) & 0xFF);
+
+ if (exponent != 0)
+ {
+ // For normalized value, according to https://en.wikipedia.org/wiki/Single-precision_floating-point_format
+ // value = 1.fraction * 2^(exp - 127)
+ // = (1 + mantissa / 2^23) * 2^(exp - 127)
+ // = (2^23 + mantissa) * 2^(exp - 127 - 23)
+ //
+ // So f = (2^23 + mantissa), e = exp - 150;
+
+ fraction |= (1U << 23);
+ exponent -= 150;
+ }
+ else
+ {
+ // For denormalized value, according to https://en.wikipedia.org/wiki/Single-precision_floating-point_format
+ // value = 0.fraction * 2^(1 - 127)
+ // = (mantissa / 2^23) * 2^(-126)
+ // = mantissa * 2^(-126 - 23)
+ // = mantissa * 2^(-149)
+ // So f = mantissa, e = -149
+ exponent = -149;
+ }
+
+ return fraction;
+ }
}
}
diff --git a/src/System.Private.CoreLib/shared/System/Number.Grisu3.cs b/src/System.Private.CoreLib/shared/System/Number.Grisu3.cs
index 1f0072efb6..96ec7af2f8 100644
--- a/src/System.Private.CoreLib/shared/System/Number.Grisu3.cs
+++ b/src/System.Private.CoreLib/shared/System/Number.Grisu3.cs
@@ -8,23 +8,34 @@ namespace System
{
internal static partial class Number
{
- internal static unsafe class Grisu3
+ // This is a port of the `Grisu3` implementation here: https://github.com/google/double-conversion/blob/a711666ddd063eb1e4b181a6cb981d39a1fc8bac/double-conversion/fast-dtoa.cc
+ // The backing algorithm and the proofs behind it are described in more detail here: http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf
+ // ========================================================================================================================================
+ //
+ // Overview:
+ //
+ // The general idea behind Grisu3 is to leverage additional bits and cached powers of ten to generate the correct digits.
+ // The algorithm is imprecise for some numbers. Fortunately, the algorithm itself can determine this scenario and gives us
+ // a result indicating success or failure. We must fallback to a different algorithm for the failing scenario.
+ internal static class Grisu3
{
- private const int Alpha = -59;
+ private const int CachedPowersDecimalExponentDistance = 8;
+ private const int CachedPowersMinDecimalExponent = -348;
+ private const int CachedPowersPowerMaxDecimalExponent = 340;
+ private const int CachedPowersOffset = -CachedPowersMinDecimalExponent;
+
+ // 1 / Log2(10)
private const double D1Log210 = 0.301029995663981195;
- private const int Gamma = -32;
- private const int PowerDecimalExponentDistance = 8;
- private const int PowerMinDecimalExponent = -348;
- private const int PowerMaxDecimalExponent = 340;
- private const int PowerOffset = -PowerMinDecimalExponent;
- private const uint Ten4 = 10000;
- private const uint Ten5 = 100000;
- private const uint Ten6 = 1000000;
- private const uint Ten7 = 10000000;
- private const uint Ten8 = 100000000;
- private const uint Ten9 = 1000000000;
-
- private static readonly short[] s_CachedPowerBinaryExponents = new short[]
+
+ // The minimal and maximal target exponents define the range of w's binary exponent,
+ // where w is the result of multiplying the input by a cached power of ten.
+ //
+ // A different range might be chosen on a different platform, to optimize digit generation,
+ // but a smaller range requires more powers of ten to be cached.
+ private const int MaximalTargetExponent = -32;
+ private const int MinimalTargetExponent = -60;
+
+ private static readonly short[] s_CachedPowersBinaryExponent = new short[]
{
-1220,
-1193,
@@ -115,9 +126,9 @@ namespace System
1066,
};
- private static readonly short[] s_CachedPowerDecimalExponents = new short[]
+ private static readonly short[] s_CachedPowersDecimalExponent = new short[]
{
- PowerMinDecimalExponent,
+ CachedPowersMinDecimalExponent,
-340,
-332,
-324,
@@ -203,24 +214,10 @@ namespace System
316,
324,
332,
- PowerMaxDecimalExponent,
+ CachedPowersPowerMaxDecimalExponent,
};
- private static readonly uint[] s_CachedPowerOfTen = new uint[]
- {
- 1, // 10^0
- 10, // 10^1
- 100, // 10^2
- 1000, // 10^3
- 10000, // 10^4
- 100000, // 10^5
- 1000000, // 10^6
- 10000000, // 10^7
- 100000000, // 10^8
- 1000000000, // 10^9
- };
-
- private static readonly ulong[] s_CachedPowerSignificands = new ulong[]
+ private static readonly ulong[] s_CachedPowersSignificand = new ulong[]
{
0xFA8FD5A0081C0288,
0xBAAEE17FA23EBF76,
@@ -311,410 +308,621 @@ namespace System
0xAF87023B9BF0EE6B,
};
- public static bool Run(double value, int precision, ref NumberBuffer number)
+ private static readonly uint[] s_SmallPowersOfTen = new uint[]
{
- // ========================================================================================================================================
- // This implementation is based on the paper: http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf
- // You must read this paper to fully understand the code.
- //
- // Deviation: Instead of generating shortest digits, we generate the digits according to the input count.
- // Therefore, we do not need m+ and m- which are used to determine the exact range of values.
- // ========================================================================================================================================
- //
- // Overview:
- //
- // The idea of Grisu3 is to leverage additional bits and cached power of ten to produce the digits.
- // We need to create a handmade floating point data structure DiyFp to extend the bits of double.
- // We also need to cache the powers of ten for digits generation. By choosing the correct index of powers
- // we need to start with, we can eliminate the expensive big num divide operation.
- //
- // Grisu3 is imprecision for some numbers. Fortunately, the algorithm itself can determine that and give us
- // a success/fail flag. We may fall back to other algorithms (For instance, Dragon4) if it fails.
- //
- // w: the normalized DiyFp from the input value.
- // mk: The index of the cached powers.
- // cmk: The cached power.
- // D: Product: w * cmk.
- // kappa: A factor used for generating digits. See step 5 of the Grisu3 procedure in the paper.
-
- // Handle sign bit.
- if (double.IsNegative(value))
+ 1, // 10^0
+ 10, // 10^1
+ 100, // 10^2
+ 1000, // 10^3
+ 10000, // 10^4
+ 100000, // 10^5
+ 1000000, // 10^6
+ 10000000, // 10^7
+ 100000000, // 10^8
+ 1000000000, // 10^9
+ };
+
+ public static bool TryRunDouble(double value, int requestedDigits, ref NumberBuffer number)
+ {
+ double v = double.IsNegative(value) ? -value : value;
+
+ Debug.Assert(v > 0);
+ Debug.Assert(double.IsFinite(v));
+
+ int length = 0;
+ int decimalExponent = 0;
+ bool result = false;
+
+ if (requestedDigits == -1)
{
- value = -value;
- number.IsNegative = true;
+ DiyFp w = DiyFp.CreateAndGetBoundaries(v, out DiyFp boundaryMinus, out DiyFp boundaryPlus).Normalize();
+ result = TryRunShortest(in boundaryMinus, in w, in boundaryPlus, number.Digits, out length, out decimalExponent);
}
else
{
- number.IsNegative = false;
+ DiyFp w = new DiyFp(v).Normalize();
+ result = TryRunCounted(in w, requestedDigits, number.Digits, out length, out decimalExponent);
}
- // Step 1: Determine the normalized DiyFp w.
-
- DiyFp.GenerateNormalizedDiyFp(value, out DiyFp w);
-
- // Step 2: Find the cached power of ten.
+ if (result)
+ {
+ Debug.Assert((requestedDigits == -1) || (length == requestedDigits));
- // Compute the proper index mk.
- int mk = KComp(w.e + DiyFp.SignificandLength);
+ number.Scale = length + decimalExponent;
+ number.Digits[length] = (byte)('\0');
+ number.DigitsCount = length;
+ }
- // Retrieve the cached power of ten.
- CachedPower(mk, out DiyFp cmk, out int decimalExponent);
+ return result;
+ }
- // Step 3: Scale the w with the cached power of ten.
+ public static bool TryRunSingle(float value, int requestedDigits, ref NumberBuffer number)
+ {
+ float v = float.IsNegative(value) ? -value : value;
- DiyFp.Multiply(ref w, ref cmk, out DiyFp D);
+ Debug.Assert(v > 0);
+ Debug.Assert(float.IsFinite(v));
- // Step 4: Generate digits.
+ int length = 0;
+ int decimalExponent = 0;
+ bool result = false;
- bool isSuccess = DigitGen(ref D, precision, number.GetDigitsPointer(), out int length, out int kappa);
+ if (requestedDigits == -1)
+ {
+ DiyFp w = DiyFp.CreateAndGetBoundaries(v, out DiyFp boundaryMinus, out DiyFp boundaryPlus).Normalize();
+ result = TryRunShortest(in boundaryMinus, in w, in boundaryPlus, number.Digits, out length, out decimalExponent);
+ }
+ else
+ {
+ DiyFp w = new DiyFp(v).Normalize();
+ result = TryRunCounted(in w, requestedDigits, number.Digits, out length, out decimalExponent);
+ }
- if (isSuccess)
+ if (result)
{
- number.Digits[precision] = (byte)('\0');
- number.Scale = (length - decimalExponent + kappa);
+ Debug.Assert((requestedDigits == -1) || (length == requestedDigits));
+
+ number.Scale = length + decimalExponent;
+ number.Digits[length] = (byte)('\0');
+ number.DigitsCount = length;
}
- return isSuccess;
+ return result;
}
- // Returns the biggest power of ten that is less than or equal to the given number.
- static void BiggestPowerTenLessThanOrEqualTo(uint number, int bits, out uint power, out int exponent)
+ // The counted version of Grisu3 only generates requestedDigits number of digits.
+ // This version does not generate the shortest representation, and with enough requested digits 0.1 will at some point print as 0.9999999...
+ // Grisu3 is too imprecise for real halfway cases (1.5 will not work) and therefore the rounding strategy for halfway cases is irrelevant.
+ private static bool TryRunCounted(in DiyFp w, int requestedDigits, Span<byte> buffer, out int length, out int decimalExponent)
{
- switch (bits)
- {
- case 32:
- case 31:
- case 30:
- {
- if (Ten9 <= number)
- {
- power = Ten9;
- exponent = 9;
- break;
- }
+ Debug.Assert(requestedDigits > 0);
- goto case 29;
- }
+ int tenMkMinimalBinaryExponent = MinimalTargetExponent - (w.e + DiyFp.SignificandSize);
+ int tenMkMaximalBinaryExponent = MaximalTargetExponent - (w.e + DiyFp.SignificandSize);
- case 29:
- case 28:
- case 27:
- {
- if (Ten8 <= number)
- {
- power = Ten8;
- exponent = 8;
- break;
- }
+ DiyFp tenMk = GetCachedPowerForBinaryExponentRange(tenMkMinimalBinaryExponent, tenMkMaximalBinaryExponent, out int mk);
- goto case 26;
- }
+ Debug.Assert(MinimalTargetExponent <= (w.e + tenMk.e + DiyFp.SignificandSize));
+ Debug.Assert(MaximalTargetExponent >= (w.e + tenMk.e + DiyFp.SignificandSize));
- case 26:
- case 25:
- case 24:
- {
- if (Ten7 <= number)
- {
- power = Ten7;
- exponent = 7;
- break;
- }
+ // Note that tenMk is only an approximation of 10^-k.
+ // A DiyFp only contains a 64-bit significand and tenMk is thus only precise up to 64-bits.
- goto case 23;
- }
+ // The DiyFp.Multiply procedure rounds its result and tenMk is approximated too.
+ // The variable scaledW (as well as scaledBoundaryMinus/Plus) are now off by a small amount.
+ //
+ // In fact, scaledW - (w * 10^k) < 1ulp (unit in last place) of scaledW.
+ // In other words, let f = scaledW.f and e = scaledW.e, then:
+ // (f - 1) * 2^e < (w * 10^k) < (f + 1) * 2^e
- case 23:
- case 22:
- case 21:
- case 20:
- {
- if (Ten6 <= number)
- {
- power = Ten6;
- exponent = 6;
- break;
- }
+ DiyFp scaledW = w.Multiply(in tenMk);
- goto case 19;
- }
+ // We now have (double)(scaledW * 10^-mk).
+ //
+ // DigitGenCounted will generate the first requestedDigits of scaledW and return together with a kappa such that:
+ // scaledW ~= buffer * 10^kappa.
+ //
+ // It will not always be exactly the same since DigitGenCounted only produces a limited number of digits.
- case 19:
- case 18:
- case 17:
- {
- if (Ten5 <= number)
- {
- power = Ten5;
- exponent = 5;
- break;
- }
+ bool result = TryDigitGenCounted(in scaledW, requestedDigits, buffer, out length, out int kappa);
+ decimalExponent = -mk + kappa;
+ return result;
+ }
- goto case 16;
- }
+ // Provides a decimal representation of v.
+ // Returns true if it succeeds; otherwise, the result cannot be trusted.
+ //
+ // There will be length digits inside the buffer (not null-terminated).
+ // If the function returns true then:
+ // v == (double)(buffer * 10^decimalExponent)
+ //
+ // The digits in the buffer are the shortest represenation possible (no 0.09999999999999999 instead of 0.1).
+ // The shorter representation will even be chosen if the longer one would be closer to v.
+ //
+ // The last digit will be closest to the actual v.
+ // That is, even if several digits might correctly yield 'v' when read again, the closest will be computed.
+ private static bool TryRunShortest(in DiyFp boundaryMinus, in DiyFp w, in DiyFp boundaryPlus, Span<byte> buffer, out int length, out int decimalExponent)
+ {
+ // boundaryMinus and boundaryPlus are the boundaries between v and its closest floating-point neighbors.
+ // Any number strictly between boundaryMinus and boundaryPlus will round to v when converted to a double.
+ // Grisu3 will never output representations that lie exactly on a boundary.
- case 16:
- case 15:
- case 14:
- {
- if (Ten4 <= number)
- {
- power = Ten4;
- exponent = 4;
- break;
- }
+ Debug.Assert(boundaryPlus.e == w.e);
- goto case 13;
- }
+ int tenMkMinimalBinaryExponent = MinimalTargetExponent - (w.e + DiyFp.SignificandSize);
+ int tenMkMaximalBinaryExponent = MaximalTargetExponent - (w.e + DiyFp.SignificandSize);
- case 13:
- case 12:
- case 11:
- case 10:
- {
- if (1000 <= number)
- {
- power = 1000;
- exponent = 3;
- break;
- }
+ DiyFp tenMk = GetCachedPowerForBinaryExponentRange(tenMkMinimalBinaryExponent, tenMkMaximalBinaryExponent, out int mk);
- goto case 9;
- }
+ Debug.Assert(MinimalTargetExponent <= (w.e + tenMk.e + DiyFp.SignificandSize));
+ Debug.Assert(MaximalTargetExponent >= (w.e + tenMk.e + DiyFp.SignificandSize));
- case 9:
- case 8:
- case 7:
- {
- if (100 <= number)
- {
- power = 100;
- exponent = 2;
- break;
- }
+ // Note that tenMk is only an approximation of 10^-k.
+ // A DiyFp only contains a 64-bit significan and tenMk is thus only precise up to 64-bits.
- goto case 6;
- }
+ // The DiyFp.Multiply procedure rounds its result and tenMk is approximated too.
+ // The variable scaledW (as well as scaledBoundaryMinus/Plus) are now off by a small amount.
+ //
+ // In fact, scaledW - (w * 10^k) < 1ulp (unit in last place) of scaledW.
+ // In other words, let f = scaledW.f and e = scaledW.e, then:
+ // (f - 1) * 2^e < (w * 10^k) < (f + 1) * 2^e
- case 6:
- case 5:
- case 4:
- {
- if (10 <= number)
- {
- power = 10;
- exponent = 1;
- break;
- }
+ DiyFp scaledW = w.Multiply(in tenMk);
+ Debug.Assert(scaledW.e == (boundaryPlus.e + tenMk.e + DiyFp.SignificandSize));
- goto case 3;
- }
+ // In theory, it would be possible to avoid some recomputations by computing the difference between w
+ // and boundaryMinus/Plus (a power of 2) and to compute scaledBoundaryMinus/Plus by subtracting/adding
+ // from scaledW. However, the code becomes much less readable and the speed enhancements are not terrific.
- case 3:
- case 2:
- case 1:
- {
- if (1 <= number)
- {
- power = 1;
- exponent = 0;
- break;
- }
+ DiyFp scaledBoundaryMinus = boundaryMinus.Multiply(in tenMk);
+ DiyFp scaledBoundaryPlus = boundaryPlus.Multiply(in tenMk);
- goto case 0;
- }
+ // DigitGen will generate the digits of scaledW. Therefore, we have:
+ // v == (double)(scaledW * 10^-mk)
+ //
+ // Set decimalExponent == -mk and pass it to DigitGen and if scaledW is not an integer than it will be updated.
+ // For instance, if scaledW == 1.23 then the buffer will be filled with "123" and the decimalExponent will be decreased by 2.
- case 0:
- {
- power = 0;
- exponent = -1;
- break;
- }
+ bool result = TryDigitGenShortest(in scaledBoundaryMinus, in scaledW, in scaledBoundaryPlus, buffer, out length, out int kappa);
+ decimalExponent = -mk + kappa;
+ return result;
+ }
- default:
- {
- power = 0;
- exponent = 0;
+ // Returns the biggest power of ten that is less than or equal to the given number.
+ // We furthermore receive the maximum number of bits 'number' has.
+ //
+ // Returns power == 10^(exponent) such that
+ // power <= number < power * 10
+ // If numberBits == 0, then 0^(0-1) is returned.
+ // The number of bits must be <= 32.
+ //
+ // Preconditions:
+ // number < (1 << (numberBits + 1))
+ private static uint BiggestPowerTen(uint number, int numberBits, out int exponentPlusOne)
+ {
+ // Inspired by the method for finding an integer log base 10 from here:
+ // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
- Debug.Fail("unreachable");
- break;
- }
+ Debug.Assert(number < (1U << (numberBits + 1)));
+
+ // 1233/4096 is approximately 1/log2(10)
+ int exponentGuess = ((numberBits + 1) * 1233) >> 12;
+ Debug.Assert((uint)(exponentGuess) < s_SmallPowersOfTen.Length);
+
+ uint power = s_SmallPowersOfTen[exponentGuess];
+
+ // We don't have any guarantees that 2^numberBits <= number
+ if (number < power)
+ {
+ exponentGuess -= 1;
+ power = s_SmallPowersOfTen[exponentGuess];
}
- }
- private static void CachedPower(int k, out DiyFp cmk, out int decimalExponent)
- {
- int index = ((PowerOffset + k - 1) / PowerDecimalExponentDistance) + 1;
- cmk = new DiyFp(s_CachedPowerSignificands[index], s_CachedPowerBinaryExponents[index]);
- decimalExponent = s_CachedPowerDecimalExponents[index];
+ exponentPlusOne = exponentGuess + 1;
+ return power;
}
- private static bool DigitGen(ref DiyFp mp, int precision, byte* digits, out int length, out int k)
+ // Generates (at most) requestedDigits of input number w.
+ //
+ // w is a floating-point number (DiyFp), consisting of a significand and an exponent.
+ // Its exponent is bounded by MinimalTargetExponent and MaximalTargetExponent, hence:
+ // -60 <= w.e <= -32
+ //
+ // Returns false if it fails, in which case the generated digits in the buffer should not be used.
+ //
+ // Preconditions:
+ // w is correct up to 1 ulp (unit in last place). That is, its error must be strictly less than a unit of its last digit.
+ // MinimalTargetExponent <= w.e <= MaximalTargetExponent
+ //
+ // Postconditions:
+ // Returns false if the procedure fails; otherwise:
+ // * buffer is not null-terminated, but length contains the number of digits.
+ // * The representation in buffer is the most precise representation of requestedDigits digits.
+ // * buffer contains at most requestedDigits digits of w. If there are less than requestedDigits digits then some trailing '0's have been removed.
+ // * kappa is such that w = buffer * 10^kappa + eps with |eps| < 10^kappa / 2.
+ //
+ // This procedure takes into account the imprecision of its input numbers.
+ // If the precision is not enough to guarantee all the postconditions, then false is returned.
+ // This usually happens rarely, but the failure-rate increases with higher requestedDigits
+ private static bool TryDigitGenCounted(in DiyFp w, int requestedDigits, Span<byte> buffer, out int length, out int kappa)
{
- // Split the input mp to two parts. Part 1 is integral. Part 2 can be used to calculate
- // fractional.
- //
- // mp: the input DiyFp scaled by cached power.
- // K: final kappa.
- // p1: part 1.
- // p2: part 2.
-
- Debug.Assert(precision > 0);
- Debug.Assert(digits != null);
- Debug.Assert(mp.e >= Alpha);
- Debug.Assert(mp.e <= Gamma);
-
- ulong mpF = mp.f;
- int mpE = mp.e;
+ Debug.Assert(MinimalTargetExponent <= w.e);
+ Debug.Assert(w.e <= MaximalTargetExponent);
+ Debug.Assert(MinimalTargetExponent >= -60);
+ Debug.Assert(MaximalTargetExponent <= -32);
- var one = new DiyFp(1UL << -mpE, mpE);
+ // w is assumed to have an error less than 1 unit.
+ // Whenever w is scaled we also scale its error.
+ ulong wError = 1;
- ulong oneF = one.f;
- int oneNegE = -one.e;
+ // We cut the input number into two parts: the integral digits and the fractional digits.
+ // We don't emit any decimal separator, but adapt kapp instead.
+ // For example: instead of writing "1.2", we put "12" into the buffer and increase kappa by 1.
+ var one = new DiyFp((1UL << -w.e), w.e);
- ulong ulp = 1;
+ // Division by one is a shift.
+ uint integrals = (uint)(w.f >> -one.e);
- uint p1 = (uint)(mpF >> oneNegE);
- ulong p2 = mpF & (oneF - 1);
+ // Modulo by one is an and.
+ ulong fractionals = w.f & (one.f - 1);
- // When p2 (fractional part) is zero, we can predicate if p1 is good to produce the numbers in requested digit count:
+ // We deviate from the original algorithm here and do some early checks to determine if we can satisfy requestedDigits.
+ // If we determine that we can't, we exit early and avoid most of the heavy lifting that the algorithm otherwise does.
//
- // - When requested digit count >= 11, p1 is not be able to exhaust the count as 10^(11 - 1) > uint.MaxValue >= p1.
- // - When p1 < 10^(count - 1), p1 is not be able to exhaust the count.
- // - Otherwise, p1 may have chance to exhaust the count.
- if ((p2 == 0) && ((precision >= 11) || (p1 < s_CachedPowerOfTen[precision - 1])))
+ // When fractionals is zero, we can easily determine if integrals can satisfy requested digits:
+ // If requestedDigits >= 11, integrals is not able to exhaust the count by itself since 10^(11 -1) > uint.MaxValue >= integrals.
+ // If integrals < 10^(requestedDigits - 1), integrals cannot exhaust the count.
+ // Otherwise, integrals might be able to exhaust the count and we need to execute the rest of the code.
+ if ((fractionals == 0) && ((requestedDigits >= 11) || (integrals < s_SmallPowersOfTen[requestedDigits - 1])))
{
+ Debug.Assert(buffer[0] == '\0');
length = 0;
- k = 0;
+ kappa = 0;
return false;
}
- // Note: The code in the paper simply assigns div to Ten9 and kappa to 10 directly.
- // That means we need to check if any leading zero of the generated
- // digits during the while loop, which hurts the performance.
- //
- // Now if we can estimate what the div and kappa, we do not need to check the leading zeros.
- // The idea is to find the biggest power of 10 that is less than or equal to the given number.
- // Then we don't need to worry about the leading zeros and we can get 10% performance gain.
- int index = 0;
- BiggestPowerTenLessThanOrEqualTo(p1, (DiyFp.SignificandLength - oneNegE), out uint div, out int kappa);
- kappa++;
-
- // Produce integral.
+ uint divisor = BiggestPowerTen(integrals, (DiyFp.SignificandSize - (-one.e)), out kappa);
+ length = 0;
+
+ // Loop invariant:
+ // buffer = w / 10^kappa (integer division)
+ // These invariants hold for the first iteration:
+ // kappa has been initialized with the divisor exponent + 1
+ // The divisor is the biggest power of ten that is smaller than integrals
while (kappa > 0)
{
- int d = (int)(Math.DivRem(p1, div, out p1));
- digits[index] = (byte)('0' + d);
+ uint digit = Math.DivRem(integrals, divisor, out integrals);
+ Debug.Assert(digit <= 9);
+ buffer[length] = (byte)('0' + digit);
- index++;
- precision--;
+ length++;
+ requestedDigits--;
kappa--;
- if (precision == 0)
+ // Note that kappa now equals the exponent of the
+ // divisor and that the invariant thus holds again.
+ if (requestedDigits == 0)
{
break;
}
- div /= 10;
+ divisor /= 10;
}
- // End up here if we already exhausted the digit count.
- if (precision == 0)
+ if (requestedDigits == 0)
{
- ulong rest = ((ulong)(p1) << oneNegE) + p2;
-
- length = index;
- k = kappa;
-
- return RoundWeed(
- digits,
- index,
+ ulong rest = ((ulong)(integrals) << -one.e) + fractionals;
+ return TryRoundWeedCounted(
+ buffer,
+ length,
rest,
- ((ulong)(div)) << oneNegE,
- ulp,
- ref k
+ tenKappa: ((ulong)(divisor)) << -one.e,
+ unit: wError,
+ ref kappa
);
}
- // We have to generate digits from part2 if we have requested digit count left
- // and part2 is greater than ulp.
- while ((precision > 0) && (p2 > ulp))
+ // The integrals have been generated and we are at the point of the decimal separator.
+ // In the following loop, we simply multiply the remaining digits by 10 and divide by one.
+ // We just need to pay attention to multiply associated data (the unit), too.
+ // Note that the multiplication by 10 does not overflow because:
+ // w.e >= -60 and thus one.e >= -60
+
+ Debug.Assert(one.e >= MinimalTargetExponent);
+ Debug.Assert(fractionals < one.f);
+ Debug.Assert((ulong.MaxValue / 10) >= one.f);
+
+ while ((requestedDigits > 0) && (fractionals > wError))
{
- p2 *= 10;
+ fractionals *= 10;
+ wError *= 10;
- int d = (int)(p2 >> oneNegE);
- digits[index] = (byte)('0' + d);
+ // Integer division by one.
+ uint digit = (uint)(fractionals >> -one.e);
+ Debug.Assert(digit <= 9);
+ buffer[length] = (byte)('0' + digit);
- index++;
- precision--;
+ length++;
+ requestedDigits--;
kappa--;
- p2 &= (oneF - 1);
-
- ulp *= 10;
+ // Modulo by one.
+ fractionals &= (one.f - 1);
}
- // If we haven't exhausted the requested digit counts, the Grisu3 algorithm fails.
- if (precision != 0)
+ if (requestedDigits != 0)
{
+ buffer[0] = (byte)('\0');
length = 0;
- k = 0;
+ kappa = 0;
return false;
}
- length = index;
- k = kappa;
+ return TryRoundWeedCounted(
+ buffer,
+ length,
+ rest: fractionals,
+ tenKappa: one.f,
+ unit: wError,
+ ref kappa
+ );
+ }
+
+ // Generates the digits of input number w.
+ //
+ // w is a floating-point number (DiyFp), consisting of a significand and an exponent.
+ // Its exponent is bounded by kMinimalTargetExponent and kMaximalTargetExponent, hence:
+ // -60 <= w.e() <= -32.
+ //
+ // Returns false if it fails, in which case the generated digits in the buffer should not be used.
+ //
+ // Preconditions:
+ // low, w and high are correct up to 1 ulp (unit in the last place). That is, their error must be less than a unit of their last digits.
+ // low.e() == w.e() == high.e()
+ // low < w < high, and taking into account their error: low~ <= high~
+ // kMinimalTargetExponent <= w.e() <= kMaximalTargetExponent
+ //
+ // Postconditions:
+ // Returns false if procedure fails; otherwise:
+ // * buffer is not null-terminated, but len contains the number of digits.
+ // * buffer contains the shortest possible decimal digit-sequence such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the correct values of low and high (without their error).
+ // * If more than one decimal representation gives the minimal number of decimal digits then the one closest to W (where W is the correct value of w) is chosen.
+ //
+ // This procedure takes into account the imprecision of its input numbers.
+ // If the precision is not enough to guarantee all the postconditions then false is returned.
+ // This usually happens rarely (~0.5%).
+ //
+ // Say, for the sake of example, that:
+ // w.e() == -48, and w.f() == 0x1234567890abcdef
+ //
+ // w's value can be computed by w.f() * 2^w.e()
+ //
+ // We can obtain w's integral digits by simply shifting w.f() by -w.e().
+ // -> w's integral part is 0x1234
+ // w's fractional part is therefore 0x567890abcdef.
+ //
+ // Printing w's integral part is easy (simply print 0x1234 in decimal).
+ //
+ // In order to print its fraction we repeatedly multiply the fraction by 10 and get each digit.
+ // For example, the first digit after the point would be computed by
+ // (0x567890abcdef * 10) >> 48. -> 3
+ //
+ // The whole thing becomes slightly more complicated because we want to stop once we have enough digits.
+ // That is, once the digits inside the buffer represent 'w' we can stop.
+ //
+ // Everything inside the interval low - high represents w.
+ // However we have to pay attention to low, high and w's imprecision.
+ private static bool TryDigitGenShortest(in DiyFp low, in DiyFp w, in DiyFp high, Span<byte> buffer, out int length, out int kappa)
+ {
+ Debug.Assert(low.e == w.e);
+ Debug.Assert(w.e == high.e);
+
+ Debug.Assert((low.f + 1) <= (high.f - 1));
+
+ Debug.Assert(MinimalTargetExponent <= w.e);
+ Debug.Assert(w.e <= MaximalTargetExponent);
+
+ // low, w, and high are imprecise, but by less than one ulp (unit in the last place).
+ //
+ // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that the new numbers
+ // are outside of the interval we want the final representation to lie in.
+ //
+ // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield numbers that
+ // are certain to lie in the interval. We will use this fact later on.
+ //
+ // We will now start by generating the digits within the uncertain interval.
+ // Later, we will weed out representations that lie outside the safe interval and thus might lie outside the correct interval.
+
+ ulong unit = 1;
+
+ var tooLow = new DiyFp((low.f - unit), low.e);
+ var tooHigh = new DiyFp((high.f + unit), high.e);
+
+ // tooLow and tooHigh are guaranteed to lie outside the interval we want the generated number in.
+
+ DiyFp unsafeInterval = tooHigh.Subtract(in tooLow);
+
+ // We now cut the input number into two parts: the integral digits and the fractional digits.
+ // We will not write any decimal separator, but adapt kappa instead.
+ //
+ // Reminder: we are currently computing the digits (Stored inside the buffer) such that:
+ // tooLow < buffer * 10^kappa < tooHigh
+ //
+ // We use tooHigh for the digitGeneration and stop as soon as possible.
+ // If we stop early, we effectively round down.
+
+ var one = new DiyFp((1UL << -w.e), w.e);
+
+ // Division by one is a shift.
+ uint integrals = (uint)(tooHigh.f >> -one.e);
+
+ // Modulo by one is an and.
+ ulong fractionals = tooHigh.f & (one.f - 1);
+
+ uint divisor = BiggestPowerTen(integrals, (DiyFp.SignificandSize - (-one.e)), out kappa);
+ length = 0;
+
+ // Loop invariant:
+ // buffer = tooHigh / 10^kappa (integer division)
+ // These invariants hold for the first iteration:
+ // kappa has been initialized with the divisor exponent + 1
+ // The divisor is the biggest power of ten that is smaller than integrals
+ while (kappa > 0)
+ {
+ uint digit = Math.DivRem(integrals, divisor, out integrals);
+ Debug.Assert(digit <= 9);
+ buffer[length] = (byte)('0' + digit);
+
+ length++;
+ kappa--;
+
+ // Note that kappa now equals the exponent of the
+ // divisor and that the invariant thus holds again.
+
+ ulong rest = ((ulong)(integrals) << -one.e) + fractionals;
+
+ // Invariant: tooHigh = buffer * 10^kappa + DiyFp(rest, one.e)
+ // Reminder: unsafeInterval.e == one.e
+
+ if (rest < unsafeInterval.f)
+ {
+ // Rounding down (by not emitting the remaining digits)
+ // yields a number that lies within the unsafe interval
+
+ return TryRoundWeedShortest(
+ buffer,
+ length,
+ tooHigh.Subtract(w).f,
+ unsafeInterval.f,
+ rest,
+ tenKappa: ((ulong)(divisor)) << -one.e,
+ unit
+ );
+ }
+
+ divisor /= 10;
+ }
+
+ // The integrals have been generated and we are at the point of the decimal separator.
+ // In the following loop, we simply multiply the remaining digits by 10 and divide by one.
+ // We just need to pay attention to multiply associated data (the unit), too.
+ // Note that the multiplication by 10 does not overflow because:
+ // w.e >= -60 and thus one.e >= -60
+
+ Debug.Assert(one.e >= MinimalTargetExponent);
+ Debug.Assert(fractionals < one.f);
+ Debug.Assert((ulong.MaxValue / 10) >= one.f);
+
+ while (true)
+ {
+ fractionals *= 10;
+ unit *= 10;
+
+ unsafeInterval = new DiyFp((unsafeInterval.f * 10), unsafeInterval.e);
- return RoundWeed(digits, index, p2, oneF, ulp, ref k);
+ // Integer division by one.
+ uint digit = (uint)(fractionals >> -one.e);
+ Debug.Assert(digit <= 9);
+ buffer[length] = (byte)('0' + digit);
+
+ length++;
+ kappa--;
+
+ // Modulo by one.
+ fractionals &= (one.f - 1);
+
+ if (fractionals < unsafeInterval.f)
+ {
+ return TryRoundWeedShortest(
+ buffer,
+ length,
+ tooHigh.Subtract(w).f * unit,
+ unsafeInterval.f,
+ rest: fractionals,
+ tenKappa: one.f,
+ unit
+ );
+ }
+ }
}
- private static int KComp(int e)
+ // Returns a cached power-of-ten with a binary exponent in the range [minExponent; maxExponent] (boundaries included).
+ private static DiyFp GetCachedPowerForBinaryExponentRange(int minExponent, int maxExponent, out int decimalExponent)
{
- return (int)(Math.Ceiling((Alpha - e + DiyFp.SignificandLength - 1) * D1Log210));
+ Debug.Assert(s_CachedPowersSignificand.Length == s_CachedPowersBinaryExponent.Length);
+ Debug.Assert(s_CachedPowersSignificand.Length == s_CachedPowersDecimalExponent.Length);
+
+ double k = Math.Ceiling((minExponent + DiyFp.SignificandSize - 1) * D1Log210);
+ int index = ((CachedPowersOffset + (int)(k) - 1) / CachedPowersDecimalExponentDistance) + 1;
+
+ Debug.Assert((uint)(index) < s_CachedPowersSignificand.Length);
+
+ Debug.Assert(minExponent <= s_CachedPowersBinaryExponent[index]);
+ Debug.Assert(s_CachedPowersBinaryExponent[index] <= maxExponent);
+
+ decimalExponent = s_CachedPowersDecimalExponent[index];
+ return new DiyFp(s_CachedPowersSignificand[index], s_CachedPowersBinaryExponent[index]);
}
- private static bool RoundWeed(byte* buffer, int len, ulong rest, ulong tenKappa, ulong ulp, ref int kappa)
+ // Rounds the buffer upwards if the result is closer to v by possibly adding 1 to the buffer.
+ // If the precision of the calculation is not sufficient to round correctly, return false.
+ //
+ // The rounding might shift the whole buffer, in which case, the kappy is adjusted.
+ // For example "99", kappa = 3 might become "10", kappa = 4.
+ //
+ // If (2 * rest) > tenKappa then the buffer needs to be round up.
+ // rest can have an error of +/- 1 unit.
+ // This function accounts for the imprecision and returns false if the rounding direction cannot be unambiguously determined.
+ //
+ // Preconditions:
+ // rest < tenKappa
+ private static bool TryRoundWeedCounted(Span<byte> buffer, int length, ulong rest, ulong tenKappa, ulong unit, ref int kappa)
{
Debug.Assert(rest < tenKappa);
- // 1. tenKappa <= ulp: we don't have an idea which way to round.
- // 2. Even if tenKappa > ulp, but if tenKappa <= 2 * ulp we cannot find the way to round.
- // Note: to prevent overflow, we need to use tenKappa - ulp <= ulp.
- if ((tenKappa <= ulp) || ((tenKappa - ulp) <= ulp))
+ // The following tests are done in a specific order to avoid overflows.
+ // They will work correctly with any ulong values of rest < tenKappa and unit.
+ //
+ // If the unit is too big, then we don't know which way to round.
+ // For example, a unit of 50 means that the real number lies within rest +/- 50.
+ // If 10^kappa == 40, then there is no way to tell which way to round.
+ //
+ // Even if unit is just half the size of 10^kappa we are already completely lost.
+ // And after the previous test, we know that the expression will not over/underflow.
+ if ((unit >= tenKappa) || ((tenKappa - unit) <= unit))
{
return false;
}
- // tenKappa >= 2 * (rest + ulp). We should round down.
- // Note: to prevent overflow, we need to check if tenKappa > 2 * rest as a prerequisite.
- if (((tenKappa - rest) > rest) && ((tenKappa - (2 * rest)) >= (2 * ulp)))
+ // If 2 * (rest + unit) <= 10^kappa, we can safely round down.
+ if (((tenKappa - rest) > rest) && ((tenKappa - (2 * rest)) >= (2 * unit)))
{
return true;
}
- // tenKappa <= 2 * (rest - ulp). We should round up.
- // Note: to prevent overflow, we need to check if rest > ulp as a prerequisite.
- if ((rest > ulp) && (tenKappa <= (rest - ulp) || ((tenKappa - (rest - ulp)) <= (rest - ulp))))
+ // If 2 * (rest - unit) >= 10^kappa, we can safely round up.
+ if ((rest > unit) && (tenKappa <= (rest - unit) || ((tenKappa - (rest - unit)) <= (rest - unit))))
{
- // Find all 9s from end to start.
- buffer[len - 1]++;
- for (int i = len - 1; i > 0; i--)
+ // Increment the last digit recursively until we find a non '9' digit.
+ buffer[length - 1]++;
+
+ for (int i = (length - 1); i > 0; i--)
{
- if (buffer[i] != (byte)('0' + 10))
+ if (buffer[i] != ('0' + 10))
{
- // We end up a number less than 9.
break;
}
- // Current number becomes 0 and add the promotion to the next number.
buffer[i] = (byte)('0');
buffer[i - 1]++;
}
- if (buffer[0] == (char)('0' + 10))
+ // If the first digit is now '0'+10, we had a buffer with all '9's.
+ // With the exception of the first digit, all digits are now '0'.
+ // Simply switch the first digit to '1' and adjust the kappa.
+ // For example, "99" becomes "10" and the power (the kappa) is increased.
+ if (buffer[0] == ('0' + 10))
{
- // First number is '0' + 10 means all numbers are 9.
- // We simply make the first number to 1 and increase the kappa.
buffer[0] = (byte)('1');
kappa++;
}
@@ -724,6 +932,123 @@ namespace System
return false;
}
+
+ // Adjusts the last digit of the generated number and screens out generated solutions that may be inaccurate.
+ // A solution may be inaccurate if it is outside the safe interval or if we cannot provide that it is closer to the input than a neighboring representation of the same length.
+ //
+ // Input:
+ // buffer containing the digits of tooHigh / 10^kappa
+ // the buffer's length
+ // distanceTooHighW == (tooHigh - w).f * unit
+ // unsafeInterval == (tooHigh - tooLow).f * unit
+ // rest = (tooHigh - buffer * 10^kapp).f * unit
+ // tenKappa = 10^kappa * unit
+ // unit = the common multiplier
+ //
+ // Output:
+ // Returns true if the buffer is guaranteed to contain the closest representable number to the input.
+ //
+ // Modifies the generated digits in the buffer to approach (round towards) w.
+ private static bool TryRoundWeedShortest(Span<byte> buffer, int length, ulong distanceTooHighW, ulong unsafeInterval, ulong rest, ulong tenKappa, ulong unit)
+ {
+ ulong smallDistance = distanceTooHighW - unit;
+ ulong bigDistance = distanceTooHighW + unit;
+
+ // Let wLow = tooHigh - bigDistance, and wHigh = tooHigh - smallDistance.
+ //
+ // Note: wLow < w < wHigh
+ //
+ // The real w * unit must lie somewhere inside the interval
+ // ]w_low; w_high[ (often written as "(w_low; w_high)")
+
+ // Basically the buffer currently contains a number in the unsafe interval
+ // ]too_low; too_high[ with too_low < w < too_high
+ //
+ // tooHigh - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ // ^v 1 unit ^ ^ ^ ^
+ // boundaryHigh --------------------- . . . .
+ // ^v 1 unit . . . .
+ // - - - - - - - - - - - - - - - - - - - + - - + - - - - - - . .
+ // . . ^ . .
+ // . bigDistance . . .
+ // . . . . rest
+ // smallDistance . . . .
+ // v . . . .
+ // wHigh - - - - - - - - - - - - - - - - - - . . . .
+ // ^v 1 unit . . . .
+ // w --------------------------------------- . . . .
+ // ^v 1 unit v . . .
+ // wLow - - - - - - - - - - - - - - - - - - - - - . . .
+ // . . v
+ // buffer -------------------------------------------------+-------+--------
+ // . .
+ // safeInterval .
+ // v .
+ // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - .
+ // ^v 1 unit .
+ // boundaryLow ------------------------- unsafeInterval
+ // ^v 1 unit v
+ // tooLow - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
+ //
+ //
+ // Note that the value of buffer could lie anywhere inside the range tooLow to tooHigh.
+ //
+ // boundaryLow, boundaryHigh and w are approximations of the real boundaries and v (the input number).
+ // They are guaranteed to be precise up to one unit.
+ // In fact the error is guaranteed to be strictly less than one unit.
+ //
+ // Anything that lies outside the unsafe interval is guaranteed not to round to v when read again.
+ // Anything that lies inside the safe interval is guaranteed to round to v when read again.
+ //
+ // If the number inside the buffer lies inside the unsafe interval but not inside the safe interval
+ // then we simply do not know and bail out (returning false).
+ //
+ // Similarly we have to take into account the imprecision of 'w' when finding the closest representation of 'w'.
+ // If we have two potential representations, and one is closer to both wLow and wHigh, then we know it is closer to the actual value v.
+ //
+ // By generating the digits of tooHigh we got the largest (closest to tooHigh) buffer that is still in the unsafe interval.
+ // In the case where wHigh < buffer < tooHigh we try to decrement the buffer.
+ // This way the buffer approaches (rounds towards) w.
+ //
+ // There are 3 conditions that stop the decrementation process:
+ // 1) the buffer is already below wHigh
+ // 2) decrementing the buffer would make it leave the unsafe interval
+ // 3) decrementing the buffer would yield a number below wHigh and farther away than the current number.
+ //
+ // In other words:
+ // (buffer{-1} < wHigh) && wHigh - buffer{-1} > buffer - wHigh
+ //
+ // Instead of using the buffer directly we use its distance to tooHigh.
+ //
+ // Conceptually rest ~= tooHigh - buffer
+ //
+ // We need to do the following tests in this order to avoid over- and underflows.
+
+ Debug.Assert(rest <= unsafeInterval);
+
+ while ((rest < smallDistance) && ((unsafeInterval - rest) >= tenKappa) && (((rest + tenKappa) < smallDistance) || ((smallDistance - rest) >= (rest + tenKappa - smallDistance))))
+ {
+ buffer[length - 1]--;
+ rest += tenKappa;
+ }
+
+ // We have approached w+ as much as possible.
+ // We now test if approaching w- would require changing the buffer.
+ // If yes, then we have two possible representations close to w, but we cannot decide which one is closer.
+ if ((rest < bigDistance) && ((unsafeInterval - rest) >= tenKappa) && (((rest + tenKappa) < bigDistance) || ((bigDistance - rest) > (rest + tenKappa - bigDistance))))
+ {
+ return false;
+ }
+
+ // Weeding test.
+ //
+ // The safe interval is [tooLow + 2 ulp; tooHigh - 2 ulp]
+ // Since tooLow = tooHigh - unsafeInterval this is equivalent to
+ // [tooHigh - unsafeInterval + 4 ulp; tooHigh - 2 ulp]
+ //
+ // Conceptually we have: rest ~= tooHigh - buffer
+ return ((2 * unit) <= rest) && (rest <= (unsafeInterval - 4 * unit));
+ }
}
}
}
diff --git a/tests/CoreFX/CoreFX.issues.json b/tests/CoreFX/CoreFX.issues.json
index 1f27486cb9..c249ffa259 100644
--- a/tests/CoreFX/CoreFX.issues.json
+++ b/tests/CoreFX/CoreFX.issues.json
@@ -230,7 +230,19 @@
{
"name": "System.ComponentModel.Tests.EnumConverterTests.ConvertTo_ULongFlagsEnum_EnumArray",
"reason": "System.OverflowException : Value was either too large or too small for an Int64."
- }
+ },
+ {
+ "name": "System.ComponentModel.TypeConverterTests.SizeFConverterTests.ConvertTo",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "System.ComponentModel.TypeConverterTests.SizeFConverterTests.ConvertToString",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "System.ComponentModel.TypeConverterTests.SizeFConverterTests.ConvertToInvariantString",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
]
}
},
@@ -923,7 +935,23 @@
{
"name" : "Microsoft.VisualBasic.Tests.ConversionsTests.ToULong_InvalidObject_ThrowsInvalidCastException",
"reason" : "outdated"
- }
+ },
+ {
+ "name" : "Microsoft.VisualBasic.Tests.ConversionsTests.ToSingle_String_ReturnsExpected",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name" : "Microsoft.VisualBasic.Tests.ConversionsTests.ToDouble_String_ReturnsExpected",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name" : "Microsoft.VisualBasic.Tests.ConversionsTests.ToSingle_Object_ReturnsExpected",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name" : "Microsoft.VisualBasic.Tests.ConversionsTests.ToDouble_Object_ReturnsExpected",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
]
}
},
@@ -1025,7 +1053,28 @@
{
"name": "System.Tests.TimeSpanTests.Parse",
"reason": "Temporary disabling till merging the PR https://github.com/dotnet/corefx/pull/34561"
- }
+ },
+
+ {
+ "name": "System.Tests.SingleTests.Test_ToString",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "System.Tests.SingleTests.TryFormat",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "System.Tests.DoubleTests.Test_ToString",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "System.Tests.DoubleTests.TryFormat",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "System.Tests.TimeSpanTests.Total_Days_Hours_Minutes_Seconds_Milliseconds",
+ "reason" : "https://github.com/dotnet/coreclr/pull/22040"
+ },
]
}
},
@@ -1070,6 +1119,10 @@
"name": "System.Json.Tests.JsonPrimitiveTests.ToString_DateTimeOffset",
"reason": "waiting on corefx test update"
},
+ {
+ "name": "System.Json.Tests.JsonValueTests.Parse_IntegralBoundaries_LessThanMaxDouble_Works",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
]
}
},
@@ -1111,8 +1164,112 @@
{
"name": "System.Linq.Expressions.Tests.BindTests.StaticReadonlyField",
"reason": "https://github.com/dotnet/coreclr/pull/20886 and https://github.com/dotnet/corefx/pull/33413"
- }
+ },
+ {
+ "name": "System.Linq.Expressions.Tests.StackSpillerTests.Spill_Optimizations_LiteralField",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ ]
+ }
+ },
+ {
+ "name": "System.Xml.XmlSerializer.Tests",
+ "enabled": true,
+ "exclusions": {
+ "namespaces": null,
+ "classes": null,
+ "methods": [
+ {
+ "name": "XmlSerializerTests.Xml_FloatAsRoot",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
]
}
- }
+ },
+ {
+ "name": "System.Xml.XmlSerializer.ReflectionOnly.Tests",
+ "enabled": true,
+ "exclusions": {
+ "namespaces": null,
+ "classes": null,
+ "methods": [
+ {
+ "name": "XmlSerializerTests.Xml_FloatAsRoot",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ ]
+ }
+ },
+ {
+ "name": "System.Runtime.Serialization.Xml.Tests",
+ "enabled": true,
+ "exclusions": {
+ "namespaces": null,
+ "classes": null,
+ "methods": [
+ {
+ "name": "DataContractSerializerTests.DCS_FloatAsRoot",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "DataContractSerializerTests.DCS_BasicPerSerializerRoundTripAndCompare_EnumStruct",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "DataContractSerializerTests.DCS_BasicRoundTripResolvePrimitiveTypes",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ ]
+ }
+ },
+ {
+ "name": "System.Runtime.Serialization.Xml.ReflectionOnly.Tests",
+ "enabled": true,
+ "exclusions": {
+ "namespaces": null,
+ "classes": null,
+ "methods": [
+ {
+ "name": "DataContractSerializerTests.DCS_FloatAsRoot",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "DataContractSerializerTests.DCS_BasicPerSerializerRoundTripAndCompare_EnumStruct",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ {
+ "name": "DataContractSerializerTests.DCS_BasicRoundTripResolvePrimitiveTypes",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ ]
+ }
+ },
+ {
+ "name": "System.Runtime.Serialization.Json.Tests",
+ "enabled": true,
+ "exclusions": {
+ "namespaces": null,
+ "classes": null,
+ "methods": [
+ {
+ "name": "DataContractJsonSerializerTests.DCJS_FloatAsRoot",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ ]
+ }
+ },
+ {
+ "name": "System.Runtime.Serialization.Json.ReflectionOnly.Tests",
+ "enabled": true,
+ "exclusions": {
+ "namespaces": null,
+ "classes": null,
+ "methods": [
+ {
+ "name": "DataContractJsonSerializerTests.DCJS_FloatAsRoot",
+ "reason": "https://github.com/dotnet/coreclr/pull/22040"
+ },
+ ]
+ }
+ },
]