X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libjava%2Fgnu%2Fjava%2Fmath%2FMPN.java;fp=libjava%2Fgnu%2Fjava%2Fmath%2FMPN.java;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=988c56f0719935a9eeb53ec842f7085154484189;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libjava/gnu/java/math/MPN.java b/libjava/gnu/java/math/MPN.java deleted file mode 100644 index 988c56f0..00000000 --- a/libjava/gnu/java/math/MPN.java +++ /dev/null @@ -1,768 +0,0 @@ -/* gnu.java.math.MPN - Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc. - -This file is part of GNU Classpath. - -GNU Classpath is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2, or (at your option) -any later version. - -GNU Classpath 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 for more details. - -You should have received a copy of the GNU General Public License -along with GNU Classpath; see the file COPYING. If not, write to the -Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA -02111-1307 USA. - -Linking this library statically or dynamically with other modules is -making a combined work based on this library. Thus, the terms and -conditions of the GNU General Public License cover the whole -combination. - -As a special exception, the copyright holders of this library give you -permission to link this library with independent modules to produce an -executable, regardless of the license terms of these independent -modules, and to copy and distribute the resulting executable under -terms of your choice, provided that you also meet, for each linked -independent module, the terms and conditions of the license of that -module. An independent module is a module which is not derived from -or based on this library. If you modify this library, you may extend -this exception to your version of the library, but you are not -obligated to do so. If you do not wish to do so, delete this -exception statement from your version. */ - -// Included from Kawa 1.6.62 with permission of the author, -// Per Bothner . - -package gnu.java.math; - -/** This contains various low-level routines for unsigned bigints. - * The interfaces match the mpn interfaces in gmp, - * so it should be easy to replace them with fast native functions - * that are trivial wrappers around the mpn_ functions in gmp - * (at least on platforms that use 32-bit "limbs"). - */ - -public class MPN -{ - /** Add x[0:size-1] and y, and write the size least - * significant words of the result to dest. - * Return carry, either 0 or 1. - * All values are unsigned. - * This is basically the same as gmp's mpn_add_1. */ - public static int add_1 (int[] dest, int[] x, int size, int y) - { - long carry = (long) y & 0xffffffffL; - for (int i = 0; i < size; i++) - { - carry += ((long) x[i] & 0xffffffffL); - dest[i] = (int) carry; - carry >>= 32; - } - return (int) carry; - } - - /** Add x[0:len-1] and y[0:len-1] and write the len least - * significant words of the result to dest[0:len-1]. - * All words are treated as unsigned. - * @return the carry, either 0 or 1 - * This function is basically the same as gmp's mpn_add_n. - */ - public static int add_n (int dest[], int[] x, int[] y, int len) - { - long carry = 0; - for (int i = 0; i < len; i++) - { - carry += ((long) x[i] & 0xffffffffL) - + ((long) y[i] & 0xffffffffL); - dest[i] = (int) carry; - carry >>>= 32; - } - return (int) carry; - } - - /** Subtract Y[0:size-1] from X[0:size-1], and write - * the size least significant words of the result to dest[0:size-1]. - * Return borrow, either 0 or 1. - * This is basically the same as gmp's mpn_sub_n function. - */ - - public static int sub_n (int[] dest, int[] X, int[] Y, int size) - { - int cy = 0; - for (int i = 0; i < size; i++) - { - int y = Y[i]; - int x = X[i]; - y += cy; /* add previous carry to subtrahend */ - // Invert the high-order bit, because: (unsigned) X > (unsigned) Y - // iff: (int) (X^0x80000000) > (int) (Y^0x80000000). - cy = (y^0x80000000) < (cy^0x80000000) ? 1 : 0; - y = x - y; - cy += (y^0x80000000) > (x ^ 0x80000000) ? 1 : 0; - dest[i] = y; - } - return cy; - } - - /** Multiply x[0:len-1] by y, and write the len least - * significant words of the product to dest[0:len-1]. - * Return the most significant word of the product. - * All values are treated as if they were unsigned - * (i.e. masked with 0xffffffffL). - * OK if dest==x (not sure if this is guaranteed for mpn_mul_1). - * This function is basically the same as gmp's mpn_mul_1. - */ - - public static int mul_1 (int[] dest, int[] x, int len, int y) - { - long yword = (long) y & 0xffffffffL; - long carry = 0; - for (int j = 0; j < len; j++) - { - carry += ((long) x[j] & 0xffffffffL) * yword; - dest[j] = (int) carry; - carry >>>= 32; - } - return (int) carry; - } - - /** - * Multiply x[0:xlen-1] and y[0:ylen-1], and - * write the result to dest[0:xlen+ylen-1]. - * The destination has to have space for xlen+ylen words, - * even if the result might be one limb smaller. - * This function requires that xlen >= ylen. - * The destination must be distinct from either input operands. - * All operands are unsigned. - * This function is basically the same gmp's mpn_mul. */ - - public static void mul (int[] dest, - int[] x, int xlen, - int[] y, int ylen) - { - dest[xlen] = MPN.mul_1 (dest, x, xlen, y[0]); - - for (int i = 1; i < ylen; i++) - { - long yword = (long) y[i] & 0xffffffffL; - long carry = 0; - for (int j = 0; j < xlen; j++) - { - carry += ((long) x[j] & 0xffffffffL) * yword - + ((long) dest[i+j] & 0xffffffffL); - dest[i+j] = (int) carry; - carry >>>= 32; - } - dest[i+xlen] = (int) carry; - } - } - - /* Divide (unsigned long) N by (unsigned int) D. - * Returns (remainder << 32)+(unsigned int)(quotient). - * Assumes (unsigned int)(N>>32) < (unsigned int)D. - * Code transcribed from gmp-2.0's mpn_udiv_w_sdiv function. - */ - public static long udiv_qrnnd (long N, int D) - { - long q, r; - long a1 = N >>> 32; - long a0 = N & 0xffffffffL; - if (D >= 0) - { - if (a1 < ((D - a1 - (a0 >>> 31)) & 0xffffffffL)) - { - /* dividend, divisor, and quotient are nonnegative */ - q = N / D; - r = N % D; - } - else - { - /* Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d */ - long c = N - ((long) D << 31); - /* Divide (c1*2^32 + c0) by d */ - q = c / D; - r = c % D; - /* Add 2^31 to quotient */ - q += 1 << 31; - } - } - else - { - long b1 = D >>> 1; /* d/2, between 2^30 and 2^31 - 1 */ - //long c1 = (a1 >> 1); /* A/2 */ - //int c0 = (a1 << 31) + (a0 >> 1); - long c = N >>> 1; - if (a1 < b1 || (a1 >> 1) < b1) - { - if (a1 < b1) - { - q = c / b1; - r = c % b1; - } - else /* c1 < b1, so 2^31 <= (A/2)/b1 < 2^32 */ - { - c = ~(c - (b1 << 32)); - q = c / b1; /* (A/2) / (d/2) */ - r = c % b1; - q = (~q) & 0xffffffffL; /* (A/2)/b1 */ - r = (b1 - 1) - r; /* r < b1 => new r >= 0 */ - } - r = 2 * r + (a0 & 1); - if ((D & 1) != 0) - { - if (r >= q) { - r = r - q; - } else if (q - r <= ((long) D & 0xffffffffL)) { - r = r - q + D; - q -= 1; - } else { - r = r - q + D + D; - q -= 2; - } - } - } - else /* Implies c1 = b1 */ - { /* Hence a1 = d - 1 = 2*b1 - 1 */ - if (a0 >= ((long)(-D) & 0xffffffffL)) - { - q = -1; - r = a0 + D; - } - else - { - q = -2; - r = a0 + D + D; - } - } - } - - return (r << 32) | (q & 0xFFFFFFFFl); - } - - /** Divide divident[0:len-1] by (unsigned int)divisor. - * Write result into quotient[0:len-1. - * Return the one-word (unsigned) remainder. - * OK for quotient==dividend. - */ - - public static int divmod_1 (int[] quotient, int[] dividend, - int len, int divisor) - { - int i = len - 1; - long r = dividend[i]; - if ((r & 0xffffffffL) >= ((long)divisor & 0xffffffffL)) - r = 0; - else - { - quotient[i--] = 0; - r <<= 32; - } - - for (; i >= 0; i--) - { - int n0 = dividend[i]; - r = (r & ~0xffffffffL) | (n0 & 0xffffffffL); - r = udiv_qrnnd (r, divisor); - quotient[i] = (int) r; - } - return (int)(r >> 32); - } - - /* Subtract x[0:len-1]*y from dest[offset:offset+len-1]. - * All values are treated as if unsigned. - * @return the most significant word of - * the product, minus borrow-out from the subtraction. - */ - public static int submul_1 (int[] dest, int offset, int[] x, int len, int y) - { - long yl = (long) y & 0xffffffffL; - int carry = 0; - int j = 0; - do - { - long prod = ((long) x[j] & 0xffffffffL) * yl; - int prod_low = (int) prod; - int prod_high = (int) (prod >> 32); - prod_low += carry; - // Invert the high-order bit, because: (unsigned) X > (unsigned) Y - // iff: (int) (X^0x80000000) > (int) (Y^0x80000000). - carry = ((prod_low ^ 0x80000000) < (carry ^ 0x80000000) ? 1 : 0) - + prod_high; - int x_j = dest[offset+j]; - prod_low = x_j - prod_low; - if ((prod_low ^ 0x80000000) > (x_j ^ 0x80000000)) - carry++; - dest[offset+j] = prod_low; - } - while (++j < len); - return carry; - } - - /** Divide zds[0:nx] by y[0:ny-1]. - * The remainder ends up in zds[0:ny-1]. - * The quotient ends up in zds[ny:nx]. - * Assumes: nx>ny. - * (int)y[ny-1] < 0 (i.e. most significant bit set) - */ - - public static void divide (int[] zds, int nx, int[] y, int ny) - { - // This is basically Knuth's formulation of the classical algorithm, - // but translated from in scm_divbigbig in Jaffar's SCM implementation. - - // Correspondance with Knuth's notation: - // Knuth's u[0:m+n] == zds[nx:0]. - // Knuth's v[1:n] == y[ny-1:0] - // Knuth's n == ny. - // Knuth's m == nx-ny. - // Our nx == Knuth's m+n. - - // Could be re-implemented using gmp's mpn_divrem: - // zds[nx] = mpn_divrem (&zds[ny], 0, zds, nx, y, ny). - - int j = nx; - do - { // loop over digits of quotient - // Knuth's j == our nx-j. - // Knuth's u[j:j+n] == our zds[j:j-ny]. - int qhat; // treated as unsigned - if (zds[j]==y[ny-1]) - qhat = -1; // 0xffffffff - else - { - long w = (((long)(zds[j])) << 32) + ((long)zds[j-1] & 0xffffffffL); - qhat = (int) udiv_qrnnd (w, y[ny-1]); - } - if (qhat != 0) - { - int borrow = submul_1 (zds, j - ny, y, ny, qhat); - int save = zds[j]; - long num = ((long)save&0xffffffffL) - ((long)borrow&0xffffffffL); - while (num != 0) - { - qhat--; - long carry = 0; - for (int i = 0; i < ny; i++) - { - carry += ((long) zds[j-ny+i] & 0xffffffffL) - + ((long) y[i] & 0xffffffffL); - zds[j-ny+i] = (int) carry; - carry >>>= 32; - } - zds[j] += carry; - num = carry - 1; - } - } - zds[j] = qhat; - } while (--j >= ny); - } - - /** Number of digits in the conversion base that always fits in a word. - * For example, for base 10 this is 9, since 10**9 is the - * largest number that fits into a words (assuming 32-bit words). - * This is the same as gmp's __mp_bases[radix].chars_per_limb. - * @param radix the base - * @return number of digits */ - public static int chars_per_word (int radix) - { - if (radix < 10) - { - if (radix < 8) - { - if (radix <= 2) - return 32; - else if (radix == 3) - return 20; - else if (radix == 4) - return 16; - else - return 18 - radix; - } - else - return 10; - } - else if (radix < 12) - return 9; - else if (radix <= 16) - return 8; - else if (radix <= 23) - return 7; - else if (radix <= 40) - return 6; - // The following are conservative, but we don't care. - else if (radix <= 256) - return 4; - else - return 1; - } - - /** Count the number of leading zero bits in an int. */ - public static int count_leading_zeros (int i) - { - if (i == 0) - return 32; - int count = 0; - for (int k = 16; k > 0; k = k >> 1) { - int j = i >>> k; - if (j == 0) - count += k; - else - i = j; - } - return count; - } - - public static int set_str (int dest[], byte[] str, int str_len, int base) - { - int size = 0; - if ((base & (base - 1)) == 0) - { - // The base is a power of 2. Read the input string from - // least to most significant character/digit. */ - - int next_bitpos = 0; - int bits_per_indigit = 0; - for (int i = base; (i >>= 1) != 0; ) bits_per_indigit++; - int res_digit = 0; - - for (int i = str_len; --i >= 0; ) - { - int inp_digit = str[i]; - res_digit |= inp_digit << next_bitpos; - next_bitpos += bits_per_indigit; - if (next_bitpos >= 32) - { - dest[size++] = res_digit; - next_bitpos -= 32; - res_digit = inp_digit >> (bits_per_indigit - next_bitpos); - } - } - - if (res_digit != 0) - dest[size++] = res_digit; - } - else - { - // General case. The base is not a power of 2. - int indigits_per_limb = MPN.chars_per_word (base); - int str_pos = 0; - - while (str_pos < str_len) - { - int chunk = str_len - str_pos; - if (chunk > indigits_per_limb) - chunk = indigits_per_limb; - int res_digit = str[str_pos++]; - int big_base = base; - - while (--chunk > 0) - { - res_digit = res_digit * base + str[str_pos++]; - big_base *= base; - } - - int cy_limb; - if (size == 0) - cy_limb = res_digit; - else - { - cy_limb = MPN.mul_1 (dest, dest, size, big_base); - cy_limb += MPN.add_1 (dest, dest, size, res_digit); - } - if (cy_limb != 0) - dest[size++] = cy_limb; - } - } - return size; - } - - /** Compare x[0:size-1] with y[0:size-1], treating them as unsigned integers. - * @result -1, 0, or 1 depending on if xy. - * This is basically the same as gmp's mpn_cmp function. - */ - public static int cmp (int[] x, int[] y, int size) - { - while (--size >= 0) - { - int x_word = x[size]; - int y_word = y[size]; - if (x_word != y_word) - { - // Invert the high-order bit, because: - // (unsigned) X > (unsigned) Y iff - // (int) (X^0x80000000) > (int) (Y^0x80000000). - return (x_word ^ 0x80000000) > (y_word ^0x80000000) ? 1 : -1; - } - } - return 0; - } - - /** Compare x[0:xlen-1] with y[0:ylen-1], treating them as unsigned integers. - * @result -1, 0, or 1 depending on if xy. - */ - public static int cmp (int[] x, int xlen, int[] y, int ylen) - { - return xlen > ylen ? 1 : xlen < ylen ? -1 : cmp (x, y, xlen); - } - - /* Shift x[x_start:x_start+len-1] count bits to the "right" - * (i.e. divide by 2**count). - * Store the len least significant words of the result at dest. - * The bits shifted out to the right are returned. - * OK if dest==x. - * Assumes: 0 < count < 32 - */ - - public static int rshift (int[] dest, int[] x, int x_start, - int len, int count) - { - int count_2 = 32 - count; - int low_word = x[x_start]; - int retval = low_word << count_2; - int i = 1; - for (; i < len; i++) - { - int high_word = x[x_start+i]; - dest[i-1] = (low_word >>> count) | (high_word << count_2); - low_word = high_word; - } - dest[i-1] = low_word >>> count; - return retval; - } - - /* Shift x[x_start:x_start+len-1] count bits to the "right" - * (i.e. divide by 2**count). - * Store the len least significant words of the result at dest. - * OK if dest==x. - * Assumes: 0 <= count < 32 - * Same as rshift, but handles count==0 (and has no return value). - */ - public static void rshift0 (int[] dest, int[] x, int x_start, - int len, int count) - { - if (count > 0) - rshift(dest, x, x_start, len, count); - else - for (int i = 0; i < len; i++) - dest[i] = x[i + x_start]; - } - - /** Return the long-truncated value of right shifting. - * @param x a two's-complement "bignum" - * @param len the number of significant words in x - * @param count the shift count - * @return (long)(x[0..len-1] >> count). - */ - public static long rshift_long (int[] x, int len, int count) - { - int wordno = count >> 5; - count &= 31; - int sign = x[len-1] < 0 ? -1 : 0; - int w0 = wordno >= len ? sign : x[wordno]; - wordno++; - int w1 = wordno >= len ? sign : x[wordno]; - if (count != 0) - { - wordno++; - int w2 = wordno >= len ? sign : x[wordno]; - w0 = (w0 >>> count) | (w1 << (32-count)); - w1 = (w1 >>> count) | (w2 << (32-count)); - } - return ((long)w1 << 32) | ((long)w0 & 0xffffffffL); - } - - /* Shift x[0:len-1] left by count bits, and store the len least - * significant words of the result in dest[d_offset:d_offset+len-1]. - * Return the bits shifted out from the most significant digit. - * Assumes 0 < count < 32. - * OK if dest==x. - */ - - public static int lshift (int[] dest, int d_offset, - int[] x, int len, int count) - { - int count_2 = 32 - count; - int i = len - 1; - int high_word = x[i]; - int retval = high_word >>> count_2; - d_offset++; - while (--i >= 0) - { - int low_word = x[i]; - dest[d_offset+i] = (high_word << count) | (low_word >>> count_2); - high_word = low_word; - } - dest[d_offset+i] = high_word << count; - return retval; - } - - /** Return least i such that word&(1<>= 4; - i += 4; - } - if ((word & 3) == 0) - { - word >>= 2; - i += 2; - } - if ((word & 1) == 0) - i += 1; - return i; - } - - /** Return least i such that words & (1< 0) - { - int j; - for (j = 0; j < len-i; j++) - other_arg[j] = other_arg[j+i]; - for ( ; j < len; j++) - other_arg[j] = 0; - } - i = findLowestBit(other_arg[0]); - if (i > 0) - MPN.rshift (other_arg, other_arg, 0, len, i); - - // Now both odd_arg and other_arg are odd. - - // Subtract the smaller from the larger. - // This does not change the result, since gcd(a-b,b)==gcd(a,b). - i = MPN.cmp(odd_arg, other_arg, len); - if (i == 0) - break; - if (i > 0) - { // odd_arg > other_arg - MPN.sub_n (odd_arg, odd_arg, other_arg, len); - // Now odd_arg is even, so swap with other_arg; - int[] tmp = odd_arg; odd_arg = other_arg; other_arg = tmp; - } - else - { // other_arg > odd_arg - MPN.sub_n (other_arg, other_arg, odd_arg, len); - } - while (odd_arg[len-1] == 0 && other_arg[len-1] == 0) - len--; - } - if (initShiftWords + initShiftBits > 0) - { - if (initShiftBits > 0) - { - int sh_out = MPN.lshift (x, initShiftWords, x, len, initShiftBits); - if (sh_out != 0) - x[(len++)+initShiftWords] = sh_out; - } - else - { - for (i = len; --i >= 0;) - x[i+initShiftWords] = x[i]; - } - for (i = initShiftWords; --i >= 0; ) - x[i] = 0; - len += initShiftWords; - } - return len; - } - - public static int intLength (int i) - { - return 32 - count_leading_zeros (i < 0 ? ~i : i); - } - - /** Calcaulte the Common Lisp "integer-length" function. - * Assumes input is canonicalized: len==BigInteger.wordsNeeded(words,len) */ - public static int intLength (int[] words, int len) - { - len--; - return intLength (words[len]) + 32 * len; - } - - /* DEBUGGING: - public static void dprint (BigInteger x) - { - if (x.words == null) - System.err.print(Long.toString((long) x.ival & 0xffffffffL, 16)); - else - dprint (System.err, x.words, x.ival); - } - public static void dprint (int[] x) { dprint (System.err, x, x.length); } - public static void dprint (int[] x, int len) { dprint (System.err, x, len); } - public static void dprint (java.io.PrintStream ps, int[] x, int len) - { - ps.print('('); - for (int i = 0; i < len; i++) - { - if (i > 0) - ps.print (' '); - ps.print ("#x" + Long.toString ((long) x[i] & 0xffffffffL, 16)); - } - ps.print(')'); - } - */ -}