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

Cache object: 510b3f64979290f8fb79a277b1a1a754


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