/*

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

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

 *

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

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

 * published by the Free Software Foundation.  Oracle designates this

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

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

 *

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

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

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

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

 * accompanied this code).

 *

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

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

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

 *

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

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

 * questions.

 */

package sun.misc;

import sun.misc.DoubleConsts;

import sun.misc.FloatConsts;

import java.util.regex.*;

public class FloatingDecimal{

    boolean     isExceptional;

    boolean     isNegative;

    int         decExponent;

    char        digits[];

    int         nDigits;

    int         bigIntExp;

    int         bigIntNBits;

    boolean     mustSetRoundDir = false;

    boolean     fromHex = false;

    int         roundDir = 0; // set by doubleValue

    /*

     * The fields below provides additional information about the result of

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

     * methods. They are changed if needed by those two methods.

     */

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

    boolean     exactDecimalConversion = false;

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

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

    boolean     decimalDigitsRoundedUp = false;

    private     FloatingDecimal( boolean negSign, int decExponent, char []digits, int n,  boolean e )

    {

        isNegative = negSign;

        isExceptional = e;

        this.decExponent = decExponent;

        this.digits = digits;

        this.nDigits = n;

    }

    /*

     * Constants of the implementation

     * Most are IEEE-754 related.

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

     */

    static final long   signMask = 0x8000000000000000L;

    static final long   expMask  = 0x7ff0000000000000L;

    static final long   fractMask= ~(signMask|expMask);

    static final int    expShift = 52;

    static final int    expBias  = 1023;

    static final long   fractHOB = ( 1L<<expShift ); // assumed High-Order bit

    static final long   expOne   = ((long)expBias)<<expShift; // exponent of 1.0

    static final int    maxSmallBinExp = 62;

    static final int    minSmallBinExp = -( 63 / 3 );

    static final int    maxDecimalDigits = 15;

    static final int    maxDecimalExponent = 308;

    static final int    minDecimalExponent = -324;

    static final int    bigDecimalExponent = 324; // i.e. abs(minDecimalExponent)

    static final long   highbyte = 0xff00000000000000L;

    static final long   highbit  = 0x8000000000000000L;

    static final long   lowbytes = ~highbyte;

    static final int    singleSignMask =    0x80000000;

    static final int    singleExpMask  =    0x7f800000;

    static final int    singleFractMask =   ~(singleSignMask|singleExpMask);

    static final int    singleExpShift  =   23;

    static final int    singleFractHOB  =   1<<singleExpShift;

    static final int    singleExpBias   =   127;

    static final int    singleMaxDecimalDigits = 7;

    static final int    singleMaxDecimalExponent = 38;

    static final int    singleMinDecimalExponent = -45;

    static final int    intDecimalDigits = 9;

    /*

     * count number of bits from high-order 1 bit to low-order 1 bit,

     * inclusive.

     */

    private static int

    countBits( long v ){

        //

        // the strategy is to shift until we get a non-zero sign bit

        // then shift until we have no bits left, counting the difference.

        // we do byte shifting as a hack. Hope it helps.

        //

        if ( v == 0L ) return 0;

        while ( ( v & highbyte ) == 0L ){

            v <<= 8;

        }

        while ( v > 0L ) { // i.e. while ((v&highbit) == 0L )

            v <<= 1;

        }

        int n = 0;

        while (( v & lowbytes ) != 0L ){

            v <<= 8;

            n += 8;

        }

        while ( v != 0L ){

            v <<= 1;

            n += 1;

        }

        return n;

    }

    /*

     * Keep big powers of 5 handy for future reference.

     */

    private static FDBigInt b5p[];

    private static synchronized FDBigInt

    big5pow( int p ){

        assert p >= 0 : p; // negative power of 5

        if ( b5p == null ){

            b5p = new FDBigInt[ p+1 ];

        }else if (b5p.length <= p ){

            FDBigInt t[] = new FDBigInt[ p+1 ];

            System.arraycopy( b5p, 0, t, 0, b5p.length );

            b5p = t;

        }

        if ( b5p[p] != null )

            return b5p[p];

        else if ( p < small5pow.length )

            return b5p[p] = new FDBigInt( small5pow[p] );

        else if ( p < long5pow.length )

            return b5p[p] = new FDBigInt( long5pow[p] );

        else {

            // construct the value.

            // recursively.

            int q, r;

            // in order to compute 5^p,

            // compute its square root, 5^(p/2) and square.

            // or, let q = p / 2, r = p -q, then

            // 5^p = 5^(q+r) = 5^q * 5^r

            q = p >> 1;

            r = p - q;

            FDBigInt bigq =  b5p[q];

            if ( bigq == null )

                bigq = big5pow ( q );

            if ( r < small5pow.length ){

                return (b5p[p] = bigq.mult( small5pow[r] ) );

            }else{

                FDBigInt bigr = b5p[ r ];

                if ( bigr == null )

                    bigr = big5pow( r );

                return (b5p[p] = bigq.mult( bigr ) );

            }

        }

    }

