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