Potential speedup for Huffman decompression

[mreineck]

As far as I understand, the current Huffman decompressor looks at the compressed stream one bit at a time, navigating through the tree depending on the value of that bit. I expect that this could be speeded up quite significantly with the following change:

• whenever the decompresor starts work on a new value, it looks at the next 8 bits in the stream, not just the next single bit.
• these 8 bits can be used in several (very small) lookup tables with information
  • whether these 8 bits contain a full key or not
  • if they contain a full key: how many bits the key had and what the corresponding value is
  • if they don't contain a full key: where in the tree to continue searching

After this first modified step, the search would continue exactly as before.
I'm not absolutely sure, but I expect this change could improve performance quite a lot, since most keys are short and since the total number of memory accesses is reduced drastically for the first 8 bits of each key.

Using the first 16 bits instad of 8 might also work, but then the size of the lookup tables may already be uncomfortably large (larger than L2 cache).