sys/src/cmd/ip/ppp/unthwack.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 enum
   9 {
  10         DMaxFastLen     = 7,
  11         DBigLenCode     = 0x3c,         /* minimum code for large lenth encoding */
  12         DBigLenBits     = 6,
  13         DBigLenBase     = 1             /* starting items to encode for big lens */
  14 };
  15
  16 static uchar lenval[1 << (DBigLenBits - 1)] =
  17 {
  18         0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  19         3, 3, 3, 3, 3, 3, 3, 3,
  20         4, 4, 4, 4,
  21         5,
  22         6,
  23         255,
  24         255
  25 };
  26
  27 static uchar lenbits[] =
  28 {
  29         0, 0, 0,
  30         2, 3, 5, 5,
  31 };
  32
  33 static uchar offbits[16] =
  34 {
  35         5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 13
  36 };
  37
  38 static ushort offbase[16] =
  39 {
  40         0, 0x20,
  41         0x40, 0x60,
  42         0x80, 0xc0,
  43         0x100, 0x180,
  44         0x200, 0x300,
  45         0x400, 0x600,
  46         0x800, 0xc00,
  47         0x1000,
  48         0x2000
  49 };
  50
  51 void
  52 unthwackinit(Unthwack *ut)
  53 {
  54         int i;
  55
  56         memset(ut, 0, sizeof *ut);
  57         for(i = 0; i < DWinBlocks; i++)
  58                 ut->blocks[i].data = ut->data[i];
  59 }
  60
  61 ulong
  62 unthwackstate(Unthwack *ut, uchar *mask)
  63 {
  64         ulong bseq, seq;
  65         int slot, m;
  66
  67         seq = ~0UL;
  68         m = 0;
  69         slot = ut->slot;
  70         for(;;){
  71                 slot--;
  72                 if(slot < 0)
  73                         slot += DWinBlocks;
  74                 if(slot == ut->slot)
  75                         break;
  76                 if(ut->blocks[slot].maxoff == 0)
  77                         continue;
  78                 bseq = ut->blocks[slot].seq;
  79                 if(seq == ~0UL)
  80                         seq = bseq;
  81                 else if(seq - bseq > MaxSeqMask)
  82                         break;
  83                 else
  84                         m |= 1 << (seq - bseq - 1);
  85         }
  86         *mask = m;
  87         return seq;
  88 }
  89
  90 /*
  91  * insert this block in it's correct sequence number order.
  92  * replace the oldest block, which is always pointed to by ut->slot.
  93  * the encoder doesn't use a history at wraparound,
  94  * so don't worry about that case.
  95  */
  96 static int
  97 unthwackinsert(Unthwack *ut, int len, ulong seq)
  98 {
  99         uchar *d;
 100         int slot, tslot;
 101
 102         tslot = ut->slot;
 103         for(;;){
 104                 slot = tslot - 1;
 105                 if(slot < 0)
 106                         slot += DWinBlocks;
 107                 if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0)
 108                         break;
 109                 d = ut->blocks[tslot].data;
 110                 ut->blocks[tslot] = ut->blocks[slot];
 111                 ut->blocks[slot].data = d;
 112                 tslot = slot;
 113         }
 114         ut->blocks[tslot].seq = seq;
 115         ut->blocks[tslot].maxoff = len;
 116
 117         ut->slot++;
 118         if(ut->slot >= DWinBlocks)
 119                 ut->slot = 0;
 120
 121         ut->blocks[ut->slot].seq = ~0UL;
 122         ut->blocks[ut->slot].maxoff = 0;
 123
 124         return tslot;
 125 }
 126
 127 int
 128 unthwackadd(Unthwack *ut, uchar *src, int nsrc, ulong seq)
 129 {
 130         int tslot;
 131
 132         if(nsrc > ThwMaxBlock)
 133                 return -1;
 134
 135         tslot = unthwackinsert(ut, nsrc, seq);
 136         if(tslot < 0)
 137                 return -1;
 138
 139         memmove(ut->blocks[tslot].data, src, nsrc);
 140
 141         return nsrc;
 142 }
 143
 144 int
 145 unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
 146 {
 147         UnthwBlock blocks[CompBlocks], *b, *eblocks;
 148         uchar *s, *d, *dmax, *smax, lit;
 149         ulong cmask, cseq, bseq, utbits;
 150         int i, off, len, bits, slot, use, code, utnbits, overbits, lithist;
 151
 152         if(nsrc < 4 || nsrc > ThwMaxBlock){
 153                 snprint(ut->err, ThwErrLen, "block too small or large");
 154                 return -1;
 155         }
 156
 157         slot = ut->slot;
 158         b = blocks;
 159         *b = ut->blocks[slot];
 160         d = b->data;
 161         dmax = d + ndst;
 162
 163         /*
 164          * set up the history blocks
 165          */
 166         cseq = seq - src[0];
 167         cmask = src[1];
 168         b++;
 169         while(cseq != seq && b < blocks + CompBlocks){
 170                 slot--;
 171                 if(slot < 0)
 172                         slot += DWinBlocks;
 173                 if(slot == ut->slot)
 174                         break;
 175                 bseq = ut->blocks[slot].seq;
 176                 if(bseq == cseq){
 177                         *b = ut->blocks[slot];
 178                         b++;
 179                         if(cmask == 0){
 180                                 cseq = seq;
 181                                 break;
 182                         }
 183                         do{
 184                                 bits = cmask & 1;
 185                                 cseq--;
 186                                 cmask >>= 1;
 187                         }while(!bits);
 188                 }
 189         }
 190         eblocks = b;
 191         if(cseq != seq){
 192                 snprint(ut->err, ThwErrLen, "blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n", seq, cseq, src[0], cmask, src[1]);
 193                 return -2;
 194         }
 195
 196         smax = src + nsrc;
 197         src += 2;
 198         utnbits = 0;
 199         utbits = 0;
 200         overbits = 0;
 201         lithist = ~0;
 202         while(src < smax || utnbits - overbits >= MinDecode){
 203                 while(utnbits <= 24){
 204                         utbits <<= 8;
 205                         if(src < smax)
 206                                 utbits |= *src++;
 207                         else
 208                                 overbits += 8;
 209                         utnbits += 8;
 210                 }
 211
 212                 /*
 213                  * literal
 214                  */
 215                 len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
 216                 if(len == 0){
 217                         if(lithist & 0xf){
 218                                 utnbits -= 9;
 219                                 lit = (utbits >> utnbits) & 0xff;
 220                                 lit &= 255;
 221                         }else{
 222                                 utnbits -= 8;
 223                                 lit = (utbits >> utnbits) & 0x7f;
 224                                 if(lit < 32){
 225                                         if(lit < 24){
 226                                                 utnbits -= 2;
 227                                                 lit = (lit << 2) | ((utbits >> utnbits) & 3);
 228                                         }else{
 229                                                 utnbits -= 3;
 230                                                 lit = (lit << 3) | ((utbits >> utnbits) & 7);
 231                                         }
 232                                         lit = (lit - 64) & 0xff;
 233                                 }
 234                         }
 235                         if(d >= dmax){
 236                                 snprint(ut->err, ThwErrLen, "too much output");
 237                                 return -1;
 238                         }
 239                         *d++ = lit;
 240                         lithist = (lithist << 1) | (lit < 32) | (lit > 127);
 241                         blocks->maxoff++;
 242                         continue;
 243                 }
 244
 245                 /*
 246                  * length
 247                  */
 248                 if(len < 255)
 249                         utnbits -= lenbits[len];
 250                 else{
 251                         utnbits -= DBigLenBits;
 252                         code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
 253                         len = DMaxFastLen;
 254                         use = DBigLenBase;
 255                         bits = (DBigLenBits & 1) ^ 1;
 256                         while(code >= use){
 257                                 len += use;
 258                                 code -= use;
 259                                 code <<= 1;
 260                                 utnbits--;
 261                                 if(utnbits < 0){
 262                                         snprint(ut->err, ThwErrLen, "len out of range");
 263                                         return -1;
 264                                 }
 265                                 code |= (utbits >> utnbits) & 1;
 266                                 use <<= bits;
 267                                 bits ^= 1;
 268                         }
 269                         len += code;
 270
 271                         while(utnbits <= 24){
 272                                 utbits <<= 8;
 273                                 if(src < smax)
 274                                         utbits |= *src++;
 275                                 else
 276                                         overbits += 8;
 277                                 utnbits += 8;
 278                         }
 279                 }
 280
 281                 /*
 282                  * offset
 283                  */
 284                 utnbits -= 4;
 285                 bits = (utbits >> utnbits) & 0xf;
 286                 off = offbase[bits];
 287                 bits = offbits[bits];
 288
 289                 utnbits -= bits;
 290                 off |= (utbits >> utnbits) & ((1 << bits) - 1);
 291                 off++;
 292
 293                 b = blocks;
 294                 while(off > b->maxoff){
 295                         off -= b->maxoff;
 296                         b++;
 297                         if(b >= eblocks){
 298                                 snprint(ut->err, ThwErrLen, "offset out of range");
 299                                 return -1;
 300                         }
 301                 }
 302                 if(d + len > dmax
 303                 || b != blocks && len > off){
 304                         snprint(ut->err, ThwErrLen, "len out of range");
 305                         return -1;
 306                 }
 307                 s = b->data + b->maxoff - off;
 308                 blocks->maxoff += len;
 309
 310                 for(i = 0; i < len; i++)
 311                         d[i] = s[i];
 312                 d += len;
 313         }
 314         if(utnbits < overbits){
 315                 snprint(ut->err, ThwErrLen, "compressed data overrun");
 316                 return -1;
 317         }
 318
 319         len = d - blocks->data;
 320         memmove(dst, blocks->data, len);
 321
 322         unthwackinsert(ut, len, seq);
 323
 324         return len;
 325 }