1 files changed, 106 insertions, 43 deletions

diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 0de084e53f..9504eaecb8 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -20,6 +20,8 @@
  *
  */
 
+#include <limits.h>
+#include <assert.h>
 #include "xinclude.h"
 
 
@@ -120,35 +122,6 @@ void *xdl_cha_alloc(chastore_t *cha) {
 	return data;
 }
 
-
-void *xdl_cha_first(chastore_t *cha) {
-	chanode_t *sncur;
-
-	if (!(cha->sncur = sncur = cha->head))
-		return NULL;
-
-	cha->scurr = 0;
-
-	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
-}
-
-
-void *xdl_cha_next(chastore_t *cha) {
-	chanode_t *sncur;
-
-	if (!(sncur = cha->sncur))
-		return NULL;
-	cha->scurr += cha->isize;
-	if (cha->scurr == sncur->icurr) {
-		if (!(sncur = cha->sncur = sncur->next))
-			return NULL;
-		cha->scurr = 0;
-	}
-
-	return (char *) sncur + sizeof(chanode_t) + cha->scurr;
-}
-
-
 long xdl_guess_lines(mmfile_t *mf, long sample) {
 	long nl = 0, size, tsize = 0;
 	char const *data, *cur, *top;
@@ -276,6 +249,109 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,
 	return ha;
 }
 
+#ifdef XDL_FAST_HASH
+
+#define REPEAT_BYTE(x)  ((~0ul / 0xff) * (x))
+
+#define ONEBYTES	REPEAT_BYTE(0x01)
+#define NEWLINEBYTES	REPEAT_BYTE(0x0a)
+#define HIGHBITS	REPEAT_BYTE(0x80)
+
+/* 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;
+		 *
+		 * Doing it like this avoids warnings on 32-bit machines.
+		 */
+		long a = (REPEAT_BYTE(0x01) / 0xff + 1);
+		return mask * a >> (sizeof(long) * 7);
+	} else {
+		/* Carl Chatfield / Jan Achrenius G+ version for 32-bit */
+		/* (000000 0000ff 00ffff ffffff) -> ( 1 1 2 3 ) */
+		long a = (0x0ff0001 + mask) >> 23;
+		/* Fix the 1 for 00 case */
+		return a & mask;
+	}
+}
+
+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 +369,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;
@@ -324,20 +401,6 @@ int xdl_num_out(char *out, long val) {
 	return str - out;
 }
 
-
-long xdl_atol(char const *str, char const **next) {
-	long val, base;
-	char const *top;
-
-	for (top = str; XDL_ISDIGIT(*top); top++);
-	if (next)
-		*next = top;
-	for (val = 0, base = 1, top--; top >= str; top--, base *= 10)
-		val += base * (long)(*top - '0');
-	return val;
-}
-
-
 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
 		      const char *func, long funclen, xdemitcb_t *ecb) {
 	int nb = 0;