[Courgette] Extract qsufsort module and add tests.

courgette/third_party/qsufsort.h

 /*
-  bsdiff.c -- Binary patch generator.
+  qsufsort.h -- Suffix array generation.
 
   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 - Extrat qsufsort to a separate file as template.
+                 --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 <cstring>
 
 namespace courgette {
+namespace qsuf {
 
 // ------------------------------------------------------------------------
 //
 // 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>&.
+// code formatting and variable names.  The changes from the original are:
+// (1) replacing tabs with spaces,
+// (2) indentation,
+// (3) using 'const',
+// (4) changing the V and I parameters from int* to template <typename T>.
 //
 // 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.
 
+template <typename T>
 static void
-split(PagedArray<int>& I,PagedArray<int>& V,int start,int len,int h)
+split(T I,T 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;
@@ skipping 32 matching lines @@
 
   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);
+  if(jj>start) split<T>(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);
+  if(start+len>kk) split<T>(I,V,kk,start+len-kk,h);
 }
 
+template <class T>
 static void
-qsufsort(PagedArray<int>& I, PagedArray<int>& V,const unsigned char *old,int oldsize)
+qsufsort(T I, T 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);
+        split<T>(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;
 }
 
+template <class T>
 static int
-search(PagedArray<int>& I,const unsigned char *old,int oldsize,
+search(T 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);
+    return search<T>(I,old,oldsize,newbuf,newsize,x,en,pos);
   } else {
-    return search(I,old,oldsize,newbuf,newsize,st,x,pos);
+    return search<T>(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,
-                               SinkStream* patch_stream)
-{
-  base::Time start_bsdiff_time = base::Time::Now();
-  VLOG(1) << "Start bsdiff";
-  size_t initial_patch_stream_length = patch_stream->Length();
-
-  SinkStreamSet patch_streams;
-  SinkStream* control_stream_copy_counts = patch_streams.stream(0);
-  SinkStream* control_stream_extra_counts = patch_streams.stream(1);
-  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* old = old_stream->Buffer();
-  const int oldsize = static_cast<int>(old_stream->Remaining());
-
-  uint32 pending_diff_zeros = 0;
-
-  PagedArray<int> I;
-  PagedArray<int> V;
-
-  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();
-  qsufsort(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;
-  int extra_bytes_length = 0;
-
-  // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is
-  // the number of bytes to copy from the old file (possibly with mistakes),
-  // 'extra' is the number of bytes to copy from a stream of fresh bytes, and
-  // 'seek' is an offset to move to the position to copy for the next triple.
-  //
-  // The invariant at the top of this loop is that we are committed to emitting
-  // a triple for the part of |newbuf| surrounding a 'seed' match near
-  // |lastscan|.  We are searching for a second match that will be the 'seed' of
-  // the next triple.  As we scan through |newbuf|, one of four things can
-  // happen at the current position |scan|:
-  //
-  //  1. We find a nice match that appears to be consistent with the current
-  //     seed.  Continue scanning.  It is likely that this match will become
-  //     part of the 'copy'.
-  //
-  //  2. We find match which does much better than extending the current seed
-  //     old match.  Emit a triple for the current seed and take this match as
-  //     the new seed for a new triple.  By 'much better' we remove 8 mismatched
-  //     bytes by taking the new seed.
-  //
-  //  3. There is not a good match.  Continue scanning.  These bytes will likely
-  //     become part of the 'extra'.
-  //
-  //  4. There is no match because we reached the end of the input, |newbuf|.
-
-  // This is how the loop advances through the bytes of |newbuf|:
-  //
-  // ...012345678901234567890123456789...
-  //    ssssssssss                      Seed at |lastscan|
-  //              xxyyyxxyyxy           |scan| forward, cases (3)(x) & (1)(y)
-  //                         mmmmmmmm   New match will start new seed case (2).
-  //    fffffffffffffff                 |lenf| = scan forward from |lastscan|
-  //                     bbbb           |lenb| = scan back from new seed |scan|.
-  //    ddddddddddddddd                 Emit diff bytes for the 'copy'.
-  //                   xx               Emit extra bytes.
-  //                     ssssssssssss   |lastscan = scan - lenb| is new seed.
-  //                                 x  Cases (1) and (3) ....
-
-
-  int lastscan = 0, lastpos = 0, lastoffset = 0;
-
-  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);
-
-      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)
-
-      if ((scan + lastoffset < oldsize) &&
-          (old[scan + lastoffset] == newbuf[scan]))
-        oldscore--;
-      // Case (3) continues in this loop until we fall out of the loop (4).
-    }
-
-    if ((match_length != oldscore) || (scan == newsize)) {  // Cases (2) and (4)
-      // This next chunk of code finds the boundary between the bytes to be
-      // copied as part of the current triple, and the bytes to be copied as
-      // part of the next triple.  The |lastscan| match is extended forwards as
-      // far as possible provided doing to does not add too many mistakes.  The
-      // |scan| match is extended backwards in a similar way.
-
-      // Extend the current match (if any) backwards.  |lenb| is the maximal
-      // extension for which less than half the byte positions in the extension
-      // are wrong.
-      int lenb = 0;
-      if (scan < newsize) {  // i.e. not case (4); there is a match to extend.
-        int score = 0, Sb = 0;
-        for (int i = 1;  (scan >= lastscan + i) && (pos >= i);  i++) {
-          if (old[pos - i] == newbuf[scan - i]) score++;
-          if (score*2 - i > Sb*2 - lenb) { Sb = score; lenb = i; }
-        }
-      }
-
-      // Extend the lastscan match forward; |lenf| is the maximal extension for
-      // which less than half of the byte positions in entire lastscan match are
-      // wrong.  There is a subtle point here: |lastscan| points to before the
-      // seed match by |lenb| bytes from the previous iteration.  This is why
-      // the loop measures the total number of mistakes in the the match, not
-      // just the from the match.
-      int lenf = 0;
-      {
-        int score = 0, Sf = 0;
-        for (int i = 0;  (lastscan + i < scan) && (lastpos + i < oldsize);  ) {
-          if (old[lastpos + i] == newbuf[lastscan + i]) score++;
-          i++;
-          if (score*2 - i > Sf*2 - lenf) { Sf = score; lenf = i; }
-        }
-      }
-
-      // If the extended scans overlap, pick a position in the overlap region
-      // that maximizes the exact matching bytes.
-      if (lastscan + lenf > scan - lenb) {
-        int overlap = (lastscan + lenf) - (scan - lenb);
-        int score = 0;
-        int Ss = 0, lens = 0;
-        for (int i = 0;  i < overlap;  i++) {
-          if (newbuf[lastscan + lenf - overlap + i] ==
-              old[lastpos + lenf - overlap + i]) score++;
-          if (newbuf[scan - lenb + i] ==  old[pos - lenb + i]) score--;
-          if (score > Ss) { Ss = score; lens = i + 1; }
-        }
-
-        lenf += lens - overlap;
-        lenb -= lens;
-      };
-
-      for (int i = 0;  i < lenf;  i++) {
-        uint8 diff_byte = newbuf[lastscan + i] - old[lastpos + i];
-        if (diff_byte) {
-          ++diff_bytes_nonzero;
-          if (!diff_skips->WriteVarint32(pending_diff_zeros))
-            return MEM_ERROR;
-          pending_diff_zeros = 0;
-          if (!diff_bytes->Write(&diff_byte, 1))
-            return MEM_ERROR;
-        } else {
-          ++pending_diff_zeros;
-        }
-      }
-      int gap = (scan - lenb) - (lastscan + lenf);
-      for (int i = 0;  i < gap;  i++) {
-        if (!extra_bytes->Write(&newbuf[lastscan + lenf + i], 1))
-          return MEM_ERROR;
-      }
-
-      diff_bytes_length += lenf;
-      extra_bytes_length += gap;
-
-      uint32 copy_count = lenf;
-      uint32 extra_count = gap;
-      int32 seek_adjustment = ((pos - lenb) - (lastpos + lenf));
-
-      if (!control_stream_copy_counts->WriteVarint32(copy_count) ||
-          !control_stream_extra_counts->WriteVarint32(extra_count) ||
-          !control_stream_seeks->WriteVarint32Signed(seek_adjustment)) {
-        return MEM_ERROR;
-      }
-
-      ++control_length;
-#ifdef DEBUG_bsmedberg
-      VLOG(1) << StringPrintf("Writing a block:  copy: %-8u extra: %-8u seek: "
-                              "%+-9d", copy_count, extra_count,
-                              seek_adjustment);
-#endif
-
-      lastscan = scan - lenb;   // Include the backward extension in seed.
-      lastpos = pos - lenb;     //  ditto.
-      lastoffset = lastpos - lastscan;
-    }
-  }
-
-  if (!diff_skips->WriteVarint32(pending_diff_zeros))
-    return MEM_ERROR;
-
-  I.clear();
-
-  MBSPatchHeader header;
-  // The string will have a null terminator that we don't use, hence '-1'.
-  static_assert(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header.tag),
-                "MBS_PATCH_HEADER_TAG must match header field size");
-  memcpy(header.tag, MBS_PATCH_HEADER_TAG, sizeof(header.tag));
-  header.slen     = oldsize;
-  header.scrc32   = CalculateCrc(old, oldsize);
-  header.dlen     = newsize;
-
-  if (!WriteHeader(patch_stream, &header))
-    return MEM_ERROR;
-
-  size_t diff_skips_length = diff_skips->Length();
-  if (!patch_streams.CopyTo(patch_stream))
-    return MEM_ERROR;
-
-  VLOG(1) << "Control tuples: " << control_length
-          << "  copy bytes: " << diff_bytes_length
-          << "  mistakes: " << diff_bytes_nonzero
-          << "  (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 qsuf
+}  // namespace courgette