flate

commit 21159561f3409a46a0949d92fc131f18784271b5
parent 6ee26d56c3e3e39af131e339290495825e8951a3
Author: nsz <nszabolcs@gmail.com>
Date:   Mon,  6 Jul 2009 19:13:49 +0200

complexification
Diffstat:
deflate_simple.c
 | 
97
++++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------

1 file changed, 66 insertions(+), 31 deletions(-)
diff --git a/deflate_simple.c b/deflate_simple.c
@@ -25,11 +25,6 @@ enum {
 	Nclen       = 19   /* number of code length codes */
 };
 
-typedef struct {
-	ushort dist;
-	ushort len;
-} Match;
-
 enum {
 	SymLitlen,
 	SymDist,
@@ -44,6 +39,11 @@ typedef struct {
 } Sym;
 
 typedef struct {
+	ushort dist;
+	ushort len;
+} Match;
+
+typedef struct {
 	ushort head[HashSize];  /* position of hash chain heads */
 	ushort chain[WinSize];  /* hash chains */
 	int pos;                /* position in hash chain */
@@ -538,6 +538,7 @@ fprintf(stderr, "tree len: %d bits: %d\n", nsym, dynsize);
 
 	outbits(s, s->lastblock, 1);
 	if ((long long)fixsize * dynlen > (long long)dynsize * fixlen) {
+fprintf(stderr, "dyn ");
 		blocklen = dynlen;
 		outbits(s, 2, 2);
 		outbits(s, nlit - 257, 5);
@@ -567,6 +568,7 @@ fprintf(stderr, "tree len: %d bits: %d\n", nsym, dynsize);
 		/* EOB */
 		outbits(s, lcode[256], llen[256]);
 	} else {
+fprintf(stderr, "fix ");
 		blocklen = fixlen;
 		outbits(s, 1, 2);
 		/* block data */
@@ -582,7 +584,7 @@ fprintf(stderr, "tree len: %d bits: %d\n", nsym, dynsize);
 		/* EOB */
 		outbits(s, fixed_lcode[256], fixed_llen[256]);
 	}
-fprintf(stderr, "blocklen: %d symlen: %d dynsize: %d dynlen: %d fixsize: %d fixlen:%d\n", blocklen, s->symlen, dynsize, dynlen, fixsize, fixlen);
+fprintf(stderr, "symlen: %d dynsize: %d dynlen: %d fixsize: %d fixlen:%d\n", s->symlen, dynsize, dynlen, fixsize, fixlen);
 	s->symstart = (s->symstart + blocklen) % SymSize;
 	s->symlen -= blocklen;
 }
@@ -615,51 +617,82 @@ static int log2_8(uint n) {
 	return r;
 }
 
+static int nlog(uint n) {
+	return n*log2_8(n);
+}
+
 static void chooseblock(State *s) {
 	int lfreq[Nlitlen], dfreq[Ndist];
-	int i, len, bestlen, longestlen;
-	int ltotal, dtotal;
-	int bestvfm;
+	int ln, dn;
+	int len;
+	uint bestrate;
+	int bestlen, longestlen, besti;
+	int extra;
+	int hlen;
+	int i;
 	Sym sym;
 
+	hlen = 600 * 8; /* length of encoded huff tree (usually 400..900 bits) */
+	extra = 0;
 	memset(lfreq, 0, sizeof(lfreq));
 	memset(dfreq, 0, sizeof(dfreq));
-	lfreq[256] = 1;	  /* we're bound to need one EOB */
-	ltotal = 1;
-	dtotal = longestlen = bestvfm = 0;
-	bestlen = -1;
-	len = 400 * 8;	  /* approximate size of the Huffman trees */
+	lfreq[256] = 1; /* EOB */
+	ln = 1;
+	dn = 0;
+/*
+	for (i = 0; i < s->symlen; i++) {
+		sym = getsym(s, i);
+		if (sym.type == SymLitlen) {
+			lfreq[sym.n]++;
+			ln++;
+		}
+		if (sym.type == SymDist) {
+			dfreq[sym.n]++;
+			dn++;
+		}
+		if (sym.type == SymExtra)
+			extra += 8 * sym.len;
+	}
+	len = hlen + nlog(ln) + nlog(dn);
+	for (i = 0; i < Nlitlen; i++)
+		len -= nlog(lfreq[i]);
+	for (i = 0; i < Ndist; i++)
+		len -= nlog(dfreq[i]);
+*/
+	len = hlen;
+	bestlen = longestlen = besti = 0;
+	bestrate = len << 9;
 	for (i = 0; i < s->symlen; i++) {
 		sym = getsym(s, i);
 		if (sym.type == SymLitlen) {
 			if (sym.n < Nlit) {
-				int vfm = i * 32768 / len;
+				uint rate = ((uint)len << 9)/(ln + dn);
 
-				if (vfm > bestvfm) {
-					bestlen = i;
-					bestvfm = vfm;
+				if (rate < bestrate) {
+					besti = i;
+					bestlen = len;
+					bestrate = rate;
 				}
 				longestlen = i;
 			}
-			len += lfreq[sym.n] * log2_8(lfreq[sym.n]);
-			len -= ltotal * log2_8(ltotal);
+			len += nlog(lfreq[sym.n]);
+			len -= nlog(ln);
 			lfreq[sym.n]++;
-			ltotal++;
-			len -= lfreq[sym.n] * log2_8(lfreq[sym.n]);
-			len += ltotal * log2_8(ltotal);
+			ln++;
+			len += nlog(ln);
+			len -= nlog(lfreq[sym.n]);
 		}
 		if (sym.type == SymDist) {
-			len += dfreq[sym.n] * log2_8(dfreq[sym.n]);
-			len -= dtotal * log2_8(dtotal);
+			len += nlog(dfreq[sym.n]);
+			len -= nlog(dn);
 			dfreq[sym.n]++;
-			dtotal++;
-			len -= dfreq[sym.n] * log2_8(dfreq[sym.n]);
-			len += dtotal * log2_8(dtotal);
+			dn++;
+			len += nlog(dn);
+			len -= nlog(dfreq[sym.n]);
 		}
-		if (sym.type == SymExtra)
-			len += 8 * sym.len;
 	}
-	block(s, bestlen, longestlen);
+fprintf(stderr, "i: %u bits: %u rate: %u full: %u\n", besti, bestlen>>3, bestrate>>5, ((uint)len<<9)/(ln+dn) >> 5);
+	block(s, besti, longestlen);
 }
 
 static int count = 0;
@@ -745,6 +778,8 @@ int deflate(uchar *src, int len, uchar *dst) {
 	s.dst = dst;
 	lzcompress(&s, src, len);
 	chooseblock(&s);
+	if (s.symlen > 4000)
+		chooseblock(&s);
 	s.lastblock = 1;
 	block(&s, s.symlen, s.symlen);
 	outbits(&s, 0, 7);