Category : C Source Code
Archive   : CSRC2.ZIP
Filename : DIFF1.C

 
Output of file : DIFF1.C contained in archive : CSRC2.ZIP
subseq()
/*
* Generate maximum common subsequence chain in clist[]
*/
{
int a;
register int ktop;
register int b;
register int s;
int 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++;
clist = (CANDIDATE *)compact((char *)clist,
clength * 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 int low;
int high;
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 int 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(fileAname, fileBname)
char *fileAname;
char *fileBname;
/*
* Check for hash matches (jackpots) and collect random access indices to
* the two files.
*/
{
register int a; /* Current line in file A */
register int b; /* Current line in file B */
int jackpot;

b = 1;
rewind(infd[0]);
rewind(infd[1]);
oldseek[0] = ftell(infd[0]);
newseek[0] = ftell(infd[1]);
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) {
getline(infd[0], text);
oldseek[a] = ftell(infd[0]);
continue;
}
while (b < match[a]) {
getline(infd[1], textb);
newseek[b] = ftell(infd[1]);
b++;
}
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++;
}
oldseek[a] = ftell(infd[0]);
newseek[b] = ftell(infd[1]);
b++;
}
for (; b <= lenB; b++) {
getline(infd[1], textb);
newseek[b] = ftell(infd[1]);
}
return(jackpot);
}

output()
{
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) {
/*
* 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);
}

change(astart, aend, bstart, bend)
int astart;
int aend;
int bstart;
int bend;
/*
* Output a change entry: fileA[astart..aend] changed to fileB[bstart..bend]
*/
{
/*
* This catches a "dummy" last entry
*/
if (astart > aend && bstart > bend)
return;
range(astart, aend);
putchar((astart > aend) ? 'a'
: (bstart > bend) ? 'd' : 'c');
if (!eflag)
range(bstart, bend);
putchar('\n');
if (!eflag) {
fetch(oldseek, astart, aend, lenA, infd[0], "< ");
if (astart <= aend && bstart <= bend)
printf("---\n");
}
fetch(newseek, bstart, bend, lenB, infd[1], (!eflag) ? "> " : "");
if (eflag && bstart <= bend)
printf(".\n");
}

range(from, to)
int from;
int to;
/*
* Print a range
*/
{
printf("%d", (to > from) ? from : to);
if (to >= from)
printf(",%d", to);
}

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;
int first;
int last;

first = last = FALSE;
if (cflag) {
if (start > end)
return;
if (start > 1) {
start--;
first++;
}
if (end < trueend-1) {
end++;
last++;
}
}
if (fseek(fd, seekvec[start - 1], 0) != 0) {
printf("?Can't read line %d at %08lx (hex) in file%c\n",
start, seekvec[start - 1],
(fd == infd[0]) ? 'A' : 'B');
}
else {
for (i = start; i <= end; 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
if (cflag) {
if (first || (last && i == end)) {
putchar(' ');
first = FALSE;
}
else putchar('|');
}
else printf("%s", pfx);
printf("%s\n", text);
#endif
}
}
}

getline(fd, buffer)
FILE *fd;
char *buffer;
/*
* 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.
*/
{
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) ? 1 : crc);
}

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--;
}
}
cpystr(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.
*/
#ifdef MEGAMAX
if ((newname = myalloc(tp - text + strlen(*arg) + 1, "dir")) == NULL)
error("Out of space at start");
#else
if ((newname = malloc(tp - text + strlen(*arg) + 1)) == NULL)
error("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;
}

char *
myalloc(amount, why)
int amount;
char *why;
/*
* Allocate or crash.
*/
{
register char *pointer;

#ifdef MEGAMAX
if ((pointer = (char *) Malloc((long) amount)) == NULL)
noroom(why);
#else
if ((pointer = malloc((unsigned) amount)) == NULL)
noroom(why);
#endif
return (pointer);
}
#ifdef MEGAMAX
/*
* blk_move.c
*/

blk_move(source, dest, count)
register char *source, *dest; /* Adrese mem. blokova */
register int count; /* Broj byte-a koje treba preseliti */
{
asm { ; Uradi to u asembleru
subq #1, count ; Smanji brojac za jedan jer dfb broji do -1
loop: move.b (source)+, (dest)+
dbf count, loop ; Smanji brojac i vrati se u petlju
}
}

/*
* realloc.c
*/

char *realloc(ptr, size)
char *ptr;
unsigned size;
{
register char *new_ptr;

Mfree(ptr); /* Oslobodi zauzetu memoriju */
new_ptr = (char *)Malloc((long) size); /* Alociraj nov blok memorije */
if (new_ptr != (char *)NULL) /* Prebaci stari blok u novi */
blk_move(ptr, new_ptr, size);
return new_ptr;
}
#endif

char *
compact(pointer, new_amount, why)
char *pointer;
int new_amount;
char *why;
/*
* Reallocate pointer, compacting storage
*/
{
char *new_pointer;
#ifndef MEGAMAX
extern char *realloc();

/*
* This routine is heavily dependent on C storage allocator hacks
*/

#ifndef vms
free(pointer); /* Do not change */
free(free_space); /* The order of this code. */
free_space = malloc(1); /* This code doesn't work on */
#endif
#endif
if ((new_pointer = /* Vax-11 C */
realloc(pointer, (unsigned) new_amount)) == NULL)
noroom(why);
#ifdef DEBUG
if (new_pointer != pointer) {
fprintf(stderr, "moved from %06o to %06o\n",
pointer, new_pointer);
}
/* rdump(new_pointer, why);
*/
#endif
return (new_pointer);
}

noroom(why)
char *why;
{
fprintf(stderr, "?DIFF-F-out of room when %s\n", why);
exit(-1);
}

#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\"\n", what, filename);
if (fatalflag)
error("Can't continue");
}

#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 = klist[i]; cp > &clist[0]; cp = &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


  3 Responses to “Category : C Source Code
Archive   : CSRC2.ZIP
Filename : DIFF1.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/