Changing PNG compression

[przemoc]

Project I found thanks to retweet by someone I follow on twitter.

Overview

Main idea was to change ZLIB's compression/decompression used in PNGs to different algorithms and see what's gonna happen.

I've even tried it once (at the beginning of 2011), but I was trying to do that using libpng, which was somewhat painful.

Some time ago, Noel Llopis tweeted about lodepng (actually, I've seen RT via Glenn Fiedler). I think I've header about LodePNG some time ago, but must've forgotten about it. So I've taken a look at it, and it's seems it's once of those pieces made by developer for developers.

It allows exchanging both whole ZLIB or only inflate/deflate methods. I've actually decided to do the second thing.

The only thing you actually need to do is to write your own lodepng_custom_inflate and/or lodepng_custom_deflate.

So I've created small app suitable for doing the test. Source code of test app is available in the repo. Please, keep in mind, this is PoC-like code, so it's more hacky-do-the-job-way than elegant way.

I've added few known, and lesser known algorithms

• snappy - http://code.google.com/p/snappy/
• dash - http://code.google.com/p/data-shrinker/
• lz4 - http://code.google.com/p/lz4/ http://fastcompression.blogspot.com/p/lz4.html
• lzham - http://code.google.com/p/lzham/ level 4
• bsc - http://libbsc.com/ (without sort transform)

snappy, data-shrinker, bsc were compiled with -O2, lzham with -O3 (accidentally), I'm not sure if lz4 had O2 or Os, I hope the first.

Algorithms were allowed to use only one thread (I think bsc is able to use more).

So skipping the PNG part this is actually comparison of few compression/decompression algorithms.

Results

Results are here.
Now what (I think) these results tells us?

• if you don't care about file size, but do care about load time, go for snappy
  
  • so for example it compressed 18Mb to 9.1Mb (when zlib shrinked it to 5.5), but the loading is almost 3 times that of zlib
  
  
• the same goes for dash, but (sorry to say) it's source code looks like PoC (and seems OOB/overflows are possible), so I'd probably NOT use it in real world software
• if you'd like better-than-zlib ratio, with comparable load-times go for LZHAM deterministic parsing variant
• now there is LZ4, it's load times, are not as good as snappy's but it's compression ratio is slightly better, and what's really nice, you could probably do the decompressor in just a few lines of code, and simple code
• and there is BSC, keeping in mind, that it has the best compression ratio, it's kinda surprising, that it actually has quite good compression time, OTOH, decompression time is terribly awful
  
  • seems like a good candidate for compressing stuff downloaded from internet, it compresses quite fast, and for end-user, if the file has already been downloaded, decompression time shouldn't really matter

http://code.google.com/p/png-fun/
http://code.google.com/p/png-fun/wiki/results

[m^2]

Something seems wrong with the results.
I've seen quite a few benches of Snappy and LZ4 and it's the 1st time when I see the latter having worse decompression times.
I looked into the source:
https://code.google.com/p/png-fun/so...se/wrapLz4.cpp
And it barely resembles the original:
https://code.google.com/p/lz4/source/browse/trunk/lz4.c
I thought that the author may be using some older revision and went back all the way to r2 and I think no, it seems to be a totally independent implementation.
So the performance results are misleading. And the strength is not well tested either, for example lodepng deflate implementation is quite bad. If he tried the 7-zip one, it would score better. If he decoded with zlib, this one would be much better too. At least he's clear about what he uses here...not so much with LZ4 as the encoder is LZ4hc and that's why LZ4 is much stronger than Snappy / Shrinker. Oh, and where's LZO? It's 1x1_999 is very good when it comes to decompression efficiency.

[Cyan]

Good point,
in order to explain why he created his own gimLz4Decompress() function,
the author states in the source code :

// I had a problem when using original LZ4_uncompress...

It could have been interesting to know which problem, in order to solve it

[gim]

)Hi all,

First of all, thanks to przemoc, for pointing me here.

Regarding LZ4, the problem I had is the original decompressor, didn't decompress whole stream created by lz4hc (sounds kinda bad, doesn't it)...
But as I've written, I'm not sure if LZ4 wasn't actually compiled with -Os, so maybe gcc fscked something up, I haven't investigated it, I've assumed,
that the "hc" version might generate output that is incorrectly interpreted by decompressor, that's why I've added my own implementation, basing
on description of LZ4 format. (so yeah m^2 is right this is misleading)
I'll try to find some time to generate the data. (maybe even tomorrow).

As for lode-deflate m^2 is perfectly right, lode's implementation is faar from perfect, i know that,
that's why I'm actually calling it lode-inflate/lode-deflate.

As for usage of LZ4hc, I know it trades speed for ratio, using it was quite intentional.

And good point about LZ0, dunno why I haven't thought about including it. If I have some more time I'll add it.

Also I'd like to redo all the tests, and compile all the libs/algorithms with similar flags to be more fair.

I know there are looots of algorithms out there, and I know there are already good comparisons of those algorithms.
As you've seen I've selected only a few, that were of some interest to me, bsc was actually kinda artificially added
to show there are also algorithms with much better compression ratio. (and yeah I know it's not the best one,
but comparing to better ones, this one has not-that-bad decompression speed )

[gim]

Hi,

I've pushed test case to the repository
http://code.google.com/p/png-fun/sou...Flz4-test-case

(I've checkout LZ4 from svn repo)

Here are results, that I get:

\-(161633:hg$)-- ./lz4test.c
testcase.bin: OK
test_lz4hc_output.bin: OK
 [+]   compressed 1000 to 151
 [+] decompressed 45 from 151
 [+] gimlz4decomp 1000 from 151

EDIT
ok, I must do something wrong, as I've just checked using "lz4demo" tool:

*** Compression CLI using LZ4 algorithm , by Yann Collet (Aug 15 2012) ***
Compressed 1000 bytes into 159 bytes ==> 15.90%
Done in 0.00 s ==> inf MB/s
*** Compression CLI using LZ4 algorithm , by Yann Collet (Aug 15 2012) ***
Successfully decoded 1000 bytes 
Done in 0.00 s ==> inf MB/s

EDIT2

I think I've found source of problem, I probably should have been using

LZ4_uncompress_unknownOutputSize

, and not

LZ4_uncompress

...

[gim]

Something seems wrong with the results.
I've seen quite a few benches of Snappy and LZ4 and it's the 1st time when I see the latter having worse decompression times.

Great thanks, for pointing my mistake!

I've updated the code, run tests on LZ4 again, and updated results:
http://code.google.com/p/png-fun/wik...ts_2012_Aug_15

(Actually I was suspecting LZ4 should be faster, as it's "format" is still LZ-based, but
drops bit-based operations, that bothers other LZ-based compressors)

I'll try to add LZ0 to the results during next weekend.