From dc4270710739296602235caa5cfd065feafd87b7 Mon Sep 17 00:00:00 2001
From: Yann Collet <cyan@fb.com>
Date: Thu, 3 May 2018 15:38:32 -0700
Subject: created LZ4HC_FindLongestMatch()

simplified match finder
only searching forward and within current buffer,
for easier testing of optimizations.
---
 lib/lz4hc.c | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++----------
 1 file 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... */
-- 
cgit v0.12