1 /* $OpenBSD: bsd-comp.c,v 1.4 1997/09/05 04:26:57 millert Exp $ */ 2 /* $NetBSD: bsd-comp.c,v 1.6 1996/10/13 02:10:58 christos Exp $ */ 3 4 /* Because this code is derived from the 4.3BSD compress source: 5 * 6 * 7 * Copyright (c) 1985, 1986 The Regents of the University of California. 8 * All rights reserved. 9 * 10 * This code is derived from software contributed to Berkeley by 11 * James A. Woods, derived from original work by Spencer Thomas 12 * and Joseph Orost. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 1. Redistributions of source code must retain the above copyright 18 * notice, this list of conditions and the following disclaimer. 19 * 2. Redistributions in binary form must reproduce the above copyright 20 * notice, this list of conditions and the following disclaimer in the 21 * documentation and/or other materials provided with the distribution. 22 * 3. All advertising materials mentioning features or use of this software 23 * must display the following acknowledgement: 24 * This product includes software developed by the University of 25 * California, Berkeley and its contributors. 26 * 4. Neither the name of the University nor the names of its contributors 27 * may be used to endorse or promote products derived from this software 28 * without specific prior written permission. 29 * 30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 33 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 40 * SUCH DAMAGE. 41 */ 42 43 /* 44 * This version is for use with mbufs on BSD-derived systems. 45 */ 46 47 #include <sys/param.h> 48 #include <sys/types.h> 49 #include <sys/systm.h> 50 #include <sys/mbuf.h> 51 #include <sys/socket.h> 52 #include <net/if.h> 53 #include <net/if_types.h> 54 #include <net/ppp_defs.h> 55 #include <net/if_ppp.h> 56 57 #define PACKETPTR struct mbuf * 58 #include <net/ppp-comp.h> 59 60 #if DO_BSD_COMPRESS 61 /* 62 * PPP "BSD compress" compression 63 * The differences between this compression and the classic BSD LZW 64 * source are obvious from the requirement that the classic code worked 65 * with files while this handles arbitrarily long streams that 66 * are broken into packets. They are: 67 * 68 * When the code size expands, a block of junk is not emitted by 69 * the compressor and not expected by the decompressor. 70 * 71 * New codes are not necessarily assigned every time an old 72 * code is output by the compressor. This is because a packet 73 * end forces a code to be emitted, but does not imply that a 74 * new sequence has been seen. 75 * 76 * The compression ratio is checked at the first end of a packet 77 * after the appropriate gap. Besides simplifying and speeding 78 * things up, this makes it more likely that the transmitter 79 * and receiver will agree when the dictionary is cleared when 80 * compression is not going well. 81 */ 82 83 /* 84 * A dictionary for doing BSD compress. 85 */ 86 struct bsd_db { 87 int totlen; /* length of this structure */ 88 u_int hsize; /* size of the hash table */ 89 u_char hshift; /* used in hash function */ 90 u_char n_bits; /* current bits/code */ 91 u_char maxbits; 92 u_char debug; 93 u_char unit; 94 u_int16_t seqno; /* sequence # of next packet */ 95 u_int hdrlen; /* header length to preallocate */ 96 u_int mru; 97 u_int maxmaxcode; /* largest valid code */ 98 u_int max_ent; /* largest code in use */ 99 u_int in_count; /* uncompressed bytes, aged */ 100 u_int bytes_out; /* compressed bytes, aged */ 101 u_int ratio; /* recent compression ratio */ 102 u_int checkpoint; /* when to next check the ratio */ 103 u_int clear_count; /* times dictionary cleared */ 104 u_int incomp_count; /* incompressible packets */ 105 u_int incomp_bytes; /* incompressible bytes */ 106 u_int uncomp_count; /* uncompressed packets */ 107 u_int uncomp_bytes; /* uncompressed bytes */ 108 u_int comp_count; /* compressed packets */ 109 u_int comp_bytes; /* compressed bytes */ 110 u_int16_t *lens; /* array of lengths of codes */ 111 struct bsd_dict { 112 union { /* hash value */ 113 u_int32_t fcode; 114 struct { 115 #if BYTE_ORDER == LITTLE_ENDIAN 116 u_int16_t prefix; /* preceding code */ 117 u_char suffix; /* last character of new code */ 118 u_char pad; 119 #else 120 u_char pad; 121 u_char suffix; /* last character of new code */ 122 u_int16_t prefix; /* preceding code */ 123 #endif 124 } hs; 125 } f; 126 u_int16_t codem1; /* output of hash table -1 */ 127 u_int16_t cptr; /* map code to hash table entry */ 128 } dict[1]; 129 }; 130 131 #define BSD_OVHD 2 /* BSD compress overhead/packet */ 132 #define BSD_INIT_BITS BSD_MIN_BITS 133 134 static void *bsd_comp_alloc __P((u_char *options, int opt_len)); 135 static void *bsd_decomp_alloc __P((u_char *options, int opt_len)); 136 static void bsd_free __P((void *state)); 137 static int bsd_comp_init __P((void *state, u_char *options, int opt_len, 138 int unit, int hdrlen, int debug)); 139 static int bsd_decomp_init __P((void *state, u_char *options, int opt_len, 140 int unit, int hdrlen, int mru, int debug)); 141 static int bsd_compress __P((void *state, struct mbuf **mret, 142 struct mbuf *mp, int slen, int maxolen)); 143 static void bsd_incomp __P((void *state, struct mbuf *dmsg)); 144 static int bsd_decompress __P((void *state, struct mbuf *cmp, 145 struct mbuf **dmpp)); 146 static void bsd_reset __P((void *state)); 147 static void bsd_comp_stats __P((void *state, struct compstat *stats)); 148 149 /* 150 * Procedures exported to if_ppp.c. 151 */ 152 struct compressor ppp_bsd_compress = { 153 CI_BSD_COMPRESS, /* compress_proto */ 154 bsd_comp_alloc, /* comp_alloc */ 155 bsd_free, /* comp_free */ 156 bsd_comp_init, /* comp_init */ 157 bsd_reset, /* comp_reset */ 158 bsd_compress, /* compress */ 159 bsd_comp_stats, /* comp_stat */ 160 bsd_decomp_alloc, /* decomp_alloc */ 161 bsd_free, /* decomp_free */ 162 bsd_decomp_init, /* decomp_init */ 163 bsd_reset, /* decomp_reset */ 164 bsd_decompress, /* decompress */ 165 bsd_incomp, /* incomp */ 166 bsd_comp_stats, /* decomp_stat */ 167 }; 168 169 /* 170 * the next two codes should not be changed lightly, as they must not 171 * lie within the contiguous general code space. 172 */ 173 #define CLEAR 256 /* table clear output code */ 174 #define FIRST 257 /* first free entry */ 175 #define LAST 255 176 177 #define MAXCODE(b) ((1 << (b)) - 1) 178 #define BADCODEM1 MAXCODE(BSD_MAX_BITS) 179 180 #define BSD_HASH(prefix,suffix,hshift) ((((u_int32_t)(suffix)) << (hshift)) \ 181 ^ (u_int32_t)(prefix)) 182 #define BSD_KEY(prefix,suffix) ((((u_int32_t)(suffix)) << 16) \ 183 + (u_int32_t)(prefix)) 184 185 #define CHECK_GAP 10000 /* Ratio check interval */ 186 187 #define RATIO_SCALE_LOG 8 188 #define RATIO_SCALE (1<<RATIO_SCALE_LOG) 189 #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG) 190 191 static void bsd_clear __P((struct bsd_db *)); 192 static int bsd_check __P((struct bsd_db *)); 193 static void *bsd_alloc __P((u_char *, int, int)); 194 static int bsd_init __P((struct bsd_db *, u_char *, int, int, int, int, 195 int, int)); 196 197 /* 198 * clear the dictionary 199 */ 200 static void 201 bsd_clear(db) 202 struct bsd_db *db; 203 { 204 db->clear_count++; 205 db->max_ent = FIRST-1; 206 db->n_bits = BSD_INIT_BITS; 207 db->ratio = 0; 208 db->bytes_out = 0; 209 db->in_count = 0; 210 db->incomp_count = 0; 211 db->checkpoint = CHECK_GAP; 212 } 213 214 /* 215 * If the dictionary is full, then see if it is time to reset it. 216 * 217 * Compute the compression ratio using fixed-point arithmetic 218 * with 8 fractional bits. 219 * 220 * Since we have an infinite stream instead of a single file, 221 * watch only the local compression ratio. 222 * 223 * Since both peers must reset the dictionary at the same time even in 224 * the absence of CLEAR codes (while packets are incompressible), they 225 * must compute the same ratio. 226 */ 227 static int /* 1=output CLEAR */ 228 bsd_check(db) 229 struct bsd_db *db; 230 { 231 u_int new_ratio; 232 233 if (db->in_count >= db->checkpoint) { 234 /* age the ratio by limiting the size of the counts */ 235 if (db->in_count >= RATIO_MAX 236 || db->bytes_out >= RATIO_MAX) { 237 db->in_count -= db->in_count/4; 238 db->bytes_out -= db->bytes_out/4; 239 } 240 241 db->checkpoint = db->in_count + CHECK_GAP; 242 243 if (db->max_ent >= db->maxmaxcode) { 244 /* Reset the dictionary only if the ratio is worse, 245 * or if it looks as if it has been poisoned 246 * by incompressible data. 247 * 248 * This does not overflow, because 249 * db->in_count <= RATIO_MAX. 250 */ 251 new_ratio = db->in_count << RATIO_SCALE_LOG; 252 if (db->bytes_out != 0) 253 new_ratio /= db->bytes_out; 254 255 if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE) { 256 bsd_clear(db); 257 return 1; 258 } 259 db->ratio = new_ratio; 260 } 261 } 262 return 0; 263 } 264 265 /* 266 * Return statistics. 267 */ 268 static void 269 bsd_comp_stats(state, stats) 270 void *state; 271 struct compstat *stats; 272 { 273 struct bsd_db *db = (struct bsd_db *) state; 274 u_int out; 275 276 stats->unc_bytes = db->uncomp_bytes; 277 stats->unc_packets = db->uncomp_count; 278 stats->comp_bytes = db->comp_bytes; 279 stats->comp_packets = db->comp_count; 280 stats->inc_bytes = db->incomp_bytes; 281 stats->inc_packets = db->incomp_count; 282 stats->ratio = db->in_count; 283 out = db->bytes_out; 284 if (stats->ratio <= 0x7fffff) 285 stats->ratio <<= 8; 286 else 287 out >>= 8; 288 if (out != 0) 289 stats->ratio /= out; 290 } 291 292 /* 293 * Reset state, as on a CCP ResetReq. 294 */ 295 static void 296 bsd_reset(state) 297 void *state; 298 { 299 struct bsd_db *db = (struct bsd_db *) state; 300 301 db->seqno = 0; 302 bsd_clear(db); 303 db->clear_count = 0; 304 } 305 306 /* 307 * Allocate space for a (de) compressor. 308 */ 309 static void * 310 bsd_alloc(options, opt_len, decomp) 311 u_char *options; 312 int opt_len, decomp; 313 { 314 int bits; 315 u_int newlen, hsize, hshift, maxmaxcode; 316 struct bsd_db *db; 317 318 if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS 319 || options[1] != CILEN_BSD_COMPRESS 320 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION) 321 return NULL; 322 bits = BSD_NBITS(options[2]); 323 switch (bits) { 324 case 9: /* needs 82152 for both directions */ 325 case 10: /* needs 84144 */ 326 case 11: /* needs 88240 */ 327 case 12: /* needs 96432 */ 328 hsize = 5003; 329 hshift = 4; 330 break; 331 case 13: /* needs 176784 */ 332 hsize = 9001; 333 hshift = 5; 334 break; 335 case 14: /* needs 353744 */ 336 hsize = 18013; 337 hshift = 6; 338 break; 339 case 15: /* needs 691440 */ 340 hsize = 35023; 341 hshift = 7; 342 break; 343 case 16: /* needs 1366160--far too much, */ 344 /* hsize = 69001; */ /* and 69001 is too big for cptr */ 345 /* hshift = 8; */ /* in struct bsd_db */ 346 /* break; */ 347 default: 348 return NULL; 349 } 350 351 maxmaxcode = MAXCODE(bits); 352 newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0])); 353 MALLOC(db, struct bsd_db *, newlen, M_DEVBUF, M_NOWAIT); 354 if (!db) 355 return NULL; 356 bzero(db, sizeof(*db) - sizeof(db->dict)); 357 358 if (!decomp) { 359 db->lens = NULL; 360 } else { 361 MALLOC(db->lens, u_int16_t *, (maxmaxcode+1) * sizeof(db->lens[0]), 362 M_DEVBUF, M_NOWAIT); 363 if (!db->lens) { 364 FREE(db, M_DEVBUF); 365 return NULL; 366 } 367 } 368 369 db->totlen = newlen; 370 db->hsize = hsize; 371 db->hshift = hshift; 372 db->maxmaxcode = maxmaxcode; 373 db->maxbits = bits; 374 375 return (void *) db; 376 } 377 378 static void 379 bsd_free(state) 380 void *state; 381 { 382 struct bsd_db *db = (struct bsd_db *) state; 383 384 if (db->lens) 385 FREE(db->lens, M_DEVBUF); 386 FREE(db, M_DEVBUF); 387 } 388 389 static void * 390 bsd_comp_alloc(options, opt_len) 391 u_char *options; 392 int opt_len; 393 { 394 return bsd_alloc(options, opt_len, 0); 395 } 396 397 static void * 398 bsd_decomp_alloc(options, opt_len) 399 u_char *options; 400 int opt_len; 401 { 402 return bsd_alloc(options, opt_len, 1); 403 } 404 405 /* 406 * Initialize the database. 407 */ 408 static int 409 bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp) 410 struct bsd_db *db; 411 u_char *options; 412 int opt_len, unit, hdrlen, mru, debug, decomp; 413 { 414 int i; 415 416 if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS 417 || options[1] != CILEN_BSD_COMPRESS 418 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION 419 || BSD_NBITS(options[2]) != db->maxbits 420 || (decomp && db->lens == NULL)) 421 return 0; 422 423 if (decomp) { 424 i = LAST+1; 425 while (i != 0) 426 db->lens[--i] = 1; 427 } 428 i = db->hsize; 429 while (i != 0) { 430 db->dict[--i].codem1 = BADCODEM1; 431 db->dict[i].cptr = 0; 432 } 433 434 db->unit = unit; 435 db->hdrlen = hdrlen; 436 db->mru = mru; 437 #ifndef DEBUG 438 if (debug) 439 #endif 440 db->debug = 1; 441 442 bsd_reset(db); 443 444 return 1; 445 } 446 447 static int 448 bsd_comp_init(state, options, opt_len, unit, hdrlen, debug) 449 void *state; 450 u_char *options; 451 int opt_len, unit, hdrlen, debug; 452 { 453 return bsd_init((struct bsd_db *) state, options, opt_len, 454 unit, hdrlen, 0, debug, 0); 455 } 456 457 static int 458 bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug) 459 void *state; 460 u_char *options; 461 int opt_len, unit, hdrlen, mru, debug; 462 { 463 return bsd_init((struct bsd_db *) state, options, opt_len, 464 unit, hdrlen, mru, debug, 1); 465 } 466 467 468 /* 469 * compress a packet 470 * One change from the BSD compress command is that when the 471 * code size expands, we do not output a bunch of padding. 472 */ 473 int /* new slen */ 474 bsd_compress(state, mret, mp, slen, maxolen) 475 void *state; 476 struct mbuf **mret; /* return compressed mbuf chain here */ 477 struct mbuf *mp; /* from here */ 478 int slen; /* uncompressed length */ 479 int maxolen; /* max compressed length */ 480 { 481 struct bsd_db *db = (struct bsd_db *) state; 482 int hshift = db->hshift; 483 u_int max_ent = db->max_ent; 484 u_int n_bits = db->n_bits; 485 u_int bitno = 32; 486 u_int32_t accm = 0, fcode; 487 struct bsd_dict *dictp; 488 u_char c; 489 int hval, disp, ent, ilen; 490 u_char *rptr, *wptr; 491 u_char *cp_end; 492 int olen; 493 struct mbuf *m; 494 495 #define PUTBYTE(v) { \ 496 ++olen; \ 497 if (wptr) { \ 498 *wptr++ = (v); \ 499 if (wptr >= cp_end) { \ 500 m->m_len = wptr - mtod(m, u_char *); \ 501 MGET(m->m_next, M_DONTWAIT, MT_DATA); \ 502 m = m->m_next; \ 503 if (m) { \ 504 m->m_len = 0; \ 505 if (maxolen - olen > MLEN) \ 506 MCLGET(m, M_DONTWAIT); \ 507 wptr = mtod(m, u_char *); \ 508 cp_end = wptr + M_TRAILINGSPACE(m); \ 509 } else \ 510 wptr = NULL; \ 511 } \ 512 } \ 513 } 514 515 #define OUTPUT(ent) { \ 516 bitno -= n_bits; \ 517 accm |= ((ent) << bitno); \ 518 do { \ 519 PUTBYTE(accm >> 24); \ 520 accm <<= 8; \ 521 bitno += 8; \ 522 } while (bitno <= 24); \ 523 } 524 525 /* 526 * If the protocol is not in the range we're interested in, 527 * just return without compressing the packet. If it is, 528 * the protocol becomes the first byte to compress. 529 */ 530 rptr = mtod(mp, u_char *); 531 ent = PPP_PROTOCOL(rptr); 532 if (ent < 0x21 || ent > 0xf9) { 533 *mret = NULL; 534 return slen; 535 } 536 537 /* Don't generate compressed packets which are larger than 538 the uncompressed packet. */ 539 if (maxolen > slen) 540 maxolen = slen; 541 542 /* Allocate one mbuf to start with. */ 543 MGET(m, M_DONTWAIT, MT_DATA); 544 *mret = m; 545 if (m != NULL) { 546 m->m_len = 0; 547 if (maxolen + db->hdrlen > MLEN) 548 MCLGET(m, M_DONTWAIT); 549 m->m_data += db->hdrlen; 550 wptr = mtod(m, u_char *); 551 cp_end = wptr + M_TRAILINGSPACE(m); 552 } else 553 wptr = cp_end = NULL; 554 555 /* 556 * Copy the PPP header over, changing the protocol, 557 * and install the 2-byte packet sequence number. 558 */ 559 if (wptr) { 560 *wptr++ = PPP_ADDRESS(rptr); /* assumes the ppp header is */ 561 *wptr++ = PPP_CONTROL(rptr); /* all in one mbuf */ 562 *wptr++ = 0; /* change the protocol */ 563 *wptr++ = PPP_COMP; 564 *wptr++ = db->seqno >> 8; 565 *wptr++ = db->seqno; 566 } 567 ++db->seqno; 568 569 olen = 0; 570 rptr += PPP_HDRLEN; 571 slen = mp->m_len - PPP_HDRLEN; 572 ilen = slen + 1; 573 for (;;) { 574 if (slen <= 0) { 575 mp = mp->m_next; 576 if (!mp) 577 break; 578 rptr = mtod(mp, u_char *); 579 slen = mp->m_len; 580 if (!slen) 581 continue; /* handle 0-length buffers */ 582 ilen += slen; 583 } 584 585 slen--; 586 c = *rptr++; 587 fcode = BSD_KEY(ent, c); 588 hval = BSD_HASH(ent, c, hshift); 589 dictp = &db->dict[hval]; 590 591 /* Validate and then check the entry. */ 592 if (dictp->codem1 >= max_ent) 593 goto nomatch; 594 if (dictp->f.fcode == fcode) { 595 ent = dictp->codem1+1; 596 continue; /* found (prefix,suffix) */ 597 } 598 599 /* continue probing until a match or invalid entry */ 600 disp = (hval == 0) ? 1 : hval; 601 do { 602 hval += disp; 603 if (hval >= db->hsize) 604 hval -= db->hsize; 605 dictp = &db->dict[hval]; 606 if (dictp->codem1 >= max_ent) 607 goto nomatch; 608 } while (dictp->f.fcode != fcode); 609 ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */ 610 continue; 611 612 nomatch: 613 OUTPUT(ent); /* output the prefix */ 614 615 /* code -> hashtable */ 616 if (max_ent < db->maxmaxcode) { 617 struct bsd_dict *dictp2; 618 /* expand code size if needed */ 619 if (max_ent >= MAXCODE(n_bits)) 620 db->n_bits = ++n_bits; 621 622 /* Invalidate old hash table entry using 623 * this code, and then take it over. 624 */ 625 dictp2 = &db->dict[max_ent+1]; 626 if (db->dict[dictp2->cptr].codem1 == max_ent) 627 db->dict[dictp2->cptr].codem1 = BADCODEM1; 628 dictp2->cptr = hval; 629 dictp->codem1 = max_ent; 630 dictp->f.fcode = fcode; 631 632 db->max_ent = ++max_ent; 633 } 634 ent = c; 635 } 636 637 OUTPUT(ent); /* output the last code */ 638 db->bytes_out += olen; 639 db->in_count += ilen; 640 if (bitno < 32) 641 ++db->bytes_out; /* count complete bytes */ 642 643 if (bsd_check(db)) 644 OUTPUT(CLEAR); /* do not count the CLEAR */ 645 646 /* 647 * Pad dribble bits of last code with ones. 648 * Do not emit a completely useless byte of ones. 649 */ 650 if (bitno != 32) 651 PUTBYTE((accm | (0xff << (bitno-8))) >> 24); 652 653 if (m != NULL) { 654 m->m_len = wptr - mtod(m, u_char *); 655 m->m_next = NULL; 656 } 657 658 /* 659 * Increase code size if we would have without the packet 660 * boundary and as the decompressor will. 661 */ 662 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) 663 db->n_bits++; 664 665 db->uncomp_bytes += ilen; 666 ++db->uncomp_count; 667 if (olen + PPP_HDRLEN + BSD_OVHD > maxolen) { 668 /* throw away the compressed stuff if it is longer than uncompressed */ 669 if (*mret != NULL) { 670 m_freem(*mret); 671 *mret = NULL; 672 } 673 ++db->incomp_count; 674 db->incomp_bytes += ilen; 675 } else { 676 ++db->comp_count; 677 db->comp_bytes += olen + BSD_OVHD; 678 } 679 680 return olen + PPP_HDRLEN + BSD_OVHD; 681 #undef OUTPUT 682 #undef PUTBYTE 683 } 684 685 686 /* 687 * Update the "BSD Compress" dictionary on the receiver for 688 * incompressible data by pretending to compress the incoming data. 689 */ 690 static void 691 bsd_incomp(state, dmsg) 692 void *state; 693 struct mbuf *dmsg; 694 { 695 struct bsd_db *db = (struct bsd_db *) state; 696 u_int hshift = db->hshift; 697 u_int max_ent = db->max_ent; 698 u_int n_bits = db->n_bits; 699 struct bsd_dict *dictp; 700 u_int32_t fcode; 701 u_char c; 702 u_int32_t hval, disp; 703 int slen, ilen; 704 u_int bitno = 7; 705 u_char *rptr; 706 u_int ent; 707 708 /* 709 * If the protocol is not in the range we're interested in, 710 * just return without looking at the packet. If it is, 711 * the protocol becomes the first byte to "compress". 712 */ 713 rptr = mtod(dmsg, u_char *); 714 ent = PPP_PROTOCOL(rptr); 715 if (ent < 0x21 || ent > 0xf9) 716 return; 717 718 db->incomp_count++; 719 db->seqno++; 720 ilen = 1; /* count the protocol as 1 byte */ 721 rptr += PPP_HDRLEN; 722 slen = dmsg->m_len - PPP_HDRLEN; 723 for (;;) { 724 if (slen <= 0) { 725 dmsg = dmsg->m_next; 726 if (!dmsg) 727 break; 728 rptr = mtod(dmsg, u_char *); 729 slen = dmsg->m_len; 730 continue; 731 } 732 ilen += slen; 733 734 do { 735 c = *rptr++; 736 fcode = BSD_KEY(ent, c); 737 hval = BSD_HASH(ent, c, hshift); 738 dictp = &db->dict[hval]; 739 740 /* validate and then check the entry */ 741 if (dictp->codem1 >= max_ent) 742 goto nomatch; 743 if (dictp->f.fcode == fcode) { 744 ent = dictp->codem1+1; 745 continue; /* found (prefix,suffix) */ 746 } 747 748 /* continue probing until a match or invalid entry */ 749 disp = (hval == 0) ? 1 : hval; 750 do { 751 hval += disp; 752 if (hval >= db->hsize) 753 hval -= db->hsize; 754 dictp = &db->dict[hval]; 755 if (dictp->codem1 >= max_ent) 756 goto nomatch; 757 } while (dictp->f.fcode != fcode); 758 ent = dictp->codem1+1; 759 continue; /* finally found (prefix,suffix) */ 760 761 nomatch: /* output (count) the prefix */ 762 bitno += n_bits; 763 764 /* code -> hashtable */ 765 if (max_ent < db->maxmaxcode) { 766 struct bsd_dict *dictp2; 767 /* expand code size if needed */ 768 if (max_ent >= MAXCODE(n_bits)) 769 db->n_bits = ++n_bits; 770 771 /* Invalidate previous hash table entry 772 * assigned this code, and then take it over. 773 */ 774 dictp2 = &db->dict[max_ent+1]; 775 if (db->dict[dictp2->cptr].codem1 == max_ent) 776 db->dict[dictp2->cptr].codem1 = BADCODEM1; 777 dictp2->cptr = hval; 778 dictp->codem1 = max_ent; 779 dictp->f.fcode = fcode; 780 781 db->max_ent = ++max_ent; 782 db->lens[max_ent] = db->lens[ent]+1; 783 } 784 ent = c; 785 } while (--slen != 0); 786 } 787 bitno += n_bits; /* output (count) the last code */ 788 db->bytes_out += bitno/8; 789 db->in_count += ilen; 790 (void)bsd_check(db); 791 792 ++db->incomp_count; 793 db->incomp_bytes += ilen; 794 ++db->uncomp_count; 795 db->uncomp_bytes += ilen; 796 797 /* Increase code size if we would have without the packet 798 * boundary and as the decompressor will. 799 */ 800 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) 801 db->n_bits++; 802 } 803 804 805 /* 806 * Decompress "BSD Compress". 807 * 808 * Because of patent problems, we return DECOMP_ERROR for errors 809 * found by inspecting the input data and for system problems, but 810 * DECOMP_FATALERROR for any errors which could possibly be said to 811 * be being detected "after" decompression. For DECOMP_ERROR, 812 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be 813 * infringing a patent of Motorola's if we do, so we take CCP down 814 * instead. 815 * 816 * Given that the frame has the correct sequence number and a good FCS, 817 * errors such as invalid codes in the input most likely indicate a 818 * bug, so we return DECOMP_FATALERROR for them in order to turn off 819 * compression, even though they are detected by inspecting the input. 820 */ 821 int 822 bsd_decompress(state, cmp, dmpp) 823 void *state; 824 struct mbuf *cmp, **dmpp; 825 { 826 struct bsd_db *db = (struct bsd_db *) state; 827 u_int max_ent = db->max_ent; 828 u_int32_t accm = 0; 829 u_int bitno = 32; /* 1st valid bit in accm */ 830 u_int n_bits = db->n_bits; 831 u_int tgtbitno = 32-n_bits; /* bitno when we have a code */ 832 struct bsd_dict *dictp; 833 int explen, i, seq, len; 834 u_int incode, oldcode, finchar; 835 u_char *p, *rptr, *wptr; 836 struct mbuf *m, *dmp, *mret; 837 int adrs, ctrl, ilen; 838 int space, codelen, extra; 839 840 /* 841 * Save the address/control from the PPP header 842 * and then get the sequence number. 843 */ 844 *dmpp = NULL; 845 rptr = mtod(cmp, u_char *); 846 adrs = PPP_ADDRESS(rptr); 847 ctrl = PPP_CONTROL(rptr); 848 rptr += PPP_HDRLEN; 849 len = cmp->m_len - PPP_HDRLEN; 850 seq = 0; 851 for (i = 0; i < 2; ++i) { 852 while (len <= 0) { 853 cmp = cmp->m_next; 854 if (cmp == NULL) 855 return DECOMP_ERROR; 856 rptr = mtod(cmp, u_char *); 857 len = cmp->m_len; 858 } 859 seq = (seq << 8) + *rptr++; 860 --len; 861 } 862 863 /* 864 * Check the sequence number and give up if it differs from 865 * the value we're expecting. 866 */ 867 if (seq != db->seqno) { 868 if (db->debug) 869 printf("bsd_decomp%d: bad sequence # %d, expected %d\n", 870 db->unit, seq, db->seqno - 1); 871 return DECOMP_ERROR; 872 } 873 ++db->seqno; 874 875 /* 876 * Allocate one mbuf to start with. 877 */ 878 MGETHDR(dmp, M_DONTWAIT, MT_DATA); 879 if (dmp == NULL) 880 return DECOMP_ERROR; 881 mret = dmp; 882 dmp->m_len = 0; 883 dmp->m_next = NULL; 884 MCLGET(dmp, M_DONTWAIT); 885 dmp->m_data += db->hdrlen; 886 wptr = mtod(dmp, u_char *); 887 space = M_TRAILINGSPACE(dmp) - PPP_HDRLEN + 1; 888 889 /* 890 * Fill in the ppp header, but not the last byte of the protocol 891 * (that comes from the decompressed data). 892 */ 893 wptr[0] = adrs; 894 wptr[1] = ctrl; 895 wptr[2] = 0; 896 wptr += PPP_HDRLEN - 1; 897 898 ilen = len; 899 oldcode = CLEAR; 900 explen = 0; 901 for (;;) { 902 if (len == 0) { 903 cmp = cmp->m_next; 904 if (!cmp) /* quit at end of message */ 905 break; 906 rptr = mtod(cmp, u_char *); 907 len = cmp->m_len; 908 ilen += len; 909 continue; /* handle 0-length buffers */ 910 } 911 912 /* 913 * Accumulate bytes until we have a complete code. 914 * Then get the next code, relying on the 32-bit, 915 * unsigned accm to mask the result. 916 */ 917 bitno -= 8; 918 accm |= *rptr++ << bitno; 919 --len; 920 if (tgtbitno < bitno) 921 continue; 922 incode = accm >> tgtbitno; 923 accm <<= n_bits; 924 bitno += n_bits; 925 926 if (incode == CLEAR) { 927 /* 928 * The dictionary must only be cleared at 929 * the end of a packet. But there could be an 930 * empty mbuf at the end. 931 */ 932 if (len > 0 || cmp->m_next != NULL) { 933 while ((cmp = cmp->m_next) != NULL) 934 len += cmp->m_len; 935 if (len > 0) { 936 m_freem(mret); 937 if (db->debug) 938 printf("bsd_decomp%d: bad CLEAR\n", db->unit); 939 return DECOMP_FATALERROR; /* probably a bug */ 940 } 941 } 942 bsd_clear(db); 943 explen = ilen = 0; 944 break; 945 } 946 947 if (incode > max_ent + 2 || incode > db->maxmaxcode 948 || (incode > max_ent && oldcode == CLEAR)) { 949 m_freem(mret); 950 if (db->debug) { 951 printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ", 952 db->unit, incode, oldcode); 953 printf("max_ent=0x%x explen=%d seqno=%d\n", 954 max_ent, explen, db->seqno); 955 } 956 return DECOMP_FATALERROR; /* probably a bug */ 957 } 958 959 /* Special case for KwKwK string. */ 960 if (incode > max_ent) { 961 finchar = oldcode; 962 extra = 1; 963 } else { 964 finchar = incode; 965 extra = 0; 966 } 967 968 codelen = db->lens[finchar]; 969 explen += codelen + extra; 970 if (explen > db->mru + 1) { 971 m_freem(mret); 972 if (db->debug) { 973 printf("bsd_decomp%d: ran out of mru\n", db->unit); 974 #ifdef DEBUG 975 while ((cmp = cmp->m_next) != NULL) 976 len += cmp->m_len; 977 printf(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n", 978 len, finchar, codelen, explen); 979 #endif 980 } 981 return DECOMP_FATALERROR; 982 } 983 984 /* 985 * For simplicity, the decoded characters go in a single mbuf, 986 * so we allocate a single extra cluster mbuf if necessary. 987 */ 988 if ((space -= codelen + extra) < 0) { 989 dmp->m_len = wptr - mtod(dmp, u_char *); 990 MGET(m, M_DONTWAIT, MT_DATA); 991 if (m == NULL) { 992 m_freem(mret); 993 return DECOMP_ERROR; 994 } 995 m->m_len = 0; 996 m->m_next = NULL; 997 dmp->m_next = m; 998 MCLGET(m, M_DONTWAIT); 999 space = M_TRAILINGSPACE(m) - (codelen + extra); 1000 if (space < 0) { 1001 /* now that's what I call *compression*. */ 1002 m_freem(mret); 1003 return DECOMP_ERROR; 1004 } 1005 dmp = m; 1006 wptr = mtod(dmp, u_char *); 1007 } 1008 1009 /* 1010 * Decode this code and install it in the decompressed buffer. 1011 */ 1012 p = (wptr += codelen); 1013 while (finchar > LAST) { 1014 dictp = &db->dict[db->dict[finchar].cptr]; 1015 #ifdef DEBUG 1016 if (--codelen <= 0 || dictp->codem1 != finchar-1) 1017 goto bad; 1018 #endif 1019 *--p = dictp->f.hs.suffix; 1020 finchar = dictp->f.hs.prefix; 1021 } 1022 *--p = finchar; 1023 1024 #ifdef DEBUG 1025 if (--codelen != 0) 1026 printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n", 1027 db->unit, codelen, incode, max_ent); 1028 #endif 1029 1030 if (extra) /* the KwKwK case again */ 1031 *wptr++ = finchar; 1032 1033 /* 1034 * If not first code in a packet, and 1035 * if not out of code space, then allocate a new code. 1036 * 1037 * Keep the hash table correct so it can be used 1038 * with uncompressed packets. 1039 */ 1040 if (oldcode != CLEAR && max_ent < db->maxmaxcode) { 1041 struct bsd_dict *dictp2; 1042 u_int32_t fcode; 1043 u_int32_t hval, disp; 1044 1045 fcode = BSD_KEY(oldcode,finchar); 1046 hval = BSD_HASH(oldcode,finchar,db->hshift); 1047 dictp = &db->dict[hval]; 1048 1049 /* look for a free hash table entry */ 1050 if (dictp->codem1 < max_ent) { 1051 disp = (hval == 0) ? 1 : hval; 1052 do { 1053 hval += disp; 1054 if (hval >= db->hsize) 1055 hval -= db->hsize; 1056 dictp = &db->dict[hval]; 1057 } while (dictp->codem1 < max_ent); 1058 } 1059 1060 /* 1061 * Invalidate previous hash table entry 1062 * assigned this code, and then take it over 1063 */ 1064 dictp2 = &db->dict[max_ent+1]; 1065 if (db->dict[dictp2->cptr].codem1 == max_ent) { 1066 db->dict[dictp2->cptr].codem1 = BADCODEM1; 1067 } 1068 dictp2->cptr = hval; 1069 dictp->codem1 = max_ent; 1070 dictp->f.fcode = fcode; 1071 1072 db->max_ent = ++max_ent; 1073 db->lens[max_ent] = db->lens[oldcode]+1; 1074 1075 /* Expand code size if needed. */ 1076 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) { 1077 db->n_bits = ++n_bits; 1078 tgtbitno = 32-n_bits; 1079 } 1080 } 1081 oldcode = incode; 1082 } 1083 dmp->m_len = wptr - mtod(dmp, u_char *); 1084 1085 /* 1086 * Keep the checkpoint right so that incompressible packets 1087 * clear the dictionary at the right times. 1088 */ 1089 db->bytes_out += ilen; 1090 db->in_count += explen; 1091 if (bsd_check(db) && db->debug) { 1092 printf("bsd_decomp%d: peer should have cleared dictionary\n", 1093 db->unit); 1094 } 1095 1096 ++db->comp_count; 1097 db->comp_bytes += ilen + BSD_OVHD; 1098 ++db->uncomp_count; 1099 db->uncomp_bytes += explen; 1100 1101 *dmpp = mret; 1102 return DECOMP_OK; 1103 1104 #ifdef DEBUG 1105 bad: 1106 if (codelen <= 0) { 1107 printf("bsd_decomp%d: fell off end of chain ", db->unit); 1108 printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n", 1109 incode, finchar, db->dict[finchar].cptr, max_ent); 1110 } else if (dictp->codem1 != finchar-1) { 1111 printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ", 1112 db->unit, incode, finchar); 1113 printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode, 1114 db->dict[finchar].cptr, dictp->codem1); 1115 } 1116 m_freem(mret); 1117 return DECOMP_FATALERROR; 1118 #endif /* DEBUG */ 1119 } 1120 #endif /* DO_BSD_COMPRESS */ 1121