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