diff options
author | Yann Collet <cyan@fb.com> | 2018-05-03 23:31:41 (GMT) |
---|---|---|
committer | Yann Collet <cyan@fb.com> | 2018-05-03 23:31:41 (GMT) |
commit | 434ace7244b063c418b8d9f5c29330411a1df237 (patch) | |
tree | 8862536ad6199767f01c57193cd145c0346178f5 /lib/lz4hc.c | |
parent | dc4270710739296602235caa5cfd065feafd87b7 (diff) | |
download | lz4-434ace7244b063c418b8d9f5c29330411a1df237.zip lz4-434ace7244b063c418b8d9f5c29330411a1df237.tar.gz lz4-434ace7244b063c418b8d9f5c29330411a1df237.tar.bz2 |
implemented search accelerator
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.
Diffstat (limited to 'lib/lz4hc.c')
-rw-r--r-- | lib/lz4hc.c | 20 |
1 files changed, 18 insertions, 2 deletions
diff --git a/lib/lz4hc.c b/lib/lz4hc.c index 132673e..6c50db5 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -1099,6 +1099,7 @@ LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4, int nbAttempts = maxNbAttempts; U32 const pattern = LZ4_read32(ip); U32 matchIndex; + int fromMStart = 0; DEBUGLOG(7, "LZ4HC_InsertAndGetWiderMatch"); /* First Match */ @@ -1132,8 +1133,8 @@ LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4, } /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */ assert(longest > MINMATCH); - while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) { - const BYTE* const matchPtr = base + matchIndex; + while ((matchIndex-fromMStart>=lowestMatchIndex) && (nbAttempts)) { + const BYTE* const matchPtr = base + matchIndex - fromMStart; assert(matchIndex < ipIndex); assert(matchIndex >= dictLimit); assert(matchPtr >= lowPrefixPtr); @@ -1146,6 +1147,21 @@ LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4, if (mlt > longest) { longest = mlt; *matchpos = matchPtr; + matchIndex -= fromMStart; /* beginning of match */ + if (1 && matchIndex + longest <= ipIndex) { + U32 distanceToNextMatch = 1; + int pos; + for (pos = 0; pos <= longest - MINMATCH; pos++) { + U32 const candidateDist = DELTANEXTU16(chainTable, matchIndex + pos); + if (candidateDist > distanceToNextMatch) { + distanceToNextMatch = candidateDist; + fromMStart = pos; + } + } + if (distanceToNextMatch > matchIndex) break; /* avoid overflow */ + matchIndex -= distanceToNextMatch - fromMStart; + continue; + } } } } { U32 const nextOffset = DELTANEXTU16(chainTable, matchIndex); |