The Blues Brothers Huffman Compression

The Blues Brothers Huffman Compression

Format type	Compression algorithm
Type	Stream
I/O unit size	1-byte in, 1-bit out
Games	The Blues Brothers Quik the Thunder Rabbit

The Blues Brothers Huffman Compression is an implementation of Huffman Compression.

For more information, check out Titus Interactive SQZ Compression.

Data type	Description
BYTE[2] unknown	Always zero?
UINT16LE decompressedSize	Size of decompressed data.
UINT16LE HuffmanTreeSize	Size of Huffman tree.
UINT16LE[HuffmanTreeSize / 2] HuffmanTree	Huffman tree. A node is a leaf node when the most significant bit is set, otherwise it's an internal node.
BYTE[] compressedData	Compressed data. The most significant bit of a byte is processed first, then the second most significant bit etc.

Source code

Some example code is available in various languages showing how to decompress files using the Huffman algorithm.

QuickBASIC

CONST fileIn = "SPRITE.SQV"
CONST fileOut = "SPRITE.OUT"

DIM unknown                 AS INTEGER
DIM decompressedSizeInteger AS INTEGER
DIM decompressedSize        AS LONG
DIM HuffmanTreeSize         AS INTEGER
DIM node                    AS INTEGER
DIM byteIn                  AS STRING * 1
DIM byteOut                 AS STRING * 1
DIM bitPosition             AS INTEGER
DIM bit                     AS INTEGER
DIM i                       AS LONG

OPEN fileIn FOR BINARY AS #1
OPEN fileOut FOR BINARY AS #2

GET #1, , unknown 'always zero?
GET #1, , decompressedSizeInteger
'QBasic doesn't have unsigned integers, so we have to hack around it this way
decompressedSize = VAL("&H" + HEX$(decompressedSizeInteger) + "&")
GET #1, , HuffmanTreeSize


DIM HuffmanTree(0 TO HuffmanTreeSize \ 2 - 1) AS INTEGER

'Load Huffman tree
FOR i = 0 TO HuffmanTreeSize \ 2 - 1
  GET #1, , HuffmanTree(i)
NEXT i


node = 0
bitPosition = 7
i = 0
DO WHILE i <> decompressedSize
  IF bitPosition = 7 THEN
    GET #1, , byteIn
  END IF

  bit = (ASC(byteIn) AND (2 ^ bitPosition)) \ (2 ^ bitPosition)
  bitPosition = bitPosition - 1
  IF bitPosition < 0 THEN
    bitPosition = 7
  END IF
 
  IF bit = 1 THEN
    node = node + 1
  END IF
  IF HuffmanTree(node) AND &H8000 THEN
    byteOut = CHR$(HuffmanTree(node) AND &HFF)
    PUT #2, , byteOut
    i = i + 1
    node = 0
  ELSE
    node = HuffmanTree(node) \ 2
  END IF
LOOP

CLOSE #1, #2

Credits

This file format was reverse engineered by Frenkel, who was inspired by Jesses. If you find this information helpful in a project you're working on, please give credit where credit is due. (A link back to this wiki would be nice too!)