flate

commit ebb7e504ec96aaa2524f78ec704f38f0ebc275d2
parent 27c7698383f93c1358c170b6201f3b1d032a483d
Author: nsz <nszabolcs@gmail.com>
Date:   Sat, 18 Jul 2009 15:15:22 +0200

hash tweak, removed some checks
Diffstat:
deflate_simple.c
 | 
33
++++++---------------------------

1 file changed, 6 insertions(+), 27 deletions(-)
diff --git a/deflate_simple.c b/deflate_simple.c
@@ -1,4 +1,3 @@
-#include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
 
@@ -21,12 +20,12 @@ enum {
 	MinMatch = 3,
 	MaxMatch = 258,
 	BigDist = 1 << 12,
-	MaxChainStep = 64,
-	HashBits = 12,
+	MaxChainStep = 32,
+	HashBits = 13,
 	HashSize = 1 << HashBits,
 	WinSize = 1 << 15,
 	BlockLen = 1 << 15,
-	RunlenSize = (BlockLen + 2 * MaxMatch) * 3/4,
+	RbufSize = (BlockLen + 2 * MaxMatch) * 3/4,
 	RunlenFlag = 1 << 30,
 
 	CodeBits    = 16,  /* max number of bits in a code + 1 */
@@ -51,7 +50,7 @@ typedef struct {
 	uchar *dst;             /* compressed output */
 	uint bits;
 	int nbits;
-	int rbuf[RunlenSize];   /* literal run length and (len,dist) */
+	int rbuf[RbufSize];     /* literal run length and (len,dist) */
 	int *rend;              /* current pos in rbuf */
 	int run;                /* literal count */
 	int lfreq[Nlitlen];
@@ -109,12 +108,8 @@ static void huffcodes(ushort *codes, const uchar *lens, int n) {
 		count = c[i];
 		c[i] = code;
 		code += count;
-		if (code > (1 << i))
-			abort(); /* over-subscribed */
 		code <<= 1;
 	}
-	if (code < (1 << i))
-		/* incomplete */;
 	for (i = 0; i < n; i++)
 		if (lens[i])
 			codes[i] = revcode(c[lens[i]]++, lens[i]);
@@ -122,8 +117,6 @@ static void huffcodes(ushort *codes, const uchar *lens, int n) {
 			codes[i] = 0;
 }
 
-/* min-heap for hufflens() */
-
 static int heapparent(int n) {return (n - 2)/4 * 2;}
 static int heapchild(int n)  {return 2 * n + 2;}
 
@@ -461,22 +454,8 @@ static void recordlit(State *s, int c) {
 
 /* 32 bit multiplicative hash */
 static uint gethash(uchar *p) {
-	return 2654435761U * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits);
-}
-
-/*
-static uint murmurhash(uchar *p) {
-	enum {m = 0x5bd1e995};
-	uint h = 0x6789abcd;
-
-	h ^= (p[2] << 16) + (p[1] << 8) + p[0];
-	h *= m;
-	h ^= h >> 13;
-	h *= m;
-	h ^= h >> 15;
-	return h % HashSize;
+	return 0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits);
 }
-*/
 
 static Match getmatch(State *s, uchar *src, int len) {
 	int i, j;
@@ -595,6 +574,7 @@ int deflate(uchar *src, int len, uchar *dst) {
 }
 
 
+#include <stdlib.h>
 #include <stdio.h>
 
 enum {Siz = 1<<24};
@@ -612,6 +592,5 @@ int main() {
 	fprintf(stderr, "compressed: %d\n", len);
 	free(dst);
 	free(src);
-
 	return 0;
 }