java.math.BigInteger merges

[Per Bothner <per at bothner dot com>]

I checked this into the trunk.  It should probably also be checked into
the Gcc 3.0 branch.  These are basically merging in of patches from
Kawa's gnu.math package (from which the BigInteger implementation was taken).

I believe this fixes libgcj/1615.

2001-03-01  Per Bothner  <per@bothner.com>

	Changes merged from Kawa's gnu.math.
	* java/math/BigInteger.java 
	* gnu/gcj/math/MPN.java (rshift0): New method handles zero shift count.
	(rshift(int[],int[],int,int):  Removed - not needed.
	(gcd):  Use rshift0 rather than rshift.
	* java/math/BigInteger.java (setShiftRight):  Likewise.
	(divide):  Simplify by using rshift0.
	(divide):  Zero-extend results if high-order bit set.

Index: gnu/gcj/math/MPN.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/gnu/gcj/math/MPN.java,v
retrieving revision 1.3
diff -u -r1.3 MPN.java
--- MPN.java	2000/03/07 19:55:24	1.3
+++ MPN.java	2001/03/02 06:46:48
@@ -481,7 +481,7 @@
     return xlen > ylen ? 1 : xlen < ylen ? -1 : cmp (x, y, xlen);
   }
 
-  /* Shift x[x_start:x_start+len-1]count bits to the "right"
+  /* 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.
@@ -506,6 +506,23 @@
     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
@@ -530,20 +547,6 @@
     return ((long)w1 << 32) | ((long)w0 & 0xffffffffL);
   }
 
-  /* Shift x[0: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.
-   * OK if count > 32 (but must be >= 0).
-   */
-  public static void rshift (int[] dest, int[] x, int len, int count)
-  {
-    int word_count = count >> 5;
-    count &= 31;
-    rshift (dest, x, word_count, len, count);
-    while (word_count < len)
-      dest[word_count++] = 0;
-  }
-
   /* 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.
@@ -624,8 +627,8 @@
 
     // Temporarily devide both x and y by 2**sh.
     len -= initShiftWords;
-    MPN.rshift (x, x, initShiftWords, len, initShiftBits);
-    MPN.rshift (y, y, initShiftWords, len, initShiftBits);
+    MPN.rshift0 (x, x, initShiftWords, len, initShiftBits);
+    MPN.rshift0 (y, y, initShiftWords, len, initShiftBits);
 
     int[] odd_arg; /* One of x or y which is odd. */
     int[] other_arg; /* The other one can be even or odd. */
@@ -704,7 +707,7 @@
   }
 
   /** Calcaulte the Common Lisp "integer-length" function.
-   * Assumes input is canonicalized:  len==IntNum.wordsNeeded(words,len) */
+   * Assumes input is canonicalized:  len==BigInteger.wordsNeeded(words,len) */
   public static int intLength (int[] words, int len)
   {
     len--;
@@ -712,7 +715,7 @@
   }
 
   /* DEBUGGING:
-  public static void dprint (IntNum x)
+  public static void dprint (BigInteger x)
   {
     if (x.words == null)
       System.err.print(Long.toString((long) x.ival & 0xffffffffL, 16));
Index: java/math/BigInteger.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/math/BigInteger.java,v
retrieving revision 1.10
diff -u -r1.10 BigInteger.java
--- BigInteger.java	2001/01/17 04:13:17	1.10
+++ BigInteger.java	2001/03/02 06:46:49
@@ -794,13 +794,7 @@
 	  xwords[xlen++] = 0;
 	MPN.divide(xwords, xlen, ywords, ylen);
 	rlen = ylen;
-	if (remainder != null || rounding_mode != TRUNCATE)
-	  {
-	    if (nshift == 0)
-	      System.arraycopy(xwords, 0, ywords, 0, rlen);
-	    else
-	      MPN.rshift(ywords, xwords, 0, rlen, nshift);
-	  }
+	MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
 
 	qlen = xlen + 1 - ylen;
 	if (quotient != null)
@@ -810,6 +804,12 @@
 	  }
       }
 
+    if (ywords[rlen-1] < 0)
+      {
+        ywords[rlen] = 0;
+        rlen++;
+      }
+
     // Now the quotient is in xwords, and the remainder is in ywords.
 
     boolean add_one = false;
@@ -1399,15 +1399,10 @@
 	  {
 	    if (words == null || words.length < d_len)
 	      realloc(d_len);
-	    if (count == 0)
-	      System.arraycopy(x.words, word_count, words, 0, d_len);
-            else
-	      {
-		MPN.rshift(words, x.words, word_count, d_len, count);
-        	if (neg)
-        	  words[d_len-1] |= -1 << (32 - count);
-              }
+	    MPN.rshift0 (words, x.words, word_count, d_len, count);
 	    ival = d_len;
+	    if (neg)
+	      words[d_len-1] |= -1 << (32 - count);
 	  }
       }
   }

-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/