flate

commit 83b468c05c4b53f1b8a07d13210fb1963d277749
parent 18ac1ccecb9472bfe9a8a97aa96e62bf4f289746
Author: nsz <nszabolcs@gmail.com>
Date:   Tue, 11 Aug 2009 00:16:36 +0200

deflate code cleanups
Diffstat:
Makefile
 | 
6
+++---
deflate.c
 | 
88
++++++++++++++++++++++++++++++++++++++++----------------------------------------

2 files changed, 47 insertions(+), 47 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,5 +1,5 @@
 #CFLAGS=-g -Wall -ansi -pedantic
-CFLAGS=-Os -Wall -ansi -pedantic
+CFLAGS=-O3 -Wall -ansi -pedantic
 LDFLAGS=
 SRC=inflate.c inflate_example.c inflate_simple.c inflate_callback.c \
     deflate.c deflate_example.c
@@ -35,8 +35,8 @@ profinf: inflate_example.c inflate.c
 	rm -f a.out a.valgrind *.gcno *.gcda gmon.out
 
 profdef: deflate_example.c deflate.c
-	gcc -O3 -fprofile-arcs -ftest-coverage -pg -g -Wall $+
-	./a.out <q.tar >/dev/null
+	gcc -O1 -fprofile-arcs -ftest-coverage -pg -g -Wall $+
+	./a.out <a.pdf >/dev/null
 	gcov -b $+ >/dev/null
 	gprof a.out >$<.gprof
 	rm -f a.out *.gcno *.gcda gmon.out
diff --git a/deflate.c b/deflate.c
@@ -13,12 +13,10 @@ TODO:
 	bounds on the compressend size
 	(zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree)
 	overlap freq/code, rbuf/dstwin ?
-	. better dstsize (blocklen <= 32k)
-	. input from in+nin instead of src+srcend
-	. setting s->state..
-	. ushort vs int
-	. memcpy vs memset
-	. do not return with flatein after 0 read size
+	verify dstsize
+	input from in+nin instead of src+srcend
+	setting s->state..
+	ushort vs int
 
 spec case tests:
 	empty block
