home *** CD-ROM | disk | FTP | other *** search
/ Amiga Developer CD 2.1 / Amiga Developer CD v2.1.iso / Extras / Networking / SANA-II / slip_src / slcompress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-17  |  16.2 KB  |  553 lines
  1. /*
  2.  * Routines to compress and uncompess tcp packets (for transmission over low
  3.  * speed serial lines.
  4.  *
  5.  * Copyright (c) 1989 Regents of the University of California. All rights
  6.  * reserved.
  7.  *
  8.  * Redistribution and use in source and binary forms are permitted provided that
  9.  * the above copyright notice and this paragraph are duplicated in all such
  10.  * forms and that any documentation, advertising materials, and other
  11.  * materials related to such distribution and use acknowledge that the
  12.  * software was developed by the University of California, Berkeley.  The
  13.  * name of the University may not be used to endorse or promote products
  14.  * derived from this software without specific prior written permission. THIS
  15.  * SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  16.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  17.  * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18.  *
  19.  * Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989: - Initial distribution.
  20.  */
  21.  
  22. #ifndef lint
  23. static char rcsid[] = "$Header: HOG:Other/networking/sana2/src/slip/RCS/slcompress.c,v 38.1 94/02/17 14:14:37 kcd Exp $";
  24. #endif
  25.  
  26. #include <exec/types.h>
  27. #include <sys/types.h>
  28. #include "param.h"
  29. #include "mbuf.h"
  30. #include "in.h"
  31. #include "in_systm.h"
  32. #include "ip.h"
  33. #include "tcp.h"
  34. #include "string.h"
  35. #include "slcompress.h"
  36. #include "slcompress_protos.h"
  37.  
  38. #ifndef SL_NO_STATS
  39. #define INCR(counter) ++comp->counter;
  40. #else
  41. #define INCR(counter)
  42. #endif
  43.  
  44. #define BCMP(p1, p2, n) memcmp((char *)(p1), (char *)(p2), (int)(n))
  45. #define BCOPY(p1, p2, n) movmem((char *)(p1), (char *)(p2), (int)(n))
  46. #ifndef KERNEL
  47. #define ovbcopy movmem
  48. #endif
  49.  
  50. typedef    char *    caddr_t;
  51.  
  52. extern struct Library *SysBase;
  53.  
  54. void
  55.  sl_compress_init(comp)
  56.     struct slcompress *comp;
  57. {
  58.     register u_int i;
  59.     register struct cstate *tstate = comp->tstate;
  60.  
  61.     setmem((char *) comp, sizeof(*comp), 0);
  62.     for (i = MAX_STATES - 1; i > 0; --i)
  63.     {
  64.         tstate[i].cs_id = i;
  65.         tstate[i].cs_next = &tstate[i - 1];
  66.     }
  67.     tstate[0].cs_next = &tstate[MAX_STATES - 1];
  68.     tstate[0].cs_id = 0;
  69.     comp->last_cs = &tstate[0];
  70.     comp->last_recv = 255;
  71.     comp->last_xmit = 255;
  72. }
  73.  
  74.  
  75. /*
  76.  * ENCODE encodes a number that is known to be non-zero.  ENCODEZ checks for
  77.  * zero (since zero has to be encoded in the long, 3 byte form).
  78.  */
  79. #define ENCODE(n) { \
  80.         if ((u_short)(n) >= 256) { \
  81.                 *cp++ = 0; \
  82.                 cp[1] = (n); \
  83.                 cp[0] = (n) >> 8; \
  84.                 cp += 2; \
  85.         } else { \
  86.                 *cp++ = (n); \
  87.         } \
  88. }
  89. #define ENCODEZ(n) { \
  90.         if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
  91.                 *cp++ = 0; \
  92.                 cp[1] = (n); \
  93.                 cp[0] = (n) >> 8; \
  94.                 cp += 2; \
  95.         } else { \
  96.                 *cp++ = (n); \
  97.         } \
  98. }
  99.  
  100. #define DECODEL(f) { \
  101.         if (*cp == 0) {\
  102.                 (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
  103.                 cp += 3; \
  104.         } else { \
  105.                 (f) = htonl(ntohl(f) + (u_long)*cp++); \
  106.         } \
  107. }
  108.  
  109. #define DECODES(f) { \
  110.         if (*cp == 0) {\
  111.                 (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
  112.                 cp += 3; \
  113.         } else { \
  114.                 (f) = htons(ntohs(f) + (u_long)*cp++); \
  115.         } \
  116. }
  117.  
  118. #define DECODEU(f) { \
  119.         if (*cp == 0) {\
  120.                 (f) = htons((cp[1] << 8) | cp[2]); \
  121.                 cp += 3; \
  122.         } else { \
  123.                 (f) = htons((u_long)*cp++); \
  124.         } \
  125. }
  126.  
  127.  
  128. u_char
  129. sl_compress_tcp(m, ip, comp, compress_cid)
  130.     struct mbuf *m;
  131.     register struct ip *ip;
  132.     struct slcompress *comp;
  133.     ULONG compress_cid;
  134. {
  135.     register struct cstate *cs = comp->last_cs->cs_next;
  136.     register u_int hlen = ip->ip_hl;
  137.     register struct tcphdr *oth;
  138.     register struct tcphdr *th;
  139.     register u_int deltaS, deltaA;
  140.     register u_int changes = 0;
  141.     u_char new_seq[16];
  142.     register u_char *cp = new_seq;
  143.     /*
  144.      * Bail if this is an IP fragment or if the TCP packet isn't
  145.      * `compressible' (i.e., ACK isn't set or some other control bit is set).
  146.      * (We assume that the caller has already made sure the packet is IP
  147.      * proto TCP).
  148.      */
  149.     if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40)
  150.         return (TYPE_IP);
  151.  
  152.     th = (struct tcphdr *) & ((int *) ip)[hlen];
  153.     if ((th->th_flags & (TH_SYN | TH_FIN | TH_RST | TH_ACK)) != TH_ACK)
  154.         return (TYPE_IP);
  155.     /*
  156.      * Packet is compressible -- we're going to send either a COMPRESSED_TCP
  157.      * or UNCOMPRESSED_TCP packet.  Either way we need to locate (or create)
  158.      * the connection state.  Special case the most recently used connection
  159.      * since it's most likely to be used again & we don't have to do any
  160.      * reordering if it's used.
  161.      */
  162.  
  163.     INCR(sls_packets)
  164.         if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
  165.             ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
  166.             *(int *) th != ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl])
  167.     {
  168.         /*
  169.          * Wasn't the first -- search for it.
  170.          *
  171.          * States are kept in a circularly linked list with last_cs pointing to
  172.          * the end of the list.  The list is kept in lru order by moving a
  173.          * state to the head of the list whenever it is referenced.  Since
  174.          * the list is short and, empirically, the connection we want is
  175.          * almost always near the front, we locate states via linear search.
  176.          * If we don't find a state for the datagram, the oldest state is
  177.          * (re-)used.
  178.          */
  179.         register struct cstate *lcs;
  180.         register struct cstate *lastcs = comp->last_cs;
  181.  
  182.         do
  183.         {
  184.             lcs = cs;
  185.             cs = cs->cs_next;
  186.             INCR(sls_searches)
  187.                 if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr
  188.                     && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr
  189.                     && *(int *) th == ((int *) &cs->cs_ip)[cs->cs_ip.ip_hl])
  190.                 goto found;
  191.         } while (cs != lastcs);
  192.  
  193.         /*
  194.          * Didn't find it -- re-use oldest cstate.  Send an uncompressed
  195.          * packet that tells the other side what connection number we're
  196.          * using for this conversation. Note that since the state list is
  197.          * circular, the oldest state points to the newest and we only need
  198.          * to set last_cs to update the lru linkage.
  199.          */
  200.         INCR(sls_misses)
  201.             comp->last_cs = lcs;
  202.         hlen += th->th_off;
  203.         hlen <<= 2;
  204.         goto uncompressed;
  205.  
  206.       found:
  207.         /*
  208.          * Found it -- move to the front on the connection list.
  209.          */
  210.         if (cs == lastcs)
  211.             comp->last_cs = lcs;
  212.         else
  213.         {
  214.             lcs->cs_next = cs->cs_next;
  215.             cs->cs_next = lastcs->cs_next;
  216.             lastcs->cs_next = cs;
  217.         }
  218.     }
  219.  
  220.     /*
  221.      * Make sure that only what we expect to change changed. The first line
  222.      * of the `if' checks the IP protocol version, header length & type of
  223.      * service.  The 2nd line checks the "Don't fragment" bit. The 3rd line
  224.      * checks the time-to-live and protocol (the protocol check is
  225.      * unnecessary but costless).  The 4th line checks the TCP header length.
  226.      * The 5th line checks IP options, if any.  The 6th line checks TCP
  227.      * options, if any.  If any of these things are different between the
  228.      * previous & current datagram, we send the current datagram
  229.      * `uncompressed'.
  230.      */
  231.     oth = (struct tcphdr *) & ((int *) &cs->cs_ip)[hlen];
  232.     deltaS = hlen;
  233.     hlen += th->th_off;
  234.     hlen <<= 2;
  235.  
  236.     if (((u_short *) ip)[0] != ((u_short *) & cs->cs_ip)[0] ||
  237.         ((u_short *) ip)[3] != ((u_short *) & cs->cs_ip)[3] ||
  238.         ((u_short *) ip)[4] != ((u_short *) & cs->cs_ip)[4] ||
  239.         th->th_off != oth->th_off ||
  240.         (deltaS > 5 &&
  241.          BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
  242.         (th->th_off > 5 &&
  243.          BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))
  244.         goto uncompressed;
  245.  
  246.     /*
  247.      * Figure out which of the changing fields changed.  The receiver expects
  248.      * changes in the order: urgent, window, ack, seq (the order minimizes
  249.      * the number of temporaries needed in this section of code).
  250.      */
  251.     if (th->th_flags & TH_URG)
  252.     {
  253.         deltaS = ntohs(th->th_urp);
  254.         ENCODEZ(deltaS);
  255.         changes |= NEW_U;
  256.     }
  257.     else if (th->th_urp != oth->th_urp)
  258.         /*
  259.          * argh! URG not set but urp changed -- a sensible implementation
  260.          * should never do this but RFC793 doesn't prohibit the change so we
  261.          * have to deal with it.
  262.          */
  263.         goto uncompressed;
  264.  
  265.     if (deltaS = (u_short) (ntohs(th->th_win) - ntohs(oth->th_win)))
  266.     {
  267.         ENCODE(deltaS);
  268.         changes |= NEW_W;
  269.     }
  270.  
  271.     if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack))
  272.     {
  273.         if (deltaA > 0xffff)
  274.             goto uncompressed;
  275.         ENCODE(deltaA);
  276.         changes |= NEW_A;
  277.     }
  278.  
  279.     if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq))
  280.     {
  281.         if (deltaS > 0xffff)
  282.             goto uncompressed;
  283.         ENCODE(deltaS);
  284.         changes |= NEW_S;
  285.     }
  286.  
  287.     switch (changes)
  288.     {
  289.  
  290.     case 0:
  291.         /*
  292.          * Nothing changed. If this packet contains data and the last one
  293.          * didn't, this is probably a data packet following an ack (normal on
  294.          * an interactive connection) and we send it compressed.  Otherwise
  295.          * it's probably a retransmit, retransmitted ack or window probe.
  296.          * Send it uncompressed in case the other side missed the compressed
  297.          * version.
  298.          */
  299.         if (ip->ip_len != cs->cs_ip.ip_len &&
  300.             ntohs(cs->cs_ip.ip_len) == hlen)
  301.             break;
  302.  
  303.         /* (fall through) */
  304.  
  305.     case SPECIAL_I:
  306.     case SPECIAL_D:
  307.         /*
  308.          * actual changes match one of our special case encodings -- send
  309.          * packet uncompressed.
  310.          */
  311.         goto uncompressed;
  312.  
  313.     case NEW_S | NEW_A:
  314.         if (deltaS == deltaA &&
  315.             deltaS == ntohs(cs->cs_ip.ip_len) - hlen)
  316.         {
  317.             /* special case for echoed terminal traffic */
  318.             changes = SPECIAL_I;
  319.             cp = new_seq;
  320.         }
  321.         break;
  322.  
  323.     case NEW_S:
  324.         if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen)
  325.         {
  326.             /* special case for data xfer */
  327.             changes = SPECIAL_D;
  328.             cp = new_seq;
  329.         }
  330.         break;
  331.     }
  332.  
  333.     deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
  334.     if (deltaS != 1)
  335.     {
  336.         ENCODEZ(deltaS);
  337.         changes |= NEW_I;
  338.     }
  339.     if (th->th_flags & TH_PUSH)
  340.         changes |= TCP_PUSH_BIT;
  341.     /*
  342.      * Grab the cksum before we overwrite it below.  Then update our state
  343.      * with this packet's header.
  344.      */
  345.     deltaA = ntohs(th->th_sum);
  346.     BCOPY(ip, &cs->cs_ip, hlen);
  347.  
  348.     /*
  349.      * We want to use the original packet as our compressed packet. (cp -
  350.      * new_seq) is the number of bytes we need for compressed sequence
  351.      * numbers.  In addition we need one byte for the change mask, one for
  352.      * the connection id and two for the tcp checksum. So, (cp - new_seq) + 4
  353.      * bytes of header are needed.  hlen is how many bytes of the original
  354.      * packet to toss so subtract the two to get the new packet size.
  355.      */
  356.     deltaS = cp - new_seq;
  357.     cp = (u_char *) ip;
  358.     if (compress_cid == 0 || comp->last_xmit != cs->cs_id)
  359.     {
  360.         comp->last_xmit = cs->cs_id;
  361.         hlen -= deltaS + 4;
  362.         cp += hlen;
  363.         *cp++ = changes | NEW_C;
  364.         *cp++ = cs->cs_id;
  365.     }
  366.     else
  367.     {
  368.         hlen -= deltaS + 3;
  369.         cp += hlen;
  370.         *cp++ = changes;
  371.     }
  372.     m->m_len -= hlen;
  373.     m->m_off += hlen;
  374.     *cp++ = deltaA >> 8;
  375.     *cp++ = deltaA;
  376.     BCOPY(new_seq, cp, deltaS);
  377.     INCR(sls_compressed)
  378.         return (TYPE_COMPRESSED_TCP);
  379.  
  380.     /*
  381.      * Update connection state cs & send uncompressed packet ('uncompressed'
  382.      * means a regular ip/tcp packet but with the 'conversation id' we hope
  383.      * to use on future compressed packets in the protocol field).
  384.      */
  385.  
  386.   uncompressed:
  387.     BCOPY(ip, &cs->cs_ip, hlen);
  388.     ip->ip_p = cs->cs_id;
  389.     comp->last_xmit = cs->cs_id;
  390.     return (TYPE_UNCOMPRESSED_TCP);
  391. }
  392.  
  393.  
  394. ULONG
  395.  sl_uncompress_tcp(bufp, len, type, comp)
  396.     u_char **bufp;
  397.     ULONG len;
  398.     ULONG type;
  399.     struct slcompress *comp;
  400. {
  401.     register u_char *cp;
  402.     register u_int hlen, changes;
  403.     register struct tcphdr *th;
  404.     register struct cstate *cs;
  405.     register struct ip *ip;
  406.  
  407.     switch (type)
  408.     {
  409.  
  410.     case TYPE_UNCOMPRESSED_TCP:
  411.         ip = (struct ip *) *bufp;
  412.         if (ip->ip_p >= MAX_STATES)
  413.             goto bad;
  414.         cs = &comp->rstate[comp->last_recv = ip->ip_p];
  415.         comp->flags &= ~SLF_TOSS;
  416.         ip->ip_p = IPPROTO_TCP;
  417.         hlen = ip->ip_hl;
  418.         hlen += ((struct tcphdr *) & ((int *) ip)[hlen])->th_off;
  419.         hlen <<= 2;
  420.         BCOPY(ip, &cs->cs_ip, hlen);
  421.         cs->cs_ip.ip_sum = 0;
  422.         cs->cs_hlen = hlen;
  423.         INCR(sls_uncompressedin)
  424.             return (len);
  425.  
  426.     default:
  427.         goto bad;
  428.  
  429.     case TYPE_COMPRESSED_TCP:
  430.         break;
  431.     }
  432.     /* We've got a compressed packet. */
  433.     INCR(sls_compressedin)
  434.         cp = *bufp;
  435.     changes = *cp++;
  436.     if (changes & NEW_C)
  437.     {
  438.         /*
  439.          * Make sure the state index is in range, then grab the state. If we
  440.          * have a good state index, clear the 'discard' flag.
  441.          */
  442.         if (*cp >= MAX_STATES)
  443.             goto bad;
  444.  
  445.         comp->flags &= ~SLF_TOSS;
  446.         comp->last_recv = *cp++;
  447.     }
  448.     else
  449.     {
  450.         /*
  451.          * this packet has an implicit state index.  If we've had a line
  452.          * error since the last time we got an explicit state index, we have
  453.          * to toss the packet.
  454.          */
  455.         if (comp->flags & SLF_TOSS)
  456.         {
  457.             INCR(sls_tossed)
  458.                 return (0);
  459.         }
  460.     }
  461.     cs = &comp->rstate[comp->last_recv];
  462.     hlen = cs->cs_ip.ip_hl << 2;
  463.     th = (struct tcphdr *) & ((u_char *) & cs->cs_ip)[hlen];
  464.     th->th_sum = htons((*cp << 8) | cp[1]);
  465.     cp += 2;
  466.     if (changes & TCP_PUSH_BIT)
  467.         th->th_flags |= TH_PUSH;
  468.     else
  469.         th->th_flags &= ~TH_PUSH;
  470.  
  471.     switch (changes & SPECIALS_MASK)
  472.     {
  473.     case SPECIAL_I:
  474.         {
  475.             register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
  476.             th->th_ack = htonl(ntohl(th->th_ack) + i);
  477.             th->th_seq = htonl(ntohl(th->th_seq) + i);
  478.         }
  479.         break;
  480.  
  481.     case SPECIAL_D:
  482.         th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
  483.                            - cs->cs_hlen);
  484.         break;
  485.  
  486.     default:
  487.         if (changes & NEW_U)
  488.         {
  489.             th->th_flags |= TH_URG;
  490.             DECODEU(th->th_urp)
  491.         }
  492.         else
  493.             th->th_flags &= ~TH_URG;
  494.         if (changes & NEW_W)
  495.             DECODES(th->th_win)
  496.                 if (changes & NEW_A)
  497.                 DECODEL(th->th_ack)
  498.                     if (changes & NEW_S)
  499.                     DECODEL(th->th_seq)
  500.                         break;
  501.     }
  502.     if (changes & NEW_I)
  503.     {
  504.         DECODES(cs->cs_ip.ip_id)
  505.     }
  506.     else
  507.         cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
  508.  
  509.     /*
  510.      * At this point, cp points to the first byte of data in the packet.  If
  511.      * we're not aligned on a 4-byte boundary, copy the data down so the ip &
  512.      * tcp headers will be aligned.  Then back up cp by the tcp/ip header
  513.      * length to make room for the reconstructed header (we assume the packet
  514.      * we were handed has enough space to prepend 128 bytes of header).
  515.      * Adjust the length to account for the new header & fill in the IP total
  516.      * length.
  517.      */
  518.     len -= (cp - *bufp);
  519.     if (len < 0)
  520.         /*
  521.          * we must have dropped some characters (crc should detect this but
  522.          * the old slip framing won't)
  523.          */
  524.         goto bad;
  525.  
  526.     if ((int) cp & 3)
  527.     {
  528.         if (len > 0)
  529.             (void) ovbcopy(cp, (caddr_t) ((int) cp & ~3), len);
  530.         cp = (u_char *) ((int) cp & ~3);
  531.     }
  532.     cp -= cs->cs_hlen;
  533.     len += cs->cs_hlen;
  534.     cs->cs_ip.ip_len = htons(len);
  535.     BCOPY(&cs->cs_ip, cp, cs->cs_hlen);
  536.     *bufp = cp;
  537.  
  538.     /* recompute the ip header checksum */
  539.     {
  540.         register u_short *bp = (u_short *) cp;
  541.         for (changes = 0; hlen > 0; hlen -= 2)
  542.             changes += *bp++;
  543.         changes = (changes & 0xffff) + (changes >> 16);
  544.         changes = (changes & 0xffff) + (changes >> 16);
  545.         ((struct ip *) cp)->ip_sum = ~changes;
  546.     }
  547.     return (len);
  548.   bad:
  549.     comp->flags |= SLF_TOSS;
  550.     INCR(sls_errorin)
  551.         return (0);
  552. }
  553.