Add libmar to build update tools to the repo.
[working/Evergreen.git] / Open-ILS / xul / staff_client / external / libmar / tool / bsdiff.c
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  * Modified 18 March 2013 by Jason Stephenson <jason@sigio.com>.
29  *
30  * Modifications to make it compatible with the output of Mozilla's mbsdiff:
31  *
32  * Switch from 64 bit off_t to 32 bit int32_t.
33  * Don't bzip2 the output blocks.
34  * Use the modified header that Mozilla's bspatch expects.
35  * Add crc32 of the original file to the header.
36  * Use 32-bit ftell and fseek instead of ftello and fseeko.
37  */
38
39 #include <sys/types.h>
40 #include <err.h>
41 #include <fcntl.h>
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <netinet/in.h>
46 #include <unistd.h>
47
48 /* Calculate the crc32. */
49 extern uint32_t
50 crc32(const unsigned char *buf, uint32_t len);
51
52 #define MIN(x,y) (((x)<(y)) ? (x) : (y))
53
54 static void split(int32_t *I,int32_t *V,int32_t start,int32_t len,int32_t h)
55 {
56         int32_t i,j,k,x,tmp,jj,kk;
57
58         if(len<16) {
59                 for(k=start;k<start+len;k+=j) {
60                         j=1;x=V[I[k]+h];
61                         for(i=1;k+i<start+len;i++) {
62                                 if(V[I[k+i]+h]<x) {
63                                         x=V[I[k+i]+h];
64                                         j=0;
65                                 };
66                                 if(V[I[k+i]+h]==x) {
67                                         tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
68                                         j++;
69                                 };
70                         };
71                         for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
72                         if(j==1) I[k]=-1;
73                 };
74                 return;
75         };
76
77         x=V[I[start+len/2]+h];
78         jj=0;kk=0;
79         for(i=start;i<start+len;i++) {
80                 if(V[I[i]+h]<x) jj++;
81                 if(V[I[i]+h]==x) kk++;
82         };
83         jj+=start;kk+=jj;
84
85         i=start;j=0;k=0;
86         while(i<jj) {
87                 if(V[I[i]+h]<x) {
88                         i++;
89                 } else if(V[I[i]+h]==x) {
90                         tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
91                         j++;
92                 } else {
93                         tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
94                         k++;
95                 };
96         };
97
98         while(jj+j<kk) {
99                 if(V[I[jj+j]+h]==x) {
100                         j++;
101                 } else {
102                         tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
103                         k++;
104                 };
105         };
106
107         if(jj>start) split(I,V,start,jj-start,h);
108
109         for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
110         if(jj==kk-1) I[jj]=-1;
111
112         if(start+len>kk) split(I,V,kk,start+len-kk,h);
113 }
114
115 static void qsufsort(int32_t *I,int32_t *V,u_char *old,int32_t oldsize)
116 {
117         int32_t buckets[256];
118         int32_t i,h,len;
119
120         for(i=0;i<256;i++) buckets[i]=0;
121         for(i=0;i<oldsize;i++) buckets[old[i]]++;
122         for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
123         for(i=255;i>0;i--) buckets[i]=buckets[i-1];
124         buckets[0]=0;
125
126         for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
127         I[0]=oldsize;
128         for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
129         V[oldsize]=0;
130         for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
131         I[0]=-1;
132
133         for(h=1;I[0]!=-(oldsize+1);h+=h) {
134                 len=0;
135                 for(i=0;i<oldsize+1;) {
136                         if(I[i]<0) {
137                                 len-=I[i];
138                                 i-=I[i];
139                         } else {
140                                 if(len) I[i-len]=-len;
141                                 len=V[I[i]]+1-i;
142                                 split(I,V,i,len,h);
143                                 i+=len;
144                                 len=0;
145                         };
146                 };
147                 if(len) I[i-len]=-len;
148         };
149
150         for(i=0;i<oldsize+1;i++) I[V[i]]=i;
151 }
152
153 static int32_t matchlen(u_char *old,int32_t oldsize,u_char *new,int32_t newsize)
154 {
155         int32_t i;
156
157         for(i=0;(i<oldsize)&&(i<newsize);i++)
158                 if(old[i]!=new[i]) break;
159
160         return i;
161 }
162
163 static int32_t search(int32_t *I,u_char *old,int32_t oldsize,
164                 u_char *new,int32_t newsize,int32_t st,int32_t en,int32_t *pos)
165 {
166         int32_t x,y;
167
168         if(en-st<2) {
169                 x=matchlen(old+I[st],oldsize-I[st],new,newsize);
170                 y=matchlen(old+I[en],oldsize-I[en],new,newsize);
171
172                 if(x>y) {
173                         *pos=I[st];
174                         return x;
175                 } else {
176                         *pos=I[en];
177                         return y;
178                 }
179         };
180
181         x=st+(en-st)/2;
182         if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) {
183                 return search(I,old,oldsize,new,newsize,x,en,pos);
184         } else {
185                 return search(I,old,oldsize,new,newsize,st,x,pos);
186         };
187 }
188
189 int main(int argc,char *argv[])
190 {
191         int fd;
192         u_char *old,*new;
193         int32_t oldsize,newsize;
194         int32_t *I,*V;
195         int32_t scan,pos,len;
196         int32_t lastscan,lastpos,lastoffset;
197         int32_t oldscore,scsc;
198         int32_t s,Sf,lenf,Sb,lenb;
199         int32_t overlap,Ss,lens;
200         int32_t i;
201         int32_t dblen,eblen;
202         u_char *db,*eb;
203         u_char header[32];
204         FILE * pf;
205         uint32_t crcVal;
206         int32_t outVal; /* place holder for result of htonl */
207
208         if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);
209
210         /* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
211                 that we never try to malloc(0) and get a NULL pointer */
212         if(((fd=open(argv[1],O_RDONLY,0))<0) ||
213                 ((oldsize=lseek(fd,0,SEEK_END))==-1) ||
214                 ((old=malloc(oldsize+1))==NULL) ||
215                 (lseek(fd,0,SEEK_SET)!=0) ||
216                 (read(fd,old,oldsize)!=oldsize) ||
217                 (close(fd)==-1)) err(1,"%s",argv[1]);
218
219         if(((I=malloc((oldsize+1)*sizeof(int32_t)))==NULL) ||
220                 ((V=malloc((oldsize+1)*sizeof(int32_t)))==NULL)) err(1,NULL);
221
222         /* Calculate the old file's crc32 value. */
223         crcVal = crc32(old, oldsize);
224
225         qsufsort(I,V,old,oldsize);
226
227         free(V);
228
229         /* Allocate newsize+1 bytes instead of newsize bytes to ensure
230                 that we never try to malloc(0) and get a NULL pointer */
231         if(((fd=open(argv[2],O_RDONLY,0))<0) ||
232                 ((newsize=lseek(fd,0,SEEK_END))==-1) ||
233                 ((new=malloc(newsize+1))==NULL) ||
234                 (lseek(fd,0,SEEK_SET)!=0) ||
235                 (read(fd,new,newsize)!=newsize) ||
236                 (close(fd)==-1)) err(1,"%s",argv[2]);
237
238         if(((db=malloc(newsize+1))==NULL) ||
239                 ((eb=malloc(newsize+1))==NULL)) err(1,NULL);
240         dblen=0;
241         eblen=0;
242
243         /* Create the patch file */
244         if ((pf = fopen(argv[3], "w")) == NULL)
245                 err(1, "%s", argv[3]);
246
247         /* This is the modified header used by Mozilla's hacked bspatch. It
248          * doesn't actually bzip2 anything despite what the documentation on
249          * the wiki implies. */
250         /* Header is
251                 0       8        "MBDIFF10"
252     8 4  length of the file to be patched
253     12 4 crc32 of file to be patched
254     16 4 length of the new file
255                 20 4 length of ctrl block
256                 24 4 length of diff block
257     28 4 length of extra block
258         /* File is
259                 0       32      Header
260                 32      ??      ctrl block
261                 ??      ??      diff block
262                 ??      ??      extra block */
263         memcpy(header, "MBDIFF10", 8);
264         outVal = htonl(oldsize);
265         memcpy(header + 8, &outVal, 4);
266         outVal = htonl(crcVal);
267         memcpy(header + 12, &outVal, 4);
268         outVal = htonl(newsize);
269         memcpy(header + 16, &outVal, 4);
270         memcpy(header + 20, 0, 12);
271         if (fwrite(header, 32, 1, pf) != 1)
272                 err(1, "fwrite(%s)", argv[3]);
273
274         /* Compute the differences, writing ctrl as we go */
275         scan=0;len=0;
276         lastscan=0;lastpos=0;lastoffset=0;
277         while(scan<newsize) {
278                 oldscore=0;
279
280                 for(scsc=scan+=len;scan<newsize;scan++) {
281                         len=search(I,old,oldsize,new+scan,newsize-scan,
282                                         0,oldsize,&pos);
283
284                         for(;scsc<scan+len;scsc++)
285                         if((scsc+lastoffset<oldsize) &&
286                                 (old[scsc+lastoffset] == new[scsc]))
287                                 oldscore++;
288
289                         if(((len==oldscore) && (len!=0)) || 
290                                 (len>oldscore+8)) break;
291
292                         if((scan+lastoffset<oldsize) &&
293                                 (old[scan+lastoffset] == new[scan]))
294                                 oldscore--;
295                 };
296
297                 if((len!=oldscore) || (scan==newsize)) {
298                         s=0;Sf=0;lenf=0;
299                         for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
300                                 if(old[lastpos+i]==new[lastscan+i]) s++;
301                                 i++;
302                                 if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; };
303                         };
304
305                         lenb=0;
306                         if(scan<newsize) {
307                                 s=0;Sb=0;
308                                 for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) {
309                                         if(old[pos-i]==new[scan-i]) s++;
310                                         if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; };
311                                 };
312                         };
313
314                         if(lastscan+lenf>scan-lenb) {
315                                 overlap=(lastscan+lenf)-(scan-lenb);
316                                 s=0;Ss=0;lens=0;
317                                 for(i=0;i<overlap;i++) {
318                                         if(new[lastscan+lenf-overlap+i]==
319                                            old[lastpos+lenf-overlap+i]) s++;
320                                         if(new[scan-lenb+i]==
321                                            old[pos-lenb+i]) s--;
322                                         if(s>Ss) { Ss=s; lens=i+1; };
323                                 };
324
325                                 lenf+=lens-overlap;
326                                 lenb-=lens;
327                         };
328
329                         for(i=0;i<lenf;i++)
330                                 db[dblen+i]=new[lastscan+i]-old[lastpos+i];
331                         for(i=0;i<(scan-lenb)-(lastscan+lenf);i++)
332                                 eb[eblen+i]=new[lastscan+lenf+i];
333
334                         dblen+=lenf;
335                         eblen+=(scan-lenb)-(lastscan+lenf);
336
337                         outVal = htonl(lenf);
338                         if (fwrite(&outVal, 4, 1, pf) != 1)
339                                 err(1, "fwrite(%s)", argv[3]);
340
341                         outVal = htonl((scan-lenb)-(lastscan+lenf));
342                         if (fwrite(&outVal, 4, 1, pf) != 1)
343                                 err(1, "fwrite(%s)", argv[3]);
344
345                         outVal = htonl((pos-lenb)-(lastpos+lenf));
346                         if (fwrite(&outVal, 4, 1, pf) != 1)
347                                 err(1, "fwrite(%s)", argv[3]);
348
349                         lastscan=scan-lenb;
350                         lastpos=pos-lenb;
351                         lastoffset=pos-scan;
352                 };
353         };
354
355         /* Compute size of ctrl data */
356         if ((len = ftell(pf)) == -1)
357                 err(1, "ftell");
358         outVal = htonl(len - 32);
359         memcpy(header + 20, &outVal, 4);
360
361         /* Write the diff data */
362         if (fwrite(db, 1, dblen, pf) != dblen)
363                 err(1, "fwrite(%s)", argv[3]);
364
365         /* Size of diff data */
366         outVal = htonl(dblen);
367         memcpy(header + 24, &outVal, 4);
368
369         /* Write extra data */
370         if (fwrite(eb, 1, eblen, pf) != eblen)
371                 err(1, "fwrite(%s)", argv[3]);
372
373         /* Size of extra data */
374         outVal = htonl(eblen);
375         memcpy(header + 28, &outVal, 4);
376
377         /* Seek to the beginning, write the header, and close the file */
378         if (fseek(pf, 0, SEEK_SET))
379                 err(1, "fseek");
380         if (fwrite(header, 32, 1, pf) != 1)
381                 err(1, "fwrite(%s)", argv[3]);
382         if (fclose(pf))
383                 err(1, "fclose");
384
385         /* Free the memory we used */
386         free(db);
387         free(eb);
388         free(I);
389         free(old);
390         free(new);
391
392         return 0;
393 }