index : riscv-gnu-toolchain/gcc.git	devel/analyzer devel/autopar_devel devel/autopar_europar_2021 devel/bypass-asm devel/c++-contracts devel/c++-coroutines devel/c++-modules devel/c++-name-lookup devel/coarray_native devel/existing-fp8 devel/fortran_unsigned devel/gccgo devel/gfortran-caf devel/gfortran-test devel/gimple-linterchange devel/gomp-5_0-branch devel/icpp2021 devel/ira-select devel/ix86/evex512 devel/jlaw/crc devel/jlaw/pr124029 devel/jlaw/pr80770 devel/loop-unswitch-support-switches devel/lto-offload devel/m2link devel/modula-2 devel/mold-lto-plugin devel/mold-lto-plugin-v2 devel/nothrow-detection devel/omp/gcc-10 devel/omp/gcc-11 devel/omp/gcc-12 devel/omp/gcc-13 devel/omp/gcc-14 devel/omp/gcc-15 devel/omp/gcc-9 devel/omp/ompd devel/power-ieee128 devel/range-gen3 devel/ranger devel/rust/master devel/sh-lra devel/sphinx devel/ssa-range devel/subreg-coalesce devel/unified-autovect master releases/egcs-1.0 releases/egcs-1.1 releases/gcc-10 releases/gcc-11 releases/gcc-12 releases/gcc-13 releases/gcc-14 releases/gcc-15 releases/gcc-2.95 releases/gcc-2.95.2.1-branch releases/gcc-3.0 releases/gcc-3.1 releases/gcc-3.2 releases/gcc-3.3 releases/gcc-3.4 releases/gcc-4.0 releases/gcc-4.1 releases/gcc-4.2 releases/gcc-4.3 releases/gcc-4.4 releases/gcc-4.5 releases/gcc-4.6 releases/gcc-4.7 releases/gcc-4.8 releases/gcc-4.9 releases/gcc-5 releases/gcc-6 releases/gcc-7 releases/gcc-8 releases/gcc-9 releases/libgcj-2.95 trunk
	Unnamed repository; edit this file 'description' to name the repository.	root

aboutsummaryrefslogtreecommitdiff

log msg author committer range

path: root/libjava/classpath/java/math/BigInteger.java

blob: c897d8bf48dd9d0610cbecacec899864da3dc146 (plain)

