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

Cache object: 4482070d8049ae714f2e71713bb29064


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