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