File:  [DragonFly] / src / sys / net / bsd_comp.c
Revision 1.5: download - view: text, annotated - select for diffs
Thu Apr 22 04:21:29 2004 UTC (10 years, 3 months ago) by dillon
Branches: MAIN
CVS tags: HEAD
M_NOWAIT -> M_WAITOK or M_INTWAIT conversions.  There is a whole lot of net
code that is improperly using M_NOWAIT.  Also remove now unneeded NULL checks
since malloc will panic rather then return NULL when M_NULLOK is not set.

Use M_INTWAIT|M_NULLOK in some cases (such as route table allocation) in
order to allow malloc to return NULL when the limit for the malloc type
is reached.

    1: /* Because this code is derived from the 4.3BSD compress source:
    2:  *
    3:  *
    4:  * Copyright (c) 1985, 1986 The Regents of the University of California.
    5:  * All rights reserved.
    6:  *
    7:  * This code is derived from software contributed to Berkeley by
    8:  * James A. Woods, derived from original work by Spencer Thomas
    9:  * and Joseph Orost.
   10:  *
   11:  * Redistribution and use in source and binary forms, with or without
   12:  * modification, are permitted provided that the following conditions
   13:  * are met:
   14:  * 1. Redistributions of source code must retain the above copyright
   15:  *    notice, this list of conditions and the following disclaimer.
   16:  * 2. Redistributions in binary form must reproduce the above copyright
   17:  *    notice, this list of conditions and the following disclaimer in the
   18:  *    documentation and/or other materials provided with the distribution.
   19:  * 3. All advertising materials mentioning features or use of this software
   20:  *    must display the following acknowledgement:
   21:  *	This product includes software developed by the University of
   22:  *	California, Berkeley and its contributors.
   23:  * 4. Neither the name of the University nor the names of its contributors
   24:  *    may be used to endorse or promote products derived from this software
   25:  *    without specific prior written permission.
   26:  *
   27:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   28:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   29:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   30:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   31:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   32:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   33:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   34:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   35:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   36:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   37:  * SUCH DAMAGE.
   38:  */
   39: 
   40: /*
   41:  * This version is for use with mbufs on BSD-derived systems.
   42:  *
   43:  * $FreeBSD: src/sys/net/bsd_comp.c,v 1.11.2.1 2002/04/14 21:41:48 luigi Exp $
   44:  * $DragonFly: src/sys/net/bsd_comp.c,v 1.5 2004/04/22 04:21:29 dillon Exp $
   45:  */
   46: 
   47: #include <sys/param.h>
   48: #include <sys/systm.h>
   49: #include <sys/malloc.h>
   50: #include <sys/mbuf.h>
   51: #include <net/ppp_layer/ppp_defs.h>
   52: 
   53: #define PACKETPTR	struct mbuf *
   54: #include <net/ppp_layer/ppp_comp.h>
   55: 
   56: #if DO_BSD_COMPRESS
   57: /*
   58:  * PPP "BSD compress" compression
   59:  *  The differences between this compression and the classic BSD LZW
   60:  *  source are obvious from the requirement that the classic code worked
   61:  *  with files while this handles arbitrarily long streams that
   62:  *  are broken into packets.  They are:
   63:  *
   64:  *	When the code size expands, a block of junk is not emitted by
   65:  *	    the compressor and not expected by the decompressor.
   66:  *
   67:  *	New codes are not necessarily assigned every time an old
   68:  *	    code is output by the compressor.  This is because a packet
   69:  *	    end forces a code to be emitted, but does not imply that a
   70:  *	    new sequence has been seen.
   71:  *
   72:  *	The compression ratio is checked at the first end of a packet
   73:  *	    after the appropriate gap.	Besides simplifying and speeding
   74:  *	    things up, this makes it more likely that the transmitter
   75:  *	    and receiver will agree when the dictionary is cleared when
   76:  *	    compression is not going well.
   77:  */
   78: 
   79: /*
   80:  * A dictionary for doing BSD compress.
   81:  */
   82: struct bsd_db {
   83:     int	    totlen;			/* length of this structure */
   84:     u_int   hsize;			/* size of the hash table */
   85:     u_char  hshift;			/* used in hash function */
   86:     u_char  n_bits;			/* current bits/code */
   87:     u_char  maxbits;
   88:     u_char  debug;
   89:     u_char  unit;
   90:     u_int16_t seqno;			/* sequence # of next packet */
   91:     u_int   hdrlen;			/* header length to preallocate */
   92:     u_int   mru;
   93:     u_int   maxmaxcode;			/* largest valid code */
   94:     u_int   max_ent;			/* largest code in use */
   95:     u_int   in_count;			/* uncompressed bytes, aged */
   96:     u_int   bytes_out;			/* compressed bytes, aged */
   97:     u_int   ratio;			/* recent compression ratio */
   98:     u_int   checkpoint;			/* when to next check the ratio */
   99:     u_int   clear_count;		/* times dictionary cleared */
  100:     u_int   incomp_count;		/* incompressible packets */
  101:     u_int   incomp_bytes;		/* incompressible bytes */
  102:     u_int   uncomp_count;		/* uncompressed packets */
  103:     u_int   uncomp_bytes;		/* uncompressed bytes */
  104:     u_int   comp_count;			/* compressed packets */
  105:     u_int   comp_bytes;			/* compressed bytes */
  106:     u_int16_t *lens;			/* array of lengths of codes */
  107:     struct bsd_dict {
  108: 	union {				/* hash value */
  109: 	    u_int32_t	fcode;
  110: 	    struct {
  111: #if BYTE_ORDER == LITTLE_ENDIAN
  112: 		u_int16_t prefix;	/* preceding code */
  113: 		u_char	suffix;		/* last character of new code */
  114: 		u_char	pad;
  115: #else
  116: 		u_char	pad;
  117: 		u_char	suffix;		/* last character of new code */
  118: 		u_int16_t prefix;	/* preceding code */
  119: #endif
  120: 	    } hs;
  121: 	} f;
  122: 	u_int16_t codem1;		/* output of hash table -1 */
  123: 	u_int16_t cptr;			/* map code to hash table entry */
  124:     } dict[1];
  125: };
  126: 
  127: #define BSD_OVHD	2		/* BSD compress overhead/packet */
  128: #define BSD_INIT_BITS	BSD_MIN_BITS
  129: 
  130: static void	bsd_clear (struct bsd_db *db);
  131: static int	bsd_check (struct bsd_db *db);
  132: static void	*bsd_alloc (u_char *options, int opt_len, int decomp);
  133: static int	bsd_init (struct bsd_db *db, u_char *options, int opt_len,
  134: 			      int unit, int hdrlen, int mru, int debug,
  135: 			      int decomp);
  136: static void	*bsd_comp_alloc (u_char *options, int opt_len);
  137: static void	*bsd_decomp_alloc (u_char *options, int opt_len);
  138: static void	bsd_free (void *state);
  139: static int	bsd_comp_init (void *state, u_char *options, int opt_len,
  140: 				   int unit, int hdrlen, int debug);
  141: static int	bsd_decomp_init (void *state, u_char *options, int opt_len,
  142: 				     int unit, int hdrlen, int mru, int debug);
  143: static int	bsd_compress (void *state, struct mbuf **mret,
  144: 				  struct mbuf *mp, int slen, int maxolen);
  145: static void	bsd_incomp (void *state, struct mbuf *dmsg);
  146: static int	bsd_decompress (void *state, struct mbuf *cmp,
  147: 				    struct mbuf **dmpp);
  148: static void	bsd_reset (void *state);
  149: static void	bsd_comp_stats (void *state, struct compstat *stats);
  150: 
  151: /*
  152:  * Procedures exported to if_ppp.c.
  153:  */
  154: struct compressor ppp_bsd_compress = {
  155:     CI_BSD_COMPRESS,		/* compress_proto */
  156:     bsd_comp_alloc,		/* comp_alloc */
  157:     bsd_free,			/* comp_free */
  158:     bsd_comp_init,		/* comp_init */
  159:     bsd_reset,			/* comp_reset */
  160:     bsd_compress,		/* compress */
  161:     bsd_comp_stats,		/* comp_stat */
  162:     bsd_decomp_alloc,		/* decomp_alloc */
  163:     bsd_free,			/* decomp_free */
  164:     bsd_decomp_init,		/* decomp_init */
  165:     bsd_reset,			/* decomp_reset */
  166:     bsd_decompress,		/* decompress */
  167:     bsd_incomp,			/* incomp */
  168:     bsd_comp_stats,		/* decomp_stat */
  169: };
  170: 
  171: /*
  172:  * the next two codes should not be changed lightly, as they must not
  173:  * lie within the contiguous general code space.
  174:  */
  175: #define CLEAR	256			/* table clear output code */
  176: #define FIRST	257			/* first free entry */
  177: #define LAST	255
  178: 
  179: #define MAXCODE(b)	((1 << (b)) - 1)
  180: #define BADCODEM1	MAXCODE(BSD_MAX_BITS)
  181: 
  182: #define BSD_HASH(prefix,suffix,hshift)	((((u_int32_t)(suffix)) << (hshift)) \
  183: 					 ^ (u_int32_t)(prefix))
  184: #define BSD_KEY(prefix,suffix)		((((u_int32_t)(suffix)) << 16) \
  185: 					 + (u_int32_t)(prefix))
  186: 
  187: #define CHECK_GAP	10000		/* Ratio check interval */
  188: 
  189: #define RATIO_SCALE_LOG	8
  190: #define RATIO_SCALE	(1<<RATIO_SCALE_LOG)
  191: #define RATIO_MAX	(0x7fffffff>>RATIO_SCALE_LOG)
  192: 
  193: /*
  194:  * clear the dictionary
  195:  */
  196: static void
  197: bsd_clear(db)
  198:     struct bsd_db *db;
  199: {
  200:     db->clear_count++;
  201:     db->max_ent = FIRST-1;
  202:     db->n_bits = BSD_INIT_BITS;
  203:     db->ratio = 0;
  204:     db->bytes_out = 0;
  205:     db->in_count = 0;
  206:     db->checkpoint = CHECK_GAP;
  207: }
  208: 
  209: /*
  210:  * If the dictionary is full, then see if it is time to reset it.
  211:  *
  212:  * Compute the compression ratio using fixed-point arithmetic
  213:  * with 8 fractional bits.
  214:  *
  215:  * Since we have an infinite stream instead of a single file,
  216:  * watch only the local compression ratio.
  217:  *
  218:  * Since both peers must reset the dictionary at the same time even in
  219:  * the absence of CLEAR codes (while packets are incompressible), they
  220:  * must compute the same ratio.
  221:  */
  222: static int				/* 1=output CLEAR */
  223: bsd_check(db)
  224:     struct bsd_db *db;
  225: {
  226:     u_int new_ratio;
  227: 
  228:     if (db->in_count >= db->checkpoint) {
  229: 	/* age the ratio by limiting the size of the counts */
  230: 	if (db->in_count >= RATIO_MAX
  231: 	    || db->bytes_out >= RATIO_MAX) {
  232: 	    db->in_count -= db->in_count/4;
  233: 	    db->bytes_out -= db->bytes_out/4;
  234: 	}
  235: 
  236: 	db->checkpoint = db->in_count + CHECK_GAP;
  237: 
  238: 	if (db->max_ent >= db->maxmaxcode) {
  239: 	    /* Reset the dictionary only if the ratio is worse,
  240: 	     * or if it looks as if it has been poisoned
  241: 	     * by incompressible data.
  242: 	     *
  243: 	     * This does not overflow, because
  244: 	     *	db->in_count <= RATIO_MAX.
  245: 	     */
  246: 	    new_ratio = db->in_count << RATIO_SCALE_LOG;
  247: 	    if (db->bytes_out != 0)
  248: 		new_ratio /= db->bytes_out;
  249: 
  250: 	    if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE) {
  251: 		bsd_clear(db);
  252: 		return 1;
  253: 	    }
  254: 	    db->ratio = new_ratio;
  255: 	}
  256:     }
  257:     return 0;
  258: }
  259: 
  260: /*
  261:  * Return statistics.
  262:  */
  263: static void
  264: bsd_comp_stats(state, stats)
  265:     void *state;
  266:     struct compstat *stats;
  267: {
  268:     struct bsd_db *db = (struct bsd_db *) state;
  269:     u_int out;
  270: 
  271:     stats->unc_bytes = db->uncomp_bytes;
  272:     stats->unc_packets = db->uncomp_count;
  273:     stats->comp_bytes = db->comp_bytes;
  274:     stats->comp_packets = db->comp_count;
  275:     stats->inc_bytes = db->incomp_bytes;
  276:     stats->inc_packets = db->incomp_count;
  277:     stats->ratio = db->in_count;
  278:     out = db->bytes_out;
  279:     if (stats->ratio <= 0x7fffff)
  280: 	stats->ratio <<= 8;
  281:     else
  282: 	out >>= 8;
  283:     if (out != 0)
  284: 	stats->ratio /= out;
  285: }
  286: 
  287: /*
  288:  * Reset state, as on a CCP ResetReq.
  289:  */
  290: static void
  291: bsd_reset(state)
  292:     void *state;
  293: {
  294:     struct bsd_db *db = (struct bsd_db *) state;
  295: 
  296:     db->seqno = 0;
  297:     bsd_clear(db);
  298:     db->clear_count = 0;
  299: }
  300: 
  301: /*
  302:  * Allocate space for a (de) compressor.
  303:  */
  304: static void *
  305: bsd_alloc(options, opt_len, decomp)
  306:     u_char *options;
  307:     int opt_len, decomp;
  308: {
  309:     int bits;
  310:     u_int newlen, hsize, hshift, maxmaxcode;
  311:     struct bsd_db *db;
  312: 
  313:     if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
  314: 	|| options[1] != CILEN_BSD_COMPRESS
  315: 	|| BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  316: 	return NULL;
  317:     bits = BSD_NBITS(options[2]);
  318:     switch (bits) {
  319:     case 9:			/* needs 82152 for both directions */
  320:     case 10:			/* needs 84144 */
  321:     case 11:			/* needs 88240 */
  322:     case 12:			/* needs 96432 */
  323: 	hsize = 5003;
  324: 	hshift = 4;
  325: 	break;
  326:     case 13:			/* needs 176784 */
  327: 	hsize = 9001;
  328: 	hshift = 5;
  329: 	break;
  330:     case 14:			/* needs 353744 */
  331: 	hsize = 18013;
  332: 	hshift = 6;
  333: 	break;
  334:     case 15:			/* needs 691440 */
  335: 	hsize = 35023;
  336: 	hshift = 7;
  337: 	break;
  338:     case 16:			/* needs 1366160--far too much, */
  339: 	/* hsize = 69001; */	/* and 69001 is too big for cptr */
  340: 	/* hshift = 8; */	/* in struct bsd_db */
  341: 	/* break; */
  342:     default:
  343: 	return NULL;
  344:     }
  345: 
  346:     maxmaxcode = MAXCODE(bits);
  347:     newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0]));
  348:     MALLOC(db, struct bsd_db *, newlen, M_DEVBUF, M_WAITOK);
  349:     bzero(db, sizeof(*db) - sizeof(db->dict));
  350: 
  351:     if (!decomp) {
  352: 	db->lens = NULL;
  353:     } else {
  354: 	MALLOC(db->lens, u_int16_t *, (maxmaxcode+1) * sizeof(db->lens[0]),
  355: 	       M_DEVBUF, M_WAITOK);
  356:     }
  357: 
  358:     db->totlen = newlen;
  359:     db->hsize = hsize;
  360:     db->hshift = hshift;
  361:     db->maxmaxcode = maxmaxcode;
  362:     db->maxbits = bits;
  363: 
  364:     return (void *) db;
  365: }
  366: 
  367: static void
  368: bsd_free(state)
  369:     void *state;
  370: {
  371:     struct bsd_db *db = (struct bsd_db *) state;
  372: 
  373:     if (db->lens)
  374: 	free(db->lens, M_DEVBUF);
  375:     free(db, M_DEVBUF);
  376: }
  377: 
  378: static void *
  379: bsd_comp_alloc(options, opt_len)
  380:     u_char *options;
  381:     int opt_len;
  382: {
  383:     return bsd_alloc(options, opt_len, 0);
  384: }
  385: 
  386: static void *
  387: bsd_decomp_alloc(options, opt_len)
  388:     u_char *options;
  389:     int opt_len;
  390: {
  391:     return bsd_alloc(options, opt_len, 1);
  392: }
  393: 
  394: /*
  395:  * Initialize the database.
  396:  */
  397: static int
  398: bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp)
  399:     struct bsd_db *db;
  400:     u_char *options;
  401:     int opt_len, unit, hdrlen, mru, debug, decomp;
  402: {
  403:     int i;
  404: 
  405:     if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
  406: 	|| options[1] != CILEN_BSD_COMPRESS
  407: 	|| BSD_VERSION(options[2]) != BSD_CURRENT_VERSION
  408: 	|| BSD_NBITS(options[2]) != db->maxbits
  409: 	|| (decomp && db->lens == NULL))
  410: 	return 0;
  411: 
  412:     if (decomp) {
  413: 	i = LAST+1;
  414: 	while (i != 0)
  415: 	    db->lens[--i] = 1;
  416:     }
  417:     i = db->hsize;
  418:     while (i != 0) {
  419: 	db->dict[--i].codem1 = BADCODEM1;
  420: 	db->dict[i].cptr = 0;
  421:     }
  422: 
  423:     db->unit = unit;
  424:     db->hdrlen = hdrlen;
  425:     db->mru = mru;
  426: #ifndef DEBUG
  427:     if (debug)
  428: #endif
  429: 	db->debug = 1;
  430: 
  431:     bsd_reset(db);
  432: 
  433:     return 1;
  434: }
  435: 
  436: static int
  437: bsd_comp_init(state, options, opt_len, unit, hdrlen, debug)
  438:     void *state;
  439:     u_char *options;
  440:     int opt_len, unit, hdrlen, debug;
  441: {
  442:     return bsd_init((struct bsd_db *) state, options, opt_len,
  443: 		    unit, hdrlen, 0, debug, 0);
  444: }
  445: 
  446: static int
  447: bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug)
  448:     void *state;
  449:     u_char *options;
  450:     int opt_len, unit, hdrlen, mru, debug;
  451: {
  452:     return bsd_init((struct bsd_db *) state, options, opt_len,
  453: 		    unit, hdrlen, mru, debug, 1);
  454: }
  455: 
  456: 
  457: /*
  458:  * compress a packet
  459:  *	One change from the BSD compress command is that when the
  460:  *	code size expands, we do not output a bunch of padding.
  461:  */
  462: int					/* new slen */
  463: bsd_compress(state, mret, mp, slen, maxolen)
  464:     void *state;
  465:     struct mbuf **mret;		/* return compressed mbuf chain here */
  466:     struct mbuf *mp;		/* from here */
  467:     int slen;			/* uncompressed length */
  468:     int maxolen;		/* max compressed length */
  469: {
  470:     struct bsd_db *db = (struct bsd_db *) state;
  471:     int hshift = db->hshift;
  472:     u_int max_ent = db->max_ent;
  473:     u_int n_bits = db->n_bits;
  474:     u_int bitno = 32;
  475:     u_int32_t accm = 0, fcode;
  476:     struct bsd_dict *dictp;
  477:     u_char c;
  478:     int hval, disp, ent, ilen;
  479:     u_char *rptr, *wptr;
  480:     u_char *cp_end;
  481:     int olen;
  482:     struct mbuf *m;
  483: 
  484: #define PUTBYTE(v) {					\
  485:     ++olen;						\
  486:     if (wptr) {						\
  487: 	*wptr++ = (v);					\
  488: 	if (wptr >= cp_end) {				\
  489: 	    m->m_len = wptr - mtod(m, u_char *);	\
  490: 	    MGET(m->m_next, M_DONTWAIT, MT_DATA);	\
  491: 	    m = m->m_next;				\
  492: 	    if (m) {					\
  493: 		m->m_len = 0;				\
  494: 		if (maxolen - olen > MLEN)		\
  495: 		    MCLGET(m, M_DONTWAIT);		\
  496: 		wptr = mtod(m, u_char *);		\
  497: 		cp_end = wptr + M_TRAILINGSPACE(m);	\
  498: 	    } else					\
  499: 		wptr = NULL;				\
  500: 	}						\
  501:     }							\
  502: }
  503: 
  504: #define OUTPUT(ent) {					\
  505:     bitno -= n_bits;					\
  506:     accm |= ((ent) << bitno);				\
  507:     do {						\
  508: 	PUTBYTE(accm >> 24);				\
  509: 	accm <<= 8;					\
  510: 	bitno += 8;					\
  511:     } while (bitno <= 24);				\
  512: }
  513: 
  514:     /*
  515:      * If the protocol is not in the range we're interested in,
  516:      * just return without compressing the packet.  If it is,
  517:      * the protocol becomes the first byte to compress.
  518:      */
  519:     rptr = mtod(mp, u_char *);
  520:     ent = PPP_PROTOCOL(rptr);
  521:     if (ent < 0x21 || ent > 0xf9) {
  522: 	*mret = NULL;
  523: 	return slen;
  524:     }
  525: 
  526:     /* Don't generate compressed packets which are larger than
  527:        the uncompressed packet. */
  528:     if (maxolen > slen)
  529: 	maxolen = slen;
  530: 
  531:     /* Allocate one mbuf to start with. */
  532:     MGET(m, M_DONTWAIT, MT_DATA);
  533:     *mret = m;
  534:     if (m != NULL) {
  535: 	m->m_len = 0;
  536: 	if (maxolen + db->hdrlen > MLEN)
  537: 	    MCLGET(m, M_DONTWAIT);
  538: 	m->m_data += db->hdrlen;
  539: 	wptr = mtod(m, u_char *);
  540: 	cp_end = wptr + M_TRAILINGSPACE(m);
  541:     } else
  542: 	wptr = cp_end = NULL;
  543: 
  544:     /*
  545:      * Copy the PPP header over, changing the protocol,
  546:      * and install the 2-byte packet sequence number.
  547:      */
  548:     if (wptr) {
  549: 	*wptr++ = PPP_ADDRESS(rptr);	/* assumes the ppp header is */
  550: 	*wptr++ = PPP_CONTROL(rptr);	/* all in one mbuf */
  551: 	*wptr++ = 0;			/* change the protocol */
  552: 	*wptr++ = PPP_COMP;
  553: 	*wptr++ = db->seqno >> 8;
  554: 	*wptr++ = db->seqno;
  555:     }
  556:     ++db->seqno;
  557: 
  558:     olen = 0;
  559:     rptr += PPP_HDRLEN;
  560:     slen = mp->m_len - PPP_HDRLEN;
  561:     ilen = slen + 1;
  562:     for (;;) {
  563: 	if (slen <= 0) {
  564: 	    mp = mp->m_next;
  565: 	    if (!mp)
  566: 		break;
  567: 	    rptr = mtod(mp, u_char *);
  568: 	    slen = mp->m_len;
  569: 	    if (!slen)
  570: 		continue;   /* handle 0-length buffers */
  571: 	    ilen += slen;
  572: 	}
  573: 
  574: 	slen--;
  575: 	c = *rptr++;
  576: 	fcode = BSD_KEY(ent, c);
  577: 	hval = BSD_HASH(ent, c, hshift);
  578: 	dictp = &db->dict[hval];
  579: 
  580: 	/* Validate and then check the entry. */
  581: 	if (dictp->codem1 >= max_ent)
  582: 	    goto nomatch;
  583: 	if (dictp->f.fcode == fcode) {
  584: 	    ent = dictp->codem1+1;
  585: 	    continue;	/* found (prefix,suffix) */
  586: 	}
  587: 
  588: 	/* continue probing until a match or invalid entry */
  589: 	disp = (hval == 0) ? 1 : hval;
  590: 	do {
  591: 	    hval += disp;
  592: 	    if (hval >= db->hsize)
  593: 		hval -= db->hsize;
  594: 	    dictp = &db->dict[hval];
  595: 	    if (dictp->codem1 >= max_ent)
  596: 		goto nomatch;
  597: 	} while (dictp->f.fcode != fcode);
  598: 	ent = dictp->codem1 + 1;	/* finally found (prefix,suffix) */
  599: 	continue;
  600: 
  601:     nomatch:
  602: 	OUTPUT(ent);		/* output the prefix */
  603: 
  604: 	/* code -> hashtable */
  605: 	if (max_ent < db->maxmaxcode) {
  606: 	    struct bsd_dict *dictp2;
  607: 	    /* expand code size if needed */
  608: 	    if (max_ent >= MAXCODE(n_bits))
  609: 		db->n_bits = ++n_bits;
  610: 
  611: 	    /* Invalidate old hash table entry using
  612: 	     * this code, and then take it over.
  613: 	     */
  614: 	    dictp2 = &db->dict[max_ent+1];
  615: 	    if (db->dict[dictp2->cptr].codem1 == max_ent)
  616: 		db->dict[dictp2->cptr].codem1 = BADCODEM1;
  617: 	    dictp2->cptr = hval;
  618: 	    dictp->codem1 = max_ent;
  619: 	    dictp->f.fcode = fcode;
  620: 
  621: 	    db->max_ent = ++max_ent;
  622: 	}
  623: 	ent = c;
  624:     }
  625: 
  626:     OUTPUT(ent);		/* output the last code */
  627:     db->bytes_out += olen;
  628:     db->in_count += ilen;
  629:     if (bitno < 32)
  630: 	++db->bytes_out;	/* count complete bytes */
  631: 
  632:     if (bsd_check(db))
  633: 	OUTPUT(CLEAR);		/* do not count the CLEAR */
  634: 
  635:     /*
  636:      * Pad dribble bits of last code with ones.
  637:      * Do not emit a completely useless byte of ones.
  638:      */
  639:     if (bitno != 32)
  640: 	PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
  641: 
  642:     if (m != NULL) {
  643: 	m->m_len = wptr - mtod(m, u_char *);
  644: 	m->m_next = NULL;
  645:     }
  646: 
  647:     /*
  648:      * Increase code size if we would have without the packet
  649:      * boundary and as the decompressor will.
  650:      */
  651:     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  652: 	db->n_bits++;
  653: 
  654:     db->uncomp_bytes += ilen;
  655:     ++db->uncomp_count;
  656:     if (olen + PPP_HDRLEN + BSD_OVHD > maxolen) {
  657: 	/* throw away the compressed stuff if it is longer than uncompressed */
  658: 	if (*mret != NULL) {
  659: 	    m_freem(*mret);
  660: 	    *mret = NULL;
  661: 	}
  662: 	++db->incomp_count;
  663: 	db->incomp_bytes += ilen;
  664:     } else {
  665: 	++db->comp_count;
  666: 	db->comp_bytes += olen + BSD_OVHD;
  667:     }
  668: 
  669:     return olen + PPP_HDRLEN + BSD_OVHD;
  670: #undef OUTPUT
  671: #undef PUTBYTE
  672: }
  673: 
  674: 
  675: /*
  676:  * Update the "BSD Compress" dictionary on the receiver for
  677:  * incompressible data by pretending to compress the incoming data.
  678:  */
  679: static void
  680: bsd_incomp(state, dmsg)
  681:     void *state;
  682:     struct mbuf *dmsg;
  683: {
  684:     struct bsd_db *db = (struct bsd_db *) state;
  685:     u_int hshift = db->hshift;
  686:     u_int max_ent = db->max_ent;
  687:     u_int n_bits = db->n_bits;
  688:     struct bsd_dict *dictp;
  689:     u_int32_t fcode;
  690:     u_char c;
  691:     u_int32_t hval, disp;
  692:     int slen, ilen;
  693:     u_int bitno = 7;
  694:     u_char *rptr;
  695:     u_int ent;
  696: 
  697:     /*
  698:      * If the protocol is not in the range we're interested in,
  699:      * just return without looking at the packet.  If it is,
  700:      * the protocol becomes the first byte to "compress".
  701:      */
  702:     rptr = mtod(dmsg, u_char *);
  703:     ent = PPP_PROTOCOL(rptr);
  704:     if (ent < 0x21 || ent > 0xf9)
  705: 	return;
  706: 
  707:     db->seqno++;
  708:     ilen = 1;		/* count the protocol as 1 byte */
  709:     rptr += PPP_HDRLEN;
  710:     slen = dmsg->m_len - PPP_HDRLEN;
  711:     for (;;) {
  712: 	if (slen <= 0) {
  713: 	    dmsg = dmsg->m_next;
  714: 	    if (!dmsg)
  715: 		break;
  716: 	    rptr = mtod(dmsg, u_char *);
  717: 	    slen = dmsg->m_len;
  718: 	    continue;
  719: 	}
  720: 	ilen += slen;
  721: 
  722: 	do {
  723: 	    c = *rptr++;
  724: 	    fcode = BSD_KEY(ent, c);
  725: 	    hval = BSD_HASH(ent, c, hshift);
  726: 	    dictp = &db->dict[hval];
  727: 
  728: 	    /* validate and then check the entry */
  729: 	    if (dictp->codem1 >= max_ent)
  730: 		goto nomatch;
  731: 	    if (dictp->f.fcode == fcode) {
  732: 		ent = dictp->codem1+1;
  733: 		continue;   /* found (prefix,suffix) */
  734: 	    }
  735: 
  736: 	    /* continue probing until a match or invalid entry */
  737: 	    disp = (hval == 0) ? 1 : hval;
  738: 	    do {
  739: 		hval += disp;
  740: 		if (hval >= db->hsize)
  741: 		    hval -= db->hsize;
  742: 		dictp = &db->dict[hval];
  743: 		if (dictp->codem1 >= max_ent)
  744: 		    goto nomatch;
  745: 	    } while (dictp->f.fcode != fcode);
  746: 	    ent = dictp->codem1+1;
  747: 	    continue;	/* finally found (prefix,suffix) */
  748: 
  749: 	nomatch:		/* output (count) the prefix */
  750: 	    bitno += n_bits;
  751: 
  752: 	    /* code -> hashtable */
  753: 	    if (max_ent < db->maxmaxcode) {
  754: 		struct bsd_dict *dictp2;
  755: 		/* expand code size if needed */
  756: 		if (max_ent >= MAXCODE(n_bits))
  757: 		    db->n_bits = ++n_bits;
  758: 
  759: 		/* Invalidate previous hash table entry
  760: 		 * assigned this code, and then take it over.
  761: 		 */
  762: 		dictp2 = &db->dict[max_ent+1];
  763: 		if (db->dict[dictp2->cptr].codem1 == max_ent)
  764: 		    db->dict[dictp2->cptr].codem1 = BADCODEM1;
  765: 		dictp2->cptr = hval;
  766: 		dictp->codem1 = max_ent;
  767: 		dictp->f.fcode = fcode;
  768: 
  769: 		db->max_ent = ++max_ent;
  770: 		db->lens[max_ent] = db->lens[ent]+1;
  771: 	    }
  772: 	    ent = c;
  773: 	} while (--slen != 0);
  774:     }
  775:     bitno += n_bits;		/* output (count) the last code */
  776:     db->bytes_out += bitno/8;
  777:     db->in_count += ilen;
  778:     (void)bsd_check(db);
  779: 
  780:     ++db->incomp_count;
  781:     db->incomp_bytes += ilen;
  782:     ++db->uncomp_count;
  783:     db->uncomp_bytes += ilen;
  784: 
  785:     /* Increase code size if we would have without the packet
  786:      * boundary and as the decompressor will.
  787:      */
  788:     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  789: 	db->n_bits++;
  790: }
  791: 
  792: 
  793: /*
  794:  * Decompress "BSD Compress".
  795:  *
  796:  * Because of patent problems, we return DECOMP_ERROR for errors
  797:  * found by inspecting the input data and for system problems, but
  798:  * DECOMP_FATALERROR for any errors which could possibly be said to
  799:  * be being detected "after" decompression.  For DECOMP_ERROR,
  800:  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
  801:  * infringing a patent of Motorola's if we do, so we take CCP down
  802:  * instead.
  803:  *
  804:  * Given that the frame has the correct sequence number and a good FCS,
  805:  * errors such as invalid codes in the input most likely indicate a
  806:  * bug, so we return DECOMP_FATALERROR for them in order to turn off
  807:  * compression, even though they are detected by inspecting the input.
  808:  */
  809: int
  810: bsd_decompress(state, cmp, dmpp)
  811:     void *state;
  812:     struct mbuf *cmp, **dmpp;
  813: {
  814:     struct bsd_db *db = (struct bsd_db *) state;
  815:     u_int max_ent = db->max_ent;
  816:     u_int32_t accm = 0;
  817:     u_int bitno = 32;		/* 1st valid bit in accm */
  818:     u_int n_bits = db->n_bits;
  819:     u_int tgtbitno = 32-n_bits;	/* bitno when we have a code */
  820:     struct bsd_dict *dictp;
  821:     int explen, i, seq, len;
  822:     u_int incode, oldcode, finchar;
  823:     u_char *p, *rptr, *wptr;
  824:     struct mbuf *m, *dmp, *mret;
  825:     int adrs, ctrl, ilen;
  826:     int space, codelen, extra;
  827: 
  828:     /*
  829:      * Save the address/control from the PPP header
  830:      * and then get the sequence number.
  831:      */
  832:     *dmpp = NULL;
  833:     rptr = mtod(cmp, u_char *);
  834:     adrs = PPP_ADDRESS(rptr);
  835:     ctrl = PPP_CONTROL(rptr);
  836:     rptr += PPP_HDRLEN;
  837:     len = cmp->m_len - PPP_HDRLEN;
  838:     seq = 0;
  839:     for (i = 0; i < 2; ++i) {
  840: 	while (len <= 0) {
  841: 	    cmp = cmp->m_next;
  842: 	    if (cmp == NULL)
  843: 		return DECOMP_ERROR;
  844: 	    rptr = mtod(cmp, u_char *);
  845: 	    len = cmp->m_len;
  846: 	}
  847: 	seq = (seq << 8) + *rptr++;
  848: 	--len;
  849:     }
  850: 
  851:     /*
  852:      * Check the sequence number and give up if it differs from
  853:      * the value we're expecting.
  854:      */
  855:     if (seq != db->seqno) {
  856: 	if (db->debug)
  857: 	    printf("bsd_decomp%d: bad sequence # %d, expected %d\n",
  858: 		   db->unit, seq, db->seqno - 1);
  859: 	return DECOMP_ERROR;
  860:     }
  861:     ++db->seqno;
  862: 
  863:     /*
  864:      * Allocate one mbuf to start with.
  865:      */
  866:     MGETHDR(dmp, M_DONTWAIT, MT_DATA);
  867:     if (dmp == NULL)
  868: 	return DECOMP_ERROR;
  869:     mret = dmp;
  870:     dmp->m_len = 0;
  871:     dmp->m_next = NULL;
  872:     MCLGET(dmp, M_DONTWAIT);
  873:     dmp->m_data += db->hdrlen;
  874:     wptr = mtod(dmp, u_char *);
  875:     space = M_TRAILINGSPACE(dmp) - PPP_HDRLEN + 1;
  876: 
  877:     /*
  878:      * Fill in the ppp header, but not the last byte of the protocol
  879:      * (that comes from the decompressed data).
  880:      */
  881:     wptr[0] = adrs;
  882:     wptr[1] = ctrl;
  883:     wptr[2] = 0;
  884:     wptr += PPP_HDRLEN - 1;
  885: 
  886:     ilen = len;
  887:     oldcode = CLEAR;
  888:     explen = 0;
  889:     for (;;) {
  890: 	if (len == 0) {
  891: 	    cmp = cmp->m_next;
  892: 	    if (!cmp)		/* quit at end of message */
  893: 		break;
  894: 	    rptr = mtod(cmp, u_char *);
  895: 	    len = cmp->m_len;
  896: 	    ilen += len;
  897: 	    continue;		/* handle 0-length buffers */
  898: 	}
  899: 
  900: 	/*
  901: 	 * Accumulate bytes until we have a complete code.
  902: 	 * Then get the next code, relying on the 32-bit,
  903: 	 * unsigned accm to mask the result.
  904: 	 */
  905: 	bitno -= 8;
  906: 	accm |= *rptr++ << bitno;
  907: 	--len;
  908: 	if (tgtbitno < bitno)
  909: 	    continue;
  910: 	incode = accm >> tgtbitno;
  911: 	accm <<= n_bits;
  912: 	bitno += n_bits;
  913: 
  914: 	if (incode == CLEAR) {
  915: 	    /*
  916: 	     * The dictionary must only be cleared at
  917: 	     * the end of a packet.  But there could be an
  918: 	     * empty mbuf at the end.
  919: 	     */
  920: 	    if (len > 0 || cmp->m_next != NULL) {
  921: 		while ((cmp = cmp->m_next) != NULL)
  922: 		    len += cmp->m_len;
  923: 		if (len > 0) {
  924: 		    m_freem(mret);
  925: 		    if (db->debug)
  926: 			printf("bsd_decomp%d: bad CLEAR\n", db->unit);
  927: 		    return DECOMP_FATALERROR;	/* probably a bug */
  928: 		}
  929: 	    }
  930: 	    bsd_clear(db);
  931: 	    explen = ilen = 0;
  932: 	    break;
  933: 	}
  934: 
  935: 	if (incode > max_ent + 2 || incode > db->maxmaxcode
  936: 	    || (incode > max_ent && oldcode == CLEAR)) {
  937: 	    m_freem(mret);
  938: 	    if (db->debug) {
  939: 		printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
  940: 		       db->unit, incode, oldcode);
  941: 		printf("max_ent=0x%x explen=%d seqno=%d\n",
  942: 		       max_ent, explen, db->seqno);
  943: 	    }
  944: 	    return DECOMP_FATALERROR;	/* probably a bug */
  945: 	}
  946: 
  947: 	/* Special case for KwKwK string. */
  948: 	if (incode > max_ent) {
  949: 	    finchar = oldcode;
  950: 	    extra = 1;
  951: 	} else {
  952: 	    finchar = incode;
  953: 	    extra = 0;
  954: 	}
  955: 
  956: 	codelen = db->lens[finchar];
  957: 	explen += codelen + extra;
  958: 	if (explen > db->mru + 1) {
  959: 	    m_freem(mret);
  960: 	    if (db->debug) {
  961: 		printf("bsd_decomp%d: ran out of mru\n", db->unit);
  962: #ifdef DEBUG
  963: 		while ((cmp = cmp->m_next) != NULL)
  964: 		    len += cmp->m_len;
  965: 		printf("  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
  966: 		       len, finchar, codelen, explen);
  967: #endif
  968: 	    }
  969: 	    return DECOMP_FATALERROR;
  970: 	}
  971: 
  972: 	/*
  973: 	 * For simplicity, the decoded characters go in a single mbuf,
  974: 	 * so we allocate a single extra cluster mbuf if necessary.
  975: 	 */
  976: 	if ((space -= codelen + extra) < 0) {
  977: 	    dmp->m_len = wptr - mtod(dmp, u_char *);
  978: 	    MGET(m, M_DONTWAIT, MT_DATA);
  979: 	    if (m == NULL) {
  980: 		m_freem(mret);
  981: 		return DECOMP_ERROR;
  982: 	    }
  983: 	    m->m_len = 0;
  984: 	    m->m_next = NULL;
  985: 	    dmp->m_next = m;
  986: 	    MCLGET(m, M_DONTWAIT);
  987: 	    space = M_TRAILINGSPACE(m) - (codelen + extra);
  988: 	    if (space < 0) {
  989: 		/* now that's what I call *compression*. */
  990: 		m_freem(mret);
  991: 		return DECOMP_ERROR;
  992: 	    }
  993: 	    dmp = m;
  994: 	    wptr = mtod(dmp, u_char *);
  995: 	}
  996: 
  997: 	/*
  998: 	 * Decode this code and install it in the decompressed buffer.
  999: 	 */
 1000: 	p = (wptr += codelen);
 1001: 	while (finchar > LAST) {
 1002: 	    dictp = &db->dict[db->dict[finchar].cptr];
 1003: #ifdef DEBUG
 1004: 	    if (--codelen <= 0 || dictp->codem1 != finchar-1)
 1005: 		goto bad;
 1006: #endif
 1007: 	    *--p = dictp->f.hs.suffix;
 1008: 	    finchar = dictp->f.hs.prefix;
 1009: 	}
 1010: 	*--p = finchar;
 1011: 
 1012: #ifdef DEBUG
 1013: 	if (--codelen != 0)
 1014: 	    printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
 1015: 		   db->unit, codelen, incode, max_ent);
 1016: #endif
 1017: 
 1018: 	if (extra)		/* the KwKwK case again */
 1019: 	    *wptr++ = finchar;
 1020: 
 1021: 	/*
 1022: 	 * If not first code in a packet, and
 1023: 	 * if not out of code space, then allocate a new code.
 1024: 	 *
 1025: 	 * Keep the hash table correct so it can be used
 1026: 	 * with uncompressed packets.
 1027: 	 */
 1028: 	if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
 1029: 	    struct bsd_dict *dictp2;
 1030: 	    u_int32_t fcode;
 1031: 	    u_int32_t hval, disp;
 1032: 
 1033: 	    fcode = BSD_KEY(oldcode,finchar);
 1034: 	    hval = BSD_HASH(oldcode,finchar,db->hshift);
 1035: 	    dictp = &db->dict[hval];
 1036: 
 1037: 	    /* look for a free hash table entry */
 1038: 	    if (dictp->codem1 < max_ent) {
 1039: 		disp = (hval == 0) ? 1 : hval;
 1040: 		do {
 1041: 		    hval += disp;
 1042: 		    if (hval >= db->hsize)
 1043: 			hval -= db->hsize;
 1044: 		    dictp = &db->dict[hval];
 1045: 		} while (dictp->codem1 < max_ent);
 1046: 	    }
 1047: 
 1048: 	    /*
 1049: 	     * Invalidate previous hash table entry
 1050: 	     * assigned this code, and then take it over
 1051: 	     */
 1052: 	    dictp2 = &db->dict[max_ent+1];
 1053: 	    if (db->dict[dictp2->cptr].codem1 == max_ent) {
 1054: 		db->dict[dictp2->cptr].codem1 = BADCODEM1;
 1055: 	    }
 1056: 	    dictp2->cptr = hval;
 1057: 	    dictp->codem1 = max_ent;
 1058: 	    dictp->f.fcode = fcode;
 1059: 
 1060: 	    db->max_ent = ++max_ent;
 1061: 	    db->lens[max_ent] = db->lens[oldcode]+1;
 1062: 
 1063: 	    /* Expand code size if needed. */
 1064: 	    if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
 1065: 		db->n_bits = ++n_bits;
 1066: 		tgtbitno = 32-n_bits;
 1067: 	    }
 1068: 	}
 1069: 	oldcode = incode;
 1070:     }
 1071:     dmp->m_len = wptr - mtod(dmp, u_char *);
 1072: 
 1073:     /*
 1074:      * Keep the checkpoint right so that incompressible packets
 1075:      * clear the dictionary at the right times.
 1076:      */
 1077:     db->bytes_out += ilen;
 1078:     db->in_count += explen;
 1079:     if (bsd_check(db) && db->debug) {
 1080: 	printf("bsd_decomp%d: peer should have cleared dictionary\n",
 1081: 	       db->unit);
 1082:     }
 1083: 
 1084:     ++db->comp_count;
 1085:     db->comp_bytes += ilen + BSD_OVHD;
 1086:     ++db->uncomp_count;
 1087:     db->uncomp_bytes += explen;
 1088: 
 1089:     *dmpp = mret;
 1090:     return DECOMP_OK;
 1091: 
 1092: #ifdef DEBUG
 1093:  bad:
 1094:     if (codelen <= 0) {
 1095: 	printf("bsd_decomp%d: fell off end of chain ", db->unit);
 1096: 	printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
 1097: 	       incode, finchar, db->dict[finchar].cptr, max_ent);
 1098:     } else if (dictp->codem1 != finchar-1) {
 1099: 	printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",
 1100: 	       db->unit, incode, finchar);
 1101: 	printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode,
 1102: 	       db->dict[finchar].cptr, dictp->codem1);
 1103:     }
 1104:     m_freem(mret);
 1105:     return DECOMP_FATALERROR;
 1106: #endif /* DEBUG */
 1107: }
 1108: #endif /* DO_BSD_COMPRESS */