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