home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Frozen Fish 1: Amiga
/
FrozenFish-Apr94.iso
/
bbs
/
alib
/
d1xx
/
d142
/
diff.lha
/
Diff
/
diff.c
< prev
next >
Wrap
C/C++ Source or Header
|
1988-05-22
|
38KB
|
1,731 lines
/*
* Last Hacked by Johan Widen, jw@sics.se, 17 Jan 88.
* Decreased memory use by cleaning up the data types. "new style" context
* diffs. File dates are now displayed under UNIX and Amiga-DOS.
* Incorporated documentation cleanup and TURBO-C adaptions by mike2@lcuxa.
*
* Previously Hacked by Robert A. Larson, blarson@ecla.usc.edu, Nov 29 86
* OSK support.
* Real context diffs, with a couple of minor problems:
* If the first change is deleting leading lines, and the second
* such that the context overlaps the deleted lines, the deleted
* lines are output as context. This is consistant with other
* cases of overlapping context, but patch doesn't like it. It's
* not hard to manually fix the diff in this (rare?) case.
* At most 9 lines of context is output.
*
* Previously Hacked by John Gilmore, hoptoad!gnu, 26Sep86.
* Compiles and runs under Unix. Much faster since it doesn't reallocate
* every data structure in the inner loop(!). Compatible with Unix diff
* output format, though it occasionally finds different sets of changed
* lines (both are valid). -c option needs work. Also, ftell's in
* <check> should be dumped when possible.
*
From: EVERHART%ARISIA%rca.com@CSNET-RELAY.ARPA
Message-Id: <8608201845.AA15181@lll-crg.ARPA>
Date: Wed, 20 Aug 86 10:34 EDT
To: hoptoad!gnu@LLL-CRG.ARPA
Subject: Decus C DIFF source.
*/
/*
* D I F F
*/
/* For VMS:
)BUILD $(TKBOPTIONS) = {
TASK = ...DIF
}
*/
/*
* OSK changes: since OSK doesn't have realloc, put the size
* allocated in the head of each allocated region. This code
* assumes int is a maximally alligned type.
*/
/*
* Borland Turbo C instructions.
*
* 1. Make certain that TURBO is #defined.
* 2. Compile in the Large model.
* 3. Set the optimizations:
* a) to optimize for speed, not size
* b) to use register variables
* c) to invoke register optimization
* c) to invoke jump optimization
*/
#ifdef TURBO
#include <alloc.h>
#include <errno.h>
#include <process.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#else
#include <stdio.h>
#include <ctype.h>
#endif
#ifdef unix
#include <sys/types.h>
#include <sys/stat.h>
#endif
#ifdef vms
#include <ssdef.h>
#include <stsdef.h>
#define IO_SUCCESS (SS | STS)
#define IO_ERROR SS
#endif
#ifdef AMIGA
#ifndef MANX
#ifndef LATTICE
#define LATTICE 1
#define ANSI 1
#endif
#endif
#ifdef LATTICE
#include <stdlib.h>
#include <string.h>
extern char *_TZ;
#endif
#endif
/*
* Note: IO_SUCCESS and IO_ERROR are defined in the Decus C stdio.h file
*/
#ifndef IO_SUCCESS
#define IO_SUCCESS 0
#endif
#ifndef IO_ERROR
#define IO_ERROR 1
#endif
#define EOS 0
#ifdef unix
char temfile[L_tmpnam];
char *tmpnam();
#define TEMPFILE (temfile[0]? temfile: tmpnam(temfile))
#else
#define TEMPFILE "diff.tmp"
#endif
#define TRUE 1
#define FALSE 0
#ifdef pdp11
#define short int
#endif
typedef short LINENO;
typedef unsigned short HASH;
typedef struct candidate {
LINENO b; /* Line in fileB */
LINENO a; /* Line in fileA */
LINENO link; /* Previous candidate */
} CANDIDATE;
typedef struct line {
HASH hash; /* Hash value etc. */
LINENO serial; /* Line number */
} LINE;
#define MAXLINES 32760 /* depends on sizeof(short) */
#define LSIZE_INC 200 /* # of line entries to alloc at once */
LINE *file[2]; /* Hash/line for total file */
#define fileA file[0]
#define fileB file[1]
LINE *sfile[2]; /* Hash/line after prefix */
#define sfileA sfile[0]
#define sfileB sfile[1]
int len[2]; /* Actual lines in each file */
#define lenA len[0]
#define lenB len[1]
int slen[2]; /* Squished lengths */
#define slenA slen[0]
#define slenB slen[1]
int prefix; /* Identical lines at start */
int suffix; /* Identical lines at end */
FILE *infd[2] = { NULL, NULL }; /* Input file identifiers */
FILE *tempfd; /* Temp for input redirection */
#ifndef LATTICE
extern long ftell();
extern FILE *fopen();
#ifdef TURBO
extern void *malloc();
#else
extern char *malloc();
#endif
#endif
#ifdef ANSI
int error(char *,);
char *fgetss(char *, int, FILE *);
HASH hash(char *);
HASH newcand(LINENO, LINENO, LINENO);
unsigned search(unsigned, unsigned, LINENO);
unsigned subseq();
#else
char *fgetss();
HASH hash();
HASH newcand();
unsigned search();
unsigned subseq();
#endif
/*
* The following vectors overlay the area defined by fileA
*/
HASH *class; /* Unsorted line numbers */
HASH *klist; /* Index of element in clist */
CANDIDATE *clist; /* Storage pool for candidates */
int clength = 0; /* Number of active candidates */
#define CSIZE_INC 50 /* How many to allocate each time we have to */
int csize = CSIZE_INC; /* Current size of storage pool */
LINENO *match; /* Longest subsequence */
long *oldseek; /* Seek position in file A */
/*
* The following vectors overlay the area defined by fileB
*/
LINENO *member; /* Concatenated equiv. classes */
long *newseek; /* Seek position in file B */
char *textb; /* Input from file2 for check */
/*
* Global variables
*/
int eflag = FALSE; /* Edit script requested */
int bflag = FALSE; /* Blank supress requested */
int cflag = FALSE; /* Context printout */
int iflag = FALSE; /* Ignore case requested */
char text[257]; /* Input line from file1 */
extern char *myalloc(); /* Storage allocator */
extern char *compact(); /* Storage compactor */
#ifdef DEBUG
#ifndef OSK
#define TIMING
#endif
#endif
#ifdef TIMING
extern long time();
extern char *358mend;
long totaltime;
long sectiontime;
char *mstart;
#endif
main(argc, argv)
int argc;
char **argv;
/*
* Diff main program
*/
{
register int i;
register char *ap;
#ifdef OSK
extern int _memmins;
_memmins = 16 * 1024; /* tell OSK we will malloc a lot */
#endif
#ifdef TIMING
sectiontime = time(&totaltime);
#endif
#ifdef vms
argc = getredirection(argc,argv);
#endif
while (argc > 1 && *(ap = argv[1]) == '-' && *++ap != EOS) {
while (*ap != EOS) {
switch ((*ap++)) {
case 'b':
bflag++;
break;
case 'c':
if (*ap > '0' && *ap <= '9') cflag = *ap++ - '0';
else cflag = 3;
break;
case 'e':
eflag++;
break;
case 'i':
iflag++;
break;
default:
fprintf(stderr,
"Warning, bad option '%c'\n",
ap[-1]);
break;
}
}
argc--;
argv++;
}
if (argc != 3)
error("Usage: diff [-options] file1 file2");
if (cflag && eflag) {
fprintf(stderr,
"Warning, -c and -e are incompatible, -c supressed.\n");
cflag = FALSE;
}
argv++;
for (i = 0; i <= 1; i++) {
if (argv[i][0] == '-' && argv[i][1] == EOS) {
infd[i] = stdin;
if ((tempfd = fopen(TEMPFILE, "w")) == NULL)
cant(TEMPFILE, "work", 1);
}
else {
infd[i] = fopen(argv[i], "r");
if (!infd[i]) cant(argv[i], "input", 2); /* Fatal error */
}
}
if (infd[0] == stdin && infd[1] == stdin)
error("Can't diff two things both on standard input.");
if (infd[0] == NULL && infd[1] == NULL) {
cant(argv[0], "input", 0);
cant(argv[1], "input", 1);
}
#ifdef vms
else if (infd[1] == NULL)
opendir(1, &argv[1], infd[0]);
else if (infd[0] == NULL)
opendir(0, &argv[0], infd[1]);
#endif
/*
* Read input, building hash tables.
*/
input(0);
input(1);
if(lenA > MAXLINES || lenB > MAXLINES)
error("Can't handle files with more than %d lines.", MAXLINES);
squish();
#ifdef DEBUG
printf("before sort\n");
for (i = 1; i <= slenA; i++)
printf("sfileA[%d] = %6d %06o\n",
i, sfileA[i].serial, sfileA[i].hash);
for (i = 1; i <= slenB; i++)
printf("sfileB[%d] = %6d %06o\n",
i, sfileB[i].serial, sfileB[i].hash);
#endif
sort(sfileA, slenA);
sort(sfileB, slenB);
#ifdef TIMING
ptime("input");
#endif
#ifdef DEBUG
printf("after sort\n");
for (i = 1; i <= slenA; i++)
printf("sfileA[%d] = %6d %06o\n",
i, sfileA[i].serial, sfileB[i].hash);
for (i = 1; i <= slenB; i++)
printf("sfileB[%d] = %6d %06o\n",
i, sfileB[i].serial, sfileB[i].hash);
#endif
/*
* Build equivalence classes.
*/
member = (LINENO *)fileB;
equiv(); /* This will overwrite fileB */
member = (LINENO *)compact((char *)member, (slenB + 2) * sizeof (LINENO),
"squeezing member vector");
/* sfileB and fileB are no longer valid */
/*
* Reorder equivalence classes into array class[]
*/
class = (HASH *)fileA;
unsort(); /* This will overwrite fileA */
class = (HASH *)compact((char *)class, (slenA + 2) * sizeof (HASH),
"compacting class vector");
/* sfileA and fileA are no longer valid */
#ifdef TIMING
ptime("equiv/unsort");
#endif
/*
* Find longest subsequences
*/
klist = (HASH *)myalloc((slenA + 2) * sizeof (HASH), "klist");
clist = (CANDIDATE *)myalloc(csize * sizeof (CANDIDATE), "clist");
i = subseq();
#ifndef OSK
free((char *)member);
free((char *)class);
#else
free((char *)member - sizeof(int));
free((char *)class - sizeof(int));
#endif
match = (LINENO *)myalloc((lenA + 2) * sizeof (LINENO), "match");
unravel(klist[i]);
#ifndef OSK
free((char *)clist);
free((char *)klist);
#else
free((char *)clist - sizeof(int));
free((char *)klist - sizeof(int));
#endif
#ifdef TIMING
ptime("subsequence/unravel");
#endif
/*
* Check for fortuitous matches and output differences
*/
oldseek = (long *)myalloc((lenA + 2) * sizeof (* oldseek), "oldseek");
newseek = (long *)myalloc((lenB + 2) * sizeof (* newseek), "newseek");
textb = myalloc(sizeof text, "textbuffer");
check(argv[0], argv[1]);
#ifdef TIMING
ptime("check");
#endif
output(argv[0], argv[1]);
#ifdef TIMING
ptime("output");
printf("%ld seconds required\n", sectiontime - totaltime);
#endif
if (tempfd != NULL) {
fclose(tempfd);
#ifdef vms
remove(TEMPFILE);
#else
unlink(TEMPFILE);
#endif
}
}
input(which)
int which; /* 0 or 1 to redefine infd[] */
/*
* Read the file, building hash table
*/
{
register LINE *lentry;
register int linect = 0;
FILE *fd;
int lsize = LSIZE_INC;
lentry = (LINE *)myalloc(sizeof(LINE) * (lsize+3), "line");
fd = infd[which];
while (!getline(fd, text)) {
if (++linect >= lsize) {
lsize += LSIZE_INC;
lentry = (LINE *)compact((char *)lentry,
(lsize + 3) * sizeof(LINE),
"extending line vector");
}
lentry[linect].hash = hash(text);
}
/*
* If input was from stdin ("-" command), finish off the temp file.
*/
if (fd == stdin) {
fclose(tempfd);
tempfd = infd[which] = fopen(TEMPFILE, "r");
}
/* If we wanted to be stingy with memory, we could realloc lentry down
* to its exact size (+3 for some odd reason) here. No need? */
len[which] = linect;
file[which] = lentry;
}
squish()
/*
* Look for initial and trailing sequences that have identical hash values.
* Don't bother building them into the candidate vector.
*/
{
register int i;
register LINE *ap;
register LINE *bp;
int j;
int k;
/*
* prefix -> first line (from start) that doesn't hash identically
*/
i = 0; ap = &fileA[1]; bp = &fileB[1];
while (i < lenA && i < lenB && ap->hash == bp->hash) {
i++; ap++; bp++;
}
prefix = i;
/*
* suffix -> first line (from end) that doesn't hash identically
*/
j = lenA - i;
k = lenB - i;
ap = &fileA[lenA];
bp = &fileB[lenB];
i = 0;
while (i < j && i < k && ap->hash == bp->hash) {
i++; ap--; bp--;
}
suffix = i;
/*
* Tuck the counts away
*/
for (k = 0; k <= 1; k++) {
sfile[k] = file[k] + prefix;
slen[k] = len[k] - prefix - suffix;
for (i = 0, ap = sfile[k]; i <= slen[k]; i++, ap++) {
ap->serial = i;
}
}
}
sort(vector, vecsize)
LINE *vector; /* What to sort */
int vecsize; /* How many to sort */
/*
* Sort hash entries
*/
{
register int j;
register LINE *aim;
register LINE *ai;
int mid;
int k;
LINE work;
for (j = 1; j <= vecsize; j *= 2);
mid = (j - 1);
while ((mid /= 2) != 0) {
k = vecsize - mid;
for (j = 1; j <= k; j++) {
for (ai = &vector[j]; ai > vector; ai -= mid) {
aim = &ai[mid];
if (aim->hash > ai->hash ||
aim->hash == ai->hash &&
aim->serial > ai->serial)
break;
work.hash = ai->hash;
ai->hash = aim->hash;
aim->hash = work.hash;
work.serial = ai->serial;
ai->serial = aim->serial;
aim->serial = work.serial;
}
}
}
}
equiv()
/*
* Build equivalence class vector
*/
{
register LINE *ap;
register LINE *bp;
register LINENO *mp;
register int j;
LINE *atop, *btop;
#ifdef DEBUG
printf("equiv entry\n");
for (j = 1; j <= slenA; j++)
printf("sfileA[%d] = %6d %06o\n",
j, sfileA[j].serial, sfileA[j].hash);
for (j = 1; j <= slenB; j++)
printf("sfileB[%d] = %6d %06o\n",
j, sfileB[j].serial, sfileB[j].hash);
#endif
j = 1;
ap = &sfileA[1];
bp = &sfileB[1];
atop = &sfileA[slenA];
while (ap <= atop && j <= slenB) {
if (ap->hash < bp->hash) {
ap->hash = 0;
ap++;
}
else if (ap->hash == bp->hash) {
ap->hash = j;
ap++;
}
else {
bp++;
j++;
}
}
while (ap <= atop) {
ap->hash = 0;
ap++;
}
sfileB[slenB + 1].hash = 0;
#ifdef DEBUG
printf("equiv exit\n");
for (j = 1; j <= slenA; j++)
printf("sfileA[%d] = %6d %06o\n",
j, sfileA[j].serial, sfileA[j].hash);
for (j = 1; j <= slenB; j++)
printf("sfileB[%d] = %6d %06o\n",
j, sfileB[j].serial, sfileB[j].hash);
#endif
bp = sfileB;
btop = &sfileB[slenB];
mp = member;
while (++bp <= btop) {
*(++mp) = -(bp->serial);
while (bp[1].hash == bp->hash) {
bp++;
*(++mp) = bp->serial;
}
}
*(++mp) = -1;
#ifdef DEBUG
for (j = 0; j <= slenB; j++)
printf("member[%d] = %d\n", j, member[j]);
#endif
}
unsort()
/*
* Build class vector
*/
{
HASH *temp;
register HASH *tp;
register LINE *ap;
register HASH *cp;
LINE *evec;
HASH *eclass;
#ifdef DEBUG
int i;
#endif
tp = temp = (HASH *)myalloc((slenA + 1) * sizeof(HASH), "unsort scratch");
ap = &sfileA[1];
evec = &sfileA[slenA];
while (ap <= evec) {
#ifdef DEBUG
printf("temp[%2d] := %06o\n", ap->serial, ap->hash);
#endif
tp[ap->serial] = ap->hash;
ap++;
}
/*
* Copy into class vector and free work space
*/
cp = &class[1];
eclass = &class[slenA];
tp = &temp[1];
while (cp <= eclass)
*cp++ = *tp++;
#ifndef OSK
free((char *) temp);
#else
free((char *)temp - sizeof(int));
#endif
#ifdef DEBUG
printf("unsort exit\n");
for (i = 1; i <= slenA; i++)
printf("class[%d] = %d %06o\n", i, class[i], class[i]);
#endif
}
unsigned
subseq()
/*
* Generate maximum common subsequence chain in clist[]
*/
{
int a;
register unsigned ktop;
register LINENO b;
register unsigned s;
unsigned r;
HASH i;
HASH cand;
klist[0] = newcand(0, 0, -1);
klist[1] = newcand((LINENO) (slenA + 1), (LINENO) (slenB + 1), -1);
ktop = 1; /* -> guard entry */
for (a = 1; a <= slenA; a++) {
/*
* For each non-zero element in fileA ...
*/
if ((i = class[a]) == 0)
continue;
cand = klist[0]; /* No candidate now */
r = 0; /* Current r-candidate */
do {
#ifdef DEBUG
printf("a = %d, i = %d, b = %d\n", a, i, member[i]);
#endif
/*
* Perform the merge algorithm
*/
if ((b = member[i]) < 0)
b = -b;
#ifdef DEBUG
printf("search(%d, %d, %d) -> %d\n",
r, ktop, b, search(r, ktop, b));
#endif
if (s = search(r, ktop, b)) {
if (clist[klist[s]].b > b) {
klist[r] = cand;
r = s;
cand = newcand((LINENO) a, b, klist[s-1]);
#ifdef DEBUG
dumpklist(ktop, "klist[s-1]->b > b");
#endif
}
if (s >= ktop) {
klist[ktop + 1] = klist[ktop];
ktop++;
#ifdef DEBUG
klist[r] = cand;
dumpklist(ktop, "extend");
#endif
break;
}
}
} while (member[++i] > 0);
klist[r] = cand;
}
#ifdef DEBUG
printf("last entry = %d\n", ktop - 1);
#endif
return(ktop - 1); /* Last entry found */
}
HASH
newcand(a, b, pred)
LINENO a; /* Line in fileA */
LINENO b; /* Line in fileB */
LINENO pred; /* Link to predecessor, index in cand[] */
{
register CANDIDATE *new;
clength++;
if (++clength >= csize) {
csize += CSIZE_INC;
clist = (CANDIDATE *)compact((char *)clist,
csize * sizeof (CANDIDATE),
"extending clist");
}
new = &clist[clength - 1];
new->a = a;
new->b = b;
new->link = pred;
return((HASH) (clength - 1));
}
unsigned
search(low, high, b)
register unsigned low;
register unsigned high;
register LINENO b;
/*
* Search klist[low..top] (inclusive) for b. If klist[low]->b >= b,
* return zero. Else return s such that klist[s-1]->b < b and
* klist[s]->b >= b. Note that the algorithm presupposes the two
* preset "fence" elements, (0, 0) and (slenA, slenB).
*/
{
register LINENO temp;
register unsigned mid;
if (clist[klist[low]].b >= b)
return(0);
while ((mid = (low + high) / 2) > low) {
if ((temp = clist[klist[mid]].b) > b)
high = mid;
else if (temp < b)
low = mid;
else {
return(mid);
}
}
return(mid + 1);
}
unravel(k)
register int k;
{
register int i;
register CANDIDATE *cp;
int first_trailer;
int difference;
first_trailer = lenA - suffix;
difference = lenB - lenA;
#ifdef DEBUG
printf("first trailer = %d, difference = %d\n",
first_trailer, difference);
#endif
for (i = 0; i <= lenA; i++) {
match[i] = (i <= prefix) ? i
: (i > first_trailer) ? i + difference
: 0;
}
#ifdef DEBUG
printf("unravel\n");
#endif
while (k != -1) {
cp = &clist[k];
#ifdef DEBUG
if (k < 0 || k >= clength)
error("Illegal link -> %d", k);
printf("match[%d] := %d\n", cp->a + prefix, cp->b + prefix);
#endif
match[cp->a + prefix] = cp->b + prefix;
k = cp->link;
}
}
/*
* Check for hash matches (jackpots) and collect random access indices to
* the two files.
*
* It should be possible to avoid doing most of the ftell's by noticing
* that we are not doing a context diff and noticing that if a line
* compares equal to the other file, we will not ever need to know its
* file position. FIXME.
*/
check(fileAname, fileBname)
char *fileAname;
char *fileBname;
{
register int a; /* Current line in file A */
register int b; /* Current line in file B */
int jackpot;
/*
* The VAX C ftell() returns the address of the CURRENT record, not the
* next one (as in DECUS C or, effectively, other C's). Hence, the values
* are "off by one" in the array. OFFSET compensates for this.
*/
#ifdef vms
#define OFFSET (-1)
#else
#define OFFSET 0
#endif
b = 1;
rewind(infd[0]);
rewind(infd[1]);
/*
* See above; these would be over-written on VMS anyway.
*/
#ifndef vms
oldseek[0] = ftell(infd[0]);
newseek[0] = ftell(infd[1]);
#endif
jackpot = 0;
#ifdef DEBUG
printf("match vector\n");
for (a = 0; a <= lenA; a++)
printf("match[%d] = %d\n", a, match[a]);
#endif
for (a = 1; a <= lenA; a++) {
if (match[a] == 0) {
/* Unique line in A */
oldseek[a+OFFSET] = ftell(infd[0]);
getline(infd[0], text);
continue;
}
while (b < match[a]) {
/* Skip over unique lines in B */
newseek[b+OFFSET] = ftell(infd[1]);
getline(infd[1], textb);
b++;
}
/*
* Compare the two, supposedly matching, lines.
* Unless we are going to print these lines, don't bother to
* remember where they are. We only print matching lines
* if a context diff is happening, or if a jackpot occurs.
*/
if (cflag) {
oldseek[a+OFFSET] = ftell(infd[0]);
newseek[b+OFFSET] = ftell(infd[1]);
}
getline(infd[0], text);
getline(infd[1], textb);
if (strcmp(text, textb)) {
#ifdef DEBUG
fprintf(stderr, "Spurious match:\n");
fprintf(stderr, "line %d in %s, \"%s\"\n",
a, fileAname, text);
fprintf(stderr, "line %d in %s, \"%s\"\n",
b, fileBname, textb);
#endif
match[a] = 0;
jackpot++;
}
b++;
}
for (; b <= lenB; b++) {
newseek[b+OFFSET] = ftell(infd[1]);
getline(infd[1], textb);
}
/*
* The logical converse to the code up above, for NON-VMS systems, to
* store away an fseek() pointer at the beginning of the file. For VMS,
* we need one at EOF...
*/
#ifdef vms
oldseek[lenA] = ftell(infd[0]);
getline(infd[0],text); /* Will hit EOF... */
newseek[lenB] = ftell(infd[1]);
getline(infd[1],textb); /* Will hit EOF... */
#endif
return(jackpot);
}
output(fileAname, fileBname)
char *fileAname, *fileBname;
{
register int astart;
register int aend;
int bstart;
register int bend;
rewind(infd[0]);
rewind(infd[1]);
match[0] = 0;
match[lenA+1] = lenB + 1;
if (!eflag) {
if (cflag) {
coutput(fileAname, fileBname);
return;
} else {
/*
* Normal printout
*/
for (astart = 1; astart <= lenA; astart = aend + 1) {
/*
* New subsequence, skip over matching stuff
*/
while (astart <= lenA &&
match[astart] == (match[astart - 1] + 1))
astart++;
/*
* Found a difference, setup range and print it
*/
bstart = match[astart - 1] + 1;
aend = astart - 1;
while (aend < lenA && match[aend + 1] == 0)
aend++;
bend = match[aend + 1] - 1;
match[aend] = bend;
change(astart, aend, bstart, bend);
}
}
}
else {
/*
* Edit script output -- differences are output "backwards"
* for the benefit of a line-oriented editor.
*/
for (aend = lenA; aend >= 1; aend = astart - 1) {
while (aend >= 1
&& match[aend] == (match[aend + 1] - 1)
&& match[aend] != 0)
aend--;
bend = match[aend + 1] - 1;
astart = aend + 1;
while (astart > 1 && match[astart - 1] == 0)
astart--;
bstart = match[astart - 1] + 1;
match[astart] = bstart;
change(astart, aend, bstart, bend);
}
}
if (lenA == 0)
change(1, 0, 1, lenB);
}
coutput(fileAname, fileBname)
char *fileAname, *fileBname;
{
int astart;
int aend;
int bstart;
int bend = 0;
int change, ctmp, cFirst, cOld;
int a1start, a1end, b1start, b1end, a2start, a2end, b2start, b2end;
int astartLast, aendLast, bstartLast, bendLast;
int low;
int numDifferences = 0;
#define CINSERTION 1
#define CDELETION 2
#define CCHANGE 4
for (astart = 1; astart <= lenA; astart = aend + 1) {
if(!(change = findentry(&astart, &aend, &bstart, &bend)))
break;
/* find last entry to print in this diff */
cFirst = change;
astartLast = astart;
aendLast = a1end = aend;
bstartLast = bstart;
bendLast = b1end = bend;
for(a1start = aendLast + 1; a1start <= lenA; a1start = a1end + 1) {
if(!(ctmp = findentry(&a1start, &a1end, &b1start, &b1end)) ||
((a1start - aendLast) >= 2*cflag &&
(b1start - bendLast) >= 2*cflag))
break;
change |= ctmp;
astartLast = a1start;
aendLast = a1end;
bstartLast = b1start;
bendLast = b1end;
}
if(!numDifferences++)
printHeader(fileAname, fileBname);
fputs("***************\n*** ", stdout);
range(astart, aendLast, 0);
fputs(" ****\n", stdout);
if (change & (CDELETION | CCHANGE)) {
a1start = astart; a1end = aend; b2end = bend;
cOld = cFirst;
low = astart - cflag;
while (a1start < astartLast) {
a2start = a1end + 1;
ctmp = findentry(&a2start, &a2end, &b2start, &b2end);
fetch(oldseek, a1start, a1end, low, a2start - 1, lenA,
infd[0], (cOld & CDELETION) ? "- " : "! ");
cOld = ctmp;
low = a2start;
a1start = a2start;
a1end = a2end;
}
fetch(oldseek, astartLast, aendLast, low, aendLast + cflag, lenA,
infd[0], (cOld & CDELETION) ? "- " : "! ");
}
fputs("--- ", stdout);
range(bstart, bendLast, 1);
fputs(" ----\n", stdout);
if (change & (CINSERTION | CCHANGE)) {
a2start = astart; a2end = aend;
b1start = bstart; b1end = b2end = bend;
cOld = cFirst;
low = bstart - cflag;
while (a2start < astartLast) {
a2start = a2end + 1;
ctmp = findentry(&a2start, &a2end, &b2start, &b2end);
fetch(newseek, b1start, b1end, low, b2start - 1, lenB,
infd[1], (cOld & CINSERTION) ? "+ " : "! ");
cOld = ctmp;
low = b2start;
b1start = b2start;
b1end = b2end;
}
fetch(newseek, bstartLast, bendLast, low, bendLast + cflag, lenB,
infd[1], (cOld & CINSERTION) ? "+ " : "! ");
}
aend = aendLast;
bend = bendLast;
}
if (lenA == 0 && lenB > 0) {
numDifferences++;
printHeader(fileAname, fileBname);
cchange(1, 0, 1, lenB);
}
if (!numDifferences)
printf("No differences encountered\n");
}
printHeader(fileAname, fileBname)
char *fileAname, *fileBname;
{
long fileDate;
#ifdef unix
struct stat statbuf;
#endif
#ifdef AMIGA
#ifdef LATTICE
_TZ = "GMT0";
#endif
if(infd[0] == tempfd)
fileDate = time(0);
else
fileDate = getft(fileAname);
printf("*** %s\t%s", fileAname, ctime(&fileDate));
if(infd[1] == tempfd)
fileDate = time(0);
else
fileDate = getft(fileBname);
printf("--- %s\t%s", fileBname, ctime(&fileDate));
#else
#ifdef unix
if(infd[0] == tempfd)
fileDate = time(0);
else {
fstat(fileno(infd[0]), &statbuf);
fileDate = statbuf.st_mtime;
}
printf("*** %s\t%s", fileAname, ctime(&fileDate));
if(infd[1] == tempfd)
fileDate = time(0);
else {
fstat(fileno(infd[1]), &statbuf);
fileDate = statbuf.st_mtime;
}
printf("--- %s\t%s", fileBname, ctime(&fileDate));
#else
printf("*** %s\n--- %s\n", fileAname, fileBname);
#endif
#endif
}
int
findentry(astartp, aendp, bstartp, bendp)
int *astartp, *aendp, *bstartp, *bendp;
{
int save;
register int astart = *astartp;
register int aend;
if(astart > lenA)
return(0);
save = match[astart - 1];
match[astart - 1] = *bendp;
/* Skip over matching stuff */
while (astart <= lenA && match[astart] == (match[astart - 1] + 1))
astart++;
*bstartp = match[astart - 1] + 1;
aend = astart - 1;
while (aend < lenA && match[aend + 1] == 0)
aend++;
*bendp = match[aend + 1] - 1;
match[*astartp - 1] = save;
*astartp = astart;
*aendp = aend;
if (astart > aend) {
if (*bstartp > *bendp)
return(0);
else
return(CINSERTION);
} else if (*bstartp > *bendp)
return(CDELETION);
else
return(CCHANGE);
}
/*
* Output a non context diff change entry:
* fileA[astart..aend] changed to fileB[bstart..bend]
*/
change(astart, aend, bstart, bend)
int astart;
int aend;
int bstart;
int bend;
{
char c;
/*
* This catches a "dummy" last entry
*/
if (astart > aend && bstart > bend)
return;
c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
if (c == 'a')
range(astart-1, astart-1, 0); /* Addition: just print one odd # */
else
range(astart, aend, 0); /* Print both, if different */
putchar(c);
if (!eflag) {
if (c == 'd')
range(bstart-1, bstart-1, 1); /* Deletion: just print one odd # */
else
range(bstart, bend, 1); /* Print both, if different */
}
putchar('\n');
if (c != 'a') {
fetch(oldseek, astart, aend, 0, 0, lenA, infd[0], "< ");
if (astart <= aend && bstart <= bend)
printf("---\n");
}
if (c != 'd')
fetch(newseek, bstart, bend, 0, 0, lenB, infd[1], eflag ? "" : "> ");
if (eflag && bstart <= bend)
printf(".\n");
}
/*
* Output a context diff change entry:
* fileA[astart..aend] changed to fileB[bstart..bend]
*/
cchange(astart, aend, bstart, bend)
int astart;
int aend;
int bstart;
int bend;
{
char c;
/*
* This catches a "dummy" last entry
*/
if (astart > aend && bstart > bend)
return;
c = (astart > aend) ? 'a' : (bstart > bend) ? 'd' : 'c';
fputs("***************\n*** ", stdout);
range(astart, aend, 0);
fputs(" ****\n", stdout);
fetch(oldseek, astart, aend, astart - cflag, aend + cflag, lenA, infd[0],
c=='d' ? "- " : "! ");
fputs("--- ", stdout);
range(bstart, bend, 1);
fputs(" ----\n", stdout);
fetch(newseek, bstart, bend, bstart - cflag, bend + cflag, lenB, infd[1],
c=='a' ? "+ " : "! ");
}
range(from, to, w)
int from;
int to;
int w;
/*
* Print a range
*/
{
if (cflag) {
if((from -= cflag) <= 0) from = 1;
if((to += cflag) > len[w]) to = len[w];
if(!to) from = 0;
}
if (to > from) {
printf("%d,%d", from, to);
} else if (to < from) {
printf("%d,%d", to, from);
} else {
printf("%d", from);
}
}
fetch(seekvec, start, end, low, high, trueend, fd, pfx)
long *seekvec;
register int start;
register int end;
int low;
int high;
int trueend;
FILE *fd;
char *pfx;
/*
* Print the appropriate text
*/
{
register int i;
register int first;
register int last;
if (cflag) {
if((first = low) <= 0) first = 1;
if((last = high) > trueend) last = trueend;
} else {
first = start;
last = end;
}
if (first > last)
return;
if (fseek(fd, seekvec[first], 0) != 0) {
printf("?Can't read line %d at %08lx (hex) in file%c\n",
start, seekvec[first],
(fd == infd[0]) ? 'A' : 'B');
}
else {
for (i = first; i <= last; i++) {
if (fgetss(text, sizeof text, fd) == NULL) {
printf("** Unexpected end of file\n");
break;
}
#ifdef DEBUG
printf("%5d: %s%s\n", i, pfx, text);
#else
fputs((cflag && (i<start || i>end)) ? " " : pfx, stdout);
fputs(text, stdout);
putchar('\n');
#endif
}
}
}
/*
* Input routine, read one line to buffer[], return TRUE on eof, else FALSE.
* The terminating newline is always removed. If "-b" was given, trailing
* whitespace (blanks and tabs) are removed and strings of blanks and
* tabs are replaced by a single blank. Getline() does all hacking for
* redirected input files.
*/
int
getline(fd, buffer)
FILE *fd;
char *buffer;
{
register char *top;
register char *fromp;
register char c;
if (fgetss(buffer, sizeof text, fd) == NULL) {
*buffer = EOS;
return(TRUE);
}
if (fd == stdin) {
fputs(buffer, tempfd);
putc('\n', tempfd);
}
if (bflag || iflag) {
top = buffer;
fromp = buffer;
while ((c = *fromp++) != EOS) {
if (bflag && (c == ' ' || c == '\t')) {
c = ' ';
while (*fromp == ' ' || *fromp == '\t')
fromp++;
}
if (iflag)
c = tolower(c);
*top++ = c;
}
if (bflag && top[-1] == ' ')
top--;
*top = EOS;
}
return(FALSE);
}
static unsigned short crc16a[] = {
0000000, 0140301, 0140601, 0000500,
0141401, 0001700, 0001200, 0141101,
0143001, 0003300, 0003600, 0143501,
0002400, 0142701, 0142201, 0002100,
};
static unsigned short crc16b[] = {
0000000, 0146001, 0154001, 0012000,
0170001, 0036000, 0024000, 0162001,
0120001, 0066000, 0074000, 0132001,
0050000, 0116001, 0104001, 0043000,
};
unsigned short
hash(buffer)
char *buffer;
/*
* Return the CRC16 hash code for the buffer
* Algorithm from Stu Wecker (Digital memo 130-959-002-00).
*/
{
register unsigned short crc;
register char *tp;
register short temp;
crc = 0;
for (tp = buffer; *tp != EOS;) {
temp = *tp++ ^ crc; /* XOR crc with new char */
crc = (crc >> 8)
^ crc16a[(temp & 0017)]
^ crc16b[(temp & 0360) >> 4];
}
#ifdef DEBUG_ALL
printf("%06o: %s\n", (crc == 0) ? 1 : crc, buffer);
#endif
return((crc == 0) ? (unsigned short) 1 : crc);
}
#ifdef vms
opendir(which, arg, okfd)
int which; /* Which file to open (0 or 1) */
char **arg; /* File name argument, &argv[which] */
FILE *okfd; /* File name (already open) */
{
register char *tp;
register int c;
register char *newname;
fgetname(okfd, text);
/*
* Skip over device name
*/
for (tp = text; (c = *tp) && c != ':'; tp++);
if (c) tp++;
else tp = text;
/*
* Skip over [UIC] or [PPN] if present
*/
if (*tp == '[' || *tp == '(') {
while ((c = *tp++) && c != ']' && c != ')');
if (c == 0) {
fprintf(stderr, "?Bug: bad file name \"%s\"\n",
text);
tp--;
}
}
strcpy(text, tp);
/*
* Don't include version
*/
for (tp = text; (c = *tp) && c != ';'; tp++);
*tp = 0;
/*
* Now, text has the file name, tp - text, its length,
* and *arg the (possible) directory name. Create a new
* file name for opening.
*/
#ifndef OSK
if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
error("Out of space at start");
#else
newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start");
#endif
concat(newname, *arg, text, NULL);
if ((infd[which] = fopen(newname, "r")) == NULL)
cant(*arg, "constructed input", 1);
else
*arg = newname;
}
#endif
char *
myalloc(amount, why)
int amount;
char *why;
/*
* Allocate or crash.
*/
{
register char *pointer;
#ifdef OSK
amount += sizeof(int);
#endif
if ((pointer = malloc((unsigned) amount)) == NULL)
noroom(why);
#ifdef OSK
*((int *)pointer) = amount;
pointer += sizeof(int);
#ifdef DEBUG
fprintf(stderr, "Myalloc: %d at %06o\n", amount, pointer);
#endif
#endif
return (pointer);
}
/*
* Reallocate pointer, compacting storage
*
* The "compacting storage" part is probably not relevant any more.
* There used to be horrid code here that malloc'd one byte and freed
* it at magic times, to cause garbage collection of the freespace
* or something. It's safely gone now, you didn't have to see it.
* -- John Gilmore, Nebula Consultants, Sept 26, 1986
*/
char *
compact(pointer, new_amount, why)
char *pointer;
int new_amount;
char *why;
{
register char *new_pointer;
#ifndef OSK
#ifdef TURBO
extern void *realloc();
#else
extern char *realloc();
#endif
if ((new_pointer = realloc(pointer, (unsigned) new_amount)) == NULL){
noroom(why);
}
#else
register int old_amount;
new_amount += sizeof(int);
if((new_pointer = malloc(new_amount)) == NULL) noroom(why);
*(int *)new_pointer = new_amount;
new_pointer += sizeof(int);
old_amount = *(((int *)pointer)-1);
/* _strass is like bcopy with the first two arguments reversted */
_strass(new_pointer, pointer, (new_amount <= old_amount ?
new_amount : old_amount) - sizeof(int));
#ifdef DEBUG
fprintf(stderr, "compact %d to %d from %06o to %06o\n",
old_amount, new_amount, pointer, new_pointer);
#endif
free(pointer - sizeof(int));
#endif
#ifndef OSK
#ifdef DEBUG
if (new_pointer != pointer) {
fprintf(stderr, "moved from %06o to %06o\n",
pointer, new_pointer);
}
/* rdump(new_pointer, why);
*/
#endif
#endif
return (new_pointer);
}
noroom(why)
char *why;
{
fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
exit(IO_ERROR);
}
#ifdef DEBUG
rdump(pointer, why)
int *pointer;
char *why;
/*
* Dump memory block
*/
{
int *last;
int count;
last = ((int **)pointer)[-1];
fprintf(stderr, "dump %s of %06o -> %06o, %d words",
why, pointer, last, last - pointer);
last = (int *)(((int) last) & ~1);
for (count = 0; pointer < last; ++count) {
if ((count & 07) == 0) {
fprintf(stderr, "\n%06o", pointer);
}
fprintf(stderr, "\t%06o", *pointer);
pointer++;
}
fprintf(stderr, "\n");
}
#endif
cant(filename, what, fatalflag)
char *filename;
char *what;
int fatalflag;
/*
* Can't open file message
*/
{
fprintf(stderr, "Can't open %s file \"%s\": ", what, filename);
#ifndef OSK
perror((char *)NULL);
#else
prerr(0, errno);
#endif
if (fatalflag) {
exit(fatalflag);
}
}
#ifdef DEBUG
dump(d_linep, d_len, d_which)
LINE *d_linep;
{
register int i;
printf("Dump of file%c, %d elements\n", "AB"[d_which], d_len);
printf("linep @ %06o\n", d_linep);
for (i = 0; i <= d_len; i++) {
printf("%3d %6d %06o\n", i,
d_linep[i].serial, d_linep[i].hash);
}
}
dumpklist(kmax, why)
int kmax;
char *why;
/*
* Dump klist
*/
{
register int i;
register CANDIDATE *cp;
register int count;
printf("\nklist[0..%d] %s, clength = %d\n", kmax, why, clength);
for (i = 0; i <= kmax; i++) {
cp = &clist[klist[i]];
printf("%2d %2d", i, klist[i]);
if (cp >= &clist[0] && cp < &clist[clength])
printf(" (%2d %2d -> %2d)\n", cp->a, cp->b, cp->link);
else if (klist[i] == -1)
printf(" End of chain\n");
else printf(" illegal klist element\n");
}
for (i = 0; i <= kmax; i++) {
count = -1;
for (cp = (CANDIDATE *)klist[i]; cp > &clist[0];
cp = (CANDIDATE *)&cp->link) {
if (++count >= 6) {
printf("\n ");
count = 0;
}
printf(" (%2d: %2d,%2d -> %d)",
cp-clist, cp->a, cp->b, cp->link);
}
printf("\n");
}
printf("*\n");
}
#endif
#ifdef TIMING
ptime(why)
char *why;
/*
* Dump time buffer
*/
{
long ttemp;
ttemp = time(NULL);
printf("%ld seconds for %s\n",
ttemp - sectiontime, why);
sectiontime = ttemp;
}
#endif
/*
* s t r e q . c
*/
/*)LIBRARY
*/
#ifdef DOCUMENTATION
title streq String Equality Test
index String equality test
synopsis
.s.nf
streq(a, b);
char *a;
char *b;
.s.f
Description
Return TRUE if the strings are equal.
Bugs
#endif
/* #define EOS 0
#define FALSE 0
#define TRUE 1
*/
int
streq(s1, s2)
register char *s1;
register char *s2;
/*
* TRUE if strings are identical
*/
{
while (*s1++ == *s2) {
if (*s2++ == EOS)
return (TRUE);
}
return (FALSE);
}
/*
* e r r o r . c
*/
/*)LIBRARY
*/
#ifdef DOCUMENTATION
title error Fatal Error Exit
index Fatal error exit
synopsis
.s.nf
_error()
error(format, args)
char *format;
.s.f
documentation
Fatal error exits. _error() halts, error() prints something
on stderr and then halts.
bugs
Not a real vararg function. Only handles up to a fixed number of args.
#endif
/* VARARGS */
error(format, arg1, arg2)
char *format;
int arg1, arg2;
/*
* Error message before retiring.
*/
{
fprintf(stderr, format, arg1, arg2);
putc('\n', stderr);
_error();
}
_error()
{
exit(1);
}
/*
* Fgetss() is like fgets() except that the terminating newline
* is removed.
*/
char *fgetss(s, n, iop)
char *s;
FILE *iop;
{
int len;
s[n - 1] = 0;
if(fgets(s, n-1, iop) == NULL)
return(NULL);
len = strlen(s);
if(s[len - 1] == '\n')
s[len - 1] = 0;
return(s);
}