path: root/drivers/net/ppp/bsd_comp.c

/*
 * 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;