flate

commit d33497ff1a084ba6e0d11741973808c5c83777d5
parent dcfb7bbf3479341307b7f219decfa6acab0d3e37
Author: nsz <nszabolcs@gmail.com>
Date:   Tue, 18 Aug 2009 11:12:10 +0200

deflate at fixed endpos, removing avail check made the code slower!
Diffstat:
deflate.c
 | 
94
++++++++++++++++++++++++++++++++++++++++++++++++-------------------------------

1 file changed, 57 insertions(+), 37 deletions(-)
diff --git a/deflate.c b/deflate.c
@@ -18,13 +18,17 @@ enum {
 	HashBits    = 13,
 	HashSize    = 1 << HashBits, /* hash table size */
 	BigDist     = 1 << 12, /* max match distance for short match length */
+	MaxDist     = 1 << 15, /* max match distance for short match length */
 	HistSize    = 2*WinSize, /* history buffer size (64K, indexed with ushort) */
 	HistEnd     = MaxMatch + MinMatch - 1, /* reserved space at the end of hist buffer */
 	HistSafe    = HistSize - HistEnd - WinSize, /* worst case available history */
 	BlockSize   = HistSafe, /* block size (should be <= HistSafe) */
 	DstSize     = BlockSize + MaxMatch + 6, /* output buffer size (worst case compressed block size + 1) */
 	LzSize      = 1 << 13, /* lz buffer size */
-	LzLitFlag   = 1 << 15  /* marks literal run length in lz buffer */
+	LzLitFlag   = 1 << 15,  /* marks literal run length in lz buffer */
+
+	MinAvail    = MaxMatch + MinMatch - 1,
+	EndPos      = HistSize - MinAvail
 };
 
 typedef struct {
@@ -479,13 +483,14 @@ static int gethash(uchar *p) {
 static int updatechain(State *s) {
 	int h, i;
 
-	if (s->avail < MinMatch) /* assert(s->eof) */
+/*	if (s->avail < MinMatch)
 		return 0;
+*/
 	h = gethash(s->hist + s->pos);
 	i = s->head[h];
 	s->head[h] = s->pos;
-	if (i >= s->pos || s->pos - i >= HistSafe)
-		i = 0;
+	if (i >= s->pos || s->pos >= HistSafe + i)
+		return 0;
 	s->chain[s->pos % WinSize] = i;
 	return i;
 }
@@ -523,7 +528,7 @@ static Match getmatch(State *s, int mpos) {
 }
 
 /* start a new block */
-static void newblock(State *s) {
+static void startblock(State *s) {
 	s->startpos = s->pos;
 	s->dst = s->dstbegin = s->dstbuf;
 	s->lz = s->lzbuf;
@@ -545,40 +550,50 @@ correctness assertions:
 	- startpos does not underflow during shift hist
 */
 
-/* shift and fill s->hist */
-static int updatehist(State *s) {
-	int n, k;
+/* if block should be ended then end it and shift input window */
+static int endblock(State *s) {
+	int n;
 
-	if (s->pos >= HistSize - HistEnd) {
-		/* shift hist */
-		memcpy(s->hist, s->hist + WinSize, HistSize - WinSize);
+	if (s->pos >= EndPos || s->lz - s->lzbuf > LzSize - 3 || (s->eof && s->avail == 0)) {
+		/* deflate block */
+		flushlit(s);
+		if (s->prevm.len)
+			s->pos--;
+		deflate_block(s);
+		if (s->eof) {
+			putbits(s, 0, 7);
+			return 1;
+		}
+		/* shift input window */
+		memcpy(s->hist, s->hist + WinSize, WinSize);
 		for (n = 0; n < HashSize; n++)
 			s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0;
 		for (n = 0; n < WinSize; n++)
 			s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
-		s->startpos -= WinSize;
 		s->pos -= WinSize;
+		return 1;
 	}
-	if (s->avail <= HistEnd && !s->eof) {
-		/* fill hist */
+	return 0;
+}
+
+static int fillwin(State *s) {
+	int n, k;
+
+	/* s->avail <= MinAvail && s->pos < EndPos */
+	if (!s->eof) {
 		k = s->srcend - s->src;
-		n = HistSize - s->pos - s->avail; /* s->avail + n > HistEnd */
+		n = 2*WinSize - s->pos - s->avail; /* s->avail + n > MinAvail */
 		if (k > n)
 			k = n;
 		memcpy(s->hist + s->pos + s->avail, s->src, k);
 		s->src += k;
 		s->avail += k;
-		if (s->avail <= HistEnd) /* s->srcend == s->src */
+		if (s->avail <= MinAvail) /* s->srcend == s->src */
 			return 0;
 	}
 	return 1;
 }
 
-/* check if the current block should be ended */
-static int endofblock(State *s) {
-	return s->avail == 0 || s->pos - s->startpos >= BlockSize || s->lz - s->lzbuf > LzSize - 3;
-}
-
 /* deflate from s->src into s->dstbuf */
 static int deflate_state(State *s) {
 	Match m;
@@ -591,23 +606,23 @@ static int deflate_state(State *s) {
 			return FlateOut;
 		if (s->eof)
 			return FlateOk;
-		newblock(s);
+		startblock(s);
 		if (s->prevm.len)
 			s->pos++;
 	} else
 		return s->state;
 
 	for (;;) {
-		if (!updatehist(s))
-			return FlateIn;
-		if (endofblock(s)) {
-			flushlit(s);
-			if (s->prevm.len)
-				s->pos--;
-			deflate_block(s);
-			if (s->eof)
-				putbits(s, 0, 7);
-			return FlateOut;
+		if (s->avail <= MinAvail) {
+			if (s->eof && s->avail < MinMatch)
+				while (s->avail) {
+					recordlit(s, s->hist[s->pos++]);
+					s->avail--;
+				}
+			if (endblock(s))
+				return FlateOut;
+			if (!fillwin(s))
+				return FlateIn;
 		}
 		head = updatechain(s);
 		if (head)
@@ -619,11 +634,16 @@ static int deflate_state(State *s) {
 		} else if (s->prevm.len) {
 			recordmatch(s, s->prevm);
 			s->prevm.len -= 2;
-			do {
-				s->pos++;
-				s->avail--;
-				updatechain(s);
-			} while (--s->prevm.len);
+			if (s->avail < s->prevm.len + MinMatch) {
+				s->pos += s->prevm.len;
+				s->avail -= s->prevm.len;
+				s->prevm.len = 0;
+			} else
+				do {
+					s->pos++;
+					s->avail--;
+					updatechain(s);
+				} while (--s->prevm.len);
 		} else
 			recordlit(s, s->hist[s->pos]);
 		s->pos++;