home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 270_01 / diff.c < prev    next >
Encoding:
C/C++ Source or Header  |  1980-01-01  |  9.8 KB  |  448 lines
  1. /**
  2.  
  3.     DIFF.C
  4.     
  5.     File differencing program.
  6.     
  7.     The algorithm used here is the "recursive longest matching 
  8.     sequence" algorithm discussed in the 10/87 issue if DDJ.
  9.     Some code is borrowed from the accompanying article.
  10.  
  11. **/
  12.  
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <string.h>
  16. #include "diff.h"
  17.  
  18. static char szBuffer[MAXLINE] ;
  19.  
  20. /**
  21.  
  22.     Hash()
  23.     
  24.     Calculate a hash value for a string.  This value can be used
  25.     for a first level equality check for strings, thus eliminating
  26.     a time consuming strcmp() for each comparison.
  27.     
  28.     The hash value is a variation on the standard checksum hash, which
  29.     includes the length of the string in the high word of the int.
  30.  
  31. **/
  32.  
  33. static unsigned Hash( szPtr ) 
  34. char *szPtr ;
  35. {
  36.     unsigned chksum ;
  37.     char *s ;
  38.  
  39.     /*--- Compute checksum of string ---*/
  40.     for ( chksum = 0, s = szPtr ; *s ; chksum ^= *s++ )
  41.         ;
  42.  
  43.     /*--- return combined 7-bit checksum and length ---*/
  44.     return ( (chksum & 0xFF) | ((s - szPtr) << 8) ) ;
  45. }
  46.  
  47. /**
  48.  
  49.     ReadFile()
  50.     
  51.     Read a file into an array of LINEs.
  52.  
  53. **/
  54.  
  55. static LINE *ReadFile( pFile, nLines )
  56. FILE *pFile ;
  57. int *nLines ;
  58. {
  59.     LINE *pLine ;
  60.     int nSize ;
  61.  
  62.     /*--- allocate one page of lines ---*/
  63.     pLine = (LINE *)calloc( PAGESIZE, sizeof(LINE *) ) ;
  64.  
  65.     *nLines = 0 ;
  66.  
  67.     while (pLine != NULL) 
  68.     {
  69.         pLine[*nLines].addr = ftell( pFile ) ;
  70.         fgets( szBuffer, MAXLINE, pFile ) ;
  71.  
  72.         if ( feof(pFile) )
  73.             break ;
  74.  
  75.         pLine[*nLines].hash = Hash(szBuffer) ;
  76.         pLine[*nLines].linenum = *nLines + 1;
  77.         ++(*nLines) ;    
  78.  
  79.         /*--- check to see if page filled ---*/
  80.         if ( *nLines % PAGESIZE == 0 )
  81.         {
  82.             nSize = (*nLines + PAGESIZE) * sizeof(LINE *) ;
  83.             pLine = (LINE *)realloc(pLine, nSize) ;
  84.         }
  85.     }
  86.  
  87.     return pLine ;
  88. }
  89.  
  90. /**
  91.  
  92.     CheckHashes()
  93.     
  94.     Check to see if the next N hash codes match.  This function
  95.     assumes that the hash codes for the first compare match.
  96.     
  97.     Returns:
  98.         TRUE  if N or greater hash codes match
  99.         FALSE if less than N hash codes match
  100.  
  101. **/
  102.  
  103. static BOOL CheckHashes( pLine1, pLine2, nCount )
  104. LINE *pLine1,        /* Starting line in file 1 */
  105. *pLine2 ;        /* starting line in file 2 */
  106. int  nCount ;        /* minimum number of codes to match */
  107. {
  108.     int i ;
  109.  
  110.     for ( i = 0 ; i < nCount && (++pLine1)->hash == (++pLine2)->hash ; i++ )
  111.         ;
  112.  
  113.     return ( i < nCount ) ? FALSE : TRUE ;
  114. }
  115.  
  116. /**
  117.  
  118.     CheckStrings()
  119.  
  120.     This routine actually compares the strings associated with the
  121.     specified file lines.
  122.     
  123.     Returns:
  124.         A count of how many consecutive strings match
  125.         
  126. **/
  127.  
  128. static int CheckStrings( pFile1, pLine1, pFile2, pLine2, nMost )
  129. FILE *pFile1 ;        /* file 1 stream */
  130. LINE *pLine1 ;        /* line in file 1 */
  131. FILE *pFile2 ;        /* file 2 stream */
  132. LINE *pLine2 ;        /* line in file 2 */
  133. int  nMost ;        /* most possible matches */
  134. {
  135.     static char szBuf1[MAXLINE], szBuf2[MAXLINE] ;
  136.     int i ;
  137.  
  138.     /*--- seek to starting locations for strings ---*/
  139.     fseek( pFile1, pLine1->addr, SEEK_SET ) ;
  140.     fseek( pFile2, pLine2->addr, SEEK_SET ) ;
  141.  
  142.     for ( i = 0 ; i < nMost ; i ++ )
  143.     {
  144.         fgets( szBuf1, MAXLINE, pFile1 ) ;
  145.         fgets( szBuf2, MAXLINE, pFile2 ) ;
  146.  
  147.         if ( strcmp(szBuf1, szBuf2) )
  148.             break ;
  149.     }
  150.     return i ;
  151. }
  152.  
  153. /**
  154.  
  155.     PrintLines()
  156.     
  157.     Print a range of lines form a file 
  158.  
  159. **/
  160.  
  161. static void PrintLines( pFile1, pLine1, nLines1, pFile2, pLine2, nLines2 ) 
  162. FILE *pFile1 ;
  163. LINE *pLine1 ;
  164. int nLines1 ;
  165. FILE *pFile2 ;
  166. LINE *pLine2 ;
  167. int nLines2 ;
  168. {
  169.     BOOL bSeparator = FALSE ;
  170.     int nType ;
  171.     
  172.     if ( nLines1 > 0 && nLines2 > 0 )
  173.         nType = CHANGE ;
  174.     else if ( nLines1 > 0 )
  175.         nType = DELETE ;
  176.     else if ( nLines2 > 0 )
  177.         nType = ADD ;
  178.     
  179.     if ( nLines1 > 0 )
  180.         fseek( pFile1, pLine1->addr, SEEK_SET ) ;
  181.         
  182.     if ( nLines2 > 0 )
  183.         fseek( pFile2, pLine2->addr, SEEK_SET ) ;
  184.         
  185.     switch( nType )
  186.     {
  187.     case CHANGE:        /* change a range of lines */
  188.         if ( nLines1 > 1 )
  189.             printf( "%d,%d", pLine1->linenum, 
  190.                     pLine1->linenum+nLines1-1 ) ;
  191.         else
  192.             printf( "%d", pLine1->linenum ) ;
  193.  
  194.         if ( nLines2 > 1 )
  195.             printf( "c%d,%d\n", pLine2->linenum, 
  196.                     pLine2->linenum+nLines2-1 ) ;
  197.         else
  198.             printf( "c%d\n", pLine2->linenum ) ;
  199.  
  200.         bSeparator = TRUE ;
  201.         break ;
  202.     case DELETE:
  203.         if ( nLines1 > 1 )
  204.             printf( "%d,%d", pLine1->linenum, 
  205.                     pLine1->linenum+nLines1-1 ) ;    
  206.         else
  207.             printf( "%d", pLine1->linenum ) ;
  208.  
  209.         printf( "d%d\n", pLine2->linenum-1 ) ;
  210.         break ;
  211.     case ADD:
  212.         printf( "%d", pLine1->linenum-1 ) ;
  213.  
  214.         if ( nLines2 > 1 )
  215.             printf( "a%d,%d\n", pLine2->linenum, 
  216.                     pLine2->linenum+nLines2-1 ) ;    
  217.         else
  218.             printf( "a%d\n", pLine2->linenum ) ;
  219.         break ;
  220.     }
  221.  
  222.     /*--- print the line range(s) ---*/
  223.     while ( nLines1-- > 0 )
  224.     {
  225.         fgets( szBuffer, MAXLINE, pFile1 ) ;
  226.         printf( "< %s", szBuffer ) ;
  227.     }
  228.     if ( bSeparator ) 
  229.         printf("---\n" ) ;
  230.     while ( nLines2-- > 0 )
  231.     {
  232.         fgets( szBuffer, MAXLINE, pFile2 ) ;
  233.         printf( "> %s", szBuffer ) ;
  234.     }
  235. }
  236.  
  237. /**
  238.  
  239.     DoDiff()
  240.     
  241.     Difference two files using "recursive longest matching sequence"
  242.     algorithm.
  243.     
  244. **/
  245.  
  246. static void DoDiff( pFile1, pLine1, nMost1, pFile2, pLine2, nMost2, nLong )
  247. FILE *pFile1 ;        /* file 1 stream */
  248. LINE *pLine1 ;        /* start line in file 1 */
  249. int  nMost1 ;        /* Max lines in file 1 */
  250. FILE *pFile2 ;        /* file 2 stream */
  251. LINE *pLine2 ;        /* start line in file 1 */
  252. int  nMost2 ;        /* Max lines in file 1 */
  253. int  nLong ;        /* 'long enough' match value */
  254. {
  255.     int nMostSoFar = 0,    /* longest sequence so far */
  256.     nLongest = 0,        /* longest possible sequence */
  257.     nLines = 0,        /* Lines in current match */
  258.     nLongStart1 = 0,    /* start of longest sequence in file 1 */
  259.     nLongStart2 = 0,    /* start of longest sequence in file 2 */
  260.     nLong1 = 0,        /* length of longest possible in file 1 */
  261.     nLong2 = 0,        /* length of longest possible in file 2 */
  262.     nStart1 = 0,        /* starting line for recursion in file 1 */
  263.     nStart2 = 0 ;        /* starting line for recursion in file 2 */
  264.     int i, j ;
  265.     
  266.  
  267.     for ( i = 0 ; i < nMost1 ; i ++ )
  268.     {
  269.         for ( j = 0 ; j < nMost2 ; j ++ )
  270.         {
  271.             if ( pLine1[i].hash == pLine2[j].hash )
  272.                 if ( CheckHashes( pLine1+i, pLine2+j, 
  273.                             nMostSoFar) )
  274.                 {
  275.                     /* count this sequence */
  276.                     nLongest = min( nMost1 -i, nMost2 -j );
  277.                     nLines = CheckStrings( pFile1, pLine1+i,
  278.                                 pFile2, pLine2+j,
  279.                                 nLongest ) ;
  280.                     if ( nLines > nMostSoFar )
  281.                     {
  282.                         nLongStart1 = i ;
  283.                         nLongStart2 = j ;
  284.                         nMostSoFar = nLines ;
  285.                     }
  286.  
  287.                     if ( nMostSoFar > nLong )
  288.                     {
  289.                         /*
  290.                            recurse using all lines
  291.                            below the matching set
  292.                            of lines.
  293.                         */
  294.                         nLong1 = nLongStart1 ;
  295.                         nLong2 = nLongStart2 ;
  296.                         if ( nLong1 > 0 && nLong2 > 0 )
  297.                             DoDiff( pFile1,
  298.                                 pLine1,
  299.                                 nLong1,
  300.                                 pFile2,
  301.                                 pLine2,
  302.                                 nLong2,
  303.                                 nLong );
  304.                         else if ( nLong1>0 || nLong2>0)
  305.                             PrintLines( pFile1,
  306.                                     pLine1,
  307.                                     nLong1,
  308.                                     pFile2,
  309.                                     pLine2,
  310.                                     nLong2 ) ;
  311.  
  312.                         /*
  313.                            recurse using all lines
  314.                            above the matching set
  315.                            of lines.
  316.                         */
  317.                         nStart1=nLongStart1+nMostSoFar;
  318.                         nStart2=nLongStart2+nMostSoFar;
  319.                         nLong1=nMost1-nStart1;
  320.                         nLong2=nMost2-nStart2;
  321.                         if ( nLong1 > 0 && nLong2 > 0 )
  322.                             DoDiff( pFile1,
  323.                                 pLine1+nStart1,
  324.                                 nLong1,
  325.                                 pFile2,
  326.                                 pLine2+nStart2,
  327.                                 nLong2,
  328.                                 nLong );
  329.                         else if ( nLong1>0 || nLong2>0)
  330.                             PrintLines( pFile1,
  331.                                     pLine1+nStart1,
  332.                                     nLong1,
  333.                                     pFile2,
  334.                                     pLine2+nStart2,
  335.                                     nLong2 ) ;
  336.  
  337.                         return ;
  338.                     }
  339.                 }
  340.         }
  341.     }
  342.     /* 
  343.        At this point, we have searched the entire range and
  344.        have the longest range of matches specified as starting
  345.        at line nLongestStartX and nMostSoFar lines long.
  346.     */
  347.  
  348.     if ( nMostSoFar > 0 )        /* any matches? */
  349.     {
  350.         /*
  351.            recurse using all lines
  352.            below the matching set
  353.            of lines.
  354.         */
  355.         nLong1 = nLongStart1 ;
  356.         nLong2 = nLongStart2 ;
  357.         if ( nLong1 > 0 && nLong2 > 0 )
  358.             DoDiff( pFile1,    pLine1,    nLong1,    
  359.                 pFile2,    pLine2,    nLong2, nLong );
  360.         else if ( nLong1 > 0 || nLong2 > 0)
  361.             PrintLines( pFile1, pLine1, nLong1,
  362.                     pFile2, pLine2, nLong2 ) ;
  363.  
  364.         /*
  365.            recurse using all lines
  366.            above the matching set
  367.            of lines.
  368.         */
  369.         nStart1=nLongStart1+nMostSoFar;
  370.         nStart2=nLongStart2+nMostSoFar;
  371.         nLong1=nMost1-nStart1;
  372.         nLong2=nMost2-nStart2;
  373.         if ( nLong1 > 0 && nLong2 > 0 )
  374.             DoDiff( pFile1,    pLine1+nStart1, nLong1,    
  375.                 pFile2,    pLine2+nStart2, nLong2, nLong );
  376.         else if ( nLong1 > 0 || nLong2 > 0)
  377.             PrintLines( pFile1, pLine1+nStart1, nLong1,
  378.                     pFile2, pLine2+nStart2, nLong2 ) ;
  379.     }
  380.     else        /* no match, this is a difference */
  381.         PrintLines( pFile1, pLine1, nMost1, pFile2, pLine2, nMost2 ) ;
  382. }
  383.  
  384. /**
  385.  
  386.     Banner()
  387.     
  388.     Print a startup banner
  389.     
  390. **/
  391.  
  392. static void banner()
  393. {
  394.     fprintf( stderr, "DIFF - File Difference Report Generator\n" ) ;
  395.     fprintf( stderr, "By Ralph E. Brendler\n\n" ) ;
  396. }
  397.     
  398.  
  399. /**
  400.  
  401.     MAIN ROUTINE
  402.     
  403. **/
  404.  
  405. void main( argc, argv )
  406. int argc ;
  407. char *argv[] ;
  408. {
  409.     FILE *pFile1, *pFile2 ;
  410.     LINE *pLine1, *pLine2 ;
  411.     int  nLine1, nLine2 ;
  412.  
  413.     if ( argc != 3 )
  414.     {
  415.         fprintf( stderr, "Usage: DIFF file1 file2\n" ) ;
  416.         exit(1) ;
  417.     }
  418.     
  419.     banner() ;        /* print startup banner */
  420.  
  421.     if ( (pFile1 = fopen(argv[1],"rt")) == NULL )
  422.     {
  423.         fprintf( stderr, "Unable to open %s\n", argv[1] ) ;
  424.         exit(1) ;
  425.     }
  426.  
  427.     if ( (pFile2 = fopen(argv[2],"rt")) == NULL )
  428.     {
  429.         fprintf( stderr, "Unable to open %s\n", argv[2] ) ;
  430.         exit(1) ;
  431.     }
  432.  
  433.     if ( (pLine1 = ReadFile(pFile1, &nLine1)) == NULL )
  434.     {
  435.         fprintf( stderr, "Out of memory\n" ) ;
  436.         exit(1) ;
  437.     }
  438.  
  439.     if ( (pLine2 = ReadFile(pFile2, &nLine2)) == NULL )
  440.     {
  441.         fprintf( stderr, "Out of memory\n" ) ;
  442.         exit(1) ;
  443.     }
  444.  
  445.     DoDiff( pFile1, pLine1, nLine1, pFile2, pLine2, nLine2, 25 ) ;
  446. }
  447.  
  448.