modules/vjcompress.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: vjcompress.c,v 1.1 1994/09/16 06:58:24 paulus Exp $
  28  */
  29
  30 #include <sys/types.h>
  31 #include <sys/param.h>
  32 #include <netinet/in.h>
  33 #include <netinet/in_systm.h>
  34 #include <netinet/ip.h>
  35 #include <netinet/tcp.h>
  36
  37 #ifdef __STDC__
  38 #define __P(x)  x
  39 #else
  40 #define __P()   ()
  41 #endif
  42
  43 #include <net/vjcompress.h>
  44
  45 #ifndef VJ_NO_STATS
  46 #define INCR(counter) ++comp->counter
  47 #else
  48 #define INCR(counter)
  49 #endif
  50
  51 #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n))
  52 #undef  BCOPY
  53 #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n))
  54 #ifndef KERNEL
  55 #define ovbcopy bcopy
  56 #endif
  57
  58 void
  59 vj_compress_init(comp, max_state)
  60     struct vjcompress *comp;
  61     int max_state;
  62 {
  63     register u_int i;
  64     register struct cstate *tstate = comp->tstate;
  65
  66     if (max_state == -1)
  67         max_state = MAX_STATES - 1;
  68     bzero((char *)comp, sizeof(*comp));
  69     for (i = max_state; i > 0; --i) {
  70         tstate[i].cs_id = i;
  71         tstate[i].cs_next = &tstate[i - 1];
  72     }
  73     tstate[0].cs_next = &tstate[max_state];
  74     tstate[0].cs_id = 0;
  75     comp->last_cs = &tstate[0];
  76     comp->last_recv = 255;
  77     comp->last_xmit = 255;
  78     comp->flags = VJF_TOSS;
  79 }
  80
  81
  82 /* ENCODE encodes a number that is known to be non-zero.  ENCODEZ
  83  * checks for zero (since zero has to be encoded in the long, 3 byte
  84  * form).
  85  */
  86 #define ENCODE(n) { \
  87         if ((u_short)(n) >= 256) { \
  88                 *cp++ = 0; \
  89                 cp[1] = (n); \
  90                 cp[0] = (n) >> 8; \
  91                 cp += 2; \
  92         } else { \
  93                 *cp++ = (n); \
  94         } \
  95 }
  96 #define ENCODEZ(n) { \
  97         if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
  98                 *cp++ = 0; \
  99                 cp[1] = (n); \
 100                 cp[0] = (n) >> 8; \
 101                 cp += 2; \
 102         } else { \
 103                 *cp++ = (n); \
 104         } \
 105 }
 106
 107 #define DECODEL(f) { \
 108         if (*cp == 0) {\
 109                 (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
 110                 cp += 3; \
 111         } else { \
 112                 (f) = htonl(ntohl(f) + (u_long)*cp++); \
 113         } \
 114 }
 115
 116 #define DECODES(f) { \
 117         if (*cp == 0) {\
 118                 (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
 119                 cp += 3; \
 120         } else { \
 121                 (f) = htons(ntohs(f) + (u_long)*cp++); \
 122         } \
 123 }
 124
 125 #define DECODEU(f) { \
 126         if (*cp == 0) {\
 127                 (f) = htons((cp[1] << 8) | cp[2]); \
 128                 cp += 3; \
 129         } else { \
 130                 (f) = htons((u_long)*cp++); \
 131         } \
 132 }
 133
 134 u_int
 135 vj_compress_tcp(ip, mlen, comp, compress_cid, vjhdrp)
 136     register struct ip *ip;
 137     u_int mlen;
 138     struct vjcompress *comp;
 139     int compress_cid;
 140     u_char **vjhdrp;
 141 {
 142     register struct cstate *cs = comp->last_cs->cs_next;
 143     register u_int hlen = ip->ip_hl;
 144     register struct tcphdr *oth;
 145     register struct tcphdr *th;
 146     register u_int deltaS, deltaA;
 147     register u_int changes = 0;
 148     u_char new_seq[16];
 149     register u_char *cp = new_seq;
 150
 151     /*
 152      * Bail if this is an IP fragment or if the TCP packet isn't
 153      * `compressible' (i.e., ACK isn't set or some other control bit is
 154      * set).  (We assume that the caller has already made sure the
 155      * packet is IP proto TCP).
 156      */
 157     if ((ip->ip_off & htons(0x3fff)) || mlen < 40)
 158         return (TYPE_IP);
 159
 160     th = (struct tcphdr *)&((int *)ip)[hlen];
 161     if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK)
 162         return (TYPE_IP);
 163     /*
 164      * Packet is compressible -- we're going to send either a
 165      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way we need
 166      * to locate (or create) the connection state.  Special case the
 167      * most recently used connection since it's most likely to be used
 168      * again & we don't have to do any reordering if it's used.
 169      */
 170     INCR(vjs_packets);
 171     if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
 172         ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
 173         *(int *)th != ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl]) {
 174         /*
 175          * Wasn't the first -- search for it.
 176          *
 177          * States are kept in a circularly linked list with
 178          * last_cs pointing to the end of the list.  The
 179          * list is kept in lru order by moving a state to the
 180          * head of the list whenever it is referenced.  Since
 181          * the list is short and, empirically, the connection
 182          * we want is almost always near the front, we locate
 183          * states via linear search.  If we don't find a state
 184          * for the datagram, the oldest state is (re-)used.
 185          */
 186         register struct cstate *lcs;
 187         register struct cstate *lastcs = comp->last_cs;
 188
 189         do {
 190             lcs = cs; cs = cs->cs_next;
 191             INCR(vjs_searches);
 192             if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr
 193                 && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr
 194                 && *(int *)th == ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl])
 195                 goto found;
 196         } while (cs != lastcs);
 197
 198         /*
 199          * Didn't find it -- re-use oldest cstate.  Send an
 200          * uncompressed packet that tells the other side what
 201          * connection number we're using for this conversation.
 202          * Note that since the state list is circular, the oldest
 203          * state points to the newest and we only need to set
 204          * last_cs to update the lru linkage.
 205          */
 206         INCR(vjs_misses);
 207         comp->last_cs = lcs;
 208         hlen += th->th_off;
 209         hlen <<= 2;
 210         if (hlen > mlen)
 211             return (TYPE_IP);
 212         goto uncompressed;
 213
 214     found:
 215         /*
 216          * Found it -- move to the front on the connection list.
 217          */
 218         if (cs == lastcs)
 219             comp->last_cs = lcs;
 220         else {
 221             lcs->cs_next = cs->cs_next;
 222             cs->cs_next = lastcs->cs_next;
 223             lastcs->cs_next = cs;
 224         }
 225     }
 226
 227     /*
 228      * Make sure that only what we expect to change changed. The first
 229      * line of the `if' checks the IP protocol version, header length &
 230      * type of service.  The 2nd line checks the "Don't fragment" bit.
 231      * The 3rd line checks the time-to-live and protocol (the protocol
 232      * check is unnecessary but costless).  The 4th line checks the TCP
 233      * header length.  The 5th line checks IP options, if any.  The 6th
 234      * line checks TCP options, if any.  If any of these things are
 235      * different between the previous & current datagram, we send the
 236      * current datagram `uncompressed'.
 237      */
 238     oth = (struct tcphdr *)&((int *)&cs->cs_ip)[hlen];
 239     deltaS = hlen;
 240     hlen += th->th_off;
 241     hlen <<= 2;
 242     if (hlen > mlen)
 243         return (TYPE_IP);
 244
 245     if (((u_short *)ip)[0] != ((u_short *)&cs->cs_ip)[0] ||
 246         ((u_short *)ip)[3] != ((u_short *)&cs->cs_ip)[3] ||
 247         ((u_short *)ip)[4] != ((u_short *)&cs->cs_ip)[4] ||
 248         th->th_off != oth->th_off ||
 249         (deltaS > 5 && BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
 250         (th->th_off > 5 && BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))
 251         goto uncompressed;
 252
 253     /*
 254      * Figure out which of the changing fields changed.  The
 255      * receiver expects changes in the order: urgent, window,
 256      * ack, seq (the order minimizes the number of temporaries
 257      * needed in this section of code).
 258      */
 259     if (th->th_flags & TH_URG) {
 260         deltaS = ntohs(th->th_urp);
 261         ENCODEZ(deltaS);
 262         changes |= NEW_U;
 263     } else if (th->th_urp != oth->th_urp)
 264         /* argh! URG not set but urp changed -- a sensible
 265          * implementation should never do this but RFC793
 266          * doesn't prohibit the change so we have to deal
 267          * with it. */
 268         goto uncompressed;
 269
 270     if (deltaS = (u_short)(ntohs(th->th_win) - ntohs(oth->th_win))) {
 271         ENCODE(deltaS);
 272         changes |= NEW_W;
 273     }
 274
 275     if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) {
 276         if (deltaA > 0xffff)
 277             goto uncompressed;
 278         ENCODE(deltaA);
 279         changes |= NEW_A;
 280     }
 281
 282     if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) {
 283         if (deltaS > 0xffff)
 284             goto uncompressed;
 285         ENCODE(deltaS);
 286         changes |= NEW_S;
 287     }
 288
 289     switch(changes) {
 290
 291     case 0:
 292         /*
 293          * Nothing changed. If this packet contains data and the
 294          * last one didn't, this is probably a data packet following
 295          * an ack (normal on an interactive connection) and we send
 296          * it compressed.  Otherwise it's probably a retransmit,
 297          * retransmitted ack or window probe.  Send it uncompressed
 298          * in case the other side missed the compressed version.
 299          */
 300         if (ip->ip_len != cs->cs_ip.ip_len &&
 301             ntohs(cs->cs_ip.ip_len) == hlen)
 302             break;
 303
 304         /* (fall through) */
 305
 306     case SPECIAL_I:
 307     case SPECIAL_D:
 308         /*
 309          * actual changes match one of our special case encodings --
 310          * send packet uncompressed.
 311          */
 312         goto uncompressed;
 313
 314     case NEW_S|NEW_A:
 315         if (deltaS == deltaA && deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
 316             /* special case for echoed terminal traffic */
 317             changes = SPECIAL_I;
 318             cp = new_seq;
 319         }
 320         break;
 321
 322     case NEW_S:
 323         if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
 324             /* special case for data xfer */
 325             changes = SPECIAL_D;
 326             cp = new_seq;
 327         }
 328         break;
 329     }
 330
 331     deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
 332     if (deltaS != 1) {
 333         ENCODEZ(deltaS);
 334         changes |= NEW_I;
 335     }
 336     if (th->th_flags & TH_PUSH)
 337         changes |= TCP_PUSH_BIT;
 338     /*
 339      * Grab the cksum before we overwrite it below.  Then update our
 340      * state with this packet's header.
 341      */
 342     deltaA = ntohs(th->th_sum);
 343     BCOPY(ip, &cs->cs_ip, hlen);
 344
 345     /*
 346      * We want to use the original packet as our compressed packet.
 347      * (cp - new_seq) is the number of bytes we need for compressed
 348      * sequence numbers.  In addition we need one byte for the change
 349      * mask, one for the connection id and two for the tcp checksum.
 350      * So, (cp - new_seq) + 4 bytes of header are needed.  hlen is how
 351      * many bytes of the original packet to toss so subtract the two to
 352      * get the new packet size.
 353      */
 354     deltaS = cp - new_seq;
 355     cp = (u_char *)ip;
 356     if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {
 357         comp->last_xmit = cs->cs_id;
 358         hlen -= deltaS + 4;
 359         *vjhdrp = (cp += hlen);
 360         *cp++ = changes | NEW_C;
 361         *cp++ = cs->cs_id;
 362     } else {
 363         hlen -= deltaS + 3;
 364         *vjhdrp = (cp += hlen);
 365         *cp++ = changes;
 366     }
 367     *cp++ = deltaA >> 8;
 368     *cp++ = deltaA;
 369     BCOPY(new_seq, cp, deltaS);
 370     INCR(vjs_compressed);
 371     return (TYPE_COMPRESSED_TCP);
 372
 373     /*
 374      * Update connection state cs & send uncompressed packet (that is,
 375      * a regular ip/tcp packet but with the 'conversation id' we hope
 376      * to use on future compressed packets in the protocol field).
 377      */
 378  uncompressed:
 379     BCOPY(ip, &cs->cs_ip, hlen);
 380     ip->ip_p = cs->cs_id;
 381     comp->last_xmit = cs->cs_id;
 382     return (TYPE_UNCOMPRESSED_TCP);
 383 }
 384
 385 /*
 386  * Called when we may have missed a packet.
 387  */
 388 void
 389 vj_uncompress_err(comp)
 390     struct vjcompress *comp;
 391 {
 392     comp->flags |= VJF_TOSS;
 393     INCR(vjs_errorin);
 394 }
 395
 396 /*
 397  * "Uncompress" a packet of type TYPE_UNCOMPRESSED_TCP.
 398  */
 399 int
 400 vj_uncompress_uncomp(buf, comp)
 401     u_char *buf;
 402     struct vjcompress *comp;
 403 {
 404     register u_int hlen;
 405     register struct cstate *cs;
 406     register struct ip *ip;
 407
 408     ip = (struct ip *) buf;
 409     if (ip->ip_p >= MAX_STATES) {
 410         comp->flags |= VJF_TOSS;
 411         INCR(vjs_errorin);
 412         return (0);
 413     }
 414     cs = &comp->rstate[comp->last_recv = ip->ip_p];
 415     comp->flags &=~ VJF_TOSS;
 416     ip->ip_p = IPPROTO_TCP;
 417     hlen = ip->ip_hl;
 418     hlen += ((struct tcphdr *)&((int *)ip)[hlen])->th_off;
 419     hlen <<= 2;
 420     BCOPY(ip, &cs->cs_ip, hlen);
 421     cs->cs_hlen = hlen;
 422     INCR(vjs_uncompressedin);
 423     return (1);
 424 }
 425
 426 /*
 427  * Uncompress a packet of type TYPE_COMPRESSED_TCP.
 428  * The packet starts at buf and is of total length total_len.
 429  * The first buflen bytes are at buf; this must include the entire
 430  * compressed TCP/IP header.  This procedure returns the length
 431  * of the VJ header, with a pointer to the uncompressed IP header
 432  * in *hdrp and its length in *hlenp.
 433  */
 434 int
 435 vj_uncompress_tcp(buf, buflen, total_len, comp, hdrp, hlenp)
 436     u_char *buf;
 437     int buflen, total_len;
 438     struct vjcompress *comp;
 439     u_char **hdrp;
 440     u_int *hlenp;
 441 {
 442     register u_char *cp;
 443     register u_int hlen, changes;
 444     register struct tcphdr *th;
 445     register struct cstate *cs;
 446     register struct ip *ip;
 447     register u_short *bp;
 448     register u_int vjlen;
 449
 450     INCR(vjs_compressedin);
 451     cp = buf;
 452     changes = *cp++;
 453     if (changes & NEW_C) {
 454         /* Make sure the state index is in range, then grab the state.
 455          * If we have a good state index, clear the 'discard' flag. */
 456         if (*cp >= MAX_STATES)
 457             goto bad;
 458
 459         comp->flags &=~ VJF_TOSS;
 460         comp->last_recv = *cp++;
 461     } else {
 462         /* this packet has an implicit state index.  If we've
 463          * had a line error since the last time we got an
 464          * explicit state index, we have to toss the packet. */
 465         if (comp->flags & VJF_TOSS) {
 466             INCR(vjs_tossed);
 467             return (-1);
 468         }
 469     }
 470     cs = &comp->rstate[comp->last_recv];
 471     hlen = cs->cs_ip.ip_hl << 2;
 472     th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen];
 473     th->th_sum = htons((*cp << 8) | cp[1]);
 474     cp += 2;
 475     if (changes & TCP_PUSH_BIT)
 476         th->th_flags |= TH_PUSH;
 477     else
 478         th->th_flags &=~ TH_PUSH;
 479
 480     switch (changes & SPECIALS_MASK) {
 481     case SPECIAL_I:
 482         {
 483             register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
 484             th->th_ack = htonl(ntohl(th->th_ack) + i);
 485             th->th_seq = htonl(ntohl(th->th_seq) + i);
 486         }
 487         break;
 488
 489     case SPECIAL_D:
 490         th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
 491                            - cs->cs_hlen);
 492         break;
 493
 494     default:
 495         if (changes & NEW_U) {
 496             th->th_flags |= TH_URG;
 497             DECODEU(th->th_urp);
 498         } else
 499             th->th_flags &=~ TH_URG;
 500         if (changes & NEW_W)
 501             DECODES(th->th_win);
 502         if (changes & NEW_A)
 503             DECODEL(th->th_ack);
 504         if (changes & NEW_S)
 505             DECODEL(th->th_seq);
 506         break;
 507     }
 508     if (changes & NEW_I) {
 509         DECODES(cs->cs_ip.ip_id);
 510     } else
 511         cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
 512
 513     /*
 514      * At this point, cp points to the first byte of data in the
 515      * packet.  Fill in the IP total length and update the IP
 516      * header checksum.
 517      */
 518     vjlen = cp - buf;
 519     buflen -= vjlen;
 520     if (buflen < 0)
 521         /* we must have dropped some characters (crc should detect
 522          * this but the old slip framing won't) */
 523         goto bad;
 524
 525     total_len += cs->cs_hlen - vjlen;
 526     cs->cs_ip.ip_len = htons(total_len);
 527
 528     /* recompute the ip header checksum */
 529     bp = (u_short *) &cs->cs_ip;
 530     cs->cs_ip.ip_sum = 0;
 531     for (changes = 0; hlen > 0; hlen -= 2)
 532         changes += *bp++;
 533     changes = (changes & 0xffff) + (changes >> 16);
 534     changes = (changes & 0xffff) + (changes >> 16);
 535     cs->cs_ip.ip_sum = ~ changes;
 536
 537     *hdrp = (u_char *) &cs->cs_ip;
 538     *hlenp = cs->cs_hlen;
 539     return vjlen;
 540
 541  bad:
 542     comp->flags |= VJF_TOSS;
 543     INCR(vjs_errorin);
 544     return (-1);
 545 }