From abfbdf119992742605e52ac1d1ab61ab2e9f03f5 Mon Sep 17 00:00:00 2001 From: "mark@chromium.org" Date: Wed, 9 Jun 2010 21:09:13 +0000 Subject: Modify bsdiff 4.3 to create goobsdiff, which is appropriate for use as the Mac binary differ/patcher. BUG=45017 TEST=none Review URL: http://codereview.chromium.org/2716005 git-svn-id: svn://svn.chromium.org/chrome/trunk/src@49316 0039d316-1c4b-4281-b951-d872f2087c98 --- .../mac/third_party/bsdiff/README.chromium | 41 +- chrome/installer/mac/third_party/bsdiff/bsdiff.c | 404 ----------------- chrome/installer/mac/third_party/bsdiff/bspatch.c | 204 --------- .../installer/mac/third_party/bsdiff/goobsdiff.c | 490 +++++++++++++++++++++ .../installer/mac/third_party/bsdiff/goobsdiff.gyp | 36 ++ .../installer/mac/third_party/bsdiff/goobspatch.c | 328 ++++++++++++++ 6 files changed, 893 insertions(+), 610 deletions(-) delete mode 100644 chrome/installer/mac/third_party/bsdiff/bsdiff.c delete mode 100644 chrome/installer/mac/third_party/bsdiff/bspatch.c create mode 100644 chrome/installer/mac/third_party/bsdiff/goobsdiff.c create mode 100644 chrome/installer/mac/third_party/bsdiff/goobsdiff.gyp create mode 100644 chrome/installer/mac/third_party/bsdiff/goobspatch.c (limited to 'chrome/installer/mac') diff --git a/chrome/installer/mac/third_party/bsdiff/README.chromium b/chrome/installer/mac/third_party/bsdiff/README.chromium index 4e8b024..edee853 100644 --- a/chrome/installer/mac/third_party/bsdiff/README.chromium +++ b/chrome/installer/mac/third_party/bsdiff/README.chromium @@ -8,7 +8,44 @@ License File: LICENSE Description: Binary diff/patch utility. There are other copies of BSDiff in the Chromium repository, but they're all different. The other copies are based on Mozilla's -fork of BSDiff, which serves a different set of needs. +fork of BSDiff, which serves a different set of needs. Relative to upstream +BSDiff, Mozilla's version removes all compression, adds a CRC-32 check of the +original file, replaces the custom off_t encoding with signed 32-bit +big-endian integers, and contains a total reorganization of the code. The +version in this directory contains no Mozilla code and builds directly on the +upstream version. It retains and enhances the compression, uses SHA1 to check +both the original file and the patched file, uses a different off_t encoding +more compatible with the original, and involves minimal changes to the +original code. + +Theoretically, a hash of the original file should be enough to guarantee data +integrity, but in the event of algorithmic or programming bugs or other +unexpected conditions, a hash of the patched file provides a better guarantee. +This implementation now checks the integrity of both the original and the +patched files. SHA1, rather than CRC-32, is used to minimize the likelihood +that an original file that has been intentionally tampered with will produce +an altered patched file without being detected. Local Modifications: - - Added LICENSE file by copying the license block from bsdiff.c and bspatch.c. + - Added LICENSE file by copying the license block from bsdiff.c and + bspatch.c. + - The following modifications are relative to the original unpatched version, + checked in to the Chromium repository at r49280. + - Created goobsdiff.gyp for GYP build system integration. + - Renamed bsdiff.c to goobsdiff.c and bspatch.c to goobspatch.c. + - Added #include to goobspatch.c so that it compiles. (Oops!) + - Changed the magic number in the header from BSDIFF40 to BSDIFF4G. + - Expanded the header to include SHA1 hashes of the original and new files, + and added hash checks to the patcher. + - Expanded the header to include the lengths of the control, diff, and extra + blocks in the patch file, and added patch file length validation to the + patcher. + - Replaced custom off_t encoding with signed 64-bit little-endian integers. + - The control, diff, and extra blocks can be compressed with bzip2 or gzip, + or left uncompressed, independently of one another, depending on which is + smallest. This often results in a net reduction in patch size of about 3%. + - Error messages in the patcher are slightly more descriptive. + - The patcher treats a few more unexpected read cases as errors than it did + previously. This will theoretically cause it to exit with an error instead + of sitting in a busy loop or crashing when certain malformatted patch files + are provided. diff --git a/chrome/installer/mac/third_party/bsdiff/bsdiff.c b/chrome/installer/mac/third_party/bsdiff/bsdiff.c deleted file mode 100644 index 150a7f7..0000000 --- a/chrome/installer/mac/third_party/bsdiff/bsdiff.c +++ /dev/null @@ -1,404 +0,0 @@ -/*- - * 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 - -#define MIN(x,y) (((x)<(y)) ? (x) : (y)) - -static 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;kstart) split(I,V,start,jj-start,h); - - for(i=0;ikk) split(I,V,kk,start+len-kk,h); -} - -static 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;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(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; - 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]; - FILE * pf; - BZFILE * pfbz2; - int bz2err; - - 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; - - /* 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 -#include -#include -#include -#include -#include -#include - -static off_t offtin(u_char *buf) -{ - off_t y; - - y=buf[7]&0x7F; - y=y*256;y+=buf[6]; - y=y*256;y+=buf[5]; - y=y*256;y+=buf[4]; - y=y*256;y+=buf[3]; - y=y*256;y+=buf[2]; - y=y*256;y+=buf[1]; - y=y*256;y+=buf[0]; - - if(buf[7]&0x80) y=-y; - - return y; -} - -int main(int argc,char * argv[]) -{ - FILE * f, * cpf, * dpf, * epf; - BZFILE * cpfbz2, * dpfbz2, * epfbz2; - int cbz2err, dbz2err, ebz2err; - int fd; - ssize_t oldsize,newsize; - ssize_t bzctrllen,bzdatalen; - u_char header[32],buf[8]; - u_char *old, *new; - off_t oldpos,newpos; - off_t ctrl[3]; - off_t lenread; - off_t i; - - if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]); - - /* Open patch file */ - if ((f = fopen(argv[3], "r")) == NULL) - err(1, "fopen(%s)", argv[3]); - - /* - File format: - 0 8 "BSDIFF40" - 8 8 X - 16 8 Y - 24 8 sizeof(newfile) - 32 X bzip2(control block) - 32+X Y bzip2(diff block) - 32+X+Y ??? bzip2(extra block) - with control block a set of triples (x,y,z) meaning "add x bytes - from oldfile to x bytes from the diff block; copy y bytes from the - extra block; seek forwards in oldfile by z bytes". - */ - - /* Read header */ - if (fread(header, 1, 32, f) < 32) { - if (feof(f)) - errx(1, "Corrupt patch\n"); - err(1, "fread(%s)", argv[3]); - } - - /* Check for appropriate magic */ - if (memcmp(header, "BSDIFF40", 8) != 0) - errx(1, "Corrupt patch\n"); - - /* Read lengths from header */ - bzctrllen=offtin(header+8); - bzdatalen=offtin(header+16); - newsize=offtin(header+24); - if((bzctrllen<0) || (bzdatalen<0) || (newsize<0)) - errx(1,"Corrupt patch\n"); - - /* Close patch file and re-open it via libbzip2 at the right places */ - if (fclose(f)) - err(1, "fclose(%s)", argv[3]); - if ((cpf = fopen(argv[3], "r")) == NULL) - err(1, "fopen(%s)", argv[3]); - if (fseeko(cpf, 32, SEEK_SET)) - err(1, "fseeko(%s, %lld)", argv[3], - (long long)32); - if ((cpfbz2 = BZ2_bzReadOpen(&cbz2err, cpf, 0, 0, NULL, 0)) == NULL) - errx(1, "BZ2_bzReadOpen, bz2err = %d", cbz2err); - if ((dpf = fopen(argv[3], "r")) == NULL) - err(1, "fopen(%s)", argv[3]); - if (fseeko(dpf, 32 + bzctrllen, SEEK_SET)) - err(1, "fseeko(%s, %lld)", argv[3], - (long long)(32 + bzctrllen)); - if ((dpfbz2 = BZ2_bzReadOpen(&dbz2err, dpf, 0, 0, NULL, 0)) == NULL) - errx(1, "BZ2_bzReadOpen, bz2err = %d", dbz2err); - if ((epf = fopen(argv[3], "r")) == NULL) - err(1, "fopen(%s)", argv[3]); - if (fseeko(epf, 32 + bzctrllen + bzdatalen, SEEK_SET)) - err(1, "fseeko(%s, %lld)", argv[3], - (long long)(32 + bzctrllen + bzdatalen)); - if ((epfbz2 = BZ2_bzReadOpen(&ebz2err, epf, 0, 0, NULL, 0)) == NULL) - errx(1, "BZ2_bzReadOpen, bz2err = %d", ebz2err); - - 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((new=malloc(newsize+1))==NULL) err(1,NULL); - - oldpos=0;newpos=0; - while(newposnewsize) - errx(1,"Corrupt patch\n"); - - /* Read diff string */ - lenread = BZ2_bzRead(&dbz2err, dpfbz2, new + newpos, ctrl[0]); - if ((lenread < ctrl[0]) || - ((dbz2err != BZ_OK) && (dbz2err != BZ_STREAM_END))) - errx(1, "Corrupt patch\n"); - - /* Add old data to diff string */ - for(i=0;i=0) && (oldpos+inewsize) - errx(1,"Corrupt patch\n"); - - /* Read extra string */ - lenread = BZ2_bzRead(&ebz2err, epfbz2, new + newpos, ctrl[1]); - if ((lenread < ctrl[1]) || - ((ebz2err != BZ_OK) && (ebz2err != BZ_STREAM_END))) - errx(1, "Corrupt patch\n"); - - /* Adjust pointers */ - newpos+=ctrl[1]; - oldpos+=ctrl[2]; - }; - - /* Clean up the bzip2 reads */ - BZ2_bzReadClose(&cbz2err, cpfbz2); - BZ2_bzReadClose(&dbz2err, dpfbz2); - BZ2_bzReadClose(&ebz2err, epfbz2); - if (fclose(cpf) || fclose(dpf) || fclose(epf)) - err(1, "fclose(%s)", argv[3]); - - /* Write the new file */ - if(((fd=open(argv[2],O_CREAT|O_TRUNC|O_WRONLY,0666))<0) || - (write(fd,new,newsize)!=newsize) || (close(fd)==-1)) - err(1,"%s",argv[2]); - - free(new); - free(old); - - return 0; -} diff --git a/chrome/installer/mac/third_party/bsdiff/goobsdiff.c b/chrome/installer/mac/third_party/bsdiff/goobsdiff.c new file mode 100644 index 0000000..8d41ec3 --- /dev/null +++ b/chrome/installer/mac/third_party/bsdiff/goobsdiff.c @@ -0,0 +1,490 @@ +/*- + * 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 + +#if defined(__APPLE__) +#include +#define htole64(x) OSSwapHostToLittleInt64(x) +#elif defined(__linux__) +#include +#elif defined(_WIN32) && (defined(_M_IX86) || defined(_M_X64)) +#define htole64(x) (x) +#else +#error Provide htole64 for this platform +#endif + +#define MIN(x,y) (((x)<(y)) ? (x) : (y)) + +static 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;kstart) split(I,V,start,jj-start,h); + + for(i=0;ikk) split(I,V,kk,start+len-kk,h); +} + +static 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;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 inline void offtout(off_t x,u_char *buf) +{ + *((off_t*)buf) = htole64(x); +} + +/* zlib provides compress2, which deflates to deflate (zlib) format. This is + * unfortunately distinct from gzip format in that the headers wrapping the + * decompressed data are different. gbspatch reads gzip-compressed data using + * the file-oriented gzread interface, which only supports gzip format. + * compress2gzip is identical to zlib's compress2 except that it produces gzip + * output compatible with gzread. This change is achieved by calling + * deflateInit2 instead of deflateInit and specifying 31 for windowBits; + * numbers greater than 15 cause the addition of a gzip wrapper. */ +static int compress2gzip(Bytef *dest, uLongf *destLen, + const Bytef *source, uLong sourceLen, int level) +{ + z_stream stream; + int err; + + stream.next_in = (Bytef*)source; + stream.avail_in = (uInt)sourceLen; + + stream.next_out = dest; + stream.avail_out = (uInt)*destLen; + if ((uLong)stream.avail_out != *destLen) return Z_BUF_ERROR; + + stream.zalloc = (alloc_func)0; + stream.zfree = (free_func)0; + stream.opaque = (voidpf)0; + + err = deflateInit2(&stream, + level, Z_DEFLATED, 31, 8, Z_DEFAULT_STRATEGY); + if (err != Z_OK) return err; + + err = deflate(&stream, Z_FINISH); + if (err != Z_STREAM_END) { + deflateEnd(&stream); + return err == Z_OK ? Z_BUF_ERROR : err; + } + *destLen = stream.total_out; + + err = deflateEnd(&stream); + return err; +} + +/* Recompress buf of size buf_len using bzip2 or gzip. The smallest version is + * used. The original uncompressed variant may be the smallest. Returns a + * number identifying the encoding, 1 for uncompressed, 2 for bzip2, and 3 for + * gzip. If the original uncompressed variant is not smallest, it is freed. + * The caller must free any buf after this function returns. */ +static char make_small(u_char **buf, off_t *buf_len) +{ + u_char *source = *buf; + off_t source_len = *buf_len; + u_char *bz2, *gz; + unsigned int bz2_len; + unsigned long gz_len; + int zerr; + char smallest; + + smallest = 1; + + bz2_len = source_len + 1; + bz2 = malloc(bz2_len); + zerr = BZ2_bzBuffToBuffCompress((char*)bz2, &bz2_len, (char*)source, + source_len, 9, 0, 0); + if (zerr == BZ_OK) { + if (bz2_len < *buf_len) { + smallest = 2; + *buf = bz2; + *buf_len = bz2_len; + } else { + free(bz2); + bz2 = NULL; + } + } else if (zerr == BZ_OUTBUFF_FULL) { + free(bz2); + bz2 = NULL; + } else { + errx(1, "BZ2_bzBuffToBuffCompress: %d", zerr); + } + + gz_len = source_len + 1; + gz = malloc(gz_len); + zerr = compress2gzip(gz, &gz_len, source, source_len, 9); + if (zerr == Z_OK) { + if (gz_len < *buf_len) { + smallest = 3; + *buf = gz; + *buf_len = gz_len; + } else { + free(gz); + gz = NULL; + } + } else if (zerr == Z_BUF_ERROR) { + free(gz); + gz = NULL; + } else { + errx(1, "compress2gzip: %d", zerr); + } + + if (smallest != 1) { + free(source); + } + + return smallest; +} + +int main(int argc,char *argv[]) +{ + int fd; + 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 cblen, dblen, eblen; + u_char *cb, *db, *eb; + u_char header[96]; + FILE * pf; + + if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile",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(((cb=malloc(newsize+1))==NULL) || + ((db=malloc(newsize+1))==NULL) || + ((eb=malloc(newsize+1))==NULL)) err(1,NULL); + cblen=0; + dblen=0; + eblen=0; + + /* Create the patch file */ + if ((pf = fopen(argv[3], "wb")) == NULL) + err(1, "%s", argv[3]); + + /* File format: + 0 8 "BSDIFF4G" + 8 8 length of compressed control block (x) + 16 8 length of compressed diff block (y) + 24 8 length of compressed extra block (z) + 32 8 length of old file + 40 8 length of new file + 48 20 SHA1 of old file + 68 20 SHA1 of new file + 88 1 encoding of control block + 89 1 encoding of diff block + 90 1 encoding of extra block + 91 5 unused + 96 x compressed control block + 96+x y compressed diff block + 96+x+y z compressed extra block + Encodings are 1 (uncompressed), 2 (bzip2), and 3 (gzip). */ + memset(header, 0, sizeof(header)); + if (fwrite(header, sizeof(header), 1, pf) != 1) + err(1, "fwrite(%s)", argv[3]); + memcpy(header, "BSDIFF4G", 8); + offtout(oldsize, header + 32); + offtout(newsize, header + 40); + SHA1(old, oldsize, header + 48); + SHA1(new, newsize, header + 68); + + /* Compute the differences */ + 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 + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#if defined(__APPLE__) +#include +#define le64toh(x) OSSwapLittleToHostInt64(x) +#elif defined(__linux__) +#include +#elif defined(_WIN32) && (defined(_M_IX86) || defined(_M_X64)) +#define le64toh(x) (x) +#else +#error Provide le64toh for this platform +#endif + +static inline off_t offtin(u_char *buf) +{ + return le64toh(*((off_t*)buf)); +} + +static void sha1tostr(const u_char *sha1, char *sha1str) +{ + int i; + for (i = 0; i < SHA_DIGEST_LENGTH; ++i) + sprintf(&sha1str[i * 2], "%02x", sha1[i]); +} + +/* cfile is a uniform interface to read from maybe-compressed files. */ + +typedef struct { + FILE *f; /* method = 1, 2 */ + union { + BZFILE *bz2; /* method = 2 */ + gzFile gz; /* method = 3 */ + } u; + const char *tag; + unsigned char method; +} cfile; + +/* Opens a file at path, seeks to offset off, and prepares for reading using + * the specified method. Supported methods are plain uncompressed (1), bzip2 + * (2), and gzip (3). tag is used as an identifier for error reporting. */ +static void cfopen(cfile *cf, const char *path, off_t off, + const char *tag, unsigned char method) +{ + int fd; + int zerr; + + if (method == 1 || method == 2) { + /* Use stdio for uncompressed files. The bzip interface also + * sits on top of a stdio FILE* but does not take "ownership" + * of the FILE*. */ + if ((cf->f = fopen(path, "rb")) == NULL) + err(1, "fdopen(%s)", tag); + if ((fseeko(cf->f, off, SEEK_SET)) != 0) + err(1, "fseeko(%s, %lld)", tag, off); + if (method == 2) { + if ((cf->u.bz2 = BZ2_bzReadOpen(&zerr, cf->f, 0, 0, + NULL, 0)) == NULL) + errx(1, "BZ2_bzReadOpen(%s): %d", tag, zerr); + } + } else if (method == 3) { + if ((fd = open(path, O_RDONLY)) < 0) + err(1, "open(%s)", tag); + if (lseek(fd, off, SEEK_SET) != off) + err(1, "lseek(%s, %lld)", tag, off); + if ((cf->u.gz = gzdopen(fd, "rb")) == NULL) + errx(1, "gzdopen(%s)", tag); + } else { + errx(1, "cfopen(%s): unknown method %d", tag, method); + } + + cf->tag = tag; + cf->method = method; +} + +static void cfclose(cfile *cf) +{ + int zerr; + + if (cf->method == 1 || cf->method == 2) { + if (cf->method == 2) { + zerr = BZ_OK; + BZ2_bzReadClose(&zerr, cf->u.bz2); + if (zerr != BZ_OK) + errx(1, "BZ2_bzReadClose(%s): %d\n", + cf->tag, zerr); + } + if (fclose(cf->f) != 0) + err(1, "fclose(%s)", cf->tag); + } else if (cf->method == 3) { + if ((zerr = gzclose(cf->u.gz)) != Z_OK) + errx(1, "gzclose(%s): %d", cf->tag, zerr); + } else { + errx(1, "cfclose(%s): unknown method %d", cf->tag, cf->method); + } +} + +static void cfread(cfile *cf, u_char *buf, size_t len) +{ + size_t nread; + int zerr; + + if (cf->method == 1) { + if ((nread = fread(buf, 1, len, cf->f)) != len) { + if (!ferror(cf->f)) + errx(1, "fread(%s, %zd): short read %zd", + cf->tag, len, nread); + err(1, "fread(%s, %zd)", cf->tag, len); + } + } else if (cf->method == 2) { + zerr = BZ_OK; + if ((nread = BZ2_bzRead(&zerr, cf->u.bz2, buf, len)) != len) { + if (zerr == BZ_OK) + errx(1, "BZ2_bzRead(%s, %zd): short read %zd", + cf->tag, len, nread); + errx(1, "BZ2_bzRead(%s, %zd): %d", cf->tag, len, zerr); + } + } else if (cf->method == 3) { + if ((nread = gzread(cf->u.gz, buf, len)) != len) { + zerr = Z_OK; + gzerror(cf->u.gz, &zerr); + if (zerr == Z_OK) + errx(1, "gzread(%s, %zd): short read %zd", + cf->tag, len, nread); + errx(1, "gzread(%s, %zd): %d", cf->tag, len, zerr); + } + } else { + errx(1, "cfread(%s, %zd): unknown method %d", + cf->tag, len, cf->method); + } +} + +int main(int argc,char * argv[]) +{ + FILE * f; + cfile cf, df, ef; + int fd; + off_t expect_oldsize, oldsize, newsize, patchsize; + off_t zctrllen, zdatalen, zextralen; + u_char header[96], buf[8]; + u_char *old, *new; + off_t oldpos,newpos; + off_t ctrl[3]; + off_t i; + u_char sha1[SHA_DIGEST_LENGTH]; + char sha1str[SHA_DIGEST_LENGTH * 2 + 1]; + char expected_sha1str[SHA_DIGEST_LENGTH * 2 + 1]; + + if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile",argv[0]); + + /* Open patch file */ + if ((f = fopen(argv[3], "rb")) == NULL) + err(1, "fopen(%s)", argv[3]); + + /* + File format: + 0 8 "BSDIFF4G" + 8 8 length of compressed control block (x) + 16 8 length of compressed diff block (y) + 24 8 length of compressed extra block (z) + 32 8 length of old file + 40 8 length of new file + 48 20 SHA1 of old file + 68 20 SHA1 of new file + 88 1 encoding of control block + 89 1 encoding of diff block + 90 1 encoding of extra block + 91 5 unused + 96 x compressed control block + 96+x y compressed diff block + 96+x+y z compressed extra block + Encodings are 1 (uncompressed), 2 (bzip2), and 3 (gzip). + The control block is a set of triples (x,y,z) meaning "add x bytes + from oldfile to x bytes from the diff block; copy y bytes from the + extra block; seek forwards in oldfile by z bytes". + */ + + /* Read header */ + if (fread(header, 1, sizeof(header), f) < sizeof(header)) { + if (feof(f)) + errx(1, "corrupt patch (header size)"); + err(1, "fread(%s)", argv[3]); + } + + /* Check for appropriate magic */ + if (memcmp(header, "BSDIFF4G", 8) != 0) + errx(1, "corrupt patch (magic)"); + + /* Read lengths from header */ + zctrllen = offtin(header + 8); + zdatalen = offtin(header + 16); + zextralen = offtin(header + 24); + expect_oldsize = offtin(header + 32); + newsize = offtin(header + 40); + if (zctrllen < 0 || zdatalen < 0 || zextralen < 0) + errx(1, "corrupt patch (stream sizes)"); + if (expect_oldsize < 0 || newsize < 0) + errx(1, "corrupt patch (file sizes)"); + + if (fseeko(f, 0, SEEK_END) != 0 || (patchsize = ftello(f)) < 0) + err(1, "fseeko/ftello(%s)", argv[3]); + if (patchsize != sizeof(header) + zctrllen + zdatalen + zextralen) + errx(1, "corrupt patch (patch size)"); + + cfopen(&cf, argv[3], sizeof(header), "control", header[88]); + cfopen(&df, argv[3], sizeof(header) + zctrllen, "diff", header[89]); + cfopen(&ef, argv[3], sizeof(header) + zctrllen + zdatalen, "extra", + header[90]); + + if (fclose(f)) + err(1, "fclose(%s)", argv[3]); + + 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 (expect_oldsize != oldsize) + errx(1, "old size mismatch: %lld != %lld", + oldsize, expect_oldsize); + SHA1(old, oldsize, sha1); + if (memcmp(sha1, header + 48, sizeof(sha1)) != 0) { + sha1tostr(sha1, sha1str); + sha1tostr(header + 48, expected_sha1str); + errx(1, "old hash mismatch: %s != %s", + sha1str, expected_sha1str); + } + if((new=malloc(newsize+1))==NULL) err(1,NULL); + + oldpos=0;newpos=0; + while(newposnewsize) + errx(1,"corrupt patch (diff): overrun"); + + /* Read diff string */ + cfread(&df, new + newpos, ctrl[0]); + + /* Add old data to diff string */ + for(i=0;i=0) && (oldpos+inewsize) + errx(1,"corrupt patch (extra): overrun"); + + /* Read extra string */ + cfread(&ef, new + newpos, ctrl[1]); + + /* Adjust pointers */ + newpos+=ctrl[1]; + oldpos+=ctrl[2]; + }; + + /* Clean up the readers */ + cfclose(&cf); + cfclose(&df); + cfclose(&ef); + + SHA1(new, newsize, sha1); + if (memcmp(sha1, header + 68, sizeof(sha1)) != 0) { + sha1tostr(sha1, sha1str); + sha1tostr(header + 68, expected_sha1str); + errx(1, "new hash mismatch: %s != %s", + sha1str, expected_sha1str); + } + + /* Write the new file */ + if(((fd=open(argv[2],O_CREAT|O_TRUNC|O_WRONLY,0644))<0) || + (write(fd,new,newsize)!=newsize) || (close(fd)==-1)) + err(1,"open/write/close(%s)",argv[2]); + + free(new); + free(old); + + return 0; +} -- cgit v1.1