Merge branch 'tr/xdiff-fast-hash'

Use word-at-a-time comparison to find end of line or NUL (end of buffer),
borrowed from the linux-kernel discussion.

By Thomas Rast
* tr/xdiff-fast-hash:
  xdiff: choose XDL_FAST_HASH code on sizeof(long) instead of __WORDSIZE
  xdiff: load full words in the inner loop of xdl_hash_record

2 files changed, 118 insertions, 0 deletions

diff --git a/Makefile b/Makefile
index 7e243085da..bdf2a578df 100644
--- a/Makefile
+++ b/Makefile
@@ -288,6 +288,11 @@ all::
 # dependency rules.
 #
 # Define NATIVE_CRLF if your platform uses CRLF for line endings.
+#
+# Define XDL_FAST_HASH to use an alternative line-hashing method in
+# the diff algorithm.  It gives a nice speedup if your processor has
+# fast unaligned word loads.  Does NOT work on big-endian systems!
+# Enabled by default on x86_64.
 
 GIT-VERSION-FILE: FORCE
 	@$(SHELL_PATH) ./GIT-VERSION-GEN
@@ -902,6 +907,9 @@ EXTLIBS =
 # because maintaining the nesting to match is a pain.  If
 # we had "elif" things would have been much nicer...
 
+ifeq ($(uname_M),x86_64)
+	XDL_FAST_HASH = YesPlease
+endif
 ifeq ($(uname_S),OSF1)
 	# Need this for u_short definitions et al
 	BASIC_CFLAGS += -D_OSF_SOURCE
@@ -1775,6 +1783,10 @@ ifndef NO_MSGFMT_EXTENDED_OPTIONS
 	MSGFMT += --check --statistics
 endif
 
+ifneq (,$(XDL_FAST_HASH))
+	BASIC_CFLAGS += -DXDL_FAST_HASH
+endif
+
 ifeq ($(TCLTK_PATH),)
 NO_TCLTK=NoThanks
 endif
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 0de084e53f..1b3b471ac8 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -20,6 +20,8 @@
  *
  */
 
+#include <limits.h>
+#include <assert.h>
 #include "xinclude.h"
 
 
@@ -276,6 +278,109 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,
 	return ha;
 }
 
+#ifdef XDL_FAST_HASH
+
+#define ONEBYTES	0x0101010101010101ul
+#define NEWLINEBYTES	0x0a0a0a0a0a0a0a0aul
+#define HIGHBITS	0x8080808080808080ul
+
+/* Return the high bit set in the first byte that is a zero */
+static inline unsigned long has_zero(unsigned long a)
+{
+	return ((a - ONEBYTES) & ~a) & HIGHBITS;
+}
+
+static inline long count_masked_bytes(unsigned long mask)
+{
+	if (sizeof(long) == 8) {
+		/*
+		 * Jan Achrenius on G+: microoptimized version of
+		 * the simpler "(mask & ONEBYTES) * ONEBYTES >> 56"
+		 * that works for the bytemasks without having to
+		 * mask them first.
+		 */
+		return mask * 0x0001020304050608 >> 56;
+	} else {
+		/*
+		 * Modified Carl Chatfield G+ version for 32-bit *
+		 *
+		 * (a) gives us
+		 *   -1 (0, ff), 0 (ffff) or 1 (ffffff)
+		 * (b) gives us
+		 *   0 for 0, 1 for (ff ffff ffffff)
+		 * (a+b+1) gives us
+		 *   correct 0-3 bytemask count result
+		 */
+		long a = (mask - 256) >> 23;
+		long b = mask & 1;
+		return a + b + 1;
+	}
+}
+
+unsigned long xdl_hash_record(char const **data, char const *top, long flags)
+{
+	unsigned long hash = 5381;
+	unsigned long a = 0, mask = 0;
+	char const *ptr = *data;
+	char const *end = top - sizeof(unsigned long) + 1;
+
+	if (flags & XDF_WHITESPACE_FLAGS)
+		return xdl_hash_record_with_whitespace(data, top, flags);
+
+	ptr -= sizeof(unsigned long);
+	do {
+		hash += hash << 5;
+		hash ^= a;
+		ptr += sizeof(unsigned long);
+		if (ptr >= end)
+			break;
+		a = *(unsigned long *)ptr;
+		/* Do we have any '\n' bytes in this word? */
+		mask = has_zero(a ^ NEWLINEBYTES);
+	} while (!mask);
+
+	if (ptr >= end) {
+		/*
+		 * There is only a partial word left at the end of the
+		 * buffer. Because we may work with a memory mapping,
+		 * we have to grab the rest byte by byte instead of
+		 * blindly reading it.
+		 *
+		 * To avoid problems with masking in a signed value,
+		 * we use an unsigned char here.
+		 */
+		const char *p;
+		for (p = top - 1; p >= ptr; p--)
+			a = (a << 8) + *((const unsigned char *)p);
+		mask = has_zero(a ^ NEWLINEBYTES);
+		if (!mask)
+			/*
+			 * No '\n' found in the partial word.  Make a
+			 * mask that matches what we read.
+			 */
+			mask = 1UL << (8 * (top - ptr) + 7);
+	}
+
+	/* The mask *below* the first high bit set */
+	mask = (mask - 1) & ~mask;
+	mask >>= 7;
+	hash += hash << 5;
+	hash ^= a & mask;
+
+	/* Advance past the last (possibly partial) word */
+	ptr += count_masked_bytes(mask);
+
+	if (ptr < top) {
+		assert(*ptr == '\n');
+		ptr++;
+	}
+
+	*data = ptr;
+
+	return hash;
+}
+
+#else /* XDL_FAST_HASH */
 
 unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
 	unsigned long ha = 5381;
@@ -293,6 +398,7 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
 	return ha;
 }
 
+#endif /* XDL_FAST_HASH */
 
 unsigned int xdl_hashbits(unsigned int size) {
 	unsigned int val = 1, bits = 0;