I'm trying to write a code to compress .png image files, but I'm having trouble implementing DEFLATE. I know how to write the LZ77 and Huffman code, but I'm not sure how to combine those two. I know I'm supposed to have pairs of distances and lengths and literals as the output of LZ77, but I'm not sure how to create the input to Huffman from them. I know there's supposed to be two Huffman trees, one for lengths and literals and the other one for distances, but I'm not sure how to implement that, specifically in image compression. Does anyone have any idea, or an example?
1 Answers
3
votes
You could just use zlib, which provides well-tested, efficient, and free-to-use code to compress to the DEFLATE format.
If you really want to implement your own, perhaps for pedagogical reasons, then you will first need to understand how to decode DEFLATE streams. Once you've written your own DEFLATE decoder, you will be in a much better position to write a DEFLATE encoder.
You need to read RFC 1951 many times, decode example DEFLATE streams by hand, and write your own inflate code, testing it on many streams. You can also look at puff.c for further edification. It is an unambiguous definition of the DEFLATE format by virtue of being a simple, working inflator written to be easy to understand. (Or at least, easier than the inflate code in zlib, which is written for maximum efficiency.)
