V10/cmd/odist/pax/ship/libodelta/910208/base

0707070000000000011006440044230044230000010000000467126123100002400000000211MakefileUgsfGgsf/*
 * old kpv delta/update/malloc library
 */

SYSV == 1

odelta :LIBRARY: update.h suftree.h \
	delta.c mtchstring.c suftree.c update.c
0707070000000000021006440044230044230000010000000425126261600002300000022032delta.cUgsfGgsf#include	"update.h"
#include	"suftree.h"

/*
**	Compute delta commands to transform the source string 'src'
**	to the target string 'tar'. Small blockmoves are transformed
**	to blockadds for space efficiency.
**	Return -1 in case of error.
**
**	For details on computing blockmoves, see:
**	"The String-to-String Correction Problem with Block Moves"
**	W. Tichy, ACM TOCS, v.2, No.4, 1984, pp.309-321.
**
**	Written by Kiem-Phong Vo, 5/18/88
*/

extern char	*malloc();

#define M_MAX	9	/* max size of a block move instruction */
#define A_MAX	5	/* max size of the header of an add instruction */

/* structure of a delta instruction */
typedef struct _m_
{
	int		type;	/* DELTA_MOVE or DELTA_ADD */
	long		size;	/* size of the block being moved or added */
	long		addr;	/* offset where the block starts */
	struct _m_	*last;	/* doubly linked list for easy insert/delete */
	struct _m_	*next;
} Move;

/* bases of the source and target strings */
static char	*Bsrc, *Btar;

/* Data buffer area */
static char	*Ddata, *Dend, *Dnext;
static int	Dfd;

#define delinit(buf,fd)	(Ddata=Dnext=buf, Dend=buf+BUFSIZE, Dfd=fd)
#define delflush()	(write(Dfd,Ddata,Dnext-Ddata) >= 0 ? (Dnext=Ddata,0) : -1)

static int delputc(byte)
char	byte;
{
	if(Dnext == Dend)
		if(delflush() < 0)
			return -1;
	*Dnext++ = byte;
	return 0;
}

static int delputl(n,v)
register int	n;
register long	v;
{
	register int	i;
	unsigned char	c[4];

	for(i = 0; i < n; ++i)
	{
		c[i] = (unsigned char)(v%BASE);
		v /= BASE;
	}
	for(i = n-1; i >= 0; --i)
		if(delputc((char)c[i]) < 0)
			return -1;
	return 0;
}

static int delputs(n,addr)
register long	n;
register long	addr;
{
	if(n < (Dend-Dnext))
	{
		memcopy(Dnext,Btar+addr,n);
		Dnext += n;
	}
	else
	{
		if(delflush() < 0)
			return -1;
		if(write(Dfd,Btar+addr,n) != n)
			return -1;
	}
	return 0;
}

/* write an instruction */
static int putMove(this)
Move	*this;
{
	register char	inst;

	inst = this->type;
	inst |= (NBYTE(this->size)&07) << 3;
	if(this->type == DELTA_MOVE)
	{
		inst |= NBYTE(this->addr)&07;
		if(delputc(inst) < 0 ||
		   delputl(NBYTE(this->size),this->size) < 0 ||
		   delputl(NBYTE(this->addr),this->addr) < 0)
			return -1;
	}
	else
	{
		if(delputc(inst) < 0 ||
		   delputl(NBYTE(this->size),this->size) < 0 ||
		   delputs(this->size,this->addr) < 0)
			return -1;
	}
	return 0;
}

/* constructor for Move */
static Move *newMove(type,size,addr,last)
int	type;
long	size;
long	addr;
Move	*last;
{
	register Move *this = (Move*) malloc(sizeof(Move));
	if(this == NIL(Move))
		return NIL(Move);
	this->type = type;
	this->size = size;
	this->addr = addr;
	if(last)
	{
		last->next = this;
		this->last = last;
	}
	else	this->last = NIL(Move);
	this->next = NIL(Move);
	return this;
}

/* destructor for Move, return the elt after move */
static Move *delMove(this)
Move	*this;
{
	register Move *next = this->next;
	register Move *last = this->last;
	if(last)
		last->next = next;
	if(next)
		next->last = last;
	free((char*)this); 
	return next ? next : last;
}

