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