/* * diff.c - public domain context diff program * * This is pd-diff from comp.sources.misc. */ #ifdef TURBO #include #include #include #include #include #include #else /* !TURBO */ #include #include #endif /* TURBO */ #ifdef VMS #include #include #define IO_SUCCESS -1 #define IO_ERROR 1 #endif /* vms */ #define EOS 0 #ifdef unix char temfile[L_tmpnam]; char *tmpnam(); #define TEMPFILE (temfile[0]? temfile: (tmpnam(temfile), temfile)) #else /* unix */ #define TEMPFILE "diff.tmp" #endif /* unix */ #define TRUE 1 #define FALSE 0 #ifdef pdp11 #define short int #endif /* pdp11 */ 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 /* !TURBO */ extern char *malloc(); #endif /* TURBO */ char *fgetss(); unsigned short hash(); #ifdef AMIGA /* Define these types for Amiga C */ char *savptr; int savsiz; char *wrk; char *wrk2; int cpysiz; #endif /* AMIGA */ /* * 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 /* OSK */ #endif /* DEBUG */ #ifdef TIMING extern long time(); extern char *4532mend; long totaltime; long sectiontime; char *mstart; #endif /* TIMING */ void free(); void exit(); #ifndef OSK void perror(); #endif /* OSK */ /* * Diff main program */ main(argc, argv) int argc; char **argv; { register int i; register char *ap; #ifdef OSK extern int _memmins; _memmins = 16 * 1024; /* tell OSK we will malloc a lot */ #endif /* OSK */ #ifdef TIMING sectiontime = time(&totaltime); #endif /* TIMING */ 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 /* vms */ /* * 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 /* DEBUG */ sort(sfileA, slenA); sort(sfileB, slenB); #ifdef TIMING ptime("input"); #endif /* TIMING */ #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 /* DEBUG */ /* * 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 /* TIMING */ /* * 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 /* OSK */ free((char *) member - sizeof(int)); free((char *) class - sizeof(int)); #endif /* OSK */ match = (int *) myalloc((lenA + 2) * sizeof(int), "match"); unravel(klist[i]); #ifndef OSK free((char *) clist); free((char *) klist); #else /* OSK */ free((char *) clist - sizeof(int)); free((char *) klist - sizeof(int)); #endif /* OSK */ #ifdef TIMING ptime("subsequence/unravel"); #endif /* TIMING */ /* * 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 /* TIMING */ output(argv[0], argv[1]); #ifdef TIMING ptime("output"); printf("%ld seconds required\n", sectiontime - totaltime); #endif /* TIMING */ if (tempfd != NULL) { fclose(tempfd); #ifdef unix unlink(TEMPFILE); #else /* !unix */ #ifdef OSK unlink(TEMPFILE); #else /* OSK */ #ifdef MSC /* MSC 4.0 does not understand disjunctive * #if's. */ unlink(TEMPFILE); #else /* MSC */ remove(TEMPFILE); #endif /* MSC */ #endif /* OSK */ #endif /* unxi */ } return(IO_SUCCESS); } /* * Read the file, building hash table */ input(which) int which; /* 0 or 1 to redefine infd[] */ { 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; } /* * Look for initial and trailing sequences that have identical hash values. * Don't bother building them into the candidate vector. */ squish() { 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 hash entries */ sort(vector, vecsize) LINE *vector; /* What to sort */ int vecsize; /* How many to sort */ { 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; } } } } /* * Build equivalence class vector */ equiv() { register LINE *ap; union { 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 /* DEBUG */ 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 /* DEBUG */ 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 /* DEBUG */ } /* * Build class vector */ unsort() { register int *temp; register int *tp; union { LINE *ap; short *cp; } u; LINE *evec; short *eclass; #ifdef DEBUG int i; #endif /* DEBUG */ 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 /* DEBUG */ 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 /* OSK */ free((char *) temp - sizeof(int)); #endif /* OSK */ #ifdef DEBUG printf("unsort exit\n"); for (i = 1; i <= slenA; i++) printf("class[%d] = %d %06o\n", i, class[i], class[i]); #endif /* DEBUG */ } /* * Generate maximum common subsequence chain in clist[] */ subseq() { 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 /* DEBUG */ /* * 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 /* DEBUG */ 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 /* DEBUG */ } if (s >= ktop) { klist[ktop + 1] = klist[ktop]; ktop++; #ifdef DEBUG klist[r] = cand; dumpklist(ktop, "extend"); #endif /* DEBUG */ break; } } } while (member[++i] > 0); klist[r] = cand; } #ifdef DEBUG printf("last entry = %d\n", ktop - 1); #endif /* DEBUG */ 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 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). */ search(low, high, b) register unsigned low; register unsigned high; register int b; { 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 /* DEBUG */ for (i = 0; i <= lenA; i++) { match[i] = (i <= prefix) ? i : (i > first_trailer) ? i + difference : 0; } #ifdef DEBUG printf("unravel\n"); #endif /* DEBUG */ 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 /* DEBUG */ 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; 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 /* vms */ jackpot = 0; #ifdef DEBUG printf("match vector\n"); for (a = 0; a <= lenA; a++) printf("match[%d] = %d\n", a, match[a]); #endif /* DEBUG */ for (a = 1; a <= lenA; a++) { if (match[a] == 0) { /* Unique line in A */ oldseek[a] = ftell(infd[0]); getline(infd[0], text); continue; } while (b < match[a]) { /* Skip over unique lines in B */ newseek[b] = 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] = ftell(infd[0]); newseek[b] = 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] = 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 /* vms */ 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"); } /* * Print a range */ range(from, to, w) int from; int to; int w; { 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); } } /* * Print the appropriate text */ fetch(seekvec, start, end, trueend, fd, pfx) long *seekvec; register int start; register int end; int trueend; FILE *fd; char *pfx; { 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 /* !DEBUG */ fputs((cflag && (i < start || i > end)) ? " " : pfx, stdout); fputs(text, stdout); putchar('\n'); #endif /* DEBUG */ } } } /* * 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, }; /* * Return the CRC16 hash code for the buffer * Algorithm from Stu Wecker (Digital memo 130-959-002-00). */ unsigned short hash(buffer) char *buffer; { 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 /* DEBUG_ALL */ 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 /* AMIGA */ #else /* OSK */ newname = myalloc(tp - text + strlen(*arg) + 1, "Out of space at start"); #endif /* OSK */ newname = strcat(*arg, text); /* 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 /* vms */ /* * Allocate or crash. */ char * myalloc(amount, why) unsigned amount; char *why; { register char *pointer; #ifdef OSK amount += sizeof(int); #endif /* OSK */ 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 /* DEBUG */ #endif /* OSK */ #ifdef AMIGA savsiz = amount; savptr = pointer; #endif /* AMIGA */ 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; unsigned new_amount; char *why; { register char *new_pointer; #ifndef AMIGA #ifndef OSK #ifdef TURBO extern void *realloc(); #else /* !TURBO */ extern char *realloc(); #endif /* TURBO */ if ((new_pointer = realloc(pointer, (unsigned) new_amount)) == NULL) { noroom(why); } #else /* OSK */ 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 /* DEBUG */ free(pointer - sizeof(int)); #endif /* OSK */ #else /* AMIGA */ /* * 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 /* AMIGA */ #ifndef OSK #ifdef DEBUG if (new_pointer != pointer) { fprintf(stderr, "moved from %06o to %06o\n", pointer, new_pointer); } /* rdump(new_pointer, why); */ #endif /* DEBUG */ #endif /* OSK */ 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 /* AMIGA */ #ifdef DEBUG /* * Dump memory block */ rdump(pointer, why) int *pointer; char *why; { 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 /* DEBUG */ /* * Can't open file message */ cant(filename, what, fatalflag) char *filename; char *what; int fatalflag; { 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; int d_len; int d_which; { 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); } } /* * Dump klist */ dumpklist(kmax, why) int kmax; char *why; { 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 /* DEBUG */ #ifdef TIMING /* * Dump time buffer */ ptime(why) char *why; { long ttemp; ttemp = time(NULL); printf("%ld seconds for %s\n", ttemp - sectiontime, why); sectiontime = ttemp; } #endif /* TIMING */ /* * TRUE if strings are identical */ int streq(s1, s2) register char *s1; register char *s2; { while (*s1++ == *s2) { if (*s2++ == EOS) return (TRUE); } return (FALSE); } /* * Error message before retiring. */ /* VARARGS */ error(format, args) char *format; { fprintf(stderr, format, &args); putc('\n', stderr); _error(); } _error() { exit(1); } /* * Like fput() except that it puts a newline at the end of the line. */ fputss(s, iop) register char *s; register FILE *iop; { fputs(s, iop); putc('\n', iop); } /* * Fgetss() is like fgets() except that the terminating newline * is removed. */ char * fgetss(s, n, iop) char *s; register FILE *iop; { register char *cs; if (fgets(s, n, iop) == NULL) return ((char *) NULL); cs = s + strlen(s) - 1; if (*cs == '\n') *cs = '\0'; return (s); }