1 /* $NetBSD: slcompress.c,v 1.22 2001/07/18 16:43:10 thorpej 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 68 void 69 sl_compress_init(comp) 70 struct slcompress *comp; 71 { 72 u_int i; 73 struct cstate *tstate = comp->tstate; 74 75 memset((char *)comp, 0, 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 */ 93 void 94 sl_compress_setup(comp, max_state) 95 struct slcompress *comp; 96 int max_state; 97 { 98 u_int i; 99 struct cstate *tstate = comp->tstate; 100 101 if (max_state == -1) { 102 max_state = MAX_STATES - 1; 103 memset((char *)comp, 0, sizeof(*comp)); 104 } else { 105 /* Don't reset statistics */ 106 memset((char *)comp->tstate, 0, sizeof(comp->tstate)); 107 memset((char *)comp->rstate, 0, 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 174 u_int 175 sl_compress_tcp(m, ip, comp, compress_cid) 176 struct mbuf *m; 177 struct ip *ip; 178 struct slcompress *comp; 179 int compress_cid; 180 { 181 struct cstate *cs = comp->last_cs->cs_next; 182 u_int hlen = ip->ip_hl; 183 struct tcphdr *oth; 184 struct tcphdr *th; 185 u_int deltaS, deltaA; 186 u_int changes = 0; 187 u_char new_seq[16]; 188 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 struct cstate *lcs; 226 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 */ 426 uncompressed: 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 434 int 435 sl_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((caddr_t)((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 */ 483 int 484 sl_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 u_char *cp; 493 u_int hlen, changes; 494 struct tcphdr *th; 495 struct cstate *cs; 496 struct ip *ip; 497 u_int16_t *bp; 498 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 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 624 bad: 625 comp->flags |= SLF_TOSS; 626 INCR(sls_errorin) 627 return (-1); 628 } 629