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

equal deleted inserted replaced

-:0060e9d7c450
+:620b31ed8807
 * @since 9
 */
 public BigInteger(byte[] val, int off, int len) {
 if (val.length == 0) {
 throw new NumberFormatException("Zero length BigInteger");
-} else if ((off < 0) || (off >= val.length) || (len < 0) ||
+}
-(len > val.length - off)) { // 0 <= off < val.length
+Objects.checkFromIndexSize(off, len, val.length);
-throw new IndexOutOfBoundsException();
-}
 if (val[off] < 0) {
 mag = makePositive(val, off, len);
 signum = -1;
 } else {
 * @since 9
 */
 public BigInteger(int signum, byte[] magnitude, int off, int len) {
 if (signum < -1 || signum > 1) {
 throw(new NumberFormatException("Invalid signum value"));
-} else if ((off < 0) || (len < 0) ||
+}
-(len > 0 &&
+Objects.checkFromIndexSize(off, len, magnitude.length);
-((off >= magnitude.length) ||
-(len > magnitude.length - off)))) { // 0 <= off < magnitude.length
-throw new IndexOutOfBoundsException();
-}
 // stripLeadingZeroBytes() returns a zero length array if len == 0
 this.mag = stripLeadingZeroBytes(magnitude, off, len);
 if (this.mag.length == 0) {
 /** The natural log of 2.  This is used in computing cache indices. */
 private static final double LOG_TWO = Math.log(2.0);
 static {
+assert 0 < KARATSUBA_THRESHOLD
+&& KARATSUBA_THRESHOLD < TOOM_COOK_THRESHOLD
+&& TOOM_COOK_THRESHOLD < Integer.MAX_VALUE
+&& 0 < KARATSUBA_SQUARE_THRESHOLD
+&& KARATSUBA_SQUARE_THRESHOLD < TOOM_COOK_SQUARE_THRESHOLD
+&& TOOM_COOK_SQUARE_THRESHOLD < Integer.MAX_VALUE :
+"Algorithm thresholds are inconsistent";
 for (int i = 1; i <= MAX_CONSTANT; i++) {
 int[] magnitude = new int[1];
 magnitude[0] = i;
 posConst[i] = new BigInteger(magnitude,  1);
 negConst[i] = new BigInteger(magnitude, -1);
 *
 * @param  val value to be multiplied by this BigInteger.
 * @return {@code this * val}
 */
 public BigInteger multiply(BigInteger val) {
+return multiply(val, false);
+}
+/**
+* Returns a BigInteger whose value is {@code (this * val)}.  If
+* the invocation is recursive certain overflow checks are skipped.
+*
+* @param  val value to be multiplied by this BigInteger.
+* @param  isRecursion whether this is a recursive invocation
+* @return {@code this * val}
+*/
+private BigInteger multiply(BigInteger val, boolean isRecursion) {
 if (val.signum == 0 || signum == 0)
 return ZERO;
 int xlen = mag.length;
 return new BigInteger(result, resultSign);
 } else {
 if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) {
 return multiplyKaratsuba(this, val);
 } else {
+//
+// In "Hacker's Delight" section 2-13, p.33, it is explained
+// that if x and y are unsigned 32-bit quantities and m and n
+// are their respective numbers of leading zeros within 32 bits,
+// then the number of leading zeros within their product as a
+// 64-bit unsigned quantity is either m + n or m + n + 1. If
+// their product is not to overflow, it cannot exceed 32 bits,
+// and so the number of leading zeros of the product within 64
+// bits must be at least 32, i.e., the leftmost set bit is at
+// zero-relative position 31 or less.
+//
+// From the above there are three cases:
+//
+//     m + n    leftmost set bit    condition
+//     -----    ----------------    ---------
+//     >= 32    x <= 64 - 32 = 32   no overflow
+//     == 31    x >= 64 - 32 = 32   possible overflow
+//     <= 30    x >= 64 - 31 = 33   definite overflow
+//
+// The "possible overflow" condition cannot be detected by
+// examning data lengths alone and requires further calculation.
+//
+// By analogy, if 'this' and 'val' have m and n as their
+// respective numbers of leading zeros within 32*MAX_MAG_LENGTH
+// bits, then:
+//
+//     m + n >= 32*MAX_MAG_LENGTH        no overflow
+//     m + n == 32*MAX_MAG_LENGTH - 1    possible overflow
+//     m + n <= 32*MAX_MAG_LENGTH - 2    definite overflow
+//
+// Note however that if the number of ints in the result
+// were to be MAX_MAG_LENGTH and mag[0] < 0, then there would
+// be overflow. As a result the leftmost bit (of mag[0]) cannot
+// be used and the constraints must be adjusted by one bit to:
+//
+//     m + n >  32*MAX_MAG_LENGTH        no overflow
+//     m + n == 32*MAX_MAG_LENGTH        possible overflow
+//     m + n <  32*MAX_MAG_LENGTH        definite overflow
+//
+// The foregoing leading zero-based discussion is for clarity
+// only. The actual calculations use the estimated bit length
+// of the product as this is more natural to the internal
+// array representation of the magnitude which has no leading
+// zero elements.
+//
+if (!isRecursion) {
+// The bitLength() instance method is not used here as we
+// are only considering the magnitudes as non-negative. The
+// Toom-Cook multiplication algorithm determines the sign
+// at its end from the two signum values.
+if (bitLength(mag, mag.length) +
+bitLength(val.mag, val.mag.length) >
+32L*MAX_MAG_LENGTH) {
+reportOverflow();
+}
+}
 return multiplyToomCook3(this, val);
 }
 }
 }
 private static int[] implMultiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z) {
 int xstart = xlen - 1;
 int ystart = ylen - 1;
 if (z == null || z.length < (xlen+ ylen))
 z = new int[xlen+ylen];
 long carry = 0;
 for (int j=ystart, k=ystart+1+xstart; j >= 0; j--, k--) {
 long product = (y[j] & LONG_MASK) *
 (x[xstart] & LONG_MASK) + carry;
 b1 = b.getToomSlice(k, r, 1, largest);
 b0 = b.getToomSlice(k, r, 2, largest);
 BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1, db1;
-v0 = a0.multiply(b0);
+v0 = a0.multiply(b0, true);
 da1 = a2.add(a0);
 db1 = b2.add(b0);
-vm1 = da1.subtract(a1).multiply(db1.subtract(b1));
+vm1 = da1.subtract(a1).multiply(db1.subtract(b1), true);
 da1 = da1.add(a1);
 db1 = db1.add(b1);
-v1 = da1.multiply(db1);
+v1 = da1.multiply(db1, true);
 v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(
-db1.add(b2).shiftLeft(1).subtract(b0));
+db1.add(b2).shiftLeft(1).subtract(b0), true);
-vinf = a2.multiply(b2);
+vinf = a2.multiply(b2, true);
 // The algorithm requires two divisions by 2 and one by 3.
 // All divisions are known to be exact, that is, they do not produce
 // remainders, and all results are positive.  The divisions by 2 are
 // implemented as right shifts which are relatively efficient, leaving
 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
 *
 * @return {@code this<sup>2</sup>}
 */
 private BigInteger square() {
+return square(false);
+}
+/**
+* Returns a BigInteger whose value is {@code (this<sup>2</sup>)}. If
+* the invocation is recursive certain overflow checks are skipped.
+*
+* @param isRecursion whether this is a recursive invocation
+* @return {@code this<sup>2</sup>}
+*/
+private BigInteger square(boolean isRecursion) {
 if (signum == 0) {
 return ZERO;
 }
 int len = mag.length;
 return new BigInteger(trustedStripLeadingZeroInts(z), 1);
 } else {
 if (len < TOOM_COOK_SQUARE_THRESHOLD) {
 return squareKaratsuba();
 } else {
+//
+// For a discussion of overflow detection see multiply()
+//
+if (!isRecursion) {
+if (bitLength(mag, mag.length) > 16L*MAX_MAG_LENGTH) {
+reportOverflow();
+}
+}
 return squareToomCook3();
 }
 }
 }
 a2 = getToomSlice(k, r, 0, len);
 a1 = getToomSlice(k, r, 1, len);
 a0 = getToomSlice(k, r, 2, len);
 BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1;
-v0 = a0.square();
+v0 = a0.square(true);
 da1 = a2.add(a0);
-vm1 = da1.subtract(a1).square();
+vm1 = da1.subtract(a1).square(true);
 da1 = da1.add(a1);
-v1 = da1.square();
+v1 = da1.square(true);
-vinf = a2.square();
+vinf = a2.square(true);
-v2 = da1.add(a2).shiftLeft(1).subtract(a0).square();
+v2 = da1.add(a2).shiftLeft(1).subtract(a0).square(true);
 // The algorithm requires two divisions by 2 and one by 3.
 // All divisions are known to be exact, that is, they do not produce
 // remainders, and all results are positive.  The divisions by 2 are
 // implemented as right shifts which are relatively efficient, leaving
 // Factor out powers of two from the base, as the exponentiation of
 // these can be done by left shifts only.
 // The remaining part can then be exponentiated faster.  The
 // powers of two will be multiplied back at the end.
 int powersOfTwo = partToSquare.getLowestSetBit();
-long bitsToShift = (long)powersOfTwo * exponent;
+long bitsToShiftLong = (long)powersOfTwo * exponent;
-if (bitsToShift > Integer.MAX_VALUE) {
+if (bitsToShiftLong > Integer.MAX_VALUE) {
 reportOverflow();
 }
+int bitsToShift = (int)bitsToShiftLong;
 int remainingBits;
 // Factor the powers of two out quickly by shifting right, if needed.
 if (powersOfTwo > 0) {
 partToSquare = partToSquare.shiftRight(powersOfTwo);
 remainingBits = partToSquare.bitLength();
 if (remainingBits == 1) {  // Nothing left but +/- 1?
 if (signum < 0 && (exponent&1) == 1) {
-return NEGATIVE_ONE.shiftLeft(powersOfTwo*exponent);
+return NEGATIVE_ONE.shiftLeft(bitsToShift);
 } else {
-return ONE.shiftLeft(powersOfTwo*exponent);
+return ONE.shiftLeft(bitsToShift);
 }
 }
 } else {
 remainingBits = partToSquare.bitLength();
 if (remainingBits == 1) { // Nothing left but +/- 1?
 // Multiply back the powers of two (quickly, by shifting left)
 if (powersOfTwo > 0) {
 if (bitsToShift + scaleFactor <= 62) { // Fits in long?
 return valueOf((result << bitsToShift) * newSign);
 } else {
-return valueOf(result*newSign).shiftLeft((int) bitsToShift);
+return valueOf(result*newSign).shiftLeft(bitsToShift);
 }
-}
+} else {
-else {
 return valueOf(result*newSign);
 }
 } else {
+if ((long)bitLength() * exponent / Integer.SIZE > MAX_MAG_LENGTH) {
+reportOverflow();
+}
 // Large number algorithm.  This is basically identical to
 // the algorithm above, but calls multiply() and square()
 // which may use more efficient algorithms for large numbers.
 BigInteger answer = ONE;
 }
 }
 // Multiply back the (exponentiated) powers of two (quickly,
 // by shifting left)
 if (powersOfTwo > 0) {
-answer = answer.shiftLeft(powersOfTwo*exponent);
+answer = answer.shiftLeft(bitsToShift);
 }
 if (signum < 0 && (exponent&1) == 1) {
 return answer.negate();
 } else {
 // 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);
+n = (pow2 ? magBitLength - 1 : magBitLength);
 } else {
 n = magBitLength;
 }
 }
 bitLengthPlusOne = n + 1;

changeset 53327	620b31ed8807
parent 52220	9c260a6b6471
child 57956	e0b8b019d2f5