home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / utility / diff / diff.mem < prev    next >
Encoding:
Text File  |  1988-07-20  |  9.5 KB  |  347 lines
  1.  
  2.  
  3. Jan 13 13:00 1988  CDIFF.MEM Page 1
  4.  
  5.  
  6.  
  7.      Diff maintains all information needed to compare the two files in
  8.      main memory. This means that very large files (or fairly large
  9.      files with many differences) will cause the program to abort with
  10.      an "out of space" error. Main memory requirements (in words) are
  11.      approximately:
  12.  
  13.       2 * (length of file1 + length of file2) + (3 * number of changes)
  14.  
  15.      The diff algorithm reads each file twice (once to build hash
  16.      tables and a second time to check for fortuitous matches), then
  17.      reads the differences by seeking randomly within the files. CPU
  18.      time requirements include sorting the two hash vectors and
  19.      randomly searching memory tables for equivalence classes. For
  20.      example, running in Vax compatibility mode, two 1000 line files
  21.      with a fair number of differences took about 25 seconds (elapsed
  22.      wall clock time) for processing. Most of this time was spent in
  23.      the file read routines. This test required slightly more than
  24.      6000 words of memory for internal tables.
  25.  
  26.      The diff algorithm was developed by J. W. Hunt and M. D. McIlroy,
  27.      using a central algorithm defined by H. S. Stone. The algorithm
  28.      was described in:
  29.  
  30.           Hunt, J. W., and McIlroy, M. D.,
  31.           An Algorithm for Differential File Comparison,
  32.           Computing Science Technical Report #41,
  33.           Bell Laboratories, Murray Hill, NJ  07974
  34.  
  35.      The following description is summarized from that document. While
  36.      it has been slightly modified to correspond to the program
  37.      source, the algorithm is essentially identical.
  38.  
  39.      1. Read the input files, building two vectors containing the line
  40.      number (serial) and hash value (hash) of each line. Data for
  41.      fileA will be in a vector pointed to by fi\eA[], while data for
  42.      fileB will be pointed to by fileB[]. The lengths (number of
  43.      lines) of the files will be represented by lenA and lenB
  44.      respectiveLy. [This is slightly different from the        + 3 * (number of changes)
  45.  
  46.           (Where "length" is the number of lines of data in each
  47.           file.)
  48.  
  49.           The algorithm reads each file twice, once to build hash
  50.           tables and once to check for fortuitous matches (two lines
  51.           that are in fact different, but which have the same hash
  52.           value). CPU time requirements include sorting the hash
  53.           tables and randomly searching memory tables for equivalence
  54.           classes. For example, on a time-shared VAX-11/780, comparing
  55.           two 1000 line files required about 30 seconds (elapsed clock
  56.           time) and about 10,000 bytes of working storage. About 90
  57.           per-cent of the time was taken up by file I/O.
  58.  
  59.      D✓D✓D✓DI✓I✓I✓IA✓A✓A✓AG✓G✓G✓GN✓N✓N✓NO✓O✓O✓OS✓S✓S✓ST✓T✓T✓TI✓I✓I✓IC✓C✓C✓CS✓S✓S✓S
  60.           Warning, bad option 'x'
  61.                The option is ignored.
  62.  
  63.  
  64.  
  65.      Page 1                                          (printed 1/13/88)
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.      C✓C✓C✓CD✓D✓D✓DI✓I✓I✓IF✓F✓F✓FF✓F✓F✓F(✓(✓(✓(1✓1✓1✓1)✓)✓)✓)                    U✓U✓U✓UN✓N✓N✓NI✓I✓I✓IX✓X✓X✓X 5✓5✓5✓5.✓.✓.✓.0✓0✓0✓0                     C✓C✓C✓CD✓D✓D✓DI✓I✓I✓IF✓F✓F✓FF✓F✓F✓F(✓(✓(✓(1✓1✓1✓1)✓)✓)✓)
  73.  
  74.  
  75.  
  76.           Usage ...
  77.                Two input files were not specified.
  78.  
  79.           Can't open input file "filename".
  80.                Can't continue.
  81.  
  82.           Out of space
  83.                The program ran out of memory while comparing the two
  84.                files.
  85.  
  86.           Can't read line nnn at xxx in file[A/B]
  87.                This indicates an I/O error when seeking to the
  88.                specific line.  It should not happen.
  89.  
  90.           Spurious match, output is not optimal.
  91.                Two lines that were different yielded the same hash
  92.                value.  This is harmless except that the difference
  93.                output is not the minimum set of differences between
  94.                the two files.  For example, instead of the output:
  95.                           lines 1 to 5 were changed to ...
  96.                the program will print
  97.                           lines 1 to 3 were changed to ...
  98.                           lines 4 to 5 were changed to ...
  99.  
  100.           The program uses a CRC16 hash code.
  101.                The likelihood of this error is quite small.
  102.  
  103.      A✓A✓A✓AU✓U✓U✓UT✓T✓T✓TH✓H✓H✓HO✓O✓O✓OR✓R✓R✓R
  104.           The diff algorithm was developed by J. W. Hunt and M. D.
  105.           McIlroy, using a central algorithm defined by H. S. Stone.
  106.           It was published in:
  107.                Hunt, J. W., and McIlroy, M. D.,
  108.                An Algorithm for Differential File Comparison,
  109.                Computing Science Technical Report #41,
  110.                Bell Laboratories, Murray Hill, NJ  07974
  111.  
  112.      B✓B✓B✓BU✓U✓U✓UG✓G✓G✓GS✓S✓S✓S
  113.           On RSX and DECUS C on VMS systems, diff may fail if the both
  114.           files are not "variable-length, implied carriage control"
  115.           format.  The scopy program can be used to convert files to
  116.           this format if problems arise.
  117.  
  118.           When compiled under VAX C, diff handles STREAM_LF files
  119.           properly (in addition to the canonical variable-length
  120.           implied carriage control files). Other variations should
  121.           work, but have not been tested.
  122.  
  123.           When compiled under VAX C, diff is quite slow for unknown
  124.           reasons which ought to be investigated. On the other hand,
  125.           it has access to effectively unlimited memory.
  126.  
  127.           Output in a form suitable for ed - the -e option - seems
  128.  
  129.  
  130.  
  131.      Page 2                                          (printed 1/13/88)
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.      C✓C✓C✓CD✓D✓D✓DI✓I✓I✓IF✓F✓F✓FF✓F✓F✓F(✓(✓(✓(1✓1✓1✓1)✓)✓)✓)                    U✓U✓U✓UN✓N✓N✓NI✓I✓I✓IX✓X✓X✓X 5✓5✓5✓5.✓.✓.✓.0✓0✓0✓0                     C✓C✓C✓CD✓D✓D✓DI✓I✓I✓IF✓F✓F✓FF✓F✓F✓F(✓(✓(✓(1✓1✓1✓1)✓)✓)✓)
  139.  
  140.  
  141.  
  142.           rather pointless; the analogue on DEC systems is SLP (SUMSLP
  143.           on VMS). It would be simple to provide SLP-compatible
  144.           output. The question is, why bother - since the various DEC
  145.           file comparisonFound 424 control chars in "diff.doc"
  146. utilities already produce it.
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.      Page 3                                          (printed 1/13/88)
  199.  
  200.  
  201.  
  202.   -1  -3  -5  -4
  203.  
  204.      After unsort() has unwound fileB:
  205.  
  206.      Class[] (1 .. lines in fileA):
  207.       3   4  0  5  0  1
  208.  
  209.      Within unravel(), match is built in the following order:
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217. Jan 13 13:00 1988  CDIFF.MEM Page 5
  218.  
  219.  
  220.  
  221.       match[6] := 6
  222.       match[4] := 5
  223.       match[2] := 3
  224.       match[1] := 1
  225.  
  226.      Match[] (0 .. lines in fileA):
  227.  
  228.        0  1  3  0  5  0  6
  229.  
  230.      Output is as follows:
  231.  
  232.       1a2
  233.       > line 1.5 inserted
  234.       3c4
  235.       < line 3
  236.       ---
  237.       > line 3 changed
  238.       5d5
  239.       < line 5 gets deleted
  240.  
  241. ********************************************************************
  242.  
  243. /*
  244.  *        s t r e q . c
  245.  */
  246.  
  247.  
  248. String Equality Test
  249. String equality test
  250.  
  251. Synopsis:
  252.   streq(a, b);
  253.   char      *a;
  254.   char      *b;
  255.  
  256. Description:
  257.  
  258.   Return TRUE if the strings are equal.
  259.  
  260. Bugs
  261.  
  262. ***************************************************************
  263.  
  264. /*
  265.  *        e r r o r . c
  266.  */
  267.  
  268.  
  269. Fatal Error Exit
  270.  
  271.     Synopsis:
  272.  
  273.       _error()
  274.  
  275.       error(format, args)
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282.  
  283. Jan 13 13:00 1988  CDIFF.MEM Page 6
  284.  
  285.  
  286.       char      *format;
  287.  
  288.     Documentation:
  289.  
  290.       Fatal error exits.  _error() halts, error() prints something
  291.       on stderr and then halts.
  292.  
  293.     Bugs:
  294.  
  295.       THIS DOES NOT WORK ON MANY SYSTEMS DUE TO EXTREMLY NON-PORTABLE CODE.
  296.       Why oh why can't people learn to use varargs properly?  This code will
  297.       blow up on OSK.  Fortunatly, it isn't used often...
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343.  
  344.  
  345.  
  346.  
  347.