I wonder how an LZ_ADD-compressed bitmap would compare to a PNG. PNG is basically just DEFLATE on a bitmap, but you first apply some additional encoding to each row to help the compressor, by expressing the row as a kind of difference from the previous row. It would be cool if that became unnecessary.
Lz_xor
11–14 of 14 posts
Re: Lz_xor
#12The 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
Here's an interesting counterargument to this by one of the leading AI researchers (creator of Keras and much more), François Chollet: https://www.youtube.com/watch?v=-V-vOXLyKGw
Re: Lz_xor
#13This 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 author is focused on GPU texture compression for games[1] so they're not too concerned with fast compression speed. Given a game will be played on (at a minimum) tens of thousands of machines, some of which may be quite limited (e.g. handheld consoles or mobile devices), the game developers are only more than happy to trade off once-off compression times for decompression size / speed. They'd likely only perform this on a later "release build" of their game too.
The author mentions in a tweet going from minutes to seconds for compression when switching CPU for GPU[2]. From memory he has made other references to a few seconds for compression being entirely reasonable for such tasks but I can't find a direct reference.
[1]: http://www.binomial.info/
[2]: https://twitter.com/richgel999/status/1476325003662667777
Re: Lz_xor
#14I 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.
Got it, there's no "LIT w/length" instruction in LZSS, so it's logically a new compare-and-branch every time a literal character is hit. I hadn't regarded it as a performance-wise argument, but size-wise for some reason.