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