15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bsdiff.c -- Binary patch generator. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Copyright 2003 Colin Percival 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) For the terms under which this work may be distributed, please see 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) the adjoining file "LICENSE". 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ChangeLog: 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) values throughout. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --Benjamin Smedberg <benjamin@smedbergs.us> 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) provided by libbz2. 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --Darin Fisher <darin@meer.net> 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2007-11-14 - Changed to use Crc from Lzma library instead of Bzip library 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --Rahul Kuchhal 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2009-03-31 - Change to use Streams. Added lots of comments. 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --Stephen Adams <sra@chromium.org> 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2010-05-26 - Use a paged array for V and I. The address space may be too 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fragmented for these big arrays to be contiguous. 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --Stephen Adams <sra@chromium.org> 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "courgette/third_party/bsdiff.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdlib.h> 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/memory/scoped_ptr.h" 325e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)#include "base/strings/string_util.h" 33eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "base/time/time.h" 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "courgette/crc.h" 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "courgette/streams.h" 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "courgette/third_party/paged_array.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace courgette { 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ------------------------------------------------------------------------ 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The following code is taken verbatim from 'bsdiff.c'. Please keep all the 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// code formatting and variable names. The changes from the original are (1) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// replacing tabs with spaces, (2) indentation, (3) using 'const', and (4) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// changing the V and I parameters from int* to PagedArray<int>&. 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The code appears to be a rewritten version of the suffix array algorithm 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sadakane, special cased for bytes. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)split(PagedArray<int>& I,PagedArray<int>& V,int start,int len,int h) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i,j,k,x,tmp,jj,kk; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(len<16) { 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(k=start;k<start+len;k+=j) { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) j=1;x=V[I[k]+h]; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=1;k+i<start+len;i++) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(V[I[k+i]+h]<x) { 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x=V[I[k+i]+h]; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) j=0; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(V[I[k+i]+h]==x) { 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) j++; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<j;i++) V[I[k+i]]=k+j-1; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(j==1) I[k]=-1; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x=V[I[start+len/2]+h]; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) jj=0;kk=0; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=start;i<start+len;i++) { 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(V[I[i]+h]<x) jj++; 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(V[I[i]+h]==x) kk++; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) jj+=start;kk+=jj; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i=start;j=0;k=0; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while(i<jj) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(V[I[i]+h]<x) { 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i++; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if(V[I[i]+h]==x) { 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) j++; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k++; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while(jj+j<kk) { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(V[I[jj+j]+h]==x) { 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) j++; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k++; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(jj>start) split(I,V,start,jj-start,h); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(jj==kk-1) I[jj]=-1; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(start+len>kk) split(I,V,kk,start+len-kk,h); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)qsufsort(PagedArray<int>& I, PagedArray<int>& V,const unsigned char *old,int oldsize) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int buckets[256]; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i,h,len; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<256;i++) buckets[i]=0; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<oldsize;i++) buckets[old[i]]++; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=1;i<256;i++) buckets[i]+=buckets[i-1]; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=255;i>0;i--) buckets[i]=buckets[i-1]; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buckets[0]=0; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i; 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I[0]=oldsize; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<oldsize;i++) V[i]=buckets[old[i]]; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) V[oldsize]=0; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I[0]=-1; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(h=1;I[0]!=-(oldsize+1);h+=h) { 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) len=0; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<oldsize+1;) { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(I[i]<0) { 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) len-=I[i]; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i-=I[i]; 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(len) I[i-len]=-len; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) len=V[I[i]]+1-i; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) split(I,V,i,len,h); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i+=len; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) len=0; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(len) I[i-len]=-len; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;i<oldsize+1;i++) I[V[i]]=i; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)matchlen(const unsigned char *old,int oldsize,const unsigned char *newbuf,int newsize) 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0;(i<oldsize)&&(i<newsize);i++) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(old[i]!=newbuf[i]) break; 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return i; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)search(PagedArray<int>& I,const unsigned char *old,int oldsize, 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const unsigned char *newbuf,int newsize,int st,int en,int *pos) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int x,y; 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(en-st<2) { 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x=matchlen(old+I[st],oldsize-I[st],newbuf,newsize); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) y=matchlen(old+I[en],oldsize-I[en],newbuf,newsize); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(x>y) { 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *pos=I[st]; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return x; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *pos=I[en]; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return y; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x=st+(en-st)/2; 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if(memcmp(old+I[x],newbuf,std::min(oldsize-I[x],newsize))<0) { 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return search(I,old,oldsize,newbuf,newsize,x,en,pos); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return search(I,old,oldsize,newbuf,newsize,st,x,pos); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// End of 'verbatim' code. 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ------------------------------------------------------------------------ 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static CheckBool WriteHeader(SinkStream* stream, MBSPatchHeader* header) { 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool ok = stream->Write(header->tag, sizeof(header->tag)); 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok &= stream->WriteVarint32(header->slen); 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok &= stream->WriteVarint32(header->scrc32); 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ok &= stream->WriteVarint32(header->dlen); 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ok; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BSDiffStatus CreateBinaryPatch(SourceStream* old_stream, 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SourceStream* new_stream, 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* patch_stream) 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles){ 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::Time start_bsdiff_time = base::Time::Now(); 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VLOG(1) << "Start bsdiff"; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t initial_patch_stream_length = patch_stream->Length(); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStreamSet patch_streams; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* control_stream_copy_counts = patch_streams.stream(0); 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* control_stream_extra_counts = patch_streams.stream(1); 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* control_stream_seeks = patch_streams.stream(2); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* diff_skips = patch_streams.stream(3); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* diff_bytes = patch_streams.stream(4); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* extra_bytes = patch_streams.stream(5); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8* old = old_stream->Buffer(); 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int oldsize = static_cast<int>(old_stream->Remaining()); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 pending_diff_zeros = 0; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PagedArray<int> I; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PagedArray<int> V; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!I.Allocate(oldsize + 1)) { 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(ERROR) << "Could not allocate I[], " << ((oldsize + 1) * sizeof(int)) 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << " bytes"; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!V.Allocate(oldsize + 1)) { 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(ERROR) << "Could not allocate V[], " << ((oldsize + 1) * sizeof(int)) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << " bytes"; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::Time q_start_time = base::Time::Now(); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) qsufsort(I, V, old, oldsize); 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VLOG(1) << " done qsufsort " 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << (base::Time::Now() - q_start_time).InSecondsF(); 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) V.clear(); 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8* newbuf = new_stream->Buffer(); 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int newsize = static_cast<int>(new_stream->Remaining()); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int control_length = 0; 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int diff_bytes_length = 0; 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int diff_bytes_nonzero = 0; 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int extra_bytes_length = 0; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the number of bytes to copy from the old file (possibly with mistakes), 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 'extra' is the number of bytes to copy from a stream of fresh bytes, and 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 'seek' is an offset to move to the position to copy for the next triple. 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The invariant at the top of this loop is that we are committed to emitting 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a triple for the part of |newbuf| surrounding a 'seed' match near 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |lastscan|. We are searching for a second match that will be the 'seed' of 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the next triple. As we scan through |newbuf|, one of four things can 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // happen at the current position |scan|: 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1. We find a nice match that appears to be consistent with the current 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // seed. Continue scanning. It is likely that this match will become 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // part of the 'copy'. 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2. We find match which does much better than extending the current seed 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // old match. Emit a triple for the current seed and take this match as 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the new seed for a new triple. By 'much better' we remove 8 mismatched 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bytes by taking the new seed. 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 3. There is not a good match. Continue scanning. These bytes will likely 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // become part of the 'extra'. 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 4. There is no match because we reached the end of the input, |newbuf|. 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is how the loop advances through the bytes of |newbuf|: 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ...012345678901234567890123456789... 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ssssssssss Seed at |lastscan| 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // xxyyyxxyyxy |scan| forward, cases (3)(x) & (1)(y) 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // mmmmmmmm New match will start new seed case (2). 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // fffffffffffffff |lenf| = scan forward from |lastscan| 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bbbb |lenb| = scan back from new seed |scan|. 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ddddddddddddddd Emit diff bytes for the 'copy'. 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // xx Emit extra bytes. 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ssssssssssss |lastscan = scan - lenb| is new seed. 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // x Cases (1) and (3) .... 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int lastscan = 0, lastpos = 0, lastoffset = 0; 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int scan = 0; 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int match_length = 0; 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (scan < newsize) { 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int pos = 0; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int oldscore = 0; // Count of how many bytes of the current match at |scan| 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // extend the match at |lastscan|. 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scan += match_length; 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int scsc = scan; scan < newsize; ++scan) { 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) match_length = search(I, old, oldsize, 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) newbuf + scan, newsize - scan, 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0, oldsize, &pos); 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for ( ; scsc < scan + match_length ; scsc++) 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((scsc + lastoffset < oldsize) && 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (old[scsc + lastoffset] == newbuf[scsc])) 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) oldscore++; 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((match_length == oldscore) && (match_length != 0)) 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; // Good continuing match, case (1) 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (match_length > oldscore + 8) 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; // New seed match, case (2) 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((scan + lastoffset < oldsize) && 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (old[scan + lastoffset] == newbuf[scan])) 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) oldscore--; 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Case (3) continues in this loop until we fall out of the loop (4). 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((match_length != oldscore) || (scan == newsize)) { // Cases (2) and (4) 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This next chunk of code finds the boundary between the bytes to be 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // copied as part of the current triple, and the bytes to be copied as 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // part of the next triple. The |lastscan| match is extended forwards as 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // far as possible provided doing to does not add too many mistakes. The 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |scan| match is extended backwards in a similar way. 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Extend the current match (if any) backwards. |lenb| is the maximal 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // extension for which less than half the byte positions in the extension 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // are wrong. 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int lenb = 0; 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (scan < newsize) { // i.e. not case (4); there is a match to extend. 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int score = 0, Sb = 0; 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; (scan >= lastscan + i) && (pos >= i); i++) { 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (old[pos - i] == newbuf[scan - i]) score++; 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (score*2 - i > Sb*2 - lenb) { Sb = score; lenb = i; } 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Extend the lastscan match forward; |lenf| is the maximal extension for 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // which less than half of the byte positions in entire lastscan match are 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // wrong. There is a subtle point here: |lastscan| points to before the 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // seed match by |lenb| bytes from the previous iteration. This is why 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the loop measures the total number of mistakes in the the match, not 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // just the from the match. 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int lenf = 0; 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int score = 0, Sf = 0; 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; (lastscan + i < scan) && (lastpos + i < oldsize); ) { 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (old[lastpos + i] == newbuf[lastscan + i]) score++; 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i++; 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (score*2 - i > Sf*2 - lenf) { Sf = score; lenf = i; } 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the extended scans overlap, pick a position in the overlap region 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that maximizes the exact matching bytes. 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (lastscan + lenf > scan - lenb) { 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int overlap = (lastscan + lenf) - (scan - lenb); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int score = 0; 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int Ss = 0, lens = 0; 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < overlap; i++) { 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (newbuf[lastscan + lenf - overlap + i] == 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) old[lastpos + lenf - overlap + i]) score++; 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (newbuf[scan - lenb + i] == old[pos - lenb + i]) score--; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (score > Ss) { Ss = score; lens = i + 1; } 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lenf += lens - overlap; 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lenb -= lens; 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < lenf; i++) { 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8 diff_byte = newbuf[lastscan + i] - old[lastpos + i]; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (diff_byte) { 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++diff_bytes_nonzero; 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!diff_skips->WriteVarint32(pending_diff_zeros)) 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pending_diff_zeros = 0; 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!diff_bytes->Write(&diff_byte, 1)) 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++pending_diff_zeros; 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int gap = (scan - lenb) - (lastscan + lenf); 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < gap; i++) { 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!extra_bytes->Write(&newbuf[lastscan + lenf + i], 1)) 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) diff_bytes_length += lenf; 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) extra_bytes_length += gap; 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 copy_count = lenf; 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 extra_count = gap; 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 seek_adjustment = ((pos - lenb) - (lastpos + lenf)); 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!control_stream_copy_counts->WriteVarint32(copy_count) || 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !control_stream_extra_counts->WriteVarint32(extra_count) || 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) !control_stream_seeks->WriteVarint32Signed(seek_adjustment)) { 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++control_length; 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef DEBUG_bsmedberg 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VLOG(1) << StringPrintf("Writing a block: copy: %-8u extra: %-8u seek: " 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "%+-9d", copy_count, extra_count, 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seek_adjustment); 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lastscan = scan - lenb; // Include the backward extension in seed. 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lastpos = pos - lenb; // ditto. 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lastoffset = lastpos - lastscan; 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!diff_skips->WriteVarint32(pending_diff_zeros)) 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I.clear(); 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBSPatchHeader header; 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The string will have a null terminator that we don't use, hence '-1'. 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(sizeof(MBS_PATCH_HEADER_TAG) - 1 == sizeof(header.tag), 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MBS_PATCH_HEADER_TAG_must_match_header_field_size); 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(header.tag, MBS_PATCH_HEADER_TAG, sizeof(header.tag)); 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header.slen = oldsize; 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header.scrc32 = CalculateCrc(old, oldsize); 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) header.dlen = newsize; 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!WriteHeader(patch_stream, &header)) 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t diff_skips_length = diff_skips->Length(); 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!patch_streams.CopyTo(patch_stream)) 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return MEM_ERROR; 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VLOG(1) << "Control tuples: " << control_length 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << " copy bytes: " << diff_bytes_length 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << " mistakes: " << diff_bytes_nonzero 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << " (skips: " << diff_skips_length << ")" 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << " extra bytes: " << extra_bytes_length 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << "\nUncompressed bsdiff patch size " 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << patch_stream->Length() - initial_patch_stream_length 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << "\nEnd bsdiff " 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << (base::Time::Now() - start_bsdiff_time).InSecondsF(); 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return OK; 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 455