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 import java.math.BigInteger;
32 import static java.math.BigInteger.ONE;
33 import org.testng.annotations.Test;
34 
35 //
36 // The intent of this test is to probe the boundaries between overflow and
37 // non-overflow, principally for multiplication and squaring, specifically
38 // the largest values which should not overflow and the smallest values which
39 // should. The transition values used are not necessarily at the exact
40 // boundaries but should be "close." Quite a few different values were used
41 // experimentally before settling on the ones in this test. For multiplication
42 // and squaring all cases are exercised: definite overflow and non-overflow
43 // which can be detected "up front," and "indefinite" overflow, i.e., overflow
44 // which cannot be detected up front so further calculations are required.
45 //
46 // Testing negative values is unnecessary. For both multiplication and squaring
47 // the paths lead to the Toom-Cook algorithm where the signum is used only to
48 // determine the sign of the result and not in the intermediate calculations.
49 // This is also true for exponentiation.
50 //
51 // @Test annotations with optional element "enabled" set to "false" should
52 // succeed when "enabled" is set to "true" but they take too to run in the
53 // course of the typical regression test execution scenario.
54 //
55 public class LargeValueExceptions {
56     // BigInteger.MAX_MAG_LENGTH
57     private static final int MAX_INTS = 1 << 26;
58 
59     // Number of bits corresponding to MAX_INTS
60     private static final long MAX_BITS = (0xffffffffL & MAX_INTS) << 5L;
61 
62     // Half BigInteger.MAX_MAG_LENGTH
63     private static final int MAX_INTS_HALF = MAX_INTS / 2;
64 
65     // --- squaring ---
66 
67     // Largest no overflow determined by examining data lengths alone.
68     @Test(enabled=false)
squareNoOverflow()69     public void squareNoOverflow() {
70         BigInteger x = ONE.shiftLeft(16*MAX_INTS - 1).subtract(ONE);
71         BigInteger y = x.multiply(x);
72     }
73 
74     // Smallest no overflow determined by extra calculations.
75     @Test(enabled=false)
squareIndefiniteOverflowSuccess()76     public void squareIndefiniteOverflowSuccess() {
77         BigInteger x = ONE.shiftLeft(16*MAX_INTS - 1);
78         BigInteger y = x.multiply(x);
79     }
80 
81     // Largest overflow detected by extra calculations.
82     @Test(expectedExceptions=ArithmeticException.class,enabled=false)
squareIndefiniteOverflowFailure()83     public void squareIndefiniteOverflowFailure() {
84         BigInteger x = ONE.shiftLeft(16*MAX_INTS).subtract(ONE);
85         BigInteger y = x.multiply(x);
86     }
87 
88     // Smallest overflow detected by examining data lengths alone.
89     @Test(expectedExceptions=ArithmeticException.class)
squareDefiniteOverflow()90     public void squareDefiniteOverflow() {
91         BigInteger x = ONE.shiftLeft(16*MAX_INTS);
92         BigInteger y = x.multiply(x);
93     }
94 
95     // --- multiplication ---
96 
97     // Largest no overflow determined by examining data lengths alone.
98     @Test(enabled=false)
multiplyNoOverflow()99     public void multiplyNoOverflow() {
100         final int halfMaxBits = MAX_INTS_HALF << 5;
101 
102         BigInteger x = ONE.shiftLeft(halfMaxBits).subtract(ONE);
103         BigInteger y = ONE.shiftLeft(halfMaxBits - 1).subtract(ONE);
104         BigInteger z = x.multiply(y);
105     }
106 
107     // Smallest no overflow determined by extra calculations.
108     @Test(enabled=false)
multiplyIndefiniteOverflowSuccess()109     public void multiplyIndefiniteOverflowSuccess() {
110         BigInteger x = ONE.shiftLeft((int)(MAX_BITS/2) - 1);
111         long m = MAX_BITS - x.bitLength();
112 
113         BigInteger y = ONE.shiftLeft((int)(MAX_BITS/2) - 1);
114         long n = MAX_BITS - y.bitLength();
115 
116         if (m + n != MAX_BITS) {
117             throw new RuntimeException("Unexpected leading zero sum");
118         }
119 
120         BigInteger z = x.multiply(y);
121     }
122 
123     // Largest overflow detected by extra calculations.
124     @Test(expectedExceptions=ArithmeticException.class,enabled=false)
multiplyIndefiniteOverflowFailure()125     public void multiplyIndefiniteOverflowFailure() {
126         BigInteger x = ONE.shiftLeft((int)(MAX_BITS/2)).subtract(ONE);
127         long m = MAX_BITS - x.bitLength();
128 
129         BigInteger y = ONE.shiftLeft((int)(MAX_BITS/2)).subtract(ONE);
130         long n = MAX_BITS - y.bitLength();
131 
132         if (m + n != MAX_BITS) {
133             throw new RuntimeException("Unexpected leading zero sum");
134         }
135 
136         BigInteger z = x.multiply(y);
137     }
138 
139     // Smallest overflow detected by examining data lengths alone.
140     @Test(expectedExceptions=ArithmeticException.class)
multiplyDefiniteOverflow()141     public void multiplyDefiniteOverflow() {
142         // multiply by 4 as MAX_INTS_HALF refers to ints
143         byte[] xmag = new byte[4*MAX_INTS_HALF];
144         xmag[0] = (byte)0xff;
145         BigInteger x = new BigInteger(1, xmag);
146 
147         byte[] ymag = new byte[4*MAX_INTS_HALF + 1];
148         ymag[0] = (byte)0xff;
149         BigInteger y = new BigInteger(1, ymag);
150 
151         BigInteger z = x.multiply(y);
152     }
153 
154     // --- exponentiation ---
155 
156     @Test(expectedExceptions=ArithmeticException.class)
powOverflow()157     public void powOverflow() {
158         BigInteger.TEN.pow(Integer.MAX_VALUE);
159     }
160 
161     @Test(expectedExceptions=ArithmeticException.class)
powOverflow1()162     public void powOverflow1() {
163         int shift = 20;
164         int exponent = 1 << shift;
165         BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent));
166         BigInteger y = x.pow(exponent);
167     }
168 
169     @Test(expectedExceptions=ArithmeticException.class)
powOverflow2()170     public void powOverflow2() {
171         int shift = 20;
172         int exponent = 1 << shift;
173         BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent)).add(ONE);
174         BigInteger y = x.pow(exponent);
175     }
176 
177     @Test(expectedExceptions=ArithmeticException.class,enabled=false)
powOverflow3()178     public void powOverflow3() {
179         int shift = 20;
180         int exponent = 1 << shift;
181         BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent)).subtract(ONE);
182         BigInteger y = x.pow(exponent);
183     }
184 
185     @Test(enabled=false)
powOverflow4()186     public void powOverflow4() {
187         int shift = 20;
188         int exponent = 1 << shift;
189         BigInteger x = ONE.shiftLeft((int)(MAX_BITS / exponent - 1)).add(ONE);
190         BigInteger y = x.pow(exponent);
191     }
192 }
193