diff options
author | Nick Terrell <terrelln@fb.com> | 2019-07-31 07:57:16 (GMT) |
---|---|---|
committer | Nick Terrell <terrelln@fb.com> | 2019-07-31 17:17:26 (GMT) |
commit | 064adb2e8d95698168d436afc223e8ba44e56831 (patch) | |
tree | 29b96380f4b7525b9ba5feea661cb35684d79cc0 /lib | |
parent | 38c3945de300851757d0dd76182ee28aaf8253a4 (diff) | |
download | lz4-064adb2e8d95698168d436afc223e8ba44e56831.zip lz4-064adb2e8d95698168d436afc223e8ba44e56831.tar.gz lz4-064adb2e8d95698168d436afc223e8ba44e56831.tar.bz2 |
[lz4hc] Chain swap with acceleration
Diffstat (limited to 'lib')
-rw-r--r-- | lib/lz4hc.c | 14 |
1 files changed, 10 insertions, 4 deletions
diff --git a/lib/lz4hc.c b/lib/lz4hc.c index 0608ec6..5922ed7 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -312,20 +312,26 @@ LZ4HC_InsertAndGetWiderMatch ( if (chainSwap && matchLength==longest) { /* better match => select a better chain */ assert(lookBackLength==0); /* search forward only */ if (matchIndex + (U32)longest <= ipIndex) { + int const kTrigger = 4; U32 distanceToNextMatch = 1; + int const end = longest - MINMATCH + 1; + int step = 1; + int accel = 1 << kTrigger; int pos; - for (pos = matchChainPos; pos <= longest - MINMATCH; ++pos) { + for (pos = 0; pos < end; pos += step) { U32 const candidateDist = DELTANEXTU16(chainTable, matchIndex + (U32)pos); + step = (accel++ >> kTrigger); if (candidateDist > distanceToNextMatch) { distanceToNextMatch = candidateDist; matchChainPos = (U32)pos; - } } + accel = 1 << kTrigger; + } + } if (distanceToNextMatch > 1) { if (distanceToNextMatch > matchIndex) break; /* avoid overflow */ matchIndex -= distanceToNextMatch; continue; - } - } } + } } } { U32 const distNextMatch = DELTANEXTU16(chainTable, matchIndex); if (patternAnalysis && distNextMatch==1 && matchChainPos==0) { |