[Courgette Experimental] Replace QSufSort with libdivsufsort

courgette/third_party/bsdiff/bsdiff_create.cc

Index: courgette/third_party/bsdiff/bsdiff_create.cc
diff --git a/courgette/third_party/bsdiff/bsdiff_create.cc b/courgette/third_party/bsdiff/bsdiff_create.cc
index b89c2f1a57a997fef35fdf1d881c9b4a7e29aa94..3f2698eb1309da9158f32f1c9ac24adb91a67ea1 100644
--- a/courgette/third_party/bsdiff/bsdiff_create.cc
+++ b/courgette/third_party/bsdiff/bsdiff_create.cc
@@ -43,6 +43,9 @@
 //                --Samuel Huang <huangs@chromium.org>
 // 2015-08-12 - Interface change to search().
 //                --Samuel Huang <huangs@chromium.org>
+// 2016-07-14 - Replacing qsufsort with divsufsort.
+//                --Samuel Huang <huangs@chromium.org>
+
 
 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
@@ -53,6 +56,7 @@
 #include <stddef.h>
 #include <stdint.h>
 #include <stdlib.h>
+
 #include <algorithm>
 
 #include "base/logging.h"
@@ -63,7 +67,7 @@
 #include "courgette/streams.h"
 #include "courgette/third_party/bsdiff/bsdiff_search.h"
 #include "courgette/third_party/bsdiff/paged_array.h"
-#include "courgette/third_party/bsdiff/qsufsort.h"
+#include "courgette/third_party/divsufsort/divsufsort.h"
 
 namespace courgette {
 
@@ -95,8 +99,7 @@ BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
 
   uint32_t pending_diff_zeros = 0;
 
-  PagedArray<int> I;
-  PagedArray<int> V;
+  PagedArray<divsuf::saidx_t> I;
 
   if (!I.Allocate(oldsize + 1)) {
     LOG(ERROR) << "Could not allocate I[], " << ((oldsize + 1) * sizeof(int))
@@ -104,17 +107,13 @@ BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
     return MEM_ERROR;
   }
 
-  if (!V.Allocate(oldsize + 1)) {
-    LOG(ERROR) << "Could not allocate V[], " << ((oldsize + 1) * sizeof(int))
-               << " bytes";
-    return MEM_ERROR;
-  }
-
   base::Time q_start_time = base::Time::Now();
-  qsuf::qsufsort<PagedArray<int>&>(I, V, old, oldsize);
-  VLOG(1) << " done qsufsort "
-          << (base::Time::Now() - q_start_time).InSecondsF();
-  V.clear();
+
+  // Divsufsort excludes the empty-string suffix, so add it manually.
+  I[0] = oldsize;
+  divsuf::saint_t result = divsuf::divsufsort(old, I.begin() + 1, oldsize);
+  if (result != 0)
+    return UNEXPECTED_ERROR;
 
   const uint8_t* newbuf = new_stream->Buffer();
   const int newsize = static_cast<int>(new_stream->Remaining());
@@ -174,9 +173,8 @@ BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
 
     scan += match_length;
     for (int scsc = scan; scan < newsize; ++scan) {
-      match_length = courgette::search<PagedArray<int>&>(
+      match_length = bsdiff::search<PagedArray<divsuf::saidx_t>&>(
           I, old, oldsize, newbuf + scan, newsize - scan, &pos);
-
       for (; scsc < scan + match_length; scsc++)
         if ((scsc + lastoffset < oldsize) &&
             (old[scsc + lastoffset] == newbuf[scsc]))