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
thwackinit(Thwack * tw)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
thwackcleanup(Thwack * tw)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
thwackack(Thwack * tw,ulong seq,ulong mask)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
thwmatch(ThwBlock * b,ThwBlock * eblocks,uchar ** ss,uchar * esrc,ulong h)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
thwack(Thwack * tw,int mustadd,uchar * dst,int ndst,Block * bsrc,ulong seq,ulong stats[ThwStats])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 }
421