/* make a new add command */
static Move *makeAdd(beg,end,last)
char	*beg, *end;
Move	*last;
{
	register Move	*this;

	this = newMove(DELTA_ADD,(long)(end-beg),(long)(beg-Btar),NIL(Move));
	if(!this)
		return NIL(Move);

	/* remove small previous adjacent moves */
	while(last)
	{
		register int a_size, cost_m, cost_a;

		if(last->type == DELTA_ADD)
			break;

		cost_m = NBYTE(last->size) + NBYTE(last->addr) +
			 NBYTE(this->size) + this->size;
		a_size = this->size + last->size;
		cost_a = NBYTE(a_size) + a_size;
		if(cost_m < cost_a)
			break;

		this->size  = a_size;
		this->addr -= last->size;
		last = delMove(last);
	}

	/* merge with adjacent adds */
	if(last && last->type == DELTA_ADD)
	{
		this->size += last->size;
		this->addr -= last->size;
		last = delMove(last);
	}

	if(last)
	{
		last->next = this;
		this->last = last;
	}
	return this;
}

/* check to see if a move is appropriate */
static int chkMove(m_size,m_addr,a_size)
long	m_size, m_addr, a_size;
{
	register int cost_m, cost_a;

	cost_m = NBYTE(m_size) + NBYTE(m_addr);
	cost_a = NBYTE(m_size) + m_size;
	if(cost_m >= cost_a)
		return 0;

	/* it's good but it may be better to merge it to an add */
	if(a_size > 0)
	{
		register int m_cost, a_cost;

		m_cost = cost_m + NBYTE(a_size) + a_size;
		a_size += m_size;
		a_cost = NBYTE(a_size) + a_size;

		/* it is better to merge! */
		if(m_cost >= a_cost)
			return 0;
	}

	return m_size;
}

/* optimize a sequence of moves */
static Move *optMove(s)
register Move *s;
{
	register long	add, m_cost, a_cost;
	register Move	*this, *last;

	add = (s->last && s->last->type == DELTA_ADD) ? s->last->size : 0;

	m_cost = 0;
	a_cost = 0;
	for(this = s; this != NIL(Move); this = this->next)
	{
		register long cost_m, cost_a;

		if(this->type == DELTA_ADD || this->size > (M_MAX+A_MAX))
			break;

		m_cost += 1+NBYTE(this->size)+NBYTE(this->addr);
		a_cost += this->size;

		/* costs of alternatives */
		cost_m = m_cost;
		cost_a = a_cost;
		if(add > 0)
		{
			cost_m += 1 + add + NBYTE(add);
			cost_a += add;
		}
		if(this->next && this->next->type == DELTA_ADD)
		{
			cost_m += 1 + this->next->size + NBYTE(this->next->size);
			cost_a += this->next->size;
		}
		cost_a += 1 + NBYTE(cost_a);

		/* conversion is bad */
		if(cost_m < cost_a)
			continue;

		/* convert the entire sequence to an add */
		s->type = DELTA_ADD;
		while(this != s)
		{
			last = this->last;
			s->size += this->size;
			(void)delMove(this);
			this = last;
		}

		/* merge adjacent adds */
		if((last = s->last) && last->type == DELTA_ADD)
		{
			last->size += s->size;
			(void)delMove(s);
			s = last;
		} 
		if(s->next && s->next->type == DELTA_ADD)
		{
			s->size += s->next->size;
			(void)delMove(s->next);
		}
		/* done */
		break;
	}
	return s;
}

