changeset 11218:cbe302e284b5

4026465: Provide more byte array constructors for BigInteger Summary: Add two's complement and sign-magnitude constructors for byte arrays with offset and length. Reviewed-by: darcy, alanb, scolebourne
author bpb
date Fri, 09 Jan 2015 17:27:28 -0800
parents eed55a6ebaa3
children efedac7f44ed
files src/java.base/share/classes/java/math/BigInteger.java test/java/math/BigInteger/BigIntegerTest.java
diffstat 2 files changed, 234 insertions(+), 38 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/math/BigInteger.java	Fri Jan 09 11:58:34 2015 -0800
+++ b/src/java.base/share/classes/java/math/BigInteger.java	Fri Jan 09 17:27:28 2015 -0800
@@ -265,24 +265,41 @@
     // Constructors
 
     /**
-     * Translates a byte array containing the two's-complement binary
-     * representation of a BigInteger into a BigInteger.  The input array is
+     * Translates a byte sub-array containing the two's-complement binary
+     * representation of a BigInteger into a BigInteger.  The sub-array is
+     * specified via an offset into the array and a length.  The sub-array is
      * assumed to be in <i>big-endian</i> byte-order: the most significant
-     * byte is in the zeroth element.
+     * byte is the element at index {@code off}.  The {@code val} array is
+     * assumed to be unchanged for the duration of the constructor call.
      *
-     * @param  val big-endian two's-complement binary representation of
-     *         BigInteger.
+     * An {@code IndexOutOfBoundsException} is thrown if the length of the array
+     * {@code val} is non-zero and either {@code off} is negative, {@code len}
+     * is negative, or {@code off+len} is greater than the length of
+     * {@code val}.
+     *
+     * @param  val byte array containing a sub-array which is the big-endian
+     *         two's-complement binary representation of a BigInteger.
+     * @param  off the start offset of the binary representation.
+     * @param  len the number of bytes to use.
      * @throws NumberFormatException {@code val} is zero bytes long.
+     * @throws IndexOutOfBoundsException if the provided array offset and
+     *         length would cause an index into the byte array to be
+     *         negative or greater than or equal to the array length.
+     * @since 1.9
      */
