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