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