Back in 1999 I wrote an implementation of adaptive Huffman coding and decoding in C++. Over the past couple of days I have been playing with converting it to 32-bit x86 assembler. I thought it might be of interest to other people on the messageboard, so I am posting my current work in progress (under the zlib license).

The C++ implementation was inspired by:

The Data Compression Book, 2nd ed.
by Mark Nelson
M&T Books, 1996, ISBN: 1558514341

Introduction to Data Compression
by Khalid Sayood
Morgan Kaufmann, 1996, ISBN: 1558603468

The most interesting part is probably the rescale function, which runs in-place and in linear time. It uses a sorted list of leafs and a queue of nodes, which are both kept inside the memory occupied by the tree while rebuilding.

The code is around 1k large and uses around 6k of work memory during compression and decompression.

Please note that this is a work in progress -- I have not optimised the code or done extensive testing. The current code encodes blocks of data, but I am working on a more general setup.

Oh, and yes -- it's NASM style assembler ;-)
Posted on 2003-01-29 04:12:49 by Jibz