biginteger.java

来自「《移动Agent技术》一书的所有章节源代码。」· Java 代码 · 共 1,801 行 · 第 1/3 页

package java.math;

import java.util.Random;

public class BigInteger
{

	private int sign;	// -1 means -ve; +1 means +ve; 0 means 0;
	private int magnitude[];// array of ints with [0] being the most significant
	private int nBits = -1; // cache bitCount() value
	private int nBitLength = -1; // cache bitLength() value
	private static final long IMASK = 0xffffffffL;

    private BigInteger()
    {
    }

	private BigInteger(int nWords) {
		sign = 1;
		magnitude = new int[nWords];
	}


	private BigInteger(
		int signum,
		int[] mag)
	{
		sign = signum;
		if (mag.length > 0)
        {
			int i = 0;
			while (i < mag.length && mag[i] == 0)
            {
                i++;
            }
			if (i == 0)
            {
				magnitude = mag;
            }
			else
            {
				// strip leading 0 bytes
				int[] newMag = new int[mag.length - i];
				System.arraycopy(mag, i, newMag, 0, newMag.length);
				magnitude = newMag;
				if (newMag.length == 0) sign = 0;
            }
        }
		else
        {
			magnitude = mag;
			sign = 0;
        }
	}

	public BigInteger(
	    String sval)
		throws NumberFormatException
	{
		this(sval, 10);
	}


	public BigInteger(
	    String sval,
		int rdx)
		throws NumberFormatException
	{
		if (sval.length() == 0) {
			throw new NumberFormatException("Zero length BigInteger");
			}

		if (rdx < Character.MIN_RADIX || rdx > Character.MAX_RADIX) {
			throw new NumberFormatException("Radix out of range");
			}

		int index = 0;
		sign = 1;

		if (sval.charAt(0) == '-') {
			if (sval.length() == 1) {
				throw new NumberFormatException("Zero length BigInteger");
				}

			sign = -1;
			index = 1;
			}

		// strip leading zeros from the string value
		while (index < sval.length() &&
				Character.digit(sval.charAt(index), rdx) == 0) {
			index++;
			}

		if (index >= sval.length()) {
			// zero value - we're done
			sign = 0;
			magnitude = new int[0];
			return;
			}

		//////
		// could we work out the max number of ints required to store
		// sval.length digits in the given base, then allocate that
		// storage in one hit?, then generate the magnitude in one hit too?
		//////

		BigInteger b = BigInteger.ZERO;
		BigInteger r = valueOf(rdx);
		while (index < sval.length()) {
			// (optimise this by taking chunks of digits instead?)
			b = b.multiply(r).add(valueOf(Character.digit(sval.charAt(index), rdx)));
			index++;
			}

		magnitude = b.magnitude;

		return;
	}


	public BigInteger(
	    byte[] bval)
		throws NumberFormatException
	{
		if (bval.length == 0) {
			throw new NumberFormatException("Zero length BigInteger");
			}

		sign = 1;
		if (bval[0] < 0) {
			// FIXME:
			int iBval;
			sign = -1;
			// strip leading sign bytes
			for (iBval = 0; iBval < bval.length && bval[iBval] == -1; iBval++) ;
			magnitude = new int[(bval.length - iBval)/2 + 1];
			// copy bytes to magnitude
			// invert bytes then add one to find magnitude of value
			}
		else {
			// strip leading zero bytes and return magnitude bytes
			magnitude = makeMagnitude(bval);
			}
	}


	private int[] makeMagnitude(byte[] bval) {
		int i;
		int[] mag;
		int firstSignificant;

		// strip leading zeros
		for (firstSignificant = 0;
			firstSignificant < bval.length && bval[firstSignificant] == 0;
			firstSignificant++) ;

		if (firstSignificant >= bval.length) {
			return new int[0];
			}

		int nInts = (bval.length - firstSignificant + 3) / 4;
		int bCount = (bval.length - firstSignificant) % 4;
		if (bCount == 0) bCount = 4;

		mag = new int[nInts];
		int v = 0;
		int magnitudeIndex = 0;
		for (i = firstSignificant; i < bval.length; i++)
        {
			v <<= 8;
			v |= bval[i] & 0xff;
			bCount--;
			if (bCount <= 0)
            {
				mag[magnitudeIndex] = v;
				magnitudeIndex++;
				bCount = 4;
				v = 0;
            }
        }

		if (magnitudeIndex < mag.length)
        {
			mag[magnitudeIndex] = v;
        }

		return mag;
	}


