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