1 /*

     2  * Copyright (c) 1996, 2013, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package sun.misc;

    27 

    28 import java.util.Arrays;

    29 import java.util.regex.*;

    30 

    31 /**

    32  * A class for converting between ASCII and decimal representations of a single

    33  * or double precision floating point number. Most conversions are provided via

    34  * static convenience methods, although a <code>BinaryToASCIIConverter</code>

    35  * instance may be obtained and reused.

    36  */

    37 public class FloatingDecimal{

    38     //

    39     // Constants of the implementation;

    40     // most are IEEE-754 related.

    41     // (There are more really boring constants at the end.)

    42     //

    43     static final int    EXP_SHIFT = DoubleConsts.SIGNIFICAND_WIDTH - 1;

    44     static final long   FRACT_HOB = ( 1L<<EXP_SHIFT ); // assumed High-Order bit

    45     static final long   EXP_ONE   = ((long)DoubleConsts.EXP_BIAS)<<EXP_SHIFT; // exponent of 1.0

    46     static final int    MAX_SMALL_BIN_EXP = 62;

    47     static final int    MIN_SMALL_BIN_EXP = -( 63 / 3 );

    48     static final int    MAX_DECIMAL_DIGITS = 15;

    49     static final int    MAX_DECIMAL_EXPONENT = 308;

    50     static final int    MIN_DECIMAL_EXPONENT = -324;

    51     static final int    BIG_DECIMAL_EXPONENT = 324; // i.e. abs(MIN_DECIMAL_EXPONENT)

    52     static final int    MAX_NDIGITS = 1100;

    53 

    54     static final int    SINGLE_EXP_SHIFT  =   FloatConsts.SIGNIFICAND_WIDTH - 1;

    55     static final int    SINGLE_FRACT_HOB  =   1<<SINGLE_EXP_SHIFT;

    56     static final int    SINGLE_MAX_DECIMAL_DIGITS = 7;

    57     static final int    SINGLE_MAX_DECIMAL_EXPONENT = 38;

    58     static final int    SINGLE_MIN_DECIMAL_EXPONENT = -45;

    59     static final int    SINGLE_MAX_NDIGITS = 200;

    60 

    61     static final int    INT_DECIMAL_DIGITS = 9;

    62 

    63     /**

    64      * Converts a double precision floating point value to a <code>String</code>.

    65      *

    66      * @param d The double precision value.

    67      * @return The value converted to a <code>String</code>.

    68      */

    69     public static String toJavaFormatString(double d) {

    70         return getBinaryToASCIIConverter(d).toJavaFormatString();

    71     }

    72 

    73     /**

    74      * Converts a single precision floating point value to a <code>String</code>.

    75      *

    76      * @param f The single precision value.

    77      * @return The value converted to a <code>String</code>.

    78      */

    79     public static String toJavaFormatString(float f) {

    80         return getBinaryToASCIIConverter(f).toJavaFormatString();

    81     }

    82 

    83     /**

    84      * Appends a double precision floating point value to an <code>Appendable</code>.

    85      * @param d The double precision value.

    86      * @param buf The <code>Appendable</code> with the value appended.

    87      */

    88     public static void appendTo(double d, Appendable buf) {

    89         getBinaryToASCIIConverter(d).appendTo(buf);

    90     }

    91 

    92     /**

    93      * Appends a single precision floating point value to an <code>Appendable</code>.

    94      * @param f The single precision value.

    95      * @param buf The <code>Appendable</code> with the value appended.

    96      */

    97     public static void appendTo(float f, Appendable buf) {

    98         getBinaryToASCIIConverter(f).appendTo(buf);

    99     }

   100 

   101     /**

   102      * Converts a <code>String</code> to a double precision floating point value.

   103      *

   104      * @param s The <code>String</code> to convert.

   105      * @return The double precision value.

   106      * @throws NumberFormatException If the <code>String</code> does not

   107      * represent a properly formatted double precision value.

   108      */

   109     public static double parseDouble(String s) throws NumberFormatException {

   110         return readJavaFormatString(s).doubleValue();

   111     }

   112 

   113     /**

   114      * Converts a <code>String</code> to a single precision floating point value.

   115      *

   116      * @param s The <code>String</code> to convert.

   117      * @return The single precision value.

   118      * @throws NumberFormatException If the <code>String</code> does not

   119      * represent a properly formatted single precision value.

   120      */

   121     public static float parseFloat(String s) throws NumberFormatException {

   122         return readJavaFormatString(s).floatValue();

   123     }

   124 

   125     /**

   126      * A converter which can process single or double precision floating point

   127      * values into an ASCII <code>String</code> representation.

   128      */

   129     public interface BinaryToASCIIConverter {

   130         /**

   131          * Converts a floating point value into an ASCII <code>String</code>.

   132          * @return The value converted to a <code>String</code>.

   133          */

   134         public String toJavaFormatString();

   135 

   136         /**

   137          * Appends a floating point value to an <code>Appendable</code>.

   138          * @param buf The <code>Appendable</code> to receive the value.

   139          */

   140         public void appendTo(Appendable buf);

   141 

   142         /**

   143          * Retrieves the decimal exponent most closely corresponding to this value.

   144          * @return The decimal exponent.

   145          */

   146         public int getDecimalExponent();

   147 

   148         /**

   149          * Retrieves the value as an array of digits.

   150          * @param digits The digit array.

   151          * @return The number of valid digits copied into the array.

   152          */

   153         public int getDigits(char[] digits);

   154 

   155         /**

   156          * Indicates the sign of the value.

   157          * @return {@code value < 0.0}.

   158          */

   159         public boolean isNegative();

   160 

   161         /**

   162          * Indicates whether the value is either infinite or not a number.

   163          *

   164          * @return <code>true</code> if and only if the value is <code>NaN</code>

   165          * or infinite.

   166          */

   167         public boolean isExceptional();

   168 

   169         /**

   170          * Indicates whether the value was rounded up during the binary to ASCII

   171          * conversion.

   172          *

   173          * @return <code>true</code> if and only if the value was rounded up.

   174          */

   175         public boolean digitsRoundedUp();

   176 

   177         /**

   178          * Indicates whether the binary to ASCII conversion was exact.

   179          *

   180          * @return <code>true</code> if any only if the conversion was exact.

   181          */

   182         public boolean decimalDigitsExact();

   183     }

   184 

   185     /**

   186      * A <code>BinaryToASCIIConverter</code> which represents <code>NaN</code>

   187      * and infinite values.

   188      */

   189     private static class ExceptionalBinaryToASCIIBuffer implements BinaryToASCIIConverter {

   190         private final String image;

   191         private boolean isNegative;

   192 

   193         public ExceptionalBinaryToASCIIBuffer(String image, boolean isNegative) {

   194             this.image = image;

   195             this.isNegative = isNegative;

   196         }

   197 

   198         @Override

   199         public String toJavaFormatString() {

   200             return image;

   201         }

   202 

   203         @Override

   204         public void appendTo(Appendable buf) {

   205             if (buf instanceof StringBuilder) {

   206                 ((StringBuilder) buf).append(image);

   207             } else if (buf instanceof StringBuffer) {

   208                 ((StringBuffer) buf).append(image);

   209             } else {

   210                 assert false;

   211             }

   212         }

   213 

   214         @Override

   215         public int getDecimalExponent() {

   216             throw new IllegalArgumentException("Exceptional value does not have an exponent");

   217         }

   218 

   219         @Override

   220         public int getDigits(char[] digits) {

   221             throw new IllegalArgumentException("Exceptional value does not have digits");

   222         }

   223 

   224         @Override

   225         public boolean isNegative() {

   226             return isNegative;

   227         }

   228 

   229         @Override

   230         public boolean isExceptional() {

   231             return true;

   232         }

   233 

   234         @Override

   235         public boolean digitsRoundedUp() {

   236             throw new IllegalArgumentException("Exceptional value is not rounded");

   237         }

   238 

   239         @Override

   240         public boolean decimalDigitsExact() {

   241             throw new IllegalArgumentException("Exceptional value is not exact");

   242         }

   243     }

   244 

   245     private static final String INFINITY_REP = "Infinity";

   246     private static final int INFINITY_LENGTH = INFINITY_REP.length();

   247     private static final String NAN_REP = "NaN";

   248     private static final int NAN_LENGTH = NAN_REP.length();

   249 

   250     private static final BinaryToASCIIConverter B2AC_POSITIVE_INFINITY = new ExceptionalBinaryToASCIIBuffer(INFINITY_REP, false);

   251     private static final BinaryToASCIIConverter B2AC_NEGATIVE_INFINITY = new ExceptionalBinaryToASCIIBuffer("-" + INFINITY_REP, true);

   252     private static final BinaryToASCIIConverter B2AC_NOT_A_NUMBER = new ExceptionalBinaryToASCIIBuffer(NAN_REP, false);

   253     private static final BinaryToASCIIConverter B2AC_POSITIVE_ZERO = new BinaryToASCIIBuffer(false, new char[]{'0'});

   254     private static final BinaryToASCIIConverter B2AC_NEGATIVE_ZERO = new BinaryToASCIIBuffer(true,  new char[]{'0'});

   255 

   256     /**

   257      * A buffered implementation of <code>BinaryToASCIIConverter</code>.

   258      */

   259     static class BinaryToASCIIBuffer implements BinaryToASCIIConverter {

   260         private boolean isNegative;

   261         private int decExponent;

   262         private int firstDigitIndex;

   263         private int nDigits;

   264         private final char[] digits;

   265         private final char[] buffer = new char[26];

   266 

   267         //

   268         // The fields below provide additional information about the result of

   269         // the binary to decimal digits conversion done in dtoa() and roundup()

   270         // methods. They are changed if needed by those two methods.

   271         //

   272 

   273         // True if the dtoa() binary to decimal conversion was exact.

   274         private boolean exactDecimalConversion = false;

   275 

   276         // True if the result of the binary to decimal conversion was rounded-up

   277         // at the end of the conversion process, i.e. roundUp() method was called.

   278         private boolean decimalDigitsRoundedUp = false;

   279 

   280         /**

   281          * Default constructor; used for non-zero values,

   282          * <code>BinaryToASCIIBuffer</code> may be thread-local and reused

   283          */

   284         BinaryToASCIIBuffer(){

   285             this.digits = new char[20];

   286         }

   287 

   288         /**

   289          * Creates a specialized value (positive and negative zeros).

   290          */

   291         BinaryToASCIIBuffer(boolean isNegative, char[] digits){

   292             this.isNegative = isNegative;

   293             this.decExponent  = 0;

   294             this.digits = digits;

   295             this.firstDigitIndex = 0;

   296             this.nDigits = digits.length;

   297         }

   298 

   299         @Override

   300         public String toJavaFormatString() {

   301             int len = getChars(buffer);

   302             return new String(buffer, 0, len);

   303         }

   304 

   305         @Override

   306         public void appendTo(Appendable buf) {

   307             int len = getChars(buffer);

   308             if (buf instanceof StringBuilder) {

   309                 ((StringBuilder) buf).append(buffer, 0, len);

   310             } else if (buf instanceof StringBuffer) {

   311                 ((StringBuffer) buf).append(buffer, 0, len);

   312             } else {

   313                 assert false;

   314             }

   315         }

   316 

   317         @Override

   318         public int getDecimalExponent() {

   319             return decExponent;

   320         }

   321 

   322         @Override

   323         public int getDigits(char[] digits) {

   324             System.arraycopy(this.digits,firstDigitIndex,digits,0,this.nDigits);

   325             return this.nDigits;

   326         }

   327 

   328         @Override

   329         public boolean isNegative() {

   330             return isNegative;

   331         }

   332 

   333         @Override

   334         public boolean isExceptional() {

   335             return false;

   336         }

   337 

   338         @Override

   339         public boolean digitsRoundedUp() {

   340             return decimalDigitsRoundedUp;

   341         }

   342 

   343         @Override

   344         public boolean decimalDigitsExact() {

   345             return exactDecimalConversion;

   346         }

   347 

   348         private void setSign(boolean isNegative) {

   349             this.isNegative = isNegative;

   350         }

   351 

   352         /**

   353          * This is the easy subcase --

   354          * all the significant bits, after scaling, are held in lvalue.

   355          * negSign and decExponent tell us what processing and scaling

   356          * has already been done. Exceptional cases have already been

   357          * stripped out.

   358          * In particular:

   359          * lvalue is a finite number (not Inf, nor NaN)

   360          * lvalue > 0L (not zero, nor negative).

   361          *

   362          * The only reason that we develop the digits here, rather than

   363          * calling on Long.toString() is that we can do it a little faster,

   364          * and besides want to treat trailing 0s specially. If Long.toString

   365          * changes, we should re-evaluate this strategy!

   366          */

   367         private void developLongDigits( int decExponent, long lvalue, int insignificantDigits ){

   368             if ( insignificantDigits != 0 ){

   369                 // Discard non-significant low-order bits, while rounding,

   370                 // up to insignificant value.

   371                 long pow10 = FDBigInteger.LONG_5_POW[insignificantDigits] << insignificantDigits; // 10^i == 5^i * 2^i;

   372                 long residue = lvalue % pow10;

   373                 lvalue /= pow10;

   374                 decExponent += insignificantDigits;

   375                 if ( residue >= (pow10>>1) ){

   376                     // round up based on the low-order bits we're discarding

   377                     lvalue++;

   378                 }

   379             }

   380             int  digitno = digits.length -1;

   381             int  c;

   382             if ( lvalue <= Integer.MAX_VALUE ){

   383                 assert lvalue > 0L : lvalue; // lvalue <= 0

   384                 // even easier subcase!

   385                 // can do int arithmetic rather than long!

   386                 int  ivalue = (int)lvalue;

   387                 c = ivalue%10;

   388                 ivalue /= 10;

   389                 while ( c == 0 ){

   390                     decExponent++;

   391                     c = ivalue%10;

   392                     ivalue /= 10;

   393                 }

   394                 while ( ivalue != 0){

   395                     digits[digitno--] = (char)(c+'0');

   396                     decExponent++;

   397                     c = ivalue%10;

   398                     ivalue /= 10;

   399                 }

   400                 digits[digitno] = (char)(c+'0');

   401             } else {

   402                 // same algorithm as above (same bugs, too )

   403                 // but using long arithmetic.

   404                 c = (int)(lvalue%10L);

   405                 lvalue /= 10L;

   406                 while ( c == 0 ){

   407                     decExponent++;

   408                     c = (int)(lvalue%10L);

   409                     lvalue /= 10L;

   410                 }

   411                 while ( lvalue != 0L ){

   412                     digits[digitno--] = (char)(c+'0');

   413                     decExponent++;

   414                     c = (int)(lvalue%10L);

   415                     lvalue /= 10;

   416                 }

   417                 digits[digitno] = (char)(c+'0');

   418             }

   419             this.decExponent = decExponent+1;

   420             this.firstDigitIndex = digitno;

   421             this.nDigits = this.digits.length - digitno;

   422         }

   423 

   424         private void dtoa( int binExp, long fractBits, int nSignificantBits, boolean isCompatibleFormat)

   425         {

   426             assert fractBits > 0 ; // fractBits here can't be zero or negative

   427             assert (fractBits & FRACT_HOB)!=0  ; // Hi-order bit should be set

   428             // Examine number. Determine if it is an easy case,

   429             // which we can do pretty trivially using float/long conversion,

   430             // or whether we must do real work.

   431             final int tailZeros = Long.numberOfTrailingZeros(fractBits);

   432 

   433             // number of significant bits of fractBits;

   434             final int nFractBits = EXP_SHIFT+1-tailZeros;

   435 

   436             // reset flags to default values as dtoa() does not always set these

   437             // flags and a prior call to dtoa() might have set them to incorrect

   438             // values with respect to the current state.

   439             decimalDigitsRoundedUp = false;

   440             exactDecimalConversion = false;

   441 

   442             // number of significant bits to the right of the point.

   443             int nTinyBits = Math.max( 0, nFractBits - binExp - 1 );

   444             if ( binExp <= MAX_SMALL_BIN_EXP && binExp >= MIN_SMALL_BIN_EXP ){

   445                 // Look more closely at the number to decide if,

   446                 // with scaling by 10^nTinyBits, the result will fit in

   447                 // a long.

   448                 if ( (nTinyBits < FDBigInteger.LONG_5_POW.length) && ((nFractBits + N_5_BITS[nTinyBits]) < 64 ) ){

   449                     //

   450                     // We can do this:

   451                     // take the fraction bits, which are normalized.

   452                     // (a) nTinyBits == 0: Shift left or right appropriately

   453                     //     to align the binary point at the extreme right, i.e.

   454                     //     where a long int point is expected to be. The integer

   455                     //     result is easily converted to a string.

   456                     // (b) nTinyBits > 0: Shift right by EXP_SHIFT-nFractBits,

   457                     //     which effectively converts to long and scales by

   458                     //     2^nTinyBits. Then multiply by 5^nTinyBits to

   459                     //     complete the scaling. We know this won't overflow

   460                     //     because we just counted the number of bits necessary

   461                     //     in the result. The integer you get from this can

   462                     //     then be converted to a string pretty easily.

   463                     //

   464                     if ( nTinyBits == 0 ) {

   465                         int insignificant;

   466                         if ( binExp > nSignificantBits ){

   467                             insignificant = insignificantDigitsForPow2(binExp-nSignificantBits-1);

   468                         } else {

   469                             insignificant = 0;

   470                         }

   471                         if ( binExp >= EXP_SHIFT ){

   472                             fractBits <<= (binExp-EXP_SHIFT);

   473                         } else {

   474                             fractBits >>>= (EXP_SHIFT-binExp) ;

   475                         }

   476                         developLongDigits( 0, fractBits, insignificant );

   477                         return;

   478                     }

   479                     //

   480                     // The following causes excess digits to be printed

   481                     // out in the single-float case. Our manipulation of

   482                     // halfULP here is apparently not correct. If we

   483                     // better understand how this works, perhaps we can

   484                     // use this special case again. But for the time being,

   485                     // we do not.

   486                     // else {

   487                     //     fractBits >>>= EXP_SHIFT+1-nFractBits;

   488                     //     fractBits//= long5pow[ nTinyBits ];

   489                     //     halfULP = long5pow[ nTinyBits ] >> (1+nSignificantBits-nFractBits);

   490                     //     developLongDigits( -nTinyBits, fractBits, insignificantDigits(halfULP) );

   491                     //     return;

   492                     // }

   493                     //

   494                 }

   495             }

   496             //

   497             // This is the hard case. We are going to compute large positive

   498             // integers B and S and integer decExp, s.t.

   499             //      d = ( B / S )// 10^decExp

   500             //      1 <= B / S < 10

   501             // Obvious choices are:

   502             //      decExp = floor( log10(d) )

   503             //      B      = d// 2^nTinyBits// 10^max( 0, -decExp )

   504             //      S      = 10^max( 0, decExp)// 2^nTinyBits

   505             // (noting that nTinyBits has already been forced to non-negative)

   506             // I am also going to compute a large positive integer

   507             //      M      = (1/2^nSignificantBits)// 2^nTinyBits// 10^max( 0, -decExp )

   508             // i.e. M is (1/2) of the ULP of d, scaled like B.

   509             // When we iterate through dividing B/S and picking off the

   510             // quotient bits, we will know when to stop when the remainder

   511             // is <= M.

   512             //

   513             // We keep track of powers of 2 and powers of 5.

   514             //

   515             int decExp = estimateDecExp(fractBits,binExp);

   516             int B2, B5; // powers of 2 and powers of 5, respectively, in B

   517             int S2, S5; // powers of 2 and powers of 5, respectively, in S

   518             int M2, M5; // powers of 2 and powers of 5, respectively, in M

   519 

   520             B5 = Math.max( 0, -decExp );

   521             B2 = B5 + nTinyBits + binExp;

   522 

   523             S5 = Math.max( 0, decExp );

   524             S2 = S5 + nTinyBits;

   525 

   526             M5 = B5;

   527             M2 = B2 - nSignificantBits;

   528 

   529             //

   530             // the long integer fractBits contains the (nFractBits) interesting

   531             // bits from the mantissa of d ( hidden 1 added if necessary) followed

   532             // by (EXP_SHIFT+1-nFractBits) zeros. In the interest of compactness,

   533             // I will shift out those zeros before turning fractBits into a

   534             // FDBigInteger. The resulting whole number will be

   535             //      d * 2^(nFractBits-1-binExp).

   536             //

   537             fractBits >>>= tailZeros;

   538             B2 -= nFractBits-1;

   539             int common2factor = Math.min( B2, S2 );

   540             B2 -= common2factor;

   541             S2 -= common2factor;

   542             M2 -= common2factor;

   543 

   544             //

   545             // HACK!! For exact powers of two, the next smallest number

   546             // is only half as far away as we think (because the meaning of

   547             // ULP changes at power-of-two bounds) for this reason, we

   548             // hack M2. Hope this works.

   549             //

   550             if ( nFractBits == 1 ) {

   551                 M2 -= 1;

   552             }

   553 

   554             if ( M2 < 0 ){

   555                 // oops.

   556                 // since we cannot scale M down far enough,

   557                 // we must scale the other values up.

   558                 B2 -= M2;

   559                 S2 -= M2;

   560                 M2 =  0;

   561             }

   562             //

   563             // Construct, Scale, iterate.

   564             // Some day, we'll write a stopping test that takes

   565             // account of the asymmetry of the spacing of floating-point

   566             // numbers below perfect powers of 2

   567             // 26 Sept 96 is not that day.

   568             // So we use a symmetric test.

   569             //

   570             int ndigit = 0;

   571             boolean low, high;

   572             long lowDigitDifference;

   573             int  q;

   574 

   575             //

   576             // Detect the special cases where all the numbers we are about

   577             // to compute will fit in int or long integers.

   578             // In these cases, we will avoid doing FDBigInteger arithmetic.

   579             // We use the same algorithms, except that we "normalize"

   580             // our FDBigIntegers before iterating. This is to make division easier,

   581             // as it makes our fist guess (quotient of high-order words)

   582             // more accurate!

   583             //

   584             // Some day, we'll write a stopping test that takes

   585             // account of the asymmetry of the spacing of floating-point

   586             // numbers below perfect powers of 2

   587             // 26 Sept 96 is not that day.

   588             // So we use a symmetric test.

   589             //

   590             // binary digits needed to represent B, approx.

   591             int Bbits = nFractBits + B2 + (( B5 < N_5_BITS.length )? N_5_BITS[B5] : ( B5*3 ));

   592 

   593             // binary digits needed to represent 10*S, approx.

   594             int tenSbits = S2+1 + (( (S5+1) < N_5_BITS.length )? N_5_BITS[(S5+1)] : ( (S5+1)*3 ));

   595             if ( Bbits < 64 && tenSbits < 64){

   596                 if ( Bbits < 32 && tenSbits < 32){

   597                     // wa-hoo! They're all ints!

   598                     int b = ((int)fractBits * FDBigInteger.SMALL_5_POW[B5] ) << B2;

   599                     int s = FDBigInteger.SMALL_5_POW[S5] << S2;

   600                     int m = FDBigInteger.SMALL_5_POW[M5] << M2;

   601                     int tens = s * 10;

   602                     //

   603                     // Unroll the first iteration. If our decExp estimate

   604                     // was too high, our first quotient will be zero. In this

   605                     // case, we discard it and decrement decExp.

   606                     //

   607                     ndigit = 0;

   608                     q = b / s;

   609                     b = 10 * ( b % s );

   610                     m *= 10;

   611                     low  = (b <  m );

   612                     high = (b+m > tens );

   613                     assert q < 10 : q; // excessively large digit

   614                     if ( (q == 0) && ! high ){

   615                         // oops. Usually ignore leading zero.

   616                         decExp--;

   617                     } else {

   618                         digits[ndigit++] = (char)('0' + q);

   619                     }

   620                     //

   621                     // HACK! Java spec sez that we always have at least

   622                     // one digit after the . in either F- or E-form output.

   623                     // Thus we will need more than one digit if we're using

   624                     // E-form

   625                     //

   626                     if ( !isCompatibleFormat ||decExp < -3 || decExp >= 8 ){

   627                         high = low = false;

   628                     }

   629                     while( ! low && ! high ){

   630                         q = b / s;

   631                         b = 10 * ( b % s );

   632                         m *= 10;

   633                         assert q < 10 : q; // excessively large digit

   634                         if ( m > 0L ){

   635                             low  = (b <  m );

   636                             high = (b+m > tens );

   637                         } else {

   638                             // hack -- m might overflow!

   639                             // in this case, it is certainly > b,

   640                             // which won't

   641                             // and b+m > tens, too, since that has overflowed

   642                             // either!

   643                             low = true;

   644                             high = true;

   645                         }

   646                         digits[ndigit++] = (char)('0' + q);

   647                     }

   648                     lowDigitDifference = (b<<1) - tens;

   649                     exactDecimalConversion  = (b == 0);

   650                 } else {

   651                     // still good! they're all longs!

   652                     long b = (fractBits * FDBigInteger.LONG_5_POW[B5] ) << B2;

   653                     long s = FDBigInteger.LONG_5_POW[S5] << S2;

   654                     long m = FDBigInteger.LONG_5_POW[M5] << M2;

   655                     long tens = s * 10L;

   656                     //

   657                     // Unroll the first iteration. If our decExp estimate

   658                     // was too high, our first quotient will be zero. In this

   659                     // case, we discard it and decrement decExp.

   660                     //

   661                     ndigit = 0;

   662                     q = (int) ( b / s );

   663                     b = 10L * ( b % s );

   664                     m *= 10L;

   665                     low  = (b <  m );

   666                     high = (b+m > tens );

   667                     assert q < 10 : q; // excessively large digit

   668                     if ( (q == 0) && ! high ){

   669                         // oops. Usually ignore leading zero.

   670                         decExp--;

   671                     } else {

   672                         digits[ndigit++] = (char)('0' + q);

   673                     }

   674                     //

   675                     // HACK! Java spec sez that we always have at least

   676                     // one digit after the . in either F- or E-form output.

   677                     // Thus we will need more than one digit if we're using

   678                     // E-form

   679                     //

   680                     if ( !isCompatibleFormat || decExp < -3 || decExp >= 8 ){

   681                         high = low = false;

   682                     }

   683                     while( ! low && ! high ){

   684                         q = (int) ( b / s );

   685                         b = 10 * ( b % s );

   686                         m *= 10;

   687                         assert q < 10 : q;  // excessively large digit

   688                         if ( m > 0L ){

   689                             low  = (b <  m );

   690                             high = (b+m > tens );

   691                         } else {

   692                             // hack -- m might overflow!

   693                             // in this case, it is certainly > b,

   694                             // which won't

   695                             // and b+m > tens, too, since that has overflowed

   696                             // either!

   697                             low = true;

   698                             high = true;

   699                         }

   700                         digits[ndigit++] = (char)('0' + q);

   701                     }

   702                     lowDigitDifference = (b<<1) - tens;

   703                     exactDecimalConversion  = (b == 0);

   704                 }

   705             } else {

   706                 //

   707                 // We really must do FDBigInteger arithmetic.

   708                 // Fist, construct our FDBigInteger initial values.

   709                 //

   710                 FDBigInteger Sval = FDBigInteger.valueOfPow52(S5, S2);

   711                 int shiftBias = Sval.getNormalizationBias();

   712                 Sval = Sval.leftShift(shiftBias); // normalize so that division works better

   713 

   714                 FDBigInteger Bval = FDBigInteger.valueOfMulPow52(fractBits, B5, B2 + shiftBias);

   715                 FDBigInteger Mval = FDBigInteger.valueOfPow52(M5 + 1, M2 + shiftBias + 1);

   716 

   717                 FDBigInteger tenSval = FDBigInteger.valueOfPow52(S5 + 1, S2 + shiftBias + 1); //Sval.mult( 10 );

   718                 //

   719                 // Unroll the first iteration. If our decExp estimate

   720                 // was too high, our first quotient will be zero. In this

   721                 // case, we discard it and decrement decExp.

   722                 //

   723                 ndigit = 0;

   724                 q = Bval.quoRemIteration( Sval );

   725                 low  = (Bval.cmp( Mval ) < 0);

   726                 high = tenSval.addAndCmp(Bval,Mval)<=0;

   727 

   728                 assert q < 10 : q; // excessively large digit

   729                 if ( (q == 0) && ! high ){

   730                     // oops. Usually ignore leading zero.

   731                     decExp--;

   732                 } else {

   733                     digits[ndigit++] = (char)('0' + q);

   734                 }

   735                 //

   736                 // HACK! Java spec sez that we always have at least

   737                 // one digit after the . in either F- or E-form output.

   738                 // Thus we will need more than one digit if we're using

   739                 // E-form

   740                 //

   741                 if (!isCompatibleFormat || decExp < -3 || decExp >= 8 ){

   742                     high = low = false;

   743                 }

   744                 while( ! low && ! high ){

   745                     q = Bval.quoRemIteration( Sval );

   746                     assert q < 10 : q;  // excessively large digit

   747                     Mval = Mval.multBy10(); //Mval = Mval.mult( 10 );

   748                     low  = (Bval.cmp( Mval ) < 0);

   749                     high = tenSval.addAndCmp(Bval,Mval)<=0;

   750                     digits[ndigit++] = (char)('0' + q);

   751                 }

   752                 if ( high && low ){

   753                     Bval = Bval.leftShift(1);

   754                     lowDigitDifference = Bval.cmp(tenSval);

   755                 } else {

   756                     lowDigitDifference = 0L; // this here only for flow analysis!

   757                 }

   758                 exactDecimalConversion  = (Bval.cmp( FDBigInteger.ZERO ) == 0);

   759             }

   760             this.decExponent = decExp+1;

   761             this.firstDigitIndex = 0;

   762             this.nDigits = ndigit;

   763             //

   764             // Last digit gets rounded based on stopping condition.

   765             //

   766             if ( high ){

   767                 if ( low ){

   768                     if ( lowDigitDifference == 0L ){

   769                         // it's a tie!

   770                         // choose based on which digits we like.

   771                         if ( (digits[firstDigitIndex+nDigits-1]&1) != 0 ) {

   772                             roundup();

   773                         }

   774                     } else if ( lowDigitDifference > 0 ){

   775                         roundup();

   776                     }

   777                 } else {

   778                     roundup();

   779                 }

   780             }

   781         }

   782 

   783         // add one to the least significant digit.

   784         // in the unlikely event there is a carry out, deal with it.

   785         // assert that this will only happen where there

   786         // is only one digit, e.g. (float)1e-44 seems to do it.

   787         //

   788         private void roundup() {

   789             int i = (firstDigitIndex + nDigits - 1);

   790             int q = digits[i];

   791             if (q == '9') {

   792                 while (q == '9' && i > firstDigitIndex) {

   793                     digits[i] = '0';

   794                     q = digits[--i];

   795                 }

   796                 if (q == '9') {

   797                     // carryout! High-order 1, rest 0s, larger exp.

   798                     decExponent += 1;

   799                     digits[firstDigitIndex] = '1';

   800                     return;

   801                 }

   802                 // else fall through.

   803             }

   804             digits[i] = (char) (q + 1);

   805             decimalDigitsRoundedUp = true;

   806         }

   807 

   808         /**

   809          * Estimate decimal exponent. (If it is small-ish,

   810          * we could double-check.)

   811          *

   812          * First, scale the mantissa bits such that 1 <= d2 < 2.

   813          * We are then going to estimate

   814          *          log10(d2) ~=~  (d2-1.5)/1.5 + log(1.5)

   815          * and so we can estimate

   816          *      log10(d) ~=~ log10(d2) + binExp * log10(2)

   817          * take the floor and call it decExp.

   818          */

   819         static int estimateDecExp(long fractBits, int binExp) {

   820             double d2 = Double.longBitsToDouble( EXP_ONE | ( fractBits & DoubleConsts.SIGNIF_BIT_MASK ) );

   821             double d = (d2-1.5D)*0.289529654D + 0.176091259 + (double)binExp * 0.301029995663981;

   822             long dBits = Double.doubleToRawLongBits(d);  //can't be NaN here so use raw

   823             int exponent = (int)((dBits & DoubleConsts.EXP_BIT_MASK) >> EXP_SHIFT) - DoubleConsts.EXP_BIAS;

   824             boolean isNegative = (dBits & DoubleConsts.SIGN_BIT_MASK) != 0; // discover sign

   825             if(exponent>=0 && exponent<52) { // hot path

   826                 long mask   = DoubleConsts.SIGNIF_BIT_MASK >> exponent;

   827                 int r = (int)(( (dBits&DoubleConsts.SIGNIF_BIT_MASK) | FRACT_HOB )>>(EXP_SHIFT-exponent));

   828                 return isNegative ? (((mask & dBits) == 0L ) ? -r : -r-1 ) : r;

   829             } else if (exponent < 0) {

   830                 return (((dBits&~DoubleConsts.SIGN_BIT_MASK) == 0) ? 0 :

   831                         ( (isNegative) ? -1 : 0) );

   832             } else { //if (exponent >= 52)

   833                 return (int)d;

   834             }

   835         }

   836 

   837         private static int insignificantDigits(int insignificant) {

   838             int i;

   839             for ( i = 0; insignificant >= 10L; i++ ) {

   840                 insignificant /= 10L;

   841             }

   842             return i;

   843         }

   844 

   845         /**

   846          * Calculates

   847          * <pre>

   848          * insignificantDigitsForPow2(v) == insignificantDigits(1L<<v)

   849          * </pre>

   850          */

   851         private static int insignificantDigitsForPow2(int p2) {

   852             if(p2>1 && p2 < insignificantDigitsNumber.length) {

   853                 return insignificantDigitsNumber[p2];

   854             }

   855             return 0;

   856         }

   857 

   858         /**

   859          *  If insignificant==(1L << ixd)

   860          *  i = insignificantDigitsNumber[idx] is the same as:

   861          *  int i;

   862          *  for ( i = 0; insignificant >= 10L; i++ )

   863          *         insignificant /= 10L;

   864          */

   865         private static int[] insignificantDigitsNumber = {

   866             0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3,

   867             4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7,

   868             8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11,

   869             12, 12, 12, 12, 13, 13, 13, 14, 14, 14,

   870             15, 15, 15, 15, 16, 16, 16, 17, 17, 17,

   871             18, 18, 18, 19

   872         };

   873 

   874         // approximately ceil( log2( long5pow[i] ) )

   875         private static final int[] N_5_BITS = {

   876                 0,

   877                 3,

   878                 5,

   879                 7,

   880                 10,

   881                 12,

   882                 14,

   883                 17,

   884                 19,

   885                 21,

   886                 24,

   887                 26,

   888                 28,

   889                 31,

   890                 33,

   891                 35,

   892                 38,

   893                 40,

   894                 42,

   895                 45,

   896                 47,

   897                 49,

   898                 52,

   899                 54,

   900                 56,

   901                 59,

   902                 61,

   903         };

   904 

   905         private int getChars(char[] result) {

   906             assert nDigits <= 19 : nDigits; // generous bound on size of nDigits

   907             int i = 0;

   908             if (isNegative) {

   909                 result[0] = '-';

   910                 i = 1;

   911             }

   912             if (decExponent > 0 && decExponent < 8) {

   913                 // print digits.digits.

   914                 int charLength = Math.min(nDigits, decExponent);

   915                 System.arraycopy(digits, firstDigitIndex, result, i, charLength);

   916                 i += charLength;

   917                 if (charLength < decExponent) {

   918                     charLength = decExponent - charLength;

   919                     Arrays.fill(result,i,i+charLength,'0');

   920                     i += charLength;

   921                     result[i++] = '.';

   922                     result[i++] = '0';

   923                 } else {

   924                     result[i++] = '.';

   925                     if (charLength < nDigits) {

   926                         int t = nDigits - charLength;

   927                         System.arraycopy(digits, firstDigitIndex+charLength, result, i, t);

   928                         i += t;

   929                     } else {

   930                         result[i++] = '0';

   931                     }

   932                 }

   933             } else if (decExponent <= 0 && decExponent > -3) {

   934                 result[i++] = '0';

   935                 result[i++] = '.';

   936                 if (decExponent != 0) {

   937                     Arrays.fill(result, i, i-decExponent, '0');

   938                     i -= decExponent;

   939                 }

   940                 System.arraycopy(digits, firstDigitIndex, result, i, nDigits);

   941                 i += nDigits;

   942             } else {

   943                 result[i++] = digits[firstDigitIndex];

   944                 result[i++] = '.';

   945                 if (nDigits > 1) {

   946                     System.arraycopy(digits, firstDigitIndex+1, result, i, nDigits - 1);

   947                     i += nDigits - 1;

   948                 } else {

   949                     result[i++] = '0';

   950                 }

   951                 result[i++] = 'E';

   952                 int e;

   953                 if (decExponent <= 0) {

   954                     result[i++] = '-';

   955                     e = -decExponent + 1;

   956                 } else {

   957                     e = decExponent - 1;

   958                 }

   959                 // decExponent has 1, 2, or 3, digits

   960                 if (e <= 9) {

   961                     result[i++] = (char) (e + '0');

   962                 } else if (e <= 99) {

   963                     result[i++] = (char) (e / 10 + '0');

   964                     result[i++] = (char) (e % 10 + '0');

   965                 } else {

   966                     result[i++] = (char) (e / 100 + '0');

   967                     e %= 100;

   968                     result[i++] = (char) (e / 10 + '0');

   969                     result[i++] = (char) (e % 10 + '0');

   970                 }

   971             }

   972             return i;

   973         }

   974 

   975     }

   976 

   977     private static final ThreadLocal<BinaryToASCIIBuffer> threadLocalBinaryToASCIIBuffer =

   978             new ThreadLocal<BinaryToASCIIBuffer>() {

   979                 @Override

   980                 protected BinaryToASCIIBuffer initialValue() {

   981                     return new BinaryToASCIIBuffer();

   982                 }

   983             };

   984 

   985     private static BinaryToASCIIBuffer getBinaryToASCIIBuffer() {

   986         return threadLocalBinaryToASCIIBuffer.get();

   987     }

   988 

   989     /**

   990      * A converter which can process an ASCII <code>String</code> representation

   991      * of a single or double precision floating point value into a

   992      * <code>float</code> or a <code>double</code>.

   993      */

   994     interface ASCIIToBinaryConverter {

   995 

   996         double doubleValue();

   997 

   998         float floatValue();

   999 

  1000     }

  1001 

  1002     /**

  1003      * A <code>ASCIIToBinaryConverter</code> container for a <code>double</code>.

  1004      */

  1005     static class PreparedASCIIToBinaryBuffer implements ASCIIToBinaryConverter {

  1006         private final double doubleVal;

  1007         private final float floatVal;

  1008 

  1009         public PreparedASCIIToBinaryBuffer(double doubleVal, float floatVal) {

  1010             this.doubleVal = doubleVal;

  1011             this.floatVal = floatVal;

  1012         }

  1013 

  1014         @Override

  1015         public double doubleValue() {

  1016             return doubleVal;

  1017         }

  1018 

  1019         @Override

  1020         public float floatValue() {

  1021             return floatVal;

  1022         }

  1023     }

  1024 

  1025     static final ASCIIToBinaryConverter A2BC_POSITIVE_INFINITY = new PreparedASCIIToBinaryBuffer(Double.POSITIVE_INFINITY, Float.POSITIVE_INFINITY);

  1026     static final ASCIIToBinaryConverter A2BC_NEGATIVE_INFINITY = new PreparedASCIIToBinaryBuffer(Double.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY);

  1027     static final ASCIIToBinaryConverter A2BC_NOT_A_NUMBER  = new PreparedASCIIToBinaryBuffer(Double.NaN, Float.NaN);

  1028     static final ASCIIToBinaryConverter A2BC_POSITIVE_ZERO = new PreparedASCIIToBinaryBuffer(0.0d, 0.0f);

  1029     static final ASCIIToBinaryConverter A2BC_NEGATIVE_ZERO = new PreparedASCIIToBinaryBuffer(-0.0d, -0.0f);

  1030 

  1031     /**

  1032      * A buffered implementation of <code>ASCIIToBinaryConverter</code>.

  1033      */

  1034     static class ASCIIToBinaryBuffer implements ASCIIToBinaryConverter {

  1035         boolean     isNegative;

  1036         int         decExponent;

  1037         char        digits[];

  1038         int         nDigits;

  1039 

  1040         ASCIIToBinaryBuffer( boolean negSign, int decExponent, char[] digits, int n)

  1041         {

  1042             this.isNegative = negSign;

  1043             this.decExponent = decExponent;

  1044             this.digits = digits;

  1045             this.nDigits = n;

  1046         }

  1047 

  1048         /**

  1049          * Takes a FloatingDecimal, which we presumably just scanned in,

  1050          * and finds out what its value is, as a double.

  1051          *

  1052          * AS A SIDE EFFECT, SET roundDir TO INDICATE PREFERRED

  1053          * ROUNDING DIRECTION in case the result is really destined

  1054          * for a single-precision float.

  1055          */

  1056         @Override

  1057         public double doubleValue() {

  1058             int kDigits = Math.min(nDigits, MAX_DECIMAL_DIGITS + 1);

  1059             //

  1060             // convert the lead kDigits to a long integer.

  1061             //

  1062             // (special performance hack: start to do it using int)

  1063             int iValue = (int) digits[0] - (int) '0';

  1064             int iDigits = Math.min(kDigits, INT_DECIMAL_DIGITS);

  1065             for (int i = 1; i < iDigits; i++) {

  1066                 iValue = iValue * 10 + (int) digits[i] - (int) '0';

  1067             }

  1068             long lValue = (long) iValue;

  1069             for (int i = iDigits; i < kDigits; i++) {

  1070                 lValue = lValue * 10L + (long) ((int) digits[i] - (int) '0');

  1071             }

  1072             double dValue = (double) lValue;

  1073             int exp = decExponent - kDigits;

  1074             //

  1075             // lValue now contains a long integer with the value of

  1076             // the first kDigits digits of the number.

  1077             // dValue contains the (double) of the same.

  1078             //

  1079 

  1080             if (nDigits <= MAX_DECIMAL_DIGITS) {

  1081                 //

  1082                 // possibly an easy case.

  1083                 // We know that the digits can be represented

  1084                 // exactly. And if the exponent isn't too outrageous,

  1085                 // the whole thing can be done with one operation,

  1086                 // thus one rounding error.

  1087                 // Note that all our constructors trim all leading and

  1088                 // trailing zeros, so simple values (including zero)

  1089                 // will always end up here

  1090                 //

  1091                 if (exp == 0 || dValue == 0.0) {

  1092                     return (isNegative) ? -dValue : dValue; // small floating integer

  1093                 }

  1094                 else if (exp >= 0) {

  1095                     if (exp <= MAX_SMALL_TEN) {

  1096                         //

  1097                         // Can get the answer with one operation,

  1098                         // thus one roundoff.

  1099                         //

  1100                         double rValue = dValue * SMALL_10_POW[exp];

  1101                         return (isNegative) ? -rValue : rValue;

  1102                     }

  1103                     int slop = MAX_DECIMAL_DIGITS - kDigits;

  1104                     if (exp <= MAX_SMALL_TEN + slop) {

  1105                         //

  1106                         // We can multiply dValue by 10^(slop)

  1107                         // and it is still "small" and exact.

  1108                         // Then we can multiply by 10^(exp-slop)

  1109                         // with one rounding.

  1110                         //

  1111                         dValue *= SMALL_10_POW[slop];

  1112                         double rValue = dValue * SMALL_10_POW[exp - slop];

  1113                         return (isNegative) ? -rValue : rValue;

  1114                     }

  1115                     //

  1116                     // Else we have a hard case with a positive exp.

  1117                     //

  1118                 } else {

  1119                     if (exp >= -MAX_SMALL_TEN) {

  1120                         //

  1121                         // Can get the answer in one division.

  1122                         //

  1123                         double rValue = dValue / SMALL_10_POW[-exp];

  1124                         return (isNegative) ? -rValue : rValue;

  1125                     }

  1126                     //

  1127                     // Else we have a hard case with a negative exp.

  1128                     //

  1129                 }

  1130             }

  1131 

  1132             //

  1133             // Harder cases:

  1134             // The sum of digits plus exponent is greater than