flate

commit d695e2aaa37ee9a3f7b05fe5e23cb3c6fbb7d3e2
parent 31fab0436815a7314aee7f320c610ecf6897223f
Author: nsz <nszabolcs@gmail.com>
Date:   Wed, 15 Jul 2009 08:06:46 +0200

deflate += prev match (lazy matching)
Diffstat:
deflate_simple.c
 | 
38
+++++++++++++++++++++++++++-----------

1 file changed, 27 insertions(+), 11 deletions(-)
diff --git a/deflate_simple.c b/deflate_simple.c
@@ -5,7 +5,7 @@
 /*
 TODO:
 	hufflen: parent+heap only
-	match: check backwards, lazy
+	match: check backwards
 	block end: lcount, dcount
 */
 
@@ -351,7 +351,7 @@ static void emitblock(State *s, int blocklen) {
 	for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--);
 
 	/* calc size */
-	uncsize = 3 + 4 + 8*blocklen; /* +byte alignment */
+	uncsize = 3 + 4 + 8*blocklen; /* +byte alignment (8-nbits+3)%8 */
 	fixsize = 3;
 	dynsize = 3 + 5 + 5 + 4;
 	dynsize += 3 * nclen;
@@ -396,10 +396,9 @@ static void emitblock(State *s, int blocklen) {
 		putbits(s, nlit - 257, 5);
 		putbits(s, ndist - 1, 5);
 		putbits(s, nclen - 4, 4);
-		/* clen code lengths */
+		/* huffman code trees */
 		for (i = 0; i < nclen; i++)
 			putbits(s, clen[clenorder[i]], 3);
-		/* code lengths */
 		for (i = 0; i < nc; i++) {
 			c = codes[i];
 			putbits(s, ccode[c], clen[c]);
@@ -542,19 +541,35 @@ int deflate(uchar *src, int len, uchar *dst) {
 	int step;
 	int hash;
 	Match m;
+	Match prevm = {0, 0};
+	uchar prevc = '\0';
 
 	lzinit(&s);
 	newblock(&s, src);
 	s.dst = dst;
 	while (len > 0) {
 		m = getmatch(&s, src, len);
-		if (m.len >= MinMatch) {
-			recordmatch(&s, m);
-			step = m.len;
-		} else {
-			recordlit(&s, *src);
-			step = 1;
-		}
+		if (m.len >= MinMatch)
+			if (m.len <= prevm.len) {
+				recordmatch(&s, prevm);
+				step = prevm.len - 1;
+				prevm.len = 0;
+			} else {
+				if (prevm.len > 0)
+					recordlit(&s, prevc);
+				prevm = m;
+				prevc = *src;
+				step = 1;
+			}
+		else
+			if (prevm.len > 0) {
+				recordmatch(&s, prevm);
+				step = prevm.len - 1;
+				prevm.len = 0;
+			} else {
+				recordlit(&s, *src);
+				step = 1;
+			}
 		while (step > 0) {
 			if (len >= MinMatch) {
 				hash = gethash(src);
@@ -573,6 +588,7 @@ int deflate(uchar *src, int len, uchar *dst) {
 			newblock(&s, src);
 		}
 	}
+
 	if (s.runlen)
 		*s.lzp++ = s.runlen | LzRunlen;
 	s.lastblock = 1;