MonotonicBlockPackedWriter mis-encodes a block that ends near Long.MAX_VALUE: {1, Long.MAX_VALUE} reads back as {1, Long.MIN_VALUE}

MonotonicBlockPackedWriter (lucene/core util.packed, public, @lucene.internal) encodes blocks of non-decreasing, non-negative longs as a line min + avg * i plus a non-negative correction per value, packed with just enough bits for the largest correction. To keep every correction non-negative, flush() lowers min wherever min + (long) (avg * i) > values[i]. When a block ends close to Long.MAX_VALUE, that sum wraps to a negative number, the signed test is false, min is not lowered, the negative correction is ignored by Math.max, and the block gets too few bits. The reader decodes the stream faithfully, so get(i) is wrong with no error: {1, Long.MAX_VALUE} (block size 64) reads back as {1, Long.MIN_VALUE} with assertions on and off.

It is a regression from LUCENE-5721 (4.9.0), which replaced wrap-consistent zig-zag deltas with this loop; 4.2.0 and 4.8.1 round-trip the same inputs. It is latent: the only in-tree caller, the non-default blockterms terms index, stores file-pointer deltas and term-byte offsets far below the trigger, so only code that calls the internal writer directly with such values is hit. Comparing values[i] - (long) (avg * i) < min instead cannot overflow for increasing blocks; this sign-aware fix keeps the format and passes the repro, TestPackedInts and the codecs tests.

// MonotonicBlockPackedWriter.flush()
final float avg = off == 1 ? 0f : (float) (values[off - 1] - values[0]) / (off - 1);  // :74
long min = values[0];                                                                  // :75
// adjust min so that all deltas will be positive                                     // :76
for (int i = 1; i < off; ++i) {
  final long actual = values[i];
  final long expected = expected(min, avg, i);   // min + (long) (avg * (long) i)      // :79
  if (expected > actual) {                       // signed compare                     // :80
    min -= (expected - actual);
  }
}
long maxDelta = 0;
for (int i = 0; i < off; ++i) {
  values[i] = values[i] - expected(min, avg, i);                                       // :87
  maxDelta = Math.max(maxDelta, values[i]);      // a negative delta is ignored        // :88
}
// :91-98: writeZLong(min), the float bits of avg, then 0 bits if maxDelta == 0, else bitsRequired(maxDelta)

// MonotonicBlockPackedReader
static long expected(long origin, float average, int index) {                         // :37
  return origin + (long) (average * (long) index);
}
// get(index) = expected(minValues[block], averages[block], idx) + subReaders[block].get(idx)   // :123

1. avg = (float) (Long.MAX_VALUE - 1) / 1 = 9.223372E18, exactly 2^63 as a float; min = 1.
2. (long) (avg * 1) saturates to Long.MAX_VALUE, so expected = 1 + Long.MAX_VALUE wraps to -9223372036854775808.
3. -9223372036854775808 > 9223372036854775807 is false: min stays 1.
4. Deltas {0, Long.MAX_VALUE - Long.MIN_VALUE} = {0, -1} after the wrap; Math.max keeps 0, so the block is written with 0 bits (no packed values, so no assertion can fire).
5. The reader returns expected(1, avg, 1) + 0 = -9223372036854775808.

With the sign-aware fix the same block gets min = 0, deltas {1, 0}, 1 bit per value, and get(1) = Long.MAX_VALUE.

