The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/net/bsd_comp.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * Because this code is derived from the 4.3BSD compress source:
    3  *
    4  *
    5  * Copyright (c) 1985, 1986 The Regents of the University of California.
    6  * All rights reserved.
    7  *
    8  * This code is derived from software contributed to Berkeley by
    9  * James A. Woods, derived from original work by Spencer Thomas
   10  * and Joseph Orost.
   11  *
   12  * Redistribution and use in source and binary forms, with or without
   13  * modification, are permitted provided that the following conditions
   14  * are met:
   15  * 1. Redistributions of source code must retain the above copyright
   16  *    notice, this list of conditions and the following disclaimer.
   17  * 2. Redistributions in binary form must reproduce the above copyright
   18  *    notice, this list of conditions and the following disclaimer in the
   19  *    documentation and/or other materials provided with the distribution.
   20  * 4. Neither the name of the University nor the names of its contributors
   21  *    may be used to endorse or promote products derived from this software
   22  *    without specific prior written permission.
   23  *
   24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   34  * SUCH DAMAGE.
   35  */
   36 
   37 /*
   38  * This version is for use with mbufs on BSD-derived systems.
   39  *
   40  * $FreeBSD: releng/6.4/sys/net/bsd_comp.c 147785 2005-07-05 23:39:51Z rwatson $
   41  */
   42 
   43 #include "opt_mac.h"
   44 
   45 #include <sys/param.h>
   46 #include <sys/systm.h>
   47 #include <sys/lock.h>
   48 #include <sys/mac.h>
   49 #include <sys/malloc.h>
   50 #include <sys/mbuf.h>
   51 #include <sys/mutex.h>
   52 
   53 #include <net/ppp_defs.h>
   54 
   55 #define PACKETPTR       struct mbuf *
   56 #include <net/ppp_comp.h>
   57 
   58 /*
   59  * PPP "BSD compress" compression
   60  *  The differences between this compression and the classic BSD LZW
   61  *  source are obvious from the requirement that the classic code worked
   62  *  with files while this handles arbitrarily long streams that
   63  *  are broken into packets.  They are:
   64  *
   65  *      When the code size expands, a block of junk is not emitted by
   66  *          the compressor and not expected by the decompressor.
   67  *
   68  *      New codes are not necessarily assigned every time an old
   69  *          code is output by the compressor.  This is because a packet
   70  *          end forces a code to be emitted, but does not imply that a
   71  *          new sequence has been seen.
   72  *
   73  *      The compression ratio is checked at the first end of a packet
   74  *          after the appropriate gap.  Besides simplifying and speeding
   75  *          things up, this makes it more likely that the transmitter
   76  *          and receiver will agree when the dictionary is cleared when
   77  *          compression is not going well.
   78  */
   79 
   80 /*
   81  * A dictionary for doing BSD compress.
   82  */
   83 struct bsd_db {
   84     int     totlen;                     /* length of this structure */
   85     u_int   hsize;                      /* size of the hash table */
   86     u_char  hshift;                     /* used in hash function */
   87     u_char  n_bits;                     /* current bits/code */
   88     u_char  maxbits;
   89     u_char  debug;
   90     u_char  unit;
   91     u_int16_t seqno;                    /* sequence # of next packet */
   92     u_int   hdrlen;                     /* header length to preallocate */
   93     u_int   mru;
   94     u_int   maxmaxcode;                 /* largest valid code */
   95     u_int   max_ent;                    /* largest code in use */
   96     u_int   in_count;                   /* uncompressed bytes, aged */
   97     u_int   bytes_out;                  /* compressed bytes, aged */
   98     u_int   ratio;                      /* recent compression ratio */
   99     u_int   checkpoint;                 /* when to next check the ratio */
  100     u_int   clear_count;                /* times dictionary cleared */
  101     u_int   incomp_count;               /* incompressible packets */
  102     u_int   incomp_bytes;               /* incompressible bytes */
  103     u_int   uncomp_count;               /* uncompressed packets */
  104     u_int   uncomp_bytes;               /* uncompressed bytes */
  105     u_int   comp_count;                 /* compressed packets */
  106     u_int   comp_bytes;                 /* compressed bytes */
  107     u_int16_t *lens;                    /* array of lengths of codes */
  108     struct bsd_dict {
  109         union {                         /* hash value */
  110             u_int32_t   fcode;
  111             struct {
  112 #if BYTE_ORDER == LITTLE_ENDIAN
  113                 u_int16_t prefix;       /* preceding code */
  114                 u_char  suffix;         /* last character of new code */
  115                 u_char  pad;
  116 #else
  117                 u_char  pad;
  118                 u_char  suffix;         /* last character of new code */
  119                 u_int16_t prefix;       /* preceding code */
  120 #endif
  121             } hs;
  122         } f;
  123         u_int16_t codem1;               /* output of hash table -1 */
  124         u_int16_t cptr;                 /* map code to hash table entry */
  125     } dict[1];
  126 };
  127 
  128 #define BSD_OVHD        2               /* BSD compress overhead/packet */
  129 #define BSD_INIT_BITS   BSD_MIN_BITS
  130 
  131 static void     bsd_clear(struct bsd_db *db);
  132 static int      bsd_check(struct bsd_db *db);
  133 static void     *bsd_alloc(u_char *options, int opt_len, int decomp);
  134 static int      bsd_init(struct bsd_db *db, u_char *options, int opt_len,
  135                     int unit, int hdrlen, int mru, int debug, 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, struct mbuf *mp,
  144                     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 static 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 static 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 #ifdef MAC
  883     mac_copy_mbuf(cmp, dmp);
  884 #endif
  885 
  886     /*
  887      * Fill in the ppp header, but not the last byte of the protocol
  888      * (that comes from the decompressed data).
  889      */
  890     wptr[0] = adrs;
  891     wptr[1] = ctrl;
  892     wptr[2] = 0;
  893     wptr += PPP_HDRLEN - 1;
  894 
  895     ilen = len;
  896     oldcode = CLEAR;
  897     explen = 0;
  898     for (;;) {
  899         if (len == 0) {
  900             cmp = cmp->m_next;
  901             if (!cmp)           /* quit at end of message */
  902                 break;
  903             rptr = mtod(cmp, u_char *);
  904             len = cmp->m_len;
  905             ilen += len;
  906             continue;           /* handle 0-length buffers */
  907         }
  908 
  909         /*
  910          * Accumulate bytes until we have a complete code.
  911          * Then get the next code, relying on the 32-bit,
  912          * unsigned accm to mask the result.
  913          */
  914         bitno -= 8;
  915         accm |= *rptr++ << bitno;
  916         --len;
  917         if (tgtbitno < bitno)
  918             continue;
  919         incode = accm >> tgtbitno;
  920         accm <<= n_bits;
  921         bitno += n_bits;
  922 
  923         if (incode == CLEAR) {
  924             /*
  925              * The dictionary must only be cleared at
  926              * the end of a packet.  But there could be an
  927              * empty mbuf at the end.
  928              */
  929             if (len > 0 || cmp->m_next != NULL) {
  930                 while ((cmp = cmp->m_next) != NULL)
  931                     len += cmp->m_len;
  932                 if (len > 0) {
  933                     m_freem(mret);
  934                     if (db->debug)
  935                         printf("bsd_decomp%d: bad CLEAR\n", db->unit);
  936                     return DECOMP_FATALERROR;   /* probably a bug */
  937                 }
  938             }
  939             bsd_clear(db);
  940             explen = ilen = 0;
  941             break;
  942         }
  943 
  944         if (incode > max_ent + 2 || incode > db->maxmaxcode
  945             || (incode > max_ent && oldcode == CLEAR)) {
  946             m_freem(mret);
  947             if (db->debug) {
  948                 printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
  949                        db->unit, incode, oldcode);
  950                 printf("max_ent=0x%x explen=%d seqno=%d\n",
  951                        max_ent, explen, db->seqno);
  952             }
  953             return DECOMP_FATALERROR;   /* probably a bug */
  954         }
  955 
  956         /* Special case for KwKwK string. */
  957         if (incode > max_ent) {
  958             finchar = oldcode;
  959             extra = 1;
  960         } else {
  961             finchar = incode;
  962             extra = 0;
  963         }
  964 
  965         codelen = db->lens[finchar];
  966         explen += codelen + extra;
  967         if (explen > db->mru + 1) {
  968             m_freem(mret);
  969             if (db->debug) {
  970                 printf("bsd_decomp%d: ran out of mru\n", db->unit);
  971 #ifdef DEBUG
  972                 while ((cmp = cmp->m_next) != NULL)
  973                     len += cmp->m_len;
  974                 printf("  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
  975                        len, finchar, codelen, explen);
  976 #endif
  977             }
  978             return DECOMP_FATALERROR;
  979         }
  980 
  981         /*
  982          * For simplicity, the decoded characters go in a single mbuf,
  983          * so we allocate a single extra cluster mbuf if necessary.
  984          */
  985         if ((space -= codelen + extra) < 0) {
  986             dmp->m_len = wptr - mtod(dmp, u_char *);
  987             MGET(m, M_DONTWAIT, MT_DATA);
  988             if (m == NULL) {
  989                 m_freem(mret);
  990                 return DECOMP_ERROR;
  991             }
  992             m->m_len = 0;
  993             m->m_next = NULL;
  994             dmp->m_next = m;
  995             MCLGET(m, M_DONTWAIT);
  996             space = M_TRAILINGSPACE(m) - (codelen + extra);
  997             if (space < 0) {
  998                 /* now that's what I call *compression*. */
  999                 m_freem(mret);
 1000                 return DECOMP_ERROR;
 1001             }
 1002             dmp = m;
 1003             wptr = mtod(dmp, u_char *);
 1004         }
 1005 
 1006         /*
 1007          * Decode this code and install it in the decompressed buffer.
 1008          */
 1009         p = (wptr += codelen);
 1010         while (finchar > LAST) {
 1011             dictp = &db->dict[db->dict[finchar].cptr];
 1012 #ifdef DEBUG
 1013             if (--codelen <= 0 || dictp->codem1 != finchar-1)
 1014                 goto bad;
 1015 #endif
 1016             *--p = dictp->f.hs.suffix;
 1017             finchar = dictp->f.hs.prefix;
 1018         }
 1019         *--p = finchar;
 1020 
 1021 #ifdef DEBUG
 1022         if (--codelen != 0)
 1023             printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
 1024                    db->unit, codelen, incode, max_ent);
 1025 #endif
 1026 
 1027         if (extra)              /* the KwKwK case again */
 1028             *wptr++ = finchar;
 1029 
 1030         /*
 1031          * If not first code in a packet, and
 1032          * if not out of code space, then allocate a new code.
 1033          *
 1034          * Keep the hash table correct so it can be used
 1035          * with uncompressed packets.
 1036          */
 1037         if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
 1038             struct bsd_dict *dictp2;
 1039             u_int32_t fcode;
 1040             u_int32_t hval, disp;
 1041 
 1042             fcode = BSD_KEY(oldcode,finchar);
 1043             hval = BSD_HASH(oldcode,finchar,db->hshift);
 1044             dictp = &db->dict[hval];
 1045 
 1046             /* look for a free hash table entry */
 1047             if (dictp->codem1 < max_ent) {
 1048                 disp = (hval == 0) ? 1 : hval;
 1049                 do {
 1050                     hval += disp;
 1051                     if (hval >= db->hsize)
 1052                         hval -= db->hsize;
 1053                     dictp = &db->dict[hval];
 1054                 } while (dictp->codem1 < max_ent);
 1055             }
 1056 
 1057             /*
 1058              * Invalidate previous hash table entry
 1059              * assigned this code, and then take it over
 1060              */
 1061             dictp2 = &db->dict[max_ent+1];
 1062             if (db->dict[dictp2->cptr].codem1 == max_ent) {
 1063                 db->dict[dictp2->cptr].codem1 = BADCODEM1;
 1064             }
 1065             dictp2->cptr = hval;
 1066             dictp->codem1 = max_ent;
 1067             dictp->f.fcode = fcode;
 1068 
 1069             db->max_ent = ++max_ent;
 1070             db->lens[max_ent] = db->lens[oldcode]+1;
 1071 
 1072             /* Expand code size if needed. */
 1073             if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
 1074                 db->n_bits = ++n_bits;
 1075                 tgtbitno = 32-n_bits;
 1076             }
 1077         }
 1078         oldcode = incode;
 1079     }
 1080     dmp->m_len = wptr - mtod(dmp, u_char *);
 1081 
 1082     /*
 1083      * Keep the checkpoint right so that incompressible packets
 1084      * clear the dictionary at the right times.
 1085      */
 1086     db->bytes_out += ilen;
 1087     db->in_count += explen;
 1088     if (bsd_check(db) && db->debug) {
 1089         printf("bsd_decomp%d: peer should have cleared dictionary\n",
 1090                db->unit);
 1091     }
 1092 
 1093     ++db->comp_count;
 1094     db->comp_bytes += ilen + BSD_OVHD;
 1095     ++db->uncomp_count;
 1096     db->uncomp_bytes += explen;
 1097 
 1098     *dmpp = mret;
 1099     return DECOMP_OK;
 1100 
 1101 #ifdef DEBUG
 1102  bad:
 1103     if (codelen <= 0) {
 1104         printf("bsd_decomp%d: fell off end of chain ", db->unit);
 1105         printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
 1106                incode, finchar, db->dict[finchar].cptr, max_ent);
 1107     } else if (dictp->codem1 != finchar-1) {
 1108         printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",
 1109                db->unit, incode, finchar);
 1110         printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode,
 1111                db->dict[finchar].cptr, dictp->codem1);
 1112     }
 1113     m_freem(mret);
 1114     return DECOMP_FATALERROR;
 1115 #endif /* DEBUG */
 1116 }

Cache object: 9c86080c0deeeba8030e665262ba70b1


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.