flate

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

commit 44ccdf16a1e951aff295edcbc76b23b4117a36e8
parent 2e11080e70d83bc8d30c95a37c3191db79609a00
Author: nsz <nszabolcs@gmail.com>
Date:   Tue, 11 Aug 2009 14:19:18 +0200

deflate += comments
Diffstat:
deflate.c | 31++++++++++++++++++++++---------
1 file changed, 22 insertions(+), 9 deletions(-)

diff --git a/deflate.c b/deflate.c @@ -79,7 +79,7 @@ typedef struct { ushort chain[MaxDist]; /* hash chain */ LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */ LzCode *lz; /* current pos in lzbuf */ - int run; /* literal run length */ + int nlit; /* literal run length */ ushort lfreq[Nlitlen]; ushort dfreq[Ndist]; uchar dstbuf[DstSize]; @@ -277,6 +277,7 @@ static void putbits(State *s, uint bits, int n) { } } +/* run length encode literal and dist code lengths into codes and extra */ static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *dlen, int ndist) { int i, c, r, rr; int n = 0; @@ -286,7 +287,6 @@ static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *d for (i = 0; i < ndist; i++) codes[nlit + i] = dlen[i]; for (i = 0; i < nlit + ndist;) { - /* run length encoding */ c = codes[i]; for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++); i += r; @@ -316,6 +316,7 @@ static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *d return n; } +/* compress block data into s->dstbuf using given codes */ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) { int n; LzCode *lz; @@ -336,6 +337,7 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar putbits(s, lcode[EOB], llen[EOB]); } +/* build code trees and select dynamic/fixed/uncompressed block compression */ static void deflate_block(State *s) { uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist]; uchar llen[Nlitlen], dlen[Ndist], clen[Nclen]; @@ -365,7 +367,7 @@ static void deflate_block(State *s) { huffcodes(ccode, clen, Nclen); for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--); - /* calc size */ + /* calc compressed size */ uncsize = 3 + 16 + 8 * blocklen + (16 - 3 - s->nbits) % 8; /* byte aligned */ fixsize = 3; dynsize = 3 + 5 + 5 + 4 + 3 * nclen; @@ -443,6 +445,7 @@ fprintf(stderr, "blen: %d [%d,%d] lzlen: %d dynlen: %d (tree: %d, rate: %.3f) fi */ } +/* find n in base */ static int bisect(ushort *base, int len, int n) { int lo = 0; int hi = len; @@ -458,15 +461,17 @@ static int bisect(ushort *base, int len, int n) { return lo - 1; } +/* add literal run length to lzbuf */ static void flushlit(State *s) { - if (s->run) { + if (s->nlit) { s->lz->bits = LzLitFlag; - s->lz->n = s->run; + s->lz->n = s->nlit; s->lz++; - s->run = 0; + s->nlit = 0; } } +/* add match to lzbuf and update freq counts */ static void recordmatch(State *s, Match m) { int n; @@ -483,16 +488,18 @@ static void recordmatch(State *s, Match m) { s->dfreq[n]++; } +/* update literal run length */ static void recordlit(State *s, int c) { - s->run++; + s->nlit++; s->lfreq[c]++; } -/* multiplicative hash */ +/* multiplicative hash (using a prime close to golden ratio * 2^32) */ static int gethash(uchar *p) { return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits)) % HashSize; } +/* update hash chain at the current position */ static int updatechain(State *s) { int h, i; @@ -507,6 +514,7 @@ static int updatechain(State *s) { return i; } +/* find longest match, mpos is the next in the hash chain */ static Match getmatch(State *s, int mpos) { Match m = {0, MinMatch-1}; int len; @@ -538,16 +546,18 @@ static Match getmatch(State *s, int mpos) { return m; } +/* start a new block */ static void newblock(State *s) { s->startpos = s->pos; s->dst = s->dstbegin = s->dstbuf; s->lz = s->lzbuf; - s->run = 0; + s->nlit = 0; memset(s->lfreq, 0, sizeof(s->lfreq)); memset(s->dfreq, 0, sizeof(s->dfreq)); s->lfreq[EOB]++; } +/* shift and fill win from s->src */ static int fillwin(State *s) { int n, k; @@ -576,6 +586,7 @@ static int fillwin(State *s) { return 1; } +/* check if the current block should be ended */ static int endofblock(State *s) { if (s->avail == 0) return 1; @@ -585,6 +596,7 @@ static int endofblock(State *s) { return 0; } +/* deflate from s->src into s->dstbuf */ static int deflate_state(State *s) { Match m; int head; @@ -636,6 +648,7 @@ static int deflate_state(State *s) { } } +/* alloc and init state */ static State *alloc_state(void) { State *s = malloc(sizeof(State)); int i;