changeset 13119:715972927a17

8136500: Integer/Long getChars and stringSize should be more idiomatic Reviewed-by: igerasim, sherman, psandoz, jrose
author shade
date Tue, 24 Nov 2015 19:02:33 +0300
parents 6ad5d252b55c
children db013eafc5c3
files src/java.base/share/classes/java/lang/AbstractStringBuilder.java src/java.base/share/classes/java/lang/Integer.java src/java.base/share/classes/java/lang/Long.java test/java/lang/Integer/ToString.java test/java/lang/Long/ToString.java
diffstat 5 files changed, 302 insertions(+), 128 deletions(-) [+]
line wrap: on
line diff
--- a/src/java.base/share/classes/java/lang/AbstractStringBuilder.java	Tue Nov 24 15:46:14 2015 +0100
+++ b/src/java.base/share/classes/java/lang/AbstractStringBuilder.java	Tue Nov 24 19:02:33 2015 +0300
@@ -732,13 +732,7 @@
      * @return  a reference to this object.
      */
     public AbstractStringBuilder append(int i) {
-        if (i == Integer.MIN_VALUE) {
-            append("-2147483648");
-            return this;
-        }
-        int appendedLength = (i < 0) ? Integer.stringSize(-i) + 1
-                                     : Integer.stringSize(i);
-        int spaceNeeded = count + appendedLength;
+        int spaceNeeded = count + Integer.stringSize(i);
         ensureCapacityInternal(spaceNeeded);
         if (isLatin1()) {
             Integer.getChars(i, spaceNeeded, value);
@@ -764,13 +758,7 @@
      * @return  a reference to this object.
      */
     public AbstractStringBuilder append(long l) {
-        if (l == Long.MIN_VALUE) {
-            append("-9223372036854775808");
-            return this;
-        }
-        int appendedLength = (l < 0) ? Long.stringSize(-l) + 1
-                                     : Long.stringSize(l);
-        int spaceNeeded = count + appendedLength;
+        int spaceNeeded = count + Long.stringSize(l);
         ensureCapacityInternal(spaceNeeded);
         if (isLatin1()) {
             Long.getChars(l, spaceNeeded, value);
--- a/src/java.base/share/classes/java/lang/Integer.java	Tue Nov 24 15:46:14 2015 +0100
+++ b/src/java.base/share/classes/java/lang/Integer.java	Tue Nov 24 19:02:33 2015 +0300
@@ -396,7 +396,7 @@
         } while (charPos > offset);
     }
 
-    static final char [] DigitTens = {
+    static final byte[] DigitTens = {
         '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
         '1', '1', '1', '1', '1', '1', '1', '1', '1', '1',
         '2', '2', '2', '2', '2', '2', '2', '2', '2', '2',
@@ -409,7 +409,7 @@
         '9', '9', '9', '9', '9', '9', '9', '9', '9', '9',
         } ;
 
-    static final char [] DigitOnes = {
+    static final byte[] DigitOnes = {
         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
@@ -422,21 +422,6 @@
         '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
         } ;
 
-        // I use the "invariant division by multiplication" trick to
-        // accelerate Integer.toString.  In particular we want to
-        // avoid division by 10.
-        //
-        // The "trick" has roughly the same performance characteristics
-        // as the "classic" Integer.toString code on a non-JIT VM.
-        // The trick avoids .rem and .div calls but has a longer code
-        // path and is thus dominated by dispatch overhead.  In the
-        // JIT case the dispatch overhead doesn't exist and the
-        // "trick" is considerably faster than the classic code.
-        //
-        // RE:  Division by Invariant Integers using Multiplication
-        //      T Gralund, P Montgomery
-        //      ACM PLDI 1994
-        //
 
     /**
      * Returns a {@code String} object representing the
@@ -450,9 +435,7 @@
      */
     @HotSpotIntrinsicCandidate
     public static String toString(int i) {
-        if (i == Integer.MIN_VALUE)
-            return "-2147483648";
-        int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
+        int size = stringSize(i);
         if (COMPACT_STRINGS) {
             byte[] buf = new byte[size];
             getChars(i, size, buf);
@@ -489,84 +472,105 @@
      * digit at the specified index (exclusive), and working
      * backwards from there.
      *
-     * Will fail if i == Integer.MIN_VALUE
+     * @implNote This method converts positive inputs into negative
+     * values, to cover the Integer.MIN_VALUE case. Converting otherwise
+     * (negative to positive) will expose -Integer.MIN_VALUE that overflows
+     * integer.
      */
     static void getChars(int i, int index, byte[] buf) {
         int q, r;
         int charPos = index;
-        char sign = 0;
 
-        if (i < 0) {
-            sign = '-';
+        boolean negative = i < 0;
+        if (!negative) {
             i = -i;
         }
 
         // Generate two digits per iteration
-        while (i >= 65536) {
+        while (i <= -100) {
             q = i / 100;
-        // really: r = i - (q * 100);
-            r = i - ((q << 6) + (q << 5) + (q << 2));
+            r = (q * 100) - i;
             i = q;
-            buf [--charPos] = (byte)DigitOnes[r];
-            buf [--charPos] = (byte)DigitTens[r];
+            buf[--charPos] = DigitOnes[r];
+            buf[--charPos] = DigitTens[r];
         }
 
-        // Fall thru to fast mode for smaller numbers
-        // assert(i <= 65536, i);
-        for (;;) {
-            q = (i * 52429) >>> (16+3);
-            r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
-            buf [--charPos] = (byte)digits [r];
-            i = q;
-            if (i == 0) break;
+        // We know there are at most two digits left at this point.
+        q = i / 10;
+        r = (q * 10) - i;
+        buf[--charPos] = (byte)('0' + r);
+
+        // Whatever left is the remaining digit.
+        if (q < 0) {
+            buf[--charPos] = (byte)('0' - q);
         }
-        if (sign != 0) {
-            buf [--charPos] = (byte)sign;
+
+        if (negative) {
+            buf[--charPos] = (byte)'-';
         }
     }
 
     static void getCharsUTF16(int i, int index, byte[] buf) {
         int q, r;
         int charPos = index;
-        char sign = 0;
 
-        if (i < 0) {
-            sign = '-';
+        boolean negative = (i < 0);
+        if (!negative) {
             i = -i;
         }
 
-        // Generate two digits per iteration
-        while (i >= 65536) {
+        // Get 2 digits/iteration using ints
+        while (i <= -100) {
             q = i / 100;
-        // really: r = i - (q * 100);
-            r = i - ((q << 6) + (q << 5) + (q << 2));
+            r = (q * 100) - i;
             i = q;
             StringUTF16.putChar(buf, --charPos, DigitOnes[r]);
             StringUTF16.putChar(buf, --charPos, DigitTens[r]);
         }
 
-        // Fall thru to fast mode for smaller numbers
-        // assert(i <= 65536, i);
-        for (;;) {
-            q = (i * 52429) >>> (16+3);
-            r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
-            StringUTF16.putChar(buf, --charPos, Integer.digits[r]);
-            i = q;
-            if (i == 0) break;
+        // We know there are at most two digits left at this point.
+        q = i / 10;
+        r = (q * 10) - i;
+        StringUTF16.putChar(buf, --charPos, '0' + r);
+
+        // Whatever left is the remaining digit.
+        if (q < 0) {
+            StringUTF16.putChar(buf, --charPos, '0' - q);
         }
-        if (sign != 0) {
-            StringUTF16.putChar(buf, --charPos, sign);
+
+        if (negative) {
+            StringUTF16.putChar(buf, --charPos, '-');
         }
     }
 
+    // Left here for compatibility reasons, see JDK-8143900.
     static final int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
                                       99999999, 999999999, Integer.MAX_VALUE };
 
-    // Requires positive x
+    /**
+     * Returns the string representation size for a given int value.
+     *
+     * @param x int value
+     * @return string size
+     *
+     * @implNote There are other ways to compute this: e.g. binary search,
+     * but values are biased heavily towards zero, and therefore linear search
+     * wins. The iteration results are also routinely inlined in the generated
+     * code after loop unrolling.
+     */
     static int stringSize(int x) {
-        for (int i=0; ; i++)
-            if (x <= sizeTable[i])
-                return i+1;
+        int d = 1;
+        if (x >= 0) {
+            d = 0;
+            x = -x;
+        }
+        int p = -10;
+        for (int i = 1; i < 10; i++) {
+            if (x > p)
+                return i + d;
+            p = 10 * p;
+        }
+        return 10 + d;
     }
 
     /**
--- a/src/java.base/share/classes/java/lang/Long.java	Tue Nov 24 15:46:14 2015 +0100
+++ b/src/java.base/share/classes/java/lang/Long.java	Tue Nov 24 19:02:33 2015 +0300
@@ -448,9 +448,7 @@
      * @return  a string representation of the argument in base&nbsp;10.
      */
     public static String toString(long i) {
-        if (i == Long.MIN_VALUE)
-            return "-9223372036854775808";
-        int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
+        int size = stringSize(i);
         if (COMPACT_STRINGS) {
             byte[] buf = new byte[size];
             getChars(i, size, buf);
@@ -481,58 +479,59 @@
     }
 
     /**
-     * Places characters representing the integer i into the
+     * Places characters representing the long i into the
      * character array buf. The characters are placed into
      * the buffer backwards starting with the least significant
      * digit at the specified index (exclusive), and working
      * backwards from there.
      *
-     * Will fail if i == Long.MIN_VALUE
+     * @implNote This method converts positive inputs into negative
+     * values, to cover the Long.MIN_VALUE case. Converting otherwise
+     * (negative to positive) will expose -Long.MIN_VALUE that overflows
+     * long.
      */
     static void getChars(long i, int index, byte[] buf) {
         long q;
         int r;
         int charPos = index;
-        char sign = 0;
 
-        if (i < 0) {
-            sign = '-';
+        boolean negative = (i < 0);
+        if (!negative) {
             i = -i;
         }
 
         // Get 2 digits/iteration using longs until quotient fits into an int
-        while (i > Integer.MAX_VALUE) {
+        while (i <= Integer.MIN_VALUE) {
             q = i / 100;
-            // really: r = i - (q * 100);
-            r = (int)(i - ((q << 6) + (q << 5) + (q << 2)));
+            r = (int)((q * 100) - i);
             i = q;
-            buf[--charPos] = (byte)Integer.DigitOnes[r];
-            buf[--charPos] = (byte)Integer.DigitTens[r];
+            buf[--charPos] = Integer.DigitOnes[r];
+            buf[--charPos] = Integer.DigitTens[r];
         }
 
         // Get 2 digits/iteration using ints
         int q2;
         int i2 = (int)i;
-        while (i2 >= 65536) {
+        while (i2 <= -100) {
             q2 = i2 / 100;
-            // really: r = i2 - (q * 100);
-            r = i2 - ((q2 << 6) + (q2 << 5) + (q2 << 2));
+            r  = (q2 * 100) - i2;
             i2 = q2;
-            buf[--charPos] = (byte)Integer.DigitOnes[r];
-            buf[--charPos] = (byte)Integer.DigitTens[r];
+            buf[--charPos] = Integer.DigitOnes[r];
+            buf[--charPos] = Integer.DigitTens[r];
         }
 
-        // Fall thru to fast mode for smaller numbers
-        // assert(i2 <= 65536, i2);
-        for (;;) {
-            q2 = (i2 * 52429) >>> (16+3);
-            r = i2 - ((q2 << 3) + (q2 << 1));  // r = i2-(q2*10) ...
-            buf[--charPos] = (byte)Integer.digits[r];
-            i2 = q2;
-            if (i2 == 0) break;
+        // We know there are at most two digits left at this point.
+        q2 = i2 / 10;
+        r  = (q2 * 10) - i2;
+        buf[--charPos] = (byte)('0' + r);
+
+        // Whatever left is the remaining digit.
+        if (q2 < 0) {
+            buf[--charPos] = (byte)('0' - q2);
         }
-        if (sign != 0) {
-            buf[--charPos] = (byte)sign;
+
+        if (negative) {
+            buf[--charPos] = (byte)'-';
         }
     }
 
@@ -540,18 +539,16 @@
         long q;
         int r;
         int charPos = index;
-        char sign = 0;
 
-        if (i < 0) {
-            sign = '-';
+        boolean negative = (i < 0);
+        if (!negative) {
             i = -i;
         }
 
         // Get 2 digits/iteration using longs until quotient fits into an int
-        while (i > Integer.MAX_VALUE) {
+        while (i <= Integer.MIN_VALUE) {
             q = i / 100;
-            // really: r = i - (q * 100);
-            r = (int)(i - ((q << 6) + (q << 5) + (q << 2)));
+            r = (int)((q * 100) - i);
             i = q;
             StringUTF16.putChar(buf, --charPos, Integer.DigitOnes[r]);
             StringUTF16.putChar(buf, --charPos, Integer.DigitTens[r]);
@@ -560,38 +557,53 @@
         // Get 2 digits/iteration using ints
         int q2;
         int i2 = (int)i;
-        while (i2 >= 65536) {
+        while (i2 <= -100) {
             q2 = i2 / 100;
-            // really: r = i2 - (q * 100);
-            r = i2 - ((q2 << 6) + (q2 << 5) + (q2 << 2));
+            r  = (q2 * 100) - i2;
             i2 = q2;
             StringUTF16.putChar(buf, --charPos, Integer.DigitOnes[r]);
             StringUTF16.putChar(buf, --charPos, Integer.DigitTens[r]);
         }
 
-        // Fall thru to fast mode for smaller numbers
-        // assert(i2 <= 65536, i2);
-        for (;;) {
-            q2 = (i2 * 52429) >>> (16+3);
-            r = i2 - ((q2 << 3) + (q2 << 1));  // r = i2-(q2*10) ...
-            StringUTF16.putChar(buf, --charPos, Integer.digits[r]);
-            i2 = q2;
-            if (i2 == 0) break;
+        // We know there are at most two digits left at this point.
+        q2 = i2 / 10;
+        r  = (q2 * 10) - i2;
+        StringUTF16.putChar(buf, --charPos, '0' + r);
+
+        // Whatever left is the remaining digit.
+        if (q2 < 0) {
+            StringUTF16.putChar(buf, --charPos, '0' - q2);
         }
-        if (sign != 0) {
-            StringUTF16.putChar(buf, --charPos, sign);
+
+        if (negative) {
+            StringUTF16.putChar(buf, --charPos, '-');
         }
     }
 
-    // Requires positive x
+    /**
+     * Returns the string representation size for a given long value.
+     *
+     * @param x long value
+     * @return string size
+     *
+     * @implNote There are other ways to compute this: e.g. binary search,
+     * but values are biased heavily towards zero, and therefore linear search
+     * wins. The iteration results are also routinely inlined in the generated
+     * code after loop unrolling.
+     */
     static int stringSize(long x) {
-        long p = 10;
-        for (int i=1; i<19; i++) {
-            if (x < p)
-                return i;
-            p = 10*p;
+        int d = 1;
+        if (x >= 0) {
+            d = 0;
+            x = -x;
         }
-        return 19;
+        long p = -10;
+        for (int i = 1; i < 19; i++) {
+            if (x > p)
+                return i + d;
+            p = 10 * p;
+        }
+        return 19 + d;
     }
 
     /**
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/lang/Integer/ToString.java	Tue Nov 24 19:02:33 2015 +0300
@@ -0,0 +1,85 @@
+/*
+ * Copyright (c) 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
+ * @bug 8136500
+ * @summary Test Integer.toString method
+ */
+
+public class ToString {
+
+    public static void main(String[] args) throws Exception {
+        test("-2147483648", Integer.MIN_VALUE);
+        test("2147483647",  Integer.MAX_VALUE);
+        test("0", 0);
+
+        // Wiggle around the exponentially increasing base.
+        final int LIMIT = (1 << 15);
+        int base = 10000;
+        while (base < Integer.MAX_VALUE / 10) {
+            for (int d = -LIMIT; d < LIMIT; d++) {
+                int c = base + d;
+                if (c > 0) {
+                    buildAndTest(c);
+                }
+            }
+            base *= 10;
+        }
+
+        for (int c = 1; c < LIMIT; c++) {
+            buildAndTest(Integer.MAX_VALUE - LIMIT + c);
+        }
+    }
+
+    private static void buildAndTest(int c) {
+        if (c <= 0) {
+            throw new IllegalArgumentException("Test bug: can only handle positives, " + c);
+        }
+
+        StringBuilder sbN = new StringBuilder();
+        StringBuilder sbP = new StringBuilder();
+
+        int t = c;
+        while (t > 0) {
+            char digit = (char) ('0' + (t % 10));
+            sbN.append(digit);
+            sbP.append(digit);
+            t = t / 10;
+        }
+
+        sbN.append("-");
+        sbN.reverse();
+        sbP.reverse();
+
+        test(sbN.toString(), -c);
+        test(sbP.toString(), c);
+    }
+
+    private static void test(String expected, int value) {
+        String actual = Integer.toString(value);
+        if (!expected.equals(actual)) {
+            throw new RuntimeException("Expected " + expected + ", but got " + actual);
+        }
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/lang/Long/ToString.java	Tue Nov 24 19:02:33 2015 +0300
@@ -0,0 +1,85 @@
+/*
+ * Copyright (c) 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
+ * @bug 8136500
+ * @summary Test Long.toString method
+ */
+
+public class ToString {
+
+    public static void main(String[] args) throws Exception {
+        test("-9223372036854775808", Long.MIN_VALUE);
+        test("9223372036854775807",  Long.MAX_VALUE);
+        test("0", 0);
+
+        // Wiggle around the exponentially increasing base.
+        final int LIMIT = (1 << 15);
+        long base = 10000;
+        while (base < Long.MAX_VALUE / 10) {
+            for (int d = -LIMIT; d < LIMIT; d++) {
+                long c = base + d;
+                if (c > 0) {
+                    buildAndTest(c);
+                }
+            }
+            base *= 10;
+        }
+
+        for (int c = 1; c < LIMIT; c++) {
+            buildAndTest(Long.MAX_VALUE - LIMIT + c);
+        }
+    }
+
+    private static void buildAndTest(long c) {
+        if (c <= 0) {
+            throw new IllegalArgumentException("Test bug: can only handle positives, " + c);
+        }
+
+        StringBuilder sbN = new StringBuilder();
+        StringBuilder sbP = new StringBuilder();
+
+        long t = c;
+        while (t > 0) {
+            char digit = (char) ('0' + (t % 10));
+            sbN.append(digit);
+            sbP.append(digit);
+            t = t / 10;
+        }
+
+        sbN.append("-");
+        sbN.reverse();
+        sbP.reverse();
+
+        test(sbN.toString(), -c);
+        test(sbP.toString(), c);
+    }
+
+    private static void test(String expected, long value) {
+        String actual = Long.toString(value);
+        if (!expected.equals(actual)) {
+            throw new RuntimeException("Expected " + expected + ", but got " + actual);
+        }
+    }
+}