| /* |
| * 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; |
| |
| /** |
| * Implements a Java <code>long</code> in a way that can be translated to |
| * JavaScript. |
| */ |
| class BigLongLibBase { |
| |
| /* |
| * 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 Production Mode, any place it uses a |
| * long is not usable in Production Mode. There is currently one such method: |
| * {@link LongLib#getAsLongArray}. |
| */ |
| static class BigLong { |
| int l, m, h; |
| } |
| |
| |
| // Note that the {@link LonghLib#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 BigLong remainder; |
| |
| 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; |
| |
| protected static BigLong create(int value) { |
| int a0 = value & MASK; |
| int a1 = (value >> BITS) & MASK; |
| int a2 = (value < 0) ? MASK_2 : 0; |
| |
| if (LongLib.RUN_IN_JVM) { |
| BigLong a = new BigLong(); |
| a.l = a0; |
| a.m = a1; |
| a.h = a2; |
| return a; |
| } |
| return create0(a0, a1, a2); |
| } |
| |
| protected static BigLong create(int a0, int a1, int a2) { |
| if (LongLib.RUN_IN_JVM) { |
| BigLong a = new BigLong(); |
| a.l = a0; |
| a.m = a1; |
| a.h = a2; |
| return a; |
| } |
| return create0(a0, a1, a2); |
| } |
| |
| protected static BigLong divMod(BigLong a, BigLong 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 = BigLongLib.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(BigLongLib.Const.MAX_VALUE); |
| aIsCopy = true; |
| negative = !negative; |
| } else { |
| // Signed shift of MIN_VALUE produces the right answer |
| BigLong c = BigLongLib.shr(a, bpower); |
| if (negative) { |
| negate(c); |
| } |
| if (computeRemainder) { |
| remainder = create(); // zero |
| } |
| return c; |
| } |
| } else if (isNegative(a)) { |
| aIsNegative = true; |
| a = BigLongLib.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 (BigLongLib.compare(a, b) < 0) { |
| if (computeRemainder) { |
| if (aIsNegative) { |
| remainder = BigLongLib.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(BigLong a) { |
| if (LongLib.RUN_IN_JVM) { |
| return a.h; |
| } |
| return getHNative(a); |
| } |
| |
| protected static int getL(BigLong a) { |
| if (LongLib.RUN_IN_JVM) { |
| return a.l; |
| } |
| return getLNative(a); |
| } |
| |
| protected static int getM(BigLong a) { |
| if (LongLib.RUN_IN_JVM) { |
| return a.m; |
| } |
| return getMNative(a); |
| } |
| |
| protected static boolean isMinValue(BigLong a) { |
| return getH(a) == SIGN_BIT_VALUE && getM(a) == 0 && getL(a) == 0; |
| } |
| |
| protected static boolean isNegative(BigLong a) { |
| return sign(a) != 0; |
| } |
| |
| protected static boolean isZero(BigLong a) { |
| return getL(a) == 0 && getM(a) == 0 && getH(a) == 0; |
| } |
| |
| /** |
| * a = -a |
| */ |
| protected static void negate(BigLong 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 (LongLib.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(BigLong a) { |
| return getH(a) >> (BITS2 - 1); |
| } |
| |
| // Assumes a is non-negative |
| protected static double toDoubleHelper(BigLong a) { |
| return getL(a) + (getM(a) * TWO_PWR_22_DBL) + (getH(a) * TWO_PWR_44_DBL); |
| } |
| |
| /** |
| * Return the number of leading zeros of a long value. |
| */ |
| // package-private for testing |
| static int numberOfLeadingZeros(BigLong a) { |
| int b2 = Integer.numberOfLeadingZeros(getH(a)); |
| if (b2 == 32) { |
| int b1 = Integer.numberOfLeadingZeros(getM(a)); |
| if (b1 == 32) { |
| return Integer.numberOfLeadingZeros(getL(a)) + 32; |
| } else { |
| return b1 + BITS2 - (32 - BITS); |
| } |
| } else { |
| return b2 - (32 - BITS2); |
| } |
| } |
| |
| /** |
| * Creates a long instance equal to 0. |
| */ |
| private static BigLong create() { |
| if (LongLib.RUN_IN_JVM) { |
| return new BigLong(); |
| } |
| return create0(0, 0, 0); |
| } |
| |
| /** |
| * Creates a long instance equal to a given long. |
| */ |
| static BigLong create(BigLong a) { |
| if (LongLib.RUN_IN_JVM) { |
| BigLong b = new BigLong(); |
| 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 BigLong create0(int l, int m, int h) /*-{ |
| return {l:l,m:m,h:h}; |
| }-*/; |
| |
| private static BigLong divModByMinValue(BigLong 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(BigLongLib.Const.ONE); |
| } |
| if (computeRemainder) { |
| remainder = create(a); |
| } |
| return create(); // zero |
| } |
| |
| private static BigLong divModByShift(BigLong a, int bpower, |
| boolean negative, boolean aIsNegative, boolean computeRemainder) { |
| BigLong c = BigLongLib.shr(a, bpower); |
| if (negative) { |
| negate(c); |
| } |
| |
| if (computeRemainder) { |
| a = maskRight(a, bpower); |
| if (aIsNegative) { |
| remainder = BigLongLib.neg(a); |
| } else { |
| remainder = create(a); |
| } |
| } |
| return c; |
| } |
| |
| private static BigLong divModHelper(BigLong a, BigLong 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); |
| BigLong bshift = BigLongLib.shl(b, shift); |
| |
| BigLong 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 = BigLongLib.neg(a); |
| if (aIsMinValue) { |
| remainder = BigLongLib.sub(remainder, BigLongLib.Const.ONE); |
| } |
| } else { |
| remainder = create(a); |
| } |
| } |
| |
| return quotient; |
| } |
| |
| private static native int getHNative(BigLong a) /*-{ |
| return a.h; |
| }-*/; |
| |
| private static native int getLNative(BigLong a) /*-{ |
| return a.l; |
| }-*/; |
| |
| private static native int getMNative(BigLong a) /*-{ |
| return a.m; |
| }-*/; |
| |
| /** |
| * a &= ((1L << bits) - 1) |
| */ |
| private static BigLong maskRight(BigLong 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 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(BigLong 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(BigLong a, int bit) { |
| if (LongLib.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(BigLong a, int bit) /*-{ |
| a.h |= 1 << bit; |
| }-*/; |
| |
| private static native void setBitL(BigLong a, int bit) /*-{ |
| a.l |= 1 << bit; |
| }-*/; |
| |
| private static native void setBitM(BigLong a, int bit) /*-{ |
| a.m |= 1 << bit; |
| }-*/; |
| |
| private static native void setH(BigLong a, int x) /*-{ |
| a.h = x; |
| }-*/; |
| |
| private static native void setL(BigLong a, int x) /*-{ |
| a.l = x; |
| }-*/; |
| |
| private static native void setM(BigLong a, int x) /*-{ |
| a.m = x; |
| }-*/; |
| |
| /** |
| * a >>= 1. Assumes a >= 0. |
| */ |
| private static void toShru1(BigLong a) { |
| int a1 = getM(a); |
| int a2 = getH(a); |
| int a0 = getL(a); |
| |
| if (LongLib.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(BigLong a, BigLong 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 (LongLib.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. |
| */ |
| BigLongLibBase() { |
| } |
| } |