• Advertisement

Archived

This topic is now archived and is closed to further replies.

PNG Decoding Question

This topic is 5490 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, I am having some trouble understanding the PNG file format and would appreciate any help. I understand chunks and so forth. Specifically, I do not understand Dynamic and Fixed Huffman coding of the data blocks. I understand the concept of the Huffman Code process of replacing bit string code lengths for byte data and how to translate code lengths into a Huffman table, and also the LZ77 window compression process is simple enough. But how is it implemented in the data blocks in a PNG file? Either the book I''m reading is very confused or over my head?! Thanks alot.

Share this post


Link to post
Share on other sites
Advertisement
What book is that? If it is anything but the specification, you should go get it here: RFC 2083 - PNG (Portable Network Graphics) Specification Version 1.0

It was a while ago since I worked with PNG directly, so I cannot provide any help without re-reading the specs. If you specify and/or narrow your question, though, I might be able to help some.


Share this post


Link to post
Share on other sites
Thanks CWizard!

Specifically, I am having trouble with Section 3.2.6 and 3.2.7 (pages 11 and 12) of the Deflate compression format (ftp://ftp.rfc-editor.org/in-notes/rfc1951.txt).

In particular:
1) the 4 to 19 3-bit code length codes... What exactly are they? Why 3-bit? Why in order of 16 17 18 0 8 7 ...? I know they have something to do with Huffman coding the length codes in the data block, but this format makes absolutely no sense to me whatsoever. If these are the maximum lengths, it would make more sense to have 4 bits each because the max code length is 15, for example. Or if they are the frequency of length codes 0 thru 15, with 16 thru 18 being repetition codes, is the range of frequencies of each code length in a data block from 0 to 7 (3-bit)?! These are my two best guesses at what they might mean.

2) the number of literal/length codes equal to 257 to 286? Why? If the value of a literal is between 1 and 255, and the value of a length code is between 257 and 285, why make the number of length/literal codes equal to the value range of length codes?!

The book is "Compressed Image File Formats" by John Miano. He obviously knows his stuff, but it''s not getting across to me.

Share this post


Link to post
Share on other sites
quote:
Original post by BrianMJC
Specifically, I am having trouble with Section 3.2.6 and 3.2.7 (pages 11 and 12) of the Deflate compression format (ftp://ftp.rfc-editor.org/in-notes/rfc1951.txt).
That was a long time since I read it, but just did it again
quote:

1) the 4 to 19 3-bit code length codes... What exactly are they? Why 3-bit? Why in order of 16 17 18 0 8 7 ...? I know they have something to do with Huffman coding the length codes in the data block, but this format makes absolutely no sense to me whatsoever. If these are the maximum lengths, it would make more sense to have 4 bits each because the max code length is 15, for example. Or if they are the frequency of length codes 0 thru 15, with 16 thru 18 being repetition codes, is the range of frequencies of each code length in a data block from 0 to 7 (3-bit)?! These are my two best guesses at what they might mean.
First, most of the seemingly arbitrary lengths, and orders etc. are not easy to explain, but are presumable the result of statistical data gathered while developing the algorithm.

The Code Length codes are the codes used to to represent the lengths of the codes in the Literat/Length (L/L) and Distance (D) alphabet. There is a maximum of 19 Code Length codes (0-18). Why they are 3-bit, is that the maximum code length is 7 (bits), which is plenty enough to represnt the codes for L/L and D alphabet''s code lengths. I think your mixing the various levels of code lengths (very very easy to do ). Reread it some 10 times, and make sure you understand every single word of the spec. It will click sooner or later.
quote:
2) the number of literal/length codes equal to 257 to 286? Why? If the value of a literal is between 1 and 255, and the value of a length code is between 257 and 285, why make the number of length/literal codes equal to the value range of length codes?!
I do not understand your question fully. The number of Literal/Length codes is at least 257. 256 is the end-of-block code, and there must be at least one length code. In these 5 bits you have a value between 0 and 29. Add 257 to this and you get how many Literal/Length code lengths are defined.

"The value of a length code"? Not sure what you mean, but the code themselves are between 257 and 285, and can be decoded to a value range of 3-258.

Sorry, I''m not too good at explaining things like this, and it was a while since I wrote my last deflate (en|de)coder. The only thing to do is to keep reading the specs over and over again, while trying to simulate the process in your head (or on paper).


Share this post


Link to post
Share on other sites
CWizard, I really appreciate your help. It is sinking in more now that I''ve reread it about 25 times!!

Let me go through the format from start to end, to clarify my second question now that I am at least more clear on what exactly I do not understand. In a Dynamic Huffman compressed data block, after the 3-bit header, we encounter the 5-bit HLIT value, the number of Literal/Length Codes, values from 257 to 286. Does this define the number of Literal/Length Codes we will encounter in this entire data block or the number of Literal/Length Codes we actually use in this data block? Example: if HLIT = 00011 (257 + 3 = 260), is the value 260 interpreted as "There are 260 literal and length codes in this data block" or "We will use literal and length codes below or equal to 260; 261 thru 285 do not appear in this data block?"

Next we read in the 5-bit HDIST value, the number of Distance Codes (0 - 29). Again, is this how many Distance codes we will read in this data block or how many we use? Example: if HDIST = 00100 (1 + 4 = 5), is the 5 interpreted as "There are five distance codes in this data block" or "We will use distance codes 1, 2, 3, 4 and 5 and not 6 and above in this data block?"

Next we read 4-bit HCLEN, the number of Code Length Codes (4 - 19). Does this tell us how many 3-bit ''Code Lengths for the Code Length alphabet'' fields follow? Example: if we have a value of 7 (0011 = 4 + 3), does this mean we will encounter the code lengths for 16 17 18 0 8 7 9 and not the rest (6 10 5 ...)? Meaning we consider the remaining Code Lengths as set to zero, I imagine?

The remainder of the format is easy to follow, and I suspect I will understand the Fixed Huffman format once I get the Dynamic one down. Thanks again, you''re helping alot.

Peace.

Share this post


Link to post
Share on other sites
After rereading your post, I realize you''ve answered my main questions already. The values I ask about above indicate which codes are defined and do not tell us how many codes appear in the data block... the phrase in the documentation "number of" implies (to me at least!) "how many," but this is not so. That''s what confused me the most.

I think I can go and figure it out now, I''ll experiment. I wish there were a demonstration of an entire sample data block being decoded, that would make it alot easier!

Thanks again and be well.

Share this post


Link to post
Share on other sites
It''s best for you if you figure it out yourself, and I don''t have time right now to explain more. You can check out the C-example referenced in the deflate spec.


Share this post


Link to post
Share on other sites

  • Advertisement