home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume2 / pd-diff-v2 / diff.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-07  |  32.8 KB  |  1,565 lines
  1. /*
  2.  * diff.c - public domain context diff program
  3.  *
  4.  */
  5.  
  6. #ifdef TURBO
  7. #include <alloc.h>
  8. #include <errno.h>
  9. #include <process.h>
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13.  
  14. #else /* !TURBO */
  15. #include <stdio.h>
  16. #include <ctype.h>
  17. #endif /* TURBO */
  18.  
  19. #ifdef vms
  20. #include      <ssdef.h>
  21. #include      <stsdef.h>
  22. #define  IO_SUCCESS  (SS | STS)
  23. #define  IO_ERROR  SS
  24. #endif /* vms */
  25.  
  26. /*
  27.  * Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
  28.  */
  29.  
  30. #ifndef  IO_SUCCESS
  31. #define  IO_SUCCESS  0
  32. #endif /* IO_SUCCESS */
  33. #ifndef  IO_ERROR
  34. #define  IO_ERROR  1
  35. #endif /* IO_ERROR */
  36.  
  37. #define  EOS      0
  38. #ifdef unix
  39. char            temfile[L_tmpnam];
  40. char           *tmpnam();
  41. #define  TEMPFILE  (temfile[0]? temfile: (tmpnam(temfile), temfile))
  42. #else /* unix */
  43. #define  TEMPFILE  "diff.tmp"
  44. #endif /* unix */
  45. #define  TRUE      1
  46. #define  FALSE      0
  47.  
  48. #ifdef  pdp11
  49. #define  short  int
  50. #endif /* pdp11 */
  51.  
  52. typedef struct candidate {
  53.     int             b;            /* Line in fileB       */
  54.     int             a;            /* Line in fileA       */
  55.     int             link;        /* Previous candidate       */
  56. } CANDIDATE;
  57.  
  58. typedef struct line {
  59.     unsigned short  hash;        /* Hash value etc.       */
  60.     short           serial;        /* Line number        */
  61. } LINE;
  62.  
  63. LINE           *file[2];        /* Hash/line for total file  */
  64. #define  fileA  file[0]
  65. #define  fileB  file[1]
  66.  
  67. LINE           *sfile[2];        /* Hash/line after prefix  */
  68. #define  sfileA  sfile[0]
  69. #define  sfileB  sfile[1]
  70.  
  71. int             len[2];            /* Actual lines in each file  */
  72. #define  lenA  len[0]
  73. #define  lenB  len[1]
  74.  
  75. int             slen[2];        /* Squished lengths       */
  76. #define  slenA  slen[0]
  77. #define  slenB  slen[1]
  78.  
  79. int             prefix;            /* Identical lines at start  */
  80. int             suffix;            /* Identical lenes at end  */
  81.  
  82. FILE           *infd[2] = {NULL, NULL};    /* Input file identifiers  */
  83. FILE           *tempfd;            /* Temp for input redirection  */
  84.  
  85. extern long     ftell();
  86. extern FILE    *fopen();
  87.  
  88. #ifdef TURBO
  89. extern void    *malloc();
  90. #else /* !TURBO */
  91. extern char    *malloc();
  92. #endif /* TURBO */
  93.  
  94. char           *fgetss();
  95. unsigned short  hash();
  96.  
  97. #ifdef    AMIGA
  98. /* Define these types for Amiga C */
  99. char           *savptr;
  100. int             savsiz;
  101. char           *wrk;
  102. char           *wrk2;
  103. int             cpysiz;
  104. #endif /* AMIGA */
  105.  
  106. /*
  107.  * The following vectors overlay the area defined by fileA
  108.  */
  109.  
  110. short          *class;            /* Unsorted line numbers  */
  111. int            *klist;            /* Index of element in clist  */
  112. CANDIDATE      *clist;            /* Storage pool for candidates  */
  113. int             clength = 0;    /* Number of active candidates  */
  114. #define    CSIZE_INC 50            /* How many to allocate each time we have to */
  115. int             csize = CSIZE_INC;        /* Current size of storage pool */
  116.  
  117. int            *match;            /* Longest subsequence       */
  118. long           *oldseek;        /* Seek position in file A  */
  119.  
  120. /*
  121.  * The following vectors overlay the area defined by fileB
  122.  */
  123.  
  124. short          *member;            /* Concatenated equiv. classes  */
  125. long           *newseek;        /* Seek position in file B  */
  126. char           *textb;            /* Input from file2 for check  */
  127.  
  128. /*
  129.  * Global variables
  130.  */
  131.  
  132. int             eflag = FALSE;    /* Edit script requested  */
  133. int             bflag = FALSE;    /* Blank supress requested  */
  134. int             cflag = FALSE;    /* Context printout       */
  135. int             iflag = FALSE;    /* Ignore case requested  */
  136. char            text[257];        /* Input line from file1  */
  137. extern char    *myalloc();        /* Storage allocator       */
  138.  
  139. extern char    *compact();        /* Storage compactor       */
  140.  
  141. #ifdef  DEBUG
  142. #ifndef OSK
  143. #define  TIMING
  144. #endif /* OSK */
  145. #endif /* DEBUG */
  146. #ifdef  TIMING
  147. extern long     time();
  148. extern char    *4532mend;
  149. long            totaltime;
  150. long            sectiontime;
  151. char           *mstart;
  152. #endif /* TIMING */
  153. void            free();
  154. void            exit();
  155. #ifndef OSK
  156. void            perror();
  157. #endif /* OSK */
  158.  
  159. /*
  160.  * Diff main program
  161.  */
  162.  
  163. main(argc, argv)
  164.     int             argc;
  165.     char          **argv;
  166. {
  167.     register int    i;
  168.     register char  *ap;
  169.  
  170. #ifdef OSK
  171.     extern int      _memmins;
  172.     _memmins = 16 * 1024;        /* tell OSK we will malloc a lot */
  173. #endif /* OSK */
  174. #ifdef  TIMING
  175.     sectiontime = time(&totaltime);
  176. #endif /* TIMING */
  177. #ifdef vms
  178.     argc = getredirection(argc, argv);
  179. #endif /* vms */
  180.     while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
  181.         while (*ap != EOS) {
  182.             switch ((*ap++)) {
  183.             case 'b':
  184.                 bflag++;
  185.                 break;
  186.  
  187.             case 'c':
  188.                 if (*ap > '0' && *ap <= '9')
  189.                     cflag = *ap++ - '0';
  190.                 else
  191.                     cflag = 3;
  192.                 break;
  193.  
  194.             case 'e':
  195.                 eflag++;
  196.                 break;
  197.  
  198.             case 'i':
  199.                 iflag++;
  200.                 break;
  201.  
  202.             default:
  203.                 fprintf(stderr,
  204.                         "Warning, bad option '%c'\n",
  205.                         ap[-1]);
  206.                 break;
  207.             }
  208.         }
  209.         argc--;
  210.         argv++;
  211.     }
  212.  
  213.     if (argc != 3)
  214.         error("Usage: diff [-options] file1 file2");
  215.     if (cflag && eflag) {
  216.         fprintf(stderr,
  217.                 "Warning, -c and -e are incompatible, -c supressed.\n");
  218.         cflag = FALSE;
  219.     }
  220.     argv++;
  221.     for (i = 0; i <= 1; i++) {
  222.         if (argv[i][0] == '-' && argv[i][1] == EOS) {
  223.             infd[i] = stdin;
  224.             if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
  225.                 cant(TEMPFILE, "work", 1);
  226.         } else {
  227.             infd[i] = fopen(argv[i], "r");
  228.             if (!infd[i])
  229.                 cant(argv[i], "input", 2);        /* Fatal error */
  230.         }
  231.     }
  232.  
  233.     if (infd[0] == stdin && infd[1] == stdin)
  234.         error("Can't diff two things both on standard input.");
  235.  
  236.     if (infd[0] == NULL && infd[1] == NULL) {
  237.         cant(argv[0], "input", 0);
  238.         cant(argv[1], "input", 1);
  239.     }
  240. #ifdef vms
  241.     else if (infd[1] == NULL)
  242.         opendir(1, &argv[1], infd[0]);
  243.     else if (infd[0] == NULL)
  244.         opendir(0, &argv[0], infd[1]);
  245. #endif /* vms */
  246.  
  247.     /*
  248.      * Read input, building hash tables. 
  249.      */
  250.     input(0);
  251.     input(1);
  252.     squish();
  253. #ifdef  DEBUG
  254.     printf("before sort\n");
  255.     for (i = 1; i <= slenA; i++)
  256.         printf("sfileA[%d] = %6d %06o\n",
  257.                i, sfileA[i].serial, sfileA[i].hash);
  258.     for (i = 1; i <= slenB; i++)
  259.         printf("sfileB[%d] = %6d %06o\n",
  260.                i, sfileB[i].serial, sfileB[i].hash);
  261. #endif /* DEBUG */
  262.     sort(sfileA, slenA);
  263.     sort(sfileB, slenB);
  264. #ifdef  TIMING
  265.     ptime("input");
  266. #endif /* TIMING */
  267. #ifdef  DEBUG
  268.     printf("after sort\n");
  269.     for (i = 1; i <= slenA; i++)
  270.         printf("sfileA[%d] = %6d %06o\n",
  271.                i, sfileA[i].serial, sfileB[i].hash);
  272.     for (i = 1; i <= slenB; i++)
  273.         printf("sfileB[%d] = %6d %06o\n",
  274.                i, sfileB[i].serial, sfileB[i].hash);
  275. #endif /* DEBUG */
  276.  
  277.     /*
  278.      * Build equivalence classes. 
  279.      */
  280.     member = (short *) fileB;
  281.     equiv();
  282.     member = (short *) compact((char *) member, (slenB + 2) * sizeof(int),
  283.                                "squeezing member vector");
  284.  
  285.     /*
  286.      * Reorder equivalence classes into array class[] 
  287.      */
  288.     class = (short *) fileA;
  289.     unsort();
  290.     class = (short *) compact((char *) class, (slenA + 2) * sizeof(int),
  291.                               "compacting class vector");
  292. #ifdef  TIMING
  293.     ptime("equiv/unsort");
  294. #endif /* TIMING */
  295.  
  296.     /*
  297.      * Find longest subsequences 
  298.      */
  299.     klist = (int *) myalloc((slenA + 2) * sizeof(int), "klist");
  300.     clist = (CANDIDATE *) myalloc(csize * sizeof(CANDIDATE), "clist");
  301.     i = subseq();
  302. #ifndef OSK
  303.     free((char *) member);
  304.     free((char *) class);
  305. #else /* OSK */
  306.     free((char *) member - sizeof(int));
  307.     free((char *) class - sizeof(int));
  308. #endif /* OSK */
  309.     match = (int *) myalloc((lenA + 2) * sizeof(int), "match");
  310.     unravel(klist[i]);
  311. #ifndef OSK
  312.     free((char *) clist);
  313.     free((char *) klist);
  314. #else /* OSK */
  315.     free((char *) clist - sizeof(int));
  316.     free((char *) klist - sizeof(int));
  317. #endif /* OSK */
  318. #ifdef  TIMING
  319.     ptime("subsequence/unravel");
  320. #endif /* TIMING */
  321.  
  322.     /*
  323.      * Check for fortuitous matches and output differences 
  324.      */
  325.     oldseek = (long *) myalloc((lenA + 2) * sizeof(*oldseek), "oldseek");
  326.     newseek = (long *) myalloc((lenB + 2) * sizeof(*newseek), "newseek");
  327.     textb = myalloc(sizeof text, "textbuffer");
  328.     if (check(argv[0], argv[1]))
  329.         fprintf(stderr, "Spurious match, output is not optimal\n");
  330. #ifdef  TIMING
  331.     ptime("check");
  332. #endif /* TIMING */
  333.     output(argv[0], argv[1]);
  334. #ifdef  TIMING
  335.     ptime("output");
  336.     printf("%ld seconds required\n", sectiontime - totaltime);
  337. #endif /* TIMING */
  338.     if (tempfd != NULL) {
  339.         fclose(tempfd);
  340. #ifdef unix
  341.         unlink(TEMPFILE);
  342. #else /* !unix */
  343. #ifdef OSK
  344.         unlink(TEMPFILE);
  345. #else /* OSK */
  346. #ifdef MSC                        /* MSC 4.0 does not understand disjunctive
  347.                                  * #if's.  */
  348.         unlink(TEMPFILE);
  349. #else /* MSC */
  350.         remove(TEMPFILE);
  351. #endif /* MSC */
  352. #endif /* OSK */
  353. #endif /* unxi */
  354.     }
  355.     return(0);
  356. }
  357.  
  358.  
  359. /*
  360.  * Read the file, building hash table
  361.  */
  362.  
  363. input(which)
  364.     int             which;        /* 0 or 1 to redefine infd[]  */
  365. {
  366.     register LINE  *lentry;
  367.     register int    linect = 0;
  368.     FILE           *fd;
  369. #define    LSIZE_INC 200            /* # of line entries to alloc at once */
  370.     int             lsize = LSIZE_INC;
  371.  
  372.     lentry = (LINE *) myalloc(sizeof(LINE) * (lsize + 3), "line");
  373.     fd = infd[which];
  374.     while (!getline(fd, text)) {
  375.         if (++linect >= lsize) {
  376.             lsize += 200;
  377.             lentry = (LINE *) compact((char *) lentry,
  378.                                       (lsize + 3) * sizeof(LINE),
  379.                                       "extending line vector");
  380.         }
  381.         lentry[linect].hash = hash(text);
  382.     }
  383.  
  384.     /*
  385.      * If input was from stdin ("-" command), finish off the temp file. 
  386.      */
  387.     if (fd == stdin) {
  388.         fclose(tempfd);
  389.         tempfd = infd[which] = fopen(TEMPFILE, "r");
  390.     }
  391.  
  392.     /*
  393.      * If we wanted to be stingy with memory, we could realloc lentry down to
  394.      * its exact size (+3 for some odd reason) here.  No need?  
  395.      */
  396.     len[which] = linect;
  397.     file[which] = lentry;
  398. }
  399.  
  400.  
  401. /*
  402.  * Look for initial and trailing sequences that have identical hash values.
  403.  * Don't bother building them into the candidate vector.
  404.  */
  405.  
  406. squish()
  407. {
  408.     register int    i;
  409.     register LINE  *ap;
  410.     register LINE  *bp;
  411.     int             j;
  412.     int             k;
  413.  
  414.     /*
  415.      * prefix -> first line (from start) that doesn't hash identically 
  416.      */
  417.     i = 0;
  418.     ap = &fileA[1];
  419.     bp = &fileB[1];
  420.     while (i < lenA && i < lenB && ap->hash == bp->hash) {
  421.         i++;
  422.         ap++;
  423.         bp++;
  424.     }
  425.     prefix = i;
  426.  
  427.     /*
  428.      * suffix -> first line (from end) that doesn't hash identically 
  429.      */
  430.     j = lenA - i;
  431.     k = lenB - i;
  432.     ap = &fileA[lenA];
  433.     bp = &fileB[lenB];
  434.     i = 0;
  435.     while (i < j && i < k && ap->hash == bp->hash) {
  436.         i++;
  437.         ap--;
  438.         bp--;
  439.     }
  440.     suffix = i;
  441.  
  442.     /*
  443.      * Tuck the counts away 
  444.      */
  445.     for (k = 0; k <= 1; k++) {
  446.         sfile[k] = file[k] + prefix;
  447.         j = slen[k] = len[k] - prefix - suffix;
  448.  
  449.         for (i = 0, ap = sfile[k]; i <= slen[k]; i++, ap++) {
  450.             ap->serial = i;
  451.         }
  452.     }
  453. }
  454.  
  455.  
  456. /*
  457.  * Sort hash entries
  458.  */
  459.  
  460. sort(vector, vecsize)
  461.     LINE           *vector;        /* What to sort        */
  462.     int             vecsize;    /* How many to sort       */
  463. {
  464.     register int    j;
  465.     register LINE  *aim;
  466.     register LINE  *ai;
  467.     int             mid;
  468.     int             k;
  469.     LINE            work;
  470.  
  471.     for (j = 1; j <= vecsize; j *= 2);
  472.     mid = (j - 1);
  473.     while ((mid /= 2) != 0) {
  474.         k = vecsize - mid;
  475.         for (j = 1; j <= k; j++) {
  476.             for (ai = &vector[j]; ai > vector; ai -= mid) {
  477.                 aim = &ai[mid];
  478.                 if (aim < ai)
  479.                     break;        /* ?? Why ??       */
  480.                 if (aim->hash > ai->hash ||
  481.                     aim->hash == ai->hash &&
  482.                     aim->serial > ai->serial)
  483.                     break;
  484.                 work.hash = ai->hash;
  485.                 ai->hash = aim->hash;
  486.                 aim->hash = work.hash;
  487.                 work.serial = ai->serial;
  488.                 ai->serial = aim->serial;
  489.                 aim->serial = work.serial;
  490.             }
  491.         }
  492.     }
  493. }
  494.  
  495.  
  496. /*
  497.  * Build equivalence class vector
  498.  */
  499.  
  500. equiv()
  501. {
  502.     register LINE  *ap;
  503.     union {
  504.         LINE           *bp;
  505.         short          *mp;
  506.     }               r;
  507.     register int    j;
  508.     LINE           *atop;
  509.  
  510. #ifdef  DEBUG
  511.     printf("equiv entry\n");
  512.     for (j = 1; j <= slenA; j++)
  513.         printf("sfileA[%d] = %6d %06o\n",
  514.                j, sfileA[j].serial, sfileA[j].hash);
  515.     for (j = 1; j <= slenB; j++)
  516.         printf("sfileB[%d] = %6d %06o\n",
  517.                j, sfileB[j].serial, sfileB[j].hash);
  518. #endif /* DEBUG */
  519.     j = 1;
  520.     ap = &sfileA[1];
  521.     r.bp = &sfileB[1];
  522.     atop = &sfileA[slenA];
  523.     while (ap <= atop && j <= slenB) {
  524.         if (ap->hash < r.bp->hash) {
  525.             ap->hash = 0;
  526.             ap++;
  527.         } else if (ap->hash == r.bp->hash) {
  528.             ap->hash = j;
  529.             ap++;
  530.         } else {
  531.             r.bp++;
  532.             j++;
  533.         }
  534.     }
  535.     while (ap <= atop) {
  536.         ap->hash = 0;
  537.         ap++;
  538.     }
  539.     sfileB[slenB + 1].hash = 0;
  540. #ifdef  DEBUG
  541.     printf("equiv exit\n");
  542.     for (j = 1; j <= slenA; j++)
  543.         printf("sfileA[%d] = %6d %06o\n",
  544.                j, sfileA[j].serial, sfileA[j].hash);
  545.     for (j = 1; j <= slenB; j++)
  546.         printf("sfileB[%d] = %6d %06o\n",
  547.                j, sfileB[j].serial, sfileB[j].hash);
  548. #endif /* DEBUG */
  549.     ap = &sfileB[0];
  550.     atop = &sfileB[slenB];
  551.     r.mp = &member[0];
  552.     while (++ap <= atop) {
  553.         r.mp++;
  554.         *r.mp = -(ap->serial);
  555.         while (ap[1].hash == ap->hash) {
  556.             ap++;
  557.             r.mp++;
  558.             *r.mp = ap->serial;
  559.         }
  560.     }
  561.     r.mp[1] = -1;
  562. #ifdef  DEBUG
  563.     for (j = 0; j <= slenB; j++)
  564.         printf("member[%d] = %d\n", j, member[j]);
  565. #endif /* DEBUG */
  566. }
  567.  
  568.  
  569. /*
  570.  * Build class vector
  571.  */
  572.  
  573. unsort()
  574. {
  575.     register int   *temp;
  576.     register int   *tp;
  577.     union {
  578.         LINE           *ap;
  579.         short          *cp;
  580.     }               u;
  581.     LINE           *evec;
  582.     short          *eclass;
  583. #ifdef  DEBUG
  584.     int             i;
  585. #endif /* DEBUG */
  586.  
  587.     temp = (int *) myalloc((slenA + 1) * sizeof(int), "unsort scratch");
  588.     u.ap = &sfileA[1];
  589.     evec = &sfileA[slenA];
  590.     while (u.ap <= evec) {
  591. #ifdef  DEBUG
  592.         printf("temp[%2d] := %06o\n", u.ap->serial, u.ap->hash);
  593. #endif /* DEBUG */
  594.         temp[u.ap->serial] = u.ap->hash;
  595.         u.ap++;
  596.     }
  597.  
  598.     /*
  599.      * Copy into class vector and free work space 
  600.      */
  601.     u.cp = &class[1];
  602.     eclass = &class[slenA];
  603.     tp = &temp[1];
  604.     while (u.cp <= eclass)
  605.         *u.cp++ = *tp++;
  606. #ifndef OSK
  607.     free((char *) temp);
  608. #else /* OSK */
  609.     free((char *) temp - sizeof(int));
  610. #endif /* OSK */
  611. #ifdef  DEBUG
  612.     printf("unsort exit\n");
  613.     for (i = 1; i <= slenA; i++)
  614.         printf("class[%d] = %d %06o\n", i, class[i], class[i]);
  615. #endif /* DEBUG */
  616. }
  617.  
  618.  
  619. /*
  620.  * Generate maximum common subsequence chain in clist[]
  621.  */
  622.  
  623. subseq()
  624. {
  625.     int             a;
  626.     register unsigned ktop;
  627.     register int    b;
  628.     register int    s;
  629.     unsigned        r;
  630.     int             i;
  631.     int             cand;
  632.  
  633.     klist[0] = newcand(0, 0, -1);
  634.     klist[1] = newcand(slenA + 1, slenB + 1, -1);
  635.     ktop = 1;                    /* -> guard entry  */
  636.     for (a = 1; a <= slenA; a++) {
  637.  
  638.         /*
  639.          * For each non-zero element in fileA ... 
  640.          */
  641.         if ((i = class[a]) == 0)
  642.             continue;
  643.         cand = klist[0];        /* No candidate now  */
  644.         r = 0;                    /* Current r-candidate  */
  645.         do {
  646. #ifdef  DEBUG
  647.             printf("a = %d, i = %d, b = %d\n", a, i, member[i]);
  648. #endif /* DEBUG */
  649.  
  650.             /*
  651.              * Perform the merge algorithm 
  652.              */
  653.             if ((b = member[i]) < 0)
  654.                 b = -b;
  655. #ifdef  DEBUG
  656.             printf("search(%d, %d, %d) -> %d\n",
  657.                    r, ktop, b, search(r, ktop, b));
  658. #endif /* DEBUG */
  659.             if ((s = search(r, ktop, b)) != 0) {
  660.                 if (clist[klist[s]].b > b) {
  661.                     klist[r] = cand;
  662.                     r = s;
  663.                     cand = newcand(a, b, klist[s - 1]);
  664. #ifdef  DEBUG
  665.                     dumpklist(ktop, "klist[s-1]->b > b");
  666. #endif /* DEBUG */
  667.                 }
  668.                 if (s >= ktop) {
  669.                     klist[ktop + 1] = klist[ktop];
  670.                     ktop++;
  671. #ifdef  DEBUG
  672.                     klist[r] = cand;
  673.                     dumpklist(ktop, "extend");
  674. #endif /* DEBUG */
  675.                     break;
  676.                 }
  677.             }
  678.         } while (member[++i] > 0);
  679.         klist[r] = cand;
  680.     }
  681. #ifdef  DEBUG
  682.     printf("last entry = %d\n", ktop - 1);
  683. #endif /* DEBUG */
  684.     return (ktop - 1);            /* Last entry found  */
  685. }
  686.  
  687.  
  688. int
  689. newcand(a, b, pred)
  690.     int             a;            /* Line in fileA        */
  691.     int             b;            /* Line in fileB        */
  692.     int             pred;        /* Link to predecessor, index in cand[]  */
  693. {
  694.     register CANDIDATE *new;
  695.  
  696.     clength++;
  697.     if (++clength >= csize) {
  698.         csize += CSIZE_INC;
  699.         clist = (CANDIDATE *) compact((char *) clist,
  700.                                       csize * sizeof(CANDIDATE),
  701.                                       "extending clist");
  702.     }
  703.     new = &clist[clength - 1];
  704.     new->a = a;
  705.     new->b = b;
  706.     new->link = pred;
  707.     return (clength - 1);
  708. }
  709.  
  710.  
  711. /*
  712.  * Search klist[low..top] (inclusive) for b.  If klist[low]->b >= b,
  713.  * return zero.  Else return s such that klist[s-1]->b < b and
  714.  * klist[s]->b >= b.  Note that the algorithm presupposes the two
  715.  * preset "fence" elements, (0, 0) and (slenA, slenB).
  716.  */
  717.  
  718. search(low, high, b)
  719.     register unsigned low;
  720.     register unsigned high;
  721.     register int    b;
  722. {
  723.     register int    temp;
  724.     register unsigned mid;
  725.  
  726.     if (clist[klist[low]].b >= b)
  727.         return (0);
  728.     while ((mid = (low + high) / 2) > low) {
  729.         if ((temp = clist[klist[mid]].b) > b)
  730.             high = mid;
  731.         else if (temp < b)
  732.             low = mid;
  733.         else {
  734.             return (mid);
  735.         }
  736.     }
  737.     return (mid + 1);
  738. }
  739.  
  740.  
  741. unravel(k)
  742.     register int    k;
  743. {
  744.     register int    i;
  745.     register CANDIDATE *cp;
  746.     int             first_trailer;
  747.     int             difference;
  748.  
  749.     first_trailer = lenA - suffix;
  750.     difference = lenB - lenA;
  751. #ifdef  DEBUG
  752.     printf("first trailer = %d, difference = %d\n",
  753.            first_trailer, difference);
  754. #endif /* DEBUG */
  755.     for (i = 0; i <= lenA; i++) {
  756.         match[i] = (i <= prefix) ? i
  757.             : (i > first_trailer) ? i + difference
  758.             : 0;
  759.     }
  760. #ifdef  DEBUG
  761.     printf("unravel\n");
  762. #endif /* DEBUG */
  763.     while (k != -1) {
  764.         cp = &clist[k];
  765. #ifdef  DEBUG
  766.         if (k < 0 || k >= clength)
  767.             error("Illegal link -> %d", k);
  768.         printf("match[%d] := %d\n", cp->a + prefix, cp->b + prefix);
  769. #endif /* DEBUG */
  770.         match[cp->a + prefix] = cp->b + prefix;
  771.         k = cp->link;
  772.     }
  773. }
  774.  
  775.  
  776. /*
  777.  * Check for hash matches (jackpots) and collect random access indices to
  778.  * the two files.
  779.  *
  780.  * It should be possible to avoid doing most of the ftell's by noticing
  781.  * that we are not doing a context diff and noticing that if a line
  782.  * compares equal to the other file, we will not ever need to know its
  783.  * file position.  FIXME.
  784.  */
  785.  
  786. check(fileAname, fileBname)
  787.     char           *fileAname;
  788.     char           *fileBname;
  789. {
  790.     register int    a;            /* Current line in file A  */
  791.     register int    b;            /* Current line in file B  */
  792.     int             jackpot;
  793.  
  794. /*
  795.  * The VAX C ftell() returns the address of the CURRENT record, not the
  796.  * next one (as in DECUS C or, effectively, other C's).  Hence, the values
  797.  * are "off by one" in the array.  OFFSET compensates for this.
  798.  */
  799.  
  800. #ifdef vms
  801. #define OFFSET (-1)
  802. #else /* !vms */
  803. #define OFFSET 0
  804. #endif /* vms */
  805.  
  806.     b = 1;
  807.     rewind(infd[0]);
  808.     rewind(infd[1]);
  809. /*
  810.  * See above; these would be over-written on VMS anyway.
  811.  */
  812.  
  813. #ifndef vms
  814.     oldseek[0] = ftell(infd[0]);
  815.     newseek[0] = ftell(infd[1]);
  816. #endif /* vms */
  817.  
  818.     jackpot = 0;
  819. #ifdef  DEBUG
  820.     printf("match vector\n");
  821.     for (a = 0; a <= lenA; a++)
  822.         printf("match[%d] = %d\n", a, match[a]);
  823. #endif /* DEBUG */
  824.     for (a = 1; a <= lenA; a++) {
  825.         if (match[a] == 0) {
  826.             /* Unique line in A */
  827.             oldseek[a + OFFSET] = ftell(infd[0]);
  828.             getline(infd[0], text);
  829.             continue;
  830.         }
  831.         while (b < match[a]) {
  832.             /* Skip over unique lines in B */
  833.             newseek[b + OFFSET] = ftell(infd[1]);
  834.             getline(infd[1], textb);
  835.             b++;
  836.         }
  837.  
  838.         /*
  839.          * Compare the two, supposedly matching, lines. Unless we are going
  840.          * to print these lines, don't bother to remember where they are.  We
  841.          * only print matching lines if a context diff is happening, or if a
  842.          * jackpot occurs. 
  843.          */
  844.         if (cflag) {
  845.             oldseek[a + OFFSET] = ftell(infd[0]);
  846.             newseek[b + OFFSET] = ftell(infd[1]);
  847.         }
  848.         getline(infd[0], text);
  849.         getline(infd[1], textb);
  850.         if (!streq(text, textb)) {
  851.             fprintf(stderr, "Spurious match:\n");
  852.             fprintf(stderr, "line %d in %s, \"%s\"\n",
  853.                     a, fileAname, text);
  854.             fprintf(stderr, "line %d in %s, \"%s\"\n",
  855.                     b, fileBname, textb);
  856.             match[a] = 0;
  857.             jackpot++;
  858.         }
  859.         b++;
  860.     }
  861.     for (; b <= lenB; b++) {
  862.         newseek[b + OFFSET] = ftell(infd[1]);
  863.         getline(infd[1], textb);
  864.     }
  865. /*
  866.  * The logical converse to the code up above, for NON-VMS systems, to
  867.  * store away an fseek() pointer at the beginning of the file.  For VMS,
  868.  * we need one at EOF...
  869.  */
  870.  
  871. #ifdef vms
  872.     oldseek[lenA] = ftell(infd[0]);
  873.     getline(infd[0], text);        /* Will hit EOF...  */
  874.     newseek[lenB] = ftell(infd[1]);
  875.     getline(infd[1], textb);    /* Will hit EOF...  */
  876. #endif /* vms */
  877.  
  878.     return (jackpot);
  879. }
  880.  
  881.  
  882. output(fileAname, fileBname)
  883.     char           *fileAname, *fileBname;
  884. {
  885.     register int    astart;
  886.     register int    aend = 0;
  887.     int             bstart;
  888.     register int    bend;
  889.  
  890.     rewind(infd[0]);
  891.     rewind(infd[1]);
  892.     match[0] = 0;
  893.     match[lenA + 1] = lenB + 1;
  894.     if (!eflag) {
  895.         if (cflag) {
  896.  
  897.             /*
  898.              * Should include ctime style dates after the file names, but
  899.              * this would be non-trivial on OSK.  Perhaps there should be a
  900.              * special case for stdin. 
  901.              */
  902.             printf("*** %s\n--- %s\n", fileAname, fileBname);
  903.         }
  904.  
  905.         /*
  906.          * Normal printout 
  907.          */
  908.         for (astart = 1; astart <= lenA; astart = aend + 1) {
  909.  
  910.             /*
  911.              * New subsequence, skip over matching stuff 
  912.              */
  913.             while (astart <= lenA
  914.                    && match[astart] == (match[astart - 1] + 1))
  915.                 astart++;
  916.  
  917.             /*
  918.              * Found a difference, setup range and print it 
  919.              */
  920.             bstart = match[astart - 1] + 1;
  921.             aend = astart - 1;
  922.             while (aend < lenA && match[aend + 1] == 0)
  923.                 aend++;
  924.             bend = match[aend + 1] - 1;
  925.             match[aend] = bend;
  926.             change(astart, aend, bstart, bend);
  927.         }
  928.     } else {
  929.  
  930.         /*
  931.          * Edit script output -- differences are output "backwards" for the
  932.          * benefit of a line-oriented editor. 
  933.          */
  934.         for (aend = lenA; aend >= 1; aend = astart - 1) {
  935.             while (aend >= 1
  936.                    && match[aend] == (match[aend + 1] - 1)
  937.                    && match[aend] != 0)
  938.                 aend--;
  939.             bend = match[aend + 1] - 1;
  940.             astart = aend + 1;
  941.             while (astart > 1 && match[astart - 1] == 0)
  942.                 astart--;
  943.             bstart = match[astart - 1] + 1;
  944.             match[astart] = bstart;
  945.             change(astart, aend, bstart, bend);
  946.         }
  947.     }
  948.     if (lenA == 0)
  949.         change(1, 0, 1, lenB);
  950. }
  951.  
  952.  
  953. /*
  954.  * Output a change entry: fileA[astart..aend] changed to fileB[bstart..bend]
  955.  */
  956.  
  957. change(astart, aend, bstart, bend)
  958.     int             astart;
  959.     int             aend;
  960.     int             bstart;
  961.     int             bend;
  962. {
  963.     char            c;
  964.  
  965.     /*
  966.      * This catches a "dummy" last entry 
  967.      */
  968.     if (astart > aend && bstart > bend)
  969.         return;
  970.     c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
  971.     if (cflag)
  972.         fputs("**************\n*** ", stdout);
  973.  
  974.     if (c == 'a' && !cflag)
  975.         range(astart - 1, astart - 1, 0);        /* Addition: just print one
  976.                                                  * odd # */
  977.     else
  978.         range(astart, aend, 0);    /* Print both, if different */
  979.     if (!cflag) {
  980.         putchar(c);
  981.         if (!eflag) {
  982.             if (c == 'd')
  983.                 range(bstart - 1, bstart - 1, 1);        /* Deletion: just print
  984.                                                          * one odd # */
  985.             else
  986.                 range(bstart, bend, 1);    /* Print both, if different */
  987.         }
  988.     }
  989.     putchar('\n');
  990.     if ((!eflag && c != 'a') || cflag) {
  991.         fetch(oldseek, astart, aend, lenA, infd[0],
  992.               cflag ? (c == 'd' ? "- " : "! ") : "< ");
  993.         if (cflag) {
  994.             fputs("--- ", stdout);
  995.             range(bstart, bend, 1);
  996.             fputs(" -----\n", stdout);
  997.         } else if (astart <= aend && bstart <= bend)
  998.             printf("---\n");
  999.     }
  1000.     fetch(newseek, bstart, bend, lenB, infd[1],
  1001.           cflag ? (c == 'a' ? "+ " : "! ") : (eflag ? "" : "> "));
  1002.     if (eflag && bstart <= bend)
  1003.         printf(".\n");
  1004. }
  1005.  
  1006.  
  1007. /*
  1008.  * Print a range
  1009.  */
  1010.  
  1011. range(from, to, w)
  1012.     int             from;
  1013.     int             to;
  1014.     int             w;
  1015. {
  1016.     if (cflag) {
  1017.         if ((from -= cflag) <= 0)
  1018.             from = 1;
  1019.         if ((to += cflag) > len[w])
  1020.             to = len[w];
  1021.     }
  1022.     if (to > from) {
  1023.         printf("%d,%d", from, to);
  1024.     } else if (to < from) {
  1025.         printf("%d,%d", to, from);
  1026.     } else {
  1027.         printf("%d", from);
  1028.     }
  1029. }
  1030.  
  1031.  
  1032. /*
  1033.  * Print the appropriate text
  1034.  */
  1035.  
  1036. fetch(seekvec, start, end, trueend, fd, pfx)
  1037.     long           *seekvec;
  1038.     register int    start;
  1039.     register int    end;
  1040.     int             trueend;
  1041.     FILE           *fd;
  1042.     char           *pfx;
  1043. {
  1044.     register int    i;
  1045.     register int    first;
  1046.     register int    last;
  1047.  
  1048.     if (cflag) {
  1049.         if ((first = start - cflag) <= 0)
  1050.             first = 1;
  1051.         if ((last = end + cflag) > trueend)
  1052.             last = trueend;
  1053.     } else {
  1054.         first = start;
  1055.         last = end;
  1056.     }
  1057.     if (fseek(fd, seekvec[first], 0) != 0) {
  1058.         printf("?Can't read line %d at %08lx (hex) in file%c\n",
  1059.                start, seekvec[first],
  1060.                (fd == infd[0]) ? 'A' : 'B');
  1061.     } else {
  1062.         for (i = first; i <= last; i++) {
  1063.             if (fgetss(text, sizeof text, fd) == NULL) {
  1064.                 printf("** Unexpected end of file\n");
  1065.                 break;
  1066.             }
  1067. #ifdef DEBUG
  1068.             printf("%5d: %s%s\n", i, pfx, text);
  1069. #else /* !DEBUG */
  1070.             fputs((cflag && (i < start || i > end)) ? "  " : pfx, stdout);
  1071.             fputs(text, stdout);
  1072.             putchar('\n');
  1073. #endif /* DEBUG */
  1074.         }
  1075.     }
  1076. }
  1077.  
  1078.  
  1079. /*
  1080.  * Input routine, read one line to buffer[], return TRUE on eof, else FALSE.
  1081.  * The terminating newline is always removed.  If "-b" was given, trailing
  1082.  * whitespace (blanks and tabs) are removed and strings of blanks and
  1083.  * tabs are replaced by a single blank.  Getline() does all hacking for
  1084.  * redirected input files.
  1085.  */
  1086.  
  1087. int
  1088. getline(fd, buffer)
  1089.     FILE           *fd;
  1090.     char           *buffer;
  1091. {
  1092.     register char  *top;
  1093.     register char  *fromp;
  1094.     register char   c;
  1095.  
  1096.     if (fgetss(buffer, sizeof text, fd) == NULL) {
  1097.         *buffer = EOS;
  1098.         return (TRUE);
  1099.     }
  1100.     if (fd == stdin)
  1101.         fputss(buffer, tempfd);
  1102.     if (bflag || iflag) {
  1103.         top = buffer;
  1104.         fromp = buffer;
  1105.         while ((c = *fromp++) != EOS) {
  1106.             if (bflag && (c == ' ' || c == '\t')) {
  1107.                 c = ' ';
  1108.                 while (*fromp == ' ' || *fromp == '\t')
  1109.                     fromp++;
  1110.             }
  1111.             if (iflag)
  1112.                 c = tolower(c);
  1113.             *top++ = c;
  1114.         }
  1115.         if (bflag && top[-1] == ' ')
  1116.             top--;
  1117.         *top = EOS;
  1118.     }
  1119.     return (FALSE);
  1120. }
  1121.  
  1122.  
  1123. static unsigned short crc16a[] = {
  1124.                                   0000000, 0140301, 0140601, 0000500,
  1125.                                   0141401, 0001700, 0001200, 0141101,
  1126.                                   0143001, 0003300, 0003600, 0143501,
  1127.                                   0002400, 0142701, 0142201, 0002100,
  1128. };
  1129.  
  1130. static unsigned short crc16b[] = {
  1131.                                   0000000, 0146001, 0154001, 0012000,
  1132.                                   0170001, 0036000, 0024000, 0162001,
  1133.                                   0120001, 0066000, 0074000, 0132001,
  1134.                                   0050000, 0116001, 0104001, 0043000,
  1135. };
  1136.  
  1137.  
  1138. /*
  1139.  * Return the CRC16 hash code for the buffer
  1140.  * Algorithm from Stu Wecker (Digital memo 130-959-002-00).
  1141.  */
  1142.  
  1143. unsigned short
  1144. hash(buffer)
  1145.     char           *buffer;
  1146. {
  1147.     register unsigned short crc;
  1148.     register char  *tp;
  1149.     register short  temp;
  1150.  
  1151.     crc = 0;
  1152.     for (tp = buffer; *tp != EOS;) {
  1153.         temp = *tp++ ^ crc;        /* XOR crc with new char  */
  1154.         crc = (crc >> 8)
  1155.             ^ crc16a[(temp & 0017)]
  1156.             ^ crc16b[(temp & 0360) >> 4];
  1157.     }
  1158. #ifdef  DEBUG_ALL
  1159.     printf("%06o: %s\n", (crc == 0) ? 1 : crc, buffer);
  1160. #endif /* DEBUG_ALL */
  1161.     return ((crc == 0) ? (unsigned short) 1 : crc);
  1162. }
  1163.  
  1164.  
  1165. #ifdef vms
  1166. opendir(which, arg, okfd)
  1167.     int             which;        /* Which file to open (0 or 1)       */
  1168.     char          **arg;        /* File name argument, &argv[which]  */
  1169.     FILE           *okfd;        /* File name (already open)       */
  1170. {
  1171.     register char  *tp;
  1172.     register int    c;
  1173.     register char  *newname;
  1174.  
  1175.     fgetname(okfd, text);
  1176.  
  1177.     /*
  1178.      * Skip over device name 
  1179.      */
  1180.     for (tp = text; (c = *tp) && c != ':'; tp++);
  1181.     if (c)
  1182.         tp++;
  1183.     else
  1184.         tp = text;
  1185.  
  1186.     /*
  1187.      * Skip over [UIC] or [PPN] if present 
  1188.      */
  1189.     if (*tp == '[' || *tp == '(') {
  1190.         while ((c = *tp++) && c != ']' && c != ')');
  1191.         if (c == 0) {
  1192.             fprintf(stderr, "?Bug: bad file name \"%s\"\n",
  1193.                     text);
  1194.             tp--;
  1195.         }
  1196.     }
  1197.     strcpy(text, tp);
  1198.  
  1199.     /*
  1200.      * Don't include version 
  1201.      */
  1202.     for (tp = text; (c = *tp) && c != ';'; tp++);
  1203.     *tp = 0;
  1204.  
  1205.     /*
  1206.      * Now, text has the file name, tp - text, its length, and *arg the
  1207.      * (possible) directory name.  Create a new file name for opening. 
  1208.      */
  1209. #ifndef    OSK
  1210.     if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
  1211.         error("Out of space at start");
  1212. #ifdef    AMIGA
  1213.     savsiz = tp - text + strlen(*arg) + 1;
  1214.     savptr = newname;
  1215. #endif /* AMIGA */
  1216. #else /* OSK */
  1217.     newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start");
  1218. #endif /* OSK */
  1219.     concat(newname, *arg, text, NULL);
  1220.     if ((infd[which] = fopen(newname, "r")) == NULL)
  1221.         cant(*arg, "constructed input", 1);
  1222.     else
  1223.         *arg = newname;
  1224. }
  1225. /* Amiga C doesn't have all these extensions for directory... */
  1226. #endif /* vms */
  1227.  
  1228.  
  1229. /*
  1230.  * Allocate or crash.
  1231.  */
  1232.  
  1233. char           *
  1234. myalloc(amount, why)
  1235.     unsigned        amount;
  1236.     char           *why;
  1237. {
  1238.     register char  *pointer;
  1239.  
  1240. #ifdef OSK
  1241.     amount += sizeof(int);
  1242. #endif /* OSK */
  1243.     if ((pointer = malloc((unsigned) amount)) == NULL)
  1244.         noroom(why);
  1245. #ifdef OSK
  1246.     *((int *) pointer) = amount;
  1247.     pointer += sizeof(int);
  1248. #ifdef DEBUG
  1249.     fprintf(stderr, "Myalloc: %d at %06o\n", amount, pointer);
  1250. #endif /* DEBUG */
  1251. #endif /* OSK */
  1252. #ifdef    AMIGA
  1253.     savsiz = amount;
  1254.     savptr = pointer;
  1255. #endif /* AMIGA */
  1256.  
  1257.     return (pointer);
  1258. }
  1259.  
  1260.  
  1261. /*
  1262.  * Reallocate pointer, compacting storage
  1263.  *
  1264.  * The "compacting storage" part is probably not relevant any more.
  1265.  * There used to be horrid code here that malloc'd one byte and freed
  1266.  * it at magic times, to cause garbage collection of the freespace
  1267.  * or something.  It's safely gone now, you didn't have to see it.
  1268.  *    -- John Gilmore, Nebula Consultants, Sept 26, 1986
  1269.  */
  1270.  
  1271. char           *
  1272. compact(pointer, new_amount, why)
  1273.     char           *pointer;
  1274.     unsigned        new_amount;
  1275.     char           *why;
  1276. {
  1277.     register char  *new_pointer;
  1278.  
  1279. #ifndef AMIGA
  1280. #ifndef OSK
  1281. #ifdef TURBO
  1282.     extern void    *realloc();
  1283. #else /* !TURBO */
  1284.     extern char    *realloc();
  1285. #endif /* TURBO */
  1286.  
  1287.     if ((new_pointer = realloc(pointer, (unsigned) new_amount)) == NULL) {
  1288.         noroom(why);
  1289.     }
  1290. #else /* OSK */
  1291.     register int    old_amount;
  1292.     new_amount += sizeof(int);
  1293.     if ((new_pointer = malloc(new_amount)) == NULL)
  1294.         noroom(why);
  1295.     *(int *) new_pointer = new_amount;
  1296.     new_pointer += sizeof(int);
  1297.     old_amount = *(((int *) pointer) - 1);
  1298.     /* _strass is like bcopy with the first two arguments reversted */
  1299.     _strass(new_pointer, pointer, (new_amount <= old_amount ?
  1300.                                    new_amount : old_amount) - sizeof(int));
  1301. #ifdef DEBUG
  1302.     fprintf(stderr, "compact %d to %d from %06o to %06o\n",
  1303.             old_amount, new_amount, pointer, new_pointer);
  1304. #endif /* DEBUG */
  1305.     free(pointer - sizeof(int));
  1306. #endif /* OSK */
  1307. #else /* AMIGA */
  1308.  
  1309.     /*
  1310.      * This routine is heavily dependent on C storage allocator hacks For
  1311.      * Amiga, we can't rely on storage being left alone "up to" the boundary
  1312.      * of allocation as in VMS or RSX. Therefore we have to be different here
  1313.      * and allocate a new larger segment, then free the old one. Messy but
  1314.      * hopefully it will work. 
  1315.      */
  1316.     extern char    *malloc();
  1317.  
  1318.     /* No realloc().  Do a malloc and copy it.  */
  1319.     if ((new_pointer = malloc((unsigned) new_amount)) == NULL) {
  1320.         noroom(why);
  1321.     }
  1322.   /* This MUST assume the program calls compact using the old pointer as the
  1323.   last call of malloc... Reason is that RSX version is really simpleminded */
  1324.     cpysiz = savsiz;
  1325.   /* Complain if deallocate area not same as last allocate area */
  1326.     if (savptr != pointer)
  1327.         bogus(why);
  1328.     wrk2 = new_pointer;
  1329.     for (wrk = pointer; cpysiz > 0; cpysiz--) {
  1330.   /* copy data to new area */
  1331.         *wrk2++ = *wrk++;
  1332.     }
  1333.   /* when done, free old memory area. */
  1334.     free(pointer);
  1335. #endif /* AMIGA */
  1336.  
  1337. #ifndef OSK
  1338. #ifdef  DEBUG
  1339.     if (new_pointer != pointer) {
  1340.         fprintf(stderr, "moved from %06o to %06o\n",
  1341.                 pointer, new_pointer);
  1342.     }
  1343. /*  rdump(new_pointer, why);
  1344. */
  1345. #endif /* DEBUG */
  1346. #endif /* OSK */
  1347.     return (new_pointer);
  1348. }
  1349.  
  1350.  
  1351. noroom(why)
  1352.     char           *why;
  1353. {
  1354.     fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
  1355.     exit(IO_ERROR);
  1356. }
  1357.  
  1358.  
  1359. #ifdef    AMIGA
  1360. bogus(why)
  1361.     char           *why;
  1362. {
  1363.     fprintf(stderr, "?DIFF-F-invalid compaction when %s\n", why);
  1364.     exit(IO_ERROR);
  1365. }
  1366. #endif    /* AMIGA */
  1367.  
  1368.  
  1369. #ifdef  DEBUG
  1370. /*
  1371.  * Dump memory block
  1372.  */
  1373.  
  1374. rdump(pointer, why)
  1375.     int            *pointer;
  1376.     char           *why;
  1377. {
  1378.     int            *last;
  1379.     int             count;
  1380.  
  1381.     last = ((int **) pointer)[-1];
  1382.     fprintf(stderr, "dump %s of %06o -> %06o, %d words",
  1383.             why, pointer, last, last - pointer);
  1384.     last = (int *) (((int) last) & ~1);
  1385.     for (count = 0; pointer < last; ++count) {
  1386.         if ((count & 07) == 0) {
  1387.             fprintf(stderr, "\n%06o", pointer);
  1388.         }
  1389.         fprintf(stderr, "\t%06o", *pointer);
  1390.         pointer++;
  1391.     }
  1392.     fprintf(stderr, "\n");
  1393. }
  1394. #endif /* DEBUG */
  1395.  
  1396.  
  1397. /*
  1398.  * Can't open file message
  1399.  */
  1400.  
  1401. cant(filename, what, fatalflag)
  1402.     char           *filename;
  1403.     char           *what;
  1404.     int             fatalflag;
  1405. {
  1406.     fprintf(stderr, "Can't open %s file \"%s\": ", what, filename);
  1407. #ifndef    OSK
  1408.     perror((char *) NULL);
  1409. #else
  1410.     prerr(0, errno);
  1411. #endif
  1412.     if (fatalflag) {
  1413.         exit(fatalflag);
  1414.     }
  1415. }
  1416.  
  1417.  
  1418. #ifdef  DEBUG
  1419. dump(d_linep, d_len, d_which)
  1420.     LINE           *d_linep;
  1421.     int                d_len;
  1422.     int                d_which;
  1423. {
  1424.     register int    i;
  1425.  
  1426.     printf("Dump of file%c, %d elements\n", "AB"[d_which], d_len);
  1427.     printf("linep @ %06o\n", d_linep);
  1428.     for (i = 0; i <= d_len; i++) {
  1429.         printf("%3d  %6d  %06o\n", i,
  1430.                d_linep[i].serial, d_linep[i].hash);
  1431.     }
  1432. }
  1433.  
  1434.  
  1435. /*
  1436.  * Dump klist
  1437.  */
  1438.  
  1439. dumpklist(kmax, why)
  1440.     int             kmax;
  1441.     char           *why;
  1442. {
  1443.     register int    i;
  1444.     register CANDIDATE *cp;
  1445.     register int    count;
  1446.  
  1447.     printf("\nklist[0..%d] %s, clength = %d\n", kmax, why, clength);
  1448.     for (i = 0; i <= kmax; i++) {
  1449.         cp = &clist[klist[i]];
  1450.         printf("%2d %2d", i, klist[i]);
  1451.         if (cp >= &clist[0] && cp < &clist[clength])
  1452.             printf(" (%2d %2d -> %2d)\n", cp->a, cp->b, cp->link);
  1453.         else if (klist[i] == -1)
  1454.             printf(" End of chain\n");
  1455.         else
  1456.             printf(" illegal klist element\n");
  1457.     }
  1458.     for (i = 0; i <= kmax; i++) {
  1459.         count = -1;
  1460.         for (cp = (CANDIDATE *) klist[i]; cp > &clist[0];
  1461.              cp = (CANDIDATE *) & cp->link) {
  1462.             if (++count >= 6) {
  1463.                 printf("\n    ");
  1464.                 count = 0;
  1465.             }
  1466.             printf(" (%2d: %2d,%2d -> %d)",
  1467.                    cp - clist, cp->a, cp->b, cp->link);
  1468.         }
  1469.         printf("\n");
  1470.     }
  1471.     printf("*\n");
  1472. }
  1473. #endif    /* DEBUG */
  1474.  
  1475.  
  1476.  
  1477. #ifdef  TIMING
  1478.  
  1479. /*
  1480.  * Dump time buffer
  1481.  */
  1482.  
  1483. ptime(why)
  1484.     char           *why;
  1485. {
  1486.     long            ttemp;
  1487.  
  1488.     ttemp = time(NULL);
  1489.     printf("%ld seconds for %s\n",
  1490.            ttemp - sectiontime, why);
  1491.     sectiontime = ttemp;
  1492. }
  1493. #endif    /* TIMING */
  1494.  
  1495.  
  1496. /*
  1497.  * TRUE if strings are identical
  1498.  */
  1499.  
  1500. int
  1501. streq(s1, s2)
  1502.     register char  *s1;
  1503.     register char  *s2;
  1504. {
  1505.     while (*s1++ == *s2) {
  1506.         if (*s2++ == EOS)
  1507.             return (TRUE);
  1508.     }
  1509.     return (FALSE);
  1510. }
  1511.  
  1512.  
  1513. /*
  1514.  * Error message before retiring.
  1515.  */
  1516.  
  1517. /* VARARGS */
  1518. error(format, args)
  1519.     char           *format;
  1520. {
  1521.     fprintf(stderr, format, &args);
  1522.     putc('\n', stderr);
  1523.     _error();
  1524. }
  1525.  
  1526.  
  1527. _error()
  1528. {
  1529.     exit(1);
  1530. }
  1531.  
  1532.  
  1533. /*
  1534.  * Like fput() except that it puts a newline at the end of the line.
  1535.  */
  1536.  
  1537. fputss(s, iop)
  1538.     register char  *s;
  1539.     register FILE  *iop;
  1540. {
  1541.     fputs(s, iop);
  1542.     putc('\n', iop);
  1543. }
  1544.  
  1545.  
  1546. /*
  1547.  * Fgetss() is like fgets() except that the terminating newline
  1548.  * is removed. 
  1549.  */
  1550.  
  1551. char           *
  1552. fgetss(s, n, iop)
  1553.     char           *s;
  1554.     register FILE  *iop;
  1555. {
  1556.     register char  *cs;
  1557.  
  1558.     if (fgets(s, n, iop) == NULL)
  1559.         return ((char *) NULL);
  1560.     cs = s + strlen(s) - 1;
  1561.     if (*cs == '\n')
  1562.         *cs = '\0';
  1563.     return (s);
  1564. }
  1565.