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/7.4/sys/net/bsd_comp.c 163606 2006-10-22 11:52:19Z 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/malloc.h>
   49 #include <sys/mbuf.h>
   50 #include <sys/mutex.h>
   51 
   52 #include <net/ppp_defs.h>
   53 
   54 #define PACKETPTR       struct mbuf *
   55 #include <net/ppp_comp.h>
   56 
   57 #include <security/mac/mac_framework.h>
   58 
   59 /*
   60  * PPP "BSD compress" compression
   61  *  The differences between this compression and the classic BSD LZW
   62  *  source are obvious from the requirement that the classic code worked
   63  *  with files while this handles arbitrarily long streams that
   64  *  are broken into packets.  They are:
   65  *
   66  *      When the code size expands, a block of junk is not emitted by
   67  *          the compressor and not expected by the decompressor.
   68  *
   69  *      New codes are not necessarily assigned every time an old
   70  *          code is output by the compressor.  This is because a packet
   71  *          end forces a code to be emitted, but does not imply that a
   72  *          new sequence has been seen.
   73  *
   74  *      The compression ratio is checked at the first end of a packet
   75  *          after the appropriate gap.  Besides simplifying and speeding
   76  *          things up, this makes it more likely that the transmitter
   77  *          and receiver will agree when the dictionary is cleared when
   78  *          compression is not going well.
   79  */
   80 
   81 /*
   82  * A dictionary for doing BSD compress.
   83  */
   84 struct bsd_db {
   85     int     totlen;                     /* length of this structure */
   86     u_int   hsize;                      /* size of the hash table */
   87     u_char  hshift;                     /* used in hash function */
   88     u_char  n_bits;                     /* current bits/code */
   89     u_char  maxbits;
   90     u_char  debug;
   91     u_char  unit;
   92     u_int16_t seqno;                    /* sequence # of next packet */
   93     u_int   hdrlen;                     /* header length to preallocate */
   94     u_int   mru;
   95     u_int   maxmaxcode;                 /* largest valid code */
   96     u_int   max_ent;                    /* largest code in use */
   97     u_int   in_count;                   /* uncompressed bytes, aged */
   98     u_int   bytes_out;                  /* compressed bytes, aged */
   99     u_int   ratio;                      /* recent compression ratio */
  100     u_int   checkpoint;                 /* when to next check the ratio */
  101     u_int   clear_count;                /* times dictionary cleared */
  102     u_int   incomp_count;               /* incompressible packets */
  103     u_int   incomp_bytes;               /* incompressible bytes */
  104     u_int   uncomp_count;               /* uncompressed packets */
  105     u_int   uncomp_bytes;               /* uncompressed bytes */
  106     u_int   comp_count;                 /* compressed packets */
  107     u_int   comp_bytes;                 /* compressed bytes */
  108     u_int16_t *lens;                    /* array of lengths of codes */
  109     struct bsd_dict {
  110         union {                         /* hash value */
  111             u_int32_t   fcode;
  112             struct {
  113 #if BYTE_ORDER == LITTLE_ENDIAN
  114                 u_int16_t prefix;       /* preceding code */
  115                 u_char  suffix;         /* last character of new code */
  116                 u_char  pad;
  117 #else
  118                 u_char  pad;
  119                 u_char  suffix;         /* last character of new code */
  120                 u_int16_t prefix;       /* preceding code */
  121 #endif
  122             } hs;
  123         } f;
  124         u_int16_t codem1;               /* output of hash table -1 */
  125         u_int16_t cptr;                 /* map code to hash table entry */
  126     } dict[1];
  127 };
  128 
  129 #define BSD_OVHD        2               /* BSD compress overhead/packet */
  130 #define BSD_INIT_BITS   BSD_MIN_BITS
  131 
  132 static void     bsd_clear(struct bsd_db *db);
  133 static int      bsd_check(struct bsd_db *db);
  134 static void     *bsd_alloc(u_char *options, int opt_len, int decomp);
  135 static int      bsd_init(struct bsd_db *db, u_char *options, int opt_len,
  136                     int unit, int hdrlen, int mru, int debug, int decomp);
  137 static void     *bsd_comp_alloc(u_char *options, int opt_len);
  138 static void     *bsd_decomp_alloc(u_char *options, int opt_len);
  139 static void     bsd_free(void *state);
  140 static int      bsd_comp_init(void *state, u_char *options, int opt_len,
  141                     int unit, int hdrlen, int debug);
  142 static int      bsd_decomp_init(void *state, u_char *options, int opt_len,
  143                     int unit, int hdrlen, int mru, int debug);
  144 static int      bsd_compress(void *state, struct mbuf **mret, struct mbuf *mp,
  145                     int slen, int maxolen);
  146 static void     bsd_incomp(void *state, struct mbuf *dmsg);
  147 static int      bsd_decompress(void *state, struct mbuf *cmp,
  148                     struct mbuf **dmpp);
  149 static void     bsd_reset(void *state);
  150 static void     bsd_comp_stats(void *state, struct compstat *stats);
  151 
  152 /*
  153  * Procedures exported to if_ppp.c.
  154  */
  155 struct compressor ppp_bsd_compress = {
  156     CI_BSD_COMPRESS,            /* compress_proto */
  157     bsd_comp_alloc,             /* comp_alloc */
  158     bsd_free,                   /* comp_free */
  159     bsd_comp_init,              /* comp_init */
  160     bsd_reset,                  /* comp_reset */
  161     bsd_compress,               /* compress */
  162     bsd_comp_stats,             /* comp_stat */
  163     bsd_decomp_alloc,           /* decomp_alloc */
  164     bsd_free,                   /* decomp_free */
  165     bsd_decomp_init,            /* decomp_init */
  166     bsd_reset,                  /* decomp_reset */
  167     bsd_decompress,             /* decompress */
  168     bsd_incomp,                 /* incomp */
  169     bsd_comp_stats,             /* decomp_stat */
  170 };
  171 
  172 /*
  173  * the next two codes should not be changed lightly, as they must not
  174  * lie within the contiguous general code space.
  175  */
  176 #define CLEAR   256                     /* table clear output code */
  177 #define FIRST   257                     /* first free entry */
  178 #define LAST    255
  179 
  180 #define MAXCODE(b)      ((1 << (b)) - 1)
  181 #define BADCODEM1       MAXCODE(BSD_MAX_BITS)
  182 
  183 #define BSD_HASH(prefix,suffix,hshift)  ((((u_int32_t)(suffix)) << (hshift)) \
  184                                          ^ (u_int32_t)(prefix))
  185 #define BSD_KEY(prefix,suffix)          ((((u_int32_t)(suffix)) << 16) \
  186                                          + (u_int32_t)(prefix))
  187 
  188 #define CHECK_GAP       10000           /* Ratio check interval */
  189 
  190 #define RATIO_SCALE_LOG 8
  191 #define RATIO_SCALE     (1<<RATIO_SCALE_LOG)
  192 #define RATIO_MAX       (0x7fffffff>>RATIO_SCALE_LOG)
  193 
  194 /*
  195  * clear the dictionary
  196  */
  197 static void
  198 bsd_clear(db)
  199     struct bsd_db *db;
  200 {
  201     db->clear_count++;
  202     db->max_ent = FIRST-1;
  203     db->n_bits = BSD_INIT_BITS;
  204     db->ratio = 0;
  205     db->bytes_out = 0;
  206     db->in_count = 0;
  207     db->checkpoint = CHECK_GAP;
  208 }
  209 
  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 */
  224 bsd_check(db)
  225     struct bsd_db *db;
  226 {
  227     u_int new_ratio;
  228 
  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) {
  233             db->in_count -= db->in_count/4;
  234             db->bytes_out -= db->bytes_out/4;
  235         }
  236 
  237         db->checkpoint = db->in_count + CHECK_GAP;
  238 
  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              */
  247             new_ratio = db->in_count << RATIO_SCALE_LOG;
  248             if (db->bytes_out != 0)
  249                 new_ratio /= db->bytes_out;
  250 
  251             if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE) {
  252                 bsd_clear(db);
  253                 return 1;
  254             }
  255             db->ratio = new_ratio;
  256         }
  257     }
  258     return 0;
  259 }
  260 
  261 /*
  262  * Return statistics.
  263  */
  264 static void
  265 bsd_comp_stats(state, stats)
  266     void *state;
  267     struct compstat *stats;
  268 {
  269     struct bsd_db *db = (struct bsd_db *) state;
  270     u_int out;
  271 
  272     stats->unc_bytes = db->uncomp_bytes;
  273     stats->unc_packets = db->uncomp_count;
  274     stats->comp_bytes = db->comp_bytes;
  275     stats->comp_packets = db->comp_count;
  276     stats->inc_bytes = db->incomp_bytes;
  277     stats->inc_packets = db->incomp_count;
  278     stats->ratio = db->in_count;
  279     out = db->bytes_out;
  280     if (stats->ratio <= 0x7fffff)
  281         stats->ratio <<= 8;
  282     else
  283         out >>= 8;
  284     if (out != 0)
  285         stats->ratio /= out;
  286 }
  287 
  288 /*
  289  * Reset state, as on a CCP ResetReq.
  290  */
  291 static void
  292 bsd_reset(state)
  293     void *state;
  294 {
  295     struct bsd_db *db = (struct bsd_db *) state;
  296 
  297     db->seqno = 0;
  298     bsd_clear(db);
  299     db->clear_count = 0;
  300 }
  301 
  302 /*
  303  * Allocate space for a (de) compressor.
  304  */
  305 static void *
  306 bsd_alloc(options, opt_len, decomp)
  307     u_char *options;
  308     int opt_len, decomp;
  309 {
  310     int bits;
  311     u_int newlen, hsize, hshift, maxmaxcode;
  312     struct bsd_db *db;
  313 
  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;
  318     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 */
  324         hsize = 5003;
  325         hshift = 4;
  326         break;
  327     case 13:                    /* needs 176784 */
  328         hsize = 9001;
  329         hshift = 5;
  330         break;
  331     case 14:                    /* needs 353744 */
  332         hsize = 18013;
  333         hshift = 6;
  334         break;
  335     case 15:                    /* needs 691440 */
  336         hsize = 35023;
  337         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     }
  346 
  347     maxmaxcode = MAXCODE(bits);
  348     newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0]));
  349     MALLOC(db, struct bsd_db *, newlen, M_DEVBUF, M_NOWAIT);
  350     if (!db)
  351         return NULL;
  352     bzero(db, sizeof(*db) - sizeof(db->dict));
  353 
  354     if (!decomp) {
  355         db->lens = NULL;
  356     } else {
  357         MALLOC(db->lens, u_int16_t *, (maxmaxcode+1) * sizeof(db->lens[0]),
  358                M_DEVBUF, M_NOWAIT);
  359         if (!db->lens) {
  360             free(db, M_DEVBUF);
  361             return NULL;
  362         }
  363     }
  364 
  365     db->totlen = newlen;
  366     db->hsize = hsize;
  367     db->hshift = hshift;
  368     db->maxmaxcode = maxmaxcode;
  369     db->maxbits = bits;
  370 
  371     return (void *) db;
  372 }
  373 
  374 static void
  375 bsd_free(state)
  376     void *state;
  377 {
  378     struct bsd_db *db = (struct bsd_db *) state;
  379 
  380     if (db->lens)
  381         free(db->lens, M_DEVBUF);
  382     free(db, M_DEVBUF);
  383 }
  384 
  385 static void *
  386 bsd_comp_alloc(options, opt_len)
  387     u_char *options;
  388     int opt_len;
  389 {
  390     return bsd_alloc(options, opt_len, 0);
  391 }
  392 
  393 static void *
  394 bsd_decomp_alloc(options, opt_len)
  395     u_char *options;
  396     int opt_len;
  397 {
  398     return bsd_alloc(options, opt_len, 1);
  399 }
  400 
  401 /*
  402  * Initialize the database.
  403  */
  404 static int
  405 bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp)
  406     struct bsd_db *db;
  407     u_char *options;
  408     int opt_len, unit, hdrlen, mru, debug, decomp;
  409 {
  410     int i;
  411 
  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;
  418 
  419     if (decomp) {
  420         i = LAST+1;
  421         while (i != 0)
  422             db->lens[--i] = 1;
  423     }
  424     i = db->hsize;
  425     while (i != 0) {
  426         db->dict[--i].codem1 = BADCODEM1;
  427         db->dict[i].cptr = 0;
  428     }
  429 
  430     db->unit = unit;
  431     db->hdrlen = hdrlen;
  432     db->mru = mru;
  433 #ifndef DEBUG
  434     if (debug)
  435 #endif
  436         db->debug = 1;
  437 
  438     bsd_reset(db);
  439 
  440     return 1;
  441 }
  442 
  443 static int
  444 bsd_comp_init(state, options, opt_len, unit, hdrlen, debug)
  445     void *state;
  446     u_char *options;
  447     int opt_len, unit, hdrlen, debug;
  448 {
  449     return bsd_init((struct bsd_db *) state, options, opt_len,
  450                     unit, hdrlen, 0, debug, 0);
  451 }
  452 
  453 static int
  454 bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug)
  455     void *state;
  456     u_char *options;
  457     int opt_len, unit, hdrlen, mru, debug;
  458 {
  459     return bsd_init((struct bsd_db *) state, options, opt_len,
  460                     unit, hdrlen, mru, debug, 1);
  461 }
  462 
  463 
  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 static int                                      /* new slen */
  470 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;
  479     u_int max_ent = db->max_ent;
  480     u_int n_bits = db->n_bits;
  481     u_int bitno = 32;
  482     u_int32_t accm = 0, fcode;
  483     struct bsd_dict *dictp;
  484     u_char c;
  485     int hval, disp, ent, ilen;
  486     u_char *rptr, *wptr;
  487     u_char *cp_end;
  488     int olen;
  489     struct mbuf *m;
  490 
  491 #define PUTBYTE(v) {                                    \
  492     ++olen;                                             \
  493     if (wptr) {                                         \
  494         *wptr++ = (v);                                  \
  495         if (wptr >= cp_end) {                           \
  496             m->m_len = wptr - mtod(m, u_char *);        \
  497             MGET(m->m_next, M_DONTWAIT, MT_DATA);       \
  498             m = m->m_next;                              \
  499             if (m) {                                    \
  500                 m->m_len = 0;                           \
  501                 if (maxolen - olen > MLEN)              \
  502                     MCLGET(m, M_DONTWAIT);              \
  503                 wptr = mtod(m, u_char *);               \
  504                 cp_end = wptr + M_TRAILINGSPACE(m);     \
  505             } else                                      \
  506                 wptr = NULL;                            \
  507         }                                               \
  508     }                                                   \
  509 }
  510 
  511 #define OUTPUT(ent) {                                   \
  512     bitno -= n_bits;                                    \
  513     accm |= ((ent) << bitno);                           \
  514     do {                                                \
  515         PUTBYTE(accm >> 24);                            \
  516         accm <<= 8;                                     \
  517         bitno += 8;                                     \
  518     } while (bitno <= 24);                              \
  519 }
  520 
  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      */
  526     rptr = mtod(mp, u_char *);
  527     ent = PPP_PROTOCOL(rptr);
  528     if (ent < 0x21 || ent > 0xf9) {
  529         *mret = NULL;
  530         return slen;
  531     }
  532 
  533     /* Don't generate compressed packets which are larger than
  534        the uncompressed packet. */
  535     if (maxolen > slen)
  536         maxolen = slen;
  537 
  538     /* Allocate one mbuf to start with. */
  539     MGET(m, M_DONTWAIT, MT_DATA);
  540     *mret = m;
  541     if (m != NULL) {
  542         m->m_len = 0;
  543         if (maxolen + db->hdrlen > MLEN)
  544             MCLGET(m, M_DONTWAIT);
  545         m->m_data += db->hdrlen;
  546         wptr = mtod(m, u_char *);
  547         cp_end = wptr + M_TRAILINGSPACE(m);
  548     } else
  549         wptr = cp_end = NULL;
  550 
  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;
  564 
  565     olen = 0;
  566     rptr += PPP_HDRLEN;
  567     slen = mp->m_len - PPP_HDRLEN;
  568     ilen = slen + 1;
  569     for (;;) {
  570         if (slen <= 0) {
  571             mp = mp->m_next;
  572             if (!mp)
  573                 break;
  574             rptr = mtod(mp, u_char *);
  575             slen = mp->m_len;
  576             if (!slen)
  577                 continue;   /* handle 0-length buffers */
  578             ilen += slen;
  579         }
  580 
  581         slen--;
  582         c = *rptr++;
  583         fcode = BSD_KEY(ent, c);
  584         hval = BSD_HASH(ent, c, hshift);
  585         dictp = &db->dict[hval];
  586 
  587         /* Validate and then check the entry. */
  588         if (dictp->codem1 >= max_ent)
  589             goto nomatch;
  590         if (dictp->f.fcode == fcode) {
  591             ent = dictp->codem1+1;
  592             continue;   /* found (prefix,suffix) */
  593         }
  594 
  595         /* continue probing until a match or invalid entry */
  596         disp = (hval == 0) ? 1 : hval;
  597         do {
  598             hval += disp;
  599             if (hval >= db->hsize)
  600                 hval -= db->hsize;
  601             dictp = &db->dict[hval];
  602             if (dictp->codem1 >= max_ent)
  603                 goto nomatch;
  604         } while (dictp->f.fcode != fcode);
  605         ent = dictp->codem1 + 1;        /* finally found (prefix,suffix) */
  606         continue;
  607 
  608     nomatch:
  609         OUTPUT(ent);            /* output the prefix */
  610 
  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))
  616                 db->n_bits = ++n_bits;
  617 
  618             /* Invalidate old hash table entry using
  619              * this code, and then take it over.
  620              */
  621             dictp2 = &db->dict[max_ent+1];
  622             if (db->dict[dictp2->cptr].codem1 == max_ent)
  623                 db->dict[dictp2->cptr].codem1 = BADCODEM1;
  624             dictp2->cptr = hval;
  625             dictp->codem1 = max_ent;
  626             dictp->f.fcode = fcode;
  627 
  628             db->max_ent = ++max_ent;
  629         }
  630         ent = c;
  631     }
  632 
  633     OUTPUT(ent);                /* output the last code */
  634     db->bytes_out += olen;
  635     db->in_count += ilen;
  636     if (bitno < 32)
  637         ++db->bytes_out;        /* count complete bytes */
  638 
  639     if (bsd_check(db))
  640         OUTPUT(CLEAR);          /* do not count the CLEAR */
  641 
  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)
  647         PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
  648 
  649     if (m != NULL) {
  650         m->m_len = wptr - mtod(m, u_char *);
  651         m->m_next = NULL;
  652     }
  653 
  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)
  659         db->n_bits++;
  660 
  661     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) {
  666             m_freem(*mret);
  667             *mret = NULL;
  668         }
  669         ++db->incomp_count;
  670         db->incomp_bytes += ilen;
  671     } else {
  672         ++db->comp_count;
  673         db->comp_bytes += olen + BSD_OVHD;
  674     }
  675 
  676     return olen + PPP_HDRLEN + BSD_OVHD;
  677 #undef OUTPUT
  678 #undef PUTBYTE
  679 }
  680 
  681 
  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
  687 bsd_incomp(state, dmsg)
  688     void *state;
  689     struct mbuf *dmsg;
  690 {
  691     struct bsd_db *db = (struct bsd_db *) state;
  692     u_int hshift = db->hshift;
  693     u_int max_ent = db->max_ent;
  694     u_int n_bits = db->n_bits;
  695     struct bsd_dict *dictp;
  696     u_int32_t fcode;
  697     u_char c;
  698     u_int32_t hval, disp;
  699     int slen, ilen;
  700     u_int bitno = 7;
  701     u_char *rptr;
  702     u_int ent;
  703 
  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      */
  709     rptr = mtod(dmsg, u_char *);
  710     ent = PPP_PROTOCOL(rptr);
  711     if (ent < 0x21 || ent > 0xf9)
  712         return;
  713 
  714     db->seqno++;
  715     ilen = 1;           /* count the protocol as 1 byte */
  716     rptr += PPP_HDRLEN;
  717     slen = dmsg->m_len - PPP_HDRLEN;
  718     for (;;) {
  719         if (slen <= 0) {
  720             dmsg = dmsg->m_next;
  721             if (!dmsg)
  722                 break;
  723             rptr = mtod(dmsg, u_char *);
  724             slen = dmsg->m_len;
  725             continue;
  726         }
  727         ilen += slen;
  728 
  729         do {
  730             c = *rptr++;
  731             fcode = BSD_KEY(ent, c);
  732             hval = BSD_HASH(ent, c, hshift);
  733             dictp = &db->dict[hval];
  734 
  735             /* validate and then check the entry */
  736             if (dictp->codem1 >= max_ent)
  737                 goto nomatch;
  738             if (dictp->f.fcode == fcode) {
  739                 ent = dictp->codem1+1;
  740                 continue;   /* found (prefix,suffix) */
  741             }
  742 
  743             /* continue probing until a match or invalid entry */
  744             disp = (hval == 0) ? 1 : hval;
  745             do {
  746                 hval += disp;
  747                 if (hval >= db->hsize)
  748                     hval -= db->hsize;
  749                 dictp = &db->dict[hval];
  750                 if (dictp->codem1 >= max_ent)
  751                     goto nomatch;
  752             } while (dictp->f.fcode != fcode);
  753             ent = dictp->codem1+1;
  754             continue;   /* finally found (prefix,suffix) */
  755 
  756         nomatch:                /* output (count) the prefix */
  757             bitno += n_bits;
  758 
  759             /* code -> hashtable */
  760             if (max_ent < db->maxmaxcode) {
  761                 struct bsd_dict *dictp2;
  762                 /* expand code size if needed */
  763                 if (max_ent >= MAXCODE(n_bits))
  764                     db->n_bits = ++n_bits;
  765 
  766                 /* Invalidate previous hash table entry
  767                  * assigned this code, and then take it over.
  768                  */
  769                 dictp2 = &db->dict[max_ent+1];
  770                 if (db->dict[dictp2->cptr].codem1 == max_ent)
  771                     db->dict[dictp2->cptr].codem1 = BADCODEM1;
  772                 dictp2->cptr = hval;
  773                 dictp->codem1 = max_ent;
  774                 dictp->f.fcode = fcode;
  775 
  776                 db->max_ent = ++max_ent;
  777                 db->lens[max_ent] = db->lens[ent]+1;
  778             }
  779             ent = c;
  780         } while (--slen != 0);
  781     }
  782     bitno += n_bits;            /* output (count) the last code */
  783     db->bytes_out += bitno/8;
  784     db->in_count += ilen;
  785     (void)bsd_check(db);
  786 
  787     ++db->incomp_count;
  788     db->incomp_bytes += ilen;
  789     ++db->uncomp_count;
  790     db->uncomp_bytes += ilen;
  791 
  792     /* Increase code size if we would have without the packet
  793      * boundary and as the decompressor will.
  794      */
  795     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
  796         db->n_bits++;
  797 }
  798 
  799 
  800 /*
  801  * Decompress "BSD Compress".
  802  *
  803  * Because of patent problems, we return DECOMP_ERROR for errors
  804  * found by inspecting the input data and for system problems, but
  805  * DECOMP_FATALERROR for any errors which could possibly be said to
  806  * be being detected "after" decompression.  For DECOMP_ERROR,
  807  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
  808  * infringing a patent of Motorola's if we do, so we take CCP down
  809  * instead.
  810  *
  811  * Given that the frame has the correct sequence number and a good FCS,
  812  * errors such as invalid codes in the input most likely indicate a
  813  * bug, so we return DECOMP_FATALERROR for them in order to turn off
  814  * compression, even though they are detected by inspecting the input.
  815  */
  816 static int
  817 bsd_decompress(state, cmp, dmpp)
  818     void *state;
  819     struct mbuf *cmp, **dmpp;
  820 {
  821     struct bsd_db *db = (struct bsd_db *) state;
  822     u_int max_ent = db->max_ent;
  823     u_int32_t accm = 0;
  824     u_int bitno = 32;           /* 1st valid bit in accm */
  825     u_int n_bits = db->n_bits;
  826     u_int tgtbitno = 32-n_bits; /* bitno when we have a code */
  827     struct bsd_dict *dictp;
  828     int explen, i, seq, len;
  829     u_int incode, oldcode, finchar;
  830     u_char *p, *rptr, *wptr;
  831     struct mbuf *m, *dmp, *mret;
  832     int adrs, ctrl, ilen;
  833     int space, codelen, extra;
  834 
  835     /*
  836      * Save the address/control from the PPP header
  837      * and then get the sequence number.
  838      */
  839     *dmpp = NULL;
  840     rptr = mtod(cmp, u_char *);
  841     adrs = PPP_ADDRESS(rptr);
  842     ctrl = PPP_CONTROL(rptr);
  843     rptr += PPP_HDRLEN;
  844     len = cmp->m_len - PPP_HDRLEN;
  845     seq = 0;
  846     for (i = 0; i < 2; ++i) {
  847         while (len <= 0) {
  848             cmp = cmp->m_next;
  849             if (cmp == NULL)
  850                 return DECOMP_ERROR;
  851             rptr = mtod(cmp, u_char *);
  852             len = cmp->m_len;
  853         }
  854         seq = (seq << 8) + *rptr++;
  855         --len;
  856     }
  857 
  858     /*
  859      * Check the sequence number and give up if it differs from
  860      * the value we're expecting.
  861      */
  862     if (seq != db->seqno) {
  863         if (db->debug)
  864             printf("bsd_decomp%d: bad sequence # %d, expected %d\n",
  865                    db->unit, seq, db->seqno - 1);
  866         return DECOMP_ERROR;
  867     }
  868     ++db->seqno;
  869 
  870     /*
  871      * Allocate one mbuf to start with.
  872      */
  873     MGETHDR(dmp, M_DONTWAIT, MT_DATA);
  874     if (dmp == NULL)
  875         return DECOMP_ERROR;
  876     mret = dmp;
  877     dmp->m_len = 0;
  878     dmp->m_next = NULL;
  879     MCLGET(dmp, M_DONTWAIT);
  880     dmp->m_data += db->hdrlen;
  881     wptr = mtod(dmp, u_char *);
  882     space = M_TRAILINGSPACE(dmp) - PPP_HDRLEN + 1;
  883 #ifdef MAC
  884     mac_copy_mbuf(cmp, dmp);
  885 #endif
  886 
  887     /*
  888      * Fill in the ppp header, but not the last byte of the protocol
  889      * (that comes from the decompressed data).
  890      */
  891     wptr[0] = adrs;
  892     wptr[1] = ctrl;
  893     wptr[2] = 0;
  894     wptr += PPP_HDRLEN - 1;
  895 
  896     ilen = len;
  897     oldcode = CLEAR;
  898     explen = 0;
  899     for (;;) {
  900         if (len == 0) {
  901             cmp = cmp->m_next;
  902             if (!cmp)           /* quit at end of message */
  903                 break;
  904             rptr = mtod(cmp, u_char *);
  905             len = cmp->m_len;
  906             ilen += len;
  907             continue;           /* handle 0-length buffers */
  908         }
  909 
  910         /*
  911          * Accumulate bytes until we have a complete code.
  912          * Then get the next code, relying on the 32-bit,
  913          * unsigned accm to mask the result.
  914          */
  915         bitno -= 8;
  916         accm |= *rptr++ << bitno;
  917         --len;
  918         if (tgtbitno < bitno)
  919             continue;
  920         incode = accm >> tgtbitno;
  921         accm <<= n_bits;
  922         bitno += n_bits;
  923 
  924         if (incode == CLEAR) {
  925             /*
  926              * The dictionary must only be cleared at
  927              * the end of a packet.  But there could be an
  928              * empty mbuf at the end.
  929              */
  930             if (len > 0 || cmp->m_next != NULL) {
  931                 while ((cmp = cmp->m_next) != NULL)
  932                     len += cmp->m_len;
  933                 if (len > 0) {
  934                     m_freem(mret);
  935                     if (db->debug)
  936                         printf("bsd_decomp%d: bad CLEAR\n", db->unit);
  937                     return DECOMP_FATALERROR;   /* probably a bug */
  938                 }
  939             }
  940             bsd_clear(db);
  941             explen = ilen = 0;
  942             break;
  943         }
  944 
  945         if (incode > max_ent + 2 || incode > db->maxmaxcode
  946             || (incode > max_ent && oldcode == CLEAR)) {
  947             m_freem(mret);
  948             if (db->debug) {
  949                 printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
  950                        db->unit, incode, oldcode);
  951                 printf("max_ent=0x%x explen=%d seqno=%d\n",
  952                        max_ent, explen, db->seqno);
  953             }
  954             return DECOMP_FATALERROR;   /* probably a bug */
  955         }
  956 
  957         /* Special case for KwKwK string. */
  958         if (incode > max_ent) {
  959             finchar = oldcode;
  960             extra = 1;
  961         } else {
  962             finchar = incode;
  963             extra = 0;
  964         }
  965 
  966         codelen = db->lens[finchar];
  967         explen += codelen + extra;
  968         if (explen > db->mru + 1) {
  969             m_freem(mret);
  970             if (db->debug) {
  971                 printf("bsd_decomp%d: ran out of mru\n", db->unit);
  972 #ifdef DEBUG
  973                 while ((cmp = cmp->m_next) != NULL)
  974                     len += cmp->m_len;
  975                 printf("  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
  976                        len, finchar, codelen, explen);
  977 #endif
  978             }
  979             return DECOMP_FATALERROR;
  980         }
  981 
  982         /*
  983          * For simplicity, the decoded characters go in a single mbuf,
  984          * so we allocate a single extra cluster mbuf if necessary.
  985          */
  986         if ((space -= codelen + extra) < 0) {
  987             dmp->m_len = wptr - mtod(dmp, u_char *);
  988             MGET(m, M_DONTWAIT, MT_DATA);
  989             if (m == NULL) {
  990                 m_freem(mret);
  991                 return DECOMP_ERROR;
  992             }
  993             m->m_len = 0;
  994             m->m_next = NULL;
  995             dmp->m_next = m;
  996             MCLGET(m, M_DONTWAIT);
  997             space = M_TRAILINGSPACE(m) - (codelen + extra);
  998             if (space < 0) {
  999                 /* now that's what I call *compression*. */
 1000                 m_freem(mret);
 1001                 return DECOMP_ERROR;
 1002             }
 1003             dmp = m;
 1004             wptr = mtod(dmp, u_char *);
 1005         }
 1006 
 1007         /*
 1008          * Decode this code and install it in the decompressed buffer.
 1009          */
 1010         p = (wptr += codelen);
 1011         while (finchar > LAST) {
 1012             dictp = &db->dict[db->dict[finchar].cptr];
 1013 #ifdef DEBUG
 1014             if (--codelen <= 0 || dictp->codem1 != finchar-1)
 1015                 goto bad;
 1016 #endif
 1017             *--p = dictp->f.hs.suffix;
 1018             finchar = dictp->f.hs.prefix;
 1019         }
 1020         *--p = finchar;
 1021 
 1022 #ifdef DEBUG
 1023         if (--codelen != 0)
 1024             printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
 1025                    db->unit, codelen, incode, max_ent);
 1026 #endif
 1027 
 1028         if (extra)              /* the KwKwK case again */
 1029             *wptr++ = finchar;
 1030 
 1031         /*
 1032          * If not first code in a packet, and
 1033          * if not out of code space, then allocate a new code.
 1034          *
 1035          * Keep the hash table correct so it can be used
 1036          * with uncompressed packets.
 1037          */
 1038         if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
 1039             struct bsd_dict *dictp2;
 1040             u_int32_t fcode;
 1041             u_int32_t hval, disp;
 1042 
 1043             fcode = BSD_KEY(oldcode,finchar);
 1044             hval = BSD_HASH(oldcode,finchar,db->hshift);
 1045             dictp = &db->dict[hval];
 1046 
 1047             /* look for a free hash table entry */
 1048             if (dictp->codem1 < max_ent) {
 1049                 disp = (hval == 0) ? 1 : hval;
 1050                 do {
 1051                     hval += disp;
 1052                     if (hval >= db->hsize)
 1053                         hval -= db->hsize;
 1054                     dictp = &db->dict[hval];
 1055                 } while (dictp->codem1 < max_ent);
 1056             }
 1057 
 1058             /*
 1059              * Invalidate previous hash table entry
 1060              * assigned this code, and then take it over
 1061              */
 1062             dictp2 = &db->dict[max_ent+1];
 1063             if (db->dict[dictp2->cptr].codem1 == max_ent) {
 1064                 db->dict[dictp2->cptr].codem1 = BADCODEM1;
 1065             }
 1066             dictp2->cptr = hval;
 1067             dictp->codem1 = max_ent;
 1068             dictp->f.fcode = fcode;
 1069 
 1070             db->max_ent = ++max_ent;
 1071             db->lens[max_ent] = db->lens[oldcode]+1;
 1072 
 1073             /* Expand code size if needed. */
 1074             if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
 1075                 db->n_bits = ++n_bits;
 1076                 tgtbitno = 32-n_bits;
 1077             }
 1078         }
 1079         oldcode = incode;
 1080     }
 1081     dmp->m_len = wptr - mtod(dmp, u_char *);
 1082 
 1083     /*
 1084      * Keep the checkpoint right so that incompressible packets
 1085      * clear the dictionary at the right times.
 1086      */
 1087     db->bytes_out += ilen;
 1088     db->in_count += explen;
 1089     if (bsd_check(db) && db->debug) {
 1090         printf("bsd_decomp%d: peer should have cleared dictionary\n",
 1091                db->unit);
 1092     }
 1093 
 1094     ++db->comp_count;
 1095     db->comp_bytes += ilen + BSD_OVHD;
 1096     ++db->uncomp_count;
 1097     db->uncomp_bytes += explen;
 1098 
 1099     *dmpp = mret;
 1100     return DECOMP_OK;
 1101 
 1102 #ifdef DEBUG
 1103  bad:
 1104     if (codelen <= 0) {
 1105         printf("bsd_decomp%d: fell off end of chain ", db->unit);
 1106         printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
 1107                incode, finchar, db->dict[finchar].cptr, max_ent);
 1108     } else if (dictp->codem1 != finchar-1) {
 1109         printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",
 1110                db->unit, incode, finchar);
 1111         printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode,
 1112                db->dict[finchar].cptr, dictp->codem1);
 1113     }
 1114     m_freem(mret);
 1115     return DECOMP_FATALERROR;
 1116 #endif /* DEBUG */
 1117 }

Cache object: 2185a60a9505c44c09490c26d32639d3


[ 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.