1/* $NetBSD: bsd-comp.c,v 1.3 2021/01/09 16:39:28 christos Exp $ */ 2 3/* Because this code is derived from the 4.3BSD compress source: 4 * 5 * 6 * Copyright (c) 1985, 1986 The Regents of the University of California. 7 * All rights reserved. 8 * 9 * This code is derived from software contributed to Berkeley by 10 * James A. Woods, derived from original work by Spencer Thomas 11 * and Joseph Orost. 12 * 13 * Redistribution and use in source and binary forms, with or without 14 * modification, are permitted provided that the following conditions 15 * are met: 16 * 1. Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * 2. Redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution. 21 * 3. All advertising materials mentioning features or use of this software 22 * must display the following acknowledgement: 23 * This product includes software developed by the University of 24 * California, Berkeley and its contributors. 25 * 4. Neither the name of the University nor the names of its contributors 26 * may be used to endorse or promote products derived from this software 27 * without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 39 * SUCH DAMAGE. 40 */ 41 42#include <sys/cdefs.h> 43__RCSID("$NetBSD: bsd-comp.c,v 1.3 2021/01/09 16:39:28 christos Exp $"); 44 45/* 46 * Id: bsd-comp.c,v 1.4 2004/01/17 05:47:55 carlsonj Exp 47 */ 48 49#include <sys/types.h> 50#include <stdio.h> 51#include <stddef.h> 52#include <stdlib.h> 53#include <string.h> 54#include "pppdump.h" 55#include "ppp_defs.h" 56#include "ppp-comp.h" 57 58#if DO_BSD_COMPRESS 59 60/* 61 * PPP "BSD compress" compression 62 * The differences between this compression and the classic BSD LZW 63 * source are obvious from the requirement that the classic code worked 64 * with files while this handles arbitrarily long streams that 65 * are broken into packets. They are: 66 * 67 * When the code size expands, a block of junk is not emitted by 68 * the compressor and not expected by the decompressor. 69 * 70 * New codes are not necessarily assigned every time an old 71 * code is output by the compressor. This is because a packet 72 * end forces a code to be emitted, but does not imply that a 73 * new sequence has been seen. 74 * 75 * The compression ratio is checked at the first end of a packet 76 * after the appropriate gap. Besides simplifying and speeding 77 * things up, this makes it more likely that the transmitter 78 * and receiver will agree when the dictionary is cleared when 79 * compression is not going well. 80 */ 81 82/* 83 * A dictionary for doing BSD compress. 84 */ 85struct bsd_db { 86 int totlen; /* length of this structure */ 87 u_int hsize; /* size of the hash table */ 88 u_char hshift; /* used in hash function */ 89 u_char n_bits; /* current bits/code */ 90 u_char maxbits; 91 u_char debug; 92 u_char unit; 93 u_short seqno; /* sequence number of next packet */ 94 u_int hdrlen; /* header length to preallocate */ 95 u_int mru; 96 u_int maxmaxcode; /* largest valid code */ 97 u_int max_ent; /* largest code in use */ 98 u_int in_count; /* uncompressed bytes, aged */ 99 u_int bytes_out; /* compressed bytes, aged */ 100 u_int ratio; /* recent compression ratio */ 101 u_int checkpoint; /* when to next check the ratio */ 102 u_int clear_count; /* times dictionary cleared */ 103 u_int incomp_count; /* incompressible packets */ 104 u_int incomp_bytes; /* incompressible bytes */ 105 u_int uncomp_count; /* uncompressed packets */ 106 u_int uncomp_bytes; /* uncompressed bytes */ 107 u_int comp_count; /* compressed packets */ 108 u_int comp_bytes; /* compressed bytes */ 109 u_short *lens; /* array of lengths of codes */ 110 struct bsd_dict { 111 union { /* hash value */ 112 u_int32_t fcode; 113 struct { 114#ifdef BSD_LITTLE_ENDIAN 115 u_short prefix; /* preceding code */ 116 u_char suffix; /* last character of new code */ 117 u_char pad; 118#else 119 u_char pad; 120 u_char suffix; /* last character of new code */ 121 u_short prefix; /* preceding code */ 122#endif 123 } hs; 124 } f; 125 u_short codem1; /* output of hash table -1 */ 126 u_short cptr; /* map code to hash table entry */ 127 } dict[1]; 128}; 129 130#define BSD_OVHD 2 /* BSD compress overhead/packet */ 131#define BSD_INIT_BITS BSD_MIN_BITS 132 133static void *bsd_decomp_alloc(u_char *options, int opt_len); 134static void bsd_free(void *state); 135static int bsd_decomp_init(void *state, u_char *options, int opt_len, 136 int unit, int hdrlen, int mru, int debug); 137static void bsd_incomp(void *state, PACKETPTR in); 138static int bsd_decompress(void *state, PACKETPTR in, PACKETPTR *out); 139static void bsd_reset(void *state); 140static void bsd_comp_stats(void *state, struct compstat *stats); 141 142/* 143 * Exported procedures. 144 */ 145struct compressor ppp_bsd_compress = { 146 CI_BSD_COMPRESS, /* compress_proto */ 147 NULL, /* comp_alloc */ 148 NULL, /* comp_free */ 149 NULL, /* comp_init */ 150 NULL, /* comp_reset */ 151 NULL, /* comp_compress */ 152 NULL, /* comp_stat */ 153 bsd_decomp_alloc, /* decomp_alloc */ 154 bsd_free, /* decomp_free */ 155 bsd_decomp_init, /* decomp_init */ 156 bsd_reset, /* decomp_reset */ 157 bsd_decompress, /* decompress */ 158 bsd_incomp, /* incomp */ 159 bsd_comp_stats, /* decomp_stat */ 160}; 161 162/* 163 * the next two codes should not be changed lightly, as they must not 164 * lie within the contiguous general code space. 165 */ 166#define CLEAR 256 /* table clear output code */ 167#define FIRST 257 /* first free entry */ 168#define LAST 255 169 170#define MAXCODE(b) ((1 << (b)) - 1) 171#define BADCODEM1 MAXCODE(BSD_MAX_BITS) 172 173#define BSD_HASH(prefix,suffix,hshift) ((((u_int32_t)(suffix)) << (hshift)) \ 174 ^ (u_int32_t)(prefix)) 175#define BSD_KEY(prefix,suffix) ((((u_int32_t)(suffix)) << 16) \ 176 + (u_int32_t)(prefix)) 177 178#define CHECK_GAP 10000 /* Ratio check interval */ 179 180#define RATIO_SCALE_LOG 8 181#define RATIO_SCALE (1<<RATIO_SCALE_LOG) 182#define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG) 183 184static void bsd_clear __P((struct bsd_db *)); 185static int bsd_check __P((struct bsd_db *)); 186static void *bsd_alloc __P((u_char *, int, int)); 187static int bsd_init __P((struct bsd_db *, u_char *, int, int, int, int, 188 int, int)); 189 190/* 191 * clear the dictionary 192 */ 193static void 194bsd_clear(struct bsd_db *db) 195{ 196 db->clear_count++; 197 db->max_ent = FIRST-1; 198 db->n_bits = BSD_INIT_BITS; 199 db->ratio = 0; 200 db->bytes_out = 0; 201 db->in_count = 0; 202 db->checkpoint = CHECK_GAP; 203} 204 205/* 206 * If the dictionary is full, then see if it is time to reset it. 207 * 208 * Compute the compression ratio using fixed-point arithmetic 209 * with 8 fractional bits. 210 * 211 * Since we have an infinite stream instead of a single file, 212 * watch only the local compression ratio. 213 * 214 * Since both peers must reset the dictionary at the same time even in 215 * the absence of CLEAR codes (while packets are incompressible), they 216 * must compute the same ratio. 217 */ 218static int /* 1=output CLEAR */ 219bsd_check(struct bsd_db *db) 220{ 221 u_int new_ratio; 222 223 if (db->in_count >= db->checkpoint) { 224 /* age the ratio by limiting the size of the counts */ 225 if (db->in_count >= RATIO_MAX 226 || db->bytes_out >= RATIO_MAX) { 227 db->in_count -= db->in_count/4; 228 db->bytes_out -= db->bytes_out/4; 229 } 230 231 db->checkpoint = db->in_count + CHECK_GAP; 232 233 if (db->max_ent >= db->maxmaxcode) { 234 /* Reset the dictionary only if the ratio is worse, 235 * or if it looks as if it has been poisoned 236 * by incompressible data. 237 * 238 * This does not overflow, because 239 * db->in_count <= RATIO_MAX. 240 */ 241 new_ratio = db->in_count << RATIO_SCALE_LOG; 242 if (db->bytes_out != 0) 243 new_ratio /= db->bytes_out; 244 245 if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE) { 246 bsd_clear(db); 247 return 1; 248 } 249 db->ratio = new_ratio; 250 } 251 } 252 return 0; 253} 254 255/* 256 * Return statistics. 257 */ 258static void 259bsd_comp_stats(void *state, struct compstat *stats) 260{ 261 struct bsd_db *db = (struct bsd_db *) state; 262 u_int out; 263 264 stats->unc_bytes = db->uncomp_bytes; 265 stats->unc_packets = db->uncomp_count; 266 stats->comp_bytes = db->comp_bytes; 267 stats->comp_packets = db->comp_count; 268 stats->inc_bytes = db->incomp_bytes; 269 stats->inc_packets = db->incomp_count; 270 stats->ratio = db->in_count; 271 out = db->bytes_out; 272 if (stats->ratio <= 0x7fffff) 273 stats->ratio <<= 8; 274 else 275 out >>= 8; 276 if (out != 0) 277 stats->ratio /= out; 278} 279 280/* 281 * Reset state, as on a CCP ResetReq. 282 */ 283static void 284bsd_reset(void *state) 285{ 286 struct bsd_db *db = (struct bsd_db *) state; 287 288 db->seqno = 0; 289 bsd_clear(db); 290 db->clear_count = 0; 291} 292 293/* 294 * Allocate space for a (de) compressor. 295 */ 296static void * 297bsd_alloc(u_char *options, int opt_len, int decomp) 298{ 299 int bits; 300 u_int newlen, hsize, hshift, maxmaxcode; 301 struct bsd_db *db; 302 303 if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3 304 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION) 305 return NULL; 306 307 bits = BSD_NBITS(options[2]); 308 switch (bits) { 309 case 9: /* needs 82152 for both directions */ 310 case 10: /* needs 84144 */ 311 case 11: /* needs 88240 */ 312 case 12: /* needs 96432 */ 313 hsize = 5003; 314 hshift = 4; 315 break; 316 case 13: /* needs 176784 */ 317 hsize = 9001; 318 hshift = 5; 319 break; 320 case 14: /* needs 353744 */ 321 hsize = 18013; 322 hshift = 6; 323 break; 324 case 15: /* needs 691440 */ 325 hsize = 35023; 326 hshift = 7; 327 break; 328 case 16: /* needs 1366160--far too much, */ 329 /* hsize = 69001; */ /* and 69001 is too big for cptr */ 330 /* hshift = 8; */ /* in struct bsd_db */ 331 /* break; */ 332 default: 333 return NULL; 334 } 335 336 maxmaxcode = MAXCODE(bits); 337 newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0])); 338 db = (struct bsd_db *) malloc(newlen); 339 if (!db) 340 return NULL; 341 memset(db, 0, sizeof(*db) - sizeof(db->dict)); 342 343 if (!decomp) { 344 db->lens = NULL; 345 } else { 346 db->lens = (u_short *) malloc((maxmaxcode+1) * sizeof(db->lens[0])); 347 if (!db->lens) { 348 free(db); 349 return NULL; 350 } 351 } 352 353 db->totlen = newlen; 354 db->hsize = hsize; 355 db->hshift = hshift; 356 db->maxmaxcode = maxmaxcode; 357 db->maxbits = bits; 358 359 return (void *) db; 360} 361 362static void 363bsd_free(void *state) 364{ 365 struct bsd_db *db = (struct bsd_db *) state; 366 367 if (db->lens) 368 free(db->lens); 369 free(db); 370} 371 372static void * 373bsd_decomp_alloc(u_char *options, int opt_len) 374{ 375 return bsd_alloc(options, opt_len, 1); 376} 377 378/* 379 * Initialize the database. 380 */ 381static int 382bsd_init(struct bsd_db *db, u_char *options, int opt_len, int unit, 383 int hdrlen, int mru, int debug, int decomp) 384{ 385 int i; 386 387 if (opt_len < CILEN_BSD_COMPRESS 388 || options[0] != CI_BSD_COMPRESS || options[1] != CILEN_BSD_COMPRESS 389 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION 390 || BSD_NBITS(options[2]) != db->maxbits 391 || (decomp && db->lens == NULL)) 392 return 0; 393 394 if (decomp) { 395 i = LAST+1; 396 while (i != 0) 397 db->lens[--i] = 1; 398 } 399 i = db->hsize; 400 while (i != 0) { 401 db->dict[--i].codem1 = BADCODEM1; 402 db->dict[i].cptr = 0; 403 } 404 405 db->unit = unit; 406 db->hdrlen = hdrlen; 407 db->mru = mru; 408 if (debug) 409 db->debug = 1; 410 411 bsd_reset(db); 412 413 return 1; 414} 415 416static int 417bsd_decomp_init(void *state, u_char *options, int opt_len, 418 int unit, int hdrlen, int mru, int debug) 419{ 420 return bsd_init((struct bsd_db *) state, options, opt_len, 421 unit, hdrlen, mru, debug, 1); 422} 423 424 425/* 426 * Update the "BSD Compress" dictionary on the receiver for 427 * incompressible data by pretending to compress the incoming data. 428 */ 429static void 430bsd_incomp(void *state, PACKETPTR in) 431{ 432 struct bsd_db *db = (struct bsd_db *) state; 433 u_int hshift = db->hshift; 434 u_int max_ent = db->max_ent; 435 u_int n_bits = db->n_bits; 436 struct bsd_dict *dictp; 437 u_int32_t fcode; 438 u_char c; 439 long hval, disp; 440 int slen, ilen; 441 u_int bitno = 7; 442 u_char *rptr; 443 u_int ent; 444 445 rptr = in->buf; 446 ent = rptr[0]; /* get the protocol */ 447 if (ent == 0) { 448 ++rptr; 449 in->len--; 450 ent = rptr[0]; 451 } 452 if ((ent & 1) == 0 || ent < 0x21 || ent > 0xf9) 453 return; 454 455 db->seqno++; 456 ilen = 1; /* count the protocol as 1 byte */ 457 ++rptr; 458 slen = in->buf + in->len - rptr; 459 ilen += slen; 460 for (; slen > 0; --slen) { 461 c = *rptr++; 462 fcode = BSD_KEY(ent, c); 463 hval = BSD_HASH(ent, c, hshift); 464 dictp = &db->dict[hval]; 465 466 /* validate and then check the entry */ 467 if (dictp->codem1 >= max_ent) 468 goto nomatch; 469 if (dictp->f.fcode == fcode) { 470 ent = dictp->codem1+1; 471 continue; /* found (prefix,suffix) */ 472 } 473 474 /* continue probing until a match or invalid entry */ 475 disp = (hval == 0) ? 1 : hval; 476 do { 477 hval += disp; 478 if (hval >= db->hsize) 479 hval -= db->hsize; 480 dictp = &db->dict[hval]; 481 if (dictp->codem1 >= max_ent) 482 goto nomatch; 483 } while (dictp->f.fcode != fcode); 484 ent = dictp->codem1+1; 485 continue; /* finally found (prefix,suffix) */ 486 487 nomatch: /* output (count) the prefix */ 488 bitno += n_bits; 489 490 /* code -> hashtable */ 491 if (max_ent < db->maxmaxcode) { 492 struct bsd_dict *dictp2; 493 /* expand code size if needed */ 494 if (max_ent >= MAXCODE(n_bits)) 495 db->n_bits = ++n_bits; 496 497 /* Invalidate previous hash table entry 498 * assigned this code, and then take it over. 499 */ 500 dictp2 = &db->dict[max_ent+1]; 501 if (db->dict[dictp2->cptr].codem1 == max_ent) 502 db->dict[dictp2->cptr].codem1 = BADCODEM1; 503 dictp2->cptr = hval; 504 dictp->codem1 = max_ent; 505 dictp->f.fcode = fcode; 506 507 db->max_ent = ++max_ent; 508 db->lens[max_ent] = db->lens[ent]+1; 509 } 510 ent = c; 511 } 512 bitno += n_bits; /* output (count) the last code */ 513 db->bytes_out += bitno/8; 514 db->in_count += ilen; 515 (void)bsd_check(db); 516 517 ++db->incomp_count; 518 db->incomp_bytes += ilen; 519 ++db->uncomp_count; 520 db->uncomp_bytes += ilen; 521 522 /* Increase code size if we would have without the packet 523 * boundary and as the decompressor will. 524 */ 525 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) 526 db->n_bits++; 527} 528 529 530/* 531 * Decompress "BSD Compress" 532 * 533 * Because of patent problems, we return DECOMP_ERROR for errors 534 * found by inspecting the input data and for system problems, but 535 * DECOMP_FATALERROR for any errors which could possibly be said to 536 * be being detected "after" decompression. For DECOMP_ERROR, 537 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be 538 * infringing a patent of Motorola's if we do, so we take CCP down 539 * instead. 540 * 541 * Given that the frame has the correct sequence number and a good FCS, 542 * errors such as invalid codes in the input most likely indicate a 543 * bug, so we return DECOMP_FATALERROR for them in order to turn off 544 * compression, even though they are detected by inspecting the input. 545 */ 546static int 547bsd_decompress(void *state, PACKETPTR in, PACKETPTR *out) 548{ 549 struct bsd_db *db = (struct bsd_db *) state; 550 u_int max_ent = db->max_ent; 551 u_int32_t accm = 0; 552 u_int bitno = 32; /* 1st valid bit in accm */ 553 u_int n_bits = db->n_bits; 554 u_int tgtbitno = 32-n_bits; /* bitno when we have a code */ 555 struct bsd_dict *dictp; 556 int explen, seq, len; 557 u_int incode, oldcode, finchar; 558 u_char *p, *rptr, *wptr; 559 int ilen; 560 int codelen, extra; 561 562 rptr = in->buf; 563 if (*rptr == 0) 564 ++rptr; 565 ++rptr; /* skip protocol (assumed 0xfd) */ 566 seq = (rptr[0] << 8) + rptr[1]; 567 rptr += BSD_OVHD; 568 ilen = len = in->buf + in->len - rptr; 569 570 /* 571 * Check the sequence number and give up if it is not what we expect. 572 */ 573 if (seq != db->seqno++) { 574 if (db->debug) 575 printf("bsd_decomp%d: bad sequence # %d, expected %d\n", 576 db->unit, seq, db->seqno - 1); 577 return DECOMP_ERROR; 578 } 579 580 wptr = (*out)->buf + db->hdrlen; 581 582 oldcode = CLEAR; 583 explen = 0; 584 while (len > 0) { 585 /* 586 * Accumulate bytes until we have a complete code. 587 * Then get the next code, relying on the 32-bit, 588 * unsigned accm to mask the result. 589 */ 590 bitno -= 8; 591 accm |= *rptr++ << bitno; 592 --len; 593 if (tgtbitno < bitno) 594 continue; 595 incode = accm >> tgtbitno; 596 accm <<= n_bits; 597 bitno += n_bits; 598 599 if (incode == CLEAR) { 600 /* 601 * The dictionary must only be cleared at 602 * the end of a packet. But there could be an 603 * empty message block at the end. 604 */ 605 if (len > 0) { 606 if (db->debug) 607 printf("bsd_decomp%d: bad CLEAR\n", db->unit); 608 return DECOMP_FATALERROR; 609 } 610 bsd_clear(db); 611 explen = ilen = 0; 612 break; 613 } 614 615 if (incode > max_ent + 2 || incode > db->maxmaxcode 616 || (incode > max_ent && oldcode == CLEAR)) { 617 if (db->debug) { 618 printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ", 619 db->unit, incode, oldcode); 620 printf("max_ent=0x%x seqno=%d\n", 621 max_ent, db->seqno); 622 } 623 return DECOMP_FATALERROR; /* probably a bug */ 624 } 625 626 /* Special case for KwKwK string. */ 627 if (incode > max_ent) { 628 finchar = oldcode; 629 extra = 1; 630 } else { 631 finchar = incode; 632 extra = 0; 633 } 634 635 codelen = db->lens[finchar]; 636 explen += codelen + extra; 637 if (explen > db->mru + 1) { 638 if (db->debug) 639 printf("bsd_decomp%d: ran out of mru\n", db->unit); 640 return DECOMP_FATALERROR; 641 } 642 643 /* 644 * Decode this code and install it in the decompressed buffer. 645 */ 646 p = (wptr += codelen); 647 while (finchar > LAST) { 648 dictp = &db->dict[db->dict[finchar].cptr]; 649#ifdef DEBUG 650 --codelen; 651 if (codelen <= 0) { 652 printf("bsd_decomp%d: fell off end of chain ", db->unit); 653 printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n", 654 incode, finchar, db->dict[finchar].cptr, max_ent); 655 return DECOMP_FATALERROR; 656 } 657 if (dictp->codem1 != finchar-1) { 658 printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ", 659 db->unit, incode, finchar); 660 printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode, 661 db->dict[finchar].cptr, dictp->codem1); 662 return DECOMP_FATALERROR; 663 } 664#endif 665 *--p = dictp->f.hs.suffix; 666 finchar = dictp->f.hs.prefix; 667 } 668 *--p = finchar; 669 670#ifdef DEBUG 671 if (--codelen != 0) 672 printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n", 673 db->unit, codelen, incode, max_ent); 674#endif 675 676 if (extra) /* the KwKwK case again */ 677 *wptr++ = finchar; 678 679 /* 680 * If not first code in a packet, and 681 * if not out of code space, then allocate a new code. 682 * 683 * Keep the hash table correct so it can be used 684 * with uncompressed packets. 685 */ 686 if (oldcode != CLEAR && max_ent < db->maxmaxcode) { 687 struct bsd_dict *dictp2; 688 u_int32_t fcode; 689 int hval, disp; 690 691 fcode = BSD_KEY(oldcode,finchar); 692 hval = BSD_HASH(oldcode,finchar,db->hshift); 693 dictp = &db->dict[hval]; 694 695 /* look for a free hash table entry */ 696 if (dictp->codem1 < max_ent) { 697 disp = (hval == 0) ? 1 : hval; 698 do { 699 hval += disp; 700 if (hval >= db->hsize) 701 hval -= db->hsize; 702 dictp = &db->dict[hval]; 703 } while (dictp->codem1 < max_ent); 704 } 705 706 /* 707 * Invalidate previous hash table entry 708 * assigned this code, and then take it over 709 */ 710 dictp2 = &db->dict[max_ent+1]; 711 if (db->dict[dictp2->cptr].codem1 == max_ent) { 712 db->dict[dictp2->cptr].codem1 = BADCODEM1; 713 } 714 dictp2->cptr = hval; 715 dictp->codem1 = max_ent; 716 dictp->f.fcode = fcode; 717 718 db->max_ent = ++max_ent; 719 db->lens[max_ent] = db->lens[oldcode]+1; 720 721 /* Expand code size if needed. */ 722 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) { 723 db->n_bits = ++n_bits; 724 tgtbitno = 32-n_bits; 725 } 726 } 727 oldcode = incode; 728 } 729 (*out)->len = wptr - ((*out)->buf + db->hdrlen); 730 731 /* 732 * Keep the checkpoint right so that incompressible packets 733 * clear the dictionary at the right times. 734 */ 735 db->bytes_out += ilen; 736 db->in_count += explen; 737 if (bsd_check(db) && db->debug) { 738 printf("bsd_decomp%d: peer should have cleared dictionary\n", 739 db->unit); 740 } 741 742 ++db->comp_count; 743 db->comp_bytes += ilen + BSD_OVHD; 744 ++db->uncomp_count; 745 db->uncomp_bytes += explen; 746 747 return DECOMP_OK; 748} 749#endif /* DO_BSD_COMPRESS */ 750