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