CODEWITHSUNDEEP
pngdeflate
hopeless-programmer
hopeless-programmer

Reputation: 990

Invalid length codes in DEFLATE format during PNG decoding

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:

png image <- its here.

Specifically, at decoding DEFLATE's lengths/distances alphabets. These bytes:

image hex

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:

enter image description here

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.

Upvotes: 0

Views: 42

Answers (1)

Mark Adler
Mark Adler

Reputation: 112502

You 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)

Upvotes: 1

Related Questions