deflate.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

		 * we have a new best match.
		 * extend it to it's maximum length
		 */
		t += runlen + 2;
		s += runlen + 2;
		for(; s < es; s++){
			if(*s != *t)
				break;
			t++;
		}
		runlen = s - p;
		*m = off - 1;
		if(s == es || runlen > ml)
			break;
matchloop:;
		last = off;
	}
	return runlen;
}

static int
lzcomp(LZstate *lz, LZblock *lzb, uchar *ep, ushort *parse, int finish)
{
	ulong cont, excost, *litlencount, *offcount;
	uchar *p, *q, *s, *es;
	ushort *nexts, *hash;
	int v, i, h, runlen, n, now, then, m, prevlen, prevoff, maxdefer;

	litlencount = lzb->litlencount;
	offcount = lzb->offcount;
	nexts = lz->nexts;
	hash = lz->hash;
	now = lz->now;

	p = &lz->hist[lz->pos];
	if(lz->prevlen != MinMatch - 1)
		p++;

	/*
	 * hash in the links for any hanging link positions,
	 * and calculate the hash for the current position.
	 */
	n = MinMatch;
	if(n > ep - p)
		n = ep - p;
	cont = 0;
	for(i = 0; i < n - 1; i++){
		m = now - ((MinMatch-1) - i);
		if(m < lz->dot)
			continue;
		s = lz->hist + (((p - lz->hist) - (now - m)) & (HistBlock-1));

		cont = (s[0] << 16) | (s[1] << 8) | s[2];
		h = hashit(cont);
		prevoff = 0;
		for(then = hash[h]; ; then = nexts[then & (MaxOff-1)]){
			v = (ushort)(now - then);
			if(v <= prevoff || v >= (MinMatch-1) - i)
				break;
			prevoff = v;
		}
		if(then == (ushort)m)
			continue;
		nexts[m & (MaxOff-1)] = hash[h];
		hash[h] = m;
	}
	for(i = 0; i < n; i++)
		cont = (cont << 8) | p[i];

	/*
	 * now must point to the index in the nexts array
	 * corresponding to p's position in the history
	 */
	prevlen = lz->prevlen;
	prevoff = lz->prevoff;
	maxdefer = lz->maxcheck >> 2;
	excost = 0;
	v = lzb->lastv;
	for(;;){
		es = p + MaxMatch;
		if(es > ep){
			if(!finish || p >= ep)
				break;
			es = ep;
		}

		h = hashit(cont);
		runlen = lzmatch(now, hash[h], p, es, nexts, lz->hist, prevlen, lz->maxcheck, &m);

		/*
		 * back out of small matches too far in the past
		 */
		if(runlen == MinMatch && m >= MinMatchMaxOff){
			runlen = MinMatch - 1;
			m = 0;
		}

		/*
		 * record the encoding and increment counts for huffman trees
		 * if we get a match, defer selecting it until we check for
		 * a longer match at the next position.
		 */
		if(prevlen >= runlen && prevlen != MinMatch - 1){
			/*
			 * old match at least as good; use that one
			 */
			n = prevlen - MinMatch;
			if(v || n){
				*parse++ = v | LenFlag | (n << LenShift);
				*parse++ = prevoff;
			}else
				*parse++ = prevoff << LenShift;
			v = 0;

			n = lencode[n];
			litlencount[n]++;
			excost += litlenextra[n - LenStart];

			if(prevoff < MaxOffCode)
				n = offcode[prevoff];
			else
				n = bigoffcode[prevoff >> 7];
			offcount[n]++;
			excost += offextra[n];

			runlen = prevlen - 1;
			prevlen = MinMatch - 1;
			nmatches++;
		}else if(runlen == MinMatch - 1){
			/*
			 * no match; just put out the literal
			 */
			if(++v == MaxLitRun){
				*parse++ = v;
				v = 0;
			}
			litlencount[*p]++;
			nlits++;
			runlen = 1;
		}else{
			if(prevlen != MinMatch - 1){
				/*
				 * longer match now. output previous literal,
				 * update current match, and try again
				 */
				if(++v == MaxLitRun){
					*parse++ = v;
					v = 0;
				}
				litlencount[p[-1]]++;
				nlits++;
			}

			prevoff = m;

			if(runlen < maxdefer){
				prevlen = runlen;
				runlen = 1;
			}else{
				n = runlen - MinMatch;
				if(v || n){
					*parse++ = v | LenFlag | (n << LenShift);
					*parse++ = prevoff;
				}else
					*parse++ = prevoff << LenShift;
				v = 0;

				n = lencode[n];
				litlencount[n]++;
				excost += litlenextra[n - LenStart];

				if(prevoff < MaxOffCode)
					n = offcode[prevoff];
				else
					n = bigoffcode[prevoff >> 7];
				offcount[n]++;
				excost += offextra[n];

				prevlen = MinMatch - 1;
				nmatches++;
			}
		}

		/*
		 * update the hash for the newly matched data
		 * this is constructed so the link for the old
		 * match in this position must be at the end of a chain,
		 * and will expire when this match is added, ie it will
		 * never be examined by the match loop.
		 * add to the hash chain only if we have the real hash data.
		 */
		for(q = p + runlen; p != q; p++){
			if(p + MinMatch <= ep){
				h = hashit(cont);
				nexts[now & (MaxOff-1)] = hash[h];
				hash[h] = now;
				if(p + MinMatch < ep)
					cont = (cont << 8) | p[MinMatch];
			}
			now++;
		}
	}

	/*
	 * we can just store away the lazy state and
	 * pick it up next time.  the last block will have finish set
	 * so we won't have any pending matches
	 * however, we need to correct for how much we've encoded
	 */
	if(prevlen != MinMatch - 1)
		p--;

	lzb->excost += excost;
	lzb->eparse = parse;
	lzb->lastv = v;

	lz->now = now;
	lz->prevlen = prevlen;
	lz->prevoff = prevoff;

	return p - &lz->hist[lz->pos];
}

