xref: /freebsd/usr.bin/bsdiff/bsdiff/bsdiff.c (revision 38f0b757fd84d17d0fc24739a7cda160c4516d81)
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 #include <sys/cdefs.h>
28 __FBSDID("$FreeBSD$");
29 
30 #include <sys/types.h>
31 
32 #include <bzlib.h>
33 #include <err.h>
34 #include <fcntl.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <unistd.h>
39 
40 #ifndef O_BINARY
41 #define O_BINARY 0
42 #endif
43 
44 #define MIN(x,y) (((x)<(y)) ? (x) : (y))
45 
46 static void split(off_t *I,off_t *V,off_t start,off_t len,off_t h)
47 {
48 	off_t i,j,k,x,tmp,jj,kk;
49 
50 	if(len<16) {
51 		for(k=start;k<start+len;k+=j) {
52 			j=1;x=V[I[k]+h];
53 			for(i=1;k+i<start+len;i++) {
54 				if(V[I[k+i]+h]<x) {
55 					x=V[I[k+i]+h];
56 					j=0;
57 				};
58 				if(V[I[k+i]+h]==x) {
59 					tmp=I[k+j];I[k+j]=I[k+i];I[k+i]=tmp;
60 					j++;
61 				};
62 			};
63 			for(i=0;i<j;i++) V[I[k+i]]=k+j-1;
64 			if(j==1) I[k]=-1;
65 		};
66 		return;
67 	};
68 
69 	x=V[I[start+len/2]+h];
70 	jj=0;kk=0;
71 	for(i=start;i<start+len;i++) {
72 		if(V[I[i]+h]<x) jj++;
73 		if(V[I[i]+h]==x) kk++;
74 	};
75 	jj+=start;kk+=jj;
76 
77 	i=start;j=0;k=0;
78 	while(i<jj) {
79 		if(V[I[i]+h]<x) {
80 			i++;
81 		} else if(V[I[i]+h]==x) {
82 			tmp=I[i];I[i]=I[jj+j];I[jj+j]=tmp;
83 			j++;
84 		} else {
85 			tmp=I[i];I[i]=I[kk+k];I[kk+k]=tmp;
86 			k++;
87 		};
88 	};
89 
90 	while(jj+j<kk) {
91 		if(V[I[jj+j]+h]==x) {
92 			j++;
93 		} else {
94 			tmp=I[jj+j];I[jj+j]=I[kk+k];I[kk+k]=tmp;
95 			k++;
96 		};
97 	};
98 
99 	if(jj>start) split(I,V,start,jj-start,h);
100 
101 	for(i=0;i<kk-jj;i++) V[I[jj+i]]=kk-1;
102 	if(jj==kk-1) I[jj]=-1;
103 
104 	if(start+len>kk) split(I,V,kk,start+len-kk,h);
105 }
106 
107 static void qsufsort(off_t *I,off_t *V,u_char *old,off_t oldsize)
108 {
109 	off_t buckets[256];
110 	off_t i,h,len;
111 
112 	for(i=0;i<256;i++) buckets[i]=0;
113 	for(i=0;i<oldsize;i++) buckets[old[i]]++;
114 	for(i=1;i<256;i++) buckets[i]+=buckets[i-1];
115 	for(i=255;i>0;i--) buckets[i]=buckets[i-1];
116 	buckets[0]=0;
117 
118 	for(i=0;i<oldsize;i++) I[++buckets[old[i]]]=i;
119 	I[0]=oldsize;
120 	for(i=0;i<oldsize;i++) V[i]=buckets[old[i]];
121 	V[oldsize]=0;
122 	for(i=1;i<256;i++) if(buckets[i]==buckets[i-1]+1) I[buckets[i]]=-1;
123 	I[0]=-1;
124 
125 	for(h=1;I[0]!=-(oldsize+1);h+=h) {
126 		len=0;
127 		for(i=0;i<oldsize+1;) {
128 			if(I[i]<0) {
129 				len-=I[i];
130 				i-=I[i];
131 			} else {
132 				if(len) I[i-len]=-len;
133 				len=V[I[i]]+1-i;
134 				split(I,V,i,len,h);
135 				i+=len;
136 				len=0;
137 			};
138 		};
139 		if(len) I[i-len]=-len;
140 	};
141 
142 	for(i=0;i<oldsize+1;i++) I[V[i]]=i;
143 }
144 
145 static off_t matchlen(u_char *old,off_t oldsize,u_char *new,off_t newsize)
146 {
147 	off_t i;
148 
149 	for(i=0;(i<oldsize)&&(i<newsize);i++)
150 		if(old[i]!=new[i]) break;
151 
152 	return i;
153 }
154 
155 static off_t search(off_t *I,u_char *old,off_t oldsize,
156 		u_char *new,off_t newsize,off_t st,off_t en,off_t *pos)
157 {
158 	off_t x,y;
159 
160 	if(en-st<2) {
161 		x=matchlen(old+I[st],oldsize-I[st],new,newsize);
162 		y=matchlen(old+I[en],oldsize-I[en],new,newsize);
163 
164 		if(x>y) {
165 			*pos=I[st];
166 			return x;
167 		} else {
168 			*pos=I[en];
169 			return y;
170 		}
171 	};
172 
173 	x=st+(en-st)/2;
174 	if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) {
175 		return search(I,old,oldsize,new,newsize,x,en,pos);
176 	} else {
177 		return search(I,old,oldsize,new,newsize,st,x,pos);
178 	};
179 }
180 
181 static void offtout(off_t x,u_char *buf)
182 {
183 	off_t y;
184 
185 	if(x<0) y=-x; else y=x;
186 
187 		buf[0]=y%256;y-=buf[0];
188 	y=y/256;buf[1]=y%256;y-=buf[1];
189 	y=y/256;buf[2]=y%256;y-=buf[2];
190 	y=y/256;buf[3]=y%256;y-=buf[3];
191 	y=y/256;buf[4]=y%256;y-=buf[4];
192 	y=y/256;buf[5]=y%256;y-=buf[5];
193 	y=y/256;buf[6]=y%256;y-=buf[6];
194 	y=y/256;buf[7]=y%256;
195 
196 	if(x<0) buf[7]|=0x80;
197 }
198 
199 int main(int argc,char *argv[])
200 {
201 	int fd;
202 	u_char *old,*new;
203 	off_t oldsize,newsize;
204 	off_t *I,*V;
205 	off_t scan,pos,len;
206 	off_t lastscan,lastpos,lastoffset;
207 	off_t oldscore,scsc;
208 	off_t s,Sf,lenf,Sb,lenb;
209 	off_t overlap,Ss,lens;
210 	off_t i;
211 	off_t dblen,eblen;
212 	u_char *db,*eb;
213 	u_char buf[8];
214 	u_char header[32];
215 	FILE * pf;
216 	BZFILE * pfbz2;
217 	int bz2err;
218 
219 	if(argc!=4) errx(1,"usage: %s oldfile newfile patchfile\n",argv[0]);
220 
221 	/* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
222 		that we never try to malloc(0) and get a NULL pointer */
223 	if(((fd=open(argv[1],O_RDONLY|O_BINARY,0))<0) ||
224 		((oldsize=lseek(fd,0,SEEK_END))==-1) ||
225 		((old=malloc(oldsize+1))==NULL) ||
226 		(lseek(fd,0,SEEK_SET)!=0) ||
227 		(read(fd,old,oldsize)!=oldsize) ||
228 		(close(fd)==-1)) err(1,"%s",argv[1]);
229 
230 	if(((I=malloc((oldsize+1)*sizeof(off_t)))==NULL) ||
231 		((V=malloc((oldsize+1)*sizeof(off_t)))==NULL)) err(1,NULL);
232 
233 	qsufsort(I,V,old,oldsize);
234 
235 	free(V);
236 
237 	/* Allocate newsize+1 bytes instead of newsize bytes to ensure
238 		that we never try to malloc(0) and get a NULL pointer */
239 	if(((fd=open(argv[2],O_RDONLY|O_BINARY,0))<0) ||
240 		((newsize=lseek(fd,0,SEEK_END))==-1) ||
241 		((new=malloc(newsize+1))==NULL) ||
242 		(lseek(fd,0,SEEK_SET)!=0) ||
243 		(read(fd,new,newsize)!=newsize) ||
244 		(close(fd)==-1)) err(1,"%s",argv[2]);
245 
246 	if(((db=malloc(newsize+1))==NULL) ||
247 		((eb=malloc(newsize+1))==NULL)) err(1,NULL);
248 	dblen=0;
249 	eblen=0;
250 
251 	/* Create the patch file */
252 	if ((pf = fopen(argv[3], "wb")) == NULL)
253 		err(1, "%s", argv[3]);
254 
255 	/* Header is
256 		0	8	 "BSDIFF40"
257 		8	8	length of bzip2ed ctrl block
258 		16	8	length of bzip2ed diff block
259 		24	8	length of new file */
260 	/* File is
261 		0	32	Header
262 		32	??	Bzip2ed ctrl block
263 		??	??	Bzip2ed diff block
264 		??	??	Bzip2ed extra block */
265 	memcpy(header,"BSDIFF40",8);
266 	offtout(0, header + 8);
267 	offtout(0, header + 16);
268 	offtout(newsize, header + 24);
269 	if (fwrite(header, 32, 1, pf) != 1)
270 		err(1, "fwrite(%s)", argv[3]);
271 
272 	/* Compute the differences, writing ctrl as we go */
273 	if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
274 		errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
275 	scan=0;len=0;pos=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 			offtout(lenf,buf);
338 			BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
339 			if (bz2err != BZ_OK)
340 				errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
341 
342 			offtout((scan-lenb)-(lastscan+lenf),buf);
343 			BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
344 			if (bz2err != BZ_OK)
345 				errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
346 
347 			offtout((pos-lenb)-(lastpos+lenf),buf);
348 			BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
349 			if (bz2err != BZ_OK)
350 				errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
351 
352 			lastscan=scan-lenb;
353 			lastpos=pos-lenb;
354 			lastoffset=pos-scan;
355 		};
356 	};
357 	BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
358 	if (bz2err != BZ_OK)
359 		errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
360 
361 	/* Compute size of compressed ctrl data */
362 	if ((len = ftello(pf)) == -1)
363 		err(1, "ftello");
364 	offtout(len-32, header + 8);
365 
366 	/* Write compressed diff data */
367 	if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
368 		errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
369 	BZ2_bzWrite(&bz2err, pfbz2, db, dblen);
370 	if (bz2err != BZ_OK)
371 		errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
372 	BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
373 	if (bz2err != BZ_OK)
374 		errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
375 
376 	/* Compute size of compressed diff data */
377 	if ((newsize = ftello(pf)) == -1)
378 		err(1, "ftello");
379 	offtout(newsize - len, header + 16);
380 
381 	/* Write compressed extra data */
382 	if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
383 		errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
384 	BZ2_bzWrite(&bz2err, pfbz2, eb, eblen);
385 	if (bz2err != BZ_OK)
386 		errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
387 	BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
388 	if (bz2err != BZ_OK)
389 		errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
390 
391 	/* Seek to the beginning, write the header, and close the file */
392 	if (fseeko(pf, 0, SEEK_SET))
393 		err(1, "fseeko");
394 	if (fwrite(header, 32, 1, pf) != 1)
395 		err(1, "fwrite(%s)", argv[3]);
396 	if (fclose(pf))
397 		err(1, "fclose");
398 
399 	/* Free the memory we used */
400 	free(db);
401 	free(eb);
402 	free(I);
403 	free(old);
404 	free(new);
405 
406 	return 0;
407 }
408