/*
 * Copyright (c) 1998, 2017, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code 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
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * @test
 * @library /test/lib
 * @build jdk.test.lib.RandomFactory
 * @run main BigIntegerTest
 * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672 8032027
 * @summary tests methods in BigInteger (use -Dseed=X to set PRNG seed)
 * @run main/timeout=400 BigIntegerTest
 * @author madbot
 * @key randomness
 */
package test.java.math.BigInteger;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Random;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.DoubleStream;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.Stream;

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * This is a simple test class created to ensure that the results
 * generated by BigInteger adhere to certain identities. Passing
 * this test is a strong assurance that the BigInteger operations
 * are working correctly.
 *
 * Four arguments may be specified which give the number of
 * decimal digits you desire in the four batches of test numbers.
 *
 * The tests are performed on arrays of random numbers which are
 * generated by a Random class as well as special cases which
 * throw in boundary numbers such as 0, 1, maximum sized, etc.
 *
 */

// Android-changed: Replace error counting with asserts.
public class BigIntegerTest {
    //
    // Bit large number thresholds based on the int thresholds
    // defined in BigInteger itself:
    //
    // KARATSUBA_THRESHOLD        = 80  ints = 2560 bits
    // TOOM_COOK_THRESHOLD        = 240 ints = 7680 bits
    // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits
    // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits
    //
    // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits
    //
    // BURNIKEL_ZIEGLER_THRESHOLD = 80  ints = 2560 bits
    //
    static final int BITS_KARATSUBA = 2560;
    static final int BITS_TOOM_COOK = 7680;
    static final int BITS_KARATSUBA_SQUARE = 4096;
    static final int BITS_TOOM_COOK_SQUARE = 6912;
    static final int BITS_SCHOENHAGE_BASE = 640;
    static final int BITS_BURNIKEL_ZIEGLER = 2560;
    static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280;

    static final int ORDER_SMALL = 60;
    static final int ORDER_MEDIUM = 100;
    // #bits for testing Karatsuba
    static final int ORDER_KARATSUBA = 2760;
    // #bits for testing Toom-Cook and Burnikel-Ziegler
    static final int ORDER_TOOM_COOK = 8000;
    // #bits for testing Karatsuba squaring
    static final int ORDER_KARATSUBA_SQUARE = 4200;
    // #bits for testing Toom-Cook squaring
    static final int ORDER_TOOM_COOK_SQUARE = 7000;

    static final int SIZE = 1000; // numbers per batch

    private static Random random = new Random();

    static boolean failure = false;

    private static void constructor() {
        // --- guard condition tests for array indexing ---

        int arrayLength = 23;
        int halfLength = arrayLength/2;
        byte[] array = new byte[arrayLength];
        random.nextBytes(array);

        int[][] offLen = new int[][] { // offset, length, num exceptions
            {-1, arrayLength, 1},                         // negative offset
            {0, arrayLength, 0},                          // OK
            {1, arrayLength, 1},                          // length overflow
            {arrayLength - 1, 1, 0},                      // OK
            {arrayLength, 1, 1},                          // offset overflow
            {0, -1, 1},                                   // negative length
            {halfLength, arrayLength - halfLength + 1, 1} // length overflow
        };

        // two's complement
        for (int[] ol : offLen) {
            try {
                BigInteger bi = new BigInteger(array, ol[0], ol[1]);
                if (ol[2] == 1) {
                    Assert.fail("IndexOutOfBoundsException did not occur for "
                        + " two's complement constructor with parameters offset "
                        + ol[0] + " and length " + ol[1]);
                }
            } catch (IndexOutOfBoundsException e) {
                if (ol[2] == 0) {
                    Assert.fail("Unexpected IndexOutOfBoundsException did occur for "
                            + " two's complement constructor with parameters offset "
                            + ol[0] + " and length " + ol[1]);
                }
            }
        }

        // sign-magnitude
        for (int[] ol : offLen) {
            try {
                BigInteger bi = new BigInteger(1, array, ol[0], ol[1]);
                if (ol[2] == 1) {
                    Assert.fail("IndexOutOfBoundsException did not occur for "
                        + " sign-magnitude constructor with parameters offset "
                        + ol[0] + " and length " + ol[1]);
                }
            } catch (IndexOutOfBoundsException e) {
                if (ol[2] == 0) {
                    Assert.fail("Unexpected IndexOutOfBoundsException did occur for "
                            + " two's complement constructor with parameters offset "
                            + ol[0] + " and length " + ol[1]);
                }
            }
        }

        // --- tests for creation of zero-valued BigIntegers ---

        byte[] magZeroLength = new byte[0];
        for (int signum = -1; signum <= 1; signum++) {
            BigInteger bi = new BigInteger(signum, magZeroLength);
            Assert.assertEquals(bi.compareTo(BigInteger.ZERO), 0,
                    "A: Zero length BigInteger != 0 for signum " + signum);
        }

        for (int signum = -1; signum <= 1; signum++) {
            BigInteger bi = new BigInteger(signum, magZeroLength, 0, 0);
            Assert.assertEquals(bi.compareTo(BigInteger.ZERO), 0,
                    "B: Zero length BigInteger != 0 for signum " + signum);
        }

        byte[] magNonZeroLength = new byte[42];
        random.nextBytes(magNonZeroLength);
        for (int signum = -1; signum <= 1; signum++) {
            BigInteger bi = new BigInteger(signum, magNonZeroLength, 0, 0);
            Assert.assertEquals(bi.compareTo(BigInteger.ZERO), 0,
                    "C: Zero length BigInteger != 0 for signum " + signum);
        }

        // --- tests for accurate creation of non-zero BigIntegers ---

        for (int i = 0; i < SIZE; i++) {
            // create reference value via a different code path from those tested
            BigInteger reference = new BigInteger(2 + random.nextInt(336), 4, random);

            byte[] refArray = reference.toByteArray();
            int refLen = refArray.length;
            int factor = random.nextInt(5);
            int objLen = refArray.length + factor*random.nextInt(refArray.length) + 1;
            int offset = random.nextInt(objLen - refLen);
            byte[] objArray = new byte[objLen];
            System.arraycopy(refArray, 0, objArray, offset, refLen);

            BigInteger twosComp = new BigInteger(objArray, offset, refLen);
            Assert.assertEquals(twosComp.compareTo(reference), 0,
                    "Two's-complement BigInteger not equal for offset " +
                        offset + " and length " + refLen);

            boolean isNegative = random.nextBoolean();
            BigInteger signMag = new BigInteger(isNegative ? -1 : 1, objArray, offset, refLen);
            Assert.assertEquals(signMag.compareTo(isNegative ? reference.negate() : reference), 0,
                    "Sign-magnitude BigInteger not equal for offset " +
                        offset + " and length " + refLen);
        }
    }

