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