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

##### Functions

    asciifile         X
    change            X
    check             X
    copytemp          X
    diffreg           X
    dump_context_vec  X
    equiv             X
    fetch             X
    newcand           X
    output            X
    prepare           X
    prune             X
    range             X
    readhash          X
    search            X
    skipline          X
    sort              X
    splice            X
    stone             X
    unravel           X
    unsort            X

##### Variables

    J                 X
    cand              X
    chrtran           X
    class             X
    clen              X
    clist             X
    clow2low          X
    context_vec_end   X
    context_vec_ptr   X
    context_vec_start X
    cup2low           X
    file              X
    ixnew             X
    ixold             X
    klist             X
    len               X
    line              X
    member            X
    pref              X
    sfile             X
    slen              X
    suff              X

##### Macros

    HALFLONG          X
    MAX_CONTEXT       X
    POW2              X
    c                 X
    high              X
    low               X
    prints            X

##### struct's

    cand              X
    context_vec       X
    line              X

       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

asciifile defined in line 939; used 2 times

- in line 223(2)

change defined in line 694; used 3 times

- in line 644, 652-655(2)

check defined in line 469; used 1 times

- in line 258

copytemp defined in line 267; used 3 times

- in line 176, 183
- in /usr/src/bin/diff/diff.h line 82

diffreg defined in line 143; used 1 times

- in /usr/src/bin/diff/diff.c line 147

dump_context_vec defined in line 963; used 2 times

- in line 667, 735

equiv defined in line 348; used 1 times

- in line 238

fetch defined in line 793; used 10 times

- in line 771-775(2), 1006-1014(4), 1040-1048(4)

newcand defined in line 417; used 3 times

- in line 386, 404-408(2)

output defined in line 627; used 1 times

- in line 259

prepare defined in line 314; used 2 times

- in line 229-230(2)

prune defined in line 331; used 1 times

- in line 233

range defined in line 784; used 5 times

- in line 748-756(3), 980, 1019

readhash defined in line 872; used 1 times

- in line 323

search defined in line 428; used 1 times

- in line 397

skipline defined in line 617; used 7 times

- in line 490-494(2), 528-530(2), 544-546(2), 558

sort defined in line 568; used 2 times

- in line 234-235(2)

splice defined in line 294; used 3 times

- in line 158, 165
- in /usr/src/bin/diff/diff.h line 81

stone defined in line 376; used 1 times

- in line 247

unravel defined in line 452; used 1 times

- in line 252

unsort defined in line 603; used 1 times

- in line 242

#### Defined variables

J defined in line 96; used 22 times

- in line 251, 457-461(2), 489-493(2), 526, 542, 635-651(15)

cand defined in line 82; used 2 times

- in line 246, 420

chrtran defined in line 99; used 5 times

- in line 156, 524(2), 887, 919

class defined in line 91; used 6 times

- in line 241-249(6)

clen defined in line 95; used 3 times

- in line 420-425(3)

clist defined in line 94; used 11 times

- in line 246, 253, 395, 401, 420-421(3), 433, 441, 460(2)

clow2low defined in line 105; used 1 times

- in line 156

context_vec_end defined in line 683; used 2 times

- in line 715, 731

context_vec_ptr defined in line 684; used 18 times

- in line 716, 731-741(9), 971-977(3), 989, 997, 1023, 1031, 1051

context_vec_start defined in line 682; used 9 times

- in line 712-716(3), 732, 967, 991, 1023-1025(2), 1051

cup2low defined in line 124; used 1 times

- in line 156

file defined in line 86; used 13 times

- in line 237-241(2), 295-307(5), 328, 335-341(5)

ixnew defined in line 98; used 10 times

- in line 257, 485, 494, 554-558(2), 775, 1040-1048(4)

ixold defined in line 97; used 9 times

- in line 256, 485-490(2), 553, 771, 1006-1014(4)

klist defined in line 93; used 4 times

- in line 245-254(4)

len defined in line 87; used 22 times

- in line 251-257(3), 327, 334-342(7), 456-458(4), 488, 557, 634-636(2), 655, 975-977(2)

line defined in line 86; used 2 times

- in line 322-324(2)

member defined in line 92; used 6 times

- in line 237-239(4), 247-248(2)

pref defined in line 90; used 13 times

- in line 334-342(10), 457-461(3)

sccsid defined in line 2; never used
sfile defined in line 88; used 7 times

- in line 234-242(5), 341-344(2)

slen defined in line 89; used 11 times

- in line 234-247(9), 342-343(2)

suff defined in line 90; used 8 times

- in line 337-342(7), 458

#### Defined struct's

cand defined in line 78; used 10 times

- in line 94(2), 246(2), 419-420(4), 455(2)

context_vec defined in line 675; used 8 times

- in line 682(2), 712-714(4), 967(2)

line defined in line 83; used 20 times

- in line 88(2), 318-324(6), 349(2), 569-574(8), 604(2)

#### Defined macros

HALFLONG defined in line 863; used 8 times

- in line 864-865(2), 889-891(2), 900-902(2), 921-923(2)

MAX_CONTEXT defined in line 686; used 2 times

- in line 713-715(2)

POW2 defined in line 862; used 3 times

- in line 888, 899, 920

c defined in line 658; used 71 times

- in line 348-350(2), 367-379(5), 386, 393-408(7), 428-433(3), 441, 474, 499-508(4), 515-516(3), 524-527(2), 533, 540-543(2), 549, 619-622(3), 659-664(4), 678, 694, 700, 719, 734, 740(2), 749-755(3), 761-766(3), 772-776(3), 799, 844-850(3), 965, 976, 998-1000(3), 1024, 1032-1034(3), 1042-1043(2)

high defined in line 865; used 2 times

- in line 933-934(2)

low defined in line 864; used 2 times

- in line 933-934(2)

prints defined in line 73; used 3 times

- in line 773-777(2), 841

Last modified: 1994-01-11 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 4065 |