1 /* 2 * @(#)slcompress.c 7.4 (Berkeley) 07/01/89 3 * 4 * THIS CODE IS NOT FOR DISTRIBUTION! 5 * KEEP YOUR GRUBBY HANDS OFF UNLESS AUTHORIZED BY VAN JACOBSON TO COPY! 6 * ASK SAM, MIKE, OR BILL ABOUT IT. 7 * 8 * Routines to compress and uncompess tcp packets (for transmission 9 * over low speed serial lines. 10 * 11 * Copyright (c) 1988, 1989 by Van Jacobson, Lawrence Berkeley Laboratory 12 * All rights reserved. 13 */ 14 15 #include "sl.h" 16 #if NSL > 0 17 #ifndef lint 18 static char rcsid[] = "$Header: slcompress.c,v 1.10 89/06/05 08:28:52 van Exp $"; 19 #endif 20 21 #include <sys/types.h> 22 #include <sys/param.h> 23 #include <sys/mbuf.h> 24 #include <netinet/in.h> 25 #include <netinet/in_systm.h> 26 #include <netinet/ip.h> 27 #include <netinet/tcp.h> 28 29 #include "slcompress.h" 30 31 #ifndef NO_SL_STATS 32 #define INCR(counter) ++comp->counter; 33 #else 34 #define INCR(counter) 35 #endif 36 37 #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n)) 38 #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n)) 39 40 41 void 42 sl_compress_init(comp) 43 struct slcompress *comp; 44 { 45 register u_int i; 46 register struct cstate *tstate = comp->tstate; 47 48 bzero((char *)comp, sizeof(*comp)); 49 for (i = MAX_STATES - 1; i > 0; --i) { 50 tstate[i].cs_id = i; 51 tstate[i].cs_next = &tstate[i - 1]; 52 } 53 tstate[0].cs_next = &tstate[MAX_STATES - 1]; 54 tstate[0].cs_id = 0; 55 comp->last_cs = &tstate[0]; 56 comp->last_recv = 255; 57 comp->last_xmit = 255; 58 } 59 60 61 /* ENCODE encodes a number that is known to be non-zero. ENCODEZ 62 * checks for zero (since zero has to be encoded in the long, 3 byte 63 * form). 64 */ 65 #define ENCODE(n) { \ 66 if ((u_short)(n) >= 256) { \ 67 *cp++ = 0; \ 68 cp[1] = (n); \ 69 cp[0] = (n) >> 8; \ 70 cp += 2; \ 71 } else { \ 72 *cp++ = (n); \ 73 } \ 74 } 75 #define ENCODEZ(n) { \ 76 if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \ 77 *cp++ = 0; \ 78 cp[1] = (n); \ 79 cp[0] = (n) >> 8; \ 80 cp += 2; \ 81 } else { \ 82 *cp++ = (n); \ 83 } \ 84 } 85 86 #define DECODEL(f) { \ 87 if (*cp == 0) {\ 88 (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \ 89 cp += 3; \ 90 } else { \ 91 (f) = htonl(ntohl(f) + (u_long)*cp++); \ 92 } \ 93 } 94 95 #define DECODES(f) { \ 96 if (*cp == 0) {\ 97 (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \ 98 cp += 3; \ 99 } else { \ 100 (f) = htons(ntohs(f) + (u_long)*cp++); \ 101 } \ 102 } 103 104 105 u_char 106 sl_compress_tcp(m, ip, comp) 107 struct mbuf *m; 108 register struct ip *ip; 109 struct slcompress *comp; 110 { 111 register struct cstate *cs = comp->last_cs->cs_next; 112 register u_int hlen = ip->ip_hl; 113 register struct tcphdr *oth; 114 register struct tcphdr *th; 115 register u_int deltaS, deltaA; 116 register u_int changes = 0; 117 u_char new_seq[16]; 118 register u_char *cp = new_seq; 119 120 /* 121 * Bail if this is an ip fragment or if we don't have 122 * a complete ip & tcp header in the first mbuf. Otherwise, 123 * check flags to see if this is a packet we might compress 124 * and, if so, try to locate the connection state. 125 * special case the most recently used connection since 126 * it's most likely to be used again & we don't have to 127 * do any reordering if it's used. 128 */ 129 if ((ip->ip_off & 0x3fff) || m->m_len < 40) 130 return (TYPE_IP); 131 132 th = (struct tcphdr *)&((int *)ip)[hlen]; 133 if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK) 134 return (TYPE_IP); 135 136 INCR(sls_packets) 137 if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr || 138 ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr || 139 *(int *)th != ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl]) { 140 /* 141 * Wasn't the first -- search for it. 142 * 143 * States are kept in a circularly linked list with 144 * first_cs pointing to the head of the list. The 145 * list is kept in lru order by moving a state to the 146 * head of the list whenever it is referenced. Since 147 * the list is short and, empirically, the connection 148 * we want is almost always near the front, we locate 149 * states via linear search. If we don't find a state 150 * for the datagram, the oldest state is used. 151 */ 152 register struct cstate *lcs; 153 154 do { 155 lcs = cs; cs = cs->cs_next; 156 INCR(sls_searches) 157 if (*(int *)th == ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl] 158 && ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr 159 && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr) 160 goto found; 161 } while (cs != comp->last_cs); 162 INCR(sls_misses) 163 164 /* 165 * Didn't find it -- re-use oldest cstate. 166 * Send an uncompressed packet that tells 167 * the other side what connection number 168 * we're using for this conversation. Note 169 * that since the state list is circular, the 170 * oldest state points to the newest and we only 171 * need to set last_cs to update the lru linkage. 172 */ 173 comp->last_cs = lcs; 174 hlen += th->th_off; 175 hlen <<= 2; 176 goto uncompressed; 177 178 found: 179 /* 180 * Found it -- move to the front on the connection list. 181 */ 182 if (comp->last_cs == cs) 183 comp->last_cs = lcs; 184 else { 185 lcs->cs_next = cs->cs_next; 186 cs->cs_next = comp->last_cs->cs_next; 187 comp->last_cs->cs_next = cs; 188 } 189 } 190 191 /* 192 * Make sure that only what we expect to change changed. 193 */ 194 oth = (struct tcphdr *)&((int *)&cs->cs_ip)[hlen]; 195 deltaS = hlen; 196 hlen += th->th_off; 197 hlen <<= 2; 198 199 if (((u_short *)ip)[0] != ((u_short *)&cs->cs_ip)[0] || 200 ((u_short *)ip)[4] != ((u_short *)&cs->cs_ip)[4] || 201 th->th_off != oth->th_off || 202 (deltaS > 5 && 203 BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) || 204 (th->th_off > 5 && 205 BCMP(th + 1, oth + 1, (th->th_off - 5) << 2))) 206 goto uncompressed; 207 208 /* 209 * Figure out which of the changing fields changed. The 210 * receiver expects changes in the order: urgent, window, 211 * ack, seq (the order minimizes the number of temporaries 212 * needed in this section of code). 213 */ 214 if (th->th_flags & TH_URG) { 215 deltaS = ntohs(th->th_urp); 216 ENCODEZ(deltaS); 217 changes |= NEW_U; 218 } else if (th->th_urp != oth->th_urp) 219 /* argh! URG not set but urp changed -- a sensible 220 * implementation should never do this but RFC793 221 * doesn't prohibit the change so we have to deal 222 * with it. */ 223 goto uncompressed; 224 225 if (deltaS = (u_short)(ntohs(th->th_win) - ntohs(oth->th_win))) { 226 ENCODE(deltaS); 227 changes |= NEW_W; 228 } 229 230 if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) { 231 if (deltaA > 0xffff) 232 goto uncompressed; 233 ENCODE(deltaA); 234 changes |= NEW_A; 235 } 236 237 if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) { 238 if (deltaS > 0xffff) 239 goto uncompressed; 240 ENCODE(deltaS); 241 changes |= NEW_S; 242 } 243 244 switch(changes) { 245 246 case 0: 247 if (ip->ip_len != cs->cs_ip.ip_len && ntohs(ip->ip_len) != hlen) 248 break; 249 /* 250 * Nothing changed and this packet looks like a duplicate 251 * of the last or contains no data -- this is probably a 252 * retransmitted ack or window probe. Send it 253 * uncompressed in case the other side missed the 254 * compressed version. 255 * 256 * (fall through) 257 */ 258 259 case SPECIAL_I: 260 case SPECIAL_D: 261 /* 262 * actual changes match one of our special case encodings -- 263 * send packet uncompressed. 264 */ 265 goto uncompressed; 266 267 case NEW_S|NEW_A: 268 if (deltaS == deltaA && 269 deltaS == ntohs(cs->cs_ip.ip_len) - hlen) { 270 /* special case for echoed terminal traffic */ 271 changes = SPECIAL_I; 272 cp = new_seq; 273 } 274 break; 275 276 case NEW_S: 277 if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) { 278 /* special case for data xfer */ 279 changes = SPECIAL_D; 280 cp = new_seq; 281 } 282 break; 283 } 284 285 deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id); 286 if (deltaS != 1) { 287 ENCODEZ(deltaS); 288 changes |= NEW_I; 289 } 290 if (th->th_flags & TH_PUSH) 291 changes |= TCP_PUSH_BIT; 292 /* 293 * Grab the cksum before we overwrite it below. Then update our 294 * state with this packet's header. 295 */ 296 deltaA = ntohs(th->th_sum); 297 BCOPY(ip, &cs->cs_ip, hlen); 298 299 /* 300 * We want to use the original packet as our compressed packet. 301 * (cp - new_seq) is the number of bytes we need for compressed 302 * sequence numbers. In addition we need one byte for the change 303 * mask, one for the connection id and two for the tcp checksum. 304 * So, (cp - new_seq) + 4 bytes of header are needed. hlen is how 305 * many bytes of the original packet to toss so subtract the two to 306 * get the new packet size. 307 */ 308 deltaS = cp - new_seq; 309 cp = (u_char *)ip; 310 if (comp->last_xmit != cs->cs_id) { 311 comp->last_xmit = cs->cs_id; 312 hlen -= deltaS + 4; 313 cp += hlen; 314 m->m_len -= hlen; 315 m->m_data += hlen; 316 *cp++ = changes | NEW_C; 317 *cp++ = cs->cs_id; 318 } else { 319 hlen -= deltaS + 3; 320 cp += hlen; 321 m->m_len -= hlen; 322 m->m_data += hlen; 323 *cp++ = changes; 324 } 325 *cp++ = deltaA >> 8; 326 *cp++ = deltaA; 327 BCOPY(new_seq, cp, deltaS); 328 INCR(sls_compressed) 329 return (TYPE_COMPRESSED_TCP); 330 331 /* 332 * Update connection state cs & send uncompressed packet ('uncompressed' 333 * means a regular ip/tcp packet but with the 'conversation id' we hope 334 * to use on future compressed packets in the protocol field). 335 */ 336 uncompressed: 337 BCOPY(ip, &cs->cs_ip, hlen); 338 ip->ip_p = cs->cs_id; 339 comp->last_xmit = cs->cs_id; 340 return (TYPE_UNCOMPRESSED_TCP); 341 } 342 343 344 int 345 sl_uncompress_tcp(bufp, len, type, comp) 346 u_char **bufp; 347 int len; 348 u_int type; 349 struct slcompress *comp; 350 { 351 register u_char *cp; 352 register u_int hlen, changes; 353 register struct tcphdr *th; 354 register struct cstate *cs; 355 register struct ip *ip; 356 357 switch (type) { 358 359 case TYPE_UNCOMPRESSED_TCP: 360 ip = (struct ip *) *bufp; 361 if (ip->ip_p >= MAX_STATES) { 362 INCR(sls_errorin) 363 return (0); 364 } 365 cs = &comp->rstate[comp->last_recv = ip->ip_p]; 366 comp->flags &=~ SLF_TOSS; 367 ip->ip_p = IPPROTO_TCP; 368 hlen = ip->ip_hl; 369 hlen += ((struct tcphdr *)&((int *)ip)[hlen])->th_off; 370 hlen <<= 2; 371 BCOPY(ip, &cs->cs_ip, hlen); 372 cs->cs_ip.ip_sum = 0; 373 cs->cs_hlen = hlen; 374 INCR(sls_uncompressedin) 375 return (len); 376 377 case TYPE_ERROR: 378 comp->flags |= SLF_TOSS; 379 default: 380 INCR(sls_errorin) 381 return (0); 382 383 case TYPE_COMPRESSED_TCP: 384 break; 385 } 386 /* We've got a compressed packet. */ 387 INCR(sls_compressedin) 388 cp = *bufp; 389 changes = *cp++; 390 if (changes & NEW_C) { 391 /* Make sure the state index is in range, then grab the state. 392 * If we have a good state index, clear the 'discard' flag. */ 393 if (*cp >= MAX_STATES) { 394 INCR(sls_errorin) 395 return (0); 396 } 397 comp->flags &=~ SLF_TOSS; 398 comp->last_recv = *cp++; 399 } else { 400 /* this packet has an implicit state index. If we've 401 * had a line error since the last time we got an 402 * explicit state index, we have to toss the packet. */ 403 if (comp->flags & SLF_TOSS) { 404 INCR(sls_tossed) 405 return (0); 406 } 407 } 408 cs = &comp->rstate[comp->last_recv]; 409 hlen = cs->cs_ip.ip_hl << 2; 410 th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen]; 411 th->th_sum = htons((*cp << 8) | cp[1]); 412 cp += 2; 413 if (changes & TCP_PUSH_BIT) 414 th->th_flags |= TH_PUSH; 415 else 416 th->th_flags &=~ TH_PUSH; 417 418 switch (changes & SPECIALS_MASK) { 419 case SPECIAL_I: 420 { 421 register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen; 422 th->th_ack = htonl(ntohl(th->th_ack) + i); 423 th->th_seq = htonl(ntohl(th->th_seq) + i); 424 } 425 break; 426 427 case SPECIAL_D: 428 th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len) 429 - cs->cs_hlen); 430 break; 431 432 default: 433 if (changes & NEW_U) { 434 th->th_flags |= TH_URG; 435 DECODES(th->th_urp) 436 } else 437 th->th_flags &=~ TH_URG; 438 if (changes & NEW_W) 439 DECODES(th->th_win) 440 if (changes & NEW_A) 441 DECODEL(th->th_ack) 442 if (changes & NEW_S) 443 DECODEL(th->th_seq) 444 break; 445 } 446 if (changes & NEW_I) { 447 DECODES(cs->cs_ip.ip_id) 448 } else 449 cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1); 450 451 /* 452 * At this point, cp points to the first byte of data in the 453 * packet. If we're not aligned on a 4-byte boundary, copy the 454 * data down so the ip & tcp headers will be aligned. Then back up 455 * cp by the tcp/ip header length to make room for the reconstructed 456 * header (we assume the packet we were handed has enough space to 457 * prepend 128 bytes of header). Adjust the lenth to account for 458 * the new header & fill in the IP total length. 459 */ 460 len -= (cp - *bufp); 461 if (len < 0) { 462 /* we must have dropped some characters (crc should detect 463 * this but the old slip framing won't) */ 464 INCR(sls_errorin) 465 return (0); 466 } 467 if ((int)cp & 3) { 468 if (len > 0) 469 BCOPY(cp, (int)cp &~ 3, len); 470 cp = (u_char *)((int)cp &~ 3); 471 } 472 cp -= cs->cs_hlen; 473 len += cs->cs_hlen; 474 cs->cs_ip.ip_len = htons(len); 475 BCOPY(&cs->cs_ip, cp, cs->cs_hlen); 476 *bufp = cp; 477 478 /* recompute the ip header checksum */ 479 { 480 register u_short *bp = (u_short *)cp; 481 for (changes = 0; hlen > 0; hlen -= 2) 482 changes += *bp++; 483 changes = (changes & 0xffff) + (changes >> 16); 484 changes = (changes & 0xffff) + (changes >> 16); 485 ((struct ip *)cp)->ip_sum = ~ changes; 486 } 487 return (len); 488 } 489 #endif 490