2 * Copyright (c) 2002-2004 Jan Dubiec <jdx@slackware.pl>
3 * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice unmodified, this list of conditions, and the following
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.
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
32 * MPPC decompression library.
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
41 #include <sys/param.h>
42 #include <sys/systm.h>
46 #define MPPE_HIST_LEN 8192
48 struct MPPC_decomp_state
{
49 uint8_t hist
[2*MPPE_HIST_LEN
];
53 static uint32_t __inline
54 getbits(const uint8_t *buf
, const uint32_t n
, uint32_t *i
, uint32_t *l
)
56 static const uint32_t m
[] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
62 res
= (buf
[*i
] & m
[ol
]) >> (*l
);
69 res
= (buf
[(*i
)++] & m
[ol
]) << 8;
70 res
= (res
| buf
[*i
]) >> (*l
);
76 static uint32_t __inline
77 getbyte(const uint8_t *buf
, const uint32_t i
, const uint32_t l
)
82 return ((((buf
[i
] << 8) | buf
[i
+1]) >> l
) & 0xff);
87 lamecopy(uint8_t *dst
, uint8_t *src
, uint32_t len
)
93 size_t MPPC_SizeOfDecompressionHistory(void)
95 return (sizeof(struct MPPC_decomp_state
));
98 void MPPC_InitDecompressionHistory(char *history
)
100 struct MPPC_decomp_state
*state
= (struct MPPC_decomp_state
*)history
;
102 bzero(history
, sizeof(struct MPPC_decomp_state
));
103 state
->histptr
= MPPE_HIST_LEN
;
106 int MPPC_Decompress(u_char
**src
, u_char
**dst
, u_long
*srcCnt
, u_long
*dstCnt
, char *history
, int flags
)
108 struct MPPC_decomp_state
*state
= (struct MPPC_decomp_state
*)history
;
109 uint32_t olen
, off
, len
, bits
, val
, sig
, i
, l
;
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
;
119 hist
= state
->hist
+ state
->histptr
;
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
;
130 /* Buffer overflow; drop packet. */
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
));
146 /* buffer overflow; drop packet */
155 /* Not a literal byte so it must be an (offset,length) pair */
158 if (sig
== 0xf0) { /* 10-bit offset; 0 <= offset < 64 */
159 off
= (((val
&0x0f)<<2)|getbits(isrc
, 2 , &i
,&l
));
162 if (sig
== 0xe0) { /* 12-bit offset; 64 <= offset < 320 */
163 off
= ((((val
&0x0f)<<4)|getbits(isrc
, 4 , &i
,&l
))+64);
166 if ((sig
&0xe0) == 0xc0) {/* 16-bit offset; 320 <= offset < 8192 */
167 off
= ((((val
&0x1f)<<8)|getbyte(isrc
, i
++, l
))+320);
169 if (off
> MPPE_HIST_LEN
- 1) {
173 } else { /* NOTREACHED */
179 /* Decode length of match. */
180 val
= getbyte(isrc
, i
, l
);
181 if ((val
& 0x80) == 0x00) { /* len = 3 */
184 getbits(isrc
, 1 , &i
,&l
);
185 } else if ((val
& 0xc0) == 0x80) { /* 4 <= len < 8 */
186 len
= 0x04 | ((val
>>4) & 0x03);
188 getbits(isrc
, 4 , &i
,&l
);
189 } else if ((val
& 0xe0) == 0xc0) { /* 8 <= len < 16 */
190 len
= 0x08 | ((val
>>2) & 0x07);
192 getbits(isrc
, 6 , &i
,&l
);
193 } else if ((val
& 0xf0) == 0xe0) { /* 16 <= len < 32 */
194 len
= 0x10 | (val
& 0x0f);
199 val
= (val
<< 8) | getbyte(isrc
, ++i
, l
);
200 if ((val
& 0xf800) == 0xf000) { /* 32 <= len < 64 */
201 len
= 0x0020 | ((val
>> 6) & 0x001f);
203 getbits(isrc
, 2 , &i
,&l
);
204 } else if ((val
& 0xfc00) == 0xf800) { /* 64 <= len < 128 */
205 len
= 0x0040 | ((val
>> 4) & 0x003f);
207 getbits(isrc
, 4 , &i
,&l
);
208 } else if ((val
& 0xfe00) == 0xfc00) { /* 128 <= len < 256 */
209 len
= 0x0080 | ((val
>> 2) & 0x007f);
211 getbits(isrc
, 6 , &i
,&l
);
212 } else if ((val
& 0xff00) == 0xfe00) { /* 256 <= len < 512 */
213 len
= 0x0100 | (val
& 0x00ff);
218 val
= (val
<< 8) | getbyte(isrc
, ++i
, l
);
219 if ((val
& 0xff8000) == 0xff0000) { /* 512 <= len < 1024 */
220 len
= 0x000200 | ((val
>> 6) & 0x0001ff);
222 getbits(isrc
, 2 , &i
,&l
);
223 } else if ((val
& 0xffc000) == 0xff8000) {/* 1024 <= len < 2048 */
224 len
= 0x000400 | ((val
>> 4) & 0x0003ff);
226 getbits(isrc
, 4 , &i
,&l
);
227 } else if ((val
& 0xffe000) == 0xffc000) {/* 2048 <= len < 4096 */
228 len
= 0x000800 | ((val
>> 2) & 0x0007ff);
230 getbits(isrc
, 6 , &i
,&l
);
231 } else if ((val
& 0xfff000) == 0xffe000) {/* 4096 <= len < 8192 */
232 len
= 0x001000 | (val
& 0x000fff);
235 } else { /* NOTREACHED */
242 s
= state
->hist
+ state
->histptr
;
243 state
->histptr
+= len
;
245 if (state
->histptr
< 2*MPPE_HIST_LEN
) {
246 /* Copy uncompressed bytes to the history. */
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.
254 lamecopy(s
, s
- off
, len
);
256 /* Buffer overflow; drop packet. */
262 /* Do PFC decompression. */
264 if ((hist
[0] & 0x01) != 0) {
270 if (len
<= *dstCnt
) {
271 /* Copy uncompressed packet to the output buffer. */
272 memcpy(*dst
, hist
, olen
);
274 /* Buffer overflow; drop packet. */
275 rtn
|= MPPC_DEST_EXHAUSTED
;