commit 96787dc8ded9ff295326fe1695e1eccf144bf0d6
parent 00e3991660b4fd5eb4c19978c1fc3e017f59f544
Author: nsz <nszabolcs@gmail.com>
Date: Mon, 27 Apr 2009 20:05:06 +0200
optimized inflate (needs clean up)
Diffstat:
| README | | | 2 | ++ |
| inflate.c | | | 260 | +++++++++++++++++++++++++++++++++++++++++++++++++------------------------------ |
2 files changed, 163 insertions(+), 99 deletions(-)
diff --git a/README b/README
@@ -3,6 +3,8 @@ minimal deflate implementation
based on:
rfc1951 from ietf
tinf from ibsensoftware
+ zlib
+ gzip
puff from zlib
libflate from plan 9
halibut/deflate from putty
diff --git a/inflate.c b/inflate.c
@@ -15,6 +15,10 @@ typedef unsigned int uint;
enum {
HuffBits = 16, /* max number of bits in a code */
+ HuffLitlenBits = 9, /* log2(litlen huff table size) */
+ HuffDistBits = 6, /* log2(dist huff table size) */
+ HuffClenBits = 6, /* log2(clen huff table size) */
+ HuffTableBits = HuffLitlenBits, /* log2(max huff table size) */
Nlit = 256, /* number of lit codes */
Nlen = 29, /* number of len codes */
Nlitlen = Nlit+Nlen+3, /* litlen codes + block end + 2 unused */
@@ -29,17 +33,18 @@ enum {
FlateCorrupted = -4
};
-
typedef struct {
- uchar op;
- uchar bits;
- ushort val;
-} Code;
+ short len; /* complete: code len, incomplete: -(extra bits), err: 0 */
+ ushort sym; /* symbol if complete, decode helper if incomplete */
+} HuffEntry;
typedef struct {
+ HuffEntry table[1 << HuffTableBits]; /* for decoding the first nbits */
+ int nbits; /* table length is 1 << nbits */
+ int sum; /* sum(count[0..nbits-1]) */
ushort count[HuffBits]; /* code bit length -> count */
ushort symbol[Nlitlen]; /* symbols ordered by code length */
-} HuffTree;
+} HuffTable;
typedef struct {
uchar *src;
@@ -54,13 +59,13 @@ typedef struct {
int error;
- HuffTree ltree; /* dynamic lit/len tree */
- HuffTree dtree; /* dynamic distance tree */
+ HuffTable ltab; /* dynamic lit/len table */
+ HuffTable dtab; /* dynamic distance table */
} FlateStream;
-static HuffTree ltree; /* fixed lit/len tree */
-static HuffTree dtree; /* fixed distance tree */
+static HuffTable ltab; /* fixed lit/len table */
+static HuffTable dtab; /* fixed distance table */
/* base offset and extra bits tables */
static uchar lenbits[Nlen] = {
@@ -81,62 +86,118 @@ static uchar clenorder[Nclen] = {
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};
-static void init_fixed_trees(void) {
- int i;
+/* increment bitwise reversed n (msb is bit 0, lsb is bit len-1) */
+static uint revinc(uint n, int len) {
+ uint i;
- ltree.count[7] = 24;
- ltree.count[8] = 152;
- ltree.count[9] = 112;
- for (i = 0; i < 24; i++)
- ltree.symbol[i] = 256 + i;
- for (i = 0; i < 144; i++)
- ltree.symbol[24 + i] = i;
- for (i = 0; i < 8; i++)
- ltree.symbol[24 + 144 + i] = 280 + 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++)
- dtree.symbol[i] = i;
+ i = 1 << (len - 1);
+ while (n & i)
+ i >>= 1;
+ if (i) {
+ n &= i - 1;
+ n |= i;
+ } else
+ n = 0;
+ return n;
}
-/* build huffman code tree from code lengths */
-static int build_tree(HuffTree *t, const uchar *lens, int n) {
+/* build huffman code tree from code lengths (each should be < HuffBits) */
+static int build_table(HuffTable *h, uchar *lens, int n, int nbits) {
int offs[HuffBits];
- int i, sum, left;
-
- for (i = 0; i < HuffBits; i++)
- t->count[i] = 0;
+ int left;
+ uint i, c, sum, code, len, min, max;
+ ushort *count = h->count;
+ ushort *symbol = h->symbol;
+ HuffEntry *table = h->table;
+ HuffEntry entry;
/* count code lengths and calc first code for each length */
+ for (i = 0; i < HuffBits; i++)
+ count[i] = 0;
for (i = 0; i < n; i++)
- t->count[lens[i]]++;
- if (t->count[0] == n)
+ count[lens[i]]++;
+ if (count[0] == n)
return -1;
- t->count[0] = 0;
+ count[0] = 0;
+
+ /* bound code lengths, force root to be within code lengths */
+ for (max = HuffBits - 1; max > 0; max--)
+ if (count[max] != 0)
+ break;
+ if (nbits > max)
+ nbits = max;
+ for (min = 1; min < HuffBits; min++)
+ if (count[min] != 0)
+ break;
+ if (nbits < min)
+ nbits = min;
+ h->nbits = nbits;
/* check if length is over-subscribed or incomplete */
- for (left = i = 1; i < HuffBits; i++) {
- left <<= 1;
- left -= t->count[i];
+ for (left = 1 << min, i = min; i <= max; left <<= 1, i++) {
+ left -= count[i];
/* left < 0: over-subscribed, left > 0: incomplete */
if (left < 0)
return -1;
}
- for (sum = 0, i = 0; i < HuffBits; i++) {
+ for (sum = 0, i = 0; i <= max; i++) {
offs[i] = sum;
- sum += t->count[i];
+ sum += count[i];
}
+ /* needed for decoding codes longer than nbits */
+ if (nbits < max)
+ h->sum = offs[nbits + 1];
/* sort symbols by code length */
for (i = 0; i < n; i++)
if (lens[i])
- t->symbol[offs[lens[i]]++] = i;
+ symbol[offs[lens[i]]++] = i;
+
+ /* lookup table for decoding nbits from input.. */
+ for (i = 0; i < 1 << nbits; i++)
+ table[i].len = 0; /* invalid marker for incomplete code */
+ code = 0;
+ /* ..if code is at most nbits */
+ for (len = min; len <= nbits; len++)
+ for (c = count[len]; c > 0; c--) {
+ entry.len = len;
+ entry.sym = *symbol;
+ for (i = code; i < 1 << nbits; i += 1 << len)
+ table[i] = entry;
+ /* next code */
+ symbol++;
+ code = revinc(code, len);
+ }
+ /* ..if code is longer than nbits: nbits prefixes are marked */
+ for (i = 0; code; i++) {
+ table[code].len = -1; /* TODO +validation? */
+ table[code].sym = i;
+ code = revinc(code, nbits);
+ }
return 0;
}
+static void init_fixed_trees(void) {
+ int i;
+ uchar lens[Nlitlen];
+
+ for (i = 0; i < 144; i++)
+ lens[i] = 8;
+ for (; i < 256; i++)
+ lens[i] = 9;
+ for (; i < 280; i++)
+ lens[i] = 7;
+ for (; i < 288; i++) /* a complete, but wrong code set */
+ lens[i] = 8;
+ build_table(<ab, lens, Nlitlen, 8);
+
+
+ for (i = 0; i < Ndist; i++) /* an incomplete code set */
+ lens[i] = 5;
+ build_table(&dtab, lens, Ndist, 5);
+}
+
/* get one bit from s->src stream */
static uint getbit(FlateStream *s) {
uint bit;
@@ -167,45 +228,50 @@ static uint getbits(FlateStream *s, int n) {
}
/* decode a symbol from stream with tree */
-static uint decode_symbol(FlateStream *s, HuffTree *t) {
- int sum = 0, cur = 0;
- ushort *count = t->count + 1;
+static uint decode_symbol(FlateStream *s, HuffTable *h) {
+ int sum, cur;
+ ushort *count;
+ uint htbits = h->nbits;
uint nbits = s->nbits;
uint bits = s->bits;
- int n = HuffBits/8 + 1; /* process 3 bytes at most */
-
- while (n--) {
- /* slightly faster than getbit() in a loop */
- while (nbits--) {
- cur |= bits & 1;
- bits >>= 1;
- sum += *count;
- cur -= *count;
- if (cur < 0)
- goto found;
- cur <<= 1;
- count++;
- }
- if (s->src == s->srcend) {
- s->error = FlateShortSrc;
- return 0;
- }
- bits = *s->src++;
- nbits = 8;
- }
-found:
- if (count >= t->count + HuffBits) {
- s->error = FlateCorrupted;
- return 0;
+ uint mask = (1 << htbits) - 1;
+ HuffEntry entry;
+
+ /* TODO: check src */
+ while (nbits < htbits) {
+ bits |= (*s->src++ << nbits);
+ nbits += 8;
}
+ entry = h->table[bits & mask];
+ if (entry.len > 0) {
+ s->bits = bits >> entry.len;
+ s->nbits = nbits - entry.len;
+ return entry.sym;
+ } else if (entry.len == 0)
+ /* error */;
+
+ bits >>= htbits;
+ nbits -= htbits;
s->bits = bits;
s->nbits = nbits;
- return t->symbol[sum + cur];
+ cur = entry.sym << 1; /* TODO: do it in build_tab */
+ sum = h->sum;
+ count = h->count + htbits + 1;
+ for (;;) {
+ cur |= getbit(s);
+ sum += *count;
+ cur -= *count;
+ if (cur < 0)
+ break;
+ cur <<= 1;
+ count++;
+ }
+ return h->symbol[sum + cur];
}
/* decode dynamic trees from stream */
-static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
- HuffTree ctree;
+static void decode_tables(FlateStream *s, HuffTable *lt, HuffTable *dt) {
+ HuffTable cltab;
uchar lens[Nlitlen+Ndist];
uint nlit, ndist, nclen;
uint i;
@@ -225,17 +291,18 @@ static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
lens[i] = 0;
for (i = 0; i < nclen; i++)
lens[clenorder[i]] = getbits(s, 3);
- if (build_tree(&ctree, lens, Nclen) < 0) {
+ if (build_table(&cltab, lens, Nclen, HuffClenBits) < 0) {
s->error = FlateCorrupted;
return;
}
/* decode code lengths for the dynamic trees */
for (i = 0; i < nlit + ndist; ) {
- uint sym = decode_symbol(s, &ctree);
+ uint sym = decode_symbol(s, &cltab);
uint len;
uchar c;
+/* fprintf(stderr, "sym: %u, nbits: %u, bits: x%03x, src: %u\n", sym, s->nbits, s->bits, (unsigned)s->src);*/
if (sym < 16) {
lens[i++] = sym;
} else if (sym == 16) {
@@ -257,14 +324,14 @@ static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
return;
}
/* build dynamic huffman trees */
- if (build_tree(lt, lens, nlit) < 0)
+ if (build_table(lt, lens, nlit, HuffLitlenBits) < 0)
s->error = FlateCorrupted;
- if (build_tree(dt, lens + nlit, ndist) < 0)
+ if (build_table(dt, lens + nlit, ndist, HuffDistBits) < 0)
s->error = FlateCorrupted;
}
/* decode a block of data from stream with trees */
-static void decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
+static void decode_block(FlateStream *s, HuffTable *lt, HuffTable *dt) {
uint sym;
for (;;) {
@@ -342,14 +409,14 @@ static void inflate_uncompressed_block(FlateStream *s) {
}
static void inflate_fixed_block(FlateStream *s) {
- decode_block(s, <ree, &dtree);
+ decode_block(s, <ab, &dtab);
}
static void inflate_dynamic_block(FlateStream *s) {
- decode_trees(s, &s->ltree, &s->dtree);
+ decode_tables(s, &s->ltab, &s->dtab);
if (s->error != FlateOk)
return;
- decode_block(s, &s->ltree, &s->dtree);
+ decode_block(s, &s->ltab, &s->dtab);
}
@@ -400,38 +467,33 @@ uint inflate(void *dst, uint dstlen, void *src, uint srclen) {
}
+/* simple test */
+
#include <stdlib.h>
#include <stdio.h>
-void *readall(char *name, uint *len) {
- uint size = 1 << 22;
+void *readall(FILE *in) {
+ uint len = 1 << 22;
void *buf;
- FILE *in;
- in = fopen(name, "r");
- if (in == NULL)
- return NULL;
- buf = malloc(size);
- *len = fread(buf, 1, size, in);
+ buf = malloc(len);
+ fread(buf, 1, len, in);
fclose(in);
return buf;
}
int main(int argc, char **argv) {
+ uint len = 1 << 24;
uchar *src, *dst;
- uint srclen, dstlen=1<<22;
- if (argc < 2)
- return -1;
- src = readall(argv[1], &srclen);
inflate_init();
- dstlen = inflate(dst = malloc(dstlen), dstlen, src, srclen);
- if (dstlen == 0)
- fputs("inflate: error\n", stderr);
- else
- fprintf(stderr, "inflate: uncompressed %u bytes\n", dstlen);
- fwrite(dst, 1, dstlen, stdout);
+ src = readall(argc < 2 ? stdin : fopen(argv[1], "r"));
+ dst = malloc(len);
+ len = inflate(dst, len, src, len>>2);
+ fprintf(stderr, "decompressed %u bytes\n", len);
+ fwrite(dst, 1, len, stdout);
free(dst);
free(src);
return 0;
}
+
