File:  [DragonFly] / src / sys / net / bsd_comp.c
Revision 1.4: download - view: text, annotated - select for diffs
Tue Aug 26 20:49:47 2003 UTC (11 years, 3 months ago) by rob
Branches: MAIN
CVS tags: HEAD
__P() removal

    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.4 2003/08/26 20:49:47 rob 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_NOWAIT);
  349:     if (!db)
  350: 	return NULL;
  351:     bzero(db, sizeof(*db) - sizeof(db->dict));
  352: 
  353:     if (!decomp) {
  354: 	db->lens = NULL;
  355:     } else {
  356: 	MALLOC(db->lens, u_int16_t *, (maxmaxcode+1) * sizeof(db->lens[0]),
  357: 	       M_DEVBUF, M_NOWAIT);
  358: 	if (!db->lens) {
  359: 	    free(db, M_DEVBUF);
  360: 	    return NULL;
  361: 	}
  362:     }
  363: 
  364:     db->totlen = newlen;
  365:     db->hsize = hsize;
  366:     db->hshift = hshift;
  367:     db->maxmaxcode = maxmaxcode;
  368:     db->maxbits = bits;
  369: 
  370:     return (void *) db;
  371: }
  372: 
  373: static void
  374: bsd_free(state)
  375:     void *state;
  376: {
  377:     struct bsd_db *db = (struct bsd_db *) state;
  378: 
  379:     if (db->lens)
  380: 	free(db->lens, M_DEVBUF);
  381:     free(db, M_DEVBUF);
  382: }
  383: 
  384: static void *
  385: bsd_comp_alloc(options, opt_len)
  386:     u_char *options;
  387:     int opt_len;
  388: {
  389:     return bsd_alloc(options, opt_len, 0);
  390: }
  391: 
  392: static void *
  393: bsd_decomp_alloc(options, opt_len)
  394:     u_char *options;
  395:     int opt_len;
  396: {
  397:     return bsd_alloc(options, opt_len, 1);
  398: }
  399: 
  400: /*
  401:  * Initialize the database.
  402:  */
  403: static int
  404: bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp)
  405:     struct bsd_db *db;
  406:     u_char *options;
  407:     int opt_len, unit, hdrlen, mru, debug, decomp;
  408: {
  409:     int i;
  410: 
  411:     if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
  412: 	|| options[1] != CILEN_BSD_COMPRESS
  413: 	|| BSD_VERSION(options[2]) != BSD_CURRENT_VERSION
  414: 	|| BSD_NBITS(options[2]) != db->maxbits
  415: 	|| (decomp && db->lens == NULL))
  416: 	return 0;
  417: 
  418:     if (decomp) {
  419: 	i = LAST+1;
  420: 	while (i != 0)
  421: 	    db->lens[--i] = 1;
  422:     }
  423:     i = db->hsize;
  424:     while (i != 0) {
  425: 	db->dict[--i].codem1 = BADCODEM1;
  426: 	db->dict[i].cptr = 0;
  427:     }
  428: 
  429:     db->unit = unit;
  430:     db->hdrlen = hdrlen;
  431:     db->mru = mru;
  432: #ifndef DEBUG
  433:     if (debug)
  434: #endif
  435: 	db->debug = 1;
  436: 
  437:     bsd_reset(db);
  438: 
  439:     return 1;
  440: }
  441: 
  442: static int
  443: bsd_comp_init(state, options, opt_len, unit, hdrlen, debug)
  444:     void *state;
  445:     u_char *options;
  446:     int opt_len, unit, hdrlen, debug;
  447: {
  448:     return bsd_init((struct bsd_db *) state, options, opt_len,
  449: 		    unit, hdrlen, 0, debug, 0);
  450: }
  451: 
  452: static int
  453: bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug)
  454:     void *state;
  455:     u_char *options;
  456:     int opt_len, unit, hdrlen, mru, debug;
  457: {
  458:     return bsd_init((struct bsd_db *) state, options, opt_len,
  459: 		    unit, hdrlen, mru, debug, 1);
  460: }
  461: 
  462: 
  463: /*
  464:  * compress a packet
  465:  *	One change from the BSD compress command is that when the
  466:  *	code size expands, we do not output a bunch of padding.
  467:  */
  468: int					/* new slen */
  469: bsd_compress(state, mret, mp, slen, maxolen)
  470:     void *state;
  471:     struct mbuf **mret;		/* return compressed mbuf chain here */
  472:     struct mbuf *mp;		/* from here */
  473:     int slen;			/* uncompressed length */
  474:     int maxolen;		/* max compressed length */
  475: {
  476:     struct bsd_db *db = (struct bsd_db *) state;
  477:     int hshift = db->hshift;
  478:     u_int max_ent = db->max_ent;
  479:     u_int n_bits = db->n_bits;
  480:     u_int bitno = 32;
  481:     u_int32_t accm = 0, fcode;
  482:     struct bsd_dict *dictp;
  483:     u_char c;
  484:     int hval, disp, ent, ilen;
  485:     u_char *rptr, *wptr;
  486:     u_char *cp_end;
  487:     int olen;
  488:     struct mbuf *m;
  489: 
  490: #define PUTBYTE(v) {					\
  491:     ++olen;						\
  492:     if (wptr) {						\
  493: 	*wptr++ = (v);					\
  494: 	if (wptr >= cp_end) {				\
  495: 	    m->m_len = wptr - mtod(m, u_char *);	\
  496: 	    MGET(m->m_next, M_DONTWAIT, MT_DATA);	\
  497: 	    m = m->m_next;				\
  498: 	    if (m) {					\
  499: 		m->m_len = 0;				\
  500: 		if (maxolen - olen > MLEN)		\
  501: 		    MCLGET(m, M_DONTWAIT);		\
  502: 		wptr = mtod(m, u_char *);		\
  503: 		cp_end = wptr + M_TRAILINGSPACE(m);	\
  504: 	    } else					\
  505: 		wptr = NULL;				\
  506: 	}						\
  507:     }							\
  508: }
  509: 
  510: #define OUTPUT(ent) {					\
  511:     bitno -= n_bits;					\
  512:     accm |= ((ent) << bitno);				\
  513:     do {						\
  514: 	PUTBYTE(accm >> 24);				\
  515: 	accm <<= 8;					\
  516: 	bitno += 8;					\
  517:     } while (bitno <= 24);				\
  518: }
  519: 
  520:     /*
  521:      * If the protocol is not in the range we're interested in,
  522:      * just return without compressing the packet.  If it is,
  523:      * the protocol becomes the first byte to compress.
  524:      */
  525:     rptr = mtod(mp, u_char *);
  526:     ent = PPP_PROTOCOL(rptr);
  527:     if (ent < 0x21 || ent > 0xf9) {
  528: 	*mret = NULL;
  529: 	return slen;
  530:     }
  531: 
  532:     /* Don't generate compressed packets which are larger than
  533:        the uncompressed packet. */
  534:     if (maxolen > slen)
  535: 	maxolen = slen;
  536: 
  537:     /* Allocate one mbuf to start with. */
  538:     MGET(m, M_DONTWAIT, MT_DATA);
  539:     *mret = m;
  540:     if (m != NULL) {
  541: 	m->m_len = 0;
  542: 	if (maxolen + db->hdrlen > MLEN)
  543: 	    MCLGET(m, M_DONTWAIT);
  544: 	m->m_data += db->hdrlen;
  545: 	wptr = mtod(m, u_char *);
  546: 	cp_end = wptr + M_TRAILINGSPACE(m);
  547:     } else
  548: 	wptr = cp_end = NULL;
  549: 
  550:     /*
  551:      * Copy the PPP header over, changing the protocol,
  552:      * and install the 2-byte packet sequence number.
  553:      */
  554:     if (wptr) {
  555: 	*wptr++ = PPP_ADDRESS(rptr);	/* assumes the ppp header is */
  556: 	*wptr++ = PPP_CONTROL(rptr);	/* all in one mbuf */
  557: 	*wptr++ = 0;			/* change the protocol */
  558: 	*wptr++ = PPP_COMP;
  559: 	*wptr++ = db->seqno >> 8;
  560: 	*wptr++ = db->seqno;
  561:     }
  562:     ++db->seqno;
  563: 
  564:     olen = 0;
  565:     rptr += PPP_HDRLEN;
  566:     slen = mp->m_len - PPP_HDRLEN;
  567:     ilen = slen + 1;
  568:     for (;;) {
  569: 	if (slen <= 0) {
  570: 	    mp = mp->m_next;
  571: 	    if (!mp)
  572: 		break;
  573: 	    rptr = mtod(mp, u_char *);
  574: 	    slen = mp->m_len;
  575: 	    if (!slen)
  576: 		continue;   /* handle 0-length buffers */
  577: 	    ilen += slen;
  578: 	}
  579: 
  580: 	slen--;
  581: 	c = *rptr++;
  582: 	fcode = BSD_KEY(ent, c);
  583: 	hval = BSD_HASH(ent, c, hshift);
  584: 	dictp = &db->dict[hval];
  585: 
  586: 	/* Validate and then check the entry. */
  587: 	if (dictp->codem1 >= max_ent)
  588: 	    goto nomatch;
  589: 	if (dictp->f.fcode == fcode) {
  590: 	    ent = dictp->codem1+1;
  591: 	    continue;	/* found (prefix,suffix) */
  592: 	}
  593: 
  594: 	/* continue probing until a match or invalid entry */
  595: 	disp = (hval == 0) ? 1 : hval;
  596: 	do {
  597: 	    hval += disp;
  598: 	    if (hval >= db->hsize)
  599: 		hval -= db->hsize;
  600: 	    dictp = &db->dict[hval];
  601: 	    if (dictp->codem1 >= max_ent)
  602: 		goto nomatch;
  603: 	} while (dictp->f.fcode != fcode);
  604: 	ent = dictp->codem1 + 1;	/* finally found (prefix,suffix) */
  605: 	continue;
  606: 
  607:     nomatch:
  608: 	OUTPUT(ent);		/* output the prefix */
  609: 
  610: 	/* code -> hashtable */
  611: 	if (max_ent < db->maxmaxcode) {
  612: 	    struct bsd_dict *dictp2;
  613: 	    /* expand code size if needed */
  614: 	    if (max_ent >= MAXCODE(n_bits))
  615: 		db->n_bits = ++n_bits;
  616: 
  617: 	    /* Invalidate old hash table entry using
  618: 	     * this code, and then take it over.
  619: 	     */
  620: 	    dictp2 = &db->dict[max_ent+1];
  621: 	    if (db->dict[dictp2->cptr].codem1 == max_ent)
  622: 		db->dict[dictp2->cptr].codem1 = BADCODEM1;
  623: 	    dictp2->cptr = hval;
  624: 	    dictp->codem1 = max_ent;
  625: 	    dictp->f.fcode = fcode;
  626: 
  627: 	    db->max_ent = ++max_ent;
  628: 	}
  629: 	ent = c;
  630:     }
  631: 
  632:     OUTPUT(ent);		/* output the last code */
  633:     db->bytes_out += olen;
  634:     db->in_count += ilen;
  635:     if (bitno < 32)
  636: 	++db->bytes_out;	/* count complete bytes */
  637: 
  638:     if (bsd_check(db))
  639: 	OUTPUT(CLEAR);		/* do not count the CLEAR */
  640: 
  641:     /*
  642:      * Pad dribble bits of last code with ones.
  643:      * Do not emit a completely useless byte of ones.
  644:      */
  645:     if (bitno != 32)
  646: 	PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
  647: 
  648:     if (m != NULL) {
  649: 	m->m_len = wptr - mtod(m, u_char *);
  650: 	m->m_next = NULL;
  651:     }
  652: 
  653:     /*
  654:      * Increase code size if we would have without the packet
  655:      * boundary and as the decompressor will.
  656:      */
  657:     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  658: 	db->n_bits++;
  659: 
  660:     db->uncomp_bytes += ilen;
  661:     ++db->uncomp_count;
  662:     if (olen + PPP_HDRLEN + BSD_OVHD > maxolen) {
  663: 	/* throw away the compressed stuff if it is longer than uncompressed */
  664: 	if (*mret != NULL) {
  665: 	    m_freem(*mret);
  666: 	    *mret = NULL;
  667: 	}
  668: 	++db->incomp_count;
  669: 	db->incomp_bytes += ilen;
  670:     } else {
  671: 	++db->comp_count;
  672: 	db->comp_bytes += olen + BSD_OVHD;
  673:     }
  674: 
  675:     return olen + PPP_HDRLEN + BSD_OVHD;
  676: #undef OUTPUT
  677: #undef PUTBYTE
  678: }
  679: 
  680: 
  681: /*
  682:  * Update the "BSD Compress" dictionary on the receiver for
  683:  * incompressible data by pretending to compress the incoming data.
  684:  */
  685: static void
  686: bsd_incomp(state, dmsg)
  687:     void *state;
  688:     struct mbuf *dmsg;
  689: {
  690:     struct bsd_db *db = (struct bsd_db *) state;
  691:     u_int hshift = db->hshift;
  692:     u_int max_ent = db->max_ent;
  693:     u_int n_bits = db->n_bits;
  694:     struct bsd_dict *dictp;
  695:     u_int32_t fcode;
  696:     u_char c;
  697:     u_int32_t hval, disp;
  698:     int slen, ilen;
  699:     u_int bitno = 7;
  700:     u_char *rptr;
  701:     u_int ent;
  702: 
  703:     /*
  704:      * If the protocol is not in the range we're interested in,
  705:      * just return without looking at the packet.  If it is,
  706:      * the protocol becomes the first byte to "compress".
  707:      */
  708:     rptr = mtod(dmsg, u_char *);
  709:     ent = PPP_PROTOCOL(rptr);
  710:     if (ent < 0x21 || ent > 0xf9)
  711: 	return;
  712: 
  713:     db->seqno++;
  714:     ilen = 1;		/* count the protocol as 1 byte */
  715:     rptr += PPP_HDRLEN;
  716:     slen = dmsg->m_len - PPP_HDRLEN;
  717:     for (;;) {
  718: 	if (slen <= 0) {
  719: 	    dmsg = dmsg->m_next;
  720: 	    if (!dmsg)
  721: 		break;
  722: 	    rptr = mtod(dmsg, u_char *);
  723: 	    slen = dmsg->m_len;
  724: 	    continue;
  725: 	}
  726: 	ilen += slen;
  727: 
  728: 	do {
  729: 	    c = *rptr++;
  730: 	    fcode = BSD_KEY(ent, c);
  731: 	    hval = BSD_HASH(ent, c, hshift);
  732: 	    dictp = &db->dict[hval];
  733: 
  734: 	    /* validate and then check the entry */
  735: 	    if (dictp->codem1 >= max_ent)
  736: 		goto nomatch;
  737: 	    if (dictp->f.fcode == fcode) {
  738: 		ent = dictp->codem1+1;
  739: 		continue;   /* found (prefix,suffix) */
  740: 	    }
  741: 
  742: 	    /* continue probing until a match or invalid entry */
  743: 	    disp = (hval == 0) ? 1 : hval;
  744: 	    do {
  745: 		hval += disp;
  746: 		if (hval >= db->hsize)
  747: 		    hval -= db->hsize;
  748: 		dictp = &db->dict[hval];
  749: 		if (dictp->codem1 >= max_ent)
  750: 		    goto nomatch;
  751: 	    } while (dictp->f.fcode != fcode);
  752: 	    ent = dictp->codem1+1;
  753: 	    continue;	/* finally found (prefix,suffix) */
  754: 
  755: 	nomatch:		/* output (count) the prefix */
  756: 	    bitno += n_bits;
  757: 
  758: 	    /* code -> hashtable */
  759: 	    if (max_ent < db->maxmaxcode) {
  760: 		struct bsd_dict *dictp2;
  761: 		/* expand code size if needed */
  762: 		if (max_ent >= MAXCODE(n_bits))
  763: 		    db->n_bits = ++n_bits;
  764: 
  765: 		/* Invalidate previous hash table entry
  766: 		 * assigned this code, and then take it over.
  767: 		 */
  768: 		dictp2 = &db->dict[max_ent+1];
  769: 		if (db->dict[dictp2->cptr].codem1 == max_ent)
  770: 		    db->dict[dictp2->cptr].codem1 = BADCODEM1;
  771: 		dictp2->cptr = hval;
  772: 		dictp->codem1 = max_ent;
  773: 		dictp->f.fcode = fcode;
  774: 
  775: 		db->max_ent = ++max_ent;
  776: 		db->lens[max_ent] = db->lens[ent]+1;
  777: 	    }
  778: 	    ent = c;
  779: 	} while (--slen != 0);
  780:     }
  781:     bitno += n_bits;		/* output (count) the last code */
  782:     db->bytes_out += bitno/8;
  783:     db->in_count += ilen;
  784:     (void)bsd_check(db);
  785: 
  786:     ++db->incomp_count;
  787:     db->incomp_bytes += ilen;
  788:     ++db->uncomp_count;
  789:     db->uncomp_bytes += ilen;
  790: 
  791:     /* Increase code size if we would have without the packet
  792:      * boundary and as the decompressor will.
  793:      */
  794:     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  795: 	db->n_bits++;
  796: }
  797: 
  798: 
  799: /*
  800:  * Decompress "BSD Compress".
  801:  *
  802:  * Because of patent problems, we return DECOMP_ERROR for errors
  803:  * found by inspecting the input data and for system problems, but
  804:  * DECOMP_FATALERROR for any errors which could possibly be said to
  805:  * be being detected "after" decompression.  For DECOMP_ERROR,
  806:  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
  807:  * infringing a patent of Motorola's if we do, so we take CCP down
  808:  * instead.
  809:  *
  810:  * Given that the frame has the correct sequence number and a good FCS,
  811:  * errors such as invalid codes in the input most likely indicate a
  812:  * bug, so we return DECOMP_FATALERROR for them in order to turn off
  813:  * compression, even though they are detected by inspecting the input.
  814:  */
  815: int
  816: bsd_decompress(state, cmp, dmpp)
  817:     void *state;
  818:     struct mbuf *cmp, **dmpp;
  819: {
  820:     struct bsd_db *db = (struct bsd_db *) state;
  821:     u_int max_ent = db->max_ent;
  822:     u_int32_t accm = 0;
  823:     u_int bitno = 32;		/* 1st valid bit in accm */
  824:     u_int n_bits = db->n_bits;
  825:     u_int tgtbitno = 32-n_bits;	/* bitno when we have a code */
  826:     struct bsd_dict *dictp;
  827:     int explen, i, seq, len;
  828:     u_int incode, oldcode, finchar;
  829:     u_char *p, *rptr, *wptr;
  830:     struct mbuf *m, *dmp, *mret;
  831:     int adrs, ctrl, ilen;
  832:     int space, codelen, extra;
  833: 
  834:     /*
  835:      * Save the address/control from the PPP header
  836:      * and then get the sequence number.
  837:      */
  838:     *dmpp = NULL;
  839:     rptr = mtod(cmp, u_char *);
  840:     adrs = PPP_ADDRESS(rptr);
  841:     ctrl = PPP_CONTROL(rptr);
  842:     rptr += PPP_HDRLEN;
  843:     len = cmp->m_len - PPP_HDRLEN;
  844:     seq = 0;
  845:     for (i = 0; i < 2; ++i) {
  846: 	while (len <= 0) {
  847: 	    cmp = cmp->m_next;
  848: 	    if (cmp == NULL)
  849: 		return DECOMP_ERROR;
  850: 	    rptr = mtod(cmp, u_char *);
  851: 	    len = cmp->m_len;
  852: 	}
  853: 	seq = (seq << 8) + *rptr++;
  854: 	--len;
  855:     }
  856: 
  857:     /*
  858:      * Check the sequence number and give up if it differs from
  859:      * the value we're expecting.
  860:      */
  861:     if (seq != db->seqno) {
  862: 	if (db->debug)
  863: 	    printf("bsd_decomp%d: bad sequence # %d, expected %d\n",
  864: 		   db->unit, seq, db->seqno - 1);
  865: 	return DECOMP_ERROR;
  866:     }
  867:     ++db->seqno;
  868: 
  869:     /*
  870:      * Allocate one mbuf to start with.
  871:      */
  872:     MGETHDR(dmp, M_DONTWAIT, MT_DATA);
  873:     if (dmp == NULL)
  874: 	return DECOMP_ERROR;
  875:     mret = dmp;
  876:     dmp->m_len = 0;
  877:     dmp->m_next = NULL;
  878:     MCLGET(dmp, M_DONTWAIT);
  879:     dmp->m_data += db->hdrlen;
  880:     wptr = mtod(dmp, u_char *);
  881:     space = M_TRAILINGSPACE(dmp) - PPP_HDRLEN + 1;
  882: 
  883:     /*
  884:      * Fill in the ppp header, but not the last byte of the protocol
  885:      * (that comes from the decompressed data).
  886:      */
  887:     wptr[0] = adrs;
  888:     wptr[1] = ctrl;
  889:     wptr[2] = 0;
  890:     wptr += PPP_HDRLEN - 1;
  891: 
  892:     ilen = len;
  893:     oldcode = CLEAR;
  894:     explen = 0;
  895:     for (;;) {
  896: 	if (len == 0) {
  897: 	    cmp = cmp->m_next;
  898: 	    if (!cmp)		/* quit at end of message */
  899: 		break;
  900: 	    rptr = mtod(cmp, u_char *);
  901: 	    len = cmp->m_len;
  902: 	    ilen += len;
  903: 	    continue;		/* handle 0-length buffers */
  904: 	}
  905: 
  906: 	/*
  907: 	 * Accumulate bytes until we have a complete code.
  908: 	 * Then get the next code, relying on the 32-bit,
  909: 	 * unsigned accm to mask the result.
  910: 	 */
  911: 	bitno -= 8;
  912: 	accm |= *rptr++ << bitno;
  913: 	--len;
  914: 	if (tgtbitno < bitno)
  915: 	    continue;
  916: 	incode = accm >> tgtbitno;
  917: 	accm <<= n_bits;
  918: 	bitno += n_bits;
  919: 
  920: 	if (incode == CLEAR) {
  921: 	    /*
  922: 	     * The dictionary must only be cleared at
  923: 	     * the end of a packet.  But there could be an
  924: 	     * empty mbuf at the end.
  925: 	     */
  926: 	    if (len > 0 || cmp->m_next != NULL) {
  927: 		while ((cmp = cmp->m_next) != NULL)
  928: 		    len += cmp->m_len;
  929: 		if (len > 0) {
  930: 		    m_freem(mret);
  931: 		    if (db->debug)
  932: 			printf("bsd_decomp%d: bad CLEAR\n", db->unit);
  933: 		    return DECOMP_FATALERROR;	/* probably a bug */
  934: 		}
  935: 	    }
  936: 	    bsd_clear(db);
  937: 	    explen = ilen = 0;
  938: 	    break;
  939: 	}
  940: 
  941: 	if (incode > max_ent + 2 || incode > db->maxmaxcode
  942: 	    || (incode > max_ent && oldcode == CLEAR)) {
  943: 	    m_freem(mret);
  944: 	    if (db->debug) {
  945: 		printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
  946: 		       db->unit, incode, oldcode);
  947: 		printf("max_ent=0x%x explen=%d seqno=%d\n",
  948: 		       max_ent, explen, db->seqno);
  949: 	    }
  950: 	    return DECOMP_FATALERROR;	/* probably a bug */
  951: 	}
  952: 
  953: 	/* Special case for KwKwK string. */
  954: 	if (incode > max_ent) {
  955: 	    finchar = oldcode;
  956: 	    extra = 1;
  957: 	} else {
  958: 	    finchar = incode;
  959: 	    extra = 0;
  960: 	}
  961: 
  962: 	codelen = db->lens[finchar];
  963: 	explen += codelen + extra;
  964: 	if (explen > db->mru + 1) {
  965: 	    m_freem(mret);
  966: 	    if (db->debug) {
  967: 		printf("bsd_decomp%d: ran out of mru\n", db->unit);
  968: #ifdef DEBUG
  969: 		while ((cmp = cmp->m_next) != NULL)
  970: 		    len += cmp->m_len;
  971: 		printf("  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
  972: 		       len, finchar, codelen, explen);
  973: #endif
  974: 	    }
  975: 	    return DECOMP_FATALERROR;
  976: 	}
  977: 
  978: 	/*
  979: 	 * For simplicity, the decoded characters go in a single mbuf,
  980: 	 * so we allocate a single extra cluster mbuf if necessary.
  981: 	 */
  982: 	if ((space -= codelen + extra) < 0) {
  983: 	    dmp->m_len = wptr - mtod(dmp, u_char *);
  984: 	    MGET(m, M_DONTWAIT, MT_DATA);
  985: 	    if (m == NULL) {
  986: 		m_freem(mret);
  987: 		return DECOMP_ERROR;
  988: 	    }
  989: 	    m->m_len = 0;
  990: 	    m->m_next = NULL;
  991: 	    dmp->m_next = m;
  992: 	    MCLGET(m, M_DONTWAIT);
  993: 	    space = M_TRAILINGSPACE(m) - (codelen + extra);
  994: 	    if (space < 0) {
  995: 		/* now that's what I call *compression*. */
  996: 		m_freem(mret);
  997: 		return DECOMP_ERROR;
  998: 	    }
  999: 	    dmp = m;
 1000: 	    wptr = mtod(dmp, u_char *);
 1001: 	}
 1002: 
 1003: 	/*
 1004: 	 * Decode this code and install it in the decompressed buffer.
 1005: 	 */
 1006: 	p = (wptr += codelen);
 1007: 	while (finchar > LAST) {
 1008: 	    dictp = &db->dict[db->dict[finchar].cptr];
 1009: #ifdef DEBUG
 1010: 	    if (--codelen <= 0 || dictp->codem1 != finchar-1)
 1011: 		goto bad;
 1012: #endif
 1013: 	    *--p = dictp->f.hs.suffix;
 1014: 	    finchar = dictp->f.hs.prefix;
 1015: 	}
 1016: 	*--p = finchar;
 1017: 
 1018: #ifdef DEBUG
 1019: 	if (--codelen != 0)
 1020: 	    printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
 1021: 		   db->unit, codelen, incode, max_ent);
 1022: #endif
 1023: 
 1024: 	if (extra)		/* the KwKwK case again */
 1025: 	    *wptr++ = finchar;
 1026: 
 1027: 	/*
 1028: 	 * If not first code in a packet, and
 1029: 	 * if not out of code space, then allocate a new code.
 1030: 	 *
 1031: 	 * Keep the hash table correct so it can be used
 1032: 	 * with uncompressed packets.
 1033: 	 */
 1034: 	if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
 1035: 	    struct bsd_dict *dictp2;
 1036: 	    u_int32_t fcode;
 1037: 	    u_int32_t hval, disp;
 1038: 
 1039: 	    fcode = BSD_KEY(oldcode,finchar);
 1040: 	    hval = BSD_HASH(oldcode,finchar,db->hshift);
 1041: 	    dictp = &db->dict[hval];
 1042: 
 1043: 	    /* look for a free hash table entry */
 1044: 	    if (dictp->codem1 < max_ent) {
 1045: 		disp = (hval == 0) ? 1 : hval;
 1046: 		do {
 1047: 		    hval += disp;
 1048: 		    if (hval >= db->hsize)
 1049: 			hval -= db->hsize;
 1050: 		    dictp = &db->dict[hval];
 1051: 		} while (dictp->codem1 < max_ent);
 1052: 	    }
 1053: 
 1054: 	    /*
 1055: 	     * Invalidate previous hash table entry
 1056: 	     * assigned this code, and then take it over
 1057: 	     */
 1058: 	    dictp2 = &db->dict[max_ent+1];
 1059: 	    if (db->dict[dictp2->cptr].codem1 == max_ent) {
 1060: 		db->dict[dictp2->cptr].codem1 = BADCODEM1;
 1061: 	    }
 1062: 	    dictp2->cptr = hval;
 1063: 	    dictp->codem1 = max_ent;
 1064: 	    dictp->f.fcode = fcode;
 1065: 
 1066: 	    db->max_ent = ++max_ent;
 1067: 	    db->lens[max_ent] = db->lens[oldcode]+1;
 1068: 
 1069: 	    /* Expand code size if needed. */
 1070: 	    if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
 1071: 		db->n_bits = ++n_bits;
 1072: 		tgtbitno = 32-n_bits;
 1073: 	    }
 1074: 	}
 1075: 	oldcode = incode;
 1076:     }
 1077:     dmp->m_len = wptr - mtod(dmp, u_char *);
 1078: 
 1079:     /*
 1080:      * Keep the checkpoint right so that incompressible packets
 1081:      * clear the dictionary at the right times.
 1082:      */
 1083:     db->bytes_out += ilen;
 1084:     db->in_count += explen;
 1085:     if (bsd_check(db) && db->debug) {
 1086: 	printf("bsd_decomp%d: peer should have cleared dictionary\n",
 1087: 	       db->unit);
 1088:     }
 1089: 
 1090:     ++db->comp_count;
 1091:     db->comp_bytes += ilen + BSD_OVHD;
 1092:     ++db->uncomp_count;
 1093:     db->uncomp_bytes += explen;
 1094: 
 1095:     *dmpp = mret;
 1096:     return DECOMP_OK;
 1097: 
 1098: #ifdef DEBUG
 1099:  bad:
 1100:     if (codelen <= 0) {
 1101: 	printf("bsd_decomp%d: fell off end of chain ", db->unit);
 1102: 	printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
 1103: 	       incode, finchar, db->dict[finchar].cptr, max_ent);
 1104:     } else if (dictp->codem1 != finchar-1) {
 1105: 	printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",
 1106: 	       db->unit, incode, finchar);
 1107: 	printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode,
 1108: 	       db->dict[finchar].cptr, dictp->codem1);
 1109:     }
 1110:     m_freem(mret);
 1111:     return DECOMP_FATALERROR;
 1112: #endif /* DEBUG */
 1113: }
 1114: #endif /* DO_BSD_COMPRESS */