/* the real thing */
delta(src,n_src,tar,n_tar,delfd)
char	*src;
long	n_src;
char	*tar;
long	n_tar;
int	delfd;
{
	register char	*sp, *tp, *esrc, *etar;
	register long	size, addr;
	Suftree		*tree;
	Move		*moves, *last;
	char		inst, buf[BUFSIZE];
	long		mtchstring();

	/* initialize the output area */
	delinit(buf,delfd);

	/* output file sizes */
	inst = DELTA_TYPE | ((NBYTE(n_src)&07) << 3) | (NBYTE(n_tar)&07);
	if(delputc(inst) < 0)
		return -1;
	if(delputl(NBYTE(n_src),n_src) < 0 || delputl(NBYTE(n_tar),n_tar) < 0)
		return -1;

	/* bases */
	Bsrc = src;
	Btar = tar;
	esrc = src + n_src - 1;
	etar = tar + n_tar - 1;

	/* initialize list and last block */
	moves = NIL(Move);
	last = NIL(Move);

	/* try making suffix tree */
	if(!(tree = n_tar > 0 ? bldsuftree(src,n_src) : NIL(Suftree)))
	{
		/* not enough space for tree, remove matching prefix and suffix */
		for(; src <= esrc && tar <= etar; ++src, ++tar)
			if(*src != *tar)
				break;
		if((size = src-Bsrc) > 0)
		{
			register int cost_m, cost_a;

			cost_m = NBYTE(size) + NBYTE(0);
			cost_a = NBYTE(size) + size;
			if(cost_m < cost_a)
			{
				moves = newMove(DELTA_MOVE,size,0L,NIL(Move));
				if(!moves)
					return -1;
				n_src -= src-Bsrc;
				n_tar -= tar-Btar;
			}
			else
			{
				src = Bsrc;
				tar = Btar;
			}
		}

		for(sp = esrc, tp = etar; sp >= src && tp >= tar; --sp, --tp)
			if(*sp != *tp)
				break;
		if((size = esrc-sp) > 0)
		{
			addr = sp+1-Bsrc;
			if(chkMove(size,addr,0L) > 0)
			{
				last = newMove(DELTA_MOVE,size,addr,NIL(Move));
				if(!last)
					return -1;
				esrc = sp;
				etar = tp;
				n_tar = etar-tar+1;
				n_src = esrc-src+1;
			}
		}

		/* try making the tree again */
		tree = n_tar > 0 ? bldsuftree(src,n_src) : NIL(Suftree);
	}

	/* compute block moves */
	tp = NIL(char);
	while(n_tar > 0)
	{
		char	*match;

		if(tree)
			size = mtchsuftree(tree,tar,n_tar,&match);
		else	size = mtchstring(src,n_src,tar,n_tar,&match);
		if(size < 0)
			return -1;
		if(size > 0)
			size = chkMove(size,(long)(match-Bsrc),(long)(tp ? tp-tar : 0));

		/* output a block move */
		if(size > 0)
		{
			if(tp)
			{
				moves = makeAdd(tp,tar,moves);
				if(!moves)
					return -1;
				tp = NIL(char);
			}
			moves = newMove(DELTA_MOVE,size,(long)(match-Bsrc),moves);
			if(!moves)
				return -1;
			tar += size;
			n_tar -= size;
		}
		else
		{
			if(!tp)
				tp = tar;
			tar += 1;
			n_tar -= 1;
		}
	}

	/* add any remaining blocks */
	if(tp)
	{
		if(last && chkMove(last->size,last->addr,(long)(tar-tp)) <= 0)
		{
			tar += last->size;
			last = delMove(last);
		}
		moves = makeAdd(tp,tar,moves);
		if(!moves)
			return -1;
	}
	if(last)
	{
		moves->next = last;
		last->last = moves;
	}

	/* release space use for string matching */
	if(tree)
		delsuftree(tree);
	else	mtchstring(NIL(char),0L,NIL(char),0L,NIL(char*));

	/* optimize move instructions */
	if(moves)
	{
		register Move	*this;

		this = moves;
		while(this->last)
			this = this->last;
		for(; this != NIL(Move); this = this->next)
			if(this->type == DELTA_MOVE && this->size <= (M_MAX+A_MAX))
				moves = this = optMove(this);

		while(moves->last)
			moves = moves->last;
	}

	/* write out the move instructions */
	addr = 0L;
	while(moves)
	{
		if(moves->type == DELTA_ADD)
			moves->addr = addr;
		addr += moves->size;
		if(putMove(moves) < 0)
			return -1;
		moves = delMove(moves);
	}

	/* write ending token */
	delputc((char)DELTA_TYPE);

	/* flush buffer */
	return delflush();
}
0707070000000000031006440044230044230000010000000425126261600003000000006234mtchstring.cUgsfGgsf#include	"update.h"


/*
**	Find the longest prefix of tar that match some substring of src
**	This uses an inverted index for speed.
*/
#define ALPHA	(256)	/* alphabet size */

static void freemem(n_index,index)
long	*n_index;
char	***index;
{
	register int i;
	if(n_index && index)
	{
		for(i = 0; i < ALPHA; ++i)
			if(n_index[i] > 0)
				free(index[i]);
		free(index);
		free(n_index);
	}
}

/* initial assumptions: src[0] == tar[0] && src+n_match <= endsrc */
static long domatch(src,endsrc,tar,endtar,n_match)
char	*src, *endsrc, *tar, *endtar;
long	n_match;
{
	register char	*sp, *tp;

	/* see if this really improves on the current match */
	for(sp = src+n_match, tp = tar+n_match; sp > src; --sp, --tp)
		if(*sp != *tp)
			break;

	/* got an improvement, match as many more as we can */
	if(sp == src)
	{
		sp = src+n_match+1;
		tp = tar+n_match+1;
		for(; sp < endsrc && tp < endtar; ++sp, ++tp)
			if(*sp != *tp)
				break;
	}
	return tp-tar;
}

