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