# HG changeset patch # User bpb # Date 1389811222 28800 # Node ID ae235c2bbac937b8e93c5bd82c6e1b78fee8e8bf # Parent cf7ce8b79a2544e2d66b6556cddd6bb78c771154 8030814: Long.parseUnsignedLong should throw exception on too large input Summary: Change test for overflow of unsigned long Reviewed-by: darcy, psandoz Contributed-by: Dmitry Nadezhin diff -r cf7ce8b79a25 -r ae235c2bbac9 jdk/src/share/classes/java/lang/Long.java --- a/jdk/src/share/classes/java/lang/Long.java Wed Jan 15 00:03:38 2014 -0800 +++ b/jdk/src/share/classes/java/lang/Long.java Wed Jan 15 10:40:22 2014 -0800 @@ -700,21 +700,58 @@ throw new NumberFormatException("Bad digit at end of " + s); } long result = first * radix + second; - if (compareUnsigned(result, first) < 0) { + + /* + * Test leftmost bits of multiprecision extension of first*radix + * for overflow. The number of bits needed is defined by + * GUARD_BIT = ceil(log2(Character.MAX_RADIX)) + 1 = 7. Then + * int guard = radix*(int)(first >>> (64 - GUARD_BIT)) and + * overflow is tested by splitting guard in the ranges + * guard < 92, 92 <= guard < 128, and 128 <= guard, where + * 92 = 128 - Character.MAX_RADIX. Note that guard cannot take + * on a value which does not include a prime factor in the legal + * radix range. + */ + int guard = radix * (int) (first >>> 57); + if (guard >= 128 || + (result >= 0 && guard >= 128 - Character.MAX_RADIX)) { /* - * The maximum unsigned value, (2^64)-1, takes at - * most one more digit to represent than the - * maximum signed value, (2^63)-1. Therefore, - * parsing (len - 1) digits will be appropriately - * in-range of the signed parsing. In other - * words, if parsing (len -1) digits overflows - * signed parsing, parsing len digits will - * certainly overflow unsigned parsing. + * For purposes of exposition, the programmatic statements + * below should be taken to be multi-precision, i.e., not + * subject to overflow. + * + * A) Condition guard >= 128: + * If guard >= 128 then first*radix >= 2^7 * 2^57 = 2^64 + * hence always overflow. + * + * B) Condition guard < 92: + * Define left7 = first >>> 57. + * Given first = (left7 * 2^57) + (first & (2^57 - 1)) then + * result <= (radix*left7)*2^57 + radix*(2^57 - 1) + second. + * Thus if radix*left7 < 92, radix <= 36, and second < 36, + * then result < 92*2^57 + 36*(2^57 - 1) + 36 = 2^64 hence + * never overflow. * - * The compareUnsigned check above catches - * situations where an unsigned overflow occurs - * incorporating the contribution of the final - * digit. + * C) Condition 92 <= guard < 128: + * first*radix + second >= radix*left7*2^57 + second + * so that first*radix + second >= 92*2^57 + 0 > 2^63 + * + * D) Condition guard < 128: + * radix*first <= (radix*left7) * 2^57 + radix*(2^57 - 1) + * so + * radix*first + second <= (radix*left7) * 2^57 + radix*(2^57 - 1) + 36 + * thus + * radix*first + second < 128 * 2^57 + 36*2^57 - radix + 36 + * whence + * radix*first + second < 2^64 + 2^6*2^57 = 2^64 + 2^63 + * + * E) Conditions C, D, and result >= 0: + * C and D combined imply the mathematical result + * 2^63 < first*radix + second < 2^64 + 2^63. The lower + * bound is therefore negative as a signed long, but the + * upper bound is too small to overflow again after the + * signed long overflows to positive above 2^64 - 1. Hence + * result >= 0 implies overflow given C and D. */ throw new NumberFormatException(String.format("String value %s exceeds " + "range of unsigned long.", s)); diff -r cf7ce8b79a25 -r ae235c2bbac9 jdk/test/java/lang/Long/Unsigned.java --- a/jdk/test/java/lang/Long/Unsigned.java Wed Jan 15 00:03:38 2014 -0800 +++ b/jdk/test/java/lang/Long/Unsigned.java Wed Jan 15 10:40:22 2014 -0800 @@ -23,7 +23,7 @@ /* * @test - * @bug 4504839 4215269 6322074 + * @bug 4504839 4215269 6322074 8030814 * @summary Basic tests for unsigned operations * @author Joseph D. Darcy */ @@ -310,6 +310,55 @@ } } + // test case known at one time to fail + errors += testUnsignedOverflow("1234567890abcdef1", 16, true); + + // largest value with guard = 91 = 13*7; radix = 13 + errors += testUnsignedOverflow("196a78a44c3bba320c", 13, false); + + // smallest value with guard = 92 = 23*2*2; radix = 23 + errors += testUnsignedOverflow("137060c6g1c1dg0", 23, false); + + // guard in [92,98]: no overflow + + // one less than smallest guard value to overflow: guard = 99 = 11*3*3, radix = 33 + errors += testUnsignedOverflow("b1w8p7j5q9r6f", 33, false); + + // smallest guard value to overflow: guard = 99 = 11*3*3, radix = 33 + errors += testUnsignedOverflow("b1w8p7j5q9r6g", 33, true); + + // test overflow of overflow + BigInteger maxUnsignedLong = + BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE); + for (int radix = Character.MIN_RADIX; radix <= Character.MAX_RADIX; radix++) { + BigInteger quotient = maxUnsignedLong.divide(BigInteger.valueOf(radix)); + for (int addend = 2; addend <= radix; addend++) { + BigInteger b = quotient.multiply(BigInteger.valueOf(radix + addend)); + errors += testUnsignedOverflow(b.toString(radix), radix, b.compareTo(maxUnsignedLong) > 0); + } + } + + return errors; + } + + // test for missing or unexpected unsigned overflow exception + private static int testUnsignedOverflow(String s, int radix, boolean exception) { + int errors = 0; + long result; + try { + result = Long.parseUnsignedLong(s, radix); + if (exception) { + System.err.printf("Unexpected result %d for Long.parseUnsignedLong(%s,%d)\n", + result, s, radix); + errors++; + } + } catch (NumberFormatException nfe) { + if (!exception) { + System.err.printf("Unexpected exception %s for Long.parseUnsignedLong(%s,%d)\n", + nfe.toString(), s, radix); + errors++; + } + } return errors; }