flate

commit 162823bea29ac79fd3fb107de28c4032fc9db7f5
parent 9de8fb994bd9a86f1f0948249d5fe49d6a9ea97d
Author: nsz@tpx <unknown>
Date:   Sun,  9 Aug 2009 10:29:26 +0200

winsize = 2*maxdist + maxmatch
Diffstat:
deflate.c
 | 
136
+++++++++++++++++++++++++++++++++++++------------------------------------------

1 file changed, 63 insertions(+), 73 deletions(-)
diff --git a/deflate.c b/deflate.c
@@ -29,17 +29,17 @@ spec case tests:
 */
 
 enum {
-	WinSize = 1 << 15,
-	DstSize = 2*WinSize + 8,
-	RbufSize = 1 << 13,
-	RunlenFlag = 1 << 15,
-	MinMatch = 3,
-	MaxMatch = 258,
-	BigDist = 1 << 12,
-	MaxDist = WinSize - MaxMatch,
+	MinMatch    = 3,
+	MaxMatch    = 258,
 	MaxChainLen = 256,
-	HashBits = 13,
-	HashSize = 1 << HashBits,
+	HashBits    = 13,
+	HashSize    = 1 << HashBits,
+	BigDist     = 1 << 12,
+	MaxDist     = 1 << 15,
+	WinSize     = 2*MaxDist + MaxMatch,
+	DstSize     = 2*WinSize + 8,
+	RbufSize    = 1 << 13,
+	RunlenFlag  = 1 << 15,
 
 	CodeBits    = 16,  /* max number of bits in a code + 1 */
 	EOB         = 256, /* end of block symbol */
@@ -73,14 +73,14 @@ typedef struct {
 	uchar *dstbegin;
 	uint bits;
 	int nbits;
-	int lfreq[Nlitlen];
-	int dfreq[Ndist];
+	uchar win[WinSize];
 	ushort head[HashSize];  /* position of hash chain heads */
-	ushort chain[WinSize];  /* hash chains next */
-	uchar win[2*WinSize];
+	ushort chain[MaxDist];  /* hash chains next */
 	Runlen rbuf[RbufSize];  /* literal run length, match len, match dist */
 	Runlen *rend;           /* current pos in rbuf */
 	int run;                /* literal count */
+	int lfreq[Nlitlen];
+	int dfreq[Ndist];
 	uchar dstbuf[DstSize];
 } State;
 
@@ -335,16 +335,17 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar 
 	putbits(s, lcode[EOB], llen[EOB]);
 }
 
-static void deflate_block(State *s, int blocklen) {
+static void deflate_block(State *s) {
 	int cfreq[Nclen];
 	uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist];
 	uchar llen[Nlitlen], dlen[Ndist], clen[Nclen];
 	ushort lcode[Nlitlen], dcode[Ndist], ccode[Nclen];
 	int i, c, n, ncodes;
 	int nlit, ndist, nclen;
-	int dynsize, fixsize, uncsize;
 	Runlen *r;
 	uchar *pc;
+	int dynsize, fixsize, uncsize;
+	int blocklen = s->pos - s->startpos;
 int dyntree;
 
 	/* calc dynamic codes */
@@ -465,7 +466,6 @@ static void recordmatch(State *s, Match m) {
 	int n;
 
 	flushlit(s);
-/*fprintf(stderr, "len:%u dist:%u\n", m.len, m.dist);*/
 	n = bisect(lenbase, Nlen, m.len);
 	s->rend->n = n;
 	s->rend->bits = m.len - lenbase[n];
@@ -479,7 +479,6 @@ static void recordmatch(State *s, Match m) {
 }
 
 static void recordlit(State *s, int c) {
-/*fprintf(stderr, "lit:%c\n", c);*/
 	s->run++;
 	s->lfreq[c]++;
 }
@@ -497,7 +496,7 @@ static ushort addtochain(State *s, ushort pos) {
 	h = gethash(s->win + pos);
 	i = s->head[h];
 	s->head[h] = pos;
-	s->chain[pos % WinSize] = i;
+	s->chain[pos % MaxDist] = i;
 	return i;
 }
 
@@ -532,7 +531,7 @@ static Match getmatch(State *s, ushort pos, ushort mpos) {
 			}
 			m.len = len;
 		}
-	} while ((mpos = s->chain[mpos % WinSize]) > limit && --chainlen);
+	} while ((mpos = s->chain[mpos % MaxDist]) > limit && --chainlen);
 	if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist))
 		m.len = 0;
 	return m;
