/*- * Copyright 2003-2005 Colin Percival * All rights reserved * * Redistribution and use in source and binary forms, with or without * modification, are permitted providing that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #if 0 __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c,v 1.1 2005/08/06 01:59:05 cperciva Exp $"); #endif #include #include #include #include #include #include #include #include #include #include #ifdef USE_OFF_T #define t_off off_t #define t_off_max LLONG_MAX #else #define t_off int32_t #define t_off_max INT_MAX #endif #define MIN(x,y) (((x)<(y)) ? (x) : (y)) static void split(t_off *I,t_off *V,t_off start,t_off len,t_off h) { t_off i,j,k,x,tmp,jj,kk; if(len<16) { for(k=start;kstart) split(I,V,start,jj-start,h); for(i=0;ikk) split(I,V,kk,start+len-kk,h); } static void qsufsort(t_off *I,t_off *V,u_char *old,t_off oldsize) { t_off buckets[256]; t_off i,h,len; for(i=0;i<256;i++) buckets[i]=0; for(i=0;i0;i--) buckets[i]=buckets[i-1]; buckets[0]=0; for(i=0;iy) { *pos=I[st]; return x; } else { *pos=I[en]; return y; } }; x=st+(en-st)/2; if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) { return search(I,old,oldsize,new,newsize,x,en,pos); } else { return search(I,old,oldsize,new,newsize,st,x,pos); }; } static void offtout(t_off x,u_char *buf) { t_off y; if(x<0) y=-x; else y=x; buf[0]=y%256;y-=buf[0]; y=y/256;buf[1]=y%256;y-=buf[1]; y=y/256;buf[2]=y%256;y-=buf[2]; y=y/256;buf[3]=y%256;y-=buf[3]; y=y/256;buf[4]=y%256;y-=buf[4]; y=y/256;buf[5]=y%256;y-=buf[5]; y=y/256;buf[6]=y%256;y-=buf[6]; y=y/256;buf[7]=y%256; if(x<0) buf[7]|=0x80; } int main(int argc,char *argv[]) { int fd; u_char *old,*new; off_t oldsize,newsize; t_off *I,*V; t_off scan,pos,len; t_off lastscan,lastpos,lastoffset; t_off oldscore,scsc; t_off s,Sf,lenf,Sb,lenb; t_off overlap,Ss,lens; t_off i; t_off dblen,eblen; u_char *db,*eb; u_char buf[8]; u_char header[32]; FILE * pf; BZFILE * pfbz2; int bz2err; if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]); fd = open(argv[1], O_RDONLY,0); if (fd < 0) err(1, "Open %s", argv[1]); oldsize = lseek(fd, 0, SEEK_END); if (oldsize < 0) err(1, "seek %s", argv[1]); if (oldsize > t_off_max) err(1, "file too large %s", argv[1]); old = mmap(NULL, oldsize, PROT_READ, MAP_SHARED | MAP_POPULATE, fd, 0); if (old == MAP_FAILED) err(1, "mmap() %s", argv[1]); close(fd); if(((I=malloc((oldsize+1)*sizeof(t_off)))==NULL) || ((V=malloc((oldsize+1)*sizeof(t_off)))==NULL)) err(1,NULL); qsufsort(I,V,old,oldsize); free(V); /* Allocate newsize+1 bytes instead of newsize bytes to ensure that we never try to malloc(0) and get a NULL pointer */ fd = open(argv[2], O_RDONLY, 0); if (fd < 0) err(1, "open %s", argv[2]); newsize = lseek(fd, 0, SEEK_END); if (newsize == -1) err(1, "lseek %s", argv[2]); if (newsize > t_off_max) err(1, "file too large %s", argv[2]); new = mmap(NULL, newsize, PROT_READ, MAP_SHARED | MAP_POPULATE, fd, 0); if (new == MAP_FAILED) err(1, "mmap %s", argv[2]); close(fd); if(((db=malloc(newsize+1))==NULL) || ((eb=malloc(newsize+1))==NULL)) err(1,NULL); dblen=0; eblen=0; /* Create the patch file */ if ((pf = fopen(argv[3], "w")) == NULL) err(1, "%s", argv[3]); /* Header is 0 8 "BSDIFF40" 8 8 length of bzip2ed ctrl block 16 8 length of bzip2ed diff block 24 8 length of new file */ /* File is 0 32 Header 32 ?? Bzip2ed ctrl block ?? ?? Bzip2ed diff block ?? ?? Bzip2ed extra block */ memcpy(header,"BSDIFF40",8); offtout(0, header + 8); offtout(0, header + 16); offtout(newsize, header + 24); if (fwrite(header, 32, 1, pf) != 1) err(1, "fwrite(%s)", argv[3]); /* Compute the differences, writing ctrl as we go */ if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); scan=0;len=0; lastscan=0;lastpos=0;lastoffset=0; while(scanoldscore+8)) break; if((scan+lastoffsetSf*2-lenf) { Sf=s; lenf=i; }; }; lenb=0; if(scan=lastscan+i)&&(pos>=i);i++) { if(old[pos-i]==new[scan-i]) s++; if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }; }; }; if(lastscan+lenf>scan-lenb) { overlap=(lastscan+lenf)-(scan-lenb); s=0;Ss=0;lens=0; for(i=0;iSs) { Ss=s; lens=i+1; }; }; lenf+=lens-overlap; lenb-=lens; }; for(i=0;i