Subversion Repositories planix.SVN

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1 
#include <u.h>
2 
#include <libc.h>
3 
#include <ip.h>
4 
#include <auth.h>
5 
#include "ppp.h"
6 
#include "thwack.h"
7 
 
8 
typedef struct Huff	Huff;
9 
 
10 
enum
11 
{
12 
	MaxFastLen	= 9,
13 
	BigLenCode	= 0x1f4,	/* minimum code for large lenth encoding */
14 
	BigLenBits	= 9,
15 
	BigLenBase	= 4		/* starting items to encode for big lens */
16 
};
17 
 
18 
enum
19 
{
20 
	StatBytes,
21 
	StatOutBytes,
22 
	StatLits,
23 
	StatMatches,
24 
	StatOffBits,
25 
	StatLenBits,
26 
 
27 
	StatDelay,
28 
	StatHist,
29 
 
30 
	MaxStat
31 
};
32 
 
33 
struct Huff
34 
{
35 
	short	bits;				/* length of the code */
36 
	ulong	encode;				/* the code */
37 
};
38 
 
39 
static	Huff	lentab[MaxFastLen] =
40 
{
41 
	{2,	0x2},		/* 10 */
42 
	{3,	0x6},		/* 110 */
43 
	{5,	0x1c},		/* 11100 */
44 
	{5,	0x1d},		/* 11101 */
45 
	{6,	0x3c},		/* 111100 */
46 
	{7,	0x7a},		/* 1111010 */
47 
	{7,	0x7b},		/* 1111011 */
48 
	{8,	0xf8},		/* 11111000 */
49 
	{8,	0xf9},		/* 11111001 */
50 
};
51 
 
52 
void
53 
thwackinit(Thwack *tw)
54 
{
55 
	int i;
56 
 
57 
	qlock(&tw->acklock);
58 
	tw->slot = 0;
59 
	memset(tw->hash, 0, sizeof(tw->hash));
60 
	memset(tw->blocks, 0, sizeof(tw->blocks));
61 
	for(i = 0; i < EWinBlocks; i++){
62 
		tw->blocks[i].hash = tw->hash[i];
63 
		if(tw->data[i] != nil){
64 
			freeb(tw->data[i]);
65 
			tw->data[i] = nil;
66 
		}
67 
	}
68 
	qunlock(&tw->acklock);
69 
}
70 
 
71 
void
72 
thwackcleanup(Thwack *tw)
73 
{
74 
	int i;
75 
 
76 
	qlock(&tw->acklock);
77 
	for(i = 0; i < EWinBlocks; i++){
78 
		if(tw->data[i] != nil){
79 
			freeb(tw->data[i]);
80 
			tw->data[i] = nil;
81 
		}
82 
	}
83 
	qunlock(&tw->acklock);
84 
}
85 
 
86 
/*
87 
 * acknowledgement for block seq & nearby preds
88 
 */
89 
void
90 
thwackack(Thwack *tw, ulong seq, ulong mask)
91 
{
92 
	int slot, b;
93 
 
94 
	qlock(&tw->acklock);
95 
	slot = tw->slot;
96 
	for(;;){
97 
		slot--;
98 
		if(slot < 0)
99 
			slot += EWinBlocks;
100 
		if(slot == tw->slot)
101 
			break;
102 
		if(tw->blocks[slot].seq != seq)
103 
			continue;
104 
 
105 
		tw->blocks[slot].acked = 1;
106 
 
107 
		if(mask == 0)
108 
			break;
109 
		do{
110 
			b = mask & 1;
111 
			seq--;
112 
			mask >>= 1;
113 
		}while(!b);
114 
	}
115 
	qunlock(&tw->acklock);
116 
}
117 
 
118 
/*
119 
 * find a string in the dictionary
120 
 */
121 
static int
122 
thwmatch(ThwBlock *b, ThwBlock *eblocks, uchar **ss, uchar *esrc, ulong h)
123 
{
124 
	int then, toff, w, ok;
125 
	uchar *s, *t;
126 
 
127 
	s = *ss;
128 
	if(esrc < s + MinMatch)
129 
		return 0;
130 
 
131 
	toff = 0;
132 
	for(; b < eblocks; b++){
133 
		then = b->hash[(h ^ b->seq) & HashMask];
134 
		toff += b->maxoff;
135 
		w = (ushort)(then - b->begin);
136 
 
137 
		if(w >= b->maxoff)
138 
			continue;
139 
 
140 
 
141 
		/*
142 
		 * don't need to check for the end because
143 
		 * 1) s too close check above
144 
		 * 2) entries too close not added to hash tables
145 
		 */
146 
		t = w + b->data;
147 
		if(s[0] != t[0] || s[1] != t[1] || s[2] != t[2])
148 
			continue;
149 
		ok = b->edata - t;
150 
		if(esrc - s > ok)
151 
			esrc = s + ok;
152 
 
153 
		t += 3;
154 
		for(s += 3; s < esrc; s++){
155 
			if(*s != *t)
156 
				break;
157 
			t++;
158 
		}
159 
		*ss = s;
160 
		return toff - w;
161 
	}
162 
	return 0;
163 
}
164 
 
