flate

commit cb1e87d4b17b038d4b65e0f9bc6ec3f4353d1394
parent ebb7e504ec96aaa2524f78ec704f38f0ebc275d2
Author: nsz <nszabolcs@gmail.com>
Date:   Sun, 26 Jul 2009 00:36:42 +0200

deflate optimizations
Diffstat:
Makefile
 | 
13
++++++++-----
deflate_simple.c
 | 
32
++++++++++----------------------

2 files changed, 18 insertions(+), 27 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,7 +1,7 @@
-CFLAGS=-g -Wall -ansi -pedantic
-#CFLAGS=-O3 -Wall -ansi -pedantic
+#CFLAGS=-g -Wall -ansi -pedantic
+CFLAGS=-O3 -Wall -ansi -pedantic
 LDFLAGS=
-SRC=inflate.c inflate_simple.c inflate_callback.c deflate_simple.c
+SRC=inflate.c inflate_simple.c inflate_callback.c deflate.c deflate_simple.c
 OBJ=${SRC:.c=.o}
 EXE=${SRC:.c=}
 
@@ -12,6 +12,8 @@ inflate_simple: inflate_simple.o
 	${CC} -o $@ $^ ${LDFLAGS}
 inflate_callback: inflate_callback.o
 	${CC} -o $@ $^ ${LDFLAGS}
+deflate: deflate.o
+	${CC} -o $@ $^ ${LDFLAGS}
 deflate_simple: deflate_simple.o
 	${CC} -o $@ $^ ${LDFLAGS}
 ${OBJ}: Makefile
@@ -20,8 +22,9 @@ ${OBJ}: Makefile
 clean:
 	rm -f ${OBJ} ${EXE}
 
+prof: profinf profdef
 
-prof: inflate.c
+profinf: inflate.c
 	gcc -O3 -fprofile-arcs -ftest-coverage -pg -g -Wall $<
 	./a.out <a.dat >/dev/null
 	gcov -b $< >/dev/null
@@ -32,7 +35,7 @@ prof: inflate.c
 #	grep alloc a.valgrind
 	rm -f a.out a.valgrind *.gcno *.gcda gmon.out
 
-profdef: deflate_simple.c
+profdef: deflate.c
 	gcc -O0 -fprofile-arcs -ftest-coverage -pg -g -Wall $<
 	./a.out <a.pdf >/dev/null
 	gcov -b $< >/dev/null
diff --git a/deflate_simple.c b/deflate_simple.c
@@ -1,16 +1,4 @@
 #include <string.h>
-#include <stdio.h>
-
-/*
-TODO:
-	hufflen: parent+heap only
-	match: check backwards
-	block end: lcount, dcount
-	bisect len/dist base -> lookup table
-	don't store lz extra nbits: lenbits[lensym]
-	xcode can be calculated into array xfreq
-	stop after good match
-*/
 
 typedef unsigned char uchar;
 typedef unsigned short ushort;
@@ -20,12 +8,12 @@ enum {
 	MinMatch = 3,
 	MaxMatch = 258,
 	BigDist = 1 << 12,
-	MaxChainStep = 32,
+	MaxChainStep = 64,
 	HashBits = 13,
 	HashSize = 1 << HashBits,
 	WinSize = 1 << 15,
 	BlockLen = 1 << 15,
-	RbufSize = (BlockLen + 2 * MaxMatch) * 3/4,
+	RbufSize = BlockLen * 3/4 + 2 * MaxMatch,
 	RunlenFlag = 1 << 30,
 
 	CodeBits    = 16,  /* max number of bits in a code + 1 */
@@ -321,7 +309,7 @@ static void deflate_block(State *s, int blocklen) {
 	int dynsize, fixsize, uncsize;
 	int *pn;
 	uchar *pc;
-int dyntree;
+/*int dyntree;*/
 
 	/* calc dynamic codes */
 	hufflens(llen, s->lfreq, Nlitlen, CodeBits-1);
@@ -352,7 +340,7 @@ int dyntree;
 		if (c == 18)
 			dynsize += 7;
 	}
-dyntree = dynsize - 3;
+/*dyntree = dynsize - 3;*/
 	for (pn = s->rbuf, pc = s->src; pn != s->rend;) {
 		n = *pn++;
 		if (n & RunlenFlag) {
@@ -413,8 +401,10 @@ dyntree = dynsize - 3;
 		memcpy(s->dst, s->src, blocklen);
 		s->dst += blocklen;
 	}
+/*
 fprintf(stderr, "blocklen: %d lzlen: %d dynsize: %d (tree: %d, rate: %.3f) fixsize: %d (rate: %.3f) uncsize: %d (rate: %.3f)\n", blocklen, s->rend - s->rbuf,
 	dynsize, dyntree, dynsize/(float)blocklen, fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen);
+*/
 }
 
 static int bisect(ushort *base, int len, int n) {
@@ -466,6 +456,8 @@ static Match getmatch(State *s, uchar *src, int len) {
 
 	if (len < MinMatch)
 		return m;
+	if (len > MaxMatch)
+		len = MaxMatch;
 	pos = s->head[gethash(src)];
 	for (i = 0; i < MaxChainStep; i++) {
 		dist = (WinSize + s->pos - pos) % WinSize;
@@ -478,10 +470,8 @@ static Match getmatch(State *s, uchar *src, int len) {
 		if (j > m.len) {
 			m.dist = dist;
 			m.len = j;
-			if (j > MaxMatch) {
-				m.len = MaxMatch;
+			if (j == len)
 				return m;
-			}
 		}
 		pos = s->chain[pos];
 	}
@@ -524,7 +514,6 @@ int deflate(uchar *src, int len, uchar *dst) {
 	uint hash;
 	Match m;
 	Match prevm = {0, 0};
-	uchar prevc = 0;
 
 	deflate_init(&s);
 	newblock(&s);
@@ -534,10 +523,9 @@ int deflate(uchar *src, int len, uchar *dst) {
 		m = getmatch(&s, src, len);
 		if (m.len > prevm.len) {
 			if (prevm.len)
-				recordlit(&s, prevc);
+				recordlit(&s, *(src-1));
 			step = 1;
 			prevm = m;
-			prevc = *src;
 		} else if (prevm.len) {
 			recordmatch(&s, prevm);
 			step = prevm.len - 1;