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