commit 1b3aea40ec37c7d9fcce28ebe271ecd895200702
parent a832945746253cae75977ce7daa5a14ad34a3885
Author: nsz <nszabolcs@gmail.com>
Date: Mon, 20 Apr 2009 20:35:17 +0200
cleanups, gcov
Diffstat:
| Makefile | | | 13 | +++++++++++++ |
| README | | | 1 | + |
| inflate.c | | | 87 | ++++++++++++++++++++++++++++++++++--------------------------------------------- |
3 files changed, 51 insertions(+), 50 deletions(-)
diff --git a/Makefile b/Makefile
@@ -12,3 +12,16 @@ ${OBJ}: Makefile
${CC} -c ${CFLAGS} $<
clean:
rm -f ${OBJ} inflate
+
+
+gcov: inflate.c
+ gcc -fprofile-arcs -ftest-coverage -pg ${CFLAGS} $<
+ ./a.out test.dat > /dev/null
+ gcov -b $< > /dev/null
+ gprof a.out > $<.gprof
+ gcc ${CFLAGS} $<
+ valgrind -v --leak-check=yes ./a.out > /dev/null 2> a.valgrind
+ grep ERROR a.valgrind >a.err.valgrind
+ grep alloc a.valgrind >a.alloc.valgrind
+ rm a.out *.gcno *.gcda gmon.out
+
diff --git a/README b/README
@@ -5,6 +5,7 @@ source:
tinf from ibsensoftware
puff from zlib
libflate from plan 9
+ halibut/deflate from putty
build:
make
diff --git a/inflate.c b/inflate.c
@@ -1,10 +1,12 @@
/*
TODO:
- error check (src len, dst len)
- fillbits(s, n) -> faster getbits()
+ error check (src len, dst len, hufftree)
clever io
p9 hufftable
int types
+ speedup:
+ fillbits(s, n) -> faster getbits()
+ loop unroll in decode_symbol
*/
typedef unsigned char uchar;
@@ -13,21 +15,17 @@ typedef unsigned int uint;
typedef unsigned long ulong;
enum {
- HuffBits = 16, /* maximum bits in a encoded code */
+ HuffBits = 16, /* max number of bits in a code */
Nlit = 256, /* number of lit codes */
Nlen = 29, /* number of len codes */
Nlitlen = Nlit + Nlen + 3, /* number of litlen codes + block end + 2 unused */
- Ndist = 30, /* number of offset codes */
- Nclen = 19, /* number of codelen codes */
- LenShift = 10 /* code = len<<LenShift|code */
-/* LitlenBits = 7,*/ /* number of bits in litlen decode table */
-/* DistBits = 6,*/ /* number of bits in offset decode table */
-/* ClenBits = 6*/ /* number of bits in code len decode table */
+ Ndist = 30, /* number of distance codes */
+ Nclen = 19, /* number of code length codes */
};
typedef struct {
- ushort count[HuffBits]; /* code bit len -> count */
- ushort symbol[Nlitlen]; /* litlen code -> symbol */
+ ushort count[HuffBits]; /* code bit length -> count */
+ ushort symbol[Nlitlen]; /* symbols ordered by code length */
} HuffTree;
typedef struct {
@@ -46,7 +44,6 @@ typedef struct {
static HuffTree ltree; /* fixed lit/len tree */
static HuffTree dtree; /* fixed distance tree */
-/* extra bits and base tables for length codes */
static uchar lenbits[Nlen] = {
0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
@@ -55,7 +52,6 @@ static uchar lenbits[Nlen] = {
static ushort lenbase[Nlen];
-/* extra bits and base tables for distance codes */
static uchar distbits[Ndist] = {
0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
@@ -92,15 +88,15 @@ static void init_fixed_trees(void) {
ltree.count[9] = 112;
for (i = 0; i < 24; i++)
ltree.symbol[i] = 256 + i;
- for (i = 0; i < 144; ++i)
+ for (i = 0; i < 144; i++)
ltree.symbol[24 + i] = i;
- for (i = 0; i < 8; ++i)
+ for (i = 0; i < 8; i++)
ltree.symbol[24 + 144 + i] = 280 + i;
- for (i = 0; i < 112; ++i)
+ for (i = 0; i < 112; i++)
ltree.symbol[24 + 144 + 8 + i] = 144 + i;
dtree.count[5] = Ndist;
- for (i = 0; i < Ndist; ++i)
+ for (i = 0; i < Ndist; i++)
dtree.symbol[i] = i;
}
@@ -121,16 +117,12 @@ static void build_tree(HuffTree *t, const uchar *lens, uint n) {
sum += t->count[i];
}
- /* create code->symbol translation table (symbols sorted by code) */
+ /* sort symbols by code length */
for (i = 0; i < n; i++)
if (lens[i])
t->symbol[offs[lens[i]]++] = i;
}
-/*
- * decode functions
- */
-
/* get one bit from s->src stream */
static uint getbit(FlateStream *s) {
uint bit;
@@ -162,10 +154,12 @@ static uint decode_symbol(FlateStream *s, HuffTree *t) {
/* get bits while code value is above sum */
do {
- cur <<= 1;
- cur |= getbit(s);
len++;
+ if (len >= HuffBits)
+ /* error */;
sum += t->count[len];
+ cur <<= 1;
+ cur |= getbit(s);
cur -= t->count[len];
} while (cur >= 0);
@@ -182,7 +176,8 @@ static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
nlit = 257 + getbits(s, 5);
ndist = 1 + getbits(s, 5);
nclen = 4 + getbits(s, 4);
- /*if (nlit > Nlitlen || ndist > Ndist) */
+ if (nlit > Nlitlen || ndist > Ndist)
+ /* error */;
/* build code length tree */
for (i = 0; i < Nclen; i++)
@@ -212,9 +207,8 @@ static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
/* repeat 0 for 11-138 times */
for (len = 11 + getbits(s, 7); len; len--)
lens[i++] = 0;
- } else {
- /* error */
- }
+ } else
+ /* error */;
}
/* build dynamic trees */
@@ -237,8 +231,8 @@ static int decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
if (sym < 256)
*s->dst++ = sym;
else {
- int len, dist;
- int i;
+ uint len, dist;
+ uint i;
sym -= 257;
if (sym >= Nlen)
@@ -257,7 +251,6 @@ static int decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
}
}
-/* inflate an uncompressed block of data */
static int inflate_uncompressed_block(FlateStream *s) {
uint len, invlen;
@@ -277,20 +270,17 @@ static int inflate_uncompressed_block(FlateStream *s) {
return 0;
}
-/* inflate a block of data compressed with fixed huffman trees */
static int inflate_fixed_block(FlateStream *s) {
return decode_block(s, <ree, &dtree);
}
-/* inflate a block of data compressed with dynamic huffman trees */
static int inflate_dynamic_block(FlateStream *s) {
decode_trees(s, &s->ltree, &s->dtree);
return decode_block(s, &s->ltree, &s->dtree);
}
-/*
- * extern functions
- */
+
+/* extern functions */
/* initialize global (static) data */
void inflate_init(void) {
@@ -301,7 +291,7 @@ void inflate_init(void) {
/* inflate stream from src to dst */
int inflate(void *dst, uint *dstlen, const void *src, uint srclen) {
FlateStream s;
- uint bfinal;
+ uint final;
s.src = src;
s.nbits = 0;
@@ -309,17 +299,14 @@ int inflate(void *dst, uint *dstlen, const void *src, uint srclen) {
s.dstlen = dstlen;
*dstlen = 0;
do {
- uint btype;
+ uint blocktype;
int res;
- /* read final block flag */
- bfinal = getbit(&s);
-
- /* read block type */
- btype = getbits(&s, 2);
+ final = getbit(&s);
+ blocktype = getbits(&s, 2);
/* decompress block */
- switch (btype) {
+ switch (blocktype) {
case 0:
res = inflate_uncompressed_block(&s);
break;
@@ -334,7 +321,7 @@ int inflate(void *dst, uint *dstlen, const void *src, uint srclen) {
}
if (res != 0)
return -1;
- } while (!bfinal);
+ } while (!final);
return 0;
}
@@ -343,7 +330,7 @@ int inflate(void *dst, uint *dstlen, const void *src, uint srclen) {
#include <stdlib.h>
unsigned char *readall(char *name, uint *len) {
- ulong size = 1 << 20;
+ ulong size = 1 << 22;
uchar *buf;
FILE *in;
@@ -359,7 +346,7 @@ unsigned char *readall(char *name, uint *len) {
int main(int argc, char **argv) {
int ret;
uchar *src;
- uint srclen, dstlen=1<<16;
+ uint srclen, dstlen=1<<22;
uchar *dst;
if (argc < 2)
@@ -368,10 +355,10 @@ int main(int argc, char **argv) {
inflate_init();
ret = inflate(dst = malloc(dstlen), &dstlen, src, srclen);
if (ret)
- puts("inflate: error\n");
+ fputs("inflate: error\n", stderr);
else
- printf("inflate: uncompressed %u bytes\n", dstlen);
- puts((char *)dst);
+ fprintf(stderr, "inflate: uncompressed %u bytes\n", dstlen);
+ fwrite(dst, 1, dstlen, stdout);
free(dst);
free(src);
return ret;
