Hello, the bulk of this message is a new patch that replaces the one found at [1]. It appears both inline and as an attachment in the hope that at least one form makes it through. What did change in the meantime? * The most convoluted part of the implementation has been refactored to both reduce the SLOC count and enhance performance, which now reaches about 16x speedup wrt the current OpenJDK implementation. * The Javadoc for the toString() methods has a new definition of d_v, the decimal to format as a string. While slightly more abstract, it is far clearer than the former one, I hope. * A new test has been added to extensively check the consistency of class MathUtils, which is a vital component of the whole code. For the interested reader, there's now a document (subject to change at any time) devoted to the explanation of the underlying Schubfach algorithm and its high performance implementation [2]. For how to pronounce the German noun Schubfach (shoobfaX, the X as in LaTeX), click on the left speaker button in [3]. Beside lack of time until Christmas, one of the reasons it took me so long in writing the document is because I want it to be readable by anyone minimally interested in the subject. It does not require any previous knowledge or any math other than simple algebraic manipulations, love for logical reasoning and some maturity. It requires some willingness and some hours to go through, though. Not being tied to journal publishing, I exploited this luxury to ensure a rather relaxed reading pace. For the expert reader in a hurry, however, here's a suggested reading guide: * Take a look at figure 2 to make sure that the definition of the decimal d_v is well understood. * Review definition 4 about the shortest form and the length of a decimal and result 5 about the length of decimals in the proximity of another one. * Have a knowledge of result 8, which is key in avoiding an iterative search and which is exploited in the design of Schubfach. * Take a breath and delve into the discussion of Schubfach in section 8.1, leading to figure 3. * From section 9 onward the discussion is about an efficient implementation. This is essential reading to understand the rather concise Java implementation. There's no shortcut known to me, so have a clear mind and drop me a line, even in private, if you have troubles. Greetings Raffaello ---- [1] https://mail.openjdk.java.net/pipermail/core-libs-dev/2018-September/055698.... [2] https://drive.google.com/open?id=1KLtG_LaIbK9ETXI290zqCxvBW94dj058 [3] https://translate.google.com/?hl=&ie=UTF-8&sl=it&tl=en#view=home&op=translat... ---- # HG changeset patch # Date 1550416868 -3600 # Sun Feb 17 16:21:08 2019 +0100 # Node ID 726d159731343a7120278def10482527123411e8 # Parent d230a040662314f69fe50620a68fae6634550b49 Patch to fix JDK-4511638 4511638: Double.toString(double) sometimes produces incorrect results Reviewed-by: TBD Contributed-by: Raffaello Giulietti <raffaello.giulietti@gmail.com> diff --git a/src/java.base/share/classes/java/lang/Double.java b/src/java.base/share/classes/java/lang/Double.java --- a/src/java.base/share/classes/java/lang/Double.java +++ b/src/java.base/share/classes/java/lang/Double.java @@ -30,6 +30,7 @@ import java.lang.constant.ConstantDesc; import java.util.Optional; +import jdk.internal.math.DoubleToDecimal; import jdk.internal.math.FloatingDecimal; import jdk.internal.math.DoubleConsts; import jdk.internal.HotSpotIntrinsicCandidate; @@ -145,69 +146,120 @@ public static final Class<Double> TYPE = (Class<Double>) Class.getPrimitiveClass("double"); /** - * Returns a string representation of the {@code double} - * argument. All characters mentioned below are ASCII characters. - * <ul> - * <li>If the argument is NaN, the result is the string - * "{@code NaN}". - * <li>Otherwise, the result is a string that represents the sign and - * magnitude (absolute value) of the argument. If the sign is negative, - * the first character of the result is '{@code -}' - * ({@code '\u005Cu002D'}); if the sign is positive, no sign character - * appears in the result. As for the magnitude <i>m</i>: - * <ul> - * <li>If <i>m</i> is infinity, it is represented by the characters - * {@code "Infinity"}; thus, positive infinity produces the result - * {@code "Infinity"} and negative infinity produces the result - * {@code "-Infinity"}. - * - * <li>If <i>m</i> is zero, it is represented by the characters - * {@code "0.0"}; thus, negative zero produces the result - * {@code "-0.0"} and positive zero produces the result - * {@code "0.0"}. + * Returns a string rendering of the {@code double} argument. * - * <li>If <i>m</i> is greater than or equal to 10^-3 but less - * than 10⁷, then it is represented as the integer part of - * <i>m</i>, in decimal form with no leading zeroes, followed by - * '{@code .}' ({@code '\u005Cu002E'}), followed by one or - * more decimal digits representing the fractional part of <i>m</i>. - * - * <li>If <i>m</i> is less than 10^-3 or greater than or - * equal to 10⁷, then it is represented in so-called - * "computerized scientific notation." Let <i>n</i> be the unique - * integer such that 10^<i>n</i> ≤ <i>m</i> {@literal <} - * 10^<i>n</i>+1; then let <i>a</i> be the - * mathematically exact quotient of <i>m</i> and - * 10^<i>n</i> so that 1 ≤ <i>a</i> {@literal <} 10. The - * magnitude is then represented as the integer part of <i>a</i>, - * as a single decimal digit, followed by '{@code .}' - * ({@code '\u005Cu002E'}), followed by decimal digits - * representing the fractional part of <i>a</i>, followed by the - * letter '{@code E}' ({@code '\u005Cu0045'}), followed - * by a representation of <i>n</i> as a decimal integer, as - * produced by the method {@link Integer#toString(int)}. + * <p>The characters of the result are all drawn from the ASCII set. + * <ul> + * <li> Any NaN, whether quiet or signaling, is rendered as + * {@code "NaN"}, regardless of the sign bit. + * <li> The infinities +∞ and -∞ are rendered as + * {@code "Infinity"} and {@code "-Infinity"}, respectively. + * <li> The positive and negative zeroes are rendered as + * {@code "0.0"} and {@code "-0.0"}, respectively. + * <li> A finite negative {@code v} is rendered as the sign + * '{@code -}' followed by the rendering of the magnitude -{@code v}. + * <li> A finite positive {@code v} is rendered in two stages: + * <ul> + * <li> <em>Selection of a decimal</em>: A well-defined + * decimal <i>d</i>_{<code>v</code>} is selected + * to represent {@code v}. + * <li> <em>Formatting as a string</em>: The decimal + * <i>d</i>_{<code>v</code>} is formatted as a string, + * either in plain or in computerized scientific notation, + * depending on its value. * </ul> * </ul> - * How many digits must be printed for the fractional part of - * <i>m</i> or <i>a</i>? There must be at least one digit to represent - * the fractional part, and beyond that as many, but only as many, more - * digits as are needed to uniquely distinguish the argument value from - * adjacent values of type {@code double}. That is, suppose that - * <i>x</i> is the exact mathematical value represented by the decimal - * representation produced by this method for a finite nonzero argument - * <i>d</i>. Then <i>d</i> must be the {@code double} value nearest - * to <i>x</i>; or if two {@code double} values are equally close - * to <i>x</i>, then <i>d</i> must be one of them and the least - * significant bit of the significand of <i>d</i> must be {@code 0}. + * + * <p>A <em>decimal</em> is a number of the form + * <i>d</i>×10^<i>i</i> + * for some (unique) integers <i>d</i> > 0 and <i>i</i> such that + * <i>d</i> is not a multiple of 10. + * These integers are the <em>significand</em> and + * the <em>exponent</em>, respectively, of the decimal. + * The <em>length</em> of the decimal is the (unique) + * integer <i>n</i> meeting + * 10^<i>n</i>-1 ≤ <i>d</i> < 10^<i>n</i>. + * + * <p>The decimal <i>d</i>_{<code>v</code>} + * for a finite positive {@code v} is defined as follows: + * <ul> + * <li>Let <i>R</i> be the set of all decimals that round to {@code v} + * according to the usual round-to-closest rule of + * IEEE 754 floating-point arithmetic. + * <li>Let <i>m</i> be the minimal length over all decimals in <i>R</i>. + * <li>When <i>m</i> ≥ 2, let <i>T</i> be the set of all decimals + * in <i>R</i> with length <i>m</i>. + * Otherwise, let <i>T</i> be the set of all decimals + * in <i>R</i> with length 1 or 2. + * <li>Define <i>d</i>_{<code>v</code>} as + * the decimal in <i>T</i> that is closest to {@code v}. + * Or if there are two such decimals in <i>T</i>, + * select the one with the even significand (there is exactly one). + * </ul> + * + * <p>The (uniquely) selected decimal <i>d</i>_{<code>v</code>} + * is then formatted. * - * <p>To create localized string representations of a floating-point - * value, use subclasses of {@link java.text.NumberFormat}. + * <p>Let <i>d</i>, <i>i</i> and <i>n</i> be the significand, exponent and + * length of <i>d</i>_{<code>v</code>}, respectively. + * Further, let <i>e</i> = <i>n</i> + <i>i</i> - 1 and let + * <i>d</i>₁…<i>d</i>_<i>n</i> + * be the usual decimal expansion of the significand. + * Note that <i>d</i>₁ ≠ 0 ≠ <i>d</i>_<i>n</i>. + * <ul> + * <li>Case -3 ≤ <i>e</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <code>0.0</code>…<code>0</code><!-- + * --><i>d</i>₁…<i>d</i>_<i>n</i>, + * where there are exactly -(<i>n</i> + <i>i</i>) zeroes between + * the decimal point and <i>d</i>₁. + * For example, 123 × 10^-4 is formatted as + * {@code 0.0123}. + * <li>Case 0 ≤ <i>e</i> < 7: + * <ul> + * <li>Subcase <i>i</i> ≥ 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<i>d</i>_<i>n</i><!-- + * --><code>0</code>…<code>0.0</code>, + * where there are exactly <i>i</i> zeroes + * between <i>d</i>_<i>n</i> and the decimal point. + * For example, 123 × 10² is formatted as + * {@code 12300.0}. + * <li>Subcase <i>i</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>}.<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>+1}…<!-- + * --><i>d</i>_<i>n</i>. + * There are exactly -<i>i</i> digits to the right of + * the decimal point. + * For example, 123 × 10^-1 is formatted as + * {@code 12.3}. + * </ul> + * <li>Case <i>e</i> < -3 or <i>e</i> ≥ 7: + * computerized scientific notation is used to format + * <i>d</i>_{<code>v</code>}. + * Here <i>e</i> is formatted as by {@link Integer#toString(int)}. + * <ul> + * <li>Subcase <i>n</i> = 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.0E</code><i>e</i>. + * For example, 1 × 10²³ is formatted as + * {@code 1.0E23}. + * <li>Subcase <i>n</i> > 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.</code><i>d</i>₂<!-- + * -->…<i>d</i>_<i>n</i><code>E</code><i>e</i>. + * For example, 123 × 10^-21 is formatted as + * {@code 1.23E-19}. + * </ul> + * </ul> * - * @param d the {@code double} to be converted. - * @return a string representation of the argument. + * @param v the {@code double} to be rendered. + * @return a string rendering of the argument. */ public static String toString(double d) { - return FloatingDecimal.toJavaFormatString(d); + return DoubleToDecimal.toString(d); } /** diff --git a/src/java.base/share/classes/java/lang/Float.java b/src/java.base/share/classes/java/lang/Float.java --- a/src/java.base/share/classes/java/lang/Float.java +++ b/src/java.base/share/classes/java/lang/Float.java @@ -30,6 +30,7 @@ import java.lang.constant.ConstantDesc; import java.util.Optional; +import jdk.internal.math.FloatToDecimal; import jdk.internal.math.FloatingDecimal; import jdk.internal.HotSpotIntrinsicCandidate; @@ -142,73 +143,120 @@ public static final Class<Float> TYPE = (Class<Float>) Class.getPrimitiveClass("float"); /** - * Returns a string representation of the {@code float} - * argument. All characters mentioned below are ASCII characters. - * <ul> - * <li>If the argument is NaN, the result is the string - * "{@code NaN}". - * <li>Otherwise, the result is a string that represents the sign and - * magnitude (absolute value) of the argument. If the sign is - * negative, the first character of the result is - * '{@code -}' ({@code '\u005Cu002D'}); if the sign is - * positive, no sign character appears in the result. As for - * the magnitude <i>m</i>: + * Returns a string rendering of the {@code float} argument. + * + * <p>The characters of the result are all drawn from the ASCII set. * <ul> - * <li>If <i>m</i> is infinity, it is represented by the characters - * {@code "Infinity"}; thus, positive infinity produces - * the result {@code "Infinity"} and negative infinity - * produces the result {@code "-Infinity"}. - * <li>If <i>m</i> is zero, it is represented by the characters - * {@code "0.0"}; thus, negative zero produces the result - * {@code "-0.0"} and positive zero produces the result - * {@code "0.0"}. - * <li> If <i>m</i> is greater than or equal to 10^-3 but - * less than 10⁷, then it is represented as the - * integer part of <i>m</i>, in decimal form with no leading - * zeroes, followed by '{@code .}' - * ({@code '\u005Cu002E'}), followed by one or more - * decimal digits representing the fractional part of - * <i>m</i>. - * <li> If <i>m</i> is less than 10^-3 or greater than or - * equal to 10⁷, then it is represented in - * so-called "computerized scientific notation." Let <i>n</i> - * be the unique integer such that 10^<i>n</i>≤ - * <i>m</i> {@literal <} 10^<i>n</i>+1; then let <i>a</i> - * be the mathematically exact quotient of <i>m</i> and - * 10^<i>n</i> so that 1 ≤ <i>a</i> {@literal <} 10. - * The magnitude is then represented as the integer part of - * <i>a</i>, as a single decimal digit, followed by - * '{@code .}' ({@code '\u005Cu002E'}), followed by - * decimal digits representing the fractional part of - * <i>a</i>, followed by the letter '{@code E}' - * ({@code '\u005Cu0045'}), followed by a representation - * of <i>n</i> as a decimal integer, as produced by the - * method {@link java.lang.Integer#toString(int)}. - * + * <li> Any NaN, whether quiet or signaling, is rendered as + * {@code "NaN"}, regardless of the sign bit. + * <li> The infinities +∞ and -∞ are rendered as + * {@code "Infinity"} and {@code "-Infinity"}, respectively. + * <li> The positive and negative zeroes are rendered as + * {@code "0.0"} and {@code "-0.0"}, respectively. + * <li> A finite negative {@code v} is rendered as the sign + * '{@code -}' followed by the rendering of the magnitude -{@code v}. + * <li> A finite positive {@code v} is rendered in two stages: + * <ul> + * <li> <em>Selection of a decimal</em>: A well-defined + * decimal <i>d</i>_{<code>v</code>} is selected + * to represent {@code v}. + * <li> <em>Formatting as a string</em>: The decimal + * <i>d</i>_{<code>v</code>} is formatted as a string, + * either in plain or in computerized scientific notation, + * depending on its value. * </ul> * </ul> - * How many digits must be printed for the fractional part of - * <i>m</i> or <i>a</i>? There must be at least one digit - * to represent the fractional part, and beyond that as many, but - * only as many, more digits as are needed to uniquely distinguish - * the argument value from adjacent values of type - * {@code float}. That is, suppose that <i>x</i> is the - * exact mathematical value represented by the decimal - * representation produced by this method for a finite nonzero - * argument <i>f</i>. Then <i>f</i> must be the {@code float} - * value nearest to <i>x</i>; or, if two {@code float} values are - * equally close to <i>x</i>, then <i>f</i> must be one of - * them and the least significant bit of the significand of - * <i>f</i> must be {@code 0}. + * + * <p>A <em>decimal</em> is a number of the form + * <i>d</i>×10^<i>i</i> + * for some (unique) integers <i>d</i> > 0 and <i>i</i> such that + * <i>d</i> is not a multiple of 10. + * These integers are the <em>significand</em> and + * the <em>exponent</em>, respectively, of the decimal. + * The <em>length</em> of the decimal is the (unique) + * integer <i>n</i> meeting + * 10^<i>n</i>-1 ≤ <i>d</i> < 10^<i>n</i>. + * + * <p>The decimal <i>d</i>_{<code>v</code>} + * for a finite positive {@code v} is defined as follows: + * <ul> + * <li>Let <i>R</i> be the set of all decimals that round to {@code v} + * according to the usual round-to-closest rule of + * IEEE 754 floating-point arithmetic. + * <li>Let <i>m</i> be the minimal length over all decimals in <i>R</i>. + * <li>When <i>m</i> ≥ 2, let <i>T</i> be the set of all decimals + * in <i>R</i> with length <i>m</i>. + * Otherwise, let <i>T</i> be the set of all decimals + * in <i>R</i> with length 1 or 2. + * <li>Define <i>d</i>_{<code>v</code>} as + * the decimal in <i>T</i> that is closest to {@code v}. + * Or if there are two such decimals in <i>T</i>, + * select the one with the even significand (there is exactly one). + * </ul> + * + * <p>The (uniquely) selected decimal <i>d</i>_{<code>v</code>} + * is then formatted. * - * <p>To create localized string representations of a floating-point - * value, use subclasses of {@link java.text.NumberFormat}. + * <p>Let <i>d</i>, <i>i</i> and <i>n</i> be the significand, exponent and + * length of <i>d</i>_{<code>v</code>}, respectively. + * Further, let <i>e</i> = <i>n</i> + <i>i</i> - 1 and let + * <i>d</i>₁…<i>d</i>_<i>n</i> + * be the usual decimal expansion of the significand. + * Note that <i>d</i>₁ ≠ 0 ≠ <i>d</i>_<i>n</i>. + * <ul> + * <li>Case -3 ≤ <i>e</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <code>0.0</code>…<code>0</code><!-- + * --><i>d</i>₁…<i>d</i>_<i>n</i>, + * where there are exactly -(<i>n</i> + <i>i</i>) zeroes between + * the decimal point and <i>d</i>₁. + * For example, 123 × 10^-4 is formatted as + * {@code 0.0123}. + * <li>Case 0 ≤ <i>e</i> < 7: + * <ul> + * <li>Subcase <i>i</i> ≥ 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<i>d</i>_<i>n</i><!-- + * --><code>0</code>…<code>0.0</code>, + * where there are exactly <i>i</i> zeroes + * between <i>d</i>_<i>n</i> and the decimal point. + * For example, 123 × 10² is formatted as + * {@code 12300.0}. + * <li>Subcase <i>i</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>}.<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>+1}…<!-- + * --><i>d</i>_<i>n</i>. + * There are exactly -<i>i</i> digits to the right of + * the decimal point. + * For example, 123 × 10^-1 is formatted as + * {@code 12.3}. + * </ul> + * <li>Case <i>e</i> < -3 or <i>e</i> ≥ 7: + * computerized scientific notation is used to format + * <i>d</i>_{<code>v</code>}. + * Here <i>e</i> is formatted as by {@link Integer#toString(int)}. + * <ul> + * <li>Subcase <i>n</i> = 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.0E</code><i>e</i>. + * For example, 1 × 10²³ is formatted as + * {@code 1.0E23}. + * <li>Subcase <i>n</i> > 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.</code><i>d</i>₂<!-- + * -->…<i>d</i>_<i>n</i><code>E</code><i>e</i>. + * For example, 123 × 10^-21 is formatted as + * {@code 1.23E-19}. + * </ul> + * </ul> * - * @param f the float to be converted. - * @return a string representation of the argument. + * @param v the {@code float} to be rendered. + * @return a string rendering of the argument. */ public static String toString(float f) { - return FloatingDecimal.toJavaFormatString(f); + return FloatToDecimal.toString(f); } /** diff --git a/src/java.base/share/classes/jdk/internal/math/DoubleToDecimal.java b/src/java.base/share/classes/jdk/internal/math/DoubleToDecimal.java new file mode 100644 --- /dev/null +++ b/src/java.base/share/classes/jdk/internal/math/DoubleToDecimal.java @@ -0,0 +1,508 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +package jdk.internal.math; + +import static java.lang.Double.*; +import static java.lang.Long.numberOfLeadingZeros; +import static java.lang.Math.multiplyHigh; +import static jdk.internal.math.MathUtils.*; + +/** + * This class exposes a method to render a {@code double} as a string. + * + * @author Raffaello Giulietti + */ +final public class DoubleToDecimal { + /* + For full details about this code see the following references: + + [1] Giulietti, "The Schubfach way to render doubles", + https://drive.google.com/open?id=1KLtG_LaIbK9ETXI290zqCxvBW94dj058 + + [2] IEEE Computer Society, "IEEE Standard for Floating-Point Arithmetic" + + [3] Moeller & Granlund, "Improved division by invariant integers" + + [4] Bouvier & Zimmermann, "Division-Free Binary-to-Decimal Conversion" + */ + + // The precision in bits. + private static final int P = 53; + + // Exponent width in bits. + private static final int W = (Double.SIZE - 1) - (P - 1); + + // Minimum value of the exponent: -(2^(W-1)) - P + 3. + private static final int Q_MIN = (-1 << W - 1) - P + 3; + + // Minimum value of the significand of a normal value: 2^(P-1). + private static final long C_MIN = 1L << P - 1; + + // Mask to extract the biased exponent. + private static final int BQ_MASK = (1 << W) - 1; + + // Mask to extract the fraction bits. + private static final long T_MASK = (1L << P - 1) - 1; + + /* + H is the minimal number of decimal digits needed to ensure that + for all finite v, round-to-half-even(toString(v)) = v + */ + private static final int H = 17; + + // Used in rop(). + private static final long MASK_63 = (1L << 63) - 1; + + // Used for digit extraction in toChars() and its dependencies. + private static final int MASK_28 = (1 << 28) - 1; + + // For thread-safety, each thread gets its own instance of this class. + private static final ThreadLocal<DoubleToDecimal> threadLocal = + ThreadLocal.withInitial(DoubleToDecimal::new); + + /* + Room for the longer of the forms + -ddddd.dddddddddddd H + 2 characters + -0.00ddddddddddddddddd H + 5 characters + -d.ddddddddddddddddE-eee H + 7 characters + where there are H digits d + */ + private final byte[] buf = new byte[H + 7]; + + // Index into buf of rightmost valid character. + private int index; + + private DoubleToDecimal() { + } + + /** + * Returns a string rendering of the {@code double} argument. + * + * <p>The characters of the result are all drawn from the ASCII set. + * <ul> + * <li> Any NaN, whether quiet or signaling, is rendered as + * {@code "NaN"}, regardless of the sign bit. + * <li> The infinities +∞ and -∞ are rendered as + * {@code "Infinity"} and {@code "-Infinity"}, respectively. + * <li> The positive and negative zeroes are rendered as + * {@code "0.0"} and {@code "-0.0"}, respectively. + * <li> A finite negative {@code v} is rendered as the sign + * '{@code -}' followed by the rendering of the magnitude -{@code v}. + * <li> A finite positive {@code v} is rendered in two stages: + * <ul> + * <li> <em>Selection of a decimal</em>: A well-defined + * decimal <i>d</i>_{<code>v</code>} is selected + * to represent {@code v}. + * <li> <em>Formatting as a string</em>: The decimal + * <i>d</i>_{<code>v</code>} is formatted as a string, + * either in plain or in computerized scientific notation, + * depending on its value. + * </ul> + * </ul> + * + * <p>A <em>decimal</em> is a number of the form + * <i>d</i>×10^<i>i</i> + * for some (unique) integers <i>d</i> > 0 and <i>i</i> such that + * <i>d</i> is not a multiple of 10. + * These integers are the <em>significand</em> and + * the <em>exponent</em>, respectively, of the decimal. + * The <em>length</em> of the decimal is the (unique) + * integer <i>n</i> meeting + * 10^<i>n</i>-1 ≤ <i>d</i> < 10^<i>n</i>. + * + * <p>The decimal <i>d</i>_{<code>v</code>} + * for a finite positive {@code v} is defined as follows: + * <ul> + * <li>Let <i>R</i> be the set of all decimals that round to {@code v} + * according to the usual round-to-closest rule of + * IEEE 754 floating-point arithmetic. + * <li>Let <i>m</i> be the minimal length over all decimals in <i>R</i>. + * <li>When <i>m</i> ≥ 2, let <i>T</i> be the set of all decimals + * in <i>R</i> with length <i>m</i>. + * Otherwise, let <i>T</i> be the set of all decimals + * in <i>R</i> with length 1 or 2. + * <li>Define <i>d</i>_{<code>v</code>} as + * the decimal in <i>T</i> that is closest to {@code v}. + * Or if there are two such decimals in <i>T</i>, + * select the one with the even significand (there is exactly one). + * </ul> + * + * <p>The (uniquely) selected decimal <i>d</i>_{<code>v</code>} + * is then formatted. + * + * <p>Let <i>d</i>, <i>i</i> and <i>n</i> be the significand, exponent and + * length of <i>d</i>_{<code>v</code>}, respectively. + * Further, let <i>e</i> = <i>n</i> + <i>i</i> - 1 and let + * <i>d</i>₁…<i>d</i>_<i>n</i> + * be the usual decimal expansion of the significand. + * Note that <i>d</i>₁ ≠ 0 ≠ <i>d</i>_<i>n</i>. + * <ul> + * <li>Case -3 ≤ <i>e</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <code>0.0</code>…<code>0</code><!-- + * --><i>d</i>₁…<i>d</i>_<i>n</i>, + * where there are exactly -(<i>n</i> + <i>i</i>) zeroes between + * the decimal point and <i>d</i>₁. + * For example, 123 × 10^-4 is formatted as + * {@code 0.0123}. + * <li>Case 0 ≤ <i>e</i> < 7: + * <ul> + * <li>Subcase <i>i</i> ≥ 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<i>d</i>_<i>n</i><!-- + * --><code>0</code>…<code>0.0</code>, + * where there are exactly <i>i</i> zeroes + * between <i>d</i>_<i>n</i> and the decimal point. + * For example, 123 × 10² is formatted as + * {@code 12300.0}. + * <li>Subcase <i>i</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>}.<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>+1}…<!-- + * --><i>d</i>_<i>n</i>. + * There are exactly -<i>i</i> digits to the right of + * the decimal point. + * For example, 123 × 10^-1 is formatted as + * {@code 12.3}. + * </ul> + * <li>Case <i>e</i> < -3 or <i>e</i> ≥ 7: + * computerized scientific notation is used to format + * <i>d</i>_{<code>v</code>}. + * Here <i>e</i> is formatted as by {@link Integer#toString(int)}. + * <ul> + * <li>Subcase <i>n</i> = 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.0E</code><i>e</i>. + * For example, 1 × 10²³ is formatted as + * {@code 1.0E23}. + * <li>Subcase <i>n</i> > 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.</code><i>d</i>₂<!-- + * -->…<i>d</i>_<i>n</i><code>E</code><i>e</i>. + * For example, 123 × 10^-21 is formatted as + * {@code 1.23E-19}. + * </ul> + * </ul> + * + * @param v the {@code double} to be rendered. + * @return a string rendering of the argument. + */ + public static String toString(double v) { + return threadLocalInstance().toDecimal(v); + } + + private static DoubleToDecimal threadLocalInstance() { + return threadLocal.get(); + } + + private String toDecimal(double v) { + /* + For details not discussed here see reference [2]. + + Let + Q_MAX = 2^(W-1) - P + C_MAX = 2^P - 1 + For finite v != 0, determine integers c and q such that + |v| = c 2^q and + Q_MIN <= q <= Q_MAX and + either C_MIN <= c <= C_MAX (normal value) + or 0 < c < C_MIN and q = Q_MIN (subnormal value) + */ + long bits = doubleToRawLongBits(v); + long t = bits & T_MASK; + int bq = (int) (bits >>> P - 1) & BQ_MASK; + if (bq < BQ_MASK) { + index = -1; + if (bits < 0) { + append('-'); + } + if (bq != 0) { + // normal value + return toDecimal(Q_MIN - 1 + bq, C_MIN | t); + } + if (t != 0) { + // subnormal value + return toDecimal(Q_MIN, t); + } + return bits == 0 ? "0.0" : "-0.0"; + } + if (t != 0) { + return "NaN"; + } + return bits > 0 ? "Infinity" : "-Infinity"; + } + + private String toDecimal(int q, long c) { + // For full details see reference [1]. + int out = (int) c & 0x1; + long cb; + long cbr; + long cbl; + int k; + int h; + if (c != C_MIN | q == Q_MIN) { + // regular spacing + cb = c << 1; + cbr = cb + 1; + k = flog10pow2(q); + h = q + flog2pow10(-k) + 3; + } else { + // irregular spacing + cb = c << 2; + cbr = cb + 2; + k = flog10threeQuartersPow2(q); + h = q + flog2pow10(-k) + 2; + } + cbl = cb - 1; + + long g1 = g1(-k); + long g0 = g0(-k); + long vb = rop(g1, g0, cb << h); + long vbl = rop(g1, g0, cbl << h); + long vbr = rop(g1, g0, cbr << h); + + long s = vb >> 2; + if (s >= 100) { + /* + sp10 = 10 s', tp10 = 10 t' = sp10 + 10 + This is the only place where a division (the %) is carried out. + */ + long sp10 = s - s % 10; + long tp10 = sp10 + 10; + boolean upin = vbl + out <= sp10 << 2; + boolean wpin = (tp10 << 2) + out <= vbr; + if (upin != wpin) { + return toChars(upin ? sp10 : tp10, k); + } + } else if (s < 10) { + switch ((int) s) { + case 4: + return toChars(49, -325); // 4.9 10^(-324) + case 9: + return toChars(99, -325); // 9.9 10^(-324) + } + } + long t = s + 1; + boolean uin = vbl + out <= s << 2; + boolean win = (t << 2) + out <= vbr; + if (uin != win) { + // Exactly one of s 10^k or t 10^k lies in Rv. + return toChars(uin ? s : t, k); + } + // Both s 10^k and t 10^k lie in Rv: determine the one closest to v. + long cmp = vb - (s + t << 1); + return toChars(cmp < 0 || cmp == 0 && (s & 0x1) == 0 ? s : t, k); + } + + private static long rop(long g1, long g0, long cp) { + // For full details see reference [1]. + long x1 = multiplyHigh(g0, cp); + long y0 = g1 * cp; + long y1 = multiplyHigh(g1, cp); + long z = (y0 >>> 1) + x1; + long vbp = y1 + (z >>> 63); + return vbp | (z & MASK_63) + MASK_63 >>> 63; + } + + /* + Formats the decimal f 10^e. + */ + private String toChars(long f, int e) { + /* + For details not discussed here see reference [3]. + + Determine len such that + 10^(len-1) <= f < 10^len + */ + int len = flog10pow2(Long.SIZE - numberOfLeadingZeros(f)); + if (f >= pow10[len]) { + len += 1; + } + + /* + Let fp and ep be the original f and e, respectively. + Transform f and e to ensure + 10^(H-1) <= f < 10^H + fp 10^ep = f 10^(e-H) = 0.f 10^e + */ + f *= pow10[H - len]; + e += len; + + /* + The toChars?() methods perform left-to-right digits extraction + using ints, provided that the arguments are limited to 8 digits. + Therefore, split the H = 17 digits of f into: + h = the most significant digit of f + m = the next 8 most significant digits of f + l = the last 8, least significant digits of f + + To avoid divisions, it can be shown ([3]) that + floor(f / 10^8) = + floor(193'428'131'138'340'668 f / 2^84) = + floor(48'357'032'784'585'167 f / 2^82) = + floor(floor(48'357'032'784'585'167 f / 2^64) / 2^18) + and similarly + floor(hm / 10^8) = floor(1'441'151'881 hm / 2^57) + */ + long hm = multiplyHigh(f, 48_357_032_784_585_167L) >>> 18; + int l = (int) (f - 100_000_000L * hm); + int h = (int) (hm * 1_441_151_881L >>> 57); + int m = (int) (hm - 100_000_000 * h); + + if (0 < e && e <= 7) { + return toChars1(h, m, l, e); + } + if (-3 < e && e <= 0) { + return toChars2(h, m, l, e); + } + return toChars3(h, m, l, e); + } + + private String toChars1(int h, int m, int l, int e) { + /* + 0 < e <= 7: plain format without leading zeroes. + The left-to-right digits generation is inspired by [4]. + */ + appendDigit(h); + int y = y(m); + int t; + int i = 1; + for (; i < e; ++i) { + t = 10 * y; + appendDigit(t >>> 28); + y = t & MASK_28; + } + append('.'); + for (; i <= 8; ++i) { + t = 10 * y; + appendDigit(t >>> 28); + y = t & MASK_28; + } + lowDigits(l); + return charsToString(); + } + + private String toChars2(int h, int m, int l, int e) { + // -3 < e <= 0: plain format with leading zeroes. + appendDigit(0); + append('.'); + for (; e < 0; ++e) { + appendDigit(0); + } + appendDigit(h); + append8Digits(m); + lowDigits(l); + return charsToString(); + } + + private String toChars3(int h, int m, int l, int e) { + // -3 >= e | e > 7: computerized scientific notation + appendDigit(h); + append('.'); + append8Digits(m); + lowDigits(l); + exponent(e - 1); + return charsToString(); + } + + private void lowDigits(int l) { + if (l != 0) { + append8Digits(l); + } + removeTrailingZeroes(); + } + + private void append8Digits(int m) { + // The left-to-right digits generation is inspired by [4] + int y = y(m); + for (int i = 0; i < 8; ++i) { + int t = 10 * y; + appendDigit(t >>> 28); + y = t & MASK_28; + } + } + + private void removeTrailingZeroes() { + while (buf[index] == '0') { + --index; + } + if (buf[index] == '.') { + ++index; + } + } + + /* + Computes floor((m + 1) 2^28 / 10^8) - 1, needed by [4], as in [3] + */ + private int y(int m) { + return (int) (multiplyHigh( + (long) (m + 1) << 28, + 48_357_032_784_585_167L) >>> 18) - 1; + } + + private void exponent(int e) { + append('E'); + if (e < 0) { + append('-'); + e = -e; + } + if (e < 10) { + appendDigit(e); + return; + } + /* + It can be shown ([3]) that + floor(e / 10) = floor(205 e / 2^11) + floor(e / 100) = floor(1'311 e / 2^17) + */ + if (e < 100) { + int d = e * 205 >>> 11; + appendDigit(d); + appendDigit(e - 10 * d); + return; + } + int d = e * 1_311 >>> 17; + appendDigit(d); + e -= 100 * d; + d = e * 205 >>> 11; + appendDigit(d); + appendDigit(e - 10 * d); + } + + private void append(int c) { + buf[++index] = (byte) c; + } + + private void appendDigit(int d) { + buf[++index] = (byte) ('0' + d); + } + + /* + Using the deprecated, yet public constructor enhances performance. + */ + private String charsToString() { + return new String(buf, 0, 0, index + 1); + } + +} diff --git a/src/java.base/share/classes/jdk/internal/math/FloatToDecimal.java b/src/java.base/share/classes/jdk/internal/math/FloatToDecimal.java new file mode 100644 --- /dev/null +++ b/src/java.base/share/classes/jdk/internal/math/FloatToDecimal.java @@ -0,0 +1,482 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +package jdk.internal.math; + +import static java.lang.Float.*; +import static java.lang.Integer.numberOfLeadingZeros; +import static java.lang.Math.multiplyHigh; +import static jdk.internal.math.MathUtils.*; + +/** + * This class exposes a method to render a {@code float} as a string. + * + * @author Raffaello Giulietti + */ +final public class FloatToDecimal { + /* + For full details about this code see the following references: + + [1] Giulietti, "The Schubfach way to render doubles", + https://drive.google.com/open?id=1KLtG_LaIbK9ETXI290zqCxvBW94dj058 + + [2] IEEE Computer Society, "IEEE Standard for Floating-Point Arithmetic" + + [3] Moeller & Granlund, "Improved division by invariant integers" + + [4] Bouvier & Zimmermann, "Division-Free Binary-to-Decimal Conversion" + */ + + // The precision in bits. + private static final int P = 24; + + // Exponent width in bits. + private static final int W = (Float.SIZE - 1) - (P - 1); + + // Minimum value of the exponent: -(2^(W-1)) - P + 3. + private static final int Q_MIN = (-1 << W - 1) - P + 3; + + // Minimum value of the significand of a normal value: 2^(P-1). + private static final int C_MIN = 1 << P - 1; + + // Mask to extract the biased exponent. + private static final int BQ_MASK = (1 << W) - 1; + + // Mask to extract the fraction bits. + private static final int T_MASK = (1 << P - 1) - 1; + + /* + H is the minimal number of decimal digits needed to ensure that + for all finite v, round-to-half-even(toString(v)) = v + */ + private static final int H = 9; + + // Used in rop(). + private static final long MASK_31 = (1L << 31) - 1; + + // Used for digit extraction in toChars() and its dependencies. + private static final int MASK_28 = (1 << 28) - 1; + + // For thread-safety, each thread gets its own instance of this class. + private static final ThreadLocal<FloatToDecimal> threadLocal = + ThreadLocal.withInitial(FloatToDecimal::new); + + /* + Room for the longer of the forms + -ddddd.dddd H + 2 characters + -0.00ddddddddd H + 5 characters + -d.ddddddddE-ee H + 6 characters + where there are H digits d + */ + private final byte[] buf = new byte[H + 6]; + + // Index into buf of rightmost valid character. + private int index; + + private FloatToDecimal() { + } + + /** + * Returns a string rendering of the {@code float} argument. + * + * <p>The characters of the result are all drawn from the ASCII set. + * <ul> + * <li> Any NaN, whether quiet or signaling, is rendered as + * {@code "NaN"}, regardless of the sign bit. + * <li> The infinities +∞ and -∞ are rendered as + * {@code "Infinity"} and {@code "-Infinity"}, respectively. + * <li> The positive and negative zeroes are rendered as + * {@code "0.0"} and {@code "-0.0"}, respectively. + * <li> A finite negative {@code v} is rendered as the sign + * '{@code -}' followed by the rendering of the magnitude -{@code v}. + * <li> A finite positive {@code v} is rendered in two stages: + * <ul> + * <li> <em>Selection of a decimal</em>: A well-defined + * decimal <i>d</i>_{<code>v</code>} is selected + * to represent {@code v}. + * <li> <em>Formatting as a string</em>: The decimal + * <i>d</i>_{<code>v</code>} is formatted as a string, + * either in plain or in computerized scientific notation, + * depending on its value. + * </ul> + * </ul> + * + * <p>A <em>decimal</em> is a number of the form + * <i>d</i>×10^<i>i</i> + * for some (unique) integers <i>d</i> > 0 and <i>i</i> such that + * <i>d</i> is not a multiple of 10. + * These integers are the <em>significand</em> and + * the <em>exponent</em>, respectively, of the decimal. + * The <em>length</em> of the decimal is the (unique) + * integer <i>n</i> meeting + * 10^<i>n</i>-1 ≤ <i>d</i> < 10^<i>n</i>. + * + * <p>The decimal <i>d</i>_{<code>v</code>} + * for a finite positive {@code v} is defined as follows: + * <ul> + * <li>Let <i>R</i> be the set of all decimals that round to {@code v} + * according to the usual round-to-closest rule of + * IEEE 754 floating-point arithmetic. + * <li>Let <i>m</i> be the minimal length over all decimals in <i>R</i>. + * <li>When <i>m</i> ≥ 2, let <i>T</i> be the set of all decimals + * in <i>R</i> with length <i>m</i>. + * Otherwise, let <i>T</i> be the set of all decimals + * in <i>R</i> with length 1 or 2. + * <li>Define <i>d</i>_{<code>v</code>} as + * the decimal in <i>T</i> that is closest to {@code v}. + * Or if there are two such decimals in <i>T</i>, + * select the one with the even significand (there is exactly one). + * </ul> + * + * <p>The (uniquely) selected decimal <i>d</i>_{<code>v</code>} + * is then formatted. + * + * <p>Let <i>d</i>, <i>i</i> and <i>n</i> be the significand, exponent and + * length of <i>d</i>_{<code>v</code>}, respectively. + * Further, let <i>e</i> = <i>n</i> + <i>i</i> - 1 and let + * <i>d</i>₁…<i>d</i>_<i>n</i> + * be the usual decimal expansion of the significand. + * Note that <i>d</i>₁ ≠ 0 ≠ <i>d</i>_<i>n</i>. + * <ul> + * <li>Case -3 ≤ <i>e</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <code>0.0</code>…<code>0</code><!-- + * --><i>d</i>₁…<i>d</i>_<i>n</i>, + * where there are exactly -(<i>n</i> + <i>i</i>) zeroes between + * the decimal point and <i>d</i>₁. + * For example, 123 × 10^-4 is formatted as + * {@code 0.0123}. + * <li>Case 0 ≤ <i>e</i> < 7: + * <ul> + * <li>Subcase <i>i</i> ≥ 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<i>d</i>_<i>n</i><!-- + * --><code>0</code>…<code>0.0</code>, + * where there are exactly <i>i</i> zeroes + * between <i>d</i>_<i>n</i> and the decimal point. + * For example, 123 × 10² is formatted as + * {@code 12300.0}. + * <li>Subcase <i>i</i> < 0: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁…<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>}.<!-- + * --><i>d</i>_{<i>n</i>+<i>i</i>+1}…<!-- + * --><i>d</i>_<i>n</i>. + * There are exactly -<i>i</i> digits to the right of + * the decimal point. + * For example, 123 × 10^-1 is formatted as + * {@code 12.3}. + * </ul> + * <li>Case <i>e</i> < -3 or <i>e</i> ≥ 7: + * computerized scientific notation is used to format + * <i>d</i>_{<code>v</code>}. + * Here <i>e</i> is formatted as by {@link Integer#toString(int)}. + * <ul> + * <li>Subcase <i>n</i> = 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.0E</code><i>e</i>. + * For example, 1 × 10²³ is formatted as + * {@code 1.0E23}. + * <li>Subcase <i>n</i> > 1: + * <i>d</i>_{<code>v</code>} is formatted as + * <i>d</i>₁<code>.</code><i>d</i>₂<!-- + * -->…<i>d</i>_<i>n</i><code>E</code><i>e</i>. + * For example, 123 × 10^-21 is formatted as + * {@code 1.23E-19}. + * </ul> + * </ul> + * + * @param v the {@code float} to be rendered. + * @return a string rendering of the argument. + */ + public static String toString(float v) { + return threadLocalInstance().toDecimal(v); + } + + private static FloatToDecimal threadLocalInstance() { + return threadLocal.get(); + } + + private String toDecimal(float v) { + /* + For details not discussed here see reference [2]. + + Let + Q_MAX = 2^(W-1) - P + C_MAX = 2^P - 1 + For finite v != 0, determine integers c and q such that + |v| = c 2^q and + Q_MIN <= q <= Q_MAX and + either C_MIN <= c <= C_MAX (normal value) + or 0 < c < C_MIN and q = Q_MIN (subnormal value) + */ + int bits = floatToRawIntBits(v); + int t = bits & T_MASK; + int bq = (bits >>> P - 1) & BQ_MASK; + if (bq < BQ_MASK) { + index = -1; + if (bits < 0) { + append('-'); + } + if (bq != 0) { + // normal value + return toDecimal(Q_MIN - 1 + bq, C_MIN | t); + } + if (t != 0) { + // subnormal value + return toDecimal(Q_MIN, t); + } + return bits == 0 ? "0.0" : "-0.0"; + } + if (t != 0) { + return "NaN"; + } + return bits > 0 ? "Infinity" : "-Infinity"; + } + + private String toDecimal(int q, int c) { + // For full details see reference [1]. + int out = c & 0x1; + long cb; + long cbr; + long cbl; + int k; + int h; + if (c != C_MIN | q == Q_MIN) { + // regular spacing + cb = c << 1; + cbr = cb + 1; + k = flog10pow2(q); + h = q + flog2pow10(-k) + 34; + } else { + // irregular spacing + cb = c << 2; + cbr = cb + 2; + k = flog10threeQuartersPow2(q); + h = q + flog2pow10(-k) + 33; + } + cbl = cb - 1; + + long g = g1(-k) + 1; + int vb = rop(g, cb << h); + int vbl = rop(g, cbl << h); + int vbr = rop(g, cbr << h); + + int s = vb >> 2; + if (s >= 100) { + /* + sp10 = 10 s', tp10 = 10 t' = sp10 + 10 + This is the only place where a division (the %) is carried out. + */ + int sp10 = s - s % 10; + int tp10 = sp10 + 10; + boolean upin = vbl + out <= sp10 << 2; + boolean wpin = (tp10 << 2) + out <= vbr; + if (upin != wpin) { + return toChars(upin ? sp10 : tp10, k); + } + } else if (s < 10) { + switch (s) { + case 1: return toChars(14, -46); // 1.4 * 10^-45 + case 2: return toChars(28, -46); // 2.8 * 10^-45 + case 4: return toChars(42, -46); // 4.2 * 10^-45 + case 5: return toChars(56, -46); // 5.6 * 10^-45 + case 7: return toChars(70, -46); // 7.0 * 10^-45 + case 8: return toChars(84, -46); // 8.4 * 10^-45 + case 9: return toChars(98, -46); // 9.8 * 10^-45 + } + } + int t = s + 1; + boolean uin = vbl + out <= s << 2; + boolean win = (t << 2) + out <= vbr; + if (uin != win) { + // Exactly one of s 10^k or t 10^k lies in Rv. + return toChars(uin ? s : t, k); + } + // Both s 10^k and t 10^k lie in Rv: determine the one closest to v. + int cmp = vb - (s + t << 1); + return toChars(cmp < 0 || cmp == 0 && (s & 0x1) == 0 ? s : t, k); + } + + private static int rop(long g, long cp) { + // For full details see reference [1]. + long x1 = multiplyHigh(g, cp); + long vbp = x1 >> 31; + return (int) (vbp | (x1 & MASK_31) + MASK_31 >>> 31); + } + + /* + Formats the decimal f 10^e. + */ + private String toChars(int f, int e) { + /* + For details not discussed here see reference [3]. + + Determine len such that + 10^(len-1) <= f < 10^len + */ + int len = flog10pow2(Integer.SIZE - numberOfLeadingZeros(f)); + if (f >= pow10[len]) { + len += 1; + } + + /* + Let fp and ep be the original f and e, respectively. + Transform f and e to ensure + 10^(H-1) <= f < 10^H + fp 10^ep = f 10^(e-H) = 0.f 10^e + */ + f *= pow10[H - len]; + e += len; + + /* + The toChars?() methods perform left-to-right digits extraction + using ints, provided that the arguments are limited to 8 digits. + Therefore, split the H = 9 digits of f into: + h = the most significant digit of f + l = the last 8, least significant digits of f + + To avoid divisions, it can be shown ([3]) that + floor(f / 10^8) = floor(1'441'151'881 f / 2^57) + */ + int h = (int) (f * 1_441_151_881L >>> 57); + int l = f - 100_000_000 * h; + + if (0 < e && e <= 7) { + return toChars1(h, l, e); + } + if (-3 < e && e <= 0) { + return toChars2(h, l, e); + } + return toChars3(h, l, e); + } + + private String toChars1(int h, int l, int e) { + /* + 0 < e <= 7: plain format without leading zeroes. + The left-to-right digits generation is inspired by [4]. + */ + appendDigit(h); + int y = y(l); + int t; + int i = 1; + for (; i < e; ++i) { + t = 10 * y; + appendDigit(t >>> 28); + y = t & MASK_28; + } + append('.'); + for (; i <= 8; ++i) { + t = 10 * y; + appendDigit(t >>> 28); + y = t & MASK_28; + } + removeTrailingZeroes(); + return charsToString(); + } + + private String toChars2(int h, int l, int e) { + // -3 < e <= 0: plain format with leading zeroes. + appendDigit(0); + append('.'); + for (; e < 0; ++e) { + appendDigit(0); + } + appendDigit(h); + append8Digits(l); + removeTrailingZeroes(); + return charsToString(); + } + + private String toChars3(int h, int l, int e) { + // -3 >= e | e > 7: computerized scientific notation + appendDigit(h); + append('.'); + append8Digits(l); + removeTrailingZeroes(); + exponent(e - 1); + return charsToString(); + } + + private void append8Digits(int m) { + // The left-to-right digits generation is inspired by [4] + int y = y(m); + for (int i = 0; i < 8; ++i) { + int t = 10 * y; + appendDigit(t >>> 28); + y = t & MASK_28; + } + } + + private void removeTrailingZeroes() { + while (buf[index] == '0') { + --index; + } + if (buf[index] == '.') { + ++index; + } + } + + /* + Computes floor((m + 1) 2^28 / 10^8) - 1, needed by [4], as in [3] + */ + private int y(int m) { + return (int) (multiplyHigh( + (long) (m + 1) << 28, + 48_357_032_784_585_167L) >>> 18) - 1; + } + + private void exponent(int e) { + append('E'); + if (e < 0) { + append('-'); + e = -e; + } + if (e < 10) { + appendDigit(e); + return; + } + /* + It can be shown ([3]) that + floor(e / 10) = floor(205 e / 2^11) + */ + int d = e * 205 >>> 11; + appendDigit(d); + appendDigit(e - 10 * d); + } + + private void append(int c) { + buf[++index] = (byte) c; + } + + private void appendDigit(int d) { + buf[++index] = (byte) ('0' + d); + } + + /* + Using the deprecated, yet public constructor enhances performance. + */ + private String charsToString() { + return new String(buf, 0, 0, index + 1); + } + +} diff --git a/src/java.base/share/classes/jdk/internal/math/MathUtils.java b/src/java.base/share/classes/jdk/internal/math/MathUtils.java new file mode 100644 --- /dev/null +++ b/src/java.base/share/classes/jdk/internal/math/MathUtils.java @@ -0,0 +1,794 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +package jdk.internal.math; + +/** + * This class exposes package private utilities for other classes. + * + * All methods are assumed to be invoked with correct arguments, so they are + * not checked at all. + * + * @author Raffaello Giulietti + */ +final class MathUtils { + /* + For full details about this code see the following reference: + + Giulietti, "The Schubfach way to render doubles", + https://drive.google.com/open?id=1KLtG_LaIbK9ETXI290zqCxvBW94dj058 + */ + + // C_10 = floor(log10(2) * 2^Q_10), A_10 = floor(log10(3/4) * 2^Q_10) + private static final int Q_10 = 41; + private static final long C_10 = 661_971_961_083L; + private static final long A_10 = -274_743_187_321L; + + // C_2 = floor(log2(10) * 2^Q_2) + private static final int Q_2 = 38; + private static final long C_2 = 913_124_641_741L; + + // The minimum and maximum exponents for g1(int) + static final int MIN_EXP = -292; + static final int MAX_EXP = 324; + + private MathUtils() { + } + + // pow10[e] = 10^e, 0 <= e <= 17 + static final long[] pow10 = { + 1L, + 10L, + 100L, + 1_000L, + 10_000L, + 100_000L, + 1_000_000L, + 10_000_000L, + 100_000_000L, + 1_000_000_000L, + 10_000_000_000L, + 100_000_000_000L, + 1_000_000_000_000L, + 10_000_000_000_000L, + 100_000_000_000_000L, + 1_000_000_000_000_000L, + 10_000_000_000_000_000L, + 100_000_000_000_000_000L, + }; + + /** + * Returns the unique integer <i>k</i> such that + * 10^<i>k</i> ≤ 2^{{@code e}} + * < 10^<i>k</i>+1. + * <p> + * The result is correct when |{@code e}| ≤ 5_456_721. + * Otherwise the result is undefined. + * + * @param e The exponent of 2, which should meet + * |{@code e}| ≤ 5_456_721 for safe results. + * @return ⌊log₁₀2^{{@code e}}⌋. + */ + static int flog10pow2(int e) { + return (int) (e * C_10 >> Q_10); + } + + /** + * Returns the unique integer <i>k</i> such that + * 10^<i>k</i> ≤ 3/4 · 2^{{@code e}} + * < 10^<i>k</i>+1. + * <p> + * The result is correct when + * -2_956_395 ≤ |{@code e}| ≤ 2_500_325. + * Otherwise the result is undefined. + * + * @param e The exponent of 2, which should meet + * -2_956_395 ≤ |{@code e}| ≤ 2_500_325 for safe results. + * @return ⌊log₁₀(3/4 · + * 2^{{@code e}})⌋. + */ + static int flog10threeQuartersPow2(int e) { + return (int) (e * C_10 + A_10 >> Q_10); + } + + /** + * Returns the unique integer <i>k</i> such that + * 2^<i>k</i> ≤ 10^{{@code e}} + * < 2^<i>k</i>+1. + * <p> + * The result is correct when |{@code e}| ≤ 1_838_394. + * Otherwise the result is undefined. + * + * @param e The exponent of 10, which should meet + * |{@code e}| ≤ 1_838_394 for safe results. + * @return ⌊log₂10^{{@code e}}⌋. + */ + static int flog2pow10(int e) { + return (int) (e * C_2 >> Q_2); + } + + /** + * Let 10^{{@code e}} = <i>β</i> 2^<i>r</i>, + * for the unique pair of integer <i>r</i> and real <i>β</i> meeting + * 2¹²⁵ ≤ <i>β</i> < 2¹²⁶. + * Further, let <i>g</i> = ⌊<i>β</i>⌋ + 1. + * Split <i>g</i> into the higher 63 bits <i>g</i>₁ and + * the lower 63 bits <i>g</i>₀. Thus, + * <i>g</i>₁ = + * ⌊<i>g</i> 2^-63⌋ + * and + * <i>g</i>₀ = + * <i>g</i> - <i>g</i>₁ 2⁶³. + * <p> + * This method returns <i>g</i>₁ while + * {@link #g0(int)} returns <i>g</i>₀. + * <p> + * If needed, the exponent <i>r</i> can be computed as + * <i>r</i> = {@code flog2pow10(e)} - 125 (see {@link #flog2pow10(int)}). + * + * @param e The exponent of 10, + * which must meet {@link #MIN_EXP} ≤ {@code e} ≤ + * {@link #MAX_EXP}. + * @return <i>g</i>₁ as described above. + */ + static long g1(int e) { + return g[e - MIN_EXP << 1]; + } + + /** + * Returns <i>g</i>₀ as described in + * {@link #g1(int)}. + * + * @param e The exponent of 10, + * which must meet {@link #MIN_EXP} ≤ {@code e} ≤ + * {@link #MAX_EXP}. + * @return <i>g</i>₀ as described in + * {@link #g1(int)}. + */ + static long g0(int e) { + return g[e - MIN_EXP << 1 | 1]; + } + + /** + * The precomputed values for {@link #g1(int)} and {@link #g0(int)}. + */ + private static final long[] g = { + /* -292 */ 0x7FBB_D8FE_5F5E_6E27L, 0x497A_3A27_04EE_C3DFL, + /* -291 */ 0x4FD5_679E_FB9B_04D8L, 0x5DEC_6458_6315_3A6CL, + /* -290 */ 0x63CA_C186_BA81_C60EL, 0x7567_7D6E_7BDA_8906L, + /* -289 */ 0x7CBD_71E8_6922_3792L, 0x52C1_5CCA_1AD1_2B48L, + /* -288 */ 0x4DF6_6731_41B5_62BBL, 0x53B8_D9FE_50C2_BB0DL, + /* -287 */ 0x6174_00FD_9222_BB6AL, 0x48A7_107D_E4F3_69D0L, + /* -286 */ 0x79D1_013C_F6AB_6A45L, 0x1AD0_D49D_5E30_4444L, + /* -285 */ 0x4C22_A0C6_1A2B_226BL, 0x20C2_84E2_5ADE_2AABL, + /* -284 */ 0x5F2B_48F7_A0B5_EB06L, 0x08F3_261A_F195_B555L, + /* -283 */ 0x76F6_1B35_88E3_65C7L, 0x4B2F_EFA1_ADFB_22ABL, + /* -282 */ 0x4A59_D101_758E_1F9CL, 0x5EFD_F5C5_0CBC_F5ABL, + /* -281 */ 0x5CF0_4541_D2F1_A783L, 0x76BD_7336_4FEC_3315L, + /* -280 */ 0x742C_5692_47AE_1164L, 0x746C_D003_E3E7_3FDBL, + /* -279 */ 0x489B_B61B_6CCC_CADFL, 0x08C4_0202_6E70_87E9L, + /* -278 */ 0x5AC2_A3A2_47FF_FD96L, 0x6AF5_0283_0A0C_A9E3L, + /* -277 */ 0x7173_4C8A_D9FF_FCFCL, 0x45B2_4323_CC8F_D45CL, + /* -276 */ 0x46E8_0FD6_C83F_FE1DL, 0x6B8F_69F6_5FD9_E4B9L, + /* -275 */ 0x58A2_13CC_7A4F_FDA5L, 0x2673_4473_F7D0_5DE8L, + /* -274 */ 0x6ECA_98BF_98E3_FD0EL, 0x5010_1590_F5C4_7561L, + /* -273 */ 0x453E_9F77_BF8E_7E29L, 0x120A_0D7A_999A_C95DL, + /* -272 */ 0x568E_4755_AF72_1DB3L, 0x368C_90D9_4001_7BB4L, + /* -271 */ 0x6C31_D92B_1B4E_A520L, 0x242F_B50F_9001_DAA1L, + /* -270 */ 0x439F_27BA_F111_2734L, 0x169D_D129_BA01_28A5L, + /* -269 */ 0x5486_F1A9_AD55_7101L, 0x1C45_4574_2881_72CEL, + /* -268 */ 0x69A8_AE14_18AA_CD41L, 0x4356_96D1_32A1_CF81L, + /* -267 */ 0x4209_6CCC_8F6A_C048L, 0x7A16_1E42_BFA5_21B1L, + /* -266 */ 0x528B_C7FF_B345_705BL, 0x189B_A5D3_6F8E_6A1DL, + /* -265 */ 0x672E_B9FF_A016_CC71L, 0x7EC2_8F48_4B72_04A4L, + /* -264 */ 0x407D_343F_C40E_3FC7L, 0x1F39_998D_2F27_42E7L, + /* -263 */ 0x509C_814F_B511_CFB9L, 0x0707_FFF0_7AF1_13A1L, + /* -262 */ 0x64C3_A1A3_A256_43A7L, 0x28C9_FFEC_99AD_5889L, + /* -261 */ 0x7DF4_8A0C_8AEB_D491L, 0x12FC_7FE7_C018_AEABL, + /* -260 */ 0x4EB8_D647_D6D3_64DAL, 0x5BDD_CFF0_D80F_6D2BL, + /* -259 */ 0x6267_0BD9_CC88_3E11L, 0x32D5_43ED_0E13_4875L, + /* -258 */ 0x7B00_CED0_3FAA_4D95L, 0x5F8A_94E8_5198_1A93L, + /* -257 */ 0x4CE0_8142_27CA_707DL, 0x4BB6_9D11_32FF_109CL, + /* -256 */ 0x6018_A192_B1BD_0C9CL, 0x7EA4_4455_7FBE_D4C3L, + /* -255 */ 0x781E_C9F7_5E2C_4FC4L, 0x1E4D_556A_DFAE_89F3L, + /* -254 */ 0x4B13_3E3A_9ADB_B1DAL, 0x52F0_5562_CBCD_1638L, + /* -253 */ 0x5DD8_0DC9_4192_9E51L, 0x27AC_6ABB_7EC0_5BC6L, + /* -252 */ 0x754E_113B_91F7_45E5L, 0x5197_856A_5E70_72B8L, + /* -251 */ 0x4950_CAC5_3B3A_8BAFL, 0x42FE_B362_7B06_47B3L, + /* -250 */ 0x5BA4_FD76_8A09_2E9BL, 0x33BE_603B_19C7_D99FL, + /* -249 */ 0x728E_3CD4_2C8B_7A42L, 0x20AD_F849_E039_D007L, + /* -248 */ 0x4798_E604_9BD7_2C69L, 0x346C_BB2E_2C24_2205L, + /* -247 */ 0x597F_1F85_C2CC_F783L, 0x6187_E9F9_B72D_2A86L, + /* -246 */ 0x6FDE_E767_3380_3564L, 0x59E9_E478_24F8_7527L, + /* -245 */ 0x45EB_50A0_8030_215EL, 0x7832_2ECB_171B_4939L, + /* -244 */ 0x5766_24C8_A03C_29B6L, 0x563E_BA7D_DCE2_1B87L, + /* -243 */ 0x6D3F_ADFA_C84B_3424L, 0x2BCE_691D_541A_A268L, + /* -242 */ 0x4447_CCBC_BD2F_0096L, 0x5B61_01B2_5490_A581L, + /* -241 */ 0x5559_BFEB_EC7A_C0BCL, 0x3239_421E_E9B4_CEE1L, + /* -240 */ 0x6AB0_2FE6_E799_70EBL, 0x3EC7_92A6_A422_029AL, + /* -239 */ 0x42AE_1DF0_50BF_E693L, 0x173C_BBA8_2695_41A0L, + /* -238 */ 0x5359_A56C_64EF_E037L, 0x7D0B_EA92_303A_9208L, + /* -237 */ 0x6830_0EC7_7E2B_D845L, 0x7C4E_E536_BC49_368AL, + /* -236 */ 0x411E_093C_AEDB_672BL, 0x5DB1_4F42_35AD_C217L, + /* -235 */ 0x5165_8B8B_DA92_40F6L, 0x551D_A312_C319_329CL, + /* -234 */ 0x65BE_EE6E_D136_D134L, 0x2A65_0BD7_73DF_7F43L, + /* -233 */ 0x7F2E_AA0A_8584_8581L, 0x34FE_4ECD_50D7_5F14L, + /* -232 */ 0x4F7D_2A46_9372_D370L, 0x711E_F140_5286_9B6CL, + /* -231 */ 0x635C_74D8_384F_884DL, 0x0D66_AD90_6728_4247L, + /* -230 */ 0x7C33_920E_4663_6A60L, 0x30C0_58F4_80F2_52D9L, + /* -229 */ 0x4DA0_3B48_EBFE_227CL, 0x1E78_3798_D097_73C8L, + /* -228 */ 0x6108_4A1B_26FD_AB1BL, 0x2616_457F_04BD_50BAL, + /* -227 */ 0x794A_5CA1_F0BD_15E2L, 0x0F9B_D6DE_C5EC_A4E8L, + /* -226 */ 0x4BCE_79E5_3676_2DADL, 0x29C1_664B_3BB3_E711L, + /* -225 */ 0x5EC2_185E_8413_B918L, 0x5431_BFDE_0AA0_E0D5L, + /* -224 */ 0x7672_9E76_2518_A75EL, 0x693E_2FD5_8D49_190BL, + /* -223 */ 0x4A07_A309_D72F_689BL, 0x21C6_DDE5_784D_AFA7L, + /* -222 */ 0x5C89_8BCC_4CFB_42C2L, 0x0A38_955E_D661_1B90L, + /* -221 */ 0x73AB_EEBF_603A_1372L, 0x4CC6_BAB6_8BF9_6274L, + /* -220 */ 0x484B_7537_9C24_4C27L, 0x4FFC_34B2_177B_DD89L, + /* -219 */ 0x5A5E_5285_832D_5F31L, 0x43FB_41DE_9D5A_D4EBL, + /* -218 */ 0x70F5_E726_E3F8_B6FDL, 0x74FA_1256_44B1_8A26L, + /* -217 */ 0x4699_B078_4E7B_725EL, 0x591C_4B75_EAEE_F658L, + /* -216 */ 0x5840_1C96_621A_4EF6L, 0x2F63_5E53_65AA_B3EDL, + /* -215 */ 0x6E50_23BB_FAA0_E2B3L, 0x7B3C_35E8_3F15_60E9L, + /* -214 */ 0x44F2_1655_7CA4_8DB0L, 0x3D05_A1B1_276D_5C92L, + /* -213 */ 0x562E_9BEA_DBCD_B11CL, 0x4C47_0A1D_7148_B3B6L, + /* -212 */ 0x6BBA_42E5_92C1_1D63L, 0x5F58_CCA4_CD9A_E0A3L, + /* -211 */ 0x4354_69CF_7BB8_B25EL, 0x2B97_7FE7_0080_CC66L, + /* -210 */ 0x5429_8443_5AA6_DEF5L, 0x767D_5FE0_C0A0_FF80L, + /* -209 */ 0x6933_E554_3150_96B3L, 0x341C_B7D8_F0C9_3F5FL, + /* -208 */ 0x41C0_6F54_9ED2_5E30L, 0x1091_F2E7_967D_C79CL, + /* -207 */ 0x5230_8B29_C686_F5BCL, 0x14B6_6FA1_7C1D_3983L, + /* -206 */ 0x66BC_ADF4_3828_B32BL, 0x19E4_0B89_DB24_87E3L, + /* -205 */ 0x4035_ECB8_A319_6FFBL, 0x002E_8736_28F6_D4EEL, + /* -204 */ 0x5043_67E6_CBDF_CBF9L, 0x603A_2903_B334_8A2AL, + /* -203 */ 0x6454_41E0_7ED7_BEF8L, 0x1848_B344_A001_ACB4L, + /* -202 */ 0x7D69_5258_9E8D_AEB6L, 0x1E5A_E015_C802_17E1L, + /* -201 */ 0x4E61_D377_6318_8D31L, 0x72F8_CC0D_9D01_4EEDL, + /* -200 */ 0x61FA_4855_3BDE_B07EL, 0x2FB6_FF11_0441_A2A8L, + /* -199 */ 0x7A78_DA6A_8AD6_5C9DL, 0x7BA4_BED5_4552_0B52L, + /* -198 */ 0x4C8B_8882_96C5_F9E2L, 0x5D46_F745_4B53_4713L, + /* -197 */ 0x5FAE_6AA3_3C77_785BL, 0x3498_B516_9E28_18D8L, + /* -196 */ 0x779A_054C_0B95_5672L, 0x21BE_E25C_45B2_1F0EL, + /* -195 */ 0x4AC0_434F_873D_5607L, 0x3517_4D79_AB8F_5369L, + /* -194 */ 0x5D70_5423_690C_AB89L, 0x225D_20D8_1673_2843L, + /* -193 */ 0x74CC_692C_434F_D66BL, 0x4AF4_690E_1C0F_F253L, + /* -192 */ 0x48FF_C1BB_AA11_E603L, 0x1ED8_C1A8_D189_F774L, + /* -191 */ 0x5B3F_B22A_9496_5F84L, 0x068E_F213_05EC_7551L, + /* -190 */ 0x720F_9EB5_39BB_F765L, 0x0832_AE97_C767_92A5L, + /* -189 */ 0x4749_C331_4415_7A9FL, 0x151F_AD1E_DCA0_BBA8L, + /* -188 */ 0x591C_33FD_951A_D946L, 0x7A67_9866_93C8_EA91L, + /* -187 */ 0x6F63_40FC_FA61_8F98L, 0x5901_7E80_38BB_2536L, + /* -186 */ 0x459E_089E_1C7C_F9BFL, 0x37A0_EF10_2374_F742L, + /* -185 */ 0x5705_8AC5_A39C_382FL, 0x2589_2AD4_2C52_3512L, + /* -184 */ 0x6CC6_ED77_0C83_463BL, 0x0EEB_7589_3766_C256L, + /* -183 */ 0x43FC_546A_67D2_0BE4L, 0x7953_2975_C2A0_3976L, + /* -182 */ 0x54FB_6985_01C6_8EDEL, 0x17A7_F3D3_3348_47D4L, + /* -181 */ 0x6A3A_43E6_4238_3295L, 0x5D91_F0C8_001A_59C8L, + /* -180 */ 0x4264_6A6F_E963_1F9DL, 0x4A7B_367D_0010_781DL, + /* -179 */ 0x52FD_850B_E3BB_E784L, 0x7D1A_041C_4014_9625L, + /* -178 */ 0x67BC_E64E_DCAA_E166L, 0x1C60_8523_5019_BBAEL, + /* -177 */ 0x40D6_0FF1_49EA_CCDFL, 0x71BC_5336_1210_154DL, + /* -176 */ 0x510B_93ED_9C65_8017L, 0x6E2B_6803_9694_1AA0L, + /* -175 */ 0x654E_78E9_037E_E01DL, 0x69B6_4204_7C39_2148L, + /* -174 */ 0x7EA2_1723_445E_9825L, 0x2423_D285_9B47_6999L, + /* -173 */ 0x4F25_4E76_0ABB_1F17L, 0x2696_6393_810C_A200L, + /* -172 */ 0x62EE_A213_8D69_E6DDL, 0x103B_FC78_614F_CA80L, + /* -171 */ 0x7BAA_4A98_70C4_6094L, 0x344A_FB96_79A3_BD20L, + /* -170 */ 0x4D4A_6E9F_467A_BC5CL, 0x60AE_DD3E_0C06_5634L, + /* -169 */ 0x609D_0A47_1819_6B73L, 0x78DA_948D_8F07_EBC1L, + /* -168 */ 0x78C4_4CD8_DE1F_C650L, 0x7711_39B0_F2C9_E6B1L, + /* -167 */ 0x4B7A_B007_8AD3_DBF2L, 0x4A6A_C40E_97BE_302FL, + /* -166 */ 0x5E59_5C09_6D88_D2EFL, 0x1D05_7512_3DAD_BC3AL, + /* -165 */ 0x75EF_B30B_C8EB_07ABL, 0x0446_D256_CD19_2B49L, + /* -164 */ 0x49B5_CFE7_5D92_E4CAL, 0x72AC_4376_402F_BB0EL, + /* -163 */ 0x5C23_43E1_34F7_9DFDL, 0x4F57_5453_D03B_A9D1L, + /* -162 */ 0x732C_14D9_8235_857DL, 0x032D_2968_C44A_9445L, + /* -161 */ 0x47FB_8D07_F161_736EL, 0x11FC_39E1_7AAE_9CABL, + /* -160 */ 0x59FA_7049_EDB9_D049L, 0x567B_4859_D95A_43D6L, + /* -159 */ 0x7079_0C5C_6928_445CL, 0x0C1A_1A70_4FB0_D4CCL, + /* -158 */ 0x464B_A7B9_C1B9_2AB9L, 0x4790_5086_31CE_84FFL, + /* -157 */ 0x57DE_91A8_3227_7567L, 0x7974_64A7_BE42_263FL, + /* -156 */ 0x6DD6_3612_3EB1_52C1L, 0x77D1_7DD1_ADD2_AFCFL, + /* -155 */ 0x44A5_E1CB_672E_D3B9L, 0x1AE2_EEA3_0CA3_ADE1L, + /* -154 */ 0x55CF_5A3E_40FA_88A7L, 0x419B_AA4B_CFCC_995AL, + /* -153 */ 0x6B43_30CD_D139_2AD1L, 0x3202_94DE_C3BF_BFB0L, + /* -152 */ 0x4309_FE80_A2C3_BAC2L, 0x6F41_9D0B_3A57_D7CEL, + /* -151 */ 0x53CC_7E20_CB74_A973L, 0x4B12_044E_08ED_CDC2L, + /* -150 */ 0x68BF_9DA8_FE51_D3D0L, 0x3DD6_8561_8B29_4132L, + /* -149 */ 0x4177_C289_9EF3_2462L, 0x26A6_135C_F6F9_C8BFL, + /* -148 */ 0x51D5_B32C_06AF_ED7AL, 0x704F_9834_34B8_3AEFL, + /* -147 */ 0x664B_1FF7_085B_E8D9L, 0x4C63_7E41_41E6_49ABL, + /* -146 */ 0x7FDD_E7F4_CA72_E30FL, 0x7F7C_5DD1_925F_DC15L, + /* -145 */ 0x4FEA_B0F8_FE87_CDE9L, 0x7FAD_BAA2_FB7B_E98DL, + /* -144 */ 0x63E5_5D37_3E29_C164L, 0x3F99_294B_BA5A_E3F1L, + /* -143 */ 0x7CDE_B485_0DB4_31BDL, 0x4F7F_739E_A8F1_9CEDL, + /* -142 */ 0x4E0B_30D3_2890_9F16L, 0x41AF_A843_2997_0214L, + /* -141 */ 0x618D_FD07_F2B4_C6DCL, 0x121B_9253_F3FC_C299L, + /* -140 */ 0x79F1_7C49_EF61_F893L, 0x16A2_76E8_F0FB_F33FL, + /* -139 */ 0x4C36_EDAE_359D_3B5BL, 0x7E25_8A51_969D_7808L, + /* -138 */ 0x5F44_A919_C304_8A32L, 0x7DAE_ECE5_FC44_D609L, + /* -137 */ 0x7715_D360_33C5_ACBFL, 0x5D1A_A81F_7B56_0B8CL, + /* -136 */ 0x4A6D_A41C_205B_8BF7L, 0x6A30_A913_AD15_C738L, + /* -135 */ 0x5D09_0D23_2872_6EF5L, 0x64BC_D358_985B_3905L, + /* -134 */ 0x744B_506B_F28F_0AB3L, 0x1DEC_082E_BE72_0746L, + /* -133 */ 0x48AF_1243_7799_66B0L, 0x02B3_851D_3707_448CL, + /* -132 */ 0x5ADA_D6D4_557F_C05CL, 0x0360_6664_84C9_15AFL, + /* -131 */ 0x7191_8C89_6ADF_B073L, 0x0438_7FFD_A5FB_5B1BL, + /* -130 */ 0x46FA_F7D5_E2CB_CE47L, 0x72A3_4FFE_87BD_18F1L, + /* -129 */ 0x58B9_B5CB_5B7E_C1D9L, 0x6F4C_23FE_29AC_5F2DL, + /* -128 */ 0x6EE8_233E_325E_7250L, 0x2B1F_2CFD_B417_76F8L, + /* -127 */ 0x4551_1606_DF7B_0772L, 0x1AF3_7C1E_908E_AA5BL, + /* -126 */ 0x56A5_5B88_9759_C94EL, 0x61B0_5B26_34B2_54F2L, + /* -125 */ 0x6C4E_B26A_BD30_3BA2L, 0x3A1C_71EF_C1DE_EA2EL, + /* -124 */ 0x43B1_2F82_B63E_2545L, 0x4451_C735_D92B_525DL, + /* -123 */ 0x549D_7B63_63CD_AE96L, 0x7566_3903_4F76_26F4L, + /* -122 */ 0x69C4_DA3C_3CC1_1A3CL, 0x52BF_C744_2353_B0B1L, + /* -121 */ 0x421B_0865_A5F8_B065L, 0x73B7_DC8A_9614_4E6FL, + /* -120 */ 0x52A1_CA7F_0F76_DC7FL, 0x30A5_D3AD_3B99_620BL, + /* -119 */ 0x674A_3D1E_D354_939FL, 0x1CCF_4898_8A7F_BA8DL, + /* -118 */ 0x408E_6633_4414_DC43L, 0x4201_8D5F_568F_D498L, + /* -117 */ 0x50B1_FFC0_151A_1354L, 0x3281_F0B7_2C33_C9BEL, + /* -116 */ 0x64DE_7FB0_1A60_9829L, 0x3F22_6CE4_F740_BC2EL, + /* -115 */ 0x7E16_1F9C_20F8_BE33L, 0x6EEB_081E_3510_EB39L, + /* -114 */ 0x4ECD_D3C1_949B_76E0L, 0x3552_E512_E12A_9304L, + /* -113 */ 0x6281_48B1_F9C2_5498L, 0x42A7_9E57_9975_37C5L, + /* -112 */ 0x7B21_9ADE_7832_E9BEL, 0x5351_85ED_7FD2_85B6L, + /* -111 */ 0x4CF5_00CB_0B1F_D217L, 0x1412_F3B4_6FE3_9392L, + /* -110 */ 0x6032_40FD_CDE7_C69CL, 0x7917_B0A1_8BDC_7876L, + /* -109 */ 0x783E_D13D_4161_B844L, 0x175D_9CC9_EED3_9694L, + /* -108 */ 0x4B27_42C6_48DD_132AL, 0x4E9A_81FE_3544_3E1CL, + /* -107 */ 0x5DF1_1377_DB14_57F5L, 0x2241_227D_C295_4DA3L, + /* -106 */ 0x756D_5855_D1D9_6DF2L, 0x4AD1_6B1D_333A_A10CL, + /* -105 */ 0x4964_5735_A327_E4B7L, 0x4EC2_E2F2_4004_A4A8L, + /* -104 */ 0x5BBD_6D03_0BF1_DDE5L, 0x4273_9BAE_D005_CDD2L, + /* -103 */ 0x72AC_C843_CEEE_555EL, 0x7310_829A_8407_4146L, + /* -102 */ 0x47AB_FD2A_6154_F55BL, 0x27EA_51A0_9284_88CCL, + /* -101 */ 0x5996_FC74_F9AA_32B2L, 0x11E4_E608_B725_AAFFL, + /* -100 */ 0x6FFC_BB92_3814_BF5EL, 0x565E_1F8A_E4EF_15BEL, + /* -99 */ 0x45FD_F53B_630C_F79BL, 0x15FA_D3B6_CF15_6D97L, + /* -98 */ 0x577D_728A_3BD0_3581L, 0x7B79_88A4_82DA_C8FDL, + /* -97 */ 0x6D5C_CF2C_CAC4_42E2L, 0x3A57_EACD_A391_7B3CL, + /* -96 */ 0x445A_017B_FEBA_A9CDL, 0x4476_F2C0_863A_ED06L, + /* -95 */ 0x5570_81DA_FE69_5440L, 0x7594_AF70_A7C9_A847L, + /* -94 */ 0x6ACC_A251_BE03_A951L, 0x12F9_DB4C_D1BC_1258L, + /* -93 */ 0x42BF_E573_16C2_49D2L, 0x5BDC_2910_0315_8B77L, + /* -92 */ 0x536F_DECF_DC72_DC47L, 0x32D3_3354_03DA_EE55L, + /* -91 */ 0x684B_D683_D38F_9359L, 0x1F88_0029_04D1_A9EAL, + /* -90 */ 0x412F_6612_6439_BC17L, 0x63B5_0019_A303_0A33L, + /* -89 */ 0x517B_3F96_FD48_2B1DL, 0x5CA2_4020_0BC3_CCBFL, + /* -88 */ 0x65DA_0F7C_BC9A_35E5L, 0x13CA_D028_0EB4_BFEFL, + /* -87 */ 0x7F50_935B_EBC0_C35EL, 0x38BD_8432_1261_EFEBL, + /* -86 */ 0x4F92_5C19_7358_7A1BL, 0x0376_729F_4B7D_35F3L, + /* -85 */ 0x6376_F31F_D02E_98A1L, 0x6454_0F47_1E5C_836FL, + /* -84 */ 0x7C54_AFE7_C43A_3ECAL, 0x1D69_1318_E5F3_A44BL, + /* -83 */ 0x4DB4_EDF0_DAA4_673EL, 0x3261_ABEF_8FB8_46AFL, + /* -82 */ 0x6122_296D_114D_810DL, 0x7EFA_16EB_73A6_585BL, + /* -81 */ 0x796A_B3C8_55A0_E151L, 0x3EB8_9CA6_508F_EE71L, + /* -80 */ 0x4BE2_B05D_3584_8CD2L, 0x7733_61E7_F259_F507L, + /* -79 */ 0x5EDB_5C74_82E5_B007L, 0x5500_3A61_EEF0_7249L, + /* -78 */ 0x7692_3391_A39F_1C09L, 0x4A40_48FA_6AAC_8EDBL, + /* -77 */ 0x4A1B_603B_0643_7185L, 0x7E68_2D9C_82AB_D949L, + /* -76 */ 0x5CA2_3849_C7D4_4DE7L, 0x3E02_3903_A356_CF9BL, + /* -75 */ 0x73CA_C65C_39C9_6161L, 0x2D82_C744_8C2C_8382L, + /* -74 */ 0x485E_BBF9_A41D_DCDCL, 0x6C71_BC8A_D79B_D231L, + /* -73 */ 0x5A76_6AF8_0D25_5414L, 0x078E_2BAD_8D82_C6BDL, + /* -72 */ 0x7114_05B6_106E_A919L, 0x0971_B698_F0E3_786DL, + /* -71 */ 0x46AC_8391_CA45_29AFL, 0x55E7_121F_968E_2B44L, + /* -70 */ 0x5857_A476_3CD6_741BL, 0x4B60_D6A7_7C31_B615L, + /* -69 */ 0x6E6D_8D93_CC0C_1122L, 0x3E39_0C51_5B3E_239AL, + /* -68 */ 0x4504_787C_5F87_8AB5L, 0x46E3_A7B2_D906_D640L, + /* -67 */ 0x5645_969B_7769_6D62L, 0x789C_919F_8F48_8BD0L, + /* -66 */ 0x6BD6_FC42_5543_C8BBL, 0x56C3_B607_731A_AEC4L, + /* -65 */ 0x4366_5DA9_754A_5D75L, 0x263A_51C4_A7F0_AD3BL, + /* -64 */ 0x543F_F513_D29C_F4D2L, 0x4FC8_E635_D1EC_D88AL, + /* -63 */ 0x694F_F258_C744_3207L, 0x23BB_1FC3_4668_0EACL, + /* -62 */ 0x41D1_F777_7C8A_9F44L, 0x4654_F3DA_0C01_092CL, + /* -61 */ 0x5246_7555_5BAD_4715L, 0x57EA_30D0_8F01_4B76L, + /* -60 */ 0x66D8_12AA_B298_98DBL, 0x0DE4_BD04_B2C1_9E54L, + /* -59 */ 0x4047_0BAA_AF9F_5F88L, 0x78AE_F622_EFB9_02F5L, + /* -58 */ 0x5058_CE95_5B87_376BL, 0x16DA_B3AB_ABA7_43B2L, + /* -57 */ 0x646F_023A_B269_0545L, 0x7C91_6096_9691_149EL, + /* -56 */ 0x7D8A_C2C9_5F03_4697L, 0x3BB5_B8BC_3C35_59C5L, + /* -55 */ 0x4E76_B9BD_DB62_0C1EL, 0x5551_9375_A5A1_581BL, + /* -54 */ 0x6214_682D_523A_8F26L, 0x2AA5_F853_0F09_AE22L, + /* -53 */ 0x7A99_8238_A6C9_32EFL, 0x754F_7667_D2CC_19ABL, + /* -52 */ 0x4C9F_F163_683D_BFD5L, 0x7951_AA00_E3BF_900BL, + /* -51 */ 0x5FC7_EDBC_424D_2FCBL, 0x37A6_1481_1CAF_740DL, + /* -50 */ 0x77B9_E92B_52E0_7BBEL, 0x258F_99A1_63DB_5111L, + /* -49 */ 0x4AD4_31BB_13CC_4D56L, 0x7779_C004_DE69_12ABL, + /* -48 */ 0x5D89_3E29_D8BF_60ACL, 0x5558_3006_1603_5755L, + /* -47 */ 0x74EB_8DB4_4EEF_38D7L, 0x6AAE_3C07_9B84_2D2AL, + /* -46 */ 0x4913_3890_B155_8386L, 0x72AC_E584_C132_9C3BL, + /* -45 */ 0x5B58_06B4_DDAA_E468L, 0x4F58_1EE5_F17F_4349L, + /* -44 */ 0x722E_0862_1515_9D82L, 0x632E_269F_6DDF_141BL, + /* -43 */ 0x475C_C53D_4D2D_8271L, 0x5DFC_D823_A4AB_6C91L, + /* -42 */ 0x5933_F68C_A078_E30EL, 0x157C_0E2C_8DD6_47B5L, + /* -41 */ 0x6F80_F42F_C897_1BD1L, 0x5ADB_11B7_B14B_D9A3L, + /* -40 */ 0x45B0_989D_DD5E_7163L, 0x08C8_EB12_CECF_6806L, + /* -39 */ 0x571C_BEC5_54B6_0DBBL, 0x6AFB_25D7_8283_4207L, + /* -38 */ 0x6CE3_EE76_A9E3_912AL, 0x65B9_EF4D_6324_1289L, + /* -37 */ 0x440E_750A_2A2E_3ABAL, 0x5F94_3590_5DF6_8B96L, + /* -36 */ 0x5512_124C_B4B9_C969L, 0x3779_42F4_7574_2E7BL, + /* -35 */ 0x6A56_96DF_E1E8_3BC3L, 0x6557_93B1_92D1_3A1AL, + /* -34 */ 0x4276_1E4B_ED31_255AL, 0x2F56_BC4E_FBC2_C450L, + /* -33 */ 0x5313_A5DE_E87D_6EB0L, 0x7B2C_6B62_BAB3_7564L, + /* -32 */ 0x67D8_8F56_A29C_CA5DL, 0x19F7_863B_6960_52BDL, + /* -31 */ 0x40E7_5996_25A1_FE7AL, 0x203A_B3E5_21DC_33B6L, + /* -30 */ 0x5121_2FFB_AF0A_7E18L, 0x6849_60DE_6A53_40A4L, + /* -29 */ 0x6569_7BFA_9ACD_1D9FL, 0x025B_B916_04E8_10CDL, + /* -28 */ 0x7EC3_DAF9_4180_6506L, 0x62F2_A75B_8622_1500L, + /* -27 */ 0x4F3A_68DB_C8F0_3F24L, 0x1DD7_A899_33D5_4D20L, + /* -26 */ 0x6309_0312_BB2C_4EEDL, 0x254D_92BF_80CA_A068L, + /* -25 */ 0x7BCB_43D7_69F7_62A8L, 0x4EA0_F76F_60FD_4882L, + /* -24 */ 0x4D5F_0A66_A23A_9DA9L, 0x3124_9AA5_9C9E_4D51L, + /* -23 */ 0x60B6_CD00_4AC9_4513L, 0x5D6D_C14F_03C5_E0A5L, + /* -22 */ 0x78E4_8040_5D7B_9658L, 0x54C9_31A2_C4B7_58CFL, + /* -21 */ 0x4B8E_D028_3A6D_3DF7L, 0x34FD_BF05_BAF2_9781L, + /* -20 */ 0x5E72_8432_4908_8D75L, 0x223D_2EC7_29AF_3D62L, + /* -19 */ 0x760F_253E_DB4A_B0D2L, 0x4ACC_7A78_F41B_0CBAL, + /* -18 */ 0x49C9_7747_490E_AE83L, 0x4EBF_CC8B_9890_E7F4L, + /* -17 */ 0x5C3B_D519_1B52_5A24L, 0x426F_BFAE_7EB5_21F1L, + /* -16 */ 0x734A_CA5F_6226_F0ADL, 0x530B_AF9A_1E62_6A6DL, + /* -15 */ 0x480E_BE7B_9D58_566CL, 0x43E7_4DC0_52FD_8285L, + /* -14 */ 0x5A12_6E1A_84AE_6C07L, 0x54E1_2130_67BC_E326L, + /* -13 */ 0x7097_09A1_25DA_0709L, 0x4A19_697C_81AC_1BEFL, + /* -12 */ 0x465E_6604_B7A8_4465L, 0x7E4F_E1ED_D10B_9175L, + /* -11 */ 0x57F5_FF85_E592_557FL, 0x3DE3_DA69_454E_75D3L, + /* -10 */ 0x6DF3_7F67_5EF6_EADFL, 0x2D5C_D103_96A2_1347L, + /* -9 */ 0x44B8_2FA0_9B5A_52CBL, 0x4C5A_02A2_3E25_4C0DL, + /* -8 */ 0x55E6_3B88_C230_E77EL, 0x3F70_834A_CDAE_9F10L, + /* -7 */ 0x6B5F_CA6A_F2BD_215EL, 0x0F4C_A41D_811A_46D4L, + /* -6 */ 0x431B_DE82_D7B6_34DAL, 0x698F_E692_70B0_6C44L, + /* -5 */ 0x53E2_D623_8DA3_C211L, 0x43F3_E037_0CDC_8755L, + /* -4 */ 0x68DB_8BAC_710C_B295L, 0x74F0_D844_D013_A92BL, + /* -3 */ 0x4189_374B_C6A7_EF9DL, 0x5916_872B_020C_49BBL, + /* -2 */ 0x51EB_851E_B851_EB85L, 0x0F5C_28F5_C28F_5C29L, + /* -1 */ 0x6666_6666_6666_6666L, 0x3333_3333_3333_3334L, + /* 0 */ 0x4000_0000_0000_0000L, 0x0000_0000_0000_0001L, + /* 1 */ 0x5000_0000_0000_0000L, 0x0000_0000_0000_0001L, + /* 2 */ 0x6400_0000_0000_0000L, 0x0000_0000_0000_0001L, + /* 3 */ 0x7D00_0000_0000_0000L, 0x0000_0000_0000_0001L, + /* 4 */ 0x4E20_0000_0000_0000L, 0x0000_0000_0000_0001L, + /* 5 */ 0x61A8_0000_0000_0000L, 0x0000_0000_0000_0001L, + /* 6 */ 0x7A12_0000_0000_0000L, 0x0000_0000_0000_0001L, + /* 7 */ 0x4C4B_4000_0000_0000L, 0x0000_0000_0000_0001L, + /* 8 */ 0x5F5E_1000_0000_0000L, 0x0000_0000_0000_0001L, + /* 9 */ 0x7735_9400_0000_0000L, 0x0000_0000_0000_0001L, + /* 10 */ 0x4A81_7C80_0000_0000L, 0x0000_0000_0000_0001L, + /* 11 */ 0x5D21_DBA0_0000_0000L, 0x0000_0000_0000_0001L, + /* 12 */ 0x746A_5288_0000_0000L, 0x0000_0000_0000_0001L, + /* 13 */ 0x48C2_7395_0000_0000L, 0x0000_0000_0000_0001L, + /* 14 */ 0x5AF3_107A_4000_0000L, 0x0000_0000_0000_0001L, + /* 15 */ 0x71AF_D498_D000_0000L, 0x0000_0000_0000_0001L, + /* 16 */ 0x470D_E4DF_8200_0000L, 0x0000_0000_0000_0001L, + /* 17 */ 0x58D1_5E17_6280_0000L, 0x0000_0000_0000_0001L, + /* 18 */ 0x6F05_B59D_3B20_0000L, 0x0000_0000_0000_0001L, + /* 19 */ 0x4563_9182_44F4_0000L, 0x0000_0000_0000_0001L, + /* 20 */ 0x56BC_75E2_D631_0000L, 0x0000_0000_0000_0001L, + /* 21 */ 0x6C6B_935B_8BBD_4000L, 0x0000_0000_0000_0001L, + /* 22 */ 0x43C3_3C19_3756_4800L, 0x0000_0000_0000_0001L, + /* 23 */ 0x54B4_0B1F_852B_DA00L, 0x0000_0000_0000_0001L, + /* 24 */ 0x69E1_0DE7_6676_D080L, 0x0000_0000_0000_0001L, + /* 25 */ 0x422C_A8B0_A00A_4250L, 0x0000_0000_0000_0001L, + /* 26 */ 0x52B7_D2DC_C80C_D2E4L, 0x0000_0000_0000_0001L, + /* 27 */ 0x6765_C793_FA10_079DL, 0x0000_0000_0000_0001L, + /* 28 */ 0x409F_9CBC_7C4A_04C2L, 0x1000_0000_0000_0001L, + /* 29 */ 0x50C7_83EB_9B5C_85F2L, 0x5400_0000_0000_0001L, + /* 30 */ 0x64F9_64E6_8233_A76FL, 0x2900_0000_0000_0001L, + /* 31 */ 0x7E37_BE20_22C0_914BL, 0x1340_0000_0000_0001L, + /* 32 */ 0x4EE2_D6D4_15B8_5ACEL, 0x7C08_0000_0000_0001L, + /* 33 */ 0x629B_8C89_1B26_7182L, 0x5B0A_0000_0000_0001L, + /* 34 */ 0x7B42_6FAB_61F0_0DE3L, 0x31CC_8000_0000_0001L, + /* 35 */ 0x4D09_85CB_1D36_08AEL, 0x0F1F_D000_0000_0001L, + /* 36 */ 0x604B_E73D_E483_8AD9L, 0x52E7_C400_0000_0001L, + /* 37 */ 0x785E_E10D_5DA4_6D90L, 0x07A1_B500_0000_0001L, + /* 38 */ 0x4B3B_4CA8_5A86_C47AL, 0x04C5_1120_0000_0001L, + /* 39 */ 0x5E0A_1FD2_7128_7598L, 0x45F6_5568_0000_0001L, + /* 40 */ 0x758C_A7C7_0D72_92FEL, 0x5773_EAC2_0000_0001L, + /* 41 */ 0x4977_E8DC_6867_9BDFL, 0x16A8_72B9_4000_0001L, + /* 42 */ 0x5BD5_E313_8281_82D6L, 0x7C52_8F67_9000_0001L, + /* 43 */ 0x72CB_5BD8_6321_E38CL, 0x5B67_3341_7400_0001L, + /* 44 */ 0x47BF_1967_3DF5_2E37L, 0x7920_8008_E880_0001L, + /* 45 */ 0x59AE_DFC1_0D72_79C5L, 0x7768_A00B_22A0_0001L, + /* 46 */ 0x701A_97B1_50CF_1837L, 0x3542_C80D_EB48_0001L, + /* 47 */ 0x4610_9ECE_D281_6F22L, 0x5149_BD08_B30D_0001L, + /* 48 */ 0x5794_C682_8721_CAEBL, 0x259C_2C4A_DFD0_4001L, + /* 49 */ 0x6D79_F823_28EA_3DA6L, 0x0F03_375D_97C4_5001L, + /* 50 */ 0x446C_3B15_F992_6687L, 0x6962_029A_7EDA_B201L, + /* 51 */ 0x5587_49DB_77F7_0029L, 0x63BA_8341_1E91_5E81L, + /* 52 */ 0x6AE9_1C52_55F4_C034L, 0x1CA9_2411_6635_B621L, + /* 53 */ 0x42D1_B1B3_75B8_F820L, 0x51E9_B68A_DFE1_91D5L, + /* 54 */ 0x5386_1E20_5327_3628L, 0x6664_242D_97D9_F64AL, + /* 55 */ 0x6867_A5A8_67F1_03B2L, 0x7FFD_2D38_FDD0_73DCL, + /* 56 */ 0x4140_C789_40F6_A24FL, 0x6FFE_3C43_9EA2_486AL, + /* 57 */ 0x5190_F96B_9134_4AE3L, 0x6BFD_CB54_864A_DA84L, + /* 58 */ 0x65F5_37C6_7581_5D9CL, 0x66FD_3E29_A7DD_9125L, + /* 59 */ 0x7F72_85B8_12E1_B504L, 0x00BC_8DB4_11D4_F56EL, + /* 60 */ 0x4FA7_9393_0BCD_1122L, 0x4075_D890_8B25_1965L, + /* 61 */ 0x6391_7877_CEC0_556BL, 0x1093_4EB4_ADEE_5FBEL, + /* 62 */ 0x7C75_D695_C270_6AC5L, 0x74B8_2261_D969_F7ADL, + /* 63 */ 0x4DC9_A61D_9986_42BBL, 0x58F3_157D_27E2_3ACCL, + /* 64 */ 0x613C_0FA4_FFE7_D36AL, 0x4F2F_DADC_71DA_C97FL, + /* 65 */ 0x798B_138E_3FE1_C845L, 0x22FB_D193_8E51_7BDFL, + /* 66 */ 0x4BF6_EC38_E7ED_1D2BL, 0x25DD_62FC_38F2_ED6CL, + /* 67 */ 0x5EF4_A747_21E8_6476L, 0x0F54_BBBB_472F_A8C6L, + /* 68 */ 0x76B1_D118_EA62_7D93L, 0x5329_EAAA_18FB_92F8L, + /* 69 */ 0x4A2F_22AF_927D_8E7CL, 0x23FA_32AA_4F9D_3BDBL, + /* 70 */ 0x5CBA_EB5B_771C_F21BL, 0x2CF8_BF54_E384_8AD2L, + /* 71 */ 0x73E9_A632_54E4_2EA2L, 0x1836_EF2A_1C65_AD86L, + /* 72 */ 0x4872_07DF_750E_9D25L, 0x2F22_557A_51BF_8C74L, + /* 73 */ 0x5A8E_89D7_5252_446EL, 0x5AEA_EAD8_E62F_6F91L, + /* 74 */ 0x7132_2C4D_26E6_D58AL, 0x31A5_A58F_1FBB_4B75L, + /* 75 */ 0x46BF_5BB0_3850_4576L, 0x3F07_8779_73D5_0F29L, + /* 76 */ 0x586F_329C_4664_56D4L, 0x0EC9_6957_D0CA_52F3L, + /* 77 */ 0x6E8A_FF43_57FD_6C89L, 0x127B_C3AD_C4FC_E7B0L, + /* 78 */ 0x4516_DF8A_16FE_63D5L, 0x5B8D_5A4C_9B1E_10CEL, + /* 79 */ 0x565C_976C_9CBD_FCCBL, 0x1270_B0DF_C1E5_9502L, + /* 80 */ 0x6BF3_BD47_C3ED_7BFDL, 0x770C_DD17_B25E_FA42L, + /* 81 */ 0x4378_564C_DA74_6D7EL, 0x5A68_0A2E_CF7B_5C69L, + /* 82 */ 0x5456_6BE0_1111_88DEL, 0x3102_0CBA_835A_3384L, + /* 83 */ 0x696C_06D8_1555_EB15L, 0x7D42_8FE9_2430_C065L, + /* 84 */ 0x41E3_8447_0D55_B2EDL, 0x5E49_99F1_B69E_783FL, + /* 85 */ 0x525C_6558_D0AB_1FA9L, 0x15DC_006E_2446_164FL, + /* 86 */ 0x66F3_7EAF_04D5_E793L, 0x3B53_0089_AD57_9BE2L, + /* 87 */ 0x4058_2F2D_6305_B0BCL, 0x1513_E056_0C56_C16EL, + /* 88 */ 0x506E_3AF8_BBC7_1CEBL, 0x1A58_D86B_8F6C_71C9L, + /* 89 */ 0x6489_C9B6_EAB8_E426L, 0x00EF_0E86_7347_8E3BL, + /* 90 */ 0x7DAC_3C24_A567_1D2FL, 0x412A_D228_1019_71C9L, + /* 91 */ 0x4E8B_A596_E760_723DL, 0x58BA_C359_0A0F_E71EL, + /* 92 */ 0x622E_8EFC_A138_8ECDL, 0x0EE9_742F_4C93_E0E6L, + /* 93 */ 0x7ABA_32BB_C986_B280L, 0x32A3_D13B_1FB8_D91FL, + /* 94 */ 0x4CB4_5FB5_5DF4_2F90L, 0x1FA6_62C4_F3D3_87B3L, + /* 95 */ 0x5FE1_77A2_B571_3B74L, 0x278F_FB76_30C8_69A0L, + /* 96 */ 0x77D9_D58B_62CD_8A51L, 0x3173_FA53_BCFA_8408L, + /* 97 */ 0x4AE8_2577_1DC0_7672L, 0x6EE8_7C74_561C_9285L, + /* 98 */ 0x5DA2_2ED4_E530_940FL, 0x4AA2_9B91_6BA3_B726L, + /* 99 */ 0x750A_BA8A_1E7C_B913L, 0x3D4B_4275_C68C_A4F0L, + /* 100 */ 0x4926_B496_530D_F3ACL, 0x164F_0989_9C17_E716L, + /* 101 */ 0x5B70_61BB_E7D1_7097L, 0x1BE2_CBEC_031D_E0DCL, + /* 102 */ 0x724C_7A2A_E1C5_CCBDL, 0x02DB_7EE7_03E5_5912L, + /* 103 */ 0x476F_CC5A_CD1B_9FF6L, 0x11C9_2F50_626F_57ACL, + /* 104 */ 0x594B_BF71_8062_87F3L, 0x563B_7B24_7B0B_2D96L, + /* 105 */ 0x6F9E_AF4D_E07B_29F0L, 0x4BCA_59ED_99CD_F8FCL, + /* 106 */ 0x45C3_2D90_AC4C_FA36L, 0x2F5E_7834_8020_BB9EL, + /* 107 */ 0x5733_F8F4_D760_38C3L, 0x7B36_1641_A028_EA85L, + /* 108 */ 0x6D00_F732_0D38_46F4L, 0x7A03_9BD2_0833_2526L, + /* 109 */ 0x4420_9A7F_4843_2C59L, 0x0C42_4163_451F_F738L, + /* 110 */ 0x5528_C11F_1A53_F76FL, 0x2F52_D1BC_1667_F506L, + /* 111 */ 0x6A72_F166_E0E8_F54BL, 0x1B27_862B_1C01_F247L, + /* 112 */ 0x4287_D6E0_4C91_994FL, 0x00F8_B3DA_F181_376DL, + /* 113 */ 0x5329_CC98_5FB5_FFA2L, 0x6136_E0D1_ADE1_8548L, + /* 114 */ 0x67F4_3FBE_77A3_7F8BL, 0x3984_9906_1959_E699L, + /* 115 */ 0x40F8_A7D7_0AC6_2FB7L, 0x13F2_DFA3_CFD8_3020L, + /* 116 */ 0x5136_D1CC_CD77_BBA4L, 0x78EF_978C_C3CE_3C28L, + /* 117 */ 0x6584_8640_00D5_AA8EL, 0x172B_7D6F_F4C1_CB32L, + /* 118 */ 0x7EE5_A7D0_010B_1531L, 0x5CF6_5CCB_F1F2_3DFEL, + /* 119 */ 0x4F4F_88E2_00A6_ED3FL, 0x0A19_F9FF_7737_66BFL, + /* 120 */ 0x6323_6B1A_80D0_A88EL, 0x6CA0_787F_5505_406FL, + /* 121 */ 0x7BEC_45E1_2104_D2B2L, 0x47C8_969F_2A46_908AL, + /* 122 */ 0x4D73_ABAC_B4A3_03AFL, 0x4CDD_5E23_7A6C_1A57L, + /* 123 */ 0x60D0_9697_E1CB_C49BL, 0x4014_B5AC_5907_20ECL, + /* 124 */ 0x7904_BC3D_DA3E_B5C2L, 0x3019_E317_6F48_E927L, + /* 125 */ 0x4BA2_F5A6_A867_3199L, 0x3E10_2DEE_A58D_91B9L, + /* 126 */ 0x5E8B_B310_5280_FDFFL, 0x6D94_396A_4EF0_F627L, + /* 127 */ 0x762E_9FD4_6721_3D7FL, 0x68F9_47C4_E2AD_33B0L, + /* 128 */ 0x49DD_23E4_C074_C66FL, 0x719B_CCDB_0DAC_404EL, + /* 129 */ 0x5C54_6CDD_F091_F80BL, 0x6E02_C011_D117_5062L, + /* 130 */ 0x7369_8815_6CB6_760EL, 0x6983_7016_455D_247AL, + /* 131 */ 0x4821_F50D_63F2_09C9L, 0x21F2_260D_EB5A_36CCL, + /* 132 */ 0x5A2A_7250_BCEE_8C3BL, 0x4A6E_AF91_6630_C47FL, + /* 133 */ 0x70B5_0EE4_EC2A_2F4AL, 0x3D0A_5B75_BFBC_F59FL, + /* 134 */ 0x4671_294F_139A_5D8EL, 0x4626_7929_97D6_1984L, + /* 135 */ 0x580D_73A2_D880_F4F2L, 0x17B0_1773_FDCB_9FE4L, + /* 136 */ 0x6E10_D08B_8EA1_322EL, 0x5D9C_1D50_FD3E_87DDL, + /* 137 */ 0x44CA_8257_3924_BF5DL, 0x1A81_9252_9E47_14EBL, + /* 138 */ 0x55FD_22ED_076D_EF34L, 0x4121_F6E7_45D8_DA25L, + /* 139 */ 0x6B7C_6BA8_4949_6B01L, 0x516A_74A1_174F_10AEL, + /* 140 */ 0x432D_C349_2DCD_E2E1L, 0x02E2_88E4_AE91_6A6DL, + /* 141 */ 0x53F9_341B_7941_5B99L, 0x239B_2B1D_DA35_C508L, + /* 142 */ 0x68F7_8122_5791_B27FL, 0x4C81_F5E5_50C3_364AL, + /* 143 */ 0x419A_B0B5_76BB_0F8FL, 0x5FD1_39AF_527A_01EFL, + /* 144 */ 0x5201_5CE2_D469_D373L, 0x57C5_881B_2718_826AL, + /* 145 */ 0x6681_B41B_8984_4850L, 0x4DB6_EA21_F0DE_A304L, + /* 146 */ 0x4011_1091_35F2_AD32L, 0x3092_5255_368B_25E3L, + /* 147 */ 0x5015_54B5_836F_587EL, 0x7CB6_E6EA_842D_EF5CL, + /* 148 */ 0x641A_A9E2_E44B_2E9EL, 0x5BE4_A0A5_2539_6B32L, + /* 149 */ 0x7D21_545B_9D5D_FA46L, 0x32DD_C8CE_6E87_C5FFL, + /* 150 */ 0x4E34_D4B9_425A_BC6BL, 0x7FCA_9D81_0514_DBBFL, + /* 151 */ 0x61C2_09E7_92F1_6B86L, 0x7FBD_44E1_465A_12AFL, + /* 152 */ 0x7A32_8C61_77AD_C668L, 0x5FAC_9619_97F0_975BL, + /* 153 */ 0x4C5F_97BC_EACC_9C01L, 0x3BCB_DDCF_FEF6_5E99L, + /* 154 */ 0x5F77_7DAC_257F_C301L, 0x6ABE_D543_FEB3_F63FL, + /* 155 */ 0x7755_5D17_2EDF_B3C2L, 0x256E_8A94_FE60_F3CFL, + /* 156 */ 0x4A95_5A2E_7D4B_D059L, 0x3765_169D_1EFC_9861L, + /* 157 */ 0x5D3A_B0BA_1C9E_C46FL, 0x653E_5C44_66BB_BE7AL, + /* 158 */ 0x7489_5CE8_A3C6_758BL, 0x5E8D_F355_806A_AE18L, + /* 159 */ 0x48D5_DA11_665C_0977L, 0x2B18_B815_7042_ACCFL, + /* 160 */ 0x5B0B_5095_BFF3_0BD5L, 0x15DE_E61A_CC53_5803L, + /* 161 */ 0x71CE_24BB_2FEF_CECAL, 0x3B56_9FA1_7F68_2E03L, + /* 162 */ 0x4720_D6F4_FDF5_E13EL, 0x4516_23C4_EFA1_1CC2L, + /* 163 */ 0x58E9_0CB2_3D73_598EL, 0x165B_ACB6_2B89_63F3L, + /* 164 */ 0x6F23_4FDE_CCD0_2FF1L, 0x5BF2_97E3_B66B_BCEFL, + /* 165 */ 0x4576_11EB_4002_1DF7L, 0x0977_9EEE_5203_5616L, + /* 166 */ 0x56D3_9666_1002_A574L, 0x6BD5_86A9_E684_2B9BL, + /* 167 */ 0x6C88_7BFF_9403_4ED2L, 0x06CA_E854_6025_3682L, + /* 168 */ 0x43D5_4D7F_BC82_1143L, 0x243E_D134_BC17_4211L, + /* 169 */ 0x54CA_A0DF_ABA2_9594L, 0x0D4E_8581_EB1D_1295L, + /* 170 */ 0x69FD_4917_968B_3AF9L, 0x10A2_26E2_65E4_573BL, + /* 171 */ 0x423E_4DAE_BE17_04DBL, 0x5A65_584D_7FAE_B685L, + /* 172 */ 0x52CD_E11A_6D9C_C612L, 0x50FE_AE60_DF9A_6426L, + /* 173 */ 0x6781_5961_0903_F797L, 0x253E_59F9_1780_FD2FL, + /* 174 */ 0x40B0_D7DC_A5A2_7ABEL, 0x4746_F83B_AEB0_9E3EL, + /* 175 */ 0x50DD_0DD3_CF0B_196EL, 0x1918_B64A_9A5C_C5CDL, + /* 176 */ 0x6514_5148_C2CD_DFC9L, 0x5F5E_E3DD_40F3_F740L, + /* 177 */ 0x7E59_659A_F381_57BCL, 0x1736_9CD4_9130_F510L, + /* 178 */ 0x4EF7_DF80_D830_D6D5L, 0x4E82_2204_DABE_992AL, + /* 179 */ 0x62B5_D761_0E3D_0C8BL, 0x0222_AA86_116E_3F75L, + /* 180 */ 0x7B63_4D39_51CC_4FADL, 0x62AB_5527_95C9_CF52L, + /* 181 */ 0x4D1E_1043_D31F_B1CCL, 0x4DAB_1538_BD9E_2193L, + /* 182 */ 0x6065_9454_C7E7_9E3FL, 0x6115_DA86_ED05_A9F8L, + /* 183 */ 0x787E_F969_F9E1_85CFL, 0x595B_5128_A847_1476L, + /* 184 */ 0x4B4F_5BE2_3C2C_F3A1L, 0x67D9_12B9_692C_6CCAL, + /* 185 */ 0x5E23_32DA_CB38_308AL, 0x21CF_5767_C377_87FCL, + /* 186 */ 0x75AB_FF91_7E06_3CACL, 0x6A43_2D41_B455_69FBL, + /* 187 */ 0x498B_7FBA_EEC3_E5ECL, 0x0269_FC49_10B5_623DL, + /* 188 */ 0x5BEE_5FA9_AA74_DF67L, 0x0304_7B5B_54E2_BACCL, + /* 189 */ 0x72E9_F794_1512_1740L, 0x63C5_9A32_2A1B_697FL, + /* 190 */ 0x47D2_3ABC_8D2B_4E88L, 0x3E5B_805F_5A51_21F0L, + /* 191 */ 0x59C6_C96B_B076_222AL, 0x4DF2_6077_30E5_6A6CL, + /* 192 */ 0x7038_7BC6_9C93_AAB5L, 0x216E_F894_FD1E_C506L, + /* 193 */ 0x4623_4D5C_21DC_4AB1L, 0x24E5_5B5D_1E33_3B24L, + /* 194 */ 0x57AC_20B3_2A53_5D5DL, 0x4E1E_B234_65C0_09EDL, + /* 195 */ 0x6D97_28DF_F4E8_34B5L, 0x01A6_5EC1_7F30_0C68L, + /* 196 */ 0x447E_798B_F911_20F1L, 0x1107_FB38_EF7E_07C1L, + /* 197 */ 0x559E_17EE_F755_692DL, 0x3549_FA07_2B5D_89B1L, + /* 198 */ 0x6B05_9DEA_B52A_C378L, 0x629C_7888_F634_EC1EL, + /* 199 */ 0x42E3_82B2_B13A_BA2BL, 0x3DA1_CB55_99E1_1393L, + /* 200 */ 0x539C_635F_5D89_68B6L, 0x2D0A_3E2B_0059_5877L, + /* 201 */ 0x6883_7C37_34EB_C2E3L, 0x784C_CDB5_C06F_AE95L, + /* 202 */ 0x4152_2DA2_8113_59CEL, 0x3B30_0091_9845_CD1DL, + /* 203 */ 0x51A6_B90B_2158_3042L, 0x09FC_00B5_FE57_4065L, + /* 204 */ 0x6610_674D_E9AE_3C52L, 0x4C7B_00E3_7DED_107EL, + /* 205 */ 0x7F94_8121_6419_CB67L, 0x1F99_C11C_5D68_549DL, + /* 206 */ 0x4FBC_D0B4_DE90_1F20L, 0x43C0_18B1_BA61_34E2L, + /* 207 */ 0x63AC_04E2_1634_26E8L, 0x54B0_1EDE_28F9_821BL, + /* 208 */ 0x7C97_061A_9BC1_30A2L, 0x69DC_2695_B337_E2A1L, + /* 209 */ 0x4DDE_63D0_A158_BE65L, 0x6229_981D_9002_EDA5L, + /* 210 */ 0x6155_FCC4_C9AE_EDFFL, 0x1AB3_FE24_F403_A90EL, + /* 211 */ 0x79AB_7BF5_FC1A_A97FL, 0x0160_FDAE_3104_9351L, + /* 212 */ 0x4C0B_2D79_BD90_A9EFL, 0x30DC_9E8C_DEA2_DC13L, + /* 213 */ 0x5F0D_F8D8_2CF4_D46BL, 0x1D13_C630_164B_9318L, + /* 214 */ 0x76D1_770E_3832_0986L, 0x0458_B7BC_1BDE_77DDL, + /* 215 */ 0x4A42_EA68_E31F_45F3L, 0x62B7_72D5_916B_0AEBL, + /* 216 */ 0x5CD3_A503_1BE7_1770L, 0x5B65_4F8A_F5C5_CDA5L, + /* 217 */ 0x7408_8E43_E2E0_DD4CL, 0x723E_A36D_B337_410EL, + /* 218 */ 0x4885_58EA_6DCC_8A50L, 0x0767_2624_9002_88A9L, + /* 219 */ 0x5AA6_AF25_093F_ACE4L, 0x0940_EFAD_B403_2AD3L, + /* 220 */ 0x7150_5AEE_4B8F_981DL, 0x0B91_2B99_2103_F588L, + /* 221 */ 0x46D2_38D4_EF39_BF12L, 0x173A_BB3F_B4A2_7975L, + /* 222 */ 0x5886_C70A_2B08_2ED6L, 0x5D09_6A0F_A1CB_17D2L, + /* 223 */ 0x6EA8_78CC_B5CA_3A8CL, 0x344B_C493_8A3D_DDC7L, + /* 224 */ 0x4529_4B7F_F19E_6497L, 0x60AF_5ADC_3666_AA9CL, + /* 225 */ 0x5673_9E5F_EE05_FDBDL, 0x58DB_3193_4400_5543L, + /* 226 */ 0x6C10_85F7_E987_7D2DL, 0x0F11_FDF8_1500_6A94L, + /* 227 */ 0x438A_53BA_F1F4_AE3CL, 0x196B_3EBB_0D20_429DL, + /* 228 */ 0x546C_E8A9_AE71_D9CBL, 0x1FC6_0E69_D068_5344L, + /* 229 */ 0x6988_22D4_1A0E_503EL, 0x07B7_9204_4482_6815L, + /* 230 */ 0x41F5_15C4_9048_F226L, 0x64D2_BB42_AAD1_810DL, + /* 231 */ 0x5272_5B35_B45B_2EB0L, 0x3E07_6A13_5585_E150L, + /* 232 */ 0x670E_F203_2171_FA5CL, 0x4D89_4498_2AE7_59A4L, + /* 233 */ 0x4069_5741_F4E7_3C79L, 0x7075_CADF_1AD0_9807L, + /* 234 */ 0x5083_AD12_7221_0B98L, 0x2C93_3D96_E184_BE08L, + /* 235 */ 0x64A4_9857_0EA9_4E7EL, 0x37B8_0CFC_99E5_ED8AL, + /* 236 */ 0x7DCD_BE6C_D253_A21EL, 0x05A6_103B_C05F_68EDL, + /* 237 */ 0x4EA0_9704_0374_4552L, 0x6387_CA25_583B_A194L, + /* 238 */ 0x6248_BCC5_0451_56A7L, 0x3C69_BCAE_AE4A_89F9L, + /* 239 */ 0x7ADA_EBF6_4565_AC51L, 0x2B84_2BDA_59DD_2C77L, + /* 240 */ 0x4CC8_D379_EB5F_8BB2L, 0x6B32_9B68_782A_3BCBL, + /* 241 */ 0x5FFB_0858_6637_6E9FL, 0x45FF_4242_9634_CABDL, + /* 242 */ 0x77F9_CA6E_7FC5_4A47L, 0x377F_12D3_3BC1_FD6DL, + /* 243 */ 0x4AFC_1E85_0FDB_4E6CL, 0x52AF_6BC4_0559_3E64L, + /* 244 */ 0x5DBB_2626_53D2_2207L, 0x675B_46B5_06AF_8DFDL, + /* 245 */ 0x7529_EFAF_E8C6_AA89L, 0x6132_1862_485B_717CL, + /* 246 */ 0x493A_35CD_F17C_2A96L, 0x0CBF_4F3D_6D39_26EEL, + /* 247 */ 0x5B88_C341_6DDB_353BL, 0x4FEF_230C_C887_70A9L, + /* 248 */ 0x726A_F411_C952_028AL, 0x43EA_EBCF_FAA9_4CD3L, + /* 249 */ 0x4782_D88B_1DD3_4196L, 0x4A72_D361_FCA9_D004L, + /* 250 */ 0x5963_8EAD_E548_11FCL, 0x1D0F_883A_7BD4_4405L, + /* 251 */ 0x6FBC_7259_5E9A_167BL, 0x2453_6A49_1AC9_5506L, + /* 252 */ 0x45D5_C777_DB20_4E0DL, 0x06B4_226D_B0BD_D524L, + /* 253 */ 0x574B_3955_D1E8_6190L, 0x2861_2B09_1CED_4A6DL, + /* 254 */ 0x6D1E_07AB_4662_79F4L, 0x3279_75CB_6428_9D08L, + /* 255 */ 0x4432_C4CB_0BFD_8C38L, 0x5F8B_E99F_1E99_6225L, + /* 256 */ 0x553F_75FD_CEFC_EF46L, 0x776E_E406_E63F_BAAEL, + /* 257 */ 0x6A8F_537D_42BC_2B18L, 0x554A_9D08_9FCF_A95AL, + /* 258 */ 0x4299_942E_49B5_9AEFL, 0x354E_A225_63E1_C9D8L, + /* 259 */ 0x533F_F939_DC23_01ABL, 0x22A2_4AAE_BCDA_3C4EL, + /* 260 */ 0x680F_F788_532B_C216L, 0x0B4A_DD5A_6C10_CB62L, + /* 261 */ 0x4109_FAB5_33FB_594DL, 0x670E_CA58_838A_7F1DL, + /* 262 */ 0x514C_7962_80FA_2FA1L, 0x20D2_7CEE_A46D_1EE4L, + /* 263 */ 0x659F_97BB_2138_BB89L, 0x4907_1C2A_4D88_669DL, + /* 264 */ 0x7F07_7DA9_E986_EA6BL, 0x7B48_E334_E0EA_8045L, + /* 265 */ 0x4F64_AE8A_31F4_5283L, 0x3D0D_8E01_0C92_902BL, + /* 266 */ 0x633D_DA2C_BE71_6724L, 0x2C50_F181_4FB7_3436L, + /* 267 */ 0x7C0D_50B7_EE0D_C0EDL, 0x3765_2DE1_A3A5_0143L, + /* 268 */ 0x4D88_5272_F4C8_9894L, 0x329F_3CAD_0647_20CAL, + /* 269 */ 0x60EA_670F_B1FA_BEB9L, 0x3F47_0BD8_47D8_E8FDL, + /* 270 */ 0x7925_00D3_9E79_6E67L, 0x6F18_CECE_59CF_233CL, + /* 271 */ 0x4BB7_2084_430B_E500L, 0x756F_8140_F821_7605L, + /* 272 */ 0x5EA4_E8A5_53CE_DE41L, 0x12CB_6191_3629_D387L, + /* 273 */ 0x764E_22CE_A8C2_95D1L, 0x377E_39F5_83B4_4868L, + /* 274 */ 0x49F0_D5C1_2979_9DA2L, 0x72AE_E439_7250_AD41L, + /* 275 */ 0x5C6D_0B31_73D8_050BL, 0x4F5A_9D47_CEE4_D891L, + /* 276 */ 0x7388_4DFD_D0CE_064EL, 0x4331_4499_C29E_0EB6L, + /* 277 */ 0x4835_30BE_A280_C3F1L, 0x09FE_CAE0_19A2_C932L, + /* 278 */ 0x5A42_7CEE_4B20_F4EDL, 0x2C7E_7D98_200B_7B7EL, + /* 279 */ 0x70D3_1C29_DDE9_3228L, 0x579E_1CFE_280E_5A5DL, + /* 280 */ 0x4683_F19A_2AB1_BF59L, 0x36C2_D21E_D908_F87BL, + /* 281 */ 0x5824_EE00_B55E_2F2FL, 0x6473_86A6_8F4B_3699L, + /* 282 */ 0x6E2E_2980_E2B5_BAFBL, 0x5D90_6850_331E_043FL, + /* 283 */ 0x44DC_D9F0_8DB1_94DDL, 0x2A7A_4132_1FF2_C2A8L, + /* 284 */ 0x5614_106C_B11D_FA14L, 0x5518_D17E_A7EF_7352L, + /* 285 */ 0x6B99_1487_DD65_7899L, 0x6A5F_05DE_51EB_5026L, + /* 286 */ 0x433F_ACD4_EA5F_6B60L, 0x127B_63AA_F333_1218L, + /* 287 */ 0x540F_980A_24F7_4638L, 0x171A_3C95_AFFF_D69EL, + /* 288 */ 0x6913_7E0C_AE35_17C6L, 0x1CE0_CBBB_1BFF_CC45L, + /* 289 */ 0x41AC_2EC7_ECE1_2EDBL, 0x720C_7F54_F17F_DFABL, + /* 290 */ 0x5217_3A79_E819_7A92L, 0x6E8F_9F2A_2DDF_D796L, + /* 291 */ 0x669D_0918_621F_D937L, 0x4A33_86F4_B957_CD7BL, + /* 292 */ 0x4022_25AF_3D53_E7C2L, 0x5E60_3458_F3D6_E06DL, + /* 293 */ 0x502A_AF1B_0CA8_E1B3L, 0x35F8_416F_30CC_9888L, + /* 294 */ 0x6435_5AE1_CFD3_1A20L, 0x2376_51CA_FCFF_BEAAL, + /* 295 */ 0x7D42_B19A_43C7_E0A8L, 0x2C53_E63D_BC3F_AE55L, + /* 296 */ 0x4E49_AF00_6A5C_EC69L, 0x1BB4_6FE6_95A7_CCF5L, + /* 297 */ 0x61DC_1AC0_84F4_2783L, 0x42A1_8BE0_3B11_C033L, + /* 298 */ 0x7A53_2170_A631_3164L, 0x3349_EED8_49D6_303FL, + /* 299 */ 0x4C73_F4E6_67DE_BEDEL, 0x600E_3547_2E25_DE28L, + /* 300 */ 0x5F90_F220_01D6_6E96L, 0x3811_C298_F9AF_55B1L, + /* 301 */ 0x7775_2EA8_024C_0A3CL, 0x0616_333F_381B_2B1EL, + /* 302 */ 0x4AA9_3D29_016F_8665L, 0x43CD_E007_8310_FAF3L, + /* 303 */ 0x5D53_8C73_41CB_67FEL, 0x74C1_5809_63D5_39AFL, + /* 304 */ 0x74A8_6F90_123E_41FEL, 0x51F1_AE0B_BCCA_881BL, + /* 305 */ 0x48E9_45BA_0B66_E93FL, 0x1337_0CC7_55FE_9511L, + /* 306 */ 0x5B23_9728_8E40_A38EL, 0x7804_CFF9_2B7E_3A55L, + /* 307 */ 0x71EC_7CF2_B1D0_CC72L, 0x5606_03F7_765D_C8EAL, + /* 308 */ 0x4733_CE17_AF22_7FC7L, 0x55C3_C27A_A9FA_9D93L, + /* 309 */ 0x5900_C19D_9AEB_1FB9L, 0x4B34_B319_5479_44F7L, + /* 310 */ 0x6F40_F205_01A5_E7A7L, 0x7E01_DFDF_A997_9635L, + /* 311 */ 0x4588_9743_2107_B0C8L, 0x7EC1_2BEB_C9FE_BDE1L, + /* 312 */ 0x56EA_BD13_E949_9CFBL, 0x1E71_76E6_BC7E_6D59L, + /* 313 */ 0x6CA5_6C58_E39C_043AL, 0x060D_D4A0_6B9E_08B0L, + /* 314 */ 0x43E7_63B7_8E41_82A4L, 0x23C8_A4E4_4342_C56EL, + /* 315 */ 0x54E1_3CA5_71D1_E34DL, 0x2CBA_CE1D_5413_76C9L, + /* 316 */ 0x6A19_8BCE_CE46_5C20L, 0x57E9_81A4_A918_547BL, + /* 317 */ 0x424F_F761_40EB_F994L, 0x36F1_F106_E9AF_34CDL, + /* 318 */ 0x52E3_F539_9126_F7F9L, 0x44AE_6D48_A41B_0201L, + /* 319 */ 0x679C_F287_F570_B5F7L, 0x75DA_089A_CD21_C281L, + /* 320 */ 0x40C2_1794_F966_71BAL, 0x79A8_4560_C035_1991L, + /* 321 */ 0x50F2_9D7A_37C0_0E29L, 0x5812_56B8_F042_5FF5L, + /* 322 */ 0x652F_44D8_C5B0_11B4L, 0x0E16_EC67_2C52_F7F2L, + /* 323 */ 0x7E7B_160E_F71C_1621L, 0x119C_A780_F767_B5EEL, + /* 324 */ 0x4F0C_EDC9_5A71_8DD4L, 0x5B01_E8B0_9AA0_D1B5L, + }; + +} diff --git a/test/jdk/java/lang/FPToDecimal/DoubleToDecString.java b/test/jdk/java/lang/FPToDecimal/DoubleToDecString.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/lang/FPToDecimal/DoubleToDecString.java @@ -0,0 +1,320 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +import java.util.Random; + +import static java.lang.Math.*; +import static java.lang.Double.*; + +/* + * @test + * @bug 8202555 + * @author Raffaello Giulietti + */ +public class DoubleToDecString { + + private static final boolean FAILURE_THROWS_EXCEPTION = true; + + private static void assertTrue(boolean ok, double v, String s) { + if (ok) { + return; + } + String message = "Double::toString applied to " + + "Double.longBitsToDouble(" + + "0x" + Long.toHexString(doubleToRawLongBits(v)) + "L" + + ")" + + " returns " + + "\"" + s + "\"" + + ", which is not correct according to the specification."; + if (FAILURE_THROWS_EXCEPTION) { + throw new RuntimeException(message); + } + System.err.println(message); + } + + private static void toDec(double v) { +// String s = Double.toString(v); + String s = DoubleToDecimal.toString(v); + assertTrue(new DoubleToStringChecker(v, s).isOK(), v, s); + } + + private static void testExtremeValues() { + toDec(NEGATIVE_INFINITY); + toDec(-MAX_VALUE); + toDec(-MIN_NORMAL); + toDec(-MIN_VALUE); + toDec(-0.0); + toDec(0.0); + toDec(MIN_VALUE); + toDec(MIN_NORMAL); + toDec(MAX_VALUE); + toDec(POSITIVE_INFINITY); + toDec(NaN); + + /* + Quiet NaNs have the most significant bit of the mantissa as 1, + while signaling NaNs have it as 0. + Exercise 4 combinations of quiet/signaling NaNs and + "positive/negative" NaNs + */ + toDec(longBitsToDouble(0x7FF8_0000_0000_0001L)); + toDec(longBitsToDouble(0x7FF0_0000_0000_0001L)); + toDec(longBitsToDouble(0xFFF8_0000_0000_0001L)); + toDec(longBitsToDouble(0xFFF0_0000_0000_0001L)); + + /* + All values treated specially by Schubfach + */ + toDec(4.9E-324); + toDec(9.9E-324); + } + + /* + A few "powers of 10" are incorrectly rendered by the JDK. + The rendering is either too long or it is not the closest decimal. + */ + private static void testPowersOf10() { + for (int e = -323; e <= 309; ++e) { + toDec(parseDouble("1e" + e)); + } + } + + /* + Many powers of 2 are incorrectly rendered by the JDK. + The rendering is either too long or it is not the closest decimal. + */ + private static void testPowersOf2() { + for (double v = MIN_VALUE; v <= MAX_VALUE; v *= 2.0) { + toDec(v); + } + } + + /* + There are tons of doubles that are rendered incorrectly by the JDK. + While the renderings correctly round back to the original value, + they are longer than needed or are not the closest decimal to the double. + Here are just a very few examples. + */ + private static final String[] Anomalies = { + // JDK renders these, and others, with 18 digits! + "2.82879384806159E17", "1.387364135037754E18", + "1.45800632428665E17", + + // JDK renders these longer than needed. + "1.6E-322", "6.3E-322", + "7.3879E20", "2.0E23", "7.0E22", "9.2E22", + "9.5E21", "3.1E22", "5.63E21", "8.41E21", + + // JDK does not render these, and many others, as the closest. + "9.9E-324", "9.9E-323", + "1.9400994884341945E25", "3.6131332396758635E25", + "2.5138990223946153E25", + }; + + private static void testSomeAnomalies() { + for (String dec : Anomalies) { + toDec(parseDouble(dec)); + } + } + + /* + Values are from + Paxson V, "A Program for Testing IEEE Decimal-Binary Conversion" + */ + private static final double[] PaxsonSignificands = { + 8_511_030_020_275_656L, + 5_201_988_407_066_741L, + 6_406_892_948_269_899L, + 8_431_154_198_732_492L, + 6_475_049_196_144_587L, + 8_274_307_542_972_842L, + 5_381_065_484_265_332L, + 6_761_728_585_499_734L, + 7_976_538_478_610_756L, + 5_982_403_858_958_067L, + 5_536_995_190_630_837L, + 7_225_450_889_282_194L, + 7_225_450_889_282_194L, + 8_703_372_741_147_379L, + 8_944_262_675_275_217L, + 7_459_803_696_087_692L, + 6_080_469_016_670_379L, + 8_385_515_147_034_757L, + 7_514_216_811_389_786L, + 8_397_297_803_260_511L, + 6_733_459_239_310_543L, + 8_091_450_587_292_794L, + + 6_567_258_882_077_402L, + 6_712_731_423_444_934L, + 6_712_731_423_444_934L, + 5_298_405_411_573_037L, + 5_137_311_167_659_507L, + 6_722_280_709_661_868L, + 5_344_436_398_034_927L, + 8_369_123_604_277_281L, + 8_995_822_108_487_663L, + 8_942_832_835_564_782L, + 8_942_832_835_564_782L, + 8_942_832_835_564_782L, + 6_965_949_469_487_146L, + 6_965_949_469_487_146L, + 6_965_949_469_487_146L, + 7_487_252_720_986_826L, + 5_592_117_679_628_511L, + 8_887_055_249_355_788L, + 6_994_187_472_632_449L, + 8_797_576_579_012_143L, + 7_363_326_733_505_337L, + 8_549_497_411_294_502L, + }; + + private static final int[] PaxsonExponents = { + -342, + -824, + 237, + 72, + 99, + 726, + -456, + -57, + 376, + 377, + 93, + 710, + 709, + 117, + -1, + -707, + -381, + 721, + -828, + -345, + 202, + -473, + + 952, + 535, + 534, + -957, + -144, + 363, + -169, + -853, + -780, + -383, + -384, + -385, + -249, + -250, + -251, + 548, + 164, + 665, + 690, + 588, + 272, + -448, + }; + + private static void testPaxson() { + for (int i = 0; i < PaxsonSignificands.length; ++i) { + toDec(scalb(PaxsonSignificands[i], PaxsonExponents[i])); + } + } + + /* + Tests all integers of the form yx_xxx_000_000_000_000_000, y != 0. + These are all exact doubles. + */ + private static void testLongs() { + for (int i = 10_000; i < 100_000; ++i) { + toDec(i * 1e15); + } + } + + /* + Tests all integers up to 100_000. + These are all exact doubles. + */ + private static void testInts() { + for (int i = 0; i <= 1_000_000; ++i) { + toDec(i); + } + } + + /* + Random doubles over the whole range + */ + private static void testRandom() { + Random r = new Random(); + for (int i = 0; i < 1_000_000; ++i) { + toDec(longBitsToDouble(r.nextLong())); + } + } + + /* + Random doubles over the integer range [0, 10^15). + These integers are all exact doubles. + */ + private static void testRandomUnit() { + Random r = new Random(); + for (int i = 0; i < 100_000; ++i) { + toDec(r.nextLong() % 1_000_000_000_000_000L); + } + } + + /* + Random doubles over the range [0, 10^15) as "multiples" of 1e-3 + */ + private static void testRandomMilli() { + Random r = new Random(); + for (int i = 0; i < 100_000; ++i) { + toDec(r.nextLong() % 1_000_000_000_000_000_000L / 1e3); + } + } + + /* + Random doubles over the range [0, 10^15) as "multiples" of 1e-6 + */ + private static void testRandomMicro() { + Random r = new Random(); + for (int i = 0; i < 100_000; ++i) { + toDec((r.nextLong() & 0x7FFF_FFFF_FFFF_FFFFL) / 1e6); + } + } + + public static void main(String[] args) { + testExtremeValues(); + testSomeAnomalies(); + testPowersOf2(); + testPowersOf10(); + testPaxson(); + testInts(); + testLongs(); + testRandom(); + testRandomUnit(); + testRandomMilli(); + testRandomMicro(); + } + +} diff --git a/test/jdk/java/lang/FPToDecimal/DoubleToStringChecker.java b/test/jdk/java/lang/FPToDecimal/DoubleToStringChecker.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/lang/FPToDecimal/DoubleToStringChecker.java @@ -0,0 +1,92 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +import java.math.BigDecimal; + +/** + * @author Raffaello Giulietti + */ +class DoubleToStringChecker extends StringChecker { + + private double v; + + DoubleToStringChecker(double v, String s) { + super(s); + this.v = v; + } + + @Override + BigDecimal toBigDecimal() { + return new BigDecimal(v); + } + + @Override + boolean recovers(BigDecimal b) { + return b.doubleValue() == v; + } + + @Override + boolean recovers(String s) { + return Double.parseDouble(s) == v; + } + + @Override + int maxExp() { + return 309; + } + + @Override + int minExp() { + return -323; + } + + @Override + int maxLen10() { + return 17; + } + + @Override + boolean isZero() { + return v == 0; + } + + @Override + boolean isInfinity() { + return v == Double.POSITIVE_INFINITY; + } + + @Override + void invert() { + v = -v; + } + + @Override + boolean isNegative() { + return Double.doubleToRawLongBits(v) < 0; + } + + @Override + boolean isNaN() { + return Double.isNaN(v); + } + +} diff --git a/test/jdk/java/lang/FPToDecimal/FloatToDecString.java b/test/jdk/java/lang/FPToDecimal/FloatToDecString.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/lang/FPToDecimal/FloatToDecString.java @@ -0,0 +1,157 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +import java.util.Random; + +import static java.lang.Float.*; + +/* + * @test + * @author Raffaello Giulietti + */ +public class FloatToDecString { + + private static final boolean FAILURE_THROWS_EXCEPTION = true; + + private static void assertTrue(boolean ok, float v, String s) { + if (ok) { + return; + } + String message = "Float::toString applied to " + + "Float.intBitsToFloat(" + + "0x" + Integer.toHexString(floatToRawIntBits(v)) + + ")" + + " returns " + + "\"" + s + "\"" + + ", which is not correct according to the specification."; + if (FAILURE_THROWS_EXCEPTION) { + throw new RuntimeException(message); + } + System.err.println(message); + } + + private static void toDec(float v) { +// String s = Float.toString(v); + String s = FloatToDecimal.toString(v); + assertTrue(new FloatToStringChecker(v, s).isOK(), v, s); + } + + /* + MIN_NORMAL is incorrectly rendered by the JDK. + */ + private static void testExtremeValues() { + toDec(NEGATIVE_INFINITY); + toDec(-MAX_VALUE); + toDec(-MIN_NORMAL); + toDec(-MIN_VALUE); + toDec(-0.0f); + toDec(0.0f); + toDec(MIN_VALUE); + toDec(MIN_NORMAL); + toDec(MAX_VALUE); + toDec(POSITIVE_INFINITY); + toDec(NaN); + + /* + Quiet NaNs have the most significant bit of the mantissa as 1, + while signaling NaNs have it as 0. + Exercise 4 combinations of quiet/signaling NaNs and + "positive/negative" NaNs. + */ + toDec(intBitsToFloat(0x7FC0_0001)); + toDec(intBitsToFloat(0x7F80_0001)); + toDec(intBitsToFloat(0xFFC0_0001)); + toDec(intBitsToFloat(0xFF80_0001)); + + /* + All values treated specially by Schubfach + */ + toDec(1.4E-45F); + toDec(2.8E-45F); + toDec(4.2E-45F); + toDec(5.6E-45F); + toDec(7.0E-45F); + toDec(8.4E-45F); + toDec(9.8E-45F); + } + + /* + Many "powers of 10" are incorrectly rendered by the JDK. + The rendering is either too long or it is not the closest decimal. + */ + private static void testPowersOf10() { + for (int e = -44; e <= 39; ++e) { + toDec(parseFloat("1e" + e)); + } + } + + /* + Many powers of 2 are incorrectly rendered by the JDK. + The rendering is either too long or it is not the closest decimal. + */ + private static void testPowersOf2() { + for (float v = MIN_VALUE; v <= MAX_VALUE; v *= 2.0) { + toDec(v); + } + } + + /* + Tests all integers up to 1_000_000. + These are all exact floats. + */ + private static void testInts() { + for (int i = 0; i <= 1_000_000; ++i) { + toDec(i); + } + } + + /* + Random floats over the whole range. + */ + private static void testRandom() { + Random r = new Random(); + for (int i = 0; i < 1_000_000; ++i) { + toDec(intBitsToFloat(r.nextInt())); + } + } + + /* + All, really all, possible floats. Takes between 90 and 120 minutes. + */ + private static void testAll() { + int bits = Integer.MIN_VALUE; + for (; bits < Integer.MAX_VALUE; ++bits) { + toDec(Float.intBitsToFloat(bits)); + } + toDec(Float.intBitsToFloat(bits)); + } + + public static void main(String[] args) { +// testAll(); + testExtremeValues(); + testPowersOf2(); + testPowersOf10(); + testInts(); + testRandom(); + } + +} diff --git a/test/jdk/java/lang/FPToDecimal/FloatToStringChecker.java b/test/jdk/java/lang/FPToDecimal/FloatToStringChecker.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/lang/FPToDecimal/FloatToStringChecker.java @@ -0,0 +1,92 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +import java.math.BigDecimal; + +/** + * @author Raffaello Giulietti + */ +class FloatToStringChecker extends StringChecker { + + private float v; + + FloatToStringChecker(float v, String s) { + super(s); + this.v = v; + } + + @Override + BigDecimal toBigDecimal() { + return new BigDecimal(v); + } + + @Override + boolean recovers(BigDecimal b) { + return b.floatValue() == v; + } + + @Override + boolean recovers(String s) { + return Float.parseFloat(s) == v; + } + + @Override + int maxExp() { + return 39; + } + + @Override + int minExp() { + return -44; + } + + @Override + int maxLen10() { + return 9; + } + + @Override + boolean isZero() { + return v == 0; + } + + @Override + boolean isInfinity() { + return v == Float.POSITIVE_INFINITY; + } + + @Override + void invert() { + v = -v; + } + + @Override + boolean isNegative() { + return Float.floatToRawIntBits(v) < 0; + } + + @Override + boolean isNaN() { + return Float.isNaN(v); + } + +} diff --git a/test/jdk/java/lang/FPToDecimal/MathUtilsChecks.java b/test/jdk/java/lang/FPToDecimal/MathUtilsChecks.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/lang/FPToDecimal/MathUtilsChecks.java @@ -0,0 +1,438 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +import java.math.BigInteger; + +import static java.math.BigInteger.*; + +import static jdk.internal.math.MathUtils.*; + +/* + * @test + * @author Raffaello Giulietti + */ +public class MathUtilsChecks { + + private static final BigInteger THREE = BigInteger.valueOf(3); + + private static void check(boolean claim) { + if (!claim) { + throw new RuntimeException(); + } + } + + /* + Let + 10^e = beta 2^r + for the unique integer r and real beta meeting + 2^125 <= beta < 2^126 + Further, let g = g1 2^63 + g0. + Checks that: + 2^62 <= g1 < 2^63, + 0 <= g0 < 2^63, + g - 1 <= beta < g, (that is, g = floor(beta) + 1) + The last predicate, after multiplying by 2^r, is equivalent to + (g - 1) 2^r < 10^e <= g 2^r + This is the predicate that will be checked in various forms. + + Throws an exception iff the check fails. + */ + private static void checkPow10(int e, long g1, long g0) { + // 2^62 <= g1 < 2^63, 0 <= g0 < 2^63 + check(g1 << 1 < 0 && g1 >= 0 && g0 >= 0); + + BigInteger g = valueOf(g1).shiftLeft(63).or(valueOf(g0)); + // double check that 2^125 <= g < 2^126 + check(g.signum() > 0 && g.bitLength() == 126); + + // see javadoc of MathUtils.g1(int) + int r = flog2pow10(e) - 125; + + /* + The predicate + (g - 1) 2^r <= 10^e < g 2^r + is equivalent to + g - 1 <= 10^e 2^(-r) < g + When + e >= 0 & r < 0 + all numerical subexpressions are integer-valued. This is the same as + g - 1 = 10^e 2^(-r) + */ + if (e >= 0 && r < 0) { + check(g.subtract(ONE).compareTo(TEN.pow(e).shiftLeft(-r)) == 0); + return; + } + + /* + The predicate + (g - 1) 2^r <= 10^e < g 2^r + is equivalent to + g 10^(-e) - 10^(-e) <= 2^(-r) < g 10^(-e) + When + e < 0 & r < 0 + all numerical subexpressions are integer-valued. + */ + if (e < 0 && r < 0) { + BigInteger pow5 = TEN.pow(-e); + BigInteger mhs = ONE.shiftLeft(-r); + BigInteger rhs = g.multiply(pow5); + check(rhs.subtract(pow5).compareTo(mhs) <= 0 && + mhs.compareTo(rhs) < 0); + return; + } + + /* + Finally, when + e >= 0 & r >= 0 + the predicate + (g - 1) 2^r < 10^e <= g 2^r + can be used straightforwardly as all numerical subexpressions are + already integer-valued. + */ + if (e >= 0) { + BigInteger mhs = TEN.pow(e); + check(g.subtract(ONE).shiftLeft(r).compareTo(mhs) <= 0 && + mhs.compareTo(g.shiftLeft(r)) < 0); + return; + } + + /* + For combinatorial reasons, the only remaining case is + e < 0 & r >= 0 + which, however, cannot arise. Indeed, the predicate + (g - 1) 2^r <= 10^e < g 2^r + implies + (g - 1) 2^r 10^(-e) <= 1 + which cannot hold, as the left-hand side is greater than 1. + */ + check(false); + } + + /* + Verifies the soundness of the values returned by + g1() and g0(). + */ + private static void testPow10Table() { + for (int e = MIN_EXP; e <= MAX_EXP; ++e) { + checkPow10(e, g1(e), g0(e)); + } + } + + /* + Let + k = floor(log10(3/4 2^e)) + The method verifies that + k = flog10threeQuartersPow2(e), |e| <= 300_000 + This range amply covers all binary exponents of IEEE 754 binary formats up + to binary256 (octuple precision), so also suffices for doubles and floats. + + The first equation above is equivalent to + 10^k <= 3 2^(e-2) < 10^(k+1) + Equality never holds. Henceforth, the predicate to check is + 10^k < 3 2^(e-2) < 10^(k+1) + This will be transformed in various ways for checking purposes. + + For integer n > 0, let further + b = len2(n) + denote its length in bits. This means exactly the same as + 2^(b-1) <= n < 2^b + */ + private static void testFlog10threeQuartersPow2() { + /* + First check the case e = 1 + */ + check(flog10threeQuartersPow2(1) == 0); + + /* + Now check the range -300_000 <= e <= 0. + By rewriting, the predicate to check is equivalent to + 3 10^(-k-1) < 2^(2-e) < 3 10^(-k) + As e <= 0, it follows that 2^(2-e) >= 4 and the right inequality + implies k < 0, so the powers of 10 are integers. + + The left inequality is equivalent to + len2(3 10^(-k-1)) <= 2 - e + and the right inequality to + 2 - e < len2(3 10^(-k)) + The original predicate is therefore equivalent to + len2(3 10^(-k-1)) <= 2 - e < len2(3 10^(-k)) + + Starting with e = 0 and decrementing until the lower bound, the code + keeps track of the two powers of 10 to avoid recomputing them. + This is easy because at each iteration k changes at most by 1. A simple + multiplication by 10 computes the next power of 10 when needed. + */ + int e = 0; + int k0 = flog10threeQuartersPow2(e); + check(k0 < 0); + BigInteger l = THREE.multiply(TEN.pow(-k0 - 1)); + BigInteger u = l.multiply(TEN); + for (;;) { + check(l.bitLength() <= 2 - e && 2 - e < u.bitLength()); + if (e == -300_000) { + break; + } + --e; + int kp = flog10threeQuartersPow2(e); + check(kp <= k0); + if (kp < k0) { + // k changes at most by 1 at each iteration, hence: + check(k0 - kp == 1); + k0 = kp; + l = u; + u = u.multiply(TEN); + } + } + + /* + Finally, check the range 2 <= e <= 300_000. + In predicate + 10^k < 3 2^(e-2) < 10^(k+1) + the right inequality shows that k >= 0 as soon as e >= 2. + It is equivalent to + 10^k / 3 < 2^(e-2) < 10^(k+1) / 3 + Both the powers of 10 and the powers of 2 are integer-valued. + The left inequality is therefore equivalent to + floor(10^k / 3) < 2^(e-2) + and thus to + len2(floor(10^k / 3)) <= e - 2 + while the right inequality is equivalent to + 2^(e-2) <= floor(10^(k+1) / 3) + and hence to + e - 2 < len2(floor(10^(k+1) / 3)) + These are summarized as + len2(floor(10^k / 3)) <= e - 2 < len2(floor(10^(k+1) / 3)) + */ + e = 2; + k0 = flog10threeQuartersPow2(e); + check(k0 >= 0); + BigInteger l10 = TEN.pow(k0); + BigInteger u10 = l10.multiply(TEN); + l = l10.divide(THREE); + u = u10.divide(THREE); + for (;;) { + check(l.bitLength() <= e - 2 && e - 2 < u.bitLength()); + if (e == 300_000) { + break; + } + ++e; + int kp = flog10threeQuartersPow2(e); + check(kp >= k0); + if (kp > k0) { + // k changes at most by 1 at each iteration, hence: + check(kp - k0 == 1); + k0 = kp; + u10 = u10.multiply(TEN); + l = u; + u = u10.divide(THREE); + } + } + } + + /* + Let + k = floor(log10(2^e)) + The method verifies that + k = flog10pow2(e), |e| <= 300_000 + This range amply covers all binary exponents of IEEE 754 binary formats up + to binary256 (octuple precision), so also suffices for doubles and floats. + + The first equation above is equivalent to + 10^k <= 2^e < 10^(k+1) + Equality holds iff e = 0, implying k = 0. + Henceforth, the predicates to check are equivalent to + k = 0, if e = 0 + 10^k < 2^e < 10^(k+1), otherwise + The latter will be transformed in various ways for checking purposes. + + For integer n > 0, let further + b = len2(n) + denote its length in bits. This means exactly the same as + 2^(b-1) <= n < 2^b + */ + private static void testFlog10pow2() { + /* + First check the case e = 0 + */ + check(flog10pow2(0) == 0); + + /* + Now check the range -300_000 <= e < 0. + By inverting all quantities, the predicate to check is equivalent to + 10^(-k-1) < 2^(-e) < 10^(-k) + As e < 0, it follows that 2^(-e) >= 2 and the right inequality + implies k < 0. + The left inequality means exactly the same as + len2(10^(-k-1)) <= -e + Similarly, the right inequality is equivalent to + -e < len2(10^(-k)) + The original predicate is therefore equivalent to + len2(10^(-k-1)) <= -e < len2(10^(-k)) + The powers of 10 are integer-valued because k < 0. + + Starting with e = -1 and decrementing towards the lower bound, the code + keeps track of the two powers of 10 so as to avoid recomputing them. + This is easy because at each iteration k changes at most by 1. A simple + multiplication by 10 computes the next power of 10 when needed. + */ + int e = -1; + int k = flog10pow2(e); + check(k < 0); + BigInteger l = TEN.pow(-k - 1); + BigInteger u = l.multiply(TEN); + for (;;) { + check(l.bitLength() <= -e && -e < u.bitLength()); + if (e == -300_000) { + break; + } + --e; + int kp = flog10pow2(e); + check(kp <= k); + if (kp < k) { + // k changes at most by 1 at each iteration, hence: + check(k - kp == 1); + k = kp; + l = u; + u = u.multiply(TEN); + } + } + + /* + Finally, in a similar vein, check the range 0 <= e <= 300_000. + In predicate + 10^k < 2^e < 10^(k+1) + the right inequality shows that k >= 0. + The left inequality means the same as + len2(10^k) <= e + and the right inequality holds iff + e < len2(10^(k+1)) + The original predicate is thus equivalent to + len2(10^k) <= e < len2(10^(k+1)) + As k >= 0, the powers of 10 are integer-valued. + */ + e = 1; + k = flog10pow2(e); + check(k >= 0); + l = TEN.pow(k); + u = l.multiply(TEN); + for (;;) { + check(l.bitLength() <= e && e < u.bitLength()); + if (e == 300_000) { + break; + } + ++e; + int kp = flog10pow2(e); + check(kp >= k); + if (kp > k) { + // k changes at most by 1 at each iteration, hence: + check(kp - k == 1); + k = kp; + l = u; + u = u.multiply(TEN); + } + } + } + + /* + Let + k = floor(log2(10^e)) + The method verifies that + k = flog2pow10(e), |e| <= 100_000 + This range amply covers all decimal exponents of IEEE 754 binary formats up + to binary256 (octuple precision), so also suffices for doubles and floats. + + The first equation above is equivalent to + 2^k <= 10^e < 2^(k+1) + Equality holds iff e = 0, implying k = 0. + Henceforth, the equivalent predicates to check are + k = 0, if e = 0 + 2^k < 10^e < 2^(k+1), otherwise + The latter will be transformed in various ways for checking purposes. + + For integer n > 0, let further + b = len2(n) + denote its length in bits. This means exactly the same as + 2^(b-1) <= n < 2^b + */ + private static void testFlog2pow10() { + /* + First check the case e = 0 + */ + check(flog2pow10(0) == 0); + + /* + Now check the range -100_000 <= e < 0. + By inverting all quantities, the predicate to check is equivalent to + 2^(-k-1) < 10^(-e) < 2^(-k) + As e < 0, this leads to 10^(-e) >= 10 and the right inequality implies + k <= -4. + The above means the same as + len2(10^(-e)) = -k + The powers of 10 are integer values since e < 0. + */ + int e = -1; + int k0 = flog2pow10(e); + check(k0 <= -4); + BigInteger l = TEN; + for (;;) { + check(l.bitLength() == -k0); + if (e == -100_000) { + break; + } + --e; + k0 = flog2pow10(e); + l = l.multiply(TEN); + } + + /* + Finally check the range 0 < e <= 100_000. + From the predicate + 2^k < 10^e < 2^(k+1) + as e > 0, it follows that 10^e >= 10 and the right inequality implies + k >= 3. + The above means the same as + len2(10^e) = k + 1 + The powers of 10 are all integer valued, as e > 0. + */ + e = 1; + k0 = flog2pow10(e); + check(k0 >= 3); + l = TEN; + for (;;) { + check(l.bitLength() == k0 + 1); + if (e == 100_000) { + break; + } + ++e; + k0 = flog2pow10(e); + l = l.multiply(TEN); + } + } + + public static void main(String[] args) { + testPow10Table(); + testFlog10pow2(); + testFlog10threeQuartersPow2(); + testFlog2pow10(); + } + +} diff --git a/test/jdk/java/lang/FPToDecimal/StringChecker.java b/test/jdk/java/lang/FPToDecimal/StringChecker.java new file mode 100644 --- /dev/null +++ b/test/jdk/java/lang/FPToDecimal/StringChecker.java @@ -0,0 +1,354 @@ +/* + * Copyright 2018-2019 Raffaello Giulietti + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE 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. + */ + +import java.io.IOException; +import java.io.StringReader; +import java.math.BigDecimal; + +/** + * @author Raffaello Giulietti + */ +abstract class StringChecker { + /* + A checker for the Javadoc specification. + It just relies on straightforward use of (expensive) BigDecimal arithmetic, + not optimized at all. + */ + + private String s; + private long c; + private int q; + private int len10; + + StringChecker(String s) { + this.s = s; + } + + /* + Returns whether s syntactically meets the expected output of + Double::toString. It is restricted to finite positive outputs. + It is an unusually long method but rather straightforward, too. + Many conditionals could be merged, but KISS here. + */ + private boolean parse() { + try { + // first determine interesting boundaries in the string + StringReader r = new StringReader(s); + int ch = r.read(); + + int i = 0; + while (ch == '0') { + ++i; + ch = r.read(); + } + // i is just after zeroes starting the integer + + int p = i; + while ('0' <= ch && ch <= '9') { + c = 10 * c + (ch - '0'); + if (c < 0) { + return false; + } + ++len10; + ++p; + ch = r.read(); + } + // p is just after digits ending the integer + + int fz = p; + if (ch == '.') { + ++fz; + ch = r.read(); + } + // fz is just after a decimal '.' + + int f = fz; + while (ch == '0') { + c = 10 * c + (ch - '0'); + if (c < 0) { + return false; + } + ++len10; + ++f; + ch = r.read(); + } + // f is just after zeroes starting the fraction + + if (c == 0) { + len10 = 0; + } + int x = f; + while ('0' <= ch && ch <= '9') { + c = 10 * c + (ch - '0'); + if (c < 0) { + return false; + } + ++len10; + ++x; + ch = r.read(); + } + // x is just after digits ending the fraction + + int g = x; + if (ch == 'E') { + ++g; + ch = r.read(); + } + // g is just after an exponent indicator 'E' + + int ez = g; + if (ch == '-') { + ++ez; + ch = r.read(); + } + // ez is just after a '-' sign in the exponent + + int e = ez; + while (ch == '0') { + ++e; + ch = r.read(); + } + // e is just after zeroes starting the exponent + + int z = e; + while ('0' <= ch && ch <= '9') { + q = 10 * q + (ch - '0'); + if (q < 0) { + return false; + } + ++z; + ch = r.read(); + } + // z is just after digits ending the exponent + + // No other char after the number + if (z != s.length()) { + return false; + } + + // The integer must be present + if (p == 0) { + return false; + } + + // The decimal '.' must be present + if (fz == p) { + return false; + } + + // The fraction must be present + if (x == fz) { + return false; + } + + // The fraction is not 0 or it consists of exactly one 0 + if (f == x && f - fz > 1) { + return false; + } + + // Plain notation, no exponent + if (x == z) { + // At most one 0 starting the integer + if (i > 1) { + return false; + } + + // If the integer is 0, at most 2 zeroes start the fraction + if (i == 1 && f - fz > 2) { + return false; + } + + // The integer cannot have more than 7 digits + if (p > 7) { + return false; + } + + q = fz - x; + + // OK for plain notation + return true; + } + + // Computerized scientific notation + + // The integer has exactly one nonzero digit + if (i != 0 || p != 1) { + return false; + } + + // + // There must be an exponent indicator + if (x == g) { + return false; + } + + // There must be an exponent + if (ez == z) { + return false; + } + + // The exponent must not start with zeroes + if (ez != e) { + return false; + } + + if (g != ez) { + q = -q; + } + + // The exponent must not lie in [-3, 7) + if (-3 <= q && q < 7) { + return false; + } + + q += fz - x; + + // OK for computerized scientific notation + return true; + } catch (IOException ex) { + // An IOException on a StringReader??? Please... + return false; + } + } + + boolean isOK() { + if (isNaN()) { + return s.equals("NaN"); + } + if (isNegative()) { + if (s.isEmpty() || s.charAt(0) != '-') { + return false; + } + invert(); + s = s.substring(1); + } + if (isInfinity()) { + return s.equals("Infinity"); + } + if (isZero()) { + return s.equals("0.0"); + } + if (!parse()) { + return false; + } + if (len10 < 2) { + c *= 10; + q -= 1; + len10 += 1; + } + if (2 > len10 || len10 > maxLen10()) { + return false; + } + + // The exponent is bounded + if (minExp() > q + len10 || q + len10 > maxExp()) { + return false; + } + + // s must recover v + try { + if (!recovers(s)) { + return false; + } + } catch (NumberFormatException e) { + return false; + } + + // Get rid of trailing zeroes, still ensuring at least 2 digits + while (len10 > 2 && c % 10 == 0) { + c /= 10; + q += 1; + len10 -= 1; + } + + if (len10 > 2) { + // Try with a shorter number less than v... + if (recovers(BigDecimal.valueOf(c / 10, -q - 1))) { + return false; + } + + // ... and with a shorter number greater than v + if (recovers(BigDecimal.valueOf(c / 10 + 1, -q - 1))) { + return false; + } + } + + // Try with the decimal predecessor... + BigDecimal dp = c == 10 ? + BigDecimal.valueOf(99, -q + 1) : + BigDecimal.valueOf(c - 1, -q); + if (recovers(dp)) { + BigDecimal bv = toBigDecimal(); + BigDecimal deltav = bv.subtract(BigDecimal.valueOf(c, -q)); + if (deltav.signum() >= 0) { + return true; + } + BigDecimal delta = dp.subtract(bv); + if (delta.signum() >= 0) { + return false; + } + int cmp = deltav.compareTo(delta); + return cmp > 0 || cmp == 0 && (c & 0x1) == 0; + } + + // ... and with the decimal successor + BigDecimal ds = BigDecimal.valueOf(c + 1, -q); + if (recovers(ds)) { + BigDecimal bv = toBigDecimal(); + BigDecimal deltav = bv.subtract(BigDecimal.valueOf(c, -q)); + if (deltav.signum() <= 0) { + return true; + } + BigDecimal delta = ds.subtract(bv); + if (delta.signum() <= 0) { + return false; + } + int cmp = deltav.compareTo(delta); + return cmp < 0 || cmp == 0 && (c & 0x1) == 0; + } + + return true; + } + + abstract BigDecimal toBigDecimal(); + + abstract boolean recovers(BigDecimal b); + + abstract boolean recovers(String s); + + abstract int maxExp(); + + abstract int minExp(); + + abstract int maxLen10(); + + abstract boolean isZero(); + + abstract boolean isInfinity(); + + abstract void invert(); + + abstract boolean isNegative(); + + abstract boolean isNaN(); + +}