Toy huffman encoder

[gauntman]

As part of a project I am working on, I wrote a simple Huffman Tree text decoder. This consists of 2 parts: a C++ program that encodes strings, and a 6502 decoder that decodes strings. The C++ program analyzes an input string table, and generates a a fixed Huffman tree plus the encoded strings. The 6502 code decodes this, and prints the result.

 

Encoding produces compression rates that range anywhere from 50-75% of the original string table size. Although this is not fantastic compression (compared to Huffman + LZH or LZW), it still doubles as light encryption, and it is a fast, memory light decoder.

 

The zip file includes 4 files:

textenc.cpp - the C++ encoding code (if you are on Linux/Mac compile with "g++ textenc.cpp -o textenc" for Windows, use mingw or other compiler)

decode.asm - the decode routine + simple display and print routine for testing

strings.asm - an example string table generated by textenc on jeeves.txt

jeeves.txt - the string table used to generate strings.asm

decode.xex - the example Atari executable

 

Note that currently, the encoding is limited to text only (characters 0-125), and automatically performs ASCII to Atari internal screen byte conversion on the strings.

 

Depending on your purpose, make sure that the tree + decompression code + compressed data is not actually larger than the original text! The break-even point for me was around 0.5-1k of original text.

 

If you end up using this for anything, let me know!

huffman.zip

[tebe]

Huffman encoder (PC - Turbo Pascal), decoder (6502) http://madteam.atari8.info/uzytki/sqz.zip

[gauntman]

SQZ looks interesting, but it seems to be a packer/unpacker for entire programs(?). It does seem to implement not just Huffman encoding but also (less optimal) Shannon-Fano encoding.

 

I wrote my Huffman encoder for streaming short strings out of memory onto the screen. Of course, SQZ may be able to do this already, but my Polish consists mostly of online translation websites - which provide very unreliable results!