mpn.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 769 行 · 第 1/2 页

	else
	  return 10;
      }
    else if (radix < 12)
      return 9;
    else if (radix <= 16)
      return 8;
    else if (radix <= 23)
      return 7;
    else if (radix <= 40)
      return 6;
    // The following are conservative, but we don't care.
    else if (radix <= 256)
      return 4;
    else
      return 1;
  }

  /** Count the number of leading zero bits in an int. */
  public static int count_leading_zeros (int i)
  {
    if (i == 0)
      return 32;
    int count = 0;
    for (int k = 16;  k > 0;  k = k >> 1) {
      int j = i >>> k;
      if (j == 0)
	count += k;
      else
	i = j;
    }
    return count;
  }

  public static int set_str (int dest[], byte[] str, int str_len, int base)
  {
    int size = 0;
    if ((base & (base - 1)) == 0)
      {
	// The base is a power of 2.  Read the input string from
	// least to most significant character/digit.  */

	int next_bitpos = 0;
	int bits_per_indigit = 0;
	for (int i = base; (i >>= 1) != 0; ) bits_per_indigit++;
	int res_digit = 0;

	for (int i = str_len;  --i >= 0; )
	  {
	    int inp_digit = str[i];
	    res_digit |= inp_digit << next_bitpos;
	    next_bitpos += bits_per_indigit;
	    if (next_bitpos >= 32)
	      {
		dest[size++] = res_digit;
		next_bitpos -= 32;
		res_digit = inp_digit >> (bits_per_indigit - next_bitpos);
	      }
	  }

	if (res_digit != 0)
	  dest[size++] = res_digit;
      }
    else
      {
	// General case.  The base is not a power of 2.
	int indigits_per_limb = MPN.chars_per_word (base);
	int str_pos = 0;

	while (str_pos < str_len)
	  {
	    int chunk = str_len - str_pos;
	    if (chunk > indigits_per_limb)
	      chunk = indigits_per_limb;
	    int res_digit = str[str_pos++];
	    int big_base = base;

	    while (--chunk > 0)
	      {
		res_digit = res_digit * base + str[str_pos++];
		big_base *= base;
	      }

	    int cy_limb;
	    if (size == 0)
	      cy_limb = res_digit;
	    else
	      {
		cy_limb = MPN.mul_1 (dest, dest, size, big_base);
		cy_limb += MPN.add_1 (dest, dest, size, res_digit);
	      }
	    if (cy_limb != 0)
	      dest[size++] = cy_limb;
	  }
       }
    return size;
  }

  /** Compare x[0:size-1] with y[0:size-1], treating them as unsigned integers.
   * @result -1, 0, or 1 depending on if x<y, x==y, or x>y.
   * This is basically the same as gmp's mpn_cmp function.
   */
  public static int cmp (int[] x, int[] y, int size)
  {
    while (--size >= 0)
      {
	int x_word = x[size];
	int y_word = y[size];
	if (x_word != y_word)
	  {
	    // Invert the high-order bit, because:
	    // (unsigned) X > (unsigned) Y iff
	    // (int) (X^0x80000000) > (int) (Y^0x80000000).
	    return (x_word ^ 0x80000000) > (y_word ^0x80000000) ? 1 : -1;
	  }
      }
    return 0;
  }

  /** Compare x[0:xlen-1] with y[0:ylen-1], treating them as unsigned integers.
   * @result -1, 0, or 1 depending on if x<y, x==y, or x>y.
   */
  public static int cmp (int[] x, int xlen, int[] y, int ylen)
  {
    return xlen > ylen ? 1 : xlen < ylen ? -1 : cmp (x, y, xlen);
  }

  /* Shift x[x_start:x_start+len-1] count bits to the "right"
   * (i.e. divide by 2**count).
   * Store the len least significant words of the result at dest.
   * The bits shifted out to the right are returned.
   * OK if dest==x.
   * Assumes: 0 < count < 32
   */

  public static int rshift (int[] dest, int[] x, int x_start,
			    int len, int count)
  {
    int count_2 = 32 - count;
    int low_word = x[x_start];
    int retval = low_word << count_2;
    int i = 1;
    for (; i < len;  i++)
      {
	int high_word = x[x_start+i];
	dest[i-1] = (low_word >>> count) | (high_word << count_2);
	low_word = high_word;
      }
    dest[i-1] = low_word >>> count;
    return retval;
  }

  /* Shift x[x_start:x_start+len-1] count bits to the "right"
   * (i.e. divide by 2**count).
   * Store the len least significant words of the result at dest.
   * OK if dest==x.
   * Assumes: 0 <= count < 32
   * Same as rshift, but handles count==0 (and has no return value).
   */
  public static void rshift0 (int[] dest, int[] x, int x_start,
			      int len, int count)
  {
    if (count > 0)
      rshift(dest, x, x_start, len, count);
    else
      for (int i = 0;  i < len;  i++)
	dest[i] = x[i + x_start];
  }

  /** Return the long-truncated value of right shifting.
  * @param x a two's-complement "bignum"
  * @param len the number of significant words in x
  * @param count the shift count
  * @return (long)(x[0..len-1] >> count).
  */
  public static long rshift_long (int[] x, int len, int count)
  {
    int wordno = count >> 5;
    count &= 31;
    int sign = x[len-1] < 0 ? -1 : 0;
    int w0 = wordno >= len ? sign : x[wordno];
    wordno++;
    int w1 = wordno >= len ? sign : x[wordno];
    if (count != 0)
      {
	wordno++;
	int w2 = wordno >= len ? sign : x[wordno];
	w0 = (w0 >>> count) | (w1 << (32-count));
	w1 = (w1 >>> count) | (w2 << (32-count));
      }
    return ((long)w1 << 32) | ((long)w0 & 0xffffffffL);
  }

  /* Shift x[0:len-1] left by count bits, and store the len least
   * significant words of the result in dest[d_offset:d_offset+len-1].
   * Return the bits shifted out from the most significant digit.
   * Assumes 0 < count < 32.
   * OK if dest==x.
   */

  public static int lshift (int[] dest, int d_offset,
			    int[] x, int len, int count)
  {
    int count_2 = 32 - count;
    int i = len - 1;
    int high_word = x[i];
    int retval = high_word >>> count_2;
    d_offset++;
    while (--i >= 0)
      {
	int low_word = x[i];
	dest[d_offset+i] = (high_word << count) | (low_word >>> count_2);
	high_word = low_word;
      }
    dest[d_offset+i] = high_word << count;
    return retval;
  }

  /** Return least i such that word&(1<<i). Assumes word!=0. */

  public static int findLowestBit (int word)
  {
    int i = 0;
    while ((word & 0xF) == 0)
      {
	word >>= 4;
	i += 4;
      }
    if ((word & 3) == 0)
      {
	word >>= 2;
	i += 2;
      }
    if ((word & 1) == 0)
      i += 1;
    return i;
  }

  /** Return least i such that words & (1<<i). Assumes there is such an i. */

  public static int findLowestBit (int[] words)
  {
    for (int i = 0;  ; i++)
      {
	if (words[i] != 0)
	  return 32 * i + findLowestBit (words[i]);
      }
  }

  /** Calculate Greatest Common Divisior of x[0:len-1] and y[0:len-1].
    * Assumes both arguments are non-zero.
    * Leaves result in x, and returns len of result.
    * Also destroys y (actually sets it to a copy of the result). */

  public static int gcd (int[] x, int[] y, int len)
  {
    int i, word;
    // Find sh such that both x and y are divisible by 2**sh.
    for (i = 0; ; i++)
      {
	word = x[i] | y[i];
	if (word != 0)
	  {
	    // Must terminate, since x and y are non-zero.
	    break;
	  }
      }
    int initShiftWords = i;
    int initShiftBits = findLowestBit (word);
    // Logically: sh = initShiftWords * 32 + initShiftBits

    // Temporarily devide both x and y by 2**sh.
    len -= initShiftWords;
    MPN.rshift0 (x, x, initShiftWords, len, initShiftBits);
    MPN.rshift0 (y, y, initShiftWords, len, initShiftBits);

    int[] odd_arg; /* One of x or y which is odd. */
    int[] other_arg; /* The other one can be even or odd. */
    if ((x[0] & 1) != 0)
      {
	odd_arg = x;
	other_arg = y;
      }
    else
      {
	odd_arg = y;
	other_arg = x;
      }

    for (;;)
      {
	// Shift other_arg until it is odd; this doesn't
	// affect the gcd, since we divide by 2**k, which does not
	// divide odd_arg.
	for (i = 0; other_arg[i] == 0; ) i++;
	if (i > 0)
	  {
	    int j;
	    for (j = 0; j < len-i; j++)
		other_arg[j] = other_arg[j+i];
	    for ( ; j < len; j++)
	      other_arg[j] = 0;
	  }
	i = findLowestBit(other_arg[0]);
	if (i > 0)
	  MPN.rshift (other_arg, other_arg, 0, len, i);

	// Now both odd_arg and other_arg are odd.

	// Subtract the smaller from the larger.
	// This does not change the result, since gcd(a-b,b)==gcd(a,b).
	i = MPN.cmp(odd_arg, other_arg, len);
	if (i == 0)
	    break;
	if (i > 0)
	  { // odd_arg > other_arg
	    MPN.sub_n (odd_arg, odd_arg, other_arg, len);
	    // Now odd_arg is even, so swap with other_arg;
	    int[] tmp = odd_arg; odd_arg = other_arg; other_arg = tmp;
	  }
	else
	  { // other_arg > odd_arg
	    MPN.sub_n (other_arg, other_arg, odd_arg, len);
	}
	while (odd_arg[len-1] == 0 && other_arg[len-1] == 0)
	  len--;
    }
    if (initShiftWords + initShiftBits > 0)
      {
	if (initShiftBits > 0)
	  {
	    int sh_out = MPN.lshift (x, initShiftWords, x, len, initShiftBits);
	    if (sh_out != 0)
	      x[(len++)+initShiftWords] = sh_out;
	  }
	else
	  {
	    for (i = len; --i >= 0;)
	      x[i+initShiftWords] = x[i];
	  }
	for (i = initShiftWords;  --i >= 0; )
	  x[i] = 0;
	len += initShiftWords;
      }
    return len;
  }

  public static int intLength (int i)
  {
    return 32 - count_leading_zeros (i < 0 ? ~i : i);
  }

  /** Calcaulte the Common Lisp "integer-length" function.
   * Assumes input is canonicalized:  len==BigInteger.wordsNeeded(words,len) */
  public static int intLength (int[] words, int len)
  {
    len--;
    return intLength (words[len]) + 32 * len;
  }

  /* DEBUGGING:
  public static void dprint (BigInteger x)
  {
    if (x.words == null)
      System.err.print(Long.toString((long) x.ival & 0xffffffffL, 16));
    else
      dprint (System.err, x.words, x.ival);
  }
  public static void dprint (int[] x) { dprint (System.err, x, x.length); }
  public static void dprint (int[] x, int len) { dprint (System.err, x, len); }
  public static void dprint (java.io.PrintStream ps, int[] x, int len)
  {
    ps.print('(');
    for (int i = 0;  i < len; i++)
      {
	if (i > 0)
	  ps.print (' ');
	ps.print ("#x" + Long.toString ((long) x[i] & 0xffffffffL, 16));
      }
    ps.print(')');
  }
  */
}