xref: /freebsd/sys/net/mppcd.c (revision 7fdf597e96a02165cfe22ff357b857d5fa15ed8a)
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 struct MPPC_decomp_state {
47     uint8_t	hist[2*MPPE_HIST_LEN];
48     uint16_t	histptr;
49 };
50 
51 static uint32_t __inline
52 getbits(const uint8_t *buf, const uint32_t n, uint32_t *i, uint32_t *l)
53 {
54     static const uint32_t m[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
55     uint32_t res, ol;
56 
57     ol = *l;
58     if (*l >= n) {
59 	*l = (*l) - n;
60 	res = (buf[*i] & m[ol]) >> (*l);
61 	if (*l == 0) {
62 	    *l = 8;
63 	    (*i)++;
64 	}
65     } else {
66 	*l = 8 - n + (*l);
67 	res = (buf[(*i)++] & m[ol]) << 8;
68 	res = (res | buf[*i]) >> (*l);
69     }
70 
71     return (res);
72 }
73 
74 static uint32_t __inline
75 getbyte(const uint8_t *buf, const uint32_t i, const uint32_t l)
76 {
77     if (l == 8) {
78 	return (buf[i]);
79     } else {
80 	return ((((buf[i] << 8) | buf[i+1]) >> l) & 0xff);
81     }
82 }
83 
84 static void __inline
85 lamecopy(uint8_t *dst, uint8_t *src, uint32_t len)
86 {
87     while (len--)
88 	*dst++ = *src++;
89 }
90 
91 size_t MPPC_SizeOfDecompressionHistory(void)
92 {
93     return (sizeof(struct MPPC_decomp_state));
94 }
95 
96 void MPPC_InitDecompressionHistory(char *history)
97 {
98     struct MPPC_decomp_state      *state = (struct MPPC_decomp_state*)history;
99 
100     bzero(history, sizeof(struct MPPC_decomp_state));
101     state->histptr = MPPE_HIST_LEN;
102 }
103 
104 int MPPC_Decompress(u_char **src, u_char **dst, u_long *srcCnt, u_long *dstCnt, char *history, int flags)
105 {
106     struct MPPC_decomp_state      *state = (struct MPPC_decomp_state*)history;
107     uint32_t olen, off, len, bits, val, sig, i, l;
108     uint8_t *hist, *s;
109     u_char *isrc = *src;
110     int	rtn = MPPC_OK;
111 
112     if ((flags & MPPC_RESTART_HISTORY) != 0) {
113 	memcpy(state->hist, state->hist + MPPE_HIST_LEN, MPPE_HIST_LEN);
114 	state->histptr = MPPE_HIST_LEN;
115     }
116 
117     hist = state->hist + state->histptr;
118     olen = len = i = 0;
119     l = 8;
120     bits = *srcCnt * 8;
121     while (bits >= 8) {
122 	val = getbyte(isrc, i++, l);
123 	if (val < 0x80) {		/* literal byte < 0x80 */
124 	    if (state->histptr < 2*MPPE_HIST_LEN) {
125 		/* Copy uncompressed byte to the history. */
126 		(state->hist)[(state->histptr)++] = (uint8_t) val;
127 	    } else {
128 		/* Buffer overflow; drop packet. */
129 		rtn &= ~MPPC_OK;
130 		return rtn;
131 	    }
132 	    olen++;
133 	    bits -= 8;
134 	    continue;
135 	}
136 
137 	sig = val & 0xc0;
138 	if (sig == 0x80) {		/* literal byte >= 0x80 */
139 	    if (state->histptr < 2*MPPE_HIST_LEN) {
140 		/* Copy uncompressed byte to the history. */
141 		(state->hist)[(state->histptr)++] =
142 		    (uint8_t) (0x80|((val&0x3f)<<1)|getbits(isrc, 1 , &i ,&l));
143 	    } else {
144 		/* buffer overflow; drop packet */
145 		rtn &= ~MPPC_OK;
146 		return (rtn);
147 	    }
148 	    olen++;
149 	    bits -= 9;
150 	    continue;
151 	}
152 
153 	/* Not a literal byte so it must be an (offset,length) pair */
154 	/* decode offset */
155 	sig = val & 0xf0;
156 	if (sig == 0xf0) {		/* 10-bit offset; 0 <= offset < 64 */
157 	    off = (((val&0x0f)<<2)|getbits(isrc, 2 , &i ,&l));
158 	    bits -= 10;
159 	} else {
160 	    if (sig == 0xe0) {		/* 12-bit offset; 64 <= offset < 320 */
161 		off = ((((val&0x0f)<<4)|getbits(isrc, 4 , &i ,&l))+64);
162 		bits -= 12;
163 	    } else {
164 		if ((sig&0xe0) == 0xc0) {/* 16-bit offset; 320 <= offset < 8192 */
165 		    off = ((((val&0x1f)<<8)|getbyte(isrc, i++, l))+320);
166 		    bits -= 16;
167 		    if (off > MPPE_HIST_LEN - 1) {
168 			rtn &= ~MPPC_OK;
169 			return (rtn);
170 		    }
171 		} else {		/* This shouldn't happen. */
172 		    rtn &= ~MPPC_OK;
173 		    return (rtn);
174 		}
175 	    }
176 	}
177 	/* Decode length of match. */
178 	val = getbyte(isrc, i, l);
179 	if ((val & 0x80) == 0x00) {			/* len = 3 */
180 	    len = 3;
181 	    bits--;
182 	    getbits(isrc, 1 , &i ,&l);
183 	} else if ((val & 0xc0) == 0x80) {		/* 4 <= len < 8 */
184 	    len = 0x04 | ((val>>4) & 0x03);
185 	    bits -= 4;
186 	    getbits(isrc, 4 , &i ,&l);
187 	} else if ((val & 0xe0) == 0xc0) {		/* 8 <= len < 16 */
188 	    len = 0x08 | ((val>>2) & 0x07);
189 	    bits -= 6;
190 	    getbits(isrc, 6 , &i ,&l);
191 	} else if ((val & 0xf0) == 0xe0) {		/* 16 <= len < 32 */
192 	    len = 0x10 | (val & 0x0f);
193 	    bits -= 8;
194 	    i++;
195 	} else {
196 	    bits -= 8;
197 	    val = (val << 8) | getbyte(isrc, ++i, l);
198 	    if ((val & 0xf800) == 0xf000) {		/* 32 <= len < 64 */
199 		len = 0x0020 | ((val >> 6) & 0x001f);
200 		bits -= 2;
201 		getbits(isrc, 2 , &i ,&l);
202 	    } else if ((val & 0xfc00) == 0xf800) {	/* 64 <= len < 128 */
203 		len = 0x0040 | ((val >> 4) & 0x003f);
204 		bits -= 4;
205 		getbits(isrc, 4 , &i ,&l);
206 	    } else if ((val & 0xfe00) == 0xfc00) {	/* 128 <= len < 256 */
207 		len = 0x0080 | ((val >> 2) & 0x007f);
208 		bits -= 6;
209 		getbits(isrc, 6 , &i ,&l);
210 	    } else if ((val & 0xff00) == 0xfe00) {	/* 256 <= len < 512 */
211 		len = 0x0100 | (val & 0x00ff);
212 		bits -= 8;
213 		i++;
214 	    } else {
215 		bits -= 8;
216 		val = (val << 8) | getbyte(isrc, ++i, l);
217 		if ((val & 0xff8000) == 0xff0000) {	/* 512 <= len < 1024 */
218 		    len = 0x000200 | ((val >> 6) & 0x0001ff);
219 		    bits -= 2;
220 		    getbits(isrc, 2 , &i ,&l);
221 		} else if ((val & 0xffc000) == 0xff8000) {/* 1024 <= len < 2048 */
222 		    len = 0x000400 | ((val >> 4) & 0x0003ff);
223 		    bits -= 4;
224 		    getbits(isrc, 4 , &i ,&l);
225 		} else if ((val & 0xffe000) == 0xffc000) {/* 2048 <= len < 4096 */
226 		    len = 0x000800 | ((val >> 2) & 0x0007ff);
227 		    bits -= 6;
228 		    getbits(isrc, 6 , &i ,&l);
229 		} else if ((val & 0xfff000) == 0xffe000) {/* 4096 <= len < 8192 */
230 		    len = 0x001000 | (val & 0x000fff);
231 		    bits -= 8;
232 		    i++;
233 		} else {				/* NOTREACHED */
234 		    rtn &= ~MPPC_OK;
235 		    return (rtn);
236 		}
237 	    }
238 	}
239 
240 	s = state->hist + state->histptr;
241 	state->histptr += len;
242 	olen += len;
243 	if (state->histptr < 2*MPPE_HIST_LEN) {
244 	    /* Copy uncompressed bytes to the history. */
245 
246 	    /*
247 	     * In some cases len may be greater than off. It means that memory
248 	     * areas pointed by s and s-off overlap. To decode that strange case
249 	     * data should be copied exactly by address increasing to make
250 	     * some data repeated.
251 	     */
252 	    lamecopy(s, s - off, len);
253 	} else {
254 	    /* Buffer overflow; drop packet. */
255 	    rtn &= ~MPPC_OK;
256 	    return (rtn);
257 	}
258     }
259 
260     /* Do PFC decompression. */
261     len = olen;
262     if ((hist[0] & 0x01) != 0) {
263 	(*dst)[0] = 0;
264 	(*dst)++;
265 	len++;
266     }
267 
268     if (len <= *dstCnt) {
269 	/* Copy uncompressed packet to the output buffer. */
270 	memcpy(*dst, hist, olen);
271     } else {
272 	/* Buffer overflow; drop packet. */
273 	rtn |= MPPC_DEST_EXHAUSTED;
274     }
275 
276     *src += *srcCnt;
277     *srcCnt = 0;
278     *dst += len;
279     *dstCnt -= len;
280 
281     return (rtn);
282 }
283