flate

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

commit 8357a25a970d35e014c98530be0d853a24a3b37c
parent d374cb0ffda5de8dbdf8d084f37d3118e582a282
Author: nsz <nszabolcs@gmail.com>
Date:   Tue, 18 Aug 2009 19:55:00 +0200

fix callback, s/hist/win/, clean up match
Diffstat:
deflate.c | 80++++++++++++++++++++++++++++++++++++++-----------------------------------------
1 file changed, 38 insertions(+), 42 deletions(-)

diff --git a/deflate.c b/deflate.c @@ -21,7 +21,6 @@ enum { MaxDist = WinSize - MaxMatch + 1, /* worst case available history */ StartPos = WinSize - MaxMatch + 1, /* block start position */ EndPos = 2*WinSize - MaxMatch + 1, /* block end position */ - HistSize = 2*WinSize, /* history buffer size (64K, indexed with ushort) */ DstSize = WinSize + MaxMatch + 6, /* worst case compressed block size */ LzSize = 1 << 13, /* lz buffer size */ LzEnd = LzSize - 2, /* guard that lzbuf does not overflow in the next iteration */ @@ -45,13 +44,13 @@ typedef struct { int startpos; /* block start pos in input win */ int avail; /* available in input win */ Match prevm; /* previous (deferred) match */ - uchar *src; /* input data (not yet in hist) */ + uchar *src; /* input data (not yet in win) */ uchar *srcend; uchar *dst; /* compressed output (position in dstbuf) */ uchar *dstbegin; /* start position of unflushed data in dstbuf */ uint bits; int nbits; - uchar hist[HistSize]; /* history (input buffer) */ + uchar win[2*WinSize]; /* input window */ ushort head[HashSize]; /* position of hash chain heads */ ushort chain[WinSize]; /* hash chain */ LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */ @@ -297,14 +296,14 @@ static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *d static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) { int n; LzCode *lz; - uchar *h; + uchar *p; - for (lz = s->lzbuf, h = s->hist + s->startpos; lz != s->lz; lz++) + for (lz = s->lzbuf, p = s->win + s->startpos; lz != s->lz; lz++) if (lz->bits & LzLitFlag) - for (n = lz->n; n > 0; n--, h++) - putbits(s, lcode[*h], llen[*h]); + for (n = lz->n; n > 0; n--, p++) + putbits(s, lcode[*p], llen[*p]); else { - h += lenbase[lz->n] + lz->bits; + p += lenbase[lz->n] + lz->bits; putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]); putbits(s, lz->bits, lenbits[lz->n]); lz++; @@ -324,7 +323,7 @@ static void deflate_block(State *s) { int i, c, n, ncodes; int nlit, ndist, nclen; LzCode *lz; - uchar *h; + uchar *p; int dynsize, fixsize, uncsize; int blocklen = s->pos - s->startpos; /* int dyntree; */ @@ -359,14 +358,14 @@ static void deflate_block(State *s) { dynsize += 7; } /* dyntree = dynsize - 3; */ - for (lz = s->lzbuf, h = s->hist + s->startpos; lz != s->lz; lz++) + for (lz = s->lzbuf, p = s->win + s->startpos; lz != s->lz; lz++) if (lz->bits & LzLitFlag) - for (n = lz->n; n > 0; n--, h++) { - fixsize += fixllen[*h]; - dynsize += llen[*h]; + for (n = lz->n; n > 0; n--, p++) { + fixsize += fixllen[*p]; + dynsize += llen[*p]; } else { - h += lenbase[lz->n] + lz->bits; + p += lenbase[lz->n] + lz->bits; fixsize += fixllen[Nlit + lz->n + 1]; dynsize += llen[Nlit + lz->n + 1]; fixsize += lenbits[lz->n]; @@ -412,7 +411,7 @@ static void deflate_block(State *s) { s->nbits = 0; putbits(s, blocklen, 16); putbits(s, ~blocklen & 0xffff, 16); - memcpy(s->dst, s->hist + s->startpos, blocklen); + memcpy(s->dst, s->win + s->startpos, blocklen); s->dst += blocklen; } /* @@ -480,10 +479,9 @@ static int gethash(uchar *p) { static int updatechain(State *s) { int h, i; - /* eliminating this check didn't make the code faster */ if (s->avail < MinMatch) return 0; - h = gethash(s->hist + s->pos); + h = gethash(s->win + s->pos); i = s->head[h]; s->head[h] = s->pos; if (i >= s->pos || s->pos - i > MaxDist) @@ -496,29 +494,28 @@ static int updatechain(State *s) { static Match getmatch(State *s, int mpos) { Match m = {0, MinMatch-1}; int len; + int maxlen = s->avail < MaxMatch ? s->avail : MaxMatch; int limit = s->pos - MaxDist; int chainlen = MaxChainLen; uchar *q; - uchar *p = s->hist + s->pos; - uchar *end = p + MaxMatch; + uchar *p = s->win + s->pos; + uchar *end = p + maxlen; do { - q = s->hist + mpos; + q = s->win + mpos; /* next match should be at least m.len+1 long */ if (q[m.len] != p[m.len] || q[m.len-1] != p[m.len-1] || q[0] != p[0]) continue; while (++p != end && *++q == *p); - len = MaxMatch - (end - p); + len = maxlen - (end - p); p -= len; if (len > m.len) { m.dist = s->pos - mpos; - if (len >= s->avail || len == MaxMatch) { - m.len = s->avail < MaxMatch ? s->avail : MaxMatch; - return m; - } m.len = len; + if (len == maxlen) + return m; } - /* >= limit can be allowed except if limit == 0 */ + /* >= limit can be allowed except when limit == 0 */ } while ((mpos = s->chain[mpos % WinSize]) > limit && --chainlen); if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist)) m.len = 0; @@ -551,7 +548,7 @@ static int endblock(State *s) { return 1; } /* shift input window */ - memcpy(s->hist, s->hist + WinSize, WinSize); + memcpy(s->win, s->win + WinSize, WinSize); for (n = 0; n < HashSize; n++) s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0; for (n = 0; n < WinSize; n++) @@ -562,6 +559,7 @@ static int endblock(State *s) { return 0; } +/* fill input window */ static int fillwin(State *s) { int n, k; @@ -571,7 +569,7 @@ static int fillwin(State *s) { n = 2*WinSize - s->pos - s->avail; /* s->avail + n >= MaxMatch */ if (k > n) k = n; - memcpy(s->hist + s->pos + s->avail, s->src, k); + memcpy(s->win + s->pos + s->avail, s->src, k); s->src += k; s->avail += k; if (s->avail < MaxMatch) /* s->srcend == s->src */ @@ -580,7 +578,7 @@ static int fillwin(State *s) { return 1; } -/* deflate from s->src into s->dstbuf */ +/* deflate compress from s->src into s->dstbuf */ static int deflate_state(State *s) { Match m; int head; @@ -610,7 +608,7 @@ static int deflate_state(State *s) { m = getmatch(s, head); if (head && m.len > s->prevm.len) { if (s->prevm.len) - recordlit(s, s->hist[s->pos-1]); + recordlit(s, s->win[s->pos-1]); s->prevm = m; } else if (s->prevm.len) { recordmatch(s, s->prevm); @@ -621,7 +619,7 @@ static int deflate_state(State *s) { updatechain(s); } while (--s->prevm.len); } else - recordlit(s, s->hist[s->pos]); + recordlit(s, s->win[s->pos]); s->pos++; s->avail--; } @@ -649,6 +647,8 @@ static State *alloc_state(void) { fixdlen[i] = 5; huffcodes(fixlcode, fixllen, Nlitlen); huffcodes(fixdcode, fixdlen, Ndist); + s->state = FlateOut; + s->src = s->srcend = 0; s->dst = s->dstbegin = s->dstbuf; s->pos = s->startpos = StartPos; s->eof = 0; @@ -673,8 +673,6 @@ int deflate(FlateStream *stream) { s = stream->state = alloc_state(); if (!s) return stream->err = "no mem.", FlateErr; - s->state = FlateOut; - s->src = s->srcend = 0; } if (stream->nin) { s->src = stream->in; @@ -698,27 +696,25 @@ int deflate(FlateStream *stream) { 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 << 12}; + enum {SrcSize = 1 << 13}; s = alloc_state(); if (!s) return FlateErr; - s->src = s->srcend = malloc(SrcSize); - if (!s->src) { + src = s->src = s->srcend = malloc(SrcSize); + if (!src) { free(s); return FlateErr; } - s->state = FlateOut; for (;;) { n = deflate_state(s); switch (n) { case FlateIn: + s->src = src; len = r(s->src, SrcSize, rdata); - if (len > 0) - s->srcend = s->src + len; - else - s->state = FlateErr; + s->srcend = s->src + len; break; case FlateOut: len = w(s->dstbegin, s->dst - s->dstbegin, wdata); @@ -729,7 +725,7 @@ int deflate_callback(int (*r)(void *, int, void *), void *rdata, int (*w)(void * break; case FlateOk: case FlateErr: - free(s->src); + free(src); free(s); return n; }