• Every observed failure coincides with the overflow. In a grid of 19,200 strictly increasing 64-value blocks (three grids of 6,400), the failing blocks are exactly those where min + (long) (avg * i) overflows (0 failures without overflow, 0 overflows without failure); a Z3 model of flush() finds no failure without the overflow for 2- and 3-value blocks. Neither covers every block size.
• How close to Long.MAX_VALUE. min starts at the first value and only goes down, so the sum overflows only through the float rounding of the slope, which scales with the block's span S. No failure with S <= 2^20; at S = 2^40 failures up to a headroom of 2^12; at S near 2^62 up to 2^36. The largest failing headroom seen was 2^39.4. A Z3 model that replaces Java's exact float arithmetic by a derived bound on the rounding error finds no failing 2- or 3-value block with a headroom of 2^41 or more.
• Assertions. What decides is the bit width the stock writer picks from the largest non-negative delta (:88, :93-98). A mis-encoded block that still has a non-negative delta above 0 is packed with 1 to 63 bits, and with -ea its negative delta trips assert unsignedBitsRequired(v) <= bitsPerValue (BulkOperationPacked.java:222) while writing. The repro's block has only the deltas 0 and -1, so it is written with 0 bits and no assertion runs (its correct encoding would need 1 bit).
• Siblings are fine. PackedLongValues.monotonicBuilder() subtracts expected(0, average, i) first (MonotonicLongValues.java:94-103), and DirectMonotonicWriter, which the default codec uses, sizes bits with |, which "has the benefit of working fine with negative values too (in case of overflow)" (DirectMonotonicWriter.java:93-96). Both round-trip the same inputs.

• Direct callers of the public, @lucene.internal MonotonicBlockPackedWriter (:51) whose block ends close to Long.MAX_VALUE: executed, wrong values with assertions on and off.
• Lucene itself: nobody known. The only production caller is FixedGapTermsIndexWriter (lucene/codecs blockterms, @lucene.experimental, not in the default codec). It stores termsFilePointer - termsStart (:169), which would need a terms file of about 8 EiB, and a running sum of indexed-term prefix lengths (:172-174), which stays below 2^46. In this tree only the test-framework formats LuceneFixedGap and MockRandomPostingsFormat create it.
• Downstream (read-only code search, not executed): the one use found, a port of the Lucene 5.4 doc-values writer in Elasticsearch's old-lucene-versions plugin, stores bounded file and buffer offsets.
• Scale. The trigger needs values within about 10^12 of 9.2 x 10^18. Offsets, ordinals and counts are many orders of magnitude smaller; a probe found 0 failures in 8,064 blocks ending at or below 2^62.
• Effect. Silent wrong numbers for that block (other blocks decode correctly), or an AssertionError while writing under -ea. No hang, no extra memory.
• Likelihood: contrived. Priority low.

• Package. The test sits in org.apache.lucene.util.packed, next to TestPackedInts, but uses only public members of the two public classes.
• Smallest input. Two values; the 0-bit block makes -ea and -da identical (no assertion is involved). The seed does not matter: the input is fixed, and a second seed fails the same way.
• Bigger blocks (the finder's second test, not needed for the repro): 64 strictly increasing values from 2^62 to Long.MAX_VALUE trip AssertionError at BulkOperationPacked.encode(BulkOperationPacked.java:222) under -ea, and read back element [62] as Long.MAX_VALUE instead of Long.MAX_VALUE - 1 under -da.
• As the regression test: this same method, for example added to TestPackedInts. It passes with the fix.

cp $REPRO/TestMonotonicBlockPackedNearMaxValue.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/packed/
cd $LUCENE
./gradlew :lucene:core:test --tests org.apache.lucene.util.packed.TestMonotonicBlockPackedNearMaxValue -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same result)

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on (the same with -Ptests.asserts=false)
TestMonotonicBlockPackedNearMaxValue > testTwoValuesEndingAtLongMaxValue FAILED
    java.lang.AssertionError: expected:<9223372036854775807> but was:<-9223372036854775808>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:D9DE765148A8604]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.junit.Assert.assertEquals(Assert.java:633)
        at org.apache.lucene.util.packed.TestMonotonicBlockPackedNearMaxValue.testTwoValuesEndingAtLongMaxValue(TestMonotonicBlockPackedNearMaxValue.java:40)
1 test completed, 1 failed

# with the sign-aware fix, assertions on and off
:lucene:core:test (SUCCESS): 1 test

