2.11BSD#431 - /usr/src/bin/diff/diffreg.c

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

Defined functions

Defined variables

Defined struct's

Defined macros