165 
/*
166 
 * knuth vol. 3 multiplicative hashing
167 
 * each byte x chosen according to rules
168 
 * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
169 
 * with reasonable spread between the bytes & their complements
170 
 *
171 
 * the 3 byte value appears to be as almost good as the 4 byte value,
172 
 * and might be faster on some machines
173 
 */
174 
/*
175 
#define hashit(c)	(((ulong)(c) * 0x6b43a9) >> (24 - HashLog))
176 
*/
177 
#define hashit(c)	((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog))
178 
 
179 
/*
180 
 * lz77 compression with single lookup in a hash table for each block
181 
 */
182 
int
183 
thwack(Thwack *tw, int mustadd, uchar *dst, int ndst, Block *bsrc, ulong seq, ulong stats[ThwStats])
184 
{
185 
	ThwBlock *eblocks, *b, blocks[CompBlocks];
186 
	uchar *s, *ss, *sss, *esrc, *half, *twdst, *twdmax;
187 
	ulong cont, cseq, bseq, cmask, code, twbits;
188 
	int n, now, toff, lithist, h, len, slot, bits, use, twnbits, lits, matches, offbits, lenbits, nhist;
189 
 
190 
	n = BLEN(bsrc);
191 
	if(n > ThwMaxBlock || n < MinMatch)
192 
		return -1;
193 
 
194 
	twdst = dst;
195 
	twdmax = dst + ndst;
196 
 
197 
	/*
198 
	 * add source to the coding window
199 
	 * there is always enough space
200 
	 */
201 
	qlock(&tw->acklock);
202 
	slot = tw->slot;
203 
	b = &tw->blocks[slot];
204 
	b->seq = seq;
205 
	b->acked = 0;
206 
	now = b->begin + b->maxoff;
207 
	if(tw->data[slot] != nil){
208 
		freeb(tw->data[slot]);
209 
		tw->data[slot] = nil;
210 
	}
211 
	s = bsrc->rptr;
212 
	b->data = s;
213 
	b->edata = s + n;
214 
	b->begin = now;
215 
	b->maxoff = n;
216 
 
217 
	/*
218 
	 * set up the history blocks
219 
	 */
220 
	cseq = seq;
221 
	cmask = 0;
222 
	*blocks = *b;
223 
	b = blocks;
224 
	b->maxoff = 0;
225 
	b++;
226 
	nhist = 0;
227 
	while(b < blocks + CompBlocks){
228 
		slot--;
229 
		if(slot < 0)
230 
			slot += EWinBlocks;
231 
		if(slot == tw->slot)
232 
			break;
233 
		if(tw->data[slot] == nil || !tw->blocks[slot].acked)
234 
			continue;
235 
		bseq = tw->blocks[slot].seq;
236 
		if(cseq == seq){
237 
			if(seq - bseq >= MaxSeqStart)
238 
				break;
239 
			cseq = bseq;
240 
		}else if(cseq - bseq > MaxSeqMask)
241 
			break;
242 
		else
243 
			cmask |= 1 << (cseq - bseq - 1);
244 
		*b = tw->blocks[slot];
245 
		nhist += b->maxoff;
246 
		b++;
247 
	}
248 
	qunlock(&tw->acklock);
249 
	eblocks = b;
250 
	*twdst++ = seq - cseq;
251 
	*twdst++ = cmask;
252 
 
253 
	cont = (s[0] << 16) | (s[1] << 8) | s[2];
254 
 
255 
	esrc = s + n;
256 
	half = s + (n >> 1);
257 
	twnbits = 0;
258 
	twbits = 0;
259 
	lits = 0;
260 
	matches = 0;
261 
	offbits = 0;
262 
	lenbits = 0;
263 
	lithist = ~0;
264 
	while(s < esrc){
265 
		h = hashit(cont);
266 
 
267 
		sss = s;
268 
		toff = thwmatch(blocks, eblocks, &sss, esrc, h);
269 
		ss = sss;
270 
 
271 
		len = ss - s;
272 
		for(; twnbits >= 8; twnbits -= 8){
273 
			if(twdst < twdmax)
274 
				*twdst++ = twbits >> (twnbits - 8);
275 
			else if(!mustadd)
276 
				return -1;
277 
		}
278 
		if(len < MinMatch){
279 
			toff = *s;
280 
			lithist = (lithist << 1) | (toff < 32) | (toff > 127);
281 
			if(lithist & 0x1e){
282 
				twbits = (twbits << 9) | toff;
283 
				twnbits += 9;
284 
			}else if(lithist & 1){
285 
				toff = (toff + 64) & 0xff;
286 
				if(toff < 96){
287 
					twbits = (twbits << 10) | toff;
288 
					twnbits += 10;
289 
				}else{
290 
					twbits = (twbits << 11) | toff;
291 
					twnbits += 11;
292 
				}
293 
			}else{
294 
				twbits = (twbits << 8) | toff;
295 
				twnbits += 8;
296 
			}
297 
			lits++;
298 
			blocks->maxoff++;
299 
 
300 
			/*
301 
			 * speed hack
302 
			 * check for compression progress, bail if none achieved
303 
			 */
304 
			if(s > half){
305 
				if(!mustadd && 4 * blocks->maxoff < 5 * lits)
306 
					return -1;
307 
				half = esrc;
308 
			}
309 
 
310 
			if(s + MinMatch <= esrc){
311 
				blocks->hash[(h ^ blocks->seq) & HashMask] = now;
312 
				if(s + MinMatch < esrc)
313 
					cont = (cont << 8) | s[MinMatch];
314 
			}
315 
			now++;
316 
			s++;
317 
			continue;
318 
		}
319 
 
320 
		blocks->maxoff += len;
321 
		matches++;
322 
 
323 
		/*
324 
		 * length of match
325 
		 */
326 
		len -= MinMatch;
327 
		if(len < MaxFastLen){
328 
			bits = lentab[len].bits;
329 
			twbits = (twbits << bits) | lentab[len].encode;
330 
			twnbits += bits;
331 
			lenbits += bits;
332 
		}else{
333 
			code = BigLenCode;
334 
			bits = BigLenBits;
335 
			use = BigLenBase;
336 
			len -= MaxFastLen;
337 
			while(len >= use){
338 
				len -= use;
339 
				code = (code + use) << 1;
340 
				use <<= (bits & 1) ^ 1;
341 
				bits++;
342 
			}
343 
			twbits = (twbits << bits) | (code + len);
344 
			twnbits += bits;
345 
			lenbits += bits;
346 
 
347 
			for(; twnbits >= 8; twnbits -= 8){
348 
				if(twdst < twdmax)
349 
					*twdst++ = twbits >> (twnbits - 8);
350 
				else if(!mustadd)
351 
					return -1;
352 
			}
353 
		}
354 
 
355 
		/*
356 
		 * offset in history
357 
		 */
358 
		toff--;
359 
		for(bits = OffBase; toff >= (1 << bits); bits++)
360 
			;
361 
		if(bits < MaxOff+OffBase-1){
362 
			twbits = (twbits << 3) | (bits - OffBase);
363 
			if(bits != OffBase)
364 
				bits--;
365 
			twnbits += bits + 3;
366 
			offbits += bits + 3;
367 
		}else{
368 
			twbits = (twbits << 4) | 0xe | (bits - (MaxOff+OffBase-1));
369 
			bits--;
370 
			twnbits += bits + 4;
371 
			offbits += bits + 4;
372 
		}
373 
		twbits = (twbits << bits) | toff & ((1 << bits) - 1);
374 
 
375 
		for(; s != ss; s++){
376 
			if(s + MinMatch <= esrc){
377 
				h = hashit(cont);
378 
				blocks->hash[(h ^ blocks->seq) & HashMask] = now;
379 
				if(s + MinMatch < esrc)
380 
					cont = (cont << 8) | s[MinMatch];
381 
			}
382 
			now++;
383 
		}
384 
	}
385 
 
386 
	if(twnbits & 7){
387 
		twbits <<= 8 - (twnbits & 7);
388 
		twnbits += 8 - (twnbits & 7);
389 
	}
390 
	for(; twnbits >= 8; twnbits -= 8){
391 
		if(twdst < twdmax)
392 
			*twdst++ = twbits >> (twnbits - 8);
393 
		else if(!mustadd)
394 
			return -1;
395 
	}
396 
 
397 
	if(twdst >= twdmax && !mustadd)
398 
		return -1;
399 
 
400 
	qlock(&tw->acklock);
401 
	tw->data[tw->slot] = bsrc;
402 
	tw->slot++;
403 
	if(tw->slot >= EWinBlocks)
404 
		tw->slot = 0;
405 
	qunlock(&tw->acklock);
406 
 
407 
	if(twdst >= twdmax)
408 
		return -1;
409 
 
410 
	stats[StatBytes] += blocks->maxoff;
411 
	stats[StatLits] += lits;
412 
	stats[StatMatches] += matches;
413 
	stats[StatOffBits] += offbits;
414 
	stats[StatLenBits] += lenbits;
415 
	stats[StatDelay] = stats[StatDelay]*7/8 + dst[0];
416 
	stats[StatHist] = stats[StatHist]*7/8 + nhist;
417 
	stats[StatOutBytes] += twdst - dst;
418 
 
419 
	return twdst - dst;
420 
}