For learning purposes I try to implement PNG/zlib/DEFLATE decoding. From scratch, according to original specs.
At this moment I'm stuck at decoding this 2x2 image:
<- its here.
Specifically, at decoding DEFLATE's lengths/distances alphabets. These bytes:
represent DEFLATE bitstream inside zlib data section of IDAT chunk of PNG. Text version:
5,193,1,1,0,0,0,128,16,255,79,23,34,9,5,3,63,210,5,251
For debug purposes I also broke it down bit by bit:
Text version:
1010000010000011100000001000000000000000000000000000000000000001000010001111111111110010111010000100010010010000101000001100000011111100010010111010000011011111
According to this representation, out of 18 symbols after HCLEN only 3 are non zero: symbols 18, 2 and 1. Symbol 0 is not among them, which means that its length is zero and it is not used in Huffman coding of length/distance alphabets. This also means, that there are no lengths 0 among alphabets, which is strange for 2x2 image. When I try to decode lengths of literals all 257 of them have length of 1 or 2, which is of course impossible.
I think I misinterpret the data or the algorithm, but I cannot understand where.
For learning purposes I try to implement PNG/zlib/DEFLATE decoding. From scratch, according to original specs.
At this moment I'm stuck at decoding this 2x2 image:
<- its here.
Specifically, at decoding DEFLATE's lengths/distances alphabets. These bytes:
represent DEFLATE bitstream inside zlib data section of IDAT chunk of PNG. Text version:
5,193,1,1,0,0,0,128,16,255,79,23,34,9,5,3,63,210,5,251
For debug purposes I also broke it down bit by bit:
Text version:
1010000010000011100000001000000000000000000000000000000000000001000010001111111111110010111010000100010010010000101000001100000011111100010010111010000011011111
According to this representation, out of 18 symbols after HCLEN only 3 are non zero: symbols 18, 2 and 1. Symbol 0 is not among them, which means that its length is zero and it is not used in Huffman coding of length/distance alphabets. This also means, that there are no lengths 0 among alphabets, which is strange for 2x2 image. When I try to decode lengths of literals all 257 of them have length of 1 or 2, which is of course impossible.
I think I misinterpret the data or the algorithm, but I cannot understand where.
Share Improve this question edited Feb 5 at 12:45 hopeless-programmer asked Feb 4 at 21:59 hopeless-programmerhopeless-programmer 9907 silver badges20 bronze badges 2- 1 Please don't put screen shots in your questions. Or at least not just screen shots. They are useless, as we can't copy and paste anything from them. Please add to your question the actual 2x2 png image, and copies of the text that you had posted as screen shots. – Mark Adler Commented Feb 5 at 2:14
- @MarkAdler good point. Fixed. – hopeless-programmer Commented Feb 5 at 15:24
1 Answer
Reset to default 1You are flipping bits where you should not. Only the Huffman codes are considered flipped. Here is a disassembly of the zlib stream in that 2x2 PNG file using infgen:
! infgen 3.5 output
!
! PNG IHDR (13)
! PNG IDAT (22)
!
level 3
zlib 8
!
last ! 1
dynamic ! 10
count 257 2 18 ! 1110 00001 00000
code 18 2 ! 010 000 000
code 2 2 ! 010 000 000 000 000 000 000 000 000 000 000 000 000
code 1 1 ! 001 000
lens 1 ! 0
zeros 138 ! 1111111 11
zeros 116 ! 1101001 11
lens 2 ! 01
lens 2 ! 01
lens 1 ! 0
lens 1 ! 0
! litlen 0 1
! litlen 255 2
! litlen 256 2
! dist 0 1
! dist 1 1
literal 0 ! 0
literal 255 ! 01
literal 0 ! 0
literal 0 ! 0
literal 255 ! 01
literal 0 ! 0
literal 255 ! 01
literal 0 ! 0
literal 255 ! 01
literal 0 ! 0
literal 0 ! 0
literal 0 ! 0
literal 255 ! 01
literal 255 ! 01
literal 0 ! 0
literal 0 ! 0
literal 0 ! 0
literal 0 ! 0
end ! 11
! 000000
!
adler
!
! PNG IEND (0)