Optimize Huffman code generation
authorEric Biggers <ebiggers3@gmail.com>
Thu, 29 May 2014 05:42:54 +0000 (00:42 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Sat, 31 May 2014 14:52:53 +0000 (09:52 -0500)
commit394751ae13025edab605cd61c8e32819e3fb33a1
tree6d3dce24c3d32e288e9fd4876e023b9914b2d820
parentcf7090dcba4736f4ea56f272b5e0152a8a0a70b5
Optimize Huffman code generation

This commit significantly improves the performance of length-limited
canonical Huffman code generation by introducing several optimizations
based on the 7-Zip implementation.

Altlhough Huffman code generation is not the main bottleneck of any of
the compression algorithms implemented here, an optimized implementation
can still improve overall performance by several percent.  In addition,
it significantly speeds up LZMS decompression, which requires frequent
rebuilding of adaptive Huffman codes.

Some peformance comparisons:

    - The average time taken to generate all three LZX codes (main,
      length, and aligned offset) when compressing a Windows PE
      filesystem with LZX decreased from 73.9 us to 17.3 us.

    - The time taken to compress a Windows PE filesystem with LZX, using
      the "fast" LZX algorithm (hash chain match finder and lazy
      parsing), decreased from 12.3 s to 11.6 s (a 5.7% improvement).

    - The time taken to decompress a Windows PE filesystem with LZMS,
      using solid blocks, decreased from 12.3 s to 9.0 s (a 27%
      improvement).
include/wimlib/compress_common.h
src/compress_common.c
src/lzms-compress.c
src/lzms-decompress.c
src/lzx-compress.c
src/xpress-compress.c