1) The handling of dynamic blocks leaves something to be desired. The parameters are left mostly undecoded. It'd be really neat if the Huffman symbols were listed somewhere, rather than just being left implicit.
2) The visualization falls apart pretty badly for texts consisting of more than one block (which tends to happen around 32 KB) - symbols are still decoded, but references all show up blank.
Large inputs make the page hang for a bit, but that's probably pretty hard to avoid.
And as an enhancement: it'd be really cool if clicking on backreferences would jump to the text being referenced.
Exactly, it misses out on explaining how the fixed Huffman table is interpreted to apply symbol and distance codes, or how dynamic tables are derived from the input itself. Sure it's the hardest part, but also the more interesting to visualize. As another commenter pointed out, we are just left with mysterious bit sequences for these codes.
As someone who's never really read that much on compression stuff, I have absolutely zero clue what this visualisation is actually showing me.
That's compounded by the lack of legend. What do the different shades of blue and purple tell me? What is Orange?
e.g. on a given text in an orange block it puts e.g. x4<-135. x4 seems to indicate that the first 4 binary values for the block are important, but I can't figure out what that 135 is referencing (I assume it's some pointer to a value?)
The byte counter seems broken somehow. "Compressing" a single character with a compression level of 0 says "12 bytes", yet in the visualization there's less than 8 bytes (~7.5).
When compressing with a level higher than 0, the bits also don't appear to add up to a natural number of bytes, so I'm thinking the visualization is missing some padding?
This is very work in progress, but for folks looking for a deeper explanation of how dynamic blocks are encoded, this is my attempt to visualize them.
(This all happens locally with way too much wasm, so attempting to upload a large gzip file will likely crash the tab.)
tl;dr for btype 2 blocks:
3 bit block header.
Three values telling you how many extra (above the minimum number) symbols are in each tree: HLIT, HDIST, and HCLEN.
First, we read (HCLEN + 4) * 3 bits.
These are the bit counts for symbols 0-18 in the code length tree, which gives you the bit patterns for a little mini-language used to compactly encode the literal/length and distance trees. 0-15 are literal bit lengths (0 meaning it's omitted). 16 repeats the previous symbol 3-6 times. 17 and 18 encode short (3-10) and long (11-138) runs of zeroes, which is useful for encoding blocks with sparse alphabets.
These bits counts are in a seemingly strange order that tries to push less-likely bit counts towards the end of the list so it can be truncated.
Knowing all the bit lengths for values in this alphabet allows you to reconstruct a huffman tree (thanks to canonical huffman codes) and decode the bit patterns for these code length codes.
That's followed by a bitstream that you decode to get the bit counts for the literal/length and distance trees. HLIT and HDIST (from earlier) tell you how many of these to expect.
Again, you can reconstruct these trees using just the bit lengths thanks to canonical huffman codes, which gives you the bit patterns for the data bitstream.
Then you just decode the rest of the bitstream (using LZSS) until you hit 256, the end of block (EOB).
If you're not already familiar with deflate, don't be discouraged if none of that made any sense. Bill Bird has an excellent (long) lecture that I recommend to everyone: https://www.youtube.com/watch?v=SJPvNi4HrWQ
9 comments
[ 4.2 ms ] story [ 29.7 ms ] threadI wonder if this can be blamed on the HN title auto-shortener or not...
1) The handling of dynamic blocks leaves something to be desired. The parameters are left mostly undecoded. It'd be really neat if the Huffman symbols were listed somewhere, rather than just being left implicit.
2) The visualization falls apart pretty badly for texts consisting of more than one block (which tends to happen around 32 KB) - symbols are still decoded, but references all show up blank.
Large inputs make the page hang for a bit, but that's probably pretty hard to avoid.
And as an enhancement: it'd be really cool if clicking on backreferences would jump to the text being referenced.
It would be cool if we could supply our own Huffman table and see how that affects the stream itself. We might want to put our text right there! https://github.com/nevesnunes/deflate-frolicking?tab=readme-...
That's compounded by the lack of legend. What do the different shades of blue and purple tell me? What is Orange?
e.g. on a given text in an orange block it puts e.g. x4<-135. x4 seems to indicate that the first 4 binary values for the block are important, but I can't figure out what that 135 is referencing (I assume it's some pointer to a value?)
When compressing with a level higher than 0, the bits also don't appear to add up to a natural number of bytes, so I'm thinking the visualization is missing some padding?
This is very work in progress, but for folks looking for a deeper explanation of how dynamic blocks are encoded, this is my attempt to visualize them.
(This all happens locally with way too much wasm, so attempting to upload a large gzip file will likely crash the tab.)
tl;dr for btype 2 blocks:
3 bit block header.
Three values telling you how many extra (above the minimum number) symbols are in each tree: HLIT, HDIST, and HCLEN.
First, we read (HCLEN + 4) * 3 bits.
These are the bit counts for symbols 0-18 in the code length tree, which gives you the bit patterns for a little mini-language used to compactly encode the literal/length and distance trees. 0-15 are literal bit lengths (0 meaning it's omitted). 16 repeats the previous symbol 3-6 times. 17 and 18 encode short (3-10) and long (11-138) runs of zeroes, which is useful for encoding blocks with sparse alphabets.
These bits counts are in a seemingly strange order that tries to push less-likely bit counts towards the end of the list so it can be truncated.
Knowing all the bit lengths for values in this alphabet allows you to reconstruct a huffman tree (thanks to canonical huffman codes) and decode the bit patterns for these code length codes.
That's followed by a bitstream that you decode to get the bit counts for the literal/length and distance trees. HLIT and HDIST (from earlier) tell you how many of these to expect.
Again, you can reconstruct these trees using just the bit lengths thanks to canonical huffman codes, which gives you the bit patterns for the data bitstream.
Then you just decode the rest of the bitstream (using LZSS) until you hit 256, the end of block (EOB).
If you're not already familiar with deflate, don't be discouraged if none of that made any sense. Bill Bird has an excellent (long) lecture that I recommend to everyone: https://www.youtube.com/watch?v=SJPvNi4HrWQ
Also for zopfli vs level 9 compression with this tool as-is.