commit 31fab0436815a7314aee7f320c610ecf6897223f
parent 7b98214df9de69821c5e453e7da7ade99e8516e7
Author: nsz <nszabolcs@gmail.com>
Date: Wed, 15 Jul 2009 07:26:44 +0200
deflate fix clencode bug
Diffstat:
| deflate_simple.c | | | 116 | +++++++++++++++++++++++++++++++++++-------------------------------------------- |
1 file changed, 52 insertions(+), 64 deletions(-)
diff --git a/deflate_simple.c b/deflate_simple.c
@@ -2,11 +2,11 @@
#include <string.h>
#include <stdio.h>
-
/*
TODO:
hufflen: parent+heap only
- match: check backwards
+ match: check backwards, lazy
+ block end: lcount, dcount
*/
typedef unsigned char uchar;
@@ -18,7 +18,6 @@ enum {
MaxMatch = 258,
MaxChainStep = 64,
HashSize = 2039,
- HashChars = 3, /* TODO: unused */
WinSize = 1 << 15,
SymSize = 1 << 16,
@@ -87,6 +86,7 @@ static uchar clenorder[Nclen] = {
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};
+
static uint revcode(uint c, int n) {
int i;
uint r = 0;
@@ -256,7 +256,7 @@ static void putbits(State *s, uint bits, int n) {
}
static int clencodes(int *codes, int *extra, uchar *llen, int nlit, uchar *dlen, int ndist) {
- int i, c, r, rb;
+ int i, c, r, rr;
int n = 0;
/* int exbits = 0;*/
@@ -267,14 +267,14 @@ static int clencodes(int *codes, int *extra, uchar *llen, int nlit, uchar *dlen,
for (i = 0; i < nlit + ndist;) {
/* run length encoding */
c = codes[i];
- for (r = 1; r < nlit + ndist && codes[i + r] == c; r++);
+ for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++);
i += r;
if (c == 0) {
while (r >= 11) {
- rb = r > 138 ? 138 : r;
+ rr = r > 138 ? 138 : r;
codes[n] = 18;
- extra[n++] = rb - 11;
- r -= rb;
+ extra[n++] = rr - 11;
+ r -= rr;
/* exbits += 7;*/
}
if (r >= 3) {
@@ -287,10 +287,10 @@ static int clencodes(int *codes, int *extra, uchar *llen, int nlit, uchar *dlen,
while (r--) {
codes[n++] = c;
while (r >= 3) {
- rb = r > 6 ? 6 : r;
+ rr = r > 6 ? 6 : r;
codes[n] = 16;
- extra[n++] = rb - 3;
- r -= rb;
+ extra[n++] = rr - 3;
+ r -= rr;
/* exbits += 2;*/
}
}
@@ -319,7 +319,6 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar
c = *p++;
putbits(s, dcode[c & 0xff], dlen[c & 0xff]);
putbits(s, c >> 16, (c >> 8) & 0xff);
-
}
}
/* EOB */
@@ -343,7 +342,6 @@ static void emitblock(State *s, int blocklen) {
huffcodes(dcode, dlen, Ndist);
for (nlit = Nlitlen; nlit > Nlit && llen[nlit-1] == 0; nlit--);
for (ndist = Ndist; ndist > 1 && dlen[ndist-1] == 0; ndist--);
-
nc = clencodes(codes, extra, llen, nlit, dlen, ndist);
memset(cfreq, 0, sizeof(cfreq));
for (i = 0; i < nc; i++)
@@ -367,7 +365,6 @@ static void emitblock(State *s, int blocklen) {
if (c == 18)
dynsize += 7;
}
-fprintf(stderr, "tree len: %d bits: %d\n", nc, dynsize);
for (p = s->lzbuf, plit = s->src; p != s->lzp;) {
c = *p++;
if (c >= LzRunlen) {
@@ -394,7 +391,7 @@ fprintf(stderr, "tree len: %d bits: %d\n", nc, dynsize);
putbits(s, s->lastblock, 1);
if (dynsize < fixsize && dynsize < uncsize) {
-fprintf(stderr, "dyn ");
+ /* dynamic code */
putbits(s, 2, 2);
putbits(s, nlit - 257, 5);
putbits(s, ndist - 1, 5);
@@ -416,10 +413,11 @@ fprintf(stderr, "dyn ");
/* block data + eob */
putblock(s, lcode, llen, dcode, dlen);
} else if (fixsize < uncsize) {
-fprintf(stderr, "fix ");
+ /* fixed code */
putbits(s, 1, 2);
putblock(s, fixed_lcode, fixed_llen, fixed_dcode, fixed_dlen);
} else {
+ /* uncompressed */
putbits(s, 0, 2);
putbits(s, 0, 7); /* align to byte boundary */
s->nbits = 0;
@@ -430,10 +428,8 @@ fprintf(stderr, "fix ");
fprintf(stderr, "blocklen: %d lzlen: %d dynsize: %d fixsize: %d uncsize: %d\n", blocklen, s->lzp - s->lzbuf, dynsize, fixsize, uncsize);
}
+
static void recordlit(State *s, ushort lit) {
-/*
-fprintf(stderr, "%3d %c\n", lit, lit);
-*/
s->runlen++;
s->lfreq[lit]++;
}
@@ -455,9 +451,7 @@ static int bisect(ushort *base, int len, int n) {
static void recordmatch(State *s, Match m) {
int i;
-/*
-fprintf(stderr, "m %d, %d\n", m.dist, m.len);
-*/
+
if (s->runlen) {
*s->lzp++ = s->runlen | LzRunlen;
s->runlen = 0;
@@ -515,48 +509,7 @@ static void newblock(State *s, uchar *src) {
s->lfreq[i] = 0;
for (i = 0; i < Ndist; i++)
s->dfreq[i] = 0;
-}
-
-static void lzcompress(State *s, uchar *src, int len) {
- int step;
- int hash;
- Match m;
-
- newblock(s, src);
- while (len > 0) {
- m = getmatch(s, src, len);
- if (m.len >= MinMatch) {
- recordmatch(s, m);
- step = m.len;
- } else {
- recordlit(s, *src);
- step = 1;
- }
- while (step > 0) {
- if (len >= MinMatch) {
- hash = gethash(src);
- s->chain[s->pos] = s->head[hash];
- s->head[hash] = s->pos;
- s->pos = (s->pos + 1) % WinSize;
- }
- src++;
- len--;
- step--;
- }
- if (src - s->src > 1 << 15) {
- if (s->runlen)
- *s->lzp++ = s->runlen | LzRunlen;
- s->lfreq[256]++; /* EOB */
- emitblock(s, src - s->src);
- newblock(s, src);
- }
- }
- if (s->runlen)
- *s->lzp++ = s->runlen | LzRunlen;
s->lfreq[256]++; /* EOB */
- s->lastblock = 1;
- emitblock(s, src - s->src);
- putbits(s, 0, 7);
}
static void lzinit(State *s) {
@@ -586,10 +539,45 @@ static void lzinit(State *s) {
int deflate(uchar *src, int len, uchar *dst) {
State s;
+ int step;
+ int hash;
+ Match m;
lzinit(&s);
+ newblock(&s, src);
s.dst = dst;
- lzcompress(&s, src, len);
+ while (len > 0) {
+ m = getmatch(&s, src, len);
+ if (m.len >= MinMatch) {
+ recordmatch(&s, m);
+ step = m.len;
+ } else {
+ recordlit(&s, *src);
+ step = 1;
+ }
+ while (step > 0) {
+ if (len >= MinMatch) {
+ hash = gethash(src);
+ s.chain[s.pos] = s.head[hash];
+ s.head[hash] = s.pos;
+ s.pos = (s.pos + 1) % WinSize;
+ }
+ src++;
+ len--;
+ step--;
+ }
+ if (src - s.src > 1 << 15) {
+ if (s.runlen)
+ *s.lzp++ = s.runlen | LzRunlen;
+ emitblock(&s, src - s.src);
+ newblock(&s, src);
+ }
+ }
+ if (s.runlen)
+ *s.lzp++ = s.runlen | LzRunlen;
+ s.lastblock = 1;
+ emitblock(&s, src - s.src);
+ putbits(&s, 0, 7);
return s.dst - dst;
}
