jdk-sandbox: comparison jdk/src/share/classes/java/math/BigInteger.java

equal deleted inserted replaced

-:d9d491a5a169
+:dd6d609861f0
 * a signum of 0.  This is necessary to ensures that there is exactly one
 * representation for each BigInteger value.
 *
 * @serial
 */
-int signum;
+final int signum;
 /**
 * The magnitude of this BigInteger, in <i>big-endian</i> order: the
 * zeroth element of this array is the most-significant int of the
 * magnitude.  The magnitude must be "minimal" in that the most-significant
 * int ({@code mag[0]}) must be non-zero.  This is necessary to
 * ensure that there is exactly one representation for each BigInteger
 * value.  Note that this implies that the BigInteger zero has a
 * zero-length mag array.
 */
-int[] mag;
+final int[] mag;
 // These "redundant fields" are initialized with recognizable nonsense
 // values, and cached the first time they are needed (or never, if they
 // aren't needed).
 /**
-* The bitCount of this BigInteger, as returned by bitCount(), or -1
+* One plus the bitCount of this BigInteger. Zeros means unitialized.
-* (either value is acceptable).
 *
 * @serial
 * @see #bitCount
-*/
+* @deprecated Deprecated since logical value is offset from stored
-private int bitCount =  -1;
+* value and correction factor is applied in accessor method.
+*/
-/**
+@Deprecated
-* The bitLength of this BigInteger, as returned by bitLength(), or -1
+private int bitCount;
+/**
+* One plus the bitLength of this BigInteger. Zeros means unitialized.
 * (either value is acceptable).
 *
 * @serial
 * @see #bitLength()
-*/
+* @deprecated Deprecated since logical value is offset from stored
-private int bitLength = -1;
+* value and correction factor is applied in accessor method.
+*/
-/**
+@Deprecated
-* The lowest set bit of this BigInteger, as returned by getLowestSetBit(),
+private int bitLength;
-* or -2 (either value is acceptable).
+/**
+* Two plus the lowest set bit of this BigInteger, as returned by
+* getLowestSetBit().
 *
 * @serial
 * @see #getLowestSetBit
-*/
+* @deprecated Deprecated since logical value is offset from stored
-private int lowestSetBit = -2;
+* value and correction factor is applied in accessor method.
+*/
-/**
+@Deprecated
-* The index of the lowest-order byte in the magnitude of this BigInteger
+private int lowestSetBit;
-* that contains a nonzero byte, or -2 (either value is acceptable).  The
-* least significant byte has int-number 0, the next byte in order of
+/**
-* increasing significance has byte-number 1, and so forth.
+* Two plus the index of the lowest-order int in the magnitude of this
-*
+* BigInteger that contains a nonzero int, or -2 (either value is acceptable).
-* @serial
+* The least significant int has int-number 0, the next int in order of
-*/
-private int firstNonzeroByteNum = -2;
-/**
-* The index of the lowest-order int in the magnitude of this BigInteger
-* that contains a nonzero int, or -2 (either value is acceptable).  The
-* least significant int has int-number 0, the next int in order of
 * increasing significance has int-number 1, and so forth.
-*/
+* @deprecated Deprecated since logical value is offset from stored
-private int firstNonzeroIntNum = -2;
+* value and correction factor is applied in accessor method.
+*/
+@Deprecated
+private int firstNonzeroIntNum;
 /**
 * This mask is used to obtain the value of an int as if it were unsigned.
 */
