This is an automated email from the ASF dual-hosted git repository.
garydgregory pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-compress.git
The following commit(s) were added to refs/heads/master by this push:
new 12ba75437 Verify Kraft's inequality is not violated (#804)
12ba75437 is described below
commit 12ba75437f4d935cc54806bd27e92314270d5c84
Author: Fredrik Kjellberg <[email protected]>
AuthorDate: Sat Aug 22 21:20:48 2026 +0200
Verify Kraft's inequality is not violated (#804)
Generated-by: Claude Opus 5 <[email protected]>
---
.../commons/compress/huffman/HuffmanDecoder.java | 39 +++++++++++----
.../bzip2/BZip2CompressorInputStreamTest.java | 24 ++++++---
.../Deflate64CompressorInputStreamTest.java | 6 ++-
.../compress/huffman/HuffmanDecoderTest.java | 58 ++++++++++++++++++++--
4 files changed, 105 insertions(+), 22 deletions(-)
diff --git
a/src/main/java/org/apache/commons/compress/huffman/HuffmanDecoder.java
b/src/main/java/org/apache/commons/compress/huffman/HuffmanDecoder.java
index ffd022c2a..3f444e88e 100644
--- a/src/main/java/org/apache/commons/compress/huffman/HuffmanDecoder.java
+++ b/src/main/java/org/apache/commons/compress/huffman/HuffmanDecoder.java
@@ -30,17 +30,20 @@
/**
* Canonical Huffman decoder.
* <p>
- * This class builds decoding tables from an array of code lengths (one entry
per symbol) and then decodes symbols from a {@link BitInputStream}. The code set
- * is expected to be a <em>complete prefix code</em>; i.e., the code lengths
must satisfy Kraft's equality.
+ * This class builds decoding tables from an array of code lengths (one entry
per symbol) and then decodes symbols from a {@link BitInputStream}.
+ * </p>
+ * <p>
+ * The constructors verify that the code lengths satisfy <em>Kraft's
inequality</em>, i.e. that no code length has more leaf nodes assigned to it
than a binary
+ * tree of that depth can hold, and reject over-subscribed code sets with a
{@link CompressorException}. Code sets that leave leaf nodes unused, i.e.
incomplete
+ * codes, are accepted, as several formats produce them. Decoding a code word
that no symbol claims fails at {@link #decodeSymbol(BitInputStream)} time.
* </p>
*
* <h2>Usage</h2>
*
* <pre>{@code
* int[] codeLengths = ...; // length per symbol (0 => unused)
- * int symbolCount = codeLengths.length;
* int maxLen = 15; // maximum non-zero code length in codeLengths
- * HuffmanDecoder dec = new HuffmanDecoder(codeLengths, symbolCount, maxLen);
+ * HuffmanDecoder dec = new HuffmanDecoder(codeLengths, 0, maxLen);
* int sym = dec.decodeSymbol(bitIn);
* }</pre>
*
@@ -57,9 +60,11 @@ public final class HuffmanDecoder {
/**
* Builds canonical decode tables.
+ *
+ * @throws CompressorException if the code lengths violate Kraft's
inequality.
*/
private static void fillCodeTable(final int[] codeLengths, final int
minLen, final int maxLen, final int[] bias,
- final int[] limit, final int[] sorted) {
+ final int[] limit, final int[] sorted) throws CompressorException {
// 1) Histogram of code lengths
final int[] count = new int[maxLen + 1];
for (int symbol = 0; symbol < codeLengths.length; symbol++) {
@@ -69,14 +74,24 @@ private static void fillCodeTable(final int[] codeLengths,
final int minLen, fin
}
count[codeLengths[symbol]]++;
}
- // 2) Generate starting offsets into sorted symbol table
+ // 2) Verify Kraft's inequality is not violated, i.e. the tree has no
more leaf nodes at any depth than fit in a binary tree of that depth.
+ int availableNodes = 1;
+ for (int len = 1; len <= maxLen; len++) {
+ availableNodes <<= 1;
+ if (count[len] > availableNodes) {
+ throw new CompressorException("Tree contains too many leaf
nodes for code length %d: %d leaf nodes, but only %d nodes available", len,
+ count[len], availableNodes);
+ }
+ availableNodes -= count[len];
+ }
+ // 3) Generate starting offsets into sorted symbol table
// The offsets are biased by -1 to simplify code in the next step
final int[] offset = new int[maxLen + 1];
offset[0] = -1;
for (int len = 1; len <= maxLen; len++) {
offset[len] = offset[len - 1] + count[len - 1];
}
- // 3) Build table of symbols sorted by length, then by symbol
+ // 4) Build table of symbols sorted by length, then by symbol
// Adjust offsets to point to the last element of each length
for (int symbol = 0; symbol < codeLengths.length; symbol++) {
final int len = codeLengths[symbol];
@@ -85,14 +100,14 @@ private static void fillCodeTable(final int[] codeLengths,
final int minLen, fin
}
sorted[++offset[len]] = symbol;
}
- // 4) Compute the largest left-justified code for each length
+ // 5) Compute the largest left-justified code for each length
int firstCode = 0;
for (int len = minLen; len <= maxLen; len++) {
firstCode += count[len];
limit[len] = firstCode - 1;
firstCode <<= 1; // prepare for next length
}
- // 5) Compute the bias for each length
+ // 6) Compute the bias for each length
for (int len = minLen; len <= maxLen; len++) {
bias[len] = limit[len] - offset[len];
}
@@ -145,7 +160,8 @@ private static int readBitsFully(final BitInputStream in,
final int numBits) thr
*
* @param codeLengths code length per symbol; {@code 0} means the symbol
is not used; not {@code null}.
* @throws NullPointerException if {@code codeLengths} is {@code null}.
- * @throws CompressorException if {@code codeLengths} size is out of
range or if any code length is out of range
+ * @throws CompressorException if {@code codeLengths} size is out of
range or if any code length is out of range or if the code lengths violate
+ * Kraft's inequality.
*/
public HuffmanDecoder(final int[] codeLengths) throws CompressorException {
this(codeLengths, 0, MAX_SUPPORTED_CODE_LENGTH);
@@ -164,7 +180,8 @@ public HuffmanDecoder(final int[] codeLengths) throws
CompressorException {
* @throws NullPointerException if {@code codeLengths} is {@code null}.
* @throws IllegalArgumentException if {@code maxCodeLength} exceeds the
implementation limit (30) or if {@code minCodeLength}
* is not in the range 0-{@code
maxCodeLength}].
- * @throws CompressorException if {@code codeLengths} size is out of
range or if any code length is out of range
+ * @throws CompressorException if {@code codeLengths} size is out of
range or if any code length is out of range or if the code lengths violate
+ * Kraft's inequality.
*/
public HuffmanDecoder(final int[] codeLengths, final int minCodeLength,
final int maxCodeLength) throws CompressorException {
Objects.requireNonNull(codeLengths, "codeLengths");
diff --git
a/src/test/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStreamTest.java
b/src/test/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStreamTest.java
index 1c1607fe3..5fb25169d 100644
---
a/src/test/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStreamTest.java
+++
b/src/test/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStreamTest.java
@@ -65,10 +65,14 @@ private void fuzzingTest(final int[] bytes) throws
IOException, ArchiveException
* <li>Number of groups: 2 (minimum).</li>
* <li>Number of selectors: 3.</li>
* <li>Selectors: all three encode j=1 (unary "10").</li>
- * <li>Huffman code lengths for 2 groups over alphabet size 3 (RUNA,
RUNB, EOB) are all equal to {@code codeLength}.</li>
+ * <li>Huffman code lengths for 2 groups over alphabet size 3 (RUNA,
RUNB, EOB): {@code codeLength} is used for every
+ * symbol, except when it equals {@link #MIN_CODE_LEN}, in which case
lengths {@code {1, 2, 2}} are used instead
+ * because three symbols sharing length 1 would violate Kraft's
inequality; the minimum length is still
+ * {@code codeLength} in that case.</li>
* </ul>
* <p>
- * <strong>Note:</strong> The values are chosen to keep everything
byte-aligned.
+ * Each Huffman group is encoded as a 5-bit start length followed, for
each symbol, by a delta encoding: pairs of a
+ * '1' bit and a direction bit ('0' increments the current length, '1'
decrements it), terminated by a '0' bit.
* </p>
* @param codeLength The code length to use for each symbol in each group;
must be in [0, 31]
*/
@@ -91,10 +95,18 @@ private BitInputStream prepareDecodingTables(final int
codeLength) {
stream.write(0b00000000); // middle 8 bits of nSelectors
stream.write(0b11_10_10_10); // low 2 bits of nSelectors + selectors
(3 x 2 bits)
- // Huffman tables: two groups, three symbols each
- // startLen (5 bits) followed by 3x '0' (done) => one byte: codeLength
<< 3
- stream.write(codeLength << 3);
- stream.write(codeLength << 3);
+ // Huffman tables: two groups, three symbols each.
+ if (codeLength == MIN_CODE_LEN) {
+ // Lengths {1, 2, 2}, encoded per group as: 00001 (startLen 1) 0
(keep) 10 0 (increment, then keep) 0 (keep).
+ // Two groups of those 10 bits are "0000101000 0000101000", which
re-split into bytes and zero-padded gives:
+ stream.write(0b0000_1010);
+ stream.write(0b0000_0010);
+ stream.write(0b1000_0000);
+ } else {
+ // All three symbols share codeLength: 5-bit startLen followed by
three '0' bits, exactly one byte per group.
+ stream.write(codeLength << 3);
+ stream.write(codeLength << 3);
+ }
return new BitInputStream(new
ByteArrayInputStream(stream.toByteArray()), ByteOrder.BIG_ENDIAN);
}
diff --git
a/src/test/java/org/apache/commons/compress/compressors/deflate64/Deflate64CompressorInputStreamTest.java
b/src/test/java/org/apache/commons/compress/compressors/deflate64/Deflate64CompressorInputStreamTest.java
index dfc0f87ef..d9013d9a6 100644
---
a/src/test/java/org/apache/commons/compress/compressors/deflate64/Deflate64CompressorInputStreamTest.java
+++
b/src/test/java/org/apache/commons/compress/compressors/deflate64/Deflate64CompressorInputStreamTest.java
@@ -183,11 +183,15 @@ void
testShouldThrowIOExceptionInsteadOfRuntimeExceptionCOMPRESS526() {
}
/**
+ * The fuzzed data below encodes a Huffman table that violates Kraft's
inequality (too many leaf nodes for its
+ * depth), which {@link
org.apache.commons.compress.huffman.HuffmanDecoder} rejects with a
+ * {@link CompressorException} before the stream would otherwise run out
of data.
+ *
* @see <a
href="https://issues.apache.org/jira/browse/COMPRESS-527";>COMPRESS-527</a>
*/
@Test
void testShouldThrowIOExceptionInsteadOfRuntimeExceptionCOMPRESS527() {
- assertThrows(EOFException.class,
+ assertThrows(CompressorException.class,
() -> fuzzingTest(new int[] { 0x50, 0x4b, 0x03, 0x04, 0x14,
0x00, 0x00, 0x00, 0x09, 0x00, 0x84, 0xb6, 0xba, 0x46, 0x72, 0xb6, 0xfe, 0x77,
0x4a,
0x00, 0x00, 0x00, 0x6b, 0x00, 0x00, 0x00, 0x03, 0x00,
0x1c, 0x00, 0x62, 0x62, 0x62, 0x55, 0x54, 0x09, 0x00, 0x03, 0xe7, 0xce, 0x64,
0x55, 0xf3, 0xce, 0x64, 0x55, 0x75, 0x78, 0x0b, 0x00,
0x01, 0x04, 0x5c, 0xf9, 0x01, 0x00, 0x04, 0x88, 0x13, 0x00, 0x00, 0x1d, 0x8b,
diff --git
a/src/test/java/org/apache/commons/compress/huffman/HuffmanDecoderTest.java
b/src/test/java/org/apache/commons/compress/huffman/HuffmanDecoderTest.java
index f44215e58..1a20c8cd0 100644
--- a/src/test/java/org/apache/commons/compress/huffman/HuffmanDecoderTest.java
+++ b/src/test/java/org/apache/commons/compress/huffman/HuffmanDecoderTest.java
@@ -36,6 +36,7 @@
import org.apache.commons.compress.AbstractTest;
import org.apache.commons.compress.compressors.CompressorException;
import org.apache.commons.compress.utils.BitInputStream;
+import org.apache.commons.lang3.ArrayUtils;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
@@ -107,6 +108,42 @@ static Stream<Arguments> testDecodeSymbols() {
// @formatter:on
}
+ static Stream<Arguments> testKraftsInequality() {
+ // Each case provides code lengths that satisfy Kraft's inequality,
one extra code length that overflows the tree, the code length at which the
+ // violation surfaces, and the leaf node and available node counts at
that code length. The extra code length and the code length at which the
+ // violation surfaces differ when the extra code still fits at its own
depth but takes a node the longer codes need.
+ // @formatter:off
+ return Stream.of(
+ // Symbol 2: 0, symbols 1 and 3: 10 and 11
+ Arguments.of(new int[] {0, 2, 1, 2}, 2, 2, 3, 2),
+ // Symbols 0 and 1: 0 and 1
+ Arguments.of(new int[] {1, 1}, 1, 1, 3, 2),
+ // Symbols 0-2: 00, 01 and 10, symbols 3 and 4: 110 and 111
+ Arguments.of(new int[] {2, 2, 2, 3, 3}, 3, 3, 3, 2),
+ // Symbols 0-2: 00, 01 and 10, symbols 3-6: 1100, 1101, 1110
and 1111
+ Arguments.of(new int[] {2, 2, 2, 4, 4, 4, 4}, 4, 4, 5, 4),
+ // All 16 codes of length 4 are taken
+ Arguments.of(new int[] {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4}, 4, 4, 17, 16),
+ // All 16 codes of length 4 are taken, so no node is left to
extend to length 5
+ Arguments.of(new int[] {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 4}, 5, 5, 1, 0),
+ // 15 codes of length 4 leave a single free node, split into
the two codes of length 5
+ Arguments.of(new int[] {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 5, 5}, 5, 5, 3, 2),
+ // Same tree, now full at length 5, so no node is left to
extend to length 6
+ Arguments.of(new int[] {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
4, 4, 5, 5}, 6, 6, 1, 0),
+ // Symbol 0: 0 takes half the tree, the other half holds 7
codes of length 4 plus the two codes of length 5
+ Arguments.of(new int[] {1, 4, 4, 4, 4, 4, 4, 4, 5, 5}, 5, 5,
3, 2),
+ // Leaf nodes at four different depths: 0, 10, then 3 codes of
length 4 and the two codes of length 5
+ Arguments.of(new int[] {1, 2, 4, 4, 4, 5, 5}, 5, 5, 3, 2),
+ // Symbol 0: 0, symbols 1-4: 100, 101, 110 and 111; the added
leaf node at length 2 used to be the parent of two of the codes of length 3
+ Arguments.of(new int[] {1, 3, 3, 3, 3}, 2, 3, 4, 2),
+ // Symbol 0: 0, symbols 1-8: 1000-1111; the added leaf node at
length 2 used to be the ancestor of four of the codes of length 4
+ Arguments.of(new int[] {1, 4, 4, 4, 4, 4, 4, 4, 4}, 2, 4, 8,
4),
+ // Same tree, where the added leaf node at length 3 used to be
the parent of two of the codes of length 4
+ Arguments.of(new int[] {1, 4, 4, 4, 4, 4, 4, 4, 4}, 3, 4, 8, 6)
+ );
+ // @formatter:on
+ }
+
private int decodeSymbol(final HuffmanDecoder decoder, final int... data)
throws IOException {
try (BitInputStream in = new BitInputStream(new
ByteArrayInputStream(AbstractTest.toByteArray(data)), ByteOrder.BIG_ENDIAN)) {
return decoder.decodeSymbol(in);
@@ -133,9 +170,10 @@ void testCodeLengthExceedingMaxCodeLength() throws
Exception {
void testCreateHuffmanDecodingTablesWithLargeAlphaSize() {
// Use a codeLengths array with length equal to MAX_ALPHA_SIZE (258)
to test array bounds.
final int[] codeLengths = new int[258];
- for (int i = 0; i < codeLengths.length; i++) {
- // Use all code lengths within valid range [1, 20]
- codeLengths[i] = (char) (i % 20 + 1);
+ // One symbol at the minimum length and the rest at the maximum length
so Kraft's inequality holds.
+ codeLengths[0] = 1;
+ for (int i = 1; i < codeLengths.length; i++) {
+ codeLengths[i] = 20;
}
final HuffmanDecoder decoder = assertDoesNotThrow(() -> new
HuffmanDecoder(codeLengths, 1, 20),
"HuffmanDecoder constructor should not throw for valid
codeLengths array of MAX_ALPHA_SIZE");
@@ -196,7 +234,7 @@ void testMinCodeLengthExceedingMaxCodeLength() {
}
@Test
- void testNoCodeLengths() throws Exception {
+ void testNoCodeLengths() {
final CompressorException e = assertThrows(CompressorException.class,
() -> new HuffmanDecoder(new int[0]),
"Expected CompressorException for empty code length list");
assertEquals("Empty code length list", e.getMessage());
@@ -234,4 +272,16 @@ void testSingleCodeLength() throws Exception {
"Expected CompressorException for invalid bitstream");
assertEquals("Invalid Huffman code: 2", e.getMessage());
}
+
+ @ParameterizedTest(name = "appending code length {1} to {0} overflows at
code length {2}")
+ @MethodSource
+ void testKraftsInequality(final int[] codeLengths, final int
extraCodeLength, final int expectedCodeLength, final int expectedLeafNodes,
+ final int expectedAvailableNodes) {
+ assertDoesNotThrow(() -> new HuffmanDecoder(codeLengths), "Code
lengths are expected to satisfy Kraft's inequality");
+ final int[] tooManyCodeLengths = ArrayUtils.add(codeLengths,
extraCodeLength);
+ final CompressorException e = assertThrows(CompressorException.class,
() -> new HuffmanDecoder(tooManyCodeLengths),
+ "Expected CompressorException for too many leaf nodes");
+ assertEquals(String.format("Tree contains too many leaf nodes for code
length %d: %d leaf nodes, but only %d nodes available", expectedCodeLength,
+ expectedLeafNodes, expectedAvailableNodes), e.getMessage());
+ }
}
