Index: head/sys/net/mppcc.c =================================================================== --- head/sys/net/mppcc.c (revision 302475) +++ head/sys/net/mppcc.c (revision 302476) @@ -1,299 +1,300 @@ /*- * Copyright (c) 2002-2004 Jan Dubiec * Copyright (c) 2007 Alexander Motin * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice unmodified, this list of conditions, and the following * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ /* * MPPC decompression library. * Version 1.0 * * Note that Hi/Fn (later acquired by Exar Corporation) held US patents * on some implementation-critical aspects of MPPC compression. * These patents lapsed due to non-payment of fees in 2007 and by 2015 * expired altogether. */ #include #include #include #define MPPE_HIST_LEN 8192 #define HASH(x) (((40543*(((((x)[0]<<4)^(x)[1])<<4)^(x)[2]))>>4) & 0x1fff) struct MPPC_comp_state { uint8_t hist[2*MPPE_HIST_LEN]; uint16_t histptr; uint16_t hash[MPPE_HIST_LEN]; }; /* Inserts 1 to 8 bits into the output buffer. */ static void __inline putbits8(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) { buf += *i; if (*l >= n) { *l = (*l) - n; val <<= *l; *buf = *buf | (val & 0xff); if (*l == 0) { *l = 8; (*i)++; *(++buf) = 0; } } else { (*i)++; *l = 8 - n + (*l); val <<= *l; *buf = *buf | ((val >> 8) & 0xff); *(++buf) = val & 0xff; } } /* Inserts 9 to 16 bits into the output buffer. */ static void __inline putbits16(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) { buf += *i; if (*l >= n - 8) { (*i)++; *l = 8 - n + (*l); val <<= *l; *buf = *buf | ((val >> 8) & 0xff); *(++buf) = val & 0xff; if (*l == 0) { *l = 8; (*i)++; *(++buf) = 0; } } else { (*i)++; (*i)++; *l = 16 - n + (*l); val <<= *l; *buf = *buf | ((val >> 16) & 0xff); *(++buf) = (val >> 8) & 0xff; *(++buf) = val & 0xff; } } /* Inserts 17 to 24 bits into the output buffer. */ static void __inline putbits24(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) { buf += *i; if (*l >= n - 16) { (*i)++; (*i)++; *l = 16 - n + (*l); val <<= *l; *buf = *buf | ((val >> 16) & 0xff); *(++buf) = (val >> 8) & 0xff; *(++buf) = val & 0xff; if (*l == 0) { *l = 8; (*i)++; *(++buf) = 0; } } else { (*i)++; (*i)++; (*i)++; *l = 24 - n + (*l); val <<= *l; *buf = *buf | ((val >> 24) & 0xff); *(++buf) = (val >> 16) & 0xff; *(++buf) = (val >> 8) & 0xff; *(++buf) = val & 0xff; } } size_t MPPC_SizeOfCompressionHistory(void) { return (sizeof(struct MPPC_comp_state)); } void MPPC_InitCompressionHistory(char *history) { struct MPPC_comp_state *state = (struct MPPC_comp_state*)history; bzero(history, sizeof(struct MPPC_comp_state)); state->histptr = MPPE_HIST_LEN; } int MPPC_Compress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags, int undef) { struct MPPC_comp_state *state = (struct MPPC_comp_state*)history; uint32_t olen, off, len, idx, i, l; uint8_t *hist, *sbuf, *p, *q, *r, *s; int rtn = MPPC_OK; /* * At this point, to avoid possible buffer overflow caused by packet * expansion during/after compression, we should make sure we have * space for the worst case. * Maximum MPPC packet expansion is 12.5%. This is the worst case when * all octets in the input buffer are >= 0x80 and we cannot find any * repeated tokens. */ if (*dstCnt < (*srcCnt * 9 / 8 + 2)) { rtn &= ~MPPC_OK; return (rtn); } /* We can't compress more then MPPE_HIST_LEN bytes in a call. */ if (*srcCnt > MPPE_HIST_LEN) { rtn &= ~MPPC_OK; return (rtn); } hist = state->hist + MPPE_HIST_LEN; /* check if there is enough room at the end of the history */ if (state->histptr + *srcCnt >= 2*MPPE_HIST_LEN) { rtn |= MPPC_RESTART_HISTORY; state->histptr = MPPE_HIST_LEN; memcpy(state->hist, hist, MPPE_HIST_LEN); } /* Add packet to the history. */ sbuf = state->hist + state->histptr; memcpy(sbuf, *src, *srcCnt); state->histptr += *srcCnt; /* compress data */ r = sbuf + *srcCnt; **dst = olen = i = 0; l = 8; while (i < *srcCnt - 2) { s = q = sbuf + i; /* Prognose matching position using hash function. */ idx = HASH(s); p = hist + state->hash[idx]; state->hash[idx] = (uint16_t) (s - hist); if (p > s) /* It was before MPPC_RESTART_HISTORY. */ p -= MPPE_HIST_LEN; /* Try previous history buffer. */ off = s - p; /* Check our prognosis. */ if (off > MPPE_HIST_LEN - 1 || off < 1 || *p++ != *s++ || *p++ != *s++ || *p++ != *s++) { /* No match found; encode literal byte. */ if ((*src)[i] < 0x80) { /* literal byte < 0x80 */ putbits8(*dst, (uint32_t) (*src)[i], 8, &olen, &l); } else { /* literal byte >= 0x80 */ putbits16(*dst, (uint32_t) (0x100|((*src)[i]&0x7f)), 9, &olen, &l); } ++i; continue; } /* Find length of the matching fragment */ #if defined(__amd64__) || defined(__i386__) /* Optimization for CPUs without strict data aligning requirements */ while ((*((uint32_t*)p) == *((uint32_t*)s)) && (s < (r - 3))) { p+=4; s+=4; } #endif while((*p++ == *s++) && (s <= r)); len = s - q - 1; i += len; /* At least 3 character match found; code data. */ /* Encode offset. */ if (off < 64) { /* 10-bit offset; 0 <= offset < 64 */ putbits16(*dst, 0x3c0|off, 10, &olen, &l); } else if (off < 320) { /* 12-bit offset; 64 <= offset < 320 */ putbits16(*dst, 0xe00|(off-64), 12, &olen, &l); } else if (off < 8192) { /* 16-bit offset; 320 <= offset < 8192 */ putbits16(*dst, 0xc000|(off-320), 16, &olen, &l); } else { /* NOTREACHED */ + __unreachable(); rtn &= ~MPPC_OK; - return rtn; + return (rtn); } /* Encode length of match. */ if (len < 4) { /* length = 3 */ putbits8(*dst, 0, 1, &olen, &l); } else if (len < 8) { /* 4 <= length < 8 */ putbits8(*dst, 0x08|(len&0x03), 4, &olen, &l); } else if (len < 16) { /* 8 <= length < 16 */ putbits8(*dst, 0x30|(len&0x07), 6, &olen, &l); } else if (len < 32) { /* 16 <= length < 32 */ putbits8(*dst, 0xe0|(len&0x0f), 8, &olen, &l); } else if (len < 64) { /* 32 <= length < 64 */ putbits16(*dst, 0x3c0|(len&0x1f), 10, &olen, &l); } else if (len < 128) { /* 64 <= length < 128 */ putbits16(*dst, 0xf80|(len&0x3f), 12, &olen, &l); } else if (len < 256) { /* 128 <= length < 256 */ putbits16(*dst, 0x3f00|(len&0x7f), 14, &olen, &l); } else if (len < 512) { /* 256 <= length < 512 */ putbits16(*dst, 0xfe00|(len&0xff), 16, &olen, &l); } else if (len < 1024) { /* 512 <= length < 1024 */ putbits24(*dst, 0x3fc00|(len&0x1ff), 18, &olen, &l); } else if (len < 2048) { /* 1024 <= length < 2048 */ putbits24(*dst, 0xff800|(len&0x3ff), 20, &olen, &l); } else if (len < 4096) { /* 2048 <= length < 4096 */ putbits24(*dst, 0x3ff000|(len&0x7ff), 22, &olen, &l); } else if (len < 8192) { /* 4096 <= length < 8192 */ putbits24(*dst, 0xffe000|(len&0xfff), 24, &olen, &l); } else { /* NOTREACHED */ rtn &= ~MPPC_OK; return (rtn); } } /* Add remaining octets to the output. */ while(*srcCnt - i > 0) { if ((*src)[i] < 0x80) { /* literal byte < 0x80 */ putbits8(*dst, (uint32_t) (*src)[i++], 8, &olen, &l); } else { /* literal byte >= 0x80 */ putbits16(*dst, (uint32_t) (0x100|((*src)[i++]&0x7f)), 9, &olen, &l); } } /* Reset unused bits of the last output octet. */ if ((l != 0) && (l != 8)) { putbits8(*dst, 0, l, &olen, &l); } /* If result is bigger then original, set flag and flush history. */ if ((*srcCnt < olen) || ((flags & MPPC_SAVE_HISTORY) == 0)) { if (*srcCnt < olen) rtn |= MPPC_EXPANDED; bzero(history, sizeof(struct MPPC_comp_state)); state->histptr = MPPE_HIST_LEN; } *src += *srcCnt; *srcCnt = 0; *dst += olen; *dstCnt -= olen; return (rtn); } Index: head/sys/net/mppcd.c =================================================================== --- head/sys/net/mppcd.c (revision 302475) +++ head/sys/net/mppcd.c (revision 302476) @@ -1,284 +1,284 @@ /*- * Copyright (c) 2002-2004 Jan Dubiec * Copyright (c) 2007 Alexander Motin * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice unmodified, this list of conditions, and the following * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ /* * MPPC decompression library. * Version 1.0 * * Note that Hi/Fn (later acquired by Exar Corporation) held US patents * on some implementation-critical aspects of MPPC compression. * These patents lapsed due to non-payment of fees in 2007 and by 2015 * expired altogether. */ #include #include #include #define MPPE_HIST_LEN 8192 struct MPPC_decomp_state { uint8_t hist[2*MPPE_HIST_LEN]; uint16_t histptr; }; static uint32_t __inline getbits(const uint8_t *buf, const uint32_t n, uint32_t *i, uint32_t *l) { static const uint32_t m[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; uint32_t res, ol; ol = *l; if (*l >= n) { *l = (*l) - n; res = (buf[*i] & m[ol]) >> (*l); if (*l == 0) { *l = 8; (*i)++; } } else { *l = 8 - n + (*l); res = (buf[(*i)++] & m[ol]) << 8; res = (res | buf[*i]) >> (*l); } return (res); } static uint32_t __inline getbyte(const uint8_t *buf, const uint32_t i, const uint32_t l) { if (l == 8) { return (buf[i]); } else { return ((((buf[i] << 8) | buf[i+1]) >> l) & 0xff); } } static void __inline lamecopy(uint8_t *dst, uint8_t *src, uint32_t len) { while (len--) *dst++ = *src++; } size_t MPPC_SizeOfDecompressionHistory(void) { return (sizeof(struct MPPC_decomp_state)); } void MPPC_InitDecompressionHistory(char *history) { struct MPPC_decomp_state *state = (struct MPPC_decomp_state*)history; bzero(history, sizeof(struct MPPC_decomp_state)); state->histptr = MPPE_HIST_LEN; } int MPPC_Decompress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags) { struct MPPC_decomp_state *state = (struct MPPC_decomp_state*)history; uint32_t olen, off, len, bits, val, sig, i, l; uint8_t *hist, *s; u_char *isrc = *src; int rtn = MPPC_OK; if ((flags & MPPC_RESTART_HISTORY) != 0) { memcpy(state->hist, state->hist + MPPE_HIST_LEN, MPPE_HIST_LEN); state->histptr = MPPE_HIST_LEN; } hist = state->hist + state->histptr; olen = len = i = 0; l = 8; bits = *srcCnt * 8; while (bits >= 8) { val = getbyte(isrc, i++, l); if (val < 0x80) { /* literal byte < 0x80 */ if (state->histptr < 2*MPPE_HIST_LEN) { /* Copy uncompressed byte to the history. */ (state->hist)[(state->histptr)++] = (uint8_t) val; } else { /* Buffer overflow; drop packet. */ rtn &= ~MPPC_OK; return rtn; } olen++; bits -= 8; continue; } sig = val & 0xc0; if (sig == 0x80) { /* literal byte >= 0x80 */ if (state->histptr < 2*MPPE_HIST_LEN) { /* Copy uncompressed byte to the history. */ (state->hist)[(state->histptr)++] = (uint8_t) (0x80|((val&0x3f)<<1)|getbits(isrc, 1 , &i ,&l)); } else { /* buffer overflow; drop packet */ rtn &= ~MPPC_OK; return (rtn); } olen++; bits -= 9; continue; } /* Not a literal byte so it must be an (offset,length) pair */ /* decode offset */ sig = val & 0xf0; if (sig == 0xf0) { /* 10-bit offset; 0 <= offset < 64 */ off = (((val&0x0f)<<2)|getbits(isrc, 2 , &i ,&l)); bits -= 10; } else { if (sig == 0xe0) { /* 12-bit offset; 64 <= offset < 320 */ off = ((((val&0x0f)<<4)|getbits(isrc, 4 , &i ,&l))+64); bits -= 12; } else { if ((sig&0xe0) == 0xc0) {/* 16-bit offset; 320 <= offset < 8192 */ off = ((((val&0x1f)<<8)|getbyte(isrc, i++, l))+320); bits -= 16; if (off > MPPE_HIST_LEN - 1) { rtn &= ~MPPC_OK; return (rtn); } - } else { /* NOTREACHED */ + } else { /* This shouldn't happen. */ rtn &= ~MPPC_OK; return (rtn); } } } /* Decode length of match. */ val = getbyte(isrc, i, l); if ((val & 0x80) == 0x00) { /* len = 3 */ len = 3; bits--; getbits(isrc, 1 , &i ,&l); } else if ((val & 0xc0) == 0x80) { /* 4 <= len < 8 */ len = 0x04 | ((val>>4) & 0x03); bits -= 4; getbits(isrc, 4 , &i ,&l); } else if ((val & 0xe0) == 0xc0) { /* 8 <= len < 16 */ len = 0x08 | ((val>>2) & 0x07); bits -= 6; getbits(isrc, 6 , &i ,&l); } else if ((val & 0xf0) == 0xe0) { /* 16 <= len < 32 */ len = 0x10 | (val & 0x0f); bits -= 8; i++; } else { bits -= 8; val = (val << 8) | getbyte(isrc, ++i, l); if ((val & 0xf800) == 0xf000) { /* 32 <= len < 64 */ len = 0x0020 | ((val >> 6) & 0x001f); bits -= 2; getbits(isrc, 2 , &i ,&l); } else if ((val & 0xfc00) == 0xf800) { /* 64 <= len < 128 */ len = 0x0040 | ((val >> 4) & 0x003f); bits -= 4; getbits(isrc, 4 , &i ,&l); } else if ((val & 0xfe00) == 0xfc00) { /* 128 <= len < 256 */ len = 0x0080 | ((val >> 2) & 0x007f); bits -= 6; getbits(isrc, 6 , &i ,&l); } else if ((val & 0xff00) == 0xfe00) { /* 256 <= len < 512 */ len = 0x0100 | (val & 0x00ff); bits -= 8; i++; } else { bits -= 8; val = (val << 8) | getbyte(isrc, ++i, l); if ((val & 0xff8000) == 0xff0000) { /* 512 <= len < 1024 */ len = 0x000200 | ((val >> 6) & 0x0001ff); bits -= 2; getbits(isrc, 2 , &i ,&l); } else if ((val & 0xffc000) == 0xff8000) {/* 1024 <= len < 2048 */ len = 0x000400 | ((val >> 4) & 0x0003ff); bits -= 4; getbits(isrc, 4 , &i ,&l); } else if ((val & 0xffe000) == 0xffc000) {/* 2048 <= len < 4096 */ len = 0x000800 | ((val >> 2) & 0x0007ff); bits -= 6; getbits(isrc, 6 , &i ,&l); } else if ((val & 0xfff000) == 0xffe000) {/* 4096 <= len < 8192 */ len = 0x001000 | (val & 0x000fff); bits -= 8; i++; } else { /* NOTREACHED */ rtn &= ~MPPC_OK; return (rtn); } } } s = state->hist + state->histptr; state->histptr += len; olen += len; if (state->histptr < 2*MPPE_HIST_LEN) { /* Copy uncompressed bytes to the history. */ /* * In some cases len may be greater than off. It means that memory * areas pointed by s and s-off overlap. To decode that strange case * data should be copied exactly by address increasing to make * some data repeated. */ lamecopy(s, s - off, len); } else { /* Buffer overflow; drop packet. */ rtn &= ~MPPC_OK; return (rtn); } } /* Do PFC decompression. */ len = olen; if ((hist[0] & 0x01) != 0) { (*dst)[0] = 0; (*dst)++; len++; } if (len <= *dstCnt) { /* Copy uncompressed packet to the output buffer. */ memcpy(*dst, hist, olen); } else { /* Buffer overflow; drop packet. */ rtn |= MPPC_DEST_EXHAUSTED; } *src += *srcCnt; *srcCnt = 0; *dst += len; *dstCnt -= len; return (rtn); }