/*
 * make up the dynamic code tables, and return the number of bits
 * needed to transmit them.
 */
static int
huffcodes(Dyncode *dc, Huff *littab, Huff *offtab)
{
	Huff *codetab;
	uchar *codes, *codeaux;
	ulong codecount[Nclen], excost;
	int i, n, m, v, c, nlit, noff, ncode, nclen;

	codetab = dc->codetab;
	codes = dc->codes;
	codeaux = dc->codeaux;

	/*
	 * trim the sizes of the tables
	 */
	for(nlit = Nlitlen; nlit > 257 && littab[nlit-1].bits == 0; nlit--)
		;
	for(noff = Noff; noff > 1 && offtab[noff-1].bits == 0; noff--)
		;

	/*
	 * make the code-length code
	 */
	for(i = 0; i < nlit; i++)
		codes[i] = littab[i].bits;
	for(i = 0; i < noff; i++)
		codes[i + nlit] = offtab[i].bits;

	/*
	 * run-length compress the code-length code
	 */
	excost = 0;
	c = 0;
	ncode = nlit+noff;
	for(i = 0; i < ncode; ){
		n = i + 1;
		v = codes[i];
		while(n < ncode && v == codes[n])
			n++;
		n -= i;
		i += n;
		if(v == 0){
			while(n >= 11){
				m = n;
				if(m > 138)
					m = 138;
				codes[c] = 18;
				codeaux[c++] = m - 11;
				n -= m;
				excost += 7;
			}
			if(n >= 3){
				codes[c] = 17;
				codeaux[c++] = n - 3;
				n = 0;
				excost += 3;
			}
		}
		while(n--){
			codes[c++] = v;
			while(n >= 3){
				m = n;
				if(m > 6)
					m = 6;
				codes[c] = 16;
				codeaux[c++] = m - 3;
				n -= m;
				excost += 3;
			}
		}
	}

	memset(codecount, 0, sizeof codecount);
	for(i = 0; i < c; i++)
		codecount[codes[i]]++;
	if(!mkgzprecode(codetab, codecount, Nclen, 8))
		return -1;

	for(nclen = Nclen; nclen > 4 && codetab[clenorder[nclen-1]].bits == 0; nclen--)
		;

	dc->nlit = nlit;
	dc->noff = noff;
	dc->nclen = nclen;
	dc->ncode = c;

	return 5 + 5 + 4 + nclen * 3 + bitcost(codetab, codecount, Nclen) + excost;
}

static void
wrdyncode(LZstate *out, Dyncode *dc)
{
	Huff *codetab;
	uchar *codes, *codeaux;
	int i, v, c;

	/*
	 * write out header, then code length code lengths,
	 * and code lengths
	 */
	lzput(out, dc->nlit-257, 5);
	lzput(out, dc->noff-1, 5);
	lzput(out, dc->nclen-4, 4);

	codetab = dc->codetab;
	for(i = 0; i < dc->nclen; i++)
		lzput(out, codetab[clenorder[i]].bits, 3);

	codes = dc->codes;
	codeaux = dc->codeaux;
	c = dc->ncode;
	for(i = 0; i < c; i++){
		v = codes[i];
		lzput(out, codetab[v].encode, codetab[v].bits);
		if(v >= 16){
			if(v == 16)
				lzput(out, codeaux[i], 2);
			else if(v == 17)
				lzput(out, codeaux[i], 3);
			else /* v == 18 */
				lzput(out, codeaux[i], 7);
		}
	}
}

