1301549Spfg/*- 2301549Spfg * Copyright (c) 2002-2004 Jan Dubiec <jdx@slackware.pl> 3301549Spfg * Copyright (c) 2007 Alexander Motin <mav@freebsd.org> 4301549Spfg * All rights reserved. 5301549Spfg * 6301549Spfg * Redistribution and use in source and binary forms, with or without 7301549Spfg * modification, are permitted provided that the following conditions 8301549Spfg * are met: 9301549Spfg * 1. Redistributions of source code must retain the above copyright 10301549Spfg * notice unmodified, this list of conditions, and the following 11301549Spfg * disclaimer. 12301549Spfg * 2. Redistributions in binary form must reproduce the above copyright 13301549Spfg * notice, this list of conditions and the following disclaimer in the 14301549Spfg * documentation and/or other materials provided with the distribution. 15301549Spfg * 16301549Spfg * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17301549Spfg * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18301549Spfg * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19301549Spfg * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20301549Spfg * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21301549Spfg * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22301549Spfg * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23301549Spfg * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24301549Spfg * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25301549Spfg * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26301549Spfg * SUCH DAMAGE. 27301549Spfg * 28301549Spfg * $FreeBSD$ 29301549Spfg */ 30301549Spfg 31301549Spfg/* 32301549Spfg * MPPC decompression library. 33301549Spfg * Version 1.0 34301549Spfg * 35301549Spfg * Note that Hi/Fn (later acquired by Exar Corporation) held US patents 36301549Spfg * on some implementation-critical aspects of MPPC compression. 37301549Spfg * These patents lapsed due to non-payment of fees in 2007 and by 2015 38301549Spfg * expired altogether. 39301549Spfg */ 40301549Spfg 41301549Spfg#include <sys/param.h> 42301549Spfg#include <sys/systm.h> 43301549Spfg 44301549Spfg#include <net/mppc.h> 45301549Spfg 46301549Spfg#define MPPE_HIST_LEN 8192 47301549Spfg 48301549Spfg#define HASH(x) (((40543*(((((x)[0]<<4)^(x)[1])<<4)^(x)[2]))>>4) & 0x1fff) 49301549Spfg 50301549Spfgstruct MPPC_comp_state { 51301549Spfg uint8_t hist[2*MPPE_HIST_LEN]; 52301549Spfg uint16_t histptr; 53301549Spfg uint16_t hash[MPPE_HIST_LEN]; 54301549Spfg}; 55301549Spfg 56301549Spfg/* Inserts 1 to 8 bits into the output buffer. */ 57301549Spfgstatic void __inline 58301549Spfgputbits8(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) 59301549Spfg{ 60301549Spfg buf += *i; 61301549Spfg if (*l >= n) { 62301549Spfg *l = (*l) - n; 63301549Spfg val <<= *l; 64301549Spfg *buf = *buf | (val & 0xff); 65301549Spfg if (*l == 0) { 66301549Spfg *l = 8; 67301549Spfg (*i)++; 68301549Spfg *(++buf) = 0; 69301549Spfg } 70301549Spfg } else { 71301549Spfg (*i)++; 72301549Spfg *l = 8 - n + (*l); 73301549Spfg val <<= *l; 74301549Spfg *buf = *buf | ((val >> 8) & 0xff); 75301549Spfg *(++buf) = val & 0xff; 76301549Spfg } 77301549Spfg} 78301549Spfg 79301549Spfg/* Inserts 9 to 16 bits into the output buffer. */ 80301549Spfgstatic void __inline 81301549Spfgputbits16(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) 82301549Spfg{ 83301549Spfg buf += *i; 84301549Spfg if (*l >= n - 8) { 85301549Spfg (*i)++; 86301549Spfg *l = 8 - n + (*l); 87301549Spfg val <<= *l; 88301549Spfg *buf = *buf | ((val >> 8) & 0xff); 89301549Spfg *(++buf) = val & 0xff; 90301549Spfg if (*l == 0) { 91301549Spfg *l = 8; 92301549Spfg (*i)++; 93301549Spfg *(++buf) = 0; 94301549Spfg } 95301549Spfg } else { 96301549Spfg (*i)++; (*i)++; 97301549Spfg *l = 16 - n + (*l); 98301549Spfg val <<= *l; 99301549Spfg *buf = *buf | ((val >> 16) & 0xff); 100301549Spfg *(++buf) = (val >> 8) & 0xff; 101301549Spfg *(++buf) = val & 0xff; 102301549Spfg } 103301549Spfg} 104301549Spfg 105301549Spfg/* Inserts 17 to 24 bits into the output buffer. */ 106301549Spfgstatic void __inline 107301549Spfgputbits24(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) 108301549Spfg{ 109301549Spfg buf += *i; 110301549Spfg if (*l >= n - 16) { 111301549Spfg (*i)++; (*i)++; 112301549Spfg *l = 16 - n + (*l); 113301549Spfg val <<= *l; 114301549Spfg *buf = *buf | ((val >> 16) & 0xff); 115301549Spfg *(++buf) = (val >> 8) & 0xff; 116301549Spfg *(++buf) = val & 0xff; 117301549Spfg if (*l == 0) { 118301549Spfg *l = 8; 119301549Spfg (*i)++; 120301549Spfg *(++buf) = 0; 121301549Spfg } 122301549Spfg } else { 123301549Spfg (*i)++; (*i)++; (*i)++; 124301549Spfg *l = 24 - n + (*l); 125301549Spfg val <<= *l; 126301549Spfg *buf = *buf | ((val >> 24) & 0xff); 127301549Spfg *(++buf) = (val >> 16) & 0xff; 128301549Spfg *(++buf) = (val >> 8) & 0xff; 129301549Spfg *(++buf) = val & 0xff; 130301549Spfg } 131301549Spfg} 132301549Spfg 133301549Spfgsize_t MPPC_SizeOfCompressionHistory(void) 134301549Spfg{ 135301549Spfg return (sizeof(struct MPPC_comp_state)); 136301549Spfg} 137301549Spfg 138301549Spfgvoid MPPC_InitCompressionHistory(char *history) 139301549Spfg{ 140301549Spfg struct MPPC_comp_state *state = (struct MPPC_comp_state*)history; 141301549Spfg 142301549Spfg bzero(history, sizeof(struct MPPC_comp_state)); 143301549Spfg state->histptr = MPPE_HIST_LEN; 144301549Spfg} 145301549Spfg 146301549Spfgint MPPC_Compress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags, int undef) 147301549Spfg{ 148301549Spfg struct MPPC_comp_state *state = (struct MPPC_comp_state*)history; 149301549Spfg uint32_t olen, off, len, idx, i, l; 150301549Spfg uint8_t *hist, *sbuf, *p, *q, *r, *s; 151301549Spfg int rtn = MPPC_OK; 152301549Spfg 153301549Spfg /* 154301549Spfg * At this point, to avoid possible buffer overflow caused by packet 155301549Spfg * expansion during/after compression, we should make sure we have 156301549Spfg * space for the worst case. 157301549Spfg 158301549Spfg * Maximum MPPC packet expansion is 12.5%. This is the worst case when 159301549Spfg * all octets in the input buffer are >= 0x80 and we cannot find any 160301549Spfg * repeated tokens. 161301549Spfg */ 162301549Spfg if (*dstCnt < (*srcCnt * 9 / 8 + 2)) { 163301549Spfg rtn &= ~MPPC_OK; 164301549Spfg return (rtn); 165301549Spfg } 166301549Spfg 167301549Spfg /* We can't compress more then MPPE_HIST_LEN bytes in a call. */ 168301549Spfg if (*srcCnt > MPPE_HIST_LEN) { 169301549Spfg rtn &= ~MPPC_OK; 170301549Spfg return (rtn); 171301549Spfg } 172301549Spfg 173301549Spfg hist = state->hist + MPPE_HIST_LEN; 174301549Spfg /* check if there is enough room at the end of the history */ 175301549Spfg if (state->histptr + *srcCnt >= 2*MPPE_HIST_LEN) { 176301549Spfg rtn |= MPPC_RESTART_HISTORY; 177301549Spfg state->histptr = MPPE_HIST_LEN; 178301549Spfg memcpy(state->hist, hist, MPPE_HIST_LEN); 179301549Spfg } 180301549Spfg /* Add packet to the history. */ 181301549Spfg sbuf = state->hist + state->histptr; 182301549Spfg memcpy(sbuf, *src, *srcCnt); 183301549Spfg state->histptr += *srcCnt; 184301549Spfg 185301549Spfg /* compress data */ 186301549Spfg r = sbuf + *srcCnt; 187301549Spfg **dst = olen = i = 0; 188301549Spfg l = 8; 189301549Spfg while (i < *srcCnt - 2) { 190301549Spfg s = q = sbuf + i; 191301549Spfg 192301549Spfg /* Prognose matching position using hash function. */ 193301549Spfg idx = HASH(s); 194301549Spfg p = hist + state->hash[idx]; 195301549Spfg state->hash[idx] = (uint16_t) (s - hist); 196301549Spfg if (p > s) /* It was before MPPC_RESTART_HISTORY. */ 197301549Spfg p -= MPPE_HIST_LEN; /* Try previous history buffer. */ 198301549Spfg off = s - p; 199301549Spfg 200301549Spfg /* Check our prognosis. */ 201301549Spfg if (off > MPPE_HIST_LEN - 1 || off < 1 || *p++ != *s++ || 202301549Spfg *p++ != *s++ || *p++ != *s++) { 203301549Spfg /* No match found; encode literal byte. */ 204301549Spfg if ((*src)[i] < 0x80) { /* literal byte < 0x80 */ 205301549Spfg putbits8(*dst, (uint32_t) (*src)[i], 8, &olen, &l); 206301549Spfg } else { /* literal byte >= 0x80 */ 207301549Spfg putbits16(*dst, (uint32_t) (0x100|((*src)[i]&0x7f)), 9, 208301549Spfg &olen, &l); 209301549Spfg } 210301549Spfg ++i; 211301549Spfg continue; 212301549Spfg } 213301549Spfg 214301549Spfg /* Find length of the matching fragment */ 215301549Spfg#if defined(__amd64__) || defined(__i386__) 216301549Spfg /* Optimization for CPUs without strict data aligning requirements */ 217301549Spfg while ((*((uint32_t*)p) == *((uint32_t*)s)) && (s < (r - 3))) { 218301549Spfg p+=4; 219301549Spfg s+=4; 220301549Spfg } 221301549Spfg#endif 222301549Spfg while((*p++ == *s++) && (s <= r)); 223301549Spfg len = s - q - 1; 224301549Spfg i += len; 225301549Spfg 226301549Spfg /* At least 3 character match found; code data. */ 227301549Spfg /* Encode offset. */ 228301549Spfg if (off < 64) { /* 10-bit offset; 0 <= offset < 64 */ 229301549Spfg putbits16(*dst, 0x3c0|off, 10, &olen, &l); 230301549Spfg } else if (off < 320) { /* 12-bit offset; 64 <= offset < 320 */ 231301549Spfg putbits16(*dst, 0xe00|(off-64), 12, &olen, &l); 232301549Spfg } else if (off < 8192) { /* 16-bit offset; 320 <= offset < 8192 */ 233301549Spfg putbits16(*dst, 0xc000|(off-320), 16, &olen, &l); 234301549Spfg } else { /* NOTREACHED */ 235302773Spfg __unreachable(); 236301549Spfg rtn &= ~MPPC_OK; 237302773Spfg return (rtn); 238301549Spfg } 239301549Spfg 240301549Spfg /* Encode length of match. */ 241301549Spfg if (len < 4) { /* length = 3 */ 242301549Spfg putbits8(*dst, 0, 1, &olen, &l); 243301549Spfg } else if (len < 8) { /* 4 <= length < 8 */ 244301549Spfg putbits8(*dst, 0x08|(len&0x03), 4, &olen, &l); 245301549Spfg } else if (len < 16) { /* 8 <= length < 16 */ 246301549Spfg putbits8(*dst, 0x30|(len&0x07), 6, &olen, &l); 247301549Spfg } else if (len < 32) { /* 16 <= length < 32 */ 248301549Spfg putbits8(*dst, 0xe0|(len&0x0f), 8, &olen, &l); 249301549Spfg } else if (len < 64) { /* 32 <= length < 64 */ 250301549Spfg putbits16(*dst, 0x3c0|(len&0x1f), 10, &olen, &l); 251301549Spfg } else if (len < 128) { /* 64 <= length < 128 */ 252301549Spfg putbits16(*dst, 0xf80|(len&0x3f), 12, &olen, &l); 253301549Spfg } else if (len < 256) { /* 128 <= length < 256 */ 254301549Spfg putbits16(*dst, 0x3f00|(len&0x7f), 14, &olen, &l); 255301549Spfg } else if (len < 512) { /* 256 <= length < 512 */ 256301549Spfg putbits16(*dst, 0xfe00|(len&0xff), 16, &olen, &l); 257301549Spfg } else if (len < 1024) { /* 512 <= length < 1024 */ 258301549Spfg putbits24(*dst, 0x3fc00|(len&0x1ff), 18, &olen, &l); 259301549Spfg } else if (len < 2048) { /* 1024 <= length < 2048 */ 260301549Spfg putbits24(*dst, 0xff800|(len&0x3ff), 20, &olen, &l); 261301549Spfg } else if (len < 4096) { /* 2048 <= length < 4096 */ 262301549Spfg putbits24(*dst, 0x3ff000|(len&0x7ff), 22, &olen, &l); 263301549Spfg } else if (len < 8192) { /* 4096 <= length < 8192 */ 264301549Spfg putbits24(*dst, 0xffe000|(len&0xfff), 24, &olen, &l); 265301549Spfg } else { /* NOTREACHED */ 266301549Spfg rtn &= ~MPPC_OK; 267301549Spfg return (rtn); 268301549Spfg } 269301549Spfg } 270301549Spfg 271301549Spfg /* Add remaining octets to the output. */ 272301549Spfg while(*srcCnt - i > 0) { 273301549Spfg if ((*src)[i] < 0x80) { /* literal byte < 0x80 */ 274301549Spfg putbits8(*dst, (uint32_t) (*src)[i++], 8, &olen, &l); 275301549Spfg } else { /* literal byte >= 0x80 */ 276301549Spfg putbits16(*dst, (uint32_t) (0x100|((*src)[i++]&0x7f)), 9, &olen, 277301549Spfg &l); 278301549Spfg } 279301549Spfg } 280301549Spfg 281301549Spfg /* Reset unused bits of the last output octet. */ 282301549Spfg if ((l != 0) && (l != 8)) { 283301549Spfg putbits8(*dst, 0, l, &olen, &l); 284301549Spfg } 285301549Spfg 286301549Spfg /* If result is bigger then original, set flag and flush history. */ 287301549Spfg if ((*srcCnt < olen) || ((flags & MPPC_SAVE_HISTORY) == 0)) { 288301549Spfg if (*srcCnt < olen) 289301549Spfg rtn |= MPPC_EXPANDED; 290301549Spfg bzero(history, sizeof(struct MPPC_comp_state)); 291301549Spfg state->histptr = MPPE_HIST_LEN; 292301549Spfg } 293301549Spfg 294301549Spfg *src += *srcCnt; 295301549Spfg *srcCnt = 0; 296301549Spfg *dst += olen; 297301549Spfg *dstCnt -= olen; 298301549Spfg 299301549Spfg return (rtn); 300301549Spfg} 301