Initial revision

5 files changed, 2540 insertions, 0 deletions

diff --git a/sys/net/bsd_comp.c b/sys/net/bsd_comp.c
new file mode 100644
index 0000000..40da4e5
--- /dev/null
+++ b/sys/net/bsd_comp.c
@@ -0,0 +1,1114 @@
+/* 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 mbufs on BSD-derived systems.
+ *
+ * $Id: bsd-comp.c,v 1.11 1995/07/04 03:35:11 paulus Exp $
+ */
+
+#include <sys/param.h>
+#include <sys/types.h>
+#include <sys/mbuf.h>
+#include <sys/socket.h>
+#include <net/if.h>
+#include <net/if_types.h>
+#include <net/ppp_defs.h>
+#include <net/if_ppp.h>
+
+#define PACKETPTR	struct mbuf *
+#include <net/ppp-comp.h>
+
+#if DO_BSD_COMPRESS
+/*
+ * 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.
+ */
+
+/*
+ * A dictionary for doing BSD compress.
+ */
+struct bsd_db {
+    int	    totlen;			/* length of this structure */
+    u_int   hsize;			/* size of the hash table */
+    u_char  hshift;			/* used in hash function */
+    u_char  n_bits;			/* current bits/code */
+    u_char  maxbits;
+    u_char  debug;
+    u_char  unit;
+    u_int16_t seqno;			/* sequence # of next packet */
+    u_int   hdrlen;			/* header length to preallocate */
+    u_int   mru;
+    u_int   maxmaxcode;			/* largest valid code */
+    u_int   max_ent;			/* largest code in use */
+    u_int   in_count;			/* uncompressed bytes, aged */
+    u_int   bytes_out;			/* compressed bytes, aged */
+    u_int   ratio;			/* recent compression ratio */
+    u_int   checkpoint;			/* when to next check the ratio */
+    u_int   clear_count;		/* times dictionary cleared */
+    u_int   incomp_count;		/* incompressible packets */
+    u_int   incomp_bytes;		/* incompressible bytes */
+    u_int   uncomp_count;		/* uncompressed packets */
+    u_int   uncomp_bytes;		/* uncompressed bytes */
+    u_int   comp_count;			/* compressed packets */
+    u_int   comp_bytes;			/* compressed bytes */
+    u_int16_t *lens;			/* array of lengths of codes */
+    struct bsd_dict {
+	union {				/* hash value */
+	    u_int32_t	fcode;
+	    struct {
+#if BYTE_ORDER == LITTLE_ENDIAN
+		u_int16_t prefix;	/* preceding code */
+		u_char	suffix;		/* last character of new code */
+		u_char	pad;
+#else
+		u_char	pad;
+		u_char	suffix;		/* last character of new code */
+		u_int16_t prefix;	/* preceding code */
+#endif
+	    } hs;
+	} f;
+	u_int16_t codem1;		/* output of hash table -1 */
+	u_int16_t cptr;			/* map code to hash table entry */
+    } dict[1];
+};
+
+#define BSD_OVHD	2		/* BSD compress overhead/packet */
+#define BSD_INIT_BITS	BSD_MIN_BITS
+
+static void	*bsd_comp_alloc __P((u_char *options, int opt_len));
+static void	*bsd_decomp_alloc __P((u_char *options, int opt_len));
+static void	bsd_free __P((void *state));
+static int	bsd_comp_init __P((void *state, u_char *options, int opt_len,
+				   int unit, int hdrlen, int debug));
+static int	bsd_decomp_init __P((void *state, u_char *options, int opt_len,
+				     int unit, int hdrlen, int mru, int debug));
+static int	bsd_compress __P((void *state, struct mbuf **mret,
+				  struct mbuf *mp, int slen, int maxolen));
+static void	bsd_incomp __P((void *state, struct mbuf *dmsg));
+static int	bsd_decompress __P((void *state, struct mbuf *cmp,
+				    struct mbuf **dmpp));
+static void	bsd_reset __P((void *state));
+static void	bsd_comp_stats __P((void *state, struct compstat *stats));
+
+/*
+ * Procedures exported to if_ppp.c.
+ */
+struct compressor ppp_bsd_compress = {
+    CI_BSD_COMPRESS,		/* compress_proto */
+    bsd_comp_alloc,		/* comp_alloc */
+    bsd_free,			/* comp_free */
+    bsd_comp_init,		/* comp_init */
+    bsd_reset,			/* comp_reset */
+    bsd_compress,		/* compress */
+    bsd_comp_stats,		/* comp_stat */
+    bsd_decomp_alloc,		/* decomp_alloc */
+    bsd_free,			/* decomp_free */
+    bsd_decomp_init,		/* decomp_init */
+    bsd_reset,			/* decomp_reset */
+    bsd_decompress,		/* decompress */
+    bsd_incomp,			/* incomp */
+    bsd_comp_stats,		/* decomp_stat */
+};
+
+/*
+ * 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(BSD_MAX_BITS)
+
+#define BSD_HASH(prefix,suffix,hshift)	((((u_int32_t)(suffix)) << (hshift)) \
+					 ^ (u_int32_t)(prefix))
+#define BSD_KEY(prefix,suffix)		((((u_int32_t)(suffix)) << 16) \
+					 + (u_int32_t)(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 void
+bsd_clear(db)
+    struct bsd_db *db;
+{
+    db->clear_count++;
+    db->max_ent = FIRST-1;
+    db->n_bits = BSD_INIT_BITS;
+    db->ratio = 0;
+    db->bytes_out = 0;
+    db->in_count = 0;
+    db->incomp_count = 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				/* 1=output CLEAR */
+bsd_check(db)
+    struct bsd_db *db;
+{
+    u_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/4;
+	    db->bytes_out -= db->bytes_out/4;
+	}
+
+	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(state, stats)
+    void *state;
+    struct compstat *stats;
+{
+    struct bsd_db *db = (struct bsd_db *) state;
+    u_int out;
+
+    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->ratio = db->in_count;
+    out = db->bytes_out;
+    if (stats->ratio <= 0x7fffff)
+	stats->ratio <<= 8;
+    else
+	out >>= 8;
+    if (out != 0)
+	stats->ratio /= out;
+}
+
+/*
+ * Reset state, as on a CCP ResetReq.
+ */
+static void
+bsd_reset(state)
+    void *state;
+{
+    struct bsd_db *db = (struct bsd_db *) state;
+
+    db->seqno = 0;
+    bsd_clear(db);
+    db->clear_count = 0;
+}
+
+/*
+ * Allocate space for a (de) compressor.
+ */
+static void *
+bsd_alloc(options, opt_len, decomp)
+    u_char *options;
+    int opt_len, decomp;
+{
+    int bits;
+    u_int newlen, hsize, hshift, maxmaxcode;
+    struct bsd_db *db;
+
+    if (opt_len != CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
+	|| options[1] != CILEN_BSD_COMPRESS
+	|| 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;
+    }
+
+    maxmaxcode = MAXCODE(bits);
+    newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0]));
+    MALLOC(db, struct bsd_db *, newlen, M_DEVBUF, M_NOWAIT);
+    if (!db)
+	return NULL;
+    bzero(db, sizeof(*db) - sizeof(db->dict));
+
+    if (!decomp) {
+	db->lens = NULL;
+    } else {
+	MALLOC(db->lens, u_int16_t *, (maxmaxcode+1) * sizeof(db->lens[0]),
+	       M_DEVBUF, M_NOWAIT);
+	if (!db->lens) {
+	    FREE(db, M_DEVBUF);
+	    return NULL;
+	}
+    }
+
+    db->totlen = newlen;
+    db->hsize = hsize;
+    db->hshift = hshift;
+    db->maxmaxcode = maxmaxcode;
+    db->maxbits = bits;
+
+    return (void *) db;
+}
+
+static void
+bsd_free(state)
+    void *state;
+{
+    struct bsd_db *db = (struct bsd_db *) state;
+
+    if (db->lens)
+	FREE(db->lens, M_DEVBUF);
+    FREE(db, M_DEVBUF);
+}
+
+static void *
+bsd_comp_alloc(options, opt_len)
+    u_char *options;
+    int opt_len;
+{
+    return bsd_alloc(options, opt_len, 0);
+}
+
+static void *
+bsd_decomp_alloc(options, opt_len)
+    u_char *options;
+    int opt_len;
+{
+    return bsd_alloc(options, opt_len, 1);
+}
+
+/*
+ * Initialize the database.
+ */
+static int
+bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp)
+    struct bsd_db *db;
+    u_char *options;
+    int opt_len, unit, hdrlen, mru, debug, decomp;
+{
+    int i;
+
+    if (opt_len != CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
+	|| options[1] != CILEN_BSD_COMPRESS
+	|| BSD_VERSION(options[2]) != BSD_CURRENT_VERSION
+	|| BSD_NBITS(options[2]) != db->maxbits
+	|| decomp && db->lens == NULL)
+	return 0;
+
+    if (decomp) {
+	i = LAST+1;
+	while (i != 0)
+	    db->lens[--i] = 1;
+    }
+    i = db->hsize;
+    while (i != 0) {
+	db->dict[--i].codem1 = BADCODEM1;
+	db->dict[i].cptr = 0;
+    }
+
+    db->unit = unit;
+    db->hdrlen = hdrlen;
+    db->mru = mru;
+#ifndef DEBUG
+    if (debug)
+#endif
+	db->debug = 1;
+
+    bsd_reset(db);
+
+    return 1;
+}
+
+static int
+bsd_comp_init(state, options, opt_len, unit, hdrlen, debug)
+    void *state;
+    u_char *options;
+    int opt_len, unit, hdrlen, debug;
+{
+    return bsd_init((struct bsd_db *) state, options, opt_len,
+		    unit, hdrlen, 0, debug, 0);
+}
+
+static int
+bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug)
+    void *state;
+    u_char *options;
+    int opt_len, unit, hdrlen, mru, debug;
+{
+    return bsd_init((struct bsd_db *) state, options, opt_len,
+		    unit, hdrlen, mru, debug, 1);
+}
+
+
+/*
+ * compress a packet
+ *	One change from the BSD compress command is that when the
+ *	code size expands, we do not output a bunch of padding.
+ */
+int					/* new slen */
+bsd_compress(state, mret, mp, slen, maxolen)
+    void *state;
+    struct mbuf **mret;		/* return compressed mbuf chain here */
+    struct mbuf *mp;		/* from here */
+    int slen;			/* uncompressed length */
+    int maxolen;		/* max compressed length */
+{
+    struct bsd_db *db = (struct bsd_db *) state;
+    int hshift = db->hshift;
+    u_int max_ent = db->max_ent;
+    u_int n_bits = db->n_bits;
+    u_int bitno = 32;
+    u_int32_t accm = 0, fcode;
+    struct bsd_dict *dictp;
+    u_char c;
+    int hval, disp, ent, ilen;
+    struct mbuf *np;
+    u_char *rptr, *wptr;
+    u_char *cp_end;
+    int olen;
+    struct mbuf *m, **mnp;
+
+#define PUTBYTE(v) {					\
+    ++olen;						\
+    if (wptr) {						\
+	*wptr++ = (v);					\
+	if (wptr >= cp_end) {				\
+	    m->m_len = wptr - mtod(m, u_char *);	\
+	    MGET(m->m_next, M_DONTWAIT, MT_DATA);	\
+	    m = m->m_next;				\
+	    if (m) {					\
+		m->m_len = 0;				\
+		if (maxolen - olen > MLEN)		\
+		    MCLGET(m, M_DONTWAIT);		\
+		wptr = mtod(m, u_char *);		\
+		cp_end = wptr + M_TRAILINGSPACE(m);	\
+	    } else					\
+		wptr = NULL;				\
+	}						\
+    }							\
+}
+
+#define OUTPUT(ent) {					\
+    bitno -= n_bits;					\
+    accm |= ((ent) << bitno);				\
+    do {						\
+	PUTBYTE(accm >> 24);				\
+	accm <<= 8;					\
+	bitno += 8;					\
+    } while (bitno <= 24);				\
+}
+
+    /*
+     * If the protocol is not in the range we're interested in,
+     * just return without compressing the packet.  If it is,
+     * the protocol becomes the first byte to compress.
+     */
+    rptr = mtod(mp, u_char *);
+    ent = PPP_PROTOCOL(rptr);
+    if (ent < 0x21 || ent > 0xf9) {
+	*mret = NULL;
+	return slen;
+    }
+
+    /* Don't generate compressed packets which are larger than
+       the uncompressed packet. */
+    if (maxolen > slen)
+	maxolen = slen;
+
+    /* Allocate one mbuf to start with. */
+    MGET(m, M_DONTWAIT, MT_DATA);
+    *mret = m;
+    if (m != NULL) {
+	m->m_len = 0;
+	if (maxolen + db->hdrlen > MLEN)
+	    MCLGET(m, M_DONTWAIT);
+	m->m_data += db->hdrlen;
+	wptr = mtod(m, u_char *);
+	cp_end = wptr + M_TRAILINGSPACE(m);
+    } else
+	wptr = cp_end = NULL;
+
+    /*
+     * Copy the PPP header over, changing the protocol,
+     * and install the 2-byte packet sequence number.
+     */
+    if (wptr) {
+	*wptr++ = PPP_ADDRESS(rptr);	/* assumes the ppp header is */
+	*wptr++ = PPP_CONTROL(rptr);	/* all in one mbuf */
+	*wptr++ = 0;			/* change the protocol */
+	*wptr++ = PPP_COMP;
+	*wptr++ = db->seqno >> 8;
+	*wptr++ = db->seqno;
+    }
+    ++db->seqno;
+
+    olen = 0;
+    rptr += PPP_HDRLEN;
+    slen = mp->m_len - PPP_HDRLEN;
+    ilen = slen + 1;
+    for (;;) {
+	if (slen <= 0) {
+	    mp = mp->m_next;
+	    if (!mp)
+		break;
+	    rptr = mtod(mp, u_char *);
+	    slen = mp->m_len;
+	    if (!slen)
+		continue;   /* handle 0-length buffers */
+	    ilen += slen;
+	}
+
+	slen--;
+	c = *rptr++;
+	fcode = BSD_KEY(ent, c);
+	hval = BSD_HASH(ent, c, hshift);
+	dictp = &db->dict[hval];
+
+	/* Validate and then check the entry. */
+	if (dictp->codem1 >= max_ent)
+	    goto nomatch;
+	if (dictp->f.fcode == fcode) {
+	    ent = dictp->codem1+1;
+	    continue;	/* found (prefix,suffix) */
+	}
+
+	/* continue probing until a match or invalid entry */
+	disp = (hval == 0) ? 1 : hval;
+	do {
+	    hval += disp;
+	    if (hval >= db->hsize)
+		hval -= db->hsize;
+	    dictp = &db->dict[hval];
+	    if (dictp->codem1 >= max_ent)
+		goto nomatch;
+	} while (dictp->f.fcode != fcode);
+	ent = dictp->codem1 + 1;	/* finally found (prefix,suffix) */
+	continue;
+
+    nomatch:
+	OUTPUT(ent);		/* output the prefix */
+
+	/* code -> hashtable */
+	if (max_ent < db->maxmaxcode) {
+	    struct bsd_dict *dictp2;
+	    /* expand code size if needed */
+	    if (max_ent >= MAXCODE(n_bits))
+		db->n_bits = ++n_bits;
+
+	    /* Invalidate old hash table entry using
+	     * this code, and then take it over.
+	     */
+	    dictp2 = &db->dict[max_ent+1];
+	    if (db->dict[dictp2->cptr].codem1 == max_ent)
+		db->dict[dictp2->cptr].codem1 = BADCODEM1;
+	    dictp2->cptr = hval;
+	    dictp->codem1 = max_ent;
+	    dictp->f.fcode = fcode;
+
+	    db->max_ent = ++max_ent;
+	}
+	ent = c;
+    }
+
+    OUTPUT(ent);		/* output the last code */
+    db->bytes_out += olen;
+    db->in_count += ilen;
+    if (bitno < 32)
+	++db->bytes_out;	/* count complete bytes */
+
+    if (bsd_check(db))
+	OUTPUT(CLEAR);		/* do not count the CLEAR */
+
+    /*
+     * Pad dribble bits of last code with ones.
+     * Do not emit a completely useless byte of ones.
+     */
+    if (bitno != 32)
+	PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
+
+    if (m != NULL) {
+	m->m_len = wptr - mtod(m, u_char *);
+	m->m_next = NULL;
+    }
+
+    /*
+     * Increase code size if we would have without the packet
+     * boundary and as the decompressor will.
+     */
+    if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
+	db->n_bits++;
+
+    db->uncomp_bytes += ilen;
+    ++db->uncomp_count;
+    if (olen + PPP_HDRLEN + BSD_OVHD > maxolen) {
+	/* throw away the compressed stuff if it is longer than uncompressed */
+	if (*mret != NULL) {
+	    m_freem(*mret);
+	    *mret = NULL;
+	}
+	++db->incomp_count;
+	db->incomp_bytes += ilen;
+    } else {
+	++db->comp_count;
+	db->comp_bytes += olen + BSD_OVHD;
+    }
+
+    return olen + PPP_HDRLEN + BSD_OVHD;
+#undef OUTPUT
+#undef PUTBYTE
+}
+
+
+/*
+ * Update the "BSD Compress" dictionary on the receiver for
+ * incompressible data by pretending to compress the incoming data.
+ */
+static void
+bsd_incomp(state, dmsg)
+    void *state;
+    struct mbuf *dmsg;
+{
+    struct bsd_db *db = (struct bsd_db *) state;
+    u_int hshift = db->hshift;
+    u_int max_ent = db->max_ent;
+    u_int n_bits = db->n_bits;
+    struct bsd_dict *dictp;
+    u_int32_t fcode;
+    u_char c;
+    u_int32_t hval, disp;
+    int slen, ilen;
+    u_int bitno = 7;
+    u_char *rptr;
+    u_int ent;
+
+    /*
+     * If the protocol is not in the range we're interested in,
+     * just return without looking at the packet.  If it is,
+     * the protocol becomes the first byte to "compress".
+     */
+    rptr = mtod(dmsg, u_char *);
+    ent = PPP_PROTOCOL(rptr);
+    if (ent < 0x21 || ent > 0xf9)
+	return;
+
+    db->incomp_count++;
+    db->seqno++;
+    ilen = 1;		/* count the protocol as 1 byte */
+    rptr += PPP_HDRLEN;
+    slen = dmsg->m_len - PPP_HDRLEN;
+    for (;;) {
+	if (slen <= 0) {
+	    dmsg = dmsg->m_next;
+	    if (!dmsg)
+		break;
+	    rptr = mtod(dmsg, u_char *);
+	    slen = dmsg->m_len;
+	    continue;
+	}
+	ilen += slen;
+
+	do {
+	    c = *rptr++;
+	    fcode = BSD_KEY(ent, c);
+	    hval = BSD_HASH(ent, c, hshift);
+	    dictp = &db->dict[hval];
+
+	    /* validate and then check the entry */
+	    if (dictp->codem1 >= max_ent)
+		goto nomatch;
+	    if (dictp->f.fcode == fcode) {
+		ent = dictp->codem1+1;
+		continue;   /* found (prefix,suffix) */
+	    }
+
+	    /* continue probing until a match or invalid entry */
+	    disp = (hval == 0) ? 1 : hval;
+	    do {
+		hval += disp;
+		if (hval >= db->hsize)
+		    hval -= db->hsize;
+		dictp = &db->dict[hval];
+		if (dictp->codem1 >= max_ent)
+		    goto nomatch;
+	    } while (dictp->f.fcode != fcode);
+	    ent = dictp->codem1+1;
+	    continue;	/* finally found (prefix,suffix) */
+
+	nomatch:		/* output (count) the prefix */
+	    bitno += n_bits;
+
+	    /* code -> hashtable */
+	    if (max_ent < db->maxmaxcode) {
+		struct bsd_dict *dictp2;
+		/* expand code size if needed */
+		if (max_ent >= MAXCODE(n_bits))
+		    db->n_bits = ++n_bits;
+
+		/* Invalidate previous hash table entry
+		 * assigned this code, and then take it over.
+		 */
+		dictp2 = &db->dict[max_ent+1];
+		if (db->dict[dictp2->cptr].codem1 == max_ent)
+		    db->dict[dictp2->cptr].codem1 = BADCODEM1;
+		dictp2->cptr = hval;
+		dictp->codem1 = max_ent;
+		dictp->f.fcode = fcode;
+
+		db->max_ent = ++max_ent;
+		db->lens[max_ent] = db->lens[ent]+1;
+	    }
+	    ent = c;
+	} while (--slen != 0);
+    }
+    bitno += n_bits;		/* output (count) the last code */
+    db->bytes_out += bitno/8;
+    db->in_count += ilen;
+    (void)bsd_check(db);
+
+    ++db->incomp_count;
+    db->incomp_bytes += ilen;
+    ++db->uncomp_count;
+    db->uncomp_bytes += ilen;
+
+    /* Increase code size if we would have without the packet
+     * boundary and as the decompressor will.
+     */
+    if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
+	db->n_bits++;
+}
+
+
+/*
+ * Decompress "BSD Compress".
+ *
+ * Because of patent problems, we return DECOMP_ERROR for errors
+ * found by inspecting the input data and for system problems, but
+ * DECOMP_FATALERROR for any errors which could possibly be said to
+ * be being detected "after" decompression.  For DECOMP_ERROR,
+ * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
+ * infringing a patent of Motorola's if we do, so we take CCP down
+ * instead.
+ *
+ * Given that the frame has the correct sequence number and a good FCS,
+ * errors such as invalid codes in the input most likely indicate a
+ * bug, so we return DECOMP_FATALERROR for them in order to turn off
+ * compression, even though they are detected by inspecting the input.
+ */
+int
+bsd_decompress(state, cmp, dmpp)
+    void *state;
+    struct mbuf *cmp, **dmpp;
+{
+    struct bsd_db *db = (struct bsd_db *) state;
+    u_int max_ent = db->max_ent;
+    u_int32_t accm = 0;
+    u_int bitno = 32;		/* 1st valid bit in accm */
+    u_int n_bits = db->n_bits;
+    u_int tgtbitno = 32-n_bits;	/* bitno when we have a code */
+    struct bsd_dict *dictp;
+    int explen, i, seq, len;
+    u_int incode, oldcode, finchar;
+    u_char *p, *rptr, *wptr;
+    struct mbuf *m, *dmp, *mret;
+    int adrs, ctrl, ilen;
+    int space, codelen, extra;
+    struct mbuf *last;
+
+    /*
+     * Save the address/control from the PPP header
+     * and then get the sequence number.
+     */
+    *dmpp = NULL;
+    rptr = mtod(cmp, u_char *);
+    adrs = PPP_ADDRESS(rptr);
+    ctrl = PPP_CONTROL(rptr);
+    rptr += PPP_HDRLEN;
+    len = cmp->m_len - PPP_HDRLEN;
+    seq = 0;
+    for (i = 0; i < 2; ++i) {
+	while (len <= 0) {
+	    cmp = cmp->m_next;
+	    if (cmp == NULL)
+		return DECOMP_ERROR;
+	    rptr = mtod(cmp, u_char *);
+	    len = cmp->m_len;
+	}
+	seq = (seq << 8) + *rptr++;
+	--len;
+    }
+
+    /*
+     * Check the sequence number and give up if it differs from
+     * the value we're expecting.
+     */
+    if (seq != db->seqno) {
+	if (db->debug)
+	    printf("bsd_decomp%d: bad sequence # %d, expected %d\n",
+		   db->unit, seq, db->seqno - 1);
+	return DECOMP_ERROR;
+    }
+    ++db->seqno;
+
+    /*
+     * Allocate one mbuf to start with.
+     */
+    MGETHDR(dmp, M_DONTWAIT, MT_DATA);
+    if (dmp == NULL)
+	return DECOMP_ERROR;
+    mret = dmp;
+    dmp->m_len = 0;
+    dmp->m_next = NULL;
+    MCLGET(dmp, M_DONTWAIT);
+    dmp->m_data += db->hdrlen;
+    wptr = mtod(dmp, u_char *);
+    space = M_TRAILINGSPACE(dmp) - PPP_HDRLEN + 1;
+
+    /*
+     * Fill in the ppp header, but not the last byte of the protocol
+     * (that comes from the decompressed data).
+     */
+    wptr[0] = adrs;
+    wptr[1] = ctrl;
+    wptr[2] = 0;
+    wptr += PPP_HDRLEN - 1;
+
+    ilen = len;
+    oldcode = CLEAR;
+    explen = 0;
+    for (;;) {
+	if (len == 0) {
+	    cmp = cmp->m_next;
+	    if (!cmp)		/* quit at end of message */
+		break;
+	    rptr = mtod(cmp, u_char *);
+	    len = cmp->m_len;
+	    ilen += len;
+	    continue;		/* handle 0-length buffers */
+	}
+
+	/*
+	 * Accumulate bytes until we have a complete code.
+	 * Then get the next code, relying on the 32-bit,
+	 * unsigned accm to mask the result.
+	 */
+	bitno -= 8;
+	accm |= *rptr++ << bitno;
+	--len;
+	if (tgtbitno < bitno)
+	    continue;
+	incode = accm >> tgtbitno;
+	accm <<= n_bits;
+	bitno += n_bits;
+
+	if (incode == CLEAR) {
+	    /*
+	     * The dictionary must only be cleared at
+	     * the end of a packet.  But there could be an
+	     * empty mbuf at the end.
+	     */
+	    if (len > 0 || cmp->m_next != NULL) {
+		while ((cmp = cmp->m_next) != NULL)
+		    len += cmp->m_len;
+		if (len > 0) {
+		    m_freem(mret);
+		    if (db->debug)
+			printf("bsd_decomp%d: bad CLEAR\n", db->unit);
+		    return DECOMP_FATALERROR;	/* probably a bug */
+		}
+	    }
+	    bsd_clear(db);
+	    explen = ilen = 0;
+	    break;
+	}
+
+	if (incode > max_ent + 2 || incode > db->maxmaxcode
+	    || incode > max_ent && oldcode == CLEAR) {
+	    m_freem(mret);
+	    if (db->debug) {
+		printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
+		       db->unit, incode, oldcode);
+		printf("max_ent=0x%x explen=%d seqno=%d\n",
+		       max_ent, explen, db->seqno);
+	    }
+	    return DECOMP_FATALERROR;	/* probably a bug */
+	}
+
+	/* Special case for KwKwK string. */
+	if (incode > max_ent) {
+	    finchar = oldcode;
+	    extra = 1;
+	} else {
+	    finchar = incode;
+	    extra = 0;
+	}
+
+	codelen = db->lens[finchar];
+	explen += codelen + extra;
+	if (explen > db->mru + 1) {
+	    m_freem(mret);
+	    if (db->debug) {
+		printf("bsd_decomp%d: ran out of mru\n", db->unit);
+#ifdef DEBUG
+		while ((cmp = cmp->m_next) != NULL)
+		    len += cmp->m_len;
+		printf("  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
+		       len, finchar, codelen, explen);
+#endif
+	    }
+	    return DECOMP_FATALERROR;
+	}
+
+	/*
+	 * For simplicity, the decoded characters go in a single mbuf,
+	 * so we allocate a single extra cluster mbuf if necessary.
+	 */
+	if ((space -= codelen + extra) < 0) {
+	    dmp->m_len = wptr - mtod(dmp, u_char *);
+	    MGET(m, M_DONTWAIT, MT_DATA);
+	    if (m == NULL) {
+		m_freem(mret);
+		return DECOMP_ERROR;
+	    }
+	    m->m_len = 0;
+	    m->m_next = NULL;
+	    dmp->m_next = m;
+	    MCLGET(m, M_DONTWAIT);
+	    space = M_TRAILINGSPACE(m) - (codelen + extra);
+	    if (space < 0) {
+		/* now that's what I call *compression*. */
+		m_freem(mret);
+		return DECOMP_ERROR;
+	    }
+	    dmp = m;
+	    wptr = mtod(dmp, u_char *);
+	}
+
+	/*
+	 * Decode this code and install it in the decompressed buffer.
+	 */
+	p = (wptr += codelen);
+	while (finchar > LAST) {
+	    dictp = &db->dict[db->dict[finchar].cptr];
+#ifdef DEBUG
+	    if (--codelen <= 0 || dictp->codem1 != finchar-1)
+		goto bad;
+#endif
+	    *--p = dictp->f.hs.suffix;
+	    finchar = dictp->f.hs.prefix;
+	}
+	*--p = finchar;
+
+#ifdef DEBUG
+	if (--codelen != 0)
+	    printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
+		   db->unit, codelen, incode, max_ent);
+#endif
+
+	if (extra)		/* the KwKwK case again */
+	    *wptr++ = finchar;
+
+	/*
+	 * If not first code in a packet, and
+	 * if not out of code space, then allocate a new code.
+	 *
+	 * Keep the hash table correct so it can be used
+	 * with uncompressed packets.
+	 */
+	if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
+	    struct bsd_dict *dictp2;
+	    u_int32_t fcode;
+	    u_int32_t hval, disp;
+
+	    fcode = BSD_KEY(oldcode,finchar);
+	    hval = BSD_HASH(oldcode,finchar,db->hshift);
+	    dictp = &db->dict[hval];
+
+	    /* look for a free hash table entry */
+	    if (dictp->codem1 < max_ent) {
+		disp = (hval == 0) ? 1 : hval;
+		do {
+		    hval += disp;
+		    if (hval >= db->hsize)
+			hval -= db->hsize;
+		    dictp = &db->dict[hval];
+		} while (dictp->codem1 < max_ent);
+	    }
+
+	    /*
+	     * Invalidate previous hash table entry
+	     * assigned this code, and then take it over
+	     */
+	    dictp2 = &db->dict[max_ent+1];
+	    if (db->dict[dictp2->cptr].codem1 == max_ent) {
+		db->dict[dictp2->cptr].codem1 = BADCODEM1;
+	    }
+	    dictp2->cptr = hval;
+	    dictp->codem1 = max_ent;
+	    dictp->f.fcode = fcode;
+
+	    db->max_ent = ++max_ent;
+	    db->lens[max_ent] = db->lens[oldcode]+1;
+
+	    /* Expand code size if needed. */
+	    if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
+		db->n_bits = ++n_bits;
+		tgtbitno = 32-n_bits;
+	    }
+	}
+	oldcode = incode;
+    }
+    dmp->m_len = wptr - mtod(dmp, u_char *);
+
+    /*
+     * Keep the checkpoint right so that incompressible packets
+     * clear the dictionary at the right times.
+     */
+    db->bytes_out += ilen;
+    db->in_count += explen;
+    if (bsd_check(db) && db->debug) {
+	printf("bsd_decomp%d: peer should have cleared dictionary\n",
+	       db->unit);
+    }
+
+    ++db->comp_count;
+    db->comp_bytes += ilen + BSD_OVHD;
+    ++db->uncomp_count;
+    db->uncomp_bytes += explen;
+
+    *dmpp = mret;
+    return DECOMP_OK;
+
+#ifdef DEBUG
+ bad:
+    if (codelen <= 0) {
+	printf("bsd_decomp%d: fell off end of chain ", db->unit);
+	printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
+	       incode, finchar, db->dict[finchar].cptr, max_ent);
+    } else if (dictp->codem1 != finchar-1) {
+	printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",
+	       db->unit, incode, finchar);
+	printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode,
+	       db->dict[finchar].cptr, dictp->codem1);
+    }
+    m_freem(mret);
+    return DECOMP_FATALERROR;
+#endif /* DEBUG */
+}
+#endif /* DO_BSD_COMPRESS */
diff --git a/sys/net/if_pppvar.h b/sys/net/if_pppvar.h
new file mode 100644
index 0000000..196e54b
--- /dev/null
+++ b/sys/net/if_pppvar.h
@@ -0,0 +1,104 @@
+/*	$Id: if_pppvar.h,v 1.1 1994/12/15 22:28:09 paulus Exp $	*/
+/*
+ * if_pppvar.h - private structures and declarations for PPP.
+ *
+ * Copyright (c) 1994 The Australian National University.
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation is hereby granted, provided that the above copyright
+ * notice appears in all copies.  This software is provided without any
+ * warranty, express or implied. The Australian National University
+ * makes no representations about the suitability of this software for
+ * any purpose.
+ *
+ * IN NO EVENT SHALL THE AUSTRALIAN NATIONAL UNIVERSITY BE LIABLE TO ANY
+ * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
+ * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
+ * THE AUSTRALIAN NATIONAL UNIVERSITY HAVE BEEN ADVISED OF THE POSSIBILITY
+ * OF SUCH DAMAGE.
+ *
+ * THE AUSTRALIAN NATIONAL UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUSTRALIAN NATIONAL UNIVERSITY HAS NO
+ * OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS,
+ * OR MODIFICATIONS.
+ *
+ * Copyright (c) 1989 Carnegie Mellon University.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms are permitted
+ * provided that the above copyright notice and this paragraph are
+ * duplicated in all such forms and that any documentation,
+ * advertising materials, and other materials related to such
+ * distribution and use acknowledge that the software was developed
+ * by Carnegie Mellon University.  The name of the
+ * University may not be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
+ * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ */
+
+/*
+ * Supported network protocols.  These values are used for
+ * indexing sc_npmode.
+ */
+#define NP_IP	0		/* Internet Protocol */
+#define NUM_NP	1		/* Number of NPs. */
+
+/*
+ * Structure describing each ppp unit.
+ */
+struct ppp_softc {
+	struct	ifnet sc_if;		/* network-visible interface */
+	u_int	sc_flags;		/* control/status bits; see if_ppp.h */
+	void	*sc_devp;		/* pointer to device-dep structure */
+	void	(*sc_start) __P((struct ppp_softc *));	/* start output proc */
+	void	(*sc_ctlp) __P((struct ppp_softc *)); /* rcvd control pkt */
+	void	(*sc_relinq) __P((struct ppp_softc *)); /* relinquish ifunit */
+	short	sc_mru;			/* max receive unit */
+	pid_t	sc_xfer;		/* used in transferring unit */
+	struct	ifqueue sc_rawq;	/* received packets */
+	struct	ifqueue sc_inq;		/* queue of input packets for daemon */
+	struct	ifqueue sc_fastq;	/* interactive output packet q */
+	struct	mbuf *sc_togo;		/* output packet ready to go */
+	struct	mbuf *sc_npqueue;	/* output packets not to be sent yet */
+	struct	mbuf **sc_npqtail;	/* ptr to last next ptr in npqueue */
+#ifdef	VJC
+	struct	vjcompress sc_comp; 	/* vjc control buffer */
+#endif
+	u_int	sc_bytessent;		/* count of octets sent */
+	u_int	sc_bytesrcvd;		/* count of octets received */
+	caddr_t	sc_bpf;			/* hook for BPF */
+	enum	NPmode sc_npmode[NUM_NP]; /* what to do with each NP */
+	struct	compressor *sc_xcomp;	/* transmit compressor */
+	void	*sc_xc_state;		/* transmit compressor state */
+	struct	compressor *sc_rcomp;	/* receive decompressor */
+	void	*sc_rc_state;		/* receive decompressor state */
+	time_t	sc_last_sent;		/* time (secs) last NP pkt sent */
+	time_t	sc_last_recv;		/* time (secs) last NP pkt rcvd */
+	
+	/* Device-dependent part for async lines. */
+	ext_accm sc_asyncmap;		/* async control character map */
+	u_long	sc_rasyncmap;		/* receive async control char map */
+	struct	mbuf *sc_outm;		/* mbuf chain currently being output */
+	struct	mbuf *sc_m;		/* pointer to input mbuf chain */
+	struct	mbuf *sc_mc;		/* pointer to current input mbuf */
+	char	*sc_mp;			/* ptr to next char in input mbuf */
+	short	sc_ilen;		/* length of input packet so far */
+	u_short	sc_fcs;			/* FCS so far (input) */
+	u_short	sc_outfcs;		/* FCS so far for output packet */
+	u_char	sc_rawin[16];		/* chars as received */
+	int	sc_rawin_count;		/* # in sc_rawin */
+};
+
+struct	ppp_softc ppp_softc[NPPP];
+
+struct	ppp_softc *pppalloc __P((pid_t pid));
+void	pppdealloc __P((struct ppp_softc *sc));
+int	pppioctl __P((struct ppp_softc *sc, int cmd, caddr_t data,
+		      int flag, struct proc *p));
+void	ppppktin __P((struct ppp_softc *sc, struct mbuf *m, int lost));
+struct	mbuf *ppp_dequeue __P((struct ppp_softc *sc));
diff --git a/sys/net/ppp_comp.h b/sys/net/ppp_comp.h
new file mode 100644
index 0000000..e2579f8
--- /dev/null
+++ b/sys/net/ppp_comp.h
@@ -0,0 +1,136 @@
+/*
+ * ppp-comp.h - Definitions for doing PPP packet compression.
+ *
+ * Copyright (c) 1994 The Australian National University.
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation is hereby granted, provided that the above copyright
+ * notice appears in all copies.  This software is provided without any
+ * warranty, express or implied. The Australian National University
+ * makes no representations about the suitability of this software for
+ * any purpose.
+ *
+ * IN NO EVENT SHALL THE AUSTRALIAN NATIONAL UNIVERSITY BE LIABLE TO ANY
+ * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
+ * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
+ * THE AUSTRALIAN NATIONAL UNIVERSITY HAVE BEEN ADVISED OF THE POSSIBILITY
+ * OF SUCH DAMAGE.
+ *
+ * THE AUSTRALIAN NATIONAL UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUSTRALIAN NATIONAL UNIVERSITY HAS NO
+ * OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS,
+ * OR MODIFICATIONS.
+ *
+ * $Id: ppp-comp.h,v 1.7 1995/05/01 01:43:37 paulus Exp $
+ */
+
+#ifndef _NET_PPP_COMP_H
+#define _NET_PPP_COMP_H
+
+/*
+ * The following symbols control whether we include code for
+ * various compression methods.
+ */
+#ifndef DO_BSD_COMPRESS
+#define DO_BSD_COMPRESS	1	/* by default, include BSD-Compress */
+#endif
+
+/*
+ * Structure giving methods for compression/decompression.
+ */
+#ifdef PACKETPTR
+struct compressor {
+	int	compress_proto;	/* CCP compression protocol number */
+
+	/* Allocate space for a compressor (transmit side) */
+	void	*(*comp_alloc) __P((u_char *options, int opt_len));
+	/* Free space used by a compressor */
+	void	(*comp_free) __P((void *state));
+	/* Initialize a compressor */
+	int	(*comp_init) __P((void *state, u_char *options, int opt_len,
+				  int unit, int hdrlen, int debug));
+	/* Reset a compressor */
+	void	(*comp_reset) __P((void *state));
+	/* Compress a packet */
+	int	(*compress) __P((void *state, PACKETPTR *mret,
+				 PACKETPTR mp, int orig_len, int max_len));
+	/* Return compression statistics */
+	void	(*comp_stat) __P((void *state, struct compstat *stats));
+
+	/* Allocate space for a decompressor (receive side) */
+	void	*(*decomp_alloc) __P((u_char *options, int opt_len));
+	/* Free space used by a decompressor */
+	void	(*decomp_free) __P((void *state));
+	/* Initialize a decompressor */
+	int	(*decomp_init) __P((void *state, u_char *options, int opt_len,
+				    int unit, int hdrlen, int mru, int debug));
+	/* Reset a decompressor */
+	void	(*decomp_reset) __P((void *state));
+	/* Decompress a packet. */
+	int	(*decompress) __P((void *state, PACKETPTR mp,
+				   PACKETPTR *dmpp));
+	/* Update state for an incompressible packet received */
+	void	(*incomp) __P((void *state, PACKETPTR mp));
+	/* Return decompression statistics */
+	void	(*decomp_stat) __P((void *state, struct compstat *stats));
+};
+#endif /* PACKETPTR */
+
+/*
+ * Return values for decompress routine.
+ * We need to make these distinctions so that we can disable certain
+ * useful functionality, namely sending a CCP reset-request as a result
+ * of an error detected after decompression.  This is to avoid infringing
+ * a patent held by Motorola.
+ * Don't you just lurve software patents.
+ */
+#define DECOMP_OK		0	/* everything went OK */
+#define DECOMP_ERROR		1	/* error detected before decomp. */
+#define DECOMP_FATALERROR	2	/* error detected after decomp. */
+
+/*
+ * CCP codes.
+ */
+#define CCP_CONFREQ	1
+#define CCP_CONFACK	2
+#define CCP_TERMREQ	5
+#define CCP_TERMACK	6
+#define CCP_RESETREQ	14
+#define CCP_RESETACK	15
+
+/*
+ * Max # bytes for a CCP option
+ */
+#define CCP_MAX_OPTION_LENGTH	32
+
+/*
+ * Parts of a CCP packet.
+ */
+#define CCP_CODE(dp)		((dp)[0])
+#define CCP_ID(dp)		((dp)[1])
+#define CCP_LENGTH(dp)		(((dp)[2] << 8) + (dp)[3])
+#define CCP_HDRLEN		4
+
+#define CCP_OPT_CODE(dp)	((dp)[0])
+#define CCP_OPT_LENGTH(dp)	((dp)[1])
+#define CCP_OPT_MINLEN		2
+
+/*
+ * Definitions for BSD-Compress.
+ */
+#define CI_BSD_COMPRESS		21	/* config. option for BSD-Compress */
+#define CILEN_BSD_COMPRESS	3	/* length of config. option */
+
+/* Macros for handling the 3rd byte of the BSD-Compress config option. */
+#define BSD_NBITS(x)		((x) & 0x1F)	/* number of bits requested */
+#define BSD_VERSION(x)		((x) >> 5)	/* version of option format */
+#define BSD_CURRENT_VERSION	1		/* current version number */
+#define BSD_MAKE_OPT(v, n)	(((v) << 5) | (n))
+
+#define BSD_MIN_BITS		9	/* smallest code size supported */
+#define BSD_MAX_BITS		15	/* largest code size supported */
+
+#endif /* _NET_PPP_COMP_H */
diff --git a/sys/net/ppp_defs.h b/sys/net/ppp_defs.h
new file mode 100644
index 0000000..77f01bb
--- /dev/null
+++ b/sys/net/ppp_defs.h
@@ -0,0 +1,160 @@
+/*	$Id: ppp_defs.h,v 1.7 1995/08/10 06:49:35 paulus Exp $	*/
+
+/*
+ * ppp_defs.h - PPP definitions.
+ *
+ * Copyright (c) 1994 The Australian National University.
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation is hereby granted, provided that the above copyright
+ * notice appears in all copies.  This software is provided without any
+ * warranty, express or implied. The Australian National University
+ * makes no representations about the suitability of this software for
+ * any purpose.
+ *
+ * IN NO EVENT SHALL THE AUSTRALIAN NATIONAL UNIVERSITY BE LIABLE TO ANY
+ * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
+ * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
+ * THE AUSTRALIAN NATIONAL UNIVERSITY HAVE BEEN ADVISED OF THE POSSIBILITY
+ * OF SUCH DAMAGE.
+ *
+ * THE AUSTRALIAN NATIONAL UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
+ * ON AN "AS IS" BASIS, AND THE AUSTRALIAN NATIONAL UNIVERSITY HAS NO
+ * OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS,
+ * OR MODIFICATIONS.
+ */
+
+#ifndef _PPP_DEFS_H_
+#define _PPP_DEFS_H_
+
+/*
+ * The basic PPP frame.
+ */
+#define PPP_HDRLEN	4	/* octets for standard ppp header */
+#define PPP_FCSLEN	2	/* octets for FCS */
+#define PPP_MRU		1500	/* default MRU = max length of info field */
+
+#define PPP_ADDRESS(p)	(((u_char *)(p))[0])
+#define PPP_CONTROL(p)	(((u_char *)(p))[1])
+#define PPP_PROTOCOL(p)	((((u_char *)(p))[2] << 8) + ((u_char *)(p))[3])
+
+/*
+ * Significant octet values.
+ */
+#define	PPP_ALLSTATIONS	0xff	/* All-Stations broadcast address */
+#define	PPP_UI		0x03	/* Unnumbered Information */
+#define	PPP_FLAG	0x7e	/* Flag Sequence */
+#define	PPP_ESCAPE	0x7d	/* Asynchronous Control Escape */
+#define	PPP_TRANS	0x20	/* Asynchronous transparency modifier */
+
+/*
+ * Protocol field values.
+ */
+#define PPP_IP		0x21	/* Internet Protocol */
+#define	PPP_VJC_COMP	0x2d	/* VJ compressed TCP */
+#define	PPP_VJC_UNCOMP	0x2f	/* VJ uncompressed TCP */
+#define PPP_COMP	0xfd	/* compressed packet */
+#define PPP_IPCP	0x8021	/* IP Control Protocol */
+#define PPP_CCP		0x80fd	/* Compression Control Protocol */
+#define PPP_LCP		0xc021	/* Link Control Protocol */
+#define PPP_PAP		0xc023	/* Password Authentication Protocol */
+#define PPP_LQR		0xc025	/* Link Quality Report protocol */
+#define PPP_CHAP	0xc223	/* Cryptographic Handshake Auth. Protocol */
+
+/*
+ * Values for FCS calculations.
+ */
+#define PPP_INITFCS	0xffff	/* Initial FCS value */
+#define PPP_GOODFCS	0xf0b8	/* Good final FCS value */
+#define PPP_FCS(fcs, c)	(((fcs) >> 8) ^ fcstab[((fcs) ^ (c)) & 0xff])
+
+/*
+ * A 32-bit unsigned integral type.
+ */
+#if !defined(__BIT_TYPES_DEFINED__) && !defined(_BITYPES)
+#ifdef	UINT32_T
+typedef UINT32_T	u_int32_t;
+#else
+typedef unsigned int	u_int32_t;
+#endif
+#endif
+
+/*
+ * Extended asyncmap - allows any character to be escaped.
+ */
+typedef u_int32_t	ext_accm[8];
+
+/*
+ * What to do with network protocol (NP) packets.
+ */
+enum NPmode {
+    NPMODE_PASS,		/* pass the packet through */
+    NPMODE_DROP,		/* silently drop the packet */
+    NPMODE_ERROR,		/* return an error */
+    NPMODE_QUEUE		/* save it up for later. */
+};
+
+/*
+ * Statistics.
+ */
+struct pppstat	{
+    u_int	ppp_ibytes;	/* bytes received */
+    u_int	ppp_ipackets;	/* packets received */
+    u_int	ppp_ierrors;	/* receive errors */
+    u_int	ppp_obytes;	/* bytes sent */
+    u_int	ppp_opackets;	/* packets sent */
+    u_int	ppp_oerrors;	/* transmit errors */
+};
+
+struct vjstat {
+    u_int	vjs_packets;	/* outbound packets */
+    u_int	vjs_compressed;	/* outbound compressed packets */
+    u_int	vjs_searches;	/* searches for connection state */
+    u_int	vjs_misses;	/* times couldn't find conn. state */
+    u_int	vjs_uncompressedin; /* inbound uncompressed packets */
+    u_int	vjs_compressedin;   /* inbound compressed packets */
+    u_int	vjs_errorin;	/* inbound unknown type packets */
+    u_int	vjs_tossed;	/* inbound packets tossed because of error */
+};
+
+struct ppp_stats {
+    struct pppstat	p;	/* basic PPP statistics */
+    struct vjstat	vj;	/* VJ header compression statistics */
+};
+
+struct compstat {
+    u_int	unc_bytes;	/* total uncompressed bytes */
+    u_int	unc_packets;	/* total uncompressed packets */
+    u_int	comp_bytes;	/* compressed bytes */
+    u_int	comp_packets;	/* compressed packets */
+    u_int	inc_bytes;	/* incompressible bytes */
+    u_int	inc_packets;	/* incompressible packets */
+    u_int	ratio;		/* recent compression ratio << 8 */
+};
+
+struct ppp_comp_stats {
+    struct compstat	c;	/* packet compression statistics */
+    struct compstat	d;	/* packet decompression statistics */
+};
+
+/*
+ * The following structure records the time in seconds since
+ * the last NP packet was sent or received.
+ */
+struct ppp_idle {
+    time_t xmit_idle;		/* time since last NP packet sent */
+    time_t recv_idle;		/* time since last NP packet received */
+};
+
+#ifndef __P
+#ifdef __STDC__
+#define __P(x)	x
+#else
+#define __P(x)	()
+#endif
+#endif
+
+#endif /* _PPP_DEFS_H_ */
diff --git a/sys/net/ppp_tty.c b/sys/net/ppp_tty.c
new file mode 100644
index 0000000..5ad17d2
--- /dev/null
+++ b/sys/net/ppp_tty.c
@@ -0,0 +1,1026 @@
+/*
+ * ppp_tty.c - Point-to-Point Protocol (PPP) driver for asynchronous
+ * 	       tty devices.
+ *
+ * Copyright (c) 1989 Carnegie Mellon University.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms are permitted
+ * provided that the above copyright notice and this paragraph are
+ * duplicated in all such forms and that any documentation,
+ * advertising materials, and other materials related to such
+ * distribution and use acknowledge that the software was developed
+ * by Carnegie Mellon University.  The name of the
+ * University may not be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
+ * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Drew D. Perkins
+ * Carnegie Mellon University
+ * 4910 Forbes Ave.
+ * Pittsburgh, PA 15213
+ * (412) 268-8576
+ * ddp@andrew.cmu.edu
+ *
+ * Based on:
+ *	@(#)if_sl.c	7.6.1.2 (Berkeley) 2/15/89
+ *
+ * Copyright (c) 1987 Regents of the University of California.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms are permitted
+ * provided that the above copyright notice and this paragraph are
+ * duplicated in all such forms and that any documentation,
+ * advertising materials, and other materials related to such
+ * distribution and use acknowledge that the software was developed
+ * by the University of California, Berkeley.  The name of the
+ * University may not be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
+ * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * Serial Line interface
+ *
+ * Rick Adams
+ * Center for Seismic Studies
+ * 1300 N 17th Street, Suite 1450
+ * Arlington, Virginia 22209
+ * (703)276-7900
+ * rick@seismo.ARPA
+ * seismo!rick
+ *
+ * Pounded on heavily by Chris Torek (chris@mimsy.umd.edu, umcp-cs!chris).
+ * Converted to 4.3BSD Beta by Chris Torek.
+ * Other changes made at Berkeley, based in part on code by Kirk Smith.
+ *
+ * Converted to 4.3BSD+ 386BSD by Brad Parker (brad@cayman.com)
+ * Added VJ tcp header compression; more unified ioctls
+ *
+ * Extensively modified by Paul Mackerras (paulus@cs.anu.edu.au).
+ * Cleaned up a lot of the mbuf-related code to fix bugs that
+ * caused system crashes and packet corruption.  Changed pppstart
+ * so that it doesn't just give up with a collision if the whole
+ * packet doesn't fit in the output ring buffer.
+ *
+ * Added priority queueing for interactive IP packets, following
+ * the model of if_sl.c, plus hooks for bpf.
+ * Paul Mackerras (paulus@cs.anu.edu.au).
+ */
+
+/* $Id: ppp_tty.c,v 1.3 1995/08/16 01:36:40 paulus Exp $ */
+/* from if_sl.c,v 1.11 84/10/04 12:54:47 rick Exp */
+
+#include "ppp.h"
+#if NPPP > 0
+
+#define VJC
+#define PPP_COMPRESS
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/proc.h>
+#include <sys/mbuf.h>
+#include <sys/dkstat.h>
+#include <sys/socket.h>
+#include <sys/ioctl.h>
+#include <sys/file.h>
+#include <sys/tty.h>
+#include <sys/kernel.h>
+#include <sys/conf.h>
+#include <sys/vnode.h>
+
+#include <net/if.h>
+#include <net/if_types.h>
+
+#ifdef VJC
+#include <netinet/in.h>
+#include <netinet/in_systm.h>
+#include <netinet/ip.h>
+#include <net/pppcompress.h>
+#endif
+
+#include <net/ppp_defs.h>
+#include <net/if_ppp.h>
+#include <net/if_pppvar.h>
+
+void	pppasyncattach __P((void));
+int	pppopen __P((dev_t dev, struct tty *tp));
+int	pppclose __P((struct tty *tp, int flag));
+int	pppread __P((struct tty *tp, struct uio *uio, int flag));
+int	pppwrite __P((struct tty *tp, struct uio *uio, int flag));
+int	ppptioctl __P((struct tty *tp, int cmd, caddr_t data, int flag,
+		       struct proc *));
+int	pppinput __P((int c, struct tty *tp));
+int	pppstart __P((struct tty *tp));
+
+static u_short	pppfcs __P((u_short fcs, u_char *cp, int len));
+static void	pppasyncstart __P((struct ppp_softc *));
+static void	pppasyncctlp __P((struct ppp_softc *));
+static void	pppasyncrelinq __P((struct ppp_softc *));
+static void	ppp_timeout __P((void *));
+static void	pppgetm __P((struct ppp_softc *sc));
+static void	pppdumpb __P((u_char *b, int l));
+static void	ppplogchar __P((struct ppp_softc *, int));
+
+/*
+ * Some useful mbuf macros not in mbuf.h.
+ */
+#define M_IS_CLUSTER(m)	((m)->m_flags & M_EXT)
+
+#define M_DATASTART(m)	\
+	(M_IS_CLUSTER(m) ? (m)->m_ext.ext_buf : \
+	    (m)->m_flags & M_PKTHDR ? (m)->m_pktdat : (m)->m_dat)
+
+#define M_DATASIZE(m)	\
+	(M_IS_CLUSTER(m) ? (m)->m_ext.ext_size : \
+	    (m)->m_flags & M_PKTHDR ? MHLEN: MLEN)
+
+/*
+ * Does c need to be escaped?
+ */
+#define ESCAPE_P(c)	(sc->sc_asyncmap[(c) >> 5] & (1 << ((c) & 0x1F)))
+
+/*
+ * Procedures for using an async tty interface for PPP.
+ */
+
+/* This is a FreeBSD-2.0 kernel. */
+#define CCOUNT(q)	((q)->c_cc)
+#define	PPP_HIWAT	400	/* Don't start a new packet if HIWAT on que */
+
+/*
+ * Define the PPP line discipline.
+ */
+
+static struct linesw pppdisc = {
+	pppopen, pppclose, pppread, pppwrite, ppptioctl,
+	pppinput, pppstart, ttymodem
+};
+
+void
+pppasyncattach()
+{
+    linesw[PPPDISC] = pppdisc;
+}
+
+TEXT_SET(pseudo_set, pppasyncattach);
+
+/*
+ * Line specific open routine for async tty devices.
+ * Attach the given tty to the first available ppp unit.
+ */
+/* ARGSUSED */
+int
+pppopen(dev, tp)
+    dev_t dev;
+    register struct tty *tp;
+{
+    struct proc *p = curproc;		/* XXX */
+    register struct ppp_softc *sc;
+    int error, s, i;
+
+    if (error = suser(p->p_ucred, &p->p_acflag))
+	return (error);
+
+    if (tp->t_line == PPPDISC) {
+	sc = (struct ppp_softc *) tp->t_sc;
+	if (sc != NULL && sc->sc_devp == (void *) tp)
+	    return (0);
+    }
+
+    if ((sc = pppalloc(p->p_pid)) == NULL)
+	return ENXIO;
+
+    if (sc->sc_relinq)
+	(*sc->sc_relinq)(sc);	/* get previous owner to relinquish the unit */
+
+    s = splimp();
+    sc->sc_ilen = 0;
+    sc->sc_m = NULL;
+    bzero(sc->sc_asyncmap, sizeof(sc->sc_asyncmap));
+    sc->sc_asyncmap[0] = 0xffffffff;
+    sc->sc_asyncmap[3] = 0x60000000;
+    sc->sc_rasyncmap = 0;
+    sc->sc_devp = (void *) tp;
+    sc->sc_start = pppasyncstart;
+    sc->sc_ctlp = pppasyncctlp;
+    sc->sc_relinq = pppasyncrelinq;
+    sc->sc_outm = NULL;
+    pppgetm(sc);
+    sc->sc_if.if_flags |= IFF_RUNNING;
+
+    tp->t_sc = (caddr_t) sc;
+    ttyflush(tp, FREAD | FWRITE);
+    splx(s);
+
+    return (0);
+}
+
+/*
+ * Line specific close routine.
+ * Detach the tty from the ppp unit.
+ * Mimics part of ttyclose().
+ */
+int
+pppclose(tp, flag)
+    struct tty *tp;
+    int flag;
+{
+    register struct ppp_softc *sc;
+    struct mbuf *m;
+    int s;
+
+    ttywflush(tp);
+    s = splimp();		/* paranoid; splnet probably ok */
+    tp->t_line = 0;
+    sc = (struct ppp_softc *) tp->t_sc;
+    if (sc != NULL) {
+	tp->t_sc = NULL;
+	if (tp == (struct tty *) sc->sc_devp) {
+	    pppasyncrelinq(sc);
+	    pppdealloc(sc);
+	}
+    }
+    splx(s);
+    return 0;
+}
+
+/*
+ * Relinquish the interface unit to another device.
+ */
+static void
+pppasyncrelinq(sc)
+    struct ppp_softc *sc;
+{
+    int s;
+
+    s = splimp();
+    if (sc->sc_outm) {
+	m_freem(sc->sc_outm);
+	sc->sc_outm = NULL;
+    }
+    if (sc->sc_m) {
+	m_freem(sc->sc_m);
+	sc->sc_m = NULL;
+    }
+    if (sc->sc_flags & SC_TIMEOUT) {
+	untimeout(ppp_timeout, (void *) sc);
+	sc->sc_flags &= ~SC_TIMEOUT;
+    }
+    splx(s);
+}
+
+/*
+ * Line specific (tty) read routine.
+ */
+int
+pppread(tp, uio, flag)
+    register struct tty *tp;
+    struct uio *uio;
+    int flag;
+{
+    register struct ppp_softc *sc = (struct ppp_softc *)tp->t_sc;
+    struct mbuf *m, *m0;
+    register int s;
+    int error = 0;
+
+    if (sc == NULL)
+	return 0;
+    /*
+     * Loop waiting for input, checking that nothing disasterous
+     * happens in the meantime.
+     */
+    s = splimp();
+    for (;;) {
+	if (tp != (struct tty *) sc->sc_devp || tp->t_line != PPPDISC) {
+	    splx(s);
+	    return 0;
+	}
+	if (sc->sc_inq.ifq_head != NULL)
+	    break;
+	if ((tp->t_state & TS_CONNECTED) == 0 && (tp->t_state & TS_ISOPEN)) {
+	    splx(s);
+	    return 0;		/* end of file */
+	}
+	if (tp->t_state & TS_ASYNC || flag & IO_NDELAY) {
+	    splx(s);
+	    return (EWOULDBLOCK);
+	}
+	error = ttysleep(tp, TSA_HUP_OR_INPUT(tp), TTIPRI | PCATCH, "pppin", 0);
+	if (error) {
+	    splx(s);
+	    return error;
+	}
+    }
+
+    /* Pull place-holder byte out of canonical queue */
+    getc(&tp->t_canq);
+
+    /* Get the packet from the input queue */
+    IF_DEQUEUE(&sc->sc_inq, m0);
+    splx(s);
+
+    for (m = m0; m && uio->uio_resid; m = m->m_next)
+	if (error = uiomove(mtod(m, u_char *), m->m_len, uio))
+	    break;
+    m_freem(m0);
+    return (error);
+}
+
+/*
+ * Line specific (tty) write routine.
+ */
+int
+pppwrite(tp, uio, flag)
+    register struct tty *tp;
+    struct uio *uio;
+    int flag;
+{
+    register struct ppp_softc *sc = (struct ppp_softc *)tp->t_sc;
+    struct mbuf *m, *m0, **mp;
+    struct sockaddr dst;
+    int len, error;
+
+    if ((tp->t_state & TS_CONNECTED) == 0)
+	return 0;		/* wrote 0 bytes */
+    if (tp->t_line != PPPDISC)
+	return (EINVAL);
+    if (sc == NULL || tp != (struct tty *) sc->sc_devp)
+	return EIO;
+    if (uio->uio_resid > sc->sc_if.if_mtu + PPP_HDRLEN ||
+	uio->uio_resid < PPP_HDRLEN)
+	return (EMSGSIZE);
+    for (mp = &m0; uio->uio_resid; mp = &m->m_next) {
+	MGET(m, M_WAIT, MT_DATA);
+	if ((*mp = m) == NULL) {
+	    m_freem(m0);
+	    return (ENOBUFS);
+	}
+	m->m_len = 0;
+	if (uio->uio_resid >= MCLBYTES / 2)
+	    MCLGET(m, M_DONTWAIT);
+	len = M_TRAILINGSPACE(m);
+	if (len > uio->uio_resid)
+	    len = uio->uio_resid;
+	if (error = uiomove(mtod(m, u_char *), len, uio)) {
+	    m_freem(m0);
+	    return (error);
+	}
+	m->m_len = len;
+    }
+    dst.sa_family = AF_UNSPEC;
+    bcopy(mtod(m0, u_char *), dst.sa_data, PPP_HDRLEN);
+    m0->m_data += PPP_HDRLEN;
+    m0->m_len -= PPP_HDRLEN;
+    return (pppoutput(&sc->sc_if, m0, &dst, (struct rtentry *)0));
+}
+
+/*
+ * Line specific (tty) ioctl routine.
+ * This discipline requires that tty device drivers call
+ * the line specific l_ioctl routine from their ioctl routines.
+ */
+/* ARGSUSED */
+int
+ppptioctl(tp, cmd, data, flag, p)
+    struct tty *tp;
+    caddr_t data;
+    int cmd, flag;
+    struct proc *p;
+{
+    struct ppp_softc *sc = (struct ppp_softc *) tp->t_sc;
+    int error, s;
+
+    if (sc == NULL || tp != (struct tty *) sc->sc_devp)
+	return -1;
+
+    error = 0;
+    switch (cmd) {
+    case PPPIOCSASYNCMAP:
+	if (error = suser(p->p_ucred, &p->p_acflag))
+	    break;
+	sc->sc_asyncmap[0] = *(u_int *)data;
+	break;
+
+    case PPPIOCGASYNCMAP:
+	*(u_int *)data = sc->sc_asyncmap[0];
+	break;
+
+    case PPPIOCSRASYNCMAP:
+	if (error = suser(p->p_ucred, &p->p_acflag))
+	    break;
+	sc->sc_rasyncmap = *(u_int *)data;
+	break;
+
+    case PPPIOCGRASYNCMAP:
+	*(u_int *)data = sc->sc_rasyncmap;
+	break;
+
+    case PPPIOCSXASYNCMAP:
+	if (error = suser(p->p_ucred, &p->p_acflag))
+	    break;
+	s = spltty();
+	bcopy(data, sc->sc_asyncmap, sizeof(sc->sc_asyncmap));
+	sc->sc_asyncmap[1] = 0;		    /* mustn't escape 0x20 - 0x3f */
+	sc->sc_asyncmap[2] &= ~0x40000000;  /* mustn't escape 0x5e */
+	sc->sc_asyncmap[3] |= 0x60000000;   /* must escape 0x7d, 0x7e */
+	splx(s);
+	break;
+
+    case PPPIOCGXASYNCMAP:
+	bcopy(sc->sc_asyncmap, data, sizeof(sc->sc_asyncmap));
+	break;
+
+    default:
+	error = pppioctl(sc, cmd, data, flag, p);
+	if (error == 0 && cmd == PPPIOCSMRU)
+	    pppgetm(sc);
+    }
+
+    return error;
+}
+
+/*
+ * FCS lookup table as calculated by genfcstab.
+ */
+static u_short fcstab[256] = {
+	0x0000,	0x1189,	0x2312,	0x329b,	0x4624,	0x57ad,	0x6536,	0x74bf,
+	0x8c48,	0x9dc1,	0xaf5a,	0xbed3,	0xca6c,	0xdbe5,	0xe97e,	0xf8f7,
+	0x1081,	0x0108,	0x3393,	0x221a,	0x56a5,	0x472c,	0x75b7,	0x643e,
+	0x9cc9,	0x8d40,	0xbfdb,	0xae52,	0xdaed,	0xcb64,	0xf9ff,	0xe876,
+	0x2102,	0x308b,	0x0210,	0x1399,	0x6726,	0x76af,	0x4434,	0x55bd,
+	0xad4a,	0xbcc3,	0x8e58,	0x9fd1,	0xeb6e,	0xfae7,	0xc87c,	0xd9f5,
+	0x3183,	0x200a,	0x1291,	0x0318,	0x77a7,	0x662e,	0x54b5,	0x453c,
+	0xbdcb,	0xac42,	0x9ed9,	0x8f50,	0xfbef,	0xea66,	0xd8fd,	0xc974,
+	0x4204,	0x538d,	0x6116,	0x709f,	0x0420,	0x15a9,	0x2732,	0x36bb,
+	0xce4c,	0xdfc5,	0xed5e,	0xfcd7,	0x8868,	0x99e1,	0xab7a,	0xbaf3,
+	0x5285,	0x430c,	0x7197,	0x601e,	0x14a1,	0x0528,	0x37b3,	0x263a,
+	0xdecd,	0xcf44,	0xfddf,	0xec56,	0x98e9,	0x8960,	0xbbfb,	0xaa72,
+	0x6306,	0x728f,	0x4014,	0x519d,	0x2522,	0x34ab,	0x0630,	0x17b9,
+	0xef4e,	0xfec7,	0xcc5c,	0xddd5,	0xa96a,	0xb8e3,	0x8a78,	0x9bf1,
+	0x7387,	0x620e,	0x5095,	0x411c,	0x35a3,	0x242a,	0x16b1,	0x0738,
+	0xffcf,	0xee46,	0xdcdd,	0xcd54,	0xb9eb,	0xa862,	0x9af9,	0x8b70,
+	0x8408,	0x9581,	0xa71a,	0xb693,	0xc22c,	0xd3a5,	0xe13e,	0xf0b7,
+	0x0840,	0x19c9,	0x2b52,	0x3adb,	0x4e64,	0x5fed,	0x6d76,	0x7cff,
+	0x9489,	0x8500,	0xb79b,	0xa612,	0xd2ad,	0xc324,	0xf1bf,	0xe036,
+	0x18c1,	0x0948,	0x3bd3,	0x2a5a,	0x5ee5,	0x4f6c,	0x7df7,	0x6c7e,
+	0xa50a,	0xb483,	0x8618,	0x9791,	0xe32e,	0xf2a7,	0xc03c,	0xd1b5,
+	0x2942,	0x38cb,	0x0a50,	0x1bd9,	0x6f66,	0x7eef,	0x4c74,	0x5dfd,
+	0xb58b,	0xa402,	0x9699,	0x8710,	0xf3af,	0xe226,	0xd0bd,	0xc134,
+	0x39c3,	0x284a,	0x1ad1,	0x0b58,	0x7fe7,	0x6e6e,	0x5cf5,	0x4d7c,
+	0xc60c,	0xd785,	0xe51e,	0xf497,	0x8028,	0x91a1,	0xa33a,	0xb2b3,
+	0x4a44,	0x5bcd,	0x6956,	0x78df,	0x0c60,	0x1de9,	0x2f72,	0x3efb,
+	0xd68d,	0xc704,	0xf59f,	0xe416,	0x90a9,	0x8120,	0xb3bb,	0xa232,
+	0x5ac5,	0x4b4c,	0x79d7,	0x685e,	0x1ce1,	0x0d68,	0x3ff3,	0x2e7a,
+	0xe70e,	0xf687,	0xc41c,	0xd595,	0xa12a,	0xb0a3,	0x8238,	0x93b1,
+	0x6b46,	0x7acf,	0x4854,	0x59dd,	0x2d62,	0x3ceb,	0x0e70,	0x1ff9,
+	0xf78f,	0xe606,	0xd49d,	0xc514,	0xb1ab,	0xa022,	0x92b9,	0x8330,
+	0x7bc7,	0x6a4e,	0x58d5,	0x495c,	0x3de3,	0x2c6a,	0x1ef1,	0x0f78
+};
+
+/*
+ * Calculate a new FCS given the current FCS and the new data.
+ */
+static u_short
+pppfcs(fcs, cp, len)
+    register u_short fcs;
+    register u_char *cp;
+    register int len;
+{
+    while (len--)
+	fcs = PPP_FCS(fcs, *cp++);
+    return (fcs);
+}
+
+/*
+ * This gets called from pppoutput when a new packet is
+ * put on a queue.
+ */
+static void
+pppasyncstart(sc)
+    register struct ppp_softc *sc;
+{
+    register struct tty *tp = (struct tty *) sc->sc_devp;
+    int s;
+
+    s = splimp();
+    pppstart(tp);
+    splx(s);
+}
+
+/*
+ * This gets called when a received packet is placed on
+ * the inq.
+ */
+static void
+pppasyncctlp(sc)
+    struct ppp_softc *sc;
+{
+    struct tty *tp;
+
+    /* Put a placeholder byte in canq for ttselect()/ttnread(). */
+    tp = (struct tty *) sc->sc_devp;
+    putc(0, &tp->t_canq);
+    ttwakeup(tp);
+}
+
+/*
+ * Start output on async tty interface.  Get another datagram
+ * to send from the interface queue and start sending it.
+ */
+int
+pppstart(tp)
+    register struct tty *tp;
+{
+    register struct ppp_softc *sc = (struct ppp_softc *) tp->t_sc;
+    register struct mbuf *m;
+    register int len;
+    register u_char *start, *stop, *cp;
+    int n, s, ndone, done, idle;
+    struct mbuf *m2;
+
+    if ((tp->t_state & TS_CONNECTED) == 0
+	|| sc == NULL || tp != (struct tty *) sc->sc_devp) {
+	if (tp->t_oproc != NULL)
+	    (*tp->t_oproc)(tp);
+	return 0;
+    }
+
+    idle = 0;
+    while (CCOUNT(&tp->t_outq) < PPP_HIWAT) {
+	/*
+	 * See if we have an existing packet partly sent.
+	 * If not, get a new packet and start sending it.
+	 */
+	m = sc->sc_outm;
+	if (m == NULL) {
+	    /*
+	     * Get another packet to be sent.
+	     */
+	    m = ppp_dequeue(sc);
+	    if (m == NULL) {
+		idle = 1;
+		break;
+	    }
+
+	    /*
+	     * The extra PPP_FLAG will start up a new packet, and thus
+	     * will flush any accumulated garbage.  We do this whenever
+	     * the line may have been idle for some time.
+	     */
+	    if (CCOUNT(&tp->t_outq) == 0) {
+		++sc->sc_bytessent;
+		(void) putc(PPP_FLAG, &tp->t_outq);
+	    }
+
+	    /* Calculate the FCS for the first mbuf's worth. */
+	    sc->sc_outfcs = pppfcs(PPP_INITFCS, mtod(m, u_char *), m->m_len);
+	}
+
+	for (;;) {
+	    start = mtod(m, u_char *);
+	    len = m->m_len;
+	    stop = start + len;
+	    while (len > 0) {
+		/*
+		 * Find out how many bytes in the string we can
+		 * handle without doing something special.
+		 */
+		for (cp = start; cp < stop; cp++)
+		    if (ESCAPE_P(*cp))
+			break;
+		n = cp - start;
+		if (n) {
+		    /* NetBSD (0.9 or later), 4.3-Reno or similar. */
+		    ndone = n - b_to_q(start, n, &tp->t_outq);
+		    len -= ndone;
+		    start += ndone;
+		    sc->sc_bytessent += ndone;
+
+		    if (ndone < n)
+			break;	/* packet doesn't fit */
+		}
+		/*
+		 * If there are characters left in the mbuf,
+		 * the first one must be special..
+		 * Put it out in a different form.
+		 */
+		if (len) {
+		    if (putc(PPP_ESCAPE, &tp->t_outq))
+			break;
+		    if (putc(*start ^ PPP_TRANS, &tp->t_outq)) {
+			(void) unputc(&tp->t_outq);
+			break;
+		    }
+		    sc->sc_bytessent += 2;
+		    start++;
+		    len--;
+		}
+	    }
+
+	    /*
+	     * If we didn't empty this mbuf, remember where we're up to.
+	     * If we emptied the last mbuf, try to add the FCS and closing
+	     * flag, and if we can't, leave sc_outm pointing to m, but with
+	     * m->m_len == 0, to remind us to output the FCS and flag later.
+	     */
+	    done = len == 0;
+	    if (done && m->m_next == NULL) {
+		u_char *p, *q;
+		int c;
+		u_char endseq[8];
+
+		/*
+		 * We may have to escape the bytes in the FCS.
+		 */
+		p = endseq;
+		c = ~sc->sc_outfcs & 0xFF;
+		if (ESCAPE_P(c)) {
+		    *p++ = PPP_ESCAPE;
+		    *p++ = c ^ PPP_TRANS;
+		} else
+		    *p++ = c;
+		c = (~sc->sc_outfcs >> 8) & 0xFF;
+		if (ESCAPE_P(c)) {
+		    *p++ = PPP_ESCAPE;
+		    *p++ = c ^ PPP_TRANS;
+		} else
+		    *p++ = c;
+		*p++ = PPP_FLAG;
+
+		/*
+		 * Try to output the FCS and flag.  If the bytes
+		 * don't all fit, back out.
+		 */
+		for (q = endseq; q < p; ++q)
+		    if (putc(*q, &tp->t_outq)) {
+			done = 0;
+			for (; q > endseq; --q)
+			    unputc(&tp->t_outq);
+			break;
+		    }
+		sc->sc_bytessent += q - endseq;
+	    }
+
+	    if (!done) {
+		/* remember where we got to */
+		m->m_data = start;
+		m->m_len = len;
+		break;
+	    }
+
+	    /* Finished with this mbuf; free it and move on. */
+	    MFREE(m, m2);
+	    m = m2;
+	    if (m == NULL) {
+		/* Finished a packet */
+		sc->sc_if.if_opackets++;
+		sc->sc_if.if_obytes = sc->sc_bytessent;
+		break;
+	    }
+	    sc->sc_outfcs = pppfcs(sc->sc_outfcs, mtod(m, u_char *), m->m_len);
+	}
+
+	/*
+	 * Here we have either finished a packet (m == NULL)
+	 * or filled up the output queue (m != NULL).
+	 */
+	sc->sc_outm = m;
+	if (m)
+	    break;
+    }
+
+    /*
+     * Send anything that may be in the output queue.
+     * We are being called in lieu of ttstart and must do what it would.
+     */
+    if (tp->t_oproc != NULL)
+	(*tp->t_oproc)(tp);
+
+    /*
+     * This timeout is needed for operation on a pseudo-tty,
+     * because the pty code doesn't call pppstart after it has
+     * drained the t_outq.
+     */
+    if (!idle && (sc->sc_flags & SC_TIMEOUT) == 0) {
+	timeout(ppp_timeout, (void *) sc, 1);
+	sc->sc_flags |= SC_TIMEOUT;
+    }
+
+    return 0;
+}
+
+/*
+ * Timeout routine - try to start some more output.
+ */
+static void
+ppp_timeout(x)
+    void *x;
+{
+    struct ppp_softc *sc = (struct ppp_softc *) x;
+    struct tty *tp = (struct tty *) sc->sc_devp;
+    int s;
+
+    s = splimp();
+    sc->sc_flags &= ~SC_TIMEOUT;
+    pppstart(tp);
+    splx(s);
+}
+
+/*
+ * Allocate enough mbuf to handle current MRU.
+ */
+static void
+pppgetm(sc)
+    register struct ppp_softc *sc;
+{
+    struct mbuf *m, **mp;
+    int len;
+    int s;
+
+    s = splimp();
+    mp = &sc->sc_m;
+    for (len = sc->sc_mru + PPP_HDRLEN + PPP_FCSLEN; len > 0; ){
+	if ((m = *mp) == NULL) {
+	    MGETHDR(m, M_DONTWAIT, MT_DATA);
+	    if (m == NULL)
+		break;
+	    *mp = m;
+	    MCLGET(m, M_DONTWAIT);
+	}
+	len -= M_DATASIZE(m);
+	mp = &m->m_next;
+    }
+    splx(s);
+}
+
+/*
+ * tty interface receiver interrupt.
+ */
+static unsigned paritytab[8] = {
+    0x96696996, 0x69969669, 0x69969669, 0x96696996,
+    0x69969669, 0x96696996, 0x96696996, 0x69969669
+};
+
+int
+pppinput(c, tp)
+    int c;
+    register struct tty *tp;
+{
+    register struct ppp_softc *sc;
+    struct mbuf *m;
+    int ilen, s;
+
+    sc = (struct ppp_softc *) tp->t_sc;
+    if (sc == NULL || tp != (struct tty *) sc->sc_devp)
+	return 0;
+
+    s = spltty();
+    ++tk_nin;
+    ++sc->sc_bytesrcvd;
+
+    if (c & TTY_FE) {
+	/* framing error or overrun on this char - abort packet */
+	if (sc->sc_flags & SC_DEBUG)
+	    printf("ppp%d: bad char %x\n", sc->sc_if.if_unit, c);
+	goto flush;
+    }
+
+    c &= 0xff;
+
+    if (c & 0x80)
+	sc->sc_flags |= SC_RCV_B7_1;
+    else
+	sc->sc_flags |= SC_RCV_B7_0;
+    if (paritytab[c >> 5] & (1 << (c & 0x1F)))
+	sc->sc_flags |= SC_RCV_ODDP;
+    else
+	sc->sc_flags |= SC_RCV_EVNP;
+
+    if (sc->sc_flags & SC_LOG_RAWIN)
+	ppplogchar(sc, c);
+
+    if (c == PPP_FLAG) {
+	ilen = sc->sc_ilen;
+	sc->sc_ilen = 0;
+	sc->sc_if.if_ibytes = sc->sc_bytesrcvd;
+
+	if (sc->sc_rawin_count > 0) 
+	    ppplogchar(sc, -1);
+
+	/*
+	 * If SC_ESCAPED is set, then we've seen the packet
+	 * abort sequence "}~".
+	 */
+	if (sc->sc_flags & (SC_FLUSH | SC_ESCAPED)
+	    || ilen > 0 && sc->sc_fcs != PPP_GOODFCS) {
+	    sc->sc_flags |= SC_PKTLOST;	/* note the dropped packet */
+	    if ((sc->sc_flags & (SC_FLUSH | SC_ESCAPED)) == 0){
+		if (sc->sc_flags & SC_DEBUG)
+		    printf("ppp%d: bad fcs %x\n", sc->sc_if.if_unit,
+			   sc->sc_fcs);
+		sc->sc_if.if_ierrors++;
+	    } else
+		sc->sc_flags &= ~(SC_FLUSH | SC_ESCAPED);
+	    splx(s);
+	    return 0;
+	}
+
+	if (ilen < PPP_HDRLEN + PPP_FCSLEN) {
+	    if (ilen) {
+		if (sc->sc_flags & SC_DEBUG)
+		    printf("ppp%d: too short (%d)\n", sc->sc_if.if_unit, ilen);
+		sc->sc_if.if_ierrors++;
+		sc->sc_flags |= SC_PKTLOST;
+	    }
+	    splx(s);
+	    return 0;
+	}
+
+	/*
+	 * Remove FCS trailer.  Somewhat painful...
+	 */
+	ilen -= 2;
+	if (--sc->sc_mc->m_len == 0) {
+	    for (m = sc->sc_m; m->m_next != sc->sc_mc; m = m->m_next)
+		;
+	    sc->sc_mc = m;
+	}
+	sc->sc_mc->m_len--;
+
+	/* excise this mbuf chain */
+	m = sc->sc_m;
+	sc->sc_m = sc->sc_mc->m_next;
+	sc->sc_mc->m_next = NULL;
+
+	ppppktin(sc, m, sc->sc_flags & SC_PKTLOST);
+	sc->sc_flags &= ~SC_PKTLOST;
+
+	pppgetm(sc);
+	splx(s);
+	return 0;
+    }
+
+    if (sc->sc_flags & SC_FLUSH) {
+	if (sc->sc_flags & SC_LOG_FLUSH)
+	    ppplogchar(sc, c);
+	splx(s);
+	return 0;
+    }
+
+    if (c < 0x20 && (sc->sc_rasyncmap & (1 << c))) {
+	splx(s);
+	return 0;
+    }
+
+    if (sc->sc_flags & SC_ESCAPED) {
+	sc->sc_flags &= ~SC_ESCAPED;
+	c ^= PPP_TRANS;
+    } else if (c == PPP_ESCAPE) {
+	sc->sc_flags |= SC_ESCAPED;
+	splx(s);
+	return 0;
+    }
+
+    /*
+     * Initialize buffer on first octet received.
+     * First octet could be address or protocol (when compressing
+     * address/control).
+     * Second octet is control.
+     * Third octet is first or second (when compressing protocol)
+     * octet of protocol.
+     * Fourth octet is second octet of protocol.
+     */
+    if (sc->sc_ilen == 0) {
+	/* reset the first input mbuf */
+	if (sc->sc_m == NULL) {
+	    pppgetm(sc);
+	    if (sc->sc_m == NULL) {
+		if (sc->sc_flags & SC_DEBUG)
+		    printf("ppp%d: no input mbufs!\n", sc->sc_if.if_unit);
+		goto flush;
+	    }
+	}
+	m = sc->sc_m;
+	m->m_len = 0;
+	m->m_data = M_DATASTART(sc->sc_m);
+	sc->sc_mc = m;
+	sc->sc_mp = mtod(m, char *);
+	sc->sc_fcs = PPP_INITFCS;
+	if (c != PPP_ALLSTATIONS) {
+	    if (sc->sc_flags & SC_REJ_COMP_AC) {
+		if (sc->sc_flags & SC_DEBUG)
+		    printf("ppp%d: garbage received: 0x%x (need 0xFF)\n",
+			   sc->sc_if.if_unit, c);
+		goto flush;
+	    }
+	    *sc->sc_mp++ = PPP_ALLSTATIONS;
+	    *sc->sc_mp++ = PPP_UI;
+	    sc->sc_ilen += 2;
+	    m->m_len += 2;
+	}
+    }
+    if (sc->sc_ilen == 1 && c != PPP_UI) {
+	if (sc->sc_flags & SC_DEBUG)
+	    printf("ppp%d: missing UI (0x3), got 0x%x\n",
+		   sc->sc_if.if_unit, c);
+	goto flush;
+    }
+    if (sc->sc_ilen == 2 && (c & 1) == 1) {
+	/* a compressed protocol */
+	*sc->sc_mp++ = 0;
+	sc->sc_ilen++;
+	sc->sc_mc->m_len++;
+    }
+    if (sc->sc_ilen == 3 && (c & 1) == 0) {
+	if (sc->sc_flags & SC_DEBUG)
+	    printf("ppp%d: bad protocol %x\n", sc->sc_if.if_unit,
+		   (sc->sc_mp[-1] << 8) + c);
+	goto flush;
+    }
+
+    /* packet beyond configured mru? */
+    if (++sc->sc_ilen > sc->sc_mru + PPP_HDRLEN + PPP_FCSLEN) {
+	if (sc->sc_flags & SC_DEBUG)
+	    printf("ppp%d: packet too big\n", sc->sc_if.if_unit);
+	goto flush;
+    }
+
+    /* is this mbuf full? */
+    m = sc->sc_mc;
+    if (M_TRAILINGSPACE(m) <= 0) {
+	if (m->m_next == NULL) {
+	    pppgetm(sc);
+	    if (m->m_next == NULL) {
+		if (sc->sc_flags & SC_DEBUG)
+		    printf("ppp%d: too few input mbufs!\n", sc->sc_if.if_unit);
+		goto flush;
+	    }
+	}
+	sc->sc_mc = m = m->m_next;
+	m->m_len = 0;
+	m->m_data = M_DATASTART(m);
+	sc->sc_mp = mtod(m, char *);
+    }
+
+    ++m->m_len;
+    *sc->sc_mp++ = c;
+    sc->sc_fcs = PPP_FCS(sc->sc_fcs, c);
+    splx(s);
+    return 0;
+
+ flush:
+    if (!(sc->sc_flags & SC_FLUSH)) {
+	sc->sc_if.if_ierrors++;
+	sc->sc_flags |= SC_FLUSH;
+	if (sc->sc_flags & SC_LOG_FLUSH)
+	    ppplogchar(sc, c);
+    }
+    splx(s);
+    return 0;
+}
+
+#define MAX_DUMP_BYTES	128
+
+static void
+ppplogchar(sc, c)
+    struct ppp_softc *sc;
+    int c;
+{
+    if (c >= 0)
+	sc->sc_rawin[sc->sc_rawin_count++] = c;
+    if (sc->sc_rawin_count >= sizeof(sc->sc_rawin)
+	|| c < 0 && sc->sc_rawin_count > 0) {
+	printf("ppp%d input: ", sc->sc_if.if_unit);
+	pppdumpb(sc->sc_rawin, sc->sc_rawin_count);
+	sc->sc_rawin_count = 0;
+    }
+}
+
+static void
+pppdumpb(b, l)
+    u_char *b;
+    int l;
+{
+    char buf[3*MAX_DUMP_BYTES+4];
+    char *bp = buf;
+    static char digits[] = "0123456789abcdef";
+
+    while (l--) {
+	if (bp >= buf + sizeof(buf) - 3) {
+	    *bp++ = '>';
+	    break;
+	}
+	*bp++ = digits[*b >> 4]; /* convert byte to ascii hex */
+	*bp++ = digits[*b++ & 0xf];
+	*bp++ = ' ';
+    }
+
+    *bp = 0;
+    printf("%s\n", buf);
+}
+
+#endif	/* NPPP > 0 */