DToA.java
/* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
/**
* **************************************************************
*
* <p>The author of this software is David M. Gay.
*
* <p>Copyright (c) 1991, 2000, 2001 by Lucent Technologies.
*
* <p>Permission to use, copy, modify, and distribute this software for any purpose without fee is
* hereby granted, provided that this entire notice is included in all copies of any software which
* is or includes a copy or modification of this software and in all copies of the supporting
* documentation for such software.
*
* <p>THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED WARRANTY. IN
* PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY REPRESENTATION OR WARRANTY OF ANY KIND
* CONCERNING THE MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
*
* <p>*************************************************************
*/
package org.mozilla.javascript;
import java.math.BigInteger;
import java.util.Objects;
class DToA {
private static char BASEDIGIT(int digit) {
return (char) ((digit >= 10) ? 'a' - 10 + digit : '0' + digit);
}
private static final int Frac_mask = 0xfffff;
private static final int Exp_shift = 20;
private static final int Exp_msk1 = 0x100000;
private static final long Frac_maskL = 0xfffffffffffffL;
private static final int Exp_shiftL = 52;
private static final long Exp_msk1L = 0x10000000000000L;
private static final int Bias = 1023;
private static final int P = 53;
private static final int Exp_shift1 = 20;
private static final int Exp_mask = 0x7ff00000;
private static final int Exp_mask_shifted = 0x7ff;
private static final int Bndry_mask = 0xfffff;
private static final int Log2P = 1;
private static final int Sign_bit = 0x80000000;
private static final int Exp_11 = 0x3ff00000;
private static final int Ten_pmax = 22;
private static final int Quick_max = 14;
private static final int Bletch = 0x10;
private static final int Frac_mask1 = 0xfffff;
private static final int Int_max = 14;
private static final int n_bigtens = 5;
private static final double[] tens = {
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
1e20, 1e21, 1e22
};
private static final double[] bigtens = {1e16, 1e32, 1e64, 1e128, 1e256};
private static int lo0bits(int y) {
int k;
int x = y;
if ((x & 7) != 0) {
if ((x & 1) != 0) return 0;
if ((x & 2) != 0) {
return 1;
}
return 2;
}
k = 0;
if ((x & 0xffff) == 0) {
k = 16;
x >>>= 16;
}
if ((x & 0xff) == 0) {
k += 8;
x >>>= 8;
}
if ((x & 0xf) == 0) {
k += 4;
x >>>= 4;
}
if ((x & 0x3) == 0) {
k += 2;
x >>>= 2;
}
if ((x & 1) == 0) {
k++;
x >>>= 1;
if ((x & 1) == 0) return 32;
}
return k;
}
/* Return the number (0 through 32) of most significant zero bits in x. */
private static int hi0bits(int x) {
int k = 0;
if ((x & 0xffff0000) == 0) {
k = 16;
x <<= 16;
}
if ((x & 0xff000000) == 0) {
k += 8;
x <<= 8;
}
if ((x & 0xf0000000) == 0) {
k += 4;
x <<= 4;
}
if ((x & 0xc0000000) == 0) {
k += 2;
x <<= 2;
}
if ((x & 0x80000000) == 0) {
k++;
if ((x & 0x40000000) == 0) return 32;
}
return k;
}
private static void stuffBits(byte[] bits, int offset, int val) {
bits[offset] = (byte) (val >> 24);
bits[offset + 1] = (byte) (val >> 16);
bits[offset + 2] = (byte) (val >> 8);
bits[offset + 3] = (byte) val;
}
/* Convert d into the form b*2^e, where b is an odd integer. b is the returned
* Bigint and e is the returned binary exponent. Return the number of significant
* bits in b in bits. d must be finite and nonzero. */
private static BigInteger d2b(double d, int[] e, int[] bits) {
byte[] dbl_bits;
int i, k, y, z, de;
long dBits = Double.doubleToLongBits(d);
int d0 = (int) (dBits >>> 32);
int d1 = (int) dBits;
z = d0 & Frac_mask;
d0 &= 0x7fffffff; /* clear sign bit, which we ignore */
if ((de = (d0 >>> Exp_shift)) != 0) z |= Exp_msk1;
if ((y = d1) != 0) {
dbl_bits = new byte[8];
k = lo0bits(y);
y >>>= k;
if (k != 0) {
stuffBits(dbl_bits, 4, y | z << (32 - k));
z >>= k;
} else stuffBits(dbl_bits, 4, y);
stuffBits(dbl_bits, 0, z);
i = (z != 0) ? 2 : 1;
} else {
// JS_ASSERT(z);
dbl_bits = new byte[4];
k = lo0bits(z);
z >>>= k;
stuffBits(dbl_bits, 0, z);
k += 32;
i = 1;
}
if (de != 0) {
e[0] = de - Bias - (P - 1) + k;
bits[0] = P - k;
} else {
e[0] = de - Bias - (P - 1) + 1 + k;
bits[0] = 32 * i - hi0bits(z);
}
return new BigInteger(dbl_bits);
}
static String JS_dtobasestr(int base, double d) {
if (!(2 <= base && base <= 36)) throw new IllegalArgumentException("Bad base: " + base);
/* Check for Infinity and NaN */
if (Double.isNaN(d)) {
return "NaN";
} else if (Double.isInfinite(d)) {
return (d > 0.0) ? "Infinity" : "-Infinity";
} else if (d == 0) {
// ALERT: should it distinguish -0.0 from +0.0 ?
return "0";
}
boolean negative;
if (d >= 0.0) {
negative = false;
} else {
negative = true;
d = -d;
}
/* Get the integer part of d including '-' sign. */
String intDigits;
double dfloor = Math.floor(d);
long lfloor = (long) dfloor;
if (lfloor == dfloor) {
// int part fits long
intDigits = Long.toString(negative ? -lfloor : lfloor, base);
} else {
// BigInteger should be used
long floorBits = Double.doubleToLongBits(dfloor);
int exp = (int) (floorBits >> Exp_shiftL) & Exp_mask_shifted;
long mantissa;
if (exp == 0) {
mantissa = (floorBits & Frac_maskL) << 1;
} else {
mantissa = (floorBits & Frac_maskL) | Exp_msk1L;
}
if (negative) {
mantissa = -mantissa;
}
exp -= 1075;
BigInteger x = BigInteger.valueOf(mantissa);
if (exp > 0) {
x = x.shiftLeft(exp);
} else if (exp < 0) {
x = x.shiftRight(-exp);
}
intDigits = x.toString(base);
}
if (d == dfloor) {
// No fraction part
return intDigits;
}
/* We have a fraction. */
StringBuilder buffer; /* The output string */
int digit;
double df; /* The fractional part of d */
BigInteger b;
buffer = new StringBuilder();
buffer.append(intDigits).append('.');
df = d - dfloor;
long dBits = Double.doubleToLongBits(d);
int word0 = (int) (dBits >> 32);
int word1 = (int) dBits;
int[] e = new int[1];
int[] bbits = new int[1];
b = d2b(df, e, bbits);
// JS_ASSERT(e < 0);
/* At this point df = b * 2^e. e must be less than zero because 0 < df < 1. */
int s2 = -(word0 >>> Exp_shift1 & Exp_mask >> Exp_shift1);
if (s2 == 0) s2 = -1;
s2 += Bias + P;
/* 1/2^s2 = (nextDouble(d) - d)/2 */
// JS_ASSERT(-s2 < e);
BigInteger mlo = BigInteger.valueOf(1);
BigInteger mhi = mlo;
if ((word1 == 0)
&& ((word0 & Bndry_mask) == 0)
&& ((word0 & (Exp_mask & Exp_mask << 1)) != 0)) {
/* The special case. Here we want to be within a quarter of the last input
significant digit instead of one half of it when the output string's value is less than d. */
s2 += Log2P;
mhi = BigInteger.valueOf(1 << Log2P);
}
b = b.shiftLeft(e[0] + s2);
BigInteger s = BigInteger.valueOf(1);
s = s.shiftLeft(s2);
/* At this point we have the following:
* s = 2^s2;
* 1 > df = b/2^s2 > 0;
* (d - prevDouble(d))/2 = mlo/2^s2;
* (nextDouble(d) - d)/2 = mhi/2^s2. */
BigInteger bigBase = BigInteger.valueOf(base);
boolean done = false;
do {
b = b.multiply(bigBase);
BigInteger[] divResult = b.divideAndRemainder(s);
b = divResult[1];
digit = (char) divResult[0].intValue();
if (Objects.equals(mlo, mhi)) mlo = mhi = mlo.multiply(bigBase);
else {
mlo = mlo.multiply(bigBase);
mhi = mhi.multiply(bigBase);
}
/* Do we yet have the shortest string that will round to d? */
int j = b.compareTo(mlo);
/* j is b/2^s2 compared with mlo/2^s2. */
BigInteger delta = s.subtract(mhi);
int j1 = (delta.signum() <= 0) ? 1 : b.compareTo(delta);
/* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
if (j1 == 0 && ((word1 & 1) == 0)) {
if (j > 0) digit++;
done = true;
} else if (j < 0 || (j == 0 && ((word1 & 1) == 0))) {
if (j1 > 0) {
/* Either dig or dig+1 would work here as the least significant digit.
Use whichever would produce an output value closer to d. */
b = b.shiftLeft(1);
j1 = b.compareTo(s);
if (j1
> 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
* such as 3.5 in base 3. */
digit++;
}
done = true;
} else if (j1 > 0) {
digit++;
done = true;
}
// JS_ASSERT(digit < (uint32)base);
buffer.append(BASEDIGIT(digit));
} while (!done);
return buffer.toString();
}
}