	public BigInteger(
		int sign,
		byte[] mag)
		throws NumberFormatException
	{
		if (sign < -1 || sign > 1)
        {
			throw new NumberFormatException("Invalid sign value");
        }

		if (sign == 0)
        {
			this.sign = 0;
			this.magnitude = new int[0];
			return;
        }

		// copy bytes
		this.magnitude = makeMagnitude(mag);
		this.sign = sign;
	}


	public BigInteger(
	    int numBits,
		Random rnd)
		throws IllegalArgumentException
	{
		if (numBits < 0)
        {
			throw new IllegalArgumentException("numBits must be non-negative");
        }

		int nBytes = (numBits + 7) / 8;

		byte[] b = new byte[nBytes];

        if (nBytes > 0)
        {
            nextRndBytes(rnd, b);
            // strip off any excess bits in the MSB
            b[0] &= rndMask[8*nBytes - numBits];
        }

        this.magnitude = makeMagnitude(b);
        this.sign = 1;
        this.nBits = -1;
        this.nBitLength = -1;
	}


	private static final int BITS_PER_BYTE = 8;
	private static final int BYTES_PER_INT = 4;

    /**
     * strictly speaking this is a little dodgey from a compliance
     * point of view as it forces people to be using SecureRandom as
     * well, that being said - this implementation is for a crypto
     * library and you do have the source!
     */
	private void nextRndBytes(
        Random rnd,
        byte[] bytes)
    {
		int numRequested = bytes.length;
		int numGot = 0, r = 0;

        if (rnd instanceof java.security.SecureRandom)
        {
            ((java.security.SecureRandom)rnd).nextBytes(bytes);
        }
        else
        {
            for (;;)
            {
			    for (int i = 0; i < BYTES_PER_INT; i++)
                {
                    if (numGot == numRequested)
                    {
                        return;
                    }

                    r = (i==0 ? rnd.nextInt() : r >> BITS_PER_BYTE);
				    bytes[numGot++] = (byte)r;
				}
			}
        }
	}

	private static final byte[] rndMask = {(byte)255, 127, 63, 31, 15, 7, 3, 1};


	public BigInteger(
	    int bitLength,
		int certainty,
		Random rnd)
		throws ArithmeticException
	{
        int nBytes = (bitLength + 7) / 8;

        byte[] b = new byte[nBytes];

		do
        {
            if (nBytes > 0)
            {
                nextRndBytes(rnd, b);
                // strip off any excess bits in the MSB
                b[0] &= rndMask[8*nBytes - bitLength];
            }

            this.magnitude = makeMagnitude(b);
            this.sign = 1;
            this.nBits = -1;
            this.nBitLength = -1;
            if (certainty > 0 && bitLength > 2)
            {
                this.magnitude[this.magnitude.length - 1] |= 1;
            }
        }
        while (this.bitLength() != bitLength
                    || !this.isProbablePrime(certainty));
	}

	public BigInteger abs()
	{
		return (sign >= 0) ? this : this.negate();
	}

    /**
     * return a = a + b - b preserved.
     */
    private int[] add(
        int[]   a,
        int[]   b)
    {
		int     tI = a.length - 1;
		int     vI = b.length - 1;
		long    m = 0;

        while (vI >= 0)
        {
            m += (((long)a[tI]) & IMASK) + (((long)b[vI--]) & IMASK);
            a[tI--] = (int)m;
            m >>>= 32;
        }

        while (tI >= 0 && m != 0)
        {
            m += (((long)a[tI]) & IMASK);
            a[tI--] = (int)m;
            m >>>= 32;
        }

        return a;
    }

	public BigInteger add(
		BigInteger val)
		throws ArithmeticException
	{
		if (val.sign == 0 || val.magnitude.length == 0) return this;
		if (this.sign == 0 || this.magnitude.length == 0) return val;

		if (val.sign < 0)
        {
			if (this.sign > 0) return this.subtract(val.negate());
        }
		else
        {
			if (this.sign < 0) return val.subtract(this.negate());
        }

		// both BigIntegers are either +ve or -ve; set the sign later

        int[]   mag, op;

        if (this.magnitude.length < val.magnitude.length)
        {
		    mag = new int[val.magnitude.length + 1];

            System.arraycopy(val.magnitude, 0, mag, 1, val.magnitude.length);
            op = this.magnitude;
        }
        else
        {
		    mag = new int[this.magnitude.length + 1];

            System.arraycopy(this.magnitude, 0, mag, 1, this.magnitude.length);
            op = val.magnitude;
        }

		return new BigInteger(this.sign, add(mag, op));
	}

