flate

commit c338151a0cb5cb8f46fb9b82e02dc90400c77e60
parent 8c0e33a192944d350098d5470a05ae72bc725c1f
Author: nsz <nszabolcs@gmail.com>
Date:   Mon,  8 Jun 2009 10:43:03 +0200

surprising decodeblock optimization: fillbits_, getbits_
Diffstat:
Makefile
 | 
2
+-
inflate.c
 | 
31
+++++++++++++++++++++++--------

2 files changed, 24 insertions(+), 9 deletions(-)
diff --git a/Makefile b/Makefile
@@ -21,7 +21,7 @@ clean:
 
 prof: inflate.c
 	gcc -O3 -fprofile-arcs -ftest-coverage -pg -g -Wall $<
-	cat a.dat | ./a.out > /dev/null
+	cat d.dat | ./a.out > /dev/null
 	gcov -b $< > /dev/null
 	gprof a.out > $<.gprof
 	gcc -g -Wall $<
diff --git a/inflate.c b/inflate.c
@@ -196,10 +196,6 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) {
 		table[code].sym = i << 1;
 		code = revinc(code, nbits);
 	}
-/*
-for (i = 0; i < CodeBits - nbits - 1; i++)
-	count[i] = count[i + nbits + 1];
-*/
 	return 0;
 }
 
@@ -242,6 +238,25 @@ static uint getbits(State *s, int n) {
 	return k;
 }
 
+static int fillbits_(uchar **src, uchar *srcend, uint *bits, uint *nbits, uint n) {
+	while (*nbits < n) {
+		if (*src == srcend)
+			return 0;
+		*bits |= *(*src)++ << *nbits;
+		*nbits += 8;
+	}
+	return 1;
+}
+
+static uint getbits_(uint *bits, uint *nbits, int n) {
+	uint k;
+
+	k = *bits & ((1 << n) - 1);
+	*bits >>= n;
+	*nbits -= n;
+	return k;
+}
+
 /* decode symbol bitwise if code is longer than huffbits */
 static uint decode_symbol_long(State *s, Huff *huff, uint bits, uint nbits, int cur) {
 	int sum = huff->sum;
@@ -372,13 +387,13 @@ static int decode_block(State *s, Huff *lhuff, Huff *dhuff) {
 				return FlateError;
 			}
 decode_lenbits:
-			if (!fillbits(s, lenbits[sym])) {
+			if (!fillbits_(&s->src, s->srcend, &s->bits, &s->nbits, lenbits[sym])) {
 				s->nclen = sym; /* using nclen to store sym */
 				s->pos = pos;
 				s->state = DecodeBlockLenBits;
 				return FlateNeedInput;
 			}
-			len = lenbase[sym] + getbits(s, lenbits[sym]);
+			len = lenbase[sym] + getbits_(&s->bits, &s->nbits, lenbits[sym]);
 decode_dist:
 			sym = decode_symbol(s, dhuff);
 			if (sym == (uint)FlateNeedInput) {
@@ -390,7 +405,7 @@ decode_dist:
 			if (sym >= Ndist)
 				return FlateError;
 decode_distbits:
-			if (!fillbits(s, distbits[sym])) {
+			if (!fillbits_(&s->src, s->srcend, &s->bits, &s->nbits, distbits[sym])) {
 				s->nclen = sym; /* using nclen to store sym */
 				s->pos = pos;
 				s->lenpos = len;
@@ -398,7 +413,7 @@ decode_distbits:
 				return FlateNeedInput;
 			}
 			/* TODO: s/dist/sym/ */
-			dist = distbase[sym] + getbits(s, distbits[sym]);
+			dist = distbase[sym] + getbits_(&s->bits, &s->nbits, distbits[sym]);
 			/* copy match, loop unroll in common case */
 			if (pos + len < WinSize) {
 				/* lenbase[sym] >= 3 */