/*

 * 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

 */

import java.io.File;

import java.io.FileInputStream;

import java.io.FileOutputStream;

import java.io.ObjectInputStream;

import java.io.ObjectOutputStream;

import java.math.BigDecimal;

import java.math.BigInteger;

import java.util.Random;

import java.util.function.ToIntFunction;

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 jdk.test.lib.RandomFactory;

/**

 * 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.

 *

 */

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 = RandomFactory.getRandom();

    static boolean failure = false;

    public static void constructor() {

        int failCount = 0;

        // --- 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) {

            int numExceptions = 0;

            try {

                BigInteger bi = new BigInteger(array, ol[0], ol[1]);

            } catch (IndexOutOfBoundsException e) {

                numExceptions++;

            }

            if (numExceptions != ol[2]) {

                System.err.println("IndexOutOfBoundsException did not occur for "

                    + " two's complement constructor with parameters offset "

                    + ol[0] + " and length " + ol[1]);

                failCount++;

            }

        }

        // sign-magnitude

        for (int[] ol : offLen) {

            int numExceptions = 0;

            try {

                BigInteger bi = new BigInteger(1, array, ol[0], ol[1]);

            } catch (IndexOutOfBoundsException e) {

                numExceptions++;

            }

            if (numExceptions != ol[2]) {

                System.err.println("IndexOutOfBoundsException did not occur for "

                    + " sign-magnitude constructor with parameters offset "

                    + ol[0] + " and length " + ol[1]);

                failCount++;

            }

        }

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

            if (bi.compareTo(BigInteger.ZERO) != 0) {

                System.err.println("A: Zero length BigInteger != 0 for signum " + signum);

                failCount++;

            }

        }

        for (int signum = -1; signum <= 1; signum++) {

            BigInteger bi = new BigInteger(signum, magZeroLength, 0, 0);

            if (bi.compareTo(BigInteger.ZERO) != 0) {

                System.err.println("B: Zero length BigInteger != 0 for signum " + signum);

                failCount++;

            }

        }

        byte[] magNonZeroLength = new byte[42];

        random.nextBytes(magNonZeroLength);

        for (int signum = -1; signum <= 1; signum++) {

            BigInteger bi = new BigInteger(signum, magNonZeroLength, 0, 0);

            if (bi.compareTo(BigInteger.ZERO) != 0) {

                System.err.println("C: Zero length BigInteger != 0 for signum " + signum);

                failCount++;

            }

        }

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

            if (twosComp.compareTo(reference) != 0) {

                System.err.println("Two's-complement BigInteger not equal for offset " +

                        offset + " and length " + refLen);

                failCount++;

            }

            boolean isNegative = random.nextBoolean();

            BigInteger signMag = new BigInteger(isNegative ? -1 : 1, objArray, offset, refLen);

            if (signMag.compareTo(isNegative ? reference.negate() : reference) != 0) {

                System.err.println("Sign-magnitude BigInteger not equal for offset " +

                        offset + " and length " + refLen);

                failCount++;

            }

        }

        report("Constructor", failCount);

    }

    public static void pow(int order) {

        int failCount1 = 0;

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

            if (!y.equals(z))

                failCount1++;

        }

        report("pow for " + order + " bits", failCount1);

    }

    public static void square(int order) {

        int failCount1 = 0;

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

            if (!x2.equals(xx))

                failCount1++;

        }

        report("square for " + order + " bits", failCount1);

    }

    private static void printErr(String msg) {

        System.err.println(msg);

    }

    private static int checkResult(BigInteger expected, BigInteger actual,

        String failureMessage) {

        if (expected.compareTo(actual) != 0) {

            printErr(failureMessage + " - expected: " + expected

                + ", actual: " + actual);

            return 1;

        }

        return 0;

    }

    private static void squareRootSmall() {

        int failCount = 0;

        // 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.

            failCount++;

            printErr("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.

        failCount += 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) {

            failCount += checkResult(BigInteger.ONE,

                BigInteger.valueOf(small).sqrt(), "sqrt("+small+") != 1");

        }

        report("squareRootSmall", failCount);

    }

    public static void squareRoot() {

        squareRootSmall();

        ToIntFunction<BigInteger> f = (n) -> {

            int failCount = 0;

            // square root of n^2 -> n

            BigInteger n2 = n.pow(2);

            failCount += checkResult(n, n2.sqrt(), "sqrt() n^2 -> n");

            // square root of n^2 + 1 -> n

            BigInteger n2up = n2.add(BigInteger.ONE);

            failCount += 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);

            failCount += checkResult(n, up.sqrt(), "sqrt() (n + 1)^2 - 1 -> n");

            // sqrt(n)^2 <= n

            BigInteger s = n.sqrt();

            if (s.multiply(s).compareTo(n) > 0) {

                failCount++;

                printErr("sqrt(n)^2 > n for n = " + n);

            }

            // (sqrt(n) + 1)^2 > n

            if (s.add(BigInteger.ONE).pow(2).compareTo(n) <= 0) {

                failCount++;

                printErr("(sqrt(n) + 1)^2 <= n for n = " + n);

            }

            return failCount;

        };

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

        report("squareRoot for 2^N and 2^N - 1, 1 <= N <= Double.MAX_EXPONENT",

            sb.build().collect(Collectors.summingInt(f)));

        IntStream ints = random.ints(SIZE, 4, Integer.MAX_VALUE);

        report("squareRoot for int", ints.mapToObj(x ->

            BigInteger.valueOf(x)).collect(Collectors.summingInt(f)));

        LongStream longs = random.longs(SIZE, (long)Integer.MAX_VALUE + 1L,

            Long.MAX_VALUE);

        report("squareRoot for long", longs.mapToObj(x ->

            BigInteger.valueOf(x)).collect(Collectors.summingInt(f)));

        DoubleStream doubles = random.doubles(SIZE,

            (double) Long.MAX_VALUE + 1.0, Math.sqrt(Double.MAX_VALUE));

        report("squareRoot for double", doubles.mapToObj(x ->

            BigDecimal.valueOf(x).toBigInteger()).collect(Collectors.summingInt(f)));

    }

    public static void squareRootAndRemainder() {

        ToIntFunction<BigInteger> g = (n) -> {

            int failCount = 0;

            BigInteger n2 = n.pow(2);

            // square root of n^2 -> n

            BigInteger[] actual = n2.sqrtAndRemainder();

            failCount += checkResult(n, actual[0], "sqrtAndRemainder()[0]");

            failCount += checkResult(BigInteger.ZERO, actual[1],

                "sqrtAndRemainder()[1]");

            // square root of n^2 + 1 -> n

            BigInteger n2up = n2.add(BigInteger.ONE);

            actual = n2up.sqrtAndRemainder();

            failCount += checkResult(n, actual[0], "sqrtAndRemainder()[0]");

            failCount += 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();

            failCount += checkResult(n, actual[0], "sqrtAndRemainder()[0]");

            BigInteger r = up.subtract(n2);

            failCount += checkResult(r, actual[1], "sqrtAndRemainder()[1]");

            return failCount;

        };

        IntStream bits = random.ints(SIZE, 3, Short.MAX_VALUE);

        report("sqrtAndRemainder", bits.mapToObj(x ->

            BigInteger.valueOf(x)).collect(Collectors.summingInt(g)));

    }

    public static void arithmetic(int order) {

        int failCount = 0;

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

            if (!baz.equals(BigInteger.ZERO))

                failCount++;

        }

        report("Arithmetic I for " + order + " bits", failCount);

        failCount = 0;

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

            if (!baz[0].equals(BigInteger.ZERO))

                failCount++;

        }

        report("Arithmetic II for " + order + " bits", failCount);

    }

    /**

     * 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.

     */

    public static void multiplyLarge() {

        int failCount = 0;

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

            if (!multiplyResult.equals(karatsubaMultiplyResult)) {

                failCount++;

            }

        }

        report("multiplyLarge Karatsuba", failCount);

        failCount = 0;

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