CODEWITHSUNDEEP
compressiongzipzlibdeflateinflate
Rudy Montoya
Rudy Montoya

Reputation: 85

Dynamic Huffman: Bit Packing Clarity

I was just wondering if there are any good examples of Dynamic Huffman bit-packing. I don't understand the RFC material that well regarding bit-packing. I found a lot of great examples for Static Huffman here in Stack Overflow, however examples for Dynamic seems to be lacking.

In the RFC 1951 Section 3.1.1

             * Data elements are packed into bytes in order of
               increasing bit number within the byte, i.e., starting
               with the least-significant bit of the byte.
             * Data elements other than Huffman codes are packed
               starting with the least-significant bit of the data
               element.
             * Huffman codes are packed starting with the most-
               significant bit of the code.

I am confused about the reversal in data packing between Huffman Codes and Data Elements other than Huffman Codes. What constitutes Huffman Codes and Data Elements other than Huffman Codes. In which group do the codelengths, hlit, hclen, hdist, actual compressed data fall into? Thanks.

Upvotes: 0

Views: 359

Answers (2)

Mark Adler
Mark Adler

Reputation: 112502

The literal/length and distance codes in the compressed data and the code lengths code in dynamics headers are all Huffman codes and are reversed (the most significant bit of code goes into the least significant unused bit of the current byte being assembled, and so on). Those three are all of the Huffman codes in the deflate format. Everything else in the format, including the extra bits following some of those codes, are packed in their natural order (least significant bit goes into the next least significant unused bit).

Upvotes: 0

The Hard Way
The Hard Way

Reputation: 182

This is only my interpretation of https://www.rfc-editor.org/rfc/rfc1951 . The way I understand it, the first bullet point describes bit buffer output; the way the bit buffer is emptied into the bitstream. The second and the third deal bit with buffer input.

Example: 5-bit data element 11110 followed by a 4-bit huffman code 0001

Stored in a bit buffer: 01111 0001

Stored in a reversed bit buffer (that makes more sense): 1000 11110

Packed into bytes: 00011110 xxxxxxx1

Edit: In case that was the unclear part, "Huffman codes" has a special meaning in CS, referring to the actual codes that are/could be read from a tree. Anything else named Huffman, like "Huffman code lengths" is metadata and not codes.

Obviously, this order of packed bits is for simplest possible decoding using logical and shifting operations. Metadata is in the correct bit order for consumption. The Huffman codes are reversed. This way decoding can start before all the bits that form a code are in the bit buffer.

Upvotes: 0

Related Questions