flate

commit 746ffd95970aa1019058f0baba125bfcc3a0fa02
parent 4843dbb8d8c3204eafcd979d45e4181afd9cf858
Author: nsz <nszabolcs@gmail.com>
Date:   Tue, 21 Apr 2009 21:36:31 +0200

remove over optimization
Diffstat:
Makefile
 | 
4
++--
inflate.c
 | 
62
++++++++++++++++++++++----------------------------------------

2 files changed, 24 insertions(+), 42 deletions(-)
diff --git a/Makefile b/Makefile
@@ -16,11 +16,11 @@ clean:
 
 gcov: inflate.c
 	gcc -fprofile-arcs -ftest-coverage -pg -g -Wall $<
-	./a.out a.dat > /dev/null
+	./a.out d.dat > /dev/null
 	gcov -b $< > /dev/null
 	gprof a.out > $<.gprof
 	gcc -g -Wall $<
-	valgrind -v --leak-check=yes ./a.out a.dat > /dev/null 2> a.valgrind
+	valgrind -v --leak-check=yes ./a.out d.dat > /dev/null 2> a.valgrind
 	grep ERROR a.valgrind
 	grep alloc a.valgrind
 	rm a.out a.valgrind *.gcno *.gcda gmon.out
diff --git a/inflate.c b/inflate.c
@@ -1,10 +1,12 @@
 /*
 TODO:
+	check int types
 	error check (src len, dst len, hufftree)
 	clever io
-	p9 hufftable
-	int types
-	fillbits(s, n) ?
+	optimization:
+		bottleneck: decode_symbol in decode_block
+		clever huff table
+		fillbits(s, n)..
 */
 
 typedef unsigned char uchar;
@@ -152,46 +154,26 @@ static uint decode_symbol(FlateStream *s, HuffTree *t) {
 	ushort *count = t->count + 1;
 	uint nbits = s->nbits;
 	uint bits = s->bits;
-
-	/* loop unroll, nbits, bits: approx 20% speedup */
-	while (nbits--) {
-		cur |= bits & 1;
-		bits >>= 1;
-		sum += *count;
-		cur -= *count;
-		if (cur < 0)
-			goto found;
-		cur <<= 1;
-		count++;
-	}
-	bits = *s->src++;
-	nbits = 8;
-	while (nbits--) {
-		cur |= bits & 1;
-		bits >>= 1;
-		sum += *count;
-		cur -= *count;
-		if (cur < 0)
-			goto found;
-		cur <<= 1;
-		count++;
-	}
-	bits = *s->src++;
-	nbits = 8;
-	while (nbits--) {
-		cur |= bits & 1;
-		bits >>= 1;
-		sum += *count;
-		cur -= *count;
-		if (cur < 0)
-			goto found_check;
-		cur <<= 1;
-		count++;
+	int n = HuffBits/8 + 1; /* process 3 bytes at most */
+
+	while (n--) {
+		/* slightly faster than getbit() in a loop */
+		while (nbits--) {
+			cur |= bits & 1;
+			bits >>= 1;
+			sum += *count;
+			cur -= *count;
+			if (cur < 0)
+				goto found;
+			cur <<= 1;
+			count++;
+		}
+		bits = *s->src++;
+		nbits = 8;
 	}
-found_check:
+found:
 	if (count >= t->count + HuffBits)
 		/* error */;
-found:
 	s->bits = bits;
 	s->nbits = nbits;
 	return t->symbol[sum + cur];