# HG changeset patch # User shade # Date 1448380953 -10800 # Node ID 7b1fea58eefed154ef8d604b8297e44dcd634a67 # Parent 4d5aa33be0a0da7b457faa28257e70fe27b099c6 8136500: Integer/Long getChars and stringSize should be more idiomatic Reviewed-by: igerasim, sherman, psandoz, jrose diff -r 4d5aa33be0a0 -r 7b1fea58eefe jdk/src/java.base/share/classes/java/lang/AbstractStringBuilder.java --- a/jdk/src/java.base/share/classes/java/lang/AbstractStringBuilder.java Tue Nov 24 15:46:14 2015 +0100 +++ b/jdk/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); diff -r 4d5aa33be0a0 -r 7b1fea58eefe jdk/src/java.base/share/classes/java/lang/Integer.java --- a/jdk/src/java.base/share/classes/java/lang/Integer.java Tue Nov 24 15:46:14 2015 +0100 +++ b/jdk/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; } /** diff -r 4d5aa33be0a0 -r 7b1fea58eefe jdk/src/java.base/share/classes/java/lang/Long.java --- a/jdk/src/java.base/share/classes/java/lang/Long.java Tue Nov 24 15:46:14 2015 +0100 +++ b/jdk/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 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; } /** diff -r 4d5aa33be0a0 -r 7b1fea58eefe jdk/test/java/lang/Integer/ToString.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/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); + } + } +} diff -r 4d5aa33be0a0 -r 7b1fea58eefe jdk/test/java/lang/Long/ToString.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/jdk/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); + } + } +}