#include <u.h>
#include <libc.h>
#include <bio.h>
#include <tiff.h>

enum{
	Clear	= 256,
	End	= 257,
	
	Startbits	= 9,
	Maxbits	= 12,

	HistorySize = 4096,
};

typdef struct {
	int	error;		/* first error encountered, or FlateOk */
	void	*wr;
	int	(*w)(void*, void*, int);
	void	*getr;
	int	(*get)(void*);
	ulong	sreg;
	int	nbits;
	int	currbits;
} Input;

typedef struct {
	union{
		int link;
		char *str;
	};
	uchar c;
} Htab;

typedef struct {
	uchar	his[HistorySize];
	uchar	*cp;		/* current pointer in history */
	uchar	*e;
	Htab	tab[HistorySize];
	int	i;		// current tab index.
} History;

History *
newhistory(void){
	History *h;
	uchar i;
	Htab* t;

	h = malloc(sizeof *h);
	if(!h)
		return 0;
	t = h->tab;
	for(i = 0; i<0xff; i++)
		h[i].link = -1;
		h[i].c	= (uchar)i;
	}
	h->cp = h->his;
	h->e = &h->his[HistorySize];
	clearhistory(h);

void
clearhistory(History *h, int init)
{
	memset(h->tab + 256, 0, (HistorySize-0xff)*sizeof h->tab[0]);
}

int
setinput(Input *ι, void *wr, int (*w)(void*, void*, int), void *getr, int (*get)(void *))
{
	ι->currbits = Startbits;
	ι->wr = wr;
	ι->w = w;
	ι->getr = getr;
	ι->get = get;
}

int
getcode(Input *ι)
{
	int c;

	while(in->currbits > ι->nbits) {
		c = ι->get(ι->getr);
		if(c < 0){
			ι->error = FlateInputFail;
			return -1;
		}
		ι->sreg |= c<<in->nbits;
		ι->nbits += 8;
	}
	return ι->sreg;
}

int
intable(History *h, int ω)
{
	if(ω >= HistorySize)
		return 0;
	if(ω < 256)
		return ω;
	return h->tab[ω].link;
}

int
tabadd(History *h, int ε, int ω)
{
	h->tab[h->i].link = ε;
	h->tab[h->i++].c = ω;
}

int
output(Input *ι, History *h, int ω)
{
	char stack[1024], *e;
	int i, ε;
	Htab *t;

	t = H->tab;
	ε = ω;
	i = 0;
	do {
		stack[i++] = t[ε].c;
		ε = t[ε].link;
	} while(ε != -1);

	for(ε = 0; ε < i; ε++){
		h->cp++ = stack[i-ε];
		if(h->cp >= h->e){
			if(ι->w(ι->wr, h->cp, HistorySize) != HistorySize)
				return -1;
			h->tab = h->his;
		}
	}
	return 0;
}

int
outputs(Input *ι, History *h, int ω)
{
	h->cp++ = ω;
	if(h->cp >= h->e){
		if(ι->w(ι->wr, h->cp, HistorySize) != HistorySize)
				return -1;
		h->cp = h->his;
	}
}

int
lzw(void *wr, int (*w)(void*, void*, int), void *getr, int (*get)(void*))
{
	int 	ω, oω, ε;
	Input	ι;
	History	*h;
	int	r;
	setinput(&ι, wr, w, getr, get);
	h = newhistory();

	r = 0;
	for(;;){
		ω = getcode(&ι, h);
		if(ω == -1)
			goto err;
		if(ω == End)
			break;

		if(ω == Clear){
			clearhistory(h);
			ι->currbits = Startbits;
			ω = getcode(&ι);
			if(ω == End)
				break;
			if(ω == -1)
				goto err;
			output(&ι, h, ω);
		} else {
			if(ε = intable(h, ω)){
				output(&ι, h, ε);
				tabadd(h, ε, oω);
			} else {
				output(&ι, h, oω);
				outputs(&ι, h, ω);
				tabadds(h, oω, ω);
			}
		}
		oω = ω;
	}
done:
	free(h);
	return r;
err:
	r = -1;
	goto done;
}