commit 29637fae613ae2ef326c64b4270ade27ea1ca61f
parent 66633eca00f4329f7cb3f4fc635e8afb9f66b989
Author: nsz <nszabolcs@gmail.com>
Date: Wed, 22 Apr 2009 13:00:07 +0200
inflate_simple
Diffstat:
| Makefile | | | 6 | ++++-- |
| inflate_simple.c | | | 322 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 326 insertions(+), 2 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,12 +1,14 @@
#CFLAGS=-g -Wall -ansi -pedantic
CFLAGS=-Os -Wall -ansi -pedantic
LDFLAGS=
-SRC=inflate.c
+SRC=inflate.c inflate_simple.c
OBJ=${SRC:.c=.o}
-all: inflate
+all: inflate inflate_simple
inflate: inflate.o
${CC} -o $@ $^ ${LDFLAGS}
+inflate_simple: inflate_simple.o
+ ${CC} -o $@ $^ ${LDFLAGS}
${OBJ}: Makefile
.c.o:
${CC} -c ${CFLAGS} $<
diff --git a/inflate_simple.c b/inflate_simple.c
@@ -0,0 +1,322 @@
+/* no input validation and bounds check */
+
+typedef unsigned char uchar;
+typedef unsigned short ushort;
+typedef unsigned int uint;
+
+enum {
+ 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, /* litlen codes + block end + 2 unused */
+ Ndist = 30, /* number of distance codes */
+ Nclen = 19 /* number of code length codes */
+};
+
+typedef struct {
+ ushort count[HuffBits]; /* code length -> count */
+ ushort symbol[Nlitlen]; /* symbols ordered by code length */
+} HuffTree;
+
+typedef struct {
+ uchar *src;
+
+ uchar *dst;
+ uchar *dstbegin;
+
+ uint bits;
+ uint nbits;
+
+ HuffTree ltree; /* dynamic lit/len tree */
+ HuffTree dtree; /* dynamic distance tree */
+} FlateStream;
+
+
+static HuffTree ltree; /* fixed lit/len tree */
+static HuffTree dtree; /* fixed distance tree */
+
+/* base offsets */
+static ushort lenbase[Nlen];
+static ushort distbase[Ndist];
+
+/* extra bits */
+static uchar lenbits[Nlen] = {
+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
+ 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
+ 4, 4, 4, 4, 5, 5, 5, 5, 0
+};
+static uchar distbits[Ndist] = {
+ 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
+ 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
+ 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
+};
+
+/* ordering of code lengths */
+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_base_tables(void) {
+ uint base;
+ int i;
+
+ for (base = 3, i = 0; i < Nlen; i++) {
+ lenbase[i] = base;
+ base += 1 << lenbits[i];
+ }
+ lenbase[Nlen-1]--; /* deflate bug */
+
+ for (base = 1, i = 0; i < Ndist; i++) {
+ distbase[i] = base;
+ base += 1 << distbits[i];
+ }
+}
+
+static void init_fixed_trees(void) {
+ int 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;
+}
+
+/* build huffman code tree from code lengths */
+static void build_tree(HuffTree *t, const uchar *lens, int n) {
+ int offs[HuffBits];
+ int i, sum;
+
+ for (i = 0; i < HuffBits; i++)
+ t->count[i] = 0;
+
+ /* count code lengths and calc first code for each length */
+ for (i = 0; i < n; i++)
+ t->count[lens[i]]++;
+ t->count[0] = 0;
+
+ for (sum = 0, i = 0; i < HuffBits; i++) {
+ offs[i] = sum;
+ sum += t->count[i];
+ }
+
+ /* sort symbols by code length */
+ for (i = 0; i < n; i++)
+ if (lens[i])
+ t->symbol[offs[lens[i]]++] = i;
+}
+
+/* get one bit from s->src stream */
+static uint getbit(FlateStream *s) {
+ uint bit;
+
+ if (!s->nbits--) {
+ s->bits = *s->src++;
+ s->nbits = 7;
+ }
+ bit = s->bits & 1;
+ s->bits >>= 1;
+ return bit;
+}
+
+/* get n bits from s->src stream */
+static uint getbits(FlateStream *s, int n) {
+ uint bits = 0;
+ int i;
+
+ for (i = 0; i < n; i++)
+ bits |= getbit(s) << i;
+ return bits;
+}
+
+/* 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;
+
+ for (;;) {
+ cur |= getbit(s);
+ sum += *count;
+ cur -= *count;
+ if (cur < 0)
+ break;
+ cur <<= 1;
+ count++;
+ }
+ return t->symbol[sum + cur];
+}
+
+/* decode dynamic trees from stream */
+static void decode_trees(FlateStream *s, HuffTree *lt, HuffTree *dt) {
+ HuffTree ctree;
+ uchar lens[Nlitlen+Ndist];
+ uint nlit, ndist, nclen;
+ uint i;
+
+ nlit = 257 + getbits(s, 5);
+ ndist = 1 + getbits(s, 5);
+ nclen = 4 + getbits(s, 4);
+
+ /* build code length tree */
+ 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 */
+ for (i = 0; i < nlit + ndist; ) {
+ uint sym = decode_symbol(s, &ctree);
+ uint len;
+ uchar c;
+
+ if (sym < 16) {
+ lens[i++] = sym;
+ } else if (sym == 16) {
+ /* copy previous code length 3-6 times */
+ c = lens[i - 1];
+ for (len = 3 + getbits(s, 2); len; len--)
+ lens[i++] = c;
+ } else if (sym == 17) {
+ /* repeat 0 for 3-10 times */
+ for (len = 3 + getbits(s, 3); len; len--)
+ lens[i++] = 0;
+ } else if (sym == 18) {
+ /* repeat 0 for 11-138 times */
+ for (len = 11 + getbits(s, 7); len; len--)
+ lens[i++] = 0;
+ }
+ }
+ /* build dynamic huffman trees */
+ build_tree(lt, lens, nlit);
+ build_tree(dt, lens + nlit, ndist);
+}
+
+/* decode a block of data from stream with trees */
+static void decode_block(FlateStream *s, HuffTree *lt, HuffTree *dt) {
+ uint sym;
+
+ for (;;) {
+ sym = decode_symbol(s, lt);
+
+ if (sym == 256)
+ return;
+ if (sym < 256)
+ *s->dst++ = sym;
+ else {
+ int len, dist;
+
+ sym -= 257;
+ len = lenbase[sym] + getbits(s, lenbits[sym]);
+ sym = decode_symbol(s, dt);
+ dist = distbase[sym] + getbits(s, distbits[sym]);
+ /* copy match */
+ while (len--) {
+ *s->dst = *(s->dst - dist);
+ s->dst++;
+ }
+ }
+ }
+}
+
+static void inflate_uncompressed_block(FlateStream *s) {
+ uint len;
+
+ len = (s->src[1] << 8) | s->src[0];
+ s->src += 4;
+
+ /* start next block on a byte boundary */
+ s->nbits = 0;
+
+ while (len--)
+ *s->dst++ = *s->src++;
+}
+
+static void inflate_fixed_block(FlateStream *s) {
+ decode_block(s, <ree, &dtree);
+}
+
+static void inflate_dynamic_block(FlateStream *s) {
+ decode_trees(s, &s->ltree, &s->dtree);
+ decode_block(s, &s->ltree, &s->dtree);
+}
+
+
+/* extern functions */
+
+/* initialize global (static) data */
+void inflate_init(void) {
+ init_fixed_trees();
+ init_base_tables();
+}
+
+/* inflate stream from src to dst */
+uint inflate(void *dst, void *src) {
+ FlateStream s;
+ uint final;
+
+ s.src = src;
+ s.dst = s.dstbegin = dst;
+ s.nbits = 0;
+ do {
+ uint blocktype;
+
+ final = getbit(&s);
+ blocktype = getbits(&s, 2);
+
+ /* decompress block */
+ switch (blocktype) {
+ case 0:
+ inflate_uncompressed_block(&s);
+ break;
+ case 1:
+ inflate_fixed_block(&s);
+ break;
+ case 2:
+ inflate_dynamic_block(&s);
+ break;
+ }
+ } while (!final);
+ return s.dst - s.dstbegin;
+}
+
+
+/* simple test */
+
+#include <stdlib.h>
+#include <stdio.h>
+
+void *readall(FILE *in) {
+ uint len = 1 << 22;
+ void *buf;
+
+ buf = malloc(len);
+ fread(buf, 1, len, in);
+ fclose(in);
+ return buf;
+}
+
+int main(int argc, char **argv) {
+ uchar *src, *dst;
+ uint len = 1<<24;
+
+ inflate_init();
+ src = readall(argc < 2 ? stdin : fopen(argv[1], "r"));
+ dst = malloc(len);
+ len = inflate(dst, src);
+ fprintf(stderr, "inflate_simple: uncompressed %u bytes\n", len);
+ fwrite(dst, 1, len, stdout);
+ free(dst);
+ free(src);
+ return 0;
+}
