summaryrefslogtreecommitdiffstats
Commit message (Collapse)AuthorAgeFilesLines
* small PA optimizationYann Collet2018-05-061-11/+18
| | | | | which measurably improves speed on levels 9+
* lz4hc: fixed PA / SC parameter orderYann Collet2018-05-051-5/+5
| | | | | | also : reserved PA for levels 9+ (instead of 8+). In most cases, speed is lower, and compression benefit is not worth.
* lz4hc: SC only enabled for opt parserYann Collet2018-05-051-7/+7
| | | | | the trade off is not good for regular HC parser : compression is a little bit better, but speed cost is too large in comparison.
* fixed SC.opt integration with regular HC parserYann Collet2018-05-051-4/+4
| | | | | | | | Only enabled when searching forward. note : it slighly improves compression ratio, but measurably decreases speed. Trade-off to analyse.
* lz4hc: fixed performance issueYann Collet2018-05-051-114/+20
| | | | when combining both PA and CS optimizations
* integrated chain swapper into HC match finderYann Collet2018-05-051-45/+76
| | | | | | | slower than expected Pattern analyzer and Chain Swapper work slower when both activated. Reasons unclear.
* implemented search acceleratorYann Collet2018-05-031-2/+18
| | | | | | | | | | | | | | | | | | | | | | | | greatly improves speed compared to non-accelerated, especially for slower files. On my laptop, -b12 : ``` calgary.tar : 4.3 MB/s => 9.0 MB/s enwik7 : 10.2 MB/s => 13.3 MB/s silesia.tar : 4.0 MB/s => 8.7 MB/s ``` Note : this is the simplified version, without handling dictionaries, external buffer, nor pattern analyzer. Current `dev` branch on these samples gives : ``` calgary.tar : 4.2 MB/s enwik7 : 9.7 MB/s silesia.tar : 3.5 MB/s ``` interestingly, it's slower, presumably due to handling of dictionaries.
* created LZ4HC_FindLongestMatch()Yann Collet2018-05-031-16/+88
| | | | | | simplified match finder only searching forward and within current buffer, for easier testing of optimizations.
* Merge pull request #530 from lz4/lz4fRingBufferYann Collet2018-05-034-64/+103
|\ | | | | Random lz4f clarifications
| * Merge branch 'dev' into lz4fRingBufferYann Collet2018-05-031-10/+8
| |\ | |/ |/|
* | Merge pull request #528 from lz4/complexShortcutYann Collet2018-05-033-85/+160
|\ \ | | | | | | Faster decoding speed
| * | fix comments / indentationCyan49732018-05-031-10/+8
| | | | | | | | | | | | as requested by @terrelln
| | * updated NEWS in preparation for v1.8.2Yann Collet2018-05-021-2/+2
| | |
| | * Merge branch 'lz4fRingBuffer' of github.com:Cyan4973/lz4 into lz4fRingBufferYann Collet2018-05-020-0/+0
| | |\
| | | * updated benchmark for v1.8.2Yann Collet2018-05-021-15/+14
| | | |
| | * | updated benchmark for v1.8.2Yann Collet2018-05-021-17/+16
| | |/
| | * random lz4f clarificationsYann Collet2018-05-022-45/+85
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | the initial intention was to update lz4f ring buffer strategy, but lz4f doesn't use ring buffer. Instead, it uses the destination buffer as much as possible, and merely copies just what's required to preserve history into its own buffer, at the end. Pretty efficient. This patch just clarifies a few comments and add some assert(). It's built on top of #528. It also updates doc.
| | * Merge branch 'dev' into lz4fRingBufferYann Collet2018-05-021-13/+13
| | |\ | |/ / | | / | |/ |/|
* | increased nbAttempts for lz4 -12Yann Collet2018-05-021-13/+13
| | | | | | | | shaves one more kilobyte from silesia.tar
| * removed test that might be optimized awayYann Collet2018-05-021-2/+1
| | | | | | | | under UB rule "no overflow on int"
| * introduce LZ4_decoderRingBufferSize()Yann Collet2018-05-023-62/+116
| | | | | | | | fuzzer : fix and robustify ring buffer tests
| * simplify shortcutYann Collet2018-05-021-55/+22
| |
| * Merge branch 'dev' into complexShortcutYann Collet2018-05-025-67/+79
| |\ | |/ |/|
* | Merge pull request #525 from lz4/testDecMergeYann Collet2018-05-022-13/+23
|\ \ | | | | | | added a test case for LZ4_decompress_fast_usingDict …
| * \ Merge pull request #526 from svpv/makeV1Yann Collet2018-04-291-28/+34
| |\ \ | | | | | | | | lib/Makefile: show commands with V=1
| * | | added a test case for LZ4_decompress_fast_usingDictCyan49732018-04-292-13/+23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | with a separated dictionary since a joined dictionary is now detected as prefix64K. Also : fixed a minor warning under msys
| * | | Merge pull request #522 from svpv/refactorDecYann Collet2018-04-283-90/+196
| |\ \ \ | | | | | | | | | | Refactor dec
* | \ \ \ Merge pull request #521 from lz4/BD_deterministicYann Collet2018-05-011-48/+46
|\ \ \ \ \ | | | | | | | | | | | | fix lz4hc -BD non-determinism
| * | | | | renamed variable for clarityCyan49732018-05-011-7/+7
| | | | | | | | | | | | | | | | | | | | | | | | lowLimit -> lowestMatchIndex
| * | | | | lz4hc changed variableYann Collet2018-04-301-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | to reduce confusion dictLowLimit => dictStart
| * | | | | Merge branch 'dev' into BD_deterministicYann Collet2018-04-2711-49/+152
| |\ \ \ \ \
| * | | | | | fix lz4hc -BD non-determinismYann Collet2018-04-271-3/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | related to chain table update
| * | | | | | lz4hc : minor editions for clarityYann Collet2018-04-271-38/+37
| | | | | | |
* | | | | | | added visual test dir to .gitignoreCyan49732018-05-011-1/+1
| | | | | | |
* | | | | | | clarified streaming decompression functionYann Collet2018-04-301-5/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | restrictions for ring buffer
| | | | | | * Merge pull request #527 from svpv/fastDecYann Collet2018-04-301-25/+82
| | | | | | |\ | |_|_|_|_|/ / |/| | | | | | lz4.c: two-stage shortcut for LZ4_decompress_generic
| | | | | | * lz4.c: two-stage shortcut for LZ4_decompress_genericAlexey Tourbin2018-04-281-25/+82
| | | | |_|/ | | | |/| |
* | | | | | Merge pull request #523 from svpv/makeV1Yann Collet2018-04-291-28/+34
|\ \ \ \ \ \ | | |_|_|_|/ | |/| | | | lib/Makefile: show commands with V=1
| * | | | | lib/Makefile: show commands with V=1Alexey Tourbin2018-04-281-28/+34
| | |_|/ / | |/| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | `make V=1` will now show the commands executed to build the library. A similar technique is used in e.g. linux/Makefile. The bulk of this change is produced with the following vim command: :g!/^\t@echo\>/s/^\t@/\t\$(Q)/
* | | | | Merge branch 'dev' of github.com:lz4/lz4 into devCyan49732018-04-293-90/+196
|\ \ \ \ \
| * \ \ \ \ Merge pull request #515 from svpv/refactorDecYann Collet2018-04-293-90/+196
| |\ \ \ \ \ | | | |_|_|/ | | |/| | | lz4.c: refactor the decoding routines
| | * | | | lz4.c: fixed the LZ4_decompress_fast_continue caseAlexey Tourbin2018-04-271-2/+22
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The change is very similar to that of the LZ4_decompress_safe_continue case. The only reason a make this a separate change is to ensure that the fuzzer, after it's been enhanced, can detect the flaw in LZ4_decompress_fast_continue, and that the change indeed fixes the flaw.
| | * | | | fuzzer.c: enabled ring buffer tests for decompress_fastAlexey Tourbin2018-04-271-40/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Ring buffer tests were performed only with LZ4_decompress_safe_continue, leaving my buggy changes to LZ4_decompress_safe_continue undetected. The tests are now replicated and performed in a similar manner for both LZ4_decompress_safe_continue and LZ4_decompress_safe_continue (except for the small buffer case where only one function can be tested, because part of the dictionary is overwritten with the output). I also updated function names in the messages (changed them to the actual ones). The error was reported for LZ4_decompress_safe(), which I found misleading.
| | * | | | lz4.c: fixed the LZ4_decompress_safe_continue caseAlexey Tourbin2018-04-262-18/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The previous change broke decoding with a ring buffer. That's because I didn't realize that the "double dictionary mode" was possible, i.e. that the decoding routine can look both at the first part of the dictionary passed as prefix and the second part passed via dictStart+dictSize. So this change introduces the LZ4_decompress_safe_doubleDict helper, which handles this "double dictionary" situation. (This is a bit of a misnomer, there is only one dictionary, but I can't think of a better name, and perhaps the designation is not all too bad.) The helper is used only once, in LZ4_decompress_safe_continue, it should be inlined with LZ4_FORCE_O2_GCC_PPC64LE attached to LZ4_decompress_safe_continue. (Also, in the helper functions, I change the dictStart parameter type to "const void*", to avoid a cast when calling helpers. In the helpers, the upcast to "BYTE*" is still required, for compatibility with C++.) So this fixes the case of LZ4_decompress_safe_continue, and I'm surprised by the fact that the fuzzer is now happy and does not detect a similar problem with LZ4_decompress_fast_continue. So before fixing LZ4_decompress_fast_continue, the next logical step is to enhance the fuzzer.
| | * | | | lz4.c: refactor the decoding routinesAlexey Tourbin2018-04-251-53/+79
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | I noticed that LZ4_decompress_generic is sometimes instantiated with identical set of parameters, or (what's worse) with a subtly different sets of parameters. For example, LZ4_decompress_fast_withPrefix64k is instantiated as follows: return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB); while the equivalent withPrefix64k call in LZ4_decompress_usingDict_generic passes 0 for the last argument instead of 64 KB. It turns out that there is no difference in this case: if you change 64 KB to 0 KB in LZ4_decompress_fast_withPrefix64k, you get the same binary code. Moreover, because it's been clarified that LZ4_decompress_fast doesn't check match offsets, it is now obvious that both of these fast/withPrefix64k instantiations are simply redundant. Exactly because LZ4_decompress_fast doesn't check offsets, it serves well with any prefixed dictionary. There's a difference, though, with LZ4_decompress_safe_withPrefix64k. It also passes 64 KB as the last argument, and if you change that to 0, as in LZ4_decompress_usingDict_generic, you get a completely different binary code. It seems that passing 0 enables offset checking: const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB))); However, the resulting code seems to run a bit faster. How come enabling extra checks can make the code run faster? Curiouser and curiouser! This needs extra study. Currently I take the view that the dictSize should be set to non-zero when nothing else will do, i.e. when passing the external dictionary via dictStart. Otherwise, lowPrefix betrays just enough information about the dictionary. * * * Anyway, with this change, I instantiate all the necessary cases as functions with distinctive names, which also take fewer arguments and are therefore less error-prone. I also make the functions non-inline. (The compiler won't inline the functions because they are used more than once. Hence I attach LZ4_FORCE_O2_GCC_PPC64LE to the instances while removing from the callers.) The number of instances is now is reduced from 18 (safe+fast+partial+4*continue+4*prefix+4*dict+2*prefix64+forceExtDict) down to 7 (safe+fast+partial+2*prefix+2*dict). The size of the code is not the only issue here. Separate helper function are much more amenable to profile-guided optimization: it is enough to profile only a few basic functions, while the other less-often used functions, such as LZ4_decompress_*_continue, will benefit automatically. This is the list of LZ4_decompress* functions in liblz4.so, sorted by size. Exported functions are marked with a capital T. $ nm -S lib/liblz4.so |grep -wi T |grep LZ4_decompress |sort -k2 0000000000016260 0000000000000005 T LZ4_decompress_fast_withPrefix64k 0000000000016dc0 0000000000000025 T LZ4_decompress_fast_usingDict 0000000000016d80 0000000000000040 T LZ4_decompress_safe_usingDict 0000000000016d10 000000000000006b T LZ4_decompress_fast_continue 0000000000016c70 000000000000009f T LZ4_decompress_safe_continue 00000000000156c0 000000000000059c T LZ4_decompress_fast 0000000000014a90 00000000000005fa T LZ4_decompress_safe 0000000000015c60 00000000000005fa T LZ4_decompress_safe_withPrefix64k 0000000000002280 00000000000005fa t LZ4_decompress_safe_withSmallPrefix 0000000000015090 000000000000062f T LZ4_decompress_safe_partial 0000000000002880 00000000000008ea t LZ4_decompress_fast_extDict 0000000000016270 0000000000000993 t LZ4_decompress_safe_forceExtDict
* | | | | | updated NEWS for v1.8.2Cyan49732018-04-291-0/+1
|/ / / / / | | | | | | | | | | | | | | | mentioning work from @svpv
* | | | | ignore windows+msys artefactsCyan49732018-04-281-0/+4
| |/ / / |/| | |
* | | | Merge pull request #520 from felixhandte/frame-dict-nitsYann Collet2018-04-272-8/+15
|\ \ \ \ | |_|_|/ |/| | | Minor Fixes to Dictionary Preparation in LZ4 Frame
| * | | Avoid Possibly Redundant Table Clears When Loading HC DictW. Felix Handte2018-04-272-2/+2
| | | |
| * | | Remove Redundant LZ4_resetStream() CallW. Felix Handte2018-04-271-2/+1
| | | |
generated by cgit v0.12 at 2024-11-16 22:17:10 (GMT)