ECT, an file optimizer with fast zopfli-like deflate compression

[fhanau]

Hello forum,
I created a new, lossless C++ file optimizer called ECT (for Efficient Compression Tool). Features:

GZIP
Gzip files can be created or optimized using a heavily modified version of zopfli that should be faster. On enwik8 (Intel i5_2500s @ 2.7Ghz, OS X 10.10):
Mode Size Time
2 (default, 1 isn't implemented for Gzip yet) 35.151.651B 0m56.188s
3 35.007.758B 2m59.846s
There are also modes 4 and 5, but they would need much more time.

PNG
For png optimization, there are several tools used: Mode 1 is based on optipng and cloudflares zlib fork. It just tries filter strategies 0 and 5 at zlib compression level 9. It is ~5.5 times faster and has .1% less recompression than optipng.
On the default mode 2 and above zopflipng is used for compression and optipng to determine the filter strategy. On average, Mode 2 should achive the compression ratio of zopflipng at default settings and be more than 10 times faster (This may sound like very much, but I not only sped up zopfli, but also improved dirty alpha cleaning. This allowed me to use less aggressive settings and still be as good as zopfli. On large files or files without transparent pixels my program will achive less compression and only slightly faster.) Mode 4 is slightly slower than zopflipng, but achieves 1% more compression.
When using Mode 2+, you can also enable multithreading. The current implementation uses the C++ thread library and isn't much faster (40% with 4 cores, more on large files) but will be replaced with an OpenMP implementation that will be faster.

JPEG
The JPEG recompression is based on mozjpeg and pretty much does what jpegtran does. For best compression you can enable metadata removal and progressive encoding.

https://github.com/fhanau/Efficient-Compression-Tool

Edit: The Windows binary has a bug in the deflate compression code and will corrupt your data. Do NOT use it! A new one will be uploaded soon.

[fhanau]

New Windows binary attached.

[a902cd23]

advpng -l *.png
File: Firefox screenshot.png
IHDR13 width:526 height:603 depth:8 color_type:2 compression:0 filter:0 interlace:0
IDAT 15784
IEND 0
File: Invoice.png
IHDR13 width:4811 height:6507 depth:1 color_type:3 compression:0 filter:0 interlace:0
PLTE 6
IDAT 160499
IEND 0
File: Description_scan.png
IHDR13 width:1864 height:1038 depth:4 color_type:3 compression:0 filter:0 interlace:0
PLTE48
IDAT 126827
IEND 0

First I converted all to 24 bit uncompressed png:
00953758 bytes - Firefox screenshot.png
94074044 bytes - Invoice.png
05814999 bytes - Description_scan.png

Then test:
015841 bytes - advpng_-4_-z_Firefox screenshot.png
018626 bytes - ECT_M1_Firefox screenshot.png
023169 bytes - pngout_Firefox screenshot.png

206511 bytes - advpng_-4_-z_Invoice.png
179235 bytes - ECT_M1_Invoice.png
157390 bytes - pngout_Invoice.png

127059 bytes - advpng_-4_-z_Description_scan.png
136267 bytes - ECT_M1_Description_scan.png
127017 bytes - pngout_Description_scan.png

ECT method M2 M3 M4 M5 destroyed png!

[lorents17]

fhanau thank you for your project!
I was interested in two points in your project:
1. The project pngwolf-zopfli a parameter --zopfli-maxsplit Prompt in your project uses a parameter in the code? According to my observations is better to use this parameter --zopfli-maxsplit=0
2. fast zopfli. Is it possible to make a separate program for PNG compression that is used only to him, without optimization of filters and other things. such works advdef

[necros]

if your software outperforms it`s png and gz optimization utilities pls consider taking part in http://nikkhokkho.sourceforge.net/st...=FileOptimizer ,

"Combining best of better worlds" deleted
"Combining best of better utilities" (c) 8-)

[lorents17]

When I compile the last version of the project arises such a problem when optimizing png

[fhanau]

@a902cd23: I'm sorry, it was a bug in dirty alpha cleaning. Should be fixed now.

@lorents17: In the new version maxsplit = 0 is used in Mode 3+ for Gzip to optimize speed and in all modes for PNGs.
Can you send me the file that causes the crash?

New version should be even faster:

enwik8
Mode 2: 46s 35.119.274B
Mode 3: 90s 35.012.368B

More binaries tomorrow.

[lorents17]

fhanau

this error causes any image PNG. I will wait on you compiled version.

Tell me, on account of my second question, you can make a version of the project, which does not change the optimization PNG, such as working advdef.

[fhanau]

@lorents Fixed in this binary, the github repo will be updated later.

Advdef-like behaviour should be easy to implement. I will add it soon.

[a902cd23]

New try of Version 0.1 compiled on Sep 9 2015

First: both advzip -r -4 and pngout
00015841 2015-04-23.Firefox.screenshot.png width:526 height:603
00157390 20150722.Invoice.png width:4811 height:6507
00151535 One.scanned.paged.png width:2500 height:3457
00113287 Lyca.Mobile.png width:1236 height:1104
00126975 Scanned.document.png width:1864 height:1038

Converted to 24 bit uncompressed
00953758 2015-04-23.Firefox.screenshot.png
94074044 20150722.Invoice.png
25972976 One.scanned.paged.png
04101428 Lyca.Mobile.png
05814999 Scanned.document.png

00018626 2015-04-23.Firefox.screenshot.png_M1.png
00016862 2015-04-23.Firefox.screenshot.png_M2.png
00016164 2015-04-23.Firefox.screenshot.png_M3.png
00015839 2015-04-23.Firefox.screenshot.png_M4.png
00015839 2015-04-23.Firefox.screenshot.png_M5.png

00179235 20150722.Invoice.png_M1.png
00163465 20150722.Invoice.png_M2.png
00160571 20150722.Invoice.png_M3.png
00160149 20150722.Invoice.png_M4.png
00160141 20150722.Invoice.png_M5.png

00174046 One.scanned.paged.png_M1.png
00156105 One.scanned.paged.png_M2.png
00152371 One.scanned.paged.png_M3.png
00151662 One.scanned.paged.png_M4.png
00151554 One.scanned.paged.png_M5.png

00122153 Lyca.Mobile.png_M1.png
04101428 Lyca.Mobile.png_M2.png crashed
04101428 Lyca.Mobile.png_M3.png crashed
04101428 Lyca.Mobile.png_M4.png crashed
04101428 Lyca.Mobile.png_M5.png crashed

00136267 Scanned.document.png_M1.png
05814999 Scanned.document.png_M2.png crashed
05814999 Scanned.document.png_M3.png crashed
05814999 Scanned.document.png_M4.png crashed
05814999 Scanned.document.png_M5.png crashed

No errors in PNG...

[lorents17]

I made the test of the new version, I optimized 3800 images PNG
ECT new -m2 - 1 183 578 721 bytes
ECT old -m2 - 1 183 994 164 bytes

ECT new -m4 - 1 170 830 140 bytes
ECT old -m4 - 1 170 875 356 bytes

iCatalyst /png:2 1 184 776 471 bytes
iCatalyst /png:1 1 170 505 450 bytes

If you allow, I would like to give advice.
As I understand, for optimization of PNG you use optipng + zopfli. Today optipng not the best option (PNG Optimization tools Overview). TruePNG in this plan is one many better (the initial code isn't present). On the second place there is PNGWolf (from the point of view of optimization only of filters). About it I to you recommend to develop zopfli since it is key feature of your project.

You could not make the compatibility with the original zopfli?

There are problems with the image optimization.

[fhanau]

Intel i5 2500S @2.7GHz, OSX 10.10.4 clang (Less compression w/ GCC)
Program Time Size Speedup
Mode 2: 44s 35.054.746B 7.15x
Zopfli: 315s 34.987.258B 1.0x
Mode 3: 105s 34.980.531B 3.0x
To put it in words: ECT is about 3 times faster than Zopfli and now also has more compression!

@lorents: ECT was designed to provide fast and efficient, lossless compression in one utility. Maximum compression was not a goal, it should be fast enough to be used on large databases. On some images, Truepng achieves more compression, but for that, aggressive options with several runs are needed which makes it too slow.
Devoloping the zopfli/deflate part is a good idea, I will possibly make it an seperate library one day.

[lorents17]

Thank you for new version!
There was such question, can you tell me what settings you can change to speed up the work of the original zopfl?

[fhanau]

To speed up the original zopfli, you have to sacrifice compression. A good way to do this is to decrease ZOPFLI_MAX_CHAIN_HITS in util.h. This will make some files much faster. You can also use less iterations.

In ECT, I did many low-level optimizations and used heuristics to save time and lose tiny amounts of compression, in other places (blocksplitting) I use more aggressive settings to increase compression. My deflate implementation could be even faster if the longest match function would be written in assembly but unfortunately, I can't do that .
By the way, this beats all deflate implementations in LTCB. Mr. Mahoney, if you read this, can you add ECT?

[comp1]

To speed up the original zopfli, you have to sacrifice compression. A good way to do this is to decrease ZOPFLI_MAX_CHAIN_HITS in util.h. This will make some files much faster. You can also use less iterations.

In ECT, I did many low-level optimizations and used heuristics to save time and lose tiny amounts of compression, in other places (blocksplitting) I use more aggressive settings to increase compression. My deflate implementation could be even faster if the longest match function would be written in assembly but unfortunately, I can't do that .
By the way, this beats all deflate implementations in LTCB. Mr. Mahoney, if you read this, can you add ECT?

As I think it was asked before. Adding a switch or making a version for absolute maximum compression would be very useful and ideal for me if you ever get the time. I understand that is not your goal at the moment, but I just wanted to add in that for me it would be great if that was made as well.

[lorents17]

Tell me, when can we expect a more stable version of the project? Now ect often falls in the optimization of PNG. When can we expect to optimize the PNG version without the optimization of the value of the filter, and use the value in the original PNG.

[fhanau]

New version.

Changelog:
Fixed crashes on windows
Gzip now remembers the modification time of the compressed file
Primitive alpha cleaning also in PNG Mode 1 (not only in higher modes)

And lorents, your version that doesn't change filters/etc. will come next week.

[Bulat Ziganshin]

My deflate implementation could be even faster if the longest match function would be written in assembly but unfortunately, I can't do that .

there are many 3rd-party variations of zlib, some include asm versions of longest_match. afair, even official zlib has such thing in "contributions" subdir. but the best way will be to employ binary search tree from lzma or 7z-deflate sources

[fhanau]

Lorents, here is your binary that doesnt change filter etc. It is not ECT, but zopflipng with transforms disabled and ECT's deflate plugged in as compression backend. Not tested, so it could be buggy (again).

Bulat Ziganshin, I cant use the asm longest match versions because zopfli's costmodel needs the shortest dist at every sublength while the asm versions only give the longest match. A binary tree approach sounds interesting, I will try to implement it.

[Bulat Ziganshin]

i suggest you to either use existing 7-zip implementations (lzma code is public domain), or at least study it very carefully. it's not a schoolbook binary tree, but much more efficient approach. also look at tornado 0.6a that contains this code extracted from lzma. it may be easier to understand and copy since it doesn't contain any extra code except for minimally required

[fhanau]

i suggest you to either use existing 7-zip implementations (lzma code is public domain), or at least study it very carefully. it's not a schoolbook binary tree, but much more efficient approach. also look at tornado 0.6a that contains this code extracted from lzma. it may be easier to understand and copy since it doesn't contain any extra code except for minimally required

Thank you.
I have implemented tornado's binary tree in ECT. It is faster, but I also encountered a few problems:

1. findallmatches() sometimes returns matches that are too long or no matches at all. I currently have to validate every match. Maybe I just implemented it wrong. Currently I create a BinaryTreeMatchFinder, findallmatches() on up to 32768(window size) bytes before the current block to init the hash findallmatches() for every byte (No FAST_BYTES parameter) and apply the matches to the costmodel. Do I need to do anything else?
2. How big does the BinaryTree need to be? Does this depend on the depth?
3. The Compression ratio is worse (16.24% vs.16.08%). This may be partially due to block split points being determined with a LongestMatch based strategy. Which matches does the BinaryTree not find? Can I improve this?

Source code is attached. Changes are in src/zopfli/squeeze.cpp and src/zopfli/Btree.cpp.

[lorents17]

In the new version compression speed significantly grew.

One there was a question, concerning gzip

ect -M1 -gzip C:\Users\Lorents\Desktop\1001
Processed 1 file
Saved 629.79KB out of 1.00MB (61.4732%)

ect -M2 -gzip C:\Users\Lorents\Desktop\1001
Processed 1 file
Saved 629.79KB out of 1.00MB (61.4732%)

Prompt, why results identical?

And second question

C:\Users\Lorents>C:\Users\Lorents\Desktop\7-zip\ect.exe -M2 C:\Users\Lorents\Desktop\1001.png
Processed 1 file
Saved 5.26KB out of 399.33KB (1.3162%)

C:\Users\Lorents>C:\Users\Lorents\Desktop\7-zip\deflopt.exe C:\Users\Lorents\Desktop\1001.png

***                 DeflOpt V2.07                 ***
***       Built on Wed Sep  5 18:56:30 2007       ***
***  Copyright (C) 2003-2007 by Ben Jos Walbeehm  ***



"C:/Users/Lorents/Desktop/1001.png"
Number of bytes saved: 1,037 (403,529 --> 402,492)
File rewritten.


Number of files processed  :        1
Number of files rewritten  :        1
Total number of bytes saved:    1,037
119,741,770 cycles.

C:\Users\Lorents>C:\Users\Lorents\Desktop\iCatalyst\Tools\apps\advdef.exe -z0 C:\Users\Lorents\Desktop\1001.png
      402492     1049311 260% C:\Users\Lorents\Desktop\1001.png
      402492     1049311 260%

C:\Users\Lorents>C:\Users\Lorents\Desktop\7-zip\ect.exe -M2 -gzip C:\Users\Lorents\Desktop\1001.png.gz
Processed 1 file
Saved 37.48KB out of 432.76KB (8.6616%)

C:\Users\Lorents>C:\Users\Lorents\Desktop\7-zip\deflopt.exe C:\Users\Lorents\Desktop\1001.png.gz

***                 DeflOpt V2.07                 ***
***       Built on Wed Sep  5 18:56:30 2007       ***
***  Copyright (C) 2003-2007 by Ben Jos Walbeehm  ***



"C:/Users/Lorents/Desktop/1001.png.gz"
Number of bytes saved: 579 (404,767 --> 404,188) (4,636 bits)
File rewritten.


Number of files processed  :        1
Number of files rewritten  :        1
Total number of bytes saved:      579
111,077,880 cycles.

Why so occurs?

[fhanau]

@lorents:
1. Mode 1 is not yet implemented for GZIP so Mode 2 is used.
2. -gzip gzips the file. This means that the whole file is compressed, not only the IDAT chunk containing the actual pixels. The image probably contains big metadata chunks, therefore the additional compression is so big.
By the way, this version was not intended for actual use and may be unstable. Feel free to use it, but a version with a BTree implementation and cleaned up code will use less time and much less memory.

[fhanau]

Merry Christmas!
I created a new version with Binary Tree Match Finder. It works correctly and is based on LzFind.c. This greatly improves compression in Mode 2 and 3. Speed is better on text, but worse on files with high redundancy. enwik8 is compressed in 27s! Thanks again, Bulat!

[Dimitri]

Merry Christmas
can we have an exe file please ???

[fhanau]

Merry Christmas
can we have an exe file please ???

Here you go

[nikkho]

Here you go

Any Win64 build?

[AiZ]

Hello,

I second nikkho's request : I've built a 64bit binary with MSYS2 but running it fails in 'ZopfliVerifyLenDist' function (assert(data[pos - dist + i] == data[pos + i]); ) of your modified zopfli/lz77.c. If I build with NDEBUG defined, gzip files generated are invalid. Can you fix it, please ?

Thanks in advance,

AiZ

[lorents17]

Hello
It is possible to receive the ECT version which doesn't change value of filters in PNG

[fhanau]

Hello,

I second nikkho's request : I've built a 64bit binary with MSYS2 but running it fails in 'ZopfliVerifyLenDist' function (assert(data[pos - dist + i] == data[pos + i]); ) of your modified zopfli/lz77.c. If I build with NDEBUG defined, gzip files generated are invalid. Can you fix it, please ?

Thanks in advance,

AiZ

Fixed.

@lorents: That is currently not a priority, but may come someday. Until then, you can use #19.