sys/src/cmd/ip/ppp/thwack.c

   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 }