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