/* the real thing */
long	mtchstring(src,n_src,tar,n_tar,match)
char	*src;	/* the source string to match from */
long	n_src;	/* the length of src */
char	*tar;	/* the string a prefix of which is matched */
long	n_tar;	/* the length of tar */
char	**match; /* to return the matched address in src */
{
	char		*endsrc, *endtar;
	long		n_match;
	register int	i;
	register long	n_ind;
	register char	**ind;
	static long	*N_index = NIL(long);
	static char	*Cursrc = NIL(char), ***Index = NIL(char**);
	static int	Alloced = 0;
	char		**malloc(), **realloc();

	/* free old inverted indices if necessary */
	if(src != Cursrc)
	{
		if(Alloced)
			freemem(N_index,Index);
		Alloced = 0;
		Cursrc = NIL(char);
	}

	/* nothing to do */
	if(!src || n_src <= 0 || !tar || n_tar <= 0)
		return 0;

	endsrc = src + n_src;
	endtar = tar + n_tar;

	/* build new index structure */
	if(src != Cursrc)
	{
		Cursrc = src;
		Alloced = 1;
		if(N_index = (long*) malloc(ALPHA*sizeof(long)))
		{
			register char	*sp;

			memzero((char*)N_index,ALPHA*sizeof(long));
			if(!(Index = (char ***) malloc(ALPHA*sizeof(char**))))
			{
				free(N_index);
				N_index = NIL(long);
				Alloced = 0;
			}
			else for(sp = src; sp < endsrc; ++sp)
			{
				i = (int)(*((unsigned char *)(sp)));
				ind = Index[i];
				n_ind = N_index[i];

				/* make sure we have space */
				if((n_ind%ALPHA) == 0)
				{
					ind = n_ind == 0 ?
					      malloc(ALPHA*sizeof(char *)) :
					      realloc(ind,(n_ind+ALPHA)*sizeof(char*));
					Index[i] = ind;
				}
				if(ind)
				{
					ind[n_ind] = sp;
					N_index[i] += 1;
				}
				else
				{
					freemem(N_index,Index);
					N_index = NIL(long);
					Index = NIL(char**);
					Alloced = 0;
					break;
				}
			}
		}
	}

	/* find longest matching prefix */
	i = (int)(*((unsigned char *)(tar)));
	ind   = Alloced ? Index[i] : NULL;
	n_ind = Alloced ? N_index[i] : -1;
	n_match = 0;
	while(1)
	{
		register long m;

		if(ind)
		{
			src = n_ind > 0 ? *ind++ : endsrc;
			n_ind -= 1;
		}
		else for(; src+n_match < endsrc; ++src)
			if(*src == *tar)
				break;
		if(src+n_match >= endsrc)
			break;

		if((m = domatch(src,endsrc,tar,endtar,n_match)) > n_match)
		{
			n_match = m;
			*match = src;
			if(tar+n_match >= endtar)
				break;
		}
	}

	return n_match;
}
0707070000000000041006440044230044230000010000000425126261700002500000017763suftree.cUgsfGgsf#define _IN_SUF_TREE
#include	"suftree.h"

/*
**	Construct a suffix tree for a source string
**	and perform string matching of various input strings.
**	This is based on the suffix tree algorithm of E. McCreight.
**	I extended the algorithm to remove the restriction that the
**	last element of the string has to be different from the rest
**	of the string. Note also that since the alphabet is large (256),
**	instead of being stored in an array, the children of a node
**	are kept in a linked list which is managed by a move-to-front
**	heuristic.
**
**	For details, see the paper:
**	"A Space-Economical Suffix Tree Construction Algorithm"
**	E.M. McCreight, JACM, v.23, No.2, 1976, pp.262-272.
**
**	BldSuftree returns either NULL or the pointer to the root of the
**	tree. In the latter case, the tree can be destroyed by free()-ing
**	the root.
**
**	Written by Kiem-Phong Vo, 5/20/88.
*/

/*	Delete a suffix tree */
void delsuftree(root)
Suftree	*root;
{
	if(!root)
		return;
	root -= 1;
	while(root)
	{
		register Suftree *next;
		next = NEXT(root);
		free(root);
		root = next;
	}
}

/* Find a child whose label string starts with a given character */
static Suftree	*child_find(node,c)
Suftree	*node;		/* the node whose children will be searched */
Element	c;		/* the element being looked for */
{
	register Suftree	*np, *last;

	last = NIL(Suftree);
	for(np = CHILD(node); np != NIL(Suftree); np = SIBLING(np))
		if(LENGTH(np) > 0 && *LABEL(np) == c)
			break;
		else	last = np;

	if(np && last)
	{
		/* move-to-front heuristic */
		SIBLING(last) = SIBLING(np);
		SIBLING(np) = CHILD(node);
		CHILD(node) = np;
	}
	return np;
}

