xref: /freebsd/usr.bin/bsdiff/bsdiff/bsdiff.c (revision 273c26a3c3bea87a241d6879abd4f991db180bf0)
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 <errno.h>
35 #include <fcntl.h>
36 #include <limits.h>
37 #include <stdint.h>
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <unistd.h>
42 
43 #ifndef O_BINARY
44 #define O_BINARY 0
45 #endif
46 
47 #include "divsufsort64.h"
48 #define saidx_t saidx64_t
49 #define divsufsort divsufsort64
50 
51 #define MIN(x,y) (((x)<(y)) ? (x) : (y))
52 
53 static off_t matchlen(u_char *old,off_t oldsize,u_char *new,off_t newsize)
54 {
55 	off_t i;
56 
57 	for(i=0;(i<oldsize)&&(i<newsize);i++)
58 		if(old[i]!=new[i]) break;
59 
60 	return i;
61 }
62 
63 static off_t search(off_t *I,u_char *old,off_t oldsize,
64 		u_char *new,off_t newsize,off_t st,off_t en,off_t *pos)
65 {
66 	off_t x,y;
67 
68 	if(en-st<2) {
69 		x=matchlen(old+I[st],oldsize-I[st],new,newsize);
70 		y=matchlen(old+I[en],oldsize-I[en],new,newsize);
71 
72 		if(x>y) {
73 			*pos=I[st];
74 			return x;
75 		} else {
76 			*pos=I[en];
77 			return y;
78 		}
79 	}
80 
81 	x=st+(en-st)/2;
82 	if(memcmp(old+I[x],new,MIN(oldsize-I[x],newsize))<0) {
83 		return search(I,old,oldsize,new,newsize,x,en,pos);
84 	} else {
85 		return search(I,old,oldsize,new,newsize,st,x,pos);
86 	};
87 }
88 
89 static void offtout(off_t x,u_char *buf)
90 {
91 	off_t y;
92 
93 	if(x<0) y=-x; else y=x;
94 
95 		buf[0]=y%256;y-=buf[0];
96 	y=y/256;buf[1]=y%256;y-=buf[1];
97 	y=y/256;buf[2]=y%256;y-=buf[2];
98 	y=y/256;buf[3]=y%256;y-=buf[3];
99 	y=y/256;buf[4]=y%256;y-=buf[4];
100 	y=y/256;buf[5]=y%256;y-=buf[5];
101 	y=y/256;buf[6]=y%256;y-=buf[6];
102 	y=y/256;buf[7]=y%256;
103 
104 	if(x<0) buf[7]|=0x80;
105 }
106 
107 static void
108 usage(void)
109 {
110 
111 	fprintf(stderr, "usage: bsdiff oldfile newfile patchfile\n");
112 	exit(1);
113 }
114 
115 int main(int argc,char *argv[])
116 {
117 	int fd;
118 	u_char *old,*new;
119 	off_t oldsize,newsize;
120 	saidx_t *I;
121 	off_t scan,pos,len;
122 	off_t lastscan,lastpos,lastoffset;
123 	off_t oldscore,scsc;
124 	off_t s,Sf,lenf,Sb,lenb;
125 	off_t overlap,Ss,lens;
126 	off_t i;
127 	off_t dblen,eblen;
128 	u_char *db,*eb;
129 	u_char buf[8];
130 	u_char header[32];
131 	FILE * pf;
132 	BZFILE * pfbz2;
133 	int bz2err;
134 
135 	if (argc != 4)
136 		usage();
137 
138 	/* Allocate oldsize+1 bytes instead of oldsize bytes to ensure
139 		that we never try to malloc(0) and get a NULL pointer */
140 	if(((fd=open(argv[1],O_RDONLY|O_BINARY,0))<0) ||
141 	    ((oldsize=lseek(fd,0,SEEK_END))==-1))
142 		err(1, "%s", argv[1]);
143 
144 	if (oldsize > SSIZE_MAX ||
145 	    (uintmax_t)oldsize >= SIZE_T_MAX / sizeof(off_t) ||
146 	    oldsize == OFF_MAX) {
147 		errno = EFBIG;
148 		err(1, "%s", argv[1]);
149 	}
150 
151 	if (((old=malloc(oldsize+1))==NULL) ||
152 		(lseek(fd,0,SEEK_SET)!=0) ||
153 		(read(fd,old,oldsize)!=oldsize) ||
154 		(close(fd)==-1)) err(1,"%s",argv[1]);
155 
156 	if(((I=malloc((oldsize+1)*sizeof(saidx_t)))==NULL)) err(1,NULL);
157 
158 	if(divsufsort(old, I, oldsize)) err(1, "divsufsort");
159 
160 	/* Allocate newsize+1 bytes instead of newsize bytes to ensure
161 		that we never try to malloc(0) and get a NULL pointer */
162 	if(((fd=open(argv[2],O_RDONLY|O_BINARY,0))<0) ||
163 	    ((newsize=lseek(fd,0,SEEK_END))==-1))
164 		err(1, "%s", argv[2]);
165 
166 	if (newsize > SSIZE_MAX || (uintmax_t)newsize >= SIZE_T_MAX ||
167 	    newsize == OFF_MAX) {
168 		errno = EFBIG;
169 		err(1, "%s", argv[2]);
170 	}
171 
172 	if (((new=malloc(newsize+1))==NULL) ||
173 		(lseek(fd,0,SEEK_SET)!=0) ||
174 		(read(fd,new,newsize)!=newsize) ||
175 		(close(fd)==-1)) err(1,"%s",argv[2]);
176 
177 	if(((db=malloc(newsize+1))==NULL) ||
178 		((eb=malloc(newsize+1))==NULL)) err(1,NULL);
179 	dblen=0;
180 	eblen=0;
181 
182 	/* Create the patch file */
183 	if ((pf = fopen(argv[3], "wb")) == NULL)
184 		err(1, "%s", argv[3]);
185 
186 	/* Header is
187 		0	8	 "BSDIFF40"
188 		8	8	length of bzip2ed ctrl block
189 		16	8	length of bzip2ed diff block
190 		24	8	length of new file */
191 	/* File is
192 		0	32	Header
193 		32	??	Bzip2ed ctrl block
194 		??	??	Bzip2ed diff block
195 		??	??	Bzip2ed extra block */
196 	memcpy(header,"BSDIFF40",8);
197 	offtout(0, header + 8);
198 	offtout(0, header + 16);
199 	offtout(newsize, header + 24);
200 	if (fwrite(header, 32, 1, pf) != 1)
201 		err(1, "fwrite(%s)", argv[3]);
202 
203 	/* Compute the differences, writing ctrl as we go */
204 	if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
205 		errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
206 	scan=0;len=0;pos=0;
207 	lastscan=0;lastpos=0;lastoffset=0;
208 	while(scan<newsize) {
209 		oldscore=0;
210 
211 		for(scsc=scan+=len;scan<newsize;scan++) {
212 			len=search(I,old,oldsize,new+scan,newsize-scan,
213 					0,oldsize,&pos);
214 
215 			for(;scsc<scan+len;scsc++)
216 			if((scsc+lastoffset<oldsize) &&
217 				(old[scsc+lastoffset] == new[scsc]))
218 				oldscore++;
219 
220 			if(((len==oldscore) && (len!=0)) ||
221 				(len>oldscore+8)) break;
222 
223 			if((scan+lastoffset<oldsize) &&
224 				(old[scan+lastoffset] == new[scan]))
225 				oldscore--;
226 		}
227 
228 		if((len!=oldscore) || (scan==newsize)) {
229 			s=0;Sf=0;lenf=0;
230 			for(i=0;(lastscan+i<scan)&&(lastpos+i<oldsize);) {
231 				if(old[lastpos+i]==new[lastscan+i]) s++;
232 				i++;
233 				if(s*2-i>Sf*2-lenf) { Sf=s; lenf=i; }
234 			}
235 
236 			lenb=0;
237 			if(scan<newsize) {
238 				s=0;Sb=0;
239 				for(i=1;(scan>=lastscan+i)&&(pos>=i);i++) {
240 					if(old[pos-i]==new[scan-i]) s++;
241 					if(s*2-i>Sb*2-lenb) { Sb=s; lenb=i; }
242 				}
243 			}
244 
245 			if(lastscan+lenf>scan-lenb) {
246 				overlap=(lastscan+lenf)-(scan-lenb);
247 				s=0;Ss=0;lens=0;
248 				for(i=0;i<overlap;i++) {
249 					if(new[lastscan+lenf-overlap+i]==
250 					   old[lastpos+lenf-overlap+i]) s++;
251 					if(new[scan-lenb+i]==
252 					   old[pos-lenb+i]) s--;
253 					if(s>Ss) { Ss=s; lens=i+1; }
254 				}
255 
256 				lenf+=lens-overlap;
257 				lenb-=lens;
258 			}
259 
260 			for(i=0;i<lenf;i++)
261 				db[dblen+i]=new[lastscan+i]-old[lastpos+i];
262 			for(i=0;i<(scan-lenb)-(lastscan+lenf);i++)
263 				eb[eblen+i]=new[lastscan+lenf+i];
264 
265 			dblen+=lenf;
266 			eblen+=(scan-lenb)-(lastscan+lenf);
267 
268 			offtout(lenf,buf);
269 			BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
270 			if (bz2err != BZ_OK)
271 				errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
272 
273 			offtout((scan-lenb)-(lastscan+lenf),buf);
274 			BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
275 			if (bz2err != BZ_OK)
276 				errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
277 
278 			offtout((pos-lenb)-(lastpos+lenf),buf);
279 			BZ2_bzWrite(&bz2err, pfbz2, buf, 8);
280 			if (bz2err != BZ_OK)
281 				errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
282 
283 			lastscan=scan-lenb;
284 			lastpos=pos-lenb;
285 			lastoffset=pos-scan;
286 		}
287 	}
288 	BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
289 	if (bz2err != BZ_OK)
290 		errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
291 
292 	/* Compute size of compressed ctrl data */
293 	if ((len = ftello(pf)) == -1)
294 		err(1, "ftello");
295 	offtout(len-32, header + 8);
296 
297 	/* Write compressed diff data */
298 	if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
299 		errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
300 	BZ2_bzWrite(&bz2err, pfbz2, db, dblen);
301 	if (bz2err != BZ_OK)
302 		errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
303 	BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
304 	if (bz2err != BZ_OK)
305 		errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
306 
307 	/* Compute size of compressed diff data */
308 	if ((newsize = ftello(pf)) == -1)
309 		err(1, "ftello");
310 	offtout(newsize - len, header + 16);
311 
312 	/* Write compressed extra data */
313 	if ((pfbz2 = BZ2_bzWriteOpen(&bz2err, pf, 9, 0, 0)) == NULL)
314 		errx(1, "BZ2_bzWriteOpen, bz2err = %d", bz2err);
315 	BZ2_bzWrite(&bz2err, pfbz2, eb, eblen);
316 	if (bz2err != BZ_OK)
317 		errx(1, "BZ2_bzWrite, bz2err = %d", bz2err);
318 	BZ2_bzWriteClose(&bz2err, pfbz2, 0, NULL, NULL);
319 	if (bz2err != BZ_OK)
320 		errx(1, "BZ2_bzWriteClose, bz2err = %d", bz2err);
321 
322 	/* Seek to the beginning, write the header, and close the file */
323 	if (fseeko(pf, 0, SEEK_SET))
324 		err(1, "fseeko");
325 	if (fwrite(header, 32, 1, pf) != 1)
326 		err(1, "fwrite(%s)", argv[3]);
327 	if (fclose(pf))
328 		err(1, "fclose");
329 
330 	/* Free the memory we used */
331 	free(db);
332 	free(eb);
333 	free(I);
334 	free(old);
335 	free(new);
336 
337 	return 0;
338 }
339