flate

commit 2e11080e70d83bc8d30c95a37c3191db79609a00
parent 73ed0e04029a6e2872d2b4aff478a1b56ebe7528
Author: nsz <nszabolcs@gmail.com>
Date:   Tue, 11 Aug 2009 13:48:57 +0200

deflate: freq/code overlap
Diffstat:
deflate.c
 | 
58
++++++++++++++++++++++++++++++++--------------------------

1 file changed, 32 insertions(+), 26 deletions(-)
diff --git a/deflate.c b/deflate.c
@@ -5,25 +5,28 @@
 
 /*
 TODO:
-	(hufflen: parent+heap only)
-	match: check backwards
-	block end guess with lfreq, dfreq
-	bisect len/distbase -> lookup table
-	(rolling hash)
-	bounds on the compressend size
-	(zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree)
-	overlap freq/code, rbuf/dstwin ?
-	verify dstsize
-	input from in+nin instead of src+srcend
-	setting s->state..
-	ushort vs int
-
-spec case tests:
-	empty block
-	huff overflow
-	all zero (rle)
-	dist = 32K
-	test with small bufsize (1,2..9 bytes)
+	space opt:
+		overlap rbuf/dstwin
+		hufflen: overlap arrays (parent+heap only)
+	time opt:
+		match loop unroll
+		less branching in deflate_state (check avail > MinMatch once)
+		bisect len/distbase -> lookup table
+		rolling hash
+	better compression:
+		block split heuristics with lfreq, dfreq
+		(zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree)
+	code cleanups:
+		bounds on the compressend size
+		verify dstsize
+		input from in+nin instead of src+srcend
+		setting s->state..
+		ushort vs int
+	tests:
+		empty block
+		all zero (rle)
+		uncompressed block
+		test with small nin/nout (1,2..9 bytes)
 */
 
 enum {
@@ -77,8 +80,8 @@ typedef struct {
 	LzCode lzbuf[LzSize];   /* literal run length, match len, match dist */
 	LzCode *lz;             /* current pos in lzbuf */
 	int run;                /* literal run length */
-	int lfreq[Nlitlen];
-	int dfreq[Ndist];
+	ushort lfreq[Nlitlen];
+	ushort dfreq[Ndist];
 	uchar dstbuf[DstSize];
 } State;
 
@@ -192,7 +195,7 @@ static int heappop(int *heap, int len, int *w, int *n) {
 }
 
 /* symbol frequencies -> code lengths (limited to 255) */
-static void hufflens(uchar *lens, int *freqs, int nsym, int limit) {
+static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) {
 	/* 2 <= nsym <= Nlitlen, log(nsym) <= limit <= CodeBits-1 */
 	int parent[2*Nlitlen-1];
 	int count[CodeBits];
@@ -334,17 +337,18 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar 
 }
 
 static void deflate_block(State *s) {
-	int cfreq[Nclen];
 	uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist];
 	uchar llen[Nlitlen], dlen[Ndist], clen[Nclen];
-	ushort lcode[Nlitlen], dcode[Ndist], ccode[Nclen];
+	ushort cfreq[Nclen];
+	/* freq can be overwritten by code */
+	ushort *lcode = s->lfreq, *dcode = s->dfreq, *ccode = cfreq;
 	int i, c, n, ncodes;
 	int nlit, ndist, nclen;
 	LzCode *lz;
 	uchar *pc;
 	int dynsize, fixsize, uncsize;
 	int blocklen = s->pos - s->startpos;
-int dyntree;
+/*int dyntree;*/
 
 	/* calc dynamic codes */
 	hufflens(llen, s->lfreq, Nlitlen, CodeBits-1);
@@ -375,7 +379,7 @@ int dyntree;
 		if (c == 18)
 			dynsize += 7;
 	}
-dyntree = dynsize - 3;
+/*dyntree = dynsize - 3;*/
 	for (lz = s->lzbuf, pc = s->win + s->startpos; lz != s->lz; lz++)
 		if (lz->bits & LzLitFlag)
 			for (n = lz->n; n > 0; n--, pc++) {
@@ -432,9 +436,11 @@ dyntree = dynsize - 3;
 		memcpy(s->dst, s->win + s->startpos, blocklen);
 		s->dst += blocklen;
 	}
+/*
 fprintf(stderr, "blen: %d [%d,%d] lzlen: %d dynlen: %d (tree: %d, rate: %.3f) fixlen: %d (rate: %.3f) unclen: %d (rate: %.3f) avail %d\n",
 	blocklen, s->startpos, s->pos, s->lz - s->lzbuf, dynsize, dyntree, dynsize/(float)blocklen,
 	fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen, s->avail);
+*/
 }
 
 static int bisect(ushort *base, int len, int n) {