	public int bitCount()
	{
		if (nBits == -1) {
			nBits = 0;
			for (int i = 0; i < magnitude.length; i++) {
				nBits += bitCounts[magnitude[i] & 0xff];
				nBits += bitCounts[(magnitude[i] >> 8) & 0xff];
				nBits += bitCounts[(magnitude[i] >> 16) & 0xff];
				nBits += bitCounts[(magnitude[i] >> 24) & 0xff];
				}
			}

		return nBits;
	}


    private final static byte bitCounts[] = {
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};


    private int bitLength(
        int     indx,
        int[]   mag)
	{
        int bitLength;

        if (mag.length == 0)
        {
            return 0;
        }
        else
        {
            while (indx != mag.length && mag[indx] == 0)
            {
                indx++;
            }

            if (indx == mag.length)
            {
                return 0;
            }

            // bit length for everything after the first int
            bitLength = 32 * ((mag.length - indx) - 1);

            // and determine bitlength of first int
            bitLength += bitLen(mag[indx]);

            if (sign < 0)
            {
                // Check if magnitude is a power of two
                boolean pow2 =
                    ((bitCounts[mag[indx] & 0xff]) +
                    (bitCounts[(mag[indx] >> 8) & 0xff]) +
                    (bitCounts[(mag[indx] >> 16) & 0xff]) +
                    (bitCounts[(mag[indx] >> 24) & 0xff])) == 1;

                for (int i = indx + 1; i < mag.length && pow2; i++)
                {
                    pow2 = (mag[i] == 0);
                }

                bitLength -= (pow2 ? 1 : 0);
            }
        }

		return bitLength;
    }

	public int bitLength()
	{
		if (nBitLength == -1)
        {
			if (sign == 0)
            {
                nBitLength = 0;
            }
            else
            {
                nBitLength = bitLength(0, magnitude);
            }
        }

		return nBitLength;
	}


	//
	// bitLen(val) is the number of bits in val.
	//
	static int bitLen(int w) {
        	// Binary search - decision tree (5 tests, rarely 6)
        return
         (w < 1<<15 ?
          (w < 1<<7 ?
           (w < 1<<3 ?
            (w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) :
            (w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) :
           (w < 1<<11 ?
            (w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) :
            (w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) :
          (w < 1<<23 ?
           (w < 1<<19 ?
            (w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) :
            (w < 1<<21 ? (w < 1<<20 ? 20 : 21) : (w < 1<<22 ? 22 : 23))) :
           (w < 1<<27 ?
            (w < 1<<25 ? (w < 1<<24 ? 24 : 25) : (w < 1<<26 ? 26 : 27)) :
            (w < 1<<29 ? (w < 1<<28 ? 28 : 29) : (w < 1<<30 ? 30 : 31)))));
    }


    private final static byte bitLengths[] = {
		0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
		5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};


	public int compareTo(Object o) {
		return compareTo((BigInteger)o);
	}

    /**
     * unsigned comparison on two arrays - note the arrays may
     * start with leading zeros.
     */
    private int compareTo(
        int     xIndx,
        int[]   x,
        int     yIndx,
        int[]   y)
    {
        while (xIndx != x.length && x[xIndx] == 0)
        {
            xIndx++;
        }

        while (yIndx != y.length && y[yIndx] == 0)
        {
            yIndx++;
        }

		if ((x.length - xIndx) < (y.length - yIndx))
        {
            return -1;
        }

		if ((x.length - xIndx) > (y.length - yIndx))
        {
            return 1;
        }

		// lengths of magnitudes the same, test the magnitude values
        
        while (xIndx < x.length)
        {
			long v1 = (long)(x[xIndx++]) & IMASK;
			long v2 = (long)(y[yIndx++]) & IMASK;
			if (v1 < v2)
            {
                return -1;
            }
			if (v1 > v2)
            {
                return 1;
            }
        }

		return 0;
    }

	public int compareTo(
		BigInteger val)
	{
		if (sign < val.sign) return -1;
		if (sign > val.sign) return 1;

        return compareTo(0, magnitude, 0, val.magnitude);
	}

    /**
     * return z = x / y - done in place (z value preserved, x contains the
     * remainder)
     */
    private int[] divide(
        int[]   x,
        int[]   y)
    {