commit 119a173e850bddf927f16b6363c52b17c7ebba54
parent afad3e61ac3e644dbe7e21ce0b60c8c9c6d8aaa1
Author: nsz <nszabolcs@gmail.com>
Date: Wed, 13 May 2009 01:13:00 +0200
inflate_simple consistent identifiers (with inflate)
Diffstat:
3 files changed, 61 insertions(+), 64 deletions(-)
diff --git a/Makefile b/Makefile
@@ -16,7 +16,7 @@ clean:
rm -f ${OBJ} inflate
-gcov: inflate.c
+prof: inflate.c
gcc -fprofile-arcs -ftest-coverage -pg -g -Wall $<
cat d.dat | ./a.out > /dev/null
gcov -b $< > /dev/null
diff --git a/README b/README
@@ -3,10 +3,10 @@ minimal deflate implementation
based on:
rfc1951 from ietf
tinf from ibsensoftware
+ libflate from plan 9
zlib
- gzip
puff from zlib
- libflate from plan 9
+ gzip
halibut/deflate from putty
build:
diff --git a/inflate_simple.c b/inflate_simple.c
@@ -5,7 +5,7 @@ typedef unsigned short ushort;
typedef unsigned int uint;
enum {
- HuffBits = 16, /* max number of bits in a code */
+ CodeBits = 16, /* max number of bits in a code + 1 */
Nlit = 256, /* number of lit codes */
Nlen = 29, /* number of len codes */
Nlitlen = Nlit + Nlen + 3, /* litlen codes + block end + 2 unused */
@@ -14,9 +14,9 @@ enum {
};
typedef struct {
- ushort count[HuffBits]; /* code length -> count */
+ ushort count[CodeBits]; /* code length -> count */
ushort symbol[Nlitlen]; /* symbols ordered by code length */
-} HuffTree;
+} Huff;
typedef struct {
uchar *src;
@@ -25,13 +25,13 @@ typedef struct {
uint bits;
uint nbits;
- HuffTree ltree; /* dynamic lit/len tree */
- HuffTree dtree; /* dynamic distance tree */
-} FlateStream;
+ Huff lhuff; /* dynamic lit/len huffman code tree */
+ Huff dhuff; /* dynamic distance huffman code tree */
+} Stream;
-static HuffTree ltree; /* fixed lit/len tree */
-static HuffTree dtree; /* fixed distance tree */
+static Huff lhuff; /* fixed lit/len huffman code tree */
+static Huff dhuff; /* fixed distance huffman code tree */
/* base offset tables */
static ushort lenbase[Nlen];
@@ -69,48 +69,48 @@ static void init_base_tables(void) {
}
}
-static void init_fixed_trees(void) {
+static void init_fixed_huffs(void) {
int i;
- ltree.count[7] = 24;
- ltree.count[8] = 152;
- ltree.count[9] = 112;
+ lhuff.count[7] = 24;
+ lhuff.count[8] = 152;
+ lhuff.count[9] = 112;
for (i = 0; i < 24; i++)
- ltree.symbol[i] = 256 + i;
+ lhuff.symbol[i] = 256 + i;
for (i = 0; i < 144; i++)
- ltree.symbol[24 + i] = i;
+ lhuff.symbol[24 + i] = i;
for (i = 0; i < 8; i++)
- ltree.symbol[24 + 144 + i] = 280 + i;
+ lhuff.symbol[24 + 144 + i] = 280 + i;
for (i = 0; i < 112; i++)
- ltree.symbol[24 + 144 + 8 + i] = 144 + i;
- dtree.count[5] = Ndist;
+ lhuff.symbol[24 + 144 + 8 + i] = 144 + i;
+ dhuff.count[5] = Ndist;
for (i = 0; i < Ndist; i++)
- dtree.symbol[i] = i;
+ dhuff.symbol[i] = i;
}
/* build huffman code tree from code lengths */
-static void build_tree(HuffTree *t, const uchar *lens, int n) {
- int offs[HuffBits];
+static void build_huff(Huff *h, const uchar *lens, int n) {
+ int offs[CodeBits];
int i, sum;
/* count code lengths and calc first code (offs) for each length */
- for (i = 0; i < HuffBits; i++)
- t->count[i] = 0;
+ for (i = 0; i < CodeBits; i++)
+ h->count[i] = 0;
for (i = 0; i < n; i++)
- t->count[lens[i]]++;
- t->count[0] = 0;
- for (sum = 0, i = 0; i < HuffBits; i++) {
+ h->count[lens[i]]++;
+ h->count[0] = 0;
+ for (sum = 0, i = 0; i < CodeBits; i++) {
offs[i] = sum;
- sum += t->count[i];
+ sum += h->count[i];
}
/* sort symbols by code length */
for (i = 0; i < n; i++)
if (lens[i])
- t->symbol[offs[lens[i]]++] = i;
+ h->symbol[offs[lens[i]]++] = i;
}
/* get one bit from stream */
-static uint getbit(FlateStream *s) {
+static uint getbit(Stream *s) {
uint bit;
if (!s->nbits--) {
@@ -123,7 +123,7 @@ static uint getbit(FlateStream *s) {
}
/* get n bits from stream */
-static uint getbits(FlateStream *s, int n) {
+static uint getbits(Stream *s, int n) {
uint bits = 0;
int i;
@@ -132,10 +132,10 @@ static uint getbits(FlateStream *s, int n) {
return bits;
}
-/* decode a symbol from stream with tree */
-static uint decode_symbol(FlateStream *s, HuffTree *t) {
+/* decode a symbol from stream with huffman code tree */
+static uint decode_symbol(Stream *s, Huff *h) {
int sum = 0, cur = 0;
- ushort *count = t->count + 1;
+ ushort *count = h->count + 1;
for (;;) {
cur |= getbit(s);
@@ -146,12 +146,12 @@ static uint decode_symbol(FlateStream *s, HuffTree *t) {
cur <<= 1;
count++;
}
- return t->symbol[sum + cur];
+ return h->symbol[sum + cur];
}
-/* decode dynamic trees from stream */
-static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
- HuffTree ctree;
+/* decode dynamic huffs from stream */
+static void decode_huffs(Stream *s) {
+ Huff chuff;
uchar lens[Nlitlen+Ndist];
uint nlit, ndist, nclen;
uint i;
@@ -159,15 +159,15 @@ 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);
- /* build code length tree */
+ /* build code length huff */
for (i = 0; i < Nclen; i++)
lens[i] = 0;
for (i = 0; i < nclen; i++)
lens[clenorder[i]] = getbits(s, 3);
- build_tree(&ctree, lens, Nclen);
- /* decode code lengths for the dynamic trees */
+ build_huff(&chuff, lens, Nclen);
+ /* decode code lengths for the dynamic huffs */
for (i = 0; i < nlit + ndist; ) {
- uint sym = decode_symbol(s, &ctree);
+ uint sym = decode_symbol(s, &chuff);
uint len;
uchar c;
@@ -188,17 +188,17 @@ static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
lens[i++] = 0;
}
}
- /* build dynamic huffman trees */
- build_tree(lt, lens, nlit);
- build_tree(dt, lens + nlit, ndist);
+ /* build dynamic huffman huffs */
+ build_huff(&s->lhuff, lens, nlit);
+ build_huff(&s->dhuff, lens + nlit, ndist);
}
-/* decode a block of data from stream with trees */
-static void decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
+/* decode a block of data from stream with huffman code trees */
+static void decode_block(Stream *s, Huff *lhuff, Huff *dhuff) {
uint sym;
for (;;) {
- sym = decode_symbol(s, lt);
+ sym = decode_symbol(s, lhuff);
if (sym == 256)
return;
if (sym < 256)
@@ -208,7 +208,7 @@ static void decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
sym -= 257;
len = lenbase[sym] + getbits(s, lenbits[sym]);
- sym = decode_symbol(s, dt);
+ sym = decode_symbol(s, dhuff);
dist = distbase[sym] + getbits(s, distbits[sym]);
/* copy match */
while (len--) {
@@ -219,7 +219,7 @@ static void decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
}
}
-static void inflate_uncompressed_block(FlateStream *s) {
+static void inflate_uncompressed_block(Stream *s) {
uint len;
s->nbits = 0; /* start block on a byte boundary */
@@ -229,29 +229,27 @@ static void inflate_uncompressed_block(FlateStream *s) {
*s->dst++ = *s->src++;
}
-static void inflate_fixed_block(FlateStream *s) {
- decode_block(s, <ree, &dtree);
+static void inflate_fixed_block(Stream *s) {
+ decode_block(s, &lhuff, &dhuff);
}
-static void inflate_dynamic_block(FlateStream *s) {
- decode_trees(s, &s->ltree, &s->dtree);
- decode_block(s, &s->ltree, &s->dtree);
+static void inflate_dynamic_block(Stream *s) {
+ decode_huffs(s);
+ decode_block(s, &s->lhuff, &s->dhuff);
}
/* extern */
-/* initialize global (static) data */
-void inflate_init(void) {
- init_base_tables();
- init_fixed_trees();
-}
-
/* inflate stream from src to dst, return end pointer */
void *inflate(void *dst, void *src) {
- FlateStream s;
+ Stream s;
uint final;
+ /* initialize global (static) data */
+ init_base_tables();
+ init_fixed_huffs();
+
s.src = src;
s.dst = dst;
s.nbits = 0;
@@ -292,7 +290,6 @@ int main(int argc, char **argv) {
uint len = 1 << 24;
uchar *src, *dst;
- inflate_init();
src = readall(argc < 2 ? stdin : fopen(argv[1], "r"));
dst = malloc(len);
len = (uchar *)inflate(dst, src) - dst;
