flate

commit 54ebdaf31afea94fab7aad2224526e8a2d6cca05
parent e9286640f1ed98bba3751c05fc7d9ab6728b7919
Author: nsz <nszabolcs@gmail.com>
Date:   Mon, 11 May 2009 12:27:40 +0200

io fixes
Diffstat:
Makefile
 | 
2
+-
inflate.c
 | 
77
+++++++++++++++++++++++++----------------------------------------------------
inflate_simple.c
 | 
2
+-

3 files changed, 27 insertions(+), 54 deletions(-)
diff --git a/Makefile b/Makefile
@@ -18,7 +18,7 @@ clean:
 
 gcov: inflate.c
 	gcc -fprofile-arcs -ftest-coverage -pg -g -Wall $<
-	cat d.dat | ./a.out > /dev/null
+	cat b.dat | ./a.out > /dev/null
 	gcov -b $< > /dev/null
 	gprof a.out > $<.gprof
 	gcc -g -Wall $<
diff --git a/inflate.c b/inflate.c
@@ -23,8 +23,8 @@ 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         = 1 << 16, /* input buffer size */
-	WinSize         = 1 << 16 /* output window size */
+	SrcSize         = 1 << 12, /* input buffer size */
+	WinSize         = 1 << 15 /* output window size */
 };
 
 enum {
@@ -53,16 +53,15 @@ typedef struct {
 	void *rdata;
 	uchar *srcbegin;
 	uchar *srcend;
-	uchar *src;
+	uchar *src; /* input buffer pointer */
 
 	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 */
+	uchar *win; /* output window */
+	uint pos;   /* window pos */
 
 	int error;
 
@@ -96,9 +95,8 @@ static uchar clenorder[Nclen] = {
 /* TODO: this or normal inc + reverse() */
 /* increment bitwise reversed n (msb is bit 0, lsb is bit len-1) */
 static uint revinc(uint n, uint len) {
-	uint i;
+	uint i = 1 << (len - 1);
 
-	i = 1 << (len - 1);
 	while (n & i)
 		i >>= 1;
 	if (i) {
@@ -209,8 +207,8 @@ static void init_fixed_huffs(void) {
 /* 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);
+		s->src = s->srcend = s->srcbegin;
+		s->srcend += s->r(s->src, SrcSize, s->rdata);
 		if (s->src >= s->srcend) {
 			s->error = FlateInError;
 			return 0;
@@ -221,26 +219,21 @@ static int checksrc(Stream *s) {
 
 /* 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) {
+	if (s->pos == WinSize) {
+		if (s->w(s->win, WinSize, s->wdata) != WinSize) {
 			s->error = FlateOutError;
 			return 0;
 		}
+		s->pos = 0;
 	}
 	return 1;
 }
 
 /* flush output window */
 static void flush_win(Stream *s) {
-	if (s->pos) {
+	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 */
@@ -399,9 +392,9 @@ static void decode_block(Stream *s, Huff *lhuff, Huff *dhuff) {
 		if (sym == 256)
 			return;
 		if (sym < 256) {
+			s->win[s->pos++] = sym;
 			if (!checkpos(s))
 				return;
-			s->win[s->pos++] = sym;
 		} else {
 			uint i, len, dist;
 
@@ -424,16 +417,16 @@ static void decode_block(Stream *s, Huff *lhuff, Huff *dhuff) {
 			/* copy match */
 			/* TODO: unroll 3-4 loops */
 			for (i = 0; i < len; i++) {
+				s->win[s->pos] = s->win[(s->pos - dist) & 0x7ff];
+				s->pos++;
 				if (!checkpos(s))
 					return;
-				s->win[s->pos] = s->win[(ushort)(s->pos - dist)];
-				s->pos++;
 			}
 		}
 	}
 }
 
-/* TODO: untested, ugly code */
+/* TODO: untested, slow code */
 static void inflate_uncompressed_block(Stream *s) {
 	uint len, invlen;
 
@@ -441,10 +434,8 @@ static void inflate_uncompressed_block(Stream *s) {
 	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;
+	len = getbits(s, 16);
+	invlen = getbits(s, 16);
 	/* s->nbits should be 0 here */
 	if (s->error != FlateOk)
 		return;
@@ -452,29 +443,9 @@ static void inflate_uncompressed_block(Stream *s) {
 		s->error = FlateCorrupted;
 		return;
 	}
-	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;
-		}
+	while (len--) {
+		s->win[s->pos++] = getbits(s, 8);
+		checkpos(s);
 	}
 }
 
@@ -506,7 +477,6 @@ int inflate(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, vo
 	s.wdata = wdata;
 	s.srcbegin = s.srcend = s.src = malloc(SrcSize);
 	s.win = malloc(WinSize);
-	s.flushed = 1;
 	s.pos = 0;
 	s.error = FlateOk;
 	s.nbits = 0;
@@ -536,7 +506,8 @@ int inflate(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, vo
 			break;
 	} while (!final);
 	flush_win(&s);
-	/* TODO: errors, extra data at the end */
+	free(s.win);
+	free(s.srcbegin);
 	return s.error;
 }
 
@@ -555,6 +526,7 @@ int r(void *p, int siz, void *data) {
 	struct data *d = data;
 
 	n = fread(p, 1, siz, d->f);
+/*fprintf(stderr, "r: %u\n", n);*/
 	d->n += n;
 	return n;
 }
@@ -564,6 +536,7 @@ int w(void *p, int siz, void *data) {
 	struct data *d = data;
 
 	n = fwrite(p, 1, siz, d->f);
+/*fprintf(stderr, "w: %u\n", n);*/
 	d->n += n;
 	return n;
 }
diff --git a/inflate_simple.c b/inflate_simple.c
@@ -204,7 +204,7 @@ static void decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
 		if (sym < 256)
 			*s->dst++ = sym;
 		else {
-			int len, dist;
+			uint len, dist;
 
 			sym -= 257;
 			len = lenbase[sym] + getbits(s, lenbits[sym]);