-private final static long LONG_MASK = 0xffffffffL;
+final static long LONG_MASK = 0xffffffffL;
 //Constructors
 /**
 * Translates a byte array containing the two's-complement binary
 throw new NumberFormatException("Radix out of range");
 if (val.length() == 0)
 throw new NumberFormatException("Zero length BigInteger");
 // Check for at most one leading sign
-signum = 1;
+int sign = 1;
 int index1 = val.lastIndexOf('-');
 int index2 = val.lastIndexOf('+');
 if ((index1 + index2) <= -1) {
 // No leading sign character or at most one leading sign character
 if (index1 == 0 || index2 == 0) {
 cursor = 1;
 if (val.length() == 1)
 throw new NumberFormatException("Zero length BigInteger");
 }
 if (index1 == 0)
-signum = -1;
+sign = -1;
 } else
 throw new NumberFormatException("Illegal embedded sign character");
 // Skip leading zeros and compute number of digits in magnitude
 while (cursor < len &&
 cursor++;
 if (cursor == len) {
 signum = 0;
 mag = ZERO.mag;
 return;
-} else {
+}
-numDigits = len - cursor;
-}
+numDigits = len - cursor;
+signum = sign;
 // Pre-allocate array of expected size. May be too large but can
 // never be too small. Typically exact.
 int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1);
-int numWords = (numBits + 31) /32;
+int numWords = (numBits + 31) >>> 5;
-mag = new int[numWords];
+int[] magnitude = new int[numWords];
 // Process first (potentially short) digit group
 int firstGroupLen = numDigits % digitsPerInt[radix];
 if (firstGroupLen == 0)
 firstGroupLen = digitsPerInt[radix];
 String group = val.substring(cursor, cursor += firstGroupLen);
-mag[mag.length - 1] = Integer.parseInt(group, radix);
+magnitude[numWords - 1] = Integer.parseInt(group, radix);
-if (mag[mag.length - 1] < 0)
+if (magnitude[numWords - 1] < 0)
 throw new NumberFormatException("Illegal digit");
 // Process remaining digit groups
 int superRadix = intRadix[radix];
 int groupVal = 0;
 while (cursor < val.length()) {
 group = val.substring(cursor, cursor += digitsPerInt[radix]);
 groupVal = Integer.parseInt(group, radix);
 if (groupVal < 0)
 throw new NumberFormatException("Illegal digit");
-destructiveMulAdd(mag, superRadix, groupVal);
+destructiveMulAdd(magnitude, superRadix, groupVal);
 }
 // Required for cases where the array was overallocated.
-mag = trustedStripLeadingZeroInts(mag);
+mag = trustedStripLeadingZeroInts(magnitude);
 }
 // Constructs a new BigInteger using a char array with radix=10
 BigInteger(char[] val) {
 int cursor = 0, numDigits;
 int len = val.length;
 // Check for leading minus sign
-signum = 1;
+int sign = 1;
 if (val[0] == '-') {
 if (len == 1)
 throw new NumberFormatException("Zero length BigInteger");
-signum = -1;
+sign = -1;
 cursor = 1;
 } else if (val[0] == '+') {
 if (len == 1)
 throw new NumberFormatException("Zero length BigInteger");
 cursor = 1;
 cursor++;
 if (cursor == len) {
 signum = 0;
 mag = ZERO.mag;
 return;
-} else {
+}
-numDigits = len - cursor;
-}
+numDigits = len - cursor;
+signum = sign;
 // Pre-allocate array of expected size
 int numWords;
 if (len < 10) {
 numWords = 1;
 } else {
 int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);
-numWords = (numBits + 31) /32;
+numWords = (numBits + 31) >>> 5;
 }
-mag = new int[numWords];
+int[] magnitude = new int[numWords];
 // Process first (potentially short) digit group
 int firstGroupLen = numDigits % digitsPerInt[10];
 if (firstGroupLen == 0)
 firstGroupLen = digitsPerInt[10];
-mag[mag.length-1] = parseInt(val, cursor,  cursor += firstGroupLen);
+magnitude[numWords - 1] = parseInt(val, cursor,  cursor += firstGroupLen);
 // Process remaining digit groups
 while (cursor < len) {
 int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
-destructiveMulAdd(mag, intRadix[10], groupVal);
+destructiveMulAdd(magnitude, intRadix[10], groupVal);
 }
-mag = trustedStripLeadingZeroInts(mag);
+mag = trustedStripLeadingZeroInts(magnitude);
 }
 // Create an integer with the digits between the two indexes
 // Assumes start < end. The result may be negative, but it
 // is to be treated as an unsigned value.
 for (int i=k.bitLength()-2; i>=0; i--) {
 u2 = u.multiply(v).mod(n);
 v2 = v.square().add(d.multiply(u.square())).mod(n);
-if (v2.testBit(0)) {
+if (v2.testBit(0))
-v2 = n.subtract(v2);
+v2 = v2.subtract(n);
-v2.signum = - v2.signum;
-}
 v2 = v2.shiftRight(1);
 u = u2; v = v2;
 if (k.testBit(i)) {
 u2 = u.add(v).mod(n);
-if (u2.testBit(0)) {
+if (u2.testBit(0))
-u2 = n.subtract(u2);
+u2 = u2.subtract(n);
-u2.signum = - u2.signum;
-}
 u2 = u2.shiftRight(1);
 v2 = v.add(d.multiply(u)).mod(n);
-if (v2.testBit(0)) {
+if (v2.testBit(0))
-v2 = n.subtract(v2);
+v2 = v2.subtract(n);
-v2.signum = - v2.signum;
-}
 v2 = v2.shiftRight(1);
 u = u2; v = v2;
 }
 }
 }
 return true;
 }
 /**
-* This private constructor differs from its public cousin
+* This internal constructor differs from its public cousin
 * with the arguments reversed in two ways: it assumes that its
 * arguments are correct, and it doesn't copy the magnitude array.
 */
