[Courgette] Extract qsufsort module and add tests.

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>
 */
 
 #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"
 #include "base/time/time.h"
 
 #include "courgette/crc.h"
 #include "courgette/streams.h"
 #include "courgette/third_party/paged_array.h"
+#include "courgette/third_party/qsufsort.h"
 
 namespace courgette {
 
-// ------------------------------------------------------------------------
-//
-// The following code is taken verbatim from 'bsdiff.c'. Please keep all the
-// code formatting and variable names.  The changes from the original are (1)
-// replacing tabs with spaces, (2) indentation, (3) using 'const', and (4)
-// changing the V and I parameters from int* to PagedArray<int>&.
-//
-// The code appears to be a rewritten version of the suffix array algorithm
-// presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko
-// Sadakane, special cased for bytes.
-
-static void
-split(PagedArray<int>& I,PagedArray<int>& V,int start,int len,int h)
-{
-  int i,j,k,x,tmp,jj,kk;
-
-  if(len<16) {
-    for(k=start;k<start+len;k+=j) {
-      j=1;x=V[I[k]+h];
-      for(i=1;k+i<start+len;i++) {
-        if(V[I[k+i]+h]<x) {
-          x=V[I[k+i]+h];
-          j=0;
-        };
-        if(V[I[k+i]+h]==x) {
-          tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
-          j++;
-        };
-      };
-      for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
-      if(j==1) I[k]=-1;
-    };
-    return;
-  };
-
-  x=V[I[start+len/2]+h];
-  jj=0;kk=0;
-  for(i=start;i<start+len;i++) {
-    if(V[I[i]+h]<x) jj++;
-    if(V[I[i]+h]==x) kk++;
-  };
-  jj+=start;kk+=jj;
-
-  i=start;j=0;k=0;
-  while(i<jj) {
-    if(V[I[i]+h]<x) {
-      i++;
-    } else if(V[I[i]+h]==x) {
-      tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
-      j++;
-    } else {
-      tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
-      k++;
-    };
-  };
-
-  while(jj+j<kk) {
-    if(V[I[jj+j]+h]==x) {
-      j++;
-    } else {
-      tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
-      k++;
-    };
-  };
-
-  if(jj>start) split(I,V,start,jj-start,h);
-
-  for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
-  if(jj==kk-1) I[jj]=-1;
-
-  if(start+len>kk) split(I,V,kk,start+len-kk,h);
-}
-
-static void
-qsufsort(PagedArray<int>& I, PagedArray<int>& V,const unsigned char *old,int oldsize)
-{
-  int buckets[256];
-  int i,h,len;
-
-  for(i=0;i<256;i++) buckets[i]=0;
-  for(i=0;i<oldsize;i++) buckets[old[i]]++;
-  for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
-  for(i=255;i>0;i--) buckets[i]=buckets[i-1];
-  buckets[0]=0;
-
-  for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
-  I[0]=oldsize;
-  for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
-  V[oldsize]=0;
-  for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
-  I[0]=-1;
-
-  for(h=1;I[0]!=-(oldsize+1);h+=h) {
-    len=0;
-    for(i=0;i<oldsize+1;) {
-      if(I[i]<0) {
-        len-=I[i];
-        i-=I[i];
-      } else {
-        if(len) I[i-len]=-len;
-        len=V[I[i]]+1-i;
-        split(I,V,i,len,h);
-        i+=len;
-        len=0;
-      };
-    };
-    if(len) I[i-len]=-len;
-  };
-
-  for(i=0;i<oldsize+1;i++) I[V[i]]=i;
-}
-
-static int
-matchlen(const unsigned char *old,int oldsize,const unsigned char *newbuf,int newsize)
-{
-  int i;
-
-  for(i=0;(i<oldsize)&&(i<newsize);i++)
-    if(old[i]!=newbuf[i]) break;
-
-  return i;
-}
-
-static int
-search(PagedArray<int>& I,const unsigned char *old,int oldsize,
-       const unsigned char *newbuf,int newsize,int st,int en,int *pos)
-{
-  int x,y;
-
-  if(en-st<2) {
-    x=matchlen(old+I[st],oldsize-I[st],newbuf,newsize);
-    y=matchlen(old+I[en],oldsize-I[en],newbuf,newsize);
-
-    if(x>y) {
-      *pos=I[st];
-      return x;
-    } else {
-      *pos=I[en];
-      return y;
-    }
-  }
-
-  x=st+(en-st)/2;
-  if(memcmp(old+I[x],newbuf,std::min(oldsize-I[x],newsize))<0) {
-    return search(I,old,oldsize,newbuf,newsize,x,en,pos);
-  } else {
-    return search(I,old,oldsize,newbuf,newsize,st,x,pos);
-  }
-}
-
-//  End of 'verbatim' code.
-// ------------------------------------------------------------------------
-
 static CheckBool WriteHeader(SinkStream* stream, MBSPatchHeader* header) {
   bool ok = stream->Write(header->tag, sizeof(header->tag));
   ok &= stream->WriteVarint32(header->slen);
   ok &= stream->WriteVarint32(header->scrc32);
   ok &= stream->WriteVarint32(header->dlen);
   return ok;
 }
 
 BSDiffStatus CreateBinaryPatch(SourceStream* old_stream,
                                SourceStream* new_stream,
@@ skipping 25 matching lines @@
     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();
-  qsufsort(I, V, old, oldsize);
+  qsuf::qsufsort<PagedArray<int>&>(I, V, old, oldsize);
   VLOG(1) << " done qsufsort "
           << (base::Time::Now() - q_start_time).InSecondsF();
   V.clear();
 
   const uint8* 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;
@@ skipping 43 matching lines @@
   int scan = 0;
   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 = search(I, old, oldsize,
-                            newbuf + scan, newsize - scan,
-                            0, oldsize, &pos);
+      match_length = qsuf::search<PagedArray<int>&>(
+          I, old, oldsize, newbuf + scan, newsize - scan, 0, oldsize, &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 128 matching lines @@
           << "  (skips: " << diff_skips_length << ")"
           << "  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
+}  // namespace courgette