Commit | Line | Data |
---|---|---|
2791ff57 | 1 | /*- |
ad787160 C |
2 | * Copyright (c) 1991, 1993 |
3 | * The Regents of the University of California. All rights reserved. | |
2791ff57 | 4 | * |
ad787160 C |
5 | * This module is believed to contain source code proprietary to AT&T. |
6 | * Use and redistribution is subject to the Berkeley Software License | |
7 | * Agreement and your Software Agreement with AT&T (Western Electric). | |
2791ff57 KB |
8 | */ |
9 | ||
10 | #ifndef lint | |
ad787160 | 11 | static char sccsid[] = "@(#)diffreg.c 8.1 (Berkeley) 6/6/93"; |
2791ff57 | 12 | #endif /* not lint */ |
43454f97 BJ |
13 | |
14 | #include "diff.h" | |
dc3cb8b0 | 15 | #include "pathnames.h" |
43454f97 BJ |
16 | /* |
17 | * diff - compare two files. | |
18 | */ | |
19 | ||
20 | /* | |
21 | * Uses an algorithm due to Harold Stone, which finds | |
22 | * a pair of longest identical subsequences in the two | |
23 | * files. | |
24 | * | |
25 | * The major goal is to generate the match vector J. | |
26 | * J[i] is the index of the line in file1 corresponding | |
27 | * to line i file0. J[i] = 0 if there is no | |
28 | * such line in file1. | |
29 | * | |
30 | * Lines are hashed so as to work in core. All potential | |
31 | * matches are located by sorting the lines of each file | |
32 | * on the hash (called ``value''). In particular, this | |
33 | * collects the equivalence classes in file1 together. | |
34 | * Subroutine equiv replaces the value of each line in | |
35 | * file0 by the index of the first element of its | |
36 | * matching equivalence in (the reordered) file1. | |
37 | * To save space equiv squeezes file1 into a single | |
38 | * array member in which the equivalence classes | |
39 | * are simply concatenated, except that their first | |
40 | * members are flagged by changing sign. | |
41 | * | |
42 | * Next the indices that point into member are unsorted into | |
43 | * array class according to the original order of file0. | |
44 | * | |
45 | * The cleverness lies in routine stone. This marches | |
46 | * through the lines of file0, developing a vector klist | |
47 | * of "k-candidates". At step i a k-candidate is a matched | |
48 | * pair of lines x,y (x in file0 y in file1) such that | |
49 | * there is a common subsequence of length k | |
50 | * between the first i lines of file0 and the first y | |
51 | * lines of file1, but there is no such subsequence for | |
52 | * any smaller y. x is the earliest possible mate to y | |
53 | * that occurs in such a subsequence. | |
54 | * | |
55 | * Whenever any of the members of the equivalence class of | |
56 | * lines in file1 matable to a line in file0 has serial number | |
57 | * less than the y of some k-candidate, that k-candidate | |
58 | * with the smallest such y is replaced. The new | |
59 | * k-candidate is chained (via pred) to the current | |
60 | * k-1 candidate so that the actual subsequence can | |
61 | * be recovered. When a member has serial number greater | |
62 | * that the y of all k-candidates, the klist is extended. | |
63 | * At the end, the longest subsequence is pulled out | |
64 | * and placed in the array J by unravel | |
65 | * | |
66 | * With J in hand, the matches there recorded are | |
67 | * check'ed against reality to assure that no spurious | |
68 | * matches have crept in due to hashing. If they have, | |
69 | * they are broken, and "jackpot" is recorded--a harmless | |
70 | * matter except that a true match for a spuriously | |
71 | * mated line may now be unnecessarily reported as a change. | |
72 | * | |
73 | * Much of the complexity of the program comes simply | |
74 | * from trying to minimize core utilization and | |
75 | * maximize the range of doable problems by dynamically | |
76 | * allocating what is needed and reusing what is not. | |
77 | * The core requirements for problems larger than somewhat | |
78 | * are (in words) 2*length(file0) + length(file1) + | |
79 | * 3*(number of k-candidates installed), typically about | |
80 | * 6n words for files of length n. | |
81 | */ | |
82 | ||
83 | #define prints(s) fputs(s,stdout) | |
84 | ||
85 | FILE *input[2]; | |
86 | FILE *fopen(); | |
87 | ||
88 | struct cand { | |
89 | int x; | |
90 | int y; | |
91 | int pred; | |
92 | } cand; | |
93 | struct line { | |
94 | int serial; | |
95 | int value; | |
96 | } *file[2], line; | |
97 | int len[2]; | |
98 | struct line *sfile[2]; /* shortened by pruning common prefix and suffix */ | |
99 | int slen[2]; | |
100 | int pref, suff; /* length of prefix and suffix */ | |
101 | int *class; /* will be overlaid on file[0] */ | |
102 | int *member; /* will be overlaid on file[1] */ | |
103 | int *klist; /* will be overlaid on file[0] after class */ | |
104 | struct cand *clist; /* merely a free storage pot for candidates */ | |
105 | int clen = 0; | |
106 | int *J; /* will be overlaid on class */ | |
107 | long *ixold; /* will be overlaid on klist */ | |
108 | long *ixnew; /* will be overlaid on file[1] */ | |
c470b1f1 VJ |
109 | char *chrtran; /* translation table for case-folding */ |
110 | ||
111 | /* chrtran points to one of 2 translation tables: | |
112 | * cup2low if folding upper to lower case | |
113 | * clow2low if not folding case | |
114 | */ | |
115 | char clow2low[256] = { | |
116 | 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f, | |
117 | 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f, | |
118 | 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f, | |
119 | 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f, | |
120 | 0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f, | |
121 | 0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5a,0x5b,0x5c,0x5d,0x5e,0x5f, | |
122 | 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f, | |
123 | 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f, | |
124 | 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f, | |
125 | 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f, | |
126 | 0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf, | |
127 | 0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf, | |
128 | 0xc0,0xc1,0xc2,0xc3,0xc4,0xc5,0xc6,0xc7,0xc8,0xc9,0xca,0xcb,0xcc,0xcd,0xce,0xcf, | |
129 | 0xd0,0xd1,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xdb,0xdc,0xdd,0xde,0xdf, | |
130 | 0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef, | |
131 | 0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff | |
132 | }; | |
133 | ||
134 | char cup2low[256] = { | |
135 | 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f, | |
136 | 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f, | |
137 | 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f, | |
138 | 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f, | |
139 | 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f, | |
140 | 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f, | |
141 | 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f, | |
142 | 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f, | |
143 | 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8a,0x8b,0x8c,0x8d,0x8e,0x8f, | |
144 | 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0x9b,0x9c,0x9d,0x9e,0x9f, | |
145 | 0xa0,0xa1,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,0xa8,0xa9,0xaa,0xab,0xac,0xad,0xae,0xaf, | |
146 | 0xb0,0xb1,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xbb,0xbc,0xbd,0xbe,0xbf, | |
147 | 0xc0,0xc1,0xc2,0xc3,0xc4,0xc5,0xc6,0xc7,0xc8,0xc9,0xca,0xcb,0xcc,0xcd,0xce,0xcf, | |
148 | 0xd0,0xd1,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xdb,0xdc,0xdd,0xde,0xdf, | |
149 | 0xe0,0xe1,0xe2,0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xeb,0xec,0xed,0xee,0xef, | |
150 | 0xf0,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,0xf9,0xfa,0xfb,0xfc,0xfd,0xfe,0xff | |
151 | }; | |
43454f97 BJ |
152 | |
153 | diffreg() | |
154 | { | |
87f863b7 KM |
155 | register int i, j; |
156 | FILE *f1, *f2; | |
157 | char buf1[BUFSIZ], buf2[BUFSIZ]; | |
43454f97 BJ |
158 | |
159 | if (hflag) { | |
160 | diffargv[0] = "diffh"; | |
161 | execv(diffh, diffargv); | |
162 | fprintf(stderr, "diff: "); | |
163 | perror(diffh); | |
164 | done(); | |
165 | } | |
c470b1f1 | 166 | chrtran = (iflag? cup2low : clow2low); |
2f861666 | 167 | if ((stb1.st_mode & S_IFMT) == S_IFDIR) { |
43454f97 | 168 | file1 = splice(file1, file2); |
2f861666 KM |
169 | if (stat(file1, &stb1) < 0) { |
170 | fprintf(stderr, "diff: "); | |
171 | perror(file1); | |
172 | done(); | |
173 | } | |
174 | } else if ((stb2.st_mode & S_IFMT) == S_IFDIR) { | |
43454f97 | 175 | file2 = splice(file2, file1); |
2f861666 KM |
176 | if (stat(file2, &stb2) < 0) { |
177 | fprintf(stderr, "diff: "); | |
178 | perror(file2); | |
179 | done(); | |
180 | } | |
40f5ca2a | 181 | } else if ((stb1.st_mode & S_IFMT) != S_IFREG || !strcmp(file1, "-")) { |
43454f97 BJ |
182 | if (!strcmp(file2, "-")) { |
183 | fprintf(stderr, "diff: can't specify - -\n"); | |
184 | done(); | |
185 | } | |
186 | file1 = copytemp(); | |
2f861666 KM |
187 | if (stat(file1, &stb1) < 0) { |
188 | fprintf(stderr, "diff: "); | |
189 | perror(file1); | |
190 | done(); | |
191 | } | |
40f5ca2a | 192 | } else if ((stb2.st_mode & S_IFMT) != S_IFREG || !strcmp(file2, "-")) { |
43454f97 | 193 | file2 = copytemp(); |
2f861666 KM |
194 | if (stat(file2, &stb2) < 0) { |
195 | fprintf(stderr, "diff: "); | |
196 | perror(file2); | |
197 | done(); | |
198 | } | |
199 | } | |
87f863b7 KM |
200 | if ((f1 = fopen(file1, "r")) == NULL) { |
201 | fprintf(stderr, "diff: "); | |
202 | perror(file1); | |
87f863b7 KM |
203 | done(); |
204 | } | |
205 | if ((f2 = fopen(file2, "r")) == NULL) { | |
206 | fprintf(stderr, "diff: "); | |
207 | perror(file2); | |
208 | fclose(f1); | |
87f863b7 KM |
209 | done(); |
210 | } | |
211 | if (stb1.st_size != stb2.st_size) | |
212 | goto notsame; | |
213 | for (;;) { | |
6f7a12ee RH |
214 | i = fread(buf1, 1, BUFSIZ, f1); |
215 | j = fread(buf2, 1, BUFSIZ, f2); | |
87f863b7 KM |
216 | if (i < 0 || j < 0 || i != j) |
217 | goto notsame; | |
218 | if (i == 0 && j == 0) { | |
219 | fclose(f1); | |
220 | fclose(f2); | |
d6790f57 | 221 | status = 0; /* files don't differ */ |
87f863b7 KM |
222 | goto same; |
223 | } | |
224 | for (j = 0; j < i; j++) | |
225 | if (buf1[j] != buf2[j]) | |
226 | goto notsame; | |
227 | } | |
228 | notsame: | |
d6790f57 RH |
229 | /* |
230 | * Files certainly differ at this point; set status accordingly | |
231 | */ | |
232 | status = 1; | |
46235152 | 233 | if (!asciifile(f1) || !asciifile(f2)) { |
87f863b7 KM |
234 | printf("Binary files %s and %s differ\n", file1, file2); |
235 | fclose(f1); | |
236 | fclose(f2); | |
237 | done(); | |
238 | } | |
239 | prepare(0, f1); | |
240 | prepare(1, f2); | |
241 | fclose(f1); | |
242 | fclose(f2); | |
43454f97 BJ |
243 | prune(); |
244 | sort(sfile[0],slen[0]); | |
245 | sort(sfile[1],slen[1]); | |
246 | ||
247 | member = (int *)file[1]; | |
248 | equiv(sfile[0], slen[0], sfile[1], slen[1], member); | |
249 | member = (int *)ralloc((char *)member,(slen[1]+2)*sizeof(int)); | |
250 | ||
251 | class = (int *)file[0]; | |
252 | unsort(sfile[0], slen[0], class); | |
253 | class = (int *)ralloc((char *)class,(slen[0]+2)*sizeof(int)); | |
254 | ||
255 | klist = (int *)talloc((slen[0]+2)*sizeof(int)); | |
256 | clist = (struct cand *)talloc(sizeof(cand)); | |
87f863b7 | 257 | i = stone(class, slen[0], member, klist); |
43454f97 BJ |
258 | free((char *)member); |
259 | free((char *)class); | |
260 | ||
261 | J = (int *)talloc((len[0]+2)*sizeof(int)); | |
87f863b7 | 262 | unravel(klist[i]); |
43454f97 BJ |
263 | free((char *)clist); |
264 | free((char *)klist); | |
265 | ||
266 | ixold = (long *)talloc((len[0]+2)*sizeof(long)); | |
267 | ixnew = (long *)talloc((len[1]+2)*sizeof(long)); | |
268 | check(); | |
269 | output(); | |
270 | status = anychange; | |
87f863b7 | 271 | same: |
43454f97 BJ |
272 | if (opt == D_CONTEXT && anychange == 0) |
273 | printf("No differences encountered\n"); | |
274 | done(); | |
275 | } | |
276 | ||
11c1760c | 277 | char tempfile[] = _PATH_TMP; |
409c6513 | 278 | |
43454f97 BJ |
279 | char * |
280 | copytemp() | |
281 | { | |
282 | char buf[BUFSIZ]; | |
283 | register int i, f; | |
284 | ||
285 | signal(SIGHUP,done); | |
286 | signal(SIGINT,done); | |
287 | signal(SIGPIPE,done); | |
288 | signal(SIGTERM,done); | |
409c6513 | 289 | mktemp(tempfile); |
43454f97 BJ |
290 | f = creat(tempfile,0600); |
291 | if (f < 0) { | |
804c14e9 | 292 | fprintf(stderr, "diff: "); |
43454f97 BJ |
293 | perror(tempfile); |
294 | done(); | |
295 | } | |
296 | while ((i = read(0,buf,BUFSIZ)) > 0) | |
297 | if (write(f,buf,i) != i) { | |
298 | fprintf(stderr, "diff: "); | |
299 | perror(tempfile); | |
300 | done(); | |
301 | } | |
302 | close(f); | |
303 | return (tempfile); | |
304 | } | |
305 | ||
306 | char * | |
307 | splice(dir, file) | |
308 | char *dir, *file; | |
309 | { | |
310 | char *tail; | |
311 | char buf[BUFSIZ]; | |
312 | ||
313 | if (!strcmp(file, "-")) { | |
314 | fprintf(stderr, "diff: can't specify - with other arg directory\n"); | |
315 | done(); | |
316 | } | |
317 | tail = rindex(file, '/'); | |
318 | if (tail == 0) | |
319 | tail = file; | |
320 | else | |
321 | tail++; | |
6521d648 | 322 | (void)sprintf(buf, "%s/%s", dir, tail); |
43454f97 BJ |
323 | return (savestr(buf)); |
324 | } | |
325 | ||
87f863b7 KM |
326 | prepare(i, fd) |
327 | int i; | |
328 | FILE *fd; | |
43454f97 BJ |
329 | { |
330 | register struct line *p; | |
331 | register j,h; | |
87f863b7 | 332 | |
87f863b7 | 333 | fseek(fd, (long)0, 0); |
43454f97 | 334 | p = (struct line *)talloc(3*sizeof(line)); |
87f863b7 | 335 | for(j=0; h=readhash(fd);) { |
43454f97 BJ |
336 | p = (struct line *)ralloc((char *)p,(++j+3)*sizeof(line)); |
337 | p[j].value = h; | |
338 | } | |
339 | len[i] = j; | |
340 | file[i] = p; | |
43454f97 BJ |
341 | } |
342 | ||
343 | prune() | |
344 | { | |
345 | register i,j; | |
346 | for(pref=0;pref<len[0]&&pref<len[1]&& | |
347 | file[0][pref+1].value==file[1][pref+1].value; | |
348 | pref++ ) ; | |
349 | for(suff=0;suff<len[0]-pref&&suff<len[1]-pref&& | |
350 | file[0][len[0]-suff].value==file[1][len[1]-suff].value; | |
351 | suff++) ; | |
352 | for(j=0;j<2;j++) { | |
353 | sfile[j] = file[j]+pref; | |
354 | slen[j] = len[j]-pref-suff; | |
355 | for(i=0;i<=slen[j];i++) | |
356 | sfile[j][i].serial = i; | |
357 | } | |
358 | } | |
359 | ||
360 | equiv(a,n,b,m,c) | |
361 | struct line *a, *b; | |
362 | int *c; | |
363 | { | |
364 | register int i, j; | |
365 | i = j = 1; | |
366 | while(i<=n && j<=m) { | |
367 | if(a[i].value <b[j].value) | |
368 | a[i++].value = 0; | |
369 | else if(a[i].value == b[j].value) | |
370 | a[i++].value = j; | |
371 | else | |
372 | j++; | |
373 | } | |
374 | while(i <= n) | |
375 | a[i++].value = 0; | |
376 | b[m+1].value = 0; | |
377 | j = 0; | |
378 | while(++j <= m) { | |
379 | c[j] = -b[j].serial; | |
380 | while(b[j+1].value == b[j].value) { | |
381 | j++; | |
382 | c[j] = b[j].serial; | |
383 | } | |
384 | } | |
385 | c[j] = -1; | |
386 | } | |
387 | ||
388 | stone(a,n,b,c) | |
389 | int *a; | |
390 | int *b; | |
745638c1 | 391 | register int *c; |
43454f97 BJ |
392 | { |
393 | register int i, k,y; | |
394 | int j, l; | |
395 | int oldc, tc; | |
396 | int oldl; | |
397 | k = 0; | |
398 | c[0] = newcand(0,0,0); | |
399 | for(i=1; i<=n; i++) { | |
400 | j = a[i]; | |
401 | if(j==0) | |
402 | continue; | |
403 | y = -b[j]; | |
404 | oldl = 0; | |
405 | oldc = c[0]; | |
406 | do { | |
407 | if(y <= clist[oldc].y) | |
408 | continue; | |
409 | l = search(c, k, y); | |
410 | if(l!=oldl+1) | |
411 | oldc = c[l-1]; | |
412 | if(l<=k) { | |
413 | if(clist[c[l]].y <= y) | |
414 | continue; | |
415 | tc = c[l]; | |
416 | c[l] = newcand(i,y,oldc); | |
417 | oldc = tc; | |
418 | oldl = l; | |
419 | } else { | |
420 | c[l] = newcand(i,y,oldc); | |
421 | k++; | |
422 | break; | |
423 | } | |
424 | } while((y=b[++j]) > 0); | |
425 | } | |
426 | return(k); | |
427 | } | |
428 | ||
429 | newcand(x,y,pred) | |
430 | { | |
431 | register struct cand *q; | |
432 | clist = (struct cand *)ralloc((char *)clist,++clen*sizeof(cand)); | |
433 | q = clist + clen -1; | |
434 | q->x = x; | |
435 | q->y = y; | |
436 | q->pred = pred; | |
437 | return(clen-1); | |
438 | } | |
439 | ||
440 | search(c, k, y) | |
441 | int *c; | |
442 | { | |
443 | register int i, j, l; | |
444 | int t; | |
445 | if(clist[c[k]].y<y) /*quick look for typical case*/ | |
446 | return(k+1); | |
447 | i = 0; | |
448 | j = k+1; | |
745638c1 RC |
449 | while (1) { |
450 | l = i + j; | |
451 | if ((l >>= 1) <= i) | |
452 | break; | |
43454f97 BJ |
453 | t = clist[c[l]].y; |
454 | if(t > y) | |
455 | j = l; | |
456 | else if(t < y) | |
457 | i = l; | |
458 | else | |
459 | return(l); | |
460 | } | |
461 | return(l+1); | |
462 | } | |
463 | ||
464 | unravel(p) | |
465 | { | |
466 | register int i; | |
467 | register struct cand *q; | |
468 | for(i=0; i<=len[0]; i++) | |
469 | J[i] = i<=pref ? i: | |
470 | i>len[0]-suff ? i+len[1]-len[0]: | |
471 | 0; | |
472 | for(q=clist+p;q->y!=0;q=clist+q->pred) | |
473 | J[q->x+pref] = q->y+pref; | |
474 | } | |
475 | ||
476 | /* check does double duty: | |
477 | 1. ferret out any fortuitous correspondences due | |
478 | to confounding by hashing (which result in "jackpot") | |
479 | 2. collect random access indexes to the two files */ | |
480 | ||
481 | check() | |
482 | { | |
483 | register int i, j; | |
484 | int jackpot; | |
485 | long ctold, ctnew; | |
5427f51a | 486 | register int c,d; |
46235152 KM |
487 | |
488 | if ((input[0] = fopen(file1,"r")) == NULL) { | |
489 | perror(file1); | |
490 | done(); | |
491 | } | |
492 | if ((input[1] = fopen(file2,"r")) == NULL) { | |
493 | perror(file2); | |
494 | done(); | |
495 | } | |
43454f97 BJ |
496 | j = 1; |
497 | ixold[0] = ixnew[0] = 0; | |
498 | jackpot = 0; | |
499 | ctold = ctnew = 0; | |
500 | for(i=1;i<=len[0];i++) { | |
501 | if(J[i]==0) { | |
502 | ixold[i] = ctold += skipline(0); | |
503 | continue; | |
504 | } | |
505 | while(j<J[i]) { | |
506 | ixnew[j] = ctnew += skipline(1); | |
507 | j++; | |
508 | } | |
c470b1f1 VJ |
509 | if(bflag || wflag || iflag) { |
510 | for(;;) { | |
511 | c = getc(input[0]); | |
512 | d = getc(input[1]); | |
513 | ctold++; | |
514 | ctnew++; | |
515 | if(bflag && isspace(c) && isspace(d)) { | |
516 | do { | |
517 | if(c=='\n') | |
518 | break; | |
519 | ctold++; | |
520 | } while(isspace(c=getc(input[0]))); | |
521 | do { | |
522 | if(d=='\n') | |
523 | break; | |
524 | ctnew++; | |
525 | } while(isspace(d=getc(input[1]))); | |
526 | } else if ( wflag ) { | |
527 | while( isspace(c) && c!='\n' ) { | |
528 | c=getc(input[0]); | |
529 | ctold++; | |
530 | } | |
531 | while( isspace(d) && d!='\n' ) { | |
532 | d=getc(input[1]); | |
533 | ctnew++; | |
534 | } | |
535 | } | |
536 | if(chrtran[c] != chrtran[d]) { | |
537 | jackpot++; | |
538 | J[i] = 0; | |
539 | if(c!='\n') | |
540 | ctold += skipline(0); | |
541 | if(d!='\n') | |
542 | ctnew += skipline(1); | |
543 | break; | |
544 | } | |
545 | if(c=='\n') | |
546 | break; | |
43454f97 | 547 | } |
c470b1f1 VJ |
548 | } else { |
549 | for(;;) { | |
550 | ctold++; | |
551 | ctnew++; | |
552 | if((c=getc(input[0])) != (d=getc(input[1]))) { | |
553 | /* jackpot++; */ | |
554 | J[i] = 0; | |
555 | if(c!='\n') | |
556 | ctold += skipline(0); | |
557 | if(d!='\n') | |
558 | ctnew += skipline(1); | |
559 | break; | |
560 | } | |
561 | if(c=='\n') | |
562 | break; | |
43454f97 | 563 | } |
43454f97 BJ |
564 | } |
565 | ixold[i] = ctold; | |
566 | ixnew[j] = ctnew; | |
567 | j++; | |
568 | } | |
569 | for(;j<=len[1];j++) { | |
570 | ixnew[j] = ctnew += skipline(1); | |
571 | } | |
572 | fclose(input[0]); | |
573 | fclose(input[1]); | |
574 | /* | |
575 | if(jackpot) | |
576 | fprintf(stderr, "jackpot\n"); | |
577 | */ | |
578 | } | |
579 | ||
580 | sort(a,n) /*shellsort CACM #201*/ | |
581 | struct line *a; | |
582 | { | |
583 | struct line w; | |
584 | register int j,m; | |
585 | struct line *ai; | |
586 | register struct line *aim; | |
587 | int k; | |
b31389ce JL |
588 | |
589 | if (n == 0) | |
590 | return; | |
43454f97 BJ |
591 | for(j=1;j<=n;j*= 2) |
592 | m = 2*j - 1; | |
593 | for(m/=2;m!=0;m/=2) { | |
594 | k = n-m; | |
595 | for(j=1;j<=k;j++) { | |
596 | for(ai = &a[j]; ai > a; ai -= m) { | |
597 | aim = &ai[m]; | |
598 | if(aim < ai) | |
599 | break; /*wraparound*/ | |
600 | if(aim->value > ai[0].value || | |
601 | aim->value == ai[0].value && | |
602 | aim->serial > ai[0].serial) | |
603 | break; | |
604 | w.value = ai[0].value; | |
605 | ai[0].value = aim->value; | |
606 | aim->value = w.value; | |
607 | w.serial = ai[0].serial; | |
608 | ai[0].serial = aim->serial; | |
609 | aim->serial = w.serial; | |
610 | } | |
611 | } | |
612 | } | |
613 | } | |
614 | ||
615 | unsort(f, l, b) | |
616 | struct line *f; | |
617 | int *b; | |
618 | { | |
619 | register int *a; | |
620 | register int i; | |
621 | a = (int *)talloc((l+1)*sizeof(int)); | |
622 | for(i=1;i<=l;i++) | |
623 | a[f[i].serial] = f[i].value; | |
624 | for(i=1;i<=l;i++) | |
625 | b[i] = a[i]; | |
626 | free((char *)a); | |
627 | } | |
628 | ||
629 | skipline(f) | |
630 | { | |
5427f51a | 631 | register i, c; |
46235152 KM |
632 | |
633 | for(i=1;(c=getc(input[f]))!='\n';i++) | |
634 | if (c < 0) | |
635 | return(i); | |
43454f97 BJ |
636 | return(i); |
637 | } | |
638 | ||
639 | output() | |
640 | { | |
641 | int m; | |
642 | register int i0, i1, j1; | |
643 | int j0; | |
644 | input[0] = fopen(file1,"r"); | |
645 | input[1] = fopen(file2,"r"); | |
646 | m = len[0]; | |
647 | J[0] = 0; | |
648 | J[m+1] = len[1]+1; | |
649 | if(opt!=D_EDIT) for(i0=1;i0<=m;i0=i1+1) { | |
650 | while(i0<=m&&J[i0]==J[i0-1]+1) i0++; | |
651 | j0 = J[i0-1]+1; | |
652 | i1 = i0-1; | |
653 | while(i1<m&&J[i1+1]==0) i1++; | |
654 | j1 = J[i1+1]-1; | |
655 | J[i1] = j1; | |
656 | change(i0,i1,j0,j1); | |
657 | } else for(i0=m;i0>=1;i0=i1-1) { | |
658 | while(i0>=1&&J[i0]==J[i0+1]-1&&J[i0]!=0) i0--; | |
659 | j0 = J[i0+1]-1; | |
660 | i1 = i0+1; | |
661 | while(i1>1&&J[i1-1]==0) i1--; | |
662 | j1 = J[i1-1]+1; | |
663 | J[i1] = j1; | |
664 | change(i1,i0,j1,j0); | |
665 | } | |
666 | if(m==0) | |
667 | change(1,0,1,len[1]); | |
668 | if (opt==D_IFDEF) { | |
669 | for (;;) { | |
670 | #define c i0 | |
671 | c = getc(input[0]); | |
672 | if (c < 0) | |
673 | return; | |
674 | putchar(c); | |
675 | } | |
676 | #undef c | |
677 | } | |
8f68440f | 678 | if (anychange && opt == D_CONTEXT) |
c470b1f1 | 679 | dump_context_vec(); |
43454f97 BJ |
680 | } |
681 | ||
c470b1f1 VJ |
682 | /* |
683 | * The following struct is used to record change information when | |
684 | * doing a "context" diff. (see routine "change" to understand the | |
685 | * highly mneumonic field names) | |
686 | */ | |
687 | struct context_vec { | |
688 | int a; /* start line in old file */ | |
689 | int b; /* end line in old file */ | |
690 | int c; /* start line in new file */ | |
691 | int d; /* end line in new file */ | |
692 | }; | |
693 | ||
694 | struct context_vec *context_vec_start, | |
695 | *context_vec_end, | |
696 | *context_vec_ptr; | |
697 | ||
698 | #define MAX_CONTEXT 128 | |
699 | ||
43454f97 BJ |
700 | /* indicate that there is a difference between lines a and b of the from file |
701 | to get to lines c to d of the to file. | |
702 | If a is greater then b then there are no lines in the from file involved | |
703 | and this means that there were lines appended (beginning at b). | |
704 | If c is greater than d then there are lines missing from the to file. | |
705 | */ | |
706 | change(a,b,c,d) | |
707 | { | |
43454f97 BJ |
708 | int lowa,upb,lowc,upd; |
709 | struct stat stbuf; | |
710 | ||
711 | if (opt != D_IFDEF && a>b && c>d) | |
712 | return; | |
713 | if (anychange == 0) { | |
714 | anychange = 1; | |
715 | if(opt == D_CONTEXT) { | |
716 | printf("*** %s ", file1); | |
717 | stat(file1, &stbuf); | |
718 | printf("%s--- %s ", | |
719 | ctime(&stbuf.st_mtime), file2); | |
720 | stat(file2, &stbuf); | |
721 | printf("%s", ctime(&stbuf.st_mtime)); | |
c470b1f1 VJ |
722 | |
723 | context_vec_start = (struct context_vec *) | |
724 | malloc(MAX_CONTEXT * | |
725 | sizeof(struct context_vec)); | |
726 | context_vec_end = context_vec_start + MAX_CONTEXT; | |
727 | context_vec_ptr = context_vec_start - 1; | |
43454f97 BJ |
728 | } |
729 | } | |
43454f97 | 730 | if(opt == D_CONTEXT) { |
c470b1f1 VJ |
731 | /* |
732 | * if this new change is within 'context' lines of | |
733 | * the previous change, just add it to the change | |
734 | * record. If the record is full or if this | |
735 | * change is more than 'context' lines from the previous | |
736 | * change, dump the record, reset it & add the new change. | |
737 | */ | |
738 | if ( context_vec_ptr >= context_vec_end || | |
739 | ( context_vec_ptr >= context_vec_start && | |
740 | a > (context_vec_ptr->b + 2*context) && | |
741 | c > (context_vec_ptr->d + 2*context) ) ) | |
742 | dump_context_vec(); | |
743 | ||
744 | context_vec_ptr++; | |
745 | context_vec_ptr->a = a; | |
746 | context_vec_ptr->b = b; | |
747 | context_vec_ptr->c = c; | |
748 | context_vec_ptr->d = d; | |
43454f97 BJ |
749 | return; |
750 | } | |
751 | switch (opt) { | |
752 | ||
753 | case D_NORMAL: | |
754 | case D_EDIT: | |
755 | range(a,b,","); | |
756 | putchar(a>b?'a':c>d?'d':'c'); | |
757 | if(opt==D_NORMAL) | |
758 | range(c,d,","); | |
759 | putchar('\n'); | |
760 | break; | |
761 | case D_REVERSE: | |
762 | putchar(a>b?'a':c>d?'d':'c'); | |
763 | range(a,b," "); | |
764 | putchar('\n'); | |
765 | break; | |
a3e88724 VJ |
766 | case D_NREVERSE: |
767 | if (a>b) | |
768 | printf("a%d %d\n",b,d-c+1); | |
769 | else { | |
770 | printf("d%d %d\n",a,b-a+1); | |
771 | if (!(c>d)) | |
772 | /* add changed lines */ | |
773 | printf("a%d %d\n",b, d-c+1); | |
774 | } | |
775 | break; | |
43454f97 BJ |
776 | } |
777 | if(opt == D_NORMAL || opt == D_IFDEF) { | |
778 | fetch(ixold,a,b,input[0],"< ", 1); | |
779 | if(a<=b&&c<=d && opt == D_NORMAL) | |
780 | prints("---\n"); | |
781 | } | |
782 | fetch(ixnew,c,d,input[1],opt==D_NORMAL?"> ":"", 0); | |
783 | if ((opt ==D_EDIT || opt == D_REVERSE) && c<=d) | |
784 | prints(".\n"); | |
785 | if (inifdef) { | |
536f2b0d | 786 | fprintf(stdout, "#endif /* %s */\n", endifname); |
43454f97 BJ |
787 | inifdef = 0; |
788 | } | |
789 | } | |
790 | ||
791 | range(a,b,separator) | |
792 | char *separator; | |
793 | { | |
794 | printf("%d", a>b?b:a); | |
795 | if(a<b) { | |
796 | printf("%s%d", separator, b); | |
797 | } | |
798 | } | |
799 | ||
800 | fetch(f,a,b,lb,s,oldfile) | |
801 | long *f; | |
802 | FILE *lb; | |
803 | char *s; | |
804 | { | |
805 | register int i, j; | |
c470b1f1 VJ |
806 | register int c; |
807 | register int col; | |
43454f97 BJ |
808 | register int nc; |
809 | int oneflag = (*ifdef1!='\0') != (*ifdef2!='\0'); | |
810 | ||
811 | /* | |
812 | * When doing #ifdef's, copy down to current line | |
813 | * if this is the first file, so that stuff makes it to output. | |
814 | */ | |
815 | if (opt == D_IFDEF && oldfile){ | |
816 | long curpos = ftell(lb); | |
817 | /* print through if append (a>b), else to (nb: 0 vs 1 orig) */ | |
818 | nc = f[a>b? b : a-1 ] - curpos; | |
819 | for (i = 0; i < nc; i++) | |
820 | putchar(getc(lb)); | |
821 | } | |
822 | if (a > b) | |
823 | return; | |
824 | if (opt == D_IFDEF) { | |
825 | if (inifdef) | |
536f2b0d | 826 | fprintf(stdout, "#else /* %s%s */\n", oneflag && oldfile==1 ? "!" : "", ifdef2); |
43454f97 BJ |
827 | else { |
828 | if (oneflag) { | |
829 | /* There was only one ifdef given */ | |
830 | endifname = ifdef2; | |
831 | if (oldfile) | |
832 | fprintf(stdout, "#ifndef %s\n", endifname); | |
833 | else | |
834 | fprintf(stdout, "#ifdef %s\n", endifname); | |
835 | } | |
836 | else { | |
837 | endifname = oldfile ? ifdef1 : ifdef2; | |
838 | fprintf(stdout, "#ifdef %s\n", endifname); | |
839 | } | |
840 | } | |
841 | inifdef = 1+oldfile; | |
842 | } | |
c470b1f1 | 843 | |
43454f97 BJ |
844 | for(i=a;i<=b;i++) { |
845 | fseek(lb,f[i-1],0); | |
846 | nc = f[i]-f[i-1]; | |
847 | if (opt != D_IFDEF) | |
848 | prints(s); | |
c470b1f1 VJ |
849 | col = 0; |
850 | for(j=0;j<nc;j++) { | |
851 | c = getc(lb); | |
852 | if (c == '\t' && tflag) | |
853 | do | |
854 | putchar(' '); | |
855 | while (++col & 7); | |
856 | else { | |
857 | putchar(c); | |
858 | col++; | |
859 | } | |
860 | } | |
43454f97 | 861 | } |
c470b1f1 | 862 | |
43454f97 | 863 | if (inifdef && !wantelses) { |
536f2b0d | 864 | fprintf(stdout, "#endif /* %s */\n", endifname); |
43454f97 BJ |
865 | inifdef = 0; |
866 | } | |
867 | } | |
868 | ||
5427f51a | 869 | #define POW2 /* define only if HALFLONG is 2**n */ |
43454f97 BJ |
870 | #define HALFLONG 16 |
871 | #define low(x) (x&((1L<<HALFLONG)-1)) | |
872 | #define high(x) (x>>HALFLONG) | |
873 | ||
874 | /* | |
875 | * hashing has the effect of | |
876 | * arranging line in 7-bit bytes and then | |
877 | * summing 1-s complement in 16-bit hunks | |
878 | */ | |
879 | readhash(f) | |
745638c1 | 880 | register FILE *f; |
43454f97 | 881 | { |
c470b1f1 | 882 | register long sum; |
43454f97 | 883 | register unsigned shift; |
43454f97 | 884 | register t; |
c470b1f1 VJ |
885 | register space; |
886 | ||
43454f97 BJ |
887 | sum = 1; |
888 | space = 0; | |
c470b1f1 VJ |
889 | if(!bflag && !wflag) { |
890 | if(iflag) | |
891 | for(shift=0;(t=getc(f))!='\n';shift+=7) { | |
892 | if(t==-1) | |
893 | return(0); | |
5427f51a JL |
894 | sum += (long)chrtran[t] << (shift |
895 | #ifdef POW2 | |
896 | &= HALFLONG - 1); | |
897 | #else | |
898 | %= HALFLONG); | |
899 | #endif | |
c470b1f1 VJ |
900 | } |
901 | else | |
902 | for(shift=0;(t=getc(f))!='\n';shift+=7) { | |
903 | if(t==-1) | |
904 | return(0); | |
5427f51a JL |
905 | sum += (long)t << (shift |
906 | #ifdef POW2 | |
907 | &= HALFLONG - 1); | |
908 | #else | |
909 | %= HALFLONG); | |
910 | #endif | |
c470b1f1 VJ |
911 | } |
912 | } else { | |
913 | for(shift=0;;) { | |
914 | switch(t=getc(f)) { | |
915 | case -1: | |
916 | return(0); | |
917 | case '\t': | |
918 | case ' ': | |
919 | space++; | |
920 | continue; | |
921 | default: | |
922 | if(space && !wflag) { | |
923 | shift += 7; | |
924 | space = 0; | |
925 | } | |
5427f51a JL |
926 | sum += (long)chrtran[t] << (shift |
927 | #ifdef POW2 | |
928 | &= HALFLONG - 1); | |
929 | #else | |
930 | %= HALFLONG); | |
931 | #endif | |
43454f97 | 932 | shift += 7; |
c470b1f1 VJ |
933 | continue; |
934 | case '\n': | |
935 | break; | |
43454f97 | 936 | } |
43454f97 BJ |
937 | break; |
938 | } | |
43454f97 BJ |
939 | } |
940 | sum = low(sum) + high(sum); | |
941 | return((short)low(sum) + (short)high(sum)); | |
942 | } | |
46235152 KM |
943 | |
944 | #include <a.out.h> | |
945 | ||
946 | asciifile(f) | |
947 | FILE *f; | |
948 | { | |
949 | char buf[BUFSIZ]; | |
950 | register int cnt; | |
951 | register char *cp; | |
952 | ||
953 | fseek(f, (long)0, 0); | |
6f7a12ee | 954 | cnt = fread(buf, 1, BUFSIZ, f); |
46235152 KM |
955 | if (cnt >= sizeof (struct exec)) { |
956 | struct exec hdr; | |
957 | hdr = *(struct exec *)buf; | |
958 | if (!N_BADMAG(hdr)) | |
959 | return (0); | |
960 | } | |
961 | cp = buf; | |
962 | while (--cnt >= 0) | |
963 | if (*cp++ & 0200) | |
964 | return (0); | |
965 | return (1); | |
966 | } | |
c470b1f1 VJ |
967 | |
968 | ||
969 | /* dump accumulated "context" diff changes */ | |
970 | dump_context_vec() | |
971 | { | |
972 | register int a, b, c, d; | |
973 | register char ch; | |
974 | register struct context_vec *cvp = context_vec_start; | |
975 | register int lowa, upb, lowc, upd; | |
bf94f6de | 976 | register int do_output; |
c470b1f1 VJ |
977 | |
978 | if ( cvp > context_vec_ptr ) | |
979 | return; | |
980 | ||
981 | lowa = max(1, cvp->a - context); | |
982 | upb = min(len[0], context_vec_ptr->b + context); | |
983 | lowc = max(1, cvp->c - context); | |
984 | upd = min(len[1], context_vec_ptr->d + context); | |
985 | ||
986 | printf("***************\n*** "); | |
987 | range(lowa,upb,","); | |
bf94f6de | 988 | printf(" ****\n"); |
c470b1f1 VJ |
989 | |
990 | /* | |
bf94f6de KM |
991 | * output changes to the "old" file. The first loop suppresses |
992 | * output if there were no changes to the "old" file (we'll see | |
993 | * the "old" lines as context in the "new" list). | |
c470b1f1 | 994 | */ |
bf94f6de KM |
995 | do_output = 0; |
996 | for ( ; cvp <= context_vec_ptr; cvp++) | |
c470b1f1 VJ |
997 | if (cvp->a <= cvp->b) { |
998 | cvp = context_vec_start; | |
bf94f6de | 999 | do_output++; |
c470b1f1 VJ |
1000 | break; |
1001 | } | |
bf94f6de KM |
1002 | |
1003 | if ( do_output ) { | |
1004 | while (cvp <= context_vec_ptr) { | |
1005 | a = cvp->a; b = cvp->b; c = cvp->c; d = cvp->d; | |
1006 | ||
1007 | if (a <= b && c <= d) | |
1008 | ch = 'c'; | |
1009 | else | |
1010 | ch = (a <= b) ? 'd' : 'a'; | |
1011 | ||
1012 | if (ch == 'a') | |
1013 | fetch(ixold,lowa,b,input[0]," "); | |
1014 | else { | |
1015 | fetch(ixold,lowa,a-1,input[0]," "); | |
1016 | fetch(ixold,a,b,input[0],ch == 'c' ? "! " : "- "); | |
1017 | } | |
1018 | lowa = b + 1; | |
1019 | cvp++; | |
c470b1f1 | 1020 | } |
bf94f6de | 1021 | fetch(ixold, b+1, upb, input[0], " "); |
c470b1f1 | 1022 | } |
c470b1f1 VJ |
1023 | |
1024 | /* output changes to the "new" file */ | |
bf94f6de KM |
1025 | printf("--- "); |
1026 | range(lowc,upd,","); | |
1027 | printf(" ----\n"); | |
c470b1f1 | 1028 | |
bf94f6de KM |
1029 | do_output = 0; |
1030 | for (cvp = context_vec_start; cvp <= context_vec_ptr; cvp++) | |
c470b1f1 VJ |
1031 | if (cvp->c <= cvp->d) { |
1032 | cvp = context_vec_start; | |
bf94f6de | 1033 | do_output++; |
c470b1f1 VJ |
1034 | break; |
1035 | } | |
bf94f6de KM |
1036 | |
1037 | if (do_output) { | |
1038 | while (cvp <= context_vec_ptr) { | |
1039 | a = cvp->a; b = cvp->b; c = cvp->c; d = cvp->d; | |
1040 | ||
1041 | if (a <= b && c <= d) | |
1042 | ch = 'c'; | |
1043 | else | |
1044 | ch = (a <= b) ? 'd' : 'a'; | |
1045 | ||
1046 | if (ch == 'd') | |
1047 | fetch(ixnew,lowc,d,input[1]," "); | |
1048 | else { | |
1049 | fetch(ixnew,lowc,c-1,input[1]," "); | |
1050 | fetch(ixnew,c,d,input[1],ch == 'c' ? "! " : "+ "); | |
1051 | } | |
1052 | lowc = d + 1; | |
1053 | cvp++; | |
c470b1f1 | 1054 | } |
bf94f6de | 1055 | fetch(ixnew, d+1, upd, input[1], " "); |
c470b1f1 | 1056 | } |
c470b1f1 VJ |
1057 | |
1058 | context_vec_ptr = context_vec_start - 1; | |
1059 | } |