summaryrefslogtreecommitdiffstats
path: root/lib/lz4hc.c
diff options
context:
space:
mode:
authorYann Collet <cyan@fb.com>2018-05-03 23:31:41 (GMT)
committerYann Collet <cyan@fb.com>2018-05-03 23:31:41 (GMT)
commit434ace7244b063c418b8d9f5c29330411a1df237 (patch)
tree8862536ad6199767f01c57193cd145c0346178f5 /lib/lz4hc.c
parentdc4270710739296602235caa5cfd065feafd87b7 (diff)
downloadlz4-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.c20
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);