vkempik@8318: //
vkempik@8318: // Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
vkempik@8318: // Copyright (c) 2015, Red Hat Inc. All rights reserved.
vkempik@8318: // DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
vkempik@8318: //
vkempik@8318: // This code is free software; you can redistribute it and/or modify it
vkempik@8318: // under the terms of the GNU General Public License version 2 only, as
vkempik@8318: // published by the Free Software Foundation.
vkempik@8318: //
vkempik@8318: // This code is distributed in the hope that it will be useful, but WITHOUT
vkempik@8318: // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
vkempik@8318: // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
vkempik@8318: // version 2 for more details (a copy is included in the LICENSE file that
vkempik@8318: // accompanied this code).
vkempik@8318: //
vkempik@8318: // You should have received a copy of the GNU General Public License version
vkempik@8318: // 2 along with this work; if not, write to the Free Software Foundation,
vkempik@8318: // Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
vkempik@8318: //
vkempik@8318: // Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
vkempik@8318: // or visit www.oracle.com if you need additional information or have any
vkempik@8318: // questions.
vkempik@8318: //
vkempik@8318: //
vkempik@8318: 
vkempik@8318: import java.lang.invoke.MethodHandle;
vkempik@8318: import java.lang.invoke.MethodHandles;
vkempik@8318: import java.lang.invoke.MethodType;
vkempik@8318: import java.lang.reflect.Constructor;
vkempik@8318: import java.lang.reflect.Field;
vkempik@8318: import java.lang.reflect.Method;
vkempik@8318: import java.math.BigInteger;
vkempik@8318: import java.util.Arrays;
vkempik@8318: import java.util.Random;
vkempik@8318: 
vkempik@8318: /**
vkempik@8318:  * @test
vkempik@8318:  * @bug 8130150
vkempik@8318:  * @library /testlibrary
vkempik@8318:  * @requires (os.simpleArch == "x64") & (os.family != "windows")
vkempik@8318:  * @summary Verify that the Montgomery multiply intrinsic works and correctly checks its arguments.
vkempik@8318:  */
vkempik@8318: 
vkempik@8318: public class MontgomeryMultiplyTest {
vkempik@8318: 
vkempik@8318:     static final MethodHandles.Lookup lookup = MethodHandles.lookup();
vkempik@8318: 
vkempik@8318:     static final MethodHandle montgomeryMultiplyHandle, montgomerySquareHandle;
vkempik@8318:     static final MethodHandle bigIntegerConstructorHandle;
vkempik@8318:     static final Field bigIntegerMagField;
vkempik@8318: 
vkempik@8318:     static {
vkempik@8318:        // Use reflection to gain access to the methods we want to test.
vkempik@8318:         try {
vkempik@8318:             Method m = BigInteger.class.getDeclaredMethod("montgomeryMultiply",
vkempik@8318:                 /*a*/int[].class, /*b*/int[].class, /*n*/int[].class, /*len*/int.class,
vkempik@8318:                 /*inv*/long.class, /*product*/int[].class);
vkempik@8318:             m.setAccessible(true);
vkempik@8318:             montgomeryMultiplyHandle = lookup.unreflect(m);
vkempik@8318: 
vkempik@8318:             m = BigInteger.class.getDeclaredMethod("montgomerySquare",
vkempik@8318:                 /*a*/int[].class, /*n*/int[].class, /*len*/int.class,
vkempik@8318:                 /*inv*/long.class, /*product*/int[].class);
vkempik@8318:             m.setAccessible(true);
vkempik@8318:             montgomerySquareHandle = lookup.unreflect(m);
vkempik@8318: 
vkempik@8318:             Constructor c
vkempik@8318:                 = BigInteger.class.getDeclaredConstructor(int.class, int[].class);
vkempik@8318:             c.setAccessible(true);
vkempik@8318:             bigIntegerConstructorHandle = lookup.unreflectConstructor(c);
vkempik@8318: 
vkempik@8318:             bigIntegerMagField = BigInteger.class.getDeclaredField("mag");
vkempik@8318:             bigIntegerMagField.setAccessible(true);
vkempik@8318: 
vkempik@8318:         } catch (Throwable ex) {
vkempik@8318:             throw new RuntimeException(ex);
vkempik@8318:         }
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Invoke either BigInteger.montgomeryMultiply or BigInteger.montgomerySquare.
vkempik@8318:     int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv,
vkempik@8318:                              int[] product) throws Throwable {
vkempik@8318:         int[] result =
vkempik@8318:             (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product)
vkempik@8318:                      : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product);
vkempik@8318:         return Arrays.copyOf(result, len);
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Invoke the private constructor BigInteger(int[]).
vkempik@8318:     BigInteger newBigInteger(int[] val) throws Throwable {
vkempik@8318:         return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val);
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Get the private field BigInteger.mag
vkempik@8318:     int[] mag(BigInteger n) {
vkempik@8318:         try {
vkempik@8318:             return (int[]) bigIntegerMagField.get(n);
vkempik@8318:         } catch (Exception ex) {
vkempik@8318:             throw new RuntimeException(ex);
vkempik@8318:         }
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Montgomery multiplication
vkempik@8318:     // Calculate a * b * r^-1 mod n)
vkempik@8318:     //
vkempik@8318:     // R is a power of the word size
vkempik@8318:     // N' = R^-1 mod N
vkempik@8318:     //
vkempik@8318:     // T := ab
vkempik@8318:     // m := (T mod R)N' mod R [so 0 <= m < R]
vkempik@8318:     // t := (T + mN)/R
vkempik@8318:     // if t >= N then return t - N else return t
vkempik@8318:     //
vkempik@8318:     BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N,
vkempik@8318:             int len, BigInteger n_prime)
vkempik@8318:             throws Throwable {
vkempik@8318:         BigInteger T = a.multiply(b);
vkempik@8318:         BigInteger R = BigInteger.ONE.shiftLeft(len*32);
vkempik@8318:         BigInteger mask = R.subtract(BigInteger.ONE);
vkempik@8318:         BigInteger m = (T.and(mask)).multiply(n_prime);
vkempik@8318:         m = m.and(mask); // i.e. m.mod(R)
vkempik@8318:         T = T.add(m.multiply(N));
vkempik@8318:         T = T.shiftRight(len*32); // i.e. T.divide(R)
vkempik@8318:         if (T.compareTo(N) > 0) {
vkempik@8318:             T = T.subtract(N);
vkempik@8318:         }
vkempik@8318:         return T;
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Call the Montgomery multiply intrinsic.
vkempik@8318:     BigInteger montgomeryMultiply(int[] a_words, int[] b_words, int[] n_words,
vkempik@8318:             int len, BigInteger inv)
vkempik@8318:             throws Throwable {
vkempik@8318:         BigInteger t = montgomeryMultiply(
vkempik@8318:                 newBigInteger(a_words),
vkempik@8318:                 newBigInteger(b_words),
vkempik@8318:                 newBigInteger(n_words),
vkempik@8318:                 len, inv);
vkempik@8318:         return t;
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Check that the Montgomery multiply intrinsic returns the same
vkempik@8318:     // result as the longhand calculation.
vkempik@8318:     void check(int[] a_words, int[] b_words, int[] n_words, int len, BigInteger inv)
vkempik@8318:             throws Throwable {
vkempik@8318:         BigInteger n = newBigInteger(n_words);
vkempik@8318:         BigInteger slow = montgomeryMultiply(a_words, b_words, n_words, len, inv);
vkempik@8318:         BigInteger fast
vkempik@8318:             = newBigInteger(montgomeryMultiply
vkempik@8318:                             (a_words, b_words, n_words, len, inv.longValue(), null));
vkempik@8318:         // The intrinsic may not return the same value as the longhand
vkempik@8318:         // calculation but they must have the same residue mod N.
vkempik@8318:         if (!slow.mod(n).equals(fast.mod(n))) {
vkempik@8318:             throw new RuntimeException();
vkempik@8318:         }
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     Random rnd = new Random(0);
vkempik@8318: 
vkempik@8318:     // Return a random value of length <= bits in an array of even length
vkempik@8318:     int[] random_val(int bits) {
vkempik@8318:         int len = (bits+63)/64;  // i.e. length in longs
vkempik@8318:         int[] val = new int[len*2];
vkempik@8318:         for (int i = 0; i < val.length; i++)
vkempik@8318:             val[i] = rnd.nextInt();
vkempik@8318:         int leadingZeros = 64 - (bits & 64);
vkempik@8318:         if (leadingZeros >= 32) {
vkempik@8318:             val[0] = 0;
vkempik@8318:             val[1] &= ~(-1l << (leadingZeros & 31));
vkempik@8318:         } else {
vkempik@8318:             val[0] &= ~(-1l << leadingZeros);
vkempik@8318:         }
vkempik@8318:         return val;
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     void testOneLength(int lenInBits, int lenInInts) throws Throwable {
vkempik@8318:         BigInteger mod = new BigInteger(lenInBits, 2, rnd);
vkempik@8318:         BigInteger r = BigInteger.ONE.shiftLeft(lenInInts * 32);
vkempik@8318:         BigInteger n_prime = mod.modInverse(r).negate();
vkempik@8318: 
vkempik@8318:         // Make n.length even, padding with a zero if necessary
vkempik@8318:         int[] n = mag(mod);
vkempik@8318:         if (n.length < lenInInts) {
vkempik@8318:             int[] x = new int[lenInInts];
vkempik@8318:             System.arraycopy(n, 0, x, lenInInts-n.length, n.length);
vkempik@8318:             n = x;
vkempik@8318:         }
vkempik@8318: 
vkempik@8318:         for (int i = 0; i < 10000; i++) {
vkempik@8318:             // multiply
vkempik@8318:             check(random_val(lenInBits), random_val(lenInBits), n, lenInInts, n_prime);
vkempik@8318:             // square
vkempik@8318:             int[] tmp = random_val(lenInBits);
vkempik@8318:             check(tmp, tmp, n, lenInInts, n_prime);
vkempik@8318:         }
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Test the Montgomery multiply intrinsic with a bunch of random
vkempik@8318:     // values of varying lengths.  Do this for long enough that the
vkempik@8318:     // caller of the intrinsic is C2-compiled.
vkempik@8318:     void testResultValues() throws Throwable {
vkempik@8318:         // Test a couple of interesting edge cases.
vkempik@8318:         testOneLength(1024, 32);
vkempik@8318:         testOneLength(1025, 34);
vkempik@8318:         for (int j = 10; j > 0; j--) {
vkempik@8318:             // Construct a random prime whose length in words is even
vkempik@8318:             int lenInBits = rnd.nextInt(2048) + 64;
vkempik@8318:             int lenInInts = (lenInBits + 63)/64*2;
vkempik@8318:             testOneLength(lenInBits, lenInInts);
vkempik@8318:         }
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     // Range checks
vkempik@8318:     void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv,
vkempik@8318:                                         int[] product, Class klass) {
vkempik@8318:         try {
vkempik@8318:             montgomeryMultiply(a, b, n, len, inv, product);
vkempik@8318:         } catch (Throwable ex) {
vkempik@8318:             if (klass.isAssignableFrom(ex.getClass()))
vkempik@8318:                 return;
vkempik@8318:             throw new RuntimeException(klass + " expected, " + ex + " was thrown");
vkempik@8318:         }
vkempik@8318:         throw new RuntimeException(klass + " expected, was not thrown");
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
vkempik@8318:             Class klass) {
vkempik@8318:         testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass);
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
vkempik@8318:             int[] product, Class klass) {
vkempik@8318:         testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass);
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     void testMontgomeryMultiplyChecks() {
vkempik@8318:         int[] blah = random_val(40);
vkempik@8318:         int[] small = random_val(39);
vkempik@8318:         BigInteger mod = new BigInteger(40*32 , 2, rnd);
vkempik@8318:         BigInteger r = BigInteger.ONE.shiftLeft(40*32);
vkempik@8318:         BigInteger n_prime = mod.modInverse(r).negate();
vkempik@8318: 
vkempik@8318:         // Length out of range: square
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class);
vkempik@8318:         // As above, but for multiply
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
vkempik@8318: 
vkempik@8318:         // Length odd
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class);
vkempik@8318:         // As above, but for multiply
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class);
vkempik@8318: 
vkempik@8318:         // array too small
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
vkempik@8318:         testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
vkempik@8318:     }
vkempik@8318: 
vkempik@8318:     public static void main(String args[]) {
vkempik@8318:         try {
vkempik@8318:             new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks();
vkempik@8318:             new MontgomeryMultiplyTest().testResultValues();
vkempik@8318:         } catch (Throwable ex) {
vkempik@8318:             throw new RuntimeException(ex);
vkempik@8318:         }
vkempik@8318:      }
vkempik@8318: }