flate

deflate implementation
git clone git://git.suckless.org/flate
Log | Files | Refs | README

commit 2a4423264be4b26a110c77a07ccd7e108e90c22d
parent d695e2aaa37ee9a3f7b05fe5e23cb3c6fbb7d3e2
Author: nsz <nszabolcs@gmail.com>
Date:   Wed, 15 Jul 2009 23:42:08 +0200

dont finish block until we have a lazy match
Diffstat:
deflate_simple.c | 61++++++++++++++++++++++++++++++++++---------------------------
1 file changed, 34 insertions(+), 27 deletions(-)

diff --git a/deflate_simple.c b/deflate_simple.c @@ -244,7 +244,7 @@ static void hufflens(uchar *lens, int *freqs, int nsym, int limit) { } } -/* adding n (<= 16) bits to dst */ +/* output n (<= 16) bits */ static void putbits(State *s, uint bits, int n) { s->bits |= bits << s->nbits; s->nbits += n; @@ -258,7 +258,6 @@ 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, rr; int n = 0; -/* int exbits = 0;*/ for (i = 0; i < nlit; i++) codes[i] = llen[i]; @@ -275,13 +274,11 @@ static int clencodes(int *codes, int *extra, uchar *llen, int nlit, uchar *dlen, codes[n] = 18; extra[n++] = rr - 11; r -= rr; -/* exbits += 7;*/ } if (r >= 3) { codes[n] = 17; extra[n++] = r - 3; r = 0; -/* exbits += 3;*/ } } while (r--) { @@ -291,7 +288,6 @@ static int clencodes(int *codes, int *extra, uchar *llen, int nlit, uchar *dlen, codes[n] = 16; extra[n++] = rr - 3; r -= rr; -/* exbits += 2;*/ } } } @@ -325,7 +321,7 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar putbits(s, lcode[256], llen[256]); } -static void emitblock(State *s, int blocklen) { +static void deflate_block(State *s, int blocklen) { int cfreq[Nclen]; uchar llen[Nlitlen], dlen[Ndist], clen[Nclen]; ushort lcode[Nlitlen], dcode[Ndist], ccode[Nclen]; @@ -351,7 +347,7 @@ static void emitblock(State *s, int blocklen) { for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--); /* calc size */ - uncsize = 3 + 4 + 8*blocklen; /* +byte alignment (8-nbits+3)%8 */ + uncsize = 3 + 4 + 8*blocklen + (16 - 3 - s->nbits)%8; /* byte aligned */ fixsize = 3; dynsize = 3 + 5 + 5 + 4; dynsize += 3 * nclen; @@ -365,6 +361,7 @@ static void emitblock(State *s, int blocklen) { if (c == 18) dynsize += 7; } +/* TODO: */ for (p = s->lzbuf, plit = s->src; p != s->lzp;) { c = *p++; if (c >= LzRunlen) { @@ -498,19 +495,6 @@ static Match getmatch(State *s, uchar *src, int len) { return m; } -static void newblock(State *s, uchar *src) { - int i; - - s->src = src; - s->lzp = s->lzbuf; - s->runlen = 0; - for (i = 0; i < Nlitlen; i++) - s->lfreq[i] = 0; - for (i = 0; i < Ndist; i++) - s->dfreq[i] = 0; - s->lfreq[256]++; /* EOB */ -} - static void lzinit(State *s) { int i; @@ -536,19 +520,41 @@ static void lzinit(State *s) { s->lastblock = 0; } +static void newblock(State *s) { + int i; + + s->lzp = s->lzbuf; + s->runlen = 0; + for (i = 0; i < Nlitlen; i++) + s->lfreq[i] = 0; + for (i = 0; i < Ndist; i++) + s->dfreq[i] = 0; + s->lfreq[256]++; /* EOB */ +} + int deflate(uchar *src, int len, uchar *dst) { State s; int step; int hash; Match m; Match prevm = {0, 0}; - uchar prevc = '\0'; + uchar prevc = 0; lzinit(&s); - newblock(&s, src); + newblock(&s); s.dst = dst; + s.src = 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; + } +*/ if (m.len >= MinMatch) if (m.len <= prevm.len) { recordmatch(&s, prevm); @@ -570,6 +576,7 @@ int deflate(uchar *src, int len, uchar *dst) { recordlit(&s, *src); step = 1; } + while (step > 0) { if (len >= MinMatch) { hash = gethash(src); @@ -581,18 +588,18 @@ int deflate(uchar *src, int len, uchar *dst) { len--; step--; } - if (src - s.src > 1 << 15) { + if (prevm.len == 0 && src - s.src > 1<<15) { if (s.runlen) *s.lzp++ = s.runlen | LzRunlen; - emitblock(&s, src - s.src); - newblock(&s, src); + deflate_block(&s, src - s.src); + newblock(&s); + s.src = src; } } - if (s.runlen) *s.lzp++ = s.runlen | LzRunlen; s.lastblock = 1; - emitblock(&s, src - s.src); + deflate_block(&s, src - s.src); putbits(&s, 0, 7); return s.dst - dst; }