Deflate Algorithm - dynamic Huffman

Deflate Algorithm - dynamic Huffman

Post by glutrotesl » Wed, 07 Jan 2004 07:13:47


Hello !

I don't know why, but I don't understand how to start decoding a png.
I created a solid black 2x2 pixel png file for testing Purposes. Here
is a hexdump:

00000000 8950 4E47 0D0A 1A0A 0000 000D 4948 4452 .PNG........IHDR
00000010 0000 0002 0000 0002 0802 0000 00FD D49A ................
00000020 7300 0000 0774 494D 4507 D401 0513 0036 s....tIME......6
00000030 9E1F A5AB 0000 000B 4944 4154 789C 6360 ........IDATx.c`
00000040 4006 0000 0E00 01A9 9173 B100 0000 0049 @........s.....I
00000050 454E 44AE 4260 8200 END.B`.

Ok..... the first 8 bytes are the PNG signature followed by the
IHDR-Chunk. Then, there'S an optional tIME chunk....

Everything is fine. Now I analyze the IDAT chunk. The two bytes
following "IDAT" give me some information about that chunk (window
size is 32k, compression method is 8 -> "deflate", etc...).

Well, after processing all that stuff there's the zLib stream left,
no?
(63 60 40 06 00 00 0E 00 01 A9 91 73 B1)

In binary, it starts like this:
01100011 | 01100000 | 01000000 | .....

Since the bit ordering tells me that the LSB is on ther right side, I
take the first three bits in order to determine some info about that
block.

=> 1 - this is the last block in the zlib stream
10 - (read from right to left) it's compressed usign dynamic
huffman codes

The first question is: Am I right about dynamic huffman codes or do
these 2 bits tell me that the stream is compressed using fixed huffman
codes ??

And now.... How do I have to continue ? I would be very glad if
someone would show me the resulting LZ77 stream after decompressing
the huffman here.

I read the papers RFC1950 and RFC1951 and some other docs, but I don't
get it how to use the two alphabets.

Suppose, the data is compressed using fixed huffman codes, I would
start by using that little table in the middle of page11 of the
rfc1951. Doing that I would pick out the next 8 bits (from right to
left (byte per byte)):
01100xxx | 01100000 | 01000000 | 00000110 | .....
^^^^^ ^^^

=> 00110000 => this code would result in a literal value of 0. Is this
correct ? But how to continue ?
The next code results in a 0, too.

And then, there will be a 0001001 - this results in 265. And now ?

I think I'm completely stuck somewhere so please help. :-)

Thanks very much !
Tassilo
 
 
 

Deflate Algorithm - dynamic Huffman

Post by madle » Wed, 07 Jan 2004 11:46:50


a) You may need to read a book about compression to understand the
approaches referred to in the specification. Mark Nelson's is a good
one.

b) You can look at the "puff" source code in the zlib distribution
contrib directory for an easy-to-read example in C of decoding deflate
data.

c) You can just use zlib directly and avoid having to figure out all
of this.

You can find zlib at http://www.yqcomputer.com/

mark

 
 
 

Deflate Algorithm - dynamic Huffman

Post by glutrotesl » Wed, 07 Jan 2004 20:29:22

Ok got it... it's a fixed Huffman here.
Thanks anyway. Sometimes it's sufficent to sleep one night over the
problem in order to solve it :-)

Thanks !