* Given a @a speed setting, use the interface @c speed_div callback to * adjust the setting. * @param speed The speed setting to convert back to readable KHz. * @returns ERROR_OK if the interface has not been initialized or on success; * otherwise, the error code produced by the @c speed_div callback. */ int jtag_get_speed_readable(int *speed); /** Attempt to configure the interface for the specified KHz. */ int jtag_config_khz(unsigned khz); /** * Attempt to enable RTCK/RCLK. If that fails, fallback to the * specified frequency. */ int jtag_config_rclk(unsigned fallback_speed_khz); /** Retreives the clock speed of the JTAG interface in KHz. */ unsigned jtag_get_speed_khz(void); enum reset_types { RESET_NONE = 0x0, RESET_HAS_TRST = 0x1, RESET_HAS_SRST = 0x2, RESET_TRST_AND_SRST = 0x3, RESET_SRST_PULLS_TRST = 0x4, RESET_TRST_PULLS_SRST = 0x8, RESET_TRST_OPEN_DRAIN = 0x10, RESET_SRST_PUSH_PULL = 0x20, RESET_SRST_NO_GATING = 0x40, RESET_CNCT_UNDER_SRST = 0x80 }; enum reset_types jtag_get_reset_config(void); void jtag_set_reset_config(enum reset_types type); void jtag_set_nsrst_delay(unsigned delay); unsigned jtag_get_nsrst_delay(void); void jtag_set_ntrst_delay(unsigned delay); unsigned jtag_get_ntrst_delay(void); void jtag_set_nsrst_assert_width(unsigned delay); unsigned jtag_get_nsrst_assert_width(void); void jtag_set_ntrst_assert_width(unsigned delay); unsigned jtag_get_ntrst_assert_width(void); /** @returns The current state of TRST. */ int jtag_get_trst(void); /** @returns The current state of SRST. */ int jtag_get_srst(void); /** Enable or disable data scan verification checking. */ void jtag_set_verify(bool enable); /** @returns True if data scan verification will be performed. */ bool jtag_will_verify(void); /** Enable or disable verification of IR scan checking. */ void jtag_set_verify_capture_ir(bool enable); /** @returns True if IR scan verification will be performed. */ bool jtag_will_verify_capture_ir(void); /** Initialize debug adapter upon startup. */ int adapter_init(struct command_context *cmd_ctx); /** Shutdown the debug adapter upon program exit. */ int adapter_quit(void); /** Set ms to sleep after jtag_execute_queue() flushes queue. Debug purposes. */ void jtag_set_flush_queue_sleep(int ms); /** * Initialize JTAG chain using only a RESET reset. If init fails, * try reset + init. */ int jtag_init(struct command_context *cmd_ctx); /** reset, then initialize JTAG chain */ int jtag_init_reset(struct command_context *cmd_ctx); int jtag_register_commands(struct command_context *cmd_ctx); int jtag_init_inner(struct command_context *cmd_ctx); /** * @file * The JTAG interface can be implemented with a software or hardware fifo. * * TAP_DRSHIFT and TAP_IRSHIFT are illegal end states; however, * TAP_DRSHIFT/IRSHIFT can be emulated as end states, by using longer * scans. * * Code that is relatively insensitive to the path taken through state * machine (as long as it is JTAG compliant) can use @a endstate for * jtag_add_xxx_scan(). Otherwise, the pause state must be specified as * end state and a subsequent jtag_add_pathmove() must be issued. */ /** * Generate an IR SCAN with a list of scan fields with one entry for * each enabled TAP. * * If the input field list contains an instruction value for a TAP then * that is used otherwise the TAP is set to bypass. * * TAPs for which no fields are passed are marked as bypassed for * subsequent DR SCANs. * */ void jtag_add_ir_scan(struct jtag_tap *tap, struct scan_field *fields, tap_state_t endstate); /** * The same as jtag_add_ir_scan except no verification is performed out * the output values. */ void jtag_add_ir_scan_noverify(struct jtag_tap *tap, const struct scan_field *fields, tap_state_t state); /** * Scan out the bits in ir scan mode. * * If in_bits == NULL, discard incoming bits. */ void jtag_add_plain_ir_scan(int num_bits, const uint8_t *out_bits, uint8_t *in_bits, tap_state_t endstate); /** * Generate a DR SCAN using the fields passed to the function. * For connected TAPs, the function checks in_fields and uses fields * specified there. For bypassed TAPs, the function generates a dummy * 1-bit field. The bypass status of TAPs is set by jtag_add_ir_scan(). */ void jtag_add_dr_scan(struct jtag_tap *tap, int num_fields, const struct scan_field *fields, tap_state_t endstate); /** A version of jtag_add_dr_scan() that uses the check_value/mask fields */ void jtag_add_dr_scan_check(struct jtag_tap *tap, int num_fields, struct scan_field *fields, tap_state_t endstate); /** * Scan out the bits in ir scan mode. * * If in_bits == NULL, discard incoming bits. */ void jtag_add_plain_dr_scan(int num_bits, const uint8_t *out_bits, uint8_t *in_bits, tap_state_t endstate); /** * Defines the type of data passed to the jtag_callback_t interface. * The underlying type must allow storing an @c int or pointer type. */ typedef intptr_t jtag_callback_data_t; /** * Defines a simple JTAG callback that can allow conversions on data * scanned in from an interface. * * This callback should only be used for conversion that cannot fail. * For conversion types or checks that can fail, use the more complete * variant: jtag_callback_t. */ typedef void (*jtag_callback1_t)(jtag_callback_data_t data0); /** A simpler version of jtag_add_callback4(). */ void jtag_add_callback(jtag_callback1_t f, jtag_callback_data_t data0); /** * Defines the interface of the JTAG callback mechanism. Such * callbacks can be executed once the queue has been flushed. * * The JTAG queue can be executed synchronously or asynchronously. * Typically for USB, the queue is executed asynchronously. For * low-latency interfaces, the queue may be executed synchronously. * * The callback mechanism is very general and does not make many * assumptions about what the callback does or what its arguments are. * These callbacks are typically executed *after* the *entire* JTAG * queue has been executed for e.g. USB interfaces, and they are * guaranteeed to be invoked in the order that they were queued. * * If the execution of the queue fails before the callbacks, then -- * depending on driver implementation -- the callbacks may or may not be * invoked. * * @todo Make that behavior consistent. * * @param data0 Typically used to point to the data to operate on. * Frequently this will be the data clocked in during a shift operation. * @param data1 An integer big enough to use as an @c int or a pointer. * @param data2 An integer big enough to use as an @c int or a pointer. * @param data3 An integer big enough to use as an @c int or a pointer. * @returns an error code */ typedef int (*jtag_callback_t)(jtag_callback_data_t data0, jtag_callback_data_t data1, jtag_callback_data_t data2, jtag_callback_data_t data3); /** * Run a TAP_RESET reset where the end state is TAP_RESET, * regardless of the start state. */ void jtag_add_tlr(void); /** * Application code *must* assume that interfaces will * implement transitions between states with different * paths and path lengths through the state diagram. The * path will vary across interface and also across versions * of the same interface over time. Even if the OpenOCD code * is unchanged, the actual path taken may vary over time * and versions of interface firmware or PCB revisions. * * Use jtag_add_pathmove() when specific transition sequences * are required. * * Do not use jtag_add_pathmove() unless you need to, but do use it * if you have to. * * DANGER! If the target is dependent upon a particular sequence * of transitions for things to work correctly(e.g. as a workaround * for an errata that contradicts the JTAG standard), then pathmove * must be used, even if some jtag interfaces happen to use the * desired path. Worse, the jtag interface used for testing a * particular implementation, could happen to use the "desired" * path when transitioning to/from end * state. * * A list of unambigious single clock state transitions, not * all drivers can support this, but it is required for e.g. * XScale and Xilinx support * * Note! TAP_RESET must not be used in the path! * * Note that the first on the list must be reachable * via a single transition from the current state. * * All drivers are required to implement jtag_add_pathmove(). * However, if the pathmove sequence can not be precisely * executed, an interface_jtag_add_pathmove() or jtag_execute_queue() * must return an error. It is legal, but not recommended, that * a driver returns an error in all cases for a pathmove if it * can only implement a few transitions and therefore * a partial implementation of pathmove would have little practical * application. * * If an error occurs, jtag_error will contain one of these error codes: * - ERROR_JTAG_NOT_STABLE_STATE -- The final state was not stable. * - ERROR_JTAG_STATE_INVALID -- The path passed through TAP_RESET. * - ERROR_JTAG_TRANSITION_INVALID -- The path includes invalid * state transitions. */ void jtag_add_pathmove(int num_states, const tap_state_t *path); /** * jtag_add_statemove() moves from the current state to @a goal_state. * * @param goal_state The final TAP state. * @return ERROR_OK on success, or an error code on failure. * * Moves from the current state to the goal \a state. * Both states must be stable. */ int jtag_add_statemove(tap_state_t goal_state); /** * Goes to TAP_IDLE (if we're not already there), cycle * precisely num_cycles in the TAP_IDLE state, after which move * to @a endstate (unless it is also TAP_IDLE). * * @param num_cycles Number of cycles in TAP_IDLE state. This argument * may be 0, in which case this routine will navigate to @a endstate * via TAP_IDLE. * @param endstate The final state. */ void jtag_add_runtest(int num_cycles, tap_state_t endstate); /** * A reset of the TAP state machine can be requested. * * Whether tms or trst reset is used depends on the capabilities of * the target and jtag interface(reset_config command configures this). * * srst can driver a reset of the TAP state machine and vice * versa * * Application code may need to examine value of jtag_reset_config * to determine the proper codepath * * DANGER! Even though srst drives trst, trst might not be connected to * the interface, and it might actually be *harmful* to assert trst in this case. * * This is why combinations such as "reset_config srst_only srst_pulls_trst" * are supported. * * only req_tlr_or_trst and srst can have a transition for a * call as the effects of transitioning both at the "same time" * are undefined, but when srst_pulls_trst or vice versa, * then trst & srst *must* be asserted together. */ void jtag_add_reset(int req_tlr_or_trst, int srst); void jtag_add_sleep(uint32_t us); int jtag_add_tms_seq(unsigned nbits, const uint8_t *seq, enum tap_state t); /** * Function jtag_add_clocks * first checks that the state in which the clocks are to be issued is * stable, then queues up num_cycles clocks for transmission. */ void jtag_add_clocks(int num_cycles); /** * For software FIFO implementations, the queued commands can be executed * during this call or earlier. A sw queue might decide to push out * some of the jtag_add_xxx() operations once the queue is "big enough". * * This fn will return an error code if any of the prior jtag_add_xxx() * calls caused a failure, e.g. check failure. Note that it does not * matter if the operation was executed *before* jtag_execute_queue(), * jtag_execute_queue() will still return an error code. * * All jtag_add_xxx() calls that have in_handler != NULL will have been * executed when this fn returns, but if what has been queued only * clocks data out, without reading anything back, then JTAG could * be running *after* jtag_execute_queue() returns. The API does * not define a way to flush a hw FIFO that runs *after* * jtag_execute_queue() returns. * * jtag_add_xxx() commands can either be executed immediately or * at some time between the jtag_add_xxx() fn call and jtag_execute_queue(). */ int jtag_execute_queue(void); /** same as jtag_execute_queue() but does not clear the error flag */ void jtag_execute_queue_noclear(void); /** @returns the number of times the scan queue has been flushed */ int jtag_get_flush_queue_count(void); /** Report Tcl event to all TAPs */ void jtag_notify_event(enum jtag_event); /* can be implemented by hw + sw */ int jtag_power_dropout(int *dropout); int jtag_srst_asserted(int *srst_asserted); /* JTAG support functions */ /** * Execute jtag queue and check value with an optional mask. * @param field Pointer to scan field. * @param value Pointer to scan value. * @param mask Pointer to scan mask; may be NULL. * @returns Nothing, but calls jtag_set_error() on any error. */ void jtag_check_value_mask(struct scan_field *field, uint8_t *value, uint8_t *mask); void jtag_sleep(uint32_t us); /* * The JTAG subsystem defines a number of error codes, * using codes between -100 and -199. */ #define ERROR_JTAG_INIT_FAILED (-100) #define ERROR_JTAG_INVALID_INTERFACE (-101) #define ERROR_JTAG_NOT_IMPLEMENTED (-102) #define ERROR_JTAG_TRST_ASSERTED (-103) #define ERROR_JTAG_QUEUE_FAILED (-104) #define ERROR_JTAG_NOT_STABLE_STATE (-105) #define ERROR_JTAG_DEVICE_ERROR (-107) #define ERROR_JTAG_STATE_INVALID (-108) #define ERROR_JTAG_TRANSITION_INVALID (-109) #define ERROR_JTAG_INIT_SOFT_FAIL (-110) /** * Set the current JTAG core execution error, unless one was set * by a previous call previously. Driver or application code must * use jtag_error_clear to reset jtag_error once this routine has been * called with a non-zero error code. */ void jtag_set_error(int error); /** * Resets jtag_error to ERROR_OK, returning its previous value. * @returns The previous value of @c jtag_error. */ int jtag_error_clear(void); /** * Return true if it's safe for a background polling task to access the * JTAG scan chain. Polling may be explicitly disallowed, and is also * unsafe while nTRST is active or the JTAG clock is gated off. */ bool is_jtag_poll_safe(void); /** * Return flag reporting whether JTAG polling is disallowed. */ bool jtag_poll_get_enabled(void); /** * Assign flag reporting whether JTAG polling is disallowed. */ void jtag_poll_set_enabled(bool value); /* The minidriver may have inline versions of some of the low * level APIs that are used in inner loops. */ #include <jtag/minidriver.h> int jim_jtag_newtap(Jim_Interp *interp, int argc, Jim_Obj *const *argv); #endif /* OPENOCD_JTAG_JTAG_H */

generated by cgit v1.1 at 2026-02-12 02:24:10 +0000

/* java.math.BigInteger -- Arbitary precision integers
   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2006  Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
 
GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.math;

import gnu.java.math.MPN;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Random;

/**
 * Written using on-line Java Platform 1.2 API Specification, as well
 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
 * 
 * Based primarily on IntNum.java BitOps.java by Per Bothner (per@bothner.com)
 * (found in Kawa 1.6.62).
 *
 * @author Warren Levy (warrenl@cygnus.com)
 * @date December 20, 1999.
 * @status believed complete and correct.
 */
public class BigInteger extends Number implements Comparable<BigInteger>
{
  /** All integers are stored in 2's-complement form.
   * If words == null, the ival is the value of this BigInteger.
   * Otherwise, the first ival elements of words make the value
   * of this BigInteger, stored in little-endian order, 2's-complement form. */
  private transient int ival;
  private transient int[] words;

  // Serialization fields.
  private int bitCount = -1;
  private int bitLength = -1;
  private int firstNonzeroByteNum = -2;
  private int lowestSetBit = -2;
  private byte[] magnitude;
  private int signum;
  private static final long serialVersionUID = -8287574255936472291L;


  /** We pre-allocate integers in the range minFixNum..maxFixNum. 
   * Note that we must at least preallocate 0, 1, and 10.  */
  private static final int minFixNum = -100;
  private static final int maxFixNum = 1024;
  private static final int numFixNum = maxFixNum-minFixNum+1;
  private static final BigInteger[] smallFixNums = new BigInteger[numFixNum];

  static
  {
    for (int i = numFixNum;  --i >= 0; )
      smallFixNums[i] = new BigInteger(i + minFixNum);
  }

  /**
   * The constant zero as a BigInteger.
   * @since 1.2
   */
  public static final BigInteger ZERO = smallFixNums[0 - minFixNum];

