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

/*
	huffman encoding.  this array is a static heap.
	
	for each node node[i] the children are node[2i+1],
	node[2i+2].

*/

static ushort code[4*64+40*4+1*4] = {
//	white			black
	8,	0x35,	10,	0x37,
	6,	0x7,	3,	0x2,
	4,	0x7,		2,	0x3,
	4,	0x8,		2,	0x2,
	4,	0xb,		3,	0x3,
	4,	0xc,		4,	0x3,
	4,	0xe,		4,	0x2,
	4,	0xf,		5,	0x3,
	5,	0x13,		6,	0x5,
	5,	0x14,		6,	0x4,
	5,	0x7,		7,	0x4,
	5,	0x8,		7,	0x5,
	6,	0x8,	7,	0x7,
	6,	0x3,	8,	0x4,
	6,	0x34,	8,	0x7,
	6,	0x35,	9,	0x18,
	6,	0x2a,	10,	0x17,

	6,	0x2b,	10,	0x18,
	7,	0x27,	10,	0x8,
	7,	0xc,	11,	0x67,
	7,	0x8,	11,	0x68,
	7,	0x17,	11,	0x6c,
	7,	0x3,	11,	0x37,
	7,	0x4,	11,	0x28,
	7,	0x28,	11,	0x17,
	7,	0x2b,	11,	0x18,
	7,	0x13,	12,	0xca,
	7,	0x24,	12,	0xcb,
	7,	0x18,	12,	0xcc,
	8,	0x2,	12,	0xcd,
	8,	0x3,	12,	0x68,
	8,	0x1a,	12,	0x69,
	8,	0x1b,	12,	0x6a,

	8,	0x12,	12,	0x6b,
	8,	0x13,	12,	0xd2,
	8,	0x14,	12,	0xd3,
	8,	0x15,	12,	0xd4,
	8,	0x16,	12,	0xd5,
	8,	0x17,	12,	0xd6,
	8,	0x28,	12,	0xd7,
	8,	0x29,	12,	0x6c,
	8,	0x2a,	12,	0x6d,
	8,	0x2b,	12,	0xda,
	8,	0x2c,	12,	0xdb,
	8,	0x2d,	12,	0x54,
	8,	0x4,	12,	0x55,
	8,	0x5,	12,	0x56,
	8,	0xa,	12,	0x57,
	8,	0xb,	12,	0x64,

	8,	0x52,	12,	0x65,
	8,	0x53,	12,	0x52,
	8,	0x54,	12,	0x53,
	8,	0x55,	12,	0x24,
	8,	0x24,	12,	0x37,
	8,	0x25,	12,	0x38,
	8,	0x58,	12,	0x27,
	8,	0x59,	12,	0x28,
	8,	0x5a,	12,	0x58,
	8,	0x5b,	12,	0x59,
	8,	0x4a,	12,	0x2b,
	8,	0x4b,	12,	0x2c,
	8,	0x32,	12,	0x5a,
	8,	0x33,	12,	0x66,
	8,	0x34,	12,	0x67,
// makeup codes below
	5,	0x1b,		10,	0xf,
	5,	0x12,		12,	0xc8,
	6,	0x17,	12,	0xc9,
	7,	0x37,	12,	0x5b,
	8,	0x36,	12,	0x33,
	8,	0x37,	12,	0x34,
	8,	0x64,	12,	0x35,
	8,	0x65,	13,	0x6c,
	8,	0x68,	13,	0x6d,
	8,	0x67,	13,	0x4a,
	9,	0xcc,	13,	0x4b,
	9,	0xcd,	13,	0x4c,
	9,	0xd2,	13,	0x4d,
	9,	0xd3,	13,	0x72,
	9,	0xd4,	13,	0x73,
	9,	0xd5,	13,	0x74,

	9,	0xd6,	13,	0x75,
	9,	0xd7,	13,	0x76,
	9,	0xd8,	13,	0x77,
	9,	0xd9,	13,	0x52,
	9,	0xda,	13,	0x53,
	9,	0xdb,	13,	0x54,
	9,	0x98,	13,	0x55,
	9,	0x99,	13,	0x5a,
	9,	0x9a,	13,	0x5b,
	6,	0x18,	13,	0x64,
	9,	0x9b,	13,	0x65,
	11,	0x8,	11,	0x8,
	11,	0xc,	11,	0xc,
	11,	0xd,	11,	0xd,
	12,	0x12,	12,	0x12,
	12,	0x13,	12,	0x13,

	12,	0x14,	12,	0x14,
	12,	0x15,	12,	0x15,
	12,	0x16,	12,	0x16,
	12,	0x17,	12,	0x17,
	12,	0x1c,	12,	0x1c,
	12,	0x1d,	12,	0x1d,
	12,	0x1e,	12,	0x1e,
	12,	0x1f,	12,	0x1f,
// EOL code.
	12,	0x1,	11,	0x0,
};

