/* * Copyright 2003 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. *//* * @(#)MutableBigInteger.java	1.9 03/01/23 */package java.math;/** * A class used to represent multiprecision integers that makes efficient * use of allocated space by allowing a number to occupy only part of * an array so that the arrays do not have to be reallocated as often. * When performing an operation with many iterations the array used to * hold a number is only reallocated when necessary and does not have to * be the same size as the number it represents. A mutable number allows * calculations to occur on the same number without having to create * a new number for every step of the calculation as occurs with * BigIntegers. * * @see     BigInteger * @version 1.9, 01/23/03 * @author  Michael McCloskey * @since   1.3 */class MutableBigInteger {    /**     * Holds the magnitude of this MutableBigInteger in big endian order.     * The magnitude may start at an offset into the value array, and it may     * end before the length of the value array.     */    int[] value;    /**     * The number of ints of the value array that are currently used     * to hold the magnitude of this MutableBigInteger. The magnitude starts     * at an offset and offset + intLen may be less than value.length.     */    int intLen;    /**     * The offset into the value array where the magnitude of this     * MutableBigInteger begins.     */    int offset = 0;    /**     * This mask is used to obtain the value of an int as if it were unsigned.     */    private final static long LONG_MASK = 0xffffffffL;    // Constructors    /**     * The default constructor. An empty MutableBigInteger is created with     * a one word capacity.     */    MutableBigInteger() {        value = new int[1];        intLen = 0;    }    /**     * Construct a new MutableBigInteger with a magnitude specified by     * the int val.     */    MutableBigInteger(int val) {        value = new int[1];        intLen = 1;        value[0] = val;    }    /**     * Construct a new MutableBigInteger with the specified value array     * up to the specified length.     */    MutableBigInteger(int[] val, int len) {        value = val;        intLen = len;    }    /**     * Construct a new MutableBigInteger with the specified value array     * up to the length of the array supplied.     */    MutableBigInteger(int[] val) {        value = val;        intLen = val.length;    }    /**     * Construct a new MutableBigInteger with a magnitude equal to the     * specified BigInteger.     */    MutableBigInteger(BigInteger b) {        value = (int[]) b.mag.clone();        intLen = value.length;    }    /**     * Construct a new MutableBigInteger with a magnitude equal to the     * specified MutableBigInteger.     */    MutableBigInteger(MutableBigInteger val) {        intLen = val.intLen;        value = new int[intLen];        for(int i=0; i<intLen; i++)            value[i] = val.value[val.offset+i];    }    /**     * Clear out a MutableBigInteger for reuse.     */    void clear() {        offset = intLen = 0;        for (int index=0, n=value.length; index < n; index++)            value[index] = 0;    }    /**     * Set a MutableBigInteger to zero, removing its offset.     */    void reset() {        offset = intLen = 0;    }    /**     * Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1     * as this MutableBigInteger is numerically less than, equal to, or     * greater than <tt>b</tt>.      */    final int compare(MutableBigInteger b) {        if (intLen < b.intLen)            return -1;        if (intLen > b.intLen)            return 1;        for (int i=0; i<intLen; i++) {            int b1 = value[offset+i]     + 0x80000000;            int b2 = b.value[b.offset+i] + 0x80000000;            if (b1 < b2)                return -1;            if (b1 > b2)                return 1;        }        return 0;    }    /**     * Return the index of the lowest set bit in this MutableBigInteger. If the     * magnitude of this MutableBigInteger is zero, -1 is returned.     */    private final int getLowestSetBit() {        if (intLen == 0)            return -1;        int j, b;        for (j=intLen-1; (j>0) && (value[j+offset]==0); j--)            ;        b = value[j+offset];        if (b==0)             return -1;        return ((intLen-1-j)<<5) + BigInteger.trailingZeroCnt(b);    }    /**     * Return the int in use in this MutableBigInteger at the specified     * index. This method is not used because it is not inlined on all     * platforms.     */    private final int getInt(int index) {        return value[offset+index];    }    /**     * Return a long which is equal to the unsigned value of the int in     * use in this MutableBigInteger at the specified index. This method is     * not used because it is not inlined on all platforms.     */    private final long getLong(int index) {        return value[offset+index] & LONG_MASK;    }    /**     * Ensure that the MutableBigInteger is in normal form, specifically     * making sure that there are no leading zeros, and that if the     * magnitude is zero, then intLen is zero.     */    final void normalize() {        if (intLen == 0) {            offset = 0;            return;        }        int index = offset;        if (value[index] != 0)            return;        int indexBound = index+intLen;        do {            index++;        } while(index < indexBound && value[index]==0);        int numZeros = index - offset;        intLen -= numZeros;        offset = (intLen==0 ?  0 : offset+numZeros);    }    /**     * If this MutableBigInteger cannot hold len words, increase the size     * of the value array to len words.     */    private final void ensureCapacity(int len) {        if (value.length < len) {            value = new int[len];            offset = 0;            intLen = len;        }    }    /**     * Convert this MutableBigInteger into an int array with no leading     * zeros, of a length that is equal to this MutableBigInteger's intLen.     */    int[] toIntArray() {        int[] result = new int[intLen];        for(int i=0; i<intLen; i++)            result[i] = value[offset+i];        return result;    }    /**     * Sets the int at index+offset in this MutableBigInteger to val.     * This does not get inlined on all platforms so it is not used     * as often as originally intended.     */    void setInt(int index, int val) {        value[offset + index] = val;    }    /**     * Sets this MutableBigInteger's value array to the specified array.     * The intLen is set to the specified length.     */    void setValue(int[] val, int length) {        value = val;        intLen = length;        offset = 0;    }    /**     * Sets this MutableBigInteger's value array to a copy of the specified     * array. The intLen is set to the length of the new array.     */    void copyValue(MutableBigInteger val) {        int len = val.intLen;        if (value.length < len)            value = new int[len];        for(int i=0; i<len; i++)            value[i] = val.value[val.offset+i];        intLen = len;        offset = 0;    }    /**     * Sets this MutableBigInteger's value array to a copy of the specified     * array. The intLen is set to the length of the specified array.     */    void copyValue(int[] val) {        int len = val.length;        if (value.length < len)            value = new int[len];        for(int i=0; i<len; i++)            value[i] = val[i];        intLen = len;        offset = 0;    }    /**     * Returns true iff this MutableBigInteger has a value of one.     */    boolean isOne() {        return (intLen == 1) && (value[offset] == 1);    }    /**     * Returns true iff this MutableBigInteger has a value of zero.     */    boolean isZero() {        return (intLen == 0);    }    /**     * Returns true iff this MutableBigInteger is even.     */    boolean isEven() {        return (intLen == 0) || ((value[offset + intLen - 1] & 1) == 0);    }    /**     * Returns true iff this MutableBigInteger is odd.     */    boolean isOdd() {        return ((value[offset + intLen - 1] & 1) == 1);    }    /**     * Returns true iff this MutableBigInteger is in normal form. A     * MutableBigInteger is in normal form if it has no leading zeros     * after the offset, and intLen + offset <= value.length.     */    boolean isNormal() {        if (intLen + offset > value.length)            return false;        if (intLen ==0)            return true;        return (value[offset] != 0);    }    /**     * Returns a String representation of this MutableBigInteger in radix 10.     */    public String toString() {        BigInteger b = new BigInteger(this, 1);        return b.toString();    }    /**     * Right shift this MutableBigInteger n bits. The MutableBigInteger is left     * in normal form.     */    void rightShift(int n) {        if (intLen == 0)            return;        int nInts = n >>> 5;        int nBits = n & 0x1F;        this.intLen -= nInts;        if (nBits == 0)            return;        int bitsInHighWord = BigInteger.bitLen(value[offset]);        if (nBits >= bitsInHighWord) {            this.primitiveLeftShift(32 - nBits);            this.intLen--;        } else {            primitiveRightShift(nBits);        }    }    /**     * Left shift this MutableBigInteger n bits.      */    void leftShift(int n) {        /*         * If there is enough storage space in this MutableBigInteger already         * the available space will be used. Space to the right of the used         * ints in the value array is faster to utilize, so the extra space         * will be taken from the right if possible.         */        if (intLen == 0)           return;        int nInts = n >>> 5;        int nBits = n&0x1F;        int bitsInHighWord = BigInteger.bitLen(value[offset]);                // If shift can be done without moving words, do so        if (n <= (32-bitsInHighWord)) {            primitiveLeftShift(nBits);            return;        }        int newLen = intLen + nInts +1;        if (nBits <= (32-bitsInHighWord))            newLen--;        if (value.length < newLen) {            // The array must grow            int[] result = new int[newLen];            for (int i=0; i<intLen; i++)                result[i] = value[offset+i];            setValue(result, newLen);        } else if (value.length - offset >= newLen) {            // Use space on right            for(int i=0; i<newLen - intLen; i++)                value[offset+intLen+i] = 0;        } else {            // Must use space on left            for (int i=0; i<intLen; i++)                value[i] = value[offset+i];            for (int i=intLen; i<newLen; i++)                value[i] = 0;            offset = 0;        }        intLen = newLen;        if (nBits == 0)            return;        if (nBits <= (32-bitsInHighWord))            primitiveLeftShift(nBits);        else            primitiveRightShift(32 -nBits);    }    /**     * A primitive used for division. This method adds in one multiple of the     * divisor a back to the dividend result at a specified offset. It is used     * when qhat was estimated too large, and must be adjusted.     */    private int divadd(int[] a, int[] result, int offset) {        long carry = 0;        for (int j=a.length-1; j >= 0; j--) {            long sum = (a[j] & LONG_MASK) +                        (result[j+offset] & LONG_MASK) + carry;            result[j+offset] = (int)sum;            carry = sum >>> 32;        }        return (int)carry;    }    /**     * This method is used for division. It multiplies an n word input a by one     * word input x, and subtracts the n word product from q. This is needed     * when subtracting qhat*divisor from dividend.     */    private int mulsub(int[] q, int[] a, int x, int len, int offset) {        long xLong = x & LONG_MASK;        long carry = 0;        offset += len;        for (int j=len-1; j >= 0; j--) {            long product = (a[j] & LONG_MASK) * xLong + carry;            long difference = q[offset] - product;            q[offset--] = (int)difference;            carry = (product >>> 32)                     + (((difference & LONG_MASK) >                         (((~(int)product) & LONG_MASK))) ? 1:0);        }        return (int)carry;    }    /**     * Right shift this MutableBigInteger n bits, where n is     * less than 32.     * Assumes that intLen > 0, n > 0 for speed     */    private final void primitiveRightShift(int n) {        int[] val = value;        int n2 = 32 - n;        for (int i=offset+intLen-1, c=val[i]; i>offset; i--) {            int b = c;            c = val[i-1];