root/net/bsd-comp.c

DEFINITIONS

1. bsd_clear
2. bsd_check
3. bsd_comp_stats
4. bsd_reset
5. bsd_alloc
6. bsd_free
7. bsd_comp_alloc
8. bsd_decomp_alloc
9. bsd_init
10. bsd_comp_init
11. bsd_decomp_init
12. bsd_compress
13. bsd_incomp
14. bsd_decompress

    1 /*      $OpenBSD: bsd-comp.c,v 1.6 2003/06/02 23:28:11 millert Exp $    */
    2 /*      $NetBSD: bsd-comp.c,v 1.6 1996/10/13 02:10:58 christos Exp $    */
    4 /* Because this code is derived from the 4.3BSD compress source:
    5  *
    6  *
    7  * Copyright (c) 1985, 1986 The Regents of the University of California.
    8  * All rights reserved.
    9  *
   10  * This code is derived from software contributed to Berkeley by
   11  * James A. Woods, derived from original work by Spencer Thomas
   12  * and Joseph Orost.
   13  *
   14  * Redistribution and use in source and binary forms, with or without
   15  * modification, are permitted provided that the following conditions
   16  * are met:
   17  * 1. Redistributions of source code must retain the above copyright
   18  *    notice, this list of conditions and the following disclaimer.
   19  * 2. Redistributions in binary form must reproduce the above copyright
   20  *    notice, this list of conditions and the following disclaimer in the
   21  *    documentation and/or other materials provided with the distribution.
   22  * 3. Neither the name of the University nor the names of its contributors
   23  *    may be used to endorse or promote products derived from this software
   24  *    without specific prior written permission.
   25  *
   26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   36  * SUCH DAMAGE.
   37  */
   39 /*
   40  * This version is for use with mbufs on BSD-derived systems.
   41  */
   43 #include <sys/param.h>
   44 #include <sys/types.h>
   45 #include <sys/systm.h>
   46 #include <sys/mbuf.h>
   47 #include <sys/socket.h>
   48 #include <net/if.h>
   49 #include <net/if_types.h>
   50 #include <net/ppp_defs.h>
   51 #include <net/if_ppp.h>
   53 #define PACKETPTR       struct mbuf *
   54 #include <net/ppp-comp.h>
   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  */
   79 /*
   80  * A dictionary for doing BSD compress.
   81  */
   82 struct bsd_db {
   83     int     totlen;                     /* length of this structure */
u_int   hsize;                      /* size of the hash table */
u_char  hshift;                     /* used in hash function */
u_char  n_bits;                     /* current bits/code */
u_char  maxbits;
u_char  debug;
u_char  unit;
u_int16_t seqno;                    /* sequence # of next packet */
u_int   hdrlen;                     /* header length to preallocate */
u_int   mru;
u_int   maxmaxcode;                 /* largest valid code */
u_int   max_ent;                    /* largest code in use */
u_int   in_count;                   /* uncompressed bytes, aged */
u_int   bytes_out;                  /* compressed bytes, aged */
u_int   ratio;                      /* recent compression ratio */
u_int   checkpoint;                 /* when to next check the ratio */
u_int   clear_count;                /* times dictionary cleared */
u_int   incomp_count;               /* incompressible packets */
u_int   incomp_bytes;               /* incompressible bytes */
u_int   uncomp_count;               /* uncompressed packets */
u_int   uncomp_bytes;               /* uncompressed bytes */
u_int   comp_count;                 /* compressed packets */
u_int   comp_bytes;                 /* compressed bytes */
u_int16_t *lens;                    /* array of lengths of codes */
  107     struct bsd_dict {
  108         union {                         /* hash value */
u_int32_t   fcode;
  110             struct {
  111 #if BYTE_ORDER == LITTLE_ENDIAN
u_int16_t prefix;       /* preceding code */
u_char  suffix;         /* last character of new code */
u_char  pad;
  115 #else
u_char  pad;
u_char  suffix;         /* last character of new code */
u_int16_t prefix;       /* preceding code */
  119 #endif
  120             } hs;
  121         } f;
u_int16_t codem1;               /* output of hash table -1 */
u_int16_t cptr;                 /* map code to hash table entry */
  124     } dict[1];
  125 };
  127 #define BSD_OVHD        2               /* BSD compress overhead/packet */
  128 #define BSD_INIT_BITS   BSD_MIN_BITS
  130 static void     *bsd_comp_alloc(u_char *options, int opt_len);
  131 static void     *bsd_decomp_alloc(u_char *options, int opt_len);
  132 static void     bsd_free(void *state);
  133 static int      bsd_comp_init(void *state, u_char *options, int opt_len,
  134                                    int unit, int hdrlen, int debug);
  135 static int      bsd_decomp_init(void *state, u_char *options, int opt_len,
  136                                      int unit, int hdrlen, int mru, int debug);
  137 static int      bsd_compress(void *state, struct mbuf **mret,
  138                                   struct mbuf *mp, int slen, int maxolen);
  139 static void     bsd_incomp(void *state, struct mbuf *dmsg);
  140 static int      bsd_decompress(void *state, struct mbuf *cmp,
  141                                     struct mbuf **dmpp);
  142 static void     bsd_reset(void *state);
  143 static void     bsd_comp_stats(void *state, struct compstat *stats);
  145 /*
  146  * Procedures exported to if_ppp.c.
  147  */
  148 struct compressor ppp_bsd_compress = {
CI_BSD_COMPRESS,            /* compress_proto */
bsd_comp_alloc,             /* comp_alloc */
bsd_free,                   /* comp_free */
bsd_comp_init,              /* comp_init */
bsd_reset,                  /* comp_reset */
bsd_compress,               /* compress */
bsd_comp_stats,             /* comp_stat */
bsd_decomp_alloc,           /* decomp_alloc */
bsd_free,                   /* decomp_free */
bsd_decomp_init,            /* decomp_init */
bsd_reset,                  /* decomp_reset */
bsd_decompress,             /* decompress */
bsd_incomp,                 /* incomp */
bsd_comp_stats,             /* decomp_stat */
  163 };
  165 /*
  166  * the next two codes should not be changed lightly, as they must not
  167  * lie within the contiguous general code space.
  168  */
  169 #define CLEAR   256                     /* table clear output code */
  170 #define FIRST   257                     /* first free entry */
  171 #define LAST    255
  173 #define MAXCODE(b)      ((1 << (b)) - 1)
  174 #define BADCODEM1       MAXCODE(BSD_MAX_BITS)
  176 #define BSD_HASH(prefix,suffix,hshift)  ((((u_int32_t)(suffix)) << (hshift)) \
  177                                          ^ (u_int32_t)(prefix))
  178 #define BSD_KEY(prefix,suffix)          ((((u_int32_t)(suffix)) << 16) \
  179                                          + (u_int32_t)(prefix))
  181 #define CHECK_GAP       10000           /* Ratio check interval */
  183 #define RATIO_SCALE_LOG 8
  184 #define RATIO_SCALE     (1<<RATIO_SCALE_LOG)
  185 #define RATIO_MAX       (0x7fffffff>>RATIO_SCALE_LOG)
  187 static void bsd_clear(struct bsd_db *);
  188 static int bsd_check(struct bsd_db *);
  189 static void *bsd_alloc(u_char *, int, int);
  190 static int bsd_init(struct bsd_db *, u_char *, int, int, int, int,
  191                          int, int);
  193 /*
  194  * clear the dictionary
  195  */
  196 static void
