| /* |
| 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/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" |
| |
| 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, |
| 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 |
