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