diff options
Diffstat (limited to 'src/bsdiff-4.2/bsdiff.c')
| -rw-r--r-- | src/bsdiff-4.2/bsdiff.c | 385 |
1 files changed, 0 insertions, 385 deletions
diff --git a/src/bsdiff-4.2/bsdiff.c b/src/bsdiff-4.2/bsdiff.c deleted file mode 100644 index f47226c1e0a6..000000000000 --- a/src/bsdiff-4.2/bsdiff.c +++ /dev/null @@ -1,385 +0,0 @@ -/* - 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". -*/ - -#ifndef BZIP2 -#define BZIP2 "/usr/bin/bzip2" -#endif - -#include <stdlib.h> -#include <stdio.h> -#include <string.h> -#include <err.h> -#include <unistd.h> -#include <fcntl.h> -#include <sys/wait.h> - -#define MIN(x,y) (((x)<(y)) ? (x) : (y)) - -void split(off_t *I,off_t *V,off_t start,off_t len,off_t h) -{ - off_t 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); -} - -void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize) -{ - off_t buckets[256]; - off_t 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; -} - -off_t matchlen(u_char *old,off_t oldsize,u_char *new,off_t newsize) -{ - off_t i; - - for(i=0;(i<oldsize)&&(i<newsize);i++) - if(old[i]!=new[i]) break; - - return i; -} - -off_t search(off_t *I,u_char *old,off_t oldsize, - u_char *new,off_t newsize,off_t st,off_t en,off_t *pos) -{ - off_t x,y; - - if(en-st<2) { - x=matchlen(old+I[st],oldsize-I[st],new,newsize); - y=matchlen(old+I[en],oldsize-I[en],new,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],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); - }; -} - -void offtout(off_t x,u_char *buf) -{ - off_t 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,p[2]; - pid_t pid; - u_char *old,*new; - off_t oldsize,newsize; - off_t *I,*V; - - off_t scan,pos,len; - off_t lastscan,lastpos,lastoffset; - off_t oldscore,scsc; - - off_t s,Sf,lenf,Sb,lenb; - off_t overlap,Ss,lens; - off_t i; - - off_t dblen,eblen; - u_char *db,*eb; - - u_char buf[8]; - u_char header[32]; - - if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]); - - /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure - that we never try to malloc(0) and get a NULL pointer */ - if(((fd=open(argv[1],O_RDONLY,0))<0) || - ((oldsize=lseek(fd,0,SEEK_END))==-1) || - ((old=malloc(oldsize+1))==NULL) || - (lseek(fd,0,SEEK_SET)!=0) || - (read(fd,old,oldsize)!=oldsize) || - (close(fd)==-1)) err(1,"%s",argv[1]); - - if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) || - ((V=malloc((oldsize+1)*sizeof(off_t)))==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 */ - if(((fd=open(argv[2],O_RDONLY,0))<0) || - ((newsize=lseek(fd,0,SEEK_END))==-1) || - ((new=malloc(newsize+1))==NULL) || - (lseek(fd,0,SEEK_SET)!=0) || - (read(fd,new,newsize)!=newsize) || - (close(fd)==-1)) err(1,"%s",argv[2]); - - if(((db=malloc(newsize+1))==NULL) || - ((eb=malloc(newsize+1))==NULL)) err(1,NULL); - dblen=0; - eblen=0; - - if((fd=open(argv[3],O_CREAT|O_TRUNC|O_WRONLY,0666))<0) - 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); - memset(header+8,0,24); - if(write(fd,header,32)!=32) err(1,"%s",argv[3]); - - if((pipe(p)==-1) || ((pid=fork())==-1)) err(1,NULL); - if(pid==0) { - if((close(0)==-1) || (close(1)==-1) || (dup2(fd,1)==-1) || - (dup2(p[0],0)==-1) || (close(fd)==-1) || - (close(p[0])==-1) || (close(p[1])==-1)) - err(1,NULL); - execl(BZIP2,BZIP2,"-zc",NULL); - err(1,"%s",BZIP2); - }; - if(close(p[0])==-1) err(1,NULL); - - scan=0;len=0; - lastscan=0;lastpos=0;lastoffset=0; - while(scan<newsize) { - oldscore=0; - - for(scsc=scan+=len;scan<newsize;scan++) { - len=search(I,old,oldsize,new+scan,newsize-scan, - 0,oldsize,&pos); - - for(;scsc<scan+len;scsc++) - if((scsc+lastoffset<oldsize) && - (old[scsc+lastoffset] == new[scsc])) - oldscore++; - - if(((len==oldscore) && (len!=0)) || - (len>oldscore+8)) break; - - if((scan+lastoffset<oldsize) && - (old[scan+lastoffset] == new[scan])) - oldscore--; - }; - - if((len!=oldscore) || (scan==newsize)) { - s=0;Sf=0;lenf=0; - for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) { - if(old[lastpos+i]==new[lastscan+i]) s++; - i++; - if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; }; - }; - - lenb=0; - if(scan<newsize) { - s=0;Sb=0; - for(i=1;(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;i<overlap;i++) { - if(new[lastscan+lenf-overlap+i]== - old[lastpos+lenf-overlap+i]) s++; - if(new[scan-lenb+i]== - old[pos-lenb+i]) s--; - if(s>Ss) { Ss=s; lens=i+1; }; - }; - - lenf+=lens-overlap; - lenb-=lens; - }; - - for(i=0;i<lenf;i++) - db[dblen+i]=new[lastscan+i]-old[lastpos+i]; - for(i=0;i<(scan-lenb)-(lastscan+lenf);i++) - eb[eblen+i]=new[lastscan+lenf+i]; - - dblen+=lenf; - eblen+=(scan-lenb)-(lastscan+lenf); - - offtout(lenf,buf); - if(write(p[1],buf,8)!=8) err(1,NULL); - offtout((scan-lenb)-(lastscan+lenf),buf); - if(write(p[1],buf,8)!=8) err(1,NULL); - offtout((pos-lenb)-(lastpos+lenf),buf); - if(write(p[1],buf,8)!=8) err(1,NULL); - - lastscan=scan-lenb; - lastpos=pos-lenb; - lastoffset=pos-scan; - }; - }; - - if((close(p[1])==-1) || (waitpid(pid,NULL,0)!=pid)) err(1,NULL); - - if((len=lseek(fd,0,SEEK_END))==-1) err(1,"%s",argv[3]); - offtout(len-32,buf); - if((lseek(fd,8,SEEK_SET)!=8) || (write(fd,buf,8)!=8)) - err(1,"%s",argv[3]); - offtout(newsize,buf); - if((lseek(fd,24,SEEK_SET)!=24) || (write(fd,buf,8)!=8)) - err(1,"%s",argv[3]); - - if(lseek(fd,0,SEEK_END)==-1) err(1,"%s",argv[3]); - if((pipe(p)==-1) || ((pid=fork())==-1)) err(1,NULL); - if(pid==0) { - if((close(0)==-1) || (close(1)==-1) || (dup2(fd,1)==-1) || - (dup2(p[0],0)==-1) || (close(fd)==-1) || - (close(p[0])==-1) || (close(p[1])==-1)) - err(1,NULL); - execl(BZIP2,BZIP2,"-zc",NULL); - err(1,"%s",BZIP2); - }; - if(close(p[0])==-1) err(1,NULL); - if(write(p[1],db,dblen)!=dblen) err(1,NULL); - if((close(p[1])==-1) || (waitpid(pid,NULL,0)!=pid)) err(1,NULL); - - if((newsize=lseek(fd,0,SEEK_END))==-1) err(1,"%s",argv[3]); - offtout(newsize-len,buf); - if((lseek(fd,16,SEEK_SET)!=16) || (write(fd,buf,8)!=8)) - err(1,"%s",argv[3]); - - if(lseek(fd,0,SEEK_END)==-1) err(1,"%s",argv[3]); - if((pipe(p)==-1) || ((pid=fork())==-1)) err(1,NULL); - if(pid==0) { - if((close(0)==-1) || (close(1)==-1) || (dup2(fd,1)==-1) || - (dup2(p[0],0)==-1) || (close(fd)==-1) || - (close(p[0])==-1) || (close(p[1])==-1)) - err(1,NULL); - execl(BZIP2,BZIP2,"-zc",NULL); - err(1,"%s",BZIP2); - }; - if(close(p[0])==-1) err(1,NULL); - if(write(p[1],eb,eblen)!=eblen) err(1,NULL); - if((close(p[1])==-1) || (waitpid(pid,NULL,0)!=pid)) err(1,NULL); - if(close(fd)==-1) err(1,"%s",argv[3]); - - free(db); - free(eb); - free(I); - free(old); - free(new); - - return 0; -} |