biginteger.java

《移动Agent技术》一书的所有章节源代码。

    // Hash Function

    /**
     * Computes a hash code for this object.
     */
    public int hashCode() {
	int hashCode = 0;

	for (int i=0; i<magnitude.length; i++)
	    hashCode = 37*hashCode + (magnitude[i] & 0xff);

	return hashCode * signum;
    }

    // Format Converters

    /**
     * Returns the string representation of this number in the given radix.
     * If the radix is outside the range from Character.MIN_RADIX(2) to
     * Character.MAX_RADIX(36) inclusive, it will default to 10 (as is the
     * case for Integer.toString).  The digit-to-character mapping provided
     * by Character.forDigit is used, and a minus sign is prepended if
     * appropriate.  (This representation is compatible with the (String, int)
     * constructor.)
     */
    public String toString(int radix) {
	if (signum == 0)
	    return "0";
	if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
	    radix = 10;

	/* Compute upper bound on number of digit groups and allocate space */
	int maxNumDigitGroups = (magnitude.length + 6)/7;
	String digitGroup[] = new String[maxNumDigitGroups];

	/* Translate number to string, a digit group at a time */
	BigInteger tmp = this.abs();
	int numGroups = 0;
	while (tmp.signum != 0) {
	    BigInteger b[] = tmp.divideAndRemainder(longRadix[radix]);
	    digitGroup[numGroups++] = Long.toString(b[1].longValue(), radix);
	    tmp = b[0];
	}

	/* Put sign (if any) and first digit group into result buffer */
	StringBuffer buf = new StringBuffer(numGroups*digitsPerLong[radix]+1);
	if (signum<0)
	    buf.append('-');
	buf.append(digitGroup[numGroups-1]);

	/* Append remaining digit groups padded with leading zeros */
	for (int i=numGroups-2; i>=0; i--) {
	    /* Prepend (any) leading zeros for this digit group */
	    int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
	    if (numLeadingZeros != 0)
		buf.append(zeros[numLeadingZeros]);
	    buf.append(digitGroup[i]);
	}

	return buf.toString();
    }

    /* zero[i] is a string of i consecutive zeros. */
    private static String zeros[] = new String[64];
    static {
	zeros[63] =
	    "000000000000000000000000000000000000000000000000000000000000000";
	for (int i=0; i<63; i++)
	    zeros[i] = zeros[63].substring(0, i);
    }

    /**
     * Returns the string representation of this number, radix 10.  The
     * digit-to-character mapping provided by Character.forDigit is used,
     * and a minus sign is prepended if appropriate.  (This representation
     * is compatible with the (String) constructor, and allows for string
     * concatenation with Java's + operator.)
     */
    public String toString() {
	return toString(10);
    }

    /**
     * Returns the two's-complement representation of this number.  The array
     * is big-endian (i.e., the most significant byte is in the [0] position).
     * The array contains the minimum number of bytes required to represent
     * the number (ceil((this.bitLength() + 1)/8)).  (This representation is
     * compatible with the (byte[]) constructor.)
     */
    public byte[] toByteArray() {
	byte[] result = new byte[byteLength()];
	for(int i=0; i<result.length; i++)
	    result[i] = getByte(result.length-i-1);

	return result;
    }

    /**
     * Converts this number to an int.  Standard narrowing primitive conversion
     * as per The Java Language Specification.
     */
    public int intValue() {
	int result = 0;

	for (int i=3; i>=0; i--)
	    result = (result << 8) + (getByte(i) & 0xff);
	return result;
    }

    /**
     * Converts this number to a long.  Standard narrowing primitive conversion
     * as per The Java Language Specification.
     */
    public long longValue() {
	long result = 0;

	for (int i=7; i>=0; i--)
	    result = (result << 8) + (getByte(i) & 0xff);
	return result;
    }

    /**
     * Converts this number to a float.  Similar to the double-to-float
     * narrowing primitive conversion defined in The Java Language
     * Specification: if the number has too great a magnitude to represent
     * as a float, it will be converted to infinity or negative infinity,
     * as appropriate.
     */
    public float floatValue() {
	/* Somewhat inefficient, but guaranteed to work. */
	return Float.valueOf(this.toString()).floatValue();
    }

    /**
     * Converts the number to a double.  Similar to the double-to-float
     * narrowing primitive conversion defined in The Java Language
     * Specification: if the number has too great a magnitude to represent
     * as a double, it will be converted to infinity or negative infinity,
     * as appropriate.
     */
    public double doubleValue() {
	/* Somewhat inefficient, but guaranteed to work. */
	return Double.valueOf(this.toString()).doubleValue();
    }

    static {
	System.loadLibrary("math");
	plumbInit();
    }


    private final static BigInteger ONE = valueOf(1);
    private final static BigInteger TWO = valueOf(2);

    private final static char ZERO_CHAR = Character.forDigit(0, 2);

    /**
     * Returns a copy of the input array stripped of any leading zero bytes.
     */
    static private byte[] stripLeadingZeroBytes(byte a[]) {
	int keep;

	/* Find first nonzero byte */
	for (keep=0; keep<a.length && a[keep]==0; keep++)
	    ;

	/* Allocate new array and copy relevant part of input array */
	byte result[] = new byte[a.length - keep];
	for (int i = keep; i<a.length; i++)
	    result[i - keep] = a[i];

	return result;
    }

    /**
     * Takes an array a representing a negative 2's-complement number and
     * returns the minimal (no leading zero bytes) unsigned whose value is -a.
     */
    static private byte[] makePositive(byte a[]) {
	int keep, j;

	/* Find first non-sign (0xff) byte of input */
	for (keep=0; keep<a.length && a[keep]==-1; keep++)
	    ;

	/* Allocate output array.  If all non-sign bytes are 0x00, we must
	 * allocate space for one extra output byte. */
	for (j=keep; j<a.length && a[j]==0; j++)
	    ;
	int extraByte = (j==a.length ? 1 : 0);
	byte result[] = new byte[a.length - keep + extraByte];

	/* Copy one's complement of input into into output, leaving extra
	 * byte (if it exists) == 0x00 */
	for (int i = keep; i<a.length; i++)
	    result[i - keep + extraByte] = (byte) ~a[i];

	/* Add one to one's complement to generate two's complement */
	for (int i=result.length-1; ++result[i]==0; i--)
	    ;

	return result;
    }

    /*
     * The following two arrays are used for fast String conversions.  Both
     * are indexed by radix.  The first is the number of digits of the given
     * radix that can fit in a Java long without "going negative", i.e., the
     * highest integer n such that radix ** n < 2 ** 63.  The second is the
     * "long radix" that tears each number into "long digits", each of which
     * consists of the number of digits in the corresponding element in
     * digitsPerLong (longRadix[i] = i ** digitPerLong[i]).  Both arrays have
     * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
     * used.
     */

    private static int digitsPerLong[] = {0, 0,
	62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
	14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};

    private static BigInteger longRadix[] = {null, null,
        valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
	valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
	valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
        valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
	valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
	valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
	valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
	valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
	valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
	valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
	valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
	valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
	valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
	valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
	valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
	valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
	valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
	valueOf(0x41c21cb8e1000000L)};


    /**
     * These routines provide access to the two's complement representation
     * of BigIntegers.
     */

    /**
     * Returns the length of the two's complement representation in bytes,
     * including space for at least one sign bit,
     */
    private int byteLength() {
	return bitLength()/8 + 1;
    }

    /* Returns sign bit */
    private int signBit() {
	return (signum < 0 ? 1 : 0);
    }

    /* Returns a byte of sign bits */
    private byte signByte() {
	return (byte) (signum < 0 ? -1 : 0);
    }

    /**
     * Returns the specified byte of the little-endian two's complement
     * representation (byte 0 is the LSB).  The byte number can be arbitrarily
     * high (values are logically preceded by infinitely many sign bytes).
     */
    private byte getByte(int n) {
	if (n >= magnitude.length)
	    return signByte();

	byte magByte = magnitude[magnitude.length-n-1];

	return (byte) (signum >= 0 ? magByte :
		       (n <= firstNonzeroByteNum() ? -magByte : ~magByte));
    }

    /**
     * Returns the index of the first nonzero byte in the little-endian
     * binary representation of the magnitude (byte 0 is the LSB).  If
     * the magnitude is zero, return value is undefined.
     */

     private int firstNonzeroByteNum() {
	/*
	 * Initialize bitCount field the first time this method is executed.
	 * This method depends on the atomicity of int modifies; without
	 * this guarantee, it would have to be synchronized.
	 */
	if (firstNonzeroByteNum == -2) {
	    /* Search for the first nonzero byte */
	    int i;
	    for (i=magnitude.length-1; i>=0 && magnitude[i]==0; i--)
		;
	    firstNonzeroByteNum = magnitude.length-i-1;
	}
	return firstNonzeroByteNum;
    }


    /**
     * Native method wrappers for Colin Plumb's big positive integer package.
     * Each of these wrappers (except for plumbInit) behaves as follows:
     *
     * 	1) Translate input arguments from java byte arrays into plumbNums.
     *
     *  2) Perform the requested computation.
     *
     *  3) Translate result(s) into Java byte array(s).  (The subtract
     *	   operation translates its result into a BigInteger, as its result
     *	   is, effectively, signed.)
     *
     *	4) Deallocate all of the plumbNums.
     *
     *  5) Return the resulting Java array(s) (or, in the case of subtract,
     *	   BigInteger).
     */

    private static native void plumbInit();
    private static native byte[] plumbAdd(byte[] a, byte[] b);
    private static native BigInteger plumbSubtract(byte[] a, byte[] b);
    private static native byte[] plumbMultiply(byte[] a, byte[] b);
    private static native byte[] plumbDivide(byte[] a, byte[] b);
    private static native byte[] plumbRemainder(byte[] a, byte[] b);
    private static native byte[][] plumbDivideAndRemainder(byte[] a, byte[] b);
    private static native byte[] plumbGcd(byte[] a, byte[] b);
    private static native byte[] plumbModPow(byte[] a, byte[] b, byte[] m);
    private static native byte[] plumbModInverse(byte[] a, byte[] m);
    private static native byte[] plumbSquare(byte[] a);
    private static native byte[] plumbGeneratePrime(byte[] a);

    /** use serialVersionUID from JDK 1.1. for interoperability */
    private static final long serialVersionUID = -8287574255936472291L;

    /**
     * Reconstitute the <tt>BigInteger</tt> instance from a stream (that is,
     * deserialize it).
     */
    private synchronized void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in all fields
	s.defaultReadObject();

        // Defensively copy magnitude to ensure immutability
        magnitude = (byte[]) magnitude.clone();

        // Validate signum
	if (signum < -1 || signum > 1)
	    throw new java.io.StreamCorruptedException(
                        "BigInteger: Invalid signum value");
	if ((magnitude.length==0) != (signum==0))
	    throw new java.io.StreamCorruptedException(
                        "BigInteger: signum-magnitude mismatch");

        // Set "cached computation" fields to their initial values
        bitCount = bitLength = -1;
        lowestSetBit = firstNonzeroByteNum = -2;
    }
}