sys/net/mppcd.c

   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 }