    //

    // a common operation

    //

    private static FDBigInt

    multPow52( FDBigInt v, int p5, int p2 ){

        if ( p5 != 0 ){

            if ( p5 < small5pow.length ){

                v = v.mult( small5pow[p5] );

            } else {

                v = v.mult( big5pow( p5 ) );

            }

        }

        if ( p2 != 0 ){

            v.lshiftMe( p2 );

        }

        return v;

    }

    //

    // another common operation

    //

    private static FDBigInt

    constructPow52( int p5, int p2 ){

        FDBigInt v = new FDBigInt( big5pow( p5 ) );

        if ( p2 != 0 ){

            v.lshiftMe( p2 );

        }

        return v;

    }

    /*

     * Make a floating double into a FDBigInt.

     * This could also be structured as a FDBigInt

     * constructor, but we'd have to build a lot of knowledge

     * about floating-point representation into it, and we don't want to.

     *

     * AS A SIDE EFFECT, THIS METHOD WILL SET THE INSTANCE VARIABLES

     * bigIntExp and bigIntNBits

     *

     */

    private FDBigInt

    doubleToBigInt( double dval ){

        long lbits = Double.doubleToLongBits( dval ) & ~signMask;

        int binexp = (int)(lbits >>> expShift);

        lbits &= fractMask;

        if ( binexp > 0 ){

            lbits |= fractHOB;

        } else {

            assert lbits != 0L : lbits; // doubleToBigInt(0.0)

            binexp +=1;

            while ( (lbits & fractHOB ) == 0L){

                lbits <<= 1;

                binexp -= 1;

            }

        }

        binexp -= expBias;

        int nbits = countBits( lbits );

        /*

         * We now know where the high-order 1 bit is,

         * and we know how many there are.

         */

        int lowOrderZeros = expShift+1-nbits;

        lbits >>>= lowOrderZeros;

        bigIntExp = binexp+1-nbits;

        bigIntNBits = nbits;

        return new FDBigInt( lbits );

    }

    /*

     * Compute a number that is the ULP of the given value,

     * for purposes of addition/subtraction. Generally easy.

     * More difficult if subtracting and the argument

     * is a normalized a power of 2, as the ULP changes at these points.

     */

    private static double ulp( double dval, boolean subtracting ){

        long lbits = Double.doubleToLongBits( dval ) & ~signMask;

        int binexp = (int)(lbits >>> expShift);

        double ulpval;

        if ( subtracting && ( binexp >= expShift ) && ((lbits&fractMask) == 0L) ){

            // for subtraction from normalized, powers of 2,

            // use next-smaller exponent

            binexp -= 1;

        }

        if ( binexp > expShift ){

            ulpval = Double.longBitsToDouble( ((long)(binexp-expShift))<<expShift );

        } else if ( binexp == 0 ){

            ulpval = Double.MIN_VALUE;

        } else {

            ulpval = Double.longBitsToDouble( 1L<<(binexp-1) );

        }

        if ( subtracting ) ulpval = - ulpval;

        return ulpval;

    }

    /*

     * Round a double to a float.

     * In addition to the fraction bits of the double,

     * look at the class instance variable roundDir,

     * which should help us avoid double-rounding error.

     * roundDir was set in hardValueOf if the estimate was

     * close enough, but not exact. It tells us which direction

     * of rounding is preferred.

     */

    float

    stickyRound( double dval ){

        long lbits = Double.doubleToLongBits( dval );

        long binexp = lbits & expMask;

        if ( binexp == 0L || binexp == expMask ){

            // what we have here is special.

            // don't worry, the right thing will happen.

            return (float) dval;

        }

        lbits += (long)roundDir; // hack-o-matic.

        return (float)Double.longBitsToDouble( lbits );

    }

    /*

     * This is the easy subcase --

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

     * negSign and decExponent tell us what processing and scaling

     * has already been done. Exceptional cases have already been

     * stripped out.

     * In particular:

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

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

     *

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

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

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

     * changes, we should re-evaluate this strategy!

     */

    private void

    developLongDigits( int decExponent, long lvalue, long insignificant ){

        char digits[];

        int  ndigits;

        int  digitno;

        int  c;

        //

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

        // up to insignificant value.

        int i;

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

            insignificant /= 10L;

        if ( i != 0 ){

            long pow10 = long5pow[i] << i; // 10^i == 5^i * 2^i;

            long residue = lvalue % pow10;

            lvalue /= pow10;

            decExponent += i;

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

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

                lvalue++;

            }

        }