/* Get space for tree nodes. */
static Suftree *getmem(root,n)
Suftree	*root;
int	n;
{
	Suftree	*list, *malloc(), **realloc();

	if((list = malloc((n+1)*sizeof(Suftree))) == NIL(Suftree))
	{
		if(root)
			delsuftree(root);
		return NIL(Suftree);
	}

	/* store where this list is for later deletion */
	NEXT(list) = NIL(Suftree);
	if(root)
	{
		for(root -= 1; NEXT(root) != NIL(Suftree); root = NEXT(root))
			;
		NEXT(root) = list;
	}

	return list+1;
}

/*	Build the tree.
**	Following are the meaning of a few important variables:
**		clocus: contracted locus, this variable defines the
**			tree node that points to the longest prefix
**			that terminates at a node in the current tree.
**		locus:	defines a tree node to be constructed that
**			points to the longest prefix that can be defined.
**			Unless both clocus and locus equal the root,
**			we maintain the invariance that clocus is the
**			parent of locus.
**		link:	defines the sublink of the locus of the prefix
**			of the previously inserted suffix.
*/
Suftree	*bldsuftree(src,len)
Element		*src;	/* the string to build the tree from */
long int	len;	/* the length of the string */
{
	register Element	*sp, *mp, *rescan, *endmatch, *endsrc;
	register Suftree	*match, *clocus, *locus, *link;
	register long int	mtlen, relen;
	register int		n;
	Suftree			*root, *list, *endlist;

	if(len == 0)
		return NIL(Suftree);

	/* get initial space for the tree nodes */
	root = NIL(Suftree);

	/* 2*len+1 is the maximum number of nodes that can be created */
	n = 2*len+1;
	if(n > ALLOCSIZE)
		n = ALLOCSIZE;
	if(!(list = getmem(root,n)))
		return NIL(Suftree);
	endlist = list + n;

	/* make root node */
	root = list++;
	LABEL(root) = NIL(Element);
	CHILD(root) = NIL(Suftree);
	LINK(root) = root;

	/* locus and contracted locus of the empty substring */
	locus = clocus = root;

	/* the current match length */
	mtlen = 0;

	/* the end of the source string */
	endsrc = src+len;

	/* now build the tree */
	for(; src < endsrc; ++src)
	{
		/* prepare for scanning the current suffix */
		if(locus != root)
		{
			/* define the string to be rescanned */
			rescan = LABEL(locus);
			relen  = LENGTH(locus);

			/* minus the first character of the previous prefix */
			if(clocus == root)
			{
				rescan++;
				if(relen > 0)
					--relen;
			}
			}
		else	mtlen = relen = 0;

		/* the length of the known-to-be-matched part */
		if(mtlen > 0)
			--mtlen;
		/**/ ASSERT(relen <= mtlen)

		/* use sublink to rescan */
		link = LINK(clocus);

		/* rescan */
		while(relen > 0)
		{
			/* find a child of link that starts with the
			   first character of rescan. We then know that
			   rescan must match a prefix of that child.
			*/
			match = child_find(link,*rescan);
			/**/ ASSERT(match != NULL)

			/* clocus will be the parent of the new link */
			clocus = link;

			/* rescan contains LABEL(match) */
			if(relen >= LENGTH(match))
			{
				link = match;
				relen -= LENGTH(match);
				rescan += LENGTH(match);
			}
			/* rescan is a proper prefix of LABEL(match) */
			else
			{
				if(list >= endlist)
				{
					if(!(list = getmem(root,ALLOCSIZE)))
						return NIL(Suftree);
					else	endlist = list+ALLOCSIZE;
				}

				/* make an internal node labeled with rescan */
				LABEL(list) = rescan;
				LENGTH(list) = relen;
				CHILD(list) = match;
				SIBLING(list) = SIBLING(match);
				LINK(list) = root;

				/* adjust label and pointer of old node */ 
				SIBLING(match) = NIL(Suftree);
				LABEL(match) += relen;
				LENGTH(match) -= relen;

				CHILD(link) = list;
				link = list++;
				break;
			}
		}

		/* define sublink for the prefix of the last suffix */
		if(locus != root)
			LINK(locus) = link;

		/* scan to match as much as possible */
		locus = link;
		sp = src + mtlen;
		while(sp < endsrc)
		{
			/* see if it matches some child of clocus */
			if(!(match = child_find(locus,*sp)))
				break;

			/* clocus will be the parent of the new locus */
			clocus = locus;

			/* find the extend of the match */
			mp = LABEL(match);
			endmatch = mp + LENGTH(match);
			for(; sp < endsrc && mp < endmatch; ++sp, ++mp)
				if(*sp != *mp)
					break;

			/* the whole node is matched */
			if(mp >= endmatch)
			{
				locus = match;
				mtlen += LENGTH(match);
			}
			/* found the extended locus of this suffix */
			else
			{
				if(list >= endlist)
				{
					if(!(list = getmem(root,ALLOCSIZE)))
						return NIL(Suftree);
					else	endlist = list+ALLOCSIZE;
				}

				/* make a new internal node */
				LABEL(list) = LABEL(match);
				LENGTH(list) = mp - LABEL(match);
				CHILD(list) = match;
				SIBLING(list) = SIBLING(match);
				LINK(list) = root;

				SIBLING(match) = NIL(Suftree);
				LABEL(match) += LENGTH(list);
				LENGTH(match) -= LENGTH(list);
				mtlen += LENGTH(list);

				/* the new node is the locus for this suffix */
				CHILD(locus) = list;
				locus = list++;
				break;
			}
		}

		if(list >= endlist)
		{
			if(!(list = getmem(root,ALLOCSIZE)))
				return NIL(Suftree);
			else	endlist = list+ALLOCSIZE;
		}

		/* make a new external node for the suffix */
		SUFFIX(list) = src;
		LABEL(list) = sp;
		LENGTH(list) = endsrc-sp;
		CHILD(list) = NIL(Suftree);

		/* hook it in as the first child of locus */
		SIBLING(list) = CHILD(locus);
		CHILD(locus) = list++;
	}

	return root;
}