• No upper bound is documented. "A writer for large monotonically increasing sequences of positive longs" (MonotonicBlockPackedWriter.java:26); add() asserts only l >= 0 (:66). The reader "Provides random access to a stream written with MonotonicBlockPackedWriter" (MonotonicBlockPackedReader.java:31).
• The broken invariant is written in the code: "adjust min so that all deltas will be positive" (:76), and BulkOperationPacked.encode asserts it (:222).
• Regression from an optimization. Before LUCENE-5721 the deltas were zigZagEncode(values[i] - min - (long) (avg * i)) and the reader did the same two's-complement arithmetic, so a wrap cancelled out; 4.2.0 and 4.8.1 round-trip both inputs. LUCENE-5721 is listed under 4.9.0 "Optimizations" (lucene/CHANGES.txt:12247-12248); its discussion (#6783) is about speed and bits per value, never a value bound.
• The siblings handle overflow on purpose. PackedLongValues.monotonicBuilder() subtracts the line before packing (MonotonicLongValues.java:94-103), and DirectMonotonicWriter's bit sizing is commented as "working fine with negative values too (in case of overflow)" (DirectMonotonicWriter.java:93-96).
• No test sets a limit. TestPackedInts#testMonotonicBlockPackedReaderWriter (TestPackedInts.java:1288-1330) asserts an exact round trip but uses values below about 2^31 + 2^24.

