Clojure

Multiplication overflow issues around Long/MIN_VALUE

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Minor Minor
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: Release 1.6
  • Component/s: None
  • Labels:
  • Patch:
    Code and Test
  • Approval:
    Ok

Description

Long story short (ha!), there are several related issues where overflow checking doesn't work correctly with Long/MIN_VALUE. The cause of this missed check is that in Java, these both pass:

assertTrue(Long.MIN_VALUE * -1 == Long.MIN_VALUE);
assertTrue(Long.MIN_VALUE / -1 == Long.MIN_VALUE);

This causes the following results in Clojure that do not match their siblings where the order of operands is switched:

user=> (* Long/MIN_VALUE -1)
-922337203685477580 ;; should throw
user=> (*' Long/MIN_VALUE -1)
-9223372036854775808 ;; should be positive
user=> (* Long/MIN_VALUE -1N)
-9223372036854775808N ;; should be positive
user=> (* (bigint Long/MIN_VALUE) -1N)
-9223372036854775808N ;; should be positive

Mailing list discussion here: https://groups.google.com/d/msg/clojure-dev/o1QGR1QK70M/A1KykR9OQqwJ

Patch: min_value_multiplication.diff

Approach: Modifies BigInt.multiply() and multiply/multiplyP in Numbers to take into account Long.MIN_VALUE.

After:

user=> (* Long/MIN_VALUE -1)
ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1390)
user=> (*' Long/MIN_VALUE -1)
9223372036854775808N
user=> (* Long/MIN_VALUE -1N)
9223372036854775808N
user=> (* (bigint Long/MIN_VALUE) -1N)
9223372036854775808N

Screened by: Alex Miller (should also include CLJ-1225, CLJ-1253, CLJ-1254)

Activity

Hide
Rich Hickey added a comment -

missed the ' earlier

Show
Rich Hickey added a comment - missed the ' earlier
Hide
Colin Jones added a comment -

Rich, can you clarify? My understanding is that *' is an auto-promoting operation. For instance, in 1.5.1, *' auto-promotes in the positive direction:

user=> (*' Long/MAX_VALUE Long/MAX_VALUE)
85070591730234615847396907784232501249N

and in the negative:

user=> (*' Long/MIN_VALUE -2)
18446744073709551616N

The only outlier is the one addressed in this ticket. Am I missing something? What should the result be here if not the one given by this patch?

Show
Colin Jones added a comment - Rich, can you clarify? My understanding is that *' is an auto-promoting operation. For instance, in 1.5.1, *' auto-promotes in the positive direction: user=> (*' Long/MAX_VALUE Long/MAX_VALUE) 85070591730234615847396907784232501249N and in the negative: user=> (*' Long/MIN_VALUE -2) 18446744073709551616N The only outlier is the one addressed in this ticket. Am I missing something? What should the result be here if not the one given by this patch?
Hide
Rich Hickey added a comment -

user=> (*' Long/MIN_VALUE -1)
9223372036854775808N

Is wrong - there should be no coercion, this is an overflowing operation.

Show
Rich Hickey added a comment - user=> (*' Long/MIN_VALUE -1) 9223372036854775808N Is wrong - there should be no coercion, this is an overflowing operation.
Hide
Andy Fingerhut added a comment - - edited

I have created CLJ-1225 for the corresponding issues with / and quot with these arguments. I think that Long/MIN_VALUE and -1 should be the only arguments that cause problems for multiplication overflow detection, too, since it is based upon division, and I give some reasons in CLJ-1225 why I believe these are the only arguments that give the numerically wrong answer for the Java division operator / on longs.

Show
Andy Fingerhut added a comment - - edited I have created CLJ-1225 for the corresponding issues with / and quot with these arguments. I think that Long/MIN_VALUE and -1 should be the only arguments that cause problems for multiplication overflow detection, too, since it is based upon division, and I give some reasons in CLJ-1225 why I believe these are the only arguments that give the numerically wrong answer for the Java division operator / on longs.
Hide
Colin Jones added a comment - - edited

I don't have a proof, just a half-hour or so of digging for an alternate case (found none), plus taking a look at what Guava does in checkedMultiply: https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/math/LongMath.java#522

I didn't do the leading zeros optimization they're doing to avoid even the division in the overflow check we already have; that felt like a bigger change, and not one that impacts correctness.

Show
Colin Jones added a comment - - edited I don't have a proof, just a half-hour or so of digging for an alternate case (found none), plus taking a look at what Guava does in checkedMultiply: https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/math/LongMath.java#522 I didn't do the leading zeros optimization they're doing to avoid even the division in the overflow check we already have; that felt like a bigger change, and not one that impacts correctness.
Hide
Andy Fingerhut added a comment - - edited

Is there some proof that Long/MIN_VALUE and -1 is the only pair of values that causes a problem with the way overflow-checking is currently done? It might be, but it would be nice to be sure if a proposed patch relies on that.

Show
Andy Fingerhut added a comment - - edited Is there some proof that Long/MIN_VALUE and -1 is the only pair of values that causes a problem with the way overflow-checking is currently done? It might be, but it would be nice to be sure if a proposed patch relies on that.

People

Vote (1)
Watch (3)

Dates

  • Created:
    Updated:
    Resolved: