Python PNG decoding - Huffman coding

Question

As a part of my homework, I am supposed to write a simple PNG reader in Python. I am forbidden to use any Python libraries that work with images, and as a result I should have a list lists(rows of image) of RGB touples of single pixels.

The decoder is supposed to read only the most basic PNG images, which consist only of IHDR, IDAT and IEND chunks, the IDAT only with basic RGB data. My program so far checks for the correct PNG header and decompress the IDAT chunk with zlib.decompress().

In this phase I am stuck for several days. The zlib decopress left the image data in the state, where I have byte representation of rows of the image like this:

every line begins with 1 byte, either 0x00, 0x04, 0x02 or 0x01. I have found out that 0x00 means that the row is in "raw data", meaning next bytes are representing R, G, or B of the pixel and so on till the end of the line (there is not actual newline but abother "header byte"). 0x04 or 0x02 however as I read are coded in Huffman coding and here lies my question:

How to decode these rows? Is there a python function for this (just like there is the zlib decompress for the inflate step) Also, last 2 rows begin with 0x01, which as I read about Deflate should mean "this is the last block in the stream." Why do I have that in last 2 rows of the image, not only the last one? And the data of the last 2 rows is also confusing, because some pixels are obviously in "raw" representation, but some are not.

Thank you very much, I tried to find my answer everywhere already...

Vojta

Answer 1

Huffman encoding is part of the deflate compression that zlib.decompress already undoes for you. According to section 4.5.4 of the PNG spec the first byte of each scanline is filter type, and the filters are described in section 9.

Answer 2

That first byte of data for each line doesn't affect compression: it tells which pre-filter was run on the data before compression, and it can be 0 to 4. This is descibed at http://www.w3.org/TR/PNG-Filters.html . And BTW, you can blame me--the idea of using a different filter for each scanline was mine. :-)