Speed up match length computations

diff --git a/src/lz_binary_trees.c b/src/lz_binary_trees.c
index 4a821f437ecd13232aea95347e8b86e9812a1020..98924780fffba1b46c54f4af543fcf3aad253250 100644 (file)
--- a/src/lz_binary_trees.c
+++ b/src/lz_binary_trees.c
@@ -413,9 +413,10 @@ do_search(const u8 window[restrict],
 
                if (matchptr[len] == strptr[len]) {
 
-                       while (++len != max_len)
-                               if (matchptr[len] != strptr[len])
-                                       break;
+                       if (++len != max_len && matchptr[len] == strptr[len])
+                               while (++len != max_len)
+                                       if (matchptr[len] != strptr[len])
+                                               break;
 
                        if (len > longest_match_len) {
                                longest_match_len = len;

diff --git a/src/lz_brute_force.c b/src/lz_brute_force.c
index 3d186cc239367e49f86704ac77d339eda029a5c5..548b7887ac6a188642e2f532f151b2647013bd52 100644 (file)
--- a/src/lz_brute_force.c
+++ b/src/lz_brute_force.c
@@ -93,28 +93,35 @@ lz_bf_get_matches(struct lz_mf *mf, struct lz_match matches[])
                goto out;
 
        while (matchptr-- > mf->cur_window) {
-               if (matchptr[best_len] == strptr[best_len] &&
-                   matchptr[best_len - 1] == strptr[best_len - 1] &&
-                   matchptr[0] == strptr[0])
-               {
-                       u32 len = 0;
-
-                       while (++len != max_len)
-                               if (matchptr[len] != strptr[len])
-                                       break;
-
-                       if (len > best_len) {
-                               matches[num_matches++] = (struct lz_match) {
-                                       .len = len,
-                                       .offset = strptr - matchptr,
-                               };
-                               best_len = len;
-                               if (best_len == max_len)
-                                       break;
-                               if (num_matches == mf->params.max_search_depth)
-                                       break;
-                       }
-               }
+
+               u32 len;
+
+               if (matchptr[best_len] != strptr[best_len] ||
+                   matchptr[best_len - 1] != strptr[best_len - 1] ||
+                   matchptr[0] != strptr[0])
+                       goto next_match;
+
+               for (len = 1; len < best_len - 1; len++)
+                       if (matchptr[len] != strptr[len])
+                               goto next_match;
+
+               len = best_len;
+
+               while (++len != max_len)
+                       if (matchptr[len] != strptr[len])
+                               break;
+
+               matches[num_matches++] = (struct lz_match) {
+                       .len = len,
+                       .offset = strptr - matchptr,
+               };
+               best_len = len;
+               if (best_len == max_len)
+                       break;
+               if (num_matches == mf->params.max_search_depth)
+                       break;
+       next_match:
+               ;
        }
 
        /* If the longest match is @nice_match_len in length, it may have been

diff --git a/src/lz_hash_chains.c b/src/lz_hash_chains.c
index 7eacac915d71dad4fe9343071b9e2f9635d7c2a4..012d7c462cbdb4f92172d2bb30e5ab158483b149 100644 (file)
--- a/src/lz_hash_chains.c
+++ b/src/lz_hash_chains.c
@@ -180,27 +180,32 @@ do_search(const u8 * restrict window,
        for (; cur_match && depth_remaining--; cur_match = prev_tab[cur_match]) {
 
                const u8 * const matchptr = &window[cur_match];
+               u32 len;
 
-               if (matchptr[best_len] == strptr[best_len] &&
-                   matchptr[best_len - 1] == strptr[best_len - 1] &&
-                   matchptr[0] == strptr[0])
-               {
-                       u32 len = 0;
-
-                       while (++len != max_len)
-                               if (matchptr[len] != strptr[len])
-                                       break;
-
-                       if (len > best_len) {
-                               matches[num_matches++] = (struct lz_match) {
-                                       .len = len,
-                                       .offset = strptr - matchptr,
-                               };
-                               best_len = len;
-                               if (best_len == max_len)
-                                       break;
-                       }
-               }
+               if (matchptr[best_len] != strptr[best_len] ||
+                   matchptr[best_len - 1] != strptr[best_len - 1] ||
+                   matchptr[0] != strptr[0])
+                       goto next_match;
+
+               for (len = 1; len < best_len - 1; len++)
+                       if (matchptr[len] != strptr[len])
+                               goto next_match;
+
+               len = best_len;
+
+               while (++len != max_len)
+                       if (matchptr[len] != strptr[len])
+                               break;
+
+               matches[num_matches++] = (struct lz_match) {
+                       .len = len,
+                       .offset = strptr - matchptr,
+               };
+               best_len = len;
+               if (best_len == max_len)
+                       break;
+       next_match:
+               ;
        }
        return num_matches;
 }