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