## diffname port/unthwack.c 1999/1001
## diff -e /dev/null /n/emeliedump/1999/1001/sys/src/brazil/port/unthwack.c
0a
#include "u.h"
#include "../port/lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"

#include "thwack.h"

typedef struct HuffDec		HuffDec;

struct HuffDec
{
	ulong	maxcode[MaxLen];
	ulong	last[MaxLen];
	ulong	decode[MaxLen];
};

static HuffDec lentab = 
{
/*	0	1	2	3	4	5	6	*/
	{0,	0,	0x2,	0,	0xe,	0x1e,	0x3f},
	{-1,	0+0,	0x2+1,	-1,	0xe+2,	0x1e+5,	0x3f+6},
	{
		0,
		1,
		7, 3, 2,
		4,
		6, 5
	},
};

static ulong	bitget(Unthwack *ut, int nb);
static ulong	iomegaget(Unthwack *ut);

void
unthwackinit(Unthwack *ut)
{
	int i;

	memset(ut, 0, sizeof *ut);
	for(i = 0; i < EWinBlocks; i++)
		ut->blocks[i].data = ut->data[i];
}

/*
 * to speed up, inline bitget
 */
int
unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
{
	UnthwBlock blocks[CompBlocks], *b, *eblocks;
	uchar *s, *es, *d, *dmax;
	ulong cmask, cseq, bseq, utbits, utnbits;
	int off, len, bits, slot, tslot;

	if(nsrc < 4 || nsrc > ThwMaxBlock || waserror())
		return -1;

	ut->src = src + 2;
	ut->smax = src + nsrc;

	/*
	 * find the correct slot for this block,
	 * the oldest block around.  the encoder
	 * doesn't use a history at wraparound,
	 * so don't worry about that case.
	 */
	tslot = ut->slot;
	for(;;){
		slot = tslot - 1;
		if(slot < 0)
			slot += DWinBlocks;
		if(ut->blocks[slot].seq <= seq)
			break;
		ut->blocks[slot] = ut->blocks[slot];
		tslot = slot;
	}
	b = blocks;
	ut->blocks[tslot].seq = seq;
	ut->blocks[tslot].maxoff = 0;
	*b = ut->blocks[tslot];
	d = b->data;
	dmax = d + ndst;

	/*
	 * set up the history blocks
	 */
	cseq = seq - src[0];
	cmask = src[1];
	b++;
	slot = tslot;
	while(cseq != seq && b < blocks + CompBlocks){
		slot--;
		if(slot < 0)
			slot += DWinBlocks;
		if(slot == ut->slot)
			break;
		bseq = ut->blocks[slot].seq;
		if(bseq == cseq){
			*b = ut->blocks[slot];
			b++;
			if(cmask == 0){
				cseq = seq;
				break;
			}
			do{
				bits = cmask & 1;
				cseq--;
				cmask >>= 1;
			}while(!bits);
		}
	}
	eblocks = b;
	if(cseq != seq){
		print("blocks not in decompression window: cseq=%d seq=%d cmask=%ux nb=%d\n", cseq, seq, cmask, eblocks - blocks);
		error("unthwack bad window");
	}

	utnbits = 0;
	utbits = 0;
	while(ut->src < ut->smax || ut->nbits >= MinDecode){
		while(utnbits < 9){
			if(ut->src >= ut->smax)
				error("unthwack eof");
			utbits <<= 8;
			utbits |= *ut->src++;
			utnbits += 8;
		}
		utnbits -= 9;
		off = (utbits >> utnbits) & ((1 << 9) - 1);

		bits = off >> 5;
		if(bits >= MaxOff){
			*d++ = off;
			blocks->maxoff++;
			continue;
		}
		off &= (1 << 5) - 1;
		if(bits){
			bits--;
			off |= 1 << 5;
		}
		bits += OffBase - 5;
		off <<= bits;

		while(utnbits < bits){
			if(ut->src >= ut->smax)
				error("unthwack eof");
			utbits <<= 8;
			utbits |= *ut->src++;
			utnbits += 8;
		}
		utnbits -= bits;
		off |= (utbits >> utnbits) & ((1 << bits) - 1);
		off++;

		len = 0;
		bits = 0;
		do{
			len <<= 1;
			if(utnbits < 1){
				if(ut->src >= ut->smax)
					error("unthwack eof");
				utbits <<= 8;
				utbits |= *ut->src++;
				utnbits += 8;
			}
			utnbits--;
			len |= (utbits >> utnbits) & 1;
			bits++;
		}while(len > lentab.maxcode[bits]);
		len = lentab.decode[lentab.last[bits] - len];

		if(len == MaxLen - 1){
			ut->nbits = utnbits;
			ut->bits = utbits;
			len += iomegaget(ut) - 1;
			utnbits = ut->nbits;
			utbits = ut->bits;
		}
		len += MinMatch;

		b = blocks;
		while(off > b->maxoff){
			off -= b->maxoff;
			b++;
			if(b >= eblocks)
				error("unthwack offset");
		}
		if(d + len > dmax
		|| b != blocks && len > off)
			error("unthwack len");
		s = b->data + b->maxoff - off;
		es = s + len;
		while(s < es)
			*d++ = *s++;
		blocks->maxoff += len;
	}

	len = d - blocks->data;
	memmove(dst, blocks->data, len);
	ut->blocks[tslot].maxoff = len;

	ut->slot++;
	if(ut->slot >= DWinBlocks)
		ut->slot = 0;

	poperror();
	return len;
}

