MultidimensionalCounter: unchecked int overflow makes getSize(), getCount() and the iterator silently wrong for in-contract input

[ser10us]

MultidimensionalCounter computes its total number of slots as an unchecked int product and validates it with if (tS <= 0) throw. That guard rejects a product that wraps to a negative value but not one that wraps to a positive value, so an all-positive (fully in-contract) size vector can produce a totalSize unrelated to the space that was requested. getSize(), getCount(int...), getCounts(int) and the iterator are all silently wrong as a consequence.

Affected: org.hipparchus:hipparchus-core:4.0.3 (current release) and earlier. org.hipparchus.util, hipparchus-core.

The defect

The constructor:

int tS = size[last];
for (int i = 0; i < last; i++) {
    int count = 1;
    for (int j = i + 1; j < dimension; j++) {
        count *= size[j];
    }
    uniCounterOffset[i] = count;
    tS *= size[i];                 // unchecked
}
uniCounterOffset[last] = 0;

if (tS <= 0) {                     // rejects a NEGATIVE wrap only
    throw new MathIllegalArgumentException(LocalizedCoreFormats.NUMBER_TOO_SMALL_BOUND_EXCLUDED, tS, 0);
}

totalSize = tS;

getCount(int...) has the same shape, and is arguably worse because it range-checks each index immediately before feeding it into an unchecked product:

int count = 0;
for (int i = 0; i < dimension; i++) {
    final int index = c[i];
    MathUtils.checkRangeInclusive(index, 0, size[i] - 1);
    count += uniCounterOffset[i] * c[i];   // unchecked, after validating
}
return count + c[last];

Observed behaviour

[A] true product exceeds Integer.MAX_VALUE -- accepted or rejected?

  65537x65536        getSize()=65536       ACCEPTED, getSize() unrelated to the true size 4295032832
  46341x46341        rejected -> MathIllegalArgumentException
  1000x1000x4295     getSize()=32704       ACCEPTED, getSize() unrelated to the true size 4295000000
  641x6700417        getSize()=1           ACCEPTED, getSize() unrelated to the true size 4294967297
  2x2147483647       rejected -> MathIllegalArgumentException
  3x1431655766       getSize()=2           ACCEPTED, getSize() unrelated to the true size 4294967298

[B] control: sizes that DO fit are exact, so the class is not broken generally

  3x4x5              getSize()=60          ok
  46340x46340        getSize()=2147395600  ok
  2147483647         getSize()=2147483647  ok

[C] getCount / getCounts are documented inverses

  getCount(999,999,4294) = 32703  (true index 4294999999)    WRONG
  getCounts(32703) = [0,7,2638]   (asked for [999,999,4294]) ROUND-TRIP BROKEN

[D] the iterator's bound is the same wrapped total
iterated 32704 of 4295000000 cells (0.00076%) and terminated normally
Block [A] is the point: 46341x46341 and 2x2147483647 overflow to a negative value and are correctly rejected, while 65537x65536, 1000x1000x4295, 641x6700417 and 3x1431655766 overflow to a positive value and are silently accepted. Whether a caller gets an exception or a wrong answer is determined by where the product happens to land, not by any documented boundary.

Block [B] is the control: sizes that fit in an int are exact, including 46340x46340 right below the threshold. So this is not "the class does not support large spaces" — it is that some spaces it cannot represent are accepted anyway.

Why these inputs are in contract, and the magnitudes ordinary

Every size above is strictly positive, which is the constructor's only documented precondition.

MultidimensionalCounter allocates nothing proportional to the total — it is a pure index mapper holding an int[dimension] and a few fields — so constructing one over a multi-billion-cell space is cheap and a reasonable thing for a caller to do (out-of-core grids, tiled images, parameter sweeps). A 64k x 64k grid is enough to trigger it.

Why this is a defect rather than an int-domain limitation