static int
bitcost(Huff *tab, ulong *count, int n)
{
	ulong tot;
	int i;

	tot = 0;
	for(i = 0; i < n; i++)
		tot += count[i] * tab[i].bits;
	return tot;
}

static int
mkgzprecode(Huff *tab, ulong *count, int n, int maxbits)
{
	ulong bitcount[MaxHuffBits];
	int i, nbits;

	nbits = mkprecode(tab, count, n, maxbits, bitcount);
	for(i = 0; i < n; i++){
		if(tab[i].bits == -1)
			tab[i].bits = 0;
		else if(tab[i].bits == 0){
			if(nbits != 0 || bitcount[0] != 1)
				return 0;
			bitcount[1] = 1;
			bitcount[0] = 0;
			nbits = 1;
			tab[i].bits = 1;
		}
	}
	if(bitcount[0] != 0)
		return 0;
	return hufftabinit(tab, n, bitcount, nbits);
}

static int
hufftabinit(Huff *tab, int n, ulong *bitcount, int nbits)
{
	ulong code, nc[MaxHuffBits];
	int i, bits;

	code = 0;
	for(bits = 1; bits <= nbits; bits++){
		code = (code + bitcount[bits-1]) << 1;
		nc[bits] = code;
	}

	for(i = 0; i < n; i++){
		bits = tab[i].bits;
		if(bits){
			code = nc[bits]++ << (16 - bits);
			if(code & ~0xffff)
				return 0;
			tab[i].encode = revtab[code >> 8] | (revtab[code & 0xff] << 8);
		}
	}
	return 1;
}


/*
 * this should be in a library
 */
struct Chain
{
	ulong	count;				/* occurances of everything in the chain */
	ushort	leaf;				/* leaves to the left of chain, or leaf value */
	char	col;				/* ref count for collecting unused chains */
	char	gen;				/* need to generate chains for next lower level */
	Chain	*up;				/* Chain up in the lists */
};

struct Chains
{
	Chain	*lists[(MaxHuffBits - 1) * 2];
	ulong	leafcount[MaxLeaf];		/* sorted list of leaf counts */
	ushort	leafmap[MaxLeaf];		/* map to actual leaf number */
	int	nleaf;				/* number of leaves */
	Chain	chains[ChainMem];
	Chain	*echains;
	Chain	*free;
	char	col;
	int	nlists;
};

/*
 * fast, low space overhead algorithm for max depth huffman type codes
 *
 * J. Katajainen, A. Moffat and A. Turpin, "A fast and space-economical
 * algorithm for length-limited coding," Proc. Intl. Symp. on Algorithms
 * and Computation, Cairns, Australia, Dec. 1995, Lecture Notes in Computer
 * Science, Vol 1004, J. Staples, P. Eades, N. Katoh, and A. Moffat, eds.,
 * pp 12-21, Springer Verlag, New York, 1995.
 */
static int
mkprecode(Huff *tab, ulong *count, int n, int maxbits, ulong *bitcount)
{
	Chains cs;
	Chain *c;
	int i, m, em, bits;

	/*
	 * set up the sorted list of leaves
	 */
	m = 0;
	for(i = 0; i < n; i++){
		tab[i].bits = -1;
		tab[i].encode = 0;
		if(count[i] != 0){
			cs.leafcount[m] = count[i];
			cs.leafmap[m] = i;
			m++;
		}
	}
	if(m < 2){
		if(m != 0){
			tab[cs.leafmap[0]].bits = 0;
			bitcount[0] = 1;
		}else
			bitcount[0] = 0;
		return 0;
	}
	cs.nleaf = m;
	leafsort(cs.leafcount, cs.leafmap, 0, m);

	for(i = 0; i < m; i++)
		cs.leafcount[i] = count[cs.leafmap[i]];

	/*
	 * set up free list
	 */
	cs.free = &cs.chains[2];
	cs.echains = &cs.chains[ChainMem];
	cs.col = 1;

	/*
	 * initialize chains for each list
	 */
	c = &cs.chains[0];
	c->count = cs.leafcount[0];
	c->leaf = 1;
	c->col = cs.col;
	c->up = nil;
	c->gen = 0;
	cs.chains[1] = cs.chains[0];
	cs.chains[1].leaf = 2;
	cs.chains[1].count = cs.leafcount[1];
	for(i = 0; i < maxbits-1; i++){
		cs.lists[i * 2] = &cs.chains[0];
		cs.lists[i * 2 + 1] = &cs.chains[1];
	}

	cs.nlists = 2 * (maxbits - 1);
	m = 2 * m - 2;
	for(i = 2; i < m; i++)
		nextchain(&cs, cs.nlists - 2);

	bits = 0;
	bitcount[0] = cs.nleaf;
	for(c = cs.lists[cs.nlists - 1]; c != nil; c = c->up){
		m = c->leaf;
		bitcount[bits++] -= m;
		bitcount[bits] = m;
	}
	m = 0;
	for(i = bits; i >= 0; i--)
		for(em = m + bitcount[i]; m < em; m++)
			tab[cs.leafmap[m]].bits = i;

	return bits;
}

