/*---------------------------------------------------------------------------- diff.c -- file compare and change bar inserter for text files originally produced by D Krantz, modified for Turbo C by P van Es date 4/19/88 5/2/88 v1.1 options have been UNIX-fied 5/4/88 v1.2 comparisons made faster bugs corrected upper case handling rationalised 6/14/88 v2.0 automatic resync feature added 6/18/88 v2.1 screen listing switchable 6/20/88 v2.2 resync made faster for small changes 6/21/88 v2.3 resync checksum lookup added 11/23/88 v2.4 change checksum to crc. add absolute line counter. increase text line size to 255 from 83. add -i maximum comparison column. when file 1 reaches EOF, now shows remaining lines in file 2. ---------------------------------------------------------------------------*/ /* file difference utility */ #if !defined (__COMPACT__) #error Must be compiled with COMPACT model #endif #include #include #include /* exit */ #include /* strcmp, stricmp, strcpy */ #include /* malloc, free, atoi */ typedef unsigned char byte; #define OPT_FLAG '-' /* command line switch recogniser */ #define MAXLINE 255 /* maximum input line characters */ #define FORMFEED 'L'-'@' #define EOF_REACHED 0 /* eof during resync */ #define RE_SYNCED 1 /* we managed to re-sync */ #define NO_SYNC 2 /* no sync but no eof either */ struct LINE /* structure defining line internally */ { int lineanum; /* what line in file */ int linenum; /* what line on page */ int pagenum; /* what page */ byte crc; /* use crc for quick comparison */ struct LINE *prev; /* pointer to previous line */ struct LINE *link; /* linked list pointer */ struct LINE *same; /* pointer to next line with crc */ char text[MAXLINE]; /* text of line */ }; typedef struct LINE *line_ptr; typedef FILE *FILE_PTR; struct LINE root[3]; /* root of internal linked list */ int linea_count[3] = {1,1,1}; /* file's absolute line counter */ int line_count[3] = {1,1,1}; /* file's line counter */ int page_count[3] = {1,1,1}; /* file's page counter */ int command_errors = 0; /* number of command line errors */ char xx1[132], /* space for file names */ xx2[132]; int files = 0; /* nr of files in command line */ char *infile_name[3] = {NULL,xx1,xx2}; char outfile_name[132]; /* output file name */ FILE_PTR infile[3]; /* input file pointers */ FILE *outfile; /* changebarred output file ptr */ static line_ptr at[3] = {NULL, &(root[1]), &(root[2])}; static line_ptr same_crc[256][2]; int debug = 0; /* trace switch */ int trace_enabled = 0; /* keyboard tracing switch */ int bar_col = 78; /* column for change bar */ int right_col = 80; /* maximum column to compare up to */ int top_skip = 0; /* lines to skip at top of page */ int bot_skip = 0; /* lines to skip at bottom of page */ int page_len = 66; /* length of a page */ int up_case = 0; /* boolean - ignore case */ int re_sync = 3; /* lines that must match for resync */ int output = 0; /* boolean - change barred outfile on */ int blanks = 0; /* boolean - blank lines significant */ int skip1 = 0; /* pages in first file to skip */ int skip2 = 0; /* pages in second file to skip */ int scr_on = 1; /* screen listing turned on */ static int crctab[] = /* CRC lookup table */ { 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241, 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440, 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40, 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841, 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40, 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41, 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641, 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040, 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240, 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441, 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41, 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840, 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41, 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40, 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640, 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041, 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240, 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441, 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41, 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840, 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41, 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40, 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640, 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041, 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241, 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440, 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40, 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841, 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40, 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41, 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641, 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040 }; #if 0 /* trace & other debug functions off */ #include /* kbhit, getch */ #include /* coreleft */ #define trace( x ) callstack( x ) #define ret { callpop(); return; } #define ret_val( x ) { callpop(); return( x ); } #define TRACER_FUNCTIONS #else #define trace( x ) /* nothing */ #define ret { return; } #define ret_val( x ) { return( x ); } #endif /*--------------------------------------------------------------------------*/ #ifdef TRACER_FUNCTIONS char *names[20]; int stack = 0; int callstack( char *str ) { int i; names[stack++] = str; if( debug ) { for( i = 0; i < stack; i++ ) printf( " " ); printf( "Entering %s\n", str ); } if( trace_enabled && kbhit() ) { switch( getch() ) { case 't': case 'T': debug = !debug; break; case 's': case 'S': printf( "\n------------" ); for( i = stack - 1; i >= 0; i-- ) printf( "\n%s", names[i] ); printf( "\n------------\n" ); printf( "free: %lu\n", coreleft() ); break; default: break; } } return; } int callpop( void ) { int i; if( debug ) { for( i = 0; i < stack; i++ ) printf( " " ); printf( "Exiting %s\n", names[stack - 1] ); } stack--; return; } void printentry( line_ptr lp, char *title ) { if( debug ) { if( lp == NULL ) printf( "at %s: NULL entry\n" ); else printf( "at %s: p %.3d:%.2d(%.4d) crc %.3d\n", title, lp->pagenum, lp->linenum, lp->lineanum, lp->crc ); printf( "%s",lp->text ); if( lp->link != NULL ) printf( "next line : %s", lp->link->text ); if( lp->same != NULL ) printf( "same line : %s", lp->same->text ); if( lp->prev != NULL ) printf( "prev line : %s", lp->prev->text ); printf( "\n" ); } } #endif int dont_look( /* comparison line or filler line */ line_ptr line ) { register int i; trace( "dont_look" ); if( line == NULL ) /* EOF reached */ ret_val( 0 ); if( line->linenum <= top_skip ) ret_val( 1 ); if( line->linenum > page_len - bot_skip ) ret_val( 1 ); if( !blanks ) { for( i = 0; i < MAXLINE; i++ ) switch( line->text[i] ) { case '\0': case '\n': ret_val( 1 ); case '\t': case ' ' : break; default : ret_val( 0 ); } } ret_val( 0 ); } int equal( /* point to equivalent text lines? */ line_ptr a, line_ptr b ) { trace( "equal" ); if(( a == NULL ) || ( b == NULL )) ret_val( 0 ); if( a->crc != b->crc ) ret_val( 0 ); if( up_case ) ret_val( !strncmp( a->text, b->text, right_col )) else ret_val( !strnicmp( a->text, b->text, right_col )) /* ignores case on comparison */ } int position( /* move 'f' inp ptr nxt read is where */ int f, line_ptr where ) { trace( "position" ); at[f] = &root[f]; if( where == NULL ) ret; while( at[f]->link != where ) at[f] = at[f]->link; ret; } int addcrc( /* update a CRC check */ int crc, /* running CRC value */ unsigned char c ) /* character to add */ /* CRC computation logic The logic for this method of calculating the CRC 16 bit polynomial is taken from an article by David Schwaderer in the April 1985 issue of PC Tech Journal. */ { return(( crc >> 8 ) & 0x00ff ) ^ crctab[( crc ^ c ) & 0x00ff]; } void makecrc( /* crc line for fast comparisons */ line_ptr a ) { register int i; register int j; register int cs; cs = 0; j = strlen( a->text ); if( j > right_col ) j = right_col; if( up_case ) for( i = 0; i < j; i++ ) cs = addcrc( cs, a->text[i] ); else for( i = 0; i < j; i++ ) cs = addcrc( cs, toupper( a->text[i] )); /* ignore case */ a->crc = ( byte ) cs; } line_ptr next_line( int f ) /* allocates, links and returns the next line from file 'f' if no lines are * buffered, otherwise returns the next buffered line from 'f' and updates the * link pointer to the next buffered line; it also inserts the line in the * correct place in the array same_crc */ { line_ptr place_hold, start; trace( "next_line" ); if( at[f]->link != NULL ) { at[f] = at[f]->link; ret_val( at[f] ); } else { at[f]->link = ( line_ptr ) malloc( sizeof( struct LINE )); if( at[f]->link == NULL ) { printf( "\nError: Out of Memory" ); exit (2); } place_hold = at[f]; at[f] = at[f]->link; if( place_hold == &( root[f] )) at[f]->prev = NULL; else at[f]->prev = place_hold; at[f]->link = NULL; at[f]->same = NULL; if( fgets( at[f]->text, MAXLINE, infile[f] ) == NULL ) { free( at[f] ); at[f] = place_hold; at[f]->link = NULL; at[f]->same = NULL; ret_val( NULL ); } makecrc( at[f] ); /* calc crc for new text line */ #ifdef EMBEDDED_FORMFEEDS if(( strchr( at[f]->text, FORMFEED ) != NULL ) || ( line_count[f] > page_len )) #else if(( *(at[f]->text ) == FORMFEED ) || ( line_count[f] > page_len )) #endif { page_count[f]++; line_count[f] = 1; } at[f]->lineanum = linea_count[f]++; at[f]->linenum = line_count[f]++; at[f]->pagenum = page_count[f]; if( !dont_look( at[f] )) /* insert in array unless dont_look */ { start = same_crc[at[f]->crc][f - 1]; if( start == NULL ) same_crc[at[f]->crc][f - 1] = at[f]; else { while( start->same != NULL ) start = start->same; start->same = at[f]; /* start NULL now, insert at[f] here */ } } ret_val( at[f] ); } } int discard ( /* dealloc all lines fr: root up to */ /* and incl: file 'f' & same_crc */ int f, line_ptr to ) { line_ptr temp; trace( "discard" ); for(;;) { if( root[f].link == NULL || to == NULL ) break; temp = root[f].link; if( !dont_look( temp )) /* line exists, find same_crc recd */ same_crc[temp->crc][f - 1] = temp->same; /* replace with temp->same */ root[f].link = root[f].link->link; root[f].link->prev = NULL; free( temp ); if( temp == to ) break; } at[f] = &root[f]; ret; } int put( line_ptr line ) /* if change barred output file is turned on, prints all lines from the root * of file 1 up to and including 'line'. This is only called if a match exists * for each significant line in file 2. */ { line_ptr temp; trace( "put" ); if( output ) for( temp = root[1].link; ; ) { if( temp == NULL ) ret; fputs( temp->text, outfile ); if( temp == line ) ret; temp = temp->link; } ret; } char *change_bar( /* insert chg bar into 'str' text */ char *str ) { int i; char temp[MAXLINE + 1], *dest, *base; trace( "change_bar" ); base = str; dest = temp; i = 0; if( bar_col != 0 ) { for( i = 0; *str != '\n'; i++ ) { if(( *str == '\r' ) && ( *( str + 1 ) != '\n' )) i = 0; *( dest++ ) = *( str++ ); } while( i++ < bar_col ) *( str )++ = ' '; strcpy( str, "|\n" ); } else { if( str[0] != ' ' ) { strcpy( temp, str ); strcpy( str + 1, temp ); } str[0] = '|'; } ret_val( base ); } int added( line_ptr line ) /* prints a change summary for all significant lines from the root of file 1 * up to and including 'line'. If output is enabled, adds a change bar to the * text and outputs the line to the output file */ { line_ptr temp; trace( "added" ); for( temp = root[1].link; ; ) { if( temp == NULL ) ret; if( !dont_look( temp ) && scr_on ) printf( "%.3d:%.2d(%.4d)< %s", temp->pagenum, temp->linenum, temp->lineanum, temp->text ); if( output ) if( dont_look( temp )) fputs( temp->text, outfile ); else fputs( change_bar( temp->text ), outfile ); if( temp == line ) ret; temp = temp->link; } } int deleted( line_ptr line ) /* outputs a change summary for all lines in file 2 from the root up to and * including 'line' */ { line_ptr temp; trace( "deleted" ); for( temp = root[2].link; ; ) { if( temp == NULL ) ret; if( !dont_look( temp ) && scr_on ) printf( "%.3d:%.2d(%.4d)> %s", temp->pagenum, temp->linenum, temp->lineanum, temp->text ); if( temp == line ) ret; temp = temp->link; } } int resync( line_ptr first, line_ptr second, int lookahead ) /* resynchronizes file 1 and file 2 after a difference is detected and * outputs changed lines and change summaries via added() and deleted(). * Exits with the file inputs pointing at the next two lines that match, * unless it is impossible to sync up again, in which case all lines in file 1 * are printed via added(). Deallocates lines printed by this function. */ { line_ptr file1_start, file2_start, last_bad1, last_bad2, t1, t2, crc; int i, k, moved1, moved2; trace( "resync" ); position( 2, second ); /* ensure enough lines in memory */ last_bad2 = second; for( k = 0; k < lookahead && last_bad2 != NULL ; k++ ) last_bad2 = next_line( 2 ); moved1 = 0; /* now reset file pointers */ file1_start = first; position( 1, first ); for( k = 0; k < lookahead; k++ ) { while( dont_look( file1_start = next_line( 1 ))) ; if( file1_start == NULL ) goto no_sy; moved2 = 0; crc = same_crc[file1_start->crc][1]; /* see if any matching line at all */ while( crc != NULL ) { while( !equal( crc, file1_start )) /* look for matching entries */ { crc = crc->same; if( crc == NULL ) break; } if( crc != NULL ) { t1 = file1_start; /* ok we have a hit */ file2_start = crc; t2 = file2_start; position( 1, file1_start ); position( 2, file2_start ); for( i = 0; ( i < re_sync ) && equal( t1, t2 ); i++ ) { while( dont_look( t1 = next_line( 1 ))) ; while( dont_look( t2 = next_line( 2 ))) ; if(( t1 == NULL ) || ( t2 == NULL )) break; } if( i == re_sync ) { moved2++; if(( last_bad2 = file2_start->prev ) == NULL ) moved2 = 0; goto synced; } crc = crc->same; /* get next entry */ } } last_bad1 = file1_start; /* else no sync/match yet, loop list */ position( 1, file1_start ); while( dont_look( file1_start = next_line( 1 ))) ; moved1++; } ret_val( NO_SYNC ); no_sy: position( 1, first); while(( first = next_line( 1 )) != NULL ) { added( first ); discard( 1, first ); } ret_val( EOF_REACHED ); synced: if( moved1 ) { added( last_bad1 ); discard( 1, last_bad1 ); } position( 1, file1_start ); if( moved2 ) { deleted( last_bad2 ); discard( 2, last_bad2 ); } position( 2, file2_start ); if( scr_on ) printf( "\n" ); ret_val( RE_SYNCED ); } diff( void ) /* differencing executive. Prints and deallocates all lines up to where a * difference is detected, at which point resync() is called. Exits on end of * file 1 */ { int look_lines, result; line_ptr first, second; trace( "diff" ); for( ;; ) { while( dont_look( first = next_line( 1 ))) ; if( first == NULL ) /* file 1 End-of-File */ { put( first ); while(( second = next_line( 2 )) != NULL ) /* put all file 2 as deleted */ { deleted( second ); discard( 2, second ); } ret; } while( dont_look( second = next_line( 2 ))) ; if( equal( first, second )) { put( first ); discard( 1, first ); discard( 2, second ); } else { look_lines = 10; /* start with 10 lines look-ahead */ result = NO_SYNC; while( result == NO_SYNC ) { result = resync( first, second, look_lines ); look_lines *= 2; if( look_lines == 80 ) /* when 80, assume BIG diff, set 400 */ look_lines = 400; } } if( second == NULL ) ret; } } int page_skip( void ) /* skips the first 'skip1' pages of file 1, and then the first 'skip2' pages * of file 2. This is useful to jump over tables of contents */ { line_ptr first, second; trace( "page_skip" ); for( ;; ) { first = next_line( 1 ); if(( first == NULL ) || ( first->pagenum > skip1 )) break; put( first ); discard( 1, first ); } if( first != NULL ) position( 1, first ); for( ;; ) { second = next_line( 2 ); if(( second == NULL ) || ( second->pagenum > skip2 )) break; discard( 2, second ); } if( second != NULL ) position( 2, second ); ret; } int help( /* help - outputs usage information */ void ) { printf( "\ndiff - text file differencer and change barrer" "\nusage: diff [option{option}] newfile oldfile [barfile]" "\n" "\noptions:" ); #ifdef TRACER_FUNCTIONS printf( "\n -t trace operation, default off"); #endif printf( "\n -b n column of barfile for change bar, default 78" "\n -i n compare from column 1 to n, default 80" "\n -h n lines at top of page to skip for headers, default 0" "\n -f n lines at bottom of page to skip for footers, default = 0" "\n -p n lines per page (embedded form feeds override) default = 66" "\n -c uppercase/lowercase is significant (default is off)" "\n -r n lines that must match before files are considered resynced" "\n after differences are found. default = 3" "\n -w blank lines are considered significant (default is not)" "\n -s screen listing off (default is on)" "\n -n n pages in NEWFILE to skip before compare. default = 0" "\n -o n pages in OLDFILE to skip before compare. default = 0" "\n"); ret; } int open_files( /* opens the input and output files */ void ) { int i; trace( "open_files" ); for( i = 1; i < 3; i++ ) if(( infile[i] = fopen( infile_name[i], "r" )) == NULL ) { printf( "\nError: can't open %s", infile_name[i] ); command_errors++; } if( files > 2 ) if(( outfile = fopen( outfile_name, "w" )) == NULL ) { printf( "\nError: can't create %s", outfile_name ); command_errors++; } ret; } strip_opt( /* processes each command line option */ int ac, char *av[] ) { int i; trace( "strip_opt" ); for( i = 1; i < ac; i++ ) { if( av[i][0] == OPT_FLAG ) { switch( av[i][1] ) { case 'b': bar_col = atoi( av[++i] ); break; case 'i': right_col = atoi( av[++i] ); break; case 'h': top_skip = atoi( av[++i] ); break; case 'f': bot_skip = atoi( av[++i] ); break; case 'p': page_len = atoi( av[++i] ); break; case 'c': up_case = 1; break; case 'r': re_sync = atoi( av[++i] ); break; case 'w': blanks = 1; break; case 's': scr_on = 0; break; case 'n': skip1 = atoi( av[++i] ); break; case 'o': skip2 = atoi( av[++i] ); break; #ifdef TRACER_FUNCTIONS case 't': trace_enabled = debug = 1; break; #endif default: printf( "\nUnrecognised option %s", av[i] ); command_errors++; } } else { switch( files ) { case 0: strcpy( infile_name[1], av[i] ); break; case 1: strcpy( infile_name[2], av[i] ); break; case 2: strcpy( outfile_name, av[i] ); output = 1; break; default: printf( "\nError: too many files at %s", av[i] ); command_errors++; } files++; } } /* for each command line argument */ if( !scr_on && !output ) { printf( "\nError: no output file or screen listing will be generated." ); command_errors++; } ret; } int main( int argc, char *argv[] ) { trace ( "main" ); if( argc == 1 ) { help(); exit( 0 ); } else printf( "Pag:Ln Line# diff -- version 2.4 11/23/88\n" ); strip_opt (argc, argv); if( files < 2 ) { printf( "\nError: Must specify two files" ); exit( 2 ); } open_files(); if( command_errors ) exit( 2 ); at[1]->prev = NULL; /* set root previous pointers to 0 */ at[2]->prev = NULL; page_skip(); diff(); ret; }