/*	Given a raw string and a string represented in a suffix tree,
	match the string against the tree to find a longest matching
	prefix of the string.
	Return the length of the match and where it occurs in the
	string represented by the tree.
*/
long	mtchsuftree(tree,str,len,mtchp)
Suftree	*tree;		/* the root of the suffix tree */
Element	*str;		/* the string to be matched */
long	len;		/* the length of the string */
Element	**mtchp;	/* to return the address of the match */
{
	register Suftree	*match;
	register Element	*sp, *mp, *endmp, *endstr;
	register long		mlen;

	mlen = 0;
	endstr = str + len;
	while(1)
	{
		if(!(match = child_find(tree,*str)))
			break;

		/* find the extent of the match */
		mp = LABEL(match);
		endmp = mp + LENGTH(match);
		for(sp = str; sp < endstr && mp < endmp; ++sp, ++mp)
			if(*sp != *mp)
				break;

		/* update the length of the match */
		mlen += sp-str;

		/* prepare for next iteration */
		tree = match;
		str  = sp;

		/* see if we have to work any more */
		if(mp < endmp || str >= endstr)
			break; 
	}

	if(mlen == 0)	/* no match */
		*mtchp = NIL(Element);
	else
	{
		/* find where the match starts */
		while(CHILD(tree))
			tree = CHILD(tree);
		*mtchp = SUFFIX(tree);
	}

	return mlen;
}
0707070000000000051006440044230044230000010000000425126261700002500000002273suftree.hUgsfGgsf/* the type of list elements we play with */
typedef char	Element;

/* for suffix trees, a tree node looks like this */
typedef struct _ts_
{
	Element		*_label;	/* substring labeling the edge */
	long int	_length;	/* the length of the string */
	struct _ts_	*_child;	/* list of children */
	struct _ts_	*_sibling;	/* link for the child list */
	union
	{	/* these two fields are mutual exclusive */
		struct _ts_	*_link;		/* sub-link */
		Element		*_suffix;	/* suffix */
	}	_uls_;
}	Suftree;

/* short hand for various fields in a tree node */
#define	LABEL(n)	((n)->_label)
#define LENGTH(n)	((n)->_length)
#define CHILD(n)	((n)->_child)
#define SIBLING(n)	((n)->_sibling)
#define LINK(n)		((n)->_uls_._link)
#define SUFFIX(n)	((n)->_uls_._suffix)

extern Suftree	*bldsuftree();
extern long	mtchsuftree();


/* the following definitions are not to be seen by users */
#ifdef _IN_SUF_TREE
#ifdef DEBUG
#define ASSERT(p)	if(!(p)) abort();
#else
#define ASSERT(p)
#endif /*DEBUG*/

#ifndef NULL
#define NULL	(0L)
#endif /*NULL*/

#ifndef NIL
#define NIL(type)	((type*)NULL)
#endif /*NIL*/

