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