net/ppp/bsd_comp.c

0001 /*
0002  * Update: The Berkeley copyright was changed, and the change
0003  * is retroactive to all "true" BSD software (ie everything
0004  * from UCB as opposed to other peoples code that just carried
0005  * the same license). The new copyright doesn't clash with the
0006  * GPL, so the module-only restriction has been removed..
0007  */
0008
0009 /* Because this code is derived from the 4.3BSD compress source:
0010  *
0011  * Copyright (c) 1985, 1986 The Regents of the University of California.
0012  * All rights reserved.
0013  *
0014  * This code is derived from software contributed to Berkeley by
0015  * James A. Woods, derived from original work by Spencer Thomas
0016  * and Joseph Orost.
0017  *
0018  * Redistribution and use in source and binary forms, with or without
0019  * modification, are permitted provided that the following conditions
0020  * are met:
0021  * 1. Redistributions of source code must retain the above copyright
0022  *    notice, this list of conditions and the following disclaimer.
0023  * 2. Redistributions in binary form must reproduce the above copyright
0024  *    notice, this list of conditions and the following disclaimer in the
0025  *    documentation and/or other materials provided with the distribution.
0026  * 3. All advertising materials mentioning features or use of this software
0027  *    must display the following acknowledgement:
0028  *  This product includes software developed by the University of
0029  *  California, Berkeley and its contributors.
0030  * 4. Neither the name of the University nor the names of its contributors
0031  *    may be used to endorse or promote products derived from this software
0032  *    without specific prior written permission.
0033  *
0034  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
0035  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0036  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0037  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
0038  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
0039  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
0040  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
0041  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
0042  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
0043  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
0044  * SUCH DAMAGE.
0045  */
0046
0047 /*
0048  * This version is for use with contiguous buffers on Linux-derived systems.
0049  *
0050  *  ==FILEVERSION 20000226==
0051  *
0052  *  NOTE TO MAINTAINERS:
0053  *     If you modify this file at all, please set the number above to the
0054  *     date of the modification as YYMMDD (year month day).
0055  *     bsd_comp.c is shipped with a PPP distribution as well as with
0056  *     the kernel; if everyone increases the FILEVERSION number above,
0057  *     then scripts can do the right thing when deciding whether to
0058  *     install a new bsd_comp.c file. Don't change the format of that
0059  *     line otherwise, so the installation script can recognize it.
0060  *
0061  * From: bsd_comp.c,v 1.3 1994/12/08 01:59:58 paulus Exp
0062  */
0063
0064 #include <linux/module.h>
0065 #include <linux/init.h>
0066 #include <linux/slab.h>
0067 #include <linux/vmalloc.h>
0068 #include <linux/string.h>
0069
0070 #include <linux/ppp_defs.h>
0071
0072 #undef   PACKETPTR
0073 #define  PACKETPTR 1
0074 #include <linux/ppp-comp.h>
0075 #undef   PACKETPTR
0076
0077 #include <asm/byteorder.h>
0078
0079 /*
0080  * PPP "BSD compress" compression
0081  *  The differences between this compression and the classic BSD LZW
0082  *  source are obvious from the requirement that the classic code worked
0083  *  with files while this handles arbitrarily long streams that
0084  *  are broken into packets.  They are:
0085  *
0086  *  When the code size expands, a block of junk is not emitted by
0087  *      the compressor and not expected by the decompressor.
0088  *
0089  *  New codes are not necessarily assigned every time an old
0090  *      code is output by the compressor.  This is because a packet
0091  *      end forces a code to be emitted, but does not imply that a
0092  *      new sequence has been seen.
0093  *
0094  *  The compression ratio is checked at the first end of a packet
0095  *      after the appropriate gap.  Besides simplifying and speeding
0096  *      things up, this makes it more likely that the transmitter
0097  *      and receiver will agree when the dictionary is cleared when
0098  *      compression is not going well.
0099  */
0100
0101 /*
0102  * Macros to extract protocol version and number of bits
0103  * from the third byte of the BSD Compress CCP configuration option.
0104  */
0105
0106 #define BSD_VERSION(x)  ((x) >> 5)
0107 #define BSD_NBITS(x)    ((x) & 0x1F)
0108
0109 #define BSD_CURRENT_VERSION 1
0110
0111 /*
0112  * A dictionary for doing BSD compress.
0113  */
0114
0115 struct bsd_dict {
0116     union {             /* hash value */
0117     unsigned long   fcode;
0118     struct {
0119 #if defined(__LITTLE_ENDIAN)        /* Little endian order */
0120         unsigned short  prefix; /* preceding code */
0121         unsigned char   suffix; /* last character of new code */
0122         unsigned char   pad;
0123 #elif defined(__BIG_ENDIAN)     /* Big endian order */
0124         unsigned char   pad;
0125         unsigned char   suffix; /* last character of new code */
0126         unsigned short  prefix; /* preceding code */
0127 #else
0128 #error Endianness not defined...
0129 #endif
0130     } hs;
0131     } f;
0132     unsigned short codem1;      /* output of hash table -1 */
0133     unsigned short cptr;        /* map code to hash table entry */
0134 };
0135
0136 struct bsd_db {
0137     int     totlen;         /* length of this structure */
0138     unsigned int   hsize;       /* size of the hash table */
0139     unsigned char  hshift;      /* used in hash function */
0140     unsigned char  n_bits;      /* current bits/code */
0141     unsigned char  maxbits;     /* maximum bits/code */
0142     unsigned char  debug;       /* non-zero if debug desired */
0143     unsigned char  unit;        /* ppp unit number */
0144     unsigned short seqno;       /* sequence # of next packet */
0145     unsigned int   mru;         /* size of receive (decompress) bufr */
0146     unsigned int   maxmaxcode;      /* largest valid code */
0147     unsigned int   max_ent;     /* largest code in use */
0148     unsigned int   in_count;        /* uncompressed bytes, aged */
0149     unsigned int   bytes_out;       /* compressed bytes, aged */
0150     unsigned int   ratio;       /* recent compression ratio */
0151     unsigned int   checkpoint;      /* when to next check the ratio */
0152     unsigned int   clear_count;     /* times dictionary cleared */
0153     unsigned int   incomp_count;    /* incompressible packets */
0154     unsigned int   incomp_bytes;    /* incompressible bytes */
0155     unsigned int   uncomp_count;    /* uncompressed packets */
0156     unsigned int   uncomp_bytes;    /* uncompressed bytes */
0157     unsigned int   comp_count;      /* compressed packets */
0158     unsigned int   comp_bytes;      /* compressed bytes */
0159     unsigned short  *lens;      /* array of lengths of codes */
0160     struct bsd_dict *dict;      /* dictionary */
0161 };
0162
0163 #define BSD_OVHD    2       /* BSD compress overhead/packet */
0164 #define MIN_BSD_BITS    9
0165 #define BSD_INIT_BITS   MIN_BSD_BITS
0166 #define MAX_BSD_BITS    15
0167
0168 static void bsd_free (void *state);
0169 static void *bsd_alloc(unsigned char *options, int opt_len, int decomp);
0170 static void *bsd_comp_alloc (unsigned char *options, int opt_len);
0171 static void *bsd_decomp_alloc (unsigned char *options, int opt_len);
0172
0173 static int  bsd_init        (void *db, unsigned char *options,
0174                      int opt_len, int unit, int debug, int decomp);
0175 static int  bsd_comp_init   (void *state, unsigned char *options,
0176                      int opt_len, int unit, int opthdr, int debug);
0177 static int  bsd_decomp_init (void *state, unsigned char *options,
0178                  int opt_len, int unit, int opthdr, int mru,
0179                  int debug);
0180
0181 static void bsd_reset (void *state);
0182 static void bsd_comp_stats (void *state, struct compstat *stats);
0183
0184 static int  bsd_compress (void *state, unsigned char *rptr,
0185                   unsigned char *obuf, int isize, int osize);
0186 static void bsd_incomp (void *state, unsigned char *ibuf, int icnt);
0187
0188 static int  bsd_decompress (void *state, unsigned char *ibuf, int isize,
0189                 unsigned char *obuf, int osize);
0190
0191 /* These are in ppp_generic.c */
0192 extern int  ppp_register_compressor   (struct compressor *cp);
0193 extern void ppp_unregister_compressor (struct compressor *cp);
0194
0195 /*
0196  * the next two codes should not be changed lightly, as they must not
0197  * lie within the contiguous general code space.
0198  */
0199 #define CLEAR   256         /* table clear output code */
0200 #define FIRST   257         /* first free entry */
0201 #define LAST    255
0202
0203 #define MAXCODE(b)  ((1 << (b)) - 1)
0204 #define BADCODEM1   MAXCODE(MAX_BSD_BITS)
0205
0206 #define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) \
0207                      ^ (unsigned long)(prefix))
0208 #define BSD_KEY(prefix,suffix)      ((((unsigned long)(suffix)) << 16) \
0209                      + (unsigned long)(prefix))
0210
0211 #define CHECK_GAP   10000       /* Ratio check interval */
0212
0213 #define RATIO_SCALE_LOG 8
0214 #define RATIO_SCALE (1<<RATIO_SCALE_LOG)
0215 #define RATIO_MAX   (0x7fffffff>>RATIO_SCALE_LOG)
0216
0217 /*
0218  * clear the dictionary
0219  */
0220
0221 static void
0222 bsd_clear(struct bsd_db *db)
0223 {
0224     db->clear_count++;
0225     db->max_ent      = FIRST-1;
0226     db->n_bits       = BSD_INIT_BITS;
0227     db->bytes_out    = 0;
0228     db->in_count     = 0;
0229     db->ratio        = 0;
0230     db->checkpoint   = CHECK_GAP;
0231 }
0232
0233 /*
0234  * If the dictionary is full, then see if it is time to reset it.
0235  *
0236  * Compute the compression ratio using fixed-point arithmetic
0237  * with 8 fractional bits.
0238  *
0239  * Since we have an infinite stream instead of a single file,
0240  * watch only the local compression ratio.
0241  *
0242  * Since both peers must reset the dictionary at the same time even in
0243  * the absence of CLEAR codes (while packets are incompressible), they
0244  * must compute the same ratio.
0245  */
0246
0247 static int bsd_check (struct bsd_db *db)    /* 1=output CLEAR */
0248   {
0249     unsigned int new_ratio;
0250
0251     if (db->in_count >= db->checkpoint)
0252       {
0253     /* age the ratio by limiting the size of the counts */
0254     if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)
0255       {
0256         db->in_count  -= (db->in_count  >> 2);
0257         db->bytes_out -= (db->bytes_out >> 2);
0258       }
0259
0260     db->checkpoint = db->in_count + CHECK_GAP;
0261
0262     if (db->max_ent >= db->maxmaxcode)
0263       {
0264         /* Reset the dictionary only if the ratio is worse,
0265          * or if it looks as if it has been poisoned
0266          * by incompressible data.
0267          *
0268          * This does not overflow, because
0269          *  db->in_count <= RATIO_MAX.
0270          */
0271
0272         new_ratio = db->in_count << RATIO_SCALE_LOG;
0273         if (db->bytes_out != 0)
0274           {
0275         new_ratio /= db->bytes_out;
0276           }
0277
0278         if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
0279           {
0280         bsd_clear (db);
0281         return 1;
0282           }
0283         db->ratio = new_ratio;
0284       }
0285       }
0286     return 0;
0287   }
0288
0289 /*
0290  * Return statistics.
0291  */
0292
0293 static void bsd_comp_stats (void *state, struct compstat *stats)
0294   {
0295     struct bsd_db *db = (struct bsd_db *) state;
0296
0297     stats->unc_bytes    = db->uncomp_bytes;
0298     stats->unc_packets  = db->uncomp_count;
0299     stats->comp_bytes   = db->comp_bytes;
0300     stats->comp_packets = db->comp_count;
0301     stats->inc_bytes    = db->incomp_bytes;
0302     stats->inc_packets  = db->incomp_count;
0303     stats->in_count     = db->in_count;
0304     stats->bytes_out    = db->bytes_out;
0305   }
0306
0307 /*
0308  * Reset state, as on a CCP ResetReq.
0309  */
0310
0311 static void bsd_reset (void *state)
0312   {
0313     struct bsd_db *db = (struct bsd_db *) state;
0314
0315     bsd_clear(db);
0316
0317     db->seqno       = 0;
0318     db->clear_count = 0;
0319   }
0320
0321 /*
0322  * Release the compression structure
0323  */
0324
0325 static void bsd_free (void *state)
0326 {
0327     struct bsd_db *db = state;
0328
0329     if (!db)
0330         return;
0331
0332 /*
0333  * Release the dictionary
0334  */
0335     vfree(db->dict);
0336     db->dict = NULL;
0337 /*
0338  * Release the string buffer
0339  */
0340     vfree(db->lens);
0341     db->lens = NULL;
0342 /*
0343  * Finally release the structure itself.
0344  */
0345     kfree(db);
0346 }
0347
0348 /*
0349  * Allocate space for a (de) compressor.
0350  */
0351
0352 static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)
0353   {
0354     int bits;
0355     unsigned int hsize, hshift, maxmaxcode;
0356     struct bsd_db *db;
0357
0358     if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3
0359     || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
0360       {
0361     return NULL;
0362       }
0363
0364     bits = BSD_NBITS(options[2]);
0365
0366     switch (bits)
0367       {
0368     case 9:         /* needs 82152 for both directions */
0369     case 10:            /* needs 84144 */
0370     case 11:            /* needs 88240 */
0371     case 12:            /* needs 96432 */
0372     hsize = 5003;
0373     hshift = 4;
0374     break;
0375     case 13:            /* needs 176784 */
0376     hsize = 9001;
0377     hshift = 5;
0378     break;
0379     case 14:            /* needs 353744 */
0380     hsize = 18013;
0381     hshift = 6;
0382     break;
0383     case 15:            /* needs 691440 */
0384     hsize = 35023;
0385     hshift = 7;
0386     break;
0387     case 16:            /* needs 1366160--far too much, */
0388     /* hsize = 69001; */    /* and 69001 is too big for cptr */
0389     /* hshift = 8; */   /* in struct bsd_db */
0390     /* break; */
0391     default:
0392     return NULL;
0393       }
0394 /*
0395  * Allocate the main control structure for this instance.
0396  */
0397     maxmaxcode = MAXCODE(bits);
0398     db         = kzalloc(sizeof (struct bsd_db),
0399                         GFP_KERNEL);
0400     if (!db)
0401       {
0402     return NULL;
0403       }
0404
0405 /*
0406  * Allocate space for the dictionary. This may be more than one page in
0407  * length.
0408  */
0409     db->dict = vmalloc(array_size(hsize, sizeof(struct bsd_dict)));
0410     if (!db->dict)
0411       {
0412     bsd_free (db);
0413     return NULL;
0414       }
0415
0416 /*
0417  * If this is the compression buffer then there is no length data.
0418  */
0419     if (!decomp)
0420       {
0421     db->lens = NULL;
0422       }
0423 /*
0424  * For decompression, the length information is needed as well.
0425  */
0426     else
0427       {
0428         db->lens = vmalloc(array_size(sizeof(db->lens[0]), (maxmaxcode + 1)));
0429     if (!db->lens)
0430       {
0431         bsd_free (db);
0432         return NULL;
0433       }
0434       }
0435 /*
0436  * Initialize the data information for the compression code
0437  */
0438     db->totlen     = sizeof (struct bsd_db)   +
0439             (sizeof (struct bsd_dict) * hsize);
0440
0441     db->hsize      = hsize;
0442     db->hshift     = hshift;
0443     db->maxmaxcode = maxmaxcode;
0444     db->maxbits    = bits;
0445
0446     return (void *) db;
0447   }
0448
0449 static void *bsd_comp_alloc (unsigned char *options, int opt_len)
0450   {
0451     return bsd_alloc (options, opt_len, 0);
0452   }
0453
0454 static void *bsd_decomp_alloc (unsigned char *options, int opt_len)
0455   {
0456     return bsd_alloc (options, opt_len, 1);
0457   }
0458
0459 /*
0460  * Initialize the database.
0461  */
0462
0463 static int bsd_init (void *state, unsigned char *options,
0464              int opt_len, int unit, int debug, int decomp)
0465   {
0466     struct bsd_db *db = state;
0467     int indx;
0468
0469     if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)
0470     || (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
0471     || (BSD_NBITS(options[2]) != db->maxbits)
0472     || (decomp && db->lens == NULL))
0473       {
0474     return 0;
0475       }
0476
0477     if (decomp)
0478       {
0479     indx = LAST;
0480     do
0481       {
0482         db->lens[indx] = 1;
0483       }
0484     while (indx-- > 0);
0485       }
0486
0487     indx = db->hsize;
0488     while (indx-- != 0)
0489       {
0490     db->dict[indx].codem1 = BADCODEM1;
0491     db->dict[indx].cptr   = 0;
0492       }
0493
0494     db->unit = unit;
0495     db->mru  = 0;
0496 #ifndef DEBUG
0497     if (debug)
0498 #endif
0499       db->debug = 1;
0500
0501     bsd_reset(db);
0502
0503     return 1;
0504   }
0505
0506 static int bsd_comp_init (void *state, unsigned char *options,
0507               int opt_len, int unit, int opthdr, int debug)
0508   {
0509     return bsd_init (state, options, opt_len, unit, debug, 0);
0510   }
0511
0512 static int bsd_decomp_init (void *state, unsigned char *options,
0513                 int opt_len, int unit, int opthdr, int mru,
0514                 int debug)
0515   {
0516     return bsd_init (state, options, opt_len, unit, debug, 1);
0517   }
0518
0519 /*
0520  * Obtain pointers to the various structures in the compression tables
0521  */
0522
0523 #define dict_ptrx(p,idx) &(p->dict[idx])
0524 #define lens_ptrx(p,idx) &(p->lens[idx])
0525
0526 #ifdef DEBUG
0527 static unsigned short *lens_ptr(struct bsd_db *db, int idx)
0528   {
0529     if ((unsigned int) idx > (unsigned int) db->maxmaxcode)
0530       {
0531     printk ("<9>ppp: lens_ptr(%d) > max\n", idx);
0532     idx = 0;
0533       }
0534     return lens_ptrx (db, idx);
0535   }
0536
0537 static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
0538   {
0539     if ((unsigned int) idx >= (unsigned int) db->hsize)
0540       {
0541     printk ("<9>ppp: dict_ptr(%d) > max\n", idx);
0542     idx = 0;
0543       }
0544     return dict_ptrx (db, idx);
0545   }
0546
0547 #else
0548 #define lens_ptr(db,idx) lens_ptrx(db,idx)
0549 #define dict_ptr(db,idx) dict_ptrx(db,idx)
0550 #endif
0551
0552 /*
0553  * compress a packet
0554  *
0555  *  The result of this function is the size of the compressed
0556  *  packet. A zero is returned if the packet was not compressed
0557  *  for some reason, such as the size being larger than uncompressed.
0558  *
0559  *  One change from the BSD compress command is that when the
0560  *  code size expands, we do not output a bunch of padding.
0561  */
0562
0563 static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,
0564              int isize, int osize)
0565   {
0566     struct bsd_db *db;
0567     int hshift;
0568     unsigned int max_ent;
0569     unsigned int n_bits;
0570     unsigned int bitno;
0571     unsigned long accm;
0572     int ent;
0573     unsigned long fcode;
0574     struct bsd_dict *dictp;
0575     unsigned char c;
0576     int hval;
0577     int disp;
0578     int ilen;
0579     int mxcode;
0580     unsigned char *wptr;
0581     int olen;
0582
0583 #define PUTBYTE(v)          \
0584   {                 \
0585     ++olen;             \
0586     if (wptr)               \
0587       {                 \
0588     *wptr++ = (unsigned char) (v);  \
0589     if (olen >= osize)      \
0590       {             \
0591         wptr = NULL;        \
0592       }             \
0593       }                 \
0594   }
0595
0596 #define OUTPUT(ent)         \
0597   {                 \
0598     bitno -= n_bits;            \
0599     accm |= ((ent) << bitno);       \
0600     do                  \
0601       {                 \
0602     PUTBYTE(accm >> 24);        \
0603     accm <<= 8;         \
0604     bitno += 8;         \
0605       }                 \
0606     while (bitno <= 24);        \
0607   }
0608
0609   /*
0610    * If the protocol is not in the range we're interested in,
0611    * just return without compressing the packet.  If it is,
0612    * the protocol becomes the first byte to compress.
0613    */
0614
0615     ent = PPP_PROTOCOL(rptr);
0616     if (ent < 0x21 || ent > 0xf9)
0617       {
0618     return 0;
0619       }
0620
0621     db      = (struct bsd_db *) state;
0622     hshift  = db->hshift;
0623     max_ent = db->max_ent;
0624     n_bits  = db->n_bits;
0625     bitno   = 32;
0626     accm    = 0;
0627     mxcode  = MAXCODE (n_bits);
0628
0629     /* Initialize the output pointers */
0630     wptr  = obuf;
0631     olen  = PPP_HDRLEN + BSD_OVHD;
0632
0633     if (osize > isize)
0634       {
0635     osize = isize;
0636       }
0637
0638     /* This is the PPP header information */
0639     if (wptr)
0640       {
0641     *wptr++ = PPP_ADDRESS(rptr);
0642     *wptr++ = PPP_CONTROL(rptr);
0643     *wptr++ = 0;
0644     *wptr++ = PPP_COMP;
0645     *wptr++ = db->seqno >> 8;
0646     *wptr++ = db->seqno;
0647       }
0648
0649     /* Skip the input header */
0650     rptr  += PPP_HDRLEN;
0651     isize -= PPP_HDRLEN;
0652     ilen   = ++isize;   /* Low byte of protocol is counted as input */
0653
0654     while (--ilen > 0)
0655       {
0656     c     = *rptr++;
0657     fcode = BSD_KEY  (ent, c);
0658     hval  = BSD_HASH (ent, c, hshift);
0659     dictp = dict_ptr (db, hval);
0660
0661     /* Validate and then check the entry. */
0662     if (dictp->codem1 >= max_ent)
0663       {
0664         goto nomatch;
0665       }
0666
0667     if (dictp->f.fcode == fcode)
0668       {
0669         ent = dictp->codem1 + 1;
0670         continue;   /* found (prefix,suffix) */
0671       }
0672
0673     /* continue probing until a match or invalid entry */
0674     disp = (hval == 0) ? 1 : hval;
0675
0676     do
0677       {
0678         hval += disp;
0679         if (hval >= db->hsize)
0680           {
0681         hval -= db->hsize;
0682           }
0683         dictp = dict_ptr (db, hval);
0684         if (dictp->codem1 >= max_ent)
0685           {
0686         goto nomatch;
0687           }
0688       }
0689     while (dictp->f.fcode != fcode);
0690
0691     ent = dictp->codem1 + 1;    /* finally found (prefix,suffix) */
0692     continue;
0693
0694 nomatch:
0695     OUTPUT(ent);        /* output the prefix */
0696
0697     /* code -> hashtable */
0698     if (max_ent < db->maxmaxcode)
0699       {
0700         struct bsd_dict *dictp2;
0701         struct bsd_dict *dictp3;
0702         int    indx;
0703
0704         /* expand code size if needed */
0705         if (max_ent >= mxcode)
0706           {
0707         db->n_bits = ++n_bits;
0708         mxcode     = MAXCODE (n_bits);
0709           }
0710
0711         /* Invalidate old hash table entry using
0712          * this code, and then take it over.
0713          */
0714
0715         dictp2 = dict_ptr (db, max_ent + 1);
0716         indx   = dictp2->cptr;
0717         dictp3 = dict_ptr (db, indx);
0718
0719         if (dictp3->codem1 == max_ent)
0720           {
0721         dictp3->codem1 = BADCODEM1;
0722           }
0723
0724         dictp2->cptr   = hval;
0725         dictp->codem1  = max_ent;
0726         dictp->f.fcode = fcode;
0727         db->max_ent    = ++max_ent;
0728
0729         if (db->lens)
0730           {
0731         unsigned short *len1 = lens_ptr (db, max_ent);
0732         unsigned short *len2 = lens_ptr (db, ent);
0733         *len1 = *len2 + 1;
0734           }
0735       }
0736     ent = c;
0737       }
0738
0739     OUTPUT(ent);        /* output the last code */
0740
0741     db->bytes_out    += olen - PPP_HDRLEN - BSD_OVHD;
0742     db->uncomp_bytes += isize;
0743     db->in_count     += isize;
0744     ++db->uncomp_count;
0745     ++db->seqno;
0746
0747     if (bitno < 32)
0748       {
0749     ++db->bytes_out; /* must be set before calling bsd_check */
0750       }
0751
0752     /*
0753      * Generate the clear command if needed
0754      */
0755
0756     if (bsd_check(db))
0757       {
0758     OUTPUT (CLEAR);
0759       }
0760
0761     /*
0762      * Pad dribble bits of last code with ones.
0763      * Do not emit a completely useless byte of ones.
0764      */
0765
0766     if (bitno != 32)
0767       {
0768     PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
0769       }
0770
0771     /*
0772      * Increase code size if we would have without the packet
0773      * boundary because the decompressor will do so.
0774      */
0775
0776     if (max_ent >= mxcode && max_ent < db->maxmaxcode)
0777       {
0778     db->n_bits++;
0779       }
0780
0781     /* If output length is too large then this is an incomplete frame. */
0782     if (wptr == NULL)
0783       {
0784     ++db->incomp_count;
0785     db->incomp_bytes += isize;
0786     olen              = 0;
0787       }
0788     else /* Count the number of compressed frames */
0789       {
0790     ++db->comp_count;
0791     db->comp_bytes += olen;
0792       }
0793
0794     /* Return the resulting output length */
0795     return olen;
0796 #undef OUTPUT
0797 #undef PUTBYTE
0798   }
0799
0800 /*
0801  * Update the "BSD Compress" dictionary on the receiver for
0802  * incompressible data by pretending to compress the incoming data.
0803  */
0804
0805 static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)
0806   {
0807     (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);
0808   }
0809
0810 /*
0811  * Decompress "BSD Compress".
0812  *
0813  * Because of patent problems, we return DECOMP_ERROR for errors
0814  * found by inspecting the input data and for system problems, but
0815  * DECOMP_FATALERROR for any errors which could possibly be said to
0816  * be being detected "after" decompression.  For DECOMP_ERROR,
0817  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
0818  * infringing a patent of Motorola's if we do, so we take CCP down
0819  * instead.
0820  *
0821  * Given that the frame has the correct sequence number and a good FCS,
0822  * errors such as invalid codes in the input most likely indicate a
0823  * bug, so we return DECOMP_FATALERROR for them in order to turn off
0824  * compression, even though they are detected by inspecting the input.
0825  */
0826
0827 static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
0828                unsigned char *obuf, int osize)
0829   {
0830     struct bsd_db *db;
0831     unsigned int max_ent;
0832     unsigned long accm;
0833     unsigned int bitno;     /* 1st valid bit in accm */
0834     unsigned int n_bits;
0835     unsigned int tgtbitno;  /* bitno when we have a code */
0836     struct bsd_dict *dictp;
0837     int explen;
0838     int seq;
0839     unsigned int incode;
0840     unsigned int oldcode;
0841     unsigned int finchar;
0842     unsigned char *p;
0843     unsigned char *wptr;
0844     int adrs;
0845     int ctrl;
0846     int ilen;
0847     int codelen;
0848     int extra;
0849
0850     db       = (struct bsd_db *) state;
0851     max_ent  = db->max_ent;
0852     accm     = 0;
0853     bitno    = 32;      /* 1st valid bit in accm */
0854     n_bits   = db->n_bits;
0855     tgtbitno = 32 - n_bits; /* bitno when we have a code */
0856
0857     /*
0858      * Save the address/control from the PPP header
0859      * and then get the sequence number.
0860      */
0861
0862     adrs  = PPP_ADDRESS (ibuf);
0863     ctrl  = PPP_CONTROL (ibuf);
0864
0865     seq   = (ibuf[4] << 8) + ibuf[5];
0866
0867     ibuf += (PPP_HDRLEN + 2);
0868     ilen  = isize - (PPP_HDRLEN + 2);
0869
0870     /*
0871      * Check the sequence number and give up if it differs from
0872      * the value we're expecting.
0873      */
0874
0875     if (seq != db->seqno)
0876       {
0877     if (db->debug)
0878       {
0879         printk("bsd_decomp%d: bad sequence # %d, expected %d\n",
0880            db->unit, seq, db->seqno - 1);
0881       }
0882     return DECOMP_ERROR;
0883       }
0884
0885     ++db->seqno;
0886     db->bytes_out += ilen;
0887
0888     /*
0889      * Fill in the ppp header, but not the last byte of the protocol
0890      * (that comes from the decompressed data).
0891      */
0892
0893     wptr    = obuf;
0894     *wptr++ = adrs;
0895     *wptr++ = ctrl;
0896     *wptr++ = 0;
0897
0898     oldcode = CLEAR;
0899     explen  = 3;
0900
0901     /*
0902      * Keep the checkpoint correctly so that incompressible packets
0903      * clear the dictionary at the proper times.
0904      */
0905
0906     for (;;)
0907       {
0908     if (ilen-- <= 0)
0909       {
0910         db->in_count += (explen - 3); /* don't count the header */
0911         break;
0912       }
0913
0914     /*
0915      * Accumulate bytes until we have a complete code.
0916      * Then get the next code, relying on the 32-bit,
0917      * unsigned accm to mask the result.
0918      */
0919
0920     bitno -= 8;
0921     accm  |= *ibuf++ << bitno;
0922     if (tgtbitno < bitno)
0923       {
0924         continue;
0925       }
0926
0927     incode = accm >> tgtbitno;
0928     accm <<= n_bits;
0929     bitno += n_bits;
0930
0931     /*
0932      * The dictionary must only be cleared at the end of a packet.
0933      */
0934
0935     if (incode == CLEAR)
0936       {
0937         if (ilen > 0)
0938           {
0939         if (db->debug)
0940           {
0941             printk("bsd_decomp%d: bad CLEAR\n", db->unit);
0942           }
0943         return DECOMP_FATALERROR;   /* probably a bug */
0944           }
0945
0946         bsd_clear(db);
0947         break;
0948       }
0949
0950     if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
0951         || (incode > max_ent && oldcode == CLEAR))
0952       {
0953         if (db->debug)
0954           {
0955         printk("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
0956                db->unit, incode, oldcode);
0957         printk("max_ent=0x%x explen=%d seqno=%d\n",
0958                max_ent, explen, db->seqno);
0959           }
0960         return DECOMP_FATALERROR;   /* probably a bug */
0961       }
0962
0963     /* Special case for KwKwK string. */
0964     if (incode > max_ent)
0965       {
0966         finchar = oldcode;
0967         extra   = 1;
0968       }
0969     else
0970       {
0971         finchar = incode;
0972         extra   = 0;
0973       }
0974
0975     codelen = *(lens_ptr (db, finchar));
0976     explen += codelen + extra;
0977     if (explen > osize)
0978       {
0979         if (db->debug)
0980           {
0981         printk("bsd_decomp%d: ran out of mru\n", db->unit);
0982 #ifdef DEBUG
0983         printk("  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
0984                ilen, finchar, codelen, explen);
0985 #endif
0986           }
0987         return DECOMP_FATALERROR;
0988       }
0989
0990     /*
0991      * Decode this code and install it in the decompressed buffer.
0992      */
0993
0994     wptr += codelen;
0995     p     = wptr;
0996     while (finchar > LAST)
0997       {
0998         struct bsd_dict *dictp2 = dict_ptr (db, finchar);
0999
1000         dictp = dict_ptr (db, dictp2->cptr);
1001 #ifdef DEBUG
1002         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         else
1011           {
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 #endif
1025         *--p    = dictp->f.hs.suffix;
1026         finchar = dictp->f.hs.prefix;
1027       }
1028     *--p = finchar;
1029
1030 #ifdef DEBUG
1031     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 #endif
1037
1038     if (extra)      /* the KwKwK case again */
1039       {
1040         *wptr++ = finchar;
1041       }
1042
1043     /*
1044      * If not first code in a packet, and
1045      * if not out of code space, then allocate a new code.
1046      *
1047      * Keep the hash table correct so it can be used
1048      * 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         do
1067           {
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 entry
1080          * assigned this code, and then take it over
1081          */
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 module
1130  *************************************************************/
1131
1132 static 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_MODULE
1148 };
1149
1150 /*************************************************************
1151  * Module support routines
1152  *************************************************************/
1153
1154 static 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
1162 static void __exit bsdcomp_cleanup(void)
1163 {
1164     ppp_unregister_compressor(&ppp_bsd_compress);
1165 }
1166
1167 module_init(bsdcomp_init);
1168 module_exit(bsdcomp_cleanup);
1169 MODULE_LICENSE("Dual BSD/GPL");
1170 MODULE_ALIAS("ppp-compress-" __stringify(CI_BSD_COMPRESS));