From bf12ca9a1e60e513fe5a59f07624357bc2d1d001 Mon Sep 17 00:00:00 2001
From: "yann.collet.73@gmail.com"
 <yann.collet.73@gmail.com@650e7d94-2a16-8b24-b05c-7c0b3f6821cd>
Date: Mon, 21 Nov 2011 23:56:21 +0000
Subject: [PATCH] Slightly improved compression speed

git-svn-id: https://lz4.googlecode.com/svn/trunk@41 650e7d94-2a16-8b24-b05c-7c0b3f6821cd
---
 lz4.c | 21 +++++++++++++--------
 1 file changed, 13 insertions(+), 8 deletions(-)

diff --git a/lz4.c b/lz4.c
index 1cf04d8..92fe61a 100644
--- a/lz4.c
+++ b/lz4.c
@@ -160,6 +160,7 @@ int LZ4_compressCtx(void** ctx,
 
 	BYTE* op = (BYTE*) dest;
 	
+	const size_t DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
 	int len, length;
 	const int skipStrength = SKIPSTRENGTH;
 	U32 forwardH;
@@ -227,13 +228,16 @@ _next_match:
 		// Start Counting
 		ip+=MINMATCH; ref+=MINMATCH;   // MinMatch verified
 		anchor = ip;
-		while (A32(ref) == A32(ip))
+		while (ip<matchlimit-3)
 		{
-			ip+=4; ref+=4;
-			if (ip>matchlimit-4) { ref -= ip - (matchlimit-3); ip = matchlimit-3; break; }
+			int diff = A32(ref) ^ A32(ip);
+			if (!diff) { ip+=4; ref+=4; continue; }
+			ip += DeBruijnBytePos[((U32)((diff & -diff) * 0x077CB531U)) >> 27];
+			goto _endCount;
 		}
-		if (A16(ref) == A16(ip)) { ip+=2; ref+=2; }
-		if (*ref == *ip) ip++;
+		if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }
+		if ((ip<matchlimit) && (*ref == *ip)) ip++;
+_endCount:
 		len = (ip - anchor);
 		
 		// Encode MatchLength
@@ -298,6 +302,7 @@ int LZ4_compress64kCtx(void** ctx,
 
 	BYTE* op = (BYTE*) dest;
 	
+	const size_t DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
 	int len, length;
 	const int skipStrength = SKIPSTRENGTH;
 	U32 forwardH;
@@ -366,9 +371,9 @@ _next_match:
 		anchor = ip;
 		while (ip<matchlimit-3)
 		{
-			if (A32(ref) == A32(ip)) { ip+=4; ref+=4; continue; }
-			if (A16(ref) == A16(ip)) { ip+=2; ref+=2; }
-			if (*ref == *ip) ip++;
+			int diff = A32(ref) ^ A32(ip);
+			if (!diff) { ip+=4; ref+=4; continue; }
+			ip += DeBruijnBytePos[((U32)((diff & -diff) * 0x077CB531U)) >> 27];
 			goto _endCount;
 		}
 		if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }
-- 
2.7.4