diff --git a/mercurial/bdiff.c b/mercurial/bdiff.c
--- a/mercurial/bdiff.c
+++ b/mercurial/bdiff.c
@@ -103,14 +103,14 @@ static int equatelines(struct line *a, i
 
 	/* clear the hash table */
 	for (i = 0; i <= buckets; i++) {
-		h[i].pos = INT_MAX;
+		h[i].pos = -1;
 		h[i].len = 0;
 	}
 
 	/* add lines to the hash table chains */
-	for (i = bn - 1; i >= 0; i--) {
+	for (i = 0; i < bn; i++) {
 		/* find the equivalence class */
-		for (j = b[i].hash & buckets; h[j].pos != INT_MAX;
+		for (j = b[i].hash & buckets; h[j].pos != -1;
 		     j = (j + 1) & buckets)
 			if (!cmp(b + i, b + h[j].pos))
 				break;
@@ -128,7 +128,7 @@ static int equatelines(struct line *a, i
 	/* match items in a to their equivalence class in b */
 	for (i = 0; i < an; i++) {
 		/* find the equivalence class */
-		for (j = a[i].hash & buckets; h[j].pos != INT_MAX;
+		for (j = a[i].hash & buckets; h[j].pos != -1;
 		     j = (j + 1) & buckets)
 			if (!cmp(a + i, b + h[j].pos))
 				break;
@@ -137,7 +137,7 @@ static int equatelines(struct line *a, i
 		if (h[j].len <= t)
 			a[i].n = h[j].pos; /* point to head of match list */
 		else
-			a[i].n = INT_MAX; /* too popular */
+			a[i].n = -1; /* too popular */
 	}
 
 	/* discard hash tables */
@@ -151,12 +151,12 @@ static int longest_match(struct line *a,
 	int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k;
 
 	for (i = a1; i < a2; i++) {
-		/* skip things before the current block */
-		for (j = a[i].n; j < b1; j = b[j].n)
+		/* skip all lines in b after the current block */
+		for (j = a[i].n; j >= b2; j = b[j].n)
 			;
 
 		/* loop through all lines match a[i] in b */
-		for (; j < b2; j = b[j].n) {
+		for (; j >= b1; j = b[j].n) {
 			/* does this extend an earlier match? */
 			if (i > a1 && j > b1 && pos[j - 1].pos == i - 1)
 				k = pos[j - 1].len + 1;
@@ -166,7 +166,7 @@ static int longest_match(struct line *a,
 			pos[j].len = k;
 
 			/* best match so far? */
-			if (k > mk) {
+			if (k > mk || (k == mk && i <= mi)) {
 				mi = i;
 				mj = j;
 				mk = k;
diff --git a/tests/test-bdiff.py b/tests/test-bdiff.py
--- a/tests/test-bdiff.py
+++ b/tests/test-bdiff.py
@@ -52,6 +52,9 @@ def showdiff(a, b):
         pos += l
 showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n")
 showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n")
+# we should pick up abbbc. rather than bc.de as the longest match
+showdiff("a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n",
+         "a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n")
 
 print("done")
 
diff --git a/tests/test-bdiff.py.out b/tests/test-bdiff.py.out
--- a/tests/test-bdiff.py.out
+++ b/tests/test-bdiff.py.out
@@ -20,5 +20,8 @@
 6 6 'y\n\n'
 6 6 'y\n\n'
 9 9 'y\n\n'
+0 0 'a\nb\nb\n'
+12 12 'b\nc\n.\n'
+16 18 ''
 done
 done