arclzw.c

汇编源代码大全

	if ((i -= disp) < 0)
		i += HSIZE;

	if (htab[i] == fcode) {
		ent = codetab[i];
		return;
	}
	if (htab[i] > 0)
		goto probe;

nomatch:
	putcode(ent, t);
	ent = c;
	if (free_ent < maxcodemax) {
		codetab[i] = free_ent++;	/* code -> hashtable */
		htab[i] = fcode;
	}
	if (in_count >= checkpoint)
		cl_block(t);	/* check for adaptive reset */
}

long
pred_cm(t)			/* finish compressing a file */
	FILE           *t;	/* where to put it */
{
	putcode(ent, t);	/* put out the final code */
	putcode(-1, t);		/* tell output we are done */

	return bytes_out;	/* say how big it got */
}

/*
 * Decompress a file.  This routine adapts to the codes in the file building
 * the string table on-the-fly; requiring no table to be stored in the
 * compressed file.  The tables used herein are shared with those of the
 * compress() routine.  See the definitions above.
 */

void
decomp(f, t)			/* decompress a file */
	FILE           *f;	/* file to read codes from */
	FILE           *t;	/* file to write text to */
{
	unsigned char  *stackp;
	int             finchar;
	int             code, oldcode, incode;

	if ((code = getc_unp(f)) != BITS)
		abort("File packed with %d bits, I can only handle %d", code, BITS);

	n_bits = INIT_BITS;	/* set starting code size */
	clear_flg = 0;

	/*
	 * As above, initialize the first 256 entries in the table. 
	 */
	maxcode = MAXCODE(n_bits = INIT_BITS);
	setmem(prefix, 256 * sizeof(short), 0);	/* reset decode string table */
	for (code = 255; code >= 0; code--)
		suffix[code] = (unsigned char) code;

	free_ent = FIRST;

	finchar = oldcode = getcode(f);
	if (oldcode == -1)	/* EOF already? */
		return;		/* Get out of here */
	putc_ncr((unsigned char) finchar, t);	/* first code must be 8 bits=char */
	stackp = stack;

	while ((code = getcode(f)) > -1) {
		if (code == CLEAR) {	/* reset string table */
			setmem(prefix, 256 * sizeof(short), 0);
			clear_flg = 1;
			free_ent = FIRST - 1;
			if ((code = getcode(f)) == -1)	/* O, untimely death! */
				break;
		}
		incode = code;
		/*
		 * Special case for KwKwK string. 
		 */
		if (code >= free_ent) {
			if (code > free_ent) {
				if (warn) {
					printf("Corrupted compressed file.\n");
					printf("Invalid code %d when max is %d.\n",
						code, free_ent);
				}
				nerrs++;
				return;
			}
			*stackp++ = finchar;
			code = oldcode;
		}
		/*
		 * Generate output characters in reverse order 
		 */
		while (code >= 256) {
			*stackp++ = suffix[code];
			code = prefix[code];
		}
		*stackp++ = finchar = suffix[code];

		/*
		 * And put them out in forward order 
		 */
		do
			putc_ncr(*--stackp, t);
		while (stackp > stack);

		/*
		 * Generate the new entry. 
		 */
		if ((code = free_ent) < maxcodemax) {
			prefix[code] = (unsigned short) oldcode;
			suffix[code] = finchar;
			free_ent = code + 1;
		}
		/*
		 * Remember previous code. 
		 */
		oldcode = incode;
	}
}


/*************************************************************************
 * Please note how much trouble it can be to maintain upwards            *
 * compatibility.  All that follows is for the sole purpose of unpacking *
 * files which were packed using an older method.                        *
 *************************************************************************/