@@ -37,7 +35,7 @@ enum {
 	BigDist     = 1 << 12, /* max match distance for short match length */
 	MaxDist     = 1 << 15, /* max match distance */
 	WinSize     = 2*MaxDist + MaxMatch, /* input window size */
-	DstSize     = WinSize + 8, /* output window size (worst case compressed block size) */
+	DstSize     = MaxDist + 2*MaxMatch + 6, /* output window size (worst case compressed block size) */
 	LzSize      = 1 << 13, /* lz buffer size */
 	LzLitFlag   = 1 << 15, /* marks literal run length in lz buffer */
 
@@ -62,10 +60,10 @@ typedef struct {
 
 typedef struct {
 	int state;              /* prev return value */
+	int eof;                /* end of input */
 	int pos;                /* position in input win */
-	int avail;              /* available in input win */
 	int startpos;           /* block start pos in input win */
-	int lastblock;          /* is last block */
+	int avail;              /* available in input win */
 	Match prevm;            /* previous (deferred) match */
 	uchar *src;             /* input data (not yet in win) */
 	uchar *srcend;
@@ -400,7 +398,7 @@ dyntree = dynsize - 3;
 	dynsize += llen[EOB];
 
 	/* emit block */
-	putbits(s, s->lastblock, 1);
+	putbits(s, s->eof, 1);
 	if (dynsize < fixsize && dynsize < uncsize) {
 		/* dynamic code */
 		putbits(s, 2, 2);
@@ -434,8 +432,9 @@ dyntree = dynsize - 3;
 		memcpy(s->dst, s->win + s->startpos, 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->lz - s->lzbuf,
-	dynsize, dyntree, dynsize/(float)blocklen, fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen);
+fprintf(stderr, "blen: %d [%d,%d] lzlen: %d dynlen: %d (tree: %d, rate: %.3f) fixlen: %d (rate: %.3f) unclen: %d (rate: %.3f) avail %d\n",
+	blocklen, s->startpos, s->pos, s->lz - s->lzbuf, dynsize, dyntree, dynsize/(float)blocklen,
+	fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen, s->avail);
 }
 
 static int bisect(ushort *base, int len, int n) {
@@ -488,15 +487,17 @@ static ushort gethash(uchar *p) {
 	return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits)) % HashSize;
 }
 
-static ushort addtochain(State *s) {
+static ushort updatechain(State *s) {
 	ushort i, h;
 
-	if (s->avail < MinMatch) /* TODO */
+	if (s->avail < MinMatch)
 		return 0;
 	h = gethash(s->win + s->pos);
 	i = s->head[h];
 	s->head[h] = s->pos;
 	s->chain[s->pos % MaxDist] = i;
+	if (i >= s->pos || s->pos - i >= MaxDist)
+		return 0;
 	return i;
 }
 
@@ -516,7 +517,7 @@ static Match getmatch(State *s, int mpos) {
 		if (q[m.len] != p[m.len] || q[0] != p[0])
 			continue;
 		/* loop unroll: MaxMatch % 10 == 8, overflow if avail < MaxMatch */
-		/* only small gain over while (++p != end && *++q == *p); */
+		/* only little gain over while (++p != end && *++q == *p); */
 		do; while (*++q == *++p && *++q == *++p
 		        && *++q == *++p && *++q == *++p
 		        && *++q == *++p && *++q == *++p
@@ -553,8 +554,7 @@ static int fillwin(State *s) {
 
 	if (s->pos >= 2*MaxDist) {
 		/* shift win */
-		memcpy(s->win, s->win + MaxDist, MaxDist);
-		memcpy(s->win + MaxDist, s->win + 2*MaxDist, MaxMatch);
+		memmove(s->win, s->win + MaxDist, MaxDist + MaxMatch);
 		for (n = HashSize; n--;)
 			s->head[n] = s->head[n] > MaxDist ? s->head[n] - MaxDist : 0;
 		for (n = MaxDist; n--;)
@@ -562,43 +562,51 @@ static int fillwin(State *s) {
 		s->startpos -= MaxDist;
 		s->pos -= MaxDist;
 	}
-	if (s->avail < MaxMatch) {
+	if (s->avail < MaxMatch && !s->eof) {
 		/* fill win */
 		n = WinSize - s->pos - s->avail;
 		k = s->srcend - s->src;
 		if (k > n)
 			k = n;
 		if (k == 0)
-			return FlateIn;
+			return 0;
 		memcpy(s->win + s->pos + s->avail, s->src, k);
 		s->src += k;
 		s->avail += k;
 	}
-	return FlateOk;
+	return 1;
+}
+
+static int endofblock(State *s) {
+	if (s->avail == 0)
+		return 1;
+	if ((s->pos - s->startpos >= MaxDist ||
+	     s->lz - s->lzbuf > LzSize - 3) && !s->eof)
+		return 1;
+	return 0;
 }
 
 static int deflate_state(State *s) {
 	Match m;
 	int head;
 
-	if (s->state == FlateOut) {
+	if (s->state == FlateIn)
+		s->eof = s->src == s->srcend;
+	else if (s->state == FlateOut) {
 		if (s->dstbegin < s->dst)
 			return FlateOut;
-		if (s->lastblock)
+		if (s->eof)
 			return FlateOk;
 		newblock(s);
 		if (s->prevm.len)
 			s->pos++;
-		if (fillwin(s))
-			return FlateIn;
-	} else if (s->state == FlateIn)
-		fillwin(s);
-	else
+	} else
 		return s->state;
+
 	for (;;) {
-		head = addtochain(s);
-		if (head >= s->pos || s->pos - head >= MaxDist)
-			head = 0;
+		if (!fillwin(s))
+			return FlateIn;
+		head = updatechain(s);
 		if (head)
 			m = getmatch(s, head);
 		if (head && m.len > s->prevm.len) {
@@ -607,34 +615,25 @@ static int deflate_state(State *s) {
 			s->prevm = m;
 		} else if (s->prevm.len) {
 			recordmatch(s, s->prevm);
-			/* tricky.. */
 			s->prevm.len -= 2;
 			do {
 				s->pos++;
 				s->avail--;
-				addtochain(s);
+				updatechain(s);
 			} while (--s->prevm.len);
 		} else
 			recordlit(s, s->win[s->pos]);
 		s->pos++;
 		s->avail--;
-		if (s->avail == 0) {
-			s->lastblock = 1;
-			flushlit(s);
-			deflate_block(s);
-			putbits(s, 0, 7);
-			return FlateOut;
-		}
-		if (s->pos - s->startpos >= MaxDist || s->lz - s->lzbuf > LzSize - 3) {
-fprintf(stderr, "start %d pos %d avail %d srcavail %d rlen %d\n", s->startpos, s->pos, s->avail, s->srcend - s->src, s->lz - s->lzbuf);
+		if (endofblock(s)) {
 			flushlit(s);
 			if (s->prevm.len)
 				s->pos--;
 			deflate_block(s);
+			if (s->eof)
+				putbits(s, 0, 7);
 			return FlateOut;
 		}
-		if (fillwin(s))
-			return FlateIn;
 	}
 }
 
@@ -646,7 +645,7 @@ static State *alloc_state(void) {
 		return s;
 	memset(s->chain, 0, sizeof(s->chain));
 	memset(s->head, 0, sizeof(s->head));
-	s->bits = s->nbits = s->lastblock = 0;
+	s->bits = s->nbits = 0;
 	for (i = 0; i < 144; i++)
 		fixllen[i] = 8;
 	for (; i < 256; i++)
@@ -661,6 +660,7 @@ static State *alloc_state(void) {
 	huffcodes(fixdcode, fixdlen, Ndist);
 	s->dst = s->dstbegin = s->dstbuf;
 	s->pos = s->startpos = MaxDist;
+	s->eof = 0;
 	s->avail = 0;
 	s->prevm.len = 0;
 	return s;