[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)