1 /* -*- c-basic-offset: 8 -*-
2 rdesktop: A Remote Desktop Protocol client.
3 Protocol services - RDP decompression
4 Copyright (C) Matthew Chapman <matthewc.unsw.edu.au> 1999-2008
5
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include <stdio.h>
21 #include <string.h>
22
23 #include "rdesktop.h"
24
25 /* mppc decompression */
26 /* http://www.faqs.org/rfcs/rfc2118.html */
27
28 /* Contacts: */
29
30 /* hifn contact mentioned in the FAQ is */
31 /* Robert Friend rfriend at hifn dot com */
32
33 /* if you have questions regarding MPPC */
34 /* our contact is */
35 /* Guus Dhaeze GDhaeze at hifn dot com */
36
37 /* Licensing: */
38
39 /* decompression is alright as long as we */
40 /* don't compress data */
41
42 /* Algorithm: */
43
44 /* as the RFC states the algorithm seems to */
45 /* be LZ77 with a sliding buffer */
46 /* that is empty at init. */
47
48 /* the algorithm is called LZS and is */
49 /* patented for another couple of years. */
50
51 /* more information is available in */
52 /* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */
53
54
55 RDPCOMP g_mppc_dict;
56
57 int
mppc_expand(uint8 * data,uint32 clen,uint8 ctype,uint32 * roff,uint32 * rlen)58 mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen)
59 {
60 int k, walker_len = 0, walker;
61 uint32 i = 0;
62 int next_offset, match_off;
63 int match_len;
64 int old_offset, match_bits;
65 RD_BOOL big = ctype & RDP_MPPC_BIG ? True : False;
66
67 uint8 *dict = g_mppc_dict.hist;
68
69 if ((ctype & RDP_MPPC_COMPRESSED) == 0)
70 {
71 *roff = 0;
72 *rlen = clen;
73 return 0;
74 }
75
76 if ((ctype & RDP_MPPC_RESET) != 0)
77 {
78 g_mppc_dict.roff = 0;
79 }
80
81 if ((ctype & RDP_MPPC_FLUSH) != 0)
82 {
83 memset(dict, 0, RDP_MPPC_DICT_SIZE);
84 g_mppc_dict.roff = 0;
85 }
86
87 *roff = 0;
88 *rlen = 0;
89
90 walker = g_mppc_dict.roff;
91
92 next_offset = walker;
93 old_offset = next_offset;
94 *roff = old_offset;
95 if (clen == 0)
96 return 0;
97 clen += i;
98
99 do
100 {
101 if (walker_len == 0)
102 {
103 if (i >= clen)
104 break;
105 walker = data[i++] << 24;
106 walker_len = 8;
107 }
108 if (walker >= 0)
109 {
110 if (walker_len < 8)
111 {
112 if (i >= clen)
113 {
114 if (walker != 0)
115 return -1;
116 break;
117 }
118 walker |= (data[i++] & 0xff) << (24 - walker_len);
119 walker_len += 8;
120 }
121 if (next_offset >= RDP_MPPC_DICT_SIZE)
122 return -1;
123 dict[next_offset++] = (((uint32) walker) >> ((uint32) 24));
124 walker <<= 8;
125 walker_len -= 8;
126 continue;
127 }
128 walker <<= 1;
129 /* fetch next 8-bits */
130 if (--walker_len == 0)
131 {
132 if (i >= clen)
133 return -1;
134 walker = data[i++] << 24;
135 walker_len = 8;
136 }
137 /* literal decoding */
138 if (walker >= 0)
139 {
140 if (walker_len < 8)
141 {
142 if (i >= clen)
143 return -1;
144 walker |= (data[i++] & 0xff) << (24 - walker_len);
145 walker_len += 8;
146 }
147 if (next_offset >= RDP_MPPC_DICT_SIZE)
148 return -1;
149 dict[next_offset++] = (uint8) (walker >> 24 | 0x80);
150 walker <<= 8;
151 walker_len -= 8;
152 continue;
153 }
154
155 /* decode offset */
156 /* length pair */
157 walker <<= 1;
158 if (--walker_len < (big ? 3 : 2))
159 {
160 if (i >= clen)
161 return -1;
162 walker |= (data[i++] & 0xff) << (24 - walker_len);
163 walker_len += 8;
164 }
165
166 if (big)
167 {
168 /* offset decoding where offset len is:
169 -63: 11111 followed by the lower 6 bits of the value
170 64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
171 320-2367: 1110 followed by lower 11 bits of the value ( value - 320 )
172 2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 )
173 */
174 switch (((uint32) walker) >> ((uint32) 29))
175 {
176 case 7: /* - 63 */
177 for (; walker_len < 9; walker_len += 8)
178 {
179 if (i >= clen)
180 return -1;
181 walker |= (data[i++] & 0xff) << (24 - walker_len);
182 }
183 walker <<= 3;
184 match_off = ((uint32) walker) >> ((uint32) 26);
185 walker <<= 6;
186 walker_len -= 9;
187 break;
188
189 case 6: /* 64 - 319 */
190 for (; walker_len < 11; walker_len += 8)
191 {
192 if (i >= clen)
193 return -1;
194 walker |= (data[i++] & 0xff) << (24 - walker_len);
195 }
196
197 walker <<= 3;
198 match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
199 walker <<= 8;
200 walker_len -= 11;
201 break;
202
203 case 5:
204 case 4: /* 320 - 2367 */
205 for (; walker_len < 13; walker_len += 8)
206 {
207 if (i >= clen)
208 return -1;
209 walker |= (data[i++] & 0xff) << (24 - walker_len);
210 }
211
212 walker <<= 2;
213 match_off = (((uint32) walker) >> ((uint32) 21)) + 320;
214 walker <<= 11;
215 walker_len -= 13;
216 break;
217
218 default: /* 2368 - 65535 */
219 for (; walker_len < 17; walker_len += 8)
220 {
221 if (i >= clen)
222 return -1;
223 walker |= (data[i++] & 0xff) << (24 - walker_len);
224 }
225
226 walker <<= 1;
227 match_off = (((uint32) walker) >> ((uint32) 16)) + 2368;
228 walker <<= 16;
229 walker_len -= 17;
230 break;
231 }
232 }
233 else
234 {
235 /* offset decoding where offset len is:
236 -63: 1111 followed by the lower 6 bits of the value
237 64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
238 320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
239 */
240 switch (((uint32) walker) >> ((uint32) 30))
241 {
242 case 3: /* - 63 */
243 if (walker_len < 8)
244 {
245 if (i >= clen)
246 return -1;
247 walker |= (data[i++] & 0xff) << (24 - walker_len);
248 walker_len += 8;
249 }
250 walker <<= 2;
251 match_off = ((uint32) walker) >> ((uint32) 26);
252 walker <<= 6;
253 walker_len -= 8;
254 break;
255
256 case 2: /* 64 - 319 */
257 for (; walker_len < 10; walker_len += 8)
258 {
259 if (i >= clen)
260 return -1;
261 walker |= (data[i++] & 0xff) << (24 - walker_len);
262 }
263
264 walker <<= 2;
265 match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
266 walker <<= 8;
267 walker_len -= 10;
268 break;
269
270 default: /* 320 - 8191 */
271 for (; walker_len < 14; walker_len += 8)
272 {
273 if (i >= clen)
274 return -1;
275 walker |= (data[i++] & 0xff) << (24 - walker_len);
276 }
277
278 match_off = (walker >> 18) + 320;
279 walker <<= 14;
280 walker_len -= 14;
281 break;
282 }
283 }
284 if (walker_len == 0)
285 {
286 if (i >= clen)
287 return -1;
288 walker = data[i++] << 24;
289 walker_len = 8;
290 }
291
292 /* decode length of match */
293 match_len = 0;
294 if (walker >= 0)
295 { /* special case - length of 3 is in bit 0 */
296 match_len = 3;
297 walker <<= 1;
298 walker_len--;
299 }
300 else
301 {
302 /* this is how it works len of:
303 4-7: 10 followed by 2 bits of the value
304 8-15: 110 followed by 3 bits of the value
305 16-31: 1110 followed by 4 bits of the value
306 32-63: .... and so forth
307 64-127:
308 128-255:
309 256-511:
310 512-1023:
311 1024-2047:
312 2048-4095:
313 4096-8191:
314
315 i.e. 4097 is encoded as: 111111111110 000000000001
316 meaning 4096 + 1...
317 */
318 match_bits = big ? 14 : 11; /* 11 or 14 bits of value at most */
319 do
320 {
321 walker <<= 1;
322 if (--walker_len == 0)
323 {
324 if (i >= clen)
325 return -1;
326 walker = data[i++] << 24;
327 walker_len = 8;
328 }
329 if (walker >= 0)
330 break;
331 if (--match_bits == 0)
332 {
333 return -1;
334 }
335 }
336 while (1);
337 match_len = (big ? 16 : 13) - match_bits;
338 walker <<= 1;
339 if (--walker_len < match_len)
340 {
341 for (; walker_len < match_len; walker_len += 8)
342 {
343 if (i >= clen)
344 {
345 return -1;
346 }
347 walker |= (data[i++] & 0xff) << (24 - walker_len);
348 }
349 }
350
351 match_bits = match_len;
352 match_len = (walker >> (32 - match_bits));
353 match_len &= ((1 << match_bits) - 1);
354 match_len |= (1 << match_bits);
355 walker <<= match_bits;
356 walker_len -= match_bits;
357 }
358 if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
359 {
360 return -1;
361 }
362 /* memory areas can overlap - meaning we can't use memXXX functions */
363 k = (next_offset - match_off) & (big ? 65535 : 8191);
364 do
365 {
366 dict[next_offset++] = dict[k++];
367 }
368 while (--match_len != 0);
369 }
370 while (1);
371
372 /* store history offset */
373 g_mppc_dict.roff = next_offset;
374
375 *roff = old_offset;
376 *rlen = next_offset - old_offset;
377
378 return 0;
379 }
380