biginteger.java

linux下建立JAVA虚拟机的源码KAFFE

/*
 * Java core library component.
 *
 * Copyright (c) 1997, 1998
 *      Transvirtual Technologies, Inc.  All rights reserved.
 *
 * See the file "license.terms" for information on usage and redistribution
 * of this file.
 */

package java.math;

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

import org.kaffe.util.Ptr;

public class BigInteger extends Number implements Comparable {

private static final long serialVersionUID = -8287574255936472291L;

// serialization is explicitly managed in readObject/writeObject (for
// compatibility with Sun)
private static final ObjectStreamField[] serialPersistentFields = {
	new ObjectStreamField("bitCount", int.class),
	new ObjectStreamField("bitLength", int.class),
	new ObjectStreamField("lowestSetBit", int.class),
	new ObjectStreamField("magnitude", byte[].class),
	new ObjectStreamField("signum", int.class),
};

private transient Ptr number;
private transient int hash;

private static final BigInteger MINUS_ONE;
public static final BigInteger ZERO;
public static final BigInteger ONE;
private static final BigInteger TWO;

static {
	System.loadLibrary("math");
	initialize0();
	/* ZERO and ONE must be defined here, not in their
	   declarations, otherwise they'd be initialized before the
	   libmath is loaded and initialized.  Moving their
	   declarations after this block doesn't help.  */
	MINUS_ONE = new BigInteger(-1L);
	ZERO = new BigInteger();
	ONE = new BigInteger(1L);
	TWO = new BigInteger(2L);
}

public BigInteger(byte val[]) {
	this();
	if (val.length == 0)
		throw new NumberFormatException("val.length == 0");
	int signum = (val[0] & 128) == 0 ? 1 : -1;
	if (signum == -1) {
		int lpc;

		for( lpc = 0; lpc < val.length; lpc++ )
		{
			val[lpc] = (byte)~val[lpc];
		}
	}
	assignBytes0(signum, val);
	if (signum == -1) {
		add0(this, ONE); // adjust two's complement
	}
}

public BigInteger(int signum, byte magnitude[]) {
	this();
	switch (signum) {
	case -1:
	case 0:
	case 1:
		break;
	default:
		throw new NumberFormatException("signum < -1 || signum > 1");
	}
	if (magnitude.length != 0) {
		assignBytes0(signum, magnitude);
		if (signum == 0 && cmp0(this, ZERO) != 0)
			throw new NumberFormatException("signum == 0 && magnitude[i] != 0");
	}
}

public BigInteger(String val, int radix) {
	this();
	if ((radix < Character.MIN_RADIX) || (radix > Character.MAX_RADIX)) {
	    throw new NumberFormatException("Bad radix: " + radix);
	}
	if (assignString0(val, radix) == -1) {
	  throw new NumberFormatException("Bad format: val = " + val + ", radix = " + radix);
	}
}

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

public BigInteger(int numBits, Random rndSrc) {
        this(1, randBytes(numBits, rndSrc));
}

private static byte[] randBytes(int numBits, Random rndSrc) {
	if (numBits < 0)
		throw new IllegalArgumentException("numBits < 0");
	int extra = numBits % 8;
	byte[] ret = new byte[numBits/8 + (extra>0 ? 1 : 0)];
	rndSrc.nextBytes(ret);
	if (extra > 0)
		ret[0] &= ~((~0) << (8-extra));
	return (ret);
}

public BigInteger(int bitLength, int certainty, Random rnd) {
	this();
	if (bitLength < 2)
		throw new ArithmeticException("bitLength < 2");
	byte [] bytes = new byte[(bitLength+7)/8];
	int zeroes = 8 - bitLength%8;
	/* andval is used to zero out unused bits in the most
           significant byte.  */
	byte andval = (byte)(~((~0) << zeroes));
	/* orval is used to set the most significant bit.  */
	byte orval = (byte)(0x100 >> zeroes);
 rerand:
	for(;;) {
		/* There must be a more efficient algorithm! */
		rnd.nextBytes(bytes);
		/* Ensure that we have the requested length.  */
		bytes[0] = (byte)((bytes[0] & andval) | orval);
		if (bitLength > 2) // 2 is prime, do not discard it
			bytes[bytes.length-1] |= 1;
		assignBytes0(1, bytes);
		if (probablyPrime0(certainty) == 1)
			break;
		/* Only test whether the length has changed when
		   testLength is becomes zero.  */
		long testLength = longValue()-1; // make it even
		if (bitLength < 64)
			testLength |= ~0L << bitLength;
		do {
			add0(this, TWO);
			testLength += 2;
			if (testLength == 0
			    && bitLength0() > bitLength)
				continue rerand;
		} while (probablyPrime0(certainty) == 0);
		break;
	}
}

private BigInteger(long val) {
	this();
	assignLong0(val);
}

private BigInteger() {
	init0();
}

public static BigInteger valueOf(long val) {
	return (new BigInteger(val));
}

public BigInteger add(BigInteger val) {
	BigInteger r = new BigInteger();
	r.add0(this, val);
	return (r);
}

private static void checkIfBitAddressIsNotNegative(int n) {
	if (n < 0) {
		throw new ArithmeticException("Negative bit address");
	}
}

public BigInteger subtract(BigInteger val) {
	BigInteger r = new BigInteger();
	r.sub0(this, val);
	return (r);
}

public BigInteger multiply(BigInteger val) {
	BigInteger r = new BigInteger();
	r.mul0(this, val);
	return (r);
}

public BigInteger divide(BigInteger val) {
	BigInteger r = new BigInteger();
	r.div0(this, val);
	return (r);
}

public BigInteger remainder(BigInteger val) {
	BigInteger r = new BigInteger();
	r.rem0(this, val);
	return (r);
}

public BigInteger[] divideAndRemainder(BigInteger val) {
	BigInteger q = new BigInteger();
	BigInteger r = new BigInteger();
	divrem0(q, r, this, val);
	return (new BigInteger[]{ q, r });
}

public BigInteger pow(int exponent) {
	BigInteger r = new BigInteger();
	r.pow0(this, exponent);
	return (r);
}

public BigInteger gcd(BigInteger val) {
	BigInteger r = new BigInteger();
	r.gcd0(this, val);
	return (r);
}

public BigInteger abs() {
	BigInteger r = new BigInteger();
	r.abs0(this);
	return (r);
}

public BigInteger negate() {
	BigInteger r = new BigInteger();
	r.neg0(this);
	return (r);
}

public int signum() {
	return (compareTo(ZERO));
}

public BigInteger mod(BigInteger mod) {
	BigInteger r = new BigInteger();
	r.mod0(this, mod);
	return (r);
}

public BigInteger modPow(BigInteger exponent, BigInteger mod) {
	BigInteger r = new BigInteger();
	r.modpow0(this, exponent, mod);
	return (r);
}

public BigInteger modInverse(BigInteger mod) {
	BigInteger r = new BigInteger();
	r.modinv0(this, mod);
	return (r);
}

private BigInteger shift(int n) {
	/* avoid creation of a new object if n == 0 or this is ZERO */
	if (n == 0 || this.equals(ZERO)) {
		return this;
	}

	/* if we are shifting to right, then n is negative.
	 * We want to avoid creation of new objects when we are
	 * shifting too far to the right.
	 */
	if (bitLength() < -n) {
		switch (signum()) {
		    case 1:
		    case 0:
			    /* For non-negative BigIntegers we return ZERO. */
			    return ZERO;
		    case -1:
			    /* For negative BigIntegers we return MINUS_ONE. */
			    return MINUS_ONE;
		    default:
			    throw new InternalError("signum not in {-1,0,1}");
		}
	}

	BigInteger s = BigInteger.ZERO.setBit(Math.abs(n));
	if (n > 0) {
		/* shift to left == multiply with 2^n */
		return multiply(s);
	}
	else { /* n < 0 */
		switch (signum()) {
		    case 1:
			    /* shift to right : if this is positive,
			     * then division by 2^n will round to floor.
			     * Rounding to floor is demanded by API spec.
			     */
			    return divide(s);
		    case 0:
			    /* shifting 0 to right always yields 0 */ 
			    return this;
		    case -1:
			    /* shift to right : if this is negative,
			     * then division by 2^n will not round to floor.
			     *
			     * Using BigDecimal's division would be overkill.
			     * We simulate the division with floor rounding.
			     * If the remainder is not 0, we substract 1 from
			     * the result.
			     */
			    BigInteger [] qr = divideAndRemainder(s);
			    if (!qr[1].equals(ZERO)) {
				    qr[0] = qr[0].subtract(ONE);
			    }
			    return qr[0];
		    default:
			    throw new InternalError("signum not in {-1,0,1}");
		}
	}
}

public BigInteger shiftLeft(int n) {
	return shift(n);
}

public BigInteger shiftRight(int n) {
	return shift(-n);
}

public BigInteger and(BigInteger val) {
	BigInteger r = new BigInteger();
	r.and0(this, val);
	return (r);
}