1 /* 2 * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /* 25 * @test 26 * @bug 8200698 27 * @summary Tests that exceptions are thrown for ops which would overflow 28 * @requires (sun.arch.data.model == "64" & os.maxMemory >= 4g) 29 * @run testng/othervm -Xmx4g LargeValueExceptions 30 */ 31 package test.java.math.BigInteger; 32 33 import java.math.BigInteger; 34 import static java.math.BigInteger.ONE; 35 import org.testng.annotations.Test; 36 37 // 38 // The intent of this test is to probe the boundaries between overflow and 39 // non-overflow, principally for multiplication and squaring, specifically 40 // the largest values which should not overflow and the smallest values which 41 // should. The transition values used are not necessarily at the exact 42 // boundaries but should be "close." Quite a few different values were used 43 // experimentally before settling on the ones in this test. For multiplication 44 // and squaring all cases are exercised: definite overflow and non-overflow 45 // which can be detected "up front," and "indefinite" overflow, i.e., overflow 46 // which cannot be detected up front so further calculations are required. 47 // 48 // Testing negative values is unnecessary. For both multiplication and squaring 49 // the paths lead to the Toom-Cook algorithm where the signum is used only to 50 // determine the sign of the result and not in the intermediate calculations. 51 // This is also true for exponentiation. 52 // 53 // @Test annotations with optional element "enabled" set to "false" should 54 // succeed when "enabled" is set to "true" but they take too to run in the 55 // course of the typical regression test execution scenario. 56 // 57 public class LargeValueExceptions { 58 // BigInteger.MAX_MAG_LENGTH 59 private static final int MAX_INTS = 1 << 26; 60 61 // Number of bits corresponding to MAX_INTS 62 private static final long MAX_BITS = (0xffffffffL & MAX_INTS) << 5L; 63 64 // Half BigInteger.MAX_MAG_LENGTH 65 private static final int MAX_INTS_HALF = MAX_INTS / 2; 66 67 // --- squaring --- 68 69 // Largest no overflow determined by examining data lengths alone. 70 @Test(enabled=false) squareNoOverflow()71 public void squareNoOverflow() { 72 BigInteger x = ONE.shiftLeft(16*MAX_INTS - 1).subtract(ONE); 73 BigInteger y = x.multiply(x); 74 } 75 76 // Smallest no overflow determined by extra calculations. 77 @Test(enabled=false) squareIndefiniteOverflowSuccess()78 public void squareIndefiniteOverflowSuccess() { 79 BigInteger x = ONE.shiftLeft(16*MAX_INTS - 1); 80 BigInteger y = x.multiply(x); 81 } 82 83 // Largest overflow detected by extra calculations. 84 @Test(expectedExceptions=ArithmeticException.class,enabled=false) squareIndefiniteOverflowFailure()85 public void squareIndefiniteOverflowFailure() { 86 BigInteger x = ONE.shiftLeft(16*MAX_INTS).subtract(ONE); 87 BigInteger y = x.multiply(x); 88 } 89 90 // Smallest overflow detected by examining data lengths alone. 91 // BEGIN Android-changed: Test fails on Android. 92 // java.lang.OutOfMemoryError: Failed to allocate a 134217744 byte allocation ... 93 @Test(expectedExceptions=ArithmeticException.class,enabled=false) 94 // END Android-changed: Test fails on Android. squareDefiniteOverflow()95 public void squareDefiniteOverflow() { 96 BigInteger x = ONE.shiftLeft(16*MAX_INTS); 97 BigInteger y = x.multiply(x); 98 } 99 100 // --- multiplication --- 101 102 // Largest no overflow determined by examining data lengths alone. 103 @Test(enabled=false) multiplyNoOverflow()104 public void multiplyNoOverflow() { 105 final int halfMaxBits = MAX_INTS_HALF << 5; 106 107 BigInteger x = ONE.shiftLeft(halfMaxBits).subtract(ONE); 108 BigInteger y = ONE.shiftLeft(halfMaxBits - 1).subtract(ONE); 109 BigInteger z = x.multiply(y); 110 } 111 112 // Smallest no overflow determined by extra calculations. 113 @Test(enabled=false) multiplyIndefiniteOverflowSuccess()114 public void multiplyIndefiniteOverflowSuccess() { 115 BigInteger x = ONE.shiftLeft((int)(MAX_BITS/2) - 1); 116 long m = MAX_BITS - x.bitLength(); 117 118 BigInteger y = ONE.shiftLeft((int)(MAX_BITS/2) - 1); 119 long n = MAX_BITS - y.bitLength(); 120 121 if (m + n != MAX_BITS) { 122 throw new RuntimeException("Unexpected leading zero sum"); 123 } 124 125 BigInteger z = x.multiply(y); 126 } 127 128 // Largest overflow detected by extra calculations. 129 @Test(expectedExceptions=ArithmeticException.class,enabled=false) multiplyIndefiniteOverflowFailure()130 public void multiplyIndefiniteOverflowFailure() { 131 BigInteger x = ONE.shiftLeft((int)(MAX_BITS/2)).subtract(ONE); 132 long m = MAX_BITS - x.bitLength(); 133 134 BigInteger y = ONE.shiftLeft((int)(MAX_BITS/2)).subtract(ONE); 135 long n = MAX_BITS - y.bitLength(); 136 137 if (m + n != MAX_BITS) { 138 throw new RuntimeException("Unexpected leading zero sum"); 139 } 140 141 BigInteger z = x.multiply(y); 142 } 143 144 // Smallest overflow detected by examining data lengths alone. 145 // BEGIN Android-changed: Test fails on Android. 146 // java.lang.OutOfMemoryError: Failed to allocate a 134217744 byte allocation ... 147 @Test(expectedExceptions=ArithmeticException.class,enabled=false) 148 // END Android-changed: Test fails on Android. multiplyDefiniteOverflow()149 public void multiplyDefiniteOverflow() { 150 // multiply by 4 as MAX_INTS_HALF refers to ints 151 byte[] xmag = new byte[4*MAX_INTS_HALF]; 152 xmag[0] = (byte)0xff; 153 BigInteger x = new BigInteger(1, xmag); 154 155 byte[] ymag = new byte[4*MAX_INTS_HALF + 1]; 156 ymag[0] = (byte)0xff; 157 BigInteger y = new BigInteger(1, ymag); 158 159 BigInteger z = x.multiply(y); 160 } 161 162 // --- exponentiation --- 163 164 @Test(expectedExceptions=ArithmeticException.class) powOverflow()165 public void powOverflow() { 166 BigInteger.TEN.pow(Integer.MAX_VALUE); 167 } 168 169 @Test(expectedExceptions=ArithmeticException.class) powOverflow1()170 public void powOverflow1() { 171 int shift = 20; 172 int exponent = 1 << shift; 173 BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent)); 174 BigInteger y = x.pow(exponent); 175 } 176 177 @Test(expectedExceptions=ArithmeticException.class) powOverflow2()178 public void powOverflow2() { 179 int shift = 20; 180 int exponent = 1 << shift; 181 BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent)).add(ONE); 182 BigInteger y = x.pow(exponent); 183 } 184 185 @Test(expectedExceptions=ArithmeticException.class,enabled=false) powOverflow3()186 public void powOverflow3() { 187 int shift = 20; 188 int exponent = 1 << shift; 189 BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent)).subtract(ONE); 190 BigInteger y = x.pow(exponent); 191 } 192 193 @Test(enabled=false) powOverflow4()194 public void powOverflow4() { 195 int shift = 20; 196 int exponent = 1 << shift; 197 BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent - 1)).add(ONE); 198 BigInteger y = x.pow(exponent); 199 } 200 } 201