trunk/rdesktop/mppc.c

/* -*- c-basic-offset: 8 -*-
   rdesktop: A Remote Desktop Protocol client.
   Protocol services - RDP decompression
   Copyright (C) Matthew Chapman 1999-2005

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include <stdio.h>
#include <string.h>

#include "rdesktop.h"

/* mppc decompression                       */
/* http://www.faqs.org/rfcs/rfc2118.html    */

/* Contacts:                                */

/* hifn contact mentioned in the faq is     */
/* Robert Friend rfriend at hifn dot com    */

/* if you have questions regarding MPPC     */
/* our contact is                           */
/* Guus Dhaeze  GDhaeze at hifn dot com     */

/* Licensing:                               */

/* decompression is alright as long as we   */
/* don't compress data                      */

/* Algorithm: */

/* as the rfc states the algorithm seems to */
/* be LZ77 with a sliding buffer            */
/* that is empty at init.                   */

/* the algorithm is called LZS and is       */
/* patented for another couple of years.    */

/* more information is available in         */
/* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */


RDPCOMP g_mppc_dict;

int
mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen)
{
        int k, walker_len = 0, walker;
        uint32 i = 0;
        int next_offset, match_off;
        int match_len;
        int old_offset, match_bits;

        uint8 *dict = g_mppc_dict.hist;

        if ((ctype & RDP_MPPC_COMPRESSED) == 0)
        {
                *roff = 0;
                *rlen = clen;
                return 0;
        }

        if ((ctype & RDP_MPPC_RESET) != 0)
        {
                g_mppc_dict.roff = 0;
        }

        if ((ctype & RDP_MPPC_FLUSH) != 0)
        {
                memset(dict, 0, RDP_MPPC_DICT_SIZE);
                g_mppc_dict.roff = 0;
        }

        *roff = 0;
        *rlen = 0;

        walker = g_mppc_dict.roff;

        next_offset = walker;
        old_offset = next_offset;
        *roff = old_offset;
        if (clen == 0)
                return 0;
        clen += i;

        do
        {
                if (walker_len == 0)
                {
                        if (i >= clen)
                                break;
                        walker = data[i++] << 24;
                        walker_len = 8;
                }
                if (walker >= 0)
                {
                        if (walker_len < 8)
                        {
                                if (i >= clen)
                                {
                                        if (walker != 0)
                                                return -1;
                                        break;
                                }
                                walker |= (data[i++] & 0xff) << (24 - walker_len);
                                walker_len += 8;
                        }
                        if (next_offset >= RDP_MPPC_DICT_SIZE)
                                return -1;
                        dict[next_offset++] = (((uint32) walker) >> ((uint32) 24));
                        walker <<= 8;
                        walker_len -= 8;
                        continue;
                }
                walker <<= 1;
                /* fetch next 8-bits */
                if (--walker_len == 0)
                {
                        if (i >= clen)
                                return -1;
                        walker = data[i++] << 24;
                        walker_len = 8;
                }
                /* literal decoding */
                if (walker >= 0)
                {
                        if (walker_len < 8)
                        {
                                if (i >= clen)
                                        return -1;
                                walker |= (data[i++] & 0xff) << (24 - walker_len);
                                walker_len += 8;
                        }
                        if (next_offset >= RDP_MPPC_DICT_SIZE)
                                return -1;
                        dict[next_offset++] = (uint8) (walker >> 24 | 0x80);
                        walker <<= 8;
                        walker_len -= 8;
                        continue;
                }

                /* decode offset  */
                /* length pair    */
                walker <<= 1;
                if (--walker_len < 2)
                {
                        if (i >= clen)
                                return -1;
                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                        walker_len += 8;
                }
                /* offset decoding where offset len is:
                   -63: 1111 followed by the lower 6 bits of the value
                   64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
                   320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
                 */
                switch (((uint32) walker) >> ((uint32) 30))
                {
                        case 3: /* - 63 */
                                if (walker_len < 8)
                                {
                                        if (i >= clen)
                                                return -1;
                                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                                        walker_len += 8;
                                }
                                walker <<= 2;
                                match_off = ((uint32) walker) >> ((uint32) 26);
                                walker <<= 6;
                                walker_len -= 8;
                                break;

                        case 2: /* 64 - 319 */
                                for (; walker_len < 10; walker_len += 8)
                                {
                                        if (i >= clen)
                                                return -1;
                                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                                }

                                walker <<= 2;
                                match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
                                walker <<= 8;
                                walker_len -= 10;
                                break;

                        default:        /* 320 - 8191 */
                                for (; walker_len < 14; walker_len += 8)
                                {
                                        if (i >= clen)
                                                return -1;
                                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                                }

                                match_off = (walker >> 18) + 320;
                                walker <<= 14;
                                walker_len -= 14;
                                break;
                }
                if (walker_len == 0)
                {
                        if (i >= clen)
                                return -1;
                        walker = data[i++] << 24;
                        walker_len = 8;
                }

                /* decode length of match */
                match_len = 0;
                if (walker >= 0)
                {               /* special case - length of 3 is in bit 0 */
                        match_len = 3;
                        walker <<= 1;
                        walker_len--;
                }
                else
                {
                        /* this is how it works len of:
                           4-7: 10 followed by 2 bits of the value
                           8-15: 110 followed by 3 bits of the value
                           16-31: 1110 followed by 4 bits of the value
                           32-63: .... and so forth
                           64-127:
                           128-255:
                           256-511:
                           512-1023:
                           1024-2047:
                           2048-4095:
                           4096-8191:

                           i.e. 4097 is encoded as: 111111111110 000000000001
                           meaning 4096 + 1...
                         */
                        match_bits = 11;        /* 11 bits of value at most */
                        do
                        {
                                walker <<= 1;
                                if (--walker_len == 0)
                                {
                                        if (i >= clen)
                                                return -1;
                                        walker = data[i++] << 24;
                                        walker_len = 8;
                                }
                                if (walker >= 0)
                                        break;
                                if (--match_bits == 0)
                                {
                                        return -1;
                                }
                        }
                        while (1);
                        match_len = 13 - match_bits;
                        walker <<= 1;
                        if (--walker_len < match_len)
                        {
                                for (; walker_len < match_len; walker_len += 8)
                                {
                                        if (i >= clen)
                                        {
                                                return -1;
                                        }
                                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                                }
                        }

                        match_bits = match_len;
                        match_len =
                                ((walker >> (32 - match_bits)) & (~(-1 << match_bits))) | (1 <<
                                                                                           match_bits);
                        walker <<= match_bits;
                        walker_len -= match_bits;
                }
                if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
                {
                        return -1;
                }
                /* memory areas can overlap - meaning we can't use memXXX functions */
                k = (next_offset - match_off) & (RDP_MPPC_DICT_SIZE - 1);
                do
                {
                        dict[next_offset++] = dict[k++];
                }
                while (--match_len != 0);
        }
        while (1);

        /* store history offset */
        g_mppc_dict.roff = next_offset;

        *roff = old_offset;
        *rlen = next_offset - old_offset;

        return 0;
}
1	/* -- c-basic-offset: 8 --
2	rdesktop: A Remote Desktop Protocol client.
3	Protocol services - RDP decompression
4	Copyright (C) Matthew Chapman 1999-2005
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	#include <stdio.h>
22	#include <string.h>
23
24	#include "rdesktop.h"
25
26	/* mppc decompression */
27	/* http://www.faqs.org/rfcs/rfc2118.html */
28
29	/* Contacts: */
30
31	/* hifn contact mentioned in the faq is */
32	/* Robert Friend rfriend at hifn dot com */
33
34	/* if you have questions regarding MPPC */
35	/* our contact is */
36	/* Guus Dhaeze GDhaeze at hifn dot com */
37
38	/* Licensing: */
39
40	/* decompression is alright as long as we */
41	/* don't compress data */
42
43	/* Algorithm: */
44
45	/* as the rfc states the algorithm seems to */
46	/* be LZ77 with a sliding buffer */
47	/* that is empty at init. */
48
49	/* the algorithm is called LZS and is */
50	/* patented for another couple of years. */
51
52	/* more information is available in */
53	/* http://www.ietf.org/ietf/IPR/hifn-ipr-draft-friend-tls-lzs-compression.txt */
54
55
56	RDPCOMP g_mppc_dict;
57
58	int
59	mppc_expand(uint8 * data, uint32 clen, uint8 ctype, uint32 * roff, uint32 * rlen)
60	{
61	int k, walker_len = 0, walker;
62	uint32 i = 0;
63	int next_offset, match_off;
64	int match_len;
65	int old_offset, match_bits;
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 < 2)
159	{
160	if (i >= clen)
161	return -1;
162	walker \|= (data[i++] & 0xff) << (24 - walker_len);
163	walker_len += 8;
164	}
165	/* offset decoding where offset len is:
166	-63: 1111 followed by the lower 6 bits of the value
167	64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
168	320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
169	*/
170	switch (((uint32) walker) >> ((uint32) 30))
171	{
172	case 3: /* - 63 */
173	if (walker_len < 8)
174	{
175	if (i >= clen)
176	return -1;
177	walker \|= (data[i++] & 0xff) << (24 - walker_len);
178	walker_len += 8;
179	}
180	walker <<= 2;
181	match_off = ((uint32) walker) >> ((uint32) 26);
182	walker <<= 6;
183	walker_len -= 8;
184	break;
185
186	case 2: /* 64 - 319 */
187	for (; walker_len < 10; walker_len += 8)
188	{
189	if (i >= clen)
190	return -1;
191	walker \|= (data[i++] & 0xff) << (24 - walker_len);
192	}
193
194	walker <<= 2;
195	match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
196	walker <<= 8;
197	walker_len -= 10;
198	break;
199
200	default: /* 320 - 8191 */
201	for (; walker_len < 14; walker_len += 8)
202	{
203	if (i >= clen)
204	return -1;
205	walker \|= (data[i++] & 0xff) << (24 - walker_len);
206	}
207
208	match_off = (walker >> 18) + 320;
209	walker <<= 14;
210	walker_len -= 14;
211	break;
212	}
213	if (walker_len == 0)
214	{
215	if (i >= clen)
216	return -1;
217	walker = data[i++] << 24;
218	walker_len = 8;
219	}
220
221	/* decode length of match */
222	match_len = 0;
223	if (walker >= 0)
224	{ /* special case - length of 3 is in bit 0 */
225	match_len = 3;
226	walker <<= 1;
227	walker_len--;
228	}
229	else
230	{
231	/* this is how it works len of:
232	4-7: 10 followed by 2 bits of the value
233	8-15: 110 followed by 3 bits of the value
234	16-31: 1110 followed by 4 bits of the value
235	32-63: .... and so forth
236	64-127:
237	128-255:
238	256-511:
239	512-1023:
240	1024-2047:
241	2048-4095:
242	4096-8191:
243
244	i.e. 4097 is encoded as: 111111111110 000000000001
245	meaning 4096 + 1...
246	*/
247	match_bits = 11; /* 11 bits of value at most */
248	do
249	{
250	walker <<= 1;
251	if (--walker_len == 0)
252	{
253	if (i >= clen)
254	return -1;
255	walker = data[i++] << 24;
256	walker_len = 8;
257	}
258	if (walker >= 0)
259	break;
260	if (--match_bits == 0)
261	{
262	return -1;
263	}
264	}
265	while (1);
266	match_len = 13 - match_bits;
267	walker <<= 1;
268	if (--walker_len < match_len)
269	{
270	for (; walker_len < match_len; walker_len += 8)
271	{
272	if (i >= clen)
273	{
274	return -1;
275	}
276	walker \|= (data[i++] & 0xff) << (24 - walker_len);
277	}
278	}
279
280	match_bits = match_len;
281	match_len =
282	((walker >> (32 - match_bits)) & (~(-1 << match_bits))) \| (1 <<
283	match_bits);
284	walker <<= match_bits;
285	walker_len -= match_bits;
286	}
287	if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
288	{
289	return -1;
290	}
291	/* memory areas can overlap - meaning we can't use memXXX functions */
292	k = (next_offset - match_off) & (RDP_MPPC_DICT_SIZE - 1);
293	do
294	{
295	dict[next_offset++] = dict[k++];
296	}
297	while (--match_len != 0);
298	}
299	while (1);
300
301	/* store history offset */
302	g_mppc_dict.roff = next_offset;
303
304	*roff = old_offset;
305	*rlen = next_offset - old_offset;
306
307	return 0;
308	}