Page 1 of 3 123 LastLast
Results 1 to 30 of 70

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

  1. #1
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 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. The Following 7 Users Say Thank You to inikep For This Useful Post:

    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,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    sharing your sources, executables and testfile would be great

  4. #3
    Member jibz's Avatar
    Join Date
    Jan 2015
    Location
    Denmark
    Posts
    114
    Thanks
    91
    Thanked 69 Times in 49 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. The Following User Says Thank You to jibz For This Useful Post:

    Bulat Ziganshin (1st November 2015)

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

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

  8. #6
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 Posts

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

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

  11. #9
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 Posts

  12. #10
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 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 15:45.

  13. The Following 2 Users Say Thank You to inikep For This Useful Post:

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

  14. #11
    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.

  15. #12
    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.

  16. #13
    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 16:36.

  17. #14
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 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 17:16.

  18. #15
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 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 19:17.

  19. #16
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 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 23:33.

  20. #17
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 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

  21. The Following User Says Thank You to inikep For This Useful Post:

    Matt Mahoney (4th December 2015)

  22. #18
    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)

  23. #19
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 Posts
    Thanks m^3, finally I found it (it concerns only lz5hc) and it's fixed in the "dev" branch.

  24. #20
    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.

  25. #21
    Member
    Join Date
    Jul 2013
    Location
    United States
    Posts
    194
    Thanks
    44
    Thanked 140 Times in 69 Posts
    Quote Originally Posted by m^3 View Post
    Also, I noticed that in your API you have deprecated functions. I suggest that you either remove them or remove the depreciation mark.
    As long as you're breaking API, I suggest:

    * Change parameters and return values to use size_t (or ssize_t if you want to use negative values for return codes) instead of ints.
    * Use uint8_t arrays instead of char arrays for data. Even MSVC supports stdint.h now, and people using older compilers have easy access to compatibility headers.
    * Use conformant array parameters. I usually hide this behind a macro which is defined to nothing for < C99.
    * Use the nonnull GCC attribute when appropriate. It will cause the compiler to emit a warning when someone tries to pass it a value the compilers can prove will be NULL.
    * Separate the return value and the resulting length. This lets you use handle up to SIZE_MAX instead of SSIZE_MAX bytes. You can use an in/out param (i.e., a pointer) for the compressed size.

    So, something like this (largely copied from Squash)

    Code:
    LZ5_NONNULL(1, 2, 4)
    Lz5Status
    lz5_compress (
        size_t* compressed_size,
        uint8_t compressed[LZ5_ARRAY_PARAM(*compressed_size)],
        size_t uncompressed_size,
        const uint8_t uncompressed[LZ5_ARRAY_PARAM(uncompressed_size)]);
    
    LZ5_NONNULL(1, 2, 4)
    Lz5Status
    lz5_decompress (
        size_t* decompressed_size,
        uint8_t decompressed[LZ5_ARRAY_PARAM(*decompressed_size)],
        size_t compressed_size,
        const uint8_t compressed[LZ5_ARRAY_PARAM(compressed_size)]);
    Obviously other parts of the API should also be changed similarly.

    LZ5_NONNULL and LZ5_ARRAY_PARAM would be macros; see SQUASH_NONNULL and SQUASH_ARRAY_PARAM for details. Lz5Status could be an enum; this helps people checking the result in a switch make sure that they have tested for all possibilities (most compilers have optional warnings for unhandled cases).

  26. #22
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    it will be great to synchronize these API changes with lz4/zstd
    Last edited by Bulat Ziganshin; 3rd December 2015 at 20:32.

  27. #23
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 Posts
    Quote Originally Posted by m^3 View Post
    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);]
    I think all that you need is already in "programs\fullbench.c" which can be compiled with "make fullbench".

    I didn't want to deal with framing and streaming API therefore I used well-tested LZ4 as a base.

  28. #24
    Member
    Join Date
    Sep 2010
    Location
    US
    Posts
    126
    Thanks
    4
    Thanked 69 Times in 29 Posts
    I have a request for everyone : (LZ5, LZ4, etc.)

    Put the version of your code somewhere very prominent on your github page so it's easy to see what version # you currently consider your code.

    Also put the version # in the code.

    Don't have separate version numbers for your code vs. the source rev. (eg. source rev r191 but the code says version "172" or whatever).

    Ideally the github download would be "lz5-r132.zip" instead of "lz5-master" but I suppose you can't control that.

    I find it almost impossible to tell that I'm testing the same version of the code as someone else.
    Last edited by cbloom; 3rd August 2016 at 20:32.

  29. The Following 3 Users Say Thank You to cbloom For This Useful Post:

    Bulat Ziganshin (3rd December 2015),Cyan (4th December 2015),Turtle (4th December 2015)

  30. #25
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 Posts
    My assumption is that "master" is always the last stable release and is the same as "Latest release" from https://github.com/inikep/lz5/releases (you can get "lz5-r132.zip" there).
    A new unstable version in "dev" will get a number r133 (I prefer v1.3.3 but I left it this way for similarity with LZ4).

    There is some inconsistency in LZ4 but current version of LZ5 has the same numer in lz5.h:
    #define LZ5_VERSION_MAJOR 1 /* for breaking interface changes */
    #define LZ5_VERSION_MINOR 3 /* for new (non-breaking) interface capabilities */
    #define LZ5_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
    #define LZ5_VERSION_NUMBER (LZ5_VERSION_MAJOR *100*100 + LZ5_VERSION_MINOR *100 + LZ5_VERSION_RELEASE)
    Last edited by inikep; 3rd December 2015 at 23:05.

  31. #26
    Member
    Join Date
    Jul 2013
    Location
    United States
    Posts
    194
    Thanks
    44
    Thanked 140 Times in 69 Posts
    First, to get it out of the way, the "1.3.2" style is typically what is referred to as semantic versioning. It's not really another way of writing "r132"… "r132" would be more like "132.0.0".

    In the archives provided automatically by GitHub "master" means the last commit from the master branch. You can use the master branch as stable if you want (I believe that's what LZ4 and ZSTD do), but that's definitely not the (de facto) standard way of doing it. Typically, master is used for development. There is usually no single stable branch; instead, as releases are made tags are added to the repository (typically in the form of a "v" followed by the version number, such as "v1.2.3" or "v321"). GitHub shows tags as releases, and lets you attach arbitrary files to them.

    In most projects, branches are used for two main purposes. The first is to develop features; for example, if you're working on adding XYZ support, you might create a branch called "add-xyz-support" or "wip/add-xyz-support" (wip stands for "work in progress", it is used to help people distinguish between feature branches and other uses).

    The second is typically only used for larger projects when a new stable minor release is made. They are usually named "project-major-minor" (e.g., "lz5-1-3" would correspond to the 1.3.x release series). Development then continues on master, and some patches may be backported to one or more stable branch. Eventually, someone may tag a commit on the lz5-1-3 branch as v1.3.1 (or v1.3.2, v1.3.3, …) to put out a new stable release. This lets projects continue development in master uninterrupted while still allowing a convenient way to provide small updates and bug fixes to stable versions.

    I could be wrong, but I believe the "r123" syntax is a holdover from when LZ4 was hosted in subversion, where commits are numbered sequentially. In this case "r123" would be the 123rd commit to trunk (subversion's version of master). For SVN, if trunk is used as stable (again, this was never really the standard thing to do, but some people did) then the version number and the commit number would be the same, and cbloom would be happy. Alas, git doesn't work that way. Development is distributed, so if commits were numbered sequentially "r123" would be ambiguous; your "r123" and my "r123" could be completely different. Instead, git uses SHA-1 checksums for commits, which jump around.

    Quote Originally Posted by cbloom View Post
    Don't have separate version numbers for your code vs. the source rev. (eg. source rev r191 but the code says version "172" or whatever).
    Obviously this doesn't work with git. You don't have control over the source revision ID, and they certainly look nothing like "r191"; for example, Squash master is at 98e3c8ce50d74f2fc40414e146895cac26530130 right now, and the commit before that was 79569b8775dffd9ff5d1eb4071db12fa6fc19386). However, what you can do is tag your releases, so that if someone wants "r191" they would just `git checkout r191` (or, if you're using semantic versioning, `git checkout v1.2.3`).

  32. The Following 2 Users Say Thank You to nemequ For This Useful Post:

    Bulat Ziganshin (4th December 2015),inikep (4th December 2015)

  33. #27
    Member
    Join Date
    Jul 2013
    Location
    United States
    Posts
    194
    Thanks
    44
    Thanked 140 Times in 69 Posts
    Quote Originally Posted by cbloom View Post
    Ideally the github download would be "lz5-r132.zip" instead of "lz5-master" but I suppose you can't control that.
    You can't control the download link on the main page at all, but if you go to the Releases section you can get a link to a specific release instead of master. For the ones generated automatically by GitHub it will be called "r132.zip" not "lz5-r132.zip", but still…

    Personally, I the archives GitHub generates automatically, since there are some major problems with a lot of them. It's just a snapshot of the contents of the git repository, minus the actual git data. If the project uses submodules they will not be included, and you can't get them because the git information isn't included, so the archive is basically broken. It also doesn't include the correct data for LFS (which I find remarkable given that git-lfs is a GitHub project…). Unfortunately there is no way to disable the generated archives, make the download link on the main page point to a custom (properly generated) archive, or fix the issue. I have contacted GitHub about the issues, they have no intention of fixing them.

    Basically, if the author provides an archive, you should use that instead of the github generated one. Or just use git to clone the repo and checkout whatever tag, branch, commit, etc. you want.

  34. #28
    Member
    Join Date
    Aug 2015
    Location
    Yorkshire, England
    Posts
    2
    Thanks
    84
    Thanked 2 Times in 1 Post
    In the past during development I've used SubWCRev when using SVN - it allows substituting information about the SVN header into a text file. So I have a template version of a header file with something like this:
    const char* g_pVersion = "v0.0.$WCREV$";
    Which SubWCRev would then generate the actual header file which was included and had the current version.

    You can do that with Git as well, but requires a little more work. Git has lots of information available from describe, but it takes some processing to make that useful. An example batch file that does that is here:
    https://github.com/Thell/git-vs-versioninfo-gen
    That can generate a header file for you. But you must put tags in yourself.

    For actual releases, rather than development builds I like the approach of naming a build as well as having the build number. Much easier for someone to remember if they're using "polar bear", rather than 0.0.1.2.3 or 0.0.1.2.2. The modern example is the naming of Android versions.

    -Brian.

  35. #29
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    307
    Thanks
    68
    Thanked 166 Times in 63 Posts
    Quote Originally Posted by nemequ View Post
    For the ones generated automatically by GitHub it will be called "r132.zip" not "lz5-r132.zip".
    When you click "Source code" at https://github.com/inikep/lz5/releases you will get exactly lz5-r132.zip.

  36. #30
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    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

Page 1 of 3 123 LastLast

Similar Threads

  1. Replies: 45
    Last Post: 25th November 2016, 04:30
  2. VMware tar modification
    By nimdamsk in forum Data Compression
    Replies: 5
    Last Post: 7th November 2011, 13: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
  •