2001-08-17 Mark J Roberts <mjr@anarcast.net>

[pf3gnuchains/gcc-fork.git] / libjava / java / math / BigInteger.java

diff --git a/libjava/java/math/BigInteger.java b/libjava/java/math/BigInteger.java
index 69e7f68..b9bfee6 100644 (file)
--- a/libjava/java/math/BigInteger.java
+++ b/libjava/java/math/BigInteger.java
@@ -1,6 +1,6 @@
 // BigInteger.java -- an arbitrary-precision integer
 
-/* Copyright (C) 1999, 2000  Free Software Foundation
+/* Copyright (C) 1999, 2000, 2001  Free Software Foundation
 
    This file is part of libgcj.
 
@@ -11,6 +11,9 @@ details.  */
 package java.math;
 import gnu.gcj.math.*;
 import java.util.Random;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.IOException;
 
 /**
  * @author Warren Levy <warrenl@cygnus.com>
@@ -35,8 +38,17 @@ public class BigInteger extends Number implements Comparable
    * If words == null, the ival is the value of this BigInteger.
    * Otherwise, the first ival elements of words make the value
    * of this BigInteger, stored in little-endian order, 2's-complement form. */
-  private int ival;
-  private int[] words;
+  transient private int ival;
+  transient private int[] words;
+
+  // Serialization fields.
+  private int bitCount = -1;
+  private int bitLength = -1;
+  private int firstNonzeroByteNum = -2;
+  private int lowestSetBit = -2;
+  private byte[] magnitude;
+  private int signum;
+  private static final long serialVersionUID = -8287574255936472291L;
 
 
   /** We pre-allocate integers in the range minFixNum..maxFixNum. */
@@ -132,21 +144,20 @@ public class BigInteger extends Number implements Comparable
 
   public BigInteger(int numBits, Random rnd)
   {
+    this(1, randBytes(numBits, rnd));
+  }
+
+  private static byte[] randBytes(int numBits, Random rnd)
+  {
     if (numBits < 0)
       throw new IllegalArgumentException();
 
-    // Result is always positive so tack on an extra zero word, it will be
-    // canonicalized out later if necessary.
-    int nwords = numBits / 32 + 2;
-    words = new int[nwords];
-    words[--nwords] = 0;
-    words[--nwords] = rnd.nextInt() >>> (numBits % 32);
-    while (--nwords >= 0)
-      words[nwords] = rnd.nextInt();
-
-    BigInteger result = make(words, words.length);
-    this.ival = result.ival;
-    this.words = result.words;
+    int extra = numBits % 8;
+    byte[] b = new byte[numBits / 8 + (extra > 0 ? 1 : 0)];
+    rnd.nextBytes(b);
+    if (extra > 0)
+      b[0] &= ~((~0) << (8 - extra));
+    return b;
   }
 
   public BigInteger(int bitLength, int certainty, Random rnd)
@@ -208,13 +219,9 @@ public class BigInteger extends Number implements Comparable
   private static int[] byteArrayToIntArray(byte[] bytes, int sign)
   {
     // Determine number of words needed.
-    int[] words = new int[(bytes.length + 3) / 4 + 1];
+    int[] words = new int[bytes.length/4 + 1];
     int nwords = words.length;
 
-    // For simplicity, tack on an extra word of sign at the front,
-    // it will be canonicalized out later. */
-    words[--nwords] = sign;
-
     // Create a int out of modulo 4 high order bytes.
     int bptr = 0;
     int word = sign;
@@ -750,6 +757,12 @@ public class BigInteger extends Number implements Comparable
     else if (ylen == 1)
       {
        qlen = xlen;
+       // Need to leave room for a word of leading zeros if dividing by 1
+       // and the dividend has the high bit set.  It might be safe to
+       // increment qlen in all cases, but it certainly is only necessary
+       // in the following case.
+       if (ywords[0] == 1 && xwords[xlen-1] < 0)
+         qlen++;
        rlen = 1;
        ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
       }
@@ -770,19 +783,13 @@ public class BigInteger extends Number implements Comparable
            // significant word.
            int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
            xwords[xlen++] = x_high;
-       }
+         }
 
        if (xlen == ylen)
          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)
@@ -792,6 +799,12 @@ public class BigInteger extends Number implements Comparable
          }
       }
 
+    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;
@@ -1381,10 +1394,10 @@ public class BigInteger extends Number implements Comparable
          {
            if (words == null || words.length < d_len)
              realloc(d_len);
-           MPN.rshift(words, x.words, word_count, d_len, count);
+           MPN.rshift0 (words, x.words, word_count, d_len, count);
            ival = d_len;
            if (neg)
-             words[ival-1] |= -1 << (32 - count);
+             words[d_len-1] |= -2 << (31 - count);
          }
       }
   }
@@ -2192,4 +2205,22 @@ public class BigInteger extends Number implements Comparable
       }
     return isNegative() ? x_len * 32 - i : i;
   }
+
+  private void readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    s.defaultReadObject();
+    words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
+    BigInteger result = make(words, words.length);
+    this.ival = result.ival;
+    this.words = result.words;
+  }
+
+  private void writeObject(ObjectOutputStream s)
+    throws IOException, ClassNotFoundException
+  {
+    signum = signum();
+    magnitude = toByteArray();
+    s.defaultWriteObject();
+  }
 }