bsd_clear(db)
  198     struct bsd_db *db;
  199 {
db->clear_count++;
db->max_ent = FIRST-1;
db->n_bits = BSD_INIT_BITS;
db->ratio = 0;
db->bytes_out = 0;
db->in_count = 0;
db->incomp_count = 0;
db->checkpoint = CHECK_GAP;
  208 }
  210 /*
  211  * If the dictionary is full, then see if it is time to reset it.
  212  *
  213  * Compute the compression ratio using fixed-point arithmetic
  214  * with 8 fractional bits.
  215  *
  216  * Since we have an infinite stream instead of a single file,
  217  * watch only the local compression ratio.
  218  *
  219  * Since both peers must reset the dictionary at the same time even in
  220  * the absence of CLEAR codes (while packets are incompressible), they
  221  * must compute the same ratio.
  222  */
  223 static int                              /* 1=output CLEAR */
bsd_check(db)
  225     struct bsd_db *db;
  226 {
u_int new_ratio;
  229     if (db->in_count >= db->checkpoint) {
  230         /* age the ratio by limiting the size of the counts */
  231         if (db->in_count >= RATIO_MAX
  232             || db->bytes_out >= RATIO_MAX) {
db->in_count -= db->in_count/4;
db->bytes_out -= db->bytes_out/4;
  235         }
db->checkpoint = db->in_count + CHECK_GAP;
  239         if (db->max_ent >= db->maxmaxcode) {
  240             /* Reset the dictionary only if the ratio is worse,
  241              * or if it looks as if it has been poisoned
  242              * by incompressible data.
  243              *
  244              * This does not overflow, because
  245              *  db->in_count <= RATIO_MAX.
  246              */
new_ratio = db->in_count << RATIO_SCALE_LOG;
  248             if (db->bytes_out != 0)
new_ratio /= db->bytes_out;
  251             if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE) {
bsd_clear(db);
  253                 return 1;
  254             }
db->ratio = new_ratio;
  256         }
  257     }
  258     return 0;
  259 }
  261 /*
  262  * Return statistics.
  263  */
  264 static void
bsd_comp_stats(state, stats)
  266     void *state;
  267     struct compstat *stats;
  268 {
  269     struct bsd_db *db = (struct bsd_db *) state;
u_int out;
stats->unc_bytes = db->uncomp_bytes;
stats->unc_packets = db->uncomp_count;
stats->comp_bytes = db->comp_bytes;
stats->comp_packets = db->comp_count;
stats->inc_bytes = db->incomp_bytes;
stats->inc_packets = db->incomp_count;
stats->ratio = db->in_count;
out = db->bytes_out;
  280     if (stats->ratio <= 0x7fffff)
stats->ratio <<= 8;
  282     else
out >>= 8;
  284     if (out != 0)
stats->ratio /= out;
  286 }
  288 /*
  289  * Reset state, as on a CCP ResetReq.
  290  */
  291 static void
bsd_reset(state)
  293     void *state;
  294 {
  295     struct bsd_db *db = (struct bsd_db *) state;
db->seqno = 0;
bsd_clear(db);
db->clear_count = 0;
  300 }
  302 /*
  303  * Allocate space for a (de) compressor.
  304  */
  305 static void *
bsd_alloc(options, opt_len, decomp)
u_char *options;
  308     int opt_len, decomp;
  309 {
  310     int bits;
u_int newlen, hsize, hshift, maxmaxcode;
  312     struct bsd_db *db;
  314     if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
  315         || options[1] != CILEN_BSD_COMPRESS
  316         || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
  317         return NULL;
bits = BSD_NBITS(options[2]);
  319     switch (bits) {
  320     case 9:                     /* needs 82152 for both directions */
  321     case 10:                    /* needs 84144 */
  322     case 11:                    /* needs 88240 */
  323     case 12:                    /* needs 96432 */
hsize = 5003;
hshift = 4;
  326         break;
  327     case 13:                    /* needs 176784 */
hsize = 9001;
hshift = 5;
  330         break;
  331     case 14:                    /* needs 353744 */
hsize = 18013;
hshift = 6;
  334         break;
  335     case 15:                    /* needs 691440 */
hsize = 35023;
hshift = 7;
  338         break;
  339     case 16:                    /* needs 1366160--far too much, */
  340         /* hsize = 69001; */    /* and 69001 is too big for cptr */
  341         /* hshift = 8; */       /* in struct bsd_db */
  342         /* break; */
  343     default:
  344         return NULL;
  345     }
maxmaxcode = MAXCODE(bits);
newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0]));
MALLOC(db, struct bsd_db *, newlen, M_DEVBUF, M_NOWAIT);
  350     if (!db)
  351         return NULL;
bzero(db, sizeof(*db) - sizeof(db->dict));
  354     if (!decomp) {
db->lens = NULL;
  356     } else {
MALLOC(db->lens, u_int16_t *, (maxmaxcode+1) * sizeof(db->lens[0]),
M_DEVBUF, M_NOWAIT);
  359         if (!db->lens) {
FREE(db, M_DEVBUF);
  361             return NULL;
  362         }
  363     }
db->totlen = newlen;
db->hsize = hsize;
db->hshift = hshift;
db->maxmaxcode = maxmaxcode;
db->maxbits = bits;
  371     return (void *) db;
  372 }
  374 static void
bsd_free(state)
  376     void *state;
  377 {
  378     struct bsd_db *db = (struct bsd_db *) state;
  380     if (db->lens)
FREE(db->lens, M_DEVBUF);
FREE(db, M_DEVBUF);
  383 }
  385 static void *
bsd_comp_alloc(options, opt_len)
u_char *options;
  388     int opt_len;
  389 {
  390     return bsd_alloc(options, opt_len, 0);
  391 }
  393 static void *
bsd_decomp_alloc(options, opt_len)
u_char *options;
  396     int opt_len;
  397 {
  398     return bsd_alloc(options, opt_len, 1);
  399 }
  401 /*
  402  * Initialize the database.
  403  */
  404 static int
bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp)
  406     struct bsd_db *db;
