17c478bd9Sstevel@tonic-gate /*
2*002c70ffScarlsonj  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
3*002c70ffScarlsonj  * Use is subject to license terms.
47c478bd9Sstevel@tonic-gate  *
57c478bd9Sstevel@tonic-gate  * Because this code is derived from the 4.3BSD compress source:
67c478bd9Sstevel@tonic-gate  *
77c478bd9Sstevel@tonic-gate  * Copyright (c) 1985, 1986 The Regents of the University of California.
87c478bd9Sstevel@tonic-gate  * All rights reserved.
97c478bd9Sstevel@tonic-gate  *
107c478bd9Sstevel@tonic-gate  * This code is derived from software contributed to Berkeley by
117c478bd9Sstevel@tonic-gate  * James A. Woods, derived from original work by Spencer Thomas
127c478bd9Sstevel@tonic-gate  * and Joseph Orost.
137c478bd9Sstevel@tonic-gate  *
147c478bd9Sstevel@tonic-gate  * Redistribution and use in source and binary forms, with or without
157c478bd9Sstevel@tonic-gate  * modification, are permitted provided that the following conditions
167c478bd9Sstevel@tonic-gate  * are met:
177c478bd9Sstevel@tonic-gate  * 1. Redistributions of source code must retain the above copyright
187c478bd9Sstevel@tonic-gate  *    notice, this list of conditions and the following disclaimer.
197c478bd9Sstevel@tonic-gate  * 2. Redistributions in binary form must reproduce the above copyright
207c478bd9Sstevel@tonic-gate  *    notice, this list of conditions and the following disclaimer in the
217c478bd9Sstevel@tonic-gate  *    documentation and/or other materials provided with the distribution.
227c478bd9Sstevel@tonic-gate  * 3. All advertising materials mentioning features or use of this software
237c478bd9Sstevel@tonic-gate  *    must display the following acknowledgement:
247c478bd9Sstevel@tonic-gate  *	This product includes software developed by the University of
257c478bd9Sstevel@tonic-gate  *	California, Berkeley and its contributors.
267c478bd9Sstevel@tonic-gate  * 4. Neither the name of the University nor the names of its contributors
277c478bd9Sstevel@tonic-gate  *    may be used to endorse or promote products derived from this software
287c478bd9Sstevel@tonic-gate  *    without specific prior written permission.
297c478bd9Sstevel@tonic-gate  *
307c478bd9Sstevel@tonic-gate  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
317c478bd9Sstevel@tonic-gate  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
327c478bd9Sstevel@tonic-gate  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
337c478bd9Sstevel@tonic-gate  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
347c478bd9Sstevel@tonic-gate  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
357c478bd9Sstevel@tonic-gate  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
367c478bd9Sstevel@tonic-gate  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
377c478bd9Sstevel@tonic-gate  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
387c478bd9Sstevel@tonic-gate  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
397c478bd9Sstevel@tonic-gate  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
407c478bd9Sstevel@tonic-gate  * SUCH DAMAGE.
417c478bd9Sstevel@tonic-gate  */
427c478bd9Sstevel@tonic-gate 
437c478bd9Sstevel@tonic-gate #pragma ident	"%Z%%M%	%I%	%E% SMI"
447c478bd9Sstevel@tonic-gate 
457c478bd9Sstevel@tonic-gate /*
467c478bd9Sstevel@tonic-gate  * This version is for use with STREAMS in Solaris 2
477c478bd9Sstevel@tonic-gate  *
487c478bd9Sstevel@tonic-gate  * $Id: bsd-comp.c,v 1.20 1996/08/28 06:31:57 paulus Exp $
497c478bd9Sstevel@tonic-gate  */
507c478bd9Sstevel@tonic-gate 
517c478bd9Sstevel@tonic-gate #include <sys/param.h>
527c478bd9Sstevel@tonic-gate #include <sys/types.h>
537c478bd9Sstevel@tonic-gate #include <sys/kmem.h>
547c478bd9Sstevel@tonic-gate #include <sys/stream.h>
557c478bd9Sstevel@tonic-gate #include <sys/cmn_err.h>
567c478bd9Sstevel@tonic-gate #include <sys/ddi.h>
577c478bd9Sstevel@tonic-gate #include <sys/sunddi.h>
587c478bd9Sstevel@tonic-gate #include <sys/byteorder.h>
597c478bd9Sstevel@tonic-gate #include <net/ppp_defs.h>
607c478bd9Sstevel@tonic-gate 
617c478bd9Sstevel@tonic-gate /* Defined for platform-neutral include file */
627c478bd9Sstevel@tonic-gate #define	PACKETPTR		mblk_t *
637c478bd9Sstevel@tonic-gate #include <net/ppp-comp.h>
647c478bd9Sstevel@tonic-gate 
657c478bd9Sstevel@tonic-gate #ifndef _BIG_ENDIAN
667c478bd9Sstevel@tonic-gate #define	BSD_LITTLE_ENDIAN
677c478bd9Sstevel@tonic-gate #endif
687c478bd9Sstevel@tonic-gate 
697c478bd9Sstevel@tonic-gate #if DO_BSD_COMPRESS
707c478bd9Sstevel@tonic-gate 
717c478bd9Sstevel@tonic-gate /*
727c478bd9Sstevel@tonic-gate  * PPP "BSD compress" compression
737c478bd9Sstevel@tonic-gate  *
747c478bd9Sstevel@tonic-gate  *  The differences between this compression and the classic BSD LZW
757c478bd9Sstevel@tonic-gate  *  source are obvious from the requirement that the classic code worked
767c478bd9Sstevel@tonic-gate  *  with files while this handles arbitrarily long streams that
777c478bd9Sstevel@tonic-gate  *  are broken into packets.  They are:
787c478bd9Sstevel@tonic-gate  *
797c478bd9Sstevel@tonic-gate  *	When the code size expands, a block of junk is not emitted by
807c478bd9Sstevel@tonic-gate  *	    the compressor and not expected by the decompressor.
817c478bd9Sstevel@tonic-gate  *
827c478bd9Sstevel@tonic-gate  *	New codes are not necessarily assigned every time an old
837c478bd9Sstevel@tonic-gate  *	    code is output by the compressor.  This is because a packet
847c478bd9Sstevel@tonic-gate  *	    end forces a code to be emitted, but does not imply that a
857c478bd9Sstevel@tonic-gate  *	    new sequence has been seen.
867c478bd9Sstevel@tonic-gate  *
877c478bd9Sstevel@tonic-gate  *	The compression ratio is checked at the first end of a packet
887c478bd9Sstevel@tonic-gate  *	    after the appropriate gap.	Besides simplifying and speeding
897c478bd9Sstevel@tonic-gate  *	    things up, this makes it more likely that the transmitter
907c478bd9Sstevel@tonic-gate  *	    and receiver will agree when the dictionary is cleared when
917c478bd9Sstevel@tonic-gate  *	    compression is not going well.
927c478bd9Sstevel@tonic-gate  */
937c478bd9Sstevel@tonic-gate 
947c478bd9Sstevel@tonic-gate /*
957c478bd9Sstevel@tonic-gate  * A dictionary for doing BSD compress.
967c478bd9Sstevel@tonic-gate  */
977c478bd9Sstevel@tonic-gate struct bsd_db {
987c478bd9Sstevel@tonic-gate 	int		totlen;		/* length of this structure */
997c478bd9Sstevel@tonic-gate 	uint_t		hsize;		/* size of the hash table */
1007c478bd9Sstevel@tonic-gate 	uint32_t	unit;
1017c478bd9Sstevel@tonic-gate 	uchar_t		hshift;		/* used in hash function */
1027c478bd9Sstevel@tonic-gate 	uchar_t		n_bits;		/* current bits/code */
1037c478bd9Sstevel@tonic-gate 	uchar_t		maxbits;
1047c478bd9Sstevel@tonic-gate 	uchar_t		flags;
1057c478bd9Sstevel@tonic-gate 	ushort_t	seqno;		/* sequence number of next packet */
1067c478bd9Sstevel@tonic-gate 	ushort_t	mru;
1077c478bd9Sstevel@tonic-gate 	uint_t		hdrlen;		/* header length to preallocate */
1087c478bd9Sstevel@tonic-gate 	uint_t		maxmaxcode;	/* largest valid code */
1097c478bd9Sstevel@tonic-gate 	uint_t		max_ent;	/* largest code in use */
1107c478bd9Sstevel@tonic-gate 	uint_t		in_count;	/* uncompressed bytes, aged */
1117c478bd9Sstevel@tonic-gate 	uint_t		bytes_out;	/* compressed bytes, aged */
1127c478bd9Sstevel@tonic-gate 	uint_t		ratio;		/* recent compression ratio */
1137c478bd9Sstevel@tonic-gate 	uint_t		checkpoint;	/* when to next check the ratio */
1147c478bd9Sstevel@tonic-gate 	uint_t		clear_count;	/* times dictionary cleared */
1157c478bd9Sstevel@tonic-gate 	uint_t		incomp_count;	/* incompressible packets */
1167c478bd9Sstevel@tonic-gate 	uint_t		incomp_bytes;	/* incompressible bytes */
1177c478bd9Sstevel@tonic-gate 	uint_t		uncomp_count;	/* uncompressed packets */
1187c478bd9Sstevel@tonic-gate 	uint_t		uncomp_bytes;	/* uncompressed bytes */
1197c478bd9Sstevel@tonic-gate 	uint_t		comp_count;	/* compressed packets */
1207c478bd9Sstevel@tonic-gate 	uint_t		comp_bytes;	/* compressed bytes */
1217c478bd9Sstevel@tonic-gate 	ushort_t	*lens;		/* array of lengths of codes */
1227c478bd9Sstevel@tonic-gate 	struct bsd_dict {
1237c478bd9Sstevel@tonic-gate 	union {				/* hash value */
1247c478bd9Sstevel@tonic-gate 		uint32_t	fcode;
1257c478bd9Sstevel@tonic-gate 		struct {
1267c478bd9Sstevel@tonic-gate #ifdef BSD_LITTLE_ENDIAN
1277c478bd9Sstevel@tonic-gate 			ushort_t	prefix;	/* preceding code */
1287c478bd9Sstevel@tonic-gate 			uchar_t		suffix;	/* last character of new code */
1297c478bd9Sstevel@tonic-gate 			uchar_t		pad;
1307c478bd9Sstevel@tonic-gate #else
1317c478bd9Sstevel@tonic-gate 			uchar_t		pad;
1327c478bd9Sstevel@tonic-gate 			uchar_t		suffix;	/* last character of new code */
1337c478bd9Sstevel@tonic-gate 			ushort_t	prefix;	/* preceding code */
1347c478bd9Sstevel@tonic-gate #endif
1357c478bd9Sstevel@tonic-gate 		} hs;
1367c478bd9Sstevel@tonic-gate 	} f;
1377c478bd9Sstevel@tonic-gate 		ushort_t	codem1;		/* output of hash table -1 */
1387c478bd9Sstevel@tonic-gate 		ushort_t	cptr;		/* map code to hash entry */
1397c478bd9Sstevel@tonic-gate 	} dict[1];
1407c478bd9Sstevel@tonic-gate };
1417c478bd9Sstevel@tonic-gate 
1427c478bd9Sstevel@tonic-gate #define	BSD_OVHD	2		/* BSD compress overhead/packet */
1437c478bd9Sstevel@tonic-gate #define	BSD_INIT_BITS	BSD_MIN_BITS
1447c478bd9Sstevel@tonic-gate 
1457c478bd9Sstevel@tonic-gate /* db->flags values */
1467c478bd9Sstevel@tonic-gate #define	DS_DEBUG	0x01
1477c478bd9Sstevel@tonic-gate #define	DS_TESTIN	0x02
1487c478bd9Sstevel@tonic-gate #define	DS_TESTOUT	0x04
149*002c70ffScarlsonj #define	DS_INITDONE	0x08
1507c478bd9Sstevel@tonic-gate 
1517c478bd9Sstevel@tonic-gate static void	*bsd_comp_alloc(uchar_t *options, int opt_len);
1527c478bd9Sstevel@tonic-gate static void	*bsd_decomp_alloc(uchar_t *options, int opt_len);
1537c478bd9Sstevel@tonic-gate static void	bsd_free(void *state);
1547c478bd9Sstevel@tonic-gate static int	bsd_comp_init(void *state, uchar_t *options, int opt_len,
1557c478bd9Sstevel@tonic-gate 				int unit, int hdrlen, int debug);
1567c478bd9Sstevel@tonic-gate static int	bsd_decomp_init(void *state, uchar_t *options, int opt_len,
1577c478bd9Sstevel@tonic-gate 				int unit, int hdrlen, int mru, int debug);
1587c478bd9Sstevel@tonic-gate static int	bsd_compress(void *state, mblk_t **mret,
1597c478bd9Sstevel@tonic-gate 				mblk_t *mp, int slen, int maxolen);
1607c478bd9Sstevel@tonic-gate static int	bsd_incomp(void *state, mblk_t *dmsg);
1617c478bd9Sstevel@tonic-gate static int	bsd_decompress(void *state, mblk_t **dmpp);
1627c478bd9Sstevel@tonic-gate static void	bsd_reset(void *state);
1637c478bd9Sstevel@tonic-gate static void	bsd_comp_stats(void *state, struct compstat *stats);
1647c478bd9Sstevel@tonic-gate static int	bsd_set_effort(void *xarg, void *rarg, int effortlevel);
1657c478bd9Sstevel@tonic-gate 
1667c478bd9Sstevel@tonic-gate /*
1677c478bd9Sstevel@tonic-gate  * Procedures exported to ppp_comp.c.
1687c478bd9Sstevel@tonic-gate  */
1697c478bd9Sstevel@tonic-gate struct compressor ppp_bsd_compress = {
1707c478bd9Sstevel@tonic-gate 	CI_BSD_COMPRESS,		/* compress_proto */
1717c478bd9Sstevel@tonic-gate 	bsd_comp_alloc,			/* comp_alloc */
1727c478bd9Sstevel@tonic-gate 	bsd_free,			/* comp_free */
1737c478bd9Sstevel@tonic-gate 	bsd_comp_init,			/* comp_init */
1747c478bd9Sstevel@tonic-gate 	bsd_reset,			/* comp_reset */
1757c478bd9Sstevel@tonic-gate 	bsd_compress,			/* compress */
1767c478bd9Sstevel@tonic-gate 	bsd_comp_stats,			/* comp_stat */
1777c478bd9Sstevel@tonic-gate 	bsd_decomp_alloc,		/* decomp_alloc */
1787c478bd9Sstevel@tonic-gate 	bsd_free,			/* decomp_free */
1797c478bd9Sstevel@tonic-gate 	bsd_decomp_init,		/* decomp_init */
1807c478bd9Sstevel@tonic-gate 	bsd_reset,			/* decomp_reset */
1817c478bd9Sstevel@tonic-gate 	bsd_decompress,			/* decompress */
1827c478bd9Sstevel@tonic-gate 	bsd_incomp,			/* incomp */
1837c478bd9Sstevel@tonic-gate 	bsd_comp_stats,			/* decomp_stat */
1847c478bd9Sstevel@tonic-gate 	bsd_set_effort,			/* set_effort */
1857c478bd9Sstevel@tonic-gate };
1867c478bd9Sstevel@tonic-gate 
1877c478bd9Sstevel@tonic-gate /*
1887c478bd9Sstevel@tonic-gate  * the next two codes should not be changed lightly, as they must not
1897c478bd9Sstevel@tonic-gate  * lie within the contiguous general code space.
1907c478bd9Sstevel@tonic-gate  */
1917c478bd9Sstevel@tonic-gate #define	CLEAR		256		/* table clear output code */
1927c478bd9Sstevel@tonic-gate #define	FIRST		257		/* first free entry */
1937c478bd9Sstevel@tonic-gate #define	LAST		255
1947c478bd9Sstevel@tonic-gate 
1957c478bd9Sstevel@tonic-gate #define	MAXCODE(b)	((1 << (b)) - 1)
1967c478bd9Sstevel@tonic-gate #define	BADCODEM1	MAXCODE(BSD_MAX_BITS)
1977c478bd9Sstevel@tonic-gate 
1987c478bd9Sstevel@tonic-gate #define	BSD_HASH(prefix, suffix, hshift)	\
1997c478bd9Sstevel@tonic-gate 	((((uint32_t)(suffix)) << (hshift)) ^ (uint32_t)(prefix))
2007c478bd9Sstevel@tonic-gate 
2017c478bd9Sstevel@tonic-gate #define	BSD_KEY(prefix, suffix)		\
2027c478bd9Sstevel@tonic-gate 	((((uint32_t)(suffix)) << 16) + (uint32_t)(prefix))
2037c478bd9Sstevel@tonic-gate 
2047c478bd9Sstevel@tonic-gate #define	CHECK_GAP	10000		/* Ratio check interval */
2057c478bd9Sstevel@tonic-gate 
2067c478bd9Sstevel@tonic-gate #define	RATIO_SCALE_LOG	8
2077c478bd9Sstevel@tonic-gate #define	RATIO_SCALE	(1 << RATIO_SCALE_LOG)
2087c478bd9Sstevel@tonic-gate #define	RATIO_MAX	(0x7fffffff >> RATIO_SCALE_LOG)
2097c478bd9Sstevel@tonic-gate 
2107c478bd9Sstevel@tonic-gate #define	DECOMP_CHUNK	256
2117c478bd9Sstevel@tonic-gate 
2127c478bd9Sstevel@tonic-gate /*
2137c478bd9Sstevel@tonic-gate  * bsd_clear()
2147c478bd9Sstevel@tonic-gate  *
2157c478bd9Sstevel@tonic-gate  * clear the dictionary
2167c478bd9Sstevel@tonic-gate  */
2177c478bd9Sstevel@tonic-gate static void
bsd_clear(struct bsd_db * db)2187c478bd9Sstevel@tonic-gate bsd_clear(struct bsd_db *db)
2197c478bd9Sstevel@tonic-gate {
2207c478bd9Sstevel@tonic-gate 	db->clear_count++;
2217c478bd9Sstevel@tonic-gate 	db->max_ent = FIRST-1;
2227c478bd9Sstevel@tonic-gate 	db->n_bits = BSD_INIT_BITS;
2237c478bd9Sstevel@tonic-gate 	db->ratio = 0;
2247c478bd9Sstevel@tonic-gate 	db->bytes_out = 0;
2257c478bd9Sstevel@tonic-gate 	db->in_count = 0;
2267c478bd9Sstevel@tonic-gate 	db->checkpoint = CHECK_GAP;
2277c478bd9Sstevel@tonic-gate }
2287c478bd9Sstevel@tonic-gate 
2297c478bd9Sstevel@tonic-gate /*
2307c478bd9Sstevel@tonic-gate  * bsd_check()
2317c478bd9Sstevel@tonic-gate  *
2327c478bd9Sstevel@tonic-gate  * If the dictionary is full, then see if it is time to reset it.
2337c478bd9Sstevel@tonic-gate  *
2347c478bd9Sstevel@tonic-gate  * Compute the compression ratio using fixed-point arithmetic
2357c478bd9Sstevel@tonic-gate  * with 8 fractional bits.
2367c478bd9Sstevel@tonic-gate  *
2377c478bd9Sstevel@tonic-gate  * Since we have an infinite stream instead of a single file,
2387c478bd9Sstevel@tonic-gate  * watch only the local compression ratio.
2397c478bd9Sstevel@tonic-gate  *
2407c478bd9Sstevel@tonic-gate  * Since both peers must reset the dictionary at the same time even in
2417c478bd9Sstevel@tonic-gate  * the absence of CLEAR codes (while packets are incompressible), they
2427c478bd9Sstevel@tonic-gate  * must compute the same ratio.
2437c478bd9Sstevel@tonic-gate  */
2447c478bd9Sstevel@tonic-gate static int				/* 1=output CLEAR */
bsd_check(struct bsd_db * db)2457c478bd9Sstevel@tonic-gate bsd_check(struct bsd_db *db)
2467c478bd9Sstevel@tonic-gate {
2477c478bd9Sstevel@tonic-gate 	uint_t	new_ratio;
2487c478bd9Sstevel@tonic-gate 
2497c478bd9Sstevel@tonic-gate 	if (db->in_count >= db->checkpoint) {
2507c478bd9Sstevel@tonic-gate 
2517c478bd9Sstevel@tonic-gate 		/*
2527c478bd9Sstevel@tonic-gate 		 * age the ratio by limiting the size of the counts
2537c478bd9Sstevel@tonic-gate 		 */
2547c478bd9Sstevel@tonic-gate 		if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX) {
2557c478bd9Sstevel@tonic-gate 			db->in_count -= db->in_count/4;
2567c478bd9Sstevel@tonic-gate 			db->bytes_out -= db->bytes_out/4;
2577c478bd9Sstevel@tonic-gate 		}
2587c478bd9Sstevel@tonic-gate 
2597c478bd9Sstevel@tonic-gate 		db->checkpoint = db->in_count + CHECK_GAP;
2607c478bd9Sstevel@tonic-gate 
2617c478bd9Sstevel@tonic-gate 		if (db->max_ent >= db->maxmaxcode) {
2627c478bd9Sstevel@tonic-gate 
2637c478bd9Sstevel@tonic-gate 			/*
2647c478bd9Sstevel@tonic-gate 			 * Reset the dictionary only if the ratio is worse,
2657c478bd9Sstevel@tonic-gate 			 * or if it looks as if it has been poisoned
2667c478bd9Sstevel@tonic-gate 			 * by incompressible data.
2677c478bd9Sstevel@tonic-gate 			 *
2687c478bd9Sstevel@tonic-gate 			 * This does not overflow, because
2697c478bd9Sstevel@tonic-gate 			 * db->in_count <= RATIO_MAX.
2707c478bd9Sstevel@tonic-gate 			 */
2717c478bd9Sstevel@tonic-gate 			new_ratio = db->in_count << RATIO_SCALE_LOG;
2727c478bd9Sstevel@tonic-gate 
2737c478bd9Sstevel@tonic-gate 			if (db->bytes_out != 0) {
2747c478bd9Sstevel@tonic-gate 				new_ratio /= db->bytes_out;
2757c478bd9Sstevel@tonic-gate 			}
2767c478bd9Sstevel@tonic-gate 
2777c478bd9Sstevel@tonic-gate 			if (new_ratio < db->ratio ||
278*002c70ffScarlsonj 			    new_ratio < 1 * RATIO_SCALE) {
2797c478bd9Sstevel@tonic-gate 				bsd_clear(db);
2807c478bd9Sstevel@tonic-gate 				return (1);
2817c478bd9Sstevel@tonic-gate 			}
2827c478bd9Sstevel@tonic-gate 
2837c478bd9Sstevel@tonic-gate 			db->ratio = new_ratio;
2847c478bd9Sstevel@tonic-gate 		}
2857c478bd9Sstevel@tonic-gate 	}
2867c478bd9Sstevel@tonic-gate 
2877c478bd9Sstevel@tonic-gate 	return (0);
2887c478bd9Sstevel@tonic-gate }
2897c478bd9Sstevel@tonic-gate 
2907c478bd9Sstevel@tonic-gate /*
2917c478bd9Sstevel@tonic-gate  * bsd_comp_stats()
2927c478bd9Sstevel@tonic-gate  *
2937c478bd9Sstevel@tonic-gate  * Return statistics.
2947c478bd9Sstevel@tonic-gate  */
2957c478bd9Sstevel@tonic-gate static void
bsd_comp_stats(void * state,struct compstat * stats)2967c478bd9Sstevel@tonic-gate bsd_comp_stats(void *state, struct compstat *stats)
2977c478bd9Sstevel@tonic-gate {
2987c478bd9Sstevel@tonic-gate 	struct bsd_db	*db = (struct bsd_db *)state;
2997c478bd9Sstevel@tonic-gate 	uint_t		out;
3007c478bd9Sstevel@tonic-gate 
3017c478bd9Sstevel@tonic-gate 	stats->unc_bytes = db->uncomp_bytes;
3027c478bd9Sstevel@tonic-gate 	stats->unc_packets = db->uncomp_count;
3037c478bd9Sstevel@tonic-gate 	stats->comp_bytes = db->comp_bytes;
3047c478bd9Sstevel@tonic-gate 	stats->comp_packets = db->comp_count;
3057c478bd9Sstevel@tonic-gate 	stats->inc_bytes = db->incomp_bytes;
3067c478bd9Sstevel@tonic-gate 	stats->inc_packets = db->incomp_count;
3077c478bd9Sstevel@tonic-gate 	stats->ratio = db->in_count;
3087c478bd9Sstevel@tonic-gate 
3097c478bd9Sstevel@tonic-gate 	out = db->bytes_out;
3107c478bd9Sstevel@tonic-gate 
3117c478bd9Sstevel@tonic-gate 	if (stats->ratio <= 0x7fffff) {
3127c478bd9Sstevel@tonic-gate 		stats->ratio <<= 8;
3137c478bd9Sstevel@tonic-gate 	} else {
3147c478bd9Sstevel@tonic-gate 		out >>= 8;
3157c478bd9Sstevel@tonic-gate 	}
3167c478bd9Sstevel@tonic-gate 
3177c478bd9Sstevel@tonic-gate 	if (out != 0) {
3187c478bd9Sstevel@tonic-gate 		stats->ratio /= out;
3197c478bd9Sstevel@tonic-gate 	}
3207c478bd9Sstevel@tonic-gate }
3217c478bd9Sstevel@tonic-gate 
3227c478bd9Sstevel@tonic-gate /*
3237c478bd9Sstevel@tonic-gate  * bsd_reset()
3247c478bd9Sstevel@tonic-gate  *
3257c478bd9Sstevel@tonic-gate  * Reset state, as on a CCP ResetReq.
3267c478bd9Sstevel@tonic-gate  */
3277c478bd9Sstevel@tonic-gate static void
bsd_reset(void * state)3287c478bd9Sstevel@tonic-gate bsd_reset(void *state)
3297c478bd9Sstevel@tonic-gate {
3307c478bd9Sstevel@tonic-gate 	struct bsd_db	*db = (struct bsd_db *)state;
3317c478bd9Sstevel@tonic-gate 
3327c478bd9Sstevel@tonic-gate 	if (db->hsize != 0) {
3337c478bd9Sstevel@tonic-gate 		db->seqno = 0;
3347c478bd9Sstevel@tonic-gate 
3357c478bd9Sstevel@tonic-gate 		bsd_clear(db);
3367c478bd9Sstevel@tonic-gate 
3377c478bd9Sstevel@tonic-gate 		db->clear_count = 0;
3387c478bd9Sstevel@tonic-gate 	}
3397c478bd9Sstevel@tonic-gate }
3407c478bd9Sstevel@tonic-gate 
3417c478bd9Sstevel@tonic-gate /*
3427c478bd9Sstevel@tonic-gate  * bsd_alloc()
3437c478bd9Sstevel@tonic-gate  *
3447c478bd9Sstevel@tonic-gate  * Allocate space for a (de) compressor.
3457c478bd9Sstevel@tonic-gate  */
3467c478bd9Sstevel@tonic-gate static void *
bsd_alloc(uchar_t * options,int opt_len,int decomp)3477c478bd9Sstevel@tonic-gate bsd_alloc(uchar_t *options, int opt_len, int decomp)
3487c478bd9Sstevel@tonic-gate {
3497c478bd9Sstevel@tonic-gate 	int		bits;
3507c478bd9Sstevel@tonic-gate 	uint_t		newlen;
3517c478bd9Sstevel@tonic-gate 	uint_t		hsize;
3527c478bd9Sstevel@tonic-gate 	uint_t		hshift;
3537c478bd9Sstevel@tonic-gate 	uint_t		maxmaxcode;
3547c478bd9Sstevel@tonic-gate 	uint_t		ilen;
3557c478bd9Sstevel@tonic-gate 	struct bsd_db	*db;
3567c478bd9Sstevel@tonic-gate 
3577c478bd9Sstevel@tonic-gate 	if (opt_len != 3 ||
358*002c70ffScarlsonj 	    options[0] != CI_BSD_COMPRESS ||
359*002c70ffScarlsonj 	    options[1] != 3 ||
360*002c70ffScarlsonj 	    BSD_VERSION(options[2]) != BSD_CURRENT_VERSION) {
3617c478bd9Sstevel@tonic-gate 
3627c478bd9Sstevel@tonic-gate 		return (NULL);
3637c478bd9Sstevel@tonic-gate 	}
3647c478bd9Sstevel@tonic-gate 
3657c478bd9Sstevel@tonic-gate 	bits = BSD_NBITS(options[2]);
3667c478bd9Sstevel@tonic-gate 
3677c478bd9Sstevel@tonic-gate 	switch (bits) {
3687c478bd9Sstevel@tonic-gate 
3697c478bd9Sstevel@tonic-gate 	case 9:				/* needs 82152 for both directions */
3707c478bd9Sstevel@tonic-gate 	case 10:			/* needs 84144 */
3717c478bd9Sstevel@tonic-gate 	case 11:			/* needs 88240 */
3727c478bd9Sstevel@tonic-gate 	case 12:			/* needs 96432 */
3737c478bd9Sstevel@tonic-gate 
3747c478bd9Sstevel@tonic-gate 		hsize = 5003;
3757c478bd9Sstevel@tonic-gate 		hshift = 4;
3767c478bd9Sstevel@tonic-gate 
3777c478bd9Sstevel@tonic-gate 		break;
3787c478bd9Sstevel@tonic-gate 
3797c478bd9Sstevel@tonic-gate 	case 13:			/* needs 176784 */
3807c478bd9Sstevel@tonic-gate 
3817c478bd9Sstevel@tonic-gate 		hsize = 9001;
3827c478bd9Sstevel@tonic-gate 		hshift = 5;
3837c478bd9Sstevel@tonic-gate 
3847c478bd9Sstevel@tonic-gate 		break;
3857c478bd9Sstevel@tonic-gate 
3867c478bd9Sstevel@tonic-gate 	case 14:			/* needs 353744 */
3877c478bd9Sstevel@tonic-gate 
3887c478bd9Sstevel@tonic-gate 		hsize = 18013;
3897c478bd9Sstevel@tonic-gate 		hshift = 6;
3907c478bd9Sstevel@tonic-gate 
3917c478bd9Sstevel@tonic-gate 		break;
3927c478bd9Sstevel@tonic-gate 
3937c478bd9Sstevel@tonic-gate 	case 15:			/* needs 691440 */
3947c478bd9Sstevel@tonic-gate 
3957c478bd9Sstevel@tonic-gate 		hsize = 35023;
3967c478bd9Sstevel@tonic-gate 		hshift = 7;
3977c478bd9Sstevel@tonic-gate 
3987c478bd9Sstevel@tonic-gate 		break;
3997c478bd9Sstevel@tonic-gate 
4007c478bd9Sstevel@tonic-gate 	/* XXX: this falls thru - it was originally commented */
4017c478bd9Sstevel@tonic-gate 	case 16:			/* needs 1366160--far too much, */
4027c478bd9Sstevel@tonic-gate 		/* hsize = 69001; */	/* and 69001 is too big for cptr */
4037c478bd9Sstevel@tonic-gate 		/* hshift = 8; */	/* in struct bsd_db */
4047c478bd9Sstevel@tonic-gate 		/* break; */
4057c478bd9Sstevel@tonic-gate 
4067c478bd9Sstevel@tonic-gate 	default:
4077c478bd9Sstevel@tonic-gate 
4087c478bd9Sstevel@tonic-gate 		return (NULL);
4097c478bd9Sstevel@tonic-gate 	}
4107c478bd9Sstevel@tonic-gate 
4117c478bd9Sstevel@tonic-gate 	maxmaxcode = MAXCODE(bits);
4127c478bd9Sstevel@tonic-gate 	ilen = newlen = sizeof (*db) + (hsize-1) * sizeof (db->dict[0]);
4137c478bd9Sstevel@tonic-gate 	if (decomp)
4147c478bd9Sstevel@tonic-gate 		newlen += (maxmaxcode+1) * sizeof (db->lens[0]);
4157c478bd9Sstevel@tonic-gate 	db = (struct bsd_db *)kmem_alloc(newlen, KM_NOSLEEP);
4167c478bd9Sstevel@tonic-gate 	if (!db) {
4177c478bd9Sstevel@tonic-gate 		return (NULL);
4187c478bd9Sstevel@tonic-gate 	}
4197c478bd9Sstevel@tonic-gate 
4207c478bd9Sstevel@tonic-gate 	bzero(db, sizeof (*db) - sizeof (db->dict));
4217c478bd9Sstevel@tonic-gate 
4227c478bd9Sstevel@tonic-gate 	if (!decomp) {
4237c478bd9Sstevel@tonic-gate 		db->lens = NULL;
4247c478bd9Sstevel@tonic-gate 	} else {
4257c478bd9Sstevel@tonic-gate 		db->lens = (ushort_t *)((caddr_t)db + ilen);
4267c478bd9Sstevel@tonic-gate 	}
4277c478bd9Sstevel@tonic-gate 
4287c478bd9Sstevel@tonic-gate 	db->totlen = newlen;
4297c478bd9Sstevel@tonic-gate 	db->hsize = hsize;
4307c478bd9Sstevel@tonic-gate 	db->hshift = (uchar_t)hshift;
4317c478bd9Sstevel@tonic-gate 	db->maxmaxcode = maxmaxcode;
4327c478bd9Sstevel@tonic-gate 	db->maxbits = (uchar_t)bits;
4337c478bd9Sstevel@tonic-gate 
4347c478bd9Sstevel@tonic-gate 	return ((void *)db);
4357c478bd9Sstevel@tonic-gate }
4367c478bd9Sstevel@tonic-gate 
4377c478bd9Sstevel@tonic-gate /*
4387c478bd9Sstevel@tonic-gate  * bsd_free()
4397c478bd9Sstevel@tonic-gate  */
4407c478bd9Sstevel@tonic-gate static void
bsd_free(void * state)4417c478bd9Sstevel@tonic-gate bsd_free(void *state)
4427c478bd9Sstevel@tonic-gate {
4437c478bd9Sstevel@tonic-gate 	struct bsd_db	*db = (struct bsd_db *)state;
4447c478bd9Sstevel@tonic-gate 
4457c478bd9Sstevel@tonic-gate 	if (db->hsize != 0) {
4467c478bd9Sstevel@tonic-gate 		/* XXX feeble attempt to catch bad references. */
4477c478bd9Sstevel@tonic-gate 		db->hsize = 0;
4487c478bd9Sstevel@tonic-gate 
4497c478bd9Sstevel@tonic-gate 		kmem_free(db, db->totlen);
4507c478bd9Sstevel@tonic-gate 	}
4517c478bd9Sstevel@tonic-gate }
4527c478bd9Sstevel@tonic-gate 
4537c478bd9Sstevel@tonic-gate /*
4547c478bd9Sstevel@tonic-gate  * bsd_comp_alloc()
4557c478bd9Sstevel@tonic-gate  */
4567c478bd9Sstevel@tonic-gate static void *
bsd_comp_alloc(uchar_t * options,int opt_len)4577c478bd9Sstevel@tonic-gate bsd_comp_alloc(uchar_t *options, int opt_len)
4587c478bd9Sstevel@tonic-gate {
4597c478bd9Sstevel@tonic-gate 	return (bsd_alloc(options, opt_len, 0));
4607c478bd9Sstevel@tonic-gate }
4617c478bd9Sstevel@tonic-gate 
4627c478bd9Sstevel@tonic-gate /*
4637c478bd9Sstevel@tonic-gate  * bsd_decomp_alloc()
4647c478bd9Sstevel@tonic-gate  */
4657c478bd9Sstevel@tonic-gate static void *
bsd_decomp_alloc(uchar_t * options,int opt_len)4667c478bd9Sstevel@tonic-gate bsd_decomp_alloc(uchar_t *options, int opt_len)
4677c478bd9Sstevel@tonic-gate {
4687c478bd9Sstevel@tonic-gate 	return (bsd_alloc(options, opt_len, 1));
4697c478bd9Sstevel@tonic-gate }
4707c478bd9Sstevel@tonic-gate 
4717c478bd9Sstevel@tonic-gate /*
4727c478bd9Sstevel@tonic-gate  * bsd_init()
4737c478bd9Sstevel@tonic-gate  *
4747c478bd9Sstevel@tonic-gate  * Initialize the database.
4757c478bd9Sstevel@tonic-gate  */
4767c478bd9Sstevel@tonic-gate static int
bsd_init(struct bsd_db * db,uchar_t * options,int opt_len,int unit,int hdrlen,int mru,int debug,int decomp)4777c478bd9Sstevel@tonic-gate bsd_init(struct bsd_db *db, uchar_t *options, int opt_len, int unit,
4787c478bd9Sstevel@tonic-gate 	int hdrlen, int mru, int debug, int decomp)
4797c478bd9Sstevel@tonic-gate {
4807c478bd9Sstevel@tonic-gate 	int	i;
4817c478bd9Sstevel@tonic-gate 
4827c478bd9Sstevel@tonic-gate 	if (db->hsize == 0 || opt_len < CILEN_BSD_COMPRESS ||
483*002c70ffScarlsonj 	    options[0] != CI_BSD_COMPRESS ||
484*002c70ffScarlsonj 	    options[1] != CILEN_BSD_COMPRESS ||
485*002c70ffScarlsonj 	    BSD_VERSION(options[2]) != BSD_CURRENT_VERSION ||
486*002c70ffScarlsonj 	    BSD_NBITS(options[2]) != db->maxbits ||
487*002c70ffScarlsonj 	    decomp && db->lens == NULL) {
4887c478bd9Sstevel@tonic-gate 
4897c478bd9Sstevel@tonic-gate 		return (0);
4907c478bd9Sstevel@tonic-gate 	}
4917c478bd9Sstevel@tonic-gate 
4927c478bd9Sstevel@tonic-gate 	if (decomp) {
4937c478bd9Sstevel@tonic-gate 		i = LAST + 1;
4947c478bd9Sstevel@tonic-gate 
4957c478bd9Sstevel@tonic-gate 		while (i != 0) {
4967c478bd9Sstevel@tonic-gate 			db->lens[--i] = 1;
4977c478bd9Sstevel@tonic-gate 		}
4987c478bd9Sstevel@tonic-gate 	}
4997c478bd9Sstevel@tonic-gate 
5007c478bd9Sstevel@tonic-gate 	i = db->hsize;
5017c478bd9Sstevel@tonic-gate 
5027c478bd9Sstevel@tonic-gate 	while (i != 0) {
5037c478bd9Sstevel@tonic-gate 		db->dict[--i].codem1 = BADCODEM1;
5047c478bd9Sstevel@tonic-gate 		db->dict[i].cptr = 0;
5057c478bd9Sstevel@tonic-gate 	}
5067c478bd9Sstevel@tonic-gate 
5077c478bd9Sstevel@tonic-gate 	db->unit = unit;
5087c478bd9Sstevel@tonic-gate 	db->hdrlen = hdrlen;
5097c478bd9Sstevel@tonic-gate 	db->mru = (ushort_t)mru;
5107c478bd9Sstevel@tonic-gate 
5117c478bd9Sstevel@tonic-gate 	if (debug) {
5127c478bd9Sstevel@tonic-gate 		db->flags |= DS_DEBUG;
5137c478bd9Sstevel@tonic-gate 	}
5147c478bd9Sstevel@tonic-gate 
5157c478bd9Sstevel@tonic-gate 	bsd_reset(db);
5167c478bd9Sstevel@tonic-gate 
517*002c70ffScarlsonj 	db->flags |= DS_INITDONE;
518*002c70ffScarlsonj 
5197c478bd9Sstevel@tonic-gate 	return (1);
5207c478bd9Sstevel@tonic-gate }
5217c478bd9Sstevel@tonic-gate 
5227c478bd9Sstevel@tonic-gate /*
5237c478bd9Sstevel@tonic-gate  * bsd_comp_init()
5247c478bd9Sstevel@tonic-gate  */
5257c478bd9Sstevel@tonic-gate static int
bsd_comp_init(void * state,uchar_t * options,int opt_len,int unit,int hdrlen,int debug)5267c478bd9Sstevel@tonic-gate bsd_comp_init(void *state, uchar_t *options, int opt_len, int unit, int hdrlen,
5277c478bd9Sstevel@tonic-gate 	int debug)
5287c478bd9Sstevel@tonic-gate {
5297c478bd9Sstevel@tonic-gate 	return (bsd_init((struct bsd_db *)state, options, opt_len,
530*002c70ffScarlsonj 	    unit, hdrlen, 0, debug, 0));
5317c478bd9Sstevel@tonic-gate }
5327c478bd9Sstevel@tonic-gate 
5337c478bd9Sstevel@tonic-gate /*
5347c478bd9Sstevel@tonic-gate  * bsd_decomp_init()
5357c478bd9Sstevel@tonic-gate  */
5367c478bd9Sstevel@tonic-gate static int
bsd_decomp_init(void * state,uchar_t * options,int opt_len,int unit,int hdrlen,int mru,int debug)5377c478bd9Sstevel@tonic-gate bsd_decomp_init(void *state, uchar_t *options, int opt_len, int unit,
5387c478bd9Sstevel@tonic-gate 	int hdrlen, int mru, int debug)
5397c478bd9Sstevel@tonic-gate {
5407c478bd9Sstevel@tonic-gate 	return (bsd_init((struct bsd_db *)state, options, opt_len,
541*002c70ffScarlsonj 	    unit, hdrlen, mru, debug, 1));
5427c478bd9Sstevel@tonic-gate }
5437c478bd9Sstevel@tonic-gate 
5447c478bd9Sstevel@tonic-gate 
5457c478bd9Sstevel@tonic-gate /*
5467c478bd9Sstevel@tonic-gate  * bsd_compress()
5477c478bd9Sstevel@tonic-gate  *
5487c478bd9Sstevel@tonic-gate  * compress a packet
5497c478bd9Sstevel@tonic-gate  *	One change from the BSD compress command is that when the
5507c478bd9Sstevel@tonic-gate  *	code size expands, we do not output a bunch of padding.
5517c478bd9Sstevel@tonic-gate  *
5527c478bd9Sstevel@tonic-gate  * N.B. at present, we ignore the hdrlen specified in the comp_init call.
5537c478bd9Sstevel@tonic-gate  */
5547c478bd9Sstevel@tonic-gate static int			/* new slen */
bsd_compress(void * state,mblk_t ** mretp,mblk_t * mp,int slen,int maxolen)5557c478bd9Sstevel@tonic-gate bsd_compress(void *state, mblk_t **mretp, mblk_t *mp, int slen,	int maxolen)
5567c478bd9Sstevel@tonic-gate {
5577c478bd9Sstevel@tonic-gate 	struct bsd_db	*db = (struct bsd_db *)state;
5587c478bd9Sstevel@tonic-gate 	int		hshift = db->hshift;
5597c478bd9Sstevel@tonic-gate 	uint_t		max_ent = db->max_ent;
5607c478bd9Sstevel@tonic-gate 	uint_t		n_bits = db->n_bits;
5617c478bd9Sstevel@tonic-gate 	uint_t		bitno = 32;
5627c478bd9Sstevel@tonic-gate 	uint32_t	accm = 0;
5637c478bd9Sstevel@tonic-gate 	uint32_t	fcode;
5647c478bd9Sstevel@tonic-gate 	struct bsd_dict	*dictp;
5657c478bd9Sstevel@tonic-gate 	uchar_t		c;
5667c478bd9Sstevel@tonic-gate 	int		hval;
5677c478bd9Sstevel@tonic-gate 	int		disp;
5687c478bd9Sstevel@tonic-gate 	int		ent;
5697c478bd9Sstevel@tonic-gate 	int		ilen = slen - (PPP_HDRLEN-1);
5707c478bd9Sstevel@tonic-gate 	mblk_t		*mret;
5717c478bd9Sstevel@tonic-gate 	uchar_t		*rptr, *rmax;
5727c478bd9Sstevel@tonic-gate 	uchar_t		*wptr;
5737c478bd9Sstevel@tonic-gate 	uchar_t		*cp_end;
5747c478bd9Sstevel@tonic-gate 	int		olen;
5757c478bd9Sstevel@tonic-gate 	mblk_t		*m;
5767c478bd9Sstevel@tonic-gate 	mblk_t		**mnp;
5777c478bd9Sstevel@tonic-gate #if defined(lint) || defined(_lint)
5787c478bd9Sstevel@tonic-gate 	uchar_t		hdlcaddr, hdlcctl;
5797c478bd9Sstevel@tonic-gate #else
5807c478bd9Sstevel@tonic-gate 	int		hdlcaddr, hdlcctl;
5817c478bd9Sstevel@tonic-gate #endif
5827c478bd9Sstevel@tonic-gate 
583*002c70ffScarlsonj 	ASSERT(db->flags & DS_INITDONE);
584*002c70ffScarlsonj 
5857c478bd9Sstevel@tonic-gate #define	PUTBYTE(v) {						\
5867c478bd9Sstevel@tonic-gate 	if (wptr) {						\
5877c478bd9Sstevel@tonic-gate 		*wptr++ = (v);					\
5887c478bd9Sstevel@tonic-gate 		if (wptr >= cp_end) {				\
5897c478bd9Sstevel@tonic-gate 			m->b_wptr = wptr;			\
5907c478bd9Sstevel@tonic-gate 			m = m->b_cont;				\
5917c478bd9Sstevel@tonic-gate 			if (m) {				\
5927c478bd9Sstevel@tonic-gate 				wptr = m->b_wptr;		\
5937c478bd9Sstevel@tonic-gate 				cp_end = m->b_datap->db_lim;	\
5947c478bd9Sstevel@tonic-gate 			} else {				\
5957c478bd9Sstevel@tonic-gate 				wptr = NULL;			\
5967c478bd9Sstevel@tonic-gate 			}					\
5977c478bd9Sstevel@tonic-gate 		}						\
5987c478bd9Sstevel@tonic-gate 	}							\
5997c478bd9Sstevel@tonic-gate 	++olen;							\
6007c478bd9Sstevel@tonic-gate }
6017c478bd9Sstevel@tonic-gate 
6027c478bd9Sstevel@tonic-gate #define	OUTPUT(ent) {						\
6037c478bd9Sstevel@tonic-gate 	bitno -= n_bits;					\
6047c478bd9Sstevel@tonic-gate 	accm |= ((ent) << bitno);				\
6057c478bd9Sstevel@tonic-gate 	do {							\
6067c478bd9Sstevel@tonic-gate 		PUTBYTE(accm >> 24);				\
6077c478bd9Sstevel@tonic-gate 		accm <<= 8;					\
6087c478bd9Sstevel@tonic-gate 		bitno += 8;					\
6097c478bd9Sstevel@tonic-gate 	} while (bitno <= 24);					\
6107c478bd9Sstevel@tonic-gate }
6117c478bd9Sstevel@tonic-gate 
6127c478bd9Sstevel@tonic-gate #define	ADJRPTR() {						\
6137c478bd9Sstevel@tonic-gate 	if (rptr != NULL) {					\
6147c478bd9Sstevel@tonic-gate 		while (rptr >= rmax) {				\
6157c478bd9Sstevel@tonic-gate 			if ((mp = mp->b_cont) == NULL) {	\
6167c478bd9Sstevel@tonic-gate 				rptr = NULL;			\
6177c478bd9Sstevel@tonic-gate 				break;				\
6187c478bd9Sstevel@tonic-gate 			}					\
6197c478bd9Sstevel@tonic-gate 			rptr = mp->b_rptr;			\
6207c478bd9Sstevel@tonic-gate 			rmax = mp->b_wptr;			\
6217c478bd9Sstevel@tonic-gate 		}						\
6227c478bd9Sstevel@tonic-gate 	}							\
6237c478bd9Sstevel@tonic-gate }
6247c478bd9Sstevel@tonic-gate 
6257c478bd9Sstevel@tonic-gate #define	GETBYTE(v) {						\
6267c478bd9Sstevel@tonic-gate 	if (rptr != NULL) {					\
6277c478bd9Sstevel@tonic-gate 		(v) = *rptr++;					\
6287c478bd9Sstevel@tonic-gate 	}							\
6297c478bd9Sstevel@tonic-gate }
6307c478bd9Sstevel@tonic-gate 
6317c478bd9Sstevel@tonic-gate 	if (db->hsize == 0)
6327c478bd9Sstevel@tonic-gate 		return (-1);
6337c478bd9Sstevel@tonic-gate 
6347c478bd9Sstevel@tonic-gate 	/*
6357c478bd9Sstevel@tonic-gate 	 * First get the protocol and check that we're
6367c478bd9Sstevel@tonic-gate 	 * interested in this packet.
6377c478bd9Sstevel@tonic-gate 	 */
6387c478bd9Sstevel@tonic-gate 	*mretp = NULL;
6397c478bd9Sstevel@tonic-gate 	rptr = mp->b_rptr;
6407c478bd9Sstevel@tonic-gate 	rmax = mp->b_wptr;
6417c478bd9Sstevel@tonic-gate 
6427c478bd9Sstevel@tonic-gate 	/* We CANNOT do a pullup here; it's not our buffer to toy with. */
6437c478bd9Sstevel@tonic-gate 	ADJRPTR();
6447c478bd9Sstevel@tonic-gate 	GETBYTE(hdlcaddr);
6457c478bd9Sstevel@tonic-gate 	ADJRPTR();
6467c478bd9Sstevel@tonic-gate 	GETBYTE(hdlcctl);
6477c478bd9Sstevel@tonic-gate 	ADJRPTR();
6487c478bd9Sstevel@tonic-gate 	GETBYTE(ent);
6497c478bd9Sstevel@tonic-gate 	ADJRPTR();
6507c478bd9Sstevel@tonic-gate 
6517c478bd9Sstevel@tonic-gate 	/*
6527c478bd9Sstevel@tonic-gate 	 * Per RFC 1977, the protocol field must be compressed using a
6537c478bd9Sstevel@tonic-gate 	 * PFC-like procedure.  Also, all protocols between 0000-3FFF
6547c478bd9Sstevel@tonic-gate 	 * except the two compression protocols must be LZ compressed.
6557c478bd9Sstevel@tonic-gate 	 */
6567c478bd9Sstevel@tonic-gate 	if (ent == 0) {
6577c478bd9Sstevel@tonic-gate 		GETBYTE(ent);
6587c478bd9Sstevel@tonic-gate 		if (rptr == NULL || ent == PPP_COMP || ent == PPP_COMPFRAG)
6597c478bd9Sstevel@tonic-gate 			return (0);
6607c478bd9Sstevel@tonic-gate 	} else {
6617c478bd9Sstevel@tonic-gate 		if (ent > 0x3F)
6627c478bd9Sstevel@tonic-gate 			return (0);
6637c478bd9Sstevel@tonic-gate 		ilen++;
6647c478bd9Sstevel@tonic-gate 	}
6657c478bd9Sstevel@tonic-gate 
6667c478bd9Sstevel@tonic-gate 	/*
6677c478bd9Sstevel@tonic-gate 	 * Don't generate compressed packets that are larger than the
6687c478bd9Sstevel@tonic-gate 	 * source (uncompressed) packet.
6697c478bd9Sstevel@tonic-gate 	 */
6707c478bd9Sstevel@tonic-gate 	if (maxolen > slen) {
6717c478bd9Sstevel@tonic-gate 		maxolen = slen;
6727c478bd9Sstevel@tonic-gate 	}
6737c478bd9Sstevel@tonic-gate 	if (maxolen < 6)
6747c478bd9Sstevel@tonic-gate 		maxolen = 6;
6757c478bd9Sstevel@tonic-gate 
6767c478bd9Sstevel@tonic-gate 	/*
6777c478bd9Sstevel@tonic-gate 	 * Allocate enough message blocks to give maxolen total space
6787c478bd9Sstevel@tonic-gate 	 */
6797c478bd9Sstevel@tonic-gate 	mnp = &mret;
6807c478bd9Sstevel@tonic-gate 	for (olen = maxolen; olen > 0; ) {
6817c478bd9Sstevel@tonic-gate 
6827c478bd9Sstevel@tonic-gate 		m = allocb((olen < 4096? olen: 4096), BPRI_MED);
6837c478bd9Sstevel@tonic-gate 
6847c478bd9Sstevel@tonic-gate 		*mnp = m;
6857c478bd9Sstevel@tonic-gate 		if (m == NULL) {
6867c478bd9Sstevel@tonic-gate 			if (mnp == &mret)
6877c478bd9Sstevel@tonic-gate 				return (0);
6887c478bd9Sstevel@tonic-gate 			/* We allocated some; hope for the best. */
6897c478bd9Sstevel@tonic-gate 			break;
6907c478bd9Sstevel@tonic-gate 		}
6917c478bd9Sstevel@tonic-gate 
6927c478bd9Sstevel@tonic-gate 		mnp = &m->b_cont;
6937c478bd9Sstevel@tonic-gate 		olen -= m->b_datap->db_lim - m->b_wptr;
6947c478bd9Sstevel@tonic-gate 	}
6957c478bd9Sstevel@tonic-gate 
6967c478bd9Sstevel@tonic-gate 	*mnp = NULL;
6977c478bd9Sstevel@tonic-gate 
6987c478bd9Sstevel@tonic-gate 	m = mret;
6997c478bd9Sstevel@tonic-gate 	wptr = m->b_wptr;
7007c478bd9Sstevel@tonic-gate 	cp_end = m->b_datap->db_lim;
7017c478bd9Sstevel@tonic-gate 
7027c478bd9Sstevel@tonic-gate 	olen = 0;
7037c478bd9Sstevel@tonic-gate 
7047c478bd9Sstevel@tonic-gate 	/*
7057c478bd9Sstevel@tonic-gate 	 * Copy the PPP header over, changing the protocol,
7067c478bd9Sstevel@tonic-gate 	 * and install the 2-byte sequence number
7077c478bd9Sstevel@tonic-gate 	 */
7087c478bd9Sstevel@tonic-gate 	*wptr++ = hdlcaddr;
7097c478bd9Sstevel@tonic-gate 	*wptr++ = hdlcctl;
7107c478bd9Sstevel@tonic-gate 	*wptr++ = PPP_COMP>>8;		/* change the protocol */
7117c478bd9Sstevel@tonic-gate 	*wptr++ = PPP_COMP;
7127c478bd9Sstevel@tonic-gate 	*wptr++ = db->seqno >> 8;
7137c478bd9Sstevel@tonic-gate 	*wptr++ = db->seqno;
7147c478bd9Sstevel@tonic-gate 
7157c478bd9Sstevel@tonic-gate #ifdef DEBUG
7167c478bd9Sstevel@tonic-gate 	/*
7177c478bd9Sstevel@tonic-gate 	 * If testing output, just garbling the sequence here does the
7187c478bd9Sstevel@tonic-gate 	 * trick.
7197c478bd9Sstevel@tonic-gate 	 */
7207c478bd9Sstevel@tonic-gate 	if ((db->flags & DS_TESTOUT) && (db->seqno % 100) == 50)
7217c478bd9Sstevel@tonic-gate 		wptr[-1] ^= 0xAA;
7227c478bd9Sstevel@tonic-gate #endif
7237c478bd9Sstevel@tonic-gate 
7247c478bd9Sstevel@tonic-gate 	++db->seqno;
7257c478bd9Sstevel@tonic-gate 
7267c478bd9Sstevel@tonic-gate 	for (;;) {
7277c478bd9Sstevel@tonic-gate 		ADJRPTR();
7287c478bd9Sstevel@tonic-gate 		if (rptr == NULL)
7297c478bd9Sstevel@tonic-gate 			break;
7307c478bd9Sstevel@tonic-gate 
7317c478bd9Sstevel@tonic-gate 		GETBYTE(c);
7327c478bd9Sstevel@tonic-gate 
7337c478bd9Sstevel@tonic-gate 		fcode = BSD_KEY(ent, c);
7347c478bd9Sstevel@tonic-gate 		hval = BSD_HASH(ent, c, hshift);
7357c478bd9Sstevel@tonic-gate 
7367c478bd9Sstevel@tonic-gate 		dictp = &db->dict[hval];
7377c478bd9Sstevel@tonic-gate 
7387c478bd9Sstevel@tonic-gate 		/*
7397c478bd9Sstevel@tonic-gate 		 * Validate and then check the entry
7407c478bd9Sstevel@tonic-gate 		 */
7417c478bd9Sstevel@tonic-gate 		if (dictp->codem1 >= max_ent) {
7427c478bd9Sstevel@tonic-gate 			goto nomatch;
7437c478bd9Sstevel@tonic-gate 		}
7447c478bd9Sstevel@tonic-gate 
7457c478bd9Sstevel@tonic-gate 		if (dictp->f.fcode == fcode) {
7467c478bd9Sstevel@tonic-gate 			ent = dictp->codem1+1;
7477c478bd9Sstevel@tonic-gate 
7487c478bd9Sstevel@tonic-gate 			/*
7497c478bd9Sstevel@tonic-gate 			 * found (prefix,suffix)
7507c478bd9Sstevel@tonic-gate 			 */
7517c478bd9Sstevel@tonic-gate 			continue;
7527c478bd9Sstevel@tonic-gate 		}
7537c478bd9Sstevel@tonic-gate 
7547c478bd9Sstevel@tonic-gate 		/*
7557c478bd9Sstevel@tonic-gate 		 * continue probing until a match or invalid entry
7567c478bd9Sstevel@tonic-gate 		 */
7577c478bd9Sstevel@tonic-gate 		disp = (hval == 0) ? 1 : hval;
7587c478bd9Sstevel@tonic-gate 
7597c478bd9Sstevel@tonic-gate 		do {
7607c478bd9Sstevel@tonic-gate 			hval += disp;
7617c478bd9Sstevel@tonic-gate 			if (hval >= db->hsize) {
7627c478bd9Sstevel@tonic-gate 				hval -= db->hsize;
7637c478bd9Sstevel@tonic-gate 				if (hval >= db->hsize) {
7647c478bd9Sstevel@tonic-gate 					if (db->flags & DS_DEBUG) {
7657c478bd9Sstevel@tonic-gate 						cmn_err(CE_CONT,
7667c478bd9Sstevel@tonic-gate 						    "bsd_comp%d: internal "
7677c478bd9Sstevel@tonic-gate 						    "error\n",
7687c478bd9Sstevel@tonic-gate 						    db->unit);
7697c478bd9Sstevel@tonic-gate 					}
7707c478bd9Sstevel@tonic-gate 					/* Caller will free it all */
7717c478bd9Sstevel@tonic-gate 					return (-1);
7727c478bd9Sstevel@tonic-gate 				}
7737c478bd9Sstevel@tonic-gate 			}
7747c478bd9Sstevel@tonic-gate 
7757c478bd9Sstevel@tonic-gate 			dictp = &db->dict[hval];
7767c478bd9Sstevel@tonic-gate 
7777c478bd9Sstevel@tonic-gate 			if (dictp->codem1 >= max_ent) {
7787c478bd9Sstevel@tonic-gate 				goto nomatch;
7797c478bd9Sstevel@tonic-gate 			}
7807c478bd9Sstevel@tonic-gate 		} while (dictp->f.fcode != fcode);
7817c478bd9Sstevel@tonic-gate 
7827c478bd9Sstevel@tonic-gate 		/*
7837c478bd9Sstevel@tonic-gate 		 * finally found (prefix,suffix)
7847c478bd9Sstevel@tonic-gate 		 */
7857c478bd9Sstevel@tonic-gate 		ent = dictp->codem1 + 1;
7867c478bd9Sstevel@tonic-gate 
7877c478bd9Sstevel@tonic-gate 		continue;
7887c478bd9Sstevel@tonic-gate 
7897c478bd9Sstevel@tonic-gate nomatch:
7907c478bd9Sstevel@tonic-gate 		/*
7917c478bd9Sstevel@tonic-gate 		 * output the prefix
7927c478bd9Sstevel@tonic-gate 		 */
7937c478bd9Sstevel@tonic-gate 		OUTPUT(ent);
7947c478bd9Sstevel@tonic-gate 
7957c478bd9Sstevel@tonic-gate 		/*
7967c478bd9Sstevel@tonic-gate 		 * code -> hashtable
7977c478bd9Sstevel@tonic-gate 		 */
7987c478bd9Sstevel@tonic-gate 		if (max_ent < db->maxmaxcode) {
7997c478bd9Sstevel@tonic-gate 			struct bsd_dict *dictp2;
8007c478bd9Sstevel@tonic-gate 
8017c478bd9Sstevel@tonic-gate 			/*
8027c478bd9Sstevel@tonic-gate 			 * expand code size if needed
8037c478bd9Sstevel@tonic-gate 			 */
8047c478bd9Sstevel@tonic-gate 			if (max_ent >= MAXCODE(n_bits)) {
8057c478bd9Sstevel@tonic-gate 				db->n_bits = ++n_bits;
8067c478bd9Sstevel@tonic-gate 			}
8077c478bd9Sstevel@tonic-gate 
8087c478bd9Sstevel@tonic-gate 			/*
8097c478bd9Sstevel@tonic-gate 			 * Invalidate old hash table entry using
8107c478bd9Sstevel@tonic-gate 			 * this code, and then take it over.
8117c478bd9Sstevel@tonic-gate 			 */
8127c478bd9Sstevel@tonic-gate 			dictp2 = &db->dict[max_ent+1];
8137c478bd9Sstevel@tonic-gate 
8147c478bd9Sstevel@tonic-gate 			if (db->dict[dictp2->cptr].codem1 == max_ent) {
8157c478bd9Sstevel@tonic-gate 				db->dict[dictp2->cptr].codem1 = BADCODEM1;
8167c478bd9Sstevel@tonic-gate 			}
8177c478bd9Sstevel@tonic-gate 
8187c478bd9Sstevel@tonic-gate 			dictp2->cptr = (ushort_t)hval;
8197c478bd9Sstevel@tonic-gate 			dictp->codem1 = max_ent;
8207c478bd9Sstevel@tonic-gate 			dictp->f.fcode = fcode;
8217c478bd9Sstevel@tonic-gate 
8227c478bd9Sstevel@tonic-gate 			db->max_ent = ++max_ent;
8237c478bd9Sstevel@tonic-gate 		}
8247c478bd9Sstevel@tonic-gate 
8257c478bd9Sstevel@tonic-gate 		ent = c;
8267c478bd9Sstevel@tonic-gate 	}
8277c478bd9Sstevel@tonic-gate 
8287c478bd9Sstevel@tonic-gate 	/*
8297c478bd9Sstevel@tonic-gate 	 * output the last code
8307c478bd9Sstevel@tonic-gate 	 */
8317c478bd9Sstevel@tonic-gate 	OUTPUT(ent);
8327c478bd9Sstevel@tonic-gate 
8337c478bd9Sstevel@tonic-gate 	olen += (32-bitno+7)/8;	/* count complete bytes */
8347c478bd9Sstevel@tonic-gate 
8357c478bd9Sstevel@tonic-gate 	db->bytes_out += olen;
8367c478bd9Sstevel@tonic-gate 	db->in_count += ilen;
8377c478bd9Sstevel@tonic-gate 
8387c478bd9Sstevel@tonic-gate 	if (bsd_check(db)) {
8397c478bd9Sstevel@tonic-gate 		OUTPUT(CLEAR);		/* do not count the CLEAR */
8407c478bd9Sstevel@tonic-gate 	}
8417c478bd9Sstevel@tonic-gate 
8427c478bd9Sstevel@tonic-gate 	/*
8437c478bd9Sstevel@tonic-gate 	 * Pad dribble bits of last code with ones.
8447c478bd9Sstevel@tonic-gate 	 * Do not emit a completely useless byte of ones.
8457c478bd9Sstevel@tonic-gate 	 */
8467c478bd9Sstevel@tonic-gate 	if (bitno != 32) {
8477c478bd9Sstevel@tonic-gate 		PUTBYTE((accm | (0xff << (bitno - 8))) >> 24);
8487c478bd9Sstevel@tonic-gate 	}
8497c478bd9Sstevel@tonic-gate 
8507c478bd9Sstevel@tonic-gate 	/*
8517c478bd9Sstevel@tonic-gate 	 * Increase code size if we would have without the packet
8527c478bd9Sstevel@tonic-gate 	 * boundary and as the decompressor will.
8537c478bd9Sstevel@tonic-gate 	 */
8547c478bd9Sstevel@tonic-gate 	if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
8557c478bd9Sstevel@tonic-gate 		db->n_bits++;
8567c478bd9Sstevel@tonic-gate 	}
8577c478bd9Sstevel@tonic-gate 
8587c478bd9Sstevel@tonic-gate 	db->uncomp_bytes += ilen;
8597c478bd9Sstevel@tonic-gate 	++db->uncomp_count;
8607c478bd9Sstevel@tonic-gate 
8617c478bd9Sstevel@tonic-gate 	if (wptr == NULL || olen + PPP_HDRLEN + BSD_OVHD >= maxolen) {
8627c478bd9Sstevel@tonic-gate 		/*
8637c478bd9Sstevel@tonic-gate 		 * throw away the compressed stuff if it is longer
8647c478bd9Sstevel@tonic-gate 		 * than uncompressed
8657c478bd9Sstevel@tonic-gate 		 */
8667c478bd9Sstevel@tonic-gate 		freemsg(mret);
8677c478bd9Sstevel@tonic-gate 
8687c478bd9Sstevel@tonic-gate 		mret = NULL;
8697c478bd9Sstevel@tonic-gate 
8707c478bd9Sstevel@tonic-gate 		++db->incomp_count;
8717c478bd9Sstevel@tonic-gate 		db->incomp_bytes += ilen;
8727c478bd9Sstevel@tonic-gate 
8737c478bd9Sstevel@tonic-gate 	} else {
8747c478bd9Sstevel@tonic-gate 
8757c478bd9Sstevel@tonic-gate 		m->b_wptr = wptr;
8767c478bd9Sstevel@tonic-gate 		if (m->b_cont) {
8777c478bd9Sstevel@tonic-gate 			freemsg(m->b_cont);
8787c478bd9Sstevel@tonic-gate 			m->b_cont = NULL;
8797c478bd9Sstevel@tonic-gate 		}
8807c478bd9Sstevel@tonic-gate 
8817c478bd9Sstevel@tonic-gate 		++db->comp_count;
8827c478bd9Sstevel@tonic-gate 		db->comp_bytes += olen + BSD_OVHD;
8837c478bd9Sstevel@tonic-gate 	}
8847c478bd9Sstevel@tonic-gate 
8857c478bd9Sstevel@tonic-gate 	*mretp = mret;
8867c478bd9Sstevel@tonic-gate 
8877c478bd9Sstevel@tonic-gate 	return (olen + PPP_HDRLEN + BSD_OVHD);
8887c478bd9Sstevel@tonic-gate #undef OUTPUT
8897c478bd9Sstevel@tonic-gate #undef PUTBYTE
8907c478bd9Sstevel@tonic-gate }
8917c478bd9Sstevel@tonic-gate 
8927c478bd9Sstevel@tonic-gate 
8937c478bd9Sstevel@tonic-gate /*
8947c478bd9Sstevel@tonic-gate  * bsd_incomp()
8957c478bd9Sstevel@tonic-gate  *
8967c478bd9Sstevel@tonic-gate  * Update the "BSD Compress" dictionary on the receiver for
8977c478bd9Sstevel@tonic-gate  * incompressible data by pretending to compress the incoming data.
8987c478bd9Sstevel@tonic-gate  */
8997c478bd9Sstevel@tonic-gate static int
bsd_incomp(void * state,mblk_t * mp)9007c478bd9Sstevel@tonic-gate bsd_incomp(void *state, mblk_t *mp)
9017c478bd9Sstevel@tonic-gate {
9027c478bd9Sstevel@tonic-gate 	struct bsd_db	*db = (struct bsd_db *)state;
9037c478bd9Sstevel@tonic-gate 	uint_t		hshift = db->hshift;
9047c478bd9Sstevel@tonic-gate 	uint_t		max_ent = db->max_ent;
9057c478bd9Sstevel@tonic-gate 	uint_t		n_bits = db->n_bits;
9067c478bd9Sstevel@tonic-gate 	struct bsd_dict	*dictp;
9077c478bd9Sstevel@tonic-gate 	uint32_t	fcode;
9087c478bd9Sstevel@tonic-gate 	uchar_t		c;
9097c478bd9Sstevel@tonic-gate 	long		hval;
9107c478bd9Sstevel@tonic-gate 	long		disp;
9117c478bd9Sstevel@tonic-gate 	int		slen;
9127c478bd9Sstevel@tonic-gate 	int		ilen;
9137c478bd9Sstevel@tonic-gate 	uint_t		bitno = 7;
9147c478bd9Sstevel@tonic-gate 	uchar_t		*rptr, *rmax;
9157c478bd9Sstevel@tonic-gate 	uint_t		ent;
9167c478bd9Sstevel@tonic-gate 
917*002c70ffScarlsonj 	ASSERT(db->flags & DS_INITDONE);
918*002c70ffScarlsonj 
9197c478bd9Sstevel@tonic-gate 	if (db->hsize == 0)
9207c478bd9Sstevel@tonic-gate 		return (-1);
9217c478bd9Sstevel@tonic-gate 
9227c478bd9Sstevel@tonic-gate 	rptr = mp->b_rptr;
9237c478bd9Sstevel@tonic-gate 	rmax = mp->b_wptr;
9247c478bd9Sstevel@tonic-gate 	ADJRPTR();
9257c478bd9Sstevel@tonic-gate 	GETBYTE(ent);	/* address */
9267c478bd9Sstevel@tonic-gate 	ADJRPTR();
9277c478bd9Sstevel@tonic-gate 	GETBYTE(ent);	/* control */
9287c478bd9Sstevel@tonic-gate 	ADJRPTR();
9297c478bd9Sstevel@tonic-gate 	GETBYTE(ent);	/* protocol high */
9307c478bd9Sstevel@tonic-gate 	ADJRPTR();
9317c478bd9Sstevel@tonic-gate 
9327c478bd9Sstevel@tonic-gate 	/*
9337c478bd9Sstevel@tonic-gate 	 * Per RFC 1977, the protocol field must be compressed using a
9347c478bd9Sstevel@tonic-gate 	 * PFC-like procedure.  Also, all protocols between 0000-3FFF
9357c478bd9Sstevel@tonic-gate 	 * except the two compression protocols must be LZ compressed.
9367c478bd9Sstevel@tonic-gate 	 */
9377c478bd9Sstevel@tonic-gate 	ilen = 1;			/* count the protocol as 1 byte */
9387c478bd9Sstevel@tonic-gate 	if (ent == 0) {
9397c478bd9Sstevel@tonic-gate 		GETBYTE(ent);
9407c478bd9Sstevel@tonic-gate 		if (rptr == NULL || ent == PPP_COMP || ent == PPP_COMPFRAG)
9417c478bd9Sstevel@tonic-gate 			return (0);
9427c478bd9Sstevel@tonic-gate 	} else {
9437c478bd9Sstevel@tonic-gate 		if (ent > 0x3F)
9447c478bd9Sstevel@tonic-gate 			return (0);
9457c478bd9Sstevel@tonic-gate 		ilen++;
9467c478bd9Sstevel@tonic-gate 	}
9477c478bd9Sstevel@tonic-gate 
9487c478bd9Sstevel@tonic-gate 	db->seqno++;
9497c478bd9Sstevel@tonic-gate 
9507c478bd9Sstevel@tonic-gate 	for (;;) {
9517c478bd9Sstevel@tonic-gate 
9527c478bd9Sstevel@tonic-gate 		slen = mp->b_wptr - rptr;
9537c478bd9Sstevel@tonic-gate 		if (slen <= 0) {
9547c478bd9Sstevel@tonic-gate 			mp = mp->b_cont;
9557c478bd9Sstevel@tonic-gate 			if (!mp) {
9567c478bd9Sstevel@tonic-gate 				break;
9577c478bd9Sstevel@tonic-gate 			}
9587c478bd9Sstevel@tonic-gate 
9597c478bd9Sstevel@tonic-gate 			rptr = mp->b_rptr;
9607c478bd9Sstevel@tonic-gate 			continue;	/* skip zero-length buffers */
9617c478bd9Sstevel@tonic-gate 		}
9627c478bd9Sstevel@tonic-gate 
9637c478bd9Sstevel@tonic-gate 		ilen += slen;
9647c478bd9Sstevel@tonic-gate 
9657c478bd9Sstevel@tonic-gate 		do {
9667c478bd9Sstevel@tonic-gate 			c = *rptr++;
9677c478bd9Sstevel@tonic-gate 
9687c478bd9Sstevel@tonic-gate 			fcode = BSD_KEY(ent, c);
9697c478bd9Sstevel@tonic-gate 			hval = BSD_HASH(ent, c, hshift);
9707c478bd9Sstevel@tonic-gate 
9717c478bd9Sstevel@tonic-gate 			dictp = &db->dict[hval];
9727c478bd9Sstevel@tonic-gate 
9737c478bd9Sstevel@tonic-gate 			/*
9747c478bd9Sstevel@tonic-gate 			 * validate and then check the entry
9757c478bd9Sstevel@tonic-gate 			 */
9767c478bd9Sstevel@tonic-gate 			if (dictp->codem1 >= max_ent) {
9777c478bd9Sstevel@tonic-gate 				goto nomatch;
9787c478bd9Sstevel@tonic-gate 			}
9797c478bd9Sstevel@tonic-gate 
9807c478bd9Sstevel@tonic-gate 			if (dictp->f.fcode == fcode) {
9817c478bd9Sstevel@tonic-gate 				ent = dictp->codem1 + 1;
9827c478bd9Sstevel@tonic-gate 				continue;   /* found (prefix,suffix) */
9837c478bd9Sstevel@tonic-gate 			}
9847c478bd9Sstevel@tonic-gate 
9857c478bd9Sstevel@tonic-gate 			/*
9867c478bd9Sstevel@tonic-gate 			 * continue probing until a match or invalid entry
9877c478bd9Sstevel@tonic-gate 			 */
9887c478bd9Sstevel@tonic-gate 			disp = (hval == 0) ? 1 : hval;
9897c478bd9Sstevel@tonic-gate 			do {
9907c478bd9Sstevel@tonic-gate 				hval += disp;
9917c478bd9Sstevel@tonic-gate 				if (hval >= db->hsize) {
9927c478bd9Sstevel@tonic-gate 					hval -= db->hsize;
9937c478bd9Sstevel@tonic-gate 					if (hval >= db->hsize) {
9947c478bd9Sstevel@tonic-gate 						if (db->flags & DS_DEBUG) {
9957c478bd9Sstevel@tonic-gate 							cmn_err(CE_CONT,
9967c478bd9Sstevel@tonic-gate 							    "bsd_incomp%d: "
9977c478bd9Sstevel@tonic-gate 							    "internal error\n",
9987c478bd9Sstevel@tonic-gate 							    db->unit);
9997c478bd9Sstevel@tonic-gate 						}
10007c478bd9Sstevel@tonic-gate 						return (-1);
10017c478bd9Sstevel@tonic-gate 					}
10027c478bd9Sstevel@tonic-gate 				}
10037c478bd9Sstevel@tonic-gate 
10047c478bd9Sstevel@tonic-gate 				dictp = &db->dict[hval];
10057c478bd9Sstevel@tonic-gate 				if (dictp->codem1 >= max_ent) {
10067c478bd9Sstevel@tonic-gate 					goto nomatch;
10077c478bd9Sstevel@tonic-gate 				}
10087c478bd9Sstevel@tonic-gate 			} while (dictp->f.fcode != fcode);
10097c478bd9Sstevel@tonic-gate 
10107c478bd9Sstevel@tonic-gate 			ent = dictp->codem1+1;
10117c478bd9Sstevel@tonic-gate 			continue;	/* finally found (prefix,suffix) */
10127c478bd9Sstevel@tonic-gate 
10137c478bd9Sstevel@tonic-gate nomatch:				/* output (count) the prefix */
10147c478bd9Sstevel@tonic-gate 			bitno += n_bits;
10157c478bd9Sstevel@tonic-gate 
10167c478bd9Sstevel@tonic-gate 			/*
10177c478bd9Sstevel@tonic-gate 			 * code -> hashtable
10187c478bd9Sstevel@tonic-gate 			 */
10197c478bd9Sstevel@tonic-gate 			if (max_ent < db->maxmaxcode) {
10207c478bd9Sstevel@tonic-gate 				struct bsd_dict *dictp2;
10217c478bd9Sstevel@tonic-gate 
10227c478bd9Sstevel@tonic-gate 				/*
10237c478bd9Sstevel@tonic-gate 				 * expand code size if needed
10247c478bd9Sstevel@tonic-gate 				 */
10257c478bd9Sstevel@tonic-gate 				if (max_ent >= MAXCODE(n_bits)) {
10267c478bd9Sstevel@tonic-gate 					db->n_bits = ++n_bits;
10277c478bd9Sstevel@tonic-gate 				}
10287c478bd9Sstevel@tonic-gate 
10297c478bd9Sstevel@tonic-gate 				/*
10307c478bd9Sstevel@tonic-gate 				 * Invalidate previous hash table entry
10317c478bd9Sstevel@tonic-gate 				 * assigned this code, and then take it over.
10327c478bd9Sstevel@tonic-gate 				 */
10337c478bd9Sstevel@tonic-gate 				dictp2 = &db->dict[max_ent+1];
10347c478bd9Sstevel@tonic-gate 				if (db->dict[dictp2->cptr].codem1 == max_ent) {
10357c478bd9Sstevel@tonic-gate 					db->dict[dictp2->cptr].codem1 =
1036*002c70ffScarlsonj 					    BADCODEM1;
10377c478bd9Sstevel@tonic-gate 				}
10387c478bd9Sstevel@tonic-gate 
10397c478bd9Sstevel@tonic-gate 				dictp2->cptr = (ushort_t)hval;
10407c478bd9Sstevel@tonic-gate 				dictp->codem1 = max_ent;
10417c478bd9Sstevel@tonic-gate 				dictp->f.fcode = fcode;
10427c478bd9Sstevel@tonic-gate 
10437c478bd9Sstevel@tonic-gate 				db->max_ent = ++max_ent;
10447c478bd9Sstevel@tonic-gate 				db->lens[max_ent] = db->lens[ent]+1;
10457c478bd9Sstevel@tonic-gate 			}
10467c478bd9Sstevel@tonic-gate 
10477c478bd9Sstevel@tonic-gate 			ent = c;
10487c478bd9Sstevel@tonic-gate 		} while (--slen != 0);
10497c478bd9Sstevel@tonic-gate 	}
10507c478bd9Sstevel@tonic-gate 
10517c478bd9Sstevel@tonic-gate 	bitno += n_bits;		/* output (count) the last code */
10527c478bd9Sstevel@tonic-gate 
10537c478bd9Sstevel@tonic-gate 	db->bytes_out += bitno/8;
10547c478bd9Sstevel@tonic-gate 	db->in_count += ilen;
10557c478bd9Sstevel@tonic-gate 
10567c478bd9Sstevel@tonic-gate 	(void) bsd_check(db);
10577c478bd9Sstevel@tonic-gate 
10587c478bd9Sstevel@tonic-gate 	++db->incomp_count;
10597c478bd9Sstevel@tonic-gate 	db->incomp_bytes += ilen;
10607c478bd9Sstevel@tonic-gate 	++db->uncomp_count;
10617c478bd9Sstevel@tonic-gate 	db->uncomp_bytes += ilen;
10627c478bd9Sstevel@tonic-gate 
10637c478bd9Sstevel@tonic-gate 	/*
10647c478bd9Sstevel@tonic-gate 	 * Increase code size if we would have without the packet
10657c478bd9Sstevel@tonic-gate 	 * boundary and as the decompressor will.
10667c478bd9Sstevel@tonic-gate 	 */
10677c478bd9Sstevel@tonic-gate 	if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
10687c478bd9Sstevel@tonic-gate 		db->n_bits++;
10697c478bd9Sstevel@tonic-gate 	}
10707c478bd9Sstevel@tonic-gate 	return (0);
10717c478bd9Sstevel@tonic-gate #undef ADJRPTR
10727c478bd9Sstevel@tonic-gate }
10737c478bd9Sstevel@tonic-gate 
10747c478bd9Sstevel@tonic-gate 
10757c478bd9Sstevel@tonic-gate /*
10767c478bd9Sstevel@tonic-gate  * bsd_decompress()
10777c478bd9Sstevel@tonic-gate  *
10787c478bd9Sstevel@tonic-gate  * Decompress "BSD Compress"
10797c478bd9Sstevel@tonic-gate  *
10807c478bd9Sstevel@tonic-gate  * Because of patent problems, we return DECOMP_ERROR for errors
10817c478bd9Sstevel@tonic-gate  * found by inspecting the input data and for system problems, but
10827c478bd9Sstevel@tonic-gate  * DECOMP_FATALERROR for any errors which could possibly be said to
10837c478bd9Sstevel@tonic-gate  * be being detected "after" decompression.  For DECOMP_ERROR,
10847c478bd9Sstevel@tonic-gate  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
10857c478bd9Sstevel@tonic-gate  * infringing a patent of Motorola's if we do, so we take CCP down
10867c478bd9Sstevel@tonic-gate  * instead.
10877c478bd9Sstevel@tonic-gate  *
10887c478bd9Sstevel@tonic-gate  * Given that the frame has the correct sequence number and a good FCS,
10897c478bd9Sstevel@tonic-gate  * errors such as invalid codes in the input most likely indicate a
10907c478bd9Sstevel@tonic-gate  * bug, so we return DECOMP_FATALERROR for them in order to turn off
10917c478bd9Sstevel@tonic-gate  * compression, even though they are detected by inspecting the input.
10927c478bd9Sstevel@tonic-gate  */
10937c478bd9Sstevel@tonic-gate static int
bsd_decompress(void * state,mblk_t ** dmpp)10947c478bd9Sstevel@tonic-gate bsd_decompress(void *state, mblk_t **dmpp)
10957c478bd9Sstevel@tonic-gate {
10967c478bd9Sstevel@tonic-gate 	mblk_t		*cmsg = *dmpp, *mnext;
10977c478bd9Sstevel@tonic-gate 	struct bsd_db	*db = (struct bsd_db *)state;
10987c478bd9Sstevel@tonic-gate 	uint_t		max_ent = db->max_ent;
10997c478bd9Sstevel@tonic-gate 	uint32_t	accm = 0;
11007c478bd9Sstevel@tonic-gate 	uint_t		bitno = 32;		/* 1st valid bit in accm */
11017c478bd9Sstevel@tonic-gate 	uint_t		n_bits = db->n_bits;
11027c478bd9Sstevel@tonic-gate 	uint_t		tgtbitno = 32 - n_bits;	/* bitno when we have a code */
11037c478bd9Sstevel@tonic-gate 	struct bsd_dict	*dictp;
11047c478bd9Sstevel@tonic-gate 	int		explen;
11057c478bd9Sstevel@tonic-gate 	int		seq;
11067c478bd9Sstevel@tonic-gate 	uint_t		incode;
11077c478bd9Sstevel@tonic-gate 	uint_t		oldcode;
11087c478bd9Sstevel@tonic-gate 	uint_t		finchar = 0, ofinchar;
11097c478bd9Sstevel@tonic-gate 	uchar_t		*p;
11107c478bd9Sstevel@tonic-gate 	uchar_t		*rptr, *rmax;
11117c478bd9Sstevel@tonic-gate 	uchar_t		*wptr, *prepos;
11127c478bd9Sstevel@tonic-gate 	mblk_t		*dmsg;
11137c478bd9Sstevel@tonic-gate 	mblk_t		*mret;
11147c478bd9Sstevel@tonic-gate 	int		ilen;
11157c478bd9Sstevel@tonic-gate 	int		dlen;
11167c478bd9Sstevel@tonic-gate 	int		codelen;
11177c478bd9Sstevel@tonic-gate 	int		extra;
11187c478bd9Sstevel@tonic-gate 	int		decode_proto;
11197c478bd9Sstevel@tonic-gate 	int		blockctr;
11207c478bd9Sstevel@tonic-gate 	int		outlen;
11217c478bd9Sstevel@tonic-gate #if defined(lint) || defined(_lint)
11227c478bd9Sstevel@tonic-gate 	uchar_t		adrs, ctrl;
11237c478bd9Sstevel@tonic-gate #else
11247c478bd9Sstevel@tonic-gate 	int		adrs, ctrl;
11257c478bd9Sstevel@tonic-gate #endif
11267c478bd9Sstevel@tonic-gate 
1127*002c70ffScarlsonj 	ASSERT(db->flags & DS_INITDONE);
1128*002c70ffScarlsonj 
11297c478bd9Sstevel@tonic-gate 	/* Note: spppcomp already did a pullup to fix the first buffer. */
11307c478bd9Sstevel@tonic-gate 	*dmpp = NULL;
11317c478bd9Sstevel@tonic-gate 	rptr = cmsg->b_rptr;
11327c478bd9Sstevel@tonic-gate 	rmax = cmsg->b_wptr;
11337c478bd9Sstevel@tonic-gate 	ilen = 0;
11347c478bd9Sstevel@tonic-gate 
11357c478bd9Sstevel@tonic-gate 	/*
11367c478bd9Sstevel@tonic-gate 	 * Note that we free as we go.  If we fail to decompress,
11377c478bd9Sstevel@tonic-gate 	 * there's nothing good that the caller can do.
11387c478bd9Sstevel@tonic-gate 	 */
11397c478bd9Sstevel@tonic-gate #define	ADJRPTR()					\
11407c478bd9Sstevel@tonic-gate 	while (rptr >= rmax) {				\
11417c478bd9Sstevel@tonic-gate 		mnext = cmsg->b_cont;			\
11427c478bd9Sstevel@tonic-gate 		freeb(cmsg);				\
11437c478bd9Sstevel@tonic-gate 		if ((cmsg = mnext) == NULL) {		\
11447c478bd9Sstevel@tonic-gate 			rptr = NULL;			\
11457c478bd9Sstevel@tonic-gate 			break;				\
11467c478bd9Sstevel@tonic-gate 		}					\
11477c478bd9Sstevel@tonic-gate 		rptr = cmsg->b_rptr;			\
11487c478bd9Sstevel@tonic-gate 		rmax = cmsg->b_wptr;			\
11497c478bd9Sstevel@tonic-gate 		ilen += rmax-rptr;			\
11507c478bd9Sstevel@tonic-gate 	}
11517c478bd9Sstevel@tonic-gate 
11527c478bd9Sstevel@tonic-gate 	/*
11537c478bd9Sstevel@tonic-gate 	 * Save the address/control from the PPP header
11547c478bd9Sstevel@tonic-gate 	 * and then get the sequence number.
11557c478bd9Sstevel@tonic-gate 	 */
11567c478bd9Sstevel@tonic-gate 	adrs = rptr[0];
11577c478bd9Sstevel@tonic-gate 	ctrl = rptr[1];
11587c478bd9Sstevel@tonic-gate 	rptr += 4;
11597c478bd9Sstevel@tonic-gate 	ADJRPTR();
11607c478bd9Sstevel@tonic-gate 	seq = rptr == NULL ? 0 : (*rptr++ << 8);
11617c478bd9Sstevel@tonic-gate 	ADJRPTR();
11627c478bd9Sstevel@tonic-gate 	if (rptr == NULL) {
11637c478bd9Sstevel@tonic-gate 		if (db->flags & DS_DEBUG) {
11647c478bd9Sstevel@tonic-gate 			cmn_err(CE_CONT, "bsd_decomp%d: bad buffer\n",
11657c478bd9Sstevel@tonic-gate 			    db->unit);
11667c478bd9Sstevel@tonic-gate 		}
11677c478bd9Sstevel@tonic-gate 		return (DECOMP_ERROR);
11687c478bd9Sstevel@tonic-gate 	}
11697c478bd9Sstevel@tonic-gate 	seq |= *rptr++;
11707c478bd9Sstevel@tonic-gate 
11717c478bd9Sstevel@tonic-gate #ifdef DEBUG
11727c478bd9Sstevel@tonic-gate 	/*
11737c478bd9Sstevel@tonic-gate 	 * If testing input, just pretending the sequence is bad here
11747c478bd9Sstevel@tonic-gate 	 * does the trick.
11757c478bd9Sstevel@tonic-gate 	 */
11767c478bd9Sstevel@tonic-gate 	if ((db->flags & DS_TESTIN) && (db->seqno % 300) == 101)
11777c478bd9Sstevel@tonic-gate 		seq ^= 0x55;
11787c478bd9Sstevel@tonic-gate #endif
11797c478bd9Sstevel@tonic-gate 
11807c478bd9Sstevel@tonic-gate 	/*
11817c478bd9Sstevel@tonic-gate 	 * Check the sequence number and give up if it is not what we expect.
11827c478bd9Sstevel@tonic-gate 	 */
11837c478bd9Sstevel@tonic-gate 	if (db->hsize == 0 || seq != db->seqno++) {
11847c478bd9Sstevel@tonic-gate 		freemsg(cmsg);
11857c478bd9Sstevel@tonic-gate 		if (db->flags & DS_DEBUG) {
11867c478bd9Sstevel@tonic-gate 			cmn_err(CE_CONT, "bsd_decomp%d: bad sequence # %d, "
1187*002c70ffScarlsonj 			    "expected %d\n", db->unit, seq, db->seqno - 1);
11887c478bd9Sstevel@tonic-gate 		}
11897c478bd9Sstevel@tonic-gate 
11907c478bd9Sstevel@tonic-gate 		return (DECOMP_ERROR);
11917c478bd9Sstevel@tonic-gate 	}
11927c478bd9Sstevel@tonic-gate 
11937c478bd9Sstevel@tonic-gate 	/*
11947c478bd9Sstevel@tonic-gate 	 * Allocate one message block to start with.
11957c478bd9Sstevel@tonic-gate 	 */
11967c478bd9Sstevel@tonic-gate 	if ((dmsg = allocb(DECOMP_CHUNK + db->hdrlen, BPRI_MED)) == NULL) {
11977c478bd9Sstevel@tonic-gate 		freemsg(cmsg);
11987c478bd9Sstevel@tonic-gate 		if (db->flags & DS_DEBUG) {
11997c478bd9Sstevel@tonic-gate 			cmn_err(CE_CO