mppc.c@ 32767

Last change on this file since 32767 was 11982, checked in by vboxsync, 16 years ago
All: license header changes for 2.0 (OSE headers, add Sun GPL/LGPL disclaimer)
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 9.0 KB

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

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/RDP/client/mppc.c@ 32767

Download in other formats: