Page 1 of 2 12 LastLast
Results 1 to 30 of 36

Thread: defluff - a deflate huffman optimizer

  1. #1
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post

    Lightbulb defluff - a deflate huffman optimizer

    '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!):
    Code:
    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!
    Attached Files Attached Files
    Last edited by jo.henke; 7th April 2011 at 23:40.

  2. The Following 3 Users Say Thank You to jo.henke For This Useful Post:

    Jaff (15th November 2013),nikkho (27th April 2014),porneL (2nd November 2013)

  3. #2
    Member Surfer's Avatar
    Join Date
    Mar 2009
    Location
    oren
    Posts
    200
    Thanks
    9
    Thanked 7 Times in 1 Post
    Thanks.

    Can someone compare this stuff with kzip?

  4. #3
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,462
    Thanks
    8
    Thanked 37 Times in 27 Posts
    Quote Originally Posted by Surfer View Post
    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).

  5. #4
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post

    defluff 0.2.1

    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:

    fileorigdefloptdefluffdefluff+defloptdeflopt+defluff
    1_advance.png89318931893089308930
    1_pngout.png86198603860186018601
    2_advance.png1912119119191191911919119
    2_pngout.png1868018625186241862418624
    3_advance.png87018676868386768676
    4_advance.png9221992215922159221392213
    4_pngout.png9669896522965249651796505

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

  6. #5
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    309
    Thanks
    0
    Thanked 1 Time in 1 Post
    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.
    Last edited by Intrinsic; 8th February 2011 at 01:51.

  7. #6
    Member
    Join Date
    Feb 2010
    Location
    Nordic
    Posts
    184
    Thanks
    3
    Thanked 3 Times in 1 Post
    Quote Originally Posted by Intrinsic View Post
    R:\RCmds>defluff.exe PNGChoices.png >sadakd.png
    you missed a redirection arrow thing?
    R:\RCmds> defluff.exe < PNGChoices.png > sadakd.png

  8. #7
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    309
    Thanks
    0
    Thanked 1 Time in 1 Post
    I knew that, i was just testing you...honest! :/

  9. #8
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    309
    Thanks
    0
    Thanked 1 Time in 1 Post
    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.

  10. #9
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post
    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.

  11. #10
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    449
    Thanks
    9
    Thanked 7 Times in 6 Posts
    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
    Last edited by SvenBent; 3rd March 2011 at 14:34.

  12. #11
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    449
    Thanks
    9
    Thanked 7 Times in 6 Posts
    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

    Code:
    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

  13. #12
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    449
    Thanks
    9
    Thanked 7 Times in 6 Posts
    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

    Code:
    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

  14. #13
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    342
    Thanks
    4
    Thanked 2 Times in 2 Posts
    Quote Originally Posted by SvenBent View Post
    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.
    http://schnaader.info
    Damn kids. They're all alike.

  15. #14
    Member
    Join Date
    May 2008
    Location
    Kuwait
    Posts
    190
    Thanks
    0
    Thanked 0 Times in 0 Posts
    BTW defluff fails with APNG files

  16. #15
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post
    @ 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.

  17. #16
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post

    Exclamation defluff 0.3.0

    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.

  18. #17
    Member
    Join Date
    May 2008
    Location
    Kuwait
    Posts
    190
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.)

  19. #18
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    342
    Thanks
    4
    Thanked 2 Times in 2 Posts
    Quote Originally Posted by maadjordan View Post
    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.
    http://schnaader.info
    Damn kids. They're all alike.

  20. #19
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post
    Quote Originally Posted by schnaader View Post
    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

  21. #20
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    342
    Thanks
    4
    Thanked 2 Times in 2 Posts
    To add something on-topic:

    Tested defluff on the first 100 episodes of Questionable Content.

    Code:
    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.
    http://schnaader.info
    Damn kids. They're all alike.

  22. #21
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    172
    Thanks
    6
    Thanked 36 Times in 22 Posts
    Looks promising, could you compile it on Mac OS X?

  23. #22
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post
    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.

  24. #23
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post
    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!

  25. #24
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    172
    Thanks
    6
    Thanked 36 Times in 22 Posts
    Quote Originally Posted by jo.henke View Post
    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).

  26. #25
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post

    defluff 0.3.2

    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

  27. #26
    Member
    Join Date
    May 2008
    Location
    England
    Posts
    309
    Thanks
    0
    Thanked 1 Time in 1 Post
    Top Man!

  28. #27
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    172
    Thanks
    6
    Thanked 36 Times in 22 Posts
    Are you still working on defluff? Do you plan to release it as open source in the near future?

  29. #28
    Member jo.henke's Avatar
    Join Date
    Dec 2008
    Location
    Europe
    Posts
    56
    Thanks
    0
    Thanked 3 Times in 1 Post
    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.

  30. #29
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    172
    Thanks
    6
    Thanked 36 Times in 22 Posts
    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).
    Attached Files Attached Files

  31. #30
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    2,061
    Thanks
    0
    Thanked 6 Times in 5 Posts
    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...

Page 1 of 2 12 LastLast

Similar Threads

  1. Huffman code generator
    By Shelwien in forum Data Compression
    Replies: 2
    Last Post: 24th May 2011, 03:50
  2. Ultra7z Optimizer 0.12 is out
    By Surfer in forum Data Compression
    Replies: 13
    Last Post: 30th December 2010, 01:22
  3. huffman's Coding
    By swapy in forum Data Compression
    Replies: 5
    Last Post: 12th August 2009, 23:51
  4. help : Psd optimizer
    By Yuri Grille. in forum Data Compression
    Replies: 25
    Last Post: 25th April 2009, 10:29
  5. Advanced Huffman Encoding
    By Simon Berger in forum Data Compression
    Replies: 28
    Last Post: 15th April 2009, 15:24

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •