summaryrefslogtreecommitdiffstats
path: root/lib/lz4hc.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/lz4hc.c')
-rw-r--r--lib/lz4hc.c121
1 files changed, 76 insertions, 45 deletions
diff --git a/lib/lz4hc.c b/lib/lz4hc.c
index 6c50db5..c58cd9d 100644
--- a/lib/lz4hc.c
+++ b/lib/lz4hc.c
@@ -227,6 +227,7 @@ LZ4HC_InsertAndGetWiderMatch (
const BYTE* const dictBase = hc4->dictBase;
int const lookBackLength = (int)(ip-iLowLimit);
int nbAttempts = maxNbAttempts;
+ int matchChainPos = 0;
U32 const pattern = LZ4_read32(ip);
U32 matchIndex;
U32 dictMatchIndex;
@@ -241,31 +242,30 @@ LZ4HC_InsertAndGetWiderMatch (
matchIndex, lowestMatchIndex);
while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) {
- DEBUGLOG(7, "remaining attempts : %i", nbAttempts);
+ int mlt=0;
nbAttempts--;
assert(matchIndex < ipIndex);
if (favorDecSpeed && (ipIndex - matchIndex < 8)) {
/* do nothing */
- } else if (matchIndex >= dictLimit) {
+ } else if (matchIndex >= dictLimit) { /* within current Prefix */
const BYTE* const matchPtr = base + matchIndex;
assert(matchPtr >= lowPrefixPtr);
assert(matchPtr < ip);
assert(longest >= 1);
if (LZ4_read16(iLowLimit + longest - 1) == LZ4_read16(matchPtr - lookBackLength + longest - 1)) {
if (LZ4_read32(matchPtr) == pattern) {
- int mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
int const back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, lowPrefixPtr) : 0;
+ mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
mlt -= back;
if (mlt > longest) {
longest = mlt;
- *matchpos = matchPtr+back;
- *startpos = ip+back;
+ *matchpos = matchPtr + back;
+ *startpos = ip + back;
} } }
- } else { /* matchIndex < dictLimit */
+ } else { /* lowestMatchIndex <= matchIndex < dictLimit */
const BYTE* const matchPtr = dictBase + matchIndex;
if (LZ4_read32(matchPtr) == pattern) {
const BYTE* const dictStart = dictBase + hc4->lowLimit;
- int mlt;
int back = 0;
const BYTE* vLimit = ip + (dictLimit - matchIndex);
if (vLimit > iHighLimit) vLimit = iHighLimit;
@@ -280,9 +280,10 @@ LZ4HC_InsertAndGetWiderMatch (
*startpos = ip + back;
} } }
- { U32 const nextOffset = DELTANEXTU16(chainTable, matchIndex);
- matchIndex -= nextOffset;
- if (patternAnalysis && nextOffset==1) {
+ { U32 const distNextMatch = DELTANEXTU16(chainTable, matchIndex);
+ if (1 && patternAnalysis && distNextMatch==1 && matchChainPos==0) {
+ U32 const matchCandidateIdx = matchIndex-1;
+ //static U64 g_nbPatternAnalysis = 0; g_nbPatternAnalysis++; if (g_nbPatternAnalysis % (((g_nbPatternAnalysis/1000000)+1)*100)==0) DEBUGLOG(2, "g_nbPatternAnalysis=%llu ", g_nbPatternAnalysis);
/* may be a repeated pattern */
if (repeat == rep_untested) {
if ( ((pattern & 0xFFFF) == (pattern >> 16))
@@ -293,21 +294,48 @@ LZ4HC_InsertAndGetWiderMatch (
repeat = rep_not;
} }
if ( (repeat == rep_confirmed)
- && (matchIndex >= dictLimit) ) { /* same segment only */
- const BYTE* const matchPtr = base + matchIndex;
+ && (matchCandidateIdx >= dictLimit) ) { /* same segment only */
+ const BYTE* const matchPtr = base + matchCandidateIdx;
if (LZ4_read32(matchPtr) == pattern) { /* good candidate */
size_t const forwardPatternLength = LZ4HC_countPattern(matchPtr+sizeof(pattern), iHighLimit, pattern) + sizeof(pattern);
const BYTE* const maxLowPtr = (lowPrefixPtr + MAX_DISTANCE >= ip) ? lowPrefixPtr : ip - MAX_DISTANCE;
size_t const backLength = LZ4HC_reverseCountPattern(matchPtr, maxLowPtr, pattern);
size_t const currentSegmentLength = backLength + forwardPatternLength;
+ //static U64 g_nbPatternAnalysis_confirmed = 0; g_nbPatternAnalysis_confirmed++; if (g_nbPatternAnalysis_confirmed%(((g_nbPatternAnalysis_confirmed/100000)+1)*100)==0) DEBUGLOG(2, "g_nbPatternAnalysis_confirmed=%llu ", g_nbPatternAnalysis_confirmed);
if ( (currentSegmentLength >= srcPatternLength) /* current pattern segment large enough to contain full srcPatternLength */
&& (forwardPatternLength <= srcPatternLength) ) { /* haven't reached this position yet */
- matchIndex += (U32)forwardPatternLength - (U32)srcPatternLength; /* best position, full pattern, might be followed by more match */
+ matchIndex = matchCandidateIdx + (U32)forwardPatternLength - (U32)srcPatternLength; /* best position, full pattern, might be followed by more match */
} else {
- matchIndex -= (U32)backLength; /* let's go to farthest segment position, will find a match of length currentSegmentLength + maybe some back */
+ matchIndex = matchCandidateIdx - (U32)backLength; /* let's go to farthest segment position, will find a match of length currentSegmentLength + maybe some back */
}
- } } } }
+ matchChainPos = 0;
+ continue;
+ } }
+ } }
+
+ if (mlt == longest) { /* better match => select a better chain */
+ assert(longest >= MINMATCH);
+ if (1 && matchIndex + longest <= ipIndex) {
+ U32 distanceToNextMatch = 1;
+ int pos;
+ //static U64 g_nbChainSwapper = 0; g_nbChainSwapper++; if (g_nbChainSwapper%(((g_nbChainSwapper/100000)+1)*100)==0) DEBUGLOG(2, "g_nbChainSwapper=%llu ", g_nbChainSwapper);
+ for (pos = matchChainPos; pos <= longest - MINMATCH; pos++) {
+ U32 const candidateDist = DELTANEXTU16(chainTable, matchIndex + pos);
+ if (candidateDist > distanceToNextMatch) {
+ distanceToNextMatch = candidateDist;
+ matchChainPos = pos;
+ }
+ }
+ if (distanceToNextMatch > matchIndex) break; /* avoid overflow */
+ matchIndex -= distanceToNextMatch;
+ continue;
+ }
+ }
+
+ /* follow current chain */
+ matchIndex -= DELTANEXTU16(chainTable, matchIndex+matchChainPos);
+
} /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */
if (dict == usingDictCtx && nbAttempts && ipIndex - lowestMatchIndex < MAX_DISTANCE) {
@@ -339,6 +367,7 @@ LZ4HC_InsertAndGetWiderMatch (
}
}
}
+
return longest;
}
@@ -1099,7 +1128,7 @@ LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4,
int nbAttempts = maxNbAttempts;
U32 const pattern = LZ4_read32(ip);
U32 matchIndex;
- int fromMStart = 0;
+ int matchChainPos = 0;
DEBUGLOG(7, "LZ4HC_InsertAndGetWiderMatch");
/* First Match */
@@ -1109,13 +1138,11 @@ LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4,
matchIndex, lowestMatchIndex);
/* find first match */
- while ( (longest <= MINMATCH)
+ while ( 1 && (longest < MINMATCH)
&& (matchIndex>=lowestMatchIndex)
&& (nbAttempts) ) {
const BYTE* const matchPtr = base + matchIndex;
assert(matchIndex < ipIndex);
- assert(matchIndex >= dictLimit);
- assert(matchPtr >= lowPrefixPtr);
assert(matchPtr < ip);
assert(longest >= 1);
nbAttempts--;
@@ -1124,7 +1151,6 @@ LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4,
if (mlt > longest) {
longest = mlt;
*matchpos = matchPtr;
- break;
} }
{ U32 const nextOffset = DELTANEXTU16(chainTable, matchIndex);
@@ -1132,39 +1158,44 @@ LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4,
}
} /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */
- assert(longest > MINMATCH);
- while ((matchIndex-fromMStart>=lowestMatchIndex) && (nbAttempts)) {
- const BYTE* const matchPtr = base + matchIndex - fromMStart;
+ /* search longer matches */
+ while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) {
+ const BYTE* const matchPtr = base + matchIndex;
+ int mlt = 0;
assert(matchIndex < ipIndex);
- assert(matchIndex >= dictLimit);
- assert(matchPtr >= lowPrefixPtr);
assert(matchPtr < ip);
- assert(longest >= 1);
+ assert(longest >= MINMATCH);
nbAttempts--;
if (LZ4_read16(ip + longest - 1) == LZ4_read16(matchPtr + longest - 1)) {
if (LZ4_read32(matchPtr) == pattern) {
- int mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
+ mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
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;
+ }
+ }
+ }
+
+ /* search more promising chain */
+ if (mlt == longest) {
+ if (1 && matchIndex + longest <= ipIndex) {
+ U32 distanceToNextMatch = 1;
+ int pos;
+ for (pos = matchChainPos; pos <= longest - MINMATCH; pos++) {
+ U32 const candidateDist = DELTANEXTU16(chainTable, matchIndex + pos);
+ if (candidateDist > distanceToNextMatch) {
+ distanceToNextMatch = candidateDist;
+ matchChainPos = pos;
}
- } } }
+ }
+ if (distanceToNextMatch > matchIndex) break; /* avoid overflow */
+ matchIndex -= distanceToNextMatch;
+ continue;
+ }
+ }
- { U32 const nextOffset = DELTANEXTU16(chainTable, matchIndex);
+ /* continue current chain */
+ { U32 const nextOffset = DELTANEXTU16(chainTable, matchIndex+matchChainPos);
matchIndex -= nextOffset;
}
} /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */
@@ -1190,8 +1221,8 @@ LZ4HC_FindLongerMatch(LZ4HC_CCtx_internal* const ctx,
/* note : LZ4HC_InsertAndGetWiderMatch() is able to modify the starting position of a match (*startpos),
* but this won't be the case here, as we define iLowLimit==ip,
* so LZ4HC_InsertAndGetWiderMatch() won't be allowed to search past ip */
- //int matchLength = LZ4HC_InsertAndGetWiderMatch(ctx, ip, ip, iHighLimit, minLen, &matchPtr, &ip, nbSearches, 1 /* patternAnalysis */, dict, favorDecSpeed);
- int matchLength = LZ4HC_FindLongestMatch(ctx, ip, iHighLimit, minLen, &matchPtr, nbSearches); (void)dict;
+ int matchLength = LZ4HC_InsertAndGetWiderMatch(ctx, ip, ip, iHighLimit, minLen, &matchPtr, &ip, nbSearches, 1 /* patternAnalysis */, dict, favorDecSpeed);
+ //int matchLength = LZ4HC_FindLongestMatch(ctx, ip, iHighLimit, minLen, &matchPtr, nbSearches); (void)dict;
if (matchLength <= minLen) return match;
if (favorDecSpeed) {
if ((matchLength>18) & (matchLength<=36)) matchLength=18; /* favor shortcut */
generated by cgit v0.12 at 2024-11-02 02:59:43 (GMT)