biginteger.java

gcc的组建

/* java.math.BigInteger -- Arbitary precision integers
   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005  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., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 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. */


package java.math;

import gnu.java.math.MPN;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Random;

/**
 * Written using on-line Java Platform 1.2 API Specification, as well
 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
 * 
 * Based primarily on IntNum.java BitOps.java by Per Bothner ([e-mail])
 * (found in Kawa 1.6.62).
 *
 * @author Warren Levy ([e-mail])
 * @date December 20, 1999.
 * @status believed complete and correct.
 */
public class BigInteger extends Number implements Comparable
{
  /** All integers are stored in 2's-complement form.
   * 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 transient int ival;
  private transient 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. 
   * Note that we must at least preallocate 0, 1, and 10.  */
  private static final int minFixNum = -100;
  private static final int maxFixNum = 1024;
  private static final int numFixNum = maxFixNum-minFixNum+1;
  private static final BigInteger[] smallFixNums = new BigInteger[numFixNum];

  static {
    for (int i = numFixNum;  --i >= 0; )
      smallFixNums[i] = new BigInteger(i + minFixNum);
  }

  /**
   * The constant zero as a BigInteger.
   * @since 1.2
   */
  public static final BigInteger ZERO = smallFixNums[-minFixNum];

  /**
   * The constant one as a BigInteger.
   * @since 1.2
   */
  public static final BigInteger ONE = smallFixNums[1 - minFixNum];
  
  /**
   * The constant ten as a BigInteger.
   * @since 1.5
   */
  public static final BigInteger TEN = smallFixNums[10 - minFixNum];

  /* Rounding modes: */
  private static final int FLOOR = 1;
  private static final int CEILING = 2;
  private static final int TRUNCATE = 3;
  private static final int ROUND = 4;

  /** When checking the probability of primes, it is most efficient to
   * first check the factoring of small primes, so we'll use this array.
   */
  private static final int[] primes =
    {   2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,
       47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97, 101, 103, 107,
      109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
      191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };

