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/java/math/BigInteger.java

blob: 738680a42c42c0054109dd8e2bbc8c1f3c672f24 (plain)

FTIM2_GPCM_TCH(0x8) | \ FTIM2_GPCM_TWP(0x1f)) #define CONFIG_SYS_CS3_FTIM3 0x0 /* NAND Flash on IFC */ #define CONFIG_NAND_FSL_IFC #define CONFIG_SYS_NAND_BASE 0xff800000 #define CONFIG_SYS_NAND_BASE_PHYS (0xf00000000ull | CONFIG_SYS_NAND_BASE) #define CONFIG_SYS_NAND_CSPR_EXT (0xf) #define CONFIG_SYS_NAND_CSPR (CSPR_PHYS_ADDR(CONFIG_SYS_NAND_BASE_PHYS) \ | CSPR_PORT_SIZE_8 /* Port Size = 8 bit */ \ | CSPR_MSEL_NAND /* MSEL = NAND */ \ | CSPR_V) #define CONFIG_SYS_NAND_AMASK IFC_AMASK(64*1024) #define CONFIG_SYS_NAND_CSOR (CSOR_NAND_ECC_ENC_EN /* ECC on encode */ \ | CSOR_NAND_ECC_DEC_EN /* ECC on decode */ \ | CSOR_NAND_ECC_MODE_4 /* 4-bit ECC */ \ | CSOR_NAND_RAL_3 /* RAL = 2Byes */ \ | CSOR_NAND_PGS_2K /* Page Size = 2K */ \ | CSOR_NAND_SPRZ_64/* Spare size = 64 */ \ | CSOR_NAND_PB(64)) /*Pages Per Block = 64*/ #define CONFIG_SYS_NAND_ONFI_DETECTION /* ONFI NAND Flash mode0 Timing Params */ #define CONFIG_SYS_NAND_FTIM0 (FTIM0_NAND_TCCST(0x07) | \ FTIM0_NAND_TWP(0x18) | \ FTIM0_NAND_TWCHT(0x07) | \ FTIM0_NAND_TWH(0x0a)) #define CONFIG_SYS_NAND_FTIM1 (FTIM1_NAND_TADLE(0x32) | \ FTIM1_NAND_TWBE(0x39) | \ FTIM1_NAND_TRR(0x0e) | \ FTIM1_NAND_TRP(0x18)) #define CONFIG_SYS_NAND_FTIM2 (FTIM2_NAND_TRAD(0x0f) | \ FTIM2_NAND_TREH(0x0a) | \ FTIM2_NAND_TWHRE(0x1e)) #define CONFIG_SYS_NAND_FTIM3 0x0 #define CONFIG_SYS_NAND_DDR_LAW 11 #define CONFIG_SYS_NAND_BASE_LIST { CONFIG_SYS_NAND_BASE } #define CONFIG_SYS_MAX_NAND_DEVICE 1 #define CONFIG_SYS_NAND_BLOCK_SIZE (128 * 1024) #define CONFIG_SYS_NAND_MAX_OOBFREE 2 #define CONFIG_SYS_NAND_MAX_ECCPOS 256 #if defined(CONFIG_NAND) #define CONFIG_SYS_CSPR0_EXT CONFIG_SYS_NAND_CSPR_EXT #define CONFIG_SYS_CSPR0 CONFIG_SYS_NAND_CSPR #define CONFIG_SYS_AMASK0 CONFIG_SYS_NAND_AMASK #define CONFIG_SYS_CSOR0 CONFIG_SYS_NAND_CSOR #define CONFIG_SYS_CS0_FTIM0 CONFIG_SYS_NAND_FTIM0 #define CONFIG_SYS_CS0_FTIM1 CONFIG_SYS_NAND_FTIM1 #define CONFIG_SYS_CS0_FTIM2 CONFIG_SYS_NAND_FTIM2 #define CONFIG_SYS_CS0_FTIM3 CONFIG_SYS_NAND_FTIM3 #define CONFIG_SYS_CSPR1_EXT CONFIG_SYS_NOR0_CSPR_EXT #define CONFIG_SYS_CSPR1 CONFIG_SYS_NOR0_CSPR #define CONFIG_SYS_AMASK1 CONFIG_SYS_NOR_AMASK #define CONFIG_SYS_CSOR1 CONFIG_SYS_NOR_CSOR #define CONFIG_SYS_CS1_FTIM0 CONFIG_SYS_NOR_FTIM0 #define CONFIG_SYS_CS1_FTIM1 CONFIG_SYS_NOR_FTIM1 #define CONFIG_SYS_CS1_FTIM2 CONFIG_SYS_NOR_FTIM2 #define CONFIG_SYS_CS1_FTIM3 CONFIG_SYS_NOR_FTIM3 #define CONFIG_SYS_CSPR2_EXT CONFIG_SYS_NOR1_CSPR_EXT #define CONFIG_SYS_CSPR2 CONFIG_SYS_NOR1_CSPR #define CONFIG_SYS_AMASK2 CONFIG_SYS_NOR_AMASK #define CONFIG_SYS_CSOR2 CONFIG_SYS_NOR_CSOR #define CONFIG_SYS_CS2_FTIM0 CONFIG_SYS_NOR_FTIM0 #define CONFIG_SYS_CS2_FTIM1 CONFIG_SYS_NOR_FTIM1 #define CONFIG_SYS_CS2_FTIM2 CONFIG_SYS_NOR_FTIM2 #define CONFIG_SYS_CS2_FTIM3 CONFIG_SYS_NOR_FTIM3 #else #define CONFIG_SYS_CSPR0_EXT CONFIG_SYS_NOR0_CSPR_EXT #define CONFIG_SYS_CSPR0 CONFIG_SYS_NOR0_CSPR #define CONFIG_SYS_AMASK0 CONFIG_SYS_NOR_AMASK #define CONFIG_SYS_CSOR0 CONFIG_SYS_NOR_CSOR #define CONFIG_SYS_CS0_FTIM0 CONFIG_SYS_NOR_FTIM0 #define CONFIG_SYS_CS0_FTIM1 CONFIG_SYS_NOR_FTIM1 #define CONFIG_SYS_CS0_FTIM2 CONFIG_SYS_NOR_FTIM2 #define CONFIG_SYS_CS0_FTIM3 CONFIG_SYS_NOR_FTIM3 #define CONFIG_SYS_CSPR1_EXT CONFIG_SYS_NOR1_CSPR_EXT #define CONFIG_SYS_CSPR1 CONFIG_SYS_NOR1_CSPR #define CONFIG_SYS_AMASK1 CONFIG_SYS_NOR_AMASK #define CONFIG_SYS_CSOR1 CONFIG_SYS_NOR_CSOR #define CONFIG_SYS_CS1_FTIM0 CONFIG_SYS_NOR_FTIM0 #define CONFIG_SYS_CS1_FTIM1 CONFIG_SYS_NOR_FTIM1 #define CONFIG_SYS_CS1_FTIM2 CONFIG_SYS_NOR_FTIM2 #define CONFIG_SYS_CS1_FTIM3 CONFIG_SYS_NOR_FTIM3 #define CONFIG_SYS_CSPR2_EXT CONFIG_SYS_NAND_CSPR_EXT #define CONFIG_SYS_CSPR2 CONFIG_SYS_NAND_CSPR #define CONFIG_SYS_AMASK2 CONFIG_SYS_NAND_AMASK #define CONFIG_SYS_CSOR2 CONFIG_SYS_NAND_CSOR #define CONFIG_SYS_CS2_FTIM0 CONFIG_SYS_NAND_FTIM0 #define CONFIG_SYS_CS2_FTIM1 CONFIG_SYS_NAND_FTIM1 #define CONFIG_SYS_CS2_FTIM2 CONFIG_SYS_NAND_FTIM2 #define CONFIG_SYS_CS2_FTIM3 CONFIG_SYS_NAND_FTIM3 #endif #if defined(CONFIG_RAMBOOT_PBL) #define CONFIG_SYS_RAMBOOT #endif /* I2C */ #define CONFIG_SYS_FSL_I2C_SPEED 100000 /* I2C speed */ #define CONFIG_SYS_FSL_I2C2_SPEED 100000 /* I2C2 speed */ #define I2C_MUX_PCA_ADDR_PRI 0x77 /* I2C bus multiplexer,primary */ #define I2C_MUX_PCA_ADDR_SEC 0x76 /* I2C bus multiplexer,secondary */ #define I2C_MUX_CH_DEFAULT 0x8 #define I2C_MUX_CH_VOL_MONITOR 0xa #define I2C_MUX_CH_VSC3316_FS 0xc #define I2C_MUX_CH_VSC3316_BS 0xd /* Voltage monitor on channel 2*/ #define I2C_VOL_MONITOR_ADDR 0x40 #define I2C_VOL_MONITOR_BUS_V_OFFSET 0x2 #define I2C_VOL_MONITOR_BUS_V_OVF 0x1 #define I2C_VOL_MONITOR_BUS_V_SHIFT 3 /* VSC Crossbar switches */ #define CONFIG_VSC_CROSSBAR #define VSC3316_FSM_TX_ADDR 0x70 #define VSC3316_FSM_RX_ADDR 0x71 /* * RapidIO */ /* * for slave u-boot IMAGE instored in master memory space, * PHYS must be aligned based on the SIZE */ #define CONFIG_SRIO_PCIE_BOOT_IMAGE_MEM_PHYS 0xfef200000ull #define CONFIG_SRIO_PCIE_BOOT_IMAGE_MEM_BUS1 0xfff00000ull #define CONFIG_SRIO_PCIE_BOOT_IMAGE_SIZE 0x100000 /* 1M */ #define CONFIG_SRIO_PCIE_BOOT_IMAGE_MEM_BUS2 0x3fff00000ull /* * for slave UCODE and ENV instored in master memory space, * PHYS must be aligned based on the SIZE */ #define CONFIG_SRIO_PCIE_BOOT_UCODE_ENV_MEM_PHYS 0xfef100000ull #define CONFIG_SRIO_PCIE_BOOT_UCODE_ENV_MEM_BUS 0x3ffe00000ull #define CONFIG_SRIO_PCIE_BOOT_UCODE_ENV_SIZE 0x40000 /* 256K */ /* slave core release by master*/ #define CONFIG_SRIO_PCIE_BOOT_BRR_OFFSET 0xe00e4 #define CONFIG_SRIO_PCIE_BOOT_RELEASE_MASK 0x00000001 /* release core 0 */ /* * SRIO_PCIE_BOOT - SLAVE */ #ifdef CONFIG_SRIO_PCIE_BOOT_SLAVE #define CONFIG_SYS_SRIO_PCIE_BOOT_UCODE_ENV_ADDR 0xFFE00000 #define CONFIG_SYS_SRIO_PCIE_BOOT_UCODE_ENV_ADDR_PHYS \ (0x300000000ull | CONFIG_SYS_SRIO_PCIE_BOOT_UCODE_ENV_ADDR) #endif /* * eSPI - Enhanced SPI */ #define CONFIG_SF_DEFAULT_SPEED 10000000 #define CONFIG_SF_DEFAULT_MODE 0 /* Qman/Bman */ #ifndef CONFIG_NOBQFMAN #define CONFIG_SYS_DPAA_QBMAN /* Support Q/Bman */ #define CONFIG_SYS_BMAN_NUM_PORTALS 50 #define CONFIG_SYS_BMAN_MEM_BASE 0xf4000000 #define CONFIG_SYS_BMAN_MEM_PHYS 0xff4000000ull #define CONFIG_SYS_BMAN_MEM_SIZE 0x02000000 #define CONFIG_SYS_BMAN_SP_CENA_SIZE 0x4000 #define CONFIG_SYS_BMAN_SP_CINH_SIZE 0x1000 #define CONFIG_SYS_BMAN_CENA_BASE CONFIG_SYS_BMAN_MEM_BASE #define CONFIG_SYS_BMAN_CENA_SIZE (CONFIG_SYS_BMAN_MEM_SIZE >> 1) #define CONFIG_SYS_BMAN_CINH_BASE (CONFIG_SYS_BMAN_MEM_BASE + \ CONFIG_SYS_BMAN_CENA_SIZE) #define CONFIG_SYS_BMAN_CINH_SIZE (CONFIG_SYS_BMAN_MEM_SIZE >> 1) #define CONFIG_SYS_BMAN_SWP_ISDR_REG 0xE08 #define CONFIG_SYS_QMAN_NUM_PORTALS 50 #define CONFIG_SYS_QMAN_MEM_BASE 0xf6000000 #define CONFIG_SYS_QMAN_MEM_PHYS 0xff6000000ull #define CONFIG_SYS_QMAN_MEM_SIZE 0x02000000 #define CONFIG_SYS_QMAN_SP_CENA_SIZE 0x4000 #define CONFIG_SYS_QMAN_SP_CINH_SIZE 0x1000 #define CONFIG_SYS_QMAN_CENA_BASE CONFIG_SYS_QMAN_MEM_BASE #define CONFIG_SYS_QMAN_CENA_SIZE (CONFIG_SYS_QMAN_MEM_SIZE >> 1) #define CONFIG_SYS_QMAN_CINH_BASE (CONFIG_SYS_QMAN_MEM_BASE + \ CONFIG_SYS_QMAN_CENA_SIZE) #define CONFIG_SYS_QMAN_CINH_SIZE (CONFIG_SYS_QMAN_MEM_SIZE >> 1) #define CONFIG_SYS_QMAN_SWP_ISDR_REG 0xE08 #define CONFIG_SYS_DPAA_FMAN #define CONFIG_SYS_DPAA_PME #define CONFIG_SYS_PMAN #define CONFIG_SYS_DPAA_DCE #define CONFIG_SYS_DPAA_RMAN #define CONFIG_SYS_INTERLAKEN /* Default address of microcode for the Linux Fman driver */ #if defined(CONFIG_SPIFLASH) /* * env is stored at 0x100000, sector size is 0x10000, ucode is stored after * env, so we got 0x110000. */ #define CONFIG_SYS_QE_FW_IN_SPIFLASH #define CONFIG_SYS_FMAN_FW_ADDR 0x110000 #elif defined(CONFIG_SDCARD) /* * PBL SD boot image should stored at 0x1000(8 blocks), the size of the image is * about 1MB (2048 blocks), Env is stored after the image, and the env size is * 0x2000 (16 blocks), 8 + 2048 + 16 = 2072, enlarge it to 2080. */ #define CONFIG_SYS_QE_FMAN_FW_IN_MMC #define CONFIG_SYS_FMAN_FW_ADDR (512 * 0x820) #elif defined(CONFIG_NAND) #define CONFIG_SYS_QE_FMAN_FW_IN_NAND #define CONFIG_SYS_FMAN_FW_ADDR (11 * CONFIG_SYS_NAND_BLOCK_SIZE) #elif defined(CONFIG_SRIO_PCIE_BOOT_SLAVE) /* * Slave has no ucode locally, it can fetch this from remote. When implementing * in two corenet boards, slave's ucode could be stored in master's memory * space, the address can be mapped from slave TLB->slave LAW-> * slave SRIO or PCIE outbound window->master inbound window-> * master LAW->the ucode address in master's memory space. */ #define CONFIG_SYS_QE_FMAN_FW_IN_REMOTE #define CONFIG_SYS_FMAN_FW_ADDR 0xFFE00000 #else #define CONFIG_SYS_QE_FMAN_FW_IN_NOR #define CONFIG_SYS_FMAN_FW_ADDR 0xEFF00000 #endif #define CONFIG_SYS_QE_FMAN_FW_LENGTH 0x10000 #define CONFIG_SYS_FDT_PAD (0x3000 + CONFIG_SYS_QE_FMAN_FW_LENGTH) #endif /* CONFIG_NOBQFMAN */ #ifdef CONFIG_SYS_DPAA_FMAN #define CONFIG_FMAN_ENET #define CONFIG_PHYLIB_10G #define CONFIG_PHY_VITESSE #define CONFIG_PHY_TERANETICS #define SGMII_CARD_PORT1_PHY_ADDR 0x1C #define SGMII_CARD_PORT2_PHY_ADDR 0x1D #define SGMII_CARD_PORT3_PHY_ADDR 0x1E #define SGMII_CARD_PORT4_PHY_ADDR 0x1F #define FM1_10GEC1_PHY_ADDR 0x0 #define FM1_10GEC2_PHY_ADDR 0x1 #define FM2_10GEC1_PHY_ADDR 0x2 #define FM2_10GEC2_PHY_ADDR 0x3 #endif /* SATA */ #ifdef CONFIG_FSL_SATA_V2 #define CONFIG_SYS_SATA_MAX_DEVICE 2 #define CONFIG_SATA1 #define CONFIG_SYS_SATA1 CONFIG_SYS_MPC85xx_SATA1_ADDR #define CONFIG_SYS_SATA1_FLAGS FLAGS_DMA #define CONFIG_SATA2 #define CONFIG_SYS_SATA2 CONFIG_SYS_MPC85xx_SATA2_ADDR #define CONFIG_SYS_SATA2_FLAGS FLAGS_DMA #define CONFIG_LBA48 #endif #ifdef CONFIG_FMAN_ENET #define CONFIG_MII /* MII PHY management */ #define CONFIG_ETHPRIME "FM1@DTSEC1" #endif /* * USB */ #define CONFIG_USB_EHCI_FSL #define CONFIG_EHCI_HCD_INIT_AFTER_RESET #define CONFIG_HAS_FSL_DR_USB #ifdef CONFIG_MMC #define CONFIG_FSL_ESDHC #define CONFIG_SYS_FSL_ESDHC_ADDR CONFIG_SYS_MPC85xx_ESDHC_ADDR #define CONFIG_SYS_FSL_ESDHC_BROKEN_TIMEOUT #define CONFIG_SYS_FSL_MMC_HAS_CAPBLT_VS33 #define CONFIG_ESDHC_DETECT_QUIRK \ (!(readb(QIXIS_BASE + QIXIS_BRDCFG5) & QIXIS_MUX_SDHC) || \ IS_SVR_REV(get_svr(), 1, 0)) #define CONFIG_ESDHC_DETECT_8_BIT_QUIRK \ (!(readb(QIXIS_BASE + QIXIS_BRDCFG5) & QIXIS_MUX_SDHC_WIDTH8)) #endif #define __USB_PHY_TYPE utmi /* * T4240 has 3 DDR controllers. Default to 3-way interleaving. It can be * 3way_1KB, 3way_4KB, 3way_8KB. T4160 has 2 DDR controllers. Default to 2-way * interleaving. It can be cacheline, page, bank, superbank. * See doc/README.fsl-ddr for details. */ #ifdef CONFIG_ARCH_T4240 #define CTRL_INTLV_PREFERED 3way_4KB #else #define CTRL_INTLV_PREFERED cacheline #endif #define CONFIG_EXTRA_ENV_SETTINGS \ "hwconfig=fsl_ddr:" \ "ctlr_intlv=" __stringify(CTRL_INTLV_PREFERED) "," \ "bank_intlv=auto;" \ "usb1:dr_mode=host,phy_type=" __stringify(__USB_PHY_TYPE) "\0"\ "netdev=eth0\0" \ "uboot=" __stringify(CONFIG_UBOOTPATH) "\0" \ "ubootaddr=" __stringify(CONFIG_SYS_TEXT_BASE) "\0" \ "tftpflash=tftpboot $loadaddr $uboot && " \ "protect off $ubootaddr +$filesize && " \ "erase $ubootaddr +$filesize && " \ "cp.b $loadaddr $ubootaddr $filesize && " \ "protect on $ubootaddr +$filesize && " \ "cmp.b $loadaddr $ubootaddr $filesize\0" \ "consoledev=ttyS0\0" \ "ramdiskaddr=2000000\0" \ "ramdiskfile=t4240qds/ramdisk.uboot\0" \ "fdtaddr=1e00000\0" \ "fdtfile=t4240qds/t4240qds.dtb\0" \ "bdev=sda3\0" #define CONFIG_HVBOOT \ "setenv bootargs config-addr=0x60000000; " \ "bootm 0x01000000 - 0x00f00000" #define CONFIG_ALU \ "setenv bootargs root=/dev/$bdev rw " \ "console=$consoledev,$baudrate $othbootargs;" \ "cpu 1 release 0x01000000 - - -;" \ "cpu 2 release 0x01000000 - - -;" \ "cpu 3 release 0x01000000 - - -;" \ "cpu 4 release 0x01000000 - - -;" \ "cpu 5 release 0x01000000 - - -;" \ "cpu 6 release 0x01000000 - - -;" \ "cpu 7 release 0x01000000 - - -;" \ "go 0x01000000" #define CONFIG_LINUX \ "setenv bootargs root=/dev/ram rw " \ "console=$consoledev,$baudrate $othbootargs;" \ "setenv ramdiskaddr 0x02000000;" \ "setenv fdtaddr 0x00c00000;" \ "setenv loadaddr 0x1000000;" \ "bootm $loadaddr $ramdiskaddr $fdtaddr" #define CONFIG_HDBOOT \ "setenv bootargs root=/dev/$bdev rw " \ "console=$consoledev,$baudrate $othbootargs;" \ "tftp $loadaddr $bootfile;" \ "tftp $fdtaddr $fdtfile;" \ "bootm $loadaddr - $fdtaddr" #define CONFIG_NFSBOOTCOMMAND \ "setenv bootargs root=/dev/nfs rw " \ "nfsroot=$serverip:$rootpath " \ "ip=$ipaddr:$serverip:$gatewayip:$netmask:$hostname:$netdev:off " \ "console=$consoledev,$baudrate $othbootargs;" \ "tftp $loadaddr $bootfile;" \ "tftp $fdtaddr $fdtfile;" \ "bootm $loadaddr - $fdtaddr" #define CONFIG_RAMBOOTCOMMAND \ "setenv bootargs root=/dev/ram rw " \ "console=$consoledev,$baudrate $othbootargs;" \ "tftp $ramdiskaddr $ramdiskfile;" \ "tftp $loadaddr $bootfile;" \ "tftp $fdtaddr $fdtfile;" \ "bootm $loadaddr $ramdiskaddr $fdtaddr" #define CONFIG_BOOTCOMMAND CONFIG_LINUX #include <asm/fsl_secure_boot.h> #endif /* __CONFIG_H */

