1 /*
2 * Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2015, Red Hat Inc. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /**
26 * @test
27 * @bug 8130150 8131779 8139907
28 * @summary Verify that the Montgomery multiply and square intrinsic works and correctly checks their arguments.
29 * @requires vm.flavor == "server"
30 * @modules java.base/jdk.internal.misc
31 * @library /test/lib
32 *
33 * @build sun.hotspot.WhiteBox
34 * @run driver ClassFileInstaller sun.hotspot.WhiteBox
35 * sun.hotspot.WhiteBox$WhiteBoxPermission
36 * @run main/othervm -Xbootclasspath/a:. -XX:+UnlockDiagnosticVMOptions -XX:+WhiteBoxAPI
37 * compiler.intrinsics.bigInteger.MontgomeryMultiplyTest
38 */
39
40 package compiler.intrinsics.bigInteger;
41
42 import jdk.test.lib.Platform;
43 import sun.hotspot.WhiteBox;
44
45 import java.lang.invoke.MethodHandle;
46 import java.lang.invoke.MethodHandles;
47 import java.lang.reflect.Constructor;
48 import java.lang.reflect.Executable;
49 import java.lang.reflect.Field;
50 import java.lang.reflect.Method;
51 import java.math.BigInteger;
52 import java.util.Arrays;
53 import java.util.Random;
54
55 public class MontgomeryMultiplyTest {
56
57 private static final WhiteBox wb = WhiteBox.getWhiteBox();
58
59 /* Compilation level corresponding to C2. */
60 private static final int COMP_LEVEL_FULL_OPTIMIZATION = 4;
61
62 static final MethodHandles.Lookup lookup = MethodHandles.lookup();
63
64 static final MethodHandle montgomeryMultiplyHandle, montgomerySquareHandle;
65 static final MethodHandle bigIntegerConstructorHandle;
66 static final Field bigIntegerMagField;
67
68 static {
69 // Use reflection to gain access to the methods we want to test.
70 try {
71 Method m = BigInteger.class.getDeclaredMethod("montgomeryMultiply",
72 /*a*/int[].class, /*b*/int[].class, /*n*/int[].class, /*len*/int.class,
73 /*inv*/long.class, /*product*/int[].class);
74 m.setAccessible(true);
75 montgomeryMultiplyHandle = lookup.unreflect(m);
76
77 m = BigInteger.class.getDeclaredMethod("montgomerySquare",
78 /*a*/int[].class, /*n*/int[].class, /*len*/int.class,
79 /*inv*/long.class, /*product*/int[].class);
80 m.setAccessible(true);
81 montgomerySquareHandle = lookup.unreflect(m);
82
83 Constructor c
84 = BigInteger.class.getDeclaredConstructor(int.class, int[].class);
85 c.setAccessible(true);
86 bigIntegerConstructorHandle = lookup.unreflectConstructor(c);
87
88 bigIntegerMagField = BigInteger.class.getDeclaredField("mag");
89 bigIntegerMagField.setAccessible(true);
90
91 } catch (Throwable ex) {
92 throw new RuntimeException(ex);
93 }
94 }
95
96 /* Obtain executable for the intrinsics tested. Depending on the
97 * value of 'isMultiply', the executable corresponding to either
98 * implMontgomerMultiply or implMontgomerySqure is returned. */
99 static Executable getExecutable(boolean isMultiply) throws RuntimeException {
100 try {
101 Class aClass = Class.forName("java.math.BigInteger");
102 Method aMethod;
103 if (isMultiply) {
104 aMethod = aClass.getDeclaredMethod("implMontgomeryMultiply",
105 int[].class,
106 int[].class,
107 int[].class,
108 int.class,
109 long.class,
110 int[].class);
111 } else {
112 aMethod = aClass.getDeclaredMethod("implMontgomerySquare",
113 int[].class,
114 int[].class,
115 int.class,
116 long.class,
117 int[].class);
118 }
119 return aMethod;
120 } catch (NoSuchMethodException e) {
121 throw new RuntimeException("Test bug, method is unavailable. " + e);
122 } catch (ClassNotFoundException e) {
123 throw new RuntimeException("Test bug, class is unavailable. " + e);
124 }
125 }
126
127 // Invoke either BigInteger.montgomeryMultiply or BigInteger.montgomerySquare.
128 int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv,
129 int[] product) throws Throwable {
130 int[] result =
131 (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product)
132 : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product);
133 return Arrays.copyOf(result, len);
134 }
135
136 // Invoke the private constructor BigInteger(int[]).
137 BigInteger newBigInteger(int[] val) throws Throwable {
138 return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val);
139 }
140
141 // Get the private field BigInteger.mag
142 int[] mag(BigInteger n) {
143 try {
144 return (int[]) bigIntegerMagField.get(n);
145 } catch (Exception ex) {
146 throw new RuntimeException(ex);
147 }
148 }
149
150 // Montgomery multiplication
151 // Calculate a * b * r^-1 mod n)
152 //
153 // R is a power of the word size
154 // N' = R^-1 mod N
155 //
156 // T := ab
157 // m := (T mod R)N' mod R [so 0 <= m < R]
158 // t := (T + mN)/R
159 // if t >= N then return t - N else return t
160 //
161 BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N,
162 int len, BigInteger n_prime)
163 throws Throwable {
164 BigInteger T = a.multiply(b);
165 BigInteger R = BigInteger.ONE.shiftLeft(len*32);
166 BigInteger mask = R.subtract(BigInteger.ONE);
167 BigInteger m = (T.and(mask)).multiply(n_prime);
168 m = m.and(mask); // i.e. m.mod(R)
169 T = T.add(m.multiply(N));
170 T = T.shiftRight(len*32); // i.e. T.divide(R)
171 if (T.compareTo(N) > 0) {
172 T = T.subtract(N);
173 }
174 return T;
175 }
176
177 // Call the Montgomery multiply intrinsic.
178 BigInteger montgomeryMultiply(int[] a_words, int[] b_words, int[] n_words,
179 int len, BigInteger inv)
180 throws Throwable {
181 BigInteger t = montgomeryMultiply(
182 newBigInteger(a_words),
183 newBigInteger(b_words),
184 newBigInteger(n_words),
185 len, inv);
186 return t;
187 }
188
189 // Check that the Montgomery multiply intrinsic returns the same
190 // result as the longhand calculation.
191 void check(int[] a_words, int[] b_words, int[] n_words, int len, BigInteger inv)
192 throws Throwable {
193 BigInteger n = newBigInteger(n_words);
194 BigInteger slow = montgomeryMultiply(a_words, b_words, n_words, len, inv);
195 BigInteger fast
196 = newBigInteger(montgomeryMultiply
197 (a_words, b_words, n_words, len, inv.longValue(), null));
198 // The intrinsic may not return the same value as the longhand
199 // calculation but they must have the same residue mod N.
200 if (!slow.mod(n).equals(fast.mod(n))) {
201 throw new RuntimeException();
202 }
203 }
204
205 Random rnd = new Random(0);
206
207 // Return a random value of length <= bits in an array of even length
208 int[] random_val(int bits) {
209 int len = (bits+63)/64; // i.e. length in longs
210 int[] val = new int[len*2];
211 for (int i = 0; i < val.length; i++)
212 val[i] = rnd.nextInt();
213 int leadingZeros = 64 - (bits & 64);
214 if (leadingZeros >= 32) {
215 val[0] = 0;
216 val[1] &= ~(-1l << (leadingZeros & 31));
217 } else {
218 val[0] &= ~(-1l << leadingZeros);
219 }
220 return val;
221 }
222
223 void testOneLength(int lenInBits, int lenInInts) throws Throwable {
224 BigInteger mod = new BigInteger(lenInBits, 2, rnd);
225 BigInteger r = BigInteger.ONE.shiftLeft(lenInInts * 32);
226 BigInteger n_prime = mod.modInverse(r).negate();
227
228 // Make n.length even, padding with a zero if necessary
229 int[] n = mag(mod);
230 if (n.length < lenInInts) {
231 int[] x = new int[lenInInts];
232 System.arraycopy(n, 0, x, lenInInts-n.length, n.length);
233 n = x;
234 }
235
236 for (int i = 0; i < 10000; i++) {
237 // multiply
238 check(random_val(lenInBits), random_val(lenInBits), n, lenInInts, n_prime);
239 // square
240 int[] tmp = random_val(lenInBits);
241 check(tmp, tmp, n, lenInInts, n_prime);
242 }
243 }
244
245 // Test the Montgomery multiply intrinsic with a bunch of random
246 // values of varying lengths. Do this for long enough that the
247 // caller of the intrinsic is C2-compiled.
248 void testResultValues() throws Throwable {
249 // Test a couple of interesting edge cases.
250 testOneLength(1024, 32);
251 testOneLength(1025, 34);
252 for (int j = 10; j > 0; j--) {
253 // Construct a random prime whose length in words is even
254 int lenInBits = rnd.nextInt(2048) + 64;
255 int lenInInts = (lenInBits + 63)/64*2;
256 testOneLength(lenInBits, lenInInts);
257 }
258 }
259
260 // Range checks
261 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv,
262 int[] product, Class klass) {
263 try {
264 montgomeryMultiply(a, b, n, len, inv, product);
265 } catch (Throwable ex) {
266 if (klass.isAssignableFrom(ex.getClass()))
267 return;
268 throw new RuntimeException(klass + " expected, " + ex + " was thrown");
269 }
270 throw new RuntimeException(klass + " expected, was not thrown");
271 }
272
273 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
274 Class klass) {
275 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass);
276 }
277
278 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
279 int[] product, Class klass) {
280 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass);
281 }
282
283 void testMontgomeryMultiplyChecks() {
284 int[] blah = random_val(40);
285 int[] small = random_val(39);
286 BigInteger mod = new BigInteger(40*32 , 2, rnd);
287 BigInteger r = BigInteger.ONE.shiftLeft(40*32);
288 BigInteger n_prime = mod.modInverse(r).negate();
289
290 // Length out of range: square
291 testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class);
292 testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class);
293 testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class);
294 // As above, but for multiply
295 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class);
296 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
297 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
298
299 // Length odd
300 testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class);
301 testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class);
302 testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class);
303 // As above, but for multiply
304 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class);
305 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class);
306 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class);
307
308 // array too small
309 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
310 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class);
311 testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class);
312 testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
313 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
314 testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
315 }
316
317 public static void main(String args[]) {
318 if (!Platform.isServer()) {
319 throw new Error("TESTBUG: Not server VM");
320 }
321 if (wb.isIntrinsicAvailable(getExecutable(true), COMP_LEVEL_FULL_OPTIMIZATION) &&
322 wb.isIntrinsicAvailable(getExecutable(false), COMP_LEVEL_FULL_OPTIMIZATION)) {
323 try {
324 new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks();
325 new MontgomeryMultiplyTest().testResultValues();
326 } catch (Throwable ex) {
327 throw new RuntimeException(ex);
328 }
329 }
330 }
331 }