home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / MISC / PCUNIX.ZIP / DIF.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-01-31  |  15.0 KB  |  653 lines
  1. #define VERSION "dif.c 2.01 C86 2-17-84"
  2. /*
  3.  * Differential file comparision program
  4.  *
  5.  *    Chuck Forsberg
  6.  *    Omen Technology Inc
  7.  *    Rt 1 Box 120v Portland OR 97231
  8.  *    Compuserve: 70715,131
  9.  *
  10.  * 2.01 C86 Removed BDS C 'isms; compiles with C86 v 2.00
  11.  * 2.01 fixed +++ in printf 11-27-81
  12.  * 2.00 added unsqueeze option
  13.  * 1.10 added crc information for use by ssed 1.10 in verifying antecedent
  14.  * file is correct  11-4-81 CAF
  15.  */
  16.  
  17. /* system dependent stuff */
  18.  
  19. #include <stdio.h>
  20. #define TRUE 1
  21. #define FALSE 0
  22. #define ERROR (-1)
  23. #define CPMEOF 032
  24.  
  25. FILE *in0, *in1;
  26. char *patho;            /* null or name of output file */
  27.  
  28. /* E-O-F indicator */
  29. #define LAST_TOKE 32765        /* at least 1 less than max positive int */
  30. #define MAXLEN 255
  31. #define HUNKSIZE 8192        /* Size of each circular buffer */
  32. int linno[2];
  33. char *patha, *pathb;        /* names of each file */
  34.  
  35. /* data in the circular buffers is stored in linked form */
  36.  
  37. struct line {
  38.     unsigned hash;        /* hashed value of text special case EOF=0 */
  39.     char f;            /* 0 or 1 which file it came from */
  40.     int num;        /* number of line or LAST_TOKE if EOF */
  41.     struct line *next;    /* pointer to next line, or null if last in
  42.                    buffer, or to itself if EOF */
  43.     char text[0];        /* asciz line of text */
  44. } *bottom[2],            /* bottom of each file's buffer */
  45.  *top[2],            /* top of each buffer */
  46.  *thislna, *thislnb,        /* line just fetched from buf */
  47.  cdq[2];            /* reader from each file */
  48.  
  49. struct line *getnext();        /* forward declarations */
  50. int getc1();
  51. int getc2();
  52. int getcr();
  53.  
  54. char Different, Verbose, Edit, Display, Unsqueeze;
  55. unsigned crc;        /* accumulated crc of common lines */
  56. int fudge;
  57. char ineof[2];        /* EOF (cpmeof) seen on file input */
  58.  
  59. /* following really should be automatics, but then that would slow things */
  60. int (*getit[2])();    /* getchar function for each file */
  61. int (*getthis)();    /* getchar function for current file */
  62. char *p, *q, *qq, *qqq, count;
  63.  
  64. /* Definitions and externals for unsqueezer function */
  65. #define RECOGNIZE 0xFF76    /* unlikely pattern */
  66. /* External declarations for USQ feature */
  67. #define NUMVALS 257    /* 256 data values plus SPEOF*/
  68. /* Decoding tree */
  69. struct {
  70.     int children[2];    /* left, right */
  71. } dnode[NUMVALS - 1];
  72. int bpos;    /* last bit position read */
  73. int curin;    /* last byte value read */
  74. /* Variables associated with repetition decoding */
  75. int repct;    /*Number of times to return value*/
  76. int value;    /*current byte value or EOF */
  77. int inch;
  78.  
  79. /*
  80.  * htbl stores pointers to a buncha lines which are sorted when looking
  81.  * for a match
  82.  */
  83.  
  84. #define HASHCHUNK 16    /* # lines of each file to search for initial match */
  85. #define HSIZE 2048    /* total # of lines that the hash table can hold */
  86. struct line *missm[2];        /* last line fetched for htbl */
  87. struct line *htbl[HSIZE];
  88.  
  89. char bfx[2][HUNKSIZE];        /* circular buffers */
  90.  
  91. getc1()
  92. {
  93.     return getc(in0);
  94. }
  95. getc2()
  96. {
  97.     return getc(in1);
  98. }
  99.  
  100. main(argc, argv)
  101. char **argv;
  102. {
  103.     char i, *cp, **av;
  104.     int ac;
  105.  
  106.     /* get output pathname if one was given */
  107.     patho=NULL;
  108.  
  109.     Different=Edit=Unsqueeze=Display=Verbose=FALSE;
  110.     getit[0]=getc1; getit[1]=getc2;
  111.     while (--argc && *(cp = *++argv)=='-') {
  112.  
  113.         while( *++cp) {
  114.             switch(tolower(*cp)) {
  115.             case 'd':
  116.                 Display++; break;
  117.             case 'e':
  118.                 Edit++; break;
  119.             case 'u':
  120.                 getit[0]=getcr;
  121.                 Unsqueeze++; break;
  122.             case 'v':
  123.                 Verbose++; break;
  124.             default:    
  125.                 goto usage;
  126.             }
  127.         }
  128.     }
  129.  
  130.     if(argc < 1 || argc > 2) {
  131. usage:
  132.         fprintf(stderr,VERSION);
  133.         fprintf(stderr,
  134.           "Usage: dif [-dev] filea {fileb,<fileb} [>outfile]\n");
  135.         fprintf(stderr,"\t-d display lines that match\n");
  136.         fprintf(stderr,"\t-e generate Editor script\n");
  137.         fprintf(stderr,"\t-u Unsqueeze filea\n");
  138.         fprintf(stderr,"\t-v Verbose\n");
  139.         exit(1);
  140.     }
  141.  
  142.     if((in0=fopen( patha=argv[0], "rb")) == NULL)
  143.     {
  144.         fprintf(stderr, "Can't open %s", argv[0]);
  145.         exit(1);
  146.     }
  147.     if(argc==2) {
  148.         if((in1=fopen( patha=argv[1], "rb")) == NULL)
  149.         {
  150.             fprintf(stderr, "Can't open %s", argv[1]);
  151.             exit(128);
  152.         }
  153.     }
  154.     else {
  155.         in1 = stdin;
  156.         pathb= "Standard Input";
  157.     }
  158.  
  159.     if(Unsqueeze) {
  160.         getit[0]=getcr;        /* switch getchar function */
  161.         init_usq();        /* initialize unpacking */
  162.     }
  163.  
  164.     crc=linno[0]=linno[1]=0;
  165.     ineof[0]=ineof[1]=FALSE;
  166.  
  167.     cdq[0].next=p=bottom[0] = bfx[0];
  168.     cdq[1].next=bottom[1]=top[0]= bfx[1];
  169.     top[1]= bfx[2];        /* not in pascal! */
  170.  
  171.     if(Verbose)
  172.         for(i=0; i<2; ++i )
  173.             fprintf(stderr,"bottom[%d]=%x top=%x\n",
  174.               i, bottom[i], top[i]);
  175.  
  176.     fudge=0;    /* initialize magic editing offset */
  177.  
  178.     /* initialize thisln so it won't get in the way of filling buffer */
  179.     thislna=thislnb=0;
  180.     /* get the first line from each and start chain */
  181.  
  182.     getline(0, &cdq[0]);
  183.     thislna=bottom[0];
  184.     getline(1, &cdq[1]);
  185.     thislnb=bottom[1];
  186.  
  187.     while( thislna->num != LAST_TOKE | thislnb->num != LAST_TOKE) {
  188.         if(strcmp(thislna->text, thislnb->text))
  189.             dodiff();
  190.         else {
  191.             crc += thislna->hash;
  192.             if(Display)
  193.                 printf("   %s", thislna->text);
  194.         thislna=getnext(thislna);
  195.         thislnb=getnext(thislnb);
  196.         }
  197.     }
  198.     if(Edit)
  199.         printf("$a %u\n.\n", crc);
  200.     if(Different)
  201.         fprintf(stderr,"Files are different\n");
  202.     else {
  203.         fprintf(stderr,"No differences encountered\n");
  204.         if(patho) {
  205.             unlink(patho);
  206.             fprintf(stderr,"'%s' Unlinked\n", patho);
  207.         }
  208.     }
  209. }
  210.  
  211.  
  212. /*
  213. getnext returns next line unless:
  214.     eof: return current (its chained to itself);
  215.     no room in buffer: return NULL;
  216. */
  217.  
  218. struct line *getnext(fp)
  219.     register struct line *fp;
  220. {
  221.  
  222.     if(fp->next)
  223.         return fp->next;    /* link to next line */
  224.  
  225.     getline(fp->f, fp);            /* end of buffer -get more */
  226.     return fp->next;
  227. }
  228.  
  229. getline(n, fp)
  230. struct line *fp;
  231. char n;
  232. {
  233.     struct line *gp;
  234.     int *number, len;
  235.     unsigned crck();
  236.  
  237.     number= &linno[n];
  238.     getthis=getit[n];
  239.  
  240.     q=top[n];
  241.     q -= (MAXLEN + 4 + sizeof(*fp));
  242.     qq=n?thislnb:thislna;
  243.     qqq = qq - (MAXLEN + 4 + sizeof(*fp));
  244.     p=fp->next;
  245.     if(p==NULL) {
  246.         p=fp;
  247.         p += sizeof(*fp)+1+strlen(fp->text);
  248. #ifdef UNIX
  249.         p += p % sizeof(int);
  250. #endif
  251.     }
  252.     if(Verbose)
  253.         fprintf(stderr,"File %d line %d q=%x qq=%x qqq=%x p=%x\n",
  254.           n, *number, q, qq, qqq, p );
  255.     if(ineof[n]) {
  256.         fprintf(stderr, "Getline called after E-O-F\n");
  257.         fprintf(stderr,
  258.           "%d %3d fp=%x hash=%04x next=%x p=%x ",
  259.           n, *number, fp, fp->hash, fp->next, p);
  260.         fputs(fp->text, stderr);
  261.         return;
  262.     }
  263.     for(;;) {
  264.         /* check if we need to wrap at end of buffer */
  265.         if(p > q) {
  266.             p=bottom[n];
  267.             if(Verbose)
  268.                 fprintf(stderr,"Wrapped: p=%x\n", p);
  269.             if(qq==0)
  270.                 goto yumyum;    /* special case first time */
  271.         }
  272.  
  273.         /* is the buffer filled up ? */
  274.         if(p <= qq && p >= qqq) {        /* before thislin ? */
  275. yumyum:
  276.             if(Verbose)
  277.                 fprintf(stderr,"Buffer Filled\n");
  278.             return;
  279.         }
  280. #ifdef UNIX
  281.         p += p % sizeof(int);
  282. #endif
  283.         gp=p;
  284.         gp->f=n;
  285.         for(p=gp->text, count=MAXLEN; --count; )
  286.             switch(*p++ = (*getthis)() ) {
  287.               case CPMEOF:
  288.               case 0377:
  289.                   if(Verbose)
  290.                     fprintf(stderr,
  291.                       "EOF on file %d at line %d\n",
  292.                       n, *number);
  293.                 ineof[n]=TRUE;
  294.                 gp->hash = ~0;
  295.                 gp->next = gp;        /* link to self */
  296.                 gp->num = LAST_TOKE;
  297.                 strcpy(gp->text, "**EOF**\n");
  298.                 fp->next=gp;
  299.                 return;
  300.             case 012:
  301.                 ++*number;
  302.                 goto gotline;
  303.             case 015:
  304.                 --p;
  305.             }
  306.         fprintf(stderr,"Line %d is too long\n", *number);
  307. gotline:
  308.         *p=0;
  309.         if(len=p - gp->text)
  310.             gp->hash=crck(gp->text, len, 0);
  311.         else
  312.             gp->hash = 0;
  313.         gp->num = *number;
  314.         fp->next=gp;
  315.         if(Verbose>3) {
  316.             fprintf(stderr,
  317.               "%d %3d gp=%x hash=%04x len=%3d p=%x ",
  318.               n, *number, gp, gp->hash, len, p);
  319.             fputs(gp->text, stderr);
  320.         }
  321.         fp=gp;        /* advance along new chain */
  322.         fp->next=NULL;
  323.         ++p;        /* bump pointer past trailing null */
  324.     }
  325. }
  326.  
  327. /*
  328.  * Sort htbl first by hashvalue, then by file number
  329.  */
  330.  
  331. comp(a,b)
  332. struct line **a, **b;
  333. {
  334.     if( (*a)->hash > (*b)->hash)
  335.         return 1;
  336.     if( (*a)->hash < (*b)->hash)
  337.         return -1;
  338.     return (*a)->f - (*b)->f;
  339. }
  340.  
  341.  
  342. dodiff()
  343. {
  344.     register struct line **lp;
  345.     int quantity, m, l;
  346.     char keepatit, n, wanta, wantb;
  347.  
  348.     Different=TRUE;
  349.     if(Verbose)
  350.         fprintf(stderr,"Difference at %d:%d\n",
  351.           thislna->num, thislnb->num);
  352.     wanta=wantb=TRUE;
  353.     lp=htbl;
  354.     *lp++ =missm[0]=thislna;
  355.     *lp++ =missm[1]=thislnb;
  356.  
  357.     /*
  358.      * To minimize time in locating the matching lines after small
  359.      * sections of text, start out by looking at just a few lines.
  360.      * If that doesn't work, enlarge the search.
  361.      */
  362.     for(quantity=2,l=HASHCHUNK, keepatit=TRUE;
  363.       keepatit && (wanta||wantb); l+=l) {
  364.  
  365.         if(wanta)
  366.             for(m=l; --m>=0; ) {
  367.                 if((*lp = getnext(missm[0]))==NULL) {
  368.                     wanta=FALSE; break;
  369.                 }
  370.                 missm[0]= *lp++;
  371.                 /* quit n-o-w if table filled */
  372.                 if(++quantity==HSIZE) {
  373.                     keepatit=FALSE; goto nowlook;
  374.                 }
  375.                 /* Don't fill up the table with eof's */
  376.                 if(missm[0]->num==LAST_TOKE) {
  377.                     wanta=FALSE; break;
  378.                 }
  379.             }
  380.         if(wantb)
  381.             for(m=l; --m>=0; ) {
  382.                 if((*lp = getnext(missm[1]))==NULL) {
  383.                     wantb=FALSE; break;
  384.                 }
  385.                 missm[1]= *lp++;
  386.                 if(++quantity==HSIZE) {
  387.                     keepatit=FALSE; goto nowlook;
  388.                 }
  389.                 if(missm[1]->num==LAST_TOKE) {
  390.                     wantb=FALSE; break;
  391.                 }
  392.             }
  393. nowlook:
  394.         if(Verbose)
  395.             fprintf(stderr,
  396.               "Dodiff Quantity=%d k't=%d w'a=%d w'b=%d\n",
  397.               quantity, keepatit, wanta, wantb);
  398.         if(Verbose>2)
  399.             for(m=0; m<quantity; ++m)
  400.                 fprintf(stderr,
  401.                   "HTBL %3d:addr=%x f=%d  h=%4x l=%3d nxt=%x\n",
  402.                   m, htbl[m], htbl[m]->f, htbl[m]->hash,
  403.                   htbl[m]->num, htbl[m]->next);
  404.         qsort(htbl, quantity, sizeof(p), comp);
  405.         if(lookferit(quantity)) {
  406.             return;
  407.         }
  408.     }
  409.     fprintf(stderr,"Can't find match at a:line %d b:line %d\n",
  410.       thislna->num, thislnb->num);
  411.     if(Verbose)
  412.         for(m=0; m<quantity; ++m)
  413.             fprintf(stderr,
  414.               "HTBL %d:addr=%x f=%d  h=%4x l=%3d %.30s\n",
  415.               m, htbl[m], htbl[m]->f, htbl[m]->hash,
  416.               htbl[m]->num, htbl[m]->text);
  417.     exit(1);
  418. }
  419.  
  420. /* search for lowest matching lines using the hash index for quick look */
  421. lookferit(quantity)
  422. {
  423.     struct line *loa, *lob, **pa, **pb, **pe, *fp;
  424.     int m, lowa, lowb, skipa, skipb;
  425.  
  426.     lowa=lowb=LAST_TOKE+1;
  427.     pe= &htbl[quantity];
  428.  
  429.     for(pa=htbl; pa < pe; ++pa) {
  430.         if((*pa)->f)
  431.             continue;
  432.         for(pb=pa+1; pb < pe; ++pb) {
  433.             if((*pb)->f == 0)
  434.                 continue;
  435.             if((*pa)->hash != (*pb)->hash)
  436.                 continue;
  437.             if((*pa)->num > lowa || (*pb)->num > lowb)
  438.                 continue;
  439.             if((*pa)->next==NULL || (*pb)->next==NULL)
  440.                 continue;
  441.             if((*pa)->next->hash != (*pb)->next->hash)
  442.                 continue;
  443.             if(strcmp((*pa)->text, (*pb)->text))
  444.                 continue;
  445.             if(strcmp((*pa)->next->text, (*pb)->next->text))
  446.                 continue;
  447.             lowa=(*pa)->num; lowb=(*pb)->num;
  448.             loa= *pa; lob= *pb;
  449.         }
  450.     }
  451.     if(lowa > LAST_TOKE) {
  452.         return FALSE;
  453.     }
  454.  
  455.     if(Verbose){
  456.         fprintf(stderr, "Found match at %d:%d\n", lowa, lowb);
  457.         fputs(loa->text, stderr); fputs(lob->text, stderr);
  458.     }
  459.     if(Edit) {
  460.         skipa= lowa - thislna->num;
  461.         skipb= lowb - (fp=thislnb)->num;
  462.         if(Verbose)
  463.             fprintf(stderr,"Fudge=%d skipa=%d skipb=%d\n",
  464.               fudge, skipa, skipb);
  465.         if(skipa) {
  466.             printf("%d", fudge+thislna->num);
  467.             if(skipa != 1) {
  468.                 putchar(',');
  469.                 if(lowa==LAST_TOKE)
  470.                     putchar('$');
  471.                 else
  472.                     printf("%d",
  473.                       fudge + thislna->num + skipa - 1);
  474.             }
  475.             fudge -= skipa;
  476.         }
  477.         if(skipb) {
  478.             if(skipa==0 || thislna->num==LAST_TOKE)
  479.                 /* append if no lines to remove */
  480.                 printf("%da %u\n",
  481.                   thislnb->num -1, crc);
  482.             else
  483.                 /* change if old lines gotta go */
  484.                 printf("c %u\n", crc);
  485.             for(; fp->num < lowb; fp=getnext(fp))
  486.                 fputs(fp->text, stdout);
  487.             printf(".\n");
  488.             fudge += skipb;
  489.         } else
  490.             printf("d %u\n", crc);
  491.     } else {
  492.         printf("-------- Line %4d of '%s' ----\n",thislna->num, patha);
  493.         for(fp=thislna; fp->num < lowa; fp=getnext(fp))
  494.             printf("---%s", fp->text);
  495.         printf("++++++++ Line %4d of '%s' ++++\n",thislnb->num, pathb);
  496.         for(fp=thislnb; fp->num < lowb; fp=getnext(fp))
  497.             printf("+++%s", fp->text);
  498.     }
  499.     /* advance pointers to matched lines */
  500.     thislna= loa; thislnb= lob;
  501.     return TRUE;
  502. }
  503.  
  504.  
  505. /* *** Stuff for first translation module *** */
  506. #define DLE 0x90
  507. /* *** Stuff for second translation module *** */
  508. #define SPEOF 256    /* special endfile token */
  509. #define LARGE 30000
  510.  
  511. init_usq()
  512. {
  513.     int i, c;
  514.     char cc;
  515.  
  516.     char *p;
  517.     int numnodes;        /* size of decoding tree */
  518.     char origname[14];    /* Original file name without drive */
  519.  
  520.     /* Initialization */
  521.     init_cr();
  522.     init_huff();
  523.  
  524.     if(getw(in0)!=RECOGNIZE) {
  525.         fprintf(stderr,"%s Not Squeezed\n", patha);
  526.         exit(1);
  527.     }
  528.     /* Process rest of header */
  529.     getw(in0);    /* ignore checksum ... */
  530.  
  531.     /* Get original file name */
  532.     p = origname;    /* send it to array */
  533.     do {
  534.         *p = getc(in0);
  535.     } while(*p++ != '\0');
  536.  
  537.     fprintf(stderr, "(%s -> %s)\n", patha, origname);
  538.  
  539.     numnodes = getw(in0);
  540.     if(numnodes < 0 || numnodes >= NUMVALS) {
  541.         fprintf(stderr, "%s has invalid decode tree size\n", patha);
  542.         exit(1);
  543.     }
  544.  
  545.     /* Initialize for possible empty tree (SPEOF only) */
  546.     dnode[0].children[0] = -(SPEOF + 1);
  547.     dnode[0].children[1] = -(SPEOF + 1);
  548.  
  549.     /* Get decoding tree from file */
  550.     for(i = 0; i < numnodes; ++i) {
  551.         dnode[i].children[0] = getw(in0);
  552.         dnode[i].children[1] = getw(in0);
  553.     }
  554. }
  555.  
  556.  
  557. /* initialize decoding functions */
  558.  
  559. init_cr()
  560. {
  561.     repct = 0;
  562. }
  563.  
  564. init_huff()
  565. {
  566.     bpos = 99;    /* force initial read */
  567. }
  568.  
  569. /* Get bytes with decoding - this decodes repetition,
  570.  * calls getuhuff to decode file stream into byte
  571.  * level code with only repetition encoding.
  572.  *
  573.  * The code is simple passing through of bytes except
  574.  * that DLE is encoded as DLE-zero and other values
  575.  * repeated more than twice are encoded as value-DLE-count.
  576.  */
  577.  
  578. int
  579. getcr()
  580. {
  581.     int c;
  582.  
  583.     if(repct > 0) {
  584.         /* Expanding a repeated char */
  585.         --repct;
  586.         return value;
  587.     } else {
  588.         /* Nothing unusual */
  589.         if((c = getuhuff()) != DLE) {
  590.             /* It's not the special delimiter */
  591.             value = c;
  592.             if(value == EOF)
  593.                 repct = LARGE;
  594.             return value;
  595.         } else {
  596.             /* Special token */
  597.             if((repct = getuhuff()) == 0)
  598.                 /* DLE, zero represents DLE */
  599.                 return DLE;
  600.             else {
  601.                 /* Begin expanding repetition */
  602.                 repct -= 2;    /* 2nd time */
  603.                 return value;
  604.             }
  605.         }
  606.     }
  607. }
  608.  
  609. /* Decode file stream into a byte level code with only
  610.  * repetition encoding remaining.
  611.  */
  612.  
  613. int
  614. getuhuff()
  615. {
  616.  
  617.     /* Follow bit stream in tree to a leaf*/
  618.     inch = 0;    /* Start at root of tree */
  619.     do {
  620.         if(++bpos > 7) {
  621.             if((curin = getc(in0)) == ERROR)
  622.                 return ERROR;
  623.             bpos = 0;
  624.             /* move a level deeper in tree */
  625.             inch = dnode[inch].children[1 & curin];
  626.         } else
  627.             inch = dnode[inch].children[1 & (curin >>= 1)];
  628.     } while(inch >= 0);
  629.  
  630.     /* Decode fake node index to original data value */
  631.     inch = -(inch + 1);
  632.     /* Decode special endfile token to normal EOF */
  633.     return (inch == SPEOF) ? EOF : inch;
  634. }
  635.  
  636. /*
  637.  * uses algrithim of CRCK.COM previous to 5.0
  638.  */
  639. unsigned crck(crbuf, count, oldcrc)
  640. char *crbuf;
  641. unsigned oldcrc;
  642. {
  643.     unsigned n;
  644.     while (--count >= 0) {
  645.         n= (oldcrc << 1);
  646.         n = (n & 0xFF00) | (( n + *crbuf++ ) & 0xFF);
  647.         if(oldcrc & 0x8000)
  648.             n ^= 0xA097;
  649.         oldcrc = n;
  650.     }
  651.     return oldcrc;        
  652. }
  653.