#define ALLOCSIZE	256	/* amount of nodes to allocate each time */
#define NEXT(n)		((n)->_sibling)

#endif /*_IN_SUF_TREE*/
0707070000000000061006440044230044230000010000000425126261700002400000007231update.cUgsfGgsf#include	"update.h"

/*
**	Reconstruct a target file from a source file and a delta file.
**	The delta file contain block move instructions computed by delta().
**
**	Written by Kiem-Phong Vo, 5/20/88
*/

/* buffers for delta and target files */
static unsigned char	*Ddata, *Dnext, *Dend,
			*Tdata, *Tnext, *Tend;
static int		Dfd, Tfd;

#define delinit(buf,size,fd)	(Ddata=Dnext=Dend=buf, Dfd=fd)
#define tarinit(buf,size,fd)	(Tdata=Tnext=buf, Tend=buf+size, Tfd=fd)
#define tarflush()	(write(Tfd,Tdata,Tnext-Tdata) >= 0 ? (Tnext=Tdata,0) : -1)

/* read a byte from delta file */
static int delgetc()
{
	if(Dnext >= Dend)
	{
		register int n;
		if((n = read(Dfd,Ddata,BUFSIZE)) <= 0)
			return -1;
		Dnext = Ddata, Dend = Ddata+n;
	}
	return (int)(*Dnext++);
}

/* read a long value from delta file */
static long delgetl(n)
register int	n;
{
	register long	lv;

	lv = 0;
	for(; n > 0; --n)
	{
		register int v;
		if((v = delgetc()) < 0)
			return -1;
		lv = lv*256 + v;
	}
	return lv;
}

/* transfer a number of bytes from a file to the target file */
static int filetransfer(fd,n)
int	fd;
long	n;
{
	while(n > 0)
	{
		register int r;

		if(Tnext >= Tend)
			if(tarflush() < 0)
				return -1;
		r = n > (Tend-Tnext) ? (Tend-Tnext) : n;
		if(read(fd,Tnext,r) != r)
			return -1;
		Tnext += r;
		n -= r;
	}
	return 0;
}

/* transfer a number of bytes from a memory area to the target file */
static int memtransfer(addr,n)
unsigned char	*addr;
register long	n;
{
	while(n > 0)
	{
		register int r;

		if(Tnext >= Tend)
			if(tarflush() < 0)
				return -1;
		r = n > (Tend-Tnext) ? (Tend-Tnext) : n;
		memcopy(Tnext,addr,r);
		Tnext += r;
		addr += r;
		n -= r;
	}
	return 0;
}

/* transfer a number of bytes from delta to target */
static int deltransfer(n)
long	n;
{
	register int d;

	/* transfer what's already in core */
	if((d = Dend-Dnext) > 0)
	{
		register int w = n <= d ? n : d;

		if(w > (Tend-Tnext))
			if(tarflush() < 0)
				return -1;

		/* copy from the delta buffer */
		memcopy(Tnext,Dnext,w);
		Dnext += w;
		Tnext += w;
		n -= w;
	}

	return n > 0 ? filetransfer(Dfd,n) : 0;
}

update(srcfd,offset,delfd,tarfd)
int	srcfd;
long	offset;
int	delfd;
int	tarfd;
{
	register int	i;
	register long	n_src, n_tar;
	unsigned char	delbuf[BUFSIZE], tarbuf[BUFSIZE];
	unsigned char	*src, *tar, *malloc();

	/* start buffering system for delta file */
	delinit(delbuf,BUFSIZE,delfd);

	/* read the file sizes */
	if((i = delgetc()) < 0 || (i&DELTA_TYPE) != DELTA_TYPE)
		return -1;
	if((n_src = delgetl((i>>3)&07)) < 0 || (n_tar = delgetl(i&07)) < 0)
		return -1;

	/* make data area for target file */
	if(tar = malloc(n_tar)) /* assignment = */
		tarinit(tar,n_tar,tarfd);
	else	tarinit(tarbuf,BUFSIZE,tarfd);

	/* read in source file if possible to avoid lseek */
	if(src = malloc(n_src)) /* assignment = */
	{
		lseek(srcfd,offset,0);
		if(read(srcfd,src,n_src) != n_src)
			return -1;
	}

	while((i = delgetc()) >= 0)
	{
		register long	size, addr;

		if((size = delgetl((i>>3)&07)) < 0)
			return -1;
		switch(i&DELTA_TYPE)
		{
		default :
			return -1;
		case DELTA_TYPE :
			/* sync delta file pointer */ 
			if((addr = Dend-Dnext) > 0)
				lseek(Dfd,-addr,1);
			/* flush output buffer */
			if(tarflush() < 0)
				return -1;
			/* free space used */
			if(src)
				free(src);
			if(tar)
				free(tar);
			return 0;
		case DELTA_MOVE :
			if((addr = delgetl(i&07)) < 0)
				return -1;
			if(src)
			{
				if(memtransfer(src+addr,size) < 0)
					return -1;
			}
			else
			{
				if(lseek(srcfd,offset+addr,0) < 0)
					return -1;
				if(filetransfer(srcfd,size) < 0)
					return -1;
			}
			break;
		case DELTA_ADD :
			if(deltransfer(size) < 0)
				return -1;
			break;
		}
	}

	/* should never get here */
	return -1;
}
0707070000000000071006440044230044230000010000000425126261700002400000001253update.hUgsfGgsf/* values for the instruction field */
#define DELTA_TYPE	0300
#define DELTA_MOVE	0200
#define DELTA_ADD	0100

