xref: /openbsd-src/usr.bin/diff/diffreg.c (revision b4bca33fcd90e52689100cb9afe3534ba75f7b3f)
1 /*	$OpenBSD: diffreg.c,v 1.31 2003/07/09 00:07:44 millert Exp $	*/
2 
3 /*
4  * Copyright (C) Caldera International Inc.  2001-2002.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code and documentation must retain the above
11  *    copyright notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  * 3. All advertising materials mentioning features or use of this software
16  *    must display the following acknowledgement:
17  *	This product includes software developed or owned by Caldera
18  *	International, Inc.
19  * 4. Neither the name of Caldera International, Inc. nor the names of other
20  *    contributors may be used to endorse or promote products derived from
21  *    this software without specific prior written permission.
22  *
23  * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
24  * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
25  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
27  * IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT,
28  * INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
30  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
32  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
33  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  */
36 /*-
37  * Copyright (c) 1991, 1993
38  *	The Regents of the University of California.  All rights reserved.
39  *
40  * Redistribution and use in source and binary forms, with or without
41  * modification, are permitted provided that the following conditions
42  * are met:
43  * 1. Redistributions of source code must retain the above copyright
44  *    notice, this list of conditions and the following disclaimer.
45  * 2. Redistributions in binary form must reproduce the above copyright
46  *    notice, this list of conditions and the following disclaimer in the
47  *    documentation and/or other materials provided with the distribution.
48  * 3. Neither the name of the University nor the names of its contributors
49  *    may be used to endorse or promote products derived from this software
50  *    without specific prior written permission.
51  *
52  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62  * SUCH DAMAGE.
63  *
64  *	@(#)diffreg.c   8.1 (Berkeley) 6/6/93
65  */
66 
67 #ifndef lint
68 static const char rcsid[] = "$OpenBSD: diffreg.c,v 1.31 2003/07/09 00:07:44 millert Exp $";
69 #endif /* not lint */
70 
71 #include <sys/types.h>
72 #include <sys/stat.h>
73 #include <sys/wait.h>
74 
75 #include <ctype.h>
76 #include <err.h>
77 #include <fcntl.h>
78 #include <libgen.h>
79 #include <signal.h>
80 #include <stdio.h>
81 #include <stdlib.h>
82 #include <string.h>
83 #include <unistd.h>
84 
85 #include "diff.h"
86 #include "pathnames.h"
87 
88 /*
89  * diff - compare two files.
90  */
91 
92 /*
93  *	Uses an algorithm due to Harold Stone, which finds
94  *	a pair of longest identical subsequences in the two
95  *	files.
96  *
97  *	The major goal is to generate the match vector J.
98  *	J[i] is the index of the line in file1 corresponding
99  *	to line i file0. J[i] = 0 if there is no
100  *	such line in file1.
101  *
102  *	Lines are hashed so as to work in core. All potential
103  *	matches are located by sorting the lines of each file
104  *	on the hash (called ``value''). In particular, this
105  *	collects the equivalence classes in file1 together.
106  *	Subroutine equiv replaces the value of each line in
107  *	file0 by the index of the first element of its
108  *	matching equivalence in (the reordered) file1.
109  *	To save space equiv squeezes file1 into a single
110  *	array member in which the equivalence classes
111  *	are simply concatenated, except that their first
112  *	members are flagged by changing sign.
113  *
114  *	Next the indices that point into member are unsorted into
115  *	array class according to the original order of file0.
116  *
117  *	The cleverness lies in routine stone. This marches
118  *	through the lines of file0, developing a vector klist
119  *	of "k-candidates". At step i a k-candidate is a matched
120  *	pair of lines x,y (x in file0 y in file1) such that
121  *	there is a common subsequence of length k
122  *	between the first i lines of file0 and the first y
123  *	lines of file1, but there is no such subsequence for
124  *	any smaller y. x is the earliest possible mate to y
125  *	that occurs in such a subsequence.
126  *
127  *	Whenever any of the members of the equivalence class of
128  *	lines in file1 matable to a line in file0 has serial number
129  *	less than the y of some k-candidate, that k-candidate
130  *	with the smallest such y is replaced. The new
131  *	k-candidate is chained (via pred) to the current
132  *	k-1 candidate so that the actual subsequence can
133  *	be recovered. When a member has serial number greater
134  *	that the y of all k-candidates, the klist is extended.
135  *	At the end, the longest subsequence is pulled out
136  *	and placed in the array J by unravel
137  *
138  *	With J in hand, the matches there recorded are
139  *	check'ed against reality to assure that no spurious
140  *	matches have crept in due to hashing. If they have,
141  *	they are broken, and "jackpot" is recorded--a harmless
142  *	matter except that a true match for a spuriously
143  *	mated line may now be unnecessarily reported as a change.
144  *
145  *	Much of the complexity of the program comes simply
146  *	from trying to minimize core utilization and
147  *	maximize the range of doable problems by dynamically
148  *	allocating what is needed and reusing what is not.
149  *	The core requirements for problems larger than somewhat
150  *	are (in words) 2*length(file0) + length(file1) +
151  *	3*(number of k-candidates installed),  typically about
152  *	6n words for files of length n.
153  */
154 
155 struct cand {
156 	int x;
157 	int y;
158 	int pred;
159 } cand;
160 
161 struct line {
162 	int serial;
163 	int value;
164 } *file[2];
165 
166 static int  *J;			/* will be overlaid on class */
167 static int  *class;		/* will be overlaid on file[0] */
168 static int  *klist;		/* will be overlaid on file[0] after class */
169 static int  *member;		/* will be overlaid on file[1] */
170 static int   clen;
171 static int   inifdef;		/* whether or not we are in a #ifdef block */
172 static int   len[2];
173 static int   pref, suff;	/* length of prefix and suffix */
174 static int   slen[2];
175 static int   anychange;
176 static long *ixnew;		/* will be overlaid on file[1] */
177 static long *ixold;		/* will be overlaid on klist */
178 static struct cand *clist;	/* merely a free storage pot for candidates */
179 static struct line *sfile[2];	/* shortened by pruning common prefix/suffix */
180 static u_char *chrtran;		/* translation table for case-folding */
181 
182 static void fetch(long *, int, int, FILE *, char *, int);
183 static void output(char *, FILE *, char *, FILE *);
184 static void check(char *, FILE *, char *, FILE *);
185 static void range(int, int, char *);
186 static void dump_context_vec(FILE *, FILE *);
187 static void dump_unified_vec(FILE *, FILE *);
188 static void prepare(int, FILE *);
189 static void prune(void);
190 static void equiv(struct line *, int, struct line *, int, int *);
191 static void unravel(int);
192 static void unsort(struct line *, int, int *);
193 static void change(char *, FILE *, char *, FILE *, int, int, int, int);
194 static void sort(struct line *, int);
195 static int  asciifile(FILE *);
196 static int  newcand(int, int, int);
197 static int  search(int *, int, int);
198 static int  skipline(FILE *);
199 static int  stone(int *, int, int *, int *);
200 static int  readhash(FILE *);
201 static int  files_differ(FILE *, FILE *, int);
202 
203 /*
204  * chrtran points to one of 2 translation tables: cup2low if folding upper to
205  * lower case clow2low if not folding case
206  */
207 u_char clow2low[256] = {
208 	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
209 	0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
210 	0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
211 	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
212 	0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
213 	0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41,
214 	0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c,
215 	0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
216 	0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62,
217 	0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
218 	0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
219 	0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
220 	0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
221 	0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
222 	0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
223 	0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
224 	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
225 	0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
226 	0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
227 	0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
228 	0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
229 	0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
230 	0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
231 	0xfd, 0xfe, 0xff
232 };
233 
234 u_char cup2low[256] = {
235 	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
236 	0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
237 	0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
238 	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
239 	0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
240 	0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61,
241 	0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c,
242 	0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
243 	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62,
244 	0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
245 	0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
246 	0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
247 	0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
248 	0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
249 	0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
250 	0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
251 	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
252 	0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
253 	0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
254 	0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
255 	0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
256 	0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
257 	0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
258 	0xfd, 0xfe, 0xff
259 };
260 
261 int
262 diffreg(char *ofile1, char *ofile2, int flags)
263 {
264 	char *file1 = ofile1;
265 	char *file2 = ofile2;
266 	FILE *f1 = NULL;
267 	FILE *f2 = NULL;
268 	int rval = D_SAME;
269 	int i, ostdout = -1;
270 	pid_t pid = -1;
271 
272 	anychange = 0;
273 	chrtran = (iflag ? cup2low : clow2low);
274 	if (strcmp(file1, "-") == 0 && strcmp(file2, "-") == 0)
275 		goto notsame;
276 
277 	/* XXX - only make temp file for stdin if not seekable? (millert) */
278 	if (flags & D_EMPTY1)
279 		f1 = fopen(_PATH_DEVNULL, "r");
280 	else {
281 		if (S_ISDIR(stb1.st_mode)) {
282 			file1 = splice(file1, file2);
283 			if (stat(file1, &stb1) < 0) {
284 				warn("%s", file1);
285 				status |= 2;
286 				goto closem;
287 			}
288 		} else if (!S_ISREG(stb1.st_mode)) {
289 			file1 = copytemp(file1, 1);
290 			if (file1 == NULL || stat(file1, &stb1) < 0) {
291 				warn("%s", file1);
292 				status |= 2;
293 				goto closem;
294 			}
295 		}
296 		if (strcmp(file1, "-") == 0)
297 			f1 = stdin;
298 		else
299 			f1 = fopen(file1, "r");
300 	}
301 	if (f1 == NULL) {
302 		warn("%s", file1);
303 		status |= 2;
304 		goto closem;
305 	}
306 
307 	if (flags & D_EMPTY2)
308 		f2 = fopen(_PATH_DEVNULL, "r");
309 	else {
310 		if (S_ISDIR(stb2.st_mode)) {
311 			file2 = splice(file2, file1);
312 			if (stat(file2, &stb2) < 0) {
313 				warn("%s", file2);
314 				status |= 2;
315 				goto closem;
316 			}
317 		} else if (!S_ISREG(stb2.st_mode)) {
318 			file2 = copytemp(file2, 2);
319 			if (file2 == NULL || stat(file2, &stb2) < 0) {
320 				warn("%s", file2);
321 				status |= 2;
322 				goto closem;
323 			}
324 		}
325 		if (strcmp(file2, "-") == 0)
326 			f2 = stdin;
327 		else
328 			f2 = fopen(file2, "r");
329 	}
330 	if (f2 == NULL) {
331 		warn("%s", file2);
332 		status |= 2;
333 		goto closem;
334 	}
335 
336 	switch (files_differ(f1, f2, flags)) {
337 	case 0:
338 		goto closem;
339 	case 1:
340 		break;
341 	default:
342 		/* error */
343 		status |= 2;
344 		goto closem;
345 	}
346 
347 notsame:
348 	/*
349 	 * Files certainly differ at this point; set status accordingly
350 	 */
351 	status |= 1;
352 	rval = D_DIFFER;
353 	if (!asciifile(f1) || !asciifile(f2)) {
354 		rval = D_BINARY;
355 		goto closem;
356 	}
357 	if (format == D_BRIEF)
358 		goto closem;
359 	if (lflag) {
360 		/* redirect stdout to pr */
361 		int pfd[2];
362 		char *header;
363 		char *prargv[] = { "pr", "-h", NULL, "-f", NULL };
364 
365 		easprintf(&header, "%s %s %s", diffargs, file1, file2);
366 		prargv[2] = header;
367 		fflush(stdout);
368 		rewind(stdout);
369 		pipe(pfd);
370 		switch ((pid = fork())) {
371 		case -1:
372 			warnx("No more processes");
373 			status |= 2;
374 			free(header);
375 			return (D_ERROR);
376 		case 0:
377 			/* child */
378 			if (pfd[0] != STDIN_FILENO) {
379 				dup2(pfd[0], STDIN_FILENO);
380 				close(pfd[0]);
381 			}
382 			close(pfd[1]);
383 			execv(_PATH_PR, prargv);
384 			_exit(127);
385 		default:
386 			/* parent */
387 			if (pfd[1] != STDOUT_FILENO) {
388 				ostdout = dup(STDOUT_FILENO);
389 				dup2(pfd[1], STDOUT_FILENO);
390 				close(pfd[1]);
391 			}
392 			close(pfd[0]);
393 			rewind(stdout);
394 			free(header);
395 		}
396 	} else {
397 		if (flags & D_HEADER) {
398 			if (format == D_EDIT)
399 				printf("ed - %s << '-*-END-*-'\n",
400 				    basename(file1));
401 			else
402 				printf("%s %s %s\n", diffargs, file1, file2);
403 		}
404 	}
405 	prepare(0, f1);
406 	prepare(1, f2);
407 	prune();
408 	sort(sfile[0], slen[0]);
409 	sort(sfile[1], slen[1]);
410 
411 	member = (int *)file[1];
412 	equiv(sfile[0], slen[0], sfile[1], slen[1], member);
413 	member = erealloc(member, (slen[1] + 2) * sizeof(int));
414 
415 	class = (int *)file[0];
416 	unsort(sfile[0], slen[0], class);
417 	class = erealloc(class, (slen[0] + 2) * sizeof(int));
418 
419 	klist = emalloc((slen[0] + 2) * sizeof(int));
420 	clist = emalloc(sizeof(cand));
421 	i = stone(class, slen[0], member, klist);
422 	free(member);
423 	free(class);
424 
425 	J = erealloc(J, (len[0] + 2) * sizeof(int));
426 	unravel(klist[i]);
427 	free(clist);
428 	free(klist);
429 
430 	ixold = erealloc(ixold, (len[0] + 2) * sizeof(long));
431 	ixnew = erealloc(ixnew, (len[1] + 2) * sizeof(long));
432 	check(file1, f1, file2, f2);
433 	output(file1, f1, file2, f2);
434 	if (ostdout != -1) {
435 		int wstatus;
436 
437 		/* close the pipe to pr and restore stdout */
438 		fflush(stdout);
439 		rewind(stdout);
440 		if (ostdout != STDOUT_FILENO) {
441 			close(STDOUT_FILENO);
442 			dup2(ostdout, STDOUT_FILENO);
443 			close(ostdout);
444 		}
445 		waitpid(pid, &wstatus, 0);
446 	} else if ((flags & D_HEADER) && format == D_EDIT)
447 		printf("w\nq\n-*-END-*-\n");
448 closem:
449 	if (f1 != NULL)
450 		fclose(f1);
451 	if (f2 != NULL)
452 		fclose(f2);
453 	if (tempfiles[0] != NULL) {
454 		unlink(tempfiles[0]);
455 		free(tempfiles[0]);
456 		tempfiles[0] = NULL;
457 	} else if (file1 != ofile1)
458 		free(file1);
459 	if (tempfiles[1] != NULL) {
460 		unlink(tempfiles[1]);
461 		free(tempfiles[1]);
462 		tempfiles[1] = NULL;
463 	} else if (file2 != ofile2)
464 		free(file2);
465 	return (rval);
466 }
467 
468 /*
469  * Check to see if the given files differ.
470  * Returns 0 if they are the same, 1 if different, and -1 on error.
471  * XXX - could use code from cmp(1) [faster]
472  */
473 static int
474 files_differ(FILE *f1, FILE *f2, int flags)
475 {
476 	char buf1[BUFSIZ], buf2[BUFSIZ];
477 	size_t i, j;
478 
479 	if ((flags & (D_EMPTY1|D_EMPTY2)) || stb1.st_size != stb2.st_size ||
480 	    (stb1.st_mode & S_IFMT) != (stb2.st_mode & S_IFMT))
481 		return (1);
482 	for (;;) {
483 		i = fread(buf1, 1, sizeof(buf1), f1);
484 		j = fread(buf2, 1, sizeof(buf2), f2);
485 		if (i != j)
486 			return (1);
487 		if (i == 0 && j == 0) {
488 			if (ferror(f1) || ferror(f2))
489 				return (1);
490 			return (0);
491 		}
492 		if (memcmp(buf1, buf2, i) != 0)
493 			return (1);
494 	}
495 }
496 
497 char *tempfiles[2];
498 
499 /* XXX - pass back a FILE * too (millert) */
500 char *
501 copytemp(const char *file, int n)
502 {
503 	char buf[BUFSIZ], *tempdir, *tempfile;
504 	int i, ifd, ofd;
505 
506 	if (n != 1 && n != 2)
507 		return (NULL);
508 
509 	if (strcmp(file, "-") == 0)
510 		ifd = STDIN_FILENO;
511 	else if ((ifd = open(file, O_RDONLY, 0644)) < 0)
512 		return (NULL);
513 
514 	if ((tempdir = getenv("TMPDIR")) == NULL)
515 		tempdir = _PATH_TMP;
516 	if (asprintf(&tempfile, "%s/diff%d.XXXXXXXX", tempdir, n) == -1)
517 		return (NULL);
518 	tempfiles[n - 1] = tempfile;
519 
520 	signal(SIGHUP, quit);
521 	signal(SIGINT, quit);
522 	signal(SIGPIPE, quit);
523 	signal(SIGTERM, quit);
524 	signal(SIGPIPE, SIG_IGN);
525 	ofd = mkstemp(tempfile);
526 	if (ofd < 0)
527 		return (NULL);
528 	while ((i = read(ifd, buf, BUFSIZ)) > 0) {
529 		if (write(ofd, buf, i) != i)
530 			return (NULL);
531 	}
532 	close(ifd);
533 	close(ofd);
534 	return (tempfile);
535 }
536 
537 char *
538 splice(char *dir, char *file)
539 {
540 	char *tail, *buf;
541 
542 	tail = strrchr(file, '/');
543 	if (tail == NULL)
544 		tail = file;
545 	else
546 		tail++;
547 	easprintf(&buf, "%s/%s", dir, tail);
548 	return (buf);
549 }
550 
551 static void
552 prepare(int i, FILE *fd)
553 {
554 	struct line *p;
555 	int j, h;
556 
557 	rewind(fd);
558 	p = emalloc(3 * sizeof(struct line));
559 	for (j = 0; (h = readhash(fd));) {
560 		p = erealloc(p, (++j + 3) * sizeof(struct line));
561 		p[j].value = h;
562 	}
563 	len[i] = j;
564 	file[i] = p;
565 }
566 
567 static void
568 prune(void)
569 {
570 	int i, j;
571 
572 	for (pref = 0; pref < len[0] && pref < len[1] &&
573 	    file[0][pref + 1].value == file[1][pref + 1].value;
574 	    pref++)
575 		;
576 	for (suff = 0; suff < len[0] - pref && suff < len[1] - pref &&
577 	    file[0][len[0] - suff].value == file[1][len[1] - suff].value;
578 	    suff++)
579 		;
580 	for (j = 0; j < 2; j++) {
581 		sfile[j] = file[j] + pref;
582 		slen[j] = len[j] - pref - suff;
583 		for (i = 0; i <= slen[j]; i++)
584 			sfile[j][i].serial = i;
585 	}
586 }
587 
588 static void
589 equiv(struct line *a, int n, struct line *b, int m, int *c)
590 {
591 	int i, j;
592 
593 	i = j = 1;
594 	while (i <= n && j <= m) {
595 		if (a[i].value < b[j].value)
596 			a[i++].value = 0;
597 		else if (a[i].value == b[j].value)
598 			a[i++].value = j;
599 		else
600 			j++;
601 	}
602 	while (i <= n)
603 		a[i++].value = 0;
604 	b[m + 1].value = 0;
605 	j = 0;
606 	while (++j <= m) {
607 		c[j] = -b[j].serial;
608 		while (b[j + 1].value == b[j].value) {
609 			j++;
610 			c[j] = b[j].serial;
611 		}
612 	}
613 	c[j] = -1;
614 }
615 
616 static int
617 stone(int *a, int n, int *b, int *c)
618 {
619 	int i, k, y, j, l;
620 	int oldc, tc, oldl;
621 
622 	k = 0;
623 	c[0] = newcand(0, 0, 0);
624 	for (i = 1; i <= n; i++) {
625 		j = a[i];
626 		if (j == 0)
627 			continue;
628 		y = -b[j];
629 		oldl = 0;
630 		oldc = c[0];
631 		do {
632 			if (y <= clist[oldc].y)
633 				continue;
634 			l = search(c, k, y);
635 			if (l != oldl + 1)
636 				oldc = c[l - 1];
637 			if (l <= k) {
638 				if (clist[c[l]].y <= y)
639 					continue;
640 				tc = c[l];
641 				c[l] = newcand(i, y, oldc);
642 				oldc = tc;
643 				oldl = l;
644 			} else {
645 				c[l] = newcand(i, y, oldc);
646 				k++;
647 				break;
648 			}
649 		} while ((y = b[++j]) > 0);
650 	}
651 	return (k);
652 }
653 
654 static int
655 newcand(int x, int y, int pred)
656 {
657 	struct cand *q;
658 
659 	clist = erealloc(clist, ++clen * sizeof(cand));
660 	q = clist + clen - 1;
661 	q->x = x;
662 	q->y = y;
663 	q->pred = pred;
664 	return (clen - 1);
665 }
666 
667 static int
668 search(int *c, int k, int y)
669 {
670 	int i, j, l, t;
671 
672 	if (clist[c[k]].y < y)	/* quick look for typical case */
673 		return (k + 1);
674 	i = 0;
675 	j = k + 1;
676 	while (1) {
677 		l = i + j;
678 		if ((l >>= 1) <= i)
679 			break;
680 		t = clist[c[l]].y;
681 		if (t > y)
682 			j = l;
683 		else if (t < y)
684 			i = l;
685 		else
686 			return (l);
687 	}
688 	return (l + 1);
689 }
690 
691 static void
692 unravel(int p)
693 {
694 	struct cand *q;
695 	int i;
696 
697 	for (i = 0; i <= len[0]; i++)
698 		J[i] = i <= pref ? i :
699 		    i > len[0] - suff ? i + len[1] - len[0] : 0;
700 	for (q = clist + p; q->y != 0; q = clist + q->pred)
701 		J[q->x + pref] = q->y + pref;
702 }
703 
704 /*
705  * Check does double duty:
706  *  1.	ferret out any fortuitous correspondences due
707  *	to confounding by hashing (which result in "jackpot")
708  *  2.  collect random access indexes to the two files
709  */
710 static void
711 check(char *file1, FILE *f1, char *file2, FILE *f2)
712 {
713 	int i, j, jackpot, c, d;
714 	long ctold, ctnew;
715 
716 	rewind(f1);
717 	rewind(f2);
718 	j = 1;
719 	ixold[0] = ixnew[0] = 0;
720 	jackpot = 0;
721 	ctold = ctnew = 0;
722 	for (i = 1; i <= len[0]; i++) {
723 		if (J[i] == 0) {
724 			ixold[i] = ctold += skipline(f1);
725 			continue;
726 		}
727 		while (j < J[i]) {
728 			ixnew[j] = ctnew += skipline(f2);
729 			j++;
730 		}
731 		if (bflag || wflag || iflag) {
732 			for (;;) {
733 				c = getc(f1);
734 				d = getc(f2);
735 				ctold++;
736 				ctnew++;
737 				if (bflag && isspace(c) && isspace(d)) {
738 					do {
739 						if (c == '\n')
740 							break;
741 						ctold++;
742 					} while (isspace(c = getc(f1)));
743 					do {
744 						if (d == '\n')
745 							break;
746 						ctnew++;
747 					} while (isspace(d = getc(f2)));
748 				} else if (wflag) {
749 					while (isspace(c) && c != '\n') {
750 						c = getc(f1);
751 						ctold++;
752 					}
753 					while (isspace(d) && d != '\n') {
754 						d = getc(f2);
755 						ctnew++;
756 					}
757 				}
758 				if (chrtran[c] != chrtran[d]) {
759 					jackpot++;
760 					J[i] = 0;
761 					if (c != '\n')
762 						ctold += skipline(f1);
763 					if (d != '\n')
764 						ctnew += skipline(f2);
765 					break;
766 				}
767 				if (c == '\n')
768 					break;
769 			}
770 		} else {
771 			for (;;) {
772 				ctold++;
773 				ctnew++;
774 				if ((c = getc(f1)) != (d = getc(f2))) {
775 					/* jackpot++; */
776 					J[i] = 0;
777 					if (c != '\n')
778 						ctold += skipline(f1);
779 					if (d != '\n')
780 						ctnew += skipline(f2);
781 					break;
782 				}
783 				if (c == '\n')
784 					break;
785 			}
786 		}
787 		ixold[i] = ctold;
788 		ixnew[j] = ctnew;
789 		j++;
790 	}
791 	for (; j <= len[1]; j++)
792 		ixnew[j] = ctnew += skipline(f2);
793 	/*
794 	 * if (jackpot)
795 	 *	fprintf(stderr, "jackpot\n");
796 	 */
797 }
798 
799 /* shellsort CACM #201 */
800 static void
801 sort(struct line *a, int n)
802 {
803 	struct line *ai, *aim, w;
804 	int j, m = 0, k;
805 
806 	if (n == 0)
807 		return;
808 	for (j = 1; j <= n; j *= 2)
809 		m = 2 * j - 1;
810 	for (m /= 2; m != 0; m /= 2) {
811 		k = n - m;
812 		for (j = 1; j <= k; j++) {
813 			for (ai = &a[j]; ai > a; ai -= m) {
814 				aim = &ai[m];
815 				if (aim < ai)
816 					break;	/* wraparound */
817 				if (aim->value > ai[0].value ||
818 				    (aim->value == ai[0].value &&
819 					aim->serial > ai[0].serial))
820 					break;
821 				w.value = ai[0].value;
822 				ai[0].value = aim->value;
823 				aim->value = w.value;
824 				w.serial = ai[0].serial;
825 				ai[0].serial = aim->serial;
826 				aim->serial = w.serial;
827 			}
828 		}
829 	}
830 }
831 
832 static void
833 unsort(struct line *f, int l, int *b)
834 {
835 	int *a, i;
836 
837 	a = emalloc((l + 1) * sizeof(int));
838 	for (i = 1; i <= l; i++)
839 		a[f[i].serial] = f[i].value;
840 	for (i = 1; i <= l; i++)
841 		b[i] = a[i];
842 	free(a);
843 }
844 
845 static int
846 skipline(FILE *f)
847 {
848 	int i, c;
849 
850 	for (i = 1; (c = getc(f)) != '\n'; i++)
851 		if (c < 0)
852 			return (i);
853 	return (i);
854 }
855 
856 static void
857 output(char *file1, FILE *f1, char *file2, FILE *f2)
858 {
859 	int m, i0, i1, j0, j1;
860 
861 	rewind(f1);
862 	rewind(f2);
863 	m = len[0];
864 	J[0] = 0;
865 	J[m + 1] = len[1] + 1;
866 	if (format != D_EDIT) {
867 		for (i0 = 1; i0 <= m; i0 = i1 + 1) {
868 			while (i0 <= m && J[i0] == J[i0 - 1] + 1)
869 				i0++;
870 			j0 = J[i0 - 1] + 1;
871 			i1 = i0 - 1;
872 			while (i1 < m && J[i1 + 1] == 0)
873 				i1++;
874 			j1 = J[i1 + 1] - 1;
875 			J[i1] = j1;
876 			change(file1, f1, file2, f2, i0, i1, j0, j1);
877 		}
878 	} else {
879 		for (i0 = m; i0 >= 1; i0 = i1 - 1) {
880 			while (i0 >= 1 && J[i0] == J[i0 + 1] - 1 && J[i0] != 0)
881 				i0--;
882 			j0 = J[i0 + 1] - 1;
883 			i1 = i0 + 1;
884 			while (i1 > 1 && J[i1 - 1] == 0)
885 				i1--;
886 			j1 = J[i1 - 1] + 1;
887 			J[i1] = j1;
888 			change(file1, f1, file2, f2, i1, i0, j1, j0);
889 		}
890 	}
891 	if (m == 0)
892 		change(file1, f1, file2, f2, 1, 0, 1, len[1]);
893 	if (format == D_IFDEF) {
894 		for (;;) {
895 #define	c i0
896 			c = getc(f1);
897 			if (c < 0)
898 				return;
899 			putchar(c);
900 		}
901 #undef c
902 	}
903 	if (anychange != 0) {
904 		if (format == D_CONTEXT)
905 			dump_context_vec(f1, f2);
906 		else if (format == D_UNIFIED)
907 			dump_unified_vec(f1, f2);
908 	}
909 }
910 
911 /*
912  * The following struct is used to record change information when
913  * doing a "context" or "unified" diff.  (see routine "change" to
914  * understand the highly mnemonic field names)
915  */
916 struct context_vec {
917 	int a;			/* start line in old file */
918 	int b;			/* end line in old file */
919 	int c;			/* start line in new file */
920 	int d;			/* end line in new file */
921 };
922 
923 struct context_vec *context_vec_start, *context_vec_end, *context_vec_ptr;
924 
925 #define	MAX_CONTEXT	128
926 
927 /*
928  * Indicate that there is a difference between lines a and b of the from file
929  * to get to lines c to d of the to file.  If a is greater then b then there
930  * are no lines in the from file involved and this means that there were
931  * lines appended (beginning at b).  If c is greater than d then there are
932  * lines missing from the to file.
933  */
934 static void
935 change(char *file1, FILE *f1, char *file2, FILE *f2, int a, int b, int c, int d)
936 {
937 	if (format != D_IFDEF && a > b && c > d)
938 		return;
939 	if (anychange == 0) {
940 		anychange = 1;
941 		if (format == D_CONTEXT || format == D_UNIFIED) {
942 			printf("%s %s	%s", format == D_CONTEXT ? "***" : "---",
943 			   file1, ctime(&stb1.st_mtime));
944 			printf("%s %s	%s", format == D_CONTEXT ? "---" : "+++",
945 			    file2, ctime(&stb2.st_mtime));
946 			if (context_vec_start == NULL)
947 				context_vec_start = emalloc(MAX_CONTEXT *
948 				    sizeof(struct context_vec));
949 			context_vec_end = context_vec_start + MAX_CONTEXT;
950 			context_vec_ptr = context_vec_start - 1;
951 		}
952 	}
953 	if (format == D_CONTEXT || format == D_UNIFIED) {
954 		/*
955 		 * If this new change is within 'context' lines of
956 		 * the previous change, just add it to the change
957 		 * record.  If the record is full or if this
958 		 * change is more than 'context' lines from the previous
959 		 * change, dump the record, reset it & add the new change.
960 		 */
961 		if (context_vec_ptr >= context_vec_end ||
962 		    (context_vec_ptr >= context_vec_start &&
963 		    a > (context_vec_ptr->b + 2 * context) &&
964 		    c > (context_vec_ptr->d + 2 * context))) {
965 			if (format == D_CONTEXT)
966 				dump_context_vec(f1, f2);
967 			else
968 				dump_unified_vec(f1, f2);
969 		}
970 		context_vec_ptr++;
971 		context_vec_ptr->a = a;
972 		context_vec_ptr->b = b;
973 		context_vec_ptr->c = c;
974 		context_vec_ptr->d = d;
975 		return;
976 	}
977 	switch (format) {
978 
979 	case D_NORMAL:
980 	case D_EDIT:
981 		range(a, b, ",");
982 		putchar(a > b ? 'a' : c > d ? 'd' : 'c');
983 		if (format == D_NORMAL)
984 			range(c, d, ",");
985 		putchar('\n');
986 		break;
987 	case D_REVERSE:
988 		putchar(a > b ? 'a' : c > d ? 'd' : 'c');
989 		range(a, b, " ");
990 		putchar('\n');
991 		break;
992 	case D_NREVERSE:
993 		if (a > b)
994 			printf("a%d %d\n", b, d - c + 1);
995 		else {
996 			printf("d%d %d\n", a, b - a + 1);
997 			if (!(c > d))
998 				/* add changed lines */
999 				printf("a%d %d\n", b, d - c + 1);
1000 		}
1001 		break;
1002 	}
1003 	if (format == D_NORMAL || format == D_IFDEF) {
1004 		fetch(ixold, a, b, f1, "< ", 1);
1005 		if (a <= b && c <= d && format == D_NORMAL)
1006 			puts("---");
1007 	}
1008 	fetch(ixnew, c, d, f2, format == D_NORMAL ? "> " : "", 0);
1009 	if ((format == D_EDIT || format == D_REVERSE) && c <= d)
1010 		puts(".");
1011 	if (inifdef) {
1012 		printf("#endif /* %s */\n", ifdefname);
1013 		inifdef = 0;
1014 	}
1015 }
1016 
1017 static void
1018 range(int a, int b, char *separator)
1019 {
1020 	printf("%d", a > b ? b : a);
1021 	if (a < b)
1022 		printf("%s%d", separator, b);
1023 }
1024 
1025 static void
1026 fetch(long *f, int a, int b, FILE *lb, char *s, int oldfile)
1027 {
1028 	int i, j, c, col, nc;
1029 
1030 	/*
1031 	 * When doing #ifdef's, copy down to current line
1032 	 * if this is the first file, so that stuff makes it to output.
1033 	 */
1034 	if (format == D_IFDEF && oldfile) {
1035 		long curpos = ftell(lb);
1036 		/* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1037 		nc = f[a > b ? b : a - 1] - curpos;
1038 		for (i = 0; i < nc; i++)
1039 			putchar(getc(lb));
1040 	}
1041 	if (a > b)
1042 		return;
1043 	if (format == D_IFDEF) {
1044 		if (inifdef) {
1045 			printf("#else /* %s%s */\n",
1046 			    oldfile == 1 ? "!" : "", ifdefname);
1047 		} else {
1048 			if (oldfile)
1049 				printf("#ifndef %s\n", ifdefname);
1050 			else
1051 				printf("#ifdef %s\n", ifdefname);
1052 		}
1053 		inifdef = 1 + oldfile;
1054 	}
1055 	for (i = a; i <= b; i++) {
1056 		fseek(lb, f[i - 1], SEEK_SET);
1057 		nc = f[i] - f[i - 1];
1058 		if (format != D_IFDEF)
1059 			fputs(s, stdout);
1060 		col = 0;
1061 		for (j = 0; j < nc; j++) {
1062 			c = getc(lb);
1063 			if (c == '\t' && tflag)
1064 				do
1065 					putchar(' ');
1066 				while (++col & 7);
1067 			else {
1068 				putchar(c);
1069 				col++;
1070 			}
1071 		}
1072 	}
1073 }
1074 
1075 #define POW2			/* define only if HALFLONG is 2**n */
1076 #define HALFLONG 16
1077 #define low(x)	(x&((1L<<HALFLONG)-1))
1078 #define high(x)	(x>>HALFLONG)
1079 
1080 /*
1081  * hashing has the effect of
1082  * arranging line in 7-bit bytes and then
1083  * summing 1-s complement in 16-bit hunks
1084  */
1085 static int
1086 readhash(FILE *f)
1087 {
1088 	unsigned int shift;
1089 	int t, space;
1090 	long sum;
1091 
1092 	sum = 1;
1093 	space = 0;
1094 	if (!bflag && !wflag) {
1095 		if (iflag)
1096 			for (shift = 0; (t = getc(f)) != '\n'; shift += 7) {
1097 				if (t == -1)
1098 					return (0);
1099 				sum += (long)chrtran[t] << (shift
1100 #ifdef POW2
1101 				    &= HALFLONG - 1);
1102 #else
1103 				    %= HALFLONG);
1104 #endif
1105 			}
1106 		else
1107 			for (shift = 0; (t = getc(f)) != '\n'; shift += 7) {
1108 				if (t == -1)
1109 					return (0);
1110 				sum += (long)t << (shift
1111 #ifdef POW2
1112 				    &= HALFLONG - 1);
1113 #else
1114 				    %= HALFLONG);
1115 #endif
1116 			}
1117 	} else {
1118 		for (shift = 0;;) {
1119 			switch (t = getc(f)) {
1120 			case -1:
1121 				return (0);
1122 			case '\t':
1123 			case ' ':
1124 				space++;
1125 				continue;
1126 			default:
1127 				if (space && !wflag) {
1128 					shift += 7;
1129 					space = 0;
1130 				}
1131 				sum += (long)chrtran[t] << (shift
1132 #ifdef POW2
1133 				    &= HALFLONG - 1);
1134 #else
1135 				    %= HALFLONG);
1136 #endif
1137 				shift += 7;
1138 				continue;
1139 			case '\n':
1140 				break;
1141 			}
1142 			break;
1143 		}
1144 	}
1145 	sum = low(sum) + high(sum);
1146 	return ((short) low(sum) + (short) high(sum));
1147 }
1148 
1149 int
1150 asciifile(FILE *f)
1151 {
1152 	char buf[BUFSIZ], *cp;
1153 	int cnt;
1154 
1155 	if (aflag || f == NULL)
1156 		return (1);
1157 
1158 	rewind(f);
1159 	cnt = fread(buf, 1, sizeof(buf), f);
1160 	cp = buf;
1161 	while (--cnt >= 0)
1162 		if (*cp++ & 0200)
1163 			return (0);
1164 	return (1);
1165 }
1166 
1167 static __inline int min(int a, int b)
1168 {
1169 	return (a < b ? a : b);
1170 }
1171 
1172 static __inline int max(int a, int b)
1173 {
1174 	return (a > b ? a : b);
1175 }
1176 
1177 /* dump accumulated "context" diff changes */
1178 static void
1179 dump_context_vec(FILE *f1, FILE *f2)
1180 {
1181 	struct context_vec *cvp = context_vec_start;
1182 	int lowa, upb, lowc, upd, do_output;
1183 	int a, b, c, d;
1184 	char ch;
1185 
1186 	if (context_vec_start > context_vec_ptr)
1187 		return;
1188 
1189 	b = d = 0;		/* gcc */
1190 	lowa = max(1, cvp->a - context);
1191 	upb = min(len[0], context_vec_ptr->b + context);
1192 	lowc = max(1, cvp->c - context);
1193 	upd = min(len[1], context_vec_ptr->d + context);
1194 
1195 	printf("***************\n*** ");
1196 	range(lowa, upb, ",");
1197 	printf(" ****\n");
1198 
1199 	/*
1200 	 * Output changes to the "old" file.  The first loop suppresses
1201 	 * output if there were no changes to the "old" file (we'll see
1202 	 * the "old" lines as context in the "new" list).
1203 	 */
1204 	do_output = 0;
1205 	for (; cvp <= context_vec_ptr; cvp++)
1206 		if (cvp->a <= cvp->b) {
1207 			cvp = context_vec_start;
1208 			do_output++;
1209 			break;
1210 		}
1211 	if (do_output) {
1212 		while (cvp <= context_vec_ptr) {
1213 			a = cvp->a;
1214 			b = cvp->b;
1215 			c = cvp->c;
1216 			d = cvp->d;
1217 
1218 			if (a <= b && c <= d)
1219 				ch = 'c';
1220 			else
1221 				ch = (a <= b) ? 'd' : 'a';
1222 
1223 			if (ch == 'a')
1224 				fetch(ixold, lowa, b, f1, "  ", 0);
1225 			else {
1226 				fetch(ixold, lowa, a - 1, f1, "  ", 0);
1227 				fetch(ixold, a, b, f1,
1228 				    ch == 'c' ? "! " : "- ", 0);
1229 			}
1230 			lowa = b + 1;
1231 			cvp++;
1232 		}
1233 		fetch(ixold, b + 1, upb, f1, "  ", 0);
1234 	}
1235 	/* output changes to the "new" file */
1236 	printf("--- ");
1237 	range(lowc, upd, ",");
1238 	printf(" ----\n");
1239 
1240 	do_output = 0;
1241 	for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++)
1242 		if (cvp->c <= cvp->d) {
1243 			cvp = context_vec_start;
1244 			do_output++;
1245 			break;
1246 		}
1247 	if (do_output) {
1248 		while (cvp <= context_vec_ptr) {
1249 			a = cvp->a;
1250 			b = cvp->b;
1251 			c = cvp->c;
1252 			d = cvp->d;
1253 
1254 			if (a <= b && c <= d)
1255 				ch = 'c';
1256 			else
1257 				ch = (a <= b) ? 'd' : 'a';
1258 
1259 			if (ch == 'd')
1260 				fetch(ixnew, lowc, d, f2, "  ", 0);
1261 			else {
1262 				fetch(ixnew, lowc, c - 1, f2, "  ", 0);
1263 				fetch(ixnew, c, d, f2,
1264 				    ch == 'c' ? "! " : "+ ", 0);
1265 			}
1266 			lowc = d + 1;
1267 			cvp++;
1268 		}
1269 		fetch(ixnew, d + 1, upd, f2, "  ", 0);
1270 	}
1271 	context_vec_ptr = context_vec_start - 1;
1272 }
1273 
1274 /* dump accumulated "unified" diff changes */
1275 static void
1276 dump_unified_vec(FILE *f1, FILE *f2)
1277 {
1278 	struct context_vec *cvp = context_vec_start;
1279 	int lowa, upb, lowc, upd;
1280 	int a, b, c, d;
1281 	char ch;
1282 
1283 	if (context_vec_start > context_vec_ptr)
1284 		return;
1285 
1286 	b = d = 0;		/* gcc */
1287 	lowa = max(1, cvp->a - context);
1288 	upb = min(len[0], context_vec_ptr->b + context);
1289 	lowc = max(1, cvp->c - context);
1290 	upd = min(len[1], context_vec_ptr->d + context);
1291 
1292 	printf("@@ -%d,%d +%d,%d @@\n", lowa, upb - lowa + 1,
1293 	    lowc, upd - lowc + 1);
1294 
1295 	/*
1296 	 * Output changes in "unified" diff format--the old and new lines
1297 	 * are printed together.
1298 	 */
1299 	for (; cvp <= context_vec_ptr; cvp++) {
1300 		a = cvp->a;
1301 		b = cvp->b;
1302 		c = cvp->c;
1303 		d = cvp->d;
1304 
1305 		/*
1306 		 * c: both new and old changes
1307 		 * d: only changes in the old file
1308 		 * a: only changes in the new file
1309 		 */
1310 		if (a <= b && c <= d)
1311 			ch = 'c';
1312 		else
1313 			ch = (a <= b) ? 'd' : 'a';
1314 
1315 		switch (ch) {
1316 		case 'c':
1317 			fetch(ixold, lowa, a - 1, f1, " ", 0);
1318 			fetch(ixold, a, b, f1, "-", 0);
1319 			fetch(ixnew, c, d, f2, "+", 0);
1320 			break;
1321 		case 'd':
1322 			fetch(ixold, lowa, a - 1, f1, " ", 0);
1323 			fetch(ixold, a, b, f1, "-", 0);
1324 			break;
1325 		case 'a':
1326 			fetch(ixnew, lowc, c - 1, f2, " ", 0);
1327 			fetch(ixnew, c, d, f2, "+", 0);
1328 			break;
1329 		}
1330 		lowa = b + 1;
1331 		lowc = d + 1;
1332 	}
1333 	fetch(ixnew, d + 1, upd, f2, " ", 0);
1334 
1335 	context_vec_ptr = context_vec_start - 1;
1336 }
1337