u_char *options;
  408     int opt_len, unit, hdrlen, mru, debug, decomp;
  409 {
  410     int i;
  412     if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
  413         || options[1] != CILEN_BSD_COMPRESS
  414         || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION
  415         || BSD_NBITS(options[2]) != db->maxbits
  416         || (decomp && db->lens == NULL))
  417         return 0;
  419     if (decomp) {
i = LAST+1;
  421         while (i != 0)
db->lens[--i] = 1;
  423     }
i = db->hsize;
  425     while (i != 0) {
db->dict[--i].codem1 = BADCODEM1;
db->dict[i].cptr = 0;
  428     }
db->unit = unit;
db->hdrlen = hdrlen;
db->mru = mru;
  433 #ifndef DEBUG
  434     if (debug)
  435 #endif
db->debug = 1;
bsd_reset(db);
  440     return 1;
  441 }
  443 static int
bsd_comp_init(state, options, opt_len, unit, hdrlen, debug)
  445     void *state;
u_char *options;
  447     int opt_len, unit, hdrlen, debug;
  448 {
  449     return bsd_init((struct bsd_db *) state, options, opt_len,
unit, hdrlen, 0, debug, 0);
  451 }
  453 static int
bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug)
  455     void *state;
u_char *options;
  457     int opt_len, unit, hdrlen, mru, debug;
  458 {
  459     return bsd_init((struct bsd_db *) state, options, opt_len,
unit, hdrlen, mru, debug, 1);
  461 }
  464 /*
  465  * compress a packet
  466  *      One change from the BSD compress command is that when the
  467  *      code size expands, we do not output a bunch of padding.
  468  */
  469 int                                     /* new slen */
bsd_compress(state, mret, mp, slen, maxolen)
  471     void *state;
  472     struct mbuf **mret;         /* return compressed mbuf chain here */
  473     struct mbuf *mp;            /* from here */
  474     int slen;                   /* uncompressed length */
  475     int maxolen;                /* max compressed length */
  476 {
  477     struct bsd_db *db = (struct bsd_db *) state;
  478     int hshift = db->hshift;
u_int max_ent = db->max_ent;
u_int n_bits = db->n_bits;
u_int bitno = 32;
u_int32_t accm = 0, fcode;
  483     struct bsd_dict *dictp;
u_char c;
  485     int hval, disp, ent, ilen;
u_char *rptr, *wptr;
u_char *cp_end;
  488     int olen;
  489     struct mbuf *m;
  491 #define PUTBYTE(v) {                                    \
  492     ++olen;                                             \
  493     if (wptr) {                                         \
  494         *wptr++ = (v);                                  \
  495         if (wptr >= cp_end) {                           \
m->m_len = wptr - mtod(m, u_char *);        \
MGET(m->m_next, M_DONTWAIT, MT_DATA);       \
m = m->m_next;                              \
  499             if (m) {                                    \
m->m_len = 0;                           \
  501                 if (maxolen - olen > MLEN)              \
MCLGET(m, M_DONTWAIT);              \
wptr = mtod(m, u_char *);               \
cp_end = wptr + M_TRAILINGSPACE(m);     \
  505             } else                                      \
wptr = NULL;                            \
  507         }                                               \
  508     }                                                   \
  509 }
  511 #define OUTPUT(ent) {                                   \
bitno -= n_bits;                                    \
accm |= ((ent) << bitno);                           \
  514     do {                                                \
PUTBYTE(accm >> 24);                            \
accm <<= 8;                                     \
bitno += 8;                                     \
  518     } while (bitno <= 24);                              \
  519 }
  521     /*
  522      * If the protocol is not in the range we're interested in,
  523      * just return without compressing the packet.  If it is,
  524      * the protocol becomes the first byte to compress.
  525      */
rptr = mtod(mp, u_char *);
ent = PPP_PROTOCOL(rptr);
  528     if (ent < 0x21 || ent > 0xf9) {
  529         *mret = NULL;
  530         return slen;
  531     }
  533     /* Don't generate compressed packets which are larger than
  534        the uncompressed packet. */
  535     if (maxolen > slen)
maxolen = slen;
  538     /* Allocate one mbuf to start with. */
MGET(m, M_DONTWAIT, MT_DATA);
  540     *mret = m;
  541     if (m != NULL) {
m->m_len = 0;
  543         if (maxolen + db->hdrlen > MLEN)
MCLGET(m, M_DONTWAIT);
m->m_data += db->hdrlen;
wptr = mtod(m, u_char *);
cp_end = wptr + M_TRAILINGSPACE(m);
  548     } else
