Hacker News new | past | comments | ask | show | jobs | submit login

I 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...




I 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.


"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)."




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: