# HG changeset patch # User bpb # Date 1463780501 25200 # Node ID ca210bc11ed784851a98c0c8ebe916eca0d3134b # Parent a98523f5cbff3903de8f0bcd7fddeb395172123e 5100935: No way to access the 64-bit integer multiplication of 64-bit CPUs efficiently Summary: Add methods multiplyFull() and multiplyHigh() to Math and StrictMath. Reviewed-by: darcy diff -r a98523f5cbff -r ca210bc11ed7 jdk/src/java.base/share/classes/java/lang/Math.java --- a/jdk/src/java.base/share/classes/java/lang/Math.java Fri May 20 21:44:03 2016 +0100 +++ b/jdk/src/java.base/share/classes/java/lang/Math.java Fri May 20 14:41:41 2016 -0700 @@ -1060,6 +1060,53 @@ } /** + * Returns the exact mathematical product of the arguments. + * + * @param x the first value + * @param y the second value + * @return the result + */ + public static long multiplyFull(int x, int y) { + return (long)x * (long)y; + } + + /** + * Returns as a {@code long} the most significant 64 bits of the 128-bit + * product of two 64-bit factors. + * + * @param x the first value + * @param y the second value + * @return the result + */ + public static long multiplyHigh(long x, long y) { + if (x < 0 || y < 0) { + // Use technique from section 8-2 of Henry S. Warren, Jr., + // Hacker's Delight (2nd ed.) (Addison Wesley, 2013), 173-174. + long x1 = x >> 32; + long x2 = x & 0xFFFFFFFFL; + long y1 = y >> 32; + long y2 = y & 0xFFFFFFFFL; + long z2 = x2 * y2; + long t = x1 * y2 + (z2 >>> 32); + long z1 = t & 0xFFFFFFFFL; + long z0 = t >> 32; + z1 += x2 * y1; + return x1 * y1 + z0 + (z1 >> 32); + } else { + // Use Karatsuba technique with two base 2^32 digits. + long x1 = x >>> 32; + long y1 = y >>> 32; + long x2 = x & 0xFFFFFFFFL; + long y2 = y & 0xFFFFFFFFL; + long A = x1 * y1; + long B = x2 * y2; + long C = (x1 + x2) * (y1 + y2); + long K = C - A - B; + return (((B >>> 32) + K) >>> 32) + A; + } + } + + /** * Returns the largest (closest to positive infinity) * {@code int} value that is less than or equal to the algebraic quotient. * There is one special case, if the dividend is the diff -r a98523f5cbff -r ca210bc11ed7 jdk/src/java.base/share/classes/java/lang/StrictMath.java --- a/jdk/src/java.base/share/classes/java/lang/StrictMath.java Fri May 20 21:44:03 2016 +0100 +++ b/jdk/src/java.base/share/classes/java/lang/StrictMath.java Fri May 20 14:41:41 2016 -0700 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1999, 2015, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1999, 2016, Oracle and/or its affiliates. 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 @@ -832,6 +832,33 @@ } /** + * Returns the exact mathematical product of the arguments. + * + * @param x the first value + * @param y the second value + * @return the result + * @see Math#multiplyFull(long,long) + * @since 1.9 + */ + public static long multiplyFull(int x, int y) { + return Math.multiplyFull(x, y); + } + + /** + * Returns as a {@code long} the most significant 64 bits of the 128-bit + * product of two 64-bit factors. + * + * @param x the first value + * @param y the second value + * @return the result + * @see Math#multiplyHigh(long,long) + * @since 1.9 + */ + public static long multiplyHigh(long x, long y) { + return Math.multiplyHigh(x, y); + } + + /** * Returns the largest (closest to positive infinity) * {@code int} value that is less than or equal to the algebraic quotient. * There is one special case, if the dividend is the diff -r a98523f5cbff -r ca210bc11ed7 jdk/test/java/lang/Math/MultiplicationTests.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/test/java/lang/Math/MultiplicationTests.java Fri May 20 14:41:41 2016 -0700 @@ -0,0 +1,113 @@ +/* + * Copyright (c) 2016, Oracle and/or its affiliates. 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. + */ + +/* + * @test + * @library /lib/testlibrary/ + * @build jdk.testlibrary.* + * @run main MultiplicationTests + * @bug 5100935 + * @summary Tests for multiplication methods (use -Dseed=X to set PRNG seed) + * @key randomness + */ + +import java.math.BigInteger; +import jdk.testlibrary.RandomFactory; + +public class MultiplicationTests { + private MultiplicationTests(){} + + // Number of random products to test. + private static final int COUNT = 1 << 16; + + // Initialize shared random number generator + private static java.util.Random rnd = RandomFactory.getRandom(); + + // Calculate high 64 bits of 128 product using BigInteger. + private static long multiplyHighBigInt(long x, long y) { + return BigInteger.valueOf(x).multiply(BigInteger.valueOf(y)) + .shiftRight(64).longValue(); + } + + // Check Math.multiplyHigh(x,y) against multiplyHighBigInt(x,y) + private static boolean check(long x, long y) { + long p1 = multiplyHighBigInt(x, y); + long p2 = Math.multiplyHigh(x, y); + if (p1 != p2) { + System.err.printf("Error - x:%d y:%d p1:%d p2:%d\n", x, y, p1, p2); + return false; + } else { + return true; + } + } + + private static int testMultiplyHigh() { + int failures = 0; + + // check some boundary cases + long[][] v = new long[][]{ + {0L, 0L}, + {-1L, 0L}, + {0L, -1L}, + {1L, 0L}, + {0L, 1L}, + {-1L, -1L}, + {-1L, 1L}, + {1L, -1L}, + {1L, 1L}, + {Long.MAX_VALUE, Long.MAX_VALUE}, + {Long.MAX_VALUE, -Long.MAX_VALUE}, + {-Long.MAX_VALUE, Long.MAX_VALUE}, + {Long.MAX_VALUE, Long.MIN_VALUE}, + {Long.MIN_VALUE, Long.MAX_VALUE}, + {Long.MIN_VALUE, Long.MIN_VALUE} + }; + + for (long[] xy : v) { + if(!check(xy[0], xy[1])) { + failures++; + } + } + + // check some random values + for (int i = 0; i < COUNT; i++) { + if (!check(rnd.nextLong(), rnd.nextLong())) { + failures++; + } + } + + return failures; + } + + public static void main(String argv[]) { + int failures = testMultiplyHigh(); + + if (failures > 0) { + System.err.println("Multiplication testing encountered " + + failures + " failures."); + throw new RuntimeException(); + } else { + System.out.println("MultiplicationTests succeeded"); + } + } +}