path: root/src/crunch.c

/*
 * See the bottom of this file for an explanation of the data
 * structure, complete with high-tech ASCII art.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "u816.h"
#include "crunch.h"
#include "self.h"

#define INITIAL_BITS 9
#define MAX_BITS 12
#define MAX_TOKENS (1 << MAX_BITS)
#define TOK_RESET 256
#define TOK_END 257
#define INIT_TOKEN 258

extern int opt_verbose; /* alf.c, -v option */

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];

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;
	}

	token_bits = INITIAL_BITS;
	max_token = 1 << INITIAL_BITS;
	curr_token = INIT_TOKEN;
}

char *fmt_chr(u8 c) {
	static char buf[10];
	if(c > 33 && c < 127)
		sprintf(buf, "'%c'", c);
	else
		sprintf(buf, "$%02x", c);
	return buf;
}

void indent(int level) {
	int i;

	for(i = 0; i < level; i++)
		fputs("  ", stdout);
}

int maxkidcount = 0, maxlevel = 0, totalkidcount = 0, nodeswithkids = 0;
void dump_kids(token_t *t, int level) {
	token_t *kid;
	int kidcount =0;

	if(level > maxlevel) maxlevel = level;

	if(t->kids) {
		kid = t->kids;
		while(kid) {
			kidcount++;
			totalkidcount++;
			indent(level);
			printf("#%d/%s\n", kid->number, fmt_chr(kid->chr));
			dump_kids(kid, level + 1);
			kid = kid->sibling;
		}
		indent(level - 1);
		printf("#%d has %d kids\n", t->number, kidcount);
		if(kidcount > maxkidcount) maxkidcount = kidcount;
		nodeswithkids++;
	} else {
		indent(level);
		fputs("(no kids)\n", stdout);
	}
}

void dump_tokens(void) {
	int i;

	maxkidcount = maxlevel = totalkidcount = nodeswithkids = 0;

	for(i = 0; i < 256; i++) {
		if(tokens[i].kids) {
			printf("tokens[%s], #%d\n", fmt_chr(tokens[i].chr), tokens[i].number);
			dump_kids(&tokens[i], 1);
		}
	}

	printf("maxkidcount %d, maxlevel = %d, totalkidcount = %d\n", maxkidcount, maxlevel, totalkidcount);
	printf("avgkidcount: %.2f\n", ((float)totalkidcount) / (float)(nodeswithkids));
}

void inc_output_len(void) {
	if(++output_len == MAX_INPUT_SIZE) {
		fprintf(stderr, "%s: fatal: compressed file would be >16MB.\n", self);
		exit(1);
	}
	output_buf[output_len] = 0;
}

void append_bit(int bit) {
	output_buf[output_len] |= (bit << (7 - out_bitpos));
	out_bitpos++;
	if(out_bitpos == 8) {
		out_bitpos = 0;
		inc_output_len();
	}
}

void store_token(int tok) {
	int mask;

	if(opt_verbose > 1) {
		printf("<%d >%d:%d #%d\n", in_pos, output_len, out_bitpos, tok);
	}

	for(mask = 1 << (token_bits - 1); mask; mask >>= 1) {
		append_bit(tok & mask ? 1 : 0);
	}
}

token_t *get_kid(token_t *t, u8 chr) {
	token_t *kid;

	if(!t->kids) return 0;

	kid = t->kids;
	while(kid) {
		if(kid->chr == chr)
			return kid;
		kid = kid->sibling;
	}
	return 0;
}

token_t *match_token(void) {
	token_t *t, *p;

	t = &tokens[input_buf[in_pos]];
	in_pos++;
	if(in_pos == input_len)
		return t;

	p = t;
	while((p = get_kid(t, input_buf[in_pos]))) {
		t = p;
		in_pos++;
		if(in_pos == input_len) break;
	}
	return t;
}

token_t *new_token(u8 chr) {
	token_t *newtok;

	newtok = &tokens[curr_token];
	newtok->chr = chr;
	newtok->kids = newtok->sibling = 0;
	newtok->number = curr_token;

	return newtok;
}

/* since we're not sorting the kids, adding the new kid as the
   head of the list is faster than walking the list to add it
   to the tail. gives about a 10% speedup. */
void add_kid(token_t *oldtok, token_t *newtok) {
	if(!oldtok->kids) {
		oldtok->kids = newtok;
		return;
	}

	newtok->sibling = oldtok->kids;
	oldtok->kids = newtok;
}

void make_token(token_t *oldtok, u8 newchr) {
	token_t *newtok;

	/* if the token table is full, reset it. basically start over like
	   we would with a new file. */
	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;
	}

	newtok = new_token(newchr);
	add_kid(oldtok, newtok);
	curr_token++;
}

void crunch(void) {
	token_t *tok;

	init_table();
	out_bitpos = 0;
	in_pos = 0;

	/* 0-byte input files don't get a TOK_RESET */
	if(!input_len) {
		store_token(TOK_END);
		inc_output_len();
		return;
	}

	store_token(TOK_RESET);

	while(in_pos < input_len) {
		tok = match_token();
		store_token(tok->number);
		if(in_pos < input_len)
			make_token(tok, input_buf[in_pos]);
	}

	store_token(TOK_END);
	if(out_bitpos) inc_output_len();

	if(opt_verbose > 1) {
		printf("\nfinal token table contents:\n");
		dump_tokens();
	}
	init_table();
}

/* ********************************************************************

The tokens are stored in a tree with 256 roots (tokens[0 to 256]).
There's one root per character code (0-255). This serves as the
hard-coded initial dictionary (each token number at this level maps to
its character code).

Each node's siblings pointer points to the next node at that level.
This makes each level of a tree a linked list.

Each node that has children, its kids pointer points to the head of
the siblings list (the first of its child nodes).

When creating a token, you pass make_token() a pointer to an existing
token. For example if your new token is for the string "ab", you pass
make_token() the address of tokens['a']. The new token will be
added to the 'a' token's kids as the sibling of the last kid in the
list (if there are already kids) or the first kid if there are none.

The number in the token_t increases sequentially as tokens are
created, and is the compressed token that actually get written to the
ALF file. The chr is the last character of the token (the previous
ones are at higher levels of the tree).

What match_token() does is walk the tree, starting from the current
input position and from the root node for the byte at the current
position, and search each level for a token whose chr matches the
next byte in the input. It keeps searching until there's no match, and
returns the last token it matched. It can return the root, which means
no other tokens start with that character.

An example: the input begins with "abcdaZ".


Partial token structure:

token[['a'] = token #97, no siblings
 \- kids: token #130, b; token #<whatever>, Z
    \- kids: token #131, c

Later on in the file, if we run into the string "abcX", match_token()
will start with the root token for 'a', walk through its kids looking
for 'b' (which it finds), then walk through the 'b' token's kids
looking for a 'c' (which it finds). Suppose the letter 'X' has never
occured yet in the input. match_token() will return token #131 (follow
the tree, that's the token for "abc").

A new token is created for every character in the file that doesn't
match one of the existing tokens.

Walking the tree is fast, but it might be made even faster by sorting
the kids at each level, and doing a binary search instead of linear...
or not: most nodes that have kids only have 2 or 3 (avgkidcount around
2.5 for a text file). The overhead of sorting might make performance
worse.

********************************************************************* */