1172 lines · c
1/*2 * Update: The Berkeley copyright was changed, and the change3 * is retroactive to all "true" BSD software (ie everything4 * from UCB as opposed to other peoples code that just carried5 * the same license). The new copyright doesn't clash with the6 * GPL, so the module-only restriction has been removed..7 */8 9/* Because this code is derived from the 4.3BSD compress source:10 *11 * Copyright (c) 1985, 1986 The Regents of the University of California.12 * All rights reserved.13 *14 * This code is derived from software contributed to Berkeley by15 * James A. Woods, derived from original work by Spencer Thomas16 * and Joseph Orost.17 *18 * Redistribution and use in source and binary forms, with or without19 * modification, are permitted provided that the following conditions20 * are met:21 * 1. Redistributions of source code must retain the above copyright22 * notice, this list of conditions and the following disclaimer.23 * 2. Redistributions in binary form must reproduce the above copyright24 * notice, this list of conditions and the following disclaimer in the25 * documentation and/or other materials provided with the distribution.26 * 3. All advertising materials mentioning features or use of this software27 * must display the following acknowledgement:28 * This product includes software developed by the University of29 * California, Berkeley and its contributors.30 * 4. Neither the name of the University nor the names of its contributors31 * may be used to endorse or promote products derived from this software32 * without specific prior written permission.33 *34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF44 * SUCH DAMAGE.45 */46 47/*48 * This version is for use with contiguous buffers on Linux-derived systems.49 *50 * ==FILEVERSION 20000226==51 *52 * NOTE TO MAINTAINERS:53 * If you modify this file at all, please set the number above to the54 * date of the modification as YYMMDD (year month day).55 * bsd_comp.c is shipped with a PPP distribution as well as with56 * the kernel; if everyone increases the FILEVERSION number above,57 * then scripts can do the right thing when deciding whether to58 * install a new bsd_comp.c file. Don't change the format of that59 * line otherwise, so the installation script can recognize it.60 *61 * From: bsd_comp.c,v 1.3 1994/12/08 01:59:58 paulus Exp62 */63 64#include <linux/module.h>65#include <linux/init.h>66#include <linux/slab.h>67#include <linux/vmalloc.h>68#include <linux/string.h>69 70#include <linux/ppp_defs.h>71 72#undef PACKETPTR73#define PACKETPTR 174#include <linux/ppp-comp.h>75#undef PACKETPTR76 77#include <asm/byteorder.h>78 79/*80 * PPP "BSD compress" compression81 * The differences between this compression and the classic BSD LZW82 * source are obvious from the requirement that the classic code worked83 * with files while this handles arbitrarily long streams that84 * are broken into packets. They are:85 *86 * When the code size expands, a block of junk is not emitted by87 * the compressor and not expected by the decompressor.88 *89 * New codes are not necessarily assigned every time an old90 * code is output by the compressor. This is because a packet91 * end forces a code to be emitted, but does not imply that a92 * new sequence has been seen.93 *94 * The compression ratio is checked at the first end of a packet95 * after the appropriate gap. Besides simplifying and speeding96 * things up, this makes it more likely that the transmitter97 * and receiver will agree when the dictionary is cleared when98 * compression is not going well.99 */100 101/*102 * Macros to extract protocol version and number of bits103 * from the third byte of the BSD Compress CCP configuration option.104 */105 106#define BSD_VERSION(x) ((x) >> 5)107#define BSD_NBITS(x) ((x) & 0x1F)108 109#define BSD_CURRENT_VERSION 1110 111/*112 * A dictionary for doing BSD compress.113 */114 115struct bsd_dict {116 union { /* hash value */117 unsigned long fcode;118 struct {119#if defined(__LITTLE_ENDIAN) /* Little endian order */120 unsigned short prefix; /* preceding code */121 unsigned char suffix; /* last character of new code */122 unsigned char pad;123#elif defined(__BIG_ENDIAN) /* Big endian order */124 unsigned char pad;125 unsigned char suffix; /* last character of new code */126 unsigned short prefix; /* preceding code */127#else128#error Endianness not defined...129#endif130 } hs;131 } f;132 unsigned short codem1; /* output of hash table -1 */133 unsigned short cptr; /* map code to hash table entry */134};135 136struct bsd_db {137 int totlen; /* length of this structure */138 unsigned int hsize; /* size of the hash table */139 unsigned char hshift; /* used in hash function */140 unsigned char n_bits; /* current bits/code */141 unsigned char maxbits; /* maximum bits/code */142 unsigned char debug; /* non-zero if debug desired */143 unsigned char unit; /* ppp unit number */144 unsigned short seqno; /* sequence # of next packet */145 unsigned int mru; /* size of receive (decompress) bufr */146 unsigned int maxmaxcode; /* largest valid code */147 unsigned int max_ent; /* largest code in use */148 unsigned int in_count; /* uncompressed bytes, aged */149 unsigned int bytes_out; /* compressed bytes, aged */150 unsigned int ratio; /* recent compression ratio */151 unsigned int checkpoint; /* when to next check the ratio */152 unsigned int clear_count; /* times dictionary cleared */153 unsigned int incomp_count; /* incompressible packets */154 unsigned int incomp_bytes; /* incompressible bytes */155 unsigned int uncomp_count; /* uncompressed packets */156 unsigned int uncomp_bytes; /* uncompressed bytes */157 unsigned int comp_count; /* compressed packets */158 unsigned int comp_bytes; /* compressed bytes */159 unsigned short *lens; /* array of lengths of codes */160 struct bsd_dict *dict; /* dictionary */161};162 163#define BSD_OVHD 2 /* BSD compress overhead/packet */164#define MIN_BSD_BITS 9165#define BSD_INIT_BITS MIN_BSD_BITS166#define MAX_BSD_BITS 15167 168static void bsd_free (void *state);169static void *bsd_alloc(unsigned char *options, int opt_len, int decomp);170static void *bsd_comp_alloc (unsigned char *options, int opt_len);171static void *bsd_decomp_alloc (unsigned char *options, int opt_len);172 173static int bsd_init (void *db, unsigned char *options,174 int opt_len, int unit, int debug, int decomp);175static int bsd_comp_init (void *state, unsigned char *options,176 int opt_len, int unit, int opthdr, int debug);177static int bsd_decomp_init (void *state, unsigned char *options,178 int opt_len, int unit, int opthdr, int mru,179 int debug);180 181static void bsd_reset (void *state);182static void bsd_comp_stats (void *state, struct compstat *stats);183 184static int bsd_compress (void *state, unsigned char *rptr,185 unsigned char *obuf, int isize, int osize);186static void bsd_incomp (void *state, unsigned char *ibuf, int icnt);187 188static int bsd_decompress (void *state, unsigned char *ibuf, int isize,189 unsigned char *obuf, int osize);190 191/* These are in ppp_generic.c */192extern int ppp_register_compressor (struct compressor *cp);193extern void ppp_unregister_compressor (struct compressor *cp);194 195/*196 * the next two codes should not be changed lightly, as they must not197 * lie within the contiguous general code space.198 */199#define CLEAR 256 /* table clear output code */200#define FIRST 257 /* first free entry */201#define LAST 255202 203#define MAXCODE(b) ((1 << (b)) - 1)204#define BADCODEM1 MAXCODE(MAX_BSD_BITS)205 206#define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) \207 ^ (unsigned long)(prefix))208#define BSD_KEY(prefix,suffix) ((((unsigned long)(suffix)) << 16) \209 + (unsigned long)(prefix))210 211#define CHECK_GAP 10000 /* Ratio check interval */212 213#define RATIO_SCALE_LOG 8214#define RATIO_SCALE (1<<RATIO_SCALE_LOG)215#define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)216 217/*218 * clear the dictionary219 */220 221static void222bsd_clear(struct bsd_db *db)223{224 db->clear_count++;225 db->max_ent = FIRST-1;226 db->n_bits = BSD_INIT_BITS;227 db->bytes_out = 0;228 db->in_count = 0;229 db->ratio = 0;230 db->checkpoint = CHECK_GAP;231}232 233/*234 * If the dictionary is full, then see if it is time to reset it.235 *236 * Compute the compression ratio using fixed-point arithmetic237 * with 8 fractional bits.238 *239 * Since we have an infinite stream instead of a single file,240 * watch only the local compression ratio.241 *242 * Since both peers must reset the dictionary at the same time even in243 * the absence of CLEAR codes (while packets are incompressible), they244 * must compute the same ratio.245 */246 247static int bsd_check (struct bsd_db *db) /* 1=output CLEAR */248 {249 unsigned int new_ratio;250 251 if (db->in_count >= db->checkpoint)252 {253 /* age the ratio by limiting the size of the counts */254 if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)255 {256 db->in_count -= (db->in_count >> 2);257 db->bytes_out -= (db->bytes_out >> 2);258 }259 260 db->checkpoint = db->in_count + CHECK_GAP;261 262 if (db->max_ent >= db->maxmaxcode)263 {264 /* Reset the dictionary only if the ratio is worse,265 * or if it looks as if it has been poisoned266 * by incompressible data.267 *268 * This does not overflow, because269 * db->in_count <= RATIO_MAX.270 */271 272 new_ratio = db->in_count << RATIO_SCALE_LOG;273 if (db->bytes_out != 0)274 {275 new_ratio /= db->bytes_out;276 }277 278 if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)279 {280 bsd_clear (db);281 return 1;282 }283 db->ratio = new_ratio;284 }285 }286 return 0;287 }288 289/*290 * Return statistics.291 */292 293static void bsd_comp_stats (void *state, struct compstat *stats)294 {295 struct bsd_db *db = (struct bsd_db *) state;296 297 stats->unc_bytes = db->uncomp_bytes;298 stats->unc_packets = db->uncomp_count;299 stats->comp_bytes = db->comp_bytes;300 stats->comp_packets = db->comp_count;301 stats->inc_bytes = db->incomp_bytes;302 stats->inc_packets = db->incomp_count;303 stats->in_count = db->in_count;304 stats->bytes_out = db->bytes_out;305 }306 307/*308 * Reset state, as on a CCP ResetReq.309 */310 311static void bsd_reset (void *state)312 {313 struct bsd_db *db = (struct bsd_db *) state;314 315 bsd_clear(db);316 317 db->seqno = 0;318 db->clear_count = 0;319 }320 321/*322 * Release the compression structure323 */324 325static void bsd_free (void *state)326{327 struct bsd_db *db = state;328 329 if (!db)330 return;331 332/*333 * Release the dictionary334 */335 vfree(db->dict);336 db->dict = NULL;337/*338 * Release the string buffer339 */340 vfree(db->lens);341 db->lens = NULL;342/*343 * Finally release the structure itself.344 */345 kfree(db);346}347 348/*349 * Allocate space for a (de) compressor.350 */351 352static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)353 {354 int bits;355 unsigned int hsize, hshift, maxmaxcode;356 struct bsd_db *db;357 358 if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3359 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)360 {361 return NULL;362 }363 364 bits = BSD_NBITS(options[2]);365 366 switch (bits)367 {368 case 9: /* needs 82152 for both directions */369 case 10: /* needs 84144 */370 case 11: /* needs 88240 */371 case 12: /* needs 96432 */372 hsize = 5003;373 hshift = 4;374 break;375 case 13: /* needs 176784 */376 hsize = 9001;377 hshift = 5;378 break;379 case 14: /* needs 353744 */380 hsize = 18013;381 hshift = 6;382 break;383 case 15: /* needs 691440 */384 hsize = 35023;385 hshift = 7;386 break;387 case 16: /* needs 1366160--far too much, */388 /* hsize = 69001; */ /* and 69001 is too big for cptr */389 /* hshift = 8; */ /* in struct bsd_db */390 /* break; */391 default:392 return NULL;393 }394/*395 * Allocate the main control structure for this instance.396 */397 maxmaxcode = MAXCODE(bits);398 db = kzalloc(sizeof (struct bsd_db),399 GFP_KERNEL);400 if (!db)401 {402 return NULL;403 }404 405/*406 * Allocate space for the dictionary. This may be more than one page in407 * length.408 */409 db->dict = vmalloc(array_size(hsize, sizeof(struct bsd_dict)));410 if (!db->dict)411 {412 bsd_free (db);413 return NULL;414 }415 416/*417 * If this is the compression buffer then there is no length data.418 */419 if (!decomp)420 {421 db->lens = NULL;422 }423/*424 * For decompression, the length information is needed as well.425 */426 else427 {428 db->lens = vmalloc(array_size(sizeof(db->lens[0]), (maxmaxcode + 1)));429 if (!db->lens)430 {431 bsd_free (db);432 return NULL;433 }434 }435/*436 * Initialize the data information for the compression code437 */438 db->totlen = sizeof (struct bsd_db) +439 (sizeof (struct bsd_dict) * hsize);440 441 db->hsize = hsize;442 db->hshift = hshift;443 db->maxmaxcode = maxmaxcode;444 db->maxbits = bits;445 446 return (void *) db;447 }448 449static void *bsd_comp_alloc (unsigned char *options, int opt_len)450 {451 return bsd_alloc (options, opt_len, 0);452 }453 454static void *bsd_decomp_alloc (unsigned char *options, int opt_len)455 {456 return bsd_alloc (options, opt_len, 1);457 }458 459/*460 * Initialize the database.461 */462 463static int bsd_init (void *state, unsigned char *options,464 int opt_len, int unit, int debug, int decomp)465 {466 struct bsd_db *db = state;467 int indx;468 469 if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)470 || (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)471 || (BSD_NBITS(options[2]) != db->maxbits)472 || (decomp && db->lens == NULL))473 {474 return 0;475 }476 477 if (decomp)478 {479 indx = LAST;480 do481 {482 db->lens[indx] = 1;483 }484 while (indx-- > 0);485 }486 487 indx = db->hsize;488 while (indx-- != 0)489 {490 db->dict[indx].codem1 = BADCODEM1;491 db->dict[indx].cptr = 0;492 }493 494 db->unit = unit;495 db->mru = 0;496#ifndef DEBUG497 if (debug)498#endif499 db->debug = 1;500 501 bsd_reset(db);502 503 return 1;504 }505 506static int bsd_comp_init (void *state, unsigned char *options,507 int opt_len, int unit, int opthdr, int debug)508 {509 return bsd_init (state, options, opt_len, unit, debug, 0);510 }511 512static int bsd_decomp_init (void *state, unsigned char *options,513 int opt_len, int unit, int opthdr, int mru,514 int debug)515 {516 return bsd_init (state, options, opt_len, unit, debug, 1);517 }518 519/*520 * Obtain pointers to the various structures in the compression tables521 */522 523#define dict_ptrx(p,idx) &(p->dict[idx])524#define lens_ptrx(p,idx) &(p->lens[idx])525 526#ifdef DEBUG527static unsigned short *lens_ptr(struct bsd_db *db, int idx)528 {529 if ((unsigned int) idx > (unsigned int) db->maxmaxcode)530 {531 printk ("<9>ppp: lens_ptr(%d) > max\n", idx);532 idx = 0;533 }534 return lens_ptrx (db, idx);535 }536 537static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)538 {539 if ((unsigned int) idx >= (unsigned int) db->hsize)540 {541 printk ("<9>ppp: dict_ptr(%d) > max\n", idx);542 idx = 0;543 }544 return dict_ptrx (db, idx);545 }546 547#else548#define lens_ptr(db,idx) lens_ptrx(db,idx)549#define dict_ptr(db,idx) dict_ptrx(db,idx)550#endif551 552/*553 * compress a packet554 *555 * The result of this function is the size of the compressed556 * packet. A zero is returned if the packet was not compressed557 * for some reason, such as the size being larger than uncompressed.558 *559 * One change from the BSD compress command is that when the560 * code size expands, we do not output a bunch of padding.561 */562 563static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,564 int isize, int osize)565 {566 struct bsd_db *db;567 int hshift;568 unsigned int max_ent;569 unsigned int n_bits;570 unsigned int bitno;571 unsigned long accm;572 int ent;573 unsigned long fcode;574 struct bsd_dict *dictp;575 unsigned char c;576 int hval;577 int disp;578 int ilen;579 int mxcode;580 unsigned char *wptr;581 int olen;582 583#define PUTBYTE(v) \584 { \585 ++olen; \586 if (wptr) \587 { \588 *wptr++ = (unsigned char) (v); \589 if (olen >= osize) \590 { \591 wptr = NULL; \592 } \593 } \594 }595 596#define OUTPUT(ent) \597 { \598 bitno -= n_bits; \599 accm |= ((ent) << bitno); \600 do \601 { \602 PUTBYTE(accm >> 24); \603 accm <<= 8; \604 bitno += 8; \605 } \606 while (bitno <= 24); \607 }608 609 /*610 * If the protocol is not in the range we're interested in,611 * just return without compressing the packet. If it is,612 * the protocol becomes the first byte to compress.613 */614 615 ent = PPP_PROTOCOL(rptr);616 if (ent < 0x21 || ent > 0xf9)617 {618 return 0;619 }620 621 db = (struct bsd_db *) state;622 hshift = db->hshift;623 max_ent = db->max_ent;624 n_bits = db->n_bits;625 bitno = 32;626 accm = 0;627 mxcode = MAXCODE (n_bits);628 629 /* Initialize the output pointers */630 wptr = obuf;631 olen = PPP_HDRLEN + BSD_OVHD;632 633 if (osize > isize)634 {635 osize = isize;636 }637 638 /* This is the PPP header information */639 if (wptr)640 {641 *wptr++ = PPP_ADDRESS(rptr);642 *wptr++ = PPP_CONTROL(rptr);643 *wptr++ = 0;644 *wptr++ = PPP_COMP;645 *wptr++ = db->seqno >> 8;646 *wptr++ = db->seqno;647 }648 649 /* Skip the input header */650 rptr += PPP_HDRLEN;651 isize -= PPP_HDRLEN;652 ilen = ++isize; /* Low byte of protocol is counted as input */653 654 while (--ilen > 0)655 {656 c = *rptr++;657 fcode = BSD_KEY (ent, c);658 hval = BSD_HASH (ent, c, hshift);659 dictp = dict_ptr (db, hval);660 661 /* Validate and then check the entry. */662 if (dictp->codem1 >= max_ent)663 {664 goto nomatch;665 }666 667 if (dictp->f.fcode == fcode)668 {669 ent = dictp->codem1 + 1;670 continue; /* found (prefix,suffix) */671 }672 673 /* continue probing until a match or invalid entry */674 disp = (hval == 0) ? 1 : hval;675 676 do677 {678 hval += disp;679 if (hval >= db->hsize)680 {681 hval -= db->hsize;682 }683 dictp = dict_ptr (db, hval);684 if (dictp->codem1 >= max_ent)685 {686 goto nomatch;687 }688 }689 while (dictp->f.fcode != fcode);690 691 ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */692 continue;693 694nomatch:695 OUTPUT(ent); /* output the prefix */696 697 /* code -> hashtable */698 if (max_ent < db->maxmaxcode)699 {700 struct bsd_dict *dictp2;701 struct bsd_dict *dictp3;702 int indx;703 704 /* expand code size if needed */705 if (max_ent >= mxcode)706 {707 db->n_bits = ++n_bits;708 mxcode = MAXCODE (n_bits);709 }710 711 /* Invalidate old hash table entry using712 * this code, and then take it over.713 */714 715 dictp2 = dict_ptr (db, max_ent + 1);716 indx = dictp2->cptr;717 dictp3 = dict_ptr (db, indx);718 719 if (dictp3->codem1 == max_ent)720 {721 dictp3->codem1 = BADCODEM1;722 }723 724 dictp2->cptr = hval;725 dictp->codem1 = max_ent;726 dictp->f.fcode = fcode;727 db->max_ent = ++max_ent;728 729 if (db->lens)730 {731 unsigned short *len1 = lens_ptr (db, max_ent);732 unsigned short *len2 = lens_ptr (db, ent);733 *len1 = *len2 + 1;734 }735 }736 ent = c;737 }738 739 OUTPUT(ent); /* output the last code */740 741 db->bytes_out += olen - PPP_HDRLEN - BSD_OVHD;742 db->uncomp_bytes += isize;743 db->in_count += isize;744 ++db->uncomp_count;745 ++db->seqno;746 747 if (bitno < 32)748 {749 ++db->bytes_out; /* must be set before calling bsd_check */750 }751 752 /*753 * Generate the clear command if needed754 */755 756 if (bsd_check(db))757 {758 OUTPUT (CLEAR);759 }760 761 /*762 * Pad dribble bits of last code with ones.763 * Do not emit a completely useless byte of ones.764 */765 766 if (bitno != 32)767 {768 PUTBYTE((accm | (0xff << (bitno-8))) >> 24);769 }770 771 /*772 * Increase code size if we would have without the packet773 * boundary because the decompressor will do so.774 */775 776 if (max_ent >= mxcode && max_ent < db->maxmaxcode)777 {778 db->n_bits++;779 }780 781 /* If output length is too large then this is an incomplete frame. */782 if (wptr == NULL)783 {784 ++db->incomp_count;785 db->incomp_bytes += isize;786 olen = 0;787 }788 else /* Count the number of compressed frames */789 {790 ++db->comp_count;791 db->comp_bytes += olen;792 }793 794 /* Return the resulting output length */795 return olen;796#undef OUTPUT797#undef PUTBYTE798 }799 800/*801 * Update the "BSD Compress" dictionary on the receiver for802 * incompressible data by pretending to compress the incoming data.803 */804 805static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)806 {807 (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);808 }809 810/*811 * Decompress "BSD Compress".812 *813 * Because of patent problems, we return DECOMP_ERROR for errors814 * found by inspecting the input data and for system problems, but815 * DECOMP_FATALERROR for any errors which could possibly be said to816 * be being detected "after" decompression. For DECOMP_ERROR,817 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be818 * infringing a patent of Motorola's if we do, so we take CCP down819 * instead.820 *821 * Given that the frame has the correct sequence number and a good FCS,822 * errors such as invalid codes in the input most likely indicate a823 * bug, so we return DECOMP_FATALERROR for them in order to turn off824 * compression, even though they are detected by inspecting the input.825 */826 827static int bsd_decompress (void *state, unsigned char *ibuf, int isize,828 unsigned char *obuf, int osize)829 {830 struct bsd_db *db;831 unsigned int max_ent;832 unsigned long accm;833 unsigned int bitno; /* 1st valid bit in accm */834 unsigned int n_bits;835 unsigned int tgtbitno; /* bitno when we have a code */836 struct bsd_dict *dictp;837 int explen;838 int seq;839 unsigned int incode;840 unsigned int oldcode;841 unsigned int finchar;842 unsigned char *p;843 unsigned char *wptr;844 int adrs;845 int ctrl;846 int ilen;847 int codelen;848 int extra;849 850 db = (struct bsd_db *) state;851 max_ent = db->max_ent;852 accm = 0;853 bitno = 32; /* 1st valid bit in accm */854 n_bits = db->n_bits;855 tgtbitno = 32 - n_bits; /* bitno when we have a code */856 857 /*858 * Save the address/control from the PPP header859 * and then get the sequence number.860 */861 862 adrs = PPP_ADDRESS (ibuf);863 ctrl = PPP_CONTROL (ibuf);864 865 seq = (ibuf[4] << 8) + ibuf[5];866 867 ibuf += (PPP_HDRLEN + 2);868 ilen = isize - (PPP_HDRLEN + 2);869 870 /*871 * Check the sequence number and give up if it differs from872 * the value we're expecting.873 */874 875 if (seq != db->seqno)876 {877 if (db->debug)878 {879 printk("bsd_decomp%d: bad sequence # %d, expected %d\n",880 db->unit, seq, db->seqno - 1);881 }882 return DECOMP_ERROR;883 }884 885 ++db->seqno;886 db->bytes_out += ilen;887 888 /*889 * Fill in the ppp header, but not the last byte of the protocol890 * (that comes from the decompressed data).891 */892 893 wptr = obuf;894 *wptr++ = adrs;895 *wptr++ = ctrl;896 *wptr++ = 0;897 898 oldcode = CLEAR;899 explen = 3;900 901 /*902 * Keep the checkpoint correctly so that incompressible packets903 * clear the dictionary at the proper times.904 */905 906 for (;;)907 {908 if (ilen-- <= 0)909 {910 db->in_count += (explen - 3); /* don't count the header */911 break;912 }913 914 /*915 * Accumulate bytes until we have a complete code.916 * Then get the next code, relying on the 32-bit,917 * unsigned accm to mask the result.918 */919 920 bitno -= 8;921 accm |= *ibuf++ << bitno;922 if (tgtbitno < bitno)923 {924 continue;925 }926 927 incode = accm >> tgtbitno;928 accm <<= n_bits;929 bitno += n_bits;930 931 /*932 * The dictionary must only be cleared at the end of a packet.933 */934 935 if (incode == CLEAR)936 {937 if (ilen > 0)938 {939 if (db->debug)940 {941 printk("bsd_decomp%d: bad CLEAR\n", db->unit);942 }943 return DECOMP_FATALERROR; /* probably a bug */944 }945 946 bsd_clear(db);947 break;948 }949 950 if ((incode > max_ent + 2) || (incode > db->maxmaxcode)951 || (incode > max_ent && oldcode == CLEAR))952 {953 if (db->debug)954 {955 printk("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",956 db->unit, incode, oldcode);957 printk("max_ent=0x%x explen=%d seqno=%d\n",958 max_ent, explen, db->seqno);959 }960 return DECOMP_FATALERROR; /* probably a bug */961 }962 963 /* Special case for KwKwK string. */964 if (incode > max_ent)965 {966 finchar = oldcode;967 extra = 1;968 }969 else970 {971 finchar = incode;972 extra = 0;973 }974 975 codelen = *(lens_ptr (db, finchar));976 explen += codelen + extra;977 if (explen > osize)978 {979 if (db->debug)980 {981 printk("bsd_decomp%d: ran out of mru\n", db->unit);982#ifdef DEBUG983 printk(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n",984 ilen, finchar, codelen, explen);985#endif986 }987 return DECOMP_FATALERROR;988 }989 990 /*991 * Decode this code and install it in the decompressed buffer.992 */993 994 wptr += codelen;995 p = wptr;996 while (finchar > LAST)997 {998 struct bsd_dict *dictp2 = dict_ptr (db, finchar);999 1000 dictp = dict_ptr (db, dictp2->cptr);1001#ifdef DEBUG1002 if (--codelen <= 0 || dictp->codem1 != finchar-1)1003 {1004 if (codelen <= 0)1005 {1006 printk("bsd_decomp%d: fell off end of chain ", db->unit);1007 printk("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",1008 incode, finchar, dictp2->cptr, max_ent);1009 }1010 else1011 {1012 if (dictp->codem1 != finchar-1)1013 {1014 printk("bsd_decomp%d: bad code chain 0x%x "1015 "finchar=0x%x ",1016 db->unit, incode, finchar);1017 1018 printk("oldcode=0x%x cptr=0x%x codem1=0x%x\n",1019 oldcode, dictp2->cptr, dictp->codem1);1020 }1021 }1022 return DECOMP_FATALERROR;1023 }1024#endif1025 *--p = dictp->f.hs.suffix;1026 finchar = dictp->f.hs.prefix;1027 }1028 *--p = finchar;1029 1030#ifdef DEBUG1031 if (--codelen != 0)1032 {1033 printk("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",1034 db->unit, codelen, incode, max_ent);1035 }1036#endif1037 1038 if (extra) /* the KwKwK case again */1039 {1040 *wptr++ = finchar;1041 }1042 1043 /*1044 * If not first code in a packet, and1045 * if not out of code space, then allocate a new code.1046 *1047 * Keep the hash table correct so it can be used1048 * with uncompressed packets.1049 */1050 1051 if (oldcode != CLEAR && max_ent < db->maxmaxcode)1052 {1053 struct bsd_dict *dictp2, *dictp3;1054 unsigned short *lens1, *lens2;1055 unsigned long fcode;1056 int hval, disp, indx;1057 1058 fcode = BSD_KEY(oldcode,finchar);1059 hval = BSD_HASH(oldcode,finchar,db->hshift);1060 dictp = dict_ptr (db, hval);1061 1062 /* look for a free hash table entry */1063 if (dictp->codem1 < max_ent)1064 {1065 disp = (hval == 0) ? 1 : hval;1066 do1067 {1068 hval += disp;1069 if (hval >= db->hsize)1070 {1071 hval -= db->hsize;1072 }1073 dictp = dict_ptr (db, hval);1074 }1075 while (dictp->codem1 < max_ent);1076 }1077 1078 /*1079 * Invalidate previous hash table entry1080 * assigned this code, and then take it over1081 */1082 1083 dictp2 = dict_ptr (db, max_ent + 1);1084 indx = dictp2->cptr;1085 dictp3 = dict_ptr (db, indx);1086 1087 if (dictp3->codem1 == max_ent)1088 {1089 dictp3->codem1 = BADCODEM1;1090 }1091 1092 dictp2->cptr = hval;1093 dictp->codem1 = max_ent;1094 dictp->f.fcode = fcode;1095 db->max_ent = ++max_ent;1096 1097 /* Update the length of this string. */1098 lens1 = lens_ptr (db, max_ent);1099 lens2 = lens_ptr (db, oldcode);1100 *lens1 = *lens2 + 1;1101 1102 /* Expand code size if needed. */1103 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)1104 {1105 db->n_bits = ++n_bits;1106 tgtbitno = 32-n_bits;1107 }1108 }1109 oldcode = incode;1110 }1111 1112 ++db->comp_count;1113 ++db->uncomp_count;1114 db->comp_bytes += isize - BSD_OVHD - PPP_HDRLEN;1115 db->uncomp_bytes += explen;1116 1117 if (bsd_check(db))1118 {1119 if (db->debug)1120 {1121 printk("bsd_decomp%d: peer should have cleared dictionary on %d\n",1122 db->unit, db->seqno - 1);1123 }1124 }1125 return explen;1126 }1127 1128/*************************************************************1129 * Table of addresses for the BSD compression module1130 *************************************************************/1131 1132static struct compressor ppp_bsd_compress = {1133 .compress_proto = CI_BSD_COMPRESS,1134 .comp_alloc = bsd_comp_alloc,1135 .comp_free = bsd_free,1136 .comp_init = bsd_comp_init,1137 .comp_reset = bsd_reset,1138 .compress = bsd_compress,1139 .comp_stat = bsd_comp_stats,1140 .decomp_alloc = bsd_decomp_alloc,1141 .decomp_free = bsd_free,1142 .decomp_init = bsd_decomp_init,1143 .decomp_reset = bsd_reset,1144 .decompress = bsd_decompress,1145 .incomp = bsd_incomp,1146 .decomp_stat = bsd_comp_stats,1147 .owner = THIS_MODULE1148};1149 1150/*************************************************************1151 * Module support routines1152 *************************************************************/1153 1154static int __init bsdcomp_init(void)1155{1156 int answer = ppp_register_compressor(&ppp_bsd_compress);1157 if (answer == 0)1158 printk(KERN_INFO "PPP BSD Compression module registered\n");1159 return answer;1160}1161 1162static void __exit bsdcomp_cleanup(void)1163{1164 ppp_unregister_compressor(&ppp_bsd_compress);1165}1166 1167module_init(bsdcomp_init);1168module_exit(bsdcomp_cleanup);1169MODULE_DESCRIPTION("PPP BSD-Compress compression module");1170MODULE_LICENSE("Dual BSD/GPL");1171MODULE_ALIAS("ppp-compress-" __stringify(CI_BSD_COMPRESS));1172