diff options
| -rw-r--r-- | lib/lz4hc.c | 104 |
1 files changed, 88 insertions, 16 deletions
diff --git a/lib/lz4hc.c b/lib/lz4hc.c index 0859ea6..132673e 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -1083,6 +1083,80 @@ LZ4_FORCE_INLINE int LZ4HC_sequencePrice(int litlen, int mlen) } +int +LZ4HC_FindLongestMatch (LZ4HC_CCtx_internal* hc4, + const BYTE* const ip, + const BYTE* const iHighLimit, + int longest, + const BYTE** matchpos, + const int maxNbAttempts) +{ + U16* const chainTable = hc4->chainTable; + U32* const HashTable = hc4->hashTable; + const BYTE* const base = hc4->base; + const U32 ipIndex = (U32)(ip - base); + const U32 lowestMatchIndex = (hc4->lowLimit + 64 KB > ipIndex) ? hc4->lowLimit : ipIndex - MAX_DISTANCE; + int nbAttempts = maxNbAttempts; + U32 const pattern = LZ4_read32(ip); + U32 matchIndex; + + DEBUGLOG(7, "LZ4HC_InsertAndGetWiderMatch"); + /* First Match */ + LZ4HC_Insert(hc4, ip); + matchIndex = HashTable[LZ4HC_hashPtr(ip)]; + DEBUGLOG(7, "First match at index %u / %u (lowestMatchIndex)", + matchIndex, lowestMatchIndex); + + /* find first match */ + while ( (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--; + if (LZ4_read32(matchPtr) == pattern) { + int const mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit); + if (mlt > longest) { + longest = mlt; + *matchpos = matchPtr; + break; + } } + + { U32 const nextOffset = DELTANEXTU16(chainTable, matchIndex); + matchIndex -= nextOffset; + } + } /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */ + + assert(longest > MINMATCH); + while ((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--; + 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); + if (mlt > longest) { + longest = mlt; + *matchpos = matchPtr; + } } } + + { U32 const nextOffset = DELTANEXTU16(chainTable, matchIndex); + matchIndex -= nextOffset; + } + } /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */ + + return longest; +} + + typedef struct { int off; int len; @@ -1100,9 +1174,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_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 */ @@ -1112,19 +1185,18 @@ LZ4HC_FindLongerMatch(LZ4HC_CCtx_internal* const ctx, return match; } -static int LZ4HC_compress_optimal ( - LZ4HC_CCtx_internal* ctx, - const char* const source, - char* dst, - int* srcSizePtr, - int dstCapacity, - int const nbSearches, - size_t sufficient_len, - const limitedOutput_directive limit, - int const fullUpdate, - const dictCtx_directive dict, - const HCfavor_e favorDecSpeed - ) + +static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx, + const char* const source, + char* dst, + int* srcSizePtr, + int dstCapacity, + int const nbSearches, + size_t sufficient_len, + const limitedOutput_directive limit, + int const fullUpdate, + const dictCtx_directive dict, + const HCfavor_e favorDecSpeed) { #define TRAILING_LITERALS 3 LZ4HC_optimal_t opt[LZ4_OPT_NUM + TRAILING_LITERALS]; /* ~64 KB, which is a bit large for stack... */ |