Subversion Repositories vaca_plus

Rev

Blame | Last modification | View Log | RSS feed

  1. /*-
  2.  * Copyright 2003-2005 Colin Percival
  3.  * All rights reserved
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted providing that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  *
  14.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  15.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  16.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  18.  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  22.  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  23.  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  24.  * POSSIBILITY OF SUCH DAMAGE.
  25.  */
  26.  
  27. #if 0
  28. __FBSDID("$FreeBSD: src/usr.bin/bsdiff/bsdiff/bsdiff.c,v 1.1 2005/08/06 01:59:05 cperciva Exp $");
  29. #endif
  30.  
  31. #include <sys/types.h>
  32.  
  33. #include <bzlib.h>
  34. #include <err.h>
  35. #include <fcntl.h>
  36. #include <stdio.h>
  37. #include <stdlib.h>
  38. #include <string.h>
  39. #include <unistd.h>
  40.  
  41. #define MIN(x,y) (((x)<(y)) ? (x) : (y))
  42.  
  43. static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h)
  44. {
  45.         off_t i,j,k,x,tmp,jj,kk;
  46.  
  47.         if(len<16) {
  48.                 for(k=start;k<start+len;k+=j) {
  49.                         j=1;x=V[I[k]+h];
  50.                         for(i=1;k+i<start+len;i++) {
  51.                                 if(V[I[k+i]+h]<x) {
  52.                                         x=V[I[k+i]+h];
  53.                                         j=0;
  54.                                 };
  55.                                 if(V[I[k+i]+h]==x) {
  56.                                         tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
  57.                                         j++;
  58.                                 };
  59.                         };
  60.                         for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
  61.                         if(j==1) I[k]=-1;
  62.                 };
  63.                 return;
  64.         };
  65.  
  66.         x=V[I[start+len/2]+h];
  67.         jj=0;kk=0;
  68.         for(i=start;i<start+len;i++) {
  69.                 if(V[I[i]+h]<x) jj++;
  70.                 if(V[I[i]+h]==x) kk++;
  71.         };
  72.         jj+=start;kk+=jj;
  73.  
  74.         i=start;j=0;k=0;
  75.         while(i<jj) {
  76.                 if(V[I[i]+h]<x) {
  77.                         i++;
  78.                 } else if(V[I[i]+h]==x) {
  79.                         tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
  80.                         j++;
  81.                 } else {
  82.                         tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
  83.                         k++;
  84.                 };
  85.         };
  86.  
  87.         while(jj+j<kk) {
  88.                 if(V[I[jj+j]+h]==x) {
  89.                         j++;
  90.                 } else {
  91.                         tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
  92.                         k++;
  93.                 };
  94.         };
  95.  
  96.         if(jj>start) split(I,V,start,jj-start,h);
  97.  
  98.         for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
  99.         if(jj==kk-1) I[jj]=-1;
  100.  
  101.         if(start+len>kk) split(I,V,kk,start+len-kk,h);
  102. }
  103.  
  104. static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize)
  105. {
  106.         off_t buckets[256];
  107.         off_t i,h,len;
  108.  
  109.         for(i=0;i<256;i++) buckets[i]=0;
  110.         for(i=0;i<oldsize;i++) buckets[old[i]]++;
  111.         for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
  112.         for(i=255;i>0;i--) buckets[i]=buckets[i-1];
  113.         buckets[0]=0;
  114.  
  115.         for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
  116.         I[0]=oldsize;
  117.         for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
  118.         V[oldsize]=0;
  119.         for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
  120.         I[0]=-1;
  121.  
  122.         for(h=1;I[0]!=-(oldsize+1);h+=h) {
  123.                 len=0;
  124.                 for(i=0;i<oldsize+1;) {
  125.                         if(I[i]<0) {
  126.                                 len-=I[i];
  127.                                 i-=I[i];
  128.                         } else {
  129.                                 if(len) I[i-len]=-len;
  130.                                 len=V[I[i]]+1-i;
  131.                                 split(I,V,i,len,h);
  132.                                 i+=len;
  133.                                 len=0;
  134.                         };
  135.                 };
  136.                 if(len) I[i-len]=-len;
  137.         };
  138.  
  139.         for(i=0;i<oldsize+1;i++) I[V[i]]=i;
  140. }
  141.  
  142. static off_t matchlen(u_char *old,off_t oldsize,u_char *new,off_t newsize)
  143. {
  144.         off_t i;
  145.  
  146.         for(i=0;(i<oldsize)&&(i<newsize);i++)
  147.                 if(old[i]!=new[i]) break;
  148.  
  149.         return i;
  150. }
  151.  
  152. static off_t search(off_t *I,u_char *old,off_t oldsize,
  153.                 u_char *new,off_t newsize,off_t st,off_t en,off_t *pos)
  154. {
  155.         off_t x,y;
  156.  
  157.         if(en-st<2) {
  158.                 x=matchlen(old+I[st],oldsize-I[st],new,newsize);
  159.                 y=matchlen(old+I[en],oldsize-I[en],new,newsize);
  160.  
  161.                 if(x>y) {
  162.                         *pos=I[st];
  163.                         return x;
  164.                 } else {
  165.                         *pos=I[en];
  166.                         return y;
  167.                 }
  168.         };
  169.  
  170.         x=st+(en-st)/2;
  171.         if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) {
  172.                 return search(I,old,oldsize,new,newsize,x,en,pos);
  173.         } else {
  174.                 return search(I,old,oldsize,new,newsize,st,x,pos);
  175.         };
  176. }
  177.  
  178. static void offtout(off_t x,u_char *buf)
  179. {
  180.         off_t y;
  181.  
  182.         if(x<0) y=-x; else y=x;
  183.  
  184.                 buf[0]=y%256;y-=buf[0];
  185.         y=y/256;buf[1]=y%256;y-=buf[1];
  186.         y=y/256;buf[2]=y%256;y-=buf[2];
  187.         y=y/256;buf[3]=y%256;y-=buf[3];
  188.         y=y/256;buf[4]=y%256;y-=buf[4];
  189.         y=y/256;buf[5]=y%256;y-=buf[5];
  190.         y=y/256;buf[6]=y%256;y-=buf[6];
  191.         y=y/256;buf[7]=y%256;
  192.  
  193.         if(x<0) buf[7]|=0x80;
  194. }
  195.  
  196. int main(int argc,char *argv[])
  197. {
  198.         int fd;
  199.         u_char *old,*new;
  200.         off_t oldsize,newsize;
  201.         off_t *I,*V;
  202.         off_t scan,pos,len;
  203.         off_t lastscan,lastpos,lastoffset;
  204.         off_t oldscore,scsc;
  205.         off_t s,Sf,lenf,Sb,lenb;
  206.         off_t overlap,Ss,lens;
  207.         off_t i;
  208.         off_t dblen,eblen;
  209.         u_char *db,*eb;
  210.         u_char buf[8];
  211.         u_char header[32];
  212.         FILE * pf;
  213.         BZFILE * pfbz2;
  214.         int bz2err;
  215.  
  216.         if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);
  217.  
  218.         /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
  219.                 that we never try to malloc(0) and get a NULL pointer */
  220.         if(((fd=open(argv[1],O_RDONLY,0))<0) ||
  221.                 ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
  222.                 ((old=malloc(oldsize+1))==NULL) ||
  223.                 (lseek(fd,0,SEEK_SET)!=0) ||
  224.                 (read(fd,old,oldsize)!=oldsize) ||
  225.                 (close(fd)==-1)) err(1,"%s",argv[1]);
  226.  
  227.         if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) ||
  228.                 ((V=malloc((oldsize+1)*sizeof(off_t)))==NULL)) err(1,NULL);
  229.  
  230.         qsufsort(I,V,old,oldsize);
  231.  
  232.         free(V);
  233.  
  234.         /* Allocate newsize+1 bytes instead of newsize bytes to ensure
  235.                 that we never try to malloc(0) and get a NULL pointer */
  236.         if(((fd=open(argv[2],O_RDONLY,0))<0) ||
  237.                 ((newsize=lseek(fd,0,SEEK_END))==-1) ||
  238.                 ((new=malloc(newsize+1))==NULL) ||
  239.                 (lseek(fd,0,SEEK_SET)!=0) ||
  240.                 (read(fd,new,newsize)!=newsize) ||
  241.                 (close(fd)==-1)) err(1,"%s",argv[2]);
  242.  
  243.         if(((db=malloc(newsize+1))==NULL) ||
  244.                 ((eb=malloc(newsize+1))==NULL)) err(1,NULL);
  245.         dblen=0;
  246.         eblen=0;
  247.  
  248.         /* Create the patch file */
  249.         if ((pf = fopen(argv[3], "w")) == NULL)
  250.                 err(1, "%s", argv[3]);
  251.  
  252.         /* Header is
  253.                 0       8        "BSDIFF40"
  254.                 8       8       length of bzip2ed ctrl block
  255.                 16      8       length of bzip2ed diff block
  256.                 24      8       length of new file */
  257.         /* File is
  258.                 0       32      Header
  259.                 32      ??      Bzip2ed ctrl block
  260.                 ??      ??      Bzip2ed diff block
  261.                 ??      ??      Bzip2ed extra block */
  262.         memcpy(header,"BSDIFF40",8);
  263.         offtout(0, header + 8);
  264.         offtout(0, header + 16);
  265.         offtout(newsize, header + 24);
  266.         if (fwrite(header, 32, 1, pf) != 1)
  267.                 err(1, "fwrite(%s)", argv[3]);
  268.  
  269.         /* Compute the differences, writing ctrl as we go */
  270.         if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
  271.                 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
  272.         scan=0;len=0;
  273.         lastscan=0;lastpos=0;lastoffset=0;
  274.         while(scan<newsize) {
  275.                 oldscore=0;
  276.  
  277.                 for(scsc=scan+=len;scan<newsize;scan++) {
  278.                         len=search(I,old,oldsize,new+scan,newsize-scan,
  279.                                         0,oldsize,&pos);
  280.  
  281.                         for(;scsc<scan+len;scsc++)
  282.                         if((scsc+lastoffset<oldsize) &&
  283.                                 (old[scsc+lastoffset] == new[scsc]))
  284.                                 oldscore++;
  285.  
  286.                         if(((len==oldscore) && (len!=0)) ||
  287.                                 (len>oldscore+8)) break;
  288.  
  289.                         if((scan+lastoffset<oldsize) &&
  290.                                 (old[scan+lastoffset] == new[scan]))
  291.                                 oldscore--;
  292.                 };
  293.  
  294.                 if((len!=oldscore) || (scan==newsize)) {
  295.                         s=0;Sf=0;lenf=0;
  296.                         for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
  297.                                 if(old[lastpos+i]==new[lastscan+i]) s++;
  298.                                 i++;
  299.                                 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
  300.                         };
  301.  
  302.                         lenb=0;
  303.                         if(scan<newsize) {
  304.                                 s=0;Sb=0;
  305.                                 for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) {
  306.                                         if(old[pos-i]==new[scan-i]) s++;
  307.                                         if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
  308.                                 };
  309.                         };
  310.  
  311.                         if(lastscan+lenf>scan-lenb) {
  312.                                 overlap=(lastscan+lenf)-(scan-lenb);
  313.                                 s=0;Ss=0;lens=0;
  314.                                 for(i=0;i<overlap;i++) {
  315.                                         if(new[lastscan+lenf-overlap+i]==
  316.                                            old[lastpos+lenf-overlap+i]) s++;
  317.                                         if(new[scan-lenb+i]==
  318.                                            old[pos-lenb+i]) s--;
  319.                                         if(s>Ss) { Ss=s; lens=i+1; };
  320.                                 };
  321.  
  322.                                 lenf+=lens-overlap;
  323.                                 lenb-=lens;
  324.                         };
  325.  
  326.                         for(i=0;i<lenf;i++)
  327.                                 db[dblen+i]=new[lastscan+i]-old[lastpos+i];
  328.                         for(i=0;i<(scan-lenb)-(lastscan+lenf);i++)
  329.                                 eb[eblen+i]=new[lastscan+lenf+i];
  330.  
  331.                         dblen+=lenf;
  332.                         eblen+=(scan-lenb)-(lastscan+lenf);
  333.  
  334.                         offtout(lenf,buf);
  335.                         BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
  336.                         if (bz2err != BZ_OK)
  337.                                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  338.  
  339.                         offtout((scan-lenb)-(lastscan+lenf),buf);
  340.                         BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
  341.                         if (bz2err != BZ_OK)
  342.                                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  343.  
  344.                         offtout((pos-lenb)-(lastpos+lenf),buf);
  345.                         BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
  346.                         if (bz2err != BZ_OK)
  347.                                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  348.  
  349.                         lastscan=scan-lenb;
  350.                         lastpos=pos-lenb;
  351.                         lastoffset=pos-scan;
  352.                 };
  353.         };
  354.         BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
  355.         if (bz2err != BZ_OK)
  356.                 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
  357.  
  358.         /* Compute size of compressed ctrl data */
  359.         if ((len = ftello(pf)) == -1)
  360.                 err(1, "ftello");
  361.         offtout(len-32, header + 8);
  362.  
  363.         /* Write compressed diff data */
  364.         if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
  365.                 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
  366.         BZ2_bzWrite(&bz2err, pfbz2, db, dblen);
  367.         if (bz2err != BZ_OK)
  368.                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  369.         BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
  370.         if (bz2err != BZ_OK)
  371.                 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
  372.  
  373.         /* Compute size of compressed diff data */
  374.         if ((newsize = ftello(pf)) == -1)
  375.                 err(1, "ftello");
  376.         offtout(newsize - len, header + 16);
  377.  
  378.         /* Write compressed extra data */
  379.         if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
  380.                 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
  381.         BZ2_bzWrite(&bz2err, pfbz2, eb, eblen);
  382.         if (bz2err != BZ_OK)
  383.                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  384.         BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
  385.         if (bz2err != BZ_OK)
  386.                 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
  387.  
  388.         /* Seek to the beginning, write the header, and close the file */
  389.         if (fseeko(pf, 0, SEEK_SET))
  390.                 err(1, "fseeko");
  391.         if (fwrite(header, 32, 1, pf) != 1)
  392.                 err(1, "fwrite(%s)", argv[3]);
  393.         if (fclose(pf))
  394.                 err(1, "fclose");
  395.  
  396.         /* Free the memory we used */
  397.         free(db);
  398.         free(eb);
  399.         free(I);
  400.         free(old);
  401.         free(new);
  402.  
  403.         return 0;
  404. }
  405.