commit e9286640f1ed98bba3751c05fc7d9ab6728b7919
parent e46afd79679b931cf1912ce2c98aa5293a3f006a
Author: nsz <nszabolcs@gmail.com>
Date: Wed, 6 May 2009 07:45:03 +0200
inflate with callback
Diffstat:
| Makefile | | | 4 | ++-- |
| inflate.c | | | 225 | +++++++++++++++++++++++++++++++++++++++---------------------------------------- |
2 files changed, 114 insertions(+), 115 deletions(-)
diff --git a/Makefile b/Makefile
@@ -18,11 +18,11 @@ clean:
gcov: inflate.c
gcc -fprofile-arcs -ftest-coverage -pg -g -Wall $<
- ./a.out d.dat > /dev/null
+ cat d.dat | ./a.out > /dev/null
gcov -b $< > /dev/null
gprof a.out > $<.gprof
gcc -g -Wall $<
- valgrind -v --leak-check=yes ./a.out d.dat > /dev/null 2> a.valgrind
+ cat d.dat | valgrind -v --leak-check=yes ./a.out > /dev/null 2> a.valgrind
grep ERROR a.valgrind
grep alloc a.valgrind
rm a.out a.valgrind *.gcno *.gcda gmon.out
diff --git a/inflate.c b/inflate.c
@@ -5,6 +5,9 @@ TODO:
better error handling
*/
+#include <stdlib.h>
+#include <string.h>
+
typedef unsigned char uchar;
typedef unsigned short ushort;
typedef unsigned int uint;
@@ -20,14 +23,14 @@ enum {
Nlitlen = Nlit+Nlen+3, /* litlen codes + block end + 2 unused */
Ndist = 30, /* number of distance codes */
Nclen = 19, /* number of code length codes */
- SrcSize = 32768, /* input window size */
- DstSize = 32768 /* output window size */
+ SrcSize = 1 << 16, /* input buffer size */
+ WinSize = 1 << 16 /* output window size */
};
enum {
FlateOk = 0,
- FlateShortSrc = -1,
- FlateShortDst = -2,
+ FlateInError = -1,
+ FlateOutError = -2,
FlateCorrupted = -3
};
@@ -51,18 +54,16 @@ typedef struct {
uchar *srcbegin;
uchar *srcend;
uchar *src;
- uint srcleft;
-
- int (*w)(void *, int, void *);
- void *wdata;
- uchar *dstbegin;
- uchar *dstend;
- uchar *dst;
- uint dstleft;
uint bits;
uint nbits;
+ int (*w)(void *, int, void *);
+ void *wdata;
+ uchar *win; /* output window, size: 2^16 */
+ ushort pos; /* 16bit: overflows after 2^16 */
+ ushort flushed; /* is win flushed */
+
int error;
Huff lhuff; /* dynamic lit/len huffman code tree */
@@ -205,29 +206,43 @@ static void init_fixed_huffs(void) {
build_huff(&dhuff, lens, Ndist, 5);
}
+/* check src before accessing it */
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;
+ if (s->src >= s->srcend) {
+ s->error = FlateInError;
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;
+/* check window position before writing to it */
+static int checkpos(Stream *s) {
+ if (s->pos == 0) {
+ if (s->flushed)
+ s->flushed = 0;
+ else if (s->w(s->win, WinSize, s->wdata) != WinSize) {
+ s->error = FlateOutError;
return 0;
}
}
return 1;
}
+/* flush output window */
+static void flush_win(Stream *s) {
+ if (s->pos) {
+ if (s->w(s->win, s->pos, s->wdata) != s->pos)
+ s->error = FlateOutError;
+ } else if (!s->flushed)
+ if (s->w(s->win, WinSize, s->wdata) != WinSize)
+ s->error = FlateOutError;
+ s->flushed = 1;
+}
+
/* get one bit from stream */
static uint getbit(Stream *s) {
uint bit;
@@ -384,11 +399,11 @@ static void decode_block(Stream *s, Huff *lhuff, Huff *dhuff) {
if (sym == 256)
return;
if (sym < 256) {
- if (!checkdst(s))
+ if (!checkpos(s))
return;
- *s->dst++ = sym;
+ s->win[s->pos++] = sym;
} else {
- int i, len, dist;
+ uint i, len, dist;
sym -= 257;
if (sym >= Nlen) {
@@ -407,50 +422,60 @@ static void decode_block(Stream *s, Huff *lhuff, Huff *dhuff) {
if (s->error != FlateOk)
return;
/* copy match */
- if (s->dst + len > s->dstend) {
- /* TODO */
- s->error = FlateShortDst;
- return;
- }
- if (s->dst - dist < s->dstbegin) {
- s->error = FlateCorrupted;
- return;
- }
/* TODO: unroll 3-4 loops */
- for (i = 0; i < len; i++)
- s->dst[i] = s->dst[i - dist];
- s->dst += len;
+ for (i = 0; i < len; i++) {
+ if (!checkpos(s))
+ return;
+ s->win[s->pos] = s->win[(ushort)(s->pos - dist)];
+ s->pos++;
+ }
}
}
}
+/* TODO: untested, ugly code */
static void inflate_uncompressed_block(Stream *s) {
uint len, invlen;
/* start next block on a byte boundary */
- while (s->nbits > 8) {
- s->nbits -= 8;
- s->src--;
- }
- s->nbits = 0;
- len = (s->src[1] << 8) | s->src[0];
- invlen = (s->src[3] << 8) | s->src[2];
- s->src += 4;
+ s->bits >>= s->nbits & 7;
+ s->nbits &= ~7;
+
+ len = getbits(s, 8);
+ len |= getbits(s, 8) << 8;
+ invlen = getbits(s, 8);
+ invlen |= getbits(s, 8) << 8;
+ /* s->nbits should be 0 here */
+ if (s->error != FlateOk)
+ return;
if (len != (~invlen & 0xffff)) {
s->error = FlateCorrupted;
return;
}
- if (s->dst + len > s->dstend) {
- s->error = FlateShortDst;
- return;
- }
- if (s->src + len > s->srcend) {
- s->error = FlateShortSrc;
+ flush_win(s);
+ if (s->error != FlateOk)
return;
+ /* copy from src or read len data to win */
+ /* TODO: bad (referencing back before unc block should work) */
+ s->pos = 0;
+ s->flushed = len == 0;
+ if (s->src + len < s->srcend) {
+ memcpy(s->win, s->src, len);
+ s->pos = len;
+ s->src += len;
+ } else {
+ s->pos = s->srcend - s->src;
+ memcpy(s->win, s->src, s->pos);
+ s->src = s->srcend = s->srcbegin;
+ len -= s->pos;
+ if (len) {
+ if (s->r(s->win + s->pos, len, s->rdata) < len) {
+ s->error = FlateInError;
+ return;
+ }
+ s->pos += len;
+ }
}
- /* TODO: memcpy */
- while (len--)
- *s->dst++ = *s->src++;
}
static void inflate_fixed_block(Stream *s) {
@@ -471,7 +496,7 @@ static void inflate_dynamic_block(Stream *s) {
/* extern */
/* inflate with callbacks */
-int inflate_f(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, void *), void *wdata) {
+int inflate(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, void *), void *wdata) {
Stream s;
uint final;
@@ -480,8 +505,9 @@ int inflate_f(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int,
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.win = malloc(WinSize);
+ s.flushed = 1;
+ s.pos = 0;
s.error = FlateOk;
s.nbits = 0;
do {
@@ -507,77 +533,50 @@ int inflate_f(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int,
s.error = FlateCorrupted;
}
if (s.error != FlateOk)
- return 0;
+ break;
} while (!final);
+ flush_win(&s);
/* TODO: errors, extra data at the end */
- return s.dst - s.dstbegin;
+ return s.error;
}
-/*
-uint inflate(void *dst, uint dstlen, void *src, uint srclen) {
- Stream s;
- uint final;
- s.src = src;
- s.srcend = s.src + srclen;
- s.dstbegin = s.dst = dst;
- s.dstend = s.dst + dstlen;
- s.error = FlateOk;
- s.nbits = 0;
- do {
- uint blocktype;
+/* simple test */
- final = getbit(&s);
- blocktype = getbits(&s, 2);
- if (s.error != FlateOk)
- return 0;
+#include <stdio.h>
- 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);
- return s.dst - s.dstbegin;
-}
-*/
+struct data {
+ FILE *f;
+ uint n;
+};
-/* simple test */
+int r(void *p, int siz, void *data) {
+ uint n;
+ struct data *d = data;
-#include <stdlib.h>
-#include <stdio.h>
+ n = fread(p, 1, siz, d->f);
+ d->n += n;
+ return n;
+}
-void *readall(FILE *in, uint len) {
- void *buf;
+int w(void *p, int siz, void *data) {
+ uint n;
+ struct data *d = data;
- buf = malloc(len);
- fread(buf, 1, len, in);
- fclose(in);
- return buf;
+ n = fwrite(p, 1, siz, d->f);
+ d->n += n;
+ return n;
}
-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"), srclen);
- dst = malloc(len);
- len = inflate(dst, len, src, srclen);
- fprintf(stderr, "decompressed %u bytes\n", len);
- fwrite(dst, 1, len, stdout);
- free(dst);
- free(src);
+int main() {
+ struct data in, out;
+ int err;
+
+ in.f = stdin;
+ in.n = 0;
+ out.f = stdout;
+ out.n = 0;
+ err = inflate(r, &in, w, &out);
+ fprintf(stderr, "error: %d, decompressed %u bytes\n", err, out.n);
return 0;
}
-
