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

Thread: LZ5 - a modification of LZ4 which gives a better ratio at cost of slower compression

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts

    LZ5 - a modification of LZ4 which gives a better ratio at cost of slower compression

    LZ5 is a modification of LZ4 which gives a better ratio at cost of slower compression and decompression speed.
    This is caused mainly because of 22-bit dictionary instead of 16-bit in LZ4.

    LZ5 uses different output codewords and is not compatible with LZ4. LZ4 output codewords are 3 byte long (24-bit) and look as follows:
    - LLLL_MMMM OOOOOOOO OOOOOOOO - 16-bit offset, 4-bit match length, 4-bit literal length

    LZ5 uses 3 types of codewords from 2 to 4 bytes long:
    - 1_OO_LL_MMM OOOOOOOO - 10-bit offset, 3-bit match length, 2-bit literal length
    - 00_LLL_MMM OOOOOOOO OOOOOOOO - 16-bit offset, 3-bit match length, 3-bit literal length
    - 01_LLL_MMM OOOOOOOO OOOOOOOO OOOOOOOO - 24-bit offset, 3-bit match length, 3-bit literal length

    In my experiments decompression speed of LZ5 is from 650-950 MB/s. It's slower than LZ4 but much faster than zstd and brotli.
    With the compresion ratio is opposite: LZ5 is better than LZ4 but worse than zstd and brotli.

    Code:
    | Compressor name             | Compression| Decompress.| Compr. size | Ratio |
    | ---------------             | -----------| -----------| ----------- | ----- |
    | memcpy                      |  8533 MB/s |  8533 MB/s |   104857600 |100.00 |
    | lz4 r131                    |   480 MB/s |  2275 MB/s |    64872315 | 61.87 |
    | lz4hc r131 -1               |    82 MB/s |  1896 MB/s |    59448496 | 56.69 |
    | lz4hc r131 -3               |    54 MB/s |  1932 MB/s |    56343753 | 53.73 |
    | lz4hc r131 -5               |    41 MB/s |  1969 MB/s |    55271312 | 52.71 |
    | lz4hc r131 -7               |    31 MB/s |  1969 MB/s |    54889301 | 52.35 |
    | lz4hc r131 -9               |    24 MB/s |  1969 MB/s |    54773517 | 52.24 |
    | lz4hc r131 -11              |    20 MB/s |  1969 MB/s |    54751363 | 52.21 |
    | lz4hc r131 -13              |    17 MB/s |  1969 MB/s |    54744790 | 52.21 |
    | lz4hc r131 -15              |    14 MB/s |  2007 MB/s |    54741827 | 52.21 |
    | lz5 r131                    |   195 MB/s |   939 MB/s |    55884927 | 53.30 |
    | lz5hc r131 -1               |    32 MB/s |   742 MB/s |    52927122 | 50.48 |
    | lz5hc r131 -3               |    20 MB/s |   716 MB/s |    50970192 | 48.61 |
    | lz5hc r131 -5               |    10 MB/s |   701 MB/s |    49970285 | 47.66 |
    | lz5hc r131 -7               |  5.54 MB/s |   682 MB/s |    49541511 | 47.25 |
    | lz5hc r131 -9               |  2.69 MB/s |   673 MB/s |    49346894 | 47.06 |
    | lz5hc r131 -11              |  1.36 MB/s |   664 MB/s |    49266526 | 46.98 |
    | zstd v0.3                   |   257 MB/s |   547 MB/s |    51231016 | 48.86 |
    | zstd_HC v0.3 -1             |   257 MB/s |   553 MB/s |    51231016 | 48.86 |
    | zstd_HC v0.3 -3             |    76 MB/s |   417 MB/s |    46774383 | 44.61 |
    | zstd_HC v0.3 -5             |    40 MB/s |   476 MB/s |    45628362 | 43.51 |
    | zstd_HC v0.3 -9             |    14 MB/s |   485 MB/s |    44840562 | 42.76 |
    | zstd_HC v0.3 -13            |  9.34 MB/s |   469 MB/s |    43114895 | 41.12 |
    | zstd_HC v0.3 -17            |  6.02 MB/s |   463 MB/s |    42989971 | 41.00 |
    | zstd_HC v0.3 -21            |  3.35 MB/s |   461 MB/s |    42956964 | 40.97 |
    | zstd_HC v0.3 -23            |  2.33 MB/s |   463 MB/s |    42934217 | 40.95 |
    | brotli 2015-10-29 -1        |    86 MB/s |   208 MB/s |    47882059 | 45.66 |
    | brotli 2015-10-29 -3        |    60 MB/s |   214 MB/s |    47451223 | 45.25 |
    | brotli 2015-10-29 -5        |    17 MB/s |   217 MB/s |    43363897 | 41.36 |
    | brotli 2015-10-29 -7        |  4.80 MB/s |   227 MB/s |    41222719 | 39.31 |
    | brotli 2015-10-29 -9        |  2.23 MB/s |   222 MB/s |    40839209 | 38.95 |
    The above results are obtained with https://github.com/inikep/lzbench using 1 core of Intel Core i5-4300U, Windows 10 64-bit (MinGW-w64 compilation under gcc 4.8.3) with 3 iterations.
    The "win81" input file (100 MB) is a concatanation of carefully selected files from installed version of Windows 8.1 64-bit.

  2. Thanks (7):

    Bulat Ziganshin (1st November 2015),Cyan (1st November 2015),encode (1st March 2016),Jarek (3rd November 2015),Jyrki Alakuijala (2nd November 2015),Stephan Busch (7th November 2015),yh.deng (26th May 2018)

  3. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    780
    Thanked 687 Times in 372 Posts
    sharing your sources, executables and testfile would be great

  4. #3
    Member jibz's Avatar
    Join Date
    Jan 2015
    Location
    Denmark
    Posts
    124
    Thanks
    106
    Thanked 71 Times in 51 Posts
    It looks like the source is available at the github repo he linked to. And the test file win81 he linked to in some of his other posts here and here.

  5. Thanks:

    Bulat Ziganshin (1st November 2015)

  6. #4
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Experimental version of LZ5 is here https://github.com/inikep/lz5

  7. #5
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    LZ5 v1.3.3 beta can be downloaded at:
    https://github.com/inikep/lz5/archive/dev.zip

    Changes:
    - added: new levels from 11 to 16 (maximum compression ratio)
    - added: a new parser: LZ5HC_optimal_price
    - fixed: buffer-overflow during decompression (thanks to m^2)

    Please help me with fuzzing. Here is a quick comparison:

    Code:
    Compressor name              Compression Decompress. Compr. size  Ratio
    crush 1.0 level 0               14 MB/s    195 MB/s     50419812  48.08 
    crush 1.0 level 1             4.09 MB/s    211 MB/s     48195021  45.96
    crush 1.0 level 2             0.55 MB/s    214 MB/s     47105187  44.92
    lz5hc r132 level 10             12 MB/s    670 MB/s     48109030  45.88
    lz5hc r132 level 11           6.60 MB/s    592 MB/s     47639520  45.43
    lz5hc r132 level 12           3.22 MB/s    670 MB/s     47461368  45.26
    lz5hc r132 level 13           1.09 MB/s    642 MB/s     47382059  45.19
    lz5hc v1.3.3 level 10           12 MB/s    677 MB/s     48109030  45.88
    lz5hc v1.3.3 level 11         8.76 MB/s    692 MB/s     47438817  45.24
    lz5hc v1.3.3 level 12         7.02 MB/s    651 MB/s     47063261  44.88
    lz5hc v1.3.3 level 13         4.75 MB/s    645 MB/s     46718698  44.55
    lz5hc v1.3.3 level 14         3.84 MB/s    671 MB/s     46484969  44.33
    lz5hc v1.3.3 level 15         1.93 MB/s    712 MB/s     46227364  44.09
    lz5hc v1.3.3 level 16         0.80 MB/s    709 MB/s     46125742  43.99
    Last edited by inikep; 18th December 2015 at 20:06.

  8. Thanks:

    m^2 (19th December 2015)

  9. #6
    Member
    Join Date
    Nov 2015
    Location
    boot ROM
    Posts
    95
    Thanks
    27
    Thanked 17 Times in 15 Posts
    Quote Originally Posted by inikep View Post
    ...
    Code:
    Compressor name              Compression Decompress. Compr. size  Ratio
    ...
    crush 1.0 level 2             0.55 MB/s    214 MB/s     47105187  44.92
    ...
    lz5hc v1.3.3 level 16         0.80 MB/s    709 MB/s     46125742  43.99
    Whoa, now it can beat Crush? Being 3x+ faster on decompression? Sounds interesting, let's see how it performs on my data :P.

  10. #7
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,610
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Nice. Could you add pithy results?

  11. #8
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts

  12. #9
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,610
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Missed that, thanks.

  13. #10
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    876
    Thanks
    474
    Thanked 175 Times in 85 Posts
    can anyone please provide Windows compiles of LZbench and LZ5?

  14. #11
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts

  15. #12
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    A new beta version of LZ5 r132 is available at https://github.com/inikep/lz5/releases

    It has plenty of changes and improvements therefore it needs more testing (please help me with fuzzing).

    One can see that in comparision to r131 it gives:
    1) much better ratio at the same compression speed
    or 2) much better compression speed at the same ratio

    In my experiments there is no open-source bytewise compressor that gives better ratio than lz5hc level 12 (only lzturbo 29 has better ratio but it's closed-source and much slower):

    Code:
    | lz5 r132                    |   180 MB/s |   877 MB/s |    56183327 | 53.58 |
    | lz5hc r132 level 1          |   453 MB/s |  1649 MB/s |    68770655 | 65.58 |
    | lz5hc r132 level 2          |   341 MB/s |  1533 MB/s |    65201626 | 62.18 |
    | lz5hc r132 level 3          |   222 MB/s |  1267 MB/s |    61423270 | 58.58 |
    | lz5hc r132 level 4          |   122 MB/s |   892 MB/s |    55011906 | 52.46 |
    | lz5hc r132 level 5          |    92 MB/s |   784 MB/s |    52790905 | 50.35 |
    | lz5hc r132 level 6          |    40 MB/s |   872 MB/s |    52561673 | 50.13 |
    | lz5hc r132 level 7          |    30 MB/s |   825 MB/s |    50947061 | 48.59 |
    | lz5hc r132 level 8          |    21 MB/s |   771 MB/s |    50049555 | 47.73 |
    | lz5hc r132 level 9          |    16 MB/s |   702 MB/s |    48718531 | 46.46 |
    | lz5hc r132 level 10         |    12 MB/s |   670 MB/s |    48109030 | 45.88 |
    | lz5hc r132 level 11         |  6.60 MB/s |   592 MB/s |    47639520 | 45.43 |
    | lz5hc r132 level 12         |  3.22 MB/s |   670 MB/s |    47461368 | 45.26 |
    | lz5 r131                    |   195 MB/s |   939 MB/s |    55884927 | 53.30 |
    | lz5hc r131 -1               |    32 MB/s |   742 MB/s |    52927122 | 50.48 |
    | lz5hc r131 -3               |    20 MB/s |   716 MB/s |    50970192 | 48.61 |
    | lz5hc r131 -5               |    10 MB/s |   701 MB/s |    49970285 | 47.66 |
    | lz5hc r131 -7               |  5.54 MB/s |   682 MB/s |    49541511 | 47.25 |
    | lz5hc r131 -9               |  2.69 MB/s |   673 MB/s |    49346894 | 47.06 |
    | lz5hc r131 -11              |  1.36 MB/s |   664 MB/s |    49266526 | 46.98 |
    | zstd_HC v0.3.6 level 1      |   250 MB/s |   529 MB/s |    51230550 | 48.86 |
    | zstd_HC v0.3.6 level 2      |   186 MB/s |   498 MB/s |    49678572 | 47.38 |
    | zstd_HC v0.3.6 level 3      |    90 MB/s |   484 MB/s |    48838293 | 46.58 |
    | zstd_HC v0.3.6 level 5      |    61 MB/s |   467 MB/s |    46480999 | 44.33 |
    | zstd_HC v0.3.6 level 7      |    28 MB/s |   480 MB/s |    44803941 | 42.73 |
    | zstd_HC v0.3.6 level 9      |    15 MB/s |   497 MB/s |    43899996 | 41.87 |
    | zstd_HC v0.3.6 level 12     |    11 MB/s |   505 MB/s |    42402232 | 40.44 |
    | zstd_HC v0.3.6 level 16     |  2.29 MB/s |   499 MB/s |    42122327 | 40.17 |
    | zstd_HC v0.3.6 level 20     |  1.65 MB/s |   454 MB/s |    41884658 | 39.94 |
    The above results are obtained with https://github.com/inikep/lzbench using 1 core of Intel Core i5-4300U, Windows 10 64-bit (MinGW-w64 compilation under gcc 4.8.3) with 3 iterations.
    The "win81" input file (100 MB) is a concatanation of carefully selected files from installed version of Windows 8.1 64-bit.
    Last edited by inikep; 30th November 2015 at 14:45.

  16. Thanks (2):

    Cyan (30th November 2015),m^3 (30th November 2015)

  17. #13
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Quote Originally Posted by inikep View Post
    A new beta version of LZ5 r132 is available at https://github.com/inikep/lz5/releases

    It has plenty of changes and improvements therefore it needs more testing (please help me with fuzzing).
    Hear you.

  18. #14
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Quote Originally Posted by inikep View Post
    In my experiments there is no open-source bytewise compressor that gives better ratio than lz5hc level 12 (only lzturbo 29 has better ratio but it's closed-source and much slower):
    How about encode's crush and lzss? Don't remember much about the former, but the latter had a large dictionary and optimal parsing (though inoptimal MF), should be very strong on large files.

  19. #15
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Quote Originally Posted by m^3 View Post
    That's with master. With dev the errors are still there, but slightly changed:
    Master is r131 therefore I gave this link with source code I wanted to fuzz:
    https://github.com/inikep/lz5/releases/tag/r132-beta


    Quote Originally Posted by m^3 View Post
    How about encode's crush and lzss? Don't remember much about the former, but the latter had a large dictionary and optimal parsing (though inoptimal MF), should be very strong on large files.

    LZSS is not good:

    30.11.2015 14:59 58˙764˙396 win81.lzss
    30.11.2015 15:08 53˙385˙675 win81.lzssx

    Crush is bitwise not bytewise. But it will be beaten in the next version

    Code:
    | crush 1.0 level 0           |    14 MB/s |   195 MB/s |    50419812 | 48.08 |
    | crush 1.0 level 1           |  4.09 MB/s |   211 MB/s |    48195021 | 45.96 |
    | crush 1.0 level 2           |  0.55 MB/s |   214 MB/s |    47105187 | 44.92 |
    | lz5hc r132 level 10         |    12 MB/s |   670 MB/s |    48109030 | 45.88 |
    | lz5hc r132 level 12         |  3.22 MB/s |   670 MB/s |    47461368 | 45.26 |
    Last edited by inikep; 30th November 2015 at 16:16.

  20. #16
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    --help shows the highest level to be 9. And it shows stdin/out compression which doesn't work.
    Also:
    Code:
    katmacadapc% ./lz5 -12 .gitignore  
    Compressed filename will be : .gitignore.lz5 
    Compressed 275 bytes into 266 bytes ==> 96.73%                                 
    
    =================================================================
    ==28952==ERROR: LeakSanitizer: detected memory leaks
    
    Direct leak of 16777216 byte(s) in 1 object(s) allocated from:
        #0 0x4b8aa2  (/home/madamczyk/afl-1.94b/lz5/lz5+0x4b8aa2)
        #1 0x529899  (/home/madamczyk/afl-1.94b/lz5/lz5+0x529899)
        #2 0x52d594  (/home/madamczyk/afl-1.94b/lz5/lz5+0x52d594)
        #3 0x542466  (/home/madamczyk/afl-1.94b/lz5/lz5+0x542466)
        #4 0x54178d  (/home/madamczyk/afl-1.94b/lz5/lz5+0x54178d)
        #5 0x54b7f3  (/home/madamczyk/afl-1.94b/lz5/lz5+0x54b7f3)
        #6 0x7fe3d817beac  (/lib/x86_64-linux-gnu/libc.so.6+0x1eeac)
    
    Direct leak of 8388608 byte(s) in 1 object(s) allocated from:
        #0 0x4b8aa2  (/home/madamczyk/afl-1.94b/lz5/lz5+0x4b8aa2)
        #1 0x529847  (/home/madamczyk/afl-1.94b/lz5/lz5+0x529847)
        #2 0x52d594  (/home/madamczyk/afl-1.94b/lz5/lz5+0x52d594)
        #3 0x542466  (/home/madamczyk/afl-1.94b/lz5/lz5+0x542466)
        #4 0x54178d  (/home/madamczyk/afl-1.94b/lz5/lz5+0x54178d)
        #5 0x54b7f3  (/home/madamczyk/afl-1.94b/lz5/lz5+0x54b7f3)
        #6 0x7fe3d817beac  (/lib/x86_64-linux-gnu/libc.so.6+0x1eeac)
    
    SUMMARY: AddressSanitizer: 25165824 byte(s) leaked in 2 allocation(s)

    ADDED: That's with master. With dev the errors are still there, but slightly changed:

    Code:
    katmacadapc% ./lz5 -12 .gitignore 1
    Compressed 305 bytes into 287 bytes ==> 94.10%                                 
    
    =================================================================
    ==14599==ERROR: LeakSanitizer: detected memory leaks
    
    Direct leak of 33816576 byte(s) in 1 object(s) allocated from:
        #0 0x4b8a82  (/home/madamczyk/afl-1.94b/lz5/lz5+0x4b8a82)
        #1 0x526060  (/home/madamczyk/afl-1.94b/lz5/lz5+0x526060)
    
    Direct leak of 16777216 byte(s) in 1 object(s) allocated from:
        #0 0x4b8a82  (/home/madamczyk/afl-1.94b/lz5/lz5+0x4b8a82)
        #1 0x52618e  (/home/madamczyk/afl-1.94b/lz5/lz5+0x52618e)
    
    SUMMARY: AddressSanitizer: 50593792 byte(s) leaked in 2 allocation(s).
    Last edited by m^3; 30th November 2015 at 15:36.

  21. #17
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Quote Originally Posted by m^3 View Post
    --help shows the highest level to be 9
    Now (in "dev" branch) levels 0-13 are described and available from lz5.exe
    Code:
    | lz5hc r132 level 12         |  3.22 MB/s |   670 MB/s |    47461368 | 45.26 |
    | lz5hc r132 level 13         |  1.09 MB/s |   642 MB/s |    47382059 | 45.19 |
    Quote Originally Posted by m^3 View Post
    SUMMARY: AddressSanitizer: 50593792 byte(s) leaked in 2 allocation(s).
    DrMemory on Windows and Valgrind on Ubuntu show "no leaks possible".
    Last edited by inikep; 30th November 2015 at 18:17.

  22. #18
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    LZ5 v1.3.3 (final) can be downloaded at:
    https://github.com/inikep/lz5/releases

    Changes from r132:
    - added: new levels from 11 to 18 (maximum compression ratio)
    - added: a new parser: LZ5HC_optimal_price
    - fixed: buffer-overflow during decompression (thanks to m^2)

    Here is a quick comparison:
    Code:
    Compressor name              Compression Decompress. Compr. size  Ratio
    crush 1.0 level 0               14 MB/s    195 MB/s     50419812  48.08
    crush 1.0 level 1             4.09 MB/s    211 MB/s     48195021  45.96
    crush 1.0 level 2             0.55 MB/s    214 MB/s     47105187  44.92
    lz5hc r132 level 10             12 MB/s    670 MB/s     48109030  45.88
    lz5hc r132 level 11           6.60 MB/s    592 MB/s     47639520  45.43
    lz5hc r132 level 12           3.22 MB/s    670 MB/s     47461368  45.26
    lz5hc r132 level 13           1.09 MB/s    642 MB/s     47382059  45.19
    lz5hc v1.3.3 level 10           12 MB/s    677 MB/s     48109030  45.88
    lz5hc v1.3.3 level 11         8.76 MB/s    692 MB/s     47438817  45.24
    lz5hc v1.3.3 level 12         7.02 MB/s    651 MB/s     47063261  44.88
    lz5hc v1.3.3 level 13         4.75 MB/s    645 MB/s     46718698  44.55
    lz5hc v1.3.3 level 14         3.84 MB/s    671 MB/s     46484969  44.33
    lz5hc v1.3.3 level 15         1.93 MB/s    712 MB/s     46227364  44.09
    lz5hc v1.3.3 level 16         0.80 MB/s    709 MB/s     46125742  43.99
    lz5hc v1.3.3 level 17         0.39 MB/s    679 MB/s     46050114  43.92
    lz5hc v1.3.3 level 18         0.16 MB/s    541 MB/s     46008853  43.88

  23. Thanks (3):

    comp1 (5th January 2016),Stephan Busch (8th January 2016),xcrh (8th January 2016)

  24. #19
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    803
    Thanks
    244
    Thanked 255 Times in 159 Posts
    Hi,
    Have you maybe thought about adding an entropy coder? - it would be nice to reach (exceed?) compression level of lzturbo -39.

    In this case the length choices have smaller meaning - the data should be divided into a few streams of similar probability distribution and 8-10bit alphabet size to fit L1 cache (e.g. 2048 state tANS/FSE) - the more the better use of correlations.
    For example for 24 bits:
    3bits match_length + 3bits literal_length + 2 youngest bits of offset as one alphabet for EC - such combination allows EC to use correlation between them
    the next 8 bits of offset as second alphabet for EC
    the last 8 bits of offset as third alphabet for EC (mostly zeros)
    literals as fourth alphabet for EC (Huffman?)

    Or probably better:
    3+3+4 first EC
    10 of offset second EC
    literals 3rd

    Does ZSTD encode both bytes of offset with the same probability distribution? They should have very different distributions.

    What is real life distribution of match_length? 3bits seem small?
    Last edited by Jarek; 30th November 2015 at 22:33.

  25. #20
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    LZ5 r132 uses 4 types of codewords from 1 to 4 bytes long:
    [1_OO_LL_MMM] [OOOOOOOO] - 10-bit offset, 3-bit match length, 2-bit literal length
    [00_LLL_MMM] [OOOOOOOO] [OOOOOOOO] - 16-bit offset, 3-bit match length, 3-bit literal length
    [010_LL_MMM] [OOOOOOOO] [OOOOOOOO] [OOOOOOOO] - 24-bit offset, 3-bit match length, 2-bit literal length
    [011_LL_MMM] - last offset, 3-bit match length, 2-bit literal length

    1, 00, 010, 011 can be seen as Huffman codes and are selected according to frequences of given codewords for my test files. Match lengths have always 3-bits (MMM) and literal lengths are usually 2-bits (LL) because it gives better ratio than any other division of 5-bits remaining bits. So we can encode values 0-7 (3-bits) for matches (what means length of 3-10 for MINMATCH=3). But 7 is reserved as a flag signaling that a match is equal or longer that 10 bytes. So e.g. 30 is encoded as a flag 7 (match length=10) and a next byte 30-10=20. I tried many different variants (e.g. separate match lenghts and literal lenghts) but these codewords were the best. There is not a lot left to improve for bytewise encoding. The main improvement I see will be optimal parsing (I'm working on it). Using an entropy coder we will get completly different compressor, very similar to zstd or lzturbo -3x. Maybe the next project after LZ5

  26. Thanks:

    Matt Mahoney (4th December 2015)

  27. #21
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Code:
    katmacadapc% valgrind --leak-check=full ./lz5 -12 .gitignore 
    ==15922== Memcheck, a memory error detector
    ==15922== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
    ==15922== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
    ==15922== Command: ./lz5 -12 .gitignore
    ==15922== 
    Compressed filename will be : .gitignore.lz5 
    Compressed 305 bytes into 287 bytes ==> 94.10%                                 
    ==15922== 
    ==15922== HEAP SUMMARY:
    ==15922==     in use at exit: 50,593,792 bytes in 2 blocks
    ==15922==   total heap usage: 10 allocs, 8 frees, 59,246,766 bytes allocated
    ==15922== 
    ==15922== 16,777,216 bytes in 1 blocks are definitely lost in loss record 1 of 2
    ==15922==    at 0x4C272B8: calloc (vg_replace_malloc.c:566)
    ==15922==    by 0x41066F: LZ5_createStreamHC (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x411D24: LZ5F_compressBegin (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x412960: LZ5F_compressFrame (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x417A33: LZ5IO_compressFilename_extRess.isra.2 (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x41868F: LZ5IO_compressFilename (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x4195E5: main (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922== 
    ==15922== 33,816,576 bytes in 1 blocks are possibly lost in loss record 2 of 2
    ==15922==    at 0x4C272B8: calloc (vg_replace_malloc.c:566)
    ==15922==    by 0x410640: LZ5_createStreamHC (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x411D24: LZ5F_compressBegin (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x412960: LZ5F_compressFrame (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x417A33: LZ5IO_compressFilename_extRess.isra.2 (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x41868F: LZ5IO_compressFilename (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922==    by 0x4195E5: main (in /home/madamczyk/afl-1.94b/lz5/lz5)
    ==15922== 
    ==15922== LEAK SUMMARY:
    ==15922==    definitely lost: 16,777,216 bytes in 1 blocks
    ==15922==    indirectly lost: 0 bytes in 0 blocks
    ==15922==      possibly lost: 33,816,576 bytes in 1 blocks
    ==15922==    still reachable: 0 bytes in 0 blocks
    ==15922==         suppressed: 0 bytes in 0 blocks
    ==15922== 
    ==15922== For counts of detected and suppressed errors, rerun with: -v
    ==15922== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 4 from 4)

  28. #22
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Thanks m^3, finally I found it (it concerns only lz5hc) and it's fixed in the "dev" branch.

  29. #23
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Feature request:
    Add a command line switch that, when used during compression, checks that the output decompresses correctly and crashes with failed assertion [or in any other way, as long as it is a real crash and not just printf(...); exit(1);]

    Also, I noticed that in your API you have deprecated functions. I suggest that you either remove them or remove the depreciation mark.

  30. #24
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,572
    Thanks
    780
    Thanked 687 Times in 372 Posts
    it will be great to synchronize these API changes with lz4/zstd
    Last edited by Bulat Ziganshin; 3rd December 2015 at 19:32.

  31. #25
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,610
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Got a buffer overflow in decompression:
    Code:
    katmacadapc% ../../../lz5 -d -f id:000000,sig:06,src:000104,op:flip1,pos:1276 /tmp/1
    =================================================================
    ==24729==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x631000024800 at pc 0x000000505ce9 bp 0x7fffae4a8a60 sp 0x7fffae4a8a58
    WRITE of size 8 at 0x631000024800 thread T0
        #0 0x505ce8  (/home/madamczyk/afl-1.94b/lz5/lz5+0x505ce8)
        #1 0x54d683  (/home/madamczyk/afl-1.94b/lz5/lz5+0x54d683)
        #2 0x549836  (/home/madamczyk/afl-1.94b/lz5/lz5+0x549836)
        #3 0x55bc2f  (/home/madamczyk/afl-1.94b/lz5/lz5+0x55bc2f)
        #4 0x55a402  (/home/madamczyk/afl-1.94b/lz5/lz5+0x55a402)
        #5 0x559b2a  (/home/madamczyk/afl-1.94b/lz5/lz5+0x559b2a)
        #6 0x560d27  (/home/madamczyk/afl-1.94b/lz5/lz5+0x560d27)
        #7 0x7f59654d8eac  (/lib/x86_64-linux-gnu/libc.so.6+0x1eeac)
        #8 0x41b6a8  (/home/madamczyk/afl-1.94b/lz5/lz5+0x41b6a8)
    
    0x631000024800 is located 0 bytes to the right of 65536-byte region [0x631000014800,0x631000024800)
    allocated by thread T0 here:
        #0 0x4b8910  (/home/madamczyk/afl-1.94b/lz5/lz5+0x4b8910)
        #1 0x559e8e  (/home/madamczyk/afl-1.94b/lz5/lz5+0x559e8e)
        #2 0x559afd  (/home/madamczyk/afl-1.94b/lz5/lz5+0x559afd)
        #3 0x560d27  (/home/madamczyk/afl-1.94b/lz5/lz5+0x560d27)
        #4 0x7f59654d8eac  (/lib/x86_64-linux-gnu/libc.so.6+0x1eeac)
    
    SUMMARY: AddressSanitizer: heap-buffer-overflow (/home/madamczyk/afl-1.94b/lz5/lz5+0x505ce8) 
    Shadow bytes around the buggy address:
      0x0c627fffc8b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c627fffc8c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c627fffc8d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c627fffc8e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
      0x0c627fffc8f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
    =>0x0c627fffc900:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c627fffc910: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c627fffc920: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c627fffc930: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c627fffc940: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
      0x0c627fffc950: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
    Shadow byte legend (one shadow byte represents 8 application bytes):
      Addressable:           00
      Partially addressable: 01 02 03 04 05 06 07 
      Heap left redzone:       fa
      Heap right redzone:      fb
      Freed heap region:       fd
      Stack left redzone:      f1
      Stack mid redzone:       f2
      Stack right redzone:     f3
      Stack partial redzone:   f4
      Stack after return:      f5
      Stack use after scope:   f8
      Global redzone:          f9
      Global init order:       f6
      Poisoned by user:        f7
      Container overflow:      fc
      Array cookie:            ac
      Intra object redzone:    bb
      ASan internal:           fe
      Left alloca redzone:     ca
      Right alloca redzone:    cb
    ==24729==ABORTING
    Attached Files Attached Files

  32. #26
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Good work m^2. The bug is fixed in "dev". Thanks.

  33. #27
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    LZ5 v1.4 beta can be downloaded at:
    https://github.com/inikep/lz5/archive/dev.zip

    Changes:
    - improved: levels from 13 to 15 (maximum compression ratio)
    - added: a new parser: LZ5HC_optimal_price_bt

    Please help me with fuzzing. Here is a quick comparison:

    Code:
    Compressor name              Compression Decompress. Compr. size  Ratio
    crush 1.0 level 0               14 MB/s    195 MB/s     50419812  48.08 
    crush 1.0 level 1             4.09 MB/s    211 MB/s     48195021  45.96
    crush 1.0 level 2             0.55 MB/s    214 MB/s     47105187  44.92
    lz5hc v1.3.3 level 13         4.75 MB/s    645 MB/s     46718698  44.55
    lz5hc v1.3.3 level 14         3.84 MB/s    671 MB/s     46484969  44.33
    lz5hc v1.3.3 level 15         1.93 MB/s    712 MB/s     46227364  44.09
    lz5hc v1.3.3 level 16         0.80 MB/s    709 MB/s     46125742  43.99
    lz5hc v1.4 level 13           5.38 MB/s    710 MB/s     46383307  44.23
    lz5hc v1.4 level 14           4.12 MB/s    669 MB/s     45843096  43.72
    lz5hc v1.4 level 15           2.16 MB/s    619 MB/s     45767126  43.65

  34. Thanks:

    Cyan (26th January 2016)

  35. #28
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Quote Originally Posted by inikep View Post
    LZ5 v1.4 beta can be downloaded at:
    https://github.com/inikep/lz5/archive/dev.zip

    Changes:
    - improved: levels from 13 to 15 (maximum compression ratio)
    - added: a new parser: LZ5HC_optimal_price_bt

    Please help me with fuzzing. Here is a quick comparison:

    Code:
    Compressor name              Compression Decompress. Compr. size  Ratio
    crush 1.0 level 0               14 MB/s    195 MB/s     50419812  48.08 
    crush 1.0 level 1             4.09 MB/s    211 MB/s     48195021  45.96
    crush 1.0 level 2             0.55 MB/s    214 MB/s     47105187  44.92
    lz5hc v1.3.3 level 13         4.75 MB/s    645 MB/s     46718698  44.55
    lz5hc v1.3.3 level 14         3.84 MB/s    671 MB/s     46484969  44.33
    lz5hc v1.3.3 level 15         1.93 MB/s    712 MB/s     46227364  44.09
    lz5hc v1.3.3 level 16         0.80 MB/s    709 MB/s     46125742  43.99
    lz5hc v1.4 level 13           5.38 MB/s    710 MB/s     46383307  44.23
    lz5hc v1.4 level 14           4.12 MB/s    669 MB/s     45843096  43.72
    lz5hc v1.4 level 15           2.16 MB/s    619 MB/s     45767126  43.65
    Slowness makes the higher levels pretty much unsuitable for fuzzing, but I do some basic tests.

  36. #29
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    Quote Originally Posted by m^3 View Post
    Slowness makes the higher levels pretty much unsuitable for fuzzing, but I do some basic tests.
    I run out of ideas to improve LZ5 so it can be the last version of LZ5.

    Please focus mainly on level 13 (the fastest level with LZ5HC_optimal_price_bt). For fuzzing you can make it faster changing lz5common.h:
    Code:
        /* windLog, contentLog,  H, H3,  Snum, SL, SuffL, FS, Strategy */
        { MAXD_LOG, MAXD_LOG+1, 23, 16,     8,  4,    64,  1, LZ5HC_optimal_price_bt }, // level 13
        { MAXD_LOG, MAXD_LOG+1, 23, 16,     2,  4,    16,  1, LZ5HC_optimal_price_bt }, // level 13 for fuzzing

  37. #30
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    Quote Originally Posted by inikep View Post
    I run out of ideas to improve LZ5 so it can be the last version of LZ5.

    Please focus mainly on level 13 (the fastest level with LZ5HC_optimal_price_bt). For fuzzing you can make it faster changing lz5common.h:
    Code:
        /* windLog, contentLog,  H, H3,  Snum, SL, SuffL, FS, Strategy */
        { MAXD_LOG, MAXD_LOG+1, 23, 16,     8,  4,    64,  1, LZ5HC_optimal_price_bt }, // level 13
        { MAXD_LOG, MAXD_LOG+1, 23, 16,     2,  4,    16,  1, LZ5HC_optimal_price_bt }, // level 13 for fuzzing
    That's better.

Page 1 of 2 12 LastLast

Similar Threads

  1. Replies: 45
    Last Post: 25th November 2016, 03:30
  2. VMware tar modification
    By nimdamsk in forum Data Compression
    Replies: 5
    Last Post: 7th November 2011, 12:24
  3. decompression is ~1000 times slower than compression?
    By Alexander Rhatushnyak in forum Data Compression
    Replies: 17
    Last Post: 28th April 2010, 13:27
  4. paq9a modification
    By kaitz in forum Data Compression
    Replies: 7
    Last Post: 28th September 2008, 04:46
  5. Compiler related: Intel's code slower on AMD-CPUs?!
    By Vacon in forum Data Compression
    Replies: 5
    Last Post: 10th May 2008, 17:56

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
  •