flate

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

commit 1428f6315a1c5918bd4fabd2daaa1eb0145a11a7
parent e6de1ab18b761e304518e0b3bb50c39b8ad83452
Author: nsz@tpx <unknown>
Date:   Sun,  9 Aug 2009 21:53:49 +0200

deflate cleanups (s/pos/s->pos/, todo update)
Diffstat:
deflate.c | 67++++++++++++++++++++++++++++++++-----------------------------------
1 file changed, 32 insertions(+), 35 deletions(-)

diff --git a/deflate.c b/deflate.c @@ -5,20 +5,17 @@ /* TODO: - hufflen: parent+heap only + (hufflen: parent+heap only) match: check backwards block end guess with lfreq, dfreq bisect len/distbase -> lookup table - buffer window: ushort pos: let it overflow - rolling hash - save prevm instead roll back on block boundary - read until avail > MaxMatch - runlen -> lz (rename) + (rolling hash) + . runlen -> lz (rename) bounds on the compressend size - zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree + (zlib huffcode trick: if same freq then shorter code goes to the one with smaller subtree) overlap freq/code, rbuf/dstwin ? - fix match (loopunroll near end) - better dstsize (blocklen <= 32k) + . better dstsize (blocklen <= 32k) + . input from in+nin instead of src+srcend spec case tests: empty block @@ -29,17 +26,17 @@ spec case tests: */ enum { - MinMatch = 3, - MaxMatch = 258, - MaxChainLen = 256, + MinMatch = 3, /* min match length */ + MaxMatch = 258, /* max match length */ + MaxChainLen = 256, /* max length of hash chain */ HashBits = 13, - HashSize = 1 << HashBits, - BigDist = 1 << 12, - MaxDist = 1 << 15, - WinSize = 2*MaxDist + MaxMatch, - DstSize = 2*WinSize + 8, - RbufSize = 1 << 13, - RunlenFlag = 1 << 15, + HashSize = 1 << HashBits, /* hash table size */ + BigDist = 1 << 12, /* max match distance for short match length */ + MaxDist = 1 << 15, /* max match distance */ + WinSize = 2*MaxDist + MaxMatch, /* input window size */ + DstSize = WinSize + 8, /* output window size (worst case compressed block size) */ + RbufSize = 1 << 13, /* lz buffer size */ + RunlenFlag = 1 << 15, /* marks literal run length in lz buffer */ CodeBits = 16, /* max number of bits in a code + 1 */ EOB = 256, /* end of block symbol */ @@ -61,21 +58,21 @@ typedef struct { } Runlen; typedef struct { - int state; - int pos; - int avail; - int startpos; - int lastblock; - Match prevm; - uchar *src; /* input (block start) */ + int state; /* prev return value */ + int pos; /* position in input win */ + int avail; /* available in input win */ + int startpos; /* block start pos in input win */ + int lastblock; /* is last block */ + Match prevm; /* previous (deferred) match */ + uchar *src; /* input data (not yet in win) */ uchar *srcend; - uchar *dst; /* compressed output */ - uchar *dstbegin; + uchar *dst; /* compressed output (position in dstbuf) */ + uchar *dstbegin; /* start position of unflushed data in dstbuf */ uint bits; int nbits; - uchar win[WinSize]; + uchar win[WinSize]; /* input window */ ushort head[HashSize]; /* position of hash chain heads */ - ushort chain[MaxDist]; /* hash chains next */ + ushort chain[MaxDist]; /* hash chain */ Runlen rbuf[RbufSize]; /* literal run length, match len, match dist */ Runlen *rend; /* current pos in rbuf */ int run; /* literal count */ @@ -500,14 +497,14 @@ static ushort addtochain(State *s, ushort pos) { return i; } -static Match getmatch(State *s, int pos, int mpos) { +static Match getmatch(State *s, int mpos) { Match m = {0, MinMatch-1}; int len; int maxlen = s->avail < MaxMatch ? s->avail : MaxMatch; - int limit = pos - MaxDist; + int limit = s->pos - MaxDist; int chainlen = MaxChainLen; uchar *q; - uchar *p = s->win + pos; + uchar *p = s->win + s->pos; uchar *end = p + MaxMatch; do { @@ -525,7 +522,7 @@ static Match getmatch(State *s, int pos, int mpos) { len = MaxMatch - (end - p); p -= len; if (len > m.len) { - m.dist = pos - mpos; + m.dist = s->pos - mpos; if (len >= maxlen) { m.len = maxlen; return m; @@ -599,7 +596,7 @@ static int deflate_state(State *s) { if (head >= s->pos || s->pos - head >= MaxDist) head = 0; if (head) - m = getmatch(s, s->pos, head); + m = getmatch(s, head); if (head && m.len > s->prevm.len) { if (s->prevm.len) recordlit(s, s->win[s->pos-1]);