generated by cgit v1.1 at 2026-02-27 05:21:39 +0000

// BigInteger.java -- an arbitrary-precision integer

/* Copyright (C) 1999, 2000  Free Software Foundation

   This file is part of libgcj.

This software is copyrighted work licensed under the terms of the
Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for
details.  */

package java.math;
import gnu.gcj.math.*;
import java.util.Random;

/**
 * @author Warren Levy <warrenl@cygnus.com>
 * @date December 20, 1999.
 */

/**
 * 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).
 *
 * Status:  Believed complete and correct.
 */

public class BigInteger extends Number implements Comparable
{
  /** 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 int ival;
  private int[] words;


  /** We pre-allocate integers in the range minFixNum..maxFixNum. */
  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);
  }

  // JDK1.2
  public static final BigInteger ZERO = smallFixNums[-minFixNum];

  // JDK1.2
  public static final BigInteger ONE = smallFixNums[1 - 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 };

  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();

    // Result is always positive so tack on an extra zero word, it will be
    // canonicalized out later if necessary.
    int nwords = numBits / 32 + 2;
    words = new int[nwords];
    words[--nwords] = 0;
    words[--nwords] = rnd.nextInt() >>> (numBits % 32);
    while (--nwords >= 0)
      words[nwords] = rnd.nextInt();

    BigInteger result = make(words, words.length);
    this.ival = result.ival;
    this.words = result.words;
  }

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

    // Keep going until we find a probable prime.
    while (true)
      {
	if (isProbablePrime(certainty))
	  return;

	BigInteger next = new BigInteger(bitLength, rnd);
	this.ival = next.ival;
	this.words = next.words;
      }
  }

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

  // FIXME: Could simply rename 'make' method above as valueOf while
  // changing all instances of 'make'.  Don't do this until this class
  // is done as the Kawa class this is based on has 'make' methods
  // with other parameters; wait to see if they are used in BigInteger.
  public static BigInteger valueOf(long val)
  {
    return make(val);
  }

  /** 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 make(len);
    len = BigInteger.wordsNeeded(words, len);
    if (len <= 1)
      return len == 0 ? ZERO : make(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 + 3) / 4 + 1];
    int nwords = words.length;

    // For simplicity, tack on an extra word of sign at the front,
    // it will be canonicalized out later. */
    words[--nwords] = sign;

    // 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) | (((int) bytes[bptr]) & 0xff);
    words[--nwords] = word;

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

  /** Allocate a new non-shared BigInteger.
   * @param nwords number of words to allocate
   */
  private static BigInteger alloc(int nwords)
  {
    if (nwords <= 1)
      return new BigInteger();
    BigInteger result = new BigInteger();
    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 final boolean isNegative()
  {
    return (words == null ? ival : words[ival - 1]) < 0;
  }

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

  // JDK1.2
  public int compareTo(Object obj)
  {
    if (obj instanceof BigInteger)
      return compareTo(this, (BigInteger) obj);
    throw new ClassCastException();
  }

  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 final boolean isOdd()
  {
    int low = words == null ? ival : words[0];
    return (low & 1) != 0;
  }

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

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

  private final boolean isMinusOne()
  {
    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[(int) ival - minFixNum];
    return this;
  }

  /** Add two ints, yielding a BigInteger. */
  private static final BigInteger add(int x, int y)
  {
    return BigInteger.make((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 final void setAdd(int y)
  {
    setAdd(this, y);
  }

  /** Destructively set the value of this to a long. */
  private final 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 final void set(int[] words, int length)
  {
    this.ival = length;
    this.words = words;
  }

  /** Destructively set the value of this to that of y. */
  private final 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 BigInteger.make((long) k * (long) y.ival + (long) x.ival);
    if (k != 1)
      {
	if (k == -1)
	  y = BigInteger.neg(y);
	else
	  y = BigInteger.times(y, BigInteger.make(k));
      }
    if (x.words == null)
      return BigInteger.add(y, x.ival);
    if (y.words == null)
      return BigInteger.add(x, y.ival);
    // Both are big
    int len;
    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 final 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 BigInteger.make((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 final 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(BigInteger.make(x), BigInteger.make(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(BigInteger.make(x), BigInteger.make(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;
	if (remainder != null || rounding_mode != TRUNCATE)
	  {
	    if (nshift == 0)
	      System.arraycopy(xwords, 0, ywords, 0, rlen);
	    else
	      MPN.rshift(ywords, xwords, 0, rlen, nshift);
	  }

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

    // 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 power for BigInteger exponents.
   * @param y exponent assumed to be non-negative. */
  private BigInteger pow(BigInteger y)
  {
    if (isOne())
      return this;
    if (isMinusOne())
      return y.isOdd () ? this : ONE;
    if (y.words == null && y.ival >= 0)
      return pow(y.ival);

    // Assume exponent is non-negative.
    if (isZero())
      return this;

    // Implemented by repeated squaring and multiplication.
    BigInteger pow2 = this;
    BigInteger r = null;
    for (;;)  // for (i = 0;  ; i++)
      {
        // pow2 == x**(2**i)
        // prod = x**(sum(j=0..i-1, (y>>j)&1))
        if (y.isOdd())
          r = r == null ? pow2 : times(r, pow2);  // r *= pow2
        y = BigInteger.shift(y, -1);
        if (y.isZero())
          break;
        // pow2 *= pow2;
        pow2 = times(pow2, pow2);
      }
    return r == null ? ONE : r;
  }

  /** 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;
	else
	  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 final int[] euclidInv(int a, int b, int prevDiv)
  {
    // Storage for return values, plus one slot for a temp int (see below).
    int[] xy;

    if (b == 0)
      throw new ArithmeticException("not invertible");
    else if (b == 1)
      {
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
        xy = new int[3];
	xy[0] = -prevDiv;
	xy[1] = 1;
	return xy;
      }

    xy = euclidInv(b, a % b, a / b);	// Recursion happens here.

    // xy[2] is just temp storage for intermediate results in the following
    // calculation.  This saves us a bit of space over having an int
    // allocated at every level of this recursive method.
    xy[2] = xy[0];
    xy[0] = xy[2] * -prevDiv + xy[1];
    xy[1] = xy[2];
    return xy;
  }

  private static final BigInteger[]
    euclidInv(BigInteger a, BigInteger b, BigInteger prevDiv)
  {
    // FIXME: This method could be more efficient memory-wise and should be
    // modified as such since it is recursive.

    // Storage for return values, plus one slot for a temp int (see below).
    BigInteger[] xy;

    if (b.isZero())
      throw new ArithmeticException("not invertible");
    else if (b.isOne())
      {
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
        xy = new BigInteger[3];
	xy[0] = neg(prevDiv);
	xy[1] = ONE;
	return xy;
      }

    // 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 = new BigInteger[3];
	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);
        xy = euclidInv(b, rem, quot);
      }

    // xy[2] is just temp storage for intermediate results in the following
    // calculation.  This saves us a bit of space over having a BigInteger
    // allocated at every level of this recursive method.
    xy[2] = xy[0];
    xy[0] = add(xy[1], times(xy[2], prevDiv), -1);
    xy[1] = xy[2];
    return xy;
  }

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

    // Degenerate cases.
    if (y.isOne())
      return ZERO;
    else 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();
    int xval = ival;
    int yval = y.ival;
    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.
	if (words != null || isNegative())
	  xval = mod(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
      {
	BigInteger x = this;

	// As above, force this to be a positive value via modulo math.
	if (isNegative())
	  x = mod(y);

	// Swap values so x > y.
	if (x.compareTo(y) < 0)
	  {
	    BigInteger tmp = x; x = y; y = tmp;
	    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);
	result = euclidInv(y, rem, quot)[swapped ? 0 : 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);
    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 modulos 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, t, u;
    int i;

    s = ONE;
    t = this;
    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 final int gcd(int a, int b)
  {
    // Euclid's algorithm, copied from libg++.
    if (b > a)
      {
	int tmp = a; a = b; b = tmp;
      }
    for(;;)
      {
	if (b == 0)
	  return a;
	else if (b == 1)
	  return b;
	else
	  {
	    int 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 BigInteger.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 BigInteger.make(BigInteger.gcd(xval, yval));
	  }
	xval = 1;
      }
    if (y.words == null)
      {
	if (yval == 0)
	  return BigInteger.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();
  }

  public boolean isProbablePrime(int certainty)
  {
    /** 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 and assure the number is odd.
    for (int i = 0; i < primes.length; i++)
      {
	if (words == null && ival == primes[i])
	  return true;
        if (remainder(make(primes[i])).isZero())
	  return false;
      }

    // Now perform the Rabin-Miller test.
    // NB: I know that this can be simplified programatically, but
    // I have tried to keep it as close as possible to the algorithm
    // as written in the Schneier book for reference purposes.

    // 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(make(2L << b - 1));

    Random rand = new Random();
    while (certainty-- > 0)
      {
        // Pick a random number greater than 1 and less than this.
	// The algorithm says to pick a small number to make the calculations
	// go faster, but it doesn't say how small; we'll use 2 to 1024.
	int a = rand.nextInt();
	a = (a < 0 ? -a : a) % 1023 + 2;

	BigInteger z = make(a).modPow(m, this);
	if (z.isOne() || z.equals(pMinus1))
	  continue;			// Passes the test; may be prime.

	int i;
	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(make(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);
	    if (count == 0)
	      System.arraycopy(x.words, word_count, words, 0, d_len);
	    else
	      MPN.rshift(words, x.words, word_count, d_len, count);
	    ival = d_len;
	    if (neg)
	      words[ival-1] |= -1 << (32 - 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 make(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
	if (count < 32)
	  return make((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;

	int buf_size = len * (MPN.chars_per_word(radix) + 1);
	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);
    else 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 == null || ! (obj instanceof BigInteger))
      return false;
    return BigInteger.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 BigInteger.make(Long.parseLong(s, radix));
    
    int byte_len = 0;
    byte[] bytes = new byte[len];
    boolean negative = false;
    for (int i = 0;  i < len;  i++)
      {
	char ch = s.charAt(i);
	if (ch == '-')
	  negative = true;
	else if (ch == '_' || (byte_len == 0 && (ch == ' ' || ch == '\t')))
	  continue;
	else
	  {
	    int digit = Character.digit(ch, radix);
	    if (digit < 0)
	      break;
	    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 BigInteger.neg(this).roundToDouble(0, true, false);
    else
      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 (BigInteger.negate(words, x.words, len))
      words[len++] = 0;
    ival = len;
  }

  /** Destructively negate this. */
  private final 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 make(- x.ival);
    BigInteger result = new BigInteger(0);
    result.setNegative(x);
    return result.canonicalize();
  }

  public BigInteger negate()
  {
    return BigInteger.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);
    else
      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 make(-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 BigInteger.make(x.ival & y);
    if (y >= 0)
      return BigInteger.make(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 BigInteger.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 BigInteger.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;
  }
}