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 #define HASH(x) (((40543*(((((x)[0]<<4)^(x)[1])<<4)^(x)[2]))>>4) & 0x1fff) 49 50 struct MPPC_comp_state { 51 uint8_t hist[2*MPPE_HIST_LEN]; 52 uint16_t histptr; 53 uint16_t hash[MPPE_HIST_LEN]; 54 }; 55 56 /* Inserts 1 to 8 bits into the output buffer. */ 57 static void __inline 58 putbits8(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) 59 { 60 buf += *i; 61 if (*l >= n) { 62 *l = (*l) - n; 63 val <<= *l; 64 *buf = *buf | (val & 0xff); 65 if (*l == 0) { 66 *l = 8; 67 (*i)++; 68 *(++buf) = 0; 69 } 70 } else { 71 (*i)++; 72 *l = 8 - n + (*l); 73 val <<= *l; 74 *buf = *buf | ((val >> 8) & 0xff); 75 *(++buf) = val & 0xff; 76 } 77 } 78 79 /* Inserts 9 to 16 bits into the output buffer. */ 80 static void __inline 81 putbits16(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) 82 { 83 buf += *i; 84 if (*l >= n - 8) { 85 (*i)++; 86 *l = 8 - n + (*l); 87 val <<= *l; 88 *buf = *buf | ((val >> 8) & 0xff); 89 *(++buf) = val & 0xff; 90 if (*l == 0) { 91 *l = 8; 92 (*i)++; 93 *(++buf) = 0; 94 } 95 } else { 96 (*i)++; (*i)++; 97 *l = 16 - n + (*l); 98 val <<= *l; 99 *buf = *buf | ((val >> 16) & 0xff); 100 *(++buf) = (val >> 8) & 0xff; 101 *(++buf) = val & 0xff; 102 } 103 } 104 105 /* Inserts 17 to 24 bits into the output buffer. */ 106 static void __inline 107 putbits24(uint8_t *buf, uint32_t val, const uint32_t n, uint32_t *i, uint32_t *l) 108 { 109 buf += *i; 110 if (*l >= n - 16) { 111 (*i)++; (*i)++; 112 *l = 16 - n + (*l); 113 val <<= *l; 114 *buf = *buf | ((val >> 16) & 0xff); 115 *(++buf) = (val >> 8) & 0xff; 116 *(++buf) = val & 0xff; 117 if (*l == 0) { 118 *l = 8; 119 (*i)++; 120 *(++buf) = 0; 121 } 122 } else { 123 (*i)++; (*i)++; (*i)++; 124 *l = 24 - n + (*l); 125 val <<= *l; 126 *buf = *buf | ((val >> 24) & 0xff); 127 *(++buf) = (val >> 16) & 0xff; 128 *(++buf) = (val >> 8) & 0xff; 129 *(++buf) = val & 0xff; 130 } 131 } 132 133 size_t MPPC_SizeOfCompressionHistory(void) 134 { 135 return (sizeof(struct MPPC_comp_state)); 136 } 137 138 void MPPC_InitCompressionHistory(char *history) 139 { 140 struct MPPC_comp_state *state = (struct MPPC_comp_state*)history; 141 142 bzero(history, sizeof(struct MPPC_comp_state)); 143 state->histptr = MPPE_HIST_LEN; 144 } 145 146 int MPPC_Compress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags, int undef) 147 { 148 struct MPPC_comp_state *state = (struct MPPC_comp_state*)history; 149 uint32_t olen, off, len, idx, i, l; 150 uint8_t *hist, *sbuf, *p, *q, *r, *s; 151 int rtn = MPPC_OK; 152 153 /* 154 * At this point, to avoid possible buffer overflow caused by packet 155 * expansion during/after compression, we should make sure we have 156 * space for the worst case. 157 158 * Maximum MPPC packet expansion is 12.5%. This is the worst case when 159 * all octets in the input buffer are >= 0x80 and we cannot find any 160 * repeated tokens. 161 */ 162 if (*dstCnt < (*srcCnt * 9 / 8 + 2)) { 163 rtn &= ~MPPC_OK; 164 return (rtn); 165 } 166 167 /* We can't compress more then MPPE_HIST_LEN bytes in a call. */ 168 if (*srcCnt > MPPE_HIST_LEN) { 169 rtn &= ~MPPC_OK; 170 return (rtn); 171 } 172 173 hist = state->hist + MPPE_HIST_LEN; 174 /* check if there is enough room at the end of the history */ 175 if (state->histptr + *srcCnt >= 2*MPPE_HIST_LEN) { 176 rtn |= MPPC_RESTART_HISTORY; 177 state->histptr = MPPE_HIST_LEN; 178 memcpy(state->hist, hist, MPPE_HIST_LEN); 179 } 180 /* Add packet to the history. */ 181 sbuf = state->hist + state->histptr; 182 memcpy(sbuf, *src, *srcCnt); 183 state->histptr += *srcCnt; 184 185 /* compress data */ 186 r = sbuf + *srcCnt; 187 **dst = olen = i = 0; 188 l = 8; 189 while (i < *srcCnt - 2) { 190 s = q = sbuf + i; 191 192 /* Prognose matching position using hash function. */ 193 idx = HASH(s); 194 p = hist + state->hash[idx]; 195 state->hash[idx] = (uint16_t) (s - hist); 196 if (p > s) /* It was before MPPC_RESTART_HISTORY. */ 197 p -= MPPE_HIST_LEN; /* Try previous history buffer. */ 198 off = s - p; 199 200 /* Check our prognosis. */ 201 if (off > MPPE_HIST_LEN - 1 || off < 1 || *p++ != *s++ || 202 *p++ != *s++ || *p++ != *s++) { 203 /* No match found; encode literal byte. */ 204 if ((*src)[i] < 0x80) { /* literal byte < 0x80 */ 205 putbits8(*dst, (uint32_t) (*src)[i], 8, &olen, &l); 206 } else { /* literal byte >= 0x80 */ 207 putbits16(*dst, (uint32_t) (0x100|((*src)[i]&0x7f)), 9, 208 &olen, &l); 209 } 210 ++i; 211 continue; 212 } 213 214 /* Find length of the matching fragment */ 215 #if defined(__amd64__) || defined(__i386__) 216 /* Optimization for CPUs without strict data aligning requirements */ 217 while ((*((uint32_t*)p) == *((uint32_t*)s)) && (s < (r - 3))) { 218 p+=4; 219 s+=4; 220 } 221 #endif 222 while((*p++ == *s++) && (s <= r)); 223 len = s - q - 1; 224 i += len; 225 226 /* At least 3 character match found; code data. */ 227 /* Encode offset. */ 228 if (off < 64) { /* 10-bit offset; 0 <= offset < 64 */ 229 putbits16(*dst, 0x3c0|off, 10, &olen, &l); 230 } else if (off < 320) { /* 12-bit offset; 64 <= offset < 320 */ 231 putbits16(*dst, 0xe00|(off-64), 12, &olen, &l); 232 } else if (off < 8192) { /* 16-bit offset; 320 <= offset < 8192 */ 233 putbits16(*dst, 0xc000|(off-320), 16, &olen, &l); 234 } else { /* NOTREACHED */ 235 __unreachable(); 236 rtn &= ~MPPC_OK; 237 return (rtn); 238 } 239 240 /* Encode length of match. */ 241 if (len < 4) { /* length = 3 */ 242 putbits8(*dst, 0, 1, &olen, &l); 243 } else if (len < 8) { /* 4 <= length < 8 */ 244 putbits8(*dst, 0x08|(len&0x03), 4, &olen, &l); 245 } else if (len < 16) { /* 8 <= length < 16 */ 246 putbits8(*dst, 0x30|(len&0x07), 6, &olen, &l); 247 } else if (len < 32) { /* 16 <= length < 32 */ 248 putbits8(*dst, 0xe0|(len&0x0f), 8, &olen, &l); 249 } else if (len < 64) { /* 32 <= length < 64 */ 250 putbits16(*dst, 0x3c0|(len&0x1f), 10, &olen, &l); 251 } else if (len < 128) { /* 64 <= length < 128 */ 252 putbits16(*dst, 0xf80|(len&0x3f), 12, &olen, &l); 253 } else if (len < 256) { /* 128 <= length < 256 */ 254 putbits16(*dst, 0x3f00|(len&0x7f), 14, &olen, &l); 255 } else if (len < 512) { /* 256 <= length < 512 */ 256 putbits16(*dst, 0xfe00|(len&0xff), 16, &olen, &l); 257 } else if (len < 1024) { /* 512 <= length < 1024 */ 258 putbits24(*dst, 0x3fc00|(len&0x1ff), 18, &olen, &l); 259 } else if (len < 2048) { /* 1024 <= length < 2048 */ 260 putbits24(*dst, 0xff800|(len&0x3ff), 20, &olen, &l); 261 } else if (len < 4096) { /* 2048 <= length < 4096 */ 262 putbits24(*dst, 0x3ff000|(len&0x7ff), 22, &olen, &l); 263 } else if (len < 8192) { /* 4096 <= length < 8192 */ 264 putbits24(*dst, 0xffe000|(len&0xfff), 24, &olen, &l); 265 } else { /* NOTREACHED */ 266 rtn &= ~MPPC_OK; 267 return (rtn); 268 } 269 } 270 271 /* Add remaining octets to the output. */ 272 while(*srcCnt - i > 0) { 273 if ((*src)[i] < 0x80) { /* literal byte < 0x80 */ 274 putbits8(*dst, (uint32_t) (*src)[i++], 8, &olen, &l); 275 } else { /* literal byte >= 0x80 */ 276 putbits16(*dst, (uint32_t) (0x100|((*src)[i++]&0x7f)), 9, &olen, 277 &l); 278 } 279 } 280 281 /* Reset unused bits of the last output octet. */ 282 if ((l != 0) && (l != 8)) { 283 putbits8(*dst, 0, l, &olen, &l); 284 } 285 286 /* If result is bigger then original, set flag and flush history. */ 287 if ((*srcCnt < olen) || ((flags & MPPC_SAVE_HISTORY) == 0)) { 288 if (*srcCnt < olen) 289 rtn |= MPPC_EXPANDED; 290 bzero(history, sizeof(struct MPPC_comp_state)); 291 state->histptr = MPPE_HIST_LEN; 292 } 293 294 *src += *srcCnt; 295 *srcCnt = 0; 296 *dst += olen; 297 *dstCnt -= olen; 298 299 return (rtn); 300 } 301