src/share/classes/java/math/BigInteger.java
Print this page
*** 103,113 ****
* a signum of 0. This is necessary to ensures that there is exactly one
* representation for each BigInteger value.
*
* @serial
*/
! 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
--- 103,113 ----
* a signum of 0. This is necessary to ensures that there is exactly one
* representation for each BigInteger value.
*
* @serial
*/
! 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
*** 114,178 ****
* 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;
// 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
! * (either value is acceptable).
*
* @serial
* @see #bitCount
*/
! private int bitCount = -1;
/**
! * The bitLength of this BigInteger, as returned by bitLength(), or -1
* (either value is acceptable).
*
* @serial
* @see #bitLength()
*/
! private int bitLength = -1;
/**
! * The lowest set bit of this BigInteger, as returned by getLowestSetBit(),
! * or -2 (either value is acceptable).
*
* @serial
* @see #getLowestSetBit
*/
! private int lowestSetBit = -2;
/**
! * The index of the lowest-order byte in the magnitude of this BigInteger
! * 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.
! *
! * @serial
! */
! 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.
*/
! private int firstNonzeroIntNum = -2;
/**
* This mask is used to obtain the value of an int as if it were unsigned.
*/
! private final static long LONG_MASK = 0xffffffffL;
//Constructors
/**
* Translates a byte array containing the two's-complement binary
--- 114,179 ----
* 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.
*/
! 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).
/**
! * One plus the bitCount of this BigInteger. Zeros means unitialized.
*
* @serial
* @see #bitCount
+ * @deprecated Deprecated since logical value is offset from stored
+ * value and correction factor is applied in accessor method.
*/
! @Deprecated
! 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
+ * value and correction factor is applied in accessor method.
*/
! @Deprecated
! private int bitLength;
/**
! * 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
+ * value and correction factor is applied in accessor method.
*/
! @Deprecated
! private int lowestSetBit;
/**
! * 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).
! * 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
+ * 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.
*/
! final static long LONG_MASK = 0xffffffffL;
//Constructors
/**
* Translates a byte array containing the two's-complement binary
*** 293,303 ****
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 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) {
--- 294,304 ----
throw new NumberFormatException("Radix out of range");
if (val.length() == 0)
throw new NumberFormatException("Zero length BigInteger");
// Check for at most one leading sign
! 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) {
*** 304,314 ****
cursor = 1;
if (val.length() == 1)
throw new NumberFormatException("Zero length BigInteger");
}
if (index1 == 0)
! signum = -1;
} else
throw new NumberFormatException("Illegal embedded sign character");
// Skip leading zeros and compute number of digits in magnitude
while (cursor < len &&
--- 305,315 ----
cursor = 1;
if (val.length() == 1)
throw new NumberFormatException("Zero length BigInteger");
}
if (index1 == 0)
! sign = -1;
} else
throw new NumberFormatException("Illegal embedded sign character");
// Skip leading zeros and compute number of digits in magnitude
while (cursor < len &&
*** 316,342 ****
cursor++;
if (cursor == len) {
signum = 0;
mag = ZERO.mag;
return;
- } else {
- numDigits = len - cursor;
}
// 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;
! mag = 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);
! if (mag[mag.length - 1] < 0)
throw new NumberFormatException("Illegal digit");
// Process remaining digit groups
int superRadix = intRadix[radix];
int groupVal = 0;
--- 317,344 ----
cursor++;
if (cursor == len) {
signum = 0;
mag = ZERO.mag;
return;
}
+ 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) >>> 5;
! 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);
! magnitude[numWords - 1] = Integer.parseInt(group, radix);
! if (magnitude[numWords - 1] < 0)
throw new NumberFormatException("Illegal digit");
// Process remaining digit groups
int superRadix = intRadix[radix];
int groupVal = 0;
*** 343,369 ****
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);
}
// Required for cases where the array was overallocated.
! mag = trustedStripLeadingZeroInts(mag);
}
// 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;
if (val[0] == '-') {
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
! signum = -1;
cursor = 1;
} else if (val[0] == '+') {
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
cursor = 1;
--- 345,371 ----
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(magnitude, superRadix, groupVal);
}
// Required for cases where the array was overallocated.
! 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
! int sign = 1;
if (val[0] == '-') {
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
! sign = -1;
cursor = 1;
} else if (val[0] == '+') {
if (len == 1)
throw new NumberFormatException("Zero length BigInteger");
cursor = 1;
*** 374,409 ****
cursor++;
if (cursor == len) {
signum = 0;
mag = ZERO.mag;
return;
- } else {
- numDigits = len - cursor;
}
// 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;
}
! mag = 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);
// Process remaining digit groups
while (cursor < len) {
int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
! destructiveMulAdd(mag, intRadix[10], groupVal);
}
! mag = trustedStripLeadingZeroInts(mag);
}
// 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.
--- 376,412 ----
cursor++;
if (cursor == len) {
signum = 0;
mag = ZERO.mag;
return;
}
+ 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) >>> 5;
}
! int[] magnitude = new int[numWords];
// Process first (potentially short) digit group
int firstGroupLen = numDigits % digitsPerInt[10];
if (firstGroupLen == 0)
firstGroupLen = digitsPerInt[10];
! magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen);
// Process remaining digit groups
while (cursor < len) {
int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
! destructiveMulAdd(magnitude, intRadix[10], groupVal);
}
! 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.
*** 840,869 ****
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)) {
! v2 = n.subtract(v2);
! 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)) {
! u2 = n.subtract(u2);
! u2.signum = - u2.signum;
! }
! u2 = u2.shiftRight(1);
v2 = v.add(d.multiply(u)).mod(n);
! if (v2.testBit(0)) {
! v2 = n.subtract(v2);
! v2.signum = - v2.signum;
! }
v2 = v2.shiftRight(1);
u = u2; v = v2;
}
}
--- 843,867 ----
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))
! v2 = v2.subtract(n);
!
v2 = v2.shiftRight(1);
u = u2; v = v2;
if (k.testBit(i)) {
u2 = u.add(v).mod(n);
! if (u2.testBit(0))
! u2 = u2.subtract(n);
+ u2 = u2.shiftRight(1);
v2 = v.add(d.multiply(u)).mod(n);
! if (v2.testBit(0))
! v2 = v2.subtract(n);
v2 = v2.shiftRight(1);
u = u2; v = v2;
}
}
*** 916,930 ****
}
return true;
}
/**
! * This private 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) {
this.signum = (magnitude.length==0 ? 0 : signum);
this.mag = magnitude;
}
/**
--- 914,928 ----
}
return true;
}
/**
! * 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.
*/
! BigInteger(int[] magnitude, int signum) {
this.signum = (magnitude.length==0 ? 0 : signum);
this.mag = magnitude;
}
/**
*** 934,959 ****
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
/**
* Returns a BigInteger whose value is equal to that of the
* specified {@code long}. This "static factory method" is
--- 932,941 ----
*** 978,989 ****
/**
* Constructs a BigInteger with the specified value, which may not be zero.
*/
private BigInteger(long val) {
if (val < 0) {
- signum = -1;
val = -val;
} else {
signum = 1;
}
int highWord = (int)(val >>> 32);
--- 960,971 ----
/**
* Constructs a BigInteger with the specified value, which may not be zero.
*/
private BigInteger(long val) {
if (val < 0) {
val = -val;
+ signum = -1;
} else {
signum = 1;
}
int highWord = (int)(val >>> 32);
*** 1056,1081 ****
*
* @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);
! if (cmp==0)
return ZERO;
! resultMag = (cmp>0 ? subtract(mag, val.mag)
: subtract(val.mag, mag));
resultMag = trustedStripLeadingZeroInts(resultMag);
! return new BigInteger(resultMag, cmp*signum);
}
/**
* 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
--- 1038,1062 ----
*
* @param val value to be added to this BigInteger.
* @return {@code this + val}
*/
public BigInteger add(BigInteger val) {
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 = compareMagnitude(val);
! if (cmp == 0)
return ZERO;
! int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
: subtract(val.mag, mag));
resultMag = trustedStripLeadingZeroInts(resultMag);
! 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
*** 1110,1125 ****
while (xIndex > 0)
result[--xIndex] = x[xIndex];
// Grow result if necessary
if (carry) {
! int newLen = result.length + 1;
! int temp[] = new int[newLen];
! for (int i = 1; i<newLen; i++)
! temp[i] = result[i-1];
! temp[0] = 0x01;
! result = temp;
}
return result;
}
/**
--- 1091,1104 ----
while (xIndex > 0)
result[--xIndex] = x[xIndex];
// Grow result if necessary
if (carry) {
! int bigger[] = new int[result.length + 1];
! System.arraycopy(result, 0, bigger, 1, result.length);
! bigger[0] = 0x01;
! return bigger;
}
return result;
}
/**
*** 1127,1151 ****
*
* @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);
! if (cmp==0)
return ZERO;
! resultMag = (cmp>0 ? subtract(mag, val.mag)
: subtract(val.mag, mag));
resultMag = trustedStripLeadingZeroInts(resultMag);
! return new BigInteger(resultMag, cmp*signum);
}
/**
* Subtracts the contents of the second int arrays (little) from the
* first (big). The first int array (big) must represent a larger number
--- 1106,1129 ----
*
* @param val value to be subtracted from this BigInteger.
* @return {@code this - val}
*/
public BigInteger subtract(BigInteger val) {
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 = compareMagnitude(val);
! if (cmp == 0)
return ZERO;
! int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
: subtract(val.mag, mag));
resultMag = trustedStripLeadingZeroInts(resultMag);
! 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
*** 1189,1204 ****
return ZERO;
int[] result = multiplyToLen(mag, mag.length,
val.mag, val.mag.length, null);
result = trustedStripLeadingZeroInts(result);
! return new BigInteger(result, signum*val.signum);
}
/**
* Multiplies int arrays x and y to the specified lengths and places
! * the result into z.
*/
private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
int xstart = xlen - 1;
int ystart = ylen - 1;
--- 1167,1223 ----
return ZERO;
int[] result = multiplyToLen(mag, mag.length,
val.mag, val.mag.length, null);
result = trustedStripLeadingZeroInts(result);
! 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;
+ assert v != BigDecimal.INFLATED;
+ 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. 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;
*** 1314,1329 ****
* @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);
! return new BigInteger(q, this.signum * val.signum);
}
/**
* Returns an array of two BigIntegers containing {@code (this / val)}
* followed by {@code (this % val)}.
--- 1333,1347 ----
* @return {@code this / val}
* @throws ArithmeticException {@code val==0}
*/
public BigInteger divide(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! a.divide(b, q);
! return q.toBigInteger(this.signum == val.signum ? 1 : -1);
}
/**
* Returns an array of two BigIntegers containing {@code (this / val)}
* followed by {@code (this % val)}.
*** 1336,1351 ****
* @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);
! result[0] = new BigInteger(q, this.signum * val.signum);
! result[1] = new BigInteger(r, this.signum);
return result;
}
/**
* Returns a BigInteger whose value is {@code (this % val)}.
--- 1354,1368 ----
* @throws ArithmeticException {@code val==0}
*/
public BigInteger[] divideAndRemainder(BigInteger val) {
BigInteger[] result = new BigInteger[2];
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! MutableBigInteger r = a.divide(b, q);
! result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
! result[1] = r.toBigInteger(this.signum);
return result;
}
/**
* Returns a BigInteger whose value is {@code (this % val)}.
*** 1355,1370 ****
* @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 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.
--- 1372,1385 ----
* @return {@code this % val}
* @throws ArithmeticException {@code val==0}
*/
public BigInteger remainder(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! return a.divide(b, q).toBigInteger(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.
*** 1416,1436 ****
MutableBigInteger a = new MutableBigInteger(this);
MutableBigInteger b = new MutableBigInteger(val);
MutableBigInteger result = a.hybridGCD(b);
! return new BigInteger(result, 1);
}
/**
* 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]);
// If shift can be done without recopy, do so
if (n <= (32-bitsInHighWord)) {
primitiveLeftShift(a, len, nBits);
return a;
--- 1431,1458 ----
MutableBigInteger a = new MutableBigInteger(this);
MutableBigInteger b = new MutableBigInteger(val);
MutableBigInteger result = a.hybridGCD(b);
! 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 = bitLengthForInt(a[0]);
// If shift can be done without recopy, do so
if (n <= (32-bitsInHighWord)) {
primitiveLeftShift(a, len, nBits);
return a;
*** 1479,1491 ****
/**
* 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)
return 0;
! return ((len-1)<<5) + bitLen(val[0]);
}
/**
* Returns a BigInteger whose value is the absolute value of this
* BigInteger.
--- 1501,1513 ----
/**
* 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)
return 0;
! return ((len - 1) << 5) + bitLengthForInt(val[0]);
}
/**
* Returns a BigInteger whose value is the absolute value of this
* BigInteger.
*** 1708,1722 ****
// 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);
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;
--- 1730,1743 ----
// Convert base to Montgomery form
int[] a = leftShift(base, base.length, modLen << 5);
MutableBigInteger q = new MutableBigInteger(),
a2 = new MutableBigInteger(a),
b2 = new MutableBigInteger(mod);
! 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;
*** 1974,1984 ****
private BigInteger mod2(int p) {
if (bitLength() <= p)
return this;
// Copy remaining ints of mag
! int numInts = (p+31)/32;
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
--- 1995,2005 ----
private BigInteger mod2(int p) {
if (bitLength() <= p)
return this;
// Copy remaining ints of mag
! 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
*** 2004,2024 ****
if (m.equals(ONE))
return ZERO;
// Calculate (this mod m)
BigInteger modVal = this;
! if (signum < 0 || (intArrayCmp(mag, m.mag) >= 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);
}
// Shift Operations
/**
--- 2025,2045 ----
if (m.equals(ONE))
return ZERO;
// Calculate (this mod m)
BigInteger modVal = this;
! 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 result.toBigInteger(1);
}
// Shift Operations
/**
*** 2239,2249 ****
*/
public boolean testBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! return (getInt(n/32) & (1 << (n%32))) != 0;
}
/**
* Returns a BigInteger whose value is equivalent to this BigInteger
* with the designated bit set. (Computes {@code (this | (1<<n))}.)
--- 2260,2270 ----
*/
public boolean testBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! 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))}.)
*** 2254,2270 ****
*/
public BigInteger setBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! int intNum = n/32;
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));
return valueOf(result);
}
/**
--- 2275,2291 ----
*/
public BigInteger setBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! 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 & 31));
return valueOf(result);
}
/**
*** 2278,2294 ****
*/
public BigInteger clearBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! int intNum = n/32;
! int[] result = new int[Math.max(intLength(), (n+1)/32+1)];
for (int i=0; i<result.length; i++)
result[result.length-i-1] = getInt(i);
! result[result.length-intNum-1] &= ~(1 << (n%32));
return valueOf(result);
}
/**
--- 2299,2315 ----
*/
public BigInteger clearBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! int intNum = n >>> 5;
! 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 & 31));
return valueOf(result);
}
/**
*** 2302,2318 ****
*/
public BigInteger flipBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! int intNum = n/32;
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));
return valueOf(result);
}
/**
--- 2323,2339 ----
*/
public BigInteger flipBit(int n) {
if (n<0)
throw new ArithmeticException("Negative bit address");
! 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 & 31));
return valueOf(result);
}
/**
*** 2322,2348 ****
* (Computes {@code (this==0? -1 : log2(this & -this))}.)
*
* @return index of the rightmost one bit in this BigInteger.
*/
public int getLowestSetBit() {
! /*
! * Initialize lowestSetBit field the first time this method is
! * executed. This method depends on the atomicity of int modifies;
! * without this guarantee, it would have to be synchronized.
! */
! if (lowestSetBit == -2) {
if (signum == 0) {
! lowestSetBit = -1;
} else {
// Search for lowest order nonzero int
int i,b;
for (i=0; (b = getInt(i))==0; i++)
;
! lowestSetBit = (i << 5) + trailingZeroCnt(b);
}
}
! return lowestSetBit;
}
// Miscellaneous Bit Operations
--- 2343,2367 ----
* (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;
! if (lsb == -2) { // lowestSetBit not initialized yet
! lsb = 0;
if (signum == 0) {
! lsb -= 1;
} else {
// Search for lowest order nonzero int
int i,b;
for (i=0; (b = getInt(i))==0; i++)
;
! lsb += (i << 5) + Integer.numberOfTrailingZeros(b);
}
+ lowestSetBit = lsb + 2;
}
! return lsb;
}
// Miscellaneous Bit Operations
*** 2355,2499 ****
*
* @return number of bits in the minimal two's-complement
* representation of this BigInteger, <i>excluding</i> a sign bit.
*/
public int bitLength() {
! /*
! * Initialize bitLength field the first time this method is executed.
! * This method depends on the atomicity of int modifies; without
! * this guarantee, it would have to be synchronized.
! */
! if (bitLength == -1) {
! if (signum == 0) {
! bitLength = 0;
} else {
// Calculate the bit length of the magnitude
! int magBitLength = ((mag.length-1) << 5) + bitLen(mag[0]);
!
if (signum < 0) {
// Check if magnitude is a power of two
! boolean pow2 = (bitCnt(mag[0]) == 1);
! for(int i=1; i<mag.length && pow2; i++)
! pow2 = (mag[i]==0);
! bitLength = (pow2 ? magBitLength-1 : magBitLength);
} else {
! bitLength = magBitLength;
}
}
}
! return bitLength;
}
/**
- * 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() {
! /*
! * Initialize bitCount field the first time this method is executed.
! * This method depends on the atomicity of int modifies; without
! * 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]);
!
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 +=
! trailingZeroCnt(mag[j]);
!
! bitCount = magBitCount + magTrailingZeroCount - 1;
! } else {
! bitCount = magBitCount;
}
}
! return bitCount;
}
- 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
/**
* Returns {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite. If
--- 2374,2436 ----
*
* @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;
! if (n == -1) { // bitLength not initialized yet
! int[] m = mag;
! int len = m.length;
! if (len == 0) {
! n = 0; // offset by one to initialize
} else {
// Calculate the bit length of the magnitude
! int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]);
if (signum < 0) {
// Check if magnitude is a power of two
! boolean pow2 = (Integer.bitCount(mag[0]) == 1);
! for(int i=1; i< len && pow2; i++)
! pow2 = (mag[i] == 0);
! n = (pow2 ? magBitLength -1 : magBitLength);
} else {
! n = magBitLength;
}
}
+ bitLength = n + 1;
}
! return n;
}
/**
* 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;
! if (bc == -1) { // bitCount not initialized yet
! bc = 0; // offset by one to initialize
// Count the bits in the magnitude
for (int i=0; i<mag.length; 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 += Integer.numberOfTrailingZeros(mag[j]);
! bc += magTrailingZeroCount - 1;
}
+ bitCount = bc + 1;
}
! return bc;
}
// Primality Testing
/**
* Returns {@code true} if this BigInteger is probably prime,
* {@code false} if it's definitely composite. If
*** 2534,2566 ****
* @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
! ? signum*intArrayCmp(mag, val.mag)
! : (signum>val.signum ? 1 : -1));
}
! /*
! * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is
! * less than, equal to, or greater than arg2.
*/
! private static int intArrayCmp(int[] arg1, int[] arg2) {
! if (arg1.length < arg2.length)
return -1;
! if (arg1.length > arg2.length)
return 1;
!
! // Argument lengths are equal; compare the values
! for (int i=0; i<arg1.length; i++) {
! long b1 = arg1[i] & LONG_MASK;
! long b2 = arg2[i] & LONG_MASK;
! if (b1 < b2)
! return -1;
! if (b1 > b2)
! return 1;
}
return 0;
}
/**
--- 2471,2515 ----
* @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) {
! if (signum == val.signum) {
! switch (signum) {
! case 1:
! return compareMagnitude(val);
! case -1:
! return val.compareMagnitude(this);
! default:
! return 0;
}
+ }
+ 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 (len1 > len2)
return 1;
! for (int i = 0; i < len1; i++) {
! int a = m1[i];
! int b = m2[i];
! if (a != b)
! return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
}
return 0;
}
/**
*** 2575,2591 ****
if (x == this)
return true;
if (!(x instanceof BigInteger))
return false;
BigInteger xInt = (BigInteger) x;
! if (xInt.signum != signum || xInt.mag.length != mag.length)
return false;
! for (int i=0; i<mag.length; i++)
! if (xInt.mag[i] != mag[i])
return false;
return true;
}
--- 2524,2546 ----
if (x == this)
return true;
if (!(x instanceof BigInteger))
return false;
+
BigInteger xInt = (BigInteger) x;
+ if (xInt.signum != signum)
+ return false;
! int[] m = mag;
! 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;
}
*** 2660,2675 ****
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);
! BigInteger q2 = new BigInteger(q, tmp.signum * d.signum);
! BigInteger r2 = new BigInteger(r, tmp.signum * d.signum);
digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
tmp = q2;
}
--- 2615,2629 ----
int numGroups = 0;
while (tmp.signum != 0) {
BigInteger d = longRadix[radix];
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(tmp.mag),
b = new MutableBigInteger(d.mag);
! MutableBigInteger r = a.divide(b, q);
! BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
! BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
tmp = q2;
}
*** 2834,2899 ****
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
private static int[] stripLeadingZeroInts(int val[]) {
! int byteLength = val.length;
int keep;
// Find first nonzero byte
! for (keep=0; keep<val.length && val[keep]==0; keep++)
;
!
! 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 keep;
// Find first nonzero byte
! for (keep=0; keep<val.length && val[keep]==0; keep++)
;
!
! // 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++)
;
// Allocate new array and copy relevant part of input array
! int intLength = ((byteLength - keep) + 3)/4;
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)
result[i] |= ((a[b--] & 0xff) << j);
}
return result;
}
--- 2788,2840 ----
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
private static int[] stripLeadingZeroInts(int val[]) {
! int vlen = val.length;
int keep;
// Find first nonzero byte
! for (keep = 0; keep < vlen && val[keep] == 0; keep++)
;
! return java.util.Arrays.copyOfRange(val, keep, vlen);
}
/**
* 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 vlen = val.length;
int keep;
// Find first nonzero byte
! for (keep = 0; keep < vlen && val[keep] == 0; keep++)
;
! return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
}
/**
* 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 < byteLength && a[keep]==0; keep++)
;
// Allocate new array and copy relevant part of input array
! 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 <= (bytesToTransfer << 3); j += 8)
result[i] |= ((a[b--] & 0xff) << j);
}
return result;
}
*** 3035,3045 ****
/**
* 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;
}
/* Returns sign bit */
private int signBit() {
return signum < 0 ? 1 : 0;
--- 2976,2986 ----
/**
* Returns the length of the two's complement representation in ints,
* including space for at least one sign bit.
*/
private int intLength() {
! return (bitLength() >>> 5) + 1;
}
/* Returns sign bit */
private int signBit() {
return signum < 0 ? 1 : 0;
*** 3072,3094 ****
* 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() {
! /*
! * Initialize firstNonzeroIntNum field the first time this method is
! * executed. This method depends on the atomicity of int modifies;
! * without this guarantee, it would have to be synchronized.
! */
! if (firstNonzeroIntNum == -2) {
// Search for the first nonzero int
int i;
! for (i=mag.length-1; i>=0 && mag[i]==0; i--)
;
! firstNonzeroIntNum = mag.length-i-1;
}
! return firstNonzeroIntNum;
}
/** use serialVersionUID from JDK 1.1. for interoperability */
private static final long serialVersionUID = -8287574255936472291L;
--- 3013,3035 ----
* 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;
! if (fn == -2) { // firstNonzeroIntNum not initialized yet
! fn = 0;
!
// Search for the first nonzero int
int i;
! int mlen = mag.length;
! for (i = mlen - 1; i >= 0 && mag[i] == 0; i--)
;
! fn = mlen - i - 1;
! firstNonzeroIntNum = fn + 2; // offset by two to initialize
}
! return fn;
}
/** use serialVersionUID from JDK 1.1. for interoperability */
private static final long serialVersionUID = -8287574255936472291L;
*** 3119,3128 ****
--- 3060,3075 ----
/**
* 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,
*** 3134,3168 ****
// 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);
byte[] magnitude = (byte[])fields.get("magnitude", null);
// Validate signum
! if (signum < -1 || signum > 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)) {
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
! bitCount = bitLength = -1;
! lowestSetBit = firstNonzeroByteNum = firstNonzeroIntNum = -2;
// Calculate mag field from magnitude and discard magnitude
! mag = stripLeadingZeroBytes(magnitude);
}
/**
* Save the {@code BigInteger} instance to a stream.
* The magnitude of a BigInteger is serialized as a byte array for
* historical reasons.
*
--- 3081,3130 ----
// prepare to read the alternate persistent fields
ObjectInputStream.GetField fields = s.readFields();
// Read the alternate persistent fields that we care about
! int sign = fields.get("signum", -2);
byte[] magnitude = (byte[])fields.get("magnitude", null);
// Validate signum
! 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) != (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);
}
! // Commit final fields via Unsafe
! unsafe.putIntVolatile(this, signumOffset, sign);
// Calculate mag field from magnitude and discard 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
* historical reasons.
*
*** 3172,3181 ****
--- 3134,3145 ----
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);
*** 3185,3200 ****
/**
* Returns the mag array as an array of bytes.
*/
private byte[] magSerializedForm() {
! int bitLen = (mag.length == 0 ? 0 :
! ((mag.length - 1) << 5) + bitLen(mag[0]));
! int byteLen = (bitLen + 7)/8;
byte[] result = new byte[byteLen];
! for (int i=byteLen-1, bytesCopied=4, intIndex=mag.length-1, nextInt=0;
i>=0; i--) {
if (bytesCopied == 4) {
nextInt = mag[intIndex--];
bytesCopied = 1;
} else {
--- 3149,3165 ----
/**
* Returns the mag array as an array of bytes.
*/
private byte[] magSerializedForm() {
! int len = mag.length;
!
! 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 = len - 1, nextInt = 0;
i>=0; i--) {
if (bytesCopied == 4) {
nextInt = mag[intIndex--];
bytesCopied = 1;
} else {