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