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