Strongest case for "not a bug" (the cross-model reviews, OpenAI GPT-5.6, refute and intended lenses, not real with high confidence, rating this scope argument "strong"): both classes are @lucene.internal, so the contract is what in-tree callers need, and the only caller cannot produce such values. An independent verifier adds that the classes were added for "monotonically increasing positive values (e.g. file offsets)" (LUCENE-4547, lucene/CHANGES.txt:14383-14387), and the LUCENE-5721 issue itself opens with "This compression is used in lucene for monotonically increasing offsets, e.g. stored fields index, dv BINARY/SORTED_SET offsets, OrdinalMap ..." (#6783).

Why it fails: @lucene.internal renders as "This API is for internal purposes only and might change in incompatible ways in the next release", a stability caveat, not permission to return wrong values for inputs the javadoc accepts; "e.g. file offsets" and the LUCENE-5721 list are examples of use, not a bound. The reviewers themselves reproduced the bug with their own tests, agreed on the root cause and the fix, found nothing that documents a reduced numeric domain, and said maintainers may reasonably accept the fix as an internal correctness improvement.

What it does establish: no Lucene user is known to be affected, and a maintainer could reasonably close it as out of scope for an internal API rather than take the fix. It is an argument about scope, not that the wrong values are intended.

Four options; option A was applied in a scratch worktree of main 645d4fe14a20 and run against the minimal test, the packed-ints suites, the codecs module's tests and core's static checks.

In flush() only (+12/-3). When the slope is non-negative, test values[i] - offset < min; otherwise keep the original comparison. This is the variant an independent verifier wrote after finding that the unconditional form (B) breaks a decreasing block; here the temporary is named offset and commented.

for (int i = 1; i < off; ++i) {
  final long actual = values[i];
  if (avg >= 0) {
    // actual and offset are both in [0, Long.MAX_VALUE], so actual - offset cannot overflow,
    // while min + offset can when the block ends close to Long.MAX_VALUE
    final long offset = (long) (avg * (long) i);
    if (actual - offset < min) {
      min = actual - offset;
    }
  } else {
    final long expected = expected(min, avg, i);
    if (expected > actual) {
      min -= (expected - actual);
    }
  }
}

Trade-offs

• Format unchanged, reader untouched. By reading: when the old sum does not wrap, the new test makes the same decision and computes the same min, so those blocks are written byte for byte as before. Only the mis-encoded blocks change: they get new, correct bytes in the same layout, which the unchanged reader decodes. So the format is the same, with corrected bytes for previously mis-encoded blocks; the output is not byte-for-byte identical.
• Z3 proves the subtraction form gives deltas in [0, 2^63) for non-decreasing non-negative blocks of 2-4 values.
• The code comment's "both in [0, Long.MAX_VALUE]" holds for the documented non-negative input: offset is in that range for avg >= 0 (the cast saturates), and actual is when the caller keeps to the javadoc. add() only asserts l >= 0, so with -da negative values are outside the guarantee, as they are outside the javadoc today.
• Decreasing blocks are outside the javadoc, and the writer does not reject them (add() asserts only l >= 0); the upstream test feeds local decreases of up to 16. So the avg < 0 branch is compatibility handling for input outside the documented domain, the conservative choice.
• Cost: one loop-invariant branch in a write-side loop, not on any read path. Not benchmarked.

What the checks validated

• Scratch worktree of main 645d4fe14a20, gradle, JDK 25.0.3 (2026-11-01). Stock: the minimal test fails with assertions on and off. With the fix: it passes with assertions on and off.
• org.apache.lucene.util.packed.* (seed DEADBEEF): 44 tests, 3 skipped, 0 failures (TestPackedInts, TestDirectMonotonic, TestDirectPacked, the minimal test).
• TestPackedInts#testMonotonicBlockPackedReaderWriter with -Ptests.iters=20: 20 of 20 pass.
• All of :lucene:codecs:test (random seed): 693 tests, 78 skipped, 0 failures, including TestFixedGapPostingsFormat, the format of the only in-tree caller.
• :lucene:core:check -x test: google-java-format, license checks, ecj lint and forbidden APIs pass (the minimal test included).
• Earlier, the verifier's version of the same change passed its own test, the finder's two tests, three 6,400-block grids, the decreasing block and testMonotonicBlockPackedReaderWriter x5.

min = Math.min(min, values[i] - expected(0, avg, i));, the form MonotonicLongValues uses.

Trade-offs

Smallest diff, but it assumes avg >= 0: on a block of 63 x Long.MAX_VALUE followed by Long.MAX_VALUE - 2^40, which stock main round-trips, it trips the packing assertion (-ea) or reads back -9223370937343148033 (-da). Acceptable only with a documented and asserted non-decreasing input.

A negative delta then forces 64 bits per value.

Trade-offs

Not recommended: it wastes 64 bits per value on exactly these blocks, and at 64 bits per value this reader drops the top byte (maskRight = (1L << 64) - 1 is 0 in Java, MonotonicBlockPackedReader.java:87; a probe reads 64 of 64 values wrong). The writer never emits 64 bits today, so that separate reader quirk is unreachable; it is not part of this bug. Not validated.

State that values must stay below some bound.

Trade-offs

The safe headroom depends on the block span, so there is no simple bound, and it would narrow the domain the javadoc states ("positive longs", with no upper bound). Not recommended.

• The hunt unit covered util.packed's monotonic and direct encoders. The finder modelled MonotonicBlockPackedWriter.flush() in Z3 over 64-bit vectors (domain 0 <= v_0 <= ... <= Long.MAX_VALUE) with a model-to-Java line map.
• One query found a counterexample; another showed that every failure in the model needs the int64 overflow of min + (long) (avg * i) (2- and 3-value blocks); a third bounded the reach for 2- and 3-value blocks (no failure with the last value at or below Long.MAX_VALUE - 2^41, with the float rounding replaced by a derived error bound); a fourth proved the subtraction-form fix for 2-4 values.
• A differential harness compared encode/decode on the stock jar: it found 534-589 wrong blocks of 11,760 per run (-ea and -da), for example a 1,023-value block (block size 1,024) from 1 to Long.MAX_VALUE that read back -9223372036854775808 at index 1,021 instead of 9223372036854775807.
• Independent verifiers reproduced it with their own tests, mapped the reach, found the decreasing-block flaw in the first fix, and showed the 4.8.1 to 4.9.0 regression on release jars.