/*
 * Compression library. Uses a radix tree to compress substrings
 * down to 12 bit codes.
 */

#include <stdio.h>
#include "radix.h"

#include "compresstab.h"

static struct r_node *root;
static unsigned char *decompresstab[4096];
static unsigned char singletons[260];

unsigned int strings_compressed = 0;
unsigned int strings_decompressed = 0;
unsigned int chars_in = 0;
unsigned int symbols_out = 0;


void init_string_compress()
{
	int code, i;
	unsigned char *p;


	root = (struct r_node *)malloc(sizeof(struct r_node));

	root->count = 0;

	/*
	 * Get all the printables 
	 */

	p = singletons;
	*p = '\0';
	decompresstab[0] = p;
	p++;

	for (i = 1; i < 128; i++) {
		p[0] = (unsigned char)i;
		p[1] = '\0';
		code = r_insert(&root, p);
		if (code <= 0 || code > 4095) {
			printf("Invalid code 1\n");
			abort();
		}
		decompresstab[code] = p;
		p += 2;
	}

	/*
	 * Now insert all the strings in our compression table 
	 */

	for (i = 0; cmptab[i] != NULL; i++) {
		code = r_insert(&root, (unsigned char *)(cmptab[i]));
		if (code <= 0 || code > 4095) {
			printf("Invalid code 2\n");
			abort();
		}
		p = (unsigned char *)(cmptab[i]);
		decompresstab[code] = p;
	}
#ifdef DEBUG
	printf("Done inserting.\n");
#endif

}


/*
 * Compress the input string to the output array as 12 bit codes.
 * Return the number of bytes to worry about in the output.
 */

int string_compress(src, dst)
unsigned char *src;
unsigned char *dst;
{
	int code;
	int bitnum = 0;
	int bytenum;

#ifdef DEBUG
	int i;

#endif

	strings_compressed++;
	chars_in += strlen(src) + 1;

	do {
		code = r_compress(root, &src);
#ifdef DEBUG
		printf("emit code %x\n", code);
#endif
		bytenum = (bitnum >> 3);
		if (bitnum & 7) {
			dst[bytenum] = dst[bytenum] | ((code >> 8) & 0x0f);
			dst[bytenum + 1] = (code & 0xff);
		} else {
			dst[bytenum] = (code >> 4) & 0xff;
			dst[bytenum + 1] = ((code << 4) & 0xf0);
		}
		bitnum += 12;
		symbols_out++;
	} while (code != 0);

#ifdef DEBUG
	bytenum = ((bitnum & 7) ? (bitnum >> 3) + 1 : (bitnum >> 3));
	for (i = 0; i < bytenum; i++) {
		printf("%x ", dst[i]);
	}
	printf("\n");
#endif

	return ((bitnum & 7) ? (bitnum >> 3) + 1 : (bitnum >> 3));
}

/*
 * Decompress an array of 12 bit codes as produced by string_compress().
 * Return the number of bytes in the string, including zero terminator.
 */

int string_decompress(src, dst)
unsigned char *src;
unsigned char *dst;
{
	unsigned int code, bitnum, bytenum;
	register unsigned char *p, tmp;
	int count = 0;

	strings_decompressed++;

	bitnum = 0;
	while (1) {
		bytenum = bitnum >> 3;
		if (bitnum & 7) {
			code = (tmp & 0x0f) << 8;
			code |= src[bytenum + 1];
		} else {
			code = src[bytenum] << 4;
			tmp = src[bytenum + 1];
			code |= tmp >> 4;
		}
#ifdef DEBUG
		printf("Extract code %x = '%s'\n",
		       code, decompresstab[code]);
#endif
		if (code == 0)
			break;

		p = decompresstab[code];
		while (*p) {
			count++;
			*dst++ = *p++;
		}
		bitnum += 12;
	}
	*dst = '\0';
	return count + 1;	/*
				 * Include zero terminator 
				 */
}