• getSize() is documented as the number of slots; it returns an unrelated number.
• getCount and getCounts are documented as inverses; the round trip returns [0, 7, 2638] for [999, 999, 4294].
• The iterator visits 32,704 of 4,295,000,000 cells — 0.0008% — and then terminates normally, so a loop driven by it silently processes a fraction of the data and reports success.

The existing tS <= 0 guard shows the intent was to reject unrepresentable sizes. It just only catches the half of them that wrap negative.

Suggested fix

Accumulate in long and range-check once:

long tS = size[last];
for (int i = 0; i < last; i++) {
    long count = 1;
    for (int j = i + 1; j < dimension; j++) {
        count *= size[j];
    }
    uniCounterOffset[i] = Math.toIntExact(count);
    tS *= size[I];
}
if (tS <= 0 || tS > Integer.MAX_VALUE) {
    throw new MathIllegalArgumentException(...);
}
totalSize = (int) tS;

and likewise accumulate getCount in long before narrowing. uniCounterOffset[i] is itself an unchecked product and needs the same treatment.

Note

The same code is present in the retired commons-math3 3.6.1 (org.apache.commons.math3.util.MultidimensionalCounter). Reporting it here since Hipparchus is the maintained successor.

The replication test

import org.hipparchus.util.MultidimensionalCounter;
import java.math.BigInteger;

/**
 * Every size below is strictly positive, which is the constructor's only
 * documented precondition, so all of these calls are inside the contract.
 */
public class Repro {

    static void size(int... dims) {
        BigInteger truth = BigInteger.ONE;
        StringBuilder d = new StringBuilder();
        for (int i = 0; i < dims.length; i++) {
            truth = truth.multiply(BigInteger.valueOf(dims[i]));
            d.append(i == 0 ? "" : "x").append(dims[i]);
        }
        boolean representable = truth.compareTo(BigInteger.valueOf(Integer.MAX_VALUE)) <= 0;
        try {
            MultidimensionalCounter c = new MultidimensionalCounter(dims);
            int got = c.getSize();
            String verdict = representable
                ? (BigInteger.valueOf(got).equals(truth) ? "ok" : "WRONG")
                : "ACCEPTED, getSize() unrelated to the true size " + truth;
            System.out.printf("  %-18s getSize()=%-11d %s%n", d, got, verdict);
        } catch (RuntimeException e) {
            System.out.printf("  %-18s rejected -> %s%n", d, e.getClass().getSimpleName());
        }
    }

    public static void main(String[] args) {
        System.out.println("[A] true product exceeds Integer.MAX_VALUE -- accepted or rejected?");
        size(65537, 65536);
        size(46341, 46341);
        size(1000, 1000, 4295);
        size(641, 6700417);
        size(2, 2147483647);
        size(3, 1431655766);

        System.out.println("\n[B] control: sizes that DO fit are exact, so the class is not broken generally");
        size(3, 4, 5);
        size(46340, 46340);
        size(2147483647);

        System.out.println("\n[C] getCount / getCounts are documented inverses");
        MultidimensionalCounter c = new MultidimensionalCounter(1000, 1000, 4295);
        int idx = c.getCount(999, 999, 4294);
        long expect = 999L * 1000L * 4295L + 999L * 4295L + 4294L;
        int[] back = c.getCounts(idx);
        System.out.printf("  getCount(999,999,4294) = %d   (true index %d)   %s%n",
            idx, expect, idx == expect ? "ok" : "WRONG");
        System.out.printf("  getCounts(%d) = [%d,%d,%d]   (asked for [999,999,4294])   %s%n",
            idx, back[0], back[1], back[2],
            (back[0] == 999 && back[1] == 999 && back[2] == 4294) ? "ok" : "ROUND-TRIP BROKEN");

        System.out.println("\n[D] the iterator's bound is the same wrapped total");
        long steps = 0;
        var it = c.iterator();
        while (it.hasNext()) { it.next(); steps++; }
        long real = 1000L * 1000L * 4295L;
        System.out.printf("  iterated %d of %d cells (%.5f%%) and terminated normally%n",
            steps, real, 100.0 * steps / real);
    }
}