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/mppcd.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$
   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 struct MPPC_decomp_state {
   49     uint8_t     hist[2*MPPE_HIST_LEN];
   50     uint16_t    histptr;
   51 };
   52 
   53 static uint32_t __inline
   54 getbits(const uint8_t *buf, const uint32_t n, uint32_t *i, uint32_t *l)
   55 {
   56     static const uint32_t m[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
   57     uint32_t res, ol;
   58 
   59     ol = *l;
   60     if (*l >= n) {
   61         *l = (*l) - n;
   62         res = (buf[*i] & m[ol]) >> (*l);
   63         if (*l == 0) {
   64             *l = 8;
   65             (*i)++;
   66         }
   67     } else {
   68         *l = 8 - n + (*l);
   69         res = (buf[(*i)++] & m[ol]) << 8;
   70         res = (res | buf[*i]) >> (*l);
   71     }
   72 
   73     return (res);
   74 }
   75 
   76 static uint32_t __inline
   77 getbyte(const uint8_t *buf, const uint32_t i, const uint32_t l)
   78 {
   79     if (l == 8) {
   80         return (buf[i]);
   81     } else {
   82         return ((((buf[i] << 8) | buf[i+1]) >> l) & 0xff);
   83     }
   84 }
   85 
   86 static void __inline
   87 lamecopy(uint8_t *dst, uint8_t *src, uint32_t len)
   88 {
   89     while (len--)
   90         *dst++ = *src++;
   91 }
   92 
   93 size_t MPPC_SizeOfDecompressionHistory(void)
   94 {
   95     return (sizeof(struct MPPC_decomp_state));
   96 }
   97 
   98 void MPPC_InitDecompressionHistory(char *history)
   99 {
  100     struct MPPC_decomp_state      *state = (struct MPPC_decomp_state*)history;
  101 
  102     bzero(history, sizeof(struct MPPC_decomp_state));
  103     state->histptr = MPPE_HIST_LEN;
  104 }
  105 
  106 int MPPC_Decompress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags)
  107 {
  108     struct MPPC_decomp_state      *state = (struct MPPC_decomp_state*)history;
  109     uint32_t olen, off, len, bits, val, sig, i, l;
  110     uint8_t *hist, *s;
  111     u_char *isrc = *src;
  112     int rtn = MPPC_OK;
  113 
  114     if ((flags & MPPC_RESTART_HISTORY) != 0) {
  115         memcpy(state->hist, state->hist + MPPE_HIST_LEN, MPPE_HIST_LEN);
  116         state->histptr = MPPE_HIST_LEN;
  117     }
  118 
  119     hist = state->hist + state->histptr;
  120     olen = len = i = 0;
  121     l = 8;
  122     bits = *srcCnt * 8;
  123     while (bits >= 8) {
  124         val = getbyte(isrc, i++, l);
  125         if (val < 0x80) {               /* literal byte < 0x80 */
  126             if (state->histptr < 2*MPPE_HIST_LEN) {
  127                 /* Copy uncompressed byte to the history. */
  128                 (state->hist)[(state->histptr)++] = (uint8_t) val;
  129             } else {
  130                 /* Buffer overflow; drop packet. */
  131                 rtn &= ~MPPC_OK;
  132                 return rtn;
  133             }
  134             olen++;
  135             bits -= 8;
  136             continue;
  137         }
  138 
  139         sig = val & 0xc0;
  140         if (sig == 0x80) {              /* literal byte >= 0x80 */
  141             if (state->histptr < 2*MPPE_HIST_LEN) {
  142                 /* Copy uncompressed byte to the history. */
  143                 (state->hist)[(state->histptr)++] = 
  144                     (uint8_t) (0x80|((val&0x3f)<<1)|getbits(isrc, 1 , &i ,&l));
  145             } else {
  146                 /* buffer overflow; drop packet */
  147                 rtn &= ~MPPC_OK;
  148                 return (rtn);
  149             }
  150             olen++;
  151             bits -= 9;
  152             continue;
  153         }
  154 
  155         /* Not a literal byte so it must be an (offset,length) pair */
  156         /* decode offset */
  157         sig = val & 0xf0;
  158         if (sig == 0xf0) {              /* 10-bit offset; 0 <= offset < 64 */
  159             off = (((val&0x0f)<<2)|getbits(isrc, 2 , &i ,&l));
  160             bits -= 10;
  161         } else {
  162             if (sig == 0xe0) {          /* 12-bit offset; 64 <= offset < 320 */
  163                 off = ((((val&0x0f)<<4)|getbits(isrc, 4 , &i ,&l))+64);
  164                 bits -= 12;
  165             } else {
  166                 if ((sig&0xe0) == 0xc0) {/* 16-bit offset; 320 <= offset < 8192 */
  167                     off = ((((val&0x1f)<<8)|getbyte(isrc, i++, l))+320);
  168                     bits -= 16;
  169                     if (off > MPPE_HIST_LEN - 1) {
  170                         rtn &= ~MPPC_OK;
  171                         return (rtn);
  172                     }
  173                 } else {                /* This shouldn't happen. */
  174                     rtn &= ~MPPC_OK;
  175                     return (rtn);
  176                 }
  177             }
  178         }
  179         /* Decode length of match. */
  180         val = getbyte(isrc, i, l);
  181         if ((val & 0x80) == 0x00) {                     /* len = 3 */
  182             len = 3;
  183             bits--;
  184             getbits(isrc, 1 , &i ,&l);
  185         } else if ((val & 0xc0) == 0x80) {              /* 4 <= len < 8 */
  186             len = 0x04 | ((val>>4) & 0x03);
  187             bits -= 4;
  188             getbits(isrc, 4 , &i ,&l);
  189         } else if ((val & 0xe0) == 0xc0) {              /* 8 <= len < 16 */
  190             len = 0x08 | ((val>>2) & 0x07);
  191             bits -= 6;
  192             getbits(isrc, 6 , &i ,&l);
  193         } else if ((val & 0xf0) == 0xe0) {              /* 16 <= len < 32 */
  194             len = 0x10 | (val & 0x0f);
  195             bits -= 8;
  196             i++;
  197         } else {
  198             bits -= 8;
  199             val = (val << 8) | getbyte(isrc, ++i, l);
  200             if ((val & 0xf800) == 0xf000) {             /* 32 <= len < 64 */
  201                 len = 0x0020 | ((val >> 6) & 0x001f);
  202                 bits -= 2;
  203                 getbits(isrc, 2 , &i ,&l);
  204             } else if ((val & 0xfc00) == 0xf800) {      /* 64 <= len < 128 */
  205                 len = 0x0040 | ((val >> 4) & 0x003f);
  206                 bits -= 4;
  207                 getbits(isrc, 4 , &i ,&l);
  208             } else if ((val & 0xfe00) == 0xfc00) {      /* 128 <= len < 256 */
  209                 len = 0x0080 | ((val >> 2) & 0x007f);
  210                 bits -= 6;
  211                 getbits(isrc, 6 , &i ,&l);
  212             } else if ((val & 0xff00) == 0xfe00) {      /* 256 <= len < 512 */
  213                 len = 0x0100 | (val & 0x00ff);
  214                 bits -= 8;
  215                 i++;
  216             } else {
  217                 bits -= 8;
  218                 val = (val << 8) | getbyte(isrc, ++i, l);
  219                 if ((val & 0xff8000) == 0xff0000) {     /* 512 <= len < 1024 */
  220                     len = 0x000200 | ((val >> 6) & 0x0001ff);
  221                     bits -= 2;
  222                     getbits(isrc, 2 , &i ,&l);
  223                 } else if ((val & 0xffc000) == 0xff8000) {/* 1024 <= len < 2048 */
  224                     len = 0x000400 | ((val >> 4) & 0x0003ff);
  225                     bits -= 4;
  226                     getbits(isrc, 4 , &i ,&l);
  227                 } else if ((val & 0xffe000) == 0xffc000) {/* 2048 <= len < 4096 */
  228                     len = 0x000800 | ((val >> 2) & 0x0007ff);
  229                     bits -= 6;
  230                     getbits(isrc, 6 , &i ,&l);
  231                 } else if ((val & 0xfff000) == 0xffe000) {/* 4096 <= len < 8192 */
  232                     len = 0x001000 | (val & 0x000fff);
  233                     bits -= 8;
  234                     i++;
  235                 } else {                                /* NOTREACHED */
  236                     rtn &= ~MPPC_OK;
  237                     return (rtn);
  238                 }
  239             }
  240         }
  241 
  242         s = state->hist + state->histptr;
  243         state->histptr += len;
  244         olen += len;
  245         if (state->histptr < 2*MPPE_HIST_LEN) {
  246             /* Copy uncompressed bytes to the history. */
  247 
  248             /*
  249              * In some cases len may be greater than off. It means that memory
  250              * areas pointed by s and s-off overlap. To decode that strange case
  251              * data should be copied exactly by address increasing to make
  252              * some data repeated.
  253              */
  254             lamecopy(s, s - off, len);
  255         } else {
  256             /* Buffer overflow; drop packet. */
  257             rtn &= ~MPPC_OK;
  258             return (rtn);
  259         }
  260     }
  261 
  262     /* Do PFC decompression. */
  263     len = olen;
  264     if ((hist[0] & 0x01) != 0) {
  265         (*dst)[0] = 0;
  266         (*dst)++;
  267         len++;
  268     }
  269 
  270     if (len <= *dstCnt) {
  271         /* Copy uncompressed packet to the output buffer. */
  272         memcpy(*dst, hist, olen);
  273     } else {
  274         /* Buffer overflow; drop packet. */
  275         rtn |= MPPC_DEST_EXHAUSTED;
  276     }
  277 
  278     *src += *srcCnt;
  279     *srcCnt = 0;
  280     *dst += len;
  281     *dstCnt -= len;
  282 
  283     return (rtn);
  284 }

Cache object: 389e0e158b31480c4b24a1049b9d3c9c


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