8130150: Implement BigInteger.montgomeryMultiply intrinsic

Reviewed-by: kvn, mdoerr

1 files changed, 278 insertions, 0 deletions

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