1148771Scperciva/*- 2148771Scperciva * Copyright 2003-2005 Colin Percival 3148771Scperciva * All rights reserved 4148771Scperciva * 5148771Scperciva * Redistribution and use in source and binary forms, with or without 6148771Scperciva * modification, are permitted providing that the following conditions 7148771Scperciva * are met: 8148771Scperciva * 1. Redistributions of source code must retain the above copyright 9148771Scperciva * notice, this list of conditions and the following disclaimer. 10148771Scperciva * 2. Redistributions in binary form must reproduce the above copyright 11148771Scperciva * notice, this list of conditions and the following disclaimer in the 12148771Scperciva * documentation and/or other materials provided with the distribution. 13148771Scperciva * 14148771Scperciva * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 15148771Scperciva * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16148771Scperciva * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17148771Scperciva * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 18148771Scperciva * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19148771Scperciva * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20148771Scperciva * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21148771Scperciva * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 22148771Scperciva * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 23148771Scperciva * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 24148771Scperciva * POSSIBILITY OF SUCH DAMAGE. 25148771Scperciva */ 26148771Scperciva 27148771Scperciva#include <sys/cdefs.h> 28148771Scperciva__FBSDID("$FreeBSD$"); 29148771Scperciva 30148771Scperciva#include <sys/types.h> 31148771Scperciva 32148771Scperciva#include <bzlib.h> 33148771Scperciva#include <err.h> 34148771Scperciva#include <fcntl.h> 35148771Scperciva#include <stdio.h> 36148771Scperciva#include <stdlib.h> 37148771Scperciva#include <string.h> 38148771Scperciva#include <unistd.h> 39148771Scperciva 40164922Scperciva#ifndef O_BINARY 41164922Scperciva#define O_BINARY 0 42164922Scperciva#endif 43164922Scperciva 44148771Scperciva#define MIN(x,y) (((x)<(y)) ? (x) : (y)) 45148771Scperciva 46148771Scpercivastatic void split(off_t *I,off_t *V,off_t start,off_t len,off_t h) 47148771Scperciva{ 48148771Scperciva off_t i,j,k,x,tmp,jj,kk; 49148771Scperciva 50148771Scperciva if(len<16) { 51148771Scperciva for(k=start;k<start+len;k+=j) { 52148771Scperciva j=1;x=V[I[k]+h]; 53148771Scperciva for(i=1;k+i<start+len;i++) { 54148771Scperciva if(V[I[k+i]+h]<x) { 55148771Scperciva x=V[I[k+i]+h]; 56148771Scperciva j=0; 57148771Scperciva }; 58148771Scperciva if(V[I[k+i]+h]==x) { 59148771Scperciva tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp; 60148771Scperciva j++; 61148771Scperciva }; 62148771Scperciva }; 63148771Scperciva for(i=0;i<j;i++) V[I[k+i]]=k+j-1; 64148771Scperciva if(j==1) I[k]=-1; 65148771Scperciva }; 66148771Scperciva return; 67148771Scperciva }; 68148771Scperciva 69148771Scperciva x=V[I[start+len/2]+h]; 70148771Scperciva jj=0;kk=0; 71148771Scperciva for(i=start;i<start+len;i++) { 72148771Scperciva if(V[I[i]+h]<x) jj++; 73148771Scperciva if(V[I[i]+h]==x) kk++; 74148771Scperciva }; 75148771Scperciva jj+=start;kk+=jj; 76148771Scperciva 77148771Scperciva i=start;j=0;k=0; 78148771Scperciva while(i<jj) { 79148771Scperciva if(V[I[i]+h]<x) { 80148771Scperciva i++; 81148771Scperciva } else if(V[I[i]+h]==x) { 82148771Scperciva tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp; 83148771Scperciva j++; 84148771Scperciva } else { 85148771Scperciva tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp; 86148771Scperciva k++; 87148771Scperciva }; 88148771Scperciva }; 89148771Scperciva 90148771Scperciva while(jj+j<kk) { 91148771Scperciva if(V[I[jj+j]+h]==x) { 92148771Scperciva j++; 93148771Scperciva } else { 94148771Scperciva tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp; 95148771Scperciva k++; 96148771Scperciva }; 97148771Scperciva }; 98148771Scperciva 99148771Scperciva if(jj>start) split(I,V,start,jj-start,h); 100148771Scperciva 101148771Scperciva for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1; 102148771Scperciva if(jj==kk-1) I[jj]=-1; 103148771Scperciva 104148771Scperciva if(start+len>kk) split(I,V,kk,start+len-kk,h); 105148771Scperciva} 106148771Scperciva 107148771Scpercivastatic void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize) 108148771Scperciva{ 109148771Scperciva off_t buckets[256]; 110148771Scperciva off_t i,h,len; 111148771Scperciva 112148771Scperciva for(i=0;i<256;i++) buckets[i]=0; 113148771Scperciva for(i=0;i<oldsize;i++) buckets[old[i]]++; 114148771Scperciva for(i=1;i<256;i++) buckets[i]+=buckets[i-1]; 115148771Scperciva for(i=255;i>0;i--) buckets[i]=buckets[i-1]; 116148771Scperciva buckets[0]=0; 117148771Scperciva 118148771Scperciva for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i; 119148771Scperciva I[0]=oldsize; 120148771Scperciva for(i=0;i<oldsize;i++) V[i]=buckets[old[i]]; 121148771Scperciva V[oldsize]=0; 122148771Scperciva for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1; 123148771Scperciva I[0]=-1; 124148771Scperciva 125148771Scperciva for(h=1;I[0]!=-(oldsize+1);h+=h) { 126148771Scperciva len=0; 127148771Scperciva for(i=0;i<oldsize+1;) { 128148771Scperciva if(I[i]<0) { 129148771Scperciva len-=I[i]; 130148771Scperciva i-=I[i]; 131148771Scperciva } else { 132148771Scperciva if(len) I[i-len]=-len; 133148771Scperciva len=V[I[i]]+1-i; 134148771Scperciva split(I,V,i,len,h); 135148771Scperciva i+=len; 136148771Scperciva len=0; 137148771Scperciva }; 138148771Scperciva }; 139148771Scperciva if(len) I[i-len]=-len; 140148771Scperciva }; 141148771Scperciva 142148771Scperciva for(i=0;i<oldsize+1;i++) I[V[i]]=i; 143148771Scperciva} 144148771Scperciva 145148771Scpercivastatic off_t matchlen(u_char *old,off_t oldsize,u_char *new,off_t newsize) 146148771Scperciva{ 147148771Scperciva off_t i; 148148771Scperciva 149148771Scperciva for(i=0;(i<oldsize)&&(i<newsize);i++) 150148771Scperciva if(old[i]!=new[i]) break; 151148771Scperciva 152148771Scperciva return i; 153148771Scperciva} 154148771Scperciva 155148771Scpercivastatic off_t search(off_t *I,u_char *old,off_t oldsize, 156148771Scperciva u_char *new,off_t newsize,off_t st,off_t en,off_t *pos) 157148771Scperciva{ 158148771Scperciva off_t x,y; 159148771Scperciva 160148771Scperciva if(en-st<2) { 161148771Scperciva x=matchlen(old+I[st],oldsize-I[st],new,newsize); 162148771Scperciva y=matchlen(old+I[en],oldsize-I[en],new,newsize); 163148771Scperciva 164148771Scperciva if(x>y) { 165148771Scperciva *pos=I[st]; 166148771Scperciva return x; 167148771Scperciva } else { 168148771Scperciva *pos=I[en]; 169148771Scperciva return y; 170148771Scperciva } 171148771Scperciva }; 172148771Scperciva 173148771Scperciva x=st+(en-st)/2; 174148771Scperciva if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) { 175148771Scperciva return search(I,old,oldsize,new,newsize,x,en,pos); 176148771Scperciva } else { 177148771Scperciva return search(I,old,oldsize,new,newsize,st,x,pos); 178148771Scperciva }; 179148771Scperciva} 180148771Scperciva 181148771Scpercivastatic void offtout(off_t x,u_char *buf) 182148771Scperciva{ 183148771Scperciva off_t y; 184148771Scperciva 185148771Scperciva if(x<0) y=-x; else y=x; 186148771Scperciva 187148771Scperciva buf[0]=y%256;y-=buf[0]; 188148771Scperciva y=y/256;buf[1]=y%256;y-=buf[1]; 189148771Scperciva y=y/256;buf[2]=y%256;y-=buf[2]; 190148771Scperciva y=y/256;buf[3]=y%256;y-=buf[3]; 191148771Scperciva y=y/256;buf[4]=y%256;y-=buf[4]; 192148771Scperciva y=y/256;buf[5]=y%256;y-=buf[5]; 193148771Scperciva y=y/256;buf[6]=y%256;y-=buf[6]; 194148771Scperciva y=y/256;buf[7]=y%256; 195148771Scperciva 196148771Scperciva if(x<0) buf[7]|=0x80; 197148771Scperciva} 198148771Scperciva 199148771Scpercivaint main(int argc,char *argv[]) 200148771Scperciva{ 201148771Scperciva int fd; 202148771Scperciva u_char *old,*new; 203148771Scperciva off_t oldsize,newsize; 204148771Scperciva off_t *I,*V; 205148771Scperciva off_t scan,pos,len; 206148771Scperciva off_t lastscan,lastpos,lastoffset; 207148771Scperciva off_t oldscore,scsc; 208148771Scperciva off_t s,Sf,lenf,Sb,lenb; 209148771Scperciva off_t overlap,Ss,lens; 210148771Scperciva off_t i; 211148771Scperciva off_t dblen,eblen; 212148771Scperciva u_char *db,*eb; 213148771Scperciva u_char buf[8]; 214148771Scperciva u_char header[32]; 215148771Scperciva FILE * pf; 216148771Scperciva BZFILE * pfbz2; 217148771Scperciva int bz2err; 218148771Scperciva 219148771Scperciva if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]); 220148771Scperciva 221148771Scperciva /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure 222148771Scperciva that we never try to malloc(0) and get a NULL pointer */ 223164922Scperciva if(((fd=open(argv[1],O_RDONLY|O_BINARY,0))<0) || 224148771Scperciva ((oldsize=lseek(fd,0,SEEK_END))==-1) || 225148771Scperciva ((old=malloc(oldsize+1))==NULL) || 226148771Scperciva (lseek(fd,0,SEEK_SET)!=0) || 227148771Scperciva (read(fd,old,oldsize)!=oldsize) || 228148771Scperciva (close(fd)==-1)) err(1,"%s",argv[1]); 229148771Scperciva 230148771Scperciva if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) || 231148771Scperciva ((V=malloc((oldsize+1)*sizeof(off_t)))==NULL)) err(1,NULL); 232148771Scperciva 233148771Scperciva qsufsort(I,V,old,oldsize); 234148771Scperciva 235148771Scperciva free(V); 236148771Scperciva 237148771Scperciva /* Allocate newsize+1 bytes instead of newsize bytes to ensure 238148771Scperciva that we never try to malloc(0) and get a NULL pointer */ 239164922Scperciva if(((fd=open(argv[2],O_RDONLY|O_BINARY,0))<0) || 240148771Scperciva ((newsize=lseek(fd,0,SEEK_END))==-1) || 241148771Scperciva ((new=malloc(newsize+1))==NULL) || 242148771Scperciva (lseek(fd,0,SEEK_SET)!=0) || 243148771Scperciva (read(fd,new,newsize)!=newsize) || 244148771Scperciva (close(fd)==-1)) err(1,"%s",argv[2]); 245148771Scperciva 246148771Scperciva if(((db=malloc(newsize+1))==NULL) || 247148771Scperciva ((eb=malloc(newsize+1))==NULL)) err(1,NULL); 248148771Scperciva dblen=0; 249148771Scperciva eblen=0; 250148771Scperciva 251148771Scperciva /* Create the patch file */ 252164922Scperciva if ((pf = fopen(argv[3], "wb")) == NULL) 253148771Scperciva err(1, "%s", argv[3]); 254148771Scperciva 255148771Scperciva /* Header is 256148771Scperciva 0 8 "BSDIFF40" 257148771Scperciva 8 8 length of bzip2ed ctrl block 258148771Scperciva 16 8 length of bzip2ed diff block 259148771Scperciva 24 8 length of new file */ 260148771Scperciva /* File is 261148771Scperciva 0 32 Header 262148771Scperciva 32 ?? Bzip2ed ctrl block 263148771Scperciva ?? ?? Bzip2ed diff block 264148771Scperciva ?? ?? Bzip2ed extra block */ 265148771Scperciva memcpy(header,"BSDIFF40",8); 266148771Scperciva offtout(0, header + 8); 267148771Scperciva offtout(0, header + 16); 268148771Scperciva offtout(newsize, header + 24); 269148771Scperciva if (fwrite(header, 32, 1, pf) != 1) 270148771Scperciva err(1, "fwrite(%s)", argv[3]); 271148771Scperciva 272148771Scperciva /* Compute the differences, writing ctrl as we go */ 273148771Scperciva if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) 274148771Scperciva errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); 275229910Seadler scan=0;len=0;pos=0; 276148771Scperciva lastscan=0;lastpos=0;lastoffset=0; 277148771Scperciva while(scan<newsize) { 278148771Scperciva oldscore=0; 279148771Scperciva 280148771Scperciva for(scsc=scan+=len;scan<newsize;scan++) { 281148771Scperciva len=search(I,old,oldsize,new+scan,newsize-scan, 282148771Scperciva 0,oldsize,&pos); 283148771Scperciva 284148771Scperciva for(;scsc<scan+len;scsc++) 285148771Scperciva if((scsc+lastoffset<oldsize) && 286148771Scperciva (old[scsc+lastoffset] == new[scsc])) 287148771Scperciva oldscore++; 288148771Scperciva 289148771Scperciva if(((len==oldscore) && (len!=0)) || 290148771Scperciva (len>oldscore+8)) break; 291148771Scperciva 292148771Scperciva if((scan+lastoffset<oldsize) && 293148771Scperciva (old[scan+lastoffset] == new[scan])) 294148771Scperciva oldscore--; 295148771Scperciva }; 296148771Scperciva 297148771Scperciva if((len!=oldscore) || (scan==newsize)) { 298148771Scperciva s=0;Sf=0;lenf=0; 299148771Scperciva for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) { 300148771Scperciva if(old[lastpos+i]==new[lastscan+i]) s++; 301148771Scperciva i++; 302148771Scperciva if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; }; 303148771Scperciva }; 304148771Scperciva 305148771Scperciva lenb=0; 306148771Scperciva if(scan<newsize) { 307148771Scperciva s=0;Sb=0; 308148771Scperciva for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) { 309148771Scperciva if(old[pos-i]==new[scan-i]) s++; 310148771Scperciva if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }; 311148771Scperciva }; 312148771Scperciva }; 313148771Scperciva 314148771Scperciva if(lastscan+lenf>scan-lenb) { 315148771Scperciva overlap=(lastscan+lenf)-(scan-lenb); 316148771Scperciva s=0;Ss=0;lens=0; 317148771Scperciva for(i=0;i<overlap;i++) { 318148771Scperciva if(new[lastscan+lenf-overlap+i]== 319148771Scperciva old[lastpos+lenf-overlap+i]) s++; 320148771Scperciva if(new[scan-lenb+i]== 321148771Scperciva old[pos-lenb+i]) s--; 322148771Scperciva if(s>Ss) { Ss=s; lens=i+1; }; 323148771Scperciva }; 324148771Scperciva 325148771Scperciva lenf+=lens-overlap; 326148771Scperciva lenb-=lens; 327148771Scperciva }; 328148771Scperciva 329148771Scperciva for(i=0;i<lenf;i++) 330148771Scperciva db[dblen+i]=new[lastscan+i]-old[lastpos+i]; 331148771Scperciva for(i=0;i<(scan-lenb)-(lastscan+lenf);i++) 332148771Scperciva eb[eblen+i]=new[lastscan+lenf+i]; 333148771Scperciva 334148771Scperciva dblen+=lenf; 335148771Scperciva eblen+=(scan-lenb)-(lastscan+lenf); 336148771Scperciva 337148771Scperciva offtout(lenf,buf); 338148771Scperciva BZ2_bzWrite(&bz2err, pfbz2, buf, 8); 339148771Scperciva if (bz2err != BZ_OK) 340148771Scperciva errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 341148771Scperciva 342148771Scperciva offtout((scan-lenb)-(lastscan+lenf),buf); 343148771Scperciva BZ2_bzWrite(&bz2err, pfbz2, buf, 8); 344148771Scperciva if (bz2err != BZ_OK) 345148771Scperciva errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 346148771Scperciva 347148771Scperciva offtout((pos-lenb)-(lastpos+lenf),buf); 348148771Scperciva BZ2_bzWrite(&bz2err, pfbz2, buf, 8); 349148771Scperciva if (bz2err != BZ_OK) 350148771Scperciva errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 351148771Scperciva 352148771Scperciva lastscan=scan-lenb; 353148771Scperciva lastpos=pos-lenb; 354148771Scperciva lastoffset=pos-scan; 355148771Scperciva }; 356148771Scperciva }; 357148771Scperciva BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL); 358148771Scperciva if (bz2err != BZ_OK) 359148771Scperciva errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err); 360148771Scperciva 361148771Scperciva /* Compute size of compressed ctrl data */ 362148771Scperciva if ((len = ftello(pf)) == -1) 363148771Scperciva err(1, "ftello"); 364148771Scperciva offtout(len-32, header + 8); 365148771Scperciva 366148771Scperciva /* Write compressed diff data */ 367148771Scperciva if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) 368148771Scperciva errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); 369148771Scperciva BZ2_bzWrite(&bz2err, pfbz2, db, dblen); 370148771Scperciva if (bz2err != BZ_OK) 371148771Scperciva errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 372148771Scperciva BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL); 373148771Scperciva if (bz2err != BZ_OK) 374148771Scperciva errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err); 375148771Scperciva 376148771Scperciva /* Compute size of compressed diff data */ 377148771Scperciva if ((newsize = ftello(pf)) == -1) 378148771Scperciva err(1, "ftello"); 379148771Scperciva offtout(newsize - len, header + 16); 380148771Scperciva 381148771Scperciva /* Write compressed extra data */ 382148771Scperciva if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL) 383148771Scperciva errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err); 384148771Scperciva BZ2_bzWrite(&bz2err, pfbz2, eb, eblen); 385148771Scperciva if (bz2err != BZ_OK) 386148771Scperciva errx(1, "BZ2_bzWrite, bz2err = %d", bz2err); 387148771Scperciva BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL); 388148771Scperciva if (bz2err != BZ_OK) 389148771Scperciva errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err); 390148771Scperciva 391148771Scperciva /* Seek to the beginning, write the header, and close the file */ 392148771Scperciva if (fseeko(pf, 0, SEEK_SET)) 393148771Scperciva err(1, "fseeko"); 394148771Scperciva if (fwrite(header, 32, 1, pf) != 1) 395148771Scperciva err(1, "fwrite(%s)", argv[3]); 396148771Scperciva if (fclose(pf)) 397148771Scperciva err(1, "fclose"); 398148771Scperciva 399148771Scperciva /* Free the memory we used */ 400148771Scperciva free(db); 401148771Scperciva free(eb); 402148771Scperciva free(I); 403148771Scperciva free(old); 404148771Scperciva free(new); 405148771Scperciva 406148771Scperciva return 0; 407148771Scperciva} 408