home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 3 / hamradioversion3.0examsandprograms1992.iso / misc / 9q920411 / slhc.c < prev    next >
C/C++ Source or Header  |  1992-04-06  |  15KB  |  580 lines
  1. /*
  2.  * Routines to compress and uncompress 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.  *    - Feb 1991    Bill_Simpson@um.cc.umich.edu
  35.  *            variable number of conversation slots
  36.  *            allow zero or one slots
  37.  *            separate routines
  38.  *            status display
  39.  */
  40.  
  41. #include <mem.h>
  42. #include "global.h"
  43. #include "mbuf.h"
  44. #include "internet.h"
  45. #include "ip.h"
  46. #include "tcp.h"
  47. #include "slhc.h"
  48.  
  49. static char *encode __ARGS((char *cp,int16 n));
  50. static long decode __ARGS((struct mbuf **bpp));
  51.  
  52.  
  53. /* Initialize compression data structure
  54.  *    slots must be in range 0 to 255 (zero meaning no compression)
  55.  */
  56. struct slcompress *
  57. slhc_init( rslots, tslots )
  58. int rslots;
  59. int tslots;
  60. {
  61.     register int16 i;
  62.     register struct cstate *ts;
  63.     struct slcompress *comp;
  64.  
  65.     comp = callocw( 1, sizeof(struct slcompress) );
  66.  
  67.     if ( rslots > 0  &&  rslots < 256 ) {
  68.         comp->rstate = callocw( rslots, sizeof(struct cstate) );
  69.         comp->rslot_limit = rslots - 1;
  70.     }
  71.  
  72.     if ( tslots > 0  &&  tslots < 256 ) {
  73.         comp->tstate = callocw( tslots, sizeof(struct cstate) );
  74.         comp->tslot_limit = tslots - 1;
  75.     }
  76.  
  77.     comp->xmit_oldest = 0;
  78.     comp->xmit_current = 255;
  79.     comp->recv_current = 255;
  80.  
  81.     if ( tslots > 0 ) {
  82.         ts = comp->tstate;
  83.         for(i = comp->tslot_limit; i > 0; --i){
  84.             ts[i].this = i;
  85.             ts[i].next = &(ts[i - 1]);
  86.         }
  87.         ts[0].next = &(ts[comp->tslot_limit]);
  88.         ts[0].this = 0;
  89.     }
  90.     return comp;
  91. }
  92.  
  93.  
  94. /* Free a compression data structure */
  95. void
  96. slhc_free(comp)
  97. struct slcompress *comp;
  98. {
  99.     if ( comp == NULLSLCOMPR )
  100.         return;
  101.  
  102.     if ( comp->rstate != NULLSLSTATE )
  103.         free( comp->rstate );
  104.  
  105.     if ( comp->tstate != NULLSLSTATE )
  106.         free( comp->tstate );
  107.  
  108.     free( comp );
  109. }
  110.  
  111.  
  112. /* Encode a number */
  113. static char *
  114. encode(cp,n)
  115. register char *cp;
  116. int16 n;
  117. {
  118.     if(n >= 256 || n == 0){
  119.         *cp++ = 0;
  120.         cp = put16(cp,n);
  121.     } else {
  122.         *cp++ = n;
  123.     }
  124.     return cp;
  125. }
  126.  
  127. /* Decode a number */
  128. static long
  129. decode(bpp)
  130. struct mbuf **bpp;
  131. {
  132.     register int x;
  133.  
  134.     x = PULLCHAR(bpp);
  135.     if(x == 0){
  136.         return pull16(bpp);    /* pull16 returns -1 on error */
  137.     } else {
  138.         return (long)x;        /* -1 if PULLCHAR returned error */
  139.     }
  140. }
  141.  
  142. int
  143. slhc_compress(comp, bpp, compress_cid)
  144. struct slcompress *comp;
  145. struct mbuf **bpp;
  146. int compress_cid;
  147. {
  148.     register struct cstate *ocs = &(comp->tstate[comp->xmit_oldest]);
  149.     register struct cstate *lcs = ocs;
  150.     register struct cstate *cs = lcs->next;
  151.     register int16 hlen;
  152.     register struct tcp *oth;
  153.     register unsigned long deltaS, deltaA;
  154.     register int16 changes = 0;
  155.     char new_seq[16];
  156.     register char *cp = new_seq;
  157.     struct mbuf *bp;
  158.     struct tcp th;
  159.     struct ip iph;
  160.  
  161.     /* Extract IP header */
  162.     hlen = ntohip(&iph,bpp);
  163.  
  164.     /* Bail if this packet isn't TCP, or is an IP fragment */
  165.     if(iph.protocol != TCP_PTCL || iph.offset != 0 || iph.flags.mf){
  166.         /* Send as regular IP */
  167.         if(iph.protocol != TCP_PTCL)
  168.             comp->sls_o_nontcp++;
  169.         else
  170.             comp->sls_o_tcp++;
  171.         *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  172.         return SL_TYPE_IP;
  173.     }
  174.     /* Extract TCP header */
  175.     hlen += ntohtcp(&th,bpp);
  176.  
  177.     /*  Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
  178.      *  some other control bit is set).
  179.      */
  180.     if(th.flags.syn || th.flags.fin || th.flags.rst || !th.flags.ack){
  181.         /* TCP connection stuff; send as regular IP */
  182.         comp->sls_o_tcp++;
  183.         *bpp = htontcp(&th,*bpp,NULLHEADER);
  184.         *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  185.         return SL_TYPE_IP;
  186.     }
  187.     /*
  188.      * Packet is compressible -- we're going to send either a
  189.      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way,
  190.      * we need to locate (or create) the connection state.
  191.      *
  192.      * States are kept in a circularly linked list with
  193.      * xmit_oldest pointing to the end of the list.  The
  194.      * list is kept in lru order by moving a state to the
  195.      * head of the list whenever it is referenced.  Since
  196.      * the list is short and, empirically, the connection
  197.      * we want is almost always near the front, we locate
  198.      * states via linear search.  If we don't find a state
  199.      * for the datagram, the oldest state is (re-)used.
  200.      */
  201.     for ( ; ; ) {
  202.         if( iph.source == cs->cs_ip.source
  203.          && iph.dest == cs->cs_ip.dest
  204.          && th.source == cs->cs_tcp.source
  205.          && th.dest == cs->cs_tcp.dest)
  206.             goto found;
  207.  
  208.         /* if current equal oldest, at end of list */
  209.         if ( cs == ocs )
  210.             break;
  211.         lcs = cs;
  212.         cs = cs->next;
  213.         comp->sls_o_searches++;
  214.     };
  215.     /*
  216.      * Didn't find it -- re-use oldest cstate.  Send an
  217.      * uncompressed packet that tells the other side what
  218.      * connection number we're using for this conversation.
  219.      *
  220.      * Note that since the state list is circular, the oldest
  221.      * state points to the newest and we only need to set
  222.      * xmit_oldest to update the lru linkage.
  223.      */
  224.     comp->sls_o_misses++;
  225.     comp->xmit_oldest = lcs->this;
  226.  
  227.     goto uncompressed;
  228.  
  229. found:
  230.     /*
  231.      * Found it -- move to the front on the connection list.
  232.      */
  233.     if(lcs == ocs) {
  234.         /* found at most recently used */
  235.     } else if (cs == ocs) {
  236.         /* found at least recently used */
  237.         comp->xmit_oldest = lcs->this;
  238.     } else {
  239.         /* more than 2 elements */
  240.         lcs->next = cs->next;
  241.         cs->next = ocs->next;
  242.         ocs->next = cs;
  243.     }
  244.  
  245.     /*
  246.      * Make sure that only what we expect to change changed.
  247.      * Check the following:
  248.      * IP protocol version, header length & type of service.
  249.      * The "Don't fragment" bit.
  250.      * The time-to-live field.
  251.      * The TCP header length.
  252.      * IP options, if any.
  253.      * TCP options, if any.
  254.      * If any of these things are different between the previous &
  255.      * current datagram, we send the current datagram `uncompressed'.
  256.      */
  257.     oth = &cs->cs_tcp;
  258.  
  259.     if(iph.version != cs->cs_ip.version || iph.optlen != cs->cs_ip.optlen
  260.      || iph.tos != cs->cs_ip.tos
  261.      || iph.flags.df != cs->cs_ip.flags.df
  262.      || iph.ttl != cs->cs_ip.ttl
  263.      || th.optlen != cs->cs_tcp.optlen
  264.      || (iph.optlen > 0 && memcmp(iph.options,cs->cs_ip.options,iph.optlen) != 0)
  265.      || (th.optlen > 0 && memcmp(th.options,cs->cs_tcp.options,th.optlen) != 0)){
  266.         goto uncompressed;
  267.     }
  268.     /*
  269.      * Figure out which of the changing fields changed.  The
  270.      * receiver expects changes in the order: urgent, window,
  271.      * ack, seq (the order minimizes the number of temporaries
  272.      * needed in this section of code).
  273.      */
  274.     if(th.flags.urg){
  275.         deltaS = th.up;
  276.         cp = encode(cp,deltaS);
  277.         changes |= NEW_U;
  278.     } else if(th.up != oth->up){
  279.         /* argh! URG not set but urp changed -- a sensible
  280.          * implementation should never do this but RFC793
  281.          * doesn't prohibit the change so we have to deal
  282.          * with it. */
  283.         goto uncompressed;
  284.     }
  285.     if((deltaS = th.wnd - oth->wnd) != 0){
  286.         cp = encode(cp,deltaS);
  287.         changes |= NEW_W;
  288.     }
  289.     if((deltaA = th.ack - oth->ack) != 0L){
  290.         if(deltaA > 0x0000ffff)
  291.             goto uncompressed;
  292.         cp = encode(cp,deltaA);
  293.         changes |= NEW_A;
  294.     }
  295.     if((deltaS = th.seq - oth->seq) != 0L){
  296.         if(deltaS > 0x0000ffff)
  297.             goto uncompressed;
  298.         cp = encode(cp,deltaS);
  299.         changes |= NEW_S;
  300.     }
  301.  
  302.     switch(changes){
  303.     case 0:    /* Nothing changed. If this packet contains data and the
  304.          * last one didn't, this is probably a data packet following
  305.          * an ack (normal on an interactive connection) and we send
  306.          * it compressed.  Otherwise it's probably a retransmit,
  307.          * retransmitted ack or window probe.  Send it uncompressed
  308.          * in case the other side missed the compressed version.
  309.          */
  310.         if(iph.length != cs->cs_ip.length && cs->cs_ip.length == hlen)
  311.             break;
  312.         goto uncompressed;
  313.     case SPECIAL_I:
  314.     case SPECIAL_D:
  315.         /* actual changes match one of our special case encodings --
  316.          * send packet uncompressed.
  317.          */
  318.         goto uncompressed;
  319.     case NEW_S|NEW_A:
  320.         if(deltaS == deltaA &&
  321.             deltaS == cs->cs_ip.length - hlen){
  322.             /* special case for echoed terminal traffic */
  323.             changes = SPECIAL_I;
  324.             cp = new_seq;
  325.         }
  326.         break;
  327.     case NEW_S:
  328.         if(deltaS == cs->cs_ip.length - hlen){
  329.             /* special case for data xfer */
  330.             changes = SPECIAL_D;
  331.             cp = new_seq;
  332.         }
  333.         break;
  334.     }
  335.     deltaS = iph.id - cs->cs_ip.id;
  336.     if(deltaS != 1){
  337.         cp = encode(cp,deltaS);
  338.         changes |= NEW_I;
  339.     }
  340.     if(th.flags.psh)
  341.         changes |= TCP_PUSH_BIT;
  342.     /* Grab the cksum before we overwrite it below.  Then update our
  343.      * state with this packet's header.
  344.      */
  345.     deltaA = th.checksum;
  346.     ASSIGN(cs->cs_ip,iph);
  347.     ASSIGN(cs->cs_tcp,th);
  348.     /* We want to use the original packet as our compressed packet.
  349.      * (cp - new_seq) is the number of bytes we need for compressed
  350.      * sequence numbers.  In addition we need one byte for the change
  351.      * mask, one for the connection id and two for the tcp checksum.
  352.      * So, (cp - new_seq) + 4 bytes of header are needed.
  353.      */
  354.     deltaS = cp - new_seq;
  355.     if(compress_cid == 0 || comp->xmit_current != cs->this){
  356.         bp = *bpp = pushdown(*bpp,deltaS + 4);
  357.         cp = bp->data;
  358.         *cp++ = changes | NEW_C;
  359.         *cp++ = cs->this;
  360.         comp->xmit_current = cs->this;
  361.     } else {
  362.         bp = *bpp = pushdown(*bpp,deltaS + 3);
  363.         cp = bp->data;
  364.         *cp++ = changes;
  365.     }
  366.     cp = put16(cp,(int16)deltaA);    /* Write TCP checksum */
  367.     memcpy(cp,new_seq,deltaS);    /* Write list of deltas */
  368.     comp->sls_o_compressed++;
  369.     return SL_TYPE_COMPRESSED_TCP;
  370.  
  371.     /* Update connection state cs & send uncompressed packet (i.e.,
  372.      * a regular ip/tcp packet but with the 'conversation id' we hope
  373.      * to use on future compressed packets in the protocol field).
  374.      */
  375. uncompressed:
  376.     iph.protocol = cs->this;
  377.     ASSIGN(cs->cs_ip,iph);
  378.     ASSIGN(cs->cs_tcp,th);
  379.     comp->xmit_current = cs->this;
  380.     comp->sls_o_uncompressed++;
  381.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  382.     *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  383.     return SL_TYPE_UNCOMPRESSED_TCP;
  384. }
  385.  
  386.  
  387. int
  388. slhc_uncompress(comp, bpp)
  389. struct slcompress *comp;
  390. struct mbuf **bpp;
  391. {
  392.     register int changes;
  393.     long x;
  394.     register struct tcp *thp;
  395.     register struct cstate *cs;
  396.     int len;
  397.  
  398.     /* We've got a compressed packet; read the change byte */
  399.     comp->sls_i_compressed++;
  400.     if(len_p(*bpp) < 3){
  401.         comp->sls_i_error++;
  402.         return 0;
  403.     }
  404.     changes = PULLCHAR(bpp);    /* "Can't fail" */
  405.     if(changes & NEW_C){
  406.         /* Make sure the state index is in range, then grab the state.
  407.          * If we have a good state index, clear the 'discard' flag.
  408.          */
  409.         x = PULLCHAR(bpp);    /* Read conn index */
  410.         if(x < 0 || x > comp->rslot_limit)
  411.             goto bad;
  412.  
  413.         comp->flags &=~ SLF_TOSS;
  414.         comp->recv_current = x;
  415.     } else {
  416.         /* this packet has an implicit state index.  If we've
  417.          * had a line error since the last time we got an
  418.          * explicit state index, we have to toss the packet. */
  419.         if(comp->flags & SLF_TOSS){
  420.             comp->sls_i_tossed++;
  421.             return 0;
  422.         }
  423.     }
  424.     cs = &comp->rstate[comp->recv_current];
  425.     thp = &cs->cs_tcp;
  426.  
  427.     if((x = pull16(bpp)) == -1)    /* Read the TCP checksum */
  428.         goto bad;
  429.     thp->checksum = x;
  430.  
  431.     thp->flags.psh = (changes & TCP_PUSH_BIT) ? 1 : 0;
  432.  
  433.     switch(changes & SPECIALS_MASK){
  434.     case SPECIAL_I:        /* Echoed terminal traffic */
  435.         {
  436.         register int16 i;
  437.         i = cs->cs_ip.length;
  438.         i -= (cs->cs_ip.optlen + IPLEN + TCPLEN);
  439.         thp->ack += i;
  440.         thp->seq += i;
  441.         }
  442.         break;
  443.  
  444.     case SPECIAL_D:            /* Unidirectional data */
  445.         thp->seq += cs->cs_ip.length - (cs->cs_ip.optlen +IPLEN + TCPLEN);
  446.         break;
  447.  
  448.     default:
  449.         if(changes & NEW_U){
  450.             thp->flags.urg = 1;
  451.             if((x = decode(bpp)) == -1)
  452.                 goto bad;
  453.             thp->up = x;
  454.         } else
  455.             thp->flags.urg = 0;
  456.         if(changes & NEW_W){
  457.             if((x = decode(bpp)) == -1)
  458.                 goto bad;
  459.             thp->wnd += x;
  460.         }
  461.         if(changes & NEW_A){
  462.             if((x = decode(bpp)) == -1)
  463.                 goto bad;
  464.             thp->ack += x;
  465.         }
  466.         if(changes & NEW_S){
  467.             if((x = decode(bpp)) == -1)
  468.                 goto bad;
  469.             thp->seq += x;
  470.         }
  471.         break;
  472.     }
  473.     if(changes & NEW_I){
  474.         if((x = decode(bpp)) == -1)
  475.             goto bad;
  476.         cs->cs_ip.id += x;
  477.     } else
  478.         cs->cs_ip.id++;
  479.  
  480.     /*
  481.      * At this point, bpp points to the first byte of data in the
  482.      * packet.  Put the reconstructed TCP and IP headers back on the
  483.      * packet.  Recalculate IP checksum (but not TCP checksum).
  484.      */
  485.     len = len_p(*bpp) + IPLEN + TCPLEN + cs->cs_ip.optlen;
  486.     cs->cs_ip.length = len;
  487.  
  488.     *bpp = htontcp(thp,*bpp,NULLHEADER);
  489.     *bpp = htonip(&cs->cs_ip,*bpp,IP_CS_NEW);
  490.     return len;
  491. bad:
  492.     comp->sls_i_error++;
  493.     return slhc_toss( comp );
  494. }
  495.  
  496.  
  497. int
  498. slhc_remember(comp, bpp)
  499. struct slcompress *comp;
  500. struct mbuf **bpp;
  501. {
  502.     register struct cstate *cs;
  503.     struct ip iph;
  504.     struct tcp th;
  505.  
  506.     /* Extract IP and TCP headers and verify conn ID */
  507.     ntohip(&iph,bpp);
  508.     ntohtcp(&th,bpp);
  509.     if(uchar(iph.protocol) > comp->rslot_limit) {
  510.         comp->sls_i_error++;
  511.         return slhc_toss(comp);
  512.     }
  513.  
  514.     /* Update local state */
  515.     cs = &comp->rstate[comp->recv_current = uchar(iph.protocol)];
  516.     comp->flags &=~ SLF_TOSS;
  517.     iph.protocol = TCP_PTCL;
  518.     ASSIGN(cs->cs_ip,iph);
  519.     ASSIGN(cs->cs_tcp,th);
  520.  
  521.     /* Put headers back on packet
  522.      * Neither header checksum is recalculated
  523.      */
  524.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  525.     *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  526.     comp->sls_i_uncompressed++;
  527.     return len_p(*bpp);
  528. }
  529.  
  530.  
  531. int
  532. slhc_toss(comp)
  533. struct slcompress *comp;
  534. {
  535.     if ( comp == NULLSLCOMPR )
  536.         return 0;
  537.  
  538.     comp->flags |= SLF_TOSS;
  539.     return 0;
  540. }
  541.  
  542. void
  543. slhc_i_status(comp)
  544. struct slcompress *comp;
  545. {
  546.     if (comp != NULLSLCOMPR) {
  547.         tprintf("\t%10ld Cmp,"
  548.             " %10ld Uncmp,"
  549.             " %10ld Bad, "
  550.             " %10ld Tossed\n",
  551.             comp->sls_i_compressed,
  552.             comp->sls_i_uncompressed,
  553.             comp->sls_i_error,
  554.             comp->sls_i_tossed);
  555.     }
  556. }
  557.  
  558.  
  559. void
  560. slhc_o_status(comp)
  561. struct slcompress *comp;
  562. {
  563.     if (comp != NULLSLCOMPR) {
  564.         tprintf("\t%10ld Cmp,"
  565.             " %10ld Uncmp,"
  566.             " %10ld AsIs,"
  567.             " %10ld NotTCP\n",
  568.             comp->sls_o_compressed,
  569.             comp->sls_o_uncompressed,
  570.             comp->sls_o_tcp,
  571.             comp->sls_o_nontcp);
  572.         tprintf("\t%10ld Searches,"
  573.             " %10ld Misses\n",
  574.             comp->sls_o_searches,
  575.             comp->sls_o_misses);
  576.     }
  577. }
  578.  
  579.  
  580.