wptr = cp_end = NULL;
  551     /*
  552      * Copy the PPP header over, changing the protocol,
  553      * and install the 2-byte packet sequence number.
  554      */
  555     if (wptr) {
  556         *wptr++ = PPP_ADDRESS(rptr);    /* assumes the ppp header is */
  557         *wptr++ = PPP_CONTROL(rptr);    /* all in one mbuf */
  558         *wptr++ = 0;                    /* change the protocol */
  559         *wptr++ = PPP_COMP;
  560         *wptr++ = db->seqno >> 8;
  561         *wptr++ = db->seqno;
  562     }
  563     ++db->seqno;
olen = 0;
rptr += PPP_HDRLEN;
slen = mp->m_len - PPP_HDRLEN;
ilen = slen + 1;
  569     for (;;) {
  570         if (slen <= 0) {
mp = mp->m_next;
  572             if (!mp)
  573                 break;
rptr = mtod(mp, u_char *);
slen = mp->m_len;
  576             if (!slen)
  577                 continue;   /* handle 0-length buffers */
ilen += slen;
  579         }
slen--;
c = *rptr++;
fcode = BSD_KEY(ent, c);
hval = BSD_HASH(ent, c, hshift);
dictp = &db->dict[hval];
  587         /* Validate and then check the entry. */
  588         if (dictp->codem1 >= max_ent)
  589             goto nomatch;
  590         if (dictp->f.fcode == fcode) {
ent = dictp->codem1+1;
  592             continue;   /* found (prefix,suffix) */
  593         }
  595         /* continue probing until a match or invalid entry */
disp = (hval == 0) ? 1 : hval;
  597         do {
hval += disp;
  599             if (hval >= db->hsize)
hval -= db->hsize;
dictp = &db->dict[hval];
  602             if (dictp->codem1 >= max_ent)
  603                 goto nomatch;
  604         } while (dictp->f.fcode != fcode);
ent = dictp->codem1 + 1;        /* finally found (prefix,suffix) */
  606         continue;
nomatch:
OUTPUT(ent);            /* output the prefix */
  611         /* code -> hashtable */
  612         if (max_ent < db->maxmaxcode) {
  613             struct bsd_dict *dictp2;
  614             /* expand code size if needed */
  615             if (max_ent >= MAXCODE(n_bits))
db->n_bits = ++n_bits;
  618             /* Invalidate old hash table entry using
  619              * this code, and then take it over.
  620              */
dictp2 = &db->dict[max_ent+1];
  622             if (db->dict[dictp2->cptr].codem1 == max_ent)
db->dict[dictp2->cptr].codem1 = BADCODEM1;
dictp2->cptr = hval;
dictp->codem1 = max_ent;
dictp->f.fcode = fcode;
db->max_ent = ++max_ent;
  629         }
ent = c;
  631     }
OUTPUT(ent);                /* output the last code */
db->bytes_out += olen;
db->in_count += ilen;
  636     if (bitno < 32)
  637         ++db->bytes_out;        /* count complete bytes */
  639     if (bsd_check(db))
OUTPUT(CLEAR);          /* do not count the CLEAR */
  642     /*
  643      * Pad dribble bits of last code with ones.
  644      * Do not emit a completely useless byte of ones.
  645      */
  646     if (bitno != 32)
PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
  649     if (m != NULL) {
m->m_len = wptr - mtod(m, u_char *);
m->m_next = NULL;
  652     }
  654     /*
  655      * Increase code size if we would have without the packet
  656      * boundary and as the decompressor will.
  657      */
  658     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
db->n_bits++;
db->uncomp_bytes += ilen;
  662     ++db->uncomp_count;
  663     if (olen + PPP_HDRLEN + BSD_OVHD > maxolen) {
  664         /* throw away the compressed stuff if it is longer than uncompressed */
  665         if (*mret != NULL) {
m_freem(*mret);
  667             *mret = NULL;
  668         }
  669         ++db->incomp_count;
db->incomp_bytes += ilen;
  671     } else {
  672         ++db->comp_count;
db->comp_bytes += olen + BSD_OVHD;
  674     }
  676     return olen + PPP_HDRLEN + BSD_OVHD;
  677 #undef OUTPUT
  678 #undef PUTBYTE
  679 }
  682 /*
  683  * Update the "BSD Compress" dictionary on the receiver for
  684  * incompressible data by pretending to compress the incoming data.
  685  */
  686 static void
