alf: speed up compression by another 40% (but use more memory).

1 files changed, 54 insertions, 15 deletions

diff --git a/src/crunch.c b/src/crunch.c
index fc4d6e9..709e522 100644
--- a/src/crunch.c
+++ b/src/crunch.c
@@ -23,28 +23,17 @@ u8 input_buf[MAX_INPUT_SIZE];
 u8 output_buf[MAX_INPUT_SIZE];
 unsigned int input_len, output_len, out_bitpos;
 
-typedef struct s_token {
-	u8 chr;
-	u16 number;
-	struct s_token *sibling;
-	struct s_token *kids;
-} token_t;
-
-token_t tokens[MAX_TOKENS];
+short tokens[MAX_TOKENS][256];
 
 int token_bits;
 int max_token;
 int curr_token = INIT_TOKEN;
 int in_pos;
-// int new_pos;
 
 void init_table(void) {
 	int i;
 
-	for(i = 0; i < 256; i++) {
-		tokens[i].chr = tokens[i].number = i;
-		tokens[i].kids = tokens[i].sibling = 0;
-	}
+	memset(tokens, 0, sizeof(tokens));
 
 	token_bits = INITIAL_BITS;
 	max_token = 1 << INITIAL_BITS;
@@ -67,6 +56,7 @@ void indent(int level) {
 		fputs("  ", stdout);
 }
 
+#if 0
 int maxkidcount = 0, maxlevel = 0, totalkidcount = 0, nodeswithkids = 0;
 void dump_kids(token_t *t, int level) {
 	token_t *kid;
@@ -93,8 +83,10 @@ void dump_kids(token_t *t, int level) {
 		fputs("(no kids)\n", stdout);
 	}
 }
+#endif
 
 void dump_tokens(void) {
+#if 0
 	int i;
 
 	maxkidcount = maxlevel = totalkidcount = nodeswithkids = 0;
@@ -108,6 +100,7 @@ void dump_tokens(void) {
 
 	printf("maxkidcount %d, maxlevel = %d, totalkidcount = %d\n", maxkidcount, maxlevel, totalkidcount);
 	printf("avgkidcount: %.2f\n", ((float)totalkidcount) / (float)(nodeswithkids));
+#endif
 }
 
 void inc_output_len(void) {
@@ -139,6 +132,7 @@ void store_token(int tok) {
 	}
 }
 
+#if 0
 token_t *get_kid(token_t *t, u8 chr) {
 	token_t *kid;
 
@@ -226,9 +220,54 @@ void make_token(token_t *oldtok, u8 newchr) {
 	add_kid(oldtok, newtok);
 	curr_token++;
 }
+#endif
+
+short match_token(void) {
+	short t, nt;
+
+	t = input_buf[in_pos];
+
+	in_pos++;
+	if(in_pos == input_len)
+		return t;
+
+	while((nt = tokens[t][input_buf[in_pos]])) {
+		t = nt;
+		in_pos++;
+		if(in_pos == input_len) break;
+	}
+	return t;
+}
+
+void make_token(short tok, u8 chr) {
+	if(curr_token == max_token) {
+		if(opt_verbose > 1) {
+			printf("\ntoken %d won't fit in %d bits, ", max_token, token_bits);
+		}
+		if(token_bits == MAX_BITS) {
+			if(opt_verbose > 1) {
+				printf("resetting token_bits to %d\n", INITIAL_BITS);
+				printf("token table is full, clearing, old contents:\n");
+				dump_tokens();
+			}
+			store_token(TOK_RESET); /* stored at the *old* token size! */
+			token_bits = INITIAL_BITS;
+			init_table();
+			return; /* since we're starting over, *don't* make a token */
+		} else {
+			token_bits++;
+			if(opt_verbose > 1) {
+				printf("token_bits increased to %d\n", token_bits);
+			}
+		}
+		max_token = 1 << token_bits;
+	}
 
+	tokens[tok][chr] = curr_token;
+	curr_token++;
+}
 void crunch(void) {
-	token_t *tok;
+	short tok;
 
 	init_table();
 	out_bitpos = 0;
@@ -245,7 +284,7 @@ void crunch(void) {
 
 	while(in_pos < input_len) {
 		tok = match_token();
-		store_token(tok->number);
+		store_token(tok);
 		if(in_pos < input_len)
 			make_token(tok, input_buf[in_pos]);
 	}