The Blues Brothers Huffman Compression

From ModdingWiki
Jump to: navigation, search
The Blues Brothers Huffman Compression
Format typeCompression algorithm
TypeStream
I/O unit size1-byte in, 1-bit out
Games

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!)