/*
 * The h() pointer points to the routine to use for calculating a hash value.
 * It is set in the init routines to point to either of oldh() or newh().
 * 
 * oldh() calculates a hash value by taking the middle twelve bits of the square
 * of the key.
 * 
 * newh() works somewhat differently, and was tried because it makes ARC about
 * 23% faster.  This approach was abandoned because dynamic Lempel-Zev
 * (above) works as well, and packs smaller also.  However, inadvertent
 * release of a developmental copy forces us to leave this in.
 */

static unsigned short(*h) ();	/* pointer to hash function */

static unsigned short
oldh(pred, foll)		/* old hash function */
	unsigned short  pred;	/* code for preceeding string */
	unsigned char   foll;	/* value of following char */
{
	long            local;	/* local hash value */

	local = ((pred + foll) | 0x0800) & 0xFFFF; /* create the hash key */
	local *= local;		/* square it */
	return (local >> 6) & 0x0FFF;	/* return the middle 12 bits */
}

static unsigned short
newh(pred, foll)		/* new hash function */
	unsigned short  pred;	/* code for preceeding string */
	unsigned char   foll;	/* value of following char */
{
	return (((pred + foll) & 0xFFFF) * 15073) & 0xFFF; /* faster hash */
}

/*
 * The eolist() function is used to trace down a list of entries with
 * duplicate keys until the last duplicate is found.
 */

static unsigned short
eolist(index)			/* find last duplicate */
	unsigned short  index;
{
	int             temp;

	while (temp = string_tab[index].next)	/* while more duplicates */
		index = temp;

	return index;
}

/*
 * The hash() routine is used to find a spot in the hash table for a new
 * entry.  It performs a "hash and linear probe" lookup, using h() to
 * calculate the starting hash value and eolist() to perform the linear
 * probe.  This routine DOES NOT detect a table full condition.  That MUST be
 * checked for elsewhere.
 */

static unsigned short
hash(pred, foll)		/* find spot in the string table */
	unsigned short  pred;	/* code for preceeding string */
	unsigned char   foll;	/* char following string */
{
	unsigned short  local, tempnext;	/* scratch storage */
	struct entry   *ep;	/* allows faster table handling */

	local = (*h) (pred, foll);	/* get initial hash value */

	if (!string_tab[local].used)	/* if that spot is free */
		return local;	/* then that's all we need */

	else {			/* else a collision has occured */
		local = eolist(local);	/* move to last duplicate */

		/*
		 * We must find an empty spot. We start looking 101 places
		 * down the table from the last duplicate. 
		 */

		tempnext = (local + 101) & 0x0FFF;
		ep = &string_tab[tempnext];	/* initialize pointer */

		while (ep->used) {	/* while empty spot not found */
			if (++tempnext == TABSIZE) {	/* if we are at the end */
				tempnext = 0;	/* wrap to beginning of table */
				ep = string_tab;
			} else
				++ep;	/* point to next element in table */
		}

		/*
		 * local still has the pointer to the last duplicate, while
		 * tempnext has the pointer to the spot we found.  We use
		 * this to maintain the chain of pointers to duplicates. 
		 */

		string_tab[local].next = tempnext;

		return tempnext;
	}
}

/*
 * The init_tab() routine is used to initialize our hash table. You realize,
 * of course, that "initialize" is a complete misnomer.
 */

static          void
init_tab()
{				/* set ground state in hash table */
	unsigned int    i;	/* table index */

	setmem((char *) string_tab, sizeof(string_tab), 0);

	for (i = 0; i < 256; i++)	/* list all single byte strings */
		upd_tab(NO_PRED, i);

	inbuf = EMPTY;		/* nothing is in our buffer */
}

/*
 * The upd_tab routine is used to add a new entry to the string table. As
 * previously stated, no checks are made to ensure that the table has any
 * room.  This must be done elsewhere.
 */

void
upd_tab(pred, foll)		/* add an entry to the table */
	unsigned short  pred;	/* code for preceeding string */
	unsigned short  foll;	/* character which follows string */
{
	struct entry   *ep;	/* pointer to current entry */

	/* calculate offset just once */

	ep = &string_tab[hash(pred, foll)];

	ep->used = TRUE;	/* this spot is now in use */
	ep->next = 0;		/* no duplicates after this yet */
	ep->predecessor = pred;	/* note code of preceeding string */
	ep->follower = foll;	/* note char after string */
}

