1 /* -*- c-basic-offset: 8 -*-
2 rdesktop: A Remote Desktop Protocol client.
3 Protocol services - RDP decompression
4 Copyright (C) Matthew Chapman 1999-2005
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 2 of the License, or
9 (at your option) any later version.
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.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 /* mppc decompression */
24 /* http://www.faqs.org/rfcs/rfc2118.html */
28 /* hifn contact mentioned in the faq is */
29 /* Robert Friend rfriend at hifn dot com */
31 /* if you have questions regarding MPPC */
33 /* Guus Dhaeze GDhaeze at hifn dot com */
37 /* decompression is alright as long as we */
38 /* don't compress data */
42 /* as the rfc states the algorithm seems to */
43 /* be LZ77 with a sliding buffer */
44 /* that is empty at init. */
46 /* the algorithm is called LZS and is */
47 /* patented for another couple of years. */
49 /* more information is available in */
50 /* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */
56 mppc_expand(uint8
* data
, uint32 clen
, uint8 ctype
, uint32
* roff
, uint32
* rlen
)
58 int k
, walker_len
= 0, walker
;
60 int next_offset
, match_off
;
62 int old_offset
, match_bits
;
63 BOOL big
= ctype
& RDP_MPPC_BIG
? True
: False
;
65 uint8
*dict
= g_mppc_dict
.hist
;
67 if ((ctype
& RDP_MPPC_COMPRESSED
) == 0)
74 if ((ctype
& RDP_MPPC_RESET
) != 0)
79 if ((ctype
& RDP_MPPC_FLUSH
) != 0)
81 memset(dict
, 0, RDP_MPPC_DICT_SIZE
);
88 walker
= g_mppc_dict
.roff
;
91 old_offset
= next_offset
;
103 walker
= data
[i
++] << 24;
116 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
119 if (next_offset
>= RDP_MPPC_DICT_SIZE
)
121 dict
[next_offset
++] = (((uint32
) walker
) >> ((uint32
) 24));
127 /* fetch next 8-bits */
128 if (--walker_len
== 0)
132 walker
= data
[i
++] << 24;
135 /* literal decoding */
142 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
145 if (next_offset
>= RDP_MPPC_DICT_SIZE
)
147 dict
[next_offset
++] = (uint8
) (walker
>> 24 | 0x80);
156 if (--walker_len
< (big
? 3 : 2))
160 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
166 /* offset decoding where offset len is:
167 -63: 11111 followed by the lower 6 bits of the value
168 64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
169 320-2367: 1110 followed by lower 11 bits of the value ( value - 320 )
170 2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 )
172 switch (((uint32
) walker
) >> ((uint32
) 29))
175 for (; walker_len
< 9; walker_len
+= 8)
179 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
182 match_off
= ((uint32
) walker
) >> ((uint32
) 26);
187 case 6: /* 64 - 319 */
188 for (; walker_len
< 11; walker_len
+= 8)
192 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
196 match_off
= (((uint32
) walker
) >> ((uint32
) 24)) + 64;
202 case 4: /* 320 - 2367 */
203 for (; walker_len
< 13; walker_len
+= 8)
207 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
211 match_off
= (((uint32
) walker
) >> ((uint32
) 21)) + 320;
216 default: /* 2368 - 65535 */
217 for (; walker_len
< 17; walker_len
+= 8)
221 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
225 match_off
= (((uint32
) walker
) >> ((uint32
) 16)) + 2368;
233 /* offset decoding where offset len is:
234 -63: 1111 followed by the lower 6 bits of the value
235 64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
236 320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
238 switch (((uint32
) walker
) >> ((uint32
) 30))
245 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
249 match_off
= ((uint32
) walker
) >> ((uint32
) 26);
254 case 2: /* 64 - 319 */
255 for (; walker_len
< 10; walker_len
+= 8)
259 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
263 match_off
= (((uint32
) walker
) >> ((uint32
) 24)) + 64;
268 default: /* 320 - 8191 */
269 for (; walker_len
< 14; walker_len
+= 8)
273 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
276 match_off
= (walker
>> 18) + 320;
286 walker
= data
[i
++] << 24;
290 /* decode length of match */
293 { /* special case - length of 3 is in bit 0 */
300 /* this is how it works len of:
301 4-7: 10 followed by 2 bits of the value
302 8-15: 110 followed by 3 bits of the value
303 16-31: 1110 followed by 4 bits of the value
304 32-63: .... and so forth
313 i.e. 4097 is encoded as: 111111111110 000000000001
316 match_bits
= big
? 14 : 11; /* 11 or 14 bits of value at most */
320 if (--walker_len
== 0)
324 walker
= data
[i
++] << 24;
329 if (--match_bits
== 0)
335 match_len
= (big
? 16 : 13) - match_bits
;
337 if (--walker_len
< match_len
)
339 for (; walker_len
< match_len
; walker_len
+= 8)
345 walker
|= (data
[i
++] & 0xff) << (24 - walker_len
);
349 match_bits
= match_len
;
351 ((walker
>> (32 - match_bits
)) & (~(-1 << match_bits
))) | (1 <<
353 walker
<<= match_bits
;
354 walker_len
-= match_bits
;
356 if (next_offset
+ match_len
>= RDP_MPPC_DICT_SIZE
)
360 /* memory areas can overlap - meaning we can't use memXXX functions */
361 k
= (next_offset
- match_off
) & (big
? 65535 : 8191);
364 dict
[next_offset
++] = dict
[k
++];
366 while (--match_len
!= 0);
370 /* store history offset */
371 g_mppc_dict
.roff
= next_offset
;
374 *rlen
= next_offset
- old_offset
;