DEFLATE-Lite (Capstone)

Build a simplified DEFLATE-style compressor and decompressor.

Functions

func DeflateLiteCompress(data []byte) []byte
func DeflateLiteDecompress(encoded []byte) ([]byte, bool)

Constants

• Window size: 128 bytes
• Min match length: 3
• Max match length: 18

Tokenization (LZ77)

Greedy longest match (ties -> smallest distance), same rules as the LZ77 problem. If a match is longer than 18, emit multiple match tokens capped at 18.

Symbols

Literal/Length alphabet (0..272):

• 0..255 = literal byte value
• 256..271 = match length 3..18 (symbol = 256 + (len-3))
• 272 = end-of-block

Distance alphabet (0..127):

• symbol = distance - 1 (distance in [1..128])

Header format

Byte layout:

• Bytes 0..1: ASCII 'D','L'
• Byte 2: version = 1
• Byte 3: mode (0 = fixed codes, 1 = dynamic codes)
• If mode == 1:
  • Next 273 bytes: literal/length code lengths (0..255, 256..271, 272)
  • Next 128 bytes: distance code lengths (0..127)
• Remaining bytes: bitstream (MSB-first)

Fixed code lengths (mode 0)

• Literal/Length: all 273 symbols have length 9
• Distance: all 128 symbols have length 7

Bitstream encoding (MSB-first)

• For literal: emit canonical Huffman code for its literal symbol.
• For match: emit code for length symbol, then code for distance symbol.
• Finish with end-of-block symbol (272).
• Pad with zero bits to the next byte.

Notes

• Build canonical Huffman codes from the code lengths in the header.
• Decoder must reject invalid headers and return (nil, false).
• Input length <= 4096 (keeps code lengths reasonable).