/*
 * elias's omega code, modified
 * for at least 3 bit transmission
 */
static ulong
iomegaget(Unthwack *ut)
{
	ulong v;
	int b;

	v = bitget(ut, 3);
	if((v & 0x4) == 0)
		return v + 1;
	for(;;){
		b = bitget(ut, 1);
		if(b == 0)
			return v + 1;
		if(v > 16)
			break;
		v--;
		v = (b << v) | bitget(ut, v);
	}
	error("unthwack iomegaget");
	return ~0;
}

static ulong
bitget(Unthwack *ut, int nb)
{
	int c;

	while(ut->nbits < nb){
		if(ut->src >= ut->smax)
			error("unthwack eof");
		c = *ut->src++;
		ut->bits <<= 8;
		ut->bits |= c;
		ut->nbits += 8;
	}
	ut->nbits -= nb;
	return (ut->bits >> ut->nbits) & ((1 << nb) - 1);
}
.
## diffname port/unthwack.c 1999/1007
## diff -e /n/emeliedump/1999/1001/sys/src/brazil/port/unthwack.c /n/emeliedump/1999/1007/sys/src/brazil/port/unthwack.c
210,252d
208d
198a
	if(utnbits < overbits)
		return -1;
.
192c
			return -1;
.
188c
				return -1;
.
180a

.
174,179c
			code = len - BigLenCode;
			len = MaxFastLen;
			bits = 8;
			use = BigLenBase;
			while(code >= use){
				len += use;
				code -= use;
				code <<= 1;
				utnbits--;
				code |= (utbits >> utnbits) & 1;
				use <<= bits & 1;
				bits++;
			}
			len += code;
.
168,172d
165c
				if(src < smax)
					utbits |= *src++;
				else
					overbits += 8;
