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