flate

commit b172e5df66913eddad8b48921390d9abbad62601
parent 149525989f75fd818ea16ce42cf93242484323e5
Author: nsz <nszabolcs@gmail.com>
Date:   Wed, 22 Apr 2009 21:51:01 +0200

inflate: fix tables
Diffstat:
README
 | 
2
+-
inflate.c
 | 
47
+++++++++++++++++------------------------------

2 files changed, 18 insertions(+), 31 deletions(-)
diff --git a/README b/README
@@ -1,6 +1,6 @@
 minimal deflate implementation
 
-source:
+based on:
 	rfc1951 from ietf
 	tinf from ibsensoftware
 	puff from zlib
diff --git a/inflate.c b/inflate.c
@@ -17,7 +17,7 @@ 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, /* number of litlen codes + block end + 2 unused */
+	Nlitlen		= Nlit+Nlen+3, /* litlen codes + block end + 2 unused */
 	Ndist		= 30,	/* number of distance codes */
 	Nclen		= 19	/* number of code length codes */
 };
@@ -31,6 +31,12 @@ enum {
 
 
 typedef struct {
+	uchar op;
+	uchar bits;
+	ushort val;
+} Code;
+
+typedef struct {
 	ushort count[HuffBits]; /* code bit length -> count */
 	ushort symbol[Nlitlen]; /* symbols ordered by code length */
 } HuffTree;
@@ -56,43 +62,25 @@ typedef struct {
 static HuffTree ltree; /* fixed lit/len tree */
 static HuffTree dtree; /* fixed distance tree */
 
+/* base offset and extra bits tables */
 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
+	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 ushort lenbase[Nlen] = {
+	3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
 };
-
-static ushort lenbase[Nlen];
-
 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
+	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
+};
+static ushort distbase[Ndist] = {
+	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
 };
-
-static ushort distbase[Ndist];
 
 /* 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;
 
@@ -333,7 +321,7 @@ static void inflate_uncompressed_block(FlateStream *s) {
 	len = (s->src[1] << 8) | s->src[0];
 	invlen = (s->src[3] << 8) | s->src[2];
 	s->src += 4;
-	if (len != (~invlen & 0x0000ffff)) {
+	if (len != (~invlen & 0xffff)) {
 		s->error = FlateCorrupted;
 		return;
 	}
@@ -370,7 +358,6 @@ static void inflate_dynamic_block(FlateStream *s) {
 /* initialize global (static) data */
 void inflate_init(void) {
 	init_fixed_trees();
-	init_base_tables();
 }
 
 /* inflate stream from src to dst */