This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-math.git
The following commit(s) were added to refs/heads/master by this push:
new e0ad6a3ad MathArrays: fix int overflow in the int[] L1 and Linf
distance (#348)
e0ad6a3ad is described below
commit e0ad6a3ad34f38ffe639ef1925e9e177b43f7dee
Author: 陈志谦 <[email protected]>
AuthorDate: Wed Nov 4 04:50:52 2026 +0800
MathArrays: fix int overflow in the int[] L1 and Linf distance (#348)
distance1(int[], int[]) and distanceInf(int[], int[]) computed the
offset of each pair as JdkMath.abs(p1[i] - p2[i]) in int. The difference
of two int values does not always fit in an int, and Math.abs does not
make it fit: abs(Integer.MAX_VALUE - -1) overflows to Integer.MIN_VALUE,
and abs(Integer.MIN_VALUE) is Integer.MIN_VALUE itself. A distance that
should be large was therefore returned as a negative value, or as zero
when the overflow was then "absolute-valued" a second time by max().
Widen the subtraction to long before taking the absolute value, and
accumulate the whole result in a long: distance1 sums the offsets and
distanceInf takes their maximum, and both clamp to Integer.MAX_VALUE only
on return. The accumulator cannot overflow a long — two maximum-length
arrays with Integer.MIN_VALUE in one and Integer.MAX_VALUE in the other
give (2^31-1) * (2^32-1) < 2^63. Distances that fit in an int are
unchanged, and the result is now monotonic in the offsets and independent
of the order of the arguments, which it was not before.
Adds regression tests covering both methods. The doubles overloads are
not affected.
Assisted-By: DeepSeek-V4.1 (deepseek-ai) via DeepSeek Harness
Signed-off-by: simpleqt <[email protected]>
---
.../commons/math4/legacy/core/MathArrays.java | 20 +++++---
.../commons/math4/legacy/core/MathArraysTest.java | 60 ++++++++++++++++++++++
2 files changed, 72 insertions(+), 8 deletions(-)
diff --git
a/commons-math-legacy-core/src/main/java/org/apache/commons/math4/legacy/core/MathArrays.java
b/commons-math-legacy-core/src/main/java/org/apache/commons/math4/legacy/core/MathArrays.java
index 425d3292e..be8803631 100644
---
a/commons-math-legacy-core/src/main/java/org/apache/commons/math4/legacy/core/MathArrays.java
+++
b/commons-math-legacy-core/src/main/java/org/apache/commons/math4/legacy/core/MathArrays.java
@@ -203,16 +203,18 @@ public final class MathArrays {
*
* @param p1 the first point
* @param p2 the second point
- * @return the L<sub>1</sub> distance between the two points
+ * @return the L<sub>1</sub> distance between the two points, or
+ * {@link Integer#MAX_VALUE} if the distance is too large to be
+ * represented as an {@code int}
* @throws DimensionMismatchException if the array lengths differ.
*/
public static int distance1(int[] p1, int[] p2) {
checkEqualLength(p1, p2);
- int sum = 0;
+ long sum = 0;
for (int i = 0; i < p1.length; i++) {
- sum += JdkMath.abs(p1[i] - p2[i]);
+ sum += JdkMath.abs((long) p1[i] - p2[i]);
}
- return sum;
+ return sum > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) sum;
}
/**
@@ -273,16 +275,18 @@ public final class MathArrays {
*
* @param p1 the first point
* @param p2 the second point
- * @return the L<sub>∞</sub> distance between the two points
+ * @return the L<sub>∞</sub> distance between the two points, or
+ * {@link Integer#MAX_VALUE} if the distance is too large to be
+ * represented as an {@code int}
* @throws DimensionMismatchException if the array lengths differ.
*/
public static int distanceInf(int[] p1, int[] p2) {
checkEqualLength(p1, p2);
- int max = 0;
+ long max = 0;
for (int i = 0; i < p1.length; i++) {
- max = JdkMath.max(max, JdkMath.abs(p1[i] - p2[i]));
+ max = JdkMath.max(max, JdkMath.abs((long) p1[i] - p2[i]));
}
- return max;
+ return max > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) max;
}
/**
diff --git
a/commons-math-legacy-core/src/test/java/org/apache/commons/math4/legacy/core/MathArraysTest.java
b/commons-math-legacy-core/src/test/java/org/apache/commons/math4/legacy/core/MathArraysTest.java
index 927e93f5c..9a185110d 100644
---
a/commons-math-legacy-core/src/test/java/org/apache/commons/math4/legacy/core/MathArraysTest.java
+++
b/commons-math-legacy-core/src/test/java/org/apache/commons/math4/legacy/core/MathArraysTest.java
@@ -178,6 +178,66 @@ public class MathArraysTest {
Assert.assertEquals(4, MathArrays.distanceInf(p1, p2));
}
+ /**
+ * The difference of two {@code int} values does not always fit in an
+ * {@code int}: {@code Math.abs(Integer.MAX_VALUE - -1)} overflows to
+ * {@code Integer.MIN_VALUE}, and {@code Integer.MIN_VALUE} negated is
+ * itself. The distance must not be computed in {@code int}, otherwise a
+ * large distance is reported as a negative value or as zero.
+ */
+ @Test
+ public void testL1DistanceIntOverflow() {
+ final int[][] pairs = {
+ {Integer.MIN_VALUE, 0},
+ {Integer.MAX_VALUE, -1},
+ {Integer.MAX_VALUE, Integer.MIN_VALUE},
+ {Integer.MIN_VALUE, 1},
+ };
+ for (final int[] p : pairs) {
+ Assert.assertEquals("distance1 of " + Arrays.toString(p),
+ Integer.MAX_VALUE,
+ MathArrays.distance1(new int[] {p[0]}, new
int[] {p[1]}));
+ }
+
+ // A distance which does not fit in an int is saturated.
+ Assert.assertEquals(Integer.MAX_VALUE,
+ MathArrays.distance1(new int[] {Integer.MAX_VALUE,
0},
+ new int[] {0,
Integer.MAX_VALUE}));
+ // Distances which do fit are unchanged, including the exact boundary.
+ Assert.assertEquals(Integer.MAX_VALUE,
+ MathArrays.distance1(new int[] {Integer.MAX_VALUE},
+ new int[] {0}));
+ Assert.assertEquals(2,
+ MathArrays.distance1(new int[] {1, 1},
+ new int[] {0, 0}));
+ }
+
+ /**
+ * As {@link #testL1DistanceIntOverflow()} for {@code distanceInf}.
+ */
+ @Test
+ public void testLInfDistanceIntOverflow() {
+ final int[][] pairs = {
+ {Integer.MIN_VALUE, 0},
+ {Integer.MAX_VALUE, -1},
+ {Integer.MAX_VALUE, Integer.MIN_VALUE},
+ {Integer.MIN_VALUE, 1},
+ };
+ for (final int[] p : pairs) {
+ Assert.assertEquals("distanceInf of " + Arrays.toString(p),
+ Integer.MAX_VALUE,
+ MathArrays.distanceInf(new int[] {p[0]}, new
int[] {p[1]}));
+ }
+
+ // The result is the largest offset, not the sum of the offsets.
+ Assert.assertEquals(Integer.MAX_VALUE,
+ MathArrays.distanceInf(new int[]
{Integer.MAX_VALUE, 0},
+ new int[] {0,
Integer.MAX_VALUE}));
+ Assert.assertEquals(1,
+ MathArrays.distanceInf(new int[] {1, 1},
+ new int[] {0, 0}));
+ }
+
@Test
public void testCheckOrder() {
MathArrays.checkOrder(new double[] {-15, -5.5, -1, 2, 15},
