flate

commit 75899c653f9541fafdacfd02bb7df46b6a82e22c
parent 28997f8a140bb3ee75efd89425898f94e3968492
Author: nsz@tpx <unknown>
Date:   Thu,  6 Aug 2009 21:22:35 +0200

in deflate use prevm on block boundary too
Diffstat:
deflate.c
 | 
24
++++++++++--------------

1 file changed, 10 insertions(+), 14 deletions(-)
diff --git a/deflate.c b/deflate.c
@@ -8,29 +8,25 @@
 TODO:
 	hufflen: parent+heap only
 	match: check backwards
-	block end guess with lcount, dcount
+	block end guess with lfreq, dfreq
 	bisect len/distbase -> lookup table
-	xcode can be calculated into array xfreq
-	record good prev match
 	buffer window: ushort pos: let it overflow
 	rolling hash
 	save prevm instead roll back on block boundary
 	read until avail > MaxMatch
-	if read size == 0 then no more reads
 	runlen -> lz (rename)
 	bounds on the compressend size
-	zlib trick: if same freq then shorter code goes to the one with smaller subtree
-	alloc bufs on heap?
+	zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree
 	overlap freq/code, rbuf/dstwin ?
 	fix match (loopunroll near end)
-	dstsize
+	better dstsize (blocklen <= 32k)
 
 spec case tests:
 	empty block
 	huff overflow
 	all zero (rle)
 	dist = 32K
-	test with small bufsize (1,2..17 bytes)
+	test with small bufsize (1,2..9 bytes)
 */
 
 enum {
@@ -499,7 +495,7 @@ static ushort addtochain(State *s, ushort pos) {
 
 	if (s->avail < MinMatch) /* TODO */
 		return 0;
-	h = gethash(s->win + pos); /* TODO: rolling hash */
+	h = gethash(s->win + pos);
 	i = s->head[h];
 	s->head[h] = pos;
 	s->chain[pos % WinSize] = i;
@@ -599,11 +595,8 @@ static int deflate_state(State *s) {
 			}
 			if (pos - s->blockstart > MaxDist || s->rend - s->rbuf >= RbufSize - 2) {
 				flushlit(s);
-				if (prevm.len) {
+				if (prevm.len)
 					pos--;
-					s->avail++;
-					prevm.len = 0;
-				}
 fprintf(stderr, "avail %d pos %d lastpos %d srcavail %d\n", s->avail, pos, s->pos, s->srcend - s->src);
 				deflate_block(s, pos - s->blockstart);
 				s->pos = pos;
@@ -618,6 +611,8 @@ fprintf(stderr, "avail %d pos %d lastpos %d srcavail %d\n", s->avail, pos, s->po
 				newblock(s);
 				s->blockstart = pos = s->pos;
 				prevm = s->prevm;
+				if (prevm.len)
+					pos++;
 			}
 			s->pos = pos;
 			if (fillwin(s)) {
@@ -642,6 +637,7 @@ fprintf(stderr, "avail %d pos %d srcavail %d\n", s->avail, s->pos, s->srcend - s
 			prevm = m;
 		} else if (prevm.len) {
 			recordmatch(s, prevm);
+			/* too tricky.. */
 			prevm.len -= 2;
 			do {
 				pos++;
@@ -654,7 +650,7 @@ fprintf(stderr, "avail %d pos %d srcavail %d\n", s->avail, s->pos, s->srcend - s
 		s->avail--;
 	} /* for(;;) */
 	} /* switch */
-	return FlateErr;
+	return FlateErr; /* unreachable */
 }
 
 static State *alloc_state(void) {