1 /*	$OpenBSD: diffreg.c,v 1.91 2016/03/01 20:57:35 natano 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 #include <sys/stat.h>
68 #include <sys/wait.h>
69 #include <sys/queue.h>
70 
71 #include <ctype.h>
72 #include <err.h>
73 #include <errno.h>
74 #include <fcntl.h>
75 #include <paths.h>
76 #include <stdarg.h>
77 #include <stddef.h>
78 #include <stdint.h>
79 #include <stdio.h>
80 #include <stdlib.h>
81 #include <string.h>
82 #include <unistd.h>
83 #include <limits.h>
84 #include <sha1.h>
85 #include <zlib.h>
86 
87 #include "got_error.h"
88 #include "got_object.h"
89 #include "got_diff.h"
90 
91 #include "got_lib_diff.h"
92 
93 #define MINIMUM(a, b)	(((a) < (b)) ? (a) : (b))
94 #define MAXIMUM(a, b)	(((a) > (b)) ? (a) : (b))
95 
96 /*
97  * diff - compare two files.
98  */
99 
100 /*
101  *	Uses an algorithm due to Harold Stone, which finds
102  *	a pair of longest identical subsequences in the two
103  *	files.
104  *
105  *	The major goal is to generate the match vector J.
106  *	J[i] is the index of the line in file1 corresponding
107  *	to line i file0. J[i] = 0 if there is no
108  *	such line in file1.
109  *
110  *	Lines are hashed so as to work in core. All potential
111  *	matches are located by sorting the lines of each file
112  *	on the hash (called ``value''). In particular, this
113  *	collects the equivalence classes in file1 together.
114  *	Subroutine equiv replaces the value of each line in
115  *	file0 by the index of the first element of its
116  *	matching equivalence in (the reordered) file1.
117  *	To save space equiv squeezes file1 into a single
118  *	array member in which the equivalence classes
119  *	are simply concatenated, except that their first
120  *	members are flagged by changing sign.
121  *
122  *	Next the indices that point into member are unsorted into
123  *	array class according to the original order of file0.
124  *
125  *	The cleverness lies in routine stone. This marches
126  *	through the lines of file0, developing a vector klist
127  *	of "k-candidates". At step i a k-candidate is a matched
128  *	pair of lines x,y (x in file0 y in file1) such that
129  *	there is a common subsequence of length k
130  *	between the first i lines of file0 and the first y
131  *	lines of file1, but there is no such subsequence for
132  *	any smaller y. x is the earliest possible mate to y
133  *	that occurs in such a subsequence.
134  *
135  *	Whenever any of the members of the equivalence class of
136  *	lines in file1 matable to a line in file0 has serial number
137  *	less than the y of some k-candidate, that k-candidate
138  *	with the smallest such y is replaced. The new
139  *	k-candidate is chained (via pred) to the current
140  *	k-1 candidate so that the actual subsequence can
141  *	be recovered. When a member has serial number greater
142  *	that the y of all k-candidates, the klist is extended.
143  *	At the end, the longest subsequence is pulled out
144  *	and placed in the array J by unravel
145  *
146  *	With J in hand, the matches there recorded are
147  *	check'ed against reality to assure that no spurious
148  *	matches have crept in due to hashing. If they have,
149  *	they are broken, and "jackpot" is recorded--a harmless
150  *	matter except that a true match for a spuriously
151  *	mated line may now be unnecessarily reported as a change.
152  *
153  *	Much of the complexity of the program comes simply
154  *	from trying to minimize core utilization and
155  *	maximize the range of doable problems by dynamically
156  *	allocating what is needed and reusing what is not.
157  *	The core requirements for problems larger than somewhat
158  *	are (in words) 2*length(file0) + length(file1) +
159  *	3*(number of k-candidates installed),  typically about
160  *	6n words for files of length n.
161  */
162 
163 struct cand {
164 	int	x;
165 	int	y;
166 	int	pred;
167 };
168 
169 struct line {
170 	int	serial;
171 	int	value;
172 };
173 
174 /*
175  * The following struct is used to record change information when
176  * doing a "context" or "unified" diff.  (see routine "change" to
177  * understand the highly mnemonic field names)
178  */
179 struct context_vec {
180 	int	a;		/* start line in old file */
181 	int	b;		/* end line in old file */
182 	int	c;		/* start line in new file */
183 	int	d;		/* end line in new file */
184 };
185 
186 static void	 diff_output(FILE *, const char *, ...);
187 static int	 output(FILE *, struct got_diff_state *, struct got_diff_args *, const char *, FILE *, const char *, FILE *, int);
188 static void	 check(struct got_diff_state *, FILE *, FILE *, int);
189 static void	 range(FILE *, int, int, char *);
190 static void	 uni_range(FILE *, int, int);
191 static void	 dump_context_vec(FILE *, struct got_diff_state *, struct got_diff_args *, FILE *, FILE *, int);
192 static void	 dump_unified_vec(FILE *, struct got_diff_state *, struct got_diff_args *, FILE *, FILE *, int);
193 static int	 prepare(struct got_diff_state *, int, FILE *, off_t, int);
194 static void	 prune(struct got_diff_state *);
195 static void	 equiv(struct line *, int, struct line *, int, int *);
196 static void	 unravel(struct got_diff_state *, int);
197 static int	 unsort(struct line *, int, int *);
198 static int	 change(FILE *, struct got_diff_state *, struct got_diff_args *, const char *, FILE *, const char *, FILE *, int, int, int, int, int *);
199 static void	 sort(struct line *, int);
200 static void	 print_header(FILE *, struct got_diff_state *, struct got_diff_args *, const char *, const char *);
201 static int	 ignoreline(char *);
202 static int	 asciifile(FILE *);
203 static int	 fetch(FILE *, struct got_diff_state *, struct got_diff_args *, long *, int, int, FILE *, int, int, int);
204 static int	 newcand(struct got_diff_state *, int, int, int, int *);
205 static int	 search(struct got_diff_state *, int *, int, int);
206 static int	 skipline(FILE *);
207 static int	 isqrt(int);
208 static int	 stone(struct got_diff_state *, int *, int, int *, int *, int);
209 static int	 readhash(struct got_diff_state *, FILE *, int);
210 static int	 files_differ(struct got_diff_state *, FILE *, FILE *, int);
211 static char	*match_function(struct got_diff_state *, const long *, int, FILE *);
212 static char	*preadline(int, size_t, off_t);
213 
214 /*
215  * chrtran points to one of 2 translation tables: cup2low if folding upper to
216  * lower case clow2low if not folding case
217  */
218 u_char clow2low[256] = {
219 	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
220 	0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
221 	0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
222 	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
223 	0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
224 	0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x40, 0x41,
225 	0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c,
226 	0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x57,
227 	0x58, 0x59, 0x5a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 0x60, 0x61, 0x62,
228 	0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
229 	0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
230 	0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
231 	0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
232 	0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
233 	0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
234 	0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
235 	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
236 	0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
237 	0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
238 	0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
239 	0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
240 	0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
241 	0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
242 	0xfd, 0xfe, 0xff
243 };
244 
245 u_char cup2low[256] = {
246 	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a,
247 	0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15,
248 	0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
249 	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b,
250 	0x2c, 0x2d, 0x2e, 0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
251 	0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 0x60, 0x61,
252 	0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c,
253 	0x6d, 0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
254 	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x60, 0x61, 0x62,
255 	0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d,
256 	0x6e, 0x6f, 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78,
257 	0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 0x80, 0x81, 0x82, 0x83,
258 	0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e,
259 	0x8f, 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
260 	0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 0xa0, 0xa1, 0xa2, 0xa3, 0xa4,
261 	0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
262 	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba,
263 	0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5,
264 	0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0,
265 	0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xdb,
266 	0xdc, 0xdd, 0xde, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6,
267 	0xe7, 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1,
268 	0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa, 0xfb, 0xfc,
269 	0xfd, 0xfe, 0xff
270 };
271 
272 static void
273 diff_output(FILE *outfile, const char *fmt, ...)
274 {
275 	va_list ap;
276 
277 	va_start(ap, fmt);
278 	vfprintf(outfile, fmt, ap);
279 	va_end(ap);
280 }
281 
282 const struct got_error *
283 got_diffreg(int *rval, FILE *f1, FILE *f2, int flags,
284     struct got_diff_args *args, struct got_diff_state *ds, FILE *outfile)
285 {
286 	const struct got_error *err = NULL;
287 	int i;
288 
289 	*rval = D_SAME;
290 	ds->anychange = 0;
291 	ds->lastline = 0;
292 	ds->lastmatchline = 0;
293 	ds->context_vec_ptr = ds->context_vec_start - 1;
294 	if (flags & D_IGNORECASE)
295 		ds->chrtran = cup2low;
296 	else
297 		ds->chrtran = clow2low;
298 	if (S_ISDIR(ds->stb1.st_mode) != S_ISDIR(ds->stb2.st_mode)) {
299 		*rval = (S_ISDIR(ds->stb1.st_mode) ? D_MISMATCH1 : D_MISMATCH2);
300 		return NULL;
301 	}
302 	if (flags & D_EMPTY1) {
303 		f1 = fopen(_PATH_DEVNULL, "r");
304 		if (f1 == NULL)
305 			return got_error_from_errno();
306 	}
307 	else if (f1 == NULL) {
308 		args->status |= 2;
309 		goto closem;
310 	}
311 
312 	if (flags & D_EMPTY2) {
313 		f2 = fopen(_PATH_DEVNULL, "r");
314 		if (f2 == NULL)
315 			return got_error_from_errno();
316 	} else if (f2 == NULL) {
317 		args->status |= 2;
318 		goto closem;
319 	}
320 
321 	switch (files_differ(ds, f1, f2, flags)) {
322 	case 0:
323 		goto closem;
324 	case 1:
325 		break;
326 	default:
327 		/* error */
328 		args->status |= 2;
329 		goto closem;
330 	}
331 
332 	if ((flags & D_FORCEASCII) == 0 &&
333 	    (!asciifile(f1) || !asciifile(f2))) {
334 		*rval = D_BINARY;
335 		args->status |= 1;
336 		goto closem;
337 	}
338 	if (prepare(ds, 0, f1, ds->stb1.st_size, flags)) {
339 		err = got_error_from_errno();
340 		goto closem;
341 	}
342 	if (prepare(ds, 1, f2, ds->stb2.st_size, flags)) {
343 		err = got_error_from_errno();
344 		goto closem;
345 	}
346 
347 	prune(ds);
348 	sort(ds->sfile[0], ds->slen[0]);
349 	sort(ds->sfile[1], ds->slen[1]);
350 
351 	ds->member = (int *)ds->file[1];
352 	equiv(ds->sfile[0], ds->slen[0], ds->sfile[1], ds->slen[1], ds->member);
353 	ds->member = reallocarray(ds->member, ds->slen[1] + 2, sizeof(*ds->member));
354 	if (ds->member == NULL) {
355 		err = got_error_from_errno();
356 		goto closem;
357 	}
358 
359 	ds->class = (int *)ds->file[0];
360 	if (unsort(ds->sfile[0], ds->slen[0], ds->class)) {
361 		err = got_error_from_errno();
362 		goto closem;
363 	}
364 	ds->class = reallocarray(ds->class, ds->slen[0] + 2, sizeof(*ds->class));
365 	if (ds->class == NULL) {
366 		err = got_error_from_errno();
367 		goto closem;
368 	}
369 
370 	ds->klist = calloc(ds->slen[0] + 2, sizeof(*ds->klist));
371 	if (ds->klist == NULL) {
372 		err = got_error_from_errno();
373 		goto closem;
374 	}
375 	ds->clen = 0;
376 	ds->clistlen = 100;
377 	ds->clist = calloc(ds->clistlen, sizeof(*ds->clist));
378 	if (ds->clist == NULL) {
379 		err = got_error_from_errno();
380 		goto closem;
381 	}
382 	i = stone(ds, ds->class, ds->slen[0], ds->member, ds->klist, flags);
383 	if (i < 0) {
384 		err = got_error_from_errno();
385 		free(ds->member);
386 		free(ds->class);
387 		goto closem;
388 	}
389 	free(ds->member);
390 	free(ds->class);
391 
392 	ds->J = reallocarray(ds->J, ds->len[0] + 2, sizeof(*ds->J));
393 	if (ds->J == NULL) {
394 		err = got_error_from_errno();
395 		goto closem;
396 	}
397 	unravel(ds, ds->klist[i]);
398 	free(ds->clist);
399 	ds->clist = NULL;
400 	free(ds->klist);
401 	ds->klist = NULL;
402 
403 	ds->ixold = reallocarray(ds->ixold, ds->len[0] + 2, sizeof(*ds->ixold));
404 	if (ds->ixold == NULL) {
405 		err = got_error_from_errno();
406 		goto closem;
407 	}
408 	ds->ixnew = reallocarray(ds->ixnew, ds->len[1] + 2, sizeof(*ds->ixnew));
409 	if (ds->ixnew == NULL) {
410 		err = got_error_from_errno();
411 		goto closem;
412 	}
413 	check(ds, f1, f2, flags);
414 	if (output(outfile, ds, args, args->label[0], f1, args->label[1], f2,
415 	    flags))
416 		err = got_error_from_errno();
417 closem:
418 	if (ds->anychange) {
419 		args->status |= 1;
420 		if (*rval == D_SAME)
421 			*rval = D_DIFFER;
422 	}
423 	if (f1 != NULL)
424 		fclose(f1);
425 	if (f2 != NULL)
426 		fclose(f2);
427 
428 	return (err);
429 }
430 
431 /*
432  * Check to see if the given files differ.
433  * Returns 0 if they are the same, 1 if different, and -1 on error.
434  * XXX - could use code from cmp(1) [faster]
435  */
436 static int
437 files_differ(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
438 {
439 	char buf1[BUFSIZ], buf2[BUFSIZ];
440 	size_t i, j;
441 
442 	if ((flags & (D_EMPTY1|D_EMPTY2)) || ds->stb1.st_size != ds->stb2.st_size ||
443 	    (ds->stb1.st_mode & S_IFMT) != (ds->stb2.st_mode & S_IFMT))
444 		return (1);
445 	for (;;) {
446 		i = fread(buf1, 1, sizeof(buf1), f1);
447 		j = fread(buf2, 1, sizeof(buf2), f2);
448 		if ((!i && ferror(f1)) || (!j && ferror(f2)))
449 			return (-1);
450 		if (i != j)
451 			return (1);
452 		if (i == 0)
453 			return (0);
454 		if (memcmp(buf1, buf2, i) != 0)
455 			return (1);
456 	}
457 }
458 
459 static int
460 prepare(struct got_diff_state *ds, int i, FILE *fd, off_t filesize, int flags)
461 {
462 	struct line *p;
463 	int j, h;
464 	size_t sz;
465 
466 	rewind(fd);
467 
468 	sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25;
469 	if (sz < 100)
470 		sz = 100;
471 
472 	p = calloc(sz + 3, sizeof(*p));
473 	if (p == NULL)
474 		return (-1);
475 	for (j = 0; (h = readhash(ds, fd, flags));) {
476 		if (j == sz) {
477 			sz = sz * 3 / 2;
478 			p = reallocarray(p, sz + 3, sizeof(*p));
479 			if (p == NULL)
480 				return (-1);
481 		}
482 		p[++j].value = h;
483 	}
484 	ds->len[i] = j;
485 	ds->file[i] = p;
486 
487 	return (0);
488 }
489 
490 static void
491 prune(struct got_diff_state *ds)
492 {
493 	int i, j;
494 
495 	for (ds->pref = 0; ds->pref < ds->len[0] && ds->pref < ds->len[1] &&
496 	    ds->file[0][ds->pref + 1].value == ds->file[1][ds->pref + 1].value;
497 	    ds->pref++)
498 		;
499 	for (ds->suff = 0; ds->suff < ds->len[0] - ds->pref && ds->suff < ds->len[1] - ds->pref &&
500 	    ds->file[0][ds->len[0] - ds->suff].value == ds->file[1][ds->len[1] - ds->suff].value;
501 	    ds->suff++)
502 		;
503 	for (j = 0; j < 2; j++) {
504 		ds->sfile[j] = ds->file[j] + ds->pref;
505 		ds->slen[j] = ds->len[j] - ds->pref - ds->suff;
506 		for (i = 0; i <= ds->slen[j]; i++)
507 			ds->sfile[j][i].serial = i;
508 	}
509 }
510 
511 static void
512 equiv(struct line *a, int n, struct line *b, int m, int *c)
513 {
514 	int i, j;
515 
516 	i = j = 1;
517 	while (i <= n && j <= m) {
518 		if (a[i].value < b[j].value)
519 			a[i++].value = 0;
520 		else if (a[i].value == b[j].value)
521 			a[i++].value = j;
522 		else
523 			j++;
524 	}
525 	while (i <= n)
526 		a[i++].value = 0;
527 	b[m + 1].value = 0;
528 	j = 0;
529 	while (++j <= m) {
530 		c[j] = -b[j].serial;
531 		while (b[j + 1].value == b[j].value) {
532 			j++;
533 			c[j] = b[j].serial;
534 		}
535 	}
536 	c[j] = -1;
537 }
538 
539 /* Code taken from ping.c */
540 static int
541 isqrt(int n)
542 {
543 	int y, x = 1;
544 
545 	if (n == 0)
546 		return (0);
547 
548 	do { /* newton was a stinker */
549 		y = x;
550 		x = n / x;
551 		x += y;
552 		x /= 2;
553 	} while ((x - y) > 1 || (x - y) < -1);
554 
555 	return (x);
556 }
557 
558 static int
559 stone(struct got_diff_state *ds, int *a, int n, int *b, int *c, int flags)
560 {
561 	int i, k, y, j, l;
562 	int oldc, tc, oldl, sq;
563 	u_int numtries, bound;
564 	int error;
565 
566 	if (flags & D_MINIMAL)
567 		bound = UINT_MAX;
568 	else {
569 		sq = isqrt(n);
570 		bound = MAXIMUM(256, sq);
571 	}
572 
573 	k = 0;
574 	c[0] = newcand(ds, 0, 0, 0, &error);
575 	if (error)
576 		return -1;
577 	for (i = 1; i <= n; i++) {
578 		j = a[i];
579 		if (j == 0)
580 			continue;
581 		y = -b[j];
582 		oldl = 0;
583 		oldc = c[0];
584 		numtries = 0;
585 		do {
586 			if (y <= ds->clist[oldc].y)
587 				continue;
588 			l = search(ds, c, k, y);
589 			if (l != oldl + 1)
590 				oldc = c[l - 1];
591 			if (l <= k) {
592 				if (ds->clist[c[l]].y <= y)
593 					continue;
594 				tc = c[l];
595 				c[l] = newcand(ds, i, y, oldc, &error);
596 				if (error)
597 					return -1;
598 				oldc = tc;
599 				oldl = l;
600 				numtries++;
601 			} else {
602 				c[l] = newcand(ds, i, y, oldc, &error);
603 				if (error)
604 					return -1;
605 				k++;
606 				break;
607 			}
608 		} while ((y = b[++j]) > 0 && numtries < bound);
609 	}
610 	return (k);
611 }
612 
613 static int
614 newcand(struct got_diff_state *ds, int x, int y, int pred, int *errorp)
615 {
616 	struct cand *q;
617 
618 	if (ds->clen == ds->clistlen) {
619 		ds->clistlen = ds->clistlen * 11 / 10;
620 		ds->clist = reallocarray(ds->clist, ds->clistlen,
621 		    sizeof(*ds->clist));
622 		if (ds->clist == NULL) {
623 			*errorp = -1;
624 			return 0;
625 		}
626 	}
627 	q = ds->clist + ds->clen;
628 	q->x = x;
629 	q->y = y;
630 	q->pred = pred;
631 	*errorp = 0;
632 	return (ds->clen++);
633 }
634 
635 static int
636 search(struct got_diff_state *ds, int *c, int k, int y)
637 {
638 	int i, j, l, t;
639 
640 	if (ds->clist[c[k]].y < y)	/* quick look for typical case */
641 		return (k + 1);
642 	i = 0;
643 	j = k + 1;
644 	for (;;) {
645 		l = (i + j) / 2;
646 		if (l <= i)
647 			break;
648 		t = ds->clist[c[l]].y;
649 		if (t > y)
650 			j = l;
651 		else if (t < y)
652 			i = l;
653 		else
654 			return (l);
655 	}
656 	return (l + 1);
657 }
658 
659 static void
660 unravel(struct got_diff_state *ds, int p)
661 {
662 	struct cand *q;
663 	int i;
664 
665 	for (i = 0; i <= ds->len[0]; i++)
666 		ds->J[i] = i <= ds->pref ? i :
667 		    i > ds->len[0] - ds->suff ? i + ds->len[1] - ds->len[0] : 0;
668 	for (q = ds->clist + p; q->y != 0; q = ds->clist + q->pred)
669 		ds->J[q->x + ds->pref] = q->y + ds->pref;
670 }
671 
672 /*
673  * Check does double duty:
674  *  1.	ferret out any fortuitous correspondences due
675  *	to confounding by hashing (which result in "jackpot")
676  *  2.  collect random access indexes to the two files
677  */
678 static void
679 check(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
680 {
681 	int i, j, jackpot, c, d;
682 	long ctold, ctnew;
683 
684 	rewind(f1);
685 	rewind(f2);
686 	j = 1;
687 	ds->ixold[0] = ds->ixnew[0] = 0;
688 	jackpot = 0;
689 	ctold = ctnew = 0;
690 	for (i = 1; i <= ds->len[0]; i++) {
691 		if (ds->J[i] == 0) {
692 			ds->ixold[i] = ctold += skipline(f1);
693 			continue;
694 		}
695 		while (j < ds->J[i]) {
696 			ds->ixnew[j] = ctnew += skipline(f2);
697 			j++;
698 		}
699 		if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) {
700 			for (;;) {
701 				c = getc(f1);
702 				d = getc(f2);
703 				/*
704 				 * GNU diff ignores a missing newline
705 				 * in one file for -b or -w.
706 				 */
707 				if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) {
708 					if (c == EOF && d == '\n') {
709 						ctnew++;
710 						break;
711 					} else if (c == '\n' && d == EOF) {
712 						ctold++;
713 						break;
714 					}
715 				}
716 				ctold++;
717 				ctnew++;
718 				if ((flags & D_FOLDBLANKS) && isspace(c) &&
719 				    isspace(d)) {
720 					do {
721 						if (c == '\n')
722 							break;
723 						ctold++;
724 					} while (isspace(c = getc(f1)));
725 					do {
726 						if (d == '\n')
727 							break;
728 						ctnew++;
729 					} while (isspace(d = getc(f2)));
730 				} else if ((flags & D_IGNOREBLANKS)) {
731 					while (isspace(c) && c != '\n') {
732 						c = getc(f1);
733 						ctold++;
734 					}
735 					while (isspace(d) && d != '\n') {
736 						d = getc(f2);
737 						ctnew++;
738 					}
739 				}
740 				if (ds->chrtran[c] != ds->chrtran[d]) {
741 					jackpot++;
742 					ds->J[i] = 0;
743 					if (c != '\n' && c != EOF)
744 						ctold += skipline(f1);
745 					if (d != '\n' && c != EOF)
746 						ctnew += skipline(f2);
747 					break;
748 				}
749 				if (c == '\n' || c == EOF)
750 					break;
751 			}
752 		} else {
753 			for (;;) {
754 				ctold++;
755 				ctnew++;
756 				if ((c = getc(f1)) != (d = getc(f2))) {
757 					/* jackpot++; */
758 					ds->J[i] = 0;
759 					if (c != '\n' && c != EOF)
760 						ctold += skipline(f1);
761 					if (d != '\n' && c != EOF)
762 						ctnew += skipline(f2);
763 					break;
764 				}
765 				if (c == '\n' || c == EOF)
766 					break;
767 			}
768 		}
769 		ds->ixold[i] = ctold;
770 		ds->ixnew[j] = ctnew;
771 		j++;
772 	}
773 	for (; j <= ds->len[1]; j++)
774 		ds->ixnew[j] = ctnew += skipline(f2);
775 	/*
776 	 * if (jackpot)
777 	 *	fprintf(stderr, "jackpot\n");
778 	 */
779 }
780 
781 /* shellsort CACM #201 */
782 static void
783 sort(struct line *a, int n)
784 {
785 	struct line *ai, *aim, w;
786 	int j, m = 0, k;
787 
788 	if (n == 0)
789 		return;
790 	for (j = 1; j <= n; j *= 2)
791 		m = 2 * j - 1;
792 	for (m /= 2; m != 0; m /= 2) {
793 		k = n - m;
794 		for (j = 1; j <= k; j++) {
795 			for (ai = &a[j]; ai > a; ai -= m) {
796 				aim = &ai[m];
797 				if (aim < ai)
798 					break;	/* wraparound */
799 				if (aim->value > ai[0].value ||
800 				    (aim->value == ai[0].value &&
801 					aim->serial > ai[0].serial))
802 					break;
803 				w.value = ai[0].value;
804 				ai[0].value = aim->value;
805 				aim->value = w.value;
806 				w.serial = ai[0].serial;
807 				ai[0].serial = aim->serial;
808 				aim->serial = w.serial;
809 			}
810 		}
811 	}
812 }
813 
814 static int
815 unsort(struct line *f, int l, int *b)
816 {
817 	int *a, i;
818 
819 	a = calloc(l + 1, sizeof(*a));
820 	if (a == NULL)
821 		return (-1);
822 	for (i = 1; i <= l; i++)
823 		a[f[i].serial] = f[i].value;
824 	for (i = 1; i <= l; i++)
825 		b[i] = a[i];
826 	free(a);
827 
828 	return (0);
829 }
830 
831 static int
832 skipline(FILE *f)
833 {
834 	int i, c;
835 
836 	for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
837 		continue;
838 	return (i);
839 }
840 
841 static int
842 output(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
843     const char *file1, FILE *f1, const char *file2, FILE *f2, int flags)
844 {
845 	int m, i0, i1, j0, j1;
846 	int error = 0;
847 
848 	rewind(f1);
849 	rewind(f2);
850 	m = ds->len[0];
851 	ds->J[0] = 0;
852 	ds->J[m + 1] = ds->len[1] + 1;
853 	if (args->diff_format != D_EDIT) {
854 		for (i0 = 1; i0 <= m; i0 = i1 + 1) {
855 			while (i0 <= m && ds->J[i0] == ds->J[i0 - 1] + 1)
856 				i0++;
857 			j0 = ds->J[i0 - 1] + 1;
858 			i1 = i0 - 1;
859 			while (i1 < m && ds->J[i1 + 1] == 0)
860 				i1++;
861 			j1 = ds->J[i1 + 1] - 1;
862 			ds->J[i1] = j1;
863 			error = change(outfile, ds, args, file1, f1, file2, f2,
864 			    i0, i1, j0, j1, &flags);
865 			if (error)
866 				return (error);
867 		}
868 	} else {
869 		for (i0 = m; i0 >= 1; i0 = i1 - 1) {
870 			while (i0 >= 1 && ds->J[i0] == ds->J[i0 + 1] - 1 && ds->J[i0] != 0)
871 				i0--;
872 			j0 = ds->J[i0 + 1] - 1;
873 			i1 = i0 + 1;
874 			while (i1 > 1 && ds->J[i1 - 1] == 0)
875 				i1--;
876 			j1 = ds->J[i1 - 1] + 1;
877 			ds->J[i1] = j1;
878 			change(outfile, ds, args, file1, f1, file2, f2, i1, i0,
879 			    j1, j0, &flags);
880 			if (error)
881 				return (error);
882 		}
883 	}
884 	if (m == 0) {
885 		error = change(outfile, ds, args, file1, f1, file2, f2, 1, 0,
886 		    1, ds->len[1], &flags);
887 		if (error)
888 			return (error);
889 	}
890 	if (args->diff_format == D_IFDEF) {
891 		for (;;) {
892 #define	c i0
893 			if ((c = getc(f1)) == EOF)
894 				return (0);
895 			diff_output(outfile, "%c", c);
896 		}
897 #undef c
898 	}
899 	if (ds->anychange != 0) {
900 		if (args->diff_format == D_CONTEXT)
901 			dump_context_vec(outfile, ds, args, f1, f2, flags);
902 		else if (args->diff_format == D_UNIFIED)
903 			dump_unified_vec(outfile, ds, args, f1, f2, flags);
904 	}
905 
906 	return (0);
907 }
908 
909 static void
910 range(FILE *outfile, int a, int b, char *separator)
911 {
912 	diff_output(outfile, "%d", a > b ? b : a);
913 	if (a < b)
914 		diff_output(outfile, "%s%d", separator, b);
915 }
916 
917 static void
918 uni_range(FILE *outfile, int a, int b)
919 {
920 	if (a < b)
921 		diff_output(outfile, "%d,%d", a, b - a + 1);
922 	else if (a == b)
923 		diff_output(outfile, "%d", b);
924 	else
925 		diff_output(outfile, "%d,0", b);
926 }
927 
928 static char *
929 preadline(int fd, size_t rlen, off_t off)
930 {
931 	char *line;
932 	ssize_t nr;
933 
934 	line = malloc(rlen + 1);
935 	if (line == NULL)
936 		return NULL;
937 	if ((nr = pread(fd, line, rlen, off)) < 0) {
938 		free(line);
939 		return NULL;
940 	}
941 	if (nr > 0 && line[nr-1] == '\n')
942 		nr--;
943 	line[nr] = '\0';
944 	return (line);
945 }
946 
947 static int
948 ignoreline(char *line)
949 {
950 	return 0; /* do not ignore any lines */
951 }
952 
953 /*
954  * Indicate that there is a difference between lines a and b of the from file
955  * to get to lines c to d of the to file.  If a is greater then b then there
956  * are no lines in the from file involved and this means that there were
957  * lines appended (beginning at b).  If c is greater than d then there are
958  * lines missing from the to file.
959  */
960 static int
961 change(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
962     const char *file1, FILE *f1, const char *file2, FILE *f2,
963     int a, int b, int c, int d, int *pflags)
964 {
965 	size_t max_context = 64;
966 	int i;
967 
968 restart:
969 	if (args->diff_format != D_IFDEF && a > b && c > d)
970 		return (0);
971 	if (args->ignore_pats != NULL) {
972 		char *line;
973 		/*
974 		 * All lines in the change, insert, or delete must
975 		 * match an ignore pattern for the change to be
976 		 * ignored.
977 		 */
978 		if (a <= b) {		/* Changes and deletes. */
979 			for (i = a; i <= b; i++) {
980 				line = preadline(fileno(f1),
981 				    ds->ixold[i] - ds->ixold[i - 1],
982 				    ds->ixold[i - 1]);
983 				if (line == NULL)
984 					return (-1);
985 				if (!ignoreline(line))
986 					goto proceed;
987 			}
988 		}
989 		if (a > b || c <= d) {	/* Changes and inserts. */
990 			for (i = c; i <= d; i++) {
991 				line = preadline(fileno(f2),
992 				    ds->ixnew[i] - ds->ixnew[i - 1],
993 				    ds->ixnew[i - 1]);
994 				if (line == NULL)
995 					return (-1);
996 				if (!ignoreline(line))
997 					goto proceed;
998 			}
999 		}
1000 		return (0);
1001 	}
1002 proceed:
1003 	if (*pflags & D_HEADER) {
1004 		diff_output(outfile, "%s %s %s\n", args->diffargs, file1, file2);
1005 		*pflags &= ~D_HEADER;
1006 	}
1007 	if (args->diff_format == D_CONTEXT || args->diff_format == D_UNIFIED) {
1008 		/*
1009 		 * Allocate change records as needed.
1010 		 */
1011 		if (ds->context_vec_ptr == ds->context_vec_end - 1) {
1012 			ptrdiff_t offset = ds->context_vec_ptr - ds->context_vec_start;
1013 			max_context <<= 1;
1014 			ds->context_vec_start =
1015 			    reallocarray(ds->context_vec_start, max_context,
1016 				sizeof(*ds->context_vec_start));
1017 			if (ds->context_vec_start == NULL)
1018 				return (-1);
1019 			ds->context_vec_end = ds->context_vec_start + max_context;
1020 			ds->context_vec_ptr = ds->context_vec_start + offset;
1021 		}
1022 		if (ds->anychange == 0) {
1023 			/*
1024 			 * Print the context/unidiff header first time through.
1025 			 */
1026 			print_header(outfile, ds, args, file1, file2);
1027 			ds->anychange = 1;
1028 		} else if (a > ds->context_vec_ptr->b + (2 * args->diff_context) + 1 &&
1029 		    c > ds->context_vec_ptr->d + (2 * args->diff_context) + 1) {
1030 			/*
1031 			 * If this change is more than 'diff_context' lines from the
1032 			 * previous change, dump the record and reset it.
1033 			 */
1034 			if (args->diff_format == D_CONTEXT)
1035 				dump_context_vec(outfile, ds, args, f1, f2, *pflags);
1036 			else
1037 				dump_unified_vec(outfile, ds, args, f1, f2, *pflags);
1038 		}
1039 		ds->context_vec_ptr++;
1040 		ds->context_vec_ptr->a = a;
1041 		ds->context_vec_ptr->b = b;
1042 		ds->context_vec_ptr->c = c;
1043 		ds->context_vec_ptr->d = d;
1044 		return (0);
1045 	}
1046 	if (ds->anychange == 0)
1047 		ds->anychange = 1;
1048 	switch (args->diff_format) {
1049 	case D_BRIEF:
1050 		return (0);
1051 	case D_NORMAL:
1052 	case D_EDIT:
1053 		range(outfile, a, b, ",");
1054 		diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1055 		if (args->diff_format == D_NORMAL)
1056 			range(outfile, c, d, ",");
1057 		diff_output(outfile, "\n");
1058 		break;
1059 	case D_REVERSE:
1060 		diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1061 		range(outfile, a, b, " ");
1062 		diff_output(outfile, "\n");
1063 		break;
1064 	case D_NREVERSE:
1065 		if (a > b)
1066 			diff_output(outfile, "a%d %d\n", b, d - c + 1);
1067 		else {
1068 			diff_output(outfile, "d%d %d\n", a, b - a + 1);
1069 			if (!(c > d))
1070 				/* add changed lines */
1071 				diff_output(outfile, "a%d %d\n", b, d - c + 1);
1072 		}
1073 		break;
1074 	}
1075 	if (args->diff_format == D_NORMAL || args->diff_format == D_IFDEF) {
1076 		fetch(outfile, ds, args, ds->ixold, a, b, f1, '<', 1, *pflags);
1077 		if (a <= b && c <= d && args->diff_format == D_NORMAL)
1078 			diff_output(outfile, "---\n");
1079 	}
1080 	i = fetch(outfile, ds, args, ds->ixnew, c, d, f2, args->diff_format == D_NORMAL ? '>' : '\0', 0, *pflags);
1081 	if (i != 0 && args->diff_format == D_EDIT) {
1082 		/*
1083 		 * A non-zero return value for D_EDIT indicates that the
1084 		 * last line printed was a bare dot (".") that has been
1085 		 * escaped as ".." to prevent ed(1) from misinterpreting
1086 		 * it.  We have to add a substitute command to change this
1087 		 * back and restart where we left off.
1088 		 */
1089 		diff_output(outfile, ".\n");
1090 		diff_output(outfile, "%ds/.//\n", a + i - 1);
1091 		b = a + i - 1;
1092 		a = b + 1;
1093 		c += i;
1094 		goto restart;
1095 	}
1096 	if ((args->diff_format == D_EDIT || args->diff_format == D_REVERSE) && c <= d)
1097 		diff_output(outfile, ".\n");
1098 	if (ds->inifdef) {
1099 		diff_output(outfile, "#endif /* %s */\n", args->ifdefname);
1100 		ds->inifdef = 0;
1101 	}
1102 
1103 	return (0);
1104 }
1105 
1106 static int
1107 fetch(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1108     long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1109 {
1110 	int i, j, c, lastc, col, nc;
1111 
1112 	/*
1113 	 * When doing #ifdef's, copy down to current line
1114 	 * if this is the first file, so that stuff makes it to output.
1115 	 */
1116 	if (args->diff_format == D_IFDEF && oldfile) {
1117 		long curpos = ftell(lb);
1118 		/* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1119 		nc = f[a > b ? b : a - 1] - curpos;
1120 		for (i = 0; i < nc; i++)
1121 			diff_output(outfile, "%c", getc(lb));
1122 	}
1123 	if (a > b)
1124 		return (0);
1125 	if (args->diff_format == D_IFDEF) {
1126 		if (ds->inifdef) {
1127 			diff_output(outfile, "#else /* %s%s */\n",
1128 			    oldfile == 1 ? "!" : "", args->ifdefname);
1129 		} else {
1130 			if (oldfile)
1131 				diff_output(outfile, "#ifndef %s\n", args->ifdefname);
1132 			else
1133 				diff_output(outfile, "#ifdef %s\n", args->ifdefname);
1134 		}
1135 		ds->inifdef = 1 + oldfile;
1136 	}
1137 	for (i = a; i <= b; i++) {
1138 		fseek(lb, f[i - 1], SEEK_SET);
1139 		nc = f[i] - f[i - 1];
1140 		if (args->diff_format != D_IFDEF && ch != '\0') {
1141 			diff_output(outfile, "%c", ch);
1142 			if (args->Tflag && (args->diff_format == D_NORMAL || args->diff_format == D_CONTEXT
1143 			    || args->diff_format == D_UNIFIED))
1144 				diff_output(outfile, "\t");
1145 			else if (args->diff_format != D_UNIFIED)
1146 				diff_output(outfile, " ");
1147 		}
1148 		col = 0;
1149 		for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) {
1150 			if ((c = getc(lb)) == EOF) {
1151 				if (args->diff_format == D_EDIT || args->diff_format == D_REVERSE ||
1152 				    args->diff_format == D_NREVERSE)
1153 					warnx("No newline at end of file");
1154 				else
1155 					diff_output(outfile, "\n\\ No newline at end of "
1156 					    "file\n");
1157 				return (0);
1158 			}
1159 			if (c == '\t' && (flags & D_EXPANDTABS)) {
1160 				do {
1161 					diff_output(outfile, " ");
1162 				} while (++col & 7);
1163 			} else {
1164 				if (args->diff_format == D_EDIT && j == 1 && c == '\n'
1165 				    && lastc == '.') {
1166 					/*
1167 					 * Don't print a bare "." line
1168 					 * since that will confuse ed(1).
1169 					 * Print ".." instead and return,
1170 					 * giving the caller an offset
1171 					 * from which to restart.
1172 					 */
1173 					diff_output(outfile, ".\n");
1174 					return (i - a + 1);
1175 				}
1176 				diff_output(outfile, "%c", c);
1177 				col++;
1178 			}
1179 		}
1180 	}
1181 	return (0);
1182 }
1183 
1184 /*
1185  * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1186  */
1187 static int
1188 readhash(struct got_diff_state *ds, FILE *f, int flags)
1189 {
1190 	int i, t, space;
1191 	int sum;
1192 
1193 	sum = 1;
1194 	space = 0;
1195 	if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) {
1196 		if (flags & D_IGNORECASE)
1197 			for (i = 0; (t = getc(f)) != '\n'; i++) {
1198 				if (t == EOF) {
1199 					if (i == 0)
1200 						return (0);
1201 					break;
1202 				}
1203 				sum = sum * 127 + ds->chrtran[t];
1204 			}
1205 		else
1206 			for (i = 0; (t = getc(f)) != '\n'; i++) {
1207 				if (t == EOF) {
1208 					if (i == 0)
1209 						return (0);
1210 					break;
1211 				}
1212 				sum = sum * 127 + t;
1213 			}
1214 	} else {
1215 		for (i = 0;;) {
1216 			switch (t = getc(f)) {
1217 			case '\t':
1218 			case '\r':
1219 			case '\v':
1220 			case '\f':
1221 			case ' ':
1222 				space++;
1223 				continue;
1224 			default:
1225 				if (space && (flags & D_IGNOREBLANKS) == 0) {
1226 					i++;
1227 					space = 0;
1228 				}
1229 				sum = sum * 127 + ds->chrtran[t];
1230 				i++;
1231 				continue;
1232 			case EOF:
1233 				if (i == 0)
1234 					return (0);
1235 				/* FALLTHROUGH */
1236 			case '\n':
1237 				break;
1238 			}
1239 			break;
1240 		}
1241 	}
1242 	/*
1243 	 * There is a remote possibility that we end up with a zero sum.
1244 	 * Zero is used as an EOF marker, so return 1 instead.
1245 	 */
1246 	return (sum == 0 ? 1 : sum);
1247 }
1248 
1249 static int
1250 asciifile(FILE *f)
1251 {
1252 	unsigned char buf[BUFSIZ];
1253 	size_t cnt;
1254 
1255 	if (f == NULL)
1256 		return (1);
1257 
1258 	rewind(f);
1259 	cnt = fread(buf, 1, sizeof(buf), f);
1260 	return (memchr(buf, '\0', cnt) == NULL);
1261 }
1262 
1263 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1264 
1265 static char *
1266 match_function(struct got_diff_state *ds, const long *f, int pos, FILE *fp)
1267 {
1268 	unsigned char buf[FUNCTION_CONTEXT_SIZE];
1269 	size_t nc;
1270 	int last = ds->lastline;
1271 	char *state = NULL;
1272 
1273 	ds->lastline = pos;
1274 	while (pos > last) {
1275 		fseek(fp, f[pos - 1], SEEK_SET);
1276 		nc = f[pos] - f[pos - 1];
1277 		if (nc >= sizeof(buf))
1278 			nc = sizeof(buf) - 1;
1279 		nc = fread(buf, 1, nc, fp);
1280 		if (nc > 0) {
1281 			buf[nc] = '\0';
1282 			buf[strcspn(buf, "\n")] = '\0';
1283 			if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1284 				if (begins_with(buf, "private:")) {
1285 					if (!state)
1286 						state = " (private)";
1287 				} else if (begins_with(buf, "protected:")) {
1288 					if (!state)
1289 						state = " (protected)";
1290 				} else if (begins_with(buf, "public:")) {
1291 					if (!state)
1292 						state = " (public)";
1293 				} else {
1294 					strlcpy(ds->lastbuf, buf, sizeof ds->lastbuf);
1295 					if (state)
1296 						strlcat(ds->lastbuf, state,
1297 						    sizeof ds->lastbuf);
1298 					ds->lastmatchline = pos;
1299 					return ds->lastbuf;
1300 				}
1301 			}
1302 		}
1303 		pos--;
1304 	}
1305 	return ds->lastmatchline > 0 ? ds->lastbuf : NULL;
1306 }
1307 
1308 /* dump accumulated "context" diff changes */
1309 static void
1310 dump_context_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1311     FILE *f1, FILE *f2, int flags)
1312 {
1313 	struct context_vec *cvp = ds->context_vec_start;
1314 	int lowa, upb, lowc, upd, do_output;
1315 	int a, b, c, d;
1316 	char ch, *f;
1317 
1318 	if (ds->context_vec_start > ds->context_vec_ptr)
1319 		return;
1320 
1321 	b = d = 0;		/* gcc */
1322 	lowa = MAXIMUM(1, cvp->a - args->diff_context);
1323 	upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1324 	lowc = MAXIMUM(1, cvp->c - args->diff_context);
1325 	upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1326 
1327 	diff_output(outfile, "***************");
1328 	if ((flags & D_PROTOTYPE)) {
1329 		f = match_function(ds, ds->ixold, lowa-1, f1);
1330 		if (f != NULL)
1331 			diff_output(outfile, " %s", f);
1332 	}
1333 	diff_output(outfile, "\n*** ");
1334 	range(outfile, lowa, upb, ",");
1335 	diff_output(outfile, " ****\n");
1336 
1337 	/*
1338 	 * Output changes to the "old" file.  The first loop suppresses
1339 	 * output if there were no changes to the "old" file (we'll see
1340 	 * the "old" lines as context in the "new" list).
1341 	 */
1342 	do_output = 0;
1343 	for (; cvp <= ds->context_vec_ptr; cvp++)
1344 		if (cvp->a <= cvp->b) {
1345 			cvp = ds->context_vec_start;
1346 			do_output++;
1347 			break;
1348 		}
1349 	if (do_output) {
1350 		while (cvp <= ds->context_vec_ptr) {
1351 			a = cvp->a;
1352 			b = cvp->b;
1353 			c = cvp->c;
1354 			d = cvp->d;
1355 
1356 			if (a <= b && c <= d)
1357 				ch = 'c';
1358 			else
1359 				ch = (a <= b) ? 'd' : 'a';
1360 
1361 			if (ch == 'a')
1362 				fetch(outfile, ds, args, ds->ixold, lowa, b, f1, ' ', 0, flags);
1363 			else {
1364 				fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1365 				fetch(outfile, ds, args, ds->ixold, a, b, f1,
1366 				    ch == 'c' ? '!' : '-', 0, flags);
1367 			}
1368 			lowa = b + 1;
1369 			cvp++;
1370 		}
1371 		fetch(outfile, ds, args, ds->ixold, b + 1, upb, f1, ' ', 0, flags);
1372 	}
1373 	/* output changes to the "new" file */
1374 	diff_output(outfile, "--- ");
1375 	range(outfile, lowc, upd, ",");
1376 	diff_output(outfile, " ----\n");
1377 
1378 	do_output = 0;
1379 	for (cvp = ds->context_vec_start; cvp <= ds->context_vec_ptr; cvp++)
1380 		if (cvp->c <= cvp->d) {
1381 			cvp = ds->context_vec_start;
1382 			do_output++;
1383 			break;
1384 		}
1385 	if (do_output) {
1386 		while (cvp <= ds->context_vec_ptr) {
1387 			a = cvp->a;
1388 			b = cvp->b;
1389 			c = cvp->c;
1390 			d = cvp->d;
1391 
1392 			if (a <= b && c <= d)
1393 				ch = 'c';
1394 			else
1395 				ch = (a <= b) ? 'd' : 'a';
1396 
1397 			if (ch == 'd')
1398 				fetch(outfile, ds, args, ds->ixnew, lowc, d, f2, ' ', 0, flags);
1399 			else {
1400 				fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1401 				fetch(outfile, ds, args, ds->ixnew, c, d, f2,
1402 				    ch == 'c' ? '!' : '+', 0, flags);
1403 			}
1404 			lowc = d + 1;
1405 			cvp++;
1406 		}
1407 		fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1408 	}
1409 	ds->context_vec_ptr = ds->context_vec_start - 1;
1410 }
1411 
1412 /* dump accumulated "unified" diff changes */
1413 static void
1414 dump_unified_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1415     FILE *f1, FILE *f2, int flags)
1416 {
1417 	struct context_vec *cvp = ds->context_vec_start;
1418 	int lowa, upb, lowc, upd;
1419 	int a, b, c, d;
1420 	char ch, *f;
1421 
1422 	if (ds->context_vec_start > ds->context_vec_ptr)
1423 		return;
1424 
1425 	b = d = 0;		/* gcc */
1426 	lowa = MAXIMUM(1, cvp->a - args->diff_context);
1427 	upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1428 	lowc = MAXIMUM(1, cvp->c - args->diff_context);
1429 	upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1430 
1431 	diff_output(outfile, "@@ -");
1432 	uni_range(outfile, lowa, upb);
1433 	diff_output(outfile, " +");
1434 	uni_range(outfile, lowc, upd);
1435 	diff_output(outfile, " @@");
1436 	if ((flags & D_PROTOTYPE)) {
1437 		f = match_function(ds, ds->ixold, lowa-1, f1);
1438 		if (f != NULL)
1439 			diff_output(outfile, " %s", f);
1440 	}
1441 	diff_output(outfile, "\n");
1442 
1443 	/*
1444 	 * Output changes in "unified" diff format--the old and new lines
1445 	 * are printed together.
1446 	 */
1447 	for (; cvp <= ds->context_vec_ptr; cvp++) {
1448 		a = cvp->a;
1449 		b = cvp->b;
1450 		c = cvp->c;
1451 		d = cvp->d;
1452 
1453 		/*
1454 		 * c: both new and old changes
1455 		 * d: only changes in the old file
1456 		 * a: only changes in the new file
1457 		 */
1458 		if (a <= b && c <= d)
1459 			ch = 'c';
1460 		else
1461 			ch = (a <= b) ? 'd' : 'a';
1462 
1463 		switch (ch) {
1464 		case 'c':
1465 			fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1466 			fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1467 			fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1468 			break;
1469 		case 'd':
1470 			fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1471 			fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1472 			break;
1473 		case 'a':
1474 			fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1475 			fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1476 			break;
1477 		}
1478 		lowa = b + 1;
1479 		lowc = d + 1;
1480 	}
1481 	fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1482 
1483 	ds->context_vec_ptr = ds->context_vec_start - 1;
1484 }
1485 
1486 static void
1487 print_header(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1488     const char *file1, const char *file2)
1489 {
1490 	if (args->label[0] != NULL)
1491 		diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "***" : "---",
1492 		    args->label[0]);
1493 	else
1494 		diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "***" : "---",
1495 		    file1, ctime(&ds->stb1.st_mtime));
1496 	if (args->label[1] != NULL)
1497 		diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "---" : "+++",
1498 		    args->label[1]);
1499 	else
1500 		diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "---" : "+++",
1501 		    file2, ctime(&ds->stb2.st_mtime));
1502 }