flate

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

commit e46afd79679b931cf1912ce2c98aa5293a3f006a
parent 92913b23713f768bc4467f5e29c9c0a4997d5b70
Author: nsz <nszabolcs@gmail.com>
Date:   Fri,  1 May 2009 11:08:08 +0200

inflate with callback wip
Diffstat:
inflate.c | 121+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------
1 file changed, 94 insertions(+), 27 deletions(-)

diff --git a/inflate.c b/inflate.c @@ -11,15 +11,17 @@ typedef unsigned int uint; enum { CodeBits = 16, /* max number of bits in a code */ - LitlenTableBits = 9, /* log2(litlen lookup table size) */ - DistTableBits = 6, /* log2(dist lookup table size) */ - ClenTableBits = 6, /* log2(clen lookup table size) */ - TableBits = LitlenTableBits, /* log2(max lookup table size) */ + LitlenTableBits = 9, /* litlen code bits used in lookup table */ + DistTableBits = 6, /* dist code bits used in lookup table */ + ClenTableBits = 6, /* clen code bits used in lookup table */ + TableBits = LitlenTableBits, /* log2(lookup table size) */ Nlit = 256, /* number of lit codes */ Nlen = 29, /* number of len codes */ Nlitlen = Nlit+Nlen+3, /* litlen codes + block end + 2 unused */ Ndist = 30, /* number of distance codes */ - Nclen = 19 /* number of code length codes */ + Nclen = 19, /* number of code length codes */ + SrcSize = 32768, /* input window size */ + DstSize = 32768 /* output window size */ }; enum { @@ -44,12 +46,19 @@ typedef struct { } Huff; typedef struct { - uchar *src; + int (*r)(void *, int, void *); + void *rdata; + uchar *srcbegin; uchar *srcend; + uchar *src; + uint srcleft; - uchar *dst; + int (*w)(void *, int, void *); + void *wdata; uchar *dstbegin; uchar *dstend; + uchar *dst; + uint dstleft; uint bits; uint nbits; @@ -196,15 +205,36 @@ static void init_fixed_huffs(void) { build_huff(&dhuff, lens, Ndist, 5); } +static int checksrc(Stream *s) { + if (s->src == s->srcend) { + s->src = s->srcbegin; + s->srcend = s->src + s->r(s->src, SrcSize, s->rdata); + if (s->src == s->srcend) { + s->error = FlateShortSrc; + return 0; + } + } + return 1; +} + +static int checkdst(Stream *s) { + if (s->dst == s->dstend) { + s->dst = s->dstbegin; + if (s->w(s->dst, s->dstend - s->dst, s->wdata) <= 0) { + s->error = FlateShortSrc; + return 0; + } + } + return 1; +} + /* get one bit from stream */ static uint getbit(Stream *s) { uint bit; if (!s->nbits--) { - if (s->src == s->srcend) { - s->error = FlateShortSrc; + if (!checksrc(s)) return 0; - } s->bits = *s->src++; s->nbits = 7; } @@ -223,10 +253,8 @@ static uint getbits(Stream *s, int n) { bits = s->bits; nbits = s->nbits; while (nbits < n) { - if (s->src == s->srcend) { - s->error = FlateShortSrc; + if (!checksrc(s)) return 0; - } bits |= (*s->src++ << nbits); nbits += 8; } @@ -235,7 +263,7 @@ static uint getbits(Stream *s, int n) { return bits & ((1 << n) - 1); } -/* decode a symbol from stream with tree */ +/* decode a symbol from stream with huff code */ static uint decode_symbol(Stream *s, Huff *huff) { int sum, cur; ushort *count; @@ -248,10 +276,8 @@ static uint decode_symbol(Stream *s, Huff *huff) { /* avail src should be checked outside */ while (streambits < huffbits) { /* TODO: decode_symbol is performace bottleneck, do it faster */ - if (s->src == s->srcend) { - s->error = FlateShortSrc; + if (!checksrc(s)) return 0; - } bits |= (*s->src++ << streambits); streambits += 8; } @@ -358,10 +384,8 @@ static void decode_block(Stream *s, Huff *lhuff, Huff *dhuff) { if (sym == 256) return; if (sym < 256) { - if (s->dst == s->dstend) { - s->error = FlateShortDst; + if (!checkdst(s)) return; - } *s->dst++ = sym; } else { int i, len, dist; @@ -384,6 +408,7 @@ static void decode_block(Stream *s, Huff *lhuff, Huff *dhuff) { return; /* copy match */ if (s->dst + len > s->dstend) { + /* TODO */ s->error = FlateShortDst; return; } @@ -445,7 +470,50 @@ static void inflate_dynamic_block(Stream *s) { /* extern */ -/* inflate stream from src to dst */ +/* inflate with callbacks */ +int inflate_f(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, void *), void *wdata) { + Stream s; + uint final; + + s.r = r; + s.rdata = rdata; + s.w = w; + s.wdata = wdata; + s.srcbegin = s.srcend = s.src = malloc(SrcSize); + s.dst = s.dstbegin = malloc(DstSize); + s.dstend = s.dst + DstSize; + s.error = FlateOk; + s.nbits = 0; + do { + uint blocktype; + + final = getbit(&s); + blocktype = getbits(&s, 2); + if (s.error != FlateOk) + return 0; + + /* decompress block */ + switch (blocktype) { + case 0: + inflate_uncompressed_block(&s); + break; + case 1: + inflate_fixed_block(&s); + break; + case 2: + inflate_dynamic_block(&s); + break; + default: + s.error = FlateCorrupted; + } + if (s.error != FlateOk) + return 0; + } while (!final); + /* TODO: errors, extra data at the end */ + return s.dst - s.dstbegin; +} + +/* uint inflate(void *dst, uint dstlen, void *src, uint srclen) { Stream s; uint final; @@ -464,7 +532,6 @@ uint inflate(void *dst, uint dstlen, void *src, uint srclen) { if (s.error != FlateOk) return 0; - /* decompress block */ switch (blocktype) { case 0: inflate_uncompressed_block(&s); @@ -483,15 +550,14 @@ uint inflate(void *dst, uint dstlen, void *src, uint srclen) { } while (!final); return s.dst - s.dstbegin; } - +*/ /* simple test */ #include <stdlib.h> #include <stdio.h> -void *readall(FILE *in) { - uint len = 1 << 22; +void *readall(FILE *in, uint len) { void *buf; buf = malloc(len); @@ -502,11 +568,12 @@ void *readall(FILE *in) { int main(int argc, char **argv) { uint len = 1 << 24; + uint srclen = 1 << 22; uchar *src, *dst; - src = readall(argc < 2 ? stdin : fopen(argv[1], "r")); + src = readall(argc < 2 ? stdin : fopen(argv[1], "r"), srclen); dst = malloc(len); - len = inflate(dst, len, src, len>>2); + len = inflate(dst, len, src, srclen); fprintf(stderr, "decompressed %u bytes\n", len); fwrite(dst, 1, len, stdout); free(dst);