Huffman table entropy decoding simplification (in C)

Question

First time using this site to ask a question, but I have gotten many many answers!

Background:

I am decoding a variable length video stream that was encoded using RLE and Huffman encoding. The stream is 10 to 20 Kilobytes long and therefore I am trying to "squeeze" as much time out of every step that I can so it can be decoded efficiently in real time.

Right now the step I am working on involves converting the bitstream into a number based on a Huffman table. I do this by counting the number of leading zeros to determine the number of trailing bits to include. The table looks like:

       001xs    range -3 to 3
      0001xxs   range -7 to 7
     00001xxxs  range -15 to 15

And on till 127. The s is a sign bit, 0 means positive, 1 means negative. So for example if clz=2 then I would read the next 3 bits, 2 for value and 1 for sign.

Question:

Right now the nasty expression I created to do this is:

int outblock[64];
unsigned int value; 
//example value 7 -> 111 (xxs) which translates to -3

    value=7;

outblock[index]=(((value&1)?-1:1)*(value>>1));    //expression

Is there a simpler and faster way to do this?

Thanks for any help!

Tim

EDIT: Expression edited because it was not generating proper positive values. Generates positive and negative properly now.

I do not understand why are you counting the number of leading zeroes, what do those zeroes represent? Next, is the code snippet you posted performing the Huffman decoding of the stream or is it only building the table you are later using during actual decoding? — , Dec 25 '11 at 16:28
The zeros determine the number of trailing bits to read for a value. — Tim Z, Dec 25 '11 at 20:08
The zeros indicate the number of trailing bits to read for a value. The code snippet displays the current expression I have for converting the bits read from the stream into an output value. In the example if you had 2 leading zeros then you would need to read the next 3 bits. Those next 3 bits are 111 -> 7. This is the value you feed into the expression which produces a -3 (11 -> 3 and 1 for negative sign). I never actually generate a table. I was just curious if there was a way to "optimize" this expression I created because I have to use this expression approximately 2000 times every 10ms. — Tim Z, Dec 25 '11 at 20:17
What kind of codec is this? It's not the kind of huffman coding you use in JPEG at least. It resembles the calculation of the "additional bits". In JPEG the huffman code determines how many additional bits you'll need to code the coefficient. If the leading bit is zero the value translates directly from the binary represention with the length determined by the huffman code. Otherwise you subtract by (2^length)-1. — onemasse, Jan 01 '12 at 21:06
Its a variation of Huffman and RLE coding. The image follows JPEG specification up until this encoding step. — Tim Z, Jan 04 '12 at 21:50

score 0 · Answer 1 · edited May 23 '17 at 12:26

I just quickly googled "efficient huffman decoding" and found the following links which may be useful:

It seems the most efficient way to huffman decode is to use table lookup. Have you tried a method like this?

I'd be interested to see your times of the original algorithm before doing any optimisations. Finally, what hardware / OS are you running on?

Best regards,

Huffman table entropy decoding simplification (in C)

1 Answers1