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 			err = got_error_from_errno();
306 			goto closem;
307 		}
308 	}
309 	else if (f1 == NULL) {
310 		args->status |= 2;
311 		goto closem;
312 	}
313 
314 	if (flags & D_EMPTY2) {
315 		f2 = fopen(_PATH_DEVNULL, "r");
316 		if (f2 == NULL) {
317 			err = got_error_from_errno();
318 			goto closem;
319 		}
320 	} else if (f2 == NULL) {
321 		args->status |= 2;
322 		goto closem;
323 	}
324 
325 	switch (files_differ(ds, f1, f2, flags)) {
326 	case 0:
327 		goto closem;
328 	case 1:
329 		break;
330 	default:
331 		/* error */
332 		args->status |= 2;
333 		goto closem;
334 	}
335 
336 	if ((flags & D_FORCEASCII) == 0 &&
337 	    (!asciifile(f1) || !asciifile(f2))) {
338 		*rval = D_BINARY;
339 		args->status |= 1;
340 		goto closem;
341 	}
342 	if (prepare(ds, 0, f1, ds->stb1.st_size, flags)) {
343 		err = got_error_from_errno();
344 		goto closem;
345 	}
346 	if (prepare(ds, 1, f2, ds->stb2.st_size, flags)) {
347 		err = got_error_from_errno();
348 		goto closem;
349 	}
350 
351 	prune(ds);
352 	sort(ds->sfile[0], ds->slen[0]);
353 	sort(ds->sfile[1], ds->slen[1]);
354 
355 	ds->member = (int *)ds->file[1];
356 	equiv(ds->sfile[0], ds->slen[0], ds->sfile[1], ds->slen[1], ds->member);
357 	ds->member = reallocarray(ds->member, ds->slen[1] + 2, sizeof(*ds->member));
358 	if (ds->member == NULL) {
359 		err = got_error_from_errno();
360 		goto closem;
361 	}
362 
363 	ds->class = (int *)ds->file[0];
364 	if (unsort(ds->sfile[0], ds->slen[0], ds->class)) {
365 		err = got_error_from_errno();
366 		goto closem;
367 	}
368 	ds->class = reallocarray(ds->class, ds->slen[0] + 2, sizeof(*ds->class));
369 	if (ds->class == NULL) {
370 		err = got_error_from_errno();
371 		goto closem;
372 	}
373 
374 	ds->klist = calloc(ds->slen[0] + 2, sizeof(*ds->klist));
375 	if (ds->klist == NULL) {
376 		err = got_error_from_errno();
377 		goto closem;
378 	}
379 	ds->clen = 0;
380 	ds->clistlen = 100;
381 	ds->clist = calloc(ds->clistlen, sizeof(*ds->clist));
382 	if (ds->clist == NULL) {
383 		err = got_error_from_errno();
384 		goto closem;
385 	}
386 	i = stone(ds, ds->class, ds->slen[0], ds->member, ds->klist, flags);
387 	if (i < 0) {
388 		err = got_error_from_errno();
389 		free(ds->member);
390 		free(ds->class);
391 		goto closem;
392 	}
393 	free(ds->member);
394 	free(ds->class);
395 
396 	ds->J = reallocarray(ds->J, ds->len[0] + 2, sizeof(*ds->J));
397 	if (ds->J == NULL) {
398 		err = got_error_from_errno();
399 		goto closem;
400 	}
401 	unravel(ds, ds->klist[i]);
402 	free(ds->clist);
403 	ds->clist = NULL;
404 	free(ds->klist);
405 	ds->klist = NULL;
406 
407 	ds->ixold = reallocarray(ds->ixold, ds->len[0] + 2, sizeof(*ds->ixold));
408 	if (ds->ixold == NULL) {
409 		err = got_error_from_errno();
410 		goto closem;
411 	}
412 	ds->ixnew = reallocarray(ds->ixnew, ds->len[1] + 2, sizeof(*ds->ixnew));
413 	if (ds->ixnew == NULL) {
414 		err = got_error_from_errno();
415 		goto closem;
416 	}
417 	check(ds, f1, f2, flags);
418 	if (output(outfile, ds, args, args->label[0], f1, args->label[1], f2,
419 	    flags))
420 		err = got_error_from_errno();
421 closem:
422 	if (ds->anychange) {
423 		args->status |= 1;
424 		if (*rval == D_SAME)
425 			*rval = D_DIFFER;
426 	}
427 	if (f1 != NULL)
428 		fclose(f1);
429 	if (f2 != NULL)
430 		fclose(f2);
431 
432 	return (err);
433 }
434 
435 /*
436  * Check to see if the given files differ.
437  * Returns 0 if they are the same, 1 if different, and -1 on error.
438  * XXX - could use code from cmp(1) [faster]
439  */
440 static int
441 files_differ(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
442 {
443 	char buf1[BUFSIZ], buf2[BUFSIZ];
444 	size_t i, j;
445 
446 	if ((flags & (D_EMPTY1|D_EMPTY2)) || ds->stb1.st_size != ds->stb2.st_size ||
447 	    (ds->stb1.st_mode & S_IFMT) != (ds->stb2.st_mode & S_IFMT))
448 		return (1);
449 	for (;;) {
450 		i = fread(buf1, 1, sizeof(buf1), f1);
451 		j = fread(buf2, 1, sizeof(buf2), f2);
452 		if ((!i && ferror(f1)) || (!j && ferror(f2)))
453 			return (-1);
454 		if (i != j)
455 			return (1);
456 		if (i == 0)
457 			return (0);
458 		if (memcmp(buf1, buf2, i) != 0)
459 			return (1);
460 	}
461 }
462 
463 static int
464 prepare(struct got_diff_state *ds, int i, FILE *fd, off_t filesize, int flags)
465 {
466 	struct line *p;
467 	int j, h;
468 	size_t sz;
469 
470 	rewind(fd);
471 
472 	sz = (filesize <= SIZE_MAX ? filesize : SIZE_MAX) / 25;
473 	if (sz < 100)
474 		sz = 100;
475 
476 	p = calloc(sz + 3, sizeof(*p));
477 	if (p == NULL)
478 		return (-1);
479 	for (j = 0; (h = readhash(ds, fd, flags));) {
480 		if (j == sz) {
481 			sz = sz * 3 / 2;
482 			p = reallocarray(p, sz + 3, sizeof(*p));
483 			if (p == NULL)
484 				return (-1);
485 		}
486 		p[++j].value = h;
487 	}
488 	ds->len[i] = j;
489 	ds->file[i] = p;
490 
491 	return (0);
492 }
493 
494 static void
495 prune(struct got_diff_state *ds)
496 {
497 	int i, j;
498 
499 	for (ds->pref = 0; ds->pref < ds->len[0] && ds->pref < ds->len[1] &&
500 	    ds->file[0][ds->pref + 1].value == ds->file[1][ds->pref + 1].value;
501 	    ds->pref++)
502 		;
503 	for (ds->suff = 0; ds->suff < ds->len[0] - ds->pref && ds->suff < ds->len[1] - ds->pref &&
504 	    ds->file[0][ds->len[0] - ds->suff].value == ds->file[1][ds->len[1] - ds->suff].value;
505 	    ds->suff++)
506 		;
507 	for (j = 0; j < 2; j++) {
508 		ds->sfile[j] = ds->file[j] + ds->pref;
509 		ds->slen[j] = ds->len[j] - ds->pref - ds->suff;
510 		for (i = 0; i <= ds->slen[j]; i++)
511 			ds->sfile[j][i].serial = i;
512 	}
513 }
514 
515 static void
516 equiv(struct line *a, int n, struct line *b, int m, int *c)
517 {
518 	int i, j;
519 
520 	i = j = 1;
521 	while (i <= n && j <= m) {
522 		if (a[i].value < b[j].value)
523 			a[i++].value = 0;
524 		else if (a[i].value == b[j].value)
525 			a[i++].value = j;
526 		else
527 			j++;
528 	}
529 	while (i <= n)
530 		a[i++].value = 0;
531 	b[m + 1].value = 0;
532 	j = 0;
533 	while (++j <= m) {
534 		c[j] = -b[j].serial;
535 		while (b[j + 1].value == b[j].value) {
536 			j++;
537 			c[j] = b[j].serial;
538 		}
539 	}
540 	c[j] = -1;
541 }
542 
543 /* Code taken from ping.c */
544 static int
545 isqrt(int n)
546 {
547 	int y, x = 1;
548 
549 	if (n == 0)
550 		return (0);
551 
552 	do { /* newton was a stinker */
553 		y = x;
554 		x = n / x;
555 		x += y;
556 		x /= 2;
557 	} while ((x - y) > 1 || (x - y) < -1);
558 
559 	return (x);
560 }
561 
562 static int
563 stone(struct got_diff_state *ds, int *a, int n, int *b, int *c, int flags)
564 {
565 	int i, k, y, j, l;
566 	int oldc, tc, oldl, sq;
567 	u_int numtries, bound;
568 	int error;
569 
570 	if (flags & D_MINIMAL)
571 		bound = UINT_MAX;
572 	else {
573 		sq = isqrt(n);
574 		bound = MAXIMUM(256, sq);
575 	}
576 
577 	k = 0;
578 	c[0] = newcand(ds, 0, 0, 0, &error);
579 	if (error)
580 		return -1;
581 	for (i = 1; i <= n; i++) {
582 		j = a[i];
583 		if (j == 0)
584 			continue;
585 		y = -b[j];
586 		oldl = 0;
587 		oldc = c[0];
588 		numtries = 0;
589 		do {
590 			if (y <= ds->clist[oldc].y)
591 				continue;
592 			l = search(ds, c, k, y);
593 			if (l != oldl + 1)
594 				oldc = c[l - 1];
595 			if (l <= k) {
596 				if (ds->clist[c[l]].y <= y)
597 					continue;
598 				tc = c[l];
599 				c[l] = newcand(ds, i, y, oldc, &error);
600 				if (error)
601 					return -1;
602 				oldc = tc;
603 				oldl = l;
604 				numtries++;
605 			} else {
606 				c[l] = newcand(ds, i, y, oldc, &error);
607 				if (error)
608 					return -1;
609 				k++;
610 				break;
611 			}
612 		} while ((y = b[++j]) > 0 && numtries < bound);
613 	}
614 	return (k);
615 }
616 
617 static int
618 newcand(struct got_diff_state *ds, int x, int y, int pred, int *errorp)
619 {
620 	struct cand *q;
621 
622 	if (ds->clen == ds->clistlen) {
623 		ds->clistlen = ds->clistlen * 11 / 10;
624 		ds->clist = reallocarray(ds->clist, ds->clistlen,
625 		    sizeof(*ds->clist));
626 		if (ds->clist == NULL) {
627 			*errorp = -1;
628 			return 0;
629 		}
630 	}
631 	q = ds->clist + ds->clen;
632 	q->x = x;
633 	q->y = y;
634 	q->pred = pred;
635 	*errorp = 0;
636 	return (ds->clen++);
637 }
638 
639 static int
640 search(struct got_diff_state *ds, int *c, int k, int y)
641 {
642 	int i, j, l, t;
643 
644 	if (ds->clist[c[k]].y < y)	/* quick look for typical case */
645 		return (k + 1);
646 	i = 0;
647 	j = k + 1;
648 	for (;;) {
649 		l = (i + j) / 2;
650 		if (l <= i)
651 			break;
652 		t = ds->clist[c[l]].y;
653 		if (t > y)
654 			j = l;
655 		else if (t < y)
656 			i = l;
657 		else
658 			return (l);
659 	}
660 	return (l + 1);
661 }
662 
663 static void
664 unravel(struct got_diff_state *ds, int p)
665 {
666 	struct cand *q;
667 	int i;
668 
669 	for (i = 0; i <= ds->len[0]; i++)
670 		ds->J[i] = i <= ds->pref ? i :
671 		    i > ds->len[0] - ds->suff ? i + ds->len[1] - ds->len[0] : 0;
672 	for (q = ds->clist + p; q->y != 0; q = ds->clist + q->pred)
673 		ds->J[q->x + ds->pref] = q->y + ds->pref;
674 }
675 
676 /*
677  * Check does double duty:
678  *  1.	ferret out any fortuitous correspondences due
679  *	to confounding by hashing (which result in "jackpot")
680  *  2.  collect random access indexes to the two files
681  */
682 static void
683 check(struct got_diff_state *ds, FILE *f1, FILE *f2, int flags)
684 {
685 	int i, j, jackpot, c, d;
686 	long ctold, ctnew;
687 
688 	rewind(f1);
689 	rewind(f2);
690 	j = 1;
691 	ds->ixold[0] = ds->ixnew[0] = 0;
692 	jackpot = 0;
693 	ctold = ctnew = 0;
694 	for (i = 1; i <= ds->len[0]; i++) {
695 		if (ds->J[i] == 0) {
696 			ds->ixold[i] = ctold += skipline(f1);
697 			continue;
698 		}
699 		while (j < ds->J[i]) {
700 			ds->ixnew[j] = ctnew += skipline(f2);
701 			j++;
702 		}
703 		if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS|D_IGNORECASE)) {
704 			for (;;) {
705 				c = getc(f1);
706 				d = getc(f2);
707 				/*
708 				 * GNU diff ignores a missing newline
709 				 * in one file for -b or -w.
710 				 */
711 				if (flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) {
712 					if (c == EOF && d == '\n') {
713 						ctnew++;
714 						break;
715 					} else if (c == '\n' && d == EOF) {
716 						ctold++;
717 						break;
718 					}
719 				}
720 				ctold++;
721 				ctnew++;
722 				if ((flags & D_FOLDBLANKS) && isspace(c) &&
723 				    isspace(d)) {
724 					do {
725 						if (c == '\n')
726 							break;
727 						ctold++;
728 					} while (isspace(c = getc(f1)));
729 					do {
730 						if (d == '\n')
731 							break;
732 						ctnew++;
733 					} while (isspace(d = getc(f2)));
734 				} else if ((flags & D_IGNOREBLANKS)) {
735 					while (isspace(c) && c != '\n') {
736 						c = getc(f1);
737 						ctold++;
738 					}
739 					while (isspace(d) && d != '\n') {
740 						d = getc(f2);
741 						ctnew++;
742 					}
743 				}
744 				if (ds->chrtran[c] != ds->chrtran[d]) {
745 					jackpot++;
746 					ds->J[i] = 0;
747 					if (c != '\n' && c != EOF)
748 						ctold += skipline(f1);
749 					if (d != '\n' && c != EOF)
750 						ctnew += skipline(f2);
751 					break;
752 				}
753 				if (c == '\n' || c == EOF)
754 					break;
755 			}
756 		} else {
757 			for (;;) {
758 				ctold++;
759 				ctnew++;
760 				if ((c = getc(f1)) != (d = getc(f2))) {
761 					/* jackpot++; */
762 					ds->J[i] = 0;
763 					if (c != '\n' && c != EOF)
764 						ctold += skipline(f1);
765 					if (d != '\n' && c != EOF)
766 						ctnew += skipline(f2);
767 					break;
768 				}
769 				if (c == '\n' || c == EOF)
770 					break;
771 			}
772 		}
773 		ds->ixold[i] = ctold;
774 		ds->ixnew[j] = ctnew;
775 		j++;
776 	}
777 	for (; j <= ds->len[1]; j++)
778 		ds->ixnew[j] = ctnew += skipline(f2);
779 	/*
780 	 * if (jackpot)
781 	 *	fprintf(stderr, "jackpot\n");
782 	 */
783 }
784 
785 /* shellsort CACM #201 */
786 static void
787 sort(struct line *a, int n)
788 {
789 	struct line *ai, *aim, w;
790 	int j, m = 0, k;
791 
792 	if (n == 0)
793 		return;
794 	for (j = 1; j <= n; j *= 2)
795 		m = 2 * j - 1;
796 	for (m /= 2; m != 0; m /= 2) {
797 		k = n - m;
798 		for (j = 1; j <= k; j++) {
799 			for (ai = &a[j]; ai > a; ai -= m) {
800 				aim = &ai[m];
801 				if (aim < ai)
802 					break;	/* wraparound */
803 				if (aim->value > ai[0].value ||
804 				    (aim->value == ai[0].value &&
805 					aim->serial > ai[0].serial))
806 					break;
807 				w.value = ai[0].value;
808 				ai[0].value = aim->value;
809 				aim->value = w.value;
810 				w.serial = ai[0].serial;
811 				ai[0].serial = aim->serial;
812 				aim->serial = w.serial;
813 			}
814 		}
815 	}
816 }
817 
818 static int
819 unsort(struct line *f, int l, int *b)
820 {
821 	int *a, i;
822 
823 	a = calloc(l + 1, sizeof(*a));
824 	if (a == NULL)
825 		return (-1);
826 	for (i = 1; i <= l; i++)
827 		a[f[i].serial] = f[i].value;
828 	for (i = 1; i <= l; i++)
829 		b[i] = a[i];
830 	free(a);
831 
832 	return (0);
833 }
834 
835 static int
836 skipline(FILE *f)
837 {
838 	int i, c;
839 
840 	for (i = 1; (c = getc(f)) != '\n' && c != EOF; i++)
841 		continue;
842 	return (i);
843 }
844 
845 static int
846 output(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
847     const char *file1, FILE *f1, const char *file2, FILE *f2, int flags)
848 {
849 	int m, i0, i1, j0, j1;
850 	int error = 0;
851 
852 	rewind(f1);
853 	rewind(f2);
854 	m = ds->len[0];
855 	ds->J[0] = 0;
856 	ds->J[m + 1] = ds->len[1] + 1;
857 	if (args->diff_format != D_EDIT) {
858 		for (i0 = 1; i0 <= m; i0 = i1 + 1) {
859 			while (i0 <= m && ds->J[i0] == ds->J[i0 - 1] + 1)
860 				i0++;
861 			j0 = ds->J[i0 - 1] + 1;
862 			i1 = i0 - 1;
863 			while (i1 < m && ds->J[i1 + 1] == 0)
864 				i1++;
865 			j1 = ds->J[i1 + 1] - 1;
866 			ds->J[i1] = j1;
867 			error = change(outfile, ds, args, file1, f1, file2, f2,
868 			    i0, i1, j0, j1, &flags);
869 			if (error)
870 				return (error);
871 		}
872 	} else {
873 		for (i0 = m; i0 >= 1; i0 = i1 - 1) {
874 			while (i0 >= 1 && ds->J[i0] == ds->J[i0 + 1] - 1 && ds->J[i0] != 0)
875 				i0--;
876 			j0 = ds->J[i0 + 1] - 1;
877 			i1 = i0 + 1;
878 			while (i1 > 1 && ds->J[i1 - 1] == 0)
879 				i1--;
880 			j1 = ds->J[i1 - 1] + 1;
881 			ds->J[i1] = j1;
882 			change(outfile, ds, args, file1, f1, file2, f2, i1, i0,
883 			    j1, j0, &flags);
884 			if (error)
885 				return (error);
886 		}
887 	}
888 	if (m == 0) {
889 		error = change(outfile, ds, args, file1, f1, file2, f2, 1, 0,
890 		    1, ds->len[1], &flags);
891 		if (error)
892 			return (error);
893 	}
894 	if (args->diff_format == D_IFDEF) {
895 		for (;;) {
896 #define	c i0
897 			if ((c = getc(f1)) == EOF)
898 				return (0);
899 			diff_output(outfile, "%c", c);
900 		}
901 #undef c
902 	}
903 	if (ds->anychange != 0) {
904 		if (args->diff_format == D_CONTEXT)
905 			dump_context_vec(outfile, ds, args, f1, f2, flags);
906 		else if (args->diff_format == D_UNIFIED)
907 			dump_unified_vec(outfile, ds, args, f1, f2, flags);
908 	}
909 
910 	return (0);
911 }
912 
913 static void
914 range(FILE *outfile, int a, int b, char *separator)
915 {
916 	diff_output(outfile, "%d", a > b ? b : a);
917 	if (a < b)
918 		diff_output(outfile, "%s%d", separator, b);
919 }
920 
921 static void
922 uni_range(FILE *outfile, int a, int b)
923 {
924 	if (a < b)
925 		diff_output(outfile, "%d,%d", a, b - a + 1);
926 	else if (a == b)
927 		diff_output(outfile, "%d", b);
928 	else
929 		diff_output(outfile, "%d,0", b);
930 }
931 
932 static char *
933 preadline(int fd, size_t rlen, off_t off)
934 {
935 	char *line;
936 	ssize_t nr;
937 
938 	line = malloc(rlen + 1);
939 	if (line == NULL)
940 		return NULL;
941 	if ((nr = pread(fd, line, rlen, off)) < 0) {
942 		free(line);
943 		return NULL;
944 	}
945 	if (nr > 0 && line[nr-1] == '\n')
946 		nr--;
947 	line[nr] = '\0';
948 	return (line);
949 }
950 
951 static int
952 ignoreline(char *line)
953 {
954 	return 0; /* do not ignore any lines */
955 }
956 
957 /*
958  * Indicate that there is a difference between lines a and b of the from file
959  * to get to lines c to d of the to file.  If a is greater then b then there
960  * are no lines in the from file involved and this means that there were
961  * lines appended (beginning at b).  If c is greater than d then there are
962  * lines missing from the to file.
963  */
964 static int
965 change(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
966     const char *file1, FILE *f1, const char *file2, FILE *f2,
967     int a, int b, int c, int d, int *pflags)
968 {
969 	size_t max_context = 64;
970 	int i;
971 
972 restart:
973 	if (args->diff_format != D_IFDEF && a > b && c > d)
974 		return (0);
975 	if (args->ignore_pats != NULL) {
976 		char *line;
977 		/*
978 		 * All lines in the change, insert, or delete must
979 		 * match an ignore pattern for the change to be
980 		 * ignored.
981 		 */
982 		if (a <= b) {		/* Changes and deletes. */
983 			for (i = a; i <= b; i++) {
984 				line = preadline(fileno(f1),
985 				    ds->ixold[i] - ds->ixold[i - 1],
986 				    ds->ixold[i - 1]);
987 				if (line == NULL)
988 					return (-1);
989 				if (!ignoreline(line))
990 					goto proceed;
991 			}
992 		}
993 		if (a > b || c <= d) {	/* Changes and inserts. */
994 			for (i = c; i <= d; i++) {
995 				line = preadline(fileno(f2),
996 				    ds->ixnew[i] - ds->ixnew[i - 1],
997 				    ds->ixnew[i - 1]);
998 				if (line == NULL)
999 					return (-1);
1000 				if (!ignoreline(line))
1001 					goto proceed;
1002 			}
1003 		}
1004 		return (0);
1005 	}
1006 proceed:
1007 	if (*pflags & D_HEADER) {
1008 		diff_output(outfile, "%s %s %s\n", args->diffargs, file1, file2);
1009 		*pflags &= ~D_HEADER;
1010 	}
1011 	if (args->diff_format == D_CONTEXT || args->diff_format == D_UNIFIED) {
1012 		/*
1013 		 * Allocate change records as needed.
1014 		 */
1015 		if (ds->context_vec_ptr == ds->context_vec_end - 1) {
1016 			ptrdiff_t offset = ds->context_vec_ptr - ds->context_vec_start;
1017 			max_context <<= 1;
1018 			ds->context_vec_start =
1019 			    reallocarray(ds->context_vec_start, max_context,
1020 				sizeof(*ds->context_vec_start));
1021 			if (ds->context_vec_start == NULL)
1022 				return (-1);
1023 			ds->context_vec_end = ds->context_vec_start + max_context;
1024 			ds->context_vec_ptr = ds->context_vec_start + offset;
1025 		}
1026 		if (ds->anychange == 0) {
1027 			/*
1028 			 * Print the context/unidiff header first time through.
1029 			 */
1030 			print_header(outfile, ds, args, file1, file2);
1031 			ds->anychange = 1;
1032 		} else if (a > ds->context_vec_ptr->b + (2 * args->diff_context) + 1 &&
1033 		    c > ds->context_vec_ptr->d + (2 * args->diff_context) + 1) {
1034 			/*
1035 			 * If this change is more than 'diff_context' lines from the
1036 			 * previous change, dump the record and reset it.
1037 			 */
1038 			if (args->diff_format == D_CONTEXT)
1039 				dump_context_vec(outfile, ds, args, f1, f2, *pflags);
1040 			else
1041 				dump_unified_vec(outfile, ds, args, f1, f2, *pflags);
1042 		}
1043 		ds->context_vec_ptr++;
1044 		ds->context_vec_ptr->a = a;
1045 		ds->context_vec_ptr->b = b;
1046 		ds->context_vec_ptr->c = c;
1047 		ds->context_vec_ptr->d = d;
1048 		return (0);
1049 	}
1050 	if (ds->anychange == 0)
1051 		ds->anychange = 1;
1052 	switch (args->diff_format) {
1053 	case D_BRIEF:
1054 		return (0);
1055 	case D_NORMAL:
1056 	case D_EDIT:
1057 		range(outfile, a, b, ",");
1058 		diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1059 		if (args->diff_format == D_NORMAL)
1060 			range(outfile, c, d, ",");
1061 		diff_output(outfile, "\n");
1062 		break;
1063 	case D_REVERSE:
1064 		diff_output(outfile, "%c", a > b ? 'a' : c > d ? 'd' : 'c');
1065 		range(outfile, a, b, " ");
1066 		diff_output(outfile, "\n");
1067 		break;
1068 	case D_NREVERSE:
1069 		if (a > b)
1070 			diff_output(outfile, "a%d %d\n", b, d - c + 1);
1071 		else {
1072 			diff_output(outfile, "d%d %d\n", a, b - a + 1);
1073 			if (!(c > d))
1074 				/* add changed lines */
1075 				diff_output(outfile, "a%d %d\n", b, d - c + 1);
1076 		}
1077 		break;
1078 	}
1079 	if (args->diff_format == D_NORMAL || args->diff_format == D_IFDEF) {
1080 		fetch(outfile, ds, args, ds->ixold, a, b, f1, '<', 1, *pflags);
1081 		if (a <= b && c <= d && args->diff_format == D_NORMAL)
1082 			diff_output(outfile, "---\n");
1083 	}
1084 	i = fetch(outfile, ds, args, ds->ixnew, c, d, f2, args->diff_format == D_NORMAL ? '>' : '\0', 0, *pflags);
1085 	if (i != 0 && args->diff_format == D_EDIT) {
1086 		/*
1087 		 * A non-zero return value for D_EDIT indicates that the
1088 		 * last line printed was a bare dot (".") that has been
1089 		 * escaped as ".." to prevent ed(1) from misinterpreting
1090 		 * it.  We have to add a substitute command to change this
1091 		 * back and restart where we left off.
1092 		 */
1093 		diff_output(outfile, ".\n");
1094 		diff_output(outfile, "%ds/.//\n", a + i - 1);
1095 		b = a + i - 1;
1096 		a = b + 1;
1097 		c += i;
1098 		goto restart;
1099 	}
1100 	if ((args->diff_format == D_EDIT || args->diff_format == D_REVERSE) && c <= d)
1101 		diff_output(outfile, ".\n");
1102 	if (ds->inifdef) {
1103 		diff_output(outfile, "#endif /* %s */\n", args->ifdefname);
1104 		ds->inifdef = 0;
1105 	}
1106 
1107 	return (0);
1108 }
1109 
1110 static int
1111 fetch(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1112     long *f, int a, int b, FILE *lb, int ch, int oldfile, int flags)
1113 {
1114 	int i, j, c, lastc, col, nc;
1115 
1116 	/*
1117 	 * When doing #ifdef's, copy down to current line
1118 	 * if this is the first file, so that stuff makes it to output.
1119 	 */
1120 	if (args->diff_format == D_IFDEF && oldfile) {
1121 		long curpos = ftell(lb);
1122 		/* print through if append (a>b), else to (nb: 0 vs 1 orig) */
1123 		nc = f[a > b ? b : a - 1] - curpos;
1124 		for (i = 0; i < nc; i++)
1125 			diff_output(outfile, "%c", getc(lb));
1126 	}
1127 	if (a > b)
1128 		return (0);
1129 	if (args->diff_format == D_IFDEF) {
1130 		if (ds->inifdef) {
1131 			diff_output(outfile, "#else /* %s%s */\n",
1132 			    oldfile == 1 ? "!" : "", args->ifdefname);
1133 		} else {
1134 			if (oldfile)
1135 				diff_output(outfile, "#ifndef %s\n", args->ifdefname);
1136 			else
1137 				diff_output(outfile, "#ifdef %s\n", args->ifdefname);
1138 		}
1139 		ds->inifdef = 1 + oldfile;
1140 	}
1141 	for (i = a; i <= b; i++) {
1142 		fseek(lb, f[i - 1], SEEK_SET);
1143 		nc = f[i] - f[i - 1];
1144 		if (args->diff_format != D_IFDEF && ch != '\0') {
1145 			diff_output(outfile, "%c", ch);
1146 			if (args->Tflag && (args->diff_format == D_NORMAL || args->diff_format == D_CONTEXT
1147 			    || args->diff_format == D_UNIFIED))
1148 				diff_output(outfile, "\t");
1149 			else if (args->diff_format != D_UNIFIED)
1150 				diff_output(outfile, " ");
1151 		}
1152 		col = 0;
1153 		for (j = 0, lastc = '\0'; j < nc; j++, lastc = c) {
1154 			if ((c = getc(lb)) == EOF) {
1155 				if (args->diff_format == D_EDIT || args->diff_format == D_REVERSE ||
1156 				    args->diff_format == D_NREVERSE)
1157 					warnx("No newline at end of file");
1158 				else
1159 					diff_output(outfile, "\n\\ No newline at end of "
1160 					    "file\n");
1161 				return (0);
1162 			}
1163 			if (c == '\t' && (flags & D_EXPANDTABS)) {
1164 				do {
1165 					diff_output(outfile, " ");
1166 				} while (++col & 7);
1167 			} else {
1168 				if (args->diff_format == D_EDIT && j == 1 && c == '\n'
1169 				    && lastc == '.') {
1170 					/*
1171 					 * Don't print a bare "." line
1172 					 * since that will confuse ed(1).
1173 					 * Print ".." instead and return,
1174 					 * giving the caller an offset
1175 					 * from which to restart.
1176 					 */
1177 					diff_output(outfile, ".\n");
1178 					return (i - a + 1);
1179 				}
1180 				diff_output(outfile, "%c", c);
1181 				col++;
1182 			}
1183 		}
1184 	}
1185 	return (0);
1186 }
1187 
1188 /*
1189  * Hash function taken from Robert Sedgewick, Algorithms in C, 3d ed., p 578.
1190  */
1191 static int
1192 readhash(struct got_diff_state *ds, FILE *f, int flags)
1193 {
1194 	int i, t, space;
1195 	int sum;
1196 
1197 	sum = 1;
1198 	space = 0;
1199 	if ((flags & (D_FOLDBLANKS|D_IGNOREBLANKS)) == 0) {
1200 		if (flags & D_IGNORECASE)
1201 			for (i = 0; (t = getc(f)) != '\n'; i++) {
1202 				if (t == EOF) {
1203 					if (i == 0)
1204 						return (0);
1205 					break;
1206 				}
1207 				sum = sum * 127 + ds->chrtran[t];
1208 			}
1209 		else
1210 			for (i = 0; (t = getc(f)) != '\n'; i++) {
1211 				if (t == EOF) {
1212 					if (i == 0)
1213 						return (0);
1214 					break;
1215 				}
1216 				sum = sum * 127 + t;
1217 			}
1218 	} else {
1219 		for (i = 0;;) {
1220 			switch (t = getc(f)) {
1221 			case '\t':
1222 			case '\r':
1223 			case '\v':
1224 			case '\f':
1225 			case ' ':
1226 				space++;
1227 				continue;
1228 			default:
1229 				if (space && (flags & D_IGNOREBLANKS) == 0) {
1230 					i++;
1231 					space = 0;
1232 				}
1233 				sum = sum * 127 + ds->chrtran[t];
1234 				i++;
1235 				continue;
1236 			case EOF:
1237 				if (i == 0)
1238 					return (0);
1239 				/* FALLTHROUGH */
1240 			case '\n':
1241 				break;
1242 			}
1243 			break;
1244 		}
1245 	}
1246 	/*
1247 	 * There is a remote possibility that we end up with a zero sum.
1248 	 * Zero is used as an EOF marker, so return 1 instead.
1249 	 */
1250 	return (sum == 0 ? 1 : sum);
1251 }
1252 
1253 static int
1254 asciifile(FILE *f)
1255 {
1256 	unsigned char buf[BUFSIZ];
1257 	size_t cnt;
1258 
1259 	if (f == NULL)
1260 		return (1);
1261 
1262 	rewind(f);
1263 	cnt = fread(buf, 1, sizeof(buf), f);
1264 	return (memchr(buf, '\0', cnt) == NULL);
1265 }
1266 
1267 #define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
1268 
1269 static char *
1270 match_function(struct got_diff_state *ds, const long *f, int pos, FILE *fp)
1271 {
1272 	unsigned char buf[FUNCTION_CONTEXT_SIZE];
1273 	size_t nc;
1274 	int last = ds->lastline;
1275 	char *state = NULL;
1276 
1277 	ds->lastline = pos;
1278 	while (pos > last) {
1279 		fseek(fp, f[pos - 1], SEEK_SET);
1280 		nc = f[pos] - f[pos - 1];
1281 		if (nc >= sizeof(buf))
1282 			nc = sizeof(buf) - 1;
1283 		nc = fread(buf, 1, nc, fp);
1284 		if (nc > 0) {
1285 			buf[nc] = '\0';
1286 			buf[strcspn(buf, "\n")] = '\0';
1287 			if (isalpha(buf[0]) || buf[0] == '_' || buf[0] == '$') {
1288 				if (begins_with(buf, "private:")) {
1289 					if (!state)
1290 						state = " (private)";
1291 				} else if (begins_with(buf, "protected:")) {
1292 					if (!state)
1293 						state = " (protected)";
1294 				} else if (begins_with(buf, "public:")) {
1295 					if (!state)
1296 						state = " (public)";
1297 				} else {
1298 					strlcpy(ds->lastbuf, buf, sizeof ds->lastbuf);
1299 					if (state)
1300 						strlcat(ds->lastbuf, state,
1301 						    sizeof ds->lastbuf);
1302 					ds->lastmatchline = pos;
1303 					return ds->lastbuf;
1304 				}
1305 			}
1306 		}
1307 		pos--;
1308 	}
1309 	return ds->lastmatchline > 0 ? ds->lastbuf : NULL;
1310 }
1311 
1312 /* dump accumulated "context" diff changes */
1313 static void
1314 dump_context_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1315     FILE *f1, FILE *f2, int flags)
1316 {
1317 	struct context_vec *cvp = ds->context_vec_start;
1318 	int lowa, upb, lowc, upd, do_output;
1319 	int a, b, c, d;
1320 	char ch, *f;
1321 
1322 	if (ds->context_vec_start > ds->context_vec_ptr)
1323 		return;
1324 
1325 	b = d = 0;		/* gcc */
1326 	lowa = MAXIMUM(1, cvp->a - args->diff_context);
1327 	upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1328 	lowc = MAXIMUM(1, cvp->c - args->diff_context);
1329 	upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1330 
1331 	diff_output(outfile, "***************");
1332 	if ((flags & D_PROTOTYPE)) {
1333 		f = match_function(ds, ds->ixold, lowa-1, f1);
1334 		if (f != NULL)
1335 			diff_output(outfile, " %s", f);
1336 	}
1337 	diff_output(outfile, "\n*** ");
1338 	range(outfile, lowa, upb, ",");
1339 	diff_output(outfile, " ****\n");
1340 
1341 	/*
1342 	 * Output changes to the "old" file.  The first loop suppresses
1343 	 * output if there were no changes to the "old" file (we'll see
1344 	 * the "old" lines as context in the "new" list).
1345 	 */
1346 	do_output = 0;
1347 	for (; cvp <= ds->context_vec_ptr; cvp++)
1348 		if (cvp->a <= cvp->b) {
1349 			cvp = ds->context_vec_start;
1350 			do_output++;
1351 			break;
1352 		}
1353 	if (do_output) {
1354 		while (cvp <= ds->context_vec_ptr) {
1355 			a = cvp->a;
1356 			b = cvp->b;
1357 			c = cvp->c;
1358 			d = cvp->d;
1359 
1360 			if (a <= b && c <= d)
1361 				ch = 'c';
1362 			else
1363 				ch = (a <= b) ? 'd' : 'a';
1364 
1365 			if (ch == 'a')
1366 				fetch(outfile, ds, args, ds->ixold, lowa, b, f1, ' ', 0, flags);
1367 			else {
1368 				fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1369 				fetch(outfile, ds, args, ds->ixold, a, b, f1,
1370 				    ch == 'c' ? '!' : '-', 0, flags);
1371 			}
1372 			lowa = b + 1;
1373 			cvp++;
1374 		}
1375 		fetch(outfile, ds, args, ds->ixold, b + 1, upb, f1, ' ', 0, flags);
1376 	}
1377 	/* output changes to the "new" file */
1378 	diff_output(outfile, "--- ");
1379 	range(outfile, lowc, upd, ",");
1380 	diff_output(outfile, " ----\n");
1381 
1382 	do_output = 0;
1383 	for (cvp = ds->context_vec_start; cvp <= ds->context_vec_ptr; cvp++)
1384 		if (cvp->c <= cvp->d) {
1385 			cvp = ds->context_vec_start;
1386 			do_output++;
1387 			break;
1388 		}
1389 	if (do_output) {
1390 		while (cvp <= ds->context_vec_ptr) {
1391 			a = cvp->a;
1392 			b = cvp->b;
1393 			c = cvp->c;
1394 			d = cvp->d;
1395 
1396 			if (a <= b && c <= d)
1397 				ch = 'c';
1398 			else
1399 				ch = (a <= b) ? 'd' : 'a';
1400 
1401 			if (ch == 'd')
1402 				fetch(outfile, ds, args, ds->ixnew, lowc, d, f2, ' ', 0, flags);
1403 			else {
1404 				fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1405 				fetch(outfile, ds, args, ds->ixnew, c, d, f2,
1406 				    ch == 'c' ? '!' : '+', 0, flags);
1407 			}
1408 			lowc = d + 1;
1409 			cvp++;
1410 		}
1411 		fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1412 	}
1413 	ds->context_vec_ptr = ds->context_vec_start - 1;
1414 }
1415 
1416 /* dump accumulated "unified" diff changes */
1417 static void
1418 dump_unified_vec(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1419     FILE *f1, FILE *f2, int flags)
1420 {
1421 	struct context_vec *cvp = ds->context_vec_start;
1422 	int lowa, upb, lowc, upd;
1423 	int a, b, c, d;
1424 	char ch, *f;
1425 
1426 	if (ds->context_vec_start > ds->context_vec_ptr)
1427 		return;
1428 
1429 	b = d = 0;		/* gcc */
1430 	lowa = MAXIMUM(1, cvp->a - args->diff_context);
1431 	upb = MINIMUM(ds->len[0], ds->context_vec_ptr->b + args->diff_context);
1432 	lowc = MAXIMUM(1, cvp->c - args->diff_context);
1433 	upd = MINIMUM(ds->len[1], ds->context_vec_ptr->d + args->diff_context);
1434 
1435 	diff_output(outfile, "@@ -");
1436 	uni_range(outfile, lowa, upb);
1437 	diff_output(outfile, " +");
1438 	uni_range(outfile, lowc, upd);
1439 	diff_output(outfile, " @@");
1440 	if ((flags & D_PROTOTYPE)) {
1441 		f = match_function(ds, ds->ixold, lowa-1, f1);
1442 		if (f != NULL)
1443 			diff_output(outfile, " %s", f);
1444 	}
1445 	diff_output(outfile, "\n");
1446 
1447 	/*
1448 	 * Output changes in "unified" diff format--the old and new lines
1449 	 * are printed together.
1450 	 */
1451 	for (; cvp <= ds->context_vec_ptr; cvp++) {
1452 		a = cvp->a;
1453 		b = cvp->b;
1454 		c = cvp->c;
1455 		d = cvp->d;
1456 
1457 		/*
1458 		 * c: both new and old changes
1459 		 * d: only changes in the old file
1460 		 * a: only changes in the new file
1461 		 */
1462 		if (a <= b && c <= d)
1463 			ch = 'c';
1464 		else
1465 			ch = (a <= b) ? 'd' : 'a';
1466 
1467 		switch (ch) {
1468 		case 'c':
1469 			fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1470 			fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1471 			fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1472 			break;
1473 		case 'd':
1474 			fetch(outfile, ds, args, ds->ixold, lowa, a - 1, f1, ' ', 0, flags);
1475 			fetch(outfile, ds, args, ds->ixold, a, b, f1, '-', 0, flags);
1476 			break;
1477 		case 'a':
1478 			fetch(outfile, ds, args, ds->ixnew, lowc, c - 1, f2, ' ', 0, flags);
1479 			fetch(outfile, ds, args, ds->ixnew, c, d, f2, '+', 0, flags);
1480 			break;
1481 		}
1482 		lowa = b + 1;
1483 		lowc = d + 1;
1484 	}
1485 	fetch(outfile, ds, args, ds->ixnew, d + 1, upd, f2, ' ', 0, flags);
1486 
1487 	ds->context_vec_ptr = ds->context_vec_start - 1;
1488 }
1489 
1490 static void
1491 print_header(FILE *outfile, struct got_diff_state *ds, struct got_diff_args *args,
1492     const char *file1, const char *file2)
1493 {
1494 	if (args->label[0] != NULL)
1495 		diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "***" : "---",
1496 		    args->label[0]);
1497 	else
1498 		diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "***" : "---",
1499 		    file1, ctime(&ds->stb1.st_mtime));
1500 	if (args->label[1] != NULL)
1501 		diff_output(outfile, "%s %s\n", args->diff_format == D_CONTEXT ? "---" : "+++",
1502 		    args->label[1]);
1503 	else
1504 		diff_output(outfile, "%s %s\t%s", args->diff_format == D_CONTEXT ? "---" : "+++",
1505 		    file2, ctime(&ds->stb2.st_mtime));
1506 }