home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 355_03 / slk3.exe / SDIF / SDIF.C < prev   
C/C++ Source or Header  |  1991-06-09  |  14KB  |  656 lines
  1. /*
  2.     Sherlock File Comparison Program.
  3.  
  4.     source:  sdif.c
  5.     started: February 11, 1988
  6.     version: see below
  7.  
  8.  
  9.     PUBLIC DOMAIN SOFTWARE
  10.  
  11.     Sherlock, including the SPP, SDEL and SDIF programs, was placed in
  12.     the public domain on June 15, 1991, by its author,
  13.  
  14.         Edward K. Ream
  15.         166 North Prospect Ave.
  16.         Madison, WI 53705.
  17.         (608) 257-0802
  18.  
  19.     Sherlock may be used for any commercial or non-commercial purpose.
  20.  
  21.  
  22.     DISCLAIMER OF WARRANTIES
  23.  
  24.     Edward K. Ream (Ream) specifically disclaims all warranties,
  25.     expressed or implied, with respect to this computer software,
  26.     including but not limited to implied warranties of merchantability
  27.     and fitness for a particular purpose.  In no event shall Ream be
  28.     liable for any loss of profit or any commercial damage, including
  29.     but not limited to special, incidental consequential or other damages.
  30. */
  31.  
  32. /*
  33.     Define the compiler to be used (usually from the command line.)
  34.  
  35.     MICRO_SOFT    Use MicroSoft v4.00
  36.     TURBOC        Use Turbo C v1.0
  37. */
  38.  
  39. /*
  40.     Miscellaneous global constants.
  41. */
  42. #define TRUE    (1)
  43. #define FALSE    (0)
  44. #define BAD_EXIT 1
  45. typedef int    bool;
  46.  
  47. /*
  48.     Include subsidiary header files.
  49.  
  50.     SL.H MUST be included even if SHERLOCK.C is not linked in.
  51. */
  52. #include <stdio.h>
  53. #include <stdlib.h>
  54. #include <ctype.h>
  55. #include <string.h>
  56. #include <process.h>
  57. #include <io.h>
  58. #include "sl.h"
  59.  
  60. #define SIGNON "SDIF v1.7: June 15, 1991"
  61.  
  62. #ifdef SHERLOCK
  63. #define USAGE1\
  64. "usage: SDIF in1(with macros) in2(without) [options] ++/--tracepoint\n\n"
  65. #else
  66. #define USAGE1\
  67. "usage: SDIF in1(with macros) in2(without) [options]\n\n"
  68. #endif
  69.  
  70. #define USAGE2 "-b    Report inserted blank lines.\n"
  71. #define USAGE3 "-s    Report detailed status of comparison.\n"
  72. #define USAGE4 "-v    List all lines of in1 file.\n"
  73. #define USAGE5 "-?    Print version number and exit.\n"
  74.  
  75.  
  76. /*
  77.     There are two windows, one for each file.  Each window holds up to
  78.     WINDOW_LINES lines and up to WINDOW_CHARS characters.  These windows
  79.     are used to do "look-ahead" comparisons of lines.
  80.  
  81.     Lines are inserted from the back of the window buffers and deleted from
  82.     the front.  When the back of the window buffer can not hold the next 
  83.     line, the non-deleted lines are moved to the front of the buffer.  The
  84.     window buffer is made much larger than required    lines so this moving of
  85.     lines in the window buffer doesn't happen often.
  86.  
  87.     We expect an average line size of less than 40, so that WINDOW_LINES
  88.     lines will take about 160 characters.  Thus, the window will have to be 
  89.     repacked about once in every 100 inserted lines.  This will not
  90.     slow down the program in any way.
  91. */
  92. #define WINDOW_LINES    20
  93. #define WINDOW_CHARS    7000
  94.  
  95. /* Global flags. */
  96. bool b_flag = FALSE;
  97. bool v_flag = FALSE;
  98. bool s_flag = FALSE;
  99.  
  100. /* Define the windows. */
  101. typedef struct {
  102.     FILE *  file;        /* File handle.            */
  103.     bool    eof;        /* End of file flag.        */
  104.     int    line;        /* Current line number.        */
  105.     int    nlines;        /* # of lines in window.    */
  106.     int    index[WINDOW_LINES];    /* Indices into window.    */
  107.     char    window[WINDOW_CHARS];    /* Chars of window.    */
  108.     int    first;        /* Index of first character.    */
  109.     int    last;        /* Index of last character+1.    */
  110. } w_type;
  111.  
  112. w_type w1, w2;
  113.  
  114. /* Global file names. */
  115. char *in1 = NULL;
  116. char *in2 = NULL;
  117.  
  118. /*
  119.     Function prototypes.
  120. */
  121. void    advance        (w_type *wp);
  122. bool    fill_buf    (char * buffer, w_type *wp);
  123. void    insert        (w_type *wp);
  124. void    print_change    (int n);
  125. void    print_insert    (int n1, int n2);
  126. void    print_match    (void);
  127. bool    resynch        (int n1, int n2);
  128. void    sdif        (void);
  129.  
  130. /* Main routine.  Process command line arguments. */
  131. int
  132. main(int argc, char **argv)
  133. {
  134.     char *arg;
  135.     int i;
  136.  
  137.     /* These two calls MUST come before any others. */
  138.     SL_INIT();
  139.     SL_PARSE(argc, argv, "++", "--");
  140.  
  141.     TRACEPB("main", printf("(%d, %p)\n", argc, argv));
  142.  
  143.     /* Always put out the sign on message. */
  144.     printf("%s\n", SIGNON);
  145.  
  146.     /* Make first test for correct command line. */
  147.     if (argc == 2 && (strcmp(argv[1], "-?")==0)) {
  148.         exit(BAD_EXIT);
  149.     }
  150.     else if (argc < 3) {
  151.         printf("%s%s%s%s%s", USAGE1, USAGE2, USAGE3, USAGE4, USAGE5);
  152.         exit(BAD_EXIT);
  153.     }
  154.  
  155.     /* Process all the arguments on the command line. */
  156.     argc--;
  157.     argv++;
  158.     while (argc-- > 0) {
  159.         arg = *argv++;
  160.  
  161.         if (strcmp(arg, "-b")==0) {
  162.             b_flag = TRUE;
  163.         }
  164.         else if (strcmp(arg, "-s")==0) {
  165.             s_flag = TRUE;
  166.         }
  167.         else if (strcmp(arg, "-v")==0) {
  168.             v_flag = TRUE;
  169.         }
  170.         else if (strcmp(arg, "-?")==0) {
  171.             /* Ignore it. */
  172.             ;
  173.         }
  174.         else if (in1 == NULL) {
  175.             in1 = arg;
  176.         }
  177.         else if (in2 == NULL) {
  178.             in2 = arg;
  179.         }
  180.         else {
  181.             printf("Extra file argument: %s\n", arg);
  182.             exit(BAD_EXIT);
  183.         }
  184.     }
  185.  
  186.     /* Open the input files. */
  187.     w1.file = fopen(in1, "r");
  188.     if (w1.file == NULL) {
  189.         printf("Can not open %s\n", in1);
  190.         exit(BAD_EXIT);
  191.     }
  192.     w2.file = fopen(in2, "r");
  193.     if (w2.file == NULL) {
  194.         printf("Can not open %s\n", in2);
  195.         fclose(w2.file);
  196.         exit(BAD_EXIT);
  197.     }
  198.  
  199.     /* Initialize the windows. */
  200.     w1.line = 1;
  201.     w2.line = 1;
  202.     w1.eof  = FALSE;
  203.     w2.eof  = FALSE;
  204.     w1.nlines = 0;
  205.     w2.nlines = 0;
  206.     w1.first  = 0;
  207.     w2.first  = 0;
  208.     w1.last   = 0;
  209.     w2.last   = 0;
  210.     for (i = 0; i < WINDOW_LINES; i++) {
  211.         w1.index[i] = 0;
  212.         w2.index[i] = 0;
  213.     }
  214.  
  215.     /* Compare the two files and print out differences. */
  216.     sdif();
  217.  
  218.     /* Close the files. */
  219.     fclose(w1.file);
  220.     fclose(w2.file);
  221.  
  222.     /* Print out statistics. */
  223.     TRACE("dump", SL_DUMP());
  224.  
  225.     RETURN_VOID("main");
  226. }
  227.  
  228. /*
  229.     Compare two files line by line.
  230.     Print lines that do not match.
  231.     Assume that file 1 contains any inserted lines.
  232. */
  233. void
  234. sdif(void)
  235. {
  236.     int i, j;
  237.  
  238.     TICKB("sdif");
  239.  
  240.     /* Fill up the window buffers. */
  241.     for (i = 0; i < WINDOW_LINES; i++) {
  242.         insert(&w1);
  243.         insert(&w2);
  244.     }
  245.  
  246. loop:
  247.     if (w1.nlines == 0 && w2.nlines == 0) {
  248.         RETURN_VOID("sdif");
  249.     }
  250.     else if (w1.nlines == 0 && w2.nlines >= 10) {
  251.         printf("\nFile %s ends before file %s\n", in1, in2);
  252.         RETURN_VOID("sdif");
  253.     }
  254.     else if (w2.nlines == 0 && w1.nlines >= 10) {
  255.         printf("\nFile %s ends before file %s\n", in2, in1);
  256.         RETURN_VOID("sdif");
  257.     }
  258.  
  259.     if(compare(0, 0)) {
  260.         /* Lines match. */
  261.         print_match();
  262.         advance(&w1);
  263.         advance(&w2);
  264.         goto loop;
  265.     }
  266.  
  267.     /* Look for some changed or inserted lines. */
  268.     for (i = 1; i < WINDOW_LINES; i++) {
  269.         /* 3/9/89: don't resynch on duplicated lines. */
  270.         if (resynch(i, i) && !compare(i, i+1)) {
  271.             if (s_flag) {
  272.                 printf("----- %d changed lines\n", i);
  273.             }
  274.             for (j = 0; j < i; j++) {
  275.                 print_change(j);
  276.             }
  277.             for (j = 0; j < i; j++) {
  278.                 advance(&w1);
  279.                 advance(&w2);
  280.             }
  281.             goto loop;
  282.         }
  283.  
  284.         if (resynch(i, 0)) {
  285.             if (s_flag) {
  286.                 printf("----- %d inserted lines\n", i);
  287.             }
  288.             for (j = 0; j < i; j++) {
  289.                 print_insert(j, -1);
  290.             }
  291.             for (j = 0; j < i; j++) {
  292.                 advance(&w1);
  293.             }
  294.             goto loop;
  295.         }
  296.     }
  297.  
  298.     /*
  299.         Look for lines inserted in file 2.
  300.         This can happen as a result of previous erroneous advances.
  301.     */
  302.     for (i = 1; i < WINDOW_LINES; i++) {
  303.         if (resynch(0, i)) {
  304.             if (s_flag) {
  305.                 printf("----- %d back inserted lines\n", i);
  306.             }
  307.             for (j = 0; j < i; j++) {
  308.                 print_insert(-1, j);
  309.             }
  310.             for (j = 0; j < i; j++) {
  311.                 advance(&w2);
  312.             }
  313.             goto loop;
  314.         }
  315.     }
  316.  
  317.     /*
  318.         We haven't identified either a single group of insertions or
  319.         a single group of changed lines.  We have probably just seen
  320.         a combination of changes and insertions.  Just advance both
  321.         files one line each.  We'll get back in synch quickly.
  322.     */
  323.  
  324.     if (s_flag) {
  325.         printf("----- failure advance\n");
  326.     }
  327.     if (w1.nlines) {
  328.         print_insert(0, -1);
  329.     }
  330.     else {
  331.         print_insert(-1, 0);
  332.     }
  333.     advance(&w1);
  334.     advance(&w2);
  335.     goto loop;
  336. }
  337.  
  338. /*
  339.     Advance one line in the indicated window.
  340.     This frees up space at the beginning of the window buffer.
  341. */
  342. void
  343. advance(w_type *wp)
  344. {
  345.     int freed;
  346.     int i;
  347.     int lines;
  348.  
  349.     TRACEPB("advance", printf("(%p)\n", wp));
  350.  
  351.     lines = wp -> nlines;
  352.     if (lines == 0) {
  353.         RETURN_VOID("advance");
  354.     }
  355.     freed = strlen(&wp->window[wp->index[0]])+1;
  356.  
  357.     wp -> first += freed;
  358.     lines--;
  359.     for (i = 0; i < lines; i++) {
  360.         wp -> index[i] = wp -> index[i+1];
  361.     }
  362.     wp -> nlines--;
  363.     wp -> line++;
  364.  
  365.     /* Refill the buffer. */
  366.     if (wp -> nlines == WINDOW_LINES-1) {
  367.         insert(wp);
  368.     }
  369.  
  370.     TICKX("advance");
  371. }
  372.  
  373.  
  374. /*
  375.     Return TRUE if the indicated lines match.
  376. */
  377. bool
  378. compare(int n1, int n2)
  379. {
  380.     char *p1, *p2;
  381.     int i;
  382.  
  383.     TRACEPB("compare", printf("(%d, %d)\n", n1, n2));
  384.  
  385.     if (n1 >= w1.nlines || n2 >= w2.nlines) {
  386.  
  387.         RETURN_BOOL("compare", FALSE);
  388.     }
  389.     else {
  390.         p1 = &w1.window[w1.index[n1]];
  391.         p2 = &w2.window[w2.index[n2]];
  392.  
  393.         RETURN_BOOL("compare", strcmp(p1, p2) == 0);
  394.     }
  395. }
  396.  
  397. /*
  398.     Fill a buffer from a file.
  399.     Set the end of file flag if appropriate.
  400. */
  401. bool
  402. fill_buf(char *buffer, w_type *wp)
  403. {
  404.     int c;
  405.     int i;
  406.  
  407.     TRACEPB("fill_buf", printf("(%p, %p)\n", buffer, wp));
  408.  
  409.     if (wp -> eof) {
  410.         RETURN_BOOL("fill_buf", FALSE);
  411.     }
  412.     else {
  413.         for (i = 0;;) {
  414.             c = fgetc(wp -> file);
  415.             if (c == '\r') {
  416.                 continue;
  417.             }
  418.             if (c == EOF) {
  419.                 wp -> eof = TRUE;
  420.  
  421.                 if (i == 0) {
  422.                     RETURN_BOOL("fill_buf", FALSE);
  423.                 }
  424.                 break;
  425.             }
  426.             else if (c == '\n') {
  427.                 buffer[i++] = c;
  428.                 break;
  429.             }
  430.             else {
  431.                 buffer[i++] = c;
  432.             }
  433.         }
  434.     }
  435.     buffer[i] = '\0';
  436.  
  437.     RETURN_BOOL("fill_buf", TRUE);
  438. }
  439.  
  440. /*
  441.     Insert a line at the end of the window.
  442.     Pack the buffer if required.
  443. */
  444. void
  445. insert(w_type *wp)
  446. {
  447.     char buffer [1000];
  448.     int size, avail;
  449.     int i, p, q;
  450.  
  451.     TRACEPB("insert", printf("(%p)\n", wp));
  452.  
  453.     if (!fill_buf(buffer, wp)) {
  454.         RETURN_VOID("insert");
  455.     }
  456.     size = strlen(buffer)+1;
  457.     avail = WINDOW_CHARS - wp -> last;
  458.  
  459.     if (wp -> nlines >= WINDOW_LINES) {
  460.         printf("insert: too many lines.\n");
  461.         RETURN_VOID("insert");
  462.     }
  463.  
  464.     /* Compact buffer. */
  465.     if (size >= avail) {
  466.         /* Adjust indices. */
  467.         for (i = 0; i < wp -> nlines; i++) {
  468.             wp -> index[i] -= wp -> first;
  469.         }
  470.         /* Move the characters in the buffer. */
  471.         for (p = wp -> first, q = 0; p < wp -> last; p++, q++) {
  472.             wp -> window[q] = wp -> window[p];
  473.         }
  474.         /* Adjust counts. */
  475.         wp -> last -= wp -> first;
  476.         avail      += wp -> first;
  477.         wp -> first = 0;
  478.     }
  479.  
  480.     /* Insert the buffer at the end of the window. */
  481.     if (size < avail) {
  482.         strcpy(&wp -> window[wp -> last], buffer);
  483.         wp -> index[wp -> nlines] = wp -> last;
  484.         wp -> last += size;
  485.         wp -> nlines++;
  486.     }
  487.     else {
  488.         printf("not enough room in window!!\n");
  489.         exit(BAD_EXIT);
  490.     }
  491.  
  492.     TICKX("insert");
  493. }
  494.  
  495. /*
  496.     Print a changed line (from file 1).
  497. */
  498. void
  499. print_change(int n)
  500. {
  501.     int i;
  502.     char *p, *p1, *p2;
  503.  
  504.     TRACEPB("print_change", printf("(%d)\n", n));
  505.  
  506.     p1 = &w1.window[w1.index[n]];
  507.     p2 = &w2.window[w2.index[n]];
  508.     p = p1;
  509.  
  510.     /* Do not print mismatches that involve only white space. */
  511.     if (!b_flag && !v_flag) {
  512.         while (*p1) {
  513.             if (*p1 != ' ' && *p1 != '\t' && *p1 != '\n') {
  514.                 goto print;
  515.             }
  516.             p1++;
  517.         }
  518.         while (*p2) {
  519.             if (*p2 != ' ' && *p2 != '\t' && *p2 != '\n') {
  520.                 goto print;
  521.             }
  522.             p2++;
  523.         }
  524.         RETURN_VOID("print_change");
  525.     }
  526.  
  527. print:
  528.     if (v_flag) {
  529.         printf("%3d %3d* %s", w1.line+n, w2.line+n, p);
  530.     }
  531.     else {
  532.         printf("%3d %3d: %s", w1.line+n, w2.line+n, p);
  533.     }
  534.  
  535.     TICKX("print_change");
  536. }
  537.  
  538. /*
  539.     Print an inserted line.
  540.     The line comes from in1 if n1 >0, or from n2 if n2 > 0.
  541. */
  542. void
  543. print_insert(int n1, int n2)
  544. {
  545.     char *p;
  546.  
  547.     TRACEPB("print_insert", printf("(%d, %d)\n", n1, n2));
  548.  
  549.     /* Do not print blank lines. */
  550.     if (!b_flag && !v_flag && n1 >= 0) {
  551.         p = &w1.window[w1.index[n1]];
  552.         while (*p) {
  553.             if (*p != ' ' && *p != '\t' && *p != '\n') {
  554.                 goto print;
  555.             }
  556.             p++;
  557.         }
  558.         RETURN_VOID("print_insert");
  559.     }
  560.     else if (!b_flag && !v_flag && n2 >= 0) {
  561.         p = &w2.window[w2.index[n2]];
  562.         while (*p) {
  563.             if (*p != ' ' && *p != '\t' && *p != '\n') {
  564.                 goto print;
  565.             }
  566.             p++;
  567.         }
  568.         RETURN_VOID("print_insert");
  569.     }
  570.  
  571. print:
  572.     if (n1 >= 0) {
  573.         p = &w1.window[w1.index[n1]];
  574.         printf("%3d %3s: %s", w1.line+n1, " ", p);
  575.  
  576.         /* -----
  577.         if (v_flag || n1 > 0) {
  578.             printf("%3d %3s: %s", w1.line+n1, " ", p);
  579.         }
  580.         else {
  581.             printf("%3d %3d: %s", w1.line+n1, w2.line+n1, p);
  582.         }
  583.         ----- */
  584.     }
  585.     else {
  586.         p = &w2.window[w2.index[n2]];
  587.         printf("%3s %3d: %s", " ", w2.line+n2, p);
  588.  
  589.         /* -----
  590.         if (v_flag || n2 > 0) {
  591.             printf("%3s %3d: %s", " ", w2.line+n2, p);
  592.         }
  593.         else {
  594.             printf("%3d %3d: %s", w1.line+n2, w2.line+n2, p);
  595.         }
  596.         ----- */
  597.     }
  598.  
  599.     TICKX("print_insert");
  600. }
  601.  
  602. /*
  603.     Print a matched line if the -v option was given.
  604. */
  605. void
  606. print_match(void)
  607. {
  608.     TICKB("print_match");
  609.  
  610.     if (v_flag) {
  611.         printf("%3d %3d: %s",
  612.             w1.line, w2.line, &w1.window[w1.index[0]]);
  613.     }
  614.  
  615.     TICKX("print_match");
  616. }
  617.  
  618. /*
  619.     Return TRUE if the indicated lines match and can be used to
  620.     resynchronize the files.
  621. */
  622. bool
  623. resynch(int n1, int n2)
  624. {
  625.     char *p;
  626.     int count;
  627.  
  628.     TRACEPB("resynch", printf("(%d, %d)\n", n1, n2));
  629.  
  630.     if (!compare(n1, n2)) {
  631.         RETURN_BOOL("resynch", FALSE);
  632.     }
  633.  
  634.     p = &w1.window[w1.index[n1]];
  635.  
  636.     /* Make sure we have a non-trivial resynch point. */
  637.     count = 0;
  638.     while (*p) {
  639.         if (*p != ' ' && *p != '\t' && *p != '\n') {
  640.             count++;
  641.         }
  642.         p++;
  643.     }
  644.  
  645.     if (    count >= 1 ||
  646.         (w1.eof && w2.eof && n1 == w1.nlines-1 && n2 == w2.nlines-1)
  647.        ) {
  648.         /* Non-trivial matched lines or match to end of file. */
  649.         RETURN_BOOL("resynch", TRUE);
  650.     }
  651.     else {
  652.         /* Trivial matched lines.  Look ahead for an answer. */
  653.         RETURN_BOOL("resynch", resynch(n1+1, n2+1));
  654.     }
  655. }    
  656.