mppc.c@ 77807

Last change on this file since 77807 was 55123, checked in by vboxsync, 10 years ago
rdesktop 1.8.3 modified for VBox
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 8.9 KB

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

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

source: vbox/trunk/src/VBox/RDP/client-1.8.4/mppc.c@ 77807

Download in other formats: