Results 1 to 22 of 22

Thread: Huffmix: a PNGOUT -r catalyst

  1. #1
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts

    Huffmix: a PNGOUT/KZIP -r/-rn catalyst

    Hello,
    let me introduce you a new tool called Huffmix.

    As you probably know PNG and Gzip compression is based on Deflate.
    A Deflate stream is made of one or more blocks.
    PNGOUT/KZIP lets you choose how many blocks it produces (-n option, or -b to set the block split threshold).
    PNGOUT/KZIP also has a random switch (-r randomized initial tables "good for many trials with same options", this is -rn in KZIP).
    PNGSlim alike scripts used to run hundreds of random trials in a row and only kept the smallest PNG file produced (this takes a lot of time).

    Huffmix compares two files produced in random mode and cherry-picks the smallest blocks to combine them into a new file.

    For instance if we have 3 blocks.
    File A:
    block 1: 110 bits
    block 2: 317 bits
    block 3: 272 bits
    Overall: 699 bits

    File B:
    block 1: 104 bits
    block 2: 312 bits
    block 3: 289 bits
    Overall: 705 bits

    Until now optimization scripts would have kept File A and deleted File B (since A is smaller than B), Huffmix combines File A and File B into File C by picking the smallest blocks, this gives:

    File C:
    block 1: 104 bits (from File B)
    block 2: 312 bits (from File B)
    block 3: 272 bits (from File A)
    Overall: 688 bits

    We end up with a smaller file and managed to take profit of the calculations done to produce the biggest file, it works like a catalyst.
    Of course since there's randomness involved it will not always work as demonstrated, nevertheless my first tests suggests that it actually works pretty well.

    After about 20 cycles of pngout + deflopt + defluff + huffmix these 3 already optimized files are now a few bytes smaller:
    bigmac.png 33906 -> 33902 bytes
    getadrink.png 65317 -> 65293 bytes
    mouse.png 105035 -> 104866 bytes


    Huffmix 0.6b1 is available for testing.

    Usage: huffmix [options] file1.[png|gz] file2.[png|gz] output.[png|gz]
    Options:
    -v Verbose
    -q Quiet
    -k Keep same block sequence as in first file

    output can be the same as file1 or file2 (this is a fast and easy way to screw your file if there's a bug in Huffmix, you have been warned)

    Version 0.6b1
    - solves some "Could not find matching sub-blocks" problems

    Version 0.5b4
    - internal number of Deflate blocks limit set to 1024
    - a memory allocation bug correction (led to rare segfaults or unexpected EOF)

    Version 0.5b2/b3
    - handles .gz files (gzip files created by kzip2gz)
    - internal number of Deflate blocks limit set to 600
    - a memory allocation bug correction (led to rare segfaults)

    Version 0.4b2
    - new -k and -q options
    - Huffmix has its own webpage : http://frdx.free.fr/huffmix/

    Version 0.4b1
    - no longer copies the input file if it's the same as the output.
    - allows you to combine files with different numbers of blocks (e.g. -n3 and -n5).
    Code:
     File Type C-Offset C-Length U-Offset U-Length
       A    2         0   289296        0   200724
       A    2    289296    11622    31014    46169
       A    2    300918    34023    3c46d    54457
    
     File Type C-Offset C-Length U-Offset U-Length
       B    2         0   110543        0    75987
       B    2    110543   104305    128d3    67393
       B    2    214848    75383    23014    57344
       B    2    290231    11608    31014    46169
       B    2    301839    34029    3c46d    54457
    
     File C-Offset C-Length
       A         0   289296
       B    290231    11608
       A    300918    34023
    
    IDAT new size 41872 (0xa390) bytes, saved 14 bits, output file size 41929 bytes
    Occasionally this will produce files that have different blocks compared to those produced by PNGOUT, use the -k option to preserve the block sequence.


    To ensure that PNGOUT will not modify filter or palette entries it has to be called with these options:
    pngout -ks -kp -f6

    There was a bug in PNGOUT in -f5 mode. Use the latest version of PNGOUT (May 2012 or February 2013) with Huffmix.

    For instance a simple Huffmix roundtrip looks like this:
    Code:
    pngout -force -ks -kp -f6 -r -y my_file.png my_temp_file.png
    defluff <my_temp_file.png >my_defluffed_temp_file.png
    huffmix my_file.png my_temp_file.png my_file.png
    huffmix my_file.png my_defluffed_temp_file.png my_file.png
    
    or
    
    kzip -rn -y my_temp_file.zip my_file
    kzip2gz my_temp_file.zip my_temp_file.gz
    defluff <my_temp_file.gz >my_defluffed_temp_file.gz
    huffmix my_file.gz my_temp_file.gz my_file.gz
    huffmix my_file.gz my_defluffed_temp_file.gz my_file.gz
    Start over again.

    Todo list:
    - FreeBSD version
    - Code clean up
    - Handle type zero blocks
    - Add support for full .zip files
    - Remove limitation on internal number of Deflate blocks (1024 since 0.5b4)
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	bigmac-hm.png 
Views:	147 
Size:	33.1 KB 
ID:	1591   Click image for larger version. 

Name:	getadrink-hm.png 
Views:	140 
Size:	63.8 KB 
ID:	1592   Click image for larger version. 

Name:	mouse-hm.png 
Views:	153 
Size:	102.4 KB 
ID:	1593  
    Attached Files Attached Files
    Last edited by caveman; 14th May 2013 at 18:39. Reason: 0.6b1 release

  2. #2
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    48
    Thanks
    7
    Thanked 0 Times in 0 Posts
    The interesting idea, and is the version for Windows?

  3. #3
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,422
    Thanks
    6
    Thanked 26 Times in 20 Posts
    Todo list:
    - Mac OS X port
    - Windows port
    - Smarter file copying when nothing to do
    - Handle asymmetric blocks
    - Handle type zero blocks

  4. #4
    Member
    Join Date
    Oct 2009
    Location
    usa
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Results look good, and it is a very great application for those who want to squeeze the last bytes out of PNG files.

    How easy would it be to port the Linux version to DOS?

  5. #5
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Quote Originally Posted by zyzzle View Post
    How easy would it be to port the Linux version to DOS?
    If by DOS you mean Windows NT/2000/XP/Vista/7 command line... it's available now.

  6. #6
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    As I wrote earlier I suspected a bug in PNGOUT when using the -f6 option, Ken Silverman was kind enough to check it out and he has found a bug in... -f5 mode.
    A new version of PNGOUT is available today (dated 07/02/2011).

    And before lorents17 shows up with smaller versions of the images I used, here is what I get after a few hours:
    bigmac.png 33902 -> 33900 bytes (2 bytes smaller)
    getadrink.png 65293 -> 65286 bytes (7 bytes smaller)
    mouse.png 104866 -> 104784 bytes (82 bytes smaller)
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	bigmac-hm3.png 
Views:	145 
Size:	33.1 KB 
ID:	1600   Click image for larger version. 

Name:	getadrink-hm3.png 
Views:	127 
Size:	63.8 KB 
ID:	1601   Click image for larger version. 

Name:	mouse-hm3.png 
Views:	134 
Size:	102.3 KB 
ID:	1602  
    Last edited by caveman; 3rd July 2011 at 02:35.

  7. #7
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts

    Pngdb a companion app to Huffmix

    pngdb has been updated and is now called defdb, it has its own thread here.

    I needed a tool to quickly display some internals of the Deflate stream to compare files produced by Huffmix. I make it available here since it could be helpful to others.

    For each Deflate block pngdb displays:
    - its type: 0 uncompressed, 1 fixed Huffman tree, 2 dynamic Huffman tree
    - its boundary: this is the offset in the uncompressed data where a block ends and a new one starts.
    - its compressed size in bits: self-explanatory
    and a short summary: full size of the stream in bits, number of blocks

    It looks like this:
    Code:
    T Boundary     Size
    2        0     3163
    2      dcc    16476
    2     2955    18865
    2     42e2    18606
    2     5b9a    18296
    2     7427     8514
    2     817b    14479
    98399 bits long, composed of 7 blocks
    It can also be called with two options:
    -s : displays only the overall Deflate stream size in bits
    -d : dumps the Deflate stream in human readable form:
    - [size] XX, a literal value XX in hexa (ranges from 00 to FF that is 0 to 255), took size bits compressed.
    - [size] (length, distance), LZ pair in decimal, length (3 to 25 distance (1 to 3276, took size bits compressed.
    - [size] EoB, End of Block, took size bits compressed.
    Huffman trees of type 2 blocks are not dumped (I may add this feature in the future), nor are type 0 blocks.
    It looks like this:
    Code:
     [3] 00
     [9] (3,1)
     [5] 1E
     [3] 00
    [11] (7,1)
     [5] 21
    [10] (8,9)
     [4] 40
     [4] 80
     [8] (6,9)
    ...
    [12] (9,432)
    [12] (9,450)
    [12] (9,468)
    [12] (9,486)
     [6] EoB
    Attached Files Attached Files
    Last edited by caveman; 10th December 2011 at 06:03. Reason: defdb is available

  8. #8
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Version 0.4b1 released (first post updated).

  9. #9
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Version 0.4b2 released (first post updated).

    The new -k option allows you to keep the same block sequence as in the first file.

    For instance you have a file with 3 blocks and an other one with 5 blocks, without the -k switch Huffmix could have produced an output file made of 3, 4 or 5 blocks, you can now enforce to keep the same block sequence as in the first file with the -k option.

    For instance if we have 3 and 5 blocks.
    File A:
    block 1: 110 bits
    block 2: 317 bits
    block 3: 272 bits
    Overall: 699 bits

    PNGOUT -n5 option has split block 2 and 3 in two.
    File B:
    block 1: 104 bits
    block 2: 201 bits (was part of block 2 in File A)
    block 3: 114 bits (was part of block 2 in File A) blocks 2&3 315 bits
    block 4: 148 bits (was part of block 3 in File A)
    block 5: 141 bits (was part of block 3 in File A) blocks 4&5 289 bits
    Overall: 708 bits

    Huffmix without -k outputs this file:
    File C:
    block 1: 104 bits (from File B)
    block 2: 201 bits (from File B since blocks 2&3 are smaller than block 2 from File A)
    block 3: 114 bits (from File B same as above)
    block 4: 272 bits (from File A since blocks 4&5 are bigger than block 3 from File A)
    Overall: 691 bits

    Huffmix with -k outputs this file:
    File D:
    block 1: 104 bits (from File B)
    block 2: 317 bits (from File A to preserve block sequence)
    block 3: 272 bits (from File A to preserve block sequence)
    Overall: 693 bits

    Jonathon Fowler has build the new version of PNGOUT for Linux, Mac OS X and FreeBSD.

    Using this version produced different block boundaries on some files leading to smaller files:
    bigmac.png 33900 -> 33864 bytes (36 bytes smaller)
    getadrink.png 65286 -> 65225 bytes (61 bytes smaller)
    mouse.png 104784 -> 104740 bytes (40 bytes smaller)
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	bigmac-new.png 
Views:	143 
Size:	33.1 KB 
ID:	1624   Click image for larger version. 

Name:	getadrink-new.png 
Views:	152 
Size:	63.7 KB 
ID:	1625   Click image for larger version. 

Name:	mouse-new.png 
Views:	144 
Size:	102.3 KB 
ID:	1626  
    Last edited by caveman; 27th July 2011 at 11:56. Reason: Ever-shrinking mouse latest news

  10. #10
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Added Linux x86 64-bits versions of Huffmix and Pngdb.

  11. #11
    Member
    Join Date
    Oct 2012
    Location
    Dracula's country
    Posts
    19
    Thanks
    11
    Thanked 1 Time in 1 Post

  12. #12
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Quote Originally Posted by Jaff View Post
    You can download it from the first message over-here.
    A new version supporting Gzip files is on its way.

  13. #13
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Version 0.5b2 released (first post updated).

    Version 0.5b2
    - handles .gz files (gzip files created by kzip2gz)
    - internal number of Deflate blocks limit set to 600
    - a memory allocation bug correction (led to rare segfaults)

  14. #14
    Member
    Join Date
    Oct 2012
    Location
    Dracula's country
    Posts
    19
    Thanks
    11
    Thanked 1 Time in 1 Post
    Thank you for the update!

  15. #15
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Windows version 0.5b2 has been replaced by 0.5b3 (to fix some unpexpected crash)

  16. #16
    Member
    Join Date
    Apr 2011
    Location
    Russia
    Posts
    48
    Thanks
    7
    Thanked 0 Times in 0 Posts
    Good afternoon!
    Wanted to learn, whether zip support will be realized?

  17. #17
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Sorry, full zip archive support has very low priority do not expect it this year, but some minor updates are in the works.

    Version 0.5b4 was silently released (it corrected a bug submitted by Aaron Reitz).
    Last edited by caveman; 14th May 2013 at 14:21.

  18. #18
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Version 0.6b1 released (first post updated).
    - solves some "Could not find matching sub-blocks" problems
    Last edited by caveman; 14th May 2013 at 14:21.

  19. #19
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    412
    Thanks
    4
    Thanked 2 Times in 2 Posts
    would ti be possible to add multiple file support, so vi can find the best block from more files in one run would make it easier to batch.

  20. #20
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    Quote Originally Posted by SvenBent View Post
    would ti be possible to add multiple file support, so vi can find the best block from more files in one run would make it easier to batch.
    Had another similar request... I'm a bit bit busy right now but I'll try to add this feature.

  21. #21
    Member
    Join Date
    Sep 2007
    Location
    Denmark
    Posts
    412
    Thanks
    4
    Thanked 2 Times in 2 Posts
    I'm finally updating my png optimizing batch and implanting huffmix and i really love this utility.

    please tell me if im wrong in this.
    it would be possible to run multi instance of pngout /r and huffmix trials in parralel and then just huff mix the resulting files in the end
    e.g i run 4 batch files tha does 200 iterations of png /r and huffmix individually. and then the 4 resulting files i huffmix together. i would end up with the optimal files of block from all 800 pngout /r trials.

    or wold it be more efficient to run just one run of 800 trials ? i believe the compression ratio should be identical (except random is random) but am i wrong.?

    if it works huffmix makes it pretty easy to multi thread pngout /r trials this way
    Last edited by SvenBent; 22nd April 2014 at 07:28.

  22. #22
    Member caveman's Avatar
    Join Date
    Jul 2009
    Location
    Strasbourg, France
    Posts
    155
    Thanks
    6
    Thanked 29 Times in 17 Posts
    It should work, there's only one problem that could occur:
    The randomness is apparently based on time, if you fire two (or more) pngout instances exactly at the same time they may use the same random seed and produce exactly the same file. Now this has probably been mitigated by version 20120530 (and newer) of pngout, since on the Unix ports page it is stated : "Better randomness when the -r switch is used.", eventually ask Ken about it.

    Beware that palette ordering may change during a standard pngout -r run and since this produces an entirely new image huffmix will not work, you have to pick a palette first (truepng or pngout itself) and then lock it using -kp when doing the random runs.

    Don't forget to run deflopt and defluff (I run deflopt/defluff/deflopt again) right after pngout before huffmix.

    Quote Originally Posted by SvenBent View Post
    I'm finally updating my png optimizing batch and implanting huffmix and i really love this utility.

    please tell me if im wrong in this.
    it would be possible to run multi instance of pngout /r and huffmix trials in parralel and then just huff mix the resulting files in the end
    e.g i run 4 batch files tha does 200 iterations of png /r and huffmix individually. and then the 4 resulting files i huffmix together. i would end up with the optimal files of block from all 800 pngout /r trials.

    or wold it be more efficient to run just one run of 800 trials ? i believe the compression ratio should be identical (except random is random) but am i wrong.?

    if it works huffmix makes it pretty easy to multi thread pngout /r trials this way

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
  •