biginteger.java

进行与数字证书相关开发必须的java源码

// Decompiled by Jad v1.5.7g. Copyright 2000 Pavel Kouznetsov.
// Jad home page: http://www.geocities.com/SiliconValley/Bridge/8617/jad.html
// Decompiler options: packimports(3) fieldsfirst ansi 
// Source File Name:   BigInteger.java

package jit.math;

import java.util.Random;
import java.util.Stack;
import jit.security.SecureRandom;

public class BigInteger
{

    private int sign;
    private int magnitude[];
    private int nBits;
    private int nBitLength;
    private static final long IMASK = 0xffffffffL;
    private long mQuote;
    private static final int BITS_PER_BYTE = 8;
    private static final int BYTES_PER_INT = 4;
    private static final byte rndMask[] = {
        -1, 127, 63, 31, 15, 7, 3, 1
    };
    private static final 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 static final 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 static final BigInteger ZERO = new BigInteger(0, new byte[0]);
    public static final BigInteger ONE = valueOf(1L);
    private static final BigInteger TWO = valueOf(2L);

    private BigInteger()
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
    }

    private BigInteger(int nWords)
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
        sign = 1;
        magnitude = new int[nWords];
    }

    private BigInteger(int signum, int mag[])
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
        sign = signum;
        if(mag.length > 0)
        {
            int i;
            for(i = 0; i < mag.length && mag[i] == 0; i++);
            if(i == 0)
            {
                magnitude = mag;
            } else
            {
                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
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
        if(sval.length() == 0)
            throw new NumberFormatException("Zero length BigInteger");
        if(rdx < 2 || rdx > 36)
            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;
        }
        for(; index < sval.length() && Character.digit(sval.charAt(index), rdx) == 0; index++);
        if(index >= sval.length())
        {
            sign = 0;
            magnitude = new int[0];
            return;
        }
        BigInteger b = ZERO;
        BigInteger r = valueOf(rdx);
        for(; index < sval.length(); index++)
            b = b.multiply(r).add(valueOf(Character.digit(sval.charAt(index), rdx)));

        magnitude = b.magnitude;
    }

    public BigInteger(byte bval[])
        throws NumberFormatException
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
        if(bval.length == 0)
            throw new NumberFormatException("Zero length BigInteger");
        sign = 1;
        if(bval[0] < 0)
        {
            sign = -1;
            int iBval;
            for(iBval = 0; iBval < bval.length && bval[iBval] == -1; iBval++);
            magnitude = new int[(bval.length - iBval) / 2 + 1];
        } else
        {
            magnitude = makeMagnitude(bval);
        }
    }

    private int[] makeMagnitude(byte bval[])
    {
        int firstSignificant;
        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;
        int mag[] = new int[nInts];
        int v = 0;
        int magnitudeIndex = 0;
        for(int i = firstSignificant; i < bval.length; i++)
        {
            v <<= 8;
            v |= bval[i] & 0xff;
            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
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
        if(sign < -1 || sign > 1)
            throw new NumberFormatException("Invalid sign value");
        if(sign == 0)
        {
            this.sign = 0;
            magnitude = new int[0];
            return;
        } else
        {
            magnitude = makeMagnitude(mag);
            this.sign = sign;
            return;
        }
    }

    public BigInteger(int numBits, Random rnd)
        throws IllegalArgumentException
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
        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);
            b[0] &= rndMask[8 * nBytes - numBits];
        }
        magnitude = makeMagnitude(b);
        sign = 1;
        nBits = -1;
        nBitLength = -1;
    }

    private void nextRndBytes(Random rnd, byte bytes[])
    {
        int numRequested = bytes.length;
        int numGot = 0;
        int r = 0;
        if(rnd instanceof SecureRandom)
            ((SecureRandom)rnd).nextBytes(bytes);
        else
            do
            {
                int i = 0;
                while(i < 4) 
                {
                    if(numGot == numRequested)
                        return;
                    r = i != 0 ? r >> 8 : rnd.nextInt();
                    bytes[numGot++] = (byte)r;
                    i++;
                }
            } while(true);
    }

    public BigInteger(int bitLength, int certainty, Random rnd)
        throws ArithmeticException
    {
        nBits = -1;
        nBitLength = -1;
        mQuote = -1L;
        int nBytes = (bitLength + 7) / 8;
        byte b[] = new byte[nBytes];
        do
        {
            if(nBytes > 0)
            {
                nextRndBytes(rnd, b);
                b[0] &= rndMask[8 * nBytes - bitLength];
            }
            magnitude = makeMagnitude(b);
            sign = 1;
            nBits = -1;
            nBitLength = -1;
            mQuote = -1L;
            if(certainty > 0 && bitLength > 2)
                magnitude[magnitude.length - 1] |= 0x1;
        } while(bitLength() != bitLength || !isProbablePrime(certainty));
    }

    public BigInteger abs()
    {
        return sign < 0 ? negate() : this;
    }

    private int[] add(int a[], int b[])
    {
        int tI = a.length - 1;
        int vI = b.length - 1;
        long m;
        for(m = 0L; vI >= 0; m >>>= 32)
        {
            m += ((long)a[tI] & 0xffffffffL) + ((long)b[vI--] & 0xffffffffL);
            a[tI--] = (int)m;
        }

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

        return a;
    }

    public BigInteger add(BigInteger val)
        throws ArithmeticException
    {
        if(val.sign == 0 || val.magnitude.length == 0)
            return this;
        if(sign == 0 || magnitude.length == 0)
            return val;
        if(val.sign < 0)
        {
            if(sign > 0)
                return subtract(val.negate());
        } else
        if(sign < 0)
            return val.subtract(negate());
        int mag[];
        int op[];
        if(magnitude.length < val.magnitude.length)
        {
            mag = new int[val.magnitude.length + 1];
            System.arraycopy(val.magnitude, 0, mag, 1, val.magnitude.length);
            op = magnitude;
        } else
        {
            mag = new int[magnitude.length + 1];
            System.arraycopy(magnitude, 0, mag, 1, magnitude.length);
            op = val.magnitude;
        }
        return new BigInteger(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 int bitLength(int indx, int mag[])
    {
        if(mag.length == 0)
            return 0;
        for(; indx != mag.length && mag[indx] == 0; indx++);
        if(indx == mag.length)
            return 0;
        int bitLength = 32 * (mag.length - indx - 1);
        bitLength += bitLen(mag[indx]);
        if(sign < 0)
        {
            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;
    }

    static int bitLen(int w)
    {
        return w >= 32768 ? w >= 0x800000 ? w >= 0x8000000 ? w >= 0x20000000 ? w >= 0x40000000 ? 31 : 30 : w >= 0x10000000 ? 29 : 28 : w >= 0x2000000 ? w >= 0x4000000 ? 27 : 26 : w >= 0x1000000 ? 25 : 24 : w >= 0x80000 ? w >= 0x200000 ? w >= 0x400000 ? 23 : 22 : w >= 0x100000 ? 21 : 20 : w >= 0x20000 ? w >= 0x40000 ? 19 : 18 : w >= 0x10000 ? 17 : 16 : w >= 128 ? w >= 2048 ? w >= 8192 ? w >= 16384 ? 15 : 14 : w >= 4096 ? 13 : 12 : w >= 512 ? w >= 1024 ? 11 : 10 : w >= 256 ? 9 : 8 : w >= 8 ? w >= 32 ? w >= 64 ? 7 : 6 : w >= 16 ? 5 : 4 : w >= 2 ? w >= 4 ? 3 : 2 : w >= 1 ? 1 : w >= 0 ? 0 : 32;
    }

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

    private int compareTo(int xIndx, int x[], int yIndx, int y[])
    {
        for(; xIndx != x.length && x[xIndx] == 0; xIndx++);
        for(; 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;
        while(xIndx < x.length) 
        {
            long v1 = (long)x[xIndx++] & 0xffffffffL;
            long v2 = (long)y[yIndx++] & 0xffffffffL;
            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;
        else
            return compareTo(0, magnitude, 0, val.magnitude);
    }

    private int[] divide(int x[], int y[])
    {
        int xyCmp = compareTo(0, x, 0, y);
        int count[];