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