4.3BSD - /usr/src/bin/diff/diffreg.c

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

Defined functions

Defined variables

Defined struct's

Defined macros