Use an array of pages for the large arrays....

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>
 */
 
 #include "courgette/third_party/bsdiff.h"
 
 #include <stdlib.h>
 #include <algorithm>
 
 #include "base/logging.h"
 #include "base/scoped_ptr.h"
 #include "base/string_util.h"
 #include "base/time.h"
 
 #include "courgette/crc.h"
 #include "courgette/streams.h"
+#include "courgette/third_party/paged_array.h"
 
 namespace courgette {
 
 // ------------------------------------------------------------------------
 //
 // The following code is taken verbatim from 'bsdiff.c'. Please keep all the
-// code formatting and variable names.  The only changes from the original are
-// replacing tabs with spaces, indentation, and using 'const'.
+// 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(int *I,int *V,int start,int len,int h)
+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;
@@ skipping 41 matching lines @@
 
   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(int *I,int *V,const unsigned char *old,int oldsize)
+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;
 
@@ skipping 29 matching lines @@
 {
   int i;
 
   for(i=0;(i<oldsize)&&(i<newsize);i++)
     if(old[i]!=newbuf[i]) break;
 
   return i;
 }
 
 static int
-search(int *I,const unsigned char *old,int oldsize,
+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];
@@ skipping 36 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* old = old_stream->Buffer();
   const int oldsize = old_stream->Remaining();
 
   uint32 pending_diff_zeros = 0;
 
-  scoped_array<int> I(new(std::nothrow) int[oldsize + 1]);
-  scoped_array<int> V(new(std::nothrow) int[oldsize + 1]);
-  if (I == NULL || V == NULL)
+  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.get(), V.get(), old, oldsize);
+  qsufsort(I, V, old, oldsize);
   LOG(INFO) << " done qsufsort "
             << (base::Time::Now() - q_start_time).InSecondsF();
-  V.reset();
+  V.clear();
 
   const uint8* newbuf = new_stream->Buffer();
   const int newsize = 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 40 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.get(), old, oldsize,
+      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)
@@ skipping 91 matching lines @@
 #endif
 
       lastscan = scan - lenb;   // Include the backward extension in seed.
       lastpos = pos - lenb;     //  ditto.
       lastoffset = lastpos - lastscan;
     }
   }
 
   diff_skips->WriteVarint32(pending_diff_zeros);
 
-  I.reset();
+  I.clear();
 
   MBSPatchHeader header;
   // The string will have a null terminator that we don't use, hence '-1'.
   COMPILE_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;
 
@@ skipping 11 matching lines @@
   LOG(INFO) << "Uncompressed bsdiff patch size "
             << patch_stream->Length() - initial_patch_stream_length;
 
   LOG(INFO) << "End bsdiff "
             << (base::Time::Now() - start_bsdiff_time).InSecondsF();
 
   return OK;
 }
 
 }  // namespace