1 files changed, 231 insertions, 101 deletions

diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 3653864e4b..62cb23dfd3 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -20,14 +20,12 @@
  *
  */
 
+#include <limits.h>
+#include <assert.h>
 #include "xinclude.h"
 
 
 
-#define XDL_GUESS_NLINES 256
-
-
-
 
 long xdl_bogosqrt(long n) {
 	long i;
@@ -71,12 +69,6 @@ void *xdl_mmfile_first(mmfile_t *mmf, long *size)
 }
 
 
-void *xdl_mmfile_next(mmfile_t *mmf, long *size)
-{
-	return NULL;
-}
-
-
 long xdl_mmfile_size(mmfile_t *mmf)
 {
 	return mmf->size;
@@ -130,47 +122,12 @@ 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 xdl_guess_lines(mmfile_t *mf, long sample) {
 	long nl = 0, size, tsize = 0;
 	char const *data, *cur, *top;
 
 	if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
-		for (top = data + size; nl < XDL_GUESS_NLINES;) {
-			if (cur >= top) {
-				tsize += (long) (cur - data);
-				if (!(cur = data = xdl_mmfile_next(mf, &size)))
-					break;
-				top = data + size;
-			}
+		for (top = data + size; nl < sample && cur < top; ) {
 			nl++;
 			if (!(cur = memchr(cur, '\n', top - cur)))
 				cur = top;
@@ -186,73 +143,109 @@ long xdl_guess_lines(mmfile_t *mf) {
 	return nl + 1;
 }
 
+int xdl_blankline(const char *line, long size, long flags)
+{
+	long i;
+
+	if (!(flags & XDF_WHITESPACE_FLAGS))
+		return (size <= 1);
+
+	for (i = 0; i < size && XDL_ISSPACE(line[i]); i++)
+		;
+
+	return (i == size);
+}
+
 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)
 {
 	int i1, i2;
 
+	if (s1 == s2 && !memcmp(l1, l2, s1))
+		return 1;
+	if (!(flags & XDF_WHITESPACE_FLAGS))
+		return 0;
+
+	i1 = 0;
+	i2 = 0;
+
+	/*
+	 * -w matches everything that matches with -b, and -b in turn
+	 * matches everything that matches with --ignore-space-at-eol.
+	 *
+	 * Each flavor of ignoring needs different logic to skip whitespaces
+	 * while we have both sides to compare.
+	 */
 	if (flags & XDF_IGNORE_WHITESPACE) {
-		for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
-			if (isspace(l1[i1]))
-				while (isspace(l1[i1]) && i1 < s1)
-					i1++;
-			if (isspace(l2[i2]))
-				while (isspace(l2[i2]) && i2 < s2)
-					i2++;
-			if (i1 < s1 && i2 < s2 && l1[i1++] != l2[i2++])
+		goto skip_ws;
+		while (i1 < s1 && i2 < s2) {
+			if (l1[i1++] != l2[i2++])
 				return 0;
+		skip_ws:
+			while (i1 < s1 && XDL_ISSPACE(l1[i1]))
+				i1++;
+			while (i2 < s2 && XDL_ISSPACE(l2[i2]))
+				i2++;
 		}
-		return (i1 >= s1 && i2 >= s2);
 	} else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) {
-		for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
-			if (isspace(l1[i1])) {
-				if (!isspace(l2[i2]))
-					return 0;
-				while (isspace(l1[i1]) && i1 < s1)
+		while (i1 < s1 && i2 < s2) {
+			if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) {
+				/* Skip matching spaces and try again */
+				while (i1 < s1 && XDL_ISSPACE(l1[i1]))
 					i1++;
-				while (isspace(l2[i2]) && i2 < s2)
+				while (i2 < s2 && XDL_ISSPACE(l2[i2]))
 					i2++;
-			} else if (l1[i1++] != l2[i2++])
+				continue;
+			}
+			if (l1[i1++] != l2[i2++])
 				return 0;
 		}
-		return (i1 >= s1 && i2 >= s2);
 	} else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) {
-		for (i1 = i2 = 0; i1 < s1 && i2 < s2; ) {
-			if (l1[i1] != l2[i2]) {
-				while (i1 < s1 && isspace(l1[i1]))
-					i1++;
-				while (i2 < s2 && isspace(l2[i2]))
-					i2++;
-				if (i1 < s1 || i2 < s2)
-					return 0;
-				return 1;
-			}
+		while (i1 < s1 && i2 < s2 && l1[i1++] == l2[i2++])
+			; /* keep going */
+	}
+
+	/*
+	 * After running out of one side, the remaining side must have
+	 * nothing but whitespace for the lines to match.  Note that
+	 * ignore-whitespace-at-eol case may break out of the loop
+	 * while there still are characters remaining on both lines.
+	 */
+	if (i1 < s1) {
+		while (i1 < s1 && XDL_ISSPACE(l1[i1]))
 			i1++;
+		if (s1 != i1)
+			return 0;
+	}
+	if (i2 < s2) {
+		while (i2 < s2 && XDL_ISSPACE(l2[i2]))
 			i2++;
-		}
-		return i1 >= s1 && i2 >= s2;
-	} else
-		return s1 == s2 && !memcmp(l1, l2, s1);
-
-	return 0;
+		return (s2 == i2);
+	}
+	return 1;
 }
 
-unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
+static unsigned long xdl_hash_record_with_whitespace(char const **data,
+		char const *top, long flags) {
 	unsigned long ha = 5381;
 	char const *ptr = *data;
 
 	for (; ptr < top && *ptr != '\n'; ptr++) {
-		if (isspace(*ptr) && (flags & XDF_WHITESPACE_FLAGS)) {
+		if (XDL_ISSPACE(*ptr)) {
 			const char *ptr2 = ptr;
-			while (ptr + 1 < top && isspace(ptr[1])
+			int at_eol;
+			while (ptr + 1 < top && XDL_ISSPACE(ptr[1])
 					&& ptr[1] != '\n')
 				ptr++;
-			if (flags & XDF_IGNORE_WHITESPACE_CHANGE
-					&& ptr[1] != '\n') {
+			at_eol = (top <= ptr + 1 || ptr[1] == '\n');
+			if (flags & XDF_IGNORE_WHITESPACE)
+				; /* already handled */
+			else if (flags & XDF_IGNORE_WHITESPACE_CHANGE
+				 && !at_eol) {
 				ha += (ha << 5);
 				ha ^= (unsigned long) ' ';
 			}
-			if (flags & XDF_IGNORE_WHITESPACE_AT_EOL
-					&& ptr[1] != '\n') {
+			else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL
+				 && !at_eol) {
 				while (ptr2 != ptr + 1) {
 					ha += (ha << 5);
 					ha ^= (unsigned long) *ptr2;
@@ -269,6 +262,127 @@ unsigned long xdl_hash_record(char const **data, char const *top, long flags) {
 	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;
+	char const *ptr = *data;
+
+	if (flags & XDF_WHITESPACE_FLAGS)
+		return xdl_hash_record_with_whitespace(data, top, flags);
+
+	for (; ptr < top && *ptr != '\n'; ptr++) {
+		ha += (ha << 5);
+		ha ^= (unsigned long) *ptr;
+	}
+	*data = ptr < top ? ptr + 1: ptr;
+
+	return ha;
+}
+
+#endif /* XDL_FAST_HASH */
 
 unsigned int xdl_hashbits(unsigned int size) {
 	unsigned int val = 1, bits = 0;
@@ -300,20 +414,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;
@@ -363,3 +463,33 @@ int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2,
 	return 0;
 }
 
+int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp,
+		int line1, int count1, int line2, int count2)
+{
+	/*
+	 * This probably does not work outside Git, since
+	 * we have a very simple mmfile structure.
+	 *
+	 * Note: ideally, we would reuse the prepared environment, but
+	 * the libxdiff interface does not (yet) allow for diffing only
+	 * ranges of lines instead of the whole files.
+	 */
+	mmfile_t subfile1, subfile2;
+	xdfenv_t env;
+
+	subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr;
+	subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr +
+		diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
+	subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr;
+	subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr +
+		diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
+	if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0)
+		return -1;
+
+	memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);
+	memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);
+
+	xdl_free_env(&env);
+
+	return 0;
+}