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 } 285