1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/test/compiler/intrinsics/montgomerymultiply/MontgomeryMultiplyTest.java Fri Mar 04 16:15:48 2016 +0300 1.3 @@ -0,0 +1,278 @@ 1.4 +// 1.5 +// Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved. 1.6 +// Copyright (c) 2015, Red Hat Inc. All rights reserved. 1.7 +// DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.8 +// 1.9 +// This code is free software; you can redistribute it and/or modify it 1.10 +// under the terms of the GNU General Public License version 2 only, as 1.11 +// published by the Free Software Foundation. 1.12 +// 1.13 +// This code is distributed in the hope that it will be useful, but WITHOUT 1.14 +// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.15 +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.16 +// version 2 for more details (a copy is included in the LICENSE file that 1.17 +// accompanied this code). 1.18 +// 1.19 +// You should have received a copy of the GNU General Public License version 1.20 +// 2 along with this work; if not, write to the Free Software Foundation, 1.21 +// Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.22 +// 1.23 +// Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1.24 +// or visit www.oracle.com if you need additional information or have any 1.25 +// questions. 1.26 +// 1.27 +// 1.28 + 1.29 +import java.lang.invoke.MethodHandle; 1.30 +import java.lang.invoke.MethodHandles; 1.31 +import java.lang.invoke.MethodType; 1.32 +import java.lang.reflect.Constructor; 1.33 +import java.lang.reflect.Field; 1.34 +import java.lang.reflect.Method; 1.35 +import java.math.BigInteger; 1.36 +import java.util.Arrays; 1.37 +import java.util.Random; 1.38 + 1.39 +/** 1.40 + * @test 1.41 + * @bug 8130150 1.42 + * @library /testlibrary 1.43 + * @requires (os.simpleArch == "x64") & (os.family != "windows") 1.44 + * @summary Verify that the Montgomery multiply intrinsic works and correctly checks its arguments. 1.45 + */ 1.46 + 1.47 +public class MontgomeryMultiplyTest { 1.48 + 1.49 + static final MethodHandles.Lookup lookup = MethodHandles.lookup(); 1.50 + 1.51 + static final MethodHandle montgomeryMultiplyHandle, montgomerySquareHandle; 1.52 + static final MethodHandle bigIntegerConstructorHandle; 1.53 + static final Field bigIntegerMagField; 1.54 + 1.55 + static { 1.56 + // Use reflection to gain access to the methods we want to test. 1.57 + try { 1.58 + Method m = BigInteger.class.getDeclaredMethod("montgomeryMultiply", 1.59 + /*a*/int[].class, /*b*/int[].class, /*n*/int[].class, /*len*/int.class, 1.60 + /*inv*/long.class, /*product*/int[].class); 1.61 + m.setAccessible(true); 1.62 + montgomeryMultiplyHandle = lookup.unreflect(m); 1.63 + 1.64 + m = BigInteger.class.getDeclaredMethod("montgomerySquare", 1.65 + /*a*/int[].class, /*n*/int[].class, /*len*/int.class, 1.66 + /*inv*/long.class, /*product*/int[].class); 1.67 + m.setAccessible(true); 1.68 + montgomerySquareHandle = lookup.unreflect(m); 1.69 + 1.70 + Constructor c 1.71 + = BigInteger.class.getDeclaredConstructor(int.class, int[].class); 1.72 + c.setAccessible(true); 1.73 + bigIntegerConstructorHandle = lookup.unreflectConstructor(c); 1.74 + 1.75 + bigIntegerMagField = BigInteger.class.getDeclaredField("mag"); 1.76 + bigIntegerMagField.setAccessible(true); 1.77 + 1.78 + } catch (Throwable ex) { 1.79 + throw new RuntimeException(ex); 1.80 + } 1.81 + } 1.82 + 1.83 + // Invoke either BigInteger.montgomeryMultiply or BigInteger.montgomerySquare. 1.84 + int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv, 1.85 + int[] product) throws Throwable { 1.86 + int[] result = 1.87 + (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product) 1.88 + : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product); 1.89 + return Arrays.copyOf(result, len); 1.90 + } 1.91 + 1.92 + // Invoke the private constructor BigInteger(int[]). 1.93 + BigInteger newBigInteger(int[] val) throws Throwable { 1.94 + return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val); 1.95 + } 1.96 + 1.97 + // Get the private field BigInteger.mag 1.98 + int[] mag(BigInteger n) { 1.99 + try { 1.100 + return (int[]) bigIntegerMagField.get(n); 1.101 + } catch (Exception ex) { 1.102 + throw new RuntimeException(ex); 1.103 + } 1.104 + } 1.105 + 1.106 + // Montgomery multiplication 1.107 + // Calculate a * b * r^-1 mod n) 1.108 + // 1.109 + // R is a power of the word size 1.110 + // N' = R^-1 mod N 1.111 + // 1.112 + // T := ab 1.113 + // m := (T mod R)N' mod R [so 0 <= m < R] 1.114 + // t := (T + mN)/R 1.115 + // if t >= N then return t - N else return t 1.116 + // 1.117 + BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N, 1.118 + int len, BigInteger n_prime) 1.119 + throws Throwable { 1.120 + BigInteger T = a.multiply(b); 1.121 + BigInteger R = BigInteger.ONE.shiftLeft(len*32); 1.122 + BigInteger mask = R.subtract(BigInteger.ONE); 1.123 + BigInteger m = (T.and(mask)).multiply(n_prime); 1.124 + m = m.and(mask); // i.e. m.mod(R) 1.125 + T = T.add(m.multiply(N)); 1.126 + T = T.shiftRight(len*32); // i.e. T.divide(R) 1.127 + if (T.compareTo(N) > 0) { 1.128 + T = T.subtract(N); 1.129 + } 1.130 + return T; 1.131 + } 1.132 + 1.133 + // Call the Montgomery multiply intrinsic. 1.134 + BigInteger montgomeryMultiply(int[] a_words, int[] b_words, int[] n_words, 1.135 + int len, BigInteger inv) 1.136 + throws Throwable { 1.137 + BigInteger t = montgomeryMultiply( 1.138 + newBigInteger(a_words), 1.139 + newBigInteger(b_words), 1.140 + newBigInteger(n_words), 1.141 + len, inv); 1.142 + return t; 1.143 + } 1.144 + 1.145 + // Check that the Montgomery multiply intrinsic returns the same 1.146 + // result as the longhand calculation. 1.147 + void check(int[] a_words, int[] b_words, int[] n_words, int len, BigInteger inv) 1.148 + throws Throwable { 1.149 + BigInteger n = newBigInteger(n_words); 1.150 + BigInteger slow = montgomeryMultiply(a_words, b_words, n_words, len, inv); 1.151 + BigInteger fast 1.152 + = newBigInteger(montgomeryMultiply 1.153 + (a_words, b_words, n_words, len, inv.longValue(), null)); 1.154 + // The intrinsic may not return the same value as the longhand 1.155 + // calculation but they must have the same residue mod N. 1.156 + if (!slow.mod(n).equals(fast.mod(n))) { 1.157 + throw new RuntimeException(); 1.158 + } 1.159 + } 1.160 + 1.161 + Random rnd = new Random(0); 1.162 + 1.163 + // Return a random value of length <= bits in an array of even length 1.164 + int[] random_val(int bits) { 1.165 + int len = (bits+63)/64; // i.e. length in longs 1.166 + int[] val = new int[len*2]; 1.167 + for (int i = 0; i < val.length; i++) 1.168 + val[i] = rnd.nextInt(); 1.169 + int leadingZeros = 64 - (bits & 64); 1.170 + if (leadingZeros >= 32) { 1.171 + val[0] = 0; 1.172 + val[1] &= ~(-1l << (leadingZeros & 31)); 1.173 + } else { 1.174 + val[0] &= ~(-1l << leadingZeros); 1.175 + } 1.176 + return val; 1.177 + } 1.178 + 1.179 + void testOneLength(int lenInBits, int lenInInts) throws Throwable { 1.180 + BigInteger mod = new BigInteger(lenInBits, 2, rnd); 1.181 + BigInteger r = BigInteger.ONE.shiftLeft(lenInInts * 32); 1.182 + BigInteger n_prime = mod.modInverse(r).negate(); 1.183 + 1.184 + // Make n.length even, padding with a zero if necessary 1.185 + int[] n = mag(mod); 1.186 + if (n.length < lenInInts) { 1.187 + int[] x = new int[lenInInts]; 1.188 + System.arraycopy(n, 0, x, lenInInts-n.length, n.length); 1.189 + n = x; 1.190 + } 1.191 + 1.192 + for (int i = 0; i < 10000; i++) { 1.193 + // multiply 1.194 + check(random_val(lenInBits), random_val(lenInBits), n, lenInInts, n_prime); 1.195 + // square 1.196 + int[] tmp = random_val(lenInBits); 1.197 + check(tmp, tmp, n, lenInInts, n_prime); 1.198 + } 1.199 + } 1.200 + 1.201 + // Test the Montgomery multiply intrinsic with a bunch of random 1.202 + // values of varying lengths. Do this for long enough that the 1.203 + // caller of the intrinsic is C2-compiled. 1.204 + void testResultValues() throws Throwable { 1.205 + // Test a couple of interesting edge cases. 1.206 + testOneLength(1024, 32); 1.207 + testOneLength(1025, 34); 1.208 + for (int j = 10; j > 0; j--) { 1.209 + // Construct a random prime whose length in words is even 1.210 + int lenInBits = rnd.nextInt(2048) + 64; 1.211 + int lenInInts = (lenInBits + 63)/64*2; 1.212 + testOneLength(lenInBits, lenInInts); 1.213 + } 1.214 + } 1.215 + 1.216 + // Range checks 1.217 + void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv, 1.218 + int[] product, Class klass) { 1.219 + try { 1.220 + montgomeryMultiply(a, b, n, len, inv, product); 1.221 + } catch (Throwable ex) { 1.222 + if (klass.isAssignableFrom(ex.getClass())) 1.223 + return; 1.224 + throw new RuntimeException(klass + " expected, " + ex + " was thrown"); 1.225 + } 1.226 + throw new RuntimeException(klass + " expected, was not thrown"); 1.227 + } 1.228 + 1.229 + void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv, 1.230 + Class klass) { 1.231 + testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass); 1.232 + } 1.233 + 1.234 + void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv, 1.235 + int[] product, Class klass) { 1.236 + testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass); 1.237 + } 1.238 + 1.239 + void testMontgomeryMultiplyChecks() { 1.240 + int[] blah = random_val(40); 1.241 + int[] small = random_val(39); 1.242 + BigInteger mod = new BigInteger(40*32 , 2, rnd); 1.243 + BigInteger r = BigInteger.ONE.shiftLeft(40*32); 1.244 + BigInteger n_prime = mod.modInverse(r).negate(); 1.245 + 1.246 + // Length out of range: square 1.247 + testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class); 1.248 + testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class); 1.249 + testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class); 1.250 + // As above, but for multiply 1.251 + testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class); 1.252 + testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class); 1.253 + testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class); 1.254 + 1.255 + // Length odd 1.256 + testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class); 1.257 + testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class); 1.258 + testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class); 1.259 + // As above, but for multiply 1.260 + testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class); 1.261 + testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class); 1.262 + testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class); 1.263 + 1.264 + // array too small 1.265 + testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class); 1.266 + testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class); 1.267 + testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class); 1.268 + testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class); 1.269 + testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class); 1.270 + testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class); 1.271 + } 1.272 + 1.273 + public static void main(String args[]) { 1.274 + try { 1.275 + new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks(); 1.276 + new MontgomeryMultiplyTest().testResultValues(); 1.277 + } catch (Throwable ex) { 1.278 + throw new RuntimeException(ex); 1.279 + } 1.280 + } 1.281 +}