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/mppcc.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) 2002-2004 Jan Dubiec <jdx@slackware.pl>
    3  * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
    4  * All rights reserved.
    5  *
    6  * Redistribution and use in source and binary forms, with or without
    7  * modification, are permitted provided that the following conditions
    8  * are met:
    9  * 1. Redistributions of source code must retain the above copyright
   10  *    notice unmodified, this list of conditions, and the following
   11  *    disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   26  * SUCH DAMAGE.
   27  *
   28  * $FreeBSD: releng/11.2/sys/net/mppcc.c 302773 2016-07-13 15:51:58Z pfg $
   29  */
   30 
   31 /*
   32  * MPPC decompression library.
   33  * Version 1.0
   34  *
   35  * Note that Hi/Fn (later acquired by Exar Corporation) held US patents
   36  * on some implementation-critical aspects of MPPC compression.
   37  * These patents lapsed due to non-payment of fees in 2007 and by 2015
   38  * expired altogether.
   39  */
   40 
   41 #include <sys/param.h>
   42 #include <sys/systm.h>
   43 
   44 #include <net/mppc.h>
   45 
   46 #define MPPE_HIST_LEN          8192
   47 
   48 #define HASH(x)         (((40543*(((((x)[0]<<4)^(x)[1])<<4)^(x)[2]))>>4) & 0x1fff)
   49 
   50 struct MPPC_comp_state {
   51     uint8_t     hist[2*MPPE_HIST_LEN];
   52     uint16_t    histptr;
   53     uint16_t    hash[MPPE_HIST_LEN];
   54 };
   55 
   56 /* Inserts 1 to 8 bits into the output buffer. */
   57 static void __inline 
   58 putbits8(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
   59 {
   60     buf += *i;
   61     if (*l >= n) {
   62         *l = (*l) - n;
   63         val <<= *l;
   64         *buf = *buf | (val & 0xff);
   65         if (*l == 0) {
   66             *l = 8;
   67             (*i)++;
   68             *(++buf) = 0;
   69         }
   70     } else {
   71         (*i)++;
   72         *l = 8 - n + (*l);
   73         val <<= *l;
   74         *buf = *buf | ((val >> 8) & 0xff);
   75         *(++buf) = val & 0xff;
   76     }
   77 }
   78 
   79 /* Inserts 9 to 16 bits into the output buffer. */
   80 static void __inline
   81 putbits16(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
   82 {
   83     buf += *i;
   84     if (*l >= n - 8) {
   85         (*i)++;
   86         *l = 8 - n + (*l);
   87         val <<= *l;
   88         *buf = *buf | ((val >> 8) & 0xff);
   89         *(++buf) = val & 0xff;
   90         if (*l == 0) {
   91             *l = 8;
   92             (*i)++;
   93             *(++buf) = 0;
   94         }
   95     } else {
   96         (*i)++; (*i)++;
   97         *l = 16 - n + (*l);
   98         val <<= *l;
   99         *buf = *buf | ((val >> 16) & 0xff);
  100         *(++buf) = (val >> 8) & 0xff;
  101         *(++buf) = val & 0xff;
  102     }
  103 }
  104 
  105 /* Inserts 17 to 24 bits into the output buffer. */
  106 static void __inline
  107 putbits24(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l)
  108 {
  109     buf += *i;
  110     if (*l >= n - 16) {
  111         (*i)++; (*i)++;
  112         *l = 16 - n + (*l);
  113         val <<= *l;
  114         *buf = *buf | ((val >> 16) & 0xff);
  115         *(++buf) = (val >> 8) & 0xff;
  116         *(++buf) = val & 0xff;
  117         if (*l == 0) {
  118             *l = 8;
  119             (*i)++;
  120             *(++buf) = 0;
  121         }
  122     } else {
  123         (*i)++; (*i)++; (*i)++;
  124         *l = 24 - n + (*l);
  125         val <<= *l;
  126         *buf = *buf | ((val >> 24) & 0xff);
  127         *(++buf) = (val >> 16) & 0xff;
  128         *(++buf) = (val >> 8) & 0xff;
  129         *(++buf) = val & 0xff;
  130     }
  131 }
  132 
  133 size_t MPPC_SizeOfCompressionHistory(void)
  134 {
  135     return (sizeof(struct MPPC_comp_state));
  136 }
  137 
  138 void MPPC_InitCompressionHistory(char *history)
  139 {
  140     struct MPPC_comp_state      *state = (struct MPPC_comp_state*)history;
  141 
  142     bzero(history, sizeof(struct MPPC_comp_state));
  143     state->histptr = MPPE_HIST_LEN;
  144 }
  145 
  146 int MPPC_Compress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags, int undef)
  147 {
  148     struct MPPC_comp_state      *state = (struct MPPC_comp_state*)history;
  149     uint32_t olen, off, len, idx, i, l;
  150     uint8_t *hist, *sbuf, *p, *q, *r, *s;    
  151     int rtn = MPPC_OK;
  152 
  153    /*
  154     * At this point, to avoid possible buffer overflow caused by packet
  155     * expansion during/after compression, we should make sure we have
  156     * space for the worst case.
  157 
  158     * Maximum MPPC packet expansion is 12.5%. This is the worst case when
  159     * all octets in the input buffer are >= 0x80 and we cannot find any
  160     * repeated tokens.
  161     */
  162     if (*dstCnt < (*srcCnt * 9 / 8 + 2)) {
  163         rtn &= ~MPPC_OK;
  164         return (rtn);
  165     }
  166 
  167     /* We can't compress more then MPPE_HIST_LEN bytes in a call. */
  168     if (*srcCnt > MPPE_HIST_LEN) {
  169         rtn &= ~MPPC_OK;
  170         return (rtn);
  171     }
  172 
  173     hist = state->hist + MPPE_HIST_LEN;
  174     /* check if there is enough room at the end of the history */
  175     if (state->histptr + *srcCnt >= 2*MPPE_HIST_LEN) {
  176         rtn |= MPPC_RESTART_HISTORY;
  177         state->histptr = MPPE_HIST_LEN;
  178         memcpy(state->hist, hist, MPPE_HIST_LEN);
  179     }
  180     /* Add packet to the history. */
  181     sbuf = state->hist + state->histptr;
  182     memcpy(sbuf, *src, *srcCnt);
  183     state->histptr += *srcCnt;
  184 
  185     /* compress data */
  186     r = sbuf + *srcCnt;
  187     **dst = olen = i = 0;
  188     l = 8;
  189     while (i < *srcCnt - 2) {
  190         s = q = sbuf + i;
  191 
  192         /* Prognose matching position using hash function. */
  193         idx = HASH(s);
  194         p = hist + state->hash[idx];
  195         state->hash[idx] = (uint16_t) (s - hist);
  196         if (p > s)      /* It was before MPPC_RESTART_HISTORY. */
  197             p -= MPPE_HIST_LEN; /* Try previous history buffer. */
  198         off = s - p;
  199 
  200         /* Check our prognosis. */
  201         if (off > MPPE_HIST_LEN - 1 || off < 1 || *p++ != *s++ ||
  202             *p++ != *s++ || *p++ != *s++) {
  203             /* No match found; encode literal byte. */
  204             if ((*src)[i] < 0x80) {             /* literal byte < 0x80 */
  205                 putbits8(*dst, (uint32_t) (*src)[i], 8, &olen, &l);
  206             } else {                            /* literal byte >= 0x80 */
  207                 putbits16(*dst, (uint32_t) (0x100|((*src)[i]&0x7f)), 9,
  208                     &olen, &l);
  209             }
  210             ++i;
  211             continue;
  212         }
  213 
  214         /* Find length of the matching fragment */
  215 #if defined(__amd64__) || defined(__i386__)
  216         /* Optimization for CPUs without strict data aligning requirements */
  217         while ((*((uint32_t*)p) == *((uint32_t*)s)) && (s < (r - 3))) {
  218             p+=4;
  219             s+=4;
  220         }
  221 #endif
  222         while((*p++ == *s++) && (s <= r));
  223         len = s - q - 1;
  224         i += len;
  225 
  226         /* At least 3 character match found; code data. */
  227         /* Encode offset. */
  228         if (off < 64) {                 /* 10-bit offset; 0 <= offset < 64 */
  229             putbits16(*dst, 0x3c0|off, 10, &olen, &l);
  230         } else if (off < 320) {         /* 12-bit offset; 64 <= offset < 320 */
  231             putbits16(*dst, 0xe00|(off-64), 12, &olen, &l);
  232         } else if (off < 8192) {        /* 16-bit offset; 320 <= offset < 8192 */
  233             putbits16(*dst, 0xc000|(off-320), 16, &olen, &l);
  234         } else {                /* NOTREACHED */
  235             __unreachable();
  236             rtn &= ~MPPC_OK;
  237             return (rtn);
  238         }
  239 
  240         /* Encode length of match. */
  241         if (len < 4) {                  /* length = 3 */
  242             putbits8(*dst, 0, 1, &olen, &l);
  243         } else if (len < 8) {           /* 4 <= length < 8 */
  244             putbits8(*dst, 0x08|(len&0x03), 4, &olen, &l);
  245         } else if (len < 16) {          /* 8 <= length < 16 */
  246             putbits8(*dst, 0x30|(len&0x07), 6, &olen, &l);
  247         } else if (len < 32) {          /* 16 <= length < 32 */
  248             putbits8(*dst, 0xe0|(len&0x0f), 8, &olen, &l);
  249         } else if (len < 64) {          /* 32 <= length < 64 */
  250             putbits16(*dst, 0x3c0|(len&0x1f), 10, &olen, &l);
  251         } else if (len < 128) {         /* 64 <= length < 128 */
  252             putbits16(*dst, 0xf80|(len&0x3f), 12, &olen, &l);
  253         } else if (len < 256) {         /* 128 <= length < 256 */
  254             putbits16(*dst, 0x3f00|(len&0x7f), 14, &olen, &l);
  255         } else if (len < 512) {         /* 256 <= length < 512 */
  256             putbits16(*dst, 0xfe00|(len&0xff), 16, &olen, &l);
  257         } else if (len < 1024) {        /* 512 <= length < 1024 */
  258             putbits24(*dst, 0x3fc00|(len&0x1ff), 18, &olen, &l);
  259         } else if (len < 2048) {        /* 1024 <= length < 2048 */
  260             putbits24(*dst, 0xff800|(len&0x3ff), 20, &olen, &l);
  261         } else if (len < 4096) {        /* 2048 <= length < 4096 */
  262             putbits24(*dst, 0x3ff000|(len&0x7ff), 22, &olen, &l);
  263         } else if (len < 8192) {        /* 4096 <= length < 8192 */
  264             putbits24(*dst, 0xffe000|(len&0xfff), 24, &olen, &l);
  265         } else {        /* NOTREACHED */
  266             rtn &= ~MPPC_OK;
  267             return (rtn);
  268         }
  269     }
  270 
  271     /* Add remaining octets to the output. */
  272     while(*srcCnt - i > 0) {
  273         if ((*src)[i] < 0x80) { /* literal byte < 0x80 */
  274             putbits8(*dst, (uint32_t) (*src)[i++], 8, &olen, &l);
  275         } else {                /* literal byte >= 0x80 */
  276             putbits16(*dst, (uint32_t) (0x100|((*src)[i++]&0x7f)), 9, &olen,
  277                 &l);
  278         }
  279     }
  280 
  281     /* Reset unused bits of the last output octet. */
  282     if ((l != 0) && (l != 8)) {
  283         putbits8(*dst, 0, l, &olen, &l);
  284     }
  285 
  286     /* If result is bigger then original, set flag and flush history. */
  287     if ((*srcCnt < olen) || ((flags & MPPC_SAVE_HISTORY) == 0)) {
  288         if (*srcCnt < olen)
  289             rtn |= MPPC_EXPANDED;
  290         bzero(history, sizeof(struct MPPC_comp_state));
  291         state->histptr = MPPE_HIST_LEN;
  292     }
  293 
  294     *src += *srcCnt;
  295     *srcCnt = 0;
  296     *dst += olen;
  297     *dstCnt -= olen;
  298 
  299     return (rtn);
  300 }

Cache object: 3784b987d9bded489896232444eb900a


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