ultrix/slcompress.c

   1 /*
   2  * Routines to compress and uncompess tcp packets (for transmission
   3  * over low speed serial lines.
   4  *
   5  * Copyright (c) 1989 Regents of the University of California.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms are permitted
   9  * provided that the above copyright notice and this paragraph are
  10  * duplicated in all such forms and that any documentation,
  11  * advertising materials, and other materials related to such
  12  * distribution and use acknowledge that the software was developed
  13  * by the University of California, Berkeley.  The name of the
  14  * University may not be used to endorse or promote products derived
  15  * from this software without specific prior written permission.
  16  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  18  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  19  *
  20  *      Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
  21  *      - Initial distribution.
  22  *
  23  * Modified June 1993 by Paul Mackerras, paulus@cs.anu.edu.au,
  24  * so that the entire packet being decompressed doesn't have
  25  * to be in contiguous memory (just the compressed header).
  26  *
  27  * $Id: slcompress.c,v 1.2 1994/11/28 01:42:00 paulus Exp $
  28  */
  29
  30 #include "../h/types.h"
  31 #include "../h/param.h"
  32 #include "../h/mbuf.h"
  33 #include "../net/netinet/in.h"
  34 #include "../net/netinet/in_systm.h"
  35 #include "../net/netinet/ip.h"
  36 #include "../net/netinet/tcp.h"
  37
  38 #include "ppp_defs.h"
  39 #include "slcompress.h"
  40
  41 #ifndef SL_NO_STATS
  42 #define INCR(counter) ++comp->counter;
  43 #else
  44 #define INCR(counter)
  45 #endif
  46
  47 #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n))
  48 #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n))
  49 #ifndef KERNEL
  50 #define ovbcopy bcopy
  51 #endif
  52
  53
  54 void
  55 sl_compress_init(comp)
  56         struct slcompress *comp;
  57 {
  58         register u_int i;
  59         register struct cstate *tstate = comp->tstate;
  60
  61         bzero((char *)comp, sizeof(*comp));
  62         for (i = MAX_STATES - 1; i > 0; --i) {
  63                 tstate[i].cs_id = i;
  64                 tstate[i].cs_next = &tstate[i - 1];
  65         }
  66         tstate[0].cs_next = &tstate[MAX_STATES - 1];
  67         tstate[0].cs_id = 0;
  68         comp->last_cs = &tstate[0];
  69         comp->last_recv = 255;
  70         comp->last_xmit = 255;
  71         comp->flags = SLF_TOSS;
  72 }
  73
  74
  75 /*
  76  * Like sl_compress_init, but we get to specify the maximum connection
  77  * ID to use on transmission.
  78  */
  79 void
  80 sl_compress_setup(comp, max_state)
  81         struct slcompress *comp;
  82         int max_state;
  83 {
  84         register u_int i;
  85         register struct cstate *tstate = comp->tstate;
  86
  87         if ((unsigned) max_state > MAX_STATES - 1)
  88                 max_state = MAX_STATES - 1;
  89         bzero((char *)comp, sizeof(*comp));
  90         for (i = max_state; i > 0; --i) {
  91                 tstate[i].cs_id = i;
  92                 tstate[i].cs_next = &tstate[i - 1];
  93         }
  94         tstate[0].cs_next = &tstate[max_state];
  95         tstate[0].cs_id = 0;
  96         comp->last_cs = &tstate[0];
  97         comp->last_recv = 255;
  98         comp->last_xmit = 255;
  99         comp->flags = SLF_TOSS;
 100 }
 101
 102
 103 /* ENCODE encodes a number that is known to be non-zero.  ENCODEZ
 104  * checks for zero (since zero has to be encoded in the long, 3 byte
 105  * form).
 106  */
 107 #define ENCODE(n) { \
 108         if ((u_short)(n) >= 256) { \
 109                 *cp++ = 0; \
 110                 cp[1] = (n); \
 111                 cp[0] = (n) >> 8; \
 112                 cp += 2; \
 113         } else { \
 114                 *cp++ = (n); \
 115         } \
 116 }
 117 #define ENCODEZ(n) { \
 118         if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
 119                 *cp++ = 0; \
 120                 cp[1] = (n); \
 121                 cp[0] = (n) >> 8; \
 122                 cp += 2; \
 123         } else { \
 124                 *cp++ = (n); \
 125         } \
 126 }
 127
 128 #define DECODEL(f) { \
 129         if (*cp == 0) {\
 130                 (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
 131                 cp += 3; \
 132         } else { \
 133                 (f) = htonl(ntohl(f) + (u_long)*cp++); \
 134         } \
 135 }
 136
 137 #define DECODES(f) { \
 138         if (*cp == 0) {\
 139                 (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
 140                 cp += 3; \
 141         } else { \
 142                 (f) = htons(ntohs(f) + (u_long)*cp++); \
 143         } \
 144 }
 145
 146 #define DECODEU(f) { \
 147         if (*cp == 0) {\
 148                 (f) = htons((cp[1] << 8) | cp[2]); \
 149                 cp += 3; \
 150         } else { \
 151                 (f) = htons((u_long)*cp++); \
 152         } \
 153 }
 154
 155 u_int
 156 sl_compress_tcp(m, ip, comp, compress_cid)
 157         struct mbuf *m;
 158         register struct ip *ip;
 159         struct slcompress *comp;
 160         int compress_cid;
 161 {
 162         register struct cstate *cs = comp->last_cs->cs_next;
 163         register u_int hlen = ip->ip_hl;
 164         register struct tcphdr *oth;
 165         register struct tcphdr *th;
 166         register u_int deltaS, deltaA;
 167         register u_int changes = 0;
 168         u_char new_seq[16];
 169         register u_char *cp = new_seq;
 170
 171         /*
 172          * Bail if this is an IP fragment or if the TCP packet isn't
 173          * `compressible' (i.e., ACK isn't set or some other control bit is
 174          * set).  (We assume that the caller has already made sure the
 175          * packet is IP proto TCP).
 176          */
 177         if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40)
 178                 return (TYPE_IP);
 179
 180         th = (struct tcphdr *)&((int *)ip)[hlen];
 181         if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK)
 182                 return (TYPE_IP);
 183         /*
 184          * Packet is compressible -- we're going to send either a
 185          * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way we need
 186          * to locate (or create) the connection state.  Special case the
 187          * most recently used connection since it's most likely to be used
 188          * again & we don't have to do any reordering if it's used.
 189          */
 190         INCR(sls_packets)
 191         if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
 192             ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
 193             *(int *)th != ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl]) {
 194                 /*
 195                  * Wasn't the first -- search for it.
 196                  *
 197                  * States are kept in a circularly linked list with
 198                  * last_cs pointing to the end of the list.  The
 199                  * list is kept in lru order by moving a state to the
 200                  * head of the list whenever it is referenced.  Since
 201                  * the list is short and, empirically, the connection
 202                  * we want is almost always near the front, we locate
 203                  * states via linear search.  If we don't find a state
 204                  * for the datagram, the oldest state is (re-)used.
 205                  */
 206                 register struct cstate *lcs;
 207                 register struct cstate *lastcs = comp->last_cs;
 208
 209                 do {
 210                         lcs = cs; cs = cs->cs_next;
 211                         INCR(sls_searches)
 212                         if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr
 213                             && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr
 214                             && *(int *)th == ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl])
 215                                 goto found;
 216                 } while (cs != lastcs);
 217
 218                 /*
 219                  * Didn't find it -- re-use oldest cstate.  Send an
 220                  * uncompressed packet that tells the other side what
 221                  * connection number we're using for this conversation.
 222                  * Note that since the state list is circular, the oldest
 223                  * state points to the newest and we only need to set
 224                  * last_cs to update the lru linkage.
 225                  */
 226                 INCR(sls_misses)
 227                 comp->last_cs = lcs;
 228                 hlen += th->th_off;
 229                 hlen <<= 2;
 230                 if (hlen > m->m_len)
 231                         return (TYPE_IP);
 232                 goto uncompressed;
 233
 234         found:
 235                 /*
 236                  * Found it -- move to the front on the connection list.
 237                  */
 238                 if (cs == lastcs)
 239                         comp->last_cs = lcs;
 240                 else {
 241                         lcs->cs_next = cs->cs_next;
 242                         cs->cs_next = lastcs->cs_next;
 243                         lastcs->cs_next = cs;
 244                 }
 245         }
 246
 247         /*
 248          * Make sure that only what we expect to change changed. The first
 249          * line of the `if' checks the IP protocol version, header length &
 250          * type of service.  The 2nd line checks the "Don't fragment" bit.
 251          * The 3rd line checks the time-to-live and protocol (the protocol
 252          * check is unnecessary but costless).  The 4th line checks the TCP
 253          * header length.  The 5th line checks IP options, if any.  The 6th
 254          * line checks TCP options, if any.  If any of these things are
 255          * different between the previous & current datagram, we send the
 256          * current datagram `uncompressed'.
 257          */
 258         oth = (struct tcphdr *)&((int *)&cs->cs_ip)[hlen];
 259         deltaS = hlen;
 260         hlen += th->th_off;
 261         hlen <<= 2;
 262         if (hlen > m->m_len)
 263                 return (TYPE_IP);
 264
 265         if (((u_short *)ip)[0] != ((u_short *)&cs->cs_ip)[0] ||
 266             ((u_short *)ip)[3] != ((u_short *)&cs->cs_ip)[3] ||
 267             ((u_short *)ip)[4] != ((u_short *)&cs->cs_ip)[4] ||
 268             th->th_off != oth->th_off ||
 269             (deltaS > 5 &&
 270              BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
 271             (th->th_off > 5 &&
 272              BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))
 273                 goto uncompressed;
 274
 275         /*
 276          * Figure out which of the changing fields changed.  The
 277          * receiver expects changes in the order: urgent, window,
 278          * ack, seq (the order minimizes the number of temporaries
 279          * needed in this section of code).
 280          */
 281         if (th->th_flags & TH_URG) {
 282                 deltaS = ntohs(th->th_urp);
 283                 ENCODEZ(deltaS);
 284                 changes |= NEW_U;
 285         } else if (th->th_urp != oth->th_urp)
 286                 /* argh! URG not set but urp changed -- a sensible
 287                  * implementation should never do this but RFC793
 288                  * doesn't prohibit the change so we have to deal
 289                  * with it. */
 290                  goto uncompressed;
 291
 292         if (deltaS = (u_short)(ntohs(th->th_win) - ntohs(oth->th_win))) {
 293                 ENCODE(deltaS);
 294                 changes |= NEW_W;
 295         }
 296
 297         if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) {
 298                 if (deltaA > 0xffff)
 299                         goto uncompressed;
 300                 ENCODE(deltaA);
 301                 changes |= NEW_A;
 302         }
 303
 304         if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) {
 305                 if (deltaS > 0xffff)
 306                         goto uncompressed;
 307                 ENCODE(deltaS);
 308                 changes |= NEW_S;
 309         }
 310
 311         switch(changes) {
 312
 313         case 0:
 314                 /*
 315                  * Nothing changed. If this packet contains data and the
 316                  * last one didn't, this is probably a data packet following
 317                  * an ack (normal on an interactive connection) and we send
 318                  * it compressed.  Otherwise it's probably a retransmit,
 319                  * retransmitted ack or window probe.  Send it uncompressed
 320                  * in case the other side missed the compressed version.
 321                  */
 322                 if (ip->ip_len != cs->cs_ip.ip_len &&
 323                     ntohs(cs->cs_ip.ip_len) == hlen)
 324                         break;
 325
 326                 /* (fall through) */
 327
 328         case SPECIAL_I:
 329         case SPECIAL_D:
 330                 /*
 331                  * actual changes match one of our special case encodings --
 332                  * send packet uncompressed.
 333                  */
 334                 goto uncompressed;
 335
 336         case NEW_S|NEW_A:
 337                 if (deltaS == deltaA &&
 338                     deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
 339                         /* special case for echoed terminal traffic */
 340                         changes = SPECIAL_I;
 341                         cp = new_seq;
 342                 }
 343                 break;
 344
 345         case NEW_S:
 346                 if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
 347                         /* special case for data xfer */
 348                         changes = SPECIAL_D;
 349                         cp = new_seq;
 350                 }
 351                 break;
 352         }
 353
 354         deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
 355         if (deltaS != 1) {
 356                 ENCODEZ(deltaS);
 357                 changes |= NEW_I;
 358         }
 359         if (th->th_flags & TH_PUSH)
 360                 changes |= TCP_PUSH_BIT;
 361         /*
 362          * Grab the cksum before we overwrite it below.  Then update our
 363          * state with this packet's header.
 364          */
 365         deltaA = ntohs(th->th_sum);
 366         BCOPY(ip, &cs->cs_ip, hlen);
 367
 368         /*
 369          * We want to use the original packet as our compressed packet.
 370          * (cp - new_seq) is the number of bytes we need for compressed
 371          * sequence numbers.  In addition we need one byte for the change
 372          * mask, one for the connection id and two for the tcp checksum.
 373          * So, (cp - new_seq) + 4 bytes of header are needed.  hlen is how
 374          * many bytes of the original packet to toss so subtract the two to
 375          * get the new packet size.
 376          */
 377         deltaS = cp - new_seq;
 378         cp = (u_char *)ip;
 379         if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {
 380                 comp->last_xmit = cs->cs_id;
 381                 hlen -= deltaS + 4;
 382                 cp += hlen;
 383                 *cp++ = changes | NEW_C;
 384                 *cp++ = cs->cs_id;
 385         } else {
 386                 hlen -= deltaS + 3;
 387                 cp += hlen;
 388                 *cp++ = changes;
 389         }
 390         m->m_len -= hlen;
 391         m->m_off += hlen;
 392         *cp++ = deltaA >> 8;
 393         *cp++ = deltaA;
 394         BCOPY(new_seq, cp, deltaS);
 395         INCR(sls_compressed)
 396         return (TYPE_COMPRESSED_TCP);
 397
 398         /*
 399          * Update connection state cs & send uncompressed packet ('uncompressed'
 400          * means a regular ip/tcp packet but with the 'conversation id' we hope
 401          * to use on future compressed packets in the protocol field).
 402          */
 403 uncompressed:
 404         BCOPY(ip, &cs->cs_ip, hlen);
 405         ip->ip_p = cs->cs_id;
 406         comp->last_xmit = cs->cs_id;
 407         return (TYPE_UNCOMPRESSED_TCP);
 408 }
 409
 410
 411 int
 412 sl_uncompress_tcp(bufp, len, type, comp)
 413         u_char **bufp;
 414         int len;
 415         u_int type;
 416         struct slcompress *comp;
 417 {
 418         u_char *hdr, *cp;
 419         int hlen, vjlen;
 420
 421         cp = bufp? *bufp: NULL;
 422         vjlen = sl_uncompress_tcp_core(cp, len, len, type, comp, &hdr, &hlen);
 423         if (vjlen < 0)
 424                 return (0);     /* error */
 425         if (vjlen == 0)
 426                 return (len);   /* was uncompressed already */
 427
 428         cp += vjlen;
 429         len -= vjlen;
 430
 431         /*
 432          * At this point, cp points to the first byte of data in the
 433          * packet.  If we're not aligned on a 4-byte boundary, copy the
 434          * data down so the ip & tcp headers will be aligned.  Then back up
 435          * cp by the tcp/ip header length to make room for the reconstructed
 436          * header (we assume the packet we were handed has enough space to
 437          * prepend 128 bytes of header).
 438          */
 439         if ((int)cp & 3) {
 440                 if (len > 0)
 441                         (void) ovbcopy(cp, (caddr_t)((int)cp &~ 3), len);
 442                 cp = (u_char *)((int)cp &~ 3);
 443         }
 444         cp -= hlen;
 445         len += hlen;
 446         BCOPY(hdr, cp, hlen);
 447
 448         *bufp = cp;
 449         return (len);
 450 }
 451
 452 /*
 453  * Uncompress a packet of total length total_len.  The first buflen
 454  * bytes are at buf; this must include the entire (compressed or
 455  * uncompressed) TCP/IP header.  This procedure returns the length
 456  * of the VJ header, with a pointer to the uncompressed IP header
 457  * in *hdrp and its length in *hlenp.
 458  */
 459 int
 460 sl_uncompress_tcp_core(buf, buflen, total_len, type, comp, hdrp, hlenp)
 461         u_char *buf;
 462         int buflen, total_len;
 463         u_int type;
 464         struct slcompress *comp;
 465         u_char **hdrp;
 466         u_int *hlenp;
 467 {
 468         register u_char *cp;
 469         register u_int hlen, changes;
 470         register struct tcphdr *th;
 471         register struct cstate *cs;
 472         register struct ip *ip;
 473         register u_short *bp;
 474         register u_int vjlen;
 475
 476         switch (type) {
 477
 478         case TYPE_UNCOMPRESSED_TCP:
 479                 ip = (struct ip *) buf;
 480                 if (ip->ip_p >= MAX_STATES)
 481                         goto bad;
 482                 cs = &comp->rstate[comp->last_recv = ip->ip_p];
 483                 comp->flags &=~ SLF_TOSS;
 484                 ip->ip_p = IPPROTO_TCP;
 485                 hlen = ip->ip_hl;
 486                 hlen += ((struct tcphdr *)&((int *)ip)[hlen])->th_off;
 487                 hlen <<= 2;
 488                 BCOPY(ip, &cs->cs_ip, hlen);
 489                 cs->cs_hlen = hlen;
 490                 INCR(sls_uncompressedin)
 491                 *hdrp = (u_char *) &cs->cs_ip;
 492                 *hlenp = hlen;
 493                 return (0);
 494
 495         default:
 496                 goto bad;
 497
 498         case TYPE_COMPRESSED_TCP:
 499                 break;
 500         }
 501         /* We've got a compressed packet. */
 502         INCR(sls_compressedin)
 503         cp = buf;
 504         changes = *cp++;
 505         if (changes & NEW_C) {
 506                 /* Make sure the state index is in range, then grab the state.
 507                  * If we have a good state index, clear the 'discard' flag. */
 508                 if (*cp >= MAX_STATES)
 509                         goto bad;
 510
 511                 comp->flags &=~ SLF_TOSS;
 512                 comp->last_recv = *cp++;
 513         } else {
 514                 /* this packet has an implicit state index.  If we've
 515                  * had a line error since the last time we got an
 516                  * explicit state index, we have to toss the packet. */
 517                 if (comp->flags & SLF_TOSS) {
 518                         INCR(sls_tossed)
 519                         return (-1);
 520                 }
 521         }
 522         cs = &comp->rstate[comp->last_recv];
 523         hlen = cs->cs_ip.ip_hl << 2;
 524         th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen];
 525         th->th_sum = htons((*cp << 8) | cp[1]);
 526         cp += 2;
 527         if (changes & TCP_PUSH_BIT)
 528                 th->th_flags |= TH_PUSH;
 529         else
 530                 th->th_flags &=~ TH_PUSH;
 531
 532         switch (changes & SPECIALS_MASK) {
 533         case SPECIAL_I:
 534                 {
 535                 register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
 536                 th->th_ack = htonl(ntohl(th->th_ack) + i);
 537                 th->th_seq = htonl(ntohl(th->th_seq) + i);
 538                 }
 539                 break;
 540
 541         case SPECIAL_D:
 542                 th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
 543                                    - cs->cs_hlen);
 544                 break;
 545
 546         default:
 547                 if (changes & NEW_U) {
 548                         th->th_flags |= TH_URG;
 549                         DECODEU(th->th_urp)
 550                 } else
 551                         th->th_flags &=~ TH_URG;
 552                 if (changes & NEW_W)
 553                         DECODES(th->th_win)
 554                 if (changes & NEW_A)
 555                         DECODEL(th->th_ack)
 556                 if (changes & NEW_S)
 557                         DECODEL(th->th_seq)
 558                 break;
 559         }
 560         if (changes & NEW_I) {
 561                 DECODES(cs->cs_ip.ip_id)
 562         } else
 563                 cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
 564
 565         /*
 566          * At this point, cp points to the first byte of data in the
 567          * packet.  Fill in the IP total length and update the IP
 568          * header checksum.
 569          */
 570         vjlen = cp - buf;
 571         buflen -= vjlen;
 572         if (buflen < 0)
 573                 /* we must have dropped some characters (crc should detect
 574                  * this but the old slip framing won't) */
 575                 goto bad;
 576
 577         total_len += cs->cs_hlen - vjlen;
 578         cs->cs_ip.ip_len = htons(total_len);
 579
 580         /* recompute the ip header checksum */
 581         bp = (u_short *) &cs->cs_ip;
 582         cs->cs_ip.ip_sum = 0;
 583         for (changes = 0; hlen > 0; hlen -= 2)
 584                 changes += *bp++;
 585         changes = (changes & 0xffff) + (changes >> 16);
 586         changes = (changes & 0xffff) + (changes >> 16);
 587         cs->cs_ip.ip_sum = ~ changes;
 588
 589         *hdrp = (u_char *) &cs->cs_ip;
 590         *hlenp = cs->cs_hlen;
 591         return vjlen;
 592
 593 bad:
 594         comp->flags |= SLF_TOSS;
 595         INCR(sls_errorin)
 596         return (-1);
 597 }