Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lz_xor

richg42.blogspot.com

Post reply on HN
Print view View original

1–10 of 14 posts

Re: Lz_xor

#3

Post by terrelln »

This is very interesting!

I've tried something somewhat similar in the past. I was looking at implementing an extremely fast decompressor, with ratio similar to LZ4. I was able to get 2x the decompression speed of LZ4, but struggled with compression ratio. The idea was to have 16 byte matches, and allow the matches to apply a 16-bit mask, telling whether each byte is part of the match or a literal. Then I restricted the compressor to only be able to use 16 distinct masks.

This was extremely fast to decompress, because each 16-byte match is: load the 16-byte match into an AVX2 register, load 16 bytes of literals, load the mask you're using, shuffle the literals, then blend the literals and the match. And because the matches are fixed size, you can start the fetch for multiple matches in parallel.

However, the problem I ran into, and would love to solve, is that I also wanted fast-ish compression speed. And it is very hard to search for good matches quickly. Since you have holes in the match.

I guess the author is looking at GPU compression, so they are taking a somewhat brute-force approach. But I'd be interested to see how they're doing the match finding, and what kind of speed they're getting.

Re: Lz_xor

#4

Post by pcwalton »

Can a XOR-only decompressor do the standard LZ77 trick of encoding many repeated bytes with a copy operation that refers to not-yet-decompressed data? It seems to me that you'd have to have a lot of 0 patch bytes for that. Huffman coding could encode all the 0 bytes in 1 bit each, but that still loses over regular LZ77. It seems to me that you still might want to keep "COPY" around for RLE-style data.

Re: Lz_xor

#6

Post by sedatk »

I don't understand why the author encodes every literal byte as a separate instruction while in reality, they're just consecutive bytes?

The whole:

  LIT 13
  LIT 24
  LIT 65
  LIT 32
  ...
could have been written as a single instruction:

  LIT [13, 24, 65, 32, ...]
It's almost as if author tries too hard to support their point that their variant looks better.

"Notice how much faster it makes progress through the file vs. LZSS"

Yeah, because you encode every literal separately? It's all LIT instructions?

Re: Lz_xor

#7

Post by DannyBee »

pcwalton wrote: post #4

Can a XOR-only decompressor do the standard LZ77 trick of encoding many repeated bytes with a copy operation that refers to not-yet-decompressed data? It seems to me that you'd have to have a lot of 0 patch bytes for that. Huffman coding could encode all the 0 bytes in 1 bit each, but that still loses over regular LZ77. It seems to me that you still might want to keep "COPY" around for RLE-style data.

yes, since that is about how you handle the offsets most of the time. At most you just have an instruction for source side, and one for target side. I will say however, this is useful for files, but not for deltas, as it makes delta composability much more complicated, and also makes streaming harder.

(IE with only original-source copies, and a->delta1->delta2->delta3->b, composing delta1/2/3 prior to applying them is easy and simple to reason about. If you allow target side copies, it is a lot messier)

Way back in the day, when i upgraded subversion's delta format, i did a lot of work on testing out various mechanisms - in practice, target side copies were much worse, and much more expensive to process, than doing source-only copies and then zlib'ing the delta instructions + new data ;)

Re: Lz_xor

#8

Post by puffoflogic »

sedatk wrote: post #6

I don't understand why the author encodes every literal byte as a separate instruction while in reality, they're just consecutive bytes? The whole: LIT 13 LIT 24 LIT 65 LIT 32 ... could have been written as a single instruction: LIT [13, 24, 65, 32, ...] It's almost as if author tries too hard to support their point that their variant looks better. "Notice how much faster it makes progress through the file vs. LZSS"…

Yes and no. The author was making the point that each new LIT relied on an input-dependent branch, whereas when you're decoding XOR [a,b,c] the branch is on the pre-decoded length of the instruction. LIT could be encoded like this but isn't.

Re: Lz_xor

#10

Post by thesz »

hyperpape wrote: post #2

The initial link in this piece, Compression is Compilation, was really helpful to read before reading this piece: http://richg42.blogspot.com/2015/10/compression-is-compilati... . I think I got more out of it than this piece.

And the idea that compression is intelligence also should be mentioned: http://www.hutter1.net/ai/uaibook.htm
Post reply on HN