defluff - a deflate huffman optimizer

[jo.henke]

'defluff' is a command line tool, which works on existing deflate streams. It repeats the huffman coding step of the deflate process, trying to find a representation that is as short as possible. Since most deflate implementations are optimized for speed, they don't try that hard, and defluff is often able to squeeze out a few more bits.

The already popular 'deflopt' tool has the same target, but has not all the algorithms of defluff implemented, and vice versa. For now, it is therefore a good idea to run both tools sequentially (see an older post for example results).

Currently supported file formats are:

• gzip - full support
• png - full support, including the apng extension (optimizing deflate chunks IDAT, fdAT, iCCP, iTXt, zTXt)
• zip - support for most pkzip 2.0 compatible files (the widespread ones)

No command switches are currently supported, and the usage is simply like that (input and output file must never be the same!):

Unix:  ./defluff <infile.gz >outfile.gz
Windows:  defluff.exe <infile.zip >outfile.zip

This software is still quite new and could contain bugs. Although all my tests were successful, you better always verify the output. You have been warned!

[Surfer]

Thanks.

Can someone compare this stuff with kzip?

[m^2]

Thanks.

Can someone compare this stuff with kzip?

They are not competitors. Defluff / Deflopt are meant to be used after kzip (or other compressor) to shave another few bytes (sometimes more).

[jo.henke]

I updated my initial post with a newer version of defluff that provides basic png support. It is just a quick hack that fails, if the deflated stream is embedded in more than one IDAT chunk. As long as defluff is used after png re-compression tools like advpng or pngout, this is not a problem. For full png compatibility I would have to restructure huge portions of my code, and I currently have no time for this. I just wanted to already release something you can play with ;)

However, here are some test results with the files from another thread:

No code has to be inserted here.

Files from advpng/pngout not in the list: deflopt and defluff were not able to reduce them further.

[Intrinsic]

I will integrate this into my png tool and see how it goes on my test files, should be able to post some results tomorrow. Although it uses pngout so maybe it won't help a lot if at all.

Edit: I just tried it on a few files quick and couldn't even get it to work, had to break out of it with ctrl+c. gave 0 byte files.

R:\RCmds>defluff.exe PNGChoices.png >sadakd.png
defluff 0.2.1 (experimental)
Copyright (c) 2010-2011 Joachim Henke

unexpected end of file
^C

If i just pressed return instead of breaking out of it it gave: unrecognized file format

The processed showed no activity.

This is on WinXP.

[willvarfar]

R:\RCmds>defluff.exe PNGChoices.png >sadakd.png

you missed a redirection arrow thing?
R:\RCmds> defluff.exe < PNGChoices.png > sadakd.png

[Intrinsic]

I knew that, i was just testing you...honest! :/

[Intrinsic]

I did get a chance todo some small tests, but wrist problems meant i didn't get too much done. Same findings as you though. Although on 1 file because your tool writes the data out again even if the size stays the same Deflopt was then able to reduce it further, so for example what happened:
Deflopt the file, no change
Defluff the file, no size change but data rearranged.
Deflopt was then able to reduce the file slightly.

Haven't tried these test using deflopt /b yet as that could yield more gains, or even losses.

[jo.henke]

