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