v02i059: Patch for pd-cdiff (MS C, probably others)
mike2 at lcuxa.UUCP
mike2 at lcuxa.UUCP
Thu Feb 18 12:35:18 AEST 1988
Comp.sources.misc: Volume 2, Issue 59
Submitted-By: <mike2 at lcuxa.UUCP>
Archive-Name: pd-cdiff-patch
Comp.sources.misc: Volume 2, Issue 59
Submitted-By: <mike2 at lcuxa.UUCP>
Archive-Name: pd-cdiff-patch
[Nested shars? That's a new one. ++bsa]
Neil Dixon uncovered a flaw in the logic of the cdiff program that
was distributed early in January, and which was redistributed with
changes to make it compilable in Turbo C. I've tested his patch
both on the Unix SysVr2 version and on the PC, and have not found
any errors. Conversely, the earlier version when compiled in MSC
4.0 (but, for some reason, not when compiled in TC 1.5) would
sporadically come up with "read" errors. Since it now works in MSC as
well as TC, I've included the appropriate ifdefs for both compilers,
and have incorporated Neil's patch. (This was for clarity. The line
numbers in his patch did not correspond precisely to the line numbers
in the distributed code.) Both the patch as sent to me and the
revised code are contained below.
As before, I did not write this code. I merely ported it, and of
course make no warranties whatsoever.
-------------------------CUT HERE-------------------------------
#!/bin/sh
echo extracting cdiff.pat ...
cat >cdiff.pat <<xzyyz
>From rutgers!mimsy.umd.edu!uunet!mcvax!esatst!neil Wed Feb 3 10:48:40 1988
Message-Id: <22649.8802021606 at esatst.yc.estec.nl>
To: bellcore!lcuxa!mike2
Subject: patch for PD context diff.
Date: Tue, 02 Feb 88 17:06:29 +0100
From: Neil Dixon <rutgers!mimsy.umd.edu!uunet!mcvax!esatst!neil>
When running the PD context diff program recently submitted to comp.sources.misc
we get a 'Can't read ...' error, when not performing a context diff. Here's the
simple patch.
Regards,
Neil Dixon.
Neil Dixon <neil at yc.estec.nl> UUCP: ...!mcvax!esatst!neil,
Thermal Control & Life Support Division (YCV)
European Space Research and Technology Centre (ESTEC),
Noordwijk, The Netherlands.
Phone: +31 1719 84013
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
# cdiff.patch
# This archive created: Tue Feb 2 17:05:14 1988
export PATH; PATH=/bin:$PATH
if test -f 'cdiff.patch'
then
echo shar: will not over-write existing file "'cdiff.patch'"
else
cat << \SHAR_EOF > 'cdiff.patch'
*** cdiff.c
--- cdiff.c.orig
**************
*** 935,942
}
}
putchar('\n');
! if ((!eflag && c != 'a') || cflag) {
! fetch(oldseek, astart , aend, lenA, infd[0],
cflag ? (c=='d' ? "- " : "! ") : "< ");
if (cflag) {
fputs("--- ", stdout);
--- 937,944 -----
}
}
putchar('\n');
! if (!eflag) {
! fetch(oldseek, astart, aend, lenA, infd[0],
cflag ? (c=='d' ? "- " : "! ") : "< ");
if (cflag) {
fputs("--- ", stdout);
SHAR_EOF
fi # end of overwriting check
# End of shell archive
exit 0
xzyyz
echo extracting cdiff2.c ...
cat >cdiff2.c <<xzyyz
/* Change the following as appropriate */
#undef vms
#undef TURBO /* Note: Use the small model in TC, and
invoke optimization for speed, registers,
and jumps. Even so, it still runs slowly! */
#undef pdp11
#undef OSK
#undef DEBUG
#undef unix
#define MSC 1 /* Note: The source compiles properly on
* MSC 4.0 (small model). I have no idea
* whether it will work on 5.0 */
#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 vms
#include <ssdef.h>
#include <stsdef.h>
#define IO_SUCCESS (SS$_NORMAL | STS$M_INHIB_MSG)
#define IO_ERROR SS$_ABORT
#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), temfile))
#else
#define TEMPFILE "diff.tmp"
#endif
#define TRUE 1
#define FALSE 0
#ifdef pdp11
#define short int
#endif
typedef struct candidate {
int b; /* Line in fileB */
int a; /* Line in fileA */
int link; /* Previous candidate */
} CANDIDATE;
typedef struct line {
unsigned short hash; /* Hash value etc. */
short serial; /* Line number */
} LINE;
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 lenes at end */
FILE *infd[2] = { NULL, NULL }; /* Input file identifiers */
FILE *tempfd; /* Temp for input redirection */
extern long ftell();
extern FILE *fopen();
#ifdef TURBO
extern void *malloc();
#else
extern char *malloc();
#endif
char *fgetss();
unsigned short hash();
#ifdef AMIGA
/* Define these types for Amiga C */
char *savptr;
int savsiz;
char *wrk;
char *wrk2;
int cpysiz;
#endif
/*
* The following vectors overlay the area defined by fileA
*/
short *class; /* Unsorted line numbers */
int *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 */
int *match; /* Longest subsequence */
long *oldseek; /* Seek position in file A */
/*
* The following vectors overlay the area defined by fileB
*/
short *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 *$$mend;
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);
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 = (short *)fileB;
equiv();
member = (short *)compact((char *)member, (slenB + 2) * sizeof (int),
"squeezing member vector");
/*
* Reorder equivalence classes into array class[]
*/
class = (short *)fileA;
unsort();
class = (short *)compact((char *)class, (slenA + 2) * sizeof (int),
"compacting class vector");
#ifdef TIMING
ptime("equiv/unsort");
#endif
/*
* Find longest subsequences
*/
klist = (int *)myalloc((slenA + 2) * sizeof (int), "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 = (int *)myalloc((lenA + 2) * sizeof (int), "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");
if (check(argv[0], argv[1]))
fprintf(stderr, "Spurious match, output is not optimal\n");
#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 unix
unlink(TEMPFILE);
#else
#ifdef OSK
unlink(TEMPFILE);
#else
#ifdef MSC /* MSC 4.0 does not understand disjunctive
#if's. */
unlink(TEMPFILE);
#else
remove(TEMPFILE);
#endif
#endif
#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;
#define LSIZE_INC 200 /* # of line entries to alloc at once */
int lsize = LSIZE_INC;
lentry = (LINE *)myalloc(sizeof(LINE) * (lsize+3), "line");
fd = infd[which];
while (!getline(fd, text)) {
if (++linect >= lsize) {
lsize += 200;
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;
j = 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 < ai)
break; /* ?? Why ?? */
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;
#ifdef TURBO
union {
#else
register union {
#endif
LINE *bp;
short *mp;
} r;
register int j;
LINE *atop;
#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];
r.bp = &sfileB[1];
atop = &sfileA[slenA];
while (ap <= atop && j <= slenB) {
if (ap->hash < r.bp->hash) {
ap->hash = 0;
ap++;
}
else if (ap->hash == r.bp->hash) {
ap->hash = j;
ap++;
}
else {
r.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
ap = &sfileB[0];
atop = &sfileB[slenB];
r.mp = &member[0];
while (++ap <= atop) {
r.mp++;
*r.mp = -(ap->serial);
while (ap[1].hash == ap->hash) {
ap++;
r.mp++;
*r.mp = ap->serial;
}
}
r.mp[1] = -1;
#ifdef DEBUG
for (j = 0; j <= slenB; j++)
printf("member[%d] = %d\n", j, member[j]);
#endif
}
unsort()
/*
* Build class vector
*/
{
register int *temp;
register int *tp;
#if TURBO
union {
#else
register union {
#endif
LINE *ap;
short *cp;
} u;
LINE *evec;
short *eclass;
#ifdef DEBUG
int i;
#endif
temp = (int *)myalloc((slenA + 1) * sizeof(int), "unsort scratch");
u.ap = &sfileA[1];
evec = &sfileA[slenA];
while (u.ap <= evec) {
#ifdef DEBUG
printf("temp[%2d] := %06o\n", u.ap->serial, u.ap->hash);
#endif
temp[u.ap->serial] = u.ap->hash;
u.ap++;
}
/*
* Copy into class vector and free work space
*/
u.cp = &class[1];
eclass = &class[slenA];
tp = &temp[1];
while (u.cp <= eclass)
*u.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
}
subseq()
/*
* Generate maximum common subsequence chain in clist[]
*/
{
int a;
register unsigned ktop;
register int b;
register int s;
unsigned r;
int i;
int cand;
klist[0] = newcand(0, 0, -1);
klist[1] = newcand(slenA + 1, 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)) != 0) {
if (clist[klist[s]].b > b) {
klist[r] = cand;
r = s;
cand = newcand(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 */
}
int
newcand(a, b, pred)
int a; /* Line in fileA */
int b; /* Line in fileB */
int 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(clength - 1);
}
search(low, high, b)
register unsigned low;
register unsigned high;
register int 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 int 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 (!streq(text, textb)) {
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);
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 = 0;
int bstart;
register int bend;
rewind(infd[0]);
rewind(infd[1]);
match[0] = 0;
match[lenA+1] = lenB + 1;
if (!eflag) {
if (cflag) {
/*
* Should include ctime style dates after the file names, but
* this would be non-trivial on OSK. Perhaps there should be
* a special case for stdin.
*/
printf("*** %s\n--- %s\n", fileAname, fileBname);
}
/*
* 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);
}
/*
* Output a 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 (cflag) fputs("**************\n*** ", stdout);
if (c == 'a' && !cflag)
range(astart-1, astart-1, 0); /* Addition: just print one odd # */
else
range(astart, aend, 0); /* Print both, if different */
if (!cflag) {
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 ((!eflag && c != 'a') || cflag) {
fetch(oldseek, astart, aend, lenA, infd[0],
cflag ? (c=='d' ? "- " : "! ") : "< ");
if (cflag) {
fputs("--- ", stdout);
range(bstart, bend, 1);
fputs(" -----\n", stdout);
} else if (astart <= aend && bstart <= bend)
printf("---\n");
}
fetch(newseek, bstart, bend, lenB, infd[1],
cflag ? (c=='a' ? "+ " : "! ") : (eflag ? "" : "> "));
if (eflag && bstart <= bend)
printf(".\n");
}
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) {
printf("%d,%d", from, to);
} else if (to < from) {
printf("%d,%d", to, from);
} else {
printf("%d", from);
}
}
fetch(seekvec, start, end, trueend, fd, pfx)
long *seekvec;
register int start;
register int end;
int trueend;
FILE *fd;
char *pfx;
/*
* Print the appropriate text
*/
{
register int i;
register int first;
register int last;
if (cflag) {
if((first = start - cflag) <= 0) first = 1;
if((last = end + cflag) > trueend) last = trueend;
} else {
first = start;
last = end;
}
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)
fputss(buffer, 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");
#ifdef AMIGA
savsiz = tp - text + strlen(*arg) + 1;
savptr = newname;
#endif
#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;
}
/* Amiga C doesn't have all these extensions for directory... */
#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
#ifdef AMIGA
savsiz = amount;
savptr = pointer;
#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 AMIGA
#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
#else
/*
* This routine is heavily dependent on C storage allocator hacks
* For Amiga, we can't rely on storage being left alone "up to"
* the boundary of allocation as in VMS or RSX. Therefore we have
* to be different here and allocate a new larger segment, then
* free the old one. Messy but hopefully it will work.
*/
extern char *malloc();
/* No realloc(). Do a malloc and copy it. */
if ((new_pointer = malloc((unsigned) new_amount)) == NULL){
noroom(why);
}
/* This MUST assume the program calls compact using the old pointer as the
last call of malloc... Reason is that RSX version is really simpleminded */
cpysiz=savsiz;
/* Complain if deallocate area not same as last allocate area */
if (savptr != pointer) bogus(why);
wrk2=new_pointer;
for (wrk=pointer;cpysiz > 0;cpysiz--){
/* copy data to new area */
*wrk2++ = *wrk++;
}
/* when done, free old memory area. */
free(pointer);
#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 AMIGA
bogus(why)
char *why;
{
fprintf(stderr, "?DIFF-F-invalid compaction when %s\n", why);
exit(IO_ERROR);
}
#endif
#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
*/
/* #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
*/
/* VARARGS */
error(format, args)
char *format;
/*
* Error message before retiring.
*/
{
fprintf(stderr, format, &args);
putc('\n', stderr);
_error();
}
_error()
{
exit(1);
}
/* #include <stdio.h> */
fputss(s, iop)
register char *s;
register FILE *iop;
/*
* Like fput() except that it puts a newline at the end of the line.
*/
{
#ifndef OSK
/*
* Why wasn't this written like the OSK section? What's the difference between
* fputc and putc other than I've never heard of fputc?
*/
register c;
while (c = *s++)
fputc(c, iop);
fputc('\n', iop);
#else
fputs(s, iop);
putc('\n', iop);
#endif
}
/*
* Fgetss() is like fgets() except that the terminating newline
* is removed.
*/
char *fgetss(s, n, iop)
char *s;
register FILE *iop;
{
register c;
register char *cs;
cs = s;
/*
* The getc in the next line used to be an "fgetc". Change it back if
* getc doesn't work on your system, though that would be odd.
*/
while ((c = getc(iop))>=0 && --n>0) {
if (c=='\n')
break;
*cs++ = c;
}
if (c<0 && cs==s)
return((char *)NULL);
*cs = '\0'; /* Overwrite newline as null */
return(s);
}
xzyyz
echo done
---
Mike Slomin
bellcore!lcuxa!mike2
More information about the Comp.sources.misc
mailing list