other-licenses/bsdiff/bsdiff.c

   1 /* vim:set ts=8 sw=8 sts=8 noet: */
   2 /*
   3   bsdiff.c -- Binary patch generator.
   4
   5   Copyright 2003 Colin Percival
   6
   7   For the terms under which this work may be distributed, please see
   8   the adjoining file "LICENSE".
   9
  10   ChangeLog:
  11   2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit
  12                values throughout.
  13                  --Benjamin Smedberg <benjamin@smedbergs.us>
  14   2005-05-18 - Use the same CRC algorithm as bzip2, and leverage the CRC table
  15                provided by libbz2.
  16                  --Darin Fisher <darin@meer.net>
  17 */
  18
  19 #include "bspatch.h"
  20
  21 #include <stdlib.h>
  22 #include <stdio.h>
  23 #include <string.h>
  24 #include <fcntl.h>
  25 #include <stdarg.h>
  26 #ifdef XP_WIN
  27 #include <io.h>
  28 #include <winsock2.h>
  29 #else
  30 #include <unistd.h>
  31 #include <arpa/inet.h>
  32 #define _O_BINARY 0
  33 #endif
  34
  35 #undef MIN
  36 #define MIN(x,y) (((x)<(y)) ? (x) : (y))
  37
  38 //-----------------------------------------------------------------------------
  39
  40 // This variable lives in libbz2.  It's declared in bzlib_private.h, so we just
  41 // declare it here to avoid including that entire header file.
  42 extern unsigned int BZ2_crc32Table[256];
  43
  44 static unsigned int
  45 crc32(const unsigned char *buf, unsigned int len)
  46 {
  47         unsigned int crc = 0xffffffffL;
  48
  49         const unsigned char *end = buf + len;
  50         for (; buf != end; ++buf)
  51                 crc = (crc << 8) ^ BZ2_crc32Table[(crc >> 24) ^ *buf];
  52
  53         crc = ~crc;
  54         return crc;
  55 }
  56
  57 //-----------------------------------------------------------------------------
  58
  59 static void
  60 reporterr(int e, const char *fmt, ...)
  61 {
  62         if (fmt) {
  63                 va_list args;
  64                 va_start(args, fmt);
  65                 vfprintf(stderr, fmt, args);
  66                 va_end(args);
  67         }
  68
  69         exit(e);
  70 }
  71
  72 static void
  73 split(PROffset32 *I,PROffset32 *V,PROffset32 start,PROffset32 len,PROffset32 h)
  74 {
  75         PROffset32 i,j,k,x,tmp,jj,kk;
  76
  77         if(len<16) {
  78                 for(k=start;k<start+len;k+=j) {
  79                         j=1;x=V[I[k]+h];
  80                         for(i=1;k+i<start+len;i++) {
  81                                 if(V[I[k+i]+h]<x) {
  82                                         x=V[I[k+i]+h];
  83                                         j=0;
  84                                 };
  85                                 if(V[I[k+i]+h]==x) {
  86                                         tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
  87                                         j++;
  88                                 };
  89                         };
  90                         for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
  91                         if(j==1) I[k]=-1;
  92                 };
  93                 return;
  94         };
  95
  96         x=V[I[start+len/2]+h];
  97         jj=0;kk=0;
  98         for(i=start;i<start+len;i++) {
  99                 if(V[I[i]+h]<x) jj++;
 100                 if(V[I[i]+h]==x) kk++;
 101         };
 102         jj+=start;kk+=jj;
 103
 104         i=start;j=0;k=0;
 105         while(i<jj) {
 106                 if(V[I[i]+h]<x) {
 107                         i++;
 108                 } else if(V[I[i]+h]==x) {
 109                         tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
 110                         j++;
 111                 } else {
 112                         tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
 113                         k++;
 114                 };
 115         };
 116
 117         while(jj+j<kk) {
 118                 if(V[I[jj+j]+h]==x) {
 119                         j++;
 120                 } else {
 121                         tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
 122                         k++;
 123                 };
 124         };
 125
 126         if(jj>start) split(I,V,start,jj-start,h);
 127
 128         for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
 129         if(jj==kk-1) I[jj]=-1;
 130
 131         if(start+len>kk) split(I,V,kk,start+len-kk,h);
 132 }
 133
 134 static void
 135 qsufsort(PROffset32 *I,PROffset32 *V,unsigned char *old,PROffset32 oldsize)
 136 {
 137         PROffset32 buckets[256];
 138         PROffset32 i,h,len;
 139
 140         for(i=0;i<256;i++) buckets[i]=0;
 141         for(i=0;i<oldsize;i++) buckets[old[i]]++;
 142         for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
 143         for(i=255;i>0;i--) buckets[i]=buckets[i-1];
 144         buckets[0]=0;
 145
 146         for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
 147         I[0]=oldsize;
 148         for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
 149         V[oldsize]=0;
 150         for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
 151         I[0]=-1;
 152
 153         for(h=1;I[0]!=-(oldsize+1);h+=h) {
 154                 len=0;
 155                 for(i=0;i<oldsize+1;) {
 156                         if(I[i]<0) {
 157                                 len-=I[i];
 158                                 i-=I[i];
 159                         } else {
 160                                 if(len) I[i-len]=-len;
 161                                 len=V[I[i]]+1-i;
 162                                 split(I,V,i,len,h);
 163                                 i+=len;
 164                                 len=0;
 165                         };
 166                 };
 167                 if(len) I[i-len]=-len;
 168         };
 169
 170         for(i=0;i<oldsize+1;i++) I[V[i]]=i;
 171 }
 172
 173 static PROffset32
 174 matchlen(unsigned char *old,PROffset32 oldsize,unsigned char *newbuf,PROffset32 newsize)
 175 {
 176         PROffset32 i;
 177
 178         for(i=0;(i<oldsize)&&(i<newsize);i++)
 179                 if(old[i]!=newbuf[i]) break;
 180
 181         return i;
 182 }
 183
 184 static PROffset32
 185 search(PROffset32 *I,unsigned char *old,PROffset32 oldsize,
 186        unsigned char *newbuf,PROffset32 newsize,PROffset32 st,PROffset32 en,PROffset32 *pos)
 187 {
 188         PROffset32 x,y;
 189
 190         if(en-st<2) {
 191                 x=matchlen(old+I[st],oldsize-I[st],newbuf,newsize);
 192                 y=matchlen(old+I[en],oldsize-I[en],newbuf,newsize);
 193
 194                 if(x>y) {
 195                         *pos=I[st];
 196                         return x;
 197                 } else {
 198                         *pos=I[en];
 199                         return y;
 200                 }
 201         };
 202
 203         x=st+(en-st)/2;
 204         if(memcmp(old+I[x],newbuf,MIN(oldsize-I[x],newsize))<0) {
 205                 return search(I,old,oldsize,newbuf,newsize,x,en,pos);
 206         } else {
 207                 return search(I,old,oldsize,newbuf,newsize,st,x,pos);
 208         };
 209 }
 210
 211 int main(int argc,char *argv[])
 212 {
 213         int fd;
 214         unsigned char *old,*newbuf;
 215         PROffset32 oldsize,newsize;
 216         PROffset32 *I,*V;
 217
 218         PROffset32 scan,pos,len;
 219         PROffset32 lastscan,lastpos,lastoffset;
 220         PROffset32 oldscore,scsc;
 221
 222         PROffset32 s,Sf,lenf,Sb,lenb;
 223         PROffset32 overlap,Ss,lens;
 224         PROffset32 i;
 225
 226         PROffset32 dblen,eblen;
 227         unsigned char *db,*eb;
 228
 229         unsigned int scrc;
 230
 231         MBSPatchHeader header = {
 232                 {'M','B','D','I','F','F','1','0'},
 233                 0, 0, 0, 0, 0, 0
 234         };
 235
 236         PRUint32 numtriples;
 237
 238         if(argc!=4)
 239                 reporterr(1,"usage: %s <oldfile> <newfile> <patchfile>\n",argv[0]);
 240
 241         /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
 242                 that we never try to malloc(0) and get a NULL pointer */
 243         if(((fd=open(argv[1],O_RDONLY|_O_BINARY,0))<0) ||
 244                 ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
 245                 ((old=(unsigned char*) malloc(oldsize+1))==NULL) ||
 246                 (lseek(fd,0,SEEK_SET)!=0) ||
 247                 (read(fd,old,oldsize)!=oldsize) ||
 248                 (close(fd)==-1))
 249                 reporterr(1,"%s\n",argv[1]);
 250
 251         scrc = crc32(old, oldsize);
 252
 253         if(((I=(PROffset32*) malloc((oldsize+1)*sizeof(PROffset32)))==NULL) ||
 254                 ((V=(PROffset32*) malloc((oldsize+1)*sizeof(PROffset32)))==NULL))
 255                 reporterr(1,NULL);
 256
 257         qsufsort(I,V,old,oldsize);
 258
 259         free(V);
 260
 261         /* Allocate newsize+1 bytes instead of newsize bytes to ensure
 262                 that we never try to malloc(0) and get a NULL pointer */
 263         if(((fd=open(argv[2],O_RDONLY|_O_BINARY,0))<0) ||
 264                 ((newsize=lseek(fd,0,SEEK_END))==-1) ||
 265                 ((newbuf=(unsigned char*) malloc(newsize+1))==NULL) ||
 266                 (lseek(fd,0,SEEK_SET)!=0) ||
 267                 (read(fd,newbuf,newsize)!=newsize) ||
 268                 (close(fd)==-1)) reporterr(1,"%s\n",argv[2]);
 269
 270         if(((db=(unsigned char*) malloc(newsize+1))==NULL) ||
 271                 ((eb=(unsigned char*) malloc(newsize+1))==NULL))
 272                 reporterr(1,NULL);
 273
 274         dblen=0;
 275         eblen=0;
 276
 277         if((fd=open(argv[3],O_CREAT|O_TRUNC|O_WRONLY|_O_BINARY,0666))<0)
 278                 reporterr(1,"%s\n",argv[3]);
 279
 280         /* start writing here */
 281
 282         /* We don't know the lengths yet, so we will write the header again
 283                  at the end */
 284
 285         if(write(fd,&header,sizeof(MBSPatchHeader))!=sizeof(MBSPatchHeader))
 286                 reporterr(1,"%s\n",argv[3]);
 287
 288         scan=0;len=0;
 289         lastscan=0;lastpos=0;lastoffset=0;
 290         numtriples = 0;
 291         while(scan<newsize) {
 292                 oldscore=0;
 293
 294                 for(scsc=scan+=len;scan<newsize;scan++) {
 295                         len=search(I,old,oldsize,newbuf+scan,newsize-scan,
 296                                         0,oldsize,&pos);
 297
 298                         for(;scsc<scan+len;scsc++)
 299                         if((scsc+lastoffset<oldsize) &&
 300                                 (old[scsc+lastoffset] == newbuf[scsc]))
 301                                 oldscore++;
 302
 303                         if(((len==oldscore) && (len!=0)) ||
 304                                 (len>oldscore+8)) break;
 305
 306                         if((scan+lastoffset<oldsize) &&
 307                                 (old[scan+lastoffset] == newbuf[scan]))
 308                                 oldscore--;
 309                 };
 310
 311                 if((len!=oldscore) || (scan==newsize)) {
 312                         MBSPatchTriple triple;
 313
 314                         s=0;Sf=0;lenf=0;
 315                         for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
 316                                 if(old[lastpos+i]==newbuf[lastscan+i]) s++;
 317                                 i++;
 318                                 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
 319                         };
 320
 321                         lenb=0;
 322                         if(scan<newsize) {
 323                                 s=0;Sb=0;
 324                                 for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) {
 325                                         if(old[pos-i]==newbuf[scan-i]) s++;
 326                                         if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
 327                                 };
 328                         };
 329
 330                         if(lastscan+lenf>scan-lenb) {
 331                                 overlap=(lastscan+lenf)-(scan-lenb);
 332                                 s=0;Ss=0;lens=0;
 333                                 for(i=0;i<overlap;i++) {
 334                                         if(newbuf[lastscan+lenf-overlap+i]==
 335                                            old[lastpos+lenf-overlap+i]) s++;
 336                                         if(newbuf[scan-lenb+i]==
 337                                            old[pos-lenb+i]) s--;
 338                                         if(s>Ss) { Ss=s; lens=i+1; };
 339                                 };
 340
 341                                 lenf+=lens-overlap;
 342                                 lenb-=lens;
 343                         };
 344
 345                         for(i=0;i<lenf;i++)
 346                                 db[dblen+i]=newbuf[lastscan+i]-old[lastpos+i];
 347                         for(i=0;i<(scan-lenb)-(lastscan+lenf);i++)
 348                                 eb[eblen+i]=newbuf[lastscan+lenf+i];
 349
 350                         dblen+=lenf;
 351                         eblen+=(scan-lenb)-(lastscan+lenf);
 352
 353                         triple.x = htonl(lenf);
 354                         triple.y = htonl((scan-lenb)-(lastscan+lenf));
 355                         triple.z = htonl((pos-lenb)-(lastpos+lenf));
 356                         if (write(fd,&triple,sizeof(triple)) != sizeof(triple))
 357                                 reporterr(1,NULL);
 358
 359 #ifdef DEBUG_bsmedberg
 360                         printf("Writing a block:\n"
 361                                "        X: %u\n"
 362                                "        Y: %u\n"
 363                                "        Z: %i\n",
 364                                (PRUint32) lenf,
 365                                (PRUint32) ((scan-lenb)-(lastscan+lenf)),
 366                                (PRUint32) ((pos-lenb)-(lastpos+lenf)));
 367 #endif
 368
 369                         ++numtriples;
 370
 371                         lastscan=scan-lenb;
 372                         lastpos=pos-lenb;
 373                         lastoffset=pos-scan;
 374                 };
 375         };
 376
 377         if(write(fd,db,dblen)!=dblen)
 378                 reporterr(1,NULL);
 379
 380         if(write(fd,eb,eblen)!=eblen)
 381                 reporterr(1,NULL);
 382
 383         header.slen     = htonl(oldsize);
 384         header.scrc32   = htonl(scrc);
 385         header.dlen     = htonl(newsize);
 386         header.cblen    = htonl(numtriples * sizeof(MBSPatchTriple));
 387         header.difflen  = htonl(dblen);
 388         header.extralen = htonl(eblen);
 389
 390         if (lseek(fd,0,SEEK_SET) == -1 ||
 391             write(fd,&header,sizeof(header)) != sizeof(header) ||
 392             close(fd) == -1)
 393                 reporterr(1,NULL);
 394
 395         free(db);
 396         free(eb);
 397         free(I);
 398         free(old);
 399         free(newbuf);
 400
 401         return 0;
 402 }