[HN Gopher] Lz_xor ___________________________________________________________________ Lz_xor Author : wooosh Score : 99 points Date : 2022-08-09 18:07 UTC (4 hours ago) (HTM) web link (richg42.blogspot.com) (TXT) w3m dump (richg42.blogspot.com) | pcwalton wrote: | 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. | p4bl0 wrote: | The idea that a compressor is a compiler made me think back of | Chaitin's work on incompleteness and the limits of mathematics, | which I wrote a review of a few years ago: | https://p4bl0.net/shebang/the-limits-of-mathematics.html | hyperpape wrote: | 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. | terrelln wrote: | 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. ___________________________________________________________________ (page generated 2022-08-09 23:00 UTC)