Understanding IDAT, reading DEFLATE's dynamic Huffman tree

Question

I am looking to better understand zlib, deflate, and PNG encoding. With that said, I am having trouble applying the specifications of RFC-1950 and RFC-1951 to the IDAT portion of a PNG.

Below is binary for an image.

The example image is 50x50 and all pixels are RGB(255,0,0).

Okay, after the IDAT, expect two bytes specified by zlib; the CMF [0000029] then the FLG [000002a] (no FLG.FDICT). As expected the hex is 78DA which means use DEFLATE, 32K window, and a high level of compression.

Starting with the least-significant bit of the next byte, there will be three bits for the DEFLATE header, one bit to specify the last block and two bits for compression type (none, fixed, or dynamic) [000002b].

To read bits see this.

0000024: 01000011 01001001 01000100 01000001 01010100 01111000  CIDATx
000002a: 11011010 11101101 11001111 00110001 00010001 00000000  ...1..
0000030: 00000000 00001000 00000000 10100001 11101111 01011111  ....._
0000036: 01011010 00110011 10111000 01111010 00001100 00000100  Z3.z..
000003c: 10100000 10101001 11111001 00100000 00010001 00010001  ... ..
0000042: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000048: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000004e: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000054: 00010001 00010001 00010001 00010001 00010001 00010001  ......
000005a: 00010001 00010001 00010001 00010001 00010001 00010001  ......
0000060: 00010001 00010001 00010001 00010001 00010001 10010001  ......
0000066: 10001011 00000101 10110000 00110011 01110101 10010110  ...3u.
000006c: 01111001 11000101 00011100 10110001 00000000 00000000  y.....
0000072: 00000000 00000000 01001001 01000101 01001110 01000100  ..

Mark Adler Mark Adler · Accepted Answer · 2018-11-02T11:02:56

The next three bits are from the bottom of 11101101. The 101 is 10 for a dynamic block and 1 indicating that this is the last block. That starts a 61-byte deflate stream, which decodes to the following (as disassembled by infgen):

last
dynamic
litlen 0 2
litlen 255 4
litlen 256 4
litlen 274 4
litlen 283 4
litlen 285 1
dist 3 1
dist 15 1
literal 0 255 0 0 255
match 196 4
literal 0
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 258 201
match 44 4
end

The first decompressed byte is a zero, and decompresses to 10,050 bytes.

Understanding IDAT, reading DEFLATE's dynamic Huffman tree

1 Answers