Faster version of LongLib Review at http://gwt-code-reviews.appspot.com/572801 Review by: jat@google.com git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@8235 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/GenerateJavaScriptLiterals.java b/dev/core/src/com/google/gwt/dev/jjs/impl/GenerateJavaScriptLiterals.java index 0e4a148..f848152 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/GenerateJavaScriptLiterals.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/GenerateJavaScriptLiterals.java
@@ -15,6 +15,7 @@ */ package com.google.gwt.dev.jjs.impl; +import com.google.gwt.dev.jjs.SourceInfo; import com.google.gwt.dev.jjs.ast.Context; import com.google.gwt.dev.jjs.ast.JBooleanLiteral; import com.google.gwt.dev.jjs.ast.JCharLiteral; @@ -25,8 +26,11 @@ import com.google.gwt.dev.jjs.ast.JNullLiteral; import com.google.gwt.dev.jjs.ast.JStringLiteral; import com.google.gwt.dev.jjs.ast.JVisitor; -import com.google.gwt.dev.js.ast.JsArrayLiteral; +import com.google.gwt.dev.js.ast.JsExpression; +import com.google.gwt.dev.js.ast.JsNameRef; +import com.google.gwt.dev.js.ast.JsObjectLiteral; import com.google.gwt.dev.js.ast.JsProgram; +import com.google.gwt.dev.js.ast.JsPropertyInitializer; import com.google.gwt.dev.js.ast.JsVisitable; import com.google.gwt.lang.LongLib; @@ -40,10 +44,6 @@ */ public class GenerateJavaScriptLiterals extends JVisitor { - static { - LongLib.RUN_IN_JVM = true; - } - private final JsProgram program; private final Stack<JsVisitable<?>> nodeStack = new Stack<JsVisitable<?>>(); @@ -78,13 +78,20 @@ @Override public void endVisit(JLongLiteral x, Context ctx) { - JsArrayLiteral arrayLit = new JsArrayLiteral(x.getSourceInfo()); - double[] doubleArray = LongLib.typeChange(x.getValue()); - arrayLit.getExpressions().add( - program.getNumberLiteral(x.getSourceInfo(), doubleArray[0])); - arrayLit.getExpressions().add( - program.getNumberLiteral(x.getSourceInfo(), doubleArray[1])); - push(arrayLit); + SourceInfo sourceInfo = x.getSourceInfo(); + int[] intArray = LongLib.getAsIntArray(x.getValue()); + JsObjectLiteral objectLit = new JsObjectLiteral(sourceInfo); + List<JsPropertyInitializer> inits = objectLit.getPropertyInitializers(); + JsExpression label0 = new JsNameRef(sourceInfo, "l"); + JsExpression label1 = new JsNameRef(sourceInfo, "m"); + JsExpression label2 = new JsNameRef(sourceInfo, "h"); + JsExpression value0 = program.getNumberLiteral(sourceInfo, intArray[0]); + JsExpression value1 = program.getNumberLiteral(sourceInfo, intArray[1]); + JsExpression value2 = program.getNumberLiteral(sourceInfo, intArray[2]); + inits.add(new JsPropertyInitializer(sourceInfo, label0, value0)); + inits.add(new JsPropertyInitializer(sourceInfo, label1, value1)); + inits.add(new JsPropertyInitializer(sourceInfo, label2, value2)); + push(objectLit); } @Override
diff --git a/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java b/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java index 59a624f..1d30097 100644 --- a/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java +++ b/dev/core/src/com/google/gwt/dev/jjs/impl/SameParameterValueOptimizer.java
@@ -44,6 +44,8 @@ * Detects when same literal is passed as parameter value, and uses literal * instead of parameter. The unused parameter will be removed by other analyses. */ +// TODO: this optimization can mistakenly act on methods such as LongLib.fromInt +// since only one call is seen in LongLib itself. public class SameParameterValueOptimizer { /** * Fill parameterValues map.
diff --git a/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Array.java b/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Array.java index 4e907dc..02ddedd 100644 --- a/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Array.java +++ b/dev/core/super/com/google/gwt/dev/jjs/intrinsic/com/google/gwt/lang/Array.java
@@ -209,7 +209,8 @@ /** * Creates a primitive JSON array of a given seedType. * - * @param seedType the primitive type of the array; 0: null; 1: zero; 2: false + * @param seedType the primitive type of the array; 0: null; 1: zero; + * 2: false; 3: (long) 0 * @param length the requested length * @see #NULL_SEED_TYPE * @see #ZERO_SEED_TYPE @@ -218,8 +219,15 @@ */ private static native Array createFromSeed(int seedType, int length) /*-{ var array = new Array(length); - if (seedType > 0) { - var value = [null, 0, false, [0, 0]][seedType]; + if (seedType == 3) { + // Fill array with the type used by LongLib + for (var i = 0; i < length; ++i) { + var value = new Object(); + value.l = value.m = value.h = 0; + array[i] = value; + } + } else if (seedType > 0) { + var value = [null, 0, false][seedType]; for (var i = 0; i < length; ++i) { array[i] = value; }
diff --git a/dev/core/super/com/google/gwt/lang/LongLib.java b/dev/core/super/com/google/gwt/lang/LongLib.java index 9226113..1afcfa8 100644 --- a/dev/core/super/com/google/gwt/lang/LongLib.java +++ b/dev/core/super/com/google/gwt/lang/LongLib.java
@@ -15,687 +15,439 @@ */ package com.google.gwt.lang; -import static com.google.gwt.lang.LongLib.Const.LN_2; -import static com.google.gwt.lang.LongLib.Const.MAX_VALUE; -import static com.google.gwt.lang.LongLib.Const.MIN_VALUE; -import static com.google.gwt.lang.LongLib.Const.NEG_ONE; -import static com.google.gwt.lang.LongLib.Const.ONE; -import static com.google.gwt.lang.LongLib.Const.TWO; -import static com.google.gwt.lang.LongLib.Const.TWO_PWR_24; -import static com.google.gwt.lang.LongLib.Const.ZERO; - -import com.google.gwt.core.client.UnsafeNativeLong; - /** * Implements a Java <code>long</code> in a way that can be translated to * JavaScript. */ -public class LongLib { - /* - * Implementation: An array of two doubles, low and high, such that high+low - * is mathematically equivalent to the original integer. Since a JavaScript - * Number does not hold enough bits to precisely calculate high+low, all - * operations must be implemented carefully. "low" is always between 0 and - * 2^32-1 inclusive. "high" is always between -2^63 and 2^63-2^32 inclusive - * and is a multiple of 2^32. The sign of the number is determined entirely by - * "high". Since low is always positive, small negative numbers are encoded - * with high=-2^32. For example, -1 is encoded as { high=-2^32, low=2^32-1 }. - * - * Note that this class must be careful using type "long". Being the - * implementation of the long type for web mode, any place it uses a long is - * not usable in web mode. There are currently two such methods: - * {@link #toLong(double[])} and {@link #make(long)}. - * - * The GWT RPC serialization code is dependent on the internal format of the - * long type; any changes made to this class should be reflected in the - * implementations of SerializationStreamReader and Writer. - */ - - /** - * Use nested class to avoid clinit on outer. - */ - static class CachedInts { - // Between -128 and 127. - static double[][] boxedValues = new double[256][]; - } +public class LongLib extends LongLibBase { static class Const { - static final double LN_2 = Math.log(2); - static final double[] MAX_VALUE = typeChange(Long.MAX_VALUE); - static final double[] MIN_VALUE = typeChange(Long.MIN_VALUE); - static final double[] NEG_ONE = fromInt(-1); - static final double[] ONE = fromInt(1); - static final double[] TWO = fromInt(2); + static final LongEmul MAX_VALUE = create(MASK, MASK, MASK_2 >> 1); + static final LongEmul MIN_VALUE = create(0, 0, SIGN_BIT_VALUE); + static final LongEmul ONE = fromInt(1); + static final LongEmul TWO = fromInt(2); + static final LongEmul ZERO = fromInt(0); + } + + private static LongEmul[] boxedValues; + + public static LongEmul add(LongEmul a, LongEmul b) { + int sum0 = getL(a) + getL(b); + int sum1 = getM(a) + getM(b) + (sum0 >> BITS); + int sum2 = getH(a) + getH(b) + (sum1 >> BITS); - /** - * Half of the number of bits we expect to be precise. - * - * @see LongLib#PRECISION_BITS - */ - static final double[] TWO_PWR_24 = typeChange(0x1000000L); + return create(sum0 & MASK, sum1 & MASK, sum2 & MASK_2); + } - static final double[] ZERO = fromInt(0); + public static LongEmul and(LongEmul a, LongEmul b) { + return create(getL(a) & getL(b), getM(a) & getM(b), getH(a) & getH(b)); } /** - * Set this to false before calling any methods when using this class outside - * of GWT! - */ - public static boolean RUN_IN_JVM = false; - - /** - * Number of bits we expect to be accurate for a double representing a large - * integer. - */ - private static final int PRECISION_BITS = 48; - - /** - * Index of the high bits in a 2-double array. - */ - private static final int HIGH = 1; - private static final double HIGH_MAX = 9223372032559808512d; - private static final double HIGH_MIN = -9223372036854775808d; - - /** - * Index of the low bits in a 2-double array. - */ - private static final int LOW = 0; - private static final double LOW_MAX = 4294967295d; - private static final double LOW_MIN = 0; - - private static final double TWO_PWR_15_DBL = 0x8000; - private static final double TWO_PWR_16_DBL = 0x10000; - private static final double TWO_PWR_31_DBL = TWO_PWR_16_DBL * TWO_PWR_15_DBL; - private static final double TWO_PWR_32_DBL = TWO_PWR_16_DBL * TWO_PWR_16_DBL; - private static final double TWO_PWR_48_DBL = TWO_PWR_32_DBL * TWO_PWR_16_DBL; - private static final double TWO_PWR_63_DBL = TWO_PWR_32_DBL * TWO_PWR_31_DBL; - private static final double TWO_PWR_64_DBL = TWO_PWR_32_DBL * TWO_PWR_32_DBL; - - public static double[] add(double[] a, double[] b) { - double newHigh = a[HIGH] + b[HIGH]; - double newLow = a[LOW] + b[LOW]; - return create(newLow, newHigh); - } - - public static double[] and(double[] a, double[] b) { - return makeFromBits(highBits(a) & highBits(b), lowBits(a) & lowBits(b)); - } - - /** - * Compare the receiver to the argument. + * Compare the receiver a to the argument b. * - * @return 0 if they are the same, 1 if the receiver is greater, -1 if the - * argument is greater. + * @return 0 if they are the same, a positive value if the receiver is + * greater, or a negative value if the argument is greater. */ - public static int compare(double[] a, double[] b) { - if (eq(a, b)) { - return 0; + public static int compare(LongEmul a, LongEmul b) { + int signA = sign(a); + int signB = sign(b); + if (signA != signB) { + return signB - signA; } - boolean nega = isNegative(a); - boolean negb = isNegative(b); - if (nega && !negb) { - return -1; - } - if (!nega && negb) { - return 1; + int a2 = getH(a); + int b2 = getH(b); + if (a2 != b2) { + return a2 - b2; } - // at this point, the signs are the same, so subtraction will not overflow - assert (nega == negb); - if (isNegative(sub(a, b))) { - return -1; - } else { - return 1; + int a1 = getM(a); + int b1 = getM(b); + if (a1 != b1) { + return a1 - b1; } + + int a0 = getL(a); + int b0 = getL(b); + return a0 - b0; } - public static double[] div(double[] a, double[] b) { - if (isZero(b)) { - throw new ArithmeticException("/ by zero"); + public static LongEmul div(LongEmul a, LongEmul b) { + return divMod(a, b, false); + } + + public static boolean eq(LongEmul a, LongEmul b) { + return getL(a) == getL(b) && getM(a) == getM(b) && getH(a) == getH(b); + } + + public static LongEmul fromDouble(double value) { + if (Double.isNaN(value)) { + return Const.ZERO; } - if (isZero(a)) { - return ZERO; + if (value < -TWO_PWR_63_DBL) { + return Const.MIN_VALUE; + } + if (value >= TWO_PWR_63_DBL) { + return Const.MAX_VALUE; } - if (eq(a, MIN_VALUE)) { - // handle a==MIN_VALUE carefully because of overflow issues - if (eq(b, ONE) || eq(b, NEG_ONE)) { - // this strange exception is described in JLS3 17.17.2 - return MIN_VALUE; - } - // at this point, abs(b) >= 2, so |a/b| < -MIN_VALUE - double[] halfa = shr(a, 1); - double[] approx = shl(div(halfa, b), 1); - double[] rem = sub(a, mul(b, approx)); - assert gt(rem, MIN_VALUE); - return add(approx, div(rem, b)); + boolean negative = false; + if (value < 0) { + negative = true; + value = -value; } - - if (eq(b, MIN_VALUE)) { - assert !eq(a, MIN_VALUE); - return ZERO; + int a2 = 0; + if (value >= TWO_PWR_44_DBL) { + a2 = (int) (value / TWO_PWR_44_DBL); + value -= a2 * TWO_PWR_44_DBL; } - - // To keep the implementation compact, make a and be - // both be positive and swap the sign of the result - // if necessary. - if (isNegative(a)) { - if (isNegative(b)) { - return div(neg(a), neg(b)); - } else { - return neg(div(neg(a), b)); - } + int a1 = 0; + if (value >= TWO_PWR_22_DBL) { + a1 = (int) (value / TWO_PWR_22_DBL); + value -= a1 * TWO_PWR_22_DBL; } - assert (!isNegative(a)); - if (isNegative(b)) { - return neg(div(a, neg(b))); + int a0 = (int) value; + LongEmul result = create(a0, a1, a2); + if (negative) { + negate(result); } - assert (!isNegative(b)); - - // Use float division to approximate the answer. - // Repeat until the remainder is less than b. - double[] result = ZERO; - double[] rem = a; - while (gte(rem, b)) { - // approximate using float division - double[] deltaResult = fromDouble(Math.floor(toDoubleRoundDown(rem) - / toDoubleRoundUp(b))); - if (isZero(deltaResult)) { - deltaResult = Const.ONE; - } - double[] deltaRem = mul(deltaResult, b); - - assert gte(deltaResult, ONE); - assert lte(deltaRem, rem); - result = add(result, deltaResult); - rem = sub(rem, deltaRem); - } - return result; } - public static boolean eq(double[] a, double[] b) { - return ((a[LOW] == b[LOW]) && (a[HIGH] == b[HIGH])); - } - - public static double[] fromDouble(double value) { - if (Double.isNaN(value)) { - return ZERO; - } - if (value < -TWO_PWR_63_DBL) { - return MIN_VALUE; - } - if (value >= TWO_PWR_63_DBL) { - return MAX_VALUE; - } - if (value > 0) { - return create(Math.floor(value), 0.0); - } else { - return create(Math.ceil(value), 0.0); - } - } - - public static double[] fromInt(int value) { + public static LongEmul fromInt(int value) { if (value > -129 && value < 128) { int rebase = value + 128; - double[] result = CachedInts.boxedValues[rebase]; + if (boxedValues == null) { + boxedValues = new LongEmul[256]; + } + LongEmul result = boxedValues[rebase]; if (result == null) { - result = CachedInts.boxedValues[rebase] = internalFromInt(value); + result = boxedValues[rebase] = create(value); } return result; } - return internalFromInt(value); + + return create(value); } - - public static boolean gt(double[] a, double[] b) { - return compare(a, b) > 0; + + /** + * Return a triple of ints { low, middle, high } that concatenate bitwise to + * the given number. + */ + public static int[] getAsIntArray(long l) { + int[] a = new int[3]; + a[0] = (int) (l & MASK); + a[1] = (int) ((l >> BITS) & MASK); + a[2] = (int) ((l >> BITS01) & MASK_2); + return a; } - - public static boolean gte(double[] a, double[] b) { - return compare(a, b) >= 0; - } - - public static boolean lt(double[] a, double[] b) { - return compare(a, b) < 0; - } - - public static boolean lte(double[] a, double[] b) { - return compare(a, b) <= 0; - } - - public static double[] mod(double[] a, double[] b) { - return sub(a, mul(div(a, b), b)); - } - - public static double[] mul(double[] a, double[] b) { - if (isZero(a)) { - return ZERO; - } - if (isZero(b)) { - return ZERO; - } - - // handle MIN_VALUE carefully, because neg(MIN_VALUE)==MIN_VALUE - if (eq(a, MIN_VALUE)) { - return multByMinValue(b); - } - if (eq(b, MIN_VALUE)) { - return multByMinValue(a); - } - - // If either argument is negative, change it to positive, multiply, - // and then negate the result. - if (isNegative(a)) { - if (isNegative(b)) { - return mul(neg(a), neg(b)); + + public static boolean gt(LongEmul a, LongEmul b) { + int signa = getH(a) >> (BITS2 - 1); + int signb = getH(b) >> (BITS2 - 1); + if (signa == 0) { + if (signb != 0 || getH(a) > getH(b) + || (getH(a) == getH(b) && getM(a) > getM(b)) + || (getH(a) == getH(b) && getM(a) == getM(b) && getL(a) > getL(b))) { + return true; } else { - return neg(mul(neg(a), b)); + return false; + } + } else { + if (signb == 0 || getH(a) < getH(b) + || (getH(a) == getH(b) && getM(a) < getM(b)) + || (getH(a) == getH(b) && getM(a) == getM(b) && getL(a) <= getL(b))) { + return false; + } else { + return true; } } - assert (!isNegative(a)); - if (isNegative(b)) { - return neg(mul(a, neg(b))); - } - assert (!isNegative(b)); - - // If both numbers are small, use float multiplication - if (lt(a, TWO_PWR_24) && lt(b, TWO_PWR_24)) { - return create(toDouble(a) * toDouble(b), 0.0); - } - - // Divide each number into 4 chunks of 16 bits, and then add - // up 4x4 multiplies. Skip the six multiplies where the result - // mod 2^64 would be 0. - double a3 = a[HIGH] % TWO_PWR_48_DBL; - double a4 = a[HIGH] - a3; - double a1 = a[LOW] % TWO_PWR_16_DBL; - double a2 = a[LOW] - a1; - - double b3 = b[HIGH] % TWO_PWR_48_DBL; - double b4 = b[HIGH] - b3; - double b1 = b[LOW] % TWO_PWR_16_DBL; - double b2 = b[LOW] - b1; - - double[] res = ZERO; - - res = addTimes(res, a4, b1); - res = addTimes(res, a3, b2); - res = addTimes(res, a3, b1); - res = addTimes(res, a2, b3); - res = addTimes(res, a2, b2); - res = addTimes(res, a2, b1); - res = addTimes(res, a1, b4); - res = addTimes(res, a1, b3); - res = addTimes(res, a1, b2); - res = addTimes(res, a1, b1); - - return res; } - public static double[] neg(double[] a) { - if (eq(a, MIN_VALUE)) { - return MIN_VALUE; - } - double newHigh = -a[HIGH]; - double newLow = -a[LOW]; - if (newLow > LOW_MAX) { - newLow -= TWO_PWR_32_DBL; - newHigh += TWO_PWR_32_DBL; - } - if (newLow < LOW_MIN) { - newLow += TWO_PWR_32_DBL; - newHigh -= TWO_PWR_32_DBL; - } - return createNormalized(newLow, newHigh); - } - - public static boolean neq(double[] a, double[] b) { - return ((a[LOW] != b[LOW]) || (a[HIGH] != b[HIGH])); - } - - public static double[] not(double[] a) { - return makeFromBits(~highBits(a), ~lowBits(a)); - } - - public static double[] or(double[] a, double[] b) { - return makeFromBits(highBits(a) | highBits(b), lowBits(a) | lowBits(b)); - } - - public static double[] shl(double[] a, int n) { - n &= 63; - - if (eq(a, MIN_VALUE)) { - if (n == 0) { - return a; + public static boolean gte(LongEmul a, LongEmul b) { + int signa = getH(a) >> (BITS2 - 1); + int signb = getH(b) >> (BITS2 - 1); + if (signa == 0) { + if (signb != 0 || getH(a) > getH(b) + || (getH(a) == getH(b) && getM(a) > getM(b)) + || (getH(a) == getH(b) && getM(a) == getM(b) && getL(a) >= getL(b))) { + return true; } else { - return ZERO; + return false; + } + } else { + if (signb == 0 || getH(a) < getH(b) + || (getH(a) == getH(b) && getM(a) < getM(b)) + || (getH(a) == getH(b) && getM(a) == getM(b) && getL(a) < getL(b))) { + return false; + } else { + return true; } } - - if (isNegative(a)) { - return neg(shl(neg(a), n)); - } - - final double twoToN = pwrAsDouble(n); - - double newHigh = a[HIGH] * twoToN % TWO_PWR_64_DBL; - double newLow = a[LOW] * twoToN; - double diff = newLow - (newLow % TWO_PWR_32_DBL); - newHigh += diff; - newLow -= diff; - if (newHigh >= TWO_PWR_63_DBL) { - newHigh -= TWO_PWR_64_DBL; - } - - return createNormalized(newLow, newHigh); } - public static double[] shr(double[] a, int n) { + public static boolean lt(LongEmul a, LongEmul b) { + return !gte(a, b); + } + + public static boolean lte(LongEmul a, LongEmul b) { + return !gt(a, b); + } + + public static LongEmul mod(LongEmul a, LongEmul b) { + divMod(a, b, true); + return remainder; + } + + // Assumes BITS == 22 + public static LongEmul mul(LongEmul a, LongEmul b) { + // Grab 13-bit chunks + int a0 = getL(a) & 0x1fff; + int a1 = (getL(a) >> 13) | ((getM(a) & 0xf) << 9); + int a2 = (getM(a) >> 4) & 0x1fff; + int a3 = (getM(a) >> 17) | ((getH(a) & 0xff) << 5); + int a4 = (getH(a) & 0xfff00) >> 8; + + int b0 = getL(b) & 0x1fff; + int b1 = (getL(b) >> 13) | ((getM(b) & 0xf) << 9); + int b2 = (getM(b) >> 4) & 0x1fff; + int b3 = (getM(b) >> 17) | ((getH(b) & 0xff) << 5); + int b4 = (getH(b) & 0xfff00) >> 8; + + // Compute partial products + // Optimization: if b is small, avoid multiplying by parts that are 0 + int p0 = a0 * b0; // << 0 + int p1 = a1 * b0; // << 13 + int p2 = a2 * b0; // << 26 + int p3 = a3 * b0; // << 39 + int p4 = a4 * b0; // << 52 + + if (b1 != 0) { + p1 += a0 * b1; + p2 += a1 * b1; + p3 += a2 * b1; + p4 += a3 * b1; + } + if (b2 != 0) { + p2 += a0 * b2; + p3 += a1 * b2; + p4 += a2 * b2; + } + if (b3 != 0) { + p3 += a0 * b3; + p4 += a1 * b3; + } + if (b4 != 0) { + p4 += a0 * b4; + } + + // Accumulate into 22-bit chunks: + // .........................................c10|...................c00| + // |....................|..................xxxx|xxxxxxxxxxxxxxxxxxxxxx| p0 + // |....................|......................|......................| + // |....................|...................c11|......c01.............| + // |....................|....xxxxxxxxxxxxxxxxxx|xxxxxxxxx.............| p1 + // |....................|......................|......................| + // |.................c22|...............c12....|......................| + // |..........xxxxxxxxxx|xxxxxxxxxxxxxxxxxx....|......................| p2 + // |....................|......................|......................| + // |.................c23|..c13.................|......................| + // |xxxxxxxxxxxxxxxxxxxx|xxxxx.................|......................| p3 + // |....................|......................|......................| + // |.........c24........|......................|......................| + // |xxxxxxxxxxxx........|......................|......................| p4 + + int c00 = p0 & 0x3fffff; + int c01 = (p1 & 0x1ff) << 13; + int c0 = c00 + c01; + + int c10 = p0 >> 22; + int c11 = p1 >> 9; + int c12 = (p2 & 0x3ffff) << 4; + int c13 = (p3 & 0x1f) << 17; + int c1 = c10 + c11 + c12 + c13; + + int c22 = p2 >> 18; + int c23 = p3 >> 5; + int c24 = (p4 & 0xfff) << 8; + int c2 = c22 + c23 + c24; + + // Propagate high bits from c0 -> c1, c1 -> c2 + c1 += c0 >> BITS; + c0 &= MASK; + c2 += c1 >> BITS; + c1 &= MASK; + c2 &= MASK_2; + + return create(c0, c1, c2); + } + + public static LongEmul neg(LongEmul a) { + int neg0 = (~getL(a) + 1) & MASK; + int neg1 = (~getM(a) + (neg0 == 0 ? 1 : 0)) & MASK; + int neg2 = (~getH(a) + ((neg0 == 0 && neg1 == 0) ? 1 : 0)) & MASK_2; + + return create(neg0, neg1, neg2); + } + + public static boolean neq(LongEmul a, LongEmul b) { + return getL(a) != getL(b) || getM(a) != getM(b) || getH(a) != getH(b); + } + + public static LongEmul not(LongEmul a) { + return create((~getL(a)) & MASK, (~getM(a)) & MASK, (~getH(a)) & MASK_2); + } + + public static LongEmul or(LongEmul a, LongEmul b) { + return create(getL(a) | getL(b), getM(a) | getM(b), getH(a) | getH(b)); + } + + public static LongEmul shl(LongEmul a, int n) { n &= 63; - double shiftFact = pwrAsDouble(n); - double newHigh = Math.floor(a[HIGH] / shiftFact); - double newLow = Math.floor(a[LOW] / shiftFact); - /* - * Doing the above floors separately on each component is safe. If n<32, - * a[HIGH]/shiftFact is guaranteed to be an integer already. For n>32, - * a[HIGH]/shiftFact will have fractional bits, but we need to discard them - * as they shift away. We will end up discarding all of a[LOW] in this case, - * as it divides out to entirely fractional. - */ + int res0, res1, res2; + if (n < BITS) { + res0 = getL(a) << n; + res1 = (getM(a) << n) | (getL(a) >> (BITS - n)); + res2 = (getH(a) << n) | (getM(a) >> (BITS - n)); + } else if (n < BITS01) { + res0 = 0; + res1 = getL(a) << (n - BITS); + res2 = (getM(a) << (n - BITS)) | (getL(a) >> (BITS01 - n)); + } else { + res0 = 0; + res1 = 0; + res2 = getL(a) << (n - BITS01); + } - return create(newLow, newHigh); + return create(res0 & MASK, res1 & MASK, res2 & MASK_2); + } + + public static LongEmul shr(LongEmul a, int n) { + n &= 63; + + int res0, res1, res2; + + // Sign extend h(a) + int a2 = getH(a); + boolean negative = (a2 & SIGN_BIT_VALUE) != 0; + if (negative) { + a2 |= ~MASK_2; + } + + if (n < BITS) { + res2 = a2 >> n; + res1 = (getM(a) >> n) | (a2 << (BITS - n)); + res0 = (getL(a) >> n) | (getM(a) << (BITS - n)); + } else if (n < BITS01) { + res2 = negative ? MASK_2 : 0; + res1 = a2 >> (n - BITS); + res0 = (getM(a) >> (n - BITS)) | (a2 << (BITS01 - n)); + } else { + res2 = negative ? MASK_2 : 0; + res1 = negative ? MASK : 0; + res0 = a2 >> (n - BITS01); + } + + return create(res0 & MASK, res1 & MASK, res2 & MASK_2); } /** * Logical right shift. It does not preserve the sign of the input. */ - public static double[] shru(double[] a, int n) { + public static LongEmul shru(LongEmul a, int n) { n &= 63; - double[] sr = shr(a, n); - if (isNegative(a)) { - // the following changes the high bits to 0, using - // a formula from JLS3 section 15.19 - sr = add(sr, shl(TWO, 63 - n)); + + int res0, res1, res2; + int a2 = getH(a) & MASK_2; + if (n < BITS) { + res2 = a2 >>> n; + res1 = (getM(a) >> n) | (a2 << (BITS - n)); + res0 = (getL(a) >> n) | (getM(a) << (BITS - n)); + } else if (n < BITS01) { + res2 = 0; + res1 = a2 >>> (n - BITS); + res0 = (getM(a) >> (n - BITS)) | (getH(a) << (BITS01 - n)); + } else { + res2 = 0; + res1 = 0; + res0 = a2 >>> (n - BITS01); } - return sr; + return create(res0 & MASK, res1 & MASK, res2 & MASK_2); } - public static double[] sub(double[] a, double[] b) { - double newHigh = a[HIGH] - b[HIGH]; - double newLow = a[LOW] - b[LOW]; - return create(newLow, newHigh); + public static LongEmul sub(LongEmul a, LongEmul b) { + int sum0 = getL(a) - getL(b); + int sum1 = getM(a) - getM(b) + (sum0 >> BITS); + int sum2 = getH(a) - getH(b) + (sum1 >> BITS); + + return create(sum0 & MASK, sum1 & MASK, sum2 & MASK_2); } - /** - * Cast from long to double or float. - */ - public static double toDouble(double[] a) { - return a[HIGH] + a[LOW]; + public static double toDouble(LongEmul a) { + if (LongLib.eq(a, Const.MIN_VALUE)) { + return -9223372036854775808.0; + } + if (LongLib.lt(a, Const.ZERO)) { + return -toDoubleHelper(LongLib.neg(a)); + } + return toDoubleHelper(a); } - - /** - * Cast from long to int. - */ - public static int toInt(double[] a) { - return lowBits(a); + + // Assumes Integer.MIN_VALUE <= a <= Integer.MAX_VALUE + public static int toInt(LongEmul a) { + return getL(a) | (getM(a) << BITS); } - - /** - * Implicit conversion from long to String. - */ - public static String toString(double[] a) { - if (isZero(a)) { + + public static String toString(LongEmul a) { + if (LongLibBase.isZero(a)) { return "0"; } - - if (eq(a, MIN_VALUE)) { - // Special-case MIN_VALUE because neg(MIN_VALUE)==MIN_VALUE + + if (LongLibBase.isMinValue(a)) { + // Special-case MIN_VALUE because neg(MIN_VALUE) == MIN_VALUE return "-9223372036854775808"; } - - if (isNegative(a)) { + + if (LongLibBase.isNegative(a)) { return "-" + toString(neg(a)); } - - double[] rem = a; + + LongEmul rem = a; String res = ""; - - while (!isZero(rem)) { + + while (!LongLibBase.isZero(rem)) { // Do several digits each time through the loop, so as to // minimize the calls to the very expensive emulated div. final int tenPowerZeroes = 9; final int tenPower = 1000000000; - double[] tenPowerLong = fromInt(tenPower); - - final double[] remDivTenPower = div(rem, tenPowerLong); - String digits = "" + toInt(sub(rem, mul(remDivTenPower, tenPowerLong))); - rem = remDivTenPower; - - if (!isZero(rem)) { + LongEmul tenPowerLong = fromInt(tenPower); + + rem = LongLibBase.divMod(rem, tenPowerLong, true); + String digits = "" + toInt(LongLibBase.remainder); + + if (!LongLibBase.isZero(rem)) { int zeroesNeeded = tenPowerZeroes - digits.length(); for (; zeroesNeeded > 0; zeroesNeeded--) { digits = "0" + digits; } } - + res = digits + res; } - + return res; } - - public static double[] typeChange(long value) { - if (RUN_IN_JVM) { - return makeFromBits((int) (value >> 32), (int) value); - } else { - return typeChange0(value); - } + + public static LongEmul xor(LongEmul a, LongEmul b) { + return create(getL(a) ^ getL(b), getM(a) ^ getM(b), getH(a) ^ getH(b)); } - - public static double[] xor(double[] a, double[] b) { - return makeFromBits(highBits(a) ^ highBits(b), lowBits(a) ^ lowBits(b)); - } - - static long toLong(double[] a) { - return (long) a[HIGH] + (long) a[LOW]; - } - - private static double[] addTimes(double[] accum, double a, double b) { - if (a == 0.0) { - return accum; - } - if (b == 0.0) { - return accum; - } - return add(accum, create(a * b, 0.0)); - } - - /* - * Make a new instance equal to valueLow+valueHigh. The arguments do not need - * to be normalized, though by convention valueHigh and valueLow will hold the - * high and low bits, respectively. - */ - private static double[] create(double valueLow, double valueHigh) { - assert (!Double.isNaN(valueHigh)); - assert (!Double.isNaN(valueLow)); - assert (!Double.isInfinite(valueHigh)); - assert (!Double.isInfinite(valueLow)); - assert (Math.floor(valueHigh) == valueHigh); - assert (Math.floor(valueLow) == valueLow); - - // remove overly high bits - valueHigh %= TWO_PWR_64_DBL; - valueLow %= TWO_PWR_64_DBL; - - // segregate high and low bits between high and low - { - double diffHigh = valueHigh % TWO_PWR_32_DBL; - double diffLow = Math.floor(valueLow / TWO_PWR_32_DBL) * TWO_PWR_32_DBL; - - valueHigh = (valueHigh - diffHigh) + diffLow; - valueLow = (valueLow - diffLow) + diffHigh; - } - - // Most or all of the while's in this implementation could probably be if's, - // but they are left as while's for now pending a careful review. - - // make valueLow be positive - while (valueLow < LOW_MIN) { - valueLow += TWO_PWR_32_DBL; - valueHigh -= TWO_PWR_32_DBL; - } - - // make valueLow not too large - while (valueLow > LOW_MAX) { - valueLow -= TWO_PWR_32_DBL; - valueHigh += TWO_PWR_32_DBL; - } - - // make valueHigh within range - valueHigh = valueHigh % TWO_PWR_64_DBL; - while (valueHigh > HIGH_MAX) { - valueHigh -= TWO_PWR_64_DBL; - } - while (valueHigh < HIGH_MIN) { - valueHigh += TWO_PWR_64_DBL; - } - - return createNormalized(valueLow, valueHigh); - } - - /** - * Create an instance. The high and low parts must be normalized. Normal - * callers should use the factory method {@link #make(double, double) make}. - */ - private static double[] createNormalized(double valueLow, double valueHigh) { - assert (valueHigh <= HIGH_MAX); - assert (valueHigh >= HIGH_MIN); - assert (valueLow >= 0); - assert (valueLow <= LOW_MAX); - assert (valueHigh % TWO_PWR_32_DBL == 0); - assert (Math.floor(valueLow) == valueLow); // no fractional bits allowed - - if (RUN_IN_JVM) { - return new double[] {valueLow, valueHigh}; - } else { - return newLong0(valueLow, valueHigh); - } - } - - private static int highBits(double[] a) { - return (int) (a[HIGH] / TWO_PWR_32_DBL); - } - - private static double[] internalFromInt(int value) { - if (value >= 0) { - return createNormalized(value, 0.0); - } else { - return createNormalized(value + TWO_PWR_32_DBL, -TWO_PWR_32_DBL); - } - } - - private static boolean isNegative(double[] a) { - return a[HIGH] < 0; - } - - private static boolean isOdd(double[] a) { - return (lowBits(a) & 1) == 1; - } - - private static boolean isZero(double[] a) { - return a[LOW] == 0.0 && a[HIGH] == 0.0; - } - - private static int lowBits(double[] a) { - if (a[LOW] >= TWO_PWR_31_DBL) { - return (int) (a[LOW] - TWO_PWR_32_DBL); - } else { - return (int) a[LOW]; - } - } - - /** - * Make an instance equivalent to stringing highBits next to lowBits, where - * highBits and lowBits are assumed to be in 32-bit twos-complement notation. - * As a result, for any double[] l, the following identity holds: - * - * <blockquote> <code>l == makeFromBits(l.highBits(), l.lowBits())</code> - * </blockquote> - */ - private static double[] makeFromBits(int highBits, int lowBits) { - double high = highBits * TWO_PWR_32_DBL; - double low = lowBits; - if (lowBits < 0) { - low += TWO_PWR_32_DBL; - } - return createNormalized(low, high); - } - - private static double[] multByMinValue(double[] a) { - if (isOdd(a)) { - return MIN_VALUE; - } else { - return ZERO; - } - } - - /** - * Faster web mode implementation doesn't need full type semantics. - */ - private static native double[] newLong0(double valueLow, double valueHigh) /*-{ - return [valueLow, valueHigh]; - }-*/; - - /** - * Return a power of two as a double. - * - * @return 2 raised to the <code>n</code> - */ - private static double pwrAsDouble(int n) { - if (n <= 30) { - return (1 << n); - } else { - return pwrAsDouble(30) * pwrAsDouble(n - 30); - } - } - - private static double toDoubleRoundDown(double[] a) { - int magnitute = (int) (Math.log(a[HIGH]) / LN_2); - if (magnitute <= PRECISION_BITS) { - return toDouble(a); - } else { - int diff = magnitute - PRECISION_BITS; - int toSubtract = (1 << diff) - 1; - return a[HIGH] + (a[LOW] - toSubtract); - } - } - - private static double toDoubleRoundUp(double[] a) { - int magnitute = (int) (Math.log(a[HIGH]) / LN_2); - if (magnitute <= PRECISION_BITS) { - return toDouble(a); - } else { - int diff = magnitute - PRECISION_BITS; - int toAdd = (1 << diff) - 1; - return a[HIGH] + (a[LOW] + toAdd); - } - } - - /** - * Web mode implementation; the long is already the right object. - */ - @UnsafeNativeLong - private static native double[] typeChange0(long value) /*-{ - return value; - }-*/; - + /** * Not instantiable. */ private LongLib() { } - }
diff --git a/dev/core/super/com/google/gwt/lang/LongLibBase.java b/dev/core/super/com/google/gwt/lang/LongLibBase.java new file mode 100644 index 0000000..f293f9c --- /dev/null +++ b/dev/core/super/com/google/gwt/lang/LongLibBase.java
@@ -0,0 +1,575 @@ +/* + * Copyright 2010 Google Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not + * use this file except in compliance with the License. You may obtain a copy of + * the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the + * License for the specific language governing permissions and limitations under + * the License. + */ +package com.google.gwt.lang; + +import com.google.gwt.core.client.UnsafeNativeLong; + +final class LongEmul { + int l, m, h; // Used only when RUN_IN_JVM is true + + public static LongEmul getInstance() { + return new LongEmul(); + } +} + +/** + * Implements a Java <code>long</code> in a way that can be translated to + * JavaScript. Methods that are meant to be called from outside this package + * are located in {@link LongLib}. + */ +class LongLibBase { + // Force the class to exist + public static LongEmul instance = new LongEmul(); + + /* + * Implementation: A LongEmul containing three values {l, m, h} (low, middle, + * high) such that (x.l + ((long) x.m << 22) + ((long) x.h << 44)) is equal to + * the original long integer. The constant 22 is chosen since some browsers + * are faster when operating on integers of 24 bits or less. + * + * By convention, we expect and maintain that the upper bits of each word + * be zeroed. + * + * Note that this class must be careful using type "long". Being the + * implementation of the long type for web mode, any place it uses a long is + * not usable in web mode. There is currently one such method: {@link + * LongLib#getAsIntArray}. + */ + + // Note that the 'mul' method implicitly depends on the specific value + // BITS == 22 + protected static final int BITS = 22; + protected static final int BITS01 = 2 * BITS; + protected static final int BITS2 = 64 - BITS01; + protected static final int MASK = (1 << BITS) - 1; + protected static final int MASK_2 = (1 << BITS2) - 1; + protected static LongEmul remainder; + + /** + * Allow a standalone Java test such as LongLibJreTest to run this code. + */ + protected static boolean RUN_IN_JVM = false; + + protected static final int SIGN_BIT = BITS2 - 1; + protected static final int SIGN_BIT_VALUE = 1 << SIGN_BIT; + protected static final double TWO_PWR_15_DBL = 0x8000; + protected static final double TWO_PWR_16_DBL = 0x10000; + protected static final double TWO_PWR_22_DBL = 0x400000; + protected static final double TWO_PWR_31_DBL = TWO_PWR_16_DBL * TWO_PWR_15_DBL; + protected static final double TWO_PWR_32_DBL = TWO_PWR_16_DBL * TWO_PWR_16_DBL; + protected static final double TWO_PWR_44_DBL = TWO_PWR_22_DBL * TWO_PWR_22_DBL; + protected static final double TWO_PWR_63_DBL = TWO_PWR_32_DBL * TWO_PWR_31_DBL; + + /** + * Web mode implementation; the int array is already the right object. + */ + @UnsafeNativeLong + protected static native long asLong(LongEmul value) /*-{ + return value; + }-*/; + + protected static LongEmul create(int value) { + int a0 = value & MASK; + int a1 = (value >> BITS) & MASK; + int a2 = (value < 0) ? MASK_2 : 0; + + if (RUN_IN_JVM ) { + LongEmul a = new LongEmul(); + a.l = a0; + a.m = a1; + a.h = a2; + return a; + } + return create0(a0, a1, a2); + } + + protected static LongEmul create(int a0, int a1, int a2) { + if (RUN_IN_JVM) { + LongEmul a = new LongEmul(); + a.l = a0; + a.m = a1; + a.h = a2; + return a; + } + return create0(a0, a1, a2); + } + + protected static LongEmul divMod(LongEmul a, LongEmul b, boolean computeRemainder) { + if (isZero(b)) { + throw new ArithmeticException("divide by zero"); + } + if (isZero(a)) { + if (computeRemainder) { + remainder = create(); // zero + } + return create(); // zero + } + + // MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0 + if (isMinValue(b)) { + return divModByMinValue(a, computeRemainder); + } + + // Normalize b to abs(b), keeping track of the parity in 'negative'. + // We can do this because we have already ensured that b != MIN_VALUE. + boolean negative = false; + if (isNegative(b)) { + b = LongLib.neg(b); + negative = !negative; + } + + // If b == 2^n, bpower will be n, otherwise it will be -1 + int bpower = powerOfTwo(b); + + // True if the original value of a is negative + boolean aIsNegative = false; + // True if the original value of a is Long.MIN_VALUE + boolean aIsMinValue = false; + + /* + * Normalize a to a positive value, keeping track of the sign change + * in 'negative' (which tracks the sign of both a and b and is used to + * determine the sign of the quotient) and 'aIsNegative' (which is used + * to determine the sign of the remainder). + * + * For all values of a except MIN_VALUE, we can just negate a and + * modify negative and aIsNegative appropriately. When a == MIN_VALUE, + * negation is not possible without overflowing 64 bits, so instead + * of computing abs(MIN_VALUE) / abs(b) we compute + * (abs(MIN_VALUE) - 1) / abs(b). The only circumstance under which + * these quotients differ is when b is a power of two, which will + * divide abs(MIN_VALUE) == 2^64 exactly. In this case, we can get + * the proper result by shifting MIN_VALUE in unsigned fashion. + * + * We make a single copy of a before the first operation that needs to + * modify its value. + */ + boolean aIsCopy = false; + if (isMinValue(a)) { + aIsMinValue = true; + aIsNegative = true; + // If b is not a power of two, treat -a as MAX_VALUE (instead of the + // actual value (MAX_VALUE + 1)). + if (bpower == -1) { + a = create(LongLib.Const.MAX_VALUE); + aIsCopy = true; + negative = !negative; + } else { + // Signed shift of MIN_VALUE produces the right answer + LongEmul c = LongLib.shr(a, bpower); + if (negative) { + negate(c); + } + if (computeRemainder) { + remainder = create(); // zero + } + return c; + } + } else if (isNegative(a)) { + aIsNegative = true; + a = LongLib.neg(a); + aIsCopy = true; + negative = !negative; + } + + // Now both a and b are non-negative + + // If b is a power of two, just shift + if (bpower != -1) { + return divModByShift(a, bpower, negative, aIsNegative, + computeRemainder); + } + + // if a < b, the quotient is 0 and the remainder is a + if (LongLib.lt(a, b)) { + if (computeRemainder) { + if (aIsNegative) { + remainder = LongLib.neg(a); + } else { + remainder = create(a); + } + } + return create(); // zero + } + + // Generate the quotient using bit-at-a-time long division + return divModHelper(aIsCopy ? a : create(a), b, negative, + aIsNegative, aIsMinValue, computeRemainder); + } + + protected static int getH(LongEmul a) { + if (RUN_IN_JVM) { + return a.h; + } + return getHNative(a); + } + + protected static int getL(LongEmul a) { + if (RUN_IN_JVM) { + return a.l; + } + return getLNative(a); + } + + protected static int getM(LongEmul a) { + if (RUN_IN_JVM) { + return a.m; + } + return getMNative(a); + } + + protected static boolean isMinValue(LongEmul a) { + return getH(a) == SIGN_BIT_VALUE && getM(a) == 0 && getL(a) == 0; + } + + protected static boolean isNegative(LongEmul a) { + return sign(a) != 0; + } + + protected static boolean isZero(LongEmul a) { + return getL(a) == 0 && getM(a) == 0 && getH(a) == 0; + } + + /** + * a = -a + */ + protected static void negate(LongEmul a) { + int neg0 = (~getL(a) + 1) & MASK; + int neg1 = (~getM(a) + (neg0 == 0 ? 1 : 0)) & MASK; + int neg2 = (~getH(a) + ((neg0 == 0 && neg1 == 0) ? 1 : 0)) & MASK_2; + + if (RUN_IN_JVM) { + a.l = neg0; + a.m = neg1; + a.h = neg2; + } else { + setL(a, neg0); + setM(a, neg1); + setH(a, neg2); + } + } + + /** + * @return 0 if a is >= 0, 1 if a < 0. + */ + protected static int sign(LongEmul a) { + return getH(a) >> (BITS2 - 1); + } + + // Assumes a is non-negative + protected static double toDoubleHelper(LongEmul a) { + return getL(a) + (getM(a) * TWO_PWR_22_DBL) + (getH(a) * TWO_PWR_44_DBL); + } + + /** + * Creates a long instance equal to 0. + */ + private static LongEmul create() { + if (RUN_IN_JVM) { + return new LongEmul(); + } + return create0(0, 0, 0); + } + + /** + * Creates a long instance equal to a given long. + */ + private static LongEmul create(LongEmul a) { + if (RUN_IN_JVM) { + LongEmul b = new LongEmul(); + b.l = getL(a); + b.m = getM(a); + b.h = getH(a); + return b; + } + return create0(getL(a), getM(a), getH(a)); + } + + private static native LongEmul create0(int l, int m, int h) /*-{ + return (a = @com.google.gwt.lang.LongEmul::getInstance()(), a.l = l, a.m = m, a.h = h, a); + }-*/; + + private static LongEmul divModByMinValue(LongEmul a, boolean computeRemainder) { + // MIN_VALUE / MIN_VALUE == 1, remainder = 0 + // (a != MIN_VALUE) / MIN_VALUE == 0, remainder == a + if (isMinValue(a)) { + if (computeRemainder) { + remainder = create(); // zero + } + return create(LongLib.Const.ONE); + } + if (computeRemainder) { + remainder = create(a); + } + return create(); // zero + } + + private static LongEmul divModByShift(LongEmul a, int bpower, + boolean negative, boolean aIsNegative, boolean computeRemainder) { + LongEmul c = LongLib.shr(a, bpower); + if (negative) { + negate(c); + } + + if (computeRemainder) { + a = maskRight(a, bpower); + if (aIsNegative) { + remainder = LongLib.neg(a); + } else { + remainder = create(a); + } + } + return c; + } + + private static LongEmul divModHelper(LongEmul a, LongEmul b, boolean negative, + boolean aIsNegative, boolean aIsMinValue, boolean computeRemainder) { + // Align the leading one bits of a and b by shifting b left + int shift = numberOfLeadingZeros(b) - numberOfLeadingZeros(a); + LongEmul bshift = LongLib.shl(b, shift); + + LongEmul quotient = create(); + while (shift >= 0) { + boolean gte = trialSubtract(a, bshift); + if (gte) { + setBit(quotient, shift); + if (isZero(a)) { + break; + } + } + + toShru1(bshift); + shift--; + } + + if (negative) { + negate(quotient); + } + + if (computeRemainder) { + if (aIsNegative) { + remainder = LongLib.neg(a); + if (aIsMinValue) { + remainder = LongLib.sub(remainder, LongLib.Const.ONE); + } + } else { + remainder = create(a); + } + } + + return quotient; + } + + private static native int getHNative(LongEmul a) /*-{ + return a.h; + }-*/; + + private static native int getLNative(LongEmul a) /*-{ + return a.l; + }-*/; + + private static native int getMNative(LongEmul a) /*-{ + return a.m; + }-*/; + + /** + * a &= ((1L << bits) - 1) + */ + private static LongEmul maskRight(LongEmul a, int bits) { + int b0, b1, b2; + if (bits <= BITS) { + b0 = getL(a) & ((1 << bits) - 1); + b1 = b2 = 0; + } else if (bits <= BITS01) { + b0 = getL(a); + b1 = getM(a) & ((1 << (bits - BITS)) - 1); + b2 = 0; + } else { + b0 = getL(a); + b1 = getM(a); + b2 = getH(a) & ((1 << (bits - BITS01)) - 1); + } + + return create(b0, b1, b2); + } + + /** + * Return the number of leading zeros of a long value. + */ + private static int numberOfLeadingZeros(LongEmul a) { + int b2 = Integer.numberOfLeadingZeros(getH(a)); + if (b2 == 32) { + int b1 = Integer.numberOfLeadingZeros(getM(a)); + if (b1 == 32) { + return Integer.numberOfLeadingZeros(getL(a)) + BITS2 + 2 * BITS - 32; + } else { + return b1 + BITS2 - (32 - BITS); + } + } else { + return b2 - (32 - BITS2); + } + } + + /** + * Return the exact log base 2 of a, or -1 if a is not a power of two: + * + * <pre> + * if (x == 2^n) { + * return n; + * } else { + * return -1; + * } + * </pre> + */ + private static int powerOfTwo(LongEmul a) { + // Power of two or 0 + int l = getL(a); + if ((l & (l - 1)) != 0) { + return -1; + } + int m = getM(a); + if ((m & (m - 1)) != 0) { + return -1; + } + int h = getH(a); + if ((h & (h - 1)) != 0) { + return -1; + } + if (h == 0 && m == 0 && l == 0) { + return -1; + } + if (h == 0 && m == 0 && l != 0) { + return Integer.numberOfTrailingZeros(l); + } + if (h == 0 && m != 0 && l == 0) { + return Integer.numberOfTrailingZeros(m) + BITS; + } + if (h != 0 && m == 0 && l == 0) { + return Integer.numberOfTrailingZeros(h) + BITS01; + } + + return -1; + } + + private static void setBit(LongEmul a, int bit) { + if (RUN_IN_JVM) { + if (bit < BITS) { + a.l |= 0x1 << bit; + } else if (bit < BITS01) { + a.m |= 0x1 << (bit - BITS); + } else { + a.h |= 0x1 << (bit - BITS01); + } + } else { + if (bit < BITS) { + setBitL(a, bit); + } else if (bit < BITS01) { + setBitM(a, bit - BITS); + } else { + setBitH(a, bit - BITS01); + } + } + } + + private static native void setBitH(LongEmul a, int bit) /*-{ + a.h |= 1 << bit; + }-*/; + + private static native void setBitL(LongEmul a, int bit) /*-{ + a.l |= 1 << bit; + }-*/; + + private static native void setBitM(LongEmul a, int bit) /*-{ + a.m |= 1 << bit; + }-*/; + + private static native void setH(LongEmul a, int x) /*-{ + a.h = x; + }-*/; + + private static native void setL(LongEmul a, int x) /*-{ + a.l = x; + }-*/; + + private static native void setM(LongEmul a, int x) /*-{ + a.m = x; + }-*/; + + /** + * a >>= 1. Assumes a >= 0. + */ + private static void toShru1(LongEmul a) { + int a1 = getM(a); + int a2 = getH(a); + int a0 = getL(a); + + if (RUN_IN_JVM) { + a.h = a2 >>> 1; + a.m = (a1 >>> 1) | ((a2 & 0x1) << (BITS - 1)); + a.l = (a0 >>> 1) | ((a1 & 0x1) << (BITS - 1)); + } else { + setH(a, a2 >>> 1); + setM(a, (a1 >>> 1) | ((a2 & 0x1) << (BITS - 1))); + setL(a, (a0 >>> 1) | ((a1 & 0x1) << (BITS - 1))); + } + } + + /** + * Attempt to subtract b from a if a >= b: + * + * <pre> + * if (a >= b) { + * a -= b; + * return true; + * } else { + * return false; + * } + * </pre> + */ + private static boolean trialSubtract(LongEmul a, LongEmul b) { + // Early exit + int sum2 = getH(a) - getH(b); + if (sum2 < 0) { + return false; + } + + int sum0 = getL(a) - getL(b); + int sum1 = getM(a) - getM(b) + (sum0 >> BITS); + sum2 += (sum1 >> BITS); + + if (sum2 < 0) { + return false; + } + + if (RUN_IN_JVM) { + a.l = sum0 & MASK; + a.m = sum1 & MASK; + a.h = sum2 & MASK_2; + } else { + setL(a, sum0 & MASK); + setM(a, sum1 & MASK); + setH(a, sum2 & MASK_2); + } + + return true; + } + + /** + * Not instantiable outside this package. + */ + LongLibBase() { + } +}
diff --git a/dev/core/test/com/google/gwt/lang/LongLibJreTest.java b/dev/core/test/com/google/gwt/lang/LongLibJreTest.java index d8b5c85..559bdab 100644 --- a/dev/core/test/com/google/gwt/lang/LongLibJreTest.java +++ b/dev/core/test/com/google/gwt/lang/LongLibJreTest.java
@@ -18,14 +18,14 @@ import junit.framework.TestCase; /** - * Test the LongLib class as a GWTTestCase. + * Test the LongLib class as a non-GWT TestCase. */ public class LongLibJreTest extends TestCase { - + static { - LongLib.RUN_IN_JVM = true; + LongLibBase.RUN_IN_JVM = true; } - + private LongLibTestBase impl = new LongLibTestBase(); public void testAAAA() {
diff --git a/dev/core/test/com/google/gwt/lang/LongLibTestBase.java b/dev/core/test/com/google/gwt/lang/LongLibTestBase.java index bd0f38d..9f2052a 100644 --- a/dev/core/test/com/google/gwt/lang/LongLibTestBase.java +++ b/dev/core/test/com/google/gwt/lang/LongLibTestBase.java
@@ -25,36 +25,36 @@ */ public class LongLibTestBase extends TestCase { - static void assertEquals(double[] expected, double[] actual) { + static void assertEquals(LongEmul expected, LongEmul actual) { assertTrue("expected=" + LongLib.toString(expected) + " actual=" + LongLib.toString(actual), LongLib.eq(expected, actual)); } public void testAdditive() { { - final double[] n1 = LongLib.fromInt(1234); - final double[] n2 = LongLib.fromInt(9876); + final LongEmul n1 = LongLib.fromInt(1234); + final LongEmul n2 = LongLib.fromInt(9876); assertEquals(LongLib.fromInt(11110), LongLib.add(n1, n2)); assertEquals(LongLib.fromInt(-8642), LongLib.sub(n1, n2)); } { - final double[] n1 = LongLib.fromInt(-1234); - final double[] n2 = LongLib.fromInt(9876); + final LongEmul n1 = LongLib.fromInt(-1234); + final LongEmul n2 = LongLib.fromInt(9876); assertEquals(LongLib.fromInt(8642), LongLib.add(n1, n2)); assertEquals(LongLib.fromInt(-11110), LongLib.sub(n1, n2)); } { - final double[] n1 = LongLib.fromInt(-1234); - final double[] n2 = LongLib.fromInt(-9876); + final LongEmul n1 = LongLib.fromInt(-1234); + final LongEmul n2 = LongLib.fromInt(-9876); assertEquals(LongLib.fromInt(-11110), LongLib.add(n1, n2)); assertEquals(LongLib.fromInt(8642), LongLib.sub(n1, n2)); } { - final double[] n1 = longFromBits(0x12345678, 0xabcdabcd); - final double[] n2 = longFromBits(0x77773333, 0x22224444); + final LongEmul n1 = longFromBits(0x12345678, 0xabcdabcd); + final LongEmul n2 = longFromBits(0x77773333, 0x22224444); assertEquals(longFromBits(0x89ab89ab, 0xcdeff011), LongLib.add(n1, n2)); assertEquals(longFromBits(0x9abd2345, 0x89ab6789), LongLib.sub(n1, n2)); } @@ -62,8 +62,8 @@ public void testBitOps() { { - final double[] n1 = LongLib.fromInt(1234); - final double[] n2 = LongLib.fromInt(9876); + final LongEmul n1 = LongLib.fromInt(1234); + final LongEmul n2 = LongLib.fromInt(9876); assertEquals(LongLib.fromInt(1168), LongLib.and(n1, n2)); assertEquals(LongLib.fromInt(9942), LongLib.or(n1, n2)); @@ -73,8 +73,8 @@ } { - final double[] n1 = LongLib.fromInt(-1234); - final double[] n2 = LongLib.fromInt(9876); + final LongEmul n1 = LongLib.fromInt(-1234); + final LongEmul n2 = LongLib.fromInt(9876); assertEquals(LongLib.fromInt(8708), LongLib.and(n1, n2)); assertEquals(LongLib.fromInt(-66), LongLib.or(n1, n2)); assertEquals(LongLib.fromInt(-8774), LongLib.xor(n1, n2)); @@ -83,8 +83,8 @@ } { - final double[] n1 = LongLib.shl(LongLib.fromInt(0x1234), 32); - final double[] n2 = LongLib.shl(LongLib.fromInt(0x9876), 32); + final LongEmul n1 = LongLib.shl(LongLib.fromInt(0x1234), 32); + final LongEmul n2 = LongLib.shl(LongLib.fromInt(0x9876), 32); assertEquals(LongLib.shl(LongLib.fromInt(0x1034), 32), LongLib.and(n1, n2)); assertEquals(LongLib.shl(LongLib.fromInt(0x9a76), 32), LongLib.or(n1, n2)); @@ -113,17 +113,28 @@ assertTrue(!LongLib.eq(LongLib.fromInt(12), LongLib.fromInt(11))); assertTrue(LongLib.gte(LongLib.fromInt(12), LongLib.fromInt(11))); assertTrue(LongLib.gt(LongLib.fromInt(12), LongLib.fromInt(11))); + + assertTrue(LongLib.gt(LongLib.fromInt(-10), LongLib.fromInt(-11))); + assertTrue(LongLib.gt(LongLib.fromInt(10), LongLib.fromInt(-11))); + assertTrue(!LongLib.gt(LongLib.fromInt(-10), LongLib.fromInt(11))); + assertTrue(LongLib.gte(LongLib.fromInt(-10), LongLib.fromInt(-11))); + assertTrue(LongLib.gte(LongLib.fromInt(-10), LongLib.fromInt(-10))); + assertTrue(!LongLib.lt(LongLib.fromInt(-10), LongLib.fromInt(-11))); + assertTrue(!LongLib.lte(LongLib.fromInt(-10), LongLib.fromInt(-11))); + assertTrue(LongLib.lte(LongLib.fromInt(-10), LongLib.fromInt(-10))); + assertTrue(LongLib.eq(LongLib.fromInt(-10), LongLib.fromInt(-10))); + assertTrue(!LongLib.neq(LongLib.fromInt(-10), LongLib.fromInt(-10))); // the following three comparisons cannot be implemented by // subtracting the arguments, because the subtraction causes an overflow - final double[] largeNeg = longFromBits(0x82341234, 0x0); - final double[] largePos = longFromBits(0x12341234, 0x0); + final LongEmul largeNeg = longFromBits(0x82341234, 0x0); + final LongEmul largePos = longFromBits(0x12341234, 0x0); assertTrue(LongLib.lt(largeNeg, largePos)); assertTrue(LongLib.lt(Const.MIN_VALUE, LongLib.fromInt(0))); assertTrue(LongLib.gt(LongLib.fromInt(0), Const.MIN_VALUE)); - final double[] largePosPlusOne = LongLib.add(largePos, LongLib.fromInt(1)); + final LongEmul largePosPlusOne = LongLib.add(largePos, LongLib.fromInt(1)); assertTrue(LongLib.lt(largePos, largePosPlusOne)); assertTrue(LongLib.lte(largePos, largePosPlusOne)); @@ -152,22 +163,64 @@ } public void testDiv() { - double[] deadBeef = LongLib.typeChange(0xdeadbeefdeadbeefL); - double[] ten = LongLib.fromInt(10); - assertEquals(LongLib.typeChange(-240105308887621659L), LongLib.div( + LongEmul deadBeef = longFromBits(0xdeadbeef, 0xdeadbeef); + LongEmul ten = LongLib.fromInt(10); + assertEquals(longFromBits(0xfcaaf97e, 0x63115fe5), LongLib.div( deadBeef, ten)); assertEquals(Const.ZERO, LongLib.div(Const.ONE, Const.TWO)); - assertEquals(LongLib.typeChange(4611686018427387903L), LongLib.div( + assertEquals(longFromBits(0x3fffffff, 0xffffffff), LongLib.div( Const.MAX_VALUE, Const.TWO)); + + assertEquals(Const.ZERO, LongLib.div(Const.ZERO, LongLib.fromInt(1000))); + assertEquals(Const.ONE, LongLib.div(Const.MIN_VALUE, Const.MIN_VALUE)); + assertEquals(Const.ZERO, LongLib.div(LongLib.fromInt(1000), Const.MIN_VALUE)); + assertEquals("-1125899906842624", LongLib.toString(LongLib.div(Const.MIN_VALUE, LongLib.fromInt(8192)))); + assertEquals("-1125762484664320", LongLib.toString(LongLib.div(Const.MIN_VALUE, LongLib.fromInt(8193)))); + assertEquals(Const.ZERO, LongLib.div(LongLib.fromInt(-1000), LongLib.fromInt(8192))); + assertEquals(Const.ZERO, LongLib.div(LongLib.fromInt(-1000), LongLib.fromInt(8193))); + assertEquals(LongLib.fromInt(-122070), LongLib.div(LongLib.fromInt(-1000000000), LongLib.fromInt(8192))); + assertEquals(LongLib.fromInt(-122055), LongLib.div(LongLib.fromInt(-1000000000), LongLib.fromInt(8193))); + assertEquals(LongLib.fromInt(122070), LongLib.div(LongLib.fromInt(1000000000), LongLib.fromInt(8192))); + assertEquals(LongLib.fromInt(122055), LongLib.div(LongLib.fromInt(1000000000), LongLib.fromInt(8193))); + + assertEquals(longFromBits(0x1fffff, 0xffffffff), LongLib.div(Const.MAX_VALUE, longFromBits(0x00000000, 0x00000400))); + assertEquals(longFromBits(0x1fff, 0xffffffff), LongLib.div(Const.MAX_VALUE, longFromBits(0x00000000, 0x00040000))); + assertEquals(longFromBits(0x1f, 0xffffffff), LongLib.div(Const.MAX_VALUE, longFromBits(0x00000000, 0x04000000))); + assertEquals(LongLib.fromInt(536870911), LongLib.div(Const.MAX_VALUE, longFromBits(0x00000004, 0x00000000))); + assertEquals(LongLib.fromInt(2097151), LongLib.div(Const.MAX_VALUE, longFromBits(0x00000400, 0x00000000))); + assertEquals(LongLib.fromInt(8191), LongLib.div(Const.MAX_VALUE, longFromBits(0x00040000, 0x00000000))); + assertEquals(LongLib.fromInt(31), LongLib.div(Const.MAX_VALUE, longFromBits(0x04000000, 0x00000000))); + + LongLib.div(Const.MAX_VALUE, longFromBits(0x00000000, 0x00000300)); + LongLib.div(Const.MAX_VALUE, longFromBits(0x00000000, 0x30000000)); + LongLib.div(Const.MAX_VALUE, longFromBits(0x00300000, 0x00000000)); + LongLib.div(Const.MAX_VALUE, longFromBits(0x00300000, 0x00000300)); + LongLib.div(Const.MAX_VALUE, longFromBits(0x00300000, 0x30000000)); + LongLib.div(Const.MAX_VALUE, longFromBits(0x00000000, 0x30000300)); + LongLib.div(Const.MAX_VALUE, longFromBits(0x00300000, 0x30000300)); } public void testFactorial() { - double[] fact18 = fact(LongLib.fromInt(18)); - double[] fact17 = fact(LongLib.fromInt(17)); + LongEmul fact18 = fact(LongLib.fromInt(18)); + LongEmul fact17 = fact(LongLib.fromInt(17)); assertEquals(LongLib.fromInt(18), LongLib.div(fact18, fact17)); } public void testFromDouble() { + assertEquals("4611686018427387904", LongLib.toString(LongLib.fromDouble(Math.pow(2, 62)))); + assertEquals("35184372088832", LongLib.toString(LongLib.fromDouble(Math.pow(2, 45)))); + assertEquals("35184372088832", LongLib.toString(LongLib.fromDouble(Math.pow(2, 45)))); + assertEquals("17592186044417", LongLib.toString(LongLib.fromDouble(Math.pow(2, 44) + 1))); + assertEquals("17592186044416", LongLib.toString(LongLib.fromDouble(Math.pow(2, 44)))); + assertEquals("17592186044415", LongLib.toString(LongLib.fromDouble(Math.pow(2, 44) - 1))); + assertEquals("8796093022208", LongLib.toString(LongLib.fromDouble(Math.pow(2, 43)))); + assertEquals(LongLib.fromInt(8388608), LongLib.fromDouble(Math.pow(2, 23))); + assertEquals(LongLib.fromInt(4194305), LongLib.fromDouble(Math.pow(2, 22) + 1)); + assertEquals(LongLib.fromInt(4194304), LongLib.fromDouble(Math.pow(2, 22))); + assertEquals(LongLib.fromInt(4194303), LongLib.fromDouble(Math.pow(2, 22) - 1)); + assertEquals(LongLib.fromInt(2097152), LongLib.fromDouble(Math.pow(2, 21))); + assertEquals(LongLib.fromInt(1048576), LongLib.fromDouble(Math.pow(2, 20))); + // these tests are based on JLS3, section 5.1.3 assertEquals(LongLib.fromInt(10), LongLib.fromDouble(10.5)); @@ -190,6 +243,28 @@ assertEquals(Const.MAX_VALUE, LongLib.neg(LongLib.add(Const.MIN_VALUE, LongLib.fromInt(1)))); } + + public void testMod() { + assertEquals(LongLib.fromInt(0), LongLib.mod(Const.ZERO, LongLib.fromInt(1000))); + assertEquals(LongLib.fromInt(0), LongLib.mod(Const.MIN_VALUE, Const.MIN_VALUE)); + assertEquals(LongLib.fromInt(1000), LongLib.mod(LongLib.fromInt(1000), Const.MIN_VALUE)); + assertEquals(LongLib.fromInt(0), LongLib.mod(Const.MIN_VALUE, LongLib.fromInt(8192))); + assertEquals(LongLib.fromInt(-2048), LongLib.mod(Const.MIN_VALUE, LongLib.fromInt(8193))); + assertEquals(LongLib.fromInt(-1000), LongLib.mod(LongLib.fromInt(-1000), LongLib.fromInt(8192))); + assertEquals(LongLib.fromInt(-1000), LongLib.mod(LongLib.fromInt(-1000), LongLib.fromInt(8193))); + assertEquals(LongLib.fromInt(-2560), LongLib.mod(LongLib.fromInt(-1000000000), LongLib.fromInt(8192))); + assertEquals(LongLib.fromInt(-3385), LongLib.mod(LongLib.fromInt(-1000000000), LongLib.fromInt(8193))); + assertEquals(LongLib.fromInt(2560), LongLib.mod(LongLib.fromInt(1000000000), LongLib.fromInt(8192))); + assertEquals(LongLib.fromInt(3385), LongLib.mod(LongLib.fromInt(1000000000), LongLib.fromInt(8193))); + + assertEquals(longFromBits(0x0, 0x3ff), LongLib.mod(Const.MAX_VALUE, longFromBits(0x00000000, 0x00000400))); + assertEquals(longFromBits(0x0, 0x3ffff), LongLib.mod(Const.MAX_VALUE, longFromBits(0x00000000, 0x00040000))); + assertEquals(longFromBits(0x0, 0x3ffffff), LongLib.mod(Const.MAX_VALUE, longFromBits(0x00000000, 0x04000000))); + assertEquals(longFromBits(0x3, 0xffffffff), LongLib.mod(Const.MAX_VALUE, longFromBits(0x00000004, 0x00000000))); + assertEquals(longFromBits(0x3ff, 0xffffffff), LongLib.mod(Const.MAX_VALUE, longFromBits(0x00000400, 0x00000000))); + assertEquals(longFromBits(0x3ffff, 0xffffffff), LongLib.mod(Const.MAX_VALUE, longFromBits(0x00040000, 0x00000000))); + assertEquals(longFromBits(0x3ffffff, 0xffffffff), LongLib.mod(Const.MAX_VALUE, longFromBits(0x04000000, 0x00000000))); + } public void testMultiplicative() { assertEquals(LongLib.fromInt(3333), LongLib.mul(LongLib.fromInt(1111), @@ -282,7 +357,7 @@ assertEquals(LongLib.fromInt(-1 << 5), LongLib.shl(LongLib.fromInt(-1), 5)); assertEquals(LongLib.fromInt(-1), LongLib.shl(LongLib.fromInt(-1), 0)); - assertEquals(LongLib.neg(LongLib.typeChange(0x4000000000000000L)), + assertEquals(LongLib.neg(longFromBits(0x40000000, 0x00000000)), LongLib.shr(LongLib.shl(LongLib.fromInt(1), 63), 1)); assertEquals(LongLib.fromInt(0), LongLib.shl(LongLib.shl( LongLib.fromInt(-1), 32), 32)); @@ -292,12 +367,89 @@ LongLib.neg(longFromBits(8, 0)), 1)); assertEquals(longFromBits(0x7ffffffc, 0x0), LongLib.shru( LongLib.neg(longFromBits(8, 0)), 1)); + + assertEquals(longFromBits(0x00723456, 0x789abcde), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 8)); + assertEquals(longFromBits(0x00007234, 0x56789abc), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 16)); + assertEquals(longFromBits(0x00000072, 0x3456789a), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 24)); + assertEquals(longFromBits(0x00000007, 0x23456789), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 28)); + assertEquals(longFromBits(0x00000000, 0x72345678), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 32)); + assertEquals(longFromBits(0x00000000, 0x07234567), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 36)); + assertEquals(longFromBits(0x00000000, 0x00723456), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 40)); + assertEquals(longFromBits(0x00000000, 0x00072345), LongLib.shr( + longFromBits(0x72345678, 0x9abcde00), 44)); + assertEquals(longFromBits(0x00000000, 0x00007234), LongLib.shr( + longFromBits(0x72345678, 0x9abcdef0), 48)); + + assertEquals(longFromBits(0x00723456, 0x789abcde), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 8)); + assertEquals(longFromBits(0x00007234, 0x56789abc), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 16)); + assertEquals(longFromBits(0x00000072, 0x3456789a), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 24)); + assertEquals(longFromBits(0x00000007, 0x23456789), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 28)); + assertEquals(longFromBits(0x00000000, 0x72345678), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 32)); + assertEquals(longFromBits(0x00000000, 0x07234567), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 36)); + assertEquals(longFromBits(0x00000000, 0x00723456), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 40)); + assertEquals(longFromBits(0x00000000, 0x00072345), LongLib.shru( + longFromBits(0x72345678, 0x9abcde00), 44)); + assertEquals(longFromBits(0x00000000, 0x00007234), LongLib.shru( + longFromBits(0x72345678, 0x9abcdef0), 48)); + + assertEquals(longFromBits(0xff923456, 0x789abcde), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 8)); + assertEquals(longFromBits(0xffff9234, 0x56789abc), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 16)); + assertEquals(longFromBits(0xffffff92, 0x3456789a), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 24)); + assertEquals(longFromBits(0xfffffff9, 0x23456789), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 28)); + assertEquals(longFromBits(0xffffffff, 0x92345678), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 32)); + assertEquals(longFromBits(0xffffffff, 0xf9234567), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 36)); + assertEquals(longFromBits(0xffffffff, 0xff923456), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 40)); + assertEquals(longFromBits(0xffffffff, 0xfff92345), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 44)); + assertEquals(longFromBits(0xffffffff, 0xffff9234), LongLib.shr( + longFromBits(0x92345678, 0x9abcdef0), 48)); + + assertEquals(longFromBits(0x00923456, 0x789abcde), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 8)); + assertEquals(longFromBits(0x00009234, 0x56789abc), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 16)); + assertEquals(longFromBits(0x00000092, 0x3456789a), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 24)); + assertEquals(longFromBits(0x00000009, 0x23456789), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 28)); + assertEquals(longFromBits(0x00000000, 0x92345678), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 32)); + assertEquals(longFromBits(0x00000000, 0x09234567), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 36)); + assertEquals(longFromBits(0x00000000, 0x00923456), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 40)); + assertEquals(longFromBits(0x00000000, 0x00092345), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 44)); + assertEquals(longFromBits(0x00000000, 0x00009234), LongLib.shru( + longFromBits(0x92345678, 0x9abcdef0), 48)); } // Issue 1198, and also a good exercise of several methods. public void testToHexString() { - double[] deadbeaf12341234 = longFromBits(0xdeadbeaf, 0x12341234); + LongEmul deadbeaf12341234 = longFromBits(0xdeadbeaf, 0x12341234); + assertEquals("0", toHexString(Const.ZERO)); assertEquals("deadbeaf12341234", toHexString(deadbeaf12341234)); } @@ -310,14 +462,14 @@ int top = 922337201; int bottom = 967490662; - double[] fullnum = LongLib.add(LongLib.mul(LongLib.fromInt(1000000000), + LongEmul fullnum = LongLib.add(LongLib.mul(LongLib.fromInt(1000000000), LongLib.fromInt(top)), LongLib.fromInt(bottom)); assertEquals("922337201967490662", LongLib.toString(fullnum)); assertEquals("-922337201967490662", LongLib.toString(LongLib.neg(fullnum))); } - private double[] fact(double[] n) { + private LongEmul fact(LongEmul n) { if (LongLib.eq(n, LongLib.fromInt(0))) { return LongLib.fromInt(1); } else { @@ -325,19 +477,18 @@ } } - private double[] longFromBits(int top, int bottom) { - double[] topHalf = LongLib.shl(LongLib.fromInt(top), 32); - double[] bottomHalf = LongLib.fromInt(bottom); + private LongEmul longFromBits(int top, int bottom) { + LongEmul topHalf = LongLib.shl(LongLib.fromInt(top), 32); + LongEmul bottomHalf = LongLib.fromInt(bottom); if (LongLib.lt(bottomHalf, Const.ZERO)) { bottomHalf = LongLib.add(bottomHalf, LongLib.shl(LongLib.fromInt(1), 32)); } - double[] total = LongLib.add(topHalf, bottomHalf); + LongEmul total = LongLib.add(topHalf, bottomHalf); return total; } - private String toHexString(double[] x) { - // copied from the GWT Long class and modified for double[] - double[] zero = LongLib.fromInt(0); + private String toHexString(LongEmul x) { + LongEmul zero = LongLib.fromInt(0); if (LongLib.eq(x, zero)) { return "0";
diff --git a/tools/api-checker/config/gwt20_21userApi.conf b/tools/api-checker/config/gwt20_21userApi.conf index 1959dcd..43801d2 100644 --- a/tools/api-checker/config/gwt20_21userApi.conf +++ b/tools/api-checker/config/gwt20_21userApi.conf
@@ -109,3 +109,32 @@ # Removing HTTPRequest. com.google.gwt.user.client.HTTPRequest MISSING + +# Change signature for native long from double[2] to LongEmul{l=int,m=int,h=int} +com.google.gwt.lang.LongLib::RUN_IN_JVM MISSING +com.google.gwt.lang.LongLib::add([D[D) MISSING +com.google.gwt.lang.LongLib::and([D[D) MISSING +com.google.gwt.lang.LongLib::compare([D[D) MISSING +com.google.gwt.lang.LongLib::div([D[D) MISSING +com.google.gwt.lang.LongLib::eq([D[D) MISSING +com.google.gwt.lang.LongLib::fromDouble(D) RETURN_TYPE_ERROR from double[] to java.lang.Object +com.google.gwt.lang.LongLib::fromInt(I) RETURN_TYPE_ERROR from double[] to java.lang.Object +com.google.gwt.lang.LongLib::gt([D[D) MISSING +com.google.gwt.lang.LongLib::gte([D[D) MISSING +com.google.gwt.lang.LongLib::lt([D[D) MISSING +com.google.gwt.lang.LongLib::lte([D[D) MISSING +com.google.gwt.lang.LongLib::mod([D[D) MISSING +com.google.gwt.lang.LongLib::mul([D[D) MISSING +com.google.gwt.lang.LongLib::neg([D) MISSING +com.google.gwt.lang.LongLib::neq([D[D) MISSING +com.google.gwt.lang.LongLib::not([D) MISSING +com.google.gwt.lang.LongLib::or([D[D) MISSING +com.google.gwt.lang.LongLib::shl([DI) MISSING +com.google.gwt.lang.LongLib::shr([DI) MISSING +com.google.gwt.lang.LongLib::shru([DI) MISSING +com.google.gwt.lang.LongLib::sub([D[D) MISSING +com.google.gwt.lang.LongLib::toDouble([D) MISSING +com.google.gwt.lang.LongLib::toInt([D) MISSING +com.google.gwt.lang.LongLib::toString([D) MISSING +com.google.gwt.lang.LongLib::typeChange(J) MISSING +com.google.gwt.lang.LongLib::xor([D[D) MISSING
diff --git a/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamReader.java b/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamReader.java index 83586a0..39e61eb 100644 --- a/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamReader.java +++ b/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamReader.java
@@ -65,6 +65,7 @@ @UnsafeNativeLong private static native long readLong0(JavaScriptObject obj, int idx) /*-{ + // TODO (rice): use backwards-compatible wire format? return obj[idx]; }-*/;
diff --git a/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamWriter.java b/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamWriter.java index 83c69ee..2085fbc 100644 --- a/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamWriter.java +++ b/user/src/com/google/gwt/rpc/client/impl/CommandClientSerializationStreamWriter.java
@@ -197,8 +197,7 @@ value.valueOf && (value = value.valueOf()); // See if the value is our web-mode representation of a long - if (!value.@java.lang.Object::typeMarker && value.length && - value.length == 2 && (typeof value[0] == 'number') && (typeof value[1] == 'number')) { + if (value.hasOwnProperty('l') && value.hasOwnProperty('m') && value.hasOwnProperty('h')) { type = 'long'; } }
diff --git a/user/src/com/google/gwt/rpc/server/WebModePayloadSink.java b/user/src/com/google/gwt/rpc/server/WebModePayloadSink.java index e8b0d20..5519572 100644 --- a/user/src/com/google/gwt/rpc/server/WebModePayloadSink.java +++ b/user/src/com/google/gwt/rpc/server/WebModePayloadSink.java
@@ -43,7 +43,6 @@ import com.google.gwt.user.client.rpc.IncompatibleRemoteServiceException; import com.google.gwt.user.client.rpc.SerializationException; import com.google.gwt.user.client.rpc.SerializationStreamReader; -import com.google.gwt.user.client.rpc.impl.AbstractSerializationStreamWriter; import java.io.IOException; import java.io.OutputStream; @@ -167,21 +166,21 @@ @Override public void endVisit(LongValueCommand x, Context ctx) { + // TODO (rice): use backwards-compatible wire format? long fieldValue = x.getValue(); - + /* - * Client code represents longs internally as an array of two Numbers. In - * order to make serialization of longs faster, we'll send the component - * parts so that the value can be directly reconstituted on the client. + * Client code represents longs internally as an Object with numeric + * properties l, m, and h. In order to make serialization of longs faster, + * we'll send the component parts so that the value can be directly + * reconstituted on the client. */ - double[] parts = AbstractSerializationStreamWriter.makeLongComponents( - (int) (fieldValue >> 32), (int) fieldValue); - assert parts.length == 2; - lbracket(); - push(String.valueOf(parts[0])); - comma(); - push(String.valueOf(parts[1])); - rbracket(); + int l = (int) (fieldValue & 0x3fffff); + int m = (int) ((fieldValue >> 22) & 0x3fffff); + int h = (int) ((fieldValue >> 44) & 0xfffff); + // CHECKSTYLE_OFF + push("{l:" + l + ",m:" + m + ",h:" + h + "}"); + // CHECKSTYLE_ON } @Override
diff --git a/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamReader.java b/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamReader.java index 2ed7015..3766b5d 100644 --- a/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamReader.java +++ b/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamReader.java
@@ -27,6 +27,59 @@ */ public abstract class AbstractSerializationStreamReader extends AbstractSerializationStream implements SerializationStreamReader { + + private static final double TWO_PWR_15_DBL = 0x8000; + private static final double TWO_PWR_16_DBL = 0x10000; + private static final double TWO_PWR_22_DBL = 0x400000; + private static final double TWO_PWR_31_DBL = TWO_PWR_16_DBL * TWO_PWR_15_DBL; + private static final double TWO_PWR_32_DBL = TWO_PWR_16_DBL * TWO_PWR_16_DBL; + private static final double TWO_PWR_44_DBL = TWO_PWR_22_DBL * TWO_PWR_22_DBL; + private static final double TWO_PWR_63_DBL = TWO_PWR_32_DBL * TWO_PWR_31_DBL; + + /** + * Return a long from a pair of doubles { low, high } such that the + * actual value is equal to high + low. + */ + public static long fromDoubles(double lowDouble, double highDouble) { + long high = fromDouble(highDouble); + long low = fromDouble(lowDouble); + return high + low; + } + + private static long fromDouble(double value) { + if (Double.isNaN(value)) { + return 0L; + } + if (value < -TWO_PWR_63_DBL) { + return Long.MIN_VALUE; + } + if (value >= TWO_PWR_63_DBL) { + return Long.MAX_VALUE; + } + + boolean negative = false; + if (value < 0) { + negative = true; + value = -value; + } + int a2 = 0; + if (value >= TWO_PWR_44_DBL) { + a2 = (int) (value / TWO_PWR_44_DBL); + value -= a2 * TWO_PWR_44_DBL; + } + int a1 = 0; + if (value >= TWO_PWR_22_DBL) { + a1 = (int) (value / TWO_PWR_22_DBL); + value -= a1 * TWO_PWR_22_DBL; + } + int a0 = (int) value; + + long result = ((long) a2 << 44) | ((long) a1 << 22) | a0; + if (negative) { + result = -result; + } + return result; + } private ArrayList<Object> seenArray = new ArrayList<Object>(); @@ -96,5 +149,4 @@ // index is 1-based return seenArray.size(); } - }
diff --git a/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamWriter.java b/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamWriter.java index 52e75e4..b245553 100644 --- a/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamWriter.java +++ b/user/src/com/google/gwt/user/client/rpc/impl/AbstractSerializationStreamWriter.java
@@ -33,22 +33,17 @@ public abstract class AbstractSerializationStreamWriter extends AbstractSerializationStream implements SerializationStreamWriter { - // Keep synchronized with LongLib private static final double TWO_PWR_16_DBL = 0x10000; - - // Keep synchronized with LongLib private static final double TWO_PWR_32_DBL = TWO_PWR_16_DBL * TWO_PWR_16_DBL; /** - * Make an instance equivalent to stringing highBits next to lowBits, where - * highBits and lowBits are assumed to be in 32-bit twos-complement notation. - * As a result, for any double[] l, the following identity holds: - * - * <blockquote> <code>l == makeFromBits(l.highBits(), l.lowBits())</code> - * </blockquote> + * Return a pair of doubles { low, high } that add up to the given number, + * such that "low" is always between 0 and 2^32-1 inclusive and "high" is + * always between -2^63 and 2^63-2^32 inclusive and is a multiple of 2^32. */ - // Keep synchronized with LongLib - public static double[] makeLongComponents(int highBits, int lowBits) { + public static double[] getAsDoubleArray(long value) { + int lowBits = (int) (value & 0xffffffff); + int highBits = (int) (value >> 32); double high = highBits * TWO_PWR_32_DBL; double low = lowBits; if (lowBits < 0) { @@ -211,5 +206,4 @@ */ protected abstract void serialize(Object instance, String typeSignature) throws SerializationException; - }
diff --git a/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamReader.java b/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamReader.java index 748f4b3..f1bb0e1 100644 --- a/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamReader.java +++ b/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamReader.java
@@ -17,7 +17,6 @@ import com.google.gwt.core.client.GWT; import com.google.gwt.core.client.JavaScriptObject; -import com.google.gwt.core.client.UnsafeNativeLong; import com.google.gwt.user.client.rpc.IncompatibleRemoteServiceException; import com.google.gwt.user.client.rpc.SerializationException; @@ -35,11 +34,6 @@ return array.length; }-*/; - @UnsafeNativeLong - private static native long readLong0(double low, double high) /*-{ - return [low, high]; - }-*/; - int index; JavaScriptObject results; @@ -92,10 +86,12 @@ }-*/; public long readLong() { + double low = readDouble(); + double high = readDouble(); if (GWT.isScript()) { - return readLong0(readDouble(), readDouble()); + return fromDoubles(low, high); } else { - return (long) readDouble() + (long) readDouble(); + return (long) low + (long) high; } }
diff --git a/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamWriter.java b/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamWriter.java index 291e877..584d695 100644 --- a/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamWriter.java +++ b/user/src/com/google/gwt/user/client/rpc/impl/ClientSerializationStreamWriter.java
@@ -15,9 +15,7 @@ */ package com.google.gwt.user.client.rpc.impl; -import com.google.gwt.core.client.GWT; import com.google.gwt.core.client.JavaScriptObject; -import com.google.gwt.core.client.UnsafeNativeLong; import com.google.gwt.user.client.rpc.SerializationException; import java.util.List; @@ -102,12 +100,6 @@ } }-*/; - @UnsafeNativeLong - // Keep synchronized with LongLib - private static native double[] makeLongComponents0(long value) /*-{ - return value; - }-*/; - private StringBuffer encodeBuffer; private final String moduleBaseURL; @@ -157,18 +149,9 @@ @Override public void writeLong(long fieldValue) { - /* - * Client code represents longs internally as an array of two Numbers. In - * order to make serialization of longs faster, we'll send the component - * parts so that the value can be directly reconstituted on the server. - */ - double[] parts; - if (GWT.isScript()) { - parts = makeLongComponents0(fieldValue); - } else { - parts = makeLongComponents((int) (fieldValue >> 32), (int) fieldValue); - } - assert parts.length == 2; + // Write longs as a pair of doubles for backwards compatibility + double[] parts = getAsDoubleArray(fieldValue); + assert parts != null && parts.length == 2; writeDouble(parts[0]); writeDouble(parts[1]); }
diff --git a/user/src/com/google/gwt/user/server/rpc/impl/ServerSerializationStreamWriter.java b/user/src/com/google/gwt/user/server/rpc/impl/ServerSerializationStreamWriter.java index 7bba2cb..3c21899 100644 --- a/user/src/com/google/gwt/user/server/rpc/impl/ServerSerializationStreamWriter.java +++ b/user/src/com/google/gwt/user/server/rpc/impl/ServerSerializationStreamWriter.java
@@ -555,16 +555,11 @@ return stream.toString(); } - + public void writeLong(long fieldValue) { - /* - * Client code represents longs internally as an array of two Numbers. In - * order to make serialization of longs faster, we'll send the component - * parts so that the value can be directly reconstituted on the client. - */ - double[] parts = makeLongComponents((int) (fieldValue >> 32), - (int) fieldValue); - assert parts.length == 2; + // Write longs as a pair of doubles for backwards compatibility + double[] parts = getAsDoubleArray(fieldValue); + assert parts != null && parts.length == 2; writeDouble(parts[0]); writeDouble(parts[1]); }
diff --git a/user/super/com/google/gwt/emul/java/lang/Integer.java b/user/super/com/google/gwt/emul/java/lang/Integer.java index aa4ed50..6a44ab6 100644 --- a/user/super/com/google/gwt/emul/java/lang/Integer.java +++ b/user/super/com/google/gwt/emul/java/lang/Integer.java
@@ -88,12 +88,37 @@ } public static int numberOfLeadingZeros(int i) { + // Based on Henry S. Warren, Jr: "Hacker's Delight", p. 80. if (i < 0) { return 0; } else if (i == 0) { return SIZE; } else { - return SIZE - 1 - (int) Math.floor(Math.log(i) / Math.log(2.0d)); + int y, m, n; + + y = -(i >> 16); + m = (y >> 16) & 16; + n = 16 - m; + i = i >> m; + + y = i - 0x100; + m = (y >> 16) & 8; + n += m; + i <<= m; + + y = i - 0x1000; + m = (y >> 16) & 4; + n += m; + i <<= m; + + y = i - 0x4000; + m = (y >> 16) & 2; + n += m; + i <<= m; + + y = i >> 14; + m = y & ~(y >> 1); + return n + 2 - m; } }
diff --git a/user/super/com/google/gwt/emul/java/lang/Long.java b/user/super/com/google/gwt/emul/java/lang/Long.java index 913fab7..0971d94 100644 --- a/user/super/com/google/gwt/emul/java/lang/Long.java +++ b/user/super/com/google/gwt/emul/java/lang/Long.java
@@ -103,62 +103,11 @@ public static long parseLong(String s) throws NumberFormatException { return parseLong(s, 10); } - - public static long parseLong(String orig, int intRadix) - throws NumberFormatException { - if (orig == null) { - throw new NumberFormatException("null"); - } - if (orig.length() == 0) { - throw NumberFormatException.forInputString(orig); - } - - if (intRadix < Character.MIN_RADIX || intRadix > Character.MAX_RADIX) { - throw new NumberFormatException("radix " + intRadix + " out of range"); - } - - boolean neg = false; - String s; - if (orig.charAt(0) == '-') { - neg = true; - s = orig.substring(1); - if (s.equals("")) { // orig = "-" - throw NumberFormatException.forInputString(orig); - } - } else { - s = orig; - } - - long result = 0; - if (intRadix == 16) { - result = parseHex(s); - } else { - // Cache a converted version for performance (pure long ops are faster). - long radix = intRadix; - for (int i = 0, len = s.length(); i < len; ++i) { - if (result < 0) { - throw NumberFormatException.forInputString(s); - } - result *= radix; - char c = s.charAt(i); - int value = Character.digit(c, intRadix); - if (value < 0) { - throw NumberFormatException.forInputString(s); - } - result += value; - } - } - - if (result < 0 && result != MIN_VALUE) { - throw NumberFormatException.forInputString(s); - } - if (neg) { - return -result; - } else { - return result; - } + + public static long parseLong(String s, int radix) throws NumberFormatException { + return __parseAndValidateLong(s, radix); } - + public static long reverse(long i) { int high = (int) (i >>> 32); int low = (int) i; @@ -377,5 +326,4 @@ public String toString() { return toString(value); } - }
diff --git a/user/super/com/google/gwt/emul/java/lang/Number.java b/user/super/com/google/gwt/emul/java/lang/Number.java index 810df15..32ada57 100644 --- a/user/super/com/google/gwt/emul/java/lang/Number.java +++ b/user/super/com/google/gwt/emul/java/lang/Number.java
@@ -53,6 +53,89 @@ } /** + * Use nested class to avoid clinit on outer. + */ + static class __ParseLong { + /** + * The number of digits (excluding minus sign and leading zeros) to process + * at a time. The largest value expressible in maxDigits digits as well as + * the factor radix^maxDigits must be strictly less than 2^31. + */ + private static final int[] maxDigitsForRadix = {-1, -1, // unused + 30, // base 2 + 19, // base 3 + 15, // base 4 + 13, // base 5 + 11, 11, // base 6-7 + 10, // base 8 + 9, 9, // base 9-10 + 8, 8, 8, 8, // base 11-14 + 7, 7, 7, 7, 7, 7, 7, // base 15-21 + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // base 22-35 + 5 // base 36 + }; + + /** + * A table of values radix*maxDigitsForRadix[radix]. + */ + private static final int[] maxDigitsRadixPower = new int[37]; + + /** + * The largest number of digits (excluding minus sign and leading zeros) that + * can fit into a long for a given radix between 2 and 36, inclusive. + */ + private static final int[] maxLengthForRadix = {-1, -1, // unused + 63, // base 2 + 40, // base 3 + 32, // base 4 + 28, // base 5 + 25, // base 6 + 23, // base 7 + 21, // base 8 + 20, // base 9 + 19, // base 10 + 19, // base 11 + 18, // base 12 + 18, // base 13 + 17, // base 14 + 17, // base 15 + 16, // base 16 + 16, // base 17 + 16, // base 18 + 15, // base 19 + 15, // base 20 + 15, // base 21 + 15, // base 22 + 14, // base 23 + 14, // base 24 + 14, // base 25 + 14, // base 26 + 14, // base 27 + 14, // base 28 + 13, // base 29 + 13, // base 30 + 13, // base 31 + 13, // base 32 + 13, // base 33 + 13, // base 34 + 13, // base 35 + 13 // base 36 + }; + + /** + * A table of floor(MAX_VALUE / maxDigitsRadixPower). + */ + private static final long[] maxValueForRadix = new long[37]; + + static { + for (int i = 2; i <= 36; i++) { + maxDigitsRadixPower[i] = (int) Math.pow(i, maxDigitsForRadix[i]); + maxValueForRadix[i] = Long.MAX_VALUE / maxDigitsRadixPower[i]; + } + } + } + + /** * @skip * * This function will determine the radix that the string is expressed in @@ -111,7 +194,7 @@ return toReturn; } - + /** * @skip * @@ -146,7 +229,104 @@ return toReturn; } + + /** + * @skip + * + * This function contains common logic for parsing a String in a given radix + * and validating the result. + */ + protected static long __parseAndValidateLong(String s, int radix) + throws NumberFormatException { + + if (s == null) { + throw new NumberFormatException("null"); + } + if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { + throw new NumberFormatException("radix " + radix + " out of range"); + } + int length = s.length(); + boolean negative = (length > 0) && (s.charAt(0) == '-'); + if (negative) { + s = s.substring(1); + length--; + } + if (length == 0) { + throw NumberFormatException.forInputString(s); + } + + // Strip leading zeros + while (s.length() > 0 && s.charAt(0) == '0') { + s = s.substring(1); + length--; + } + + // Immediately eject numbers that are too long -- this avoids more complex + // overflow handling below + if (length > __ParseLong.maxLengthForRadix[radix]) { + throw NumberFormatException.forInputString(s); + } + + // Validate the digits + int maxNumericDigit = '0' + Math.min(radix, 10); + int maxLowerCaseDigit = radix + 'a' - 10; + int maxUpperCaseDigit = radix + 'A' - 10; + for (int i = 0; i < length; i++) { + char c = s.charAt(i); + if (c >= '0' && c < maxNumericDigit) { + continue; + } + if (c >= 'a' && c < maxLowerCaseDigit) { + continue; + } + if (c >= 'A' && c < maxUpperCaseDigit) { + continue; + } + throw NumberFormatException.forInputString(s); + } + + long toReturn = 0; + int maxDigits = __ParseLong.maxDigitsForRadix[radix]; + long radixPower = __ParseLong.maxDigitsRadixPower[radix]; + long maxValue = __ParseLong.maxValueForRadix[radix]; + + boolean firstTime = true; + int head = length % maxDigits; + if (head > 0) { + toReturn = __parseInt(s.substring(0, head), radix); + s = s.substring(head); + length -= head; + firstTime = false; + } + + while (length >= maxDigits) { + head = __parseInt(s.substring(0, maxDigits), radix); + s = s.substring(maxDigits); + length -= maxDigits; + if (!firstTime) { + // Check whether multiplying by radixPower will overflow + if (toReturn > maxValue) { + throw new NumberFormatException(s); + } + toReturn *= radixPower; + } else { + firstTime = false; + } + toReturn += head; + } + + // A negative value means we overflowed Long.MAX_VALUE + if (toReturn < 0) { + throw NumberFormatException.forInputString(s); + } + + if (negative) { + toReturn = -toReturn; + } + return toReturn; + } + /** * @skip */
diff --git a/user/super/com/google/gwt/emul/java/util/Arrays.java b/user/super/com/google/gwt/emul/java/util/Arrays.java index 89dcc33..662a202 100644 --- a/user/super/com/google/gwt/emul/java/util/Arrays.java +++ b/user/super/com/google/gwt/emul/java/util/Arrays.java
@@ -1345,7 +1345,7 @@ */ @UnsafeNativeLong private static native void nativeLongSort(Object array) /*-{ - array.sort(@com.google.gwt.lang.LongLib::compare([D[D)); + array.sort(@com.google.gwt.lang.LongLib::compare(Lcom/google/gwt/lang/LongEmul;Lcom/google/gwt/lang/LongEmul;)); }-*/; /** @@ -1355,7 +1355,7 @@ private static native void nativeLongSort(Object array, int fromIndex, int toIndex) /*-{ var temp = array.slice(fromIndex, toIndex); - temp.sort(@com.google.gwt.lang.LongLib::compare([D[D)); + temp.sort(@com.google.gwt.lang.LongLib::compare(Lcom/google/gwt/lang/LongEmul;Lcom/google/gwt/lang/LongEmul;)); var n = toIndex - fromIndex; // Do the equivalent of array.splice(fromIndex, n, temp) except // flattening the temp slice.
diff --git a/user/test/com/google/gwt/langtest/LongLibGwtTest.java b/user/test/com/google/gwt/langtest/LongLibGwtTest.java index 66225de..1c6e4b6 100644 --- a/user/test/com/google/gwt/langtest/LongLibGwtTest.java +++ b/user/test/com/google/gwt/langtest/LongLibGwtTest.java
@@ -15,9 +15,7 @@ */ package com.google.gwt.langtest; -import com.google.gwt.core.client.GWT; import com.google.gwt.junit.client.GWTTestCase; -import com.google.gwt.lang.LongLib; import com.google.gwt.lang.LongLibTestBase; /** @@ -25,12 +23,6 @@ */ public class LongLibGwtTest extends GWTTestCase { - static { - if (!GWT.isScript()) { - LongLib.RUN_IN_JVM = true; - } - } - private LongLibTestBase impl = new LongLibTestBase(); @Override @@ -70,6 +62,10 @@ impl.testMinMax(); } + public void testMod() { + impl.testMod(); + } + public void testMultiplicative() { impl.testMultiplicative(); }
diff --git a/user/test/com/google/gwt/user/client/rpc/TestSetFactory.java b/user/test/com/google/gwt/user/client/rpc/TestSetFactory.java index 9ae14ed..4831bfd 100644 --- a/user/test/com/google/gwt/user/client/rpc/TestSetFactory.java +++ b/user/test/com/google/gwt/user/client/rpc/TestSetFactory.java
@@ -493,9 +493,21 @@ } public static Long[] createLongArray() { + long a = 16123432898849345L; + long b = 78234569989880099L; + long c = -64289238928934943L; + + // Create values that are not compile-time constants + for (int i = 0; i < 10; i++) { + a ^= b; + b ^= c; + c ^= a; + } + return new Long[] { new Long(Long.MAX_VALUE), new Long(Long.MIN_VALUE), - new Long(Long.MAX_VALUE), new Long(Long.MIN_VALUE)}; + new Long(Long.MAX_VALUE), new Long(Long.MIN_VALUE), + new Long(a), new Long(b), new Long(c)}; } public static LinkedHashMap<String, MarkerTypeLinkedHashMap> createLRULinkedHashMap() { @@ -541,8 +553,20 @@ } public static long[] createPrimitiveLongArray() { + long a = 16123432898849345L; + long b = 78234569989880099L; + long c = -64289238928934943L; + + // Create values that are not compile-time constants + for (int i = 0; i < 10; i++) { + a ^= b; + b ^= c; + c ^= a; + } + return new long[] { - Long.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE}; + Long.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE, + a, b, c}; } public static short[] createPrimitiveShortArray() {