4 ms·
Incidentally, table-based canonical Huffman works best when the "root" of the Huffman codes is stored in the more significant bits, as that simplifies the algor
by userbinator 6y ago
Incidentally, table-based canonical Huffman works best when the "root" of the Huffman codes is stored in the more significant bits, as that simplifies the algorithm from having to do a bit string reversal and the codes remain in order in the table.
...but I believe DEFLATE goes the exact opposite way, for reasons unknown.
- Jasper_ 6y agoI believe you're getting confused. There's no bit string reversal in DEFALTE, it just changes your shift slightly. Both MSB and LSB have their advantages and disadvantages. As always, ryg has great posts on this stuff: https://fgiesen.wordpress.com/2018/02/19/reading-bits-in-far-too-many-ways-part-1/ https://fgiesen.wordpress.com/2018/02/19/reading-bits-in-far...
- userbinator 6y agoI meant that with the bit ordering that DEFLATE has (the root in the LSB), you can't simply add/subtract 1 to each code to get to the next one, because the carry goes the wrong way. With a normal (ascending) canonical code, e.g. "2 codes of length 3, 2 codes of length 4" becomes 000 001 0100 0101 when read into a register. With DEFLATE, the same codes would look like 000 100 0010 1010 so you need to pre-rotate the bits in your lookup table to match.
- tyingq 6y ago"There's no bit string reversal in DEFALTE" The DEFLATE RFC describes it as such. "Huffman codes in bit-reversed order (i.e., with the first bit of the code in the relative LSB position)."