![[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] / 43BSDTahoe / bin / diff|
Return to diffreg.c CVS log | Up to [CSRG BSD Unix] / 43BSDTahoe / bin / diff |
1.1 ! root 1: static char sccsid[] = "@(#)diffreg.c 4.17 10/22/87"; ! 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: (void)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.