Fix segmentation fault with certain files.

The bug was introduced when we replaced qsufsort with divsufsort, the
implementation of qsufsort in bsdiff will set I[oldsize] for some reason,
and later on search() might access I[oldsize] in a corner case. But
divsufsort will only set I[0...oldsize-1] which is WAI, and now I[oldsize]
will be random.

The search() function is basically a binary search, and the end should
be oldsize-1 so that it will never access I[oldsize].

Interestingly, it will only segfault when used in imgdiff, even if I
extract the same old data and new data passed to bsdiff() and call bsdiff
binary with the files, segfault disappears, probably because imgdiff did
many malloc and free before calling bsdiff and the memory already contains
random data, whereas in bsdiff binary that is always 0. That's probably
why we did not encounter this bug in Chrome OS.

Bug: 28631841
Test: `imgdiff boot.img recovery.img recovery_from_boot.p` from shamu build

Change-Id: If10ec64b125131b348444364626307d379c2b8ba
diff --git a/ b/
index abfb6d1..669a1e5 100644
--- a/
+++ b/
@@ -62,6 +62,11 @@
 	return i;
+// This is a binary search of the string |new_buf| of size |newsize| (or a
+// prefix of it) in the |old| string with size |oldsize| using the suffix array
+// |I|. |st| and |en| is the start and end of the search range (inclusive).
+// Returns the length of the longest prefix found and stores the position of the
+// string found in |*pos|.
 static off_t search(saidx_t* I, const u_char* old, off_t oldsize,
                     const u_char* new_buf, off_t newsize, off_t st, off_t en,
                     off_t* pos) {
@@ -206,7 +211,7 @@
-					0,oldsize,&pos);
+					0,oldsize-1,&pos);
 			if((scsc+lastoffset<oldsize) &&