home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / misc / src0131 / slcompre.c < prev    next >
C/C++ Source or Header  |  1990-11-03  |  13KB  |  483 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. /*
  24.  * modified for KA9Q Internet Software Package by
  25.  * Katie Stevens (dkstevens@ucdavis.edu)
  26.  * University of California, Davis
  27.  * Computing Services
  28.  *    - 01-31-90    initial adaptation (from 1.19)
  29.  *    PPP.05    02-15-90 [ks]
  30.  *    PPP.08    05-02-90 [ks]    use PPP protocol field to signal compression
  31.  *    PPP.15    09-90     [ks]    improve mbuf handling
  32.  *    PPP.16  11-02     [karn]    substantially rewritten to use NOS facilities
  33.  */
  34.  
  35. #include <mem.h>
  36. #include "global.h"
  37. #include "mbuf.h"
  38. #include "tcp.h"
  39. #include "ip.h"
  40. #include "internet.h"
  41. #include "slcompress.h"
  42.  
  43. static char *encode __ARGS((char *cp,int16 n));
  44. static long decode __ARGS((struct mbuf **bufp));
  45.  
  46. void
  47. sl_compress_init(comp)
  48. struct slcompress *comp;
  49. {
  50.     register int16 i;
  51.     register struct cstate *tstate = comp->tstate;
  52.  
  53.     memset((char *)comp, 0, sizeof(*comp));
  54.     for(i = MAX_STATES - 1; i > 0; --i){
  55.         tstate[i].cs_id = i;
  56.         tstate[i].cs_next = &tstate[i - 1];
  57.     }
  58.     tstate[0].cs_next = &tstate[MAX_STATES - 1];
  59.     tstate[0].cs_id = 0;
  60.     comp->last_cs = &tstate[0];
  61.     comp->last_recv = 255;
  62.     comp->last_xmit = 255;
  63. }
  64.  
  65. /* Encode a number */
  66. static char *
  67. encode(cp,n)
  68. register char *cp;
  69. int16 n;
  70. {
  71.     if(n >= 256 || n == 0){
  72.         *cp++ = 0;
  73.         cp = put16(cp,n);
  74.     } else {
  75.         *cp++ = n;
  76.     }
  77.     return cp;
  78. }
  79.  
  80. /* Decode a number */
  81. static long
  82. decode(bufp)
  83. struct mbuf **bufp;
  84. {
  85.     int x;
  86.  
  87.     x = PULLCHAR(bufp);
  88.     if(x == 0){
  89.         return pull16(bufp);    /* pull16 returns -1 on error */
  90.     } else {
  91.         return (long)x;        /* -1 if PULLCHAR returned error */
  92.     }
  93. }
  94.  
  95. int
  96. sl_compress_tcp(bpp,comp, compress_cid)
  97. struct mbuf **bpp;
  98. struct slcompress *comp;
  99. int compress_cid;
  100. {
  101.     register struct cstate *cs = comp->last_cs->cs_next;
  102.     register int16 hlen;
  103.     register struct tcp *oth;
  104.     register unsigned long deltaS, deltaA;
  105.     register int16 changes = 0;
  106.     char new_seq[16];
  107.     register char *cp = new_seq;
  108.     struct mbuf *bp;
  109.     struct tcp th;
  110.     struct ip iph;
  111.  
  112.     /* Extract IP header */
  113.     hlen = ntohip(&iph,bpp);
  114.  
  115.     /* Bail if this packet isn't TCP, or is an IP fragment */
  116.     if(iph.protocol != TCP_PTCL || iph.offset != 0 || iph.flags.mf){
  117.         /* Send as regular IP */
  118.         if(iph.protocol != TCP_PTCL)
  119.             comp->sls_nontcp++;
  120.         else
  121.             comp->sls_asistcp++;
  122.         *bpp = htonip(&iph,*bpp,1);
  123.         return SL_TYPE_IP;
  124.     }
  125.     /* Extract TCP header */
  126.     hlen += ntohtcp(&th,bpp);
  127.  
  128.     /*  Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
  129.      *  some other control bit is set).
  130.      */
  131.     if(th.flags.syn || th.flags.fin || th.flags.rst || !th.flags.ack){
  132.         /* TCP connection stuff; send as regular IP */
  133.         comp->sls_asistcp++;
  134.         *bpp = htontcp(&th,*bpp,NULLHEADER);
  135.         *bpp = htonip(&iph,*bpp,1);
  136.         return SL_TYPE_IP;
  137.     }
  138.     /*
  139.      * Packet is compressible -- we're going to send either a
  140.      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way we need
  141.      * to locate (or create) the connection state.  Special case the
  142.      * most recently used connection since it's most likely to be used
  143.      * again & we don't have to do any reordering if it's used.
  144.      */
  145.     if(iph.source != cs->cs_ip.source ||
  146.      iph.dest  != cs->cs_ip.dest ||
  147.      th.source != cs->cs_tcp.source ||
  148.      th.dest != cs->cs_tcp.dest){
  149.         /*
  150.          * Wasn't the first -- search for it.
  151.          *
  152.          * States are kept in a circularly linked list with
  153.          * last_cs pointing to the end of the list.  The
  154.          * list is kept in lru order by moving a state to the
  155.          * head of the list whenever it is referenced.  Since
  156.          * the list is short and, empirically, the connection
  157.          * we want is almost always near the front, we locate
  158.          * states via linear search.  If we don't find a state
  159.          * for the datagram, the oldest state is (re-)used.
  160.          */
  161.         register struct cstate *lcs;
  162.         register struct cstate *lastcs = comp->last_cs;
  163.  
  164.         do {
  165.             lcs = cs; cs = cs->cs_next;
  166.             comp->sls_searches++;
  167.             if(iph.source == cs->cs_ip.source
  168.              && iph.dest == cs->cs_ip.dest
  169.              && th.source == cs->cs_tcp.source
  170.              && th.dest == cs->cs_tcp.dest)
  171.                 goto found;
  172.         } while(cs != lastcs);
  173.  
  174.         /*
  175.          * Didn't find it -- re-use oldest cstate.  Send an
  176.          * uncompressed packet that tells the other side what
  177.          * connection number we're using for this conversation.
  178.          * Note that since the state list is circular, the oldest
  179.          * state points to the newest and we only need to set
  180.          * last_cs to update the lru linkage.
  181.          */
  182.         comp->sls_misses++;
  183.         comp->last_cs = lcs;
  184.  
  185.         goto uncompressed;
  186.  
  187.     found:
  188.         /*
  189.          * Found it -- move to the front on the connection list.
  190.          */
  191.         if(cs == lastcs)
  192.             comp->last_cs = lcs;
  193.         else {
  194.             lcs->cs_next = cs->cs_next;
  195.             cs->cs_next = lastcs->cs_next;
  196.             lastcs->cs_next = cs;
  197.         }
  198.     }
  199.  
  200.     /*
  201.      * Make sure that only what we expect to change changed.
  202.      * Check the following:
  203.      * IP protocol version, header length & type of service.
  204.      * The "Don't fragment" bit.
  205.      * The time-to-live field.
  206.      * The TCP header length.
  207.      * IP options, if any.
  208.      * TCP options, if any.
  209.      * If any of these things are different between the previous &
  210.      * current datagram, we send the current datagram `uncompressed'.
  211.      */
  212.     oth = &cs->cs_tcp;
  213.  
  214.     if(iph.version != cs->cs_ip.version || iph.optlen != cs->cs_ip.optlen
  215.      || iph.tos != cs->cs_ip.tos
  216.      || iph.flags.df != cs->cs_ip.flags.df
  217.      || iph.ttl != cs->cs_ip.ttl
  218.      || th.optlen != cs->cs_tcp.optlen
  219.      || iph.optlen != cs->cs_ip.optlen
  220.      || (iph.optlen > 0 && memcmp(iph.options,cs->cs_ip.options,iph.optlen) != 0)
  221.      || (th.optlen > 0 && memcmp(th.options,cs->cs_tcp.options,th.optlen) != 0)){
  222.         goto uncompressed;
  223.     }
  224.     /*
  225.      * Figure out which of the changing fields changed.  The
  226.      * receiver expects changes in the order: urgent, window,
  227.      * ack, seq (the order minimizes the number of temporaries
  228.      * needed in this section of code).
  229.      */
  230.     if(th.flags.urg){
  231.         deltaS = th.up;
  232.         cp = encode(cp,deltaS);
  233.         changes |= NEW_U;
  234.     } else if(th.up != oth->up){
  235.         /* argh! URG not set but urp changed -- a sensible
  236.          * implementation should never do this but RFC793
  237.          * doesn't prohibit the change so we have to deal
  238.          * with it. */
  239.         goto uncompressed;
  240.     }
  241.     if((deltaS = th.wnd - oth->wnd) != 0){
  242.         cp = encode(cp,deltaS);
  243.         changes |= NEW_W;
  244.     }
  245.     if((deltaA = th.ack - oth->ack) != 0L){
  246.         if(deltaA > 0x0000ffff)
  247.             goto uncompressed;
  248.         cp = encode(cp,deltaA);
  249.         changes |= NEW_A;
  250.     }
  251.     if((deltaS = th.seq - oth->seq) != 0L){
  252.         if(deltaS > 0x0000ffff)
  253.             goto uncompressed;
  254.         cp = encode(cp,deltaS);
  255.         changes |= NEW_S;
  256.     }
  257.  
  258.     switch(changes){
  259.     case 0:    /* Nothing changed. If this packet contains data and the
  260.          * last one didn't, this is probably a data packet following
  261.          * an ack (normal on an interactive connection) and we send
  262.          * it compressed.  Otherwise it's probably a retransmit,
  263.          * retransmitted ack or window probe.  Send it uncompressed
  264.          * in case the other side missed the compressed version.
  265.          */
  266.         if(iph.length != cs->cs_ip.length && cs->cs_ip.length == hlen)
  267.             break;
  268.         goto uncompressed;
  269.     case SPECIAL_I:
  270.     case SPECIAL_D:
  271.         /* actual changes match one of our special case encodings --
  272.          * send packet uncompressed.
  273.          */
  274.         goto uncompressed;
  275.     case NEW_S|NEW_A:
  276.         if(deltaS == deltaA &&
  277.             deltaS == cs->cs_ip.length - hlen){
  278.             /* special case for echoed terminal traffic */
  279.             changes = SPECIAL_I;
  280.             cp = new_seq;
  281.         }
  282.         break;
  283.     case NEW_S:
  284.         if(deltaS == cs->cs_ip.length - hlen){
  285.             /* special case for data xfer */
  286.             changes = SPECIAL_D;
  287.             cp = new_seq;
  288.         }
  289.         break;
  290.     }
  291.     deltaS = iph.id - cs->cs_ip.id;
  292.     if(deltaS != 1){
  293.         cp = encode(cp,deltaS);
  294.         changes |= NEW_I;
  295.     }
  296.     if(th.flags.psh)
  297.         changes |= TCP_PUSH_BIT;
  298.     /* Grab the cksum before we overwrite it below.  Then update our
  299.      * state with this packet's header.
  300.      */
  301.     deltaA = th.checksum;
  302.     ASSIGN(cs->cs_ip,iph);
  303.     ASSIGN(cs->cs_tcp,th);
  304.     /* We want to use the original packet as our compressed packet.
  305.      * (cp - new_seq) is the number of bytes we need for compressed
  306.      * sequence numbers.  In addition we need one byte for the change
  307.      * mask, one for the connection id and two for the tcp checksum.
  308.      * So, (cp - new_seq) + 4 bytes of header are needed.
  309.      */
  310.     deltaS = cp - new_seq;
  311.     if(compress_cid == 0 || comp->last_xmit != cs->cs_id){
  312.         bp = *bpp = pushdown(*bpp,deltaS + 4);
  313.         cp = bp->data;
  314.         *cp++ = changes | NEW_C;
  315.         *cp++ = cs->cs_id;
  316.     } else {
  317.         bp = *bpp = pushdown(*bpp,deltaS + 3);
  318.         cp = bp->data;
  319.         *cp++ = changes;
  320.     }
  321.     cp = put16(cp,(int16)deltaA);    /* Write TCP checksum */
  322.     memcpy(cp,new_seq,deltaS);    /* Write list of deltas */
  323.     comp->sls_compressed++;
  324.     return SL_TYPE_COMPRESSED_TCP;
  325.  
  326.     /* Update connection state cs & send uncompressed packet (i.e.,
  327.      * a regular ip/tcp packet but with the 'conversation id' we hope
  328.      * to use on future compressed packets in the protocol field).
  329.      */
  330. uncompressed:
  331.     iph.protocol = cs->cs_id;
  332.     ASSIGN(cs->cs_ip,iph);
  333.     ASSIGN(cs->cs_tcp,th);
  334.     comp->last_xmit = cs->cs_id;
  335.     comp->sls_uncompressed++;
  336.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  337.     *bpp = htonip(&iph,*bpp,1);
  338.     return SL_TYPE_UNCOMPRESSED_TCP;
  339. }
  340.  
  341.  
  342. int
  343. sl_uncompress_tcp(bufp, len, type, comp)
  344. struct mbuf **bufp;
  345. int len;
  346. int16 type;
  347. struct slcompress *comp;
  348. {
  349.     register int changes;
  350.     long x;
  351.     register struct tcp *thp;
  352.     register struct cstate *cs;
  353.     struct ip iph;
  354.     struct tcp th;
  355.  
  356.     switch(type){
  357.     case SL_TYPE_UNCOMPRESSED_TCP:
  358.         /* Extract IP and TCP headers and verify conn ID */
  359.         ntohip(&iph,bufp);
  360.         ntohtcp(&th,bufp);
  361.         if(uchar(iph.protocol) >= MAX_STATES)
  362.             goto bad;
  363.  
  364.         /* Update local state */
  365.         cs = &comp->rstate[comp->last_recv = uchar(iph.protocol)];
  366.         comp->flags &=~ SLF_TOSS;
  367.         iph.protocol = TCP_PTCL;
  368.         ASSIGN(cs->cs_ip,iph);
  369.         ASSIGN(cs->cs_tcp,th);
  370.  
  371.         /* Put headers back on packet
  372.          * Neither header checksum is recalculated
  373.          */
  374.         *bufp = htontcp(&th,*bufp,NULLHEADER);
  375.         *bufp = htonip(&iph,*bufp,1);
  376.         comp->sls_uncompressedin++;
  377.         return len;
  378.  
  379.     default:
  380.         goto bad;
  381.  
  382.     case SL_TYPE_COMPRESSED_TCP:
  383.         break;
  384.     }
  385.     /* We've got a compressed packet; read the change byte */
  386.     comp->sls_compressedin++;
  387.     if(len < 3){
  388.         comp->sls_errorin++;
  389.         return 0;
  390.     }
  391.     changes = PULLCHAR(bufp);    /* "Can't fail" */
  392.     if(changes & NEW_C){
  393.         /* Make sure the state index is in range, then grab the state.
  394.          * If we have a good state index, clear the 'discard' flag.
  395.          */
  396.         x = PULLCHAR(bufp);    /* Read conn index */
  397.         if(x < 0 || x >= MAX_STATES)
  398.             goto bad;
  399.  
  400.         comp->flags &=~ SLF_TOSS;
  401.         comp->last_recv = x;
  402.     } else {
  403.         /* this packet has an implicit state index.  If we've
  404.          * had a line error since the last time we got an
  405.          * explicit state index, we have to toss the packet. */
  406.         if(comp->flags & SLF_TOSS){
  407.             comp->sls_tossed++;
  408.             return 0;
  409.         }
  410.     }
  411.     cs = &comp->rstate[comp->last_recv];
  412.     thp = &cs->cs_tcp;
  413.     
  414.     if((x = pull16(bufp)) == -1)    /* Read the TCP checksum */
  415.         goto bad; 
  416.     thp->checksum = x;
  417.  
  418.     thp->flags.psh = (changes & TCP_PUSH_BIT) ? 1 : 0;
  419.  
  420.     switch(changes & SPECIALS_MASK){
  421.     case SPECIAL_I:        /* Echoed terminal traffic */
  422.         {
  423.         register int16 i;
  424.         i = cs->cs_ip.length;
  425.         i -= (cs->cs_ip.optlen + IPLEN + TCPLEN);
  426.         thp->ack += i;
  427.         thp->seq += i;
  428.         }
  429.         break;
  430.  
  431.     case SPECIAL_D:            /* Unidirectional data */
  432.         thp->seq += cs->cs_ip.length - (cs->cs_ip.optlen +IPLEN + TCPLEN);
  433.         break;
  434.  
  435.     default:
  436.         if(changes & NEW_U){
  437.             thp->flags.urg = 1;
  438.             if((x = decode(bufp)) == -1)
  439.                 goto bad;
  440.             thp->up = x;
  441.         } else
  442.             thp->flags.urg = 0;
  443.         if(changes & NEW_W){
  444.             if((x = decode(bufp)) == -1)
  445.                 goto bad;
  446.             thp->wnd += x;
  447.         }
  448.         if(changes & NEW_A){
  449.             if((x = decode(bufp)) == -1)
  450.                 goto bad;
  451.             thp->ack += x;
  452.         }
  453.         if(changes & NEW_S){
  454.             if((x = decode(bufp)) == -1)
  455.                 goto bad;
  456.             thp->seq += x;
  457.         }
  458.         break;
  459.     }
  460.     if(changes & NEW_I){
  461.         if((x = decode(bufp)) == -1)
  462.             goto bad;
  463.         cs->cs_ip.id += x;
  464.     } else
  465.         cs->cs_ip.id++;
  466.  
  467.     /*
  468.      * At this point, bufp points to the first byte of data in the
  469.      * packet.  Put the reconstructed TCP and IP headers back on the
  470.      * packet.
  471.      */
  472.     len = len_p(*bufp) + IPLEN + TCPLEN + cs->cs_ip.optlen;
  473.     cs->cs_ip.length = len;
  474.  
  475.     *bufp = htontcp(thp,*bufp,NULLHEADER);
  476.     *bufp = htonip(&cs->cs_ip,*bufp,0);
  477.     return len;
  478. bad:
  479.     comp->flags |= SLF_TOSS;
  480.     comp->sls_errorin++;
  481.     return 0;
  482. }
  483.