-private BigInteger(int[] magnitude, int signum) {
+BigInteger(int[] magnitude, int signum) {
 this.signum = (magnitude.length==0 ? 0 : signum);
 this.mag = magnitude;
 }
 /**
 * arguments are correct.
 */
 private BigInteger(byte[] magnitude, int signum) {
 this.signum = (magnitude.length==0 ? 0 : signum);
 this.mag = stripLeadingZeroBytes(magnitude);
-}
-/**
-* This private constructor is for internal use in converting
-* from a MutableBigInteger object into a BigInteger.
-*/
-BigInteger(MutableBigInteger val, int sign) {
-if (val.offset > 0 || val.value.length != val.intLen) {
-mag = new int[val.intLen];
-for(int i=0; i<val.intLen; i++)
-mag[i] = val.value[val.offset+i];
-} else {
-mag = val.value;
-}
-this.signum = (val.intLen == 0) ? 0 : sign;
 }
 //Static Factory Methods
 /**
 /**
 * Constructs a BigInteger with the specified value, which may not be zero.
 */
 private BigInteger(long val) {
 if (val < 0) {
+val = -val;
 signum = -1;
-val = -val;
 } else {
 signum = 1;
 }
 int highWord = (int)(val >>> 32);
 *
 * @param  val value to be added to this BigInteger.
 * @return {@code this + val}
 */
 public BigInteger add(BigInteger val) {
-int[] resultMag;
 if (val.signum == 0)
 return this;
 if (signum == 0)
 return val;
 if (val.signum == signum)
 return new BigInteger(add(mag, val.mag), signum);
-int cmp = intArrayCmp(mag, val.mag);
+int cmp = compareMagnitude(val);
-if (cmp==0)
+if (cmp == 0)
 return ZERO;
-resultMag = (cmp>0 ? subtract(mag, val.mag)
+int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
 : subtract(val.mag, mag));
 resultMag = trustedStripLeadingZeroInts(resultMag);
-return new BigInteger(resultMag, cmp*signum);
+return new BigInteger(resultMag, cmp == signum ? 1 : -1);
 }
 /**
 * Adds the contents of the int arrays x and y. This method allocates
 * a new int array to hold the answer and returns a reference to that
 while (xIndex > 0)
 result[--xIndex] = x[xIndex];
 // Grow result if necessary
 if (carry) {
-int newLen = result.length + 1;
+int bigger[] = new int[result.length + 1];
-int temp[] = new int[newLen];
+System.arraycopy(result, 0, bigger, 1, result.length);
-for (int i = 1; i<newLen; i++)
+bigger[0] = 0x01;
-temp[i] = result[i-1];
+return bigger;
-temp[0] = 0x01;
-result = temp;
 }
 return result;
 }
 /**
 *
 * @param  val value to be subtracted from this BigInteger.
 * @return {@code this - val}
 */
 public BigInteger subtract(BigInteger val) {
-int[] resultMag;
 if (val.signum == 0)
 return this;
 if (signum == 0)
 return val.negate();
 if (val.signum != signum)
 return new BigInteger(add(mag, val.mag), signum);
-int cmp = intArrayCmp(mag, val.mag);
+int cmp = compareMagnitude(val);
-if (cmp==0)
+if (cmp == 0)
 return ZERO;
-resultMag = (cmp>0 ? subtract(mag, val.mag)
+int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
 : subtract(val.mag, mag));
 resultMag = trustedStripLeadingZeroInts(resultMag);
-return new BigInteger(resultMag, cmp*signum);
+return new BigInteger(resultMag, cmp == signum ? 1 : -1);
 }
 /**
 * Subtracts the contents of the second int arrays (little) from the
 * first (big).  The first int array (big) must represent a larger number
 return ZERO;
 int[] result = multiplyToLen(mag, mag.length,
 val.mag, val.mag.length, null);
 result = trustedStripLeadingZeroInts(result);
-return new BigInteger(result, signum*val.signum);
+return new BigInteger(result, signum == val.signum ? 1 : -1);
+}
+/**
+* Package private methods used by BigDecimal code to multiply a BigInteger
+* with a long. Assumes v is not equal to INFLATED.
+*/
+BigInteger multiply(long v) {
+if (v == 0 || signum == 0)
+return ZERO;
+if (v == BigDecimal.INFLATED)
+return multiply(BigInteger.valueOf(v));
+int rsign = (v > 0 ? signum : -signum);
+if (v < 0)
+v = -v;
+long dh = v >>> 32;      // higher order bits
+long dl = v & LONG_MASK; // lower order bits
+int xlen = mag.length;
+int[] value = mag;
+int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]);
+long carry = 0;
+int rstart = rmag.length - 1;
+for (int i = xlen - 1; i >= 0; i--) {
+long product = (value[i] & LONG_MASK) * dl + carry;
+rmag[rstart--] = (int)product;
+carry = product >>> 32;
+}
+rmag[rstart] = (int)carry;
+if (dh != 0L) {
+carry = 0;
+rstart = rmag.length - 2;
+for (int i = xlen - 1; i >= 0; i--) {
+long product = (value[i] & LONG_MASK) * dh +
+(rmag[rstart] & LONG_MASK) + carry;
+rmag[rstart--] = (int)product;
+carry = product >>> 32;
+}
+rmag[0] = (int)carry;
+}
+if (carry == 0L)
+rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
+return new BigInteger(rmag, rsign);
 }
 /**
 * Multiplies int arrays x and y to the specified lengths and places
-* the result into z.
+* the result into z. There will be no leading zeros in the resultant array.
 */
 private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
 int xstart = xlen - 1;
 int ystart = ylen - 1;
 * @return {@code this / val}
 * @throws ArithmeticException {@code val==0}
 */
 public BigInteger divide(BigInteger val) {
 MutableBigInteger q = new MutableBigInteger(),
-r = new MutableBigInteger(),
 a = new MutableBigInteger(this.mag),
 b = new MutableBigInteger(val.mag);
-a.divide(b, q, r);
+a.divide(b, q);
-return new BigInteger(q, this.signum * val.signum);
+return q.toBigInteger(this.signum == val.signum ? 1 : -1);
 }
 /**
 * Returns an array of two BigIntegers containing {@code (this / val)}
 * followed by {@code (this % val)}.
 * @throws ArithmeticException {@code val==0}
 */
 public BigInteger[] divideAndRemainder(BigInteger val) {
 BigInteger[] result = new BigInteger[2];
 MutableBigInteger q = new MutableBigInteger(),
-r = new MutableBigInteger(),
 a = new MutableBigInteger(this.mag),
 b = new MutableBigInteger(val.mag);
-a.divide(b, q, r);
+MutableBigInteger r = a.divide(b, q);
-result[0] = new BigInteger(q, this.signum * val.signum);
+result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
-result[1] = new BigInteger(r, this.signum);
+result[1] = r.toBigInteger(this.signum);
 return result;
 }
 /**
 * Returns a BigInteger whose value is {@code (this % val)}.
 * @return {@code this % val}
 * @throws ArithmeticException {@code val==0}
 */
 public BigInteger remainder(BigInteger val) {
 MutableBigInteger q = new MutableBigInteger(),
-r = new MutableBigInteger(),
 a = new MutableBigInteger(this.mag),
 b = new MutableBigInteger(val.mag);
-a.divide(b, q, r);
+return a.divide(b, q).toBigInteger(this.signum);
-return new BigInteger(r, this.signum);
 }
 /**
 * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
 * Note that {@code exponent} is an integer rather than a BigInteger.
 MutableBigInteger a = new MutableBigInteger(this);
 MutableBigInteger b = new MutableBigInteger(val);
 MutableBigInteger result = a.hybridGCD(b);
-return new BigInteger(result, 1);
+return result.toBigInteger(1);
+}
+/**
+* Package private method to return bit length for an integer.
+*/
+static int bitLengthForInt(int n) {
+return 32 - Integer.numberOfLeadingZeros(n);
 }
 /**
 * Left shift int array a up to len by n bits. Returns the array that
 * results from the shift since space may have to be reallocated.
 */
 private static int[] leftShift(int[] a, int len, int n) {
 int nInts = n >>> 5;
 int nBits = n&0x1F;
-int bitsInHighWord = bitLen(a[0]);
+int bitsInHighWord = bitLengthForInt(a[0]);
 // If shift can be done without recopy, do so
 if (n <= (32-bitsInHighWord)) {
 primitiveLeftShift(a, len, nBits);
 return a;
 /**
 * Calculate bitlength of contents of the first len elements an int array,
 * assuming there are no leading zero ints.
 */
 private static int bitLength(int[] val, int len) {
-if (len==0)
+if (len == 0)
 return 0;
-return ((len-1)<<5) + bitLen(val[0]);
+return ((len - 1) << 5) + bitLengthForInt(val[0]);
 }
 /**
 * Returns a BigInteger whose value is the absolute value of this
 * BigInteger.
 // Convert base to Montgomery form
 int[] a = leftShift(base, base.length, modLen << 5);
 MutableBigInteger q = new MutableBigInteger(),
-r = new MutableBigInteger(),
 a2 = new MutableBigInteger(a),
 b2 = new MutableBigInteger(mod);
-a2.divide(b2, q, r);
+MutableBigInteger r= a2.divide(b2, q);
 table[0] = r.toIntArray();
 // Pad table[0] with leading zeros so its length is at least modLen
 if (table[0].length < modLen) {
 int offset = modLen - table[0].length;
 private BigInteger mod2(int p) {
 if (bitLength() <= p)
 return this;
 // Copy remaining ints of mag
-int numInts = (p+31)/32;
+int numInts = (p + 31) >>> 5;
 int[] mag = new int[numInts];
 for (int i=0; i<numInts; i++)
 mag[i] = this.mag[i + (this.mag.length - numInts)];
 // Mask out any excess bits
 if (m.equals(ONE))
 return ZERO;
 // Calculate (this mod m)
 BigInteger modVal = this;
-if (signum < 0 || (intArrayCmp(mag, m.mag) >= 0))
+if (signum < 0 || (this.compareMagnitude(m) >= 0))
 modVal = this.mod(m);
 if (modVal.equals(ONE))
 return ONE;
 MutableBigInteger a = new MutableBigInteger(modVal);
 MutableBigInteger b = new MutableBigInteger(m);
 MutableBigInteger result = a.mutableModInverse(b);
-return new BigInteger(result, 1);
+return result.toBigInteger(1);
 }
 // Shift Operations
 /**
 */
 public boolean testBit(int n) {
 if (n<0)
 throw new ArithmeticException("Negative bit address");
-return (getInt(n/32) & (1 << (n%32))) != 0;
+return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
 }
 /**
 * Returns a BigInteger whose value is equivalent to this BigInteger
 * with the designated bit set.  (Computes {@code (this | (1<<n))}.)
 */
 public BigInteger setBit(int n) {
 if (n<0)
 throw new ArithmeticException("Negative bit address");
-int intNum = n/32;
+int intNum = n >>> 5;
 int[] result = new int[Math.max(intLength(), intNum+2)];
 for (int i=0; i<result.length; i++)
 result[result.length-i-1] = getInt(i);
-result[result.length-intNum-1] |= (1 << (n%32));
+result[result.length-intNum-1] |= (1 << (n & 31));
 return valueOf(result);
 }
 /**
 */
 public BigInteger clearBit(int n) {
 if (n<0)
 throw new ArithmeticException("Negative bit address");
-int intNum = n/32;
+int intNum = n >>> 5;
-int[] result = new int[Math.max(intLength(), (n+1)/32+1)];
+int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)];
 for (int i=0; i<result.length; i++)
 result[result.length-i-1] = getInt(i);
-result[result.length-intNum-1] &= ~(1 << (n%32));
+result[result.length-intNum-1] &= ~(1 << (n & 31));
 return valueOf(result);
 }
 /**
 */
 public BigInteger flipBit(int n) {
 if (n<0)
 throw new ArithmeticException("Negative bit address");
-int intNum = n/32;
+int intNum = n >>> 5;
 int[] result = new int[Math.max(intLength(), intNum+2)];
 for (int i=0; i<result.length; i++)
 result[result.length-i-1] = getInt(i);
-result[result.length-intNum-1] ^= (1 << (n%32));
+result[result.length-intNum-1] ^= (1 << (n & 31));
 return valueOf(result);
 }
 /**
 * (Computes {@code (this==0? -1 : log2(this & -this))}.)
 *
 * @return index of the rightmost one bit in this BigInteger.
 */
 public int getLowestSetBit() {
-/*
+@SuppressWarnings("deprecation") int lsb = lowestSetBit - 2;
-* Initialize lowestSetBit field the first time this method is
+if (lsb == -2) {  // lowestSetBit not initialized yet
-* executed. This method depends on the atomicity of int modifies;
+lsb = 0;
-* without this guarantee, it would have to be synchronized.
-*/
-if (lowestSetBit == -2) {
 if (signum == 0) {
-lowestSetBit = -1;
+lsb -= 1;
 } else {
 // Search for lowest order nonzero int
 int i,b;
 for (i=0; (b = getInt(i))==0; i++)
 ;
-lowestSetBit = (i << 5) + trailingZeroCnt(b);
+lsb += (i << 5) + Integer.numberOfTrailingZeros(b);
 }
-}
+lowestSetBit = lsb + 2;
-return lowestSetBit;
+}
+return lsb;
 }
 // Miscellaneous Bit Operations
 *
 * @return number of bits in the minimal two's-complement
 *         representation of this BigInteger, <i>excluding</i> a sign bit.
 */
 public int bitLength() {
-/*
+@SuppressWarnings("deprecation") int n = bitLength - 1;
-* Initialize bitLength field the first time this method is executed.
+if (n == -1) { // bitLength not initialized yet
-* This method depends on the atomicity of int modifies; without
+int[] m = mag;
-* this guarantee, it would have to be synchronized.
+int len = m.length;
-*/
+if (len == 0) {
-if (bitLength == -1) {
+n = 0; // offset by one to initialize
-if (signum == 0) {
+}  else {
-bitLength = 0;
-} else {
 // Calculate the bit length of the magnitude
-int magBitLength = ((mag.length-1) << 5) + bitLen(mag[0]);
+int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]);
+if (signum < 0) {
-if (signum < 0) {
+// Check if magnitude is a power of two
-// Check if magnitude is a power of two
+boolean pow2 = (Integer.bitCount(mag[0]) == 1);
-boolean pow2 = (bitCnt(mag[0]) == 1);
+for(int i=1; i< len && pow2; i++)
-for(int i=1; i<mag.length && pow2; i++)
+pow2 = (mag[i] == 0);
-pow2 = (mag[i]==0);
+n = (pow2 ? magBitLength -1 : magBitLength);
-bitLength = (pow2 ? magBitLength-1 : magBitLength);
+} else {
-} else {
+n = magBitLength;
-bitLength = magBitLength;
+}
-}
 }
-}
+bitLength = n + 1;
-return bitLength;
+}
-}
+return n;
+}
-/**
-* bitLen(val) is the number of bits in val.
-*/
-static int bitLen(int w) {
-// Binary search - decision tree (5 tests, rarely 6)
-return
-(w < 1<<15 ?
-(w < 1<<7 ?
-(w < 1<<3 ?
-(w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) :
-(w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) :
-(w < 1<<11 ?
-(w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) :
-(w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) :
-(w < 1<<23 ?
-(w < 1<<19 ?
-(w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) :
-(w < 1<<21 ? (w < 1<<20 ? 20 : 21) : (w < 1<<22 ? 22 : 23))) :
-(w < 1<<27 ?
-(w < 1<<25 ? (w < 1<<24 ? 24 : 25) : (w < 1<<26 ? 26 : 27)) :
-(w < 1<<29 ? (w < 1<<28 ? 28 : 29) : (w < 1<<30 ? 30 : 31)))));
-}
-/*
-* trailingZeroTable[i] is the number of trailing zero bits in the binary
-* representation of i.
-*/
-final static byte trailingZeroTable[] = {
--25, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
 /**
 * Returns the number of bits in the two's complement representation
 * of this BigInteger that differ from its sign bit.  This method is
 * useful when implementing bit-vector style sets atop BigIntegers.
 *
 * @return number of bits in the two's complement representation
 *         of this BigInteger that differ from its sign bit.
 */
 public int bitCount() {
-/*
+@SuppressWarnings("deprecation") int bc = bitCount - 1;
-* Initialize bitCount field the first time this method is executed.
+if (bc == -1) {  // bitCount not initialized yet
-* This method depends on the atomicity of int modifies; without
+bc = 0;      // offset by one to initialize
-* this guarantee, it would have to be synchronized.
-*/
-if (bitCount == -1) {
 // Count the bits in the magnitude
-int magBitCount = 0;
 for (int i=0; i<mag.length; i++)
-magBitCount += bitCnt(mag[i]);
+bc += Integer.bitCount(mag[i]);
 if (signum < 0) {
 // Count the trailing zeros in the magnitude
 int magTrailingZeroCount = 0, j;
 for (j=mag.length-1; mag[j]==0; j--)
 magTrailingZeroCount += 32;
-magTrailingZeroCount +=
+magTrailingZeroCount += Integer.numberOfTrailingZeros(mag[j]);
-trailingZeroCnt(mag[j]);
+bc += magTrailingZeroCount - 1;
-bitCount = magBitCount + magTrailingZeroCount - 1;
-} else {
-bitCount = magBitCount;
 }
-}
+bitCount = bc + 1;
-return bitCount;
+}
-}
+return bc;
-static int bitCnt(int val) {
-val -= (0xaaaaaaaa & val) >>> 1;
-val = (val & 0x33333333) + ((val >>> 2) & 0x33333333);
-val = val + (val >>> 4) & 0x0f0f0f0f;
-val += val >>> 8;
-val += val >>> 16;
-return val & 0xff;
-}
-static int trailingZeroCnt(int val) {
-// Loop unrolled for performance
-int byteVal = val & 0xff;
-if (byteVal != 0)
-return trailingZeroTable[byteVal];
-byteVal = (val >>> 8) & 0xff;
-if (byteVal != 0)
-return trailingZeroTable[byteVal] + 8;
-byteVal = (val >>> 16) & 0xff;
-if (byteVal != 0)
-return trailingZeroTable[byteVal] + 16;
-byteVal = (val >>> 24) & 0xff;
-return trailingZeroTable[byteVal] + 24;
 }
 // Primality Testing
 /**
 * @param  val BigInteger to which this BigInteger is to be compared.
 * @return -1, 0 or 1 as this BigInteger is numerically less than, equal
 *         to, or greater than {@code val}.
 */
 public int compareTo(BigInteger val) {
-return (signum==val.signum
+if (signum == val.signum) {
-? signum*intArrayCmp(mag, val.mag)
+switch (signum) {
-: (signum>val.signum ? 1 : -1));
+case 1:
-}
+return compareMagnitude(val);
+case -1:
-/*
+return val.compareMagnitude(this);
-* Returns -1, 0 or +1 as big-endian unsigned int array arg1 is
+default:
-* less than, equal to, or greater than arg2.
+return 0;
-*/
+}
-private static int intArrayCmp(int[] arg1, int[] arg2) {
+}
-if (arg1.length < arg2.length)
+return signum > val.signum ? 1 : -1;
+}
+/**
+* Compares the magnitude array of this BigInteger with the specified
+* BigInteger's. This is the version of compareTo ignoring sign.
+*
+* @param val BigInteger whose magnitude array to be compared.
+* @return -1, 0 or 1 as this magnitude array is less than, equal to or
+*         greater than the magnitude aray for the specified BigInteger's.
+*/
+final int compareMagnitude(BigInteger val) {
+int[] m1 = mag;
+int len1 = m1.length;
+int[] m2 = val.mag;
+int len2 = m2.length;
+if (len1 < len2)
 return -1;
-if (arg1.length > arg2.length)
+if (len1 > len2)
 return 1;
+for (int i = 0; i < len1; i++) {
-// Argument lengths are equal; compare the values
+int a = m1[i];
-for (int i=0; i<arg1.length; i++) {
+int b = m2[i];
-long b1 = arg1[i] & LONG_MASK;
+if (a != b)
-long b2 = arg2[i] & LONG_MASK;
+return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
-if (b1 < b2)
-return -1;
-if (b1 > b2)
-return 1;
 }
 return 0;
 }
 /**
 if (x == this)
 return true;
 if (!(x instanceof BigInteger))
 return false;
 BigInteger xInt = (BigInteger) x;
+if (xInt.signum != signum)
-if (xInt.signum != signum || xInt.mag.length != mag.length)
 return false;
-for (int i=0; i<mag.length; i++)
+int[] m = mag;
-if (xInt.mag[i] != mag[i])
+int len = m.length;
+int[] xm = xInt.mag;
+if (len != xm.length)
+return false;
+for (int i = 0; i < len; i++)
+if (xm[i] != m[i])
 return false;
 return true;
 }
 int numGroups = 0;
 while (tmp.signum != 0) {
 BigInteger d = longRadix[radix];
 MutableBigInteger q = new MutableBigInteger(),
-r = new MutableBigInteger(),
 a = new MutableBigInteger(tmp.mag),
 b = new MutableBigInteger(d.mag);
-a.divide(b, q, r);
+MutableBigInteger r = a.divide(b, q);
-BigInteger q2 = new BigInteger(q, tmp.signum * d.signum);
+BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
-BigInteger r2 = new BigInteger(r, tmp.signum * d.signum);
+BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
 tmp = q2;
 }
 /**
 * Returns a copy of the input array stripped of any leading zero bytes.
 */
 private static int[] stripLeadingZeroInts(int val[]) {
-int byteLength = val.length;
+int vlen = val.length;
 int keep;
 // Find first nonzero byte
-for (keep=0; keep<val.length && val[keep]==0; keep++)
+for (keep = 0; keep < vlen && val[keep] == 0; keep++)
 ;
+return java.util.Arrays.copyOfRange(val, keep, vlen);
-int result[] = new int[val.length - keep];
-for(int i=0; i<val.length - keep; i++)
-result[i] = val[keep+i];
-return result;
 }
 /**
 * Returns the input array stripped of any leading zero bytes.
 * Since the source is trusted the copying may be skipped.
 */
 private static int[] trustedStripLeadingZeroInts(int val[]) {
-int byteLength = val.length;
+int vlen = val.length;
 int keep;
 // Find first nonzero byte
-for (keep=0; keep<val.length && val[keep]==0; keep++)
+for (keep = 0; keep < vlen && val[keep] == 0; keep++)
 ;
+return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
-// Only perform copy if necessary
-if (keep > 0) {
-int result[] = new int[val.length - keep];
-for(int i=0; i<val.length - keep; i++)
-result[i] = val[keep+i];
-return result;
-}
-return val;
 }
 /**
 * Returns a copy of the input array stripped of any leading zero bytes.
 */
 private static int[] stripLeadingZeroBytes(byte a[]) {
 int byteLength = a.length;
 int keep;
 // Find first nonzero byte
-for (keep=0; keep<a.length && a[keep]==0; keep++)
+for (keep = 0; keep < byteLength && a[keep]==0; keep++)
 ;
 // Allocate new array and copy relevant part of input array
-int intLength = ((byteLength - keep) + 3)/4;
+int intLength = ((byteLength - keep) + 3) >>> 2;
 int[] result = new int[intLength];
 int b = byteLength - 1;
 for (int i = intLength-1; i >= 0; i--) {
 result[i] = a[b--] & 0xff;
 int bytesRemaining = b - keep + 1;
 int bytesToTransfer = Math.min(3, bytesRemaining);
-for (int j=8; j <= 8*bytesToTransfer; j += 8)
+for (int j=8; j <= (bytesToTransfer << 3); j += 8)
 result[i] |= ((a[b--] & 0xff) << j);
 }
 return result;
 }
 /**
 * Returns the length of the two's complement representation in ints,
 * including space for at least one sign bit.
 */
 private int intLength() {
-return bitLength()/32 + 1;
+return (bitLength() >>> 5) + 1;
 }
 /* Returns sign bit */
 private int signBit() {
 return signum < 0 ? 1 : 0;
 * Returns the index of the int that contains the first nonzero int in the
 * little-endian binary representation of the magnitude (int 0 is the
 * least significant). If the magnitude is zero, return value is undefined.
 */
 private int firstNonzeroIntNum() {
-/*
+int fn = firstNonzeroIntNum - 2;
-* Initialize firstNonzeroIntNum field the first time this method is
+if (fn == -2) { // firstNonzeroIntNum not initialized yet
-* executed. This method depends on the atomicity of int modifies;
+fn = 0;
-* without this guarantee, it would have to be synchronized.
-*/
+// Search for the first nonzero int
-if (firstNonzeroIntNum == -2) {
+int i;
-// Search for the first nonzero int
+int mlen = mag.length;
-int i;
+for (i = mlen - 1; i >= 0 && mag[i] == 0; i--)
-for (i=mag.length-1; i>=0 && mag[i]==0; i--)
+;
-;
+fn = mlen - i - 1;
-firstNonzeroIntNum = mag.length-i-1;
+firstNonzeroIntNum = fn + 2; // offset by two to initialize
 }
-return firstNonzeroIntNum;
+return fn;
 }
 /** use serialVersionUID from JDK 1.1. for interoperability */
 private static final long serialVersionUID = -8287574255936472291L;
 /**
 /**
 * Reconstitute the {@code BigInteger} instance from a stream (that is,
 * deserialize it). The magnitude is read in as an array of bytes
 * for historical reasons, but it is converted to an array of ints
 * and the byte array is discarded.
+* Note:
+* The current convention is to initialize the cache fields, bitCount,
+* bitLength and lowestSetBit, to 0 rather than some other marker value.
+* Therefore, no explicit action to set these fields needs to be taken in
+* readObject because those fields already have a 0 value be default since
+* defaultReadObject is not being used.
 */
 private void readObject(java.io.ObjectInputStream s)
 throws java.io.IOException, ClassNotFoundException {
 /*
 * In order to maintain compatibility with previous serialized forms,
 // prepare to read the alternate persistent fields
 ObjectInputStream.GetField fields = s.readFields();
 // Read the alternate persistent fields that we care about
-signum = fields.get("signum", -2);
+int sign = fields.get("signum", -2);
 byte[] magnitude = (byte[])fields.get("magnitude", null);
 // Validate signum
-if (signum < -1 || signum > 1) {
+if (sign < -1 || sign > 1) {
 String message = "BigInteger: Invalid signum value";
 if (fields.defaulted("signum"))
 message = "BigInteger: Signum not present in stream";
 throw new java.io.StreamCorruptedException(message);
 }
-if ((magnitude.length==0) != (signum==0)) {
+if ((magnitude.length == 0) != (sign == 0)) {
 String message = "BigInteger: signum-magnitude mismatch";
 if (fields.defaulted("magnitude"))
 message = "BigInteger: Magnitude not present in stream";
 throw new java.io.StreamCorruptedException(message);
 }
-// Set "cached computation" fields to their initial values
+// Commit final fields via Unsafe
-bitCount = bitLength = -1;
+unsafe.putIntVolatile(this, signumOffset, sign);
-lowestSetBit = firstNonzeroByteNum = firstNonzeroIntNum = -2;
 // Calculate mag field from magnitude and discard magnitude
-mag = stripLeadingZeroBytes(magnitude);
+unsafe.putObjectVolatile(this, magOffset,
+stripLeadingZeroBytes(magnitude));
+}
+// Support for resetting final fields while deserializing
+private static final sun.misc.Unsafe unsafe = sun.misc.Unsafe.getUnsafe();
+private static final long signumOffset;
+private static final long magOffset;
+static {
+try {
+signumOffset = unsafe.objectFieldOffset
+(BigInteger.class.getDeclaredField("signum"));
+magOffset = unsafe.objectFieldOffset
+(BigInteger.class.getDeclaredField("mag"));
+} catch (Exception ex) {
+throw new Error(ex);
+}
 }
 /**
 * Save the {@code BigInteger} instance to a stream.
 * The magnitude of a BigInteger is serialized as a byte array for
 private void writeObject(ObjectOutputStream s) throws IOException {
 // set the values of the Serializable fields
 ObjectOutputStream.PutField fields = s.putFields();
 fields.put("signum", signum);
 fields.put("magnitude", magSerializedForm());
+// The values written for cached fields are compatible with older
+// versions, but are ignored in readObject so don't otherwise matter.
 fields.put("bitCount", -1);
 fields.put("bitLength", -1);
 fields.put("lowestSetBit", -2);
 fields.put("firstNonzeroByteNum", -2);
 /**
 * Returns the mag array as an array of bytes.
 */
 private byte[] magSerializedForm() {
-int bitLen = (mag.length == 0 ? 0 :
+int len = mag.length;
-((mag.length - 1) << 5) + bitLen(mag[0]));
-int byteLen = (bitLen + 7)/8;
+int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0]));
+int byteLen = (bitLen + 7) >>> 3;
 byte[] result = new byte[byteLen];
-for (int i=byteLen-1, bytesCopied=4, intIndex=mag.length-1, nextInt=0;
+for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0;
 i>=0; i--) {
 if (bytesCopied == 4) {
 nextInt = mag[intIndex--];
 bytesCopied = 1;
 } else {

changeset 2922	dd6d609861f0
parent 2	90ce3da70b43
child 4151	db7d59c0b0e6