[Courgette] Optimize QSufSort to speed up courgette-gen.

courgette/third_party/bsdiff_create.cc

 /*
   bsdiff.c -- Binary patch generator.
 
   Copyright 2003 Colin Percival
 
   For the terms under which this work may be distributed, please see
   the adjoining file "LICENSE".
 
   ChangeLog:
   2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit
                values throughout.
                  --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>
   2015-08-03 - Extract qsufsort portion to a separate file.
                  --Samuel Huang <huangs@chromium.org>
+  2015-08-12 - Interface change to qsufsort search().
+                 --Samuel Huang <huangs@chromium.org>
 */
 
 #include "courgette/third_party/bsdiff.h"
 
 #include <stdlib.h>
 #include <algorithm>
 
 #include "base/logging.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/strings/string_util.h"
@@ skipping 109 matching lines @@
   int match_length = 0;
 
   while (scan < newsize) {
     int pos = 0;
     int oldscore = 0;  // Count of how many bytes of the current match at |scan|
                        // extend the match at |lastscan|.
 
     scan += match_length;
     for (int scsc = scan;  scan < newsize;  ++scan) {
       match_length = qsuf::search<PagedArray<int>&>(
-          I, old, oldsize, newbuf + scan, newsize - scan, 0, oldsize, &pos);
+          I, old, oldsize, newbuf + scan, newsize - scan, &pos);
 
       for ( ; scsc < scan + match_length ; scsc++)
         if ((scsc + lastoffset < oldsize) &&
             (old[scsc + lastoffset] == newbuf[scsc]))
           oldscore++;
 
       if ((match_length == oldscore) && (match_length != 0))
         break;  // Good continuing match, case (1)
       if (match_length > oldscore + 8)
         break;  // New seed match, case (2)
@@ skipping 129 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 courgette