summaryrefslogtreecommitdiffstats
path: root/lib/lz4hc.c
diff options
context:
space:
mode:
authorYann Collet <cyan@fb.com>2018-05-03 22:38:32 (GMT)
committerYann Collet <cyan@fb.com>2018-05-03 22:38:32 (GMT)
commitdc4270710739296602235caa5cfd065feafd87b7 (patch)
tree4a2c8fe93961b94bafbc2682b04cec87a406f102 /lib/lz4hc.c
parent2b6c4f3d6367bf3f8bc38358109ab0a1b1d7340b (diff)
downloadlz4-dc4270710739296602235caa5cfd065feafd87b7.zip
lz4-dc4270710739296602235caa5cfd065feafd87b7.tar.gz
lz4-dc4270710739296602235caa5cfd065feafd87b7.tar.bz2
created LZ4HC_FindLongestMatch()
simplified match finder only searching forward and within current buffer, for easier testing of optimizations.
Diffstat (limited to 'lib/lz4hc.c')
-rw-r--r--lib/lz4hc.c104
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... */