doubts regarding Rfc 1951 document

doubts regarding Rfc 1951 document

Post by rajasengol » Thu, 13 Mar 2008 16:01:16


I have gone through RFC1951 Deflate Compression Document,
In that section 3.1.1 Packing into bytes :
Data elements other than huffman codes are packed stating with with
the least significant bit
of the data element.
so,Huffman codes are non-reversed and data elements are reversed.
Is this is correct or not?
Then among the following which are all reversed ?
1.BFINAL
2.BTYPE
3.HLIT
4.HCLEN
5.HDIST
6.Code Length of Codelengths(which followed by HCLEN in Huffman
Dynamic Decompression)
7.Huffman codes for dynamic decompression.
8.Huffman code for fixed decompression.
9.extrabits for length and distance.
In my case data from gzip file is in hex.

1f 8b 8 8 ac 57 d7 47 0 b 75 72 6c 2e 74 78 74
0 ed 50 c1 4a 3 31 10 bd 17 fa f 3
62 b1 b4 64 6d bb 5b aa b0 88 1e 44 41 8b a8 37 29
4b 36 99 74 83 69 b2 4d b2 ae 7e 40 ff
db 2c db d2 aa e0 c5 ab 4 32 cc 9b 37 ef cd 4c e1
7d 79 1e 45 4b 6b aa d2 91 a5 31 4b 85
84 19 22 75 8b 45 cc ac 4a d2 7c 16 9d 93 46 47 b9
35 b5 c3 cc 17 16 29 8f b6 61 c2 79 c2
a7 93 24 66 71 3c 9b 22 46 23 ce 5 3b e5 38 16 79
3c 13 c9 f4 a2 50 29 ea 9e d2 af a9 f3
bd 75 6a 5 1b 8c ce 92 d1 f1 f8 ea e6 ee f6 39 84
d6 7b d0 4e 72 f4 bd bf db 79 31 a5 f
fe 54 65 61 14 21 df 17 f0 88 be b2 3a f3 1f 25 c2
be ba ae a8 92 42 a2 5d c0 75 a5 59 83
ce e9 a e1 e4 81 da 10 3d 5a 37 4 d8 f4 bb 9d e6
5d 2a 5 62 4b 3 1d ea e 6a d9 60 46
29 53 f 1b ca bd e1 95 c2 46 23 7b aa f2 83 ec ab
fc a6 1f 9a 2c 78 53 82 c2 37 dc cb 3a
f2 ab ca 8e a6 f 55 82 37 da 1f 3a 30 37 1e c1 17
8 8c 3a 24 bb f9 a5 e 4b 85 d5 f7 cc
76 87 1c c1 79 ea 25 23 ff d7 fb db f5 3e 1 1c 9c
8 68 26 3 0 0 fd


In the above data
1f 8b 8 8 ac 57 d7 47 0 b 75 72 6c 2e 74 78 74
0
header for gzip format ends here and compressed data starts in next
byte

BFINAL is 1;
BTYPE is 10 so Dynamic Decoding
HLIT is 280
HDIST is 1
HCLEN is 9

Am i, decoded correctly or not?

But code generated based on the code length of codelengths is
mismatched ( no such code found in the stream after 10 bd 17 )

can any one help me?
 
 
 

doubts regarding Rfc 1951 document

Post by Mark Adle » Thu, 13 Mar 2008 20:19:38


Now that you've read RFC 1951, you should also look at puff.c in the
zlib distribution (in contrib/puff). It was written to unambiguously
define the deflate format by virtue of being a working deflate
decompressor that is easy to read and understand.


"Reversed" is relative to some initial expectation, so I will try to
answer the question in absolutes.

Starting with the block descriptor, those three bits are the low three
bits of the first byte. The lowest bit (bit 0) is BFINAL. The next
two bits (bits 1 and 2) are BTYPE. BTYPE appears as a two-bit integer
with the least significant bit in the lowest (bit 1) position.

So a final static block has the low three bits: 011, i.e. starting
with the byte xxxxx011. A non-final dynamic block has the low three
bits 100 (staring byte xxxxx100).

All other integer (multi-bit) values in the format are stored the same
way. Bits are pulled and masked from the low end of the byte, and are
then treated as an integer with the least significant bit of the
integer in the least significant position in the extracted bits.

Huffman codes however are stored with the most significant bit in the
least significant position. So if you have a Huffman code like this:

A: 0
B: 10
C: 110
D: 111

Then the sequence CAB will look like:

010011

which you start reading from the bottom. So it is [01][0][011].

Mark