Trying to understand zlib / deflate in PNG files

Question

I am currently writing a small PNG image input / output library for training. My problem is this:

I created a small PNG size of only 2 by 2 pixels and opened it in a hex editor to examine its contents. This is an image that I created using GIMP and saved with compression "9".

(Note that this is an enlarged image of the original image by 2 pixels;))

So, I think uncompressed, it would look something like this in memory:

00 00 00 FF 00 00 00 00 FF 00 FF 00 

when saving without alpha channel.

(I only stated this for clarity. I know about compression and did not expect to see this byte pattern in the file).

I extracted the IDAT block and split the block identifier (IDAT) and tail CRC value and got this sequence of bytes:

 08 D7 05 C1 01 01 00 00 00 80 10 FF 4F 17 10 48 06 0F FE 02 FE 

Now the first two bytes 08 D7 contain information about the encoded block. And the last four bytes 0F FE 02 FE must be the ADLER32 checksum.

This ultimately leaves me with the following bytes:

 05 C1 01 01 00 00 00 80 10 FF 4F 17 10 48 06 

These bytes are written in binary representation:

 0000 0101 1100 0001 0000 0001 0000 0001 0000 0000 0000 0000 0000 0000 1000 0000 0001 0000 1111 1111 0100 1111 0001 0111 0001 0000 0100 1000 0000 0110 

To better understand DEFLATE, I tried to “unzip” this sequence manually, at least before I understood it well enough to write a small tool. But I was quickly stuck.

RFC 1951 ( "DEFLATE Compressed Data Format Specification" ) indicates that each encoded block begins with a three-bit header. One bit indicates whether this is the last block and two more blocks indicating the compression method. Since I assume that the encoder used only one block here (this means that the first block is automatically the last one) and used the non-stationary Huffman tree, I am looking for the bit sequence “101”, but I cannot find it (and I cannot find any other likely headers “100” or “110”).

The RFC also says that there must be two byte values ​​LEN and NLEN, preserving the length of the block, where NLEN is one of the additions to LEN, but again I can not find four such bytes that satisfy this condition. I won’t even begin to happily find anything that could represent two Huffman trees.

I read RFCs 1951 and 1950 ( “ZLIB Compressed Data Format Specification” , as well as Wikipedia articles on zlib, DEFLATE, LZ77, and Huffman, as well as some small and rather useless articles on the Internet and several responses to “Stack Overflow”, but no one could not help me in my understanding.

I would really appreciate any help or hint!

Answer 1

I think you are missing how bits are packed inside bytes (see, for example, section 3.1.1 of the RFC )

  Data elements are packed into bytes in order of increasing bit number within the byte, ie, starting with the least-significant bit of the byte. 

Therefore, if the first byte is 05 = 0000 0101, the first bit is 1.

(By the way, of course, it is very instructive to look at things in such detail, but I wonder if you are not going too far, if you intend to understand PNG.)

Further, when you conclude that you found an uncompressed IDAT stream, remember that the pixels are encoded with one of five filters per line and that there is an extra byte at the beginning of each line that signals the type of filter. So you really won't find the raw 12 bytes 00 00 00 FF 00 00 00 00 FF 00 FF 00 , but instead 12 + 2 = 14 bytes.

Answer 2

In case this helps, here is a breakdown of the contents of the IDAT snippet:

 ! infgen 2.2 output ! zlib ! last dynamic count 257 2 18 code 1 1 code 2 2 code 18 2 lens 1 zeros 138 zeros 116 lens 2 2 1 1 ! litlen 0 1 ! litlen 255 2 ! litlen 256 2 ! dist 0 1 ! dist 1 1 literal 0 0 0 0 255 0 0 0 0 0 255 0 255 0 end ! adler 

You can get the infgen source code here .