1946 }
1947 int len = mag.length;
1948
1949 if (len < KARATSUBA_SQUARE_THRESHOLD) {
1950 int[] z = squareToLen(mag, len, null);
1951 return new BigInteger(trustedStripLeadingZeroInts(z), 1);
1952 } else {
1953 if (len < TOOM_COOK_SQUARE_THRESHOLD) {
1954 return squareKaratsuba();
1955 } else {
1956 return squareToomCook3();
1957 }
1958 }
1959 }
1960
1961 /**
1962 * Squares the contents of the int array x. The result is placed into the
1963 * int array z. The contents of x are not changed.
1964 */
1965 private static final int[] squareToLen(int[] x, int len, int[] z) {
1966 /*
1967 * The algorithm used here is adapted from Colin Plumb's C library.
1968 * Technique: Consider the partial products in the multiplication
1969 * of "abcde" by itself:
1970 *
1971 * a b c d e
1972 * * a b c d e
1973 * ==================
1974 * ae be ce de ee
1975 * ad bd cd dd de
1976 * ac bc cc cd ce
1977 * ab bb bc bd be
1978 * aa ab ac ad ae
1979 *
1980 * Note that everything above the main diagonal:
1981 * ae be ce de = (abcd) * e
1982 * ad bd cd = (abc) * d
1983 * ac bc = (ab) * c
1984 * ab = (a) * b
1985 *
1986 * is a copy of everything below the main diagonal:
1987 * de
1988 * cd ce
1989 * bc bd be
1990 * ab ac ad ae
1991 *
1992 * Thus, the sum is 2 * (off the diagonal) + diagonal.
1993 *
1994 * This is accumulated beginning with the diagonal (which
1995 * consist of the squares of the digits of the input), which is then
1996 * divided by two, the off-diagonal added, and multiplied by two
1997 * again. The low bit is simply a copy of the low bit of the
1998 * input, so it doesn't need special care.
1999 */
2000 int zlen = len << 1;
2001 if (z == null || z.length < zlen)
2002 z = new int[zlen];
2003
2004 // Store the squares, right shifted one bit (i.e., divided by 2)
2005 int lastProductLowWord = 0;
2006 for (int j=0, i=0; j < len; j++) {
2007 long piece = (x[j] & LONG_MASK);
2008 long product = piece * piece;
2009 z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33);
2010 z[i++] = (int)(product >>> 1);
2011 lastProductLowWord = (int)product;
2012 }
2013
2014 // Add in off-diagonal sums
2015 for (int i=len, offset=1; i > 0; i--, offset+=2) {
2016 int t = x[i-1];
2017 t = mulAdd(z, x, offset, i-1, t);
2018 addOne(z, offset-1, i, t);
2019 }
2020
2021 // Shift back up and set low bit
2022 primitiveLeftShift(z, zlen, 1);
2840
2841 /**
2842 * Subtracts two numbers of same length, returning borrow.
2843 */
2844 private static int subN(int[] a, int[] b, int len) {
2845 long sum = 0;
2846
2847 while (--len >= 0) {
2848 sum = (a[len] & LONG_MASK) -
2849 (b[len] & LONG_MASK) + (sum >> 32);
2850 a[len] = (int)sum;
2851 }
2852
2853 return (int)(sum >> 32);
2854 }
2855
2856 /**
2857 * Multiply an array by one word k and add to result, return the carry
2858 */
2859 static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
2860 long kLong = k & LONG_MASK;
2861 long carry = 0;
2862
2863 offset = out.length-offset - 1;
2864 for (int j=len-1; j >= 0; j--) {
2865 long product = (in[j] & LONG_MASK) * kLong +
2866 (out[offset] & LONG_MASK) + carry;
2867 out[offset--] = (int)product;
2868 carry = product >>> 32;
2869 }
2870 return (int)carry;
2871 }
2872
2873 /**
2874 * Add one word to the number a mlen words into a. Return the resulting
2875 * carry.
2876 */
2877 static int addOne(int[] a, int offset, int mlen, int carry) {
2878 offset = a.length-1-mlen-offset;
2879 long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
|
1946 }
1947 int len = mag.length;
1948
1949 if (len < KARATSUBA_SQUARE_THRESHOLD) {
1950 int[] z = squareToLen(mag, len, null);
1951 return new BigInteger(trustedStripLeadingZeroInts(z), 1);
1952 } else {
1953 if (len < TOOM_COOK_SQUARE_THRESHOLD) {
1954 return squareKaratsuba();
1955 } else {
1956 return squareToomCook3();
1957 }
1958 }
1959 }
1960
1961 /**
1962 * Squares the contents of the int array x. The result is placed into the
1963 * int array z. The contents of x are not changed.
1964 */
1965 private static final int[] squareToLen(int[] x, int len, int[] z) {
1966 int zlen = len << 1;
1967 if (z == null || z.length < zlen)
1968 z = new int[zlen];
1969
1970 // Execute checks before calling intrinsified method.
1971 implSquareToLenChecks(x, len, z, zlen);
1972 return implSquareToLen(x, len, z, zlen);
1973 }
1974
1975 /**
1976 * Parameters validation.
1977 */
1978 private static void implSquareToLenChecks(int[] x, int len, int[] z, int zlen) throws RuntimeException {
1979 if (len < 1) {
1980 throw new IllegalArgumentException("invalid input length: " + len);
1981 }
1982 if (len > x.length) {
1983 throw new IllegalArgumentException("input length out of bound: " +
1984 len + " > " + x.length);
1985 }
1986 if (len * 2 > z.length) {
1987 throw new IllegalArgumentException("input length out of bound: " +
1988 (len * 2) + " > " + z.length);
1989 }
1990 if (zlen < 1) {
1991 throw new IllegalArgumentException("invalid input length: " + zlen);
1992 }
1993 if (zlen > z.length) {
1994 throw new IllegalArgumentException("input length out of bound: " +
1995 len + " > " + z.length);
1996 }
1997 }
1998
1999 /**
2000 * Java Runtime may use intrinsic for this method.
2001 */
2002 private static final int[] implSquareToLen(int[] x, int len, int[] z, int zlen) {
2003 /*
2004 * The algorithm used here is adapted from Colin Plumb's C library.
2005 * Technique: Consider the partial products in the multiplication
2006 * of "abcde" by itself:
2007 *
2008 * a b c d e
2009 * * a b c d e
2010 * ==================
2011 * ae be ce de ee
2012 * ad bd cd dd de
2013 * ac bc cc cd ce
2014 * ab bb bc bd be
2015 * aa ab ac ad ae
2016 *
2017 * Note that everything above the main diagonal:
2018 * ae be ce de = (abcd) * e
2019 * ad bd cd = (abc) * d
2020 * ac bc = (ab) * c
2021 * ab = (a) * b
2022 *
2023 * is a copy of everything below the main diagonal:
2024 * de
2025 * cd ce
2026 * bc bd be
2027 * ab ac ad ae
2028 *
2029 * Thus, the sum is 2 * (off the diagonal) + diagonal.
2030 *
2031 * This is accumulated beginning with the diagonal (which
2032 * consist of the squares of the digits of the input), which is then
2033 * divided by two, the off-diagonal added, and multiplied by two
2034 * again. The low bit is simply a copy of the low bit of the
2035 * input, so it doesn't need special care.
2036 */
2037
2038 // Store the squares, right shifted one bit (i.e., divided by 2)
2039 int lastProductLowWord = 0;
2040 for (int j=0, i=0; j < len; j++) {
2041 long piece = (x[j] & LONG_MASK);
2042 long product = piece * piece;
2043 z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33);
2044 z[i++] = (int)(product >>> 1);
2045 lastProductLowWord = (int)product;
2046 }
2047
2048 // Add in off-diagonal sums
2049 for (int i=len, offset=1; i > 0; i--, offset+=2) {
2050 int t = x[i-1];
2051 t = mulAdd(z, x, offset, i-1, t);
2052 addOne(z, offset-1, i, t);
2053 }
2054
2055 // Shift back up and set low bit
2056 primitiveLeftShift(z, zlen, 1);
2874
2875 /**
2876 * Subtracts two numbers of same length, returning borrow.
2877 */
2878 private static int subN(int[] a, int[] b, int len) {
2879 long sum = 0;
2880
2881 while (--len >= 0) {
2882 sum = (a[len] & LONG_MASK) -
2883 (b[len] & LONG_MASK) + (sum >> 32);
2884 a[len] = (int)sum;
2885 }
2886
2887 return (int)(sum >> 32);
2888 }
2889
2890 /**
2891 * Multiply an array by one word k and add to result, return the carry
2892 */
2893 static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
2894 implMulAddCheck(out, in, offset, len, k);
2895 return implMulAdd(out, in, offset, len, k);
2896 }
2897
2898 /**
2899 * Parameters validation.
2900 */
2901 private static void implMulAddCheck(int[] out, int[] in, int offset, int len, int k) {
2902 if (len > in.length) {
2903 throw new IllegalArgumentException("input length is out of bound: " + len + " > " + in.length);
2904 }
2905 if (offset < 0) {
2906 throw new IllegalArgumentException("input offset is invalid: " + offset);
2907 }
2908 if (offset > (out.length - 1)) {
2909 throw new IllegalArgumentException("input offset is out of bound: " + offset + " > " + (out.length - 1));
2910 }
2911 if (len > (out.length - offset)) {
2912 throw new IllegalArgumentException("input len is out of bound: " + len + " > " + (out.length - offset));
2913 }
2914 }
2915
2916 /**
2917 * Java Runtime may use intrinsic for this method.
2918 */
2919 private static int implMulAdd(int[] out, int[] in, int offset, int len, int k) {
2920 long kLong = k & LONG_MASK;
2921 long carry = 0;
2922
2923 offset = out.length-offset - 1;
2924 for (int j=len-1; j >= 0; j--) {
2925 long product = (in[j] & LONG_MASK) * kLong +
2926 (out[offset] & LONG_MASK) + carry;
2927 out[offset--] = (int)product;
2928 carry = product >>> 32;
2929 }
2930 return (int)carry;
2931 }
2932
2933 /**
2934 * Add one word to the number a mlen words into a. Return the resulting
2935 * carry.
2936 */
2937 static int addOne(int[] a, int offset, int mlen, int carry) {
2938 offset = a.length-1-mlen-offset;
2939 long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
|