@@ -549,27 +548,31 @@ static void newblock(State *s) {
 }
 
 static int fillwin(State *s) {
-	int n, k;
+	int n;
+	int need, have;
 
-	if (s->pos > WinSize + MaxDist) {
+	if (s->pos >= 2*MaxDist) {
 		/* shift win */
-		memcpy(s->win, s->win + WinSize, WinSize);
+		memcpy(s->win, s->win + MaxDist, MaxDist + MaxMatch);
 		for (n = HashSize; n--;)
-			s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0;
-		for (n = WinSize; n--;)
-			s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
-		s->startpos -= WinSize;
-		s->pos -= WinSize;
+			s->head[n] = s->head[n] > MaxDist ? s->head[n] - MaxDist : 0;
+		for (n = MaxDist; n--;)
+			s->chain[n] = s->chain[n] > MaxDist ? s->chain[n] - MaxDist : 0;
+		s->startpos -= MaxDist;
+		s->pos -= MaxDist;
+	}
+	if (s->avail < MaxMatch) {
+		/* fill win */
+		need = WinSize - s->pos - s->avail;
+		have = s->srcend - s->src;
+		if (have > need)
+			have = need;
+		if (have == 0)
+			return FlateIn;
+		memcpy(s->win + s->pos + s->avail, s->src, have);
+		s->src += have;
+		s->avail += have;
 	}
-	k = 2*WinSize - s->pos - s->avail;
-	n = s->srcend - s->src;
-	if (n > k)
-		n = k;
-	if (n == 0)
-		return FlateIn;
-	memcpy(s->win + s->pos + s->avail, s->src, n);
-	s->src += n;
-	s->avail += n;
 	return FlateOk;
 }
 
@@ -577,9 +580,7 @@ static int deflate_state(State *s) {
 	Match m;
 	int head;
 
-	/* messy.. */
-	switch (s->state) {
-	case FlateOut:
+	if (s->state == FlateOut) {
 		if (s->dstbegin < s->dst)
 			return FlateOut;
 		if (s->lastblock)
@@ -587,15 +588,12 @@ static int deflate_state(State *s) {
 		newblock(s);
 		if (s->prevm.len)
 			s->pos++;
-		if (fillwin(s)) {
-			s->state = FlateIn;
+		if (fillwin(s))
 			return FlateIn;
-		}
-		break;
-	case FlateIn:
+	} else if (s->state == FlateIn)
 		fillwin(s);
-		break;
-	}
+	else
+		return s->state;
 	for (;;) {
 		head = addtochain(s, s->pos);
 		if (head >= s->pos || s->pos - head >= MaxDist)
@@ -619,30 +617,23 @@ static int deflate_state(State *s) {
 			recordlit(s, s->win[s->pos]);
 		s->pos++;
 		s->avail--;
-
-		if (s->avail < MaxMatch || s->rend - s->rbuf >= RbufSize - 2) {
-			if (s->avail == 0) {
-				flushlit(s);
-				s->lastblock = 1;
-				s->state = FlateOut;
-				deflate_block(s, s->pos - s->startpos);
-				putbits(s, 0, 7);
-				return FlateOut;
-			}
-			if (s->pos - s->startpos > MaxDist || s->rend - s->rbuf >= RbufSize - 2) {
-				flushlit(s);
-				if (s->prevm.len)
-					s->pos--;
-fprintf(stderr, "avail %d pos %d srcavail %d\n", s->avail, s->pos, s->srcend - s->src);
-				deflate_block(s, s->pos - s->startpos);
-				s->state = FlateOut;
-				return FlateOut;
-			}
-			if (fillwin(s)) {
-				s->state = FlateIn;
-				return FlateIn;
-			}
+		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->rend - s->rbuf >= RbufSize - 2) {
+fprintf(stderr, "start %d pos %d avail %d srcavail %d rlen %d\n", s->startpos, s->pos, s->avail, s->srcend - s->src, s->rend - s->rbuf);
+			flushlit(s);
+			if (s->prevm.len)
+				s->pos--;
+			deflate_block(s);
+			return FlateOut;
+		}
+		if (fillwin(s))
+			return FlateIn;
 	}
 }
 
@@ -667,9 +658,8 @@ static State *alloc_state(void) {
 		fixdlen[i] = 5;
 	huffcodes(fixlcode, fixllen, Nlitlen);
 	huffcodes(fixdcode, fixdlen, Ndist);
-
 	s->dst = s->dstbegin = s->dstbuf;
-	s->pos = s->startpos = WinSize;
+	s->pos = s->startpos = MaxDist;
 	s->avail = 0;
 	return s;
 }
@@ -694,7 +684,7 @@ int deflate(FlateStream *stream) {
 		s->srcend = s->src + stream->nin;
 		stream->nin = 0;
 	}
-	n = deflate_state(s);
+	n = s->state = deflate_state(s);
 	if (n == FlateOut) {
 		k = s->dst - s->dstbegin;
 		if (k < stream->nout)