/* number of bytes required to code a value */
#define BASE		256
#define ONE		(BASE)
#define TWO		(BASE*BASE)
#define THREE		(BASE*BASE*BASE)
#define NBYTE(v)	((v) < ONE ? 1 : ((v) < TWO ? 2 : ((v) < THREE ? 3 : 4)))

#define BUFSIZE	2048

#ifndef NULL
#define NULL	(0L)
#endif

#ifndef NIL
#define NIL(type)	((type*)NULL)
#endif

/* function to copy data from one area to another */
#ifdef	SYSV
#define memcopy(to,fr,n)	memcpy(to,fr,n)
#define memzero(s,n)		memset(s,0,n)
#endif

#ifdef BSD
#define memcopy(to,fr,n)	bcopy(fr,to,n)
#define memzero(s,n)		bzero(s,n)
#endif
0707070000000000101006440044230044230000010000000475460055300002300000003501MamfileUgsfGgsfnote # # make abstract machine file generated from Makefile # #
setv AS as
setv ASFLAGS
setv AR ar
setv ARFLAGS cr
setv CC cc
setv CCFLAGS "-O"
setv CPP "$CC -E"
setv CPIO cpio
setv CPIOFLAGS
setv F77 f77
setv INSTALLROOT $HOME
setv LD ld
setv LDFLAGS 
setv LEX lex
setv LEXFLAGS
setv LPR lpr
setv LPRFLAGS
setv M4FLAGS 
setv MAKE nmake
setv MAKEFLAGS
setv PR pr
setv PRFLAGS
setv TAR tar
setv YACC yacc
setv YACCFLAGS -d
make install
make all
make libodelta.a
attr arch
make delta.o
make delta.c
attr perm
attr scan
make suftree.h
attr perm
attr scan
attr impl
done suftree.h
make update.h
attr perm
attr scan
attr impl
done update.h
done delta.c
prev delta.c
setv SYSV -DSYSV
exec $CC $CCFLAGS -I. "$SYSV" -c delta.c
done delta.o
make mtchstring.o
make mtchstring.c
attr perm
attr scan
prev update.h
done mtchstring.c
prev mtchstring.c
exec $CC $CCFLAGS -I. "$SYSV" -c mtchstring.c
done mtchstring.o
make suftree.o
make suftree.c
attr perm
attr scan
prev suftree.h
done suftree.c
prev suftree.c
exec $CC $CCFLAGS -I.  -c suftree.c
done suftree.o
make update.o
make update.c
attr perm
attr scan
prev update.h
done update.c
prev update.c
exec $CC $CCFLAGS -I. "$SYSV" -c update.c
done update.o
exec $AR cr libodelta.a delta.o mtchstring.o suftree.o update.o
exec (ranlib libodelta.a) >/dev/null 2>&1 || true
done libodelta.a
done all
make $INSTALLROOT/lib
exec if	 test ! -d $INSTALLROOT/lib
.... then	rm -rf $INSTALLROOT/lib && mkdir  $INSTALLROOT/lib  		    		    || { rm -rf $INSTALLROOT && mkdir  $INSTALLROOT && mkdir  $INSTALLROOT/lib  		    		    ;} || true
.... fi
done $INSTALLROOT/lib
make $INSTALLROOT/lib/libodelta.a
attr arch
prev libodelta.a
exec { cp libodelta.a $INSTALLROOT/lib/libodelta.a 2>/dev/null  		    		    ;} || true
exec (ranlib $INSTALLROOT/lib/libodelta.a) >/dev/null 2>&1 || true
done $INSTALLROOT/lib/libodelta.a
done install
0707070000000000000000000000000000000000010000000000000000000001300000000000TRAILER!!!