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 778fc583a Add reusable Huffman decoder. (#792)
778fc583a is described below
commit 778fc583a2bd14d82be1bd619c9319070e4bd997
Author: Gary Gregory <[email protected]>
AuthorDate: Tue Aug 4 08:21:13 2026 -0400
Add reusable Huffman decoder. (#792)
Rework of stale PR #720.
---
.../bzip2/BZip2CompressorInputStream.java | 192 +++-------------
.../compressors/deflate64/Deflate64Decoder.java | 114 ++--------
.../commons/compress/huffman/HuffmanDecoder.java | 248 +++++++++++++++++++++
.../commons/compress/huffman/package-info.java | 25 +++
.../bzip2/BZip2CompressorInputStreamTest.java | 26 +--
.../Deflate64CompressorInputStreamTest.java | 2 +-
.../deflate64/Deflate64DecoderTest.java | 4 +-
.../compress/huffman/HuffmanDecoderTest.java | 102 +++++++++
8 files changed, 428 insertions(+), 285 deletions(-)
diff --git
a/src/main/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStream.java
b/src/main/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStream.java
index 36b37e6c1..6e8eee45e 100644
---
a/src/main/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStream.java
+++
b/src/main/java/org/apache/commons/compress/compressors/bzip2/BZip2CompressorInputStream.java
@@ -31,6 +31,7 @@
import org.apache.commons.compress.compressors.CompressorException;
import org.apache.commons.compress.compressors.CompressorInputStream;
+import org.apache.commons.compress.huffman.HuffmanDecoder;
import org.apache.commons.compress.utils.BitInputStream;
import org.apache.commons.compress.utils.InputStreamStatistics;
import org.apache.commons.io.IOUtils;
@@ -60,16 +61,17 @@ static final class Data {
*/
final int[] unzftab = new int[256]; // 1024 byte
- // Needs indexes from 0 to MAX_CODE_LEN inclusive.
- final int[][] limit = new int[N_GROUPS][MAX_CODE_LEN + 1];
- // Needs indexes from 0 to MAX_CODE_LEN + 1 inclusive.
- final int[][] base = new int[N_GROUPS][MAX_CODE_LEN + 2];
- final int[][] perm = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 byte
- final int[] minLens = new int[N_GROUPS]; // 24 byte
+ /**
+ * Huffman decoding tables.
+ */
+ final HuffmanDecoder[] huffmanDecoders = new HuffmanDecoder[N_GROUPS];
+ /**
+ * Number of non-null {@link #huffmanDecoders}.
+ */
+ int huffmanDecodersCount;
final int[] cftab = new int[257]; // 1028 byte
final char[] getAndMoveToFrontDecode_yy = new char[256]; // 512 byte
- final char[][] temp_charArray2d = new char[N_GROUPS][MAX_ALPHA_SIZE];
// 3096
// byte
final byte[] recvDecodingTables_pos = new byte[N_GROUPS]; // 6 byte
// ---------------
@@ -159,85 +161,6 @@ private static void checkBounds(final int checkVal, final
int limitExclusive, fi
}
}
- /**
- * Builds the Huffman decoding tables for use by {@code
recvDecodingTables()}.
- *
- * @param alphaSize The alphabet size, guaranteed by the caller to be in
the range [2, 258]
- * (RUNA, RUNB, 255 byte values, and EOB).
- * @param nGroups The number of Huffman coding groups, guaranteed by the
caller to be in the range [0, 6].
- * @param dataShadow The data structure into which the tables are built;
requires
- * {@code temp_charArray2d} to be initialized.
- */
- static void createHuffmanDecodingTables(final int alphaSize, final int
nGroups, final Data dataShadow) {
- final char[][] len = dataShadow.temp_charArray2d;
- final int[] minLens = dataShadow.minLens;
- final int[][] limit = dataShadow.limit;
- final int[][] base = dataShadow.base;
- final int[][] perm = dataShadow.perm;
-
- for (int t = 0; t < nGroups; t++) {
- final char[] len_t = len[t];
- int minLen = len_t[0];
- int maxLen = len_t[0];
- for (int i = 1; i < alphaSize; i++) {
- final char lent = len_t[i];
- if (lent > maxLen) {
- maxLen = lent;
- }
- if (lent < minLen) {
- minLen = lent;
- }
- }
- hbCreateDecodeTables(limit[t], base[t], perm[t], len[t], minLen,
maxLen, alphaSize);
- minLens[t] = minLen;
- }
- }
-
- /**
- * Called by createHuffmanDecodingTables() exclusively.
- *
- * @param minLen minimum code length in the range [1, {@value
MAX_CODE_LEN}] guaranteed by the caller.
- * @param maxLen maximum code length in the range [1, {@value
MAX_CODE_LEN}] guaranteed by the caller.
- */
- private static void hbCreateDecodeTables(final int[] limit, final int[]
base, final int[] perm, final char[] length, final int minLen, final int maxLen,
- final int alphaSize) {
- for (int i = minLen, pp = 0; i <= maxLen; i++) {
- for (int j = 0; j < alphaSize; j++) {
- if (length[j] == i) {
- perm[pp++] = j;
- }
- }
- }
- // Ensure the arrays were not reused.
- Arrays.fill(base, 0);
- Arrays.fill(limit, minLen, maxLen + 1, 0);
- // Compute histogram of code lengths, shifted by 1.
- for (int i = 0; i < alphaSize; i++) {
- final int len = length[i] + 1;
- base[len]++;
- }
- // Compute cumulative counts: base[len] = # of codes with length < len.
- // In other terms: base[len] = index of the first code in the `perm`
table.
- for (int len = 1; len < base.length; len++) {
- base[len] += base[len - 1];
- }
- // Compute the last code for each length.
- int vec = 0;
- for (int len = minLen; len <= maxLen; len++) {
- // increment by the number of length `len` codes
- vec += base[len + 1] - base[len];
- // vec is now the last code of length `len` + 1
- limit[len] = vec - 1;
- vec <<= 1;
- }
- // Compute the bias between code value and table index.
- // base[minLen] cannot be computed using this rule, since limit[minLen
- 1] does not exist,
- // but has already the correct value 0.
- for (int len = minLen + 1; len <= maxLen; len++) {
- base[len] = (limit[len - 1] + 1 << 1) - base[len];
- }
- }
-
private static void makeMaps(final Data data) throws IOException {
final boolean[] inUse = data.inUse;
final byte[] seqToUnseq = data.seqToUnseq;
@@ -335,27 +258,24 @@ static void recvDecodingTables(final BitInputStream bin,
final Data dataShadow)
selector[i] = tmp;
}
- final char[][] len = dataShadow.temp_charArray2d;
-
- /* Now the coding tables */
+ /* Now the Huffman coding tables */
for (int t = 0; t < nGroups; t++) {
+ final int[] codeLengths = new int[alphaSize];
int curr = bsR(bin, 5);
- final char[] len_t = len[t];
for (int i = 0; i < alphaSize; i++) {
while (bsGetBit(bin)) {
curr += bsGetBit(bin) ? -1 : 1;
}
- // Same condition as in bzip2
- if (curr < 1 || curr > MAX_CODE_LEN) {
- throw new CompressorException(
- "Corrupted input, code length value out of range
[%d, %d]: %d", 1, MAX_CODE_LEN, curr);
- }
- len_t[i] = (char) curr;
+ codeLengths[i] = curr;
+ }
+ try {
+ // Same limits as in the reference C implementation of bzip2
+ dataShadow.huffmanDecoders[t] = new
HuffmanDecoder(codeLengths, alphaSize, 1, MAX_CODE_LEN);
+ } catch (final IllegalArgumentException e) {
+ throw new CompressorException("Invalid Huffman data: " +
e.getMessage(), e);
}
}
-
- // finally create the Huffman tables
- createHuffmanDecodingTables(alphaSize, nGroups, dataShadow);
+ dataShadow.huffmanDecodersCount = nGroups;
}
// Variables used by setup* methods exclusively
@@ -477,10 +397,6 @@ private void getAndMoveToFrontDecode() throws IOException {
final byte[] selector = dataShadow.selector;
final byte[] seqToUnseq = dataShadow.seqToUnseq;
final char[] yy = dataShadow.getAndMoveToFrontDecode_yy;
- final int[] minLens = dataShadow.minLens;
- final int[][] limit = dataShadow.limit;
- final int[][] base = dataShadow.base;
- final int[][] perm = dataShadow.perm;
final int limitLast = this.blockSize100k * 100000;
/*
* Setting up the unzftab entries here is not strictly necessary, but
it does save having to do it later in a separate pass, and so saves a block's
@@ -490,18 +406,14 @@ private void getAndMoveToFrontDecode() throws IOException
{
yy[i] = (char) i;
unzftab[i] = 0;
}
- int groupNo = 0;
int groupPos = G_SIZE - 1;
final int eob = dataShadow.inUseCount + 1;
- int nextSym = getAndMoveToFrontDecode0();
int lastShadow = -1;
+ // Initialize group, selector and huffmanDecoder
+ int groupNo = 0;
int zt = selector[groupNo] & 0xff;
- // All arrays have the same length
- checkBounds(zt, base.length, "zt");
- int[] base_zt = base[zt];
- int[] limit_zt = limit[zt];
- int[] perm_zt = perm[zt];
- int minLens_zt = minLens[zt];
+ HuffmanDecoder currentDecoder = getHuffmanDecoder(dataShadow, zt);
+ int nextSym = currentDecoder.decodeSymbol(bin);
while (nextSym != eob) {
if (nextSym == RUNA || nextSym == RUNB) {
int s = -1;
@@ -517,25 +429,11 @@ private void getAndMoveToFrontDecode() throws IOException
{
groupPos = G_SIZE - 1;
checkBounds(++groupNo, selector.length, "groupNo");
zt = selector[groupNo] & 0xff;
- // All arrays have the same length
- checkBounds(zt, base.length, "zt");
- base_zt = base[zt];
- limit_zt = limit[zt];
- perm_zt = perm[zt];
- minLens_zt = minLens[zt];
+ currentDecoder = getHuffmanDecoder(dataShadow, zt);
} else {
groupPos--;
}
- int zn = minLens_zt;
- checkBounds(zn, limit_zt.length, "zn");
- int zvec = bsR(bin, zn);
- while (zvec > limit_zt[zn]) {
- checkBounds(++zn, limit_zt.length, "zn");
- zvec = zvec << 1 | bsR(bin, 1);
- }
- final int tmp = zvec - base_zt[zn];
- checkBounds(tmp, perm_zt.length, "zvec");
- nextSym = perm_zt[tmp];
+ nextSym = currentDecoder.decodeSymbol(bin);
}
checkBounds(s, this.data.ll8.length, "s");
final int yy0 = yy[0];
@@ -573,47 +471,16 @@ private void getAndMoveToFrontDecode() throws IOException
{
groupPos = G_SIZE - 1;
checkBounds(++groupNo, selector.length, "groupNo");
zt = selector[groupNo] & 0xff;
- // All arrays have the same length
- checkBounds(zt, base.length, "zt");
- base_zt = base[zt];
- limit_zt = limit[zt];
- perm_zt = perm[zt];
- minLens_zt = minLens[zt];
+ currentDecoder = getHuffmanDecoder(dataShadow, zt);
} else {
groupPos--;
}
- int zn = minLens_zt;
- checkBounds(zn, limit_zt.length, "zn");
- int zvec = bsR(bin, zn);
- while (zvec > limit_zt[zn]) {
- checkBounds(++zn, limit_zt.length, "zn");
- zvec = zvec << 1 | bsR(bin, 1);
- }
- final int idx = zvec - base_zt[zn];
- checkBounds(idx, perm_zt.length, "zvec");
- nextSym = perm_zt[idx];
+ nextSym = currentDecoder.decodeSymbol(bin);
}
}
this.last = lastShadow;
}
- private int getAndMoveToFrontDecode0() throws IOException {
- final Data dataShadow = this.data;
- final int zt = dataShadow.selector[0] & 0xff;
- checkBounds(zt, dataShadow.limit.length, "zt");
- final int[] limit_zt = dataShadow.limit[zt];
- int zn = dataShadow.minLens[zt];
- checkBounds(zn, limit_zt.length, "zn");
- int zvec = bsR(bin, zn);
- while (zvec > limit_zt[zn]) {
- checkBounds(++zn, limit_zt.length, "zn");
- zvec = zvec << 1 | bsR(bin, 1);
- }
- final int tmp = zvec - dataShadow.base[zt][zn];
- checkBounds(tmp, dataShadow.perm[zt].length, "zvec");
- return dataShadow.perm[zt][tmp];
- }
-
/**
* @since 1.17
*/
@@ -924,4 +791,9 @@ private int setupRandPartC() throws IOException {
this.su_count = 0;
return setupRandPartA();
}
+
+ private static HuffmanDecoder getHuffmanDecoder(final Data dataShadow,
final int zt) throws IOException {
+ checkBounds(zt, dataShadow.huffmanDecodersCount, "zt");
+ return dataShadow.huffmanDecoders[zt];
+ }
}
diff --git
a/src/main/java/org/apache/commons/compress/compressors/deflate64/Deflate64Decoder.java
b/src/main/java/org/apache/commons/compress/compressors/deflate64/Deflate64Decoder.java
index 2bf8a53b5..d451da937 100644
---
a/src/main/java/org/apache/commons/compress/compressors/deflate64/Deflate64Decoder.java
+++
b/src/main/java/org/apache/commons/compress/compressors/deflate64/Deflate64Decoder.java
@@ -31,6 +31,7 @@
import java.util.Arrays;
import org.apache.commons.compress.compressors.CompressorException;
+import org.apache.commons.compress.huffman.HuffmanDecoder;
import org.apache.commons.compress.utils.BitInputStream;
import org.apache.commons.compress.utils.ExactMath;
import org.apache.commons.lang3.ArrayFill;
@@ -41,37 +42,6 @@
*/
class Deflate64Decoder implements Closeable {
- private static final class BinaryTreeNode {
- private final int bits;
- int literal = -1;
- BinaryTreeNode leftNode;
- BinaryTreeNode rightNode;
-
- private BinaryTreeNode(final int bits) {
- this.bits = bits;
- }
-
- void leaf(final int symbol) {
- literal = symbol;
- leftNode = null;
- rightNode = null;
- }
-
- BinaryTreeNode left() {
- if (leftNode == null && literal == -1) {
- leftNode = new BinaryTreeNode(bits + 1);
- }
- return leftNode;
- }
-
- BinaryTreeNode right() {
- if (rightNode == null && literal == -1) {
- rightNode = new BinaryTreeNode(bits + 1);
- }
- return rightNode;
- }
- }
-
private abstract static class DecoderState {
abstract int available() throws IOException;
@@ -134,8 +104,8 @@ void recordToBuffer(final int distance, final int length,
final byte[] buff) {
private final class HuffmanCodes extends DecoderState {
private boolean endOfBlock;
private final Deflate64State state;
- private final BinaryTreeNode lengthTree;
- private final BinaryTreeNode distanceTree;
+ private final HuffmanDecoder symbolDecoder;
+ private final HuffmanDecoder distanceDecoder;
private int runBufferPos;
private byte[] runBuffer = ArrayUtils.EMPTY_BYTE_ARRAY;
@@ -143,8 +113,8 @@ private final class HuffmanCodes extends DecoderState {
HuffmanCodes(final Deflate64State state, final int[] lengths, final
int[] distance) {
this.state = state;
- lengthTree = buildTree(lengths);
- distanceTree = buildTree(distance);
+ symbolDecoder = new HuffmanDecoder(lengths);
+ distanceDecoder = new HuffmanDecoder(distance);
}
@Override
@@ -170,7 +140,7 @@ private int decodeNext(final byte[] b, final int off, final
int len) throws IOEx
int result = copyFromRunBuffer(b, off, len);
while (result < len) {
- final int symbol = nextSymbol(reader, lengthTree);
+ final int symbol = symbolDecoder.decodeSymbol(reader);
if (symbol < 256) {
if (symbol < 0) {
throw new CompressorException("Invalid Deflate64
literal/length code %,d", symbol);
@@ -185,7 +155,7 @@ private int decodeNext(final byte[] b, final int off, final
int len) throws IOEx
final int runXtra = runMask & 0x1F;
run = ExactMath.add(run, readBits(runXtra));
- final int distSym = nextSymbol(reader, distanceTree);
+ final int distSym = distanceDecoder.decodeSymbol(reader);
if (distSym < 0 || distSym >= DISTANCE_TABLE.length) {
throw new CompressorException("Invalid Deflate64
distance code %,d", distSym);
}
@@ -219,10 +189,7 @@ boolean hasData() {
@Override
int read(final byte[] b, final int off, final int len) throws
IOException {
- if (len == 0) {
- return 0;
- }
- return decodeNext(b, off, len);
+ return len == 0 ? 0 : decodeNext(b, off, len);
}
@Override
@@ -243,7 +210,7 @@ boolean hasData() {
}
@Override
- int read(final byte[] b, final int off, final int len) throws
IOException {
+ int read(final byte[] b, final int off, final int len) {
if (len == 0) {
return 0;
}
@@ -380,71 +347,16 @@ Deflate64State state() {
FIXED_DISTANCE = ArrayFill.fill(new int[32], 5);
}
- private static BinaryTreeNode buildTree(final int[] litTable) {
- final int[] literalCodes = getCodes(litTable);
-
- final BinaryTreeNode root = new BinaryTreeNode(0);
-
- for (int i = 0; i < litTable.length; i++) {
- final int len = litTable[i];
- if (len != 0) {
- BinaryTreeNode node = root;
- final int lit = literalCodes[len - 1];
- for (int p = len - 1; p >= 0; p--) {
- final int bit = lit & 1 << p;
- node = bit == 0 ? node.left() : node.right();
- if (node == null) {
- throw new IllegalStateException("node doesn't exist in
Huffman tree");
- }
- }
- node.leaf(i);
- literalCodes[len - 1]++;
- }
- }
- return root;
- }
-
- private static int[] getCodes(final int[] litTable) {
- int max = 0;
- int[] blCount = new int[65];
-
- for (final int aLitTable : litTable) {
- if (aLitTable < 0 || aLitTable > 64) {
- throw new IllegalArgumentException("Invalid code " + aLitTable
+ " in literal table");
- }
- max = Math.max(max, aLitTable);
- blCount[aLitTable]++;
- }
- blCount = Arrays.copyOf(blCount, max + 1);
-
- int code = 0;
- final int[] nextCode = new int[max + 1];
- for (int i = 0; i <= max; i++) {
- code = code + blCount[i] << 1;
- nextCode[i] = code;
- }
-
- return nextCode;
- }
-
- private static int nextSymbol(final BitInputStream reader, final
BinaryTreeNode tree) throws IOException {
- BinaryTreeNode node = tree;
- while (node != null && node.literal == -1) {
- final long bit = readBits(reader, 1);
- node = bit == 0 ? node.leftNode : node.rightNode;
- }
- return node != null ? node.literal : -1;
- }
-
private static void populateDynamicTables(final BitInputStream reader,
final int[] literals, final int[] distances) throws IOException {
final int codeLengths = (int) (readBits(reader, 4) + 4);
- final int[] codeLengthValues = new int[19];
+ final int[] codeLengthValues = new int[CODE_LENGTHS_ORDER.length];
for (int cLen = 0; cLen < codeLengths; cLen++) {
codeLengthValues[CODE_LENGTHS_ORDER[cLen]] = (int)
readBits(reader, 3);
}
- final BinaryTreeNode codeLengthTree = buildTree(codeLengthValues);
+ // Decoder to decode the code lengths for the literal and distance
tables
+ final HuffmanDecoder codeLengthDecoder = new
HuffmanDecoder(codeLengthValues);
final int[] auxBuffer = new int[literals.length + distances.length];
@@ -456,7 +368,7 @@ private static void populateDynamicTables(final
BitInputStream reader, final int
auxBuffer[off++] = value;
length--;
} else {
- final int symbol = nextSymbol(reader, codeLengthTree);
+ final int symbol = codeLengthDecoder.decodeSymbol(reader);
if (symbol < 16) {
value = symbol;
auxBuffer[off++] = value;
diff --git
a/src/main/java/org/apache/commons/compress/huffman/HuffmanDecoder.java
b/src/main/java/org/apache/commons/compress/huffman/HuffmanDecoder.java
new file mode 100644
index 000000000..6ac24f2c4
--- /dev/null
+++ b/src/main/java/org/apache/commons/compress/huffman/HuffmanDecoder.java
@@ -0,0 +1,248 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.commons.compress.huffman;
+
+import java.io.EOFException;
+import java.io.IOException;
+import java.nio.ByteOrder;
+import java.util.Objects;
+
+import org.apache.commons.compress.compressors.CompressorException;
+import org.apache.commons.compress.utils.BitInputStream;
+
+/**
+ * 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.
+ * </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);
+ * int sym = dec.decodeSymbol(bitIn);
+ * }</pre>
+ *
+ * <h2>Thread-safety</h2> Instances are immutable after construction and may
be safely shared between threads.
+ *
+ * @since 1.29.0
+ */
+public final class HuffmanDecoder {
+
+ /**
+ * Maximum code length supported by this implementation.
+ */
+ private static final int MAX_SUPPORTED_CODE_LENGTH = 30;
+
+ /** Minimum non-zero code length */
+ private final int minLength;
+
+ /** Maximum non-zero code length */
+ private final int maxLength;
+
+ /**
+ * Symbols in canonical order (by length, then by symbol).
+ */
+ private final int[] sorted;
+
+ /**
+ * For each code length, the bias between code values and indices into the
sorted symbol table.
+ */
+ private final int[] bias;
+
+ /**
+ * For each code length, the largest left-justified code of that length.
+ */
+ private final int[] limit;
+
+ /**
+ * Constructs a decoder from canonical code lengths.
+ * <p>
+ * The {@code codeLengths} array provides, for each symbol index {@code i}
in {@code [0, codeLengthSize)}, the length (in bits) of that symbol's code. A
+ * value of {@code 0} marks an unused symbol. All non-zero lengths must be
{@code <= maxCodeLength}.
+ * </p>
+ *
+ * @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 IllegalArgumentException if any code length is out of range [0,
30].
+ */
+ public HuffmanDecoder(final int[] codeLengths) {
+ this(codeLengths, codeLengths.length, 0, MAX_SUPPORTED_CODE_LENGTH);
+ }
+
+ /**
+ * Constructs a decoder from canonical code lengths.
+ * <p>
+ * The {@code codeLengths} array provides, for each symbol index {@code i}
in {@code [0, codeLengthSize)}, the length (in bits) of that symbol's code. A
+ * value of {@code 0} marks an unused symbol. All non-zero lengths must be
{@code <= maxCodeLength}.
+ * </p>
+ *
+ * @param codeLengths code length per symbol; {@code 0} means the
symbol is not used; not {@code null}.
+ * @param codeLengthSize number of symbols to read from {@code
codeLengths} (must be {@code > 0} and {@code <= codeLengths.length}).
+ * @param minCodeLength minimum allowed code length present in {@code
codeLengths}.
+ * @param maxCodeLength maximum allowed code length present in {@code
codeLengths}.
+ * @throws NullPointerException if {@code codeLengths} is {@code null}.
+ * @throws IllegalArgumentException if {@code codeLengthSize} is out of
range, if any code length is out of range or if {@code maxCodeLength} exceeds
the
+ * implementation limit (30).
+ */
+ public HuffmanDecoder(final int[] codeLengths, final int codeLengthSize,
final int minCodeLength, final int maxCodeLength) throws
IllegalArgumentException {
+ Objects.requireNonNull(codeLengths, "codeLengths");
+ if (maxCodeLength > MAX_SUPPORTED_CODE_LENGTH) {
+ throw new IllegalArgumentException(String.format("maxCodeLength
(%d) exceeds supported limit (%d)", maxCodeLength, MAX_SUPPORTED_CODE_LENGTH));
+ }
+ if (codeLengthSize <= 0) {
+ throw new IllegalArgumentException(String.format("codeLengthSize
must be > 0; was %d", codeLengthSize));
+ }
+ if (codeLengths.length < codeLengthSize) {
+ throw new IllegalArgumentException(String.format("codeLengthSize
(%d) exceeds codeLengths.length (%d)", codeLengthSize, codeLengths.length));
+ }
+ // Validate and find min/max lengths
+ int min = maxCodeLength;
+ int max = minCodeLength;
+ for (int i = 0; i < codeLengthSize; i++) {
+ final int len = codeLengths[i];
+ if (len < minCodeLength || len > maxCodeLength) {
+ throw new IllegalArgumentException(
+ String.format("Invalid code length at symbol %d: %d
(expected in [%d, %d])", i, len, minCodeLength, maxCodeLength));
+ }
+ if (len == 0) {
+ continue; // unused symbol
+ }
+ if (len < min) {
+ min = len;
+ }
+ if (len > max) {
+ max = len;
+ }
+ }
+ this.minLength = min;
+ this.maxLength = max;
+ // Allocate outputs; we reuse them as scratch inside fillCodeTable
+ this.bias = new int[max + 1];
+ this.limit = new int[max + 1];
+ this.sorted = new int[codeLengthSize];
+ // Arrays are zero-initialized; no additional temps needed.
+ fillCodeTable(codeLengths, minLength, max, codeLengthSize, bias,
limit, sorted);
+ }
+
+ /**
+ * Gets the minimum code length (in bits) for this code set.
+ *
+ * @return minimum code length (in bits).
+ */
+ public int getMinLength() {
+ return minLength;
+ }
+
+ /**
+ * Gets the maximum code length (in bits) for this code set.
+ *
+ * @return maximum code length (in bits).
+ */
+ public int getMaxLength() {
+ return maxLength;
+ }
+
+ /**
+ * Builds canonical decode tables.
+ */
+ private static void fillCodeTable(final int[] codeLengths, final int
minLen, final int maxLen, final int codeLengthSize, final int[] bias,
+ final int[] limit, final int[] sorted) {
+ // 1) Histogram of code lengths
+ final int[] count = new int[maxLen + 1];
+ for (int symbol = 0; symbol < codeLengthSize; symbol++) {
+ final int len = codeLengths[symbol];
+ if (len == 0) {
+ continue;
+ }
+ count[codeLengths[symbol]]++;
+ }
+ // 2) 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
+ // Adjust offsets to point to the last element of each length
+ for (int symbol = 0; symbol < codeLengthSize; symbol++) {
+ final int len = codeLengths[symbol];
+ if (len == 0) {
+ continue;
+ }
+ sorted[++offset[len]] = symbol;
+ }
+ // 4) 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
+ for (int len = minLen; len <= maxLen; len++) {
+ bias[len] = limit[len] - offset[len];
+ }
+ }
+
+ /**
+ * Decodes one symbol from the input bitstream.
+ *
+ * @param in the source of bits (MSB-first) to read from.
+ * @return the decoded symbol index.
+ * @throws EOFException if the input ends in the middle of a Huffman code
word.
+ * @throws IOException if an I/O error occurs while reading from {@code
in}.
+ */
+ public int decodeSymbol(final BitInputStream in) throws IOException {
+ int len = minLength;
+ int code = readBitsFully(in, len);
+ while (len <= maxLength && code > limit[len]) {
+ final int b = readBit(in);
+ code = code << 1 | b;
+ len++;
+ }
+ if (len > maxLength) {
+ throw new CompressorException("Invalid Huffman code: " + code);
+ }
+ return sorted[code - bias[len]];
+ }
+
+ private static int readBit(final BitInputStream in) throws IOException {
+ final int bit = in.readBit();
+ if (bit < 0) {
+ throw new EOFException("Truncated Huffman bit stream");
+ }
+ return bit;
+ }
+
+ private static int readBitsFully(final BitInputStream in, final int
numBits) throws IOException {
+ final int code = (int) in.readBits(numBits);
+ if (code < 0) {
+ throw new EOFException("Truncated Huffman bit stream");
+ }
+ // Adjust for bit order
+ return in.getByteOrder() == ByteOrder.BIG_ENDIAN ? code :
Integer.reverse(code) >>> 32 - numBits;
+ }
+}
diff --git
a/src/main/java/org/apache/commons/compress/huffman/package-info.java
b/src/main/java/org/apache/commons/compress/huffman/package-info.java
new file mode 100644
index 000000000..3fc53a9c1
--- /dev/null
+++ b/src/main/java/org/apache/commons/compress/huffman/package-info.java
@@ -0,0 +1,25 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/**
+ * Huffman decoder package.
+ *
+ * @since 1.29.0
+ */
+package org.apache.commons.compress.huffman;
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 0095cf5c3..edbc21d36 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
@@ -103,22 +103,6 @@ private BitInputStream prepareDecodingTables(final int
codeLength) {
return new BitInputStream(new
ByteArrayInputStream(stream.toByteArray()), ByteOrder.BIG_ENDIAN);
}
- @Test
- void testCreateHuffmanDecodingTablesWithLargeAlphaSize() {
- final Data data = new Data(1);
- // Use a codeLengths array with length equal to MAX_ALPHA_SIZE (258)
to test array bounds.
- final char[] codeLengths = new char[258];
- for (int i = 0; i < codeLengths.length; i++) {
- // Use all code lengths within valid range [1, 20]
- codeLengths[i] = (char) (i % MAX_CODE_LEN + 1);
- }
- data.temp_charArray2d[0] = codeLengths;
- assertDoesNotThrow(
- () ->
BZip2CompressorInputStream.createHuffmanDecodingTables(codeLengths.length, 1,
data),
- "createHuffmanDecodingTables should not throw for valid
codeLengths array of MAX_ALPHA_SIZE");
- assertEquals(data.minLens[0], 1, "Minimum code length should be 1");
- }
-
@Test
void testFinishClose() throws Exception {
// Create a big random piece of data
@@ -222,14 +206,12 @@ void testRecvDecodingTablesWithOutOfRangeCodeLength(final
int codeLength) throws
void testRecvDecodingTablesWithValidCodeLength(final int codeLength)
throws IOException {
try (BitInputStream tables = prepareDecodingTables(codeLength)) {
final Data data = new Data(1);
-
- assertDoesNotThrow(
- () ->
BZip2CompressorInputStream.recvDecodingTables(tables, data),
+ assertDoesNotThrow(() ->
BZip2CompressorInputStream.recvDecodingTables(tables, data),
"Should accept code length " + codeLength + " within [" +
MIN_CODE_LEN + ", " + MAX_CODE_LEN + "]");
-
// We encoded 2 Huffman groups; both minLens should equal the
encoded codeLength
- assertEquals(codeLength, data.minLens[0], "Group 0 min code length
mismatch");
- assertEquals(codeLength, data.minLens[1], "Group 1 min code length
mismatch");
+ assertEquals(2, data.huffmanDecodersCount, "Expected 2 Huffman
groups");
+ assertEquals(codeLength, data.huffmanDecoders[0].getMinLength(),
"Group 0 min code length mismatch");
+ assertEquals(codeLength, data.huffmanDecoders[1].getMinLength(),
"Group 1 min code length mismatch");
}
}
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 33ae5c4d5..809dcdd63 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
@@ -173,7 +173,7 @@ void
testShouldThrowIOExceptionInsteadOfRuntimeExceptionCOMPRESS526() {
*/
@Test
void testShouldThrowIOExceptionInsteadOfRuntimeExceptionCOMPRESS527() {
- assertThrows(CompressorException.class,
+ assertThrows(EOFException.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/compressors/deflate64/Deflate64DecoderTest.java
b/src/test/java/org/apache/commons/compress/compressors/deflate64/Deflate64DecoderTest.java
index 4b609a519..f171fecf5 100644
---
a/src/test/java/org/apache/commons/compress/compressors/deflate64/Deflate64DecoderTest.java
+++
b/src/test/java/org/apache/commons/compress/compressors/deflate64/Deflate64DecoderTest.java
@@ -20,6 +20,7 @@
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.fail;
import java.io.ByteArrayInputStream;
@@ -58,7 +59,8 @@ void
testDecodeDynamicHuffmanBlockRejectsInvalidDistanceCode() throws Exception
final int len = decoder.decode(result);
fail("Should have failed but returned " + len + " entries: " +
Arrays.toString(Arrays.copyOf(result, len)));
});
- assertEquals("Invalid Deflate64 distance code -1", e.getMessage());
+ final String message = e.getMessage();
+ assertTrue(message.startsWith("Invalid Huffman code"), message);
}
}
diff --git
a/src/test/java/org/apache/commons/compress/huffman/HuffmanDecoderTest.java
b/src/test/java/org/apache/commons/compress/huffman/HuffmanDecoderTest.java
new file mode 100644
index 000000000..898656bd3
--- /dev/null
+++ b/src/test/java/org/apache/commons/compress/huffman/HuffmanDecoderTest.java
@@ -0,0 +1,102 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.commons.compress.huffman;
+
+import static org.junit.jupiter.api.Assertions.assertDoesNotThrow;
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.nio.ByteOrder;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import java.util.stream.Stream;
+
+import org.apache.commons.compress.utils.BitInputStream;
+import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+class HuffmanDecoderTest {
+
+ @Test
+ 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);
+ }
+ final HuffmanDecoder decoder = assertDoesNotThrow(() -> new
HuffmanDecoder(codeLengths, codeLengths.length, 1, 20),
+ "HuffmanDecoder constructor should not throw for valid
codeLengths array of MAX_ALPHA_SIZE");
+ assertEquals(decoder.getMinLength(), 1, "Minimum code length should be
1");
+ assertEquals(decoder.getMaxLength(), 20, "Maximum code length should
be 20");
+ }
+
+ static Stream<Arguments> testDecodeSymbols() {
+ // @formatter:off
+ return Stream.of(
+ // Simple case
+ // Symbol 0: 10
+ // Symbol 1: 11
+ // Symbol 3: 0
+ Arguments.of(
+ new int[] {2, 2, 0, 1},
+ new byte[] {(byte) 0b10_11_0_0_0_0},
+ Arrays.asList(0, 1, 3, 3, 3, 3),
+ ByteOrder.BIG_ENDIAN),
+ Arguments.of(
+ new int[] {2, 2, 0, 1},
+ new byte[] {(byte) 0b01_11_0_0_0_0},
+ Arrays.asList(3, 3, 3, 3, 1, 0),
+ ByteOrder.LITTLE_ENDIAN),
+ // Across byte boundary
+ // Symbol 0: 10
+ // Symbol 1: 11
+ // Symbol 2: 0
+ Arguments.of(
+ new int[] {2, 2, 1, 0},
+ new byte[] {(byte) 0b0_11_10_11_1, (byte)
0b0_11_10_11_0},
+ Arrays.asList(2, 1, 0, 1, 0, 1, 0, 1, 2),
+ ByteOrder.BIG_ENDIAN),
+ Arguments.of(
+ new int[] {2, 2, 1, 0},
+ new byte[] {(byte) 0b1_11_01_11_0, (byte)
0b0_11_01_11_0},
+ Arrays.asList(2, 1, 0, 1, 0, 1, 0, 1, 2),
+ ByteOrder.LITTLE_ENDIAN));
+ // @formatter:on
+ }
+
+ @ParameterizedTest
+ @MethodSource
+ void testDecodeSymbols(final int[] codeLengths, final byte[] inputData,
final List<Integer> expectedSymbols, final ByteOrder byteOrder) throws
IOException {
+ final HuffmanDecoder decoder = new HuffmanDecoder(codeLengths);
+ final Collection<Integer> actualSymbols = new ArrayList<>();
+ try (BitInputStream in = new BitInputStream(new
ByteArrayInputStream(inputData), byteOrder)) {
+ for (int i = 0; i < expectedSymbols.size(); i++) {
+ actualSymbols.add(decoder.decodeSymbol(in));
+ }
+ }
+ assertEquals(expectedSymbols, actualSymbols, "Decoded symbols do not
match expected symbols");
+ }
+}