/*
 * This algorithm encoded a file into twelve bit strings (three nybbles). The
 * gocode() routine is used to read these strings a byte (or two) at a time.
 */

static          int
gocode(fd)			/* read in a twelve bit code */
	FILE           *fd;	/* file to get code from */
{
	unsigned short  localbuf, returnval;
	int             temp;

	if (inbuf == EMPTY) {	/* if on a code boundary */
		if ((temp = getc_unp(fd)) == EOF)	/* get start of next
							 * code */
			return EOF;	/* pass back end of file status */
		localbuf = temp & 0xFF;	/* mask down to true byte value */
		if ((temp = getc_unp(fd)) == EOF)
			/* get end of code, * start of next */
			return EOF;	/* this should never happen */
		inbuf = temp & 0xFF;	/* mask down to true byte value */

		returnval = ((localbuf << 4) & 0xFF0) + ((inbuf >> 4) & 0x00F);
		inbuf &= 0x000F;/* leave partial code pending */
	} else {		/* buffer contains first nybble */
		if ((temp = getc_unp(fd)) == EOF)
			return EOF;
		localbuf = temp & 0xFF;

		returnval = localbuf + ((inbuf << 8) & 0xF00);
		inbuf = EMPTY;	/* note no hanging nybbles */
	}
	return returnval;	/* pass back assembled code */
}

static          void
push(c)				/* push char onto stack */
	int             c;	/* character to push */
{
	stack[sp] = ((char) c);	/* coerce integer into a char */

	if (++sp >= TABSIZE)
		abort("Stack overflow\n");
}

static          int
pop()
{				/* pop character from stack */
	if (sp > 0)
		return ((int) stack[--sp]);	/* leave ptr at next empty
						 * slot */

	else
		return EMPTY;
}

/***** LEMPEL-ZEV DECOMPRESSION *****/

static int      code_count;	/* needed to detect table full */
static int      firstc;		/* true only on first character */

void
init_ucr(new)			/* get set for uncrunching */
	int             new;	/* true to use new hash function */
{
	if (new)		/* set proper hash function */
		h = newh;
	else
		h = oldh;

	sp = 0;			/* clear out the stack */
	init_tab();		/* set up atomic code definitions */
	code_count = TABSIZE - 256;	/* note space left in table */
	firstc = 1;		/* true only on first code */
}

int
getc_ucr(f)			/* get next uncrunched byte */
	FILE           *f;	/* file containing crunched data */
{
	int             code, newcode;
	static int      oldcode, finchar;
	struct entry   *ep;	/* allows faster table handling */

	if (firstc) {		/* first code is always known */
		firstc = FALSE;	/* but next will not be first */
		oldcode = gocode(f);
		return finchar = string_tab[oldcode].follower;
	}
	if (!sp) {		/* if stack is empty */
		if ((code = newcode = gocode(f)) == EOF)
			return EOF;

		ep = &string_tab[code];	/* initialize pointer */

		if (!ep->used) {/* if code isn't known */
			code = oldcode;
			ep = &string_tab[code];	/* re-initialize pointer */
			push(finchar);
		}
		while (ep->predecessor != NO_PRED) {
			push(ep->follower);	/* decode string backwards */
			code = ep->predecessor;
			ep = &string_tab[code];
		}

		push(finchar = ep->follower);	/* save first character also */

		/*
		 * The above loop will terminate, one way or another, with
		 * string_tab[code].follower equal to the first character in
		 * the string. 
		 */

		if (code_count) {	/* if room left in string table */
			upd_tab(oldcode, finchar);
			--code_count;
		}
		oldcode = newcode;
	}
	return pop();		/* return saved character */
}