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