static ushort ones[] = {
	0, 
	0x1,
	0x3,
	0x7,
	0xf,
	0x1f,
	0x3f,
	0x7f,
	0xff,
	0x1ff,
	0x3ff,
	0x7ff,
	0xfff,
	0x1fff,
};

static ushort mask8[] = {
	0,
	0x80,
	0xc0,
	0xe0,
	0xf0,
	0xf8,
	0xfc,
	0xfe,
	0xff,
};

enum {
	Coden = 4,
	Maxbits = 13,
	Hwhite = 0,
	Hblack = 1,
};

static void
state(ulong i, ushort color, ulong cbits, ulong v, ulong vbits)
{
	int idx;

	if(i < nelem(code)/Coden){
		idx = Coden*i+color*2;
		if(i>64)
			i = (i-63)*64;
		fprint(2, "%c: %uld: %0*ub\n", "WB"[color], i, (int)cbits, code[idx+1]);
	}else if(i == nelem(code)/Coden)
		fprint(2, "EOL\n");
	else
		fprint(2, "%c: %uld/%d %013ulb\n", "WB"[color], i, (int)cbits, v>>vbits-13);
}

int
tiffhuff(Biobuf *b, uchar *u, int usize, int photo, ulong width){
	uchar *ue, *up, *lp, z[3];
	ushort v1, color, r, m;
	ulong v, shift, cbits, vbits, zbits, ubits, i, j, line;

	fprint(2, "tiffhuff %d\n", usize);
	ue = u+usize;
	up = u;
	lp = u;
	memset(u, usize, 0);

	line = 0;
	color = Hwhite;
	ubits = 0;
	zbits = 0;
	cbits = 0;	// shut kenc up.
	j = 0;
	while(up < ue){
		if(zbits < 16){
			m = (24-zbits)/8;
			memmove(z, z+m, 3-m);
			memset(z+3-m, 0, 3-m);
			if(Bread(b, z+3-m, m) != m)
				return -1;
			zbits += 8*m;
		}
		shift = zbits-Maxbits;
		v = (z[0]<<16 | z[1]<<8 | z[2])>>shift;
		vbits = zbits-shift;

		for(i = 0; i < nelem(code)/Coden;){
			r = Coden*i+color*2;
			cbits = code[r];
			r = code[r+1];
			v1 = (ushort)v>>vbits-cbits;
			v1 &= ones[cbits];
			if(r == v1)
				break;
i++;
//			else if(r<v1)
//				i = 2*i+1;
//			else
//				i = 2*i+2;
		}
		zbits -= cbits;
		if(i == nelem(code)/Coden){
			fprint(2, "%08uhhb %08uhhb %08uhhb\n", z[0], z[1], z[2]);
			fprint(2, "%013ulb\n", v&ones[13]);
			fprint(2, "shift=%uld; zbits=%uld cbits=%uld\n", shift, zbits, cbits);
			fprint(2, "exp %c EOL line = %uld\n", "WB"[color], line);
			assert(i < nelem(code)/Coden);
		}
		state(i, color, cbits, v, vbits);
		if(i >= 64) {
			j += 64*(i-63);
			//if(up+(j+7)/8 < ue)
				continue;
		} else 
			j += i;
		assert(j<=width);
		if(color^photo){
			r = j+ubits;
			if(r >= 8){
				*up++ |= mask8[8]>>ubits;
				r -= 8;
				memset(up, 0xff, r/8);
				up += r/8;
				ubits = r%8;
				*up |= mask8[ubits];
			} else {
				*up |= mask8[j]>>ubits;
				ubits += j;
			}
		}else{
			r = j+ubits;
			up += r/8;
			ubits = r%8;
		}
		j = 0;
		if(((up-lp)*8+ubits) % width == 0){
			fprint(2, "EOL\n");
			zbits -= zbits%8;
			if(ubits){
				up += (ulong)up%4;
				ubits = 0;
			}
			lp = up;
			line++;
			color = Hwhite;
			if(up >= ue)
				break;
			continue;
		}
		color ^= 1;
	}
	fprint(2, "line = %uld; %uld/%d\n", line, up-u, usize);
	if(ubits > 0)
		up++;
	return up-u;
}