Import sources from 2011-03-30 iso image

1 files changed, 381 insertions, 0 deletions

diff --git a/sys/src/9/port/thwack.c b/sys/src/9/port/thwack.c
new file mode 100755
index 000000000..2b48de671
--- /dev/null
+++ b/sys/src/9/port/thwack.c
@@ -0,0 +1,381 @@
+#include "u.h"
+#include "lib.h"
+#include "mem.h"
+#include "dat.h"
+#include "fns.h"
+
+#include "thwack.h"
+
+typedef struct Huff	Huff;
+
+enum
+{
+	MaxFastLen	= 9,
+	BigLenCode	= 0x1f4,	/* minimum code for large lenth encoding */
+	BigLenBits	= 9,
+	BigLenBase	= 4		/* starting items to encode for big lens */
+};
+
+enum
+{
+	StatBytes,
+	StatOutBytes,
+	StatLits,
+	StatMatches,
+	StatOffBits,
+	StatLenBits,
+
+	StatDelay,
+	StatHist,
+
+	MaxStat
+};
+
+struct Huff
+{
+	short	bits;				/* length of the code */
+	ulong	encode;				/* the code */
+};
+
+static	Huff	lentab[MaxFastLen] =
+{
+	{2,	0x2},		/* 10 */
+	{3,	0x6},		/* 110 */
+	{5,	0x1c},		/* 11100 */
+	{5,	0x1d},		/* 11101 */
+	{6,	0x3c},		/* 111100 */
+	{7,	0x7a},		/* 1111010 */
+	{7,	0x7b},		/* 1111011 */
+	{8,	0xf8},		/* 11111000 */
+	{8,	0xf9},		/* 11111001 */
+};
+
+void
+thwackinit(Thwack *tw)
+{
+	int i;
+
+	memset(tw, 0, sizeof *tw);
+	for(i = 0; i < EWinBlocks; i++){
+		tw->blocks[i].data = tw->data[i];
+		tw->blocks[i].edata = tw->blocks[i].data;
+		tw->blocks[i].hash = tw->hash[i];
+		tw->blocks[i].acked = 0;
+	}
+}
+
+/*
+ * acknowledgement for block seq & nearby preds
+ */
+void
+thwackack(Thwack *tw, ulong seq, ulong mask)
+{
+	int slot, b;
+
+	slot = tw->slot;
+	for(;;){
+		slot--;
+		if(slot < 0)
+			slot += EWinBlocks;
+		if(slot == tw->slot)
+			break;
+		if(tw->blocks[slot].seq != seq)
+			continue;
+
+		tw->blocks[slot].acked = 1;
+
+		if(mask == 0)
+			break;
+		do{
+			b = mask & 1;
+			seq--;
+			mask >>= 1;
+		}while(!b);
+	}
+}
+
+/*
+ * find a string in the dictionary
+ */
+static int
+thwmatch(ThwBlock *b, ThwBlock *eblocks, uchar **ss, uchar *esrc, ulong h)
+{
+	int then, toff, w, ok;
+	uchar *s, *t;
+
+	s = *ss;
+	if(esrc < s + MinMatch)
+		return 0;
+
+	toff = 0;
+	for(; b < eblocks; b++){
+		then = b->hash[(h ^ b->seq) & HashMask];
+		toff += b->maxoff;
+		w = (ushort)(then - b->begin);
+
+		if(w >= b->maxoff)
+			continue;
+
+
+		/*
+		 * don't need to check for the end because
+		 * 1) s too close check above
+		 * 2) entries too close not added to hash tables
+		 */
+		t = w + b->data;
+		if(s[0] != t[0] || s[1] != t[1] || s[2] != t[2])
+			continue;
+		ok = b->edata - t;
+		if(esrc - s > ok)
+			esrc = s + ok;
+
+		t += 3;
+		for(s += 3; s < esrc; s++){
+			if(*s != *t)
+				break;
+			t++;
+		}
+		*ss = s;
+		return toff - w;
+	}
+	return 0;
+}
+
+/*
+ * knuth vol. 3 multiplicative hashing
+ * each byte x chosen according to rules
+ * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
+ * with reasonable spread between the bytes & their complements
+ *
+ * the 3 byte value appears to be as almost good as the 4 byte value,
+ * and might be faster on some machines
+ */
+/*
+#define hashit(c)	(((ulong)(c) * 0x6b43a9) >> (24 - HashLog))
+*/
+#define hashit(c)	((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog))
+
+/*
+ * lz77 compression with single lookup in a hash table for each block
+ */
+int
+thwack(Thwack *tw, uchar *dst, uchar *src, int n, ulong seq, ulong stats[ThwStats])
+{
+	ThwBlock *eblocks, *b, blocks[CompBlocks];
+	uchar *s, *ss, *sss, *esrc, *half, *twdst, *twdmax;
+	ulong cont, cseq, bseq, cmask, code, twbits;
+	int now, toff, lithist, h, len, slot, bits, use, twnbits, lits, matches, offbits, lenbits, nhist;
+
+	if(n > ThwMaxBlock || n < MinMatch)
+		return -1;
+
+	twdst = dst;
+	twdmax = dst + n;
+
+	/*
+	 * add source to the coding window
+	 * there is always enough space
+	 */
+	slot = tw->slot;
+	b = &tw->blocks[slot];
+	b->seq = seq;
+	b->acked = 0;
+	now = b->begin + b->maxoff;
+	s = b->data;
+	memmove(s, src, n);
+	b->edata = s + n;
+	b->begin = now;
+	b->maxoff = n;
+
+	/*
+	 * set up the history blocks
+	 */
+	cseq = seq;
+	cmask = 0;
+	*blocks = *b;
+	b = blocks;
+	b->maxoff = 0;
+	b++;
+	nhist = 0;
+	while(b < blocks + CompBlocks){
+		slot--;
+		if(slot < 0)
+			slot += EWinBlocks;
+		if(slot == tw->slot)
+			break;
+		if(!tw->blocks[slot].acked)
+			continue;
+		bseq = tw->blocks[slot].seq;
+		if(cseq == seq){
+			if(seq - bseq >= MaxSeqStart)
+				break;
+			cseq = bseq;
+		}else if(cseq - bseq > MaxSeqMask)
+			break;
+		else
+			cmask |= 1 << (cseq - bseq - 1);
+		*b = tw->blocks[slot];
+		nhist += b->maxoff;
+		b++;
+	}
+	eblocks = b;
+	*twdst++ = seq - cseq;
+	*twdst++ = cmask;
+
+	cont = (s[0] << 16) | (s[1] << 8) | s[2];
+
+	esrc = s + n;
+	half = s + (n >> 1);
+	twnbits = 0;
+	twbits = 0;
+	lits = 0;
+	matches = 0;
+	offbits = 0;
+	lenbits = 0;
+	lithist = ~0;
+	while(s < esrc){
+		h = hashit(cont);
+
+		sss = s;
+		toff = thwmatch(blocks, eblocks, &sss, esrc, h);
+		ss = sss;
+
+		len = ss - s;
+		for(; twnbits >= 8; twnbits -= 8){
+			if(twdst >= twdmax)
+				return -1;
+			*twdst++ = twbits >> (twnbits - 8);
+		}
+		if(len < MinMatch){
+			toff = *s;
+			lithist = (lithist << 1) | (toff < 32) | (toff > 127);
+			if(lithist & 0x1e){
+				twbits = (twbits << 9) | toff;
+				twnbits += 9;
+			}else if(lithist & 1){
+				toff = (toff + 64) & 0xff;
+				if(toff < 96){
+					twbits = (twbits << 10) | toff;
+					twnbits += 10;
+				}else{
+					twbits = (twbits << 11) | toff;
+					twnbits += 11;
+				}
+			}else{
+				twbits = (twbits << 8) | toff;
+				twnbits += 8;
+			}
+			lits++;
+			blocks->maxoff++;
+
+			/*
+			 * speed hack
+			 * check for compression progress, bail if none achieved
+			 */
+			if(s > half){
+				if(4 * blocks->maxoff < 5 * lits)
+					return -1;
+				half = esrc;
+			}
+
+			if(s + MinMatch <= esrc){
+				blocks->hash[(h ^ blocks->seq) & HashMask] = now;
+				if(s + MinMatch < esrc)
+					cont = (cont << 8) | s[MinMatch];
+			}
+			now++;
+			s++;
+			continue;
+		}
+
+		blocks->maxoff += len;
+		matches++;
+
+		/*
+		 * length of match
+		 */
+		len -= MinMatch;
+		if(len < MaxFastLen){
+			bits = lentab[len].bits;
+			twbits = (twbits << bits) | lentab[len].encode;
+			twnbits += bits;
+			lenbits += bits;
+		}else{
+			code = BigLenCode;
+			bits = BigLenBits;
+			use = BigLenBase;
+			len -= MaxFastLen;
+			while(len >= use){
+				len -= use;
+				code = (code + use) << 1;
+				use <<= (bits & 1) ^ 1;
+				bits++;
+			}
+			twbits = (twbits << bits) | (code + len);
+			twnbits += bits;
+			lenbits += bits;
+
+			for(; twnbits >= 8; twnbits -= 8){
+				if(twdst >= twdmax)
+					return -1;
+				*twdst++ = twbits >> (twnbits - 8);
+			}
+		}
+
+		/*
+		 * offset in history
+		 */
+		toff--;
+		for(bits = OffBase; toff >= (1 << bits); bits++)
+			;
+		if(bits < MaxOff+OffBase-1){
+			twbits = (twbits << 3) | (bits - OffBase);
+			if(bits != OffBase)
+				bits--;
+			twnbits += bits + 3;
+			offbits += bits + 3;
+		}else{
+			twbits = (twbits << 4) | 0xe | (bits - (MaxOff+OffBase-1));
+			bits--;
+			twnbits += bits + 4;
+			offbits += bits + 4;
+		}
+		twbits = (twbits << bits) | toff & ((1 << bits) - 1);
+
+		for(; s != ss; s++){
+			if(s + MinMatch <= esrc){
+				h = hashit(cont);
+				blocks->hash[(h ^ blocks->seq) & HashMask] = now;
+				if(s + MinMatch < esrc)
+					cont = (cont << 8) | s[MinMatch];
+			}
+			now++;
+		}
+	}
+
+
+	if(twnbits & 7){
+		twbits <<= 8 - (twnbits & 7);
+		twnbits += 8 - (twnbits & 7);
+	}
+	for(; twnbits >= 8; twnbits -= 8){
+		if(twdst >= twdmax)
+			return -1;
+		*twdst++ = twbits >> (twnbits - 8);
+	}
+
+	tw->slot++;
+	if(tw->slot >= EWinBlocks)
+		tw->slot = 0;
+
+	stats[StatBytes] += blocks->maxoff;
+	stats[StatLits] += lits;
+	stats[StatMatches] += matches;
+	stats[StatOffBits] += offbits;
+	stats[StatLenBits] += lenbits;
+	stats[StatDelay] = stats[StatDelay]*7/8 + dst[0];
+	stats[StatHist] = stats[StatHist]*7/8 + nhist;
+	stats[StatOutBytes] += twdst - dst;
+
+	return twdst - dst;
+}