rdesktop/trunk/mppc.c

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

   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;
        RD_BOOL big = ctype & RDP_MPPC_BIG ? True : False;

        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 < (big ? 3 : 2))
                {
                        if (i >= clen)
                                return -1;
                        walker |= (data[i++] & 0xff) << (24 - walker_len);
                        walker_len += 8;
                }

                if (big)
                {
                        /* offset decoding where offset len is:
                           -63: 11111 followed by the lower 6 bits of the value
                           64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
                           320-2367: 1110 followed by lower 11 bits of the value ( value - 320 )
                           2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 )
                         */
                        switch (((uint32) walker) >> ((uint32) 29))
                        {
                                case 7: /* - 63 */
                                        for (; walker_len < 9; walker_len += 8)
                                        {
                                                if (i >= clen)
                                                        return -1;
                                                walker |= (data[i++] & 0xff) << (24 - walker_len);
                                        }
                                        walker <<= 3;
                                        match_off = ((uint32) walker) >> ((uint32) 26);
                                        walker <<= 6;
                                        walker_len -= 9;
                                        break;

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

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

                                case 5:
                                case 4: /* 320 - 2367 */
                                        for (; walker_len < 13; walker_len += 8)
                                        {
                                                if (i >= clen)
                                                        return -1;
                                                walker |= (data[i++] & 0xff) << (24 - walker_len);
                                        }

                                        walker <<= 2;
                                        match_off = (((uint32) walker) >> ((uint32) 21)) + 320;
                                        walker <<= 11;
                                        walker_len -= 13;
                                        break;

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

                                        walker <<= 1;
                                        match_off = (((uint32) walker) >> ((uint32) 16)) + 2368;
                                        walker <<= 16;
                                        walker_len -= 17;
                                        break;
                        }
                }
                else
                {
                        /* 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 = big ? 14 : 11;     /* 11 or 14 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 = (big ? 16 : 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) & (big ? 65535 : 8191);
                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-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 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	RD_BOOL big = ctype & RDP_MPPC_BIG ? True : False;
67
68	uint8 *dict = g_mppc_dict.hist;
69
70	if ((ctype & RDP_MPPC_COMPRESSED) == 0)
71	{
72	*roff = 0;
73	*rlen = clen;
74	return 0;
75	}
76
77	if ((ctype & RDP_MPPC_RESET) != 0)
78	{
79	g_mppc_dict.roff = 0;
80	}
81
82	if ((ctype & RDP_MPPC_FLUSH) != 0)
83	{
84	memset(dict, 0, RDP_MPPC_DICT_SIZE);
85	g_mppc_dict.roff = 0;
86	}
87
88	*roff = 0;
89	*rlen = 0;
90
91	walker = g_mppc_dict.roff;
92
93	next_offset = walker;
94	old_offset = next_offset;
95	*roff = old_offset;
96	if (clen == 0)
97	return 0;
98	clen += i;
99
100	do
101	{
102	if (walker_len == 0)
103	{
104	if (i >= clen)
105	break;
106	walker = data[i++] << 24;
107	walker_len = 8;
108	}
109	if (walker >= 0)
110	{
111	if (walker_len < 8)
112	{
113	if (i >= clen)
114	{
115	if (walker != 0)
116	return -1;
117	break;
118	}
119	walker \|= (data[i++] & 0xff) << (24 - walker_len);
120	walker_len += 8;
121	}
122	if (next_offset >= RDP_MPPC_DICT_SIZE)
123	return -1;
124	dict[next_offset++] = (((uint32) walker) >> ((uint32) 24));
125	walker <<= 8;
126	walker_len -= 8;
127	continue;
128	}
129	walker <<= 1;
130	/* fetch next 8-bits */
131	if (--walker_len == 0)
132	{
133	if (i >= clen)
134	return -1;
135	walker = data[i++] << 24;
136	walker_len = 8;
137	}
138	/* literal decoding */
139	if (walker >= 0)
140	{
141	if (walker_len < 8)
142	{
143	if (i >= clen)
144	return -1;
145	walker \|= (data[i++] & 0xff) << (24 - walker_len);
146	walker_len += 8;
147	}
148	if (next_offset >= RDP_MPPC_DICT_SIZE)
149	return -1;
150	dict[next_offset++] = (uint8) (walker >> 24 \| 0x80);
151	walker <<= 8;
152	walker_len -= 8;
153	continue;
154	}
155
156	/* decode offset */
157	/* length pair */
158	walker <<= 1;
159	if (--walker_len < (big ? 3 : 2))
160	{
161	if (i >= clen)
162	return -1;
163	walker \|= (data[i++] & 0xff) << (24 - walker_len);
164	walker_len += 8;
165	}
166
167	if (big)
168	{
169	/* offset decoding where offset len is:
170	-63: 11111 followed by the lower 6 bits of the value
171	64-319: 11110 followed by the lower 8 bits of the value ( value - 64 )
172	320-2367: 1110 followed by lower 11 bits of the value ( value - 320 )
173	2368-65535: 110 followed by lower 16 bits of the value ( value - 2368 )
174	*/
175	switch (((uint32) walker) >> ((uint32) 29))
176	{
177	case 7: /* - 63 */
178	for (; walker_len < 9; walker_len += 8)
179	{
180	if (i >= clen)
181	return -1;
182	walker \|= (data[i++] & 0xff) << (24 - walker_len);
183	}
184	walker <<= 3;
185	match_off = ((uint32) walker) >> ((uint32) 26);
186	walker <<= 6;
187	walker_len -= 9;
188	break;
189
190	case 6: /* 64 - 319 */
191	for (; walker_len < 11; walker_len += 8)
192	{
193	if (i >= clen)
194	return -1;
195	walker \|= (data[i++] & 0xff) << (24 - walker_len);
196	}
197
198	walker <<= 3;
199	match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
200	walker <<= 8;
201	walker_len -= 11;
202	break;
203
204	case 5:
205	case 4: /* 320 - 2367 */
206	for (; walker_len < 13; walker_len += 8)
207	{
208	if (i >= clen)
209	return -1;
210	walker \|= (data[i++] & 0xff) << (24 - walker_len);
211	}
212
213	walker <<= 2;
214	match_off = (((uint32) walker) >> ((uint32) 21)) + 320;
215	walker <<= 11;
216	walker_len -= 13;
217	break;
218
219	default: /* 2368 - 65535 */
220	for (; walker_len < 17; walker_len += 8)
221	{
222	if (i >= clen)
223	return -1;
224	walker \|= (data[i++] & 0xff) << (24 - walker_len);
225	}
226
227	walker <<= 1;
228	match_off = (((uint32) walker) >> ((uint32) 16)) + 2368;
229	walker <<= 16;
230	walker_len -= 17;
231	break;
232	}
233	}
234	else
235	{
236	/* offset decoding where offset len is:
237	-63: 1111 followed by the lower 6 bits of the value
238	64-319: 1110 followed by the lower 8 bits of the value ( value - 64 )
239	320-8191: 110 followed by the lower 13 bits of the value ( value - 320 )
240	*/
241	switch (((uint32) walker) >> ((uint32) 30))
242	{
243	case 3: /* - 63 */
244	if (walker_len < 8)
245	{
246	if (i >= clen)
247	return -1;
248	walker \|= (data[i++] & 0xff) << (24 - walker_len);
249	walker_len += 8;
250	}
251	walker <<= 2;
252	match_off = ((uint32) walker) >> ((uint32) 26);
253	walker <<= 6;
254	walker_len -= 8;
255	break;
256
257	case 2: /* 64 - 319 */
258	for (; walker_len < 10; walker_len += 8)
259	{
260	if (i >= clen)
261	return -1;
262	walker \|= (data[i++] & 0xff) << (24 - walker_len);
263	}
264
265	walker <<= 2;
266	match_off = (((uint32) walker) >> ((uint32) 24)) + 64;
267	walker <<= 8;
268	walker_len -= 10;
269	break;
270
271	default: /* 320 - 8191 */
272	for (; walker_len < 14; walker_len += 8)
273	{
274	if (i >= clen)
275	return -1;
276	walker \|= (data[i++] & 0xff) << (24 - walker_len);
277	}
278
279	match_off = (walker >> 18) + 320;
280	walker <<= 14;
281	walker_len -= 14;
282	break;
283	}
284	}
285	if (walker_len == 0)
286	{
287	if (i >= clen)
288	return -1;
289	walker = data[i++] << 24;
290	walker_len = 8;
291	}
292
293	/* decode length of match */
294	match_len = 0;
295	if (walker >= 0)
296	{ /* special case - length of 3 is in bit 0 */
297	match_len = 3;
298	walker <<= 1;
299	walker_len--;
300	}
301	else
302	{
303	/* this is how it works len of:
304	4-7: 10 followed by 2 bits of the value
305	8-15: 110 followed by 3 bits of the value
306	16-31: 1110 followed by 4 bits of the value
307	32-63: .... and so forth
308	64-127:
309	128-255:
310	256-511:
311	512-1023:
312	1024-2047:
313	2048-4095:
314	4096-8191:
315
316	i.e. 4097 is encoded as: 111111111110 000000000001
317	meaning 4096 + 1...
318	*/
319	match_bits = big ? 14 : 11; /* 11 or 14 bits of value at most */
320	do
321	{
322	walker <<= 1;
323	if (--walker_len == 0)
324	{
325	if (i >= clen)
326	return -1;
327	walker = data[i++] << 24;
328	walker_len = 8;
329	}
330	if (walker >= 0)
331	break;
332	if (--match_bits == 0)
333	{
334	return -1;
335	}
336	}
337	while (1);
338	match_len = (big ? 16 : 13) - match_bits;
339	walker <<= 1;
340	if (--walker_len < match_len)
341	{
342	for (; walker_len < match_len; walker_len += 8)
343	{
344	if (i >= clen)
345	{
346	return -1;
347	}
348	walker \|= (data[i++] & 0xff) << (24 - walker_len);
349	}
350	}
351
352	match_bits = match_len;
353	match_len =
354	((walker >> (32 - match_bits)) & (~(-1 << match_bits))) \| (1 <<
355	match_bits);
356	walker <<= match_bits;
357	walker_len -= match_bits;
358	}
359	if (next_offset + match_len >= RDP_MPPC_DICT_SIZE)
360	{
361	return -1;
362	}
363	/* memory areas can overlap - meaning we can't use memXXX functions */
364	k = (next_offset - match_off) & (big ? 65535 : 8191);
365	do
366	{
367	dict[next_offset++] = dict[k++];
368	}
369	while (--match_len != 0);
370	}
371	while (1);
372
373	/* store history offset */
374	g_mppc_dict.roff = next_offset;
375
376	*roff = old_offset;
377	*rlen = next_offset - old_offset;
378
379	return 0;
380	}