1 |
#include <stdio.h> |
2 |
#include <string.h> |
3 |
|
4 |
#include "rdesktop.h" |
5 |
|
6 |
/* mppc decompression */ |
7 |
/* http://www.faqs.org/rfcs/rfc2118.html */ |
8 |
|
9 |
/* TODO: research the below statements */ |
10 |
|
11 |
/* there exists one or more patents */ |
12 |
/* related to compression algorithms */ |
13 |
|
14 |
/* since we are only decompressing I */ |
15 |
/* think the end-user is safe. */ |
16 |
|
17 |
/* even if that isn't true, aren't you */ |
18 |
/* already paying royalties */ |
19 |
/* through the CAL licenses? */ |
20 |
|
21 |
/* as the rfc states the algorithm seems to */ |
22 |
/* be LZ77 with a sliding buffer */ |
23 |
/* that is empty at init. */ |
24 |
|
25 |
/* as of my limited knowledge these patents */ |
26 |
/* has expired. */ |
27 |
|
28 |
|
29 |
RDPCOMP g_mppc_dict; |
30 |
|
31 |
int |
32 |
mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen) |
33 |
{ |
34 |
int k, walker_len = 0, walker; |
35 |
int i = 0; |
36 |
int next_offset, match_off; |
37 |
int match_len; |
38 |
int old_offset, match_bits; |
39 |
|
40 |
signed char *dict = &(g_mppc_dict.hist); |
41 |
|
42 |
if ((ctype & RDP_MPPC_COMPRESSED) == 0) |
43 |
{ |
44 |
*roff = 0; |
45 |
*rlen = clen; |
46 |
return 0; |
47 |
} |
48 |
|
49 |
if ((ctype & RDP_MPPC_RESET) != 0) |
50 |
{ |
51 |
g_mppc_dict.roff = 0; |
52 |
} |
53 |
|
54 |
if ((ctype & RDP_MPPC_FLUSH) != 0) |
55 |
{ |
56 |
memset(dict, 0, RDP_MPPC_DICT_SIZE); |
57 |
g_mppc_dict.roff = 0; |
58 |
} |
59 |
|
60 |
*roff = 0; |
61 |
*rlen = 0; |
62 |
|
63 |
walker = g_mppc_dict.roff; |
64 |
|
65 |
next_offset = walker; |
66 |
old_offset = next_offset; |
67 |
*roff = old_offset; |
68 |
if (clen == 0) |
69 |
return 0; |
70 |
clen += i; |
71 |
|
72 |
do |
73 |
{ |
74 |
if (walker_len == 0) |
75 |
{ |
76 |
if (i >= clen) |
77 |
break; |
78 |
walker = data[i++] << 24; |
79 |
walker_len = 8; |
80 |
} |
81 |
if (walker >= 0) |
82 |
{ |
83 |
if (walker_len < 8) |
84 |
{ |
85 |
if (i >= clen) |
86 |
{ |
87 |
if (walker != 0) |
88 |
return -1; |
89 |
break; |
90 |
} |
91 |
walker |= (data[i++] & 0xff) << (24 - walker_len); |
92 |
walker_len += 8; |
93 |
} |
94 |
if (next_offset >= RDP_MPPC_DICT_SIZE) |
95 |
return -1; |
96 |
dict[next_offset++] = (((uint32) walker) >> ((uint32) 24)); |
97 |
walker <<= 8; |
98 |
walker_len -= 8; |
99 |
continue; |
100 |
} |
101 |
walker <<= 1; |
102 |
/* fetch next 8-bits */ |
103 |
if (--walker_len == 0) |
104 |
{ |
105 |
if (i >= clen) |
106 |
return -1; |
107 |
walker = data[i++] << 24; |
108 |
walker_len = 8; |
109 |
} |
110 |
/* literal decoding */ |
111 |
if (walker >= 0) |
112 |
{ |
113 |
if (walker_len < 8) |
114 |
{ |
115 |
if (i >= clen) |
116 |
return -1; |
117 |
walker |= (data[i++] & 0xff) << (24 - walker_len); |
118 |
walker_len += 8; |
119 |
} |
120 |
if (next_offset >= RDP_MPPC_DICT_SIZE) |
121 |
return -1; |
122 |
dict[next_offset++] = (uint8) (walker >> 24 | 0x80); |
123 |
walker <<= 8; |
124 |
walker_len -= 8; |
125 |
continue; |
126 |
} |
127 |
|
128 |
/* decode offset */ |
129 |
/* length pair */ |
130 |
walker <<= 1; |
131 |
if (--walker_len < 2) |
132 |
{ |
133 |
if (i >= clen) |
134 |
return -1; |
135 |
walker |= (data[i++] & 0xff) << (24 - walker_len); |
136 |
walker_len += 8; |
137 |
} |
138 |
/* offset decoding where offset len is: |
139 |
-63: 1111 followed by the lower 6 bits of the value |
140 |
64-319: 1110 followed by the lower 8 bits of the value ( value - 64 ) |
141 |
320-8191: 110 followed by the lower 13 bits of the value ( value - 320 ) |
142 |
*/ |
143 |
switch (((uint32) walker) >> ((uint32) 30)) |
144 |
{ |
145 |
case 3: /* - 63 */ |
146 |
if (walker_len < 8) |
147 |
{ |
148 |
if (i >= clen) |
149 |
return -1; |
150 |
walker |= (data[i++] & 0xff) << (24 - walker_len); |
151 |
walker_len += 8; |
152 |
} |
153 |
walker <<= 2; |
154 |
match_off = ((uint32) walker) >> ((uint32) 26); |
155 |
walker <<= 6; |
156 |
walker_len -= 8; |
157 |
break; |
158 |
|
159 |
case 2: /* 64 - 319 */ |
160 |
for (; walker_len < 10; walker_len += 8) |
161 |
{ |
162 |
if (i >= clen) |
163 |
return -1; |
164 |
walker |= (data[i++] & 0xff) << (24 - walker_len); |
165 |
} |
166 |
|
167 |
walker <<= 2; |
168 |
match_off = (((uint32) walker) >> ((uint32) 24)) + 64; |
169 |
walker <<= 8; |
170 |
walker_len -= 10; |
171 |
break; |
172 |
|
173 |
default: /* 320 - 8191 */ |
174 |
for (; walker_len < 14; walker_len += 8) |
175 |
{ |
176 |
if (i >= clen) |
177 |
return -1; |
178 |
walker |= (data[i++] & 0xff) << (24 - walker_len); |
179 |
} |
180 |
|
181 |
match_off = (walker >> 18) + 320; |
182 |
walker <<= 14; |
183 |
walker_len -= 14; |
184 |
break; |
185 |
} |
186 |
if (walker_len == 0) |
187 |
{ |
188 |
if (i >= clen) |
189 |
return -1; |
190 |
walker = data[i++] << 24; |
191 |
walker_len = 8; |
192 |
} |
193 |
|
194 |
/* decode length of match */ |
195 |
match_len = 0; |
196 |
if (walker >= 0) |
197 |
{ /* special case - length of 3 is in bit 0 */ |
198 |
match_len = 3; |
199 |
walker <<= 1; |
200 |
walker_len--; |
201 |
} |
202 |
else |
203 |
{ |
204 |
/* this is how it works len of: |
205 |
4-7: 10 followed by 2 bits of the value |
206 |
8-15: 110 followed by 3 bits of the value |
207 |
16-31: 1110 followed by 4 bits of the value |
208 |
32-63: .... and so forth |
209 |
64-127: |
210 |
128-255: |
211 |
256-511: |
212 |
512-1023: |
213 |
1024-2047: |
214 |
2048-4095: |
215 |
4096-8191: |
216 |
|
217 |
i.e. 4097 is encoded as: 111111111110 000000000001 |
218 |
meaning 4096 + 1... |
219 |
*/ |
220 |
match_bits = 11; /* 11 bits of value at most */ |
221 |
do |
222 |
{ |
223 |
walker <<= 1; |
224 |
if (--walker_len == 0) |
225 |
{ |
226 |
if (i >= clen) |
227 |
return -1; |
228 |
walker = data[i++] << 24; |
229 |
walker_len = 8; |
230 |
} |
231 |
if (walker >= 0) |
232 |
break; |
233 |
if (--match_bits == 0) |
234 |
{ |
235 |
return -1; |
236 |
} |
237 |
} |
238 |
while (1); |
239 |
match_len = 13 - match_bits; |
240 |
walker <<= 1; |
241 |
if (--walker_len < match_len) |
242 |
{ |
243 |
for (; walker_len < match_len; walker_len += 8) |
244 |
{ |
245 |
if (i >= clen) |
246 |
{ |
247 |
return -1; |
248 |
} |
249 |
walker |= (data[i++] & 0xff) << (24 - walker_len); |
250 |
} |
251 |
} |
252 |
|
253 |
match_bits = match_len; |
254 |
match_len = |
255 |
walker >> 32 - match_bits & ~(-1 << match_bits) | 1 << match_bits; |
256 |
walker <<= match_bits; |
257 |
walker_len -= match_bits; |
258 |
} |
259 |
if (next_offset + match_len >= RDP_MPPC_DICT_SIZE) |
260 |
{ |
261 |
return -1; |
262 |
} |
263 |
/* memory areas can overlap - meaning we can't use memXXX functions */ |
264 |
k = next_offset - match_off & (RDP_MPPC_DICT_SIZE - 1); |
265 |
do |
266 |
{ |
267 |
dict[next_offset++] = dict[k++]; |
268 |
} |
269 |
while (--match_len != 0); |
270 |
} |
271 |
while (1); |
272 |
|
273 |
/* store history offset */ |
274 |
g_mppc_dict.roff = next_offset; |
275 |
|
276 |
*roff = old_offset; |
277 |
*rlen = next_offset - old_offset; |
278 |
|
279 |
return 0; |
280 |
} |