flate

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

commit 6ee26d56c3e3e39af131e339290495825e8951a3
parent 0a06e6487a7525f7cb49d3b211c551abe56e596c
Author: nsz <nszabolcs@gmail.com>
Date:   Sat,  4 Jul 2009 20:15:24 +0200

decode simple +multiple blocks
Diffstat:
deflate_simple.c | 131+++++++++++++++++++++++++++++++++++++++++++++++--------------------------------
inflate.c | 6+++---
2 files changed, 81 insertions(+), 56 deletions(-)

diff --git a/deflate_simple.c b/deflate_simple.c @@ -30,11 +30,6 @@ typedef struct { ushort len; } Match; -typedef struct { - uchar *len; /* bit length of the code */ - ushort *code; -} Huff; - enum { SymLitlen, SymDist, @@ -65,19 +60,12 @@ typedef struct { int firstblock; int lastblock; int finished; - - Huff fixed_litlen; - Huff fixed_dist; - Huff litlen; - Huff dist; - Huff clen; } State; -#if 0 -/* TODO: globals.. */ -static Huff lhuff; /* fixed lit/len huffman code tree */ -static Huff dhuff; /* fixed distance huffman code tree */ -#endif +static uchar fixed_llen[Nlitlen]; /* fixed lit/len huffman code tree */ +static ushort fixed_lcode[Nlitlen]; +static uchar fixed_dlen[Ndist]; /* fixed distance huffman code tree */ +static ushort fixed_dcode[Ndist]; /* base offset and extra bits tables */ static uchar lenbits[Nlen] = { @@ -102,16 +90,6 @@ static short gethash(uchar *p) { return (257 * p[0] + 263 * p[1] + 269 * p[2]) % HashSize; } -static void lzinit(State *s) { - int i; - - for (i = 0; i < WinSize; i++) - s->chain[i] = 0; - for (i = 0; i < HashSize; i++) - s->head[i] = 0; - s->pos = 0; -} - static Match getmatch(State *s, uchar *src, int len) { int i, j; int pos; @@ -395,7 +373,9 @@ static void hufflenslimit(uchar *lens, int *freqs, int nsym, int limit) { /* adding < 16 bits to dst */ static void outbits(State *s, uint bits, int nbits) { +/* fprintf(stderr, "b:%3d n:%3d\n", bits, nbits); +*/ s->bits |= bits << s->nbits; s->nbits += nbits; while (s->nbits >= 8) { @@ -414,8 +394,12 @@ static Sym makesym(int type, int len, int sym) { return s; } +static void chooseblock(State *s); + static void putsym(State *s, Sym sym) { s->symbuf[(s->symstart + s->symlen++) % SymSize] = sym; + if (s->symlen == SymSize) + chooseblock(s); } static Sym getsym(State *s, int i) { @@ -487,15 +471,13 @@ static void block(State *s, int dynlen, int fixlen) { Sym sym; int nsym; int i, nlit, ndist, nclen; - int dynsize; + int dynsize, fixsize; int blocklen; - int dynamic; - int lastblock; memset(lfreq, 0, sizeof(lfreq)); memset(dfreq, 0, sizeof(dfreq)); lfreq[256] = 1; /* EOB */ - for (i = 0; i < s->symlen; i++) { + for (i = 0; i < dynlen; i++) { sym = getsym(s, i); if (sym.type == SymLitlen) lfreq[sym.n]++; @@ -530,6 +512,7 @@ static void block(State *s, int dynlen, int fixlen) { if (sym.type == SymExtra) dynsize += sym.len; } +fprintf(stderr, "tree len: %d bits: %d\n", nsym, dynsize); for (i = 0; i < dynlen; i++) { sym = getsym(s, i); if (sym.type == SymLitlen) @@ -540,16 +523,22 @@ static void block(State *s, int dynlen, int fixlen) { dynsize += sym.len; } dynsize += llen[256]; /* EOB */ -/* - dynamic = (long long)fsize * dynlen > (long long)dsize * fixlen; - blocklen = dynamic ? dlen : fixlen; -*/ - dynamic = 1; - blocklen = dynlen; - lastblock = 1; - outbits(s, lastblock ? 1 : 0, 1); - if (dynamic) { + fixsize = 3; + for (i = 0; i < fixlen; i++) { + sym = getsym(s, i); + if (sym.type == SymLitlen) + fixsize += fixed_llen[sym.n]; + if (sym.type == SymDist) + fixsize += fixed_dlen[sym.n]; + if (sym.type == SymExtra) + fixsize += sym.len; + } + fixsize += fixed_llen[256]; /* EOB */ + + outbits(s, s->lastblock, 1); + if ((long long)fixsize * dynlen > (long long)dynsize * fixlen) { + blocklen = dynlen; outbits(s, 2, 2); outbits(s, nlit - 257, 5); outbits(s, ndist - 1, 5); @@ -577,9 +566,23 @@ static void block(State *s, int dynlen, int fixlen) { } /* EOB */ outbits(s, lcode[256], llen[256]); + } else { + blocklen = fixlen; + outbits(s, 1, 2); + /* block data */ + for (i = 0; i < fixlen; i++) { + sym = getsym(s, i); + if (sym.type == SymLitlen) + outbits(s, fixed_lcode[sym.n], fixed_llen[sym.n]); + if (sym.type == SymDist) + outbits(s, fixed_dcode[sym.n], fixed_dlen[sym.n]); + if (sym.type == SymExtra) + outbits(s, sym.n, sym.len); + } + /* EOB */ + outbits(s, fixed_lcode[256], fixed_llen[256]); } - -fprintf(stderr, "blocklen: %d symlen: %d dynsize: %d\n", blocklen, s->symlen, dynsize); +fprintf(stderr, "blocklen: %d symlen: %d dynsize: %d dynlen: %d fixsize: %d fixlen:%d\n", blocklen, s->symlen, dynsize, dynlen, fixsize, fixlen); s->symstart = (s->symstart + blocklen) % SymSize; s->symlen -= blocklen; } @@ -621,11 +624,11 @@ static void chooseblock(State *s) { memset(lfreq, 0, sizeof(lfreq)); memset(dfreq, 0, sizeof(dfreq)); - lfreq[256] = 1; /* we're bound to need one EOB */ + lfreq[256] = 1; /* we're bound to need one EOB */ ltotal = 1; dtotal = longestlen = bestvfm = 0; bestlen = -1; - len = 300 * 8; /* very approximate size of the Huffman trees */ + len = 400 * 8; /* approximate size of the Huffman trees */ for (i = 0; i < s->symlen; i++) { sym = getsym(s, i); if (sym.type == SymLitlen) { @@ -645,8 +648,6 @@ static void chooseblock(State *s) { len -= lfreq[sym.n] * log2_8(lfreq[sym.n]); len += ltotal * log2_8(ltotal); } - if (sym.type == SymExtra) - len += 8 * sym.len; if (sym.type == SymDist) { len += dfreq[sym.n] * log2_8(dfreq[sym.n]); len -= dtotal * log2_8(dtotal); @@ -655,17 +656,18 @@ static void chooseblock(State *s) { len -= dfreq[sym.n] * log2_8(dfreq[sym.n]); len += dtotal * log2_8(dtotal); } + if (sym.type == SymExtra) + len += 8 * sym.len; } -/* block(s, bestlen, longestlen);*/ - block(s, s->symlen, longestlen); + block(s, bestlen, longestlen); } static int count = 0; static void emitlit(State *s, ushort lit) { - if (s->symlen == SymSize) - chooseblock(s); +/* fprintf(stderr, "%3d %c\n", lit, lit); +*/ count++; putsym(s, makesym(SymLitlen, 0, lit)); } @@ -686,9 +688,9 @@ static int bisect(ushort *base, int len, int n) { } static void emitmatch(State *s, Match m) { - if (s->symlen + 5 >= SymSize) - chooseblock(s); +/* fprintf(stderr, "m %d, %d\n", m.dist, m.len); +*/ count++; while (m.len > 0) { int len; @@ -708,6 +710,29 @@ count++; } } +static void lzinit(State *s) { + int i; + + for (i = 0; i < WinSize; i++) + s->chain[i] = 0; + for (i = 0; i < HashSize; i++) + s->head[i] = 0; + s->pos = 0; + + for (i = 0; i < 144; i++) + fixed_llen[i] = 8; + for (; i < 256; i++) + fixed_llen[i] = 9; + for (; i < 280; i++) + fixed_llen[i] = 7; + for (; i < Nlitlen; i++) + fixed_llen[i] = 8; + huffcodes(fixed_lcode, fixed_llen, Nlitlen); + for (i = 0; i < Ndist; i++) + fixed_dlen[i] = 5; + huffcodes(fixed_dcode, fixed_dlen, Ndist); +} + int deflate(uchar *src, int len, uchar *dst) { State s; @@ -720,8 +745,8 @@ int deflate(uchar *src, int len, uchar *dst) { s.dst = dst; lzcompress(&s, src, len); chooseblock(&s); - if (s.symlen) - block(&s, s.symlen, s.symlen); + s.lastblock = 1; + block(&s, s.symlen, s.symlen); outbits(&s, 0, 7); return s.dst - dst; } diff --git a/inflate.c b/inflate.c @@ -71,11 +71,11 @@ typedef struct { int state; /* decode state */ int final; /* last block flag */ - /* for decoding dynamic code trees */ + /* for decoding dynamic code trees in inflate() */ int nlit; int ndist; - int nclen; /* also used for saving decoded symbol */ - int lenpos; /* also used for copy length */ + int nclen; /* also used in decode_block() */ + int lenpos; /* also used in decode_block() */ uchar lens[Nlitlen + Ndist]; int fixed; /* fixed code tree flag */