/*

 * Copyright (c) 1998, 2015, 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 /lib/testlibrary/

 * @build jdk.testlibrary.*

 * @run main BigIntegerTest

 * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672

 * @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.BigInteger;

import java.util.Random;

/**

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

    }

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

            if (!multiplyResult.equals(toomCookMultiplyResult)) {

                failCount++;

            }

        }

        report("multiplyLarge Toom-Cook", failCount);

    }

    /**

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

     */

    public static void squareLarge() {

        int failCount = 0;

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

            if (!squareResult.equals(karatsubaSquareResult)) {

                failCount++;

            }

        }

        report("squareLarge Karatsuba", failCount);

        failCount = 0;

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

            if (!squareResult.equals(toomCookSquareResult)) {

                failCount++;

            }

        }

        report("squareLarge Toom-Cook", failCount);

    }

    /**

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

     */

    public static void divideLarge() {

        int failCount = 0;

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

            if (divideResult[0].compareTo(bzResult[0]) != 0 ||

                    divideResult[1].compareTo(bzResult[1]) != 0) {

                failCount++;

            }

        }

        report("divideLarge", failCount);

    }

    public static void bitCount() {

        int failCount = 0;

        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;

            }

            if (bigX.bitCount() != bitCount) {

                //System.err.println(x+": "+bitCount+", "+bigX.bitCount());

                failCount++;

            }

        }

        report("Bit Count", failCount);

    }

    public static void bitLength() {

        int failCount = 0;

        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;

            if (bigX.bitLength() != bitLength) {

                //System.err.println(x+": "+bitLength+", "+bigX.bitLength());

                failCount++;

            }

        }

        report("BitLength", failCount);

    }