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.1 1994/11/22 00:27:52 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 "slcompress.h"
  39
  40 #ifndef SL_NO_STATS
  41 #define INCR(counter) ++comp->counter;
  42 #else
  43 #define INCR(counter)
  44 #endif
  45
  46 #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n))
  47 #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n))
  48 #ifndef KERNEL
  49 #define ovbcopy bcopy
  50 #endif
  51
  52
  53 void
  54 sl_compress_init(comp)
  55         struct slcompress *comp;
  56 {
  57         register u_int i;
  58         register struct cstate *tstate = comp->tstate;
  59
  60         bzero((char *)comp, sizeof(*comp));
  61         for (i = MAX_STATES - 1; i > 0; --i) {
  62                 tstate[i].cs_id = i;
  63                 tstate[i].cs_next = &tstate[i - 1];
  64         }
  65         tstate[0].cs_next = &tstate[MAX_STATES - 1];
  66         tstate[0].cs_id = 0;
  67         comp->last_cs = &tstate[0];
  68         comp->last_recv = 255;
  69         comp->last_xmit = 255;
  70         comp->flags = SLF_TOSS;
  71 }
  72
  73
  74 /*
  75  * Like sl_compress_init, but we get to specify the maximum connection
  76  * ID to use on transmission.
  77  */
  78 void
  79 sl_compress_setup(comp, max_state)
  80         struct slcompress *comp;
  81         int max_state;
  82 {
  83         register u_int i;
  84         register struct cstate *tstate = comp->tstate;
  85
  86         if ((unsigned) max_state > MAX_STATES - 1)
  87                 max_state = MAX_STATES - 1;
  88         bzero((char *)comp, sizeof(*comp));
  89         for (i = max_state; i > 0; --i) {
  90                 tstate[i].cs_id = i;
  91                 tstate[i].cs_next = &tstate[i - 1];
  92         }
  93         tstate[0].cs_next = &tstate[max_state];
  94         tstate[0].cs_id = 0;
  95         comp->last_cs = &tstate[0];
  96         comp->last_recv = 255;
  97         comp->last_xmit = 255;
  98         comp->flags = SLF_TOSS;
  99 }
 100
 101
 102 /* ENCODE encodes a number that is known to be non-zero.  ENCODEZ
 103  * checks for zero (since zero has to be encoded in the long, 3 byte
 104  * form).
 105  */
 106 #define ENCODE(n) { \
 107         if ((u_short)(n) >= 256) { \
 108                 *cp++ = 0; \
 109                 cp[1] = (n); \
 110                 cp[0] = (n) >> 8; \
 111                 cp += 2; \
 112         } else { \
 113                 *cp++ = (n); \
 114         } \
 115 }
 116 #define ENCODEZ(n) { \
 117         if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
 118                 *cp++ = 0; \
 119                 cp[1] = (n); \
 120                 cp[0] = (n) >> 8; \
 121                 cp += 2; \
 122         } else { \
 123                 *cp++ = (n); \
 124         } \
 125 }
 126
 127 #define DECODEL(f) { \
 128         if (*cp == 0) {\
 129                 (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
 130                 cp += 3; \
 131         } else { \
 132                 (f) = htonl(ntohl(f) + (u_long)*cp++); \
 133         } \
 134 }
 135
 136 #define DECODES(f) { \
 137         if (*cp == 0) {\
 138                 (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
 139                 cp += 3; \
 140         } else { \
 141                 (f) = htons(ntohs(f) + (u_long)*cp++); \
 142         } \
 143 }
 144
 145 #define DECODEU(f) { \
 146         if (*cp == 0) {\
 147                 (f) = htons((cp[1] << 8) | cp[2]); \
 148                 cp += 3; \
 149         } else { \
 150                 (f) = htons((u_long)*cp++); \
 151         } \
 152 }
 153
 154
 155 u_char
 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         return sl_uncompress_tcp_part(bufp, len, len, type, comp);
 419 }
 420
 421
 422 /*
 423  * Uncompress a packet of total length total_len.  The first buflen
 424  * bytes are at *bufp; this must include the entire (compressed or
 425  * uncompressed) TCP/IP header.  In addition, there must be enough
 426  * clear space before *bufp to build a full-length TCP/IP header.
 427  */
 428 int
 429 sl_uncompress_tcp_part(bufp, buflen, total_len, type, comp)
 430         u_char **bufp;
 431         int buflen, total_len;
 432         u_int type;
 433         struct slcompress *comp;
 434 {
 435         register u_char *cp;
 436         register u_int hlen, changes;
 437         register struct tcphdr *th;
 438         register struct cstate *cs;
 439         register struct ip *ip;
 440
 441         switch (type) {
 442
 443         case TYPE_UNCOMPRESSED_TCP:
 444                 ip = (struct ip *) *bufp;
 445                 if (ip->ip_p >= MAX_STATES)
 446                         goto bad;
 447                 cs = &comp->rstate[comp->last_recv = ip->ip_p];
 448                 comp->flags &=~ SLF_TOSS;
 449                 ip->ip_p = IPPROTO_TCP;
 450                 hlen = ip->ip_hl;
 451                 hlen += ((struct tcphdr *)&((int *)ip)[hlen])->th_off;
 452                 hlen <<= 2;
 453                 BCOPY(ip, &cs->cs_ip, hlen);
 454                 cs->cs_ip.ip_sum = 0;
 455                 cs->cs_hlen = hlen;
 456                 INCR(sls_uncompressedin)
 457                 return (total_len);
 458
 459         default:
 460                 goto bad;
 461
 462         case TYPE_COMPRESSED_TCP:
 463                 break;
 464         }
 465         /* We've got a compressed packet. */
 466         INCR(sls_compressedin)
 467         cp = *bufp;
 468         changes = *cp++;
 469         if (changes & NEW_C) {
 470                 /* Make sure the state index is in range, then grab the state.
 471                  * If we have a good state index, clear the 'discard' flag. */
 472                 if (*cp >= MAX_STATES)
 473                         goto bad;
 474
 475                 comp->flags &=~ SLF_TOSS;
 476                 comp->last_recv = *cp++;
 477         } else {
 478                 /* this packet has an implicit state index.  If we've
 479                  * had a line error since the last time we got an
 480                  * explicit state index, we have to toss the packet. */
 481                 if (comp->flags & SLF_TOSS) {
 482                         INCR(sls_tossed)
 483                         return (0);
 484                 }
 485         }
 486         cs = &comp->rstate[comp->last_recv];
 487         hlen = cs->cs_ip.ip_hl << 2;
 488         th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen];
 489         th->th_sum = htons((*cp << 8) | cp[1]);
 490         cp += 2;
 491         if (changes & TCP_PUSH_BIT)
 492                 th->th_flags |= TH_PUSH;
 493         else
 494                 th->th_flags &=~ TH_PUSH;
 495
 496         switch (changes & SPECIALS_MASK) {
 497         case SPECIAL_I:
 498                 {
 499                 register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
 500                 th->th_ack = htonl(ntohl(th->th_ack) + i);
 501                 th->th_seq = htonl(ntohl(th->th_seq) + i);
 502                 }
 503                 break;
 504
 505         case SPECIAL_D:
 506                 th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
 507                                    - cs->cs_hlen);
 508                 break;
 509
 510         default:
 511                 if (changes & NEW_U) {
 512                         th->th_flags |= TH_URG;
 513                         DECODEU(th->th_urp)
 514                 } else
 515                         th->th_flags &=~ TH_URG;
 516                 if (changes & NEW_W)
 517                         DECODES(th->th_win)
 518                 if (changes & NEW_A)
 519                         DECODEL(th->th_ack)
 520                 if (changes & NEW_S)
 521                         DECODEL(th->th_seq)
 522                 break;
 523         }
 524         if (changes & NEW_I) {
 525                 DECODES(cs->cs_ip.ip_id)
 526         } else
 527                 cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
 528
 529         /*
 530          * At this point, cp points to the first byte of data in the
 531          * packet.  If we're not aligned on a 4-byte boundary, copy the
 532          * data down so the ip & tcp headers will be aligned.  Then back up
 533          * cp by the tcp/ip header length to make room for the reconstructed
 534          * header (we assume the packet we were handed has enough space to
 535          * prepend 128 bytes of header).  Adjust the length to account for
 536          * the new header & fill in the IP total length.
 537          */
 538         buflen -= (cp - *bufp);
 539         total_len -= (cp - *bufp);
 540         if (buflen < 0)
 541                 /* we must have dropped some characters (crc should detect
 542                  * this but the old slip framing won't) */
 543                 goto bad;
 544
 545         if ((int)cp & 3) {
 546                 if (buflen > 0)
 547                         (void) ovbcopy(cp, (caddr_t)((int)cp &~ 3), buflen);
 548                 cp = (u_char *)((int)cp &~ 3);
 549         }
 550         cp -= cs->cs_hlen;
 551         total_len += cs->cs_hlen;
 552         cs->cs_ip.ip_len = htons(total_len);
 553         BCOPY(&cs->cs_ip, cp, cs->cs_hlen);
 554         *bufp = cp;
 555
 556         /* recompute the ip header checksum */
 557         {
 558                 register u_short *bp = (u_short *)cp;
 559                 for (changes = 0; hlen > 0; hlen -= 2)
 560                         changes += *bp++;
 561                 changes = (changes & 0xffff) + (changes >> 16);
 562                 changes = (changes & 0xffff) + (changes >> 16);
 563                 ((struct ip *)cp)->ip_sum = ~ changes;
 564         }
 565         return (total_len);
 566 bad:
 567         comp->flags |= SLF_TOSS;
 568         INCR(sls_errorin)
 569         return (0);
 570 }