    private static void pow(int order) {
        for (int i=0; i<SIZE; i++) {
            // Test identity x^power == x*x*x ... *x
            int power = random.nextInt(6) + 2;
            BigInteger x = fetchNumber(order);
            BigInteger y = x.pow(power);
            BigInteger z = x;

            for (int j=1; j<power; j++)
                z = z.multiply(x);

            Assert.assertEquals(y, z);
        }
    }

    private static void square(int order) {
        for (int i=0; i<SIZE; i++) {
            // Test identity x^2 == x*x
            BigInteger x  = fetchNumber(order);
            BigInteger xx = x.multiply(x);
            BigInteger x2 = x.pow(2);

            Assert.assertEquals(x2, xx);
        }
    }

    private static void checkResult(BigInteger expected, BigInteger actual, String failureMessage) {
        Assert.assertEquals(expected.compareTo(actual), 0,
                failureMessage + " - expected: " + expected + ", actual: " + actual);
    }

    private static void squareRootSmall() {
        // A negative value should cause an exception.
        BigInteger n = BigInteger.ONE.negate();
        BigInteger s;
        try {
            s = n.sqrt();
            // If sqrt() does not throw an exception that is a failure.
            Assert.fail("sqrt() of negative number did not throw an exception");
        } catch (ArithmeticException expected) {
            // A negative value should cause an exception and is not a failure.
        }

        // A zero value should return BigInteger.ZERO.
        checkResult(BigInteger.ZERO, BigInteger.ZERO.sqrt(), "sqrt(0) != BigInteger.ZERO");

        // 1 <= value < 4 should return BigInteger.ONE.
        long[] smalls = new long[] {1, 2, 3};
        for (long small : smalls) {
            checkResult(BigInteger.ONE, BigInteger.valueOf(small).sqrt(), "sqrt("+small+") != 1");
        }
    }

    private static void squareRoot() {
        squareRootSmall();


        Function<BigInteger, Void> f = (n) -> {
            // square root of n^2 -> n
            BigInteger n2 = n.pow(2);
            checkResult(n, n2.sqrt(), "sqrt() n^2 -> n");

            // square root of n^2 + 1 -> n
            BigInteger n2up = n2.add(BigInteger.ONE);
            checkResult(n, n2up.sqrt(), "sqrt() n^2 + 1 -> n");

            // square root of (n + 1)^2 - 1 -> n
            BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
            checkResult(n, up.sqrt(), "sqrt() (n + 1)^2 - 1 -> n");

            // sqrt(n)^2 <= n
            BigInteger s = n.sqrt();
            Assert.assertFalse(s.multiply(s).compareTo(n) > 0,
                    "sqrt(n)^2 > n for n = " + n);

            // (sqrt(n) + 1)^2 > n
            Assert.assertFalse(s.add(BigInteger.ONE).pow(2).compareTo(n) <= 0,
                    "(sqrt(n) + 1)^2 <= n for n = " + n);
            return null;
        };

        Stream.Builder<BigInteger> sb = Stream.builder();
        int maxExponent = Double.MAX_EXPONENT + 1;
        for (int i = 1; i <= maxExponent; i++) {
            BigInteger p2 = BigInteger.ONE.shiftLeft(i);
            sb.add(p2.subtract(BigInteger.ONE));
            sb.add(p2);
            sb.add(p2.add(BigInteger.ONE));
        }
        sb.add((new BigDecimal(Double.MAX_VALUE)).toBigInteger());
        sb.add((new BigDecimal(Double.MAX_VALUE)).toBigInteger().add(BigInteger.ONE));
        // "squareRoot for 2^N and 2^N - 1, 1 <= N <= Double.MAX_EXPONENT"
        sb.build().map(f).collect(Collectors.toList());

        IntStream ints = random.ints(SIZE, 4, Integer.MAX_VALUE);
        ints.mapToObj(BigInteger::valueOf).map(f).collect(Collectors.toList());

        LongStream longs = random.longs(SIZE, (long)Integer.MAX_VALUE + 1L,
            Long.MAX_VALUE);
        longs.mapToObj(BigInteger::valueOf).map(f).collect(Collectors.toList());

        DoubleStream doubles = random.doubles(SIZE,
            (double) Long.MAX_VALUE + 1.0, Math.sqrt(Double.MAX_VALUE));
        doubles.mapToObj(x -> BigDecimal.valueOf(x).toBigInteger()).map(f).collect(Collectors.toList());
    }

