flate

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

commit a1f02b32650d405defac98da43ce6a4ca26dd202
parent 1642ddea0105b95c4b88e7dd794656a13d5a777d
Author: nsz <nszabolcs@gmail.com>
Date:   Sun, 23 Aug 2009 19:15:58 +0200

clean ups, -callback
Diffstat:
deflate.c | 85++++++++++++++++++++-----------------------------------------------------------
1 file changed, 21 insertions(+), 64 deletions(-)

diff --git a/deflate.c b/deflate.c @@ -18,11 +18,12 @@ enum { HashBits = 13, HashSize = 1 << HashBits, /* hash table size */ BigDist = 1 << 12, /* max match distance for short match length */ - BlockSize = (1 << 15) - 300, /* TODO */ MaxDist = WinSize, + BlockSize = 1 << 15, /* TODO */ SrcSize = 2*WinSize + MaxMatch, DstSize = BlockSize + MaxMatch + 6, /* worst case compressed block size */ LzSize = 1 << 13, /* lz buffer size */ + LzGuard = LzSize - 2, LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */ }; @@ -41,24 +42,24 @@ typedef struct { int startpos; /* block start pos in input src */ int endpos; /* end of available bytes in src */ int skip; /* skipped hash chain updates (until next iter) */ + Match prevm; /* previous (deferred) match */ int state; /* prev return value */ int eof; /* end of input */ - Match prevm; /* previous (deferred) match */ - int nin; uchar *in; /* input data (not yet in src) */ + uchar *inend; + uint bits; /* for output */ + int nbits; /* for output */ uchar *dst; /* compressed output (position in dstbuf) */ uchar *dstbegin; /* start position of unflushed data in dstbuf */ - uint bits; - int nbits; - uchar src[SrcSize]; /* input buf */ + LzCode *lz; /* current pos in lzbuf */ + int nlit; /* literal run length in lzbuf */ ushort head[HashSize]; /* position of hash chain heads */ ushort chain[WinSize]; /* hash chain */ - LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */ - LzCode *lz; /* current pos in lzbuf */ - int nlit; /* literal run length */ ushort lfreq[Nlitlen]; ushort dfreq[Ndist]; + uchar src[SrcSize]; /* input buf */ uchar dstbuf[DstSize]; + LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */ } State; static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */ @@ -558,10 +559,8 @@ static int shiftwin(State *s) { } static int endblock(State *s) { - LzCode *lzend = s->lzbuf + LzSize - 2; - if ((s->pos >= 2*WinSize && !shiftwin(s)) || s->pos - s->startpos >= BlockSize || - s->lz >= lzend || (s->eof && s->pos == s->endpos)) { + s->lzbuf - s->lz >= LzGuard || (s->eof && s->pos == s->endpos)) { /* deflate block */ flushlit(s); if (s->prevm.len) @@ -575,15 +574,15 @@ static int endblock(State *s) { } static int fillsrc(State *s) { - int n; + int n, k; if (s->endpos < SrcSize && !s->eof) { n = SrcSize - s->endpos; - if (n > s->nin) - n = s->nin; + k = s->inend - s->in; + if (n > k) + n = k; memcpy(s->src + s->endpos, s->in, n); s->in += n; - s->nin -= n; s->endpos += n; if (s->endpos < SrcSize) return 0; @@ -603,10 +602,9 @@ static int deflate_state(State *s) { Match m; int next; int guard; - LzCode *lzend; if (s->state == FlateIn) - s->eof = s->nin == 0; + s->eof = s->in == s->inend; else if (s->state == FlateOut) { if (s->dstbegin < s->dst) return (s->state = FlateOut); @@ -619,11 +617,10 @@ static int deflate_state(State *s) { return s->state; guard = calcguard(s); - lzend = s->lzbuf + LzSize - 2; -/*fprintf(stderr,"guard:%d pos:%d nin:%d\n", guard, s->pos, s->nin);*/ +/*fprintf(stderr,"guard:%d pos:%d nin:%d\n", guard, s->pos, s->inend - s->in);*/ for (;;) { - if (s->pos >= guard || s->lz >= lzend) { -/*fprintf(stderr,"guard:%d pos:%d len:%d end:%d start:%d nin:%d\n", guard, s->pos, s->pos - s->startpos, s->endpos, s->startpos, s->nin);*/ + if (s->pos >= guard || s->lzbuf - s->lz >= LzGuard) { +/*fprintf(stderr,"guard:%d pos:%d len:%d end:%d start:%d nin:%d\n", guard, s->pos, s->pos - s->startpos, s->endpos, s->startpos, s->inend - s->in);*/ if (endblock(s)) return (s->state = FlateOut); if (!fillsrc(s)) @@ -671,7 +668,7 @@ static State *alloc_state(void) { huffcodes(fixlcode, fixllen, Nlitlen); huffcodes(fixdcode, fixdlen, Ndist); s->state = FlateOut; - s->nin = 0; + s->in = s->inend = 0; s->dst = s->dstbegin = s->dstbuf; s->pos = s->startpos = s->endpos = WinSize; s->eof = 0; @@ -699,7 +696,7 @@ int deflate(FlateStream *stream) { } if (stream->nin) { s->in = stream->in; - s->nin = stream->nin; + s->inend = s->in + stream->nin; stream->nin = 0; } n = deflate_state(s); @@ -716,43 +713,3 @@ int deflate(FlateStream *stream) { } return n; } - -/* -int deflate_callback(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, void *), void *wdata) { - State *s; - uchar *src; - int len, n; - enum {SrcSize = 1 << 13}; - - s = alloc_state(); - if (!s) - return FlateErr; - src = s->src = s->srcend = malloc(SrcSize); - if (!src) { - free(s); - return FlateErr; - } - for (;;) { - n = deflate_state(s); - switch (n) { - case FlateIn: - s->src = src; - len = r(s->src, SrcSize, rdata); - s->srcend = s->src + len; - break; - case FlateOut: - len = w(s->dstbegin, s->dst - s->dstbegin, wdata); - if (len == s->dst - s->dstbegin) - s->dstbegin = s->dst; - else - s->state = FlateErr; - break; - case FlateOk: - case FlateErr: - free(src); - free(s); - return n; - } - } -} -*/