开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 嵌入式/单片机编程 > 嵌入式Linux > 查看源码
bsd_comp.c
资源名称：SBC-2410X_kernel.tar.gz　[点击查看]
上传用户：lgb322
上传日期：2013-02-24
资源大小：30529k
文件大小：29k
源码类别：

嵌入式Linux

开发平台：

Unix_Linux

bsd_comp.c：源码内容
  1. /*
  2.  * Update: The Berkeley copyright was changed, and the change 
  3.  * is retroactive to all "true" BSD software (ie everything
  4.  * from UCB as opposed to other peoples code that just carried
  5.  * the same license). The new copyright doesn't clash with the
  6.  * GPL, so the module-only restriction has been removed..
  7.  */
  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 by
  15.  * James A. Woods, derived from original work by Spencer Thomas
  16.  * and Joseph Orost.
  17.  *
  18.  * Redistribution and use in source and binary forms, with or without
  19.  * modification, are permitted provided that the following conditions
  20.  * are met:
  21.  * 1. Redistributions of source code must retain the above copyright
  22.  *    notice, this list of conditions and the following disclaimer.
  23.  * 2. Redistributions in binary form must reproduce the above copyright
  24.  *    notice, this list of conditions and the following disclaimer in the
  25.  *    documentation and/or other materials provided with the distribution.
  26.  * 3. All advertising materials mentioning features or use of this software
  27.  *    must display the following acknowledgement:
  28.  * This product includes software developed by the University of
  29.  * California, Berkeley and its contributors.
  30.  * 4. Neither the name of the University nor the names of its contributors
  31.  *    may be used to endorse or promote products derived from this software
  32.  *    without specific prior written permission.
  33.  *
  34.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  35.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  36.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  37.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  38.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  39.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  40.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  41.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  42.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  43.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  44.  * SUCH DAMAGE.
  45.  */
  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 the
  54.  *     date of the modification as YYMMDD (year month day).
  55.  *     bsd_comp.c is shipped with a PPP distribution as well as with
  56.  *     the kernel; if everyone increases the FILEVERSION number above,
  57.  *     then scripts can do the right thing when deciding whether to
  58.  *     install a new bsd_comp.c file. Don't change the format of that
  59.  *     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 Exp
  62.  */
  64. #include <linux/module.h>
  65. #include <linux/init.h>
  66. #include <linux/slab.h>
  67. #include <linux/vmalloc.h>
  69. #include <linux/ppp_defs.h>
  71. #undef   PACKETPTR
  72. #define  PACKETPTR 1
  73. #include <linux/ppp-comp.h>
  74. #undef   PACKETPTR
  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.  */
  98. /*
  99.  * Macros to extract protocol version and number of bits
  100.  * from the third byte of the BSD Compress CCP configuration option.
  101.  */
  103. #define BSD_VERSION(x) ((x) >> 5)
  104. #define BSD_NBITS(x) ((x) & 0x1F)
  106. #define BSD_CURRENT_VERSION 1
  108. /*
  109.  * A dictionary for doing BSD compress.
  110.  */
  112. struct bsd_dict {
  113.     union { /* hash value */
  114. unsigned long fcode;
  115. struct {
  116. #if defined(__LITTLE_ENDIAN) /* Little endian order */
  117.     unsigned short prefix; /* preceding code */
  118.     unsigned char suffix; /* last character of new code */
  119.     unsigned char pad;
  120. #elif defined(__BIG_ENDIAN) /* Big endian order */
  121.     unsigned char pad;
  122.     unsigned char suffix; /* last character of new code */
  123.     unsigned short prefix; /* preceding code */
  124. #else
  125. #error Endianness not defined...
  126. #endif
  127. } hs;
  128.     } f;
  129.     unsigned short codem1; /* output of hash table -1 */
  130.     unsigned short cptr; /* map code to hash table entry */
  131. };
  133. struct bsd_db {
  134.     int     totlen; /* length of this structure */
  135.     unsigned int   hsize; /* size of the hash table */
  136.     unsigned char  hshift; /* used in hash function */
  137.     unsigned char  n_bits; /* current bits/code */
  138.     unsigned char  maxbits; /* maximum bits/code */
  139.     unsigned char  debug; /* non-zero if debug desired */
  140.     unsigned char  unit; /* ppp unit number */
  141.     unsigned short seqno; /* sequence # of next packet */
  142.     unsigned int   mru; /* size of receive (decompress) bufr */
  143.     unsigned int   maxmaxcode; /* largest valid code */
  144.     unsigned int   max_ent; /* largest code in use */
  145.     unsigned int   in_count; /* uncompressed bytes, aged */
  146.     unsigned int   bytes_out; /* compressed bytes, aged */
  147.     unsigned int   ratio; /* recent compression ratio */
  148.     unsigned int   checkpoint; /* when to next check the ratio */
  149.     unsigned int   clear_count; /* times dictionary cleared */
  150.     unsigned int   incomp_count; /* incompressible packets */
  151.     unsigned int   incomp_bytes; /* incompressible bytes */
  152.     unsigned int   uncomp_count; /* uncompressed packets */
  153.     unsigned int   uncomp_bytes; /* uncompressed bytes */
  154.     unsigned int   comp_count; /* compressed packets */
  155.     unsigned int   comp_bytes; /* compressed bytes */
  156.     unsigned short  *lens; /* array of lengths of codes */
  157.     struct bsd_dict *dict; /* dictionary */
  158. };
  160. #define BSD_OVHD 2 /* BSD compress overhead/packet */
  161. #define MIN_BSD_BITS 9
  162. #define BSD_INIT_BITS MIN_BSD_BITS
  163. #define MAX_BSD_BITS 15
  165. static void bsd_free (void *state);
  166. static void *bsd_alloc(unsigned char *options, int opt_len, int decomp);
  167. static void *bsd_comp_alloc (unsigned char *options, int opt_len);
  168. static void *bsd_decomp_alloc (unsigned char *options, int opt_len);
  170. static int bsd_init        (void *db, unsigned char *options,
  171.          int opt_len, int unit, int debug, int decomp);
  172. static int bsd_comp_init   (void *state, unsigned char *options,
  173.          int opt_len, int unit, int opthdr, int debug);
  174. static int bsd_decomp_init (void *state, unsigned char *options,
  175.  int opt_len, int unit, int opthdr, int mru,
  176.  int debug);
  178. static void bsd_reset (void *state);
  179. static void bsd_comp_stats (void *state, struct compstat *stats);
  181. static int bsd_compress (void *state, unsigned char *rptr,
  182.       unsigned char *obuf, int isize, int osize);
  183. static void bsd_incomp (void *state, unsigned char *ibuf, int icnt);
  185. static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
  186. unsigned char *obuf, int osize);
  188. /* These are in ppp_generic.c */
  189. extern int  ppp_register_compressor   (struct compressor *cp);
  190. extern void ppp_unregister_compressor (struct compressor *cp);
  192. /*
  193.  * the next two codes should not be changed lightly, as they must not
  194.  * lie within the contiguous general code space.
  195.  */
  196. #define CLEAR 256 /* table clear output code */
  197. #define FIRST 257 /* first free entry */
  198. #define LAST 255
  200. #define MAXCODE(b) ((1 << (b)) - 1)
  201. #define BADCODEM1 MAXCODE(MAX_BSD_BITS);
  203. #define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) 
  204.  ^ (unsigned long)(prefix))
  205. #define BSD_KEY(prefix,suffix) ((((unsigned long)(suffix)) << 16) 
  206.  + (unsigned long)(prefix))
  208. #define CHECK_GAP 10000 /* Ratio check interval */
  210. #define RATIO_SCALE_LOG 8
  211. #define RATIO_SCALE (1<<RATIO_SCALE_LOG)
  212. #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)
  214. /*
  215.  * clear the dictionary
  216.  */
  218. static void
  219. bsd_clear(struct bsd_db *db)
  220. {
  221.     db->clear_count++;
  222.     db->max_ent      = FIRST-1;
  223.     db->n_bits       = BSD_INIT_BITS;
  224.     db->bytes_out    = 0;
  225.     db->in_count     = 0;
  226.     db->ratio      = 0;
  227.     db->checkpoint   = CHECK_GAP;
  228. }
  230. /*
  231.  * If the dictionary is full, then see if it is time to reset it.
  232.  *
  233.  * Compute the compression ratio using fixed-point arithmetic
  234.  * with 8 fractional bits.
  235.  *
  236.  * Since we have an infinite stream instead of a single file,
  237.  * watch only the local compression ratio.
  238.  *
  239.  * Since both peers must reset the dictionary at the same time even in
  240.  * the absence of CLEAR codes (while packets are incompressible), they
  241.  * must compute the same ratio.
  242.  */
  244. static int bsd_check (struct bsd_db *db) /* 1=output CLEAR */
  245.   {
  246.     unsigned int new_ratio;
  248.     if (db->in_count >= db->checkpoint)
  249.       {
  250. /* age the ratio by limiting the size of the counts */
  251. if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)
  252.   {
  253.     db->in_count  -= (db->in_count  >> 2);
  254.     db->bytes_out -= (db->bytes_out >> 2);
  255.   }
  257. db->checkpoint = db->in_count + CHECK_GAP;
  259. if (db->max_ent >= db->maxmaxcode)
  260.   {
  261.     /* Reset the dictionary only if the ratio is worse,
  262.      * or if it looks as if it has been poisoned
  263.      * by incompressible data.
  264.      *
  265.      * This does not overflow, because
  266.      * db->in_count <= RATIO_MAX.
  267.      */
  269.     new_ratio = db->in_count << RATIO_SCALE_LOG;
  270.     if (db->bytes_out != 0)
  271.       {
  272. new_ratio /= db->bytes_out;
  273.       }
  274.     
  275.     if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
  276.       {
  277. bsd_clear (db);
  278. return 1;
  279.       }
  280.     db->ratio = new_ratio;
  281.   }
  282.       }
  283.     return 0;
  284.   }
  286. /*
  287.  * Return statistics.
  288.  */
  290. static void bsd_comp_stats (void *state, struct compstat *stats)
  291.   {
  292.     struct bsd_db *db = (struct bsd_db *) state;
  293.     
  294.     stats->unc_bytes    = db->uncomp_bytes;
  295.     stats->unc_packets  = db->uncomp_count;
  296.     stats->comp_bytes   = db->comp_bytes;
  297.     stats->comp_packets = db->comp_count;
  298.     stats->inc_bytes    = db->incomp_bytes;
  299.     stats->inc_packets  = db->incomp_count;
  300.     stats->in_count     = db->in_count;
  301.     stats->bytes_out    = db->bytes_out;
  302.   }
  304. /*
  305.  * Reset state, as on a CCP ResetReq.
  306.  */
  308. static void bsd_reset (void *state)
  309.   {
  310.     struct bsd_db *db = (struct bsd_db *) state;
  312.     bsd_clear(db);
  314.     db->seqno       = 0;
  315.     db->clear_count = 0;
  316.   }
  318. /*
  319.  * Release the compression structure
  320.  */
  322. static void bsd_free (void *state)
  323.   {
  324.     struct bsd_db *db = (struct bsd_db *) state;
  325.     
  326.     if (db)
  327.       {
  328. /*
  329.  * Release the dictionary
  330.  */
  331. if (db->dict)
  332.   {
  333.     vfree (db->dict);
  334.     db->dict = NULL;
  335.   }
  336. /*
  337.  * Release the string buffer
  338.  */
  339. if (db->lens)
  340.   {
  341.     vfree (db->lens);
  342.     db->lens = NULL;
  343.   }
  344. /*
  345.  * Finally release the structure itself.
  346.  */
  347. kfree (db);
  348. MOD_DEC_USE_COUNT;
  349.       }
  350.   }
  352. /*
  353.  * Allocate space for a (de) compressor.
  354.  */
  356. static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)
  357.   {
  358.     int bits;
  359.     unsigned int hsize, hshift, maxmaxcode;
  360.     struct bsd_db *db;
  362.     if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3
  363. || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  364.       {
  365. return NULL;
  366.       }
  368.     bits = BSD_NBITS(options[2]);
  370.     switch (bits)
  371.       {
  372.     case 9: /* needs 82152 for both directions */
  373.     case 10: /* needs 84144 */
  374.     case 11: /* needs 88240 */
  375.     case 12: /* needs 96432 */
  376. hsize = 5003;
  377. hshift = 4;
  378. break;
  379.     case 13: /* needs 176784 */
  380. hsize = 9001;
  381. hshift = 5;
  382. break;
  383.     case 14: /* needs 353744 */
  384. hsize = 18013;
  385. hshift = 6;
  386. break;
  387.     case 15: /* needs 691440 */
  388. hsize = 35023;
  389. hshift = 7;
  390. break;
  391.     case 16: /* needs 1366160--far too much, */
  392. /* hsize = 69001; */ /* and 69001 is too big for cptr */
  393. /* hshift = 8; */ /* in struct bsd_db */
  394. /* break; */
  395.     default:
  396. return NULL;
  397.       }
  398. /*
  399.  * Allocate the main control structure for this instance.
  400.  */
  401.     maxmaxcode = MAXCODE(bits);
  402.     db         = (struct bsd_db *) kmalloc (sizeof (struct bsd_db),
  403.     GFP_KERNEL);
  404.     if (!db)
  405.       {
  406. return NULL;
  407.       }
  409.     memset (db, 0, sizeof(struct bsd_db));
  410. /*
  411.  * Allocate space for the dictionary. This may be more than one page in
  412.  * length.
  413.  */
  414.     db->dict = (struct bsd_dict *) vmalloc (hsize *
  415.     sizeof (struct bsd_dict));
  416.     if (!db->dict)
  417.       {
  418. bsd_free (db);
  419. return NULL;
  420.       }
  422.     MOD_INC_USE_COUNT;
  423. /*
  424.  * If this is the compression buffer then there is no length data.
  425.  */
  426.     if (!decomp)
  427.       {
  428. db->lens = NULL;
  429.       }
  430. /*
  431.  * For decompression, the length information is needed as well.
  432.  */
  433.     else
  434.       {
  435.         db->lens = (unsigned short *) vmalloc ((maxmaxcode + 1) *
  436.        sizeof (db->lens[0]));
  437. if (!db->lens)
  438.   {
  439.     bsd_free (db);
  440.     return (NULL);
  441.   }
  442.       }
  443. /*
  444.  * Initialize the data information for the compression code
  445.  */
  446.     db->totlen     = sizeof (struct bsd_db)   +
  447.            (sizeof (struct bsd_dict) * hsize);
  449.     db->hsize      = hsize;
  450.     db->hshift     = hshift;
  451.     db->maxmaxcode = maxmaxcode;
  452.     db->maxbits    = bits;
  454.     return (void *) db;
  455.   }
  457. static void *bsd_comp_alloc (unsigned char *options, int opt_len)
  458.   {
  459.     return bsd_alloc (options, opt_len, 0);
  460.   }
  462. static void *bsd_decomp_alloc (unsigned char *options, int opt_len)
  463.   {
  464.     return bsd_alloc (options, opt_len, 1);
  465.   }
  467. /*
  468.  * Initialize the database.
  469.  */
  471. static int bsd_init (void *state, unsigned char *options,
  472.      int opt_len, int unit, int debug, int decomp)
  473.   {
  474.     struct bsd_db *db = state;
  475.     int indx;
  476.     
  477.     if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)
  478. || (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  479. || (BSD_NBITS(options[2]) != db->maxbits)
  480. || (decomp && db->lens == NULL))
  481.       {
  482. return 0;
  483.       }
  485.     if (decomp)
  486.       {
  487. indx = LAST;
  488. do
  489.   {
  490.     db->lens[indx] = 1;
  491.   }
  492. while (indx-- > 0);
  493.       }
  495.     indx = db->hsize;
  496.     while (indx-- != 0)
  497.       {
  498. db->dict[indx].codem1 = BADCODEM1;
  499. db->dict[indx].cptr   = 0;
  500.       }
  502.     db->unit = unit;
  503.     db->mru  = 0;
  504. #ifndef DEBUG
  505.     if (debug)
  506. #endif
  507.       db->debug = 1;
  508.     
  509.     bsd_reset(db);
  510.     
  511.     return 1;
  512.   }
  514. static int bsd_comp_init (void *state, unsigned char *options,
  515.   int opt_len, int unit, int opthdr, int debug)
  516.   {
  517.     return bsd_init (state, options, opt_len, unit, debug, 0);
  518.   }
  520. static int bsd_decomp_init (void *state, unsigned char *options,
  521.     int opt_len, int unit, int opthdr, int mru,
  522.     int debug)
  523.   {
  524.     return bsd_init (state, options, opt_len, unit, debug, 1);
  525.   }
  527. /*
  528.  * Obtain pointers to the various structures in the compression tables
  529.  */
  531. #define dict_ptrx(p,idx) &(p->dict[idx])
  532. #define lens_ptrx(p,idx) &(p->lens[idx])
  534. #ifdef DEBUG
  535. static unsigned short *lens_ptr(struct bsd_db *db, int idx)
  536.   {
  537.     if ((unsigned int) idx > (unsigned int) db->maxmaxcode)
  538.       {
  539. printk ("<9>ppp: lens_ptr(%d) > maxn", idx);
  540. idx = 0;
  541.       }
  542.     return lens_ptrx (db, idx);
  543.   }
  545. static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
  546.   {
  547.     if ((unsigned int) idx >= (unsigned int) db->hsize)
  548.       {
  549. printk ("<9>ppp: dict_ptr(%d) > maxn", idx);
  550. idx = 0;
  551.       }
  552.     return dict_ptrx (db, idx);
  553.   }
  555. #else
  556. #define lens_ptr(db,idx) lens_ptrx(db,idx)
  557. #define dict_ptr(db,idx) dict_ptrx(db,idx)
  558. #endif
  560. /*
  561.  * compress a packet
  562.  *
  563.  * The result of this function is the size of the compressed
  564.  * packet. A zero is returned if the packet was not compressed
  565.  * for some reason, such as the size being larger than uncompressed.
  566.  *
  567.  * One change from the BSD compress command is that when the
  568.  * code size expands, we do not output a bunch of padding.
  569.  */
  571. static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,
  572.  int isize, int osize)
  573.   {
  574.     struct bsd_db *db;
  575.     int hshift;
  576.     unsigned int max_ent;
  577.     unsigned int n_bits;
  578.     unsigned int bitno;
  579.     unsigned long accm;
  580.     int ent;
  581.     unsigned long fcode;
  582.     struct bsd_dict *dictp;
  583.     unsigned char c;
  584.     int hval;
  585.     int disp;
  586.     int ilen;
  587.     int mxcode;
  588.     unsigned char *wptr;
  589.     int olen;
  591. #define PUTBYTE(v)
  592.   {
  593.     ++olen;
  594.     if (wptr)
  595.       {
  596. *wptr++ = (unsigned char) (v);
  597. if (olen >= osize)
  598.   {
  599.     wptr = NULL;
  600.   }
  601.       }
  602.   }
  604. #define OUTPUT(ent)
  605.   {
  606.     bitno -= n_bits;
  607.     accm |= ((ent) << bitno);
  608.     do
  609.       {
  610. PUTBYTE(accm >> 24);
  611. accm <<= 8;
  612. bitno += 8;
  613.       }
  614.     while (bitno <= 24);
  615.   }
  617.   /*
  618.    * If the protocol is not in the range we're interested in,
  619.    * just return without compressing the packet.  If it is,
  620.    * the protocol becomes the first byte to compress.
  621.    */
  623.     ent = PPP_PROTOCOL(rptr);
  624.     if (ent < 0x21 || ent > 0xf9)
  625.       {
  626. return 0;
  627.       }
  629.     db      = (struct bsd_db *) state;
  630.     hshift  = db->hshift;
  631.     max_ent = db->max_ent;
  632.     n_bits  = db->n_bits;
  633.     bitno   = 32;
  634.     accm    = 0;
  635.     mxcode  = MAXCODE (n_bits);
  637.     /* Initialize the output pointers */
  638.     wptr  = obuf;
  639.     olen  = PPP_HDRLEN + BSD_OVHD;
  641.     if (osize > isize)
  642.       {
  643. osize = isize;
  644.       }
  646.     /* This is the PPP header information */
  647.     if (wptr)
  648.       {
  649. *wptr++ = PPP_ADDRESS(rptr);
  650. *wptr++ = PPP_CONTROL(rptr);
  651. *wptr++ = 0;
  652. *wptr++ = PPP_COMP;
  653. *wptr++ = db->seqno >> 8;
  654. *wptr++ = db->seqno;
  655.       }
  657.     /* Skip the input header */
  658.     rptr  += PPP_HDRLEN;
  659.     isize -= PPP_HDRLEN;
  660.     ilen   = ++isize; /* Low byte of protocol is counted as input */
  662.     while (--ilen > 0)
  663.       {
  664. c     = *rptr++;
  665. fcode = BSD_KEY  (ent, c);
  666. hval  = BSD_HASH (ent, c, hshift);
  667. dictp = dict_ptr (db, hval);
  669. /* Validate and then check the entry. */
  670. if (dictp->codem1 >= max_ent)
  671.   {
  672.     goto nomatch;
  673.   }
  675. if (dictp->f.fcode == fcode)
  676.   {
  677.     ent = dictp->codem1 + 1;
  678.     continue; /* found (prefix,suffix) */
  679.   }
  681. /* continue probing until a match or invalid entry */
  682. disp = (hval == 0) ? 1 : hval;
  684. do
  685.   {
  686.     hval += disp;
  687.     if (hval >= db->hsize)
  688.       {
  689. hval -= db->hsize;
  690.       }
  691.     dictp = dict_ptr (db, hval);
  692.     if (dictp->codem1 >= max_ent)
  693.       {
  694. goto nomatch;
  695.       }
  696.   }
  697. while (dictp->f.fcode != fcode);
  699. ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */
  700. continue;
  702. nomatch:
  703. OUTPUT(ent); /* output the prefix */
  705. /* code -> hashtable */
  706. if (max_ent < db->maxmaxcode)
  707.   {
  708.     struct bsd_dict *dictp2;
  709.     struct bsd_dict *dictp3;
  710.     int    indx;
  712.     /* expand code size if needed */
  713.     if (max_ent >= mxcode)
  714.       {
  715. db->n_bits = ++n_bits;
  716. mxcode     = MAXCODE (n_bits);
  717.       }
  718.     
  719.     /* Invalidate old hash table entry using
  720.      * this code, and then take it over.
  721.      */
  723.     dictp2 = dict_ptr (db, max_ent + 1);
  724.     indx   = dictp2->cptr;
  725.     dictp3 = dict_ptr (db, indx);
  727.     if (dictp3->codem1 == max_ent)
  728.       {
  729. dictp3->codem1 = BADCODEM1;
  730.       }
  732.     dictp2->cptr   = hval;
  733.     dictp->codem1  = max_ent;
  734.     dictp->f.fcode = fcode;
  735.     db->max_ent    = ++max_ent;
  737.     if (db->lens)
  738.       {
  739. unsigned short *len1 = lens_ptr (db, max_ent);
  740. unsigned short *len2 = lens_ptr (db, ent);
  741. *len1 = *len2 + 1;
  742.       }
  743.   }
  744. ent = c;
  745.       }
  746.     
  747.     OUTPUT(ent); /* output the last code */
  749.     db->bytes_out    += olen - PPP_HDRLEN - BSD_OVHD;
  750.     db->uncomp_bytes += isize;
  751.     db->in_count     += isize;
  752.     ++db->uncomp_count;
  753.     ++db->seqno;
  755.     if (bitno < 32)
  756.       {
  757. ++db->bytes_out; /* must be set before calling bsd_check */
  758.       }
  760.     /*
  761.      * Generate the clear command if needed
  762.      */
  764.     if (bsd_check(db))
  765.       {
  766. OUTPUT (CLEAR);
  767.       }
  768.     
  769.     /*
  770.      * Pad dribble bits of last code with ones.
  771.      * Do not emit a completely useless byte of ones.
  772.      */
  774.     if (bitno != 32)
  775.       {
  776. PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
  777.       }
  778.     
  779.     /*
  780.      * Increase code size if we would have without the packet
  781.      * boundary because the decompressor will do so.
  782.      */
  784.     if (max_ent >= mxcode && max_ent < db->maxmaxcode)
  785.       {
  786. db->n_bits++;
  787.       }
  789.     /* If output length is too large then this is an incomplete frame. */
  790.     if (wptr == NULL)
  791.       {
  792. ++db->incomp_count;
  793. db->incomp_bytes += isize;
  794. olen              = 0;
  795.       }
  796.     else /* Count the number of compressed frames */
  797.       {
  798. ++db->comp_count;
  799. db->comp_bytes += olen;
  800.       }
  802.     /* Return the resulting output length */
  803.     return olen;
  804. #undef OUTPUT
  805. #undef PUTBYTE
  806.   }
  808. /*
  809.  * Update the "BSD Compress" dictionary on the receiver for
  810.  * incompressible data by pretending to compress the incoming data.
  811.  */
  813. static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)
  814.   {
  815.     (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);
  816.   }
  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.  */
  835. static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
  836.    unsigned char *obuf, int osize)
  837.   {
  838.     struct bsd_db *db;
  839.     unsigned int max_ent;
  840.     unsigned long accm;
  841.     unsigned int bitno; /* 1st valid bit in accm */
  842.     unsigned int n_bits;
  843.     unsigned int tgtbitno; /* bitno when we have a code */
  844.     struct bsd_dict *dictp;
  845.     int explen;
  846.     int seq;
  847.     unsigned int incode;
  848.     unsigned int oldcode;
  849.     unsigned int finchar;
  850.     unsigned char *p;
  851.     unsigned char *wptr;
  852.     int adrs;
  853.     int ctrl;
  854.     int ilen;
  855.     int codelen;
  856.     int extra;
  858.     db       = (struct bsd_db *) state;
  859.     max_ent  = db->max_ent;
  860.     accm     = 0;
  861.     bitno    = 32; /* 1st valid bit in accm */
  862.     n_bits   = db->n_bits;
  863.     tgtbitno = 32 - n_bits; /* bitno when we have a code */
  864.     
  865.     /*
  866.      * Save the address/control from the PPP header
  867.      * and then get the sequence number.
  868.      */
  870.     adrs  = PPP_ADDRESS (ibuf);
  871.     ctrl  = PPP_CONTROL (ibuf);
  873.     seq   = (ibuf[4] << 8) + ibuf[5];
  875.     ibuf += (PPP_HDRLEN + 2);
  876.     ilen  = isize - (PPP_HDRLEN + 2);
  877.     
  878.     /*
  879.      * Check the sequence number and give up if it differs from
  880.      * the value we're expecting.
  881.      */
  883.     if (seq != db->seqno)
  884.       {
  885. if (db->debug)
  886.   {
  887.     printk("bsd_decomp%d: bad sequence # %d, expected %dn",
  888.    db->unit, seq, db->seqno - 1);
  889.   }
  890. return DECOMP_ERROR;
  891.       }
  893.     ++db->seqno;
  894.     db->bytes_out += ilen;
  896.     /*
  897.      * Fill in the ppp header, but not the last byte of the protocol
  898.      * (that comes from the decompressed data).
  899.      */
  901.     wptr    = obuf;
  902.     *wptr++ = adrs;
  903.     *wptr++ = ctrl;
  904.     *wptr++ = 0;
  905.     
  906.     oldcode = CLEAR;
  907.     explen  = 3;
  909.     /*
  910.      * Keep the checkpoint correctly so that incompressible packets
  911.      * clear the dictionary at the proper times.
  912.      */
  914.     for (;;)
  915.       {
  916. if (ilen-- <= 0)
  917.   {
  918.     db->in_count += (explen - 3); /* don't count the header */
  919.     break;
  920.   }
  922. /*
  923.  * Accumulate bytes until we have a complete code.
  924.  * Then get the next code, relying on the 32-bit,
  925.  * unsigned accm to mask the result.
  926.  */
  928. bitno -= 8;
  929. accm  |= *ibuf++ << bitno;
  930. if (tgtbitno < bitno)
  931.   {
  932.     continue;
  933.   }
  935. incode = accm >> tgtbitno;
  936. accm <<= n_bits;
  937. bitno += n_bits;
  939. /*
  940.  * The dictionary must only be cleared at the end of a packet.
  941.  */
  943. if (incode == CLEAR)
  944.   {
  945.     if (ilen > 0)
  946.       {
  947. if (db->debug)
  948.   {
  949.     printk("bsd_decomp%d: bad CLEARn", db->unit);
  950.   }
  951. return DECOMP_FATALERROR; /* probably a bug */
  952.       }
  953.     
  954.     bsd_clear(db);
  955.     break;
  956.   }
  958. if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
  959.     || (incode > max_ent && oldcode == CLEAR))
  960.   {
  961.     if (db->debug)
  962.       {
  963. printk("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
  964.        db->unit, incode, oldcode);
  965. printk("max_ent=0x%x explen=%d seqno=%dn",
  966.        max_ent, explen, db->seqno);
  967.       }
  968.     return DECOMP_FATALERROR; /* probably a bug */
  969.   }
  971. /* Special case for KwKwK string. */
  972. if (incode > max_ent)
  973.   {
  974.     finchar = oldcode;
  975.     extra   = 1;
  976.   }
  977. else
  978.   {
  979.     finchar = incode;
  980.     extra   = 0;
  981.   }
  983. codelen = *(lens_ptr (db, finchar));
  984. explen += codelen + extra;
  985. if (explen > osize)
  986.   {
  987.     if (db->debug)
  988.       {
  989. printk("bsd_decomp%d: ran out of mrun", db->unit);
  990. #ifdef DEBUG
  991. printk("  len=%d, finchar=0x%x, codelen=%d, explen=%dn",
  992.        ilen, finchar, codelen, explen);
  993. #endif
  994.       }
  995.     return DECOMP_FATALERROR;
  996.   }
  998. /*
  999.  * Decode this code and install it in the decompressed buffer.
  1000.  */
  1002. wptr += codelen;
  1003. p     = wptr;
  1004. while (finchar > LAST)
  1005.   {
  1006.     struct bsd_dict *dictp2 = dict_ptr (db, finchar);
  1007.     
  1008.     dictp = dict_ptr (db, dictp2->cptr);
  1009. #ifdef DEBUG
  1010.     if (--codelen <= 0 || dictp->codem1 != finchar-1)
  1011.       {
  1012. if (codelen <= 0)
  1013.   {
  1014.     printk("bsd_decomp%d: fell off end of chain ", db->unit);
  1015.     printk("0x%x at 0x%x by 0x%x, max_ent=0x%xn",
  1016.    incode, finchar, dictp2->cptr, max_ent);
  1017.   }
  1018. else
  1019.   {
  1020.     if (dictp->codem1 != finchar-1)
  1021.       {
  1022. printk("bsd_decomp%d: bad code chain 0x%x "
  1023.        "finchar=0x%x ",
  1024.        db->unit, incode, finchar);
  1026. printk("oldcode=0x%x cptr=0x%x codem1=0x%xn",
  1027.        oldcode, dictp2->cptr, dictp->codem1);
  1028.       }
  1029.   }
  1030. return DECOMP_FATALERROR;
  1031.       }
  1032. #endif
  1033.     *--p    = dictp->f.hs.suffix;
  1034.     finchar = dictp->f.hs.prefix;
  1035.   }
  1036. *--p = finchar;
  1038. #ifdef DEBUG
  1039. if (--codelen != 0)
  1040.   {
  1041.     printk("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%xn",
  1042.    db->unit, codelen, incode, max_ent);
  1043.   }
  1044. #endif
  1046. if (extra) /* the KwKwK case again */
  1047.   {
  1048.     *wptr++ = finchar;
  1049.   }
  1051. /*
  1052.  * If not first code in a packet, and
  1053.  * if not out of code space, then allocate a new code.
  1054.  *
  1055.  * Keep the hash table correct so it can be used
  1056.  * with uncompressed packets.
  1057.  */
  1059. if (oldcode != CLEAR && max_ent < db->maxmaxcode)
  1060.   {
  1061.     struct bsd_dict *dictp2, *dictp3;
  1062.     unsigned short  *lens1,  *lens2;
  1063.     unsigned long fcode;
  1064.     int hval, disp, indx;
  1065.     
  1066.     fcode = BSD_KEY(oldcode,finchar);
  1067.     hval  = BSD_HASH(oldcode,finchar,db->hshift);
  1068.     dictp = dict_ptr (db, hval);
  1069.     
  1070.     /* look for a free hash table entry */
  1071.     if (dictp->codem1 < max_ent)
  1072.       {
  1073. disp = (hval == 0) ? 1 : hval;
  1074. do
  1075.   {
  1076.     hval += disp;
  1077.     if (hval >= db->hsize)
  1078.       {
  1079. hval -= db->hsize;
  1080.       }
  1081.     dictp = dict_ptr (db, hval);
  1082.   }
  1083. while (dictp->codem1 < max_ent);
  1084.       }
  1085.     
  1086.     /*
  1087.      * Invalidate previous hash table entry
  1088.      * assigned this code, and then take it over
  1089.      */
  1091.     dictp2 = dict_ptr (db, max_ent + 1);
  1092.     indx   = dictp2->cptr;
  1093.     dictp3 = dict_ptr (db, indx);
  1095.     if (dictp3->codem1 == max_ent)
  1096.       {
  1097. dictp3->codem1 = BADCODEM1;
  1098.       }
  1100.     dictp2->cptr   = hval;
  1101.     dictp->codem1  = max_ent;
  1102.     dictp->f.fcode = fcode;
  1103.     db->max_ent    = ++max_ent;
  1105.     /* Update the length of this string. */
  1106.     lens1  = lens_ptr (db, max_ent);
  1107.     lens2  = lens_ptr (db, oldcode);
  1108.     *lens1 = *lens2 + 1;
  1109.     
  1110.     /* Expand code size if needed. */
  1111.     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  1112.       {
  1113. db->n_bits = ++n_bits;
  1114. tgtbitno   = 32-n_bits;
  1115.       }
  1116.   }
  1117. oldcode = incode;
  1118.       }
  1120.     ++db->comp_count;
  1121.     ++db->uncomp_count;
  1122.     db->comp_bytes   += isize - BSD_OVHD - PPP_HDRLEN;
  1123.     db->uncomp_bytes += explen;
  1125.     if (bsd_check(db))
  1126.       {
  1127. if (db->debug)
  1128.   {
  1129.     printk("bsd_decomp%d: peer should have cleared dictionary on %dn",
  1130.    db->unit, db->seqno - 1);
  1131.   }
  1132.       }
  1133.     return explen;
  1134.   }
  1135.      
  1136. /*************************************************************
  1137.  * Table of addresses for the BSD compression module
  1138.  *************************************************************/
  1140. static struct compressor ppp_bsd_compress = {
  1141.     CI_BSD_COMPRESS, /* compress_proto */
  1142.     bsd_comp_alloc, /* comp_alloc */
  1143.     bsd_free, /* comp_free */
  1144.     bsd_comp_init, /* comp_init */
  1145.     bsd_reset, /* comp_reset */
  1146.     bsd_compress, /* compress */
  1147.     bsd_comp_stats, /* comp_stat */
  1148.     bsd_decomp_alloc, /* decomp_alloc */
  1149.     bsd_free, /* decomp_free */
  1150.     bsd_decomp_init, /* decomp_init */
  1151.     bsd_reset, /* decomp_reset */
  1152.     bsd_decompress, /* decompress */
  1153.     bsd_incomp, /* incomp */
  1154.     bsd_comp_stats /* decomp_stat */
  1155. };
  1157. /*************************************************************
  1158.  * Module support routines
  1159.  *************************************************************/
  1161. int __init bsdcomp_init(void)
  1162. {
  1163. int answer = ppp_register_compressor(&ppp_bsd_compress);
  1164. if (answer == 0)
  1165. printk(KERN_INFO "PPP BSD Compression module registeredn");
  1166. return answer;
  1167. }
  1169. void __exit bsdcomp_cleanup(void)
  1170. {
  1171. ppp_unregister_compressor(&ppp_bsd_compress);
  1172. }
  1174. module_init(bsdcomp_init);
  1175. module_exit(bsdcomp_cleanup);
  1176. MODULE_LICENSE("Dual BSD/GPL");