  /**
   * The constant one as a BigInteger.
   * @since 1.2
   */
  public static final BigInteger ONE = smallFixNums[1 - minFixNum];

  /**
   * The constant ten as a BigInteger.
   * @since 1.5
   */
  public static final BigInteger TEN = smallFixNums[10 - minFixNum];

  /* Rounding modes: */
  private static final int FLOOR = 1;
  private static final int CEILING = 2;
  private static final int TRUNCATE = 3;
  private static final int ROUND = 4;

  /** When checking the probability of primes, it is most efficient to
   * first check the factoring of small primes, so we'll use this array.
   */
  private static final int[] primes =
    {   2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,
       47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97, 101, 103, 107,
      109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
      191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };

  /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
  private static final int[] k =
      {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
  private static final int[] t =
      { 27, 18, 15, 12,  9,  8,  7,  6,  5,  4,   3, 2};

  private BigInteger()
  {
  }

  /* Create a new (non-shared) BigInteger, and initialize to an int. */
  private BigInteger(int value)
  {
    ival = value;
  }

  public BigInteger(String val, int radix)
  {
    BigInteger result = valueOf(val, radix);
    this.ival = result.ival;
    this.words = result.words;
  }

  public BigInteger(String val)
  {
    this(val, 10);
  }

  /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
  public BigInteger(byte[] val)
  {
    if (val == null || val.length < 1)
      throw new NumberFormatException();

    words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
    BigInteger result = make(words, words.length);
    this.ival = result.ival;
    this.words = result.words;
  }

  public BigInteger(int signum, byte[] magnitude)
  {
    if (magnitude == null || signum > 1 || signum < -1)
      throw new NumberFormatException();

    if (signum == 0)
      {
	int i;
	for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
	  ;
	if (i >= 0)
	  throw new NumberFormatException();
        return;
      }

    // Magnitude is always positive, so don't ever pass a sign of -1.
    words = byteArrayToIntArray(magnitude, 0);
    BigInteger result = make(words, words.length);
    this.ival = result.ival;
    this.words = result.words;

    if (signum < 0)
      setNegative();
  }

  public BigInteger(int numBits, Random rnd)
  {
    if (numBits < 0)
      throw new IllegalArgumentException();

    init(numBits, rnd);
  }

  private void init(int numBits, Random rnd)
  {
    int highbits = numBits & 31;
    // minimum number of bytes to store the above number of bits
    int highBitByteCount = (highbits + 7) / 8;
    // number of bits to discard from the last byte
    int discardedBitCount = highbits % 8;
    if (discardedBitCount != 0)
      discardedBitCount = 8 - discardedBitCount;
    byte[] highBitBytes = new byte[highBitByteCount];
    if (highbits > 0)
      {
        rnd.nextBytes(highBitBytes);
        highbits = (highBitBytes[highBitByteCount - 1] & 0xFF) >>> discardedBitCount;
        for (int i = highBitByteCount - 2; i >= 0; i--)
          highbits = (highbits << 8) | (highBitBytes[i] & 0xFF);
      }
    int nwords = numBits / 32;

    while (highbits == 0 && nwords > 0)
      {
	highbits = rnd.nextInt();
	--nwords;
      }
    if (nwords == 0 && highbits >= 0)
      {
	ival = highbits;
      }
    else
      {
	ival = highbits < 0 ? nwords + 2 : nwords + 1;
	words = new int[ival];
	words[nwords] = highbits;
	while (--nwords >= 0)
	  words[nwords] = rnd.nextInt();
      }
  }

  public BigInteger(int bitLength, int certainty, Random rnd)
  {
    this(bitLength, rnd);

    // Keep going until we find a probable prime.
    BigInteger result;
    while (true)
      {
        // ...but first ensure that BI has bitLength bits
        result = setBit(bitLength - 1);
        this.ival = result.ival;
        this.words = result.words;
	if (isProbablePrime(certainty))
	  return;

	init(bitLength, rnd);
      }
  }

  /** 
   *  Return a BigInteger that is bitLength bits long with a
   *  probability < 2^-100 of being composite.
   *
   *  @param bitLength length in bits of resulting number
   *  @param rnd random number generator to use
   *  @throws ArithmeticException if bitLength < 2
   *  @since 1.4
   */
  public static BigInteger probablePrime(int bitLength, Random rnd)
  {
    if (bitLength < 2)
      throw new ArithmeticException();

    return new BigInteger(bitLength, 100, rnd);
  }

  /** Return a (possibly-shared) BigInteger with a given long value. */
  public static BigInteger valueOf(long val)
  {
    if (val >= minFixNum && val <= maxFixNum)
      return smallFixNums[(int) val - minFixNum];
    int i = (int) val;
    if ((long) i == val)
      return new BigInteger(i);
    BigInteger result = alloc(2);
    result.ival = 2;
    result.words[0] = i;
    result.words[1] = (int)(val >> 32);
    return result;
  }

  /** Make a canonicalized BigInteger from an array of words.
   * The array may be reused (without copying). */
  private static BigInteger make(int[] words, int len)
  {
    if (words == null)
      return valueOf(len);
    len = BigInteger.wordsNeeded(words, len);
    if (len <= 1)
      return len == 0 ? ZERO : valueOf(words[0]);
    BigInteger num = new BigInteger();
    num.words = words;
    num.ival = len;
    return num;
  }

  /** Convert a big-endian byte array to a little-endian array of words. */
  private static int[] byteArrayToIntArray(byte[] bytes, int sign)
  {
    // Determine number of words needed.
    int[] words = new int[bytes.length/4 + 1];
    int nwords = words.length;

    // Create a int out of modulo 4 high order bytes.
    int bptr = 0;
    int word = sign;
    for (int i = bytes.length % 4; i > 0; --i, bptr++)
      word = (word << 8) | (bytes[bptr] & 0xff);
    words[--nwords] = word;

    // Elements remaining in byte[] are a multiple of 4.
    while (nwords > 0)
      words[--nwords] = bytes[bptr++] << 24 |
			(bytes[bptr++] & 0xff) << 16 |
			(bytes[bptr++] & 0xff) << 8 |
			(bytes[bptr++] & 0xff);
    return words;
  }

  /** Allocate a new non-shared BigInteger.
   * @param nwords number of words to allocate
   */
  private static BigInteger alloc(int nwords)
  {
    BigInteger result = new BigInteger();
    if (nwords > 1)
    result.words = new int[nwords];
    return result;
  }

  /** Change words.length to nwords.
   * We allow words.length to be upto nwords+2 without reallocating.
   */
  private void realloc(int nwords)
  {
    if (nwords == 0)
      {
	if (words != null)
	  {
	    if (ival > 0)
	      ival = words[0];
	    words = null;
	  }
      }
    else if (words == null
	     || words.length < nwords
	     || words.length > nwords + 2)
      {
	int[] new_words = new int [nwords];
	if (words == null)
	  {
	    new_words[0] = ival;
	    ival = 1;
	  }
	else
	  {
	    if (nwords < ival)
	      ival = nwords;
	    System.arraycopy(words, 0, new_words, 0, ival);
	  }
	words = new_words;
      }
  }

  private boolean isNegative()
  {
    return (words == null ? ival : words[ival - 1]) < 0;
  }

  public int signum()
  {
    if (ival == 0 && words == null)
      return 0;
    int top = words == null ? ival : words[ival-1];
    return top < 0 ? -1 : 1;
  }

  private static int compareTo(BigInteger x, BigInteger y)
  {
    if (x.words == null && y.words == null)
      return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
    boolean x_negative = x.isNegative();
    boolean y_negative = y.isNegative();
    if (x_negative != y_negative)
      return x_negative ? -1 : 1;
    int x_len = x.words == null ? 1 : x.ival;
    int y_len = y.words == null ? 1 : y.ival;
    if (x_len != y_len)
      return (x_len > y_len) != x_negative ? 1 : -1;
    return MPN.cmp(x.words, y.words, x_len);
  }

  /** @since 1.2 */
  public int compareTo(BigInteger val)
  {
    return compareTo(this, val);
  }

  public BigInteger min(BigInteger val)
  {
    return compareTo(this, val) < 0 ? this : val;
  }

  public BigInteger max(BigInteger val)
  {
    return compareTo(this, val) > 0 ? this : val;
  }

  private boolean isZero()
  {
    return words == null && ival == 0;
  }

  private boolean isOne()
  {
    return words == null && ival == 1;
  }

  /** Calculate how many words are significant in words[0:len-1].
   * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
   * when words is viewed as a 2's complement integer.
   */
  private static int wordsNeeded(int[] words, int len)
  {
    int i = len;
    if (i > 0)
      {
	int word = words[--i];
	if (word == -1)
	  {
	    while (i > 0 && (word = words[i - 1]) < 0)
	      {
		i--;
		if (word != -1) break;
	      }
	  }
	else
	  {
	    while (word == 0 && i > 0 && (word = words[i - 1]) >= 0)  i--;
	  }
      }
    return i + 1;
  }

  private BigInteger canonicalize()
  {
    if (words != null
	&& (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
      {
	if (ival == 1)
	  ival = words[0];
	words = null;
      }
    if (words == null && ival >= minFixNum && ival <= maxFixNum)
      return smallFixNums[ival - minFixNum];
    return this;
  }

  /** Add two ints, yielding a BigInteger. */
  private static BigInteger add(int x, int y)
  {
    return valueOf((long) x + (long) y);
  }

  /** Add a BigInteger and an int, yielding a new BigInteger. */
  private static BigInteger add(BigInteger x, int y)
  {
    if (x.words == null)
      return BigInteger.add(x.ival, y);
    BigInteger result = new BigInteger(0);
    result.setAdd(x, y);
    return result.canonicalize();
  }

  /** Set this to the sum of x and y.
   * OK if x==this. */
  private void setAdd(BigInteger x, int y)
  {
    if (x.words == null)
      {
	set((long) x.ival + (long) y);
	return;
      }
    int len = x.ival;
    realloc(len + 1);
    long carry = y;
    for (int i = 0;  i < len;  i++)
      {
	carry += ((long) x.words[i] & 0xffffffffL);
	words[i] = (int) carry;
	carry >>= 32;
      }
    if (x.words[len - 1] < 0)
      carry--;
    words[len] = (int) carry;
    ival = wordsNeeded(words, len + 1);
  }

  /** Destructively add an int to this. */
  private void setAdd(int y)
  {
    setAdd(this, y);
  }

  /** Destructively set the value of this to a long. */
  private void set(long y)
  {
    int i = (int) y;
    if ((long) i == y)
      {
	ival = i;
	words = null;
      }
    else
      {
	realloc(2);
	words[0] = i;
	words[1] = (int) (y >> 32);
	ival = 2;
      }
  }

  /** Destructively set the value of this to the given words.
  * The words array is reused, not copied. */
  private void set(int[] words, int length)
  {
    this.ival = length;
    this.words = words;
  }

  /** Destructively set the value of this to that of y. */
  private void set(BigInteger y)
  {
    if (y.words == null)
      set(y.ival);
    else if (this != y)
      {
	realloc(y.ival);
	System.arraycopy(y.words, 0, words, 0, y.ival);
	ival = y.ival;
      }
  }

  /** Add two BigIntegers, yielding their sum as another BigInteger. */
  private static BigInteger add(BigInteger x, BigInteger y, int k)
  {
    if (x.words == null && y.words == null)
      return valueOf((long) k * (long) y.ival + (long) x.ival);
    if (k != 1)
      {
	if (k == -1)
	  y = BigInteger.neg(y);
	else
	  y = BigInteger.times(y, valueOf(k));
      }
    if (x.words == null)
      return BigInteger.add(y, x.ival);
    if (y.words == null)
      return BigInteger.add(x, y.ival);
    // Both are big
    if (y.ival > x.ival)
      { // Swap so x is longer then y.
	BigInteger tmp = x;  x = y;  y = tmp;
      }
    BigInteger result = alloc(x.ival + 1);
    int i = y.ival;
    long carry = MPN.add_n(result.words, x.words, y.words, i);
    long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
    for (; i < x.ival;  i++)
      {
	carry += ((long) x.words[i] & 0xffffffffL) + y_ext;;
	result.words[i] = (int) carry;
	carry >>>= 32;
      }
    if (x.words[i - 1] < 0)
      y_ext--;
    result.words[i] = (int) (carry + y_ext);
    result.ival = i+1;
    return result.canonicalize();
  }

  public BigInteger add(BigInteger val)
  {
    return add(this, val, 1);
  }

  public BigInteger subtract(BigInteger val)
  {
    return add(this, val, -1);
  }

  private static BigInteger times(BigInteger x, int y)
  {
    if (y == 0)
      return ZERO;
    if (y == 1)
      return x;
    int[] xwords = x.words;
    int xlen = x.ival;
    if (xwords == null)
      return valueOf((long) xlen * (long) y);
    boolean negative;
    BigInteger result = BigInteger.alloc(xlen + 1);
    if (xwords[xlen - 1] < 0)
      {
	negative = true;
	negate(result.words, xwords, xlen);
	xwords = result.words;
      }
    else
      negative = false;
    if (y < 0)
      {
	negative = !negative;
	y = -y;
      }
    result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
    result.ival = xlen + 1;
    if (negative)
      result.setNegative();
    return result.canonicalize();
  }

  private static BigInteger times(BigInteger x, BigInteger y)
  {
    if (y.words == null)
      return times(x, y.ival);
    if (x.words == null)
      return times(y, x.ival);
    boolean negative = false;
    int[] xwords;
    int[] ywords;
    int xlen = x.ival;
    int ylen = y.ival;
    if (x.isNegative())
      {
	negative = true;
	xwords = new int[xlen];
	negate(xwords, x.words, xlen);
      }
    else
      {
	negative = false;
	xwords = x.words;
      }
    if (y.isNegative())
      {
	negative = !negative;
	ywords = new int[ylen];
	negate(ywords, y.words, ylen);
      }
    else
      ywords = y.words;
    // Swap if x is shorter then y.
    if (xlen < ylen)
      {
	int[] twords = xwords;  xwords = ywords;  ywords = twords;
	int tlen = xlen;  xlen = ylen;  ylen = tlen;
      }
    BigInteger result = BigInteger.alloc(xlen+ylen);
    MPN.mul(result.words, xwords, xlen, ywords, ylen);
    result.ival = xlen+ylen;
    if (negative)
      result.setNegative();
    return result.canonicalize();
  }

  public BigInteger multiply(BigInteger y)
  {
    return times(this, y);
  }

  private static void divide(long x, long y,
			     BigInteger quotient, BigInteger remainder,
			     int rounding_mode)
  {
    boolean xNegative, yNegative;
    if (x < 0)
      {
	xNegative = true;
	if (x == Long.MIN_VALUE)
	  {
	    divide(valueOf(x), valueOf(y),
		   quotient, remainder, rounding_mode);
	    return;
	  }
	x = -x;
      }
    else
      xNegative = false;

    if (y < 0)
      {
	yNegative = true;
	if (y == Long.MIN_VALUE)
	  {
	    if (rounding_mode == TRUNCATE)
	      { // x != Long.Min_VALUE implies abs(x) < abs(y)
		if (quotient != null)
		  quotient.set(0);
		if (remainder != null)
		  remainder.set(x);
	      }
	    else
	      divide(valueOf(x), valueOf(y),
		      quotient, remainder, rounding_mode);
	    return;
	  }
	y = -y;
      }
    else
      yNegative = false;

    long q = x / y;
    long r = x % y;
    boolean qNegative = xNegative ^ yNegative;

    boolean add_one = false;
    if (r != 0)
      {
	switch (rounding_mode)
	  {
	  case TRUNCATE:
	    break;
	  case CEILING:
	  case FLOOR:
	    if (qNegative == (rounding_mode == FLOOR))
	      add_one = true;
	    break;
	  case ROUND:
	    add_one = r > ((y - (q & 1)) >> 1);
	    break;
	  }
      }
    if (quotient != null)
      {
	if (add_one)
	  q++;
	if (qNegative)
	  q = -q;
	quotient.set(q);
      }
    if (remainder != null)
      {
	// The remainder is by definition: X-Q*Y
	if (add_one)
	  {
	    // Subtract the remainder from Y.
	    r = y - r;
	    // In this case, abs(Q*Y) > abs(X).
	    // So sign(remainder) = -sign(X).
	    xNegative = ! xNegative;
	  }
	else
	  {
	    // If !add_one, then: abs(Q*Y) <= abs(X).
	    // So sign(remainder) = sign(X).
	  }
	if (xNegative)
	  r = -r;
	remainder.set(r);
      }
  }

  /** Divide two integers, yielding quotient and remainder.
   * @param x the numerator in the division
   * @param y the denominator in the division
   * @param quotient is set to the quotient of the result (iff quotient!=null)
   * @param remainder is set to the remainder of the result
   *  (iff remainder!=null)
   * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
   */
  private static void divide(BigInteger x, BigInteger y,
			     BigInteger quotient, BigInteger remainder,
			     int rounding_mode)
  {
    if ((x.words == null || x.ival <= 2)
	&& (y.words == null || y.ival <= 2))
      {
	long x_l = x.longValue();
	long y_l = y.longValue();
	if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
	  {
	    divide(x_l, y_l, quotient, remainder, rounding_mode);
	    return;
	  }
      }

    boolean xNegative = x.isNegative();
    boolean yNegative = y.isNegative();
    boolean qNegative = xNegative ^ yNegative;

    int ylen = y.words == null ? 1 : y.ival;
    int[] ywords = new int[ylen];
    y.getAbsolute(ywords);
    while (ylen > 1 && ywords[ylen - 1] == 0)  ylen--;

    int xlen = x.words == null ? 1 : x.ival;
    int[] xwords = new int[xlen+2];
    x.getAbsolute(xwords);
    while (xlen > 1 && xwords[xlen-1] == 0)  xlen--;

    int qlen, rlen;

    int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
    if (cmpval < 0)  // abs(x) < abs(y)
      { // quotient = 0;  remainder = num.
	int[] rwords = xwords;  xwords = ywords;  ywords = rwords;
	rlen = xlen;  qlen = 1;  xwords[0] = 0;
      }
    else if (cmpval == 0)  // abs(x) == abs(y)
      {
	xwords[0] = 1;  qlen = 1;  // quotient = 1
	ywords[0] = 0;  rlen = 1;  // remainder = 0;
      }
    else if (ylen == 1)
      {
	qlen = xlen;
	// Need to leave room for a word of leading zeros if dividing by 1
	// and the dividend has the high bit set.  It might be safe to
	// increment qlen in all cases, but it certainly is only necessary
	// in the following case.
	if (ywords[0] == 1 && xwords[xlen-1] < 0)
	  qlen++;
	rlen = 1;
	ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
      }
    else  // abs(x) > abs(y)
      {
	// Normalize the denominator, i.e. make its most significant bit set by
	// shifting it normalization_steps bits to the left.  Also shift the
	// numerator the same number of steps (to keep the quotient the same!).

	int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
	if (nshift != 0)
	  {
	    // Shift up the denominator setting the most significant bit of
	    // the most significant word.
	    MPN.lshift(ywords, 0, ywords, ylen, nshift);

	    // Shift up the numerator, possibly introducing a new most
	    // significant word.
	    int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
	    xwords[xlen++] = x_high;
	  }

	if (xlen == ylen)
	  xwords[xlen++] = 0;
	MPN.divide(xwords, xlen, ywords, ylen);
	rlen = ylen;
	MPN.rshift0 (ywords, xwords, 0, rlen, nshift);

	qlen = xlen + 1 - ylen;
	if (quotient != null)
	  {
	    for (int i = 0;  i < qlen;  i++)
	      xwords[i] = xwords[i+ylen];
	  }
      }

    if (ywords[rlen-1] < 0)
      {
        ywords[rlen] = 0;
        rlen++;
      }

    // Now the quotient is in xwords, and the remainder is in ywords.

    boolean add_one = false;
    if (rlen > 1 || ywords[0] != 0)
      { // Non-zero remainder i.e. in-exact quotient.
	switch (rounding_mode)
	  {
	  case TRUNCATE:
	    break;
	  case CEILING:
	  case FLOOR:
	    if (qNegative == (rounding_mode == FLOOR))
	      add_one = true;
	    break;
	  case ROUND:
	    // int cmp = compareTo(remainder<<1, abs(y));
	    BigInteger tmp = remainder == null ? new BigInteger() : remainder;
	    tmp.set(ywords, rlen);
	    tmp = shift(tmp, 1);
	    if (yNegative)
	      tmp.setNegative();
	    int cmp = compareTo(tmp, y);
	    // Now cmp == compareTo(sign(y)*(remainder<<1), y)
	    if (yNegative)
	      cmp = -cmp;
	    add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
	  }
      }
    if (quotient != null)
      {
	quotient.set(xwords, qlen);
	if (qNegative)
	  {
	    if (add_one)  // -(quotient + 1) == ~(quotient)
	      quotient.setInvert();
	    else
	      quotient.setNegative();
	  }
	else if (add_one)
	  quotient.setAdd(1);
      }
    if (remainder != null)
      {
	// The remainder is by definition: X-Q*Y
	remainder.set(ywords, rlen);
	if (add_one)
	  {
	    // Subtract the remainder from Y:
	    // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
	    BigInteger tmp;
	    if (y.words == null)
	      {
		tmp = remainder;
		tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
	      }
	    else
	      tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
	    // Now tmp <= 0.
	    // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
	    // Hence, abs(Q*Y) > abs(X).
	    // So sign(remainder) = -sign(X).
	    if (xNegative)
	      remainder.setNegative(tmp);
	    else
	      remainder.set(tmp);
	  }
	else
	  {
	    // If !add_one, then: abs(Q*Y) <= abs(X).
	    // So sign(remainder) = sign(X).
	    if (xNegative)
	      remainder.setNegative();
	  }
      }
  }

  public BigInteger divide(BigInteger val)
  {
    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger quot = new BigInteger();
    divide(this, val, quot, null, TRUNCATE);
    return quot.canonicalize();
  }

  public BigInteger remainder(BigInteger val)
  {
    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger rem = new BigInteger();
    divide(this, val, null, rem, TRUNCATE);
    return rem.canonicalize();
  }

  public BigInteger[] divideAndRemainder(BigInteger val)
  {
    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger[] result = new BigInteger[2];
    result[0] = new BigInteger();
    result[1] = new BigInteger();
    divide(this, val, result[0], result[1], TRUNCATE);
    result[0].canonicalize();
    result[1].canonicalize();
    return result;
  }

  public BigInteger mod(BigInteger m)
  {
    if (m.isNegative() || m.isZero())
      throw new ArithmeticException("non-positive modulus");

    BigInteger rem = new BigInteger();
    divide(this, m, null, rem, FLOOR);
    return rem.canonicalize();
  }

  /** Calculate the integral power of a BigInteger.
   * @param exponent the exponent (must be non-negative)
   */
  public BigInteger pow(int exponent)
  {
    if (exponent <= 0)
      {
	if (exponent == 0)
	  return ONE;
	  throw new ArithmeticException("negative exponent");
      }
    if (isZero())
      return this;
    int plen = words == null ? 1 : ival;  // Length of pow2.
    int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
    boolean negative = isNegative() && (exponent & 1) != 0;
    int[] pow2 = new int [blen];
    int[] rwords = new int [blen];
    int[] work = new int [blen];
    getAbsolute(pow2);	// pow2 = abs(this);
    int rlen = 1;
    rwords[0] = 1; // rwords = 1;
    for (;;)  // for (i = 0;  ; i++)
      {
	// pow2 == this**(2**i)
	// prod = this**(sum(j=0..i-1, (exponent>>j)&1))
	if ((exponent & 1) != 0)
	  { // r *= pow2
	    MPN.mul(work, pow2, plen, rwords, rlen);
	    int[] temp = work;  work = rwords;  rwords = temp;
	    rlen += plen;
	    while (rwords[rlen - 1] == 0)  rlen--;
	  }
	exponent >>= 1;
	if (exponent == 0)
	  break;
	// pow2 *= pow2;
	MPN.mul(work, pow2, plen, pow2, plen);
	int[] temp = work;  work = pow2;  pow2 = temp;  // swap to avoid a copy
	plen *= 2;
	while (pow2[plen - 1] == 0)  plen--;
      }
    if (rwords[rlen - 1] < 0)
      rlen++;
    if (negative)
      negate(rwords, rwords, rlen);
    return BigInteger.make(rwords, rlen);
  }

  private static int[] euclidInv(int a, int b, int prevDiv)
  {
    if (b == 0)
      throw new ArithmeticException("not invertible");

    if (b == 1)
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
	return new int[] { -prevDiv, 1 };

    int[] xy = euclidInv(b, a % b, a / b);	// Recursion happens here.
    a = xy[0]; // use our local copy of 'a' as a work var
    xy[0] = a * -prevDiv + xy[1];
    xy[1] = a;
    return xy;
  }

  private static void euclidInv(BigInteger a, BigInteger b,
                                BigInteger prevDiv, BigInteger[] xy)
  {
    if (b.isZero())
      throw new ArithmeticException("not invertible");

    if (b.isOne())
      {
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
	xy[0] = neg(prevDiv);
        xy[1] = ONE;
	return;
      }

    // Recursion happens in the following conditional!

    // If a just contains an int, then use integer math for the rest.
    if (a.words == null)
      {
        int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
	xy[0] = new BigInteger(xyInt[0]);
        xy[1] = new BigInteger(xyInt[1]);
      }
    else
      {
	BigInteger rem = new BigInteger();
	BigInteger quot = new BigInteger();
	divide(a, b, quot, rem, FLOOR);
        // quot and rem may not be in canonical form. ensure
        rem.canonicalize();
        quot.canonicalize();
	euclidInv(b, rem, quot, xy);
      }

    BigInteger t = xy[0];
    xy[0] = add(xy[1], times(t, prevDiv), -1);
    xy[1] = t;
  }

  public BigInteger modInverse(BigInteger y)
  {
    if (y.isNegative() || y.isZero())
      throw new ArithmeticException("non-positive modulo");

    // Degenerate cases.
    if (y.isOne())
      return ZERO;
    if (isOne())
      return ONE;

    // Use Euclid's algorithm as in gcd() but do this recursively
    // rather than in a loop so we can use the intermediate results as we
    // unwind from the recursion.
    // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
    BigInteger result = new BigInteger();
    boolean swapped = false;

    if (y.words == null)
      {
	// The result is guaranteed to be less than the modulus, y (which is
	// an int), so simplify this by working with the int result of this
	// modulo y.  Also, if this is negative, make it positive via modulo
	// math.  Note that BigInteger.mod() must be used even if this is
	// already an int as the % operator would provide a negative result if
	// this is negative, BigInteger.mod() never returns negative values.
        int xval = (words != null || isNegative()) ? mod(y).ival : ival;
        int yval = y.ival;

	// Swap values so x > y.
	if (yval > xval)
	  {
	    int tmp = xval; xval = yval; yval = tmp;
	    swapped = true;
	  }
	// Normally, the result is in the 2nd element of the array, but
	// if originally x < y, then x and y were swapped and the result
	// is in the 1st element of the array.
	result.ival =
	  euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];

	// Result can't be negative, so make it positive by adding the
	// original modulus, y.ival (not the possibly "swapped" yval).
	if (result.ival < 0)
	  result.ival += y.ival;
      }
    else
      {
	// As above, force this to be a positive value via modulo math.
	BigInteger x = isNegative() ? this.mod(y) : this;

	// Swap values so x > y.
	if (x.compareTo(y) < 0)
	  {
	    result = x; x = y; y = result; // use 'result' as a work var
	    swapped = true;
	  }
	// As above (for ints), result will be in the 2nd element unless
	// the original x and y were swapped.
	BigInteger rem = new BigInteger();
	BigInteger quot = new BigInteger();
	divide(x, y, quot, rem, FLOOR);
        // quot and rem may not be in canonical form. ensure
        rem.canonicalize();
        quot.canonicalize();
	BigInteger[] xy = new BigInteger[2];
	euclidInv(y, rem, quot, xy);
	result = swapped ? xy[0] : xy[1];

	// Result can't be negative, so make it positive by adding the
	// original modulus, y (which is now x if they were swapped).
	if (result.isNegative())
	  result = add(result, swapped ? x : y, 1);
      }
    
    return result;
  }

  public BigInteger modPow(BigInteger exponent, BigInteger m)
  {
    if (m.isNegative() || m.isZero())
      throw new ArithmeticException("non-positive modulo");

    if (exponent.isNegative())
      return modInverse(m).modPow(exponent.negate(), m);
    if (exponent.isOne())
      return mod(m);

    // To do this naively by first raising this to the power of exponent
    // and then performing modulo m would be extremely expensive, especially
    // for very large numbers.  The solution is found in Number Theory
    // where a combination of partial powers and moduli can be done easily.
    //
    // We'll use the algorithm for Additive Chaining which can be found on
    // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
    BigInteger s = ONE;
    BigInteger t = this;
    BigInteger u = exponent;

    while (!u.isZero())
      {
	if (u.and(ONE).isOne())
	  s = times(s, t).mod(m);
	u = u.shiftRight(1);
	t = times(t, t).mod(m);
      }

    return s;
  }

  /** Calculate Greatest Common Divisor for non-negative ints. */
  private static int gcd(int a, int b)
  {
    // Euclid's algorithm, copied from libg++.
    int tmp;
    if (b > a)
      {
	tmp = a; a = b; b = tmp;
      }
    for(;;)
      {
	if (b == 0)
	  return a;
        if (b == 1)
	  return b;
        tmp = b;
	    b = a % b;
	    a = tmp;
	  }
      }

  public BigInteger gcd(BigInteger y)
  {
    int xval = ival;
    int yval = y.ival;
    if (words == null)
      {
	if (xval == 0)
	  return abs(y);
	if (y.words == null
	    && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
	  {
	    if (xval < 0)
	      xval = -xval;
	    if (yval < 0)
	      yval = -yval;
	    return valueOf(gcd(xval, yval));
	  }
	xval = 1;
      }
    if (y.words == null)
      {
	if (yval == 0)
	  return abs(this);
	yval = 1;
      }
    int len = (xval > yval ? xval : yval) + 1;
    int[] xwords = new int[len];
    int[] ywords = new int[len];
    getAbsolute(xwords);
    y.getAbsolute(ywords);
    len = MPN.gcd(xwords, ywords, len);
    BigInteger result = new BigInteger(0);
    result.ival = len;
    result.words = xwords;
    return result.canonicalize();
  }

  /**
   * <p>Returns <code>true</code> if this BigInteger is probably prime,
   * <code>false</code> if it's definitely composite. If <code>certainty</code>
   * is <code><= 0</code>, <code>true</code> is returned.</p>
   *
   * @param certainty a measure of the uncertainty that the caller is willing
   * to tolerate: if the call returns <code>true</code> the probability that
   * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
   * The execution time of this method is proportional to the value of this
   * parameter.
   * @return <code>true</code> if this BigInteger is probably prime,
   * <code>false</code> if it's definitely composite.
   */
  public boolean isProbablePrime(int certainty)
  {
    if (certainty < 1)
      return true;

    /** We'll use the Rabin-Miller algorithm for doing a probabilistic
     * primality test.  It is fast, easy and has faster decreasing odds of a
     * composite passing than with other tests.  This means that this
     * method will actually have a probability much greater than the
     * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
     * anyone will complain about better performance with greater certainty.
     *
     * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
     * Cryptography, Second Edition" by Bruce Schneier.
     */

    // First rule out small prime factors
    BigInteger rem = new BigInteger();
    int i;
    for (i = 0; i < primes.length; i++)
      {
	if (words == null && ival == primes[i])
	  return true;

        divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
        if (rem.canonicalize().isZero())
	  return false;
      }

    // Now perform the Rabin-Miller test.

    // Set b to the number of times 2 evenly divides (this - 1).
    // I.e. 2^b is the largest power of 2 that divides (this - 1).
    BigInteger pMinus1 = add(this, -1);
    int b = pMinus1.getLowestSetBit();

    // Set m such that this = 1 + 2^b * m.
    BigInteger m = pMinus1.divide(valueOf(2L << b - 1));

    // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
    // 4.49 (controlling the error probability) gives the number of trials
    // for an error probability of 1/2**80, given the number of bits in the
    // number to test.  we shall use these numbers as is if/when 'certainty'
    // is less or equal to 80, and twice as much if it's greater.
    int bits = this.bitLength();
    for (i = 0; i < k.length; i++)
      if (bits <= k[i])
        break;
    int trials = t[i];
    if (certainty > 80)
      trials *= 2;
    BigInteger z;
    for (int t = 0; t < trials; t++)
      {
        // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
        // Remark 4.28 states: "...A strategy that is sometimes employed
        // is to fix the bases a to be the first few primes instead of
        // choosing them at random.
	z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
	if (z.isOne() || z.equals(pMinus1))
	  continue;			// Passes the test; may be prime.

	for (i = 0; i < b; )
	  {
	    if (z.isOne())
	      return false;
	    i++;
	    if (z.equals(pMinus1))
	      break;			// Passes the test; may be prime.

	    z = z.modPow(valueOf(2), this);
	  }

	if (i == b && !z.equals(pMinus1))
	  return false;
      }
    return true;
  }

  private void setInvert()
  {
    if (words == null)
      ival = ~ival;
    else
      {
	for (int i = ival;  --i >= 0; )
	  words[i] = ~words[i];
      }
  }

  private void setShiftLeft(BigInteger x, int count)
  {
    int[] xwords;
    int xlen;
    if (x.words == null)
      {
	if (count < 32)
	  {
	    set((long) x.ival << count);
	    return;
	  }
	xwords = new int[1];
	xwords[0] = x.ival;
	xlen = 1;
      }
    else
      {
	xwords = x.words;
	xlen = x.ival;
      }
    int word_count = count >> 5;
    count &= 31;
    int new_len = xlen + word_count;
    if (count == 0)
      {
	realloc(new_len);
	for (int i = xlen;  --i >= 0; )
	  words[i+word_count] = xwords[i];
      }
    else
      {
	new_len++;
	realloc(new_len);
	int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
	count = 32 - count;
	words[new_len-1] = (shift_out << count) >> count;  // sign-extend.
      }
    ival = new_len;
    for (int i = word_count;  --i >= 0; )
      words[i] = 0;
  }

  private void setShiftRight(BigInteger x, int count)
  {
    if (x.words == null)
      set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
    else if (count == 0)
      set(x);
    else
      {
	boolean neg = x.isNegative();
	int word_count = count >> 5;
	count &= 31;
	int d_len = x.ival - word_count;
	if (d_len <= 0)
	  set(neg ? -1 : 0);
	else
	  {
	    if (words == null || words.length < d_len)
	      realloc(d_len);
	    MPN.rshift0 (words, x.words, word_count, d_len, count);
	    ival = d_len;
	    if (neg)
	      words[d_len-1] |= -2 << (31 - count);
	  }
      }
  }

  private void setShift(BigInteger x, int count)
  {
    if (count > 0)
      setShiftLeft(x, count);
    else
      setShiftRight(x, -count);
  }

  private static BigInteger shift(BigInteger x, int count)
  {
    if (x.words == null)
      {
	if (count <= 0)
	  return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
	if (count < 32)
	  return valueOf((long) x.ival << count);
      }
    if (count == 0)
      return x;
    BigInteger result = new BigInteger(0);
    result.setShift(x, count);
    return result.canonicalize();
  }

  public BigInteger shiftLeft(int n)
  {
    return shift(this, n);
  }

  public BigInteger shiftRight(int n)
  {
    return shift(this, -n);
  }

  private void format(int radix, StringBuffer buffer)
  {
    if (words == null)
      buffer.append(Integer.toString(ival, radix));
    else if (ival <= 2)
      buffer.append(Long.toString(longValue(), radix));
    else
      {
	boolean neg = isNegative();
	int[] work;
	if (neg || radix != 16)
	  {
	    work = new int[ival];
	    getAbsolute(work);
	  }
	else
	  work = words;
	int len = ival;

	if (radix == 16)
	  {
	    if (neg)
	      buffer.append('-');
	    int buf_start = buffer.length();
	    for (int i = len;  --i >= 0; )
	      {
		int word = work[i];
		for (int j = 8;  --j >= 0; )
		  {
		    int hex_digit = (word >> (4 * j)) & 0xF;
		    // Suppress leading zeros:
		    if (hex_digit > 0 || buffer.length() > buf_start)
		      buffer.append(Character.forDigit(hex_digit, 16));
		  }
	      }
	  }
	else
	  {
	    int i = buffer.length();
	    for (;;)
	      {
		int digit = MPN.divmod_1(work, work, len, radix);
		buffer.append(Character.forDigit(digit, radix));
		while (len > 0 && work[len-1] == 0) len--;
		if (len == 0)
		  break;
	      }
	    if (neg)
	      buffer.append('-');
	    /* Reverse buffer. */
	    int j = buffer.length() - 1;
	    while (i < j)
	      {
		char tmp = buffer.charAt(i);
		buffer.setCharAt(i, buffer.charAt(j));
		buffer.setCharAt(j, tmp);
		i++;  j--;
	      }
	  }
      }
  }

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

  public String toString(int radix)
  {
    if (words == null)
      return Integer.toString(ival, radix);
    if (ival <= 2)
      return Long.toString(longValue(), radix);
    int buf_size = ival * (MPN.chars_per_word(radix) + 1);
    StringBuffer buffer = new StringBuffer(buf_size);
    format(radix, buffer);
    return buffer.toString();
  }

  public int intValue()
  {
    if (words == null)
      return ival;
    return words[0];
  }

  public long longValue()
  {
    if (words == null)
      return ival;
    if (ival == 1)
      return words[0];
    return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
  }

  public int hashCode()
  {
    // FIXME: May not match hashcode of JDK.
    return words == null ? ival : (words[0] + words[ival - 1]);
  }

  /* Assumes x and y are both canonicalized. */
  private static boolean equals(BigInteger x, BigInteger y)
  {
    if (x.words == null && y.words == null)
      return x.ival == y.ival;
    if (x.words == null || y.words == null || x.ival != y.ival)
      return false;
    for (int i = x.ival; --i >= 0; )
      {
	if (x.words[i] != y.words[i])
	  return false;
      }
    return true;
  }

  /* Assumes this and obj are both canonicalized. */
  public boolean equals(Object obj)
  {
    if (! (obj instanceof BigInteger))
      return false;
    return equals(this, (BigInteger) obj);
  }

  private static BigInteger valueOf(String s, int radix)
       throws NumberFormatException
  {
    int len = s.length();
    // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
    // but slightly more expensive, for little practical gain.
    if (len <= 15 && radix <= 16)
      return valueOf(Long.parseLong(s, radix));

    int i, digit;
    boolean negative;
    byte[] bytes;
    char ch = s.charAt(0);
    if (ch == '-')
      {
        negative = true;
        i = 1;
        bytes = new byte[len - 1];
      }
    else
      {
        negative = false;
        i = 0;
        bytes = new byte[len];
      }
    int byte_len = 0;
    for ( ; i < len;  i++)
      {
        ch = s.charAt(i);
        digit = Character.digit(ch, radix);
        if (digit < 0)
          throw new NumberFormatException();
        bytes[byte_len++] = (byte) digit;
      }
    return valueOf(bytes, byte_len, negative, radix);
  }

  private static BigInteger valueOf(byte[] digits, int byte_len,
				    boolean negative, int radix)
  {
    int chars_per_word = MPN.chars_per_word(radix);
    int[] words = new int[byte_len / chars_per_word + 1];
    int size = MPN.set_str(words, digits, byte_len, radix);
    if (size == 0)
      return ZERO;
    if (words[size-1] < 0)
      words[size++] = 0;
    if (negative)
      negate(words, words, size);
    return make(words, size);
  }

  public double doubleValue()
  {
    if (words == null)
      return (double) ival;
    if (ival <= 2)
      return (double) longValue();
    if (isNegative())
      return neg(this).roundToDouble(0, true, false);
      return roundToDouble(0, false, false);
  }

  public float floatValue()
  {
    return (float) doubleValue();
  }

  /** Return true if any of the lowest n bits are one.
   * (false if n is negative).  */
  private boolean checkBits(int n)
  {
    if (n <= 0)
      return false;
    if (words == null)
      return n > 31 || ((ival & ((1 << n) - 1)) != 0);
    int i;
    for (i = 0; i < (n >> 5) ; i++)
      if (words[i] != 0)
	return true;
    return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
  }

  /** Convert a semi-processed BigInteger to double.
   * Number must be non-negative.  Multiplies by a power of two, applies sign,
   * and converts to double, with the usual java rounding.
   * @param exp power of two, positive or negative, by which to multiply
   * @param neg true if negative
   * @param remainder true if the BigInteger is the result of a truncating
   * division that had non-zero remainder.  To ensure proper rounding in
   * this case, the BigInteger must have at least 54 bits.  */
  private double roundToDouble(int exp, boolean neg, boolean remainder)
  {
    // Compute length.
    int il = bitLength();

    // Exponent when normalized to have decimal point directly after
    // leading one.  This is stored excess 1023 in the exponent bit field.
    exp += il - 1;

    // Gross underflow.  If exp == -1075, we let the rounding
    // computation determine whether it is minval or 0 (which are just
    // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
    // patterns).
    if (exp < -1075)
      return neg ? -0.0 : 0.0;

    // gross overflow
    if (exp > 1023)
      return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;

    // number of bits in mantissa, including the leading one.
    // 53 unless it's denormalized
    int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);

    // Get top ml + 1 bits.  The extra one is for rounding.
    long m;
    int excess_bits = il - (ml + 1);
    if (excess_bits > 0)
      m = ((words == null) ? ival >> excess_bits
	   : MPN.rshift_long(words, ival, excess_bits));
    else
      m = longValue() << (- excess_bits);

    // Special rounding for maxval.  If the number exceeds maxval by
    // any amount, even if it's less than half a step, it overflows.
    if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
      {
	if (remainder || checkBits(il - ml))
	  return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
	else
	  return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
      }

    // Normal round-to-even rule: round up if the bit dropped is a one, and
    // the bit above it or any of the bits below it is a one.
    if ((m & 1) == 1
	&& ((m & 2) == 2 || remainder || checkBits(excess_bits)))
      {
	m += 2;
	// Check if we overflowed the mantissa
	if ((m & (1L << 54)) != 0)
	  {
	    exp++;
	    // renormalize
	    m >>= 1;
	  }
	// Check if a denormalized mantissa was just rounded up to a
	// normalized one.
	else if (ml == 52 && (m & (1L << 53)) != 0)
	  exp++;
      }
	
    // Discard the rounding bit
    m >>= 1;

    long bits_sign = neg ? (1L << 63) : 0;
    exp += 1023;
    long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
    long bits_mant = m & ~(1L << 52);
    return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
  }

  /** Copy the abolute value of this into an array of words.
   * Assumes words.length >= (this.words == null ? 1 : this.ival).
   * Result is zero-extended, but need not be a valid 2's complement number.
   */
  private void getAbsolute(int[] words)
  {
    int len;
    if (this.words == null)
      {
	len = 1;
	words[0] = this.ival;
      }
    else
      {
	len = this.ival;
	for (int i = len;  --i >= 0; )
	  words[i] = this.words[i];
      }
    if (words[len - 1] < 0)
      negate(words, words, len);
    for (int i = words.length;  --i > len; )
      words[i] = 0;
  }

  /** Set dest[0:len-1] to the negation of src[0:len-1].
   * Return true if overflow (i.e. if src is -2**(32*len-1)).
   * Ok for src==dest. */
  private static boolean negate(int[] dest, int[] src, int len)
  {
    long carry = 1;
    boolean negative = src[len-1] < 0;
    for (int i = 0;  i < len;  i++)
      {
        carry += ((long) (~src[i]) & 0xffffffffL);
        dest[i] = (int) carry;
        carry >>= 32;
      }
    return (negative && dest[len-1] < 0);
  }

  /** Destructively set this to the negative of x.
   * It is OK if x==this.*/
  private void setNegative(BigInteger x)
  {
    int len = x.ival;
    if (x.words == null)
      {
	if (len == Integer.MIN_VALUE)
	  set(- (long) len);
	else
	  set(-len);
	return;
      }
    realloc(len + 1);
    if (negate(words, x.words, len))
      words[len++] = 0;
    ival = len;
  }

  /** Destructively negate this. */
  private void setNegative()
  {
    setNegative(this);
  }

  private static BigInteger abs(BigInteger x)
  {
    return x.isNegative() ? neg(x) : x;
  }

  public BigInteger abs()
  {
    return abs(this);
  }

  private static BigInteger neg(BigInteger x)
  {
    if (x.words == null && x.ival != Integer.MIN_VALUE)
      return valueOf(- x.ival);
    BigInteger result = new BigInteger(0);
    result.setNegative(x);
    return result.canonicalize();
  }

  public BigInteger negate()
  {
    return neg(this);
  }

  /** Calculates ceiling(log2(this < 0 ? -this : this+1))
   * See Common Lisp: the Language, 2nd ed, p. 361.
   */
  public int bitLength()
  {
    if (words == null)
      return MPN.intLength(ival);
      return MPN.intLength(words, ival);
  }

  public byte[] toByteArray()
  {
    // Determine number of bytes needed.  The method bitlength returns
    // the size without the sign bit, so add one bit for that and then
    // add 7 more to emulate the ceil function using integer math.
    byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
    int nbytes = bytes.length;

    int wptr = 0;
    int word;

    // Deal with words array until one word or less is left to process.
    // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
    while (nbytes > 4)
      {
	word = words[wptr++];
	for (int i = 4; i > 0; --i, word >>= 8)
          bytes[--nbytes] = (byte) word;
      }

    // Deal with the last few bytes.  If BigInteger is an int, use ival.
    word = (words == null) ? ival : words[wptr];
    for ( ; nbytes > 0; word >>= 8)
      bytes[--nbytes] = (byte) word;

    return bytes;
  }

  /** Return the boolean opcode (for bitOp) for swapped operands.
   * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
   */
  private static int swappedOp(int op)
  {
    return
    "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
    .charAt(op);
  }

  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
  private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
  {
    switch (op)
      {
        case 0:  return ZERO;
        case 1:  return x.and(y);
        case 3:  return x;
        case 5:  return y;
        case 15: return valueOf(-1);
      }
    BigInteger result = new BigInteger();
    setBitOp(result, op, x, y);
    return result.canonicalize();
  }

  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
  private static void setBitOp(BigInteger result, int op,
			       BigInteger x, BigInteger y)
  {
    if (y.words == null) ;
    else if (x.words == null || x.ival < y.ival)
      {
	BigInteger temp = x;  x = y;  y = temp;
	op = swappedOp(op);
      }
    int xi;
    int yi;
    int xlen, ylen;
    if (y.words == null)
      {
	yi = y.ival;
	ylen = 1;
      }
    else
      {
	yi = y.words[0];
	ylen = y.ival;
      }
    if (x.words == null)
      {
	xi = x.ival;
	xlen = 1;
      }
    else
      {
	xi = x.words[0];
	xlen = x.ival;
      }
    if (xlen > 1)
      result.realloc(xlen);
    int[] w = result.words;
    int i = 0;
    // Code for how to handle the remainder of x.
    // 0:  Truncate to length of y.
    // 1:  Copy rest of x.
    // 2:  Invert rest of x.
    int finish = 0;
    int ni;
    switch (op)
      {
      case 0:  // clr
	ni = 0;
	break;
      case 1: // and
	for (;;)
	  {
	    ni = xi & yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 1;
	break;
      case 2: // andc2
	for (;;)
	  {
	    ni = xi & ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 1;
	break;
      case 3:  // copy x
	ni = xi;
	finish = 1;  // Copy rest
	break;
      case 4: // andc1
	for (;;)
	  {
	    ni = ~xi & yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 2;
	break;
      case 5: // copy y
	for (;;)
	  {
	    ni = yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	break;
      case 6:  // xor
	for (;;)
	  {
	    ni = xi ^ yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	finish = yi < 0 ? 2 : 1;
	break;
      case 7:  // ior
	for (;;)
	  {
	    ni = xi | yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 1;
	break;
      case 8:  // nor
	for (;;)
	  {
	    ni = ~(xi | yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0)  finish = 2;
	break;
      case 9:  // eqv [exclusive nor]
	for (;;)
	  {
	    ni = ~(xi ^ yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	finish = yi >= 0 ? 2 : 1;
	break;
      case 10:  // c2
	for (;;)
	  {
	    ni = ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	break;
      case 11:  // orc2
	for (;;)
	  {
	    ni = xi | ~yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0)  finish = 1;
	break;
      case 12:  // c1
	ni = ~xi;
	finish = 2;
	break;
      case 13:  // orc1
	for (;;)
	  {
	    ni = ~xi | yi;
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi >= 0) finish = 2;
	break;
      case 14:  // nand
	for (;;)
	  {
	    ni = ~(xi & yi);
	    if (i+1 >= ylen) break;
	    w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
	  }
	if (yi < 0) finish = 2;
	break;
      default:
      case 15:  // set
	ni = -1;
	break;
      }
    // Here i==ylen-1; w[0]..w[i-1] have the correct result;
    // and ni contains the correct result for w[i+1].
    if (i+1 == xlen)
      finish = 0;
    switch (finish)
      {
      case 0:
	if (i == 0 && w == null)
	  {
	    result.ival = ni;
	    return;
	  }
	w[i++] = ni;
	break;
      case 1:  w[i] = ni;  while (++i < xlen)  w[i] = x.words[i];  break;
      case 2:  w[i] = ni;  while (++i < xlen)  w[i] = ~x.words[i];  break;
      }
    result.ival = i;
  }

  /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
  private static BigInteger and(BigInteger x, int y)
  {
    if (x.words == null)
      return valueOf(x.ival & y);
    if (y >= 0)
      return valueOf(x.words[0] & y);
    int len = x.ival;
    int[] words = new int[len];
    words[0] = x.words[0] & y;
    while (--len > 0)
      words[len] = x.words[len];
    return make(words, x.ival);
  }

  /** Return the logical (bit-wise) "and" of two BigIntegers. */
  public BigInteger and(BigInteger y)
  {
    if (y.words == null)
      return and(this, y.ival);
    else if (words == null)
      return and(y, ival);

    BigInteger x = this;
    if (ival < y.ival)
      {
        BigInteger temp = this;  x = y;  y = temp;
      }
    int i;
    int len = y.isNegative() ? x.ival : y.ival;
    int[] words = new int[len];
    for (i = 0;  i < y.ival;  i++)
      words[i] = x.words[i] & y.words[i];
    for ( ; i < len;  i++)
      words[i] = x.words[i];
    return make(words, len);
  }

  /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
  public BigInteger or(BigInteger y)
  {
    return bitOp(7, this, y);
  }

  /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
  public BigInteger xor(BigInteger y)
  {
    return bitOp(6, this, y);
  }

  /** Return the logical (bit-wise) negation of a BigInteger. */
  public BigInteger not()
  {
    return bitOp(12, this, ZERO);
  }

  public BigInteger andNot(BigInteger val)
  {
    return and(val.not());
  }

  public BigInteger clearBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return and(ONE.shiftLeft(n).not());
  }

  public BigInteger setBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return or(ONE.shiftLeft(n));
  }

  public boolean testBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return !and(ONE.shiftLeft(n)).isZero();
  }

  public BigInteger flipBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    return xor(ONE.shiftLeft(n));
  }

  public int getLowestSetBit()
  {
    if (isZero())
      return -1;

    if (words == null)
      return MPN.findLowestBit(ival);
    else
      return MPN.findLowestBit(words);
  }

  // bit4count[I] is number of '1' bits in I.
  private static final byte[] bit4_count = { 0, 1, 1, 2,  1, 2, 2, 3,
					     1, 2, 2, 3,  2, 3, 3, 4};

  private static int bitCount(int i)
  {
    int count = 0;
    while (i != 0)
      {
	count += bit4_count[i & 15];
	i >>>= 4;
      }
    return count;
  }

  private static int bitCount(int[] x, int len)
  {
    int count = 0;
    while (--len >= 0)
      count += bitCount(x[len]);
    return count;
  }

  /** Count one bits in a BigInteger.
   * If argument is negative, count zero bits instead. */
  public int bitCount()
  {
    int i, x_len;
    int[] x_words = words;
    if (x_words == null)
      {
	x_len = 1;
	i = bitCount(ival);
      }
    else
      {
	x_len = ival;
	i = bitCount(x_words, x_len);
      }
    return isNegative() ? x_len * 32 - i : i;
  }

  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    s.defaultReadObject();
    if (magnitude.length == 0 || signum == 0)
      {
        this.ival = 0;
        this.words = null;
      }
    else
      {
        words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
        BigInteger result = make(words, words.length);
        this.ival = result.ival;
        this.words = result.words;        
      }    
  }

  private void writeObject(ObjectOutputStream s)
    throws IOException, ClassNotFoundException
  {
    signum = signum();
    magnitude = signum == 0 ? new byte[0] : toByteArray();
    s.defaultWriteObject();
  }
}