bsd_incomp(state, dmsg)
  688     void *state;
  689     struct mbuf *dmsg;
  690 {
  691     struct bsd_db *db = (struct bsd_db *) state;
u_int hshift = db->hshift;
u_int max_ent = db->max_ent;
u_int n_bits = db->n_bits;
  695     struct bsd_dict *dictp;
u_int32_t fcode;
u_char c;
u_int32_t hval, disp;
  699     int slen, ilen;
u_int bitno = 7;
u_char *rptr;
u_int ent;
  704     /*
  705      * If the protocol is not in the range we're interested in,
  706      * just return without looking at the packet.  If it is,
  707      * the protocol becomes the first byte to "compress".
  708      */
rptr = mtod(dmsg, u_char *);
ent = PPP_PROTOCOL(rptr);
  711     if (ent < 0x21 || ent > 0xf9)
  712         return;
db->incomp_count++;
db->seqno++;
ilen = 1;           /* count the protocol as 1 byte */
rptr += PPP_HDRLEN;
slen = dmsg->m_len - PPP_HDRLEN;
  719     for (;;) {
  720         if (slen <= 0) {
dmsg = dmsg->m_next;
  722             if (!dmsg)
  723                 break;
rptr = mtod(dmsg, u_char *);
slen = dmsg->m_len;
  726             continue;
  727         }
ilen += slen;
  730         do {
c = *rptr++;
fcode = BSD_KEY(ent, c);
hval = BSD_HASH(ent, c, hshift);
dictp = &db->dict[hval];
  736             /* validate and then check the entry */
  737             if (dictp->codem1 >= max_ent)
  738                 goto nomatch;
  739             if (dictp->f.fcode == fcode) {
ent = dictp->codem1+1;
  741                 continue;   /* found (prefix,suffix) */
  742             }
  744             /* continue probing until a match or invalid entry */
disp = (hval == 0) ? 1 : hval;
  746             do {
hval += disp;
  748                 if (hval >= db->hsize)
hval -= db->hsize;
dictp = &db->dict[hval];
  751                 if (dictp->codem1 >= max_ent)
  752                     goto nomatch;
  753             } while (dictp->f.fcode != fcode);
ent = dictp->codem1+1;
  755             continue;   /* finally found (prefix,suffix) */
nomatch:                /* output (count) the prefix */
bitno += n_bits;
  760             /* code -> hashtable */
  761             if (max_ent < db->maxmaxcode) {
  762                 struct bsd_dict *dictp2;
  763                 /* expand code size if needed */
  764                 if (max_ent >= MAXCODE(n_bits))
db->n_bits = ++n_bits;
  767                 /* Invalidate previous hash table entry
  768                  * assigned this code, and then take it over.
  769                  */
dictp2 = &db->dict[max_ent+1];
  771                 if (db->dict[dictp2->cptr].codem1 == max_ent)
db->dict[dictp2->cptr].codem1 = BADCODEM1;
dictp2->cptr = hval;
dictp->codem1 = max_ent;
dictp->f.fcode = fcode;
db->max_ent = ++max_ent;
db->lens[max_ent] = db->lens[ent]+1;
  779             }
ent = c;
  781         } while (--slen != 0);
  782     }
bitno += n_bits;            /* output (count) the last code */
db->bytes_out += bitno/8;
db->in_count += ilen;
  786     (void)bsd_check(db);
  788     ++db->incomp_count;
db->incomp_bytes += ilen;
  790     ++db->uncomp_count;
db->uncomp_bytes += ilen;
  793     /* Increase code size if we would have without the packet
  794      * boundary and as the decompressor will.
  795      */
  796     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
db->n_bits++;
  798 }
  801 /*
  802  * Decompress "BSD Compress".
  803  *
  804  * Because of patent problems, we return DECOMP_ERROR for errors
  805  * found by inspecting the input data and for system problems, but
  806  * DECOMP_FATALERROR for any errors which could possibly be said to
  807  * be being detected "after" decompression.  For DECOMP_ERROR,
  808  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
  809  * infringing a patent of Motorola's if we do, so we take CCP down
  810  * instead.
  811  *
  812  * Given that the frame has the correct sequence number and a good FCS,
  813  * errors such as invalid codes in the input most likely indicate a
  814  * bug, so we return DECOMP_FATALERROR for them in order to turn off
  815  * compression, even though they are detected by inspecting the input.
  816  */
  817 int