  /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
  private static final int[] k =
      {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
  private static final int[] t =
      { 27, 18, 15, 12,  9,  8,  7,  6,  5,  4,   3, 2};

  private BigInteger()
  {
  }

  /* Create a new (non-shared) BigInteger, and initialize to an int. */
  private BigInteger(int value)
  {
    ival = value;
  }

  public BigInteger(String val, int radix)
  {
    BigInteger result = valueOf(val, radix);
    this.ival = result.ival;
    this.words = result.words;
  }

  public BigInteger(String val)
  {
    this(val, 10);
  }

  /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
  public BigInteger(byte[] val)
  {
    if (val == null || val.length < 1)
      throw new NumberFormatException();

    words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
    BigInteger result = make(words, words.length);
    this.ival = result.ival;
    this.words = result.words;
  }

  public BigInteger(int signum, byte[] magnitude)
  {
    if (magnitude == null || signum > 1 || signum < -1)
      throw new NumberFormatException();

    if (signum == 0)
      {
	int i;
	for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
	  ;
	if (i >= 0)
	  throw new NumberFormatException();
        return;
      }

    // Magnitude is always positive, so don't ever pass a sign of -1.
    words = byteArrayToIntArray(magnitude, 0);
    BigInteger result = make(words, words.length);
    this.ival = result.ival;
    this.words = result.words;

    if (signum < 0)
      setNegative();
  }

  public BigInteger(int numBits, Random rnd)
  {
    if (numBits < 0)
      throw new IllegalArgumentException();

    init(numBits, rnd);
  }

  private void init(int numBits, Random rnd)
  {
    int highbits = numBits & 31;
    if (highbits > 0)
      highbits = rnd.nextInt() >>> (32 - highbits);
    int nwords = numBits / 32;

    while (highbits == 0 && nwords > 0)
      {
	highbits = rnd.nextInt();
	--nwords;
      }
    if (nwords == 0 && highbits >= 0)
      {
	ival = highbits;
      }
    else
      {
	ival = highbits < 0 ? nwords + 2 : nwords + 1;
	words = new int[ival];
	words[nwords] = highbits;
	while (--nwords >= 0)
	  words[nwords] = rnd.nextInt();
      }
  }

  public BigInteger(int bitLength, int certainty, Random rnd)
  {
    this(bitLength, rnd);

    // Keep going until we find a probable prime.
    while (true)
      {
	if (isProbablePrime(certainty))
	  return;

	init(bitLength, rnd);
      }
  }

  /** 
   *  Return a BigInteger that is bitLength bits long with a
   *  probability < 2^-100 of being composite.
   *
   *  @param bitLength length in bits of resulting number
   *  @param rnd random number generator to use
   *  @throws ArithmeticException if bitLength < 2
   *  @since 1.4
   */
  public static BigInteger probablePrime(int bitLength, Random rnd)
  {
    if (bitLength < 2)
      throw new ArithmeticException();

    return new BigInteger(bitLength, 100, rnd);
  }

  /** Return a (possibly-shared) BigInteger with a given long value. */
  public static BigInteger valueOf(long val)
  {
    if (val >= minFixNum && val <= maxFixNum)
      return smallFixNums[(int) val - minFixNum];
    int i = (int) val;
    if ((long) i == val)
      return new BigInteger(i);
    BigInteger result = alloc(2);
    result.ival = 2;
    result.words[0] = i;
    result.words[1] = (int)(val >> 32);
    return result;
  }

  /** Make a canonicalized BigInteger from an array of words.
   * The array may be reused (without copying). */
  private static BigInteger make(int[] words, int len)
  {
    if (words == null)
      return valueOf(len);
    len = BigInteger.wordsNeeded(words, len);
    if (len <= 1)
      return len == 0 ? ZERO : valueOf(words[0]);
    BigInteger num = new BigInteger();
    num.words = words;
    num.ival = len;
    return num;
  }

  /** Convert a big-endian byte array to a little-endian array of words. */
  private static int[] byteArrayToIntArray(byte[] bytes, int sign)
  {
    // Determine number of words needed.
    int[] words = new int[bytes.length/4 + 1];
    int nwords = words.length;

    // Create a int out of modulo 4 high order bytes.
    int bptr = 0;
    int word = sign;
    for (int i = bytes.length % 4; i > 0; --i, bptr++)
      word = (word << 8) | (bytes[bptr] & 0xff);
    words[--nwords] = word;

    // Elements remaining in byte[] are a multiple of 4.
    while (nwords > 0)
      words[--nwords] = bytes[bptr++] << 24 |
			(bytes[bptr++] & 0xff) << 16 |
			(bytes[bptr++] & 0xff) << 8 |
			(bytes[bptr++] & 0xff);
    return words;
  }

  /** Allocate a new non-shared BigInteger.
   * @param nwords number of words to allocate
   */
  private static BigInteger alloc(int nwords)
  {
    BigInteger result = new BigInteger();
    if (nwords > 1)
    result.words = new int[nwords];
    return result;
  }

  /** Change words.length to nwords.
   * We allow words.length to be upto nwords+2 without reallocating.
   */
  private void realloc(int nwords)
  {
    if (nwords == 0)
      {
	if (words != null)
	  {
	    if (ival > 0)
	      ival = words[0];
	    words = null;
	  }
      }
    else if (words == null
	     || words.length < nwords
	     || words.length > nwords + 2)
      {
	int[] new_words = new int [nwords];
	if (words == null)
	  {
	    new_words[0] = ival;
	    ival = 1;
	  }
	else
	  {
	    if (nwords < ival)
	      ival = nwords;
	    System.arraycopy(words, 0, new_words, 0, ival);
	  }
	words = new_words;
      }
  }

  private boolean isNegative()
  {
    return (words == null ? ival : words[ival - 1]) < 0;
  }

  public int signum()
  {
    int top = words == null ? ival : words[ival-1];
    if (top == 0 && words == null)
      return 0;
    return top < 0 ? -1 : 1;
  }

  private static int compareTo(BigInteger x, BigInteger y)
  {
    if (x.words == null && y.words == null)
      return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
    boolean x_negative = x.isNegative();
    boolean y_negative = y.isNegative();
    if (x_negative != y_negative)
      return x_negative ? -1 : 1;
    int x_len = x.words == null ? 1 : x.ival;
    int y_len = y.words == null ? 1 : y.ival;
    if (x_len != y_len)
      return (x_len > y_len) != x_negative ? 1 : -1;
    return MPN.cmp(x.words, y.words, x_len);
  }

  // JDK1.2
  public int compareTo(Object obj)
  {
    if (obj instanceof BigInteger)
      return compareTo(this, (BigInteger) obj);
    throw new ClassCastException();
  }

  public int compareTo(BigInteger val)
  {
    return compareTo(this, val);
  }

  public BigInteger min(BigInteger val)
  {
    return compareTo(this, val) < 0 ? this : val;
  }

  public BigInteger max(BigInteger val)
  {
    return compareTo(this, val) > 0 ? this : val;
  }

  private boolean isZero()
  {
    return words == null && ival == 0;
  }

  private boolean isOne()
  {
    return words == null && ival == 1;
  }

  /** Calculate how many words are significant in words[0:len-1].
   * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
   * when words is viewed as a 2's complement integer.
   */
  private static int wordsNeeded(int[] words, int len)
  {
    int i = len;
    if (i > 0)
      {
	int word = words[--i];
	if (word == -1)
	  {
	    while (i > 0 && (word = words[i - 1]) < 0)
	      {
		i--;
		if (word != -1) break;
	      }
	  }
	else
	  {
	    while (word == 0 && i > 0 && (word = words[i - 1]) >= 0)  i--;
	  }
      }
    return i + 1;
  }

  private BigInteger canonicalize()
  {
    if (words != null
	&& (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
      {
	if (ival == 1)
	  ival = words[0];
	words = null;
      }
    if (words == null && ival >= minFixNum && ival <= maxFixNum)
      return smallFixNums[ival - minFixNum];
    return this;
  }

  /** Add two ints, yielding a BigInteger. */
  private static BigInteger add(int x, int y)
  {
    return valueOf((long) x + (long) y);
  }

  /** Add a BigInteger and an int, yielding a new BigInteger. */
  private static BigInteger add(BigInteger x, int y)
  {
    if (x.words == null)
      return BigInteger.add(x.ival, y);
    BigInteger result = new BigInteger(0);
    result.setAdd(x, y);
    return result.canonicalize();
  }

  /** Set this to the sum of x and y.
   * OK if x==this. */
  private void setAdd(BigInteger x, int y)
  {
    if (x.words == null)
      {
	set((long) x.ival + (long) y);
	return;
      }
    int len = x.ival;
    realloc(len + 1);
    long carry = y;
    for (int i = 0;  i < len;  i++)
      {
	carry += ((long) x.words[i] & 0xffffffffL);
	words[i] = (int) carry;
	carry >>= 32;
      }
    if (x.words[len - 1] < 0)
      carry--;
    words[len] = (int) carry;
    ival = wordsNeeded(words, len + 1);
  }

  /** Destructively add an int to this. */
  private void setAdd(int y)
  {
    setAdd(this, y);
  }

  /** Destructively set the value of this to a long. */
  private void set(long y)
  {
    int i = (int) y;
    if ((long) i == y)
      {
	ival = i;
	words = null;
      }
    else
      {
	realloc(2);
	words[0] = i;
	words[1] = (int) (y >> 32);
	ival = 2;
      }
  }

  /** Destructively set the value of this to the given words.
  * The words array is reused, not copied. */
  private void set(int[] words, int length)
  {
    this.ival = length;
    this.words = words;
  }

  /** Destructively set the value of this to that of y. */
  private void set(BigInteger y)
  {
    if (y.words == null)
      set(y.ival);
    else if (this != y)
      {
	realloc(y.ival);
	System.arraycopy(y.words, 0, words, 0, y.ival);
	ival = y.ival;
      }
  }

  /** Add two BigIntegers, yielding their sum as another BigInteger. */
  private static BigInteger add(BigInteger x, BigInteger y, int k)
  {
    if (x.words == null && y.words == null)
      return valueOf((long) k * (long) y.ival + (long) x.ival);
    if (k != 1)
      {
	if (k == -1)
	  y = BigInteger.neg(y);
	else
	  y = BigInteger.times(y, valueOf(k));
      }
    if (x.words == null)
      return BigInteger.add(y, x.ival);
    if (y.words == null)
      return BigInteger.add(x, y.ival);
    // Both are big
    if (y.ival > x.ival)
      { // Swap so x is longer then y.
	BigInteger tmp = x;  x = y;  y = tmp;
      }
    BigInteger result = alloc(x.ival + 1);
    int i = y.ival;
    long carry = MPN.add_n(result.words, x.words, y.words, i);