# The Blues Brothers Huffman Compression

From ModdingWiki

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