Package dev.relism.flash.http2.hpack

Class Huffman

java.lang.Object
dev.relism.flash.http2.hpack.Huffman
public final class Huffman extends Object
RFC 7541 §5.2 / Appendix B: the fixed canonical Huffman code used to compress HPACK string literals. CODES/LENGTHS are transcribed verbatim from Appendix B (each pair cross-checked against the RFC's own "code as hex" / "code as bits" columns, which the RFC gives redundantly for exactly this reason — a transcription error in either column disagrees with the other). Every other structure in this class — the decode trie, the nibble-driven FSM, the padding-validity table — is built from that one 257-row table at class-init time, not hand-derived, so a mistake in this class's own logic (as opposed to the RFC table itself) shows up as a decode/round-trip test failure rather than a silently wrong hand-written FSM.

Decoding: a nibble-driven FSM

decode(byte[], int, int, byte[], int, int) processes each input byte as two 4-bit nibbles (high nibble, then low), doing one array lookup per nibble instead of one branch per bit. Each TRANSITIONS entry packs: the next trie state, whether a symbol was completed while consuming this nibble's 4 bits (at most one — the shortest real code is 5 bits, longer than a nibble, so two symbols can never complete within a single nibble transition, see buildTransitionTable() for the proof this relies on), and that symbol's byte value if so. A "dead" transition (this nibble's bits cannot be a prefix of any valid code, at this position) is a distinct packed flag the decode loop checks first.

Padding (RFC 7541 §5.2)

A Huffman-coded string is padded to a byte boundary with the high-order bits of the EOS code (all 1s), strictly fewer than 8 of them. Inserting the EOS code itself into the trie (as a real, if never-emittable, leaf) means every prefix of the all-1s path already exists as a trie node from ordinary trie construction — buildPaddingValidity() marks exactly those nodes (reachable only via 1-bits from the root, depth 1..7) as valid end-of-input states. Anything else left over when the input ends — an incomplete real code, or 8+ bits of trailing 1s — is COMPRESSION_ERROR, and so is the EOS symbol appearing anywhere in the input (RFC 7541 §5.2: "a Huffman-encoded string literal containing the EOS symbol MUST be treated as a decoding error").

  • Method Details

    • decode

      public static int decode(byte[] src, int srcOff, int srcLen, byte[] dst, int dstOff, int dstLimit)
      Decodes the Huffman-coded string src[srcOff, srcOff + srcLen) into dst[dstOff, dstLimit), returning the number of bytes written. The output bound is enforced as bytes are produced, not after accumulating into an unbounded buffer — callers pass a dst/dstLimit sized to their own maximum (typically Http2Limits.MAX_HPACK_STRING_LENGTH), and a string that would decode past it is rejected mid-decode.
      Throws:
      Http2Exception - COMPRESSION_ERROR — on any bit sequence that is not a prefix of a real code, on the EOS symbol appearing in the input, on invalid trailing padding (not all-1s, or 8+ bits), or on exceeding dstLimit

    • encode

      public static void encode(ByteWriter out, byte[] src, int off, int len)
      Huffman-encodes src[off, off + len), writing directly into out. Pads the final byte with the high-order bits of the EOS code (all 1s), per RFC 7541 §5.2.

    • encodedLength

      public static int encodedLength(byte[] src, int off, int len)
      The number of bytes encode(dev.relism.flash.bytes.ByteWriter, byte[], int, int) would produce for src[off, off + len) — the ceiling of the total bit length over 8.