jdk8-mips64-public/hotspot: test/compiler/intrinsics/montgomerymultiply/MontgomeryMultiplyTest.java@0cd040567d60

     1 //

     2 // Copyright (c) 2000, 2015, 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 //

    26 import java.lang.invoke.MethodHandle;

    27 import java.lang.invoke.MethodHandles;

    28 import java.lang.invoke.MethodType;

    29 import java.lang.reflect.Constructor;

    30 import java.lang.reflect.Field;

    31 import java.lang.reflect.Method;

    32 import java.math.BigInteger;

    33 import java.util.Arrays;

    34 import java.util.Random;

    36 /**

    37  * @test

    38  * @bug 8130150

    39  * @library /testlibrary

    40  * @requires (os.simpleArch == "x64") & (os.family != "windows")

    41  * @summary Verify that the Montgomery multiply intrinsic works and correctly checks its arguments.

    42  * @run main/othervm -XX:+UseMontgomerySquareIntrinsic -XX:+UseMontgomeryMultiplyIntrinsic

    43  *      MontgomeryMultiplyTest

    44  * @run main/othervm -XX:+UseMontgomerySquareIntrinsic -XX:-UseMontgomeryMultiplyIntrinsic

    45  *      MontgomeryMultiplyTest

    46  * @run main/othervm -XX:-UseMontgomerySquareIntrinsic -XX:+UseMontgomeryMultiplyIntrinsic

    47  *      MontgomeryMultiplyTest

    48  */

    50 public class MontgomeryMultiplyTest {

    52     static final MethodHandles.Lookup lookup = MethodHandles.lookup();

    54     static final MethodHandle montgomeryMultiplyHandle, montgomerySquareHandle;

    55     static final MethodHandle bigIntegerConstructorHandle;

    56     static final Field bigIntegerMagField;

    58     static {

    59        // Use reflection to gain access to the methods we want to test.

    60         try {

    61             Method m = BigInteger.class.getDeclaredMethod("montgomeryMultiply",

    62                 /*a*/int[].class, /*b*/int[].class, /*n*/int[].class, /*len*/int.class,

    63                 /*inv*/long.class, /*product*/int[].class);

    64             m.setAccessible(true);

    65             montgomeryMultiplyHandle = lookup.unreflect(m);

    67             m = BigInteger.class.getDeclaredMethod("montgomerySquare",

    68                 /*a*/int[].class, /*n*/int[].class, /*len*/int.class,

    69                 /*inv*/long.class, /*product*/int[].class);

    70             m.setAccessible(true);

    71             montgomerySquareHandle = lookup.unreflect(m);

    73             Constructor c

    74                 = BigInteger.class.getDeclaredConstructor(int.class, int[].class);

    75             c.setAccessible(true);

    76             bigIntegerConstructorHandle = lookup.unreflectConstructor(c);

    78             bigIntegerMagField = BigInteger.class.getDeclaredField("mag");

    79             bigIntegerMagField.setAccessible(true);

    81         } catch (Throwable ex) {

    82             throw new RuntimeException(ex);

    83         }

    84     }

    86     // Invoke either BigInteger.montgomeryMultiply or BigInteger.montgomerySquare.

    87     int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv,

    88                              int[] product) throws Throwable {

    89         int[] result =

    90             (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product)

    91                      : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product);

    92         return Arrays.copyOf(result, len);

    93     }

    95     // Invoke the private constructor BigInteger(int[]).

    96     BigInteger newBigInteger(int[] val) throws Throwable {

    97         return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val);

    98     }

   100     // Get the private field BigInteger.mag

   101     int[] mag(BigInteger n) {

   102         try {

   103             return (int[]) bigIntegerMagField.get(n);

   104         } catch (Exception ex) {

   105             throw new RuntimeException(ex);

   106         }

   107     }

   109     // Montgomery multiplication

   110     // Calculate a * b * r^-1 mod n)

   111     //

   112     // R is a power of the word size

   113     // N' = R^-1 mod N

   114     //

   115     // T := ab

   116     // m := (T mod R)N' mod R [so 0 <= m < R]

   117     // t := (T + mN)/R

   118     // if t >= N then return t - N else return t

   119     //

   120     BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N,

   121             int len, BigInteger n_prime)

   122             throws Throwable {

   123         BigInteger T = a.multiply(b);

   124         BigInteger R = BigInteger.ONE.shiftLeft(len*32);

   125         BigInteger mask = R.subtract(BigInteger.ONE);

   126         BigInteger m = (T.and(mask)).multiply(n_prime);

   127         m = m.and(mask); // i.e. m.mod(R)

   128         T = T.add(m.multiply(N));

   129         T = T.shiftRight(len*32); // i.e. T.divide(R)

   130         if (T.compareTo(N) > 0) {

   131             T = T.subtract(N);

   132         }

   133         return T;

   134     }

   136     // Call the Montgomery multiply intrinsic.

   137     BigInteger montgomeryMultiply(int[] a_words, int[] b_words, int[] n_words,

   138             int len, BigInteger inv)

   139             throws Throwable {

   140         BigInteger t = montgomeryMultiply(

   141                 newBigInteger(a_words),

   142                 newBigInteger(b_words),

   143                 newBigInteger(n_words),

   144                 len, inv);

   145         return t;

   146     }

   148     // Check that the Montgomery multiply intrinsic returns the same

   149     // result as the longhand calculation.

   150     void check(int[] a_words, int[] b_words, int[] n_words, int len, BigInteger inv)

   151             throws Throwable {

   152         BigInteger n = newBigInteger(n_words);

   153         BigInteger slow = montgomeryMultiply(a_words, b_words, n_words, len, inv);

   154         BigInteger fast

   155             = newBigInteger(montgomeryMultiply

   156                             (a_words, b_words, n_words, len, inv.longValue(), null));

   157         // The intrinsic may not return the same value as the longhand

   158         // calculation but they must have the same residue mod N.

   159         if (!slow.mod(n).equals(fast.mod(n))) {

   160             throw new RuntimeException();

   161         }

   162     }

   164     Random rnd = new Random(0);

   166     // Return a random value of length <= bits in an array of even length

   167     int[] random_val(int bits) {

   168         int len = (bits+63)/64;  // i.e. length in longs

   169         int[] val = new int[len*2];

   170         for (int i = 0; i < val.length; i++)

   171             val[i] = rnd.nextInt();

   172         int leadingZeros = 64 - (bits & 64);

   173         if (leadingZeros >= 32) {

   174             val[0] = 0;

   175             val[1] &= ~(-1l << (leadingZeros & 31));

   176         } else {

   177             val[0] &= ~(-1l << leadingZeros);

   178         }

   179         return val;

   180     }

   182     void testOneLength(int lenInBits, int lenInInts) throws Throwable {

   183         BigInteger mod = new BigInteger(lenInBits, 2, rnd);

   184         BigInteger r = BigInteger.ONE.shiftLeft(lenInInts * 32);

   185         BigInteger n_prime = mod.modInverse(r).negate();

   187         // Make n.length even, padding with a zero if necessary

   188         int[] n = mag(mod);

   189         if (n.length < lenInInts) {

   190             int[] x = new int[lenInInts];

   191             System.arraycopy(n, 0, x, lenInInts-n.length, n.length);

   192             n = x;

   193         }

   195         for (int i = 0; i < 10000; i++) {

   196             // multiply

   197             check(random_val(lenInBits), random_val(lenInBits), n, lenInInts, n_prime);

   198             // square

   199             int[] tmp = random_val(lenInBits);

   200             check(tmp, tmp, n, lenInInts, n_prime);

   201         }

   202     }

   204     // Test the Montgomery multiply intrinsic with a bunch of random

   205     // values of varying lengths.  Do this for long enough that the

   206     // caller of the intrinsic is C2-compiled.

   207     void testResultValues() throws Throwable {

   208         // Test a couple of interesting edge cases.

   209         testOneLength(1024, 32);

   210         testOneLength(1025, 34);

   211         for (int j = 10; j > 0; j--) {

   212             // Construct a random prime whose length in words is even

   213             int lenInBits = rnd.nextInt(2048) + 64;

   214             int lenInInts = (lenInBits + 63)/64*2;

   215             testOneLength(lenInBits, lenInInts);

   216         }

   217     }

   219     // Range checks

   220     void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv,

   221                                         int[] product, Class klass) {

   222         try {

   223             montgomeryMultiply(a, b, n, len, inv, product);

   224         } catch (Throwable ex) {

   225             if (klass.isAssignableFrom(ex.getClass()))

   226                 return;

   227             throw new RuntimeException(klass + " expected, " + ex + " was thrown");

   228         }

   229         throw new RuntimeException(klass + " expected, was not thrown");

   230     }

   232     void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,

   233             Class klass) {

   234         testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass);

   235     }

   237     void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,

   238             int[] product, Class klass) {

   239         testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass);

   240     }

   242     void testMontgomeryMultiplyChecks() {

   243         int[] blah = random_val(40);

   244         int[] small = random_val(39);

   245         BigInteger mod = new BigInteger(40*32 , 2, rnd);

   246         BigInteger r = BigInteger.ONE.shiftLeft(40*32);

   247         BigInteger n_prime = mod.modInverse(r).negate();

   249         // Length out of range: square

   250         testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class);

   251         testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class);

   252         testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class);

   253         // As above, but for multiply

   254         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class);

   255         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);

   256         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);

   258         // Length odd

   259         testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class);

   260         testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class);

   261         testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class);

   262         // As above, but for multiply

   263         testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class);

   264         testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class);

   265         testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class);

   267         // array too small

   268         testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);

   269         testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class);

   270         testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class);

   271         testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class);

   272         testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);

   273         testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class);

   274     }

   276     public static void main(String args[]) {

   277         try {

   278             new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks();

   279             new MontgomeryMultiplyTest().testResultValues();

   280         } catch (Throwable ex) {

   281             throw new RuntimeException(ex);

   282         }

   283      }

   284 }

Mercurial > jdk8-mips64-public > hotspot / file revision

test/compiler/intrinsics/montgomerymultiply/MontgomeryMultiplyTest.java@0cd040567d60

test/compiler/intrinsics/montgomerymultiply/MontgomeryMultiplyTest.java