flate

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

commit 9de8fb994bd9a86f1f0948249d5fe49d6a9ea97d
parent cb7adc2901ab8582b02d3a77e9139c3fb70c6a49
Author: nsz@tpx <unknown>
Date:   Sat,  8 Aug 2009 19:57:03 +0200

deflate cleanup (wip)
Diffstat:
deflate.c | 112++++++++++++++++++++++++++++++++++++++-----------------------------------------
1 file changed, 54 insertions(+), 58 deletions(-)

diff --git a/deflate.c b/deflate.c @@ -64,7 +64,7 @@ typedef struct { int state; int pos; int avail; - int blockstart; + int startpos; int lastblock; Match prevm; uchar *src; /* input (block start) */ @@ -320,7 +320,7 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar Runlen *r; uchar *pc; - for (r = s->rbuf, pc = s->win + s->blockstart; r != s->rend; r++) + for (r = s->rbuf, pc = s->win + s->startpos; r != s->rend; r++) if (r->bits & RunlenFlag) for (n = r->n; n > 0; n--, pc++) putbits(s, lcode[*pc], llen[*pc]); @@ -377,7 +377,7 @@ int dyntree; dynsize += 7; } dyntree = dynsize - 3; - for (r = s->rbuf, pc = s->win + s->blockstart; r != s->rend; r++) + for (r = s->rbuf, pc = s->win + s->startpos; r != s->rend; r++) if (r->bits & RunlenFlag) for (n = r->n; n > 0; n--, pc++) { fixsize += fixllen[*pc]; @@ -430,7 +430,7 @@ dyntree = dynsize - 3; s->nbits = 0; putbits(s, blocklen, 16); putbits(s, ~blocklen & 0xffff, 16); - memcpy(s->dst, s->win + s->blockstart, blocklen); + memcpy(s->dst, s->win + s->startpos, blocklen); s->dst += blocklen; } fprintf(stderr, "blocklen: %d lzlen: %d dynsize: %d (tree: %d, rate: %.3f) fixsize: %d (rate: %.3f) uncsize: %d (rate: %.3f)\n", blocklen, s->rend - s->rbuf, @@ -539,6 +539,7 @@ static Match getmatch(State *s, ushort pos, ushort mpos) { } static void newblock(State *s) { + s->startpos = s->pos; s->dst = s->dstbegin = s->dstbuf; s->rend = s->rbuf; s->run = 0; @@ -557,7 +558,7 @@ static int fillwin(State *s) { s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0; for (n = WinSize; n--;) s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0; - s->blockstart -= WinSize; + s->startpos -= WinSize; s->pos -= WinSize; } k = 2*WinSize - s->pos - s->avail; @@ -574,80 +575,75 @@ static int fillwin(State *s) { static int deflate_state(State *s) { Match m; - Match prevm = {0, 0}; - int pos; int head; /* messy.. */ switch (s->state) { + case FlateOut: + if (s->dstbegin < s->dst) + return FlateOut; + if (s->lastblock) + return FlateOk; + newblock(s); + if (s->prevm.len) + s->pos++; + if (fillwin(s)) { + s->state = FlateIn; + return FlateIn; + } + break; + case FlateIn: + fillwin(s); + break; + } for (;;) { + head = addtochain(s, s->pos); + if (head >= s->pos || s->pos - head >= MaxDist) + head = 0; + if (head) + m = getmatch(s, s->pos, head); + if (head && m.len > s->prevm.len) { + if (s->prevm.len) + recordlit(s, s->win[s->pos-1]); + s->prevm = m; + } else if (s->prevm.len) { + recordmatch(s, s->prevm); + /* tricky.. */ + s->prevm.len -= 2; + do { + s->pos++; + s->avail--; + addtochain(s, s->pos); + } while (--s->prevm.len); + } else + recordlit(s, s->win[s->pos]); + s->pos++; + s->avail--; + if (s->avail < MaxMatch || s->rend - s->rbuf >= RbufSize - 2) { if (s->avail == 0) { flushlit(s); s->lastblock = 1; s->state = FlateOut; - deflate_block(s, pos - s->blockstart); + deflate_block(s, s->pos - s->startpos); putbits(s, 0, 7); return FlateOut; } - if (pos - s->blockstart > MaxDist || s->rend - s->rbuf >= RbufSize - 2) { + if (s->pos - s->startpos > MaxDist || s->rend - s->rbuf >= RbufSize - 2) { flushlit(s); - if (prevm.len) - pos--; -fprintf(stderr, "avail %d pos %d lastpos %d srcavail %d\n", s->avail, pos, s->pos, s->srcend - s->src); - deflate_block(s, pos - s->blockstart); - s->pos = pos; - s->prevm = prevm; + if (s->prevm.len) + s->pos--; +fprintf(stderr, "avail %d pos %d srcavail %d\n", s->avail, s->pos, s->srcend - s->src); + deflate_block(s, s->pos - s->startpos); s->state = FlateOut; return FlateOut; - case FlateOut: - if (s->dstbegin < s->dst) - return FlateOut; - if (s->lastblock) - return FlateOk; - newblock(s); - s->blockstart = pos = s->pos; - prevm = s->prevm; - if (prevm.len) - pos++; } - s->pos = pos; if (fillwin(s)) { - s->prevm = prevm; s->state = FlateIn; return FlateIn; - case FlateIn: - fillwin(s); - prevm = s->prevm; } - pos = s->pos; -fprintf(stderr, "avail %d pos %d srcavail %d\n", s->avail, s->pos, s->srcend - s->src); } - head = addtochain(s, pos); - if (head >= pos || pos - head >= MaxDist) - head = 0; - if (head) - m = getmatch(s, pos, head); - if (head && m.len > prevm.len) { - if (prevm.len) - recordlit(s, s->win[pos-1]); - prevm = m; - } else if (prevm.len) { - recordmatch(s, prevm); - /* too tricky.. */ - prevm.len -= 2; - do { - pos++; - s->avail--; - addtochain(s, pos); - } while (--prevm.len); - } else - recordlit(s, s->win[pos]); - pos++; - s->avail--; - } /* for(;;) */ - } /* switch */ - return FlateErr; /* unreachable */ + } } static State *alloc_state(void) { @@ -673,7 +669,7 @@ static State *alloc_state(void) { huffcodes(fixdcode, fixdlen, Ndist); s->dst = s->dstbegin = s->dstbuf; - s->pos = s->blockstart = WinSize; + s->pos = s->startpos = WinSize; s->avail = 0; return s; }