Subversion Repositories nw_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.  
  28. #include <stdlib.h>
  29. #include "bzlib.h"
  30. #include <stdio.h>
  31. #include <string.h>
  32. //#include <err.h>
  33. //#include <unistd.h>
  34. #include <io.h>
  35. #include <fcntl.h>
  36. //#include <sys/wait.h>
  37.  
  38.  
  39. #include <windows.h>
  40. #include <process.h>
  41. #include <sys/types.h>
  42. typedef unsigned char u_char;
  43. typedef long pid_t;
  44.  
  45. template<class T>
  46. void err(int i, const char* str, T arg) {
  47.         char lastErrorTxt[1024];
  48.         FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM|FORMAT_MESSAGE_IGNORE_INSERTS,NULL,GetLastError(),0,lastErrorTxt,1024,NULL);
  49.         printf("%s",lastErrorTxt);
  50.         printf(str, arg);
  51.         exit(i);
  52. }
  53. void err(int i, const char* str) {
  54.         char lastErrorTxt[1024];
  55.         FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM|FORMAT_MESSAGE_IGNORE_INSERTS,NULL,GetLastError(),0,lastErrorTxt,1024,NULL);
  56.         printf("%s",lastErrorTxt);
  57.         if (str!=NULL) {
  58.                 printf("%s",str);
  59.         }
  60.         exit(i);
  61. }
  62. template<class T>
  63. void errx(int i, const char* str, T arg) {
  64.         printf(str, arg);
  65.         exit(i);
  66. }
  67. void errx(int i, const char* str) {
  68.         printf("%s",str);
  69.         exit(i);
  70. }
  71.  
  72. #define MIN(x,y) (((x)<(y)) ? (x) : (y))
  73.  
  74. static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h)
  75. {
  76.         off_t i,j,k,x,tmp,jj,kk;
  77.  
  78.         if(len<16) {
  79.                 for(k=start;k<start+len;k+=j) {
  80.                         j=1;x=V[I[k]+h];
  81.                         for(i=1;k+i<start+len;i++) {
  82.                                 if(V[I[k+i]+h]<x) {
  83.                                         x=V[I[k+i]+h];
  84.                                         j=0;
  85.                                 };
  86.                                 if(V[I[k+i]+h]==x) {
  87.                                         tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
  88.                                         j++;
  89.                                 };
  90.                         };
  91.                         for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
  92.                         if(j==1) I[k]=-1;
  93.                 };
  94.                 return;
  95.         };
  96.  
  97.         x=V[I[start+len/2]+h];
  98.         jj=0;kk=0;
  99.         for(i=start;i<start+len;i++) {
  100.                 if(V[I[i]+h]<x) jj++;
  101.                 if(V[I[i]+h]==x) kk++;
  102.         };
  103.         jj+=start;kk+=jj;
  104.  
  105.         i=start;j=0;k=0;
  106.         while(i<jj) {
  107.                 if(V[I[i]+h]<x) {
  108.                         i++;
  109.                 } else if(V[I[i]+h]==x) {
  110.                         tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
  111.                         j++;
  112.                 } else {
  113.                         tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
  114.                         k++;
  115.                 };
  116.         };
  117.  
  118.         while(jj+j<kk) {
  119.                 if(V[I[jj+j]+h]==x) {
  120.                         j++;
  121.                 } else {
  122.                         tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
  123.                         k++;
  124.                 };
  125.         };
  126.  
  127.         if(jj>start) split(I,V,start,jj-start,h);
  128.  
  129.         for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
  130.         if(jj==kk-1) I[jj]=-1;
  131.  
  132.         if(start+len>kk) split(I,V,kk,start+len-kk,h);
  133. }
  134.  
  135. static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize)
  136. {
  137.         off_t buckets[256];
  138.         off_t 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 off_t matchlen(u_char *old,off_t oldsize,u_char *_new,off_t newsize)
  174. {
  175.         off_t i;
  176.  
  177.         for(i=0;(i<oldsize)&&(i<newsize);i++)
  178.                 if(old[i]!=_new[i]) break;
  179.  
  180.         return i;
  181. }
  182.  
  183. static off_t search(off_t *I,u_char *old,off_t oldsize,
  184.                 u_char *_new,off_t newsize,off_t st,off_t en,off_t *pos)
  185. {
  186.         off_t x,y;
  187.  
  188.         if(en-st<2) {
  189.                 x=matchlen(old+I[st],oldsize-I[st],_new,newsize);
  190.                 y=matchlen(old+I[en],oldsize-I[en],_new,newsize);
  191.  
  192.                 if(x>y) {
  193.                         *pos=I[st];
  194.                         return x;
  195.                 } else {
  196.                         *pos=I[en];
  197.                         return y;
  198.                 }
  199.         };
  200.  
  201.         x=st+(en-st)/2;
  202.         if(memcmp(old+I[x],_new,MIN(oldsize-I[x],newsize))<0) {
  203.                 return search(I,old,oldsize,_new,newsize,x,en,pos);
  204.         } else {
  205.                 return search(I,old,oldsize,_new,newsize,st,x,pos);
  206.         };
  207. }
  208.  
  209. static void offtout(off_t x,u_char *buf)
  210. {
  211.         off_t y;
  212.  
  213.         if(x<0) y=-x; else y=x;
  214.  
  215.                 buf[0]=y%256;y-=buf[0];
  216.         y=y/256;buf[1]=y%256;y-=buf[1];
  217.         y=y/256;buf[2]=y%256;y-=buf[2];
  218.         y=y/256;buf[3]=y%256;y-=buf[3];
  219.         y=y/256;buf[4]=y%256;y-=buf[4];
  220.         y=y/256;buf[5]=y%256;y-=buf[5];
  221.         y=y/256;buf[6]=y%256;y-=buf[6];
  222.         y=y/256;buf[7]=y%256;
  223.  
  224.         if(x<0) buf[7]|=0x80;
  225. }
  226.  
  227. int main(int argc,char *argv[])
  228. {
  229.         int fd;
  230.         u_char *old,*_new;
  231.         off_t oldsize,newsize;
  232.         off_t *I,*V;
  233.         off_t scan,pos,len;
  234.         off_t lastscan,lastpos,lastoffset;
  235.         off_t oldscore,scsc;
  236.         off_t s,Sf,lenf,Sb,lenb;
  237.         off_t overlap,Ss,lens;
  238.         off_t i;
  239.         off_t dblen,eblen;
  240.         u_char *db,*eb;
  241.         u_char buf[8];
  242.         u_char header[32];
  243.         FILE * pf;
  244.         BZFILE * pfbz2;
  245.         int bz2err;
  246.  
  247.         if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);
  248.  
  249.         /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
  250.                 that we never try to malloc(0) and get a NULL pointer */
  251.         //org:
  252.         //if(((fd=open(argv[1],O_RDONLY,0))<0) ||
  253.         //      ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
  254.         //      ((old=malloc(oldsize+1))==NULL) ||
  255.         //      (lseek(fd,0,SEEK_SET)!=0) ||
  256.         //      (read(fd,old,oldsize)!=oldsize) ||
  257.         //      (close(fd)==-1)) err(1,"%s",argv[1]);
  258.         //new:
  259.         //Read in chunks, don't rely on read always returns full data!
  260.         if(((fd=open(argv[1],O_RDONLY|O_BINARY|O_NOINHERIT,0))<0) ||
  261.                 ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
  262.                 ((old=(u_char*)malloc(oldsize+1))==NULL) ||
  263.                 (lseek(fd,0,SEEK_SET)!=0))
  264.                                 err(1,"%s",argv[1]);
  265.         int r=oldsize;
  266.         while (r>0 && (i=read(fd,old+oldsize-r,r))>0) r-=i;
  267.         if (r>0 || close(fd)==-1) err(1,"%s",argv[1]);
  268.  
  269.  
  270.         if(((I=(off_t*)malloc((oldsize+1)*sizeof(off_t)))==NULL) ||
  271.                 ((V=(off_t*)malloc((oldsize+1)*sizeof(off_t)))==NULL)) err(1,NULL);
  272.  
  273.         qsufsort(I,V,old,oldsize);
  274.  
  275.         free(V);
  276.  
  277.         /* Allocate newsize+1 bytes instead of newsize bytes to ensure
  278.                 that we never try to malloc(0) and get a NULL pointer */
  279.         //org:
  280.         //if(((fd=open(argv[2],O_RDONLY,0))<0) ||
  281.         //      ((newsize=lseek(fd,0,SEEK_END))==-1) ||
  282.         //      ((_new=malloc(newsize+1))==NULL) ||
  283.         //      (lseek(fd,0,SEEK_SET)!=0) ||
  284.         //      (read(fd,_new,newsize)!=newsize) ||
  285.         //      (close(fd)==-1)) err(1,"%s",argv[2]);
  286.         //new:
  287.         //Read in chunks, don't rely on read always returns full data!
  288.         if(((fd=open(argv[2],O_RDONLY|O_BINARY|O_NOINHERIT,0))<0) ||
  289.                 ((newsize=lseek(fd,0,SEEK_END))==-1) ||
  290.                 ((_new=(u_char*)malloc(newsize+1))==NULL) ||
  291.                 (lseek(fd,0,SEEK_SET)!=0))
  292.                                 err(1,"%s",argv[2]);
  293.  
  294.         r=newsize;
  295.         while (r>0 && (i=read(fd,_new+newsize-r,r))>0) r-=i;
  296.         if (r>0 || close(fd)==-1) err(1,"%s",argv[1]);
  297.  
  298.         if(((db=(u_char*)malloc(newsize+1))==NULL) ||
  299.                 ((eb=(u_char*)malloc(newsize+1))==NULL)) err(1,NULL);
  300.         dblen=0;
  301.         eblen=0;
  302.  
  303.         /* Create the patch file */
  304.         //org:
  305.         //if ((pf = fopen(argv[3], "w")) == NULL)
  306.         //new:
  307.         //if((fd=open(argv[3],O_CREAT|O_TRUNC|O_WRONLY|O_BINARY|O_NOINHERIT,0666))<0)
  308.         if ((pf = fopen(argv[3], "wb")) == NULL)
  309.                 err(1,"%s",argv[3]);
  310.  
  311.         /* Header is
  312.                 0       8        "BSDIFF40"
  313.                 8       8       length of bzip2ed ctrl block
  314.                 16      8       length of bzip2ed diff block
  315.                 24      8       length of new file */
  316.         /* File is
  317.                 0       32      Header
  318.                 32      ??      Bzip2ed ctrl block
  319.                 ??      ??      Bzip2ed diff block
  320.                 ??      ??      Bzip2ed extra block */
  321.         memcpy(header,"BSDIFF40",8);
  322.         offtout(0, header + 8);
  323.         offtout(0, header + 16);
  324.         offtout(newsize, header + 24);
  325.         if (fwrite(header, 32, 1, pf) != 1)
  326.                 err(1, "fwrite(%s)", argv[3]);
  327.  
  328.         /* Compute the differences, writing ctrl as we go */
  329.         if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
  330.                 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
  331.         scan=0;len=0;
  332.         lastscan=0;lastpos=0;lastoffset=0;
  333.         while(scan<newsize) {
  334.                 oldscore=0;
  335.  
  336.                 for(scsc=scan+=len;scan<newsize;scan++) {
  337.                         len=search(I,old,oldsize,_new+scan,newsize-scan,
  338.                                         0,oldsize,&pos);
  339.  
  340.                         for(;scsc<scan+len;scsc++)
  341.                         if((scsc+lastoffset<oldsize) &&
  342.                                 (old[scsc+lastoffset] == _new[scsc]))
  343.                                 oldscore++;
  344.  
  345.                         if(((len==oldscore) && (len!=0)) ||
  346.                                 (len>oldscore+8)) break;
  347.  
  348.                         if((scan+lastoffset<oldsize) &&
  349.                                 (old[scan+lastoffset] == _new[scan]))
  350.                                 oldscore--;
  351.                 };
  352.  
  353.                 if((len!=oldscore) || (scan==newsize)) {
  354.                         s=0;Sf=0;lenf=0;
  355.                         for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
  356.                                 if(old[lastpos+i]==_new[lastscan+i]) s++;
  357.                                 i++;
  358.                                 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
  359.                         };
  360.  
  361.                         lenb=0;
  362.                         if(scan<newsize) {
  363.                                 s=0;Sb=0;
  364.                                 for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) {
  365.                                         if(old[pos-i]==_new[scan-i]) s++;
  366.                                         if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
  367.                                 };
  368.                         };
  369.  
  370.                         if(lastscan+lenf>scan-lenb) {
  371.                                 overlap=(lastscan+lenf)-(scan-lenb);
  372.                                 s=0;Ss=0;lens=0;
  373.                                 for(i=0;i<overlap;i++) {
  374.                                         if(_new[lastscan+lenf-overlap+i]==
  375.                                            old[lastpos+lenf-overlap+i]) s++;
  376.                                         if(_new[scan-lenb+i]==
  377.                                            old[pos-lenb+i]) s--;
  378.                                         if(s>Ss) { Ss=s; lens=i+1; };
  379.                                 };
  380.  
  381.                                 lenf+=lens-overlap;
  382.                                 lenb-=lens;
  383.                         };
  384.  
  385.                         for(i=0;i<lenf;i++)
  386.                                 db[dblen+i]=_new[lastscan+i]-old[lastpos+i];
  387.                         for(i=0;i<(scan-lenb)-(lastscan+lenf);i++)
  388.                                 eb[eblen+i]=_new[lastscan+lenf+i];
  389.  
  390.                         dblen+=lenf;
  391.                         eblen+=(scan-lenb)-(lastscan+lenf);
  392.  
  393.                         offtout(lenf,buf);
  394.                         BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
  395.                         if (bz2err != BZ_OK)
  396.                                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  397.  
  398.                         offtout((scan-lenb)-(lastscan+lenf),buf);
  399.                         BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
  400.                         if (bz2err != BZ_OK)
  401.                                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  402.  
  403.                         offtout((pos-lenb)-(lastpos+lenf),buf);
  404.                         BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
  405.                         if (bz2err != BZ_OK)
  406.                                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  407.  
  408.                         lastscan=scan-lenb;
  409.                         lastpos=pos-lenb;
  410.                         lastoffset=pos-scan;
  411.                 };
  412.         };
  413.         BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
  414.         if (bz2err != BZ_OK)
  415.                 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
  416.  
  417.         /* Compute size of compressed ctrl data */
  418.         if ((len = ftell(pf)) == -1)
  419.                 err(1, "ftello");
  420.         offtout(len-32, header + 8);
  421.  
  422.         /* Write compressed diff data */
  423.         if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
  424.                 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
  425.         BZ2_bzWrite(&bz2err, pfbz2, db, dblen);
  426.         if (bz2err != BZ_OK)
  427.                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  428.         BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
  429.         if (bz2err != BZ_OK)
  430.                 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
  431.  
  432.         /* Compute size of compressed diff data */
  433.         if ((newsize = ftell(pf)) == -1)
  434.                 err(1, "ftello");
  435.         offtout(newsize - len, header + 16);
  436.  
  437.         /* Write compressed extra data */
  438.         if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
  439.                 errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
  440.         BZ2_bzWrite(&bz2err, pfbz2, eb, eblen);
  441.         if (bz2err != BZ_OK)
  442.                 errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
  443.         BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
  444.         if (bz2err != BZ_OK)
  445.                 errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
  446.  
  447.         /* Seek to the beginning, write the header, and close the file */
  448.         if (fseek(pf, 0, SEEK_SET))
  449.                 err(1, "fseeko");
  450.         if (fwrite(header, 32, 1, pf) != 1)
  451.                 err(1, "fwrite(%s)", argv[3]);
  452.         if (fclose(pf))
  453.                 err(1, "fclose");
  454.  
  455.         /* Free the memory we used */
  456.         free(db);
  457.         free(eb);
  458.         free(I);
  459.         free(old);
  460.         free(_new);
  461.  
  462.         return 0;
  463. }
  464.