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