Page 3 of 3 FirstFirst 123
Results 61 to 70 of 70

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

  1. #61
    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.

  2. #62
    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

  3. #63
    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.

  4. #64
    Member
    Join Date
    Nov 2015
    Location
    boot ROM
    Posts
    92
    Thanks
    27
    Thanked 15 Times in 14 Posts
    Hmm, when it comes to fuzzing, I think it makes more sense to fuzz decompressor. Compressor inevitably faces a lot of data, and if something goes wrong, bug reports are quite likely. Since compressor meant to deal with arbitrary input anyway, there're much less issues to expect. At most, program needs to deal with compressor output larger than input. Other than that, compression makes no major assumptions about data. On other hand, most practical attacks would try to feed untrusted and malformed data into decompressor. Provoking it to do something unexpected. Because decompressors are not meant to deal with arbitrary input, to begin with. They expect certain syntax following some rules.

    So I've got myself a bit more familiar with LZ5 format and got to think it can be interesting idea to try to "attack" it in smarter ways, looking what happens. I can see 2 viable ways:

    1) Try to lie about matches sizes/offsets, etc - attempting to provoke access beyond of buffers. If program expects small block of data on decompression, yet input is malformed, "small" block can try to provoke quite far access, possibly further than buffer size. Since it was not expected, at this point only decompressor itself can detect the fact it attempts to access beyond of allocated buffers and abort decompression with error. So IMHO it makes sense to try to fool decompressor in first place.

    2) Since larger integers are encoded by adding them, most naive implementation could be fooled into adding integers indefinitely. Eventually facing integer overflow (only viable on 32-bit systems). While virtually any CPU in the world has got conditional flags to indicate this scenario, C is a bit dumbass about this case and just silently overflows. This happened once to LZ4 and it can be used to trick decompressor to do illegal memory access.

    Btw, I've been curious why LZ4 and LZ5 encode larger numbers as sequences of added bytes? Sounds size-inefficient for some cases, no? Wouldn't it be smarter to encode like this: say, if current byte is less than, e.g. 0xfc - it is immediate value of (potentially larger) integer. Else it rather means sizeof (following larger integer) == (0x100 - curreny byte). I.e. using few highest values of byte to indicate it is larger integer instead. I think I've seen this encoding in some network protocol. As far as I understand it ... well, if in my example if I compress e.g. Linux kernel and it ends up with 1MiB block of zeros (there are about 2 such areas), even "ideal" case is going to emit like 4KiB of data just to describe adequate integer. Which sounds a bit wasteful, no? Does it brings some advantages, etc? (e.g. is it faster, etc? or why it got so popular, despite being space-inefficient for large values?).

    And while I think I've got idea about LZ5 data format, it would be great if there is some dead simple example, to make sure I've got it right.

    P.S.: I've also found recent -dev allows FS=2. i wonder what is it? It exists in code but never used in levels and when I've gave it a try, it killed HC compression speed a lot, while ratio actually got slightly worse on some random chunks of data I've tested it.
    Last edited by xcrh; 6th February 2016 at 16:39.

  5. #65
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    LZ5 is build on top of LZ4 also because it was very well tested. Trying to overflow offsets or lenghts always lead to the same problem: the access outside the buffer. The decoder needs to check if pointer goes outside (before or after) buffer and LZ5_decompress_safe() does it. LZ5_decompress_fast() is faster, because doesn't check pointers but you can use it on your own risk.

    True, LZ5 encodes larger numbers as sequences of added bytes. The solution you gave gives a slightly improvement. With ordinary files a gain is small, but with 1MiB block of zeros a gain will be great.

    FS=2 is a full binary tree update, only for testing.

  6. Thanks:

    xcrh (6th February 2016)

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

    Changes:
    - improved: levels from 13 to 15 (maximum compression ratio)
    - added a new parser: LZ5HC_optimal_price_bt
    - updated documentation: lz5_Block_format.md and lz5_Frame_format.md
    - changed lz5.exe: the "-B" option with block size [1-7] = 64KB, 256KB, 1MB, 4MB, 16MB, 64MB, 256MB (default : 4 = 4MB)

    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

  8. Thanks (6):

    comp1 (11th February 2016),Cyan (11th February 2016),JamesB (12th February 2016),tobijdc (11th February 2016),Turtle (11th February 2016),xcrh (21st February 2016)

  9. #67
    Member
    Join Date
    Nov 2015
    Location
    boot ROM
    Posts
    92
    Thanks
    27
    Thanked 15 Times in 14 Posts
    Quote Originally Posted by inikep View Post
    LZ5 is build on top of LZ4 also because it was very well tested. Trying to overflow offsets or lenghts always lead to the same problem: the access outside the buffer. The decoder needs to check if pointer goes outside (before or after) buffer and LZ5_decompress_safe() does it. LZ5_decompress_fast() is faster, because doesn't check pointers but you can use it on your own risk.
    That's what makes me curious: why LZ5 uses this particular representation? Since it got plenty of new features it seems it is better to retest everything on decompressor side anyway, as hard as possible (of course only safe version supposed to be safe). This integer representation makes some sense for LZ4 - looking on LZ4 I can get idea it was never meant for large blocks or good ratios, it values speed over everything else, so it probably shouldn't encounter large integers in first place, but LZ5 appears to target larger blocks and better ratios, so larger numbers should be a bit more common, no?

    True, LZ5 encodes larger numbers as sequences of added bytes. The solution you gave gives a slightly improvement. With ordinary files a gain is small, but with 1MiB block of zeros a gain will be great.
    I guess I can just use RLE if I'm taking particular aim on large block of zeros (in ways which do not kill decompression speed or even improve it), but as brieflz shown, LZ could eventually dub as RLE on its own, if underlying format allows compact representation. Though it is quite unusual use case, sure.

    p.s. and thx for 1.4.x - whatever, but new matchfinder is a good thing, I can confirm new numbers aren't just marketing, on most data high levels improved ratios for sure while decompression speed stays
    Last edited by xcrh; 21st February 2016 at 05:49.

  10. #68
    Member
    Join Date
    Nov 2015
    Location
    ?l?nsk, PL
    Posts
    81
    Thanks
    9
    Thanked 13 Times in 11 Posts
    I finished fuzzing LZ5, I found no additional issues.

  11. #69
    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
    I finished fuzzing LZ5, I found no additional issues.
    Big thanks m^3. However there was a bug in levels 11 and 12. It's fixed in LZ5 v1.4.1:
    https://github.com/inikep/lz5/releases/tag/v1.4.1

    @xcrh I will put encoding of larger numbers on LZ5's to do list.

  12. #70
    Programmer
    Join Date
    May 2008
    Location
    PL
    Posts
    309
    Thanks
    68
    Thanked 173 Times in 64 Posts
    LZ5 v1.5 has been released at https://github.com/inikep/lz5/releases

    Changes:
    - introduced compatibility with Visual C++ 2010 and newer
    - attached Visual Studio 2010 project
    - thoroughly tested with 21 Travis CI and 7 AppVeyor CI tests
    - fixed bug with reusing a context in lz5frame.c (LZ5F_compressBegin and LZ5_compress_HC_continue)
    - fixed rare bug in match finder (concerns levels 4 - 15)

  13. Thanks:

    Cyan (17th August 2016)

Page 3 of 3 FirstFirst 123

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, 14:27
  4. paq9a modification
    By kaitz in forum Data Compression
    Replies: 7
    Last Post: 28th September 2008, 05:46
  5. Compiler related: Intel's code slower on AMD-CPUs?!
    By Vacon in forum Data Compression
    Replies: 5
    Last Post: 10th May 2008, 18: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
  •