bsd_decompress(state, cmp, dmpp)
  819     void *state;
  820     struct mbuf *cmp, **dmpp;
  821 {
  822     struct bsd_db *db = (struct bsd_db *) state;
u_int max_ent = db->max_ent;
u_int32_t accm = 0;
u_int bitno = 32;           /* 1st valid bit in accm */
u_int n_bits = db->n_bits;
u_int tgtbitno = 32-n_bits; /* bitno when we have a code */
  828     struct bsd_dict *dictp;
  829     int explen, i, seq, len;
u_int incode, oldcode, finchar;
u_char *p, *rptr, *wptr;
  832     struct mbuf *m, *dmp, *mret;
  833     int adrs, ctrl, ilen;
  834     int space, codelen, extra;
  836     /*
  837      * Save the address/control from the PPP header
  838      * and then get the sequence number.
  839      */
  840     *dmpp = NULL;
rptr = mtod(cmp, u_char *);
adrs = PPP_ADDRESS(rptr);
ctrl = PPP_CONTROL(rptr);
rptr += PPP_HDRLEN;
len = cmp->m_len - PPP_HDRLEN;
seq = 0;
  847     for (i = 0; i < 2; ++i) {
  848         while (len <= 0) {
cmp = cmp->m_next;
  850             if (cmp == NULL)
  851                 return DECOMP_ERROR;
rptr = mtod(cmp, u_char *);
len = cmp->m_len;
  854         }
seq = (seq << 8) + *rptr++;
  856         --len;
  857     }
  859     /*
  860      * Check the sequence number and give up if it differs from
  861      * the value we're expecting.
  862      */
  863     if (seq != db->seqno) {
  864         if (db->debug)
printf("bsd_decomp%d: bad sequence # %d, expected %d\n",
db->unit, seq, db->seqno - 1);
  867         return DECOMP_ERROR;
  868     }
  869     ++db->seqno;
  871     /*
  872      * Allocate one mbuf to start with.
  873      */
MGETHDR(dmp, M_DONTWAIT, MT_DATA);
  875     if (dmp == NULL)
  876         return DECOMP_ERROR;
mret = dmp;
dmp->m_len = 0;
dmp->m_next = NULL;
MCLGET(dmp, M_DONTWAIT);
dmp->m_data += db->hdrlen;
wptr = mtod(dmp, u_char *);
space = M_TRAILINGSPACE(dmp) - PPP_HDRLEN + 1;
  885     /*
  886      * Fill in the ppp header, but not the last byte of the protocol
  887      * (that comes from the decompressed data).
  888      */
wptr[0] = adrs;
wptr[1] = ctrl;
wptr[2] = 0;
wptr += PPP_HDRLEN - 1;
ilen = len;
oldcode = CLEAR;
explen = 0;
  897     for (;;) {
  898         if (len == 0) {
cmp = cmp->m_next;
  900             if (!cmp)           /* quit at end of message */
  901                 break;
rptr = mtod(cmp, u_char *);
len = cmp->m_len;
ilen += len;
  905             continue;           /* handle 0-length buffers */
  906         }
  908         /*
  909          * Accumulate bytes until we have a complete code.
  910          * Then get the next code, relying on the 32-bit,
  911          * unsigned accm to mask the result.
  912          */
bitno -= 8;
accm |= *rptr++ << bitno;
  915         --len;
  916         if (tgtbitno < bitno)
  917             continue;
incode = accm >> tgtbitno;
accm <<= n_bits;
bitno += n_bits;
  922         if (incode == CLEAR) {
  923             /*
  924              * The dictionary must only be cleared at
  925              * the end of a packet.  But there could be an
  926              * empty mbuf at the end.
  927              */
  928             if (len > 0 || cmp->m_next != NULL) {
  929                 while ((cmp = cmp->m_next) != NULL)
len += cmp->m_len;
  931                 if (len > 0) {
m_freem(mret);
  933                     if (db->debug)
printf("bsd_decomp%d: bad CLEAR\n", db->unit);
  935                     return DECOMP_FATALERROR;   /* probably a bug */
  936                 }
  937             }
bsd_clear(db);
explen = ilen = 0;
  940             break;
  941         }
  943         if (incode > max_ent + 2 || incode > db->maxmaxcode
  944             || (incode > max_ent && oldcode == CLEAR)) {
m_freem(mret);
  946             if (db->debug) {
printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
db->unit, incode, oldcode);
printf("max_ent=0x%x explen=%d seqno=%d\n",
max_ent, explen, db->seqno);
  951             }
  952             return DECOMP_FATALERROR;   /* probably a bug */
  953         }
  955         /* Special case for KwKwK string. */
  956         if (incode > max_ent) {
finchar = oldcode;
extra = 1;
  959         } else {
finchar = incode;
extra = 0;
  962         }
codelen = db->lens[finchar];
explen += codelen + extra;
  966         if (explen > db->mru + 1) {
m_freem(mret);
  968             if (db->debug) {
printf("bsd_decomp%d: ran out of mru\n", db->unit);
  970 #ifdef DEBUG
  971                 while ((cmp = cmp->m_next) != NULL)
len += cmp->m_len;
printf("  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
len, finchar, codelen, explen);
  975 #endif
  976             }
  977             return DECOMP_FATALERROR;
  978         }
  980         /*
  981          * For simplicity, the decoded characters go in a single mbuf,
  982          * so we allocate a single extra cluster mbuf if necessary.
  983          */
  984         if ((space -= codelen + extra) < 0) {
dmp->m_len = wptr - mtod(dmp, u_char *);
MGET(m, M_DONTWAIT, MT_DATA);
  987             if (m == NULL) {
m_freem(mret);
  989                 return DECOMP_ERROR;
  990             }
m->m_len = 0;
m->m_next = NULL;
dmp->m_next = m;
MCLGET(m, M_DONTWAIT);
space = M_TRAILINGSPACE(m) - (codelen + extra);
  996             if (space < 0) {
  997                 /* now that's what I call *compression*. */
m_freem(mret);
  999                 return DECOMP_ERROR;
 1000             }
dmp = m;
wptr = mtod(dmp, u_char *);
 1003         }
 1005         /*
 1006          * Decode this code and install it in the decompressed buffer.
 1007          */
p = (wptr += codelen);
 1009         while (finchar > LAST) {
dictp = &db->dict[db->dict[finchar].cptr];
 1011 #ifdef DEBUG
 1012             if (--codelen <= 0 || dictp->codem1 != finchar-1)
 1013                 goto bad;
 1014 #endif
 1015             *--p = dictp->f.hs.suffix;
finchar = dictp->f.hs.prefix;
 1017         }
 1018         *--p = finchar;
 1020 #ifdef DEBUG
 1021         if (--codelen != 0)
printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
db->unit, codelen, incode, max_ent);
 1024 #endif
 1026         if (extra)              /* the KwKwK case again */
 1027             *wptr++ = finchar;
 1029         /*
 1030          * If not first code in a packet, and
 1031          * if not out of code space, then allocate a new code.
 1032          *
 1033          * Keep the hash table correct so it can be used
 1034          * with uncompressed packets.
 1035          */
 1036         if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
 1037             struct bsd_dict *dictp2;
