[Courgette] Replace QSufSort with libdivsufsort.

courgette/third_party/bsdiff/bsdiff_create.cc

 // Copyright 2003, 2004 Colin Percival
 // All rights reserved
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted providing that the following conditions
 // are met:
 // 1. Redistributions of source code must retain the above copyright
 //    notice, this list of conditions and the following disclaimer.
 // 2. Redistributions in binary form must reproduce the above copyright
 //    notice, this list of conditions and the following disclaimer in the
@@ skipping 20 matching lines @@
 //                --Benjamin Smedberg <benjamin@smedbergs.us>
 // 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table
 //              provided by libbz2.
 //                --Darin Fisher <darin@meer.net>
 // 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library
 //                --Rahul Kuchhal
 // 2009-03-31 - Change to use Streams.  Added lots of comments.
 //                --Stephen Adams <sra@chromium.org>
 // 2010-05-26 - Use a paged array for V and I. The address space may be too
 //              fragmented for these big arrays to be contiguous.
 //               --Stephen Adams <sra@chromium.org>

[chrisha, 2016/08/02 15:26:00]

Fix indent while you're here?

[huangs, 2016/08/02 18:32:53]

Done.

 // 2015-08-03 - Extract qsufsort portion to a separate file.
 //                --Samuel Huang <huangs@chromium.org>
 // 2015-08-12 - Interface change to search().
 //                --Samuel Huang <huangs@chromium.org>
+// 2016-07-29 - 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
 // found in the LICENSE file.
 
 #include "courgette/third_party/bsdiff/bsdiff.h"
 
 #include <stddef.h>
 #include <stdint.h>
 #include <stdlib.h>
+
 #include <algorithm>
 
 #include "base/logging.h"
 #include "base/strings/string_util.h"
 #include "base/time/time.h"
 
 #include "courgette/crc.h"
 #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 {
 
 using courgette::CalculateCrc;
 using courgette::PagedArray;
 using courgette::SinkStream;
 using courgette::SinkStreamSet;
 using courgette::SourceStream;
 using courgette::SourceStreamSet;
 
@@ skipping 22 matching lines @@
   SinkStream* control_stream_seeks = patch_streams.stream(2);
   SinkStream* diff_skips = patch_streams.stream(3);
   SinkStream* diff_bytes = patch_streams.stream(4);
   SinkStream* extra_bytes = patch_streams.stream(5);
 
   const uint8_t* old = old_stream->Buffer();
   const int oldsize = static_cast<int>(old_stream->Remaining());
 
   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))
                << " bytes";
     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 "
+  divsuf::saint_t result = divsuf::divsufsort_include_empty(
+      old, I.begin(), oldsize);
+  VLOG(1) << " done divsufsort "
           << (base::Time::Now() - q_start_time).InSecondsF();
-  V.clear();
+  if (result != 0)
+    return UNEXPECTED_ERROR;
 
   const uint8_t* newbuf = new_stream->Buffer();
   const int newsize = static_cast<int>(new_stream->Remaining());
 
   int control_length = 0;
   int diff_bytes_length = 0;
   int diff_bytes_nonzero = 0;
   int extra_bytes_length = 0;
 
   // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is
@@ skipping 39 matching lines @@
   int scan = 0;
   SearchResult match(0, 0);
 
   while (scan < newsize) {
     int oldscore = 0;  // Count of how many bytes of the current match at |scan|
                        // extend the match at |lastscan|.
     match.pos = 0;
 
     scan += match.size;
     for (int scsc = scan; scan < newsize; ++scan) {
-      match = search<PagedArray<int>&>(
+      match = search<PagedArray<divsuf::saidx_t>&>(
           I, old, oldsize, newbuf + scan, newsize - scan);
 
       for (; scsc < scan + match.size; scsc++)
         if ((scsc + lastoffset < oldsize) &&
             (old[scsc + lastoffset] == newbuf[scsc]))
           oldscore++;
 
       if ((match.size == oldscore) && (match.size != 0))
         break;  // Good continuing match, case (1)
       if (match.size > oldscore + 8)
@@ skipping 145 matching lines @@
           << "  extra bytes: " << extra_bytes_length
           << "\nUncompressed bsdiff patch size "
           << patch_stream->Length() - initial_patch_stream_length
           << "\nEnd bsdiff "
           << (base::Time::Now() - start_bsdiff_time).InSecondsF();
 
   return OK;
 }
 
 }  // namespace bsdiff