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