Data Compression

Data Compression
[ Home ] [ Up ] [ Home Wiring ] [ Expanding TiVo ] [ WebTV Anecdotes ] [ Disc Pictures ] [ JA2 Details ] [ M.A.X. ] [ Incubation ] [ Designing File Formats ] [ Software Update ] [ Blocking Asian Spam ] [ PC Construction ] [ Early Copy Protection ] [ Data Compression ] [ Handling Unsportsmanlike Conduct Online ] [ Of Games and NATs ] [ Line of Sight ] [ Trex Decks ]

Hacking Data Compression

This is a twelve-part course on lossless data compression. It was originally presented in the "A2Pro" forum of the GEnie online service, starting back in October 1992 (almost exactly 10 years ago to the day that I type this).

Each part of the course consists of a lesson and some source code. The sources were presented in C and 65816 assembly language, the latter intended for use on an Apple IIgs computer. The C code was actually developed under SunOS, but was usable with either of the 16-bit compilers then available for the IIgs.

Some of the commentary is out of date. For example, this was written before gzip and the "deflate" algorithm existed, at a time when "freeze" was being explored as a replacement for the UNIX "compress" command. You can see the precursors to these in lesson 11. On the flip side, we're still using Huffman encoding (e.g. it's used in bzip2), and GIF LZW is still widely used.

I've made the lesson text available here. For the full original lesson files, complete with source code and other goodies, you can download the full archive in ShrinkIt format. You will need something like NuLib2 or CiderPress to unpack it.

Lesson 1: Introduction: Course overview and introduction to compression concepts.
Lesson 2: Basics: Discussion of RLE and differential coding.
Lesson 3: Somewhat Clever Ad-Hoc Schemes: Simple character encodings, MTF, digrams; intro to higher-order models.
Lesson 4: Shannon, Fano, and Huffman: Explanation of probability encoding.
Lesson 5: Adaptive Encoding: Adaptive vs. static methods, Splay trees, adaptive Huffman.
Lesson 6: Arithmetic Coding: How arithmetic encoding works; includes the CACM sources and variations.
Lesson 7: Ziv and Lempel: Discussion of LZ77 and LZ78.
Lesson 8: LZW: Detailed explanation of the LZW algorithm.
Lesson 9: NuFX and ShrinkIt: Discussion about the compression used in ShrinkIt.
Lesson 10: LZSS: Detailed explanation of the LZSS algorithm.
Lesson 11: LZH, LZARI, and LZB: How to improve LZSS with Huffman, arithmetic, and unary coding.
Lesson 12: HardPressed(tm): How to write compression modules for HardPressed.

I also have the original syllabus, which more or less matches the above.

Historical note: this was written during the same period that HardPressed was under development, and while I was working full-time. This might help to explain why a 12-week course was presented over a period of nine months.

For anyone intrigued by the "stackable" compression modules described in lesson 12, I have made the complete source code to HardPressed available on this site.