-    public BigInteger(byte[] val) {
-        if (val.length == 0)
+    public BigInteger(byte[] val, int off, int len) {
+        if (val.length == 0) {
             throw new NumberFormatException("Zero length BigInteger");
-
-        if (val[0] < 0) {
-            mag = makePositive(val);
+        } else if ((off < 0) || (off >= val.length) || (len < 0) ||
+                   (len > val.length - off)) { // 0 <= off < val.length
+            throw new IndexOutOfBoundsException();
+        }
+
+        if (val[off] < 0) {
+            mag = makePositive(val, off, len);
             signum = -1;
         } else {
-            mag = stripLeadingZeroBytes(val);
+            mag = stripLeadingZeroBytes(val, off, len);
             signum = (mag.length == 0 ? 0 : 1);
         }
         if (mag.length >= MAX_MAG_LENGTH) {
@@ -291,10 +308,27 @@
     }
 
     /**
+     * Translates a byte array containing the two's-complement binary
+     * representation of a BigInteger into a BigInteger.  The input array is
+     * assumed to be in <i>big-endian</i> byte-order: the most significant
+     * byte is in the zeroth element.  The {@code val} array is assumed to be
+     * unchanged for the duration of the constructor call.
+     *
+     * @param  val big-endian two's-complement binary representation of a
+     *         BigInteger.
+     * @throws NumberFormatException {@code val} is zero bytes long.
+     */
+    public BigInteger(byte[] val) {
+        this(val, 0, val.length);
+    }
+
+    /**
      * This private constructor translates an int array containing the
      * two's-complement binary representation of a BigInteger into a
      * BigInteger. The input array is assumed to be in <i>big-endian</i>
-     * int-order: the most significant int is in the zeroth element.
+     * int-order: the most significant int is in the zeroth element.  The
+     * {@code val} array is assumed to be unchanged for the duration of
+     * the constructor call.
      */
     private BigInteger(int[] val) {
         if (val.length == 0)
@@ -315,24 +349,44 @@
     /**
      * Translates the sign-magnitude representation of a BigInteger into a
      * BigInteger.  The sign is represented as an integer signum value: -1 for
-     * negative, 0 for zero, or 1 for positive.  The magnitude is a byte array
-     * in <i>big-endian</i> byte-order: the most significant byte is in the
-     * zeroth element.  A zero-length magnitude array is permissible, and will
-     * result in a BigInteger value of 0, whether signum is -1, 0 or 1.
+     * negative, 0 for zero, or 1 for positive.  The magnitude is a sub-array of
+     * a byte array in <i>big-endian</i> byte-order: the most significant byte
+     * is the element at index {@code off}.  A zero value of the length
+     * {@code len} is permissible, and will result in a BigInteger value of 0,
+     * whether signum is -1, 0 or 1.  The {@code magnitude} array is assumed to
+     * be unchanged for the duration of the constructor call.
+     *
+     * An {@code IndexOutOfBoundsException} is thrown if the length of the array
+     * {@code magnitude} is non-zero and either {@code off} is negative,
+     * {@code len} is negative, or {@code off+len} is greater than the length of
+     * {@code magnitude}.
      *
      * @param  signum signum of the number (-1 for negative, 0 for zero, 1
      *         for positive).
      * @param  magnitude big-endian binary representation of the magnitude of
      *         the number.
+     * @param  off the start offset of the binary representation.
+     * @param  len the number of bytes to use.
      * @throws NumberFormatException {@code signum} is not one of the three
      *         legal values (-1, 0, and 1), or {@code signum} is 0 and
      *         {@code magnitude} contains one or more non-zero bytes.
+     * @throws IndexOutOfBoundsException if the provided array offset and
+     *         length would cause an index into the byte array to be
+     *         negative or greater than or equal to the array length.
+     * @since 1.9
      */
-    public BigInteger(int signum, byte[] magnitude) {
-        this.mag = stripLeadingZeroBytes(magnitude);
-
-        if (signum < -1 || signum > 1)
+    public BigInteger(int signum, byte[] magnitude, int off, int len) {
+        if (signum < -1 || signum > 1) {
             throw(new NumberFormatException("Invalid signum value"));
+        } else if ((off < 0) || (len < 0) ||
+            (len > 0 &&
+                ((off >= magnitude.length) ||
+                 (len > magnitude.length - off)))) { // 0 <= off < magnitude.length
+            throw new IndexOutOfBoundsException();
+        }
+
+        // stripLeadingZeroBytes() returns a zero length array if len == 0
+        this.mag = stripLeadingZeroBytes(magnitude, off, len);
 
         if (this.mag.length == 0) {
             this.signum = 0;
@@ -347,10 +401,33 @@
     }
 
     /**
+     * Translates the sign-magnitude representation of a BigInteger into a
+     * BigInteger.  The sign is represented as an integer signum value: -1 for
+     * negative, 0 for zero, or 1 for positive.  The magnitude is a byte array
+     * in <i>big-endian</i> byte-order: the most significant byte is the
+     * zeroth element.  A zero-length magnitude array is permissible, and will
+     * result in a BigInteger value of 0, whether signum is -1, 0 or 1.  The
+     * {@code magnitude} array is assumed to be unchanged for the duration of
+     * the constructor call.
+     *
+     * @param  signum signum of the number (-1 for negative, 0 for zero, 1
+     *         for positive).
+     * @param  magnitude big-endian binary representation of the magnitude of
+     *         the number.
+     * @throws NumberFormatException {@code signum} is not one of the three
+     *         legal values (-1, 0, and 1), or {@code signum} is 0 and
+     *         {@code magnitude} contains one or more non-zero bytes.
+     */
+    public BigInteger(int signum, byte[] magnitude) {
+         this(signum, magnitude, 0, magnitude.length);
+    }
+
+    /**
      * A constructor for internal use that translates the sign-magnitude
      * representation of a BigInteger into a BigInteger. It checks the
      * arguments and copies the magnitude so this constructor would be
-     * safe for external use.
+     * safe for external use.  The {@code magnitude} array is assumed to be
+     * unchanged for the duration of the constructor call.
      */
     private BigInteger(int signum, int[] magnitude) {
         this.mag = stripLeadingZeroInts(magnitude);
@@ -467,7 +544,9 @@
 
     /*
      * Constructs a new BigInteger using a char array with radix=10.
-     * Sign is precalculated outside and not allowed in the val.
+     * Sign is precalculated outside and not allowed in the val. The {@code val}
+     * array is assumed to be unchanged for the duration of the constructor
+     * call.
      */
     BigInteger(char[] val, int sign, int len) {
         int cursor = 0, numDigits;
@@ -1035,11 +1114,12 @@
 
     /**
      * This private constructor is for internal use and assumes that its
-     * arguments are correct.
+     * arguments are correct.  The {@code magnitude} array is assumed to be
+     * unchanged for the duration of the constructor call.
      */
     private BigInteger(byte[] magnitude, int signum) {
         this.signum = (magnitude.length == 0 ? 0 : signum);
-        this.mag = stripLeadingZeroBytes(magnitude);
+        this.mag = stripLeadingZeroBytes(magnitude, 0, magnitude.length);
         if (mag.length >= MAX_MAG_LENGTH) {
             checkRange();
         }
@@ -3977,18 +4057,18 @@
     /**
      * Returns a copy of the input array stripped of any leading zero bytes.
      */
-    private static int[] stripLeadingZeroBytes(byte a[]) {
-        int byteLength = a.length;
+    private static int[] stripLeadingZeroBytes(byte a[], int off, int len) {
+        int indexBound = off + len;
         int keep;
 
         // Find first nonzero byte
-        for (keep = 0; keep < byteLength && a[keep] == 0; keep++)
+        for (keep = off; keep < indexBound && a[keep] == 0; keep++)
             ;
 
         // Allocate new array and copy relevant part of input array
-        int intLength = ((byteLength - keep) + 3) >>> 2;
+        int intLength = ((indexBound - keep) + 3) >>> 2;
         int[] result = new int[intLength];
-        int b = byteLength - 1;
+        int b = indexBound - 1;
         for (int i = intLength-1; i >= 0; i--) {
             result[i] = a[b--] & 0xff;
             int bytesRemaining = b - keep + 1;
@@ -4003,27 +4083,27 @@
      * Takes an array a representing a negative 2's-complement number and
      * returns the minimal (no leading zero bytes) unsigned whose value is -a.
      */
-    private static int[] makePositive(byte a[]) {
+    private static int[] makePositive(byte a[], int off, int len) {
         int keep, k;
-        int byteLength = a.length;
+        int indexBound = off + len;
 
         // Find first non-sign (0xff) byte of input
-        for (keep=0; keep < byteLength && a[keep] == -1; keep++)
+        for (keep=off; keep < indexBound && a[keep] == -1; keep++)
             ;
 
 
         /* Allocate output array.  If all non-sign bytes are 0x00, we must
          * allocate space for one extra output byte. */
-        for (k=keep; k < byteLength && a[k] == 0; k++)
+        for (k=keep; k < indexBound && a[k] == 0; k++)
             ;
 
-        int extraByte = (k == byteLength) ? 1 : 0;
-        int intLength = ((byteLength - keep + extraByte) + 3) >>> 2;
+        int extraByte = (k == indexBound) ? 1 : 0;
+        int intLength = ((indexBound - keep + extraByte) + 3) >>> 2;
         int result[] = new int[intLength];
 
         /* Copy one's complement of input into output, leaving extra
          * byte (if it exists) == 0x00 */
-        int b = byteLength - 1;
+        int b = indexBound - 1;
         for (int i = intLength-1; i >= 0; i--) {
             result[i] = a[b--] & 0xff;
             int numBytesToTransfer = Math.min(3, b-keep+1);
@@ -4248,7 +4328,7 @@
                 message = "BigInteger: Signum not present in stream";
             throw new java.io.StreamCorruptedException(message);
         }
-        int[] mag = stripLeadingZeroBytes(magnitude);
+        int[] mag = stripLeadingZeroBytes(magnitude, 0, magnitude.length);
         if ((mag.length == 0) != (sign == 0)) {
             String message = "BigInteger: signum-magnitude mismatch";
             if (fields.defaulted("magnitude"))
--- a/test/java/math/BigInteger/BigIntegerTest.java	Fri Jan 09 11:58:34 2015 -0800
+++ b/test/java/math/BigInteger/BigIntegerTest.java	Fri Jan 09 17:27:28 2015 -0800
@@ -23,7 +23,7 @@
 
 /*
  * @test
- * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946
+ * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465
  * @summary tests methods in BigInteger
  * @run main/timeout=400 BigIntegerTest
  * @author madbot
@@ -89,6 +89,120 @@
     static Random rnd = new Random();
     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];
+        rnd.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];
+        rnd.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 + rnd.nextInt(336), 4, rnd);
+
+            byte[] refArray = reference.toByteArray();
+            int refLen = refArray.length;
+            int factor = rnd.nextInt(5);
+            int objLen = refArray.length + factor*rnd.nextInt(refArray.length) + 1;
+            int offset = rnd.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 = rnd.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;
 
@@ -961,6 +1075,8 @@
         if (args.length >3)
             order4 = (int)((Integer.parseInt(args[3]))* 3.333);
 
+        constructor();
+
         prime();
         nextProbablePrime();