While deflopt has stronger header optimizations implemented (for storing the Huffman table), defluff is often better suitable for encoding the data section. Therefore, in it's current state, defluff is indeed best used right before deflopt in most cases. But deflopt doesn't always do a perfect job (see the last row in the table of post #4), and I hope to be able to implement a superior set of algorithms in a future version of defluff.

[SvenBent]

my test so far show that defluff will make files bigger after deflopt & delfluf but deflop will not it look like that deflopt should come last however it seems like doing deflopt -> defluff -> delfop seems to help.
ima write my results in later tonight. however i was amazed that defluff gave gains on such heavily optimized files as i used.

--- edit ---
OMG horrible grammar

[SvenBent]

Here are some results of multiple run of deffluf and deflopt
its 4 volumes of Girls of Gaming.
I think the png are old jpg's though cause i can see some small evidence of jpeg transform noise in them
they where already heavily optimized with pngout (all filters and loys of chunksize trials. probably hundreds of runs of pngout /r on them to but not sure) advpng and deflopt.

Anyway her goes

GoG vol 1
original 	48,705,483
defluff		48,704,750
deflopt		48,704,707
defluff		48,704,749
deflopt		48,704,706
defluff		48,704,749
deflopt		48,704,706
defluff		48,704,749
deflopt /b	48,704,706
defluff		48,704,749


GoG vol 2
Original	58,087,679
defluff		58,087,104
deflopt				(25 files rewritten)
deflopt /b	58,087,060	(16 fiels rewritten)
defluff		58,087,102
deflopt 	58,087,060
deflopt /b	58,087,060	(15 files rewritten)
defluff		58,087,102
deflopt 	58,087,060	(24 files rewritten)
deflopt /b	58,087,060	(15 files rewritten)


GoG vol 3 - 104 files
Original	87,889,203
deflopt		87,889,203	(0 files rewritten)
defluff		87,888,588
deflopt		87,888,546	(23 filews rewritten)
defluff		87,888,584	
deflopt		87,888,545	(21 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)
deftlop /b	87,888,545	(16 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)
deflopt /b	87,888,545	(16 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)


GoG vol 4 - 100 files
original	69,139,311
deflopt		69,139,311	(0 files rewriten)
defluff		69,138,724
deflopt		69,138,679	(26 files rewritten)
defluff		69,138,718
deflopt		69,138,679	(22 files rewritten)
defluff		69,138,718
deflopt		69,138,679	(22 files rewritten)
defluff		69,138,718
deflopt /b	69,138,679	(49 files rewritten)
defluff		69,138,717
deflopt /b	69,138,678	(45 files rewritten)
defluff		69,138,717

Conclusion
- Defluff is a valued tool for png optimization with gives gains on even highly optimized files
- deflopt should generally run after defluff
- defluff will give gains on a deflopt'ed file. but doing deflopt again is still helpfull

[SvenBent]

Here are some results of multiple run of deffluf and deflopt
its 4 volumes of Girls of Gaming.
I think the png are old jpg's though cause i can see some small evidence of jpeg transform noise in them
they where already heavily optimized with pngout (all filters and loys of chunksize trials. probably hundreds of runs of pngout /r on them tom but not sure) advpng and deflopt.

Anyway her goes

GoG vol 1
original 	48,705,483
defluff		48,704,750
deflopt		48,704,707
defluff		48,704,749
deflopt		48,704,706
defluff		48,704,749
deflopt		48,704,706
defluff		48,704,749
deflopt /b	48,704,706
defluff		48,704,749


GoG vol 2
Original	58,087,679
defluff		58,087,104
deflopt				(25 files rewritten)
deflopt /b	58,087,060	(16 fiels rewritten)
defluff		58,087,102
deflopt 	58,087,060
deflopt /b	58,087,060	(15 files rewritten)
defluff		58,087,102
deflopt 	58,087,060	(24 files rewritten)
deflopt /b	58,087,060	(15 files rewritten)


GoG vol 3 - 104 files
Original	87,889,203
deflopt		87,889,203	(0 files rewritten)
defluff		87,888,588
deflopt		87,888,546	(23 filews rewritten)
defluff		87,888,584	
deflopt		87,888,545	(21 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)
deftlop /b	87,888,545	(16 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)
deflopt /b	87,888,545	(16 files rewritten)
defluff		87,888,584
deflopt		87,888,545	(21 files rewritten)


GoG vol 4 - 100 files
original	69,139,311
deflopt		69,139,311	(0 files rewriten)
defluff		69,138,724
deflopt		69,138,679	(26 files rewritten)
defluff		69,138,718
deflopt		69,138,679	(22 files rewritten)
defluff		69,138,718
deflopt		69,138,679	(22 files rewritten)
defluff		69,138,718
deflopt /b	69,138,679	(49 files rewritten)
defluff		69,138,717
deflopt /b	69,138,678	(45 files rewritten)
defluff		69,138,717

Conclusion
- Defluff is a valued tool for png optimization with gives gains on even highly optimized files
- deflopt should generally run after defluff
- defluff will give gains on a deflopt'ed file. but doing deflopt again is still helpfull

[schnaader]

I think the png are old jpg's though cause i can see some small evidence of jpeg transform noise in them

(Off-Topic, but perhaps interesting): You can try to compress them with lossless JPEG 2000. Files that were JPGs before will be smaller than the PNG version in most cases.

[maadjordan]

BTW defluff fails with APNG files

[jo.henke]

@ SvenBent: Thanks for sharing your testing results! Because you mentioned that your test files were already optimized with deflopt: It can make a difference, if defluff is directly run after kzip.

@ maadjordan: Thanks for the hint. The next version of defluff will bring full support for PNG and APNG files.

[jo.henke]

A new version is available at the top of this thread What's new:

• completed png support
• added apng support
• fixed a bug that could cause broken deflate output

Support for the apng extension in png files is now a unique feature of defluff, because deflopt either removes or doesn't optimize the additional frames.

[maadjordan]

Thanks for the release it worked on my test files (APNG)..
hope precomp support APNG in normal mode (with v0.41 APNG is not supported even in -slow mode.)

[schnaader]

Thanks for the release it worked on my test files (APNG)..
hope precomp support APNG in normal mode (with v0.41 APNG is not supported even in -slow mode.)

Slow mode should work. APNG has a new chunk, fDAT, that contains a zLib compressed stream like IDAT for PNG. Testing with this APNG gives 1 PNG stream of 40 KB and 20 zLib streams of 40 KB - although they can't be recompressed.

The only thing that won't work in slow mode is the concatenation of multiple fDAT chunks for one animation frame (similar to "PNG multi"). I'll look for some test files, if you have some, please let me know.

But thanks for the hint, I'll try to add APNG support in one of the next versions.

[jo.henke]

The only thing that won't work in slow mode is the concatenation of multiple fDAT chunks for one animation frame (similar to "PNG multi"). I'll look for some test files, if you have some, please let me know.

This could be the problem. Maadjordan's test file seems to contain at least a splitted deflate stream in multiple IDAT chunks. Otherwise defluff 0.2.1 shouldn't have failed on it. For testing you can find a few relevant files here: http://philip.html5.org/tests/apng/tests.html

[schnaader]

To add something on-topic:

Tested defluff on the first 100 episodes of Questionable Content.

Original                    13.638.081 bytes (100 files)
  DeflOpt                   13.254.721
    defluff                 12.208.001
      ...
      defluff x 6           12.201.512
        DeflOpt             12.201.166
          defluff           12.201.225
            ...
            defluff x 5     12.201.209
              DeflOpt       12.201.125  // best result
                defluff     12.201.207
                  DeflOpt   12.201.125

  defluff                   13.632.726
    ...
    defluff x 6             13.629.232
      DeflOpt               13.252.657
        defluff             12.223.991
          ...
          defluff x 6       12.217.546
            DeflOpt         12.217.202

As you can see, multiple passes of defluff often further improved the result. Perhaps you could add some option or change the behaviour so the program does this automatically until there are no more savings (like PNGOUT does, for example).

I tested the MD5 sums for the raw picture data (using IrfanView to convert PNG->RAW) afterwards each time and it always matched.

[caveman]

Looks promising, could you compile it on Mac OS X?

[jo.henke]

Yes, that's indeed my intended next step. I got OS X running in KVM already, but still need to install Xcode and a more recent compiler. Despite I'm very short on spare time, I hope to have a defluff Darwin binary within one week.

[jo.henke]

For Mac OS X users there is now a Darwin binary available for download. The version number 0.3.1 reflects minor internal changes that don't affect the functionality. Of someone is interessted in a PowerPC binary, just let me know!

[caveman]

For Mac OS X users there is now a Darwin binary available for download. The version number 0.3.1 reflects minor internal changes that don't affect the functionality. Of someone is interested in a PowerPC binary, just let me know!

Yes I would appreciate a PowerPC version, I wrote a tool called CryoPNG (in fact it's just OptiPNG with a dirty hack at the libpng level), it's backward compatible down to Mac OS X 10.3.9 and PowerPC G3.
I use it in conjunction with PNGOUT and DeflOpt to produce ultra-optimized PNG files of type 6 (RVB + Alpha), since I could only use DeflOpt via Wine on Intel Mac OS X (and this launches the heavy X Window system) I shifted my main development to Linux (but I receive way more requests about the Mac OS X version since apparently a lot of web-designers use Apple hardware).

[jo.henke]

Somehow I missed that the PNG chunks 'iCCP' and 'iTXt' can also contain deflate streams. But these are rarely used, so this was probably not a big loss. However the new version now also re-compresses these chunks.
And I made a Darwin PowerPC binary available

[Intrinsic]

Top Man!

[caveman]

Are you still working on defluff? Do you plan to release it as open source in the near future?

[jo.henke]

There are some more ideas to implement, but I probably won't make much progress during summer time. And indeed, I have planned to release the sources, once that is finished.

[caveman]

Joachim had you time to improve Defluff?
I've started some preliminary work to update the zlib, I'd like to patch it to directly produce optimized Huffman trees (the same way Deflopt and Defluff do) a lot of apps could benefit from this. I know that Deflopt and Defluff do some tricks that go beyond simple Huffman trees optimizations (like replacing some LZ matches of length 3 by 3 literals) but it would still be a nice first step to get the smallest possible Huffman headers right from zlib.

What I've done so far was to fix the way the lib computes the size of the blocks, it now keeps the length in bits for maximum precision. Next I will start to dump various Huffman headers to compare those produced by the lib and Deflopt/Defluff.

If you disclose your code using a license compatible with zlib I could reuse your work and your name would of course be credited in the patch. This would help me a lot (and avoid me a few headache).

[Shelwien]

Zlib uses huffman code so normally you can't generate a better code for the same block size and LZ tokens.
Possible options are:
1. optimization of codelength reduction step (zlib's workaround in the case that some codes in the tree are longer than 15 bits seemed a little weird)
But normally gzip etc work with 32k token blocks, so that reduction step simply is not used.
2. optimization of length table RLE - zlib uses a simple greedy method which is able to produce inoptimal results.
3. optimization of block parsing into tokens.

Only [3] can provide noticeable improvement, but it requires completely different data structures than ones used by zlib,
so integration of that looks complicated.
Such optimization also can be noticeably slow...