Fast method to decompress huffman and arithmetic encoded data

Question

By nature, when decompressing huffman (and I assume also Arithmetic encoded data) we have to read it in bit by bit and then see how it traverses a huffman code tree that has the actual symbol value at each leaf node. Since processors are designed for byte or multiple byte read/write, this seems to be a very slow and inefficient process.

Since huffman coding and many other methods are used to encode image and video data which produces non-byte boundary aligned results, how do we speed up the decompression process? I would assume that instead of reading 1 bit at a time we read several bits or even bytes and then using some clever method, find all symbols in it at once. I think that this is how all codecs for video and image would work to decompress the compressed image data fast. However, this is only my assumption and I do not know of any details. Could someone kindly reveal the secret to me?

Answer 1

For actual implementations take a look at (C) programming codes for decoders.

Basically the process is simple, you create an abstraction such as

bits = get_bits(n)

Where, n is the n bits you want to read. the var bits is left aligned. It extracts it from some byte_buffer - say a 32 bit or 64 bit symbols.

NOTE: All, practical codecs put major symbols at 'Byte aligned' even though >internal symbols can be bit by bit.

Now for the implementation efficiency part, basically, irrespective of what huffman code will come out to be, (and hence whatever be the required n).

this is how simple get_bits can be implemented:

// At start
frame_buffer = 0x4444 
bits_delivered = 0 

n = 1 
mask = 0x8000
bits = (mask & frame_buffer) >> 32-n
mask = mask >> n 
bits_delivered += n
if(bits_delivered == 32) 
    { load_framebuffer( &frame_buffer) }  

(Actual code needs to take care of few more stuff boundary conditions) The actual data is first fetch into frame_buffer which is a 32 bit register inside ALU (actually 16/32/64 bit depending on type of CPU) and then rest of the processing is only inside ALU's registers only.

Only when you exhaust the frame_buffer, do you really flush that bit-buffer and get another integer from memory.

This is how it gets its efficient implementation. Hope this answers your question.

Answer 2

You basically described the process yourself. Say that the codes are at most $n$ bits long and you want to use $m \ge n$ bits at a time: you build a table with $2^m$ entries. Each entry will store the first symbol decodable from the sequence using the rightmost $k$ bits ($k \le n \le m$) and the number $k$.

Now you read $m$ bits from the stream (cur), keep $m$ more bits ready (buf), look in the table and you know the first symbol. Now you right shift cur of $k$ positions, move the rightmost $k$ bits from buf to the leftmost $k$ bits of cur and start again. As soon as buf is emptied, read anothr $m$ bits in.

$m$ should be of course some multiple of 8. The problem is that it can reasonably be 8 or 16. Nothing more, because such a table would be incredibly sparse and repeated. If you need something more, than more complex solutions exist, clustering codes by length and using a master table followed by multiple extension tables. Moreover an entry could have a list of decoded symbols if more than one fit in the $m$ bits.