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