.
160,163c
			bits++;
			len = utbits >> (utnbits - bits);
		}while(bits < BigLenBits && len > lentab.maxcode[bits]);
		utnbits -= bits;

		if(bits < BigLenBits)
			len = lentab.decode[lentab.last[bits] - len];
		else{
			while(utnbits < MaxLenDecode){
.
158a
		utbits &= (1 << utnbits) - 1;
.
157d
146,152d
131a
		/*
		 * literal
		 */
.
126c
			if(src < smax)
				utbits |= *src++;
			else
				overbits += 8;
.
121,124c
	overbits = 0;
	while(src < smax || utnbits - overbits >= MinDecode){
		while(utnbits < MaxOffDecode + BigLenBits){
.
118a
	smax = src + nsrc;
	src += 2;
.
115,116c
		print("blocks not in decompression window: cseq=%ld seq=%ld cmask=%lux nb=%ld\n", cseq, seq, cmask, eblocks - blocks);
		return -1;
.
59,61d
56c
	if(nsrc < 4 || nsrc > ThwMaxBlock)
.
52,54c
	uchar *s, *es, *d, *dmax, *smax;
	ulong cmask, cseq, bseq, utbits;
	int off, len, bits, slot, tslot, use, code, utnbits, overbits;
.
45,47d
32,34d
28c
		6, 5,
		8, 7,
.
26c
		3, 2,
.
20,22c
/*	0	1	2	3	4	5	6	7	*/
	{0,	0,	0x2,	0,	0xd,	0x1c,	0x3b,	0x79},
	{-1,	0+0,	0x2+1,	-1,	0xd+2,	0x1c+4,	0x3b+5,	0x79+7},
.
13,15c
	ulong	maxcode[MaxFastLen];
	ulong	last[MaxFastLen];
	ulong	decode[MaxFastLen];
.
2c
#include "lib.h"
.
## diffname port/unthwack.c 1999/1022
## diff -e /n/emeliedump/1999/1007/sys/src/brazil/port/unthwack.c /n/emeliedump/1999/1022/sys/src/brazil/port/unthwack.c
142,144d
139,140c
			bits += OffBase - 1;
			off = 1 << bits;
		}else{
			bits = OffBase;
			off = 0;
.
137c

		/*
		 * match; next 3 bits decode offset range
		 */
		utnbits -= 4;
		bits = (utbits >> utnbits) & ((1 << 3) - 1);
.
131,133c
		if(((utbits >> (utnbits - 1)) & 1) == 0){
			if(lithist & 0xf){
				utnbits -= 9;
				lit = (utbits >> utnbits) & 0xff;
				lit &= 255;
			}else{
				utnbits -= 8;
				lit = (utbits >> utnbits) & 0x7f;
				if(lit < 32){
					if(lit < 24){
						utnbits -= 2;
						lit = (lit << 2) | ((utbits >> utnbits) & 3);
					}else{
						utnbits -= 3;
						lit = (lit << 3) | ((utbits >> utnbits) & 7);
					}
					lit = (lit - 64) & 0xff;
				}
			}
			*d++ = lit;
			lithist = (lithist << 1) | lit < 32 | lit > 127;
.
125,126d
117c
		while(utnbits <= 24){
.
115a
	lithist = ~0;
.
47,48c
	uchar *s, *es, *d, *dmax, *smax, lit;
	ulong cmask, cseq, bseq, utbits, lithist;
.
2c
#include "../port/lib.h"
.
## diffname port/unthwack.c 1999/1111
## diff -e /n/emeliedump/1999/1022/sys/src/brazil/port/unthwack.c /n/emeliedump/1999/1111/sys/src/9/port/unthwack.c
223a

		for(i = 0; i < len; i++)
			d[i] = s[i];
		d += len;
.
220,222d
208a
		utnbits -= bits;
		off |= (utbits >> utnbits) & ((1 << bits) - 1);
		off++;

.
207c
		/*
		 * offset
		 */
		utnbits -= 4;
		bits = (utbits >> utnbits) & 0xf;
		off = offbase[bits];
		bits = offbits[bits];
.
204a

			while(utnbits <= 24){
				utbits <<= 8;
				if(src < smax)
					utbits |= *src++;
				else
					overbits += 8;
				utnbits += 8;
			}
.
201,202c
				use <<= bits;
				bits ^= 1;
.
182,194c
			utnbits -= DBigLenBits;
			code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
			len = DMaxFastLen;
			use = DBigLenBase;
			bits = (DBigLenBits & 1) ^ 1;
.
158,180c
		if(len < 255)
			utnbits -= lenbits[len];
.
156c
		 * length
.
130c
		len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
		if(len == 0){
.
107c
		print("blocks not in decompression window: cseq=%ld seq=%ld cmask=%lx nb=%ld\n", cseq, seq, cmask, eblocks - blocks);
.
67c
		ut->blocks[slot] = ut->blocks[tslot];
.
55,57c
	 * insert this block in it's correct sequence number order.
	 * replace the oldest block, which is always pointed to by ut->slot.
	 * the encoder doesn't use a history at wraparound,
.
49c
	int i, off, len, bits, slot, tslot, use, code, utnbits, overbits;
.
47c
	uchar *s, *d, *dmax, *smax, lit;
.
43a
unthwackadd(Unthwack *ut, uchar *src, int nsrc, ulong seq)
{
	int slot, tslot;

	if(nsrc > ThwMaxBlock)
		return -1;

#ifndef NOUNCOMP
	tslot = ut->slot;
	for(;;){
		slot = tslot - 1;
		if(slot < 0)
			slot += DWinBlocks;
		if(ut->blocks[slot].seq <= seq)
			break;
		ut->blocks[slot] = ut->blocks[tslot];
		tslot = slot;
	}
	ut->blocks[tslot].seq = seq;
	ut->blocks[tslot].maxoff = nsrc;
	memmove(ut->blocks[tslot].data, src, nsrc);

	ut->slot++;
	if(ut->slot >= DWinBlocks)
		ut->slot = 0;
#endif
	return nsrc;
}

int
.
39c
	for(i = 0; i < DWinBlocks; i++)
.
32a
static uchar lenbits[] =
{
	0, 0, 0,
	2, 3, 5, 5,
};

static uchar offbits[16] =
{
	5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 13
};

static ushort offbase[16] =
{
	0, 0x20,
	0x40, 0x60,
	0x80, 0xc0,
	0x100, 0x180,
	0x200, 0x300,
	0x400, 0x600,
	0x800, 0xc00,
	0x1000,
	0x2000
};

.
20,30c
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	3, 3, 3, 3, 3, 3, 3, 3,
	4, 4, 4, 4,
	5,
	6,
	255,
	255
.
18c
static uchar lenval[1 << (DBigLenBits - 1)] =
.
13,15c
	DMaxFastLen	= 7,
	DBigLenCode	= 0x3c,		/* minimum code for large lenth encoding */
	DBigLenBits	= 6,
	DBigLenBase	= 1		/* starting items to encode for big lens */
.
11c
enum
.
9c
/*
 * don't include compressed blocks
 */
#define NOUNCOMP
.
2c
#include "lib.h"
.
## diffname port/unthwack.c 1999/1116
## diff -e /n/emeliedump/1999/1111/sys/src/9/port/unthwack.c /n/emeliedump/1999/1116/sys/src/9/port/unthwack.c
121c
		d = ut->blocks[tslot].data;
		ut->blocks[tslot] = ut->blocks[slot];
		ut->blocks[slot].data = d;
.
68,97d
9,13d
## diffname port/unthwack.c 2000/0912
## diff -e /n/emeliedump/1999/1116/sys/src/9/port/unthwack.c /n/emeliedump/2000/0912/sys/src/9/port/unthwack.c
192a
				if(utnbits < 0)
					return -1;
.
172c
			lithist = (lithist << 1) | (lit < 32) | (lit > 127);
.
## diffname port/unthwack.c 2001/0116
## diff -e /n/emeliedump/2000/0912/sys/src/9/port/unthwack.c /n/emeliedump/2001/0116/sys/src/9/port/unthwack.c
170a
			if(d >= dmax)
				return -1;
.
## diffname port/unthwack.c 2001/0214
## diff -e /n/emeliedump/2001/0116/sys/src/9/port/unthwack.c /n/emeliedump/2001/0214/sys/src/9/port/unthwack.c
249,251c
	unthwackinsert(ut, len, seq);
.
247d
128,129c
		print("blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n", seq, cseq, src[0], cmask, src[1]);
		return -2;
.
104d
93,94c
	ut->blocks[tslot].maxoff = len;

	ut->slot++;
	if(ut->slot >= DWinBlocks)
		ut->slot = 0;

	ut->blocks[ut->slot].seq = ~0UL;
	ut->blocks[ut->slot].maxoff = 0;

	return tslot;
}

int
unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
{
	UnthwBlock blocks[CompBlocks], *b, *eblocks;
	uchar *s, *d, *dmax, *smax, lit;
	ulong cmask, cseq, bseq, utbits;
	int i, off, len, bits, slot, use, code, utnbits, overbits, lithist;

	if(nsrc < 4 || nsrc > ThwMaxBlock)
		return -1;

	slot = ut->slot;
	b = blocks;
	*b = ut->blocks[slot];
.
91d
84c
		if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0)
.
73,78c
/*
 * insert this block in it's correct sequence number order.
 * replace the oldest block, which is always pointed to by ut->slot.
 * the encoder doesn't use a history at wraparound,
 * so don't worry about that case.
 */
static int
unthwackinsert(Unthwack *ut, int len, ulong seq)
{
	uchar *d;
	int slot, tslot;

.
70,71c
	seq = ~0UL;
	m = 0;
	slot = ut->slot;
	for(;;){
		slot--;
		if(slot < 0)
			slot += DWinBlocks;
		if(slot == ut->slot)
			break;
		if(ut->blocks[slot].maxoff == 0)
			continue;
		bseq = ut->blocks[slot].seq;
		if(seq == ~0UL)
			seq = bseq;
		else if(seq - bseq > MaxSeqMask)
			break;
		else
			m |= 1 << (seq - bseq - 1);
	}
	*mask = m;
	return seq;
}
.
65,68c
	ulong bseq, seq;
	int slot, m;
.
62,63c
ulong
unthwackstate(Unthwack *ut, uchar *mask)
.
## diffname port/unthwack.c 2001/0527
## diff -e /n/emeliedump/2001/0214/sys/src/9/port/unthwack.c /n/emeliedump/2001/0527/sys/src/9/port/unthwack.c
294c
	ut->slot++;
	if(ut->slot >= DWinBlocks)
		ut->slot = 0;
.
292a
	ut->blocks[tslot].maxoff = len;
.
217,218d
174,175c
		print("blocks not in decompression window: cseq=%ld seq=%ld cmask=%lx nb=%ld\n", cseq, seq, cmask, eblocks - blocks);
		return -1;
.
150a
	slot = tslot;
.
141c
	ut->blocks[tslot].seq = seq;
	ut->blocks[tslot].maxoff = 0;
	*b = ut->blocks[tslot];
.
115,139d
108c
		if(ut->blocks[slot].seq <= seq)
.
91,102c
	/*
	 * insert this block in it's correct sequence number order.
	 * replace the oldest block, which is always pointed to by ut->slot.
	 * the encoder doesn't use a history at wraparound,
	 * so don't worry about that case.
	 */
.
68,89c
	if(nsrc < 4 || nsrc > ThwMaxBlock)
		return -1;
.
65,66c
	UnthwBlock blocks[CompBlocks], *b, *eblocks;
	uchar *s, *d, *dmax, *smax, lit;
	ulong cmask, cseq, bseq, utbits, lithist;
	int i, off, len, bits, slot, tslot, use, code, utnbits, overbits;
.
62,63c
int
unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
.
## diffname port/unthwack.c 2001/0609
## diff -e /n/emeliedump/2001/0527/sys/src/9/port/unthwack.c /n/emeliedump/2001/0609/sys/src/9/port/unthwack.c
247,249c
	unthwackinsert(ut, len, seq);
.
245d
170a
			if(d >= dmax)
				return -1;
.
128,129c
		print("blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n", seq, cseq, src[0], cmask, src[1]);
		return -2;
.
104d
93,94c
	ut->blocks[tslot].maxoff = len;

	ut->slot++;
	if(ut->slot >= DWinBlocks)
		ut->slot = 0;

	ut->blocks[ut->slot].seq = ~0UL;
	ut->blocks[ut->slot].maxoff = 0;

	return tslot;
}

int
unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
{
	UnthwBlock blocks[CompBlocks], *b, *eblocks;
	uchar *s, *d, *dmax, *smax, lit;
	ulong cmask, cseq, bseq, utbits;
	int i, off, len, bits, slot, use, code, utnbits, overbits, lithist;

	if(nsrc < 4 || nsrc > ThwMaxBlock)
		return -1;

	slot = ut->slot;
	b = blocks;
	*b = ut->blocks[slot];
.
91d
84c
		if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0)
.
73,78c
/*
 * insert this block in it's correct sequence number order.
 * replace the oldest block, which is always pointed to by ut->slot.
 * the encoder doesn't use a history at wraparound,
 * so don't worry about that case.
 */
static int
unthwackinsert(Unthwack *ut, int len, ulong seq)
{
	uchar *d;
	int slot, tslot;

.
70,71c
	seq = ~0UL;
	m = 0;
	slot = ut->slot;
	for(;;){
		slot--;
		if(slot < 0)
			slot += DWinBlocks;
		if(slot == ut->slot)
			break;
		if(ut->blocks[slot].maxoff == 0)
			continue;
		bseq = ut->blocks[slot].seq;
		if(seq == ~0UL)
			seq = bseq;
		else if(seq - bseq > MaxSeqMask)
			break;
		else
			m |= 1 << (seq - bseq - 1);
	}
	*mask = m;
	return seq;
}
.
65,68c
	ulong bseq, seq;
	int slot, m;
.
62,63c
ulong
unthwackstate(Unthwack *ut, uchar *mask)
.