/* * Update: The Berkeley copyright was changed, and the change * is retroactive to all "true" BSD software (ie everything * from UCB as opposed to other peoples code that just carried * the same license). The new copyright doesn't clash with the * GPL, so the module-only restriction has been removed.. */ /* Because this code is derived from the 4.3BSD compress source: * * Copyright (c) 1985, 1986 The Regents of the University of California. * All rights reserved. * * This code is derived from software contributed to Berkeley by * James A. Woods, derived from original work by Spencer Thomas * and Joseph Orost. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software *    must display the following acknowledgement: *	This product includes software developed by the University of *	California, Berkeley and its contributors. * 4. Neither the name of the University nor the names of its contributors *    may be used to endorse or promote products derived from this software *    without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ /* * This version is for use with contiguous buffers on Linux-derived systems. * *  ==FILEVERSION 20000226== * *  NOTE TO MAINTAINERS: *     If you modify this file at all, please set the number above to the *     date of the modification as YYMMDD (year month day). *     bsd_comp.c is shipped with a PPP distribution as well as with *     the kernel; if everyone increases the FILEVERSION number above, *     then scripts can do the right thing when deciding whether to *     install a new bsd_comp.c file. Don't change the format of that *     line otherwise, so the installation script can recognize it. * * From: bsd_comp.c,v 1.3 1994/12/08 01:59:58 paulus Exp */ #include <linux/module.h>#include <linux/init.h>#include <linux/slab.h>#include <linux/vmalloc.h>#include <linux/string.h> #include <linux/ppp_defs.h> #undef   PACKETPTR#define  PACKETPTR 1#include <linux/ppp-comp.h>#undef   PACKETPTR #include <asm/byteorder.h> /* * PPP "BSD compress" compression *  The differences between this compression and the classic BSD LZW *  source are obvious from the requirement that the classic code worked *  with files while this handles arbitrarily long streams that *  are broken into packets.  They are: * *	When the code size expands, a block of junk is not emitted by *	    the compressor and not expected by the decompressor. * *	New codes are not necessarily assigned every time an old *	    code is output by the compressor.  This is because a packet *	    end forces a code to be emitted, but does not imply that a *	    new sequence has been seen. * *	The compression ratio is checked at the first end of a packet *	    after the appropriate gap.	Besides simplifying and speeding *	    things up, this makes it more likely that the transmitter *	    and receiver will agree when the dictionary is cleared when *	    compression is not going well. */ /* * Macros to extract protocol version and number of bits * from the third byte of the BSD Compress CCP configuration option. */ #define BSD_VERSION(x)	((x) >> 5)#define BSD_NBITS(x)	((x) & 0x1F) #define BSD_CURRENT_VERSION	1 /* * A dictionary for doing BSD compress. */ struct bsd_dict {    union {				/* hash value */	unsigned long	fcode;	struct {#if defined(__LITTLE_ENDIAN)		/* Little endian order */	    unsigned short	prefix;	/* preceding code */	    unsigned char	suffix; /* last character of new code */	    unsigned char	pad;#elif defined(__BIG_ENDIAN)		/* Big endian order */	    unsigned char	pad;	    unsigned char	suffix; /* last character of new code */	    unsigned short	prefix; /* preceding code */#else#error Endianness not defined...#endif	} hs;    } f;    unsigned short codem1;		/* output of hash table -1 */    unsigned short cptr;		/* map code to hash table entry */}; struct bsd_db {    int	    totlen;			/* length of this structure */    unsigned int   hsize;		/* size of the hash table */    unsigned char  hshift;		/* used in hash function */    unsigned char  n_bits;		/* current bits/code */    unsigned char  maxbits;		/* maximum bits/code */    unsigned char  debug;		/* non-zero if debug desired */    unsigned char  unit;		/* ppp unit number */    unsigned short seqno;		/* sequence # of next packet */    unsigned int   mru;			/* size of receive (decompress) bufr */    unsigned int   maxmaxcode;		/* largest valid code */    unsigned int   max_ent;		/* largest code in use */    unsigned int   in_count;		/* uncompressed bytes, aged */    unsigned int   bytes_out;		/* compressed bytes, aged */    unsigned int   ratio;		/* recent compression ratio */    unsigned int   checkpoint;		/* when to next check the ratio */    unsigned int   clear_count;		/* times dictionary cleared */    unsigned int   incomp_count;	/* incompressible packets */    unsigned int   incomp_bytes;	/* incompressible bytes */    unsigned int   uncomp_count;	/* uncompressed packets */    unsigned int   uncomp_bytes;	/* uncompressed bytes */    unsigned int   comp_count;		/* compressed packets */    unsigned int   comp_bytes;		/* compressed bytes */    unsigned short  *lens;		/* array of lengths of codes */    struct bsd_dict *dict;		/* dictionary */}; #define BSD_OVHD	2		/* BSD compress overhead/packet */#define MIN_BSD_BITS	9#define BSD_INIT_BITS	MIN_BSD_BITS#define MAX_BSD_BITS	15 static void	bsd_free (void *state);static void	*bsd_alloc(unsigned char *options, int opt_len, int decomp);static void	*bsd_comp_alloc (unsigned char *options, int opt_len);static void	*bsd_decomp_alloc (unsigned char *options, int opt_len); static int	bsd_init        (void *db, unsigned char *options,			         int opt_len, int unit, int debug, int decomp);static int	bsd_comp_init   (void *state, unsigned char *options,			         int opt_len, int unit, int opthdr, int debug);static int	bsd_decomp_init (void *state, unsigned char *options,				 int opt_len, int unit, int opthdr, int mru,				 int debug); static void	bsd_reset (void *state);static void	bsd_comp_stats (void *state, struct compstat *stats); static int	bsd_compress (void *state, unsigned char *rptr,			      unsigned char *obuf, int isize, int osize);static void	bsd_incomp (void *state, unsigned char *ibuf, int icnt); static int	bsd_decompress (void *state, unsigned char *ibuf, int isize,				unsigned char *obuf, int osize); /* These are in ppp_generic.c */extern int  ppp_register_compressor   (struct compressor *cp);extern void ppp_unregister_compressor (struct compressor *cp); /* * the next two codes should not be changed lightly, as they must not * lie within the contiguous general code space. */#define CLEAR	256			/* table clear output code */#define FIRST	257			/* first free entry */#define LAST	255 #define MAXCODE(b)	((1 << (b)) - 1)#define BADCODEM1	MAXCODE(MAX_BSD_BITS); #define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) \					 ^ (unsigned long)(prefix))#define BSD_KEY(prefix,suffix)		((((unsigned long)(suffix)) << 16) \					 + (unsigned long)(prefix)) #define CHECK_GAP	10000		/* Ratio check interval */ #define RATIO_SCALE_LOG	8#define RATIO_SCALE	(1<<RATIO_SCALE_LOG)#define RATIO_MAX	(0x7fffffff>>RATIO_SCALE_LOG) /* * clear the dictionary */ static voidbsd_clear(struct bsd_db *db){    db->clear_count++;    db->max_ent      = FIRST-1;    db->n_bits       = BSD_INIT_BITS;    db->bytes_out    = 0;    db->in_count     = 0;    db->ratio	     = 0;    db->checkpoint   = CHECK_GAP;} /* * If the dictionary is full, then see if it is time to reset it. * * Compute the compression ratio using fixed-point arithmetic * with 8 fractional bits. * * Since we have an infinite stream instead of a single file, * watch only the local compression ratio. * * Since both peers must reset the dictionary at the same time even in * the absence of CLEAR codes (while packets are incompressible), they * must compute the same ratio. */ static int bsd_check (struct bsd_db *db)	/* 1=output CLEAR */  {    unsigned int new_ratio;     if (db->in_count >= db->checkpoint)      {	/* age the ratio by limiting the size of the counts */	if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)	  {	    db->in_count  -= (db->in_count  >> 2);	    db->bytes_out -= (db->bytes_out >> 2);	  } 	db->checkpoint = db->in_count + CHECK_GAP; 	if (db->max_ent >= db->maxmaxcode)	  {	    /* Reset the dictionary only if the ratio is worse,	     * or if it looks as if it has been poisoned	     * by incompressible data.	     *	     * This does not overflow, because	     *	db->in_count <= RATIO_MAX.	     */ 	    new_ratio = db->in_count << RATIO_SCALE_LOG;	    if (db->bytes_out != 0)	      {		new_ratio /= db->bytes_out;	      } 	    if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)	      {		bsd_clear (db);		return 1;	      }	    db->ratio = new_ratio;	  }      }    return 0;  } /* * Return statistics. */ static void bsd_comp_stats (void *state, struct compstat *stats)  {    struct bsd_db *db = (struct bsd_db *) state;     stats->unc_bytes    = db->uncomp_bytes;    stats->unc_packets  = db->uncomp_count;    stats->comp_bytes   = db->comp_bytes;    stats->comp_packets = db->comp_count;    stats->inc_bytes    = db->incomp_bytes;    stats->inc_packets  = db->incomp_count;    stats->in_count     = db->in_count;    stats->bytes_out    = db->bytes_out;  } /* * Reset state, as on a CCP ResetReq. */ static void bsd_reset (void *state)  {    struct bsd_db *db = (struct bsd_db *) state;     bsd_clear(db);     db->seqno       = 0;    db->clear_count = 0;  } /* * Release the compression structure */ static void bsd_free (void *state){	struct bsd_db *db = state; 	if (!db)		return; /* * Release the dictionary */	vfree(db->dict);	db->dict = NULL;/* * Release the string buffer */	vfree(db->lens);	db->lens = NULL;/* * Finally release the structure itself. */	kfree(db);} /* * Allocate space for a (de) compressor. */ static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)  {    int bits;    unsigned int hsize, hshift, maxmaxcode;    struct bsd_db *db;     if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3	|| BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)      {	return NULL;      }     bits = BSD_NBITS(options[2]);     switch (bits)      {    case 9:			/* needs 82152 for both directions */    case 10:			/* needs 84144 */    case 11:			/* needs 88240 */    case 12:			/* needs 96432 */	hsize = 5003;	hshift = 4;	break;    case 13:			/* needs 176784 */	hsize = 9001;	hshift = 5;	break;    case 14:			/* needs 353744 */	hsize = 18013;	hshift = 6;	break;    case 15:			/* needs 691440 */	hsize = 35023;	hshift = 7;	break;    case 16:			/* needs 1366160--far too much, */	/* hsize = 69001; */	/* and 69001 is too big for cptr */	/* hshift = 8; */	/* in struct bsd_db */	/* break; */    default:	return NULL;      }/* * Allocate the main control structure for this instance. */    maxmaxcode = MAXCODE(bits);    db         = kmalloc(sizeof (struct bsd_db),					    GFP_KERNEL);    if (!db)      {	return NULL;      }     memset (db, 0, sizeof(struct bsd_db));/* * Allocate space for the dictionary. This may be more than one page in * length. */    db->dict = (struct bsd_dict *) vmalloc (hsize *					    sizeof (struct bsd_dict));    if (!db->dict)      {	bsd_free (db);	return NULL;      } /* * If this is the compression buffer then there is no length data. */    if (!decomp)      {	db->lens = NULL;      }/* * For decompression, the length information is needed as well. */    else      {        db->lens = (unsigned short *) vmalloc ((maxmaxcode + 1) *					       sizeof (db->lens[0]));	if (!db->lens)	  {	    bsd_free (db);	    return (NULL);	  }      }/* * Initialize the data information for the compression code */    db->totlen     = sizeof (struct bsd_db)   +      		    (sizeof (struct bsd_dict) * hsize);     db->hsize      = hsize;    db->hshift     = hshift;    db->maxmaxcode = maxmaxcode;    db->maxbits    = bits;     return (void *) db;  } static void *bsd_comp_alloc (unsigned char *options, int opt_len)  {    return bsd_alloc (options, opt_len, 0);  } static void *bsd_decomp_alloc (unsigned char *options, int opt_len)  {    return bsd_alloc (options, opt_len, 1);  } /* * Initialize the database. */ static int bsd_init (void *state, unsigned char *options,		     int opt_len, int unit, int debug, int decomp)  {    struct bsd_db *db = state;    int indx;     if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)	|| (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)	|| (BSD_NBITS(options[2]) != db->maxbits)	|| (decomp && db->lens == NULL))      {	return 0;      }     if (decomp)      {	indx = LAST;	do	  {	    db->lens[indx] = 1;	  }	while (indx-- > 0);      }     indx = db->hsize;    while (indx-- != 0)      {	db->dict[indx].codem1 = BADCODEM1;	db->dict[indx].cptr   = 0;      }     db->unit = unit;    db->mru  = 0;#ifndef DEBUG    if (debug)

Lines 1–500 of 1173. Load more