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