From: Eric Biggers <ebiggers3@gmail.com>
Date: Sun, 20 Jul 2014 04:44:17 +0000 (-0500)
Subject: Speed up match length computations
X-Git-Tag: v1.7.1~55
X-Git-Url: https://wimlib.net/git/?p=wimlib;a=commitdiff_plain;h=6929ca50c6d64ac208e7ccc5f1c2c08dada71061

Speed up match length computations
---

diff --git a/src/lz_binary_trees.c b/src/lz_binary_trees.c
index 4a821f43..98924780 100644
--- 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 3d186cc2..548b7887 100644
--- 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 7eacac91..012d7c46 100644
--- 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;
 }