/*
 * calculate the next chain on the list
 * we can always toss out the old chain
 */
static void
nextchain(Chains *cs, int list)
{
	Chain *c, *oc;
	int i, nleaf, sumc;

	oc = cs->lists[list + 1];
	cs->lists[list] = oc;
	if(oc == nil)
		return;

	/*
	 * make sure we have all chains needed to make sumc
	 * note it is possible to generate only one of these,
	 * use twice that value for sumc, and then generate
	 * the second if that preliminary sumc would be chosen.
	 * however, this appears to be slower on current tests
	 */
	if(oc->gen){
		nextchain(cs, list - 2);
		nextchain(cs, list - 2);
		oc->gen = 0;
	}

	/*
	 * pick up the chain we're going to add;
	 * collect unused chains no free ones are left
	 */
	for(c = cs->free; ; c++){
		if(c >= cs->echains){
			cs->col++;
			for(i = 0; i < cs->nlists; i++)
				for(c = cs->lists[i]; c != nil; c = c->up)
					c->col = cs->col;
			c = cs->chains;
		}
		if(c->col != cs->col)
			break;
	}

	/*
	 * pick the cheapest of
	 * 1) the next package from the previous list
	 * 2) the next leaf
	 */
	nleaf = oc->leaf;
	sumc = 0;
	if(list > 0 && cs->lists[list-1] != nil)
		sumc = cs->lists[list-2]->count + cs->lists[list-1]->count;
	if(sumc != 0 && (nleaf >= cs->nleaf || cs->leafcount[nleaf] > sumc)){
		c->count = sumc;
		c->leaf = oc->leaf;
		c->up = cs->lists[list-1];
		c->gen = 1;
	}else if(nleaf >= cs->nleaf){
		cs->lists[list + 1] = nil;
		return;
	}else{
		c->leaf = nleaf + 1;
		c->count = cs->leafcount[nleaf];
		c->up = oc->up;
		c->gen = 0;
	}
	cs->free = c + 1;

	cs->lists[list + 1] = c;
	c->col = cs->col;
}

static int
pivot(ulong *c, int a, int n)
{
	int j, pi, pj, pk;

	j = n/6;
	pi = a + j;	/* 1/6 */
	j += j;
	pj = pi + j;	/* 1/2 */
	pk = pj + j;	/* 5/6 */
	if(c[pi] < c[pj]){
		if(c[pi] < c[pk]){
			if(c[pj] < c[pk])
				return pj;
			return pk;
		}
		return pi;
	}
	if(c[pj] < c[pk]){
		if(c[pi] < c[pk])
			return pi;
		return pk;
	}
	return pj;
}

static	void
leafsort(ulong *leafcount, ushort *leafmap, int a, int n)
{
	ulong t;
	int j, pi, pj, pn;

	while(n > 1){
		if(n > 10){
			pi = pivot(leafcount, a, n);
		}else
			pi = a + (n>>1);

		t = leafcount[pi];
		leafcount[pi] = leafcount[a];
		leafcount[a] = t;
		t = leafmap[pi];
		leafmap[pi] = leafmap[a];
		leafmap[a] = t;
		pi = a;
		pn = a + n;
		pj = pn;
		for(;;){
			do
				pi++;
			while(pi < pn && (leafcount[pi] < leafcount[a] || leafcount[pi] == leafcount[a] && leafmap[pi] > leafmap[a]));
			do
				pj--;
			while(pj > a && (leafcount[pj] > leafcount[a] || leafcount[pj] == leafcount[a] && leafmap[pj] < leafmap[a]));
			if(pj < pi)
				break;
			t = leafcount[pi];
			leafcount[pi] = leafcount[pj];
			leafcount[pj] = t;
			t = leafmap[pi];
			leafmap[pi] = leafmap[pj];
			leafmap[pj] = t;
		}
		t = leafcount[a];
		leafcount[a] = leafcount[pj];
		leafcount[pj] = t;
		t = leafmap[a];
		leafmap[a] = leafmap[pj];
		leafmap[pj] = t;
		j = pj - a;

		n = n-j-1;
		if(j >= n){
			leafsort(leafcount, leafmap, a, j);
			a += j+1;
		}else{
			leafsort(leafcount, leafmap, a + (j+1), n);
			n = j;
		}
	}
}