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