    private static void squareRootAndRemainder() {
        Function<BigInteger, Void> g = (n) -> {
            BigInteger n2 = n.pow(2);

            // square root of n^2 -> n
            BigInteger[] actual = n2.sqrtAndRemainder();
            checkResult(n, actual[0], "sqrtAndRemainder()[0]");
            checkResult(BigInteger.ZERO, actual[1], "sqrtAndRemainder()[1]");

            // square root of n^2 + 1 -> n
            BigInteger n2up = n2.add(BigInteger.ONE);
            actual = n2up.sqrtAndRemainder();
            checkResult(n, actual[0], "sqrtAndRemainder()[0]");
            checkResult(BigInteger.ONE, actual[1], "sqrtAndRemainder()[1]");

            // square root of (n + 1)^2 - 1 -> n
            BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE);
            actual = up.sqrtAndRemainder();
            checkResult(n, actual[0], "sqrtAndRemainder()[0]");
            BigInteger r = up.subtract(n2);
            checkResult(r, actual[1], "sqrtAndRemainder()[1]");
            return null;
        };

        IntStream bits = random.ints(SIZE, 3, Short.MAX_VALUE);
        bits.mapToObj(BigInteger::valueOf).map(g).collect(Collectors.toList());
    }

    private static void arithmetic(int order) {
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(order);
            while(x.compareTo(BigInteger.ZERO) != 1)
                x = fetchNumber(order);
            BigInteger y = fetchNumber(order/2);
            while(x.compareTo(y) == -1)
                y = fetchNumber(order/2);
            if (y.equals(BigInteger.ZERO))
                y = y.add(BigInteger.ONE);

            // Test identity ((x/y))*y + x%y - x == 0
            // using separate divide() and remainder()
            BigInteger baz = x.divide(y);
            baz = baz.multiply(y);
            baz = baz.add(x.remainder(y));
            baz = baz.subtract(x);
            Assert.assertEquals(baz, BigInteger.ZERO);
        }

        for (int i=0; i<100; i++) {
            BigInteger x = fetchNumber(order);
            while(x.compareTo(BigInteger.ZERO) != 1)
                x = fetchNumber(order);
            BigInteger y = fetchNumber(order/2);
            while(x.compareTo(y) == -1)
                y = fetchNumber(order/2);
            if (y.equals(BigInteger.ZERO))
                y = y.add(BigInteger.ONE);

            // Test identity ((x/y))*y + x%y - x == 0
            // using divideAndRemainder()
            BigInteger baz[] = x.divideAndRemainder(y);
            baz[0] = baz[0].multiply(y);
            baz[0] = baz[0].add(baz[1]);
            baz[0] = baz[0].subtract(x);
            Assert.assertEquals(baz[0], BigInteger.ZERO);
        }
    }

    /**
     * Sanity test for Karatsuba and 3-way Toom-Cook multiplication.
     * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,
     * construct two factors each with a mag array one element shorter than the
     * threshold, and with the most significant bit set and the rest of the bits
     * random. Each of these numbers will therefore be below the threshold but
     * if shifted left be above the threshold. Call the numbers 'u' and 'v' and
     * define random shifts 'a' and 'b' in the range [1,32]. Then we have the
     * identity
     * <pre>
     * (u << a)*(v << b) = (u*v) << (a + b)
     * </pre>
     * For Karatsuba multiplication, the right hand expression will be evaluated
     * using the standard naive algorithm, and the left hand expression using
     * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right
     * hand expression will be evaluated using Karatsuba multiplication, and the
     * left hand expression using 3-way Toom-Cook multiplication.
     */
    private static void multiplyLarge() {
        BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
            BigInteger u = base.add(x);
            int a = 1 + random.nextInt(31);
            BigInteger w = u.shiftLeft(a);

            BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);
            BigInteger v = base.add(y);
            int b = 1 + random.nextInt(32);
            BigInteger z = v.shiftLeft(b);

            BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);
            BigInteger karatsubaMultiplyResult = w.multiply(z);

            Assert.assertEquals(karatsubaMultiplyResult, multiplyResult);
        }

        base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
            BigInteger u = base.add(x);
            BigInteger u2 = u.shiftLeft(1);
            BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
            BigInteger v = base.add(y);
            BigInteger v2 = v.shiftLeft(1);

            BigInteger multiplyResult = u.multiply(v).shiftLeft(2);
            BigInteger toomCookMultiplyResult = u2.multiply(v2);

            Assert.assertEquals(toomCookMultiplyResult, multiplyResult);
        }
    }

    /**
     * Sanity test for Karatsuba and 3-way Toom-Cook squaring.
     * This test is analogous to {@link AbstractMethodError#multiplyLarge}
     * with both factors being equal. The squaring methods will not be tested
     * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether
     * the parameter is the same instance on which the method is being invoked
     * and calls <code>square()</code> accordingly.
     */
    private static void squareLarge() {
        BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
            BigInteger u = base.add(x);
            int a = 1 + random.nextInt(31);
            BigInteger w = u.shiftLeft(a);

            BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
            BigInteger karatsubaSquareResult = w.multiply(w);

            Assert.assertEquals(karatsubaSquareResult, squareResult);
        }

        base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
            BigInteger u = base.add(x);
            int a = 1 + random.nextInt(31);
            BigInteger w = u.shiftLeft(a);

            BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
            BigInteger toomCookSquareResult = w.multiply(w);

            Assert.assertEquals(toomCookSquareResult, squareResult);
        }
    }

    /**
     * Sanity test for Burnikel-Ziegler division.  The Burnikel-Ziegler division
     * algorithm is used when each of the dividend and the divisor has at least
     * a specified number of ints in its representation.  This test is based on
     * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
     * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if
     * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then
     * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}.  The test
     * ensures that {@code v} is just under the B-Z threshold, that {@code z} is
     * over the threshold and {@code w} is much larger than {@code z}. This
     * implies that {@code u/v} uses the standard division algorithm and
     * {@code w/z} uses the B-Z algorithm.  The results of the two algorithms
     * are then compared using the observation described in the foregoing and
     * if they are not equal a failure is logged.
     */
    private static void divideLarge() {
        BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33);
        for (int i=0; i<SIZE; i++) {
            BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, random);
            BigInteger v = base.add(addend);

            BigInteger u = v.multiply(BigInteger.valueOf(2 + random.nextInt(Short.MAX_VALUE - 1)));

            if(random.nextBoolean()) {
                u = u.negate();
            }
            if(random.nextBoolean()) {
                v = v.negate();
            }

            int a = BITS_BURNIKEL_ZIEGLER_OFFSET + random.nextInt(16);
            int b = 1 + random.nextInt(16);
            BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a));
            BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b));

            BigInteger[] divideResult = u.divideAndRemainder(v);
            divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b));
            divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b));
            BigInteger[] bzResult = w.divideAndRemainder(z);

            Assert.assertEquals(divideResult[0].compareTo(bzResult[0]), 0);
            Assert.assertEquals(divideResult[1].compareTo(bzResult[1]), 0);
        }
    }

    private static void bitCount() {
        for (int i=0; i<SIZE*10; i++) {
            int x = random.nextInt();
            BigInteger bigX = BigInteger.valueOf((long)x);
            int bit = (x < 0 ? 0 : 1);
            int tmp = x, bitCount = 0;
            for (int j=0; j<32; j++) {
                bitCount += ((tmp & 1) == bit ? 1 : 0);
                tmp >>= 1;
            }

            Assert.assertEquals (bigX.bitCount(), bitCount);
        }
    }

    private static void bitLength() {
        for (int i=0; i<SIZE*10; i++) {
            int x = random.nextInt();
            BigInteger bigX = BigInteger.valueOf((long)x);
            int signBit = (x < 0 ? 0x80000000 : 0);
            int tmp = x, bitLength, j;
            for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)
                tmp <<= 1;
            bitLength = 32 - j;

            Assert.assertEquals(bigX.bitLength(), bitLength);
        }
    }

    private static void bitOps(int order) {
        for (int i=0; i<SIZE*5; i++) {
            BigInteger x = fetchNumber(order);
            BigInteger y;

            // Test setBit and clearBit (and testBit)
            if (x.signum() < 0) {
                y = BigInteger.valueOf(-1);
                for (int j=0; j<x.bitLength(); j++)
                    if (!x.testBit(j))
                        y = y.clearBit(j);
            } else {
                y = BigInteger.ZERO;
                for (int j=0; j<x.bitLength(); j++)
                    if (x.testBit(j))
                        y = y.setBit(j);
            }
            Assert.assertEquals(y, x);

            // Test flipBit (and testBit)
            y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
            for (int j=0; j<x.bitLength(); j++)
                if (x.signum()<0  ^  x.testBit(j))
                    y = y.flipBit(j);
            Assert.assertEquals(y, x);
        }

        for (int i=0; i<SIZE*5; i++) {
            BigInteger x = fetchNumber(order);

            // Test getLowestSetBit()
            int k = x.getLowestSetBit();
            if (x.signum() == 0) {
                Assert.assertEquals(k, -1);
            } else {
                BigInteger z = x.and(x.negate());
                int j;
                for (j=0; j<z.bitLength() && !z.testBit(j); j++)
                    ;
                Assert.assertEquals(k, j);
            }
        }
    }

    private static void bitwise(int order) {

        // Test identity x^y == x|y &~ x&y
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(order);
            BigInteger y = fetchNumber(order);
            BigInteger z = x.xor(y);
            BigInteger w = x.or(y).andNot(x.and(y));
            Assert.assertEquals(z, w, "Test identity x^y == x|y &~ x&y");
        }

        // Test identity x &~ y == ~(~x | y)
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(order);
            BigInteger y = fetchNumber(order);
            BigInteger z = x.andNot(y);
            BigInteger w = x.not().or(y).not();
            Assert.assertEquals(z, w, "Test identity x &~ y == ~(~x | y)");
        }
    }

    private static void shift(int order) {
        for (int i=0; i<100; i++) {
            BigInteger x = fetchNumber(order);
            int n = Math.abs(random.nextInt()%200);

            Assert.assertEquals(x.shiftLeft(n), x.multiply(BigInteger.valueOf(2L).pow(n)));

            BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n));
            BigInteger z = (x.signum()<0 && y[1].signum()!=0
                            ? y[0].subtract(BigInteger.ONE)
                            : y[0]);

            BigInteger b = x.shiftRight(n);

            Assert.assertEquals(z, b);

            Assert.assertEquals(x.shiftLeft(n).shiftRight(n), x);
        }
    }

    private static void divideAndRemainder(int order) {
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(order).abs();
            while(x.compareTo(BigInteger.valueOf(3L)) != 1)
                x = fetchNumber(order).abs();
            BigInteger z = x.divide(BigInteger.valueOf(2L));
            BigInteger y[] = x.divideAndRemainder(x);

            Assert.assertEquals(y[0], BigInteger.ONE);
            Assert.assertEquals(y[1], BigInteger.ZERO);

            y = x.divideAndRemainder(z);
            Assert.assertEquals(y[0], BigInteger.valueOf(2));
        }
    }

    private static void stringConv_generic() {
        // Generic string conversion.
        for (int i=0; i<100; i++) {
            byte[] xBytes = new byte[Math.abs(random.nextInt())%100+1];
            random.nextBytes(xBytes);
            BigInteger x = new BigInteger(xBytes);

            for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
                String result = x.toString(radix);
                BigInteger test = new BigInteger(result, radix);
                Assert.assertEquals(test, x,
                        "BigInteger toString: "+x+" Test: "+test+" radix: " + radix);
            }
        }
    }

    private static void stringConv_schoenhage(int k, int samples) {
        // String conversion straddling the Schoenhage algorithm crossover
        // threshold, and at twice and four times the threshold.
        int factor = 1 << k;
        int upper = factor * BITS_SCHOENHAGE_BASE + 33;
        int lower = upper - 35;

        for (int bits = upper; bits >= lower; bits--) {
            for (int i = 0; i < samples; i++) {
                BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, random));

                for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
                    String result = x.toString(radix);
                    BigInteger test = new BigInteger(result, radix);
                    Assert.assertEquals(test, x,
                            "BigInteger toString: "+x+" Test: "+test+" radix: " + radix);
                }
            }
        }
    }

    private static void byteArrayConv(int order) {
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(order);
            while (x.equals(BigInteger.ZERO))
                x = fetchNumber(order);
            BigInteger y = new BigInteger(x.toByteArray());
            Assert.assertEquals(y, x, "orig is " + x + ", new is " + y);
        }
    }

    private static void modInv(int order) {
        for (int i=0; i<SIZE; i++) {
            BigInteger x = fetchNumber(order);
            while(x.equals(BigInteger.ZERO))
                x = fetchNumber(order);
            BigInteger m = fetchNumber(order).abs();
            while(m.compareTo(BigInteger.ONE) != 1)
                m = fetchNumber(order).abs();

            try {
                BigInteger inv = x.modInverse(m);
                BigInteger prod = inv.multiply(x).remainder(m);

                if (prod.signum() == -1)
                    prod = prod.add(m);

                Assert.assertEquals(prod, BigInteger.ONE);
            } catch(ArithmeticException ignored) {
            }
        }
    }

    private static void modExp(int order1, int order2) {
        for (int i=0; i<SIZE/10; i++) {
            BigInteger m = fetchNumber(order1).abs();
            while(m.compareTo(BigInteger.ONE) != 1)
                m = fetchNumber(order1).abs();
            BigInteger base = fetchNumber(order2);
            BigInteger exp = fetchNumber(8).abs();

            BigInteger z = base.modPow(exp, m);
            BigInteger w = base.pow(exp.intValue()).mod(m);

            Assert.assertEquals(z, w, "z is "+z+" w is "+w+" mod is "+m+" base is "+base+" exp is "+exp);
        }
    }

    // This test is based on Fermat's theorem
    // which is not ideal because base must not be multiple of modulus
    // and modulus must be a prime or pseudoprime (Carmichael number)
    private static void modExp2(int order) {
        for (int i=0; i<10; i++) {
            BigInteger m = new BigInteger(100, 5, random);
            while(m.compareTo(BigInteger.ONE) != 1)
                m = new BigInteger(100, 5, random);
            BigInteger exp = m.subtract(BigInteger.ONE);
            BigInteger base = fetchNumber(order).abs();
            while(base.compareTo(m) != -1)
                base = fetchNumber(order).abs();
            while(base.equals(BigInteger.ZERO))
                base = fetchNumber(order).abs();

            BigInteger one = base.modPow(exp, m);
            Assert.assertEquals(one, BigInteger.ONE, "m is "+m+" base is "+base+" exp is "+exp);
        }
    }

    private static final int[] mersenne_powers = {
        521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
        21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
        1257787, 1398269, 2976221, 3021377, 6972593, 13466917 };

    private static final long[] carmichaels = {
      561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,
      62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,
      278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,
      225593397919L };

    // Note: testing the larger ones takes too long.
    private static final int NUM_MERSENNES_TO_TEST = 7;
    // Note: this constant used for computed Carmichaels, not the array above
    private static final int NUM_CARMICHAELS_TO_TEST = 5;

    private static final String[] customer_primes = {
        "120000000000000000000000000000000019",
        "633825300114114700748351603131",
        "1461501637330902918203684832716283019651637554291",
        "779626057591079617852292862756047675913380626199",
        "857591696176672809403750477631580323575362410491",
        "910409242326391377348778281801166102059139832131",
        "929857869954035706722619989283358182285540127919",
        "961301750640481375785983980066592002055764391999",
        "1267617700951005189537696547196156120148404630231",
        "1326015641149969955786344600146607663033642528339" };

    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = new BigInteger("2");
    private static final BigInteger SIX = new BigInteger("6");
    private static final BigInteger TWELVE = new BigInteger("12");
    private static final BigInteger EIGHTEEN = new BigInteger("18");

    private static void prime() {
        BigInteger p1, p2, c1;

        // Test consistency
        for(int i=0; i<10; i++) {
            p1 = BigInteger.probablePrime(100, random);
            Assert.assertTrue(p1.isProbablePrime(100), p1.toString(16));
        }

        // Test some known Mersenne primes (2^n)-1
        // The array holds the exponents, not the numbers being tested
        for (int i=0; i<NUM_MERSENNES_TO_TEST; i++) {
            p1 = new BigInteger("2");
            p1 = p1.pow(mersenne_powers[i]);
            p1 = p1.subtract(BigInteger.ONE);
            Assert.assertTrue(p1.isProbablePrime(100), "Mersenne prime "+i+ " failed.");
        }

        // Test some primes reported by customers as failing in the past
        for (int i=0; i<customer_primes.length; i++) {
            p1 = new BigInteger(customer_primes[i]);
            Assert.assertTrue(p1.isProbablePrime(100), "Customer prime "+i+ " failed.");
        }

        // Test some known Carmichael numbers.
        for (int i=0; i<carmichaels.length; i++) {
            c1 = BigInteger.valueOf(carmichaels[i]);
            Assert.assertFalse(c1.isProbablePrime(100), "Carmichael "+i+ " reported as prime.");
        }

        // Test some computed Carmichael numbers.
        // Numbers of the form (6k+1)(12k+1)(18k+1) are Carmichael numbers if
        // each of the factors is prime
        int found = 0;
        BigInteger f1 = new BigInteger(40, 100, random);
        while (found < NUM_CARMICHAELS_TO_TEST) {
            BigInteger k = null;
            BigInteger f2, f3;
            f1 = f1.nextProbablePrime();
            BigInteger[] result = f1.subtract(ONE).divideAndRemainder(SIX);
            if (result[1].equals(ZERO)) {
                k = result[0];
                f2 = k.multiply(TWELVE).add(ONE);
                if (f2.isProbablePrime(100)) {
                    f3 = k.multiply(EIGHTEEN).add(ONE);
                    if (f3.isProbablePrime(100)) {
                        c1 = f1.multiply(f2).multiply(f3);
                        Assert.assertFalse(c1.isProbablePrime(100), "Computed Carmichael "
                                               +c1.toString(16));
                        found++;
                    }
                }
            }
            f1 = f1.add(TWO);
        }

        // Test some composites that are products of 2 primes
        for (int i=0; i<50; i++) {
            p1 = BigInteger.probablePrime(100, random);
            p2 = BigInteger.probablePrime(100, random);
            c1 = p1.multiply(p2);
            Assert.assertFalse(c1.isProbablePrime(100),
                    "Composite failed "+c1.toString(16));
        }

        for (int i=0; i<4; i++) {
            p1 = BigInteger.probablePrime(600, random);
            p2 = BigInteger.probablePrime(600, random);
            c1 = p1.multiply(p2);
            Assert.assertFalse(c1.isProbablePrime(100),
                    "Composite failed "+c1.toString(16));
        }
    }

    private static final long[] primesTo100 = {
        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
    };

    private static final long[] aPrimeSequence = {
        1999999003L, 1999999013L, 1999999049L, 1999999061L, 1999999081L,
        1999999087L, 1999999093L, 1999999097L, 1999999117L, 1999999121L,
        1999999151L, 1999999171L, 1999999207L, 1999999219L, 1999999271L,
        1999999321L, 1999999373L, 1999999423L, 1999999439L, 1999999499L,
        1999999553L, 1999999559L, 1999999571L, 1999999609L, 1999999613L,
        1999999621L, 1999999643L, 1999999649L, 1999999657L, 1999999747L,
        1999999763L, 1999999777L, 1999999811L, 1999999817L, 1999999829L,
        1999999853L, 1999999861L, 1999999871L, 1999999873
    };

    private static void nextProbablePrime() throws Exception {
        BigInteger p1, p2, p3;
        p1 = p2 = p3 = ZERO;

        // First test nextProbablePrime on the low range starting at zero
        for (long l : primesTo100) {
            p1 = p1.nextProbablePrime();
            Assert.assertEquals(p1.longValue(), l,
                    "low range primes failed: p1 is " + p1 + ", expected " + l);
        }

        // Test nextProbablePrime on a relatively small, known prime sequence
        p1 = BigInteger.valueOf(aPrimeSequence[0]);
        for (int i=1; i<aPrimeSequence.length; i++) {
            p1 = p1.nextProbablePrime();
            Assert.assertEquals(p1.longValue(), aPrimeSequence[i], "prime sequence failed");
        }

        // Next, pick some large primes, use nextProbablePrime to find the
        // next one, and make sure there are no primes in between
        for (int i=0; i<100; i+=10) {
            p1 = BigInteger.probablePrime(50 + i, random);
            p2 = p1.add(ONE);
            p3 = p1.nextProbablePrime();
            while(p2.compareTo(p3) < 0) {
                Assert.assertFalse(p2.isProbablePrime(100),
                        "nextProbablePrime failed along range "+p1.toString(16)+" to "+p3.toString(16));
                p2 = p2.add(ONE);
            }
        }
    }

    // Android-changed: Replace File streams with ByteArray
    public static void serialize() throws Exception {
        String[] bitPatterns = {
             "ffffffff00000000ffffffff00000000ffffffff00000000",
             "ffffffffffffffffffffffff000000000000000000000000",
             "ffffffff0000000000000000000000000000000000000000",
             "10000000ffffffffffffffffffffffffffffffffffffffff",
             "100000000000000000000000000000000000000000000000",
             "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
            "-ffffffff00000000ffffffff00000000ffffffff00000000",
            "-ffffffffffffffffffffffff000000000000000000000000",
            "-ffffffff0000000000000000000000000000000000000000",
            "-10000000ffffffffffffffffffffffffffffffffffffffff",
            "-100000000000000000000000000000000000000000000000",
            "-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
        };

        for (String bitPattern : bitPatterns) {
            BigInteger b1 = new BigInteger(bitPattern, 16);
            BigInteger b2 = null;

            try (ByteArrayOutputStream fos = new ByteArrayOutputStream()) {
                try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
                    oos.writeObject(b1);
                    oos.flush();
                }

                try (ByteArrayInputStream fis = new ByteArrayInputStream(fos.toByteArray());
                        ObjectInputStream ois = new ObjectInputStream(fis)) {
                    b2 = (BigInteger) ois.readObject();
                }

                Assert.assertEquals(b1, b2, "Serialized failed for hex " + b1.toString(16));
                Assert.assertEquals(b1.or(b2), b1, "Serialized failed for hex " + b1.toString(16));
            }
        }

        for(int i=0; i<10; i++) {
            BigInteger b1 = fetchNumber(random.nextInt(100));
            BigInteger b2 = null;

            try (ByteArrayOutputStream fos = new ByteArrayOutputStream()) {
                try (ObjectOutputStream oos = new ObjectOutputStream(fos)) {
                    oos.writeObject(b1);
                    oos.flush();
                }

                try (ByteArrayInputStream fis = new ByteArrayInputStream(fos.toByteArray());
                     ObjectInputStream ois = new ObjectInputStream(fis))
                {
                    b2 = (BigInteger)ois.readObject();
                }
            }

            Assert.assertEquals(b1, b2, "Serialized failed for hex " + b1.toString(16));
            Assert.assertEquals(b1.or(b2), b1, "Serialized failed for hex " + b1.toString(16));
        }
    }

    private static final int ORDER_1 = ORDER_MEDIUM;
    private static final int ORDER_2 = ORDER_SMALL;
    private static final int ORDER_3 = ORDER_KARATSUBA;
    private static final int ORDER_4 = ORDER_TOOM_COOK;

    @Test
    public void testConstructor() {
        constructor();
    }

    @Test
    public void testPrime() {
        prime();
    }

    @Test
    public void testNextProbablePrime() throws Exception {
        nextProbablePrime();
    }

    @Test
    public void testArithmetic() {
        arithmetic(ORDER_1);   // small numbers
        arithmetic(ORDER_3);   // Karatsuba range
        arithmetic(ORDER_4);   // Toom-Cook / Burnikel-Ziegler range
    }

    @Test
    public void testDivideAndReminder() {
        divideAndRemainder(ORDER_1);   // small numbers
        divideAndRemainder(ORDER_3);   // Karatsuba range
        divideAndRemainder(ORDER_4);   // Toom-Cook / Burnikel-Ziegler range
    }

    @Test
    public void testPow() {
        pow(ORDER_1);
        pow(ORDER_3);
        pow(ORDER_4);
    }

    @Test
    public void testSquare() {
        square(ORDER_MEDIUM);
        square(ORDER_KARATSUBA_SQUARE);
        square(ORDER_TOOM_COOK_SQUARE);
    }

    @Test
    public void testSquareRoot() {
        squareRoot();
    }

    @Test
    public void testSquareRootAndReminder() {
        squareRootAndRemainder();
    }

    @Test
    public void testBitCount() {
        bitCount();
    }

    @Test
    public void testBitLength() {
        bitLength();
    }

    @Test
    public void testBitOps() {
        bitOps(ORDER_1);
    }

    @Test
    public void testBitwise() {
        bitwise(ORDER_1);
    }

    @Test
    public void testShift() {
        shift(ORDER_1);
    }

    @Test
    public void testByteArrayConv() {
        byteArrayConv(ORDER_1);
    }

    @Test
    public void testModInv() {
        modInv(ORDER_1);   // small numbers
        modInv(ORDER_3);   // Karatsuba range
        modInv(ORDER_4);   // Toom-Cook / Burnikel-Ziegler range
    }

    @Test
    public void testModExp() {
        modExp(ORDER_1, ORDER_2);
        modExp2(ORDER_1);
    }

    @Test
    public void testStringConv_generic() {
        stringConv_generic();
    }

    // String conversion straddling the Schoenhage algorithm crossover
    // threshold.
    @Test
    public void testStringConv_schoenhage_threshold_pow0() {
        stringConv_schoenhage(0, 50);
    }

    // String conversion straddling the Schoenhage algorithm crossover
    // at twice times the threshold.
    @Test
    public void testStringConv_schoenhage_threshold_pow1() {
        stringConv_schoenhage(1, 50);
    }

    // String conversion straddling the Schoenhage algorithm crossover
    // at four times the threshold.
    @Test
    public void testStringConv_schoenhage_threshold_pow2() {
        stringConv_schoenhage(2, 15);
    }

    @Test
    public void testSerialize() throws Exception {
        serialize();
    }

    @Test
    public void testMultiplyLarge() {
        multiplyLarge();
    }

    @Test
    public void testSquareLarge() {
        squareLarge();
    }

    @Test
    public void testDivideLarge() {
        divideLarge();
    }

    /*
     * Get a random or boundary-case number. This is designed to provide
     * a lot of numbers that will find failure points, such as max sized
     * numbers, empty BigIntegers, etc.
     *
     * If order is less than 2, order is changed to 2.
     */
    private static BigInteger fetchNumber(int order) {
        boolean negative = random.nextBoolean();
        int numType = random.nextInt(7);
        BigInteger result = null;
        if (order < 2) order = 2;

        switch (numType) {
            case 0: // Empty
                result = BigInteger.ZERO;
                break;

            case 1: // One
                result = BigInteger.ONE;
                break;

            case 2: // All bits set in number
                int numBytes = (order+7)/8;
                byte[] fullBits = new byte[numBytes];
                for(int i=0; i<numBytes; i++)
                    fullBits[i] = (byte)0xff;
                int excessBits = 8*numBytes - order;
                fullBits[0] &= (1 << (8-excessBits)) - 1;
                result = new BigInteger(1, fullBits);
                break;

            case 3: // One bit in number
                result = BigInteger.ONE.shiftLeft(random.nextInt(order));
                break;

            case 4: // Random bit density
                byte[] val = new byte[(order+7)/8];
                int iterations = random.nextInt(order);
                for (int i=0; i<iterations; i++) {
                    int bitIdx = random.nextInt(order);
                    val[bitIdx/8] |= 1 << (bitIdx%8);
                }
                result = new BigInteger(1, val);
                break;
            case 5: // Runs of consecutive ones and zeros
                result = ZERO;
                int remaining = order;
                int bit = random.nextInt(2);
                while (remaining > 0) {
                    int runLength = Math.min(remaining, random.nextInt(order));
                    result = result.shiftLeft(runLength);
                    if (bit > 0)
                        result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
                    remaining -= runLength;
                    bit = 1 - bit;
                }
                break;

            default: // random bits
                result = new BigInteger(order, random);
        }

        if (negative)
            result = result.negate();

        return result;
    }

}