home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / EFFO / forum4.lzh / SPRACHEN / C / DIFF / diff.c next >
Text File  |  1988-02-18  |  47KB  |  1,923 lines
  1. /*
  2.  * Last Hacked by Robert A. Larson, blarson@ecla.usc.edu, Nov 29 86
  3.  *   OSK support (except for error routines).
  4.  *   Real context diffs, with a couple of minor problems:
  5.  *      If the first change is deleting leading lines, and the second
  6.  *    such that the context overlaps the deleted lines, the deleted
  7.  *    lines are output as context.  This is consistant with other
  8.  *    cases of overlapping context, but patch doesn't like it.  It's
  9.  *    not hard to manually fix the diff in this (rare?) case.
  10.  *      File modifacation times are not output.
  11.  *      At most 9 lines of context is output.
  12.  *
  13.  * Previously Hacked by John Gilmore, hoptoad!gnu, 26Sep86.
  14.  * Compiles and runs under Unix.  Much faster since it doesn't reallocate
  15.  * every data structure in the inner loop(!).  Compatible with Unix diff
  16.  * output format, though it occasionally finds different sets of changed
  17.  * lines (both are valid).  -c option needs work.  Also, ftell's in
  18.  * <check> should be dumped when possible.
  19.  *
  20. From: EVERHART%ARISIA%rca.com@CSNET-RELAY.ARPA
  21. Message-Id: <8608201845.AA15181@lll-crg.ARPA>
  22. Date:     Wed, 20 Aug 86 10:34 EDT
  23. To: hoptoad!gnu@LLL-CRG.ARPA
  24. Subject:  Decus C DIFF (partially moved to Amiga) source.
  25.  */
  26.  
  27. /*
  28.  *        D I F F
  29.  */
  30.  
  31. /* For VMS:
  32.   )BUILD  $(TKBOPTIONS) = {
  33.         TASK  = ...DIF
  34.       }
  35. */
  36.  
  37. /*
  38.  *    OSK changes: since OSK doesn't have realloc, put the size 
  39.  *    allocated in the head of each allocated region.  This code
  40.  *    assumes int is a maximally alligned type.  There is AMIGA
  41.  *    code to avoid realloc, but it is broken.
  42.  */
  43.  
  44. #ifdef  DOCUMENTATION
  45. title  diff  Differential File Comparison
  46. index      Differential File Comparison
  47.  
  48. synopsis
  49.  
  50.   diff [option] file1 file2
  51.  
  52. description
  53.  
  54.   Diff compares two files, showing what must be changed to make
  55.   them identical. Either file1 or file2 (but not both) may refer
  56.   to directories.  If that is the case, a file in the directory
  57.   whose name is the same as the other file argument will be used.
  58.   The standard input may be used for one of the files by replacing
  59.   the argument by "-".  Except for the standard input, both files
  60.   must be on disk devices.
  61.   .s
  62.   Options:
  63.   .lm +8
  64.   .s.i -8;-b  Remove trailing whitespace (blanks and tabs)
  65.   and compress all other strings of whitespace to a single blank.
  66.   .s.i -8;-c  Print some context -- matching lines before
  67.   and after the non-match section.  Mark non-matched sections
  68.   with "|".
  69.   .s.i -8;-i  Ignore lower/upper case distinctions.
  70.   .s.i -8;-e  Output is in an "editor script" format which
  71.   is compatible with the Unix 'ed' editor.
  72.   .s.lm -8
  73.   All information needed to compare the files is maintained in main
  74.   memory. This means that very large files (or fairly large files with
  75.   many differences) will cause the program to abort with an "out
  76.   of space" message.  Main memory requirements (in words) are
  77.   approximately:
  78.   .s
  79.       2 * (length of file1 + length of file2)
  80.   .br
  81.       + 3 * (number of changes)
  82.   .s
  83.   (Where "length" is the number of lines of data in each file.)
  84.   .s
  85.   The algorithm reads each file twice, once to build hash tables and once
  86.   to check for fortuitous matches (two lines that are in fact different,
  87.   but which have the same hash value).  CPU time requirements include
  88.   sorting the hash tables and randomly searching memory tables for
  89.   equivalence classes. For example, on a time-shared VAX-11/780,
  90.   comparing two 1000 line files required about 30 seconds (elapsed
  91.   clock time) and about 10,000 bytes of working storage.  About 90
  92.   per-cent of the time was taken up by file I/O.
  93.  
  94. diagnostics
  95.  
  96.   .lm +8
  97.   .s.i -8;Warning, bad option 'x'
  98.   .s
  99.   The option is ignored.
  100.   .s.i -8;Usage ...
  101.   .s
  102.   Two input files were not specified.
  103.   .s.i -8;Can't open input file "filename".  Can't continue.
  104.   .s.i -8;Out of space
  105.   .s
  106.   The program ran out of memory while comparing the two files.
  107.   .s.i -8;Can't read line nnn at xxx in file[A/B]
  108.   .s
  109.   This indicates an I/O error when seeking to the specific line.
  110.   It should not happen.
  111.   .s.i -8;Spurious match, output is not optimal.
  112.   .s
  113.   Two lines that were different yielded the same hash value.  This is
  114.   harmless except that the difference output is not the minimum set of
  115.   differences between the two files.  For example, instead of the output:
  116.   .s
  117.       lines 1 to 5 were changed to ...
  118.   .s
  119.   the program will print
  120.   .s
  121.       lines 1 to 3 were changed to ...
  122.   .br
  123.       lines 4 to 5 were changed to ...
  124.   .s
  125.   The program uses a CRC16 hash code.  The likelihood of this error is
  126.   quite small.
  127.   .lm -8
  128.  
  129. author
  130.  
  131.   The diff algorithm was developed by J. W. Hunt and M. D. McIlroy,
  132.   using a central algorithm defined by H. S. Stone.
  133.   It was published in:
  134.   .s.lm +4.nf
  135.   Hunt, J. W., and McIlroy, M. D.,
  136.   An Algorithm for Differential File Comparison,
  137.   Computing Science Technical Report #41,
  138.   Bell Laboratories, Murray Hill, NJ  07974
  139.   .s.lm -4.f
  140.  
  141. bugs
  142.  
  143.   On RSX and DECUS C on VMS systems, diff may fail if the both
  144.   files are not "variable-length, implied carriage control"
  145.   format.  The scopy program can be used to convert files
  146.   to this format if problems arise.
  147.  
  148.   When compiled under VAX C, diff handles STREAM_LF files
  149.   properly (in addition to the canonical variable-length implied
  150.   carriage control files).  Other variations should work, but
  151.   have not been tested.
  152.  
  153.   When compiled under VAX C, diff is quite slow for unknown reasons
  154.   which ought to be investigated.  On the other hand, it has access to
  155.   effectively unlimited memory.
  156.  
  157.   Output in a form suitable for ed - the -e option - seems rather
  158.   pointless; the analogue on DEC systems is SLP (SUMSLP on VMS).
  159.   It would be simple to provide SLP-compatible output.  The question
  160.   is, why bother - since the various DEC file comparison utilities
  161.   already produce it.
  162.  
  163. #endif
  164.  
  165. /*
  166.  * Diff maintains all information needed to compare the two files in main
  167.  * memory.  This means that very large files (or fairly large files with
  168.  * many differences) will cause the program to abort with an "out of space"
  169.  * error.  Main memory requirements (in words) are approximately:
  170.  *
  171.  *  2 * (length of file1 + length of file2) + (3 * number of changes)
  172.  *
  173.  * The diff algorithm reads each file twice (once to build hash tables and
  174.  * a second time to check for fortuitous matches), then reads the differences
  175.  * by seeking randomly within the files.  CPU time requirements include
  176.  * sorting the two hash vectors and randomly searching memory tables for
  177.  * equivalence classes.  For example, running in Vax compatibility
  178.  * mode, two 1000 line files with a fair number of differences took
  179.  * about 25 seconds (elapsed wall clock time) for processing.  Most of this
  180.  * time was spent in the file read routines.  This test required slightly
  181.  * more than 6000 words of memory for internal tables.
  182.  *
  183.  * The diff algorithm was developed by J. W. Hunt and M. D. McIlroy,
  184.  * using a central algorithm defined by H. S. Stone.  The algorithm
  185.  * was described in:
  186.  *
  187.  *  Hunt, J. W., and McIlroy, M. D.,
  188.  *  An Algorithm for Differential File Comparison,
  189.  *  Computing Science Technical Report #41,
  190.  *  Bell Laboratories, Murray Hill, NJ  07974
  191.  *  
  192.  * The following description is summarized from that document.  While
  193.  * it has been slightly modified to correspond to the program source, the
  194.  * algorithm is essentially identical.
  195.  *
  196.  * 1.  Read the input files, building two vectors containing the
  197.  *  line number (serial) and hash value (hash) of each line.
  198.  *  Data for fileA will be in a vector pointed to by fileA[],
  199.  *  while data for fileB will be pointed to by fileB[]. The
  200.  *  lengths (number of lines) of the files will be represented
  201.  *  by lenA and lenB respectively.  [This is slightly different
  202.  *  from the published algorithm.]
  203.  *
  204.  * 2.  Note initial and final sequences that have identical
  205.  *  hash values to shorten subsequent processing.  Note that
  206.  *  the "jackpot" phase (step 9.) will examine all lines in
  207.  *  the file.  Next, sort each file using hash as the primary
  208.  *  key and serial as the secondary key.
  209.  *
  210.  * 3.  Construct an array of equivalence classes (member[1..lenB])
  211.  *  where each element contains the line number in fileB and a
  212.  *  flag which is True if the indicated line is the first member
  213.  *  of an equivalence class.  (An equivalence class is a set of
  214.  *  lines which all hash to the same value.  The lines themselves
  215.  *  are not necessarily identical.)
  216.  *
  217.  * 4.  Construct an array, class[1..lenA], where each element, I, is set to
  218.  *  the index of a line, J, in fileB if member[J] is the first
  219.  *   element in an equivalence class and the hash code of line[I] in
  220.  *  fileA is the same as the hash code of line[J] in fileB.  Class[I]
  221.  *  is set to zero if no such line exists.
  222.  *
  223.  *  If non-zero, class[I] now points in member[] to the beginning of
  224.  *  the class of lines in fileB equivalent to line[I] in fileA.
  225.  *
  226.  * The next two steps implement the longest common subsequence algorithm.
  227.  *
  228.  * 5.  Structure CANDIDATE { a, b, previous }, where a and b are line
  229.  *   numbers and previous a reference to a candidate, will store
  230.  *  candidate lists as they are constructed.
  231.  *
  232.  *  Vector clist[] stores references to candidates.  It is dimensioned
  233.  *  (0..min(lenA, lenB) + 1)
  234.  *
  235.  *  Initialize
  236.  *      clist[0] = CANDIDATE {   0,   0, -1 };
  237.  *      clist[1] = CANDIDATE { A+1, B+1, -1 };
  238.  *      ktop = 1;
  239.  *
  240.  *  clist[1] is a fence beyond the last usefully filled element
  241.  *  and -1 is an out-of-range clist index. Ktop is the index of the
  242.  *  fence.  Note, because of the memory allocation used, clist[]
  243.  *  is actually composed of two vectors, clist[] containing the
  244.  *  candidate reference, and klist[] containing pointers to clist.
  245.  *
  246.  * 6.  For (A = 1 to lenA) {
  247.  *      I = class[A];  -- the index in member[]:  beginning of
  248.  *            -- the class of lines in fileB equivalent
  249.  *            -- to this line in fileA.
  250.  *      if (I is non-zero) {
  251.  *        Merge each member into the candidate list
  252.  *        as discussed below.
  253.  *      }
  254.  *
  255.  * Unravel the chain of candidates, getting a vector of common subsequences:
  256.  *
  257.  * 7.  Set all elements of match[0..lenA] to zero.
  258.  *
  259.  * 8.  clist[ktop-1] points to the subsequence chain head.  For each element
  260.  *  in the chain, let A and B be the line number entries.  Then, set
  261.  *
  262.  *      match[A] = B;
  263.  *
  264.  *  The non-zero elements of match[]  now pick out a longest common
  265.  *  subsequence chain, possibly including spurious matches due to
  266.  *  hash coincidences.  The pairings between the two files are:
  267.  *
  268.  *  if (match[A] is non-zero) {
  269.  *      line A in fileA matches line match[A] in fileB;
  270.  *  }
  271.  *
  272.  * Now, read each line of fileA and fileB to check for jackpots:
  273.  *
  274.  * 9.  for (A = 1 to lenA) {
  275.  *      if (match[A] is nonzero) {
  276.  *        if (fileA[A] is not identical to fileB[match[A]])
  277.  *            match[A] = 0;  -- Hash congruence
  278.  *      }
  279.  *  }
  280.  *
  281.  * Ignoring "squish" complications, the merge step may be defined as follows:
  282.  *
  283.  *  Entry:
  284.  *      clist[]      Candidate pointer array
  285.  *      ktop      Fence beyond last filled index
  286.  *      A      Current index in fileA
  287.  *      member[]  Equivalence vector
  288.  *      I      The index in member[] of the first element
  289.  *              of the class of lines in fileB that are
  290.  *              equivalent to line[A] in fileA.
  291.  *
  292.  * 1.  Let clist[R] be "an r-candidate" and C a reference to
  293.  *  the last candidate found, which will always be an r-candidate.
  294.  *  clist[R] will be updated with this reference once the previous
  295.  *  value of clist[R] is no longer needed.  Initialize:
  296.  *
  297.  *      R = 0;
  298.  *      C = clist[0];
  299.  *
  300.  * 2.  Do steps 3 through 6 repeatedly:
  301.  *
  302.  *   3.  set B to the line number in member[I];
  303.  *  search clist[R..ktop] for an element, clist[S], such that
  304.  *
  305.  *      clist[S-1].b < B and clist[S].b >= B
  306.  *
  307.  *  Note that clist[] is ordered on clist[].b so that binary
  308.  *  search will work.  The search algorithm used requires the
  309.  *  two "fence" entries described above.
  310.  *
  311.  *  If such an element is found, perform steps 4. and 5.
  312.  *
  313.  *  4. Extend the longest common subsequence chain:
  314.  *
  315.  *      If (clist[S].b > B) {
  316.  *        clist[R] = C;
  317.  *        R = S;
  318.  *        C = candidate(A, B, clist[S - 1]);
  319.  *      }
  320.  *
  321.  *  5. Extend the number of subsequences, moving the fence:
  322.  *
  323.  *      If (S == ktop) {
  324.  *        clist[ktop + 1] = clist[ktop]
  325.  *        ktop = ktop + 1;
  326.  *        break out of step 2's loop;
  327.  *      }
  328.  *
  329.  *   6.  I = I + 1;
  330.  *  if (member[I] is the first element in another class) {
  331.  *      break out of step 2's loop;
  332.  *  }
  333.  *  else {
  334.  *      continue at step 2.
  335.  *  }
  336.  *
  337.  * 7.  clist[R] = C;
  338.  *  exit merge subroutine.
  339.  *
  340.  * To illustrate vector contents, here is a sample run:
  341.  *
  342.  * File A:
  343.  *  line 1
  344.  *  line 2
  345.  *  line 3
  346.  *  line 4
  347.  *  line 5 gets deleted
  348.  *  line 6
  349.  *
  350.  * File B:
  351.  *  line 1
  352.  *  line 1.5 inserted
  353.  *  line 2
  354.  *  line 3 changed
  355.  *  line 4
  356.  *  line 6
  357.  *
  358.  * (For clarity, the "squish" step is omitted from the following)
  359.  *
  360.  * On entry to equiv() (after readin and sorting), the file[] vector is
  361.  * as follows (the first entry in each pair is the line number, the
  362.  * second is the hash value.  Entries are sorted on hash value):
  363.  *
  364.  * FileA[] (1..lines in fileA):
  365.  *   line   hash
  366.  *  3 042400  6 043300  5 050026  1 102201  2 102701  4 103501
  367.  * FileB[] (1..lines in fileB):
  368.  *  6 043300  2 045600  1 102201  3 102701  5 103501  4 147166
  369.  *
  370.  *
  371.  * After Equiv has processed file[]:
  372.  *
  373.  * FileA[] (1..lines in fileA):
  374.  *   line value
  375.  *  3 0  6 1  5 0  1 3  2 4  4 5
  376.  * Member[] (0..lines in fileB)
  377.  *  0  -6  -2  -1  -3  -5  -4
  378.  *
  379.  *
  380.  * After unsort() has unwound fileB:
  381.  *
  382.  * Class[] (1 .. lines in fileA):
  383.  *  3   4  0  5  0  1
  384.  *
  385.  * Within unravel(), match is built in the following order:
  386.  *
  387.  *  match[6] := 6
  388.  *  match[4] := 5
  389.  *  match[2] := 3
  390.  *  match[1] := 1
  391.  *
  392.  * Match[] (0 .. lines in fileA):
  393.  *
  394.  *   0  1  3  0  5  0  6
  395.  *
  396.  * Output is as follows:
  397.  *
  398.  *  1a2
  399.  *  > line 1.5 inserted
  400.  *  3c4
  401.  *  < line 3
  402.  *  ---
  403.  *  > line 3 changed
  404.  *  5d5
  405.  *  < line 5 gets deleted
  406.  *
  407.  *
  408.  */
  409.  
  410. #include <stdio.h>
  411. #include <ctype.h>
  412.  
  413. #ifdef vms
  414. #include      <ssdef.h>
  415. #include      <stsdef.h>
  416. #define  IO_SUCCESS  (SS | STS)
  417. #define  IO_ERROR  SS
  418. #endif
  419. /*
  420.  * Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
  421.  */
  422. #ifndef  IO_SUCCESS
  423. #define  IO_SUCCESS  0
  424. #endif
  425. #ifndef  IO_ERROR
  426. #define  IO_ERROR  1
  427. #endif
  428.  
  429. #define  EOS      0
  430. #ifdef unix
  431. char temfile[L_tmpnam];
  432. char *tmpnam();
  433. #define  TEMPFILE  (temfile[0]? temfile: (tmpnam(temfile), temfile))
  434. #else
  435. #define  TEMPFILE  "diff.tmp"
  436. #endif
  437. #define  TRUE      1
  438. #define  FALSE      0
  439.  
  440. #ifdef  pdp11
  441. #define  short  int
  442. #endif
  443.  
  444. typedef struct candidate {
  445.   int  b;        /* Line in fileB      */
  446.   int  a;        /* Line in fileA      */
  447.   int  link;        /* Previous candidate      */
  448. } CANDIDATE;
  449.  
  450. typedef struct line {
  451.   unsigned short  hash;      /* Hash value etc.      */
  452.   short      serial;      /* Line number        */
  453. } LINE;
  454.  
  455. LINE  *file[2];        /* Hash/line for total file  */
  456. #define  fileA  file[0]
  457. #define  fileB  file[1]
  458.  
  459. LINE  *sfile[2];        /* Hash/line after prefix  */
  460. #define  sfileA  sfile[0]
  461. #define  sfileB  sfile[1]
  462.  
  463. int  len[2];            /* Actual lines in each file  */
  464. #define  lenA  len[0]
  465. #define  lenB  len[1]
  466.  
  467. int  slen[2];        /* Squished lengths      */
  468. #define  slenA  slen[0]
  469. #define  slenB  slen[1]
  470.  
  471. int  prefix;            /* Identical lines at start  */
  472. int  suffix;            /* Identical lenes at end  */
  473.  
  474. FILE  *infd[2] = { NULL, NULL };  /* Input file identifiers  */
  475. FILE  *tempfd;        /* Temp for input redirection  */
  476.  
  477. extern long  ftell();
  478. extern FILE *fopen();
  479. extern char *malloc();
  480.  
  481. char    *fgetss();
  482. unsigned short      hash();
  483.  
  484. #ifdef    AMIGA
  485. /* Define these types for Amiga C */
  486. char    *savptr;
  487. int    savsiz;
  488. char    *wrk;
  489. char    *wrk2;
  490. int    cpysiz;
  491. #endif
  492. /*
  493.  * The following vectors overlay the area defined by fileA
  494.  */
  495.  
  496. short      *class;      /* Unsorted line numbers  */
  497. int      *klist;      /* Index of element in clist  */
  498. CANDIDATE  *clist;      /* Storage pool for candidates  */
  499. int      clength = 0;      /* Number of active candidates  */
  500. #define    CSIZE_INC 50    /* How many to allocate each time we have to */
  501. int    csize = CSIZE_INC; /* Current size of storage pool */
  502.  
  503. int      *match;        /* Longest subsequence      */
  504. long      *oldseek;      /* Seek position in file A  */
  505.  
  506. /*
  507.  * The following vectors overlay the area defined by fileB
  508.  */
  509.  
  510. short      *member;      /* Concatenated equiv. classes  */
  511. long      *newseek;      /* Seek position in file B  */
  512. char      *textb;        /* Input from file2 for check  */
  513.  
  514. /*
  515.  * Global variables
  516.  */
  517.  
  518. int      eflag  = FALSE;  /* Edit script requested  */
  519. int      bflag  = FALSE;  /* Blank supress requested  */
  520. int      cflag  = FALSE;  /* Context printout      */
  521. int      iflag  = FALSE;  /* Ignore case requested  */
  522. char      text[257];      /* Input line from file1  */
  523. extern char  *myalloc();      /* Storage allocator      */
  524.  
  525. extern char  *compact();      /* Storage compactor      */
  526.  
  527. #ifdef  DEBUG
  528. #ifndef OSK
  529. #define  TIMING
  530. #endif
  531. #endif
  532. #ifdef  TIMING
  533. extern long  time();
  534. extern char  *2152mend;
  535. long      totaltime;
  536. long      sectiontime;
  537. char      *mstart;
  538. #endif
  539.  
  540. main(argc, argv)
  541. int      argc;
  542. char      **argv;
  543. /*
  544.  * Diff main program
  545.  */
  546. {
  547.   register int  i;
  548.   register char  *ap;
  549.  
  550. #ifdef OSK
  551.   extern int _memmins;
  552.   _memmins = 16 * 1024;            /* tell OSK we will malloc a lot */
  553. #endif
  554. #ifdef  TIMING
  555.   sectiontime = time(&totaltime);
  556. #endif
  557. #ifdef vms
  558.   argc = getredirection(argc,argv);
  559. #endif
  560.   while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
  561.       while (*ap != EOS) {
  562.         switch ((*ap++)) {
  563.         case 'b':
  564.               bflag++;
  565.               break;
  566.  
  567.         case 'c':
  568.           if (*ap > '0' && *ap <= '9') cflag = *ap++ - '0';
  569.           else cflag = 3;
  570.           break;
  571.  
  572.         case 'e':
  573.               eflag++;
  574.               break;
  575.  
  576.         case 'i':
  577.               iflag++;
  578.               break;
  579.  
  580.         default:
  581.               fprintf(stderr,
  582.                   "Warning, bad option '%c'\n",
  583.                   ap[-1]);
  584.               break;
  585.         }
  586.       }
  587.       argc--;
  588.       argv++;
  589.   }
  590.  
  591.   if (argc != 3)
  592.       error("Usage: diff [-options] file1 file2");
  593.   if (cflag && eflag) {
  594.       fprintf(stderr,
  595.         "Warning, -c and -e are incompatible, -c supressed.\n");
  596.       cflag = FALSE;
  597.   }
  598.   argv++;
  599.   for (i = 0; i <= 1; i++) {
  600.       if (argv[i][0] == '-' && argv[i][1] == EOS) {
  601.         infd[i] = stdin;
  602.         if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
  603.             cant(TEMPFILE, "work", 1);
  604.       }
  605.       else {
  606.         infd[i] = fopen(argv[i], "r");
  607.       if (!infd[i]) cant(argv[i], "input", 2);    /* Fatal error */
  608.       }
  609.   }
  610.  
  611.   if (infd[0] == stdin && infd[1] == stdin)
  612.     error("Can't diff two things both on standard input.");
  613.  
  614.   if (infd[0] == NULL && infd[1] == NULL) {
  615.       cant(argv[0], "input", 0);
  616.       cant(argv[1], "input", 1);
  617.   }
  618. #ifdef vms
  619.   else if (infd[1] == NULL)
  620.       opendir(1, &argv[1], infd[0]);
  621.   else if (infd[0] == NULL)
  622.       opendir(0, &argv[0], infd[1]);
  623. #endif
  624.  
  625.  /*
  626.    * Read input, building hash tables.
  627.    */
  628.   input(0);
  629.   input(1);
  630.   squish();
  631. #ifdef  DEBUG
  632.   printf("before sort\n");
  633.   for (i = 1; i <= slenA; i++)
  634.       printf("sfileA[%d] = %6d %06o\n",
  635.         i, sfileA[i].serial, sfileA[i].hash);
  636.   for (i = 1; i <= slenB; i++)
  637.       printf("sfileB[%d] = %6d %06o\n",
  638.         i, sfileB[i].serial, sfileB[i].hash);
  639. #endif
  640.   sort(sfileA, slenA);
  641.   sort(sfileB, slenB);
  642. #ifdef  TIMING
  643.   ptime("input");
  644. #endif
  645. #ifdef  DEBUG
  646.   printf("after sort\n");
  647.   for (i = 1; i <= slenA; i++)
  648.       printf("sfileA[%d] = %6d %06o\n",
  649.         i, sfileA[i].serial, sfileB[i].hash);
  650.   for (i = 1; i <= slenB; i++)
  651.       printf("sfileB[%d] = %6d %06o\n",
  652.         i, sfileB[i].serial, sfileB[i].hash);
  653. #endif
  654.   /*
  655.    * Build equivalence classes.
  656.    */
  657.   member = (short *)fileB;
  658.   equiv();
  659.   member = (short *)compact((char *)member, (slenB + 2) * sizeof (int),
  660.         "squeezing member vector");
  661.   /*
  662.    * Reorder equivalence classes into array class[]
  663.    */
  664.   class = (short *)fileA;
  665.   unsort();
  666.   class = (short *)compact((char *)class, (slenA + 2) * sizeof (int),
  667.         "compacting class vector");
  668. #ifdef  TIMING
  669.   ptime("equiv/unsort");
  670. #endif
  671.   /*
  672.     * Find longest subsequences
  673.    */
  674.   klist = (int *)myalloc((slenA + 2) * sizeof (int), "klist");
  675.   clist = (CANDIDATE *)myalloc(csize * sizeof (CANDIDATE), "clist");
  676.   i = subseq();
  677. #ifndef OSK
  678.   free((char *)member);
  679.   free((char *)class);
  680. #else
  681.   free((char *)member - sizeof(int));
  682.   free((char *)class - sizeof(int));
  683. #endif
  684.   match = (int *)myalloc((lenA + 2) * sizeof (int), "match");
  685.   unravel(klist[i]);
  686. #ifndef OSK
  687.   free((char *)clist);
  688.   free((char *)klist);
  689. #else
  690.   free((char *)clist - sizeof(int));
  691.   free((char *)klist - sizeof(int));
  692. #endif
  693. #ifdef  TIMING
  694.   ptime("subsequence/unravel");
  695. #endif
  696.   /*
  697.    * Check for fortuitous matches and output differences
  698.    */
  699.   oldseek = (long *)myalloc((lenA + 2) * sizeof (* oldseek), "oldseek");
  700.   newseek = (long *)myalloc((lenB + 2) * sizeof (* newseek), "newseek");
  701.   textb = myalloc(sizeof text, "textbuffer");
  702.   if (check(argv[0], argv[1]))
  703.       fprintf(stderr, "Spurious match, output is not optimal\n");
  704. #ifdef  TIMING
  705.   ptime("check");
  706. #endif
  707.   output(argv[0], argv[1]);
  708. #ifdef  TIMING
  709.   ptime("output");
  710.   printf("%ld seconds required\n", sectiontime - totaltime);
  711. #endif
  712.   if (tempfd != NULL) {
  713.       fclose(tempfd);
  714. #ifdef unix
  715.       unlink(TEMPFILE);
  716. #else
  717. #ifdef OSK
  718.     unlink(TEMPFILE);
  719. #else
  720.     remove(TEMPFILE);
  721. #endif
  722. #endif 
  723.   }
  724. }
  725.  
  726.  
  727. input(which)
  728. int      which;        /* 0 or 1 to redefine infd[]  */
  729. /*
  730.  * Read the file, building hash table
  731.  */
  732. {
  733.   register LINE      *lentry;
  734.   register int      linect = 0;
  735.   FILE        *fd;
  736. #define    LSIZE_INC 200    /* # of line entries to alloc at once */
  737.   int    lsize = LSIZE_INC;
  738.  
  739.   lentry = (LINE *)myalloc(sizeof(LINE) * (lsize+3), "line");
  740.   fd = infd[which];
  741.   while (!getline(fd, text)) {
  742.     if (++linect >= lsize) {
  743.         lsize += 200;
  744.         lentry = (LINE *)compact((char *)lentry,
  745.           (lsize + 3) * sizeof(LINE),
  746.           "extending line vector");
  747.     }
  748.       lentry[linect].hash = hash(text);
  749.   }
  750.   /*
  751.    * If input was from stdin ("-" command), finish off the temp file.
  752.    */
  753.   if (fd == stdin) {
  754.       fclose(tempfd);
  755.       tempfd = infd[which] = fopen(TEMPFILE, "r");
  756.   }
  757.   /* If we wanted to be stingy with memory, we could realloc lentry down
  758.    * to its exact size (+3 for some odd reason) here.  No need?  */
  759.   len[which] = linect;
  760.   file[which] = lentry;
  761. }
  762.  
  763. squish()
  764. /*
  765.  * Look for initial and trailing sequences that have identical hash values.
  766.  * Don't bother building them into the candidate vector.
  767.  */
  768. {
  769.   register int  i;
  770.   register LINE  *ap;
  771.   register LINE  *bp;
  772.   int      j;
  773.   int      k;
  774.  
  775.   /*
  776.    * prefix -> first line (from start) that doesn't hash identically
  777.    */
  778.   i = 0; ap = &fileA[1]; bp = &fileB[1];
  779.   while (i < lenA && i < lenB && ap->hash == bp->hash) {
  780.       i++; ap++; bp++;
  781.   }
  782.   prefix = i;
  783.   /*
  784.     * suffix -> first line (from end) that doesn't hash identically
  785.    */
  786.   j = lenA - i;
  787.   k = lenB - i;
  788.   ap = &fileA[lenA];
  789.   bp = &fileB[lenB];
  790.   i = 0;
  791.   while (i < j && i < k && ap->hash == bp->hash) {
  792.       i++; ap--; bp--;
  793.   }
  794.   suffix = i;
  795.   /*
  796.    * Tuck the counts away
  797.    */
  798.   for (k = 0; k <= 1; k++) {
  799.       sfile[k] = file[k] + prefix;
  800.       j = slen[k] = len[k] - prefix - suffix;
  801.  
  802.       for (i = 0, ap = sfile[k]; i <= slen[k]; i++, ap++) {
  803.         ap->serial = i;
  804.       }
  805.   }
  806. }
  807.  
  808. sort(vector, vecsize)
  809. LINE      *vector;      /* What to sort        */
  810. int      vecsize;      /* How many to sort      */
  811. /*
  812.  * Sort hash entries
  813.  */
  814. {
  815.   register int  j;
  816.   register LINE  *aim;
  817.   register LINE  *ai;
  818.   int      mid;  
  819.   int      k;
  820.   LINE      work;
  821.  
  822.   for (j = 1; j <= vecsize; j *= 2);
  823.   mid = (j - 1);
  824.   while ((mid /= 2) != 0) {
  825.       k = vecsize - mid;
  826.       for (j = 1; j <= k; j++) {
  827.         for (ai = &vector[j]; ai > vector; ai -= mid) {
  828.             aim = &ai[mid];
  829.             if (aim < ai)
  830.               break;  /* ?? Why ??      */
  831.             if (aim->hash > ai->hash ||
  832.                   aim->hash == ai->hash &&
  833.                   aim->serial > ai->serial)
  834.               break;
  835.             work.hash = ai->hash;
  836.             ai->hash = aim->hash;
  837.             aim->hash = work.hash;
  838.             work.serial = ai->serial;
  839.             ai->serial = aim->serial;
  840.             aim->serial = work.serial;
  841.         }
  842.       }
  843.   }
  844. }
  845.  
  846. equiv()
  847. /*
  848.  * Build equivalence class vector
  849.  */
  850. {
  851.   register LINE  *ap;
  852.   register union {
  853.       LINE    *bp;
  854.       short    *mp;
  855.   } r;
  856.   register int  j;
  857.   LINE    *atop;
  858.  
  859. #ifdef  DEBUG
  860.   printf("equiv entry\n");
  861.   for (j = 1; j <= slenA; j++)
  862.       printf("sfileA[%d] = %6d %06o\n",
  863.             j, sfileA[j].serial, sfileA[j].hash);
  864.   for (j = 1; j <= slenB; j++)
  865.       printf("sfileB[%d] = %6d %06o\n",
  866.             j, sfileB[j].serial, sfileB[j].hash);
  867. #endif
  868.   j = 1;
  869.   ap = &sfileA[1];
  870.   r.bp = &sfileB[1];
  871.   atop = &sfileA[slenA];
  872.   while (ap <= atop && j <= slenB) {
  873.       if (ap->hash < r.bp->hash) {
  874.         ap->hash = 0;
  875.         ap++;
  876.       }
  877.       else if (ap->hash == r.bp->hash) {
  878.         ap->hash = j;
  879.         ap++;
  880.       }
  881.       else {
  882.         r.bp++;
  883.         j++;
  884.       }
  885.   }
  886.   while (ap <= atop) {
  887.       ap->hash = 0;
  888.       ap++;
  889.   }
  890.   sfileB[slenB + 1].hash = 0;
  891. #ifdef  DEBUG
  892.   printf("equiv exit\n");
  893.   for (j = 1; j <= slenA; j++)
  894.       printf("sfileA[%d] = %6d %06o\n",
  895.             j, sfileA[j].serial, sfileA[j].hash);
  896.   for (j = 1; j <= slenB; j++)
  897.       printf("sfileB[%d] = %6d %06o\n",
  898.             j, sfileB[j].serial, sfileB[j].hash);
  899. #endif
  900.   ap = &sfileB[0];
  901.   atop = &sfileB[slenB];
  902.   r.mp = &member[0];
  903.   while (++ap <= atop) {
  904.       r.mp++;
  905.       *r.mp = -(ap->serial);
  906.       while (ap[1].hash == ap->hash) {
  907.         ap++;
  908.         r.mp++;
  909.         *r.mp = ap->serial;
  910.       }
  911.   }
  912.   r.mp[1] = -1;
  913. #ifdef  DEBUG
  914.   for (j = 0; j <= slenB; j++)
  915.       printf("member[%d] = %d\n", j, member[j]);
  916. #endif
  917. }
  918.  
  919. unsort()
  920. /*
  921.  * Build class vector
  922.  */
  923. {
  924.   register int  *temp;
  925.   register int  *tp;
  926.   register union {
  927.       LINE    *ap;
  928.       short    *cp;
  929.   } u;
  930.   LINE    *evec;
  931.   short    *eclass;
  932. #ifdef  DEBUG
  933.   int      i;
  934. #endif
  935.  
  936.   temp = (int *)myalloc((slenA + 1) * sizeof(int), "unsort scratch");
  937.   u.ap = &sfileA[1];
  938.   evec = &sfileA[slenA];
  939.   while (u.ap <= evec) {
  940. #ifdef  DEBUG
  941.       printf("temp[%2d] := %06o\n", u.ap->serial, u.ap->hash);
  942. #endif
  943.       temp[u.ap->serial] = u.ap->hash;
  944.       u.ap++;
  945.   }
  946.   /*
  947.    * Copy into class vector and free work space
  948.    */
  949.   u.cp = &class[1];
  950.   eclass = &class[slenA];
  951.   tp = &temp[1];
  952.   while (u.cp <= eclass)
  953.       *u.cp++ = *tp++;
  954. #ifndef OSK
  955.   free((char *) temp);
  956. #else
  957.   free((char *)temp - sizeof(int));
  958. #endif
  959. #ifdef  DEBUG
  960.   printf("unsort exit\n");
  961.   for (i = 1; i <= slenA; i++)
  962.       printf("class[%d] = %d %06o\n", i, class[i], class[i]);
  963. #endif
  964. }
  965.  
  966. subseq()
  967. /*
  968.  * Generate maximum common subsequence chain in clist[]
  969.  */
  970. {
  971.   int        a;
  972.   register unsigned      ktop;
  973.   register int      b;
  974.   register int      s;
  975.   unsigned        r;
  976.   int        i;
  977.   int        cand;
  978.  
  979.   klist[0] = newcand(0, 0, -1);
  980.   klist[1] = newcand(slenA + 1, slenB + 1, -1);
  981.   ktop = 1;            /* -> guard entry  */
  982.   for (a = 1; a <= slenA; a++) {
  983.       /*
  984.        * For each non-zero element in fileA ...
  985.        */
  986.       if ((i = class[a]) == 0)
  987.         continue;
  988.       cand = klist[0];      /* No candidate now  */
  989.       r = 0;            /* Current r-candidate  */
  990.       do {
  991. #ifdef  DEBUG
  992.         printf("a = %d, i = %d, b = %d\n", a, i, member[i]);
  993. #endif
  994.         /*
  995.          * Perform the merge algorithm
  996.          */
  997.         if ((b = member[i]) < 0)
  998.             b = -b;
  999. #ifdef  DEBUG
  1000.         printf("search(%d, %d, %d) -> %d\n",
  1001.               r, ktop, b, search(r, ktop, b));
  1002. #endif
  1003.         if ((s = search(r, ktop, b)) != 0) {
  1004.             if (clist[klist[s]].b > b) {
  1005.               klist[r] = cand;
  1006.               r = s;
  1007.               cand = newcand(a, b, klist[s-1]);
  1008. #ifdef  DEBUG
  1009.               dumpklist(ktop, "klist[s-1]->b > b");
  1010. #endif
  1011.             }
  1012.             if (s >= ktop) {
  1013.               klist[ktop + 1] = klist[ktop];
  1014.               ktop++;
  1015. #ifdef  DEBUG
  1016.               klist[r] = cand;
  1017.               dumpklist(ktop, "extend");
  1018. #endif
  1019.               break;
  1020.             }
  1021.         }
  1022.       } while (member[++i] > 0);
  1023.     klist[r] = cand;
  1024.   }
  1025. #ifdef  DEBUG
  1026.   printf("last entry = %d\n", ktop - 1);
  1027. #endif
  1028.   return(ktop - 1);        /* Last entry found  */
  1029. }
  1030.  
  1031. int
  1032. newcand(a, b, pred)
  1033. int      a;      /* Line in fileA        */
  1034. int      b;      /* Line in fileB        */
  1035. int      pred;      /* Link to predecessor, index in cand[]  */
  1036. {
  1037.   register CANDIDATE  *new;
  1038.  
  1039.   clength++;
  1040.   if (++clength >= csize) {
  1041.     csize += CSIZE_INC;
  1042.     clist = (CANDIDATE *)compact((char *)clist,
  1043.           csize * sizeof (CANDIDATE),
  1044.           "extending clist");
  1045.   }
  1046.   new = &clist[clength - 1];
  1047.   new->a = a;
  1048.   new->b = b;
  1049.   new->link = pred;
  1050.   return(clength - 1);
  1051. }
  1052.  
  1053. search(low, high, b)
  1054. register unsigned  low;
  1055. register unsigned  high;
  1056. register int  b;
  1057. /*
  1058.  * Search klist[low..top] (inclusive) for b.  If klist[low]->b >= b,
  1059.  * return zero.  Else return s such that klist[s-1]->b < b and
  1060.  * klist[s]->b >= b.  Note that the algorithm presupposes the two
  1061.  * preset "fence" elements, (0, 0) and (slenA, slenB).
  1062.  */
  1063. {
  1064.   register int      temp;
  1065.   register unsigned      mid;
  1066.  
  1067.   if (clist[klist[low]].b >= b)
  1068.       return(0);
  1069.   while ((mid = (low + high) / 2) > low) {
  1070.       if ((temp = clist[klist[mid]].b) > b)
  1071.         high = mid;
  1072.       else if (temp < b)
  1073.         low = mid;
  1074.       else {
  1075.         return(mid);
  1076.       }
  1077.   }
  1078.   return(mid + 1);
  1079. }
  1080.  
  1081.  
  1082. unravel(k)
  1083. register int  k;
  1084. {
  1085.   register int      i;
  1086.   register CANDIDATE  *cp;
  1087.   int        first_trailer;
  1088.   int        difference;
  1089.  
  1090.   first_trailer = lenA - suffix;
  1091.   difference = lenB - lenA;
  1092. #ifdef  DEBUG
  1093.   printf("first trailer = %d, difference = %d\n",
  1094.       first_trailer, difference);
  1095. #endif
  1096.   for (i = 0; i <= lenA; i++) {
  1097.       match[i] = (i <= prefix) ? i
  1098.         : (i > first_trailer) ? i + difference
  1099.         : 0;
  1100.   }
  1101. #ifdef  DEBUG
  1102.   printf("unravel\n");
  1103. #endif
  1104.   while (k != -1) {
  1105.       cp = &clist[k];
  1106. #ifdef  DEBUG
  1107.       if (k < 0 || k >= clength)
  1108.         error("Illegal link -> %d", k);
  1109.       printf("match[%d] := %d\n", cp->a + prefix, cp->b + prefix);
  1110. #endif
  1111.       match[cp->a + prefix] = cp->b + prefix;
  1112.       k = cp->link;
  1113.   }
  1114. }
  1115.  
  1116.  
  1117. /*
  1118.  * Check for hash matches (jackpots) and collect random access indices to
  1119.  * the two files.
  1120.  *
  1121.  * It should be possible to avoid doing most of the ftell's by noticing
  1122.  * that we are not doing a context diff and noticing that if a line
  1123.  * compares equal to the other file, we will not ever need to know its
  1124.  * file position.  FIXME.
  1125.  */
  1126. check(fileAname, fileBname)
  1127. char      *fileAname;
  1128. char      *fileBname;
  1129. {
  1130.   register int  a;      /* Current line in file A  */
  1131.   register int  b;      /* Current line in file B  */
  1132.   int      jackpot;
  1133.  
  1134. /*
  1135.  * The VAX C ftell() returns the address of the CURRENT record, not the
  1136.  * next one (as in DECUS C or, effectively, other C's).  Hence, the values
  1137.  * are "off by one" in the array.  OFFSET compensates for this.
  1138.  */
  1139. #ifdef vms
  1140. #define OFFSET (-1)
  1141. #else
  1142. #define OFFSET 0
  1143. #endif
  1144.  
  1145.   b = 1;
  1146.   rewind(infd[0]);
  1147.   rewind(infd[1]);
  1148. /*
  1149.  * See above; these would be over-written on VMS anyway.
  1150.  */
  1151. #ifndef vms
  1152.   oldseek[0] = ftell(infd[0]);
  1153.   newseek[0] = ftell(infd[1]);
  1154. #endif
  1155.  
  1156.   jackpot = 0;
  1157. #ifdef  DEBUG
  1158.   printf("match vector\n");
  1159.   for (a = 0; a <= lenA; a++)
  1160.       printf("match[%d] = %d\n", a, match[a]);
  1161. #endif
  1162.   for (a = 1; a <= lenA; a++) {
  1163.       if (match[a] == 0) {
  1164.       /* Unique line in A */
  1165.         oldseek[a+OFFSET] = ftell(infd[0]);
  1166.         getline(infd[0], text);
  1167.         continue;  
  1168.       }
  1169.       while (b < match[a]) {
  1170.       /* Skip over unique lines in B */
  1171.         newseek[b+OFFSET] = ftell(infd[1]);
  1172.         getline(infd[1], textb);
  1173.         b++;
  1174.       }
  1175.  
  1176.     /*
  1177.      * Compare the two, supposedly matching, lines.
  1178.      * Unless we are going to print these lines, don't bother to
  1179.      * remember where they are.  We only print matching lines
  1180.      * if a context diff is happening, or if a jackpot occurs.
  1181.      */
  1182.     if (cflag) {
  1183.         oldseek[a+OFFSET] = ftell(infd[0]);
  1184.         newseek[b+OFFSET] = ftell(infd[1]);
  1185.     }
  1186.       getline(infd[0], text);
  1187.       getline(infd[1], textb);
  1188.       if (!streq(text, textb)) {
  1189.         fprintf(stderr,  "Spurious match:\n");
  1190.         fprintf(stderr, "line %d in %s, \"%s\"\n",
  1191.             a, fileAname, text);
  1192.         fprintf(stderr, "line %d in %s, \"%s\"\n",
  1193.             b, fileBname, textb);
  1194.         match[a] = 0;
  1195.         jackpot++;
  1196.       }
  1197.  
  1198.       b++;
  1199.   }
  1200.   for (; b <= lenB; b++) {
  1201.       newseek[b+OFFSET] = ftell(infd[1]);
  1202.       getline(infd[1], textb);
  1203.   }
  1204. /*
  1205.  * The logical converse to the code up above, for NON-VMS systems, to
  1206.  * store away an fseek() pointer at the beginning of the file.  For VMS,
  1207.  * we need one at EOF...
  1208.  */
  1209. #ifdef vms
  1210.   oldseek[lenA] = ftell(infd[0]);
  1211.   getline(infd[0],text);        /* Will hit EOF...  */
  1212.   newseek[lenB] = ftell(infd[1]);
  1213.   getline(infd[1],textb);        /* Will hit EOF...  */
  1214. #endif
  1215.  
  1216.   return(jackpot);
  1217. }
  1218.  
  1219. output(fileAname, fileBname)
  1220. char *fileAname, *fileBname;
  1221. {
  1222.   register int  astart;
  1223.   register int  aend = 0;
  1224.   int      bstart;
  1225.   register int  bend;
  1226.  
  1227.   rewind(infd[0]);
  1228.   rewind(infd[1]);
  1229.   match[0] = 0;
  1230.   match[lenA+1] = lenB + 1;
  1231.   if (!eflag) {
  1232.     if (cflag) {
  1233.         /*
  1234.          * Should include ctime style dates after the file names, but
  1235.          * this would be non-trivial on OSK.  Perhaps there should be
  1236.          * a special case for stdin.
  1237.          */
  1238.         printf("*** %s\n--- %s\n", fileAname, fileBname);
  1239.     }
  1240.       /*
  1241.        * Normal printout
  1242.        */
  1243.       for (astart = 1; astart <= lenA; astart = aend + 1) {
  1244.         /*
  1245.          * New subsequence, skip over matching stuff
  1246.          */
  1247.         while (astart <= lenA
  1248.               && match[astart] == (match[astart - 1] + 1))
  1249.             astart++;
  1250.         /*
  1251.          * Found a difference, setup range and print it
  1252.          */
  1253.         bstart = match[astart - 1] + 1;
  1254.         aend = astart - 1;
  1255.         while (aend < lenA && match[aend + 1] == 0)
  1256.             aend++;
  1257.         bend = match[aend + 1] - 1;
  1258.         match[aend] = bend;
  1259.         change(astart, aend, bstart, bend);
  1260.       }
  1261.   }
  1262.   else {
  1263.       /*
  1264.        * Edit script output -- differences are output "backwards"
  1265.        * for the benefit of a line-oriented editor.
  1266.        */
  1267.       for (aend = lenA; aend >= 1; aend = astart - 1) {
  1268.         while (aend >= 1
  1269.               && match[aend] == (match[aend + 1] - 1)
  1270.               && match[aend] != 0)
  1271.             aend--;
  1272.         bend = match[aend + 1] - 1;
  1273.         astart = aend + 1;
  1274.         while (astart > 1 && match[astart - 1] == 0)
  1275.             astart--;
  1276.         bstart = match[astart - 1] + 1;
  1277.         match[astart] = bstart;
  1278.         change(astart, aend, bstart, bend);
  1279.       }
  1280.   }
  1281.   if (lenA == 0)
  1282.       change(1, 0, 1, lenB);
  1283. }
  1284.  
  1285.  
  1286. /*
  1287.  * Output a change entry: fileA[astart..aend] changed to fileB[bstart..bend]
  1288.  */
  1289. change(astart, aend, bstart, bend)
  1290. int      astart;
  1291. int      aend;
  1292. int      bstart;
  1293. int      bend;
  1294. {
  1295.   char c;
  1296.   /*
  1297.    * This catches a "dummy" last entry
  1298.    */
  1299.   if (astart > aend && bstart > bend)
  1300.       return;
  1301.   c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
  1302.   if (cflag) fputs("**************\n*** ", stdout);
  1303.  
  1304.   if (c == 'a' && !cflag)
  1305.     range(astart-1, astart-1, 0);    /* Addition: just print one odd # */
  1306.   else
  1307.     range(astart, aend, 0);        /* Print both, if different */
  1308.   if (!cflag) {
  1309.     putchar(c);
  1310.     if (!eflag) {
  1311.     if (c == 'd')
  1312.         range(bstart-1, bstart-1, 1); /* Deletion: just print one odd # */
  1313.     else
  1314.         range(bstart, bend, 1);    /* Print both, if different */
  1315.     }
  1316.   }
  1317.   putchar('\n');
  1318.   if (!eflag) {
  1319.       fetch(oldseek, astart, aend, lenA, infd[0], 
  1320.         cflag ? (c=='d' ? "- " : "! ") : "< ");
  1321.     if (cflag) {
  1322.       fputs("--- ", stdout);
  1323.       range(bstart, bend, 1);
  1324.       fputs(" -----\n", stdout);
  1325.     } else if (astart <= aend && bstart <= bend)
  1326.         printf("---\n");
  1327.   }
  1328.   fetch(newseek, bstart, bend, lenB, infd[1], 
  1329.       cflag ? (c=='a' ? "+ " : "! ") : (eflag ? "" : "> "));
  1330.   if (eflag && bstart <= bend)
  1331.       printf(".\n");
  1332. }
  1333.  
  1334.  
  1335. range(from, to, w)
  1336. int      from;
  1337. int      to;
  1338. int    w;
  1339. /*
  1340.  * Print a range
  1341.  */
  1342. {
  1343.   if (cflag) {
  1344.     if((from -= cflag) <= 0) from = 1;
  1345.     if((to += cflag) > len[w]) to = len[w];
  1346.   }
  1347.   if (to > from) {
  1348.     printf("%d,%d", from, to);
  1349.   } else if (to < from) {
  1350.     printf("%d,%d", to, from);
  1351.   } else {
  1352.     printf("%d", from);
  1353.   }
  1354. }
  1355.  
  1356.  
  1357. fetch(seekvec, start, end, trueend, fd, pfx)
  1358. long      *seekvec;
  1359. register int  start;
  1360. register int  end;
  1361. int      trueend;
  1362. FILE      *fd;
  1363. char      *pfx;
  1364. /*
  1365.  * Print the appropriate text
  1366.  */
  1367. {
  1368.   register int  i;
  1369.   register int    first;
  1370.   register int    last;
  1371.  
  1372.   if (cflag) {
  1373.     if((first = start - cflag) <= 0) first = 1;
  1374.     if((last = end + cflag) > trueend) last = trueend;
  1375.   } else {
  1376.     first = start;
  1377.     last = end;
  1378.   }
  1379.   if (fseek(fd, seekvec[first], 0) != 0) {
  1380.       printf("?Can't read line %d at %08lx (hex) in file%c\n",
  1381.         start, seekvec[first],
  1382.         (fd == infd[0]) ? 'A' : 'B');
  1383.   }
  1384.   else {
  1385.       for (i = first; i <= last; i++) {
  1386.         if (fgetss(text, sizeof text, fd) == NULL) {
  1387.             printf("** Unexpected end of file\n");
  1388.             break;
  1389.         }
  1390. #ifdef DEBUG
  1391.         printf("%5d: %s%s\n", i, pfx, text);
  1392. #else
  1393.         fputs((cflag && (i<start || i>end)) ? "  " : pfx, stdout);
  1394.         fputs(text, stdout);
  1395.       putchar('\n');
  1396. #endif
  1397.       }
  1398.   }  
  1399. }
  1400.  
  1401.  
  1402. /*
  1403.  * Input routine, read one line to buffer[], return TRUE on eof, else FALSE.
  1404.  * The terminating newline is always removed.  If "-b" was given, trailing
  1405.  * whitespace (blanks and tabs) are removed and strings of blanks and
  1406.  * tabs are replaced by a single blank.  Getline() does all hacking for
  1407.  * redirected input files.
  1408.  */
  1409. int
  1410. getline(fd, buffer)
  1411. FILE      *fd;
  1412. char      *buffer;
  1413. {
  1414.   register char  *top;
  1415.   register char  *fromp;
  1416.   register char  c;
  1417.  
  1418.   if (fgetss(buffer, sizeof text, fd) == NULL) {
  1419.       *buffer = EOS;
  1420.       return(TRUE);
  1421.   }
  1422.   if (fd == stdin)
  1423.       fputss(buffer, tempfd);
  1424.   if (bflag || iflag) {
  1425.       top = buffer;
  1426.       fromp = buffer;
  1427.       while ((c = *fromp++) != EOS) {
  1428.         if (bflag && (c == ' ' || c == '\t')) {
  1429.             c = ' ';
  1430.             while (*fromp == ' ' || *fromp == '\t')
  1431.               fromp++;
  1432.         }
  1433.         if (iflag)
  1434.             c = tolower(c);
  1435.         *top++ = c;
  1436.       }
  1437.       if (bflag && top[-1] == ' ')
  1438.         top--;
  1439.       *top = EOS;
  1440.   }
  1441.   return(FALSE);
  1442. }
  1443. static unsigned short crc16a[] = {
  1444.   0000000,  0140301,  0140601,  0000500,
  1445.   0141401,  0001700,  0001200,  0141101,
  1446.   0143001,  0003300,  0003600,  0143501,
  1447.   0002400,  0142701,  0142201,  0002100,  
  1448. };
  1449. static unsigned short crc16b[] = {
  1450.   0000000,  0146001,  0154001,  0012000,
  1451.   0170001,  0036000,  0024000,  0162001,
  1452.   0120001,  0066000,  0074000,  0132001,
  1453.   0050000,  0116001,  0104001,  0043000,
  1454. };
  1455.  
  1456. unsigned short
  1457. hash(buffer)
  1458. char      *buffer;
  1459. /*
  1460.  * Return the CRC16 hash code for the buffer
  1461.  * Algorithm from Stu Wecker (Digital memo 130-959-002-00).
  1462.  */
  1463. {
  1464.   register unsigned short  crc;
  1465.   register char      *tp;
  1466.   register short       temp;
  1467.  
  1468.   crc = 0;
  1469.   for (tp = buffer; *tp != EOS;) {
  1470.       temp = *tp++ ^ crc;  /* XOR crc with new char  */
  1471.       crc = (crc >> 8)
  1472.         ^ crc16a[(temp & 0017)]
  1473.         ^ crc16b[(temp & 0360) >> 4];
  1474.   }
  1475. #ifdef  DEBUG_ALL
  1476.   printf("%06o: %s\n", (crc == 0) ? 1 : crc, buffer);
  1477. #endif
  1478.   return((crc == 0) ? (unsigned short) 1 : crc);
  1479. }      
  1480.  
  1481.  
  1482. #ifdef vms
  1483. opendir(which, arg, okfd)
  1484. int      which;      /* Which file to open (0 or 1)      */
  1485. char      **arg;      /* File name argument, &argv[which]  */
  1486. FILE      *okfd;      /* File name (already open)      */
  1487. {
  1488.   register char      *tp;
  1489.   register int      c;
  1490.   register char      *newname;
  1491.  
  1492.   fgetname(okfd, text);
  1493.   /*
  1494.    * Skip over device name
  1495.    */
  1496.   for (tp = text; (c = *tp) && c != ':'; tp++);
  1497.   if (c)  tp++;
  1498.   else  tp = text;
  1499.   /*
  1500.    * Skip over [UIC] or [PPN] if present
  1501.    */
  1502.   if (*tp == '[' || *tp == '(') {
  1503.       while ((c = *tp++) && c != ']' && c != ')');
  1504.       if (c == 0) {
  1505.         fprintf(stderr, "?Bug: bad file name \"%s\"\n",
  1506.               text);
  1507.         tp--;
  1508.       }
  1509.   }
  1510.   strcpy(text, tp);
  1511.   /*
  1512.    * Don't include version
  1513.    */
  1514.   for (tp = text; (c = *tp) && c != ';'; tp++);
  1515.   *tp = 0;
  1516.   /*
  1517.    * Now, text has the file name, tp - text, its length,
  1518.    * and *arg the (possible) directory name.  Create a new
  1519.    * file name for opening.
  1520.    */
  1521. #ifndef    OSK
  1522.   if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
  1523.       error("Out of space at start");
  1524. #ifdef    AMIGA
  1525.     savsiz = tp - text + strlen(*arg) + 1;
  1526.     savptr = newname;
  1527. #endif
  1528. #else
  1529.   newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start");
  1530. #endif
  1531.   concat(newname, *arg, text, NULL);
  1532.   if ((infd[which] = fopen(newname, "r")) == NULL)
  1533.       cant(*arg, "constructed input", 1);
  1534.   else
  1535.       *arg = newname;
  1536. }
  1537. /* Amiga C doesn't have all these extensions for directory... */
  1538. #endif
  1539.  
  1540. char *
  1541. myalloc(amount, why)
  1542. int      amount;
  1543. char      *why;
  1544. /*
  1545.  * Allocate or crash.
  1546.  */
  1547. {
  1548.   register char  *pointer;
  1549.  
  1550. #ifdef OSK
  1551.   amount += sizeof(int);
  1552. #endif
  1553.   if ((pointer = malloc((unsigned) amount)) == NULL)
  1554.       noroom(why);
  1555. #ifdef OSK
  1556.   *((int *)pointer) = amount;
  1557.   pointer += sizeof(int);
  1558. #ifdef DEBUG
  1559.   fprintf(stderr, "Myalloc: %d at %06o\n", amount, pointer);
  1560. #endif
  1561. #endif
  1562. #ifdef    AMIGA
  1563.    savsiz =  amount;
  1564.    savptr = pointer;
  1565. #endif
  1566.  
  1567.   return (pointer);
  1568. }
  1569.  
  1570.  
  1571. /*
  1572.  * Reallocate pointer, compacting storage
  1573.  *
  1574.  * The "compacting storage" part is probably not relevant any more.
  1575.  * There used to be horrid code here that malloc'd one byte and freed
  1576.  * it at magic times, to cause garbage collection of the freespace
  1577.  * or something.  It's safely gone now, you didn't have to see it.
  1578.  *    -- John Gilmore, Nebula Consultants, Sept 26, 1986
  1579.  */
  1580. char *
  1581. compact(pointer, new_amount, why)
  1582. char      *pointer;
  1583. int      new_amount;
  1584. char      *why;
  1585. {
  1586.   register char *new_pointer;
  1587.  
  1588. #ifndef AMIGA
  1589. #ifndef OSK
  1590.   extern char *realloc();
  1591.  
  1592.   if ((new_pointer =  realloc(pointer, (unsigned) new_amount)) == NULL){
  1593.       noroom(why);
  1594.   }
  1595. #else
  1596.   register int old_amount;
  1597.   new_amount += sizeof(int);
  1598.   if((new_pointer = malloc(new_amount)) == NULL) noroom(why);
  1599.   *(int *)new_pointer = new_amount;
  1600.   new_pointer += sizeof(int);
  1601.   old_amount = *(((int *)pointer)-1);
  1602.   /* _strass is like bcopy with the first two arguments reversted */
  1603.   _strass(new_pointer, pointer, (new_amount <= old_amount ?
  1604.       new_amount : old_amount) - sizeof(int));
  1605. #ifdef DEBUG
  1606.   fprintf(stderr, "compact %d to %d from %06o to %06o\n", 
  1607.     old_amount, new_amount, pointer, new_pointer);
  1608. #endif
  1609.   free(pointer - sizeof(int));
  1610. #endif
  1611. #else
  1612.   /*
  1613.    * This routine is heavily dependent on C storage allocator hacks
  1614.    * For Amiga, we can't rely on storage being left alone "up to"
  1615.    * the boundary of allocation as in VMS or RSX. Therefore we have
  1616.    * to be different here and allocate a new larger segment, then
  1617.    * free the old one. Messy but hopefully it will work.
  1618.    */
  1619.   extern char  *malloc();
  1620.  
  1621.   /* No realloc().  Do a malloc and copy it.  */
  1622.   if ((new_pointer = malloc((unsigned) new_amount)) == NULL){
  1623.       noroom(why);
  1624.   }
  1625. /* This MUST assume the program calls compact using the old pointer as the
  1626.   last call of malloc... Reason is that RSX version is really simpleminded */
  1627.    cpysiz=savsiz;
  1628. /* Complain if deallocate area not same as last allocate area */
  1629.  if (savptr != pointer) bogus(why);
  1630.    wrk2=new_pointer;
  1631.    for (wrk=pointer;cpysiz > 0;cpysiz--){
  1632. /* copy data to new area */
  1633.      *wrk2++ = *wrk++;
  1634.      }
  1635. /* when done, free old memory area. */
  1636.    free(pointer);
  1637. #endif
  1638.  
  1639. #ifndef OSK
  1640. #ifdef  DEBUG
  1641.   if (new_pointer != pointer) {
  1642.       fprintf(stderr, "moved from %06o to %06o\n",
  1643.         pointer, new_pointer);
  1644.   }
  1645. /*  rdump(new_pointer, why);
  1646. */
  1647. #endif
  1648. #endif
  1649.   return (new_pointer);
  1650. }
  1651.  
  1652. noroom(why)
  1653. char      *why;
  1654. {
  1655.   fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
  1656.   exit(IO_ERROR);
  1657. }
  1658.  
  1659. #ifdef    AMIGA
  1660. bogus(why)
  1661. char      *why;
  1662. {
  1663.   fprintf(stderr, "?DIFF-F-invalid compaction when %s\n", why);
  1664.   exit(IO_ERROR);
  1665. }
  1666. #endif
  1667.  
  1668. #ifdef  DEBUG
  1669. rdump(pointer, why)
  1670. int      *pointer;
  1671. char      *why;
  1672. /*
  1673.  * Dump memory block
  1674.  */
  1675. {
  1676.   int  *last;
  1677.   int  count;
  1678.  
  1679.   last = ((int **)pointer)[-1];
  1680.   fprintf(stderr, "dump %s of %06o -> %06o, %d words",
  1681.         why, pointer, last, last - pointer);
  1682.   last = (int *)(((int) last) & ~1);
  1683.   for (count = 0; pointer < last; ++count) {
  1684.       if ((count & 07) == 0) {
  1685.         fprintf(stderr, "\n%06o", pointer);
  1686.       }
  1687.       fprintf(stderr, "\t%06o", *pointer);
  1688.       pointer++;
  1689.   }
  1690.   fprintf(stderr, "\n");
  1691. }
  1692. #endif
  1693. cant(filename, what, fatalflag)
  1694. char      *filename;
  1695. char      *what;
  1696. int      fatalflag;
  1697. /*
  1698.  * Can't open file message
  1699.  */
  1700. {
  1701.   fprintf(stderr, "Can't open %s file \"%s\": ", what, filename);
  1702. #ifndef    OSK
  1703.   perror((char *)NULL);
  1704. #else
  1705.   prerr(0, errno);
  1706. #endif
  1707.   if (fatalflag) {
  1708.       exit(fatalflag);
  1709.   }
  1710. }
  1711. #ifdef  DEBUG
  1712. dump(d_linep, d_len, d_which)
  1713. LINE  *d_linep;
  1714. {
  1715.   register int i;
  1716.   
  1717.   printf("Dump of file%c, %d elements\n", "AB"[d_which], d_len);
  1718.   printf("linep @ %06o\n", d_linep);
  1719.   for (i = 0; i <= d_len; i++) {
  1720.       printf("%3d  %6d  %06o\n", i,
  1721.             d_linep[i].serial, d_linep[i].hash);
  1722.   }
  1723. }
  1724.  
  1725. dumpklist(kmax, why)
  1726. int  kmax;
  1727. char  *why;
  1728. /*
  1729.  * Dump klist
  1730.  */
  1731. {
  1732.   register int      i;
  1733.   register CANDIDATE  *cp;
  1734.   register int      count;
  1735.  
  1736.   printf("\nklist[0..%d] %s, clength = %d\n", kmax, why, clength);
  1737.   for (i = 0; i <= kmax; i++) {
  1738.       cp = &clist[klist[i]];
  1739.       printf("%2d %2d", i, klist[i]);
  1740.       if (cp >= &clist[0] && cp < &clist[clength])
  1741.         printf(" (%2d %2d -> %2d)\n", cp->a, cp->b, cp->link);
  1742.       else if (klist[i] == -1)
  1743.         printf(" End of chain\n");
  1744.       else  printf(" illegal klist element\n");
  1745.   }
  1746.   for (i = 0; i <= kmax; i++) {
  1747.       count = -1;
  1748.       for (cp = (CANDIDATE *)klist[i]; cp > &clist[0]; 
  1749.         cp = (CANDIDATE *)&cp->link) {
  1750.         if (++count >= 6) {
  1751.             printf("\n    ");
  1752.             count = 0;
  1753.         }
  1754.         printf(" (%2d: %2d,%2d -> %d)",
  1755.             cp-clist, cp->a, cp->b, cp->link);
  1756.       }
  1757.       printf("\n");
  1758.   }
  1759.   printf("*\n");
  1760. }
  1761. #endif
  1762. #ifdef  TIMING
  1763. ptime(why)
  1764. char      *why;
  1765. /*
  1766.  * Dump time buffer
  1767.  */
  1768. {
  1769.   long  ttemp;
  1770.  
  1771.   ttemp = time(NULL);
  1772.   printf("%ld seconds for %s\n",
  1773.       ttemp - sectiontime, why);
  1774.   sectiontime = ttemp;
  1775. }
  1776. #endif
  1777.  
  1778. /*
  1779.  *        s t r e q . c
  1780.  */
  1781.  
  1782. /*)LIBRARY
  1783. */
  1784.  
  1785. #ifdef  DOCUMENTATION
  1786.  
  1787. title  streq  String Equality Test
  1788. index      String equality test
  1789.  
  1790. synopsis
  1791.   .s.nf
  1792.   streq(a, b);
  1793.   char      *a;
  1794.   char      *b;
  1795.   .s.f
  1796. Description
  1797.  
  1798.   Return TRUE if the strings are equal.
  1799.  
  1800. Bugs
  1801.  
  1802. #endif
  1803.  
  1804. /* #define  EOS  0
  1805. #define  FALSE  0
  1806. #define  TRUE  1
  1807. */
  1808. int
  1809. streq(s1, s2)
  1810. register char  *s1;
  1811. register char  *s2;
  1812. /*
  1813.  * TRUE if strings are identical
  1814.  */
  1815. {
  1816.   while (*s1++ == *s2) {
  1817.       if (*s2++ == EOS)
  1818.       return (TRUE);
  1819.   }
  1820.   return (FALSE);
  1821. }
  1822. /*
  1823.  *        e r r o r . c
  1824.  */
  1825.  
  1826. /*)LIBRARY
  1827. */
  1828.  
  1829. #ifdef  DOCUMENTATION
  1830.  
  1831. title  error  Fatal Error Exit
  1832. index      Fatal error exit
  1833.  
  1834. synopsis
  1835.   .s.nf
  1836.   _error()
  1837.  
  1838.   error(format, args)
  1839.   char      *format;
  1840.   .s.f
  1841. documentation
  1842.  
  1843.   Fatal error exits.  _error() halts, error() prints something
  1844.   on stderr and then halts.
  1845.  
  1846. bugs
  1847.  
  1848.   THIS DOES NOT WORK ON MANY SYSTEMS DUE TO EXTREMLY NON-PORTABLE CODE.
  1849.   Why oh why can't people learn to use varargs properly?  This code will
  1850.   blow up on OSK.  Fortunatly, it isn't used often...
  1851.  
  1852. #endif
  1853.  
  1854. /* VARARGS */
  1855. error(format, args)
  1856. char      *format;
  1857. /*
  1858.  * Error message before retiring.
  1859.  */
  1860. {
  1861.   fprintf(stderr, format, &args);
  1862.   putc('\n', stderr);
  1863.   _error();
  1864. }
  1865.  
  1866. _error()
  1867. {
  1868.   exit(1);
  1869. }
  1870.  
  1871. /* #include  <stdio.h> */
  1872.   
  1873. fputss(s, iop)
  1874. register char *s;
  1875. register FILE *iop;
  1876. /*
  1877.  * Like fput() except that it puts a newline at the end of the line.
  1878.  */
  1879. {
  1880. #ifndef OSK
  1881. /*
  1882.  * Why wasn't this written like the OSK section?  What's the difference between
  1883.  * fputc and putc other than I've never heard of fputc?
  1884.  */
  1885.   register c;
  1886.  
  1887.   while (c = *s++)
  1888.     fputc(c, iop);
  1889.   fputc('\n', iop);
  1890. #else
  1891.   fputs(s, iop);
  1892.   putc('\n', iop);
  1893. #endif
  1894. }
  1895.  
  1896.  
  1897. /*
  1898.  * Fgetss() is like fgets() except that the terminating newline
  1899.  * is removed.
  1900.  */
  1901. char *fgetss(s, n, iop)
  1902. char *s;
  1903. register FILE *iop;
  1904. {
  1905.   register c;
  1906.   register char *cs;
  1907.   
  1908.   cs = s;
  1909.   /*
  1910.    * The getc in the next line used to be an "fgetc".  Change it back if
  1911.    * getc doesn't work on your system, though that would be odd.
  1912.    */
  1913.   while ((c = getc(iop))>=0 && --n>0) {
  1914.       if (c=='\n')
  1915.         break;
  1916.       *cs++ = c;
  1917.   }
  1918.   if (c<0 && cs==s)
  1919.       return((char *)NULL);
  1920.   *cs = '\0';        /* Overwrite newline as null  */
  1921.   return(s);
  1922. }
  1923.