u_int32_t fcode;
u_int32_t hval, disp;
fcode = BSD_KEY(oldcode,finchar);
hval = BSD_HASH(oldcode,finchar,db->hshift);
dictp = &db->dict[hval];
 1045             /* look for a free hash table entry */
 1046             if (dictp->codem1 < max_ent) {
disp = (hval == 0) ? 1 : hval;
 1048                 do {
hval += disp;
 1050                     if (hval >= db->hsize)
hval -= db->hsize;
dictp = &db->dict[hval];
 1053                 } while (dictp->codem1 < max_ent);
 1054             }
 1056             /*
 1057              * Invalidate previous hash table entry
 1058              * assigned this code, and then take it over
 1059              */
dictp2 = &db->dict[max_ent+1];
 1061             if (db->dict[dictp2->cptr].codem1 == max_ent) {
db->dict[dictp2->cptr].codem1 = BADCODEM1;
 1063             }
dictp2->cptr = hval;
dictp->codem1 = max_ent;
dictp->f.fcode = fcode;
db->max_ent = ++max_ent;
db->lens[max_ent] = db->lens[oldcode]+1;
 1071             /* Expand code size if needed. */
 1072             if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
db->n_bits = ++n_bits;
tgtbitno = 32-n_bits;
 1075             }
 1076         }
oldcode = incode;
 1078     }
dmp->m_len = wptr - mtod(dmp, u_char *);
 1081     /*
 1082      * Keep the checkpoint right so that incompressible packets
 1083      * clear the dictionary at the right times.
 1084      */
db->bytes_out += ilen;
db->in_count += explen;
 1087     if (bsd_check(db) && db->debug) {
printf("bsd_decomp%d: peer should have cleared dictionary\n",
db->unit);
 1090     }
 1092     ++db->comp_count;
db->comp_bytes += ilen + BSD_OVHD;
 1094     ++db->uncomp_count;
db->uncomp_bytes += explen;
 1097     *dmpp = mret;
 1098     return DECOMP_OK;
 1100 #ifdef DEBUG
bad:
 1102     if (codelen <= 0) {
printf("bsd_decomp%d: fell off end of chain ", db->unit);
printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
incode, finchar, db->dict[finchar].cptr, max_ent);
 1106     } else if (dictp->codem1 != finchar-1) {
printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",
db->unit, incode, finchar);
printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode,
db->dict[finchar].cptr, dictp->codem1);
 1111     }
m_freem(mret);
 1113     return DECOMP_FATALERROR;
 1114 #endif /* DEBUG */
 1115 }
 1116 #endif /* DO_BSD_COMPRESS */