Import sources from 2011-03-30 iso image

1 files changed, 298 insertions, 0 deletions

diff --git a/sys/src/9/port/unthwack.c b/sys/src/9/port/unthwack.c
new file mode 100755
index 000000000..b60857596
--- /dev/null
+++ b/sys/src/9/port/unthwack.c
@@ -0,0 +1,298 @@
+#include "u.h"
+#include "lib.h"
+#include "mem.h"
+#include "dat.h"
+#include "fns.h"
+
+#include "thwack.h"
+
+enum
+{
+	DMaxFastLen	= 7,
+	DBigLenCode	= 0x3c,		/* minimum code for large lenth encoding */
+	DBigLenBits	= 6,
+	DBigLenBase	= 1		/* starting items to encode for big lens */
+};
+
+static uchar lenval[1 << (DBigLenBits - 1)] =
+{
+	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
+};
+
+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
+};
+
+void
+unthwackinit(Unthwack *ut)
+{
+	int i;
+
+	memset(ut, 0, sizeof *ut);
+	for(i = 0; i < DWinBlocks; i++)
+		ut->blocks[i].data = ut->data[i];
+}
+
+ulong
+unthwackstate(Unthwack *ut, uchar *mask)
+{
+	ulong bseq, seq;
+	int slot, m;
+
+	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;
+}
+
+/*
+ * 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;
+
+	tslot = ut->slot;
+	for(;;){
+		slot = tslot - 1;
+		if(slot < 0)
+			slot += DWinBlocks;
+		if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0)
+			break;
+		d = ut->blocks[tslot].data;
+		ut->blocks[tslot] = ut->blocks[slot];
+		ut->blocks[slot].data = d;
+		tslot = slot;
+	}
+	ut->blocks[tslot].seq = seq;
+	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];
+	d = b->data;
+	dmax = d + ndst;
+
+	/*
+	 * set up the history blocks
+	 */
+	cseq = seq - src[0];
+	cmask = src[1];
+	b++;
+	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("unthwack: blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n",
+			seq, cseq, src[0], cmask, src[1]);
+		return -2;
+	}
+
+	smax = src + nsrc;
+	src += 2;
+	utnbits = 0;
+	utbits = 0;
+	overbits = 0;
+	lithist = ~0;
+	while(src < smax || utnbits - overbits >= MinDecode){
+		while(utnbits <= 24){
+			utbits <<= 8;
+			if(src < smax)
+				utbits |= *src++;
+			else
+				overbits += 8;
+			utnbits += 8;
+		}
+
+		/*
+		 * literal
+		 */
+		len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
+		if(len == 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;
+				}
+			}
+			if(d >= dmax)
+				return -1;
+			*d++ = lit;
+			lithist = (lithist << 1) | (lit < 32) | (lit > 127);
+			blocks->maxoff++;
+			continue;
+		}
+
+		/*
+		 * length
+		 */
+		if(len < 255)
+			utnbits -= lenbits[len];
+		else{
+			utnbits -= DBigLenBits;
+			code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
+			len = DMaxFastLen;
+			use = DBigLenBase;
+			bits = (DBigLenBits & 1) ^ 1;
+			while(code >= use){
+				len += use;
+				code -= use;
+				code <<= 1;
+				utnbits--;
+				if(utnbits < 0)
+					return -1;
+				code |= (utbits >> utnbits) & 1;
+				use <<= bits;
+				bits ^= 1;
+			}
+			len += code;
+
+			while(utnbits <= 24){
+				utbits <<= 8;
+				if(src < smax)
+					utbits |= *src++;
+				else
+					overbits += 8;
+				utnbits += 8;
+			}
+		}
+
+		/*
+		 * offset
+		 */
+		utnbits -= 4;
+		bits = (utbits >> utnbits) & 0xf;
+		off = offbase[bits];
+		bits = offbits[bits];
+
+		utnbits -= bits;
+		off |= (utbits >> utnbits) & ((1 << bits) - 1);
+		off++;
+
+		b = blocks;
+		while(off > b->maxoff){
+			off -= b->maxoff;
+			b++;
+			if(b >= eblocks)
+				return -1;
+		}
+		if(d + len > dmax
+		|| b != blocks && len > off)
+			return -1;
+		s = b->data + b->maxoff - off;
+		blocks->maxoff += len;
+
+		for(i = 0; i < len; i++)
+			d[i] = s[i];
+		d += len;
+	}
+	if(utnbits < overbits)
+		return -1;
+
+	len = d - blocks->data;
+	memmove(dst, blocks->data, len);
+
+	unthwackinsert(ut, len, seq);
+
+	return len;
+}