        if ( lvalue <= Integer.MAX_VALUE ){

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

            // even easier subcase!

            // can do int arithmetic rather than long!

            int  ivalue = (int)lvalue;

            ndigits = 10;

            digits = perThreadBuffer.get();

            digitno = ndigits-1;

            c = ivalue%10;

            ivalue /= 10;

            while ( c == 0 ){

                decExponent++;

                c = ivalue%10;

                ivalue /= 10;

            }

            while ( ivalue != 0){

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

                decExponent++;

                c = ivalue%10;

                ivalue /= 10;

            }

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

        } else {

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

            // but using long arithmetic.

            ndigits = 20;

            digits = perThreadBuffer.get();

            digitno = ndigits-1;

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

            lvalue /= 10L;

            while ( c == 0 ){

                decExponent++;

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

                lvalue /= 10L;

            }

            while ( lvalue != 0L ){

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

                decExponent++;

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

                lvalue /= 10;

            }

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

        }

        char result [];

        ndigits -= digitno;

        result = new char[ ndigits ];

        System.arraycopy( digits, digitno, result, 0, ndigits );

        this.digits = result;

        this.decExponent = decExponent+1;

        this.nDigits = ndigits;

    }

    //

    // add one to the least significant digit.

    // in the unlikely event there is a carry out,

    // deal with it.

    // assert that this will only happen where there

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

    //

    private void

    roundup(){

        int i;

        int q = digits[ i = (nDigits-1)];

        if ( q == '9' ){

            while ( q == '9' && i > 0 ){

                digits[i] = '0';

                q = digits[--i];

            }

            if ( q == '9' ){

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

                decExponent += 1;

                digits[0] = '1';

                return;

            }

            // else fall through.

        }

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

        decimalDigitsRoundedUp = true;

    }

    public boolean digitsRoundedUp() {

        return decimalDigitsRoundedUp;

    }

    /*

     * FIRST IMPORTANT CONSTRUCTOR: DOUBLE

     */

    public FloatingDecimal( double d )

    {

        long    dBits = Double.doubleToLongBits( d );

        long    fractBits;

        int     binExp;

        int     nSignificantBits;

        // discover and delete sign

        if ( (dBits&signMask) != 0 ){

            isNegative = true;

            dBits ^= signMask;

        } else {

            isNegative = false;

        }

        // Begin to unpack

        // Discover obvious special cases of NaN and Infinity.

        binExp = (int)( (dBits&expMask) >> expShift );

        fractBits = dBits&fractMask;

        if ( binExp == (int)(expMask>>expShift) ) {

            isExceptional = true;

            if ( fractBits == 0L ){

                digits =  infinity;

            } else {

                digits = notANumber;

                isNegative = false; // NaN has no sign!

            }

            nDigits = digits.length;

            return;

        }

        isExceptional = false;

        // Finish unpacking

        // Normalize denormalized numbers.

        // Insert assumed high-order bit for normalized numbers.

        // Subtract exponent bias.

        if ( binExp == 0 ){

            if ( fractBits == 0L ){

                // not a denorm, just a 0!

                decExponent = 0;

                digits = zero;

                nDigits = 1;

                return;

            }

            while ( (fractBits&fractHOB) == 0L ){

                fractBits <<= 1;

                binExp -= 1;

            }

            nSignificantBits = expShift + binExp +1; // recall binExp is  - shift count.

            binExp += 1;

        } else {

            fractBits |= fractHOB;

            nSignificantBits = expShift+1;

        }

        binExp -= expBias;

        // call the routine that actually does all the hard work.

        dtoa( binExp, fractBits, nSignificantBits );

    }

    /*

     * SECOND IMPORTANT CONSTRUCTOR: SINGLE

     */

    public FloatingDecimal( float f )

    {

        int     fBits = Float.floatToIntBits( f );

        int     fractBits;

        int     binExp;

        int     nSignificantBits;

        // discover and delete sign

        if ( (fBits&singleSignMask) != 0 ){

            isNegative = true;

            fBits ^= singleSignMask;

        } else {

            isNegative = false;

        }

        // Begin to unpack

        // Discover obvious special cases of NaN and Infinity.

        binExp = (fBits&singleExpMask) >> singleExpShift;

        fractBits = fBits&singleFractMask;

        if ( binExp == (singleExpMask>>singleExpShift) ) {

            isExceptional = true;

            if ( fractBits == 0L ){

                digits =  infinity;

            } else {

                digits = notANumber;

                isNegative = false; // NaN has no sign!

            }

            nDigits = digits.length;

            return;

        }

        isExceptional = false;

        // Finish unpacking

        // Normalize denormalized numbers.

        // Insert assumed high-order bit for normalized numbers.

        // Subtract exponent bias.

        if ( binExp == 0 ){

            if ( fractBits == 0 ){

                // not a denorm, just a 0!

                decExponent = 0;

                digits = zero;

                nDigits = 1;

                return;

            }

            while ( (fractBits&singleFractHOB) == 0 ){

                fractBits <<= 1;