biginteger.java

这是linux下ssl vpn的实现程序

  private static int[] trustedStripLeadingZeroInts(int val[]) {
    int byteLength = val.length;
    int keep;

    // Find first nonzero byte
    for (keep = 0; keep < val.length && val[keep] == 0; keep++) {
      ;
    }

    // Only perform copy if necessary
    if (keep > 0) {
      int result[] = new int[val.length - keep];
      for (int i = 0; i < val.length - keep; i++) {
        result[i] = val[keep + i];
      }
      return result;
    }
    return val;
  }

  private int signInt() {
    return (int) (signum < 0 ? -1 : 0);
  }

  private static BigInteger valueOf(int val[]) {
    return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
  }

  private BigInteger(int[] magnitude, int signum) {
    this.signum = (magnitude.length == 0 ? 0 : signum);
    this.mag = magnitude;
  }

  private int firstNonzeroIntNum() {
    /*
     * Initialize firstNonzeroIntNum 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 (firstNonzeroIntNum == -2) {
      // Search for the first nonzero int
      int i;
      for (i = mag.length - 1; i >= 0 && mag[i] == 0; i--) {
        ;
      }
      firstNonzeroIntNum = mag.length - i - 1;
    }
    return firstNonzeroIntNum;
  }

  private int intLength() {
    return bitLength() / 32 + 1;
  }

  private int getInt(int n) {
    if (n < 0) {
      return 0;
    }
    if (n >= mag.length) {
      return signInt();
    }

    int magInt = mag[mag.length - n - 1];

    return (int) (signum >= 0 ? magInt :
                  (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
  }

  public BigInteger remainder(
      BigInteger val) throws ArithmeticException {
    if (val.signum == 0) {
      throw new ArithmeticException("BigInteger: Divide by zero");
    }

    if (signum == 0) {
      return BigInteger.ZERO;
    }

    int[] res = new int[this.mag.length];

    System.arraycopy(this.mag, 0, res, 0, res.length);

    return new BigInteger(signum, remainder(res, val.mag));
  }

  /**
   * do a left shift - this returns a new array.
   */
  private int[] shiftLeft(
      int[] mag,
      int n) {
    int nInts = n >>> 5;
    int nBits = n & 0x1f;
    int magLen = mag.length;
    int newMag[] = null;

    if (nBits == 0) {
      newMag = new int[magLen + nInts];
      for (int i = 0; i < magLen; i++) {
        newMag[i] = mag[i];
      }
    }
    else {
      int i = 0;
      int nBits2 = 32 - nBits;
      int highBits = mag[0] >>> nBits2;

      if (highBits != 0) {
        newMag = new int[magLen + nInts + 1];
        newMag[i++] = highBits;
      }
      else {
        newMag = new int[magLen + nInts];
      }

      int m = mag[0];
      for (int j = 0; j < magLen - 1; j++) {
        int next = mag[j + 1];

        newMag[i++] = (m << nBits) | (next >>> nBits2);
        m = next;
      }

      newMag[i] = mag[magLen - 1] << nBits;
    }

    return newMag;
  }

  public BigInteger shiftLeft(
      int n) {
    if (signum == 0 || mag.length == 0) {
      return ZERO;
    }
    if (n == 0) {
      return this;
    }

    if (n < 0) {
      return shiftRight( -n);
    }

    return new BigInteger(signum, shiftLeft(mag, n));
  }

  /**
   * do a right shift - this does it in place.
   */
  private int[] shiftRight(
      int start,
      int[] mag,
      int n) {
    int nInts = (n >>> 5) + start;
    int nBits = n & 0x1f;
    int magLen = mag.length;

    if (nInts != start) {
      int delta = (nInts - start);

      for (int i = magLen - 1; i >= nInts; i--) {
        mag[i] = mag[i - delta];
      }
      for (int i = nInts - 1; i >= start; i--) {
        mag[i] = 0;
      }
    }

    if (nBits != 0) {
      int nBits2 = 32 - nBits;
      int m = mag[magLen - 1];

      for (int i = magLen - 1; i >= nInts + 1; i--) {
        int next = mag[i - 1];

        mag[i] = (m >>> nBits) | (next << nBits2);
        m = next;
      }

      mag[nInts] >>>= nBits;
    }

    return mag;
  }

  /**
   * do a right shift by one - this does it in place.
   */
  private int[] shiftRightOne(
      int start,
      int[] mag) {
    int magLen = mag.length;

    int m = mag[magLen - 1];

    for (int i = magLen - 1; i >= start + 1; i--) {
      int next = mag[i - 1];

      mag[i] = (m >>> 1) | (next << 31);
      m = next;
    }

    mag[start] >>>= 1;

    return mag;
  }

  public BigInteger shiftRight(
      int n) {
    if (n == 0) {
      return this;
    }

    if (n < 0) {
      return shiftLeft( -n);
    }

    if (n >= bitLength()) {
      return (this.signum < 0 ? valueOf( -1) : BigInteger.ZERO);
    }

    int[] res = new int[this.mag.length];

    System.arraycopy(this.mag, 0, res, 0, res.length);

    return new BigInteger(this.signum, shiftRight(0, res, n));
  }

  public int signum() {
    return signum;
  }

  /**
   * returns x = x - y - we assume x is >= y
   */
  private int[] subtract(
      int xStart,
      int[] x,
      int yStart,
      int[] y) {
    int iT = x.length - 1;
    int iV = y.length - 1;
    long m;
    int borrow = 0;

    do {
      m = ( ( (long) x[iT]) & IMASK) - ( ( (long) y[iV--]) & IMASK) + borrow;

      x[iT--] = (int) m;

      if (m < 0) {
        borrow = -1;
      }
      else {
        borrow = 0;
      }
    }
    while (iV >= yStart);

    while (iT >= xStart) {
      m = ( ( (long) x[iT]) & IMASK) + borrow;
      x[iT--] = (int) m;

      if (m < 0) {
        borrow = -1;
      }
      else {
        break;
      }
    }

    return x;
  }

  public BigInteger subtract(
      BigInteger val) {
    if (val.signum == 0 || val.mag.length == 0) {
      return this;
    }
    if (signum == 0 || mag.length == 0) {
      return val.negate();
    }
    if (val.signum < 0) {
      if (this.signum > 0) {
        return this.add(val.negate());
      }
    }
    else {
      if (this.signum < 0) {
        return this.add(val.negate());
      }
    }

    BigInteger bigun, littlun;
    int compare = compareTo(val);
    if (compare == 0) {
      return ZERO;
    }

    if (compare < 0) {
      bigun = val;
      littlun = this;
    }
    else {
      bigun = this;
      littlun = val;
    }

    int res[] = new int[bigun.mag.length];

    System.arraycopy(bigun.mag, 0, res, 0, res.length);

    return new BigInteger(this.signum * compare,
                          subtract(0, res, 0, littlun.mag));
  }

  public byte[] toByteArray() {
    int bitLength = bitLength();
    byte[] bytes = new byte[bitLength / 8 + 1];

    int bytesCopied = 4;
    int mag = 0;
    int ofs = this.mag.length - 1;
    int carry = 1;
    long lMag;
    for (int i = bytes.length - 1; i >= 0; i--) {
      if (bytesCopied == 4 && ofs >= 0) {
        if (signum < 0) {
          // we are dealing with a +ve number and we want a -ve one, so
          // invert the magnitude ints and add 1 (propagating the carry)
          // to make a 2's complement -ve number
          lMag = ~this.mag[ofs--] & IMASK;
          lMag += carry;
          if ( (lMag & ~IMASK) != 0) {
            carry = 1;
          }
          else {
            carry = 0;
          }
          mag = (int) (lMag & IMASK);
        }
        else {
          mag = this.mag[ofs--];
        }
        bytesCopied = 1;
      }
      else {
        mag >>>= 8;
        bytesCopied++;
      }

      bytes[i] = (byte) mag;
    }

    return bytes;
  }

  public String toString() {
    return toString(10);
  }

  public String toString(int rdx) {
    if (mag == null) {
      return "null";
    }
    else if (signum == 0) {
      return "0";
    }

    String s = new String();
    String h;

    if (rdx == 16) {
      for (int i = 0; i < mag.length; i++) {
        h = "0000000" + Integer.toHexString(mag[i]);
        h = h.substring(h.length() - 8);
        s = s + h;
      }
    }
    else {
      // This is algorithm 1a from chapter 4.4 in Seminumerical Algorithms, slow but it works
      Stack S = new Stack();
      BigInteger base = new BigInteger(Integer.toString(rdx, rdx), rdx);
      // The sign is handled separatly.
      // Notice however that for this to work, radix 16 _MUST_ be a special case,
      // unless we want to enter a recursion well. In their infinite wisdom, why did not
      // the Sun engineers made a c'tor for BigIntegers taking a BigInteger as parameter?
      // (Answer: Becuase Sun's BigIntger is clonable, something bouncycastle's isn't.)
      BigInteger u = new BigInteger(this.abs().toString(16), 16);
      BigInteger b;

      // For speed, maye these test should look directly a u.magnitude.length?
      while (!u.equals(BigInteger.ZERO)) {
        b = u.mod(base);
        if (b.equals(BigInteger.ZERO)) {
          S.push("0");
        }
        else {
          S.push(Integer.toString(b.mag[0], rdx));
        }
        u = u.divide(base);
      }
      // Then pop the stack
      while (!S.empty()) {
        s = s + S.pop();
      }
    }
    // Strip leading zeros.
    while (s.length() > 1 && s.charAt(0) == '0') {
      s = s.substring(1);

    }
    if (s.length() == 0) {
      s = "0";
    }
    else if (signum == -1) {
      s = "-" + s;

    }
    return s;
  }

  public static final BigInteger ZERO = new BigInteger(0, new byte[0]);
  public static final BigInteger ONE = valueOf(1);
  private static final BigInteger TWO = valueOf(2);

  public static BigInteger valueOf(
      long val) {
    if (val == 0) {
      return BigInteger.ZERO;
    }

    // store val into a byte array
    byte[] b = new byte[8];
    for (int i = 0; i < 8; i++) {
      b[7 - i] = (byte) val;
      val >>= 8;
    }

    return new BigInteger(b);
  }

  private int max(int a, int b) {
    if (a < b) {
      return b;
    }
    return a;
  }

  public int getLowestSetBit() {
    if (this.equals(ZERO)) {
      return -1;
    }

    int w = mag.length - 1;

    while (w >= 0) {
      if (mag[w] != 0) {
        break;
      }

      w--;
    }

    int b = 31;

    while (b > 0) {
      if ( (mag[w] << b) == 0x80000000) {
        break;
      }

      b--;
    }

    return ( ( (mag.length - 1) - w) * 32 + (31 - b));
  }

  public boolean testBit(
      int n) throws ArithmeticException {
    if (n < 0) {
      throw new ArithmeticException("Bit position must not be negative");
    }

    if ( (n / 32) >= mag.length) {
      return signum < 0;
    }

    return ( (mag[ (mag.length - 1) - n / 32] >> (n % 32)) & 1) > 0;
  }
}